Next predicate confusion

Question

I am in the process of studying the prologue, I am now writing the following predicate for a game that is really simple.

you have a list of [1,0,1,0,0,1]. The legal move moves 1 to the zero position, 1 can only move to the first position containing 0, but if necessary, jump over other values.

First, I wrote a predicate to change the value from 0 to 1:

flip_first_zero([0|Tail], [1|Tail]). 

simple enough, now I'm trying to find legal steps, I will try to explain my thought process:

 next([],[],[]). next([Head|Tail], Rest, Out):- flip_first_zero([Head|Tail],List1), append(Rest,List1,Out). next([Head|Tail], [Head|Rest], List):- next(Tail,Rest, List). 

example [1,0,0,1,1,1,0] output should be [0,1,0,1,1,1,0] ; [1,0,0,0,1,1,1]; [1,0,0,1,0,1,1] ; [1,0,0,1,1,0,1]. [0,1,0,1,1,1,0] ; [1,0,0,0,1,1,1]; [1,0,0,1,0,1,1] ; [1,0,0,1,1,0,1].

[ 1 , 0,0,1,1,1,0] → [0, 1 , 0,1,1,1,0]

[1,0,0, 1 , 1,1,0] → [1,0,0,0,1,1,1, 1 ]

[1,0,0,1,1,1,0] → [1,0,0,1,0,1,1]

[1,0,0,1,1,1,0,0] → [1,0,0,1,1,0,0 1 ]

So, as I understand it, I cyclically delete my head every time, storing it in Rest, so I can add it back after.

Am I approaching this wrong?

Answer 1

The problem consists of two parts: (1) location 1, (2) the location of the first 0 after finding 1, so that 1 can be placed in a new position. The Prolog solution will reflect this. Your initial attempt is trying to process everything in one predicate, which, in my opinion, makes the task harder.

The base case is simple. It represents the smallest allowable move.

 move([1,0], [0,1]). 

Then recurrence cases. They provide at least 3 positions in the list, since a trivial case of two positions is already handled by the base case, and it sets a mutual exception in the rules to avoid redundant decisions.

 % If we're at a 0 (space), keep going move([0,X1,X2|T], [0|R]) :- move([X1,X2|T], R). % If we see a 1, we can move it, or we can leave it alone and move on move([1,X1,X2|T], [0|R]) :- place([X1,X2|T], R). move([1,X1,X2|T], [1|R]) :- move([X1,X2|T], R). % Place the 1 at the first located 0 (space) place([0|T], [1|T]). place([1|T], [1|R]) :- place(T, R). 

So, to determine the valid following positions from the starting position:

 | ?- move([1,0,0,1,1,1,0],R). R = [0,1,0,1,1,1,0] ? a R = [1,0,0,0,1,1,1] R = [1,0,0,1,0,1,1] R = [1,0,0,1,1,0,1] (1 ms) no | ?- 

You can also determine which starting positions will lead to a certain next position:

 | ?- move(S, [1,0,0,1,0,1,1]). S = [1,0,0,1,1,0,1] ? a S = [1,0,0,1,1,1,0] S = [1,0,1,0,0,1,1] no 

<h / "> This can also be done using DCG:

 move([0, 1]) --> [1, 0]. move([0|R]) --> see(0), move(R). move([0|R]) --> see(1), place(R). move([1|R]) --> see(1), move(R). see(N), [X1, X2] --> [N, X1, X2]. place([1|T]) --> [0], seq(T). place([1|R]) --> [1], place(R). seq([]) --> []. seq([X|Xs]) --> [X], seq(Xs). | ?- phrase(move(R), [1,0,0,1,1,1,0]). R = [0,1,0,1,1,1,0] ? a R = [1,0,0,0,1,1,1] R = [1,0,0,1,0,1,1] R = [1,0,0,1,1,0,1] no | ?- phrase(move([1,0,0,1,0,1,1]), S). S = [1,0,0,1,1,0,1] ? a S = [1,0,0,1,1,1,0] S = [1,0,1,0,0,1,1] no 

Answer 2

One logical way to get closer to this is to find what comes before 1, what happens after 1 and to 0, and relax. Then you need to change 1 and 0 so that you have up to 1, 0, after 1 to 0, 1 after 0.

Start small. First, to just split the list when you have 1, so that you have Before and After , you can use append/3 , like this, using the list from your example:

 ?- append(Before, [1|After], [1,0,0,1,1,1,0]). Before = [], After = [0, 0, 1, 1, 1, 0] ; Before = [1, 0, 0], After = [1, 1, 0] ; Before = [1, 0, 0, 1], After = [1, 0] ; Before = [1, 0, 0, 1, 1], After = [0] ; false. 

You already have 4 solutions that you expect. Now you need to look inside After , to see where to put 1 - well, you need to put it right after the first 0. So, let split After at 0, but only once:

 ?- append(Before, [1|After], [1,0,0,1,1,1,0]), once( append(Before0, [0|After0], After) ). Before = Before0, Before0 = [], After = [0, 0, 1, 1, 1, 0], After0 = [0, 1, 1, 1, 0] ; Before = [1, 0, 0], After = [1, 1, 0], Before0 = [1, 1], After0 = [] ; Before = [1, 0, 0, 1], After = [1, 0], Before0 = [1], After0 = [] ; Before = [1, 0, 0, 1, 1], After = [0], Before0 = After0, After0 = [] ; false. 

Now you have 3 parts: one before 1 is called Before , one between 1 and the first 0, called Before0 , and the last fragment after the first 0, called After0 . You just need to collect them back: Before , 0, Before0 , 1, After0 . You can use the 2 argument append/2 , which takes a list of lists in the first argument:

 ?- append(Before, [1|After], [1,0,0,1,1,1,0]), once( append(Before0, [0|After0], After) ), append([Before, [0|Before0], [1|After0]], Result). Result = [0, 1, 0, 1, 1, 1, 0] ; Result = [1, 0, 0, 0, 1, 1, 1] ; Result = [1, 0, 0, 1, 0, 1, 1] ; Result = [1, 0, 0, 1, 1, 0, 1] ; false. 

(I only saved Result bindings to save space.)

I think you are done at this moment.

Answer 3

Thanks for all the answers, here is how I did it:

 flip_first_zero([0|L],[1|L]):-!. flip_first_zero([X|L],[X|L1]):- flip_first_zero(L,L1). next([1|L],[0|L1]):- flip_first_zero(L,L1). next([X|L],[X|L1]):- next(L,L1).