title: Generate all Sublist Partitions

text:
# Question
Title: Generate all Sublist Partitions
Given a non-empty list of integers, output every possible partitioning of the list where each partition is a non-empty sublist.

So for the list `[1, 2, 3, 4]` the result is:

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

```

The order of the lists in the output does not matter, so `[[1, 2, 3, 4]]` could be first, last, or wherever. The order of the elements must be preserved.

This is code-golf, so shortest answer wins.

---

Related: Partition a list!

# Answer
> 2 votes
# Jelly, 2 bytes

```
ŒṖ

```

Try it online!

# Answer
> 13 votes
## Retina, ~~27~~ 19 bytes

Byte count assumes ISO 8859-1 encoding.

```
+1%`,
;$'¶$`];[
;
,

```

Try it online!

### Explanation

Of course this computes all partitions using string processing. The basic idea is that we can generate all partitions by deciding for each `,` individually whether or not we want to split the list there. This kind of stuff can be done in Retina by matching each `,` in turn and using a replacement which gives both possible outputs.

The input acts as the base case: the partition where all elements are still in a single list.

```
+1%`,
;$'¶$`];[

```

Now we repeatedly (`+`) match the first (`1`) comma (`,`), on each line (`%`) (treating that line as a separate string, which is relevant for `$'` and \`\`$1 \` in the substitution).

That comma gets replaced with:

```
;   A semicolon. This is just a stand-in for the comma, so we know we've already
    processed it and it won't be substituted again by the next iteration.
$'  Everything after the match. This completes the first (unchanged) version of
    the current line.
¶   A linefeed. Since the next iteration will scan for all lines again, this doubles
    the number of strings we're working with.
$`  Everything before the match. This completes the second (split) version of
    the current line.
];[ A semicolon around which we split the list.

```

Remember that everything in front of the match and after the match remains in the string anyway, so the full result is actually `$`;$'¶$`];[$'` which explains why we insert the suffix and prefix in that order.

This loop stops once all commas are gone.

```
;
,

```

Finally, replace the semicolons with commas again to match the input format.

# Answer
> 10 votes
# Pure Bash, 28

```
eval echo [${1//:/{:,]:[\}}]

```

Here, lists are colon-separated, and contained in square brackets. For example in the question, the input list would be `1:2:3:4` and the output is:

```
[1:2:3:4] [1:2:3]:[4] [1:2]:[3:4] [1:2]:[3]:[4] [1]:[2:3:4] [1]:[2:3]:[4] [1]:[2]:[3:4] [1]:[2]:[3]:[4]

```

Try it online.

* `${1//:/REPLACEMENT}` replaces the colons in `$1` with `{:,]:[\}`
* This generates a brace expansion like `[1{:,]:[}2{:,]:[}3{:,]:[}4]`
* The eval (and careful `\` escapes) causes the brace expansion to happen last and give the desired result.

---

If it is necessary to exactly match the given `[[ , , ...]]` format, then we can do this instead:

# Pure Bash, 47

```
eval printf '%s\\n' ${1//, /{\\,\\ ,]\\,\\ [\}}

```

Try it online.

# Answer
> 6 votes
# Pyth, 2 bytes

```
./

```

With input `[1, 2, 3, 4]` (for instance).

**Explanation**: `./` is the partition operator. It returns all divisions of the input list into disjoint sub-lists. The input is implicitly fed to the program.

Test it online!

# Answer
> 6 votes
# 05AB1E, 5 bytes

```
Œæʒ˜Q

```

Try it online!

```
Œæʒ˜Q  Main link. Argument l
Œ      Get all sublists of l
 æ     Powerset of those lists
  ʒ˜Q  Filter: Keep the lists that when flattened equal the input

```

# Answer
> 4 votes
# Python 3, ~~82~~ ~~72~~ 66 bytes

```
f=lambda l:[k+[l[i:]]for i in range(len(l))for k in f(l[:i])]or[l]

```

Try it online!

*-5 bytes thanks to @JonathanAllan*

# Answer
> 4 votes
# Haskell, ~~59~~ ~~55~~ 49 bytes

```
p[x]=[[[x]]]
p(x:r)=do a:b<-p r;[(x:a):b,[x]:a:b]

```

Try it online!

Recursive solution. Usage example: `p [1,2,3]` returns `[[[1,2,3]],[[1,2],[3]],[[1],[2,3]],[[1],[2],[3]]]`.

-6 bytes thanks to xnor!

# Answer
> 3 votes
# , 42 bytes

```
<@(</."1)~<:@#_&(][:;<@(,~"{~0 1+>./)"1)0:

```

Generates all sublist partitons by creating the keys for partition sublists of length 1 and iterating to the length of the input list. Each partition sublist is then formed by selecting from the keys.

For example, here is the process of creating the keys for a length 4 list.

Try it online!

# Answer
> 3 votes
# Brachylog, 2 bytes

```
~c

```

Try it online!

Function submission that produces output via acting as a generator. (The TIO link contains extra code to make this into a full program, for testing purposes.)

Incidentally, although not technically a builtin, this is so commonly used in Brachylog that a) it probably deserves a single-byte representation, and b) the `c` builtin can take a parameter to make assertions about its *input* (whereas with most builtins, a parameter talks about how to produce the *output*).

## Explanation

```
~c
~     Find a value with the following properties:
 c      concatenating its elements produces {the input}

```

# Answer
> 3 votes
# , ~~26~~ 24 bytes

```
<@(<;.1)~2#:@(+i.)@^<:@#

```

Try it online!

# Answer
> 2 votes
# APL, 26 bytes

```
{⊂∘⍵¨1,¨↓⍉(X⍴2)⊤⍳2*X←⍴1↓⍵}

```

Test:

```
      {⊂∘⍵¨1,¨↓⍉(X⍴2)⊤⍳2*X←⍴1↓⍵} 1 2 3 4
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│┌─────┬─┐│┌───┬───┐│┌───┬─┬─┐│┌─┬─────┐│┌─┬───┬─┐│┌─┬─┬───┐│┌─┬─┬─┬─┐│┌───────┐│
││1 2 3│4│││1 2│3 4│││1 2│3│4│││1│2 3 4│││1│2 3│4│││1│2│3 4│││1│2│3│4│││1 2 3 4││
│└─────┴─┘│└───┴───┘│└───┴─┴─┘│└─┴─────┘│└─┴───┴─┘│└─┴─┴───┘│└─┴─┴─┴─┘│└───────┘│
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘

```

Explanation:

* `X←⍴1↓⍵`: `X` is the length of  (the input list) with its first element dropped
* `⍳2*X`: the numbers \[1..2^X\]
* `(X⍴2)⊤`: base-2 representation of those numbers, with `X` positions (i.e. `X` itself will wrap around to `0`).
* `↓⍉`: rotate the matrix and split it along the lines ( gives as a result a matrix with the numbers along the columns), giving an array of bit vectors
* `1,¨`: prepend a 1 to each bit vector.
* `⊂∘⍵¨`: for each bit vector, split  at each 1.

# Answer
> 2 votes
# Haskell, 45 bytes

```
foldr(\h t->map([h]:)t++[(h:y):z|y:z<-t])[[]]

```

Try it online!

I found this solution a while back in thinking about a Haskell tip.

# Answer
> 1 votes
# Python, 90 bytes

outgolfed by ovs (making something I thought I'd tried work :p)

```
def f(a):r=[[a]];i=len(a)-1;exec("for s in f(a[:i]):s+=[a[i:]];r+=[s]\ni-=1\n"*i);return r

```

A recursive function which builds up the list of partitions from slices of the input with the tail reached when the slices are of length 1.

**Try it online!**

The `exec` saves 4 bytes over a `while` or 3 over a `for` loop (below) since it means only two `\n`s rather than two levels of indentation, allowing the whole function to be on one line (while the order of slicing does not matter).

```
def f(a):
 r=[[a]]
 for i in range(1,len(a)):
  for s in f(a[:i]):s+=[a[i:]];r+=[s]
 return r

```

# Answer
> 1 votes
# Python 3, 67 bytes

```
f=lambda x,n=1:x[n:]and[y+[x[n:]]for y in f(x[:n])]+f(x,n+1)or[[x]]

```

Try it online!

# Answer
> 1 votes
# Haskell, 59 bytes

```
x#[]=[[[x]]]
x#(a:b)=[(x:a):b,[x]:a:b]
foldr((=<<).(#))[[]]

```

# Answer
> 1 votes
# Ruby, ~~62~~ 57 bytes

```
->l{(0..2**l.size).map{|x|l.chunk{1&x/=2}.map &:last}|[]}

```

Try it online!

### How it works:

* The number of partitions is 2^(n-1): I iterate on binary numbers in that range, take the groups of zeros and ones and map them as subsets of the initial list.
* Instead of fiddling with the range, I make it double and discard duplicates at the end. Now I can also discard the first binary digit and make the chunk function shorter.

# Answer
> 1 votes
# Curry (PAKCS), 32 bytes

```
f(a:b++c:d)=(a:b):f(c:d)
f a=[a]

```

Try it online!

Curry supports non-deterministic operations which can return different values for the same input. This is a non-deterministic function whose different return values are the all sublist partitions.

# Answer
> 1 votes
# APL(Dyalog Unicode), 15 bytes SBCS

Extracted from this answer of mine. Assumes index origin 0.

```
{⊂∘⍵¨~,⍳1+×⍳≢⍵}

```

Try it on APLgolf!

# Answer
> 1 votes
# Vyxal, 7 bytes

```
ÞSṗ'f⁰⁼

```

Try it Online!

well it has a 2-byte builtin `øṖ` but it doesn't return all of the partitions...

## How?

```
ÞSṗ'f⁰⁼
ÞS      # Get all sublists of the (implicit) input
  ṗ     # Powerset
   '    # Filter for:
    f   #  Flatten
     ⁰⁼ #  Is it equal to the input? (non-vectorizing)

```

# Answer
> 0 votes
## JavaScript (ES6), 87 bytes

```
([e,...a],b=[],c=[e],d=[...b,c])=>1/a[0]?[...f(a,b,[...c,a[0]]),...f(a,d,[a[0]])]:[d]

```

Explanation: `b` is the list of previous sublists, `c` is the current sublist, (which starts off as the first element of the array, since that must be in the first sublist) while `d` is the list of all sublists. The rest of the array elements are then recursively processed. In each case there are two options: either the next element is appended to the current sublist, or the current sublist is completed and the next element starts a new sublist. The recursive results are then concatenated together. When the array is exhausted, the list of list of all sublists is the result.

# Answer
> 0 votes
# APL(NARS) 38 char, 76 bytes

```
{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}

```

this use the Nars function 11 1‼k k but is very slow, unusable for arg array of 9 elements already...

```
  P3←{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}

  ⍴∘P3¨{1..⍵}¨⍳8
1  2  4  8  16  32  64  128
  P3 'abcd'
abcd    abc d    ab cd    a bcd    ab c d    a bc d    a b cd    a b c d

```

this below is the function that not use the built in:

```
r←h w;k;i
   r←⊂,⊂w⋄k←↑⍴w⋄i←1⋄→B
A: r←r,(⊂⊂,i↑w),¨h i↓w⋄i+←1
B: →A×⍳i<k

  h 'abcd'
abcd    a bcd    a b cd    a b c d    a bc d    ab cd    ab c d    abc d
  ⍴∘h¨{1..⍵}¨⍳8
2  4  8  16  32  64  128

```

we se the type each result:

```
  o h ,1
┌──────┐
│┌1───┐│
││┌1─┐││
│││ 1│││
││└~─┘2│
│└∊───┘3
└∊─────┘
  o h 1 2
┌2───────────────────┐
│┌1─────┐ ┌2────────┐│
││┌2───┐│ │┌1─┐ ┌1─┐││
│││ 1 2││ ││ 1│ │ 2│││
││└~───┘2 │└~─┘ └~─┘2│
│└∊─────┘ └∊────────┘3
└∊───────────────────┘

```

I don't know how it works, it is only heuristic try...

Possible I make some error; both the functions build the partitions of the list whatever input and not only 1 2 ... n.

# Answer
> 0 votes
# Axiom, 251 bytes

```
C==>concat;A==>List Any;px(a:A):A==(k:=#a;r:=copy[a];k<=1=>r;i:=1;repeat(i>=k=>break;x:=a.(1..i);y:=a.((i+1)..k);z:=px(y);t:=[x,z.1];for j in 2..#z repeat(w:=(z.j)::A;m:=#w;v:=[x];for q in 1..m repeat v:=C(v,w.q);t:=C(t,[v]));r:=C(r,copy t);i:=i+1);r)

```

If someone find something better...ungof and test:

```
pp(a:List Any):List Any==
  k:=#a;r:=copy[a];k<=1=>r;i:=1
  repeat
    i>=k=>break
    x:=a.(1..i);y:=a.((i+1)..k);z:=pp(y);
    t:=[x,z.1]
    for j in 2..#z repeat
           w:=(z.j)::List Any
           m:=#w; v:=[x]
           for q in 1..m repeat
                       v:=concat(v,w.q);
           t:=concat(t,[v])
    r:=concat(r,copy t);
    i:=i+1
  r

(7) -> px []
 (7)  [[]]
                                                           Type: List Any
(8) -> px [1]
 (8)  [[1]]
                                                           Type: List Any
(9) -> px [1,2]
 (9)  [[1,2],[[1],[2]]]
                                                           Type: List Any
(10) -> px [1,2,3]
 (10)  [[1,2,3],[[1],[2,3]],[[1],[2],[3]],[[1,2],[3]]]
                                                           Type: List Any
(11) -> px [1,2,3,4,5,6]
 (11)
[[1,2,3,4,5,6], [[1],[2,3,4,5,6]], [[1],[2],[3,4,5,6]],
 [[1],[2],[3],[4,5,6]], [[1],[2],[3],[4],[5,6]], [[1],[2],[3],[4],[5],[6]],
 [[1],[2],[3],[4,5],[6]], [[1],[2],[3,4],[5,6]], [[1],[2],[3,4],[5],[6]],
 [[1],[2],[3,4,5],[6]], [[1],[2,3],[4,5,6]], [[1],[2,3],[4],[5,6]],
 [[1],[2,3],[4],[5],[6]], [[1],[2,3],[4,5],[6]], [[1],[2,3,4],[5,6]],
 [[1],[2,3,4],[5],[6]], [[1],[2,3,4,5],[6]], [[1,2],[3,4,5,6]],
 [[1,2],[3],[4,5,6]], [[1,2],[3],[4],[5,6]], [[1,2],[3],[4],[5],[6]],
 [[1,2],[3],[4,5],[6]], [[1,2],[3,4],[5,6]], [[1,2],[3,4],[5],[6]],
 [[1,2],[3,4,5],[6]], [[1,2,3],[4,5,6]], [[1,2,3],[4],[5,6]],
 [[1,2,3],[4],[5],[6]], [[1,2,3],[4,5],[6]], [[1,2,3,4],[5,6]],
 [[1,2,3,4],[5],[6]], [[1,2,3,4,5],[6]]]
                                                           Type: List Any
(12) -> [[i,#px i] for i in [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5,6]] ]
 (12)
[[[],1],[[1],1],[[1,2],2],[[1,2,3],4],[[1,2,3,4],8],[[1,2,3,4,5,6],32]]
                                                      Type: List List Any
(13) -> [#px(i) for i in [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5,6]] ]
 (13)  [1,1,2,4,8,32]
                                            Type: List NonNegativeInteger

```

If this is too much space say that and I remove examples...

---
Tags: code-golf, array, combinatorics, set-partitions
---


# Question
Title: Find the Missing Numbers in the Fibonacci Sequence Mod K
Inspired by this Math.SE question.

# Background

The Fibonacci Sequence (called `F`) is the sequence, starting `0, 1` such that each number (`F(n)`) (after the first two) is the sum of the two before it (`F(n) = F(n-1) + F(n-2)`).

A Fibonacci Sequence mod K (called `M`) is the sequence of the Fibonacci numbers mod K (`M(n) = F(n) % K`).

It can be shown that the Fibonacci Sequence mod K is cyclic for all K, as each value is determined by the previous pair, and there are only K2 possible pairs of non-negative integers both less than K. Because the Fibonacci sequence mod K is cyclic after its first repeated pair of terms, a number which doesn't appear in the Fibonacci Sequence mod K before the first repeated pair of terms will never appear.

For K = 4

```
0 1 1 2 3 1 **0 1** ...
```

For K = 8

```
0 1 1 2 3 5 0 5 5 2 7 1 **0 1** ...
```

Notice that for K = 8, 4 and 6 do not appear before the repeated `0 1`, so 4 and 6 will never appear in the Fibonacci Sequence mod 8.

# Challenge

Given an integer K strictly greater than 0, output all of the non-negative integers less than K that *do not* appear in the Fibonacci Sequence mod K.

# Rules

* Default loopholes are forbidden.
* Default I/O.
* Programs or functions are acceptable.
* You can assume that *K* will fit in your native integer type (within reason).
* If there are non-negative numbers less than K that do not appear in the Fibonacci Sequence mod K, your program/function should output all such numbers in any reasonable manner.
* If there are no non-negative integers less than K that do not appear in the Fibonacci Sequence mod K, your program/function may indicate this by returning an empty list, printing nothing, producing an error, etc.
* Order does not matter.
* This is , so shortest answer in each language wins.

# Test Cases

Generate test cases online!

## Non-Empty Test Cases

```
  8 [4, 6]
 11 [4, 6, 7, 9]
 12 [6]
 13 [4, 6, 7, 9]
 16 [4, 6, 10, 12, 14]
 17 [6, 7, 10, 11]
 18 [4, 6, 7, 9, 11, 12, 14]
 19 [4, 6, 7, 9, 10, 12, 14]
 21 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 19]
 22 [4, 6, 7, 9, 15, 17, 18, 20]
 23 [4, 7, 16, 19]
 24 [4, 6, 9, 11, 12, 14, 15, 18, 19, 20, 22]
 26 [4, 6, 7, 9, 17, 19, 20, 22]
 28 [10, 12, 14, 16, 18, 19, 23]
 29 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27]
 31 [4, 6, 9, 12, 14, 15, 17, 18, 19, 22, 25, 29]
 32 [4, 6, 10, 12, 14, 18, 20, 22, 26, 28, 30]
 33 [4, 6, 7, 9, 15, 17, 18, 20, 24, 26, 27, 28, 29, 31]
 34 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 28, 30]
 36 [4, 6, 7, 9, 10, 11, 12, 14, 16, 18, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32]
 37 [9, 10, 14, 17, 20, 23, 27, 28]
 38 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 36]
 39 [4, 6, 7, 9, 15, 17, 19, 20, 22, 24, 30, 32, 33, 35]
...
200 [4, 6, 12, 14, 20, 22, 28, 30, 36, 38, 44, 46, 52, 54, 60, 62, 68, 70, 76, 78, 84, 86, 92, 94, 100, 102, 108, 110, 116, 118, 124, 126, 132, 134, 140, 142, 148, 150, 156, 158, 164, 166, 172, 174, 180, 182, 188, 190, 196, 198]
...
300 [6, 18, 30, 42, 54, 66, 78, 90, 102, 114, 126, 138, 150, 162, 174, 186, 198, 210, 222, 234, 246, 258, 270, 282, 294]
...
400 [4, 6, 10, 12, 14, 20, 22, 26, 28, 30, 36, 38, 42, 44, 46, 52, 54, 58, 60, 62, 68, 70, 74, 76, 78, 84, 86, 90, 92, 94, 100, 102, 106, 108, 110, 116, 118, 122, 124, 126, 132, 134, 138, 140, 142, 148, 150, 154, 156, 158, 164, 166, 170, 172, 174, 180, 182, 186, 188, 190, 196, 198, 202, 204, 206, 212, 214, 218, 220, 222, 228, 230, 234, 236, 238, 244, 246, 250, 252, 254, 260, 262, 266, 268, 270, 276, 278, 282, 284, 286, 292, 294, 298, 300, 302, 308, 310, 314, 316, 318, 324, 326, 330, 332, 334, 340, 342, 346, 348, 350, 356, 358, 362, 364, 366, 372, 374, 378, 380, 382, 388, 390, 394, 396, 398]
...

```

## Empty Test Cases (no output, error, empty list, etc. is acceptable output)

```
1, 2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35 ... 100 ...

```

### Related:

Counting Fibonacci Orbits

Find the Pisano Period

# Answer
> 6 votes
# Haskell, 70 bytes

*Some amount of bytes saved thanks to Esolanging Fruit*

*8 bytes saved thanks to Laikoni*

```
a=1:scanl(+)1a
f x=[u|u<-[2..x-1],and[mod b x/=u|(_,b)<-zip[1..x^2]a]]

```

Try it online!

# Answer
> 6 votes
# Jelly, ~~9~~ 8 bytes

```
²RÆḞ%ḟ@Ḷ

```

Try it online!

Based on the pisano period `p(n) <= 6n` from A001175. Also, `p(n) <= 6n <= n^2` for `n >= 6` and `p(n) <= n^2` for `n < 6`. Saved this byte thanks to Dennis.

# Answer
> 5 votes
# Perl 6,  ~~43 42 39~~  32 bytes

```
{^$_ (-)(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}

```

Test it

```
{^$_∖(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}

```

Test it

```
{^$_∖(1,1,(*+*)%$_...{!$^a&&$^b==1})}

```

Test it

```
{^$_∖(1,1,(*+*)%$_...!*&*==1)}

```

Test it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  ^$_               # Range upto and excluding the input

  ∖                 # set minus (U+2216)

  (                 # generate the Fibonacci sequence mod k

    1, 1,           # seed the sequece (can't be 0,1)

    ( * + * ) % $_  # add two values and modulus the input (lambda)

    ...             # keep doing that until

                    # it matches 0,1
    !*              #   negate the first param (1 when 0)
    &               #   and Junction
    *               #   second param
    == 1            #   both match 1

  )
}

```

# Answer
> 3 votes
# \>\<\>, 48 bytes

```
01\
?!\:&+{:}%:1$0p&$:
v0\~:1=?
>?!;1-::0g?!nao:

```

Try it online!

Takes input through the -v flag.

Prints a lot of excess newlines, but gets the job done. This basically uses the first line to store the set of numbers that have appeared so far in the sequence.

### How It Works:

```
01\    Input is already on the stack
...... Initialises the sequence with 1 and 0
...... Goes to the second line
......

......
..\:&+{:}% Gets the next number in the modded Fibonacci sequence while preserving the previous number
......
......

......
..........:1$0p&$: Puts a 1 at that cell number on the first line
.......
.......

......             If the number is a 0 go to the third line
?!\..............: Check if the next number is a 1, meaning we've reached the end of the sequence
v0\~:1=?           Go to the fourth line if so
>.....             Re-add the 0 and go back to the second line if not

......           While input:
......             Get the cell from the first line
......             If not 0: print the number
>?!;1-::0g?!nao:   Finally, print a newline and decrement the input

```

# Answer
> 3 votes
# Python 2, 69 bytes

```
m=input();r=set(range(m))
a=b=1
exec"a,b=b,a+b;r-={a%m};"*m*6
print r

```

Try it online!

# Answer
> 3 votes
# MATL, ~~19~~ 18 bytes

```
0lbU:"yy+]vG\G:qX~

```

Try it online!

-1 byte thanks to Guiseppe.

```
  bU:"   ]         % Do K^2 (>6K) times.
0l    yy+          %  Fibbonaci
                X~ % Set exclusive difference between
          vG\      %  the fibonacci numbers mod K
             G:q   %  and 0...K-1

```

# Answer
> 2 votes
# Husk, ~~13 12~~ 10 bytes

Thanks @Zgarb for -2 bytes!

```
-U2m%⁰İfŀ⁰

```

Prints an empty list in case all integers appear, try it online!

### Explanation

```
-U2m%⁰İfŀ⁰  -- named argument ⁰, example with: 8
-           -- difference of
        ŀ⁰  -- | lowered range: [0,1,2,3,4,5,6,7]
            -- and
      İf    -- | Fibonacci sequence: [1,1,2,3,5,8,13,21,34,55,89,144,233,377…
   m%⁰      -- | map (modulo ⁰): [1,1,2,3,5,0,5,5,2,7,1,0,1,1…
 U2         -- | keep longest prefix until 2 adjacent elements repeats: [1,1,2,3,5,0,5,5,2,7,1,0,1]
            -- : [4,6]

```

# Answer
> 2 votes
# Python 3,~~173~~ ~~152~~ ~~143~~ 131 bytes

```
f=lambda n,m,a=0,b=1:a%m if n<=0else f(n-1,m,b,a+b)
p=lambda n,i=2,y={0}:y^{*range(n)}if f(i,n)==1>f(i-1,n)else p(n,i+1,y|{f(i,n)})

```

Special Thanks to @ovs.

Try It Online

How Does It Work?

The first function takes two parameters m and n, and it returns the nth Fibonacci number mod m. The second function loops through the Fibonacci numbers mod k and checks if 0 and 1 are repeated. It stores the numbers in a list and compares it with a list containing the numbers 1-n. The duplicate numbers are removed and the remaining numbers are returned.

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
L<InLÅfI%K

```

Try it online!

-3 bytes thanks to Emigna.

# Answer
> 2 votes
# Python 3, 91 bytes

```
lambda n:{*range(n)}-{*f(n*n,n)}
f=lambda c,m,l=[1,0]:f(c-1,m,[(l[0]+l[1])%m]+l)if c else l

```

Try it online!

# Answer
> 2 votes
# R, ~~92~~ 86 bytes

Thanks to @Giuseppe for saving 6 bytes!

```
function(k,n=!!0:2){while(any((z=tail(n,2))-n[1:2]))n=c(n,sum(z)%%k);setdiff(1:k-1,n)}

```

Try it online!

Pretty straightforward implementation (**previous version**, but same concept):

```
function(k,
         K=1:k-1,      #Uses default arguments to preset variables for legibility
         n=c(0,1,1)){  #(wouldn't change byte-count to put them in the body of the function)
    while(any((z=tail(n,2))!=n[1:2])) #Do as long as first 2 elements are not identical to last 2 elements
        n=c(n,sum(z)%%k) #Built the fibonacci mod k sequence
    K[!K%in%n] #Outputs integers < k if not in sequence.
}

```

# Answer
> 2 votes
# Python 3, 78 bytes

```
def m(K):M=0,1;exec(K*6*'M+=sum(M[-2:])%max(K,2),;'+'print({*range(K)}-{*M})')

```

Try it online!

Prints a set, so the output for empty test cases is `set()`, which is the empty set.

# Answer
> 2 votes
# Ruby, 47 bytes

```
->n{a=b=1;[*1...n]-(1..n*n).map{a,b=b,a+b;a%n}}

```

Try it online!

While it uses some of the same logic, this is not based off G B's Answer.

## Explanation:

```
->n{
  a=b=1;   # start sequence with 1,1
  [*1...n] # all the numbers from 1 to n-1 as an array
           # 0 is excluded as it should never be in the final answer
  -  # set operation; get all items in the first set and not in the second
  (1..n*n).map{ # n squared times
    a,b=b,a+b;  # assign next fibonacci numbers
    a%n         # return a fibonacci number mod n
  }    # Map to an array
}

```

# Answer
> 2 votes
# Common Lisp, 106 bytes

```
(lambda(k)(do((a 1 b)c(b 1(mod(+ a b)k)))((=(1- b)0 a)(dotimes(i k)(or(member i c)(print i))))(push a c)))

```

Try it online!

# Answer
> 2 votes
# Vyxal, 9 bytes

```
ʁ⁰²ɾ∆f⁰%F

```

Try it Online!

## How?

```
ʁ⁰²ɾ∆f⁰%F
           # (implicit input)
ʁ          # Exclusive zero range [0, n)
 ⁰²        # Input squared
   ɾ       # Inclusive one range [1, n]
    ∆f     # Nth fibonacci number (implicit vectorization)
      ⁰%   # Modulo with input
        F  # Remove all values from this list in the other list

```

# Answer
> 1 votes
# Ruby, ~~55~~ 53 bytes

```
->n{*a=0,b=1;(n*n).times{a<<(b+=a[-2])%n};[*1...n]-a}

```

Try it online!

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

```
n->[k|k<-[0..n-1],prod(i=0,n^2,k-fibonacci(i)%n)]

```

Try it online!

# Answer
> 1 votes
# Elixir,  ~~148~~ 144 bytes

```
 fn x->Enum.to_list(1..x-1)--List.flatten Enum.take_while Stream.chunk(Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end),2),&Enum.sum(&1)!=1end

```

Try it online!

Not an especially competitive answer, but was really fun to golf! Elixir is a pretty readable language, but an explanation for the the mess of characters in the middle follows.

---

This explanation is in two sections, the mod-fibonacci and the operating on it

Mod-fib:

```
Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end)

```

This returns an infinite stream of fibonacci mod `x`. It starts with an accumulator `{1,1}`, and applies the following operation ad infinitum: given accumulator `{p,n}`, output `p mod x` to the stream. Then, set the accumulator to `{n,p+n}`.

The rest:

```
fn x->                              Define a fxn f(x) that returns
  Enum.to_list(1..x-1)--            The numbers from 1..x-1 that are not in
  List.flatten                      The flattened list constructed by
    Enum.take_while                 Taking from mod-fib until
      Stream.chunk(                 A 2-size chunk
        Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end) (of mod fib)
        ,2)
      ,&Enum.sum(&1)!=1             sums to 1, representing [0,1] or [1,0]
end

```

# Answer
> 1 votes
# SNOBOL4 (CSNOBOL4), 153 bytes

```
 k =input
 a =table()
 y =1
i z =remdr(x + y,k)
 a<z> =1
 x =y
 y =z
 i =lt(i,k * 6) i + 1 :s(i)
o output =eq(a<o>) lt(o,k) o
 o =lt(o,k) o + 1 :s(o)
end

```

Try it online!

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

```
f=(n,a=0,b=1,q=[...Array(n).keys()])=>a*b+a-1?f(n,b,(a+b)%n,q,q[b]=0):q.filter(x=>x)

```

# Answer
> 1 votes
# Python 3, 76 bytes

```
def t(n,r=[1]):
 while n*n>len(r):r+=[sum(r[-2:])%n]
 return{*range(n)}-{*r}

```

This simply looks over the longest possible cycle of Fibonnaci numbers (n^2), and creates a list of all numbers that occur in that time. To simplify logic the numbers are stored modulo n.

---
Tags: code-golf, number, sequence, fibonacci, abstract-algebra
---


title: How many times do I break my own rule?

text:
# Question
Title: How many times do I break my own rule?
## Introduction:

In my recent *~~Strikethrough~~ the Word Search List* challenge I mentioned the following:

> When I do the word-search puzzles, I ***(almost)*** always go over the words in order, and strike them through one by one.

In some cases I do them in reversed order as a change of pace, although that doesn't matter too much right now. When I do them in the correct alphabetical order however, I sometimes already see the word after the one I'm currently searching for. In those cases, I usually 'sneakily' strike through that next word already, before I continue searching for the actual current word.

In almost™ all cases, this occurs when both words have the same starting letter, and the next word that I find accidentally is in a horizontal left-to-right direction.

#### Brief explanation of what a word search is:

In a word search you'll be given a grid of letters and a list of words. The idea is to cross off the words from the list in the grid. The words can be in eight different directions: horizontally from left-to-right or right-to-left; vertically from top-to-bottom or bottom-to-top; diagonally from the topleft-to-bottomright or bottomright-to-topleft; or anti-diagonally from the topright-to-bottomleft or bottomleft-to-topright.

## Challenge:

Today's challenge is simple. Given a grid of letters and a list of words, output the maximum amount of times what I describe above can occur.

We do this with two steps:

1. Find all words from the given list which can be found in the grid in a horizontal left-to-right direction.
2. For each of those words, check if the word before it in the given list starts with the same letter.

**Example:**

```
Grid:
JLIBPNZQOAJD
KBFAMZSBEARO
OAKTMICECTQG
YLLSHOEDAOGU
SLHCOWZBTYAH
MHANDSAOISLA
TOPIFYPYAGJT
EZTBELTEATAZ

Words:
BALL
BAT
BEAR
BELT
BOY
CAT
COW
DOG
GAL
HAND
HAT
MICE
SHOE
TOP
TOYS
ZAP

```

Horizontal left-to-right words:

Word-pairs of these horizontal left-to-right words, with its preceding word in the list:

```
Words:
BAT,BEAR   ← B
BEAR,BELT  ← B
CAT,COW    ← C
GAL,HAND
HAT,MICE
MICE,SHOE
SHOE,TOP

```

From these pairs, three start with the same letters, so the output is `3`.

## Challenge rules:

* As you may have noted above, we only look at the word directly preceding it. For the `BELT` in the example, `BALL`,`BAT`,`BEAR` are all three before it and start with a `B` as well, but we only look at the word directly preceding it (`BEAR` in this case), and the counter would only increase by 1 for the output.
* If the very first word in the list is a horizontal left-to-right word, there is obviously no word before it.
* The list of words is guaranteed to contain at least two words, and all words are guaranteed to be present in the given grid.
* You can take the inputs in any reasonable format. Could be from STDIN input-lines; as a list of lines; a matrix of characters; etc.
* You can optionally take the dimensions of the grid as additional input.
* All words are guaranteed to have at least two letters.
* You can assume each word is only once in the grid.
* You can assume the list of words are always in alphabetical order.

## General rules:

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

## Test cases:

```
Inputs:
JLIBPNZQOAJD
KBFAMZSBEARO
OAKTMICECTQG
YLLSHOEDAOGU
SLHCOWZBTYAH
MHANDSAOISLA
TOPIFYPYAGJT
EZTBELTEATAZ

BALL
BAT
BEAR
BELT
BOY
CAT
COW
DOG
GAL
HAND
HAT
MICE
SHOE
TOP
TOYS
ZAP

Output: 3

```

---

```
Inputs:
ABC
SRO
KAX

AB
ASK
ARB
ARX
AX

Output: 1

```

---

```
Inputs:
WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

BACKWARD
DIAGONAL
FIND
HORIZONTAL
RANDOM
SEEK
SLEUTH
VERTICAL
WIKIPEDIA
WORDSEARCH

Output: 1

```

---

```
AYCD
EFGH
DCBA

ABC
AYC
CB
CBA
CD
EF
EFGH

Output: 4

```

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

-3 thanks to @KevinCruijssen (take the wordsearch as a mulitline list of characters).

```
=Ḣ¥ƝŻḋẇ€

```

A dyadic Link that accepts the list of words on the left and the wordsearch (a multiline list of characters) on the right and yields a non-negative integer.

**Try it online!**

### How?

```
=Ḣ¥ƝŻḋẇ€ - Link: words W (list of lists of characters); wordsearch P (list of characters)
   Ɲ     - for neighbouring words in W:
  ¥      -   last two links as a dyad - f(left, right):
=        -     left equals right (vectorises)
 Ḣ       -     head
    Ż    - prepend a zero
           -> E = a list of 1s and 0s identifying whether the previous
                  word stated with the same letter.
       € - for each Word in W:
      ẇ  -   is Word a sublist of P?
           -> F = a list of 1s and 0s identifying whether the current
                  word is in the wordsearch
     ḋ   - E dot-product F

```
> 4 votes

# Answer
# , ~~73~~ ~~69~~ 68 bytes

*Edit: -1 byte thanks to pajonk*

```
function(g,w)sum((c(l<-substr(w,1,1),T)==c(T,l))[sapply(w,grepl,g)])

```

Try it online!

Function with arguments `g`=grid, as a single string with each line in the grid separated by spaces (newlines would also be fine), and `w`=words, as a vector of individual words.
> 5 votes

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

```
lambda n,k:sum(a[0]==b[0]*(b in n)for a,b in zip(k,k[1:]))

```

Try it online!

Takes the grid (`n`) as a string that includes newlines, and the list of words (`k`) as a... list of words.

Simple. Find the number of consecutive pairs in `k` that have the same starting letter and where the second word in the pair is in the grid. The grid is a newline string, so if a word is present horizontally, then somewhere in the grid, there is a run of letters equal to that word that is not cut off by any newline.
> 4 votes

# Answer
# Charcoal, 33 bytes

```
ＷＳ⊞υι≔⁰θＷＳ«≧⁺∧№⪫υ¶ι⁼§ι⁰ψθ≔§ι⁰ψ»Ｉθ

```

Try it online! Link is to verbose version of code. Takes both grid and list as a newline-terminated list of newline-separated strings. Explanation:

```
ＷＳ⊞υι

```

Read in the grid.

```
≔⁰θ

```

Start with no matching words.

```
ＷＳ«

```

Loop through the list.

```
≧⁺∧№⪫υ¶ι⁼§ι⁰ψθ

```

If the current word is a left-to-right word and its first letter is the same as that of the previous word then increment the count.

```
≔§ι⁰ψ

```

Save the first letter of this word for the next iteration of the loop.

```
»Ｉθ

```

Output the final count.
> 2 votes

# Answer
# , 36 31 bytes

```
1#.(0,2=&{.&>/\[)*1#.,@E.&>/@,:

```

Try it online!

*-5 stealing dominic's idea of taking the matrix lines as a single space-delimited string*
> 2 votes

# Answer
# Vyxal, 13 bytes

```
2lƛvh≈⁰ẋntc;∑

```

Try it Online or run all the test cases.

## How?

```
2lƛvh≈⁰ẋntc;∑
2l            # Get a list of overlapping pairs in the (implicit) first input
  ƛ           # Map over them:
   vh         # Get the first character of both
     ≈        # Are they equal?
      ⁰       # Push the second input
       ẋ      # Repeat (so if the first characters are not equal, empty string, else second input)
        n     # Push the pair again
         t    # Get the second item in the pair
          c   # Does the other string contain this string?
           ;  # Close map lambda
            ∑ # Summate

```
> 2 votes

# Answer
# Retina 0.8.2, 25 bytes

```
&`((.).+).*;.*\b\2.+,\1\b

```

Try it online! Takes input as two semicolon-separated comma-delimited lists but link includes header that converts from newline-separated for convenience. Explanation:

```
&`

```

Count the number of overlapping matches (except only match once at any given starting position).

```
((.).+).*;

```

Match a word in the grid.

```
.*\b\2.+

```

Check that its first letter appears in another word in the list.

```
,\1\b

```

Check that the word appears in the list.
> 1 votes

# Answer
# 05AB1E, 12 bytes

```
ü2ε€нË×yθå}O

```

Since there hasn't been a 05AB1E answer yet, I'm gonna post my prepared solution.

First input is a list of words; second the grid as a multi-line string.

Try it online or verify all test cases.

**Explanation:**

```
ü2         # Create overlapping pairs of the first (implicit) input-list of words
  ε        # Map over each overlapping pair:
   €       #  Map over both words:
    н      #   Only leave their first character
     Ë     #  Check if both first characters are the same
      ×    #  Repeat the second (implicit) input-grid by that check
           #  (so the grid itself if truthy, or an empty string if falsey)
       y   #  Push the pair of words again
        θ  #  Pop and leave the last word
         å #  Check if its in the grid (or empty string)
  }O       # After the map: sum to get the amount of truthy values
           # (after which the result is output implicitly)

```
> 1 votes

---
Tags: code-golf, string, number, grid, word-search
---


title: Pair my brackets

text:
# Question
Title: Pair my brackets
Given a string consisting of `()[]{}`, print the paired brackets in the same order as they appear in the string.
Any opening bracket `([{` can be paired with any closing bracket `)]}`.

For example:

```
({()[}]]
returns:
(], {], (), [}

```

# Rules

* A string consisting of `()[]{}` should be received as the input
* The bracket-pairs should be returned as a list, or separated by a distinct character (or nothing), etc.
* The bracket-pairs should be in the same order as the starting brackets in the string
* The brackets will be balanced, i.e. the number of opening brackets and the number of the closing brackets will be the same
* Default Loopholes apply
* This is , so the shortest code wins!

# Examples

```
[In]: ()
[Out]: ()

[In]: (}{]
[Out]: (}, {]

[In]: ([{}])
[Out]: (), [], {}

[In]: {]([(}]{)}
[Out]: {], (}, [], (}, {)

```

# Answer
# x86-64 machine code, ~~16~~ 15 bytes

```
57 57 AA 5A 88 02 AC 3C 22 7B F8 AA 79 F2 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string; and the address of the input, as a null-terminated byte string, in RSI. The starting point is after the first 6 bytes.

In assembly:

```
s:  push rdi        # (Left brackets) Push the current output address
    push rdi        #                  onto the stack twice.
    stosb           # Add AL to the output string again as a placeholder,
                    #  advancing the pointer.
                    #         (Right brackets enter here.)
r:  pop rdx         # Pop from the stack into RDX.
    mov [rdx], al   # Place AL at that address.
                    # For right brackets, this puts them in the spot reserved previously.
                    # For left brackets, this does nothing: the value there is the same.
f:                  #     (START HERE.)
    lodsb           # Load a byte from the input string into AL, advancing the pointer.
    cmp al, 0x22    # Set flags from that number minus 0x22.
    jpo r           # Jump if it has an odd number of 1 bits, true for right brackets.
    stosb           # (Left & null) Add AL to the output string, advancing the pointer.
    jns s           # Jump if the result was nonnegative.
    ret             # (Null terminator) Return.

```
> 11 votes

# Answer
# Brain-Flak, 144 bytes

```
{(({}(<()>))<<>(()()()()){(({})){<>({}[()])}{}}>)<>({}[{}])((){[()](<{}>)}){{}{}<>(<({}<<>{({}<>)<>}{}>)>)}{}<>{({}<>)<>}{}}<>{({}<({}<>)>)<>}<>

```

Try it online!

Every bracket matching challenge needs a Brain-Flak submission.

```
# For each character in the input
{

  # Push zero below character, and keep another copy of character on third stack
  (({}(<()>))<

    # Compute character mod 4
    <>(()()()()){(({})){<>({}[()])}{}}

  # Push character back onto left stack
  >)

  # Is character equal to 1 mod 4?
  <>({}[{}])

  # If so:
  ((){[()](<{}>)}){

    {}{}<>(<({}<

      # Move to first 0 in right stack
      <>{({}<>)<>}{}

    # Push character, along with zero to break conditional
    >)>)

  }{}

  # Move elements back to right stack (or move character above an earlier pushed zero if was opening bracket)
  <>{({}<>)<>}{}

}

# Move bracket pairs to left stack to output in correct order
<>{({}<({}<>)>)<>}<>

```
> 8 votes

# Answer
# Python, ~~77~~ 72 bytes

Returns a string without separators.

```
f=lambda s,a='':s and f(s[:-1],(r:=s[-1]+a)[(q:=6-ord(s[-1])&2):])+r[:q]

```

Attempt This Online!

`6-ord(x)&2` is 2 for opening brackets and 0 for closing ones.
> 6 votes

# Answer
# 05AB1E, ~~17~~ 14 bytes

```
RvyžuykÈiìˆ]¯R

```

-3 bytes thanks to *@ovs*.

Try it online or verify all test cases.

**Explanation:**

```
R           # Reverse the (implicit) input
 v          # Pop and loop over each character `y`:
  y         #  Push the character
   žuykÈi   #  If the character is an opening bracket:
   žu       #   Push constant string "()<>[]{}"
     yk     #   Get the (0-based) index of the character in this string
       Èi   #   If this index is even:
         ì  #    Prepend the top two characters together
          ˆ #    Pop this pair and add it to the global array
 ]          # Close both the if-statement and loop
  ¯         # Push the global_array
   R        # Revert it
            # (after which it is output implicitly as result)

```
> 5 votes

# Answer
# Curry (PAKCS), 45 bytes

```
f[]=[]
f(a:b++c:d)|elem c")]}"=[a,c]:f b++f d

```

Try it online!
> 5 votes

# Answer
# Bash, 104 99 94 bytes

```
awk '/[[{(]/{s[i++]=NR$1;next}{a[j++]=s[i---1]$1}END{for(x in a)print a[x]}'|sort -n|tr -d 0-9

```

Try it online!

*-5 thanks to m90 for `tr` idea!*

Bash translation of my JS answer. Was a nicer fit for awk than JS.
> 4 votes

# Answer
## Pyth - 23 bytes

Uses the fact that all the closing brackets (and none of the opening brackets) are 1 modulo 4 in ascii.

```
tMt#S.e?t%Cb4aY,kb+.)Yb

tM                 map "removing the first element"
 t#                filter on a no-op (its no-op in this case)
  S                sort
   .e              map over enumerate (k is idx, b is element)
    ?              ternary (0 is falsey)
     t             subtract 1
      %   4        modulo 4
       Cb          convert b to char code
     aY            append to Y (Y is global starting at [])
      ,kb          [k, b]
     +             concatenate
      .)Y          pop from back of Y
      b

```

Try it online.
> 4 votes

# Answer
# MathGolf, ~~13~~ 11 bytes

```
x{_$4%┴┌Å▌¬

```

-2 bytes by outputting without delimiter, which is apparently allowed (see "*(or nothing)*" in the second rule)

Try it online.

**Explanation:**

```
x              # Reverse the (implicit) input-string
 {             # Foreach over each character:
               #  (implicitly push the current character we're looping over)
  _            #  Duplicate this character
   $4%┴┌Å      #  If this character is an opening bracket:
   $           #   Pop the copy, and push its codepoint-integer
    4%         #   Modulo-4
      ┴        #   Check if this is equal to 1
       ┌       #   Invert this boolean
        Å      #   Loop that many times,
               #   using 2 characters as inner code-block:
         ▌     #    Prepend the top two characters together
          ¬    #    Rotate the entire stack once towards the right
               # (implicitly output the entire stack joined together)

```

There are a bunch of alternatives possible for `4%┴┌Å▌¬`, like for example `Z+¶¿⌐▌¬`: try it online.

```
    Z+         #   Add 38 to the codepoint-integer
      ¶        #   Check if this is a prime number
       ¿       #   If this is truthy, thus a closing bracket:
        ⌐      #    Rotate the entire stack once towards the left
       ¿       #   Else:
        ▌      #    Prepend the top two characters together
         ¬     #   Then rotate the entire stack once towards the right

```
> 4 votes

# Answer
# Mathematica/Wolfram Language, 90 88 bytes

```
Transpose@MapAt[Reverse,GatherBy[Characters@#,Mod[First@ToCharacterCode@#,4]==1&]&@#,2]&

```

Uses the Mod-4 trick from the Pyth answer to split the characters into opening and closing brackets. Takes me 20 characters to reverse the closing list (so that the first opening bracket matches the last closing) which is annoying. Then, we transpose the lists and output. Shaved two characters by keeping the characters as characters and simply comparing their char codes. 11 more characters can be removed if we allow input as a list of chars instead of as a string.

Try it online!
> 4 votes

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

```
s=>s.map(c=>[c]).filter(c=>/[([{]/.test(c)?s.push(c):!s.pop().push(c[0]))

```

Try it online! I/O is lists of characters, but the examples in the footer convert from and to strings for convenience.
> 4 votes

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

```
s=>s.map(c=>s[/[[({]/.test(c)?s.push([c])-1:s.pop()[0]+=c]||[]).flat()

```

Try it online!

Input array of characters. The idea about reusing `s` as the stack is learnt from Neil's answer.
> 4 votes

# Answer
# PHP, 93 bytes

```
$i=0;foreach(str_split($argn)as$v){if(strpos(" ({[",$v)){$a.=$v;}else{echo"$a[$i]$v ";$i++;}}

```

Try it online!

Explanation: As opening brackets are encountered in the given string they're appended to a second string, then later paired up with closing brackets as the latter are encountered in the given string.
> 4 votes

# Answer
# Python3, 155 bytes:

```
lambda x:f(x)[0]
def f(s):
 t,r=[],[]
 while s and s[0]in'([{':
  if s[1]in')]}':t+=[s[:2],*r];r=[];s=s[2:]
  else:x,y=f(s[1:]);r+=x;s=s[0]+y
 return t+r,s

```

Try it online!
> 3 votes

# Answer
# Retina 0.8.2, 43 bytes

```
M!&`[({[](([({[])|(?<-2>).)*.
(.).+(.)
$1$2

```

Try it online! Link includes test cases. Explanation:

```
M!&`

```

List all overlapping matches...

```
[({[](([({[])|(?<-2>).)*.

```

... match an opening bracket, then any number of matched brackets, and then another character.

```
(.).+(.)
$1$2

```

Remove the inner matched brackets from each result.
> 3 votes

# Answer
# Ruby, 103 bytes

```
->d{s,a=[],[];i=-1;d.chars.map{|x|i+=1;/[\[{(]/=~x ?s<<[i,x]:[t=s.pop,t[1]+=x,a<<t]};a.sort.map{_1[1]}}
```

Attempt This Online!
> 3 votes

# Answer
# Charcoal, ~~24~~ 22 bytes

```
ＦＳ¿№)]}ιＵＭ⊟υι«ι⊞υＫＤ¹↙↙

```

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

```
ＦＳ

```

Loop over the characters in the input string.

```
¿№)]}ι

```

If this is a close bracket, then...

```
ＵＭ⊟υι«

```

... pop a peeked cell and replace it with the close bracket, otherwise:

```
ι

```

Output the open bracket.

```
⊞υＫＤ¹↙

```

Peek the cell now under the cursor, but as a list whose elements can be modified.

Move to the start of the next line.
> 3 votes

# Answer
# Jelly, ~~17~~ ~~15~~ 14 bytes

```
O’4ḍ-*Ä+ƲỤs2Ṣị

```

Try it online!

Function returning a list of pairs, or full program smash-printing with no separator. Uses Maltysen's mod 4 trick.

```
O’                 Decrement the codepoints of the input,
  4ḍ               and test divisibility by 4.
O’4ḍ               That is, for each bracket, is it closing?
    -*             Raise -1 to the power of each,
      Ä            take cumulative sums,
       +Ʋ          and add the ones back in.
O’4ḍ-*Ä+Ʋ          This gives the depth of each bracket.
         Ụ         Grade up: sort the indices by the obtained depths.
          s2       Split the indices into adjacent pairs,
            Ṣ      sort the pairs lexicographically,
             ị     and index back into the original list.

```
> 3 votes

# Answer
# C (gcc), ~~122~~ 111 bytes

*6 bytes, 1 byte, and 2 bytes saved thanks to @ceilingcat, @m90, and @ovs*

```
i;f(s,l,n)char*s,*n;{for(n=s;i+=~-(-*n&2)%~*n;n++);l-=printf("%c%c",*s,*n)+(n-++s?f(s,n-s),n-s:0);l&&f(n+1,l);}

```

Try it online! Takes input as a pointer to a character array and its length `f(array,length)` (the third parameter is unused). Outputs the mashed-together brackets to stdout.
> 3 votes

# Answer
# Julia, 60 bytes

```
!x=x>"" ? !((m=match(r"(.*)([([{].)(.*)",x))[1]m[3])m[2] : x
```

Attempt This Online!

Similar to other answers, using a regex to capture the last open bracket + the next character
> 3 votes

# Answer
# JavaScript (Node.js), 123 113 129 bytes

```
d=>(s=a=[],[...d].map((x,i)=>/[[{(]/.test(x)?s=[...s,[i,x]]:a.push((t=s.pop(),t[1]+=x,t))),a.sort((a,b)=>a[0]-b[0]).map(x=>x[1]))

```

Try it online!

*-10 thanks to Steffan!*

*+16 thanks to allxy for pointing out I need to explicitly specify numeric sort*

Uses a stack `s` which tracks open characters along with their index of occurence. On each close character, moves the top stack element to an answer array `a`, modifying it to include the close character. At the end, sorts according to start index and returns the pairs.
> 2 votes

# Answer
# Perl 5, 59 bytes

```
sub{$_=pop;1while s/(.*)([({[][)}\]])/unshift@_,$2;$1/e;@_}

```

Try it online!
> 2 votes

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

```
f=lambda s:s and f(s[:(q:=len(s.strip(']})'))-1)]+s[q+2:])+s[q:q+2]

```

Try it online!

Finds the rightmost opening bracket, which by definition must be paired with a closing bracket. Then, it recursively prepends the remaining brackets in the same way.
> 2 votes

# Answer
# APL(Dyalog Unicode), 45 bytes SBCS

while this does change the order of brackets i found this approch very intersting

```
{{⍵[a,⍨(⍳≢⍵)~a←0 1+1⍳⍨2-/⍵∊'({[']}⍣(2÷⍨≢⍵)⊢⍵}

```

explanation

```
{f⍣n⊢⍵} ⍝ rubs the function f , n tikes which half its length

0 1+1⍳⍨2-/⍵∊'({[' ⍝ finds the index of first pair of brackets

a,⍨(⍳≢⍵)~a ⍝ puts those brackets at the end of the array

```

Try it on APLgolf!

A full program which \____.
> 1 votes

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


title: Mandelbrot image in every language

text:
# Question
Title: Mandelbrot image in every language
I always used a Mandelbrot image as the 'graphical' version of Hello World in any graphical application I got my hands on. Now it's your guys' turn.

* Language must be capable of graphical output or drawing charts (saving files disallowed)
* Render a square image or graph. The size at least 128 and at most 640 across\*
* The fractal coordinates range from approximately -2-2i to 2+2i
* The pixels outside of the Mandelbrot set should be colored according to the number of iterations before the magnitude exceeds 2 (excluding\* black & white)
* Each iteration count must have a unique color\*, and neighboring colors should preferably be easily distinguishable by the eye
* The other pixels (presumably inside the Mandelbrot set) must be colored either black or white
* At least 99 iterations
* ASCII art not allowed

<sup>* unless limited by the platform, *e.g.* graphical calculator</sup>

Allowed:
Disallowed:
(shrunken images)

**Winning conditions:**

Shortest version (size in bytes) for each language will get a mention in this post, ordered by size.
No answer will ever be 'accepted' with the button.

**Leaderboard:**

```
/* Configuration */

var QUESTION_ID = 23423; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 17419; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body {
  text-align: left !important;
  display: block !important;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

# Answer
# Sharp EL-9300 Graphics Calculator, 296 bytes

This was my secondary school graphing calculator, getting on for 20 years ago! I remember writing a mandelbrot generator for it way back then. And sure enough, its still sitting there in the NV memory:

```
ClrG
DispG
Range -2.35,2.35,.5,-1.55,1.55,0.5
y=-1.55
Label ly
x=-2.35
Label lx
n=1
zx=0
zy=0
Label ln
tzx=zx²-zy²+x
zy=(2*zx*zy)+y
zx=tzx
If zx²+zy²>4Goto esc
n=n+1
If n<20Goto ln
Label esc
If fpart (n/2)=0Goto npl
Plot x,y
Label npl
x=x+.05
If x<=2.35Goto lx
y=y+.05
If y<=1.55Goto ly
Wait

```

It took about 90 minutes to render.

This is totally ungolfed. I'm sure I could save a bit of space, but I just wanted to share this historical curiosity!

I love that the only control statements available are `goto`s.

Here's a photo. I don't have any other means to get the graphical output out:
> 108 votes

# Answer
I came across this the other day. I don't take credit for it, but damn, is it awesome:

Python 2:

```
_                                      =   (
                                        255,
                                      lambda
                               V       ,B,c
                             :c   and Y(V*V+B,B,  c
                               -1)if(abs(V)<6)else
               (              2+c-4*abs(V)**-0.4)/i
                 )  ;v,      x=1500,1000;C=range(v*x
                  );import  struct;P=struct.pack;M,\
            j  ='<QIIHHHH',open('M.bmp','wb').write
for X in j('BM'+P(M,v*x*3+26,26,12,v,x,1,24))or C:
            i  ,Y=_;j(P('BBB',*(lambda T:(T*80+T**9
                  *i-950*T  **99,T*70-880*T**18+701*
                 T  **9     ,T*i**(1-T**45*2)))(sum(
               [              Y(0,(A%3/3.+X%v+(X/v+
                               A/3/3.-x/2)/1j)*2.5
                             /x   -2.7,i)**2 for  \
                               A       in C
                                      [:9]])
                                        /9)
                                       )   )

```

http://preshing.com/20110926/high-resolution-mandelbrot-in-obfuscated-python/
> 91 votes

# Answer
## LaTeX, 673 bytes

```
\countdef\!1\!129\documentclass{article}\usepackage[margin=0pt,papersize=\!bp]{geometry}\usepackage{xcolor,pgf}\topskip0pt\offinterlineskip\def~{99}\let\rangeHsb~\countdef\c2\countdef\d3\countdef\e4\begin{document}\let\a\advance\let\p\pgfmathsetmacro\makeatletter\def\x#1#2#3{#10
\@whilenum#1<#2\do{#3\a#11}}\d0\x\c{\numexpr~+1}{\expandafter\edef\csname\the\c\endcsname{\hbox{\noexpand\color[Hsb]{\the\d,1,1}\/}}\a\d23
\ifnum\d>~\a\d-~\fi}\def\/{\rule{1bp}{1bp}}\x\c\!{\hbox{\x\d\!{\p\k{4*\d/(\!-1)-2}\p\K{2-4*\c/(\!-1)}\def\z{0}\def\Z{0}\x\e~{\p\:{\z*\z-\Z*\Z+\k}\p\Z{2*\z*\Z+\K}\let\z\:\p\:{\z*\z+\Z*\Z}\ifdim\:pt>4pt\csname\the\e\endcsname\e~\fi}\ifnum\e=~\/\fi}}}\stop

```

> (129 × 129)

The PDF image consists of colored square units with size 1bp × 1bp.

## Ungolfed

```
% count register \size contains the width and height of the square
\countdef\size=1
\size=31
\documentclass{article}
\usepackage[margin=0pt,papersize=\size bp]{geometry}
\usepackage{xcolor,pgf}
\topskip0pt
\offinterlineskip
\def\iterations{99}
\let\rangeHsb\iterations
\countdef\c2
\countdef\d3
\countdef\e4
\begin{document}
\let\p\pgfmathsetmacro
\makeatletter
% \Loop: for (#1 = 0; #1 < #2; #1++) {#3}
\def\Loop#1#2#3{%
  #1=0
  \@whilenum#1<#2\do{#3\advance#11}%
}
\d0%
\Loop\c{\numexpr\iterations+1\relax}{%
  \expandafter\edef\csname\the\c\endcsname{%
    \hbox{\noexpand\color[Hsb]{\the\d,1,1}\noexpand\pixel}%
  }%
  \advance\d23 \ifnum\d>\iterations\advance\d-\iterations\fi
}
\def\pixel{\rule{1bp}{1bp}}
% \c: row
% \d: column
% \e: iteration
\Loop\c\size{%
  \typeout{c: \the\c}%
  \hbox{%
    \Loop\d\size{%
      \pgfmathsetmacro\k@re{4*\d/(\size-1)-2}%
      \pgfmathsetmacro\K@im{2-4*\c/(\size-1)}%
      \def\z@re{0}%
      \def\Z@im{0}%
      \Loop\e\iterations{%
         % calculate z(n+1) = z^2(n) + k
         \pgfmathsetmacro\temp{\z@re*\z@re-\Z@im*\Z@im+\k@re}%
         \pgfmathsetmacro\Z@im{2*\z@re*\Z@im+\K@im}%
         \let\z@re\temp
         % calculate abs(z)^2
         \pgfmathsetmacro\temp{\z@re*\z@re+\Z@im*\Z@im}%
         \ifdim\temp pt>4pt\csname\the\e\endcsname\e\iterations\fi
      }%
      \ifnum\e=\iterations\pixel\fi
    }%
  }%
}
\stop

```
> 54 votes

# Answer
## x86 DOS Assembly, ~~208~~ ~~177~~ 173 bytes

The full binary, in HEX, that I created by hand, is:

```
DBE3BE00A0B81300CD1056BA640007BF87F9FDBDC7008BCDE81A008AC3AA4979F7B9C70083EF784D79EE33C0CD16B80300CD10CD208BC12BC289441CDF441CDF06A701DEF9D95C088BC52BC289441CDF441CDF06A701DEF9D95C0CD9EED914D95404D95410D95C14B301D904D84C04DE0EA901D8440CD95404D94410D86414D84408D914D80CD95C10D84C04D95414D84410DF06AB01DED99BDFE09B9E7207433ADA72C632DBC3320002000400

```

The sample image is:

The full source in readable ASM is fairly long (I used this to figure out how I was coding this sucker):

```
.286
CODE SEGMENT
ASSUME CS:code, DS:code
ORG 0100h

; *****************************************************************************
start:
  ; Mandlebrot coordinates
  zr   = DWORD PTR [SI+0]
  zi   = DWORD PTR [SI+4]
  cr   = DWORD PTR [SI+8]
  ci   = DWORD PTR [SI+12]
  zrsq = DWORD PTR [SI+16]
  zisq = DWORD PTR [SI+20]

  ; Temp int
  Temp = WORD PTR  [SI+28]

  ; ===========================================================================
  ; Initialize

  ; Initialize the FPU
  FNINIT

  ; SI points to our memory
  mov si, 0A000h ; So we can push it

  ; Shave off some bytes by reusing 100
  mov dx, 100

  ; Switch to MCGA
  mov ax, 013h
  int 010h

  ; ES:DI is the end of our drawing area
  push si
  pop es
  mov di, 63879
  std ; We're using stosb backwards

  ; Initialize our X and Y
  mov bp, 199
  mov cx, bp

  ; ===========================================================================
  ; Main draw loop

MainLoop:
  ; Get our next mandelbrot value
  call GMV

  ; Store it
  mov al, bl
  stosb

  ; Decrement our X
  dec cx
  jns MainLoop

  ; Decrement our Y
  mov cx, 199
  sub di, 120
  dec bp
  jns MainLoop

  ; ===========================================================================
  ; Done

  ; Wait for a key press
  xor ax, ax
  int 016h

  ; Change back to text mode
  mov ax, 3
  int 010h

  ; Exit to DOS
  int 020h

; *****************************************************************************
; GMV: Get Mandelbrot Value
; Gets the value for the next Mandelbrot pixel
; Returns:
;   BL - The color to use
GMV:
  ; ===========================================================================
  ; Initialize

  ; cr = (x - 100) / 50;
  mov ax, cx
  sub ax, dx                  ; \
  mov Temp, ax                ;  > ST0 = Current X - 100
  FILD Temp                   ; /
  FILD Divisor                ; ST0 = 50, ST1 = Current X - 100
  FDIVP                       ; ST0 = (Current X - 100) / 50
  FSTP cr                     ; Store the result in cr

  ; ci = (y - 100) / 50;
  mov ax, bp
  sub ax, dx                  ; \
  mov Temp, ax                ;  > ST0 = Current Y - 100
  FILD Temp                   ; /
  FILD Divisor                ; ST0 = 50, ST1 = Current Y - 100
  FDIVP                       ; ST0 = (Current Y - 100) / 50
  FSTP ci                     ; Store the result in ci

  ; zr = zi = zrsq = zisq = 0;
  FLDZ
  FST zr
  FST zi
  FST zrsq
  FSTP zisq

  ; numiteration = 1;
  mov bl, 1

  ; ===========================================================================
  ; Our main loop

  ; do {
GMVLoop:

  ; zi = 2 * zr * zi + ci;
  FLD zr
  FMUL zi
  FIMUL TwoValue
  FADD ci
  FST zi ; Reusing this later

  ; zr = zrsq - zisq + cr;
  FLD zrsq
  FSUB zisq
  FADD cr
  FST zr ; Reusing this since it already is zr

  ; zrsq = zr * zr;
  ;FLD zr ; Reused from above
  FMUL zr
  FSTP zrsq

  ; zisq = zi * zi;
  ;FLD zi ; Reused from above
  FMUL zi
  FST zisq ; Reusing this for our comparison

  ; if ((zrsq + zisq) < 4)
  ;   return numiteration;
  FADD zrsq
  FILD FourValue
  FCOMPP
  FSTSW ax
  FWAIT
  sahf
  jb GMVDone

  ;} while (numiteration++ < 200);
  inc bx
  cmp bl, dl
  jb GMVLoop

  ;return 0;
  xor bl, bl

GMVDone:
  ret
;GMV

; *****************************************************************************
; Data

; Divisor
Divisor DW 50
; Two Value
TwoValue DW 2
; 4 Value
FourValue DW 4

CODE ENDS
END start

```

This is designed for compiling with TASM, runs in MCGA, and waits for a keypress before ending the program. The colors are just the default MCGA palette.

**EDIT:** Optimized it, now it draws backwards (same image though), and saved 31 bytes!

**EDIT 2:** To assuage the OP, I have recreated the binary by hand. By doing so, I also shaved another 4 bytes off. I documented every single step of the process, showing all of my work so anybody can follow along if they really want to, here (warning, it's boring and very long): http://lightning.memso.com/media/perm/mandelbrot2.txt

I used a couple regex's in EditPadPro, to find all the `; Final: ...` entries in the file and dump them as hex binary to a .com file. The resulting binary is what you see at the top of this post.
> 40 votes

# Answer
## Java, ~~505~~ ~~405~~ 324 bytes

Just a standard calculation, ~~with golfitude~~ now with extra golfitude.

Golfed:

```
import java.awt.*;class M{public static void main(String[]v){new Frame(){public void paint(Graphics g){for(int t,s,n=640,i=n*n;--i>0;g.setColor(new Color(s*820)),g.drawLine(i/n,i%n+28,i/n,i%n),setSize(n,668)){float c=4f/n,a=c*i/n-2,b=i%n*c-2,r=a,e=b,p;for(s=t=99;t-->0&&r*r+e*e<4;s=t,p=r*r-e*e+a,e=r*e*2+b,r=p);}}}.show();}}

```

With line breaks:

```
import java.awt.*;
class M{
    public static void main(String[]v){
        new Frame(){
            public void paint(Graphics g){
                for(int t,s,n=640,i=n*n;--i>0;g.setColor(new Color(s*820)),g.drawLine(i/n,i%n+28,i/n,i%n),setSize(n,668)){
                    float c=4f/n,a=c*i/n-2,b=i%n*c-2,r=a,e=b,p;
                    for(s=t=99;t-->0&&r*r+e*e<4;s=t,p=r*r-e*e+a,e=r*e*2+b,r=p);
                }
            }
        }.show();
    }
}

```
> 27 votes

# Answer
# Javascript (ECMAScript 6) - ~~315~~ 308 Characters

```
document.body.appendChild(e=document.createElement("canvas"));v=e.getContext("2d");i=v.createImageData(e.width=e.height=n=600,n);j=0;k=i.data;f=r=>k[j++]=(n-c)*r%256;for(y=n;y--;)for(x=0;x++<n;){c=s=a=b=0;while(c++<n&&a*a+b*b<5){t=a*a-b*b;b=2*a*b+y*4/n-2;a=t+x*4/n-2}f(87);f(0);f(0);k[j++]=255}v.putImageData(i,0,0)

```

```
(d=document).body.appendChild(e=d.createElement`canvas`);v=e.getContext`2d`;i=v.createImageData(e.width=e.height=n=600,n);j=0;k=i.data;f=r=>k[j++]=(n-c)*r%256;for(y=n;y--;)for(x=0;x++<n;){c=s=a=b=0;while(c++<n&&a*a+b*b<5){t=a*a-b*b;b=2*a*b+y*4/n-2;a=t+x*4/n-2}f(87);f(0);f(0);k[j++]=255}v.putImageData(i,0,0)
```
* Change `n` to vary the image size (and number of iterations).
* Change the values passed in the `f(87);f(0);f(0);` calls (near the end) to change the RGB colour values. (`f(8);f(8);f(8);` is greyscale.)

With `f(8);f(23);f(87);`:

```
(d=document).body.appendChild(e=d.createElement`canvas`);v=e.getContext`2d`;i=v.createImageData(e.width=e.height=n=600,n);j=0;k=i.data;f=r=>k[j++]=(n-c)*r%256;for(y=n;y--;)for(x=0;x++<n;){c=s=a=b=0;while(c++<n&&a*a+b*b<5){t=a*a-b*b;b=2*a*b+y*4/n-2;a=t+x*4/n-2}f(8);f(23);f(87);k[j++]=255}v.putImageData(i,0,0)
```
> 21 votes

# Answer
# Mathematica, ~~214~~ ~~191~~ ~~215~~ ~~19~~ 30

Since version 10.0 there is a built-in: (19 bytes)

```
MandelbrotSetPlot[]

```

---

To conform to the coordinate range requirements, 11 additional bytes are required. (30 bytes)

```
MandelbrotSetPlot@{-2-2I,2+2I}

```

---

A hand-rolled case:

```
m=Compile[{{c,_Complex}},Length[FixedPointList[#^2+c&,0,99,SameTest→(Abs@#>=2&)]]];
ArrayPlot[Table[m[a+I b],{b,-2,2,.01},{a,-2,2,.01}],DataRange→{{-2,2},{-2,2}},
ColorRules→{100→Black},ColorFunction→(Hue[Log[34,#]]&)]

```
> 20 votes

# Answer
# J, 73 bytes

```
load'viewmat'
(0,?$~99 3)viewmat+/2<|(j./~i:2j479)(+*:) ::(3:)"0^:(i.99)0

```

**Edit**, some explaining:

```
x (+*:) y           NB. is x + (y^2)
x (+*:) ::(3:) y    NB. returns 3 when (+*:) fails (NaNs)
j./~i:2j479         NB. a 480x480 table of complex numbers in required range
v =: (j./~i:2j479)(+*:) ::(3:)"0 ]     NB. (rewrite the above as one verb)
v z0                NB. one iteration of the mandelbrot operation (z0 = 0)
v v z0              NB. one iteration on top of the other
(v^:n) z0           NB. the result of the mandelbrot operation, after n iterations
i.99                NB. 0 1 2 3 4 ... 98
(v^:(i.99))0        NB. returns 99 tables, one for each number of iterations
2<| y               NB. returns 1 if 2 < norm(y), 0 otherwise
2<| (v^:(i.99))0    NB. 99 tables of 1s and 0s
+/...               NB. add the tables together, element by element.
NB. we now have one 480x480 table, representing how many times each element exceeded norm-2.
colors viewmat M    NB. draw table 'M' using 'colors'; 'colors' are rgb triplets for each level of 'M'.
$~99 3              NB. 99 triplets of the numbers 99,3
?$~99 3             NB. 99 random triplets in the range 0 - 98 and 0 - 2
0,?$~99 3           NB. prepend the triplet (0,0,0): black

```
> 20 votes

# Answer
# Python with Pylab+Numpy, 151 bytes

I couldn't bear to see a non-DQ'ed Python entry, but I think I really outdid myself on this one, and I made it down to 153 characters!

```
import numpy as n
from pylab import*
i=99
x,y=n.mgrid[-2:2:999j,-2:2:999j]
c=r=x*1j+y
x-=x
while i:x[(abs(r)>2)&(x==0)]=i;r=r*r+c;i-=1
show(imshow(x))

```

Also, notably, the second to last line raises 4 distinct runtime warnings, a new personal record!
> 17 votes

# Answer
# C + Allegro 4.2.2 - 248 bytes

```
#include<allegro.h>
x=-1,y,K=400;float a,h,c,d,k;main(i){set_gfx_mode('SAFE',K,K,allegro_init(),0);while(x++<K)
for(y=0;y<K;y++){for(a=h=i=0;a*a+h*h<4&&++i<256;k=a,a=a*a-h*h+x*0.01-2,h=2*k*h+y*0.01-2);
putpixel(screen,x,y,i);}while(1);}END_OF_MAIN()

```

Output:
> 16 votes

# Answer
### Windows PowerShell (v4), 299 bytes

```
# Linewrapped here for show:

$M='System.Windows.Forms';nal n New-Object;Add-Type -A System.Drawing,$M;(
$a=n "$M.Form").backgroundimage=($b=n Drawing.Bitmap 300,300);0..299|%{
$r=$_;0..299|%{$i=99;$k=$C=n numerics.complex($_/75-2),($r/75-2);while(((
$k=$k*$k).Magnitude-lt4)-and$i--){$k+=$C}$b.SetPixel($_,$r,-5e6*++$i)}};$a.Show()

# The single line 299 char entry version:

$M='System.Windows.Forms';nal n New-Object;Add-Type -A System.Drawing,$M;($a=n "$M.Form").backgroundimage=($b=n Drawing.Bitmap 300,300);0..299|%{$r=$_;0..299|%{$i=99;$k=$C=n numerics.complex($_/75-2),($r/75-2);while((($k=$k*$k).Magnitude-lt4)-and$i--){$k+=$C}$b.SetPixel($_,$r,-5e6*++$i)}};$a.Show()

```

**Instructions**

* Run a normal PowerShell console (ISE might not work)
* Copy/paste code in, press Enter
* Wait - it takes a minute or more to run
* The only way to quit is to close the console

**Comment**

* There's a tiny bit of rule-testing going on with the colours inside the set; the rules say *"The other pixels (presumably inside the Mandelbrot set) must be colored either black or white'"*; the code is colouring the pixels completely black RGB(0,0,0) ... it just happens to be a transparent black RGBA(0,0,0,0). So what shows up is the form background colour of the current Windows theme, a slightly off-white RGB(240,240,240) in this case.
> 15 votes

# Answer
## Python + PIL, 166 bytes

```
import Image
d=600;i=Image.new('RGB',(d,d))
for x in range(d*d):
 z=o=x/9e4-2-x%d/150.j-2j;c=99
 while(abs(z)<2)*c:z=z*z+o;c-=1
 i.putpixel((x/d,x%d),5**8*c)
i.show()

```

Output (will open in the default \*.bmp viewer):
> 14 votes

# Answer
# BBC Basic (228 bytes)

What about languages that nobody ever heard of in code golf? Most likely could be optimized, but I'm not quite where - improvements possible. Based of http://rosettacode.org/wiki/Mandelbrot\_set#BBC\_BASIC, but I tried to code golf it as much as possible.

```
VDU23,22,300;300;8,8,8,8
ORIGIN0,300
GCOL1
FORX=0TO600STEP2
i=X/200-2
FORY=0TO300STEP2
j=Y/200
x=0
y=0
FORI=1TO128
IFx*x+y*y>4EXIT FOR
t=i+x*x-y*y
y=j+2*x*y
x=t
NEXT
COLOUR1,I*8,I*4,0
PLOTX,Y:PLOTX,-Y
NEXT
NEXT

```

The `>` symbol on image is prompt, and it's automatically generated after running the program.
> 13 votes

# Answer
# APL, 194 chars/bytes\*

```
m←{1{⍺=99:0⋄2<|⍵:⍺⋄(⍺+1)∇c+⍵*2}c←⍵}¨⍉v∘.+0j1×v←¯2+4÷s÷⍳s←640
'F'⎕WC'Form'('Coord' 'Pixel')('Size'(s s))
'B'⎕WC'Bitmap'('CMap'(0,,⍨⍪0,15+10×⍳24))('Bits'(24⌊m))
'F.I'⎕WC'Image'(0 0)('Picture' 'B')

```

This is for Dyalog APL with `⎕IO ⎕ML←1 3`

Most of the space is taken by API calls to show a bitmap in a window (lines 2, 3, 4)
If there was a shortcut to do it, the code would be down to 60 chars (line 1)

**Ungolfed version** (only line 1)

```
s←640            ⍝ size of the bitmap
v←(4×(⍳s)÷s)-2   ⍝ vector of s reals, uniform between ¯2 and 2
m←(0j1×v)∘.+v    ⍝ square matrix of complex numbers from ¯2j¯2 to 2j2
m←{              ⍝ transform each number in matrix m according to the following
  1{             ⍝   function that takes iteration counter as ⍺ and current value as ⍵
    ⍺=99: 0      ⍝     if we have done 99 iterations, return 0
    2<|⍵: ⍺      ⍝     if |⍵| > 2 return the number of iterations done
    (⍺+1)∇c+⍵*2  ⍝     otherwise, increment the iterations and recurse with the new value
  }c←⍵           ⍝   save the initial value as c
}¨m

```

**Screenshot:**

<sub>\*: Dyalog has its own single byte charset, with the APL symbols mapped to the upper 128 byte values, so the entire code can be stored in 194 bytes.</sub>
> 12 votes

# Answer
### R, ~~199~~ 211 characters

Old solution at 199 characters:

```
r=seq(-2,2,l=500);c=t(sapply(r,function(x)x+1i*r));d=z=array(0,dim(c));a=1:25e4;for(i in 1:99){z[a]=c[a]+z[a]^2;s=abs(z[a])<=2;d[a[!s]]=i;a=a[s]};image(d,b=0:99,c=c(1,sample(rainbow(98))),ax=F,asp=1)

```

With indentation:

```
r=seq(-2,2,l=500)
c=t(sapply(r,function(x)x+1i*r)) #Produces the initial imaginary number matrix
d=z=array(0,dim(c)) #empty matrices of same size as c
a=1:25e4            #(z will store the magnitude, d the number of iterations before it reaches 2)
for(i in 1:99){     #99 iterations
    z[a]=c[a]+z[a]^2
    s=abs(z[a])<=2
    d[a[!s]]=i
    a=a[s]
    }
image(d,b=0:99,c=c(1,sample(rainbow(98))),ax=F,asp=1) #Colors are randomly ordered (except for value 0)

```

**Edit:** Solution at 211 characters that colors the inside of the set and the outside of the first layer differently:

```
r=seq(-2,2,l=500);c=t(sapply(r,function(x)x+1i*r));d=z=array(0,dim(c));a=1:25e4;for(i in 1:99){z[a]=c[a]+z[a]^2;s=abs(z[a])<=2;d[a[!s]]=i;a=a[s]};d[a[s]]=-1;image(d,b=-1:99,c=c(1:0,sample(rainbow(98))),ax=F,asp=1)

```

With indentation:

```
r=seq(-2,2,l=500)
c=t(sapply(r,function(x)x+1i*r))
d=z=array(0,dim(c))
a=1:25e4
for(i in 1:99){
    z[a]=c[a]+z[a]^2
    s=abs(z[a])<=2
    d[a[!s]]=i
    a=a[s]
    }
d[a[s]]=-1 #Gives the inside of the set the value -1 to differenciate it from value 0.
image(d,b=-1:99,c=c(1,sample(rainbow(99))),ax=F,asp=1)

```
> 10 votes

# Answer
# Java - Processing (271 bytes)

```
void setup(){int h=100,e=5*h,i;float d,v,w,a,b,c;size(e,e);colorMode(HSB,h);loadPixels();d=4./e;v=2;for(int x=1;x<=e;x++){v-=d;w=2;for(int y=0;y<e;){w-=d;a=b=c=0;i=-1;while(a*a+b*b<4&&++i<h){c=a*a-b*b+v;b=2*a*b+w;a=c;}pixels[e*++y-x]=color(i*9%h,h,h-i);}}updatePixels();}

```

Expanded:

```
void setup(){
  int h=100, e=5*h, i; //init of size "e", max hue "h", iterator "i"
  float d,v,w,a,b,c; //init of stepwidth "d", y-coord "v", x-coord "w", Re(z) "a", Im(z) "b", temp_a "c"
  size(e,e);
  colorMode(HSB,h);
  loadPixels();
  d = 4./e;
  v = 2;
  for(int x = 1; x <= e; x++){
    v -= d;
    w = 2;
    for(int y = 0; y < e;){
      w -= d;
      a = b = c = 0;
      i = -1;
      while(a*a + b*b < 4 && ++i < h){
        c = a*a - b*b + v;
        b = 2*a*b + w;
        a = c;
      }
      pixels[e * ++y - x] = color(i*9 % h, h, h-i);
    }
  }
  updatePixels();
}

```
> 10 votes

# Answer
# Mathematica 10.0, 19 chars

```
MandelbrotSetPlot[]

```

`MandelbrotSetPlot` is a new function in Mathematica 10.0.
> 10 votes

# Answer
# TI-80 BASIC, ~~125~~ 106 bytes

```
ZDECIMAL
FOR(Y,-2,2,.1
FOR(X,-2,2,.1
0->S
0->T
1->N
LBL N
N+1->N
IF S²+T²≥4
GOTO B
S²-T²+X->I
2ST+Y->T
I->S
IF N<20
GOTO N
LBL B
IF FPART (N/2
PT-ON(X,Y
END
END

```

Based on Digital Trauma's answer.
> 10 votes

# Answer
# Applesoft BASIC, ~~302~~ ~~286~~ 280 bytes

This picks random points to draw, so it will run forever and may never fill in the full plane.

```
1HGR:POKE49234,0:DIMco(10):FORc=0TO10:READd:co(c)=d:NEXT:DATA1,2,3,5,6,1,2,3,5,6,0
2x=INT(RND(1)*280):y=INT(RND(1)*96):x1=x/280*3-2:y1=y/191*2-1:i=0:s=x1:t=y1
3s1=s*s-t*t+x1:t=2*s*t+y1:s=s1:i=i+1:IFs*s+t*t<4ANDi<20THENGOTO3
4c=co(i/2):IFc THENHCOLOR=c:HPLOTx,y:HPLOTx,191-y
5GOTO2

```

Turns out Applesoft BASIC is *really* forgiving about lack of spaces. Only one space is necessary in the entire program.

Output after 14 hours:

GIF:

Before golfing:

```
10 HGR : POKE 49234,0
20 DIM co(10) : FOR c = 0 TO 10 : READ d : co(c) = d : NEXT
30 DATA 1, 2, 3, 5, 6, 1, 2, 3, 5, 6, 0
100 x = INT(RND(1) * 280) : y = INT(RND(1) * 96)
110 x1 = x / 280 * 3 - 2 : y1 = y / 191 * 2 - 1
120 i = 0:s = x1:t = y1
130 s1 = s * s - t * t + x1
140 t = 2 * s * t + y1:s = s1: i = i + 1
150 IF s * s + t * t < 4 AND i < 20 THEN GOTO 130
160 c = co(i/2) : IF c THEN HCOLOR= c : HPLOT x,y : HPLOT x,191 - y
170 GOTO 100

```

Note: `POKE 49234,0` (in Applesoft BASIC) puts the machine into full graphics mode.

### A version optimized for B&W displays:

```
110 HGR:POKE 49234,0:HCOLOR=3
120 FOR x = 0 TO 279:FOR y = 0 TO 95
130 x1 = x / 280 * 3 - 2:y1 = y / 191 * 2 - 1
140 i = 0:s = x1:t = y1:c = 0
150 s1 = s * s - t * t + x1
160 t = 2 * s * t + y1:s = s1:c = 1 - c:i = i + 1
170 IF s * s + t * t < 4 AND i < 117 THEN GOTO 150
180 IF c = 0 THEN HPLOT x,y:HPLOT x,191 - y
190 NEXT:NEXT

```

Output after 12 hours:

### A version that will work in GW-BASIC (DOS):

```
5 CLS
6 SCREEN 1
20 DIM co(10) : FOR c = 0 TO 10 : READ d : co(c) = d : NEXT
30 DATA 1, 2, 3, 5, 6, 1, 2, 3, 5, 6, 0
100 x = INT(RND(1) * 280) : y = INT(RND(1) * 96)
110 x1 = x / 280 * 3 - 2 : y1 = y / 191 * 2 - 1
120 i = 0 : s = x1 : t = y1
130 s1 = s * s - t * t + x1
140 t = 2 * s * t + y1 : s = s1 : i = i + 1
150 IF s * s + t * t < 4 AND i < 20 THEN GOTO 130
160 c = co(i/2) : PSET (x,y),C : PSET (x,191 - y),C
170 GOTO 100

```
> 8 votes

# Answer
# , ~~140~~ ~~136~~ ~~128~~ ~~124~~ ~~123~~ ~~110~~ 109 bytes\*

```
image(outer(j<-1:396/99-2,j,Vectorize(function(x,y,n=99){while((n=n-1)&abs(F)<2)F=F*F+x+1i*y;n})),c=colors())

```

Try it at rdrr.io

6y after the Q was asked, but I love Mandelbrot sets, and the earlier R solution was 211 characters...

\*Or just 62 bytes as a pixel-shader function in ≥4.1:
`\(x,y,n=99){while((n=n-1)&abs(F)<2)F=F*F+x+1i*y;colors()[n+1]}`
> 8 votes

# Answer
## JavaScript, ~~284 283 ...(12 improvements)... 191 190 188~~ 199 bytes

<sup>currenty (2019-10-05) this is shortest js solution (the shortest one before this has 285 bytes)</sup>

Expanded

```
// Fractal calculations
c=512;

// p has pixels, p+= allways join 4 digit number implicit casted to string
// 4 char string interpred as base64 gives 3bytes = 1 RGB pixel
for( p=i=''; j=x=y=0,++i<=c*c; p+= j<c ? 9*c+9*j : 'AAAA' )
  while( x*x+y*y<4 && ++j-c )
    [x,y] = [ x*x-y*y+i%c/128-2, 2*x*y+i/c/128-2 ];

// draw pixels in 512x512 BMP base64 image
document.write("<img src=data:;base64,Qk0bAAwAAAAAABsAAAAMAAAAAAIAAgEAGAAA"+p)
```

After small constans changes

```
c=512;for(p=i='';j=x=y=0,++i<=c*c;p+=j<c?2*c+9*j:'AAAA')while(x*x+y*y<4&&++j-c)[x,y]=[x*x-y*y+i%c/128-2,2*x*y+i/c/128-2]
document.write("<img src=data:;base64,Qk0bAAwAAAAAABsAAAAMAAAAAAIAAgEAGAAA"+p)
```
> 7 votes

# Answer
# Octave (~~212~~ 136 bytes)

(Now including some ideas due to @ChrisTaylor.)

```
[y,x]=ndgrid(-2:.01:2);z=c=x+i*y;m=c-c;for n=0:99;m+=abs(z)<2;z=z.^2+c;end;imagesc(m);colormap([hsv(128)(1+mod(0:79:7890,128),:);0,0,0])

```

With whitespace:

```
[y,x] = ndgrid(-2:.01:2);
z = c = x + i*y;
m = c-c;
for n=0:99
    m += abs(z)<2;
    z = z.^2 + c;
end
imagesc(m)
colormap([hsv(128)(1+mod(0:79:7900,128),:);
          0,0,0])

```

Output:

To convert to Matlab, change "`m+=abs(z)<2`" to "`m=m+(abs(z)<2)`". \[+3 bytes\]

To make the aspect ratio 1:1, add "`;axis image`". \[+11 bytes\]

My first answer (212 bytes):

```
[x,y]=meshgrid(-2:.01:2);z=c=x+i*y;m=0*e(401);for n=0:99;m+=abs(z)<2;z=z.^2+c;endfor;t=[0*e(1,7);2.^[6:-1:0]];[s{1:7}]=ndgrid(num2cell(t,1){:});t=1+sum(cat(8,s{:}),8);imagesc(m);colormap([hsv(128)(t(:),:);0,0,0])

```
> 6 votes

# Answer
# GLSL - 225 bytes:

```
void main(){vec2 c=gl_FragCoord.xy/iResolution.y*4.-2.,z=c,v;for(int i=0;i<99;i++){z=vec2(z.x*z.x-z.y*z.y,2.*z.x*z.y)+c;if(length(z)>2.&&v.y<1.)v=vec2(float(i)/99.,1.);}gl_FragColor=(v.y<1.)?vec4(v,v):texture2D(iChannel0,v);}

```

Defining variables in the code (242 bytes):

```
uniform vec3 r;uniform sampler2D t;void main(){vec2 c=gl_FragCoord.xy/r.y*4.-2.,z=c,v;for(int i=0;i<99;i++){z=vec2(z.x*z.x-z.y*z.y,2.*z.x*z.y)+c;if(length(z)>2.&&v.y<1.)v=vec2(float(i)/99.,1.);}gl_FragColor=(v.y<1.)?vec4(v,v):texture2D(t,v);}

```

See it in ShaderToy

This requires a suitable palette texture be loaded as `iChannel0`. (The colouring here is from the "random pixel" texture on ShaderToy).
> 6 votes

# Answer
## PostScript, ~~290~~ ~~285~~ ~~282~~ ~~271~~ 261 bytes

#### Screenshot:

#### Golfed code:

```
-2 .01 2{/a exch def -2 .01 2{/b exch def/x 0 def/y 0 def 0 1 99{/i exch def x x mul y y mul add 4 ge{i log 2 div 1 1 sethsbcolor a 2 add 100 mul b 2 add 100 mul 1 1 rectfill exit}if/x x x mul y y mul sub a add/y 2 x mul y mul b add def def}for}for}for showpage

```

#### Ungolfed code:

```
-2 .01 2 {
    /a exch def
    -2 .01 2 {
        /b exch def
        /x 0 def
        /y 0 def
        0 1 99 {
           /i exch def                       % iteration count
           x x mul y y mul add 4 ge {
               i log 2 div 1 1 sethsbcolor   % rainbow colors outside
               a 2 add 100 mul
               b 2 add 100 mul 1 1 rectfill
               exit
           } if
           /x x x mul y y mul sub a add
           /y 2 x mul y mul b add
           def def
       } for
    } for
} for
showpage

```
> 6 votes

# Answer
# gnuplot 110 (105 without newlines)

Obligatory gnuplot entry. It's been done countless times but this one is from scratch (not that it's difficult). I like how `gnuplot` golfs its commands intrinsically :)

```
f(z,w,n)=abs(z)>2||!n?n:f(z*z+w,w,n-1)
se vi map
se si sq
se isos 256
sp [-2:2] [-2:2] f(0,x+y*{0,1},99) w pm

```

ungolfed:

```
f(z,w,n)=abs(z)>2||n==0?n:f(z*z+w,w,n-1)
set view map
set size square
set isosamples 256
splot [-2:2] [-2:2] f(0,x*{1,0}+y*{0,1},99) with pm3d

```

However, I'm DEEPLY disappointed at the entry of complex numbers. `x*{1,0}+y*{0,1}` must be the saddest existing way of constructing a complex number.

Oops, the image:

Set isosamples higher for better resolution. We could also say `unset tics` and `unset colorbox` for a pure image, but I think this version qualifies just fine.
> 5 votes

# Answer
## Matlab (89 bytes)

```
[X,Y]=ndgrid(-2:.01:2);C=X+i*Y;Z=C-C;K=Z;
for j=1:99,Z=Z.*Z+C;K=K+(abs(Z)<2);end,imagesc(K)

```

Output -

Doesn't satisfy the requirement that the inner cells must be black or white, but that can be satisfied by either (1) using `imshow(K)` instead of `imagesc(K)` (requires 1 fewer byte but needs the image processing toolbox) or (2) appending `colormap hot` (requires 12 more bytes).

Ungolfed version -

```
Z = zeros(N);
K = Z;

[X,Y]=ndgrid(-2:.01:2);
C = X+1i*Y;

for j = 1:99
  Z = Z.*Z + C;
  K(K==0 & abs(Z) > 2) = j;
end

imagesc(K)

```
> 5 votes

# Answer
## Floater, 620 pixels

A language I made up when I got inspired by my own challenge, as well as from the esoteric language Piet.
> 5 votes

# Answer
# Excel VBA, ~~251~~ ~~246~~ ~~224~~ ~~223~~ 221 bytes

<sub><sup>Saved 5 bytes thanks to ceilingcat</sup></sub> <sub><sup>Saved 23 bytes thanks to Taylor Scott</sup></sub>

```
Sub m
D=99
For x=1To 4*D
For y=1To 4*D
p=0
q=0
For j=1To 98
c=2*p*q
p=p^2-q^2-2+(x-1)/D
q=c+2+(1-y)/D
If p^2+q^2>=4Then Exit For
Next
j=-j*(j<D)
Cells(y,x).Interior.Color=Rnd(-j)*1E6*j/D
Next y,x
Cells.RowHeight=48
End Sub

```

Output:

I made a version that did this a long time ago but it had a lot of extras like letting the user pick the basic color and easy-to-follow math. Golfing it way down was an interesting challenge. The `Color` method uses `1E6` as a means to get a wide range of colors since the valid colors are `0` to `2^24`. Setting it to `10^6` gave nice contrast areas.

Explanation / Auto-Formatting:

```
Sub m()

    'D determines the number of pixels and is factored in a few times throughout
    D = 99
    For x = 1 To 4 * D
    For y = 1 To 4 * D
        'Test to see if it escapes
        'Use p for the real part and q for the imaginary
        p = 0
        q = 0
        For j = 1 To 98
            'This is a golfed down version of complex number math that started as separate generic functions for add, multiple, and modulus
            c = 2 * p * q
            p = p ^ 2 - q ^ 2 - 2 + (x - 1) / D
            q = c + 2 + (1 - y) / D
            If p ^ 2 + q ^ 2 >= 4 Then Exit For
        Next

        'Correct for no escape
        j = -j * (j < D)

        'Store the results
        'Rnd() with a negative input is deterministic
        'This is what gives us the distinct color bands
        Cells(y, x).Interior.Color = Rnd(-j) * 1000000# * j / D

    Next x, y

    'Resize for pixel art
    Cells.RowHeight = 48

End Sub

```

---

I also played around with `D=999` and `j=1 to 998` to get a much larger and more precise image. The results are irrelevant to the challenge because they're way too large but they *are* neat.
> 5 votes

# Answer
# JavaScript + HTML5 (356B)

(Note: lines ending with '//' are added here for some readability)

Performant version (375B):

```
<body onload='var
w,h=w=C.width=C.height=500,X=C.getContext("2d"),I=X.createImageData(w,h),D=I.data, //
y=0,f=255,T=setInterval(function(x,i,j,k,l,c,o){for(x=0;x<w;){                     //
for(i=x*4/w-2,j=y*4/h-2,k=l=0,c=f;--c&&k*k+l*l<4;)t=k*k-l*l+i,l=2*k*l+j,k=t
D[o=(y*w+x++)*4]=(c*=0xc0ffeeee)&f
D[++o]=c>>8&f
D[++o]=c>>16&f
D[++o]=f}X.putImageData(I,0,0)
++y-h||clearInterval(T)},0)'><canvas id=C>

```

Slow version (356B): remove the 'var' and parameters in the inner function so that the global scope is used.

Try it out: http://jsfiddle.net/neuroburn/Bc8Rh/
> 4 votes

# Answer
# Javascript, 285B

Based off my code and some improvements on MT0's code, I've got this down to 285B in colour:

```
document.body.appendChild(V=document.createElement('Canvas'));j=(D=(X=V.getContext('2d')).createImageData(Z=V.width=V.height=255,Z)).data;for(x=Z*Z;x--;){k=a=b=c=0;while(a*a+b*b<4&&Z>k++){c=a*a-b*b+4*(x%Z)/Z-3;b=2*a*b+4*x/(Z*Z)-2;a=c;}j[4*x]=99*k%256;j[4*x+3]=Z;}X.putImageData(D,0,0);

```

in action: http://jsfiddle.net/acLhe/7/

### was: Coffeescript, 342B

```
document.body.appendChild V=document.createElement 'Canvas'
N=99
Z=V.width=V.height=400
P=[]
P.push "rgba(0,0,0,"+Math.random()*i/N+')' for i in [N..0]
X=V.getContext '2d'
for x in [0..Z]
 for y in [0..Z]
  k=a=b=0
  [a,b]=[a*a-b*b+4*x/Z-3,2*a*b+4*y/Z-2] while a*a+b*b<4 and N>k++
  X.fillStyle=P[k-1]
  X.fillRect x,y,1,1

```

Coffeescript is supposed to be readable :-/ see it in action: http://jsfiddle.net/acLhe/6/
> 4 votes

# Answer
## QBasic, QuickBasic, QB64 - ~~156~~ 153

```
SCREEN 13
FOR J=0TO 191
B=J/48-2
FOR I=0TO 191
A=I/48-2
X=A
Y=B
C=0
DO
U=X*X
V=Y*Y
Y=2*X*Y+B
X=U-V+A
C=C+1
LOOP UNTIL C>247OR U+V>4
PSET(I,J),C
NEXT
NEXT

```

Standard DOS palette:
> 4 votes

# Answer
# QBasic, 139 bytes

*-1 c/o DLosc*

```
SCREEN 13
FOR i=0TO 199
FOR j=0TO 199
x=0
y=0
FOR c=0TO 255
t=y*y
c=c-255*(x*x+t>4)
y=2*x*y+j/50-2
x=x*x-t+i/50-2
NEXT
PSET(i,j),c
NEXT j,i

```

**Output:**

It may be necessary to append a `INPUT$(1)` to prevent the window from closing until a key is pressed.

---

# FreeBASIC, 139 bytes

Using FreeBASIC's `SCREEN 16`, we can generate a more detailed image at the same code length:

```
SCREEN 16
FOR i=0TO 383
FOR j=0TO 383
x=0
y=0
FOR c=0TO 255
t=y*y
c=c-255*(x*x+t>4)
y=2*x*y+j/96-2
x=x*x-t+i/96-2
NEXT
PSET(i,j),c
NEXT j,i

```

Compile as `fbc -lang qb mandel.bas`.

Higher resolutions are also available.
> 4 votes

# Answer
## Perl + GD, 264

```
$I=new GD::Image $s=499,$s;Z(0,0,0);Z(map rand 256,1..3)for
0..99;for$x(0..$s){for$y(0..$s){for($H=$K=$c=$t=0;$c++<99&&$H*$H+$K*$K<4;){sub
Z{$I->colorAllocate(@_)}($H,$K)=($H*$H-$K*$K+4*$x/$s-2,2*$H*$K+4*$y/$s-2)}use
GD;$I->setPixel($x,$y,$c<99&&$c)}}print $I->png

```

Golfed from this code
> 3 votes

# Answer
# Tcl/Tk, 316

# ~~322~~ ~~324~~ ~~336~~ ~~348~~ ~~349~~ ~~351~~ ~~352~~ ~~353~~ ~~354~~ ~~355~~

Now a shorter version using 3 letter #RGB shorthands style color triplets (instead of #RRGGBB triplets), which results in different colors.

And some more golfing.

```
rename set s
grid [canvas .c -w 640 -he 640]
.c cr i 320 320 -i [s p [image c photo -w 640 -h 640]]
time {incr x
s y 0
time {incr y
s a 0
s b 0
s n 0
while \$n<99 {s A [expr $a*$a-$b*$b+$x[s f *4/639.-2]]
if [s b [expr 2*$a*$b+$y$f]]*$b+[s a $A]*$a>4 break
incr n}
$p p [format #%03x [expr $n*41]] -t $x $y} 640} 640

```

---

# Tcl/Tk, 325

# ~~331~~ ~~333~~ ~~345~~ ~~357~~ ~~358~~ ~~360~~ ~~361~~ ~~362~~ ~~364~~ ~~365~~

I think I would win if the criterium was beauty!

```
rename set s
grid [canvas .c -w 640 -he 640]
.c cr i 320 320 -i [s p [image c photo -w 640 -h 640]]
time {incr x
s y 0
time {incr y
s a 0
s b 0
s n 0
while \$n<99 {s A [expr $a*$a-$b*$b+$x[s f *4/639.-2]]
if [s b [expr 2*$a*$b+$y$f]]*$b+[s a $A]*$a>4 break
incr n}
$p p [format #%06x [expr $n*16777215/99]] -t $x $y} 640} 640

```

Presentation:
> 3 votes

# Answer
## Python 3, 290 Bytes

```
from PIL import Image
import numpy as n
s=640;d=n.zeros((s,s,3),dtype=n.uint8)
for k in range(s*s):
    r=4/s*(k%s)-2;i=2-4/s*(k//s);z=c=complex(r,i)
    for i in range(50,9950,100):
        if abs(z)>2:
            d[k//s,k%s]=[i*5,i*9,i*7];break
        z=z*z+c
Image.fromarray(d).show()

```
> 3 votes

# Answer
## GLSL, 146 bytes

```
void mainImage( out vec4 o, vec2 C ) {o -= o; vec2 z;
for(;o.z++<99.^^length(z)>2.;)z=mat2(z.rg,-z.g,z)*z+C/99.-2.;o=mod(vec4(o.z)/vec4(4,2,6,0),1.19);}

```

https://www.shadertoy.com/view/sly3RW
> 3 votes

# Answer
# Julia

Well, better late than never:

```
function mandelbrot(x0,y0,side,N=800,L=55,R=3.)
    m = [0 for i=1:N,j=1:N]
    delta = side/N
    for i=1:N, j=1:N
        c = x0+delta*i+(y0+delta*j)*im
        z, h = 0+0*im, 0
        while (h<L) && (abs(z)<R)
            z = z^2+c
            h+=1
        end
        m[j,i]=h
    end
    return m
end
n=2.6
m = mandelbrot(-n/1.3,-n/2, n)
using Winston, Color
imagesc(m)
title("Mandelbrot Set")

```

Colormap Mod. :

```
function RGB_cm()
    colormap = [RGB(0,0,0) for t=1:255*5]
    rgb = [255,0,0]
    for t in 0:(255*5-1)
    c = [0, 0, 0]
    i = ifloor(t/255)
    c[(i+3)%3!=0?(i+3)%3:3] = (-1)^i
    rgb+=c
    colormap[t+1] = RGB(rgb[1],rgb[2],rgb[3])
    end
    colormap[(end-25):end] = RGB(0,0,0)
    return colormap
end
c = RGB_cm()
Winston.colormap(c)

```

**Output:**
> 2 votes

# Answer
# SmileBASIC, 126 bytes

```
X=RNDF()*4-2Y=RNDF()*4-2@N
N=N+16I=X+S*S-T*T
T=Y+S*T*2S=I
IF N<#L&&S*S+T*T<4GOTO@N
GPSET X*50+99,Y*50+99,RGB(99XOR N,N,N)EXEC.

```
> 2 votes

# Answer
# JavaScript (pixel shader), 88 bytes

```
m=(x,y,A=0,B=0,n=99)=>n--&&A*A+B*B<4?m(x,y,A*A-B*B+x,2*A*B+y,n):`hsl(${n*7} 99%${n/2}%)`

```

A pixel shader function that takes `x` and `y` between `[-2, -2]` and `[2, 2]` and returns CSS `<color>` (HSL).

```
m=(x,y,A=0,B=0,n=99)=>n--&&A*A+B*B<4?m(x,y,A*A-B*B+x,2*A*B+y,n):`hsl(${n*7} 99%${n/2}%)`

const size = 512;
const scale = 4;
const ratio = scale / size;

const canvas = document.getElementById('canvas');
canvas.width = canvas.height = size;
const ctx = canvas.getContext('2d');

let x, y;
for (x = 0; x < size; x++) for (y = 0; y < size; y++) {
  ctx.fillStyle = m((x - size / 2) * ratio, (y - size / 2) * ratio);
  ctx.fillRect(x, y, 1, 1);
}
```

```
<canvas id="canvas"/>
```

Ungolfed and Explained

```
m = (
  x,    // Re(c)
  y,    // Im(c)
  A=0,  // Re(z[i])
  B=0,  // Im(z[i])
  n=99  // 99 - i
) =>
  n-- && // if haven't reached max depth
  A * A + B * B < 4 ? // and |z| < 2
    m( // recurse
      x,
      y,
      A * A - B * B + x, // Re(z[i] ^ 2 + c)
      2 * A * B + y,     // Im(z[i] ^ 2 + c)
      n
    ) : // else return HSL colour
    `hsl(${n * 7} 99% ${n / 2}%)` // n * 7 always unique in mod 360

```
> 2 votes

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


title: Machine Epsilon

text:
# Question
Title: Machine Epsilon
Machine epsilon is an important floating point number to know when doing numerical calculations. One way to understand it is when this relation

```
1 + machine_epsilon > 1

```

does not hold. One (iterative) way to extract it is executing a small program like the one above:

```
10 EPS=1
20 EPS=EPS/2
30 EPS1 = 1+EPS
40 IF EPS1 > 1 GOTO 20
50 PRINT EPS

```

But there may be more ways. Write the shortest code to extract the machine epsilon of your computer. **NOTE:** epsilon should be a non-zero value :)

# Answer
> 7 votes
## PowerShell, 5

Since .NET has certain guarantees for `double`, this number will not change, regardless of the implementation of the CLR or the platform it runs on. Therefore, the following suffices:

```
1/8pb

```

If you desperately need an iteration that computes the value in the way you've given in the task description, then that'd be 25 characters:

```
for($e=1;1+$e-1){$e/=2}$e

```

# Answer
> 5 votes
## \>\<\> \- 18 16 characters

```
1>2,:1v
n^?)1+<;

```

Usage and output using the python interpreter:

```
$ fish scripts/epsilon.fish
1.1102230246251565e-16

```

**Edit** Fixed code to return correct value (`1.1e-16`)

# Answer
> 4 votes
## JavaScript, 28 characters

```
for(y=1;y+1-1;y/=2);alert(y)

```

I could replace the `y+1-1` with `y+1>1`, but I like for aesthetics of the former.

# Answer
> 4 votes
**Brainfuck, 16**

Brainfuck doesn't support floating-point arithmetic, so epsilon is 0.

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

```

According to this, this is the smallest such program. Program assumes that cells are unsigned bytes mod 256.

# Answer
> 3 votes
## Perl

```
$x=1;push@a,$x/=2while$x;die@a[$#a-1];

```

# Answer
> 2 votes
**Python, 29**

```
t=1.
while t+1>1:t/=2
print t

```

**Python3, 28**

"true" division sucks, IMO... but I'll use it to cut a character out

```
t=1
while t+1>1:t/=2
print t

```

# Answer
> 2 votes
## Haskell

Update

```
until((==1).(1+))(/2)1

```

Previous:

For doubles

```
last$takeWhile(/=0)$iterate(/2)1

```

For floats

```
last$takeWhile(/=0)$iterate(/2)(1::Float)

```

# Answer
> 2 votes
## PHP, 13 chars

For `1 + epsilon > 1`, to be true, `1 + epsilon` must fit into the number of bits allotted to the mantissa (`5` in `5 * 10^4`) in floating point numbers. 52 bits are allotted to the mantissa in 64-bit floating point numbers. It follows that `1 + epsilon` is `1.000...(52)...0001` (base 2), and that `episilon` is `0.000...(52)...0001`. Calculating this number in decimal gives:

```
<?=pow(2,-52);

```

You'll notice that negatively exponentiating 2 is the same as repeatedly dividing by 2 -- which is what many of the solutions here do.

Bonus, more platform-independent solution (13 chars):

```
<?=sin(pi());

```

# Answer
> 2 votes
# MATLAB, 3 bytes

I'm going to post this purely because it's one of the rare opportunities for MATLAB to be one of if not the shortest. I think it is in the rules for what the question asks.

```
eps

```

Granted, not the most ingenious or exciting code though!

# Answer
> 2 votes
# Vyxal, ~~9~~ 8 bytes

```
1{:›1>|½

```

LOTM finally gave me a reason to actually try Vyxal, and so far I like it!

-1 byte thanks to Aaron Miller

Try it Online!

# Answer
> 1 votes
## Mathematica 15 chars

```
$MachineEpsilon

-> 2.220446049250313*10^-16

```

# Answer
> 1 votes
## Ada - 151

```
generic
type T is digits <>;function E return T;function E return T is
A,B,C:T:=1.0;begin
loop
A:=A/2.0;B:=C+A;exit when B<=C;end loop;return A;end E;

```

example usage:

```
procedure Main is
   function F is new E (Float);
   function D is new E (Long_Float);
begin
   Put_Line ("Epsilon:" & Float'Image (F));
   Put_Line ("Epsilon:" & Long_Float'Image (D));
end Main;

```

output:

```
Epsilon: 5.96046E-08
Epsilon: 1.11022302462516E-16

```

# Answer
> 1 votes
# Pyth - 5 bytes

```
.IhG1

```

Try it online here.

Invert goes through all positive reals till it finds something that makes the lambda of `G` equal the second arg. So the code just inverts `1+G` till it equals `1`.

# Answer
> 1 votes
# Excel, 35 bytes

```
=LET(x,2^-ROW(1:99),MAX((1+x=1)*x))

```

## Excel (2010), 37 bytes

```
=MAX(2^-ROW(1:99)*(1+2^-ROW(1:99)=1))

```

# Answer
> 1 votes
# Java, 13 bytes

It is easy by using the ulp method.

```
Math.ulp(1.0)

```

Result is `2.220446049250313E-16`.

# Answer
> 1 votes
# Husk, 8 bytes

```
Ωoε→½□√2

```

Try it online!

Formula is the exact same as the reference implementation.

Fixed with Leo's help by using decimals.

# Answer
> 1 votes
# Grok, 21 bytes

```
1Y  j qzph
>1+1hY/2p{

```

Try it Online!

That's right, there's an online interpreter now! For those wondering, the framework is modified from the online Vyxal interpreter.

Explanation:

```
1Y  j       # Push 1 and copy it to the register
  +1h       # Add 1
>1          # Is it greater than 1?
        p{  # If yes, retrieve value from register
     Y/2    # Divide by 2 and copy it to the register, then repeat this line
      qzph  # If no, retrieve value from register,
         {  # then print as a number

```

# Answer
> 0 votes
## Ruby, 18

Just for the sake of completeness:

```
p Float::EPSILON/2

```

# Answer
> 0 votes
# Mathematica, 21 bytes

```
Print@$MachineEpsilon

```

# Answer
> 0 votes
# JavaScript ES6 in a REPL,14

```
Number.EPSILON

```

# JavaScript ES5 in a REPL,15

```
Math.pow(2,-52)

```

# Answer
> 0 votes
# MMIX, 16 bytes (4 instrs)

(jelly xxd)

```
00000000: e0003ff0 21010001 06000100 f8010000  ṭ¡?ṅ!¢¡¢©¡¢¡ẏ¢¡¡

```

A bit of a hack: add 1 as int to 1.0, then subtract off as float. Disassembled:

```
eps SETH $0,#3FF0
    ADD  $1,$0,1
    FSUB $0,$1,$0
    POP  1,0

```

# Answer
> 0 votes
# C++ (gcc), 63 bytes

```
#import<iostream>
int main(){long x=1;std::cout<<*(double*)&x;}

```

Try it online!

# Answer
> 0 votes
# GNU AWK, 34 bytes

```
BEGIN{for(e=1;1+e>1;e/=2);print e}

```

Try it online! Features different epsilons for different precisions.

Thanks to GNU MPFR arithmetic, GAWK can rely on any arbitrary byte precision. GAWK's manual reference. The standard precision (double) returns `1.11022e-16`.

```
Result:
0.000488281 half precision
5.96046e-08 single precision
1.11022e-16 double precision
9.62965e-35 quad precision
4.52784e-72 oct precision

```

# Answer
> 0 votes
# 05AB1E, 9 bytes

```
1[D>1›_#;

```

Try it online!

```
1[D>1›_#;  # full program
 [    _#   # while...
1 D        # literal...
  D        # or top of stack if not first iteration...
   >       # plus 1...
     ›     # is greater than...
    1      # literal...
        ;  # halve top of stack
           # implicit output

```

# Answer
> 0 votes
## JavaScript (ES6), 24 bytes

```
(e=n=>n+1>1?e(n/2):n)(1)

```

Try it online!

Recursive solution, using the same algorithm as in the question.

Its body is an IIFE, so it's an expression that directly evaluates to the epsilon value.

```
(
  e = n =>       //Set e to the function, so we can call it later
    n + 1 > 1    //If n+1 is still greater than 1...
      ? e(n / 2) //...perform next iteration by calling itself with n halved
      : n        //...else, we found epsilon, return it
)(1)             //Call the function with the initial value 1

```

Fun fact: this will return the *half* of `Number.EPSILON`, as its value represents the smallest number that *can* be represented, i.e. `Number.EPSILON + 1 > 1`, while `Number.EPSILON/2 + 1 === 1`.

# Answer
> 0 votes
# PostScript, 37 bytes

```
([){2 div dup 1 add 1 gt{[}if}def 1[=

```

Run through ghostscript (with optional -q to clean up output):

```
$ gs -q epsilon.ps
5.96046e-08
GS>

```

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