title: A bit of a digital XOR

text:
# Question
Title: A bit of a digital XOR
Here are the first 100 numbers of a sequence:

```
1,2,33,4,55,66,777,8,99,11,111,12,133,141,1515,1,11,18,191,22,222,222,2232,24,252,266,2772,282,2922,3030,31313,3,33,33,335,36,377,383,3939,44,441,444,4443,444,4455,4464,44747,48,499,505,5151,522,5333,5445,55555,565,5757,5855,59559,6060,61611,62626,636363,6,66,66,676,66,666,770,7717,72,737,744,7557,767,7777,7878,79797,88,888,882,8838,888,8888,8886,88878,888,8898,9900,99119,9929,99399,99494,995959,96,979,988,9999,100

```

**How does this sequence work?**

```
n:            1 2  3  4   5   6   7   8    9    10   11   12   13   14   15   16    17
binary:       1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 10001
n extended:   1 22 33 444 555 666 777 8888 9999 1010 1111 1212 1313 1414 1515 16161 17171
1-bit digits: 1 2  33 4   5 5 66  777 8    9  9 1 1  1 11 12   13 3 141  1515 1     1   1
result:       1 2  33 4   55  66  777 8    99   11   111  12   133  141  1515 1     11

```

As you can see, the steps to get the output are as follows:

1. Convert integer \\$n\\$ to a binary-string.
2. Extend integer \\$n\\$ to the same length as this binary-string. (I.e. \\$n=17\\$ is `10001` in binary, which has a length of 5. So we extend the `17` to this same length of 5 by cycling it: `17171`.)
3. Only keep the digits in the extended integer \\$n\\$ at the positions of the `1`s in the binary-string.
4. Join them together to form an integer.

## Challenge:

One of these options:

1. Given an integer \\$n\\$, output the \\$n^{\text{th}}\\$ number in the sequence.
2. Given an integer \\$n\\$, output the first \\$n\\$ numbers of this sequence.
3. Output the sequence indefinitely without taking an input (or by taking an empty unused input).

## Challenge rules:

* Step 4 isn't mandatory to some extent. You're also allowed to output a list of digits, but you aren't allowed to keep the falsey-delimiter. I.e. \\$n=13\\$ resulting in `[1,3,3]` or `"1,3,3"` instead of `133` is fine, but `"13 3"`, `[1,3,false,3]`, `[1,3,-1,3]`, etc. is not allowed.
* Although I don't think it makes much sense, with option 1 you are allowed to take a 0-based index \\$m\\$ as input and output the \\$(m+1)^{\text{th}}\\$ value.
* If you output (a part of) the sequence (options 2 or 3), you can use a list/array/stream; print to STDOUT with any non-digit delimiter (space, comma, newline, etc.); etc. Your call. If you're unsure about a certain output-format, feel free to ask in the comments.
* Please state which of the three options you've used in your answer.
* The input (with options 1 and 2) is guaranteed to be positive.
* You'll have to support at least the first \\$\[1, 10000\]\\$ numbers. \\$n=\text{...},9998,9999,10000\]\\$ result in \\$\text{...},9899989,99999999,10010\]\\$ (the largest output in terms of length within this range is \\$n=8191 → 8191819181918\\$).

## General rules:

* This is , so 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 (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

*PS: For the 05AB1E code-golfers among us, 4 bytes is possible.*

# Answer
> 10 votes
# Wolfram Language (Mathematica), 72 bytes

```
Pick[Flatten[(i=IntegerDigits)/@Table[#,s=Length[p=#~i~2]]][[;;s]],p,1]&

```

Try it online!

Here is the plot of the first 30.000 such numbers

And here is the Logarithmic plot

# Answer
> 6 votes
# Python 3, ~~80~~ \\$\cdots\\$ ~~52~~ 53 bytes

Saved ~~a~~ 2 bytes thanks to Jitse!!!
Saved ~~7~~ 6 bytes thanks to Surculose Sputum!!!
Added a byte to fix bugs kindly point out by Jitse and Surculose Sputum.

```
lambda n:[c for c,d in zip(str(n)*n,f'{n:b}')if'0'<d]

```

Try it online!

Returns the \\$n^{\text{th}}\\$ number in the sequence as a list of digits.

# Answer
> 6 votes
# Jelly, 4 bytes

```
BTịD

```

Try it online, code that computes the \\$n\\$th term of the sequence, or check the first 100 terms!

How it works:

```
B     convert number to binary, i.e. 5 -> [1, 0, 1]
 T    keep the indices of the Truthy elements, i.e. [1, 0, 1] -> [1, 3]
  ị   and then index safely into...
   D  the decimal digits of the input number

```

By "index safely" I mean that indices out of range are automatically converted into the correct range!

# Answer
> 5 votes
# , ~~13~~ 10 bytes

```
#:##@#:$":

```

Try it online!

# Answer
> 5 votes
# 05AB1E, 4 bytes

```
×IbÏ

```

Try it online!

Yeah, I found the mysterious 4-byte 05AB1E answer :D

```
×   expand the input digits (input 123 -> 123123123123123... )
Ib  get the binary value of input (123 -> 1111011)
Ï   keep only the digits where the corresponding binary digit is 1

```

# Answer
> 5 votes
# APL (dzaima/APL), 7 bytes

```
⊤⌿≢∘⊤⍴⍕

```

Try it online!

### How it works

```
⊤⌿≢∘⊤⍴⍕  ⍝ Input: n
  ≢∘⊤    ⍝ Length of base-2 digits
     ⍴⍕  ⍝ Repeat the digits of n (as a string) to the length of above
⊤⌿       ⍝ Take the digits where the corresponding base-2 digit is 1

```

---

# APL (Dyalog Unicode), 16 bytes

```
⍕(∊⊢⊆⍴⍨∘≢)2∘⊥⍣¯1

```

Try it online!

### How it works

```
⍕(∊⊢⊆⍴⍨∘≢)2∘⊥⍣¯1  ⍝ Input: n
          2∘⊥⍣¯1  ⍝ Binary digits of n
⍕                 ⍝ Stringify n
 (       )        ⍝ Inner function with the two args above
       ∘≢         ⍝ Length of binary digits
     ⍴⍨           ⍝ Cycle the string digits to the length
  ∊⊢⊆             ⍝ Filter the digits by the binary digits

```

# Answer
> 4 votes
# JavaScript (ES6), 55 bytes

```
n=>n.toString(2).replace(/./g,(d,i)=>+d?(n+=[n])[i]:'')

```

Try it online!

### Commented

```
n =>               // n = input
  n.toString(2)    // convert n to a binary string
  .replace(        // replace:
    /./g,          //   for each
    (d, i) =>      //   digit d at position i:
      +d ?         //     if d is '1':
        (n += [n]) //       coerce n to a string (if not already done)
                   //       and double its size to make sure we have enough digits
        [i]        //       extract the i-th digit
      :            //     else:
        ''         //       discard this entry
  )                // end of replace()

```

# Answer
> 4 votes
# Python 2, 52 bytes

```
lambda n:[c for c,i in zip(`n`*n,bin(n)[2:])if'0'<i]

```

Try it online!

**Input:** An integer \\$n\\$
**Output:** The \\$n^{th}\\$ numbers in the sequence, in the form of a list of digits.

**How:**

* `bin(n)` is the binary string of `n`, e.g `bin(2)` is `"0b10"`. Thus `bin(n)[2:]` is the binary string of `n` without the `0b`.
* ``n`*n` creates the n-extended string by repreating the decimal string of `n` n times. This is longer than needed, but that's ok because extra characters will be truncated later.
* `c,i in zip(`n`*n,bin(n)[2:])` takes each pair of corresponding characters `c,i` from the binary string and the n-extended string.
* `if'0'<i` checks if `i` is the character `"1"`, if so the corresponding character `c` is kept in the result list.

# Answer
> 4 votes
# C (gcc), ~~101~~ \\$\cdots\\$ ~~96~~ 91 bytes

Save ~~a~~ 6 bytes thanks to ceilingcat!!!

```
b;i;f(n){char s[n];for(b=1;i=n/b;b*=2);for(;b/=2;++i)b&n&&putchar(s[i%sprintf(s,"%d",n)]);}

```

Try it online!

Outputs the \\$n^{\text{th}}\\$ number in the sequence.

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~25~~ 24 bytes

## Code

```
{b←2∘⊥⍣¯1⋄(b⍵)/(⍴b⍵)⍴⍕⍵}
```

Try it online!

### Explanation

```
{                                        ⍝ Start function definition
  b ← 2∘⊥⍣¯1                             ⍝ Let b ← binary conversion function
              ⋄                           ⍝ Start new clause
                (b⍵)                      ⍝ Binary representation of ⍵ (input)
                     /                    ⍝ Mask boolean list over following string
                       (⍴b⍵)              ⍝ Length of boolean representation of ⍵
                             ⍴            ⍝ Reshape
                                ⍕⍵        ⍝ Stringify ⍵
                                    }     ⍝ End function definition

```

### Binary Conversion

This is all much longer than one would expect from *APL* and is due to the lack of a concise binary conversion function. Unfortunately, the above is the best we can do. Below is the breakdown:

* 'Power' () does an operation *n* times. So `f⍣¯1` calculates the inverse of `f`, if it can.
* 'Decode' () converts from an arbitrary base back to decimal; `2 ⊥ 1 1 0 1` returns `13`.
* 'Jot' () can compose two functions as in `(f∘g) 3` or curry as in`(1∘+) 3`.

Together, `2∘⊥⍣¯1` denotes the inverse of the function that converts from binary to decimal.
(Two left-curried with the encoding function, `2∘⊥`, converts binary to decimal.)

# Answer
> 3 votes
# Ruby, 68 bytes

```
->n{n.to_s(2).gsub(/./).with_index{|b,i|b>?0?(n.to_s*n)[i]:""}.to_i}

```

Try it online!

Returns the **n**th number in the sequence.

---

I'm no expert golfer, so it's undoubtedly possible there's a better Ruby solution, but I'm (not altogether unpleasantly) surprised to see a challenge where Python and JavaScript both outperform Ruby. I guess python's list comprehensions are a perfect fit for this challenge, and JavaScript passing the index as a parameter to the `replace` method is very convenient.

# Answer
> 2 votes
# APL+WIN, 25 bytes

Prompts for integer n and outputs nth term

```
((b⍴2)⊤n)/(b←1+⌊2⍟n)⍴⍕n←⎕

```

Try it online! Coutesy of Dyalog Classic

# Answer
> 2 votes
# Red, 131 bytes

```
func[n][i: 0 remove-each _ t: take/part append/dup t: to""n n |:
length? s: find to""enbase/base to#{}n 2"1"|[s/(i: i + 1) =#"0"]t]

```

Try it online!

# Answer
> 2 votes
# PHP, ~~75~~ ~~86~~ ~~81~~ 73 bytes

```
for(;$i<strlen($d=decbin($a=$argn));$i++)if($d[$i])echo$a[$i%strlen($a)];

```

Try it online!

Gives the nth number.

Original version didn't handle 0's in input correctly.

# Answer
> 2 votes
# 05AB1E, 4 bytes

```
∍IbÏ

```

**Try it online!**

### How?

```
∍IbÏ - Full program expecting a single input      e.g. 13    stack:
∍    - extend a to length b (stack empty so a=b=input)       [1313131313131]
 I   - push the input                                        [1313131313131, 13]
  b  - convert to binary                                     [1313131313131, 1101]
   Ï - a where b is 1                                        [133]
     - implicit output                                       133

```

# Answer
> 2 votes
# Perl 5 -n, 75 bytes

```
map{$i=0;@b=split//,sprintf"%b",$_;say@s=grep{$b[$i++]}split//,$_ x@b}1..$_

```

Try it online!

Prints the first `n` numbers in the sequence

# Perl 5 -nl, 60 bytes

```
@b=split//,sprintf"%b",$_;say@s=grep{$b[$i++]}split//,$_ x@b

```

Try it online!

Shorter version that just prints the `n`th number

# Answer
> 2 votes
# Rust, ~~131~~ 129 bytes

```
|n|format!("{:b}",n).chars().zip(format!("{}",n).chars().cycle()).flat_map(|(b,c)|if'0'<b{Some(c)}else{None}).collect::<String>()

```

~~Try it online!~~
Try it online!

Works according to option 1 and returns the \\$n^{\text{th}}\\$ number of the sequence as a string.

-2 thanks to Kevin Cruijssen!

## Explanation

```
|n|                  // Closure taking a parameter n
format!("{:b}",n)    // Binary string of n
.chars()             // Iterate over the chars
.zip(                // Zip iterator with
  format!("{}",n)    //   Decimal string of n
  .chars().cycle()   //   Cycle over the chars
)
.flat_map(           // Map with the following iterator-returning
                     // function and flatten the result
  |(b,c)|            //   Closure taking the char pairs (b,c)
  if'0'<b{Some(c)    //   If '1' then return an iterator yielding c
  else{None}         //   Else return an empty iterator
)
.collect::<String>() // Evaluate into a string

```

# Answer
> 1 votes
# C (gcc), 79 bytes

```
V;M;r(n){M<=V?r(n/10?:(M*=2,V)),M/=2,M&V&&putchar(n%10+48):0;}f(n){M=1;r(V=n);}

```

Try it online!

Generates the nth number

# Answer
> 1 votes
# Bash \+ GNU utilities, 87 bytes

```
x=$1$1$1$1
for((b=`dc<<<2o$1p`;b;)){ [ $[b] = $b ]&&printf ${x:0:1};x=${x:1};b=${b:1};}

```

Try the test suite online!

Input \\$n\\$ is passed as an argument, and the \\$n^\text{th}\\$ number in the sequence is output on stdout.

How it works:

`x` is set to 4 copies of the input in a row, which is more than enough digits to match the binary equivalent of the input. (A number in base 2 can never be longer than 4 times its representation in base 10, since \\$\log\_2(10)\<4.\\$)

`b` is initialized to the binary representation of the input.

The for loop repeats the following as long as `b` still has at least one `1` in it:

* If `b` doesn't start with a `0`, then the first character in `x` is printed.
* The first character is chopped off of `x` and `b`.

The golfiest trick is probably the way I check to see if `b` starts with a `1`: the expression `$[b]` means: `b` evaluated as an arithmetic expression. This will omit any initial 0s (except that it will keep a final 0 if all the characters in `b` are `0`). So `[ $[b] = b ]` is true iff `b` either starts with a `1` or is equal to `"0"`. But `b` can't equal `"0"` since the loop termination condition would have been true in that case, and the loop would have ended already.

# Answer
> 1 votes
# Ruby, 58 bytes

```
->n{a=n.digits 2;([n]*n*m='').chars{|x|m<<x*(a.pop||0)};m}

```

Try it online!

# Answer
> 1 votes
# Java (JDK), 108 bytes

```
n->{var s=""+n;for(int b=n.highestOneBit(n),i=0;b>0;b/=2,i++)if((b&n)>0)System.out.print((s+=s).charAt(i));}

```

Try it online!

## Credits

* -7 bytes thanks to Kevin Cruijssen

# Answer
> 1 votes
# Husk, 5 bytes

```
fḋ¹¢s

```

Try it online! This function works according to option 1, outputting the term as a string.

### Explanation

```
fḋ¹¢s  (Let X denote the argument.)
f      Select the elements of
    s    the string representing X,
   ¢    cycled infinitely, corresponding to truthy values of
 ḋ¹     the binary digits of X.

```

# Answer
> 1 votes
# Japt, 8 bytes

Came up with a few approaches but couldn't do better than 8 bytes.

With output as a digit array:

```
¤¬ðÍ£sgX

```

Try it

With output as a string:

```
¤ËÍçEgUs

```

Try it

```
¤¬ðÍ£sgX     :Implicit input of integer U
¤            :To binary string
 ¬           :Split
  ð          :Truthy indices when
   Í         :  Converted to integer
    £        :Map each X
     s       :  Convert U to string
      gX     :  Get digit at index X

```

```
¤ËÍçEgUì     :Implicit input of integer U
¤            :To binary string
 Ë           :Map each D at index E
  Í          :  Convert D to integer
   ç         :  That many times repeat
    Eg       :  Index E into
      Uì     :  Digit array of U

```

# Answer
> 1 votes
# Vyxal `s`, 17 bytes

```
₌SbL:‟*Ẏf?bZ't;vh

```

Try it Online!

A mess.

# Answer
> 1 votes
# AWK, 89 bytes

```
{for(f=b=1;$1>=b;e=e$1)c[d++]=and($1,b)/(b*=2);for(;d--;f++)c[d]?g=g substr(e,f,1):0}$0=g

```

Try it online!

Not that short, but AWK doesn't have a `print` format to generate binary strings from integers, so it has to iterate to get that info...

At a high level, one loop uses bitwise `and` operations with a single bit moved one position to the left each time to built an array of "binary" settings. It also builds up a string composed of multiple copies of the `N` number while it's looping. AWK doesn't have a nice `string*number` operator either.

Then the second loop works backwards through that array and for each entry which is `1`, it appends the appropriate character to a "results" accumulator.

The final step just prints the accumulated string.

```
# Loop 1, build the "binary" array and string of duplicated "N" characters
for(f=b=1;$1>=b;e=e$1)c[d++]=and($1,b)/(b*=2);
   (f=b=1;                                     # Loop init, "f" is used in loop #2
          $1>=b;                               # Exit test, goes until bit check > N
                e=e$1)                         # End of loop, build "N dup string
                      c[d++]=and($1,b)/(b*=2); # Body, does a couple of things...
                                               # d++ : increment bit position
                                               # and($1,b) : extract bit
                                               # /(b*=2) : normalize, then shift bit
                                               # c[d++]= : add to "binary" array

# Loop 2, accumulate chars associated with set bits
for(;d--;f++)c[d]?g=g substr(e,f,1):0
     d--;                             # Exit test, when all bits checked stop
         f++)                         # End of loop, increment char pos in "N" dup str
             c[d]?                 :  # Ternary, code runs if bit is set
                  g=g substr(e,f,1)   # Append current char to accumulator
                                    0 # No-op "else" from ternary

# Print the result
$0=g   # Typical AWK golf trick, assign "$0" to what you want to print w/o code block

```

# Answer
> 0 votes
# Charcoal, 11 bytes

```
⭆↨Ｉθ²⎇ι§θκω

```

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

```
   θ        Input as a string
  Ｉ         Cast to integer
 ↨  ²       Convert to base `2`
⭆           Map over digits
      ι     Current digit
     ⎇      If non-zero
        θ   Input as a string
       §    Cyclically indexed by
         κ  Current index
          ω Else empty string

```

# Answer
> 0 votes
# 05AB1E, 6 bytes

The `Ï<` ruins the consecutive word `bāsè`... (If you don't get it, the hex code 05AB1E converted to base64 would result in `base`.)

```
bāsÏ<è

```

Try it online!

# Explanation

```
b      To base 2
 ā     Length-range to 1
  s    Prepend
   Ï   Keep all that's truthy
    <  -1 due to 0-based indexing ... that's terrible!
     è Modular Indexing

```

---
Tags: code-golf, number, sequence, integer, binary
---


title: Brainf*** to tinyBF converter

text:
# Question
Title: Brainf*** to tinyBF converter
*You don't need to know these languages to participate. All necessary information has been provided in this question.*

You should write a program or function which given a brainfuck (BF) code as input outputs its tinyBF equivalent.

BF has 8 instructions characters: `+-><[],.` and tinyBF has 4: `=+>|`. Converting works the following way: starting from the beginning of the BF code each symbol is replaced by on of its two tinyBF counterparts based on the number of `=` signs in the tinyBF code until that point (i.e. `=` behaves like a toggle switch).

The converter table (with columns: Brainfuck symbol; tinyBF symbol(s) when ther are even `=`'s before; tinyBF symbol(s) when ther are odd `=`'s before):

```
BF   even    odd

+      +      =+
-     =+       +
>      >      =>
<     =>       >
[      |      =|
]     =|       |
.     ==      ==
,    |=|    =|=|

```

(This creates an almost unique tinyBF code. The only conflict occurs if the BF code contains a `[]` which is generally unused as it creates an infinite void loop.)

## Input

* An at least 1 byte long valid brainfuck program containing only the characters `+-><[],.`
* Guaranteed not to contain the string `[]`
* Trailing newline is optional.

## Output

* A tinyBF program.
* Trailing newline is optional.

## Examples

You can convert any BF program to tinyBF with this (1440 byte long) converter (see the Edit section for a small deviation).

```
Format is Input into Output

++-  into  ++=+
,[.,]  into  |=||==|=|=| or |=|=|==|=|| (both is acceptable check the Edit section)
>++.--.[<]+-,  into  >++===++===|=>|=+=+=|=|
>++-+++++++[<+++++++++>-]<.  into  >++=+=+++++++|=>=+++++++++>=+|>==

```

## Edit

As @Jakube pointed out in the official tinyBF converter in the equivalents of the `,` BF instruction (`|=|` and `=|=|`) the last `=` signs aren't counted towards the toggle state. Both the official and mine interpretations are acceptable but you have to choose one.

This is code-golf so the shortest entry wins.

# Answer
> 4 votes
# CJam, 50 bytes

```
l{"..+-><[],"#2mdT2$@T?:T=L'=?"== + > | |=|"S/@=}/

```

Try one example or all of them online.

### Explanation

The magic is in the mapping! Looking up each operator's index in a carefully ordered yet simple string produces three useful pieces of information at once: whether the operator is directionless (index == 0), the direction the operator requires (index mod 2), and the index of the output operator (index / 2).

Using that handy mapping, it's a simple case of looping through each input operator and producing a direction swap operator if the direction needs to be changed, updating the direction, and producing the output operator.

```
l                   "Read a line of input.";
{                   "For each character of input:";
  "..+-><[],"#        "Map the character:
                        '.' -> 0  |
                        '+' -> 2  |  '-' -> 3
                        '>' -> 4  |  '<' -> 5
                        '[' -> 6  |  ']' -> 7
                        ',' -> 8  |            ";
  2md                 "Calculate the quotient and remainder of the mapping
                       divided by 2.";
  T2$@T?:T            "If the the mapping is nonzero (not '.'), set the
                       direction after this operator to the remainder above.
                       Otherwise ('.'), don't change the direction.";
  =L'=?               "If the direction before this operator is equal to the
                       direction after, produce an empty string. Otherwise,
                       produce the direction switch operator, '='.";
  "== + > | |=|"S/@=  "Map the previous mapping divided by 2 to an operator:
                         0 ('.')      -> '=='
                         1 ('+', '-') -> '+'
                         2 ('>', '<') -> '>'
                         3 ('[', ']') -> '|'
                         4 (',')      -> '|=|' ";
}/

```

# Answer
> 14 votes
# Extended BrainFuck 276 bytes

(not counting uneccesary linefeeds)

```
{a<<]>&c}{b<<-]<[->}{c]<]>[>[}{d 4+[-<}3>4->3->5->-->>&d 4+>]<[-<
4+<3+<4+<8+4>]<[<]<<,[>3+&d 6->]+<-[-[-[-[14-[--[>&d 6->]+<+[--[[
-]>[-&c>.&b>>.<.<+&a->>.<.&b>.<&a->>.>>.3<&b 4>.4<&a 4>.3<&b+>>.>
>.6<]>]<]>[-3>..3<&c 3>.<<&b+>>.>.3<&a>>.<.>.<.&b+>.>.<.<&a->>.>.
<<&b 3>.5<]>]<,]

```

How to compile and run:

```
beef ebf.bf < tinybf.ebf > tinybf.bf
beef tinybf.bf < source.bf > source.tbf

```

It will work with any wrapping BF interpreter that uses/support 0 as EOF. Actual EBF source before golfing:

```
:i:f:o:p:e:a:g
$p ~"|=+>"<[<]@o
$i,( $f+++++++(-$i------)+$i-; +
     ($i-; ,
       ($i-; -
         ($i-; .
           ($i--------------; <
             ($i--; >
               ($f++++(-$i------)+$i+; [
                 ($i--; ]
                   ((-) $f(-) )
                      $f ( $o[$p.$f-]<[@f-$e.$p.$o+$i] ) ; ]
                  ) $f ( $o[-$e.$p.$f-]<[@f-$p.$i] ) ; [
                ) $f ( $o[-$e.$g.$f-]<[@f-$g.$i] ) ; >
              ) $f ( $o[$g.$f-]<[@f-$o+$e.$g.$i] ) ; <
            ) $f (- $e.. ) ; .
          ) $f ( $o[$a.$f-]<[@f-$o+$e.$a.$i] ) ; -
        ) $f ( $o[$e.$p.$e.$p.$f-]<[@f-$o+$p.$e.$p.$i] ) ; ,
     ) $f ( $o[-$e.$a.$f-]<[@f-$a.$i] ) ; +
$i,)

```

# BrainFuck 404 bytes

This is the trimmed output of the compiled EBF.

```
>>>---->--->----->-->>++++[-<++++>]<[-<++++<+++<++++<++++++++>>>>]<
[<]<<,[>+++++++[-<------>]+<-[-[-[-[--------------[--[>++++[-<-----
->]+<+[--[[-]>[-]<]>[>[>.<<-]<[->>>.<.<+<<]>]<]>[>[->>.<.<<-]<[->>.
<<<]>]<]>[>[->>.>>.<<<<<-]<[->>>>>.<<<<<<]>]<]>[>[>>>>.<<<<<-]<[->+
>>.>>.<<<<<<]>]<]>[->>>..<<<]<]>[>[>>>.<<<<-]<[->+>>.>.<<<<<]>]<]>[
>[>>.<.>.<.<<-]<[->+>.>.<.<<<]>]<]>[>[->>.>.<<<<-]<[->>>>.<<<<<]>]<,]

```

# Answer
> 2 votes
# TinyBF\***, 558 bytes

Don't credit me for this, this is the TinyBF version of @Sylwester's BrainF\*** answer (I used his code to convert his code into this code, :P). I just felt the need to put this answer up.

```
>>>=++++=>=+++=>=+++++=>=++=>>++++|=+>=++++>=|>=|=+>=++++=>=+++=>=++++=>=+++++++
+>>>>=|>=|=>|>>=|=|=|>+++++++|=+>++++++=>=|=+=>+=|=+=|=+=|=+=|=++++++++++++++=|=
++=|>++++|=+>++++++=>=|=+=>=+|=++=||=+|=>|=+|>|=>|>|>===>>+|>=|=+=>>>===>==>=+=>
>|=>=|>|=>|>|=+=>>===>==>>+|>=|=+=>>===>>>|=>=|>|=>|>|=+=>>==>>===>>>>>+|>=|=+=>
>>>>===>>>>>>|=>=|>|=>|>|>>>>===>>>>>+|>=|=+=>+>>==>>===>>>>>>|=>=|>|=>|=+=>>>==
===>>>|>|=>|>|>>>===>>>>+|>=|=+=>+>>==>===>>>>>|=>=|>|=>|>|>>===>===>===>==>>+|>
=|=+=>+>==>===>==>>>|=>=|>|=>|>|=+=>>==>===>>>>+|>=|=+=>>>>===>>>>>|=>=|>=|=||

```

# Answer
> 1 votes
# Perl, ~~244~~ ~~241~~ ~~226~~ 217 bytes

```
open(B,$ARGV[0]);%e=qw(+ + - =+ > > < => [ | ] =| . == , |=|);%o=qw(+ =+ - + > => < > [ =| ] | . == , =|=|);$q=0;while(<B>){$p='';@c=split('');foreach$c(@c){if($q%2>0){$p.=$o{$c}}else{$p.=$e{$c};}$q=$p=~/=/g;}print$p}

```

Works on all cases. Run with `perl file.pl [filename]` where `file.pl` is the name of the program, and `[filename]` is the name of the BF file.
**Changes**

* Saved 3 bytes by using `split('')` instead of `split('',$_)`.
* Saved 15 bytes by:
    + Getting rid of `$f=` in front of open (3 bytes)
    + Replacing `if($eo%2==1)` with `if($eo%2>0)` (1 byte)
    + Replacing `$p=$p.` with `$p.=` (2 bytes * 2 times = 4 bytes)
    + Removing trailing newline, as it was optional (5 bytes)
    + Removed `=()` (3 bytes)
* Saved 9 bytes by shortening variable names.

# Answer
> 1 votes
# K, 91 bytes

```
o:0;{:[i:"..+-><[],"?x;t:i!2;t:0];`0::[o=t;"";"="],("==";"+";">";"|";"|=|")@i%2;o::t}',/0:`

```

It's more-or-less a direct port of @Runer112's CJam answer. And it's much longer. Life sucks.

# Answer
> 1 votes
# JavaScript (ES6), 129 bytes

```
b=>[...b].map(x=>p+="=+,+,=>,>,=|,|,==,=|=|,+,=+,>,=>,|,=|,==,|=|".split`,`["+-><[].,".indexOf(x)+p.split`=`.length%2*8],p="")&&p

```

Uses an array of the 16 possibilities (8 characters times 2 parities), and indexes into this. The array is built by splitting a string, which saves 26 bytes over an array.

# Answer
> 0 votes
# Ruby, ~~233~~ 217 bytes

```
p,m,g,l,b,s,d,a,q,f=%w(+ - > < [ ] . , | =)
z=[{p=>p,m=>f+p,g=>g,l=>f+g,b=>q,s=>f+q,d=>f+f,a=>q+f+q},{p=>f+p,m=>p,g=>f+g,l=>g,b=>f+q,s=>q,d=>f+f,a=>f+q+f+q}]
i=0
ARGV[0].each_char{|c|v=z[i%2][c];print v;i+=v.count(f)}

```

An 8-byte improvement on the previous non-esoteric answers!
Saved 16 bytes with the `%w()` syntax

# Answer
> 0 votes
# Ruby, 101 bytes

```
->s{t="";s.chars{|c|t<<((t.count(?=)+i="..+-><[],".index(c))%2<1&&i>0?"":?=)+%w(= + > | |=|)[i/2]};t}

```

Try it online!

Uses the second interpretation of the ambiguous `,` translation rule.

---
Tags: code-golf, brainfuck, conversion
---


title: Remove submatrices

text:
# Question
Title: Remove submatrices
Given two integer matrices `a` and `b`, your challenge is to replace any occurences of `b` in `a` with a matrix of the same size filled with 0s. For example:

```
Given:
a: [ [1, 2, 3],
     [4, 3, 2],
     [3, 5, 4] ]
b: [ [3],
     [2] ]
b occurs once in a:
[ [1, 2, **3**],
  [4, 3, **2**],
  [3, 5, 4] ]
Fill that area with zeroes:
[ [1, 2, 0],
  [4, 3, 0],
  [3, 5, 4] ]
And this is your result!

```

You can assume occurences of `b` will never overlap, but there may be none. `b` will never be larger than `a`, or empty, and will only contain positive integers.

## Testcases

```
[ [1, 2],
  [3, 4] ]
[ [1] ]
=>
[ [0 2],
  [3 4] ]

[ [4, 4, 6, 7],
  [4, 2, 4, 4],
  [7, 3, 4, 2] ]
[ [4, 4],
  [4, 2] ]
=>
[ [0, 0, 6, 7],
  [0, 0, 0, 0],
  [7, 3, 0, 0] ]

[ [1, 2] ]
[ [3, 4] ]
=>
[ [1, 2] ]

[ [1, 2],
  [3, 4] ]
[ [1, 2],
  [3, 4] ]
=>
[ [0, 0],
  [0, 0] ]

[ [1, 2],
  [2, 1] ]
[ [1],
  [2] ]
=>
[ [0, 2],
  [0, 1] ]
(suggested by tsh)

[ [2, 3, 4],
  [3, 2, 3],
  [4, 3, 2] ]
[ [2, 3],
  [3, 2] ]
=>
Undefined behaviour, will not be given (overlap)

```

# Answer
# APL (Dyalog Unicode), 20 bytes

Anonymous infix lambda taking `a` and `b` as left and right argument. Requires 0-based indexing.

```
{0@((⍳⍴⍵)∘.+⍸⍵⍷⍺)⊢⍺}

```

Try it online!

`{``}`dfn; arguments are  and :

`⊢⍺` on `a`,

`0@(``)` put zeros **at** the following positions

`⍵⍷⍺` indicate (Boolean matrix) locations `b` begins (top left corner) in `a`

indices where (list of 2-element lists) those locations are

`(``)∘.+` all summation combinations (gives 3D array of 2-element lists) with:

`⍴⍵` the shape of `b`

all the indices of an array with that shape
> 11 votes

# Answer
# MATLAB/Octave with Image Processing Toolbox/Package, 78 bytes

```
@(A,B)A.*~conv2(reshape(all(im2col(A,size(B))==B(:),1),size(A)-size(B)+1),B>0)

```

**Try it online!**

### Explanation

Consider the example

```
A = [1 2 3
     4 3 2
     3 5 4]
B = [3
     2]

```

`im2col(A,size(B))` takes sliding blocks of `A` with the size of `B` and arranges them as columns:

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

```

`...==B(:)` takes each column in the above matrix and compares it element-wise with `B(:)`, which is `B` linearized into a column vector:

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

```

`all(...,1)`gives `1` for columns that only contain nonzeros:

```
0   0   0   0   1   0

```

`reshape(...,size(A)-size(B)+1)` arranges the results as a matrix, so each position corresponds to one of the original blocks in `A`. This matrix is smaller than `A`, depending on the block size:

```
0   0   1
0   0   0

```

`conv2(...,B>0)` gives the 2D convolution between the above matrix and a matrix of ones the same size as `B`. This has the effect of extending the matrix size to that of `A`, and enlarging each `1` above to a "patch" the same size as `B`:

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

```

`A.*~...` multiplies `A` element-wise by the above matrix negated, which acts as a mask that sets the desired entries to `0`:

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

```
> 8 votes

# Answer
# , 29 27 bytes

```
]*1-[:+/-@,/@(#:i.)@$@[|.E.

```

Try it online!

It took me a while to see this approach.

At first, the problem seems easy, because J has `E.`, which immediately finds the matches by returning a 0-1 matrix with a 1 marking the upper left corner of any match. For example:

```
   (,.1 4) E. i.2 3
0 1 0
0 0 0

locates 1  within 0 1 2
        4         3 4 5

```

In a sense the "hard work" is done, yet going from there to updating squares of the same size as our search target is surprisingly cumbersome.

The trick is to rotate "across" the search target dimension, and then "sum the planes", similar to how we find neighbor counts in the famous APL game of life.

Finally, we multiply the original matrix by the inverse of that result, putting zeros where the ones are and keeping everything else.

The rest is just implementation mechanics.
> 4 votes

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

```
a=>b=>a.map((r,y)=>r.map((c,x)=>c*!b.some((R,Y)=>R.some((C,X)=>!b.some((S,Z)=>S.some((D,W)=>(a[y-Y+Z]||0)[x-X+W]!=D))))))

```

Try it online!
> 2 votes

# Answer
# Charcoal, ~~55~~ 50 bytes

```
ＦＬθＦＬ§θιＦ⁼ηＥ✂θι⁺ιＬη¹✂λκ⁺κＬ§η⁰ＦＬηＦＬ§η⁰§≔§θ⁺ιμ⁺κν⁰Ｉθ

```

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

```
ＦＬθＦＬ§θι

```

Loop over the cells of `a`. (The ones that are too low or to the right won't slice properly below so the resulting submatrix will never equal `b`.)

```
Ｆ⁼ηＥ✂θι⁺ιＬη¹✂λκ⁺κＬ§η⁰

```

If this submatrix of `a` equals `b`...

```
ＦＬηＦＬ§η⁰§≔§θ⁺ιμ⁺κν⁰

```

... then set all of its elements to zero.

```
Ｉθ

```

Output the final matrix.

I tried directly mapping over the matrix and filtering out the values that were part of a submatrix but unfortunately this is a) longer at 68 bytes and b) requires 12 loop variables, when Charcoal only has 11 (`iklmnxprvst`).
> 2 votes

# Answer
# , ~~115~~ 111 bytes

(or **97 bytes** in **≥4.1** by replacing the two instances of `function` with `\`)

```
function(a,b,`~`=which){apply(array(,dim(a)-dim(b)+1)|1~T,1,function(c)if(a[d<-t(c+t(b|1~T))-1]==b)a[d]<<-0);a}

```

Try it online!
> 2 votes

# Answer
# Matlab, 153 bytes

```
c=size(a);
d=size(b);
e=c(1);
f=c(2);
g=d(1);
h=d(2);
for i=1:e-g+1
for j=1:f-h+1
if all(a(i:i+g-1,j:j+h-1)==b,'all')
a(i:i+g-1,j:j+h-1)=0;
end
end
end
a

```

I'm a bit frustrated that I wasn't able to find a vectorized solution, which would be more fitting for a Matlab solution.
> 1 votes

# Answer
# Ruby, 128 bytes

```
->a,b{w=b[0].size;a.size.times{|r|a[r].size.times{|c|a[r,q=b.size].map{|z|z[c,w]}==b&&q.times{|x|w.times{|y|a[r+x][c+y]=0}}}};a}

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6),  ~~114~~  110 bytes

Expects `(matrix)(submatrix)`.

```
m=>s=>m.map((r,y)=>r.map((v,x)=>(g=e=>+s.some((R,Y)=>R.some((V,X)=>eval("(m[y+Y]||0)[x+X]"+e))))`^V`?v:g`=0`))

```

Try it online!

### How?

Let \\$M\\$ be the parent matrix and \\$S\\$ be the submatrix.

Given an expression \\$e\\$ and a reference position \\$(x,y)\\$ in \\$M\\$, the helper function \\$g\\$ walks through all cells \\$(X,Y)\\$ of \\$S\\$ and applies \\$e\\$ to the cell \\$(x+X,y+Y)\\$ in \\$M\\$. It eventually returns \\$1\\$ if any result is \\$\neq 0\\$, or \\$0\\$ otherwise.

```
g = e =>
  +s.some((R, Y) =>
    R.some((V, X) =>
      eval("(m[y+Y]||0)[x+X]" + e)
    )
  )

```

We first invoke \\$g\\$ with the expression `"^V"` to test whether the submatrix at \\$(x,y)\\$ in \\$M\\$ is equal to \\$S\\$. If it is, we invoke \\$g\\$ a second time with the expression `"=0"` to clear the submatrix.
> 1 votes

# Answer
# Core Maude, 310 bytes

```
in linear
mod R is pr INT-MATRIX *(sort IntMatrix to M). op r : M M -> M . op t : Int
Int M M -> Int . var A B C D E : Int . var W X Y Z : M . ceq r((A,B)|-> E ;
X ; Y,Z)= r(Y,Z)if(C,D)|-> E ; W := Z /\ t(A - C,B - D,X,W)=/= 0 . eq r(X,Y)=
X[owise]. ceq t(A,B,X,(C,D)|-> E ; Y)= 0 if X[A + C,B + D]=/= E . endm

```

The result is obtained by reducing the `r` function with the input and pattern matrices, given as `IntMatrix`es, and the output is an `IntMatrix`.

This solution requires that all of the input matrices' entries be non-zero, due to a quirk of `IntMatrix`es: zero entries are omitted in the representation (since zero is the default). This is also true for the output.

### Example Session

```
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ; (0, 2) |-> 3 ;
>     (1, 0) |-> 4 ; (1, 1) |-> 3 ; (1, 2) |-> 2 ;
>     (2, 0) |-> 3 ; (2, 1) |-> 5 ; (2, 2) |-> 4,
>     (0, 0) |-> 3 ;
>     (1, 0) |-> 2
> ) .
result M: 0,0 |-> 1 ; 0,1 |-> 2 ; 1,0 |-> 4 ; 1,1 |-> 3 ; 2,0 |-> 3 ; 2,1 |-> 5
    ; 2,2 |-> 4
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ;
>     (1, 0) |-> 3 ; (1, 1) |-> 4,
>     (0, 0) |-> 1
> ) .
result M: 0,1 |-> 2 ; 1,0 |-> 3 ; 1,1 |-> 4
Maude> red r(
>     (0, 0) |-> 4 ; (0, 1) |-> 4 ; (0, 2) |-> 6 ; (0, 3) |-> 7 ;
>     (1, 0) |-> 4 ; (1, 1) |-> 2 ; (1, 2) |-> 4 ; (1, 3) |-> 4 ;
>     (2, 0) |-> 7 ; (2, 1) |-> 3 ; (2, 2) |-> 4 ; (2, 3) |-> 2 ,
>     (0, 0) |-> 4 ; (0, 1) |-> 4 ;
>     (1, 0) |-> 4 ; (1, 1) |-> 2
> ) .
result M: 0,2 |-> 6 ; 0,3 |-> 7 ; 2,0 |-> 7 ; 2,1 |-> 3
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2,
>     (0, 0) |-> 3 ; (0, 1) |-> 4
> ) .
result M: 0,0 |-> 1 ; 0,1 |-> 2
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ;
>     (1, 0) |-> 3 ; (1, 1) |-> 4,
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ;
>     (1, 0) |-> 3 ; (1, 1) |-> 4
> ) .
result M: zeroMatrix
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ;
>     (1, 0) |-> 2 ; (1, 1) |-> 1,
>     (0, 0) |-> 1 ;
>     (1, 0) |-> 2
> ) .
result M: 0,1 |-> 2 ; 1,1 |-> 1

```

### Ungolfed

```
in linear

mod R is
    pr INT-MATRIX * (sort IntMatrix to M) .

    op r : M M -> M .
    op t : Int Int M M -> Int .

    var A B C D E : Int .
    var W X Y Z : M .

    ceq r((A, B) |-> E ; X ; Y, Z) = r(Y, Z)
        if (C, D) |-> E ; W := Z
        /\ t(A - C, B - D, X, W) =/= 0 .
    eq r(X, Y) = X [owise] .

    ceq t(A, B, X, (C, D) |-> E ; Y) = 0
        if X[A + C, B + D] =/= E .
endm

```

We find an overlap by guess-and-check. We guess a submatrix and pick one entry from the submatrix and one from the pattern with the same value. We compute their offset and then try to find a counter-example to the match (via `t`). If none exists, we remove the submatrix (equivalent to setting it to zero).
> 0 votes

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


# Question
Title: Write the whole of the holed using the unholed
The ASCII characters from decimal code 33 to 126 are:

```
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

Notice that in most fonts, 25 of these characters have "holes" in them: (a genus greater than 0 you might say)

```
#$%&04689@ABDOPQRabdegopq

```

The other 68 "unholed" characters are:

```
!"'()*+,-./12357:;<=>?CEFGHIJKLMNSTUVWXYZ[\]^_`cfhijklmnrstuvwxyz{|}~

```

Your task is to write the shortest program possible using only the unholed characters that outputs each of the holed characters exactly once in any order.

Since Space, Tab and newlines (Line Feed and/or Carriage Return) are empty space they may appear in your program or its output. They still count towards the number of characters. Other ASCII characters may not be used (and certainly not non-ASCII characters).

**Notes**

* You do not have to use all of the unholed characters nor only one of each.
* The output may not contain unholed characters.
* The Whitespace language may be used.
* Output should go to stdout or can go to a file. There should be no input.

**Bonus:** Just for fun, try printing all the unholed characters using the holed characters. I'm skeptical that it can be done in an existing language.

# Answer
# Pyth, 43 35 characters

```
tTFk"*+,-7;=?GHIKVWXYhiklnvwx"C-Ck7

```

Try it here.

Prints the characters in order except that 9 is at the beginning, newline separated.

String contains all characters 7 greater than the ones needed, except that 9 would become @, so it is special cased. Algorithm thanks to @Howard.

**Explanation:**

```
tT                print(10-1)                T=10, t(x)=x-1 if x is an int.
Fk"<string>"      for k in "<string>":
C-Ck7             print(chr(ord(k)-7))       Note that C is overloaded as ord and chr.

```
> 18 votes

# Answer
### GolfScript, 37 36 characters

```
[":=<?)-/! YX[]VIHKx{}|~vih"{25^}/]+

```

Try the code here.

The string contains the forbidden characters xor'ed with 25. Fortunately all characters are mapped to valid ones.
> 24 votes

# Answer
# Brainfuck 119

```
--[------->++<]>-.+.+.+.++++++++++.++++.++.++.+.+++++++.+.+.++.+++++++++++.+.+.+.[------>+<]>--.+.++.+.++.++++++++.+.+.

```
> 22 votes

# Answer
## Bonus - dc, 179 characters

Oh good, another restricted character set challenge where `P` is allowed.

```
6A44469PD684P44D4898PDB99P4008D0BP486B48BPA60BPD096P4A68666P460A0D4P690490AP8084088P6B6AB66P6BBB608P80D4BAAPA046PBAD4P60A6668P480DD96P4A040BBP848BP40DD8D0P46840B6P696B48BP48D64BAP

```

Since `dc` is apparently obscure enough to require explaining (strange to me considering the weird stuff around here!) here's an overview:

It's primarily an RPN calculator with arbitrary-precision arithmetic. But for this challenge, I'm making use of the `P` command, which interprets a number as a series of characters in base 256 and prints them. Examples: `65 P` prints `A` (ASCII code 65). `16706 P` prints `AB` (16706=65\*256+66).

Aside from that, the only other interesting feature is that it recognizes all of the hexadecimal digits `0-9A-F` even when they are not contained in a hexadecimal number. Decimal input is the default, so the input token `999` means `9 hundreds + 9 tens + 9` and `ABC` means `10 hundreds + 11 tens + 12` making it equivalent to `1122`.

The ability to use the digits `ABD` in decimal partially makes up for the inability to use `12357`, and the choice of ordering and grouping does the rest. (If I need some numbers `x`,`y`,`z` and they aren't representable with allowed digits, then I try representing `x*256*256+y*256+z` instead.)

The program can probably be made slightly shorter by using larger groups. I didn't go past 3 bytes per number.
> 20 votes

# Answer
# Bash+coreutils, 56 bytes

```
tr \(-y \!-r<<<'*+,-7;=?GHIKVWXYhiklnvwx'
tr C-F 7-:<<<E

```

As luck would have it, adding 7 to the ascii value of the holed characters yields all unholed characters (with the exception of "9"). So we just do this transformation in reverse, then a similar transformation (subtract 12 from "E") to get the "9".

### Output:

```
#$%&0468@ABDOPQRabdegopq
9

```
> 12 votes

# Answer
## Perl - 47 Bytes (thanks @Dom Hastings for the update!) <br>Perl - 49 Bytes

Edit, 47 bytes:

```
symlink".",':=<?)-/! YX[]VIHKx{}|~vih'^(F^_)x25

```

Original, 49 bytes:

```
symlink".",':=<?)-/! YX[]VIHKx{}|~vih'^chr(25)x25

```

This is pretty much a Perl version of Howard's solution. XORing the string with 25. The output is a file with the name `#$%&04689@ABDOPQRabdegopq`. I got the idea to use `symlink` and the file name as the output format because everything else is banned.

Here's another Perl solution I came up with. It can probably be improved a lot and it is pretty long, so I'm leaving in a readable format for now.

```
until(y/1/1/>32){s//1/}
until(y/1/1/>125+1){
    if(chr(y/1/1/)!~/[!"'()*+,-.\/12357:;<=>?CEFGHIJKLMNSTUVWXYZ[\\\]^_`cfhijklmnrstuvwxyz{|}~]/) {
        symlink".",chr y/1/1/;
    }
    s/^/1/
}

```

This one outputs many files, the name of each one is one of the characters. I couldn't figure out how to append strings without using a forbidden character.

`for`, `while`, `map`, `say`, `print`, `eval`, `s///e`, and any variable name cannot be used (variables start with `@` or `$` in Perl) which made this difficult.

Hopefully file names are okay as an output format because I'm pretty sure every other way to output information uses one of the banned characters.
> 7 votes

# Answer
# MATLAB, 36 bytes

SO CLOSE.... Only 1 byte more than the current winner (isaacg)! Which, on further inspection, already did what I set out to do too. Well, no harm in reinventing the wheel...

I know this is an old challenge, but I only realized that *after* I got interested in it.

```
['*+,-7;=?GHIKVWXYhiklnvwx'-7,57,'']

```

If only I could get MATLAB to understand that I want a string without a separate `''`... suggestions, anyone?
> 5 votes

# Answer
# Brainfuck 303 275

```
++++++++[>+>++>+++>++++>+++++>++++++>+++++++>++++++++>+++++++++>++++++++++>+++++++++++>++++++++++++>+++++++++++++>++++++++++++++>+++++++++++++++>++++++++++++++++<<<<<<<<<<<<<<<<-]>>>>+++.--->----.+.+.++>.>----.++.++.+.->.+.+.-->----.++++>-.+.+.+.-->>+.+.-->----.+.++.+>-.+.+.

```

Brainfuck, the ultimate unholed esoteric language (apart from Whitespace) ;)
> 4 votes

# Answer
# JS - 196 - try it

```
h=(c=!1+[])[1];i=c[2*2];j=(f=[]+{})[1];this[i+'v'+h+'l'](h+'l'+i+'rt('+h+'t'+j+f[2]+'("Iy\x51lJj\\x'+2*2+'1\\x3'+~-1+'Nj\\x'+2*3+'75\x51EFC\x52E\\x3'+3*3+'\x51UVJhYm\x52lZ2\\x3'+3*3+'wc\x51=="))')

```
> 4 votes

# Answer
# GolfScript, 89 characters

```
71 22+,{33+}/]''+'!"\'()*+,-./12357:;<=>?CEFGHIJKLMNSTUVWXYZ[\]^_`cfhijklmnrstuvwxyz{|}'-

```

Simply builds an array of all ASCII characters and subtracts the non-"holed" characters from them.

```
71 22+,  # Builds array of 0..93
{33+}/]  # Converts to 33..126
''+      # Convert ASCII codes to string
'stuff'- # Subtracts "stuff" (the non-holed characters) from the string

```
> 2 votes

# Answer
# Befunge 98 - 69 bytes

```
"()+ijWI=*">:5j2 ,-5_"157:h">:5j2 ,-1_"=>?LMN^_lmn">:5j2 ,+3_"?"1+s <

```

Does it in 3 parts. One where unholed character values differ from holed character by 5. Then the ones that differ by 1, and finally a list of unholed characters that differ by 3 from holed ones. The terminate program instruction in Befunge is "@" (char value 64), so at the end I load "?" (char value 63) add 1 then put that in the code with the instruction 's'.

I could maybe golf it more by consolidating the three

```
>:5j2 ,(differ value)_

```

section, but probably not by much.
> 2 votes

# Answer
# Main - Insomnia, 50

```
FFy~~jF~y<={*n<<ztf>={.f=(tHL~k<yf={*n>Lj(FunLn<j~

```

It outputs:

```
abdegopq04689@ABDOPQR#$%&

```

# Bonus - Insomnia, 268

```
ogeeoddp@poe@ggep@oe@opge@gee@%d@p@gqeo@p@ge@e9de49ed9e4dppe@%e@geee@ge@p%ee@%e@dp@%ep@%ee@%d@%eeee@%e@%ee@%e@geee@%e@gee@ggopop@peo@ggep@p@ge@ggeep@ge@gee@%e@geee@ge@gee@ge@ppoep@%ee@%edep@gepe@ge@%ee@%e@geee@ge@%ee@%%eeoe@ge@pep@%gep@p@%e@%%eep@%e@gee@e%e@oe@%gep@p@

```

It outputs:

```
!"'()*+,-./12357:;<=>?CEFGHIJKLMNSTUVWXYZ[\]^_`cfhijklmnrstuvwxyz{|}~

```

I think it should be possible to reduce the length of the program if the output is rearranged, but I need to modify my search program to do this.

Just to show case another language which is capable of operate with a restricted number of characters. By the way, it can write just about any output with only 3 unique characters in the source.

Currently, this is the only language that can do both the main challenge and the bonus among all the existing answers.

**Insomnia Interpreter**.
> 2 votes

# Answer
# Befunge 98 - 46 bytes

Befunge-ified version of isaacg's Pyth entry:

```
"xwvnlkihYXWVKIHG?=;7-,+*">:5j2 ,-7_"?"1+:,s <

```
> 1 votes

# Answer
# JavaScript 240 228

Initial submission:

`z=(!1+"")[1];y=(!!1+"")[3];x={}+"";w=x[1];v=x[2];u=z+"t"+w+v;1[_="c\157nstruct\157r"][_](z+'l'+y+'rt('+u+'("Iy\x51lJj"+'+(t=u+'("\x51\x51==")')+'+'+u+'("M"+'+t+'+"==")+"Nj"+'+u+'("Zw==")+"5\x51EFC\x52E\71\x51UVJhYm\x52lZ2\71wc\x51=="))')()`

Now, this is a great start, here's how it breaks down...

```
z=(!1+"")[1];        // assigns "a" to z, !1+"" === "false"
y=(!!1+"")[3];       // assigns "e" to y, !!1 === "true"
x={}+"";             // assigns "[object Object]" to x
w=x[1];v=x[2]        // assigns "o" to w, and "b" to v
u=z+"t"+w+v;         // creates the mystical "atob" command, yes, I'm gonna use it!
1[_="c\157nstruct\157r"][_] // sets up the primitive to a number object... this acts similar to the "window" primitive object so that I can play off functions...
z+'l'+y+'rt(         // starts creating an alert call
'+u+'("Iy\x51lJj"+'+(t=u+'("\x51\x51==")')+'+'+u+'("M"+'+t+'+"==")+"Nj"+'+u+'("Zw==")+"5\x51EFC\x52E\71\x51UVJhYm\x52lZ2\71wc\x51=="))')()
// Above line abuses atob command with a couple of nested instances of the command, also using hex and octal equivalents of characters

```

And then I thought... "There must be a simpler way..." and there is...

Revised submission: `z=(!1+"")[1];y=(!!1+"")[3];x={}+"";w=x[1];v=x[2];u=z+"t"+w+v;this[y+"v"+z+"l"](z+'l'+y+'rt('+u+'("Iy\x51lJj"+'+(t=u+'("\x51\x51==")')+'+'+u+'("M"+'+t+'+"==")+"Nj"+'+u+'("Zw==")+"5\x51EFC\x52E\71\x51UVJhYm\x52lZ2\71wc\x51=="))')`

Seeing I can use `eval` (by piecing it together, inspiration from @bebe; which is a lot quicker than using the `constructor` of a `constructor` of a `number`... ) I drilled it down to 228... I know it may not win this particular Golf Challenge, but this is just my way of showing how much you can abuse JavaScript, and still get the desired result...
> 1 votes

# Answer
# Japt, 33 bytes

```
7+2+"*+,-7;=?GHIKVWXYhiklnvwx"c-7

```

Try it online!

Same algorithm as isaacg's Pyth submission, just happens to be shorter in Japt.

### How it works

```
7+2+"*+,-7;=?GHIKVWXYhiklnvwx"c-7

7+2           Obviously the number 9
    "..."c-7  Apply -7 on each char's charcode of this string
   +          String concatenation

```

Yes, it's JS, which is one of the most abusable languages, just shorter (and you don't need `alert` or `console.log` here).
> 1 votes

# Answer
# Vyxal `s`, 33 bytes

```
`*+,-7;=?GHIKVWXYhiklnvwx`C7-57JC

```

Try it Online! Uses the same (independently discovered) trick of subtracting 7 and putting a 9 on the end.
> 1 votes

# Answer
# PHP, 59 bytes

```
<?='MMMMMMMMMM:::::::::::::::'^"nihk}y{ut\r{x~ujkh[X^_]UJK";

```

Try it online!

## Explanation

Utilises the string-XOR operator (`^`) to build the desired string from non-holed letters, output via `<?=`.

Verification for 59 bytes.
> 0 votes

# Answer
# Perl 5, 72 bytes

```
*_=*~;("*,*E'syswrit\LE"^icx)->(uc,':=<?)-/! YX[]VIHKx{}|~vih'^(F^_)x25)

```

Try it online!

## Explanation

I know this is longer than the existing Perl answer, but this outputs using STDOUT, rather than a filename.

`*_=*~` aliases the `~` variables (`@`, `%`, and `$`) into `_`, meaning that `$*` (which is `STDOUT` by default) is now in `$_`, which we can access using `uc` (which returns `$_` by default if no arguments are passed). Next the string `CORE::syswrite` is built from a combination of the stringwise-XOR of the two strings and the in-line lowercase modifier (`\L`) of `E`, which is then called as a function `->(`...`)` with the arguments `STDOUT` (from `uc`) and the desired string, also built via stringwise-XOR (copied from @hmatt1's answer and amended to to save bytes using more stringwise-XOR).
> 0 votes

# Answer
# PICO-8, 196 bytes

```
c=77+2?"\35\37\52\57\111\112\113\71"..chr(33+3)..chr(31+7)..chr(32*2)..chr(72-7)..chr(71-5)..chr(71-3)..chr(71-2)..chr(c)..chr(c+1)..chr(c+2)..chr(75+22)..chr(75+23)..chr(c+21)..chr(57*2)..2*13*31

```

More variables like `c` might reduce size, not in the mood to try more at the moment.
> 0 votes

---
Tags: code-golf, restricted-source
---


# Question
Title: Bird's Algorithm for Computing Determinants
There is a division-free algorithm for computing determinants published by R.S.Bird in 2011 that uses only matrix multiplications. Given a \\$n×n\\$ matrix \\$X\\$, the matrix \\$Y=μ(X)\\$ is another \\$n×n\\$ matrix which entries are given by

$$Y\_{i,j} = \begin{cases} 0 & \text{ if } j \< i \\ X\_{i,j} & \text{ if } j \> i \\ -(X\_{i+1,i+1} + X\_{i+2,i+2} + \cdots + X\_{n,n}) & \text{ if } j = i \end{cases}$$

Thus entries of \\$X\\$ below the diagonal are made zero, those above the diagonal are left unchanged, and each diagonal entry is replaced by the negated sum of the elements in the diagonal below it. Note that \\$Y\_{n,n} = 0\\$.

Define the operation \\$A⊗X\\$ between two \\$n×n\\$ matrices \\$A\\$ and \\$X\\$ as $$A⊗X=-μ(X) \cdot A,$$ where \\$\cdot\\$ denotes matrix multiplication.

Now, to obtain \\$\det A\\$, the determinant of \\$A\\$, compute

$$A⊗(A⊗(A⊗(...⊗A)))$$

where the operation \\$⊗\\$ is applied \\$n-1\\$ times. The resulting matrix is everywhere zero except for its leading entry, which equals \\$\det A\\$.

## Example

$$A=\left\[\begin{array}{rrr}-2 & -4 & -1 \\0 & 1 & 3 \\\-2 & 3 & 1 \\\end{array}\right\]$$ $$\mu(A)=\left\[\begin{array}{rrr}-2 & -4 & -1 \\0 & -1 & 3 \\0 & 0 & 0 \\\end{array}\right\]$$ $$B=A⊗A=-\mu(A)\cdot A= \left\[\begin{array}{rrr}-6 & -1 & 11 \\6 & -8 & 0 \\0 & 0 & 0 \\\end{array}\right\]$$ $$\mu(B)=\left\[\begin{array}{rrr}8 & -1 & 11 \\0 & 0 & 0 \\0 & 0 & 0 \\\end{array}\right\]$$ $$A⊗(A⊗A)=A⊗B=-\mu(B)\cdot A=\left\[\begin{array}{rrr}38 & 0 & 0 \\0 & 0 & 0 \\0 & 0 & 0 \\\end{array}\right\]$$ $$\det A=38$$

# Challenge

Implement Bird's algorithm for computing determinants. For a given input \\$A\\$ of size \\$n \> 1\\$, your program must output the intermediate steps \\$A⊗A\\$, \\$A⊗(A⊗A)\\$, and so on, with \\$n-1\\$ applications of \\$⊗\\$. Standard code-golf rules apply. The shortest code in bytes wins.

## Test Cases

```
A:  [[0,3,1],[0,2,1],[0,2,1]]
A⊗A:    [[0,1,-1],[0,0,0],[0,0,0]]
A⊗A⊗A:  [[0,0,0],[0,0,0],[0,0,0]]

A:  [[0,3,-1],[3,0,-2],[-2,-3,0]]
A⊗A:    [[-11,-3,6],[-4,-6,0],[0,0,0]]
A⊗A⊗A:  [[21,0,0],[0,0,0],[0,0,0]]

A:  [[3,1,0],[-2,1,-2],[3,-1,-2]]
A⊗A:    [[-1,-2,2],[10,-4,0],[0,0,0]]
A⊗A⊗A:  [[-22,0,0],[0,0,0],[0,0,0]]

A:  [[2,3,3,2],[-2,-2,2,0],[-3,-3,1,2],[-3,3,-3,0]]
A⊗A:    [[19,6,-6,-8],[4,4,0,-4],[6,-6,6,0],[0,0,0,0]]
A⊗A⊗A:  [[-10,48,0,32],[-24,0,0,0],[0,0,0,0],[0,0,0,0]]
A⊗A⊗A⊗A:        [[192,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

A:  [[3,-2,2,0],[0,2,-2,2],[0,2,-3,0],[2,0,3,-2]]
A⊗A:    [[-9,6,-4,4],[-4,-6,-2,-6],[0,-4,6,0],[0,0,0,0]]
A⊗A⊗A:  [[-8,-4,-12,-4],[12,16,0,0],[0,0,0,0],[0,0,0,0]]
A⊗A⊗A⊗A:        [[56,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

A:  [[-3,-1,0,0],[-1,2,3,2],[3,0,-3,0],[2,0,2,-3]]
A⊗A:    [[11,6,3,2],[-7,-12,-13,-6],[-9,0,9,0],[0,0,0,0]]
A⊗A⊗A:  [[2,-9,-13,-6],[42,18,0,0],[0,0,0,0],[0,0,0,0]]
A⊗A⊗A⊗A:        [[-12,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

```

# Answer
> 10 votes
# K (ngn/k), <sup>~~43~~</sup> 41 bytes

```
{{+/'y*/:(u*|+\|+/x*u)-x*++\u:=#x}\x:\:x}

```

Try it online!

Brutally golfed by ngn.

-2 bytes because it is allowed to output starting with A itself.

```
input: matrix A with size n * n

{{...}\x:\:x}    scan over the list of n copies of A
{...}            inner fn: x is running matrix, y is A
u:=#x            u: identity matrix of size n
x*++\            x * transpose of row-wise cumsum of u
                 (keep upper-triangular part of x)
(...)-           subtract the above from...
+/x*u            diagonal entries of x as a flat list
u*|+\|           cumsum in reverse, placed back on the diagonal
                 the subtraction gives -mu(x)
+/'y*/:          backwards matrix product with A

```

---

# K (ngn/k), 62 bytes

```
{1_(#1_x){+/'@[;;:;]'[-y*|\'=#y;!#y;|0,+\|1_y@'!#y]*\:x}[x]\x}

```

Try it online!

### How it works

The first time actually using ternary each (given a ternary function and three input lists, map over the triples) in code golf. It works so well that I can't think of any other way to do the job.

```
input: matrix A

{1_(#1_x){f}[x]\x}    repeat applying curried function f[A] to A
                      (size of A - 1) times, and then remove the first item

f:{+/'bigThingOnY*\:x}    matrix multiply -mu(y) with x, where
                          y is the current running matrix and x is original A

bigThingOnY: @[;;:;]'[-y*|\'=#y;!#y;|0,+\|1_y@'!#y]
@[;;:;]'[u;v;w]    ternary amend each; for each row in u and each number in
                   v and w, replace v-th value in u with w
u:-y*|\'=#y    negation of y, with all entries below diagonal set to 0
v:!#y          indices of y (when zipped, overwrites diagonal entries)
w:|0,+\|1_y@'!#y    diagonal of y, remove 1st, reverse, cumsum,
                    prepend zero, and reverse back

```

# Answer
> 7 votes
# , ~~113~~ ~~109~~ ~~103~~ ~~96~~ 95 bytes

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

*-4 bytes and another -7 thanks to @Dominic van Essen.*

```
function(A,B=A)for(i in 2:nrow(A))B=print((diag(sum(b<-diag(B))-cumsum(b))-B*upper.tri(B))%*%A)

```

Try it online!

Straightforward approach.

The terms on the diagonal are calculated as `cumsum-sum`.

---

Solution shorter for R\>=4.1, by @Dominic van Essen again.

### , 97 bytes

Or **\>=4.1, 83 bytes** by replacing two `function` appearances with `\`s.

```
function(A,B=A)Map(function(i)B<<-(diag(sum(b<-diag(B))-cumsum(b))-B*upper.tri(B))%*%A,2:nrow(A))

```

Try it online!

# Answer
> 7 votes
# Python 3 \+ numpy, 117, 99, 97, 91, 89(@Dingus), 88 bytes

```
from numpy import*
def f(M):
 N=M;T=triu(M==M)
 for _ in M:N=T@N[T&T.T,print(N)]*M-T*N@M

```

Try it online!

Old version

Old version

Old version

Old version

Old version

# Detailed explanation

(refers to the latest and greatest versison (88 bytes))

We start with a sizeable upfront investment to create auxiliary matrix T which is just an upper triangular mask.

T is then used

* to extract the upper triangle of other matrices (obvious),
* to form another mask for extraction of the diagonal (Still rather obvious by and-ing with its transpose `T&T.T`) and
* to do the cumsum: matrix-vector multiplication Tv with a triangular matrix of ones yields the cumsum of v. Conveniently, we can choose between left-to-right and right-to-left summmation by using upper or lower triangles.

To avoid having to reinsert the cumsum into the diagonal we utilise the fact that matrix-matrix multiplication DM with a diagonal matrix D is the same as python style broadcasted pointwise multiplication with the diagonal reshaped into a column.

Extracting and reshaping the diagonal is done in one indexing operation `N[T&T.T,print(N)]`. The purpose of placing the print statement in this particular spot is that we can make good use of its return value, `None`. `None` as an index inserts a new axis which here has the effect of creating a column instead of a row.

# Avoiding explicit import, 84 bytes

```
def f(M):
 N=M;T=(M==M).cumsum(1);T=T>=T.T
 for _ in M:N=T@N[T&T.T,print(N)]*M-T*N@M

```

Try it online!

Bypassing the call to `triu` the last reference to the toplevel numpy namespace has been removed; the import statement is therefore no longer required. Feels a bit ugly to me but seems to be legal.

# Answer
> 3 votes
# JavaScript (ES6), 121 bytes

Essentially the same as below, but returns an array of \\$n\\$ matrices, the first one being the input matrix.

```
A=>A.map((_,i)=>m=i?m.map((r,y)=>r.map((_,x)=>r.reduce((q,v,k)=>y>k?q:m.map((r,z)=>v-=y<k|z<k?0:r[z])|q-A[k][x]*v,0))):A)

```

Try it online!

---

# JavaScript (ES6),  ~~132 128~~  126 bytes

A naive implementation of Bird's algorithm. Returns an array of \\$n-1\\$ matrices.

```
A=>A.slice(1).map(_=>m=m.map((r,y)=>r.map((_,x)=>r.reduce((q,v,k)=>y>k?q:m.map((r,z)=>v-=y<k|z<k?0:r[z])|q-A[k][x]*v,0))),m=A)

```

Try it online!

### Commented

```
A =>                        // A[] = input matrix of size n x n
A.slice(1).map(_ =>         // repeat n - 1 times:
  m =                       //   update m[]
  m.map((r, y) =>           //   for each row r[] at position y in m[]:
    r.map((_, x) =>         //     for each value at position x in r[]:
      r.reduce((q, v, k) => //       for each value v at position k in r[],
                            //       using q as an accumulator:
        y > k ?             //         if y is greater than k:
          q                 //           leave q unchanged
        :                   //         else:
          m.map((r, z) =>   //           for each row r[] at position z in m[]:
            v -=            //             subtract from v:
              y < k |       //               if y is less than k
              z < k ?       //               or z is less than k:
                0           //                 leave v unchanged
              :             //               else:
                r[z]        //                 subtract r[z] = m[z][z]
          ) |               //           end of map()
          q - A[k][x] * v,  //           subtract A[k][x] * v from q
        0                   //         start with q = 0
      )                     //       end of reduce()
    )                       //     end of map()
  ),                        //   end of map()
  m = A                     //   start with m[] = A[]
)                           // end of map()

```

# Answer
> 3 votes
# , 67 bytes

```
1}.(+/ .*~0-]((*0+/\"1@,~1&}.)+]*$@[$[:(-+/\.)*&,)=@i.@#)^:(<@#@])~

```

Try it online!

`1} …^:(<@#@])` repeat `n-1` times, returning the intermediate results. `=@i.@#` identity matrix. `]*$@[$[:(-+/\.)*&,` running sum of the diagonal. `(*0+/\"1@,~1&}.)` everything on the right of the diagonal stays the same. `+/ .*~0-` matrix multiplication of the negative with the original matrix.

# Answer
> 2 votes
# Lua (LuaJIT), ~~451~~ 392 bytes

```
function det(A)
local n,Y,X,y,yl,x=#A,{},{}
for i=1,n do x={} for j=1,n do x[#x+1]=A[i][j] end Y[#Y+1],X[#X+1]={},x end
for l=1,n-1 do
  o(l,X)
  for i=1,n do for j=1,n do Y[i][j]=0 end end
  for i=n,1,-1 do for j=n,i,-1 do
    y = j>i and -X[i][j] or (i==n and 0 or yl+X[i+1][i+1])
    yl = i==j and y or yl
    for k=1,n do Y[i][k]=Y[i][k]+y*A[j][k] end
  end end
  Y,X=X,Y
end
o(n,X)
end

```

Try it online!

Old version

# Answer
> 2 votes
# APL (Dyalog Extended), ~~62~~ 38 bytes

```
{-⍺+.×⍨(+\-+/)@(∘.=⍨⍳∘≢)⍵×∘.≤⍨⍳≢⍵}\≢⍴⊂

```

Try it online!

Breaking from right to left:

1. `≢⍴⊂` : \\$\[A,A,\cdots,A\]\\$ (produces \\$n\\$ copies of input);
2. `{...}\` : \\$\[A,A⊗A,A⊗(A⊗A),\cdots\]\\$ (`{...}` implements \\$⊗\\$);
3. `⍵×∘.≤⍨⍳≢⍵`: upper triangular matrix;
4. `(+\-+/)@(∘.=⍨⍳∘≢)` : replace diagonal by the negated sum. Thus, `(+\-+/)@(∘.=⍨⍳∘≢)⍵×∘.≤⍨⍳≢⍵` is \\$\mu(X)\\$. `(+\-+/)` is a very nice trick to compute the new diagonal, using a *train*: `(+\diag)-(+/diag)`;
5. `-⍺+.×⍨...`: \\$-\mu(X)\cdot A=A⊗X\\$.

Many thanks to @rak1507, @Adám and @Marshall for this nice improvement!

```
{((⌽0,+\¯1↓⌽1 1⍉⍵)(×⍤0 1)⍺)-((⍵×(∘.<)⍨(⍳≢⍵))+.×⍺)}\((≢⊢)⍴(⊂⊢))

```

Old version

# Answer
> 1 votes
# Charcoal, 47 bytes

```
≔θηＦ⊖Ｌθ«≔ＥηＥκΣＥθ×⎇⁼πλΣＥη∧›ςλ§ρς∧›πλ±§κπ§ξνη⟦⭆¹η

```

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

```
≔θη

```

Start with the output `X` equal to the input.

```
Ｆ⊖Ｌθ«

```

Repeat `n-1` times.

```
≔ＥηＥκΣＥθ×...§ξνη

```

Matrix multiply `-μ(X)` by `A`.

```
⎇⁼πλΣＥη∧›ςλ§ρς∧›πλ±§κπ

```

Dynamically generate `-μ(X)` as part of the multiplication; for elements on the main diagonal, sum the elements further down on the diagonal, otherwise negate or zero the element depending on whether it is above or below the diagonal.

```
⟦⭆¹η

```

Pretty print the latest result. (Normal printing would save 1 byte but be almost impossible to read.)

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

```
a->[x=matrix(n,,i,j,if(i>j,0,i-j,-x[i,j],sum(k=i+1,n,x[k,k])))*a|l<-[2..n=#x=a]]

```

Try it online!

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


title: Determine Circles

text:
# Question
Title: Determine Circles
Giving **`n`**(any amount) of points `(x,y)`. What's the minimum amount of circles required to cross every point given?

## Task

Your program will get `n` (you can have `n` as part of input or use EOF instead) points `(x,y)`.

The points might at same place =\> `(x1,y1) = (x2,y2)` **can happen**

`x` and `y` will be *integer* of range `-10000~10000`, while `n`, if you need it, will be *integer* too.

You should output an integer `A` which represent the minimum amount of circle needed to intersect all of the points. Those circle are not required to intersect each other.

## Explanation

For example: 1, 2 points will need 1 circle only to be sure that the points touch the circles boundary

but 3, 4 points may need 2 circles, or 1 (Determined by where the points are)

```
Basic test cases:
(10,10), (0,5), (0,0), (5,10) => 1 circle
(10,10), (5,5), (0,0), (5,10) => 2 circles
(1,1), (2,2), (5,3), (-1,5), (0,0) => 2
(0,0), (1,1), (2,2), (3,3), (4,4), (5,5) => 3

```

**Line are NOT considered as a circle**

If there are 3 points `(0,0)` `(5,5)` `(10,10)`. Then the answer would be `2` since those 3 points forms a line if you try to force a circle out of it.

## Rules

* Input can be taken in any convenient format.
* Output can be in any convenient format as well. As long as it follow the input-reversed input order.
* Standard Loopholes are forbidden.

## Scoring

Golf your way to the shortest code!

# Answer
> 7 votes
# Haskell, <sup>~~252~~</sup> 203 bytes

```
minimum.map g.permutations.nub
g[]=0
g(p:q:r)=1+g(snd$span(p#q$r!!0)r)
g _=1
(a#b)c d|t<-c!a?j(b!a)=t!!1/=0&&b!d?t?j(c!d)!!1==0
j[x,y]=[x,-y]
[x,y]?[z,t]=[x*z-y*t,x*t+y*z]
(!)=zipWith(-)
import Data.List

```

Try it online!

The relevant function is `minimum.map g.permutations.nub`, which takes a list of points as input (each point as a list `[x,y]`) and returns an integer as output.

This solution uses only integer arithmetic, and therefore does not suffer from accuracy problems stemming from floating point errors.

## How?

Coming soon, after I finish golfing this and convincing myself that the formulas are right.

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

-5 bytes thanks to @att.

```
CircleThrough@#/.{_@{_.,_.}|_Circle:>1,_:>Min[#+Reverse@#&[#0/@Subsets[#][[2;;-2]]]]}&

```

Try it online!

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


# Question
Title: Dynamic Memory Allocator — Shortest Code
Given an integer `n` as input, write a function that dynamically allocates `n` bytes and returns their address.

## Rules

* The allocator must be able to **dynamically** allocate memory at **runtime**.
* It doesn't matter where the memory is allocated to or in what form, as long as it's allocated in a valid location which can be read from and written to.
* Allocated memory locations must be unique and not override or cross already-allocated locations.
* You don't have to write the code in a way such that the memory can be deallocated later.
* It might be obvious, but you are not allowed to use a programming language's or standard library's built in allocator. For example, making a function return the result of `malloc` or `new` is not a valid solution.
* You don't need to worry about out-of-memory errors. Assume big amounts of memory are never allocated.
* Efficiency and speed are not a factor. The only requirement for the challenge is the shortest code, in bytes.
* Standard loopholes are not allowed.

# Answer
> 6 votes
# C (gcc), 51 bytes

```
#include<sys/mman.h>
#define m(n)mmap(0,n,7,33,0,0)

```

Try it online!

-4 bytes thanks to ceilingcat by switching to a function-like macro.

---

`mmap` is a system call which maps a file into virtual address space. On Linux, it can also be used in `MAP_ANONYMOUS` mode, where it doesn't map any file at all, but just "creates" memory out of thin air. The POSIX-portable method would be to open and map the device file `/dev/zero`, which is full of infinite null bytes.

The first argument is a "hint" to the kernel on where to allocate it close to, which can help improve caching. We can just leave it as `NULL` (or `0`, which is golfier) for a basic allocator, though.

The second argument is the size, `n`.

The third argument is the the memory `prot`ection flags of the chunk. `7` is `PROT_READ | PROT_WRITE | PROT_EXEC` to allow all operations.

The fourth argument, `flags`, sets allocation options. `33` is `MAP_ANONYMOUS | MAP_PRIVATE`, which allocates process-private memory without a backing file descriptor. This is practically equivalent to the portable POSIX method which involves opening and mapping `/dev/zero`, but it's much shorter.

The final parameters are the file descriptor (whose value is ignored, because we're using `MAP_ANONYMOUS`), and `offset`, which should be `0` because there's no file.

You can read more about `mmap` in its manual page.

---

# C (gcc) (invalid, but still interesting!), 35 bytes

```
m(int(*f)(),int n){char p[n];f(p);}

```

Try it online!

Using variable-length arrays, it's possible to get dynamic memory allocation on the stack. The memory lives only as long as its scope is running, so it has to be returned using a callback function and only used within that callback (which is not an allowed I/O method, so this answer is invalid). I'm not sure if this would be valid even then, because it might count as using a built in allocator.

# Answer
> 2 votes
# C (gcc), <sup>~~49~~ \\$\cdots\\$ ~~36~~</sup> 34 bytes

```
b[1<<24];m;r;f(n){r=b+m;m+=n;r=r;}

```

Try it online!

*Saved 2 bytes thanks to ceilingcat!!!*

Of course you don't say how much memory is needed, this will work with \\$16\\$\+ million bytes.

### Commented

```
b[1<<24];        // our memory buffer as an array of double words
m;               // declare global variable m to track where free
                 // memory is
r;               // declare r for golfing returning without return
                 // and saving current position before updating m
f(n){            // a function returning an int which will work
                 // as a void* pointer and taking an int
                 // parameter n, this will return 4x the number
                 // of bytes asked for
    r=b+m        // store current position in buffer
    m+=n;        // update where next request for memory will be
    r=r;         // return a pointer for n bytes of memory (actually
                 // n*4 bytes but that'll do for n bytes)
}

```

# Answer
> 1 votes
# C (gcc) on Linux, 45 bytes

```
#include<unistd.h>
int*a(n){return sbrk(n);}

```

Try it online!

The `sbrk` system call on Linux moves the program break by the specified number of bytes, and returns a pointer to the old program break. This has the effect of allocating that many bytes of uninitialized memory and returning a pointer.

# Answer
> 1 votes
# ZX Spectrum (48K model) BASIC, 19 bytes

```
LET r=VAL "65367"-n: CLEAR r-SGN PI

```

65367 is the default RAMTOP for the 48K model (assuming the RAM is not faulty). `CLEAR` sets the new RAMTOP lower by the requested amount, minus one, so that you can use the reserved RAM starting from the value returned in `r` by whatever combination of `PEEK` and `POKE` you desire. Note that while the BASIC has subroutines, they cannot return values, so the return value is assigned to the variable `r`.

Using `VAL "65367"` instead of plain number golfed 2 bytes (the number would be stored in additional 5 bytes otherwise); `SGN PI` instead of `1` similarly golfed 4 bytes; keywords take 1 byte each.

The standard allocator (that we cannot use) is of course `DIM`.

# Answer
> 0 votes
# Python, 28 bytes

```
def m(n):return bytearray(n)

```

# Answer
> 0 votes
# C (gcc), 44 bytes

`char a[~0U],*p=a;char*m(n){return p+=n,p-n;}`

---
Tags: code-golf
---


title: Bijective meets mixed base

text:
# Question
Title: Bijective meets mixed base
## Background

A bijective base \\$b\\$ numeration, where \\$b\\$ is a positive integer, is a bijective positional notation that makes use of \\$b\\$ symbols with associated values of \\$1,2,\cdots,b\\$.

Bijective base 2 representations of positive integers look like this:

```
1 -> 1
2 -> 2
3 -> 11
4 -> 12
5 -> 21
6 -> 22
7 -> 111
8 -> 112
9 -> 121
10 -> 122

```

Now, let's apply this to a mixed base. Bijective mixed base \\$\[b\_1,b\_2,\cdots,b\_n\]\\$ numeration uses \\$1,\cdots,b\_k\\$ as the symbols for each digit place, and the digit value of each digit place is \\$\prod\_{i=k+1}^{n}b\_i\\$, as in the usual mixed base. This system can uniquely represent the integers from 1 up to the number represented by \\$b\_1b\_2\cdots b\_n\\$.

Some numbers in bijective base \\$\[2,3,4\]\\$:

```
1 -> 1
2 -> 2
4 -> 4
5 -> 11
9 -> 21
16 -> 34
17 -> 111
28 -> 134
29 -> 211
40 -> 234

```

## Challenge

Given the base \\$b=\[b\_1,b\_2,\cdots,b\_n\]\\$ and a positive integer \\$x\\$, convert \\$x\\$ to bijective mixed base \\$b\\$ as a list of digit values. It is guaranteed that \\$x\\$ is representable in the system. Some digits of \\$b\\$ may be greater than 9. You can take the input \\$b\\$ and give output in either most- or least-significant-digit-first order (mixing is also OK).

Standard rules apply. The shortest code in bytes wins.

Protip: Jelly does not have this built-in.

## Test cases

Test cases are written in most-significant-digit-first order.

```
x = 1, b = [1] -> [1]
x = 3, b = [1,1,1,1] -> [1,1,1]

For b = [2, 1, 2, 3, 4]:
x = 1 -> [1]
x = 4 -> [4]
x = 10 -> [2, 2]
x = 20 -> [1, 1, 4]
x = 35 -> [2, 2, 3]
x = 56 -> [1, 2, 1, 4]
x = 84 -> [1, 1, 2, 2, 4]
x = 112 -> [2, 1, 2, 3, 4]

for b = [8, 9, 10, 11]:
x = 1 -> [1]
x = 2 -> [2]
x = 6 -> [6]
x = 24 -> [2, 2]
x = 120 -> [10, 10]
x = 720 -> [6, 5, 5]
x = 5040 -> [4, 9, 8, 2]

```

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

```
x=>b=>b.flatMap(v=>x?x-(x=~-x/v|0)*v:[])

```

Try it online!
> 5 votes

# Answer
# Wolfram Language (Mathematica), 40 bytes

Based on @tsh's Javascript answer.

-6 bytes thanks to @att.

```
Map[x=#;Pick[x-(x=⌊--x/#⌋)#,x>=0]&]&

```

Try it online!

Inputs and outputs are in least-significant-digit-first order.
> 3 votes

# Answer
# Haskell, 37 bytes

```
0#_=[]
a#(b:c)|q<-div(a-1)b=a-b*q:q#c

```

Try it online!

Inputs and outputs are in least-significant-digit-first order.
> 3 votes

# Answer
# Ruby, 39 bytes

```
->x,b{b.map{|y|x>0&&x-y*x= ~-x/y}-[!0]}

```

Try it online!

Freely adapted from tsh's Javascript
> 3 votes

# Answer
# Python 3, 51 bytes

```
f=lambda n,l:n*l and[~-n%l[0]+1]+f(~-n//l[0],l[1:])

```

Try it online!

reversed digit order
> 2 votes

# Answer
# Retina 0.8.2, 43 bytes

```
\d+
$*
+`(1+),*;(\1)*(1+)
;$#2$*1,$.3
.*;,

```

Try it online! Link includes test cases. Takes input in the order `b₁,...,bₙ;x`. Explanation:

```
\d+
$*

```

Convert to unary.

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

```

Repeatedly divmod `x` by `b` in reverse order, but always ensuring that the remainder is non-zero, and convert the remainder to decimal, but keep the quotient in unary.

```
.*;,

```

Delete any unused bases.
> 2 votes

# Answer
# Charcoal, 20 bytes

```
Ｗ∧θ⊟η«≦⊖θ←⸿Ｉ⊕﹪θι≧÷ιθ

```

Try it online! Link is to verbose version of code. I/O is in left-to-right order. Explanation:

```
Ｗ∧θ⊟η«

```

While `x` is nonzero, retrieve the previous mixed base `b` from the list of mixed bases.

```
≦⊖θ

```

Decrement `x`.

```
←⸿Ｉ⊕﹪θι

```

Reduce `x` modulo `b`, then increment the result, and print it on the previous line.

```
≧÷ιθ

```

Integer divide `x` by `b`.
> 1 votes

# Answer
# Red, 79 bytes

```
func[n b][r: copy[]until[insert r(n: n - 1)%(t: take/last b)+ 1 1 > n: n / t]r]

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 10 bytes

```
vD_#<y‰`>,

```

Inputs are in the order \\$\[b\],x\\$. I/O are both in least-significant-digit-first order, so reversed of the challenge description. The output is newline delimited.

Try it online or verify all test cases.

**Explanation:**

```
v           # Loop `y` over the first (implicit) input-list:
 D          #  Duplicate the current integer
            #  (which is the second implicit input-integer in the first iteration,
            #  and the quotient of the divmod every other iteration)
  _         #  If this is 0:
   #        #   Stop the loop
    <       #  (Else) Decrease the integer by 1
     y‰     #  Divmod it by `y`
       `    #  Pop and push both values separated to the stack
        >   #  Increase the top (the remainder) by 1
         ,  #  Pop and output it with trailing newline

```
> 1 votes

---
Tags: code-golf, math, integer, base-conversion
---


title: Confirm the Illuminati

text:
# Question
Title: Confirm the Illuminati
The Illuminati commands you (with their mind control) to output the following string:

```
         ^
        /_\
       /_|_\
      /_|_|_\
     /_|/o\|_\
    /_|_\_/_|_\
   /_|_|_|_|_|_\
  /_|_|_|_|_|_|_\
 /_|_|_|_|_|_|_|_\
/_|_|_|_|_|_|_|_|_\

```

# Rules:

---

Sandbox (I would leave it for the full 72 hours recommended by the sandbox FAQ, but with 7 upvotes and next to no negative feedback, 38 should be fine)

# Answer
> 23 votes
# Charcoal, ~~25~~ 21 bytes

```
Ｇ¬χ|_¶_|↗⁹↙^Ｍ³↓/o¶\‖Ｂ

```

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

```
  χ                     With sides of length 10
 ¬                      In the directions down and left
Ｇ                       Draw a closed polygon (implicit side)
   |_¶_|                Filled with |_ and _| on alternate lines
        ↗⁹               Draw a line of 9 /s
          ↙^            Draw a ^ and move the cursor down and left
            Ｍ³↓         Move down 3 characters
               /o¶\     Print the left half of the eye
                   ‖Ｂ  Reflect the canvas keeping the right edge

```

# Answer
> 52 votes
# Vim, 40 bytes

-2 bytes thanks to DJMcMayhem

```
9i_|␛r\I/␛qqYPxR /␛q8@qr^4jhR/o\␛jr/2hr\

```

You can see it in action in this GIF made using Lynn's python script

# Answer
> 10 votes
# SOGL V0.12, ~~31~~ ~~27~~ 25 bytes

```
 ^9∫Ƨ_|m└Κ}¹±§"/o¶\_”95žΓ

```

Try it Here!

```
 ^                         push "^"
  9∫      }                do 9 times, pushing counter
    Ƨ_|                      push "_|"
       m                     mold that to the counter
        └Κ                   prepend "/"
           ¹               collect the lines in an array - ["^", "/_", "/_|", ..., "/_|_|_|_|_"]
            ±              reverse each                    ["^", "_/", "|_/", ..., "_|_|_|_|_/"]
             §             reverse as ascii-art:
                            ["         ^",
                             "        /_",
                             "       /_|",
                             ...,
                             "/_|_|_|_|_"]
              "/o¶\_”      push "/o
                                 \_"
                     95ž   insert that at [9; 5]
                        Γ  palindromize horizontally

```

or a 24 byte version using `¼` (space to an antidiagonal) instead of `±§`:

```
 ^9∫Ƨ_|m└Κ}¹¼"/o¶\_”95žΓ

```

Try it Here!

# Answer
> 10 votes
# , 37 bytes

```
9i|_á\|r/òÄó_|
>òC ^4jhR/o\j2hR\_/

```

Try it online!

Hexdump:

```
00000000: 3969 7c5f 1be1 5c7c 722f f2c4 f35f 7c0a  9i|_..\|r/..._|.
00000010: 3ef2 4320 5e1b 346a 6852 2f6f 5c1b 6a32  >.C ^.4jhR/o\.j2
00000020: 6852 5c5f 2f                             hR\_/

```

Explanation:

```
9i                              " Insert 9 copies of...
  |_                            "   '|_'
    <esc>                       " Return to normal mode
         á\                     " Append a backslash
           |                    " Move to the first character
            r/                  " Replace it with a forward slash
              ò                 " Recursively...
               Ä                "   Duplicate this line (upwards)
                ó               "   Remove one instance of..
                 _|             "     '_|'
>                               "   Indent this line with one space
 ò                              " End the loop
  C ^                           " Change this line (previously '/_\') to ' ^'
     <esc>                      " Return to normal mode
          4j                    " Move down 4 lines
            h                   " Move one character to the left
             R                  " Write this text over existing characters...
              /o\               "   '/o\'
                 <esc>          " Return to normal mode
                      j         " Move down a line
                       2h       " Move two characters to the left
                         R      " Write this text over existing characters...
                          \_/   " '\_/'

```

# Answer
> 8 votes
# Python 2, ~~103~~ ~~101~~ ~~98~~ 95 bytes

-2 bytes thanks to Jonathan Frech
-3 bytes thanks to ovs

```
for i in range(10):print(9-i)*' '+['^','/_%s\\'%['|_'*~-i,'|/o\|_','|_\_/_|_'][i%6/4*i%3]][i>0]

```

Try it online!

# Answer
> 8 votes
# JavaScript (ES6), ~~95~~ 92 bytes

```
f=(n=9,s='')=>n--?f(n,s+' ')+s+`/${n-4?n-3?'_|'.repeat(n):'_|/o\\|':'_|_\\_/_|'}_\\
`:s+`^
`

```

Or **91 bytes** with a leading new-line -- which I think is not allowed:

```
f=(n=9,s=`
`)=>n--?f(n,s+' ')+s+`/${n-4?n-3?'_|'.repeat(n):'_|/o\\|':'_|_\\_/_|'}_\\`:s+`^`

```

### Demo

```
f=(n=9,s='')=>n--?f(n,s+' ')+s+`/${n-4?n-3?'_|'.repeat(n):'_|/o\\|':'_|_\\_/_|'}_\\
`:s+`^
`

O.innerText = f()
```

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

### Formatted and commented

```
f = (n = 9, s = '') =>    // n = line counter, s = leading spaces
  n-- ?                   // if we haven't reached the top:
    f(n, s + ' ') +       //   do a recursive call with one more leading space
    s +                   //   append the leading spaces
    `/${                  //   append the left border
      n - 4 ?             //   if this is not the 4th row:
        n - 3 ?           //     if this is not the 3rd row:
          '_|'.repeat(n)  //       append the brick pattern
        :                 //     else (3rd row):
          '_|/o\\|'       //       append the top of the eye
      :                   //   else (4th row):
        '_|_\\_/_|'       //     append the bottom of the eye
    }_\\\n`               //   append the right border + line-feed
  :                       // else:
    s + `^\n`             //   append the top of the pyramid and stop the recursion

```

# Answer
> 8 votes
# C (gcc), ~~124~~ ~~122~~ ~~120~~ ~~119~~ ~~117~~ ~~115~~ 118 bytes

-1 byte thanks to @xanoetux +3 missing the lowest level...

```
f(i){for(printf("%*c",i=10,94);--i;printf("\n%*c%s_\\",i,47,i^6?i^5?"_|_|_|_|_|_|_|_|_|"+i*2:"_|_\\_/_|":"_|/o\\|"));}

```

Try it online!

# Answer
> 5 votes
# PowerShell, ~~109~~ 105 bytes

```
filter f{' '*$_+'/'+'_|'*(8-$_)+'_\'}
' '*9+'^'
8|f
7|f
6|f
'     /_|/o\|_\
    /_|_\_/_|_\'
3..0|%{$_|f}

```

Try it online!

*Saved 4 bytes thanks to Veskah.*

# Answer
> 5 votes
## Haskell, ~~110~~ 107 bytes

```
"         ^\n"++do z<-[1..9];([z..8]>>" ")++'/':g z++"_\\\n"
g 4="_|/o\\|"
g 5="_|_\\_/_|"
g x=[2..x]>>"_|"

```

Try it online!

Those 9 space at the beginning hurt.

How it works

```
"         ^\n"++         -- first line, followed by
do                       -- we use the "do" syntatic sugar for monads,
                         -- here the list monad
   z<-[1..9]             -- for all 'z' from [1..9] perform the following
                         -- and collect the results in a single list
     ([z..8]>>" ")++'/'  --   make the spaces for the current line and
                         --   the left wall '/'
     g z                 --   call g to make the inner part
     "_\\\n"             --   append '_', '\' and a NL

g 4="_|/o\\|"            -- line 4 and 5 are implemented directly
g 5="_|_\\_/_|"
g x=[2..x]>>"_|"         -- all other lines are some copies of "_|"

```

Edit: -3 bytes thanks to @Laikoni:

# Answer
> 3 votes
# 05AB1E, ~~47~~ ~~42~~ 40 bytes

```
'/„_|ûûû«η'^0ǝ.∞.C":;<IJK"Çv"/o\\_/"Nèyǝ

```

Try it online!

```
'/„_|ûûû«                                # Push bottom left tier of pyramid.
         η                               # All prefixes of...
          '^0ǝ                           # Replace the tip.
              .∞.C                       # Mirror, Center.
                  ":;<IJK"Ç              # Push [58,59,60,73,74,75].
                           v"/o\\_/"Nèyǝ # Replace those indexes with the eye.

```

---

Stupid version: `„_|3×"_|/o\|".;„_|2×û"_|_\_/_".;`

---

Other, less stupid version (but still worse):

# 05AB1E, 42 bytes

```
•~µÎт•η4¾ǝ•Σ}•4ǝ•3x1•5ǝεS"|_/\^o"sèJ}€.∞.C

```

Try it online!

# Answer
> 2 votes
# Python 2, 154 bytes

```
l=bytearray
a,b=' _';g=[l(a*9+"^"+a*9)]+[l(a*(8-k)+"/%s\\"%"|".join(b*k+b))for k in range(9)]
g[4][8:11]=l("/o\\")
g[5][8:11]=l("\\_/")
for r in g:print r

```

Try it online!

-3 bytes using `bytearray` thanks to Rod
-1 byte thanks to bobrobbob

# Answer
> 2 votes
# Bubblegum, 48 bytes

```
00000000: 5380 8138 2e18 4b3f 3e86 0bce ac01 72e0  S..8..K?>.....r.
00000010: 6c30 0fc6 d1cf 8f01 71e1 cae2 218a e12a  l0......q...!..*
00000020: 6ba0 ea61 7c84 085c 0021 0417 4188 0100  k..a|..\.!..A...

```

Try it online!

# Answer
> 2 votes
# PHP, 123+3 bytes

+3 bytes for the weird tab counting. (it still moves the cursor 8 spaces in any console!)

```
for($i=10;--$i;)$r.=str_pad(str_pad("
",$i)."/",20-$i,"_|")."\\";$r[48]=$r[65]="/";$r[50]=$r[63]="\\";$r[49]=o;echo"   ^$r";

```

Note: The first character after `echo"` is a tab character!

Run with `-nr` or try it online.

other version, same length:

```
for(;$i++<9;)$r.=str_pad(str_pad("
",10-$i)."/",10+$i,"_|")."\\";$r[48]=$r[65]="/";$r[50]=$r[63]="\\";$r[49]=o;echo"    ^$r";

```

# Answer
> 2 votes
# Retina, ~~79~~ 73 bytes

```

/8x
8
$*
+`^(.*)\Sx
 $1x¶$&
 x
 ^
/111x
/1/o\|x
/1111x
/1x_/1x
1
_|
x
_\

```

Try it online!

# Answer
> 2 votes
# Ruby, 92 bytes

```
10.times{|i|s=' '*(10-i)+(i<1??^:"/#{"_|"*~-i}_\\");i/2==2&&s[9,3]="/o\\_/"[i%2*2,3];puts s}

```

# Answer
> 2 votes
# Excel VBA, 104 Bytes

Anonymous VBE immediate window function that confirms the truth.

**Version A:**

```
?Spc(9)"^":For i=0To 8:[A1]=i:?Spc(8-i)"/_"[If(A1=3,"|/o\|_",If(A1=4,"|_\_/_|_",Rept("|_",A1)))]"\":Next

```

**Version B:**

```
?Spc(9)"^":For i=0To 8:[A1]=i:?Spc(8-i)"/_"IIf(i=3,"|/o\|_",IIf(i=4,"|_\_/_|_",[Rept("|_",A1)]))"\":Next

```

# Answer
> 1 votes
# Javascript 90 bytes (if default parameter a=9 is required then 92 bytes)

```
A=(a,x=``)=>a?A(a-1,x+" ")+x+"/".padEnd(a*2,a^5?a^4?"_|":"_|/o\\|":"_|_\\_/")+`\\
`:x+`^
`
console.log(A(9))
```

# Answer
> 1 votes
# C# (.NET Core), 174 153 bytes

```
()=>string.Format(@"{1,10}
{0,10}\
{0,9}{2}{3,10}{2}{0,7}|/o\{2}{3,8}\_/_{2}{0,5}{4}  {3}{4} {3}|_{4}{3}|_|_{4}","/_","^",@"|_\
","/_|_",@"|_|_|_|_|_\
")

```

Try it online!

An inefficient way of building the pyramid, but interesting working through it.

### Acknowledgements

-21 bytes thanks to @someone

# Answer
> 1 votes
# Julia, ~~152~~ ~~141~~ ~~139~~ ~~130~~ ~~127~~ ~~120~~ ~~113~~ 112 bytes

```
q="_|";a+b=" "^a*b;a\b=replace(a,q^3,q*b,1);~n=n<0?9+"^\n":~(n-1)*(8-n+"/$(q^n)_\\\n");print(~8\"/o\\|"\"_\\_/")

```

Explained:

```
#Define constant q to abbreviate this string
q="_|";

#Redefine the addition operator to compactly provide whitespace
#where needed
a+b=" "^a*b;

#Redefine the inverse division operator so we can substitute
#"_|_|_|" with "_|"*b very compactly
a\b=replace(a,q^3,q*b,1);

#Redefine the bitwise not operator to generate pyramid layers
#Defines them recursively, calling itself to generate previous
#layers before appending its own.
#The base case generates the tip.
~n=n<0?9+"^\n":~(n-1)*(8-n+"/$(q^n)_\\\n");

#Print to output
print(

    #Pyramid with 8 body layers
    ~8

    #Then patch in the eye
    \"/o\\|"
    \"_\\_/"
)

```

# Answer
> 1 votes
# Java 8, 156 bytes

```
v->"".format("%1$9s^\n%1$8s/a%1$7s/ba%1$6s/bba     /b/o\\|a    /b_\\_/ba   /bbbbba  /bbbbbba /bbbbbbba/bbbbbbbba","").replace("a","_\\\n").replace("b","_|")

```

**Explanation:**

Try it here.

```
v->                        // Method with empty unused parameter and String return-type
  "".format(               //  Format the following String (`%1$Ns` = N spaces)
      "%1$9s^\n            //            ^
       %1$8s/a             //           /_\
       %1$7s/ba            //          /_|_\
       %1$6s/bba           //         /_|_|_\
            /b/o\\|a       //        /_|/o\|_\
           /b_\\_/ba       //       /_|_\_/_|_\
          /bbbbba          //      /_|_|_|_|_|_\
         /bbbbbba          //     /_|_|_|_|_|_|_\
        /bbbbbbba          //    /_|_|_|_|_|_|_|_\
       /bbbbbbbba","")     //   /_|_|_|_|_|_|_|_|_\
    .replace("a","_\\\n")  //  Replace all "a" with "_\" + new-line
    .replace("b","_|")     //  Replace all "b" with "_|"
                           // End of method (implicit / single-line return-statement)

```

# Answer
> 1 votes
# C# (.NET Core), 144 bytes

This one may seem quite boring, because it is quite boring.

```
()=>@"         ^
        /_\
       /z\
      /z|_\
     /_|/o\|_\
    /z\_/z\
   /z|z|z\
  /z|z|z|_\
 /z|z|z|z\
/z|z|z|z|_\".Replace("z","_|_")

```

Try it online!

# Answer
> 1 votes
# Splinter, 124 bytes

```
H{\/}G{BB}F{\_DG}E{\ H}D{\\\
}C{A\|}B{\ \ }A{\_\|\_}GG\ \^\
GGHFBEADGBHCFE\_\|H\o\\\|FHA\\\_HADBECCADBHCCC\_DECCCADHCCCC\_\\

```

Try it online!

# Answer
> 0 votes
# JavaScript, 117 bytes

I know for a *fact* I'm not beating any of the golfing languages, but at least I can give my own solution.

```
$=>[...Array(10)].map((e,i)=>' '.repeat(9-i)+(i--?`/${['_|/o\\|','_|_\\_/_|'][i-3]||'_|'.repeat(i)}_\\`:'^')).join`
`

```

Here's a demo:

```
var f = $=>[...Array(10)].map((e,i)=>' '.repeat(9-i)+(i--?`/${['_|/o\\|','_|_\\_/_|'][i-3]||'_|'.repeat(i)}_\\`:'^')).join`
`;
console.log(f());
console.log(f.toString().length);
```

Explanation:

```
$=>                                       // outer function start
[...Array(10)]                            // create an array to map
.map(…)                                   // map it
    (e,i)=>                               // mapping function start
    ' '.repeat(9-i)                       // spaces for padding
    +(i--?…:'^')                          // use the carat if at the top of the pyramid
        `/${…}_\\`                        // otherwise, make the sides + steps
            ['_|/o\\|','_|_\\_/_|'][i-3]  // use the patterns for the eye, if in the correct rows
            ||'_|'.repeat(i)              // otherwise, make the "bricks" structure
.join`
`                                         // join all the rows into a string (yes this part has a newline in it)

```

# Answer
> 0 votes
# Javascript, 238 bytes

My very first try at codegolfing :D

```
var f=()=>{let b=x=>' '.repeat(x),g='\\',h='/',i=1,st=[(b(9)+'^').split('')];for(;i<10;i++)st.push((b(9-i)+h+st.map(i=>'_').join('|')+g).split(''));st[4][8]=st[5][10]=h;st[4][9]='o';st[5][8]=st[4][10]=g;return st.map(s=>s.join('')).join('\n');}

document.getElementById("display").innerHTML = f();
console.log(f.toString().length);
```

```
<pre id="display">
</pre>
```

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


title: Binomial transform

text:
# Question
Title: Binomial transform
## Background

**Binomial transform** is a transform on a finite or infinite integer sequence, which yields another integer sequence. The binomial transform of a sequence \\$\\{a\_n\\}\\$ is given by

$$s\_n = \sum\_{k=0}^{n}{(-1)^k \binom{n}{k} a\_k}$$

It has an interesting property that applying the transform twice will yield the original, i.e. the transform is an *involution*.

## Example

Take the sequence `1, 3, 9, 27, 81`. The binomial transform of this sequence is computed as follows:

$$ \begin{align} s\_0 &= a\_0 = 1\\ s\_1 &= a\_0 - a\_1 = -2\\ s\_2 &= a\_0 - 2a\_1 + a\_2 = 4\\ s\_3 &= a\_0 - 3a\_1 + 3a\_2 - a\_3 = -8\\ s\_4 &= a\_0 - 4a\_1 + 6a\_2 - 4a\_3 + a\_4 = 16 \end{align} $$

So the binomial transform of `1, 3, 9, 27, 81` is `1, -2, 4, -8, 16`. Verifying that the binomial transform of `1, -2, 4, -8, 16` is indeed `1, 3, 9, 27, 81` is left as an exercise to the reader.

## Task

Compute the binomial transform of a given finite integer sequence.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Note that each test case works in both directions, i.e. if the left side is given as input, then the right side must be output, and vice versa.

```
[0] <-> [0]
[20, 21] <-> [20, -1]
[1, 3, 9, 27, 81] <-> [1, -2, 4, -8, 16]
[20, 21, 6, 15, 8, 48] <-> [20, -1, -16, -40, -80, -183]
[0, 1, 2, 3, 4, 5, 6] <-> [0, -1, 0, 0, 0, 0, 0]
[0, 1, 1, 2, 3, 5, 8, 13, 21]
    <-> [0, -1, -1, -2, -3, -5, -8, -13, -21]
[1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0]
    <-> [1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1]

```

# Answer
# Jelly, 5 bytes

```
_ƝƬZḢ

```

Try it online!

```
_ƝƬZḢ  Main Link
  Ƭ    While results are unique (until we hit the empty list)
 Ɲ     To each (overlapping) pair,
_      Subtract
   Z   Zip; columns to rows
    Ḣ  The first column

```

On the Wikipedia page, it says that the binomial transform is just the Nth forward differences. So, we just keep getting the difference array until we hit the empty list and stop, and then just grab the left column.
> 13 votes

# Answer
# Python 3.8, 45 bytes

```
def f(h,*t):print(h);f(*[h-(h:=x)for x in t])

```

Try it online!

Takes input splatted like `f(1,2,3)`, outputs by printing entries one per line, terminates with error.

Computes repeated differences, taking advantage of the Python 3.8 walrus operator `:=` to do so in a list comprehension.
> 9 votes

# Answer
# K (ngn/k), 13 bytes

```
,/*'(-/'2':)\

```

Try it online!

* `(...)\` run a converge-scan, repeating until consecutive executions return the same result, or a result matches the initial input
* `-/'2':` take the forward differences
* `,/*'` take the first value of each row, and flatten to remove the trailing empty list, `()`
> 7 votes

# Answer
# , 13 bytes

```
-/@:*!/~@i.@#

```

Try it online!

For e.g. 1 3 9 27:

`!/~@i.@#` table of bionimal coefficients

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

```

`*` times the input

```
1 1 1  1
0 3 6  9
0 0 9 27
0 0 0 27

```

`-/@:` reduce bottom to top with minus

```
  1 1 1  1 => + 1 1 1  1
- 0 3 6  9    - 0 3 6  9
- 0 0 9 27    + 0 0 9 27
- 0 0 0 27    - 0 0 0 27
              ----------
                1_2 4 _8

```
> 5 votes

# Answer
# JavaScript (ES6),  ~~47~~  45 bytes

Using forward differences, as hyper-neutrino first did.

Returns a comma-separated string.

```
f=([n,...a])=>a+a?n+[,f(a.map(v=>n-(n=v)))]:n

```

Try it online!

### How?

At each iteration, we extract the leading term \\$n\\$ of the array, append it to the final output and do recursive calls with the forward differences until the array is empty.

**Example:**

```
[  **20**,   21,    6,   15,    8,   48 ] < input
[  **-1**,   15,   -9,    7,  -40 ]
[  **-16**,   24,  -16,   47 ]
[  **-40**,   40,  -63 ]
[  **-80**,  103 ]
[ **-183** ]
     ^
   output
```

---

# JavaScript (ES6), 74 bytes

A naive implementation that actually computes the binomial coefficients.

```
a=>a.map((_,n)=>a.reduce((t,v,i)=>t+(g=k=>k?g(--k)*(k-n)/~k:i&1?-v:v)(i)))

```

Try it online!
> 4 votes

# Answer
# Charcoal, 18 bytes

```
Ｗθ«Ｉ…θ¹≔ＥΦθλ⁻§θλκθ

```

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

```
Ｗθ«

```

Repeat until there are no more terms.

```
Ｉ…θ¹

```

Output the next term on its own line.

```
≔ＥΦθλ⁻§θλκθ

```

Calculate reverse differences.

The binomial transform can be represented as a sort of reverse Pascal's Triangle where each value is the sum of the two below (here using the original `1, 3, 9, 27, 81` example):

```
             1
          3    -2
       9    -6     4
   27   -18    12    -8
81   -54    36   -24    16

```

The transform then appears on the rightmost entries on each row. Since addition is commutative, the symmetry demonstrates that transform is thus an involution.

The above code calculates the transform by calculating the bottomleft-topright diagonals in turn from topleft to bottomright. It's also possible to calculate the topleft to bottomright diagonals in turn from bottomleft to topright. The natural code to do this in Charcoal would normally take 17 bytes but unfortunately a combination of factors prevents this from working:

```
Ｆ⮌θ≔⁻ιＥ⊕ＬυΣ…υλυＩυ

```

Don't try it online! Explanation:

```
Ｆ⮌θ

```

Loop over the terms in reverse order.

```
≔⁻ιＥ⊕ＬυΣ…υλυ

```

Theoretically calculate the next diagonal by vectorised subtraction of sums of prefixes (i.e. cumulative sums but including a leading zero term) from the next term. This doesn't work because a) Charcoal can't calculate `CycleChop([], 0)` at all and b) Charcoal returns `None` for `Sum([])`. The cheapest fix for both of these is to use `And(l, ...)` at a cost of 2 bytes to avoid trying to sum the empty prefix at all, or alternatively each issue can be worked around separately at a cost of 1 byte each.

```
Ｉυ

```

Output the final diagonal.
> 4 votes

# Answer
# Factor, 48 bytes

```
[ [ dup first . differences vneg ] until-empty ]

```

Try it online!

Output the first member of the input sequence to stdout followed by a newline, take the differences, and flip the sign of each element until empty.
> 4 votes

# Answer
# , 45 bytes

```
function(x)for(i in x){show(x[1]);x=-diff(x)}

```

Try it online!
> 4 votes

# Answer
# Vyxal, 5 bytes

```
⁽¯↔vh

```

Try it Online!

Me when very many yes.
> 3 votes

# Answer
# Stax, <sup>~~10~~</sup> 7 bytes

```
É¿F▒x"╢

```

Run and debug it

the lack of a short method to get fixpoint made this a bit more interesting.

## Explanation

```
rwcHP:-c
r        reverse
 w       do-while top of stack is truthy
  cHP     print last element of the array
     :-   get deltas (returns [] for 2-element arrays)
       c  copy

```
> 3 votes

# Answer
# Jelly, 10 bytes

```
J’cþ`NÐeZḋ

```

Try it online!

## Explanation

```
J          | 1..length of sequence
 ’         | Decrement by 1
  cþ`      | Outer product using nCr
     NÐe   | Negate even indices
        Z  | Transpose
         ḋ | Dot product with input

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 27 bytes

```
,\(+/⊣×⊢(!⍨×¯1*⊢)1⍳⍤+⊢)¨⍳∘≢

```

Try it online!

I was too lazy to read the article, here's a stupid solution. ~~I don't know why it doesn't work in TIO, but it does work on my computer~~. Requires zero-indexing.
> 2 votes

# Answer
# Python 3, 62 bytes

```
f=lambda a:len(a)>1and f([x-y for x,y in zip(a,a[1:])])or a[0]

```

Try it online!

Recursive deltas until one element left.
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~34~~ 31 bytes

```
(a=Most@a-{##2};#)&@@a&/@(a=#)&

```

Try it online!

Uses the differences method.

```
                         (a=#)  assign a to input
                       /@       step through input:
 a=Most@a-{##2};                    update a to its forward differences
(               #)&@@a&             while taking its first element (pre-update)

```
> 2 votes

# Answer
# Red, 95 bytes

```
func[v][v: make vector! v until[print v/1 u: copy v
move back tail u u take v: u - v empty? v]]

```

Try it online!
> 2 votes

# Answer
# , 44 bytes

```
f=function(x)if(sum(x|1))c(x[1],f(-diff(x)))

```

Try it online!

Recursive function, taking inspiration from pajonk's answer.
> 2 votes

# Answer
# Japt `-g`, 9 bytes

```
Nc¡=ä-})y

```

Try it

```
Nc¡=ä-})y     :Implicit input of array U
N             :Array of all inputs
 c            :Concatenate
  ¡           :  Map U
   =          :    Reassign to U
    ä-        :    Consecutive pairs, reduced by subtraction
      }       :  End map
       )      :End concat
        y     :Transpose
              :Implicit output of first element

```
> 2 votes

# Answer
# Java (JDK), 69 bytes

```
a->{for(int l=a.length,i=0,j;++i<l;)for(j=l;j-->i;)a[j]=a[j-1]-a[j];}

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~49 43~~ 42 bytes

```
f=->a{k,*a=a;k ?[k]+f[a.map{|x|k-k=x}]:[]}

```

Try it online!
> 1 votes

# Answer
# MMIX, 52 bytes (13 instrs)

Prototype: `void __mmixware bintran(int64_t *seq, size_t len)`

jxd:

```
00000000: 3b020101 5a010002 f8000000 27020201  ;£¢¢Z¢¡£ẏ¡¡¡'££¢
00000010: 2c030200 8d040308 8dff0300 2604ff04  ,¤£¡⁽¥¤®⁽”¤¡&¥”¥
00000020: ad040308 5b02fffa 27010101 e7000008  Ḍ¥¤®[£”«'¢¢¢ḃ¡¡®
00000030: f0fffff4                             ṅ””ṡ

```

Disassembly:

```
bintran SUB   $2,$1,1       // i = len - 1
        PBNZ  $2,0F         // if(i) goto loop
        POP   0,0           // return
0H      SUBU  $2,$2,1       // loop: i--
        8ADDU $3,$2,$0      // int64_t t = seq + i
        LDO   $4,$3,8       // a = t[1]
        LDO   $255,$3,0     // b = t[0]
        SUBU  $4,$255,$4    // a = b - a
        STO   $4,$3,8       // t[1] = a
        PBNZ  $2,0B         // if(i) goto loop
        SUBU  $1,$1,1       // len--
        INCL  $0,8          // seq++
        JMP   bintran       // bintran(seq, len) (tail recursion eliminated)

```

If you wish to add early exit on zero length, this costs four bytes more.

```
bintran BZ   $1,1F
2H      PBNZ $2,0F
1H      POP  0,0
0H      SUBU $2,$2,1
        (etc)
        JMP  2B

```

The resulting machine code is identical except by prefixing of `42010001` (`B¢¡¢`).
> 0 votes

# Answer
# Pari/GP, 35 bytes

```
a->[a*Col((x-1)^n,#a)|n<-[0..#a-1]]

```

Try it online!

# Pari/GP, 38 bytes

```
a->Vec(subst(Ser(a),x,-x/t=1-x)/t+y)%y

```

Try it online!
> 0 votes

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