Predict the Landslide

Question

Landslides

In this challenge, your job is to predict the extent of damage caused by a massive landslide. We use the following simplified two-dimensional model for it, parameterized by an initial height h >= 0 and a critical coefficient c > 0. You start with a cliff of height h, and it is assumed that the terrain is completely flat infinitely to the left and to the right of it. For h = 6, the situation looks like this:

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

The - are immovable bedrock, and the # are unstable soil. If the height difference between two neighboring columns is more than c, a landslide occurs: the top c units of soil from the left column fall down to the next c columns on the right, one to each. The rightmost non-empty column in the figure is unstable for c = 2, so a landslide is triggered:

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

The column is still unstable, which causes a second landslide:

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

Now, the column on its left has become unstable, so a new landslide is triggered there:

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

After this, the cliff is stable again. The nice thing about this model is that the order in which the landslides are processed does not matter: the end result is the same.

The Task

Your program is given the integer parameters h and c as inputs (the order does not matter, but you must specify it on your answer), and it should output the total number of columns that the landslide affects. This means the number of columns in the resulting stable cliff whose height is strictly between 0 and h. In the above example, the correct output is 4.

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

These are given in the format 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

Answer 1

CJam, 62 57 bytes

As far as I can see, this is completely different approach to implement the solution from aditsu's answer.

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

Input goes in the form of h c

Example:

80 5

Output:

28

How it works

The logic is pretty straight forward here with a few tricks used to reduce code size.

• Get h + 1 (+ 1 for h = 0 case) length array with each element being h to represent the cliff
• Start iterating from the right most index of this array
  • If the two elements from current index have different more than c
    • Remove c from the current index element
    • Add 1 to next c elements of the array from the current index
    • Make the current index equal to the length of this new array
    • This makes sure that we stabilize the stones to the right of the current index first
  • else, reduce the current index
• When we hit the left most index, we are making sure that all adjacent indexes have less than or equal to c difference
• Remove any 0 or h value from the array and get length.

Code expansion

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

Try it online here

Answer 2

CJam - 70

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

Try it at http://cjam.aditsu.net/

Explanation:

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

The h operator checks the last value on the stack without removing it. If a landslide occurred, the value is the cliff array, which evaluates to true because it's not empty. If not, the last value is 0 (false).
So in case of landslide, the loop continues with the array on the stack, otherwise it ends with a 0 pushed after the array. That 0 is then removed from the array by the next - operator.

Answer 3

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)

Expanded version:

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: After some optimizing, I eliminated the awkward loop termination via break (saves 1 byte). Also changed the slide from slice based to loop based.

Answer 4

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)

(Note that SE's markdown interpreter converts literal tabs to 4 spaces. Lines 7 and 8 of this program have only a single tab [i.e. one byte] of indentation each.)

Takes input on stdin, h first. For example:

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

This program has been through a lot of improvements. I had been editing this answer to explain some of the more major edits, but it was getting kind of long. You can check the edit history if you're curious.

Explanation

First, hand c are read from stdin. In Python 2, input() is equivalent to eval(raw_input()), which is why I ask for a comma separating the numbers. input() gives returns a tuple of ints, no conversion required.

Next, a list of integers is made. It is 2*h long. The first half are h and the second half are 0. I don't have any reasoning to show that this is enough to simulate infinite hs to the left and 0s to the right. I just sort of stumbled into it and it works for all the test cases, so if someone can find input it doesn't work for I'll gladly change it. Anyway, this list is called l, but another copy of it is called b.

b's value doesn't actually matter, all that matters is that it's truthy. A non-empty list is truthy and the only way b can be empty here is if h is 0, in which case the correct answer is still printed. In any other case, b has to be truthy to ensure we enter the while b: loop. However, the first thing that happens in the loop is setting b to 0, a falsey value. During each repetition of the loop b must be specifically set back to a truthy one or the loop will end.

The rest of the loop is the actual simulation. It's very naive, essentially just being a code translation of the problem description. If any element of l is more than c greater than the one following it, it is subtracted by c and the next c elements have 1 added to them. (The bitwise magic used here is just a shorter way of writing i+1+j, by the way.) While making these transformations, b is set to 1. The first time no transformations are made, b will stay 0 and the loop terminates.

Any true expression evaluates to True, and when you try to do math on True it evaluates to 1. The same is true of False and 0. The last line of the program uses every element of l as e in the expression h>e>0 and sums the result. This gets the number of columns greater than 0 but lower than the original cliff height, which is the value the question asks for. It's printed and the program exits.

Answer 5

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)

Usage: h#c, e.g. 6#2 which outputs 4.

How it works: the helper function s does a single landslide. Repeatedly apply s until the output does not change anymore. Count the affected elements.

Found the "apply until output doesn't change" function (i.e. until=<<((==)=<<)) at Stackoverflow.

Answer 6

Mathematica, 108 104 100 97 95

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

Usage:

f[c, h]

Example:

f[5, 80]

28

Answer 7

C# 303 295

It works!

But it is a ....

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

I must find new language ;)

I'll check this CJam thing ...

Improved:

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