Integer, Merakit!

30

Tugas Anda adalah untuk merakit bilangan bulat dari 1ke N(diberikan sebagai input) menjadi persegi panjang lebar Wdan tinggi H(juga diberikan sebagai input). Angka-angka individual dapat dirotasi dengan kelipatan 90 derajat, tetapi angka-angka tersebut harus muncul sebagai blok yang bersebelahan dalam persegi panjang. Artinya, Anda tidak dapat memecah salah satu angka menjadi beberapa digit dan menempatkan digit dalam persegi panjang secara terpisah, Anda juga tidak bisa menekuk tiga digit angka di sudut. Anda dapat menganggap setiap angka sebagai batu bata dari mana Anda membangun dinding.

Berikut ini sebuah contoh. Katakan input Anda (N, W, H) = (12, 5, 3). Salah satu solusi yang mungkin adalah:

18627
21901
53114

Untuk kejelasan, berikut adalah dua salinan dari kisi ini, satu dengan angka satu digit disembunyikan dan satu dengan angka dua digit disembunyikan:

1####    #8627
2##01    #19##
##11#    53##4

Tidak apa-apa jika persegi panjang tidak dapat dibongkar lagi dengan cara yang unik. Misalnya, dalam contoh di atas, 12bisa juga ditempatkan seperti ini:

#####    18627
21#01    ##9##
##11#    53##4

Aturan

Anda mungkin menganggap bahwa Nadalah positif dan W*Hsesuai dengan jumlah digit dalam bilangan bulat dari 1ke Ninklusif, dan bahwa ubin persegi panjang ke nomor yang diberikan ada. Saat ini saya tidak memiliki bukti apakah ini selalu mungkin, tetapi saya akan tertarik pada satu jika Anda melakukannya.

Keluaran dapat berupa string yang dipisahkan dengan baris tunggal atau daftar string (satu untuk setiap baris) atau daftar daftar bilangan bulat satu digit (satu untuk setiap sel).

Hasil kiriman Anda harus determinstik dan Anda harus dapat menangani semua kasus uji dalam waktu kurang dari satu menit pada mesin desktop yang masuk akal.

Anda dapat menulis sebuah program atau fungsi dan menggunakan salah satu metode standar kami untuk menerima input dan memberikan output.

Anda dapat menggunakan bahasa pemrograman apa pun , tetapi perhatikan bahwa celah ini dilarang secara default.

Ini adalah , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.

Uji Kasus

Kecuali yang pertama, tidak ada yang unik. Setiap test case N W Hdiikuti oleh kemungkinan output. Pastikan jawaban Anda bekerja ketika persegi panjang terlalu sempit untuk menulis angka yang lebih besar secara horizontal.

1 1 1
1

6 6 1
536142

6 2 3
16
25
34

10 1 11
1
0
8
9
2
6
7
3
1
5
4

11 13 1
1234567891011

27 9 5
213112117
192422581
144136119
082512671
205263272

183 21 21
183116214112099785736
182516114011998775635
181116013911897765534
180415913811796755433
179115813711695745332
178315713611594735231
177115613511493725130
176215513411392715029
175115413311291704928
174115313211190694827
173115213111089684726
172015113010988674625
171915012910887664524
170814912810786654423
169714812710685644322
168614712610584634221
167514612510483624120
166414512410382614019
165314412310281603918
164214312210180593817
163114212110079583716

200 41 12
81711132917193661114105533118936111184136
50592924448815915414562967609909953662491
89529721161671582389717813151113658811817
41418184511110119010183423720433017331118
35171183614003547461181197275184300111711
41874381132041861871718311415915921116264
11914245014112711011594492626831219331845
17125112629222085166344707736090956375181
94507611291431121128817413566319161275711
11011540021119913511011169939551729880780
92725141607727665632702567369893534277304
78118311405621148296417218591118562161856
Martin Ender
sumber
8
Apakah ada bukti bahwa ini selalu mungkin?
Fatalkan
@Fatalize Pertanyaan bagus sebenarnya. Anda dapat berasumsi bahwa itu mungkin untuk semua input yang diberikan, tetapi bukti yang baik akan menarik.
Martin Ender
@Fatalize: Setidaknya dalam kasus input sepele (10, 1, 1), itu tidak mungkin (dengan asumsi bahwa semua angka dari 1 hingga NHARUS digunakan dalam konstruksi). Jika kendala itu dipegang, luas persegi panjang dalam unit harus setidaknya jumlah digit 1..Nuntuk memungkinkannya. Jika kendala itu rileks, itu mungkin dalam semua kasus (tapi kemudian tantangannya tidak terlalu menyenangkan: P)
Sebastian Lenartowicz
2
@SebastianLenartowicz: Saya pikir Anda merindukan bagian di mana dikatakan luas kotak cocok dengan jumlah digit angka dalam [1, N]. Jika N == 10, maka lebar dan tinggi harus 1 dan 11. Jika lebar atau tinggi adalah 1, masalah ini selalu dapat dipecahkan.
Yay295
1
@ MartinEnder Tantangan sebaliknya bisa menarik juga: Npersegi panjang digit sebagai input (dan akhirnya , tetapi program dapat menghitungnya dari lebar dan tinggi), dan program perlu memeriksa apakah persegi panjang adalah jawaban tepat untuk tantangan ini. ...
Dada

Jawaban:

3

Pyth, 35 byte

juum+WghHl+dQd~tQN<+.TGmkeHeH)_BvzY

Kredit ke mbomb007. Saya menggunakan algoritme-nya. Awalnya saya hanya ingin membantu Steven H., tetapi kemudian saya benar-benar ingin melihat versi singkat.

Mengambil Npada baris pertama, dan W,Hpada baris kedua: Cobalah online: Demonstrasi

Menemukan bug jahat dalam implementasi Pyth .[(kesalahan saya sendiri, sejak saya mengimplementasikannya). Harus memperbaikinya besok. Ini menghasilkan +3 byte.

Penjelasan:

juum+WghHl+dQd~tQN<+.TGmkeHeH)_BvzY
                                  Y   start with the empty list []
                                      I'll perform all operations on this list. 
                                      Sometimes it is called G, sometimes N. 
                                vz    read the second line and evaluate it: [W, H]
                              _B      bifurcate it with reverse: [[W, H], [H, W]]
 u                                    for each pair H in ^:
                    .TG                  transpose G
                   +   mkeH              append H[1] empty strings
                  <        eH            use only the first H[1] strings
                                         lets call this result N
  u                          )           modify N, until it doesn't change anymore:
   m                        N               map each d in N to:
     WghHl+dQ                                  if H[0] >= len(d+Q):
    +        d  Q                                 d + Q
              ~t                                  and decrement Q by 1
             d                                 else:
                                                  d
j                                     at the end print every row on a separate line
Jakube
sumber
7

Python 2, 210 200 byte

Sunting: Bekerja sekarang!

Diisi dari atas ke bawah, kiri ke kanan, dimulai dengan angka terbesar. Kemudian, transpos dan lakukan lagi. Kemudian transpos dan cetak. Saya harus memberi ruang agar transposisi dapat bekerja, karena garisnya belum terlalu panjang.

Saya kesulitan membuat sarang execbekerja (untuk melakukannya exec'exec"..."*w\n;...'*2. Jika seseorang dapat mengetahuinya, beri tahu saya.

n,w,h=input()
s=[""]*h
for x in 1,2:
    exec"for i in range(h):l=len(s[i]+`n`)<=w;s[i]+=`n`*l;n-=l\n"*w;s=[r.replace(" ","")for r in map(lambda x:`x`[2::5],zip(*[r.ljust(w)for r in s]))];w,h=h,w
print s

Cobalah online - Menggunakan fungsi yang dimodifikasi sehingga dapat menjalankan beberapa test case dengan lebih mudah (dan tidak bisa digunakanexec). Batalkan komentar versi lain dan modifikasi stdin untuk melihatnya berjalan.

Kurang bermain golf:

def f(n,w,h):
    s=[""]*h
    for x in 1,2:
        for j in[0]*w:
            for i in range(h):
                l=len(s[i]+`n`)<=w
                s[i]+=`n`*l
                n-=l
        s=[r.ljust(w)for r in s]
        s=map(lambda x:`x`[2::5],zip(*s))
        s=[r.replace(' ','')for r in s]
        w,h=h,w
    print"\n".join(s)
mbomb007
sumber
Sangat mungkin bahwa ini harus bekerja untuk semua kasus sekarang, tetapi bukti (informal) masih akan dihargai. ;)
Martin Ender
@ MartinEnder Buktinya mungkin di luar jangkauan saya. Agar angka-angkanya lebih bervariasi panjangnya, kotak uji menjadi sangat besar. Ini mungkin terkait atau sama dengan bukti apakah selalu ada solusi.
mbomb007
6

JavaScript, 284 259 245 241 240 223 209 205 byte

// Golfed
let f = (N,W,H)=>eval('a=Array(H).fill("");while(N)g:{s=""+N--;d=s[L="length"];for(i in a)if(a[i][L]+d<=W){a[i]+=s;break g}for(p=0;d;++p){l=a[p][L];for(k=p+d;k>p;)l=a[--k][L]-l?W:l;while(l<W&&d)a[p+--d]+=s[d]}}a');

// Ungolfed
(N,W,H) => {
    a = Array(H).fill(""); // Create `H` empty rows.

    while (N) g : {
        s = "" + N--; // Convert the number to a string.
        d = s[L="length"]; // Count the digits in the number.

        // Loop through the rows trying to fit the number in horizontally.
        for (i in a) {
            if (a[i][L] + d <= W) { // If it fits.
                a[i] += s; // Append the number to the row.
                break g; // This is what a goto statement looks like in JavaScript.
            }
        }

        // Loop through the rows trying to fit the number in vertically.
        for (p = 0; d; ++p) {
            l = a[p][L]; // Get the length of the row.

            // Find `d` adjacent rows of the same length.
            for (k = p + d; k > p; ) {
                // If `a[--k][L] == l`, continue.
                // Else set `l` to `W` so the next loop doesn't run.
                l = a[--k][L] - l ? W : l;
            }

            // Put the characters in position.
            while (l < W && d)
                a[p+--d] += s[d];
        }
    }

    return a;
}

let test_data = [[1,1,1],
                 [6,6,1],
                 [6,2,3],
                 [10,1,11],
                 [10,11,1],
                 [11,13,1],
                 [27,9,5],
                 [183,21,21],
                 [184,2,222],
                 [200,41,12],
                 [1003,83,35]];

for (let test of test_data)
    console.log(f(test[0],test[1],test[2]));

Yay295
sumber
1
Simpan 1 byte dengan menggunakan -alih-alih !=untuk menguji apakah dua angka berbeda.
Neil
2

Pyth, 79 50 48 Bytes

Tidak berkompetisi sampai saya menyelesaikan bug (misalnya, [6,6,1] mengembalikan sama dengan [6,1,6]). Ini pertama kalinya saya mencoba menggunakan Pyth, jadi saya mungkin kehilangan banyak fitur.

Terima kasih kepada Jakube, menyimpan 29 byte dan membuat kode saya benar-benar berfungsi!

Menyimpan dua byte lagi dengan menyadari bahwa repr()panggilan itu tidak perlu.

Ini pada dasarnya hanya terjemahan dari jawaban Python 2 mbomb007.

AEJmkHFb2VHVGIgGl+@JNQ XNJ~tQ)))=.[.TJkGA,HG)jJ

Mengambil input dalam bentuk
n
w,h.

Steven H.
sumber
2
Jawaban harus dihapus sampai merupakan solusi yang valid.
mbomb007
Saya pikir sebagian besar kode sudah benar. Satu-satunya kesalahan yang saya lihat terjadi selama transposisi. mbomb007 transpos dengan hati-hati mengisi kolom yang tersisa dengan spasi, lalu ritsleting dan menghapus spasi. Ini menjamin. bahwa setelah transposing matriks memiliki wpanjang. =.TZtidak bisa menjamin itu, karena tidak tahu panjangnya w.
Jakube
Sebenarnya kesalahan utamanya adalah, itu !>+@ZN`zKseharusnya !>+@ZN`zJ. Kemudian semua test case kecil bekerja. Tapi Anda bisa membuat test case, di mana transposing gagal (seperti dijelaskan di atas). Agar ini berfungsi, Anda perlu sesuatu seperti =.[.TZkK(isi kolom yang hilang dengan string kosong), bukan =.TZ.
Jakube
Dan cobalah untuk tidak membingungkan dirimu dengan Pyth. Dalam kode Anda, Anda memiliki dua variabel ganda yang menunjuk ke nilai yang sama (seperti Kdan @Q1). Cukup sulit untuk melacak variabel mana yang nilainya, ... Dan jangan hanya menyalin kode. Tetap sederhana. Trik boolean =Y...mungkin ide yang baik untuk Python, tetapi sederhana I(jika) akan jauh lebih mudah dibaca (dan juga lebih pendek).
Jakube
Berikut adalah solusi yang sangat sederhana menggunakan kode mbomb007: Link Dibutuhkan ndi baris pertama (dengan cara ini kita tidak harus menetapkan nilai ke variabel tambahan, kita cukup menggunakan Q). Dan wdan hpada baris kedua, yang langsung ditugaskan ke Gdan Hdengan AE.
Jakube
1

Stax , 27 byte

é!L↑?∞S░♠╔)¥¼/ÿµ◄÷│♦╫Δò6√√╣

Jalankan dan debug itu

Dibutuhkan input pada satu baris di untuk {N} {H} {W}.

Program ini dimulai dengan kotak spasi dengan ukuran yang ditentukan. Untuk setiap angka dari N.. 1, ia mencoba melakukan penggantian string tunggal dari string spasi dengan ukuran yang sesuai ke nomor yang diformat. Jika tidak ada penggantian yang dapat dilakukan, maka ia mencoba lagi dengan kisi yang ditransposisikan.

z)A+*   create "grid" of spaces and newlines of specified size
,Rr     create range [n ... 1]
F       for each number execute the indented section; it will fit the value into the grid
  $%z(  make a string out of spaces the same length as the number; e.g. 245 => "   "
  Y     store the space string in register Y; this will be used as a search substring
  [#    count the number of occurrences of y in the grid; the grid is still on the stack
  X     store the count in register X; this will be used as a condition
  G     jump to routine at closing curly brace
  y_$|e replace the first instance of y (the spaces) with the current number
  xG    push x; then jump to routine at closing curly brace
        end program
}       called routine jump target
C       pop top of stack; if it's truthy terminate routine
|jM|J   split on newlines; transpose; join with newlines

Jalankan yang ini

rekursif
sumber