title: Diamondize a Matrix

text:
# Question
Title: Diamondize a Matrix
Given a matrix, output a representation of the matrix where the top left element is on top, the anti-diagonal is the central row and the bottom right element is at the bottom.

For example, consider the following matrix:

```
1 2 3
4 5 6
7 8 9

```

The diamond version of this matrix is:

```
  1
 4 2
7 5 3
 8 6
  9

```

### Inputs and outputs

An input matrix will be given as a list of lists (or anything similar in your language of choice). The output shall be a list of lists as well.

The matrices will only contain positive integers.

The input matrix will not necessarily be square.

The input matrix will be at least 1×1.

### Test Cases

```
Input:  [[1]]
Output: [[1]]

Input:  [[1,2],[3,4]]
Output: [[1],[3,2],[4]]

Input:  [[1,2,3],[4,5,6]]
Output: [[1],[4,2],[5,3],[6]]

Input:  [[11,2,5],[3,99,3],[4,8,15],[16,23,42]]
Output: [[11],[3,2],[4,99,5],[16,8,3],[23,15],[42]]

```

### Scoring

This is , so the shortest answer in bytes wins.

# Answer
## J, 6 bytes

```
<@|./.

```

This is an unnamed a monadic verb which takes a matrix and returns a list of antidiagonals:

```
   input =. i.3 4
   input
0 1  2  3
4 5  6  7
8 9 10 11

   <@|./. input
┌─┬───┬─────┬─────┬────┬──┐
│0│4 1│8 5 2│9 6 3│10 7│11│
└─┴───┴─────┴─────┴────┴──┘

```

Test it here.

### Explanation

* `/.` is J's built-in to apply a function to each anti-diagonal. Unfortunately, these anti-diagonals are given in the opposite order of what we want here.
* In `<@|.`, we first apply `|.` which reverses the anti-diagonal and then `<` to box it (which is the only way to return a ragged array in J, since normal arrays are always rectangular, so the antidiagonals would be padded with zeroes).
> 21 votes

# Answer
# Python, 91 bytes

```
e=enumerate
lambda M:[[r[n-i]for i,r in e(M)if-1<n-i<len(r)][::-1]for n,_ in e(M[1:]+M[0])]

```

Test it on Ideone.

---

# Python + NumPy, 69 bytes

```
import numpy
lambda M:map(M[::-1].diagonal,range(1-len(M),len(M[0])))

```

Expects a 2D NumPy array as input and returns a list of NumPy arrays. Test it on Ideone.
> 6 votes

# Answer
## Jelly, 7 bytes

```
ṚŒDṙZL$

```

Try it online!

### Explanation

```
Ṛ         Reverse the matrix vertically.
 ŒD       Get its diagonals. However these start from
          the main diagonal, not the corners.
    ZL$   Get the width of the input matrix.
   ṙ      Rotate the list of diagonals left by that many
          places to obtain the correct order.

```
> 5 votes

# Answer
# Mathematica, ~~58~~ 56 bytes

```
a=Length;Reverse@#~Diagonal~b~Table~{b,1-a@#,a@#&@@#-1}&

```

Anonymous function, takes nested arrays.
> 5 votes

# Answer
## CJam, 17 bytes

```
{eeSf.*::+W%zSf-}

```

An unnamed block (function) which expects the matrix on the stack and replaces it with its antidiagonals.

Test it here.

This (found by Sp3000) works for the same byte count:

```
{_,,Sf*\.+W%zSf-}

```

### Explanation

This is best explained with an example. Consider the input:

```
[[0  1  2  3]
 [4  5  6  7]
 [8  9 10 11]]

ee    e# Enumerate matrix, turning each row [x ... z] into [i [x ... z]] where
      e# i is the vertical index from the top.

[[0 [0  1  2  3]]
 [1 [4  5  6  7]]
 [2 [8  9 10 11]]]

Sf.*  e# Replace each i with a string of i spaces.

[[""   [0  1  2  3]]
 [" "  [4  5  6  7]]
 ["  " [8  9 10 11]]]

::+   e# Prepend these strings to the rows.

[[0  1  2  3]
 ['  4  5  6  7]
 ['  '  8  9 10 11]]   e# Note that each '  corresponds to a space character.

W%    e# Reverse the rows.

[['  '  8  9 10 11]
 ['  4  5  6  7]
 [0  1  2  3]]

z     e# Zip/transpose.

[[ '  '  0]
 [ '  4  1]
 [ 8  5  2]
 [ 9  6  3]
 [10  7]
 [11]]

Sf-   e# Remove spaces from each row.

[[ 0]
 [ 4  1]
 [ 8  5  2]
 [ 9  6  3]
 [10  7]
 [11]]

```
> 4 votes

# Answer
## Python 2, ~~88~~ 87 bytes

```
lambda L:[filter(None,x)[::-1]for x in map(None,[],*[i*[0]+r for i,r in enumerate(L)])]

```

Prepend 0s, zip, then remove falsy elements. Returns a list of tuples. This uses `map(None,...)` to perform `zip_longest` (padding missing spots with `None`) and `filter(None,...)` to remove falsy elements.

Annoyingly, we need to add an extra `[]` row to the `map` to guarantee that a list of tuples is returned, since `map(None,*[[1]])` returns `[1]` rather than `[(1,)]` for a 1x1 matrix. The extra row gets stripped out by the `filter` though.

*(Thanks to @Dennis for -1 byte)*
> 4 votes

# Answer
# Ruby, ~~68~~ 66 bytes

Anonymous function.

```
->l{i=-1;k=[];l.map{|r|i-=j=-1;r.map{|e|k[i+j+=1]=[e,*k[i+j]]}};k}

```
* Because of how the splat operator works, I was able to save 2 bytes by forgoing the array addition.
> 4 votes

# Answer
# JavaScript (Firefox), ~~86~~ 75 bytes

```
a=>a.concat(a[0]).slice(1).map((_,i)=>[for(v of a)if(n=v[i--])n].reverse())

```

*Saved 11 bytes thanks to @Neil!*

Works in Firefox 30+. Takes an array of arrays.
> 3 votes

# Answer
# Husk, ~~3~~ 2 bytes

```
∂T

```

-1 byte thanks to *@mypronounismonicareinstate*.

Try it online.

**Explanation:**

```
 T  # Transpose the (implicit) matrix-argument; swapping rows/columns
∂   # Take the anti-diagonals of this transposed matrix
    # (after which the result is output implicitly)

```
> 3 votes

# Answer
# Prolog (SWI), 111 bytes

```
A*B*C:-append(A,B,C).
s(A,B,C):-A*[B]*C.
N+B:-N=[A|X],X+R,Z*Q*R,maplist(s,[[]|Z],A,Y),Y*Q*B,!;maplist(=([]),B).

```

Try it online!

## Explanation

Let's first look a version of the code that not nearly so condensed.

```
snoc(Init,Last,List) :-
  append(Init,[Last],List).

diamondize([],Soln) :-
  maplist(=([]),Soln).
diamondize([FirstRow|Rest],Soln):-
  diamondize(Rest,RestSoln),
  append(BeginRestSoln,EndSoln,RestSoln),
  maplist(snoc,[[]|BeginRestSoln],FirstRow,BeginSoln),
  append(BeginSoln,EndSoln,Soln),
  !.

```

The `diamondize/2` predicate (`+/2` in the golfed version) is responsible for calculating what the diamond version of the input matrix is. The predicate works recursively as follows: first it calculates the diamond version of the input matrix with its first row removed (`diamondize(Rest,RestSoln)`); then to calculate the diamond version of the entire input matrix it uses the fact that adding an initial row changes the diamond version by prepending a singleton list of the first element of the initial row and then pairing up each remaining element in the initial row with the first however many lists in the diamond and adding each initial row element to the end of its paired list, leaving the remaining lists in the diagonal unchanged. To do this in Prolog I use `append` to split `RestSoln` into a beginning, `BeginRestSoln`, and an end, `EndSoln`. Then I use the the builtin `maplist/4` to assert a relation between `BeginRestSoln`, the new initial row, `FirstRow`, and a new list `BeginSoln`. The `maplist/4` predicate asserts that all triples of elements of equal indices from the lists in its second, third, and fourth arguments will satisfy the predicate given as its first argument when it is called on them (note that this requires all the lists given as arguments to be of equal length). The predicate I use is `snoc/3` which asserts that when its second argument is added to the end of the list in its first argument, you get its third argument. Furthermore I add an empty list to the start of `BeginRestSoln` which means that when I `snoc` that with the first element of `FirstRow` the resulting first element of`BeginSoln` will be a singleton list of that aforementioned first element. The rest of `BeginSoln` will be the lists that began the diagonal version of the remainder of the matrix with the remaining elements of the first row added to the end, just as desired in the process described above. Finally to get the solution for the entire matrix we append `BeginSoln` with the unchanged `EndSoln`.

We have now covered the behavior of `diamondize/2` when the matrix is not empty, but the base case is the empty matrix. In that case the "solution" is considered to be a list of some undetermined length with `[]` for all its elements. This list is constructed using the `maplist/2` predicate which asserts that each element of the list given in its second argument satisfies the predicate given in its first argument. The predicate we use is `=([])/1` which is the partially applied `=/2` predicate which asserts that its two arguments unify, so our partially applied version asserts that its singular argument unifies with (ie is equal to) the empty list. However, since we do not specify a length, Prolog will attempt to satisfy the future goals with the shortest list containing only empty lists, backtracking and trying a longer such list if the future goals can't be satisfied. This behavior is very useful since in our first inductive case the predicates won't be satisfied unless the previous solution is at least one less than the length of the rows of the matrix, but we run into an issue in that longer lists of empty lists would also result in solutions that the program would consider valid, but would be invalid for this challenge. To avoid producing these solutions, we add a cut (`!`) to the end of the recursive case of `diamondize/2`, which will tell Prolog not to backtrack once we have a working solution.

Finally to golf the whole thing I used a number of tactics. First off, of course we can eliminate excess whitespace, and give variables and predicates shorter names. Then since `append/3` is being used a lot I can save a couple bytes by creating a copy of it with a shorter name, using an operator to name both it and what was the `diamondize/2` predicate (unfortunately since operator predicates technically can have at most two arguments, I cannot give `s/3` an operator name since I need to pass it to `maplist/4`). Finally I can consolidate the two cases of `+/2` into a single case with a disjunction.
> 3 votes

# Answer
## Mathematica, 60 bytes

```
#&@@@#&/@GatherBy[Join@@MapIndexed[List,#,{2}],Tr@*Last]&

```

where  is a Unicode character which Mathematica reads as the postfix `\[Transpose]` operator.

This is a bit longer than the other Mathematica solution but I figured I'd post it because it doesn't use the `Diagonals` built-in and uses a completely different approach.

### Explanation

```
MapIndexed[List,#,{2}]

```

This first transposes the matrix (such that the antidiagonals appear in the correct order if the matrix was flattened). Then we map `List` over the cells of the matrix together with the index, which turns each matrix element `i` into `{i, {x, y}}` where `x` and `y` are the coordinates of the element in the matrix.

```
Join@@...

```

This flattens the outermost dimension, so that we now have a flat list of the matrix elements (with their coordinates) in column-major order.

```
GatherBy[..., Tr@*Last]

```

This groups those elements by the sum of their coordinates. Note that antidiagonals are lines of constant `x+y`, so this does exactly the grouping we want. The order within each group is preserved. Now we just need to get rid of the coordinates again. This is done via the rather cryptic:

```
#&@@@#&/@...

```

This maps the function `#&@@@#&` over each group, which itself *applies* `#&` to each element in the group, and `#` is simply the first argument, i.e. the original matrix element.
> 2 votes

# Answer
# Octave, 77 bytes

With a little abuse of the `accumarray` function:

```
@(M)char(accumarray(((1:size(M,1))+(0:size(M,2)-1)')(:),M(:),[],@(x){num2str(x')}))

```

This defines an anonymous function. To use it, assign to a varible or use `ans`.

Input is the matrix with `:` as row separator. Output is a cell array containing an array for each row (Octave's equivalent to jagged arrays). This is displayed by Octave showing the indices of the cell array and the contents of each cell. Try it here.

To display the result separated by spaces and newlines only: **83 bytes**

```
@(M)char(accumarray(((1:size(M,1))+(0:size(M,2)-1)')(:),M(:),[],@(x){num2str(x')}))

```

You can also try it here.
> 2 votes

# Answer
# Octave, ~~63~~ 62 bytes

Removed one byte thanks to ~~@DonMue...~~ @LuisMendo!

```
@(a)cellfun(@(x)x(x>0)',num2cell(spdiags(flipud(a)),1),'un',0)

```

I went the boring route and munged the antidiagonals.

Sample run on ideone.
> 2 votes

# Answer
# Haskell, ~~83~~ 82 bytes

```
r=zip[0..]
\o->fst$span(any(>0))[reverse[e|(x,t)<-r o,(v,e)<-r t,x+v==a]|a<-[0..]]

```

nimi saved a byte. Thanks!
> 2 votes

# Answer
# \[C#\], 100 bytes

```
for(r=0;r<l;r++)for(c=0;c<i[r].Length;c++)o[c+r]=o[c+r]?.Prepend(i[r][c]).ToArray()??new[]{i[r][c]};

```

Try It online!

Maybe there's a shorter way of inserting elements. Prepend and ToArray seems verbose, but that's the best I found.
> 2 votes

# Answer
# Haskell, 56 bytes

```
a!b=zipWith(++)([]:b)$a++repeat[]
foldr1(!).map(pure<$>)

```

Try it online!
> 2 votes

# Answer
# BQN, 11 bytes

```
⌽¨+´¨∘↕∘≢⊸⊔

```

Anonymous tacit function. Takes a 2D array and returns a list of lists. Try it at BQN online!

### Explanation

```
⌽¨+´¨∘↕∘≢⊸⊔
        ≢     Get the shape of the array (a list of two integers)
      ↕∘      Range (a 2D array of coordinate pairs)
  +´¨∘        Sum each of those pairs
              We now have an array in which the top left element is 0, the two elements
              in the next antidiagonal are 1, and so forth
         ⊸    With that as left argument and the original array as right argument,
          ⊔   Group the values of the right argument into buckets based on the
              corresponding number in the left argument
⌽¨            Reverse each antidiagonal

```
> 2 votes

# Answer
# Pip, 19 bytes

```
_RMxMZD:xRL_AL BMEa

```

Try It Online!

I'm a bit rusty. There might be a shorter way to do this with loops but oh well.

```
                ME  # Map [index item] for each item of...
                  a # Input
        --------ME  # Block
         RL         # Repeat...
        x           # The empty string
           _        # By the index
            AL      # Concatenate to...
               B    # The item
     ZD:            # Transpose, filling with ""
----M               # Map over each...
_RM                 # Remove
   x                # The empty string

```
> 2 votes

# Answer
# Python, 128 bytes (numpy)

```
(lambda A: (lambda A,S:[[A[U][I-U] for U in range(min(S[1]-1,I),max(I-S[0]+1,0)-1,-1)] for I in range(S[1]+S[0]-1)])(A,A.shape))

```
> 1 votes

# Answer
# Pyth, ~~41~~ 17 bytes

```
tm_<dx+dYk.T+LaYk

```

Try it online!

Inspired by @Doorknob's solution to another problem.

How it works:

```
tm_<dx+dYk.T+LaYk
            +L      prepend to each subarray...
              aYk   (Y += ''). Y is initialized to [],
                    so this prepends [''] to the first
                    subarray, ['', ''] to the second, etc.
                    ['' 1  2  3
                     '' '' 4  5  6
                     '' '' '' 7  8  9
                     '' '' '' '' 10 11 12
                     '' '' '' '' '' 13 14 15]
          .T        transpose, giving us
                    ['' '' '' '' ''
                     1  '' '' '' ''
                     2  4  '' '' ''
                     3  5  7  '' ''
                     6  8  10 ''
                     9  11 13
                     12 14
                     15]
 m_<dx+dYk          removes all empty strings in the
                    subarrays while reversing each one
t                   remove the first subarray

```

---

Previous attempt:

```
JlQKlhQm_m@@Qk-dk}h.MZ,0-dtKh.mb,tJdUt+JK

```

Try it online!

How it works:

```
JlQKlhQm_m@@Qk-dk}h.MZ,0-dtKh.mb,tJdUt+JK    input array stored as Q
JlQ                                          J = len(Q)
   KlhQ                                      K = len(Q[0])
       m                            Ut+JK    list for d from 0 to J+K-1:
        _m       }AAAAAAAAAABBBBBBBB             reversed list for k from A to B, where:
                  h.MZ,0-dtK                       A = max(0, d-(K-1))
                       0-dtK                               0  d-(K-1)
                            h.mb,tJd               B = min(J-1, d)
                                 tJd                       J-1  d
          @@Qk-dk                                    Q[k][d-k]

```
> 1 votes

# Answer
# Groovy, 77 73 75

```
{i->o=[].withDefault{[]};a=0;i.each{b=0;it.each{o[a+b++].add(0,it)};a++};o}

```

Takes array of arrays as input and returns array of arrays.

Try it

EDIT: I forgot to output the anwser, after adding it score goes up to 75.
> 1 votes

# Answer
# APL (Dyalog Unicode), 78 bytes

```
{{⍵/⍨×≢¨⍵}{⍵/⍨×⍵}¨↓⍉(-⍳≢⍵)⌽⍵↑⍨1 2×≢⍵}

```

Try it online!
> 1 votes

# Answer
# Perl 5, 67 bytes

```
sub{map{[grep$_,map{shift@{$_[-$_]}}-$_..0]}0..$#_,($#_)x$#{$_[0]}}

```

Try it online!
> 1 votes

# Answer
# 05AB1E (legacy), ~~17~~ 16 bytes

```
εD0*«NFÁ]øí0δKʒOĀ

```

Unfortunately 05AB1E only has a builtin for the main (anti)diagonal, and not one for all (anti)diagonals, so we'll have to do things manually..

-1 byte by switching to the legacy version of 05AB1E, so the `0δK` can be `0K`.

Try it online or verify all test cases.

**Explanation:**

```
ε        # Map each row in the (implicit) input-matrix to:
 D       #  Duplicate the current row
  0*     #  Multiply each by 0, so we have a list of 0s the same length of the row
    «    #  Append the lists together
         #   i.e. [[1,2,3],[4,5,6],[7,8,9]] → [[1,2,3,0,0,0],[4,5,6,0,0,0],[7,8,9,0,0,0]]
     NF  #  Loop the (0-based) map-index amount of times:
       Á #   And rotate the row with appended 0s once towards the right each iteration
         #    → [[1,2,3,0,0,0],[0,4,5,6,0,0],[0,0,7,8,9,0]]
]ø       # After the map and inner loop: zip/transpose; swapping rows/columns
         #  → [[1,0,0],[2,4,0],[3,5,7],[0,6,8],[0,0,9],[0,0,0]]
  í      # And reverse each inner row
         #  → [[0,0,1],[0,4,2],[7,5,3],[8,6,0],[9,0,0],[0,0,0]]
0K       # Remove all 0s from each inner row
         #  → [[1],[4,2],[7,5,3],[8,6],[9],[]]
  ʒOĀ    # And filter out any empty rows
         #  → [[1],[4,2],[7,5,3],[8,6],[9]]
         # (after which the result is output implicitly)

```
> 0 votes

# Answer
# Japt, 11 bytes

Takes input as an array of space delimited strings, outputs a 2D array of integer strings.

```
ËiEç)¸ÃÕËÔf

```

Try it (header converts 2D arrays to the required input format) or run all test cases

```
ËiEç)¸ÃÕËÔf     :Implicit input of array
Ë               :Map each element at 0-based index E
 i              :  Prepend
  Eç            :    E spaces
    )           :  End prepend
     ¸          :  Split on spaces
      Ã         :End map
       Õ        :Transpose
        Ë       :Map
         Ô      :  Reverse
          f     :  Filter

```
> 0 votes

# Answer
# Vyxal, 22 bitsv2, 2.75 bytes

```
Þ`R

```

Try it Online!

Bitstring:

```
0010101000111101000010

```
> 0 votes

---
Tags: code-golf, array, matrix
---


title: The primitive circle problem

text:
# Question
Title: The primitive circle problem
# Challenge

The primitive circle problem is the problem of determining how many coprime integer lattice points \\$x,y\\$ there are in a circle centered at the origin and with radius \\$r \in \mathbb{Z}^+ \\$ such that \\$x^2+y^2 \le r^2 \\$. It's a generalization of Code-Golf: Lattice Points inside a Circle.

**Input**

Radius \\$r \in \mathbb{Z}^+\\$

**Output**

Number of coprime points

# Test Cases

Taken from sequence A175341 in the OEIS.

| Radius | Number of coprime points |
| --- | --- |
| 0 | 0 |
| 1 | 4 |
| 2 | 8 |
| 3 | 16 |
| 4 | 32 |
| 5 | 48 |

# Answer
> 10 votes
# JavaScript (ES6), 45 bytes

Based on A000089, the number of solutions to:

$$x^2+1\equiv 0 \pmod n$$

which allows to compute A304651 and eventually A175341.

```
f=(n,k=N=n*n)=>N&&4*(--k*k%N>N-2)+f(n,k||--N)

```

Try it online!

---

# C (gcc), 58 bytes

*-1 thanks to @ceilingcat*

The recursion is convenient in JS but otherwise really pointless. It is replaced with a single loop below.

```
k,N;f(n){for(k=N=n*n,n=0;N;k=k?:--N)n+=--k*k%N>N-2;k=4*n;}

```

Try it online!

# Answer
> 5 votes
# C (gcc), 63 bytes

```
f(m,r,n,x){for(r=n=0;n++<m*m;)for(x=n;x--;)r+=x*x%n>n-2;m=r*4;}

```

Try it online!

Port of @enzo's python answer (very surprised that it matches byte count with the python answer)

# Answer
> 5 votes
# Wolfram Language (Mathematica), 49 bytes

```
r4I~If[Abs@+##>r,Sign@r,#~#0~+##+#2~#0~+##]&~1

```

Try it online!

Counts edges of that star formed by the points in the first quadrant.

```
   I~                                       &~1   initial edge: 1-I
     If[Abs@+##>r,      ,                  ]      can this edge be split?
                         #~#0~+##+#2~#0~+##         yes: split the edge
                  Sign@r                            no: count if input≠0
  4                                               * 4 quadrants

```

# Answer
> 4 votes
# Python 3, ~~70~~ 63 bytes

```
lambda m:4*sum(x*x%n>n-2for n in range(m*m+1)for x in range(n))

```

Try it online!

* *-7 bytes* thank to Mukundan314 by removing the double sum and parenthesis

# Answer
> 3 votes
# Wolfram Language (Mathematica), 61 bytes

```
f[n_]=Sum[Boole[GCD[x,y]==1&&x^2+y^2<=n^2],{x,-n,n},{y,-n,n}]

```

Try it online!

# Answer
> 3 votes
# Google Sheets, 109 bytes

```
=iferror(4*sum(map(sequence(1,A2+1,0),lambda(x,map(sequence(A2),lambda(y,(1=gcd(x,y))*(x^2+y^2<=A2^2)))))),0)

```

Put the radius in cell `A2` and the formula in cell `C2`.

The formula creates a \\$(n+1)×n\\$ matrix for the upper right quadrant, excluding the \\$x\\$ axis (\\$y ≠ 0\\$). The matrix contains ones and zeros. The result is 4 times the sum of the matrix.

This would be much simpler to implement with an array formula, but unfortunately `gcd()` is an aggregating function that only gives one result per evaluation rather than a result matrix, so we need to test every lattice point separately.

# Answer
> 3 votes
# Wolfram Language (Mathematica), 53 bytes

```
(k=0;Do[k+=4Tr[1^PowerModList[-1,1/2,n]],{n,#^2}];k)&

```

Try it online!

# Answer
> 2 votes
# Jelly, 16 bytes

```
ŒRṗ2²S>ɗÐḟ²g/€ċ1

```

A monadic Link that accepts the non-negative integer* radius and yields the count of coprime lattice points in or on the circle of that radius centred at the origin.

**Try it online!**

### How?

```
ŒRṗ2²S>ɗÐḟ²g/€ċ1 - Link: non-negative integer, r
ŒR               - abs-range -> [-r..r]
  ṗ2             - Cartesian power {2}
                    -> LatticePoints of the enclosing, axis-aligned square
        Ðḟ       - filter discard those {LatticePoints} for which:
       ɗ  ²      -   last three links as a dyad - f(LatticePoint, r^2)
    ²            -     square {each coordinate of LatticePoint}
     S           -     sum {these}
      >          -     {that} greater than {r^2}?
           g/€   - reduce each {remaining LatticPoint} by GCD
              ċ1 - {that} count occurrences of one

```

* Also works for floats, up to floating-point errors, since while `ŒR` implicitly floors its input no lattice point will be in or on the circle if one of its coordinates is further out.

# Answer
> 2 votes
# PARI/GP, 54 bytes

```
f(n)=sum(x=-n,n,sum(y=-n,n,gcd(x,y)==1&&x^2+y^2<=n^2))

```

Attempt This Online!

# Answer
> 2 votes
# Desmos, 61 bytes

```

f(n)=4\sum_{a=0}^n\sum_{b=1}^n0^{\gcd(a,b)-1}\{aa+bb<=nn,0\}

```

Try It On Desmos!

Try It On Desmos! - Prettified

I really feel like this can be golfed but I can't really think of anything at the moment. I also have this other version without the piecewise but it is 62 bytes:

```
f(n)=4∑_{a=0}^n∑_{b=1}^n0^{gcd(a,b)-1}sgn(sgn(nn-aa-bb)+1)

```

# Answer
> 2 votes
# 05AB1E, 13 bytes

```
(Ÿn¬sãʒ¿}€O@O

```

Straight-forward modification (adding `ʒ¿}€`) of my 05AB1E answer for the related challenge.

Try it online or verify all test cases.

**Explanation:**

```
(             # Negate the (implicit) input-integer
 Ÿ            # Push a list in the range [(implicit) input,-input]
  n           # Square each inner value
   ¬          # Push the first item (without popping the list), which is input²
    s         # Swap so the list is at the top again
     ã        # Cartesian power of 2 to get all possible pairs
      ʒ }     # Filter this list of pairs by:
       ¿      #  Where the Greatest Common Divisor (gcd) of the pair is 1
              #  (note: only 1 is truthy in 05AB1E)
         €O   # Sum all remaining inner pairs together
              # (note: the `€` is only for n=0, so [] remains [], instead of becoming 0)
           @  # Check for each whether the input² is >= this value
            O # Sum to get the amount of truthy values
              # (which is output implicitly as result)

```

Try it online with step-by-step output lines.

# Answer
> 2 votes
# , 49 bytes

```
\(n)sum(sapply(1:n^2,\(a)4*sum(!((1:a)^2+1)%%a)))

```

Attempt This Online!

Uses the same OEIS chain A000089A304651A175341 as in @Arnauld's answer.

# Answer
> 2 votes
# Uiua 0.9.0, 21 bytes SBCS

```
×4/+≥⌵▽◰∩♭⊞⊃÷ℂ↘1.⇡+1.

```

Try on Uiua Pad! Takes \\$r\\$ as input and outputs the number of points

```
×4/+≥⌵▽◰∩♭⊞⊃÷ℂ↘1.⇡+1.
                 ⇡+1.  # push 0, 1, ... , r
              ↘1.      # push 1, 2, ... , r
          ⊞            # make tables of each possible pair (a,b)...
           ⊃÷ℂ         # with b/a and b+a*i
        ∩♭             # flatten both tables into lists
       ◰               # mask of unique quotients
      ▽                # apply mask to list of complex numbers
     ⌵                 # magnitudes
    ≥                  # test less than or equal to r
  /+                   # sum the number of such points
×4                     # multiply by 4

```

Created with the help of Luminespire.

# Answer
> 1 votes
# Retina, 96 bytes

```
.+
*_,$&*_,$&*
Lw`_+,_+,_*(?=_)
Am`^(__+)\1*,_+,\1*$
_+
$.&*$&
Cm`^(_+),\1(_*)(_*),\2$
.+
$.(4**

```

Try it online! Link includes test cases. Explanation:

```
.+
*_,$&*_,$&*

```

Create a list `[r, r, r]` (in unary).

```
Lw`_+,_+,_*(?=_)

```

Create  lists `[x=r..1, r, y=0..r-1]`.

```
Am`^(__+)\1*,_+,\1*$

```

Keep only the lists where `x` and `y` are coprime. (This particular implementation of the test assumes `x` is positive.)

```
_+
$.&*$&

```

Square `x`, `r` and `y`.

```
Cm`^(_+),\1(_*)(_*),\2$

```

Count (in decimal) the number of lists where `x²+y²<=r²`.

```
.+
$.(4**

```

Multiply by `4`.

# Answer
> 1 votes
# Charcoal, 19 bytes

```
Ｉ×⁴ΣＥ⊕ＸＮ²№Ｅι﹪⊕Ｘλ²ι⁰

```

Try it online! Link is to verbose version of code. Explanation: Uses the formulae from OEIS, `A175341(n)=A304651(n²)=4ΣA000089(n²)`.

```
       Ｎ            Input `n` as an integer
      Ｘ             Raised to power
        ²           Literal integer `2`
     ⊕              Incremented
    Ｅ               Map over implicit range
         №          Count of
                  ⁰ Literal integer `0` in
           ι        Current value
          Ｅ         Map over implicit range
               λ    Inner value
              Ｘ     Raised to power
                ²   Literal integer `2`
             ⊕      Incremented
            ﹪       Modulo
                 ι  Current value
   Σ                Take the sum
 ×                  Times
  ⁴                 Literal integer `4`
Ｉ                   Cast to string
                    Implicitly print

```

Note that the newer version of Charcoal on ATO allows you to vectorise the inner loop making it slightly more efficient, although the byte count is the same:

```
Ｉ×⁴ΣＥ⊕ＸＮ²№﹪⊕Ｘ…⁰ι²ι⁰

```

Attempt This Online! Link is to verbose version of code.

# Answer
> 1 votes
# APL(NARS), 37 chars

```
+/{(1=∨/⍵)∧0≥-/2⌽∊2*⍨r⍵}¨,∘.,⍨r..-r←⎕

```

test:

```
  +/{(1=∨/⍵)∧0≥-/2⌽∊2*⍨r⍵}¨,∘.,⍨r..-r←⎕
⎕:
  10
192
  +/{(1=∨/⍵)∧0≥-/2⌽∊2*⍨r⍵}¨,∘.,⍨r..-r←⎕
⎕:
  0
0
  +/{(1=∨/⍵)∧0≥-/2⌽∊2*⍨r⍵}¨,∘.,⍨r..-r←⎕
⎕:
  5
48

```

---
Tags: code-golf, geometry
---


title: Simulate Rule 110

text:
# Question
Title: Simulate Rule 110
Rule 110 is a cellular automaton with some interesting properties. **Your goal** is to simulate a rule 110 in as few characters as possible.

For those who don't know, rule 110 is simulated line by line in a grid. Each square in a line of the grid looks at the squares above, above-left and above-right to determine what cell it should be.

```
current pattern  111 110 101 100 011 010 001 000
new cell          0   1   1   0   1   1   1   0

```

**Input:** numbers from 0 to 39 representing top row nth input square, in any reasonable format (comma-separated string, list, function arguments). To accommodate 1-indexed languages, numbers may also be 1-indexed and so range from 1 to 40.

Example input:

```
38,39

```

**Output:** A 40 x 40 grid representing the automata running including the first row. You should leave 0 as blank and 1 as any visible printing character. Trailing spaces are allowed, as long as the actual grid can reasonably be distinguished. The bottom of the grid may have a newline but there should not be blank lines between grid lines.

Example output:

```
                                  XX
                                 XXX
                                XX X
                               XXXXX
                              XX   X
                             XXX  XX
                            XX X XXX
                           XXXXXXX X
                          XX     XXX
                         XXX    XX X
                        XX X   XXXXX
                       XXXXX  XX   X
                      XX   X XXX  XX
                     XXX  XXXX X XXX

```

etc.

Note: A similar question about 1D cellular automata has already been asked, but I hope that, by using only one rule, shorter answers can be written.

# Answer
> 8 votes
# CJam - 47

```
S40*l',/{i'!t}/{N40,S3$S++f{>3<2b137Yb='!^}}39*

```

It uses `!` for "1" cells.

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

**Explanation:**

`S40*` makes a string (array) of 40 spaces
`l',/` reads a line and splits by comma
`{…}/` executes the block for each item (the numbers in string form)
\- `i'!t` converts the number to integer and sets the item at that position in the previous string (initially 40 spaces) to '!'
At this point we have obtained the first line.
`{…}39*` executes the block 39 times
\- `N` adds a newline
\- `40,` makes the array \[0 1 … 39\]
\- `S3$S++` copies the previous line (position 3 on the stack) and pads it with a space on each side
\- `f{…}` executes the block for {each number from 0 to 39} and {the padded line}
-- `>3<` takes a slice of 3 items from the padded line starting at the current number
-- `2b` converts from base 2; the items we sliced are not base-2 digits, but characters get converted to their ASCII values and ' ' mod 8 is 0 and '!' mod 8 is 1
-- `137Yb` converts 137 to base 2 (`Y` = 2), obtaining \[1 0 0 0 1 0 0 1\], which is 110 reversed and negated (on 8 bits)
-- `='!^` gets the corresponding base-2 digit (the array wraps around so the index is taken mod 8) and xor's it with the '!' character, resulting in '!' for 0 and ' ' for 1

# Answer
> 18 votes
## Ruby, 113 characters

```
c=[0]*41
eval"[#{gets}].map{|i|c[i]=1}"+'
c=(0..39).map{|x|putc" X"[u=c[x]]
110[4*c[x-1]+2*u+c[x+1]]}<<0;puts'*40

```

Takes input on stdin. To use a different rule, simply replace the `110` in the last line with whatever rule you want to try.

Example:

```
$ ruby 110.rb <<< 38,39
                                      XX
                                     XXX
                                    XX X
                                   XXXXX
                                  XX   X
                                 XXX  XX
                                XX X XXX
                               XXXXXXX X
                              XX     XXX
                             XXX    XX X
                            XX X   XXXXX
                           XXXXX  XX   X
                          XX   X XXX  XX
                         XXX  XXXX X XXX
                        XX X XX  XXXXX X
                       XXXXXXXX XX   XXX
                      XX      XXXX  XX X
                     XXX     XX  X XXXXX
                    XX X    XXX XXXX   X
                   XXXXX   XX XXX  X  XX
                  XX   X  XXXXX X XX XXX
                 XXX  XX XX   XXXXXXXX X
                XX X XXXXXX  XX      XXX
               XXXXXXX    X XXX     XX X
              XX     X   XXXX X    XXXXX
             XXX    XX  XX  XXX   XX   X
            XX X   XXX XXX XX X  XXX  XX
           XXXXX  XX XXX XXXXXX XX X XXX
          XX   X XXXXX XXX    XXXXXXXX X
         XXX  XXXX   XXX X   XX      XXX
        XX X XX  X  XX XXX  XXX     XX X
       XXXXXXXX XX XXXXX X XX X    XXXXX
      XX      XXXXXX   XXXXXXXX   XX   X
     XXX     XX    X  XX      X  XXX  XX
    XX X    XXX   XX XXX     XX XX X XXX
   XXXXX   XX X  XXXXX X    XXXXXXXXXX X
  XX   X  XXXXX XX   XXX   XX        XXX
 XXX  XX XX   XXXX  XX X  XXX       XX X
XX X XXXXXX  XX  X XXXXX XX X      XXXXX
XXXXXX    X XXX XXXX   XXXXXX     XX   X

```

# Answer
> 10 votes
# Python - 141

```
i=input()
o=range(40)
l=''.join(' X'[c in i]for c in o)
for r in o:print l;l=''.join('X '[l[c-1:c+2]in('XXX','   ','X  ','','  ')]for c in o)

```

Run as e.g. `python 110.py <<< 38,39`

# Answer
> 8 votes
## Mathematica, 122 bytes

```
f[a_]:=Riffle[CellularAutomaton[110,Array[If[MemberQ[ToExpression["{"<>a<>"}"],#-1],1,0]&,40],39]/.0->" "/.1->"X","
"]<>""

```

Yes, you might view this as abusing this loophole, but a) that loophole is quite disputed, b) a Cellular Automaton question *needs* a Mathematica answer (especially one about Rule 110) and c) Ventero's Ruby answer is shorter anyway, so I don't think any harm is done.

Most of the characters are used for input parsing and output formatting. The actual automaton is simulated using

```
CellularAutomaton[110,initialGrid,39]

```

This uses periodic boundary conditions (so the grid wraps around).

# Answer
> 8 votes
# q, ~~67~~ ~~62~~ 58 bytes

Assumes no wrap-around:

```
{40{not(2 sv'flip 1 0 -1 xprev\:x)in 0 4 7}\@[40#0b;x;~:]}

```

Old version

```
{40{not(flip(prev;::;next)@\:x)in 3 cut 111100000b}\@[40#0b;x;not]}
{40{not(flip 1 0 -1 xprev\:x)in 3 3#111100000b}\@[40#0b;x;~:]}

```

# Answer
> 5 votes
# Python, 186

```
def r(s,m=range(40)):
 s=[int(i in s)for i in m]
 for g in m:print''.join([' X'[i]for i in s]);s=[int(not''.join(map(str,s[i-1:i+2]if i else s[:2]))in'111 100 000 00'.split())for i in m]

```

Decent but probably not optimal.

You didn't specify how input is gotten so I just made a function.

Use example:

> r(\[38,39\])

Output:

```
                                      XX
                                     XXX
                                    XX X
                                   XXXXX
                                  XX   X
                                 XXX  XX
                                XX X XXX
                               XXXXXXX X
                              XX     XXX
                             XXX    XX X
                            XX X   XXXXX
                           XXXXX  XX   X
                          XX   X XXX  XX
                         XXX  XXXX X XXX
                        XX X XX  XXXXX X
                       XXXXXXXX XX   XXX
                      XX      XXXX  XX X
                     XXX     XX  X XXXXX
                    XX X    XXX XXXX   X
                   XXXXX   XX XXX  X  XX
                  XX   X  XXXXX X XX XXX
                 XXX  XX XX   XXXXXXXX X
                XX X XXXXXX  XX      XXX
               XXXXXXX    X XXX     XX X
              XX     X   XXXX X    XXXXX
             XXX    XX  XX  XXX   XX   X
            XX X   XXX XXX XX X  XXX  XX
           XXXXX  XX XXX XXXXXX XX X XXX
          XX   X XXXXX XXX    XXXXXXXX X
         XXX  XXXX   XXX X   XX      XXX
        XX X XX  X  XX XXX  XXX     XX X
       XXXXXXXX XX XXXXX X XX X    XXXXX
      XX      XXXXXX   XXXXXXXX   XX   X
     XXX     XX    X  XX      X  XXX  XX
    XX X    XXX   XX XXX     XX XX X XXX
   XXXXX   XX X  XXXXX X    XXXXXXXXXX X
  XX   X  XXXXX XX   XXX   XX        XXX
 XXX  XX XX   XXXX  XX X  XXX       XX X
XX X XXXXXX  XX  X XXXXX XX X      XXXXX
XXXXXX    X XXX XXXX   XXXXXX     XX   X

```

# Answer
> 5 votes
# Mathematica, 113 chars

Another Mathematica answer using `CellularAutomaton`.

```
Print@@" "["X"][[#]]&/@CellularAutomaton[110,SparseArray[#+1->1&/@ImportString[InputString[],"CSV"][[1]],40],39];

```

# Answer
> 4 votes
# Lua - 351

Not the ideal language for golfing.

```
s,n,t,u=arg[1],{},table.remove,table.insert
for i=1,40 do u(n,i,'.') end
for i in s:gmatch("%d+")do u(n,i,'x');t(n)end
function a(b) c="";for i=1,40 do c=c..b[i] end;print(c);return c end
for i=1,40 do z= n[40]..a(n)..n[1];for k=2,41 do y=string.sub(z,k-1,k+1);if y=="xxx"or y=="x.." or y=="..." then u(n,k-1,'.')else u(n,k-1,'x')end;t(n)end end

```

# Answer
> 4 votes
# C - 178

This code depends on the fact that each row in a matrix is stored in contiguous memory. Also, it does not print the first row, but it prints the next 40 ones, since the rules only specified a 40x40 grid.

Indented for readability only, the byte count only includes necessary code.

```
a[41][42],i,j,*t;
main(){
    while(scanf("%d,",&j)>0)
        a[i][j]=1;
    for(;i<40;i++,puts(""))
        for(j=0;++j<40;)
            t=&a[i][j],
            putchar((*(t+42)=1&(110>>(*(t+1)?1:0)+(*t?2:0)+(*(t-1)?4:0)))?88:32);
}

```

# Answer
> 4 votes
# Haskell, ~~175 170 169 136 127~~ 124 bytes

−9 bytes thanks to @bmo

```
t(a:b:r:_)=mod(b+r+b*r+a*b*r)2
w%a=take 40.map w.iterate a
d l=t%tail$0:l++[0]
f l=map(" #"!!)%d$(fromEnum.(`elem`l))%succ$0

```

Try it online!

# Answer
> 4 votes
# Microsoft Excel, ~~21~~ 19 characters

(Not sure how to score this actually. I know this takes 39\*40 or 1560 formulas, but they all depend on the first one.)

As a bonus, this works in LibreOffice Calc too.

## The formula

`=(B1<>C1)+C1*(B1>A1`

To get the 40x40:

1. Insert the formula at cell B2. (Don't forget the `=` sign!)
2. Drag the cells to Column AO.
3. Drag these cells to Row 40.

Extra niceties:

1. Conditionally format cells to Good when value is TRUE
2. Set cell widths to 0.3" or something.

## Explanation

* The input is the first row. A value that can be converted to `TRUE`, such as 1 is `TRUE`. A blank cell or anything else is a `FALSE`.
* Column A is just a buffer to make edge cases easier to deal with.
* This is easier to see if you do the conditional formatting stuff.
* The formula is really just a hacky way of saying (B XOR C) + (BCA')

# Answer
> 4 votes
# Python 3, 126 bytes (as function)

```
def r(n,r):
 for d in range(r):print("".join(" o"[n>>i&1]for i in range(40)));n=sum((110>>(n>>i&7)&1)<<i+1 for i in range(40))

```

## 142 bytes with stdin

```
n,r=map(int,input().split())
for d in range(r):print("".join(" o"[n>>i&1]for i in range(40)));n=sum((110>>(n>>i&7)&1)<<i+1 for i in range(40))

```

## 188, my first attempt and favourite

```
import itertools as t;print("\n".join(map(lambda n:"".join(" o"[n>>i&1]for i in range(n.bit_length())),t.accumulate(range(1,40),lambda n,d:sum((110>>(n>>i&7)&1)<<i+1 for i in range(d))))))

```

# Answer
> 3 votes
# Haskell, ~~135 131~~ 130 bytes

-1 byte thanks to Ørjan Johansen (rearranging `take 40`)

Completely different approach to FrownyFrog's answer but about the same length:

```
(a?b)r=mod(b+r+b*r+a*b*r)2
r x=0:(zipWith3(?)x=<<tail$tail x++[0])
f y=take 40$map(" o"!!)<$>iterate r[sum[1|elem i y]|i<-[0..40]]

```

Uses \\$1\\$-indexing and has a leading space on each line, try it online!

## Explanation

We're going to work with length-\\$41\\$ lists with values \\$\texttt{0}\\$, \\$\texttt{1}\\$, so let's start with the correct array:

```
f y=                               [sum[1|elem i y]|i<-[0..40]]

```

Next we're going to iterate the rule \\$40\\$ times:

```
    take 40$              iterate r

```

And finally map each \\$\texttt{0}\\$ and \\$\texttt{1}\\$ to some fancy character:

```
            map(" o"!!)<$>

```

The function `r` which applies the \\$\texttt{110}\\$-rule is pretty simple: Using `zipWith3` and some padding we can outsource the actual decision for the next cell to `(?)`:

```
r x=0:(zipWith3(?)x=<<tail$tail x++[0])

```

The `(?)` operator is the most interesting part of the solution: Previously I used a Boolean rule generated with a Karnaugh map, but turns out there is an even more concise way:

```
(a?b)r=mod(b+r+b*r+a*b*r)2

```

# Answer
> 3 votes
# Husk, ~~31~~ 28 bytes

Hah, Husk is beating Jelly!

```
†!¨↑¨↑40¡ȯẊȯ!ḋ118ḋėΘ`:0M#ŀ40

```

Try it online!

## Explanation & Ungolfed

Before adding an explanation, let me ungolf this a bit.. Let's first remove the various compositions, add explicit parentheses and uncompress the `¨↑¨` string. Also let's replace `40` with `4` for a more readable explanation:

```
†!"t "↑4¡(Ẋ(!ḋ118ḋė)Θ`:0)M#ŀ4  -- example input: [3]
                           ŀ4  -- lower range of 4: [0,1,2,3]
                         M     -- map over left argument
                          #    -- | count in list
                               -- : [0,0,0,1]
        ¡(              )      -- iterate the following indefinitely (example with [0,1,1,1])
                     `:0       -- | append 0: [0,1,1,1,0]
                    Θ          -- | prepend 0: [0,0,1,1,1,0]
          Ẋ(       )           -- | map over adjacent triples (example with  1 1 0
                  ė            -- | | create list: [1,1,0]
                 ḋ             -- | | convert from base-2: 6
                               -- | | convert 118 to base-2: [1,1,1,0,1,1,0]
                               -- | | 1-based index: 1
                               -- | : [1,1,0,1]
                               -- : [[0,0,0,1],[0,0,1,1],[0,1,1,1],[1,1,0,1],[1,1,1,1],[1,0,0,1],...]
      ↑4                       -- take 4: [[0,0,0,1],[0,0,1,1],[0,1,1,1],[1,1,0,1]]
†                              -- deep map the following (example with [1,1,0,1])
 !"t "                         -- | use each element to index into "t ": "tt t"
                               -- : ["   t","  tt"," ttt","tt t"]

```

# Answer
> 2 votes
# Java, 321 characters

Input passed as argument from command line, for example `java R 38,39`

I have never written more obfuscated java code :-)

```
class R{public static void main(String[]a) {
Integer s=40;boolean[]n,o=new boolean[s];
for(String x:a[0].split(","))o[s.valueOf(x)]=s>0;
for(Object b:o){n=o.clone();
for(int j=0;j<s;j++){
boolean l=j>1&&o[j-1],r=o[j],c=j+1<s&&o[j+1];
n[j]=!(l&c&r|l&!c&!r|!(l|c|r));
System.out.print((r?"X":" ")+(j>s-2?"\n":""));
}o=n;}}}

```

# Answer
> 2 votes
Update: Correct output example here (with 40 lines not 50): New output below (removed previous one for brevity):

```
                                      xx
                                     xxx
                                    xx x
                                   xxxxx
                                  xx   x
                                 xxx  xx
                                xx x xxx
                               xxxxxxx x
                              xx     xxx
                             xxx    xx x
                            xx x   xxxxx
                           xxxxx  xx   x
                          xx   x xxx  xx
                         xxx  xxxx x xxx
                        xx x xx  xxxxx x
                       xxxxxxxx xx   xxx
                      xx      xxxx  xx x
                     xxx     xx  x xxxxx
                    xx x    xxx xxxx   x
                   xxxxx   xx xxx  x  xx
                  xx   x  xxxxx x xx xxx
                 xxx  xx xx   xxxxxxxx x
                xx x xxxxxx  xx      xxx
               xxxxxxx    x xxx     xx x
              xx     x   xxxx x    xxxxx
             xxx    xx  xx  xxx   xx   x
            xx x   xxx xxx xx x  xxx  xx
           xxxxx  xx xxx xxxxxx xx x xxx
          xx   x xxxxx xxx    xxxxxxxx x
         xxx  xxxx   xxx x   xx      xxx
        xx x xx  x  xx xxx  xxx     xx x
       xxxxxxxx xx xxxxx x xx x    xxxxx
      xx      xxxxxx   xxxxxxxx   xx   x
     xxx     xx    x  xx      x  xxx  xx
    xx x    xxx   xx xxx     xx xx x xxx
   xxxxx   xx x  xxxxx x    xxxxxxxxxx x
  xx   x  xxxxx xx   xxx   xx        xxx
 xxx  xx xx   xxxx  xx x  xxx       xx x
xx x xxxxxx  xx  x xxxxx xx x      xxxxx
xxxxxx    x xxx xxxx   xxxxxx     xx   x

```

Doing another puzzle I learned something interesting about nesting statements in for loops in php, and suddenly they are far more complex than I originally thought. When I get time I reckon I can beat this score considerably. For now though it remains unchanged at a non-competitive 408.

---

My php version 408 characters:

This was a great puzzle. I also spent ages playing with the inputs as these are fascinating things it must be said. Anyway, here is my PHP version (which is nowhere near as good as some of the answers posted but is complete. In 0th position only take above and above right, in 39th position only take above and above left, ie no wrapping. So here is my version:

```
<?php $a='38,39';$b='';$d=explode(',',$a);for($i=0;$i<40;++$i){$c=' ';
foreach($d as $k=>$v){if($v == $i){$c='x';}}$b.=$c;}echo $b."\n";
for($x=1;$x<41;++$x){$o='';for($i=1;$i<41;++$i){if(($i>1)AND(substr($b,$i-2,1)=='x')){
$l=1;}else{$l=0;}if((substr($b,$i-1,1))=='x'){$v=1;}else{$v=0;}if((substr($b,$i,1))=='x'){
$r=1;}else{$r=0;}if((($l+$v+$r)==2)OR(($v+$r)==1)){$o.='x';}else{$o.=' ';}}
echo $o."\n";$b=$o;}?>

```

You can see it and run it here: http://codepad.org/3905T8i8

Input is a input string at the start as $a='38, 39';

Output is as follows:

```
xx removed as was too long originally - had 50 lines, not 40 xx

```

Hope you like it!!!

PS I had to add a few line breaks to the code so you could see all of it and not have it stretch accross the page with a scroll bar.

# Answer
> 2 votes
# Stax, 24 bytesCP437

```
╦♥µ╤u{£┬íQ<;▀ΦΣ╢╕╚äZ↕áû↑

```

Run and debug online!

Uses the codepoint 1 in CP437 for "1" cells.

Excellent case to show the power of this language.

## Explanation

Uses the unpacked version (29 bytes) to explain.

```
0]40X*,1&xDQ0]|S3B{:b^374:B@m
0]40X*                           Prepare a tape with 40 cells
      ,1&                        Assign 1 to the cells specified by the input
         xD                      Repeat the rest of the program 40 times
           Q                     Output current tape
            0]|S                 Prepend and append a 0 cell to it
                3B               All runs of length 3
                  {         m    Map each run with block
                   :b            Convert from binary
                     ^           Increment (call this value `n`)
                      374:B      The binary representation of 374
                                 [1,0,1,1,1,0,1,1,0]
                                 which is `01101110` reversed and prepended a 1
                           @     Element at 0-based index `n`

```

# Answer
> 2 votes
# K (ngn/k), ~~44~~ 36 bytes

```
{"X "39{(2\145)@2/'3':1,x,1}\^x?!40}

```

Try it online!

`{` `}` function with argument `x`

`!40` list of ints from 0 to 39

`x?` find their indices in `x`, use `0N` (the "integer null") for not found

`^` which of them are nulls? this gives us the input, negated

`39{` `}\` apply 39 times, collecting intermediate results in a list

`1,x,1` surround the list with 1s (negated 0s)

`3':` triples of consecutive items

`2/'` binary decode each

`@` use as indices in ...

`2\145` binary encode 145 (negated bits of 110)

`"X "` finally, use the 40x40 matrix as indices in the string `"X "` (the `@` here is implicit)

# Answer
> 1 votes
# Pip, 54 bytes

```
x:Y0X40RAgoL40{Fi,40x@i:01110110@FB(y@>i@<3)Y0.xPxR0s}

```

Pip is turing complete?!

(Jokes aside, this was a fun pip answer.)

## Explanation

```
x:Y0X40RAgoL40{Fi,40x@i:01110110@FB(y@>i@<3)Y0.xPxR0s}
x:Y0X40RAgo                                             Assign 40 spaces to x and replace the input indices with 1
                                                        The same value is also yanked to y.
           L40{                                      }  Repeat 40 times
               Fi,40                                    Loop variable i through range 1-40
                    x@i:                                Assign character at index i to:
                        01110110@                       a number in 01110110 at index:
                                 FB(y@>i@<3)            a 3 letter substring of y starting at i, converted to binary.
                                            Y0.x        Yank(assign value) of 0 concantenated with x to y
                                                PxR0s   Print x with zeros replaced with spaces

```

Try it online!

# Answer
> 1 votes
# Jelly, 22 bytes

```
ṬµØ0jḄ3Ƥị236B¤µ39Ð¡Yo⁶

```

Try it online!

Took some inspiration from Erik's answer.

# Answer
> 1 votes
# JavaScript, 242, 202 bytes

```
// redable version
((...l)=>{
  k=Array(40).fill(' ');l.map(x=>k[x]='X')

  for(i=0;i++<40;){
    console.log(k.join``);
    k=k.map((x,i)=> i==0|| (i==k.length) || ["   ","XXX","X. "].includes(k.at(i-1)+k.at(i)+k.at(i+1)) ? ' ':'X')
  }
})(38,39)
```

Minified:

```
((...l)=>{k=Array(40).fill(' ');l.map(x=>k[x]='X');for(i=0;i++<40;){console.log(k.join``);k=k.map((x,i)=>i==0||(i==k.length)||["   ","XXX","X. "].includes(k.at(i-1)+k.at(i)+k.at(i+1))?' ':'X')}})(38,39)

```

# Answer
> 1 votes
# Python, 150 bytes

```
import sys
I=''.join(' X'[str(A)in sys.argv]for A in range(40))
for _ in I:print(I);I=''.join('X '[(' '+I+' ')[A:A+3]in'XXX.X   ']for A in range(100))

```

Example: `python rule110.py 39`

Old solution with hardcoded initial universe:

```
I=' '*99+'X'
for _ in I:print(I);I=''.join('X '[(' '+I+' ')[A:A+3]in'XXX.X   ']for A in range(100))

```

The rule became a bit complicated. Based on another answer, I check only the rules that result in a dead cell because there's only 3 rules that can be compressed into a small substring check.

The cell at the next `I[i]` dies if `I[i:i+3]` is any of `XXX` `X` , or  (3 spaces). Since `I[i:i+3]` is a string, we can check if it's a substring of `111` or `1000`. More concisely, `I[i] = ' '` if `I[i:i+3]` is a substring of `111SEP1000`, where `SEP` is anything besides `X` and .

# Answer
> 0 votes
# Jelly, 29 bytes

```
‘;41ṬṖŻ;0Ḅe“¢£¤¦©‘Ɗ3ƤƊ39Ð¡Yo⁶

```

Try it online!

# Answer
> 0 votes
# Perl 5 `-a`, 99 bytes

```
$_=$"x40;for$b(@F){substr$_,$b,1,1}for$b(1..40){say;s,(?<=(.)).(?=(.)),"$1$&$2"=~/111|  $/?$":1,ge}

```

Try it online!

# Answer
> 0 votes
# Rust, 370 bytes

```
fn a(f:&[u8]){let mut g=[0;40];for e in f{g[*e as usize]=1;};p(&g);for _ in 0..39{let mut n=[0;40];for e in 0..40{let m=match e{0=>r(g[0]*2+g[1]),39=>r(g[38]*4+g[39]*2),_=>r(g[e-1]*4+g[e]*2+g[e+1])};n[e]=m;}g=n;p(&g);}}fn p(g:&[u8]){println!("{}",g.iter().map(|x|format!("{}",x)).collect::<String>().replace("0"," "));}fn r(b:u8)->u8{match b{0|4|7=>0,1|2|3|5|6=>1,_=>2}}

```

Try it online!

A probably very naive implementation. Input is a slice of `u8` representing the starting `1`s. Prints rule 110, with `1` as its character.

Ungolfed:

fn r110(filled: &[u8]) {
    let mut grid = [0; 40];
    for e in filled { grid[*e as usize] = 1; }

    println!(
            "{}",
            grid
            .iter()
            .map(|x| format!("{}",x))
            .collect::<String>()
            .replace("0", " "));

    for _iteration in 0..39 {
        let mut next_grid = [0; 40];
        for element in 0..40 {
            let next = match element {
                0 => {
                    rule(grid[0]*2 + grid[1])
                }
                39 => {
                    rule(grid[38]*4 + grid[39]*2)
                }
                _ => {
                    rule(grid[element-1]*4 + grid[element]*2 + grid[element+1])
                }
            };
            next_grid[element] = next;
        }
        grid = next_grid;
        println!(
            "{}",
            grid
            .iter()
            .map(|x| format!("{}",x))
            .collect::<String>()
            .replace("0", " "));
    }
}

fn rule(bits: u8) -> u8 {
// current pattern  111 110 101 100 011 010 001 000
// new cell          0   1   1   0   1   1   1   0
    match bits {
        0 | 4 | 7 => 0,
        1 | 2 | 3 | 5 | 6 => 1,
        _ => 2
    }
}
```

---
Tags: code-golf, ascii-art, cellular-automata
---