13
\$\begingroup\$

In a Prüfer code is a unique sequence of integers that denotes a specific tree.

You can find the Prüfer code of a tree with the following algorithm taken from Wikipedia:

Consider a labeled tree T with vertices {1, 2, ..., n}. At step i, remove the leaf with the smallest label and set the ith element of the Prüfer sequence to be the label of this leaf's neighbor.

(Note that since it's a leaf it will only have one neighbor).

You should stop the iteration when only two vertices remain in the graph.

Task

Given a labeled tree as input output its Prüfer code. You may take input in any reasonable manner. Such as an adjacency matrix or your languages builtin graph representation. (You may not take input as a Prüfer code).

This is so you should aim to minimize the bytes in your source.

Test cases

Here are some inputs in ASCII with their outputs below. You do not need to support ASCII input like this.

    3
    |
1---2---4---6
    |
    5

{2,2,2,4}

1---4---3
    |
5---2---6---7
|
8

{4,4,2,6,2,5}

5---1---4   6
    |       |
    2---7---3

{1,1,2,7,3}
\$\endgroup\$
16
  • \$\begingroup\$ Can we take in a rooted tree as input? \$\endgroup\$
    – xnor
    May 11, 2017 at 23:51
  • \$\begingroup\$ Can we take input as something like [[2,1],[2,3],[2,5],[2,4,6]] for the first case? (i.e. each branch) \$\endgroup\$
    – hyper-neutrino
    May 11, 2017 at 23:52
  • \$\begingroup\$ @xnor Yes you can \$\endgroup\$
    – Wheat Wizard
    May 11, 2017 at 23:58
  • 1
    \$\begingroup\$ I feel like taking an input with edges or paths directed towards a root is precomputation towards the Prüfer Code. Either way, I think you should be clearer on "You may take input in any reasonable manner (You may not take input as a Prüfer code)." \$\endgroup\$
    – xnor
    May 12, 2017 at 0:24
  • \$\begingroup\$ @xnor Oh I didn't understand what Hyper Neutrino was asking. \$\endgroup\$
    – Wheat Wizard
    May 12, 2017 at 0:29

6 Answers 6

9
\$\begingroup\$

Mathematica, 34 bytes

<<Combinatorica`
LabeledTreeToCode

Somebody had to do it....

After loading the Combinatorica package, the function LabeledTreeToCode expects a tree input as an undirected graph with explicitly listed edges and vertices; for example, the input in the second test case could be Graph[{{{1, 4}}, {{4, 3}}, {{4, 2}}, {{2, 5}}, {{2, 6}}, {{6, 7}}, {{5, 8}}}, {1, 2, 3, 4, 5, 6, 7, 8}].

\$\endgroup\$
1
  • 6
    \$\begingroup\$ Of course there's a built-in to do this. >_> \$\endgroup\$
    – hyper-neutrino
    May 12, 2017 at 1:34
4
\$\begingroup\$

Python 3, 136 131 127 bytes

def f(t):
 while len(t)>2:
  m=min(x for x in t if len(t[x])<2);yield t[m][0];del t[m]
  for x in t:m in t[x]and t[x].remove(m)

Takes input as an adjacency matrix. First example:

>>> [*f({1:[2],2:[1,3,4,5],3:[2],4:[2,6],5:[2],6:[4]})]
[2, 2, 2, 4]
\$\endgroup\$
9
  • \$\begingroup\$ well I failed... \$\endgroup\$
    – hyper-neutrino
    May 12, 2017 at 0:16
  • \$\begingroup\$ @HyperNeutrino You were about 4 seconds faster! \$\endgroup\$
    – L3viathan
    May 12, 2017 at 0:17
  • \$\begingroup\$ Hehe yup! And about 2.7 times as long! :D gg \$\endgroup\$
    – hyper-neutrino
    May 12, 2017 at 0:17
  • 1
    \$\begingroup\$ del exists? >_> \$\endgroup\$
    – hyper-neutrino
    May 12, 2017 at 0:19
  • 2
    \$\begingroup\$ @WheatWizard You're right about the semicolons, but mixing tabs and spaces is an error in Python 3. \$\endgroup\$
    – L3viathan
    May 12, 2017 at 8:29
4
\$\begingroup\$

Jelly, 31 bytes

FĠLÞḢḢ
0ịµÇHĊṙ@µÇCịṪ,
WÇÐĿḢ€ṖṖḊ

A monadic link which takes a list of pairs of nodes (defining the edges) in any order (and each in any orientation) and returns the Prüfer Code as a list.

Try it online!

How?

FĠLÞḢḢ - Link 1, find leaf location: list of edges (node pairs)
F      - flatten
 Ġ     - group indices by value (sorted smallest to largest by value)
  LÞ   - sort by length (stable sort, so equal lengths remain in prior order)
    ḢḢ - head head (get the first of the first group. If there are leaves this yields
       -   the index of the smallest leaf in the flattened version of the list of edges)

0ịµÇHĊṙ@µÇCịṪ, - Link 2, separate smallest leaf: list with last item a list of edges
0ị             - item at index zero - the list of edges
  µ            - monadic chain separation (call that g)
   Ç           - call last link (1) as a monad (index of smallest leaf if flattened)
    H          - halve
     Ċ         - ceiling (round up)
      ṙ@       - rotate g left by that amount (places the edge to remove at the right)
        µ      - monadic chain separation (call that h)
         Ç     - call last link (1) as a monad (again)
          C    - complement (1-x)
            Ṫ  - tail h (removes and yields the edge)
           ị   - index into, 1-based and modular (gets the other node of the edge)
             , - pair with the modified h
               -    (i.e. [otherNode, restOfTree], ready for the next iteration)

WÇÐĿḢ€ṖṖḊ - Main link: list of edges (node pairs)
W         - wrap in a list (this is so the first iteration works)
  ÐĿ      - loop and collect intermediate results until no more change:
 Ç        -   call last link (2) as a monad
    Ḣ€    - head €ach (get the otherNodes, although the original tree is also collected)
      ṖṖ  - discard the two last results (they are excess to requirements)
        Ḋ - discard the first result (the tree, leaving just the Prüfer Code)
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 29 bytes

[Dg#ÐD˜{γé¬`U\X.å©Ï`XK`ˆ®_Ï]¯

Try it online!

Explanation

[Dg#                           # loop until only 1 link (2 vertices) remain
    ÐD                         # quadruple the current list of links
      ˜{                       # flatten and sort values
        γé                     # group by value and order by length of runs
          ¬`U                  # store the smallest leaf in X
             \X                # discard the sorted list and push X
               .å©             # check each link in the list if X is in that link
                  Ï`           # keep only that link
                    XK`ˆ       # add the value that isn't X to the global list
                        ®_Ï    # remove the handled link from the list of links
                           ]   # end loop
                            ¯  # output global list
\$\endgroup\$
1
\$\begingroup\$

Clojure, 111 bytes

#(loop[r[]G %](if-let[i(first(sort(remove(set(vals G))(keys G))))](recur(conj r(G i))(dissoc G i))(butlast r)))

Requires the input to be a hash-map, having "leaf-like" labels as keys and "root-like" labels as values. For example:

{1 2, 3 2, 5 2, 4 2, 6 4}
{1 4, 3 4, 4 2, 8 5, 5 2, 7 6, 6 2}

On each iteration it finds the smallest key which is not referenced by any other node, adds it to the result r and removes the node from the graph definition G. if-let goes to else case when G is empty, as first returns nil. Also the last element has to be dropped.

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

Python 2, 91 bytes

d=input()
while len(d)>2:m=min(d,key=lambda k:len(d[k]));n,=d[m];del d[m];d[n]-={m};print n

Try it online!

Based on L3viathan's solution. Takes a dictionary of sets representing adjacency lists.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.