Magnetische Skulpturen… im Weltraum!

8

Hintergrund

Dies ist eine Fortsetzung meiner früheren Herausforderung , bei der es darum ging, die Form einer Skulptur zu berechnen, die durch Fallenlassen von Magneten auf einen riesigen Stapel erhalten wurde.

Gute Nachricht: Der exzentrische Künstler mochte Ihre Arbeit und hat ein anderes Projekt für Sie. Er arbeitet immer noch mit Magnetskulpturen, hat sich aber entschlossen, sein Kunststudio zu erweitern - in den Weltraum ! Seine derzeitige Methode besteht darin, einen einzelnen würfelförmigen Magneten in die Umlaufbahn zu sprengen und andere Magnete darauf zu schießen, um einen riesigen magnetischen Satelliten zu erzeugen.

Eingang

Ihre Eingabe ist eine endliche Liste von 0s und 1s, die entweder im nativen Listenformat Ihrer Sprache oder als Zeichenfolge angegeben wird. Es wird als "Blaupause" eines Kunstwerks interpretiert und wie folgt von links nach rechts verarbeitet.

Sie beginnen mit einem einzelnen Magneten, der an einer ganzzahligen Koordinate der 2D-Ebene schwebt, und fügen gemäß den Anweisungen immer mehr Magnete hinzu. Die Richtlinie 0dreht die gesamte Skulptur um 90 Grad gegen den Uhrzeigersinn. Bei der Richtlinie 1findet der Künstler die am weitesten links stehende Säule der Skulptur und schießt von unten einen neuen Magneten darauf. Der neue Magnet haftet am untersten vorhandenen Magneten in der Säule und wird Teil der Skulptur. Beachten Sie, dass der Magnet im Gegensatz zur früheren Herausforderung nicht an anderen Magneten in der benachbarten Säule haftet. seine Geschwindigkeit ist jetzt astronomisch!

Ausgabe

Der Künstler möchte wissen, ob die gesamte Skulptur in seine Garage passt (wie er sie aus der Umlaufbahn bringt, bleibt unklar). Ihre Ausgabe ist also die Breite und Höhe der Skulptur, geordnet von niedriger nach höher. Sie können als Liste mit zwei Elementen, als Paar oder als durch Komma getrennte Zeichenfolge angegeben werden.

Beispiel

Betrachten Sie die Eingabesequenz

[1,0,1,1,0,1,0,0,1,1]

Um es zu verarbeiten, beginnen wir mit einem Magneten, der im Raum schwebt:

#

Die erste Anweisung lautet 1, also schießen wir einen neuen Magneten von unten:

#
#

Die nächste Anweisung lautet 0, also drehen wir die Skulptur:

##

Die nächsten beiden Anweisungen sind 1,1, was bedeutet, dass wir zwei Magnete in die linke Spalte schießen:

##
#
#

Dann drehen wir uns erneut und schießen einmal, wie von 0,1:

#
###
#

Schließlich drehen wir uns zweimal und schießen zweimal:

  #
###
# #
#

Die resultierende Skulptur hat Breite 3und Höhe 4, also geben wir aus [3,4].

Regeln

Sie können entweder eine Funktion oder ein vollständiges Programm angeben. Die niedrigste Byteanzahl gewinnt und Standardschlupflöcher sind nicht zulässig.

Testfälle

[1,0,1] -> [2,2]
[1,0,1,1,0,1,0,0,1,1] -> [3,4]
[1,1,0,1,1,0,1,0,1,1] -> [4,5]
[1,1,0,1,1,0,1,0,1,1,0] -> [4,5]
[1,0,1,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1] -> [3,3]
[0,1,0,1,1,1,1,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,1,1] -> [5,7]
[1,0,1,1,1,1,0,1,0,0,0,0,1,1,1,0,1,1,0,1,0,1,0,0,0,0,0,0,1,1,0,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,0,1,1,0,0,1,0,1,1,0,0,0,1,0,1,1,0,0,1,0,1,1,0] -> [11,12]
Zgarb
quelle
Sollte nicht [1,1,0,1,1,0,1,0,1,1,0]zurückkehren [5,4]und nicht [4,5]? Die Skulptur wird am Ende gedreht.
Algorithmushai
@algorithmshark Ich habe den gleichen Fehler gemacht. Der Abschnitt Ausgabe gibt an, dass das Ergebnis bestellt werden soll.
Martin Ender
1
@ MartinBüttner ist richtig. Die Rechtfertigung ist, dass Orientierung keine Rolle spielt, wenn Sie sich im Raum befinden . : P
Zgarb

Antworten:

8

Pyth : 34 33 Bytes

Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ

Eingabe ist eine Liste von Einsen und Nullen, wie in der Frage. Probieren Sie es online aus: Pyth Compiler / Executor

Erläuterung:

Es ist eine Eins-zu-Eins-Übersetzung des folgenden Python 2- Codes ( 126 Byte ).

print sorted(map(len,map(set,zip(*reduce(lambda s,i:([[-b,a]for a,b in s],s+[[min(s)[0],min(s)[1]-1]])[i],input(),[[0,0]])))))

Ich erstelle eine Liste von Koordinaten der einzelnen Magnete. Dies wird mit dem Magneten initialisiert [0,0]. Dann manipuliere ich für jede der ganzen Zahlen der Blaupause die Liste folgendermaßen. Wenn die nächste Ganzzahl ist 0, drehe ich die Skulptur, indem ich die Koordinaten für jeden Magneten [a,b]auf ändere [-b,a](im Grunde genommen mit einer Rotationsmatrix multiplizieren). Wenn die nächste Ganzzahl a ist 1, suche ich nach dem Minimalstück [a,b](das automatisch der niedrigste Magnet der Spalte ganz links ist) und hänge den Magneten [a,b-1]an die Liste an.

Nachdem alle Eingaben verarbeitet wurden, erstelle ich zwei Sätze (zum Entfernen von Duplikaten), einen für die x-Werte und einen für die y-Werte, und drucke die Größen in sortierter Reihenfolge aus.

Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ
                             ],ZZ  starting list G=[(0,0)]
      u                     Q],ZZ  for H in input(): manipulate G
       S                              Sort G after each manipulation
        ?          H                  G = ... if H==1 else ...
                    m,_ekhkG            [(-b,a) for a,b in G)] (rotate)
         +G,hhGtehG                     G+[(G[0][0],G[0][1]-1)]
                                        (G[0] is the lowest magnet in the leftmost column)
     C                             Zip the coords together
                                    (creates 2 lists, x- and y-coords)
 ml{d                              for each of those list compute number of unique values
S                                  sort and print

Eine Idee zur Verbesserung : Verwendung komplexer Zahlen als Koordinaten für die Magnete. Eine Drehung ist nur eine Multiplikation mit jund Subtraktion jvom niedrigsten Magneten in der Spalte ganz links. Leider erfordert das Auffinden dieses Magneten ganz links in Python viel zu viele Zeichen, und es wird nicht einmal davon gesprochen, das Rechteck zu finden.

Jakube
quelle
7

CJam, 48 Bytes

S]l~{{)S/);Sa+S*a+_z,f{_N*@\+<}}{zW%}?}/_,\z,]$p

Testen Sie es hier.

Erwartet die Eingabe als Array im CJam-Stil (dh Leerzeichen anstelle von Kommas) und präsentiert die Ausgabe auf ähnliche Weise. Wenn Sie die Testfälle aus der Frage direkt verwenden möchten, kopieren Sie sie direkt in das Eingabefeld (einschließlich der ->und Ergebnisse) und verwenden Sie dieses Testkabel, das die Zeilen in das richtige Eingabeformat konvertiert (und die Ergebnisse verwirft):

qN/{S/0=","Ser}%{[

S]\~{{)S/);Sa+S*a+_z,f{_N*@\+<}}{zW%}?}/_,\z,]$p

}/

Erläuterung

Ich setze die Regeln nur sehr wörtlich um. Ich behalte ein Raster mit der aktuellen Skulptur (als Array von Zeichenfolgen) und drehe dann für jede Anweisung entweder das Raster oder füge einen neuen Block hinzu. Die wichtigsten Tricks zum Speichern von Bytes sind:

  • In der unteren Reihe von rechts hinzufügen . Dies ist völlig gleichwertig. Ich bin nur eine Umdrehung voraus, und da das Gitter rotationsinvariant beginnt, spielt das keine Rolle.
  • Verwenden Sie ein Leerzeichen, um belegte Blöcke darzustellen, und ein Zeilenumbruchzeichen, um leere Blöcke darzustellen. Wenn Sie also das Raster tatsächlich ausdrucken würden, würden Sie nicht viel sehen und es würde nicht einmal rechteckig aussehen. Ich mache das, weil die meisten Array-basierten Operatoren nur dann tun, was Sie wollen, wenn das betreffende Rasterelement in ein Array eingeschlossen ist. Und mit Sund Nich habe Zugriff auf Strings den Raum und Newline - Zeichen enthält (dh das Zeichen in einem Array verpackt), statt zu verwenden, sagen sie, 1aund 0aein Array erhält eine Zahl enthält.

Lassen Sie uns den Code durchgehen:

"Overall program structure:";
S]l~{{...}{...}?}/_,\z,]$p
S]                         "Push a string with a space and wrap it in an array.
                            This is the initial grid containing a single block.";
  l~                       "Read the input and evaluate it.";
    {           }/         "For each instruction in the input...";
     {...}{...}?           "Execute the first block if it's 1, the second if it's 0.";
                  _,       "Duplicate the resulting grid and get its length. This
                            is one of the dimensions.";
                    \      "Swap with the other copy of the grid.";
                     z,    "Zip/transpose it and get its length. This is the other
                            dimension of the grid.";
                       ]$p "Wrap both in an array, sort them, and print the result.";

"The rotation block is simple. A rotation is equivalent to two reflection operations
 along different axes. The simplest ones available are to transpose the grid (which
 is a reflection about the diagonal) and reversing the rows (which is a reflection
 about the horizontal). In CJam these are z for zip/tranpose and W% for reversing
 an array. So I simply put these together in the right order to get a counter-
 clockwise rotation:";
zW%

"Now the interesting part, adding new blocks and growing the grid. This part consists
 of two steps: appending a block to the rightmost block in the bottom row (allowing
 for empty blocks after it). And then potentially padding the rest of the grid with
 new empty cells if the bottom row got longer.";
)S/);Sa+S*a+_z,f{_N*@\+<}
)                         "Split off the bottom row.";
 S/                       "Split the row on occupied blocks.";
   );                     "Split off the final substring - this discards trailing
                           empty cells.";
     Sa+                  "Add a new substring containing an occupied block to the row.";
        S*                "Join all substrings together with spaces, putting back in
                           all the occupied blocks.";
          a+              "Wrap it in an array to add the row back onto the grid.";

 "At this point we need to make sure the grid is still rectangular. The easiest way
  (I found) is to find the maximum row length, add that many empty blocks to each 
  line and then truncate the lines to that length.";

            _             "Duplicate the grid.";
             z,           "Zip/transpose it and get the length. This is the length
                           of the longest row in a ragged array.";
               f{       } "Map this block onto each row, passing in the target length.";
                 _N*      "Duplicate the target length and get a string of that many
                           empty cells.";
                    @\    "Pull up the row and then swap it with those empty cells.";
                      +   "Add the empty cells to the end of the row.";
                       <  "Truncate to the target length.";
Martin Ender
quelle
Keine Ahnung wie das funktioniert, aber es funktioniert!
Luis Mendo
@LuisMendo Eine Erklärung hinzugefügt. Wenn etwas unklar ist und Sie interessiert sind, können Sie mir gerne einen weiteren Kommentar schreiben. ;)
Martin Ender
Ich habe keine Ahnung von CJam und es scheint keine einfache Sprache zu sein. Du hattest meine +1 schon :-)
Luis Mendo
4

Matlab (92)

S=1;for d=input(''),if d,S(find(S(:,1),1,'last')+1,1)=1;else,S=rot90(S);end;end,sort(size(S))

Standardeingabe wird verwendet. Daten sollten in das Formular eingegeben werden [1,0,1,1,0,1,0,0,1,1].

Ungolfed:

S = 1; %// initial magnet
for d = input('') %// get directives, and pick them sequentially
    if d %// if directive is 1
        S(find(S(:,1),1,'last')+1,1) = 1; %// add 1 after lowest 1 in column 1. Grow if needed
    else %// if directive is 0
        S = rot90(S); %// rotate counterclockwise. Handy Matlab built-in function
    end
end
sort(size(S)) %// display size sorted

Beispiellauf:

>> clear all
>> S=1;for d=input(''),if d,S(find(S(:,1),1,'last')+1,1)=1;else,S=rot90(S);end;end,sort(size(S))
[1,0,1,1,0,1,0,0,1,1]
ans =
     3     4
Luis Mendo
quelle
1

Python - 211

import numpy as n
p=input()
q=len(p)
a=n.zeros([2*q+1]*2)
a[q,q]=1
for i in p:
 if i:x=a[:,n.where(a.any(0))[0][0]];x[len(x)-n.where(x[::-1])[0][0]+1]=1
 else:a=n.rot90(a)
z=a[:,a.any(1)]
print z[a.any(0)].shape
KSFT
quelle
Die Ausgabe sollte von niedriger nach höher sortiert werden! Auch Ihr Programm bricht für die Eingabe [1].
Jakube
0

CJam, 47 Bytes

1]]q~{{0f+(W%_1#(1tW%a\+z{1b},}{W%}?z}/),\,)]$p

Dies nimmt die von STDIN eingegebene Array-Eingabe im CJam-Stil (Leerzeichen anstelle von Komma) und druckt das Ergebnis in STDOUT.

Beispiel:

[1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1]

gibt

[3 3]

Ausgabe.

Erklärung folgt, nachdem ich überzeugt bin, dass dies nicht weiter gespielt werden kann.

Probieren Sie es hier online aus

Optimierer
quelle