Wie lange dauert es, bis der Weihnachtsmann seine Geschenke ausliefert?

12

Ich habe diese Herausforderung vor einiger Zeit veröffentlicht, die sich darauf bezieht, wie viele Elfen der Weihnachtsmann braucht, um Geschenke zu bringen.

Aufgrund des Bevölkerungswachstums ist der Weihnachtsmann in diesem Jahr zeitlich etwas dringlicher. Obwohl wir in der Vergangenheit sehr asynchron gearbeitet haben, beginnen wir zu experimentieren, immer mehr synchron zu sein. Daher muss der Weihnachtsmann wissen, wie lange er braucht, um Geschenke mit einer bestimmten Anzahl von Elfen in jeder Region auszuliefern.

Das Gewicht der Kohle hat sich in den letzten zwei Jahren nicht verändert - es ist immer noch schwerer als Geschenke, daher braucht der Weihnachtsmann drei Elfen pro ungezogener Person im Haus und zwei Elfen pro nette Person im Haus.

Elfen trainieren das ganze Jahr über zu Weihnachten, sodass sie zwischen den Lieferungen keine Pause brauchen. Sie können nur jeweils ein Haus mit Geschenken beliefern. Sie müssen den Schlitten des Weihnachtsmanns zurücknehmen und das nächste Geschenk abholen, bevor sie zum nächsten Haus gehen. Aus Gründen, die ich nicht teilen darf, verbringen Elfen keine Zeit zwischen dem Schlitten des Weihnachtsmanns und den Häusern (sondern können nur reisen, wenn der Schlitten des Weihnachtsmanns auf dem Dach liegt), und sein Schlitten bewegt sich auch nicht von Haus zu Haus. (Santas Schlitten muss von Haus zu Haus ziehen, um Kraftstoff zu sammeln, aber ich sage bereits zu viel).

Elfen, die Geschenke ausliefern, müssen vier Sekunden * pro Auslieferung der Geschenke verbringen , und Elfen, die Kohle ausliefern, müssen fünf Sekunden * pro Auslieferung verbringen (gemäß den Bestimmungen der Santa Aviation Administration müssen Handschuhe mit Kohlenstaub sofort verbrannt werden den Schlitten besteigen, was einige Zeit in Anspruch nimmt). Außerdem müssen die Häuser in der Reihenfolge, in der sie sich auf der Karte befinden, von links nach rechts besucht werden, und Elfen können erst dann Geschenke an andere Häuser liefern, wenn alle Geschenke an das Haus geliefert wurden, in dem sie sich gerade befinden.

Wenn wir annehmen würden, dass der Weihnachtsmann mehr als genug Elfen für diese Region hat, würde es nur so lange dauern, bis jemandem auf der Freche-Liste ein Geschenk überreicht wird, 5 Sekunden pro Haus oder 4 Sekunden pro Haus, wenn alle nett sind.

Im Gegensatz zu früheren Spielzeiten hat der kommende Weihnachtsmann möglicherweise nicht mehr als genug Elfen für jede Region, daher sind 4 Sekunden die absolute Mindestzeit. * , um Geschenke an ein bestimmtes Haus zu liefern, es sei denn, es gibt 0 nette Leute und 0 ungezogene Leute, in welchem ​​Fall es 0 Sekunden dauern wird.

Darüber hinaus benötigt der Weihnachtsmann mindestens drei Elfen, wenn in einem der Häuser jemand auf der Liste der unartigen Menschen steht. Wenn mindestens eines der Häuser jemanden auf der netten Liste hat und keiner von ihnen Leute auf der frechen Liste hat, braucht der Weihnachtsmann mindestens zwei Elfen. Wenn keines der Häuser weihnachtlich ist, dauert eine beliebige Anzahl von Elfen (einschließlich 0) 0 Sekunden.

Auf der Karte des Weihnachtsmanns wird ein Haus durch a dargestellt *, und jedes Haus wird durch a geteilt +. Der Weihnachtsmann verwendet immer noch die gleichen Karten wie bei der anderen Herausforderung , aber ich werde hier eine Dokumentation darüber einfügen.

Zu beiden Seiten des Hauses befindet sich eine Zahl - die linke für die Anzahl der ungezogenen Personen im Haus und die rechte für die Anzahl der netten Personen im Haus. Wenn auf einer Seite keine Zahl steht, wird sie als 0 interpretiert.

Ich weiß, es hört sich vielleicht verrückt an, aber manche Leute mögen Weihnachten nicht. Manchmal hat ein Haus also keine Nummer auf beiden Seiten.

Eine von Santas Karten könnte ungefähr so ​​aussehen.

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

Nehmen wir an, der Weihnachtsmann hat neun Elfen in seinem Schlitten.

  1. (0s) Das erste Haus hat 1 freche und 3 nette Leute. Drei der Elfen liefern Kohle in fünf Sekunden und sechs Geschenke in vier Sekunden. Nach fünf Sekunden bewegt sich der Schlitten des Weihnachtsmanns zum nächsten Haus

  2. (5s) Das zweite Haus hat 2 freche und 0 nette Leute. Sechs der Elfen liefern Kohle, was fünf Sekunden dauert. Nach fünf Sekunden bewegt sich der Schlitten des Weihnachtsmanns zum nächsten Haus

  3. (10s) Das dritte Haus hat 0 freche und 5 nette Leute. Acht der Elfen bringen vier Geschenke (derjenige, der zurückgelassen wird, kann kein Geschenk bringen). Nach vier Sekunden sind alle Elfen zurück, und zwei von ihnen holen das andere Geschenk (der Schlitten muss warten, bis die Elfen zurück sind, bevor er zum nächsten Haus geht), und brauchen weitere vier Sekunden

  4. (18s) Das vierte Haus ist nicht in Weihnachtsstimmung, hat also 0 freche und 0 nette Leute und wird übersprungen

  5. (18s) Das fünfte Haus hat 4 freche und 7 nette Leute. Das wird etwas kompliziert ...

    I. Alle neun Elfen gehen, um drei Geschenke der Kohle zu liefern (lassen Sie t + 0s, geben Sie t + 5s zurück). Nach 5s sind sie alle wieder auf dem Schlitten und drei von ihnen bringen das letzte Geschenk von Kohle (lassen Sie t + 5s, geben Sie t + 10s zurück), während die anderen sechs von ihnen gehen, um drei nette Geschenke zu bringen (lassen Sie t +) 5s, return t + 9s).

    III. Nach vier Sekunden sind sechs der Elfen zurück und bringen drei weitere schöne Geschenke (lassen Sie t + 9s, geben Sie t + 13s zurück).

    IV. Eine Sekunde nachdem sie gegangen sind, kehren die drei Elfen, die das Kohlengeschenk gebracht haben, zurück, und zwei von ihnen gehen, um das letzte schöne Geschenk zu bringen (lassen Sie + 10s, geben Sie t + 14s zurück).

  6. (18 + 14 = 32 Sekunden ) Der Weihnachtsmann liefert keine Geschenke mehr in diese Region.

Wie wir sehen können, benötigt der Weihnachtsmann insgesamt 32 Sekunden , um Geschenke in diese Region zu bringen. Das war jedoch eine stark vereinfachte Version einer der Karten des Weihnachtsmanns. Normalerweise bestehen die Karten des Weihnachtsmanns aus mehreren Zeilen und sind quadratisch, damit sie besser auf seine Liste passen. Eine normale Karte könnte ungefähr so ​​aussehen (a \nam Ende jeder Zeile)

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

Bei 26 Elfen (oder einer höheren Menge) würde es 71 Sekunden dauern, bis der Weihnachtsmann kommt .
Bei 20 Elfen würde der Weihnachtsmann 76 Sekunden brauchen .
Bei 15 Elfen würde der Weihnachtsmann 80 Sekunden brauchen .
Bei 3 Elfen würde der Weihnachtsmann 288 Sekunden brauchen .
Mit 2 Elfen (oder einer niedrigeren Menge) wäre es unmöglich.

Oh, und noch etwas - die Reihenfolge, in der die Elfen Geschenke ausliefern, spielt eine Rolle (wegen der Zeitverschiebung beim Ausliefern von Geschenken ungezogener / netter Leute), daher sollte Ihr Code immer die geringste Zeit ausgeben, die die Elfen zum Ausliefern von Geschenken benötigen.

Herausforderung

Hilf dem Weihnachtsmann herauszufinden, wie lange es dauert, bis eine bestimmte Anzahl von Elfen Geschenke ausliefert.

Häuser

  • Ein Haus wird durch a dargestellt *
  • Häuser werden durch geteilt +
  • Die Zahl auf der linken Seite des Hauses symbolisiert die Anzahl der ungezogenen Personen (keine Zahl bedeutet 0)
  • Die Zahl rechts symbolisiert die Anzahl der netten Menschen (keine Zahl bedeutet 0)
  • Möglicherweise enthält \ndie Eingabe Zeilenumbrüche ( ), die ebenfalls als Teilung behandelt werden sollten

Elfen

  • Weihnachtsmann braucht Hilfe von drei Elfen für freche Menschen (Kohle als Geschenke viel schwerer ist), und es wird diese Elfen nimmt 5 Sekunden * die Geschenke zu liefern
  • Der Weihnachtsmann braucht Hilfe von zwei Elfen für nette Menschen, und diese Elfen brauchen vier Sekunden * , um die Geschenke zu bringen
  • Wenn es auf beiden Seiten des Hauses keine Nummer gibt, wird der Weihnachtsmann das Haus nicht besuchen und dafür wird es keine Zeit in Anspruch nehmen (Menschen, die nicht in Weihnachtsstimmung sind, verdienen nicht einmal Kohle).

Santa

  • Der Weihnachtsmann muss nacheinander Geschenke zu den Häusern bringen
  • Der Weihnachtsmann kann nicht in das nächste Haus umziehen, bis alle Elfen wieder auf dem Schlitten sind und alle Geschenke in dieses Haus gebracht wurden (wir wollen die Elfen nicht zurücklassen, oder?)
  • Der Schlitten des Weihnachtsmanns verbringt keine Zeit damit, von Haus zu Haus zu reisen. (Auch aus Gründen, die ich nicht teilen darf.)

Was ist zu tun

Drucken Sie anhand einer Karte mit Häusern und einer Reihe von Elfen aus, wie lange der Weihnachtsmann benötigt, um die Häuser auf der Karte mit Geschenken zu beliefern.

* (Ich kann die Zeit, die Elfen für die Zustellung von Geschenken benötigen, nicht mit anderen teilen. Ich kann weder bestätigen noch leugnen, dass die in dieser Herausforderung angegebenen Zeiten korrekt sind.)

Regeln

  • Es gibt zwei Eingaben - die Karte und die Anzahl der Elfen. Die Eingaben können entweder als Argumente für eine Funktion oder von STDIN oder einem gleichwertigen Wert übernommen werden . Wenn es in Ihrer Sprache nicht möglich ist, zwei Eingaben vorzunehmen, können Sie die beiden Eingaben nur dann als eine einzige Eingabezeichenfolge akzeptieren, die durch ein Zeichen begrenzt ist, das normalerweise nicht in einer Eingabe enthalten ist (keine +*\noder 0-9- die Eingabezeichenfolge darf nicht mehrdeutig sein). zB ,.
  • Die Anzahl der Elfen ist immer eine nicht negative Ganzzahl (0 ist gültig)
  • Die Ausgabe kann entweder der Rückgabewert einer Funktion sein oder auf STDOUT oder ein gleichwertiges Format gedruckt werden . Wenn es für den Weihnachtsmann nicht möglich ist, Geschenke mit einer bestimmten Anzahl von Elfen in die jeweilige Region zu bringen, müssen Sie eine konsistente negative Zahl oder eine konsistente Nachricht ohne darin enthaltene Zahlen ausgeben
  • Alles zu gedruckt STDERR wird ignoriert, so dass Sie nicht das Ergebnis oder die Fehlermeldung gedruckt werden können STDERR
  • Ihr Programm kann bei einer ungültigen Anzahl von Elfen für eine Region nicht abstürzen
  • Die Ausgabe sollte nur die Gesamtzeit sein, die der Weihnachtsmann benötigt, um die Geschenke mit der angegebenen Anzahl von Elfen auszuliefern.
  • Die Ausgabe sollte immer so kurz wie möglich sein, damit die Elfen Geschenke ausliefern können
  • Die Eingabe enthält nur Zahlen, +, *, und neue Zeilen \n(es sei denn , Sie ein anderes Zeichen angeben , für welches der Eingang enthält , wenn Sie die Sprache nicht zwei Eingänge nehmen kann (Blick auf der ersten Regel) )
  • Es gelten Standardlücken

Testfälle

"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

(Hoffentlich habe ich das alles richtig verstanden)

Wertung

Der Weihnachtsmann verbringt jeden Tag damit, sich viele Dinge anzuschauen - alle Geschenke, die er ausliefern wird, alle Elfen, die er hat, alle Häuser, in die er Geschenke ausliefert ... Für den Weihnachtsmann wäre das beste Weihnachtsgeschenk in der Lage, ein bisschen von etwas zu sehen. Aus diesem Grund gewinnt die kürzeste Übermittlung in Bytes .

Bestenliste

Dies ist ein Stapel-Snippet, das sowohl eine Rangliste als auch eine Übersicht der Gewinner nach Sprache generiert.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift unter Verwendung der folgenden Markdown-Vorlage

## Language Name, N bytes

Wobei N die Größe Ihrer Übermittlung in Byte ist

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. alte Punkte durchstreichen oder Flags in die Byteanzahl aufnehmen möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in Ihrer Kopfzeile ist

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

Code-Snippet anzeigen

code-golf string Jojodmo
quelle
Ich denke, 288 sollte 281 lauten : (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(obwohl ich sagen muss, dass ich nicht den ganzen "Aufsatz" gelesen habe!)
Jonathan Allan
@JonathanAllan Yea ... Ich habe versehentlich viel zu viel Zeit damit verbracht, die Herausforderung zu schreiben ... Hoppla ... Wie auch immer, der Schlüssel, der fehlt, ist, dass der Schlitten des Weihnachtsmanns warten muss, bis alle Elfen wieder an Bord sind, bevor er zu ihm wechselt Das nächste Haus, obwohl das Addieren und Multiplizieren aller Zahlen in einigen Fällen funktioniert, funktioniert es in den meisten Fällen nicht. Beispiel: Bei 9 Elfen 4*7dauert das Haus 14 Sekunden (dies wird ungefähr zur Hälfte im "Aufsatz" behandelt, kurz bevor die 2D-Karte eingeführt wird), aber (4 * 5) + (7 * 4) = 48
Jojodmo
Der Wert von 288 ist für das Beispiel mit 3 Elfen, also müssten sie naughty*5+nice*4bei jedem Haus immer den vollen Schlag ausführen , oder? (Beachten Sie, dass es 4*7in diesem Beispiel keine gibt )
Jonathan Allan
Schaffen die Elfen die Kohle immer zuerst aus dem Weg (wie in Ihrem Beispiel) oder planen sie effizient? Wenn zum Beispiel die Karte wäre 5*15und es 9Elfen gäbe, würde es die (minimalen) 20 Sekunden oder 22 Sekunden dauern? In diesen Textdarstellungen finden Sie eine Abbildung dieses Beispiels.
Jonathan Allan
EDIT to above 5*15sollte lauten 4*15.
Jonathan Allan

Antworten:

4

Ruby , 433 400 Bytes

Nun, dieser ist in der Tat schwer, denn es stellt sich heraus, dass die Planung der Elfen NP schwer ist.

Bitte seien Sie auch nett, dies ist meine erste Einreichung, daher habe ich möglicherweise einige offensichtliche Optimierungen verpasst:

->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}

Probieren Sie es online!

Ich hatte anfangs längere Testfälle, aber da ich alle möglichen Permutationen für die Planung durchlaufe, dauert es in einigen Fällen zu lange, sodass ich sie entfernte.

elyalvarado
quelle
2
Willkommen bei PPCG! Du hast definitiv eine schwere Herausforderung für deine erste Antwort ausgewählt
Jo King,
2

Java (OpenJDK 8) , 344 Byte

Die Planung von Elfen ist schwieriger als ich dachte, daher dauerte dies eine Weile und ist ziemlich lang.

Trotzdem war dies definitiv meine Lieblingsherausforderung beim Codieren von Golf! 

(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;}

Probieren Sie es online (mit allen Tests)!

Erläuterung;

Machen Sie sich bereit: Es ist eine lange

    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

NB: Diese Antwort hängt davon ab, dass meine Korrekturen an den Testfällen korrekt sind

Luke Stevens
quelle
Ich denke (e-y*3)/2-> e-y*3>>1spart ein Byte. (Gilt höchstwahrscheinlich auch für (e-c*3)/2.)
Jonathan Frech
runTest("1*4",5,12);nicht (Sie erhalten "1*4", 5 elves => 13 FAILED. Ich war erstaunt, wie Ihr Algorithmus war so in so wenige Bytes Zeitplan gut, so dass ich es gegen alle möglichen Kombinationen von 0-7 (Elfen lief, frech und nett) und fand nur ein paar , wo es nicht zu Geben Sie die optimale Zeit. Dies ist die kleinste Kombination, wenn es fehlschlägt. Übrigens, erstaunliche Logik zu planen, für eine lange Zeit hatte ich keine Ahnung, wie Sie es getan haben.
elyalvarado