Minimally prepend numbers to get a symmetric Young diagram

Question

Background

A Young diagram is a diagram that represents a nonincreasing sequence of positive integers using left-justified rows of squares. As an example, 5, 4, 1 is drawn as

OOOOO
OOOO
O

A Young diagram is said to be symmetric if it is identical to its transpose (reflection along the NW-SE diagonal). The above diagram of 5, 4, 1 is not symmetric, since its transpose represents 3, 2, 2, 2, 1 instead:

5 OOOOO    3 OOO
4 OOOO     2 OO
1 O     => 2 OO
           2 OO
           1 O

A symmetric example is that of 4, 2, 1, 1:

OOOO
OO
O
O

Challenge

Given a nonincreasing sequence of positive integers, add as few numbers as possible to the front of it so that its Young diagram becomes symmetric. If the input is already symmetric, your code is expected to output it as-is. You may take input and give output in reverse order (numbers in increasing order; e.g. [1, 1, 2, 2] -> [1, 1, 2, 2, 4, 6]).

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

[1] -> [1]
[2] -> [2, 2]
[3] -> [3, 3, 3]
[1, 1] -> [3, 1, 1]
[2, 1] -> [2, 1]
[3, 1] -> [4, 3, 3, 1]
[2, 2, 1] -> [5, 4, 2, 2, 1]
[3, 2, 1] -> [3, 2, 1]
[4, 2, 2] -> [4, 4, 2, 2]
[4, 2, 1] -> [6, 5, 4, 4, 2, 1]
[4, 4, 3] -> [4, 4, 4, 3]
[5, 4, 1] -> [6, 5, 5, 5, 4, 1]
[4, 2, 1, 1] -> [4, 2, 1, 1]
[2, 2, 1, 1] -> [6, 4, 2, 2, 1, 1]

Answer 1

05AB1E, 25 24 21 19 bytes

g+àLZиæé€ì.ΔDÅ10ζOQ

Brute-force approach. Times out for most inputs.

-2 bytes thanks to @ovs.

Try it online or verify some of the shorter test cases.

Previous answer: 05AB1E (legacy), 25 24 bytes

Å1ζO©[DN(.£I®gN-£Q#>}N£ì

Port of @gsitcia's Python answer, so make sure to upvote him/her as well!

-1 byte by switching to the legacy version of 05AB1E. The original program was Å10ζO©[D¾.$I®g¾-£Q#>¼}¾£ì, with the following differences:

1. -1 byte: 0ζO (zip with 0 filler; sum) is replaced with ζO (zip with default space filler; sum), since the legacy version will ignore these spaces when summing;
2. -1 byte: The ¾ are replaced with N and the ¼ has been removed, because N can be accessed outside of loops in the legacy version, which will reset to 0 in the new version;
3. +1 byte: .$ wasn't a builtin yet in the legacy version, so we'll have to use (.£ instead (.$ is a[b:]; .£ is a[-b:], and ( negates the integer first).

Try it online or verify all test cases.

Explanation:

g              # Get the length of the (implicit) input-list
 +             # Add it to each value in the (implicit) input-list
  à            # Pop and leave the maximum
   L           # Create a list in the range [1,max(input)+length(input)]
    Zи         # Repeat each integer this max amount of times
      æ        # Get the powerset of this entire list
       é       # Sort it by length
        ۓ     # Prepend each in front of the (implicit) input-list
.Δ             # Find the first list which is truthy for:
  D            #  Duplicate the current list
   Å1          #  Map each integer in the list to a list of that many 1s
      ζ        #  Zip/transpose this list of lists,
     0         #  with 0 as filler to make it a rectangle
       O       #  Sum each inner row
               #  (we now have the reflection of the list)
        Q      #  Check if the duplicated current list is equal to its reflection
               # (after we've found a result, output it implicitly)

Å1             # Map each integer in the (implicit) input-list to a list of that many 1s
  ζ            # Zip/transpose this list of lists,
               # with a space as default filler to make it a rectangle
   O           # Sum each inner row, ignoring the spaces
               # (we now have the reflection of the input-list)
    ©          # Store this list in variable `®` (without popping)
[              # Start an infinite loop:
 D             #  Duplicate the current list
  N(.£         #  Remove the last 0-based loop-index amount of values from this list
      I        #  Push the input-list
       ®g      #  Push the length of list `®`
         N-    #  Decrease it by the 0-based loop-index
           £   #  Only leave that many leading items from the input-list
            Q  #  If both lists (®[cv:] and input[:len(®)-cv]) are now equal:
             # #   Stop the infinite loop
 >             #  If not, increase all values in the list by 1
}              # After the infinite loop: 
 N             # Push the (0-based) loop-index we ended at
  £            # Only leave the index amount of values from the list
   ì           # And prepend it at the front of the (implicit) input-list
               # (after which this is output implicitly as result)

Answer 2

Jelly, 21 bytes

+L}Rṗ⁸;€b1ZƑ$Ƈ
0ç1#Ḣç

Try it online!

A full program taking a list of integers as its argument and printing the shortest list satisfying the requirements. The TIO link includes all test cases.

Explanation

Helper link

Left argument is the number of additional digits to prepend, right argument is the original list

+               | Add:
 L}             | - Length of original list
   R            | Range 1..this
    ṗ⁸          | Cartesian power with number of new digits
      ;€        | Prepend each to the original list
        b1ZƑ$Ƈ  | Convert to unary and test whether unchanged by transposition

Main link

0ç1#           | Starting with zero, identify how many additional digits are needed to make the list meet the requirements
    Ḣ          | Head
     ç         | Then call the helper link again one last time

---

An alternative Jelly answer uses less brute force, 21 bytes

b1S+⁹ḣɗⱮṀŻ$;€⁸b1ZƑ$ƇḢ

Try it online!

Answer 3

Ruby, 92 ... 85 82 bytes

f=->l,*r{l==(0...l[0]).map{|x|l.count{|y|y>x}}?l:f[*r+(1..l.sum).map{|q|[q+1]+l}]}

Try it online!

Non-recursive version, 85 bytes

->l,*r{l,*r=r+(0..l.sum).map{|q|[q+1]+l}until(0...l[0]).map{|x|l.count{|y|y>x}}==l;l}

Try it online!

How?

This explanation refers to the non-recursive version, which is functionally identical to the recursive one.

Sheer brute force:

->l,*r{

We must check all sequences, starting with the original: r is the list of sequence we haven't checked yet.

l,*r=r+(0..l.sum).map{|q|[q+1]+l}

This will be executed after each check: since the sequence is not symmetric (or not a Young diagram), we create a new list of sequence which can extend this one by adding one number at the beginning. The maximum possible value is the sum of the sequence + 1 (empirical evidence). The minimum is set to 0, this will generate a lot of non-Young diagrams, but those will be discarded by the check.

until(0...l[0]).map{|x|l.count{|y|y>x}}==l;

We've found the sequence if for any number x between 1 and the maximum value in l, the xth element of l is the number of elements of l that are greater or equal to x. If the first element of l is not the maximum, then the size of the sequence won't match (this will exclude all non-Young diagrams).

l}

Finally, return the sequence we have found.

Answer 4

05AB1E, 22 bytes

∞εLyã}€`ʒIÅ¿}.ΔDāδ@øOQ

Try it online! or Try all cases!

∞ε   }          # for y in [1, 2, ...]
  L             #   take the range [1, ..., y]
   yã           #   all y-tuples of these numbers
      €`        # flatten the result by one level
        ʒ   }   # filter; keep only those lists
         IÅ¿    #   that end with the input

.Δ              # find the first list y that
  Dāδ@øOQ       #   (is a symmetric Young diagram)
   ā            #   push range [1, ..., len(y)]
    δ@          #   (<=) - table
      øO        #   sum the columns, the result is a list giving the count of numbers >= n for each n
  D     Q       #   is this equal to y?

Answer 5

JavaScript, 110 bytes

f=(a,l,g=a=>{for(i=j=k=l;j||=k=--i&&l;b[l-i]||=!j*k)k-=a[--j]<i})=>g(c=b=[...a],b=[g(a,c)])|b==c+''?c:f(a,-~l)

f=(a,l,g=a=>{for(i=j=k=l;j||=k=--i&&l;b[l-i]||=!j*k)k-=a[--j]<i})=>g(c=b=[...a],b=[g(a,c)])|b==c+''?c:f(a,-~l)

console.log(JSON.stringify(f([1])));
console.log(JSON.stringify(f([2])));
console.log(JSON.stringify(f([3])));
console.log(JSON.stringify(f([1, 1])));
console.log(JSON.stringify(f([1, 2])));
console.log(JSON.stringify(f([1, 3])));
console.log(JSON.stringify(f([1, 2, 2])));
console.log(JSON.stringify(f([1, 2, 3])));
console.log(JSON.stringify(f([2, 2, 4])));
console.log(JSON.stringify(f([1, 2, 4])));
console.log(JSON.stringify(f([3, 4, 4])));
console.log(JSON.stringify(f([1, 4, 5])));
console.log(JSON.stringify(f([1, 1, 2, 4])));
console.log(JSON.stringify(f([1, 1, 2, 2])));

First, function g try to calculate transpose of some given input.

g=a=>{for(i=j=k=l;j||=k=--i&&l;b[l-i]||=!j*k)k-=a[--j]<i}

Although there is only a variable a before the fat arrow, it actually takes 3 parameters:

1. The length l
2. The input array a
3. The output array b

It returns the transpose via modify variable b in-place.

It assumes a have l elements (as if there are some ls padded at the end of a). And try to calculate a's transpose. When b is given an non-empty array, g keeps values already in b as is, and only calculate the remaining values.

So, we can use this function to:

1. g(a,c=b=[...a]) will try to append some values to input, so it at least l elements in it, and the largest value is l. And c is the calculate result.
2. After that, g(c,b=[])will transpose c.
3. Finally, we test b==c+'': It will be true only if c is identical to its transpose.
4. We return c if it is identical to its transpose, or reject c and try a larger l.

Answer 6

BQN,31 25 bytes^SBCS

∧∘⊒⌾/{⊑𝔽⊸≡¨⊸/≠⊸+⊸∾⟜𝕩¨↑𝔽𝕩}

Try it here.

How it works:

∧∘⊒⌾/ is a helper function for the transpose. It works by taking the Indices /, then the Occurrence Count ⊒, sorts ∧ the result, then finally because of the modifier Under ⌾ — which conceptually means apply the function on the right, then the one on the left, then undo the one on the right—it takes the inverse of Indices.

To visualize an example:

    / 5‿4‿1
0‿0‿0‿0‿0‿1‿1‿1‿1‿2

    ⊒ 0‿0‿0‿0‿0‿1‿1‿1‿1‿2
0‿1‿2‿3‿4‿0‿1‿2‿3‿0

    ∧ 0‿1‿2‿3‿4‿0‿1‿2‿3‿0
0‿0‿0‿1‿1‿2‿2‿3‿3‿4

    /⁼0‿0‿0‿1‿1‿2‿2‿3‿3‿4
3‿2‿2‿2‿1

And then the main part:

{⊑𝔽⊸≡¨⊸/≠⊸+⊸∾⟜𝕩¨↑𝔽𝕩} # a 1-modifier where Transpose is 𝔽 and input is 𝕩
                ↑𝔽𝕩  # list the prefixes of transposed input
               ¨     # for each prefix in the list:
        ≠⊸+          #   add its length to itself
           ⊸∾⟜𝕩      #   and join to the input
      ⊸/             # filter by:
  𝔽⊸≡¨               #   whether each element is equivalent to its transpose
 ⊑                   # select first result

Answer 7

Python 3.8 (pre-release), 142 bytes

lambda L:(Z:=[len([0for i in L if i>j])for j in range(L[0])])*0+min(K[:n]+L for n in range(1+len(Z))if(K:=[i+n for i in Z])[n:]==L[:len(Z)-n])

Try it online!

Ungolfed:

def f(L):
  Z = [0]*L[0]
  for i in L:
    Z[:i] = [j+1 for j in Z[:i]]
  # Z is now transpose of L
  for n in range(1+len(Z)):
    K = [i+n for i in Z]
    # K is the start of the transpose of (L with n elements prepended)
    if K[n:]==L[:len(Z)-n]: # the overlapping parts must be equal
      return K[:n]+L

Answer 8

Brachylog, 21 bytes

~a₁.R⁰l⟦₅{{<.∧R⁰∋}ᶜ}ᵐ

Try it online!

My first Brachylog program, so it can probably be improved a lot.

Explanation

~a₁.R⁰l⟦₅{{<.∧R⁰∋}ᶜ}ᵐ
                       The input
~a₁                    is a suffix of
   .                   the output,
    R⁰                 aka R⁰.
      l                The output's length,
       ⟦₅              range from 0 to that-1,
         {         }ᵐ  map:
          {      }ᶜ      count all possible outputs of this predicate:
                           The number
           <               is less than
            .              the output
             ∧             and
              R⁰           R⁰
                ∋          contains
                           the output.
                       this has to be equal to the output.

Answer 9

JavaScript (ES6), 117 bytes

f=(a,n)=>(g=(i,a,n)=>n?i>n?0:g(i,[i,...a],n-i)||g(i+1,a,n):i--?a.map(v=>t-=v>i,t=a[i])|t?0:g(i,a):a)(1,a,n)||f(a,-~n)

Try it online!

How?

Starting with \$n=0\$, we prepend each non-increasing integer partition of \$n\$ to the input list and test whether one of the resulting lists is a symmetric Young diagram. We recursively increment \$n\$ until a solution is found.

For instance, the test case [5, 4, 1] is solved with \$n=16=6+5+5\$, leading to [6, 5, 5, 5, 4, 1].

Faster version (120 bytes)

This version will never generate a partition with a term less than the leading term of the input list. This allows it to solve [9, 2] (suggested by Wheat Wizard) almost instantly.

Try it online!

Commented

f = (a, n) => (       // f = main function taking the input list a[]
  g = (i, a, n) =>    // g = helper function computing the partitions
                      //     and looking for a symmetric Young diagram
    n ?               // if n is not 0:
      i > n ?         //   if i is greater than n:
        0             //     invalid partition: abort
      :               //   else:
        g(            //     first recursive call:
          i,          //       pass i unchanged
          [i, ...a],  //       prepend i to a[]
          n - i       //       subtract i from n
        ) ||          //     end of recursive call
        g(            //     second recursive call:
          i + 1,      //       increment i
          a,          //       pass a[] unchanged
          n           //       pass n unchanged
        )             //     end of recursive call
    :                 // else (n = 0 or undefined):
      i-- ?           //   decrement i; if it was not 0:
        a.map(v =>    //     for each value v in a[]:
          t -= v > i, //       decrement t if v is greater than i
          t = a[i]    //       starting with t = a[i]
        ) | t ?       //     end of map(); if t is not 0:
          0           //       this is not a symmetric Young diagram
        :             //     else:
          g(i, a)     //       process recursive calls until i = 0
      :               //   else:
        a             //     success: return a[]
)(1, a, n)            // initial call to g
|| f(a, -~n)          // if no solution was found, try again with n + 1

Answer 10

Charcoal, 43 35 bytes

ＷＳ⊞υＬι§ΦＥ⊕⌈υ⁺Ｅι⁺ιＬΦυ›νμυ⬤ι⁼λＬΦι›νμ⁰

Try it online! Link is to verbose version of code. I/O is as a Young Diagram using -s as the fill character. Explanation:

ＷＳ⊞υＬι

Input the diagram.

Ｅ⊕⌈υ

For each possible number of rows from 0 to the length of the first row (inclusive)...

⁺Ｅι⁺ιＬΦυ›νμυ

... calculate the transpose of that number of columns, concatenating with the original input.

§Φ...⬤ι⁼λＬΦι›νμ⁰

Print the first symmetric result.

Example: At each stage, an i-by-i square is prefixed to the original input (marked by # signs) and then extended by transposition (marked by = signs). The first symmetric result is then the one with 3 prefixed rows.

                                        #####===
                                ####=== #####==
                        ###===  ####==  #####==
                ##===   ###==   ####==  #####==
        #===    ##==    ###==   ####==  #####=
-----   =----   ==---   ===--   ====-   =====
----    =---    ==--    ===-    ====    ====
-       =       =       =       =       =
0       1       2       3       4       5

Answer 11

Wolfram Language (Mathematica), 87 86 76 72 bytes

l&@For[i=0,t@@(l=Join[l=#;i+t@i++,#])!=l,]&
t=Tr@UnitStep[l-#]&~Array~#&

Try it online!

The helper function t returns the first # rows of the transpose of the Young diagram of l.

main function:
   For[i=0,                             ,]  start from i=0 (#extra rows)
                      l=#;  t@i             first i rows of transposed input
                          i+                shift right by i
                 Join[           ,#]        prepend to input
           t@@(l=                   )!=l    transpose equal to itself?
l&@                                           (yes): return
                              i++             (no) : increment i and retry

t:
Tr@UnitStep[l-#]                                count entries of l >= i
                &~Array~#                       for i=1..first argument

Answer 12

R, 116 106 bytes

function(x,u=function(a,b)colSums(outer(b,1:a,`>=`)),y=x){while(any(y-u(max(y),y)))y=c(u(F<-F+1,x)+F,x);y}

Try it online!

Uses strategy copied from Neil's answer - upvote that one!