Puzzle Utilities: Difference between revisions
(Created page with "The following predicates are used in the puzzle solutions. ==Higher-order Predicates== ====unique_solution( +Goal )==== holds when <var>Goal</var> has one ground solution. ...") |
(Remove broken syntax highlighting) |
||
Line 9: | Line 9: | ||
they must all be identical (<code>==</code>). | they must all be identical (<code>==</code>). | ||
< | <pre class="prolog">unique_solution( Goal ) :- | ||
findall( Goal, Goal, [Solution|Solutions] ), | findall( Goal, Goal, [Solution|Solutions] ), | ||
same_solution( Solutions, Solution ), | same_solution( Solutions, Solution ), | ||
Line 17: | Line 17: | ||
same_solution( [Solution0|Solutions], Solution ) :- | same_solution( [Solution0|Solutions], Solution ) :- | ||
Solution0 == Solution, | Solution0 == Solution, | ||
same_solution( Solutions, Solution ).</ | same_solution( Solutions, Solution ).</pre> | ||
====forall( +Enumerator, +Test )==== | ====forall( +Enumerator, +Test )==== | ||
Line 24: | Line 24: | ||
holds everywhere that <var>Enumerator</var> does. NB: forall/2 does not instantiate arguments further. | holds everywhere that <var>Enumerator</var> does. NB: forall/2 does not instantiate arguments further. | ||
< | <pre class="prolog">forall( Enumerator, Test ) :- | ||
\+ (call(Enumerator), \+ call(Test)).</ | \+ (call(Enumerator), \+ call(Test)).</pre> | ||
====count_solutions( +Goal, ?Count )==== | ====count_solutions( +Goal, ?Count )==== | ||
Line 33: | Line 33: | ||
<code>count_solutions/2</code> enumerates the possible solutions to <var>Goal</var> but does not instantiate <var>Goal</var>'s arguments further. | <code>count_solutions/2</code> enumerates the possible solutions to <var>Goal</var> but does not instantiate <var>Goal</var>'s arguments further. | ||
< | <pre class="prolog"> | ||
count_solutions( Goal, Count ) :- | count_solutions( Goal, Count ) :- | ||
findall( x, Goal, Xs ), | findall( x, Goal, Xs ), | ||
length( Xs, Count ). | length( Xs, Count ). | ||
</ | </pre> | ||
==Lists== | ==Lists== | ||
Line 44: | Line 44: | ||
holds when <var>Element</var> is a member of <var>List</var>. | holds when <var>Element</var> is a member of <var>List</var>. | ||
< | <pre class="prolog">member( H, [H|_] ). | ||
member( H, [_|T] ) :- | member( H, [_|T] ) :- | ||
member( H, T ).</ | member( H, T ).</pre> | ||
====select( ?Element, ?List0, ?List1 )==== | ====select( ?Element, ?List0, ?List1 )==== | ||
Line 52: | Line 52: | ||
is true if <var>List1</var> is equal to <var>List0</var> with <var>Element</var> removed. | is true if <var>List1</var> is equal to <var>List0</var> with <var>Element</var> removed. | ||
< | <pre class="prolog">select( H, [H|T], T ). | ||
select( Element, [H|T0], [H|T1] ) :- | select( Element, [H|T0], [H|T1] ) :- | ||
select( Element, T0, T1 ).</ | select( Element, T0, T1 ).</pre> | ||
====memberchk( +Element, +List )==== | ====memberchk( +Element, +List )==== | ||
Line 60: | Line 60: | ||
succeeds (once) if <var>Element</var> is a member of <var>List</var>. | succeeds (once) if <var>Element</var> is a member of <var>List</var>. | ||
< | <pre class="prolog">memberchk( Element, List ) :- | ||
member( Element, List ), | member( Element, List ), | ||
!.</ | !.</pre> | ||
==Arithmetic== | ==Arithmetic== | ||
Line 72: | Line 72: | ||
* <var>Index</var> is a logical variable: a series of alternative solutions may be generated as the monotonic sequence of values between <var>Lower</var> and <var>Upper</var> (non-deterministic generator). | * <var>Index</var> is a logical variable: a series of alternative solutions may be generated as the monotonic sequence of values between <var>Lower</var> and <var>Upper</var> (non-deterministic generator). | ||
< | <pre class="prolog">between( Lower, Upper, Index ) :- | ||
integer( Lower ), | integer( Lower ), | ||
integer( Upper ), | integer( Upper ), | ||
Line 90: | Line 90: | ||
Next =< Upper, | Next =< Upper, | ||
generate_between( Next, Upper, Index ) | generate_between( Next, Upper, Index ) | ||
).</ | ).</pre> | ||
====sum( +List, ?Sum )==== | ====sum( +List, ?Sum )==== | ||
Line 96: | Line 96: | ||
holds when the <var>List</var> of numbers sum to <var>Sum</var>. | holds when the <var>List</var> of numbers sum to <var>Sum</var>. | ||
< | <pre class="prolog">sum( [H|T], Sum ) :- | ||
sum1( T, H, Sum ). | sum1( T, H, Sum ). | ||
Line 102: | Line 102: | ||
sum1( [H|T], Sum0, Sum ):- | sum1( [H|T], Sum0, Sum ):- | ||
Sum1 is Sum0 + H, | Sum1 is Sum0 + H, | ||
sum1( T, Sum1, Sum ).</ | sum1( T, Sum1, Sum ).</pre> | ||
==Character Input/Output== | ==Character Input/Output== | ||
Line 110: | Line 110: | ||
if <var>Chars</var> is a (possibly empty) list of character codes and the corresponding characters are written to the current output stream. | if <var>Chars</var> is a (possibly empty) list of character codes and the corresponding characters are written to the current output stream. | ||
< | <pre class="prolog">put_chars( [] ). | ||
put_chars( [Char|Chars] ) :- | put_chars( [Char|Chars] ) :- | ||
put( Char ), | put( Char ), | ||
put_chars( Chars ).</ | put_chars( Chars ).</pre> | ||
====get_chars( ?Chars )==== | ====get_chars( ?Chars )==== | ||
Line 119: | Line 119: | ||
if <var>Chars</var> is a (possibly empty) list of character codes read from the current input stream. | if <var>Chars</var> is a (possibly empty) list of character codes read from the current input stream. | ||
< | <pre class="prolog">get_chars( Input ) :- | ||
get0( Char ), | get0( Char ), | ||
( Char > -1 -> | ( Char > -1 -> | ||
Line 126: | Line 126: | ||
; otherwise -> | ; otherwise -> | ||
Input = [] | Input = [] | ||
).</ | ).</pre> | ||
The code is available as plain text [http://www.binding-time.co.uk/download/misc.txt here]. | The code is available as plain text [http://www.binding-time.co.uk/download/misc.txt here]. |
Revision as of 19:13, 5 January 2017
The following predicates are used in the puzzle solutions.
Higher-order Predicates
unique_solution( +Goal )
holds when Goal has one ground solution. Operationally, Goal
may produce several solutions, ("don't care" non-deterministically), but
they must all be identical (==
).
unique_solution( Goal ) :- findall( Goal, Goal, [Solution|Solutions] ), same_solution( Solutions, Solution ), Solution = Goal. same_solution( [], _Solution ). same_solution( [Solution0|Solutions], Solution ) :- Solution0 == Solution, same_solution( Solutions, Solution ).
forall( +Enumerator, +Test )
is true if Enumerator and Test are goals and Test holds everywhere that Enumerator does. NB: forall/2 does not instantiate arguments further.
forall( Enumerator, Test ) :- \+ (call(Enumerator), \+ call(Test)).
count_solutions( +Goal, ?Count )
is true if Count is the number of solutions for Goal. The solutions might not be distinct.
count_solutions/2
enumerates the possible solutions to Goal but does not instantiate Goal's arguments further.
count_solutions( Goal, Count ) :- findall( x, Goal, Xs ), length( Xs, Count ).
Lists
member( ?Element, ?List )
holds when Element is a member of List.
member( H, [H|_] ). member( H, [_|T] ) :- member( H, T ).
select( ?Element, ?List0, ?List1 )
is true if List1 is equal to List0 with Element removed.
select( H, [H|T], T ). select( Element, [H|T0], [H|T1] ) :- select( Element, T0, T1 ).
memberchk( +Element, +List )
succeeds (once) if Element is a member of List.
memberchk( Element, List ) :- member( Element, List ), !.
Arithmetic
between( +Lower, +Upper, ?Index )
is true if Lower =< Index =< Upper. Two valid cases are possible:
- Index is already instantiated to an integer, so the checks on order are applied (test).
- Index is a logical variable: a series of alternative solutions may be generated as the monotonic sequence of values between Lower and Upper (non-deterministic generator).
between( Lower, Upper, Index ) :- integer( Lower ), integer( Upper ), Lower =< Upper, ( integer( Index ) -> % Case 1: "test" Index >= Lower, Index =< Upper ; var( Index ) -> % Case 2: "generate". generate_between( Lower, Upper, Index ) ). generate_between( Lower, Upper, Index ) :- ( Lower =:= Upper -> Index = Lower ; Index = Lower ; Next is Lower + 1, Next =< Upper, generate_between( Next, Upper, Index ) ).
sum( +List, ?Sum )
holds when the List of numbers sum to Sum.
sum( [H|T], Sum ) :- sum1( T, H, Sum ). sum1( [], Sum, Sum ). sum1( [H|T], Sum0, Sum ):- Sum1 is Sum0 + H, sum1( T, Sum1, Sum ).
Character Input/Output
put_chars( +Chars )
if Chars is a (possibly empty) list of character codes and the corresponding characters are written to the current output stream.
put_chars( [] ). put_chars( [Char|Chars] ) :- put( Char ), put_chars( Chars ).
get_chars( ?Chars )
if Chars is a (possibly empty) list of character codes read from the current input stream.
get_chars( Input ) :- get0( Char ), ( Char > -1 -> Input = [Char|Chars], get_chars( Chars ) ; otherwise -> Input = [] ).
The code is available as plain text here.