Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14219

Re: Autumn Challenge 2024: Numbrix Puzzle

Show all headers | View raw

Woa! I am always struggling to beat SWI-Prolog,
since I am always 2-3 times slower. But this
time not, possibly to do that the problem

is highly non-deterministic, so SWI-Prologs
clever tail recursion cannot kick in. Plus
my neck optimization possibly shows in predicates

such as next/2, since it also applies if there is
no cut (!)/0 and for predicates such as arithmetic
comparison and arithmetic evaluation as well,

and next optimization is ultra fast, since it
uses the native stack for these cases as well.
Here a bitwise based search:

/* SWI-Prolog 9.3.11 */
?- between(4,6,N), K is N^2-1,
     time(aggregate_all(count, (between(0,K,P),
     Q is 1<<P, path3(P, Q, N)), C)), write(C), nl, fail; true.
% 471,690 inferences, 0.031 CPU in 0.042 seconds
(74% CPU, 15094080 Lips)
552
% 53,076,891 inferences, 4.422 CPU in 4.428 seconds
(100% CPU, 12003255 Lips)
8648
% 15,537,147,614 inferences, 1421.922 CPU in 1438.575 seconds
(99% CPU, 10926864 Lips)
458696

/* Dogelog Player 1.2.4, JDK 22 */
?- between(4,6,N), K is N^2-1,
     time(aggregate_all(count, (between(0,K,P),
     Q is 1<<P, path3(P, Q, N)), C)), write(C), nl, fail; true.
% Zeit 76 ms, GC 0 ms, Lips 6258960, Uhr 09.10.2024 12:31
552
% Zeit 3507 ms, GC 1 ms, Lips 15151859, Uhr 09.10.2024 12:31
8648
% Zeit 1256978 ms, GC 76 ms, Lips 12363270, Uhr 09.10.2024 12:52
458696

But the difference of being faster is only small...

Mild Shock schrieb:
> Hi,
> 
> A path inside a rectangular grid can be
> encoded by numbering the cells so that
> successive integers are in adjacent cells.
> 
> Example:
> 
>    3---2---1  20--21
>    |           |   |
>    4  17--18--19  22
>    |   |           |
>    5  16--15--14  23
>    |           |   |
>    6   9--10  13  24
>    |   |   |   |   |
>    7---8  11--12  25
> 
> Turn it into a so called Numbrix puzzle,
> created by Marilyn vos Savant, in that
> you reveal a few numbers, and
> 
> the solitaire player has find and fill
> the remaining numbers. Similar approach
> as in Sudoku, except the constaints are
> 
> different. Implement the following in Prolog:
> 
> a) A solver for Numbrix
> 
> b) A riddle generator for Numbrix
> 
> c) Some game play for Numbrix
> 
> Have Fun!

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Autumn Challenge 2024: Numbrix Puzzle Mild Shock <janburse@fastmail.fm> - 2024-10-02 00:14 +0200
  Re: Autumn Challenge 2024: Numbrix Puzzle Mild Shock <janburse@fastmail.fm> - 2024-10-09 13:03 +0200
    Re: Autumn Challenge 2024: Numbrix Puzzle Mild Shock <janburse@fastmail.fm> - 2024-10-09 15:07 +0200

csiph-web