Introdução

Alguns de vocês já devem ter ouvido falar do Hilbert's Grand Hotel . O gerente perdeu sua lista de onde os hóspedes estão hospedados, mas ainda tem a ordem em que fizeram o check-in. Cada hóspede não pode ficar em um quarto com um número de quarto menor que o valor e se um convidado for adicionado a um valor menor. quarto, todos os hóspedes em quartos superiores, sem espaço vazio entre eles e o novo hóspede, mudam para um quarto. Você pode ajudá-lo a encontrar onde cada um dos convidados está hospedado?

Exigências

Escreva um programa que receba uma lista ordenada de números naturais como entrada e os coloque em seu índice. Se já houver um valor nesse índice, ele será deslocado para a próxima entrada na lista. Esse processo se repete até que o primeiro espaço vazio (0 ou indefinido) seja encontrado. Quaisquer espaços indefinidos entre o índice mais alto atual e qualquer nova entrada serão preenchidos adicionando 0s. Como este é o Grand Hotel de Hilbert, não existem quartos maiores que o atual índice ocupado mais alto.

Entrada e saída

A entrada será uma lista ordenada de números naturais (permitida a leitura através de qualquer forma de entrada aceita).
Cada número na entrada é considerado um hóspede que chega ao hotel e está em ordem de chegada.

A saída será o arranjo final dos convidados (números)

Exemplos

Entrada: 1 3 1
Saída: 1 1 3
Passo a passo:
1
Crie uma sala no índice 1 e coloque 1 nela
1 0 3
Crie salas até o índice 3 e coloque 3 na sala 3
1 1 3
Desloque o conteúdo da sala 1 para cima um quarto e coloque 1 no quarto 1

Entrada: 1 4 3 1 2 1
Saída : 1 1 2 1 3 4
Passo a passo:
1
Crie uma sala no índice 1 e coloque 1 nela
1 0 0 4
Crie salas até o índice 4 e coloque 4 na sala 4
1 0 3 4
Coloque 3 na sala 3
1 1 3 4
Desloque o conteúdo da sala 1 para cima um quarto e coloque 1 na sala 1
1 2 1 3 4
Desloque o conteúdo das salas 2 para 4 para cima um quarto e coloque 2 na sala 2
1 1 2 1 3 4
Desloque o conteúdo dos quartos 1 para 5 em um quarto e coloque 1 no quarto 1

Entrada: 10
Saída: 0 0 0 0 0 0 0 0 0 0 10
Passo a passo:
0 0 0 0 0 0 0 0 0 10 10
Crie salas até a sala 10 e coloque 10 na sala 10

Notas:
Trabalhar com 0 indexado é bom e, nesse caso, você pode inserir um 0 na frente da saída

As brechas padrão são proibidas, o código mais curto em bytes ganha

Gelatina , 28 bytes

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

Experimente 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 indexado. Usa um loop 2 em 1 que procura o próximo convidado depois de obter um 0 (ou um formulário nulo que vai além da sala final atual). Use como:

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

Experimente online!

JavaScript (ES6), 144 120 bytes

Economizou 20B graças a Arnauld e 11B graças a Neil

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)

Uso

Você pode atribuir a função à variável f e a lista deve ser fornecida como uma matriz. Exemplo:

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

Saída

A saída também está em uma matriz. Como o Javascript funciona com indexação zero, há um 0 extra na frente.

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

JavaScript (ES6), 86 bytes

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)

Zero à esquerda no resultado porque o JavaScript é indexado em 0.

Mathematica, 98 bytes

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

Função sem nome, obtendo uma lista de números inteiros positivos e retornando uma lista de números inteiros indexada em 0. A Iffunção inteira pega uma lista parcialmente concluída e o próximo número inteiro a ser inserido como argumentos. Se o próximo número inteiro exceder o comprimento da lista parcial, PadRight@##~Append~#2aumentará a lista parcial de acordo; caso contrário, Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]insere o próximo número inteiro em sua posição e joga fora o primeiro 0encontrado depois dele. Fold[...,{0},#]aplica essa função repetidamente à lista original, começando com o hotel vazio {0}e produz a lista final de hotéis.

JavaScript (ES6), 81

Usando 0 indexação

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)

Menos golfe

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
}

Teste

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

Para evitar problemas com a indexação incorreta, preencho alguns zeros e depois os removo no final. Talvez essa não seja a melhor solução, mas funciona.

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

Válido para o Python 2.7.13 e 3.6.0. Esse código funciona por meio da troca do valor retido pelo valor contido em cada índice até que o valor retido seja 0. Se atingir um índice ainda não presente na matriz, ele adiciona zeros ao final da matriz até que a matriz contenha esse valor. índice. Agradecimentos ao Wheat Wizard e ao xnor por jogar 9 bytes cada