Velocity Reviews > Perl > The MU puzzle

# The MU puzzle

oversby@hotmail.com
Guest
Posts: n/a

 04-13-2006
I was working on trying to solve the MU puzzle from the
Godel Escher Bach book
http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
(yes, I know now it is impossible) when I saw an interesting
sub-problem - which integers between 0 and 1000 can be
derived by sequences of "doubling" and "subtracting three"
operations? I first tried to solve this with scheme and then
with perl but I'm having some problems with the perl program.

A quick outline of the algorithm:

Begin with a list of lists containing [[1]]

Foreach list
take the head of the list
double it
subtract three from it.
if either result is within the range 0 and 1000 and not already
in the hash it is valid
foreach valid result
concatenate the result to the list and add it to a new list
of lists

Continue creating new in-progress lists until an iteration does not add
any more
keys to the hash

We create lists like this for two purposes:

#1 To reduce the amount of work needed to do - at any one time
there are many more keys in the hash then there are lists in the
list of lists.
#2 To keep a record of the steps necessary to produce a given integer.

Here is the perl code:

use strict;

my %HASH = (1 => 1);

sub display
{
my \$l = \$_[0];
my \$first = 1;
print '(';
foreach my \$elem (@\$l) {
unless (\$first) { print ' '; }
\$first = 0;

if (ref \$elem eq 'ARRAY') {
display(\$elem);
} else {
print \$elem;
}
}
print ')';
}

sub valid
{
my \$v = \$_[0];
return (\$v >= 0) && (\$v <= 1000) && (! exists(\$HASH{\$v}));
}

sub new_list
{
my \$l = \$_[0];

my @retVal = ();
foreach my \$subList (@\$l) {
my \$head = \$subList->[0];
foreach my \$v ((\$head * 2), (\$head - 3)) {
if (valid(\$v)) {
\$HASH{\$v} = 1;
push @retVal, [(\$v, @\$subList)];
}
}
}
return \@retVal;
}

my \$l = [[1]];
my \$solutions = 1;

while (1) {
\$l = new_list(\$l);
display(\$l); print "\n";
my \$keys = scalar keys %HASH;
if (\$keys == \$solutions) { last; }
print "\$solutions, \$keys\n";
\$solutions = \$keys;
}

# display(\$l);

foreach (@\$l) {
display(\$_);
print "\n";
}

This seems to progress correctly for a number of iterations, but
towards the end of the processing it loses
all the results. Any ideas why?

This may look like uni coursework or similar, but I promise it isn't
(at least for me!). Here is my scheme program
that solves the problem:

(require (lib "28.ss" "srfi"))
(require (lib "69.ss" "srfi"))

(define (double x) (* x 2))
(define (sub3 x) (- x 3))

(define (valid? x hash) (and (>= x 0)
(<= x 1000)
(not (hash-table-exists? hash x))))

(define (make-soln s e hash)
(hash-table-set! hash s #t)
(cons s e))

(define (add-solutions seq hash)
(if (null? seq) '()
(let* ((e (car seq))
(f (car e))
(s1 (double f))
(s2 (sub3 f)))
(cond ((and (valid? s1 hash) (valid? s2 hash))
(append (list (make-soln s1 e hash) (make-soln s2 e
hash))
(add-solutions (cdr seq) hash)))
((valid? s1 hash) (append (list (make-soln s1 e hash))
(add-solutions (cdr seq) hash)))
((valid? s2 hash) (append (list (make-soln s2 e hash))
(add-solutions (cdr seq) hash)))
(else (append (list e) (add-solutions (cdr seq)
hash)))))))

(define (solve solutions solutions-count hash iterations)
(let* ((new-solutions (add-solutions solutions hash))
(new-count (hash-table-size hash)))
(if (= solutions-count new-count)
(begin
(display (format "Iterations == ~a~%" iterations))
(display new-solutions)
(newline)
new-solutions)
(solve new-solutions new-count hash (+ iterations 1)))))

(let ((hash (make-hash-table)))
(hash-table-set! hash 1 #t)
((solve '((1)) 1 hash 1)
(display (format " Solutions == ~a~%" (hash-table-size hash)))
(hash-table-keys hash))

IanO

xhoster@gmail.com
Guest
Posts: n/a

 04-13-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> I was working on trying to solve the MU puzzle from the
> Godel Escher Bach book
> http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
> (yes, I know now it is impossible) when I saw an interesting
> sub-problem - which integers between 0 and 1000 can be
> derived by sequences of "doubling" and "subtracting three"
> operations? I first tried to solve this with scheme and then
> with perl but I'm having some problems with the perl program.
>
> A quick outline of the algorithm:
>
> Begin with a list of lists containing [[1]]

Why not just a hash containing 1, or even an empty hash since 1 is
special cased?

>
> Foreach list
> take the head of the list
> double it
> subtract three from it.
> if either result is within the range 0 and 1000 and not already
> in the hash it is valid

You are not allowed to go temporarily outside 0 to 1000 in order to find
a number which *is* in that range?

> foreach valid result
> concatenate the result to the list and add it to a new list
> of lists

What is the list of lists for?

>
> Continue creating new in-progress lists until an iteration does not add
> any more
> keys to the hash
>
> We create lists like this for two purposes:
>
> #1 To reduce the amount of work needed to do - at any one time
> there are many more keys in the hash then there are lists in the
> list of lists.
> #2 To keep a record of the steps necessary to produce a given integer.

It seems to me you only need to two hashes (or a hash and a list).
One hash holds all the number you can reach as keys, and what number they
are reachd from as values. The other hash/array holds all things that
can be reached but which you haven't yet decided where they lead.

....
> sub new_list
> {
> my \$l = \$_[0];
>
> my @retVal = ();
> foreach my \$subList (@\$l) {
> my \$head = \$subList->[0];
> foreach my \$v ((\$head * 2), (\$head - 3)) {
> if (valid(\$v)) {
> \$HASH{\$v} = 1;
> push @retVal, [(\$v, @\$subList)];
> }
> }
> }
> return \@retVal;
> }
>
>
> This seems to progress correctly for a number of iterations, but
> towards the end of the processing it loses
> all the results. Any ideas why?

Because you throw them away. Once a list has head node which >1000, <0 or
equal to something else already discovered, it is not kept. Eventually,
every list does one of these things.

Maybe you should start with my @retval=@\$l; rather than my @retval=() ?

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service \$9.95/Month 30GB

thundergnat
Guest
Posts: n/a

 04-13-2006
(E-Mail Removed) wrote:

>
> A quick outline of the algorithm:
>
> Begin with a list of lists containing [[1]]
>
> Foreach list
> take the head of the list
> double it
> subtract three from it.
> if either result is within the range 0 and 1000 and not already
> in the hash it is valid
> foreach valid result
> concatenate the result to the list and add it to a new list
> of lists
>
> Continue creating new in-progress lists until an iteration does not add
> any more
> keys to the hash
>
> We create lists like this for two purposes:
>
> #1 To reduce the amount of work needed to do - at any one time
> there are many more keys in the hash then there are lists in the
> list of lists.
> #2 To keep a record of the steps necessary to produce a given integer.
>
> Here is the perl code:
>

[snip code]

Seems to me you keep reassigning \$l to a new list of lists each iteration
rather than pushing the new LOL onto the array.

Your script seem awfully complex anyway. Would something like this work?
(Sorted by highest value in array.)

use warnings;
use strict;

my %HASH = (1, 1);
my \$list = [[1]];

get_list(\$list);

print '(',(join ' ', @{\$_}),")\n" for sort {\$a->[0] <=> \$b->[0]} @\$list;

print scalar keys %HASH, " solutions.\n";

sub valid
{
\$_[0] >= 0 && \$_[0] <= 1000 && !exists \$HASH{\$_[0]};
}

sub get_list
{
for my \$subList (@{\$_[0]}) {
my \$head = \$subList->[0];
for (\$head * 2, \$head - 3) {
push @{\$_[0]}, [\$_, @\$subList] and \$HASH{\$_} = 1 if valid \$_;
}
}
}

oversby@hotmail.com
Guest
Posts: n/a

 04-14-2006
> It seems to me you only need to two hashes (or a hash and a list).
> One hash holds all the number you can reach as keys, and what number they
> are reachd from as values. The other hash/array holds all things that
> can be reached but which you haven't yet decided where they lead.

Wouldn't I then lose the information as to how to reach a particular
integer.

> Because you throw them away. Once a list has head node which >1000, <0 or
> equal to something else already discovered, it is not kept. Eventually,
> every list does one of these things.

Oh yes, well spotted. I'll fix that.

> Maybe you should start with my @retval=@\$l; rather than my @retval=() ?
>
> Xho

But then surely I'll get repeated lists, e.g. (8 4 2 1), (5 8 4 2 1)
and (16 8 4 2 1) rather than just the latter two lists?

IanO

oversby@hotmail.com
Guest
Posts: n/a

 04-14-2006
thundergnat wrote:
> Your script seem awfully complex anyway. Would something like this work?
> (Sorted by highest value in array.)

[snip code]

Doesn't this only do one iteration? It does simplify the valid,
get_list and display routines signifcantly though, thanks.

IanO

Peter J. Holzer
Guest
Posts: n/a

 04-14-2006
(E-Mail Removed) wrote:

> I was working on trying to solve the MU puzzle from the
> Godel Escher Bach book
> http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
> (yes, I know now it is impossible) when I saw an interesting
> sub-problem - which integers between 0 and 1000 can be
> derived by sequences of "doubling" and "subtracting three"
> operations?

All numbers which are not evenly divisable by three.

Proof: By doubling, you will eventually arrive at 1024, which is
341*3+1. By repeatedly subtracting 3, you will reach all numbers of the
form 3n+1 below 1024 and hence below 1000.
One of these numbers is 499, if you double that, you will get 998, which
is the largest number of the form 3n+2 below 1000. By repeatedly
subtracting 3, you get all the other numbers of this form.
There is no way to get at numbers of the form 3n+0, as subtracting 3
will preserve the remainder and doubling will just flip between 1 and 2.

(You will get the same result if intermediate values outside [0..1000]
aren't allowed - you just have to prove that you can reach 1000 first).

That said, here is a recursive solution to your problem:

#!/usr/bin/perl
use warnings;
use strict;
no warnings 'recursion';

my @a;

sub mu {
my (\$n, \$l) = @_;
return if (\$a[\$n]);
return if (\$n < 0 || \$n > 1000);
print STDERR "\$n at level \$l\n";
\$a[\$n] = 1;
mu(\$n-3, \$l+1);
mu(\$n*2, \$l+1);
}

mu(1, 0);

for my \$n (0 .. \$#a) {
print "\$n\n" if (\$a[\$n]);
}

(Try plotting the first and last column of STDERR)

hp

--
_ | Peter J. Holzer | LĂ¶schung von at.usenet.schmankerl?
|_|_) | Sysadmin WSR/LUGA |
| | | (E-Mail Removed) | Diskussion derzeit in at.usenet.gruppen
__/ | http://www.hjp.at/ |

oversby@hotmail.com
Guest
Posts: n/a

 04-14-2006
(E-Mail Removed) wrote:
> thundergnat wrote:
> > Your script seem awfully complex anyway. Would something like this work?
> > (Sorted by highest value in array.)

>
> [snip code]
>
> Doesn't this only do one iteration? It does simplify the valid,
> get_list and display routines signifcantly though, thanks.
>
> IanO

Oops, sorry... it does do all the iterations doesn't it (he says after
actually running it!) And if I understand it correctly, it modifies
the list we are iterating through while we are iterating through it.
I don't think it quite solves the same problem though as mine
would not retain a list (4 2 1) when it already had (8 4 2 1). Still,
it is very neat and elegant, thanks.

IanO

xhoster@gmail.com
Guest
Posts: n/a

 04-14-2006
(E-Mail Removed) wrote:
> > It seems to me you only need to two hashes (or a hash and a list).
> > One hash holds all the number you can reach as keys, and what number
> > they are reachd from as values. The other hash/array holds all things
> > that can be reached but which you haven't yet decided where they lead.

>
> Wouldn't I then lose the information as to how to reach a particular
> integer.

Nope, you would just need to calculate it on demand.

16 => 8,
5 => 8,
8 => 4,
4 => 2,
2 => 1,

At any given starting point, you just keep following until you the link
until you reach 1.

>
> > Because you throw them away. Once a list has head node which >1000, <0
> > or equal to something else already discovered, it is not kept.
> > Eventually, every list does one of these things.

>
> Oh yes, well spotted. I'll fix that.
>
> > Maybe you should start with my @retval=@\$l; rather than my @retval=() ?
> >
> > Xho

>
> But then surely I'll get repeated lists, e.g. (8 4 2 1), (5 8 4 2 1)
> and (16 8 4 2 1) rather than just the latter two lists?

I don't understand the problem. Those aren't repeated, they are
three different lists. It is OK if they overlap, as long as one is not a
subset of anyother?

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service \$9.95/Month 30GB

oversby@hotmail.com
Guest
Posts: n/a

 04-14-2006
(E-Mail Removed) wrote:
> (E-Mail Removed) wrote:
> > But then surely I'll get repeated lists, e.g. (8 4 2 1), (5 8 4 2 1)
> > and (16 8 4 2 1) rather than just the latter two lists?

>
> I don't understand the problem. Those aren't repeated, they are
> three different lists. It is OK if they overlap, as long as one is not a
> subset of anyother?

Well, it isn't really a problem, that is true - your solution still
solves the problem I specified. To my mind, the information
is repeated though as (5 8 4 2 1) and (16 8 4 2 1) are all the
possible paths resulting from a path of (8 4 2 1) and keeping
that path around is a little redundant.

oversby@hotmail.com
Guest
Posts: n/a

 04-14-2006
Peter J. Holzer wrote:
> (E-Mail Removed) wrote:
>
> > I was working on trying to solve the MU puzzle from the
> > Godel Escher Bach book
> > http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
> > (yes, I know now it is impossible) when I saw an interesting
> > sub-problem - which integers between 0 and 1000 can be
> > derived by sequences of "doubling" and "subtracting three"
> > operations?

>
> All numbers which are not evenly divisable by three.
>
> Proof: By doubling, you will eventually arrive at 1024, which is
> 341*3+1. By repeatedly subtracting 3, you will reach all numbers of the
> form 3n+1 below 1024 and hence below 1000.
> One of these numbers is 499, if you double that, you will get 998, which
> is the largest number of the form 3n+2 below 1000. By repeatedly
> subtracting 3, you get all the other numbers of this form.
> There is no way to get at numbers of the form 3n+0, as subtracting 3
> will preserve the remainder and doubling will just flip between 1 and 2.

Ah yes, this is a nice proof. I was trying to think how to
derive it before I gave up thinking my maths isn't sufficiently
good. Thanks very much!

I like the recursive perl too but I see why I didn't come up
with that - I'm not cut out to think recursively

IanO.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post S.Rodgers Firefox 9 12-14-2005 11:15 AM =?Utf-8?B?Qm9ya28=?= Wireless Networking 3 01-25-2005 06:49 AM Brad Snow Firefox 6 09-03-2004 04:54 AM sk A+ Certification 1 07-17-2004 05:19 PM Earl Teigrob ASP .Net 3 08-06-2003 09:41 PM

Advertisments