Hi guys. This is the first problem I’ve worked on. I’m getting a TLE error.
So my initial approach to this, was to create a Min-Max game tree. Here’s my most recent solution.
The psuedocode algorithm is:
def recursiveFunction(string, currentTurn):
for word in dictionary:
if word is in string: //use a string matching algorithm
remove word from string, and split the remaining string
value-a = recursiveFunction(string-a, !currentTurn)
if value-a == currentTurn return currentTurn //winning position
value-b recursiveFunction(string-b, !currentTurn)
if value-b == currentTurn return currentTurn //winning position
if none of the words in the dictionary are in the string (or none of them are winning positions)
return !currentTurn //losing position
(I think this is right).
So the idea is, it’s recursively branching out, but if it finds a branch that it’s definitely going to win, then it can skip the other branches at that level.
But ofcourse, I’m getting a TLE error, so I’ve looked on here for a guide for doing it.
The editorial suggests using the Sprague-Grundy theorem.
Did a bit of reading on using the S-G theorem. Couple of good sources:
One
Two.
Now both of these tutorials talk about the S-G theorem in the context of the game of Nim.
With Nim, - I understand that you don’t need to recursively branch out the tree to find the grundy number of each game, you can just apply the XOR function from the start, and solve it instantly.
(The reason you don’t need to expand the tree for nim, is because you know that a pile of N coins, has a grundy number of N - you know this by thinking it through - eg, a pile of 3, expanded can be a pile of 2, 1, or 0, a pile of 2 can be 0, 1, a pile of 1 can only become 0, so 1 has a grundy number of 1, 2 has a grundy number of 2, 3 has a grundy number of 3…).
Similarly, for the horses chess game mentioned in this tutorial, we can preprocess the grundy numbers for each position on the board, and look those grundy numbers up for our board configuration and apply the XOR function.
But I’m not finding it so clear how we apply this to this problem.
Even the editorial seems to suggest that some recursion is involved:
the game is split into two subgames, S(i, a-1) and S(b+1, j). Because a player can choose any game in his/her turn, the Grundy number of the game is simply the XOR of the Grundy numbers of the two subgames.
Ie - it seems to involve still expanding the tree till you find a losing position, and then passing that up.
ie something like this:
def recursiveFunction(string):
set = []
for word in dictionary:
if word is in string:
remove word from string and split the remaining string:
set.add(recursiveFunction(string-a) XOR recursiveFunction(string-b))
return mex(set)
I can’t see that this is fundementally different to the min-max solution.
And actually - isn’t the min-max faster? - as the min-max can quit once it’s found a winning branch, whereas the S-G needs to continue trying every word.
So, it’s either I need to clarify my use of the S-G theorem, or this simply a matter of optimizing my current algorithm. For example, I don’t I think i need to string search every iteration, I can just store index positions.