Esta pergunta é baseada no quebra-cabeça de posicionamento numérico Towers (também conhecido como Arranha-céus), que você pode jogar online . Seu objetivo é pegar uma solução para o quebra-cabeça e determinar as pistas - o número de torres visíveis ao longo de cada linha e coluna. Isso é código de golfe, e o menor número de bytes vence.

Como funciona a Towers

A solução para um quebra-Towers é um quadrado latino - uma n*ngrade em que cada linha e coluna contém uma permutação dos números 1através n. Um exemplo para n=5é:

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 linha e coluna é rotulada com uma pista em cada extremidade, 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 é um número de 1até nque informa quantas torres você "vê" olhando ao longo da linha / coluna dessa direção, se os números forem tratados como torres com essa altura. Cada torre bloqueia torres mais curtas atrás dela. Em outras palavras, as torres que você pode ver são as mais altas do que qualquer torre antes delas.

Por exemplo, vamos olhar para a primeira linha.

 2 >   4 3 5 2 1   < 3

Tem uma pista da 2esquerda, porque você pode ver o 4e o 5. O 4bloqueia a 3visão e 5bloqueia tudo o resto. Da direita, você pode ver 3torres: 1, 2, e 5.

Requisitos do programa

Escreva um programa ou função que capte a grade de números e produza ou imprima as pistas, girando no sentido horário a partir do canto superior esquerdo.

Entrada

Um n*nquadrado latino com 2<=n<=9.

O formato é flexível. Você pode usar qualquer estrutura de dados que represente uma grade ou lista contendo números ou caracteres de dígitos. Você pode precisar de um separador entre as linhas ou nenhum separador. Algumas possibilidades são uma lista, uma lista de listas, uma matriz, uma sequência separada por token, como

43521 54132 15243 21354 32415,

ou uma string sem espaços.

Você não é dado ncomo parte da entrada.

Saída

Retorne ou imprima as pistas começando no canto superior esquerdo e indo no sentido horário. Então, primeiro as pistas superiores lendo para a direita, depois as pistas certas lendo para baixo, depois as pistas inferiores lendo para a esquerda, e as pistas esquerdas para cima.

Isso seria 23145 34321 12222 33212para o exemplo 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

Assim como para a entrada, você pode usar uma lista, sequência ou qualquer estrutura ordenada. Os quatro "grupos" podem ser separados ou não, em uma estrutura aninhada ou plana. Mas, o formato deve ser o mesmo para cada grupo.

Exemplos de casos de teste:

(Seu formato de entrada / saída não precisa ser o mesmo que este.)

>> [[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 sua conveniência, aqui estão os mesmos casos de teste em um formato de sequência simples.

>> 1221

21
12
21
12

>> 312231123

122
221
123
321

>> 4352154132152432135432415

23145
34321
12222
33212

>> 264137589729683145597461823618572934153926478375248691831794256942815367486359712

422333321
133222233
432123322
312433225

APL 19

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

(jogou um pouco mais depois da sugestão da ngn, obrigado)

Explicação:

(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)  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

Experimente em 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

Há uma enorme quantidade de lista rolando por aí.

Recebe a entrada como uma lista aninhada (por exemplo, ligue com 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]])). Saída é uma lista simples e plana.

Ungolfed:

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

Não faço ideia por que isso funciona com uma compreensão de lista, mas sim NameErrorcom uma compreensão definida ...

Um pouco longo, mas se alguém estiver interessado - sim, é possível obter isso em um 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]]

Pitão , 25 bytes

V4=Q_CQ~Yml{meS<dhkUd_Q)Y

Porta Pyth obrigatória.

Insira a lista via STDIN, por exemplo [[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]].

Experimente on-line ... é o que eu diria, mas, infelizmente, por razões de segurança, o intérprete on-line não permite o uso de eval em colchetes aninhados. Experimente o código da solução alternativa JcQ5V4=J_CJ~Yml{meS<dhkUd_J)Ye insira como uma lista nivelada 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].

(Obrigado a @isaacg, que ajudou a obter alguns bytes de golfe)

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]]

Saída como

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

Como funciona

A idéia básica é fazer com que o código funcione ao longo das linhas e gire a grade no sentido anti-horário 4 vezes. Para contar as torres, estou levantando cada torre o máximo que não fizer uma "diferença visual" (ou seja, não a altere se estiver visível, ou puxe-a para a mesma altura da torre em frente a ) e, em seguida, estou contando alturas distintas.

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∊¨↓(∘.>⍨⍵)≥∘.<⍨⍳⍴⍵}¨↓(⌽∘⍉⍪⊢⍪⊖∘⍉⍪⊖∘⌽)⍵}

Testado aqui.

J, 35 caracteres

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

Exemplo:

   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

Experimente aqui.

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,[],[])

Avalie no console JavaScript do navegador (usei o Firefox 34.0, não parece funcionar no Chrome 39 ??) Teste com:

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]]));

Aqui está a encarnação atual do código não destruído - está ficando mais 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, não olhei para nenhuma das outras respostas, queria ver se eu mesmo poderia descobrir algo. Minha abordagem foi achatar as matrizes de entrada em uma matriz unidimensional e pré-calcular deslocamentos para as linhas de todas as quatro direções. Então usei shift à direita para testar se a próxima torre era falsa e, se era, então incrementava o contador para cada linha.

Espero que haja muitas maneiras de melhorar isso, talvez não pré-calcule as compensações, mas use algum tipo de estouro / módulo na matriz de entrada 1D? E talvez combine meus loops, fique mais funcional, desduplicado.

Todas as sugestões serão apreciadas!

Atualização # 1 : Progresso, nós temos a tecnologia! Consegui me livrar das compensações pré-calculadas e fazê-las alinhadas com os operadores ternários ligados. Também foi capaz de se livrar da minha declaração if e converter os loops for em whiles.

Atualização # 2 : Isso é bastante frustrante; nenhuma festa de pizza para mim. Eu imaginei que ficar funcional e usar a recursão reduziria muitos bytes, mas minhas primeiras tentativas acabaram sendo maiores em até 100 caracteres! Em desespero, eu comecei a usar as funções de flechas de gordura ES6 para realmente reduzi-las. Depois, substituí os operadores booleanos pelos aritméticos e remova parênteses, ponto e vírgula e espaços sempre que possível. Eu até parei de declarar meus vars e poluí o namespace global com meus símbolos locais. Sujo, sujo. Depois de todo esse esforço, superei a pontuação da Atualização # 1 em 8 caracteres, até 256. Blargh!

Se eu aplicasse as mesmas otimizações cruéis e truques do ES6 na minha função Atualização # 1, superaria essa pontuação por uma milha. Eu posso fazer uma atualização nº 3 apenas para ver como isso seria.

Atualização # 3 : Acontece que a abordagem recursiva da seta gorda tinha muito mais vida útil, eu só precisava trabalhar com a entrada bidimensional diretamente, em vez de achatá-la e melhorar a alavancagem dos escopos de fechamento. Reescrevi os cálculos de deslocamento da matriz interna duas vezes e obtive a mesma pontuação, portanto, essa abordagem pode estar quase esgotada!

Apenas Java 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

Saída como: 23145343211222233212

Recuado:

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;
        }
    }
}

Quaisquer dicas seriam extremamente apreciadas!

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 é provavelmente um golfe realmente ruim. Eu pensei que o problema era interessante, então decidi resolvê-lo sem olhar para a solução de mais ninguém. Enquanto escrevo esta frase, ainda não vi as respostas sobre essa pergunta. Eu não ficaria surpreso se alguém já tivesse feito um programa Python mais curto;)

Exemplo 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, você pode incluir espaço em branco na entrada. Praticamente em qualquer lugar, honestamente. Contanto que você puder eval(), funcionará.

Explicação

A única parte interessante deste programa é a primeira linha. Ele define uma função f(l)que informa quantas torres podem ser vistas seguidas, e o restante do programa está apenas aplicando essa função em todas as posições possíveis.

Quando chamado, ele encontra o comprimento de le o salva em uma variável n. Em seguida, cria uma nova variável kcom essa compreensão bastante monstruosa da lista:

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

Não é tão ruim quando você o divide. Desde então n==len(l), tudo antes do ifjusto representa l. No entanto, usando ifpodemos remover alguns elementos da lista. Nós construímos uma lista com ([0]+list(l)), que é apenas " lcom um valor 0adicionado ao início" (ignore a chamada para list(), que está lá apenas porque às vezes lé um gerador e precisamos garantir que seja realmente uma lista aqui). l[c]só é colocado na lista final se for maior que ([0]+list(l))[c]. Isso faz duas coisas:

• Como existe um novo elemento no início da lista, o índice de cada um l[c]se torna c+1. Estamos comparando efetivamente cada elemento ao elemento à esquerda dele. Se é maior, é visível. Caso contrário, ele será oculto e removido da lista.
• A primeira torre é sempre visível porque não há nada que possa bloqueá-la. Como colocamos 0 no começo, a primeira torre é sempre maior. (Se não fizer isso [0]+absurdo e apenas em relação l[c]a l[c-1], Python iria comparar a primeira torre para o último (você pode indexar em uma lista a partir da extremidade -1, -2etc.), de modo que se a última torre era mais alto do que o primeiro, teríamos o resultado errado.

Quando tudo estiver dito e feito, lcontém um certo número de torres e kcada uma delas que não é mais curta que seu vizinho imediato à esquerda. Se nenhum deles foi (por exemplo, para f([1,2,3,4,5])), então l == k. Sabemos que não há mais o que fazer e retornar n(o comprimento da lista). Se l != kisso significa que pelo menos uma das torres foi removida desta vez e pode haver mais o que fazer. Então, voltamos f(k). Deus, eu amo recursão. Curiosamente, fsempre recursa um nível mais profundo do que o estritamente "necessário". Quando a lista que será retornada é gerada, a função não tem como saber disso a princípio.

Quando comecei a escrever essa explicação, esse programa tinha 223 bytes. Ao explicar as coisas, percebi que havia maneiras de salvar personagens, então estou feliz por ter digitado isso! O maior exemplo é que f(l)foi originalmente implementado como um loop infinito que foi interrompido quando a computação foi concluída, antes que eu percebesse que a recursão funcionaria. Isso mostra que a primeira solução que você pensa nem sempre é a melhor. :)

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 assim:

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 #, até 354 ...

Abordagem diferente da usada pelo 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);
        }
    }
}