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

Groups > comp.lang.prolog > #13448 > unrolled thread

Re: The road to Artificial Intelligence

Back to article view | Back to comp.lang.prolog

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 03:28 -0800
    Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 04:15 -0800
      Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 04:47 -0800
        Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 08:10 -0800
          Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 08:24 -0800
            Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-20 08:47 -0800
              Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-20 08:50 -0800
                Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-20 11:12 -0800
    Was it worth the wait? [gemini by Google] Mild Shock <janburse@fastmail.fm> - 2024-02-22 16:49 +0100
      Pulverizer against Delhi Belly? (Was: Was it worth the wait? [gemini by Google]) Mild Shock <janburse@fastmail.fm> - 2024-02-22 19:11 +0100
    Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-02-27 17:03 +0100
      Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-03-16 14:06 +0100
        Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-03-16 14:13 +0100
          Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-03-24 01:32 +0100
            Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-03-24 18:26 +0100
              Re: The road to Artificial Intelligence Mikko <mikko.levanto@iki.fi> - 2024-03-25 09:59 +0200

#13448 — Re: The road to Artificial Intelligence

Don't buy your Pearls in Honk Kong. They are all fake.

So what do you prefer, this Haskell monster:
https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf

Or this elegant Prolog code, less than half a page:

% solve(+Integer, -Term, -Integer, +List, -List)
solve(1, N, N, P, Q) :- !, select(N, P, Q).
solve(K, G, N, P, Q) :-
   J is K-1,
   between(1, J, I),
   L is K-I,
   solve(I, E, A, P, H),
   solve(L, F, B, H, Q),
   combine(E, A, F, B, G, N).

combine(E, A, F, B, E+F, N) :- A =< B, N is A+B.
combine(E, A, F, B, E-F, N) :- A > B, N is A-B.
combine(E, A, F, B, E*F, N) :- A =< B, N is A*B.
combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B.

Speedy enough I guess:

?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)).
% 4,857,250 inferences, 0.484 CPU in 0.468 seconds (104% CPU, 10027871 Lips)
true.

[toc] | [next] | [standalone]

#13449

Lets go a little bit beyond what the paper calls
5 Fusing generation and evaluation, by introducing
a little constraint propagation. Now I get:

?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)).
% % 3,604,685 inferences, 0.344 CPU in 0.343 seconds (100% CPU, 10486356 Lips)
% true.

Code got a little bit longer, but still quite readable:

% solve(+Integer, -Term, -Integer, +List, -List)
solve(1, N, N, P, Q) :- !, select(N, P, Q).
solve(K, G, N, P, Q) :- var(N), !,
   J is K-1,
   between(1, J, I),
   L is K-I,
   solve(I, E, A, P, H),
   solve(L, F, B, H, Q),
   combine(E, A, F, B, G, N).
solve(K, G, N, P, Q) :-
   J is K-1,
   between(1, J, I),
   L is K-I,
   solve(I, E, A, P, H),
   forward(E, A, F, B, G, N),
   solve(L, F, B, H, Q).

combine(E, A, F, B, E+F, N) :- A =< B, N is A+B.
combine(E, A, F, B, E-F, N) :- A > B, N is A-B.
combine(E, A, F, B, E*F, N) :- A =< B, N is A*B.
combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B.

forward(E, A, F, B, E+F, N) :- N > A, B is N-A, A =< B.
forward(E, A, F, B, E-F, N) :- A > N, B is A-N.
forward(E, A, F, B, E*F, N) :- N mod A =:= 0, B is N div A, A =< B.
forward(E, A, F, B, E/F, N) :- A mod N =:= 0, B is A div N.

Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 12:28:47 UTC+1:
> Don't buy your Pearls in Honk Kong. They are all fake. 
> 
> So what do you prefer, this Haskell monster: 
> https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf 
> 
> Or this elegant Prolog code, less than half a page: 
> 
> % solve(+Integer, -Term, -Integer, +List, -List) 
> solve(1, N, N, P, Q) :- !, select(N, P, Q). 
> solve(K, G, N, P, Q) :- 
> J is K-1, 
> between(1, J, I), 
> L is K-I, 
> solve(I, E, A, P, H), 
> solve(L, F, B, H, Q), 
> combine(E, A, F, B, G, N). 
> 
> combine(E, A, F, B, E+F, N) :- A =< B, N is A+B. 
> combine(E, A, F, B, E-F, N) :- A > B, N is A-B. 
> combine(E, A, F, B, E*F, N) :- A =< B, N is A*B. 
> combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B. 
> 
> Speedy enough I guess: 
> 
> ?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)). 
> % 4,857,250 inferences, 0.484 CPU in 0.468 seconds (104% CPU, 10027871 Lips) 
> true.

[toc] | [prev] | [next] | [standalone]

#13450

https://stackoverflow.com/a/74908845/17524790

This stack overflow solution does also some early pruning. But it is based
on powerset permutation and not on permutation. So you will find solutions where not
all numbers are used, only some. You see that it might omit numbers here:

?- time(solve_countdown([1,7,7,3], 24, Ts)).
% 12,117 inferences, 0.002 CPU in 0.002 seconds (99% CPU, 5370013 Lips)
Ts = [3*(1+7), (7-1)*(7-3)].

Or maybe this is part of the requirement? Ok, my bad, wasn’t paying attention.

Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 13:15:41 UTC+1:
> Lets go a little bit beyond what the paper calls 
> 5 Fusing generation and evaluation, by introducing 
> a little constraint propagation. Now I get:
> ?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)).
> % % 3,604,685 inferences, 0.344 CPU in 0.343 seconds (100% CPU, 10486356 Lips) 
> % true. 
> 
> Code got a little bit longer, but still quite readable:
> % solve(+Integer, -Term, -Integer, +List, -List) 
> solve(1, N, N, P, Q) :- !, select(N, P, Q).
> solve(K, G, N, P, Q) :- var(N), !,
> J is K-1, 
> between(1, J, I), 
> L is K-I, 
> solve(I, E, A, P, H), 
> solve(L, F, B, H, Q), 
> combine(E, A, F, B, G, N). 
> solve(K, G, N, P, Q) :- 
> J is K-1, 
> between(1, J, I), 
> L is K-I, 
> solve(I, E, A, P, H),
> forward(E, A, F, B, G, N), 
> solve(L, F, B, H, Q).
> combine(E, A, F, B, E+F, N) :- A =< B, N is A+B. 
> combine(E, A, F, B, E-F, N) :- A > B, N is A-B. 
> combine(E, A, F, B, E*F, N) :- A =< B, N is A*B. 
> combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B.
> forward(E, A, F, B, E+F, N) :- N > A, B is N-A, A =< B. 
> forward(E, A, F, B, E-F, N) :- A > N, B is A-N. 
> forward(E, A, F, B, E*F, N) :- N mod A =:= 0, B is N div A, A =< B. 
> forward(E, A, F, B, E/F, N) :- A mod N =:= 0, B is A div N.
> Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 12:28:47 UTC+1: 
> > Don't buy your Pearls in Honk Kong. They are all fake. 
> > 
> > So what do you prefer, this Haskell monster: 
> > https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf 
> > 
> > Or this elegant Prolog code, less than half a page: 
> > 
> > % solve(+Integer, -Term, -Integer, +List, -List) 
> > solve(1, N, N, P, Q) :- !, select(N, P, Q). 
> > solve(K, G, N, P, Q) :- 
> > J is K-1, 
> > between(1, J, I), 
> > L is K-I, 
> > solve(I, E, A, P, H), 
> > solve(L, F, B, H, Q), 
> > combine(E, A, F, B, G, N). 
> > 
> > combine(E, A, F, B, E+F, N) :- A =< B, N is A+B. 
> > combine(E, A, F, B, E-F, N) :- A > B, N is A-B. 
> > combine(E, A, F, B, E*F, N) :- A =< B, N is A*B. 
> > combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B. 
> > 
> > Speedy enough I guess: 
> > 
> > ?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)). 
> > % 4,857,250 inferences, 0.484 CPU in 0.468 seconds (104% CPU, 10027871 Lips) 
> > true.

[toc] | [prev] | [next] | [standalone]

#13451

Not sure whether CLP(FD) will show the same timing figures. Since in the
above I did the small CLP(FD) inference manually, CLP(FD) might be still
slower because some overhead, unless some intervals or other approaches

come into play. One might also try freeze/2. Maybe somebody can write a
sequel to the Pearls paper from a Prolog perspective and include the
propagation technique, and show the world its muscles? Don’t have

time for that, also the matter is somehow related to focusing proof calculi.

Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 13:47:27 UTC+1:
> https://stackoverflow.com/a/74908845/17524790 
> 
> This stack overflow solution does also some early pruning. But it is based 
> on powerset permutation and not on permutation. So you will find solutions where not 
> all numbers are used, only some. You see that it might omit numbers here: 
> 
> ?- time(solve_countdown([1,7,7,3], 24, Ts)). 
> % 12,117 inferences, 0.002 CPU in 0.002 seconds (99% CPU, 5370013 Lips) 
> Ts = [3*(1+7), (7-1)*(7-3)]. 
> 
> Or maybe this is part of the requirement? Ok, my bad, wasn’t paying attention.
> Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 13:15:41 UTC+1: 
> > Lets go a little bit beyond what the paper calls 
> > 5 Fusing generation and evaluation, by introducing 
> > a little constraint propagation. Now I get: 
> > ?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)). 
> > % % 3,604,685 inferences, 0.344 CPU in 0.343 seconds (100% CPU, 10486356 Lips) 
> > % true. 
> > 
> > Code got a little bit longer, but still quite readable: 
> > % solve(+Integer, -Term, -Integer, +List, -List) 
> > solve(1, N, N, P, Q) :- !, select(N, P, Q). 
> > solve(K, G, N, P, Q) :- var(N), !, 
> > J is K-1, 
> > between(1, J, I), 
> > L is K-I, 
> > solve(I, E, A, P, H), 
> > solve(L, F, B, H, Q), 
> > combine(E, A, F, B, G, N). 
> > solve(K, G, N, P, Q) :- 
> > J is K-1, 
> > between(1, J, I), 
> > L is K-I, 
> > solve(I, E, A, P, H), 
> > forward(E, A, F, B, G, N), 
> > solve(L, F, B, H, Q). 
> > combine(E, A, F, B, E+F, N) :- A =< B, N is A+B. 
> > combine(E, A, F, B, E-F, N) :- A > B, N is A-B. 
> > combine(E, A, F, B, E*F, N) :- A =< B, N is A*B. 
> > combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B. 
> > forward(E, A, F, B, E+F, N) :- N > A, B is N-A, A =< B. 
> > forward(E, A, F, B, E-F, N) :- A > N, B is A-N. 
> > forward(E, A, F, B, E*F, N) :- N mod A =:= 0, B is N div A, A =< B. 
> > forward(E, A, F, B, E/F, N) :- A mod N =:= 0, B is A div N. 
> > Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 12:28:47 UTC+1: 
> > > Don't buy your Pearls in Honk Kong. They are all fake. 
> > > 
> > > So what do you prefer, this Haskell monster: 
> > > https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf 
> > > 
> > > Or this elegant Prolog code, less than half a page: 
> > > 
> > > % solve(+Integer, -Term, -Integer, +List, -List) 
> > > solve(1, N, N, P, Q) :- !, select(N, P, Q). 
> > > solve(K, G, N, P, Q) :- 
> > > J is K-1, 
> > > between(1, J, I), 
> > > L is K-I, 
> > > solve(I, E, A, P, H), 
> > > solve(L, F, B, H, Q), 
> > > combine(E, A, F, B, G, N). 
> > > 
> > > combine(E, A, F, B, E+F, N) :- A =< B, N is A+B. 
> > > combine(E, A, F, B, E-F, N) :- A > B, N is A-B. 
> > > combine(E, A, F, B, E*F, N) :- A =< B, N is A*B. 
> > > combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B. 
> > > 
> > > Speedy enough I guess: 
> > > 
> > > ?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)). 
> > > % 4,857,250 inferences, 0.484 CPU in 0.468 seconds (104% CPU, 10027871 Lips) 
> > > true.

[toc] | [prev] | [next] | [standalone]

#13452

A nice exercise is to eliminate the var/1 in the solution. By splitting the code into two
solve/5 predicates, you then get what is sometime shown in functional programming
language theory papers. Some calculi where some evaluator who knows what has different

focusing modes. Which often only corresponds to different Prolog mode declarations.

Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 17:10:22 UTC+1:
> Not sure whether CLP(FD) will show the same timing figures. Since in the 
> above I did the small CLP(FD) inference manually, CLP(FD) might be still 
> slower because some overhead, unless some intervals or other approaches 
> 
> come into play. One might also try freeze/2. Maybe somebody can write a 
> sequel to the Pearls paper from a Prolog perspective and include the 
> propagation technique, and show the world its muscles? Don’t have 
> 
> time for that, also the matter is somehow related to focusing proof calculi.
> Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 13:47:27 UTC+1: 
> > https://stackoverflow.com/a/74908845/17524790 
> > 
> > This stack overflow solution does also some early pruning. But it is based 
> > on powerset permutation and not on permutation. So you will find solutions where not 
> > all numbers are used, only some. You see that it might omit numbers here: 
> > 
> > ?- time(solve_countdown([1,7,7,3], 24, Ts)). 
> > % 12,117 inferences, 0.002 CPU in 0.002 seconds (99% CPU, 5370013 Lips) 
> > Ts = [3*(1+7), (7-1)*(7-3)]. 
> > 
> > Or maybe this is part of the requirement? Ok, my bad, wasn’t paying attention. 
> > Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 13:15:41 UTC+1: 
> > > Lets go a little bit beyond what the paper calls 
> > > 5 Fusing generation and evaluation, by introducing 
> > > a little constraint propagation. Now I get: 
> > > ?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)). 
> > > % % 3,604,685 inferences, 0.344 CPU in 0.343 seconds (100% CPU, 10486356 Lips) 
> > > % true. 
> > > 
> > > Code got a little bit longer, but still quite readable: 
> > > % solve(+Integer, -Term, -Integer, +List, -List) 
> > > solve(1, N, N, P, Q) :- !, select(N, P, Q). 
> > > solve(K, G, N, P, Q) :- var(N), !, 
> > > J is K-1, 
> > > between(1, J, I), 
> > > L is K-I, 
> > > solve(I, E, A, P, H), 
> > > solve(L, F, B, H, Q), 
> > > combine(E, A, F, B, G, N). 
> > > solve(K, G, N, P, Q) :- 
> > > J is K-1, 
> > > between(1, J, I), 
> > > L is K-I, 
> > > solve(I, E, A, P, H), 
> > > forward(E, A, F, B, G, N), 
> > > solve(L, F, B, H, Q). 
> > > combine(E, A, F, B, E+F, N) :- A =< B, N is A+B. 
> > > combine(E, A, F, B, E-F, N) :- A > B, N is A-B. 
> > > combine(E, A, F, B, E*F, N) :- A =< B, N is A*B. 
> > > combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B. 
> > > forward(E, A, F, B, E+F, N) :- N > A, B is N-A, A =< B. 
> > > forward(E, A, F, B, E-F, N) :- A > N, B is A-N. 
> > > forward(E, A, F, B, E*F, N) :- N mod A =:= 0, B is N div A, A =< B. 
> > > forward(E, A, F, B, E/F, N) :- A mod N =:= 0, B is A div N. 
> > > Mostowski Collapse schrieb am Samstag, 18. Februar 2023 um 12:28:47 UTC+1: 
> > > > Don't buy your Pearls in Honk Kong. They are all fake. 
> > > > 
> > > > So what do you prefer, this Haskell monster: 
> > > > https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf 
> > > > 
> > > > Or this elegant Prolog code, less than half a page: 
> > > > 
> > > > % solve(+Integer, -Term, -Integer, +List, -List) 
> > > > solve(1, N, N, P, Q) :- !, select(N, P, Q). 
> > > > solve(K, G, N, P, Q) :- 
> > > > J is K-1, 
> > > > between(1, J, I), 
> > > > L is K-I, 
> > > > solve(I, E, A, P, H), 
> > > > solve(L, F, B, H, Q), 
> > > > combine(E, A, F, B, G, N). 
> > > > 
> > > > combine(E, A, F, B, E+F, N) :- A =< B, N is A+B. 
> > > > combine(E, A, F, B, E-F, N) :- A > B, N is A-B. 
> > > > combine(E, A, F, B, E*F, N) :- A =< B, N is A*B. 
> > > > combine(E, A, F, B, E/F, N) :- A mod B =:= 0, N is A div B. 
> > > > 
> > > > Speedy enough I guess: 
> > > > 
> > > > ?- time((solve(6, E, 999, [1,3,5,10,25,50], _), fail; true)). 
> > > > % 4,857,250 inferences, 0.484 CPU in 0.468 seconds (104% CPU, 10027871 Lips) 
> > > > true.

[toc] | [prev] | [next] | [standalone]

#13462

Now waitinging for a CLP(X) solution of the count down 
problem, anybody up to it? Maybe with CLP(FD) or
with freeze/2? But I doubt Scryer Prolog can produce

a solution, its a little bit slow. On my machine:

/* Scryer Prolog 0.9.1-166 */
?- N #= 2^14, time((between(1,N,_), A #\= B, false; true)).
   % CPU time: 2.207s
   N = 16384.

/* Jekejeke Prolog 1.5.6 */
?- N #= 2^14, time((between(1,N,_), A #\= B, false; true)).
% Threads 391 ms, GC 5 ms, Up 396 ms (Current 02/20/23 17:39:44)
N = 16384.

/* SWI-Prolog 9.1.4 */
?- N #= 2^14, time((between(1,N,_), A #\= B, false; true)).
% 2,310,145 inferences, 0.109 CPU in 0.110 seconds (100% CPU, 21121326 Lips)
N = 16384.

LoL

[toc] | [prev] | [next] | [standalone]

#13463

But the number of Scryer Prolog tickets went down 
from 222 to 219. If one extrapolates that, I guess
in 100 years from now it will be finished.

Enough time to optimize my own CLP(FD) or
even introduce CLP(FD) to the Dogelog Player. 
Not yet sure, whether it will or will not have

attributed variables. Maybe an explicit approach
like in the count down problem is often the better
approach? Well not really, a CLP(X) based 

approach has more potential for early pruning.

Mostowski Collapse schrieb am Montag, 20. Februar 2023 um 17:47:47 UTC+1:
> Now waiting for a CLP(X) solution of the count down 
> problem, anybody up to it? Maybe with CLP(FD) or 
> with freeze/2? But I doubt Scryer Prolog can produce 
> 
> a solution, its a little bit slow. On my machine: 
> 
> /* Scryer Prolog 0.9.1-166 */ 
> ?- N #= 2^14, time((between(1,N,_), A #\= B, false; true)). 
> % CPU time: 2.207s 
> N = 16384. 
> 
> /* Jekejeke Prolog 1.5.6 */ 
> ?- N #= 2^14, time((between(1,N,_), A #\= B, false; true)). 
> % Threads 391 ms, GC 5 ms, Up 396 ms (Current 02/20/23 17:39:44) 
> N = 16384. 
> 
> /* SWI-Prolog 9.1.4 */ 
> ?- N #= 2^14, time((between(1,N,_), A #\= B, false; true)). 
> % 2,310,145 inferences, 0.109 CPU in 0.110 seconds (100% CPU, 21121326 Lips) 
> N = 16384. 
> 
> LoL

[toc] | [prev] | [next] | [standalone]

#13464

This is also a nice test case:

bomb(N) :- bomb(N), bomb(N).

/* Scryer Prolog 0.9.1-166 */
?- bomb(1000).
Killed

/* Trealla Prolog 2.9.4 */
?- bomb(1000).
Killed

/* Jekejeke Prolog 1.4.6 */
?- bomb(1000).
Error: Execution aborted since memory threshold exceeded.
	bomb/1
	bomb/1
	bomb/1
	bomb/1
	bomb/1
	bomb/1
	bomb/1
	bomb/1
	bomb/1
	bomb/1
	... 3259796 more user frames ...
?- sys_trap(bomb(1000), E, true).
E = error(system_error(memory_threshold), [pred(bomb/1), pred(bomb/1), pred(bomb/1), pred(bomb/1), pred(bomb/1), pred(bomb/1), pred(bomb/1), pred(bomb/1), pred(bomb/1), pred(bomb/1), pred_more(2766689)]).

/* SWI-Prolog 9.1.4 */
?- bomb(1000).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 1.0Gb, global: 80Kb, trail: 1Kb
ERROR:   Stack depth: 14,909,825, last-call: 0%, Choice points: 3
ERROR:   Probable infinite recursion (cycle):
ERROR:     [14,909,825] user:bomb(1000)
ERROR:     [14,909,824] user:bomb(1000)
?- catch(bomb(1000), E, true).
E = error(resource_error(stack), stack_overflow{choicepoints:4, cycle:[frame(14912327, user:bomb(1000), []), frame(14912326, user:bomb(1000), [])], depth:14912327, environments:14912326, globalused:4, localused:1048523, stack_limit:1048576, trailused:0}).

LoL

[toc] | [prev] | [next] | [standalone]

#13988 — Was it worth the wait? [gemini by Google]

Interesting, new Google gemini, had a vague notion
of this algorithm when I asked it. ChatGPT was totally
clueless. BTW nice video:

Dijkstra's Hidden Prime Finding Algorithm
https://www.youtube.com/watch?v=fwxjMKBMR7s

DIJKSTRA'S PRIME NUMBER ALGORITHM
https://www.heinrichhartmann.com/archive/Dijkstra%27s-Prime-Number-Algorithm.html

gemini couldn't produce correct Python code though.

[toc] | [prev] | [next] | [standalone]

#13989 — Pulverizer against Delhi Belly? (Was: Was it worth the wait? [gemini by Google])

Google gemini is nevertheless a complete idiot.
It just showed me:

X = (24 + 394479375 * 1) / 36641
X = 394479403 / 36641
X = 10769

LoL

Mild Shock schrieb:
> Interesting, new Google gemini, had a vague notion
> of this algorithm when I asked it. ChatGPT was totally
> clueless. BTW nice video:
> 
> Dijkstra's Hidden Prime Finding Algorithm
> https://www.youtube.com/watch?v=fwxjMKBMR7s
> 
> DIJKSTRA'S PRIME NUMBER ALGORITHM
> https://www.heinrichhartmann.com/archive/Dijkstra%27s-Prime-Number-Algorithm.html 
> 
> 
> gemini couldn't produce correct Python code though.

[toc] | [prev] | [next] | [standalone]

#13996

Terence Tao, "Machine Assisted Proof"
https://www.youtube.com/watch?v=AayZuuDDKP0

Mostowski Collapse schrieb:
> Don't buy your Pearls in Honk Kong. They are all fake.
> 
> So what do you prefer, this Haskell monster:
> https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf

[toc] | [prev] | [next] | [standalone]

#14019

I didn't make all my homework yet.
For example just fiddling around with CLP(FD), I get:

?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4,
           1..3, 1..3, 1..6]), all_distinct(Vs).
false.

Does Scryer Prolog CLP(Z) have some explanator for that?
What is exactly the conflict that it fails?

Mild Shock schrieb:
> 
> Terence Tao, "Machine Assisted Proof"
> https://www.youtube.com/watch?v=AayZuuDDKP0
> 
> Mostowski Collapse schrieb:
>> Don't buy your Pearls in Honk Kong. They are all fake.
>>
>> So what do you prefer, this Haskell monster:
>> https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf

[toc] | [prev] | [next] | [standalone]

#14020

Or a more striking example, Peter Norvig's impossible
Sudoku, which he claims took him 1439 seconds
to show that it is unsolvable:

/* Peter Norvig */
problem(9, [[_,_,_,_,_,5,_,8,_],
             [_,_,_,6,_,1,_,4,3],
             [_,_,_,_,_,_,_,_,_],
             [_,1,_,5,_,_,_,_,_],
             [_,_,_,1,_,6,_,_,_],
             [3,_,_,_,_,_,_,_,5],
             [5,3,_,_,_,_,_,6,1],
             [_,_,_,_,_,_,_,_,4],
             [_,_,_,_,_,_,_,_,_]]).

https://norvig.com/sudoku.html

whereby SWI-Prolog with all_distinct/1 does
it in a blink, even without labeling:

?- problem(9, M), time(sudoku(M)).
% 316,054 inferences, 0.016 CPU in 0.020 seconds
  (80% CPU, 20227456 Lips)
false.

Pretty cool!

Mild Shock schrieb:
> I didn't make all my homework yet.
> For example just fiddling around with CLP(FD), I get:
> 
> ?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4,
>            1..3, 1..3, 1..6]), all_distinct(Vs).
> false.
> 
> Does Scryer Prolog CLP(Z) have some explanator for that?
> What is exactly the conflict that it fails?
> 
> Mild Shock schrieb:
>>
>> Terence Tao, "Machine Assisted Proof"
>> https://www.youtube.com/watch?v=AayZuuDDKP0
>>
>> Mostowski Collapse schrieb:
>>> Don't buy your Pearls in Honk Kong. They are all fake.
>>>
>>> So what do you prefer, this Haskell monster:
>>> https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf
> 

[toc] | [prev] | [next] | [standalone]

#14022

Now I have the feeling there are no difficult 9x9
Sudokus for the computer. At least not for computers
running SWI-Prolog and using CLP(FD) with the global
constraint all_distinct/1.

I was fishing among the 17-clue Sudokus, and the
hardest I could find so far was this one:

/* Gordon Royle #3668 */
problem(11,[[_,_,_,_,_,_,_,_,_],
             [_,_,_,_,_,_,_,1,2],
             [_,_,3,_,_,4,_,_,_],
             [_,_,_,_,_,_,_,_,3],
             [_,1,_,2,5,_,_,_,_],
             [6,_,_,_,_,_,7,_,_],
             [_,_,_,_,2,_,_,_,_],
             [_,_,7,_,_,_,4,_,_],
             [5,_,_,1,6,_,_,8,_]]).

But SWI-Prolog still does it in around 3 seconds.
SWI-Prolog does other 17-clue Sudokus in less than 100ms.

Are there any 17-clue Sudokus that take more time?

Mild Shock schrieb:
> 
> Or a more striking example, Peter Norvig's impossible
> Sudoku, which he claims took him 1439 seconds
> to show that it is unsolvable:
> 
> /* Peter Norvig */
> problem(9, [[_,_,_,_,_,5,_,8,_],
>              [_,_,_,6,_,1,_,4,3],
>              [_,_,_,_,_,_,_,_,_],
>              [_,1,_,5,_,_,_,_,_],
>              [_,_,_,1,_,6,_,_,_],
>              [3,_,_,_,_,_,_,_,5],
>              [5,3,_,_,_,_,_,6,1],
>              [_,_,_,_,_,_,_,_,4],
>              [_,_,_,_,_,_,_,_,_]]).
> 
> https://norvig.com/sudoku.html
> 
> whereby SWI-Prolog with all_distinct/1 does
> it in a blink, even without labeling:
> 
> ?- problem(9, M), time(sudoku(M)).
> % 316,054 inferences, 0.016 CPU in 0.020 seconds
>   (80% CPU, 20227456 Lips)
> false.
> 
> Pretty cool!
> 
> Mild Shock schrieb:
>> I didn't make all my homework yet.
>> For example just fiddling around with CLP(FD), I get:
>>
>> ?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4,
>>            1..3, 1..3, 1..6]), all_distinct(Vs).
>> false.
>>
>> Does Scryer Prolog CLP(Z) have some explanator for that?
>> What is exactly the conflict that it fails?
>>
>> Mild Shock schrieb:
>>>
>>> Terence Tao, "Machine Assisted Proof"
>>> https://www.youtube.com/watch?v=AayZuuDDKP0
>>>
>>> Mostowski Collapse schrieb:
>>>> Don't buy your Pearls in Honk Kong. They are all fake.
>>>>
>>>> So what do you prefer, this Haskell monster:
>>>> https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf
>>
> 

[toc] | [prev] | [next] | [standalone]

#14023

Is 3 seconds even enough to generate
unique Sudokus? How many trials would be
needed? The uniqueness problem

seems to have no useful reduction,
already the question whether a partial
latin square has a unique solution

is NP complete?

Finding Another Solution
T. Yato & T. Seta - 2002
https://academic.timwylie.com/17CSCI4341/sudoku.pdf

Mild Shock schrieb:
> Now I have the feeling there are no difficult 9x9
> Sudokus for the computer. At least not for computers
> running SWI-Prolog and using CLP(FD) with the global
> constraint all_distinct/1.
> 
> I was fishing among the 17-clue Sudokus, and the
> hardest I could find so far was this one:
> 
> /* Gordon Royle #3668 */
> problem(11,[[_,_,_,_,_,_,_,_,_],
>              [_,_,_,_,_,_,_,1,2],
>              [_,_,3,_,_,4,_,_,_],
>              [_,_,_,_,_,_,_,_,3],
>              [_,1,_,2,5,_,_,_,_],
>              [6,_,_,_,_,_,7,_,_],
>              [_,_,_,_,2,_,_,_,_],
>              [_,_,7,_,_,_,4,_,_],
>              [5,_,_,1,6,_,_,8,_]]).
> 
> But SWI-Prolog still does it in around 3 seconds.
> SWI-Prolog does other 17-clue Sudokus in less than 100ms.
> 
> Are there any 17-clue Sudokus that take more time?

[toc] | [prev] | [next] | [standalone]

#14024

On 2024-03-24 17:26:20 +0000, Mild Shock said:

> https://academic.timwylie.com/17CSCI4341/sudoku.pdf

For an expamle about what is reasonable to expect see pages
  https://mlevanto.github.io/solver.html
  https://mlevanto.github.io/SudokuV.html
  https://mlevanto.github.io/Latina.html

The first one is a solver. It also determines whether the
solution is unique.

The other two problem generators. They are a bit slow but
still usable.

Buttons at the bottom are for saving the problem or solution
in different file formats.

-- 
Mikko

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.prolog

csiph-web