Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

(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 taking refuge in the Monastery: (5)
As of 2018-03-17 21:05 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (226 votes). Check out past polls.