Les philosophes ont longtemps réfléchi au problème du chariot . Malheureusement, aucun humain n'a encore résolu ce problème. Heureusement, en tant que programmeurs, nous pouvons utiliser des ordinateurs pour résoudre le problème pour nous!

Contribution

Votre programme prendra en entrée un graphe orienté (fini) (avec au plus une arête de xà y, pour tout xet y), avec un nœud désigné, et un entier non négatif attaché à chaque arête (représentant le nombre de personnes liées à cette piste) . De plus, chaque nœud a au moins un bord de sortie.

Le chariot démarre au nœud désigné. À chaque tour, si le chariot est au nœud x, l'utilitaire sélectionne un bord (x,y). Les gens sur ce bord meurent et le chariot est maintenant au bord y. Ce processus se poursuit pour toujours.

Notez que les gens ne peuvent mourir qu'une seule fois, donc si le bord (x,y)a des ngens attachés et que le chariot les traverse, disons, 100 fois, cela n'entraînera que des nmorts.

Production

L'utilitariste fait ses choix de manière à minimiser le nombre de personnes qui meurent (ce qui est garanti d'être fini, car il n'y a que des personnes finies). Votre programme affichera ce numéro.

Format d'entrée

Vous pouvez prendre le graphique d'entrée de la manière raisonnable qui vous convient. Par exemple, vous pouvez le prendre comme une matrice et compter le nœud désigné comme celui étiqueté 0. Ou vous pouvez utiliser quelque chose comme x1,y1,n1;x2,y2,n2;.... Par exemple 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0pour représenter le problème du chariot standard (avec des boucles à la fin).

Cas de test

• 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (passer de 0 à a, a à c (tuer une personne), puis continuer à boucler le chariot de c à c).
• 0,0,1;0,a,5;a,a,0 -> 1 (Continuez de 0 à 0, écrasez-vous sur 1 personne pour l'éternité),
• 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (notez que la solution gourmande d'aller en b serait incorrecte))
• 0,a,1;0,b,5;a,b,1;b,a,1 -> 3 (0 -> a -> b -> a -> b -> ...)
• 0,a,1;0,b,1;a,a,0;b,b,0 -> 1 (Notez qu'il existe deux options différentes que l'utilitaire pourrait prendre pour que les deux ne tuent qu'une seule personne)

Il s'agit de code-golf , donc la réponse la plus courte l'emporte! Bonne chance.

Remarques: Il n'y aura pas de boucles de boucle malade et la dérive multipiste est interdite. Aussi, bien que je préfère penser à ce problème en termes des trois lois (/ s) d'Asimov, Peter Taylor a noté dans le bac à sable que ce problème est mathématiquement équivalent à celui de trouver le rho (chemin de retour des boucles sur lui-même) de poids le plus faible .

Gelée , 27 23 octets

ṗL$µṭ0FIm2ASµÐḟµQ⁴ySµ€Ṃ

Essayez-le en ligne! (dernier cas de test)

Version cruelle (Mutilate the most people)

Prend la saisie sous forme de nombres. Pour le dernier exemple, 1est aet 2est b. 0est le nœud de départ. Le premier argument est la liste des bords (par exemple [0,1],[0,2],[1,1],[2,2]), et le deuxième argument est une liste des bords et le nombre de personnes sur eux (par exemple [[0,1],[0,2],[1,1],[2,2]],[1,1,0,0]).

Comment ça fonctionne

ṗL$µṭ0FIm2ASµÐḟµQ⁴ySµ€Ṃ
ṗL$                       - on the first argument, get the Cartesian power of it to its length.
                            this gives all paths of the length of the input. Cycles are implicit
   µ        µÐḟ           - get valid paths starting with 0 -- filter by:
    ṭ0                      - prepend 0
      F                     - flatten
       I                    - get the difference between elements
        m2                  - every second difference: 0 for each edge that starts at the node the previous edge ended at, nonzero otherwise.
          AS                - 0 iff all elements are 0
               µ    µ€    - on each path:
                Q           - remove repeat edges.
                 ⁴y         - translate according to the mapping in the second program argument
                   S        - Sum
                      Ṃ   - get the minimum of these.

Python 3 , 80 octets

y=lambda d,s=0,p=[],f=0:f in p and s or min(y(d,s+d[f][t],p+[f],t)for t in d[f])

Essayez-le en ligne!

Prend l'entrée comme un dictionnaire saisi par l'identifiant du nœud. Les entrées sont un dictionnaire de voisins et le nombre de personnes sur la piste entre un nœud et le voisin. Par exemple, pour le premier cas de test:

{0: {1: 0}, 1: {2: 5, 3: 1}, 2: {2: 0}, 3: {3: 0}}

0 est le nœud de départ, 1 est le nœud 'a', 2 est le nœud 'b', etc.

Perl 6 , 90 74 octets

Merci à Jo King pour -16 octets.

my&g=->\a,\b=0,\c=@,\d=0 {a{d}&&b||min map {g a,b+$^f,(|c,d),$^e},a{d}.kv}

Port de la solution Python de RootTwo .

Essayez-le en ligne!