Combien de temps faut-il au Père Noël pour livrer ses cadeaux?

12

J'ai publié ce défi il y a quelque temps, qui concerne le nombre d' elfes dont le Père Noël a besoin pour offrir des cadeaux.

En raison de l'augmentation de la population, le Père Noël est un peu plus pressé cette année. Bien que dans le passé nous fonctionnions de manière très asynchrone, nous commençons à expérimenter de plus en plus de synchronisation. Ainsi, le Père Noël a besoin de savoir combien de temps il lui faudra pour livrer des cadeaux à chaque région avec un nombre donné d'elfes.

Le poids du charbon n'a pas changé au cours des deux dernières années - il est toujours plus lourd que les cadeaux, donc le Père Noël a besoin de trois elfes par personne coquine dans la maison et de deux elfes par personne agréable dans la maison.

Les elfes passent toute l'année à s'entraîner pour Noël, ils n'ont donc pas besoin de repos entre les accouchements. Ils ne peuvent livrer des cadeaux qu'à une seule maison à la fois, et doivent remonter le traîneau du Père Noël et récupérer le prochain cadeau avant d'aller à la prochaine maison. Pour des raisons que je ne suis pas libre de partager, les elfes ne passent pas de temps à voyager entre le traîneau du Père Noël et les maisons (mais ne peuvent voyager que lorsque le traîneau du Père Noël est sur le toit), ni son traîneau ne passe du temps à se déplacer de maison en maison. (Traîneau du Père Noël ne doit se déplacer de maison en maison afin de carburant Collect, mais je suis déjà en dire trop).

Les elfes qui livrent des cadeaux doivent passer quatre secondes * chacun à livrer les cadeaux, et les elfes qui livrent du charbon doivent passer cinq secondes * chacun à les livrer (conformément aux réglementations de la Santa Aviation Administration, les gants avec de la poussière de charbon doivent être incinérés immédiatement après monter à bord du traîneau, ce qui prend un certain temps). De plus, les maisons doivent être visitées dans l'ordre où elles se trouvent sur la carte, de gauche à droite, et les elfes ne peuvent pas commencer à livrer des cadeaux à d'autres maisons tant que tous les cadeaux n'ont pas été livrés à la maison où ils se trouvent actuellement.

Si nous supposions que le Père Noël avait plus qu'assez d'elfes pour cette région, cela ne prendrait que le temps de livrer un cadeau à quelqu'un sur la liste coquine, 5 secondes, par maison, ou 4 secondes par maison si tout le monde est gentil.

Pourtant, contrairement aux saisons précédentes, ce Noël de Noël à venir pourrait ne pas avoir plus qu'assez d'elfes pour chaque région, donc 4 secondes est le temps minimum absolu * qu'il faudra pour livrer des cadeaux à une maison donnée, à moins qu'il n'y ait 0 des gens sympas et 0 vilains, auquel cas cela prendra 0 seconde.

De plus, si même l'une des maisons a quelqu'un sur la liste coquine, le Père Noël aura besoin d'au moins trois elfes. Si au moins une des maisons a quelqu'un sur la belle liste et qu'aucune d'entre elles n'a de personnes sur la liste coquine, le Père Noël aura besoin d'au moins deux elfes. Si aucune des maisons n'est dans l'esprit de Noël, n'importe quel nombre d'elfes (dont 0) prendra 0 seconde.

Sur la carte du Père Noël, une maison est représentée par un *, et chaque maison est divisée par un +. Le Père Noël utilise toujours les mêmes cartes que dans l'autre défi , mais je vais inclure de la documentation à leur sujet ici.

Il y aura un numéro de chaque côté de la maison - celui de gauche représentant le nombre de vilains dans la maison, et celui de droite représentant le nombre de gentilles personnes dans la maison. S'il n'y a pas de nombre d'un côté, il est interprété comme un 0.

Je sais que cela peut sembler fou, mais certaines personnes "n'aiment pas Noël", donc parfois, une maison peut ne pas avoir de numéro de chaque côté.

Une des cartes du Père Noël pourrait ressembler à ceci.

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

Disons que le Père Noël a neuf elfes dans son traîneau.

  1. (0s) La première maison a 1 coquine et 3 belles personnes. Trois des elfes livrent du charbon en cinq secondes et six des cadeaux en quatre secondes. Après cinq secondes, le traîneau du Père Noël se déplace vers la prochaine maison

  2. (5s) La deuxième maison a 2 coquines et 0 personnes sympas. Six des elfes livrent du charbon, ce qui prend cinq secondes. Après cinq secondes, le traîneau du Père Noël se déplace vers la prochaine maison

  3. (10s) La troisième maison a 0 coquines et 5 personnes sympas. Huit des elfes vont livrer quatre cadeaux (celui qui reste ne peut pas livrer un cadeau). Après quatre secondes, tous les elfes sont de retour, et deux d'entre eux vont livrer l'autre présent (le traîneau doit attendre que les elfes reviennent avant d'aller dans la maison suivante), ce qui prend encore quatre secondes

  4. (18s) La quatrième maison n'est pas dans l'esprit de Noël, donc 0 coquine et 0 gentille personne, et est sautée

  5. (18s) La cinquième maison a 4 coquines et 7 belles personnes. Cela devient un peu compliqué ...

    I. Les neuf elfes vont livrer trois cadeaux de charbon (laisser t + 0s, retourner t + 5s) II. Après 5s, ils sont tous de retour sur le traîneau, et trois d'entre eux vont livrer le dernier cadeau de charbon (laisser t + 5s, retourner t + 10s) tandis que les six autres vont livrer trois beaux cadeaux (laisser t + 5s, retour t + 9s).

    III. Après quatre secondes, six des elfes sont de retour et vont livrer trois autres cadeaux sympas (laisser t + 9s, retourner t + 13s).

    IV. Une seconde après leur départ, les trois elfes qui livraient le charbon présent reviennent, et deux d'entre eux partent pour livrer le dernier beau cadeau (congé + 10s, retour t + 14s)

  6. (18 + 14 = 32 secondes ) Le Père Noël a fini de livrer des cadeaux dans cette région.

Comme nous pouvons le voir, il faut un total de 32 secondes au Père Noël pour livrer des cadeaux dans cette région. Mais c'était une version trop simplifiée d'une des cartes du Père Noël. Normalement, les cartes du Père Noël ont plusieurs lignes et sont de forme carrée pour mieux s'intégrer dans sa liste. Une carte normale pourrait ressembler à ceci (un \nà la fin de chaque ligne)

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

Avec 26 elfes (ou tout montant supérieur), cela prendrait au père Noël 71 secondes .
Avec 20 elfes , cela prendrait 76 secondes au Père Noël .
Avec 15 elfes , cela prendrait 80 secondes au Père Noël .
Avec 3 elfes , cela prendrait 288 secondes au Père Noël .
Avec 2 elfes (ou n'importe quel montant inférieur), ce serait impossible.

Oh, et encore une chose - l'ordre dans lequel les elfes livrent les cadeaux est important (en raison de la différence de temps entre les cadeaux des méchants / gentils), donc votre code devrait toujours afficher le moins de temps que les elfes peuvent prendre pour livrer les cadeaux.

Défi

Aidez le Père Noël à déterminer combien de temps il faudra à un certain nombre d'elfes pour livrer des cadeaux.

Maisons

  • Une maison est représentée par un *
  • Les maisons sont divisées par +
  • Le nombre à gauche de la maison symbolise le nombre de vilains (aucun chiffre ne signifie 0)
  • Le nombre à droite symbolise le nombre de personnes sympas (aucun chiffre ne signifie 0)
  • Il peut y avoir des sauts de ligne ( \n) en entrée, qui doivent également être traités comme un fractionnement

Elfes

  • Le père Noël a besoin de l'aide de trois elfes pour les vilains (le charbon est beaucoup plus lourd que les cadeaux), et il faudra cinq secondes * à ces elfes pour livrer les cadeaux
  • Le Père Noël a besoin de l'aide de deux elfes pour les gens sympas, et il faudra quatre secondes à ces elfes * pour livrer les cadeaux
  • S'il n'y a pas de numéro de chaque côté de la maison, le Père Noël ne visitera pas cette maison, et cela ne prendra donc pas de temps (les gens qui ne sont pas dans l'esprit de Noël ne méritent même pas le charbon)

Père Noël

  • Le Père Noël doit livrer des cadeaux aux maisons un par un
  • Le Père Noël ne peut pas passer à la maison voisine avant que tous les elfes soient de retour sur le traîneau et que tous les cadeaux aient été livrés à cette maison (nous ne voulons pas laisser les elfes derrière nous, maintenant?)
  • Le traîneau du Père Noël ne passe pas de temps à voyager de maison en maison (encore une fois, pour des raisons que je ne suis pas libre de partager)

Que faire

Sur la carte d'une maison et d'un certain nombre d'elfes, indiquez combien de temps il faudra au Père Noël pour livrer des cadeaux aux maisons sur la carte.

* (Je ne peux pas partager le temps qu'il faut aux elfes pour livrer des cadeaux. Je ne peux ni confirmer ni infirmer que les temps inclus dans ce défi sont corrects)

Règles

  • Il y a deux entrées - la carte et le nombre d'elfes. Les entrées peuvent être prises soit comme arguments d'une fonction, soit depuis STDIN ou équivalent. Si la prise de deux entrées est impossible dans votre langue, alors et seulement alors pouvez-vous accepter les deux entrées comme une seule chaîne d'entrée, délimitée par un caractère qui n'est normalement pas dans une entrée (pas l'un de +*\nou 0-9- la chaîne d'entrée ne peut pas être ambiguë) par exemple ,.
  • Le nombre d'elfes sera toujours un entier non négatif (0 est valide)
  • La sortie peut être soit la valeur de retour d'une fonction, soit imprimée sur STDOUT ou équivalent. S'il est impossible pour le Père Noël de livrer des cadeaux dans la région donnée avec un nombre donné d'elfes, vous devez produire un nombre négatif cohérent ou un message cohérent sans aucun nombre
  • Tout ce qui est imprimé dans STDERR sera ignoré, vous ne pouvez donc pas imprimer le résultat ou le message d' erreur dans STDERR
  • Votre programme ne peut pas planter étant donné un nombre invalide d'elfes pour une région
  • La sortie ne devrait être que le temps total qu'il faudra au Père Noël pour livrer les cadeaux avec le nombre donné d'elfes.
  • La sortie devrait toujours être le moins de temps qu'il faut aux elfes pour livrer des cadeaux
  • L'entrée ne contient que des chiffres, des +, *et des sauts de ligne \n(sauf si vous spécifiez un autre caractère que l'entrée comprendra si votre langue ne peut pas prendre deux entrées (regardez la première règle) )
  • Des échappatoires standard s'appliquent

Cas de test

"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

(j'espère que tout cela est correct)

Notation

Le Père Noël passe chaque jour à toujours regarder beaucoup de choses - tous les cadeaux qu'il va livrer, tous les elfes qu'il a, toutes les maisons où il livre des cadeaux ... Pour le Père Noël, le meilleur cadeau de Noël serait capable de voir un petit quelque chose. Pour cette raison, la soumission la plus courte en octets l'emporte .

Classement

Il s'agit d'un extrait de pile qui génère à la fois un classement et un aperçu des gagnants par langue.

Pour vous assurer que votre réponse apparaît, veuillez commencer votre réponse avec un titre en utilisant le modèle Markdown suivant

## Language Name, N bytes

Où N est la taille, en octets, de votre soumission

Si vous souhaitez inclure plusieurs nombres dans votre en-tête (par exemple, en supprimant les anciens scores ou en incluant des indicateurs dans le nombre d'octets), assurez-vous simplement que le score réel est le dernier numéro de votre en-tête

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

Afficher l'extrait de code

code-golf string Jojodmo
la source
Je pense que 288 devrait lire 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(bien que je dois dire que je n'ai pas lu tout "l'essai"!)
Jonathan Allan
@JonathanAllan Oui ... J'ai accidentellement passé trop de temps à écrire le défi ... oups ... Quoi qu'il en soit, l'élément clé qui manque est que le traîneau du Père Noël doit attendre que tous les elfes remontent à bord avant de passer à la maison suivante, donc bien que l'addition de tous les nombres et leur multiplication puissent fonctionner dans certains cas, cela ne fonctionne pas dans la plupart des cas. Par exemple, avec 9 elfes, la maison 4*7prend 14 secondes (ce qui est couvert à mi-chemin dans "l'essai", juste avant l'introduction de la carte 2D) mais (4 * 5) + (7 * 4) = 48
Jojodmo
La valeur 288 est pour l'exemple avec 3 elfes, donc ils devraient toujours effectuer le coup complet de naughty*5+nice*4chaque maison, non? (notez qu'il n'y en a pas 4*7dans cet exemple)
Jonathan Allan
Les elfes éliminent-ils toujours le charbon en premier (comme dans votre exemple) ou planifient-ils efficacement? Par exemple, si la carte était 5*15et qu'il y avait des 9elfes, cela prendrait-il les 20 ou 22 secondes (minimes)? Voir ces représentations textuelles pour voir une illustration de cet exemple.
Jonathan Allan
EDIT to above 5*15devrait se lire 4*15.
Jonathan Allan

Réponses:

4

Ruby , 433 400 octets

Eh bien, celui-ci est en effet difficile, car il s'avère que la programmation des elfes est difficile NP.

Aussi, soyez gentil, c'est ma première soumission, donc j'ai peut-être manqué quelques optimisations évidentes:

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

Essayez-le en ligne!

Au départ, j'avais des cas de test plus longs, mais comme je répète toutes les permutations possibles pour la planification, dans certains cas, cela prend trop de temps, alors je les ai supprimés.

elyalvarado
la source
2
Bienvenue chez PPCG! Vous avez certainement choisi un défi difficile pour votre première réponse
Jo King
2

Java (OpenJDK 8) , 344 octets

La planification des elfes est plus difficile que je ne le pensais, donc cela a pris un peu de temps et est assez long.

Malgré cela, cela a certainement été mon défi préféré pour coder le 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;}

Essayez-le en ligne (avec tous les tests)!

Explication;

Préparez-vous: c'est long

    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: Cette réponse dépend de la correction de mes corrections aux cas de test

Luke Stevens
la source
Je pense que (e-y*3)/2-> e-y*3>>1enregistre un octet. (Très probablement également applicable à (e-c*3)/2.)
Jonathan Frech
runTest("1*4",5,12);échoue (vous obtenez "1*4", 5 elves => 13 FAILED. J'ai été étonné de voir comment votre algorithme était si bon à planifier en si peu d'octets, alors je l'ai exécuté contre toutes les combinaisons possibles de 0 à 7 (elfes, vilains et gentils) et en ai trouvé quelques-unes où il ne parvient pas à donne le temps optimal. C'est la plus petite combinaison en cas d'échec. BTW, une logique incroyable à planifier, pendant longtemps je ne savais pas comment tu l'as fait.
elyalvarado