Analyzing Earthquakes

Question

Background

The Random Domino Automaton is a toy model for earthquakes, inspired by cellular automata. In this challenge, your task is to simulate a simplified version of this model, and collect data out of it.

The automaton is defined on an array A of k bits, representing a fault line on which earthquakes may occur. The array wraps around at its borders. The condition A[i] = 0 means that position i is relaxed, and A[i] = 1 means that it's excited, or contains stored energy. At each time step, one position of the array is chosen uniformly at random. If that position is relaxed, it becomes excited (potential energy is added to the system). If that position is already excited, it triggers an earthquake, and the chosen position and all excited positions connected to it are relaxed again. The number of excited positions that become relaxed is the magnitude of the earthquake.

Example

Consider the array

100101110111

of length 12. If the random process chooses the second bit from the left, the array is updated to

110101110111
 ^

since the chosen bit (marked with ^) was 0. If we next choose the fourth bit from the left, which is an isolated 1, an eartquake of magnitude 1 is triggered, and the bit is set to 0 again:

110001110111
 ^

Next, we might choose the second bit from the right, which triggers an earthquake of magnitude 5:

000001110000
 ^

Note that all 1s in the same "cluster" as the chosen one were part of the quake, and the array wraps around at the border.

The Task

You shall take as inputs two positive integers k and t, and your task is to simulate the random domino automaton for t time steps, starting from an initial length-k array of all 0s. Your output shall be a list L of k integers, where L[i] (with 1-based indexing) contains the number of earthquakes of magnitude i that occurred during the simulation. You are allowed to drop trailing zeroes from the output.

For the inputs k = 15 and t = 1000, some representative outputs are

[117, 97, 45, 26, 10, 5, 3, 1, 3, 0, 0, 0, 0, 0, 0]
[135, 91, 58, 21, 8, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0]
[142, 63, 51, 31, 17, 4, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[106, 75, 45, 30, 16, 8, 5, 2, 2, 0, 0, 0, 0, 0, 0]
[111, 96, 61, 22, 3, 8, 3, 2, 0, 0, 0, 1, 0, 0, 0]

Rules

Both full programs and functions are allowed. The shortest byte count wins, and standard loopholes are disallowed.

Note that you are not required to simulate the automaton using any particular implementation, only the output matters.

• DeadChex: Is it possible that you can add a caret ^ under the bit that changes? It might make it easier to visualize the example
• Zgarb: @DeadChex Good idea, updated.

Answer 1

CJam, (削除) 57 (削除ここまで) 55 bytes

{:K,K0a*@[{Kmrm<){_{_0#>W%K0e]}2*_)}1?+}*;]1fb2/::-fe=}

This is an anonymous function that pops k and t from the stack (k on top of t) and leaves the desired array in return.

Try it online in the CJam interpreter.

How it works

:K e# Save the topmost integer (k) in K.
, e# Push I := [0 ... K-1].
K0a* e# Push J := [0 ... 0] (K elements).
@ e# Rotate the other integer (t) on top of the stack.
[{ e# Do t times:
 Kmr e# Pseudo-randomly select an integer between 0 and t-1.
 m< e# Rotate the array J than many units to the left.
 ) e# Pop out the last element.
 { e# If it is 1:
 _ e# Copy J.
 { e# Do 2 times:
 _0# e# Push the first index of 0 in J.
 > e# Discard the preceding elements.
 W% e# Reverse the array.
 K0e] e# Pad it with zeroes to length K.
 }2* e#
 _) e# Copy J and pop out the last element.
 } e#
 1? e# Else: Push 1.
 + e# Push the integer on the stack on J.
}* e#
; e# Discard the last value of J.
] e# Collect the intermediate values of J in an array.
1fb e# Replace each array by the sum of its elements (number of ones).
2/ e# Split the array into chunks of length 2.
::- e# Replace each chunk by the difference of its elements.
fe= e# Count the occurrences of each integer in I.

Answer 2

Python 2, 153 bytes

from random import*
k,t=input()
E=[0]*k
L=E+[0]
def g(i,x=0):y=E[i];E[i]=y&x^x;return y and-~g(i-1)+g(-~i%k)
exec"L[g(randrange(k),1)]+=1;"*t
print L[1:]

Turns out I had almost the same solution as Fry's, but with a bit more bit fiddling.

• FryAmTheEggman: Wow I had actually looked at randrange, but I didn't realize it worked with only one argument. Nice work!

Answer 3

Java, (削除) 278 (削除ここまで) 272 bytes

Java isn't the best Golf language, and I'm not the best golfer, but it was a lot of fun to write so here it is! Let me know about bugs and improvements! (I decided to resubmit as just a function.)

void e(int k, int t){int[]d=new int[k],b=d.clone();for(;t-->0;){int m=0,q=(int)(Math.random()*k),i=q,h=1,f=0;d[q]++;if(d[q]>1){for(;;){if(i<0){i=k-1;h=-1;}if(d[i%k]>0){m++;d[i%k]=0;}else{if(f>0)break;h*=-1;i=q;f=1;}i+=h;}b[m-1]++;}}System.out.println(Arrays.toString(b));}

And the file with spaces and comments:

void e(int k, int t){
 int[]d=new int[k],b=d.clone(); //b is the record, d is the map 
 for(;t-->0;){ //do time steps //q is the spot
 int m=0,q=(int)(Math.random()*k),i=q,h=1,f=0; 
 //m-magnitude,i spot examining, h moving index, f change counter
 d[q]++; //add the energy
 if(d[q]>1){ //double energy, quake here 
 for(;;){ //shorthand while true
 if(i<0){ //i has wrapped negative, need to start a left hand search from the end now
 i=k-1; //Start at the end
 h=-1; //Left handed search
 }
 if(d[i%k]>0){ //is the spot energetic and set off
 m++; //add one to the mag counter
 d[i%k]=0; //remove energy
 } else { //it's a non active spot so we need to flip search direction
 if(f>0) break; //we've already flipped once, break
 h*=-1; //flip the direction now
 i=q; //reset the spot we look at to the epicenter
 f=1; //add one to the flip counter
 }
 i+=h; //add the search increment to the spot we look at
 }
 b[m-1]++; //update the mag record
 }
 }
 System.out.println(Arrays.toString(b)); //print it out
 }

• mbomb007: If you could tab the comments out a bit in the 2nd program, that might help with readability. Thanks. (Use Alt+09, or tab it out in Notepad++)
• Compass: d[q]+=1; this can become d[q]++; you can increment directly on arrays instead of using += everywhere. That should save a bunch of characters.
• Compass: Also: for(;t>0;t--){ can be changed to for(;t-->0;){ :D
• Geobits: Congrats on your first golf here! :D Now.... by just rearranging the declarations a bit and returning (instead of printing) the result, you can get this down quite a bit. There might be more to be done, but I have to go. Here's a 244 byte version: pastebin.com/TWAXvyHW

Answer 4

Python 2, (削除) 174 (削除ここまで) 170

from random import*
k,t=input()
D=[0]*k
E=D+[0]
def U(x):b=D[x];D[x]=0;return b and-~U(x-1)+U(-~x%k)
for x in[0]*t:r=randint(0,k-1);e=U(r);E[e-1]+=1;D[r]=e<1
print E[:-1]

Thanks @Vioz for finding a shorter way to make D, and proving again that not is usually golfable. And also for writing the explanation.

I had tried to make a similar program in Pyth, but there seems to be a scope issue in what I was trying to do. This pretty naively implements the dominoes and the function U propagates earthquakes. The subtraction direction in U doesn't need a mod because it will wrap around naturally. The last element of E counts the number of times a zero is turned into a one, so it is not printed at the end.

Ungolfed + Explanation:

from random import*
k,t=input() # Takes input in form k,t
D = [0]*k # Empty array of size k is made for
 # performing the simulation.
E = D+[0] # Empty array of size k+1 is made for
 # storing the magnitudes.
def U(x): # Define a function U that takes an int x
 b = D[x] # Assign b to the value at x in D
 D[x] = 0 # Clear the value at x in D
 return b and U(x-1)+1 + U((x+1)%k) # Return the sum of U(x-1)+1 and U((x+1)%k)
 # if b is a 1.
for x in[0]*t: # Perform t tests
 r=randint(0,k-1) # Generate a random number between 0 and k-1
 e=U(r) # Assign e to the value of U(r)
 E[e-1]+=1; # Increment the magnitude array at position
 # e-1
 D[r] = e<1 # Set D[r] to be 1 if no earthquake happened.
print E[:-1] # Print the magnitude list

• Kade: Changing D[r]=not e to D[r]=e<1 saves 2 bytes, and E=[0]*-~k to E=D+[0] saves another 2, to get you down to 170.

Answer 5

Pyth, 48 bytes

Km0QJsM.u?<+vM.sjkZ1円KQe=Z.>NOQ+PZ1vwKm/-VJtJhdQ

Got a little bit inspired by @Dennis's explanation. Had some similar thoughts yesterday, but didn't really follow them.

Try it online: Demonstration

Explanation:

 implicit: Q is the first input number
 m0Q create a list with Q zeros
K store the list in K
 .u vwK apply the following expression eval(input) times, 
 start with N = K:
 .>NOQ shift N by a random integer of [0, ..., Q-1]
 =Z store the result in Z
 ? e Z if the last digit == 1:
 jkZ convert Z to string
 .s 1円 remove "1"s from the start and end
 vM convert to list of integers
 + K add K (adds a bunch of zeros)
 < Q correct size (take the first Q elements)
 implicitly update N with this result
 else:
 PZ all but last of Z
 + 1 append 1
 implicitly update N with this result
 .u gives all the intermediate states
 sM sum each list
J store in J
m/-VJtJhdQ
m Q map each d in [0, 1, ..., Q-1] to:
 -VJtJ vectorized minus between J and J[1:]
 / hd count d+1 in ^
 implicitly print

Answer 6

ES6, (削除) 224 (削除ここまで) (削除) 196 (削除ここまで) (削除) 189 (削除ここまで) (削除) 179 (削除ここまで) 172

The easy stuff has been golfed, but still some work to do. I'll type out an explanation later. Also, if someone can tell me why the short new Date%k thing doesn't work so well anymore, that'd be swell.

f=(k,t)=>{a=Array(k).fill(0);o=a.slice(0);for(;t--;){c=0;r=Math.random()*k|0;if(a[r]){for(d=r+1;d<k&a[d];c++)a[d++]--;for(d=r-1;d&a[d];c++)a[d--]--;o[c]++};a[r]^=1}return o}

Usage is

f(10, 1000);

• Optimizer: You can remove the new . You don't need that t in the for loop, No need of that last two ;
• Compass: @Optimizer you are hero to cause
• Optimizer: a[r]^=1 will defs work if initial value is either 1 or 0

Answer 7

Perl, 212

The previous version I had put up was not correctly wrapping, and implementing that took some work.

sub f{sub n{$i=($i+$d)%($#a+1)}($k,$t)=@_;@L=@a=(0)x$k;for(1..$t){$i=$x=int rand($k);if(++$a[$x]>1){$d=1;my%z;for(;;){$z{$i}=1;n;if(!$a[$i]){$d*=-1;n}last if($d>0&&$i==$x)}@z=keys %z;@a[@z]=(0)x@z;++$L[$#z]}}@L}

This is probably not the right algorithm for this, but I can't think right now. The ungolfed version is below.

Ungolfed:

sub f {
 # n() implements the iterator, so that each time it is called a
 # global index is incremented or decremented correctly wrapping
 # around
 sub n { $i = ($i + $d) % ($#a + 1) }
 # Receive input
 ($k, $t) = @_;
 # Initialise the array for earthquake magnitudes an the fault
 # line
 @L = @a = (0) x $k;
 for(1..$t){
 # Assign a random integer value to two control variables
 # $i is used for moving along the fault, and $x to remember
 # the initial value
 $i = $x = int rand($k);
 # The corresponding value in the fault line is incremented,
 # and earthquakes detected
 if(++$a[$x]>1){
 # Earthquake!
 # To propagate the earthquake, we move along the fault 
 # bouncing on unactivated nodes. We stop when we've covered
 # the entire activated block.
 # $d tracks the direction (initially forward);
 $d = 1;
 # %z keeps the indeces of known activated nodes
 my %z;
 for(;;){
 $z{$i} = 1; # Read current node
 n; # Move head
 if (!$a[$i]) { # If next one is deactivated
 $d *= -1; # change direction
 n # and move the head (bounce!)
 }
 # If we've reached the beginning, and we're moving
 # forward we've covered the entire activated block
 last if ($d > 0 && $i == $x);
 }
 # Deactivate all consecutive activated nodes
 @z = keys %z;
 @a[@z] = (0) x @z;
 # And store the magnitude of the earthquake
 ++$L[$#z];
 }
 }
 # Return list of magnitudes
 @L
}
print join ' ', f(15, 1000), "\n";

Answer 8

CJam, 76 bytes

l~_0a*:R@{1$mr_2$={W@@[W1]{{_@0t@)\@K+_2$=}g2$+)}fK;\(_R=)R\t:R;}{1t}?}*;;Rp

Well, this is not very competitive. But since it took me long enough, I thought I'd post it anyway.

l~ Get input.
_0a* Initial bit pattern, list of k zeros.
:R Save away the list of zeros, will be used for histogram.
@{ Pull number of tries to top of stack, and start main loop.
1$mr Generate random position in range 0 to k-1.
_2$ Duplicate current pattern and position.
= Get current value of bit at position.
{ Start if statement. This is the block for bit value 1.
W@@ Create initial count of 1 bits in quake, and push it down the stack.
[W1]{ Start for loop over value [-1 1], the two increments for going left/right.
{ Start while loop that proceeds as long as 1 bits are found.
_@0t Set current value of bit to 0.
@) Get current bit counter to top of stack, and increment it.
\@ Pull list and bit position back to top of stack.
K+ Increment/decrement bit position.
_2$= Get value at new bit position.
}g End of while loop over 1 bits.
2$+) Restore position to get ready to move in opposite direction.
}fK End for loop over left/right increment.
;\(_ Pull counter of 1 bits in quake to top of stack.
R= Get current value in histogram,
) increment it,
R\t:R and store it back in the histogram.
;} End of if branch for 1 bit.
{1t}? Else branch of if. For 0 bit, simply set it.
}* End main loop.
;;Rp Clean up stack and print histogram.

Try it online