This game for two players is found in the book 101 BASIC Computer Games of 1973,
which in turn refers to the article by infamous Martin Gardner in Scientific American. Wikipedia
mentions two more names though. Anyway, despite being over 50 years old, this problem seemingly doesn't yet have some simple general strategy.
Two players have a rectangular chocolate bar, consisting of small rectangular blocks. Let's mark the top-left corner with coordinates (1, 1)
and bottom-right with coordinates (W, H) (thus the bar consists of W*H blocks). Each player in turn will eat (chomp!) some segment of
a bar. For this any (not yet eaten) block with coordinates X, Y could be picked and removed altogether with every other blocks found in
sub-rectangle with top-left corner at (X, Y) and bottom-right at (W, H). The one who is obliged to take the last block at (1, 1) loses
the game (generally this block is designated as poisoned but let's not be so radical).
The picture above, taken from wiki page, shows example with 5*4 bar and first move made at (5, 3) block.
For mathematician it is clear that such a game is an "impartial" one with "perfect information" and due to Sprague-Grundy theorem is "analyzable by Nim game". However, it looks like all this clarity doesn't help much, for with Nim we know how to detect winning/losing positions and with Chomp we don't.
That is the goal of this problem :)
Input data: will give a list of positions in the game, every position is described literally, with Xs for chocolate blocks (so that
W by H bar is printed as H lines of W characters each). Positions are separated by lines containing three dash (---) and the end of
input is signalized by empty position (e.g. there'll be two lines of dashes).
Answer: for every position please tell is it winnable (use character W) or not (i.e. losing - use character L),
separating them with spaces.
Example
input:
X
---
XXX
---
XXX
X
---
XXX
XX
---
XXXXXX
XXXXXX
XXXX
XXX
XX
---
---
answer:
L W W L L