No such thing as a small change PerlMonks

### (OT) Hofstadter Metapuzzle

by MeowChow (Vicar)
 on May 22, 2002 at 22:13 UTC 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

MeowChow
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?
MeowChow
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)
enjoy,
jynx
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...

one
one
one
...
one

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.

MetaFoo

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 :)
MeowChow
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?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://168608]
Approved by VSarkiss
help
Chatterbox?
 [erix]: ganesh in musht? [LanX]: as a monotheist he would fight other problems LanX succesfully trolled the CB into religion and leaves now! :) [erix]: looking for his navel [zentara]: Unicorns are not conceived, they are created. Unicorns don't want another life. :-) [erix]: you go check your data LanX :P [Your Mother]: marto++ (me as well) [zentara]: choroba I stand corrected, I guess Jesus killed a tree once too. [erix]: the neighbours (a nat.hist. museum) have a narwhal skull with *2* tusks

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (15)
As of 2017-03-30 16:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should Pluto Get Its Planethood Back?

Results (361 votes). Check out past polls.