Ganze Zahlen, montieren!

30

Ihre Aufgabe ist es, die Ganzzahlen von 1bis N(als Eingabe angegeben) zu einem Rechteck aus Breite Wund Höhe H(auch als Eingabe angegeben) zusammenzusetzen. Einzelne Zahlen können um ein Vielfaches von 90 Grad gedreht werden, sie müssen jedoch als zusammenhängende Blöcke im Rechteck erscheinen. Das heißt, Sie können eine der Zahlen nicht in mehrere Ziffern aufteilen und die Ziffern einzeln im Rechteck platzieren. Sie können auch nicht drei Ziffern einer Zahl um eine Ecke biegen. Sie könnten jede Zahl als Baustein betrachten, aus dem Sie eine Mauer bauen.

Hier ist ein Beispiel. Sagen Sie, Ihre Eingabe ist (N, W, H) = (12, 5, 3). Eine mögliche Lösung ist:

18627
21901
53114

Der Übersichtlichkeit halber sind hier zwei Kopien dieses Rasters aufgeführt, eine mit ausgeblendeten einstelligen Zahlen und eine mit ausgeblendeten zweistelligen Zahlen:

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

Es ist in Ordnung, wenn das Rechteck nicht auf einzigartige Weise wieder zerlegt werden kann. Im obigen Beispiel 12könnte das beispielsweise auch so platziert werden:

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

Regeln

Sie können davon ausgehen, dass dies Npositiv ist und W*Hmit der Anzahl der Ziffern in den ganzen Zahlen von 1bis Neinschließlich übereinstimmt , und dass eine Aufteilung des Rechtecks ​​in die angegebenen Zahlen vorhanden ist. Ich habe derzeit keinen Beweis, ob dies immer möglich ist, aber ich wäre an einem interessiert, wenn Sie dies tun.

Die Ausgabe kann entweder eine einzelne durch Zeilenvorschub getrennte Zeichenfolge oder eine Liste von Zeichenfolgen (eine für jede Zeile) oder eine Liste von Listen mit einstelligen Ganzzahlen (eine für jede Zelle) sein.

Die Ergebnisse Ihrer Einreichung müssen eindeutig sein und Sie sollten in der Lage sein, alle Testfälle in weniger als einer Minute auf einem vernünftigen Desktop-Computer zu bearbeiten.

Sie können ein Programm oder eine Funktion schreiben und eine unserer Standardmethoden zum Empfangen und Bereitstellen von Eingaben verwenden.

Sie können jede Programmiersprache verwenden , aber beachten Sie, dass diese Lücken standardmäßig verboten sind.

Das ist , also gewinnt die kürzeste gültige Antwort - gemessen in Bytes .

Testfälle

Bis auf die erste ist keine davon einzigartig. Jedem Testfall N W Hfolgt eine mögliche Ausgabe. Stellen Sie sicher, dass Ihre Antwort funktioniert, wenn das Rechteck zu schmal ist, um die größeren Zahlen horizontal zu schreiben.

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
quelle
8
Gibt es einen Beweis dafür, dass dies immer möglich ist?
Fatalize
@ Fatalize Gute Frage eigentlich. Sie können davon ausgehen, dass dies für alle gegebenen Eingaben möglich ist, aber ein Beweis in beide Richtungen wäre interessant.
Martin Ender
@Fatalize: Zumindest im einfachen Fall von Eingaben (10, 1, 1)ist dies nicht möglich (vorausgesetzt, dass alle Zahlen von 1 bis NMÜSSEN in der Konstruktion verwendet werden). Wenn diese Einschränkung eingehalten wird, muss der Bereich des Rechtecks ​​in Einheiten mindestens die Anzahl der Stellen 1..Nbetragen, um dies zu ermöglichen. Wenn diese Einschränkung gelockert ist, ist es in allen Fällen möglich (aber dann macht die Herausforderung nicht viel Spaß: P)
Sebastian Lenartowicz
2
@SebastianLenartowicz: Ich glaube, Sie haben den Teil verpasst, in dem steht, dass der Bereich des Rechtecks ​​mit der Summe der Ziffern der Zahlen in [1, N] übereinstimmt. Wenn N == 10, dann müssen Breite und Höhe 1 und 11 sein. Wenn die Breite oder Höhe 1 ist, ist dieses Problem immer lösbar.
2.
1
@MartinEnder Die gegenteilige Herausforderung könnte ebenfalls interessant sein: eine Reihe von Ziffern als Eingabe (und schließlich N, aber das Programm könnte sie aus der Breite und Höhe berechnen), und das Programm muss prüfen, ob das Rechteck eine gültige Antwort auf diese Herausforderung ist. ...
Dada

Antworten:

3

Pyth, 35 Bytes

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

Dank an mbomb007. Ich habe seinen Algorithmus benutzt. Eigentlich wollte ich nur Steven H. helfen, aber dann wollte ich unbedingt eine Kurzversion sehen.

Nimmt Nin der ersten Zeile und W,Hin der zweiten Zeile: Probieren Sie es online: Demonstration

Habe einen fiesen Fehler in der Pyth-Implementierung von gefunden .[(meine eigene Schuld, da ich sie implementiert habe). Muss ich morgen reparieren. Dies führte zu +3 Bytes.

Erläuterung:

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

Python 2, 210 200 Bytes

Edit: Funktioniert jetzt!

Füllt von oben nach unten, von links nach rechts, beginnend mit den größten Zahlen. Dann transponieren und wiederholen. Dann transponieren und drucken. Ich musste Leerzeichen einfügen, damit die Transposition funktioniert, da die Linien noch nicht die volle Länge haben.

Ich hatte Probleme damit, ein verschachteltes execArbeitsobjekt zu finden exec'exec"..."*w\n;...'*2. Wenn jemand es herausfinden kann, lass es mich wissen.

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

Online testen - Verwendet eine geänderte Funktion, sodass mehrere Testfälle einfacher ausgeführt werden können (und nicht verwendet werden könnenexec). Kommentieren Sie die andere Version aus und ändern Sie stdin, damit sie ausgeführt wird.

Weniger golfen:

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
quelle
Es ist sehr wahrscheinlich, dass dies jetzt für alle Fälle funktioniert, aber ein (informeller) Beweis wäre immer noch wünschenswert. ;)
Martin Ender
@MartinEnder Ein Beweis ist mir wahrscheinlich ein Rätsel. Damit die Zahlen länger variieren, werden die Testfälle sehr groß. Es hängt wahrscheinlich mit dem Beweis zusammen, ob es immer eine Lösung gibt.
mbomb007
6

JavaScript, 284 259 245 241 240 223 209 205 Bytes

// 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
quelle
1
Speichern Sie 1 Byte, indem Sie -anstelle von !=testen, ob zwei Zahlen unterschiedlich sind.
Neil
2

Pyth, 79 50 48 Bytes

Nicht konkurrieren, bis ich Fehler herausgefunden habe (zum Beispiel [6,6,1] ergibt dasselbe wie [6,1,6]). Ich habe zum ersten Mal versucht, Pyth zu verwenden, daher fehlen mir wahrscheinlich viele Funktionen.

Dank Jakube konnten 29 Bytes gespart werden und mein Code funktionierte tatsächlich!

Es wurden weitere zwei Byte eingespart, indem erkannt wurde, dass die repr()Aufrufe unnötig waren.

Es ist im Grunde nur eine Übersetzung der Python 2-Antwort von mbomb007.

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

Nimmt Eingaben in Form von
n
w,h.

Steven H.
quelle
2
Antworten sollten gelöscht werden, bis sie eine gültige Lösung sind.
mbomb007
Ich denke, der größte Teil des Codes ist korrekt. Der einzige Fehler, den ich sehe, tritt während der Umsetzung auf. Bei der Transponierung von mbomb007 werden die verbleibenden Spalten vorsichtig mit Leerzeichen gefüllt. Anschließend werden die Leerzeichen gezippt und entfernt. Dies garantiert. dass das nach dem transponieren der matrix wlänge hat. =.TZkann das nicht garantieren, da es die Länge nicht kennt w.
Jakube
Eigentlich ist der Hauptfehler, das !>+@ZN`zKsoll sein !>+@ZN`zJ. Dann klappen alle kleinen Testfälle. Sie können jedoch Testfälle erstellen, bei denen die Umsetzung fehlschlägt (wie oben beschrieben). Damit dies funktioniert, benötigen Sie =.[.TZkKstattdessen etwas wie (füllen Sie die fehlenden Spalten mit leeren Zeichenfolgen) =.TZ.
Jakube
Und versuche dich nicht mit Pyth zu verwechseln. In Ihrem Code haben Sie zwei Mehrfachvariablen, die auf dieselben Werte verweisen (wie Kund @Q1). Es war ziemlich schwer zu verfolgen, welche Variable welcher Wert ist ... Und kopieren Sie nicht nur den Code. Halte es einfach. Der Boolesche Trick =Y...mag für Python eine gute Idee sein, aber ein einfaches I(wenn) wäre viel lesbarer (und auch kürzer).
Jakube
Hier ist eine wirklich einfache Lösung, die den Code von mbomb007 verwendet: Link Es nimmt ndie erste Zeile ein (auf diese Weise müssen wir den Wert keiner zusätzlichen Variablen zuweisen, wir können ihn einfach verwenden Q). Und wund hin der zweiten Zeile, die sofort Gund Hmit zugewiesen werden AE.
Jakube
1

Stax , 27 Bytes

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

Führen Sie es aus und debuggen Sie es

Es werden Eingaben in einer Zeile im for vorgenommen {N} {H} {W}.

Dieses Programm beginnt mit einem Raster von Leerzeichen der angegebenen Größe. Für jede Zahl von N... 1wird versucht, eine einzelne Zeichenfolge aus einer Zeichenfolge von Leerzeichen der entsprechenden Größe in die formatierte Zahl zu ersetzen. Kann kein Austausch durchgeführt werden, wird ein erneuter Versuch mit einem transponierten Gitter unternommen.

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

Führen Sie dieses aus

rekursiv
quelle