## Square Triple

### February 14, 2020

We have a simple homework problem today:

Given a list of distinct integers, find all triples (

xyz) wherex,yandzare in the list andx*y=z².

Your task is to find the list of triples. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Easiest way to make this o(n2) is to first compute an array of squares and use this to filter results… as usual in Perl…

Here’s an O(n²) solution that doesn’t require any auxiliary storage. Assumes input is sorted and all positive:

Here is my approach to the problem using Julia, as usual: https://pastebin.com/FjqkHhQ7

Although I iterate through the data points using a triple loop, not all combinations are examined since I take advantage of the fact that the integers are distinct (so there is one zero at most), simplifying the whole process. Cheers!

Here’s a O(n^2) solution in Python.

I’ve assumed x, y, z are distinct (e.g., no (x=1,y=1,z=1) nor (x=0, y=2, z=0)), which I think is suggested by the problem specifying a “list of distinct integers” for the input.

Output:

@programmingpraxis, I think that using square roots for this problem can be problematic, since as-is it won’t handle negative values for z.

(where “square roots” in my comment refers to the conventional function that returns a

singlenon-negative value)Klong version

The problem says to find ALL triples, but the model answer finds only half of them.

Nothing whatsoever in the problem says that the numbers are all positive or all non-negative.

In fact by using “integer” instead of “natural number” it suggests that negative numbers are allowed.

Given [-2,1,2,4], (1,4,2) and (1,4,-2) are both legal triples, but the model answer will not find the second.

I thought it might be interesting to explain some of the facilities of the Klong programming language. I like to learn this about other languages – they all seem to have their strengths – and Klong is one of the more unusual ones I’ve come upon.

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

[[1 1] [1 2] [1 3] [1 4] [1 5] [1 6] [1 7] [1 8] [1 9] [1 10] [1 11] [1 12] [1 13] [1 14] [1 15] [1 16] [1 17] [1 18] [1 19] [1 20]]

[4 5 6]

[1 3 5 7 9 11 13 15 17 19]

[0]

[1 2 3]?4

[]

*/[2 3]

6

Richard noticed that the example solution did not find all solutions. Mine didn’t either. Here’s version 2 for Klong.

This is a common lisp solution. It assumes the input list is sorted in accending order.

Sample run:

Python Solution:

def find_triples(int_list):

triples = []

# Loop through all integers in list

for k in range(len(int_list)):

for i in range(len(int_list)):

for j in range(len(int_list)):

# Detect valid pair

if int_list[k] * int_list[i] == int_list[j] ** 2:

same = False

# Check each tuple to see if different permutation of pair is already present

for tup in triples:

if int_list[k] in tup and int_list[i] in tup and int_list[j] in tup:

same = True

break

if not same:

triples.append((int_list[k], int_list[i], int_list[j]))

else:

continue

return triples

print(find_triples(range(1, 15)))

OUTPUT:

[(1, 1, 1), (1, 4, 2), (1, 9, 3), (2, 8, 4), (3, 12, 6), (4, 9, 6), (5, 5, 5), (7, 7, 7), (10, 10, 10), (11, 11, 11), (13, 13, 13), (14, 14, 14)]