Wprowadzenie
Niektórzy z was mogli słyszeć o Grand Hotelu Hilberta . Kierownik tam zgubił listę miejsc, w których przebywają goście, ale nadal ma kolejność, w której się zameldowali. Każdy gość nie może przebywać w pokoju o numerze pokoju mniejszym niż ich wartość i jeśli gość zostanie dodany do niższej pokoju, wszyscy goście w wyższych pokojach bez pustej przestrzeni między nimi a nowym gościem są przenoszeni o jeden pokój do góry. Czy możesz pomóc mu znaleźć miejsce pobytu każdego z gości?
Wymagania
Napisz program, który odbiera uporządkowaną listę liczb naturalnych jako dane wejściowe i umieszcza je pod ich indeksem. Jeśli w tym indeksie znajduje się już wartość, jest ona przenoszona do następnego wpisu na liście. Ten proces powtarza się, dopóki nie zostanie znalezione pierwsze puste (0 lub niezdefiniowane) miejsce. Wszelkie niezdefiniowane spacje między bieżącym najwyższym indeksem a wszelkimi nowymi danymi wejściowymi zostaną wypełnione przez dodanie zer. Ponieważ jest to Grand Hotel Hilberta, pokoje wyższe niż obecnie najwyższy wskaźnik zajętości nie istnieją.
Wejście i wyjście
Dane wejściowe będą uporządkowaną listą liczb naturalnych (dopuszczonych do odczytu przez dowolną zaakceptowaną formę wprowadzania)
Każda liczba w danych wejściowych jest uważana za jednego gościa przybywającego do hotelu i jest w kolejności przybycia
Wyjście będzie ostateczną aranżacją gości (liczby)
Przykłady
Wejście: 1 3 1
Wyjście: 1 1 3
Krok po kroku:
1
Utwórz pokój o indeksie 1 i umieść w nim
1 1 3 3
Utwórz pokoje do indeksu 3 i umieść 3 w pokoju 3
1 1 3
Przesuń zawartość pokoju 1 w górę jeden pokój i umieść 1 w pokoju 1Wejście: 1 4 3 1 2 1
Wyjście : 1 1 2 1 3 4
Krok po kroku:
1
Utwórz pokój o indeksie 1 i umieść w nim
1 1 0 0 4
Utwórz pokoje o indeksie 4 i umieść 4 w pokoju 4
1 0 3 4
Umieść 3 w pokoju 3
1 1 3 4
Zmień zawartość pokoju 1 w górę o jeden pokój i umieść 1 w pokoju 1
1 2 1 3 4
Zmień zawartość pokoi od 2 do 4 w górę o jeden pokój i umieść 2 w pokoju 2
1 1 2 1 3 4
Przesuń zawartość pokoi od 1 do 5 w górę o jeden pokój i umieść 1 w pokoju 1Wejście: 10
Wyjście: 0 0 0 0 0 0 0 0 0 0 10
Krok po kroku:
0 0 0 0 0 0 0 0 0 10
Utwórz pokoje do pokoju 10 i umieść 10 w pokoju 10Uwagi:
Praca z indeksem 0 jest w porządku i możesz w takim przypadku wstawić 0 z przodu wyjścia
Standardowe luki są zabronione, najkrótszy kod w bajtach wygrywa
źródło
PHP 93 bajty
0 zindeksowanych. Wykorzystuje pętlę 2 w 1, która wyszukuje następnego gościa po otrzymaniu 0 (lub postaci zerowej wychodzącej poza bieżący pokój końcowy). Użyj jak:
Nie golfowany:
źródło
Haskell , 107 bajtów
Wypróbuj online!
źródło
JavaScript (ES6),
144120 bajtówOszczędności 20B dzięki Arnauldowi i 11B dzięki Neilowi
Stosowanie
Możesz przypisać funkcję do zmiennej,
f
a lista powinna być podana w postaci tablicy. Przykład:Wydajność
Dane wyjściowe są również w tablicy. Ponieważ JavaScript działa z indeksowaniem zerowym, na początku jest dodatkowe 0.
źródło
(c+'').split`,`.map(Number)
czy mógłbym wykonać robotę?c.map(n=>n|0)
zamiast(c+'').split`,`.map(Number)
.map()
ogóle nie iteruje niezdefiniowanych wartości w tablicy. (To powiedziawszy, jestem prawie pewien, że istnieje krótsza droga niż ta, którą zasugerowałem.)JavaScript (ES6), 86 bajtów
Wiodące zero w wyniku, ponieważ JavaScript jest indeksowany na 0.
źródło
Mathematica, 98 bajtów
Nienazwana funkcja pobierająca listę liczb całkowitych dodatnich i zwracająca indeksowaną liczbę 0 liczb całkowitych. Cała
If
funkcja przyjmuje częściowo wypełnioną listę i następną liczbę całkowitą do wstawienia jako argumenty. Jeśli następna liczba całkowita przekracza długość listy częściowej, odpowiednioPadRight@##~Append~#2
zwiększa listę częściową; w przeciwnym razieJoin[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]
wstawia następną liczbę całkowitą na swoje miejsce, a następnie wyrzuca pierwszą0
znalezioną za nią.Fold[...,{0},#]
stosuje tę funkcję wielokrotnie do pierwotnej listy, zaczynając od pustego hotelu{0}
, i wyświetla ostateczną listę hoteli.źródło
JavaScript (ES6), 81
Korzystanie z indeksowania 0
Mniej golfa
Test
źródło
R, 133 bajty
Aby uniknąć problemów ze złym indeksowaniem, piszę z zerami, a następnie usuwam je na końcu. To może nie jest najlepsze rozwiązanie, ale działa.
źródło
Python,
134125116 bajtówDotyczy zarówno Pythona 2.7.13, jak i 3.6.0. Ten kod działa poprzez zamianę wartości wstrzymanej na wartość zawartą w każdym indeksie, aż wartość wstrzymana wyniesie 0. Jeśli osiągnie indeks jeszcze nie w tablicy, dodaje zera na końcu tablicy, dopóki tablica nie będzie zawierała tego indeks. Dzięki Wheat Wizard i xnor za grę w golfa po 9 bajtów
źródło
while
iif
nie potrzebują parens. Możesz umieścić wiele instrukcji w jednym wierszu oddzielonych znakami;
podobne,if(i<d):r.extend([0]*(d-i));i=d
chyba że w późniejszych instrukcjach występuje przepływ kontrolny.