2 ms·
The first code example on that page claims to solve "the 3SUM problem". According to [1], "the 3SUM problem asks if a given set of n real numbers contains thre
by nemoniac 1y ago
The first code example on that page claims to solve "the 3SUM problem".
According to [1], "the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero."
It's not clear to me what problem the Janet code solves but it's clearly not that 3SUM problem.
On the example input of
@[2 4 1 3 8 7 -3 -1 12 -5 -8]
it outputs
@[@[6 1 7] @[2 5 10] @[1 2 9] @[4 6 9] @[3 0 9] @[6 2 0]]
For what it's worth, here's some Common Lisp code that does solve the 3SUM problem in O(n^2).
(defun 3sum (a)
(let ((h (make-hash-table))
(len (length a)))
(dotimes (i len)
(setf (gethash (aref a i) h) t))
(dotimes (i len)
(dotimes (j i)
(when (gethash (- (+ (aref a i) (aref a j))) h)
(return-from 3sum t))))))
(3sum #(2 4 1 3 8 7 -3 -1 12 -5 -8))
;; => t
[1] https://en.wikipedia.org/wiki/3SUM https://en.wikipedia.org/wiki/3SUM
- bmacho 1y agoIt outputs the indices corresponding to the solution. E.g. @[6 1 7] == A[6], A[1], A[7] == -3, 4, -1 @[2 5 10] == == 1, 7, -8
- lispitillo 1y agoIf you want a one line code, in J, for the 42 solutions: _ 11 11 #:,I. 0=,a+/,+/~ a=: 2 4 1 3 8 7 _3 _1 12 _5 _8 Or the 8 solutions in a 2x12 matrix: 2 12 $, ~. (/:~)"1 ({&a) _ 11 11 #:,I. 0=,a+/,+/~ a=: 2 4 1 3 8 7 _3 _1 12 _5 _8 _3 1 2 _5 2 3 _1 _1 2 _8 4 4 _5 1 4 _3 _1 4 _8 1 7 _5 _3 8