Reconstruct an array by successive insertions

Question

Given an array of letters in the range 'a' to 'o', compute how to construct the array by successively inserting the letters in alphabetical order. You will always start the insertion with a base array of all the 'o's that are in the array to be reconstructed.

Examples

Let the input array be:

['o', 'b', 'o', 'b', 'a']

The base would have been ['o', 'o'] in this case. To construct it you would do the following insertings.

• Insert 'a' at index 2 (indexing from 0). This gives ['o', 'o', 'a']
• Insert 'b at index 1. This gives ['o', 'b', 'o', 'a']
• Insert 'b' at index 3. This gives ['o', 'b', 'o', 'b', 'a']

Let the input array be:

['a', 'o', 'b', 'o', 'a', 'c', 'b']

The base case to start inserting will therefore be: ['o', 'o']

• Insert 'a' at index 0 giving ['a', 'o', 'o']
• Insert 'a' at index 3 giving ['a', 'o', 'o', 'a']
• Insert 'b' at index 2 giving ['a', 'o', 'b', 'o', 'a']
• Insert 'b' at index 5 giving ['a', 'o', 'b', 'o', 'a', 'b']
• Insert 'c' at index 5 giving ['a', 'o', 'b', 'o', 'a', 'c', 'b']

Let the input array be:

['c', 'b', 'a', 'o',  'o', 'o']

The base case to start inserting will therefore be: ['o', 'o', 'o']

• Insert 'a' at index 0
• Insert 'b' at index 0
• Insert 'c' at index 0

Let the input array be:

['c', 'b', 'a', 'o', 'b', 'o', 'b', 'a']

Output

The exact output format is of your choosing but it should be equivalent to:

For case 1:

'a', 2
'b', 1, 3

For case 2:

'a', 0, 3
'b', 2, 5
'c', 5

For case 3:

'a', 0
'b', 0
'c', 0

For case 4:

'a', 0, 3
'b', 0, 3, 5
'c', 0

BONUS (just for bragging rights) Make your code time efficient. That is can you minimise the number of operations it performs?

Answer 1

05AB1E, 11 bytes

η@O<ø{.γн}¦

Try it online!

Takes a list of numbers, 0 to 14, with o being 0, and a, b, ... being 1,2,....

We can notice that the index of an element in the correct list is the number of elements before it which are less than or equal to it.

η      # prefixes [[1], [1, 0], [1, 0, 2], [1, 0, 2, 0], [1, 0, 2, 0, 1], [1, 0, 2, 0, 1, 3], [1, 0, 2, 0, 1, 3, 2]]
@      # element in list greater than or equal to each element in the prefixes: [[1], [0, 1], [1, 1, 1], [0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 0, 1]]
O      # sum: [1, 1, 3, 2, 4, 6, 6]
<      # subtract one, to account for the element itself: [0, 0, 2, 1, 3, 5, 5]
ø      # zip with the original array: [[1, 0], [0, 0], [2, 2], [0, 1], [1, 3], [3, 5], [2, 5]]
{      # sort: [[0, 0], [0, 1], [1, 0], [1, 3], [2, 2], [2, 5], [3, 5]]
.γ     # group by:
 н     # the first element
} # [[[0, 0], [0, 1]], [[1, 0], [1, 3]], [[2, 2], [2, 5]], [[3, 5]]]
¦      # remove the first element, the zeros: [[[1, 0], [1, 3]], [[2, 2], [2, 5]], [[3, 5]]]

If we can use a looser output format, not grouping the pairs by value, we can get 8 bytes: η@O<øʒнĀ

Answer 2

Vyxal, 11 bytes

14ʁṘ(n~=T,o

Try it Online!

Takes a list of numbers, outputs 14 arrays containing the indices from n to a, descending.

9 bytes if I can take input as [14...0] instead of [0...14].

14ʁṘ(n~=T,o
             # Implicitly inputting the array
14ʁṘ(        # Loop n from 13 to 0:
     n~=T,   # Print all the indices of n in the current array
          o  # Remove n from the array

Vyxal, 10 bytes

K≥Ṡ‹Zs⁽hġḢ

Try it Online!

Port of Command Master's clever answer.

Answer 3

R, 41 bytes

\(x)Map(\(i)which(x[x<=i]==i)-1,1:max(x))

How?

f=
\(x)                        # define function with argument x;
    Map( ... ,1:max(x))     # map over integers from 1 to max(x)
                            #   for each of these, assigned to variable i:
      which(          )     #     find the indices of
            x[    ]         #       elements of the subset of x
              x<=i          #       that contains only elements <=i
                   ==i      #     that are equal to i
                       -1   #   and subtract 1 to convert to 0-based indices

Attempt This Online!

Outputs a list of vectors of the 0-based indices to insert each element that is present in the input.
Can be 2 bytes shorter by also including some empty vectors for elements that aren't present in the input. And, of course, trivially 2 bytes shorter again using R's native 1-based indexing (omit the -1).

---

R, 93 bytes

\(x){a=l=!1:15
a[]=list({})
Map(\(v){a[[v]]<<-c(a[[v]],l[v])
l[v:15]<<-l[v:15]+1},x+1)
a[-1]}

Attempt This Online!

Runs in O(n) time complexity, making a single pass through the input list with only O(1) operations at each step.

Answer 4

JavaScript (ES6), 67 bytes

Expects an array of integers in \$[1\dots15]\$. Returns an array of 14 arrays containing the insertion indices.

f=(a,n=14,b=[])=>n?[...f(a.filter((c,i)=>c-n||!b.push(i)),n-1),b]:b

Try it online!

Commented

f = (              // f is a recursive function taking:
  a,               //   a[] = input array
  n = 14,          //   n   = item counter
  b = []           //   b[] = output array for the current item
) =>               //
n ?                // if n is not equal to 0:
  [                //   update the output:
    ...f(          //     do a recursive call:
      a.filter(    //       filter a[]
      (c, i) =>    //       for each value c at index i in a[]:
        c - n ||   //         keep this value if it's not equal to n
        !b.push(i) //         otherwise, remove it and append i to b[]
      ),           //       end of filter()
      n - 1        //       decrement n
    ),             //     end of recursive call
    b              //     append b[]
  ]                //
:                  // else:
  b                //   stop

Answer 5

Python3, 202 bytes:

def f(a):
 t=[[],[]]
 for i in a:t[i!='o']+=[i]
 q=[(t[0],sorted(t[1]),[])]
 while q:
  j,k,I=q.pop(0)
  if a==j:return I
  if k:
   for u in range(len(j)+1):q+=[(j[:u]+[k[0]]+j[u:],k[1:],I+[(k[0],u)])]

Try it online!

Answer 6

K (ngn/k), ^{60 58} 56 bytes

{-1_'"o"_(+/'</1*:\-1_(1_)\|<<x*~"o"=x)@|'=|x,:@/1>:\?x}

Try it online!

Probably missing something clever but sorting the keys in the result cost 16 14 bytes.

-2 : Cheaper way to force o’s to bottom

Answer 7

Python 3, 74 bytes

f=lambda x:sorted((i,sum(j<=i for j in x[:n]))for n,i in enumerate(x)if i)

Takes input as integers:

['a', 'o', 'b', 'o', 'a', 'c', 'b'] -> [1, 0, 2, 0, 1, 3, 2]

Outputs an array in the form [(input, index)]:

Input:

['a', 'o', 'b', 'o', 'a', 'c', 'b']

Output:

[(1, 0), (1, 3), (2, 2), (2, 5), (3, 5)]

Answer 8

Charcoal, 22 bytes

⊞υoＷ⌊⁻θυ⟦ιＩ⌕Ａ⁻θ⁻θ⊞Ｏυιι

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

⊞υo

Start as if o had already been processed.

Ｗ⌊⁻θυ

While there are any unprocessed letters, take the minimum.

⟦ιＩ⌕Ａ⁻θ⁻θ⊞Ｏυιι

Output the letter and the indices that it would have been at i.e. the indices after removing the remaining unprocessed letters.

         ⊞Ｏυι   All processed letters so far (including the current one)
       ⁻θ⊞Ｏυι   All unprocessed letters so far (may include duplicates)
     ⁻θ⁻θ⊞Ｏυι   Input with unprocessed letters removed
   ⌕Ａ        ι  Get the indices of the current letter
⟦ιＩ             Output the letter with its indices

Answer 9

Pip, 22 bytes

FiR,14{PiAEg@*ig:gRMi}

a to o is mapped from 0 to 14.

Semi-port of Steffan's Vyxal answer

Attempt This Online! | 19 bytes if indices don't have to be grouped

FiR,14{PiAEg@*ig:gRMi}­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁢⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏⁠‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏‏​⁡⁠⁡‌­
FiR,14{              }  # ‎⁡For i in range 14, 0
       P   g@*i         # ‎⁢Print all indices of i in list
        iAE             # ‎⁣Prepended with i
               g:gRMi   # ‎⁤Remove all instances of i in list

Answer 10

J, 21 bytes

*@/:~#/:{1#.(}:<:{:)\

Attempt This Online!

Inspired by CommandMaster's nice insight, though the mechanics are different.

• 1#.(}:<:{:)\ For each prefix, count 1#. the number of those to the left of the last element }: that are less than or equal to <: the last element {:. This part is the same as CommandMaster's approach.
• /:{ Now order those elements according to the "grade up" /: of the original input. For example, if, when ordering the original input, the 3rd element moves to the first slot, then move the 3rd element of the result of step 1 to the first slot, and so on.
  • At this point we are done, except that we are still including the "base element" zeroes. They will all be at the beginning of our answer now, so we only need to remove from the start of our solution array the number of zeroes contained in the input.
• *@/:~ To remove them, we sort the input and take the signum, which will give as an array like 0 0 1 1 1 1, where the number of zeroes at the start matches the number of zeroes in the input.
• # Use that to filter our previous result.

Answer 11

Python, 95 bytes

f=lambda a,c='l':[0]*(c<'a')or-~(x:=a.rfind(c))and[c,x]+f(a[:x]+a[x+1:],c)or f(a,chr(ord(c)-1))

Attempt This Online!

Python, 97 bytes

f=lambda a,c='n':c>'`'and(-~(x:=a.rfind(c))and f(a[:x]+a[x+1:],c)+[c,x]or f(a,chr(ord(c)-1)))or[]

Attempt This Online!

Using a more standard output format.

Explanation forthcoming.

Answer 12

jq, 62 bytes

unique[:-1][]as$e|map(select(.<=$e or.=="o"))|[$e]+indices($e)

Try it online!

Answer 13

Scala, 420 bytes

Port of @Ajax1234's Python answer in Scala.

---

Golfed version. Try it online!

def f(a:List[Char])={val t=a.foldRight((List[Char](),List[Char]())){case(i,(x,y))=>if(i!='o')(i::x,y)else(x,i::y)}
def l(q:List[(List[Char],List[Char],List[(Char,Int)])]):Option[List[(Char,Int)]]=q match{case Nil=>None
case(j,k,i)::r=>if(a==j)Some(i.reverse)else if(k.nonEmpty)l(r++(0 to j.length).toList.flatMap(u=>List((j.take(u)++(k.head::j.drop(u)),k.tail,(k.head,u)::i))))else l(r)}
l(List((t._2,t._1.sorted,Nil)))}

Ungolfed version. Try it online!

object Main extends App {
  def f(a: List[Char]): Option[List[(Char, Int)]] = {
    val t = a.foldRight((List[Char](), List[Char]())) { case (i, (x, y)) =>
      if (i != 'o') (i :: x, y) else (x, i :: y)
    }
    
    def loop(queue: List[(List[Char], List[Char], List[(Char, Int)])]): Option[List[(Char, Int)]] =
      queue match {
        case Nil => None
        case (j, k, i) :: rest =>
          if (a == j) Some(i.reverse)
          else if (k.nonEmpty) {
            val newQueue = (0 to j.length).toList.flatMap(u => List((j.take(u) ++ (k.head :: j.drop(u)), k.tail, (k.head, u) :: i)))
            loop(rest ++ newQueue)
          } else {
            loop(rest)
          }
      }
    
    loop(List((t._2, t._1.sorted, Nil)))
  }

  println(f(List('o', 'b', 'o', 'b', 'a')))
  println(f(List('a', 'o', 'b', 'o', 'a', 'c', 'b')))
  println(f(List('c', 'b', 'a', 'o',  'o', 'o')))
}

Answer 14

Nibbles, 9 bytes (18 nibbles)

. ,@ :$ +-1 `? |@~-$@ @

Attempt This Online!

Outputs a list containing 100 lists: the first entry of each is the element to add, the next entry/entries are the 0-based positions to insert it. Obviously only lists 1-14 can contain insertion positions if these are the only values possible in the input.
8 bytes by outputting only lists of positions (without the element itself as the first entry); 6 bytes using 1-based indexing.

.                           # map over
  ,@                        # 1..100
     :$                     #   prepending each value to:
            `?              #   indices of
                @           #     the input
               |            #       (filtered to retain only
                 ~-$        #       elements less than or equal to
                    @       #       the current value)
                      @     #     that equal the current value
        +-1                 #   minus 1 (for 0-based indexing)

---

Nibbles, 10.5 bytes (21 nibbles)

. ,`/$] :$ +-1 `? |@~-$@ @

Attempt This Online!

Outputs a list as above, but only containing lists of element(s) + position(s) for values that are present in the input.
8.5 bytes or 6.5 bytes by outputting only lists of positions, and with 1-based indexing, respectively.

Answer 15

K (ngn/k), 39 bytes

{a!1_{&(*z)=x^y}[x]':(1_)\a@:<a:?x^"o"}

Try it online!

Takes input as a string, returning a dictionary mapping the sorted non-"o" characters to lists of indices.

• a:?x^"o" identify the non-"o" characters in the input
• a@:< sort them, storing the result in the a variable
• (1_)\ generate the suffixes of the sorted characters
• {...}[x]': set up an each-previous, fixing the x variable to the original input
  • &(*z)=x^y identify the indices each character should be inserted into
• a!1_ build a dictionary mapping the non-"o" characters to the indices

Answer 16

Jelly, 10 bytes

>Ðḟ¹ẹɗⱮṀ’Ė

Try it online!

A monadic link that takes a list of numbers from 0 to 14, with 0 corresponding to 'o' and 1 to 14 corresponding to 'a' to 'n'. Returns a list of lists; each list in the return value has the number in the original input it corresponds to as the first item and then a list of the 0-indexed insertion indices as the second item. If 1-indexing was allowed this would save a byte. If it were permissible to omit the labelling of the index lists with the number to which they correspond, this would save a further byte.

Explanation

     ɗⱮṀ   | For each integer y from 1 to the max integer in the argument:
>Ðḟ        | - Filter the original argument removing those values > y
   ¹       | - No-op (needed because of the way chaining works in Jelly within a dyadic chain)
    ė      | - Indices of y in this filtered list
        ’  | Decrease by 0 (because of Jelly’s 1-indexing)
         Ė | Enumerate (prefix each list with a sequential number)

Answer 17

Excel (ms365), 170 bytes

Formula in B1:

=DROP(IFNA(REDUCE(0,CHAR(ROW(97:110)),LAMBDA(o,n,IFERROR(VSTACK(o,HSTACK(n,LET(x,TOROW(A:A,3),y,FILTER(x,(x<=n)+(x="o")),FILTER(SEQUENCE(,COUNTA(y)),y=n)-1))),o))),""),1)

There is most likely some room for improvement. I deliberately use TOCOL(A:A,3) instead of an exact reference just so it's easy to moderate the input in column A:A.

Therefor, without too much hassle you can get the following: