[Community Puzzle] Block the spreading fire!

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @Teiglin,validated by @jordan_codingame,@MathisHammel and @CodinBoss1234.
If you have any issues, feel free to ping them.

#2

Hi, I share with you my first idea which is : RANDOM CHOICE

while True:
    matrix_of_progress = []
    cooldown = int(input())  
    for i in range(height):
        for j in input().split():
            fire_progress = int(j)
            matrix_of_progress.append(fire_progress)
    
    mask = map(lambda x: x==-1, matrix_of_progress)
    indexs = [i for i, is_elligible in enumerate(mask) if is_elligible]

    if cooldown == 0 and len(indexs) > 0:
        random = randrange(len(indexs))
        cell_number = indexs[random]
        x, y = int(cell_number % width), int(cell_number / width)
        print(str(x), str(y))
    else:
        print('WAIT')

I know this is not very efficient but I like to have this kind of easy result at the beginning

Good luck :fire::fire::fire:

1 Like
#3

I’m a little bit confused about the constraints:

0 ≤ value ≤ 1000

And in the first Test-Case, the houseValue is 3700…??

#4

Indeed, thank you for this report. I don’t even know why I wrote this constraint, it should not impact players. I will remove it after the event (I prefer to edit the game as little as possible while it is “featured”).

#5

Well, surely there must be some constraint. Like, is it constrained to be representable by a 32-bit integer at least?

#6

I can write at least that the value is positive, and since I wrote that the sum of the values is below 12000, it should be enough. By the way, if there were cells with negative value, it would be funny since it would mean that we might want to “guide” the fire towards these cells :thinking: But it would be another game.

3 Likes
#7

guys i just entered and all test cases went good is it normal ???

#8

The statement says:

Note: Tests cannot fail. If a test is ended because of a timeout or a bad output, the game will compute the spreading of the remaining fire (if any) for the final score.

1 Like
#10

Awesome puzzle!
I initially thought it would be too challenging so I didn’t attempt it. I Decided to try it since it was the featured puzzle, and I really enjoyed it.
The puzzle is unique, easy to understand, and has a good variety of test cases.

Nice work!

2 Likes
#11

If the best solutions are revealed at the end of the event, doesn’t that kind of defeat the purpose of a competitive puzzle?

#12

No worries, that will not happen. Thibaud has replied on Discord, and I quote him as follows:

I’ve set the review start date as the end date so this phase shouldn’t happen and no solutions could be shared.
Not ideal and quite misleading for all users, but the only other solution I see is to cancel the event, which would be a shame

#13

Thanks for the quote!

#14

We(mostly I) could learn a LOT if the best solution is revealed. But then, it may not be fair to the winners.
I’m looking forward to the post-analysis if there’s going to be one either way.

#15

Is there no post contest analysis? I would really like to learn how to solve this optimally (or be as close as possible). I suspect this problem might be NP hard.

#16

I’d be happy to explain the general algorithm behind my solution (currently ranked 4th). I’m still somewhat new to this site so I don’t know if this is allowed or if there are any rules/guidelines I must follow. Perhaps someone can let me know. Cheers

#17

Explanation is allowed, as long as you don’t share any working code in full.

2 Likes
#18

An explanation of my algorithm (currently #4):

The most significant part of my algorithm is how I represent a candidate solution. Representing candidate solutions as a sequence of random cuts is very unlikely to yield any points or at least have an effective use of cuts. All sequences of cuts that generate some points have something in common: they disconnect section/s of the map from the fire.

Therefore I represent my candidate solutions as a set of cells on the map that I want to save (be disconnected from where the fire is). From this I can determine a few things:

  • The perimeter around the set of cells, which will become the target cells to cut.

  • The order in which the cuts must be made OR if there is no such order that can prevent the fire from reaching any of the saved cells. In which case, the solution will be discarded.

  • The total value of the cells that have been saved from the fire.

I initially used a simple hill climbing approach where I do as follows:

  • Choose a random starting point on the map (optionally weighted by value)
  • Check if there is a sequence of cuts that can be made to save that cell. If not, start again
  • While there is time left, AND the number of iterations since last improvement < max iters without improvement:
    • Choose a perimeter cell to convert to a saved cell (or with a very low probability add a random cell on the map instead. This will allow for multiple disconnected regions to be saved)
    • Check if there is a sequence of cuts that can be made to save the new set of cells. If not, don’t accept the new cell.

This approach was already quite effective. Regarding performance, I could get around 60-80k iterations (of the inner loop) for the 7th test case

The improvements that got my solution to #4:

  • I removed redundant iterations that were caused by the process of randomly selecting cells. When choosing a random cell to add, I now randomly iterate through all possible cell indices, rather than randomly generating an index over and over. This means that I only check a cell once at most, and I will check every cell before giving up with the current solution (or accepting a valid cell if found).

  • I spent the last 500ms of the initial turn and about 95ms of every future turn using Simulated Annealing to try and improve upon my current best solution. The hill climbing approach will often get stuck in a local maxima, so the goal of using SA was to get past the local maxima.

    I randomly remove saved cells, and randomly add saved cells, with adding cells having a higher probability than removing them (because more saved cells generally means better value). I only accept states that are valid. I also restart the annealing schedule every 20 or so iterations so it does not traverse too far away from the current best solution.

    My previous score on the 7th test case was almost always 7523, but with SA it is almost always 8622. On other test cases it usually only offers a small improvement or no improvement.

Feedback and questions welcome! I’m also curious to know how other players attempted this challenge.

9 Likes
#19

My solution (#6 at the end of the event)

I didn’t find a unique algorithm that works for all, so i used conditions to recognize the situation.
If tree_fire > 4*tree_cut => cut all around fire
if xMin==xMax || yMin==yMax => one dimension grid, cut next to the fire
if horizontal/vertical line with few cells to cut => cut it straight, trying diagonal when possible.
Etc…
The most difficult tests case were the two last : to find the good diagonal througth the village, and in the random grid, to find cells where cutting one tree can block the fire (because of existing cutted cells).

I admire those that found an algorithm working for all.

3 Likes
#20

My algorithm is sitting at 53K only but I am proud of it anyway.

image
image566Ă—554 46.6 KB

2 Likes
#21

i don’t know if it is just me, but one of the problem of this puzzle is the debugging process of the input (to copy it back in my IDE and study a solution via debugging).
The big maps are cut when displaying the readline() : (for example)
-2 -2 -2 -2-2 -2 -2 -2-2 -2 -2 -2-2 -2 -2 -2-2 -2 -2 -2-2 -2 -2 -2
-2 -2 -2 -2-2 -2 -2 -2-2 -2 -2 -2-2 -2 -2 -2 …
Is there a way to get all the datas ?
ty.