Edit: Eu concederei uma recompensa de 100 reputações para o primeiro solucionador do quebra - cabeça de bônus no final da pergunta!

Acrescentarei a recompensa à pergunta somente quando a resposta aparecer, pois essa recompensa não tem prazo.

Dada uma lista não decrescente de números inteiros positivos de um dígito, você deve determinar a profundidade da masmorra em que os dígitos serão cavados.

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

Antes do início da escavação, o solo está nivelado.

Cada dígito pode remover exatamente um bloco de solo de baixo de si mesmo, mas ele tem que alcançar essa posição de fora da masmorra e, depois de removido, o bloco deve sair da masmorra. Enquanto isso, um dígito não pode descer ou subir mais do que seu valor numérico em qualquer etapa horizontal.

Os dígitos usam a seguinte estratégia para escavar:

• O dígito com o menor valor digita primeiro e, depois disso, o próximo digger é sempre o próximo valor menor do restante dos dígitos.
• O primeiro dígito pode cavar em qualquer posição. (Todo o terreno é o mesmo.)
• Os dígitos a seguir sempre digitam na coluna já iniciada à esquerda, onde podem sair e sair. Se essa coluna não existir, eles começarão a cavar uma nova coluna no lado direito da coluna mais à direita.

Por exemplo, os dígitos 1 1 1 2 3 3cavariam a seguinte masmorra (visualização passo a passo com números marcando que tipo de dígito desenterra essa posição):

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

Explicação para o exemplo:

• O segundo 1não poderia sair da única coluna disponível, se a aprofundasse até-profundidade, para que ela se 2afundasse.
• O terceiro 1pode cavar na coluna mais à esquerda, criando uma 2coluna -deep, pois pode sair para a 1coluna -ep e depois para o nível do solo.
• O próximo 2e 3ambos podem cavar na coluna mais à esquerda.
• O último 3não pode cavar na coluna mais à esquerda, mas na próxima.

Entrada

• Uma lista não decrescente de números inteiros positivos de um dígito com pelo menos um elemento.

Resultado

• Um único número inteiro positivo, a profundidade da masmorra construída.

Exemplos

Entrada => Saída (com as profundidades das colunas da masmorra da esquerda para a direita como explicação que não faz parte da saída)

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

Isso é código-golfe, portanto a entrada mais curta vence.

Quebra-cabeça bônus

Você pode provar (ou refutar) que a estratégia descrita na seção "Os dígitos usam a seguinte estratégia para cavar" sempre fornece a masmorra mais profunda possível para os dígitos fornecidos?

Pitão, 21 bytes

huXf>+H@GhT@GT0G1Qm0Q

Experimente on-line: demonstração única ou suíte de testes

Explicação:

                  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

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);}

Versão expandida e executável

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}));
    }
}