Description du problème
Nous aimons tous un Twix (parce que c'est le meilleur bonbon), mais c'est le premier Halloween des enfants --- nous devons prendre au moins un de chaque type de bonbons pour eux. À chaque Halloween, tous les résidents de l'avenue Numberline envoient un e-mail indiquant les types de bonbons qu'ils donneront cette année.
Oh! Et nous vivons dans un monde 1D.
Étant exceptionnellement paresseux à certains égards et pas à d'autres, nous avons fait une carte des maisons indiquant leurs positions le long de la rue. Nous avons également noté les types de bonbons dont ils disposent. Voici la carte que nous avons faite pour cette année:
[(-2, {"Kisses", "KitKats"}),
(1, {"KitKats", "Peanut Butter Cups"}),
(6, {"Kisses", "Twix"}),
(9, {"Skittles"}),
(10, {"Twix"})]
Pour le bien des petites jambes des enfants, nous devons trouver la marche la plus courte à partir de n'importe quelle maison du quartier pour recueillir au moins un bonbon de chaque type.
Exemples
À la demande de quelques utilisateurs (dont Shaggy), je vais lancer quelques exemples pratiques. Espérons que cela clarifie les choses. :) Entrée:
[(-2, {"Kisses", "KitKats"}),
(1, {"KitKats", "Peanut Butter Cups"}),
(6, {"Kisses", "Twix"}),
(9, {"Skittles"}),
(10, {"Twix"})]
Production:
[1, 2, 3]
Une autre carte et solution ...
Contribution:
[(-3, {"KitKats", "Twix"}),
(-1, {"Hundred Grands"}),
(3, {"Kisses"}),
(12, {"Hundred Grands", "Twix", "KitKats"})]
Sortie :
[0, 1, 2]
Nous pourrions commencer à la maison coordonnée 9 à ramasser des bonbons aux maisons 6 et 1. Cela remplit le quota de bonbons en marchant 8 unités, mais est-ce la solution la plus courte?
Règles
Les entrées doivent prendre un argument unique structuré de manière similaire à l'exemple et produire les indices des maisons à visiter dans la solution la plus courte.
Les règles de golf de code typiques s'appliquent: la solution correcte la plus courte en octets gagne!
PS C'était une question d'entrevue qui m'a été donnée par l'une des plus grandes entreprises technologiques du monde. Si vous n'aimez pas le golf, essayez de trouver une solution temporelle O (k * n) où k est le nombre de types de bonbons et n est le nombre de maisons.
Éditer
Comme l'a souligné Jonathon Allan, il existe une certaine confusion quant à la signification des «indices» dans ce cas. Nous voulons afficher les positions des maisons dans la liste des arguments et non leurs coordonnées sur la voie.
Réponses:
Gelée , 16 octets
Un lien monadique acceptant l'entrée comme décrit dans une liste triée des maisons de l'avenue Numberline les plus basses aux plus hautes (si nous devons accepter toute commande, nous pouvons ajouter une
Ṣ
) qui donne le chemin le plus court commençant à la maison numérotée la plus basse et remontant l'avenue.Essayez-le en ligne!
Si nous voulons trouver tous ces chemins les plus courts, remplacez les octets de fin,,
ÞḢ
parÐṂ
; c'est aussi 16 octets.Comment?
la source
Python 2 ,
133130127 octetsEssayez-le en ligne!
la source
05AB1E , 22 octets
Suppose que les nombres dans la liste d'entrée sont triés du plus bas au plus élevé.
Si plusieurs solutions sont trouvées, elles sortiront toutes.
Essayez-le en ligne.
Explication:
la source
Perl 6 , 70 octets
Essayez-le en ligne!
la source
Haskell ,
343372 octetsMerci à @ ASCII uniquement pour les améliorations, il y a aussi une variante de 271 octets qu'il a proposée dans les commentaires :)
Essayez-le en ligne!
Non golfé
Premier essai
la source
Solution temporelle O (k * n), avec espace O (k * n)
Ainsi, notre algorithme est:
la source