Recientemente ha habido una gran nevada, y mi camino de entrada necesita nieve. Si el quitanieves sobrepasa un área que ya ha nevado, entonces esa área tendrá nieve y tendrá que volver a soplar. Y, por supuesto, el quitanieves no puede comenzar en el medio del camino de entrada, debe comenzar desde mi garaje, donde está almacenado.

Más formalmente:

Su programa toma una forma estándar de entrada como una cadena o matriz multidimensional que se parece a lo siguiente:

XXXXOOOOXXXX
X          X
X          X
XXXXXXXXXXXX

Xrepresenta un área que no puede ser nevada, Orepresenta un área donde se puede desplegar el quitanieves y los espacios vacíos representan áreas donde hay nieve. Puede elegir diferentes valores si lo desea.

Su programa debe generar algo como lo siguiente:

XXXX*%OOXXXX
Xv<<<^<<<<<X
X>>>>>>>>>^X
XXXXXXXXXXXX

El quitanieves comienza en el *. El *siempre apunta al espacio que no es de garaje más cercano. El <, >, v, y ^todos representan punteros de la siguiente dirección, donde es. Apuntan al quitanieves a dónde ir. Una vez que un puntero apunta al %, el soplador ha vuelto al garaje, y toda la entrada debe estar despejada.

El quitanieves debe recorrer todo el camino de entrada. El camino del quitanieves nunca puede solaparse. No se debe dar una entrada imposible.

Como no quiero estar afuera más tiempo del necesario y no necesito pasar mucho tiempo escribiendo, el programa debe ser lo más breve posible. ¡El código más corto gana!

Casos de prueba:

Estos casos de prueba pueden tener múltiples respuestas correctas. He proporcionado posibles soluciones debajo de cada caso de prueba.

Caso de prueba 1: el que se da en el ejemplo.

Caso de prueba 2:

XOOOOOX
X     X
X     X
X     XXXXXXXX
X            X
X            X
XXXXXXXXXXXXXX

X*OOO%X
Xv>>>^X
Xv^<<<X
Xv>>>^XXXXXXXX
Xv^<<<<<<<<<<X
X>>>>>>>>>>>^X
XXXXXXXXXXXXXX

Caso de prueba 3:

XOOOOX
X    X
X    X
X  XXX
X    X
X    X
XXXXXX

XOO%*X
X>>^vX
X^v<<X
X^vXXX
X^>>vX
X^<<<X
XXXXXX

Caso de prueba 4:

XXXXXXXXXXXXX
O           X
O    X      X
O    X      X
O           X
XXXXXXXXXXXXX

XXXXXXXXXXXXX
*>>>>>>>>>>vX
Ov<v<Xv<<<<<X
Ov^v^X>>>>>vX
%<^<^<<<<<<<X
XXXXXXXXXXXXX

JavaScript (ES6), 346 310 299 298 297 296 283 bytes

f=(a,y=0,x=0)=>(a[y][x]?a[y][x]=='O'&&(a[y][x]='*',(g=w=>(w=a[y])&&w[x]&&(w[x]<'!'?g(w[x]='v',y++)||g(w[x++]='>',y--)||g(w[--x]='^',y--)||g(w[x--]='<',y++)||+(w[++x]=' '):w[x]=='O'&&!/ /.test(a)?w[x]='%':0))(y++)||g(y-=2)||g(y++,x++)||g(x-=2)||+(a[y][++x]='O'))||f(a,y,x+1):f(a,y+1))

<textarea id="tests">XXXXOOOOXXXX&#10;X          X&#10;X          X&#10;XXXXXXXXXXXX&#10;&#10;XOOOOOX&#10;X     X&#10;X     X&#10;X     XXXXXXXX&#10;X            X&#10;X            X&#10;XXXXXXXXXXXXXX&#10;&#10;XOOOOX&#10;X    X&#10;X    X&#10;X  XXX&#10;X    X&#10;X    X&#10;XXXXXX&#10;&#10;XXXXXXXXXXXXX&#10;O           X&#10;O    X      X&#10;O    X      X&#10;O           X&#10;XXXXXXXXXXXXX</textarea><br><button onclick="for(test of document.getElementById('tests').value.split('\n\n')){console.log(test);arr=test.split('\n').map(line=>line.split(''));f(arr);console.log(arr.map(line=>line.join('')).join('\n'))}">Run</button>

Muy hacky en algunos lugares, pero quería sacar el código. Entrada como una matriz de caracteres 2D, salida modificando dicha matriz.

Versión sin golf

Este es el mismo algoritmo exacto, salvo por algunos Truthy / magia Falsy con +' 'estar NaNsiendo Falsy (y algunas más), algunas variables de golf y el uso de ifs en lugar de ?:, ||y &&.

f = (a, y = 0, x = 0) => {         // main function
  if (!a[y][x])                    // check for end of line
    return f(a, y + 1);            // end of line, recursively check next
  if (a[y][x] == 'O') {            // check for valid start position
    a[y][x] = '*';                 // set the start position
    function g() {                 // pathfinder function
      if (!a[y] || !a[y][x])       // check for out of bounds
        return 0;
      if (a[y][x] == ' ') {        // check for snow
        a[y][x] = 'v';             // set current cell to 'down'
        y++;                       // move position down
        if (g()) return 1;         // see if a valid route is found from there
        y--;                       // if not, reset position and try again
        a[y][x] = '>';             // repeat for other directions
        x++;
        if (g()) return 1;
        x--;
        a[y][x] = '^';
        y--;
        if (g()) return 1;
        y++;
        a[y][x] = '<';
        x++;
        if (g()) return 1;
        x++;
        a[y][x] = ' ';             // no route found, reset cell to snow
        return 0;
      }
      if (a[y][x] == 'O'           // check for valid exit
          && !/ /.test(a)) {       // and that no snow is left
        a[y][x] = '%';             // set the exit
        return 1;
      }
    }
    y++;                           // move a cell down from the start position
    if (g()) return 1;             // see if a valid route starts there
    y -= 2;                        // repeat for other directions
    if (g()) return 1;
    y++; x++;
    if (g()) return 1;
    x -= 2;
    if (g()) return 1;
    x++;
    a[y][x] = 'O';                 // no route found, continue on
  }
  return f(a, y, x + 1);           // check the next cell
}