title: Make a 2d menger sponge

text:
# Question
Title: Make a 2d menger sponge
A menger sponge is a fractal made out of cubes within cubes within cubes...

If you start with a cube, on each face there are 9 squares. The middle square becomes empty (or 0). The other 8 squares iterate this process. They each get split up into 9 squares and the middle square face is taken out.

The goal today is to generate a menger sponge *face*, not the cube.

Here are some example given an input for the number of iterations.

```
0:
1
(No holes or anything, solid face)

1:
1 1 1
1 0 1
1 1 1

2:
111111111
101101101
111111111
111000111
101000101
111000111
111111111
101101101
111111111

```

To complete the challenge, based on an input, return a set of 1 (filled in blocks) and 0 (empty blocks) with spaces between or not.

This is code golf, lowest number of bytes wins.

# Answer
# SOGL V0.12, 19 bytes

```
1¹.{³³┼┼≥:10ŗ;┼┼⁴++

```

Try it Here!

```
1¹                   push [1]
  .{                 input times do
    ³³                 duplicate top of stack 4 times, resulting in 5 total copies in the stack
      ┼┼               join the last 3 copies horizontally together
        ≥              put the joined at the bottom of the stack
         :             duplicate top of stack again
          10ŗ          replace 1 with 0 only in the top item
             ;         swap the top 2 items
              ┼┼       join the top 3 items horizontally together
                ⁴      copy the item one below top of stack
                 ++    add together vertically

```
> 1 votes

---
Tags: code-golf, fractal
---


# Question
Title: Approximate floating point number with n-digit precision
We have a floating point number `r` between 0 and 1, and an integer `p`.

Find the fraction of integers with the smallest denominator, which approximates `r` with at least `p`-digit precision.

* Inputs: `r` (a floating point number) and `p` (integer).
* Outputs: `a` and `b` integers, where
    + `a/b` (as float) approximates `r` until `p` digits.
    + `b` is the possible smallest such positive integer.

For example:

* if `r=0.14159265358979` and `p=9`,
* then the result is `a=4687` and `b=33102`,
* because `4687/33102=0.1415926530119026`.

Any solution has to work in theory with arbitrary-precision types, but limitations caused by implementations' fixed-precision types do not matter.

Precision means the number of digits after "`0.`" in `r`. Thus, if `r=0.0123` and `p=3`, then `a/b` should start with `0.012`. If the first `p` digits of the fractional part of `r` are 0, undefined behavior is acceptable.

Win criteria:

* The algorithmically fastest algorithm wins. *Speed is measured in O(p).*
* If there are multiple fastest algorithms, then the shortest wins.
* My own answer is excluded from the set of the possible winners.

P.s. the math part is actually much easier as it seems, I suggest to read this post.

# Answer
> 7 votes
# JavaScript, O(10p) & 72 bytes

```
r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]}

```

It is trivial to prove that the loop will be done after at most O(10p) iterations.

```
f=
r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]}
```

```
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow>
    <mn>0.<input type="text" id="n" value="" oninput="[p,q]=f(+('0.'+n.value))(n.value.length);v1.value=p;v2.value=q;d.value=p/q" /></mn>
    <mo>=</mo>
    <mfrac>
      <mrow><mn><output id="v1">0</output></mn></mrow>
      <mrow><mn><output id="v2">1</output></mn></mrow>
    </mfrac>
    <mo>=</mo>
    <mn><output id="d">0</output></mn>
  </mrow>
</math>
```

Many thanks to Neil's idea, save 50 bytes.

# Answer
> 4 votes
# Haskell, O(10p) in worst case ~~121~~ 119 bytes

```
g(0,1,1,1)
g(a,b,c,d)r p|z<-floor.(*10^p),u<-a+c,v<-b+d=last$g(last$(u,v,c,d):[(a,b,u,v)|r<u/v])r p:[(u,v)|z r==z(u/v)]

```

Try it online!

*Saved 2 bytes thanks to Laikoni*

I used the algorithm from https://math.stackexchange.com/questions/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i.

At each step, the new interval is one half of the previous interval. Thus, the interval size is `2**-n`, where `n` is the current step. When `2**-n < 10**-p`, we are sure to have the right approximation. Yet if `n > 4*p` then `2**-n < 2**-(4*p) == 16**-p < 10**-p`. The conclusion is that the algorithm is `O(p)`.

**EDIT As pointed out by orlp in a comment, the claim above is false.** In the worst case, `r = 1/10**p` (`r= 1-1/10**p` is similar), there will be `10**p` steps : `1/2, 1/3, 1/4, ...`. There is a better solution, but I don't have the time right now to fix this.

# Answer
> 0 votes
### C, 473 bytes (without context), O(p), non-competing

This solution uses the math part detailed in this excellent post. I calculated only `calc()` into the answer size.

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void calc(float r, int p, int *A, int *B) {
  int a=0, b=1, c=1, d=1, e, f;
  int tmp = r*pow(10, p);
  float ivl = (float)(tmp) / pow(10, p);
  float ivh = (float)(tmp + 1) / pow(10, p);

  for (;;) {
    e = a + c;
    f = b + d;

    if ((ivl <= (float)e/f) && ((float)e/f <= ivh)) {
      *A = e;
      *B = f;
      return;
    }

    if ((float)e/f < ivl) {
      a = e;
      b = f;
      continue;
    } else {
      c = e;
      d = f;
      continue;
    }
  }
}

int main(int argc, char **argv) {
  float r = atof(argv[1]);
  int p = atoi(argv[2]), a, b;
  calc(r, p, &a, &b);
  printf ("a=%i b=%i\n", a, b);
  return 0;
}

```

---
Tags: math, fastest-algorithm
---


# Question
Title: Distinct Reversible Primitive Binary Necklaces
# Introduction - What is a necklace?

A necklace is something that OEIS people are obsessed with. The OEIS challenge has like 5 necklace sequences.

A binary necklace of length `n` is a loop with `n` beads that are either `0` or `1`. Two necklaces are the same if one can be rotated to become the other, and two reversible necklaces are the same if one can be rotated, reversed, or reversed and rotated to become the other.

A primitive necklace is one that cannot be expressed as more than one copy of a string of beads chained together. Note that the copies must be assembled all in the same order (no reversing) for a necklace to be considered non-primitive.

For example, let's take a look at this necklace: `0 1 1 0 1 1`. It is not primitive because it can be expressed as `0 1 1` repeated twice. `0 1 0 1 1` is primitive.

`0 1 1 0` is primitive because `0 1` and `1 0` are not considered the same string. This necklace is equivalent to `1 1 0 0` because it can be rotated left one bead to become this one, but not equivalent to `0 1 0 1` (which isn't primitive by the way).

# Challenge

Given an non-negative integer `n`, return the number of distinct reversible primitive binary necklaces of length `n`. Input and output as a single integer each.

The first few terms of this sequence are `1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 4110`, 0-indexed.

**This is OEIS A001371**

Reference Implementation in Python 3 \- quite slow

# Answer
# Python 2, ~~178~~ ~~171~~ ~~139~~ 137 bytes

```
lambda n:sum(1-any(i>int(b[j::-1]+b[:j:-1],2)or j*(i>=int(b[j:]+b[:j],2))for j in range(n))for i in range(2**n)for b in[bin(i+2**n)[3:]])

```

Try it online! Edit: Saved ~~7~~ 21 bytes thanks to @HalvardHummel.
> 6 votes

# Answer
# JavaScript (ES6), ~~198~~ 192 bytes

I was curious to know what a fully mathematical answer would look like. So here it is. Quite long but very fast.

```
n=>(g=d=>d&&(n%d?0:(q=n/d,C=(a,b)=>b?C(b,a%b):a<2,M=n=>n%++k?k>n?(q%2+3)/4*(1<<q/2)+(R=d=>d&&(q%d?0:(P=k=>k--&&C(q/d,k)+P(k))(q/d)<<d)+R(d-1))(q)/q/2:M(n):n/k%k&&-M(n/k))(d,k=1))+g(d-1))(n)||1

```

### Demo

```
let f =

n=>(g=d=>d&&(n%d?0:(q=n/d,C=(a,b)=>b?C(b,a%b):a<2,M=n=>n%++k?k>n?(q%2+3)/4*(1<<q/2)+(R=d=>d&&(q%d?0:(P=k=>k--&&C(q/d,k)+P(k))(q/d)<<d)+R(d-1))(q)/q/2:M(n):n/k%k&&-M(n/k))(d,k=1))+g(d-1))(n)||1

for(n = 0; n <= 30; n++) {
  console.log('a(' + n + ') = ' + f(n))
}
```

### How?

This is based on the following formulas:

```
A000029(n) =
  (n % 2 + 3) / 4 * 2 ** floor(n / 2) +
  sum(φ(n / d) * 2 ** d, for d in divisors(n)) / (2 * n)

A001371(n) =
  1 if n = 0
  sum(μ(d) * A000029(n / d), for d in divisors(n)) if n > 0

```

Where ***φ*** is Euler's totient function and ***μ*** is Möbius function.

```
n => (g = d =>
  // if d = 0, stop the recursion of g()
  d && (
    // if d is not a divisor of n, ignore this iteration
    n % d ? 0 :
    (
      // define q = n / d, C = function that tests whether a and b are coprime,
      // M = Möbius function (requires k to be initialized to 1)
      q = n / d,
      C = (a, b) => b ? C(b, a % b) : a < 2,
      M = n => n % ++k ? k > n || M(n) : n / k % k && -M(n / k)
    )(d, k = 1) * ( // invoke M with d
      // first part of the formula for A000029
      (q % 2 + 3) / 4 * (1 << q / 2) +
      // 2nd part of the formula for A000029
      (R = d =>
        // if d = 0, stop the recursion of R()
        d && (
          // if d is not a divisor of q, ignore this iteration
          q % d ? 0 :
          // compute phi(q / d) * 2 ** d
          (P = k => k-- && C(Q, k) + P(k))(Q = q / d) << d
        // recursive call to R()
        ) + R(d - 1)
      )(q) / q / 2 // invoke R with q, and divide the result by q * 2
    )
  // recursive call to g()
  ) + g(d - 1)
)(n) || 1

```

NB: In the current golfed version, the 2nd part of the code is now directly embedded inside ***M()***. But that makes the code harder to read.
> 5 votes

# Answer
# Mathematica, ~~128~~ ~~125~~ ~~124~~ ~~109~~ 99 bytes

```
1~Max~(L=Length)@(U=Union)[U[#,Reverse/@#]&/@MaximalBy[U@Partition[#,L@#,1,1]&/@{0,1}~Tuples~#,L]]&

```

## How it works

* `{0,1}~Tuples~#` finds all binary sequences of the given length
* `U@Partition[#,L@#,1,1]&/@...` finds all possible rotations of each one of them
* `MaximalBy[...,L]` picks out the entries with the most distinct rotations; these correspond to the primitive necklaces.
* `U[#,Reverse/@#]&/@...` puts the rotations in each entry, and their reversals, into a canonical order...
* `(L=Length)@(U=Union)[...]` ...so that we can delete duplicate primitive necklaces, and then count the elements remaining.
* `1~Max~...` we make sure the result is at least 1 to get the zeroth term right.

---

*-2 bytes thanks to Jonathan Frech, and -2 thanks to me learning from him*

*-15 more bytes from switching to* `MaximalBy` *and related changes*

*-10 from switching to* `Partition`
> 4 votes

# Answer
# Husk, 21 bytes

```
Ṡ#▲mLüOmȯṁSe↔U¡ṙ1ΠRḋ2

```

Try it online! The link shows results from 0 to 10.

## Explanation

```
Ṡ#▲mLüOmȯṁSe↔U¡ṙ1ΠRḋ2  Implicit input, say n=4.
                  Rḋ2  The list [1,0] repeated n times: [[1,0],[1,0],[1,0],[1,0]]
                 Π     Cartesian product: [[1,1,1,1],[0,1,1,1],[1,0,1,1],...,[0,0,0,0]]
       mȯ              For each list, say x=[0,1,0,0]:
              ¡ṙ1        Iterate rotation by one step: [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],...
             U           Take prefix of unique values: [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]
         ṁSe↔            After each element, insert its reversal: [[0,1,0,0],[0,0,1,0],[1,0,0,0],[0,0,0,1],[0,0,0,1],[1,0,0,0],[0,0,1,0],[0,1,0,0]]
     üO                Remove duplicates with respect to sorting.
   mL                  Get length of each list of lists.
Ṡ#▲                    Count the number of maximal lengths.

```
> 3 votes

# Answer
# Jelly, 25 bytes

```
2ḶṗµṙJ;U$ṢḢµ€QµsJṖE€ẸṆµ€S

```

Try it online!

Very inefficient.
> 2 votes

# Answer
# Javascript (ES7), 180 bytes

```
n=>[...Array(2**n)].filter((_,m)=>![...m=m.toString(2).padStart(n,0)].some(_=>s[m=m.replace(/(.)(.*)/,"$2$1")]|s[[...m].reverse().join``])&!/^(.+)\1+$/.test(m)&(s[m]=1),s=[]).length

```

Explanation:

```
n=>[...Array(2**n)].filter((_,m)=>(     // For every number m from 0 to 2^n-1
    m=m.toString(2).padStart(n,0),      // Take the binary representation (padded)

    ![...m].some(_=>(                   // Repeat once for every digit in m
        m=m.replace(/(.)(.*)/,"$2$1"),  // Rotate m one step
        s[m]|s[[...m].reverse().join``] // Search for m and the reverse of m in the
    ))                                  // lookup table

    &!/^(.+)\1+$/.test(m)               // Test if m is primitive
    &(s[m]=1)                           // Add m to the lookup table

),s=[]).length                          // Get the length of the list of numbers that
                                        // satisfy the above conditions

```

```
f=n=>[...Array(2**n)].filter((_,m)=>![...m=m.toString(2).padStart(n,0)].some(_=>s[m=m.replace(/(.)(.*)/,"$2$1")]|s[[...m].reverse().join``])&!/^(.+)\1+$/.test(m)&(s[m]=1),s=[]).length
```

```
<input id=i type=number value=5/><button onclick="o.innerText=f(i.value)">Test</button><br><pre id=o></pre>
```
> 1 votes

---
Tags: code-golf, math, sequence, combinatorics
---


title: Smallest unused number sharing a factor

text:
# Question
Title: Smallest unused number sharing a factor
This is a pretty run of the mill question. I will define a sequence and you golf some code to output a entry given a index.

* The first item in the sequence is 2.
* The nth item in the sequence is the smallest positive integer other than n and 1 sharing at least one factor with n (other than 1) that has not already appeared in the list.

# Test cases

Here are the first 25 items in the sequence:

```
1  2
2  4
3  6
4  8
5  10
6  3
7  14
8  12
9  15
10 5
11 22
12 9
13 26
14 7
15 18
16 20
17 34
18 16
19 38
20 24
21 27
22 11
23 46
24 21
25 30

```

Related (offset by one) OEIS

# Answer
> 5 votes
# Jelly, 19 bytes

```
R»2ɓ²Rg⁸>1Tḟ⁸ḟḢṭµ/Ṫ

```

Try it online!

# Answer
> 3 votes
# Python 3, 118 117 bytes

<sup> -1 byte thanks to Cameron Aavik! </sup>

```
import math
def f(n,i=3):
 if n<2:return 2
 while 1:
  if math.gcd(n,i)>1>(i in map(f,range(n)))<i!=n:return i
  i+=1

```

Try it online!

The code is pretty inefficient (it brute-forces a value that doesn't exist in the previous results, and calculates the previous results again on every new value), so it works properly but I wouldn't recommend running it on large numbers.

# Answer
> 2 votes
# Haskell, ~~60~~ 59 bytes

EDIT:

* -1 byte: @xnor pointed out `all(/=x)` was shorter than `x`notElem``.

`f` takes an integer and returns an integer.

```
f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:map f[1..n-1]]!!0

```

Try it online!

This is very exponential time, so TIO times out after 21, while my interpreted GHCi got up to 22 before I stopped it just now. The following 9 bytes longer version memorizing into a list easily goes up into the thousands:

```
f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:take(n-1)l]!!0
l=f<$>[1..]

```

Try it online!

* `f n` uses a list comprehension to generate candidates `x`, taking the first passing one with `!!0`.
* `gcd x n>1` checks that `x` and `n` have common factors.
* `||n<2` exempts `n==1` from the factor requirement.
* `all(/=x)$n:map f[1..n-1]` checks that `x` is neither `n` nor a preceding sequence element.

# Answer
> 2 votes
No built-in for GCD in C#, so...

# C# (.NET Core), 197 196 194 bytes

```
n=>{if(n<2)return 2;var p=new int[n-1];int i=0,a,b;for(;i<n-1;)p[i]=f(++i);for(i=2;;i++)if(n!=i){for(a=n,b=i;a*b>0;)if(a>b)a%=b;else b%=a;if(b!=1&a!=1&!System.Array.Exists(p,e=>e==i))return i;}}

```

Try it online!

Once again, refrain from using this code to calculate numbers in the sequence for `n>30`...

* -1 byte by changing the GCD `while` loop for a `for` loop.
* -2 bytes thanks to Kevin Cruijssen! Nice one!

# Answer
> 0 votes
# APL (Dyalog), 46 bytes

```
{⍺←2⋄1=⍵:2⋄(~∨/⍺∊∇¨⍳⍵-1)∧(1<⍺∨⍵)∧⍺≠⍵:⍺⋄⍵∇⍨1+⍺}

```

Try it online!

---
Tags: code-golf, number, sequence, permutations
---


title: 0.0000000000000000001

text:
# Question
Title: 0.0000000000000000001
Notice the pattern in the below sequence:

```
0.1, 0.01, 0.001, 0.0001, 0.00001 and so on, until reaching 0.{one hundred zeros}1

```

Then, continued:

```
0.2, 0.02, 0.002, 0.0002, 0.00002 and so on, until reaching 0.{two hundred zeros}2

```

Continued:

```
0.3, 0.03, etc, until 0.{three hundred zeros}3

```

Continued:

```
0.4, 0.04, etc, until 0.{four hundred zeros}4

```

Sped up a bit:

```
0.10, 0.010, etc.  until 0.{one thousand zeros}10

```

Sped up some more:

`0.100, 0.0100...`

You get the idea.

The input your code will receive is an integer, the number of terms, and the output is that many number of terms of the sequence.

Input and output formats are unrestricted, and separators are not required.

Trailing zeros are necessary.

Standard loopholes apply.

---

The outputs of some nth terms are given below:

```
nth term -> number
-------------------
1        -> 0.1
102      -> 0.2
303      -> 0.3
604      -> 0.4
1005     -> 0.5
1506     -> 0.6
2107     -> 0.7
2808     -> 0.8
3609     -> 0.9
4510     -> 0.10

```

# Answer
# 05AB1E, 23 bytes

Online compiler can't show all terms for high N but it works fine offline.

```
Lvy2°*>F„0.0N×yJ,¼¾¹Qiq

```

**Explanation**

```
                          # implicit input X
Lv                        # for each y in range [1 .. X]
  y2°*>F                  # for each N in range [0 .. y*100+1)
        „0.               # push the string "0."
           0N×            # push 0 repeated N times
              y           # push current y
               J,         # join and print
                 ¼¾¹Qiq   # quit the program after X terms printed

```

Try it online!
> 10 votes

# Answer
# Haskell, ~~53~~ 63 bytes

This does the same thing as the 05AB1E answer now

```
f=(`take`["0."++('0'<$[1..y])++show x|x<-[1..],y<-[0..x*100]])

```
> 5 votes

# Answer
# Python 2, ~~73~~ 64 bytes

I think this is pretty short. I'm not sure that I can get it any shorter now that I golfed the `if-else` away.

```
s=z=1
exec'print"0.%0*d"%(z,s);q=z>s*100;z+=1-z*q;s+=q;'*input()

```

**Try it online**

Less golfed:

```
n=input()
s=z=1
for i in range(n):
    print"0.%0*d"%(z,s)
    if z>s*100:z=1;s+=1
    else:z+=1

```
> 5 votes

# Answer
# Perl 5, 57 52 bytes

(needs `-E` for `say`)

```
for(1..<>){say"0."."0"x$i++.$.;$.++,$i=0if$i>100*$.}

```

Or readably:

```
# $. is the input line number, use it to count the
# number at the end.
# $i counts zeroes in the middle, starts at 0 implicitly
for(1..<>){                      # get the number of terms from stdin and loop
                                 # <> implicitly increases $. (to 1)
    say "0." . "0" x $i++ . $.;  # print the number, add one zero
    $.++, $i=0 if $i > 100 * $.; # increment the number, reset number
                                 # of zeroes if we've printed enough
}

```

Trailing zeroes are printed since the number after the row of zeroes is just an integer concatenated as a string.

Test run:

```
$ perl -E 'for(1..<>){say"0."."0"x$i++.$.;$.++,$i=0if$i>100*$.}' | tail -3
4511
0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009
0.10
0.010

```
> 5 votes

# Answer
## QBIC, ~~73~~ 64 bytes

```
:#0|{C=!q$D=@0.|[0,q*100|d=d+1?D+$LTRIM$|(C) D=D+A~d=a|_X]]q=q+1

```

Saved 9 bytes by removing `x` as upper bound in the `FOR` loop. Upper bound is now set as `q*100`. Shame that QBasic automatically adds a space in front of a printed number, that's a costly `LTRIM$`...

Some explanation: `q` is used as the current number in the loop. This starts as 1 and gets incremented every 100N turns. This number gets converted to a string and is then appended to the string `0.` and the correct number of `0`'s. In detail:

```
We use q as our 'base number', this is 1 implicitly
:                Get the max number of terms from a numeric CMD line param
#0|              Define string A$ as "0"
{                DO
C=!q$            our base number is cast to the string C$
D=@0.|           define D$ as "0."
[0,q*100|        FOR each of the terms we need to do for our base number
                 (i.e. 101 for 1, 201 for 2 ...)
d=d+1            Keep track of the total # of terms
                 (i.e. 101 after the 1 cycle, 302 after the 2...)
?D+$LTRIM$|(C)   Print to screen D$ + C$, where D$ = "0.[000]"
                 and C$ is our base number (1, or 2, or - much later - 100)
                 LTRIM is in there to prevent "0.00 1"
D=D+A            Add A$ to the end of D$ ("0.00" becomes "0.000")
~d=a|_X]         Stop if we've reached the max. # of terms
]                NEXT
q=q+1            If we've done all the terms necessary with this base number
                 then raise base number.
The DO loop gets closed implicitly by QBIC.

```

---

Edit: QBIC has seen quite some development over time, and the above can now be solved in 49 bytes, 15 bytes shorter:

```
{D=@0.`[0,q*100|d=d+1?D+!q$┘D=D+@0`~d=a|_X]]q=q+1

```
> 3 votes

# Answer
# PHP, 83 Bytes

```
for($s=1;$i++<$argv[1];){if($r>100*$s){$s++;$r=0;}echo" 0.".str_repeat(0,$r++).$s;}

```
> 2 votes

# Answer
## PowerShell v2+, 89 bytes

```
param($n)for($j=1;;$j++){for($i=0;$i-le100*$j;$i++){"0.$('0'*$i)$j";if(++$k-ge$n){exit}}}

```

Straight-up double-`for` loop. The first, for `$j` is infinite. The inner, for `$i`, loops from `0` up to `100*$j`, using string concatenation and string multiplication to print out the appropriate item. It also checks total loop counter `$k` against input `$n`, and `exit`s the program after we hit that point.
> 2 votes

# Answer
# GNU sed 163 157

+2 included for -rn

```
s,^,0.1\n,;:;P;s,\.,.0,;s,.$,,;/0{101}/{s,0\.0*(09)?,\1,
s,.9*\n,x&,;h;s,.*x(.*)\n.*,\1,;y,0123456789,1234567890,
G;s,(.*\n)(.*)x.*\n(.*),0.\2\1\3,};/\n./b

```

Takes input in unary based in this consensus.

Try it online!

---

An easy way to run this is:

```
 yes 1 | head -{input} | tr -d '\n' | sed -rnf zeroOne.sed

```

---

**Explanation**

```
s,^,0.1\n,                   #add 0.1 as the first line of the pattern space
:
P                            #print everything up to the first newline
s,\.,.0,                     #add a 0 after the .
s,.$,,                       #reduce the number left to print by one
/0{100}/{                    #if there is a string of 100 zero do the following
    s,0\.0*(09)?,\1,                 #get rid of all the 0s (except one if the we are adding another digit)
    s,.9*\n,x&,              #put an x before the left most number that will change
    h                        #store in hold space
    s,.*x(.*)\n.*,\1,        #remove everything except the numbers that change
    y,0123456789,1234567890, #replace numbers with the next one up
    G                        #bring the rest of the string back
    s,(.*\n)(.*)x.*\n(.*),0.\2\1\3,
                             #replace the x and numbers that changed with the new ones
}
/\n./b                   #branch back unless there isn't anything on the last line

```
> 2 votes

# Answer
# Mathematica, 70 bytes

```
Take[Join@@Table["0."<>Array["0"&,k]<>ToString@m,{m,#},{k,0,100m}],#]&

```

Unnamed function that takes the desired length as its argument and returns a list of strings (using strings instead of numbers makes the trailing zeros easy to include).

This version is slow as hell! because if you want, for example, the first 10 terms, it actually computes the sequence all the way through the 10th segment (101 + 201 + ... + 1001 = 5510 terms) and then retains only the first 10. So already at input 303, it's computing nearly five million terms and discarding almost all of them. The **81**-byte version

```
Take[Join@@Table["0."<>Array["0"&,k]<>ToString@m,{m,Sqrt[#/50]+1},{k,0,100m}],#]&

```

doesn't have this flaw, and in fact calculates nearly the fewest segments possible.
> 2 votes

# Answer
# JavaScript (ES6), 69

```
n=>[...Array(n)].map(_=>(w=l--?z:(l=++x*100,z='0.'),z+=0,w+x),l=x=0)

```

Unnamed function with desired length in input and returning an array of strings.

**Test**

```
f=
n=>[...Array(n)].map(_=>(w=l--?z:(l=++x*100,z='0.'),z+=0,w+x),l=x=0)

var tid=0
function exec()
{
    var n=+I.value;
    O.textContent=f(n).map((r,i)=>i+1+' '+r).join`\n`;
}

function update()
{
  clearTimeout(tid);
  tid=setTimeout(exec, 1000);
}

exec()
```

```
<input id=I value=305 type=number oninput='update()'><pre id=O></pre>
```
> 2 votes

# Answer
# dc, 71 bytes

```
sn1sj1si1[lj1+dddsjZ1-dkAr^/li1+si]sJ[0nK1+kA/pljA0*K=Jlnlid1+si<M]dsMx

```

Try it online!

Honestly, I thought taking advantage of dc's arbitrary precision would make this easy, but I'm pretty sure just printing a ton of zeroes will be golfier. It feels really suboptimal, but I still think the use of arbitrary precision is interesting.

`sn1sj1si1` We're taking top-of-stack as our nth-term target, so we store it in `n`, initialize `i` and `j` at 1, and leave a 1 on the stack.

`[lj1+dddsjZ1-dkAr^/li1+si]sJ` Macro `J` handles what to do when we've hit the 100, 200, &c. mark. Counter `j` keeps track of this, so we increment it, we set our precision to the number of digits it has less one, and then we leave the first digit of it (`Z1-Ar^/`; divide by 10^(number of digits less one)) on the stack since this is our starting point for the next big long chain.

`[0nK1+kA/pljA0*K=Jlnlid1+si<M]dsMx` Our main macro. First we print a leading 0 with `0n`. Then `K1+k` increments our precision by one place. `A/` divides by ten, pushing us a place over to the right.`p` prints, and then the rest is housekeeping. We can test our current precision to determine whether or not we need to jump into macro `J`, so we multiply counter `j` by a hundred (note: `A0` here may need to be replaced with `100` on some implementations (cygwin)) and do the comparison. We load `n`, our target nth term, increment our main counter, `i`, and then compare the two. If we haven't yet hit the target, we keep running `M`.
> 1 votes

# Answer
# Excel VBA, 63 Bytes

Anonymous VBE immediate window function that takes input from range `[A1]` and outputs to the VBE immediate window

```
n=[A1]:While n>i*100:n=n-1-i*100:i=i+1:Wend:?"0."String(n,48)&i

```
> 1 votes

# Answer
# Java 8, 120 bytes

```
n->{String r="";a:for(int i=1,j,k,c=n;;i++)for(j=0;j<=i*100;r+=i+"\n"){for(r+="0.",k=j++;k-->0;r+=0);if(c--<1)break a;}}

```

Explanation and TIO uses the one below however. The difference: the one above creates one big String and then returns it; the one below prints every line separately (which is much better for performance).

**130 bytes:**

```
n->{String r;a:for(int i=1,j,k,c=n;;i++)for(j=0;j<=i*100;System.out.println(r+i)){for(r="0.",k=j++;k-->0;r+=0);if(c--<1)break a;}}

```

**Explanation:**

Try it here. (Will time out or exceed output limit for test cases above `604`, but locally test case `4510` works in below 2 seconds.)

```
n->{                  // Method with integer parameter and no return-type
  String r;           //  Row String
  a:for(int i=1,      //  Index integer `i` starting at 1
        j,k,          //  Some other index integers
        c=n           //  Counter integer starting at the input
        ;;i++)        //  Loop (1) indefinitely
      for(j=0;        //   Reset `j` to 0
          j<=i*100;   //   Loop (2) from 0 to `i*100` (inclusive)
          System.out.println(r+i)){
                      //     After every iteration: print `r+i` + new-line
        for(r="0.",   //    Reset row-String to "0."
            k=j++;    //    Reset `k` to `j`
            k-->0;    //    Loop (3) from `j` down to `0`
          r+=0        //     And append the row-String with "0"
        );            //    End of loop (3)
        if(c--<1)     //    As soon as we've outputted `n` items
          break a;    //     Break loop `a` (1)
      }               //   End of loop (2) (implicit / single-line body)
                      //  End of loop (1) (implicit / single-line body)
}                     // End of method

```
> 0 votes

---
Tags: code-golf, sequence
---


title: Chain reaction of bombs

text:
# Question
Title: Chain reaction of bombs
## Introduction:

Before the task, here is what every element does on the map:

**Plain land** (`X`): This does nothing.

**Destroyed land** (`-`): This is the same as plain land, but destroyed by a bomb.

**The active bomb** (`!`): On a map, this will destroy everything in a 3x3 square:

```
XXXXX                         XXXXX
XXXXX                         X---X
XX!XX     > will become >     X---X
XXXXX                         X---X
XXXXX                         XXXXX

```

**The passive bomb** (`@`): It does nothing, until it is detonated by another bomb. This also has a **3x3** square explosion radius:

```
XXXXX                         XXXXX
XXXXX                         XXXXX
XX@XX     > will become >     XX@XX (nothing happened)
XXXXX                         XXXXX
XXXXX                         XXXXX

```

But:

```
XXXXX                         XXXXX
XXXXX                         X---X
XX@XX     > will become >     ----X (both bombs have exploded)
X!XXX                         ----X
XXXXX                         ---XX

```

**The nuke** (`~`): It does nothing, until it is detonated by another bomb. The difference is that this bomb has a **5x5** square explosion radius:

```
XXXXX                         XXXXX
XXXXX                         XXXXX
XX~XX     > will become >     XX~XX (nothing happened)
XXXXX                         XXXXX
XXXXX                         XXXXX

```

But:

```
XXXXX                         -----
XXXXX                         -----
XX~XX     > will become >     ----- (both bombs have exploded)
X!XXX                         -----
XXXXX                         -----

```

## The task

* Given a **9x9 map**, output the map *after* the chain reaction.
* You may provide a function or a program.
* This is , so the submission with the least amount of bytes wins!

## Test cases

Test case 1 (*3 steps*):

```
XXXXXXXXX           XXXXXXXXX
----XXXXX           ----XXXXX
XXXX@XXXX           XXXX@XXXX
XXXXXXXX-           XXX---XX-
XXXX@XXXX     >     ------XXX
XXXXXXXX-           ------XX-
XX~XXXXXX           -----XXXX
X!XXXXXX-           -----XXX-
XXXXXXXXX           -----XXXX

```

Test case 2 (*2 steps*):

```
XXXXXXXXX           XXXXXXXXX
XXXXXXXXX           XXXXXXXXX
XX~XXXXXX           XX~XXXXXX
---------           ---------
XXXX!XXXX     >     XXX---XXX
XXXXXXXXX           XXX------
XXX@@X@!X           XXX@@----
XXXXXXXXX           XXXXX----
XXXXXXXXX           XXXXXXXXX

```

Test case 3 (*2 steps*):

```
XXXXXXXXX           XXXXXXXXX
XXXXXXXXX           XXXXXXXXX
XX~XXXXXX           XX~XXXXXX
XXXXXXXXX           XXX---XXX
XXXX!XXXX     >     XXX---XXX
XXXXXXXXX           XXX------
XXX@@X@!X           XXX@@----
XXXXXXXXX           XXXXX----
XXXXXXXXX           XXXXXXXXX

```

Test case 4 (*1 step*):

```
XXXXXXXXX           XXXXXXXXX
XXXX-XXXX           XXXX-XXXX
XXXXXXXXX           XXX---XXX
XX-X!X-XX           XX-----XX
XXXXXXXXX     >     XXX---XXX
XX-----XX           XX-----XX
XXXX-XXXX           XXXX-XXXX
XXXXXXXXX           XXXXXXXXX
XXXXXXXXX           XXXXXXXXX

```

Test case 5 (*9 steps*):

```
!XXXXXXXX           ---XXXXXX
X@XXXXXXX           ----XXXXX
XX@XXXXXX           -----XXXX
XXX@XXXXX           X-----XXX
XXXX@XXXX     >     XX-----XX
XXXXX@XXX           XXX-----X
XXXXXX@XX           XXXX-----
XXXXXXX@X           XXXXX----
XXXXXXXX@           XXXXXX---

```

Test case 6 (*9 steps*):

```
XX@@@XXXX           ------XXX
XXXXXXXXX           ------XXX
~XXXXXXXX           ---XXXXXX
XXXXXXXXX           ---XXXXXX
~XXXXXXXX     >     ---XXXXXX
XXXXXXXXX           ---XXXXXX
~XXXXXXXX           ---XXXXXX
@XXXXXXXX           ---XXXXXX
!XXXXXXXX           ---XXXXXX

```

Test case 7 (*3 steps*):

```
!XXXXXXXX           ---XXXXXX
X@XXXXXXX           ----XXXXX
XX@XXXXXX           ----XXXXX
XXXXXXXXX           X---X----
XXXXXX@@!     >     XXXXX----
XXXXXXXXX           X---X----
XX@XXXXXX           ----XXXXX
X@XXXXXXX           ----XXXXX
!XXXXXXXX           ---XXXXXX

```

# Answer
> 11 votes
# Matlab, ~~120~~ 111 bytes

```
function f=c(f);c=@(x,i)conv2(x+0,ones(i),'s');a=c(f<34,3);for k=f;a=c(a&f<65,3)|a;a=c(a&f>99,5)|a;end;f(a)='-'

```

> Convolution is the key to success.

The idea is following: Find the active bomb. Enlarge this area to a 3x3 square. Find new affected bombs, enlarge the correspoding areas to the corresponding size and add those to the previously destroyed area. Repeat this enough times (in my case as many times as we have input characters, just because that is the shortest variant) to be sure that we reached a stationary point (=no more exploding bombs). Then set all the destroyed area to `-` and display the result.

The input is assumed to be a matrix of characters, e.g.

```
['!XXXXXXXX';
'X@XXXXXXX';
'XX@XXXXXX';
'XXX@XXXXX';
'XXXX@XXXX';
'XXXXX@XXX';
'XXXXXX@XX';
'XXXXXXX@X';
'XXXXXXXX@'];

```

# Answer
> 10 votes
## Retina, ~~188~~ ~~168~~ ~~154~~ 152 bytes

Bytes counted as ISO 8859-1.

```
+Tm`@~X!:`!:\-`(.)?.?.(.?(?<1>.)?)(?<=(:|(?(1)_)!|^(?(5)_)(?<-5>.)*(:|(?(1)_)!)(?<1>.*¶)?.*¶(.)*.|(?=(.)*¶.*(?<1>¶.*)?(:|(?(1)_)!)(?<-6>.)*(?(6)_)$))\2)

```

Try it online!

~~This is more of a proof of concept. There is a horrible amount of duplication between bombs and nukes, which I'll try to get rid of before adding an explanation.~~ Well, I got rid of that duplication but it increased the complexity significantly so it didn't actually result in huge savings...

# Answer
> 8 votes
# APL (Dyalog), 56 chars or 62 bytes\*

My colleague Marshall came up with an elegant solution, 21 characters shorter than mine:

```
{'-'@(({1∊⍵≥∘.⌈⍨5⍴1+4↑1}⌺5 5×∘(('X'≠⍵)+'~'=⍵))⍣≡'!'∘=)⍵}

```

Try it online!

`{``}` anonymous function where the argument is represented by

`'-'@(``)⍵`*dash* **at** the positions masked by the following tacit function:

`'!'∘=` Boolean where exclamation point equals the argument

`(``)⍣≡` apply the following tacit function until nothing more changes:

`×∘(``)` multiply by the following constant:

`'~'=⍵` Boolean where tilde equals the original argument

`(``)+` to that, add:

`'X'≠⍵` Boolean where X is different from the original argument

`{``}⌺5 5` for each, apply the following function on the 5×5 area centered on it:

`4↑1` take the first four elements of one, padding with zeros \[1,0,0,0\]

`1+` add one \[2,1,1,1\]

`5⍴` reshape cyclically into length five \[2,1,1,1,2\]

`∘.⌈⍨` maximum table with itself on both axes

`⍵≥` Boolean where the corresponding neighbours are greater than or equal to that

`1∊` Boolean if any is true

---

<sup>* Just replace  with `⎕U233A`  under Classic for single byte per character.</sup>

# Answer
> 4 votes
# Java, ~~574~~ ~~562~~ ~~558~~ ~~549~~ ~~525~~ 523 bytes

```
import java.util.*;interface B{static char[][]g=new char[9][9];static void d(int i,int j,int r){g[i][j]=45;for(int x=Math.max(i-r,0);x<Math.min(i+r+1,9);x++)for(int y=Math.max(j-r,0);y<Math.min(j+r+1,9);y++)if(g[x][y]==64){d(x,y,1);}else if(g[x][y]>99){d(x,y,2);}else g[x][y]=45;}static void main(String[]a){Scanner q=new Scanner(System.in);for(int i=0;i<9;i++){int j=0;for(char c:q.nextLine().toCharArray())g[i][j++]=c;}for(int j=0;j<9;j++)for(int k=0;k<9;k++)if(g[j][k]==33)d(j,k,1);for(char[]z:g)System.out.println(z);}}

```

# Answer
> 1 votes
# APL (Dyalog Classic), 61 bytes

```
'-'@({i/⍨∨⌿↑(↓⌈/¨|⍵∘.-i)≤3|'X@~-'⍳a[⍵]}⍣≡('!'=,a)/i←,⍳⍴a)⊢a←⎕

```

Try it online!

`a←⎕` evaluate input and assign to `a`

`i←,⍳⍴a` the indices (pairs of coords) of all cells

`('!'=,a)/` filter only the initially active bombs

`{ }⍣≡` perform a transformation on the list until it stabilizes

* `'X@~-'⍳a[⍵]` substitute 0 for `X`, 1 for `@`, etc, 4 for anything else (`!`)
* `3|` mod 3 to get the "radius" of impact; it must be greater or equal to the...
* `(↓⌈/¨|⍵∘.-i)≤` ...Manhattan distances between cells in the list and all cells
* `i/⍨∨⌿↑` get bitmask of which cells are affected and select those from `i`

`'-'@( )⊢a` put `-` at those positions

---
Tags: code-golf, ascii-art, grid
---


# Question
Title: EOC Vault Password Rank 3 Puzzle - Vault Password
## The shortest reliable password testing code

**Introduction**

I started playing Empire of Code recently, and there was some challenge. The player is supposed to write a piece of Python or Javascript code to detect if the string passed to it is reliable password, that is, it contains at least one lowercase Latin letter, one uppercase Latin letter and one digit and has at least 10 characters.

It was quite easy for me to fit within the 130 characters limit for rank 3 using Javascript, however, I spent a lot of time trying to fit within the 100 characters limit for rank 3 using Python. Some guy said that he has managed to fit in 71 characters for Python. I tried hard but still couldn't reduce the code to less than 90 characters. Is it possible to use even less than 71 characters?

**Winning condition:** The shortest Python code (or Javascript), which solves given problem, wins. You may assume whatever was assumed in the original problem description in the game, given below.

*Remark:* The solution should define a function or method called "golf" which takes the password as the first parameter and returns a boolean value indicating whether the given password satisfies the criterion.

> **Challenge Vault Password**
> <sub>\[The following description is merged from two versions of the problem description (for Python and for Javascript), copied from the game site https://empireofcode.com/ \]</sub>
>
> We've installed a new vault to contain our valuable resources and treasures, but before we can put anything into it, we need a suitable password for our new vault. One that should be as safe as possible.
>
> The password will be considered strong enough if its length is greater than or equal to 10 characters, it contains at least one digit, as well as at least one uppercase letter and one lowercase letter. The password may only contain ASCII latin letters or digits, no punctuation symbols.
>
> You are given a password. We need your code to verify if it meets the conditions for a secure password.
>
> In this mission the main goal to make your code as short as possible. The shorter your code, the more points you earn. Your score for this mission is dynamic and directly related to the length of your code.
>
> **Input:** A password as a string.
>
> **Output:** A determination if the password safe or not as a boolean, or any data type that can be converted and processed as a boolean. When the results process, you will see the converted results.
>
> **Example:**
>
> golf('A1213pokl') === false
>
> golf('bAse730onE') === true
>
> golf('asasasasasasasaas') === false
>
> golf('QWERTYqwerty') === false
>
> golf('123456123456') === false
>
> golf('QwErTy911poqqqq') === true
>
> **Precondition:**
>
> 0 \< |password| ≤ 64
>
> The password matches the regexp expression "\[a-zA-Z0-9\]+"
>
> **Scoring:**
>
> Scoring in this mission is based on the number of characters used in your code (comment lines are not counted).
>
> **Rank1:**
>
> Any code length.
>
> **Rank2:**
>
> Your code should be shorter than 230 characters for Javascript code or shorter than 200 characters for Python code.
>
> **Rank3:**
>
> Your code should be shorter than 130 characters for Javascript code or shorter than 100 characters for Python code.

# Answer
> 6 votes
# Python, 59 bytes

```
golf=lambda s:(9<len(s))*(s.lower()>s>s.upper())*'?'>min(s)

```

(Still) probably not optimal.

# Answer
> 1 votes
# JavaScript ES6, 67 - ES5, 88

Slightly longer than necessary as it has to return a proper true/false value (not truthy/falsy)

```
// MORE COMMON JAVASCRIPT - ECMASCRIPT 5 - 88 byte
function golf(p){return!(!~(p.search(/\d/)|p.search("[a-z]")|p.search("[A-Z]"))||!p[9])}

// NEWEST JAVASCRIPT - ECMASCRIPT 6 - 67 byte
/*
golf=p=>!(!~(p.search`\\d`|p.search`[a-z]`|p.search`[A-Z]`)||!p[9])
*/

// Explanation
// search gives -1 if not found, if any of search results is -1 then ORing we have a result of -1
// ~ operator is 0 if and only if operand is -1
// !p[9] is true if the string has less than 10 characters

// TEST
function out(x) {
  O.innerHTML += x + '\n'
};

;[['A1213pokl',0],['bAse730onE',1],['asasasasasasasaas',0],['QWERTYqwerty',0],['123456123456',0],['QwErTy911poqqqq',1]]
.forEach(function(pwd){out(pwd[0]+' '+!!pwd[1]+' '+golf(pwd[0]))})
```

```
<pre id=O></pre>
```

# Answer
> 1 votes
# JavaScript – 83 bytes

```
function golf(x){return!!(/\d/.test(x)&/[a-z]/.test(x)&/[A-Z]/.test(x)&x.length>9)}

```

# Answer
> 1 votes
# Python, 83 bytes

Alternatively, you can try this (**93 bytes**):

```
import re
def golf(p):
    return bool(re.findall(r'(?=.*[a-z])(?=.*[A-Z])(?=.*\d).{10,}',p))

```

or (**83 bytes**)

```
import re
golf=lambda p:bool(re.findall(r'(?=.*[a-z])(?=.*[A-Z])(?=.*\d).{10,}',p))

```

Try it online!

# Answer
> 0 votes
The solution on Python I could implement, 90 bytes

```
import re
golf=lambda p:re.compile(r'(?=.{10,})(?=.*\d)(?=.*[a-z])(?=.*[A-Z])').search(p)

```

---
Tags: code-golf
---


title: Casciitum Scribe

text:
# Question
Title: Casciitum Scribe
# Introduction

Cacti come in various different sizes, shapes and colors. However, the most iconic cactus and must-have in every Western has to be the saguaro. Important features are its size and arms, which have defined the stereotypical cactus appearance.

Your task is to bring the saguaro in the ASCII world. However, -- as in the real world -- no saguaro is like another, so your program has to be able to generate saguaros with varying arm configurations.

# An example saguaro

> * Input: `[0b10, 0b11]` (`[2, 3]` in decimal, input length of `2`)

```
     _
    / \
 _  | |
/ \ | |
| | | |
\ \_| |
 \__  |
    \ |
 _  | |  _
/ \ | | / \
| | | | | |
\ \_| |_/ /
 \__   __/
    \ /
    | |
    | |
```

# Specifications

A saguaro always has a base and a top, with variable amounts of stem in between. The stem parts can have no arms, an arm on the right, one on the left or two arms.

Saguaro growth patterns are given as an input list containing two-bit values. `00` means no arms, `01` an arm on the right, `10` an arm on the left and `11` two arms (all in binary). The input list's length determines the saguaro's height.

Saguaro sections look like the following. Cactus parts are surrounded by octothorps, `#`, for clarity which shall not be printed.
A saguaro's height is always equal to `4+6*k` characters for nonnegative integers `k`.

```
#############
#     _     # Saguaro top
#    / \    #
#############
# _  | |  _ # Stem, both arms
#/ \ | | / \# Stem id: 11
#| | | | | |#
#\ \_| |_/ /#
# \__   __/ #
#    \ /    #
#############
# _  | |    # Stem, left arm
#/ \ | |    # Stem id: 10
#| | | |    #
#\ \_| |    #
# \__  |    #
#    \ |    #
#############
#    | |  _ # Stem, right arm
#    | | / \# Stem id: 01
#    | | | |#
#    | |_/ /#
#    |  __/ #
#    | /    #
#############
#    | |    # Stem, no arms
#    | |    # Stem id: 00
#    | |    #
#    | |    #
#    | |    #
#    | |    #
#############
#    | |    # Saguaro base
#    | |    #
#############
```

# Input

As previously said, the input consists of a list of two-bit values (`0, 1, 2, 3` in decimal). It can be given in any reasonable format. The list's first element corresponds to the saguaro's highest stem part, the second element to its second highest stem part, etc.
If you want, you can require the input list's length as an additional input. Please specify it in your answer if you do so.

# Output

Your output ASCII saguaro should be built using the exact stem parts as described above. Trailing spaces on a line and trailing new lines are ignored; you may print more, fewer or as many as specified above.

# Rules

# Test cases

> * An outlier. Input: `[0b01, 0b00, 0b01, 0b11]`

```
     _
    / \
    | |  _
    | | / \
    | | | |
    | |_/ /
    |  __/
    | /
    | |
    | |
    | |
    | |
    | |
    | |
    | |  _
    | | / \
    | | | |
    | |_/ /
    |  __/
    | /
 _  | |  _
/ \ | | / \
| | | | | |
\ \_| |_/ /
 \__   __/
    \ /
    | |
    | |
```

---

> * Alternating arms. Input: `[0b10, 0b01, 0b10]`

```
     _
    / \
 _  | |
/ \ | |
| | | |
\ \_| |
 \__  |
    \ |
    | |  _
    | | / \
    | | | |
    | |_/ /
    |  __/
    | /
 _  | |
/ \ | |
| | | |
\ \_| |
 \__  |
    \ |
    | |
    | |
```

---

> * An abundance of arms. Input: `[0b11, 0b11]`

```
     _
    / \
 _  | |  _
/ \ | | / \
| | | | | |
\ \_| |_/ /
 \__   __/
    \ /
 _  | |  _
/ \ | | / \
| | | | | |
\ \_| |_/ /
 \__   __/
    \ /
    | |
    | |
```

---

> * No arms, also known as a spear. Input: `[0b00]`

```
     _
    / \
    | |
    | |
    | |
    | |
    | |
    | |
    | |
    | |
```

---

> * No body, some call it a young cactus. Input: `[]`

```
     _
    / \
    | |
    | |
```

---

# Answer
# Charcoal, ~~50~~ 49 bytes

```
↘_\¶/Ｆ²«Ｊ¹¦²Ｆθ¿﹪÷Ｉκ⁺¹ι²”{➙∧⊟≕δaL7ＹF¬⊕ρ↥↖_K”↓⁶↓²‖Ｔ

```

Try it online! Link is to verbose version of code. Explanation:

```
↘_\¶/

```

Draw the top.

```
Ｆ²«

```

Loop over each side.

```
Ｊ¹¦²

```

Jump to just under the right side of the top.

```
Ｆθ

```

Loop over each stem part.

```
¿﹪÷Ｉκ⁺¹ι²

```

Test whether there is an arm.

```
”{➙∧⊟≕δaL7ＹF¬⊕ρ↥↖_K”

```

If so print an arm.

```
↓⁶

```

Otherwise just print a vertical line.

```
↓²

```

After printing the stem, print the base.

```
‖Ｔ

```

Reflect ready to draw the other side. Once both sides are drawn, the sides are then reflected back into their final position.
> 10 votes

# Answer
# JavaScript (ES6), 210 bytes

I spent far too long on another solution before realising there was a better way, which didn't leave me as much time as I would've liked to work on this.

```
a=>`     _
    / \\`+a.map(([x,y])=>`
 1  | |  2
3 5 | | 4 6
7 7 | | 8 8
5 51| |24 4
 511${`| `[x]} ${`| `[y]}224
    ${`|\\`[x]} `.replace(/\d/g,m=>` _/\\|`[m%2?x*-~m/2:y*m/2])+`|/`[y],s=`
    | |`).join``+s+s

```

---

## Try it

```
o.innerText=(f=
a=>`     _
    / \\`+a.map(([x,y])=>`
 1  | |  2
3 5 | | 4 6
7 7 | | 8 8
5 51| |24 4
 511${"| "[x]} ${"| "[y]}224
    ${"|\\"[x]} `.replace(/\d/g,m=>` _/\\|`[m%2?x*-~m/2:y*m/2])+"|/"[y],s=`
    | |`).join``+s+s
)(i.value=["11","10","01","00"]);oninput=_=>o.innerText=f(i.value.split`,`)
```

```
<input id=i><pre id=o>
```
> 7 votes

# Answer
# Python 2, 189 bytes

```
lambda l:'     _\n    / \\\n'+'\n'.join(('    |',' /|\  _   \  \|\_    __ |||| \\'[j::6])[i/2]+' '+('|','|||| /   __  /|/_ _   /  \|/'[j::6])[i%2]for i in l for j in range(6))+'\n    | |'*2

```

Try it online!
> 5 votes

# Answer
# Python 2, ~~256~~ ~~253...205~~ ~~203~~ 199 bytes

```
r=[('     _',''),('/','\ ')]
for a in input()+[0]:r+=zip(*[['|'*6,'_|    |_,,/|  \/  |\,,||  ||  ||,,\| _\/_ |/,,\ ____ /,,\/'[i::2].split(',')][2-i&a>0]for i in 0,1])
for l in r[:-4]:print'%5s %s'%l

```

Try it online!
> 3 votes

# Answer
# Java (OpenJDK 8), ~~626~~ ~~566~~ ~~499~~ ~~466~~ ~~398~~ ~~312~~ ~~310~~ 308 bytes

Can be golfed a tonne

```
a->{String r=" |,",g="    |",n="     _,    / \\,";boolean j,k;for(int e:a)n+=((k=e>1)?" _  |":g)+((j=e%2>0)?" |  _,":r)+(k?"/ \\ |":g)+(j?" | / \\,":r)+(k?"| | |":g)+(j?" | | |,":r)+(k?"\\ \\_|":g)+(j?" |_/ /,":r)+(k?" \\__ ":g)+(j?"  __/,":r)+(k?"    \\":g)+(j?" /,":r);return(n+g+r+g+r).replace(",","\n");}

```

Try it online!
> 1 votes

# Answer
# PowerShell, 235 bytes

```
param($a)'     _
    / \'
($a|%{((,'1|'*6),('1|  _
1| / \
1|2
1|_/ /
1 __/
1/'),(' _ 2
/ \2
| |2
\ \_| |
 \__  |
    \ |'),(' _ 2  _
/ \2 / \
| |22
\ \_| |_/ /
 \__   __/
    \ /'))[$_]})-replace1,'    | '-replace2,' | |'
,'    | |'*2

```

Try it online!

PowerShell doesn't have a `map` or `zip` or a real easy way to reverse strings, so we're left with something else -- simple replacements of repeated sections.

The first two lines take input as an array of integers and output the top of the cactus. Then we loop through `$a` and select into an array of four strings based on the current value. Those strings are left on the pipeline and then we use our `-replace` to fill in the appropriate spots. We then put the bottom of the cactus onto the pipeline as well.

Everything is gathered from the pipeline and an implicit `Write-Output` happens at program completion, inserting a newline between every element.
> 1 votes

# Answer
# 05AB1E, ~~76~~ 75 bytes

```
„ _…/ \‚4ú»,v6F'|4ú"_ |/\"•Aö¡Èèj{^ë•5вèJ5ôNè©‚y1›èð'|®∞2äθ‚yÉèJ,}}„| 4úû=,

```

Try it online!
> 1 votes

# Answer
# SOGL V0.12, ~~56~~ ~~54~~ 53 bytes

```
5⁷yΙ‚‘∑≡`a#¾‘O.{@.2%i»¹{"⁸G‘6∙;?X"j1>ζ╔²i[n¹‘5n}┼±↔}O

```

Try it Here!

Explanation:

```
..‘                   push the ending part - "    | |\n    | |"
   ..‘O               output the starting part - "     _ \n    / \"
       .{             input times do
         @              push a space
          .2%           push input%2
             i»         push floor(prevInput/2)
               ¹        wrap the two in an array

{                   }   for each of the two numbers
 "..‘                     push "|    " - base stem
     6∙                   multiply vertically 6 times
       ;?       }         if the current item iterating over is truthy (i.e. != 0)
         X                  remove ToS - the regular stem - from the stack
          "..‘              push "|  _ | / \| | ||_/ / __/ /    " - stem with an arm
              5n            split it into line lengths of 5
                 ┼        add that horizontally to the space pushed earlier (or whatever it's become)
                  ±↔      reverse ToS - the stem currently - horizontally
                     O  output the array of the current part

```
> 0 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---


title: Finding Snakes in a Matrix

text:
# Question
Title: Finding Snakes in a Matrix
# Challenge

Given a binary matrix and a binary string, determine if that binary string can be found starting at any point in the matrix and moving in any direction at any subsequent point to form the binary string. That is, can the string be found folded up however inside the matrix?

The string can only be folded at 90 degrees or 180 degrees (edge connections; Manhattan Distance 1) and cannot overlap itself at any point.

# Example

Let's take the following example:

```
Matrix:

010101
111011
011010
011011

Snake: 0111111100101

```

This is a truthy test case. We can see the snake folded up in the following position:

```
0-1 0 1 0 1
  |
1 1 1-0 1 1
  | | |   |
0 1 1 0-1-0
  | |
0 1-1 0 1 1

```

# Rules

* Standard Loopholes Apply
* You may take the length of the string and the width and height of the matrix as input if you'd like
* You may take the binary matrix and the binary string as a multiline string/array of strings/newline-joined string/anything else-joined string and a string
* You may take the dimensions as a flat array instead of several arguments
* Your program must finish for any 5 x 5 matrix with any string of up to length 10 in under a minute

# Limitations

* The matrix is not necessarily square
* The string will be non-empty
* The string can be length-1
* The string will not contain more squares than available (that is, `len(string) <= width(matrix) * height(matrix)`

# Test Cases

Truthy

```
01010
10101
01010
10101
01010

0101010101010101010101010

01110
01100
10010
10110
01101

011111000110100

0

0

10
01

1010

100
010
001

100010001

```

Falsy

```
00000
00000
00000
00000
00000

1

10101
01010
10101
01010
10101

11

100
010
001

111

10001
01010
00100
01010
10001

1000100010001000101010100

```

# Answer
# Python 2, ~~275~~ ~~271~~ ~~264~~ 249 bytes

* Saved four bytes by replacing `-1` with `H` and removing one slicing operation (`[:]`).
* Saved seven bytes thanks to Halvard Hummel; removing yet another slicing operation (`[:]`), using multiple-target assignment to give a visited entry a value `v not in "01"` (`S=S[1:];M[y][x]=H;` -\> `S=M[y][x]=S[1:];`) and switching from a ternary if/else to a simple logical or (`any(...)if S else 1` -\> `not S or any(...)`).
* If you somewhat extend your definition of *truthy* and *falsey*, you could allow this 257 byte long solution. It raises an exception (`ZeroDivisionError`) when the snake is found and returns an empty list (`[]`) when there is no snake to be found, which are two distinct behaviours.
* Saved fourteen bytes thanks to user202729; golfing two array deep copies
* Saved a byte; golfed `not S or` to `S<[1]or` ~ `S==[]or`.

```
lambda M,S,w,h:any(H(eval(`M`),S,w,h,x,y)for y in range(h)for x in range(w)if S[0]==M[y][x])
def H(M,S,w,h,x,y):S=M[y][x]=S[1:];return S<[1]or any(H(eval(`M`),S,w,h,x+X,y+Y)for X,Y in[(~0,0),(1,0),(0,~0),(0,1)]if~0<x+X<w>0<=y+Y<h!=S[0]==M[y+Y][x+X])

```

Try it online!

# Explanation

Lambda function which takes in the matrix as a two-dimensional list of strings (either `"0"` or `"1"`), the snake as a one-dimensional list and the matrix dimensions as two integers.
The lambda function searches the matrix for entries that match the snake's first element. For every found match, it calls `H` with a deep copy of the matrix, no copy of the snake, the matrix dimensions and the match's position.

When `H` is called, it removes `S`' first entry and sets the given position's matrix entry to something else than `"0", "1"`. If `S`' length is zero, it returns `True`; as it calls itself recursively, the snake was found somewhere in the matrix.
If `S`' length is non-zero, it loops through the four cardinal directions, tests if that position is in the matrix, compares the matrix' element at that position with the first element of `S` and -- if it matches -- calls itself recursively.
`H`'s return values are funneled up the stack frames, always checking if at least one function found a possible snake.

# Formatted Output

I have augmented my program to also output the path the snake slithers (if there is one). It uses the same ASCII output design as the question. TIO link.
> 13 votes

# Answer
# JavaScript (ES6), ~~138~~ 134

Not so different from @Neil's, but what else could it be?

Input: matrix as a multi line string, binary string, width (not counting newline)

NB: the logic in the recursive function `r` is somewhat inverted to save a couple of bytes

```
(m,s,w)=>[...m].some((c,p,m,r=(p,o)=>s[m[p]=r,o]&&([~w,-~w,1,-1].every(d=>m[d+=p]!=s[o]||r(d,o+1))&&(m[p]=s[o-1])))=>c==s[0]&&!r(p,1))

```

*Less golfed*

```
(m,s,w)=>(
  m=[...m],
  r= (p, o) =>
    (m[p] = -w, s[o])
    && (
         [~w, -~w, 1, -1].every( d =>
            m[d+=p] != s[o] || r(d, o+1)
         )
         && (m[p]=s[o-1])
    ),
  m.some((c,p) =>c == s[0] && !r(p,1))
)

```

**Test**

```
var F=
(m,s,w)=>[...m].some((c,p,m,r=(p,o)=>s[m[p]=r,o]&&([~w,-~w,1,-1].every(d=>m[d+=p]!=s[o]||r(d,o+1))&&(m[p]=s[o-1])))=>c==s[0]&&!r(p,1))

// this slightly modified version tracks the path
var Mark=
(m,s,w)=>(m=[...m]).some((c,p,m,r=(p,o)=>s[m[p]=-o,o]&&([~w,-~w,1,-1].every(d=>m[d+=p]!=s[o]||r(d,o+1))&&(m[p]=s[o-1])))=>c==s[0]&&!r(p,1))
?m.map((c,p)=>c<-1?'.───│┘└.│┐┌.│'[((m[p-1]-c)**2<2)+((m[p+1]-c)**2<2)*2+((m[p+~w]-c)**2<2)*4+((m[p-~w]-c)**2<2)*8]:c<0?'*':c).join``:''

function go()
{
  O.textContent =F(M.value, S.value, M.value.search('\n'))+'\n\n'
  +Mark(M.value, S.value, M.value.search('\n'))
}

go()
```

```
#M {width:100px; height:100px }
```

```
<textarea id=M>010101
111011
011010
011011</textarea><br>
<input id=S value='0111111100101' oninput='go()'>
<button onclick='go()'>go</button>
<pre id=O></pre>
```
> 9 votes

# Answer
## JavaScript (ES6), 149 bytes

```
(m,s,w)=>[...m].some((c,i)=>c==s[0]&&g(m,s,i),g=(m,s,i)=>!(s=s.slice(1))||[~w,-1,1,-~w].some(o=>m[o+=i]==s[0]&&g(m.slice(0,i)+' '+m.slice(i+1),s,o)))

```

Takes the matrix as a newline-delimited string, the snake as a string and the width (as an integer). Loosely based on @JonathanFrech's answer.
> 6 votes

# Answer
# Mathematica, ~~180~~ ~~156~~ ~~141~~ ~~153~~ ~~138~~ ~~136~~ 104 bytes

```
MemberQ[#|Table[""<>Part[Join@@#,p],{x,1##4},{y,1##4},{p,FindPath[GridGraph@{##4},x,y,#3,All]}],#2,All]&

```

## Example input

```
[{{"1","1","1","1","1"},{"0","0","0","0","0"}},"10011001",8,5,2]

```

## Explanation

1. `GridGraph@{##4}` is a `Graph` object for a grid of vertices with adjacent vertices connected by edges, with dimensions `{##4}` \- that is, `{#4,#5}` or `{width,height}`.
2. We iterate over all starting vertices `x` (numbered `1` to `1##4 = width*height`), all ending vertices `y`, and all paths `p` of length at most `#3` from `x` to `y`.
3. For each such path, `""<>Part[Join@@#,p]` extracts the corresponding characters of the matrix and puts them into a string.
4. We also include the matrix itself, whose characters are all the strings of length 1 that can be found in it.
5. We see if one of these strings matches `s`, searching at all levels because this is a very multidimensional list we've built.

Note: Replacing `#3` by `{#3-1}` in `FindPath`, so that we only find paths of exactly the right length, is a huge improvement in terms of speed - but costs 4 more bytes.

---

*-24 bytes: taking dimensions of things as input*

*-15 bytes: using `StringPart` and `StringJoin` properly*

*+12 bytes: fixing the length-1 case*

*-15 bytes: ...*

*-2 bytes: taking size of the matrix as input as an array*

*-32 bytes: using `Table` to iterate over the path lets us avoid using `Function`, and using `MemberQ[...,s,All]` lets us just sort of stick the matrix onto the table when dealing with snakes of length 1.*
> 5 votes

# Answer
# C# (.NET Core), 346 341 336 302 297 bytes

```
(m,h,w,s,l)=>{for(int y=0;y<h;y++)for(int x=0;x<w;x++)if(N(x,y,l-1))return 0<1;return 1<0;bool N(int x,int y,int p){if(p<0)return 0<1;if(y<0|x<0|y==h|x==w||m[y,x]>1||s[p]!=m[y,x])return 1<0;int g=m[y,x];m[y,x]=2;if(N(x,y-1,--p)||N(x-1,y,p)||N(x,y+1,p)||N(x+1,y,p))return 0<1;m[y,x]=g;return 1<0;}}

```

Try it online!

5 bytes saved by golfing the `p` increment

5 bytes saved by taking in the snake length and starting at its tail, and removing an unnecessary space

34 bytes saved by reading the challenge properly and seeing I can take in the matrix's height and width

5 bytes saved, the single element test case failed, and the fix was beneficial

### Ungolfed

```
(m,h,w,s,l)=>{
    // Go through every potential starting point
    for(int y=0; y<h; y++)
        for(int x=0; x<w; x++)
            if(N(x,y,l-1)) // start the recursive steps
                return 0<1; // return true if N returns true, otherwise check the next element

    return 1<0; // return false as the snake doesn't fit into the matrix

    // C#7 local function in a Func
    bool N(int x, int y, int p)
    {
        // if there is no more snake to fit return true
        if(p<0)
            return 0<1;

        // if m element has part of the snake or
        // snake part doesn't match matrix element then return false
        if(y<0 | x<0 | y==h | x==w || m[y,x]>1 || s[p] != m[y,x])
            return 1<0;

        // hold the current matrix element
        int g=m[y,x];
        // set the current matrix element to 2 to indicate it has a part of the snake
        m[y,x]=2;

        // check each of the four neighbours and recurse down that neighbour
        // except if they are outside the matrix
        if(N(x,y-1,--p) ||
           N(x-1,y,p) ||
           N(x,y+1,p) ||
           N(x+1,y,p))
               return 0<1; // return true if remainder of the snake fits into the matrix

        // if snake doesn't fit then set the matrix element as not having part of the snake
        m[y,x]=g;
        // return false to indicate this neighbour direction doesn't fit the snake
        return 1<0;
    }
}

```
> 3 votes

# Answer
# Kotlin, 413 bytes

```
var x:(Array<Array<Char>>,String)->Boolean={b,s->fun f(s:String,x:Int,y:Int):Boolean{if(b[x][y]!=s[0])
return 0>1
if(s.length<2)
return 1>0
val v=b[x][y]
b[x][y]='Z'
try{return(-1..1).map{x+it}.flatMap{t->(-1..1).map{y+it}.map{t to it}}.filter{(X,Y)->(x-X)*(x-X)+(y-Y)*(y-Y)==1&&X in b.indices&&Y in b[0].indices&&f(s.substring(1),X,Y)}.any()}finally{b[x][y]=v}}
b.indices.any{x->(0..b[0].size-1).any{f(s,x,it)}}}

```

## Beautified

```
var x: (Array<Array<Char>>, String) -> Boolean = { b, s ->
    fun f(s: String, x: Int, y: Int): Boolean {
        if (b[x][y] != s[0])
            return 0 > 1
        if (s.length < 2)
            return 1 > 0
        val v = b[x][y]
        b[x][y] = 'Z'
        try {
            return (-1..1).map{ x + it }
                    .flatMap { t -> (-1..1).map{y+it}.map { t to it } }
                    .filter { (X, Y) ->
                        (x - X)*(x - X) + (y - Y)*(y - Y) == 1 &&
                                X in b.indices && Y in b[0].indices &&
                                f(s.substring(1), X, Y) }
                    .any()
        } finally {
            b[x][y] = v
        }
    }
    b.indices.any { x -> (0..b[0].size - 1).any { f(s, x, it) } }
}

```

## Test

```
var x:(Array<Array<Char>>,String)->Boolean={b,s->fun f(s:String,x:Int,y:Int):Boolean{if(b[x][y]!=s[0])
return 0>1
if(s.length<2)
return 1>0
val v=b[x][y]
b[x][y]='Z'
try{return(-1..1).map{x+it}.flatMap{t->(-1..1).map{y+it}.map{t to it}}.filter{(X,Y)->(x-X)*(x-X)+(y-Y)*(y-Y)==1&&X in b.indices&&Y in b[0].indices&&f(s.substring(1),X,Y)}.any()}finally{b[x][y]=v}}
b.indices.any{x->(0..b[0].size-1).any{f(s,x,it)}}}

data class Test(val board: String, val snake: String, val output: Boolean)

val tests = listOf(
        Test("""01010
            |10101
            |01010
            |10101
            |01010""", "0101010101010101010101010", true),
        Test("""01110
            |01100
            |10010
            |10110
            |01101""", "011111000110100", true),
        Test("""0""", "0", true),
        Test("""10
            |01""", "1010", true),
        Test("""100
            |010
            |001""", "100010001", true),
        Test("""00000
            |00000
            |00000
            |00000
            |00000""", "1", false),
        Test("""10101
            |01010
            |10101
            |01010
            |10101""", "11", false),
        Test("""100
            |010
            |001""", "111", false),
        Test("""10001
            |01010
            |00100
            |01010
            |10001""", "1000100010001000101010100", false)
)

fun main(args: Array<String>) {
    tests.filter {(board, snake, expected) ->
        val boardR = board.trimMargin().lines().map { it.toCharArray().toTypedArray() }.toTypedArray()
        val result = x(boardR, snake)
        result != expected
    }.forEach { throw AssertionError(it) }
    println("Test Passed")
}

```
> 1 votes

---
Tags: code-golf, decision-problem, restricted-time, binary-matrix
---


title: Polyglot the English Alphabet!

text:
# Question
Title: Polyglot the English Alphabet!
In this polyglot challenge, you will work together to figure out how to output all the 26 letters of the English alphabet!

**How does this work?**

For each answer, you must pick a new language (or a new major version of a language, for example, python 2 and python 3 are counted separately) that prints the next letter after the previous one.

**Example of an answer.**

Python 3 (Letter a):

```
print("a")

```

**Other rules.**

1. All letters are in lowercase.
2. Language must be Turing complete.
3. The same person cannot post twice in a row.
4. If an answer is found to be invalid it must be deleted.
5. Two users who post "at the same time" will have to let the earlier submission stand.
6. The same language must not be posted more than once.
7. Once we were done we keep going and start back at a.
8. It should print in all previous languages what it did in their original challenge

**More things:**

1. Set the sorting to oldest so this post works well.
2. Try not to make it impossible for the other person or else your post may be set as invalid.

# Answer
# Charcoal, 3 bytes

```
a⎚b

```

Try it online!

:P
> 3 votes

# Answer
# Mathematica, 1 byte ...............

```
a

```
> 2 votes

---
Tags: polyglot, alphabet, answer-chaining
---


# Question
Title: List prime-factorized natural numbers up to N in ascending order
For a given `n` list prime factorization of all natural numbers between `1` and `n` in ascending order. For example, for `n` = 10 the output would be:

```
1:
2: 2^1
3: 3^1
4: 2^2
5: 5^1
6: 2^1 3^1
7: 7^1
8: 2^3
9: 3^2
10: 2^1 5^1

```

**Requirements:**

* *You cannot just iterate over the numbers and factor each of them.* (Unless you know how to factor a number in logarithmic time, and then I doubt you'd be wasting your time solving puzzles.) This is too inefficient.
* The output should be as in the example above: On each line the number and the list of its prime factors.
* Consider that `n` can be *very* large, so it might be infeasible to generate all the factorizations into memory and then sort them at the end. (But if you have a clever solution that violates this, post it too.)

# Answer
Below is my attempt, in R5RS scheme (disclaimer: I'm not actually a Schemer (yet!), so pardon the (probably) terrible code).

```
(define count 10)

; `factors` is our vector of linked-lists of factors.  We're adding to these
; as we go on.
(define factors (make-vector count 'not-found))
(vector-set! factors 0 '())

; `primes-so-far` contains all the prime numbers we've discovered thus far.
; We use this list to speed up the dividing of numbers.
;   `primes-so-far-last` is a ref to the last entry in the `primes-so-far`
; list, for O(1) appending to the list.
(define primes-so-far '(dummy))
(define primes-so-far-last primes-so-far)

;; Helpers
(define (factor-ref n)
  (vector-ref factors (- n 1)))

(define (factor-cached? n)
  (not (eq? (vector-ref factors (- n 1)) 'not-found)))

(define (factor-put n factor)
  (let* ((rest        (/ n factor))
         (factor-cell (cons factor (factor-ref rest))))
    (vector-set! factors (- n 1) factor-cell)
    factor-cell))

(define (prime-append n)
  (let ((new-prime-cell (cons n '())))
    (set-cdr! primes-so-far-last new-prime-cell)
    (set!     primes-so-far-last new-prime-cell)
    new-prime-cell))

;; The factor procedure (assumes that `[1..n-1]` have already been factorized).
(define (factor n)
  (define (divides? m n)
    (= (modulo n m) 0))

  ; n       the number to factor.
  ; primes  the list of primes to try to divide with.
  (define (iter n primes)
    (cond ((factor-cached? n)
           (factor-ref n))

          ((null? primes)
           ; no primes left to divide with; n is prime.
           (prime-append n)
           (factor-put n n)) ; the only prime factor in a prime is itself

          ((divides? (car primes) n)
           (factor-put n (car primes))
           (factor-ref n))

          (else
           (iter n (cdr primes)))))

  (iter n (cdr primes-so-far)))

(define (print-loop i)
  (if (<= i count)
      (begin
        (display i)
        (display ": ")
        (display (factor i))
        (newline)
        (print-loop (+ i 1)))))

(print-loop 1)

```

Prints as:

```
1: ()
2: (2)
3: (3)
4: (2 2)
5: (5)
6: (2 3)
7: (7)
8: (2 2 2)
9: (3 3)
10: (2 5)

```

(Not exactly like in the task description, but all you'd have to do to get that output is to fold the list and merge repetitions of the same number, during the output part of the code. The internal representation/algorithm would still be the same.)

The idea is to cache the previously computed values, but make use of the fact that the factors of `n` is the first prime factor of `n` and the prime factors of (n / first-factor). But the latter is already known, so we just re-use the already existing list of factors for that smaller number. Thus, for each number in `[1..n]` which is not prime, a single cons cell is stored.

For each number, a single cons cell is created and stored. Thus, this approach should run with `O(n)` storage usage. I've no clue if it's possible to neatly express the time-complexity.
> 4 votes

# Answer
## C++

Implements a sieve using primes up to `sqrt(n)`. Maintains a list of linked lists to keep track of which primes divide which upcoming numbers. Each time a prime `p` is used, its `Factor` structure is moved `p` slots down the list.

Most of the time is spent in just `printf`ing the answer.

```
#include <stdio.h>
#include <stdlib.h>

// lists of Factors represent known prime factors of a number
struct Factor {
  Factor(int p) : prime(p), next(NULL) { }
  int prime;
  Factor *next;
};

int main(int argc, char *argv[]) {
  long long n = atoll(argv[1]);

  // figure out the maximum prime we need to sieve with
  int maxp = 1;
  while ((long long)maxp * maxp < n) maxp++;
  maxp--;

  // find next power of two up from that for our circular buffer size
  int size = 1;
  while (size < maxp) size *= 2;
  int mask = size - 1;

  // allocate circular buffer of lists of sieving prime factors for upcoming numbers
  Factor **factors = new Factor*[size]();

  printf("1:\n");

  for (long long x = 2; x < n; x++) {
    Factor *list = factors[x & mask];
    factors[x & mask] = NULL; // reset so it can hold the list for x + size

    if (!list && x <= maxp) { // x is a prime we need to sieve with - make new list with just itself
      list = new Factor(x);
    }

    // print factor list, push each Factor along to the next list.
    printf("%lld:", x);
    long long y = x;
    while (list) {
      Factor *f = list;
      list = f->next;
      int p = f->prime;

      // count how many factors of p are in x
      int k = 1;
      y /= p;
      while (y % p == 0) {
        k++;
        y /= p;
      }
      printf(" %d^%d", p, k);

      // splice f into the list for the next number it divides
      long long z = x + f->prime;
      f->next = factors[z & mask];
      factors[z & mask] = f;
    }
    // remaining part of x must be prime
    if (y != 1) printf(" %lld^1", y);
    printf("\n");
  }
}

```
> 4 votes

# Answer
# C (gcc)

```
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

int square(int a){
	return a * a;
}

void prime_factors(int n){
	// this is an array of n elements, which will contain all found primes.
	// curprime stores the index of the last found prime, which saves us searching for where to insert the next one and things.
	int* primes = calloc(sizeof(int), n);
	int curprime = 0;

	printf("1:\n"); // Micro optimization, and rids me of the messing around that is 1.
	for(int i=2; i<=n; i++){
		// Print the current i.
		printf("%i: ",i);

		// Define val, which we'll slowly make smaller and smaller. Mwahaha.
		int val = i;
		int isprime = true;	// This will be set to false if it's divisible by any primes, which of course, means it's also not a prime.

		// Loop through primes, this loop stops if we've reached either more than sqrt(count) primes, or val is equal to zero (as such, it's fully prime factorized).
		for(int*prime_pointer = primes; val && square((int)(prime_pointer-primes)) < curprime; prime_pointer++){
			int prime = *prime_pointer;
			// if the current val is divisible by the current prime.
			while(val%prime == 0){
				isprime = false; 	// We know that this number isn't prime.
				val = val / prime;	// Divide val by it.
				printf("%i ",prime);// And write this prime.
			}
		}
		if(isprime){	// If this number is a prime.
			printf("%i ",i);	// Append it to its own list.
			primes[curprime++] = i;	// And append this new prime to our list of primes.
		}
		printf("\n");	// Terminate the line with a newline. Duh...
	}
}

int main(int argc, char** argv){
	prime_factors(1000);
}

```

Defines the function `prime_factors` which takes an integer `n` and outputs via printf in the following format:

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

```

This uses O(n) extra memory, and I'm not sure the time complexity.

Try it online!
> 0 votes

---
Tags: number-theory, primes, fastest-code, factoring
---


title: It's a find-a-movie challenge

text:
# Question
Title: It's a find-a-movie challenge
This is a simple(ish) web scraping challenge.

**Input**

Your code should take an MPAA film rating and a number from 0 to 100 as input. It can do this in any way you find convenient.

**Output**

Your code should return the name of any movie which has a) that film rating and b) the numerical score on the Tomatometer from rottentomatoes.

If there is no such movie it can output anything you like.

The possible MPAA film ratings are `G, PG, PG-13, R, NC-17, NR`.

Your code may report one or more movies, that is up to you.

To clarify, your code is meant to access the web to get the answers to queries.

**Example**

Say the input is "PG, 98" then your code could output "Zootropolis".

Please show an example of your code working with the film rating `PG` and score `98` along with your answer.

# Answer
# Stratos, 133 bytes

```
{
f"www.rottentomatoes.com/api/private/v2.0/browse?minTomato=%&maxTomato=%&type=dvd-streaming-all"r"results")s"mpaaRating"=⁰
s"title"

```

Try it!
> 2 votes

# Answer
# Bash, 182 bytes

```
curl "https://www.rottentomatoes.com/api/private/v2.0/browse?minTomato=$2&maxTomato=$2&type=dvd-streaming-all" 2>/dev/null|grep -o "{[^}]*aRating\":\"$1\""|grep -Po 'title":"\K[^"]*'

```

Usage:

```
$ bash script PG 98
The Island President
Inside Out
Zootopia
Paddington
Love & Friendship
Long Way North (Tout en haut du monde)

```
> 12 votes

# Answer
# JavaScript (ES6), ~~167~~ ~~162~~ 159 bytes

Needs to be run from the root of rottentomatoes.com. Returns a `Promise` object containing the title.

```
s=>n=>fetch(`api/private/v2.0/browse?minTomato=${n}&maxTomato=${n}&type=dvd-streaming-all`).then(r=>r.json()).then(j=>j.results.find(x=>x.mpaaRating==s).title)

```

If we can require that it be run in a specific directory then it becomes 139 bytes:

```
s=>n=>fetch(`browse?minTomato=${n}&maxTomato=${n}&type=dvd-streaming-all`).then(r=>r.json()).then(j=>j.results.find(x=>x.mpaaRating==s).title)

```
> 6 votes

# Answer
# Python 2 \+ requests, ~~209~~ 204 bytes

*-5 bytes thanks to Ian Gödel.*

```
lambda r,t:[i['title']for i in get('http://rottentomatoes.com/api/private/v2.0/browse?minTomato=%d&maxTomato=%d&type=dvd-streaming-all'%(t,t)).json()['results']if i['mpaaRating']==r]
from requests import*

```
> 3 votes

# Answer
# q/kdb+, 168 bytes

**Solution:**

```
{(r(&)(r:.j.k[.Q.hg`$"https://www.rottentomatoes.com/api/private/v2.0/browse?type=dvd-streaming-all&min",t,"&max",t:"Tomato=",y]`results)[;`mpaaRating]like x)[;`title]}

```

**Example:**

```
q){(r(&)(r:.j.k[.Q.hg`$"https://www.rottentomatoes.com/api/private/v2.0/browse?type=dvd-streaming-all&min",t,"&max",t:"Tomato=",y]`results)[;`mpaaRating]like x)[;`title]}["PG";"98"]
"The Island President"
"Inside Out"
"Zootopia"
"Paddington"
"Love & Friendship"
"Long Way North (Tout en haut du monde)"

```

**Explanation:**

```
.Q.hg           / fetch a URL
.j.k            / parse json string into Q dictionaries
`results        / index into dictionary with key `results
[;`mpaaRating]  / index into these sub dictionaries extracting mpaaRating
like x          / binary list where they match, e.g. "PG"
(&)             / where, list indices where true
[;`title]       / index into dictionary with key `title

```

**Notes:**

* If you want to try this out yourself, take a read through the Cookbook/SSL page to ensure your environment is setup correctly.
* Fails if we remove the `s` of `https`, or the `www.`, gives `301 Permanently Moved` response.
> 2 votes

# Answer
# JavaScript (ES2017), 158 bytes

```
async(r,n)=>(await(await fetch(`api/private/v2.0/browse?minTomato=${n}&maxTomato=${n}&type=dvd-streaming-all`)).json()).results.find(m=>m.mpaaRating==r).title

```

Run from the Rotten Tomatoes home page:

```
f=async(r,n)=>(await fetch(`api/private/v2.0/browse?minTomato=${n}&maxTomato=${n}&type=dvd-streaming-all`).then(x=>x.json())).results.find(m=>m.mpaaRating==r).title
f('PG',98).then(console.log)

```
> 2 votes

---
Tags: code-golf, internet
---


title: Check if there is an isomorph substring

text:
# Question
Title: Check if there is an isomorph substring
This question is an extension of Check if words are isomorphs and copies the first part of it to give the definition of an isomorph.

Two words are *isomorphs* if they have the same pattern of letter repetitions. For example, both `ESTATE` and `DUELED` have pattern `abcdca`

```
ESTATE
DUELED

abcdca

```

because letters 1 and 6 are the same, letters 3 and 5 are the same, and nothing further. This also means the words are related by a substitution cipher, here with the matching `E <-> D, S <-> U, T <-> E, A <-> L`.

Given two strings X and Y, with X no longer than Y, the task is to determine if there is a substring of Y which is an isomorph with X.

**Input:** Two non-empty strings of letters from a..zA..Z which one string per line. This will come from standard input.

**Output** A substring of the second string which is an isomorph with the first string, if such a thing exists. Otherwise output "No!".

**Rules** Your code must run in linear time in the total length of the input.

**Score** Your score is the number of bytes in your code. Fewest bytes wins.

---

**Example input and output**

```
adca
ddaddabdaabbcc

dabd

```

**Tip**

There is at least one not *that* complicated, practically fast and linear time solution to this problem.

# Answer
> 8 votes
# Python 2, ~~338~~ ~~326~~ ~~323~~ ~~321~~ ~~310~~ ~~306~~ ~~297~~ ~~293~~ ~~290~~ ~~289~~ ~~280~~ ~~279~~ ~~266~~ ~~264~~ ~~259~~ ~~237~~ ~~230~~ ~~229~~ ~~226~~ ~~223~~ ~~222~~ ~~220~~ ~~219~~ 217 (~~260~~ ~~238~~ ~~231~~ ~~228~~ ~~225~~ ~~223~~ ~~221~~ ~~220~~ 218 with 0 exit status)

```
exec'''s=raw_input()
S=[M-s.rfind(c,0,M)for M,c in enumerate(s)]
k=0
j=x=%s
while k<=M+x:
 if S[k]>j<W[j]or S[k]==W[j]:
    k+=1;j+=1;T+=[j]
    if j-L>x:print s[k-j:k];z
 else:j=T[j]
'''*2%('-1;T=[0];W=S;L=M',0)
print'No!'

```

The algorithm is a variation of KMP, using an index-based test for character matching. The basic idea is that if we get a mismatch at position `X[i]` then we can fall back to the next possible place for a match according to the longest suffix of `X[:i]` that is isomorphic to a prefix of `X`.

Working from left to right, we assign each character an index equal to the distance to the most recent previous occurrence of that character, or if there is no previous occurrence then we take the length of the current string prefix. For example:

```
MISSISSIPPI
12313213913

```

To test whether two characters match, we compare indices, adjusting appropriately for indices that are greater than the length of the current (sub)string.

The KMP algorithm becomes a little simplified since we cannot get a mismatch on the first character.

This program outputs the first match if one exists. I use a runtime error to exit in the event of a match, but the code can be easily modified to exit cleanly at the cost of some bytes.

**Note:** For computing indices, we can use `str.rfind` (as opposed to my earlier approach using a dictionary) and still have linear complexity, assuming that `str.rfind` starts searching from the end (which seems the only sane implementation choice) -- for each character in the alphabet, we never have to traverse the same part of the string twice, so there is an upper bound of (size of alphabet) * (size of string) comparisons.

Since the code got fairly obfuscated in the course of golfing, here is an earlier (293 byte) solution that's a bit easier to read:

```
e=lambda a:a>i<W[i]or a==W[i]
exec('s=raw_input();S=[];p={};M=i=0\nfor c in s:S+=[M-p.get(c,-1)];p[c]=M;M+=1\nW=S;L=M;'*2)[:-9]
T=[0]*L
k=1
while~k+L:
 if e(W[k]):i+=1;k+=1;T[k]=i
 else:i=T[i]
m=i=0
while m+i<M:
 if e(S[m+i]):
    if~-L==i:print s[m:m+L];z
    i+=1
 else:m+=i-T[i];i=T[i]
print'No!'

```

The `e` function tests equivalence of characters. The `exec` statement assigns indices and does some variable initialisations. The first loop processes `X` for fall back values, and the second loop does the string search.

**Update:** Here is a version that exits cleanly, at the cost of one byte:

```
r='No!'
exec'''s=raw_input()
S=[M-s.rfind(c,0,M)for M,c in enumerate(s)]
k=0
j=x=%s
while k<=M+x:
 if S[k]>j<W[j]or S[k]==W[j]:
    k+=1;j+=1;T+=[j]
    if j-L>x:r=k=s[k-j:k]
 else:j=T[j]
'''*2%('-1;T=[0];W=S;L=M',0)
print r

```

# Answer
> 6 votes
# Python 3, 401 bytes

```
import string,itertools
X=input()
Y=input()
x=len(X)
t=[-1]+[0]*~-x
j=2
c=0
while j<x:
 if X[j-1]==X[c]:c+=1;t[j]=c;j+=1
 elif c>0:c=t[c]
 else:t[j]=0;j+=1
s=string.ascii_letters
*b,=map(s.find,X)
for p in itertools.permutations(s):
 m=i=0
 while m+i<len(Y):
  if p[b[i]]==Y[m+i]:
   if~-x==i:print(Y[m:m+x]);exit()
   else:i+=1
  else:
   if-1<t[i]:m+=i-t[i];i=t[i]
   else:i=0;m+=1
else:print("No!")

```

This is still mostly ungolfed, but I think it should work. The core algorithm is KMP, plus an additional factor which is factorial in the size of the alphabet (which is fine, since the alphabet is constant). In other words, this is/should be one completely impractical linear algorithm.

Here's a few annotations to help with the analysis:

```
# KMP failure table for the substring, O(n)
t=[-1]+[0]*~-x
j=2
c=0
while j<x:
 if X[j-1]==X[c]:c+=1;t[j]=c;j+=1
 elif c>0:c=t[c]
 else:t[j]=0;j+=1

# Convert each char to its index in a-zA-Z, O(alphabet * n)
s=string.ascii_letters
*b,=map(s.find,X)

# For every permutation of letters..., O(alphabet!)
for p in itertools.permutations(s):
 # Run KMP, O(n)
 m=i=0
 while m+i<len(Y):
  if p[b[i]]==Y[m+i]:
   if~-x==i:print(Y[m:m+x]);exit()
   else:i+=1
  else:
   if-1<t[i]:m+=i-t[i];i=t[i]
   else:i=0;m+=1
else:print("No!")

```

For testing, you can replace `s` with a smaller alphabet than `string.ascii_letters`.

# Answer
> 2 votes
# APL (Dyalog), 32 bytes

This is an infix function, taking X as left argument and Y as right argument.

```
{(s,⊂'No!')⊃⍨(⍳⍨¨s←⍵,/⍨≢⍺)⍳⊂⍳⍨⍺}

```

Try it online!

`{``}` anonymous lambda where  and  represent the arguments (X and Y)

`⍳⍨⍺`**ɩ**ndex selfie of X (**ɩ**ndices of the first occurrence of elements of X in X)

enclose so we can look for that entire pattern

`(``)⍳`**ɩ**ndex of first occurrence of that in…

`≢⍺` tally (length) of X

`⍵,/⍨` all substrings of that size of Y (lit. concatenation reduction of those, but that is a no-op)

`s←` store in `s` (for **s**ubstrings)

`⍳⍨¨`**ɩ**ndex selfie of each of those

now we have the index of the first pattern, or 1 + the number of patterns if no match was found

`(``)⊃⍨` use that index to pick from…

`⊂'No!'` the enclosed string (so that it functions as a single element)

`s,` prepended with `s`

---
Tags: code-golf
---


title: I'm symmetric, not palindromic!

text:
# Question
Title: I'm symmetric, not palindromic!
## Background

Inspired by I'm a palindrome. Are you?, where it is presented the shocking fact that “`()()` is not a palindrome, but `())(`”, I asked myself what instead is `()()` and the answer is simply: it is a string with a vertical symmetry axis!

### The task

Write a program or function that takes a string S (or the appropriate equivalent in your language) as input, checks for symmetry along the vertical axis, and returns a truthy or falsy value accordingly. You can use any reasonable means to take the input and provide the output.

### Reflectional symmetry

Reflectional symmetry around a vertical axis (or left-right symmetry) means that if you put a mirror vertically at the exact center of the string, the reflected image of the first half of the string is identical to the second half of the string.

For example, the following strings are reflectional symmetric around a vertical axis:

```
()()
()()()
[A + A]
WOW ! WOW
OH-AH_wx'xw_HA-HO
(<<[[[T*T]]]>>)
(:)
)-(
())(()
qpqp

```

while the following are not:

```
())(
((B))
11
+-*+-
WOW ! wow
(;)
qppq

```

### Rules of the contest

• Your program or function will receive only printable ASCII characters. You can include or not the empty string, (which is symmetric, of course!) as legal input, which is better for you.

• The ASCII characters that can be considered symmetric with respect to the vertical axes are the following (note the initial space, and the difference between uppercase and lowercase letters):

```
 !"'+*-.:=AHIMOTUVWXY^_ovwx|

```

The ASCII characters that can be considered “mirrored” and their corresponding characters are:

```
()<>[]{}qpbd/\

```

Note that, since they are mirrored, you can have both `()` as well as `)(`, `/\` and `\/`, etc.

All the other ASCII printable characters must be considered asymmetric and without a mirrored corresponding character.

• This is a challenge: the shorter your program is, measured in bytes, the better, in any programming language.

• Kudos to people that will produce a symmetric program!

**Note**: this question is not a duplicate of "Convenient Palindrome”, that requires to check for palindromic strings in which parentheses are flipped. This question is different for two reasons:

1) it is a restriction of the other question for what concerns non-parentheses characters, since only symmetric characters can appear in reverse order.

2) Since it is based on the concept of symmetry, and not on a concept of “convenient palindrome”, mirrored characters can appear in both order, i.e. `[]` and `][`, and this makes the program to solve it different from programs that solve the other problem.

# Answer
> 7 votes
## JavaScript (ES6), ~~130~~ ~~125~~ 113 bytes

```
f=
s=>s==[...s].reverse(s=`()<>[]{}qpbd/\\`).map(c=>s[s.indexOf(c)^1]||/[- !"'+*.:=AHIMOT-Y^_ovwx|]/.exec(c)).join``
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```

Edit: Saved 5 bytes thanks to @Arnauld. Saved a further 11 bytes thanks to @YairRand.

# Answer
> 5 votes
# Jelly,  ~~69~~  62 bytes

```
“(<[{qb/“ !"'+*-.:=AHIMOTUVWXY^_ovwx|“)>]}pd\”,Ṛ$F©f@ð®œs2¤yU⁼

```

Try it online!

All test cases

*-7 bytes thanks to @JonathanAllan*

**How it Works**

```
“(<[{qb/“ !"'+*-.:=AHIMOTUVWXY^_ovwx|“)>]}pd\”,Ṛ$F©f@ð®œs2¤yU⁼  main link

“(<[{qb/“ !"'+*-.:=AHIMOTUVWXY^_ovwx|“)>]}pd\”  The literal list of strings  ['(<[{qb/', ' !"\'+*-.:=AHIMOTUVWXY^_ovwx|', ')>]}pd\\']
               $                 Last two links (if not part of an LCC) as a monad
            Ṛ                    Reverse array Does not vectorize.
           ,                     Pair; return [x, y].
                 ©               Copy link result to register (® atom to retrieve).
              F                  Flatten list.
                  f              Filter; remove the elements from x that are not in y.
                   @             Swaps operands.

                    ð            Start a new dyadic chain
                         ¤       Nilad followed by links as a nilad.
                      2          The literal integer 2
                   ®             Restore; retrieve the value of the register. Initially 0.
                    œs           Split x into y chunks of similar lengths.
                          y      Translate the elements of y according to the mapping in x.
                           U     Upend; reverse an array.
                            ⁼    Equals. Does not vectorize.

```

# Answer
> 4 votes
# Python 3, ~~211~~ ~~208~~ 195 bytes

```
lambda S,p="()<>[]{}qpbd\/",s=" !\"'+*-.:=AHIMOTUVWXY^_ovwx|":(S==S.translate({ord(s[2*x]):s[2*x+1]for s in(p,p[::-1])for x in range(7)})[::-1])*(~len(S)%2*s[len(S)//2]in s)*(not set(S)-set(p+s))

```

Saved 13 bytes thanks to Jonathan Allan.

# Answer
> 2 votes
# SOGL V0.12, 88 bytes

```
"el²┘N!←8mYdDm⁵╔C⅛┌6▼ģη⁷fņ‘;W‽0←}C
l»{Kα}lalh=‽;KCø;{:↔³↔=?"qpbd”⁴²+:GW:2%«H+W}:h=?:CΚ}=

```

Try it Here!

~24 bytes to add `qpbd` mirroring and 6 bytes for `(x-1 XOR 1) + 1` :/

# Answer
> 2 votes
# Kotlin 1.1, ~~201~~ 199 bytes

```
{var R="(<[{qb/\\dp}]>)"
var m=HashMap<Any,Any>()
"\"!'+*-.:=AHIMOTUVWXY^_ovwx| ".map{m[it]=it}
R.indices.map{m[R[it]]=R[R.length-(it+1)]}
it.zip(it.reversed()).filter{m[it.first]!=it.second}.none()}

```

## Beautified

```
{
    var R = "(<[{qb/\\dp}]>)"
    var m = HashMap<Any, Any>()
    "\"!'+*-.:=AHIMOTUVWXY^_ovwx| ".map { m[it] = it }
    R.indices.map { m[R[it]] = R[R.length - (it + 1)] }
    it.zip(it.reversed()).filter { m[it.first] != it.second }.none()
}

```

## Test

```
var i:(String)->Boolean =
{var R="(<[{qb/\\dp}]>)"
var m=HashMap<Any,Any>()
"\"!'+*-.:=AHIMOTUVWXY^_ovwx| ".map{m[it]=it}
R.indices.map{m[R[it]]=R[R.length-(it+1)]}
it.zip(it.reversed()).filter{m[it.first]!=it.second}.none()}
fun main(args: Array<String>) {
    var GOOD = listOf("()()",
            "()()()",
            "[A + A]",
            "WOW ! WOW",
            "OH-AH_wx'xw_HA-HO",
            "(<<[[[T*T]]]>>)",
            "(:)",
            ")-(",
            "())(()",
            "qpqp")

    var BAD = listOf("())(",
            "((B))",
            "11",
            "+-*+-",
            "WOW ! wow",
            "(;)",
            "qppq")

    GOOD.filterNot { i(it) }.forEach { throw AssertionError(it) }
    BAD.filter { i(it) }.forEach { throw AssertionError(it) }
    println("Test Passed")
}

```

**Can't run on TIO because 1.1 is not supported**

# Answer
> 2 votes
# Python 2, ~~182~~ ~~167~~ ~~163~~ ~~162~~ ~~160~~ 158 bytes

```
lambda s:s[::-1]==s.translate(m(t+w,w+t),m("","").translate(None," !\"'+*-.:=AHIMOTUVWXY^_ovwx|"+t+w))
from string import*
m=maketrans
t=")>[{/qd"
w="(<]}\pb"

```

Try it online!

*Saved 2 bytes thanks to Jonathan Allan*

**Explanation** First, we need to build the list of all chars that don't have a symmetric (the char itself : `A`, ... or another char `(` for `)`, ...):

* `m("","")` returns a string with all the available chars.
* `m("","").translate(None," \t!\"'+*-.:=AHIMOTUVWXY^_ovwx|"+t+w))` removes from all the available chars the chars that have a symmetric.

Then, we map every char to its symmetric char and remove the chars that don't have a symmetric with `s.translate(m(t+w,w+t),<chars that don't have a symmetric>)`

If the result equals to the reversed string, we have a symmetric string.

# Answer
> 1 votes
# Perl 5, 102 + 1 (-p) = 103 bytes

```
$_=!/[^ !"'+*.:=AHIMOT-Y^_ovwx|()<>[\]{}qpbd\/\\-]/&&$_ eq reverse y|()<>[]{}qpbd/\\|)(><][}{pqdb\\/|r

```

Try it online!

# Answer
> 1 votes
# Scala, 140 bytes

```
s.zip(s.reverse).forall(c=>(" !\"'+*-.:=AHIMOTUVWXY^_ovwx|".flatMap(x=>x+""+x)+"()<>[]{}qpbd/\\\\/dbpq}{][><)(").indexOf(c._1+""+c._2)%2==0)

```

Try it online!

---
Tags: code-golf, string
---