10
\$\begingroup\$

You may know the mathematician von Koch by his famous snowflake. However he has more interesting computer science problems up his sleeves. Indeed, let's take a look at this conjecture:

Given a tree with n nodes (thus n-1 edges). Find a way to enumerate the nodes from 1 to n and, accordingly, the edges from 1 to n-1 in such a way, that for each edge k the difference of its node numbers equals to k. The conjecture is that this is always possible.

Here's an example to make it perfectly clear :

enter image description here

YOUR TASK

Your code will take as input a tree, you can take the format you want but for the test cases I will provide the tree by their arcs and the list of their nodes.

For example this is the input for the tree in the picture :

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

Your code must return the tree with nodes and edges numbered. You can return a more graphical output but I will provide this kind of output for the test cases :

[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

TEST CASES

[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

This is this the shortest answer in bytes win!

Note : This is stronger than the Ringel-Kotzig conjecture, which states every tree has a graceful labeling. Since in the Koch conjecture it is not possible to skip integers for the labeling contrary to the graceful labeling in the Ringel-Kotzig conjecture. Graceful labeling has been asked before here.

\$\endgroup\$
  • \$\begingroup\$ Will there be more than 26 nodes? \$\endgroup\$ – Leaky Nun May 6 '17 at 15:14
  • \$\begingroup\$ @LeakyNun It is already hard to brute force after 17 nodes ^^ \$\endgroup\$ – user68509 May 6 '17 at 15:15
  • \$\begingroup\$ @WheatWizard It's absolutely not the same as the von Koch conjecture since in this thread you're allowed to skip integers. The whole point of the conjecture is making the labeling possible without skipping \$\endgroup\$ – user68509 May 6 '17 at 15:26
3
\$\begingroup\$

Jelly, 30 bytes

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

Try it online! (Use GṄ³çG as footer to make output prettier. )

Inputs similar to example, e.g. abcdef and [d,a],[a,b],[a,g],[b,c],[b,e],[e,f]

Outputs the list e.g. a,b,c,d,e,f in order.

Note: My program produces different values than the test cases as there are several possibilities which are all valid.

Explanation

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 

Save 1 byte by showing all possible solutions:

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

Try it online! (Use GṄ³çG⁷³G as a footer to make output prettier)

Use converter to copy-paste test case into an input list.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 108 bytes

lamba function, accepts an array of 2-element arrays containing the edges (where each edge is expressed as a pair of numbers corresponding to the relevant notes.)

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

Ungolfed in test program

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

Output

output is a 2 element array, containing:

the new node numbering

the edge numbering.

For example the first edge of the first example [4,1] is between nodes 6 and 1 under the new node numbering and is therefore edge 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]]

There are in fact multiple solutons for each test case. the return stops the function once the first one is found.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy