Hilbert's Grand Hotel

Question

Introduction

Some of you may have heard of Hilbert's Grand Hotel. The manager there has lost his list of where the guests are staying but he still has the order in which they checked in. Each guest can not stay in a room with a room number less than their value and if a guest is added to a lower room, all guests in higher rooms with no empty space between them and the new guest are shifted up one room. Can you help him find where each of the guests are staying?

Requirements

Write a program which receives an ordered list of natural numbers as input and places them at their index. If there is already a value in that index, it is shifted up to the next entry in the list. This process repeats until the first empty (0 or undefined) space is found. Any undefined spaces between the current highest index and any new input will be filled by adding 0s. As this is Hilbert's Grand Hotel, rooms higher than the current highest occupied index do not exist.

Input and Output

Input will be an ordered list of natural numbers (allowed to be read through any accepted form of input)
Each number in the input is considered one guest arriving at the hotel and is in order of arrival

Output will be the final arrangement of guests (numbers)

Examples

Input: 1 3 1
Output: 1 1 3
Step by step:
1
Create room at index 1 and place 1 in it
1 0 3
Create rooms up to index 3 and place 3 in room 3
1 1 3
Shift the contents of room 1 up one room and place 1 in room 1

Input: 1 4 3 1 2 1
Output: 1 1 2 1 3 4
Step by step:
1
Create room at index 1 and place 1 in it
1 0 0 4
Create rooms up to index 4 and place 4 in room 4
1 0 3 4
Place 3 in room 3
1 1 3 4
Shift contents of room 1 up one room and place 1 in room 1
1 2 1 3 4
Shift contents of rooms 2 to 4 up one room and place 2 in room 2
1 1 2 1 3 4
Shift contents of rooms 1 to 5 up one room and place 1 in room 1

Input: 10
Output: 0 0 0 0 0 0 0 0 0 0 10
Step by step:
0 0 0 0 0 0 0 0 0 10
Create rooms up to room 10 and place 10 in room 10

Notes:
Working with 0 indexed is fine and you may insert a 0 at the front of the output in that case

Standard loopholes are forbidden, shortest code in bytes wins

Answer 1

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 indexed. Uses a 2 in 1 loop that looks up the next guest after it gets a 0 (or a null form going beyond the current final room). Use like:

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

Answer 2

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

Try it online!

Answer 3

Jelly, 24 22 bytes

aŻƤSƇḢßoɓ@ooƑ?
Ṭ×)ç@ƒ0

Try it online!

I still have the strangest feeling that something closer to Dennis's answer should beat this, but I haven't had any luck with that so far. I have twisted the first line into something that sounds like some kind of exploding can (from my original recursive solution; I thought it saved a byte but I didn't look at the output too carefully so it actually ties but it does look funnier).

aŻƤSƇḢßoɓ@ooƑ?    Helper link: add a pre-positioned guest to the hotel

        ɓ         With reversed arguments (hotel left, guest right):
           oƑ?    Unless both arrays have a nonzero at the same location,
          o       return with the guest placed in its empty room;
        ɓ         if they do:
         @        (guest left, hotel right)
a                 Overlay the guest's zeroes on the hotel.
 ŻƤ               Prepend another zero to each prefix,
   SƇḢ            and take the first with a nonzero sum.
      ß           Call this link again with that as the new guest
       o          and with the hotel having the previous guest replace the new one.

Ṭ×)ç@ƒ0    Main link

  )        For each guest value,
Ṭ          obtain a list of all zeroes then a one at that index,
 ×         and multiply that by the same guest value.
     ƒ0    Starting with 0, reduce that by
   ç@      the helper with reversed arguments.

Essentially just boots occupants out of their rooms in sequence until there's no collision, considering a new guest as equivalent to someone evicted from the last room they can't start in.

Dennis's answer with some simple golfs for fair comparison, and an explanation for those still wondering:

Jelly, 26 bytes

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

Try it online!

’⁹ḣ;⁸;ṫ@œṡ0Fɗð0ẋ;@    Helper link: add a guest on the left to the hotel on the right

             ð        Let the right argument to the rest of the link be
              0ẋ      zero repeated by the value of the guest
                ;@    concatenated to the end of the hotel.
 ⁹ḣ                   Take elements from that right argument numbering
’                     one less than the guest,
   ;⁸                 concatenate the guest,
     ;      ɗ         and concatenate:
      ṫ@              remove elements from that right argument numbering the guest value,
        œṡ0           split those remaining around the first zero,
           F          and flatten them back together.

ç@ƒ0œr0    Main link

ç@ƒ0       With the hotel starting as 0, add each guest to the hotel in sequence.
    œr0    Trim trailing zeroes.

Answer 4

Jelly, 28 bytes

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

Try it online!

Answer 5

JavaScript (ES6), 144 120 bytes

Saved 20B thanks to Arnauld and 11B thanks to 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)

Usage

You can assign the function to the variable f and the list should be given as an array. Example:

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

Output

The output is in an array as well. Since Javascript works zero-indexed, there is an extra 0 up front.

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

Answer 6

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)

Leading zero in the result because JavaScript is 0-indexed.

Answer 7

Mathematica, 98 bytes

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

Unnamed function taking a list of positive integers and returning a 0-indexed list of integers. The whole If function takes a partially completed list and the next integer to insert as arguments. If the next integer exceeds the length of the partial list, PadRight@##~Append~#2 increases the partial list accordingly; otherwise, Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]] inserts the next integer into its position, then throws away the first 0 found after it. Fold[...,{0},#] applies this function repeatedly to the original list, starting with the empty hotel {0}, and outputs the final hotel list.

Answer 8

JavaScript (ES6), 81

Using 0 indexing

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)

Less golfed

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>

Answer 9

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

To avoid problems with bad indexing, I pad with some zeros, and then strip them at the end. This is maybe not the best solution, but it works.

Answer 10

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

Valid for both Python 2.7.13 and 3.6.0. This code functions by means of a swapping the held value with the value contained at each index until the held value is 0. If it reaches an index not yet in the array, it adds zeros to the end of the array until the array contains that index. Thanks to Wheat Wizard and xnor for golfing off 9 bytes each