title: Who needs 8 bits for one character?

text:
# Question
Title: Who needs 8 bits for one character?
Given a string and the characters used to encode it, you need to compress the string by only using as many bits as each character needs. You will return the character codes for each character needed to create a compressed string.

For example, given the string `"the fox"` and the encoder characters `" abcdefghijklmnopqrstuvwxyz"`, the output should be `[170, 76, 19, 195, 32]`.

## How, though?

First, you need to map each encoder character to some bits. If we have the encoder characters `abc`, then we can map the characters to bits, by mapping the character to the position of the character in binary, like this:

```
a => 01
b => 10
c => 11

```

With `13579`, we would map it like this:

```
1 => 001
3 => 010
5 => 011
7 => 100
9 => 101

```

Note that we pad zeros at the beginning as many as necessary.

Next, we would go through the string, and for each character, we would get the corresponding bits for that character. Then join all the bits together, and then convert to chunks of 8 to get the bytes. If the last byte is not 8 bits long, add zeros at the end till it is 8 bits long. Lastly, convert each byte to its decimal representation.

Reverse challenge is here.

## Test cases

```
String: "the fox", encoder characters: " abcdefghijklmnopqrstuvwxyz" => [170, 76, 19, 195, 32]
String: "971428563", encoder characters: "123456789" => [151, 20, 40, 86, 48]
String: "the quick brown fox jumps over the lazy dog", encoder characters: " abcdefghijklmnopqrstuvwxyz" => [170, 76, 25, 89, 68, 96, 71, 56, 97, 225, 60, 50, 21, 217, 209, 160, 97, 115, 76, 53, 73, 130, 209, 111, 65, 44, 16]
String: "abc", encoder characters: "abc" => [108]
String: "aaaaaaaa", encoder characters: "a" => [255]
String: "aaaabbbb", encoder characters: "ab" => [85, 170]

```

## Rules

* Inputs can be a string, list, or even list of character codes. It doesn't matter, I/O is very flexible for this challenge.
* Input will always be valid, e.g. the string will never include characters not in the encoder characters, etc.
* Encoder characters will always contain \**less than 256 characters.
* Neither input will ever be empty.
* This is , so the shortest answer in bytes for each language wins.
* Standard I/O rules apply.
* Default loopholes are forbidden.

## Reference implementation in JavaScript

```
function encode(str, encoderChars) {
  const maxBitCount = Math.ceil(Math.log2(encoderChars.length + 1));
  const charToBit = Object.fromEntries(encoderChars.map((c, i) => [c, (i + 1).toString(2).padStart(maxBitCount, "0")]));
  const bits = [...str].map((c) => charToBit[c]).join("");
  const bytes = bits.match(/.{1,8}/g) || [];
  return bytes.map((x) => parseInt(x.padEnd(8, '0'), 2));
}

```

Attempt This Online!

# Answer
> 11 votes
# Vyxal, 19 bytes

```
¹żb:∩L∆ZĿf8ẇR8∆ZRvB

```

Try it Online!

```
        Ŀ           # Replace each element of <the key> in <the input>
                    # with the corresponding value of...
¹ż                  # 1...len(key)
  b                 # Convert each to binary
      ∆Z            # left-pad each with zeroes to length
   :∩L              # The maximum length - the length when transposed
         f8ẇ        # Reshape into chunks of 8
            R   R   # With each reversed...
             8∆Z    # Left-pad to length 8 (so right-pad)
                 vB # Convert each back from binary

```

# Answer
> 8 votes
# JavaScript (ES7),  ~~124 122~~  117 bytes

Expects `(encoder_characters)(string)`, where `string` is passed as an array of characters.

```
(b,o=k=[],i=32)=>g=a=>(i+=~Math.log2(b.length),k|=b.indexOf(a.shift())+1<<i)?g(a,i<25&&(o.push(k>>>24),k<<=8,i+=8)):o

```

Try it online!

# Answer
> 5 votes
# Jelly, 21 bytes

```
JBUz0ZU⁸,yFŻ8¡s8z0ZḊḄ

```

Try It Online!

```
JBUz0ZU⁸,yFŻ8¡s8z0ZḊḄ  Main Link
J                      Generate [1, 2, ...] as long as the encoding list
 B                     Convert to binary
  Uz0ZU                Reverse, transpose padding with 0, transpose, reverse (*)
       ⁸,              Pair the encoding list with the padded binary list
         y             Use this to translate the message into binary strings
          F            Flatten
           Ż8¡         Prepend 0 8 times (in case the list is shorter than 8)
              s8       Slice into blocks of 8
                z0Z    Transpose padding with 0, transpose (**)
                   Ḋ   Remove the block of 8 zeroes at the start
                    Ḅ  Convert from binary into numbers

(*)  this is a common pattern used to left-pad everything to the same length
(**) this is a common pattern used to right-pad everything to the same length -
     because we prepended a block of 8 zeroes, there is at least one sublist
     of length 8, so everything will be padded to length 8

```

# Answer
> 4 votes
# Python, 115 bytes

```
lambda s,e,o=0:[*sum(-~e.find(x)<<8*(L:=(l:=len(f"{len(e):b}"))*len(s)+7>>3)-(o:=o+l)for x in s).to_bytes(L,'big')]
```

Attempt This Online!

## Old Python, 122 bytes

```
def f(s,e,o=0):
 for x in s:o<<=(l:=len(f"{len(e):b}"));o-=~e.find(x)
 l*=len(s);return[*(o<<-l%8).to_bytes(l+7>>3,'big')]
```

Attempt This Online!

# Answer
> 3 votes
# Retina, 90 bytes

```
L$`(.?)(?=.*(¶.*)(?!$)\1)
$.2*
+`(_+)\1
$1
 _
_
P^`.+
.+$
7*
¶

L`.{8}
_
 _
+`_
 __
%`_

```

Try it online! Explanation:

```
L$`(.?)(?=.*(¶.*)(?!$)\1)
$.2*

```

Get the 1-indexed indices of all of the input string's characters in the encoder characters, plus the number of encoder characters.

```
+`(_+)\1
$1
 _
_

```

Convert to binary using the custom base conversion characters  `_`.

```
P^`.+

```

Left-pad all of the binary strings to the width of the binary number of encoder characters.

```
.+$
7*

```

Replace the binary number of encoder characters with seven spaces.

Join the binary strings together.

```
L`.{8}

```

Split into strings of length 8, ignoring any trailing spaces.

```
_
 _
+`_
 __
%`_

```

Convert from the custom binary to decimal.

# Answer
> 3 votes
# Ruby, ~~128~~ ~~120~~ 118 bytes

First attempt, probably some ways to make it more optimal

```
->s,x{s.map{(x.index(_1)+1).to_s(2).rjust Math.log2(x.size+1).ceil,?0}.join.scan(/.{1,8}/).map{_1.ljust(8,?0).to_i 2}}

```

s should be the character codes of the input string and x should be the character codes of the encoder. Returns an array of character codes.

Attempt this online!

# Answer
> 2 votes
# Factor, 123 bytes

```
[ dup length [1,b] dup last log2 1 + '[ >bin _ 48 pad-head ] map zip substitute concat 8 group [ 8 48 pad-tail bin> ] map ]

```

Try it online!

## Explanation

Takes the string as an array of codepoints and the encoder characters as a string.

```
                        ! { 57 55 49 52 50 56 53 54 51 } "123456789"
dup                     ! { 57 55 49 52 50 56 53 54 51 } "123456789" "123456789"
length                  ! { 57 55 49 52 50 56 53 54 51 } "123456789" 9
[1,b]                   ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 }
dup                     ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } { 1 2 3 4 5 6 7 8 9 }
last                    ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } 9
log2                    ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } 3
1 +                     ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } 4
'[ >bin _ 48 pad-head ] ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } [ >bin 4 48 pad-head ]
map                     ! { 57 55 49 52 50 56 53 54 51 } "123456789" { "0001" "0010" "0011" "0100" "0101" "0110" "0111" "1000" "1001" }
zip                     ! { 57 55 49 52 50 56 53 54 51 } { { 49 "0001" } { 50 "0010" } { 51 "0011" } { 52 "0100" } { 53 "0101" } { 54 "0110" } { 55 "0111" } { 56 "1000" } { 57 "1001" }
substitute              ! { "1001" "0111" "0001" "0100" "0010" "1000" "0101" "0110" "0011" }
concat                  ! "100101110001010000101000010101100011"
8 group                 ! { "10010111" "00010100" "00101000" "01010110" "0011" }
[ 8 48 pad-tail bin> ]  ! { "10010111" "00010100" "00101000" "01010110" "0011" } [ 8 48 pad-tail bin> ]
map                     ! { 151 20 40 86 48 }

```

# Answer
> 2 votes
# Python 3, <sup>~~133~~ ~~132~~</sup> 131 bytes

```
def f(s,e):w=len(f"{len(e):b}");return[int((''.join(f'{e.find(c)+1:0{w}b}'for c in s)+8*'0')[i:i+8],2)for i in range(0,len(s)*w,8)]

```

Try it online!

*Saved a byte thanks to Steffan!!!*

# Answer
> 2 votes
# Charcoal, 26 bytes

```
ＩＥ⪪⭆θ◧⍘⊕⌕ηι !Ｌ↨Ｌη²¦⁸⍘◨ι⁸ !

```

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

```
    θ                       Input string
   ⭆                        Map over characters and join
         η                  Encoder characters
        ⌕                   Find 0-based index of
          ι                 Current character
       ⊕                    Incremented
      ⍘                     Custom base conversion using
            !               Literal string ` !`
     ◧                      Left-padded to length
                η           Encoder characters
               Ｌ            Length
              ↨             Converted to base
                 ²          Literal integer `2`
             Ｌ              Length
  ⪪                         Split into substrings of length
                   ⁸        Literal integer `8`
 Ｅ                          Map over substrings
                      ι     Current substring
                     ◨      Right-padded to length
                       ⁸    Literal integer `8`
                    ⍘       Custom base conversion using
                         !  Literal string ` !`
Ｉ                           Cast to string
                            Implicitly print

```

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

Prompts for string followed by encoder characters:

```
2⊥⍉(m,8)⍴(8×m←⌈(⍴n)÷8)↑n←,⍉((⌈2⍟⌈/n)⍴2)⊤n←⎕⍳⎕

```

Try it online! Thanks to Dyalog Classic

# Answer
> 2 votes
# 05AB1E, 17 bytes

```
āb¤g°+€¦‡¾8×«8ô¨C

```

Inputs in reversed order, with the encoding string as first input.

Try it online or verify all test cases.

**Explanation:**

```
ā          # Push a list in the range [1, (implicit) first input-length]
 b         # Convert each to a binary string
  ¤g°+€¦   # Right-pad with 0s to make them all the same length:
  ¤        #  Push the last/longest binary-string
   g       #  Pop and push its length
    °      #  Pop and push 10 to the power this length
     +     #  Add it to each binary
      €¦   #  Remove the leading 1 from each
‡          # Transliterate all characters in the first input to these
           # binary-strings in the second (implicit) input
 ¾8×       # Push a string of 8 0s: "00000000"
    «      # Append the strings together
     8ô    # Split it into parts of size 8
       ¨   # Remove the trailing part
        C  # Convert all binary-strings to integers
           # (after which it is output implicitly as result)

```

`¤g°+€¦` could alternatively be `¤gjð0:` for the same byte-count:

```
  ¤g       #  Same as above to get the length
    j      #  Pad each with leading spaces up to this length
     ð0:   #  Replace all spaces with 0s

```

# Answer
> 2 votes
# Python 3, 116 bytes

```
lambda s,e,j=''.join:map(lambda*a:int(j(a),2),*[iter(j(f"{e.find(c)+1:0{len(bin(len(e)))-2}b}"for c in s)+7*'0')]*8)

```

Try it online!

Using xnor's `zip/iter` trick for chunkification (but with `map` instead).

# Answer
> 2 votes
# PARI/GP, 90 bytes

```
f(s,e)=digits(fromdigits([[i|i<-[1..#e],e[i]==c][1]|c<-s],2^l=#binary(#e))<<(-l*#s%8),256)
```

Attempt This Online!

Inputs lists of characters.

# Answer
> 2 votes
# Desmos, ~~304~~ 265 bytes

```
g=[1...Q][c=s[floor(i/q)+1]][1]
Q=c.length+1
q=ceil(log_2Q)
l=[floor(log_2g)...0]
k=\{q=l[1]+1:[],[2...q-l[1]]0\}
d=[join(k,mod(floor(g/2^l),2))[mod(i,q)+1]fori=[0...qs.length-1]]
v=join(d,[1...8]0)[8u-7...8u]
f(s,c)=[total(2^{[7...0]}v)foru=[1...ceil(d.length/8)]]

```

Both inputs are list of codepoints, as is output. This took me a *long* time.

Try it on Desmos!

*-39 bytes thanks to Aiden Chow*

# Answer
> 2 votes
# MATL, 17 bytes

```
&m2Gt&mBwY)!8e!XB

```

Try it online!

Of note, `B` returns a matrix with the binary strings as rows, so they are automatically padded to the same length.

# Answer
> 2 votes
# Uiua, 30 bytes\*

*or **69 bytes** using native UTF-8 encoding*

```
▽±.⍘⋯≡⇌↯⊂¯1 8≡⇌⬚0⊂∶×0⋯⧻∶⋯+1⊗⊙.

```

Try it!

---

**See answer to the reverse challenge here and here for a single-byte-character-system (SBCS) encoding.*

# Answer
> 1 votes
# Julia 1.7, 125 bytes

```
s\e=parse.(Int,only.(eachmatch(r"(.{8})",join(string.(findlast.(s,e);base=2,pad=floor(Int,log2(2length(e)))))*"0"^7)),base=2)
```

Attempt This Online!

expects `s` as a list of characters and `e` a string. Needs Julia 1.7 for `only(::RegexMatch)`

---
Tags: code-golf, string, binary, compression
---


title: Binary expansion and partition numbers

text:
# Question
Title: Binary expansion and partition numbers
Not sure if it's correct to ask such a question on this site, but let's try.

Let **a(n)** be a sequence of positive integer such that **a(1) = 1**. To reproduce the sequence **a(n)** through itself, use the following rule: if binary **1xyz** is a term then so are **110xyz** and **1XYZ** where the last one is the same as **1xyz** with rewrite **1 -\> 10**.

The sequence begins with

**1, 2, 4, 6, 8, 12, 16, 20, 24, 26, 32, 40, 48, 52**

These numbers in binary:

```
[1]
[1, 0]
[1, 0, 0]
[1, 1, 0]
[1, 0, 0, 0]
[1, 1, 0, 0]
[1, 0, 0, 0, 0]
[1, 0, 1, 0, 0]
[1, 1, 0, 0, 0]
[1, 1, 0, 1, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 0]
[1, 1, 0, 0, 0, 0]
[1, 1, 0, 1, 0, 0]

```

Here are examples:

* **1 -\> 10** by the rule **1xyz -\> 1XYZ** (rewrite **1 -\> 10**)
* **10 -\> 100** by the rule **1xyz -\> 1XYZ** (rewrite **1 -\> 10**)
* **1 -\> 110** by the rule **1xyz -\> 110xyz**
* **100 -\> 1000** by the rule **1xyz -\> 1XYZ** (rewrite **1 -\> 10**)
* **10 -\> 1100** by the rule **1xyz -\> 110xyz**
* **1000 -\> 10000** by the rule **1xyz -\> 1XYZ** (rewrite **1 -\> 10**)
* **110 -\> 10100** by the rule **1xyz -\> 1XYZ** (rewrite **1 -\> 10**)
* **100 -\> 11000** by the rule **1xyz -\> 110xyz**
* **110 -\> 11010** by the rule **1xyz -\> 110xyz**
* **10000 -\> 100000** by the rule **1xyz -\> 1XYZ** (rewrite **1 -\> 10**)
* **1100 -\> 101000** by the rule **1xyz -\> 1XYZ** (rewrite **1 -\> 10**)
* **1000 -\> 110000** by the rule **1xyz -\> 110xyz**
* **1100 -\> 110100** by the rule **1xyz -\> 110xyz**

It appears that positions of the powers of **2** in **a(n)** are partition numbers (A000041).

I tried to write an efficient PARI/GP program to generate a list of the first **n** terms and this is what I got:

```
b1(n) = my(L = logint(n, 2), A = n); A -= 2^L; L - if(A==0, 1, logint(A, 2))
upto(n) = my(v1, v2); v1 = vector(n, i, if(i < 3, i)); v2 = [1, 2];  my(k = 2, j = 1, q = 0); for(i = 3, n, my(A = v2[j] + q); if(A >= v2[k-1], k++; v1[i] = 2^(k-1); j=k\2; q = 0; v2 = concat(v2, i), v1[i] = v1[A] + 2^(j-1) + 2^(k - 1); if((k - j - 2) >= b1(v1[A+1]), j++; q = 0, q++))); v1

```

Is there a way to write a simpler program (that is, such a program which returns same number of values faster than my program given above)?

# Answer
# Rust

Port of @l4m2's c++ answer in Rust.

Try it online!

```
fn foo(p: i32, x: u128, lb: i32, pos: &mut usize, arr: &mut Vec<u128>) {
    if *pos >= arr.len() {
        return;
    }

    if p >= lb {
        arr[*pos] = x;
        *pos += 1;
    }

    for k in ((lb + 1)..=p).rev() {
        foo(p - k, x | ((1 as u128) << (p - k)), k, pos, arr);
    }
}
fn solve(arr: &mut Vec<u128>) {
    let mut pos: usize = 0;
    let mut p = 0;

    loop {
        if pos >= arr.len() {
            break;
        }
        foo(p, (1 as u128) << p, 0, &mut pos, arr);
        p += 1;
    }
}

fn main() {
    let n = 50_000_00;
    let mut a = vec![0; n];
    solve(&mut a);

    let mut i = 1;
    while i < n {
        println!("{:12} {:016X}{:016X}", i, (a[i] >> 64) as u64, (a[i] & 0xFFFFFFFFFFFFFFFF) as u64);
        i *= 2;
    }
    println!("{:12} {:016X}{:016X}", n-1, (a[n-1] >> 64) as u64, (a[n-1] & 0xFFFFFFFFFFFFFFFF) as u64);
}

```
> 1 votes

# Answer
# Charcoal, 52 bytes, 10,000 in ~10s on TIO

```
⊞υ¹ＦＮ«≔⌊υι⟦Ｉι⟧≔⁻υ⟦ι⟧υ≔⍘ι²ι⊞υ⍘⪫⪪ι1¦10²⊞υ⍘⁺110✂ι¹Ｌι¹¦²

```

Try it online! Link is to verbose version of code. Explanation: For each number, generates the two derived numbers, and then takes the minimum number generated for the next number.

```
⊞υ¹

```

Start with `1`.

```
ＦＮ«

```

Generate `n` numbers.

```
≔⌊υι

```

Get the next minimum.

```
⟦Ｉι⟧

```

Write it to the canvas.

```
≔⁻υ⟦ι⟧υ

```

Remove it from the list.

```
≔⍘ι²ι

```

Convert it to binary.

```
⊞υ⍘⪫⪪ι1¦10²

```

Change all `1`s into `10`s, convert from binary, and push the result to the list.

```
⊞υ⍘⁺110✂ι¹Ｌι¹¦²

```

Remove the leading `1`, prefix `110`, convert from binary, and push the result to the list.
> 0 votes

---
Tags: tips, binary, fastest-code, integer-partitions
---


# Question
Title: Evaluate a Linear Feedback Shift Register
## Introduction

The Fibonacci Linear Feedback Shift Register (LFSR) is a digital circuit which generates a stream of random-looking bits. It consists of several 1-bit flip-flops in a row, with certain positions designated as 'tapped'. In each iteration, the values in the tapped positions are XORed together (i.e., summed modulo 2) and the result is held in reserve. Then the bits are shifted to the right. The rightmost bit falls off the register and becomes the output, while the reserve bit is input on the left.

## Maximal LFSR

The output stream of a LFSR is periodic; it repeats after some number of iterations. A maximal LFSR has a period of 2^n - 1, where n is its number of bits. This only occurs if the tapped positions are correctly chosen; otherwise the period will be less. If the LFSR is maximal, it will cycle through all possible internal states (except all zeroes) exactly once before repeating.

For more information about maximal Fibonacci LFSRs (primitive polynomials), see this article: https://en.wikipedia.org/wiki/Linear\_feedback\_shift\_register#Fibonacci\_LFSRs

## Task

You must write a function that takes as its arguments a list representing the initial internal state of an n-bit LFSR (a list of length n made of 0 and at least one 1), and a list of tapped positions. The tapped positions are input as a list with either of these general formats (brackets, commas, and spaces are shown for convenience and are entirely optional):

Format A: \[0, 0, 1, 1\]

Format B: \[3, 4\]

Both formats declare that the 3rd and 4th positions are tapped.

The function must produce exactly one complete cycle of output of the LFSR (either as function output, or printed to the screen), as well as a Boolean evaluation of whether or not the LFSR period is maximal.

If you prefer, you may use two functions to produce the LFSR output and maximality evaluation.

## Scoring

Per usual code golf rules, your score is the number of characters in your code. Make sure your code evaluates these examples correctly:

### Example 1

State: \[1, 0, 1, 0\]

Taps: \[3,4\]

Output: \[0,1,0,1,1,1,1,0,0,0,1,0,0,1,1\] and True (since the period is 2^n - 1 = 15)

### Example 2

State: \[1, 0, 1, 0, 1\]

Taps: \[3, 5\]

Output: \[1,0,1,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1\] and True (since the period is 2^n - 1 = 31)

### Example 3

State: \[1, 0, 1, 0, 1\]

Taps: \[4, 5\]

Output: \[1,0,1,0,1,1,1,1,1,0,0,0,0,1,0,0,0,1,1,0,0\] and False (since the output has period 21, which is not equal to 2^n - 1)

# Answer
> 2 votes
### GolfScript, 38 characters

```
:f;:i[{0{(2$=^}f/\+)\.i=!}do;].,)2i,?=

```

You may declare it as a named function if you enclose the code in `{<code>}:F`. It takes the top two arguments from the stack and pushes the results back to the stack, e.g. (test it online):

```
[1 0 1 0 1] [3 5]

:f;:i[{0{(2$=^}f/\+)\.i=!}do;].,)2i,?=

# => yields [1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1] 1

```

*Annotated code:*

```
:f;          # save tap positions (1 indexed) to variable f
:i           # and the initial state to variable i
[{           # the [{...}do;] loop generates an array using the loop
             #   top of stack is the current state
  0          #   push zero (accumulator)
  {          #   {...}f/ loops over all tap positions
    (        #     make the current position zero-indexed
    2$=      #     take the corresponding bit from the current state (2$)
    ^        #     xor with the accumulator
  }f/        #   end of loop
  \+         #   prepend the new bit to the current state
  )\         #   and shift out the last bit (output)
  .i=        #   compare the current state to input
  !          #   if not equal then loop
}do;]        # end of loop - discard the state
.,)          # length of the output + 1
2i,?         # 2^length of initial state
=            # are those two numbers equal?

```

# Answer
> 1 votes
## Perl - 78 bytes

```
sub f{($_,$t)=@_;s//($_&$t)%9&1/e,@o=(@o,chop)until$o{$_}++;@o,$/,@o+1>>y///c}

```

Input is expected as two binary strings, one representing the current state, and the other the taps. For example, the input `('10101', '00011')` corresponds to an initial state with the 1st, 3rd, and 5th bits set (one indexed), with taps on the 4th and 5th bit.

For the truth condition, a `0` or `1` is returned, separated by a newline.

**Note**: The bit counting logic above, `($_&$t)%9&1`, will fail if the total number of bits is more than *16*, and/or the number of taps is greater than *8*. This can be replaced by `($_&$t)=~y|0||c&1` at the cost of *6* bytes.

**Test Case 1**
Input:

```
print f('1010', '0011');

```

Output:

```
010111100010011
1

```

**Test Case 2**
Input:

```
print f('10101', '00101');

```

Output:

```
1010100001001011001111100011011
1

```

**Test Case 3** Input:

```
print f('10101', '00011');

```

Output:

```
101011111000010001100
0

```

# Answer
> 0 votes
# Javascript (E6) 144 ~~157 169~~

**Edit** Output as string instead of array

```
F=(s,t)=>(P=>{b=s.length,i=s=P(s,2),t=P(t,2);for(o='';!o||i-s;){for(p=q=s&t;q>>=1;p^=q);o+=s&1,s=s>>1|(p&1)<<b-1}})(parseInt)||[!!o[(1<<b)-2],o]

```

**Ungolfed**

```
F=(s,t)=>
( P => { // Inner block, spare a final 'return'
  b = s.length,
  i = s = P(s,2), t=P(t,2);
  for (o='';!o||i-s;) {
    for (p=q=s&t;q>>=1;p^=q);
    o += s & 1,
    s = s >> 1 | (p&1) << b-1
  }
} ) (parseInt)
|| [!!o[(1<<b)-2], o]

```

**Usage**

State and Tapped position input as strings of bits (format A) Return an array with true/false and a string of output bits

**Test**

Javascript console in firefox,

`F('1010', '0011')` `[true, "010111100010011"]`

`F('10101', '00101')` `[true, "1010100001001011001111100011011"]`

`F('10101', '00011')` `[false, "101011111000010001100"]`

# Answer
> 0 votes
# Go, 208 bytes

```
import."slices"
func f(S,T[]int)(o[]int,m bool){s:=S
for len(o)<1||!Equal(s,S){l,L:=S[T[0]],len(S)-1
for _,i:=range T[1:]{l^=S[i]}
o,S=append(o,S[L]),append([]int{l},S[:L]...)}
O:=len(o)+1
return o,O&(O-1)<1}

```

Attempt This Online!

---
Tags: code-golf, electrical-engineering
---


title: I want 8 bits for every character!

text:
# Question
Title: I want 8 bits for every character!
This is the reverse of this challenge.

Given an encoded list of codepoints and the characters used to encode it, you need to decompress it to its original string.

For example, given the encoded list `[170, 76, 19, 195, 32]` and the encoder characters `" abcdefghijklmnopqrstuvwxyz"`, the output should be `"the fox"`.

## How, though?

First, we need to go through the encoder characters and find out what bits they correspond to. We do this by getting the binary of each corresponding (1-indexed) index in the encoder string. For example, the encoder string `6923`:

```
6, index 1 => 1
9, index 2 => 10
2, index 3 => 11
3, index 4 => 100

```

Now we need to pad each with leading zeros until they are all of equal length:

```
6, index 1 => 001
9, index 2 => 010
2, index 3 => 011
3, index 4 => 100

```

Now that we have a lookup table, let's decode it. First, let's get the binary of each codepoint. Let's say we have codepoints `[137, 147, 16]` (and still encoder string `6923`):

```
137 => 10001001
147 => 10010011
16  => 10000

```

The last one may not be 8 bits long. In this case, pad it with leading zeros until it is:

```
137 => 10001001
147 => 10010011
16  => 00010000

```

Now, smash all these bits into one string: `100010011001001100010000`. Now, we need to group it into sizes of how long each byte will be in the lookup table. Looking back at our lookup table with `6923` encoder string, we can see that each byte is 3 bits long. This means that we need to split the bits into chunks of 3:

```
100 010 011 001 001 100 010 000

```

Now, for each, check its character in the lookup table. If it is all zeros (and therefore not in the lookup table), ignore it.

```
100 => 3
010 => 9
011 => 2
001 => 6
001 => 6
100 => 3
010 => 9
000 is ignored

```

Now, joining this together, the string was `3926639`, and we're done!

## Test cases

```
Codes: [170, 76, 19, 195, 32], encoder characters: " abcdefghijklmnopqrstuvwxyz" => "the fox"
Codes: [151, 20, 40, 86, 48], encoder characters: "123456789" => "971428563"
Codes: [170, 76, 25, 89, 68, 96, 71, 56, 97, 225, 60, 50, 21, 217, 209, 160, 97, 115, 76, 53, 73, 130, 209, 111, 65, 44, 16], encoder characters: " abcdefghijklmnopqrstuvwxyz" => "the quick brown fox jumps over the lazy dog"
Codes: [108], encoder characters: "abc" => "abc"
Codes: [255], encoder characters: "a" => "aaaaaaaa"
Codes: [85, 170], encoder characters: "ab" => "aaaabbbb"

```

## Rules

* Second input can be a string, list, or even list of codepoints (same with output). It doesn't matter, I/O is very flexible for this challenge.
* First input can, again, be a list of the codepoints, or a string containing the represented codepoints (if your language uses an SBCS, you're free to use it (but you can still use UTF-8)). Again, I/O is flexible.
* Input will always be valid.
* Encoder characters will always contain **less** than 256 characters.
* Neither input will ever be empty.
* This is , so the shortest answer in bytes for each language wins.
* Standard I/O rules apply.
* Default loopholes are forbidden.

## Reference implementation in JavaScript

```
function decode(points, encoderChars) {
  const maxBitCount = Math.ceil(Math.log2(encoderChars.length + 1));
  const charToBit = Object.fromEntries(encoderChars.map((c, i) => [c, (i + 1).toString(2).padStart(maxBitCount, "0")]));
  const charBits =
    points
      .map((x) => x.toString(2).padStart(8, "0"))
      .join("")
      .match(RegExp(`.{1,${maxBitCount}}`, "g")) || [];
  return charBits
    .map((x) => Object.entries(charToBit).find((y) => y[1] === x)?.[0] || "")
    .join("");
}

```

Attempt This Online! (feel free to steal the test case code for your own JS answer)

# Answer
# Vyxal, 16 bytes

```
b8∆Zf⁰LbLẇvBꜝ‹İ∑

```

Try it Online!

```
b                # Convert each from binary
 8∆Z             # Pad each to length 8
    f            # Flatten
         ẇ       # Split into chunks of length...
     ⁰LbL        # Length of the encoder string, in binary
          vBꜝ‹   # Convert each from binary, remove 0s and decrement
              İ∑ # Index those into the encoder and sum

```
> 7 votes

# Answer
# Uiua, ~~29~~ 25 bytes (SBCS\*)

*or **55 bytes** using native UTF-8 encoding*

```
⇌⊏-1▽±.⍘⋯↯⊂¯1⧻⋯⧻,⇌↘1⋯⊂255

```

Try it!

```
                     ⊂255  # prepend 255 to list of codepoints (to force 8 bits)
                    ⋯      # convert each to bits
                  ↘1       # drop the first one (the 255)
                 ⇌         # and reverse the rows (so concatenation of uiua's big-endian bits will work);
                ,          # now duplicate the second stack item (the encoding characters)
               ⧻           # get its length
             ⧻⋯            # convert to bits and get the number of bits
         ↯⊂¯1              # reshape the codepoint-bit-array to rows of this length
       ⍘⋯                  # and convert each row back to a number from bits (=invert bits);
     ±.                    # get the signs of a copy of this (1 or 0)
    ▽                      # and use it to remove any zeros
 ⊏                         # and use the resulting numbers to index into the encoding characters
  -1                       # (after subtracting 1 to convert to zero-based indexing)
⇌                          # finally, re-reverse (to undo the earlier reversal)

```

---

**Uiua natively supports UTF-8 encoding, allowing functions to bound to multi-byte characters such as emojis. However, this isn't essential for programming in Uiua, and its full functionality can be achieved using the union of printable ASCII characters with Uiua's 108 glyphs, which can each be represented using a single byte.
This answer to the challenge provides one way that such a mapping can be implemented, which can be considered as a single-byte character system (SBCS) for Uiua (with the obvious proviso that multi-byte characters other than Uiua's glyphs are not used in the code). Since Uiua's default behaviour is to run any file in the directory with a `.ua` filename suffix, this can even be used as a runnable implementation by simply prepending `&fwa "program.ua"` to save the output to the file "`program.ua`".*
> 4 votes

# Answer
# , 35 31 bytes

```
((]i.0-.~($@]$!.0,@[)&.#:)#\){]

```

Try it online!
> 2 votes

# Answer
# PARI/GP, 70 bytes

```
f(p,e)=[e[i]|i<-digits(fromdigits(p,256)>>(8*#p%l=#binary(#e)),2^l),i]
```

Attempt This Online!

Inputs and outputs lists of characters.
> 2 votes

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

```
₁+b€¦JIgbgôC0K<è

```

Port of *@emanresuA*'s Vyxal answer, so make sure to upvote him/her as well!
-1 byte thanks to *@CommandMaster*

Outputs as a list of characters.

Try it online or verify all test cases.

**Explanation:**

```
₁+               # Add 256 to each integer in the first (implicit) input-list
  b              # Convert them to binary-strings
   €¦            # Remove the leading "1" from each
     J           # Join the list of strings together
      I          # Push the second input-string
       g         # Pop and push its length
        b        # Convert it to binary
         g       # Pop and push its length
          ô      # Split the earlier string into parts of that size
           C     # Convert each inner string from binary to a base-10 integer
            0K   # Remove all 0s
              <  # Decrease each by 1 the 1-based indices 0-based
               è # Use it to index into the second (implicit) input-string
                 # (after which the resulting list is output implicitly)

```
> 2 votes

# Answer
# Python, 139 bytes

```
lambda L,E:(n:=len(bin(len(E)))-2)and"".join(["",*E][int("".join(bin(i)[2:].rjust(8,"0")for i in L)[i:i+n],2)]for i in range(0,len(L)*8,n))
```

Attempt This Online!

I suspect it could be shorter, but I'm not well versed in binary manipulation
> 1 votes

# Answer
# Python 3, 112 bytes

```
lambda s,e,j=''.join:j(map(lambda*a:['',*e][int(j(a),2)],*[iter(j(map('{:08b}'.format,s)))]*len(f'{len(e):b}')))

```

Try it online!

Basically the inverse of my answer to the other question.
> 1 votes

# Answer
# JavaScript (ES7),  ~~99~~  95 bytes

Expects `(encoder_characters)(stream)`.

```
(d,v,i=n=0)=>g=a=>d[k=2**n-1]?g(a,n++):(i>7?0:v=v<<8|a.shift(i+=8),j=v>>(i-=n)&k)?d[j-1]+g(a):a

```

Try it online!
> 1 votes

# Answer
# Charcoal, ~~26~~ 25 bytes

```
⁻⭆⪪⭆θ◧⍘ι !⁸Ｌ↨Ｌη²§⁺ψη⍘ι !ψ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
    θ                       Input array
   ⭆                        Map over values and join
       ι                    Current value
      ⍘                     Custom base conversion using
         !                  Literal string ` !`
     ◧                      Right-padded to length
          ⁸                 Literal integer `8`
  ⪪                         Split into substrings of length
              η             Encoder characters
             Ｌ              Length
            ↨               Converted to base
               ²            Literal integer `2`
           Ｌ                Length
 ⭆                          Map over values and join
                  ψ         Predefined variable null
                 ⁺          Concatenated with
                   η        Encoder characters
                §           Indexed by
                     ι      Current value
                    ⍘       Custom base conversion using
                       !    Literal string ` !`
⁻                           Remove occurrences of
                        ψ   Predefined variable null character
                            Implicitly print

```

This approach turned out to be shorter than a numerical approach based on base-256 conversion and custom string base conversion.

23 bytes using the older version of Charcoal on TIO:

```
⭆⪪⭆θ◧⍘ι !⁸Ｌ↨Ｌη²§⁺ψη⍘ι !

```

Try it online! Link is to verbose version of code. Explanation: The version of Charcoal on TIO special-cases `AtIndex` to return the empty string instead of the null character, even when indexing into an array. Most of this time that behaviour is incredibly annoying but here it's actually helpful. Unfortunately that version of Charcoal does suffer from a bug in `BaseString` so it doesn't support zero values in the input, which can happen on rare occasion.
> 1 votes

# Answer
# Jelly, 17 bytes

```
BUz0ZUFsLBLƊ}Ḅt0ị

```

A dyadic Link that accepts the code on the left and the alphabet on the right and yields the plain text.

**Try it online!**

### How?

```
BUz0ZUFsLBLƊ}Ḅt0ị - Link: code (list of integers in [1,255]), alphabet (list)
B                 - convert code numbers to binary lists
 U                - reverse each
  z0              - transpose with filler zero
    Z             - transpose
     U            - reverse each
      F           - flatten
           Ɗ}     - last three links as a monad - f(alphabet):
        L         -   length of alphabet
         B        -   to binary list
          L       -   length
       s          - split flattened bits into slices of that length
             Ḅ    - convert these from binary
              t0  - trim zeros
                ị - index into the alphabet

```
> 1 votes

# Answer
# Pip `-x`, 26 bytes

```
b@DFBFI(STB_+E8MJa)<>#TB#b

```

Takes a list and a string as command-line arguments. The string may need to be quoted twice, once for the shell and once for Pip. Or, add the `-r` flag and supply the list and string (as a double-quoted Pip string literal) on stdin. Attempt This Online!

### Explanation

The `-x` flag evaluates both arguments. Then:

```
b@DFBFI(STB_+E8MJa)<>#TB#b
                 a          First argument (list of numbers)
               MJ           Map this function and join the results into one string:
           _                 The argument
            +E8              Plus 2 to the 8th power
         TB                  Converted to binary
        S                    Without the first character
                             I.e. convert to binary with leading zeros as necessary
       (          )<>       Group that string into chunks of this size:
                        #b   Length of second argument (encoder string)
                      TB     To binary
                     #       Length of that
     FI                     Filter out results that are falsey (here, equal to 0)
   FB                       Convert each remaining value from binary
  D                         Decrement (because Pip is 0-indexed)
b@                          Use as an index into b

```

The result is a list of characters, which by default is joined together and autoprinted.
> 1 votes

# Answer
## Ignores the transformation process and just decodes

# Burlesque, 45 bytes

```
id[-sab2L[PpqsvZ]vv{b28'0P[}\mpPco)b2:nzqgv\m

```

Try it online!

```
id           # Indices
[-           # Drop first
sa           # Non-destructive length
b2L[Pp       # Store length of longest binary in temp stack
qsvZ]        # Zip with ids and save to global map
vv           # Drop empty list
{b28'0P[}\m  # Map to binary, pad to 8, concat
pPco         # Get from temp stack, chunks of
)b2:nz       # Map from binary, filter for nonzero
qgv\m        # Get each value, concat

```

## Follows the transformation process

# Burlesque, 61 bytes

```
id[-)b2J)L[>]Js1{'0P[}j+]m[qsvZ]vv{b28'0P[}\mg1cof{b2nz}qgv\m

```

Try it online!

Pretty sure this has some golfing to be done further, but it works.

```
id      # Get indices of string
[-      # Drop 0 (string ends with null so this is ok)
)b2     # Map to binary
J)L[>]  # Get length of longest
Js1     # Save copy
{
 '0P[   # Pad left with 0s
}
j+]     # Append length of longest
m[      # Apply to each
qsvZ]   # Zip binary with encoder and save to global map
vv      # Drop resulting empty list (encoded string now top of stack)
{
 b2     # To binary
 8'0P[  # Pad to 8 with zeros
}\m     # Map concat
g1      # Get max length
co      # Chunks of
f{      # Filter
 b2nz   # Decimal value of is non-zero
}
qgv\m   # Get vals from global map and concat

```
> 1 votes

# Answer
# MathGolf, ~~17~~ 16 bytes

```
@♠+àm╞y\£à£/åç(§

```

-1 byte implicitly thanks to *@CommandMaster*, applying the same change as in my 05AB1E answer

I/O as a list of characters.

Try it online.
Minor note: the spaces in the input-lists are replaced with `_`, because there is a bug in MathGolf when reading a list that contains spaces (it reads them as `", "` instead of `" "`)..

**Explanation:**

```
@          # Reverse triple swap, so the stack now contains two encoder lists and
           # the integer-list
 ♠+        # Add 256 to each integer
   à       # Convert all integers in the list to binary-strings
    m╞     # Remove the leading "1" from each
      y    # Join it to a single string
 \         # Swap so an encoder-list is at the top
  £        # Pop and push its length
   à       # Convert it to a binary string
    £      # Pop and push its length again
     /     # Split the earlier string into parts of that size
      å    # Convert each from a binary-string back to an integer
       ç   # Remove all 0s with a falsey filter
        (  # Decrease each to make the 1-based indices 0-based
         § # Index it into the remaining encode-list
           # (after which the entire stack is output implicitly as result)

```
> 1 votes

# Answer
# GolfScript, ~~54~~ ~~53~~ ~~47~~ 46 bytes

```
~{256|{2base}:b~1>}%[]*\:a,b,/{b.{(a=}and}%""+

```

Try it online!

This is my second GolfScript submission, so I might be able to improve it. I haven't decided on the best way to write explanations for these so this time I'll leave a commented version:

```
~      # Evaluate the input; the codepoint list is on top of the stack.
{      # Open a block (like anonymous function) to run on each codepoint:
    256|     # Bitwise or with 256 to set the ninth bit
    {2base}  # A block which calls `2 base` (convert to/from base 2).
    :b       # Assign the block to variable b.
    ~        # and call it on the codepoint.
    1>       # Slice from index 1 to the end, removing the extra 9 bit.
}%     # Close this block and call it on each codepoint (map).
[]*    # Flatten the list by joining it on nothing.
\:a    # Swap and assign the second input,
       # the encoder alphabet, to variable a.
,      # Push the length of a.
b      # Convert it to binary.
,      # The length of the digit list.
/      # Split the codepoint list into chunks of this size.
{      # Open a block to run on each chunk:
    b.       # Convert the chunk from binary to decimal.
    {        # A block taking a 1-based index:
        (a=        # Decrement and 0-based index into a.
    }        # This returns a number, so we have to coerce to string later.
    and      # If the number isn't zero, run the block.
}%     # Run this block on each chunk (map).
""+    # Append an empty string to coerce the list.

```
> 0 votes

---
Tags: code-golf, string, binary, compression
---


title: Longest Consecutive Sequence

text:
# Question
Title: Longest Consecutive Sequence
## Description

Given a list of positive integers, write the shortest code to find the number count of the longest consecutive sequence of numbers within the list.

## Input

A list of positive integers. You can assume the list is not empty and may contain duplicates.

## Output

The length of the longest consecutive sequence of numbers within the list.

## Test cases

```
Input: [100, 4, 200, 1, 3, 2]
Output: 4 // because of [1, 2, 3, 4]

Input: [1, 2, 3, 4, 5]
Output: 5 // because of [1, 2, 3, 4, 5]

Input: [10, 9, 8, 7, 6, 5]
Output: 6 // because of [5, 6, 7, 8, 9, 10]

Input: [1, 1, 1, 2, 3]
Output: 3 // because of [1, 2, 3].

Input: [5]
Output: 1 // No consecutive numbers exist. You can leave the Output empty too or output -1. It must be shown by this no consecutive numbers exist

Input: [7, 3, 9, 5, 4, 2, 8]
Output: 4 // because of [2, 3, 4, 5].

```

Code with shortest bytes win, and if equated, the earlier post wins.

# Answer
> 14 votes
# Jelly, 6 bytes

```
f‘$ƬL’

```

Try it online!

```
   Ƭ    -- iterate until the result doesn't change, collecting intermediate value
f‘      -- keep the values that are still in the list when each value is incremented
    L   -- take the length (number of intermediate values, including the initial list and the empty list at the end)
     ‘  -- decrement

```

# Answer
> 13 votes
# Jelly, 5 bytes

```
ṬŒg§Ṁ

```

A monadic Link that accepts a list of positive integers and yields the length of the longest consecutive sequence.

**Try it online!**

### How?

```
ṬŒg§Ṁ - Link: list of positive integers, A  e.g. [4, 8, 3, 4, 2, 7, 4]
Ṭ     - untruth {A}                              [0, 1, 1, 1, 0, 0, 1, 1]
                                         ( i.e.:     2  3  4        7  8  )
 Œg   - group runs of equal elements             [[0], [1, 1, 1], [0, 0], [1, 1]]
   §  - sums                                     [0, 3, 0, 2]
    Ṁ - maximum                                  3

```

# Answer
> 7 votes
# Python 3, 45 bytes

```
f=lambda l:len(l)and-~f({*l}&{x-1for x in l})

```

Try it online!

Without using sets:

**Python, 48 bytes**

```
f=lambda l:l>[]and-~f([x for x in l if-~x in l])

```

Try it online!

Repeatedly filters `l` by only keeping elements `x` where `x+1` is also in `l`, and counts how many repetitions until the list is empty.

# Answer
> 7 votes
# Haskell, 32 bytes

```
f[]=0
f l=1+f[n|n<-l,elem(n+1)l]

```

Try it online!

Repeatedly filters `l` by only keeping elements `n` where `n+1` is also in `l`, and counts how many repetitions until the list is empty.

# Answer
> 7 votes
# Vyxal, 35 bitsv2, 4.375 bytes

```
ÞǔĠṠG

```

**Try it Online!**

### How?

Port of my Jelly answer.

```
ÞǔĠṠG - list of positive integers     e.g. [4, 8, 3, 4, 2, 7, 4]
Þǔ    - unthruth                           [0, 1, 1, 1, 0, 0, 1, 1]
                                   ( i.e.:     2  3  4        7  8  )
  Ġ   - group runs of equal elements       [[0], [1, 1, 1], [0, 0], [1, 1]]
   Ṡ  - sums                               [0, 3, 0, 2]
    G - maximum                            3

```

# Answer
> 6 votes
# , ~~50~~ ~~38~~ 37 bytes

*Edit: -1 bytes thanks to Giuseppe*

```
\(x,y=rle(1:max(x)%in%x))max(y$l*y$v)

```

Attempt This Online!

# Answer
> 6 votes
# , 22 bytes

```
[:#[:+/ .*~^:a:~1=-//~

```

Attempt This Online!

We view this is a graph problem. Let's consider the example `10, 9, 8, 7, 6, 5` for the explanation:

* `1=-//~` Create an adjacency matrix, where two numbers are connected if their difference is 1 (signs matter):

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

```

This says that 10 connects to 9, 9 connects to 8, etc.
* `[:+/ .*~^:a:` Multiply this matrix by itself until we reach a fixed point. One self-multiplication, eg, tells us the connections after two steps:

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

```

After two steps, 10 connects to 8, 9 to 7, etc. Then two self multiplications show us the connections after 3 steps, and so on. Eventually, we'll reach a matrix of all zeroes and stop, and the length of this chain tells us the length of the longest consecutive run of numbers.
* `[:#` So we return that length.

## , port of ovs's answer, ~~21~~ 20 bytes

```
1#@}.((e.>:)#[)^:a:~

```

Attempt This Online!

# Answer
> 5 votes
# Scala 3, ~~74~~ ~~73~~ 70 bytes

Port of @xnor's Python answer in Scala.

Thanks to @corvus\_192's comment and @Kjetil S's comment.

---

```
def f(l:Seq[Int]):Int=if(l.size<1)0 else 1+f(l.filter(l contains _+1))

```

Attempt This Online!

# Answer
> 4 votes
# Vyxal `G`, 56 bitsv2, 7 bytes

```
ṗ's¯1=A;@

```

Try it Online!

#### Explanation

```
ṗ's¯1=A;@  '# Implicit input
ṗ'     ;   '# Filter the powerset by:
  s¯        #  Sort and get deltas
    1=A     #  All equal to 1?
        @   # Length of each inner list
            # Take the maximum
            # Implicit output

```

# Answer
> 4 votes
# julia, ~~24~~ 22 bytes

*Edit: 2-byte improvement due to MarcMush*

Same approach as most others here, counting how many times `v` can be intersected with `v-1` before we get an empty list

```
!v=v>[]&&!(v∩.~-v)+1

```

Attempt This Online!

### How?

```
!v =
  v > [] &&         # return 0 if v == [] and terminate, otherwise proceed
  !(v ∩ .~ -v) + 1  # recurse on the intersection of v with v + 1 and add 1
                      to count recursion depth. Here, ~ is bitwise not, so
                      ~(-k) == k-1 for signed integers.

```

# Answer
> 3 votes
# Python, ~~122~~ ~~113~~ ~~101~~ ~~52~~ 51 bytes

Port of Arnaulds answer

```
lambda a:max(map(g:=lambda v:v in a and-~g(v+1),a))

```

Attempt This Online!

Previous Answer

```
lambda a:max(len([*l])for b,l in groupby(r in a for r in range(max(a)+1))if b)
from itertools import*

```

Attempt This Online!

# Answer
> 3 votes
# Factor \+ `math.extras`, 51 bytes

```
[ sort members [ - -1 = ] max-monotonic-count 1 + ]

```

Attempt This Online!

Sort, uniquify, then count the longest run of two adjacent numbers differing by one.

# Answer
> 2 votes
# JavaScript (ES6), 51 bytes

```
a=>Math.max(...a.map(g=v=>a.includes(v)&&1+g(v+1)))

```

Try it online!

### Commented

```
a =>                 // a[] = input array
Math.max(...         // return the maximum value in this:
  a.map(g = v =>     //   for each value v in a[],
                     //   using a recursive callback function g:
    a.includes(v) && //     if a[] includes v:
      1 +            //       increment the final result
      g(v + 1)       //       and do a recursive call with v + 1
  )                  //   end of map()
)                    // end of Math.max()

```

---

# JavaScript (ES6), 56 bytes

*This version was originally shorter (50 bytes), but invalid (as pointed out by Dominic van Essen). Now fixed at the cost of 6 bytes by adding `p^v?...:0`, which makes it uncompetitive.*

Expects an `Uint32Array`.

```
a=>a.sort().map(p=v=>p^v?p+1^(p=v)?i=1:m+=++i>m:0,m=1)|m

```

Try it online!

# Answer
> 2 votes
# Ruby, ~~48~~ 47 bytes

```
->l{1.step.find{|z|l.all?{|x|[*x..x+z]-l!=[]}}}

```

Try it online!

# Answer
> 2 votes
# Nibbles, ~~5.5~~ 5 bytes (10 nibbles)

```
,|`.$`&+~$

```

Attempt This Online!

Port of ovs' Jelly answer.

```
,|`.$`&+~$    # full program
,|`.$`&+~$$   # with implicit arg:
  `.          # iterate while unique
    $         # starting with input:
       +~$    #   add 1 to every element
     `&       #   intersection with original list
 |            # now, filter this list-of-lists
          $   #   to include only non-empty lists
,             # and return its length

```

# Answer
> 2 votes
# Nekomata, 7 bytes

```
ˡ{N→ᵈ:∩

```

Attempt This Online!

A port of @ovs's Jelly answer.

```
ˡ{N→ᵈ:∩
ˡ{          Loop until failure, and return the number of iterations
  N             Check if the list is nonempty
   →            Increment
    ᵈ:∩         Intersect with the input

```

# Answer
> 2 votes
# **T-SQL**, 114 bytes

`SELECT MAX(c)FROM(SELECT COUNT(b)c FROM(SELECT a*(a+1)/2-SUM(a)OVER(ORDER BY a)b FROM @t GROUP BY a)X GROUP BY b)Y`

dbfiddle

Readable version of the code:

```
DECLARE @t TABLE(i INT NOT NULL IDENTITY(1,1) --table with identity to emulate a 'list' (not counted in byte count)
                , a INT NOT NULL);

INSERT INTO @t (a) --Assigning the 'list' values (not counted in byte count)
VALUES(100)
    , (4)
    , (200)
    , (1)
    , (3)
    , (2);

SELECT MAX(c) --5. Determine the maximum count from the subquery
FROM(
    SELECT COUNT(*)c --4. Count how many rows make up each group
    FROM(
        --After this query it is simply a matter of determining which value of b appears the most times, and how many times that is.
        SELECT a*(a+1)/2-SUM(a) OVER(ORDER BY a)b /*2. Calculates the sum of values which are missing from the consecutive sequence
                                                between 1 and a (both inclusive).
                                                This utilises the default behaviour of the windowed function. This defaults to:
                                                SUM(a) OVER(ORDER BY a ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
                                                Which is far more descriptive, but too verbose for golf :).*/
        FROM @t
        GROUP BY a --1. Removes duplicate occurences of a, as this is just noise anyway...
    )X --necessary alias
    GROUP BY b -- 3. Group by b as these are the groups we want to know the size of
)Y --necessary alias

```

This algorithm does the following:

* Remove duplicate elements (essentially turn a list into a set)
* Order the elements
* Find all the consecutive sequences
* Prescribe a unique identifier for each consecutive sequence
* Get the count of elements in each distinct sequence (length of each sequence)
* Get the maximum count.

In my opinion the interesting part of this is prescribing the unique identifier. Let's generalise the problem, starting with an arbitrary subset of the natural numbers.

$$X \subseteq \mathbb N\_{\ne 0}$$

Consider the following binary relation

$$R = \\{(a, b): |a - b| \leq 1, (a, b) \in X \times X\\}$$ `R` is the set of all ordered pairs which are no more than 1 distance apart. Here the distance is taxicab or L1 or whatever you want to call it.

It's fairly easy to see that `R` is symmetric, and reflexive, but NOT transitive.

Take the example $$X = \\{1, 2, 3, 5, 6, 7, 8\\}$$ $$(1, 2) \in R , (2, 3) \in R , (1, 3) \notin R$$

You can't have three distinct natural numbers all within a distance of 1 from eachother.

We need to extend the definition of `R` so that it is transitive. We need to find the transitive closure of `R`.

$$R^{+} = R \cup \\{(a, c): (a, b) \in R \wedge (b, c) \in R\\}$$

Now we have an equivalence relation, and it properly describes the equivalence classes that underly this problem. However we still need to determine a label for each of these equivalence classes. Normally the smallest positive representitve of each equivalence class is chosen. This would be `[1]` and `[5]` in the example above. But these are just labels, as long as they are unique they could be anything. Let's make a function that sufficiently labels an element's equivalence class.

$$Label(i) = \sum\_{k=1}^{i} k - \sum\_{j\in X \wedge j\leq i}{j}$$

We can replace the first sum with the equivalent expression $$ \sum\_{k=1}^{i} k = \frac{i(i + 1)}{2}$$

Thus, $$Label(i) = \frac{i(i + 1)}{2} - \sum\_{j\in X \wedge j\leq i}{j}$$

Intuitively this is just the sum of everything 'missing' up to the current element.

$$Label(i) = \sum\_{j \in \mathbb N\_{\ne 0} \setminus X \wedge j \leq i} j$$

Now i am really interested, is there a generalisation of this? That is to say if we take the base relation `R` and redefined it:

$$R = \\{(a, b): |a - b| \leq k, (a, b) \in X \times X\\}, k \in \mathbb N\_{\ne 0}$$

Would there be an equivalent intuitive 'label function' for any value of `k`?

# Answer
> 2 votes
# 05AB1E, 6 bytes

```
ZLåγOà

```

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

Try it online or verify all test cases.

**Explanation:**

```
Z       # Push the maximum of the (implicit) input-list (without popping)
 L      # Pop and push a list in the range [1,max]
  å     # Check for each value whether it's in the input-list (1 if truthy; 0 if falsey)
   γ    # Group adjacent equal bits together
    O   # Sum each inner list
     à  # Pop and push the maximum
        # (which is output implicitly as result)

```

---

Since I was curious: a port of *@ovs*' Jelly answer is 8 bytes instead:

```
.ΓÐ<åÏ}g

```

Try it online or verify all test cases.

**Explanation:**

```
.Γ    }   # Continue until the list no longer changes, keeping all intermediate results
          # (excluding the initial value), using the (implicit) input-list
  Ð       #  Triplicate the current list
   <      #  Pop the top copy, and decrease all its values by 1
    å     #  Pop it and another list, and check for each value-1 whether it's in thelist
     Ï    #  Pop both again, and keep all values at the truthy positions
       g  # After the changes-loop: pop and push its length
          # (which is output implicitly as result)

```

# Answer
> 2 votes
# Charcoal, ~~23~~ ~~19~~ 13 bytes

```
ＩＬ⌈⪪⭆⊕⌈θ¬№θι1

```

Try it online! Link is to verbose version of code. Explanation: Port of @JonathanAllan's Jelly answer, with the "untruth" replaced by a map over range using `0` for present and `1` for absent as this lets me split on `1`s to find the longest run of `0`s. (I can't split on `0`s as this will fail if there are `10` of the same value in the list.)

```
       θ        Input list
      ⌈         Maximum
     ⊕          Incremented
    ⭆           Map over implicit range and join
         №      Count of
           ι    Current value
          θ     In input list
        ¬       Logical Not
   ⪪        1   Split on `1`s
  ⌈             Take the longest run of `0`s
 Ｌ              Take the length
Ｉ               Cast to string
                Implicitly print

```

Previous 19-byte solution also works with negative integers:

```
Ｉ⌈Ｅθ⌈Ｅθ∧¬⁻…·ιλθ⊕⁻λι

```

Try it online! Link is to verbose version of code. Explanation: Creates inclusive ranges between all pairs of input elements and outputs the length of the longest range that is a subset of the input.

```
   θ                Input array
  Ｅ                 Map over elements
      θ             Input array
     Ｅ              Map over elements
          …·        Inclusive range from
            ι       Outer value to
             λ      Inner value
         ⁻          Remove elements found in
              θ     Input array
        ¬           Is empty
       ∧            Logical And
                 λ  Inner value
                ⁻   Minus
                  ι Outer value
               ⊕    Incremented
    ⌈               Take the maximum
 ⌈                  Take the maximum
Ｉ                   Cast to string
                    Implicitly print

```

# Answer
> 2 votes
# Perl 5, 32 bytes

```
sub f{@_?1+f(grep$_+1~~@_,@_):0}

```

Try it online!

Copied idea from others here. Return count of rounds of removal of ints n where n+1 dont exists before list is empty.

# Answer
> 2 votes
# Rust, 74 bytes

Try it online!

```
|a:&[u8]|(*a.iter().min().unwrap()..).take_while(|x|a.contains(x)).count()

```

Explanation:

```
let f = |a: &[u8]| {
    // create an iterator starting from the least element
    (*a.iter().min().unwrap()..)
        // take item if in list, stopping at the first item not in list
        .take_while(|x| a.contains(x))
        // get total number of items taken
        .count()
};

```

# Answer
> 1 votes
# Retina 0.8.2, 51 bytes

```
$
,
\d+
$*
D`1+,
O`1+
(\G1+, |1\1)+
$#1¶
O#^`
1G`

```

Try it online! Link includes test cases. Explanation:

```
$
,

```

Suffix a comma to the last entry too.

```
\d+
$*

```

Convert to unary.

```
D`1+,

```

Deduplicate.

```
O`1+

```

Sort ascending.

```
(\G1+, |1\1)+
$#1¶

```

Count consecutive sequences. The first alternation is only possible at the start of the match, while the second alternation is only possible on subsequent repetitions of the capture group.

```
O#^`

```

Sort descending numerically.

```
1G`

```

Take the first (i.e. largest).

# Answer
> 1 votes
# Excel, 65 bytes

```
=MAX(LEN(TEXTSPLIT(CONCAT(FREQUENCY(A1#,SEQUENCE(MAX(A1#)))),0)))

```

Input is spilled *vertical* array in `A1#`.

# Answer
> 1 votes
# C (clang 16), 93 bytes

Using C23 `_BitInt(65536)` as a clang extension in C89 for implicit `int`. Works for input integers in the range \[0,65535\], e.g. 16-bit unsigned (but it takes them as an array of `int`, with an `int n` length). It returns the count.

```
typedef _BitInt(1<<16)T;f(*p,n){T b=0;for(;n--;)b|=(T)1<<p[n];for(n=1;b&=b<<1;n++);return n;}

```

First loop: Add each input to a set implemented as a bitmap (`bitset |= 1<<n`). Second loop: treating that as a wide integer, count the longest run of set bit. (Shift and AND to remove the low bit from each run of bits, count iterations until the whole thing becomes zero.)

Godbolt including a test caller with the test cases from the question.

See Add two really big numbers re: `_BitInt`. Clang 16 supports very large widths: the current max is 8388608 bits for signed or unsigned, `_BitInt(1<<23)`. So not enough to handle values up to `INT_MAX`, but we don't handle negative `int` values either.

And yes, shifting and ANDing a 64KiB bitmap as a wide integer takes a ridiculous amount of asm instructions since clang fully unrolls it. I used `_BitInt(1<<8)` while developing this to keep edit/compile/run cycles short. With 1\<\<16 width, `clang16 -std=gnu89 -Os -Wall -Wno-implicit-int` makes 24249 lines of asm for x86-64 (only a couple of them labels instead of instructions.) It also uses about 30472 + 128 (red zone) = 30600 bytes of stack space. (64Kib = 8KiB)

Ungolfed:

```
typedef _BitInt(1<<8) T;   // narrower for testing with small number inputs
/* int */ ungolfed(int *p, int n){
    T bitset = 0;
    for(;n--;){
        bitset |= (T)1<<p[n];   // cast needed *before* the shift
    }
    int retval=1;            // reuse n for this in the golfed version
    // https://stackoverflow.com/questions/3304705/finding-consecutive-bit-string-of-1-or-0
    while(bitset &= bitset<<1){ // doesn't count the iteration that clears the last bit, hence retval=1 to start
        retval++;
    }
    return retval;
}

```

With `clang -fsanitize=undefined`, it will reject out-of-bounds inputs, e.g. *runtime error: shift exponent 200000 is too large for 65536-bit type 'T' (aka '\_BitInt(65536)')*

# Answer
> 1 votes
# Google Sheets, 61 bytes

`=sort(max(len(split(join(,frequency(A:A,sequence(9^4))),0))))`

Put the input in cells `A1:A` and the formula in `B1`.

Uses `frequency()` like the Excel answer. Does not require CSE.

# Answer
> 1 votes
# Haskell + hgl, 19 bytes

```
l<ixe(fl~<(<P1)<fe)

```

Uses xnor's method.

## 20 bytes

Here's one that works online:

```
P1<l<ih eq1<δ<sr<nb

```

Attempt This Online!

### Explanation

* `nb` removes all duplicates from the list
* `sr` sorts the list
* `δ` gets the differences between consecutive elements
* `ih eq1` gets the longest contiguous sublist of `1`s
* `l` takes the length
* `P1` adds 1

## Reflection

Some things can be improved:

* The glue in `fl~<(<P1)<fe` is too much, there should be some helper function that can reduce the amount of glue here.
* `sr<nb` could probably be a single function.

# Answer
> 1 votes
# Uiua, 8 bytes

```
/↥⊜⧻.⍘⊚⊝

```

Try it!

Inspired by Dominic van Essen's Uiua answer.

```
/↥⊜⧻.⍘⊚⊝
       ⊝  # deduplicate
     ⍘⊚   # inverted where, i.e. how many times each element occurs
  ⊜⧻.     # lengths of contiguous equal elements
/↥        # maximum

```

Original answer:

# Uiua, 18 bytes

```
+1/↥⊜⧻.=1≡/-◫2⊝⊏⍏.

```

Try it!

```
+1/↥⊜⧻.=1≡/-◫2⊝⊏⍏.
               ⊏⍏.  # sort
              ⊝     # deduplicate
            ◫2      # windows of size two
         ≡/-        # difference of each window
       =1           # change non-ones to zeros
    ⊜⧻.             # find length of each contiguous group of ones
  /↥                # maximum
+1                  # plus one

```

# Answer
> 1 votes
# Uiua, 12 bytes

```
/↥⍘⊚-⇡⧻.⊝⊏⍏.

```

Try it!

```
/↥⍘⊚-⇡⧻.⊝⊏⍏.
         ⊏⍏.  # sort
        ⊝     # deduplicate
     ⇡⧻.      # copy & make series of same length
    -         # subtract
  ⍘⊚          # invert where
/↥            # maximum

```

---
Tags: code-golf, array, integer
---


title: Make a Plain PIE!

text:
# Question
Title: Make a Plain PIE!
**(2 Jan 2018) Because of the winning criteria I am going to accept the Jelly answer, but I am also giving upvotes to all other answers which all use astounding methods as well**

## Introduction

There are lots of challenges asking for a shortest program to calculate mathematical constants. I saw some with restrictions like banning the literals 3.14 and π etc. However, there seems no such challenges using the number of distinct characters as one of the criteria.

## The Challenge

~~Make a Plain PIE using the fewest kinds and least amount of ingredients but still yummy enough~~

Write a code that calculates π\*e to at least 10 decimal places, that uses as *FEW* distinct characters (and de facto numeric literal characters) and as short as possible.

This challenge is not banning numeric literals; instead they are discouraged. Numeric literals are *seasonings* ;)

## Requirements

* The code must be a full program receiving no inputs and outputting the result, or a function which can be called with no arguments either outputting or returning the result. Lambdas are allowed.
* The result must start with `8.5397342226` and must be in a *numeric type*. There should only be one output/return in the main program/function. Sub-functions are allowed.

## Restrictions

* String-to-number conversion functions *that trivially turn the string literal to a number it represents* are not allowed unless explicitly declared and implemented within the code. Also, *NO implicit conversions from strings to numbers*.
    + eg. `eval`, `Number()`, `parseInt()` and `"string" * 1`
    + Character-code functions and length functions like `ord`, `String.charCodeAt(n)` and `String.length` are allowed because they do not trivially convert the string into the corresponding number.
* Use of the following built-ins are not allowed:
    + Mathematical constants, or any built-in functions that evaluates to those constants directly
        - eg. `Math.PI` in JS, `žs` in 05AB1E (because it evaluates to π directly)
    + Trigonometric functions and the exponential function, unless explicitly defined and implemented in the code.
        - eg. `Math.atan` and `Math.exp` in JS
        - Built-in power functions and exponentiation operators (eg. \** or ^) are allowed, given that they receive 2 arguments/operands (WLOG `a` and `b`) and returns ab
* The length of each run of numeric literal used must not be longer than 5 (eg. `12345` allowed (but not encouraged), but `123456` is not allowed).
* Standard loopholes apply.

## Scoring

* The scoring is divided into three parts:
    + **Distinctness**: Scored by counting the number of distinct characters used. Uppercase and lowercase are counted separately. However, the following characters must each be counted as 10 characters:
        - Hexadecimal digits: `0123456789abcdefABCDEF`
        - Decimal points: `.`
        - Any other single characters that may be used as numeric literals (applicable in golfing languages)
    + **Size**: Scored by the length of the code in bytes.
    + **Accuracy**: Scored by the number of correct digits counting from the decimal point. Any digits after the first wrong digit are not counted. For fairness, a maximum of 15 digits are counted. The value of π\*e according to WolframAlpha is `8.539734222673567(06546...)`.
* The total score is calculated by `(Distinctness * Size) / Accuracy`

## Winning Criteria

The answer with the lowest score wins. If tied then the candidate answer which is posted earlier wins.

For non-golfing languages, the score can be calculated using the following snippet (For some golfing languages, the snippet does not work since this checks for UTF-8 length of the code only):

```
$(document).ready(() => {
 $("#calculate").on("click", () => {
  var count = {};
  var distinct = 0;
  var nonnums = 0;
  var numerals = 0;
  var length = 0;
  for (const c of [...$("#code").val()]) {
   count[c]++;
   if (c.charCodeAt(0) <= 0x7F)
    length += 1;
   else if (c.charCodeAt(0) <= 0x3FF)
    length += 2;
   else if (c.charCodeAt(0) >= 0xD800 && c.charCodeAt(0) <= 0xDFFF)
    length += 4;
   else
    length += 3;
  }
  for (const c in count) {
   if ("0123456789abcdefABCDEF.".indexOf(c) == -1) {
    nonnums += 1;
    distinct += 1;
   }
   else {
    numerals += 1;
    distinct += 10;
   }
  }

  var output = $("#output").val();
  var match = /^8\.(5397342226(7(3(5(67?)?)?)?)?)/.exec(output);
  if (match == null)
   $("#result").html("The result does not have 10-digit accuracy!");
  else {
   var accuracy = match[1].length;
   $("#result").html(`
    Size        : ${length} bytes<br>
    Distinctness: ${distinct} (Numerals: ${numerals}, Non-numerals: ${nonnums})<br>
    Accuracy    : ${accuracy} decimal places<br>
    Score       : ${(distinct * length / accuracy).toFixed(2)}
   `);
  }
 });
});
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<h2>Calculator for Non-esoteric Programming Languages (BASIC-like, C-like, Python, Ruby, etc.)</h2>
Code: <br><textarea cols=50 rows=10 id="code"></textarea><br>
Output: <input id="output"><br>
<input type="button" id="calculate" value="Calculate Score">
<pre id="result"></pre>
```

## Example

**Submission**

# JavaScript(ES6), S=141, D=49, A=12, 575.75pt

```
(t=()=>{for(f=o=9/9;++o<9999;)f+=o**-(9>>9/9);return (f*(9*9+9))**(9/9/(9>>9/9))},u=()=>{for(f=o=r=9/9;++o<99;){f+=r;r/=o}return f})=>t()*u()

```

Output: `8.53973422267302`

**Scoring**

```
Size        : 141 bytes
Distinctness: 49 (Numerals: 3 (use of "9", "e" and "f")), Non-numerals: 19)
Accuracy    : 12 decimal places
Score       : 575.75

```

# Answer
> 1 votes
# Jelly, 11 × 38 ÷ 10 = 41.8

```
“Þẹjuụ’÷ȷ10

```

Try it online!

# Explanation

```
“Þẹjuụ’÷ȷ10  Main Link
“Þẹjuụ’      85397342226
       ÷     Divided by
        ȷ10  1e10

```

# Answer
> 5 votes
# Mathematica, (18\*226)/15 = 271

only 1s

```
N[1+1+1+1+1+1+1+1+1/(1+1/(1+1/(1+1+1+1+1+1/(1+1/(1+1+1+1/(1+1/(1+1+1+1+1/(1+1+1+1+1+1+1+1+1+1+1+1+1/(1+1+1+1/(1+1+1/(1+1/(1+1+1+1+1+1/(1+1+1/(1+1+1+1+1+1+1+1+1+1+1+1+1/(1+1/(1+1)))))))))))))))),1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1]

```

Try it online!

# Mathematica, 244

1s & 2s

```
N[2+2+2+2+1/(1+1/(1+1/(1+2+2+1/(1+1/(1+2+1/(1+1/(2+2+1/(12+1/(1+2+1/(2+1/(1+1/(1+2+2+1/(2+1/(12+1/(1+1/(1+1)))))))))))))))),12+2+2]

```

Try it online!

# Answer
> 4 votes
# Mathematica, 257.6

```
N[2Integrate[Sqrt[1-n^2],{n,-1,1}],22]Sum[1/n!,{n,0,22}]

```

Try it online!

# Mathematica, 276

this is accurate to **4095 digits**

```
N[2Integrate[Sqrt[1-n^2],{n,-1,1}],2^12]Sum[1/n!,{n,0,2^12}]

```

Try it online!

# Answer
> 3 votes
# Imperative Tampio, 2206.46

```
K:lla on h:t.K:n z on riippuen siitä,onko sen h:iden määrä nolla,joko nolla tai sen ensimmäinen h lisättynä uuden K:n,jonka h:t ovat sen h:t toisesta alkaen eikä muuta,z:aan jaettuna kymmenellä.Kun iso sivu avautuu,se näyttää uuden K:n,jonka h:ita ovat kolme lisättynä viiteen,viisi,kolme,neljä lisättynä viiteen,7,kolme,neljä,kaksi,kaksi,kaksi,kuusi,7,kolme,viisi ja 7 eikä muuta,z:n.

```

> K:lla **on** h:t.K:n z **on** **riippuen** **siitä**,**onko** sen h:iden määrä `nolla`,**joko** `nolla` **tai** sen `ensimmäinen` h **lisättynä** **uuden** K:n,**jonka** h:t **ovat** sen h:t `toisesta` **alkaen** **eikä** **muuta**,z:aan **jaettuna** `kymmenellä`.**Kun** iso sivu *avautuu*,se *näyttää* **uuden** K:n,**jonka** h:ita **ovat** `kolme` **lisättynä** `viiteen`,`viisi`,`kolme`,`neljä` **lisättynä** `viiteen`,`7`,`kolme`,`neljä`,`kaksi`,`kaksi`,`kaksi`,`kuusi`,`7`,`kolme`,`viisi` **ja** `7` **eikä** **muuta**,z:n.

Online version

Tampio has an advantage that number literals can be written using letters instead of digits. I also noticed that the interpreter thinks that one-letter words are nouns, so I can use them as identifiers. Of course, this language is so verbose that it won't help it to win any challenge.

Ungolfed:

> Listalla **on** alkiot.
>
> Listan lukuarvo **on** **riippuen** **siitä**, **onko** sen alkioiden määrä `nolla`,
>
> * **joko** `nolla`
> * **tai** sen `ensimmäinen` alkio **lisättynä** **uuden** listan, **jonka** alkiot **ovat** sen alkiot `toisesta` **alkaen** **eikä** **muuta**, lukuarvoon **jaettuna** `kymmenellä`.
>
> **Kun** nykyinen sivu *avautuu*,
>
> * se *näyttää* **uuden** listan, **jonka** alkioita **ovat** `8`,`5`,`3`,`9`,`7`,`3`,`4`,`2`,`2`,`2`,`6`,`7`,`3`,`5` **ja** `7` **eikä** **muuta**, lukuarvon.

# Answer
> 2 votes
# APL, 6×124÷15 = 49.6 points

```
zz+zz+zz+zz+÷z+÷z+÷z+zz+zz+÷z+÷z+zz+÷z+÷zz+zz+÷zz+zz+zz+zz+zz+zz+÷z+zz+÷zz+÷z+÷z+zz+zz+÷zz+÷zz+zz+zz+zz+zz+zz+÷z+÷zz←z+z←⍴⍴⍬

```

Try it online! (Paste in the code then hit Ctrl+Enter.)

Assigns `1` to `z`, then abbreviates `z+z` to `zz`, and then approximates the continued fraction of `πe` as `8+1/(1+1/(1+1/(5+1/(1+1/(3+1/(1+1/(4+1/(10+1/(3+1/(2+1/(1+1/(5+1/(2+1/(12+1/(1+1/2)))))))))))))))` (inspired by Jenny\_mathy’s Mathematica answer).

`1` is computed as `⍴⍴⍬`: the dimensions vector (`1`) of the dimensions vector (`0`) of the empty vector ().

Because of APL’s `÷` reciprocal operator and right-to-left grouping rules, this representation doesn’t even need parentheses. We use 6 distinct non-numeric symbols: `z+÷←⍴⍬`

---

This code should work in any APL dialect; the only important thing is that there is one where

* the answer is printed to 15 figures by default;
* the glyphs are encoded as one byte each (i.e. source code is in some custom APL codepage, not UTF-8).

Graham reports that APL+Win fits the bill.

# Answer
> 2 votes
# Desmos, 199 bytes, Score = 199\*(3\*10+22)/11 = 940.73

```
h=g(\left\{\right\}+\left\{\right\})\int_{-\left\{\right\}}^{\left\{\right\}}\sqrt{\left\{\right\}-x^{\left\{\right\}+\left\{\right\}}}dx
\int_{\left\{\right\}}^{g}\left\{\right\}/xdx~\left\{\right\}

```

Try it on Desmos! Stores the result in variable `h`.

Calculates the exact values of \\$\pi\\$ and \\$e\\$ using integrals, and multiplies them together. This should theoretically yield a perfect score of 0, but Desmos only displays values to a precision of 11 decimal digits. Also, this code does not use the characters `0123456789`, instead opting for strings of `\left\{\right\}`, which are condition-less piecewise functions that evaluate to 1.

Equivalent equations:

\\$h=2g\int\_{-1}^{1}\sqrt{1-x^2}dx\\$ (\\$e\\$ * area of circle with radius 1)

\\$\int\_{1}^{g}\frac{1}{x}dx\sim1\\$ (\\$e\\$ is the unique positive real value of \\$c\\$ such that \\$\int\_{1}^{c}\frac{1}{x}dx=1\\$; the \\$\sim\\$ tells Desmos that the equation is a regression, and therefore needs to solve for g)

# Answer
> 1 votes
# Swift, ~~116 * 39 / 14 ≈ 323.14~~ 114 * 39 / 14 ≈ 317.57

```
print(2+2+2+2+1/(1+1/(1+1/(2+2+1+1/(1+1/(2+1+1/(1+1/(2+2+1/(12+1/(2+1+1/(2+1/(1+1/(2+2+1+1/(2+1/12.2))))))))))))))

```

Try it online!

Uses a continued fraction to approximate π\*e to 14 decimal places

# Answer
> 1 votes
# Pyt, ~~22\*73/11=146~~ ~~22\*72/11=144~~ ~~23\*53/11~~ 22\*39/11=78

```
1⁺1⁺⁺⁺⁺⁺^ř⁻Đ!⇹1⁺*⁺‼/Ʃ1⁺*1⁺⁺1⁺⁺⁺⁺*ř⁻!⅟Ʃ*

```

Uses approximations for π and e, respectively.

Per the codepage (which is in the interpreter2 file), each character is one byte.

Explanation (stuff in brackets is what is used from the stack):

```
1⁺1⁺⁺⁺⁺⁺^ř⁻Đ!⇹1⁺*⁺‼/Ʃ1⁺*           makes π

1⁺1⁺⁺⁺⁺⁺^         makes 64
(64)ř             makes a list [1,2,...,64]
([1,...,64])⁻     subtracts one from each element in the list
([0,...,63])Đ     duplicates list (on top of stack twice)
([0,...,63])!     performs element-wise factorial
([...],[...])⇹    swaps top two items on the stack
([...])1⁺*⁺       doubles all values in list and adds one
([...])‼          element-wise double factorial
([...],[...])/    divides element-wise
([...])Ʃ          sums all elements in the list (approximately π/2)
(π/2)1⁺*          doubles (yields π)

1⁺⁺1⁺⁺⁺⁺*ř⁻!⅟Ʃ

1⁺⁺1⁺⁺⁺⁺*         makes 15
         ř⁻       makes a list [0,1,...,14]
           !      Takes the factorial of each element in the list
            ⅟     Finds the multiplicative inverse of each element
             Ʃ    Sums the list (e)

(π,e)*              multiplies
                    (implicit print)

```

Try it online!

---
Tags: math, number, code-challenge
---


title: Visualise the Euclidean GCD

text:
# Question
Title: Visualise the Euclidean GCD
The Euclidean GCD Algorithm is an algorithm that efficiently computes the GCD of two positive integers, by repeatedly subtracting the smaller number from the larger number until they become equal. It can be visualised as such:

We start with a MxN grid, where M and N are the numbers. In this example I'll use M=12, N=5:

```
       12
  ____________
 |
 |
5|
 |
 |

```

We then, going from the top left, remove a square with a side length of the smaller of the two values, 5, leaving a 7x5 rectangle. This is visualised by replacing the last column of the 5x5 square with a column of `|`s.

```
          7
  ____________
 |    |
 |    |
5|    |
 |    |
 |    |

```

We then remove another 5x5 square, leaving a 2x5 rectangle:

```
            2
  ____________
 |    |    |
 |    |    |
5|    |    |
 |    |    |
 |    |    |

```

Next, we remove two 2x2 squares, leaving a 2x1 rectangle. As these squares are added when the rectangle is taller than it is wide, their bottom rows are replaced with rows of `_`s.

```
            2
  ____________
 |    |    |
 |    |    |__
 |    |    |
 |    |    |__
1|    |    |

```

And finally, we remove a 1x1 square, leaving a 1x1 square, whose last and only column is replaced with a `|`. As this is a square, the two sides are equal, so the GCD of 12 and 5 is 1.

The final visualisation looks like this. Note that the numbers are not included, those were just visual indicators.

```
    |    |
    |    |__
    |    |
    |    |__
    |    ||

```

Here's a larger example for M=16, N=10. (I'm not going to go through all the steps here).

```
         |
         |
         |
         |
         |
         |______
         |   |
         |   |__
         |   |
         |   |

```

Note that, as gcd(16, 10) = 2, the algorithm ends with a 2x2 square.

Your challenge is to implement this visualisation, given two numbers M and N where M \> N. Your output may have any amount of leading/trailing whitespace.

## Testcases

```
12, 5 ->
    |    |
    |    |__
    |    |
    |    |__
    |    ||

10, 16 ->
         |
         |
         |
         |
         |
         |______
         |   |
         |   |__
         |   |
         |   |
25, 18 ->
                 |
                 |
                 |
                 |
                 |
                 |
                 |_______
                 |
                 |
                 |
                 |
                 |
                 |
                 |_______
                 |   |
                 |   |
                 |   |___
                 |   |||

25, 10 ->
         |         |
         |         |
         |         |
         |         |
         |         |_____
         |         |
         |         |
         |         |
         |         |
         |         |

34, 15 ->
              |              |
              |              |
              |              |
              |              |____
              |              |
              |              |
              |              |
              |              |____
              |              |
              |              |
              |              |
              |              |____
              |              |  |_
              |              |  |_
              |              |  |

89, 55 ->
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |
                                                      |__________________________________
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |
                                                      |                    |_____________
                                                      |                    |       |
                                                      |                    |       |
                                                      |                    |       |
                                                      |                    |       |
                                                      |                    |       |_____
                                                      |                    |       |  |
                                                      |                    |       |  |__
                                                      |                    |       |  ||

```

# Answer
# Charcoal, 43 bytes

```
ＮθＮηＢθη Ｗ⁻θη¿›θη«≧⁻ηθＭ⊖η→Ｐ↓η→»«≧⁻θηＭ⊖θ↓⟦×_θ

```

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

```
ＮθＮη

```

Input `M` and `N`.

```
Ｂθη

```

Draw an `M×N` box. This solves two problems; firstly, in case one value divides the other, as I assume I'm not allowed `-N` trailing white space; secondly, in case `M>N`, as I assume I'm not allowed `1-N` leading white space.

```
Ｗ⁻θη

```

Repeat until `M=N`.

```
¿›θη«

```

If `M>N`, then:

```
≧⁻ηθ

```

Subtract `N` from `M`.

```
Ｍ⊖η→

```

Move `N-1` to the right.

```
Ｐ↓η

```

Draw `N` `|`s downwards.

Move to the right.

```
»«

```

Otherwise, if `N>M`:

```
≧⁻θη

```

Subtract `M` from `N`.

```
Ｍ⊖θ↓

```

Move `M-1` down.

```
⟦×_θ

```

Draw `M` `_`s and move down.
> 2 votes

# Answer
# JavaScript (V8), 128 bytes

```
x=>h=(y,i=x,j=y)=>j?(g=(x,y)=>i?y-j+1|x<i?x-i+1|y<j?x>y?g(x-y,y):x<y?g(x,y-x):' ':'|':'_':`
`)(x,y)+(i?h(y,i-1,j):h(y,x,j-1)):''

```

Try it online!
> 1 votes

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


title: Make a super fair number

text:
# Question
Title: Make a super fair number
An even distribution number is a number such that if you select any of it's digits at random the probability of it being any particular value (e.g. `0` or `6`) is the same, \\$\frac1{10}\\$. A precise definition is given later on.

Here are a few examples:

* \\$\frac{137174210}{1111111111} =0.\overline{1234567890}\\$ is an even distribution number.
* \\$2.3\\$ is not an even distribution number since 7 of the digits `1456789` never appear and all but two of the digits are `0`.
* \\$1.023456789\\$ may look like it's an even distribution number, but for this challenge we count all the digits after the decimal point, including all the `0`s. So nearly all the digits are `0`, and the probability of selecting anything else is \\$0\\$.

Precisely speaking if we have a sequence of digits \\$\\{d\_0^\infty\\}\\$ then the "probability" of a particular digit \\$k\\$ in that sequence is:

\\$ \displaystyle P(\\{d\_0^\infty\\},k) = \lim\_{n\rightarrow\infty}\dfrac{\left|\\{i\in\[0\dots n\], d\_i=k\\}\right|}{n} \\$

That is if we take the prefixes of size \\$n\\$ and determine the probability that a digit selected uniformly from that prefix is \\$k\\$, then the overall probability is the limit as \\$n\\$ goes to infinity.

Thus an even distribution number is a number where all the probabilities for each \\$k\\$, converge and give \\$\frac1{10}\\$.

Now a super fair number is a number \\$x\\$ such that for any rational number \\$r\\$, \\$x+r\\$ is an even distribution number.

# Task

Output a super fair number. Since super fair numbers are irrational you should output as an infinite sequence of digits. You can do this using any of the defaults.

This is so the goal is to minimize the size of your source code as measured in bytes.

# Answer
> 5 votes
# Jelly, ~~4~~ 3 bytes

```
‘Ṙß

```

Try it online!

# Jelly, 7 bytes (if leading `0.` is required)

```
.1¹2‘Ṙ¿

```

Try it online!

A niladic link that takes no arguments and prints Champernowne’s constant, one of the few numbers that have been proven ‘normal’, which is the more common term for this type of number (though the request here is more specifically for an irrational ‘simply normal’ number in base 10 which is an easier target to meet).

Thanks to @JonathanAllan for saving a byte!

# Answer
> 4 votes
# , ~~26~~ 19 bytes

```
\(n)sample(0:9,n,T)

```

Attempt This Online!

Function that returns `n` digits, representing the digits after the decimal point.
The particular choice of super-fair number returned changes each time the function is called, since the digits are random.
Add +14 bytes to output digits from the same super-fair number on successive calls.

# Answer
> 4 votes
# , ~~19~~ 18 bytes

```
repeat cat(F<-F+1)

```

Try it online!

Like my other answer, this outputs Champernowne’s constant. Thanks to @DominicVanEssen for saving a byte!

# Answer
> 4 votes
# Python, 31 bytes

```
i=0
while[print(i,end="")]:i+=1

```

Attempt This Online!

Edit: since someone is downvoting all the Champernowne constant answers, I thought that I should prove that it is a super fair number.

I don't have time to write a formal proof right now, but the basic idea is that as you move further along Champernowne constant the period of the digits of the rational number gets insignificant compared to the period of most digits (of i).

This essentially means that we can treat the effect of the rational number as (a combination of) constant offsets. Applying a constant offset just has the effect of "rotating" when digits appear; it doesn't change their frequency.

Essentially the point is that only digits in the "middle" of i really matter, and what happens at the edges doesn't.

# Answer
> 3 votes
# 05AB1E, ~~8~~ 2 bytes

```
∞S

```

Try it online! Outputs as a list of digits.

# Answer
> 1 votes
# Charcoal, 9 bytes

```
⭆Ｎ⁺‽χ….¬κ

```

Try it online! Link is to verbose version of code. Explanation: Prints `i` random digits.

If `e` is ever proven normal, then for 8 bytes:

```
×ψ⊕Ｎ¤≕E

```

Try it online! Link is to verbose version of code. Explanation: Prints the first `i` digits of `e`, which is believed to be normal.

# Answer
> 1 votes
# Nibbles, 3 bytes (6 nibbles)

(or **4 bytes (8 nibbles)** if leading `0.` is required.

```
+.,~`p

```

Attempt This Online!

Outputs the digits of Champernowne's constant. Credit to Nick Kennedy's answer for pointing-out that this has been proven to be a 'normal' number.

---

# Nibbles, 3.5 bytes (7 nibbles)

```
+.,~`p*

```

Attempt This Online!

Outputs the digits of a different super-fair number, proven by Abram Besicovitch to be 'normal'. **5 bytes** if the leading `0.` is required.

# Answer
> 1 votes
# Gaia, 3 bytes

```
ṅ$<

```

Try it online!

Prints the first \\$n\\$ digits of the Copeland–Erdős constant, the concatenation of the primes.

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

```
f=x=>x&&(f(x>>1)+x)%10

```

Try it online!

Looks messy but unproven

---
Tags: code-golf, math, sequence, open-ended-function
---