Sellos científicos varados sobre un iceberg

Introducción

Una familia de focas está varada sobre un iceberg en el Círculo Polar Ártico. Hay un transmisor de radio ubicado en el iceberg que los sellos pueden usar para pedir ayuda. Sin embargo, solo el sello de papá sabe cómo operar el transmisor de radio. Y lo que es peor, el hielo es muy resbaladizo en esta época del año, por lo que los sellos se deslizarán sin control hasta que lleguen a otro sello o se salgan del borde del iceberg, lo que hace que sea muy difícil para el sello papá alcanzar el transmisor de radio. Afortunadamente, uno de los sellos es un científico de la computación, por lo que decide escribir un programa para descubrir cómo maniobrar el sello de papá al transmisor de radio. Como no hay mucho espacio en el hielo para escribir un programa, ella decide hacer que el programa use la menor cantidad de bytes posible.

Descripción de entrada

El programa del sello recibirá información de STDIN, argumentos de línea de comando o funciones de entrada del usuario (como raw_input()). No se puede preinicializar en una variable (por ejemplo, "Este programa espera la entrada en una variable x").

La primera línea de la entrada consta de dos enteros separados por comas en la forma

A,B

A continuación hay Blíneas que consisten en Acaracteres cada una. Cada línea solo puede contener caracteres de los siguientes:

.: El frío, el frío, el océano. El mapa siempre tendrá esto como borde.
#: Una parte del iceberg.
a... z: Un sello que no es el sello de papá en el iceberg.
D: El sello de papá en el iceberg.
*: El transmisor de radio.

(Tenga en cuenta que el sello de papá siempre se anota con una mayúscula D. Una minúscula des simplemente un sello normal).

Descripción de salida

De acuerdo con las siguientes reglas con respecto a cómo se pueden mover los sellos, emite una lista de instrucciones para los sellos sobre cómo deben moverse para llevar el sello de papá al transmisor de radio.

Regla: todos los sellos pueden moverse hacia arriba ( U), hacia abajo ( D), hacia la izquierda ( L) y hacia la derecha ( R). No pueden deslizarse en diagonal.
Regla: Al moverse, un sello continuará moviéndose en la misma dirección hasta que choque con otro sello o caiga al mar.
1. Si un sello choca con otro sello, dejará de moverse. El sello con el que chocó no se moverá.
2. Si un sello cae al mar, se ahogará y desaparecerá del mapa. Es decir, no actúa como un colisionador para otros sellos y no se puede mover de nuevo.
Regla: dos sellos no se pueden mover al mismo tiempo, tampoco se puede mover un sello mientras otro se mueve. El siguiente sello solo se puede mover una vez que el sello anterior haya dejado de moverse.
Regla: no hay restricción con respecto a mover un sello varias veces, o el número de sellos que se ahogan.
Regla: Una solución correcta tendrá el sello papá finales en el transmisor de radio. El sello de papá no puede simplemente pasar el transmisor mientras se desliza.

La salida constará de varias líneas, cada una en forma

A,B

¿Dónde Aestá el sello de moverse ( Dpara el sello papá, a... zpara los demás), y Bes la dirección para mover el sello (o bien U, D, L, o R). Tenga en cuenta que no necesita encontrar la ruta más corta. Cualquier ruta que lleve al sello de papá a la meta es un resultado aceptable.

Ejemplo de entradas y salidas

Entrada:

25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................

Salida:

D,R

Entrada:

9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........

Salida (una salida posible de muchas):

m,R
b,L
D,U
D,R
D,D
D,L

Entrada:

26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................

Salida (una salida posible de muchas):

v,D
D,L

Si tiene alguna otra pregunta, por favor pregunte en los comentarios.

code-golf Ajenjo
fuente

¿Todas las entradas tendrán una solución válida? Si no, ¿cuál es el resultado / comportamiento esperado?

Geobits

@Geobits Todas las entradas tendrán una solución válida. Las entradas sin soluciones se consideran inválidas y su programa puede hacer lo que sea con ellas.

Absenta

¿Está permitido finalizar el programa lanzando una excepción?

DLosc

¿Qué sucede si un sello que no es de papá golpea el transmisor de radio? ¿Se detendrá o se moverá a través de él?

Reto Koradi

Eso invalida mi solución. :(

DLosc

Respuestas:

Python 3, 520 bytes

R=range
g=[list(input())for i in R(int(input().split(',')[1]))]
f=set(sum(g,[]))-set(".#*")
L=8
def P(p,g):
 if len(p)>L:return
 for s in f:
  c=sum(y.index(s)for y in g if s in y)
  if c<1:continue
  r,=[n for n in R(len(g))if s in g[n]]
  for d in R(4):
   m=p+s+",%s\n"%"LURD"[d];G=[y[:]for y in g];o="#";i,j=I,J=r,c
   while"#"==o:G[i][j]="#";G[I][J]=s;i,j=I,J;I,J=i+d%2*(d-2),j+(~d%-2&d-1);o=G[I][J]
   if"."==o:G[i][j]="#"
   if"D"==s:
    if"."==o:continue
    if"*"==o:print(m);1/0
   P(m,G)
while 1:P("",g);L+=4

Puedo hacer una explicación más detallada más adelante si la gente lo desea, pero básicamente esto ejecuta una búsqueda profunda con profundización iterativa en el espacio de estado de posibles movimientos. Si un movimiento hace que el sello de papá se caiga, se rechaza inmediatamente. Si el papá termina al lado del transmisor, se imprime la secuencia de movimientos y el programa se divide por cero para forzar una salida.

Puedo hacer que el código se ejecute significativamente más rápido agregando if G!=g:al comienzo de la penúltima línea, por 8 bytes adicionales; esto rechaza los movimientos que no cambian nada, como k,Len el primer caso de prueba.

El tiempo de ejecución varía notablemente de una ejecución a la siguiente, incluso con la misma entrada, evidentemente como resultado del hecho de que elijo el siguiente sello para moverlo iterando sobre un set, que es un tipo desordenado. Calculé el segundo caso de prueba a los 5 minutos y 30 segundos, aunque no pareció mucho la primera vez que lo ejecuté. Con la optimización mencionada anteriormente, es más como 40 segundos.

DLosc
fuente

Curiosamente, en Python 2 debería dar el mismo orden cada vez. Creo que cambiaron Python 3 para proporcionar hashes aleatorios en cada ejecución para los mismos objetos para evitar ciertas vulnerabilidades: "La aleatorización de hash está habilitada de forma predeterminada. Establezca la variable de entorno PYTHONHASHSEED en 0 para deshabilitar la aleatorización de hash. Consulte también el objeto .__ hash __ () método."

Claudiu

JavaScript (ES6) 322 334 323

Edición2 Animación agregada en el fragmento

Editar corrección de errores, recuerde la posición inicial de '*', así que lo encuentro incluso cuando un sello se desliza sobre él y lo borro.

Implementado como una función con la cadena de entrada como parámetro (probablemente no válido pero esperando una aclaración). Salida a través de una ventana emergente.
El problema con la entrada de cadenas multilínea en JavaScript es que promptno lo maneja bien.

En cuanto al algoritmo: un BFS, debería encontrar una solución óptima. Mantengo una cola del estado del juego en variablel , el estado de la cuadrícula de personajes gy la secuencia de movimientos hasta ahora s. Además, hay un conjunto de cuadrículas obtenidas hasta ahora en variable k, para evitar explorar la misma cuadrícula una y otra vez.

El bucle principal es

quitar el estado del juego
pruebe todos los movimientos posibles, ponga en cola el estado después de cada movimiento válido (IIF, la cuadrícula resultante aún no está presente)
si se encuentra la solución, salga del bucle

F=s=>{
  o=~s.match(/\d+/),g=[...z=s.replace(/.*/,'')];
  for(l=[[g,'']],k=[];[g,s]=l.shift(),!g.some((c,p)=>
      c>'A'&&[-1,1,o,-o].some((d,j)=>{
        t=s+' '+[c,'LRUD'[j]];
        for(q=p;(u=g[q+d])<'.';)q+=d;
        return(c<'a'&z[q]=='*')||
        c>'D'|u>'.'&&!(
          f=[...g],u=='.'?0:f[q]=c,f[p]='#',
          k[h=f.map(v=>v>'D'?0:v)]||(k[h]=l.push([f,t]))
        )
      })
    ););
  alert(t)
}

Ejecute Snippet para probar en FireFox

Mostrar fragmento de código

F=s=>{
  o=~s.match(/\d+/),g=[...z=s.replace(/.*/,'')];
  for(l=[[g,k=[]]];[g,s]=l.shift(),!g.some((c,p)=>
      c>'A'&&[-1,1,o,-o].some((d,j)=>{
        t=s+' '+[c,'LRUD'[j]];
        for(q=p;(u=g[q+d])<'.';)q+=d;
        return(c<'a'&z[q]=='*')||
        c>'D'|u>'.'&&!(
          f=[...g],u=='.'?0:f[q]=c,f[p]='#',
          k[h=f.map(v=>v>'D'?0:v)]||(k[h]=l.push([f,t]))
        )
      })
    ););
  return t
}

$('.T td').each(function(i,td) { $('.R td').eq(i).text(F($(td).text())) });

$(".R").on('click','td',function(){ 
  var i = $(this).index();
  var $td = $('.T td').eq(i);
  var t = $td.text().trim();
  animate($td, $td.text().trim(), $('.R td').eq(i).text().trim());
});

$('#GO').on('click',function() { 
  var s = T0.value, h=F(s)
  console.log(s)
  $('#R0').text(h);
  animate($('#A'), s,h);
});

function animate($out, s, h){
  o=~s.match(/\d+/),g=[...s.replace(/.*/,'')];
  
  fr=[g.join('')];
  h.replace(/.,(.)/g, (c,d)=>{
    i = g.indexOf(c=c[0]);
    d = [-1,1,o,-o]['LRUD'.search(d)]
    for(;g[i+d]<'.';i+=d)
    {
      g[i]='#',z=[...g],g[i+d]=c,z[i+d]='<b>'+c+'</b>', fr.push(z.join(''))
    }
    if(g[i+d]=='.')
    {
      g[i]='#', fr.push(g.join(''))
    }
  })

  var fa = ()=>{
    var f=fr.shift();                  
    f ? $out.html(f) : (
      clearInterval(i), 
      $out.text(s), 
      $out.toggleClass('Anim')
  )};
  $out.toggleClass('Anim');
  fa();
  var i=setInterval(fa, 500);  
}

td { vertical-align: top; font-family: monospace; white-space: pre; }
textarea { width: 99%;  height:10em;}
pre { margin: 0; }
.R td { background: #fdc; padding: 6px 0; }
.R td:hover { background: #ffc }
.T td { background: #ddf}
B { color: red }
.T td.Anim, td.Anim { background: #ffc; }

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table cellspacing=5>
  <tr>
    <th colspan=4>Predefined tests</th>
  </tr>
  <tr class=T>
    <td>25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................</td>
    <td>9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........</td>
<td>26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................</td>
<td>8,5
........
.##c###.
.a#*#D#.
.##b###.
........</td>
    </tr>
  <tr><td colspan=4>Click on solution text to start animation</td>
  </tr>  
  <tr class=R>  
    <td></td><td></td><td></td><td></td>
  </tr>  
  <tr><th colspan=2>Your test  </th></tr>
  <tr><td colspan=2><textarea id=T0></textarea></td>
    <td colspan=2 id=A></td>
  </tr>
  <tr>
    <td colspan=2>Find solution and animate <button id=GO>go</button></td>
    <td colspan=2 id=R0></td>
  </tr>  
</table>

Expandir fragmento

edc65
fuente

C ++, 628 bytes

Bueno, esto no resultó muy corto:

#include <set>
#include <iostream>
using namespace std;struct R{string b,m;bool operator<(R r)const{return b<r.b;}};int w,h,t,j,k,z=1;char c,f;set<R> p,q;int m(R r,int x,int d,char a){for(j=x,c=r.b[x];(f=r.b[j+=d])==35;);if(c-68||f-46){r.b[x]=35;if(f-46)r.b[j-d]=c;r.m+=c;r.m+=44;r.m+=a;r.m+=10;if(c==68&j-d==t){cout<<r.m;z=0;}if(p.count(r)+q.count(r)==0){q.insert(r);}}}int main(){cin>>w>>c>>h>>c;R r;string l;for(;k++<h;){getline(cin,l);r.b+=l;}t=r.b.find(42);r.b[t]=35;q.insert(r);for(;z;){r=*q.begin();q.erase(q.begin());p.insert(r);for(k=0;z&&k<w*h;++k){if(r.b[k]>64){m(r,k,-1,76);m(r,k,1,82);m(r,k,-w,85);m(r,k,w,68);}}}}

Elegí C ++ porque quería usar las estructuras de datos ( set, string), pero es intrínsecamente bastante detallado. La solución tiene un rendimiento razonablemente bueno, resolviendo la prueba 2 en poco más de 2 segundos en un MacBook Pro, a pesar de que no está optimizado para el tiempo de ejecución.

Código antes de comenzar a eliminar espacios en blanco y alguna otra reducción de longitud:

#include <set>
#include <iostream>

using namespace std;

struct R {
    string b, m;
    bool operator<(R r) const {return b < r.b; }
};

int w, h, t;
set<R> p, q;
bool z = true;

void m(R r, int k, int d, char a) {
    int j = k;
    char s = r.b[k], f;
    for (; (f = r.b[j += d]) == 35;);
    if (s - 68 || f - 46) {
        r.b[k] = 35;
        if (f - 46) {
            r.b[j - d] = s;
        }
        r.m += s;
        r.m += 44;
        r.m += a;
        r.m += 10;
        if (s == 68 && j - d == t) {
            cout << r.m;
            z = false;
        }
        if (p.count(r) + q.count(r) == 0) {
            q.insert(r);
        }
    }
}

int main() {
    char c;
    cin >> w >> c >> h >> c;
    string b, l;
    int k;
    for (k = 0; k < h; ++k) {
        getline(cin, l);
        b += l;
    }

    t = b.find(42);
    b[t] = 35;

    R r;
    r.b = b;
    q.insert(r);

    for ( ; z; ) {
        r = *q.begin();
        q.erase(q.begin());
        p.insert(r);

        for (k = 0; z && k < w * h; ++k) {
            c = r.b[k];
            if (c > 64) {
                m(r, k, -1, 76);
                m(r, k, 1, 82);
                m(r, k, -w, 85);
                m(r, k, w, 68);
            }
        }
    }

    return 0;
}

La idea central detrás del algoritmo es que se mantienen dos conjuntos:

q es el conjunto de configuraciones que están pendientes de procesamiento.
p es el conjunto de configuraciones que se han procesado.

El algoritmo comienza con la configuración inicial en q. En cada paso, se genera una configuración q, se agrega a p, todos los posibles movimientos de sellado se generan y se insertan las nuevas configuraciones resultantes q.

Prueba de funcionamiento:

bash-3.2$ ./a.out <test1
D,R
bash-3.2$ time ./a.out <test2
p,U
c,U
p,R
c,L
m,L
b,L
a,L
D,U
b,L
D,R
D,D
D,L

real    0m2.267s
user    0m2.262s
sys 0m0.003s
bash-3.2$ ./a.out <test3
v,U
D,L
bash-3.2$

Reto Koradi
fuente

Usando una cola en lugar de establecerla para 'q', puede encontrar soluciones más cortas en menos tiempo (mi solución para la prueba 2 son 6 pasos).

edc65

@ edc65 Sí, inicialmente me sorprendió la cantidad de movimientos allí. Lo revisé para confirmar que es una solución válida. Usar un FIFO para qciertamente sería mejor en ese sentido. La razón por la que usé un conjunto fue porque quería evitar ingresar la misma entrada varias veces. Pero comencé a tener dudas una vez que vi el resultado.

Reto Koradi

En cuanto al rendimiento, debe usar una cola Y un conjunto para evitar repeticiones. Pero ponga en el conjunto una versión modificada de la cuadrícula, ya que cada cría de foca es intercambiable.

edc65