Reconstruct a list from its prefixes

Question

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 code-golf, 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]

• xnor: Can the list have repeats?
• emanresu A: @xnor Yes, whoops, I'll add some testcases for that.
• doubleunary: Perhaps replace "set" with "ordered list" — a set is usually taken to mean an unordered data type that stores unique values.
• tsh: @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++.
• Wheat Wizard: It really bothers me that the empty prefix isn't included. :(

Answer 1

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.

Answer 2

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?

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

Answer 3

R, 34 bytes

\(L)diff(c(0,sort(sapply(L,sum))))

Attempt This Online!

Uses the same approach as @xnor's answer.

Answer 4

Haskell, 49 bytes

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

Try it online!

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

Slightly different approach, (削除) 62 (削除ここまで) (削除) 60 (削除ここまで) (削除) 59 (削除ここまで) (削除) 57 (削除ここまで) 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.

• Wheat Wizard: Since the input is always positive sortOn sum works in place of sortOn(0<$), and is 1 byte shorter.
• totallyhuman: @WheatWizard Inching closer and closer... but still so far. Thanks!

Answer 5

05AB1E, 5 bytes

 ̄aéO\

Try it online or verify all test cases.

Explanation:

 ̄a # 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)

Answer 6

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.

Answer 7

K (ngn/k), 11 bytes

-':.1<:\+/'

Try it online!

Another port of xnor's answer. +/' sums, .1<:\ sort, -': differences.

Answer 8

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.

Answer 9

Haskell, (削除) 78 (削除ここまで) (削除) 71 (削除ここまで) 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!

• totallyhuman: 49-byte port of xnor's Python answer.
• matteo_c: @totallyhuman it's basically another solution, I'd post it separately
• totallyhuman: Fair, just didn't feel like making another answer for a port.
• Wheat Wizard: Some improvements on this method
• xnor: Down to 59 using span

Answer 10

Charcoal, 20 bytes

WΦθ=Lκ⊕Lυ⊞υ−Σ⊟ι↨υ1Iυ

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

WΦθ=Lκ⊕Lυ

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

⊞υ−Σ⊟ι↨υ1

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

Iυ

Output the final list.

Answer 11

Uiua ^SBCS , 9 bytes

°\+⊏⍏.⍚/+

Try it!

Port of xnor's Python answer.

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

Answer 12

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)

Answer 13

APL+WIN, 19 bytes

Prompts for prefixes as nested vectors.

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

Try it online! Thanks to Dyalog Classic

Answer 14

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)
 println(s"Result: $result")
 }
 }
 def calculateDifference(lists: List[List[Int]]): List[Int] = {
 val sortedSums = lists.map(_.sum).sorted
 sortedSums.foldLeft((List[Int](), 0)) { (accAndPrev, curr) =>
 val (acc, prev) = accAndPrev
 (acc :+ (curr - prev), curr)
 }._1
 }
}

Answer 15

Perl 5 -MList::Util=sum, 46 bytes

sub{map{$c-=($t=$c+sum@$_);$t}sort{@$a-@$b}@_}

Try it online!

Answer 16

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!

• Conor O'Brien: 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!
• doubleunary: D'oh. Thanks @ConorO'Brien.
• Arnauld: 66 bytes

Answer 17

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!

Answer 18

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.