To pytanie jest oparte na wieżach z układaniem liczb (znanych również jako Wieżowce), w które można grać online . Twoim celem jest rozwiązanie zagadki i ustalenie wskazówek - liczby wież widocznych wzdłuż każdego rzędu i kolumny. To jest kod golfowy, więc wygrywa najmniej bajtów.

Jak działa Towers

Rozwiązaniem puzzle Towers to kwadrat łaciński - n*nsiatka, w której każdy wiersz i kolumna zawiera permutacji liczb 1dzięki n. Przykładem n=5jest:

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 

Każdy wiersz i kolumna jest oznaczony wskazówką na każdym końcu, na przykład:

       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

Każda wskazówka jest liczbą od 1do, nktóra mówi, ile wież „widzisz” patrząc wzdłuż rzędu / kolumny z tego kierunku, jeśli liczby są traktowane jak wieże o tej wysokości. Każda wieża blokuje za nią krótsze wieże. Innymi słowy, wieże, które można zobaczyć, są wyższe niż jakakolwiek wieża przed nimi.

Na przykład spójrzmy na pierwszy wiersz.

 2 >   4 3 5 2 1   < 3

Ma wskazówkę 2z lewej, ponieważ możesz zobaczyć 4i 5. W 4blokuje 3od wzroku i 5blokuje wszystko. Z prawej strony widać 3wieże: 1, 2, i 5.

Wymagania programu

Napisz program lub funkcję, która pobiera siatkę liczb i wyników lub drukuje wskazówki, postępując zgodnie z ruchem wskazówek zegara od lewego górnego rogu.

Wkład

n*nŁacińsko-kwadrat z 2<=n<=9.

Format jest elastyczny. Możesz użyć dowolnej struktury danych, która reprezentuje siatkę lub listę zawierającą cyfry lub znaki cyfrowe. Może być wymagany separator między wierszami lub brak separatora. Niektóre możliwości to lista, lista list, macierz, ciąg znaków oddzielony tokenami

43521 54132 15243 21354 32415,

lub ciąg bez spacji.

Nie jesteś podany njako część danych wejściowych.

Wydajność

Wróć lub wydrukuj wskazówki, zaczynając od lewego górnego rogu i postępując zgodnie z ruchem wskazówek zegara. Więc najpierw górne wskazówki czytają w prawo, następnie prawe wskazówki czytają w dół, następnie dolne wskazówki czytają w lewo, lewe wskazówki czytają w górę.

Tak byłoby 23145 34321 12222 33212w poprzednim przykładzie

       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

Podobnie jak w przypadku danych wejściowych, możesz użyć listy, łańcucha lub dowolnej uporządkowanej struktury. Cztery „grupy” można rozdzielić lub nie, w strukturze zagnieżdżonej lub płaskiej. Ale format musi być taki sam dla każdej grupy.

Przykładowe przypadki testowe:

(Twój format wejścia / wyjścia nie musi być taki sam jak te.)

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

Dla Twojej wygody, oto te same przypadki testowe w formacie płaskiego łańcucha.

>> 1221

21
12
21
12

>> 312231123

122
221
123
321

>> 4352154132152432135432415

23145
34321
12222
33212

>> 264137589729683145597461823618572934153926478375248691831794256942815367486359712

422333321
133222233
432123322
312433225

APL 19

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

(grałem trochę więcej po sugestii NNN, dzięki)

Wyjaśnienie:

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

Wypróbuj na tryapl.org

Python 2, 115 bajtów

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

Tam dzieje się okropnie dużo przerzucanych list.

Pobiera dane wejściowe jako listę zagnieżdżoną (np. Połączenie z 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]])). Dane wyjściowe to pojedyncza płaska lista.

Nie golfowany:

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

Alternatywa 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

Nie mam pojęcia, dlaczego to działa ze zrozumieniem listy, ale rzuca się NameErrorna określone rozumienie ...

Trochę za długo, ale jeśli ktoś jest zainteresowany - tak, można sprowadzić to do 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 bajtów

V4=Q_CQ~Yml{meS<dhkUd_Q)Y

Obowiązkowy port Pyth.

Wprowadź listę za pomocą STDIN, np [[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]].

Wypróbuj online ... powiedziałbym, ale niestety ze względów bezpieczeństwa tłumacz online nie pozwala na użycie eval w nawiasach zagnieżdżonych. JcQ5V4=J_CJ~Yml{meS<dhkUd_J)YZamiast tego wypróbuj kod obejścia i wprowadź jako spłaszczoną listę, np [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].

(Dzięki @isaacg, który pomógł rozegrać kilka bajtów)

CJam, 29 27 bajtów

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

Dane wejściowe jak

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

Dane wyjściowe jak

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

Jak to działa

Podstawową ideą jest, aby kod działał wzdłuż wierszy i obracał siatkę 4 razy w lewo. Aby policzyć wieże, podnoszę każdą wieżę, o ile nie robi to „różnicy wizualnej” (tj. Nie zmieniaj jej, jeśli jest widoczna, ani nie podciągaj jej na tę samą wysokość wieży przed it), a następnie liczę różne wysokości.

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

Testowane tutaj.

J, 35 znaków

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

Przykład:

   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

Wypróbuj tutaj.

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 bajtów

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}])&

Stosowanie:

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

Ocena w konsoli JavaScript przeglądarki (użyłem Firefoksa 34.0, wydaje się, że nie działa w Chrome 39?) Testuj z:

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

Oto obecne wcielenie nieoznakowanego kodu - coraz trudniej jest go śledzić:

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

Celowo nie spojrzałem na żadną z innych odpowiedzi, chciałem sprawdzić, czy sam mogę coś wymyślić. Moje podejście polegało na spłaszczeniu tablic wejściowych do tablicy jednowymiarowej i wstępnym obliczeniu przesunięć do wierszy ze wszystkich czterech kierunków. Następnie użyłem Shift w prawo, aby sprawdzić, czy następna wieża była fałszywa, a jeśli tak, to zwiększ licznik dla każdego rzędu.

Mam nadzieję, że istnieje wiele sposobów, aby to poprawić, być może nie dokonaj wstępnego obliczenia przesunięć, ale raczej zastosuj pewnego rodzaju przepełnienie / modulo na tablicy wejściowej 1D? I może połącz moje pętle, stań się bardziej funkcjonalny, deduplikuj.

Wszelkie sugestie będą mile widziane!

Aktualizacja nr 1 : Postęp, mamy technologię! Byłem w stanie pozbyć się wstępnie obliczonych przesunięć i wykonać je zgodnie z połączonymi ze sobą operatorami trójskładnikowymi. Był także w stanie pozbyć się mojej instrukcji if i przekonwertować pętle for na while.

Aktualizacja nr 2 : Jest to dość frustrujące; dla mnie nie ma pizzy. Pomyślałem, że przejście na funkcjonalność i użycie rekurencji zmniejszy liczbę bajtów, ale moje pierwsze próby zakończyły się powiększeniem nawet o 100 znaków! W desperacji zdecydowałem się na użycie funkcji strzałek z tłuszczu ES6, aby naprawdę je spowolnić. Potem zabrałem się do zastępowania operatorów logicznych operacjami arytmetycznymi i usuwania parenów, średników i spacji, gdzie tylko mogłem. Zrezygnowałem nawet z deklarowania moich zmiennych i zanieczyściłem globalną przestrzeń nazw moimi lokalnymi symbolami. Brudny, brudny. Po całym tym wysiłku pobiłem swój wynik aktualizacji nr 1 aż o 8 znaków, aż do 256. Blargh!

Gdybym zastosował te same bezwzględne optymalizacje i sztuczki ES6 do mojej funkcji aktualizacji nr 1, pobiłbym ten wynik o milę. Mogę zrobić aktualizację nr 3 tylko po to, żeby zobaczyć, jak by to wyglądało.

Aktualizacja nr 3 : Okazało się, że podejście rekurencyjne z grubą strzałą miało o wiele więcej życia, po prostu musiałem bezpośrednio pracować z dwuwymiarowym wejściem zamiast spłaszczać go i lepiej wykorzystywać zakresy zamknięcia. Dwa razy przepisałem obliczenia przesunięcia tablicy wewnętrznej i uzyskałem ten sam wynik, więc to podejście może być bliskie wyczerpania!

Tylko Java 352 350 325 bajtów ...

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

Dane wejściowe jak 43521 54132 15243 21354 32415

Dane wyjściowe takie jak: 23145343211222233212

Zębaty:

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

Wszelkie wskazówki będą mile widziane!

Python 2 - 204 bajty

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

To prawdopodobnie bardzo kiepski golf. Myślałem, że problem jest interesujący, więc postanowiłem go rozwiązać, nie patrząc na czyjeś rozwiązanie. Kiedy piszę to zdanie, muszę jeszcze spojrzeć na odpowiedzi na to pytanie. Nie zdziwiłbym się, gdyby ktoś inny zrobił już krótszy program w języku Python;)

Przykład we / wy

$ ./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]

Opcjonalnie możesz włączyć białe znaki na wejściu. Prawie wszędzie, szczerze mówiąc. Tak długo, jak to możliwe eval(), będzie działać.

Wyjaśnienie

Jedyną interesującą częścią tego programu jest pierwsza linia. Definiuje funkcję, f(l)która mówi, ile wież można zobaczyć z rzędu, a reszta programu po prostu stosuje tę funkcję do każdej możliwej pozycji.

Po wywołaniu znajduje długość li zapisuje ją w zmiennej n. Następnie tworzy nową zmienną kz tym dość potwornym zrozumieniem listy:

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

Nie jest tak źle, kiedy się psujesz. Ponieważ n==len(l)wszystko przed ifsprawiedliwymi reprezentuje l. Jednak za pomocą ifmożemy usunąć niektóre elementy z listy. Tworzymy listę z ([0]+list(l)), która jest po prostu „ lz 0dodanym na początku” (zignoruj ​​wywołanie do list(), to tylko tam, ponieważ czasami ljest generator i musimy upewnić się, że faktycznie jest to lista). l[c]jest umieszczany na końcowej liście, tylko jeśli jest większy niż ([0]+list(l))[c]. To robi dwie rzeczy:

• Ponieważ na początku listy znajduje się nowy element, indeks każdego l[c]staje się c+1. Skutecznie porównujemy każdy element z elementem po jego lewej stronie. Jeśli jest większy, jest widoczny. W przeciwnym razie jest ukryty i usunięty z listy.
• Pierwsza wieża jest zawsze widoczna, ponieważ nic nie może jej zablokować. Ponieważ na początku stawiamy 0, pierwsza wieża jest zawsze większa. (Jeśli nie zrobić to [0]+nonsens i tylko w stosunku l[c]do l[c-1]Python by porównać pierwszej wieży do ostatniego (można indeks do listy od końca z -1, -2itp), więc jeżeli ostatnia wieża była wyższa niż po pierwsze otrzymalibyśmy zły wynik.

Kiedy wszystko jest powiedziane i zrobione, lzawiera pewną liczbę wież i kzawiera każdą z nich, która nie jest krótsza niż jej bezpośredni sąsiad po lewej stronie. Jeśli żaden z nich nie był (np. Za f([1,2,3,4,5])), to l == k. Wiemy, że nie ma już nic do zrobienia i powrotu n(długość listy). Jeśli l != kto oznacza, że ​​przynajmniej jedna z wież została tym razem usunięta i może być więcej do zrobienia. Więc wracamy f(k). Boże, kocham rekursję. Co ciekawe, fzawsze powtarza się o jeden poziom głębiej niż jest to absolutnie „konieczne”. Po wygenerowaniu listy, która zostanie zwrócona, funkcja nie może na początku tego wiedzieć.

Kiedy zacząłem pisać to wyjaśnienie, ten program miał 223 bajty. Podczas wyjaśniania rzeczy zdałem sobie sprawę, że istnieją sposoby na uratowanie postaci, więc cieszę się, że to napisałem! Największym przykładem jest to, że f(l)pierwotnie została zaimplementowana jako nieskończona pętla, która została przerwana, kiedy obliczenia zostały wykonane, zanim zdałem sobie sprawę, że rekurencja zadziała. To po prostu pokazuje, że pierwsze rozwiązanie, o którym myślisz, nie zawsze będzie najlepsze. :)

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

używane w ten sposób:

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

Zastosowano inne podejście niż 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);
        }
    }
}