Can a run ascending list be made?

Question

A run ascending list is a list such that runs of consecutive equal elements are strictly increasing in length. For example [1,1,2,2,1,1,1] can be split into three runs [[1,1],[2,2],[1,1,1]] with lengths [2,2,3], since two runs are the same length this is not a run ascending list. Similarly [2,2,1,3,3,3] is not run ascending since the second run ([1]) is shorter than the first ([2,2]). [4,4,0,0,0,0,3,3,3,3,3] is run ascending since the three runs strictly increase in length.

An interesting challenge is to figure out for a particular set of symbols whether they can be arranged into a run ascending list. Of course the values of the individual symbols don't matter. It just matters how many of each there are.

In this challenge you will be given a list of \$n\$ positive integers, \$x_i\$, as input. Your task is to determine if a run ascending list can be made from the numbers \$1\$ to \$n\$ with each number \$k\$ appearing exactly \$x_k\$ times.

For example if the input is [4,4,7] it means you must determine if a run ascending list can be made with four 1s, four 2s and seven 3s. The answer is yes:

[1, 3,3, 1,1,1, 2,2,2,2, 3,3,3,3,3]

If the input is [9,9,1] it means you must try to find a run ascending list made of nine 1s, nine 2s and one 3. This cannot be done. It must start with the single 3 since that run can only be 1 long. Then the 1s and 2s must alternate to the end, since each run must larger than the previous, there must be more of whichever number goes last.

Rules

You should take as input a non-empty list of positive integers. You should output one of two distinct values. One if a run ascending list can be made the other if it cannot.

This is code-golf the goal is to minimize the size of your source code as measured in bytes.

Testcases

Inputs that cannot make a run ascending list

[2,2]
[40,40]
[40,40,1]
[4,4,3]
[3,3,20]
[3,3,3,3]

Inputs that can make a run ascending list

[1]
[10]
[6,7]
[7,6]
[4,4,2]
[4,4,7]
[4,4,8]

Answer 1

Python 3, 106 bytes

def f(a,n=-1,x=0):a[n]-=x;return~-any(a)^any(f(1*a,i,j+1)for i,k in enumerate(a)for j in range(x,k)if i-n)

Try it online!

Brute force search. Recursively subtracts a strictly increasing value from every index in the input, as long as it is not equal to the prviously picked index. This continues until all values in the input are zero or the options to continue are exhausted.

Answer 2

05AB1E, 13 bytes

āsÅΓœεÅγü›P}à

Brute-force approach, so extremely slow.

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

Explanation:

ā           # Push a list in the range [1, (implicit) input-length]
 s          # Swap so the input-list is at the top
  ÅΓ        # Run-length decode using the two lists
    œ       # Get all permutations of this list
     ε      # Map over each permutation:
      Åγ    #  Run-length encode the list, pushing the values and counts as two
            #  separated lists to the stack
        ü›P #  Check if this counts-list is strictly increasing:
        ü   #   For each overlapping pair of the counts-list:
         ›  #    Check if the first is larger than the second
          P #   Product to check if all of them are truthy
            #   (or if the list is empty after the overlapping pairs builtin,
            #   which means the counts-list only contains a single value)
     }à     # After the map: max to check if any of them is truthy
            # (which is output implicitly as result)

Answer 3

Brachylog, 15 bytes

{igᵗj₍}ᶠcpḅlᵐ<₁

Try it online!

Times out on most of the test cases. I believe the algorithm is something like \$O(S!)\$, where \$S\$ is the sum of the input list.

Explanation

{igᵗj₍}ᶠcpḅlᵐ<₁
{     }ᶠ         Find all ways to satisfy this predicate:
 i                 [E, I] pair where E is an element of the input and I is its index
  gᵗ               Turn that into [E, [I]]
    j₍             Concatenate [I] to itself E times
                 Result: a list of lists like [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2]]
        c        Concatenate those lists into one big list
         p       Consider some permutation of that list
          ḅ      Break it into blocks (i.e. runs of the same value)
           lᵐ    Take the length of each block
             <₁  Assert that the list of lengths is strictly increasing

Answer 4

JavaScript (ES6), 84 bytes

Returns \$0\$ or \$1\$.

f=(a,i=0,p,g)=>a.some((v,j)=>v&&(g=_=>p!=j&v>i&&f(a,v,j,a[j]-=v)|g(a[j]+=v--))())|!g

Try it online!

Commented

f = (             // f is a recursive function taking:
  a,              //   a[] = input array
  i = 0,          //   i = previous run length
  p,              //   p = previous index
  g               //   g = variable used to store a local
                  //       helper function and as a flag
) =>              //
a.some((v, j) =>  // for each value v at position j in a[]:
  v && (          //   abort if v = 0
  g = _ =>        //   g is a helper function which ignores its argument
  p != j &        //     if the index is not equal to the previous one
  v > i &&        //     and v is greater than the previous run length:
    f(            //       do a recursive call to f:
      a,          //         pass a[]
      v,          //         update i to v
      j,          //         update p to j
      a[j] -= v   //         subtract v from a[j]
    ) |           //       end of recursive call
    g(            //       do a recursive call to g:
      a[j] += v-- //         restore a[j] and decrement v
    )             //       end of recursive call
  )()             //   initial call to g
) |               // end of some()
!g                // success if some() is truthy or g = 0,
                  // which means that a[] is now filled with 0's

Answer 5

Vyxal, 17 bytes

żZødṖƛĠvL2lvƒ>A;G

Try it Online!

Port of 05AB1E. vw and f are only needed due to a bug, and ƒ∴ is needed instead of G due to another bug. Bugs fixed.

Could be 13 bytes, but, well, this challenge is what inspired me to create all those new builtins, so, I guess it doesn't count.

Answer 6

Burlesque, 32 bytes

{+.bxj.*}wiFLr@{gw)-]qU_qsom&}ay

Try it online!

Drastically inefficient brute force

{    # Generate initial list, e.g. for [2,2] builds {1 1 2 2}
 +.  # Increment (indexed from zero)
 bx  # Box
 j.* # Product
}wi  # Zip with indices and map
FL   # Flatten (strictly builds {{{1}{1}}{{2}{2}}})
r@   # All possible permutations (even repeated ones)
{
 gw  # Group like with length (count)
 )-] # Get length (count)
 qU_ # Quoted Unique
 qso # Quoted sorted
 m&  # Make and (is sorted and unique)
}ay  # Any

Answer 7

Charcoal, 59 bytes

⊞υ⟦±¹θ⁰⟧ＦυＦ…⊟ι⌈§ι¹ＦＬθＦ∧⁻λ§ι⁰›§§ι¹λκ⊞υ⟦λＥ§ι¹⁻ν∧⁼ξλ⊕κ⊕κ⟧⬤υ⌈⊟ι

Try it online! Link is to verbose version of code. Outputs nothing if a run ascending list can be made, - if not. Explanation: Inspired by @Jitse's Python answer.

⊞υ⟦±¹θ⁰⟧Ｆυ

Start a search with a previous run of 0 -1s and the original input still to process.

Ｆ…⊟ι⌈§ι¹

Loop over potential next run lengths.

ＦＬθ

Loop over potential next run values.

Ｆ∧⁻λ§ι⁰›§§ι¹λκ

If this is a new run and there are enough of the value remaining, then...

⊞υ⟦λＥ§ι¹⁻ν∧⁼ξλ⊕κ⊕κ⟧

... add a new search entry of the run and updated array of counts.

⬤υ⌈⊟ι

See whether an array of all zeros was achieved.

Answer 8

Husk, 12 bytes

¬ΛȯV≤mLgP`ṘN

Try it online!

Brute force approach, times out for even moderate inputs. TIO link includes a set of very short true & false inputs.

¬ΛȯV≤mLgP`ṘN
           N  # for each integer 1..N
         `Ṙ   # replicate it the number of times in the input array;
        P     # now get all permutations of this list
 Λȯ           # and output zero if none of these satisfy:
   V          #   there is at least one pair of adjacent elemnts
    ≤         #   for which the left is smaller or equal to the right,
     mL       #   for the lengths of each
       g      #   group of equal elements;
              # (at this point truthy (nonzero) means a run-ascending list cannot be made,
              # falsy (zero) means a run-ascending list can be made)
¬             # so NOT the result to get a consistent output
              # 1=can be made, 0=cannot be made

(Omit the final ¬ for falsy & truthy-but-non-consistent output)