[Community Puzzle] Forest Fire

Puzzles
#21

Thank you for the reply. Yes I had my print statement nested inside of another loop. That is what caused the warning.

#22

Hey, I tried a greedy algorithm that find all the places for every unit (J,H,C) that shut down the fire and then I sort all the data by how much fire shut down.
It worked for the first 3 cases, but for the more complicated tests it didn’t.

Then I implemented algorithm that find the path to the victory by searching every possibility until finding the right path, but it was too slow.

I also combined both so it will start his search for the best path from the places and units that shut down most fire, it also didn’t work.

I think I need to implement the first algorithm I mentioned but exploring every possibility for the next 4 or 5 turns to find the best place and unit. Is it right or there is other way?

Thanks :slightly_smiling_face:

#23

You can find a heuristic for this puzzle, no need for a simulation.
For example if you take the 3x3 square that contains the most fires and it contains more than 4 fires, then a canadair at that spot is your best option.

1 Like
#24

Thank you :smiley:
what you suggested help me to reach 88% but I still can’t pass XXL test case :slightly_frowning_face:

What I did according to your suggestion:
if HowMuchFireShutDown(‘C’) > 4 -> find the location to put ‘C’ unit so it would shut down the most fire.
if HowMuchFireShutDown(‘H’) > 1 -> find the location to put ‘H’ unit so it would shut down the most fire.
if HowMuchFireShutDown(‘J’) > 0 -> put in this place, there is no better place (because it can shut down just one).

#25

Actually looking back at my code, i’m using a canadair if there’s more than 5 fires, not 4. Can’t remember why but maybe that will help you :slight_smile:

3 Likes
#26

The reason is simple: Canadair Superscooper is the best :slight_smile:
image

1 Like
#27

I know what is the reason.
Consider this case:
FFX
FFX
XXF

This if: FireShutDown(‘C’) > 4, would work in this case and will waste me 2100 liters.

But there is better solution to this situation: putting ‘H’ unit that will clear the group of 4 fires and ‘J’ unit that will clear 1 fire.

This solution help us waste less water because the cost of this solution is just: 1200 + 600 = 1800 liters.

So the second solution is better than the first one because 1800 < 2100 !!!

And this is what I was missing.

Thanks for your help I was able to understand it and solve the puzzle.
Thank you!! :smiley:

3 Likes
#28

Thanks the “>5 then C” works for the given cases.
I’m still wondering if “>5” is doable by greedy:
FFFF
FFFF
XXXX
XXXX
It seems 2100(6)+600(1)+600(1)=3300,
But 1200(4)+1200(4)=2400 is better.

“>6 then C” works for the above, but then:
FFFF
FFFF
FXXX
XXXX
3300 is still not the best, comparing to:
1200+1200+600=3000.

“>7 then C” works for the above, but then:
XXFF
FFFF
FFFF
FXFX
2100+600x4=4500
We still have: 1200x3+600=4200.

Next level is “>8 then C”, meaning C only if all 9 fire, and it’s not best for
XXXX
XFFF
XFFX
XFXX
Here “>5 then C” gives 2100, instead of 1200+600x2=2400.

#29

Hello,

Any suggestion how to solve this puzzle?
I didn’t get how to solve it, I try so many ideas, but only the 1st test works.

Thanks in advance.

#30

Consider test case 3.
There is an area of size 3 (x:2, y :1) that contains 6 fire cells:

.XX
XX.
XX.

These could be extinguished with

  • 1 Canadair using 2100 liters of water
  • 2 Helicopters using 2400 liters of water
  • 1 Helicopter and 2 Jump Squads using 2400 liters of water
  • 6 Jumpers using 3600 liters of water

Obviously using the Canadair is the best choice.

You need to analyze the map and find areas that best fit available units.
If the area looked like:

.X.
XX.
XX.

Then Canadair would no longer be the best choice since it could be extinguished with 1 Heli and 1 Jump Squad using 1800 liters of water.

1 Like
#31

Surprisingly, this puzzle is indeed more complex than what meets the eye at first.
Thank you for listing the non-trivial arrangements that will break a naive greedy algo.

I think the term “greedy” here is misleading, as it doesn’t really define the parameters of the greediness. Is it greedy based on “cost per fire” (definitely not, as shown above). or maybe it’s greedy based on a bigger-viewport calculation (like the best value of any given 3x3 square - this won’t work either).

Given the problem parameters, it seems that the right “viewport” for a possible greedy algo is 4x4, but I think I can show that this also has some problems.

This leaves 2 straight-forward approaches for a “good enough” solution to pass this puzzle:

  1. Tailor a solution using some sort of greedy + heuristics to pass the test cases
  2. Use a basic solution using a 3x3 viewport, and take care of a special case where a heli is better than canadian inside the 3x3

I tried option (1) but didn’t manage to find the right weights, so went to option (2).
The resulting solution is straight forward, doesn’t require heuristics or magic numbers.

It does require handling of the special case where a heli (or heli + jumper) provides better cost than a Canadian. this can happen if there are 3-5 fires, and it depends on their arrangement within the 3x3. All other cases are trivial and require either a Canadian or jumpers.

It’s an interesting puzzle, albeit a bit frustrating :slight_smile:

1 Like