Vous connaissez peut-être le mathématicien von Koch par son célèbre flocon de neige. Cependant, il a des problèmes informatiques plus intéressants dans ses manches. En effet, jetons un œil à cette conjecture:

Étant donné un arbre avec des nnœuds (donc des n-1arêtes). Trouvez un moyen d'énumérer les nœuds de 1à net, en conséquence, les arêtes de 1à n-1de telle manière que, pour chaque arête, kla différence de ses numéros de nœuds soit égale à k. La conjecture est que cela est toujours possible.

Voici un exemple pour le rendre parfaitement clair:

TA TÂCHE

Votre code prendra en entrée un arbre, vous pouvez prendre le format que vous souhaitez mais pour les cas de test je fournirai l'arbre par leurs arcs et la liste de leurs nœuds.

Par exemple, c'est l'entrée pour l'arbre dans l'image:

[a,b,c,d,e,f,g]
d -> a
a -> b
a -> g
b -> c
b -> e
e -> f

Votre code doit renvoyer l'arborescence avec des nœuds et des bords numérotés. Vous pouvez renvoyer une sortie plus graphique mais je fournirai ce type de sortie pour les cas de test:

[a7,b3,c6,d1,e5,f4,g2]
d -> a 6
a -> b 4
a -> g 5
b -> c 3
b -> e 2
e -> f 1

CAS D'ESSAI

[a,b,c,d,e,f,g]             [a7,b3,c6,d1,e5,f4,g2]
d -> a                      d -> a 6
a -> b                      a -> b 4
a -> g             =>       a -> g 5
b -> c                      b -> c 3
b -> e                      b -> e 2
e -> f                      e -> f 1


[a,b,c,d]                   [a4,b1,c3,d2]
a -> b                      a -> b 3
b -> c            =>        b -> c 2
b -> d                      b -> d 1


[a,b,c,d,e]                [a2,b3,c1,d4,e5]
a -> b                      a -> b 1
b -> c                      b -> c 2
c -> d             =>       c -> d 3
c -> e                      c -> e 4

C'est le code-golf, c'est la réponse la plus courte en octets!

Remarque: Ceci est plus fort que la conjecture de Ringel-Kotzig , qui stipule que chaque arbre a un étiquetage gracieux. Étant donné que dans la conjecture de Koch, il n'est pas possible de sauter des entiers pour l'étiquetage contrairement à l'étiquetage gracieux dans la conjecture de Ringel-Kotzig. Un étiquetage gracieux a déjà été demandé ici .

Gelée , 30 octets

JŒ!³,$€
ǵy⁴VIAµ€Q⁼$€TðḢịø³JŒ!

Essayez-le en ligne! (Utilisez GṄ³çGcomme pied de page pour rendre la sortie plus jolie.)

Entrées similaires à l'exemple, par exemple abcdefet[d,a],[a,b],[a,g],[b,c],[b,e],[e,f]

Affiche la liste, par exemple a,b,c,d,e,fdans l'ordre.

Remarque: Mon programme produit des valeurs différentes de celles des cas de test car il existe plusieurs possibilités qui sont toutes valides.

Explication

JŒ!³,$€                - helper function, generates all possible numberings, input is e.g. 'abcd'
J                      - range(len(input)). e.g. [1,2,3,4]
 Œ!                    - all permutations of the range.
   ³,$                 - pair the input with ... 
      €                - each permutation. Sample element e.g. ['abcd',[3,1,2,4]]

ǵy⁴VIAµ€Q⁼$€TðḢịø³JŒ! - main dyadic link, input is e.g. 'abcd' and '[a,b],[b,c],[b,d]'
 µy                    - use a numbering as an element-wise mapping e.g. 'abcd'->[3,1,2,4]
   ⁴                   - apply this to the list of edges. e.g. '[3,1],[1,2],[1,4]'
    V                  - turn this into an internal list.
     IAµ€              - find absolute difference on each edge
         Q⁼            - Is this invariant under deduplication? Returns 1 if the numbering is valid; 0 otherwise.
Ç          $€          - apply this to all possible numberings
             Tð        - return the indices of all valid numberings
               Ḣ       - choose the first one and
                ị      - get the element corresponding to its index in 
                 ø³JŒ! - all possible numberings 

Économisez 1 octet en montrant toutes les solutions possibles:

JŒ!³,$€
ǵy⁴VIAµ€Q⁼$€Tðịø³JŒ!

Essayez-le en ligne! (Utilisez GṄ³çG⁷³Gcomme pied de page pour rendre la sortie plus jolie)

Utilisez le convertisseur pour copier-coller le cas de test dans une liste d'entrée.

Rubis, 108 octets

Fonction lamba, accepte un tableau de tableaux à 2 éléments contenant les arêtes (où chaque arête est exprimée comme une paire de nombres correspondant aux notes pertinentes.)

->a{[*1..1+n=a.size].permutation.map{|i|k=a.map{|j|(i[j[0]-1]-i[j[1]-1]).abs}
(k&k).size==n&&(return[i,k])}}

Non testé dans le programme de test

f=->a{                                    #Accept an array of n tuples (where n is the number of EDGES in this case)
  [*1..1+n=a.size].permutation.map{|i|    #Generate a range 1..n+1 to label the nodes, convert to array, make an array of all permutations and iterate through it.
    k=a.map{|j|(i[j[0]-1]-i[j[1]-1]).abs} #Iterate through a, build an array k of differences between nodes per current permutation, as a trial edge labelling.
    (k&k).size==n&&(return[i,k])          #Intersect k with itself to remove duplicates. If all elements are unique the size will still equal n so
  }                                       #return a 2 element array [list of nodes, list of edges]
}

p f[[[4,1],[1,2],[1,7],[2,3],[2,5],[5,6]]]

p f[[[1,2],[2,3],[2,4]]]

p f[[[1,2],[2,3],[3,4],[2,5]]]

Production

la sortie est un tableau à 2 éléments, contenant:

la nouvelle numérotation des nœuds

la numérotation des bords.

Par exemple, le premier bord du premier exemple [4,1]est entre les nœuds 6 et 1 sous la nouvelle numérotation des nœuds et est donc le bord 6-1 = 5.

[[1, 5, 2, 6, 3, 4, 7], [5, 4, 6, 3, 2, 1]]
[[1, 4, 2, 3], [3, 2, 1]]
[[1, 5, 3, 4, 2], [4, 2, 1, 3]]

Il y a en fait plusieurs solutons pour chaque cas de test. la returnarrête la fonction une fois la première trouvée.