Introdução

Você é um biólogo que estuda os padrões de movimento das bactérias. Sua equipe de pesquisa tem vários deles em uma placa de Petri e você está registrando a atividade deles. Infelizmente, você está seriamente subfinanciado e não pode pagar por uma câmera de vídeo; portanto, basta tirar uma foto do prato em intervalos regulares. Sua tarefa é criar um programa que rastreie os movimentos dos germes a partir dessas figuras.

Entrada

Suas entradas são duas matrizes 2D de caracteres em qualquer formato razoável, representando imagens consecutivas da placa de Petri. Nas duas matrizes, o caractere .representa espaço vazio e Orepresenta um germe (você pode escolher dois caracteres distintos, se desejar). Além disso, a matriz "depois" é obtida da matriz "antes" movendo alguns germes um passo em uma das quatro direções cardinais; em particular, as matrizes têm a mesma forma. Os germes se movem simultaneamente, portanto, um deles pode se mover para um espaço que já continha outro germe, se sair do caminho. É garantido que as bordas da matriz "before" contenham apenas espaços vazios e que haja pelo menos um germe. Assim, o seguinte é um par válido de entradas:

Before  After
......  ......
.O..O.  ....O.
.OO.O.  .OO.O.
......  ..O...

Saída

Sua saída é uma única matriz 2D de caracteres no mesmo formato que as entradas. É obtido da matriz "before" substituindo os germes que foram movidos por um dos >^<v, dependendo da direção do movimento (você também pode usar 4 caracteres distintos aqui). Pode haver várias saídas possíveis, mas você deve fornecer apenas uma delas. No exemplo acima, uma saída correta possível é

......
.v..O.
.>v.O.
......

Movimento desnecessário é permitido na saída e germes podem trocar de lugar, portanto o seguinte também é válido:

......
.v..v.
.>v.^.
......

Regras e pontuação

Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas.

Estou interessado em algoritmos relativamente eficientes, mas não quero banir totalmente a força bruta. Por esse motivo, há um bônus de -75% para resolver o último caso de teste em 10 minutos em uma CPU moderna (não consigo testar a maioria das soluções, por isso confio em você aqui). Isenção de responsabilidade: eu sei que existe um algoritmo rápido (procure por "problema de caminhos disjuntos"), mas não o implementei.

Casos de teste adicionais

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..
..............................

Oitava, 494 496 bytes - bônus de 372 bytes = 124 bytes

function o=G(b,a)
y='.O<^v>';s=(b>46)+0;t=a>46;v=t;f=s;t(:,2:end,2)=t(:,1:end-1);t(2:end,:,3)=t(1:end-1,:,1);t(1:end-1,:,4)=t(2:end,:,1);t(:,1:end-1,5)=t(:,2:end,1);t=reshape(t,[],5);m=size(s,1);p=[0 -m -1 1 m];
function z(n)
f(n+p(s(n)))--;q=find(t(n,:));w=n+p(q);d=min(f(w));q=q(f(w)==d);j=randi(numel(q));s(n)=q(j);f(n+p(q(j)))++;end
for g=find(s)' z(g);end
while any((f~=v)(:)) L=find(s);k=zeros(size(s));for h=L' k(h)=f(h+p(s(h)));end;c=find(k>1);g=c(randi(numel(c)));z(g);end
o = y(s+1);end

Ainda há muito o que fazer nesta resposta, mas eu queria ter a explicação não-destruída.

Eu vi isso como um problema de satisfação com restrições, então segui minha heurística de pesquisa local favorita, Min-conflitos . A ideia é, dada uma colocação inicial com cada germe em um destino acessível, selecione um germe aleatório que ocupe a mesma célula de destino que um ou mais outros germes e mova-o para uma célula válida que já tenha um mínimo de outros germes. Repita conforme necessário até que o canal corresponda à meta.

Curiosamente, não é garantido que esse algoritmo seja finalizado (se a meta for inacessível, ela continuará indefinidamente, por exemplo), mas se for finalizada, será garantida a produção de uma solução válida.

Aqui está o código:

function output = germs(before, after)

%before = ['......';'.O..O.';'.OO.O.';'......'];
%after = ['......';'....O.';'.OO.O.';'..O...'];

symbs = '.O<^v>';
start = (before > 46) + 0;                   %should be called current_board
target = after > 46;                         %destinations on current cell == O
goal = target;
conflicts = start;
target(:, 2:end,2) = target(:, 1:end-1);     %destinations on cell to left
target(2:end, :,3) = target(1:end-1, :,1);   %destinations on cell above
target(1:end-1, :,4) = target(2:end, :,1);   %destinations on cell below
target(:, 1:end-1,5) = target(:, 2:end,1);   %destinations on cell to right
target=reshape(target,[],5);
m = size(start,1);                           %number of rows = offset to previous/next column
offsets = [0 -m -1 1 m];                     %offsets of neighbors from current index


function moveGerm(n)
   conflicts(n+offsets(start(n)))--;         %take germ off board
   move = find(target(n, :));                %get valid moves for this germ
   neighbors = n + offsets(move);            %valid neighbors = current position + offsets
   minVal = min(conflicts(neighbors));       %minimum number of conflicts for valid moves
   move = move(conflicts(neighbors)==minVal);
   mi = randi(numel(move));                  %choose a random move with minimum conflicts
   start(n) = move(mi);                      %add move type to board
   conflicts(n + offsets(move(mi)))++;       %add a conflict on the cell we move to
end

% Generate an initial placement
for g = find(start)'
   moveGerm(g);                              %make sure all germs are moved to valid cells
end

% Repeat until board matches goal
while any((conflicts ~= goal)(:))
   germList = find(start);                   %list of all our germs
   cost = zeros(size(start));                %calculate conflicts for each germ
   for h = germList'
      cost(h) = conflicts(h + offsets(start(h)));
   end
   conflicted = find(cost > 1);              %find those germs that occupy the same cell as another
   g = conflicted(randi(numel(conflicted))); %choose a random germ to move
   moveGerm(g);
end

output = symbs(start+1);                     %use moves as indices into symbol array for output

end

Saída para o último caso de teste:

>> gtest
ans =

..............................
.OO>.O.v.....>.....>.v.O..v...
..>^O.v...>..^>..v..O.v.......
.....v......>..>.....O....O...
.O.<^<OO......>...O..O....v...
.<O..O..v<.O..^<..O..>....>...
..<.^.v......OO.O^..<..<O.....
..^....v..v.Ov...>>>.^OO...O..
.....<..OO......O..O...Ov.<<..
........>..O........O^.v.>....
..^.....OO.....OO.OO.......O..
.^.....^.O..O>.vO....v......O.
..<..Ov^^..O....OO..........O.
.O..O...>.v....O..^....^...OO.
....O...<v..O.......<.^..v<...
........O.O....O.v....O.......
.OO.......<.OO..O.......O..O..
....O....O.<.O...O^<..O.v.OO..
.O^..<<...O.>.v.>.>...<O...v..
..............................

Elapsed time is 0.681691 seconds.

O tempo médio decorrido foi inferior a 9 segundos 1 segundo * em um Core i5 de 5 anos, qualificado para o bônus.

Estou tentando fazer isso funcionar com ideone, mas estou tendo o que acredito ser um escopo de problemas com a maneira como ele lida com funções aninhadas. (Aqui está o link ideone que não funciona) para referência: http://ideone.com/mQSwgZ )
O código da ideone está funcionando agora. Eu tive que forçar todas as variáveis ​​para global, o que era desnecessário executando localmente.

* Eu tinha uma nota na minha versão não destruída de que uma das etapas era ineficiente, então tentei ver se conseguia acelerar a execução e, para 2 bytes adicionais, o tempo de execução agora é de menos de um segundo. A saída de código e amostra foi atualizada e a entrada no ideone foi alterada para o último caso de teste.

Python, 1171 bytes - bônus de 878,25 bytes = 292,75 bytes

from itertools import *;from random import *;R=range;L=len;O=choice;G='O'
def A(a,b):a.append(b)
def D(y,z):
 a=[];b=[];c=[]
 for i in R(L(y)):
  A(c,[])
  for j in R(L(y[0])):
   k=[(i,j),y[i][j]==G,z[i][j]==G,[],0];A(c[i],k)
   for l,m in [(0,1),(1,0)]:
    try:
     n=c[i-l][j-m]
     if k[2]&n[1]:A(n[3],k)
     if k[1]&n[2]:A(k[3],n)
    except:pass
   if k[1]&~k[2]:A(a,k)
   elif k[2]&~k[1]:A(b,k)
 d={}
 for i in a:
  j=[[i]]
  while j:
   k=j.pop();l=[e[0] for e in k]
   while True:
    m=k[-1];n=[o for o in m[3] if o[0] not in l]
    if not n:
     if m in b:A(d.setdefault(i[0],[]),k)
     break
    for o in n[1:]:p=k[:];A(p,o);A(j,p)
    A(k,n[0]);A(l,n[0][0])
 e={}
 for i in a:e[i[0]]=O(d[i[0]])
 def E():return sum(any(k in j for k in i) for i,j in combinations(e.values(),2))
 f=E()
 for i in count():
  t=3**-i/L(a);j=O(a);k=e[j[0]];e[j[0]]=O(d[j[0]]);l=E()
  if not l:break
  else:
   if l>f and random()>t:e[j[0]]=k
   else:f=l
 for i in e.values():
  for j in R(L(i)-1):i[j][4]=i[j+1]
 for i in c:
  for j in R(L(i)):
   k=i[j]
   if 1&~k[1]:i[j]='.'
   elif not k[4]:i[j]=G
   else:l,m=k[0];n,o=k[4][0];i[j]='v>^<'[abs((l-n+1)+2*(m-o))]
 return c

Link da Ideone: http://ideone.com/0Ylmwq

Leva de 1 a 8 segundos no último caso de teste, em média, qualificando-se para o bônus.

Este é o meu primeiro envio de código de golfe, portanto, provavelmente não é o programa com o melhor golfe por aí. No entanto, foi um desafio interessante e eu gostei bastante. O @Beaker merece uma menção por me lembrar que as pesquisas baseadas em heurísticas são uma coisa. Antes de ele postar sua solução e me inspirar a refazer a minha, minha pesquisa de força bruta era muito longa para se qualificar para o bônus no último caso de teste (era da ordem de 69! Iterações, que é um número de 99 dígitos. .).

Como não queria copiar diretamente a solução da Beaker, decidi usar o recozimento simulado para a heurística da minha pesquisa. Parece mais lento que o conflito mínimo para esse problema (provavelmente porque é um algoritmo de otimização, e não de satisfação com restrições), mas ainda está bem dentro da marca de 10 minutos. Também teve o benefício de ser bastante pequeno, em termos de código. Gastei muito mais bytes em transformar o problema do que em encontrar uma solução para ele.

Explicação

Minha solução é provavelmente ineficiente em termos de bytes, mas tive problemas para conceituar como resolver o problema como está e, portanto, acabei tendo que transformá-lo em um problema diferente que era mais fácil para mim entender. Percebi que existem quatro possibilidades para cada célula na grade:

• Não tinha germe antes ou depois, o que significa que podemos ignorá-lo
• Tinha um germe antes, mas não depois, o que significa que temos que encontrar um movimento para isso.
• Ele não tinha germe antes, mas um depois, o que também significa que precisamos encontrar um movimento para isso.
• Tinha um germe antes e depois, o que significa que talvez precisássemos encontrar um movimento para isso, mas talvez não.

Depois de decompor os dados nessas classes, consegui transformar ainda mais o problema. Foi imediatamente óbvio para mim que eu tinha que encontrar uma maneira de fornecer um germe do conjunto "antes, mas não depois" para uma célula no conjunto "depois, mas não antes". Além disso, os germes podem mover apenas um espaço; portanto, a única maneira de afetar as células mais distantes é "empurrando" um caminho ininterrupto de germes para dentro dessa célula. Isso significava que o problema era encontrar caminhos X separados por vértices em um gráfico, onde cada célula com um germe era um vértice no referido gráfico, e as arestas representavam células adjacentes.

Eu resolvi esse problema que, construindo primeiro o gráfico explicado acima. Enumerei todos os caminhos possíveis de cada célula no Antes e de cada célula no Depois, depois designei aleatoriamente cada célula no Antes de um de seus caminhos possíveis. Por fim, usei o recozimento simulado para alterar a solução potencial de forma semi-aleatória, até encontrar uma solução que não tem conflitos para nenhum dos caminhos.

Versão anotada

from itertools import *;from random import *;

# redefine some built-in functions to be shorter
R=range;L=len;O=choice;G='O'
def A(a,b):a.append(b)

# The function itself.  Input is in the form of two 2d arrays of characters, one each for before and after.
def D(y,z):
 # Declare the Before-but-not-after set, the After-but-not-before set, and a temp cell array
 # (the cells are temporarily stored in a 2d array because I need to be able to locate neighbors)
 a=[];b=[];c=[]

 # Build the graph
 for i in R(L(y)):
  # Append a row to the 2d temp array
  A(c,[])

  for j in R(L(y[0])):
   # Define the interesting information about the cell, then add it to the temp array
   # The cell looks like this: [position, does it have a germ before?, does it have a germ after?, list of neighbors with germs, final move]
   k=[(i,j),y[i][j]==G,z[i][j]==G,[],0];A(c[i],k)
   for l,m in [(0,1),(1,0)]:
    # Fill up the neighbors by checking the above and left cell, then mutually assigning edges
    try:
     n=c[i-l][j-m]
     if k[2]&n[1]:A(n[3],k)
     if k[1]&n[2]:A(k[3],n)
    except:pass

   # Decide if it belongs in the Before or After set
   if k[1]&~k[2]:A(a,k)
   elif k[2]&~k[1]:A(b,k)

 # For each cell in the before set, define ALL possible paths from it (this is a big number of paths if the grid is dense with germs)
 # This uses a bastard form of depth-first search where different paths can cross each other, but no path will cross itself
 d={}
 for i in a:
  j=[[i]]  # Define the initial stack of incomplete paths as the starting node.
  while j:
   # While the stack is not empty, pop an incomplete path of the stack and finish it
   k=j.pop();l=[e[0] for e in k]
   while True:
    # Set the list of next possible moves to the neighbors of the current cell,
    # ignoring any that are already in the current path.
    m=k[-1];n=[o for o in m[3] if o[0] not in l]

    # If there are no more moves, save the path if it ends in an After cell and break the loop
    if not n:
     if m in b:A(d.setdefault(i[0],[]),k)
     break

    # Otherwise, set the next move in this path to be the first move,
    # then split off new paths and add them to the stack for every other move
    for o in n[1:]:p=k[:];A(p,o);A(j,p)
    A(k,n[0]);A(l,n[0][0])

 # Perform simulated annealing to calculate the solution
 e={}
 for i in a:e[i[0]]=O(d[i[0]])  # Randomly assign paths for the first potential solution

 # Define a function for calculating the number of conflicts between all paths, then do the initial calculation for the initial potential solution
 def E():return sum(any(k in j for k in i) for i,j in combinations(e.values(),2))
 f=E()

 # Do the annealing
 for i in count():
  # The "temperature" for simulated annealing is calculated as 3^-i/len(Before set).
  # 3 was chosen as an integer approximation of e, and the function e^(-i/len) itself was chosen because
  # it exponentially decays, and does so slower for larger problem sets
  t=3**-i/L(a)

  j=O(a)              # Pick a random Before cell to change
  k=e[j[0]]           # Save it's current path
  e[j[0]]=O(d[j[0]])  # Replace the current path with a new one, randomly chosen
  l=E()               # Recalculate the number of conflicts

  if not l:break  # If there are no conflicts, we have a valid solution and can terminate
  else:           # Otherwise check the temperature to see if we keep the new move
   if l>f and random()>t:e[j[0]]=k  # Always keep the move if it's better, and undo it with probability 1 - T if it's worse
   else:f=l                         # If we don't undo, remember the new conflict count

 # Set each of the cells' final moves based on the paths
 for i in e.values():
  for j in R(L(i)-1):i[j][4]=i[j+1]

 # Build the output in the form of a 2d array of characters
 # Reuse the temp 2d array from step since its the right size
 for i in c:
  for j in R(L(i)):
   k=i[j]
   # Cells that are empty in the before array are always empty in the output
   if 1&~k[1]:i[j]='.'
   # Cells that aren't empty and don't have a move are always germs in the output
   elif not k[4]:i[j]=G
   # Otherwise draw the move
   else:l,m=k[0];n,o=k[4][0];i[j]='v>^<'[abs((l-n+1)+2*(m-o))]
 return c