Deslizamientos de tierra

En este desafío, su trabajo es predecir el alcance del daño causado por un deslizamiento de tierra masivo. Utilizamos el siguiente modelo bidimensional simplificado para ello, parametrizado por una altura inicial h >= 0 y un coeficiente crítico c > 0 . Comienzas con un acantilado de altura h, y se supone que el terreno es completamente plano infinitamente a la izquierda y a la derecha. Para h = 6, la situación se ve así:

##########
##########
##########
##########
##########
##########
-----------------------

El -son lecho de roca inamovible, y el #son suelos inestables. Si la diferencia de altura entre dos columnas vecinas es mayor que c, se produce un deslizamiento de tierra : las cunidades superiores de suelo de la columna izquierda caen a las siguientes ccolumnas a la derecha, una a cada una. La columna no vacía más a la derecha de la figura es inestable c = 2, por lo que se desencadena un deslizamiento de tierra:

#########
#########
##########
##########
##########
############
-----------------------

La columna aún es inestable, lo que causa un segundo deslizamiento de tierra:

#########
#########
#########
#########
############
############
-----------------------

Ahora, la columna a su izquierda se ha vuelto inestable, por lo que se desencadena un nuevo deslizamiento de tierra allí:

########
########
#########
###########
############
############
-----------------------

Después de esto, el acantilado es estable nuevamente. Lo bueno de este modelo es que el orden en que se procesan los deslizamientos de tierra no importa: el resultado final es el mismo.

La tarea

Su programa recibe los parámetros enteros hy ccomo entradas (el orden no importa, pero debe especificarlo en su respuesta), y debería generar el número total de columnas que afecta el deslizamiento de tierra. Esto significa el número de columnas en el acantilado estable resultante cuya altura es estrictamente entre 0y h. En el ejemplo anterior, la salida correcta es 4.

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

Estos se dan en el formato h c -> output.

0  2  -> 0
2  3  -> 0
6  2  -> 4
6  6  -> 0
10 1  -> 10
15 1  -> 14
15 2  -> 11
15 3  -> 6
40 5  -> 16
80 5  -> 28
80 10 -> 17

CJam, 62 57 bytes

Hasta donde puedo ver, este es un enfoque completamente diferente para implementar la solución de la respuesta de aditsu.

q~:C;:HaH)*H){(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h-H-,

La entrada va en forma de h c

Ejemplo:

80 5

Salida:

28

Cómo funciona

La lógica es bastante sencilla aquí con algunos trucos utilizados para reducir el tamaño del código.

• Obtenga h + 1( + 1para el h = 0caso) una matriz de longitud con cada elemento hpara representar el acantilado
• Comience a iterar desde el índice más a la derecha de esta matriz
  • Si los dos elementos del índice actual tienen diferentes más de c
    • Eliminar cdel elemento de índice actual
    • Agregar 1a los siguientes celementos de la matriz desde el índice actual
    • Haga que el índice actual sea igual a la longitud de esta nueva matriz
    • Esto asegura que estabilicemos las piedras a la derecha del índice actual primero
  • de lo contrario, reduzca el índice actual
• Cuando tocamos el índice más a la izquierda, nos estamos asegurando de que todos los índices adyacentes tengan una cdiferencia menor o igual a
• Eliminar cualquier 0o hvalor de la matriz y obtener longitud.

Expansión de código

q~:C;:HaH)*H){(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h-H-,
q~:C;:HaH)*H)
q~:C;:H                  "Read the input, evaluate it, store height in H and coeff. in C";
       aH)*              "Wrap the height number in an array and repeat it H + 1 times";
           H)            "Put H+1 on stack, representing the current index of iteration";
{(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h
(:I\_@>2<:-C>
(:I                      "Decrement the current index and store it in I";
   \_                    "Swap to put array on top and make 1 copy";
     @>2<                "Get the two elements starting from Ith index";
         :-              "Get the difference. The best part of this approach is that";
                         "For the right most index, where there is only element, it";
                         "returns the element itself, which is the expected difference";
           C>            "Check if difference is greater than C";
{I0a*C~)+C1a*+]z1fb_,}   "This block will be executed when the difference is more than C";
 I0a*                    "Get an array of I length and all elements 0";
     C~)+                "Get -C value and append it to the above array";
         C1a*+           "Get C length array of 1s and concat with the above array";
              ]          "Wrap the two arrays, the cliff and the above one in an array";
               z1fb      "Transpose to get number pairs and add those pairs. For example";
                         "If we are at the right most index with H = 80 and C = 5,";
                         "The right section of the cliff looks like:";
                         "[ ... 80 80 80 80 80] and the array created in above step";
                         "looks like [ ... 0 0 0 0 -5 1 1 1 1 1]. After z, we have:";
                         "[ ... [80 0] [80 0] [80 0] [80 0] [80 -5] [1] [1] [1] [1] [1]]";
                         "After 1fb we get [ ... 80 80 80 80 75 1 1 1 1 1]";
                   _,    "Take a copy of the above resultant array and take its length";
I?                       "If difference was not greater than C, put I on stack";
                         "Now we either have the decremented index or new array length";
                         "on stack."
{ ... }h                 "This is a do while loop which makes sure that we iterate to";
                         "the left of the array. This loops runs till the top stack";
                         "element is 0 while not popping the top element";
        -H-,             "After the loop, we have the final cliff array and 0 on stack";
                         "Remove any 0 elements from the array, then remove any H";
                         "elements from the array and then take length to get the";
                         "number of columns which were modified";

Pruébalo en línea aquí

CJam - 70

q~:C;:H0]H*$W%{[__W<\1>]z{~-}%{C>}#):I{I(_2$=C-tC,{I+_2$=)t}/}0?}h-H-,

Pruébalo en http://cjam.aditsu.net/

Explicación:

q~                    read and evaluate the input
:C;                   store the 2nd number in C and remove
:H                    store the first number in H
0]H*                  make an array [H 0] and repeat it H times
$W%                   sort and reverse, obtaining [(H H's) (H 0's)] (initial cliff)
{                     loop...
    [__W<\1>]         make an array with the cliff without the first column
                      and the cliff without the last column
    z{~-}%            subtract the 2 arrays to get the height differences
    {C>}#             find the index of the first height diff. greater than C
    ):I               increment and store in I
    {                 if the value is non-zero (i.e. landslide occurring)
        I(_2$=C-t     subtract C from the corresponding column height
        C,            make an array [0 1 ... C-1]
        {             for each of those numbers
            I+        add I, obtaining a column index where some soil falls
            _2$=)t    increment the column height
        }/            end loop
    }0?               else break outer loop; end if
}h                    ...while the condition is true
-H-                   remove all 0 and H from the final stable cliff
,                     count the remaining columns

El hoperador verifica el último valor en la pila sin eliminarlo. Si ocurrió un deslizamiento de tierra, el valor es la matriz de acantilados, que se evalúa como verdadera porque no está vacía. Si no, el último valor es 0 (falso).
Entonces, en caso de deslizamiento de tierra, el bucle continúa con la matriz en la pila, de lo contrario termina con un 0 empujado después de la matriz. Ese 0 luego es eliminado de la matriz por el siguiente -operador.

Pitón, 200 190 174

h,c=input();q=[h]*h+[0]*h
try:
 while 1:
    d=[b-a for a,b in zip(q[1:],q)];g=max(d);a=d.index(g)
    for i in range(c):q[a+1+i]+=1/(g>c);q[a]-=1
except:print sum(h>i>0for i in q)

Versión ampliada:

h, c = input()
# Initialize the heights
q = [h]*h + [0]*h
try:
    while 1:
        # Difference between the heights
        d = [b-a for a,b in zip(q[1:],q)]
        # It may error here, when h == 0, but thats okay
        g = max(d)
        a = d.index(g)
        for i in range(c):
            # This is the termination condition, when g <= c
            q[a+1+i] += 1 / (g>c)
            # Save the newline; also move this line to after termination
            q[a] -= 1
except:
    # Count all heights that have changed
    print sum(h > i > 0 for i in q)

Editar: después de un poco de optimización, eliminé la incómoda terminación del bucle a través de un descanso (guarda 1 byte). También cambió la diapositiva de rebanada a bucle.

Python 2 - 194 158 bytes

h,c=input()
b=l=[h]*h+[0]*h
while b:
 b=0
 for i in range(len(l)-1):
  if l[i]-l[i+1]>c:
    for j in range(c):l[i-~j]+=1
    l[i]-=c;b=1
print sum(h>e>0for e in l)

(Tenga en cuenta que el intérprete de rebajas de SE convierte las pestañas literales en 4 espacios. Las líneas 7 y 8 de este programa tienen una sola pestaña [es decir, un byte] de sangría cada una).

Toma entrada en stdin, hprimero. Por ejemplo:

$ ./landslide.py <<< '6, 2'
4

Este programa ha pasado por muchas mejoras. Había estado editando esta respuesta para explicar algunas de las ediciones más importantes, pero se estaba haciendo bastante larga. Puede consultar el historial de edición si tiene curiosidad.

Explicación

Primero, hy cse leen de stdin. En Python 2, input()es equivalente a eval(raw_input()), por eso pido una coma que separe los números. input()devuelve una tupla de entradas, no se requiere conversión.

A continuación, se hace una lista de enteros. Es 2*hlargo La primera mitad son hy la segunda mitad son 0. No tengo ningún razonamiento para demostrar que esto es suficiente para simular infinitos hs a la izquierda y 0s a la derecha. Simplemente me topé con él y funciona para todos los casos de prueba, por lo que si alguien puede encontrar información, no funciona, con mucho gusto lo cambiaré. De todos modos, se llama a esta lista l, pero se llama a otra copia b.

bEl valor en realidad no importa, lo único que importa es que es verdad. Una lista no vacía es verdadera y la única forma en que bpuede estar vacía aquí es si hes 0, en cuyo caso todavía se imprime la respuesta correcta. En cualquier otro caso, btiene que ser sincero para garantizar que entremos en el while b:bucle. Sin embargo, lo primero que sucede en el bucle es establecer ba 0, un valor falsey. Durante cada repetición del ciclo bdebe establecerse específicamente en uno verdadero o el ciclo finalizará.

El resto del bucle es la simulación real. Es muy ingenuo, esencialmente solo es una traducción de código de la descripción del problema. Si algún elemento de les más que cmayor que el siguiente, se resta cy los siguientes celementos tienen 1 agregado. (La magia bit a bit utilizada aquí es solo una forma más corta de escribir i+1+j, por cierto). Mientras realiza estas transformaciones, bse establece en 1. La primera vez que no se realicen transformaciones, bpermanecerá 0 y el bucle terminará.

Cualquier expresión verdadera se evalúa como True, y cuando intenta hacer cálculos matemáticos Truese evalúa como 1. Lo mismo es cierto para Falsey 0. La última línea del programa usa todos los elementos de lcomo een la expresión h>e>0y suma el resultado. Esto obtiene el número de columnas mayor que 0 pero menor que la altura del acantilado original, que es el valor que pide la pregunta. Está impreso y el programa sale.

Haskell, 163 156 151 Bytes

h#c=sum[1|e<-(until=<<((==)=<<))s$r h++r 0,e`mod`h/=0]where r=replicate$h+1;s w@(x:y:z)|x==0=w|x>c+y=x-c:map(+1)(take c(y:z))++drop c(y:z)|1<2=x:s(y:z)

Uso: h#cpor ejemplo, 6#2qué salidas 4.

Cómo funciona: la función auxiliar shace un solo deslizamiento de tierra. Aplicar repetidamente shasta que la salida ya no cambie. Cuenta los elementos afectados.

Encontró la función "aplicar hasta que la salida no cambia" (es decir until=<<((==)=<<)) en Stackoverflow .

Mathematica, 108 104 100 97 95

f=Max@#-Min@#&[0Range@#2//.{x___,k:##..&[a_,{#}],a_,y___}:>Sort@{x,##&@@({k}-1),a+#,y}/.{}->0]&

Uso:

f[c, h]

Ejemplo:

f[5, 80]

28

C # 303 295

¡Funciona!

Pero es un ...

int q(int n,int c){var s=Enumerable.Repeat(n,n).ToList();s.Add(0);var d=new HashSet<int>();var g=true;while(g){g=false;for(int i=s.Count-1;i>0;i--){int z=i;int y=i-1;if((s[y]-s[z])>c){s[y]-=c;d.Add(y);g=true;for(int j=1;j<=c;j++){s[y+j]++;d.Add(y+j);if(s[s.Count-1]>0)s.Add(0);}break;}}}return d.Count;}

Debo encontrar un nuevo lenguaje;)

Comprobaré esto de CJam ...

Mejorado:

int q(int n,int c){var s=Enumerable.Repeat(n,n).ToList();s.Add(0);var d=new HashSet<int>();var g=1>0;while(g){g=1<0;for(int i=s.Count-1;i>0;i--){int z=i,y=i-1;if((s[y]-s[z])>c){s[y]-=c;d.Add(y);g=1>0;for(int j=1;j<=c;j++){s[y+j]++;d.Add(y+j);if(s[s.Count-1]>0)s.Add(0);}break;}}}return d.Count;}