note Aristotle <p>And here's the proof (sorry it's so wide).</p> <readmore> <table border="1" cellspacing="0" cellpadding="3"> <tr><td></td> <td>Rate</td> <td>bgreenlee</td> <td>japhy2</td> <td>japhy</td> <td>ccn2</td> <td>ccn</td> <td>jasper</td> <td>deibyz</td> <td>murugu</td> <td>clive</td> <td>buu</td> <td>jdporter</td> <td>aristotle</td> <td>limbic_region</td> <td>elgon</td> <td>browseruk</td> <td>aristotle2</td> <td>random_walk</td> <td>tune</td></tr> <tr><td>bgreenlee</td> <td>1.59/s</td> <td>--</td> <td>-44%</td> <td>-44%</td> <td>-49%</td> <td>-49%</td> <td>-50%</td> <td>-90%</td> <td>-90%</td> <td>-91%</td> <td>-97%</td> <td>-98%</td> <td>-99%</td> <td>-100%</td> <td>-100%</td> <td>-100%</td> <td>-100%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>japhy2</td> <td>2.82/s</td> <td>77%</td> <td>--</td> <td>-1%</td> <td>-10%</td> <td>-10%</td> <td>-11%</td> <td>-82%</td> <td>-82%</td> <td>-84%</td> <td>-94%</td> <td>-97%</td> <td>-98%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>japhy</td> <td>2.85/s</td> <td>79%</td> <td>1%</td> <td>--</td> <td>-9%</td> <td>-9%</td> <td>-10%</td> <td>-82%</td> <td>-82%</td> <td>-84%</td> <td>-94%</td> <td>-97%</td> <td>-98%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>ccn2</td> <td>3.14/s</td> <td>97%</td> <td>11%</td> <td>10%</td> <td>--</td> <td>0%</td> <td>-1%</td> <td>-80%</td> <td>-80%</td> <td>-82%</td> <td>-94%</td> <td>-96%</td> <td>-98%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>ccn</td> <td>3.14/s</td> <td>97%</td> <td>11%</td> <td>10%</td> <td>0%</td> <td>--</td> <td>-1%</td> <td>-80%</td> <td>-80%</td> <td>-82%</td> <td>-94%</td> <td>-96%</td> <td>-98%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>jasper</td> <td>3.16/s</td> <td>99%</td> <td>12%</td> <td>11%</td> <td>1%</td> <td>1%</td> <td>--</td> <td>-80%</td> <td>-80%</td> <td>-82%</td> <td>-94%</td> <td>-96%</td> <td>-98%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-99%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td><del>deibyz</del></td> <td>15.6/s</td> <td>880%</td> <td>453%</td> <td>448%</td> <td>396%</td> <td>396%</td> <td>393%</td> <td>--</td> <td>-1%</td> <td>-10%</td> <td>-68%</td> <td>-82%</td> <td>-91%</td> <td>-96%</td> <td>-97%</td> <td>-97%</td> <td>-97%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td><del>murugu</del></td> <td>15.8/s</td> <td>891%</td> <td>459%</td> <td>454%</td> <td>402%</td> <td>402%</td> <td>398%</td> <td>1%</td> <td>--</td> <td>-9%</td> <td>-68%</td> <td>-82%</td> <td>-91%</td> <td>-96%</td> <td>-96%</td> <td>-97%</td> <td>-97%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>clive</td> <td>17.3/s</td> <td>984%</td> <td>512%</td> <td>506%</td> <td>449%</td> <td>449%</td> <td>446%</td> <td>11%</td> <td>9%</td> <td>--</td> <td>-65%</td> <td>-81%</td> <td>-90%</td> <td>-95%</td> <td>-96%</td> <td>-96%</td> <td>-97%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>buu</td> <td>49.1/s</td> <td>2981%</td> <td>1639%</td> <td>1623%</td> <td>1460%</td> <td>1460%</td> <td>1450%</td> <td>214%</td> <td>211%</td> <td>184%</td> <td>--</td> <td>-45%</td> <td>-72%</td> <td>-87%</td> <td>-89%</td> <td>-90%</td> <td>-91%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>jdporter</td> <td>89.1/s</td> <td>5493%</td> <td>3057%</td> <td>3027%</td> <td>2732%</td> <td>2732%</td> <td>2714%</td> <td>471%</td> <td>465%</td> <td>416%</td> <td>82%</td> <td>--</td> <td>-50%</td> <td>-76%</td> <td>-80%</td> <td>-81%</td> <td>-83%</td> <td>-100%</td> <td>-100%</td></tr> <tr><td>aristotle</td> <td>178/s</td> <td>11060%</td> <td>6199%</td> <td>6139%</td> <td>5551%</td> <td>5551%</td> <td>5516%</td> <td>1039%</td> <td>1027%</td> <td>929%</td> <td>262%</td> <td>100%</td> <td>--</td> <td>-51%</td> <td>-60%</td> <td>-63%</td> <td>-67%</td> <td>-99%</td> <td>-100%</td></tr> <tr><td><del>limbic_region</del></td> <td>364/s</td> <td>22756%</td> <td>12800%</td> <td>12679%</td> <td>11474%</td> <td>11474%</td> <td>11401%</td> <td>2232%</td> <td>2207%</td> <td>2008%</td> <td>642%</td> <td>309%</td> <td>105%</td> <td>--</td> <td>-19%</td> <td>-24%</td> <td>-32%</td> <td>-99%</td> <td>-99%</td></tr> <tr><td><del>elgon</del></td> <td>448/s</td> <td>28063%</td> <td>15795%</td> <td>15646%</td> <td>14161%</td> <td>14161%</td> <td>14071%</td> <td>2774%</td> <td>2743%</td> <td>2498%</td> <td>814%</td> <td>404%</td> <td>152%</td> <td>23%</td> <td>--</td> <td>-7%</td> <td>-16%</td> <td>-99%</td> <td>-99%</td></tr> <tr><td><del>browseruk</del></td> <td>481/s</td> <td>30111%</td> <td>16951%</td> <td>16791%</td> <td>15198%</td> <td>15198%</td> <td>15102%</td> <td>2983%</td> <td>2950%</td> <td>2687%</td> <td>881%</td> <td>440%</td> <td>171%</td> <td>32%</td> <td>7%</td> <td>--</td> <td>-10%</td> <td>-99%</td> <td>-99%</td></tr> <tr><td>aristotle2</td> <td>532/s</td> <td>33288%</td> <td>18744%</td> <td>18567%</td> <td>16807%</td> <td>16807%</td> <td>16701%</td> <td>3307%</td> <td>3271%</td> <td>2980%</td> <td>984%</td> <td>497%</td> <td>199%</td> <td>46%</td> <td>19%</td> <td>11%</td> <td>--</td> <td>-98%</td> <td>-99%</td></tr> <tr><td><del>random_walk</del></td> <td>35318/s</td> <td>2217869%</td> <td>1251726%</td> <td>1239954%</td> <td>1123012%</td> <td>1123012%</td> <td>1115948%</td> <td>226223%</td> <td>223816%</td> <td>204478%</td> <td>71886%</td> <td>39555%</td> <td>19774%</td> <td>9604%</td> <td>7775%</td> <td>7242%</td> <td>6543%</td> <td>--</td> <td>-31%</td></tr> <tr><td><del>tune</del></td> <td>51210/s</td> <td>3215868%</td> <td>1814999%</td> <td>1797929%</td> <td>1628368%</td> <td>1628368%</td> <td>1618126%</td> <td>328060%</td> <td>324569%</td> <td>296530%</td> <td>104276%</td> <td>57399%</td> <td>28717%</td> <td>13971%</td> <td>11319%</td> <td>10545%</td> <td>9532%</td> <td>45%</td> <td>--</td></tr> </table> </readmore> <p>Note that I had to disqualify some entries for failing the tests.</p> <p>The full benchmark I ran follows. Note that some entries required slight modifications in order to compile with strictures and run without warnings. I paid careful attention to keep the semantics intact, but if I disqualified your entry, please check my copy of your code for potential breakage.</p> <readmore> <code> use strict; use warnings; use Benchmark qw( cmpthese ); use Test::More qw( no_plan ); use CGI qw/ :html /; my %contestant = ( aristotle => sub { my $str = shift; my $rts = reverse $str; my $palindrome = ''; for my $rotate_count ( 0 .. length( $str ) - 1 ) { my $mask = $str ^ $rts; # to distinguish adjacent palindromes substr $mask, $rotate_count, 0, "\1"; while ( $mask =~ /\0{3,}/g ) { my $len = $+[0] - $-[0]; next if $len <= length $palindrome; my $offs = $-[0]; --$offs if $offs > $rotate_count; # compensate for marker $palindrome = substr $str, $offs, $len; } substr $rts, 0, 0, chop $rts; } return $palindrome; }, aristotle2 => sub { my $str = shift; my $rts = reverse $str; my $palindrome = ''; my $minlen = 3; for my $rotate_count ( 0 .. length( $str ) - 1 ) { my $mask = $str ^ $rts; # to distinguish adjacent palindromes substr $mask, $rotate_count, 0, "\1"; while ( $mask =~ /\0{$minlen,}/g ) { my $offs = $-[0]; --$offs if $offs > $rotate_count; # compensate for marker $palindrome = substr $str, $offs, $+[0] - $-[0]; $minlen = 1 + length $palindrome; } substr $rts, 0, 0, chop $rts; } return $palindrome; }, buu => sub { my @p; my $arg = shift; my $p = ''; while ( $arg =~ /((.).?\2)/g ) { my $m = $1; while ( $arg =~ /((.)$m\2)/ ) { $m = $1; } if ( length( $m ) > length( $p ) ) { $p = $m; } } return $p; }, ccn => sub { local $_ = shift; my @n; for ( my $i = 0 ; $i < length ; pos = $i++ ) { $n[ length $& ] = $& if /\G(.+).?(??{reverse $1})/; } return @n ? $n[-1] : ''; }, ccn2 => sub { local $_ = shift; my $s = ''; for ( my $i = 0 ; $i < length ; pos = $i++ ) { $s = $& if /\G(.+).?(??{reverse $1})/ and length( $s ) < length( $& ); } return $s; }, tune => sub { my $l = ''; map { $l = $_ if ( $_ eq reverse $_ ) && ( length $l < length $_ ) } split /\s+/, $_[0]; return $l; }, random_walk => sub { my ( $left, $right, $pal, $i ) = ( "", "", "", 1 ); my $test = join " ", @ARGV; for ( ; $i < ( ( length $test ) / 2 ) + 2 ; $i++ ) { $left .= "(.)"; $right = "(\\$i)" . $right; if ( $test =~ /$left.?$right/ ) { $pal = $&; next } return $pal; } }, clive => sub { my $rev = reverse $_[0]; my $len = 0; my $d; for ( 0 .. length( $_[0] ) - 1 ) { my $c = join '', map { substr( $rev, $_, 1 ) eq substr( $_[0], $_, 1 ) ? 1 : 0 } 0 .. length( $_[0] ) - 1; my $match = ( sort { length( $a ) <=> length( $b ) } $c =~ /(1+)/g )[-1]; $match > $len and $len = $match and $d = $c; $rev = substr( $rev, 1 ) . substr( $rev, 0, 1 ); } $d =~ s/(.*)($len).*/substr($_[0],length($1),length($len))/e; return $d; }, murugu => sub { my $x = shift; my $prev = 0; my $max; while ( $x =~ /(([a-z0-9]+)[a-z0-9]?(??{reverse $2}))/gi ) { $max = $1 if ( length( $1 ) > $prev ); $prev = length $max; } $max; }, jasper => sub { $_ = pop; s/\s//sg; my @a; do { push @a, $1 if /((.*).?(??{reverse$2}))/i; } while s/.//; ( sort { length( $b ) <=> length $a } @a )[0]; }, deibyz => sub { my $match = ''; while ( /.*?(.+)(.?)((??{reverse$1})).*?/g ) { $match = $1 . $2 . $3 if length( $1 . $2 . $3 ) > length( $match ); } $match; }, limbic_region => sub { my %lookup; my ( $index, $record ) = ( -1, 0 ); push @{ $lookup{ substr( $_[0], $_, 1 ) } }, $_ for 0 .. ( length $_[0] ) - 1; LETTER: for my $letter ( keys %lookup ) { my $last = $#{ $lookup{ $letter } }; for my $start ( 0 .. $last - 1 ) { for my $end ( reverse( $start + 1 .. $last ) ) { my $pos = $lookup{ $letter }[$start]; my $length = $lookup{ $letter }[$end] - $pos + 1; next LETTER if $length <= $record; my $palindrome = substr( $_[0], $pos, $length ); if ( $palindrome eq reverse $palindrome ) { ( $index, $record ) = ( $pos, $length ); last; } } } } return substr( $_[0], $index, $record ); }, bgreenlee => sub { my $str = shift; my $longest = ''; while ( $str =~ /(?=(.*)(.?)((??{reverse $1})))/g ) { $longest = "$1$2$3" if length( "$1$2$3" ) > length( $longest ); } return $longest; }, browseruk => sub { my $string = shift; my @pals; while ( $string =~ m[(.) (?=( (?:\1) | (?:.\1) ) ) ]gx ) { my ( $left, $right ) = ( $-[0], $+[-1] ); while ( $left and $right < length( $string ) and substr( $string, $left, 1 ) eq substr( $string, $right, 1 ) ) { $left--; $right++; } my $pal = substr( $string, $left, $right - $left ); if ( !@pals or length( $pals[-1] ) < length( $pal ) ) { @pals = $pal; } else { push @pals, $pal unless @pals; } } return wantarray ? $pals[0] : @pals; }, jdporter => sub { local $_ = shift; my $pal; for my $i ( 0 .. length( $_ ) ) { last if defined( $pal ) && length( $_ ) - $i < length( $pal ); my $j = rindex $_, substr( $_, $i, 1 ); while ( $j > $i ) { my $s = substr $_, $i, $j - $i + 1; if ( $s eq reverse $s ) # it's a palindrome { # but is it the longest yet found? $pal = $s unless defined $pal && length( $pal ) > length( $s ); } $j--; $j = rindex $_, substr( $_, $i, 1 ), $j; } } $pal; }, elgon => sub { use POSIX qw(ceil); my $string = shift; my %char_hash = map { $_ => 1 } split //, $string; foreach my $key ( keys %char_hash ) { my @appearances; for ( my $i = 0 ; $i < length( $string ) ; $i++ ) { push( @appearances, $i ) if substr( $string, $i, 1 ) eq $key; } foreach my $start ( @appearances ) { foreach my $finish ( reverse @appearances ) { next if $start >= $finish; my $half_length = ceil( ( $finish - $start + 1 ) / 2 ); return substr( $string, ( $start ), ( $finish - $start + 1 ) ) if substr( $string, $start, $half_length ) eq reverse substr( $string, ( $finish - $half_length + 1 ), $half_length ); } } } return "FAILED!"; }, japhy => sub { our$P="";pop=~m{(.+).?(??{reverse$1}) (?{length$P<length$&and$P=$&})^}xs;$P }, japhy2 => sub { our@P="";pop=~m{(.+).?(??{reverse$ 1})(?{$P[length$&]=$&})^}xs;$P[-1] }, ); my @input = ( '2710327103701371111111111111111111611111111111111111111116602611111111' . '1111111111111111111111111111111111111111111611111111111111111', 'abcdefghijklmnopqrstuvwxyz12345678987654321zyxwvutsrqponmlkjihgfedcba', 'ababcbabcdcbabcdedcbabcdefedcbabcdefgfedcbababcbabcdcbabcdedcbabcdefedcbabcdefgfedcba', 'abcdedcbabcdefgfedcbabcdefghijklmnonmlkjihgfedcbabcdefghijklkjihgfedcbabcdefghijklmnoponmlkjihgfedcba', ); my @correct = ( '61111111111111111111111111111111111111111111111111116', 'abcdefghijklmnopqrstuvwxyz12345678987654321zyxwvutsrqponmlkjihgfedcba', 'edcbabcdefedcbabcde', 'onmlkjihgfedcbabcdefghijklkjihgfedcbabcdefghijklmno', ); for my $user ( sort keys %contestant ) { my @result = map $contestant{ $user }->( $_ ), @{[ @input ]}; for( 0 .. $#input ) { is $result[ $_ ], $correct[ $_ ], "$user test $_"; } } print "\nRunning benchmark\n"; my $result = cmpthese( 0, { map +( $_ => do { my $user = $_; sub { $contestant{ $user }->( $_ ) for @{[ @input ]} }; } ), keys %contestant }, "none" ); print map Tr( td( $_ ) )."\n", @$result; </code> </readmore> <div class="pmsig pmsig-114691"> <p align="right"><em>Makeshifts last the longest.</em></p> </div> 382567 382881