Deslizamentos de terra

Nesse desafio, seu trabalho é prever a extensão dos danos causados ​​por um grande deslizamento de terra. Utilizamos o seguinte modelo bidimensional simplificado, parametrizado por uma altura inicial h >= 0 e um coeficiente crítico c > 0 . Você começa com um penhasco de altura h, e supõe-se que o terreno seja completamente plano infinitamente à esquerda e à direita dele. Pois h = 6, a situação é assim:

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

Os -alicerces são imóveis e o #solo é instável. Se a diferença de altura entre duas colunas vizinhas for maior que c, ocorre um deslizamento de terra : a parte superiorc unidades do solo da coluna esquerda caem para as próximas ccolunas à direita, uma para cada. A coluna não vazia à direita na figura é instável c = 2, portanto, um deslizamento de terra é acionado:

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

A coluna ainda é instável, o que causa um segundo deslizamento de terra:

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

Agora, a coluna à esquerda ficou instável, então um novo deslizamento de terra é acionado lá:

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

Depois disso, o penhasco fica estável novamente. O bom desse modelo é que a ordem na qual os deslizamentos são processados ​​não importa: o resultado final é o mesmo.

A tarefa

Seu programa recebe os parâmetros inteiros he ccomo entradas (a ordem não importa, mas você deve especificá-lo em sua resposta) e deve gerar o número total de colunas afetadas pelo deslizamento de terra. Isso significa o número de colunas no penhasco estável resultante, cuja altura é estritamente entre 0e h. No exemplo acima, a saída correta é 4.

Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas.

Casos de teste

Estes são dados no 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

Tanto quanto posso ver, essa é uma abordagem completamente diferente para implementar a solução da resposta do aditsu.

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

A entrada vai na forma de h c

Exemplo:

80 5

Saída:

28

Como funciona

A lógica é bastante direta aqui, com alguns truques usados ​​para reduzir o tamanho do código.

• Obter h + 1( + 1por h = 0caso) matriz de comprimento com cada elemento sendoh representando a falésia
• Comece a iterar a partir do índice mais à direita desta matriz
  • Se os dois elementos do índice atual tiverem mais de c
    • Remover cdo elemento de índice atual
    • Adicione 1aos próximos celementos da matriz do índice atual
    • Tornar o índice atual igual ao comprimento dessa nova matriz
    • Isso garante que estabilizamos as pedras à direita do índice atual primeiro
  • caso contrário, reduza o índice atual
• Quando atingimos o índice mais à esquerda, garantimos que todos os índices adjacentes tenham menos ou igual à cdiferença
• Remova qualquer valor 0ou hda matriz e obtenha comprimento.

Expansão 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";

Experimente online aqui

CJam - 70

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

Experimente em http://cjam.aditsu.net/

Explicação:

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

O hoperador verifica o último valor na pilha sem removê-lo. Se um deslizamento de terra ocorreu, o valor é a matriz do penhasco, avaliada como verdadeira porque não está vazia. Caso contrário, o último valor é 0 (falso).
Portanto, no caso de deslizamento de terra, o loop continua com a matriz na pilha, caso contrário, termina com um 0 pressionado após a matriz. Esse 0 é então removido da matriz pelo próximo -operador.

Python, 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)

Versão expandida:

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)

Edit: Após algumas otimizações, eliminei a terminação do loop inábil por meio de interrupção (economiza 1 byte). Também mudou o slide de fatia baseada em loop.

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)

(Observe que o intérprete de redução de conversão do SE converte guias literais em 4 espaços. As linhas 7 e 8 deste programa têm apenas uma única guia [isto é, um byte] de recuo cada.)

Recebe entrada em stdin, hprimeiro. Por exemplo:

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

Este programa passou por muitas melhorias. Eu estava editando esta resposta para explicar algumas das edições mais importantes, mas estava ficando um pouco longa. Você pode verificar o histórico de edições se estiver curioso.

Explicação

Primeiro, he csão lidos pelo stdin. No Python 2, input()é equivalente a eval(raw_input()), e é por isso que peço uma vírgula separando os números.input()retorna uma tupla de ints, nenhuma conversão é necessária.

Em seguida, é feita uma lista de números inteiros. É 2*hlongo. A primeira metade é he a segunda metade é 0. Não tenho nenhum raciocínio para mostrar que isso é suficiente para simular infinitos hs à esquerda e 0s à direita. Eu meio que tropecei nele e ele funciona em todos os casos de teste; portanto, se alguém puder encontrar informações, não funcionará. De qualquer forma, essa lista é chamada l, mas outra cópia é chamadab .

bO valor de realmente não importa, tudo o que importa é que é verdade. Uma lista não vazia é realmente verdadeira e a única maneira de bficar vazia aqui é se hfor 0; nesse caso, a resposta correta ainda será impressa. Em qualquer outro caso, bdeve ser verdade para garantir que entramos no while b:loop. No entanto, a primeira coisa que acontece no loop é definir b0, um valor falsey. Durante cada repetição do loop, bdeve-se voltar especificamente para um número real ou o loop terminará.

O restante do loop é a simulação real. É muito ingênuo, essencialmente apenas sendo uma tradução de código da descrição do problema. Se qualquer elemento de lfor cmaior que o seguinte, é subtraído por ce os próximos celementos têm 1 adicionado a eles. (A mágica bit a bit usada aqui é apenas uma maneira mais curta de escrever i+1+j, a propósito.) Ao fazer essas transformações, bé definido como 1. Na primeira vez que nenhuma transformação for feita, bpermanecerá 0 e o loop será encerrado.

Qualquer expressão verdadeira é avaliada como True, e quando você tenta fazer matemática, Trueé avaliada como 1. O mesmo vale para Falsee 0. A última linha do programa usa todos os elementos de lcomo ena expressão h>e>0e soma o resultado. Isso obtém o número de colunas maior que 0, mas menor que a altura original do penhasco, que é o valor que a pergunta solicita. É impresso e o programa sai.

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 exemplo, 6#2quais saídas 4.

Como funciona: a função auxiliar sfaz um único deslizamento de terra. Aplicar repetidamentes até que a saída não mude mais. Conte os elementos afetados.

Encontrada a função "aplicar até a saída não mudar" (ou seja, until=<<((==)=<<) ) no 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]

Exemplo:

f[5, 80]

28.

C # 303 295

Funciona!

Mas é um ....

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

Eu preciso encontrar um novo idioma;)

Vou verificar essa coisa CJam ...

Melhorado:

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