23
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

Jelly, 28 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Explain please? \$\endgroup\$ – ckjbgames Jan 27 '17 at 19:28
5
\$\begingroup\$

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 );
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Hahaha, that almost looks like it could be perl! \$\endgroup\$ – Zachary Craig Jan 25 '17 at 18:03
3
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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]
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I didn't really test that, but could (c+'').split`,`.map(Number) do the job? \$\endgroup\$ – Arnauld Jan 25 '17 at 15:26
  • \$\begingroup\$ Clever trick, and yes, it does work. Thanks. \$\endgroup\$ – Luke Jan 25 '17 at 15:29
  • \$\begingroup\$ Oops, I forgot to test testcase 2, and it turns out my function doesn't support adding things to the front of the array... \$\endgroup\$ – Luke Jan 25 '17 at 15:41
  • \$\begingroup\$ I believe you could do c.map(n=>n|0) rather than (c+'').split`,`.map(Number). \$\endgroup\$ – ETHproductions Jan 25 '17 at 17:47
  • \$\begingroup\$ @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.) \$\endgroup\$ – Arnauld Jan 25 '17 at 18:32
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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>

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Ad Hoc Garf Hunter Jan 25 '17 at 14:52
  • \$\begingroup\$ I was working with a stupid editor which converted tab to 4 spaces XP \$\endgroup\$ – fəˈnɛtɪk Jan 25 '17 at 14:54
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Jan 25 '17 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.