Einführung

Einige von Ihnen haben vielleicht von Hilberts Grand Hotel gehört . Der Manager dort hat seine Liste mit den Aufenthaltsorten der Gäste verloren, hat jedoch immer noch die Reihenfolge, in der sie eingecheckt haben. Jeder Gast kann nicht in einem Zimmer mit einer niedrigeren Zimmernummer als ihrem Wert übernachten und wenn ein Gast zu einer niedrigeren hinzugefügt wird zimmer, alle gäste in höheren zimmern ohne leeren raum zwischen ihnen und dem neuen gast werden um ein zimmer nach oben verschoben. Können Sie ihm helfen, herauszufinden, wo sich die Gäste aufhalten?

Bedarf

Schreiben Sie ein Programm, das eine geordnete Liste natürlicher Zahlen als Eingabe erhält und diese an ihrem Index ablegt. Wenn der Index bereits einen Wert enthält, wird er zum nächsten Eintrag in der Liste verschoben. Dieser Vorgang wird wiederholt, bis der erste leere (0 oder undefinierte) Bereich gefunden wurde. Undefinierte Leerzeichen zwischen dem aktuell höchsten Index und neuen Eingaben werden durch Hinzufügen von Nullen aufgefüllt. Da dies Hilberts Grand Hotel ist, gibt es keine Zimmer, die höher sind als der derzeit am höchsten belegte Index.

Ein- und Ausgang

Bei der Eingabe handelt es sich um eine geordnete Liste natürlicher Zahlen (die durch jede akzeptierte Form der Eingabe gelesen werden dürfen).
Jede Zahl in der Eingabe gilt als ein Gast, der im Hotel ankommt, und ist in der Reihenfolge seiner Ankunft

Ausgabe wird die endgültige Anordnung der Gäste (Zahlen) sein

Beispiele

Eingabe: 1 3 1
Ausgabe: 1 1 3
Schritt für Schritt:
1
Raum auf Index 1 anlegen und 1 darin platzieren
1 0 3
Räume auf Index 3 anlegen und 3 in Raum 3 platzieren
1 1 3
Verschieben Sie den Inhalt von Raum 1 nach oben ein Raum und Platz 1 in Raum 1

Eingabe: 1 4 3 1 2 1
Ausgabe : 1 1 2 1 3 4
Schritt für Schritt:
1
Raum an Index 1 anlegen und 1 darin platzieren
1 0 0 4
Räume bis Index 4 anlegen und 4 in Raum 4
1 0 3 platzieren 4
Platzieren Sie 3 in Raum 3
1 1 3 4
Verschieben Sie den Inhalt von Raum 1 um einen Raum und platzieren Sie 1 in Raum 1
1 2 1 3 4
Verschieben Sie den Inhalt von Räumen 2 bis 4 um einen Raum und platzieren Sie 2 in Raum 2
1 1 2 1 3 4
Verschieben Sie den Inhalt der Räume 1 bis 5 um einen Raum und platzieren Sie 1 in Raum 1

Eingabe: 10
Ausgabe: 0 0 0 0 0 0 0 0 0 0 10
Schritt für Schritt:
0 0 0 0 0 0 0 0 0 10
Erstellen Sie Räume bis zu Raum 10 und platzieren Sie 10 in Raum 10

Hinweise: Das
Arbeiten mit einer indizierten 0 ist in Ordnung. In diesem Fall können Sie eine 0 vor der Ausgabe einfügen

Standardlücken sind verboten, kürzester Code in Bytes gewinnt

Gelee , 28 Bytes

ṫœṡ0F
’⁹ḣ;⁸;ç@ð0ẋ;@
0;ç@/œr0

Probieren Sie es online!

PHP 93 Bytes

for(;$r=$g?$r+1:$g=$argv[++$i];[$g,$h[$r]]=[$h[$r],$g])$h=array_pad($h?:[],$g,0);print_r($h);

0 indiziert. Verwendet eine 2-in-1-Schleife, die den nächsten Gast sucht, nachdem er eine 0 (oder ein Null-Formular, das über den aktuellen endgültigen Raum hinausgeht) erhalten hat. Verwenden Sie wie:

php -r "for(;$r=$g?$r+1:$g=$argv[++$i];[$g,$h[$r]]=[$h[$r],$g])$h=array_pad($h?:[],$g,0);print_r($h);" 1 4 3 1 2 1

Ungolfed:

for( $hotel = []; $room = $guest = $argv[ ++$i ]; )
{
    for( $hotel = array_pad( $hotel, $guest, 0 ); $guest; $room++ )
    {
        $last = $hotel[ $room ];
        $hotel[ $room ] = $guest;
        $guest = $last;
    }
}
print_r( $hotel );

Haskell , 107 Bytes

h=foldl(\h n->let{(b,a)=splitAt n h;(c,d)=span(>0)a;e=0:e;f=take n$b++e;g(0:m)=m;g m=m}in f++[n]++c++g d)[]

Probieren Sie es online!

JavaScript (ES6), 144 120 Byte

20B dank Arnauld und 11B dank Neil gerettet

a=>a.map((d,c)=>b[d]?(b.splice(d,0,d),b.splice([...b,0].find‌​Index((e,g)=>g&&!e),‌​1)):b[d]=d,b=[])&&[...b].map(c=>c|0)

Verwendung

Sie können die Funktion der Variablen zuweisen fund die Liste sollte als Array angegeben werden. Beispiel:

f=a=>a.map((d,c)=>b[d]?(b.splice(d,0,d),b.splice([...b,0].find‌​Index((e,g)=>g&&!e),‌​1)):b[d]=d,b=[])&&[...b].map(c=>c|0)
f([1,4,3,1,2,1])

Ausgabe

Die Ausgabe erfolgt ebenfalls in einem Array. Da Javascript mit einem Nullindex arbeitet, gibt es eine zusätzliche 0 im Voraus.

[0, 1, 1, 2, 1, 3, 4]

JavaScript (ES6), 86 Byte

f=([n,...a],r=[],p=n,m=r[p],_=r[p]=n)=>n?m?f([m,...a],r,p+1):f(a,r):[...r].map(n=>n|0)

Führende Null im Ergebnis, da JavaScript 0-indiziert ist.

Mathematica, 98 Bytes

Fold[If[Length@#<#2,PadRight@##~Append~#2,Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]&,{0},#]&

Unbenannte Funktion, die eine Liste positiver Ganzzahlen aufnimmt und eine 0-indizierte Liste von Ganzzahlen zurückgibt. Die gesamte IfFunktion benötigt eine unvollständige Liste und die nächste Ganzzahl, die als Argumente eingefügt werden soll. Wenn die nächste Ganzzahl die Länge der Teilliste überschreitet, PadRight@##~Append~#2wird die Teilliste entsprechend erhöht. Andernfalls wird Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]die nächste Ganzzahl an ihrer Position eingefügt und anschließend die zuerst 0gefundene weggeworfen. Fold[...,{0},#]Wendet diese Funktion wiederholt auf die ursprüngliche Liste an, beginnend mit dem leeren Hotel {0}, und gibt die endgültige Hotelliste aus.

JavaScript (ES6), 81

Indizierung 0 verwenden

l=>l.map(v=>(s=(p,v,w=r[p])=>(w&&s(p+1,w),r[p]=v))(v,v),r=[])&&[...r].map(x=>~~x)

Weniger golfen

l => {
  s = ( // recursively insert a value, shifting present values up until it finds an empty spot
       p, // insert position
       v, // value to insert
       w = r[p] // value a current position
      ) => ( 
         w && s(p+1,w), // if there is a value, put it in the next position
         r[p] = v // now the current place is empty
      );
  r = []; // initialize the result array   
  l.map( // execute the following for each value in input
     v => s(v,v) // insert value
  );
  return [...r].map(x=>~~x) // fill the missing places with 0
}

Prüfung

F=
l=>l.map(v=>(s=(p,v,w=r[p])=>(w&&s(p+1,w),r[p]=v))(v,v),r=[])&&[...r].map(x=>~~x)

out=x=>O.textContent+=x+'\n'

out([1,3,1]+' -> '+F([1,3,1]))
out([10]+' -> '+F([10]))

function go() {
   var v = I.value.match(/\d+/g).map(x=>+x)
   out(v +' -> ' + F(v))
}
go()

<input id=I value='1 4 3 1 2 1'><button onclick='go()'>go</button>
<pre id=O></pre>

R, 133 Bytes

a=scan()
z=rep(0,max(a))
for(i in a){b=match(0,z[-1:-i])+i
if(z[i])z[i:b]=c(i,z[i:(b-1)])else(z[i]=i)
z=c(z,0)}
z[1:max(which(z!=0))]

Um Probleme mit einer schlechten Indizierung zu vermeiden, fülle ich mit Nullen auf und entferne sie am Ende. Dies ist vielleicht nicht die beste Lösung, aber es funktioniert.

Python, 134 125 116 Bytes

def a(b):
 r=[]
 i=0
 for n in b:
    d=n
    while n:
     if i<d:r.extend([0]*(d-i));i=d
     n,r[d-1]=r[d-1],n;d+=1
 return r

Gültig für Python 2.7.13 und 3.6.0. Dieser Code funktioniert durch Austauschen des gehaltenen Werts mit dem Wert, der an jedem Index enthalten ist, bis der gehaltene Wert 0 ist. Wenn er einen Index erreicht, der noch nicht im Array enthalten ist, fügt er am Ende des Arrays Nullen hinzu, bis das Array diese enthält Index. Dank an Wheat Wizard und xnor für das Golfen mit jeweils 9 Bytes