Pythagorean Triples Logic

training
, ,
1

What happens

I 'm solving challenge 54 from CodeAbbey and I’m stuck because a logical failure.

What do you understand or find about that problem

Actually in my immersion process I’m using hy, nonetheless, I wrote a python code trying to understand the logic behind finding pythagorean triples.

This video was really usefull to take in the problem: Pythagorean Triples Generator (Nevertheless, I think that this solution doesn’t encompass all possible universes of triples).

You make any workaround? What did you do?

In the evidences section I’m attaching the python code (just pure logic) that evaluates what triplet satisfy the condition: a + b + c = S where S will be the input from Codeabbey (I’m using just one value, 30 in this case —the triplet is 12 5 13).

I known that values from CodeAbbey will be greater than 10e+7.

Why fails your workaround?

I spent almost all day long trying to generate a nested recursion pseudoloop (and I made it) but I don’t know why it keeps the recursion and doesn’t stop when satisfy realSum == entrySum, also attaching a screenshot of the output.

Evidences

Evidence 1 (Code):

# Generate the triplet with m and n
def genTriplet (m, n):
    a = 2 * m * n
    b = (m * m) - (n * n)
    c = (m * m) + (n * n)
    summ = a + b + c
    return a, b, c, summ

def serieGenerator (m, n, entrySum):
    a,b,c,realSum = genTriplet(m,n)
    if n >= m:
        return
    else:
        if realSum == entrySum:
            return print(m,n,"/","EL TRIANGULO CON SUMA DE LADOS", entrySum, "ES:",a,b,c)
        else:
            print(m,n,"/","sides=",a,b,c,"/","sum=",realSum)
            serieGenerator(m, n+1, entrySum)

def pythaTriplet (limit, m, n, entrySum):
    a,b,c,realSum = genTriplet(m,n)
    if m > limit:
        return
    elif realSum == entrySum:
        return
    else:
        serieGenerator(m, n, entrySum)
        pythaTriplet(limit, m + 1, n, entrySum)
        
# Run the main function with a limit of 10
# 2 and 1 are the first test (because m > n always)
# And the sum of the triplet to find is 30            
pythaTriplet(10, 2, 1, 30)

Evidence 2 (Output):

2 1 / sides= 4 3 5 / sum= 12
3 1 / sides= 6 8 10 / sum= 24
3 2 / EL TRIANGULO CON SUMA DE LADOS 30 ES: 12 5 13
4 1 / sides= 8 15 17 / sum= 40
4 2 / sides= 16 12 20 / sum= 48
4 3 / sides= 24 7 25 / sum= 56
5 1 / sides= 10 24 26 / sum= 60
5 2 / sides= 20 21 29 / sum= 70
5 3 / sides= 30 16 34 / sum= 80
5 4 / sides= 40 9 41 / sum= 90
...
...
10 1 / sides= 20 99 101 / sum= 220
10 2 / sides= 40 96 104 / sum= 240
10 3 / sides= 60 91 109 / sum= 260
10 4 / sides= 80 84 116 / sum= 280
10 5 / sides= 100 75 125 / sum= 300
10 6 / sides= 120 64 136 / sum= 320
10 7 / sides= 140 51 149 / sum= 340
10 8 / sides= 160 36 164 / sum= 360
10 9 / sides= 180 19 181 / sum= 380

I need help with

Is not totally evident why the recursion never stop, Why is that? I’m assuming that when realSum == entrySum it should stop…but no, it doesn’t.

A logical, theoric or specific help would be great hand.

Thanks!

2

UPDATE 210809

What I found:

I corrected the leak by which the recursion never stops, and also transcript the logical thinking to hy.

I need help with:

After “solving” the logical issue about finding triples (also the doubt keeps in the air: “what if the input sum is’nt catched by the formula postuled?”). Arise a new issue. The real inputs of the problem are higher than 10e+7, so a number bigger as 12819482 would make hy collapsed, check the code and error:

Script

(defn genTrip [m n]
  (setv tripValues
  [(* 2 m n) (- (* m m)
  (* n n)) (+ (* m m) (* n n))
  (* (* 2 m) (+ m n))])
  
  (return tripValues))

(defn recursiveLoop [m n entrySum]
  (setv triple (genTrip m n))
  (setv a_side (get triple 0))
  (setv b_side (get triple 1))
  (setv c_side (get triple 2))
  (setv realSum (get triple 3))
  
  (if (>= n m)
    None
    (do
      (if (= realSum entrySum)
        (print m n "/ El triangulo con suma de lados" entrySum "es:" a_side b_side c_side)
        (recursiveLoop m (+ n 1) entrySum)))))

(defn pythaTriplet [limit m n entrySum]
  (setv triple (genTrip m n))
  (setv a_side (get triple 0))
  (setv b_side (get triple 1))
  (setv c_side (get triple 2))
  (setv realSum (get triple 3))

  (if (> m limit)
    None
    (do
      (if (= realSum entrySum)
        (print m n "/ El triangulo con suma de lados" entrySum "es:" a_side b_side c_side)
        (do
          (recursiveLoop m n entrySum)
          (pythaTriplet limit (+ m 1) n entrySum))))))

(pythaTriplet 10 2 1 12)
(pythaTriplet 10 2 1 30)
(pythaTriplet 10 2 1 60)
; Necessarily we need to increase the limit of iterations
(pythaTriplet 1000 2 1 12819482)

Output

2 1 / El triangulo con suma de lados 12 es: 4 3 5
3 2 / El triangulo con suma de lados 30 es: 12 5 13
5 1 / El triangulo con suma de lados 60 es: 10 24 26
                                        ...
                                        ...
                                        ...
RecursionError: maximum recursion depth exceeded

I also change the input to be (pythaTriplet 2000 1900 1 12819482)

Where I change the maximum number of iterations and also m starting from 1900 and not 2, but the same error arise.

Question

  • Is there a better way to optimize this problem?
  • Am I using bad recursion?
  • How to catch all possible triplets? Both primitive as multiples

Thanks to any help!

3

this problem with the “tail” has been touched on several times in the forum, pls check this algorithm - What is tail call optimization? - Stack Overflow

1 Like
4

Thanks for the help Luis! I’m reading about tail recursion and sound great to avoid stack overflow. Nontheless when I implement a simple function as the Factorial of a number (as is mentioned in the link you posted) Hy falls in the same pit.

Code

(defn factTailRec [x]
  (defn go [x accum]
    (if (= x 1) accum
        (go (- x 1) (* x accum))))
  (go x 1))

(print (factTailRec 999))

Output

Traceback (most recent call last):
                              ...
                              ...
                              ...
RecursionError: maximum recursion depth exceeded in comparison

Do I have to configure some limits in my virtual machine? Or why the tail call optimization is not working in my code?

Thank you again!!!

5

Pls, change your language to lfe that is allowed in your policy, while we find a solution.

6

SOLUTION

Thanks to Computerphile for the beauty explanation of Tail Optimization Call (TOC) I solved the issue of memory stack.

Also, thanks to Hy documentation for the loop explanation. I left this snipet of code, where I made a double loop using recursion and TOC, I’m really proud of make this:

Code

(require [hy.contrib.loop [loop]])

(defn secondLoop [limit m n]
  (loop [[j m] [n_count 1]]
    (if (= j 1)
      None
        (do
          (print m "--" n_count)
          (recur (dec j) (inc n_count))))))

(defn mainLoop [limit m n]
  (loop [[i limit] [m_count m]]
    (if (= i 0)
      None
      (if (> m_count limit)
        None
        (do
          (secondLoop limit m_count n)
          (recur (dec i) (inc m_count)))))))

(mainLoop 100 2 1)

OUTPUT

2 -- 1
3 -- 1
3 -- 2
4 -- 1
4 -- 2
4 -- 3
5 -- 1
5 -- 2
5 -- 3
5 -- 4
  ...
  ...
  ...
100 -- 85
100 -- 86
100 -- 87
100 -- 88
100 -- 89
100 -- 90
100 -- 91
100 -- 92
100 -- 93
100 -- 94
100 -- 95
100 -- 96
100 -- 97
100 -- 98
100 -- 99

This is a really cool way to obtain extremly big number without running out of memory.

7

Hello! it’s good that you get a solution by your own!, however, I want to let you know that the real problem here is that Python does not support TCO directly (though there are libraries that could help solve that problem), so since hy is a dialect of python, initially it would not support TOC either

However, I didn’t know that Hy had implemented a solution that allows you to create functions that use tail-call optimization, that’s the good part here, with this function you shouldn’t run into the stack overflow problem as long as you implement a suitable TCO solution

The following is the same implementation of the above-quoted snippet (which previously had a stack overflow), using the loop function, you can check that you will not get a stack overflow with such a number of recursive calls

(require [hy.contrib.loop [loop]])
(defn factorial [n]
  (loop [[i n] [acc 1]]
    (if (= i 0)
      acc
      (recur (dec i) (* acc i)))))

(print (factorial 1000))

I made this clarification since a possible misunderstanding of the problem could lead you to add unnecessary complexity in your code

thx for share with us your solution

1 Like