Editar: ¡otorgaré una recompensa de 100 reputación por el primer solucionador del rompecabezas de bonificación al final de la pregunta!
Agregaré la recompensa a la pregunta solo cuando aparezca la respuesta, ya que esta recompensa no tiene fecha límite.
Dada una lista no decreciente de enteros positivos de un dígito, debes determinar qué tan profundo cavarán los dígitos.
███ ███ A dungeon with 5 blocks removed and a depth of 3.
███ ███
███ ████
████████
Antes del inicio de la excavación, el suelo está nivelado.
Cada dígito puede eliminar exactamente un bloque de tierra debajo de sí mismo, pero debe alcanzar esa posición desde el exterior de la mazmorra y, después de eliminarlo, el bloque debe abandonar la mazmorra. Al hacerlo, un dígito no puede descender ni ascender más que su valor numérico en ningún paso horizontal.
Los dígitos utilizan la siguiente estrategia para excavar:
- El dígito con el valor más pequeño excava primero y luego el siguiente buscador es siempre el siguiente valor más pequeño del resto de los dígitos.
- El primer dígito puede excavar en cualquier posición. (Todo el terreno es el mismo)
- Los siguientes dígitos siempre cavan en la columna más a la izquierda ya iniciada donde pueden ir y salir. Si no existe tal columna, comienzan a cavar una nueva columna en el lado derecho de la derecha.
Por ejemplo, los dígitos 1 1 1 2 3 3
cavarían la siguiente mazmorra (visualización paso a paso con números que marcan qué tipo de dígito cava esa posición):
███1████ ███11███ ███11███ ███11███ ███11███ ███11███
████████ ████████ ███1████ ███1████ ███1████ ███13███
████████ ████████ ████████ ███2████ ███2████ ███2████
████████ ████████ ████████ ████████ ███3████ ███3████
████████ ████████ ████████ ████████ ████████ ████████
Explicación para el ejemplo:
- El segundo
1
no podría salir de la única columna disponible si lo profundizara a profundidad para que2
cavara directamente. - El tercero
1
puede cavar en la columna más a la izquierda creando una2
columna profunda ya que puede moverse hacia la1
columna profunda y luego al nivel del suelo. - El siguiente
2
y3
ambos pueden cavar en la columna más a la izquierda. - El último
3
no puede cavar en la columna más a la izquierda, pero puede en la siguiente.
Entrada
- Una lista no decreciente de enteros positivos de un dígito con al menos un elemento.
Salida
- Un solo entero positivo, la profundidad de la mazmorra construida.
Ejemplos
Entrada => Salida (con las profundidades de las columnas de la mazmorra de izquierda a derecha como explicación que no forma parte de la salida)
[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])
Este es el código de golf, por lo que gana la entrada más corta.
Rompecabezas de bonificación
¿Puedes probar (o refutar) que la estrategia descrita en la sección "Los dígitos usan la siguiente estrategia para cavar" siempre ofrece la mazmorra más profunda posible para los dígitos dados?
fuente