Re: [Factor-talk] Backtracking
Alexander, John - Nice exchange of ideas here; much obliged to you both. I've attached timers to each approach, and they're comparable, at approximately a second each. Alexander, your non-MACRO: def of `last3` - : last3 ( seq -- X Y Z ) 3 cut* nip first3 ; inline - is very appealing; I'll make use of this. Hadn't thought of it. John, as usual, your `solve` word cuts straight to the quick, in illustrating the use of the `backtrack` vocab. Factor is my 2nd language, after Forth (via Neon, circa 1984!), & a really great system to explore modern programming. Onward, ~cw On Sun, Oct 8, 2017 at 4:05 AM, Alexander Ilin wrote: > Hello, John! > > 08.10.2017, 07:46, "John Benediktsson" : > > Regarding unsafe-amb. You should use ``amb-lazy`` in compiled words. > Here's a simple version that prints all solutions. > > > As I said, a perfect solution! Thanks for the `amb-lazy` hint. > > ---=--- > Александр > > -- *~ Memento Amori* -- Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] Backtracking
Hello, John! 08.10.2017, 07:46, "John Benediktsson" :Regarding unsafe-amb. You should use ``amb-lazy`` in compiled words. Here's a simple version that prints all solutions. As I said, a perfect solution! Thanks for the `amb-lazy` hint. ---=---Александр -- Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] Backtracking
Hello, Alston! 08.10.2017, 06:55, "CW Alston" :The solution to the puzzle that I wrote doesn't use `amb`. I approached the problemwith `math.combinatorics` & `math.ranges` instead, so I'm not much help there.But I had to wrestle with the same conundrum, regarding compilation in the Listenerversus source file compilation. See if the example helps. I posted the (brief) sourcefile below. I like your approach using ``, because it tests fewer combinations towards a solution.I'd be very interested in an approach using `backtracking`! I think John posted a perfect one. In fact, I first learned about the `backtrack` vocab from his very own blog posts:https://re-factor.blogspot.ru/2015/06/send-more-money.htmlhttps://re-factor.blogspot.ru/2017/02/711.html ---=---Александр -- Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] Backtracking
Thank you for the reply, and for the code suggestions! 08.10.2017, 07:13, "CW Alston" :-for `last3` :IN: scratchpad { 1 2 3 4 5 6 } 3 tail spill-seq ! or something like it In fact, here's a non-MACRO:-way to do the same:: last3 ( seq -- X Y Z )3 cut* nip first3 ; inline ! --for `6array` :IN: scratchpad 5 6 7 8 9 10 6 narray Thanks, I forgot all about `narray`! ! - is undefined in Factor Version 0.98; should use `iota`.I didn't find anywhere in `sequences` or its child-vocabs.(I'm running factor-macosx-x86-64-2017-05-14-20-08.dmg): I'm on the bleeding edge, you see. They've renamed `iota` to `` and `iota-tuple` to `iota`. ---=---Александр --
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot___
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] Backtracking
You should use with the latest pre-release of 0.98.
Regarding unsafe-amb. You should use ``amb-lazy`` in compiled words.
Here's a simple version that prints all solutions. There's no reason to
use though if you disallow zero. You should just use numbers in
range [1,9].
:: solve ( -- )
[
10 [1,b) amb-lazy :> A
10 [1,b) amb-lazy :> B
10 [1,b) amb-lazy :> C
10 [1,b) amb-lazy :> D
10 [1,b) amb-lazy :> E
10 [1,b) amb-lazy :> F
{
[ { A B C D E F } all-unique? ]
[ D E < ]
[ E F < ]
[
A 100 * B 10 * + C + D * E 11 * * F 111 * * :> prod
prod sqrt >integer dup * prod =
]
} 0&& must-be-true { A B C D E F } .
] amb-all ;
On Sat, Oct 7, 2017 at 9:12 PM, CW Alston wrote:
> P.S. -- 3 small code suggestions:
> -for `last3` :
> IN: scratchpad { 1 2 3 4 5 6 } 3 tail spill-seq ! or something like it
> --- Data stack:
> 4
> 5
> 6
> ! -
> -for `6array` :
> IN: scratchpad 5 6 7 8 9 10 6 narray
> --- Data stack:
> { 5 6 7 8 9 10 }
> ! -
> is undefined in Factor Version 0.98; should use `iota`.
> I didn't find anywhere in `sequences` or its child-vocabs.
> (I'm running factor-macosx-x86-64-2017-05-14-20-08.dmg):
>
> IN: scratchpad \
> Error
> 1: \
>^
> No word named “” found in current vocabulary search path
>
>
> IN: scratchpad \ iota see
> USING: kernel math ;
> IN: sequences
> : iota ( n -- iota )
> dup 0 < [ non-negative-integer-expected ] when
> iota-tuple boa ; inline
> ! -
> ~cw
>
> On Sat, Oct 7, 2017 at 8:55 PM, CW Alston wrote:
>
>> Hi Alexander -
>> Regarding "Cannot apply “unsafe-amb” to a run-time computed value",
>> see `Optimizing compiler` in the source code browser,
>> & especially `bad-macro-input` under `Stack checker errors`:
>>
>> "Most code you write will run with the optimizing compiler. Sometimes,
>> the non-optimizing compiler is used, for example for listener
>> interactions,
>> or for running the quotation passed to call(."
>>
>> I was bitten by the same compiler issue in my `spill-seq` word (see code
>> below).
>> My solution worked fine interactively in the Listener, but flunked out in
>> a
>> source code compile. It took quite a bit of experimentation to compose an
>> idiom,
>> incorporating a MACRO: definiton & quotation calls, that would compile in
>> my source.
>> This seems to stem from the use of the optimizing compiler with source
>> files,
>> whereas the non-optimizing compiler used in the Listener is more
>> permissive.
>>
>> The solution to the puzzle that I wrote doesn't use `amb`. I approached
>> the problem
>> with `math.combinatorics` & `math.ranges` instead, so I'm not much help
>> there.
>> But I had to wrestle with the same conundrum, regarding compilation in
>> the Listener
>> versus source file compilation. See if the example helps. I posted the
>> (brief) source
>> file below.
>>
>> I'd be very interested in an approach using `backtracking`!
>> Cheers,
>> cw
>>
>> -- alternative solution follows
>>
>> ! Copyright (C) 2017 CW Alston.
>> ! See http://factorcode.org/license.txt for BSD license.
>> USING: combinators.short-circuit fry kernel kernel.private
>> locals macros math math.combinatorics math.functions math.ranges
>> multiline prettyprint sequences ;
>> IN: andrew-task*
>>
>> ! Problem suggested by Alexander Ilin:
>> ! The task is to find digits A, B, C, D, E, and F, such that:
>> ! all digits are 1..9,
>> ! all of the digits are different,
>> ! D < E < F,
>> ! ABC*D*EE*FFF = n^2, where n is an integer.
>>
>> ! number of possible sequences of digits 1-9, taken 6 at a time:
>> ! 9 6 nPk . => 60480
>>
>> ! put sequence elements on the stack
>> MACRO: spill-seq ( seq -- quot )
>> '[ _ [ length iota ] keep [ nth ] curry each ] ;
>>
>> ! check each permutation for solution to task specs
>> :: (check-6) ( perm-seq -- ? )
>>[ perm-seq spill-seq
>> :> F :> E :> D :> C :> B :> A
>> {
>> [ D E < E F < and ]
>> [
>> A 100 * B 10 * C + + :> ABC
>> 11 E * :> EE
>> 111 F * :> FFF
>> { ABC D EE FFF } product :> prod
>> prod sqrt >integer dup * prod =
>> ]
>> } 0&& ] ; inline
>>
>> : 9P6 ( -- permutations )
>> 1 9 [a,b] { } clone-like ! ( -- { 1 2 3 4 5 6 7 8 9 } )
>> 6 ; inline ! ( -- permutations )
>>
>> : solve-andrew ( -- seq )
>> 9P6 [ (check-6) call( -- ? ) ] find nip ;
>>
>> : solve-andrew. ( -- ) solve-andrew . ;
>>
>> MAIN: solve-andrew.
>>
>> /*
>> USE: andrew-task*
>> IN: scratchpad solve-andrew.
>> { 8 1 4 2 3 9 } ! solution
>>
>> ! checking:
>> IN: scratchpad 8 100 * 1 10 * 4 + + "abc" set
>> IN: scratchpad 11 3 * "ee" set
>> IN: scratchpad 111 9 * "fff" set
>> IN: scratchpad "abc" get 2 "ee" get "fff" get 4 narray
>>
>> --- Data stack:
>> { 814 2 33 999 }
>> IN: scratchpad product "
Re: [Factor-talk] Backtracking
P.S. -- 3 small code suggestions:
-for `last3` :
IN: scratchpad { 1 2 3 4 5 6 } 3 tail spill-seq ! or something like it
--- Data stack:
4
5
6
! -
-for `6array` :
IN: scratchpad 5 6 7 8 9 10 6 narray
--- Data stack:
{ 5 6 7 8 9 10 }
! -
is undefined in Factor Version 0.98; should use `iota`.
I didn't find anywhere in `sequences` or its child-vocabs.
(I'm running factor-macosx-x86-64-2017-05-14-20-08.dmg):
IN: scratchpad \
Error
1: \
^
No word named “” found in current vocabulary search path
IN: scratchpad \ iota see
USING: kernel math ;
IN: sequences
: iota ( n -- iota )
dup 0 < [ non-negative-integer-expected ] when
iota-tuple boa ; inline
! -
~cw
On Sat, Oct 7, 2017 at 8:55 PM, CW Alston wrote:
> Hi Alexander -
> Regarding "Cannot apply “unsafe-amb” to a run-time computed value",
> see `Optimizing compiler` in the source code browser,
> & especially `bad-macro-input` under `Stack checker errors`:
>
> "Most code you write will run with the optimizing compiler. Sometimes,
> the non-optimizing compiler is used, for example for listener
> interactions,
> or for running the quotation passed to call(."
>
> I was bitten by the same compiler issue in my `spill-seq` word (see code
> below).
> My solution worked fine interactively in the Listener, but flunked out in
> a
> source code compile. It took quite a bit of experimentation to compose an
> idiom,
> incorporating a MACRO: definiton & quotation calls, that would compile in
> my source.
> This seems to stem from the use of the optimizing compiler with source
> files,
> whereas the non-optimizing compiler used in the Listener is more
> permissive.
>
> The solution to the puzzle that I wrote doesn't use `amb`. I approached
> the problem
> with `math.combinatorics` & `math.ranges` instead, so I'm not much help
> there.
> But I had to wrestle with the same conundrum, regarding compilation in the
> Listener
> versus source file compilation. See if the example helps. I posted the
> (brief) source
> file below.
>
> I'd be very interested in an approach using `backtracking`!
> Cheers,
> cw
>
> -- alternative solution follows
>
> ! Copyright (C) 2017 CW Alston.
> ! See http://factorcode.org/license.txt for BSD license.
> USING: combinators.short-circuit fry kernel kernel.private
> locals macros math math.combinatorics math.functions math.ranges
> multiline prettyprint sequences ;
> IN: andrew-task*
>
> ! Problem suggested by Alexander Ilin:
> ! The task is to find digits A, B, C, D, E, and F, such that:
> ! all digits are 1..9,
> ! all of the digits are different,
> ! D < E < F,
> ! ABC*D*EE*FFF = n^2, where n is an integer.
>
> ! number of possible sequences of digits 1-9, taken 6 at a time:
> ! 9 6 nPk . => 60480
>
> ! put sequence elements on the stack
> MACRO: spill-seq ( seq -- quot )
> '[ _ [ length iota ] keep [ nth ] curry each ] ;
>
> ! check each permutation for solution to task specs
> :: (check-6) ( perm-seq -- ? )
>[ perm-seq spill-seq
> :> F :> E :> D :> C :> B :> A
> {
> [ D E < E F < and ]
> [
> A 100 * B 10 * C + + :> ABC
> 11 E * :> EE
> 111 F * :> FFF
> { ABC D EE FFF } product :> prod
> prod sqrt >integer dup * prod =
> ]
> } 0&& ] ; inline
>
> : 9P6 ( -- permutations )
> 1 9 [a,b] { } clone-like ! ( -- { 1 2 3 4 5 6 7 8 9 } )
> 6 ; inline ! ( -- permutations )
>
> : solve-andrew ( -- seq )
> 9P6 [ (check-6) call( -- ? ) ] find nip ;
>
> : solve-andrew. ( -- ) solve-andrew . ;
>
> MAIN: solve-andrew.
>
> /*
> USE: andrew-task*
> IN: scratchpad solve-andrew.
> { 8 1 4 2 3 9 } ! solution
>
> ! checking:
> IN: scratchpad 8 100 * 1 10 * 4 + + "abc" set
> IN: scratchpad 11 3 * "ee" set
> IN: scratchpad 111 9 * "fff" set
> IN: scratchpad "abc" get 2 "ee" get "fff" get 4 narray
>
> --- Data stack:
> { 814 2 33 999 }
> IN: scratchpad product "prod" set
> IN: scratchpad "prod" get sqrt >integer
>
> --- Data stack:
> 7326
> IN: scratchpad dup *
>
> --- Data stack:
> 53670276
> IN: scratchpad "prod" get = .
> t
> */
> ! -
>
> On Fri, Oct 6, 2017 at 10:30 AM, Alexander Ilin wrote:
>
>> Hello!
>>
>> I found a perfect task to learn the `backtrack` vocab, and have
>> successfully solved the problem (although the help system could use some
>> example code). The only question I have left is why can't I compile the
>> vocab below. I get the error that says "Cannot apply “unsafe-amb” to a
>> run-time computed value" in the `solve` word. It works perfectly well in
>> the listener, so why can't it work in a vocab?
>>
>> Could someone point out the reason for the error? Which part of the
>> quotation is run-time computed? I have inlined everything I could, but it
>> didn't help.
>>
>> ```
>> ! Copyright (C) 2017 Alexander Ilin.
>> ! See http://factorcode.org/license.txt for BSD license.
>> USING:
>> arrays backtrack
Re: [Factor-talk] Backtracking
Hi Alexander -
Regarding "Cannot apply “unsafe-amb” to a run-time computed value",
see `Optimizing compiler` in the source code browser,
& especially `bad-macro-input` under `Stack checker errors`:
"Most code you write will run with the optimizing compiler. Sometimes,
the non-optimizing compiler is used, for example for listener interactions,
or for running the quotation passed to call(."
I was bitten by the same compiler issue in my `spill-seq` word (see code
below).
My solution worked fine interactively in the Listener, but flunked out in a
source code compile. It took quite a bit of experimentation to compose an
idiom,
incorporating a MACRO: definiton & quotation calls, that would compile in
my source.
This seems to stem from the use of the optimizing compiler with source
files,
whereas the non-optimizing compiler used in the Listener is more permissive.
The solution to the puzzle that I wrote doesn't use `amb`. I approached the
problem
with `math.combinatorics` & `math.ranges` instead, so I'm not much help
there.
But I had to wrestle with the same conundrum, regarding compilation in the
Listener
versus source file compilation. See if the example helps. I posted the
(brief) source
file below.
I'd be very interested in an approach using `backtracking`!
Cheers,
cw
-- alternative solution follows
! Copyright (C) 2017 CW Alston.
! See http://factorcode.org/license.txt for BSD license.
USING: combinators.short-circuit fry kernel kernel.private
locals macros math math.combinatorics math.functions math.ranges
multiline prettyprint sequences ;
IN: andrew-task*
! Problem suggested by Alexander Ilin:
! The task is to find digits A, B, C, D, E, and F, such that:
! all digits are 1..9,
! all of the digits are different,
! D < E < F,
! ABC*D*EE*FFF = n^2, where n is an integer.
! number of possible sequences of digits 1-9, taken 6 at a time:
! 9 6 nPk . => 60480
! put sequence elements on the stack
MACRO: spill-seq ( seq -- quot )
'[ _ [ length iota ] keep [ nth ] curry each ] ;
! check each permutation for solution to task specs
:: (check-6) ( perm-seq -- ? )
[ perm-seq spill-seq
:> F :> E :> D :> C :> B :> A
{
[ D E < E F < and ]
[
A 100 * B 10 * C + + :> ABC
11 E * :> EE
111 F * :> FFF
{ ABC D EE FFF } product :> prod
prod sqrt >integer dup * prod =
]
} 0&& ] ; inline
: 9P6 ( -- permutations )
1 9 [a,b] { } clone-like ! ( -- { 1 2 3 4 5 6 7 8 9 } )
6 ; inline ! ( -- permutations )
: solve-andrew ( -- seq )
9P6 [ (check-6) call( -- ? ) ] find nip ;
: solve-andrew. ( -- ) solve-andrew . ;
MAIN: solve-andrew.
/*
USE: andrew-task*
IN: scratchpad solve-andrew.
{ 8 1 4 2 3 9 } ! solution
! checking:
IN: scratchpad 8 100 * 1 10 * 4 + + "abc" set
IN: scratchpad 11 3 * "ee" set
IN: scratchpad 111 9 * "fff" set
IN: scratchpad "abc" get 2 "ee" get "fff" get 4 narray
--- Data stack:
{ 814 2 33 999 }
IN: scratchpad product "prod" set
IN: scratchpad "prod" get sqrt >integer
--- Data stack:
7326
IN: scratchpad dup *
--- Data stack:
53670276
IN: scratchpad "prod" get = .
t
*/
! -
On Fri, Oct 6, 2017 at 10:30 AM, Alexander Ilin wrote:
> Hello!
>
> I found a perfect task to learn the `backtrack` vocab, and have
> successfully solved the problem (although the help system could use some
> example code). The only question I have left is why can't I compile the
> vocab below. I get the error that says "Cannot apply “unsafe-amb” to a
> run-time computed value" in the `solve` word. It works perfectly well in
> the listener, so why can't it work in a vocab?
>
> Could someone point out the reason for the error? Which part of the
> quotation is run-time computed? I have inlined everything I could, but it
> didn't help.
>
> ```
> ! Copyright (C) 2017 Alexander Ilin.
> ! See http://factorcode.org/license.txt for BSD license.
> USING:
> arrays backtrack combinators.short-circuit infix kernel
> locals math math.functions prettyprint scratchpad
> sequences sequences.private sets
> ;
>
> IN: andrew-task
>
> ! The task is to find digits A, B, C, D, E, and F, such that:
> ! all digits are 1..9,
> ! all of the digits are different,
> ! D < E < F,
> ! ABC*D*EE*FFF = n^2, where n is an integer.
>
> ALIAS: 0? zero?
>
> : last3 ( seq -- X Y Z )
> unclip-last [ unclip-last [ last ] dip ] dip ; inline
>
> : 6array ( A B C D E F -- {ABCDEF} )
> 4array swap prefix swap prefix ; inline
>
> : check-success ( {ABCDEF} -- )
> {
> [ [ 0? ] count 0? ]
> [ duplicates empty? ]
> [ last3 [| D E F | D E < E F < and ] call ]
> [
> [ first3 ] [ last3 ] bi
> [| A B C D E F |
> [infix A * 100 + B * 10 + C infix] :> ABC
> 11 E * :> EE
> 111 F * :> FFF
> { ABC D EE FFF } product :> prod
> prod sqrt >integer dup * prod =
>
[Factor-talk] Backtracking
Hello!
I found a perfect task to learn the `backtrack` vocab, and have successfully
solved the problem (although the help system could use some example code). The
only question I have left is why can't I compile the vocab below. I get the
error that says "Cannot apply “unsafe-amb” to a run-time computed value" in the
`solve` word. It works perfectly well in the listener, so why can't it work in
a vocab?
Could someone point out the reason for the error? Which part of the quotation
is run-time computed? I have inlined everything I could, but it didn't help.
```
! Copyright (C) 2017 Alexander Ilin.
! See http://factorcode.org/license.txt for BSD license.
USING:
arrays backtrack combinators.short-circuit infix kernel
locals math math.functions prettyprint scratchpad
sequences sequences.private sets
;
IN: andrew-task
! The task is to find digits A, B, C, D, E, and F, such that:
! all digits are 1..9,
! all of the digits are different,
! D < E < F,
! ABC*D*EE*FFF = n^2, where n is an integer.
ALIAS: 0? zero?
: last3 ( seq -- X Y Z )
unclip-last [ unclip-last [ last ] dip ] dip ; inline
: 6array ( A B C D E F -- {ABCDEF} )
4array swap prefix swap prefix ; inline
: check-success ( {ABCDEF} -- )
{
[ [ 0? ] count 0? ]
[ duplicates empty? ]
[ last3 [| D E F | D E < E F < and ] call ]
[
[ first3 ] [ last3 ] bi
[| A B C D E F |
[infix A * 100 + B * 10 + C infix] :> ABC
11 E * :> EE
111 F * :> FFF
{ ABC D EE FFF } product :> prod
prod sqrt >integer dup * prod =
] call
]
} 1&& must-be-true ; inline
: solve ( -- )
[
10 amb 10 amb 10 amb
10 amb 10 amb 10 amb
6array dup check-success .
] amb-all ;
MAIN: solve
```
---=---
Александр
--
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
___
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
