pythonrecursioncommon-lispcoin-change# Converting a recursion problem code from Python to Common Lisp

## Update:

# Correctness

# Efficiency

# Style

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?

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>.
```

Solution

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) ...)
```

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.

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)))))))))
```

- Python Jinja2 LaTeX Table
- Getting attributes of a class
- How can I print many significant figures in Python?
- How to allow list append() method to return the new list
- Calculate Last Friday of Month in Pandas
- Python type hint for Iterable[str] that isn't str
- How to iterate over a list in chunks
- How to exit the entire application from a Python thread?
- Running shell command and capturing the output
- How do I pass a variable by reference?
- Convert range(r) to list of strings of length 2 in python
- How can I get the start and end dates for each week?
- how to use send_message() in python-telegram-bot
- Python conditional replacement based on element type
- How can I count the number of items in an arbitrary iterable (such as a generator)?
- Find longest consecutive range of numbers in list
- Insert text in braces with asyncpg
- How does one put a link / url to the web-site's home page in Django?
- How to determine if a path is a subdirectory of another?
- Custom Keybindings for Ipython terminal
- FastAPI asynchronous background tasks blocks other requests?
- How to make sure that information from one file is duplicated into several text documents, without specific lines
- Installing a Python environment with Anaconda
- sklearn pipeline model predicting same results for all input
- Brew command not found after installing Anaconda Python
- How to get an XPath from selenium webelement or from lxml?
- Pipe PuTTY console to Python script
- How to align the axes of a figure in matplotlib?
- Persist ParentDocumentRetriever of langchain
- How to reset index in a pandas dataframe?