Instructions

You run the prolog program below by entering queries of the form: cool([1,1,1,0,0,0], X) and then by using ; to step through the various solutions for X. (The solutions will be generated in the cool-lex order.) This program was written by Aaron Williams.

The Prolog Program

all0([]).
all0([H|T]) :-
  H = 0,
  all0(T).

has01([A,B|T]) :-
  ( A=0, B=1 ->
    true
  ;
    has01([B|T])
  ).
  
decreasing([]).
decreasing([H|T]) :-
  ( H=1 ->
    decreasing(T)
  ;
    all0(T)
  ).

continue([H|T]) :-
  ( H=1 ->
    true
  ;
    has01(T)
  ).

next([H|T], X) :-
  continue([H|T]),
  ( decreasing(T) ->
    append(T,[H],X)
  ;
    append(D,[0,1|C],T),
    decreasing(D),
    append(D,[0,1,H|C], X)
  ).
  
cool(A,C) :-
  next(A,C).
cool(A,C) :-
  next(A,B),
  cool(B,C).