Wprowadzenie

Niektórzy z was mogli słyszeć o Grand Hotelu Hilberta . Kierownik tam zgubił listę miejsc, w których przebywają goście, ale nadal ma kolejność, w której się zameldowali. Każdy gość nie może przebywać w pokoju o numerze pokoju mniejszym niż ich wartość i jeśli gość zostanie dodany do niższej pokoju, wszyscy goście w wyższych pokojach bez pustej przestrzeni między nimi a nowym gościem są przenoszeni o jeden pokój do góry. Czy możesz pomóc mu znaleźć miejsce pobytu każdego z gości?

Wymagania

Napisz program, który odbiera uporządkowaną listę liczb naturalnych jako dane wejściowe i umieszcza je pod ich indeksem. Jeśli w tym indeksie znajduje się już wartość, jest ona przenoszona do następnego wpisu na liście. Ten proces powtarza się, dopóki nie zostanie znalezione pierwsze puste (0 lub niezdefiniowane) miejsce. Wszelkie niezdefiniowane spacje między bieżącym najwyższym indeksem a wszelkimi nowymi danymi wejściowymi zostaną wypełnione przez dodanie zer. Ponieważ jest to Grand Hotel Hilberta, pokoje wyższe niż obecnie najwyższy wskaźnik zajętości nie istnieją.

Wejście i wyjście

Dane wejściowe będą uporządkowaną listą liczb naturalnych (dopuszczonych do odczytu przez dowolną zaakceptowaną formę wprowadzania)
Każda liczba w danych wejściowych jest uważana za jednego gościa przybywającego do hotelu i jest w kolejności przybycia

Wyjście będzie ostateczną aranżacją gości (liczby)

Przykłady

Wejście: 1 3 1
Wyjście: 1 1 3
Krok po kroku:
1
Utwórz pokój o indeksie 1 i umieść w nim
1 1 3 3
Utwórz pokoje do indeksu 3 i umieść 3 w pokoju 3
1 1 3
Przesuń zawartość pokoju 1 w górę jeden pokój i umieść 1 w pokoju 1

Wejście: 1 4 3 1 2 1
Wyjście : 1 1 2 1 3 4
Krok po kroku:
1
Utwórz pokój o indeksie 1 i umieść w nim
1 1 0 0 4
Utwórz pokoje o indeksie 4 i umieść 4 w pokoju 4
1 0 3 4
Umieść 3 w pokoju 3
1 1 3 4
Zmień zawartość pokoju 1 w górę o jeden pokój i umieść 1 w pokoju 1
1 2 1 3 4
Zmień zawartość pokoi od 2 do 4 w górę o jeden pokój i umieść 2 w pokoju 2
1 1 2 1 3 4
Przesuń zawartość pokoi od 1 do 5 w górę o jeden pokój i umieść 1 w pokoju 1

Wejście: 10
Wyjście: 0 0 0 0 0 0 0 0 0 0 10
Krok po kroku:
0 0 0 0 0 0 0 0 0 10
Utwórz pokoje do pokoju 10 i umieść 10 w pokoju 10

Uwagi:
Praca z indeksem 0 jest w porządku i możesz w takim przypadku wstawić 0 z przodu wyjścia

Standardowe luki są zabronione, najkrótszy kod w bajtach wygrywa

Galaretka , 28 bajtów

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

Wypróbuj online!

PHP 93 bajty

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

0 zindeksowanych. Wykorzystuje pętlę 2 w 1, która wyszukuje następnego gościa po otrzymaniu 0 (lub postaci zerowej wychodzącej poza bieżący pokój końcowy). Użyj jak:

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

Nie golfowany:

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 bajtów

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)[]

Wypróbuj online!

JavaScript (ES6), 144 120 bajtów

Oszczędności 20B dzięki Arnauldowi i 11B dzięki Neilowi

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)

Stosowanie

Możesz przypisać funkcję do zmiennej, fa lista powinna być podana w postaci tablicy. Przykład:

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])

Wydajność

Dane wyjściowe są również w tablicy. Ponieważ JavaScript działa z indeksowaniem zerowym, na początku jest dodatkowe 0.

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

JavaScript (ES6), 86 bajtów

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)

Wiodące zero w wyniku, ponieważ JavaScript jest indeksowany na 0.

Mathematica, 98 bajtów

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

Nienazwana funkcja pobierająca listę liczb całkowitych dodatnich i zwracająca indeksowaną liczbę 0 liczb całkowitych. Cała Iffunkcja przyjmuje częściowo wypełnioną listę i następną liczbę całkowitą do wstawienia jako argumenty. Jeśli następna liczba całkowita przekracza długość listy częściowej, odpowiednio PadRight@##~Append~#2zwiększa listę częściową; w przeciwnym razie Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]wstawia następną liczbę całkowitą na swoje miejsce, a następnie wyrzuca pierwszą 0znalezioną za nią. Fold[...,{0},#]stosuje tę funkcję wielokrotnie do pierwotnej listy, zaczynając od pustego hotelu {0}, i wyświetla ostateczną listę hoteli.

JavaScript (ES6), 81

Korzystanie z indeksowania 0

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)

Mniej golfa

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
}

Test

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 bajty

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))]

Aby uniknąć problemów ze złym indeksowaniem, piszę z zerami, a następnie usuwam je na końcu. To może nie jest najlepsze rozwiązanie, ale działa.

Python, 134 125 116 bajtów

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

Dotyczy zarówno Pythona 2.7.13, jak i 3.6.0. Ten kod działa poprzez zamianę wartości wstrzymanej na wartość zawartą w każdym indeksie, aż wartość wstrzymana wyniesie 0. Jeśli osiągnie indeks jeszcze nie w tablicy, dodaje zera na końcu tablicy, dopóki tablica nie będzie zawierała tego indeks. Dzięki Wheat Wizard i xnor za grę w golfa po 9 bajtów