17
\$\begingroup\$

emanresu A posted a challenge to reconstruct an ordered list of integers from its unordered set of unordered prefixes. Many users (beginning with xnor's answer) noticed that summing each unordered prefix led to a very short solution. Well, let's cruelly take that possibility away by using data that isn't integers!

A few answers from the other challenge work for this version as well; that's no problem. I'm just hoping to stimulate other answers in other languages.

(The text below is a slightly modified but mostly copied version of emanresu A's original text.)

A list of strings \$[a_1,a_2,a_3, \ldots, a_n]\$ can be uniquely represented as an unordered list of its unordered prefixes \$ [[a_1],[a_1, a_2], [a_1,a_2,a_3], \ldots, [a_1,a_2,a_3, \ldots, a_n]] \$. Both the set of prefixes and the set of elements of each individual prefix can be in any order - for example,

["lorem","ipsum","dolor"]

could be represented by any of

[["lorem"],["lorem","ipsum"],["lorem","ipsum","dolor"]] or
[["dolor","ipsum","lorem"],["ipsum","lorem"],["lorem"]] or
[["ipsum","lorem"],["lorem"],["dolor","lorem","ipsum"]]

and these are all equivalent up to order and all represent ["lorem","ipsum","dolor"].

Your challenge is, given an unordered list of the unordered prefixes of a (non-empty) list of strings, to return the ordered list represented by them. The list may contain repeated items. You may stipulate that the input includes the empty prefix if desired. This is , so shortest code in each language wins!

Testcases

Note that the order of the output does matter: for the third test case, for example, you must output ["consectetuer","sit","elit","adipiscing"], not ["adipiscing","sit","elit","consectetuer"].

[["lorem"],
 ["lorem","ipsum"],
 ["lorem","ipsum","dolor"]]
-> ["lorem","ipsum","dolor"]

[["ipsum","lorem"],
 ["lorem"],
 ["dolor","lorem","ipsum"]]
-> ["lorem","ipsum","dolor"]

[["consectetuer","sit","elit"],
 ["adipiscing","sit","elit","consectetuer"],
 ["consectetuer","sit"],
 ["consectetuer"]] 
-> ["consectetuer","sit","elit","adipiscing"]

[["consectetuer","ipsum","dolor","lorem"],
 ["lorem","ipsum"],
 ["lorem"],
 ["consectetuer","lorem","ipsum"],
 ["ipsum","ipsum","dolor","lorem","consectetuer"]]
-> ["lorem","ipsum","consectetuer","dolor","ipsum"]

[["ipsum"],
 ["nunc","ipsum","justo","in"],
 ["justo","in","ipsum","molestie","nunc"],
 ["ipsum","nunc","justo"],
 ["justo","ipsum"]]
-> ["ipsum","justo","nunc","in","molestie"]

[["elit","sit"],
 ["sit","elit","elit","sit"],
 ["sit","sit","elit"],
 ["sit"]]
-> ["sit","elit","sit","elit"]

[["pede","non","phasellus","lectus"],
 ["lectus","non"],
 ["pede","non","nunc","phasellus","lectus","sit","ipsum"],
 ["non"],
 ["phasellus","lectus","non"],
 ["pede","non","ipsum","phasellus","lectus"],
 ["ipsum","pede","non","phasellus","sit","lectus"]]
-> ["non","lectus","phasellus","pede","ipsum","sit","nunc"]

[["pellentesque","ullamcorper","semper","vestibulum"],
 ["semper","pellentesque"],
 ["pellentesque","semper","vestibulum"],
 ["pellentesque"]]
-> ["pellentesque","semper","vestibulum","ullamcorper"]
Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ May i assume each string contains only letters? \$\endgroup\$
    – tsh
    Commented Mar 4 at 5:52
  • \$\begingroup\$ @tsh I'm fine with that. \$\endgroup\$
    – Greg Martin
    Commented Mar 4 at 6:54
  • \$\begingroup\$ Does this answer your question? Reconstruct a list from its prefixes \$\endgroup\$
    – noodle person
    Commented Mar 4 at 12:18

15 Answers 15

Reset to default
5
\$\begingroup\$

Python 2, 73 68 bytes

lambda L:reduce(lambda v,l:map(l.remove,v)and v+l,sorted(L,key=len))

Try it online!

An anonymous function that accepts a List of lists and returns a list as result.

Copying my answer from the original question.

  • -5 bytes thank to @Mukundan314

How does it work?

With the input sorted by length (so [["ipsum","lorem"],["dolor","lorem","ipsum"],["lorem"]] becomes [["lorem"],["ipsum","lorem"],["dolor","lorem","ipsum"]]), for each sublist, remove the first occurrence of elements already visited from l and mark the remaining element as visited.

It works for duplicates.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ -5 bytes by doing v+l instead of v+[l[0]] \$\endgroup\$
    – Mukundan314
    Commented Mar 4 at 13:51
  • \$\begingroup\$ @Mukundan314 freaking awesome! \$\endgroup\$
    – enzo
    Commented Mar 4 at 15:22
  • \$\begingroup\$ 67 with *0+v+l \$\endgroup\$
    – no comment
    Commented Mar 7 at 16:04
4
\$\begingroup\$

Haskell, 57 bytes

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

Try it online!

Hey, I knew my slightly different approach would come in handy! Only change is needing to sort by length instead of sum, 'cause uh... well you know.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Nekomata, 8 bytes

↕ᵉtiᶻ{∕z

Attempt This Online!

The input includes the empty prefix.

↕ᵉtiᶻ{∕z
↕           Take a permutation of the input (non-deterministically)
 ᵉt         Take its tail (removing the first item)
   i        and its initial prefix (removing the last item)
    ᶻ{      Zip with:
      ∕         Set minus
       z        Check that the result is a singleton

Nekomata, 9 bytes

ᵐ∑oç∆ᵐᶠZH

Attempt This Online!

The input does not include the empty prefix.

Using @xnor's trick in emanresu A's challenge.

ᵐ∑oç∆ᵐᶠZH
ᵐ∑          Take the sum of each item of the input
            Strings are automatically converted to code points and padded with zeros
  o         Sort
   ç        Prepend zero
    ∆       Take the differences
     ᵐᶠZ    Remove zeros
        H   Convert the code points to characters
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Ha, your 9-byte found a way to bust out of Greg's guard rails :) \$\endgroup\$
    – Jonah
    Commented Mar 4 at 18:43
3
\$\begingroup\$

Jcram, 18 bytes

Ⓜ⍅Ⓛ⍎⍗¹W⍜nχ0⍒⑨1βⓏ2⏛

JavaScript (Node.js), 100 bytes

a=>a.sort((a,b)=>a.length-b.length).map(k=>a.map(a=>k.splice(k.indexOf(a),1))&&a.push(...k),a=[])&&a

Try it online! Uses a similar method to movatica's python answer.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Well done! Golfing with JCram is probably not so easy :P. \$\endgroup\$
    – Kamila Szewczyk
    Commented Apr 18 at 15:27
3
\$\begingroup\$

JavaScript (ES6), 77 bytes

f=a=>a.some(b=>(w=b[0])==b)?[w,...f(a,a.map(b=>b.splice(b.indexOf(w),1)))]:[]

Try it online!

Or:

f=a=>a.some(b=>(w=b[0])==b)?[w,...f(a.map(b=>b.filter(v=>v!=w||x++,x=0)))]:[]

Try it online!

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Jelly, 7 bytes

LÞœ^ƝṪ€

A monadic Link that accepts the prefixes as a list of lists of lists of characters (including an empty prefix) and yields a list of lists of characters.

Try it online! Or see the test-suite.

How?

LÞœ^ƝṪ€ - Link: Prefixes
 Þ      - sort by:
L       -   length
    Ɲ   - for neighbouring pairs:
  œ^    -   multiset symmetric difference
     Ṫ€ - tail of each
Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ You're allowed to take an empty list in the list of prefixes, so you can remove the Ż for 7 \$\endgroup\$
    – emanresu A
    Commented Mar 4 at 1:37
  • \$\begingroup\$ Thanks @emanresuA. \$\endgroup\$
    – Jonathan Allan
    Commented Mar 4 at 16:51
3
\$\begingroup\$

J, 25 bytes

2(~.#~2|1#.=)@;\a:,]/:#&>

Attempt This Online! Setup borrowed from Jonah's answer.

Sort by length, join adjacent prefixes, take the element that appears an odd number of times.

J, 27 bytes

2(0{~:#])/\a:>@;/:~&.>/:#&>

Attempt This Online!

Sort each prefix, sort by length. For each pair adjacent prefixes: Take the first different value from the longer prefix.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Very nice insight \$\endgroup\$
    – Jonah
    Commented Mar 5 at 14:30
2
\$\begingroup\$

05AB1E, 13 bytes

¯IévDysõ.;õK«

Try it online or verify all test cases.

Explanation:

¯              # Push an empty list; result-list starts with []
 I             # Push the input-list of lists
  é            # Sort it by length (shortest to longest)
   v           # Pop and loop over each inner list `y`:
    D          #  Duplicate the current result-list
     y         #  Push the current loop-list `y`
      s        #  Swap so the duplicated result-list is at the top
       õ.;     #  Replace every first occurrence in `y` with an empty string
          õK   #  Then remove those empty strings
            «  #  And merge the remaining single item to the result-list
               # (after the loop, the result-list is output implicitly)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Perl 5, 83 77 bytes

sub{map{$r{$z}--;%t=%r;++$t{$_}for@$_;($z)=grep$t{$_}==1,@$_}sort{@$a-@$b}@_}

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python, 76 75 74 bytes

-2 bytes thanx to Mukundan314

lambda p,l=[]:[[*map(q.remove,l),l:=q+l][-1][0]for q in sorted(p,key=len)]

Attempt This Online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 72 bytes: lambda p,l=[]:[[q,*map(q.remove,l),l:=l+q][0]for q in sorted(p,key=len)]; I don't remember if this is an acceptable output format though; fixing it would requires 3 bytes tying it with the current 75 bytes \$\endgroup\$
    – Mukundan314
    Commented Mar 4 at 7:36
  • 1
    \$\begingroup\$ 74 bytes: lambda p,l=[]:[[*map(q.remove,l),l:=q+l][-1][0]for q in sorted(p,key=len)]; this one doesn't have any caveats \$\endgroup\$
    – Mukundan314
    Commented Mar 4 at 7:40
2
\$\begingroup\$

J, 40 bytes

({.,1$:^:(0<#)@}.](1}.i.|.[)&.>{.)@/:#&>

Attempt This Online!

This approach is more or less a port of Arnauld's recursive approach.

J, 45 bytes

[:,@(2~.&>@-.~&>/\a:,]/:#&>)(a:-.~&,<\/.~)&.>

Try it online!

Kinda long, but possibly interesting approach to dealing with repeats:

  • (a:-.~&,<\/.~)&.> A pre-processing step that goes through each set and replaces repeated items by actually repeating them. This allows our main code to assume uniqueness.
    • Eg, conceptually, if we have a list like [a, b, a], it becomes [a, b, [a, a]]. We use nested J boxes for this.
  • The remaining steps may now assume no repeats.
  • a:,]/:#&> Sort the sets by their length, and add an empty set to start
  • 2...-.~&>/\ Do consecutive set differences to recover the original list
  • ~.&>@ Uniquify each to undo the effect of the first pre-processing step
  • ,@ Flatten the result
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python, 69 bytes

lambda p:[s for s,in sorted(p,key=len)if[r.remove(s)for r in p if r]]

Attempt This Online!

Python, 73 bytes

lambda p:p and(m:=min(p,key=len))+f([q for q in p if q!=m!=q.remove(*m)])

Attempt This Online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 23 bytes

Ｗ⌊Φθ⁼Ｌκ⊕Ｌυ⊞υ⊟Φ��›№ικ№υκυ

Try it online! Link is to verbose version of code. Accepts but does not require the empty prefix. Explanation:

Ｗ⌊Φθ⁼Ｌκ⊕Ｌυ

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

⊞υ⊟Φι›№ικ№υκ

... find any terms that appear more times in that prefix than in the terms collected so far and push one to the (predefined empty) list of terms so far.

υ

Output the final list.

Differences between this solution and the numeric solution:

  • Slightly different way of retrieving the next prefix, since I need to refer to it twice
  • Different method of finding the next term, of course
  • Resulting list is of strings so only takes 1 byte to output
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python, 101 bytes

lambda l,p=0:[PyObj_FromPtr(-p+(p:=x))for x in sorted(sum(map(id,b))for b in l)]
from _ctypes import*

Attempt This Online!

-6 bytes thanks to Mukundan314.

Direct adaptation of xnor's answer for integers, converting the strings to and from integers using id and its inverse _ctypes.PyObj_FromPtr.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ -6 bytes by replacing id(a)for a in b with map(id,b) \$\endgroup\$
    – Mukundan314
    Commented Mar 4 at 14:01
0
\$\begingroup\$

APL+WIN, 58 bytes

Prompts for a nested vector of nested vectors of strings.

 i←↑r←m[⍋∊⍴¨m←⎕]⋄⍎∊(⍴r)⍴⊂'r←1↓1↓¨(¯1+r⍳¨r[1])⌽¨r⋄i←i,↑r⋄'⋄i

Try it online! Thanks to Dyalog Classic

Improve this answer
\$\endgroup\$

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