There are three computers connected by a network. One of them is a server and the other two are clients. The server has some files, each with a different name. The full name of each file consists of two parts, a name and an extension. Both clients know the full names of all of the files stored on the server. From among its files, the server chooses a single file and sends the name part of that file's full name to one of the clients and the extension part of the full name to the other client.
The clients then begin communicating in an effort to determine which file was selected by the server (they want to learn the file's full name). However, the clients have to communicate in a very restricted manner. Clients take turns sending messages to each other, but they can only say when they don't know the full name of the file. If one client does not know the full name of the chosen file, that client will send a message saying "I don't know the full file name" to the other client when it's his turn. The two clients alternate, sending only this message back and forth. The client that received the name part of the full file name always waits for the client that received the extension part to send the first message.
This continues either until one of the clients figures out the full file name (so it won't say anything on its turn and the conversation falls silent), or they forever keep saying "I don't know the full file name". The clients are very smart and always completely use all available information.
So some files chosen by the server would cause the clients to fall silent after a certain number of steps, while other files lead to infinite denials. You are to find the file(s) that give rise to the longest finite conversation.
On STDIN you get the list of files, one full name per file. The full names are restricted to something like MS-DOG 8.3 format. Each full file name is represented in name.extension form, where both the name and the extension consist of only capital, alphabetic characters and decimal digits. The name part will have at least one character and at most eight. The extension part will have at most three characters and may be empty. If extension is empty then separating dot may be omitted. So each line matches /^[A-Z0-9]{1,8}(\.[A-Z0-9]{0,3})?\n\z/. Each filename will appear in the input no more than once. There will always be between 1 and 1000 (inclusive) files on the list.
On STDOUT you should write the files leading to the longest finite conversation, one file per line, in exactly the same order and spelling as these files appeared in input.
Nothing should be written to STDERR. The returncode of your program does not matter.
Example input:
LICENCE.TMP WIN32.LOG FILEID. PSTOTEXT.TXT GSVIEW32.EXE GSVIEW32.ICO GSVIEWDE.HLP LICENCE GSVIEWEN.HLP GSVW32DE.DLL FILEID.TMP GSVW32EN.DLL PSTOTXT3.DLL PSTOTXT3.EXE GSV16SPL.EXE GVWGS32.EXE ZLIB32.DLL PRINTER.INI README.TXT
Four files (LICENCE.TMP, FILEID., LICENCE and FILEID.TMP) will lead to an infinite conversation. Three files (WIN32.LOG, GSVIEW32.ICO and PRINTER.INI) lead to immediate silence, Two files (PSTOTXT3.DLL and PSTOTXT3.EXE) lead to two messages exchanged, for all other files only one message will be sent. So the longest finite conversation is two messages, and the output should be:
PSTOTXT3.DLL PSTOTXT3.EXE
Check your solution using the test program
The challenge runs under the generic perl golf rules.
This challenge is an experiment in doing a hard golf. Therefore:
Tell the length of your solutions (but not the solution itself) to ton- on ircnet #perl or mail the number to perl-golf@ton.iguana.be. If you send a team solution, give your team name and (optionally) the names of the members of the team
This challenge is based on, but different from an old ACM challenge
90 ton 99 mtve 132 k.c.ivey 139 q.huo
90 ton -0p s>\n>$|--;s%(\w+)\.?(.*\n)%(map$|?/^\w+\b.?$2/m:/^$1\b/m,$`,$')?$&:!($\=$@.=$&)%eg>eeg}{
99 mtve sub f{++$a{(/\w+/g)[$|]}}$\=$X||$\,%a=$X=$|--x0,@:=grep f>2||!($X.=$_),grep f,@:,<>for 1..1e3;print
132 k.c.ivey -p0i(\w+)\.?(\w*) %c=c;s/$^I( )?/$3?$;:$&.($c{${2-$|}}eq c&&$")/ge,%c=$|--while(map$c{$_}.=c x$|--,/$^I\n/g),grep/^c$/,%c;s/\S+\n| //g
Post mortem:
89 mtve -0p s>\n>$|--;s%(\w+).?(.*\n)%(map$|?/^\w+\b.?$2/m:/^$1\b/m,$`,$')?$&:!($\=$@.=$&)%eg>eeg}{