Después de su desastroso paseo en canoa , terminó cayéndose de una cascada al final de los rápidos del río. Tu canoa explotó, pero lograste sobrevivir a la explosión. Sin embargo, su viaje por el río se desvió completamente del mapa: ahora se ha encontrado perdido en medio de un bosque. Afortunadamente, todavía tiene sus habilidades de programación, por lo que decide tallar un programa en el costado de un árbol para ayudarlo a encontrar su camino a través del bosque. Sin embargo, no hay mucha superficie en el árbol, por lo que debe hacer que su programa sea lo más corto posible.

El bosque se puede describir como un cuadrado de caracteres nby n( n > 5), que solo consistirá en letras minúsculas a-z. Un ejemplo de bosque:

anehcienwlndm
baneiryeivown
bnabncmxlriru
anhahirrnrauc
riwuafuvocvnc
riwnbaueibnxz
hyirorairener
ruwiiwuauawoe
qnnvcizdaiehr
iefyioeorauvi
quoeuroenraib
cuivoaisdfuae
efoiebnxmcsua

Es posible que haya notado que en este bosque, hay una línea diagonal de acaracteres que lo atraviesa desde la esquina superior izquierda hasta la esquina inferior derecha. Este es un "camino" a través del bosque que lo llevará a algún lado si lo sigue. Su tarea es escribir un programa que encuentre la ruta singular. Ahora describiré más específicamente lo que connota un "camino" en este desafío.

Una "ruta", en este desafío, se define como una línea similar a una que podría haberse generado con un algoritmo de Bresenham , pero con los requisitos adicionales que:

• La línea debe tener un mínimo de 6 caracteres.
• Cada grupo de caracteres colineales (completamente adyacentes) en la línea debe tener la misma longitud .
• Comenzará en un borde del bosque y terminará en el borde opuesto (vea mi comentario aquí para más detalles)

Para explicar el segundo requisito más claramente, considere la siguiente línea:

aaa
   aaa
      aaa
         aaa
            aaa

Esta línea se compone de "segmentos" colineales de caracteres, cada uno de los cuales tiene exactamente tres caracteres de longitud. Califica como un camino. Ahora considere esta línea:

a
 aa
   a
    aa
      a
       aa

Esta línea está compuesta de "segmentos" colineales que no tienen exactamente la misma longitud de caracteres (algunos de ellos tienen 1 carácter y otros 2). Por lo tanto, este no califica como un camino.

Su programa, dado un mapa del bosque, identifica los caracteres utilizados en el camino. La entrada es a lo que sea conveniente (por ejemplo, argumento de línea de comando, STDIN prompt(), etc.). No se puede inicializar previamente en una variable. La primera parte de la entrada es un número entero único que nrepresenta el tamaño del bosque (el bosque siempre es un cuadrado). Después de eso hay un espacio y luego todo el bosque como una sola cadena. Por ejemplo, el bosque de ejemplo se presentaría, como una entrada, así:

13  anehcienwlndmbaneiryeivownbnabncmxlriruanhahirrnraucriwuafuvocvncriwnbaueibnxzhyirorairenerruwiiwuauawoeqnnvcizdaiehriefyioeorauviquoeuroenraibcuivoaisdfuaeefoiebnxmcsua

El resultado para esto sería:

a

porque el camino se forma usando la letra a. Solo habrá un camino en el bosque. Este es el código de golf, por lo que gana el menor número de caracteres. Si tiene preguntas, pregunte en los comentarios.

APL (Dyalog 14) (70)

⎕ML←3⋄Z/⍨1=≢¨Z←∪¨(↓⍉F),(↓F),{(⍳≢⍵)⌷¨↓⍵}¨(⊂F),⊂⌽F←⊃{⍵⍴⍨2/⍎⍺}/I⊂⍨' '≠I←⍞

Explicación:

• ⎕ML←3: establecido MLen 3, significado ⊂tiene su significado APL2.
• I←⍞: lee una línea desde el teclado y la almacena en I
• I⊂⍨' '≠I: dividido Ien los espacios
• {... }/: aplica esta función a las dos cadenas resultantes:
  • 2/⍎⍺: evalúa el argumento izquierdo y lo replica dos veces, dando el tamaño de la matriz
  • ⍵⍴⍨: formatea el argumento correcto usando ese tamaño
• F←⊃: desempaquételo y guárdelo F.
• {(⍳≢⍵)⌷¨↓⍵}¨(⊂F),⊂⌽F: obtenga las diagonales: de cada fila en ambos Fy ⌽F(reflejado verticalmente F), obtenga el valor en la columna X, donde X es su número de fila
• (↓⍉F),(↓F),: obtener las filas y columnas de F
• Z←∪¨: encuentre los valores únicos en cada fila, columna y diagonal y guárdelos Z.

Dado que el 'bosque' es rectangular, si hay una ruta válida, significa que uno de estos consistirá en un solo carácter, que es el carácter de la ruta, por lo que:

• Z/⍨1=≢¨Z: tome esas submatrices Zque solo tienen un elemento.

Esto mostrará los caracteres para todas las rutas válidas, pero dado que solo debe haber uno que no importe.

Lua - 506 380 - bytes

Me sentí un poco mal por no haber recibido ninguna sumisión por su bien pensado desafío, por lo que preparé esto. Fue divertido deducir cuáles son las propiedades mínimas distinguibles que debe tener la ruta de la información que proporcionó. Espero haberlo hecho bien ... Y haberlo implementado correctamente.

a=io.read"*l"n=a:match("%d+")+0 m=a:match"[a-z]+"o=""for i=1,n do for k=1,n^2,n do o=o..m:sub(i+k-1,i+k-1)end end q={m,o}for g=1,n^2 do for u=1,2 do l=q[u]:sub(g,g)for r=1,n do i=1 t=0 e=0 while i do s,e=q[u]:find(l:rep(r),e+1)if s then x=s-(e-s)-i-1 print(s,i,r,n,r)if x==n or x==n-2 or t==0 then t=t+1 i=s end else i=nil end end if t*r==n then print(l)os.exit()end end end end

Se puede probar con:

lua divisorPath.lua "input"

Si aparece un retador salvaje, buscaré en mi código lo que valga.

Actualización : golf en honor de aquellos que se levantarán por encima de nosotros. Mientras estaba en eso, tuve que arreglar mi código en una ruta reconocida que iba de derecha a izquierda. Ups

MATLAB - 270 caracteres

A continuación se define una función xque acepta una cadena de bosque como argumento y devuelve el carácter que representa la "ruta" válida a través del bosque sujeto a las reglas dadas.

function F=x(s),A=sscanf(s,'%d%s');n=A(1);A=reshape(A(2:end),n,n);for c=A(:)',B=A==c;for i=1:n,if~mod(n,i),C=[kron(eye(i),ones(n/i,1)),zeros(n,n-i)];for j=0:n-i,f=@(B)sum(sum(B&circshift(C,[0,j]))==n;D=fliplr(B);if f(B)|f(B')|f(D)|f(D'),F=char(c);end;end;end;end;end;end

La versión no minificada es

function F = x(s)
    A = sscanf( s, '%d %s' );
    n = A(1);
    A = reshape( A(2:end), n,n );
    for c = A(:)'
        B = A==c;
        for i = 1:n
            if ~mod( n, i )
                C = [kron( eye(i), ones( n/i,1 ) ), zeros( n,n-i )];
                for j = 0:n-i
                    f = @(B) sum(sum( B & circshift( C, [0 j] ))) == n;
                    D = fliplr(B);
                    if f(B) | f(B') | f(D) | f(D')
                        F = char(c);
                    end
                end
            end
        end
    end
end

La premisa básica es construir una máscara booleana para cada ruta válida posible y devolver cualquier carácter cuya función de índice en la matriz cubra cualquier máscara. Para lograr esto, solo se crean máscaras verticales o de arriba a abajo en forma de barra invertida, pero la matriz forestal se compara en las cuatro orientaciones: identidad, volteado, girado 90 °, volteado girado 90 °.

La función se ejecuta para cualquiera n. Un ejemplo de que se invoca en la línea de comandos es

x('13 anehcienwlndmbaneiryeivownbnabncmxlriruanhahirrnraucriwuafuvocvncriwnbaueibnxzhyirorairenerruwiiwuauawoeqnnvcizdaiehriefyioeorauviquoeuroenraibcuivoaisdfuaeefoiebnxmcsua')

ans =

    a

Python - 384 325 275

Este algoritmo básicamente verifica la primera y última fila de la matriz para buscar caracteres coincidentes y luego calcula la longitud de cada segmento de línea

012345
------
aaVaaa|0
aaVaaa|1
aaaVaa|2
aaaVaa|3
aaaaVa|4
aaaaVa|5

En el ejemplo anterior:
la V en la primera fila está en el índice 2, la V en la última fila en el índice 4.
Por lo tanto, la longitud de cada segmento de línea sería n / (4-2) +1 = 2 con n = 6 .

Luego verifica si la línea es válida.

Para encontrar una ruta de izquierda a derecha, intercambia filas con columnas y vuelve a hacer lo mismo.

Editar: No puedo llegar a 270 (¡Maldita sea Python y tu maldita sangría!)

n,m=raw_input().split()
n,r=int(n),range
t=r(n)
a=[m[i:i+n]for i in r(0,n*n,n)]
for v in a,["".join([a[i][j]for i in t])for j in t]:
 for i in t:
  for j in t:
   p=1-2*(j-i<0);d,c=p*(j-i)+1,v[0][i]
   if 6<=sum([v[z][i+(z/(n/d))*p*(n%d==0)]==c for z in t])==n:print c;exit()