Ile czasu zajmie Mikołajowi dostarczenie prezentów?

12

Jakiś czas temu opublikowałem to wyzwanie , które dotyczy liczby elfów, których Święty Mikołaj musi dostarczyć.

Ze względu na wzrost populacji, Święty Mikołaj jest trochę bardziej presja na czas w tym roku. Chociaż w przeszłości działaliśmy bardzo asynchronicznie, zaczynamy eksperymentować z coraz większą synchronizacją. Tak więc Święty Mikołaj musi wiedzieć, ile czasu zajmie mu dostarczenie prezentów do każdego regionu z określoną liczbą elfów.

Ciężar węgla nie zmienił się w ciągu ostatnich dwóch lat - wciąż jest większy niż prezenty, więc Święty Mikołaj potrzebuje trzech elfów na niegrzeczną osobę w domu i dwóch elfów na miłą osobę w domu.

Elfy spędzają cały rok na Bożym Narodzeniu, więc nie potrzebują odpoczynku między dostawami. Mogą dostarczać prezenty tylko do jednego domu na raz i muszą wrócić do sań Świętego Mikołaja i odebrać następny prezent przed przejściem do następnego domu. Z powodów, których nie wolno mi dzielić, elfy nie spędzają czasu podróżując między saniami Świętego Mikołaja a domami (ale mogą podróżować tylko wtedy, gdy sanie Świętego Mikołaja znajdują się na dachu), a jego sanie nie spędzają czasu na przemieszczaniu się z domu do domu. (Sanie Mikołaja ma potrzeby, aby przejść od domu do domu w celu zebrania paliwa, ale ja już mówiąc zbyt dużo).

Elfy, które dostarczają prezenty, muszą poświęcić cztery sekundy * na dostarczenie prezentów, a Elfy, które dostarczają węgiel, muszą poświęcić pięć sekund * na dostarczenie prezentów (zgodnie z przepisami administracji lotniczej Santa Aviation rękawice z pyłem węglowym muszą zostać spalone natychmiast po wejście na sanie, co zajmuje trochę czasu). Dodatkowo domy należy odwiedzać w kolejności, w jakiej znajdują się na mapie, od lewej do prawej, a elfy nie mogą zacząć dostarczać prezentów do innych domów, dopóki wszystkie prezenty nie zostaną dostarczone do domu, w którym się znajdują.

Gdybyśmy zakładali, że Święty Mikołaj ma wystarczająco dużo elfów dla tego regionu, zajęłoby to tylko tyle, ile potrzeba, by dostarczyć prezent komuś z niegrzecznej listy, 5 sekund na dom lub 4 sekundy na dom, jeśli wszyscy są mili.

Jednak w przeciwieństwie do poprzednich sezonów ten nadchodzący Święty Mikołaj może nie mieć wystarczającej ilości elfów dla każdego regionu, więc 4 sekundy to absolutnie minimalna ilość czasu * , którą zajmie dostarczenie prezentów do dowolnego domu, chyba że jest 0 mili ludzie i 0 niegrzecznych ludzi, w takim przypadku zajmie to 0 sekund.

Dodatkowo, jeśli choć jeden z domów ma kogoś na liście niegrzecznych, Święty Mikołaj potrzebuje co najmniej trzech elfów. Jeśli przynajmniej jeden z domów ma kogoś na ładnej liście, a żaden z nich nie ma ludzi na liście niegrzecznych, Święty Mikołaj będzie potrzebował co najmniej dwóch elfów. Jeśli żaden z domów nie jest w świątecznym nastroju, dowolna liczba elfów (w tym 0) zajmie 0 sekund.

Na mapie Świętego Mikołaja dom jest reprezentowany przez *, a każdy dom jest podzielony przez +. Święty Mikołaj nadal używa tych samych map, co w innym wyzwaniu , ale dołączę tutaj dokumentację.

Po obu stronach domu będzie liczba - ta po lewej reprezentująca liczbę niegrzecznych ludzi w domu, a ta po prawej reprezentująca liczbę miłych ludzi w domu. Jeśli po jednej stronie nie ma numeru, jest interpretowane jako 0.

Wiem, że może to zabrzmieć szalenie, ale niektórzy ludzie „nie lubią Bożego Narodzenia”, więc czasami dom może nie mieć numeru po obu stronach.

Jedna z map Świętego Mikołaja może wyglądać mniej więcej tak.

1*3+2*+*5+*+4*7

Powiedzmy, że Święty Mikołaj ma dziewięć elfów na saniach.

  1. (0s) Pierwszy dom ma 1 niegrzecznego i 3 miłych ludzi. Trzy elfy dostarczają węgiel, zabierając pięć sekund, a sześć dostarcza prezenty, zabierając cztery sekundy. Po pięciu sekundach sanie Świętego Mikołaja przenoszą się do następnego domu

  2. (5s) Drugi dom ma 2 niegrzeczne i 0 miłych ludzi. Sześć elfów dostarcza węgiel, zabierając pięć sekund. Po pięciu sekundach sanie Świętego Mikołaja przenoszą się do następnego domu

  3. (10s) Trzeci dom ma 0 niegrzecznych i 5 miłych ludzi. Osiem elfów idzie po cztery prezenty (ten, który pozostaje, nie może dostarczyć prezentu). Po czterech sekundach wszystkie elfy wróciły, a dwie z nich idą, by dostarczyć drugi prezent (sanie muszą poczekać, aż elfy wrócą, zanim przejdą do następnego domu), zabierając kolejne cztery sekundy

  4. (18s) Czwarty dom nie jest w świątecznym nastroju, więc ma 0 niegrzecznych i 0 miłych ludzi i jest pomijany

  5. (18s) Piąty dom ma 4 niegrzeczne i 7 miłych ludzi. To się komplikuje ...

    I. Wszystkie dziewięć elfów idzie po trzy dary węgla (zostaw t + 0s, zwróć t + 5s) II. Po 5 sekundach wszyscy wracają na sanie, a trzy z nich idą, aby dostarczyć ostatni prezent węgla (zostaw t + 5s, zwróć t + 10s), a pozostałe sześć dostarczy trzy ładne prezenty (zostaw t + 5s, zwróć t + 9s).

    III. Po czterech sekundach sześć elfów powraca i idzie dostarczyć jeszcze trzy fajne prezenty (zostaw t + 9s, zwróć t + 13s).

    IV. Sekundę po ich wyjściu trzy elfy, które dostarczały obecny węgiel, wracają, a dwa z nich wychodzą, by dostarczyć ostatni miły prezent (zostaw + 10s, zwróć t + 14s)

  6. (18 + 14 = 32 sekundy ) Święty Mikołaj zakończył dostarczanie prezentów do tego regionu.

Jak widzimy, dostarczenie prezentów do tego regionu zajmuje Mikołajowi w sumie 32 sekundy . To była jednak zbyt uproszczona wersja jednej z map Świętego Mikołaja. Zwykle mapy Świętego Mikołaja mają wiele linii i mają kwadratowy kształt, aby lepiej pasowały do ​​jego listy. Normalna mapa może wyglądać \nmniej więcej tak (a na końcu każdej linii)

1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*

Przy 26 elfach (lub dowolnej większej ilości) zajęłoby to Mikołajowi 71 sekund .
Przy 20 elfach Mikołajowi zajęłoby to 76 sekund .
Z 15 elfami Święty Mikołaj zająłby 80 sekund .
Przy 3 elfach Mikołajowi zajęłoby to 288 sekund .
Przy 2 elfach (lub dowolnej mniejszej ilości) byłoby to niemożliwe.

Aha, i jeszcze jedno - kolejność, w jakiej elfy dostarczają prezenty, ma znaczenie (ze względu na różnicę czasową w dostarczaniu prezentów niegrzecznym / miłym ludziom), więc twój kod powinien zawsze generować najmniej czasu, jaki elfy mogą poświęcić na dostarczanie prezentów.

Wyzwanie

Pomóż Mikołajowi określić, ile czasu zajmie dostarczenie prezentów przez określoną liczbę elfów.

Domy

  • Dom jest reprezentowany przez *
  • Domy są podzielone według +
  • Liczba po lewej stronie domu symbolizuje liczbę niegrzecznych ludzi (brak liczby oznacza 0)
  • Liczba po prawej stronie symbolizuje liczbę miłych ludzi (brak liczby oznacza 0)
  • Na \nwejściu mogą znajdować się znaki nowej linii ( ), które również należy traktować jako podział

Elfy

  • Święty Mikołaj potrzebuje pomocy trzech elfów dla niegrzecznych ludzi (węgiel jest znacznie cięższy niż prezenty), a dostarczenie prezentów zajmie tym elfom pięć sekund *
  • Święty Mikołaj potrzebuje pomocy od dwóch elfów dla miłych ludzi, a dostarczenie prezentów zajmie im cztery sekundy *
  • Jeśli po obu stronach domu nie ma numeru, Święty Mikołaj nie odwiedzi tego domu, a zatem nie zajmie to czasu (ludzie spoza Bożego Narodzenia nie zasługują nawet na węgiel)

Święty

  • Święty Mikołaj musi dostarczać prezenty do domów jeden po drugim
  • Święty Mikołaj nie może przejść do następnego domu, dopóki wszystkie elfy nie wrócą na sanie, a wszystkie prezenty zostaną dostarczone do tego domu (nie chcemy zostawić elfów, prawda?)
  • Sanie Świętego Mikołaja nie spędzają czasu na podróżowaniu od domu do domu (ponownie, z powodów, których nie mam wolności dzielić)

Co robić

Biorąc pod uwagę mapę domów i kilku elfów, wydrukuj, ile czasu Święty Mikołaj dostarczy prezenty do domów na mapie.

* (Nie mogę dzielić ilości czasu potrzebnej elfom na dostarczenie prezentów. Nie mogę potwierdzić ani zaprzeczyć, że czasy zawarte w tym wyzwaniu są prawidłowe)

Zasady

  • Istnieją dwa dane wejściowe - mapa i liczba elfów. Dane wejściowe mogą być pobierane jako argumenty funkcji lub STDIN lub równoważne. Jeśli przyjęcie dwóch danych wejściowych jest niemożliwe w Twoim języku, wtedy i tylko wtedy możesz zaakceptować dwa dane wejściowe jako pojedynczy ciąg wejściowy, ograniczony przez jakiś znak, który zwykle nie jest wprowadzany (nie jeden +*\nlub 0-9- ciąg wejściowy nie może być niejednoznaczny) np ,.
  • Liczba elfów zawsze będzie nieujemną liczbą całkowitą (0 jest poprawne)
  • Dane wyjściowe mogą być albo wartością zwracaną przez funkcję, albo drukowane do STDOUT lub równoważne. Jeśli Mikołaj nie może dostarczyć prezentów do danego regionu z określoną liczbą elfów, musisz wyprowadzić spójną liczbę ujemną lub spójną wiadomość bez żadnych liczb
  • Wszystko wydrukowane do STDERR zostanie zignorowane, więc nie możesz wydrukować wyniku lub komunikatu o błędzie do STDERR
  • Twój program nie może ulec awarii z powodu nieprawidłowej liczby elfów dla regionu
  • Rezultatem powinien być jedynie całkowity czas, jaki zajmie Mikołajowi na dostarczenie prezentów o podanej liczbie elfów.
  • Wydajność powinna zawsze obejmować najmniej czasu potrzebnego elfom na dostarczenie prezentów
  • Wejście będzie zawierać tylko liczby, +, *oraz nowe linie \n(chyba że podasz inną postać, która będzie zawierać dane wejściowe jeśli język nie może trwać dwa wejścia (spojrzeć na pierwszej reguły) )
  • Standardowe luki zastosowanie

Przypadki testowe

"1*1", 5 elves => 5
"1*1", 3 elves => 9
"1*2", 7 elves => 5
"1*2", 5 elves => 10
"1*2", 3 elves => 13
"2*1", 8 elves => 5
"2*1", 5 elves => 9
"2*1", 3 elves => 14
"1*" , 3 elves => 5
"1*" , 2 elves => (error message)
"*1" , 2 elves => 4
"*1" , 0 elves => (error message)
"*"  , 0 elves => 0

"1*1+1*1",   5 elves => 10
"1*1+1*1",   3 elves => 18
"1*1+*+1*1", 3 elves => 18
"1*2+2*1",   8 elves => 10
"1*2+2*1",   7 elves => 14
"1*2+2*1",   6 elves => 18
"1*2+2*1",   3 elves => 27
"1*2+2*1",   2 elves => (error message)
"*+*+*+*",   2 elves => 0
"*+*+*+*",   0 elves => 0

"1*3+2*+*5+*+4*7", 9 elves => 32

(mam nadzieję, że wszystko dobrze zrozumiałem)

Punktacja

Święty Mikołaj spędza każdy dzień zawsze patrząc na wiele rzeczy - wszystkie prezenty, które dostarczy, wszystkie elfy, które ma, wszystkie domy, które dostarcza prezenty ... Dla Świętego Mikołaja najlepszym prezentem świątecznym będzie w stanie zobaczyć trochę czegoś. Z tego powodu wygrywa najkrótsze przesłanie w bajtach .

Tabela liderów

To jest fragment kodu, który generuje zarówno tabelę wyników, jak i przegląd zwycięzców według języka.

Aby mieć pewność, że Twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown

## Language Name, N bytes

Gdzie N jest rozmiarem twojego przesłania w bajtach

Jeśli chcesz dołączyć wiele liczb do nagłówka (na przykład przekreślając stare wyniki lub włączając flagi w liczbie bajtów), po prostu upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku

## Language Name, <s>K</s> X + 2 = N bytes

Pokaż fragment kodu

code-golf string Jojodmo
źródło
Myślę, że 288 powinien przeczytać 281 : (1+0+0+1+2+3+1+0+0+0+4+1+0+0+1+2+3+2+0+0)*5+(2+0+4+0+4+0+6+0+0+0+2+1+4+3+0+3+10+0+5+0)*4=21*5+44*4=105+176=281(chociaż muszę powiedzieć, że nie przeczytałem całego „eseju”!)
Jonathan Allan,
@JonathanAllan Yea ... Przypadkowo spędziłem zbyt dużo czasu na pisaniu wyzwania ... ups ... W każdym razie kluczową rzeczą, której brakuje, jest to, że sanie Świętego Mikołaja muszą poczekać, aż wszystkie elfy wrócą na pokład, zanim przeprowadzą się do następny dom, więc chociaż dodanie wszystkich liczb i pomnożenie ich może w niektórych przypadkach zadziałać, w większości nie. Na przykład, mając 9 elfów, dom 4*7zajmuje 14 sekund (jest to omówione w połowie eseju, tuż przed wprowadzeniem mapy 2D), ale (4 * 5) + (7 * 4) = 48
Jojodmo,
Wartość 288 jest na przykład z 3 elfami, więc zawsze musieliby wykonać pełne uderzenie naughty*5+nice*4w każdym domu, prawda? (zauważ, że 4*7w tym przykładzie nie ma )
Jonathan Allan
Czy elfy zawsze najpierw usuwają węgiel (tak jak w twoim przykładzie), czy też planują efektywnie? Na przykład, jeśli mapa była 5*15i byłyby 9elfy, czy zajęłoby to (minimum) 20 sekund lub 22 sekund? Zobacz te reprezentacje tekstowe, aby zobaczyć ilustrację tego przykładu.
Jonathan Allan
EDYTUJ powyżej 5*15powinien przeczytać 4*15.
Jonathan Allan

Odpowiedzi:

4

Rubinowy , 433 400 bajtów

Cóż, ten jest naprawdę trudny, ponieważ okazuje się, że planowanie elfów jest trudne NP.

Ponadto, proszę bądź miły, to moje pierwsze zgłoszenie, więc mogłem przegapić pewne oczywiste optymalizacje:

->e,h{h.split(/\+|\n/).map{|h|n,g=h.split(?*).map(&:to_i)+[0,0];return-1if(g>0&&e<2)||(n>0&&e<3);([[3,5]]*n+[[2,4]]*g).permutation.map{|j|c=[0]*e;j.map{|q|w,y=q;k=l=0;r=c.map{|x|a=b=0;c[k..e].map{|r|r<=x ?a+=1:break};(t=k+=1).times{c[t-=1]<=x ?b+=1:break};[a,b]};d=r.inject([]){|v,x|v<<l if x[0]>=w;l+=1;v}.min{|a,b|c[a]<=>c[b]};b=d-r[d][1]+1;z=c[d]+y;(b..(b+w-1)).map{|x|c[x]=z}};c.max}.min||0}.sum}

Wypróbuj online!

Początkowo miałem dłuższe przypadki testowe, ale ponieważ powtarzam wszystkie możliwe kombinacje dla planowania, w niektórych przypadkach zajmuje to dużo czasu, więc je usunąłem.

elyalvarado
źródło
2
Witamy w PPCG! Zdecydowanie wybrałeś trudne wyzwanie dla swojej pierwszej odpowiedzi
Jo King
2

Java (OpenJDK 8) , 344 bajty

Planowanie elfów jest trudniejsze niż myślałem, więc zajęło to trochę czasu i jest dość długie.

Mimo to zdecydowanie było to moje ulubione wyzwanie związane z kodowaniem golfa! 

(e,d)->{int r=0,x,y,c,p,b,g,m;for(String h:d[0].split("\\+")){d=h.split("\\*",-1);b=new Byte("0"+d[0]);g=new Byte("0"+d[1]);m=-1>>>1;for(y=1;y<=e/3&(x=(e-y*3)/2)>0;c=b/y+(b%y++<1?0:1),p=g/x+(g%x<1?0:1),x=c*5>p*4?c*5:p*4,m=x<m?x:m);for(y=0;b+g>0;b-=c,g-=p){c=e/3<b?e/3:b;x=(e-c*3)/2;p=x<g?x:g;if(c+p<1)return-1;y+=c>0?5:4;}r+=m<y?m:y;}return r;}

Wypróbuj online (ze wszystkimi testami)!

Wyjaśnienie;

Przygotuj się: jest długi

    int r=0,x,y,c,p,b,g,m;               // Define all the variables I need

    for(String h:d[0].split("\\+")){     // Split houses on '+' and loop through them

        d=h.split("\\*",-1);             // Split the current house on '*' using the limit
                                         // to preserve empty strings.

        b=new Byte("0"+d[0]);            // Parse the naughty (b) and nice (g) people
        g=new Byte("0"+d[1]);

        m=-1>>>1;                        // Initialise minimum time as max integer using
                                         // overflow

        for(y=1;y<=e/3&(x=(e-y*3)/2)>0;  // For each number of elves that can concurrently
                                         // deliver coal, and still leave enough elves to
                                         // deliver presents

            c=b/y+(b%y++<1?0:1),         // Determine the number of runs needed to deliver
                                         // all coal using this number of elves

            p=g/x+(g%x<1?0:1),           // Determine the number of runs needed to deliver
                                         // all presents using this number of elves

            x=c*5>p*4?c*5:p*4,           // Get the maximum time required for the
                                         // delivery of coal or presents

            m=x<m?x:m);                  // If this is less than the current minimum time,
                                         // set it as the minimum time


        for(y=0;b+g>0;b-=c,g-=p){        // While there are still people to deliver to;

            c=e/3<b?e/3:b;               // Determine the max amount of coal to deliver

            x=(e-c*3)/2;                 // Determine how many presents can be
                                         // delivered with the remaining elves.

            p=x<g?x:g;                   // If this number is more than nice people
                                         // remaining, just use the nice people remaining

            if(c+p<1)return-1;           // If no presents can be delivered, return the
                                         // error code (-1)

            y+=c>0?5:4;                  // Increase the time by 5 if coal was
                                         // delivered, and 4 if only presents

        }                                // At the end of each loop (see above)
                                         // remove the presents and coal delivered
                                         // from the number of naughty and nice houses

        r+=m<y?m:y;                      // Increment the total time by which ever
                                         // is smaller of the calculated times
    }
    return r;                            // Return the total time

Uwaga: Ta odpowiedź zależy od poprawności moich przypadków testowych

Luke Stevens
źródło
Myślę, że (e-y*3)/2-> e-y*3>>1zapisuje bajt. (Najprawdopodobniej dotyczy to również (e-c*3)/2.)
Jonathan Frech
runTest("1*4",5,12);kończy się niepowodzeniem (rozumiesz "1*4", 5 elves => 13 FAILED. Byłem zaskoczony, jak twój algorytm był tak dobry do planowania w tak niewielu bajtach, więc sprawdziłem go we wszystkich możliwych kombinacjach od 0 do 7 (elfy, niegrzeczne i miłe) i znalazłem tylko kilka, w których nie udało się daj optymalny czas. To jest najmniejsza kombinacja, jeśli się nie powiedzie. BTW, niesamowita logika do zaplanowania, przez długi czas nie miałem pojęcia, jak to zrobiłaś
elyalvarado 26.04.2018