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.


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']


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?

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

17 Answers 17


05AB1E, 11 bytes


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


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

             # 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


Try it Online!

Port of Command Master's clever answer.


R, 41 bytes



\(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


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.

  • \$\begingroup\$ This looks clever. Can you explain what it is doing for those who don't read R. \$\endgroup\$
    – Simd
    Sep 26 at 9:52
  • 1
    \$\begingroup\$ @Simd - Done. Let me know if anything isn't clear. It's easy to sometimes forget that not everyone speaks your own language... \$\endgroup\$ Sep 26 at 10:16
  • \$\begingroup\$ 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) \$\endgroup\$
    – Simd
    Sep 26 at 10:22
  • \$\begingroup\$ 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). \$\endgroup\$ Sep 26 at 10:26
  • \$\begingroup\$ It would be very cool if O(n) were possible. \$\endgroup\$
    – Simd
    Sep 26 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.


Try it online!


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):
 for i in a:t[i!='o']+=[i]
 while q:
  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!

  • 1
    \$\begingroup\$ Could you add some explanation? \$\endgroup\$
    – Simd
    Sep 24 at 12:05

K (ngn/k), 60 58 56 bytes


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


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


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

Charcoal, 22 bytes


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


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.

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

Pip, 22 bytes


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{              }  # ‎⁡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

J, 21 bytes


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.

  • \$\begingroup\$ ato.pxeger.com/… looks wrong \$\endgroup\$
    – Simd
    Sep 25 at 4:51
  • \$\begingroup\$ I think the problem is just the trailing zero in the output and that it is in the wrong order \$\endgroup\$
    – Simd
    Sep 25 at 7:20
  • \$\begingroup\$ @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. \$\endgroup\$ Sep 25 at 14:12
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ Sep 25 at 14:18
  • 1
    \$\begingroup\$ @JonathanAllan Because of a typo :) Also, we made the exact same modification to the code at the exact same time, very funny. \$\endgroup\$ Sep 25 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
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)}

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


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.


     ɗⱮṀ   | 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

enter image description here

Formula in B1:


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:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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