Digital Cellular Automata

Question

Write a program or function that takes in an odd positive integer N and a string of decimal digits (0123456789). The string represents a ten-state one-dimensional cellular automaton. Each digit occupies one cell and the update rule from one generation to the next is that every cell becomes the digit resulting from the sum of the N cells centered on the cell, modulo 10.

The first and last cells wrap around as if neighbors, so cells can always have N cells centered on them. Note that N may be larger than the length of the string, which means it could wrap around multiple times and some digits will accordingly be in the sum multiple times.

As an example, if N is 7 and the string is 038, to visualize the cells to sum we can write 038 repeating infinitely in both directions

...038038038038038...

then the digit that the 0 will change into is the sum of the 7 digits centered around any 0, modulo 10:

...038038038038038...
      ^_____^
         |
    sum all these

This is (0+3+8+0+3+8+0)%10, which is 2.

Similarly the digits the 3 and 8 change into are defined by (3+8+0+3+8+0+3)%10 = 5 and (8+0+3+8+0+3+8)%10 = 0 respectively.

Thus, the generation after 038 is 250 when N is 7.

Your program or function needs to print or return the digit string of the very next generation of the input digit string. i.e. apply the update rule once to each cell and give the output. The shortest code in bytes wins.

Test Cases

[digit string] -> [N = 1], [N = 3], [N = 5], [N = 7], [N = 9], [N = 43]
0 -> 0, 0, 0, 0, 0, 0
1 -> 1, 3, 5, 7, 9, 3
2 -> 2, 6, 0, 4, 8, 6
3 -> 3, 9, 5, 1, 7, 9
4 -> 4, 2, 0, 8, 6, 2
5 -> 5, 5, 5, 5, 5, 5
6 -> 6, 8, 0, 2, 4, 8
7 -> 7, 1, 5, 9, 3, 1
8 -> 8, 4, 0, 6, 2, 4
9 -> 9, 7, 5, 3, 1, 7
00 -> 00, 00, 00, 00, 00, 00
07 -> 07, 47, 41, 81, 85, 47
10 -> 10, 12, 32, 34, 54, 12
11 -> 11, 33, 55, 77, 99, 33
12 -> 12, 54, 78, 10, 34, 54
34 -> 34, 10, 78, 54, 12, 10
66 -> 66, 88, 00, 22, 44, 88
80 -> 80, 86, 46, 42, 02, 86
038 -> 038, 111, 294, 250, 333, 472
101 -> 101, 222, 343, 545, 666, 989
987 -> 987, 444, 901, 765, 222, 543
1234 -> 1234, 7698, 3412, 9876, 1234, 7698
26697 -> 26697, 54128, 00000, 56982, 84413, 54128
001002 -> 001002, 211122, 331332, 335334, 455544, 113112
129577020 -> 129577020, 326194923, 474081605, 961120291, 333333333, 183342413
6023845292173530 -> 6023845292173530, 6853571632015189, 1197228291289874, 9238433109901549, 0110956118726779, 1982123699138828

Answer 1

Pyth, 20 19 bytes

1 byte thanks to @FryAmTheEggman.

sm`esmv@z-+dk/Q2Qlz

Try it online. Test suite.

Answer 2

CJam, 21 bytes

l~_,\2/f-l:~fm>:.+Af%

Test it here.

Explanation

l~   e# Read and evaluate N.
_,   e# Duplicate and turn into range [0 1 ... N-1]
\2/  e# Swap with other copy and (integer) divide by 2.
f-   e# Subtract this from each element in the range to get
     e# [-(N-1)/2 ... -1 0 1 ... (N-1)/2]
l:~  e# Read string and evaluate each digit separately.
fm>  e# Make one copy of the result for each element i in the range, shifting the array
     e# i cells to the right, cyclically.
:.+  e# Sum the columns of the resulting matrix.
Af%  e# Take each of those sums modulo 10.

Answer 3

Mathematica, 85 bytes

""<>ToString/@CellularAutomaton[{Tr@#~Mod~10&,{},#/2-1/2},FromDigits/@Characters@#2]&

Answer 4

Python 3, 114 92 86 80 bytes

Took off 6 bytes thanks to Sp3000 and another 6 bytes thanks to xnor!

a=lambda N,D,i=0:D[i:]and str(int((D*N)[(i-N//2)%len(D):][:N],11)%10)+a(N,D,i+1)

Defines a named function a that takes N and D as parameters, the N and digit string defined in the challenge.

Explanation

In Python 3, and between two strings will end up being the latter. Hence, D[i:]and ... short-circuits once all center positions have been iterated over as D[i:] will be an empty string and therefore falsy. (D*N)[(i-N//2)%len(D):][:N] duplicates the digit string a bunch of times, then slices it in the right places to give the substring that has the correct digit as the center. Recall for a moment that the sum of the digits of a base 10 number modulo 9 is the same as the number itself modulo 9. str(int(...,10)%10) treats the resulting number-string as if it was base 11 and gets the remainder modulo 10, then converts back to string. Finally, a(N,D,i+1) moves on to the next center position. Because of the +, once the recursion is done, all of the resulting digits are lumped together and returned.

Answer 5

Haskell, 92 bytes

String conversion is really expensive in Haskell...

x!n=last.show.sum.map(read.pure).take n.(`drop`cycle x).fst<$>zip[div(1-n)2`mod`length x..]x

This defines an infix function !, used as follows:

> "1234"!3
"7698"

Explanation

On the right we have [div(1-n)2`mod`length x..], which is just the infinite list of integers starting from (1-n)/2 modulo length(x) (we take the modulus, since we want the first element to be non-negative). These correspond to the starting indices of the CA neighborhoods. We zip it with x just to obtain a list of the correct length.

The function <$> is the infix version of map, and its left argument is a function composition read from right to left. Thus for each integer in the above list (extracted with fst), we drop that many characters from cycle x (which is the concatenation of infinitely may copies of x), take n characters from the remainder, convert them to strings and then integers with read.pure, take their sum, convert that to string with show, and take the last character of that, which corresponds to the remainder mod 10.

Answer 6

NARS2000 APL, 37 characters (72 bytes)

⎕←10⊥10∣+⌿⊃({⍵..-⍵}⌊⎕÷2)∘.⌽⊂49-⍨⎕AV⍳⍞

Explanation:

  ⎕←10⊥10∣+⌿⊃({⍵..-⍵}⌊⎕÷2)∘.⌽⊂49-⍨⎕AV⍳⍞
⍝ ⎕←                                    output
⍝   10⊥                                 the base-10 digits in
⍝      10∣                              the modulo-10
⍝         +⌿                            column-wise sum of
⍝           ⊃                           the matrix version of
⍝                         ∘.⌽           the outer-product rotation of
⍝                            ⊂            the scalar version of
⍝                                 ⎕AV⍳    the index in the atomic vector of
⍝                                     ⍞   an input string
⍝                             49-⍨        minus 49 ('0' + 1)
⍝                                       by
⍝             {⍵..-⍵}                     the range ⍵ to -⍵, where ⍵ is
⍝                    ⌊                    the floor of
⍝                     ⎕                   an input integer
⍝                      ÷2                 divided by 2

Answer 7

Octave, 64 bytes

@(s,n)["" mod(sum(bsxfun(@shift,s'-48,(1:n)-ceil(n/2))'),10)+48]

Answer 8

J, 41 bytes

"."0@]{~(1":10|+/@:)#@]|-:@<:@[-~(+/&i.#)

Turned out longer than I expected. Should be golfable.

We generate a matrix with elements in a row showing the positions whose values should be added (mod 10) to get sum for a position.

Usage:

   7 ("."0@]{~(1":10|+/@:)#@]|-:@<:@[-~(+/&i.#)) '038'
250

Try it online here.