|
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? | [reply]
[d/l] |
|
|
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 | [reply] |
|
|
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.
| [reply] |
|
|
|
|
#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 | [reply]
[d/l]
[select] |
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
| [reply] |
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.
| [reply]
[d/l] |
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'
| [reply] |
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";
}
| [reply]
[d/l] |
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.) | [reply] |
Re: (OT) Metapuzzle
by Aristotle (Chancellor) on May 23, 2002 at 04:55 UTC
|
| [reply]
[d/l] |
|
|
Sorry, we're counting digits. Otherwise the puzzle wouldn't be one :)
MeowChow
s aamecha.s a..a\u$&owag.print | [reply] |
|
|
Drop one "number of X is" and it still would be. :-)
____________
Makeshifts last the longest.
| [reply] |
|
|
|
|
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.
| [reply] |