Topological Sort

Score: 77.51 (fail)

Replace die() with a call to an undefined sub.

#!perl -ln0
$_ x=2;s/(^| )(\Q$1\E\s)+/$1&&&1/megwhile/^(\S+)\s(?!\C* \1
)/m&&print$1

Score: 78.49 (fail)

I doubt that there's much left to gain by reorganizing the loop a third time.

#!perl -ln0
$_ x=2;s-(^| )(\Q$1\E\s)+-$1&&die-megwhile/^(\S+)\s(?!\C* \1
)/m&&print$1

Score: 79.49 (fail)

It seems that the carefully crafted loop based on s///e and redo was rather suboptimal...

#!perl -ln0
$_ x=2;(print$1),s-(^| )(\Q$1\E\s)+-$1&&die-megwhile/^(\S+)\s(?!\C* \1
)/m

Score: 81.45 (fail)

Replaced the "$_ x=2;{foo}" with "foo for$_ x2".

#!perl -ln0
s%^(\S+)\s(?!\C* \1
)%print$1;s-(^| )(\Q$1\E\s)+-$1&&die-meg;redo%emfor$_ x2

Score: 82.47 (fail)

Smarter test for loops, nicked from an earlier solution. Too bad, I really liked that sqrt...

#!perl -ln0
$_ x=2;{s%^(\S+)\s(?!\C* \1
)%print$1;s-(^| )(\Q$1\E\s)+-$1&&die-meg;redo%em}

Score: 83.45 (fail)

Oops, remove an useless .*

#!perl -ln0
$_ x=2;{s%^(\S+)\s(?!\C* \1
)%sqrt$;{$1}--;print$1;s|^(\Q$1\E\s)*||mg;redo%em}

Score: 84.45 (fail)

Embed everything inside the main substitution. We aren't even a day into the contest, and already I don't understand what the code actually does.

#!perl -ln0
s/^(\S+)\s(?!.*((?!\1)\S+) \1
)/print$1;s%(^| )(\Q$1\E\s)+%$1&&die%meg;redo/sem

Score: 85.46 (fail)

I don't know why this works. Probably I don't quite understand the exact semantics of zero-width negative look-ahead. I'm not going to complain, though.

#!perl -ln0
$_ x=2;{s%^(\S+)\s(?!\C*.+ \1
)%sqrt$;{$1}--;print$1;s|^(\Q$1\E\s)*||mg;redo%em}

Score: 86.54 (pass)

Replaced x=2 with x=3, which allowed changing a ^ from the regexp to \n, which allowed removing a /m-modifier from the regexp.

#!perl -ln0
$_ x=3;s/(^| )(\Q$1\E\s)+/$1&&&1/megwhile/
(\S+)\s(?!\C*
(?!\1 ).+ \1
)/&&print$1

Score: 87.54 (pass)

Finally had time to construct a test-case for the suspicious bit of code in my solution. Any sub-84 solution from me is going to fail on "a b b c a a". Time for v1.9? :-)

#!perl -ln0
$_ x=2;s/(^| )(\Q$1\E\s)+/$1&&&1/megwhile/^(\S+)\s(?!\C*^(?!\1 ).+ \1
)/m&&print$1

Score: 91.55 (fail)

Just testings the waters, before I spend any more time on this idea. This program fails for some inputs of over 100000 lines. If this entry isn't accepted, a clarification on the maximum input size would be appreciated.

#!perl -p0
1/(1e5-$z++);s|^((\S+) (\S+)
)(.*\S+ \2
)|$4$1|msg&&redo;y/ /
/;s/^(\S+
)(?=.*^\1)//gsm

Score: 92.45 (fail)

Heh, wouldn't have thought that sqrt would be useful on this hole :-)

#!perl -ln0
$_ x=2;s%^(\S+)\s(?!.*((?!\1)\S+) \1
)%sqrt$n{$1}--;print$1;s|^(\Q$1\E\s)*||mg;redo%sem

Score: 92.50 (pass)

This is just my 82 stroke solution with extra checks. I haven't constructed a test which the 82 doesn't pass, but I'm pretty sure there is one.

#!perl -ln0
$_ x=2;{s%^(\S+)\s(?!\C*^(?!\1 ).+ \1
)%print$1;s-(^| )(\Q$1\E\s)+-$1&&die-meg;redo%em}

Score: 93.48 (fail)

Works even with "a b, b c, d a", unlike the 84.

#!perl -ln0
$_.=$_;s/^(\S+)\s(?!.*((?!\1)\S+) \1
)/$n{$1}++&¨print$1;s|^(\Q$1\E\s)*||mg;redo/sem

Score: 94.46 (pass)

Sandtrap-insurance.

#!perl -ln0
$_ x=2;{s%^(\S+)\s(?!.*((?!\1)\S+) \1
)%sqrt$;{$1}--;print$1;s|^(\Q$1\E\s)*||mg;redo%sem}

Score: 97.46 (fail)

Join the sub-100 club using some regex merging.

#!perl -ln0
s/$/\t
$`/;s/^(\S+)\s(?!.*((?!\1)\S+) \1
).*\t/print$1;s|^(\Q$1\E\s)*||mg;redo/sem;/\S/&&die

Score: 101.44 (fail)

Yesss my preciousss..... We takessss back the second place...

#!perl -ln0
s/^(.+) \1$/$1/gm;s/$/\t
$`/;s/^(\S+)\s(?!.* \1
).*\t/print$1;s|^\Q$1\E\s||mg;redo/sem;/\S/&&die

Score: 107.47 (pass)

Ah, I should have remembered that regexes always win... :-)

#!perl -ln0
s/^(.+) \1$/$1/gm;$_.="\t
$_";s/^\Q$1\E\s//mgwhile
s/^(\S+)\s(?!.* \1
)(.*\t)/print$1;$2/mse;/\S/&&die

Score: 118.47 (pass)

I'm afraid that this isn't how Ton did his 88, but at least it takes me to unshared second place... Well, back to the drawing board.

#!perl
@a=<>;{map{s/^(.+) \1$/$1/;if((($a)=split)&&!grep/ \Q$a\E$/,@a){print"$a
";s/^\Q$a\E\s//for@a;redo}}@a}map/\S/&&die,@a

Score: 125.48 (fail)

#!perl
@a=<>;{map{s/^(.*) \1$/$1/;($a,$b)=split;if(!grep/ $a$/,@a){print"$a
";@a=grep!/^$a(\s|$)/,@a;$b&&push@a,$b;redo}}@a;@a&&die}

Score: 126.48 (pass)

Regexp metacharacters should work now.

#!perl
@a=<>;{map{s/^(.+) \1$/$1/;($a,$b)=split;if(/\S/&&!grep/ \Q$a\E$/,@a){
print"$a
";s/^\Q$a\E\s//for@a;redo}}@a}map{/\S/&&die}@a