Paul Rubin schrieb am Montag, 13. Februar 2023 um 21:31:27 UTC+1:
> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> > However, given that your C++ solution is a lot faster and cannot
> > benefit from lazy evaluation, I expect that the potential lazy
> > evaluation advantage does not happen in this Haskell program.
>
> OK, here is my insane Forth version. Runtime with gforth-fast 0.7 about
> 1.4 seconds on same laptop as before. Same brute force algorithm. Uses
> the following highly recommended (lol) Forth techniques:
>
> - ROLL and FPICK with variable depths up to 10 deep
> - 13 local variables in one word
> - stores temporary small integer values on floating point stack
> (this works with IEEE floating point, YMMV otherwise)
> - A couple more that I have forgotten.
>
> ================================================================
>
> : 10f@>s ( copy 10 integers from fp stack to data stack :O )
> 10 0 do 9 i - fpick f>s loop ;
>
> : checkresult ( -- )
> 10f@>s { x0 x1 s e n d m o r y }
> m 0> x0 x1 > and IF
> s 1000 * e 100 * + n 10 * + d + { send }
> m 1000 * o 100 * + r 10 * + e + { more }
> m 10000 * o 1000 * + n 100 * + e 10 * + y + { money }
> send more + money = IF
> send . more . money . cr
> THEN
> THEN ;
>
> : rec ( n1 n2 ... )
> depth 0= IF
> checkresult
> ELSE
> depth { d }
> d 0 DO
> s>f RECURSE f>s d 1- ROLL
> LOOP
> THEN ;
>
> 0 1 2 3 4 5 6 7 8 9 rec bye

Kool!

Not as small but here's another permuter:

CREATE LET 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 ,

: EXCHANGE ( i j -- )
cells let + swap cells let +
dup @ >r swap dup @ rot ! r> swap ! ;

: LT@ ( n -- ) cells let + @ ;

: M 0 lt@ ; : O 1 lt@ ; : R 2 lt@ ; : Y 3 lt@ ;
: S 4 lt@ ; : E 5 lt@ ; : N 6 lt@ ; : D 7 lt@ ;

: S1 S 10 * E + 10 * N + 10 * D + ;
: S2 M 10 * O + 10 * R + 10 * E + ;
: S3 M 10 * O + 10 * N + 10 * E + 10 * Y + ;

: CONSTR ( -- flag )
false
M 1 <> IF EXIT THEN
s1 s2 + s3 <> IF EXIT THEN
drop true ;

: USE-PERM ( -- )
constr IF
cr ." SEND+MORE=MONEY -> " s1 . s2 . s3 .
ABORT THEN ;

\ Heap's algorithm, thanks to Gerry Jackson
: PERMUTE ( n -- ) \ n assumed > 0
1- ?dup 0= IF use-perm EXIT THEN
dup 0 DO
dup recurse
dup over 1 and negate i and exchange
LOOP
recurse ;

10 PERMUTE

On 13/02/2023 22:11, minf...@arcor.de wrote:
> Paul Rubin schrieb am Montag, 13. Februar 2023 um 21:31:27 UTC+1:
>> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> However, given that your C++ solution is a lot faster and cannot
>>> benefit from lazy evaluation, I expect that the potential lazy
>>> evaluation advantage does not happen in this Haskell program.
>>
>> OK, here is my insane Forth version. Runtime with gforth-fast 0.7 about
>> 1.4 seconds on same laptop as before. Same brute force algorithm. Uses
>> the following highly recommended (lol) Forth techniques:
>>
>> - ROLL and FPICK with variable depths up to 10 deep
>> - 13 local variables in one word
>> - stores temporary small integer values on floating point stack
>> (this works with IEEE floating point, YMMV otherwise)
>> - A couple more that I have forgotten.
>>
>> ================================================================
>>
>> : 10f@>s ( copy 10 integers from fp stack to data stack :O )
>> 10 0 do 9 i - fpick f>s loop ;
>>
>> : checkresult ( -- )
>> 10f@>s { x0 x1 s e n d m o r y }
>> m 0> x0 x1 > and IF
>> s 1000 * e 100 * + n 10 * + d + { send }
>> m 1000 * o 100 * + r 10 * + e + { more }
>> m 10000 * o 1000 * + n 100 * + e 10 * + y + { money }
>> send more + money = IF
>> send . more . money . cr
>> THEN
>> THEN ;
>>
>> : rec ( n1 n2 ... )
>> depth 0= IF
>> checkresult
>> ELSE
>> depth { d }
>> d 0 DO
>> s>f RECURSE f>s d 1- ROLL
>> LOOP
>> THEN ;
>>
>> 0 1 2 3 4 5 6 7 8 9 rec bye
>
> Kool!
>
> Not as small but here's another permuter:
>
> CREATE LET 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 ,
>
> : EXCHANGE ( i j -- )
> cells let + swap cells let +
> dup @ >r swap dup @ rot ! r> swap ! ;
>
> : LT@ ( n -- ) cells let + @ ;
>
> : M 0 lt@ ; : O 1 lt@ ; : R 2 lt@ ; : Y 3 lt@ ;
> : S 4 lt@ ; : E 5 lt@ ; : N 6 lt@ ; : D 7 lt@ ;
>
> : S1 S 10 * E + 10 * N + 10 * D + ;
> : S2 M 10 * O + 10 * R + 10 * E + ;
> : S3 M 10 * O + 10 * N + 10 * E + 10 * Y + ;
>
> : CONSTR ( -- flag )
> false
> M 1 <> IF EXIT THEN
> s1 s2 + s3 <> IF EXIT THEN
> drop true ;
>
> : USE-PERM ( -- )
> constr IF
> cr ." SEND+MORE=MONEY -> " s1 . s2 . s3 .
> ABORT THEN ;
>
> \ Heap's algorithm, thanks to Gerry Jackson
> : PERMUTE ( n -- ) \ n assumed > 0
> 1- ?dup 0= IF use-perm EXIT THEN
> dup 0 DO
> dup recurse
> dup over 1 and negate i and exchange
> LOOP
> recurse ;
>
> 10 PERMUTE

ISTM that using Heap's algorithm to generate the permutations offers
more opportunities for optimisation of a solution to this problem. This
is because the algorithm generates each permutation from the previous
one by interchanging a single pair of elements. The position of the
other n-2 elements are unchanged. Therefore in the SEND + MORE = MONEY
equation only the increments/decrements for the three components of the
equation need to be calculated and applied to the result of the previous
calculation.

For example suppose digits 12345678 are allocated to SENDMORY as
SENDMORY
12345678
then
SEND MORE MONEY becomes
1234 5672 56328
suppose the next permutation is generated by exchanging digits 4 and 5
then D contributes +1 to SEND
M contributes -1000 to MORE and -10000 to MONEY
So instead of doing the entire calculation only these increments need to
be added to SEND MORE and MONEY from the previous permutation.

These increments could be pre-calculated as a power of 10 for each
letter to be multiplied by the difference in the digits changed for that
letter.

I don't know whether that's it's worth going to that much trouble.

As a wild speculation I wonder if this suggests a way of homing in on
the solution.

--
Gerry

Gerry Jackson <do-not-use@swldwa.uk> writes:
> ISTM that using Heap's algorithm to generate the permutations... This
> is because the algorithm generates each permutation from the previous
> one by interchanging a single pair of elements.

I wasn't familiar with this algorithm. It sounds like a good approach,
and I will have to study it.

On 15/02/2023 9:13 am, Paul Rubin wrote:
> Gerry Jackson <do-not-use@swldwa.uk> writes:
>> ISTM that using Heap's algorithm to generate the permutations... This
>> is because the algorithm generates each permutation from the previous
>> one by interchanging a single pair of elements.
>
> I wasn't familiar with this algorithm.

Same here. Being short and simple, I've included it in my collection of
miscellaneous routines. Neat implementation.

Paul Rubin schrieb am Dienstag, 14. Februar 2023 um 23:13:47 UTC+1:
> Gerry Jackson <do-no...@swldwa.uk> writes:
> > ISTM that using Heap's algorithm to generate the permutations... This
> > is because the algorithm generates each permutation from the previous
> > one by interchanging a single pair of elements.
> I wasn't familiar with this algorithm. It sounds like a good approach,
> and I will have to study it.

Happy reading ;-)
https://sedgewick.io/wp-content/themes/sedgewick/papers/1977Permutation.pdf

On Tuesday, February 14, 2023 at 6:11:05 PM UTC+1, Gerry Jackson wrote:
> On 13/02/2023 22:11, minf...@arcor.de wrote:
> > Paul Rubin schrieb am Montag, 13. Februar 2023 um 21:31:27 UTC+1:
> >> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
[..]
> ISTM that using Heap's algorithm to generate the permutations offers
> more opportunities for optimisation of a solution to this problem. This
> is because the algorithm generates each permutation from the previous
> one by interchanging a single pair of elements. The position of the
> other n-2 elements are unchanged. Therefore in the SEND + MORE = MONEY
> equation only the increments/decrements for the three components of the
> equation need to be calculated and applied to the result of the previous
> calculation.
[..]
This algorithm removes the random element that I mentioned in my remark on
parallellism. With no recursion overhead and no duplicated tries, that should be
quite efficient for certain types of problems. And, of course, simple to implement.

-marcel

Marcel Hendrix schrieb am Mittwoch, 15. Februar 2023 um 09:12:06 UTC+1:
> On Tuesday, February 14, 2023 at 6:11:05 PM UTC+1, Gerry Jackson wrote:
> > On 13/02/2023 22:11, minf...@arcor.de wrote:
> > > Paul Rubin schrieb am Montag, 13. Februar 2023 um 21:31:27 UTC+1:
> > >> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> [..]
> > ISTM that using Heap's algorithm to generate the permutations offers
> > more opportunities for optimisation of a solution to this problem. This
> > is because the algorithm generates each permutation from the previous
> > one by interchanging a single pair of elements. The position of the
> > other n-2 elements are unchanged. Therefore in the SEND + MORE = MONEY
> > equation only the increments/decrements for the three components of the
> > equation need to be calculated and applied to the result of the previous
> > calculation.
> [..]
> This algorithm removes the random element that I mentioned in my remark on
> parallellism. With no recursion overhead and no duplicated tries, that should be
> quite efficient for certain types of problems. And, of course, simple to implement.

It seems that the most efficient non-recursive permutation algorithms require
a second control array. So in addition to swapping cells in the target array, control
array cells have to be managed as well, which eats up the promised efficiency gain.
https://www.quickperm.org/

iForth64 now runs on snellius (https://servicedesk.surf.nl/wiki/display/WIKI/Snellius)
I didn't even need to recompile, just copied the binaries from my 5800X straight onto
the surf node.

FORTH> .TICKER-INFO
AMD EPYC 7F72 24-Core Processor
TICKS-GET uses os time & PROCESSOR-CLOCK 3000MHz
Do: < n TO PROCESSOR-CLOCK RECALIBRATE >
ok
FORTH> GO
Solving ... 26 microseconds elapsed, the solution is: 9567 + 1085 = 10652 ok

'Super' does not mean 'superfast' :--)

-marcel

On 16/02/2023 6:45 am, Marcel Hendrix wrote:
> iForth64 now runs on snellius (https://servicedesk.surf.nl/wiki/display/WIKI/Snellius)
> I didn't even need to recompile, just copied the binaries from my 5800X straight onto
> the surf node.
>
> FORTH> .TICKER-INFO
> AMD EPYC 7F72 24-Core Processor
> TICKS-GET uses os time & PROCESSOR-CLOCK 3000MHz
> Do: < n TO PROCESSOR-CLOCK RECALIBRATE >
> ok
> FORTH> GO
> Solving ... 26 microseconds elapsed, the solution is: 9567 + 1085 = 10652 ok
>
> 'Super' does not mean 'superfast' :--)

Brain the size of a planet and you give it useless tasks to perform.

On Thursday, February 16, 2023 at 1:20:08 AM UTC+1, dxforth wrote:
> Brain the size of a planet and you give it useless tasks to perform.

Starting Forth bottom-up.

-marcel

minf...@arcor.de schrieb am Mittwoch, 15. Februar 2023 um 10:16:33 UTC+1:
> It seems that the most efficient non-recursive permutation algorithms require
> a second control array. So in addition to swapping cells in the target array, control
> array cells have to be managed as well, which eats up the promised efficiency gain.

Here's with non-recursive permutation algorithm. Quick timing showed no speed
increase significant for practical purposes. Only benefit would be less 'stress' on the
return stack.

CREATE LET 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 ,

: EXCHANGE ( i j -- )
cells let + swap cells let +
dup @ >r swap dup @ rot ! r> swap ! ;

: LT@ ( n -- ) cells let + @ ;

: M 0 lt@ ; : O 1 lt@ ; : R 2 lt@ ; : Y 3 lt@ ;
: S 4 lt@ ; : E 5 lt@ ; : N 6 lt@ ; : D 7 lt@ ;

: S1 S 10 * E + 10 * N + 10 * D + ;
: S2 M 10 * O + 10 * R + 10 * E + ;
: S3 M 10 * O + 10 * N + 10 * E + 10 * Y + ;

: CONSTR ( -- flag )
false
M 1 <> IF EXIT THEN
s1 s2 + s3 <> IF EXIT THEN
drop true ;

: USE-PERM ( -- )
constr IF
cr ." SEND+MORE=MONEY -> " s1 . s2 . s3 .
ABORT THEN ;

\ ----- Heap's algorithm recursive -----

: PERMUTE-R ( n -- ) \ n assumed > 0
1- ?dup 0= IF use-perm EXIT THEN
dup 0 DO
dup recurse
dup over 1 and negate i and exchange
LOOP
recurse ;

\ 10 PERMUTE-R

\ +++++ Heap's algorithm non-recursive +++++

\ control array:
CREATE CAR 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
: CA ( n -- ) cells car + ;

: PERMUTE-NR ( n -- ) \ n assumed > 0
use-perm
1 BEGIN 2dup >= WHILE
dup ca @ over <
IF dup 1 and
IF dup ca @ ELSE 0 THEN over exchange use-perm
1 swap ca +! 1
ELSE 0 over ca ! 1+
THEN
REPEAT 2drop ;

10 PERMUTE-NR

On Friday, February 17, 2023 at 2:36:38 PM UTC+1, minf...@arcor.de wrote:
> minf...@arcor.de schrieb am Mittwoch, 15. Februar 2023 um 10:16:33 UTC+1:
[..]
> 10 PERMUTE-NR

PERMUTE-NR is ~700x slower than my latest solution ( 14 microseconds ) :--(

-marcel

On Friday, February 17, 2023 at 6:05:51 PM UTC+1, Marcel Hendrix wrote:
> On Friday, February 17, 2023 at 2:36:38 PM UTC+1, minf...@arcor.de wrote:
> > minf...@arcor.de schrieb am Mittwoch, 15. Februar 2023 um 10:16:33 UTC+1:
> [..]
> > 10 PERMUTE-NR
>
> PERMUTE-NR is ~700x slower than my latest solution ( 14 microseconds ) :--(

Including program development, this was even quicker:

"Me> Assume every character is actually a figure, which calculation is made here: SEND+MORE=MONEY

ChatGPT> In the SEND+MORE=MONEY puzzle, the goal is to assign each letter a digit from 0 to 9 in such a way that the resulting mathematical equation is correct. Each letter represents a distinct digit, and the leftmost digit in any number cannot be 0.

Here is one possible solution to the puzzle:

O = 0
M = 1
Y = 2
E = 5
N = 6
D = 7
R = 8
S = 9

With these assignments, the equation becomes:

9567 + 1085 = 10652

which is true."

;-) Hans Bezemer

Hans Bezemer schrieb am Freitag, 17. Februar 2023 um 18:29:07 UTC+1:
> On Friday, February 17, 2023 at 6:05:51 PM UTC+1, Marcel Hendrix wrote:
> > On Friday, February 17, 2023 at 2:36:38 PM UTC+1, minf...@arcor.de wrote:
> > > minf...@arcor.de schrieb am Mittwoch, 15. Februar 2023 um 10:16:33 UTC+1:
> > [..]
> > > 10 PERMUTE-NR
> >
> > PERMUTE-NR is ~700x slower than my latest solution ( 14 microseconds ) :--(
> Including program development, this was even quicker:
>
> "Me> Assume every character is actually a figure, which calculation is made here: SEND+MORE=MONEY
>
> ChatGPT> In the SEND+MORE=MONEY puzzle, the goal is to assign each letter a digit from 0 to 9 in such a way that the resulting mathematical equation is correct. Each letter represents a distinct digit, and the leftmost digit in any number cannot be 0.
>
> Here is one possible solution to the puzzle:
>
> O = 0
> M = 1
> Y = 2
> E = 5
> N = 6
> D = 7
> R = 8
> S = 9
>
> With these assignments, the equation becomes:
> 9567 + 1085 = 10652
> which is true."
>
> ;-) Hans Bezemer

Think of it, computers have come a long way since:

The oldest computer can be traced back to Adam and Eve.
Surprise! Surprise!
It was an apple.
But with extremely limited memory.
Just 1 byte.
Then everything crashed.

On Friday, February 17, 2023 at 7:15:40 PM UTC+1, minf...@arcor.de wrote:
> Think of it, computers have come a long way since.

It often is way off - but sometimes it amazes me. I recently wrote a medium sized program for work.
I fed it to ChatGPT - with minimal comments. Explain it. And it returned this (a bit more, but anyways):

"The program initializes some resources, including two binary search tables "names" and "counts" to store
field values and their frequencies, respectively, and an array of dynamic strings "field-names" to store
the field names.

The main logic of the program is in a loop that reads the CSV file, extracts the field values, and counts
the frequency of each field value. The loop continues until it reaches the end of the file, and then it
prints out the results for each field value. Finally, if the "fodsfile" flag is set, the program opens a FODS
file and writes the results to it".

That's right on the money. There was more, but those were pretty spot on as well. Amazing..

Hans Bezemer

On Friday, February 17, 2023 at 6:29:07 PM UTC+1, Hans Bezemer wrote:
> On Friday, February 17, 2023 at 6:05:51 PM UTC+1, Marcel Hendrix wrote:
> > On Friday, February 17, 2023 at 2:36:38 PM UTC+1, minf...@arcor.de wrote:
> > > minf...@arcor.de schrieb am Mittwoch, 15. Februar 2023 um 10:16:33 UTC+1:
> > [..]
> > > 10 PERMUTE-NR
> >
> > PERMUTE-NR is ~700x slower than my latest solution ( 14 microseconds ) :--(
[..]
> Including program development, this was even quicker:
>
> "Me> Assume every character is actually a figure, which calculation is made here: SEND+MORE=MONEY
>
> ChatGPT> In the SEND+MORE=MONEY puzzle, the goal is to assign each letter a digit from 0 to 9
> in such a way that the resulting mathematical equation is correct. Each letter represents a distinct digit,
> and the leftmost digit in any number cannot be 0.
>
> Here is one possible solution to the puzzle:
>
> O = 0
> M = 1
> Y = 2
> E = 5
> N = 6
> D = 7
> R = 8
> S = 9
>
> With these assignments, the equation becomes:
> 9567 + 1085 = 10652
> which is true."
>
> ;-) Hans Bezemer

I also asked it that. It gave almost the same explanation and the same solution.
However, then I asked for another solution, and it gave me a wrong one, twice --
apparently it assumes the audience is not checking. In the end it did produce
a correct answer. Of course, when I said it was wrong, it quickly agreed.

It also could place the quotes to "Who is on third," and "What is the answer to
everything?" Again, it refused to defend its answers and simply agreed with
me that the answer to the latter is 46.

I thought about it backing down so quickly. Commercially it makes sense -- what
would happen if chatGPT started giving correct and unrefutable but inconvenient
answers to (e.g.) its American audience? Stock would plummet.

-marcel

On 18/02/2023 12:36 am, minf...@arcor.de wrote:
>
> Here's with non-recursive permutation algorithm. Quick timing showed no speed
> increase significant for practical purposes. Only benefit would be less 'stress' on the
> return stack.

Haven't measured it but appears to be less of an issue than the time taken
to generate the permutations which rises factorially. The latter is likely
to get you first.

On 18/02/2023 5:32 am, Marcel Hendrix wrote:
>
> I thought about it backing down so quickly. Commercially it makes sense -- what
> would happen if chatGPT started giving correct and unrefutable but inconvenient
> answers to (e.g.) its American audience? Stock would plummet.

When is Forth's (our) second coming? Perhaps nobody here has invested in that :)

dxforth schrieb am Samstag, 18. Februar 2023 um 01:51:35 UTC+1:
> On 18/02/2023 12:36 am, minf...@arcor.de wrote:
> >
> > Here's with non-recursive permutation algorithm. Quick timing showed no speed
> > increase significant for practical purposes. Only benefit would be less 'stress' on the
> > return stack.
> Haven't measured it but appears to be less of an issue than the time taken
> to generate the permutations which rises factorially. The latter is likely
> to get you first.

Brute-force permutations over the 10 decimal digits 0..9 don't rise factorially unless you
increase the base.

But principally you are right. The Magic Hexagon puzzle cannot be solved by calculating
all possible permutations over 19 positions - it would run for weeks (whereas Prolog
solves it within less than a second by working the constraints).

The point is that speed matters when you are sure a priori that there is at least one solution.

On Saturday, February 18, 2023 at 8:11:11 AM UTC+1, minf...@arcor.de wrote:
> dxforth schrieb am Samstag, 18. Februar 2023 um 01:51:35 UTC+1:
> > On 18/02/2023 12:36 am, minf...@arcor.de wrote:
> > >
> > > Here's with non-recursive permutation algorithm. Quick timing showed no speed
> > > increase significant for practical purposes. Only benefit would be less 'stress' on the
> > > return stack.
> > Haven't measured it but appears to be less of an issue than the time taken
> > to generate the permutations which rises factorially. The latter is likely
> > to get you first.
> Brute-force permutations over the 10 decimal digits 0..9 don't rise factorially unless you
> increase the base.
>
> But principally you are right. The Magic Hexagon puzzle cannot be solved by calculating
> all possible permutations over 19 positions - it would run for weeks (whereas Prolog
> solves it within less than a second by working the constraints).
>
> The point is that speed matters when you are sure a priori that there is at least one solution.

For me, there is still some magic attached to this approach. It seems obvious
that pruning the number of paths to try would always be better than randomly
trying them all.

-marcel

Marcel Hendrix schrieb am Samstag, 18. Februar 2023 um 08:59:35 UTC+1:
> On Saturday, February 18, 2023 at 8:11:11 AM UTC+1, minf...@arcor.de wrote:
> > dxforth schrieb am Samstag, 18. Februar 2023 um 01:51:35 UTC+1:
> > > On 18/02/2023 12:36 am, minf...@arcor.de wrote:
> > > >
> > > > Here's with non-recursive permutation algorithm. Quick timing showed no speed
> > > > increase significant for practical purposes. Only benefit would be less 'stress' on the
> > > > return stack.
> > > Haven't measured it but appears to be less of an issue than the time taken
> > > to generate the permutations which rises factorially. The latter is likely
> > > to get you first.
> > Brute-force permutations over the 10 decimal digits 0..9 don't rise factorially unless you
> > increase the base.
> >
> > But principally you are right. The Magic Hexagon puzzle cannot be solved by calculating
> > all possible permutations over 19 positions - it would run for weeks (whereas Prolog
> > solves it within less than a second by working the constraints).
> >
> > The point is that speed matters when you are sure a priori that there is at least one solution.
> For me, there is still some magic attached to this approach. It seems obvious
> that pruning the number of paths to try would always be better than randomly
> trying them all.
>

CLP is a truly fascinating topic, very much underrated. Sniff into the basics (see page 20ff):
https://www.cs.upc.edu/~erodri/webpage/cps/theory/cp/intro/slides.pdf

Software-wise, backtracking requires keeping complete search states in memory for each branch.
Those states comprise the (so-far pruned) domains of each variable, those are big objects.
https://en.wikipedia.org/wiki/AC-3_algorithm

There is a rather compact Python constraint solver:
https://files.pythonhosted.org/packages/37/8b/5f1bc2734ca611943e1d6733ee244238679f6410a10cd45ede55a61a8402/python-constraint-1.4.0.tar.bz2
Sources are in subfolder /constraint/__init.py__

Standard Forth would have to be tooled up too much to hope to come close to it.

On Saturday, February 18, 2023 at 8:59:35 AM UTC+1, Marcel Hendrix wrote:
[..]
> For me, there is still some magic attached to this approach. It seems obvious
> that pruning the number of paths to try would always be better than randomly
> trying them all.
>
> -marcel

One thing that tricked me was that the best algorithm had very little variation in the
elapsed time. That is solved: I forgot that I averaged over 1000 runs. That removes
most of the magic.

Here is a graph:

FORTH> GO:
data = [
1483 11
4711 32
2281 15
787 5
1418 10
1500 10
1218 8
194 1
2748 19
757 5
3062 20
6727 45
9049 61
996 7
139 1
5418 36
1530 10
7151 47
2122 14
6732 45
2220 15
1933 12
1448 9
526 3
353 2
9012 61
7225 49
3592 24
6518 45
351 2
253 1
3328 22
5591 37
530 3
642 4
908 6
2517 16
3824 26
1385 9
3503 23
6569 44
3014 20
494 3
2379 15
458 3
1606 11
243 2
4478 29
4999 33
362 2
3765 24
5302 37
9505 65
1267 8
1490 10
6159 41
1159 8
1787 12
3057 20
3445 23
3562 24
8708 62
1368 10
3411 24
1053 7
707 4
4901 32
51 0
1579 11
1292 8
2696 18
978 6
1026 7
3886 27
7605 50
2282 15
1088 7
2847 19
1502 10
1313 9
9272 66
3985 26
855 6
903 6
7492 50
477 3
6297 42
382 2
757 5
1498 9
4803 32
3441 23
1627 11
3508 23
7551 51
2280 16
2264 15
5765 38
560 4
43 0
]; sd = sort(data);
figure(1); clf;
plot(0.001*sd(:,1),sd(:,2),'LineWidth',2); grid on;
xlabel('\bftries [x1000]'); ylabel('\bfelapsed time [\mus]'); title('\bfSEND+MORE=MONEY in iForth')

See https://ibb.co/Brp9Hcy .

So it more or less linear in time, with a very likelyhood that it more than 10,000 tries are needed.
As shown earlier, with 1000 tries 20 useconds worst-case is almost guaranteed.

-marcel

On Saturday, February 18, 2023 at 10:25:20 AM UTC+1, minf...@arcor.de wrote:
> Marcel Hendrix schrieb am Samstag, 18. Februar 2023 um 08:59:35 UTC+1:
> > On Saturday, February 18, 2023 at 8:11:11 AM UTC+1, minf...@arcor.de wrote:
[..]
> Standard Forth would have to be tooled up too much to hope to come close to it.

I won't bite :--)

-marcel

On Saturday, February 18, 2023 at 8:59:35 AM UTC+1, Marcel Hendrix wrote:
> For me, there is still some magic attached to this approach. It seems obvious
> that pruning the number of paths to try would always be better than randomly
> trying them all.
In essence you're right. I have my stack-optimizer discarding any diagrams which
result in datastack or returnstack underflow. However, there are plenty of sequences
that are clearly detrimental like:
DUP DROP
OVER DROP
SWAP SWAP
ROT ROT ROT
>R R>
R> >R
etc.

It makes no sense to pursue those. However, this list is not exhaustive. It would
most certainly complicate the program. And since it is a brute force program, it
eliminates only a limited number of cases - while burning up CPU time in order
to pursue them. So - how much time can you reasonably save here?

A seven word solution takes less than a second. Usually - if you need a solution
that exceeds 8 words, it's usually not going to work at all (in my experience) -
and you're better off with a solution using higher order words (like 2SWAP, 2DROP).

IMHO - always be careful when optimizing. I recently did some "optimizing" - and
while benchmarking I found out that in some cases, the "optimized" solution was
actually 10% SLOWER. So I combined the old AND the new routine in order to fix
that so in the WORST case scenario both were at least equally fast - and in the BEST
case the new one was almost twice as fast.

Lesson learned - no matter how well you think you know your own compiler, always
test your solutions and challenge your own assumptions.

Hans Bezemer

---8<---
$ pp4th -x stackopt.4th abc abcabc
- Trying a 1 word solution..
No solutions.
- Trying a 2 word solution..
No solutions.
- Trying a 3 word solution..
No solutions.
- Trying a 4 word solution..
No solutions.
- Trying a 5 word solution..
No solutions.
- Trying a 6 word solution..
No solutions.
- Trying a 7 word solution..
>r over over r@ rot rot r>
---8<---

On Saturday, February 18, 2023 at 4:01:54 PM UTC+1, Hans Bezemer wrote:
> On Saturday, February 18, 2023 at 8:59:35 AM UTC+1, Marcel Hendrix wrote:
[..]
> Hans Bezemer
>
> ---8<---
> $ pp4th -x stackopt.4th abc abcabc
> - Trying a 1 word solution..
> No solutions.
> - Trying a 2 word solution..
> No solutions.
> - Trying a 3 word solution..
> No solutions.
> - Trying a 4 word solution..
> No solutions.
> - Trying a 5 word solution..
> No solutions.
> - Trying a 6 word solution..
> No solutions.
> - Trying a 7 word solution..
> >r over over r@ rot rot r>
> ---8<---

: XINVERT5 PARAMS| a b c d e | e d c b a ;
: test 1 2 3 4 5 xinvert5 - - - * . ;

FORTH> see test
Flags: ANSI
$01348540 : test
$0134854A push #10 b#
$0134854C jmp .+10 ( $0124A102 ) offset NEAR
$01348551 ;
FORTH> test 10 ok

FORTH> : 3dup PARAMS| a b c | a b c a b c ;
Redefining `3dup` ok
FORTH> : test 1 2 3 3dup + - + - + . ;
Redefining `test` ok
FORTH> see test
Flags: ANSI
$013485C0 : test
$013485CA push 4 b#
$013485CC jmp .+10 ( $0124A102 ) offset NEAR
$013485D1 ;
FORTH> test 4 ok

-marcel