introduction

Vous êtes un biologiste qui étudie les schémas de mouvement des bactéries. Votre équipe de recherche en a un tas dans une boîte de Pétri, et vous enregistrez leur activité. Malheureusement, vous êtes sérieusement sous-financé et vous ne pouvez pas vous permettre une caméra vidéo, vous prenez donc simplement une photo du plat à intervalles réguliers. Votre tâche consiste à créer un programme qui retrace les mouvements des germes à partir de ces images.

Contribution

Vos entrées sont deux tableaux 2D de caractères dans n'importe quel format raisonnable, représentant des images consécutives de la boîte de Pétri. Dans les deux tableaux, le personnage .représente un espace vide et Oreprésente un germe (vous pouvez choisir deux caractères distincts si vous le souhaitez). En outre, le tableau "après" est obtenu à partir du tableau "avant" en déplaçant certains germes d'un pas dans l'une des quatre directions cardinales; en particulier, les tableaux ont la même forme. Les germes se déplacent simultanément, de sorte que l'un d'eux peut se déplacer vers un espace qui contenait déjà un autre germe, s'il s'éloigne. Il est garanti que les bordures du tableau "avant" ne contiennent que des espaces vides et qu'il y a au moins un germe. Ainsi, ce qui suit est une paire d'entrées valide:

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

Production

Votre sortie est un seul tableau 2D de caractères dans le même format que les entrées. Il est obtenu à partir du tableau «avant» en remplaçant les germes qui se sont déplacés par l'un des >^<v, selon la direction du mouvement (vous pouvez également utiliser 4 caractères distincts ici). Il peut y avoir plusieurs sorties possibles, mais vous ne devez en donner qu'une seule. Dans l'exemple ci-dessus, une sortie correcte possible est

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

Les mouvements inutiles sont autorisés dans la sortie et les germes peuvent changer de place, ce qui suit est également valide:

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

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.

Je suis intéressé par des algorithmes relativement efficaces, mais je ne veux pas interdire complètement le forçage brut. Pour cette raison, il y a un bonus de -75% pour résoudre le dernier cas de test dans les 10 minutes sur un processeur moderne (je ne peux pas tester la plupart des solutions, donc je vais juste vous faire confiance ici). Avertissement: je sais qu'il existe un algorithme rapide (recherche de "problème de chemins disjoints"), mais je ne l'ai pas implémenté moi-même.

Cas de test supplémentaires

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

Octave, 494 496 octets - bonus de 372 octets = 124 octets

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

Il y a encore beaucoup de golf à faire sur cette réponse, mais je voulais obtenir l'explication non golfée.

J'ai vu cela comme un problème de satisfaction de contrainte, alors j'ai choisi mon heuristique de recherche locale préférée, Min-conflits . L'idée est, étant donné un placement de départ avec chaque germe dans une destination accessible, de sélectionner un germe aléatoire qui occupe la même cellule de destination qu'un ou plusieurs autres germes et de le déplacer vers une cellule valide qui contient déjà un minimum d'autres germes. Répétez autant de fois que nécessaire jusqu'à ce que le placement corresponde à l'objectif.

Fait intéressant, cet algorithme n'est pas garanti de se terminer (si l'objectif est inaccessible, il continuera indéfiniment, par exemple), mais s'il se termine, il est garanti de produire une solution valide.

Voici le code:

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

Sortie pour le dernier cas de test:

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

Le temps moyen écoulé était inférieur à 9 secondes 1 seconde * sur un Core i5 de 5 ans, éligible au bonus.

J'essaie de faire fonctionner cela sur ideone, mais j'ai ce que je crois être des problèmes de portée avec la façon dont il gère les fonctions imbriquées. (Voici le lien ideone qui ne fonctionne pas pour référence: http://ideone.com/mQSwgZ )
Le code sur ideone fonctionne maintenant. J'ai dû forcer toutes les variables à global, ce qui n'était pas nécessaire de l'exécuter localement.

* J'avais une note dans ma version non golfée qu'une des étapes était inefficace, donc je l'ai essayée pour voir si je pouvais accélérer l'exécution et pour 2 octets supplémentaires le temps d'exécution est maintenant réduit à moins d'une seconde. Le code et l'exemple de sortie ont été mis à jour et l'entrée sur ideone a été changée pour le dernier cas de test.

Python, 1171 octets - 878,25 octets bonus = 292,75 octets

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

Lien Ideone: http://ideone.com/0Ylmwq

Cela prend de 1 à 8 secondes en moyenne sur le dernier test élémentaire, ce qui donne droit au bonus.

Ceci est ma première soumission de code-golf, donc ce n'est probablement pas le programme le mieux joué. Néanmoins, ce fut un défi intéressant et je l'ai beaucoup apprécié. @Beaker mérite une mention pour me rappeler que les recherches basées sur l'heuristique sont une chose. Avant de poster sa solution et de m'inspirer pour refaire la mienne, ma recherche par force brute était trop longue pour être éligible au bonus sur le dernier cas de test (c'était de l'ordre de 69! Itérations, qui est un nombre à 99 chiffres .. .).

Je ne voulais pas copier directement la solution de Beaker, j'ai donc décidé d'utiliser le recuit simulé pour mon heuristique de recherche. Il semble plus lent que min-conflict pour ce problème (probablement parce que c'est un algorithme d'optimisation plutôt que de satisfaction de contraintes), mais il est toujours bien dans la limite des 10 minutes. Il avait également l'avantage d'être assez petit, au niveau du code. J'ai dépensé beaucoup plus d'octets pour transformer le problème que pour trouver une solution.

Explication

Ma solution est probablement assez inefficace au niveau des octets, mais j'ai eu du mal à conceptualiser comment résoudre le problème tel quel et j'ai donc dû le transformer en un problème différent qui était plus facile à comprendre pour moi. J'ai réalisé qu'il y a quatre possibilités pour chaque cellule sur la grille:

• Il n'avait pas de germe avant ou après, ce qui signifie que nous pouvons l'ignorer
• Il y avait un germe avant mais pas après, ce qui signifie que nous devons trouver un mouvement pour lui.
• Il n'avait pas de germe avant mais un après, ce qui signifie également que nous devons trouver un mouvement pour lui.
• Il y avait un germe avant et après, ce qui signifie que nous devrons peut-être trouver un mouvement pour cela, mais là encore peut-être pas.

Après avoir décomposé les données dans ces classes, j'ai pu transformer davantage le problème. Il était immédiatement évident pour moi que je devais trouver un moyen de fournir un germe de l'ensemble «avant mais pas après» à une cellule de l'ensemble «après mais pas avant». De plus, les germes ne peuvent se déplacer que d'un espace, donc la seule façon pour eux d'affecter des cellules plus éloignées est de "pousser" un chemin ininterrompu de germes dans cette cellule. Cela signifiait que le problème devenait de trouver X chemins disjoints au sommet sur un graphique, où chaque cellule avec un germe était un sommet dans ledit graphique, et les bords représentaient des cellules adjacentes.

J'ai résolu ce problème en construisant d'abord le graphique expliqué ci-dessus. J'ai ensuite énuméré chaque chemin possible depuis chaque cellule dans Avant et chaque cellule dans Après, puis assigné au hasard chaque cellule dans Avant l'un de ses chemins possibles. Enfin, j'ai utilisé un recuit simulé pour muter semi-aléatoirement la solution potentielle jusqu'à ce que je trouve finalement une solution qui n'a aucun conflit pour aucun des chemins.

Version annotée

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