# Reconstruct a list from its prefixes

A list $$\[a_1,a_2,a_3 \cdots a_n]\$$ can be uniquely represented as an unordered list of its prefixes - $$\ [[a_1],[a_1, a_2], [a_1,a_2,a_3] \cdots [a_1,a_2,a_3 \cdots a_n]] \$$. This can be in any order - for example, $$\[1, 2, 3]\$$ could be represented by any of $$\[[1],[1,2],[1,2,3]]\$$, $$\[[3,2,1],[2,1],[1]]\$$, or $$\[[2, 1], [1],[3,1,2]]\$$; and these are all equivalent up to order and all represent $$\[1, 2, 3]\$$.

Your challenge is, given a (non-empty) list of the prefixes of a list of positive integers in any order, to return the list represented by that. The list may contain repeated items. This is , shortest wins!

## Testcases

Note: the order of the output does matter, e.g. for the third test case you must output [6, 4, 8, 7], not [7, 4, 8, 6].

[[1], [1, 2], [1, 2, 3]] -> [1, 2, 3]
[[2, 1], [1], [3, 1, 2]] -> [1, 2, 3]
[[6, 4, 8], [7, 4, 8, 6], [6, 4], [6]] -> [6, 4, 8, 7]
[[6, 2, 3, 1], [1, 2], [1], [6, 1, 2], [2, 2, 3, 1, 6]] -> [1, 2, 6, 3, 2]
[[2], [30, 2, 27, 40], [27, 40, 2, 89, 30], [2, 30, 27], [27, 2]] -> [2, 27, 30, 40, 89]
[[8, 4], [4, 8, 8, 4], [4, 4, 8], [4]] -> [4, 8, 4, 8]
[[22, 98, 62, 80], [80, 98], [22, 98, 10, 62, 80, 87, 2], [98], [62, 80, 98], [22, 98, 2, 62, 80], [2, 22, 98, 62, 87, 80]] -> [98, 80, 62, 22, 2, 87, 10]
[[43, 84, 56, 19], [56, 43], [43, 56, 19], [43]] -> [43, 56, 19, 84]
• Can the list have repeats?
– xnor
Feb 29 at 22:39
• @xnor Yes, whoops, I'll add some testcases for that. Feb 29 at 22:40
• Perhaps replace "set" with "ordered list" — a set is usually taken to mean an unordered data type that stores unique values. Feb 29 at 23:21
• @doubleunary Maybe it should be multiset. or bag. Which is both unordered and may contains duplicate values. And example is collections.Counter in Python or std::multiset int C++.
– tsh
Mar 1 at 2:27
• It really bothers me that the empty prefix isn't included. :( Mar 1 at 16:39

# Python 3, 51 bytes

lambda l,p=0:[-p+(p:=x)for x in sorted(map(sum,l))]

Try it online!

Take the sums of the input lists, sort them in increasing order, take adjacent differences. This works because the difference between the sums of two consecutive prefixes is just the added element, and sorting works because the numbers are positive.

# Jelly, 4 bytes

§ṢŻI

A monadic Link that accepts a list of lists of positive integers and yields a list of positive integers.

Try it online!

### How?

§    - sums
Ṣ   - sort
Ż  - prefix a zero
I - forward differences

import Data.List
(zipWith(-)<*>(0:)).sort.map sum

Try it online!

You guessed it, another port of xnor's Python answer.

## Slightly different approach, 62605957 56 bytes

Another one bytes the dust thanks to Wheat Wizard.

import Data.List
concat.(zipWith(\\)<*>([]:)).sortOn sum

Try it online!

Figured I'd try something different for the sake of variety. Concatenate the forward differences of the prefixes (plus the empty list) sorted by sum. Ties the first approach if the output can be a list of singletons.

• Since the input is always positive sortOn sum works in place of sortOn(0<$), and is 1 byte shorter. Mar 1 at 17:12 • @WheatWizard Inching closer and closer… but still so far. Thanks! Mar 2 at 1:51 # R, 34 bytes \(L)diff(c(0,sort(sapply(L,sum)))) Attempt This Online! Uses the same approach as @xnor's answer. # Python 2, 73 bytes lambda L:reduce(lambda v,l:map(l.remove,v)and v+[l[0]],sorted(L,key=len)) Try it online! An anonymous function that accepts a List of lists and returns a list as result. How does it work? With the input sorted by length (so [[2, 1], [1], [3, 1, 2]] becomes [[1], [2, 1], [3, 1, 2]]), for each sublist, remove the first occurrence of elements already visited from l and mark the remaining element as visited. It works for duplicates. # 05AB1E, 5 bytes ¯ªéO¥ Explanation: ¯ª # Append an empty list to the (implicit) input list of lists é # Sort these lists by length O # Sum each inner list ¥ # Pop and get their forward differences # (after which this list is output implicitly as result) # K (ngn/k), 11 bytes -':.1<:\+/' Try it online! Another port of xnor's answer. +/' sums, .1<:\ sort, -': differences. # Haskell + hgl, 14 bytes δ<(0:)<sm<<sj Attempt This Online! A simple shameless port of the haskell answer. # Reflection I'm a little bothered by the fact the empty prefix is not included in the input. Both because I am a helpless pedant and because it adds a bunch of bytes to my answer. It adds 5-bytes, over a third of the total answer. But the challenge is what it is, and I should expect challenges to do things that don't fit with my desire for recursive symmetry. The fact that this is such a deficit is indicative more that hgl needs to be more flexible. • I need to change the type of K. It is virtually impossible for Haskell to ever infer its type, and so I have a 1-byte function which I consistently can't use for its intended purpose. This goes for helpers like K0 and Qi as well. • paf appears to consistently be more useful than pa, even though pa is given the 2-byte name. They should probably be swapped. • I should add a version of paf which takes a "starting value". It would be helpful here. This can be implemented on Scan instead of foldable. • A sort combined with a map would be good. Like sB but which returns the converted values instead of the pre-converted values. # Haskell, 7871 59 bytes -7 bytes thanks to @Wheat Wizard, -12 bytes thanks to @xnor f w|h:_<-[x|[x]<-w]=h:f[a++b|(a,_:b)<-span(/=h)<$>w]
f _=[]

Try it online!

• Mar 1 at 10:04
• @totallyhuman it's basically another solution, I'd post it separately Mar 1 at 10:14
• Fair, just didn't feel like making another answer for a port. Mar 1 at 10:16
• Some improvements on this method Mar 1 at 17:50
• Down to 59 using span
– xnor
Mar 2 at 4:37

# UiuaSBCS, 9 bytes

°\+⊏⍏.⍚/+

Try it!

°\+⊏⍏.⍚/+
⍚/+  # sums
⊏⍏.     # sort
°\+        # differences

# MathGolf, 6 bytes

mΣs0▌│

Try it online.

Explanation:

m       # Map over each inner list of the (implicit) input-list of lists:
Σ      #  Sum each inner list
s     # Sort the sums from lowest to highest
0▌   # Prepend a 0 to the list of sums
│  # Pop and get the forward differences of this list
# (after which the entire stack is output implicitly as result)

# Charcoal, 20 bytes

ＷΦθ⁼Ｌκ⊕Ｌυ⊞υ⁻Σ⊟ι↨υ¹Ｉυ

Try it online! Link is to verbose version of code. Explanation:

ＷΦθ⁼Ｌκ⊕Ｌυ

While there is a prefix with one more member than the number of terms collected so far, ...

⊞υ⁻Σ⊟ι↨υ¹

... subtract the sum of that prefix from the sum of the terms collected so far and push that to the (predefined empty) list of terms so far.

Ｉυ

Output the final list.

# APL+WIN, 19 bytes

Prompts for prefixes as nested vectors.

-2-/0,+/¨m[⍋+/¨m←⎕]

Try it online! Thanks to Dyalog Classic

# Scala 3, 84 bytes

Golfed version. Attempt This Online!

x=>{x.map(_.sum).sorted.foldLeft((Seq[Int](),0)){(A,c)=>val(a,p)=A;(a:+(c-p),c)}._1}

Ungolfed version. Attempt This Online!

object Main {
def main(args: Array[String]): Unit = {
val inputs = List(
List(List(1), List(1, 2), List(1, 2, 3)),
List(List(2, 1), List(1), List(3, 1, 2)),
List(List(6, 4, 8), List(7, 4, 8, 6), List(6, 4), List(6)),
List(List(6, 2, 3, 1), List(1, 2), List(1), List(6, 1, 2), List(2, 2, 3, 1, 6)),
List(List(2), List(30, 2, 27, 40), List(27, 40, 2, 89, 30), List(2, 30, 27), List(27, 2)),
List(List(8, 4), List(4, 8, 8, 4), List(4, 4, 8), List(4)),
List(List(22, 98, 62, 80), List(80, 98), List(22, 98, 10, 62, 80, 87, 2), List(98), List(62, 80, 98), List(22, 98, 2, 62, 80), List(2, 22, 98, 62, 87, 80)),
List(List(43, 84, 56, 19), List(56, 43), List(43, 56, 19), List(43))
)

inputs.foreach { input =>
val result = calculateDifference(input)

Try it online!

# JavaScript (V8), 82 bytes

s=>(x=s.map(y=>y.reduce((a,c)=>a+c)).sort((a,b)=>a-b))&&x.map((z,i)=>i?z-x[i-1]:z)

Try it online!

Arnauld's magic, 66 bytes

a=>a.map(b=>eval(b.join+)).sort((a,b)=>a-b).map(v=>-p+(p=v),p=0)

Try it online!

• You can save 4 bytes by removing some unnecessary parentheses: s=>(x=s.map(y=>y.reduce((a,c)=>a+c)).sort((a,b)=>a-b))&&x.map((z,i)=>i?z-x[i-1]:z) Try it online! Mar 2 at 3:07
• D'oh. Thanks @ConorO'Brien. Mar 2 at 8:08
• 66 bytes Mar 2 at 8:13

# Wolfram Language (Mathematica), 77 bytes

Fold[({x,y}={##};First@Select[Permutations@y,Most@#==x&])&,SortBy[#,Length]]&

Since it is difficult to improve Arnauld’s algorithm, I try to solve a more general problem.
This code reconstructs any list: with negative numbers, strings etc.

Try it online!

# jq, 50 bytes

map(add)|sort|.[0],range(length)as$i|.[$i+1]-.[$i] Try it online! Uses the Arnauld/xnor approach of sum then sort then pairwise differences. Raises an error, but only after the entire output has been streamed. ## General solution, 71 bytes sort_by(length)|while(any;.[0][0]as$i|map(del(.[index(\$i)]))[1:])[0][0]

Try it online!

Works on lists with arbitrary content - we take the shortest prefix (which has a length of 1), remove it and remove its first (only) value from all remaining prefixes. This gives us a prefix list for the list's tail. We then repeat the process for that prefix list. This eventually gives us a prefix list for the target list and all its suffixes. We then take the first (only) value from the first (shortest) prefix in each of those lists, to get the elements of the target list in order.