Hilbert's Grand Hotel

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

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 );  • Hahaha, that almost looks like it could be perl! Commented Jan 25, 2017 at 18:03 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!

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.

)        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       With the hotel starting as 0, add each guest to the hotel in sequence.
œr0    Trim trailing zeroes.

• You outgolfed Dennis? You absolute madlad. Have an upvote. Commented Aug 16, 2021 at 7:09

Jelly, 28 bytes

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


Try it online!

• Explain please? Commented Jan 27, 2017 at 19:28

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]

• I didn't really test that, but could (c+'').split,.map(Number) do the job? Commented Jan 25, 2017 at 15:26
• Clever trick, and yes, it does work. Thanks.
– Luke
Commented Jan 25, 2017 at 15:29
• Oops, I forgot to test testcase 2, and it turns out my function doesn't support adding things to the front of the array...
– Luke
Commented Jan 25, 2017 at 15:41
• I believe you could do c.map(n=>n|0) rather than (c+'').split,.map(Number). Commented Jan 25, 2017 at 17:47
• @ETHproductions The problem is that map() doesn't iterate at all on undefined values in the array. (That said, I'm pretty sure there's a shorter way than the one I suggested.) Commented Jan 25, 2017 at 18:32

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.

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.

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>

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.

Python, 134125 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

• Instead of using spaces for all your indents you could use a space for level one indents, a tab for level two and a tab followed by a space for level three. Commented Jan 25, 2017 at 14:52
• I was working with a stupid editor which converted tab to 4 spaces XP Commented Jan 25, 2017 at 14:54
• The conditions for while and if don't need parens. You can put multiple statements on one line separated by ; like if(i<d):r.extend([0]*(d-i));i=d unless there's control flow in the later statements.
– xnor
Commented Jan 25, 2017 at 20:40