[Community Puzzle] Forest Fire


#1

https://www.codingame.com/training/medium/forest-fire

Send your feedback or ask for help here!

Created by @AlBlazing,validated by @eulerscheZahl,@bbb000bbbyyy and @JBM.
If you have any issues, feel free to ping them.


#2

Errr… I can’t seem to get a submission through.
The IDE’s results pane is stuck in a “computing score” status.


#3

Fixed.
The validators have to be named test<number>.json, not validator<number>.json.
I renamed them and reuploaded.

In the validation process I would really like to see the puzzle in a way as it will be shown after approval (including hidden statement for reverse clashes).


#4

18/06 /2019 - 17:10

Still stuck for me.

a

Also, 1 on every 3 attempts at stage 2, I get this error:


#5

Thanks, now it works.


#6

Test 02 fails on 3/5 runs for me with:

The game has crashed. Please contact the author and enclose the following error:

java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
   at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
   at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
   at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
   at java.base/java.util.Objects.checkIndex(Objects.java:372)
   at java.base/java.util.ArrayList.get(ArrayList.java:458)
   at com.codingame.game.Referee.init(Referee.java:55)
   at com.codingame.gameengine.core.GameManager.start(GameManager.java:111)
   at com.codingame.gameengine.core.RefereeMain.start(RefereeMain.java:69)
   at com.codingame.gameengine.core.RefereeMain.main(RefereeMain.java:52)

#7

Can you share the outputs of your bot to reproduce the crash?

Edit:
the game crashes on this line:
L = Integer.parseInt(gameManager.getTestCaseInput().get(0));
The referee randomly fails reading the map from the testcase. It works most of the time but not always. I think that’s the SDK’s fault, not the game itself.


#8
The game has crashed. Please contact the author and enclose the following error:

java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
	at com.codingame.game.Referee.gameTurn(Referee.java:160)
	at com.codingame.gameengine.core.GameManager.start(GameManager.java:122)
	at com.codingame.gameengine.core.RefereeMain.start(RefereeMain.java:69)
	at com.codingame.gameengine.core.RefereeMain.main(RefereeMain.java:52)

#9

As I wrote above, that line 55 reads the testcase input:

L = Integer.parseInt(gameManager.getTestCaseInput().get(0));

For whatever reason it failed to do so.
I had a similar issue with Bender, where one validator was almost always failing. A simple reupload of the game solved the problem.

Maybe reuploading will work here as well, but instead I would like staff to have a look (ping @_CG_Thibaud) as I think the cause goes beyond the puzzle itself.

I had to play the 2nd testcase about 10 times to reproduce the crash. I think any player code should do the job, as the testcase gets loaded before executing the player.


#10

I can pass all IDE tests, but not with the same code :frowning:
The statement suggests ‘greedy algorithms’ so I did not implement simulation just selecting ‘best’ next action from all possible ones.
However, if I sort the actions by ‘cost per fire’, ‘fire’, ‘vehiclesize’ then IDE test L fails, all other OK including XL.
If I sort the actions by ‘fire’, ‘cost per fire’, ‘vehiclesize’ then IDE test XL fails, all others OK.
It seems I still need to take into account if an actions make good action in subsequent turn impossible - but that would need simulation and search tree which I wanted to avoid by being greedy.
Any ideas, what is the good greediness criteria to use?


#11

As @TBali pointed out, greedy with weighting also didn’t work for me. I got 100% with some random weights associated to the fires doused, and a check for immediate completion. But I DON’T pass all test cases, so it’s not a correct solution. Can the author of the puzzle please explain what greedy approach is intended by the tag :slight_smile:


#12

A few weeks after my earlier post I finally passed this puzzle with the greedy method by using a manual (but fixed) precedence of the possible actions. (A fixed “[coversize][firecount] => priority” lookup table, I found by try-and-error.) Not nice, but at least not ‘test-case specific hardcoded’. In retrospect, the resulting order has some logic , but not one that I thought of by myself :slight_smile:


#13

Congratulations on not having hard coded :pensive:. But I don’t follow your algo. Could you elaborate?


#14

Code excerpt (in PHP syntax, sorry if not your prefered one…)

const Order = array(
// [cover][fire] => precedence
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1 => [ 0, 7, 0, 0, 0, 0, 0, 0, 0, 0],
2 => [ 0, 8, 6, 5, 4, 0, 0, 0, 0, 0],
3 => [ 0, 13, 12, 11, 10, 9, 3, 2, 1, 0]
);
static function compare3(array $a, array $b): int {
$a1 =self::Order[$a[‘cover’]][$a[‘fire’]];
$b1 =self::Order[$b[‘cover’]][$b[‘fire’]];
return $a1 <=> $b1;
}

Preparation:
I generate an array for the 14 possible actions (where cover*cover <= fire)
Could have used a class for the Action, used associative array instead.

tryOrder[] = array(‘cover’ => $coverSize, ‘fire’ => $fireSize, ‘cost’ => $perFireCost);

then sort it using the fixed priority above:

usort($tryOrder, array(‘ForestFire’, ‘compare3’));

Then I try to use the actions in this sorted order

foreach ($tryOrder as $try)
// check if current action is still possible (have enough water and have suitable target) and use it