[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


#15

I have to wonder if I missed the point of the exercise as I was able to solve the puzzle without taking water usage into consideration (my program assumed there would always be enough water to put out all the fires).

My program just went from most dense to least dense, firing the appropriate amount of water to cover the intended area. I passed every test case, and I was wondering if my solution was possibly too long or if the puzzle wasn’t able to fool the conditions that I had set for it.


#16

It doesn’t work for me. I’m getting this error :
java.lang.NumberFormatException: For input string: “”
at java.base/java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
at java.base/java.lang.Integer.parseInt(Integer.java:662)
at java.base/java.lang.Integer.parseInt(Integer.java:770)
at com.codingame.game.Referee.gameTurn(Referee.java:168)
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)