Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

(OT) Hofstadter Metapuzzle

by MeowChow (Vicar)
on May 22, 2002 at 22:13 UTC ( #168608=perlmeditation: print w/replies, xml ) Need Help??

I believe this first appeared in Hofstadter's Metamagical Themas. Fill in the blanks below with numbers that would make the following sentence true:

The number of 0s in this sentence is _, of 1s is _, of 2s is _, of 3s is _, of 4s is _, of 5s is _, of 6s is _, of 7s is _, of 8s is _, and of 9s is _.

There are two solutions. Enjoy :)

Update: As dws points out, I meant numeric numbers, as in non-zero-padded positive integers, or /^[1-9]\d*$/ for the regexpically inclined. I'll leave it to dws to enumerate the remainder of the class of solutions for which words are permissable in the answer. :p

               s aamecha.s a..a\u$&owag.print

Replies are listed 'Best First'.
Re: Hofstadter Metapuzzle
by tadman (Prior) on May 22, 2002 at 23:20 UTC
    Thankfully, the statement doesn't "overflow" so this program works:
    #!/usr/bin/perl -w use strict; my $statement = "The number of 0s in this sentence is _, of 1s is _, o +f 2s is _, of 3s is _, of 4s is _, of 5s is _, of 6s is _, of 7s is _ +, of 8s is _, and of 9s is _."; my @index; my $resume = 0; while (($resume = index($statement, "_", $resume)) && $resume > 0) { push (@index, $resume++); } my $changed; do { $changed = 0; for my $n (0 .. $#index) { my $count = (grep { /$n/ } split (//, $statement)); my $old_count = substr($statement, $index[$n], 1); if ($count ne $old_count) { substr($statement, $index[$n], 1) = $count; $changed++; } } } while ($changed); print $statement,"\n";
    The great mystery is finally revealed. Golf anyone?
      Nice work. Iterative processes are hit-or-miss with these sorts of problems, though. They depend on your initial state, can degenerate into cycles, and are not necessarily capable of producing all possible solutions. I wonder if this program can be tweaked to produce the second solution?
                     s aamecha.s a..a\u$&owag.print
        Some puzzles like this don't settle into a steady state, leaving the logical equivalent of a "flip-flop" circuit, the classic paradoxical "This statement is false."-type problem, or two self-defeating, self-reinforcing arrangements like in the "Life" game.

        I think if you seed the initial statement differently, it might settle on a different possibility, though of course, this particular implementation uses the underscores for placement, so that will have to change.

      Not counting the data section,

      i get a score of 128. i'm not counting the data section since anyone golfing will need the input, so it shouldn't be counted. That's my theory at least. Anyway, here's my attempt:

      #23456789_123456789_123456789_123456789_123456789_123456789_123456789_ $_=<DATA>;push@_,@+while/_/g;{for$a(0..$#_){substr($_,$_[$a]-1,1 )=$;,$|++if($;=@{[/$a/g]})!=substr$_,$_[$a]-1,1}$|--&&redo}print __DATA__ The number of 0s in this sentence is _, of 1s is _, of 2s is _, of 3s +is _, of 4 s is _, of 5s is _, of 6s is _, of 7s is _, of 8s is _, and of 9s is _ +.
      On the other hand, here's a much shorter 77 byte solution that's less interesting. It uses the same data section as above. Please note in both cases there should be no "\n"s in the data.
      sub{$a=<DATA>;$a=~s,($_.*?)_,$1.pop,efor-1..9;print$a}->(1,1,2,1,1,1,2 +,3,7,1)
Re: (OT) Metapuzzle
by dws (Chancellor) on May 22, 2002 at 22:25 UTC
    Since you didn't specify that the numbers had to be numeric...


Re: (OT) Hofstadter Metapuzzle
by hagus (Monk) on May 23, 2002 at 10:30 UTC
    Another solution for the hell of it. No idea how you would coax the second solution out of it. No matter how I tweak things (shotgun debugging :) it converges to the same answer. Hmm.

    #!/usr/bin/perl use strict; use warnings; my @arr = (0..9); my %hash; @hash{@arr} = (0) x @arr; sub scanit { my $number = shift; my $cnt = 0; for (0..9) { foreach my $c (split //, $hash{$_}) { $cnt++ if ($number == $c); } } $cnt+1; } my $solcount=0; while (1) { my $cond = 0; # update the counts for (my $i=9; $i>=0; $i--) { my $cnt = scanit($i); $hash{$i} = $cnt; } # check whether our solution is valid. for (0..9) { my $cnt = scanit($_); $cond = 1 if ($hash{$_} != $cnt); } # print it if it is. if ($cond == 0) { my @print; for (1..9) { push @print, "of $_ "."s is $hash{$_}"; } print "The number of 0s in this sentence is $hash{0}, " . join(", ", @print) . "\n"; die; } else { $cond = 1; } }
    Ash OS durbatulk, ash OS gimbatul,
    Ash OS thrakatulk, agh burzum-ishi krimpatul!
    Uzg-Microsoft-ishi amal fauthut burguuli.
Re: (OT) Hofstadter Metapuzzle
by grinder (Bishop) on May 23, 2002 at 08:58 UTC
    The number of 0s in this sentence is _, of 1s is _, of 2s is _, of 3s is _, of 4s is _, of 5s is _, of 6s is _, of 7s is _, of 8s is _, and of 9s is _.

    That's not how I recall reading the puzzle in G.E.B, (but then again it's over a decade since I last opened the book). As I recall the question, it was:

    There are _ a's, _ b's and _ c's and _ d's [repeat for e..y] and _ z's in this sentence.

    And of course the numbers are written in English 'one x, one y and one z'.

    This is a much harder problem to solve. Changing one number value has a rippling effect on more than one other number value. IIRC Hofstadter tried to solve it in Lisp, gave up, and a friend built a hardware implementation to solve the question.

    Bonus points for solving the general question: i.e. the phrase may contain any amount of fluff ("In this sentence, if you look carefully and count all the letters you will see that it contains _ a's...)

    A short while later: come to think of it, the general problem is to solve this in any language. All you need is a module that spits out a string representation in your desired language (1 => 'ein', 2 => 'zwei', 3 => 'drei'). There are modules on CPAN that do that part for you Lingua::EN::Number, Lingua::FR::Number and Lingua::JA::Number (hmm, that last one should really be JP, but never mind). Then plug that into your algorithm, and solve the problem in any language.

    Cette phrase contient _ a, _ b, ... et _ z.

    print@_{sort keys %_},$/if%_=split//,'= & *a?b:e\f/h^h!j+n,o@o;r$s-t%t#u'
Re: (OT) Hofstadter Metapuzzle
by robin (Chaplain) on May 23, 2002 at 16:49 UTC
    And apparently, if you can write a script to solve puzzles of this sort, you can sell the output for $15 a time! (There's something indecent about that.)
Re: (OT) Hofstadter Metapuzzle
by YuckFoo (Abbot) on May 24, 2002 at 16:04 UTC
    The program I have is really hit and miss, it can run all day without finding a solution, or it can find one in 5 minutes. This solution required only 75k iterations (fast).

    Having run the program all day without solutions, I'm wondering if it's been proven that all sentence beginnings have a solution. <p< I'll clean up the code a bit and post it later.


    Maybe the question should be rephrased like this:

    #!/usr/bin/perl use strict; my $str = "Do any Perlmonks know of a sentence made with five a's, one b, two c's, four d's, thirty-three e's, six f's, two g's, nine h's, ten i's, one j, three k's, two l's, three m's, twenty-one n's, sixteen o's, two p's, one q, ten r's, twenty-eight s's, twenty-five t's, three u's, three v's, ten w's, four x's, six y's, and one z?"; for my $ch ('a'..'z') { my $num = (() = $str =~ m{$ch}ig); print "$ch $num\n"; }
Re: (OT) Metapuzzle
by Aristotle (Chancellor) on May 23, 2002 at 04:55 UTC
    If we are counting numbers and not digits: s/_/1/g; s/(1s is)  1/${1} 10/;

    Makeshifts last the longest.

      Sorry, we're counting digits. Otherwise the puzzle wouldn't be one :)
                     s aamecha.s a..a\u$&owag.print
        Drop one "number of X is" and it still would be. :-)

        Makeshifts last the longest.
Second Solution (spoiler)
by hagus (Monk) on May 24, 2002 at 00:13 UTC
    I surfed around and got some hints. It's so very obvious when you see it. In fact I think I've done this puzzle before, now that I see the answer.

    Start at the end and just places 1s in all the positions. When you get to 2, put a '2' there. In position 1 we have '11', and position 0 we have 1.

    Now the obvious question is how we have a program deduct this answer by itself, sort of trying 9!^2 solutions, or whatever :)

    Ash OS durbatulk, ash OS gimbatul,
    Ash OS thrakatulk, agh burzum-ishi krimpatul!
    Uzg-Microsoft-ishi amal fauthut burguuli.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://168608]
Approved by VSarkiss
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (7)
As of 2017-04-28 18:10 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (526 votes). Check out past polls.