# RabbitFarm

### 2021-05-16

#### The Weekly Challenge 112 (Prolog Solutions)

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

## Part 2

You are given \$n steps to climb. Write a script to find out the distinct ways to climb to the top. You are allowed to climb either 1 or 2 steps at a time.

### Solution

``````
:-initialization(main).

steps --> [].
steps --> step, steps.
step  --> [0]; [1]; [2].

sum_steps(Steps, Goal):-
length(Steps, Goal),
phrase(steps, Steps),
sum_list(Steps, Goal).

zero_remove([], []).
zero_remove([H|T], [ZR_H|ZR_T]):-
delete(H, 0, ZR_H),
zero_remove(T, ZR_T).

main:-
findall(Steps, sum_steps(Steps, 4), S),
zero_remove(S, SZR),
sort(SZR, SZR_Unique),
write(SZR_Unique), nl,
halt.
``````

### Sample Run

``````
\$ gprolog --consult-file prolog/ch-2.p
GNU Prolog 1.4.5 (32 bits)
Compiled Dec  3 2020, 00:37:14 with gcc
By Daniel Diaz
[[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]
``````

### Notes

I've been trying to do more with DCGs. This is not the most algorithmically pure use of DCG's but the point here was just to try something new.

Overview of this brute force approach with DCGs:

• Generate all lists of numbers of length `Goal` using digits 0, 1, and 2.
• Keep all those lists that sum to `Goal`
• Remove zeroes from these matching lists
• Remove duplicate lists (using `sort/2`)

## References

Challenge 112

posted at: 18:20 by: Adam Russell | path: /prolog | permanent link to this entry