13
6
The goal of this challenge is to write a program able to guess a word in the smallest possible number of attempts. It is based on the concept of the Lingo TV show (http://en.wikipedia.org/wiki/Lingo_(U.S._game_show)).
Rules
Given a word length passed as the first argument on its command line, the player program disposes of five attempts to guess the word by writing a guess on its standard output followed by a single \n
character.
After a guess is made, the program receives a string on its standard input, also followed by a single \n
character.
The string has the same length as the word to guess and is comprised of a sequence of the following characters:
X
: which means that the given letter is not present in the word to guess?
: which means that the given letter is present in the word to guess, but at another locationO
: which means that the letter at this location has been correctly guessed
For example, if the word to guess is dents
, and the program sends the word dozes
, it will receive OXX?O
because d
and s
are correct, e
is misplaced, and o
and z
are not present.
Be careful that if a letter is present more times in the guessing attempt than in the word to guess, it will not be marked as ?
and O
more times than the number of occurences of the letter in the word to guess.
For example, if the word to guess is cozies
and the program sends tosses
, it will receive XOXXOO
because there is only one s
to locate.
Words are chosen from an english word list. If the word sent by the program is not a valid word of the correct length, the attempt is considered as an automatic failure and only X
's are returned.
The player program should assume that a file named wordlist.txt
and containing one word per line is present in the current working directory, and can be read as necessary.
Guesses should only be comprised of alphabetic low-case characters ([a-z]
).
No other network or file operations are allowed for the program.
The game ends when a string only comprised of O
is returned or after the program has made 5 attempts and was not able to guess the word.
Scoring
The score of a game is given by the given formula:
score = 100 * (6 - number_of_attempts)
So if the word is correctly guessed on the first try, 500 points are given. The last try is worth 100 points.
Failure to guess the word grants zero points.
The pit
Player programs will be evaluated by trying to have them guess 100 random words for each word length between 4 and 13 characters inclusively.
Random word selection will be done by advance so all entries will have to guess the same words.
The winning program, and accepted answer, will be the one to reach the highest score.
Programs will be run in an Ubuntu virtual machine, using the code at https://github.com/noirotm/lingo. Implementations in any language are accepted as long as reasonable instructions to compile and/or run them are provided.
I'm providing a few test implementations in ruby in the git repository, feel free to take inspiration from them.
This question will be periodically updated with rankings for published answers so challengers can improve their entries.
The official final evaluation will take place on the 1st of July.
Update
Entries can now assume the presence of wordlistN.txt
files to speed up reading the word list for the current word length for N between 4 and 13 inclusively.
For example, there is a wordlist4.txt
file containing all four letter words, and wordlist10.txt
containing all ten letter words, and so on.
First round results
At the date of 2014-07-01, three entries have been submitted, with the following results:
4 5 6 7 8 9 10 11 12 13 Total
./chinese-perl-goth.pl 8100 12400 15700 19100 22100 25800 27900 30600 31300 33600 226600
java Lingo 10600 14600 19500 22200 25500 28100 29000 31600 32700 33500 247300
./edc65 10900 15800 22300 24300 27200 29600 31300 33900 33400 33900 262600
** Rankings **
1: ./edc65 (262600)
2: java Lingo (247300)
3: ./chinese-perl-goth.pl (226600)
All entries performed consistently, with a clear winner, being @edc65's C++'s entry.
All contestants are pretty awesome. I have been unable so far to even beat @chinese-perl-goth.
If more entries are submitted, another evaluation will take place. Current entries can also be improved if you feel like you can do better.
So basicly you have to make 2 programs/functions? 1 that knows the word and the other one that tries to guess it? – Teun Pronk – 2014-05-09T12:14:55.887
@TeunPronk no, only one program, the word guesser. The game engine exists and can be compiled from the github repository mentioned in the question. – SirDarius – 2014-05-09T12:24:11.870
1Just to clarify: if the program takes more than 6 tries to guess the word, does it get negative points or just zero? In other words, do we need logic to quit the program after 6 tries to avoid negative points? (Rules say zero points if the program fails to guess the word) – DankMemes – 2014-05-09T13:44:18.623
@ZoveGames: OP states *the player program disposes of five attempts to guess the word by writing a guess on its standard output...*. – Kyle Kanos – 2014-05-09T13:57:30.060
Sorry I didn't read completely... – DankMemes – 2014-05-09T14:07:55.720
1@ZoveGames after five attempts, your program should exit, but the game engine will forcibly terminate it if it refuses to do so :) – SirDarius – 2014-05-09T14:38:36.893
@SirDarius Is the program allowed to make you guess a new word? – MisterBla – 2014-05-15T12:12:41.610
@RichardA no, the player program is run only for one word. – SirDarius – 2014-05-15T12:18:28.107
@SirDarius Could you please explain what you mean with "Implementations in any language are accepted as long as reasonable instructions to compile and/or run them are provided."? I didn't quite understand what you meant with that. – MisterBla – 2014-05-15T12:22:21.617
@RichardA There is no language restriction for this challenge, however, if you choose an exotic language not readily available on Ubuntu, please give explanations how to have your program running. – SirDarius – 2014-05-15T12:34:57.570
@SirDarius Ubuntu ships with Python right? – MisterBla – 2014-05-15T12:37:17.793
1@RichardA yes right, don't worry about Python, it is a first-class citizen, so I will have no problem running some python code :) – SirDarius – 2014-05-15T12:39:13.393
Seems like Python is unable to pick up from stdin. Not sure why. pit.rb hangs when trying to read from stdin – MisterBla – 2014-05-17T21:30:34.857
The output of the program should be a valid word? Or can it be any sequence of character? I want to clarify the rule "If the word sent by the program is not a valid word of the correct length" whether it only wants to specify the length of the guess. Because I see this really similar to Mastermind, where you can guess any sequence of colored pegs.
– justhalf – 2014-05-19T01:40:01.617@justhalf you must give a word that belongs to the wordlist, AND has the same length as the word to guess. – SirDarius – 2014-05-19T07:37:16.447
@RichardA what do you mean by
pit.rb
hangs? It takes quite a long time to finishpit.rb
, for your information. And ensure that you dosys.stdout.flush()
after eachprint
in Python. – justhalf – 2014-05-20T08:36:50.600@justhalf Well, after 10 minutes NOTHING happens. I do flush my output, but it seems either the lingo application waits for input indefinitely or my python script waits for output indefinitely. Send:
print(words[index], end="", flush=True, file=sys.stdout)
Receive:response = sys.stdin.readline()
– MisterBla – 2014-05-20T09:06:53.890@RichardA if you don't feel like publishing a non-working entry, you can always use a temporary Gist as a sandbox, so I can test things on my side. – SirDarius – 2014-05-20T09:34:51.043
@SirDarius http://pastebin.com/Rfx1D8Xc My entry so far.
– MisterBla – 2014-05-20T09:45:38.747@RichardA using python 2 here, replaced the print line by
print words[index]
followed bysys.stdout.flush()
and it works fine – SirDarius – 2014-05-20T09:57:01.067@SirDarius I'm using Python 3, is that okay or do I HAVE to use Python 2? – MisterBla – 2014-05-20T10:20:51.693
You should not use
end=""
, the game engine specifically waits for\n
– justhalf – 2014-05-20T10:33:21.033@RichardA Either will do, as long as it works ;) – SirDarius – 2014-05-20T10:34:56.310
Anyway, for testing you should use ./lingo instead of pit.rb, right? You can run just single word there. – justhalf – 2014-05-20T10:35:32.520
@justhalf Does it really? I might have found my bug then! – MisterBla – 2014-05-20T10:36:06.643
1@justhalf Thanks so much for that! I can finally continue! – MisterBla – 2014-05-20T10:37:33.340
What are the runtime constraints? My first guess is pretty slow (52 hours in my first try, but I can do better...) – edc65 – 2014-06-22T16:04:39.020
@edc65 I haven't enforced constraints yet, given that all posted entries are quite fast so far. 52 hours is not acceptable though ;) The challenge is not that hard, unless you are using an extremely complex algorithm, I don't see why a guess would take more than a second (not including the time needed to read the word list). Don't let this discourage you though, I'm eager to see more challengers ! – SirDarius – 2014-06-23T08:08:33.643
@SirDarius, is there any possibility to count the number of correct guesses beside the score? I feel my answer tends to give the correct answers albeit in more guesses. – justhalf – 2014-07-02T00:15:40.867
1@justhalf good idea indeed, i'll try to implement that – SirDarius – 2014-07-02T09:51:15.337