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:

References

Challenge 112

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