Vox Codei - Puzzle discussion

Puzzles
#46

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:

  • danBhentschel
#47

I actually meant for the Hard version… do you take into consideration the WAIT command in the sequence?

#48

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.

#49

@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

#50

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”.

#51

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 :open_mouth:
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.

1 Like
#52

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 :slight_smile: Overall only 1 position had to be changed from default value of ‘1’.

#53

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.

#54

lol it ran as exactly as mine

#55

i just tried it. I love it. do u have more?

#57

Hi,
What is the point of “waiting”? It’s better to plant the bombs the soonest, no?

#58

Hi @codingame,
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.

#59

For episode 1 following approach worked well for me:

  1. 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.
  2. 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

#60

8 posts were merged into an existing topic: Vox Codei - Episode 2

#66

I almost finished the puzzle, but I have a bug I need to share: The only testcase I’m not able to solve is Foresee the future better with two bombs:

BUT in the test Foresee the future (same with three bombs), I solved it… using only 2 bombs:

This shouldn’t be too hard to solve, but I had to share it :joy:

#67

What’s your code for handling the bomb limits?

#69

This was my approach. Didn’t even need memorization and run under 10ms the worst case. It was quite easy, code very understandable and fast. Used python with sets for the bomb/nodes relations and iterators for the combinations

#72

For Vox Codei Ep 1 there is NO need to use backtracking in this puzzle. I have been mislead by comments in this forum (no offense! :slight_smile:) to use such a technique and lost a lot of time figuring it’s absolutely unecessary. You can solve the puzzle with a simple greedy algorithm. IMO, the hard part is to find the heuristic for the final test (trap). Otherwise it’s pretty straightforward using bruteforce and simulation.

#73

This is a forum culture issue that affects Vox Codei and a few other puzzles, @UrbanWhale.

This is the primary topic for all of Vox Codei. There are comments here that relate to VC Ep 1, VC Ep 2, and to the original contest (IIRC. Been a while since I read the topic from the top). Sometimes you have to determine from context which incarnation of VC a particular post refers to. When it sounds like a poster is talking about a different puzzle, they may well be. Just acknowledge and move on, maybe bookmark something if it looks like it will be useful later.

#74

Hi, I have just finished the puzzle in python and when I confirmed my solution, which passed the tests %100, I decided to give it a try one of the solutions that codingame offers… The second solution isn’t solving whole test cases, hups!! Only 93%…