I don’t understand the problem statement / the examples
Statement says that capturing is based on any combination of these adjacent dice .
The Capture example demoes 4 adjacent dice and captures all 4 of them.
There is also a Capture with multiple possible dice combinations example.
My conclusion: As there is a dedictated example with multiple possible dice combinations , the Capture example has just one possible combination. BUT there are 4 adjacent dice. Any combination of those 4 meets has a sum of displayed values less than or equal to six … so there are quite some combinations also for that example.
My understanding is also that Any combination also comprises combinations with single dice in it → that means each capture is by definition a Capture with multiple possible dice combinations.
Last not least: The Non-capture example has 2 adjacent dice … one of them being a 2 → So there is a combination that can be captured !?
For a combination to be valid, at least two dices must be involved.
I will use test case 11 unique states to illustrate:
We start with the following board and a depth of 1.
---
616
101
616
---
After 1 move, we get 11 unique board states:
---
616
120 // combination of right and down
606
---
---
606
120 // combination of right and up
616
---
---
616
021 // combination of left and down
606
---
---
606
021 // combination of left and up
616
---
---
616
020 // combination of left and right
616
---
---
606
121 // combination of up and down
606
---
---
606
130 // combination of up, right, and down
606
---
---
616
030 // combination of left, right, and down
606
---
---
606
030 // combination of left, up, and right
616
---
---
606
031 // combination of left, up, and down
606
---
---
606
040 // combination of left, up, right, and down
606
---
Note: In this exercise, you will not […] need to track whose dice is whose.
Does your answer mean that we actually do have to keep track something?
Example:
Start with an empty grid. Player A can play top left corner and player B bottom right corner or vice versa. The two states look identical but every move generated from the two states will secretly be different?
The Capture example is misleading because it is in fact a Capture with multiple possible dice combinations
We should not calculate possible final boards, but possible turn sequences and the resulting final boards. It may happen that multiple turn sequences produve the same board state
I was also confused about this, and feel the current rules are a bit misleading.
Compute all possible future states of an ongoing game of Mark Steere’s Cephalopods in the shortest time possible .
Your objective is to find all the possible board states
Your program must […] compute all possible board states
Output One integer:final_sum, the sum of all board hashes for possible game states after at most depth turns.
None of these suggest that duplicate game states should be included in the final sum, but as BorisH pointed out above, the first test case (that has only a single possible final gamestate) suggests that we need to sum the final game states (including duplicate states) of all unique paths to that state.
I think the opening line of the puzzle would be much less confusing if it was “Simulate all possible games” instead of the current “Compute all possible future states”.
Sorry I couldn’t answer earlier as forum was broken on my end…
No. We just need to generate at each step every possible move, or - as @BorisH phrased it under your reply - every possible sequences of moves within the given depth. (== DFS)
On another note, the constraint 1 < depth < 20 is not respected on several test cases… some have a depth of 1, a bunch have a depth up to 40.
Question on the scoring/leaderboard: Are there different leaderboards for the different languages? Especially as this is about best wall clock time the language might provide an advantage already so I’m not sure that would be fair.
On the other hand if there are multiple leaderboards, is it possible to participate in multiple ones using different languages? Might be quite interesting.
Also a question that I was wondering about in another puzzle is about compiled languages: Is it safe to assume they are compiled with full optimisations enabled? I.e. -O3 for C/C++?
Just a supposition, but it looks like an optimization challenge. Optimization challenges typically do not take the programming language into account for ranking, so I think using C++ is a good idea.
Do I need to do anything besides clicking ‘SUBMIT’ to get into the leaderboard? (or is there some bug?) I’ve tried submitting twice, and while I’m getting the results back, my rank is still N/A and I can’t see myself on the leaderboard.
This may be a longshot but I’m not sure where else to ask. My code works for the first few test cases but when I get to the 5th test case (20 unique states), my code returns too many end states. I have checked and it does only return 20 unique states but in terms of paths, I am getting 5368 unique paths when I think I should be getting only 1484. I have made sure that the state computed is only marked as an end state if the board is full or the max depth has been reached. I am not sure what else to do. Is there some other criteria for eliminating end states that I am not aware of?
Thanks.
Hi,
I am kinda in a similar case.
The firsts tests are ok but the 5th is not.
But I found less path than needed : i got 144 instead of 1484.
In my case I think it’s because there is some legal plays my code might consider “illegal” and I need to find them and debug my code.
In your case it might by your code playing illegal plays thus finding more paths.
I’m also a bit stumped at example 5. I’m lacking some states, only amounting to 1136 paths and 12 unique states:
616121615, 616131615, 616141615, 616116611, 606016631, 606106631, 616006631, 606116630, 616016630, 606046600, 616106630, 616126611