Perl Guru Forums: Fun With Perl: Perl Quizzes - Learn Perl the Fun Way: A little puzzle while waiting for the next quiz...

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	LOG IN

Home: Fun With Perl: Perl Quizzes - Learn Perl the Fun Way:
A little puzzle while waiting for the next quiz...

TheGame+
Deleted

Jul 21, 2000, 2:02 AM

Post #1 of 8 (21935 views)

A little puzzle while waiting for the next quiz...	Can't Post

[if this isn't appropriate, just delete]
Suppose you have the following sequence (*) :
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
...
(*) if you can't figure out how it's built, see below...

What would be the best way to build this series automatically in Perl ? And how long would it take before the number '4' appears in one of the series ?

Have fun...

(*) ...4 enil no teg uoy tahw s'taht oS .1 eno dna 2 eno evah uoy enil driht eht no
,elpmaxe roF .enil txen eht teg ot enil hcae no srebmun eht gnitaremune yrT

Cameron
Deleted

Jul 22, 2000, 7:47 AM

Post #2 of 8 (21935 views)

Re: A little puzzle while waiting for the next quiz... [In reply to]	Can't Post

#!perl-w
print "1\n";
P(1);
sub P{
my $new='';
my $line=shift;
while($line){
my ($digit)=$line=~/(\d)/;
my($seq)=$line=~/($digit+)/;
$length=length $seq;
$line=~s/($digit+)//;
print "$length$digit";
$new=$new.$length.$digit;

}
print "\n";
P($new);
}

japhy
Enthusiast

Jul 24, 2000, 7:44 AM

Post #3 of 8 (21935 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>code:<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 Smile

I rule!

------------------
Jeff "japhy" Pinyan -- accomplished author, consultant, hacker, and teacher

japhy
Enthusiast

Jul 24, 2000, 7:59 AM

Post #4 of 8 (21935 views)

Re: A little puzzle while waiting for the next quiz... [In reply to]	Can't Post

I did what I said I'd do. I got rid of the temporary array by appending to @a, and keeping track of how much of @a is the original @a.

<BLOCKQUOTE>code:<HR>

#!/usr/bin/perl

@a = (1);

for (1..6) {
print "@a\n";
my $s = @a;
my $rem;
while ($e = shift @a) {
$rem++;
my $count = 1;
$rem++, $count++, shift @a while $a[0] == $e and $rem < $s;
push @a, ($count,$e);
last if $rem == $s;
}
}
</pre><HR></BLOCKQUOTE>

I'm going to try and come up with some crazy map() scheme, but I don't think it's possible. I'll try my hardest, though.

------------------
Jeff "japhy" Pinyan -- accomplished author, consultant, hacker, and teacher

japhy
Enthusiast

Jul 24, 2000, 8:13 AM

Post #5 of 8 (21935 views)

Re: A little puzzle while waiting for the next quiz... [In reply to]	Can't Post

How silly of me. It's not a difficult task, if I decide to infringe on the regex idea given by Cameron:

<BLOCKQUOTE>code:<HR>

#!/usr/bin/perl

@a = (1);

for (1..10) {
print "@a\n";
my $i;
@a = map ++$i % 2 ? length : $_, join("",@a) =~ /((\d)\2*)/g;
}
</pre><HR></BLOCKQUOTE>

I think this is actually the fastest of them. I'll benchmark though.

------------------
Jeff "japhy" Pinyan -- accomplished author, consultant, hacker, and teacher

TheGame+
Deleted

Jul 24, 2000, 9:00 AM

Post #6 of 8 (21935 views)

Re: A little puzzle while waiting for the next quiz... [In reply to]	Can't Post

Indeed japhy - that's more the kind of solution I was hoping for Smile

I know there are many ways to do things in Perl, but I was wondering where you were going with all the shifting and pushing - it seemed a lot less "Perl-ish" than the regex Cameron used. Of course, I hadn't thought of using that conditional mapping...

Anyway, since this is supposed to be a learning experience for everyone, I'd like to point out one little problem with the solution Cameron gave : it uses recursive calls to P($new), and that's probably not recommended here.

japhy
Enthusiast

Jul 24, 2000, 9:02 AM

Post #7 of 8 (21935 views)

Re: A little puzzle while waiting for the next quiz... [In reply to]	Can't Post

My second solution was faster then the others (and yes, I did change the 1..6 to a 1..10). I optimized Cameron's to be a { ...; redo } block instead of a function call, since recursion can slow you down.

The results of the pattern(10) benchmark are:

Benchmark: timing 500 iterations of Cameron, japhy_map, japhy_notmp, japhy_orig.
..
Cameron: 14 wallclock secs (13.33 usr + 0.08 sys = 13.41 CPU)
japhy_map: 4 wallclock secs ( 3.76 usr + 0.00 sys = 3.76 CPU)
japhy_notmp: 3 wallclock secs ( 2.87 usr + 0.00 sys = 2.87 CPU)
japhy_orig: 3 wallclock secs ( 3.00 usr + 0.00 sys = 3.00 CPU)

Then I ran 10 iterations for pattern(35) to see which method was better for many iterations of the pattern itself. I excluded Cameron's code because it was too slow.

Benchmark: timing 10 iterations of japhy_map, japhy_notmp, japhy_orig...
japhy_map: 59 wallclock secs (57.14 usr + 0.21 sys = 57.35 CPU)
japhy_notmp: 59 wallclock secs (51.52 usr + 0.03 sys = 51.55 CPU)
japhy_orig: 53 wallclock secs (51.81 usr + 0.04 sys = 51.85 CPU)

So the no-temporary-array method seems to be the fastest approach I could come up with.

------------------
Jeff "japhy" Pinyan -- accomplished author, consultant, hacker, and teacher

Cameron
Deleted

Jul 24, 2000, 11:03 AM

Post #8 of 8 (21935 views)

Re: A little puzzle while waiting for the next quiz... [In reply to]	Can't Post

#!perl-w
@a=1;print"@a\n";
for(1..10){
print map{s/((\d)\2*)/length($1).$2/eg;"$_\n"}@a;
}

another slow way.

Search for (options)

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives