Square Triple
February 14, 2020
Our algorithm finds all pairs, then checks if the square root of the product is in the list:
(define (f xs)
(list-of (list x y z)
(x in xs)
(y in xs)
(< x y)
(z2 is (* x y))
(z is (isqrt z2))
(= (* z z) z2)
(member z xs)))
We eliminate duplicates by insisting that x < y. Here’s an example:
> (f (range 1 20)) ((1 4 2) (1 9 3) (1 16 4) (2 8 4) (2 18 6) (3 12 6) (4 9 6) (4 16 8) (8 18 12) (9 16 12))
That takes time O(n³); n * n to form the pairs and another factor of n to search the list. We could reduce that to O(n²) by first inserting the list items in a hash table and checking membership there. Another improvement is a quick exit if the product exceeds the maximum list item. We’ll leave those improvements as an exercise to the reader.
You can run the program at https://ideone.com/L7itmh.
Programming Praxis 
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…
use strict; use feature qw(say); my @ints = 1..50; ## Test data... my %squares = map { $_*$_ => $_ } @ints; ## Use hash to store possible squares (value is sqrt) say map { my $a = $_; ## Nested map store copy of outer key... map { join ',', $a, $_, $squares{$a*$_}.' ' } ## Display three values - sqrt is value of hash keyed by square grep { exists $squares{$a*$_} } ## Now check to see if the product is a square.. grep { $a < $_ } ## Quick filter only want 1st no < 2nd no @ints } @ints;Here’s an O(n²) solution that doesn’t require any auxiliary storage. Assumes input is sorted and all positive:
# If ab = z^2 with a != b, can assume a < z < b, so # keep 2 pointers into the list and keep track of the # product of values pointed to - if too high, the lower # pointer needs to be increased, if too low, the higher: def triples(a): n = len(a) for i in range(1,n-1): target = a[i]*a[i] j,k = i-1,i+1 while j >= 0 and k < n: product = a[j]*a[k] if product > target: j = j-1 elif product < target: k = k+1 else: yield(a[j],a[k],a[i]) j,k = j-1,k+1 # [(1, 4, 2), (1, 9, 3), (1, 16, 4), (2, 8, 4), (2, 18, 6), # (3, 12, 6), (4, 9, 6), (4, 16, 8), (8, 18, 12), (9, 16, 12)] print(sorted(list(triples(range(1,20)))))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.
from collections import defaultdict def square_triple(input): output = [] roots = defaultdict(list) for x in input: roots[x * x].append(x) for x in input: for y in input: if x == y: continue for z in roots[x * y]: if x != z and y != z: output.append((x, y, z)) return output for triple in square_triple(range(-8, 9)): print(triple)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 single non-negative value)
Klong version
:" Number from 1 to 20" list::1+!20 [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20] :" Get all pairs of number in list" pairs::{x,:\list}'list [[[1 1] [1 2] [1 3] [1 4] [1 5] [1 6] [1 7] [1 8] [1 9] [1 10]...]] :" Flatten the list" l::,/pairs::{x,:\list}'list [[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] ...] :" Only those pairs where the first # < second # l::l@&{~(x@0)=x@1}'l::,/pairs::{x,:\list}'list [[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]...] :" Only those pairs where product is square of one of the number in the list" l::l@&{#sqrs?*/x}'l::l@&{~(x@0)=x@1}'l::,/pairs::{x,:\list}'list [[1 4] [1 9] [1 16] [2 8] [2 18] [3 12] [4 1] [4 9] [4 16] [5 20] [8 2] [8 18] [9 1] [9 4] [9 16] [12 3] [16 1] [16 4] [16 9] [18 2] [18 8] [20 5]] :" Get rid of duplicates" l@&{(x@0)<x@1}'l::l@&{#sqrs?*/x}'l::l@&{~(x@0)=x@1}'l::,/pairs::{x,:\list}'list [[1 4] [1 9] [1 16] [2 8] [2 18] [3 12] [4 9] [4 16] [5 20] [8 18] [9 16]] :" Add square root of product" {x,_(*/x)^0.5}'l@&{(x@0)<x@1}'l::l@&{#sqrs?*/x}'l::l@&{~(x@0)=x@1}'l::,/pairs::{x,:\list}'list [[1 4 2] [1 9 3] [1 16 4] [2 8 4] [2 18 6] [3 12 6] [4 9 6] [4 16 8] [5 20 10] [8 18 12] [9 16 12]]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.
list::[-2 1 2 4] [-2 1 2 4] pairs::pairs@&{~(x@0)=x@1}'pairs::,/{x,:\list}'list [[-2 1] [-2 2] [-2 4] [1 -2] [1 2] [1 4] [2 -2] [2 1] [2 4] [4 -2] [4 1] [4 2]] {(x@1),(x@2),x@0}'triples@&{(x@1)<x@2}'triples::triples@&{((x@0)^2)=((x@1)*x@2)}'triples::,/{x,:\pairs}'list [[1 4 -2] [1 4 2]]This is a common lisp solution. It assumes the input list is sorted in accending order.
(defun sol (ns) (flet ((fn (xs) (let ((x (car xs)) (ys (cdr xs)) (res nil)) (dolist (y ys res) (let ((z (sqrt (* x y)))) (when (find z ys :test #'=) (push (list x y (ceiling z)) res))))))) (mapcon #'fn ns)))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)]