title: Co-primality and the number pi

text:
# Question
Title: Co-primality and the number pi
# Introduction

Number theory is full of wonders, in the form of unexpected connections. Here's one of them.

Two integers are co-prime if they have no factors in common other than 1. Given a number \\$N\\$, consider all integers from 1 to \\$N\\$. Draw two such integers *at random* (all integers have the same probability of being selected at each draw; draws are independent and with replacement). Let \\$p\\$ denote the probability that the two selected integers are co-prime. Then \\$p\\$ tends to \\${6} / {\pi^2} \approx 0.6079...\\$ as \\$N\\$ tends to infinity.

# The challenge

The purpose of this challenge is to compute \\$p\\$ as a function of \\$N\\$.

As an example, consider \\$N = 4\\$. There are 16 possible pairs obtained from the integers 1,2,3,4. 11 of those pairs are co-prime, namely \\$(1,1)\\$, \\$(1,2)\\$, \\$(1,3)\\$, \\$(1,4)\\$, \\$(2,1)\\$, \\$(3,1)\\$, \\$(4,1)\\$, \\$(2,3)\\$, \\$(3,2)\\$, \\$(3,4)\\$, \\$(4,3)\\$. Thus \\$p = {11} / {16} = 0.6875\\$ for \\$N = 4\\$.

The *exact* value of \\$p\\$ needs to be computed with at least \\$4\\$ decimals. This implies that the computation has to be deterministic (as opposed to Monte Carlo). But it need not be a direct enumeration of all pairs as above; any method can be used.

Function arguments or stdin/stdout may be used. If displaying the output, trailing zeros may be omitted. So for example \\$0.6300\\$ can be displayed as `0.63`. It should be displayed as a decimal number, not as a fraction (displaying the string `63/100` is not allowed).

Winning criterion is fewest bytes. There are no restrictions on the use of built-in functions.

# Test cases

Input / output (only four decimals are mandatory, as indicated above):

```
1    / 1.000000000000000
2    / 0.750000000000000
4    / 0.687500000000000
10   / 0.630000000000000
100  / 0.608700000000000
1000 / 0.608383000000000

```

# Answer
# Jelly, ~~12~~ 8 bytes

```
RÆṪSḤ’÷²

```

Try it online!

The following binary code works with this version of the Jelly interpreter.

```
0000000: 52 91 b0 53 aa b7 9a 8a  R..S....

```

### Idea

Clearly, the number of pairs **(j, k)** such that **j ≤ k** and **j** and **k** are co-prime equals the number of pairs **(k, j)** that satisfy the same conditions. Also, if **j = k**, **j = 1 = k**.

Thus, to count the number of co-prime pairs with coordinates between **1** and **n**, it suffices to calculate the amount **m** of pairs **(j, k)** such that **j ≤ k**, then compute **2m - 1**.

Finally, since Euler's totient function **φ(k)** yields the number integers between between **1** and **k** that are co-prime to **k**, we can calculate **m** as **φ(1) + … + φ(n)**.

### Code

```
RÆṪSḤ’÷²    Input: n

R           Yield [1, ..., n].
 ÆṪ         Apply Euler's totient function to each k in [1, ..., n].
   S        Compute the sum of all results.
    Ḥ       Multiply the result by 2.
     ’      Subtract 1.
      ÷²    Divide the result by n².

```
> 17 votes

# Answer
# Mathematica ~~43~~ 42 bytes

I found Lattice points visible from the origin, from which the picture below is taken, to be helpful in reframing the problem through the following questions regarding a given square region of the unit lattice:

* What fraction of the unit-lattice points have co-prime coordinates?
* What fraction of unit-lattice points can be seen from the origin?

---

```
N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&

```

---

**Examples**

Trailing zeros are omitted.

```
N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&/@Range@10

```

> {1., 0.75, 0.777778, 0.6875, 0.76, 0.638889, 0.714286, 0.671875, 0.679012, 0.63}

---

**Timing**

The timing, in seconds, precedes the answer.

```
N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&[1000]// AbsoluteTiming

```

> {0.605571, 0.608383}
> 17 votes

# Answer
# Pyth - ~~13~~ 11 bytes

```
.OqR1iM^SQ2

```

Test Suite.
> 7 votes

# Answer
## Mathematica, ~~42~~ 32 bytes

```
Count[GCD~Array~{#,#},1,2]/#^2.&

```

Anonymous function, uses simple brute force. The last case runs in about .37 seconds on my machine. Explanation:

```
                               &   A function taking N and returning
Count[               , , ]           the number of
                      1               ones
                                     in the
                        2             second
                                     level of
         ~Array~                      a matrix of
      GCD                              the greatest common denominators of
                {#,#}                 all 2-tuples in [1..N]
                          /         divided by
                           #          N
                            ^2.      squared.

```
> 6 votes

# Answer
# Dyalog APL, 15 bytes

```
(+/÷⍴)∘∊1=⍳∘.∨⍳

```

Pretty straightforward. It's a monadic function train. Iota is the numbers from 1 to input, so we take the outer product by gcd, then count the proportion of ones.
> 4 votes

# Answer
# Octave, ~~49~~ 47 bytes

Just calculating the `gcd` of all pairs and counting.

```
@(n)mean(mean(gcd(c=kron(ones(n,1),1:n),c')<2))

```

> The kronecker product is awesome.
> 3 votes

# Answer
## Sage, 55 bytes

```
lambda a:n((sum(map(euler_phi,range(1,a+1)))*2-1)/a**2)

```

Thanks to Sage computing everything symbolically, machine epsilon and floating-point issues don't crop up. The tradeoff is, in order to follow the output format rule, an additional call to `n()` (the decimal approximation function) is needed.

Try it online
> 3 votes

# Answer
# 05AB1E, 8 bytes

```
LÕO·<sn/

```

Try it online!

Explanation:

```
L         Push inclusive range of (implicit) input (4 -> [1, 2, 3, 4])
 Õ        Perform Euler's Totient on each element ([1, 2, 3, 4] -> [1, 1, 2, 2])
  O       Sum list elements ([1, 1, 2, 2] -> 6)
   ·<     Double result and subtract 1 (2*6 - 1 = 11)
     sn   Square input (4 -> 16)
       /  Divide sum by input squared (11 / 16 = 0.6875)
          (Implicit output)

```

It might be golf-able, I just copied Dennis' Jelly method, and I haven't really bothered trying to make it any smaller.
> 3 votes

# Answer
# MATL, ~~20~~ 17 bytes

This uses current version (5.0.0) of the language.

Approach based on @flawr's answer.

```
i:tg!X*t!Zd1=Y)Ym

```

*Edit (April 28, 2015)*: Try it online! After this answer was posted, function `Y)` was renamed to `X:`; the link includes that change.

### Example

```
>> matl i:tg!X*t!Zd1=Y)Ym
> 100
0.6087

```

### Explanation

```
i:         % vector 1, 2, ... up to input number
tg!        % copy, convert into ones, transpose
X*         % Kronecker product. Produces a matrix
t!         % copy, transpose
Zd         % gcd of all pairs
1=         % is it equal to 1?
Y)         % linearize into column array
Ym         % compute mean

```

---

Old answer: **20 bytes**

```
Oi:t"t@Zd1=sb+w]n2^/

```

**Explanation**

```
O             % produce literal 0. Initiallizes count of co-prime pairs.
i             % input number, say N
:             % create vector 1, 2, ... N
t             % duplicate of vector
"             % for loop
    t         % duplicate of vector
    @         % loop variable: each element from vector
    Zd        % gcd of vector and loop variable. Produces a vector
    1=s       % number of "1" in result. Each "1" indicates co-primality
    b+w       % accumulate into count of co-prime pairs
]             % end
n2^/          % divide by N^2

```
> 2 votes

# Answer
# JavaScript (ES6), 88 bytes

```
n=>eval(`p=0;for(i=n;i;i--)for(j=n;j;j--,p+=a)for(a=1,k=j;k>1;k--)a=i%k||j%k?a:0;p/n/n`)

```

## Explanation

```
n=>
  eval(`                     // use eval to enable for loop without {} or return
    p=0;                     // p = number of pairs
    for(i=n;i;i--)           // i = 1 to n
      for(j=n;j;j--,p+=a)    // j = i to n, a will equal 1 if i and j are coprime, else 0
        for(a=1,k=j;k>1;k--) // for each number from 0 to j
          a=i%k||j%k?a:0;    // if i%k and j%k are both 0, this pair is not coprime
    p/n/n                    // return result (equivalent to p/(n*n))
  `)

```

## Test

Takes a while for large (`>100`) values of `n`.

```
var solution = n=>eval(`p=0;for(i=n;i;i--)for(j=n;j;j--,p+=a)for(a=1,k=j;k>1;k--)a=i%k||j%k?a:0;p/n/n`)
```

```
N = <input type="text" id="input" value="100" />
<button onclick="result.textContent=solution(+input.value)">Go</button>
<pre id="result"></pre>
```
> 2 votes

# Answer
## Seriously, 15 bytes

```
,;ª)u1x`▒`MΣτD/

```

Hex Dump:

```
2c3ba62975317860b1604de4e7442f

```

Try It Online

I'm not going to bother explaining it since it literally uses exactly the same algorithm as Dennis's Jelly solution (although I derived it independently).
> 2 votes

# Answer
## Mathematica, 35 bytes

Implements @Dennis's algorithm.

```
(2`4Plus@@EulerPhi@Range[#]-1)/#^2&

```

Compute the sum of the totient (Euler's phi function) over the range from 1 to the input value. Multiply by floating point two (with four digits of precision) and subtract one. (More precision can be retained by using instead "`2`" and "`1`4`".) This is the total number of coprime pairs, so divide by the square of the input to get the desired fraction. Because the two is an approximate number, so is the result.

Testing (with timing data in the left column since at least one of us thinks that's interesting), with the function assigned to `f` so that the test line is more easily read.:

```
f=(2`4Plus@@EulerPhi@Range[#]-1)/#^2&
RepeatedTiming[f[#]] & /@ {1, 2, 4, 10, 100, 1000}
(* {{5.71*10^-6, 1.000},
    {5.98*10^-6, 0.750},
    {0.000010  , 0.6875},
    {0.0000235 , 0.6300},
    {0.00028   , 0.6087},
    {0.0033    , 0.6084} }  *)

```

Edit: Showing extent of the range of inputs (swapping the precision to the one instead of the two because otherwise the results get rather monotonous) and challenging others to do the same...

```
f = (2 Plus @@ EulerPhi@Range[#] - 1`4)/#^2 &
{#}~Join~RepeatedTiming[f[#]] & /@ {1, 2, 4, 10, 100, 1000, 10^4, 10^5, 10^6, 10^7}
(*  Results are {input, wall time, output}
    {{       1,  5.3*10^-6, 1.000},
     {       2,  6.0*10^-6, 0.7500},
     {       4,  0.0000102, 0.68750},
     {      10,  0.000023 , 0.63000},
     {     100,  0.00028  , 0.6087000},
     {    1000,  0.0035   , 0.608383000},
     {   10000,  0.040    , 0.60794971000},
     {  100000,  0.438    , 0.6079301507000},
     { 1000000,  4.811    , 0.607927104783000},
     {10000000, 64.0      , 0.60792712854483000}}  *)

```

`RepeatedTiming[]` performs the calculation multiple times and takes an average of the times, attempting to ignore cold caches and other effects causing timing outliers. The asymptotic limit is

```
N[6/Pi^2,30]
(*  0.607927101854026628663276779258  *)

```

so for arguments \>10^4, we can just return "0.6079" and meet the specified precision and accuracy requirements.
> 2 votes

# Answer
# Samau, 12 bytes

**Disclaimer: Not competing because I updated the language after the question was posted.**

```
▌;\φΣ2*($2^/

```

Hex dump (Samau uses CP737 encoding):

```
dd 3b 5c ad 91 32 2a 28 24 32 5e 2f

```

Using the same algorithm as Dennis's answer in Jelly.
> 2 votes

# Answer
# J, ~~19~~ 17 bytes

```
*:%~1-~5+/@p:|@i:

```

Usage:

```
   (*:%~1-~5+/@p:|@i:) 4
0.6875

```

Explanation:

```
*:%~1-~5+/@p:|@i:
               i: [-n..n]
             |@   absolute value of each element ([n..1,0,1,..n])
       5+/@p:     sum of the totient function for each element
    1-~           decreased by one, giving the number of co-prime pairs
*:%~              divided by N^2

```

Dennis' solution gives a nice explanation how can we use the totient function.

Try it online here.
> 2 votes

# Answer
# Julia, 95 bytes

```
n->(c=combinations([1:n;1:n],2);((L=length)(collect(filter(x->gcd(x...)<2,c)))÷2+1)/L(∪(c)))

```

Just the straightforward approach for now; I'll look into shorter/more elegant solutions soon. This is an anonymous function that accepts an integer and returns a float. To call it, assign it to a variable.

Ungolfed:

```
function f(n::Integer)
    # Get all pairs of the integers from 1 to n
    c = combinations([1:n; 1:n], 2)

    # Get the coprime pairs
    p = filter(x -> gcd(x...) == 1, c)

    # Compute the probability
    return (length(collect(p)) ÷ 2 + 1) / length(unique(c))
end

```
> 2 votes

# Answer
# PARI/GP, 25 bytes

Making the function anonymous would save a byte, but then I'd have to use `self` making it more expensive overall.

```
f(n)=n^2-sum(j=2,n,f(n\j))

```
> 2 votes

# Answer
# Python2/Pypy, 178 bytes

The `x` file:

```
N={1:set([1])}
n=0
c=1.0
e=input()
while n<e:
 n+=1
 for d in N[n]:
  m=n+d
  try:N[m].add(d)
  except:N[m]=set([d,m])
 for m in range(1,n):
  if N[m]&N[n]==N[1]:c+=2
print c/n/n

```

Running:

```
$ pypy x <<<1
1.0
$ pypy x <<<10
0.63
$ pypy x <<<100
0.6087
$ pypy x <<<1000
0.608383

```

The code counts the co-prime pairs `(n,m) for m<n` twice (`c+=2`). This ignores `(i,i) for i=1..n` which is ok except for `(1,1)`, thus being corrected by initialising the counter with `1` (`1.0` to prepare for float division later) to compensate.
> 1 votes

# Answer
# Factor, ~~120~~ 113 bytes

I've spent class golfing this and I can't get it shorter.

Translation of: Julia.

```
[ [a,b] dup append 2 <combinations> [ members ] keep [ first2 coprime? ] filter [ length ] bi@ 2 /i 1 + swap /f ]

```

Example runs on the first 5 test cases (a value of 1000 causes it to freeze the editor, and I can't be bothered to compile an executable right now):

```
! with floating point division
IN: scratchpad auto-use {
      1
      2
      4
      10
      100
    }
    [
      [1,b] dup append 2 <combinations> [ members ] keep
      [ first2 coprime? ] filter [ length ] bi@ 2 /i 1 + swap /f
    ]
    map

--- Data stack:
{ 1.0 0.75 0.6875 0.63 0.6087 }
! with rational division
IN: scratchpad auto-use {
      1
      2
      4
      10
      100
    }
    [
      [1,b] dup append 2 <combinations> [ members ] keep
      [ first2 coprime? ] filter [ length ] bi@ 2 /i 1 + swap /
    ]
    map

--- Data stack:
{ 1.0 0.75 0.6875 0.63 0.6087 }
{ 1 3/4 11/16 63/100 6087/10000 }

```
> 1 votes

# Answer
# Whispers v2, 75 bytes

```
> 1
> Input
>> φ(L)
>> ∑ 1 2 3
>> 4+4
>> ≺5
>> 2²
>> 6÷7
>> Output 8

```

Try it online!

## How it works

Implements Dennis's algorithm.

We calculate \\$m = \sum\_{k=1}^n\phi(k)\\$. We then double \\$m\\$ and decrement it to get \\$2m-1\\$, before squaring \\$n\\$ and dividing by it, to output \\$\frac{2m-1}{n^2}\\$
> 1 votes

# Answer
# , 78 bytes

```
mean(mapply(function(x,y)sum(!x%%which(!y%%1:y))<2,1:(N=scan()),rep(1:N,e=N)))

```

Try it online!

Uses `which(!y%%1:y)` to calculate divisors of y (including 1), and `!x%%divisors_of_y` to count common divisors of x and y (including 1), so `sum(common_divisors)<2` is `TRUE` for co-prime pairs.

The R `mapply` function applies a custom function to two (or more) sets of arguments, here specified as `1:N` and `rep(1:N,each=N)` (which repeats each number in `1:N`, `N` times).

Conveniently, R 'recycles' the shorter argument list to the length of the longer one, so `1:N` gets repeated for us automaticaly.
> 1 votes

---
Tags: code-golf, math, arithmetic, number-theory, pi
---


title: Szekeres's sequence

text:
# Question
Title: Szekeres's sequence
# Definition

* \\$a(1) = 1\\$
* \\$a(2) = 2\\$
* \\$a(n)\\$ is smallest number \\$k\>a(n-1)\\$ which avoids any 3-term arithmetic progression in \\$a(1), a(2), ..., a(n-1), k\\$.
* In other words, \\$a(n)\\$ is the smallest number \\$k\>a(n-1)\\$ such that there does not exist \\$x, y\\$ where \\$0\<x\<y\<n\\$ and \\$a(y)-a(x) = k-a(y)\\$.

# Worked out example

For \\$n=5\\$:

We have \\$a(1), a(2), a(3), a(4) = 1, 2, 4, 5\\$

If \\$a(5)=6\\$, then \\$2, 4, 6\\$ form an arithmetic progression.

If \\$a(5)=7\\$, then \\$1, 4, 7\\$ form an arithmetic progression.

If \\$a(5)=8\\$, then \\$2, 5, 8\\$ form an arithmetic progression.

If \\$a(5)=9\\$, then \\$1, 5, 9\\$ form an arithmetic progression.

If \\$a(5)=10\\$, no arithmetic progression can be found.

Therefore \\$a(5)=10\\$.

# Task

Given \\$n\\$, output \\$a(n)\\$.

# Specs

* \\$n\\$ will be a positive integer.
* You can use 0-indexed instead of 1-indexed, in which case \\$n\\$ can be \\$0\\$. Please state it in your answer if you are using 0-indexed.

# Scoring

Since we are trying to avoid 3-term arithmetic progression, and 3 is a small number, your code should be as small (i.e. short) as possible, in terms of byte-count.

# Testcases

The testcases are 1-indexed. You can use 0-indexed, but please specify it in your answer if you do so.

```
1     1
2     2
3     4
4     5
5     10
6     11
7     13
8     14
9     28
10    29
11    31
12    32
13    37
14    38
15    40
16    41
17    82
18    83
19    85
20    86
10000 1679657

```

# References

# Answer
# Jelly, 4 bytes

```
Bḅ3‘

```

Try it online! or verify all test cases.

### How it works

This uses 0-based indexing and the primary definition from OEIS:

> Szekeres's sequence: **a(n)-1** in ternary = **n-1** in binary

```
Bḅ3‘  Main link. Argument: n

B     Convert n to binary.
 ḅ3   Convert from ternary to integer.
   ‘  Increment the result.

```
> 11 votes

# Answer
# Haskell, ~~37 36~~ 32 bytes

Using the given formula in the OEIS entry, using 0-based indices. Thanks @nimi for 4 bytes!

```
a 0=1;a m=3*a(div m 2)-2+mod m 2

```
> 7 votes

# Answer
# Python 3, 28 bytes

```
lambda n:int(bin(n)[2:],3)+1

```

An anonymous function that takes input via argument and returns the result. This is zero-indexed.

**How it works**

```
lambda n    Anonymous function with input zero-indexed term index n
bin(n)      Convert n to a binary string..
...[2:]     ...remove `0b` from beginning...
int(...,3)  ...convert from base-3 to decimal...
...+1       ...increment...
:...        and return

```

Try it on Ideone
> 3 votes

# Answer
# Python 3, 113 bytes

```
def f(n):
 i=1;a=[]
 for _ in range(n):
  while any(i+x in[y*2for y in a]for x in a):i+=1
  a+=[i]
 return a[n-1]

```

Ideone it!
> 2 votes

# Answer
# Ruby, ~~28~~ 24 bytes

Using the same method as Dennis, with 0-based indexes:

```
->n{n.to_s(2).to_i(3)+1}

```

Run the test cases on repl.it: https://repl.it/Cif8/1
> 2 votes

# Answer
## Pyke, 5 bytes

```
b2b3h

```

Try it here!

0-based indexing

Same formula as jelly answer
> 2 votes

# Answer
# APL (Dyalog Extended), 5 bytes

```
1+3⊥⊤

```

Try it online!

Jo King's suggestion.

# APL (Dyalog Unicode), 12 bytes

```
1+3⊥2(⊥⍣¯1)⊢

```

Try it online!

Based on Dennis' Jelly answer.

Outputs are zero indexed.

```
1+3⊥2(⊥⍣¯1)⊢
           ⊢ Take argument
    2(⊥⍣¯1)  Encode in binary
  3⊥         Decode from ternary
1+           Add 1

```
> 2 votes

# Answer
# Java 7, ~~60~~ 42 bytes

0 Indexed

```
int s(int n){return n<1?1:3*s(n/2)-2+n%2;}

```

Using the implicit sequence definition from OEIS. Thanks to Kevin for the improvement using only one return statement.
> 1 votes

# Answer
## Java 8, ~~52~~ 46 bytes

0 indexed.

```
i->Integer.valueOf(Integer.toString(i,2),3)+1;

```
> 0 votes

# Answer
# Pip, 11 bytes

```
1+(aTB2)FB3

```

Try it online!

Based on Dennis' Jelly answer. Zero Indexed.
> 0 votes

# Answer
# Japt, 4 bytes

0-indexed

```
Ò¢n3

```

Try it or run all test cases from the OEIS entry

Same as most other solutions:

```
Ò¢n3     :Implicit input of integer U
Ò        :Negation the bitwise NOT of
 ¢       :U converted to a binary string
  n3     :Converted from a ternary string

```
> 0 votes

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


title: Dovetail two blocks of bits

text:
# Question
Title: Dovetail two blocks of bits
Check if two blocks of bits dovetail perfectly.

# Specifications

* A block of bits is a fixed sequence of 8 bits just like this for example : **11110101**.
* For simplicity we refer to `truthy`/`falsey` values as `1`/`0` bits but they can be everything capable of representing those two states in a clear, well defined and consistent way, for example :`0/1` `x/y` `False/True` `"false"/"true"` `'a'/'b'` `[]/[...]` `odd/even` `>0 / <0` `0 / !0`

**What does it mean dovetail perfectly?**

* 1's bits of one block can fit only into 0's of the other block or outside it.
* You can shift an entire block left or right but you cannot modify a block nor reverse it.
* The resulting block must contain all 1's of both inputted blocks and only those.
* There must not be any 0's between 1's while there can be any trailing and leading 0's.
* The resulting block can be more than 8 bits long.
* Example

```
 Input : [ 10010111, 01011010 ]

             10010111
             ↓  ↓ ↓↓↓
           01011010   <- shif by 2
  result   0111111111  => dovetails perfectly

```

**Input:** two blocks of bits.

* You don't need to handle empty blocks (all 0's).

**Output:** your solution have to clearly state if input blocks can dovetail perfectly as described above or not.

* the resulting block won't be a valid answer.

# Test cases.

```
00000000, 00000000 | you don't
00000000, ...      | need to
...     , 00000000 | handle these

11111111, 11111111 -> True
11111111, 10000000 -> True
11110000, 00101000 -> False
00101000, 10100000 -> True
10000000, 00111000 -> True
00110011, 11001100 -> True
00010000, 11101010 -> False
10000100, 10111101 -> True
01111010, 01011111 -> True
10010101, 00001101 -> False
01010011, 10110000 -> True
00000111, 00010011 -> False
00000011, 00000101 -> False

```

# Rules

* Input/output can be given by any convenient method.
* You can print it to STDOUT, return it as a function result or error message/s.
* Either a full program or a function are acceptable.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

---

Sandbox

# Answer
> 7 votes
# JavaScript (ES6),  ~~63 54 52~~  50 bytes

*Saved 2 bytes by applying an optimization similar to the one suggested by @AZTECCO on my C answer*

Expects `(a)(b)`, where **a** and **b** are bytes. Returns **0** if the blocks can dovetail perfectly or **1** otherwise.

```
a=>g=b=>b?a<<8&b|(c=a<<8|b,c+=c&-c)&c-1&&g(b<<1):1

```

Try it online!

### How?

The recursive function **g** attempts to shift **b** to the left, 1 position at a time, until the following conditions are both met:

* `(a << 8) & b` is equal to **0**, i.e. **a \<\< 8** and **b** have no set bits in common
* `c = (a << 8) | b` is a sequence of consecutive **1**'s, possibly followed by trailing **0**'s

For the second test, we add to **c** the rightmost set bit in **c** and see if this results in a single **1**, by carry propagation along the sequence of consecutive **1**'s.

We use the following bitwise tricks:

```
c & -c      // returns the rightmost set bit in c

c & (c - 1) // returns c without the rightmost set bit in c
            // (0 if c is an exact power of 2)

```

Example:

```
0111111000 + (0111111000 & -0111111000) = 0111111000 + 0000001000 = 1000000000
1000000000 & (1000000000 - 1) = 1000000000 & 0111111111 = 0

```

We stop the recursion when `b = 0`, which means that all bits have been thrown away. (This is why we do `b << 1` instead of `b * 2`, so that **b** is forced to a 32-bit integer rather than an IEEE 754 floating-point number.)

# Answer
> 5 votes
# Python 3, 68 bytes

```
lambda a,b:any(a<<8&b<<x==('01'in bin(a<<8^b<<x))for x in range(17))

```

Try it online!

The function tries all overlap configurations of the two binary sequences. It performs a bitwise `xor` for each configuration and checks if all the resulting `1`s are consecutive. This gives a false positive for some cases where the `xor` operation results in a leading `0`, so additionally it checks if the bitwise `and` operation yields `0`.

-4 bytes thanks to xnor

# Answer
> 5 votes
# Python 2, ~~78~~ ~~59~~ 57 bytes

Output is via exit code. The program fails (1) for truthy inputs and completes (0) for falsely ones. Input are two non-negative integers.

This is now quite similar to Arnauld's answers, but I found the `d&-d` trick on this website.

```
a,b=input()
b<<=8
exec"d=a|b;a&b<1>d&(d&-d)+d>q;a*=2;"*17

```

Try it online!

# Answer
> 4 votes
# C (gcc),  ~~61 58 57~~  53 bytes

*Saved 4 bytes thanks to @AZTECCO*

A port of my JS answer.

Returns **0** if the blocks can dovetail perfectly or a non-zero integer otherwise.

```
c;f(a,b){for(a<<=8;b&&a&b|(c=a|b,c+=c&-c)&c-1;b*=2);}

```

Try it online!

# Answer
> 3 votes
# Jelly,  ~~18~~  17 bytes

```
T_8+Ɱ17;ṢIPʋ€T}1e

```

A dyadic Link accepting two lists of eight ones/zeros which yields `1` if they may dovetail, or `0` if not.

**Try it online!** Or see the test-suite (I reordered them to have the eight truthy cases followed by the five falsey cases).

There is probably a terser way...

### How?

```
T_8+Ɱ17;ṢIPʋ€T}1e - Link: block A; block B
T                 - truthy indices of A
 _8               - subtract eight from each
     17           - seventeen
   +Ɱ             - map with addition -> a list of the 17 shifted versions of T
            €     - for each:
             T}   -   using the truthy indices of B as the right argument
           ʋ      -   last four links as a dyad:
       ;          -     concatenate
        Ṣ         -     sort
         I        -     incremental differences
          P       -     product (0 if two 1-bits collide; >1 if zero-gaps would result)
               1e - does 1 exist in that result?

```

# Answer
> 3 votes
# 05AB1E, 18 bytes

```
¬0*æδì`âε0ζO0ÚPΘ}à

```

Input as a pair of lists of bit-integers, outputs `1`/`0` for truthy/falsey respectively.

Try it online or verify all test cases. (The test suite contains an additional `Ù` after the `æ`, otherwise it'll time out. The single TIO takes roughly 35-40 seconds without this uniquify.)

**Explanation:**

```
¬                # Push the first list of the (implicit) input-pair (without popping)
 0*              # Multiply each value by 0 to create a list of 0s of that same length
   æ             # Get the powerset of this list of 0s (including empty list)
                 # (prefixes builtin would be preferably here, but unfortunately it lacks
                 #  an empty list; obviously this powerset contains a lot of duplicated
                 #  lists, which is why the uniquify `Ù` in the test suite is used to
                 #  make the program faster)
    δ            # Apply double-vectorized (using the powerset of 0s and implicit input)
     ì           #  Prepend the list of 0s to the inner input-list
      `          # Pop and push both list of lists separated to the stack
       â         # Use the cartesian product to get every possible pair of inner lists
        ε        # Map each pair of lists to:
          ζ      #  Zip/transpose; swapping rows/columns,
         0       #  using a 0 as trailing filler-item if the lists are unequal in length
           O     #  Sum each inner pair
            0Ú   #  Remove all leading and trailing 0s from this list
              P  #  Take the product of the remaining values
               Θ #  And check that this is equal to 1
        }à       # After the map: check if any are truthy by taking the maximum
                 # (after which this is output implicitly as result)

```

Try it online for a step-by-step from input to output (with the uniquify to speed it up).

# Answer
> 3 votes
# Husk, 15 bytes

```
VΠ¤×ż≠ö→kΣQṠ+mṗ

```

Try it online! or verify test cases. Output is a positive integer for truthy cases and 0 for falsy.

## Explanation

Parentheses added for clarity.

```
VΠ¤(×ż≠)(→kΣQ(Ṡ+mṗ))   Implicit inputs: two lists of integers.
  ¤( A )(     B    )   Apply B to both and combine with A.
         →kΣQ(Ṡ+mṗ)    Argument is a list x.
                m      Map
                 ṗ     primality test
              Ṡ+       and concatenate before x.
                       Since 0 and 1 aren't primes, this effectively prepends 8 zeros.
            Q          All contiguous slices.
          k            Classify (into separate lists)
           Σ           by sum.
         →             Get the last class, i.e. the slices with maximal sum.
                       They are those that contain all the 1s of x.
    ×ż≠                Combining function:
    ×                  Cartesian product by
     ż                 zip (preserving overflowing elements) by
      ≠                absolute difference.
                       Now we have a list of all combinations of slices from both extended lists,
                       with 1 and 1 producing 0.
V                      Does any of them have
 Π                     nonzero product (all 1s)?

```

# Answer
> 3 votes
# x86 32-bit machine code, 27 bytes

An x86-64 version would be callable from C as `int dovetail(dummy, unsigned x, unsigned y);` Returns EAX=0 for dovetail, non-zero for not; all paths of execution for non-zero inputs that don't dovetail lead to `EAX=(x<<n)|y` as the last thing calculated in EAX before returning. Also more simply and obviously, returns ZF=1 for dovetail, ZF=0 for not.

Try it online!. NASM listing: offset, machine code, source

```
 1                         dovetail:                   ; bool dovetail (ESI, EDX)
 2 00000000 86F2               xchg  dh, dl             ; shl edx,8 ; upper bytes are zero
 3                         .loop:
 4 00000002 85F2               test  edx, esi
 5 00000004 7510               jnz   .overlap           ; skip any bit conflicts
 6
 7 00000006 8D0432             lea   eax, [edx+esi]     ; equivalent to | or ^ for non-overlapping bits
 8 00000009 0FBCC8             bsf   ecx, eax           ; count trailing zeros
 9 0000000C D3E8               shr   eax, cl            ; shift out low zeros
10 0000000E 40                 inc   eax                ; turn contiguous low bits into 1 set bit
11
12 0000000F 8D48FF             lea  ecx, [eax-1]        ; clear lowest set bit
13 00000012 21C8               and  eax, ecx            ; like blsr  eax, eax
14 00000014 7404               jz   .dovetail_found     ; there was only 1 set bit, now 0
15                         .overlap:
16 00000016 01F6               add  esi, esi
17 00000018 79E8               jns  .loop             ; keep looping until ESI hits the top
18
19                         .dovetail_found:
20                             ;; return value in ZF:
21                                   ; 1 for dovetail detection by BLSR
22                                   ; 0 for exiting loop via ESI setting SF: implies non-zero
23 0000001A C3                 ret

```

See https://catonmat.net/low-level-bit-hacks for an overview of bithack tricks including isolating or clearing the lowest set bit.

---

Alternate versions:

BMI1 `blsr eax, eax` is 5 bytes, same as `lea edx, [rax-1]` / `and eax, edx`. That would require BMI1 (Haswell+, Piledriver+). I used `and` instead of `test` so an integer result in EAX would be available.

BMI1 `blsi ecx, eax` (5B) / `add eax, ecx` (2B) (`eax += lowest_set_bit(eax)`) turned out *not* to be the shortest way to turn a contiguous bit-range into a single set bit. Instead, shifting to the bottom with `bsf` / `shr` / `inc` saved 1 byte in 32-bit code, for a total of 6 bytes to turn a contiguous bit-range into a single set bit. An x86-64 version (no single-byte `inc` encoding) could save instructions at equal code-size by doing that, though, if BMI1 was available.

---

I was hoping to avoid doing the `x & y == 0` test separately from combining the bits. e.g. by **XORing** them together and checking that a contiguous bit-range started at the bottom of one of the inputs:

```
    mov  eax, edx
    xor  eax, esi
    jz  .all_cancelled      ; exclude all-zeros from the 1-set-bit test

    blsi  ecx, esi          ; isolate lowest set of the shifting input
    add   eax, ecx          ; carry turns contiguous set bits into 1
                    ; BROKEN, need blsi(esi|edx)

```

But we can't just use the lowest set bit of the XOR result; some conflicting bits might have cancelled each other. e.g. x=0b110010 y=1 would give a false-positive when with `x ^ (y<<1) = 0b110000` having all its set bits contiguous.

And it doesn't work to isolate the lowest set bit of the input you're shifting; once you shift it left past the lowest set bit of the other input, you need to be adding *that* isolated bit instead. e.g. the following input was mis-handled by my first version using `xor` and `blsi ecx, esi`, because it only dovetails with ESI's lowest bit shifted left past EDX's lowest set bit.

```
mov edx, 0b0110010
mov esi, 0b1001100

```

This way could still work with some kind of `min(blsi(x), blsi(y))`, or `blsi(x|y)`, but doing that separately is not a win.

# Answer
> 2 votes
# Factor, ~~149~~ 139 bytes

```
: d ( a b -- ? ) [ 8 [ 0 suffix ] times 15 rotate ] bi@
all-rotations [ dupd [ + ] 2map [ 0 = ] trim all-equal? ] map
f [ or ] reduce nip ;

```

Try it online!

Gets the input as arrays of integers.

A naive solution - pads both arrays with 8 additional 0s, then adds each of the rotations of the second array to the first one, trims the leading/trailing zeros and check if the resulting arrays consist only of one number (1).

# Answer
> 2 votes
# Retina 0.8.2, ~~82~~ 81 bytes

```

$'¶$`;
(.+),(.*;.*)
$2,$1
+`;(.)(.*),(.)
-$1$3;$2,
-(0|(1))+
$#2
;|,

m`^0*1+0*$

```

Try it online! Link includes test cases. Explanation:

```

$'¶$`;

```

Create duplicates of the input with `;`s inserted at every position.

```
(.+),(.*;.*)
$2,$1

```

Swap the two inputs if the `;` lies within the second.

```
+`;(.)(.*),(.)
-$1$3;$2,

```

Try to dovetail the part between the `;` and the `,` with the other input.

```
-(0|(1))+
$#2

```

Count the number of bits in each overlap.

```
;|,

```

Delete the separators.

```
m`^0*1+0*$

```

Check whether a dovetail produced a valid result. Edit: Saved 1 byte by returning any non-zero value for a valid result (value is number of possible dovetailings plus one if concatenating the inputs is a valid dovetailing).

# Answer
> 2 votes
# C (gcc), ~~105~~ \\$\cdots\\$ ~~63~~ 62 bytes

Saved a whopping 13 bytes thanks to the man himself Arnauld!!!
Saved a byte thanks to AZTECCO!!!

```
t;f(a,b){for(a<<=t=8;b&&t;b*=2)t=a|b,t/=t&-t,t=a&b|t&-~t;t=b;}

```

Try it online!

Returns \\$!0\\$ for true and \\$0\\$ otherwise.

### Explanation

Shifts the first parameter, \\$a\\$, over \\$8\\$-bits so we can try all different shift positions by just shifting the second parameter, \\$b\\$. Loops over all shifts of \\$b\\$ checking to see if all bits are ever different from \\$a\\$ and \\$b\\$ forms one continuous block of \\$1\\$s when combined with \\$a\\$.

# Answer
> 2 votes
# Perl 5 `-p`, 68 bytes

```
s/\b0+|0+\b//g;s/(1*)(.*?)(1*) //;y/01/10/;$_=/^(0*$1)?$2(${3}0*)?$/

```

Try it online!

* `s/\b0+|0+\b//g` trims 0 from two blocks
* `s/(1*)(.*?)(1*) //` substitution to remove the first argument, and capture 3 groups :

+ $1: the left ones
    + $2: shortest sequence between
    + $3: the right ones (eventually)
* `y/01/10/` transliteration of second argument remaining (bitwise not)
* `/^(0*$1)?$2(${3}0*)?$/` the pattern second argument (inverted) must match

# Answer
> 1 votes
# C (gcc), ~~94~~ ~~82~~ ~~71~~ 70 bytes

*Edit: -12 bytes by poring over Noodle9's similar C answer and rather shamelessly stealing all of the golfing tricks that I could use here... so please upvote that one, too!*

*More edits: ...thanks to various stolen tips & tricks from Arnauld, also -12 more bytes...*

```
c;i;f(a,b){for(b<<=9,i=18;i-->1;i*=a&b||c&c++)a*=2,c/=(c=b|a)&-c;i=i;}

```

Try it online!

My first ever answer in 'C' (which embarassingly didn't work the first time: thanks to Arnauld for spotting the bug...).

Input is two 8-bit integers, outputs '-1' (truthy) if bits of input dovetail together perfectly, '0' (falsy) otherwise.

Works by first bit-shifting b by 9 bits, and then testing for successful dovetailing with a shifted by 1..18 bits (so, all-the-way to the right up to all-the-way to the left).
Tests dovetailing at each position by checking that a AND b is zero (so there are no 'clashing' bits), then taking A XOR B, chopping-off any trailing zeros, and testing whether x AND (x+1) is equal to zero (which is only true for 2^n-1 = strings of 1-bits).

# Answer
> 1 votes
# Charcoal, 29 bytes

```
¬⬤α№⭆↨⁺×Ｘ³χ⍘η³×Ｘ³κ⍘θ³¦³⮌⍘λ²01

```

Try it online! Works by dovetailing in base 3, which avoids issues other answers have when trying to XOR or add the values together. Explanation:

```
  α                             (Uppercase alphabet)
¬⬤                              No indices match
   №                            (Non-zero) Count of
                           01   Literal string `01` in
                   θ            First input
                  ⍘ ³           Converted as if base 3
              ×                 Multiplied by
                ³               Literal 3
               Ｘ                Raised to power
                 κ              Current index
      ⁺                         Plus
            η                   Second input
           ⍘ ³                  Converted as if base 3
       ×                        Multiplied by
         ³                      Literal `3`
        Ｘ                       Raised to power
          χ                     Predefined constant 10
     ↨                ³         Converted to base 3 as a list
    ⭆                           Map over digits
                         λ      Current digit
                        ⍘ ²     Converted to base 2 as a string
                       ⮌        Reversed
                                Implicitly print

```

# Answer
> 1 votes
# Java 8, ~~86~~ ~~83~~ 82 bytes

```
(a,b)->{int i=18,t;for(a<<=8;--i>0;i=(a&b)>-(t&(t&-t)+t)?i:0,b*=2)t=a|b;return i;}

```

Inspired by halve the other answers. -3 bytes thanks to *@AZTECCO*.
-1 byte thanks to *@ceilingcat*.

Inputs as (32-bit) integers. Output as `-1` for truthy and `0` for falsey.

Try it online.

**Explanation:**

```
(a,b)->{               // Method with two integer parameters and boolean return-type
  int i=18,            //  Index-integer, starting at 18
      t;               //  Temp-integer, uninitialized
  for(a<<=8;           //  Bit-shift the first input-integer `a` 8 bits to the left
      --i>0            //  Loop `i` in the range (18, 0):
      ;                //    After every iteration:
       i=(a&b)         //     Get `a` bitwise-AND `b`
         <             //     And check that it's smaller than:
          -(           //      The negative of:
            t          //      `t`
             &         //      Bitwise-AND with:
              (t&-t)   //       `t` bitwise-AND `-t`
                    +t)//       and add `t`
         ?             //     If this is truthy:
          0            //      Change `i` to 0 (which will also stop the loop)
         :             //     Else:
          i,           //      Keep `i` the same
       b*=2)           //     And multiply `b` by 2
    t=a|b;             //   Set `t` to `a` bitwise-OR `b`
  return i;}           //  Return `i` as result (where -1 means we've changed `i` to 0
                       //  manually as truthy output and 0 means the loop has fully
                       //  looped as falsey output)

```

---
Tags: code-golf, decision-problem, binary
---


# Question
Title: Maximal saturated domino covering of a rectangle
Inspired by this OEIS entry.

## Background

A **saturated domino covering** is a placement of dominoes over an area such that

1. the dominoes are completely inside the area,
2. the dominoes entirely cover the given area,
3. the dominoes may overlap, and
4. removal of any domino reveals an uncovered cell (thus failing to satisfy condition 2).

The following is an example of a maximal such covering of `3 × 3` rectangle (since dominoes may overlap, each domino is drawn separately):

```
AA.   B..   ..C   ...   ...   ...
...   B..   ..C   .D.   ...   ...
...   ...   ...   .D.   EE.   .FF

```

## Challenge

Given the dimensions (width and height) of a rectangle, compute the maximum number of dominoes in its saturated domino covering.

You can assume the input is valid: the width and height are positive integers, and `1 × 1` will not be given as input.

Standard rules apply. The shortest code in bytes wins.

## Test cases

A193764 gives the answers for square boards. The following test cases were verified with this Python + Z3 code (not supported on TIO).

Only the test cases for `n <= m` are shown for brevity, but your code should not assume so; it should give the same answer for `n` and `m` swapped.

```
n m => answer
1 2 => 1
1 3 => 2
1 9 => 6
1 10 => 6
2 2 => 2
2 3 => 4
2 5 => 7
3 3 => 6
3 4 => 8
3 7 => 15
4 4 => 12
4 7 => 21

```

# Answer
# Sagemath, 60 bytes

```
lambda m,n:m*n-len(graphs.GridGraph([m,n]).dominating_set())

```

Try it online!

---

From Saturated Domino Coverings by Buchanan et al:

> **Corollary 6.3:** *If \\$B\\$ is a rectangular \\$m \times n\\$ board, then \\$d(B) = |B| - \gamma(G\_{m,n})\\$.*

Where \\$\gamma(\ldots)\\$ is the domination number and \\$G\_{m,n}\\$ is a grid graph. We also clearly have that if \\$B\\$ represents an \\$m\times n\\$ board then \\$|B| = mn\\$.
> 8 votes

# Answer
# JavaScript (ES6), 120 bytes

A shorter (and slower) version, using the same algorithm with `eval()` and two `for` loops.

Expects `(m)(n)`.

```
m=>n=>eval("for(M=0,b=1<<m*n;b--;)for(k=j=m*n;j--?b>>j&1&&k--||(b<<m|b>>m|(j%m&&b*2)|(~j%m&&b/2))>>j&1:k>M&&!(M=k););M")

```

Try it online!

Or try an implementation in C (gcc) (127 bytes) which can process the last test case on TIO.

---

# JavaScript (ES6), 128 bytes

Expects `(m)(n)`.

```
m=>n=>[...Array(1<<m*n)].map(M=(_,b)=>(g=j=>j--?b>>j&1&&k--||(b<<m|b>>m|(j%m&&b*2)|(~j%m&&b/2))>>j&1?g(j):0:k<M?0:M=k)(k=m*n))|M

```

Try it online!

### How?

This is based on the formula used by Sisyphus, except that we have to actually compute \\$\gamma(G\_{m,n})\\$ since there's obviously no JS built-in for that.

For each \\$b\\$, \\$0\le b\<2^{m\times n}\\$, we test whether at least one of the following conditions is true for all \\$j\\$, \\$0\le j\<m\times n\\$:

* the \\$j\\$-th bit of \\$b\\$ is set
* or the \\$j\\$-th bit of \\$b\\$ is adjacent to a set bit in \\$b\\$ when re-arranging the bits in a grid of size \\$m\times n\\$

If this is successful, the set bits in \\$b\\$ represent the vertices of a valid dominating set of the \\$m\times n\\$ grid graph.

While doing that, we also compute the number \\$k\\$, which is equal to \\$m\times n\\$ minus the total number of bits that are set in \\$b\\$. We update the final result \\$M\\$ to \\$k\\$ whenever \\$b\\$ is a valid bit mask and \\$k\ge M\\$.

### Commented

```
m => n =>                 // (m, n) = size of the grid
[...Array(1 << m * n)]    // build an array of 2 ** (m * n) values
.map(M =                  // initialize M to a non-numeric value
(_, b) => (               // for each b, 0 <= b < 2 ** (m * n):
  g = j =>                //   g is a recursive function taking a counter j
    j-- ?                 //     decrement j; if it was not equal to 0:
      b >> j & 1          //       if the j-th bit of b is set:
        && k--            //         decrement k
      ||                  //       otherwise, we compute a bit mask where all bits of
      (                   //       b adjacent to the j-th bit in the grid are shifted
                          //       to the rightmost position and OR'd together:
        b << m |          //         this is the bit 'below'
        b >> m |          //         this is the bit 'above'
        (j % m && b * 2)  //         this is the bit 'on the right', which is valid
        |                 //         only if j mod m = 0
        (~j % m && b / 2) //         this is the bit 'on the left', which is valid
                          //         only if (j + 1) mod m = 0
      ) >> j & 1          //       test the least significant bit of the result
      ?                   //       if one of the above tests is successful:
        g(j)              //         do a recursive call
      :                   //       else:
        0                 //         abort
    :                     //     else:
      k < M ? 0 : M = k   //       if k is better than M, update M to k
  )(k = m * n)            //   initial call to g with j = k = m * n
) | M                     // end of map(); return M

```
> 4 votes

# Answer
# 05AB1E, 33 bytes

```
*LIô2FD€ü2€`sø}\«æʒ˜D¢2ô2@PO_}éθg

```

Input as two loose integers.

Try it online or verify the small test cases.

**Explanation:**

Step 1: Get a list of all possible dominos based on the input-dimensions:

```
*              # Multiply the two (implicit) inputs together
 L             # Pop and push a list in the range [1, n*m]
  Iô           # Split it into parts equal to the second input
    2F         # Loop 2 times:
      D        #  Duplicate the matrix at the top of the stack
       €       #  For each row:
        ü2     #   Create overlapping pairs
          €`   #  Flatten it one level down to a list of pairs
            s  #  Swap so the copy is at the top of the stack
             ø #  Zip/Transpose; swapping rows/columns
     }\        # After the loop: discard to leftover copy
       «       # And merge the two list of pairs together

```

Step 2: Create all possible combination of dominos:

```
æ              # Get the powerset of this list of pairs

```

Step 3: Filter every possible combination so only valid ones are left that comply to all four rules:

```
ʒ              # Filter the list of list of pairs by:
 ˜             #  Flatten the list of pairs to a list of integers
  D            #  Duplicate it
   ¢           #  Count each integer in the flattened list
    2ô         #  Convert it back to a list of pairs
               #  (unfortunately `¢` doesn't vectorize apparently, otherwise `D˜¢` would
               #   have sufficed..)
      2@       #  Check for each count if it's >= 2
        P      #  Check if this is truthy for both values within a pair
         O     #  Sum the checks of all pairs together
          _    #  And check that this is 0 (thus falsey for all of them)
}              # Close the filter

```

Step 4: Get the length of the longest valid board of dominos, and print it as our result:

```
é              # Sort the list of list of pairs by length
 θ             # Pop and push the last/longest list of pairs
  g            # And pop and push its length
               # (after which it is output implicitly as result)

```
> 3 votes

# Answer
# Jelly, 39 bytes

```
ṙJḊÑ$€¬Ȧ
ẎQL=³×⁴¤
pp`_/ṢF⁼ʋƇØ.ŒPÇƇÑƇL€Ṁ

```

Try it online!

This is kinda (very) clunky lol. Haven't used Jelly in a while.

Will golf for a bit before I give a full explanation, but basically how it works is it generates all of the cells, and then gets all adjacent pairs to get all dominoes, then takes the powerset and filters for valid states by two conditions: firstly, using the second line to ensure all squares are covered, and secondly, using the first line to ensure condition 4 by checking all modifications of removing one domino and making sure all fail condition 2 using the second line.
> 2 votes

# Answer
# Charcoal, 60 bytes

```
ＮθＮη⊞υ×1×θηＦθＦηＦυ«⎚⪪ληＪκι¿∧ΣＫＫ№ＫＶ1«ＵＭΦＫＶΣμ0¹⊞υ⪫ＫＡω»»⎚Ｉ⌈Ｅυ№ι0

```

Try it online! Link is to verbose version of code. Brute force, so `4 × 7` times out on TIO. Explanation:

```
ＮθＮη

```

Input the dimensions of the rectangle.

```
⊞υ×1×θη

```

Start a breadth-first search with a string of `1`s representing an empty rectangle.

```
ＦθＦη

```

Loop over each row and column.

```
Ｆυ«

```

Loop over each rectangle discovered so far.

```
⎚⪪λη

```

Wrap the string to the size of the rectangle and output it on a clear canvas.

```
Ｊκι

```

Jump to the cell under consideration.

```
¿∧ΣＫＫ№ＫＶ1«

```

If both the cell and at least one neighbour are empty, then:

```
ＵＭΦＫＶΣμ0

```

Change all of the neighbours to `0`s (somewhat arbitrary choice; any non-digit except `-` would also work).

```
¹

```

Change the cell itself to `-` (chosen for golfiness of course).

```
⊞υ⪫ＫＡω

```

Save the resulting rectangle.

```
»»⎚Ｉ⌈Ｅυ№ι0

```

Print the maximum number of dominoes that were placed. (I can't believe that it's possible for the code to place more dominoes and yet fail to cover the rectangle than its best result that does cover the rectangle.)
> 1 votes

# Answer
# Jelly, 24 bytes

```
pŒcạ/SỊƊƇŒPẎċⱮⱮ$Ṃ€ṀỊƲƇṪL

```

A dyadic Link accepting the dimensions which yields the maximal number of dominos which may be placed.

**Try it online!** (Too slow for the last three test-cases, but here are all the others.)

### How?

Make all grid-contained dominos as pairs of coordinates, then filter the power-set of these to those sets which don't contain any domino whose coordinates are both contained by others, then return the length of the longest such set.

```
pŒcạ/SỊƊƇŒPẎċⱮⱮ$Ṃ€ṀỊƲƇṪL - Link: n; m
p                        - Cartesian product (all coordinates)
 Œc                      - all pairs (of coordinates)
        Ƈ                - filter keep those for which:
       Ɗ                 -   last three links as a monad:
    /                    -     reduce (the pair) by:
   ạ                     -       absolute difference
     S                   -       sum
      Ị                  -       insignificant? (effectively: equals 1?)
                           (-> all grid-contained dominos)
         ŒP              - power-set (ordered by length)
                     Ƈ   - filter keep those (sets of dominos) for which:
                    Ʋ    -   last four links as a monad:
               $         -     last two links as a monad:
           Ẏ             -       tighten (-> list of all coordinates used)
              Ɱ          -       map (across the dominos in the set) with:
             Ɱ           -         map (across the coordinates in the domino) with:
            ċ            -           count (of the coordinate in all coordinates used)
                Ṃ€       -     minimum of each
                  Ṁ      -     maximum
                   Ị     -     insignificant? (effectively: equals 1?)
                      Ṫ  - tail
                       L - length

```
> 1 votes

---
Tags: code-golf, combinatorics, grid, tiling, dominoes
---


title: The Perfect Polynomial

text:
# Question
Title: The Perfect Polynomial
The coefficients of a perfect square polynomial can be calculated by the formula \\$(ax)^2 + 2abx + b^2\\$, where both a and b are integers. The objective of this challenge is to create a program that not only can find if an input trinomial is a perfect square, but also find its square root binomial. The input trinomial will be written in this format:

```
1 2 1

```

which symbolizes the perfect square number \\$x^2 + 2x+ 1\\$, since all 3 input numbers represent coefficients of the trinomial. The outputs must be readable and understandable. To count as a perfect square in this challenge, a trinomial must have \\$a\\$ and \\$b\\$ as real integer numbers. No fractions, decimals, irrational numbers or imaginary/complex numbers allowed in the final binomial. Make a program that accomplishes this, and since this is , the shortest code in bytes wins.

# Answer
> 2 votes
# JavaScript (Node.js), 42 bytes

**I would delete this, but I can't because it's been accepted.**

```
(a,b,c)=>[A=Math.sqrt(a),b/A/2,b*b==c*a*4]

```

Try it online!

Can be called as `f(a,b,c)`. Output is in the form `[<factor of x>, <constant>, True/False]` (if it's False, then the first 2 values are meaningless).

---
Tags: code-golf, math, polynomials
---


title: C4_4 Reflection!

text:
# Question
Title: C4_4 Reflection!
In this challenge, your task is to input a rectangle ASCII pattern (You may assume only printable characters need to be handled, and you may assume a trailing newline or not), C4\_4 symmetrify, and output it.

Here, C4\_4 symmetric means symmetric under 90-degree rotation around a corner of the corner character. The corresponding "symmetrify" process is copy and rotate 90-degree clockwise three times, and then put all four copies together. For the precise arrangement, you can look at Test Cases.

# Test Cases

```
Input:
asdf
jkl;

Output:
    ja
    ks
asdfld
jkl;;f
  f;;lkj
  dlfdsa
  sk
  aj

Input:
.O.
..O
OOO

Output:
.O.O..
..OO.O
OOOOO.
.OOOOO
O.OO..
..O.O.

Input:
gc
oo
ld
fe

Output:
  gc
  oo
  ldflog
  feedoc
codeef
golfdl
    oo
    cg

```

# Answer
# Charcoal, 6 bytes

```
Ａ⟲Ｃ²⁴⁶

```

Try it online! Link is to verbose version of code. Explanation:  implicitly prints the input,  performs the rotation,  signifies to keep copies, and `²⁴⁶` represents the numbers of 45-degree rotations to make. (Charcoal defaults to rotating around the bottom-right corner as desired.)
> 7 votes

# Answer
# Python 3, 193 bytes

```
def f(s):q=len(s[0])-len(s);s=[[" "]*len(s[0])]*q+s;s=[[" "]*-q+l for l in s];j=lambda a,b:[x+y for x,y in zip(a,b)];r=lambda x:[*map(list,zip(*x[::-1]))];return j(s,r(s))+j(r(r(r(s))),r(r(s)))

```

Try it online!
> 4 votes

# Answer
# , 38 bytes

```
(,|."1@|.)@(,.|:@|.)@((2$_1*>./)@${.])

```

Try it online!

No doubt it can be golfed much further.
> 3 votes

# Answer
# JavaScript (ES6),  ~~178~~  173 bytes

Takes input as an array of strings. Returns a string.

```
m=>(g=x=>~y?(Y=y<w?y:W-y,X=x<w?x:W-x,Z=y<w^x<w?Y:X,(m[Z-z*d]||0)[(X^Y^Z)+!z*d]||' ')+[`
`[x-W]]+g(x<W?x+1:!y--):'')(0,w=m[0].length,h=m.length,d=w-h,(z=d>0)?0:w=h,y=W=w*2-1)

```

Try it online!
> 3 votes

# Answer
# Red, 217 bytes

```
func[a][n: max(l: length? a)length? a/1
p: copy""insert/dup p" "n
loop n - l[insert a copy p]forall a[pad/left a/1 n]repeat y n[repeat x n[append
a/:y a/(n - x + 1)/:y]]repeat y n[append a reverse copy a/(n - y + 1)]]

```

Try it online!

Returns a list of strings
> 2 votes

# Answer
# Icon, ~~255~~ 206 bytes

```
procedure f(a)
n:=*a;n<:=t:=*a[1]
1to n-*a&push(a,repl(" ",t))&\z
(!a)[1:1]:=repl(" ",n-t)&\z
i:=1to n&j:=1to n&a[i]||:=a[n-j+1,i]&\z
i:=1to n&put(a,"")&j:=1to 2*n&a[n+i]||:=a[n-i+1,2*n-j+1]&\z
return a
end

```

Try it online!
> 1 votes

# Answer
# Python 3, 140 bytes

```
def f(a):l=len(a[0]);k=len(a)-l;b=[k*' '+i for i in-k*[l*' ']+a];b+=[*map(''.join,zip(*b))][::-1];return[i+j[::-1]for i,j in zip(b,b[::-1])]

```

Try it online!

Expects and returns a list of lines.

### Explanation

```
def f(a):
 l=len(a[0]);k=len(a)-l;                     # Extract dimensions
 b=[k*' '+i for i in-k*[l*' ']+a];           # Make it square
 b+=[*map(''.join,zip(*b))][::-1];           # Construct left half of the output
 return[i+j[::-1]for i,j in zip(b,b[::-1])]  # Construct the right half and return

```
> 1 votes

# Answer
# APL (Dyalog Unicode), 22 bytes

```
{(⌽⍪⊖)(⍉,⌽)⍵↑⍨-2/⌈/⍴⍵}

```

Try it online!
> 0 votes

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


title: Hexasweep (part 1): The Solver

text:
# Question
Title: Hexasweep (part 1): The Solver
(This is part 1 in a two-part challenge.)

Your task is to solve a Hexasweep puzzle.

A Hexasweep puzzle is set out on a grid of diamonds arranged in hexagonal shapes, of which the board looks like a hexagon, like so:

```
         _____
        /\    \
  _____/ X\____\_____
 /\    \  / XX /\    \
/X \____\/____/X \____\
\ X/ XX /\    \ X/    /
 \/____/  \____\/____/
 /\    \  / X  /\    \
/  \____\/____/  \____\
\  / XX /\    \  / XX /
 \/____/  \____\/____/
       \ X/    /
        \/____/

```

The above image is composed of 7 hexagons (21 diamonds), and is thus a Hexasweep puzzle of size 2.

* If you want to expand it, cover the current Hexasweep puzzle with more hexagons (so that there are 19 hexagons - that will make a Hexasweep puzzle of size 3).
* The same goes for the other direction - to make a Hexasweep puzzle of size 1, remove the outermost layer of hexagons (so that there's 1 hexagon).

Each diamond can contain 0, 1 or 2 "bombs", with bombs depicted as `X` above. With bombs filled out, this is the **final solution**.

Numbers are marked on "intersection points", to show how many bombs are on the diamonds which are touching those intersection points - the intersection points of this grid are shown below using `O`.

```
         _____
        /\    \
  _____/  OO___\_____
 /\    \  OO   /\    \
/  OO___OO___OO  OO___\
\  OO   OO   OO  OO   /
 \/___OO  OO___OO____/
 /\   OO  OO   OO    \
/  OO___OO___OO  OO___\
\  OO   OO   OO  OO   /
 \/____/  OO___\/____/
       \  OO   /
        \/____/

```

As you can see, there are two "types" of intersection points - those with 3 diamonds touching it, and those with 6 (the one that are touching the edge of the board aren't counted):

```
  _____
 /\  XX\
/X OO___\
\ XOO   /
 \/____/

       /\
 _____/X \_____
 \ XX \ X/    /
  \____OO____/
  / XX OO  X \
 /____/  \____\
      \ X/
       \/

```

The two intersections would be marked with `4` and `8` respectively.

In the original Hexasweep puzzle above, the intersection numbers would be:

```
   3
4 5 4 2
 2 1 3
2 4 1 2
   1

```

Which would be condensed to:

```
3,4,5,4,2,2,1,3,2,4,1,2,1

```

Given an input in this "condensed form", you must output the original puzzle, in "condensed form" (see above).

The solved image (the first one, with the crosses) - which would be formed from the puzzle - would be read from top to bottom, starting from the left:

```
2,0,0,2,0,2,1,0,1,0,2,0,1,0,0,2,0,0,0,0,2

```

That is now the "condensed form" of the puzzle.

If there is more than 1 answer (as in the condensed form above), the output must be `N`.

### Examples:

```
0,0,4,3,1,3,4,7,1,4,3,6,1 -> 0,0,0,0,1,0,0,2,0,0,0,2,0,1,0,1,2,0,0,2,2 (size 2 Hexasweep)
6 -> 2,2,2 (size 1 Hexasweep)
0,1,5,3,1,4,4,7,2,5,3,6,1 -> N (multiple solutions)

```

### Specs:

* Any delimiter for the "condensed form" as input are allowed (it doesn't have to be `,` separating the numbers).
* You may output a list, or a string with any delimiter.
* Your program must be generalised: it must be able to solve Hexasweep puzzles of any size (at least from size 1 to size 4).

This is , so lowest amount of bytes wins!

# Answer
> 15 votes
# Javascript (V8), 1509 bytes

```
V=>{S=Math.sqrt(V[L="length"])/3+1|0;C=(Y=Array)(3**(W=12*(S-1)||2))[F="fill"]``.map(c=>Y(G=3*S*(S-1)+1)[F]``.map(h=>[N=-1,N,N]))
O=[];R=Y(4*S-3)[F]``.map(r=>[]);for(r=0,c=1,m=S,i=0;i<G;++r>=m&&(r=0,m+=++c>S?N:1))R[r*2+(X=Math.abs)(S-c)][P="push"](i++,N)
R=R.map(r=>(r.pop(t=Y(((T=2*S-1)-r[L]+1)/2)[F](N)),t.concat(r,t)));I=R.flat()[K="filter"](Q=r=>r+1);J=[[m=1,0]]
if(S>1){for(i=0;i<S-1;i++)J[P]([m+=3,0]);for(i=0;i<S-1;i++)J[P]([m-1,2],[m,0]);for(i=0;i<S-1;i++)J[P]([m-=3,0])}M=[]
J[K](j=>(t=j[1],Y(j[0])[F]``[K](_=>M[P](t++%3))))
z=0;g=p=>{for(j=0;j<R[L];j++)if(p<(t=R[j][K](Q))[L]){a=R[b=j].indexOf(t[p]);break}else p-=t[L]}
M=M.map((v,i)=>v?(v<2?(g(z-1),[[I[z-1],1],[I[z-1],2],[R[b-1][++a],0],[R[b-1][a],2],[R[b+1][a],0],[R[b+1][a],1]]):(g(z),[[I[z],0],[R[b-1][a-1],2],[R[b+1][a-1],1]])):(x=[0,1,2].map(d=>[I[z],d]),z++,x))
C.map((c,i)=>{r=-2;s=_=>[...i.toString(3).padStart(W,0).substr(r+=2,2).split``.map(n=>+n),N];for(j=0;j<S;c[j++]=s())
t=S-1;for(j=1;j<S;j++)c[++t]=s(),c[t+=j+S-1]=s();for(j=S-2;j>0;j--)c[++t]=s(),c[t+=j+S-1]=s();if(S>1)for(j=0;j<S;j++)c[++t]=s()})
C.map(c=>{q=1;l:while(c.find(h=>h[0]<0|h[1]<0|h[2]<0))for(j=0;j<M[L];j++){t=M[j];if(t[K](Z=v=>!(c[v[0]][v[1]]+1))[L]==1){if((s=V[j]-t.reduce(U=(a,v)=>a+(c[v[0]][v[1]]+1||1)-1,0))<0||s>2){q=0;break l};r=t.find(Z);c[r[0]][r[1]]=s}};
M.map((t,j)=>{if(t.reduce(U,0)!=V[j])q=0})
q&&O[P](c)});if(O[L]>1)return"N";O=O[p=0];E=[];for(i=0;i<T;i++){a=T-X(S-i-1);for(j=0;j<a;j++)E[P](O[p+j][0]);for(j=0;j<a;j++)E[P](O[p][1],O[p++][2])}return E}

```

Wow. This was not as fun as I expected it would be.

This is by far not an optimal solution. It's hard to golf something this big. I think you could save a hundred bytes or so by brute forcing the answer instead. However, my goal wasn't to be super competitive (yet!), but instead to provide a baseline for other answers to work off of.

Seeing as this challenge hasn't been answered in the four years since it was asked, it obviously took a few days. The strategy I ended up using was to generate a list of all possible values for the outer ring of hexagons, and repeatedly fill in any diamonds whose values can be inferred from the vertexes near them. If any contradictions are found, that starting value is ignored and the next one is analyzed.

This likely costs a few bytes compared to brute forcing, but it means it can finish running before the inevitable heat death of the universe. It takes less than a second for size one, about half a minute for size two, and based on the time complexity somewhere in the span of a few weeks to a few months for size three (haven't tested yet). My computer doesn't actually have enough memory for attempting higher than size two (gives me `invalid array length`), but with enough time and memory it's theoretically possible to use this approach for puzzles with millions of hexagons.

If anyone wants to use this to develop a shorter or faster solution, here's the pre-golfed version of my code (it's not very pretty, but it works):

```
var hexasweep = function(vertexes) {
    var size = Math.sqrt(vertexes.length) / 3 + 1 | 0;

    var configs = new Array(3 ** (2 * (6 * (size - 1) || 1))).fill(0).map(c => new Array(3 * size * (size - 1) + 1).fill(0).map(h => [-1, -1, -1]));

    var solutions = [];

    var reference_array = new Array(4 * size - 3).fill(0).map(r => []);

    for (let r = 0, c = 0, m = size, i = 0; i < 3 * size * (size - 1) + 1; i++) {
        reference_array[r * 2 + Math.abs(size - c - 1)].push(i, -1);

        if (++r >= m) {
            m += (++c >= size ? -1 : 1);
            r = 0;
        }
    }

    for (let t, r, i = 0; i < reference_array.length; i++) {
        r = reference_array[i];

        r.pop();

        t = new Array(((2 * size - 1) - r.length) / 2).fill(-1);

        reference_array[i] = t.concat(r, t);
    }

    var reference = reference_array.flat().filter(r => r + 1);

    var m = 1, length_map = [];

    length_map.push([m = 1, 0]);

    if (size > 1) {
        for (let i = 0; i < size - 1; i++) {
            length_map.push([m += 3, 0]);
        }

        for (let i = 0; i < size - 1; i++) {
            length_map.push([m - 1, 2], [m, 0]);
        }

        for (let i = 0; i < size - 1; i++) {
            length_map.push([m -= 3, 0]);
        }
    }

    var vertex_map = [];

    for (let t, i = 0; i < length_map.length; i++) {
        t = length_map[i][1];

        for (let j = 0; j < length_map[i][0]; j++) {
            vertex_map.push(t++ % 3);
        }
    }

    for (let v, z = 0, b, a, g, i = 0; i < vertex_map.length; i++) {
        v = vertex_map[i];

        g = p => {
            for (let t, j = 0; j < reference_array.length; j++) {
                if (p < (t = reference_array[j].filter(r => r + 1)).length) {
                    b = j;
                    a = reference_array[j].indexOf(t[p]);

                    break;
                } else {
                    p -= t.length;
                }
            }
        }

        if (v == 0) {
            vertex_map[i] = [0, 1, 2].map(d => [reference[z], d]);
            z++;
        } else if (v == 2) {
            g(z);

            vertex_map[i] = [[reference[z], 0], [reference_array[b - 1][a - 1], 2], [reference_array[b + 1][a - 1], 1]];
        } else {
            g(z - 1);

            vertex_map[i] = [
                [reference[z - 1], 1],
                [reference[z - 1], 2],
                [reference_array[b - 1][a + 1], 0],
                [reference_array[b - 1][a + 1], 2],
                [reference_array[b + 1][a + 1], 0],
                [reference_array[b + 1][a + 1], 1]
            ];
        }
    }

    for (let r, s, t, c, i = 0; i < configs.length; i++) {
        c = configs[i];

        r = -2;
        s = _ => (i.toString(3).padStart(2 * (6 * (size - 1) || 1), 0).substr(r += 2, 2)).split("").map(n => +n).concat(-1);

        for (let j = 0; j < size; j++) {
            c[j] = s();
        }

        t = size - 1;

        for (let j = 1; j < size; j++) {
            c[++t] = s();
            c[t += j + size - 1] = s();
        }

        for (let j = size - 2; j >= 1; j--) {
            c[++t] = s();
            c[t += j + size - 1] = s();
        }

        if (size > 1) {
            for (let j = 0; j < size; j++) {
                c[++t] = s();
            }
        }
    }

    // Validate each

    for (let c, i = 0; i < configs.length; i++) {
        c = configs[i];

        (_ => {
            while (c.find(h => h[0] == -1 || h[1] == -1 || h[2] == -1)) {
                for (let t, r, s, j = 0; j < vertexes.length; j++) {
                    t = vertex_map[j];

                    if (t.filter(v => !(c[v[0]][v[1]] + 1)).length == 1) {
                        if ((s = vertexes[j] - t.reduce((a, v) => a + (c[v[0]][v[1]] + 1 || 1) - 1, 0)) < 0 || s > 2) {
                            return;
                        }

                        r = t.find(v => !(c[v[0]][v[1]] + 1));

                        c[r[0]][r[1]] = s;
                    }
                }
            }

            for (let j = 0; j < vertexes.length; j++) {
                if (vertex_map[j].reduce((a, v) => a + (c[v[0]][v[1]] + 1 || 1) - 1, 0) != vertexes[j])
                    return;
            }

            solutions.push(c);
        })();
    }

    if (solutions.length > 1)
        return "N";

    // Convert to output list format

    var solution = solutions[0];

    var result = [];

    for (let p = 0, a, i = 0; i < 2 * size - 1; i++) {
        a = 2 * size - 1 - Math.abs(size - i - 1);

        for (let j = 0; j < a; j++) {
            result.push(solution[p + j][0]);
        }

        for (let j = 0; j < a; j++) {
            result.push(solution[p][1], solution[p++][2]);
        }
    }

    return result;
};

```

This challenge would actually be really fun as : I think there are a lot of byte-expensive shortcuts that could really speed this up that I didn't have time to explore.

Thank you for a fun challenge.

---
Tags: code-golf, game
---


title: Will all the dominoes fall?

text:
# Question
Title: Will all the dominoes fall?
The purpose of this challenge is to figure out whether all the dominoes will fall, given an input string representing a top view of the table.

## Input format

The program can take the input as a single string with newlines or a list of strings. Spaces denote, well, empty spaces, and the rest represent dominoes.

The start domino and the direction the dominoes start to fall will be denoted by one of `<`(left),`>` (right), `^` (up), `v`(down). There will be exactly one start domino in the input.

The other dominoes will be represented by one of the following four characters:

* `|` \- falls right when pushed from the left, falls left when pushed from the right
* `-` \- falls up when pushed from the bottom, falls down when pushed from above
* `/` \- falls right when pushed from the top and vice versa, falls left when pushed from the bottom and vice versa
* `\` \- falls left when pushed from the top and vice versa, falls right when pushed from the bottom and vice versa.

Basically, `|` and `-` keep the momentum going in the same direction, and the slashes (`/` and `\`) cause quarter-turns.

Dominoes may not fall twice. If a domino falls, you may consider that an empty space in the next iteration.

Pushing `-` from the left or right and pushing `|` from the top or bottom are undefined behavior.

## Output

A truthy/consistent value if all the dominoes will fall, and a consistent falsy value otherwise

Here's an example to make it a bit more clear (`o` represents a fallen domino for the sake of this example):

```
Step 1 - Starts at the 4th domino in the first row
\||<
-
-  -
\||\

Step 2 - start domino has fallen
\||o
-
-  -
\||\

Step 3 - Go left because start was '<'
\|oo
-
-  -
\||\

Step 4 - keep going left
\ooo
-
-  -
\||\

Step 5 - keep going left
\ooo
-
-  -
\||\

Step 6 - keep going to left, will go down next
oooo
-
-  -
\||\

Step 7 - change direction, go down because of '\'
oooo
o
-  -
\||\

Step 8 - keep going down
oooo
o
o  -
\||\

Step 9 - go down, will go left next because of '\'
oooo
o
o  -
o||\

Oops! Can't go any further, so output should be a falsy value

```

## Rules

Just to clarify, there's no gravity or anything. The direction depends on the position of the domino (`/`, `\`, `|`, or `-`)

This is , so shortest code in bytes wins.

## More test cases:

### Truthy

```
>
_________________________________________________________

\|||<
-
-
/|||
__________________________________________________________

     \|/
     /|/
       -
       -
    \||\
    ^

```

### Falsy

```
\|/
- -
/|/|  <-This last '|' doesn't fall, because the '/' before it has already fallen once
  ^
__________________________________________________________

|< |  <- This last '|' doesn't fall, because the dominoes don't wrap around.
__________________________________________________________

>||\||   Because after the '\', it tries to go up

```

Undefined behavior:

<pre><code>>-       Can't push '-' from the left
```
</code></pre>

# Answer
# Charcoal, ~~86~~ 69 bytes

```
ＷＳ⊞υι≔⪫υ¶θ≔v>^<ηＰθ…θ⌈Ｅη⌕θιＷ№ηＫＫ«↶⊗⁺³⌕ηＫＫ≔ⅈι ≔§⪪\-//|\³⁻ⅈιη»≔⌈ＫＡθ⎚→‹θ!

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` if all the dominoes fall, nothing if some remain. Explanation:

```
ＷＳ⊞υι≔⪫υ¶θ

```

Input the table as an array of strings and join them together.

```
≔v>^<η

```

Make a string of rotations for the starting domino characters. The string starts with the character for a clockwise rotation, then the one for no rotation, then an anticlockwise rotation, then a u-turn.

```
Ｐθ…θ⌈Ｅη⌕θι

```

Print the table and then up until the (last) occurrence of one the starting domino characters.

```
Ｗ№ηＫＫ«

```

While the current character is present in the table of rotations...

```
↶⊗⁺³⌕ηＫＫ

```

... pivot according to the position of the character in the table of rotations (annoyingly I have to spend an extra byte adding 3 instead of subtracting 1 because Charcoal can't pivot by negative amounts)...

```
≔ⅈι ≔§⪪\-//|\³⁻ⅈιη

```

... and, temporarily saving the current X-coordinate, erase the current character, moving in the current direction, then choose the list of valid characters (again listed in the order rotate clockwise, don't rotate, rotate anticlockwise) depending on whether the current direction is vertical or horizontal (detected via the change in X-coordinate, since Charcoal has no builtin to read the current direction).

```
»≔⌈ＫＡθ⎚→‹θ!

```

Check that only spaces are left.
> 7 votes

# Answer
# Java 10, ~~312~~ ~~304~~ ~~298~~ 295 bytes

```
m->{int i=m.length,j,x=0,y=0,d=0,t;for(;i-->0;)for(j=m[i].length;j-->0;d=t<0?d:t+(m[y=i][x=j]=0))t="<>^v".indexOf(m[i][j]);try{for(;;t=m[y+=d/2*t][x+=d<2?t:0],m[y][x]=0,d=t>99?d<2?d:d/0:t>91?(d+3)%6-d%3*2:t>46?d+2&3:t>44&d>1?d:d/0)t=d%2*2-1;}finally{for(var r:m)for(var c:r)i+=c/33;return i<0;}}

```

-9 bytes thanks to *@ceilingcat*.

Input as a character matrix.

Try it online.

**Explanation:**

```
m->{                        // Method with char-matrix input & boolean return
  int i=m.length,           //  Index-integer `i`, starting at the amount of rows
      j,                    //  Index-integer `j`, uninitialized
      x=0,y=0,              //  Current `x,y`-coordinates, starting at 0,0
      d=0,                  //  Current direction, starting at 0
      t;                    //  Temp-integer
  for(;i-->0;)              //  Loop `i` over all rows:
    for(j=m[i].length;j-->0 //   Inner loop `j` over each cell:
        ;                   //     After every iteration:
         d=                 //      Set `d` to:
           t<0?             //       If index `t` is -1 (thus NOT our start position):
            d               //        Leave `d` as is
           :                //       Else (we've found out start position):
            t               //        Set `d` to `t`
             +(m[y=i]       //        Set `y` to `i`
                [x=j]       //        Set `x` to `j`
                     =0))   //        Empty this cell containing the starting character
      t="<>^v".indexOf(m[i][j])
                            //    Set `t` to the index of the current character in
                            //    "<>^v", or -1 if it's a different character
  try{for(;                 //  Loop indefinitely:
           ;                //    After every iteration:
            t=m[y+=d/2*t]   //     Adjust the `y`-coordinate based on the direction
               [x+=d<2?t:0],//     Do the same for the `x`-coordinate
                            //     And set `t` to the character of this new cell
            m[y][x]=0,      //     Then empty this cell
            d=              //     And change the direction to:
              t>99?         //      If the current character is '|':
                   d<2?     //       If the direction is left/right:
                       d    //        Leave the direction as is
                      :     //       Else (it's up/down instead)
                       d/0  //        Throw a division-by-zero error
              :t>91?        //      Else-if the character is '\':
                    (d+3)%6-d%3*2
                            //       Change the direction: 0→3; 1→2; 2→1; 3→0
              :t>46?        //      Else-if the character is '/':
                     d+2&3  //       Change the direction: 0→2; 1→3; 2→0; 3→1
              :t>44         //      Else-if the character is '-':
                   &d>1?    //       And the direction is up/down:
                        d   //        Leave the direction as is
              :             //      Else (the character is '-', but the direction is
                            //      left/right, OR the character is ' ' or an emptied
                            //      cell):
               d/0)         //       Throw a division-by-zero error
        t=d%2*2-1;}         //   Set `t` depending on `d`: 0→-1; 1→1; 2→-1; 3→1
  finally{                  //  After an error has occurred (either a manual
                            //  division-by-zero, or ArrayIndexOutOfBoundsException):
    for(var r:m)            //   Loop over all rows of the matrix:
      for(var c:r)          //    Inner loop over all cells:
        i+=                 //     Increase `i` by:
           c/33;            //      The codepoint of the cell integer-divided by 33
    return i<0;}}           //   Return whether `i` is still -1
                            //   (`i` is -1 when we enter the finally, and will
                            //    remain that way if all cells are either a space or
                            //    emptied)

```
> 6 votes

# Answer
# Python 3, 323 bytes

```
def f(m,e=enumerate,z='^v<>'):
 for a,r in e(m):
  for b,i in e(r):
   if i in z:x,y=b,a;c,d=[(0,-1),(0,1),(-1,0),(1,0)][z.index(i)]
 while 1:
  try:
   m[y][x]=' '
   if all(i==' 'for i in sum(m,[])):return 1
   x+=c;y+=d;n=m[y][x];assert (n!=' ')&(x>=0)&(y>=0)
  except:return 0
  if n=='/':c,d=d,c
  if n=='\\':c,d=-d,-c

```

Try it online!

Version showing each step

Quite simply moves through the dominoes, recording the current coordinates and direction, and making sure we haven't gone of the board/stopped knocking over dominoes/removed all dominoes.

Less golfed version:

```
def main(chars):
    for this_y, row in enumerate(chars):
        for this_x, char in enumerate(row):
            if char in '^v<>':
                x, y = this_x, this_y
                dx, dy = [(0, -1), (0, 1), (-1, 0), (1, 0)]['^v<>'.index(char)]
    while True:
        try:
            chars[y][x] = ' '
            if all(i == ' ' for i in sum(chars, [])):
                return True
            x += dx
            y += dy
            char = chars[y][x]
        except IndexError:
            return False
        if char == ' ':
            return False
        if x < 0 or y < 0:
            return False
        elif char == '/':
            dx, dy = dy, dx
        elif char == '\\':
            dx, dy = -dy, -dx

```
> 4 votes

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


title: No. Of Factors Does the Number Have

text:
# Question
Title: No. Of Factors Does the Number Have
Create a function which takes in a input integer and then returns the number of factors it has, like if you pass `25` then it will return `3` since it has 3 factors i.e. `1,5,25`. **Challenge:** Make the fastest and the smallest code!

# Answer
> 3 votes
# Neim, 1 byte

```
     # Get Divisor count

```

Try it online!

Got to use Neim, yay.

---
Tags: code-golf, fastest-code, python, factoring
---


title: Delicate primes

text:
# Question
Title: Delicate primes
Inspired by Find the largest fragile prime.

By removing at least 1 digit from a positive integer, we can get a different non-negative integer. Note that this is different to the `Remove` function in the linked question. We say a prime number is delicate if all integers generated this way are not prime. For example, \\$60649\\$ generates the following integers:

```
0, 4, 6, 9, 49, 60, 64, 66, 69, 604, 606, 609, 649, 664, 669, 6049, 6064, 6069, 6649

```

None of these integers are prime, therefore \\$60649\\$ is a delicate prime. Note that any leading zeros are removed, and that the requirement is "not prime", so \\$0\\$ and \\$1\\$ both qualify, meaning that, for example, \\$11\\$ is a delicate prime.

Similar to the standard rule, you are to do one of the following tasks:

* Given a positive integer \\$n\\$, output two distinct, consistent* values depending on whether \\$n\\$ is a delicate prime or not
* Given a positive integer \\$n\\$, output the \\$n\\$th delicate prime
* Given a positive integer \\$n\\$, output the first \\$n\\$ delicate primes
* Output infinitely the list of delicate primes

*: You may choose to output two sets of values instead, where the values in the set correspond to your language’s definition of truthy and falsey. For example, a Python answer may output an empty list for falsey/truthy and a non-empty list otherwise.

You may choose which of the tasks you wish to do.

You can input and output in any standard way, and, as this is , shortest code in bytes wins

For reference, the first 20 delicate primes are:

```
2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949

```

A couple more to look out for:

```
821 - False (Removing the 8 and the 1 gives 2 which is prime)

```

---

I'll offer a +100 bounty for an answer which implements one of the standard I/Os rather than the method, that either:

* is shorter than a naive implementation (please include such a version as proof if one hasn't already been posted)
* or that doesn't rely on checking whether values are delicate primes or not when generating values (e.g. may use the fact that only specific digits can occur, or something else that isn't simply slapping a "loop over numbers, finding delicate primes")

This is kinda subjective as to what counts as "checking for delicate primes", so I'll use my best judgement when it comes to awarding the bounty.

# Answer
> 12 votes
# 05AB1E, 4 bytes

### Code

Uses the **05AB1E**-encoding. Checks whether the given number is a *delicate prime* or not.

```
æpJΘ

```

Try it online! or Check for all numbers between 1 and 9949.

## Explanation

```
æ      # Get the powerset of the number.
 p     # Check for each element whether it is a prime.
  J    # Join these numbers into one big number.
   Θ   # Check whether this joined number is equal to 1.

```

# Answer
> 9 votes
# APL (Dyalog Extended), ~~16~~ 14 bytes

```
</1⍭⍎⍕(⊢,,¨)\⍞

```

Try it online!

-2 bytes (`∊⍎¨¨ → ⍎⍕`) thanks to @ngn.

Full program that takes a single number from stdin and prints 1 (true) or 0 (false).

The trick here is how it generates all non-empty subsequences:

* `(⊢,,¨)/ str` gives all subsequences of `str` which include the last character.

```
  (⊢,,¨)/ '1234'
→ '1' (⊢,,¨) '2' (⊢,,¨) '3' (⊢,,¨) '4'
→ '1' (⊢,,¨) '2' (⊢,,¨) '4' '34'
→ '1' (⊢,,¨) '4' '34' '24' '234'
→ '4' '34' '24' '234' '14' '134' '124' '1234'

```
* `(⊢,,¨)\ str` applies `(⊢,,¨)/` to each prefix of `str`, giving all non-empty subsequences as a list of lists of strings.

```
  (⊢,,¨)\ '1234'
→ '1' ('2' '12') ('3' '23' '13' '123') ('4' '34' '24' '234' '14' '134' '124' '1234')

```

Explanation of whole code:

```
</1⍭⍎⍕(⊢,,¨)\⍞
             ⍞  ⍝ Take n from stdin as a string
      (    )\   ⍝ For each prefix, reduce from right by
         ,¨     ⍝   prepend the previous char to each string
       ⊢,       ⍝   and append to the previous list of strings
    ⍎⍕          ⍝ Convert nested strings to a single string,
                ⍝ and then eval it to get a simple integer vector
  1⍭  ⍝ Test each number for primality
</    ⍝ Test if the only truth is the last one

```

# Answer
> 7 votes
# Brachylog, 7 6 bytes

```
ṗ⊇ᵘṗˢȮ

```

Try it online!

```
ṗ⊇ᵘṗˢȮ the implicit input
ṗ      is a prime
 ⊇ᵘ    and from every unique subset
   ṗˢ  select the primes
     Ȯ and this should be a list with one element (the prime input itself)

```

# Answer
> 7 votes
# Jelly, 7 bytes

```
DŒPḌẒḄ’

```

A monadic Link accepting a positive integer which returns zero (falsey) if it's a delicate prime, or a non-zero integer (truthy) if not.

**Try it online!** Or see the first twenty.

### How?

```
DŒPḌẒḄ’ - Link: n         e.g. 824                      409
D       - decimal digits       [8,2,4]                  [4,0,9]
 ŒP     - power-set            [[],[8]...,[8,2,4]]      [[],[4],...,[4,0,9]]
   Ḍ    - undecimal            [0,8,2,4,82,84,24,824]   [0,4,0,9,40,49,9,409]
    Ẓ   - is prime?            [0,0,1,0,0,0,0,0]        [0,0,0,0,0,0,0,1]
     Ḅ  - from binary          32                       1
      ’ - decrement            31                       0

```

# Answer
> 5 votes
# Japt, 7 bytes

```
¥à f_°j

```

Try it or test `[0,1000)`

```
¥à f_°j     :Implicit input of integer string
¥           :Is equal to
 à          :Combinations
   f        :Filter
    _       :By passing each through a function
     °      :Postfix increment, to cast to an integer
      j     :Is prime?

```

# Answer
> 4 votes
# Pyth, ~~14~~ 8 bytes

```
qjfP_sTy

```

Try it online!

## Explanation

```
qjfP_sTy
  f       # filter
       y  # all subsets of input
   P_sT   # with a primality test
 j        # join result of filter on newlines
q         # check if it equals input

```

# Answer
> 4 votes
# , 25 23 bytes

*-2 thanks to Jonah!*

Returns a list containing either 1 being truthy or 0 otherwise.

```
1</@p:(#~2#:@i.@^#)&.":

```

Try it online!

### How it works

```
1</@p:(#~2#:@i.@^#)&.":
                   &.": convert the number to a string
      (  2      ^#)      2 ^ length
          #:@i.@         enumerated and to base 2
       #~                select from the string based on the bit mask
                   &.": convert from strings to numbers
1   p:                  primes -> 1, non-primes -> 0
                         so in the delicate prime case, we have
                         (2^L) - 1 zeros and one 1 for the input itself
 </@                    reduce from left to right with less-than
                         (so last position is 1, everything else 0)

```

# Answer
> 3 votes
# Retina 0.8.2, 53 bytes

```
^
;
+%`;(.)
$1;$'¶$`;
.+
$*
%A`^.?$|^(..+)\1+$
^1+¶+$

```

Try it online! Link includes test cases. Explanation:

```
^
;
+%`;(.)
$1;$'¶$`;

```

Generate all subsequences of the input.

```
.+
$*

```

Convert then to unary.

```
%A`^.?$|^(..+)\1+$

```

Delete the ones that aren't prime, but don't delete the newlines. (A multiline replace also works, but is harder to format an explanation for.)

```
^1+¶+$

```

Check that the original input was prime but none of the proper subsequences were.

# Answer
> 3 votes
# Scala, ~~173~~ 170 bytes

```
n=>(s"$n".indices.toSet.subsets.filter{x=>1<x.size&x.size<s"$n".size}.map(_.toSeq.sorted.map(""+n).mkString.toInt).toSet+n).filter{x=>x>1&2.to(x/2).forall(x%_>0)}==Set(n)

```

Try it online!

# Answer
> 3 votes
# , ~~163~~ 154 bytes

```
function(x,n=nchar(x),s=sum)(a=apply(!expand.grid(rep(list(0:1),n)),1,function(v)(y=s((x%/%10^(n:1-1)%%10)[v]*10^(s(v):1-1)))&s(!y%%1:y)==2))[1]&!s(a[-1])

```

Try it online!

Checks for primes among the numbers formed by removing all combinations of digits from x. The first combination is removal of *no* digits: this must be TRUE, and all other prime tests must be FALSE.

Commented:

```
is_delicate_prime=
function(x,                     # x = number to test
 n=nchar(x),                    # n = number of digits of x
 s=sum)                         # s = alias to sum() function
(a=                             # a = matrix of all prime-tests:
 apply(                         #     apply the function v to each of...
  !expand.grid(rep(list(0:1),n)),   # all combinations of n of TRUE/FALSE...
  1,                            #     row-by-row...
  function(v)                   #     defining the output of v as:
   (y=s((x%/%10^(n:1-1)%%10)    #       the digits of x...
    [v]                         #       (considering only the elements chosen by v)...
       *10^(s(v):1-1)))         #       multiplied by 10^((v-1)..0)...
   &s(!y%%1:y)==2))             #       tested for primality AND non-zero
[1]                             # Finally, output TRUE if a[1] is TRUE...
   &!s(a[-1])                   # and the sum of all other elements of a are FALSE

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 54 bytes

```
Select[FromDigits/@Subsets@@RealDigits@#,PrimeQ]=={#}&

```

Try it online!

# Answer
> 2 votes
# Python 2, ~~139~~ \\$\cdots\\$ ~~145~~ 142 bytes

Added 36 bytes to fix a bug kindly pointed out by pxeger.
Saved 5 bytes thanks to pxeger!!!

```
lambda n,R=range:all((g<2or any(g%i<1for i in R(2,g)))-(`g`==n)for g in{int(''.join(n[j]for j in R(len(n))if i>>j&1))for i in R(1,2**len(n))})

```

Try it online!

Inputs an integer as a string and returns `True` if it's a delicate prime or `False` otherwise.

# Answer
> 2 votes
# JavaScript (ES6),  ~~98~~  95 bytes

Expects `n` as a string. Returns a Boolean value.

```
n=>[...n].reduce((a,x)=>[...a,...a.map(y=>(g=k=>y%--k?g(k):(p+=q=y>1&k<2,y))(y+=x))],[p=0])|q/p

```

Try it online!

### How?

We compute the powerset of the digits of `n` in such a way that the order is preserved and `n` itself is computed last. The result is true if the only prime among the resulting integers is the last one.

# Answer
> 2 votes
# Python 3.8 (pre-release), ~~146~~ 144 bytes

*-2 bytes by removing redundant parentheses*

I was also working on a very similar answer just before Noodle9 posted theirs, and I combined ideas from that to get this (upvote it!). That one is now quite different because they initially had a broken one, so I thought I'd post mine.

```
lambda s,R=range:(l:=len(s))*all((g!=int(s))^(g>1)&all(g%k for k in R(2,g))for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l)})

```

Try it online!

Explanation:

```
lambda s,R=range:(l:=len(s))*all((g!=int(s))^(g>1)&all(g%k for k in R(2,g))for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l)})

lambda s        :                                                                                function
        ,R=range                                                                                alias `range` built-in to `R`
                                                                                {            s[j]for j in R(l)if i>>j&1  for i in R(1,2**l)}         compute the power-set (excluding the empty set)
                                                                                int(''.join(                          ))                            convert each list of digits to an integer
                             all(                                          for g in                                                            )        check the integers for primality
                                                    all(g%k for k in R(2,g))                                                                            check for factors in the number
                                              (g>1)&                                                                                makes sure 0 and 1 aren't treated as prime
                                 (g!=int(s))^                                                                                ensure the number itself is prime
                 (l:=len(s))*                                                                                store the length in `l`

```

# Answer
> 1 votes
# SageMath, 139 bytes

```
def f(n):s=str(n);l=len(s);return p(n)*all(~-p(g)for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l-1)})
R=range;p=is_prime

```

Try it online!

Port of my Python answer.

# Answer
> 1 votes
# Python 3,  181 bytes

**Using itertools and a golfed recipe for `powerset`.**

```
lambda s,R=range:all(p(int(''.join(t)),R)for t in sum(([*combinations(s,k)]for k in R(1,len(s))),[]))>p(int(s),R)
from itertools import*
p=lambda n,R:any(n%i<1for i in R(2,n))or 2>n

```

Try it online!

Expects input as a string.

The function `p` returns `True` if its input is not prime, and `False` if it is prime; the main function returns `(forall t, p(t)) > p(s)` where `t` takes all the "subvalues" of `s`. The only way for booleans to satisfy this inequality is `True > False`, which means all `t` are nonprimes and `s` is not nonprime.

*Disclaimer: There were already two python answers when I posted this one.*

---
Tags: code-golf, math, sequence, decision-problem, primes
---