Esta pregunta se basa en el rompecabezas de colocación de números Towers (también conocido como Skyscrapers), que puedes jugar en línea . Su objetivo es tomar una solución al rompecabezas y determinar las pistas: el número de torres visibles a lo largo de cada fila y columna. Este es el código de golf, por lo que gana menos bytes.

Cómo funcionan las torres

La solución a un rompecabezas Torres es un cuadrado latino - una n*ncuadrícula en la que cada fila y columna contiene una permutación de los números 1a través n. Un ejemplo para n=5es:

4 3 5 2 1 
5 4 1 3 2 
1 5 2 4 3 
2 1 3 5 4 
3 2 4 1 5 

Cada fila y columna está etiquetada con una pista en cada extremo como:

       2 3 1 4 5    
       v v v v v

 2 >   4 3 5 2 1   < 3
 1 >   5 4 1 3 2   < 4
 2 >   1 5 2 4 3   < 3
 3 >   2 1 3 5 4   < 2
 3 >   3 2 4 1 5   < 1 

       ^ ^ ^ ^ ^
       2 2 2 2 1

Cada pista es un número de 1a nque te dice cuántas torres "ver" mirando a lo largo de la fila / columna de esa dirección, si los números son tratados como torres con esa altura. Cada torre bloquea torres más cortas detrás de ella. En otras palabras, las torres que puedes ver son las que son más altas que cualquier torre antes que ellas.

Por ejemplo, veamos la primera fila.

 2 >   4 3 5 2 1   < 3

Tiene una pista de 2la izquierda porque puedes ver el 4y el 5. Los 4bloques de la 3de la vista y la 5bloquea todo lo demás. Desde la derecha, se puede ver 3torres: 1, 2, y 5.

Requisitos del programa

Escriba un programa o función que tome en la cuadrícula de números y produzca o imprima las pistas, yendo en sentido horario desde la parte superior izquierda.

Entrada

Un n*ncuadrado latino con 2<=n<=9.

El formato es flexible. Puede usar cualquier estructura de datos que represente una cuadrícula o lista que contenga números o caracteres de dígitos. Es posible que necesite un separador entre las filas o ningún separador en absoluto. Algunas posibilidades son una lista, una lista de listas, una matriz, una cadena separada por tokens como

43521 54132 15243 21354 32415,

o una cadena sin espacios.

No te dan ncomo parte de la entrada.

Salida

Devuelve o imprime las pistas comenzando desde la parte superior izquierda y en sentido horario. Entonces, primero las pistas superiores leen hacia la derecha, luego las pistas correctas leen hacia abajo, luego las pistas inferiores leen hacia la izquierda, las pistas izquierdas leen hacia arriba.

Esto sería 23145 34321 12222 33212para el ejemplo anterior.

       2 3 1 4 5    
       v v v v v

 2 >   4 3 5 2 1   < 3
 1 >   5 4 1 3 2   < 4
 2 >   1 5 2 4 3   < 3
 3 >   2 1 3 5 4   < 2
 3 >   3 2 4 1 5   < 1 

       ^ ^ ^ ^ ^
       2 2 2 2 1

Al igual que para la entrada, puede usar una lista, cadena o cualquier estructura ordenada. Los cuatro "grupos" se pueden separar o no, en una estructura anidada o plana. Pero, el formato debe ser el mismo para cada grupo.

Ejemplos de casos de prueba:

(Su formato de entrada / salida no tiene que ser el mismo que estos).

>> [[1 2] [2 1]]

[2 1]
[1 2]
[2 1]
[1 2]

>> [[3 1 2] [2 3 1] [1 2 3]]

[1 2 2]
[2 2 1]
[1 2 3]
[3 2 1]

>> [[4 3 5 2 1] [5 4 1 3 2] [1 5 2 4 3] [2 1 3 5 4] [3 2 4 1 5]]

[2 3 1 4 5]
[3 4 3 2 1]
[1 2 2 2 2]
[3 3 2 1 2]

>> [[2 6 4 1 3 7 5 8 9] [7 2 9 6 8 3 1 4 5] [5 9 7 4 6 1 8 2 3] [6 1 8 5 7 2 9 3 4] [1 5 3 9 2 6 4 7 8] [3 7 5 2 4 8 6 9 1] [8 3 1 7 9 4 2 5 6] [9 4 2 8 1 5 3 6 7] [4 8 6 3 5 9 7 1 2]]

[4 2 2 3 3 3 3 2 1]
[1 3 3 2 2 2 2 3 3]
[4 3 2 1 2 3 3 2 2]
[3 1 2 4 3 3 2 2 5]

Para su conveniencia, estos son los mismos casos de prueba en un formato de cadena plana.

>> 1221

21
12
21
12

>> 312231123

122
221
123
321

>> 4352154132152432135432415

23145
34321
12222
33212

>> 264137589729683145597461823618572934153926478375248691831794256942815367486359712

422333321
133222233
432123322
312433225

APL 19

≢¨∪/⌈\(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)

(Golf un poco más después de la sugerencia de ngn, gracias)

Explicación:

(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)  rotates matrix 4 times appending results
⌈\ gets maximums for each row up to current column (example: 4 2 3 5 1 gives 4 4 4 5 5)
≢¨∪/ counts unique elements for each row

Pruébalo en tryapl.org

Python 2, 115 bytes

def T(m):o=[];exec'm=zip(*m)[::-1]\nfor r in m[::-1]:\n n=k=0\n for x in r:k+=x>n;n=max(x,n)\n o+=[k]\n'*4;return o

Hay una gran cantidad de listas cambiando allí.

Toma la entrada como una lista anidada (por ejemplo, llamar con T([[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]])). La salida es una sola lista plana.

Sin golf:

def T(m):
 o=[]
 for _ in [0]*4:
  m=zip(*m)[::-1]
  for r in m[::-1]:
   n=k=0
   for x in r:k+=x>n;n=max(x,n)
   o+=[k]
 return o

Alternativa 115:

def T(m):o=[];exec'm=zip(*m)[::-1];o+=[len(set([max(r[:i+1])for i in range(len(r))]))for r in m[::-1]];'*4;return o

No tengo idea de por qué esto funciona con una comprensión de lista, pero arroja una NameErrorcon una comprensión establecida ...

Un poco demasiado, pero si alguien está interesado, sí, ¡es posible que esto se reduzca a una lambda!

T=lambda m:[len({max(r[:i+1])for i in range(len(r))})for k in[1,2,3,4]for r in eval("zip(*"*k+"m"+")[::-1]"*k)[::-1]]

Pyth , 25 bytes

V4=Q_CQ~Yml{meS<dhkUd_Q)Y

Puerto Pyth obligatorio.

Ingrese la lista a través de STDIN, por ejemplo [[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]].

Pruébelo en línea ... es lo que diría, pero desafortunadamente, por razones de seguridad, el intérprete en línea no permite el uso de eval en paréntesis anidados. Intente con el código de solución alternativa JcQ5V4=J_CJ~Yml{meS<dhkUd_J)Ye ingrese como una lista aplanada como [4, 3, 5, 2, 1, 5, 4, 1, 3, 2, 1, 5, 2, 4, 3, 2, 1, 3, 5, 4, 3, 2, 4, 1, 5].

(Gracias a @isaacg que ayudó a jugar golf unos pocos bytes)

CJam, 29 27 bytes

q~{z_{[{1$e>}*]_&,}%pW%}4*;

Entrada como

[[4 3 5 2 1] [5 4 1 3 2] [1 5 2 4 3] [2 1 3 5 4] [3 2 4 1 5]]

Salida como

[2 3 1 4 5]
[3 4 3 2 1]
[1 2 2 2 2]
[3 3 2 1 2]

Cómo funciona

La idea básica es hacer que el código funcione a lo largo de las filas y rotar la cuadrícula en sentido antihorario 4 veces. Para contar las torres, estoy elevando cada torre hasta donde no haga una "diferencia visual" (es decir, no la cambie si es visible, ni la levante a la misma altura de la torre frente a ), y luego estoy contando distintas alturas.

q~                          "Read and evaluate the input.";
  {                    }4*  "Four times...";
   z                        "Transpose the grid.";
    _                       "Duplicate.";
     {            }%        "Map this block onto each row.";
      [       ]             "Collect into an array.";
       {    }*              "Fold this block onto the row.";
        1$                  "Copy the second-to-topmost element.":
          e>                "Take the maximum of the top two stack elements.";
                            "This fold replaces each element in the row by the
                             maximum of the numbers up to that element. So e.g.
                             [2 1 3 5 4] becomes [2 2 3 5 5].";
               _&,          "Count unique elements. This is how many towers you see.";
                    p       "Print array of results.";
                     W%     "Reverse the rows for the next run. Together with the transpose at
                             the start this rotates the grid counter-clockwise.";
                          ; "Get rid of the grid so that it isn't printed at the end.";

APL, 44

{{+/~0∊¨↓(∘.>⍨⍵)≥∘.<⍨⍳⍴⍵}¨↓(⌽∘⍉⍪⊢⍪⊖∘⍉⍪⊖∘⌽)⍵}

Probado aquí.

J, 35 caracteres

(+/@((>./={:)\)"2@(|.@|:^:(<4)@|:))

Ejemplo:

   t=.4 3 5 2 1,. 5 4 1 3 2,. 1 5 2 4 3,. 2 1 3 5 4,. 3 2 4 1 5
   (+/@((>./={:)\)"2@(|.@|:^:(<4)@|:)) t
2 3 1 4 5
3 4 3 2 1
1 2 2 2 2
3 3 2 1 2

Pruébalo aquí.

Haskell, 113

import Data.List
f(x:s)=1+f[r|r<-s,r>x]
f _=0
r=reverse
t=transpose
(?)=map
l s=[f?t s,(f.r)?s,r$(f.r)?t s,r$f?s]

Mathematica, 230,120,116,113 110 bytes

f=(t=Table;a=#;s=Length@a;t[v=t[c=m=0;t[h=a[[y,x]];If[h>m,c++;m=h],{y,s}];c,{x,s}];a=Thread@Reverse@a;v,{4}])&

Uso:

f[{
  {4, 3, 5, 2, 1},
  {5, 4, 1, 3, 2},
  {1, 5, 2, 4, 3},
  {2, 1, 3, 5, 4},
  {3, 2, 4, 1, 5}
}]

{{2, 3, 1, 4, 5}, {3, 4, 3, 2, 1}, {1, 2, 2, 2, 2}, {3, 3, 2, 1, 2}}

JavaScript 335 264 256 213

T=I=>((n,O)=>(S=i=>i--&&O.push([])+S(i)+(R=(j,a,x)=>j--&&R(j,0,0)+(C=k=>k--&&((!(a>>(b=I[(F=[f=>n-k-1,f=>j,f=>k,f=>n-j-1])[i]()][F[i+1&3]()])))&&++x+(a=1<<b))+C(k))(n)+O[i].push(x))(n,0,0))(4)&&O)(I.length,[],[])

Evalúe en la consola de JavaScript del navegador (usé Firefox 34.0, parece que no funciona en Chrome 39 ??) Pruebe con:

JSON.stringify(T([[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]]));

Aquí está la encarnación actual del código no protegido: es cada vez más difícil de seguir:

function countVisibleTowers(input) {
  return ((n, out) =>
      (sideRecurse = i =>
          i-- &&
          out.push([]) +
          sideRecurse(i) +
          (rowRecurse = (j, a, x) =>
              j-- &&
              rowRecurse(j, 0, 0) +
              (columnRecurse = k =>
                  k-- &&
                  ((!(a >> (b = input[
                                        (offsetFtn = [
                                            f => n - k - 1,   // col negative
                                            f => j,           // row positive
                                            f => k,           // col positive
                                            f => n - j - 1    // row negative
                                        ])[i]()
                                     ]
                                     [
                                        offsetFtn[i + 1 & 3]()
                                     ]))) &&
                  ++x +
                  (a = 1 << b)) +
                  columnRecurse(k)
              )(n) +
              out[i].push(x)
          )(n, 0, 0)
      )(4) && out
  )(input.length, [], [])
}

Intencionalmente no miré ninguna de las otras respuestas, quería ver si podía resolver algo por mí mismo. Mi enfoque consistía en aplanar las matrices de entrada a una matriz unidimensional y precalcular las compensaciones a las filas desde las cuatro direcciones. Luego usé shift right para probar si la siguiente torre era falsa y si lo era, luego incremente el contador para cada fila.

Espero que haya muchas maneras de mejorar esto, tal vez no calcular previamente los desplazamientos, sino usar algún tipo de desbordamiento / módulo en la matriz de entrada 1D. Y quizás combinar mis bucles, ser más funcional, deduplicar.

¡Cualquier sugerencia sera apreciada!

Actualización n. ° 1 : ¡Progreso, tenemos la tecnología! Pude deshacerme de las compensaciones precalculadas y hacerlas en línea con operadores ternarios unidos. También pude deshacerme de mi declaración if y convertir los bucles for en whiles.

Actualización n. ° 2 : Esto es bastante frustrante; No hay fiesta de pizza para mí. Pensé que funcionar y usar la recursión reduciría muchos bytes, ¡pero mis primeros intentos terminaron siendo mayores en hasta 100 caracteres! En su desesperación, utilicé las funciones de flecha de grasa ES6 para reducirlo realmente. Luego decidí reemplazar los operadores booleanos por aritméticos y eliminar parens, punto y coma y espacios donde pude. Incluso dejé de declarar mis variables y contaminé el espacio de nombres global con mis símbolos locales. Sucio sucio. Después de todo ese esfuerzo, superé mi puntaje de Actualización n. ° 1 con la friolera de 8 caracteres, hasta 256. ¡Blargh!

Si aplicara las mismas optimizaciones despiadadas y trucos ES6 a mi función de Actualización n. ° 1, superaría esta puntuación por una milla. Puedo hacer una Actualización # 3 solo para ver cómo se vería.

Actualización n. ° 3 : Resulta que el enfoque recursivo de la flecha gorda tenía mucha más vida, solo necesitaba trabajar con la entrada bidimensional directamente en lugar de aplanarla y mejorar el aprovechamiento de los ámbitos de cierre. Reescribí los cálculos de compensación de la matriz interna dos veces y obtuve el mismo puntaje, por lo que este enfoque puede estar cerca de ser explotado.

Java, solo 352 350 325 bytes ...

class S{public static void main(String[]a){int n=a.length,i=0,j,k,b,c;int[][]d=new int[n][n];for(;i<n;i++)for(j=0;j<n;)d[i][j]=a[i].charAt(j++);for(i=0;i<4;i++){int[][]e=new int[n][n];for(k=0;k<n;k++)for(j=0;j<n;)e[n-j-1][k]=d[k][j++];d=e;for(j=n;j-->(k=c=b=0);System.out.print(c))for(;k<n;k++)b=d[j][k]>b?d[j][k]+0*c++:b;}}}

Entrada como 43521 54132 15243 21354 32415

Salida como: 23145343211222233212

Sangrado:

class S{
    public static void main(String[]a){
        int n=a.length,i=0,j,k,b,c;
        int[][]d=new int[n][n];
        for(;i<n;i++)
            for(j=0;j<n;)d[i][j]=a[i].charAt(j++);
        for(i=0;i<4;i++){
            int[][]e=new int[n][n];
            for(k=0;k<n;k++)
                for(j=0;j<n;)e[n-j-1][k]=d[k][j++];
            d=e;
            for(j=n;j-->(k=c=b=0);System.out.print(c))
                for(;k<n;k++)b=d[j][k]>b?d[j][k]+0*c++:b;
        }
    }
}

¡Algún consejo sería de gran aprecio!

Python 2 - 204 bytes

def f(l):n=len(l);k=[l[c]for c in range(n)if l[c]>([0]+list(l))[c]];return f(k)if k!=l else n
r=lambda m:(l[::-1]for l in m)
m=input();z=zip(*m);n=0
for t in z,r(m),r(z),m:print map(f,t)[::1-(n>1)*2];n+=1

Este es probablemente un golf realmente pobre. Pensé que el problema era interesante, así que decidí abordarlo sin buscar la solución de nadie más. Mientras escribo esta oración, todavía tengo que mirar las respuestas a esta pregunta. No me sorprendería que alguien más haya hecho un programa Python más corto;)

Ejemplo de E / S

$ ./towers.py <<< '[[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]]'
[2, 3, 1, 4, 5]
[3, 4, 3, 2, 1]
[1, 2, 2, 2, 2]
[3, 3, 2, 1, 2]

Opcionalmente, puede incluir espacios en blanco en la entrada. Casi en cualquier lugar, sinceramente. Mientras puedas eval(), funcionará.

Explicación

La única parte interesante de este programa es la primera línea. Define una función f(l)que le dice cuántas torres se pueden ver en una fila, y el resto del programa simplemente aplica esa función a cada posición posible.

Cuando se le llama, encuentra la longitud ly la guarda en una variable n. Luego crea una nueva variable kcon esta comprensión de lista bastante monstruosa:

[l[c]for c in range(n)if l[c]>([0]+list(l))[c]]

No es tan malo cuando lo descompones. Desde entonces n==len(l), todo antes de lo ifjusto representa l. Sin embargo, usando ifpodemos eliminar algunos elementos de la lista. Construimos una lista con ([0]+list(l)), que es solo " lcon un 0agregado al principio" (ignore la llamada a list(), eso solo está allí porque a veces les un generador y debemos asegurarnos de que en realidad sea una lista aquí). l[c]solo se coloca en la lista final si es mayor que ([0]+list(l))[c]. Esto hace dos cosas:

• Como hay un nuevo elemento al comienzo de la lista, el índice de cada uno se l[c]convierte c+1. Estamos comparando efectivamente cada elemento con el elemento a la izquierda del mismo. Si es mayor, es visible. De lo contrario, se oculta y se elimina de la lista.
• La primera torre siempre es visible porque no hay nada que pueda bloquearla. Como ponemos 0 al principio, la primera torre siempre es mayor. (Si no hicimos este [0]+sentido y sólo se comparó l[c]a l[c-1], Python sería comparar la primera torre a la última (que puede indexar en una lista desde el extremo con -1, -2, etc.), por lo que si la última torre era más alto que el primero obtendríamos el resultado incorrecto.

Cuando todo está dicho y hecho, lcontiene un número de torres y kcontiene cada una de ellas que no es más corta que su vecino inmediato a la izquierda. Si ninguno de ellos fuera (por ejemplo, para f([1,2,3,4,5])), entonces l == k. Sabemos que no queda nada que hacer y regresar n(la longitud de la lista). Si l != k, eso significa que al menos una de las torres fue retirada esta vez y puede haber más por hacer. Entonces volvemos f(k). Dios, amo la recursión. Curiosamente, fsiempre recurre un nivel más profundo de lo estrictamente "necesario". Cuando se genera la lista que se devolverá, la función no tiene forma de saberlo al principio.

Cuando comencé a escribir esta explicación, este programa tenía 223 bytes de longitud. Al explicar las cosas, me di cuenta de que había formas de salvar personajes, ¡así que me alegro de haber escrito esto! El mayor ejemplo es que f(l)se implementó originalmente como un bucle infinito que se rompió cuando se realizó el cálculo, antes de darme cuenta de que la recursión funcionaría. Simplemente demuestra que la primera solución que piensas no siempre será la mejor. :)

Matlab, (123) (119)

function r=m(h);p=[h rot90(h) rot90(h,2) rot90(h,3)];for i=2:size(p) p(i,:)=max(p(i,:),p(i-1,:));end;r=sum(diff(p)>0)+1

usado así:

m([
 4     3     5     2     1;
 5     4     1     3     2;
 1     5     2     4     3;
 2     1     3     5     4;
 3     2     4     1     5])

 [2 3 1 4 5 3 4 3 2 1 1 2 2 2 2 3 3 2 1 2]

C #, hasta 354 ...

Enfoque diferente al utilizado por TheBestOne.

using System;
using System.Linq;

class A
{
    static void Main(string[] h)
    {
        int m = (int)Math.Sqrt(h[0].Length),k=0;
        var x = h[0].Select(c => c - 48);
        var s = Enumerable.Range(0, m);
        for (; k < 4; k++)
        {
            (k%2 == 0 ? s : s.Reverse())
                .Select(j =>
                        (k > 0 && k < 3 ? x.Reverse() : x).Where((c, i) => (k % 2 == 0 ? i % m : i / m) == j)
                                                          .Aggregate(0, (p, c) =>
                                                                        c > p%10
                                                                            ? c + 10 + p/10*10
                                                                            : p, c => c/10))
                .ToList()
                .ForEach(Console.Write);
        }
    }
}