Convert a parent vector to a depth vector

Question

Consider the following diagram of a tree structure, with each node numbered by its index in a depth-first pre-order traversal:

0 ├─────┬──┬──┐ 1 5 6 8 ├──┐ │ ├──┬───────┐ 2 3 7 9 10 13 │ ├───┐ 4 11 12

Label each node by its depth—that is, the number of ancestors it has, with the root node having depth zero. (In this diagram, this corresponds with the node's vertical placement.)

0 ├─────┬──┬──┐ 1 1 1 1 ├──┐ │ ├──┬───────┐ 2 2 2 2 2 2 │ ├───┐ 3 3 3

Flattening this tree, again by depth-first pre-order traversal, gives the depth vector:

0 1 2 2 3 1 1 2 1 2 2 3 3 2

In this representation, the depth of the Nth node is at index N.

Now consider the same tree but with each node numbered by its parent's index (with the root node said to be its own parent.)

0 ├─────┬──┬──┐ 0 0 0 0 ├──┐ │ ├──┬───────┐ 1 1 6 8 8 8 │ ├───┐ 3 10 10

Flattening this, similarly, gives the parent vector:

0 0 1 1 3 0 0 6 0 8 8 10 10 8

In this representation, the parent of the Nth node is at index N.

Either of these representations is enough to reconstruct the original tree structure. Often, when writing parsers in array languages, a depth vector is a convenient way to build the tree while parsing, but a parent vector is more useful when operating on the nodes of the tree. Therefore, converting from a depth vector to a parent vector is a somewhat common operation, and a quite simple one: for each node N, its parent is the closest node to the left whose depth is one less than N's. Converting from a parent vector to a depth vector is a less common operation, but I think a more interesting one. It is still fairly simple, but has somewhat more to it than the inverse and I think it has some room for interesting golf tricks.

In this challenge, you are tasked to construct the depth vector given the parent vector.

You may choose to omit the root node in both the input and output. If you do, you may count depth one in the test cases as zero. You may use either zero- or one-based indices for the parent vector. The input will never represent an invalid tree (e.g. nodes which point to themselves or are out of order.)

Test cases:

 0 0 → 0 1 0 → 0 0 0 1 2 3 4 1 6 → 0 1 2 3 4 5 2 3 0 0 1 2 3 3 0 6 6 6 9 → 0 1 2 3 4 4 1 2 2 2 3 0 0 1 1 3 0 0 6 0 8 8 10 10 8 → 0 1 2 2 3 1 1 2 1 2 2 3 3 2

If the root is omitted in the input, must it be omitted in the output? (and vice versa) — Unrelated String
– Unrelated String, Commented Mar 24 at 16:26
Can we have the parent index of the root be nil rather than 0? — Adamátor
– Adamátor, Commented Mar 25 at 8:30
Nice challenge! There seems to be a small problem with the horizontal alignment of the tree diagrams (at least on my browser). — aeh5040
– aeh5040, Commented Mar 25 at 11:11
@xigoi I did consider this when sandboxing the challenge, but I think I'll say no — noodle person
– noodle person, Commented Mar 25 at 12:47

Mukundan314 · Accepted Answer · 2025-03-24 13:25:14Z

12

JavaScript (Node.js), 30 bytes

x=>x.map((i,j)=>x[~j]=x[-i]+1)

Try it online!

Python, 46 bytes

lambda x,r=[0]:[(r:=r+[r[i]+1])[-1]for i in x]

Attempt This Online!

root node is omitted in both input and output of both answers

edited Mar 24 at 13:25

answered Mar 24 at 12:41

Mukundan314

13.7k1 gold badge19 silver badges62 bronze badges

1

\$\begingroup\$ +1, that JS answer is pretty smart. I was trying to port it and couldn't figure out why it didn't work when I inserted values at index ~j, until I realized the ~j aren't indices, but instead are string keys of a dictionary that you're building inside the array. \$\endgroup\$

Kevin Cruijssen
– Kevin Cruijssen

2025-03-24 14:03:48 +00:00
Commented Mar 24 at 14:03
2

\$\begingroup\$ @KevinCruijssen, a while after posting I realized I had overcomplicated it x=>x.map((i,j)=>x[j]=-~x[i-1]) works too which might be easier to port. \$\endgroup\$

Mukundan314
– Mukundan314

2025-03-24 14:06:29 +00:00
Commented Mar 24 at 14:06

Add a comment |

colossus16 · Accepted Answer · 2025-03-24 13:52:31Z

Haskell, 26 bytes

f p=0:[1+f p!!i|i<-tail p]

Try it online!

The depth of each node (except the root) will be 1 plus the depth of its parent. Since the parent always comes before its children in the input I can use self reference to get the parent's depth with f p!!i. Then I just need to ensure my base case (the root) is handled specially by always prepending 0 and only iterating over the tail.

m90 · Accepted Answer · 2025-03-24 17:47:04Z

x86-64 machine code, 17 bytes

57 59 83 0F FF AD 8B 04 81 FF C0 AB FF CA 75 F5 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the depth vector, as an array of 32-bit integers; the address of the parent vector, as an array of 32-bit integers, in RSI; and the number of nodes in EDX.

In assembly:

f: push rdi; pop rcx # Copy the depth-vector address into RCX. or DWORD PTR [rdi], -1 # Set the first value to -1 (will become 0). r: lodsd # Load a parent-vector value into EAX, advancing RSI. mov eax, [rcx + 4*rax] # Load that index's depth into EAX. inc eax # Add 1 to the depth in EAX. stosd # Store EAX into the depth vector, advancing RDI. dec edx # Subtract 1 from EDX, counting down from the length. jnz r # Jump back to repeat if it's nonzero. ret # Return.

Unrelated String · Accepted Answer · 2025-03-24 19:02:27Z

Jelly, 6 bytes

JịƬ>1S

Try it online!

Takes input 1-indexed with the root (test harness converts for convenience).

J Starting with the 1-index of each node, ị 1-index each into the parent vector Ƭ repeatedly until nothing changes (i.e. they're all 1). >1S How many values are greater than 1 in each column?

The initial J is needed to distinguish the root from its immediate children, so that it takes 0 steps to reach itself but its children need 1. Omitting the root complicates things, as out-of-bounds indexing wraps around--the root is needed as a "sink" that keeps things 1 once they've been 1 once, because the loop keeps running until the entire vector hits a cycle, and the cycle needs to be convenient even if looping on individual elements (as in JịƬ€¹Ẉ’) because Ƭ is Jelly's only looping quick that reuses the right argument instead of Doing The Fibonacci Thing™.

Kevin Cruijssen · Accepted Answer · 2025-03-26 09:13:27Z

05AB1E, 9 8 bytes

ÎvDyè>=ª

Port of @Mukundan314's Python answer, but outputs each value on a separated newline instead.
Root note is omitted.

Try it online or verify all test cases.

Could have been 7 bytes if we're allowed to input with omitted root note, but output with root note, by removing the =:
Try it online or verify all test cases.

Explanation:

Î # Push 0 and the input-list v # Pop the list and loop over each value `y`: D # Duplicate the current list, # or the 0 in the first iteration yè # Pop and push its y'th (0-based modular) value > # Increase that by 1 = # Output it with trailing newline (without popping) ª # Pop and add it to the list # (convert the initial 0 to list of digits [0] before adding to it)

Joao-3 · Accepted Answer · 2025-03-24 20:50:44Z

Uiua, 15 13 bytes

∧(˜⊂+1⊸⊡)⊃↘↙1

Try it in the pad!

Thanks to @Tbw for -2 bytes!

Takes in a 0-indexed array, with the root node included.

For every node, the program looks up the corresponding depth in the (partial) result array, then adds 1.

You can get rid of the fill with ∧(˜⊂+1⊸⊡):¤°⊂ or ∧(˜⊂+1⊸⊡)⊃↘↙1 — Tbw
– Tbw, Commented Mar 24 at 17:29

Neil · Accepted Answer · 2025-03-25 01:15:20Z

Charcoal, 13 bytes

ＦＡ⊞υ∧Ｌυ⊕§υιＩυ

Try it online! Link is to verbose version of code. I/O includes root (input value is arbitrary). Explanation:

ＦＡ

Loop over the parent vector.

⊞υ∧Ｌυ⊕§υι

If this is the root, then push zero, otherwise push one more than the parent's depth.

Ｉυ

Output the depth vector.

att · Accepted Answer · 2025-03-25 06:45:20Z

APL(Dyalog Unicode), 11 bytes ^SBCS

(⊢⍪1+⌷∘,)⌿⊖

Try it on APLgolf!

1-indexed.

( )⌿⊖ for each (non-root) node ⊢⍪ append 1+⌷ 1+ its parent's depth ∘, (fix initial case)

APL(Dyalog Unicode), 13 bytes ^SBCS

⊂(⊢⌊1+⌷)⍣≡⍳⍤≢

Try it on APLgolf!

Also 1-indexed.

 ⍳⍤≢ starting from 1 2...n, ( )⍣≡ fixed point of: ⊢⌊ min with ⊂ 1+⌷ 1+ parents' depths

z.. · Accepted Answer · 2025-03-25 06:47:05Z

Google Sheets, 54 bytes

^{Port of Mukundan314's answer}

Expects input in A:A.

=REDUCE(0,TOCOL(A:A,1),LAMBDA(x,y,{x;INDEX(x,y+1)+1}))

G B · Accepted Answer · 2025-03-25 12:36:06Z

3

Ruby, 38 bytes

->n{k=0;n[k]=1+n[n[k]]while n[k+=1];n}

Try it online!

answered Mar 25 at 12:36

G B

23.4k1 gold badge24 silver badges55 bronze badges

\$\begingroup\$ I think you can use "A program or function taking input by reference may output by modifying the input value in place" to not return n \$\endgroup\$

Mukundan314
– Mukundan314

2025-03-25 14:20:01 +00:00
Commented Mar 25 at 14:20
\$\begingroup\$ You can remove k=0; and replace it with $. for -1 byte \$\endgroup\$

Glory2Ukraine
– Glory2Ukraine

2025-03-25 15:23:07 +00:00
Commented Mar 25 at 15:23

Add a comment |

TwilightSparkle · Accepted Answer · 2025-03-30 01:34:54Z

3

GolfScript, 22 20 19 17 16 bytes

~:&{{}{(&=}/,}%`

Try it online!

This is nicer

edited Mar 30 at 1:34

answered Mar 29 at 7:44

TwilightSparkle

4,0261 gold badge18 silver badges36 bronze badges

2

\$\begingroup\$ I love how the edit history goes from "This is so bad" to "This is horrible" to nothing as you golfed the solution XD Always love a good golfscript solution I'll take a look at how this works later \$\endgroup\$

noodle person
– noodle person

2025-03-29 11:10:40 +00:00
Commented Mar 29 at 11:10
1

\$\begingroup\$ @noodleperson Now it's nice \$\endgroup\$

TwilightSparkle
– TwilightSparkle

2025-03-29 14:52:46 +00:00
Commented Mar 29 at 14:52

Add a comment |

Glory2Ukraine · Accepted Answer · 2025-03-26 08:28:09Z

R, 33 bytes

\(x)Reduce(\(a,b)c(a,a[b+1]+1),x)

Attempt This Online!

The golfiest way to work with vectors is to avoid counters. Therefore the best options are Reduce, for or Map, the last two were 38 and 48 bytes long, respectively.

_Related: _{Mukundan314's answer,} _{z..'s answer}

Neil · Accepted Answer · 2025-03-26 10:25:11Z

Retina 0.8.2, 81 bytes

+1`((_*)\d+ )(\d) $1_$2$3 \d+ $* +`_1 +`(_)+(?<=(#*)\B(?<-1> \w+)+) #$2 ^|#+ $.&

Try it online! Link includes test cases. Explanation:

+1`((_*)\d+ )(\d) $1_$2$3

Generate (in unary using _s) the index of each node.

\d+ $*

Convert the parent indices to unary (using 1s).

+`_1

Subtract each parent index from its index.

+`(_)+(?<=(#*)\B(?<-1> \w+)+) #$2

Replace the offsets with their depth (in unary using #s), repeating until all nodes have been processed. (Each iteration replaces the next layer of nodes.)

^|#+ $.&

Convert the depths to decimal.

if the input is 0 0 1 1 3 0 0 6 0 8 8 10 10 3 the result has to be 0 1 2 2 3 1 1 2 1 2 2 3 3 2 or 0 1 2 2 3 1 1 2 1 2 2 3 3 3? (change only the last element) — Rosario
– Rosario, Commented Mar 28 at 12:34
@Rosario The input has to be a valid pre-order traversal, which that is not. — Neil
– Neil, Commented Mar 28 at 14:03

CursorCoercer · Accepted Answer · 2025-03-27 17:54:20Z

Pyth, 8 bytes

ml.u@+ZQ

Try it online!

Input is 0-indexed with root node omitted.

Explanation

ml.u@+ZQNd)Q # implicitly add Nd)Q # implicitly assign Q = eval(input()) m Q # map over Q l # length .u d) # repeatedly call lambda N on d until the result repeats, returning a list of all intermediate results @+ZQN # ([0]+Q)[N]

Rosario · Accepted Answer · 2025-03-29 16:08:02Z

APL(NARS), 37 chars

{{2≥⍵:⍵-1⋄1+∇¯1+a[⍵]+a[⍵]=1}¨⍳≢a←⍳⍨⍵}

The input has to be one array of integers (not a scalar, a vector). I have not much familiarity with this subject. It all start from one function like d below

r←d w;l;i;k;a i←1⋄l←≢w⋄p←0⋄r←⍬⋄a←⍳⍨w →0×⍳i>l⋄→3×⍳i≤2⋄→3×⍳i=k←a[i]⋄p←r[k+k=1] r,←p⋄(i p)+←1⋄→2

//14+23+40+17=94

this function d it seems fits the data test... It would work that increment one counter p that represent deep that start from 0, but if the number has index >2 and in the array of input is already calculated the deep, than assign to p the deep already calculated and continue as above. For root the deep is 0, for all the node has parent root the deep is 1. The recursive function is just the traslation of that d function from iterative to recursive, i think will be more slow because it has to recaulculate values. The complexity of the function d is the same of the function {⍳⍨⍵} i think is len(input)^2 ({⍳⍨⍵} would return the first index where appear the value in the input array), for the recursive function i don't know complexity.

Test:

 f←{{2≥⍵:⍵-1⋄1+∇¯1+a[⍵]+a[⍵]=1}¨⍳≢a←⍳⍨⍵} f 0 ┌1──┐ │ ¯1│ └~──┘ f ,0 ┌1─┐ │ 0│ └~─┘ f 0 0 ┌2───┐ │ 0 1│ └~───┘ f 0 0 1 2 3 4 1 6 ┌8───────────────┐ │ 0 1 2 3 4 5 2 3│ └~───────────────┘ f 0 0 1 2 3 3 0 6 6 6 9 ┌11────────────────────┐ │ 0 1 2 3 4 4 1 2 2 2 3│ └~─────────────────────┘ f 0 0 1 1 3 0 0 6 0 8 8 10 10 8 ┌14──────────────────────────┐ │ 0 1 2 2 3 1 1 2 1 2 2 3 3 2│ └~───────────────────────────┘ f 0 0 1 1 3 0 0 6 0 8 8 10 10 3 ┌14──────────────────────────┐ │ 0 1 2 2 3 1 1 2 1 2 2 3 3 3│ └~───────────────────────────┘

It is possible to golf the d function for have

r←d w;l;i;a i←1⋄l←≢w⋄r←,0⋄a←⍳⍨w →0×⍳l<i+←1⋄r,←1+r[¯1+a[i]+a[i]=1]⋄→2

//12+20+37=69

Unrelated String · Accepted Answer · 2025-03-27 19:37:20Z

Retina, 52 bytes

vrL`.*\d\b %(/^\d+ /+~`.*?(\d+)(#.*)?$ $1`\d+¶$$&# #

Try it online!

Input is a space-separated list; output is newline-separated. (Test harness patches this to be less annoying.) Root-inclusive. Fundamentally 0.8.2-incompatible due to relying on eval stages for dynamic limits.

vrL`.*\d\b

Get each prefix of the input's elements on its own line. (The \d\b is to only get prefixes of the input's elements, and not all prefixes of its string representation!)

%(

introduces a group stage mapped over lines:

/^\d+ /+~`.*?(\d+)(#.*)?$ $1`\d+¶$$&#

The first stage loops while there's a space after the first run of digits /^\d+ /+, and executes an eval stage ~ which evaluates the result of replacing the entire string capturing the first run of digits .*?(\d+) followed by a pound sign or the end of the string (#.*)?$ with: another replace stage (implicit) which matches runs of digits \d+ and replaces only the run at the matched index $1` with the match $$& followed by a pound sign #.

The second stage in the group simply counts every pound sign on the line.

aqui8 · Accepted Answer · 2025-04-10 11:52:50Z

1

BQN, 11 chars

(⊢∾1+⊏⟜⥊)´⌽

Adapted from the APL solution

answered Apr 10 at 11:52

aqui8

1111 bronze badge

\$\begingroup\$ Welcome to the site! Nice first submission. \$\endgroup\$

noodle person
– noodle person

2025-04-10 12:03:59 +00:00
Commented Apr 10 at 12:03

Add a comment |

Stack Exchange Network

Convert a parent vector to a depth vector

17 Answers 17

JavaScript (Node.js), 30 bytes

Python, 46 bytes

Haskell, 26 bytes

x86-64 machine code, 17 bytes

Jelly, 6 bytes

05AB1E, 9 8 bytes

Uiua, 15 13 bytes

Charcoal, 13 bytes

APL(Dyalog Unicode), 11 bytes ^SBCS

APL(Dyalog Unicode), 13 bytes ^SBCS

Google Sheets, 54 bytes

Ruby, 38 bytes

GolfScript, 22 20 19 17 16 bytes

R, 33 bytes

Retina 0.8.2, 81 bytes

Pyth, 8 bytes

Explanation

APL(NARS), 37 chars

Retina, 52 bytes

BQN, 11 chars

Hot Network Questions

Convert a parent vector to a depth vector

17 Answers 17

JavaScript (Node.js), 30 bytes

Python, 46 bytes

Haskell, 26 bytes

x86-64 machine code, 17 bytes

Jelly, 6 bytes

05AB1E, 9 8 bytes

Uiua, 15 13 bytes

Charcoal, 13 bytes

APL(Dyalog Unicode), 11 bytes SBCS

APL(Dyalog Unicode), 13 bytes SBCS

Google Sheets, 54 bytes

Ruby, 38 bytes

GolfScript, 22 20 19 17 16 bytes

R, 33 bytes

Retina 0.8.2, 81 bytes

Pyth, 8 bytes

Explanation

APL(NARS), 37 chars

Retina, 52 bytes

BQN, 11 chars

Related

Hot Network Questions

APL(Dyalog Unicode), 11 bytes ^SBCS

APL(Dyalog Unicode), 13 bytes ^SBCS