
japhy
Enthusiast
Jul 24, 2000, 7:44 AM
Post #3 of 8
(20490 views)
|
Re: A little puzzle while waiting for the next quiz...
[In reply to]
|
Can't Post
|
|
I don't like my current solution, since it requires a temporary array. I'll get around it somehow. <BLOCKQUOTE><font size="1" face="Arial,Helvetica,sans serif">code:</font><HR> #!/usr/bin/perl @a = (1); for (1..10) { my @b; print "@a\n"; while ($e = shift @a) { my $count = 1; $count++, shift @a while $a[0] == $e; push @b, ($count,$e); } @a = @b; } </pre><HR></BLOCKQUOTE> As for getting the digit 4 to appear, that is impossible. Proof Except for the first line, each line is of the form "C N C N C N", where C denotes the count, and N denotes the number of that count. You can extrapolate the entire pattern forwards and backwards from any given line: "3 1 2 2 1 1" was preceeded by "1 1 1 2 2 1" and is followed by "1 3 1 1 2 2 2 1". Before a line can contain 4 as a number, it must contain 4 as a count. This requires a line that contains one of these two patterns: "C X X X X N", or "N X X X X C", where X is the same number each time. First Case: C X X X X N C is the count for the first X, and then X acts as both its own count and the number, and then the last X is the count of N. However, "C X X X" can not occur, since C X's and X X's should be replaced by (C+X) X's. Therefore, the pattern "C X X X X N" can not occur. Second Case: N X X X X C Both X X pairs are a count-number pair. This is impossible since X X's and X X's should be (X+X) X's. Therefore, the pattern "N X X X X C" can not occur. The number 4 will never be used in this pattern. QED Extrapolation: since 4 consecutive repeated numbers can never occur, this pattern can never contain more than 4 consecutive repeated numbers, therefore, this pattern only contains the numbers 1, 2, and 3. (From "American Beauty", said by Kevin Spacey I rule! ------------------ Jeff "japhy" Pinyan -- accomplished author, consultant, hacker, and teacher
|