19
\$\begingroup\$

I recently had a problem to solve at work where I had two lists: a master list, and a smaller list that contains a subset of the items in the master list potentially in a different order. I needed to reorder the master list in such a way that the items in the subset would appear in the same order without changing the order of the items not found in the list and keeping items in the same location whenever possible. Okay, that probably sounds confusing, so I'll break it down:

  • The master list defines the default order of items.
  • The subset list defines relative order of certain items.
  • Where the master list has two elements out of order according to the subset list, the item that is earlier in the master list should be moved to the earliest index where it is in the correct location relative to other items within the subset list. (i.e. immediately after the later item)

Your task is to implement this reordering algorithm.

Example Test Cases

Master: [1, 2, 3]
Subset: []
Result: [1, 2, 3]

Master: [9001, 42, 69, 1337, 420]
Subset: [69]
Result: [9001, 42, 69, 1337, 420]

Master: [9001, 42, 69, 1337, 420, 99, 255]
Subset: [69, 9001, 1337]
Result: [42, 69, 9001, 1337, 420, 99, 255]

Master: [1, 2, 3, 4, 5]
Subset: [2, 5]
Result: [1, 2, 3, 4, 5]

Master: [apple, banana, carrot, duck, elephant]
Subset: [duck, apple]
Result: [banana, carrot, duck, apple, elephant]

Master: [Alice, Betty, Carol, Debbie, Elaine, Felicia, Georgia, Helen, Ilene, Julia]
Subset: [Betty, Felicia, Carol, Julia]
Result: [Alice, Betty, Debbie, Elaine, Felicia, Carol, Georgia, Helen, Ilene, Julia]

Master: [snake, lizard, frog, werewolf, vulture, dog, human]
Subset: [snake, werewolf, lizard, human, dog]
Result: [snake, frog, werewolf, lizard, vulture, human, dog]

Master: [Pete, Rob, Jeff, Stan, Chris, Doug, Reggie, Paul, Alex]
Subset: [Jeff, Stan, Pete, Paul]
Result: [Rob, Jeff, Stan, Pete, Chris, Doug, Reggie, Paul, Alex]

Master: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Subset: [8, 1, 2, 12, 11, 10]
Result: [3, 4, 5, 6, 7, 8, 1, 2, 9, 12, 11, 10]

Master: [lol, rofl, lmao, roflmao, lqtm, smh, jk, wat]
Subset: [wat, lmao, rofl]
Result: [lol, roflmao, lqtm, smh, jk, wat, lmao, rofl]

Rules

  • Standard loopholes, yadda yadda, convenient I/O, blah blah.
  • Even though the examples use numbers and strings, you only need to support one element type, whether that's integers, strings, or anything else with well-defined equality semantics, including heterogeneous lists if that's convenient in your language.
  • You may assume both the master list and the subset list contain no duplicates
  • You may assume that all items found in the subset list are found in the master list
  • Either list may be empty
  • You must, at minimum, support arrays up to 100 elements long.
  • Reordering may be implemented in-place or through the creation of a new list/array.

Happy Golfing!

\$\endgroup\$
  • 1
    \$\begingroup\$ A nice, beefy problem. \$\endgroup\$ – Jonah Apr 5 at 0:27
  • \$\begingroup\$ Is 8 1 3 4 5 6 7 2 9 12 11 10 a valid solution to the second-to-last one? \$\endgroup\$ – Ven Apr 5 at 14:18
  • \$\begingroup\$ @Ven No. Even though that fits within the constraints of keeping the subset items in the same relative order, I wanted to make sure there was only one correct answer, so the earlier out-of-order item should be moved to be after the later out-of-order item. \$\endgroup\$ – Beefster Apr 5 at 16:47
  • \$\begingroup\$ Why does it matter that there are more than one correct answer? Please add the constraint to the rules of the challenge please. \$\endgroup\$ – Ven Apr 6 at 14:38

10 Answers 10

4
\$\begingroup\$

Retina 0.8.2, 51 bytes

+`(\b(\w+),(\w+)\b.*¶.*\b)\3,(.*\b\2\b)
$1$4,$3
1A`

Try it online! Takes input as a comma-separated list of subwords on the first line and a comma-separated master list of words on the second line. Explanation:

(\b(\w+),(\w+)\b.*¶.*\b)\3,(.*\b\2\b)

Find two adjacent subwords where the second word precedes the first on the master list.

$1$4,$3

Move the second word to appear after the first word in the master list.

+`

Repeat until no words appear out of order.

1A`

Delete the subwords.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6),  96 89 74  71 bytes

This started as a bulky mess and was eventually shrunk to a rather concise and elegant form. I'd like to thank the .splice() method for its fruitful collaboration on that one. ;)

Takes input as (master)(subset). Outputs by updating the master list.

m=>s=>s.map(p=x=>m.splice(p,0,...m.splice(i=m.indexOf(x),p>i||!(p=i))))

Try it online!

How?

We are using two nested .splice() methods on the same array to conditionally move an element from position \$i\$ to position \$p\$:

m.splice(p, 0, ...m.splice(i, condition))

If the condition is truthy (coerced to \$1\$):

  • the inner .splice() removes and returns the element at position \$i\$ as a singleton array \$[element]\$
  • thanks to the spread syntax, this element is expanded as a 3rd argument for the outer .splice(), which causes it to be inserted back at position \$p\$

If the condition is falsy (coerced to \$0\$):

  • the inner .splice() removes nothing and returns an empty array
  • as a result, the outer .splice() receives undefined as its 3rd argument and nothing is inserted either

Commented

m => s =>                 // m[] = master list, s[] = subset list
  s.map(                  //
    p =                   // p = position in the master list of the last element from
                          //     the subset list (initialized to a non-numeric value)
    x =>                  // for each element x in the subset list:
    m.splice(             //   insert in the master list:
      p,                  //     at position p
      0,                  //     without removing any element
      ...m.splice(        //     remove from the master list and flatten:
        i = m.indexOf(x), //       i = position of x in the master list
        p > i             //       if p is greater than i, remove x from its current
                          //       position and insert it at position p
        || !(p = i)       //       otherwise, set p to i and don't remove/insert anything
      )                   //     end of inner splice()
    )                     //   end of outer splice()
  )                       // end of map()
\$\endgroup\$
  • 1
    \$\begingroup\$ "I'd like to thank the .splice() method for ..." Cue PPCG Oscar's Music... :) \$\endgroup\$ – Chas Brown Apr 5 at 3:21
  • \$\begingroup\$ More correctly, the outer splice call receives 3 or 2 arguments respectively, which makes it do the right thing. \$\endgroup\$ – Neil Apr 6 at 17:00
2
\$\begingroup\$

Haskell, 79 bytes

(m:n)#u@(s:t)|m==s=m:n#t|all(/=m)u=m:n#u|(x,_:z)<-span(/=s)n=(x++s:m:z)#u
m#_=m

Try it online!

(m:n)#u@(s:t)                 -- m: head of master list
                              -- n: tail of master list
                              -- s: head of subset
                              -- t: tail of subset
                              -- u: whole subset
   |m==s                      -- if m==s
        =m:n#t                -- return 'm' and append a recursive call with 'n' and 't'
   |all(/=m)u                 -- if 'm' is not in 'u'
             =m:n#u           -- return 'm' and append a recursive call with 'n' and 'u'
   |                          -- else (note: 's' is element of 'n')
    (x,_:z)<-span(/=s)n       -- split 'n' into a list 'x' before element 's' and
                              -- a list 'z' after element 's' and
       = (x++s:m:z)#u         -- make a recursive call with
                              -- x++s:m:z as the new master list (i.e. 'm' inserted into 'n' after 's') 
                              -- and 'u'
m # _ = m                     -- if either list is emtpy, return the master list
\$\endgroup\$
2
\$\begingroup\$

Ruby, 73 68 bytes

->a,b{0while b.zip(a&b).find{|m,n|m!=n&&a=a[0..a.index(m)]-[n]|a};a}

Try it online!

How?

  • The intersection between a and b contains all elements of b, but in the same order as we would find them in a
  • So, if we iterate on b and on the intersection in parallel, as soon as we find a difference, we can relocate a single element.
  • Relocation is done by cutting a on the position of the element we found in b, then removing the element we found in the intersection, and then adding the remainder of a.
  • Repeat from the beginning, until all elements of b are in the right order in a
\$\endgroup\$
  • \$\begingroup\$ what is the 0 doing in 0while? \$\endgroup\$ – Jonah Apr 5 at 15:24
  • \$\begingroup\$ It's just a NOP. \$\endgroup\$ – G B Apr 5 at 16:25
  • \$\begingroup\$ why is it needed? \$\endgroup\$ – Jonah Apr 5 at 17:07
  • 1
    \$\begingroup\$ Because the comparison and manipulation is done in a single block, to avoid declaring a variable before starting the loop. It means: "do nothing while the operation returns true.", the code is shorter than "do operation while result is true" \$\endgroup\$ – G B Apr 8 at 5:50
1
\$\begingroup\$

Python 2, 124 109 106 99 96 bytes

def f(a,b,i=0):
 while b[i+1:]:x,y=map(a.index,b)[i:i+2];i+=1;x>y>a.insert(x,a.pop(y))
 return a

Try it online!

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

Perl 6, 40 bytes

{*.permutations.first(*.grep(.any)eq$_)}

Try it online!

Anonymous code block that takes the input curried (like f(subList)(masterList), and finds the first lexographical permutation of the indexes of the master list where the elements from the sub list are in the correct order.

Intuitively, the first satisfying permutation will leave the correctly ordered elements in the original order, while moving the incorrectly placed ones the minimum needed distance forward in order to have them in the correct order, which places them directly after the previous element in the subset.

Explanation:

{*                                     } # Anonymous code block that returns a lambda
  .permutations                          # In all permutations of the master list
               .first(                )  # Find the first permutation
                     (*.grep(.any)       # Where the order of the subset
                                  eq$_   # Is the same as the given order


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

Jelly, 9 bytes

Œ!iⱮṢƑ¥ƇḢ

Try it online! or Test suite

Inefficient, particularly with large master lists. Generates all possible permutations, filters out those where the subset is in the wrong order, and then returns the first.

Explanation

Œ!        | Generate all permutations of the master list
      ¥Ƈ  | Filter including only those where...
  iⱮ      |   the index of each sublist item in this permutation...
     Ƒ    |   is...
    Ṣ     |   in order. 
        Ḣ | Finally take the first item
\$\endgroup\$
  • \$\begingroup\$ This doesn't seem like it would conform to the rule "Where the master list has two elements out of order according to the subset list, the item that is earlier in the master list should be moved to the earliest index where it is in the correct location relative to other items within the subset list. (i.e. immediately after the later item)" \$\endgroup\$ – Beefster Apr 5 at 20:49
  • \$\begingroup\$ @Beefster it works on the ones I’ve tried so far. I think the ordering of the permutations is such that this is the correct result. Happy to be proved wrong if there’s a counterexample. \$\endgroup\$ – Nick Kennedy Apr 5 at 20:50
  • \$\begingroup\$ @Beefster I’ve now tried all of your examples except the female names and the 1..12 and the ordering of the result is correct. \$\endgroup\$ – Nick Kennedy Apr 5 at 21:12
  • 2
    \$\begingroup\$ @Beefster My answer has a partial explanation for why this works \$\endgroup\$ – Jo King Apr 6 at 2:33
1
\$\begingroup\$

J, 49 bytes

[:(<@({:+i.@>:@-/)@i.~C.])^:(>/@i.~)&.>/]|.@;2<\[

Try it online!

explanation

We take the subset as the left arg and the full input as the right.

We'll work through the code with a specific example for clarity:

5 2 4 f 1 2 3 4 5

Take the boxed infixes of size two of the subset:

2 <\ [

producing:

┌───┬───┐
│5 2│2 4│
└───┴───┘

append them to the original input, and reverse the whole thing:

] |.@;

We get:

┌───┬───┬─────────┐
│2 4│5 2│1 2 3 4 5│
└───┴───┴─────────┘

Solving the problem becomes a right to left reduction on the above. We need only find the right verb to insert / between the items.

Each iteration of the reduction will update the rightmost box (the full input, which we're transforming) so it conforms to the ordering constraint represented by the pair to its left. When the reduction is finished, the input will respect the complete subset ordering.

If the ordering of the pair is the same as ordering in the input, the following will evaluate to 0 and we'll do nothing:

^:(>/@i.~)

Otherwise it will evaluate to 1 and we'll apply the verb to the left of ^:

   {: + i.@>:@-/)@i.~ C. ]

which moves the left item to the right of the right item. This movement is simply a cyclic permutation of all the items between (and including) the two elements in question.

J has primitive to apply such a cyclic permutation:

<cyclic permutation definition> C. ]

and the remainder of the verb does nothing but pick out the indexes we need to cycle:

{: + i.@>:@-/)@i.~

which seems longer than it should be, but I wasn't able to golf that phrase further.

Finally we rebox the result <@ and we're done.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 24 bytes

i@€MƤFṬœṗƲḊ;JḟF}W€ʋ@¥ṢFị

Try it online! or Test suite

Explanation

A dyadic link that takes the subset as the left and master list as right arguments. The below example uses 9001, 42, 69, 1337, 420, 99, 255 as master and 69, 9001, 1337 as subset.

i@€                      | Find the index of each subset item in the master list [3, 1, 4]
         Ʋ               | Previous 4 links as a monad
   MƤ                    | Find the index of the maximum for each prefix of this list [1, 1, 3]
     F                   | Flatten (because the previous result are actually each length one lists)
      Ṭ                  | Convert to a boolean list [1,0,1]
       œṗ                | Partition the [3, 1, 4] list before each 1 [[], [3, 1], [4]]
          Ḋ              | Remove the empty first list [[3, 1], [4]]
                    ¥    | Previous two links as a dyad
                  ʋ@     | Previous 4 links as a dyad with reversed arguments
            J            | Sequence along the master list [1, 2, 3, 4, 5, 6, 7]
             ḟF}         | Filter out items in the flattened [3, 1, 4] list
                W€       | Wrap each item as a list [[2], [5], [6], [7]]
           ;             | Concatenate rhis to the [[3, 1], [4]] list
                     Ṣ   | Sort (effectively by first item in each list) [[2], [3, 1], [4], [5], [6], [7]]
                      F  | Flatten
                       ị | Look up in original master list (and implicitly output)
\$\endgroup\$
0
\$\begingroup\$

C# (Visual C# Interactive Compiler), 118 bytes

a=>b=>{for(int j;b.Any();)foreach(var e in b.Intersect(a.Take(j=a.IndexOf(b.Dequeue())))){a.Remove(e);a.Insert(j,e);}}

Try it online!

Leveraging some classes in the System.Collections.Generic namespace. The master is a List<T> and the subset is a Queue<T>.

// a: master
// b: subset
a=>b=>{
  // continue until b is empty
  for(int j;b.Any();)
    // iterate over values that are out of order in a
    // per the head of b using loop variable e
    foreach(var e in
      // the out of order values are determined by
      // intersecting remaining values in b with
      b.Intersect(
        // values in a occurring before the current head of b
        // save the position in a to variable j and remove the head of b
        a.Take(j=a.IndexOf(b.Dequeue()))
      )
    ){
      // push back the out of order element in a
      a.Remove(e);
      a.Insert(j,e);
    }
}
\$\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.