For fun i did do a backtrack implementation in Sleep yesterday. So now I can write prolog type stuff:
Here is the code for backtrack. This function accepts an array of arrays as the argument. Each position of the top level array represents a free variable that I want to bind something to. And each array held at each position represents the domain of all possible values I can bind to that free variable. Using coroutines (to promote lazy generation of bound values) backtrack assigns all possible combinations of the values to each free position and returns a potential result.
sub backtrack
{
local('$var $next $slist');
if (size($1) > 1)
{
$slist = sublist($1, 1);
foreach $var ($1[0])
{
while $next ([$this: $slist])
{
yield concat($var, $next);
}
}
}
else
{
foreach $var ($1[0])
{
yield $var;
}
}
}
Here is the SEND + MORE = MONEY puzzle written in Sleep using this.
@digits = @(0, 2, 3, 4, 5, 6, 7, 8, 9);
sub isAnswer
{
local('$S $E $N $D $M $O $R $Y');
($S, $E, $N, $D, $M, $O, $R, $Y) = $1;
if ( (int("$S$E$N$D") + int("$M$O$R$E")) == int("$M$O$N$E$Y"))
{
# make sure there are no duplicates
if (size(putAll(%(), $1, { return 1; })) == 8)
{
return 1;
}
}
}
# S E N D M O R Y
while $potential (backtrack(@(@digits, @digits, @digits, @digits, @(1), @digits, @digits, @digits)))
{
if (isAnswer($potential))
{
local('$S $E $N $D $M $O $R $Y');
($S, $E, $N, $D, $M, $O, $R, $Y) = $potential;
println(" $S$E$N$D");
println(" + $M$O$R$E");
println("-----------");
println(" $M$O$N$E$Y");
return;
}
}
Not the fastest thing in the world. It takes about 455 seconds for Sleep to solve this puzzle. I think it has to analyze over 4.5 million solutions to do this. Oh well, that is what I get with an interpreted language sitting on top of a virtual machine.
Here is another problem... finding integer solutions for a circle of radius 5:
global('@digits $solution $X $Y');
@digits = @(-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5);
while $solution (backtrack(@(@digits, @digits)))
{
($X, $Y) = $solution;
if ((($X * $X) + ($Y * $Y)) == 25)
{
println("$X $+ , $Y");
}
}
I became inspired to play with all this when I saw some examples of erlang's list comprehension in action. Its pretty neat how they enable a mechanism for logic programming. I've thought about adding something like it to Sleep. Fortunately Sleep does have yield and that does enable the backtracking. So maybe not :)
http://en.wikibooks.org/wiki/Erlang_Programming/List_Comprehensions
|
