The MU puzzle

Discussion in 'Perl Misc' started by oversby@hotmail.com, Apr 13, 2006.

  1. Guest

    I was working on trying to solve the MU puzzle from the
    Godel Escher Bach book
    http://en.wikipedia.org/wiki/Gödel,_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
     
    , Apr 13, 2006
    #1
    1. Advertising

  2. Guest

    wrote:
    > I was working on trying to solve the MU puzzle from the
    > Godel Escher Bach book
    > http://en.wikipedia.org/wiki/Gödel,_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
     
    , Apr 13, 2006
    #2
    1. Advertising

  3. thundergnat Guest

    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 $_;
    }
    }
    }
     
    thundergnat, Apr 13, 2006
    #3
  4. Guest

    > 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
     
    , Apr 14, 2006
    #4
  5. Guest

    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
     
    , Apr 14, 2006
    #5
  6. wrote:

    > I was working on trying to solve the MU puzzle from the
    > Godel Escher Bach book
    > http://en.wikipedia.org/wiki/Gödel,_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 |
    | | | | Diskussion derzeit in at.usenet.gruppen
    __/ | http://www.hjp.at/ |
     
    Peter J. Holzer, Apr 14, 2006
    #6
  7. Guest

    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
     
    , Apr 14, 2006
    #7
  8. Guest

    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
     
    , Apr 14, 2006
    #8
  9. Guest

    wrote:
    > 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.
     
    , Apr 14, 2006
    #9
  10. Guest

    Peter J. Holzer wrote:
    > wrote:
    >
    > > I was working on trying to solve the MU puzzle from the
    > > Godel Escher Bach book
    > > http://en.wikipedia.org/wiki/Gödel,_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.
     
    , Apr 14, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Earl Teigrob
    Replies:
    3
    Views:
    6,652
    Nedu N
    Aug 6, 2003
  2. dwa

    Design Puzzle!

    dwa, Jun 10, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    370
    Cowboy \(Gregory A. Beamer\) [MVP]
    Jun 10, 2004
  3. Shankara Narayanan

    Booking puzzle....

    Shankara Narayanan, Jun 17, 2004, in forum: ASP .Net
    Replies:
    20
    Views:
    933
    bredal Jensen
    Jun 30, 2004
  4. VB Programmer
    Replies:
    2
    Views:
    431
    Alan Lambert
    Nov 4, 2004
  5. G. Stewart

    regex puzzle!

    G. Stewart, Nov 23, 2004, in forum: ASP .Net
    Replies:
    8
    Views:
    518
    G. Stewart
    Nov 25, 2004
Loading...

Share This Page