Converting a recursion problem code from Python to Common Lisp

Question

I'm trying to convert a recursion problem written in Python (the 4th problem here see its repo page for details) into (Common) Lisp

Here is the Python code which I've edited slightly for readability:

def coin(target,coins,res):
    # Default output to target
    min_coins = target
    # Base Case
    if target in coins:
        res[target] = 1
        return 1
    # Return a known result if it happens to be greater than 1
    elif res[target] > 0:
        return res[target]
    else:
        # for every coin value that is <= than target
        for i in [c for c in coins if c <= target]:
            num_coins = 1 + coin(target-i,coins,res)
            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:
                min_coins = num_coins
                res[target] = min_coins
    return min_coins

target = 14
coins = [1,3,5]
res = [0]*(target+1)
print(coin(target,coins,res))
# => returns 4  ( 1 x 1, 1 x 3, 2 x 5)

Here is the Lisp code I've written:

(defun coin (target coins res)
  (let ((min_coins target))  
    (if (some (lambda (x) (= target x)) coins)
        (progn
          (setf (aref res target) 1)
          1)
      (if (> (aref res target) 0)
          (aref res target)
        (dolist (i (remove-if-not (lambda (x) (<= x target)) coins))
          (let ((num_coins (1+ (coin (- target i) coins res))))
            (when (< num_coins min_coins)
              (setf min_coins num_coins)
              (setf (aref res target) min_coins))
            min_coins))))))

(coin 14 '(1 3 5) (make-array 15 :initial-element 0) )

When it's executed it stops with this error:

The value
  NIL
is not of type
  NUMBER

How to arrange it so that it runs correctly?

Update:

After (trace coin) here is the output:

CL-USER> (coin 14 '(1 3 5) (make-array 15 :initial-element 0) )
  0: (COIN 14 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
    1: (COIN 13 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
      2: (COIN 12 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
        3: (COIN 11 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
          4: (COIN 10 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
            5: (COIN 9 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
              6: (COIN 8 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
                7: (COIN 7 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
                  8: (COIN 6 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
                    9: (COIN 5 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
                    9: COIN returned 1
                    9: (COIN 3 (1 3 5) #(0 0 0 0 0 1 2 0 0 0 0 0 0 0 0))
                    9: COIN returned 1
                    9: (COIN 1 (1 3 5) #(0 0 0 1 0 1 2 0 0 0 0 0 0 0 0))
                    9: COIN returned 1
                  8: COIN returned NIL
; Evaluation aborted on #<TYPE-ERROR expected-type: NUMBER datum: NIL>.

Dunton

You can use (member target coins) instead of some. – Seychelles

Which line is the error happening on? – Seychelles

A series of if/elif/else should be translated to cond rather than nested if. – Seychelles

Updated the OP. Added trace output, if that helps. – Dunton

Yep, the cond should have been used instead if/elif/else I knew it but by the time I've started writing the code, I've forgotten that :) – Dunton

Answer 1

Correctness

Your code fails because your dolist returns nil.

You need to replace

(dolist (i (remove-if-not (lambda (x) (<= x target)) coins)) ...)

with

(dolist (i (remove-if-not (lambda (x) (<= x target)) coins) min_coins) ...)

Efficiency

You are creating gratuitous lists in Python by using [] in for loop and in Lisp by using remove-if-not in dolist. A proverbial "sufficiently smart compiler" should be able to eliminate it, but Python 3 is not smart enough and neither is SBCL.

Style

Code readability matters. I suggest modifying your code:

def coin(target,coins,res):
    # Default output to target
    # Base Case
    if target in coins:
        res[target] = 1
        return 1
    # Return a known result if it happens to be greater than 1
    if res[target] > 0:
        return res[target]
    # for every coin value that is <= than target
    min_coins = target
    for i in target:
        if i <= target:
            num_coins = 1 + coin(target-i,coins,res)
            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:
                min_coins = num_coins
                res[target] = min_coins
    return min_coins

and

(defun coin (target coins res)
  (cond ((find target coins)
         (setf (aref res target) 1))
        ((plusp (aref res target))
         (aref res target))
        (t
         (let ((min-coins target))
           (dolist (i coins min-coins)
             (when (<= i target)
               (let ((num-coins (1+ (coin (- target i) coins res))))
                 (when (< num-coins min-coins)
                   (setf min-coins num-coins)
                   (setf (aref res target) min-coins)))))))))

Countrywide

Or just move min_coins out of the if, just like in the Python. – Seychelles

I've tried it and it worked. I've tried moving min_coins out of the if 's, as @Seychelles suggested and it stopped giving errors but gave wrong results though. So I think the most practical solution is adding the min_coins as a third argument to dolist – Dunton

As per the PS1 Inefficiency remark, about creating gratuitous lists in Python by using [] in for loop: Yes that looks inefficent at first sight but it's a necessary part of the algorithm. Actually, at first I've tried to think of a more efficient algorithm and implement it in Lisp but having failed that I've decided to convert it into Lisp as is. – Dunton

@LarsMalmsteen: my code does not create the extra list but uses a check inside the loop, both in Python and Lisp. Works fine. – Countrywide

Answer 2

A relatively similar version in Common Lisp is this:

(defun coin (target coins res)
  (let ((min-coins target))
    (cond ((member target coins)
           (setf (elt res target) 1)
           (return-from coin 1))
          ((plusp (elt res target))
           (return-from coin (elt res target)))
          (t (loop for i in (loop for c in coins when (<= c target) collect c)
                   for num-coins = (1+ (coin (- target i) coins res))
                   if (< num-coins min-coins)
                     do (setf min-coins num-coins)
                   else
                     do (setf (elt res target) min-coins))))
    (return-from coin min-coins)))

(let* ((target 14)
       (coins  '(1 3 5))
       (res    (make-list (1+ target) :initial-element 0)))
  (print (coin target coins res)))

There are a few basic difference between Lisp and Python. Four of those are:

• in Lisp all expressions return values (zero, one, or more). Thus it is usually not Lisp style to call return or return-from like in Python. To adjust for Lisp style, one can transform the code to a version without returns. But that can introduce errors, if not done carefully. return-from needs the name of the block to return from.

• in Lisp the basic data structure is a singly linked list. In Python it's a king of an array. Thus different operators might be needed and the performance is different. In Lisp things like traversing a list, appending to the end, random access, etc. are costly. For some use this might not be matter, but it is usually preferred to use data structures which fit better to the purpose. So here I have used Lisp lists and it might be useful to replace them with vectors (one-dimensional arrays). There is also the idea of a type sequence, which provides generic operations for lists and vectors. Operations are elt, remove, remove-if, concatenate, map and a bunch of others.

• local variables can't be introduced in the middle of some sequence of expressions. There are special constructs like let needed.

• iteration in Lisp can be done with LOOP

Willms

Even in Lisp one would use vectors when doing random access! – Countrywide

Answer 3

Yea, I did it a different way, but came to a similar conclusion. Added depth parameter to figure out what it was doing during recursion. Then used that to follow the logic in your Lisp script. Used this cheat-sheet for reference https://jtra.cz/stuff/lisp/sclr/index.html

#! /usr/bin/env python3

def coin( target, coins, result, depth ):
    min_coins = target  ##  Default output to target
    print( depth, result )
    if target in coins:  ##  Base Case
        result[ target ] = 1
        return 1
    # Return a known result if it happens to be greater than 1
    elif result[ target ] > 0:
        return result[ target ]
    else:
        # for every coin value that is <= than target
        for i in [ c for c in coins if c <= target ]:
            num_coins = 1 +coin( target -i,  coins,  result,  depth +1 )
            # reset Minimum if we have a new minimum
            if num_coins < min_coins:
                min_coins = num_coins
                result[ target ] = min_coins
    return min_coins

target = 14
coins = [ 1, 3, 5 ]
result = [0] *( target +1 )

print( coin( target, coins, result, 0 ) )
# => returns 4  ( 1 x 1, 1 x 3, 2 x 5)

---

---

#! /usr/bin/sbcl --script

(defun coin (target coins result depth)
    "recursive coin count"
    (let ((min_coins target))  ;;  min_coins = target

        (cond ((member target coins)  ;;  if target in coins:

            (progn 
                (setf (aref result target) 1)  ;;  result[ target ] = 1
                1))  ;;  return 1

            ((> (aref result target) 0)  ;;  elif result[ target ] > 0:
                (aref result target))  ;;  return result[ target ]

            ((progn  ;;  for every coin value that is <= target

                (dolist (i (remove-if-not (lambda (x) (<= x target)) coins))

                    ;;  num_coins = 1 +coin( target -i,  coins,  result,  depth +1 )
                    (let ((num_coins (1+ (coin (- target i) coins result (+ depth 1)))))
 
                      (when (< num_coins min_coins)  ;;  if num_coins < min_coins:

                        (setf min_coins num_coins)  ;;  min_coins = num_coins

                        (setf (aref result target) min_coins))))  ;;  result[ target ] = min_coins

                min_coins))  ;;  return min_coins
        )
    )
)

(defvar c 14)
(print (coin c '(1 3 5) (make-array (+ c 1) :initial-element 0) 0 ) )

Tay