title: Euler characteristic of a binary matrix

text:
# Question
Title: Euler characteristic of a binary matrix
A binary matrix represents a shape in the plane. `1` means a unit square at that position. `0` means nothing. The background is `0`.

For example, the matrix `[[0,1,0],[0,0,1],[1,1,1]]` represents the following shape:

```
     o----o
     |////|
     |////|
     o----o----o
          |////|
          |////|
o----o----o----o
|////|////|////|
|////|////|////|
o----o----o----o

```

There are several equivalent ways to define the Euler characteristic.

One way is finding all the vertices and edges of these squares, and defining the Euler characteristic to be \\$\chi=V-E+F\\$, where \\$V\\$ is the number of vertices, \\$E\\$ is the number of edges, and \\$F\\$ is the number of tiles.

For example, the above shape has \\$13\\$ vertices, \\$17\\$ edges, and \\$5\\$ tiles. So its Euler characteristic is \\$13-17+5=1\\$.

An equivalent definition is the total number of connected regions in the shape, minus the number of holes that occur inside those regions. Regions that connected diagonally are considered connected, while holes that are connected diagonally are considered disconnected.

For example, the above shape has \\$1\\$ connected region, and \\$0\\$ hole. So its Euler characteristic is \\$1-0=1\\$.

Note that there is an alternative but non-equivalent definition of the Euler characteristic, where regions that connected diagonally are considered disconnected, while holes that are connected diagonally are considered connected. The Euler characteristic of the above shape would be \\$2\\$ using that definition.

## Task

Given a binary matrix, find its Euler characteristic.

You can use any two consistent values instead of `0` and `1` for the binary matrix.

This is , so the shortest code in bytes wins.

## Testcases

```
[[1]] -> 1
[[1,0,1]] -> 2
[[1,0],[0,1]] -> 1
[[0,1,0],[0,0,1],[1,1,1]] -> 1
[[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]] -> -1
[[0,0,1,1,0],[0,1,1,1,1],[1,1,0,1,1],[0,1,1,0,0]] -> 0
[[1,1,1,0,1,1,1],[1,0,1,0,1,0,1],[1,1,1,0,1,1,1]] -> 0
[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] -> 1

```

# Answer
# Charcoal, 36 bytes

```
ＦＡ«Ｆι«ＦκＵＯ³@#¶#@→→»⸿⸿»≔⁻№ＫＡ@№ＫＡ#θ⎚Ｉθ

```

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

```
ＦＡ«Ｆι«ＦκＵＯ³@#¶#@→→»⸿⸿»

```

Draw the shape represented by the matrix, except using a `3×3` square with `@`s at the vertices and faces and `#`s at the edges.

```
≔⁻№ＫＡ@№ＫＡ#θ

```

Subtract the final number of edges from the number of vertices and faces.

```
⎚Ｉθ

```

Clear the canvas and output the result.

Example: The last test case `[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]` results in the following drawing:

```
@#@#@#@#@#@
#@#@#@#@#@#
@#@#@#@#@#@
#@#     #@#
@#@ @#@ @#@
#@# #@# #@#
@#@ @#@ @#@
#@#     #@#
@#@#@#@#@#@
#@#@#@#@#@#
@#@#@#@#@#@

```

This has 53 `@`s and 52 `#`s so its characteristic is `1`.
> 10 votes

# Answer
# Python NumPy, 79 bytes

```
lambda A:sum(g(g(pad(A,1)).T))
g=lambda A:r_[-A,A|roll(A,1)]
from numpy import*
```

Attempt This Online!

## Old Python NumPy, 85 bytes

```
lambda A:sum([A:=r_[A:=pad(A.T,1),-A[1:]|-A[:-1]]for i in"12"][1])
from numpy import*
```

Attempt This Online!

## How?

This is essentially a golfed version of the formula V-E+F given in OP. Our criterion to find edges (vertices) is that at least one of the 2 (4) adjacent squares is marked.

Little trick:

We make a sizeable saving by folding squares and vertical edges into one matrix. It turns out that the expression that computes and appends vertical edges from the squares alone can be reused verbatim to get and append horizontal edges and vertices in just one more step.
> 5 votes

# Answer
# , ~~74~~ ~~68~~ 67 bytes

*Edit: -1 byte thanks to pajonk*

```
function(m,`^`=cbind)sum(w<--t(m^0|0^m),-(t(m)^0|0^t(m)),w^0|0^w,m)

```

Try it online!

Gets vertical edges by adding a row of `0`s to the first or last column of the matrix `m`, and summing the non-zero elements when these two matrices are added together:
`sum(cbind(m,0)+cbind(0,m)>0)`, which is golfed (by substituting the `cbind` function) to `sum(m^0+0^m>0)`.

Repeats the same operation with the `t`ranspose of `m` to get horizontal edges:
`sum(cbind(t(m),0)+cbind(0,t(m))>0)`, golfed to `sum(t(m)^0+0^t(m)>0)`.

We then recycle the added-together vertical-edge matrix, transposed (saved inline as `w<-t(...)`), and repeat the operation again to get the vertices:
`sum(cbind(w,0)+cbind(0,w)>0)`, golfed to `sum(w^0+0^w>0)`.

Finally, the sum of `m` gives us the tiles, and we can wrap it all together using only a single call to `sum`.
> 3 votes

# Answer
# Octave with Image Package, 7 bytes

```
bweuler

```

Try it online!

A built-in.

---

# Octave, 49 bytes

```
@(m)sum(conv2(m,[1,2;4,8])(:)==[1,6,7])*[1;-1;-1]

```

Try it online!

Based on this blog article. The Euler characteristic is \\$M\_1-M\_2-M\_3\\$, where \\$M\_1\\$, \\$M\_2\\$, \\$M\_3\\$ are the numbers of \\$2\times2\\$ submatrices of the form \\$\bigl(\begin{smallmatrix}1&0\\0&0\end{smallmatrix}\bigr)\\$, \\$\bigl(\begin{smallmatrix}1&1\\1&0\end{smallmatrix}\bigr)\\$, \\$\bigl(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\bigr)\\$ respectively.

Thanks @Cris Luengo for pointing out that this is Gray's algorithm.
> 3 votes

# Answer
# Python with numpy, ~~79~~ 77 bytes

```
lambda m:sum(sign(diff(diff(pad(kron(m,eye(2)-.5),1)).T)))
from numpy import*
```

Attempt This Online!

This is based on my answer to "Expand a matrix goo-ily".

`kron` expands each 1 into `eye(2)-.5`, which is \\$ \begin{array}{|c|c|} \hline 0.5 & -0.5 \\ \hline -0.5 & 0.5 \\ \hline \end{array} \\$. After `pad` adds a border of zeroes, taking `diff` in both directions (with a transpose in between because that's shorter than specifying a different direction for `diff`; the rearrangement doesn't change anything in the end) is equivalent to a sum with multipliers \\$ \begin{array}{|c|c|} \hline 1 & -1 \\ \hline -1 & 1 \\ \hline \end{array} \\$ on each 2-by-2 square (overlapping). The nonzero terms (before summing) are positive at even positions (by sum of coordinates), which correspond to faces and vertices, and negative at odd positions, which correspond to edges. `sign` produces 1 or -1, correspondingly, for each part that is present, and `sum` gives the Euler characteristic.
> 2 votes

# Answer
# Python3, 606 bytes:

```
E=enumerate
def V(m,x,y):
 if x>=0 and y>=0:
  try:return m[x][y]
  except:return 0
def f(m):
 s,R=[],[0,0]
 while(O:=[(x,y)for x,b in E(m)for y,_ in E(b)if m[x][y]and(x,y)not in s]):
  q=[O[0]]
  while q:
   x,y=q.pop(0)
   M,D=[(0,1),(0,-1),(1,0),(-1,0)],[(-1,-1),(-1,1),(1,-1),(1,1)]
   if(x,y)in s:continue
   s+=[(x,y)]
   for u,v in M:
    R[1]+=(p:=(x+u,y+v))not in s
    if V(m,*p)and p not in s:q+=[p]
   for u,v in D:
    R[0]+=(p:=(x+u,y+v))not in s and all((x+u+j,y+v+k)not in s for j,k in[(0,[-1,1][v<1]),([-1,1][u<1],0)])
    if V(m,*p)and p not in s:q+=[p]
 return R[0]-R[1]+sum(map(sum,m))

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES7), 105 bytes

This is based on the simple yet brilliant method used by Neil. It's probably not the shortest approach in JS, though.

```
m=>[...7**8+'23'].map(n=>m.map((r,y)=>r.map((v,x)=>!v|m[k=[x*2+n%3,y*2+n/3|0]]?0:o-=m[k]=n&1||-1)),o=0)|o

```

Try it online!

### Commented

```
m =>                     // m[] = input binary matrix, reused as an object
                         //       to store the cells of the expanded matrix
[...7 ** 8 + '23']       // all digits from 0 to 8 (order doesn't matter):
                         // [ '5', '7', '6', '4', '8', '0', '1', '2', '3' ]
.map(n =>                // for each n in the above list:
  m.map((r, y) =>        //   for each row r[] at position y in m[]:
    r.map((v, x) =>      //     for each value v at position x in r[]:
      !v |               //       if v = 0
      m[                 //       or the cell at ...
        k = [            //       ... the key position k defined as ...
          x * 2 + n % 3, //         [ 2x + (n mod 3),
          y * 2 + n / 3  //           2y + floor(n / 3) ]
          | 0            //
        ]                //
      ] ?                //       ... is already set:
        0                //         do nothing
      :                  //       else:
        o -= m[k] =      //         set m[k] and update o:
          n & 1          //           -1 if n is odd (edges)
          || -1          //           +1 otherwise (vertices and faces)
    )                    //     end of map()
  ),                     //   end of map()
  o = 0                  //   start with o = 0
) | o                    // end of map(); return o

```
> 1 votes

---
Tags: code-golf, array, geometry, binary-matrix, topology
---


title: ASCII-Art n'th Root

text:
# Question
Title: ASCII-Art n'th Root
## Challenge:

Given two integers \\$a\\$ and \\$b\\$, with lengths \\$A=length(a), B=length(b)\\$, output an ASCII-art of the \\$a^{th}\\$ root of \\$b\\$, including the answer rounded to \\$A\\$ amount of decimal places.
The size of the ASCII-art root also depends on \\$A\\$ and \\$B\\$.

**Example:**

\\$a=123\\$, \\$b=1234\\$

```
     ____
123 /1234 = 1.060
\  /
 \/

```

Because \\$B=4\\$, we have four `_` above the `1234`. Because \\$A=3\\$, we have three `/` and \\$1.0595772951...\\$ is rounded to `1.060`.

*: This will not be equal to \\$A\\$, but \\$\left\lceil{\frac{A}{2}}\right\rceil+1\\$ instead.*

## Challenge rules:

* I/O format is flexible:
    + You're allowed to take the input loose or as a pair of integers; doubles; strings; list of digits; etc.
    + You're allowed to print the result directly to STDOUT; return it as a string; return it as a list/array/stream of string-lines; return it as a matrix of characters; etc.
* If input \\$a\\$ has an odd length \\$A\\$, the number is left-aligned in the output. So in the example above you're not allowed to have the second line as  `123/1234 = 1.060`! (It should be `123<space>/...` instead of `<space>123/...`)
* The `=` in the output should be surrounded by a single leading/trailing space
* Rounding can be done in any reasonable way (e.g. rounding towards 0, half-up, half-even, banker's rounding, etc.)
* If the rounded result ends with `0`s, you're allowed to omit them. (E.g., the `1.060` in the example above may also be `1.06`.)
* You can assume \\$a\>0\\$ and \\$b\geq0\\$ (\\$a\\$ is positive, \\$b\\$ is non-negative).
* Trailing spaces in the output, and a single trailing newline is fine. Multiple trailing newlines or trailing whitespaces are not.

## General rules:

* This is , so the shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (e.g. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
Inputs: a=3, b=100 (A=1, B=3)
   ___
3 /100 = 4.6
\/

Inputs: a=123, b=1234 (A=3, B=4)
     ____
123 /1234 = 1.060
\  /
 \/

Inputs: a=10, b=10 (A=2, B=2)
   __
10/10 = 1.26
\/

Inputs: a=1298123, b=9023847978341 (A=7, B=13)
         _____________
1298123 /9023847978341 = 1.0000230
\      /
 \    /
  \  /
   \/

Inputs: a=2500, b=0 (A=4, B=1)
     _
2500/0 = 0.0000
\  /
 \/

```

# Answer
> 9 votes
# Python, 143 bytes

```
def f(a,b):
 A=len(str(-a))&-2;print(A*" ",len(str(b))*"_"+f"\n{a:<{A}}/{b} = {b**(1/a):.{A}}");p="\\"
 while A:A-=2;print(p+A*" "+"/");p=" "+p
```

Attempt This Online!

# Answer
> 6 votes
# JavaScript (ES8),  ~~158~~  156 bytes

Expects `(a)(b)`, where both arguments are strings.

```
a=>b=>" "[R='repeat'](q=(A=a.length)+A%2)+` ${"_"[R](b.length)}
${a.padEnd(q)}/${b} = ${(b**=1/a).toFixed(A)}
`+(g=p=>q?p+" "[R](q-=2)+`/
`+g(" "+p):"")`\\`

```

Try it online!

# Answer
> 6 votes
# Lua, 205 203 188 bytes

```
a,b=...p,c,s=print,a.rep,a.len d=s(a)r=d%2+d+1 p(c(" ",r)..c("_",s(b)))p(a.format("%s%s/%s = %."..d.."f",a,c(" ",d%2),b,b^(1/a)))for i=1,r//2 do p(c(" ",i-1).."\\"..c(" ",r-i*2-1).."/")end

```

Attempt This Online! Explanation soon:tm: once I'm out of school. I added an explanation to the footer of the ATO link.

# Answer
> 6 votes
# Charcoal, 37 bytes

```
θ⸿↘⊘⊕Ｌθ↑↗⊘⁺³Ｌθ⟦⭆η_⟧η = ﹪⁺⁺%.ＬθfＸＩη∕¹Ｎ

```

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

```
θ

```

Output the first input.

```
⸿↘⊘⊕Ｌθ↑↗⊘⁺³Ｌθ⟦⭆η_⟧

```

Draw the square root sign.

```
η = ﹪⁺⁺%.ＬθfＸＩη∕¹Ｎ

```

Output the second input and the formatted result.

# Answer
> 5 votes
# Python 3.8 (pre-release), 161 bytes

```
lambda a,b:f"{' '*(Z:=(A:=len(str(a)))+1&-2)} {'_'*(B:=len(str(b)))}\n{a:<{Z}}/{b} = {b**a**-1:.{A}f}"+"".join(f"\n{' '*i}\\{' '*(Z+2*~i)}/"for i in range(Z//2))

```

Try it online!

# Answer
> 5 votes
# Julia 1.0, 137 bytes

```
!x=length("$x")
a\b=[" "^-~(X=!a+!a%2)*"_"^!b;"$a"*" "^(r=1:X÷2;!a%2)*"/$b = $(round(b^a^-1,digits=!a))";@. ' '^~-r*"\\"*" "^(X-2r)*'/']

```

Try it online!

# Answer
> 4 votes
# Python, 169 bytes

```
def f(a,b):print(" "*((A:=len(str(a)))-1+(x:=A%2)),"","_"*len(str(b))+f"\n{a}{x*' '}/{b} =",round(b**1/a,A),*("\n"+i*" "+"\\"+(A-i-i-2+x)*" "+"/"for i in range(A//2+x)))
```

Attempt This Online!

# Answer
> 4 votes
# C (gcc), ~~222~~ 218 bytes

*-4 bytes thanks to @ceilingcat*

```
#define P;printf(
#define X snprintf(0,0,"%.0f"
A;B;f(double a,double b){A=X,a)P"  %*c",A+A%2,95);for(B=X,b);--B P"_"))P"\n%.0f%*c%.0f = %.*f",a,1+A%2,47,b,A,pow(b,1/a));for(A-=~A&1;B++<A--P"\n%*c%*c",B,92,2+A-B,47));}

```

Try it online!

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


title: Storing a band matrix

text:
# Question
Title: Storing a band matrix
Related challenge

A band matrix is a matrix whose non-zero entries fall within a diagonal *band*, consisting of the main diagonal and zero or more diagonals on either side of it. (The main diagonal of a matrix \\$A\\$ consists of all entries \\$A\_{i,j}\\$ for which \\$i=j\\$.) For this challenge, we will only be considering square matrices.

For example, given this matrix:

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

```

this is the band:

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

```

The main diagonal (`1 4 0 9 3`) and the diagonals above it (`2 5 7 1`) and below it (`3 6 8 2`) are the only places non-zero elements are found; all other elements are zero. (Some of the elements in the band may also be zero.)

One nice feature of band matrices is that they can be stored more efficiently: only the elements in the band need to be stored. For example, our 5-by-5 matrix above can instead be stored as a 5-by-3 matrix, where each column represents one diagonal of the original matrix:

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

```

Note how the shorter diagonals are padded with zeros: diagonals below the main diagonal are padded at the beginning, while diagonals above the main diagonal are padded at the end.

In this challenge, the band to be stored must be symmetrical about the main diagonal. For example, this matrix:

```
2 3 4 0 0 0
1 2 3 4 0 0
0 1 2 3 4 0
0 0 1 2 3 4
0 0 0 1 2 3
0 0 0 0 1 2

```

has this band:

```
2 3 4
1 2 3 4
0 1 2 3 4
  0 1 2 3 4
    0 1 2 3
      0 1 2

```

and so it is stored as:

```
0 0 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 0
0 1 2 0 0

```

In this case, one of the diagonals to be stored consists entirely of `0`s, but that diagonal must be included because it is symmetric to the nonzero diagonal consisting of `4`s. (This rule means the output matrix will always have an odd number of columns.)

## Challenge

Given an \\$N\\$-by-\\$N\\$ band matrix containing nonnegative integers, output/return its rearranged version.

If \\$B\\$ is the number of diagonals in the band, the resulting matrix will be \\$N\\$ rows by \\$B\\$ columns. If you prefer, you may output the result matrix transposed (that is, a matrix of \\$B\\$ rows by \\$N\\$ columns).

You may assume that \\$B \< N\\$. In other words, no input that would generate output the same size or larger needs to be handled.

The matrix will always have at least one nonzero entry.

This is : the goal is to make your code (measured in bytes) as short as possible.

## Test cases

```
1 0
0 1
=>
1
1

1 0 0
0 2 0
0 0 3
=>
1
2
3

0  0  0
0  0  0
0  0 42
=>
 0
 0
42

1 2 0 0
3 4 5 0
0 6 0 7
0 0 8 9
=>
0 1 2
3 4 5
6 0 7
8 9 0

1 2 0 0 0
3 4 5 0 0
0 6 0 7 0
0 0 8 9 1
0 0 0 2 3
=>
0 1 2
3 4 5
6 0 7
8 9 1
2 3 0

0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
=>
0 0 1
0 0 0
0 0 0
0 0 0
0 0 0

2 3 4 0 0 0
1 2 3 4 0 0
0 1 2 3 4 0
0 0 1 2 3 4
0 0 0 1 2 3
0 0 0 0 1 2
=>
0 0 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 0
0 1 2 0 0

```

# Answer
> 7 votes
# , ~~94~~ ~~84~~ ~~83~~ 78 bytes

*Edit: -5 bytes thanks to Giuseppe*

```
function(m,b=max(abs(row(m)-col(m))*!!m))matrix(c(!1:b,m),dim(m)+1)[-b:b+b+1,]

```

Try it online!

(of which 38 bytes are shamefully copied from Giuseppe's method to calculate the bandwidth: upvote that!)

As noticed by @pajonk, there are 2 'rearranged versions' of any square 'band matrix', depending on how 'rows' and 'columns' are assigned: add +3 bytes (corresponding to `t`ransposing the input matrix) to flip this.

**How?**

For an `n`x`n` matrix, we first calculate the bandwidth `b` and prepend `b` zeros to the front of the matrix elements as a 1d-vector. We then split this up again into a matrix with `n+1` rows: this aligns the diagonals, placing the 'bands' in the first `2b+1` rows. The 'rearranged version' is now just the `2b+1`x`n` submatrix of this.

# Answer
> 4 votes
# , 66 53 bytes

```
#{.#|.-@$(#"1~0{](]#~[-:"2*"2)#\>/#\|@-/#\)@|.]{.~3*$

```

Try it online!

### Basic Strategy

We want to avoid special casing the "pad the partial top rows on the left", and "pad the partial bottom rows on the right". If we extend the input "offscreen" in both directions, a solution which automatically handles these cases falls out for free.

### Explanation

Consider:

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

```
* `]{.~3*$` Extend the input so its shape is 3 times its original shape:

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

```
* `-@$(...)@|.` And rotate it so the original is centered:

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

```
* `#\>/#\|@-/#\` Generate all possible bands:

```
1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1

1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1

1 1 1 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1

... etc

```
* `](]#~[-:"2*"2)` Filter only those that, when multiplied elementwise with the extended input, return the input unchanged:

```
1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1

1 1 1 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1

...etc

```
* `0{` Take the first:

```
1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1

```
* `#"1~` Use these masks to filter the extended input, row-wise:

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

```
* `#{.#|.` To extract only the middle portion that is our final answer, rotate left the length of the original input, and then take the length of the original input:

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

```

# Answer
> 3 votes
# Charcoal, 28 bytes

```
≔⌈Ｅθ⌈Ｅι∧λ↔⁻μκηＩＥθＥ⁺κ…·±ηη§ιλ

```

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

```
≔⌈Ｅθ⌈Ｅι∧λ↔⁻μκη

```

Calculate the width of the band.

```
ＩＥθＥ⁺κ…·±ηη§ιλ

```

Output the relevant cyclic diagonals.

# Answer
> 3 votes
# 05AB1E, ~~24~~ 20 bytes

```
ĀDƶsøƶøαàUεNX-._X·>£

```

-4 bytes thanks to *@Neil*.

Try it online or verify all test cases.

**Explanation:**

Step 1: Get the bandwidth of the input-matrix, using the same exact code as my answer in the related challenge:

```
Ā        # Transform each non-0 integer in the (implicit) input-matrix to a 1
 D       # Duplicate this matrix of 0s/1s
  ƶ      # Multiply each inner value by its 1-based row-index
 s       # Swap so the matrix of 0s/1s is at the top again
  øƶø    # Do the same for the columns
         # (where `ø` is a zip/transpose, to swap rows/columns)
     α   # Take the absolute difference of the values at the same positions
      à  # Pop and push the flattened maximum

```

Step 2: Leave the actual diagonal band matrix using the \\$bandwidth\times2+1\\$, and output it as result:

```
       U # Pop and store the bandwidth in variable `X`
ε        # Map over the rows of the (implicit) input-matrix
 NX-     #  Push N-X, where `N` is the 0-based map-index
    ._   #  Rotate the current row that many times towards the left,
         #  where negative values will rotate towards the right instead
 X·>     #  Push 2X+1, where `X` is still the bandwidth
    £    #  Leave that many leading items from the current rotated row
         # (after which the mapped matrix is output implicitly as result)

```

# Answer
> 3 votes
# Vyxal, ~~37~~ ~~26~~ ~~18~~ 17 bytes

```
vT:ẏεfG£¨2Ǔ¥ǔ¥d›Ẏ

```

Try it Online!

## How?

```
vT:ẏεfG£¨2Ǔ¥ǔ¥d›Ẏ
vT                  # For each row, get the indices of truthy elements
  :ẏ                # Duplicate and push a range in [0..length of list)
    ε               # Vectorizing absolute difference
     fG             # Get the flattened maximum difference
       £            # Store in the register
        ¨2          # Open dyadic map lambda on (implicit) input, pushing both item and index
          Ǔ         # Rotate row left by index
           ¥ǔ       # Rotate row right by the contents of the register
             ¥d›    # Push 2*register+1
                Ẏ   # Leave that many leading items in the current rotated row

```

*-10 bytes thanks to Neil, and another -9 from myself*

# Answer
> 1 votes
# JavaScript (ES6),  ~~118~~  116 bytes

```
f=(m,k,q=m.map(_=>0),M=m.map((r,y)=>q.concat(r,q[S='slice'](~y),0)[S](y+k,~k)))=>M.some(r=>r[0]|r[S](-1))?M:f(m,-~k)

```

Try it online!

### How?

Given a matrix \\$m\\$ of size \\$N\times N\\$, we build a vector \\$q\\$ of size \\$N\\$ filled with \\$0\\$'s:

```
q = m.map(_ => 0)

```

For each row \\$r\\$ at position \\$y\\$ (0-indexed) in \\$m\\$, we use \\$q\\$ to append \\$N\\$ leading \\$0\\$'s and \\$y+2\\$ trailing \\$0\\$'s:

```
q.concat(r, q.slice(~y), 0)

```

For instance:

```
[ 1 2 3 ] --> [ 0 0 0 1 2 3 0 0 ]
[ 4 5 6 ] --> [ 0 0 0 4 5 6 0 0 0 ]
[ 7 8 9 ] --> [ 0 0 0 7 8 9 0 0 0 0 ]

```

Starting with \\$k=0\\$, we then remove \\$y+k\\$ leading \\$0\\$'s and \\$k+1\\$ trailing \\$0\\$'s:

```
.slice(y + k, ~k)

```

Which gives a new matrix \\$M\_k\\$ of width \\$2(N-k)+1\\$:

```
[ 0 0 0 1 2 3 0 0 ]     --> [ 0 0 0 1 2 3 0 ]
[ 0 0 0 4 5 6 0 0 0 ]   --> [ 0 0 4 5 6 0 0 ]
[ 0 0 0 7 8 9 0 0 0 0 ] --> [ 0 7 8 9 0 0 0 ]

```

We increment \\$k\\$ and repeat the whole process on the original matrix until there's at least one non-zero value in either the first or the last column of \\$M\_k\\$:

```
M.some(r => r[0] | r.slice(-1))

```

NB: `r.slice(-1)` returns an atomic array which is coerced to an integer by the bitwise operator.

# Answer
> 1 votes
# PARI/GP, 89 bytes

```
m->a=0;matrix(#m,,i,j,m[i,j]&&a=max(a,abs(i-j)));matrix(#m,2*a+1,i,j,m[i,(i+j-a-2)%#m+1])
```

Attempt This Online!

# Answer
> 1 votes
# Python NumPy, 126 bytes

```
def f(*a):x=triu(tri(l:=len(a),2*l-1,l-1))[::-1];x[x>0]=r_[a];j=min(where(x+x[:,::-1])[1]);return x[:,j:-j]
from numpy import*
```

Attempt This Online!

Rather opportunistically takes the splatted array (this saves three bytes) as input.

#### How?

Uses the properties of masked assignment to map *all* diagonals by the deceptively short statement `x[x>0]=r_[a]`. The actual work is in setting up the initial mask `x`. And in trimming excess columns afterwards.

# Answer
> 0 votes
# Python, ~~203~~ 193 bytes

*-10 bytes thanks to @Steffan*

```
def f(m):R=range;n=len(m);r=R(n);d=[*map(any,c:=[[m[i][i+d]if i+d in r else 0for i in r]for d in R(-n,n+1)])];k=min(d.index(1),d[::-1].index(1));return[[c[i][j]for i in R(k,n+n-k+1)]for j in r]
```

Attempt This Online!

# Answer
> 0 votes
# APL+WIN, 64 bytes

Prompts for input matrix. Index origin = 0

```
b←⌈/⌈/¨+/¨^\¨b(⌽b←×0 1↓a←(⍳n←¯1↑r←↑⍴m)⌽m←⎕)⋄((r,-b)↑a),(r,1+b)↑a

```

Try it online! Thanks to Dyalog Classic

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


title: Draw the EU Estimated Sign

text:
# Question
Title: Draw the EU Estimated Sign
The specification of the "estimated" sign used by the European Union Directive (U+212e in Unicode, which you may not simply print for this challenge) is quite precise.

To copy some restrictions from this question: Render the symbol to file or screen using vector or raster graphics. If your output is rasterised, your image must have dimensions of 264 pixels × 240 pixels or more. Any other helping lines or length indicators must not be drawn.

# Answer
> 15 votes
# VBA, ~~587~~ 560 bytes

```
Sub S(a,b,c,d,e,f)
Set v=ActiveSheet.Shapes.AddShape(a,b,c,d,e)
v.Fill.ForeColor.RGB=f
v.Line.Visible=0
If a=5 Then v.Adjustments(1)=.5
End Sub
Sub U():p=91.5:w=-1
S 1,0,0,500,450,w
S 9,0,0,500,450,0
S 9,38.5,13.5,423,423,w
S 1,36,120,29,210,0
S 1,65,80,26.5,290,0
S 1,435,120,29,105,0
S 1,408.5,80,26.5,145,0
q=212.25:S 1,9,q,480,19,0
S 5,p,205.75,317,13,w
S 1,405,231.25,95,131.5,w
r=14.5:S 1,p,70.5,r,30,0
q=85:S 9,p,59.6,q,q,w
S 1,p,349.5,r,30,0
S 9,p,305.4,q,q,w
S 1,395,70.5,r,30,0
S 9,323.5,59.6,q,q,w
q=231.25:S 1,p,q,6.5,6.5,0
S 9,p,q,13,13,w
End Sub

```

Invoke macro U. Basically a lot of shape drawing. Shape 1 is a rectangle, 5 a rounded rectangle and 9 is an oval. Output is 500 wide by 450 high.

**Edit**: added the rounded rectangle (with adjustment to turn the ends into semicircles) to produce the radiused corners on top of the bar with one shape draw.

# Answer
> 3 votes
# Haml + Sass, 20 + 722 = 742 bytes

I'm sure this could be golfed a lot more, but I'm happy enough with it. Demo on CodePen.

Note: Because of default margins, this needs a browser window at least 1,000-some pixels wide.

## Haml

```
#u
#v
 #w
 #x
 #y
#z

```

## Sass

```
$w: 1000px
$h: 900px
$a: 183px
$b: 25px
$p: 85px
$q: 13px
$d: 846px
$e: $w - 2*$a
$f: 143px
$s: 50%
$t: $p/5.5
=d($w:$w,$h:$h)
 width: $w
 height: $h
=m($c)
 background-color: $c
=k
 +m(#000)
 position: absolute
 content: ''
=l
 +k
 +m(#fff)
=o($o:$p)
 +d($o,$p)
=r($a)
 border-radius: $a
*
 +k
html,body
 +l
 position: relative
#u
 +d
 clip-path: ellipse($s $s)
#v
 +d($e)
 left: $a
 clip-path: circle(($d/2) at $s $s)
#v::before,#v::after
 +l
 +d($e,($h -$b)/2)
 +r($q)
#v::after
 bottom: 0
#w,#x
 +o($t)
 top: $f
#w::before,#x::before,#y::before
 +l
 +o
 +r($s 0)
#x,#x::before
 right: 0
#x::before
 +r(0 $s 0 0)
#y
 +o($t)
 bottom: $f
 z-index: 9
#y::before
 +r(0 0 0 $s)
#z
 +l
 +d($s,267px)
 top: ($h+$b)/2
 right: 0

```

# Answer
> 3 votes
# GLSL + shadertoy.com, ~~349~~ ~~345~~ 344 bytes

```
#define F float
void mainImage(out vec4 R,vec2 C){F S=min(iResolution.x,iResolution.y/0.9);vec2 p=C/vec2(0.5,0.45)/S-1.;F A=0.94-length(p*vec2(1.22,1));F H=min(min(-p.y-0.025,p.y+0.551),p.x);F B=max(length(p)-1.,min(abs(p.y)-0.025,max(A,H)));F D=max(min(p.x,-p.y),max(-A,0.634-abs(p.x)));R=vec4(vec3(max(H,min(B*D*64.-0.01,min(B,D)))*S/3.),1);}

```

Can be tested by pasting the code on this page: https://www.shadertoy.com/new

Output (when the screen size is 1440\*900):

# Answer
> 1 votes
## PostScript, ~~280~~ 140 bytes

Now smaller, with binary tokens and less precision!

```
00000000: 5b28 5b29 7b31 3339 9205 8881 3588 0035  [([){139....5..5
00000010: 2035 9207 887f 3588 7f88 2835 9207 9242   5....5...(5...B
00000020: 747d 285d 297b 885d 3938 8822 3088 2d92  t}(]){.]98."0.-.
00000030: 0588 0c30 9285 9242 7d2f 747b 3188 ff92  ...0...B}/t{1...
00000040: 8b7d 3e3e 920d 8864 3930 92ad 387b 307d  .}>>...d90..8{0}
00000050: 9283 880a 3992 8b88 0a30 8768 0192 0592  ....9....0.h....
00000060: 422e 3035 202e 3035 3592 8b31 9296 87a9  B.05 .055..1....
00000070: 0034 315b 3587 4001 8869 9280 87a9 0034  .41[5.@..i.....4
00000080: 5b92 965d 88ff 3192 8b5d 745d            [..]..1..]t]

```

Before being tokenized (255 bytes):

```
[([){139 arc -127 5 0 5 5 arct 127 5 127 40 5 arct fill t}(]){93 98 34 0 45 arc 12 0 rlineto fill}/t{1 -1 scale}>>begin
100 90 translate
8{0}repeat
10 9 scale
10 0 360 arc fill
.05 .055 scale
1 setgray
169 41[5 320 105 rectfill
169 4[setgray]-1 1 scale]t]

```

Step-by-step:

Final output:

(Gray background is from Preview.app and not part of actual output.)

# Answer
> 0 votes
# C (gcc), ~~251~~ 248 bytes

*-3 bytes thanks to @ceilingcat*

```
#define q(x,y)(x)*(x)+(y)*(y)
#define A abs
main(i,j){puts("P5 264 240 1");for(i=-121;i++<119;)for(j=-133;j++<131;)putchar(((q(i,j*.9)>'8?'|q(i,j)<12471&A(j)<84)&q(A(i)-72,A(j)-81)>39|q(A(i)-65,A(j)-61)<504)&A(i)>3&(A(j)-83||A(i)-4)|j>0&i>3&i<73);}

```

Try it online!

---
Tags: code-golf, graphical-output
---


title: Bandwidth of a matrix

text:
# Question
Title: Bandwidth of a matrix
A band matrix is a matrix whose non-zero entries fall within a diagonal *band*, consisting of the main diagonal and zero or more diagonals on either side of it. (The main diagonal of a matrix consists of all entries \\$a\_{i,j}\\$ for which \\$i=j\\$.) For this challenge, we will only be considering square matrices.

For example, given this matrix:

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

```

this is the band:

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

```

The main diagonal (`1 4 0 9`) and the diagonals above it (`2 5 7`) and below it (`3 6 8`) are the only places non-zero elements are found; all other elements are zero. (Some of the elements in the band may also be zero.)

The *bandwidth* of the matrix is the smallest number \\$k\\$ such that all non-zero elements are contained within a band consisting of the main diagonal, \\$k\\$ diagonals above it, and \\$k\\$ diagonals below it. The bandwidth of the above matrix is 1: all non-zero elements fall within the main diagonal, the one diagonal above it, or the one diagonal below it. For another example:

```
1 1 0 0
1 1 1 0
1 1 1 1
0 1 1 1

```

The bandwidth of this matrix is 2, because it takes two diagonals above and below the main diagonal to catch all non-zero elements:

```
1 1 0
1 1 1 0
1 1 1 1
  1 1 1

```

Note that for the purposes of this challenge, the band must extend the same distance on either side of the main diagonal, which is why the diagonal `0 0` is included above.

Mathematically, the bandwidth is the smallest number \\$k\\$ such that for every entry \\$a\_{i,j}\\$ in the matrix, \\$a\_{i,j} = 0\\$ if \\$|i-j|\>k\\$.

## Challenge

Given a square matrix containing nonnegative integers, output its bandwidth.

The matrix will always have at least one nonzero entry.

This is : make your code (measured in bytes) as short as possible.

## Test cases

```
1
=>
0

1 0 0
0 1 0
0 0 1
=>
0

1 2 0 0
3 4 5 0
0 6 0 7
0 0 8 9
=>
1

1 1 0 0
1 1 1 0
1 1 1 1
0 1 1 1
=>
2

16 18  8
 6 14 22
20 10 12
=>
2

0 0 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
=>
3

```

# Answer
> 8 votes
# Jelly, 5 bytes

```
ŒṪIAṀ

```

Try it online!

```
ŒṪ     -- indices of non-zero values
  I    -- reduce each index by subtraction
   A   -- get the absolute values
    Ṁ  -- select the maximum

```

# Answer
> 7 votes
# , ~~41~~ 40 bytes

-1 byte thanks to Giuseppe

```
function(A)max(diff(t(which(t(A)|A,T))))

```

Try it online!

Note that the matrix \\$A|A^T\\$ has the same bandwidth as the matrix \\$A\\$, but is symmetrical. We can therefore consider only its lower-triangular part, for which row index is greater than column index.

The formula given in the question is \\$\max(|i-j|)\\$ such that \\$A\_{ij}\neq 0\\$; this is equivalent to \\$\max(i-j)\\$ such that \\$(A|A^T)\_{ij}\neq 0\\$ (without the absolute value). The call `which(x,T)` returns a 2-column matrix listing the row and column indices of all `TRUE` values in `x`; we need to transpose the output since `diff` acts column-wise.

This saves 3 bytes compared to the more obvious strategy:

```
function(A)max(abs(which(!!A,T)%*%c(1,-1)))

```

Edit: Outgolfed by Giuseppe's 38 byte answer.

# Answer
> 7 votes
# , 38 bytes

```
function(A)max(abs(row(A)-col(A))*!!A)

```

Try it online!

Test harness taken from Robin Ryder's answer.

R has some weird built-ins. Given a matrix `M`, `row` will return a matrix of the same size with each entry equal to its row number, and `col` likewise, but with columns. That is, \\$row(M)\_{ij}=i\\$ and \\$col(M)\_{ij}=j\\$. So `abs(row(A)-col(A))` gives us a matrix of possible bandwidths like so for a \\$5\times 5\\$ matrix:

```
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    2    3    4
[2,]    1    0    1    2    3
[3,]    2    1    0    1    2
[4,]    3    2    1    0    1
[5,]    4    3    2    1    0

```

Then we "filter" the entries where `A` is nonzero and take the maximum to obtain the bandwidth.

# Answer
> 4 votes
# Python 3, 68 bytes

```
lambda a,e=enumerate:max(abs(i-j)for i,r in e(a)for j,c in e(r)if c)

```

Try it online!

Finds the largest \\$|i-j|\\$ among all entries \\$a\_{ij} \neq 0\\$.

# Answer
> 4 votes
# Charcoal, 13 bytes

```
Ｉ⌈ＥＡ⌈Ｅι∧λ↔⁻μκ

```

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

```
   Ａ            Input array
  Ｅ             Map over rows
      ι         Current row
     Ｅ          Map over elements
        λ       Current element
       ∧        Logical And
           μ    Column index
          ⁻     Subtract
            κ   Row index
         ↔      Absolute value
    ⌈           Take the maximum
 ⌈              Take the maximum
Ｉ               Cast to string
                Implicitly print

```

# Answer
> 3 votes
# MATL, ~~10~~ 6 bytes

```
&f-|X>

```

Try it online!

Port of @ovs's Jelly solution.

*(-4 bytes thanks to @LuisMendo)*

---

*Older*

### MATL, 16 bytes

```
&+t"tX@&Rs~?X@q.

```

Try it out! Check all cases

Outputs a transformed version of the input (input + input's transpose) and then the bandwidth. Not sure if extraneous output like this is usually allowed; if not, the "cleaner" version is just 1 byte longer: `&+XH"HX@&Rs~?X@q.` Try it out

# Answer
> 3 votes
# Pari/GP, 50 bytes

```
a->m=0;matrix(#a,,i,j,a[i,j]&&m=max(m,abs(i-j)));m

```

Try it online!

# Answer
> 3 votes
# , <sup>~~38~~ ~~31~~</sup> 23 bytes

```
>./@,@(~:&0*|@-/~@i.@#)

```

-7 bytes by removing some useless parentheses
-8 bytes, thanks @ovs (see comment below)

Try it online!

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

```
x=>x.map((r,i)=>r.map((c,j)=>v=c?Math.max(i-j,j-i,v):v),v=0)&&v

```

Try it online!

# Answer
> 2 votes
# JavaScript (ES7),  ~~58~~  55 bytes

```
m=>m.map(q=(r,y)=>r.map(v=>q=!v|(n=y*y--)<q?q:n))|q**.5

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 9 bytes

```
ĀDƶsøƶøαà

```

(Or `ø‚Ā€ƶ`øαà` as minor alternative.)

Try it online or verify all test cases.

**Explanation:**

```
Ā        # Transform each non-0 integer in the input-matrix to a 1
 D       # Duplicate this matrix of 0s/1s
  ƶ      # Multiply each inner value by its 1-based row-index
 s       # Swap so the matrix of 0s/1s is at the top again
  øƶø    # Do the same for the columns
         # (where `ø` is a zip/transpose, to swap rows/columns)
     α   # Take the absolute difference of the values at the same positions
      à  # Pop and push the flattened maximum
         # (which is output implicitly as result)

```

# Answer
> 1 votes
# Vyxal `G`, 7 bytes

```
vT:ẏ-ȧf

```

Try it Online! or Run all the test cases!

Port of Jelly answer.

## How?

```
vT:ẏ-ȧf
vT      # Get the truthy indices of each
  :ẏ    # Duplicate and get length range [0, length)
    -ȧ  # Subtract the two and get the absolute values (implicit vectorization with both)
      f # Flatten
        # G flag takes the maximum of the top of the stack

```

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


title: Haplololololololology!

text:
# Question
Title: Haplololololololology!
## Haplology

Haplology is a linguistic term:

> the omission of one occurrence of a sound or syllable that is repeated within a word, for example probly for probably.

For this challenge, it means specifically, replacing any sequences of two or more letters that are repeated two or more times with just one copy.

For example:

If there are multiple, non-overlapping repeating sequences, they all get replaced:

* cancangogo -\> cango
* yadayadablahblah -\> yadablah

Only a single round of replacements is performed, taking the longest possible sequences first, then working from left to right:

* mississippi -\> missippi
* mymememymemebooboo -\> mymemeboo
* aaaabaaaab -\> aaaab

This means the returned result can contain repeating sequences:

* babambambadingding -\> babambading

It cans also mean the end result is longer that it would be if replacement happened strictly left to right:

* bababababababadoobababababababadoo -\> bababababababadoo (not badoobadoo)

Any spaces or hyphens that occur between elements of a repeating section must be stripped out, and otherwise retained:

### Challenge

Write a function/program/etc which applies haplology, as defined above, to a single input string.

### Inputs and outputs

Each input will match this regex: `^[a-z]([a-z -]?[a-z])*$`

Your output is a lowercase string containing the haplologised input. No extraneous characters.

Standard rules for taking input and output.

### Scoring

Code golf. Standard rules and exclusions apply.

### Updates

#### Additional test cases and clarification

The algorithm (ignoring punctuation) is:

* find the longest chunk of letters that is repeated at least twice, giving precedence to the left-most chunk
* replace those repeated chunks with one chunk
* repeat, until none left
* never allow any any letter to be processed as part of different chunks

* mamapapatatat -\> mapatat (there is no duplicated sequence longer than 2 characters, so work left to right: mama, papa, tata)
* babababa -\> baba (\[baba\] x2)
* ratratatat -\> ratat (\[rat\] x2, \[at\] x2)

#### Questions

> Why does babambambadingding give babambading instead of bambading (from \[baba\]\[mbamba\]\[dingding\])?

In order of priority, the chunks are \[ding\], \[bam\]. The chunk \[mba\] is the same length as \[bam\], but \[bam\] occurs to its left.

> Why doesn't the "hare krishna" test case greedily take the third consecutive hare?

Because the longer \[hare rama\] takes precedence over the shorter \[hare\]

# Answer
# Jelly, ~~45~~ 38 bytes

```
ḷⱮjⱮƤ““ “-”ẎʋƤṖe@€i1ḣ@ȯ
ŒṖÇƑÐḟẈṢṚƲÞṪÇ€

```

Try it online!

~~Should be correct for real this time thanks to Tanner Swett.~~

Should be correct *for real this time*.

It's even less performant now! Now designed from the ground up to handle spaces and hyphens, but there's got to be a shorter way to do `““ “-”`...

```
ḷⱮjⱮƤ““ “-”ẎʋƤṖe@€i1ḣ@ȯ    Monadic helper link: de-n-plicate an entire string
            ʋƤ             For each prefix of the argument:
 Ɱ                         create a list of, for each element of the argument
              Ṗ            but one,
ḷ                          a copy of the prefix;
    Ƥ                      for each prefix of that list,
  j                        join the copies on
   Ɱ ““ “-”                each of the empty string, a space, and a hyphen;
           Ẏ               flatten the results.
               e@€         Check if the argument is in each of those,
                  i1       get the first index of 1,
                    ḣ@     and return the argument truncated to that length
                      ȯ    or unchanged if it's 1 long and got clobbered.

ŒṖÇƑÐḟẈṢṚƲÞṪÇ€    Main link
ŒṖ                All ways to partition the input.
         ƲÞ       Sort them by
      Ẉ           the lengths
       ṢṚ         sorted descending of
    Ðḟ            the slices which are not
   Ƒ              unchanged by
  Ç               the helper link,
          Ṫ       take the last,
           Ç€     and map the helper over its slices.

```
> 7 votes

# Answer
# 05AB1E, 45 bytes

```
.œεDü2εËyε„ -SNiÛëÜ}}Ë~y€g≠P*}Zi_1šÏJë¯]˜éIªн

```

Very slow, but should work for all test cases including those in the comments.

Try it online or verify some of the smaller test cases. (Some of the test cases are slightly modified in the test suite.)

**Explanation:**

```
.œ             # Get all partitions of the (implicit) input-string
  ε            # Map over each partition-list:
   D           #  Duplicate the partition-list
    ü2         #  Get the overlapping pairs of the strings
      ε        #  Map over each pair:
       Ë       #   Check if both strings in the pair are the same
       y       #   Push the pair again
        ε      #   Map over it:
         „ -S  #    Push pair ["-"," "]
         Ni    #    If the inner map-index is 1 (thus the right item):
           Û   #     Strip the leading "-"/" "
          ë    #    Else (it's 0, thus the left item):
           Ü   #     Strip the trailing "-"/" "
          }    #    Close the if-else statement
        }Ë     #   After the inner-most map: check if both values are the same
             ~ #   Check if either of the two checks is truthy
       y       #   Push the pair yet again
        €g     #   Get the length of each part
          ≠    #   Check for each length that it's NOT 1
           P   #   Take the product to check whether it's truthy for both
            *  #   Check if both checks are truthy
      }        #  Close the inner map
       Z       #  Push the maximum (without popping the list)
        i      #  Pop, and if this is truthy:
         _     #   Invert all booleans in the list
          1š   #   Prepend an additional leading 1
            Ï  #   Only leave the string-parts at the truthy indices
             J #   And join them together to a string
        ë      #  Else:
         ¯     #   Push an empty list instead
  ]            # Close the if-else statement and outer map
   ˜           # Flatten to remove all empty lists
    é          # Sort the strings by length
     Iª        # Append the input in case it's empty
       н       # Pop and leave the first/shortest one
               # (which is output implicitly as result)

```
> 4 votes

# Answer
# Java (JDK), 308 bytes

```
s->{var r=new java.util.Stack();for(int l=s.length(),i;l>1;l--)for(i=0;i<=s.length()-l;){var x=s.substring(i,l+i++);var p=java.util.regex.Pattern.compile("(\\w[\\w -]*\\w)(-? ?\\1)+").matcher(x);s=p.matches()&&r.add(p.group(1))?s.replace(x,"%"+r.size()+"$S"):s;}return"".format(s.toLowerCase(),r.toArray());}

```

Try it online!

## Explanation

This algorithm takes all substrings that exist, from longest, to smallest and checks if that one is a repetition with spaces or dashes. If it is, it takes the repeated value and stores it in a list (the `Stack` in the code) and replaces that long substring to something with special characters (`%1$S` with 1 being any number, actually) so that it's not matched anymore later on.

After all repetitions are found, the string, taken as lowercase, is actually a formattable that can be properly formatted to wrap up the replacements with `String.format`.

## Credits

* -3 bytes thanks to Kevin Cruijssen.
* -3 bytes by backporting Jakque's regex suggestion from my Python answer.
> 4 votes

# Answer
# Python 3.8 (pre-release), 196 bytes

```
import re
def f(s,*r):
 for l in range(-len(s),-2):
  for i in range(len(s)-~l):
   if p:=re.match("(\w[\w -]*\w)(-? ?\\1)+$",x:=s[i:i-l]):s=re.sub(x,"{%s}"%len(r),s);r+=p[1],
 return s.format(*r)

```

Try it online!

## Credits
> 4 votes

# Answer
# Python3, 283 bytes:

```
R,L=range,len
def f(s):
 m=[]
 for x in R(L(s)):
  for y in R(x+2,L(s)):
   S=s;T=s[x:y];K=0;X=x
   while S[(F:=(X+(X<L(S)and S[X]in[' ','-']))):][:L(T)]==T:K+=1;X=F+L(T)
   if K>1:m+=[[s[:x],T,len(T*K),s[X:]]]
 return s if[]==m else f((M:=max(m,key=lambda x:x[2]))[0])+M[1]+f(M[-1])

```

Try it online!

A no-import solution in Python.
> 3 votes

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


title: Make Me a Sandwich

text:
# Question
Title: Make Me a Sandwich
Challenge: Write a makefile, which would lead to this behavior:

```
% make me a sandwich
What? Make it yourself
% sudo make me a sandwich
Okay

```

Rules:

1. Should work on a Linux machine, where the user isn't root but allowed to use `sudo`.
2. Must not say `Okay` to any shorter make command (e.g. `sudo make sandwich`).
3. The second command should work because of `sudo`, not because it's the second invocation.

Guidelines:

1. Keep it short (after all, it's a Code Golf site).
2. It would be nice if it would actually make a sandwich.
3. Try to cleverly hide why `sudo` makes a difference.

The winner will be decided by votes.

# Answer
> 11 votes
Okay, I'll bite. This doesn't necessarily adhere to guideline #3, but it does a fair job on the other two guidelines. It also cleans up after itself, as any good sandwich-maker should.

```
.SILENT:

%:%.c
        $(CC) -o $@ $^ && rm -f $^

default:
        echo 'The makings for a sandwich are here.'

a.c:
        echo '#include <stdio.h>' > a.c
        echo 'int main() {' >> a.c
        echo '  char *txt[] = { "What? Make it yourself.", "Okay." };' >> a.c
        echo '  int n = 0;' >> a.c
        echo '  while (getchar() != EOF) n ^= 1;' >> a.c
        echo '  puts(txt[n]); return 0; }' >> a.c

me.c:
        echo '#include <stdio.h>' > me.c
        echo '#include <unistd.h>' >> me.c
        echo 'int main() {' >> me.c
        echo '  char *txt[] = { "/dev/null", "sandwich" };' >> me.c
        echo '  puts(txt[!getuid()]); return 0; }' >> me.c

sandwich:
        ./me | ./a | tee `./me`
        rm -f me a

clean:
        rm -f sandwich

```

(Less buggy, and hopefully a bit less boring, than my initial submission.)

# Answer
> 9 votes
A fairly compact solution that ignores guideline #2 (127 characters, including some unnecessary whitespace). I follow breadbox's practice of cleaning up after myself. Don't put any other file in the same directory as the makefile! Also, note that the makefile must be called `Makefile`, other names will not work.

```
me: ; echo echo Okay >$@
a: ; chmod u=x me
sandwich: ; ./me 2>/dev/null || echo 'What? Make it yourself'; rm -f [!M]*
.SILENT:

```

Usage:

```
$ make me a sandwich
What? Make it yourself
$ sudo make me a sandwich
Okay
$ sudo make me sandwich
What? Make it yourself
$ sudo make a sandwich
chmod: cannot access `me': No such file or directory
make: *** [a] Error 1
$ sudo make sandwich
What? Make it yourself

```

I like the way this one deals with guideline #3. Just one press of `Shift` makes the difference.

# Answer
> 4 votes
Not mine, and not a true solution as it violates rule #2, but it has a very interesting story that led me here:

```
# With apologies to XKCD #149
me:
    @:
a:
    @:
sandwich:
    @[ "$$(id -u)" -eq 0 ] && { echo "Okay"; touch sandwich; } || echo "What? Make it yourself!"

```

So, where this came from?

I was just messing with the cloud-init script `/boot/user-data` in Ubuntu 22.04 Server image for Raspberry Pi, when I came into this example snippet:

```
## Write arbitrary files to the file-system (including binaries!)
#write_files:
#- path: /etc/default/console-setup
#  content: |
#    # Consult the console-setup(5) manual page.
#    ACTIVE_CONSOLES="/dev/tty[1-6]"
#    CHARMAP="UTF-8"
#    VIDEOMODE=
#    FONT="Lat15-Terminus18x10.psf.gz"
#    FONTFACE=
#    FONTSIZE=
#    CODESET="Lat15"
#  permissions: '0644'
#  owner: root:root
#- encoding: gzip
#  path: /root/Makefile
#  content: !!binary |
#    H4sICF2DTWIAA01ha2VmaWxlAFNWCM8syVBILMjPyU/PTC1WKMlXiPB2dlFQNjSx5MpNteLi
#    dLDiSoRQxYl5KeWZyRkgXrSCkoqKRmaKgm6pppKCbmqhgoFCrIKamkK1QmpyRr6Ckn92YqWS
#    NdC80uQMBZhOa4VahZoaqIrwjMQSewXfxOxUhcwShcr80qLi1Jw0RSUuAIYfEJmVAAAA
#  owner: root:root
#  permissions: '0644'

```

That binary blob caught my eye... was that an executable? A binary Makefile? It made no sense. Assuming this was plain text with base64 encoding, I tried in a terminal:

```
$ txt='H4sICF2DTWIAA01ha2VmaWxlAFNWCM8syVBILMjPyU/PTC1WKMlXiPB2dlFQNjSx5MpNteLi
> dLDiSoRQxYl5KeWZyRkgXrSCkoqKRmaKgm6pppKCbmqhgoFCrIKamkK1QmpyRr6Ckn92YqWS
> NdC80uQMBZhOa4VahZoaqIrwjMQSewXfxOxUhcwShcr80qLi1Jw0RSUuAIYfEJmVAAAA'
$ printf "$txt" | base64 -d
]�MbMakefileS�,�PH,���O�L-V(�W��vvQP64���M���t��J�Pŉy)��� ^�����Ff��n����nj���B����B�BjrF���vb��5м��
                                                                                �Nk�Z�������{���T�����Ң�Ԝ4E%.���

```

Ouch, a true binary indeed! What the hell..

Oh, wait... `encoding: gzip`. Hummm...

```
$ printf "$txt" | base64 -d | gunzip

```

Ta-da! The `Makefile` above appears!

What a convoluted Easter Egg from... well, I have no idea! And, what was that all about?

So I read the comic, experimented a bit with that Makefile, finally understood the joke, then googled for "make me a sandwich", and finally arrived here!

# Answer
> 3 votes
This solution doesn't adhere to guideline #2 — or does being vaguely sandwich-shaped count? I went on a kind of palindrome theme at the beginning, but I could only find so many ways to make lines symmetric without resorting to lame `real code # ecod laer`. I didn't take guideline #1 very seriously, aesthetics comes first.

Remember that it's a makefile; the 3 successive lines beginning with `if`, `rm` and `echo` begin with a tab. The other indented lines begin with spaces.

```
me : mr ; env | grep -q DO_US || rm -- mr || SU_OD q- perg | vne ; rm : em
                            .SILENT:##:TNELIS.
                              . = a.  .a = .
$(.:.=):;:>$@
sandwich:
    if expr>/dev/null $$(id -u); then echo 'What? Make it yourself'; fi
    rm f- a me mr 2>/dev/null
    echo Okay
mr : ; true : ; touch me : em f- mr || rm -f me : em hcuot ; : eurt ; : rm

```

Usage (the commands can be issued in any order):

```
$ sudo make me a sandwich
Okay
$ sudo make me sandwich
make: *** [sandwich] Error 1
$ sudo make a sandwich
make: *** [sandwich] Error 1
$ sudo make sandwich
make: *** [sandwich] Error 1
$ make me a sandwich
What? Make it yourself
make: *** [sandwich] Error 1

```

As for guideline #3, this isn't cleverly hidden, just slightly weirdly. Some hints:

> There are two different tests: one search for `SUDO_USER`, and one test of whether `id -u` prints 0. Do you see why `What?` is *not* printed for root? Do you see how the lack of `SUDO_USER` causes `Okay` not to be printed?

# Answer
> 2 votes
Here is a first go using a different and simpler technique:

```
.SILENT:

reset_command:
    @rm -f command

me a sandwich: reset_command
    @echo $@ >> command
    -@make `cat command | tr "\n" "_"` 2>/dev/null

me_a_sandwich_: reset_command
    @if [ `whoami` == "root" ]; then echo "Okay"; else echo "What? Make it yourself."; fi

```

I'm pretty sure there is more that I can do with this - get it to respond to other input commands for instance. I'll have to work on the root switch obfuscation and the actual sandwich making.

---
Tags: popularity-contest
---


title: Batt to the Basics

text:
# Question
Title: Batt to the Basics
One of your acquaintances has a hobby of making make-shift electrical gadgets using various types of batteries. However, since they're thrifty, they want to use as few batteries as possible for their projects. This challenge uses several types of batteries; your job is to output the fewest number of batteries that will output a given voltage when chained together.

### The batteries you'll be using

Here are the types of batteries you will be using, along with their ID numbers (I assigned those for this challenge) and their output voltages:

1. AA 1.5V
2. Button battery 3V
3. Li-ion battery 3.7V
4. 9V battery 9V
5. Car battery 12V

Batteries can also be half-charged, meaning that their voltage is half of what it is fully charged (I've removed any batteries who's half-voltages are the voltages of any full batteries):

6. ½ AA .75V
7. ½ Li-ion 1.85V
8. ½ 9V battery 4.5V
9. ½ Car battery 6V

### The rules

* Input `i` must be a float where `1 ≤ i ≤ 100`, and where `i` has 1 or 2 decimal digits.
* Output must be a list of the *fewest number* of battery ID numbers (as listed above) that, when combined, will output the voltage, **or** an empty list (or any other empty value) if the voltage can't be produced using the above batteries. Alternatively, the list can consist of the *voltages* of the batteries used; however, the voltages **must** correspond with one of the batteries above.

Here are some test cases (the numbers aren't very large right now because of the time it takes to run the code for large numbers):

```
input: 1.5
output: [1.5]

input: 2
output: [] or None

input: 7.5
output: [6, 1.5]

input: 15
output: [12, 3]

```

This is a challenge, so the fewest bytes wins!

# Answer
# JavaScript (Node.js), 98 bytes

```
f=(v,s=[],...y)=>s[v*7|0]?'':eval(s)+v?f(v,...y,...[1.5,3,3.7,9,12,.75,1.85,4.5,6].map(e=>s+-e)):s

```

Try it online!

Return voltages splitted by `-`

```
f=(v,s=[],...y)=> // s,...y as testing buffer
    s[v*7|0]?'':  // The longest outputLength/input case, -0.75, need *6.67
    eval(s)+v?    // not equal?
        f(        // continue
            v,
            ...y,
            ...[1.5,3,3.7,9,12,.75,1.85,4.5,6].map(e=>s+-e))
    :s

```
> 3 votes

# Answer
# Python, ~~170~~ 169 bytes

```
from itertools import*
f=lambda i:next(filter(None,(next((x for x in product([1.5,3,3.75,9,12,.75,1.85,4.5,6],repeat=n)if sum(x)==i),0)for n in range(int(i/.75)+2))),())
```

Attempt This Online!

10 bytes could be saved by replacing `range(int(i/.75)+2)` with `range(41)`, but then it may not find the correct solution if `i>30`. I prefer the longer version, since it is correct for any (numeric) input.

Note: it is *extremely* inefficient, but it eventually terminates for every input.
> 2 votes

# Answer
# 05AB1E, 25 bytes

```
•UyмµñFb₃^•₅в20/₃иæé.ΔOQ

```

Outputs a list of the voltages of the batteries, and `-1` if it can't find a result.

(Don't) try it online. (Will time out for all test cases.)

If we remove the `é` it can be somewhat tested, but it won't output the required shortest result anymore: try it online. (And might still time-out.)
And with only `•UyмµñFb₃^•₅в20/₃иæ` we can see all the possible powerset lists: try it online.

**Explanation:**

```
•UyмµñFb₃^•     # Push compressed integer 540570253786318174620
 ₅в             # Convert it to base-255 as list: [30,60,74,180,240,15,37,90,120]
   20/          # Divide each by 20: [1.5,3,3.7,9,12,0.75,1.85,4.5,6]
      ₃и        # Cycle-repeat this list 95 times
                # (95 is the lowest 1-byte constant above 40, which is required to
                # reach the maximum to support input 30 with the lowest voltage 0.75)
        æ       # Pop and push its powerset
         é      # Sort it by length
          .Δ    # Find the first inner list which is truthy for:
                # (or -1 if none were truthy)
            O   #  Sum the list
             Q  #  Check if it's equal to the (implicit) input-float
                # (after which the result is output implicitly)

```

See this 05AB1E tip (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•UyмµñFb₃^•` is `540570253786318174620` and `•UyмµñFb₃^•₅в` is `[30,60,74,180,240,15,37,90,120]`.
> 2 votes

# Answer
# Python 3.8 (pre-release), 126 bytes

Recursive brute-force solution.
Throws exception if no solution is found.

```
lambda n:(g:=lambda i,s=0,l=[]:[l]*(s==i)if s>=i else[b[0]for a in[12,9,6,4.5,3.7,3,1.85,1.5,.75]if(b:=g(i,s+a,l+[a]))])(n)[0]

```

Try it online!
> 2 votes

# Answer
# Python 3 (PyPy), 95 bytes

Returns a singleton list containing the solution. Based on friddo's answer.

```
f=lambda i,*l:sum([f(i,*l,ord(b)/20)for b in'ð´xZJ<%'],[])[:1]if i>sum(l)else[l][sum(l)>i:]

```

Try it online!
> 2 votes

# Answer
# Vyxal, 29 bytes

```
» 3J↔kṫ₅uR»₈τ20/41ẋfṗÞṡ'∑⁰=;h

```

Don't try it online! (it times out)

Add `vøḋ` to the end if it can't be returned as list of rationals instead of decimals. `vøḋ` will return a list of strings, tho. Returns `0` if it can't find a solution.

You can somewhat test it without the `Þṡ`, but it won't return the optimal answer: Try it Online!

**Extremely** slow.

Port of 05AB1E.

## How?

```
» 3J↔kṫ₅uR»                   # Push compressed integer 557746805944978070136
           ₈τ                 # Convert to base 256: [30, 60, 74, 180, 240, 15, 37, 90, 120]
             20/              # Divide each by 20: [1.5, 3.0, 3.7, 9.0, 12.0, 0.75, 1.85, 4.5, 6.0]
                41ẋ           # Repeat that list 41 times: [[1.5, 3.0, ...], [1.5, 3.0, ...], ...]
                   f          # Flatten it: [1.5, 3.0, ..., 1.5, 3.0, ..., ...]
                    ṗ         # Powerset
                     Þṡ       # Sort by length (this is what slows it down so much)
                       '   ;  # Filter for:
                        ∑⁰=   # The sum of this list is equal to the input
                            h # Get the first item

```
> 2 votes

---
Tags: code-golf, number
---


title: Music with pi and e

text:
# Question
Title: Music with pi and e
Because I forgot to celebrate Pi Day (14.3), let's celebrate with \\$\pi\\$, \\$e\\$ (Euler's number) and music!

## Challenge

No, we don't have time to eat a pi-pizza, let's make a program.
What you need is \\$500\\$ digits of \\$\pi\\$, and \\$10\\$ digits of \\$e\\$.

The input is an integer \\$n\\$ between \\$0\\$ and \\$499\\$ inclusive.

Then you should loop through the first \\$n\\$ digits of \\$\pi\\$:

If the digit is:

* \\$0\\$ then the note is `C`
* \\$1\\$ then the note is `D`
* \\$2\\$ then the note is `E`
* \\$3\\$ then the note is `F`
* \\$4\\$ then the note is `G`
* \\$5\\$ then the note is `A`
* \\$6\\$ then the note is `B`
* \\$7\\$ then the note is `C'`
* \\$8\\$ then the note is `D'`
* \\$9\\$ then the note is `E'`

Next, for each digit in \\$\pi\\$, take a digit from \\$e\\$ based on this mapping:

* If the digit from \\$\pi\\$ is \\$0\\$, take the \\$1\\$st digit from \\$e\\$
* If the digit from \\$\pi\\$ is \\$1\\$, take the \\$2\\$st digit from \\$e\\$
* If the digit from \\$\pi\\$ is \\$2\\$, take the \\$3\\$st digit from \\$e\\$
* etc.

You need only \\$10\\$ digits of \\$e\\$, because the digits in \\$\pi\\$ are between \\$0\\$ and \\$9\\$.

Finally, take the note and the digit from \\$e\\$. Return a tuple (or equivalent) containing:

* the note
* the \\$e\\$ digit divided by \\$4\\$ (representing the beat)

## Test cases

```
In:10
Out:
('D', 0.25)
('G', 2.0)
('D', 0.25)
('A', 0.25)
("E'", 1.0)
('E', 2.0)
('B', 2.0)
('A', 0.25)
('F', 0.5)
('A', 0.25)
In:5
Out:
('D', 0.25)
('G', 2.0)
('D', 0.25)
('A', 0.25)
("E'", 1.0)

```

### Help

Here are \\$500\\$ digits of \\$\pi\\$:

```
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912

```

And \\$10\\$ digits of \\$e\\$:
```
2.7182818284

```

Note that '3.' and '2.' don't count in the digits of \\$\pi\\$ and \\$e\\$, and that we are using \\$0\\$ indexing (so the \\$0\\$th digit of \\$\pi\\$ is \\$1\\$ etc.).

## Rules

* This is so the shortest answer wins.
* Optional; After every tuple or list output, there can be a trailing newline.

### As one week is over, here is an ungolfed code in Python 2:

# Python 2, 526 bytes

```
def music_maker(n):
 i=p=1;x=3*100**n
 while x:x=x*i/-~i/4;i+=2;p+=x/i
 pi_number=str(p)[:-1] #First 3 lines calculates Calculate Pi
 euler='7182818284'
 del x,i,p #You don't need those Variables any more. They were ment for calculating
 for i in range(n):
  current_pi = pi_number[i] #Current Pi
  current_e = euler[int(current_pi)] #Current e
  number_to_note = {0:"C", 1:"D",2:"E",3:"F",4:"G",5:"A",6:"B",7:"C'",8:"D'",9:"E'"} #Dict number to note
  print((number_to_note[int(current_pi)], int(current_e)/4)) #Prints result

```

Try it online!

# Answer
# 05AB1E, ~~33~~ 30 bytes

```
LεAuS7£ÀÀD3£''««žsyè©èžt¦®è4/‚

```

Outputs as a list of pairs in the `["string-note", beat-decimal]` format.

Try it online.

**Explanation:**

```
L                # Push a list in the range [1, (implicit) input]
 ε               # Map each integer to:
  Au             #  Push the uppercase alphabet
    S            #  Convert it to a list of characters
     7£          #  Only leave the first 7: ["A","B","C","D","E","F","G"]
       ÀÀ        #  Rotate it twice towards the left: ["C","D","E","F","G","A","B"]
         D       #  Duplicate it
          3£     #  Only leave the first 3 character of this copy: ["C","D","E"]
            ''«  #  Append a "'" to each: ["C'","D'","E'"]
               « #  Merge the two lists together:
                 #   ["C","D","E","F","G","A","B","C'","D'","E'"]
  žs             #  Push an infinite list of pi-digits: [3,1,4,1,5,...]
    yè           #  Index the current integer into it (0-based, so leading 3 is skipped)
      ©          #  Store it in variable `®` (without popping)
       è         #  Index this pi-digit into the notes string-list
  žt             #  Push an infinite list of e-digits: [2,7,1,8,2,...]
    ¦            #  Remove the leading 2
     ®           #  Push the pi-digit from variable `®`
      è          #  Index it into the infinite list of decimal e-digits
       4/        #  Divide it by 4
  ‚              #  Pair the pi-note and e-digit/4 together
                 # (after which the resulting list of pairs is output implicitly)

```
> 5 votes

# Answer
# JavaScript (Node.js),  ~~150 ... 134~~  133 bytes

*Saved 3 bytes thanks to @KevinCruijssen*

Expects a BigInt as input and prints the music to STDOUT. This also works for \\$n\>500\\$.

```
n=>{for(k=p=1n,x=3n*100n**n;x;p+=x/k)x=x*k++/k++/4n;for(;x<n;)console.log('CDEFGABCDE'[d=(p+'')[x++]]+" '"[d/7|0]+'7182818284'[d]/4)}

```

Try it online!

## How?

### Part 1: compute \\$n\\$ digits of \\$\pi\\$

This is based on the following formula:

$$\pi-3=\sum\_{n=1}^{\infty}\frac{3}{4^n}\left(\prod\_{k=1}^{n}\frac{2k-1}{2k}\right)\times\frac{1}{2n+1}$$

Instead of using floats -- whose precision is obviously far too limited -- we use a Big Integer \\$x\\$ initialized to \\$3\\$ times a large enough power of \\$10\\$ and process integer divisions until we have \\$x=0\\$.

For 500 digits, we could just use \\$x=3\cdot10^{503}\\$. We instead start with \\$x=3\cdot100^n\\$, which is more than enough to get \\$n\\$ correct digits and easier to golf.

```
for(                    // loop:
  k = p = 1n,           //   start with k = p = 1
  x = 3n * 100n ** n;   //   start with x = 3 * 100 ** n
  x;                    //   stop when x = 0
  p += x / k            //   add x / k to p after each iteration
)                       //
  x =                   //   update x to:
    x * k++ / k++ / 4n  //     x * k / (k + 1) / 4 (and increment k twice)

```

### Part 2: convert to music notes

```
for(; x < n;)           // repeat as many times as requested:
  console.log(          //   print:
    'CDEFGABCDE'[       //     string of notes
      d = (p + '')[x++] //     d = x-th digit of pi, extracted from p
    ] +                 //
    " '"[d / 7 | 0] +   //     append a quote if d is greater than or equal to 7,
                        //     or a space otherwise
    '7182818284'[d]     //     get the d-th digit of e (using Math.E would be longer)
    / 4                 //     and divide it by 4 for the beat
  )                     //   end of console.log()

```
> 10 votes

# Answer
# Perl 5 `-Mbignum=bpi`, ~~86~~ 84 bytes

```
say+(C..G,A..E)[$_],"'"x($_>6),$",((exp 1)=~/./g)[$_+3]/4for(substr bpi<>+1,2)=~/./g

```

Try it online!

## How?

```
for               # loop over
  (substr         # a substring of
     bpi<>+1,     #   PI to the appropriate number of decimals
     2)           #   starting after the second character
  =~/./g          # split into characters

    say+              # output
      (C..G,A..E)[$_],  # the note letter
      "'"x($_>6),       # a ' if it is in the next octave higher
      $",               # a space
      ((exp 1)          # Euler's number
       =~/./g)           # split into characters
       [$_+3]            # skipping the first 3 (2.7)
       /4                # divided by 4 beats

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), 97 bytes

```
Print[C[D,E,F,G,A,B,"C'","D'","E'"][[#]]|R[E,10,2+#][[1,-1]]/4]&/@#&@@R[Pi,10,#,-1]&
R=RealDigits

```

Try it online!

Prints notes as `[key] | [duration]`, with one note per line.

Since Mathematica's number-\>string functions are so bulky (`FromCharacterCode`, anyone?), hardcoding the keys' names as symbols seems to be shorter.
> 4 votes

# Answer
# Charcoal, 52 bytes

```
Ｐ×φψ¤≕Pi→→≔ＥＫＤＮ→Ｉιθ⎚Ｅθ⁺⁺⁺§…α⁷⁺²ι×'›ι⁶ ∕Ｉ§⪫74×²1828ι⁴

```

Try it online! Link is to verbose version of code. Actually works up to `n=998`. Explanation:

```
Ｐ×φψ¤≕Pi

```

Charcoal apparently has a built-in for π, but unfortunately the only way I know how to use it is copied from the Charcoal answer to Bake a slice of Pi which involves using it as a flood fill. Here I just output `1,000` null characters which therefore gives me `998` decimals of π, well above the `499` required by the challenge.

```
→→≔ＥＫＤＮ→Ｉιθ

```

Now input the number of decimals required, read them from the canvas, and convert them to integers.

Clear the canvas ready for the actual output.

```
Ｅθ⁺⁺⁺

```

Map over the digits and concatenate...

```
§…α⁷⁺²ι

```

... the first `7` letters of the uppercase alphabet, cyclically indexed by 2 more than the digit...

```
×'›ι⁶

```

... an `'` if the digit is greater than 6...

```

```

... a space...

```
∕Ｉ§⪫74×²1828ι⁴

```

... and the appropriate digit divided by 4, taken from the string `7182818284`, constructed by doubling the string `1828` and inserting it into the string `74`.
> 3 votes

# Answer
# Python 2, ~~173~~ ~~164~~ ~~162~~ ~~156~~ ~~150~~ ~~149~~ ~~143~~ 141 bytes

```
def f(n):
 i=p=1;x=3*100**n
 while x:x=x*i/-~i/4;i+=2;p+=x/i
 while x<n:i=int(`p`[x]);print"CDEFGAB"[i%7]+"'"[i<8:],1907986849/9**i%9/4.;x+=1

```

Try it online.

Prints the pairs newline-delimited to STDOUT in the format `string-note beat-decimal` (space-delimited).

Port of *@Arnauld*'s JavaScript answer, so make sure to upvote him!
-6 bytes thanks to *@ovs*, which opened up -6 more bytes by switching to Python 2
-1 byte thanks to *@Arnauld*
-2 bytes thanks to *@Tanmay*
> 3 votes

# Answer
# Vyxal, 29 bytes

```
ƛkAf7Ẏ2Ǔ:3Ẏ\'vJJn∆iin∆i›∆ė4/"

```

Try it Online! or Run both test cases!

Port of 05AB1E. If it can't output rationals instead of decimals, add `øḋ` before `"`. Then it will be as strings.

## How?

```
ƛkAf7Ẏ2Ǔ:3Ẏ\'vJJn∆iin∆i›∆ė4/"
ƛ                              # For each item `n` in the (implicit) inclusive one range of the (implicit) input
 kA                            # Push the uppercase alphabet
   f                           # Convert to list of characters
    7Ẏ                         # Leave only the first seven letters: ["A","B","C","D","E","F","G"]
      2Ǔ                       # Rotate left twice: ["C","D","E","F","G","A","B"]
        :                      # Duplicate
         3Ẏ                    # Leave only the first three letters of the duplicate: ["C","D","E"]
           \'vJ                # Append a single quotation mark to each letter: ["C'","D'","E'"]
               J               # Join these two lists together: ["C","D","E","F","G","A","B","C'","D'","E'"]
                n∆i            # Get the `n`th (zero-indexed) digit of pi
                   i           # Index this into the list of notes
                    n∆i        # Get the `n`th pi digit again
                       ›       # Increment it
                        ∆ė     # Get the zero-indexed E digit from that
                          4/   # Divide by four
                            "  # Pair the pi-note and e-digit/4 together

```
> 3 votes

# Answer
# perl -MMath::BigFloat -pl, 170 bytes

```
$n=$_;$p=new Math::BigFloat;$p->accuracy(500);$_=$p->bpi;s/..//;s!.!'('.substr(CDEFGABCDE,$&,1).("'"x($&>6)).', '.((substr 7182818284,$&,1)/4).")\n"!eg;/(.+\n){$n}/;$_=$&

```

Try it online!

## How does this work?

```
$n = $_;

```

This gets the input (which is in `$_` due to the `-p` switch; the `-l` switch removes the newline).

```
$p = new Math::BigFloat;
$p -> accuracy (500);
$_ = $p -> bpi;
s/..//;

```

This gets us the 500 required digits from \\$\pi\\$. First we create a `Math::BigFloat` object, give it an accuracy of 500 (so, 500 decimals behind the comma). We then query the object to get \\$\pi\\$, which we store in `$_`. And we then remove the first two characters, to set rid of the leading `3.`.

```
s !.!
  '(' .    substr (CDEFGABCDE, $&, 1) . ("'" x ($& > 6)) .
  ', ' . ((substr  7182818284, $&, 1) / 4) .
  ")\n"
  !eg

```

This does the majority of the work. We take each digit of \\$\pi\\$ and replace it with the result of the middle three lines of code above. During the replacement, the digit being replaced is in `$&`. We start with an opening paren, then we look up the note by using the current digit as in index into a string (`substr (CDEFGABCDE, $&, 1)`. If the digit is greater than 6, we need to add a prime (`("'" x ($& > 6))`). We then add a comma. Then, to get the beat, we index into the digits of \\$\epsilon\\$, and divide by four (`((substr 7182818284, $&, 1) / 4)`). Finally, we add an closing paren and a newline.

```
/(.+\n){$n}/;
$_ = $&

```

This trims the resulting string to the desired length. We're grabbing `n` times a group of non-newline characters followed by a newline character, and store the result into `$_`, which gets printed due to the `-p` command line switch.
> 1 votes

---
Tags: code-golf, math, number, music, pi
---


title: Convert to base i - 1

text:
# Question
Title: Convert to base i - 1
Given \\$ i = \sqrt{-1} \\$, a base-\\$ (i - 1) \\$ binary number \\$ N \\$ with \\$ n \\$ binary digits from \\$ d\_{0} \\$ to \\$ d\_{n - 1} \\$ satisfies the following equation.

$$ N = d\_{n - 1} (i - 1) ^ {n - 1} + d\_{n - 2} (i - 1) ^ {n - 2} + \cdots + d\_{1} (i - 1) + d\_{0} $$

For example, a decimal number \\$ 15 \\$ is \\$ 100011101 \\$ in base-\\$ (i - 1) \\$ since,

$$ (i - 1) ^ {9 - 1} + (i - 1) ^ {5 - 1} + (i - 1) ^ {4 - 1} + (i - 1) ^ {3 - 1} + (i - 1) ^ {1 - 1} $$

$$ = 16 + (-4) + (2 + 2i) + (-2i) + 1 = 15 $$

This is a list of \\$ 0 \\$ to \\$ 9 \\$ converted to base-\\$ (i - 1) \\$.

```
0         0
1         1
2      1100
3      1101
4 111010000
5 111010001
6 111011100
7 111011101
8 111000000
9 111000001

```

Given a decimal integer as input, convert the input to a base-\\$ (i - 1) \\$ binary number, which is then converted again to decimal as output.

For example,

```
 15 -> 100011101 -> 285
(in)               (out)

```

You may assume that the input is always \\$ \ge 0 \\$, and the output will fit in the range of \\$ \[0, 2^{31})\\$.

---

### Test cases

```
0 -> 0
1 -> 1
2 -> 12
3 -> 13
4 -> 464
5 -> 465
6 -> 476
7 -> 477
8 -> 448
9 -> 449
2007 -> 29367517
9831 -> 232644061

```

# Answer
> 9 votes
# Python, 49 bytes (@xnor)

```
lambda n:3*int(f"{n+a^a:b}",4)&a+a//12
a=2**34//5
```

Attempt This Online!

## Old Python, 51 bytes

```
lambda n:3*int(f"{n+a^a:b}",4)&a+a//12
a=0xcccccccc
```

Attempt This Online!

### How

In polar coordinates the base is \\$b\_k = \sqrt 2^k \times e^{\frac{3ki\pi} 4}\\$. From this it is easy to verify $$ \begin{align} 1 &= b\_0 & 2 &= b\_2+b\_3 & -4 &= b\_4 & -8 &= b\_6+b\_7 \\ 16 &= b\_8 & 32 &= b\_{10}+b\_{11} & -64 &= b\_{12} & &\ldots \end{align} $$

*Display 1*

Observations:

1. as the size of the base is \\$\sqrt 2\\$ we need twice the number of 'bits' than in standard binary.
2. Bits 1, 5, 9, ... are never used. This is encoded by the bitmask `0b ... 1101 1101 1101 = 0xdddddddd = a + a//12`
3. Standard bits 2,3,6,7,10,11,... occur with a negative sign. This is encoded by the bitmask `0b ... 1100 1100 1100 = 0xcccccccc = a`.

We can do the transformation in two steps: from standard base S = 1,2,4,8,16,32,... to 'alternating' A = 1,2,-4,-8,16,32,... and then from A to final base C (for 'complex').

Step 1, S-\>A:

Because of observation 3 if any of the bits of `a` is set in the input *n* (S bits) we need to borrow from the next higher bit. If that bit is also in `a` or was already set in *n* we need to borrow from the next higher bit and so on.

One can check that the right cascade of carries is triggered by simply adding *n* and `a`.

One can also check that afterwards the not in `a` A bits are already correct whereas the in `a` A bits are all wrong. In other words we need to `xor` with `a` and that completes step 1.

Step 2, A-\>C:

For this we just need to look up the bit pairs from display 1. One way of doing this is to repeat all bits and then mask as explained in observation 2.

# Answer
> 8 votes
# APL (Dyalog Extended), 17 bytes

Full program. Counting up from `¯1` (exclusive) check if the binary representation interpreted as base `¯1J1` matches the input.

```
1+⍣(⎕=¯1J1⊥2⊤⊣)¯1

```

Try it online!

---

# APL (Dyalog Unicode), 28 bytes

```
{0=⍵:0⋄(16×∇-⌊⍵÷4)+12⊥2 2⊤⍵}

```

Try it online!

The Python implementation on OEIS can be simplified to

$$ f(n) = \begin{cases} 0 & \text{if } n = 0 \\ 16 f(-\lfloor{n \over 4}\rfloor) + \[0,1,12,13\]\[n \bmod 4\] & \text{otherwise.} \end{cases} $$

`12⊥2 2⊤⍵` is a short way of expressing the mod-4 mapping using the base conversion primitives, everything else should map 1-to-1 to the mathematical notation.

# Answer
> 7 votes
# JavaScript (Node.js), 33 bytes

Implementation of the formula mentioned in my other answer. Borrowed the `3-n>>2` from a comment by AnttiP.

```
f=n=>n&&1-(n&3)&13^1|f(3-n>>2)<<4

```

Try it online!

The `(n&3)` could be `n%4` in Python, but Javascript handles negative dividends differently.

While one could have come up with the magic formula `1-(n&3)&13^1` by hand, I used Lynn's pysearch to find it.

| `(n&3)` | `1-(n&3)` | `1-(n&3)&13` | `1-(n&3)&13^1` |
| --- | --- | --- | --- |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | -1 | 13 | 12 |
| 3 | -2 | 12 | 13 |

# Answer
> 6 votes
# , ~~54~~ 51 bytes

Or **\>=4.1, 44 bytes** by replacing the word `function` with a `\`.

*Edit: -3 bytes thanks to Polichinelle.*

```
f=function(n)`if`(n,16*f(-(n%/%4))+n%%4*6-5*n%%2,0)

```

Try it online!

Based on formula found by @ovs.

# Answer
> 5 votes
# Jelly, 8 bytes

```
Bḅ-ı=ʋ1#

```

Try it online!

Let \\$f(n)\\$ be the function described in the question. We use the fact that \\$f(n) \ge n\\$ for al \\$n = 0,1,2,...\\$ to save a couple of bytes.

## How it works

```
Bḅ-ı=ʋ1# - Main link. Takes n on the left
     ʋ   - Group the last 4 links into a dyad g(k, n):
B        -   Convert k to binary
 ḅ-ı     -   Convert this to base -ı (-1+1j)
    =    -   Does this equal n?
      1# - Find the first k ≥ n, such that g(k,n) is true

```

# Answer
> 4 votes
# Factor, ~~82~~ 78 bytes

```
:: f ( m -- n ) m [ 0 ] [ 4 / ⌊ neg f 16 * m 4 rem "\0\r"nth + ] if-zero ;

```

Try it online!

This is a direct implementation of the recursive formula given by @ovs.

And for posterity, my original answer:

# Factor \+ `lists.lazy math.unicode`, 85 bytes

```
[ 0 lfrom [ >bin reverse 49 swap indices C{ -1 1 } swap n^v Σ = ] with lfilter car ]

```

Try it online!

## Explanation

Tries every number starting from 0 until it finds a match, in a brute force way. Slow for the larger inputs, but should theoretically eventually finish.

* `0 lfrom [ ... = ] with lfilter car` Apply `...` to every number \>= 0 until it equals the input. For instance, for input 15 and n=285...

```
                 ! 15 285
>bin             ! 15 "100011101"
reverse          ! 15 "101110001"
49               ! 15 "101110001" 49
swap             ! 15 49 "101110001"
indices          ! 15 V{ 0 2 3 4 8 }            (get indices of the 1s)
C{ -1 1 }        ! 15 V{ 0 2 3 4 8 } C{ -1 1 }  (i-1)
swap             ! 15 C{ -1 1 } V{ 0 2 3 4 8 }
n^v              ! 15 V{ 1 C{ 0 -2 } C{ 2 2 } -4 16 }
Σ                ! 15 15                        (sum)
=                ! t

```

# Answer
> 4 votes
# JavaScript, 42 bytes

```
f=(x,y=0)=>x|y&&x+y&1|2*f(1-y-x>>1,x-y>>1)

```

Try it online!

`f(x,y)` produces the base-\\$(-1-i)\\$ representation of \\$ x+iy \\$ (which is identical to the base-\\$(-1+i)\\$ representation for real numbers) reinterpreted as binary, for integers \\$x,y\\$.

`x|y` is zero iff `x` and `y` are both zero; the `&&` short-circuits to produce zero in that case. Otherwise, `x+y&1` gives the ones digit of the base-\\$(-1-i)\\$ representation of \\$ x+iy \\$ (since all higher digits contribute an even amount to `x+y`), and the recursive call produces the rest of the digits.

# Answer
> 4 votes
# x86\_64 machine code, 31 bytes (or 27 bytes)

```
\x81\xc7\xcc\xcc\x00\x00\x81\xf7\xcc\xcc\x00\x00\xb8\x55\x55\x55\x55\xc4\xe2
\x43\xf5\xc0\x8d\x04\x40\x25\xdd\xdd\xdd\xdd\xc3

```

Try it online!

**assembly**

```
add edi, 0xcccc
xor edi, 0xcccc
mov eax, 0x55555555
pdep eax, edi, eax
lea eax, [rax + rax * 2]
and eax, 0xdddddddd
ret

```

This is a port of the amazing solution from @loopywalt. See his post for a detailed explanation of the algorithm. `pdep` is an interesting instruction which solves a problem that otherwise needs some sort of loop or a look-up table. It executes in constant time fast on any Intel hardware that supports it, but on AMD chips before Zen3, it was a slow microcoded instruction with variable latency.

The sequence of 6 instructions has a blazing estimated throughput of 2 cycles.

The first two instructions can be modified to save 4 bytes, but it will run a bit slower.

```
mov ax, 0xcccc
add edi, eax
xor edi, eax

```

# Answer
> 3 votes
# Python 3, <sup>~~65~~ ~~45~~</sup> 40 bytes

```
f=lambda n:n and(n&2)*6+n%2+16*f(3-n>>2)

```

Try it online!

*Saved a whopping ~~20~~ 25 bytes thanks to AnttiP!!!*

# Answer
> 3 votes
# JavaScript (Node.js), ~~33~~ 32 bytes

```
f=n=>n&&f(3-n>>2)*16|6*(n&2)|n&1

```

Try it online!

This is another implementation of the \\$n\rightarrow \lfloor{n/4}\rfloor\\$ recurrence given in the OEIS. (I saved a byte by changing `-(n>>2)` to `3-n>>2`, as suggested by @AnttiP and others.)

# Answer
> 3 votes
# Husk, ~~16~~ 14 bytes

```
B16mo?I+10εB_4

```

Try it online!

Converts to base `-4`, replaces digits `0`, `1`, `2`, `3` with `0`, `1`, `12` & `13`, and converts back from base `16`.

# Answer
> 2 votes
# Charcoal, 28 bytes

```
ＮθＷθ«Ｆ1220⊞υ＆θＩκ≔±÷θ⁴θ»Ｉ↨⮌υ²

```

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

```
Ｎθ

```

Input `n`.

```
Ｗθ«

```

Repeat until `n` is zero.

```
Ｆ1220⊞υ＆θＩκ

```

Create four more "bits" in the "base 2" representation of `n` using the digits `0221` bitwise anded with the current value. This results in `0000`, `0001`, `0220` (i.e. `1100`) and `0221` (i.e. `1101`) (although the bits are actually pushed in reverse order so that they accumulate correctly).

```
≔±÷θ⁴θ

```

Integer divide `q` by `4` and negate it. (Sadly this is not the same as integer dividing `q` by `-4`, otherwise I could use negative base conversion.)

```
»Ｉ↨⮌υ²

```

Convert the "bits" from "base 2" and output the result.

# Answer
> 1 votes
# Pari/GP, 33 bytes

```
f(n)=if(n,16*f(n\-4)+n%4*6-n%2*5)

```

Try it online!

A port of @pajonk's R answer.

# Answer
> 1 votes
# 05AB1E, 12 bytes

```
4(вεD2@ì}16β

```

Port of *@DominicVanEssen*'s Husk answer, so make sure to upvote him as well!

Try it online or verify all test cases.

**Explanation:**

```
4(в      # Convert the (implicit) base-10 input-integer to base-(-4) as list
   ε     # Map over each integer in the list
    D    #  Duplicate it
     2@  #  Check if it's >= 2
       ì #  Prepend that 0/1 to the integer
   }16β  # After the map: convert the list from base-16 to a base-10 integer
         # (which is output implicitly as result)

```

Two equal-bytes alternatives for `εD2@ì}` could be `D2@T*+` or `D2@søJ`, but I haven't been able to find anything shorter for this.

# Answer
> 1 votes
## Python, 48 bytes

```
f=lambda n:16*f(-(n//4))+6*(n&2)+n%2 if n else 0

```

This is a recursive function that takes advantage of the fact that because (i-1)^4 = -4, then every 4 bits of the output corresponds to a base -4 number.

`f(-(n//4))` makes the recursive call for the base -4 representation of `n` *except* the last digit. Unfortunately, the inner parentheses are necessary. Multiplying by 16 shifts left 4 binary digits to make room for the last digit.

`6*(n&2)+n%2` is a golfed way to encode the last base -4 digit:

* 00 → 0000
* 01 → 0001
* 10 → 1100
* 11 → 1101

The last bit of the input (`n%2` or `n&1`) corresponds directly to the last digit of the output, while the first bit of the input (`n&2`), corresponds to either 000 (decimal 0) or 110 (decimal 6). Unfortunately, the parentheses in `n&2` are necessary because of operator precedence.

`if n else 0` handles the base case of the recursion.

# Answer
> 1 votes
# Vyxal, 9 bytes

```
λb°‹β?=;ṅ

```

Try it Online!

Port of Jelly.

---
Tags: code-golf, number-theory, base-conversion, complex-numbers
---


title: Floating Point XOR

text:
# Question
Title: Floating Point XOR
Your task is pretty simple. Given two floats, bitwise xor the binary representation of them, and output that as a float.

For example,

```
Normal: 16.7472 ^ 123.61 = 7.13402e-37
Binary: 01000001100001011111101001000100 ^ 01000010111101110011100001010010 = 00000011011100101100001000010110

Normal: 2.2 ^ 4.4 = 1.17549e-38
Binary: 01000000000011001100110011001101 ^ 01000000100011001100110011001101 = 00000000100000000000000000000000

Normal: 7.898 ^ 3.4444 = 1.47705e-38
Binary: 01000000111111001011110001101010 ^ 01000000010111000110101001111111 = 00000000101000001101011000010101

```

Restrictions/clarifications:

# Answer
> 57 votes
# x86-64 machine code, 4 bytes

```
0f 57 c1 c3

```

In assembly:

```
xorps xmm0, xmm1
ret

```

This is a callable function that takes two floats or doubles as arguments (in `xmm0` and `xmm1`) and returns a float or double (in `xmm0`).

That matches the calling conventions of both Windows x64 *and* the x86-64 SysV ABI, and works for floats as well as doubles. (They're passed / returned in the low 4 or 8 bytes of XMM registers).

# Answer
> 12 votes
# C++ (gcc), ~~74~~ 32 bytes

```
#define f(x,y)*(int*)x^=*(int*)y

```

Try it online!

I haven’t previously golfed in C++ so am grateful to all those who helped halve the size of the code! A macro which takes pointers to two floats as its arguments and modified the first to return the result.

Thanks to @12Me1 for saving 2 bytes and @Arnauld for saving 4! Thanks to @Nishioka for saving another 14, @Neil a further 6 and @AZTECCO and @Nishioka another 11! Thanks to @PeterCordes for saving 5 bytes!

# Answer
> 9 votes
# ARM Thumb Machine Code, 6 4 Bytes

48 40 70 47

In assembly:

```
EORS R0, R1 ; Exclusive Or of the first two params, store result in the return register
BX LR       ; Branch to the value stored in the Link Register (Return address)

```

Under the standard Arm calling convention, the first two parameters are passed in the registers R0 and R1, results are returned in R0, and LR holds the return address. Assuming you're using the soft float ABI with 32 bit floats, this will perform the desired operation in 4 bytes.

-2 bytes thanks to Cody Gray

# Answer
> 6 votes
# Python 3 \+ numpy, ~~75~~ 59 bytes

```
lambda x,y:(x.view("i")^y.view("i")).view("f")
import numpy

```

Try it online!

Defines a lambda which takes two numpy float32 arrays as its arguments and returns a numpy float32 array.

Thanks to @ShadowRanger for saving 14 bytes, and Joel a further 2!

If the import can be dropped (since my lambda itself calls methods on numpy objects rather than any base numpy functions), I could save a further 13 bytes. I’m uncertain on this from the code golf standard rules.

# Answer
> 6 votes
# Jelly \+ numpy, ~~89~~ 77 bytes

```
“(F(“I^F(“IvF).item()”;"F“¢lẒṾ:/²)Ɓɱ¡vẠ⁷5Rʠ¡7ɼṆṪ{ė4¶Gẉn`¡Ð}ṫȥṄo{b»Ḳ¤¹ṣḢ}jʋƒŒV

```

Try it online!

Has the dubious honour of being longer than the Python 3 code it reproduces, largely because of the need to convert to/from numpy objecte and the fact that numpy isn’t loaded by Jelly so the `__import__()` built-in has to be used.

A monadic link taking the two floats as a list as its argument and returning a float.

Evaluates the following Python 3 code:

```
(__import__('numpy').float32(x).view("i")^__import__('numpy').float32(y).view("i")).view(__import__('numpy').float32).item()

```

where `x` and `y` are substituted with the input.

# Answer
> 5 votes
# APL (Dyalog Unicode), 14 bytesSBCS

Full program. Prompts for 1-column matrix of two IEEE 754 64-bit floating-point numbers (binary64) from stdin. Prints one such number to stdout.

```
645⎕DR≠⌿11⎕DR⎕

```

Try it online!

prompt (numbers that collapse to non-floats can be forced into floats with the function `⊃⊢⎕DR⍨645,⍨⎕DR`)

`11⎕DR` convert to 1-bit Binary (1) **D**ata **R**epresentation (2-row, 64-column matrix)

`≠⌿` vertical XOR reduction

`645⎕DR` convert to 64-bit float (5) **D**ata **R**epresentation (single number)

# Answer
> 5 votes
# VAX BASIC (later VMS BASIC, then Compaq Basic), 11 bytes

```
H = F XOR G

```

Seems a bit silly to me, obviously, older languages will do better because they didn't worry abut strong-typing issues as much.

# Answer
> 3 votes
# Octave, 59 bytes

```
@(a,b)(t=@typecast)(bitxor(t(a,u='int32'),t(b,u)),'single')

```

Try it online!

Typecast is the MATLAB/Octave way of casting without changing the underlying bits. This is required because `bitxor` only works on integers. No idea why they never implemented floating point numbers, even though you can explicitly specify the `AssumedType` as a third argument to `bitxor`. I guess the only use is recreational programming.

# Answer
> 2 votes
# JavaScript (Node.js),  ~~105~~  101 bytes

*Shorter Node version suggested by @Neil*
*Saved 4 more bytes thanks to @ShieruAsakoto*

Takes input as `(x)(y)`.

```
x=>y=>(v=Buffer(4),v.writeInt32LE((g=n=>v.writeFloatLE(n)&&v.readInt32LE())(x)^g(y)),v.readFloatLE())

```

Try it online!

---

# JavaScript (ES6), 115 bytes

Takes input as an array of 2 floats.

```
a=>(v=new DataView(new ArrayBuffer(4))).getFloat32(v.setUint32([x,y]=a.map(n=>v.getUint32(v.setFloat32(0,n))),x^y))

```

Try it online!

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), 92 bytes

```
x=>BitConverter.Int32BitsToSingle(x.Aggregate(0,(a,b)=>a^BitConverter.SingleToInt32Bits(b)))

```

Try it online!

# Answer
> 2 votes
# Perl 5 `-p`, ~~31~~ 27 bytes

*-4 bytes thanks to Grimy*

```
$\=unpack f,$a^=pack f,$_}{

```

Try it online!

# Answer
> 2 votes
# MATL, 10 bytes

```
4Z%Z}Z~9Z%

```

Try it online!

Splitting with `Z}` was shorter than taking two inputs `,4Z%]`

# Answer
> 2 votes
# Java (JDK), ~~109~~ ~~76~~ 63 bytes

```
a->b->a.intBitsToFloat(a.floatToIntBits(a)^a.floatToIntBits(b))

```

Try it online!

Been a while since I golfed in Java and I'm not certain if I need the declaration on the LHS as part of the byte count? If it used DoubleBinaryOperator the LHS would be shorter, but the RHS would have to use Double.doubleToLongBits and Double.longBitsToDouble, so that's actually longer.

Thanks to Neil for a substantial savings on the byte count!

Thanks to Unmitigated for currying the way to another improvement!

# Answer
> 2 votes
# C, 23 bytes

```
f(int*x,int*y){*x^=*y;}

```

Try it online!

This might be a bit shifty; it takes the pointers to `float`s as pointers to `int`s.

However, it does work (this is C after all).

This takes advantage of acceptable input by taking a pointer to the variable and modifying it in-place. No (usable) value is returned.

# Answer
> 1 votes
## Wolfram Mathematica, 50 bytes

```
BitXor@@(FromDigits[RealDigits[#,2,32,0][[1]],2]&)

```

Although I strongly suspect that this could be more golfed, the two extra arguments in `RealDigits` function seem to be necessary for getting a correct result.

Try it online!

# Answer
> 1 votes
# Ruby, ~~78~~ 67 bytes

-11 bytes thanks to @grawity.

```
->x{[x.pack("gg").unpack("NN").inject(&:^)].pack(?N).unpack(?g)[0]}

```

Try it online!

Input is an array of two floats.

# Answer
> 1 votes
# Lua, 73 bytes

```
a,b=('II'):unpack(('ff'):pack(...))print((('f'):unpack(('I'):pack(a~b))))

```

Try it online!

This code assumes 4-bytes unsigned integers and floats which is configuration on `tio.run`. Run as full program with input as arguments.

# Answer
> 1 votes
# MMIX, 8 bytes (2 instrs)

Really, just put in an xor command.

```
00000000: c600 0001 f801 0000                      İ¡¡¢ẏ¢¡¡

```

```
xorflt  XOR $0,$0,$1
        POP 1,0

```

Simples.

# Answer
> 1 votes
# Julia 1.0, 40 bytes

```
~=reinterpret
!x=Float64~⊻((Int~x)...)

```

Try it online!

expects `Float64`s on a 64 bit platform. On a 32 bit platform, use `Float32`

# Answer
> 0 votes
# Clean, 36 bytes

```
f::!Real!Real->Real
f _ _=code{xor%}

```

Try it online!

Thankfully the `Real` and `Int` types are the same sizes on 64-bit platforms...
Unfortunately requires a complete signature otherwise the graph turns into a pretzel and everything segfaults.

# Answer
> 0 votes
# JavaScript (Node.js), 87 bytes

```
x=>(v=Buffer(8),x.map((c,i)=>v.writeFloatLE(c,h=4*i)),v.map(e=>e^v[h++]).readFloatLE())

```

Try it online!

silly

# Answer
> 0 votes
# Factor, 40 bytes

```
[ [ float>bits ] bi@ bitxor bits>float ]

```

Try it online!

```
                     ! 2.2 4.4
[ float>bits ] bi@   ! 1074580685 1082969293
bitxor               ! 8388608
bits>float           ! 1.175494350822288e-38

```

---
Tags: code-golf, bitwise, floating-point
---