Digits Digging a Dungeon

Question

Edit: I will award a 100-reputation bounty for the first solver of the bonus puzzle at the end of the question!

I will add the bounty to the question only when the answer appears as this bounty has no deadline.

Given a non-decreasing list of one-digit positive integers, you should determine how deep dungeon the digits will dig.

███  ███  A dungeon with 5 blocks removed and a depth of 3.
███  ███
███ ████
████████

Before the start of the digging the ground is level.

Every digit can remove exactly one block of soil from below itself but it has to reach that position from outside the dungeon and after it removed the block has to leave the dungeon. While doing so a digit can't descend or ascend more than its numerical value at any horizontal step.

The digits use the following strategy for digging:

• The digit with the smallest value digs firsts and after that the next digger is always the next smallest value from the rest of the digits.
• The first digit can dig at any position. (All ground is the same.)
• The following digits always dig at the leftmost already started column where they can go and come out. If no such column exists they start to dig a new column on the right side of the rightmost one.

For example the digits 1 1 1 2 3 3 would dig the following dungeon (step-by-step visualization with numbers marking which kind of digit dig out that position):

███1████    ███11███    ███11███    ███11███    ███11███    ███11███
████████    ████████    ███1████    ███1████    ███1████    ███13███
████████    ████████    ████████    ███2████    ███2████    ███2████
████████    ████████    ████████    ████████    ███3████    ███3████
████████    ████████    ████████    ████████    ████████    ████████

Explanation for the example:

• The second 1 couldn't climb out of the only available column if it would deepen it to 2-deep so it digs right to it.
• The third 1 can dig in the leftmost column creating a 2-deep column as it can move out into the 1-deep column and then to the ground level.
• The next 2 and 3 both can dig in the leftmost column.
• The last 3 can't dig in the leftmost column but can in the next one.

Input

• A non-decreasing list of positive one-digit integers with at least one element.

Output

• A single positive integer, the depth of the constructed dungeon.

Examples

Input => Output (with the depths of the columns of the dungeon from left to right as explanation which is not part of the output)

[3]  =>  1
(column depths are [1])

[1, 1, 1, 2, 3, 3]  =>  4
(column depths are [4, 2])

[1, 1, 1, 1, 1, 1, 1, 1]  =>  3
(column depths are [3, 2, 2, 1])

[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5]  =>  11
(column depths are [11, 6, 2])

[1, 1, 1, 1, 1, 2, 2, 9, 9, 9]  =>  7
(column depths are [7, 2, 1])

[2, 2, 2, 2, 2, 5, 5, 5, 7, 7, 9]  =>  9
(column depths are [9, 2])

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]  =>  10
(column depths are [10, 5])

[1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9]  =>  13
(column depths are [13, 5])

[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]  =>  13
(column depths are [13, 5])

[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9]  =>  21
(column depths are [21, 12, 3])

This is code-golf so the shortest entry wins.

Bonus puzzle

Can you prove (or disprove) that the strategy described in the "The digits use the following strategy for digging" section always gives the deepest possible dungeon for the given digits?

Answer 1

Pyth, 21 bytes

huXf>+H@GhT@GT0G1Qm0Q

Try it online: Single Demonstration or Test Suite

Explanation:

                  m0Q   generate a list of zeros of length len(input)
                        This will simulate the current depths
 u               Qm0Q   reduce G, starting with G=[0,...,0], for H in input():
   f          0             find the first number T >= 0, which satisfies:
    >+H@GhT@GT                  H + G[T+1] > G[T]
  X            G1           increase the depth at this position by one
                            update G with this result
h                       print the first element in this list

Answer 2

Java, 199

import java.util.*;a->{List<Integer>l=new ArrayList();l.add(0);int x,y,z=0;s:for(int i:a){for(x=0;x<z;x++)if((y=l.get(x))-l.get(x+1)<i){l.set(x,l.get(x)+1);continue s;}l.add(z++,1);}return l.get(0);}

Expanded, runnable version

import java.util.*;
class DIGits {
    public static void main(String[] args) {
        java.util.function.Function<int[], Integer> f =
                a->{
                    List<Integer> l = new ArrayList();
                    l.add(0);
                    int x, y, z = 0;
                    s:
                    for (int i : a) {
                        for (x = 0; x < z; x++) {
                            if ((y = l.get(x)) - l.get(x + 1) < i) {
                                l.set(x, l.get(x) + 1);
                                continue s;
                            }
                        }
                        l.add(z++, 1);
                    }
                    return l.get(0);
                };
        System.out.println(f.apply(new int[]{1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9}));
    }
}