Little Prolog challenge

Another candidate for Paul Bissex’s Let’s play a game: BASIC vs. Ruby vs. Python vs. PHP, this time I implemented the REVERSE game in Prolog. I thought my LISP was a bit rusty when I started my Little LISP challenge. Where does that put my Prolog? Ashes?

I had to peruse the SWI Prolog documentation and google extensively to end up with these lines. I do not know whether this program is portable or not, it was tested on SWI Prolog 5.2.13. I welcome any criticism to improve it.

First a couple of utility functions:

%% choose(List, Elt) - chooses a random element
%% in List and unifies it with Elt.
choose([], []).
choose(List, Elt) :-
        length(List, Length),
        random(0, Length, Index),
        nth0(Index, List, Elt).

%% shuffle(ListIn, ListOut) - randomly shuffles
%% ListIn and unifies it with ListOut
shuffle([], []).
shuffle(List, [Element|Rest]) :-
        choose(List, Element),
        delete(List, Element, NewList),
        shuffle(NewList, Rest).

%% split(List, Index, Front, Back) - splits List
%% at index Index and unifies the first list with
%% Front and the second one with Back
split(List, 0, [], List).
split([Head|Tail], Index, [Head|HeadList], TailList) :-
        NewIndex is Index - 1,
        split(Tail, NewIndex, HeadList, TailList).

Now the game itself:

playgame(N) :-
        numlist(1, N, InitialState),
        shuffle(InitialState, State),
        play(State, Moves),
        format('Done! That took ~d steps.~n', Moves).

play(State, 0) :- sort(State, State).
play(State, Moves) :-
        format('~w~nHow many to swap? ', [State]),
        read(HowMany),
        split(State, HowMany, Front, Back),
        reverse(Front, ReversedFront),
        append(ReversedFront, Back, NewState),
        play(NewState, NewMoves),
        Moves is NewMoves + 1.

I had forgotten how Prolog can be so elegant and how satisfying writing Prolog code can be. I am particularly proud of the clause that checks whether a given state is the goal state, play(State, 0) :- sort(State, State).. Any questions, critics or ideas?

Updated 06/08/06

Markus Triska mailed me a couple of improvements. First of all he points out that choose([], []). is incorrect. I can only agree!
He also offers a far cleaner implementation of the split predicate, using append/3:

split(List, Index, Front, Back) :-
	length(Front, Index),
	append(Front, Back, List).

Finally, he optimizes play by making it tail-recursive:

play(State, M, M) :- sort(State, State).
play(State, M0, M) :-
	format('~w~nHow many to swap? ', [State]),
	read(HowMany),
	split(State, HowMany, Front, Back),
	reverse(Front, ReversedFront),
	append(ReversedFront, Back, NewState),
	succ(M0, M1),
	play(NewState, M1, M).

This requires a slight modification in the playgame predicate:

playgame(N) :-
	numlist(1, N, InitialState),
	shuffle(InitialState, State),
	play(State, 0, Moves),
	format('Done! That took ~d steps.~n', Moves).

Thanks Markus!

About these ads