4
\$\begingroup\$

Challenge

Being someone who plays far too much chess in his spare time, I thought I'd set a code golf challenge inspired by the game of chess (with a software flavour), for those interested.

The challenge is to determine the winner of a game of standard chess given a PGN (Portable Game Notation) file as input -- or in the case of a draw/stalemate, be able to recognise it.

Write a full program that takes via the standard input stream a PGN file except the final result string and outputs the winner of the game. (See the Wikipedia article for a simple description of the text format.) The program should determine the winner from the provided move information and output 1-0 for White winning, 0-1 for Black winning, and 1/2-1/2 for a draw (by stalemate). Mutually agreed draws and resignations should be denoted ? since they cannot be differentiated on this basis alone. White is always assumed to move first.

Note that the Result metadata tag nor the game result at the end of the PGN block itself is to be included in any input, as this must be determined by the program's algorithm. The checkmate symbol (usually #) is also never present. All other metadata and comments are valid input to the program.

Example (from Wikipedia page):

Input:

[Event "F/S Return Match"]
[Site "Belgrade, Serbia Yugoslavia|JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8  10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 1/2-1/2

Output: ? (since it was a mutually agreed draw)

Rules

Other than mentioned in the problem statement, there are no further restrictions. You may write the program in any compiled/interpreted programming language. The code for the program must be complete, i.e. compile without any modifications or external reference.

The aim as always is to solve the task with the smallest number of characters of code.

(Saying that, I can't promise to accept the answer with the shortest code. I'll also be looking at elegance of the code and time complexity of the algorithm, especially in the case of verbose language, and hope others will do the same!)

My Solution

I'll be attempting an F# solution while this question is open -- will post it here when I have something.


Format

Please post your answers in the following format for the purpose of easy comparison:

Language

Number of characters: ???

Fully golfed code:

(code here)

Clear (ideally commented) code:

(code here)

Any notes on the algorithm/clever shortcuts the program takes.


\$\endgroup\$
  • \$\begingroup\$ Migrated from StackOverflow, per request. \$\endgroup\$ – Noldorin Sep 26 '11 at 0:16
  • 4
    \$\begingroup\$ There is no way to determine the result in your example - it was an agreed-upon draw. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Sep 26 '11 at 2:11
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft: You're right. That's a really bad example! I'll try to replace it soon. Let's assume for now that it's an actual checkmate or stalemate, alright? \$\endgroup\$ – Noldorin Sep 26 '11 at 2:39
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft: Actually, I take that back. An agreed-upon draw can be determined easily, because after the last move it will neither be checkmate nor stalemate, and all games are assumed to be complete. \$\endgroup\$ – Noldorin Sep 26 '11 at 13:31
  • 2
    \$\begingroup\$ Various unnecessarily combative comments deleted. Acceptance is at the discretion of the asker, but [code-golf] implies that minimum length (along with correctness) is the primary criterion for a good solution. \$\endgroup\$ – dmckee Sep 27 '11 at 16:45
6
\$\begingroup\$

Ruby 1.9

Number of characters: 93

Assuming that all inputs are valid games, and that games always end in checkmates or stalemates (as per Noldorin's response in the comments), then we only need to check who played the last move and whether it was a checkmate or not.

Golfed code:

*a,b,c=$<.read.gsub(/{[^}]*}|;.*$/,"").split;puts c=~/#/?(b=~/[^.]\.$/?"1-0":"0-1"):"1/2-1/2"

Ungolfed code:

# read entire input
game = $<.read
# strip comments
game = game.gsub(/{[^}]*}|;.*$/,"")
# split the input and get the last two words
*rest, second, last = game.split
# check if the last move has a checkmate symbol
if last =~ /#/
# if so, then determine whether the last move is white or black based
# on the number of periods in the second-to-last word
  puts second =~ /[^.]\.$/ ? "1-0" : "0-1"
else
# if not, then it's a draw
  puts "1/2-1/2"
end
\$\endgroup\$
  • \$\begingroup\$ Sneaky! This does indeed solve the challenge. I think I'm going to have to edit the original task slightly, to make it more challenging I'm afraid...sorry. \$\endgroup\$ – Noldorin Sep 26 '11 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.