CODEWITHSUNDEEP
lispelisp
Wizard
Wizard

Reputation: 22113

A varaible independent its local scope

I tried to solve the twoSum Problem with primitive tools of car and cdr

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

The idea is to take a x from nums, then check if x's complement (target -x) is member of set nums-x

The key logic is 

if ((memberp complement (remove-first x nums)) 
then  (list x complement))

Begin with a helper function try nums

(defun two-sum (nums target)
 (try nums))

The main function:

(defun try (nums)
  (let ((x (car nums))
        (complement (- target x)))
    (cond
     ((null x) '())
     ((memberp complement (remove-first x nums))
      (list x complement))
     (t (try (cdr nums)))
     )))

Then I realize that nums in ((memberp complement (remove-first x nums)) should be stay unchanged and independent from the local scope of let.

How could get such a nums?

memberp and `remove-first'

(defun remove-first (item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

(defun filter (predicate sequence)
  (cond ((null sequence) nil)
        ((funcall predicate (car sequence))
         (cons (car sequence)
               (filter predicate
                       (cdr sequence))))
        (t  (filter predicate
                    (cdr sequence)))))

(defun memberp(item x)
  (cond ((null x) 'false)
        ((equal item (car x)) x)
        (t (memq item (cdr x)))))

Upvotes: 0

Views: 45

Answers (1)

Renzo
Renzo

Reputation: 27424

Here is a simple recursive function to compute the indexes:

(defun two-sum (list target &optional (pos 0))
  (if (null (cdr list))
      nil
      (let ((p (my-position (- target (car list)) list)))
        (if p
            (list pos (+ pos p))
            (two-sum (cdr list) target (1+ pos))))))

(defun my-position (element list &optional (pos 0))
  (cond ((null list) nil)
        ((eql element (car list)) pos)
        (t (my-position element (cdr list) (1+ pos)))))

The function is initially called with the list and the target. The parameter pos, which initially is not passed to the function, is assigned automatically to 0, and in the subsequent calls it will be incremented by one, so that it tracks the index of the current element of the list.

The first condition checks if the list has less than two elements: if it is empty (or its cdr is empty) the result is nil since no solution is possibile (note that in Common Lisp (cdr nil) is nil).

Otherwise we compute the position of the “complement” of the number in the rest of the list (note that position is a primitive function, so I called my-position its rewriting). If the element is present, we return both pos and (+ pos p) (since the position found is relative to the current position), otherwise (my-position returns nil when no element is found) we recur on the rest of the list.

Note that with this method there is no need to consider every time all the elements of the list.

Upvotes: 1

Related Questions