Remix.run Logo
nemoniac 6 days 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
bmacho 6 days ago | parent | next [-]

It 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 6 days ago | parent | prev [-]

If 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