21
Introduction
You are a biologist studying the movement patterns of bacteria. Your research team has a bunch of them in a petri dish, and you are recording their activity. Unfortunately, you are seriously underfunded, and can't afford a video camera, so you just take a picture of the dish at regular intervals. Your task is to make a program that traces the movements of the germs from these pictures.
Input
Your inputs are two 2D arrays of characters in any reasonable format, representing consecutive pictures of the petri dish.
In both arrays, the character .
represents empty space, and O
represents a germ (you can choose any two distinct characters if you want).
Also, the "after" array is obtained from the "before" array by moving some germs one step in one of the four cardinal directions; in particular, the arrays have the same shape.
The germs move simultaneously, so one of them may move to a space that already contained another germ, if it moves out of the way.
It is guaranteed that the borders of the "before" array contain only empty spaces, and that there is at least one germ.
Thus, the following is a valid pair of inputs:
Before After
...... ......
.O..O. ....O.
.OO.O. .OO.O.
...... ..O...
Output
Your output is a single 2D array of characters in the same format as the inputs.
It is obtained from the "before" array by replacing those germs that have moved with one of >^<v
, depending on the direction of movement (you can also use any 4 distinct characters here).
There may be several possible outputs, but you shall give only one of them.
In the above example, one possible correct output is
......
.v..O.
.>v.O.
......
Unnecessary movement is allowed in the output and germs can swap places, so the following is also valid:
......
.v..v.
.>v.^.
......
Rules and scoring
You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.
I'm interested in relatively efficient algorithms, but I don't want to ban brute forcing entirely. For this reason, there's a bonus of -75% for solving the last test case within 10 minutes on a modern CPU (I'm unable to test most solutions, so I'll just trust you here). Disclaimer: I know that a fast algorithm exists (search for "disjoint paths problem"), but I haven't implemented it myself.
Additional test cases
Before
......
.O..O.
..OO..
......
After
......
..O...
...OO.
..O...
Possible output
......
.>..v.
..vO..
......
Before
.......
.OOOOO.
.O..OO.
.OO..O.
.OOOOO.
.......
After
.......
..OOOOO
.O...O.
.O...O.
.OOOOOO
....O..
Possible output
.......
.>>>>>.
.O..>v.
.Ov..v.
.O>>v>.
.......
Before
..........
.OOO..OOO.
.OOOOOOOO.
.OOO..OOO.
..........
After
..O.......
.OOO..O.O.
..OOOOOOOO
.O.O..OOO.
.......O..
Possible output
..........
.>^O..O>v.
.^O>>>vO>.
.O>^..>vO.
..........
Before
............
.OO..OOOOOO.
.OO......OO.
...OOOOOO...
.O.OOOOOO.O.
...OOOOOO...
.OOOOOOOOOO.
............
After
..........O.
.OO..OOOOO..
.O...O...O..
.O.OOOOOOO..
.O.OOOOOO..O
...OO..OO...
....OOOOOOOO
.OOO........
Possible output
............
.OO..v<<<<^.
.v<......^<.
...OOO>>>...
.O.OOO^OO.>.
...OOv^OO...
.vvvO>>>>>>.
............
Before
................
.OOOOOO.OOOOOOO.
..OO..OOOOOOOOO.
.OOO..OOOO..OOO.
..OOOOOOOO..OOO.
.OOOOOOOOOOOOOO.
................
After
................
..OOOOO.OOOOOOOO
..OO..OOOOOOOOO.
..OO..OOOO..OOOO
..OOOOOOOO..OOO.
..OOOOOOOOOOOOOO
................
Possible output
................
.>>>>>v.>>>>>>>.
..OO..>>^>>>>>v.
.>>v..OOO^..OO>.
..O>>>>>>^..OOO.
.>>>>>>>>>>>>>>.
................
Before
..............................
.OOO.O.O.....O.....O.O.O..O...
..OOO.O...O..OO..O..O.O.......
.....O......O..O.....O....O...
.O.OOOOO......O...O..O....O...
.OO..O..OO.O..OO..O..O....O...
..O.O.O......OO.OO..O..OO.....
..O....O..O.OO...OOO.OOO...O..
.....O..OO......O..O...OO.OO..
........O..O........OO.O.O....
..O.....OO.....OO.OO.......O..
.O.....O.O..OO.OO....O......O.
..O..OOOO..O....OO..........O.
.O..O...O.O....O..O....O...OO.
....O...OO..O.......O.O..OO...
........O.O....O.O....O.......
.OO.......O.OO..O.......O..O..
....O....O.O.O...OOO..O.O.OO..
.OO..OO...O.O.O.O.O...OO...O..
..............................
After
..............................
.OOOOO.......OO.....O..O......
...OO..O...O...O....OO....O...
....O.O......O..OO...OO...O...
.OO.OOOO......OO..O..O........
O.O.OO..O..O..O..OO...O...OO..
.OO.....O....OO.O..O.OO.O.....
......O.....O.....OOO.OO...O..
....O..OOOO..O..O..O.O.O.OO...
..O......O.O........O...O.O...
.O.....OOO.....OO.OO...O...O..
.......OOO..O.O.O...........O.
.O...O.....O...OOOO..O.O....O.
.O..O.O..O.....O......O....OO.
....O..O..O.O......O.....O....
........OOO....O......O..O....
.OO......O..OO..OOO.....O..O..
..O.O....OO..O...OO...O...OO..
.O..OO....O..O...O.O.O.OO.....
..............O............O..
Possible output
..............................
.OOO.O.v.....>.....>.v.O..v...
..>>^.v...>..^>..v..O.v.......
.....<......>..>.....O....O...
.O.<O><O......O...O..O....v...
.<O..O..v<.O..O^..O..>....>...
..<.^.v......OO.O^..>..<O.....
..^....v..v.Ov...>>^.<OO...O..
.....<..OO......O..O...Ov.v<..
........>..O........O^.v.^....
..^.....Ov.....OO.OO.......O..
.^.....^.^..O>.vO....v......O.
..<..Ov^^..O....><..........O.
.O..O...>.v....O..^....^...OO.
....O...<v..O.......<.^..v<...
........O.O....O.v....O.......
.OO.......<.Ov..O.......O..O..
....O....O.<.^...O^v..O.v.OO..
.O^..<<...O.>.v.>.^...<O...v..
..............................
Just to be sure, germs can only move by one or zero cells, right? – Domino – 2015-10-28T16:14:57.570
@JacqueGoupil Yes, that's correct. Each of
>^<v
corresponds to a movement of exactly one step in the respective direction. – Zgarb – 2015-10-28T16:20:08.873I didn't try solving it yet, but here's a tool to build more test cases :) https://jsfiddle.net/xd2xns64/embedded/result/
– Domino – 2015-10-28T17:43:25.830Oh, careful, there's a chance the script will loop forever if it tries to move all cells against an edge but then the edge cells have nowhere to go. – Domino – 2015-10-28T19:05:15.123