Pertanyaan ini didasarkan pada Menara puzzle penempatan angka (juga dikenal sebagai Pencakar Langit), yang dapat Anda mainkan online . Tujuan Anda adalah untuk mengambil solusi untuk teka-teki dan menentukan petunjuk - jumlah menara terlihat di sepanjang setiap baris dan kolom. Ini adalah kode golf, byte paling sedikit menang.

Bagaimana Towers bekerja

Solusi untuk teka-teki Towers adalah kotak Latin - n*nkotak di mana setiap baris dan kolom berisi permutasi angka yang 1dilewati n. Contoh untuk n=5adalah:

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 

Setiap baris dan kolom diberi label dengan petunjuk di setiap ujungnya seperti:

       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

Setiap petunjuk adalah angka dari 1ke nyang memberitahu Anda berapa banyak menara yang Anda "lihat" melihat sepanjang baris / kolom dari arah itu, jika angka-angka diperlakukan sebagai menara dengan ketinggian itu. Setiap menara memblokir menara yang lebih pendek di belakangnya. Dengan kata lain, menara yang Anda lihat adalah menara yang lebih tinggi dari menara mana pun sebelumnya.

Sebagai contoh, mari kita lihat baris pertama.

 2 >   4 3 5 2 1   < 3

Ini memiliki petunjuk dari 2kiri karena Anda dapat melihat 4dan 5. The 4blok 3dari pandangan dan 5blok segala sesuatu yang lain. Dari kanan, Anda dapat melihat 3menara: 1, 2, dan 5.

Persyaratan program

Tulis program atau fungsi yang menggunakan kotak angka dan keluaran atau cetak petunjuk, searah jarum jam dari kiri atas.

Memasukkan

Kotak n*nLatin dengan 2<=n<=9.

Formatnya fleksibel. Anda dapat menggunakan struktur data apa pun yang mewakili kisi atau daftar yang berisi angka atau karakter digit. Anda mungkin memerlukan pemisah antara baris atau tidak ada pemisah sama sekali. Beberapa kemungkinan adalah daftar, daftar daftar, matriks, string yang dipisahkan dengan token seperti

43521 54132 15243 21354 32415,

atau string tanpa spasi.

Anda tidak diberikan nsebagai bagian dari input.

Keluaran

Kembalikan atau cetak petunjuk mulai dari kiri atas dan searah jarum jam. Jadi, pertama membaca petunjuk atas ke kanan, kemudian petunjuk kanan membaca ke bawah, lalu petunjuk bawah membaca ke kiri, petunjuk kiri membaca ke atas.

Ini akan menjadi 23145 34321 12222 33212contoh sebelumnya

       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

Sama seperti untuk input, Anda dapat menggunakan daftar, string, atau struktur yang dipesan. Keempat "kelompok" dapat dipisahkan atau tidak, dalam struktur bersarang atau datar. Tapi, formatnya harus sama untuk setiap grup.

Contoh kasus uji:

(Format input / output Anda tidak harus sama dengan ini.)

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

Untuk kenyamanan Anda, berikut adalah kasus uji yang sama dalam format string datar.

>> 1221

21
12
21
12

>> 312231123

122
221
123
321

>> 4352154132152432135432415

23145
34321
12222
33212

>> 264137589729683145597461823618572934153926478375248691831794256942815367486359712

422333321
133222233
432123322
312433225

APL 19

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

(bermain golf lebih banyak setelah saran ngn, terima kasih)

Penjelasan:

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

Cobalah di tryapl.org

Python 2, 115 byte

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

Ada banyak sekali daftar membalik terjadi di sana.

Mengambil input sebagai daftar bersarang (mis. Panggilan dengan 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]])). Output adalah daftar datar tunggal.

Tidak Terkumpul:

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

Alternatif 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

Saya tidak tahu mengapa ini bekerja dengan daftar pemahaman, tetapi chuck NameErrordengan pemahaman ...

Agak terlalu lama, tetapi jika ada yang tertarik - ya, ini bisa menjadi 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 byte

V4=Q_CQ~Yml{meS<dhkUd_Q)Y

Port Pyth wajib.

Masukkan daftar melalui STDIN, mis [[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]].

Coba online ... adalah apa yang akan saya katakan tetapi sayangnya, untuk alasan keamanan, penerjemah online melarang penggunaan eval pada kurung bersarang. Coba kode penyelesaiannya JcQ5V4=J_CJ~Yml{meS<dhkUd_J)Y, dan masukan seperti daftar rata seperti [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].

(Terima kasih kepada @isaacg yang membantu bermain golf beberapa byte)

CJam, 29 27 byte

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

Masukan seperti

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

Output seperti

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

Bagaimana itu bekerja

Ide dasarnya adalah membuat kode bekerja di sepanjang baris dan memutar grid berlawanan arah jarum jam 4 kali. Untuk menghitung menara, saya menaikkan setiap menara sejauh itu tidak membuat "perbedaan visual" (yaitu, jangan mengubahnya jika terlihat, atau menariknya ke ketinggian yang sama dengan menara di depan itu), dan kemudian saya menghitung ketinggian yang berbeda.

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

Diuji di sini.

J, 35 karakter

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

Contoh:

   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

Coba di sini.

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 byte

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

Pemakaian:

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

Mengevaluasi di konsol JavaScript browser (saya menggunakan Firefox 34.0, sepertinya tidak berfungsi di Chrome 39 ??) Uji dengan:

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

Inilah inkarnasi kode yang tidak dikenali saat ini - semakin sulit untuk diikuti:

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

Saya sengaja tidak melihat jawaban lain, saya ingin melihat apakah saya bisa mengerjakan sesuatu sendiri. Pendekatan saya adalah untuk meratakan array input ke array satu dimensi dan precompute offset ke baris dari keempat arah. Kemudian saya menggunakan shift kanan untuk menguji apakah menara berikutnya salah dan jika itu, maka menambah penghitung untuk setiap baris.

Saya berharap ada banyak cara untuk meningkatkan ini, mungkin tidak menghitung ulang offset, melainkan menggunakan semacam overflow / modulo pada array input 1D? Dan mungkin menggabungkan loop saya, dapatkan lebih fungsional, deduplicate.

Setiap saran akan dihargai!

Pembaruan # 1 : Kemajuan, kami memiliki teknologi! Saya dapat menyingkirkan offset yang telah dihitung dan melakukannya sesuai dengan operator ternary yang dirangkai. Juga bisa menyingkirkan pernyataan if saya dan mengubah loop for menjadi whiles.

Pembaruan # 2 : Ini cukup membuat frustrasi; tidak ada pesta pizza untuk saya. Saya pikir fungsional dan menggunakan rekursi akan mengurangi banyak byte, tetapi beberapa percobaan pertama saya akhirnya menjadi lebih besar sebanyak 100 karakter! Dalam keputus-asaan, saya pergi menggunakan babi seluruh fungsi lemak ES6 untuk benar-benar pare itu. Kemudian saya mengambil untuk mengganti operator boolean dengan yang aritmatika dan menghapus parens, semi-titik dua dan spasi di mana pun saya bisa. Saya bahkan berhenti mendeklarasikan vars saya dan mencemari namespace global dengan simbol lokal saya. Kotor, kotor. Setelah semua upaya itu, saya mengalahkan skor Pembaruan # 1 saya dengan 8 karakter kekalahan, ke 256. Blargh!

Jika saya menerapkan optimasi kejam yang sama dan trik ES6 ke fungsi Pembaruan # 1 saya, saya akan mengalahkan skor ini dengan satu mil. Saya dapat melakukan Pembaruan # 3 hanya untuk melihat seperti apa nantinya.

Pembaruan # 3 : Ternyata pendekatan rekursif panah lemak punya lebih banyak kehidupan di dalamnya, saya hanya perlu bekerja dengan input 2 dimensi secara langsung daripada meratakannya dan menjadi lebih baik tentang memanfaatkan lingkup penutupan. Saya menulis ulang perhitungan offset array dalam dua kali dan mendapatkan skor yang sama, jadi pendekatan ini mungkin hampir habis!

Java, hanya 352 350 325 byte ...

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

Masukan seperti 43521 54132 15243 21354 32415

Output seperti: 23145343211222233212

Bertakuk:

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

Setiap tips akan sangat dihargai!

Python 2 - 204 byte

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

Ini mungkin golf yang sangat buruk. Saya pikir masalahnya menarik, jadi saya memutuskan untuk mengatasinya tanpa melihat solusi orang lain. Saat saya mengetik kalimat ini, saya belum melihat jawaban atas pertanyaan ini. Saya tidak akan terkejut jika orang lain telah melakukan program Python yang lebih pendek;)

Contoh I / O

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

Anda dapat memasukkan spasi putih dalam input. Cukup banyak di mana saja, jujur. Selama Anda bisa eval(), itu akan berhasil.

Penjelasan

Satu-satunya bagian yang menarik dari program ini adalah baris pertama. Ini mendefinisikan fungsi f(l)yang memberitahu Anda berapa banyak menara yang dapat dilihat secara berturut-turut, dan program lainnya hanya menerapkan fungsi itu untuk setiap posisi yang memungkinkan.

Saat dipanggil, ia menemukan panjang ldan menyimpannya dalam variabel n. Kemudian ia menciptakan variabel baru kdengan pemahaman daftar yang cukup mengerikan ini:

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

Tidak terlalu buruk ketika Anda memecahnya. Karena n==len(l), segala sesuatu sebelum yang ifadil mewakili l. Namun, menggunakan ifkami dapat menghapus beberapa elemen dari daftar. Kami membuat daftar dengan ([0]+list(l)), yang hanya " ldengan 0menambahkan ke awal" (abaikan panggilan ke list(), itu hanya ada karena kadang l- kadang generator dan kami perlu memastikan itu sebenarnya daftar di sini). l[c]hanya dimasukkan ke dalam daftar akhir jika lebih besar dari ([0]+list(l))[c]. Ini melakukan dua hal:

• Karena ada elemen baru di awal daftar, indeks masing-masing l[c]menjadi c+1. Kami secara efektif membandingkan setiap elemen dengan elemen di sebelah kiri. Jika lebih besar, itu terlihat. Kalau tidak, itu tersembunyi dan dihapus dari daftar.
• Menara pertama selalu terlihat karena tidak ada yang dapat memblokirnya. Karena kita menempatkan 0 di awal, menara pertama selalu lebih besar. (Jika kita tidak melakukan ini [0]+omong kosong dan hanya dibandingkan l[c]dengan l[c-1], Python akan membandingkan menara pertama dengan yang terakhir (Anda dapat mengindeks ke dalam daftar dari akhir dengan -1, -2, dll), jadi jika menara terakhir adalah lebih tinggi daripada pertama kita akan mendapatkan hasil yang salah.

Ketika semua dikatakan dan dilakukan, lberisi beberapa menara dan kberisi masing-masing menara yang tidak lebih pendek dari tetangga terdekatnya ke kiri. Jika tidak ada dari mereka (misalnya untuk f([1,2,3,4,5])), maka l == k. Kami tahu tidak ada yang tersisa untuk dilakukan dan dikembalikan n(panjang daftar). Jika l != k, itu berarti setidaknya satu dari menara telah dihapus kali ini dan mungkin ada lebih banyak yang harus dilakukan. Jadi kita kembali f(k). Ya Tuhan, aku suka rekursi. Menariknya, fselalu berulang satu tingkat lebih dalam daripada yang benar-benar "diperlukan". Ketika daftar yang akan dihasilkan dihasilkan, fungsi tidak memiliki cara untuk mengetahui hal itu pada awalnya.

Ketika saya mulai menulis penjelasan ini, program ini panjangnya 223 byte. Sambil menjelaskan hal-hal yang saya sadari bahwa ada cara untuk menyelamatkan karakter, jadi saya senang saya mengetik ini! Contoh terbesar adalah yang f(l)awalnya diimplementasikan sebagai loop tak terbatas yang pecah ketika perhitungan dilakukan, sebelum saya menyadari rekursi akan bekerja. Itu hanya menunjukkan bahwa solusi pertama yang Anda pikirkan tidak akan selalu menjadi yang terbaik. :)

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

digunakan seperti ini:

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

Pendekatan yang berbeda dari yang digunakan 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);
        }
    }
}