Haskell, 146 chars
To make things interesting, you get to determine your input structure for the state- which you must then explain.
OK :). My representation of a board is one of those 126 characters
ĻŃŇʼnŊœŗřŚşšŢťŦŨųŷŹźſƁƂƅƆƈƏƑƒƕƖƘƝƞƠƤƳƷƹƺƿǁǂDždžLjǏǑǒǕǖǘǝǞǠǤǯDZDzǵǶǸǽǾȀȄȍȎȐȔȜȳȷȹȺȿɁɂɅɆɈɏɑɒɕɖɘɝɞɠɤɯɱɲɵɶɸɽɾʀʄʍʎʐʔʜʯʱʲʵʶʸʽʾˀ˄ˍˎː˔˜˭ˮ˰˴˼̌
Here's the solution in 146 chars :
main=interact$(\x->case(head x)of h|elem h "ĻŃœťŦŨųŷŹƁƂƅƈƕƠƤƳƿǂdžǞǤǵǾȀȳȿɁɅɑɒɘɝɠɤɵɽʀʐʽʾː˭ˮ˰˴˼̌"->"lose";h|elem h "ƏƝƞƹǁLjǑǝȍȺɆɈɶɾʎʸ"->"cat";h->"win")
And here's how it works, as an haskell script :
import Data.List (subsequences, (\\))
import Data.Char (chr)
-- A set of indexes [0-8] describing where on the board pieces of a single color have been played
-- For example the board "OxO;Oxx;xxO" is indexes [0,2,3,8]
type Play = [Int]
-- There are 126 filled tic tac toe boards when X plays first.
-- (This is a combination of 4 OHs among 9 places : binomial(9 4) = 126)
-- perms returns a list of all such possible boards (represented by the index of their OHs).
perms = filter (\x -> 4 == length x) $ subsequences [0..8]
-- We now create an encoding for plays that brings them down to a single char.
-- The index list can be seen as an 9 bit binary word [0,2,3,8] -> '100001101'
-- This, in turn is the integer 269. The possible boards give integers between 15 and 480.
-- Let's call those PlayInts
type PlayInt = Int
permToInt [] = 0
permToInt (x:xs) = (2 ^ x) + permToInt xs
-- Since the characters in the range 15-480 are not all printable. We offset the chars by 300, this gives the range
-- ĻŃŇʼnŊœŗřŚşšŢťŦŨųŷŹźſƁƂƅƆƈƏƑƒƕƖƘƝƞƠƤƳƷƹƺƿǁǂDždžLjǏǑǒǕǖǘǝǞǠǤǯDZDzǵǶǸǽǾȀȄȍȎȐȔȜȳȷȹȺȿɁɂɅɆɈɏɑɒɕɖɘɝɞɠɤɯɱɲɵɶɸɽɾʀʄʍʎʐʔʜʯʱʲʵʶʸʽʾˀ˄ˍˎː˔˜˭ˮ˰˴˼̌
-- Of all distinct, printable characters
uOffset = 300
-- Transform a PlayInt to its Char representation
pIntToUnicode i = chr $ i + uOffset
-- Helper function to convert a board in a more user friendly representation to its Char
-- This accepts a representation in the form "xooxxxoxo"
convertBoard s = let play = map snd $ filter (\(c, i) -> c == 'o') $ (zip s [0..]) :: Play
in pIntToUnicode $ permToInt play
--
-- Now let's cook some data for our final result
--
-- All boards as chars
allUnicode = let allInts = map permToInt perms
in map pIntToUnicode allInts
-- Now let's determine which boards give which outcome.
-- These are all lines, columns, and diags that give a win when filled
wins = [
[0,1,2],[3,4,5],[6,7,8], -- lines
[0,3,6],[1,4,7],[2,5,8], -- columns
[0,4,8],[2,4,6] -- diagonals
]
isWin :: Play -> Bool
isWin ps = let triplets = filter (\x -> 3 == length x) $ subsequences ps -- extract all triplets in the 4 or 5 moves played
in any (\t -> t `elem` wins) triplets -- And check if any is a win line
-- These are OH wins
oWins = filter isWin perms
-- EX wins when the complement board wins
xWins = filter (isWin . complement) perms
where complement ps = [0..9] \\ ps
-- And it's stalemate otherwise
cWins = (perms \\ oWins) \\ xWins
-- Write the cooked data to files
cookData = let toString = map (pIntToUnicode . permToInt) in do
writeFile "all.txt" allUnicode
writeFile "cWins.txt" $ toString cWins
writeFile "oWins.txt" $ toString oWins
writeFile "xWins.txt" $ toString xWins
-- Now we know that there are 48 OH-wins, 16 stalemates, and 62 EX wins (they have more because they play 5 times instead of 4).
-- Finding the solution is just checking to which set an input board belongs to (ungolfed :)
main = interact $ \x -> case (head x) of -- Only consider the first input char
h | elem h "ĻŃœťŦŨųŷŹƁƂƅƈƕƠƤƳƿǂdžǞǤǵǾȀȳȿɁɅɑɒɘɝɠɤɵɽʀʐʽʾː˭ˮ˰˴˼̌" -> "lose" -- This string is == oWins
h | elem h "ƏƝƞƹǁLjǑǝȍȺɆɈɶɾʎʸ" -> "cat" -- And this one == cWins
h -> "win"
Do we write a function? Take in an input? Do we get to choose the output format? – xnor – 2014-06-24T02:42:54.193
Output should be either
win,lose,cat. For input it must be from a human (not randomly generated). Thus usingdef q(x):#magic code hereworks just as well as(/*magic code */)(prompt())– Dylan Madisetti – 2014-06-24T02:46:16.4101I like this input structure:
(win|lose|cat) [xo]{9}, where the first word denotes whether the game is a win, lose, or cat (?) for player x. Able to represent any state. – Runer112 – 2014-06-24T02:51:33.303Is it okay if we exit with an exception? – undergroundmonorail – 2014-06-24T02:56:22.230
@undergroundmonorail sure – Dylan Madisetti – 2014-06-24T02:58:56.163
@Runer112 added clause 3 for you.
('win')["oooxxoxxo"]would work in your proposed solution, but give the wrong answer thus not being eligible. – Dylan Madisetti – 2014-06-24T03:01:18.457@DylanMadisetti that's why I specified that the first word must denote whether the game is a win, lose, or cat. The example you gave does not match my input structure. – Runer112 – 2014-06-24T03:13:49.920
@Runer112 You're right, and that's why it breaks rule 3. My improper state should not be able to work – Dylan Madisetti – 2014-06-24T03:15:34.000
2Can I suggest a rule like "The win state must be determined from the board" or "The input must contain no information except the board state"? – undergroundmonorail – 2014-06-24T03:16:28.687
Agreed. Checking the validity makes it more complex – Dylan Madisetti – 2014-06-24T03:18:23.103
are we to assume a complete board? otherwise a binary representatiomn wouldn't work great. – Not that Charles – 2014-06-24T03:32:02.637
Let's assume a complete board – Dylan Madisetti – 2014-06-24T03:34:00.587
3Are we assuming only legal games played? If so, certain states would be impossible, i.e. XXX OOO XXX but otherwise some full-board states include this as a fourth impossible outcome, where X wins but O also wins. – Riot – 2014-06-24T04:17:15.223
I think win before lose. If it's becoming too trivial we can throw in some of these stipulations – Dylan Madisetti – 2014-06-24T04:19:38.207
This question from the math stackexchange may be of relevance: http://math.stackexchange.com/questions/467757/determine-the-winner-of-a-tic-tac-toe-board-with-a-single-matrix-expression
– Riot – 2014-06-24T05:01:07.39010why "cat" out of interest? – Chris – 2014-06-24T12:08:40.513
Can the representation of the input state be redundant? Meaning, can the content of a cell be written in more than one place in the input? – xnor – 2014-06-24T12:43:07.453
1@Chris
catis the terminology I learned for a tie. A cat game. No one else? – Dylan Madisetti – 2014-06-24T13:16:57.387@xnor let's go with no, otherwise you can just check for groups of 3 in a long list of board permutations – Dylan Madisetti – 2014-06-24T13:19:39.900
7@DylanMadisetti: never heard it before and googlign for "win lose cat" came up with nothing. I'd have gone with tie or draw personally. Or in the case of this game maybe "inevitability". ;-) I don't much mind as far as the competition goes though. A string is a string. ;-) – Chris – 2014-06-24T13:22:48.703
@chris not crazy. 3rd line http://en.wikipedia.org/wiki/Tic-tac-toe
– Dylan Madisetti – 2014-06-24T14:09:02.120@DylanMadisetti: Just because other people say it, doesn't mean you're not crazy. ;-) – Chris – 2014-06-24T14:29:30.850
Lol, "cat" :) I think "chicken" makes more sense :p (reference from a certain movie with Al Pacino) – aditsu quit because SE is EVIL – 2014-06-24T17:45:24.520
1Can I number all of the boxes? For example, with numbering 123456789 a board like {x: [1, 2, 3], o: [4, 8, 9]} would be winning for x? – Cruncher – 2014-06-24T18:58:52.267
@Cruncher Sure looks like valid input except your example isn't a complete board. Magic square ideas? – Dylan Madisetti – 2014-06-24T19:00:54.980
@DylanMadisetti it is a complete example. X has won. No need to fill in the rest. But yes, magic square ideas. What language is best at finding a subset of 3 with sum 15? lol – Cruncher – 2014-06-24T19:06:03.787