Edycja: Na końcu pytania przyznam nagrodę za 100 punktów reputacji za pierwsze rozwiązanie układanki bonusowej !

Dodam nagrodę do pytania tylko wtedy, gdy pojawi się odpowiedź, ponieważ ta nagroda nie ma terminu.

Biorąc pod uwagę nie malejącą listę jednocyfrowych liczb całkowitych dodatnich, powinieneś określić, jak głębokie lochy będą kopać cyfry.

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

Przed rozpoczęciem kopania ziemia jest pozioma.

Każda cyfra może usunąć dokładnie jeden blok ziemi spod siebie, ale musi osiągnąć tę pozycję spoza lochu, a po usunięciu blok musi opuścić loch. Czyniąc to, cyfra nie może zejść ani podnieść się bardziej niż jej wartość liczbowa na żadnym poziomym kroku.

Cyfry używają następującej strategii do kopania:

• Cyfra o najmniejszej wartości kopie jako pierwsza, a następnie następna koparka jest zawsze następną najmniejszą wartością spośród pozostałych cyfr.
• Pierwsza cyfra może kopać w dowolnej pozycji. (Cały grunt jest taki sam.)
• Następujące cyfry zawsze kopią w najbardziej rozpoczętej w lewo kolumnie, do której można przejść i wyjść. Jeśli taka kolumna nie istnieje, zaczynają kopać nową kolumnę po prawej stronie skrajnej prawej.

Na przykład cyfry 1 1 1 2 3 3wykopaliby następujący loch (wizualizacja krok po kroku z liczbami oznaczającymi, który rodzaj cyfry wykopuje tę pozycję):

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

Objaśnienie dla przykładu:

• Drugi 1nie mógł wydostać się z jedynej dostępnej kolumny, jeśli pogłębiłby ją do 2głębokości, więc kopałby wprost do niej.
• Trzeci 1może kopać w 2skrajnej lewej kolumnie, tworząc kolumnę -głębną, ponieważ może przenieść się do 1kolumny -głębnej, a następnie na poziom gruntu.
• Następny 2i 3oba mogą kopać w lewej kolumnie.
• Ostatni 3nie może kopać w lewej kolumnie, ale może w następnej.

Wejście

• Nie malejąca lista dodatnich jednocyfrowych liczb całkowitych z co najmniej jednym elementem.

Wynik

• Pojedyncza dodatnia liczba całkowita, głębokość zbudowanego lochu.

Przykłady

Wejście => Dane wyjściowe (z głębokością kolumn lochu od lewej do prawej jako wyjaśnienie, które nie jest częścią wyniku)

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

To jest golf golfowy, więc wygrywa najkrótszy wpis.

Układanka premiowa

Czy możesz udowodnić (lub obalić), że strategia opisana w sekcji „Cyfry używają następującej strategii do kopania” zawsze zapewnia najgłębsze możliwe lochy dla danych cyfr?

Pyth, 21 bajtów

huXf>+H@GhT@GT0G1Qm0Q

Wypróbuj online: Pojedyncza demonstracja lub pakiet testowy

Wyjaśnienie:

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

Rozszerzona wersja do uruchomienia

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