[Community Puzzle] Minimax Simple Example

@ Wildcat
Hello, I am trying to solve the puzzle and for some reason I fail test 4 in the IDE and test 1 of the validators.
Can you please let me know if there is anything particular about these two tests, or maybe provide the input for validator test 1, so I can figure out where the difference to my solution is.

Thanks in advance.

I think the error is in our code. I too fail the validator 4. Although I have access to it, I will not share without @wildcat 's permission.

Yes, it might be the code or a misinterpretation of the puzzle statement - for instance with regard to the building of the game tree.
I think a smaller test case of a few turns that is different from test 1 in the IDE should be able to make that obvious as it would still be solvable on paper.

The inputs for the test 1 of the validators are:

4 4
ON 2
IT 4
IN 1
I 1

The solution for this test is

N 0-1

Tell me when you’ll resolve your problem, if I have to clarify the puzzle statement.

Thanks a lot. The test case helped me to find the problem. I was not taking into consideration the last move i.e. how the score changes after the last letter goes to the opponent.
I do not think that you need to change the puzzle statement, as this point is pretty clear. The confusion was on my side.

Just another clarification - after adjusting my score calculations I get two identical solutions for test 4 in the IDE.
The first solution is the right answer: collected letters for maximizing player I, E, G, R, A, M, D, H (and T, C, L, F, P, S, O, N for the minimizing player) producing the score of I 29-14.
An alternative solution is: collected letters for maximizing player T, E, F, R, A, M, D, N (and I, C, G, L, S, P, O, H for the minimizing player) giving the score T 20-5.
As it can be seen both paths have the same point difference between the scores of the maximizing and the minimizing player of 15.
Maybe the puzzle statement could be adjusted to reflect this possibility.


When I pick T first, I get a score of 22-15. I had a look at Wildcat’s solution at that confirms my result.

I am stuck from the 8 turns in the validator and the 16 rounds in the test cases. I am not sure what is failing in my code. I get right the previous cases (that includes @Wildcat validator case mentioned above). In the 16 turns test case my code code is outputting “I 18-15”. Maybe having another example of 8 turns could help me. Any help would be appreciated.

I solved the problem! The minimax algorithm retrieved the right value. I just screwed it up returning p1 and p2. Now I only need to optimize it to get a 100%.

1 Like

I am struggling getting the last test case. I apply a standard alpha prunning minimax algorithm in python. But I get at most to do 86k iterations before I get a timeout. I also use memoization for getting the points from the player choices. Am I not seeing something? Or is there any trick that I am not using? Any hint would be appreciated!

EDIT: I succeeded in the end. I profiled my code and I saw that I was wasting a lot of time checking words inside the players combinations. In the end I used some python “sets” to to check that up faster.

1 Like