How to solve Lumberjack quiz problem in prolog?

user_13189473 0
Viewed 189

I've read about this problem in the book Olympiads in Informatics. I managed to solve it in haskell, but I want recode it, but I realized it's hard to transform in prolog due to too many built in function usage (and I used many of them in declarative form). So I want to rebuild it from scratch and I tried to search for similar problems solved in prolog, but I did not succeed. Can somebody help me with linking a solution of a similar problem in prolog or expand my cut predicate. Huge thanks in advance.

The problem: "The task can be summarized in the following way: there is a line of trees, with one meter of space between each of them. Each tree has a known height, in meters, and you can cut it aiming it toward its right or left. When an "m" meter tree falls, like in a domino game it forces the falling of its m−1 close trees, and this in turn can force other tree to fall. You can decide which tree to cut, and for each of them you can choose in which direction it will fall. Provide a list as short as possible of the trees to be felled, with a positive number representing a decision to the right and a negative number representing the code for a decision to the left.

enter image description here

My input:

tree(1,1).
tree(2,1).
tree(3,1).
tree(4,2).
tree(5,5).
tree(6,1).

My current code:

treecut(F, DL):-
    see(F),
    readfromfile([_|L]),
    seen,
    modifytolist(L, AL),
    cut(AL, DL). %how to do it?

readfromfile([Line|L]):-
    read(Line),
    Line \= end_of_file,
    readfromfile(L),
    !.
readfromfile([]).

modifytolist([], []):-!.
modifytolist([H|T], [H2|T2]):-
    pattern(H, H2),
    modifytolist(T,T2).

pattern(tree(P,H), (P,H)).

splitree((P,H), P, H):-!.

Output what I want

treecut('input1.pl',L).
L = [(5, -1),  (6, 1)].
prolog tree
1 Answers

This puzzle seems a lot of fun. Here is my first attempt:

makeZerosLeft([], [], _, 0) .
makeZerosLeft([I|In], [O|Out], N, Cnt):-
    makeZerosLeft(In, Out, N, Cnt1),
    Cnt is Cnt1+1,
    ( Cnt1<N ->   O=0 ;   O=I).

makeZerosRight(IO, IO, 0):- !.
makeZerosRight([], [], _):- !.
makeZerosRight([_|I], [0|O], N):-
    NN is N-1,
    makeZerosRight(I, O, NN).

checkZeros([]).
checkZeros([0|T]):-
    checkZeros(T).

fallingtrees(L1, L2, -1, N, O, L2):-
    makeZerosLeft(L1, O, N, _).
fallingtrees(L1, L2, 1, N, L1, O):-
    makeZerosRight(L2, O, N).

cutthem(L,[],0):-
    checkZeros(L).
cutthem(List, [(Pos,Dir)|CutList], s(S)):-
    append(L1,[Tree|L2],List), % choose Tree T
    Tree > 0, % not chopped
    length([_|L1], Pos), % pos of T 
    fallingtrees(L1, L2, Dir, Tree, O1, O2),
    append(O1,[0|O2], NewList),
    cutthem(NewList, CutList, S).
  
cutthemN(L, C, N):-
    cutthem(L, C, N).
cutthemN(L, C, N):-
    cutthemN(L, C, s(N)).

treecut(L,C):-
    cutthemN(L, C, s(0)).

Results:

?- treecut([1,1,1,2,5,1],L).
L = [(5, -1),  (6, -1)] ;
L = [(5, -1),  (6, 1)] ;
L = [(6, 1),  (5, -1)] ;
L = [(1, -1),  (2, 1),  (4, 1)] ;
...

?- treecut([2,3,2,1,4,2,1],L).
L = [(5,-1), (6,1)]  ;
L = [(5, -1),  (7, -1)] ;
L = [(6, 1),  (5, -1)] ;
L = [(7, -1),  (5, -1)] ;
L = [(1, -1),  (2, 1),  (6, 1)] ;
...

?- treecut([3,1,2,1,1,3,4,1,1,1,2,1,4,1,2,1,7,1,2,3],L).
L = [(1, 1),  (5, -1),  (6, 1),  (17, -1),  (20, -1)] ;
L = [(1, 1),  (5, -1),  (17, -1),  (6, 1),  (20, -1)] ;
L = [(1, 1),  (5, -1),  (17, -1),  (20, -1),  (6, 1)] ;
L = [(1, 1),  (5, 1),  (7, 1),  (17, -1),  (20, -1)] ;
L = [(1, 1),  (5, 1),  (17, -1),  (7, 1),  (20, -1)] ;
L = [(1, 1),  (5, 1),  (17, -1),  (20, -1),  (7, 1)] ;
...

My approach works directly on inputlists.
The heart of is the predicate cutthem/3 which gets a List of tree-heights and and a search depth and will "output" the list of steps. At first it checks if all trees were chopped (List contains 0's only). If so the job is done.
Otherwise it will choose a tree and the two lists of trees left and right from it (L1 and L2). The tree has the height Tree and position Pos. Then it will choose a direction Dir. For a left fall it will replace the last Tree elements from L1 with zeros (O1), for a right fall it will replace the first Tree elements from L2 with zeros (O2). Afterwards it will create the new list from O1 and O2 with a zero in the middle and call itself again. A counter S is running to restrict the search-depth. The search-depth is determined incrementally trough the predicate cutthemN/3 so the algorithm is implemented as a Breadth-first search.

user_80806480
Related