Введение

Некоторые из вас, возможно, слышали о Гранд Отеле Гильберта . Менеджер там потерял свой список того, где находятся гости, но у него все еще есть порядок, в котором они зарегистрировались. Каждый гость не может оставаться в комнате с номером комнаты, который меньше их стоимости, и если гость добавлен к более низкому комната, все гости в более высоких комнатах без свободного места между ними и новым гостем перемещаются на одну комнату. Можете ли вы помочь ему найти, где каждый из гостей остановился?

Требования

Напишите программу, которая получает упорядоченный список натуральных чисел в качестве входных данных и помещает их в свой индекс. Если в этом индексе уже есть значение, оно перемещается к следующей записи в списке. Этот процесс повторяется до тех пор, пока не будет найдено первое пустое (0 или неопределенное) пространство. Любые неопределенные пробелы между текущим самым высоким индексом и любым новым вводом будут заполнены добавлением 0. Поскольку это Гранд-отель Гильберта, номеров, превышающих текущий самый высокий индекс занятости, не существует.

Вход и выход

На входе будет упорядоченный список натуральных чисел (разрешено читать через любую принятую форму ввода).
Каждый номер на входе считается одним гостем, прибывающим в отель, и находится в порядке прибытия

На выходе будет окончательное расположение гостей (номера)

Примеры

Вход: 1 3 1
Выход: 1 1 3
Шаг за шагом:
1
Создайте комнату с индексом 1 и поместите в нее
1 1 3 3
Создайте комнаты с индексом 3 и поместите 3 в комнату 3
1 1 3
Сдвиньте содержимое комнаты 1 вверх одна комната и место 1 в комнате 1

Вход: 1 4 3 1 2 1
Выход : 1 1 2 1 3 4
Шаг за шагом:
1
Создайте комнату с индексом 1 и поместите в нее
1 1 0 0 4
Создайте комнаты с индексом 4 и поместите 4 в комнату 4
1 0 3 4
Поместите 3 в комнату 3
1 1 3 4
Поменяйте содержимое комнаты 1 на одну комнату и поместите 1 в комнату 1
1 2 1 3 4
Поменяйте содержимое комнаты 2 на 4 на одну комнату и поместите 2 в комнату 2
1 1 2 1 3 4
Поменяйте содержимое комнат с 1 по 5 на одну комнату и поместите 1 в комнату 1

Вход: 10
Выход: 0 0 0 0 0 0 0 0 0 0 10
Шаг за шагом:
0 0 0 0 0 0 0 0 0 10
Создайте комнаты до комнаты 10 и поместите 10 в комнату 10

Примечания:
Работа с индексированными 0 - это нормально, и в этом случае вы можете вставить 0 в начало вывода

Стандартные лазейки запрещены, выигрывает самый короткий код в байтах

Желе , 28 байт

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

Попробуйте онлайн!

PHP 93 байта

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

0 проиндексировано. Использует цикл 2 в 1, который ищет следующего гостя после того, как он получает 0 (или нулевую форму, выходящую за пределы текущей последней комнаты). Используйте как:

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 байт

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

Попробуйте онлайн!

JavaScript (ES6), 144 120 байт

Экономия 20B благодаря Арно и 11B благодаря Нейлу

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и список должен быть представлен в виде массива. Пример:

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

Выход

Вывод также в массиве. Поскольку Javascript работает с нулевым индексом, есть дополнительный 0 в начале.

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

JavaScript (ES6), 86 байт

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)

Лидирующий ноль в результате, потому что JavaScript индексируется 0.

Mathematica, 98 байт

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

Безымянная функция, принимающая список натуральных чисел и возвращающая 0-индексированный список целых чисел. Вся Ifфункция принимает частично заполненный список и следующее целое число для вставки в качестве аргументов. Если следующее целое число превышает длину частичного списка, соответственно PadRight@##~Append~#2увеличивает частичный список; в противном случае Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]вставляет следующее целое число в свою позицию, а затем выбрасывает первое 0найденное после него. Fold[...,{0},#]повторно применяет эту функцию к исходному списку, начиная с пустой гостиницы {0}, и выводит окончательный список гостиниц.

JavaScript (ES6), 81

Использование индексации 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)

Меньше гольфа

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
}

Тест

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 байта

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

Чтобы избежать проблем с плохой индексацией, я дополняю нулями, а затем в конце убираю их. Возможно, это не лучшее решение, но оно работает.

Python, 134 125 116 байт

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

Действительно как для Python 2.7.13, так и для 3.6.0. Этот код функционирует посредством замены удерживаемого значения на значение, содержащееся в каждом индексе, пока удерживаемое значение не станет равным 0. Если он достигает индекса, еще не находящегося в массиве, он добавляет нули в конец массива, пока массив не содержит показатель. Спасибо Wheat Wizard и xnor за игру в гольф по 9 байт каждый