Liczby całkowite, montuj!

30

Twoim zadaniem jest złożenie liczb całkowitych od 1do N(podanych jako dane wejściowe) w prostokącie o szerokości Wi wysokości H(podanych również jako dane wejściowe). Poszczególne liczby mogą być obracane o dowolną wielokrotność 90 stopni, ale muszą pojawiać się jako ciągłe bloki w prostokącie. Oznacza to, że nie można podzielić jednej liczby na wiele cyfr i osobno umieścić cyfr w prostokącie, nie można też zgiąć trzech cyfr liczby za rogiem. Możesz rozważyć każdą liczbę jako cegłę, z której budujesz ścianę.

Oto przykład. Powiedz, że twój wkład to (N, W, H) = (12, 5, 3). Jednym z możliwych rozwiązań jest:

18627
21901
53114

Dla jasności, oto dwie kopie tej siatki, jedna z ukrytymi jednocyfrowymi liczbami i jedna z ukrytymi dwucyfrowymi liczbami:

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

W porządku, jeśli prostokąta nie można ponownie zdemontować w unikalny sposób. Na przykład w powyższym przykładzie 12można również umieścić tak:

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

Zasady

Możesz założyć, że Njest dodatnia i W*Hodpowiada liczbie cyfr w liczbach całkowitych od 1do Nwłącznie oraz, że istnieje wstawienie prostokąta do podanych liczb. Obecnie nie mam dowodu, czy jest to zawsze możliwe, ale byłbym zainteresowany jednym z nich, jeśli tak.

Dane wyjściowe mogą być albo ciągiem oddzielonym pojedynczym wierszem, albo listą ciągów (po jednym dla każdej linii) lub listą liczb całkowitych o wartości jednocyfrowej (po jednym dla każdej komórki).

Wyniki przesłania muszą być ustalone i powinieneś być w stanie obsłużyć wszystkie przypadki testowe w mniej niż minutę na rozsądnej maszynie stacjonarnej.

Możesz napisać program lub funkcję i użyć dowolnej z naszych standardowych metod otrzymywania danych wejściowych i dostarczania danych wyjściowych.

Możesz używać dowolnego języka programowania , ale pamiętaj, że te luki są domyślnie zabronione.

To jest , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .

Przypadki testowe

Z wyjątkiem pierwszego, żaden z nich nie jest wyjątkowy. Po każdym przypadku testowym N W Hnastępuje możliwe wyjście. Upewnij się, że twoja odpowiedź działa, gdy prostokąt jest zbyt wąski, aby pisać większe liczby w poziomie.

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
źródło
8
Czy istnieje dowód, że jest to zawsze możliwe?
Fatalize
@ Właściwie dobre pytanie. Możesz założyć, że jest to możliwe dla wszystkich danych wejściowych, ale dowód w obu przypadkach byłby interesujący.
Martin Ender
@ Fatalizacja: Przynajmniej w trywialnym przypadku wprowadzania danych (10, 1, 1)nie jest to możliwe (przy założeniu, że wszystkie liczby od 1 do NMUSZĄ być użyte w konstrukcji). Jeśli to ograniczenie zostanie utrzymane, obszar prostokąta w jednostkach musi być co najmniej liczbą cyfr 1..N, aby było to możliwe. Jeśli to ograniczenie jest złagodzone, jest to możliwe we wszystkich przypadkach (ale wtedy wyzwanie nie jest zbyt zabawne: P)
Sebastian Lenartowicz
2
@SebastianLenartowicz: Myślę, że przegapiłeś tę część, w której mówi, że obszar prostokąta odpowiada sumie cyfr liczb w [1, N]. Jeśli N == 10, wówczas szerokość i wysokość muszą wynosić 1 i 11. Jeśli szerokość lub wysokość wynosi 1, problem ten zawsze można rozwiązać.
Yay295,
1
@MartinEnder Przeciwne wyzwanie może być również interesujące: prostokąt cyfr jako dane wejściowe (i ostatecznie N, ale program może obliczyć to na podstawie szerokości i wysokości), a program musi sprawdzić, czy prostokąt jest wartościową odpowiedzią na to wyzwanie. ...
Dada

Odpowiedzi:

3

Pyth, 35 bajtów

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

Kredyty dla mbomb007. Użyłem jego algorytmu. Początkowo chciałem tylko pomóc Stevenowi H., ale potem naprawdę chciałem zobaczyć krótką wersję.

Przechodzi Ndo pierwszej linii, a W,Hdo drugiej linii: Wypróbuj online: Demonstracja

Znalazłem paskudny błąd w implementacji Pytha .[(moja wina, odkąd go zaimplementowałem). Muszę to naprawić jutro. Dało to +3 bajty.

Wyjaśnienie:

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
źródło
7

Python 2, 210 200 bajtów

Edycja: działa teraz!

Wypełnia od góry do dołu, od lewej do prawej, zaczynając od największych liczb. Następnie dokonaj transpozycji i zrób to ponownie. Następnie transponuj i wydrukuj. Musiałem obstawić spacje, aby transpozycja zadziałała, ponieważ linie nie są jeszcze na całej długości.

Miałem problem z uruchomieniem gniazda exec(do zrobienia exec'exec"..."*w\n;...'*2. Jeśli ktoś może to rozgryźć, daj mi znać.

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

Wypróbuj online - używa zmodyfikowanej funkcji, dzięki czemu można łatwiej uruchamiać wiele przypadków testowych (i nie można jej używaćexec). Odkomentuj drugą wersję i zmodyfikuj stdin, aby zobaczyć, jak działa.

Mniej golfa:

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
źródło
Jest bardzo prawdopodobne, że powinno to działać teraz we wszystkich przypadkach, ale (nieformalny) dowód byłby nadal mile widziany. ;)
Martin Ender
@MartinEnder Dowód jest prawdopodobnie poza mną. Aby liczby miały większą długość, przypadki testowe stają się bardzo duże. Jest to prawdopodobnie związane z tym samym dowodem, czy zawsze istnieje rozwiązanie.
mbomb007,
6

JavaScript, 284 259 245 241 240 223 209 205 bajtów

// 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
źródło
1
Zaoszczędź 1 bajt, używając -zamiast !=sprawdzać, czy dwie liczby są różne.
Neil,
2

Pyth, 79 50 48 bajtów

Nie konkuruje, dopóki nie rozwiążę błędów (na przykład [6,6,1] zwraca to samo co [6,1,6]). Po raz pierwszy próbuję używać Pytha, więc prawdopodobnie brakuje mi wielu funkcji.

Dzięki Jakube zaoszczędziłem 29 bajtów i sprawiłem, że mój kod faktycznie działał!

Zaoszczędzono kolejne dwa bajty, zdając sobie sprawę, że repr()połączenia były niepotrzebne.

To po prostu tłumaczenie odpowiedzi Python 2 na mbomb007.

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

Pobiera dane wejściowe w postaci
n
w,h.

Steven H.
źródło
2
Odpowiedzi należy usuwać, dopóki nie będą poprawnym rozwiązaniem.
mbomb007
Myślę, że większość kodu jest poprawna. Jedyny błąd, jaki widzę, występuje podczas transpozycji. mbomb007 transponuje, ostrożnie wypełniając pozostałe kolumny spacjami, a następnie zamyka i usuwa spacje. To gwarancje. że po transponowaniu macierz ma wdługość. =.TZnie mogę tego zagwarantować, ponieważ nie zna długości w.
Jakube,
Właściwie to głównym błędem !>+@ZN`zKpowinno być !>+@ZN`zJ. Następnie działają wszystkie małe przypadki testowe. Możesz jednak utworzyć przypadki testowe, w których transpozycja się nie powiedzie (jak opisano powyżej). Aby to zadziałało, potrzebujesz czegoś takiego =.[.TZkK(wypełnij brakujące kolumny pustymi ciągami) zamiast =.TZ.
Jakube,
I staraj się nie mylić z Pyth. W twoim kodzie masz dwie wielokrotne zmienne, które wskazują te same wartości (jak Ki @Q1). Trudno było śledzić, która zmienna jest jaką wartością ... I nie kopiuj tylko kodu. Nie komplikuj. Logiczna sztuczka =Y...może być dobrym pomysłem dla Pythona, ale prosty I(jeśli) byłby o wiele bardziej czytelny (a także krótszy).
Jakube,
Oto naprawdę proste rozwiązanie wykorzystujące kod mbomb007: Link Przybiera npierwszą linię (w ten sposób nie musimy przypisywać wartości do dodatkowej zmiennej, możemy po prostu użyć Q). A wi hna drugiej linii, która się natychmiast przypisany do Gi Hz AE.
Jakube,
1

Stax , 27 bajtów

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

Uruchom i debuguj

Zajmuje wejście w jednym wierszu dla {N} {H} {W}.

Ten program rozpoczyna się od siatki odstępów o określonym rozmiarze. Dla każdej liczby od N... 1próbuje zastąpić pojedynczy ciąg z ciągu spacji o odpowiednim rozmiarze do sformatowanej liczby. Jeśli nie można wykonać zamiany, oznacza to, że próbuje ponownie z transponowaną siatką.

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

Uruchom ten

rekurencyjny
źródło