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
Copyright (C) 1999-2020 Daniel Diaz
compiling /home/adamcrussell/Projects/perlweeklychallenge-club/challenge-112/adam-russell/prolog/ch-2.p for byte code...
/home/adamcrussell/Projects/perlweeklychallenge-club/challenge-112/adam-russell/prolog/ch-2.p compiled, 22 lines read - 2790 bytes written, 43 ms
[[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
posted at: 18:20 by: Adam Russell | path: /prolog | permanent link to this entry