[Community Puzzle] Flood fill Example

Puzzles
#19

ok, thanks, i’m starting to understand the problem. I can’t see how to solve it yet but I’ll think about it and come back if I can’t.

1 Like
#20

I got it ! Thank you for all your advice.

#21

can someone explain why there’s + in (6,4) in test case 2? the 5 tower can reach (6,4) at time = 6, the 2 tower can reach (6,4) at time = 5

#....##..#.#
#.#..#..5..#
...#........
......##....
......#..#..
1...........
............
.#.2#.......
...#..3.#.#.
....#.....#.
....#.....#.
...4...#....
#22

Not sure which cell you’re referring to as (6, 4). Would you please edit your message and mark that cell using another character?

#23

I have the same question as @Null-None. Can someone explain why there’s + at the X spot in test case 2? the 5 tower can reach at time = 6, the 2 tower can reach at time = 5. The spot is marked X below

#....##..#.#
#.#..#..5..#
...#........
......##....
.....X#..#..
1...........
............
.#.2#.......
...#..3.#.#.
....#.....#.
....#.....#.
...4...#....
#24

Tower 3 also reaches that spot at time = 5.

(P.S. Not sure if Null-None is asking about that spot? X is (5, 4), not (6, 4).)

1 Like
#25

For anyone new who might still be struggling with the ‘duplicate tower names’ question, here’s a different way to think about it (which might be a good addition to the puzzle instructions):

Each tower has a unique name such as “Alderaan”, “Tatooine”, etc.
However, the map will only show the first character of each tower’s name (‘A’, ‘T’, etc.).
Although the tower names are unique, the first character might not be.
Since each tower is marked at a single location on the map, repeat instances of the same character (‘A’ and ‘A’) can be known to represent different towers (“Alderaan” and “Antares”).

3 Likes
#26

In my solution, there is a std::map<char, char> IDs (“dictionnary” in other languages ?) to give a unique incremental id to the towers, and remember which char is associated to this id.

char uniq = -1;
IDs['A'] = 'A'; // First 'A' encountred
IDs[uniq--] = 'A'; // Second 'A' encountred

When I parse the grid, chars are replaced by their unique ID.
Flood fill is computed with the unique ID.
And at the end, I use my IDs map (or dictionnary) to display the good letters.

1 Like
#27

Ok, not sure what went wrong.
My code passes all tests, but when submitted it says I failed the second validator.
I know this validators are a bit different to the tests we see in order to prevent hardcoding the solution but I did not hardcode the solution.
My code is written in Golang and I tried doing the comparisons in bytes and strings (of length 1). Both ways all tests are passed.
I also consider propagating the ‘+’ and towers with the same name (otherwise I would not pass the tests).

I would like to know what makes my code valid on all tests but invalid on one validator once submitted.

Thanks

#28

Tower ID can be any character different than ‘.’ and ‘#’. Probably you have some assumption about what the ID can be. I also failed with the 2nd validator when assumed that the ID can be only letter.

#29

Technically my code should work with anything different than ‘.’ and ‘#’, but will take another look just in case.
Thanks

#30

Are you guaranteed to have less than 256 towers?

#31

Hello, i’ve got the same problem as @MISELLO. All my tests and validator tests passed, but not the first validator. I missed something ?

#32

I don’t see anything special about the first validator. You may want to re-check your code. If you still can’t find any issues, please post here again.

#33

I hoped less than 128 ^^ but if it is the only objection, you can use a map<int, char>.

#34

I also have the issue with the second validator when all tests in the IDE work. Have you found any solution to this issue ?

#35

Hi!
I have just submited another solution and this time it passed all tests and validators.
I still have no idea what was wrong in my previous code.
Things I did differently:

  • Store the map as a matrix of bytes instead of matrix of a defined structure.
  • Have a separated matrix of data containing the time that cell was filled and from what tower.
  • Have a queue of nodes to process, instead of trying to propagate every cell.

As I said, I don’t know what caused the my first solution to fail the second validation, but I guess that having a queue was the key in my case.

Note: It is a FIFO queue. I start adding the position of the towers in the queue and every time I want to expand I add the new position to the queue. Every node of the queue contains the coordinades x & y. The time (the towers are t=0, their neighbors are t=1 and so on) and the tower index. Then I have an array of towers where I match the tower index to their symbol (symbol is what the problem calls ID).

Hope this helps you to find the issue.

#36

Hey,

I am curious about this. In my case, I noticed that I updated the cell values too early and it caused errors. So I split the update into:

  • find cells that change their value and store the expected changes in a dictionary
  • update the cells values

I think this is the equivalent of your implementation of tracking time. I think FIFO or LIFO during the update should not affect the solution. I am using a dictionary in python and there is no order for elements, and it works.

#37

Thanks for your answer.

I have a list of nodes to process and propagate each node in that list. Processed nodes are then removed from it and the nodes where the propagation was successful are then added to it for the next iteration of my loop.
The iteration number of my loop acts as the distance from a source to another node.

Thus I don’t think the run time is the issue in my case, and I find it hard to find a test case where my algorithm doesn’t work. Modifying my “map” to not be a data structure should not change the behavior of the algorithm.

#38

This sentence made me thing of something.
If you have a unique queue or list where you remove processed noded and add new nodes that need to be propagated probably the condition of the loop is while the queue/list is not empty keep going.
Said that, each iteration would corresponds to a node and not the distance from a source. I think that knowing the time or distance is important because if two sources reach the same spot at the same time (or have the same distance from source) we should print a ‘+’ there.
I solved this having a field called “t” in my node. This “t” is 0 at the tower and every time it propagates I increase it.

Not sure if this helps because you already said your code passes all tests, so you probably have already solved that even by other means.

If your code keeps failing at the validator I can only suggest to keep the idea (because it is good if it passes the tests) and try another approach as I did.

Good luck!