Validar soluciones de bucle

9

Este es un desafío adicional para el desafío de generar rompecabezas Loopy . Es posible que desee resolver este desafío antes de intentar el desafío más difícil en el enlace anterior.

El objetivo de este desafío es validar la solución a un rompecabezas en bucle. Tome toda la documentación sobre qué es un rompecabezas en bucle del enlace anterior. Un rompecabezas en bucle resuelto está formateado de una manera muy similar a la salida de una presentación válida para el desafío "generar rompecabezas en bucle" y puede verse así:

+-+-+ +-+ +-+ +
|   | | |2|3|  
+-+ + + + + +-+
 2| | | |2|  3|
+ + +-+ + + +-+
 2|  2 1|3| |  
+-+ +-+ +-+ +-+
|2  | |    1 2|
+ +-+ +-+ +-+ +
| |2 1 2|3|3| |
+ + +-+ +-+ +-+
| | |3|2   1   
+ +-+ +-+-+-+-+
|        2 2  |
+-+-+-+-+-+-+-+

La ruta que constituye la solución está marcada con |y -caracteres entre los +caracteres.

Especificación de entrada

Su programa recibirá un rompecabezas en bucle con una solución formateada como el ejemplo anterior como entrada. Su programa inferirá el tamaño del rompecabezas a partir de la entrada. Puede hacer los siguientes supuestos sobre la entrada:

  • El rompecabezas tiene no menos de 2 y no más de 99 celdas en cualquier dirección
  • Por lo tanto, cada línea tiene una longitud máxima de 199 caracteres, sin incluir los caracteres de la nueva línea.
  • Por lo tanto, la entrada contiene un máximo de 99 líneas.
  • cada línea puede terminar después del último carácter imprimible o puede rellenarse con espacios en blanco para que tenga una longitud de hasta 2 · y + 1 caracteres donde y es el número de celdas en dirección horizontal
  • cada posición con las coordenadas x e y incluso contiene un +carácter
  • las posiciones adyacentes horizontal o verticalmente a las posiciones que contienen +caracteres contienen un espacio en blanco, están detrás del final de la línea o contienen un -carácter si es adyacente horizontalmente o un |carácter si es adyacente verticalmente
  • todas las otras posiciones son o bien detrás del extremo de la línea o contienen uno de los personajes , 0, 1, 2, o3
  • todas las líneas terminan con los caracteres de línea nueva predeterminados de su plataforma
  • hay exactamente una nueva línea final

La entrada se recibirá de una de las siguientes maneras:

  • De entrada estándar
  • Como el valor de un parámetro nombrado pen una solicitud HTTP POST
  • Como el contenido de un formulario HTML
  • Como el contenido de un archivo nombrado pen un directorio definido por la implementación
  • En una implementación definida de manera en tiempo de ejecución si los cuatro primeros no están disponibles
  • Codificado si su idioma no proporciona medios para recibir información

Especificación de salida

Su programa terminará para todas las entradas que coincidan con la especificación de entrada y calculará si la solución al rompecabezas es correcta. Su programa generará el resultado del cálculo como un valor booleano de una de las siguientes maneras:

  • Como un estado de salida de cero (la solución es válida) o no cero (la solución no es válida)
  • Como el carácter y(la solución es válida) o n(la solución no es válida) seguido de cero o más caracteres arbitrarios de salida de una manera definida por la implementación

El comportamiento de su programa no se especifica cuando se encuentra una entrada no formateada de acuerdo con la especificación de entrada.

Puntuación

La puntuación de su programa es el número de caracteres en su fuente, excepto los caracteres de espacios en blanco omitibles y los comentarios omitibles. Se le recomienda sangrar su envío para que sea más fácil de leer para los demás y comentar su solución para que sea más fácil de seguir.

Los envíos que no siguen la especificación de entrada o salida o generan resultados incorrectos no son válidos.

FUZxxl
fuente
¿Cómo se manejan las entradas? Leer de un archivo? STDIN? ¿Puedo escribir una función?
Martin Ender
@ MartinBüttner "su programa recibirá ...". No estoy seguro de por qué te gustaría leer de un archivo.
John Dvorak
@ MartinBüttner Tienes que escribir un programa completo. Creo que el lenguaje "su programa", "terminará", "estado de salida" es bastante claro.
FUZxxl
1
También tenga en cuenta que en la mayoría de los rompecabezas 0también hay un número válido para una celda.
Howard
@Howard Lo siento, me perdí eso.
FUZxxl

Respuestas:

2

GolfScript, 133 caracteres

'|':^4,{48+.(}%+^*1>.^/'-'*+2/:F;4{{~@@/*}2F//n%zip-1%n*}:X*.'+-'?.3+@/(-2<' 9'+\+'9-+  99|+  9'3/:F;.,4*{X}*.9`?@=\' +09
'-!&'ny'1/=

Espera la entrada de STDIN e imprime ypara una solución válida y npara una no válida. Realiza la tarea utilizando principalmente reemplazar cadenas en la cuadrícula o con versiones rotadas de la cuadrícula.

Código anotado:

# construct the string "|0|/|1|0|2|1|3|2-0-/-1-0-2-1-3-2"
# split into pieces of two and save to variable F
'|':^4,{48+.(}%+^*1>.^/'-'*+
2/:F;

# run the code block X 4 times
# with X: string-replace 1st item in F with 2nd, 3rd with 4th, ...
# i.e. '|0' with '|/', '|1' with '|0'
# and then rotate grid by 90 degrees
4{{~@@/*}2F//n%zip-1%n*}:X*

# for a valid grid all digits are now reduced to exactly '0'
# (i.e. no '1' or '2' or '3' or '/')

# now follow the loop along and remove it
# start: find the first occurence of '+-+' and replace with '+ 9'
# note: '9' is the marker for the current position
.'+-'?
.3+@/(-2<' 9'+\+

# string-replace '9-+' or '9|+' by '  9' (i.e. go one step along the loop)
# using block X enough times
'9-+  99|+  9'3/:F;
.,4*{X}*

# look for the marker '9' in the result and check if it is at the original
# position again
.9`?
@=

# the remaining grid must not contain any digits besides 0 and 9
# esp. no '|' or '-' may remain
\' +09
'-!

# check if both conditions are fulfilled and output corresponding character
&'ny'1/=
Howard
fuente
2

C # 803 579bytes

El programa completo, se lee desde STDIN, debe hacer frente a cualquier esquema común de nueva línea siempre que tenga avances de línea. Gracias a HackerCow por señalar que no tengo que agregar una nueva línea en una pregunta diferente, lo que me lleva a eliminarla aquí y guardar 4 bytes

Código de golf:

using C=System.Console;class P{static void Main(){var D=C.In.ReadToEnd().Replace("\r","").Split('\n');int w=D[0].Length+2,h=D.Length+1,i=0,j,c,T=0,O=1,o,z,R=0;var B=new int[w,h];var S=new int[w*h*9];for(;i++<w-2;)for(j=0;j<h-2;B[i,j]=c)if((c=(D[j++][i-1]-8)%10)>5){c=5;T++;S[0]=i+j*w;}for(i=0;++i<w-1;)for(j=0;++j<h-1;)R=(i%2+j%2>1&(o=B[i,j-1]%2+B[i-1,j]%2+B[i+1,j]%2+B[i,j+1]%2)>0&o!=2)|((c=B[i,j])<4&c!=o)?7:R;for(o=h=0;o<O;B[i,j]=0)if(B[i=(c=S[o++])%w,j=c/w]>4){h++;S[O++]=(S[O++]=c-w-1)+2;S[O++]=(S[O++]=c+w-1)+2;z=j%2<1?w*2:2;S[O++]=c-z;S[O++]=c+z;}C.Write(h-R<T?"n":"y");}}

El código realiza 3 verificaciones, primero verificando el número de líneas alrededor de cada número y que cada cruce tiene 0 o 2 líneas que salen de él, luego que todas las líneas están unidas.

Código formateado:

using C=System.Console;

class P
{
    static void Main()
    {
        var D=C.In.ReadToEnd().Replace("\r","").Split('\n');
        int w=D[0].Length+2,h=D.Length+1,i=0,j,c,T=0,O=1,o,z,R=0;
        var B=new int[w,h]; // this is the grid
        var S=new int[w*h*9]; // this is a list of joined up lines (stored as x+y*w)

        for(;i++<w-2;)
            for(j=0;j<h-2;B[i,j]=c)
                if((c=(D[j++][i-1]-8)%10)>5)
                { // we are a line
                    c=5;
                    T++; // increment line counter
                    S[0]=i+j*w; // set start of loop
                }

        for(i=0;++i<w-1;) // this loop checks the numbers and that every + has 0 or 2 lines leading from it
            for(j=0;++j<h-1;)
                R=(i%2+j%2>1&(o=B[i,j-1]%2+B[i-1,j]%2+B[i+1,j]%2+B[i,j+1]%2)>0&o!=2)|((c=B[i,j])<4&c!=o)?7:R; // set R to 7 (no significance) if check fails

        for(o=h=0;o<O;B[i,j]=0) // this loops through the list of joined lines adding more until the whole loop has been seen
            if(B[i=(c=S[o++])%w,j=c/w]>4)
            {
                h++; // increment "seen" counter
                S[O++]=(S[O++]=c-w-1)+2;
                S[O++]=(S[O++]=c+w-1)+2;
                z=j%2<1?w*2:2; // special for | and -
                S[O++]=c-z;
                S[O++]=c+z;
            }

        C.Write(h-R<T?"n":"y"); // check if R is greater than 0 or h is less than T and output appropriately
    }
}
VisualMelon
fuente
Gracias @ edc65, ¡no tengo idea de cómo me perdí eso!
VisualMelon
1

Cobra - 514

class P
    def main
        t,m,g=[[1]][:0],nil,File.readAllLines('p')
        u,i=g[0].length,1
        for l in g.length,for c in u,if g[l][c]in'0123'
            n=0
            for j in-1:2:2,for r in[g[l+j][c],g[l][c+j]],if r in'-|',n+=1
            if'[n]'<>g[l][c],m?='n'
        else if g[l][c]in'-|',x,y,t,d=c,l,t+[[c,l]],g[l][c]
        while i
            i=z=6
            for f,b in[[-1,1],[1,1],[0,2],[-1,-1],[+1,-1],[0,-2]]
                if'-'==d,f,b=b,f
                for w in t.count,if z and t[w]==[x+f,y+b],t,x,y,d,z=t[:w]+t[w+1:],x+=f,y+=b,g[y][x],0
                i-=z//6
        print if(t.count,'n',m?'y')

Comprueba si cada número tiene el número correcto de líneas al lado, y luego recorre un camino alrededor de las líneas y comprueba si faltó alguna.

Οurous
fuente