# Reconstruct an array by successive insertions

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?

• Can I take numbers instead of letters? Commented Sep 24, 2023 at 12:36
• Would 'b' 2, 1 be valid for the first case, or does it have to be in increasing order? Commented Sep 24, 2023 at 12:37
• If c appears in the input, are a and b guaranteed to appear at least once as well? Commented Sep 24, 2023 at 12:55
• @Arnauld yes they are
– Simd
Commented Sep 24, 2023 at 13:07
• @CommandMaster has to be in increasing order
– Simd
Commented Sep 24, 2023 at 13:09

# 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<øʒнĀ

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

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

• This looks clever. Can you explain what it is doing for those who don't read R.
– Simd
Commented Sep 26, 2023 at 9:52
• @Simd - Done. Let me know if anything isn't clear. It's easy to sometimes forget that not everyone speaks your own language... Commented Sep 26, 2023 at 10:16
• Thank you. Do you think this can be done in linear time? (Formally it already is linear time but I mean assuming that the range of values is larger than 14)
– Simd
Commented Sep 26, 2023 at 10:22
• I think it's currently polynomial time, O(n^2). For each element of x it needs to check over all the elements of x. It would need a change of approach to run in O(n). Commented Sep 26, 2023 at 10:26
• It would be very cool if O(n) were possible.
– Simd
Commented Sep 26, 2023 at 12:34

# 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


# 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!

• Could you add some explanation?
– Simd
Commented Sep 24, 2023 at 12:05

# Pip, 22 bytes

FiR,14{PiAEg@*ig:gRMi}


a to o is mapped from 0 to 14.

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

• Quick 1-byte golf: gRM:i. If you're okay with a slightly odd output format, this is 19 bytes. Either way, you should include the -p flag in the language header, since the output wouldn't be readable without it. Commented Feb 25 at 18:17

# K (ngn/k), 6058 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

# 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)]


# 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


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

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

• ato.pxeger.com/… looks wrong
– Simd
Commented Sep 25, 2023 at 4:51
• I think the problem is just the trailing zero in the output and that it is in the wrong order
– Simd
Commented Sep 25, 2023 at 7:20
• @Simd I think it's an acceptable alternative format, since it still contains all the necessary information -- it's easy to adapt to remove those differences, but it adds a few bytes. Commented Sep 25, 2023 at 14:12
• Not sure why c='l' rather than c='n'. Otherwise, here is a two-byte fix (may still be golfable of course). EDIT looks like you got there first :) Commented Sep 25, 2023 at 14:18
• @JonathanAllan Because of a typo :) Also, we made the exact same modification to the code at the exact same time, very funny. Commented Sep 25, 2023 at 14:18

# jq, 62 bytes

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


Try it online!

# 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
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')))
}


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

# 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

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


# 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: