The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
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.
:-initialization(main). steps --> . steps --> step, steps. step --> ; ; . 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.
$ 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]]
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
Goalusing digits 0, 1, and 2.
- Keep all those lists that sum to
- Remove zeroes from these matching lists
- Remove duplicate lists (using