Found the problem I was using an instruction forbidden by a strict compiler
The tests are somewhat trivial as the restriction on the number of rounds is not really used.
Look at the example:
rounds = 3, bombs = 3
@ . . . . . @ @ . . . . . @ . . . . . . .
We are short at rounds, so the only solution here would be to use the fist bomb to trigger the second and the third placed on rounds 2 and 3.
@ . . . . . @ @ . . . . . @ 2 . . 1 . . 3
or a more interesting solution with chain reaction:
@ . . . . . @ @ . . . . . @ 1 . . 2 . . 3
There are no like test cases provided, unfortunately
This is the puzzle I have spent most of my time so far, including the VERY HARD ones.
I haven’t found a perfect solution, but I have something to contribute - no one has mentioned memorization yet.
My program places one bomb at a random location (with the location hitting the most nodes played first), or it chooses to wait, and then recursively evaluates the board. Since a bomb and a round is consumed, the board becomes simpler and the recursion is guaranteed to finish, returning whether a bomb sequence is a winning one.
This is where the memorization comes in - my program remembers the losing bomb sequences that have been studied, for example, (0,0), (1,0), (2,0), so if the same sequence is repeated somewhere in the recursion in a different order, say (1,0), (0,0), (2,0), then the recursion can skip the evaluation.
The memorization has reduced the computation by about 100x, and my last case finished evaluation in about 2s, but it was still too slow to pass the test. Because in the last case the bomb sequence is not in the greedy path, it had to take some time to compute. Finally I passed the test by hard-coding the greedy evaluation to not consider bomb placements that only hits one node.
Many of the problems in the HARD category require some kind of memorization to reduce repeated evaluations, and I believe this puzzle requires it too.
I think memorization is a good idea… but what if that sequence could be a winning one in a different state of the game ?
Hi @saffar_mehdi3 I realised the forum thread is shared by the Hard and Very Hard variants of the same puzzle. The memorisation I mentioned only works for the Hard version.
Huh. You appear to be correct. There isn’t an “official” thread for the Redux version of the puzzle, though this one seems to be a decent substitute:
I actually meant for the Hard version… do you take into consideration the WAIT command in the sequence?
Hi @saffar_mehdi3 it works fine with WAIT, because in the Hard version the only purpose of WAIT is for a bomb to clear a node so the next bomb can be placed where the node used to be - so before the node is cleared, the position can never be evaluated and thus never be memorised.
@respho but in what case would one want to place a bomb at the same position again ?
EDIT: wooops nevermind, I thought you meant place the bomb at the position of the last bomb, not the spy node lol
None of you used genetics? i tried but still i can’t guess right way to cross or mutate solutions in a smart way. I just do it randomly and it doesn’t actually pass test “destroy cg”.
Whew, was that a mouthful! I think that time constrains are more generous than the problem description states. I got all the problems, excluding the “Not so fast”, response times below one millisecond, but this last one solved the placements in about 300ms. Problem description states that reaction time must be under 100ms, but surprisingly it accepted the 300ms reaction time and stated a success
My code is somewhat “KISS” style, so definitely improvable, but why bother if already accepted…
I solved it using the decision tree and backtracking, as was suggested in problem details.
I was thinking about using gentics but then I decied I was too lazy for it and went with a simple ‘genetic ready’ solution. Basicly I wanted to do a quick mokup of a code (to see if it’s viable) that would use an exploding bomb weighted pattern to decide which placement of a bomb is the best. My plan was to later on add some kind of genetic generation of mentioned weights.
However it turned out that a simple greedy algorithm with such a pattern as a ‘best fit’ function will pass tests. I fine tuned weights by hand in like 5 min Overall only 1 position had to be changed from default value of ‘1’.
Finally solved the Vox Codei puzzle, by a relatively straight forward way.
Greedy + a little heuristic (to conquer the “not so fast” trap).
The heuristic used is to count the “lonely” targets after a blast. Based on the cross-shape blast effect, I conclude that any similar “not so fast” trap will use a greedy kill count>=4 to fool a greedy algorithm. So, if there are 4 or more lonely targets remaining after a blast, it could be a trap. A second best greedy result should be tried.
I ignored all inputs in the while(true) loop after the map. I just need the map data and output the full list of commands immediately.
lol it ran as exactly as mine
i just tried it. I love it. do u have more?
What is the point of “waiting”? It’s better to plant the bombs the soonest, no?
I’ve started playing in C. It seems that there is a problem with the default code:
char mapRow[width+1]; // one line of the firewall grid
fgets(mapRow, width+1, stdin); // one line of the firewall grid
It can easily be fixed by using: gets(mapRow); or by removing the \n char from the end of the input text.
For episode 1 following approach worked well for me:
- Unite all nodes into “elimination groups” (EG) in a way that no EG is a subset of another. EG is all nodes destroyed by one bomb.
- Find combination of nuber_of_bombs EGs that include all nodes
Sorting by EG size and memoisation turns step 2 factorial complexity into something acceptably fast
Done. 2 episodes 100%
I managed to solve the task in the third turn (100 ms time frame) for episode 2 and in the first turn for episode 1.
For episode 1 first I mark best cells for placing bombs (which will destroy more than 2 surveillance nodes) and then using DFS to try different combinations of those cells.
For episode 2 first I gather the movement data from the first two turns, then generate the surveillance nodes movement directions, after that I mark the best cells to place bombs, using the directions data and simulating all rounds and then try different combinations of those cells using DFS.
Most important things I made, were to sort the candidate cells based on the destroyed nodes if a bomb is placed there and if a bomb destroys much nodes, use it immediately.
I got here after trying about 4 different strategies in time span of several weeks.
My combination algorithm is not good it’s rather problem specific, and generates many duplicate combinations, but at the end it worked nicely.
I am stuck at 80% with Vox Codei - Episode 2 puzzle. I have a working simulator and a DFS-style search on the game state tree, but:
- If I limit search depth to 4 steps ahead, then IDE tests 08 and 10 fails (use up too much bombs in sub-optimal solution)
- If I try to search deeper, even more tests fail due to timeout.
I am not sure how to proceed:
- Do I miss some important search tree pruning idea?
- Or shall I simply try to make my code faster? (It’s currently not speed-optimized, using arrays of objects, more bytes than essential for game state representation, and written in PHP…)