title: Encrypting Emojis

text:
# Question
Title: Encrypting Emojis
## Problem

You are tasked with creating a program that performs emoji encryption on a given string of emojis. In this encryption scheme, each emoji is replaced by a unique character (from `a` to `z`). Your program should take an emoji string as input and output the corresponding encrypted string.

The mapping of emojis to characters is up to you and can vary each time the program is run. For example:

```
Input:
Output 1: aaabbcdce
Output 2: xxxiikbkg

```

Both outputs are valid.

Your task is to write a program that produces encrypted strings for given emoji inputs. Your program will be evaluated based on its **average result value** and size of code (in bytes).

## Value of the Result

Each letter from `a` to `z` has a value from `0` to `25` in ascending order. ie.

```
a = 0
b = 1
c = 2
  .
  .
  .
y = 24
z = 25

```

The value of the result is calculated as the summation of the values of all characters in the resulting string. For example:

```
aaabbcdce
0 + 0 + 0 + 1 + 1 + 2 + 3 + 2 + 4 = 13

```

## Scoring Criteria:

Run the program 10,000 times, each time generating a random 25-emoji string, and calculate the average value of the results. Your score will be determined by this average value in comparison with the size of the code.

The goal is to create a program that, on average, produces encrypted strings with the lowest possible value based on the emoji-to-character mapping chosen for each run (a `run` is considered converting 25 emojis to a string hence there will be 10,000 unique runs considered in your score)

Create and submit a program that generates encrypted strings as described above, and your score will be the average result value obtained from the 10,000 runs and multiply by the size of the code in bytes. A lower Score is better.

$${\text{average value of results over }10,000\text{ runs}}\times {\text{size of code in bytes}} $$ **LOWER SCORE IS BETTER**

## Notes:

**Ignore decryption**

This problem emphasizes randomness and the ability to produce low-value results on average, so figuring out which emoji has been repeated the most in the input and giving it the character `a` will improve the program's result.

#### Input restrictions

* Input Emoji string will contain **25** emojis without any spaces.
* There will only be **10** unique emojis in the Input at maximum.
* The 10 valid emojis in the Input are

some example inputs:

```
Invalid input: ♿⛷5⃣⏏ (it has more than 10 unique emojis)
                ♿⛷  5⃣⏏ (invalid for including spaces)

Valid input:  ( Valid since it has only 9 unique emojis (<= 10) and no spaces)
Valid output to this Input: abccdaefeagaaaefehcccaief

```

### example random Input generators

#### Python

```
import random

input_string = ''.join(random.choice("") for _ in range(25))

print("Emoji String:", input_string)

```

# Answer
# 05AB1E, score: 516.3704 (73.7672 * 7 bytes)

```
ÙΣ¢}RA‡

```

Try it online or verify the average score of 10,000 random runs.

**Explanation:**

```
Ù        # Uniquify the emoticon-characters of the (implicit) input-string
 Σ       # Sort it from lowest to highest by:
  ¢      #  The count of the character in the (implicit) input-string
   }R    # After the sort-by: reverse it from highest to lowest count
     A   # Push the lowercase alphabet string
      ‡  # Transliterate the descending sorted unique emoticons to lowercase letters in
         # the (implicit) input-string
         # (after which the result is output implicitly)

```
> 4 votes

# Answer
# , ~~73.2 * 81 bytes = *5929.2*~~ ~~73.2 * 70 bytes = *5124.4*~~ 73.2 * 64 bytes = *4684.8*

Same method as below for finding most common letters, but two significant improvements suggested in comments by @pajonk:

1. -11 bytes thanks to a much better approach to splitting and concatenating strings using `utf8ToInt()`.
2. -6 bytes pointing out `chartr()` can take a range of characters (e.g. `"a-d"` rather than `"abcd"`).

```
\(x)chartr(intToUtf8(names(sort(-table(utf8ToInt(x))))),'a-z',x)

```

Attempt This Online!

The ATO link includes a footer with 10k random test cases.

---

Original approach:

# , 73.2 * 81 bytes = 5929.2

```
\(x,p=paste0,`^`=Reduce)chartr(p^names(sort(-table(strsplit(x,"")))),p^letters,x)

```

Attempt This Online!

*-4 bytes thanks to noticing I was being very foolish by using paste0() twice on the same string*

## How?

Fun question. R code golfers will no doubt be aware of the advice:

> If you see a challenge involving string manipulation, just press the back button and read the next question. `strsplit` is single handily responsible for ruining R golf

I boldly ignored this, but it was quickly clear that once you've invested all the bytes in splitting the string into a vector, you need a fairly low-scoring mapping of letters to emojis to come in under 10k. I note some of the answers have slightly lower average value of results than my 73.2 (around the 73.1 range). If anyone has a lot of time and compute power, it would be interesting to see how low you could get it by brute forcing the best random seed.

The actual algorithm is not rocket science: simply assigning the most frequent character `a`, the next most frequent `b` etc. Here is an ungolfed version:

```
f <- function(x, p = paste0, `^` = Reduce) {
    s <- strsplit(x, "")
    m <- sort(-table(s))

    # Ungolfed equivalent to
    # chartr(
    #     Reduce(paste0, names(m)),
    #     Reduce(paste0, letters), x
    # )
    chartr(p^p^names(m), p^p^letters, x)
}

```

The main golfing is using this trick by @J.Doe:

> Operator abuse gives you `p=paste0;"^"=Reduce;p^p^r` which saves two bytes on the usual `paste0` call.

It also uses `chartr()`, basically the equivalent of Python's string `translate()` method, for an (irrelevantly) fast one-to-one replacement of each emoji with the letters of the alphabet. For clarity, the second argument should be `letters[1:10]`, but `chartr()` is fine with the replacement being longer than the pattern to be replaced.

---

Approaches which aim to optimise the number of bytes:

# , 57 bytes * 90.2775 = *5145.8175*

```
\(x)chartr(gsub("(.)(?=.*\\1)","",x,pe=T),"jihgfedcba",x)

```

Attempt This Online!

+7 bytes but still lower scoring than the previous approach below, thanks to the observation in the comment by Dominic Van Essen that, as the regex leads to assigning `"a"` to the emoji whose final appearance occurs first, you're more-likely to assign `"a"` to emojis that only appear once.

So if we reverse the replacement string to `"jihgfedcba"` then we end up with a value of 90.3, much lower than 116.9 in the approach below, which despite the increase in bytes leads to a better overall score. Although still not as low as the first method, and neither scores as well as the excellent answer by Dominic Van Essen.

---

*Previous iteration*

# , ~~116.935 * 57 bytes = *6665.295*~~ 116.935 * 50 bytes = *5846.75*

*Again -7 thanks to @pajonk as `"abcdefghij"` became `"a-j"` in `chartr()`*

```
\(x)chartr(gsub("(.)(?=.*\\1)","",x,pe=T),"a-j",x)

```

Attempt This Online!

## How?

This was an attempt to do it in as few bytes as possible. Rather than splitting the input string into a vector, this just finds the unique characters with regex, and replace them in the order they appear with the letters `"a"` to `"j"`.

Nice to not have to `strsplit()` and `paste()` for once, and be able to do everything in `chartr()`. It's quite a bit shorter. But it's obviously not an optimal approach to the value part of the score, and the overall score is still higher than the original answer.
> 6 votes

# Answer
# Charcoal, score 90.24 * 13 bytes = 1173.12

```
⭆θ§β⌕Φθ⁼μ⌕θλι

```

Try it online! Link is to verbose version of code. Attempt This Online! Link is to test suite for `10000` random iterations. Explanation: Outputs the letter corresponding to the first time this emoji was found in the input. Note that the code is too slow for the test suite so it had to be optimised slightly.

# Charcoal, score 287 * 6 bytes = 1722

```
⭆θ§β℅ι

```

Try it online! Link is to verbose version of code. Attempt This Online! Link is to test suite for `10000` random iterations. Explanation: Outputs the letter corresponding to the emoji's ordinal modulo `26`.

# Charcoal, score 73.275 * 25 bytes = 1831.875

```
Ｗ⁻⪪θ¹υ⊞υ⊟⌈Ｅι⟦№ικκ⟧⭆θ§β⌕υι

```

Try it online! Link is to verbose version of code. Attempt This Online! Link is to test suite for `10000` random iterations. Explanation:

```
Ｗ⁻⪪θ¹υ⊞υ⊟⌈Ｅι⟦№ικκ⟧

```

Sort the characters by frequency in descending order.

```
⭆θ§β⌕υι

```

Map them to lowercase letters.
> 4 votes

# Answer
# , 112.5 * 34 bytes = 3825

```
\(x)letters[utf8ToInt(x)%%430%%11]

```

Attempt This Online!

Output is a vector of characters in the range `"a"` to `"j"`.

Developed independently of, but uses similar approach to Arnauld's Javascript answer.

The aim here is to maximally golf the code-size, while keeping the encrypted letters in the range `a`-`j` (but ignoring their abundances in the input).
We find the modulo values to map the emoji character codes to `1:10` using:

```
x=utf8ToInt("")
for(i in 1:max(x))for(j in 1:99){y=unique(x%%i%%j);if(min(y)==1&&max(y)==10&&length(y)==10)print(c(i,j))}

```

which pretty quickly outputs `430 11` and nothing else.

---

# , 112.5 * 39 bytes = 4387.5

```
\(x)intToUtf8(utf8ToInt(x)%%430%%11+96)

```

Attempt This Online!

As above, but outputs as a single string (same as SamR's R answer).

---

# , 73.2 * 61 bytes = 4465.2

```
\(x)intToUtf8(rank(-table(y<-el(strsplit(x,""))),,"f")[y]+96)

```

Attempt This Online!

Minimizing the output string value at the expense of code-size doesn't seem to pay-off.
> 4 votes

# Answer
# Ruby, 90.0438 * 31 bytes = 2,791.3578

```
->s{s.tr s.chars.uniq*'','a-z'}

```

Attempt This Online!

# Ruby, 73.1206 * 53 bytes = 3,875.3918

```
->s{s.tr s.chars.uniq.sort_by{-s.count(_1)}*'','a-z'}

```

Attempt This Online!
> 3 votes

# Answer
# JavaScript (ES5), score: 112.346 * 62 bytes = 6965.433

```
x=>x.replace(/../g,e=>(e.charCodeAt(1)%576%11+9).toString(36))

```

Attempt This Online! A simple hashing method; optimized for the specific emoji specified in the challenge.

# JavaScript (ES6), score: 73.152 * 109 bytes = 7973.590

```
x=>x.replace(/./gu,e=>"abcdefghij"[[...new Set(x)].sort((a,b,c=e=>x.split(e).length)=>c(b)-c(a)).indexOf(e)])

```

Attempt This Online! A more generic approach, which sorts the input's unique characters (code points) to minimize the value per run.
> 3 votes

# Answer
# Python, score 103.6078\*101 bytes = 10464,3878

assigns the characters in alphabetical order

```
lambda l:''.join(chr(97+[x for(x,_)in groupby(sorted(l))].index(c))for c in l)
from itertools import*

```

Attempt This Online!

---

# Python, score 73.2 * 136 bytes = 9955,2

*-21 bytes, thanks to @Value Ink*

always produces a string with the lowest possible average byte value

```
lambda l:''.join(chr(97+[x for(_,x)in sorted([(-len([*n]),c)for(c,n)in groupby(sorted(l))])].index(c))for c in l)
from itertools import*

```

Attempt This Online!
> 2 votes

# Answer
# sclin, 89.8656 * 30 bytes = 2695.968

```
dup""uniq $abc","zip >M swap :

```

Try it here! Uses a very simple index-based mapping.

For testing purposes:

```
10000=$n.
""=$e.
$W ( ; S>c 97- +/ ) map $n tk +/ $n / n>o
$W ( $e "."/?& :r ) map 25tk dup >o " => ">o ; dup n>o
dup""uniq $abc","zip >M swap :

```

## Explanation

Prettified code:

```
dup () uniq $abc \, zip >M swap :

```
* `dup () uniq` get unique emojis
* `$abc \, zip` pair emoji with alphabet to create translation map
* `swap :` translate emojis to alphabet

---

# sclin, 73.147 * 50 bytes = 3657.35

```
""Q""group"len _"sort $abc"0.: dip ,"zip >M swap :

```

Try it here! Uses frequency-based mapping.

For testing purposes:

```
10000=$n.
""=$e.
$W ( ; S>c 97- +/ ) map $n tk +/ $n / n>o
$W ( $e "."/?& :r ) map 25tk dup >o " => ">o ; dup n>o
""Q""group"len _"sort $abc"0.: dip ,"zip >M swap :

```

## Explanation

Prettified code:

```
dup () group ( len _ ) sort $abc ( 0.: dip , ) zip >M swap :

```
* `() group` group emojis
* `( len _ ) sort` sort descending by frequency
* `$abc ( 0.: dip , ) zip >M` pair emoji with alphabet to create translation map
* `swap :` translate emojis to alphabet
> 2 votes

# Answer
# Python, 107.3917 * 38 bytes = 4080.8846

```
lambda x:[97+ord(c)%3203%13for c in x]

```

Attempt This Online!

Outputs as a list of codepoints. Scoring script taken from bsoelch's answer.

# Python, 101.9159 * 61 bytes = 6216.870

```
lambda x:x.translate(dict(zip(map(ord,set(x)),"abcdefghij")))

```

Attempt This Online!

Outputs as a string.
> 2 votes

# Answer
# JavaScript (ES6), 112.5 * 24 bytes = 2700

Expects and returns a list of code points.

```
a=>a.map(n=>n%430%11+96)

```

Try it online!

This version uses a fixed mapping of the smileys to `abcdefghij`.

The theoretical average score is:

$$\frac{25}{10}\sum\_{n=0}^9 n=112.5$$

---

# JavaScript (Node.js), ~90 * 50 bytes = ~4500

```
s=>s.replace(e=/../g,c=>Buffer([e[c]||=i++]),i=97)

```

Attempt This Online!

This version uses a dynamic mapping of the smileys to `abcdefghij`, according to their order of appearance.
> 1 votes

# Answer
# Excel, 89.9 * 67 bytes = 6022.9

```
=LET(c,MID(A2,ROW(1:25)*2-1,2),CONCAT(CHAR(96+MATCH(c,UNIQUE(c),0))))

```

This does not optimize for the lowest character sum because doing so in Excel takes so many bytes that the overall score ends up higher. The formula is written for the input (the 25 random emojis) to be in the cell `A2`. To simulate 10,000 runs, I wrote a formula to generate those random string, copied it down for 10,000 rows, then copy / pasted values. The encrypted results are on PasteBin and the end result in Excel look like this:

Note: When I copy / pasted down the formula from `B2`, I changed the row reference to be absolute (`$1:$25`) so it would work on all the rows below the original formula.

---

Explanation:

* `LET(c,MID(A2,ROW(1:25)*2-1,2)` defines the variable `c` to be an array with one emoji per row. It's a little tricky to pull out only because Excel sees these emojis as being 2 characters long so need to pull out strings of length 2.
* `CONCAT(CHAR(96+MATCH(c,UNIQUE(c),0)))`
    + `UNIQUE(c)` filters for just the unique emojis
    + `MATCH(c,UNIQUE(c),0)` finds the first instance of each emoji within that unique list
    + `CHAR(96+MATCH(~))` converts that match value into a character in the range `a-j`
    + `CONCAT(CHAR(~))` combines all those characters into one string
> 1 votes

# Answer
# Haskell, score 73.2 * 110 bytes = 8052.0

```
import Data.List
j(Just x)=x
f s=map(toEnum.(97+).j.(`elemIndex`(map head$sortOn((0-).length)$group$sort s)))s

```

---

# Haskell, score 90.1 * 72 bytes = 6487.2

```
import Data.List
j(Just x)=x
f s=map(toEnum.(97+).j.(`elemIndex`nub s))s

```
> 1 votes

---
Tags: string, sequence, code-challenge, encoding, encryption
---


# Question
Title: Compute the chromatic number of special graphs
This challenge is about computing the chromatic number of special types of graphs.

# Input

The input will consist of two integers.

* A positive integer \\$n \> 1\\$.
* A distance \\$d \< n\\$.

# Task

The two inputs values will define a graph with \\$2^n\\$ nodes. Each node corresponds to a different binary array of length \\$n\\$. Two nodes in the graph will be connected if and only if the Hamming distance between the arrays corresponding to the two nodes is exactly \\$d\\$.

# Output

The chromatic number of the corresponding graph.

# Timing

I will try your code with inputs \\$n,d\\$ in increasing order until it takes more than 1 minute to run on my PC. So I will try `2,1`, `3,1`, `3,2`, `4,1`, `4,2`, `4,3`, `5,1`, `5,2`, `5,3`, `5,4` etc. Your score is how far through that infinite list your code manages to get.

# Examples

```
Input 2,1 -> 2
Input 3,1 -> 2
Input 3,2 -> 4
Input 4,1 -> 2
Input 4,2 -> 4
Input 4,3 -> 2
Input 5,1 -> 2
Input 5,2 -> 8
Input 5,3 -> 2
Input 5,4 -> 4
Input 6,1 -> 2
Input 6,2 -> 8
Input 6,3 -> 2
Input 6,4 -> 7
Input 6,5 -> 2
Input 7,1 -> 2
Input 7,2 -> 8
Input 7,3 -> 2
Input 7,4 -> 8
Input 7,5 -> 2
Input 7,6 -> 4
Input 8,1 -> 2
Input 8,2 -> 8
Input 8,3 -> 2
Input 8,4 -> 8
Input 8,5 -> 2
Input 8,6 -> 7
Input 8,7 -> 2
Input 9,1 -> 2
Input 9,2 -> 13
Input 9,3 -> 2
Input 9,4 -> [10,16]
Input 9,5 -> 2
Input 9,6 -> [7,11]
Input 9,7 -> 2
Input 9,8 -> 4

```

# What is a chromatic number?

A coloring of a graph assigns a color to each node so that no two nodes that are connected by an edge have the same color. The chromatic number of a graph is the smallest number of colors needed to color that graph.

# All languages are equal

This challenge like (almost?) all challenges is per language. So if you have fast code in Python, you don't need to worry if someone else is using optimized C. I will keep a table for all languages used.

# The timing machine

I will run your code in Ubuntu on a AMD Ryzen 5 3400G with 16GB of RAM.

# Related:

Find the Chromatic Number is a challenge to compute the chromatic number of a graph.

# Leaderboard:

* **11, 6** using **Wolfram language 13.0** by Aspen.
* **8,5** using **Python 3 + PySAT** by alephalpha.
* **8,5** using **Python 3 + Z3** by Bubbler.
* **8,5** using **Wolfram language 12.0.1** by alephalpha.

# Permanent bounty

I will award 100 points to any answer that can compute 9,2.

# Answer
# Rust, `8,7` in 3 minutes on the Rust playground

```
use std::time::Instant;
use std::{
    collections::HashMap,
    hash::Hash,
    sync::atomic::{AtomicU32, Ordering},
};

use rayon::prelude::*;

const MAX_THREADS: usize = 4;
static NUM_TASKS: AtomicU32 = AtomicU32::new(0);

#[derive(Clone, Copy, Debug)]
struct Edge {
    opposite_edge: u32,
    opposite_color: u32,
    opposite_vertex: u16,
}

#[repr(C)]
#[derive(Clone, Copy)]
struct Color {
    up: u32,
    down: u32,
    vertex: u16,
    last_edge: u32,
}

#[repr(C)]
#[derive(Clone, Copy)]
struct Vertex {
    up: u32,
    down: u32,
    left: u16,
    right: u16,
    count_colors: u16,
    count_edges: u16,
}

#[repr(C)]
#[derive(Clone, Copy)]
struct Root {
    padding_1: u64,
    left: u16,
    right: u16,
    padding_2: u32,
}

impl Root {
    fn new() -> Self {
        Self {
            padding_1: 0,
            left: 0,
            right: 0,
            padding_2: 0,
        }
    }
}

// the reason for repr(C) is so color/vertex up/down are in the same locations

#[repr(C, align(16))]
#[derive(Clone, Copy)]
union Node {
    edge: Edge,
    color: Color,
    vertex: Vertex,
    root: Root,
}

impl Default for Node {
    fn default() -> Self {
        Self { root: Root::new() }
    }
}

#[derive(Clone)]
struct GraphColoring {
    nodes: Vec<Node>,
    allowance: u32,
    // num_checks: u64,
    max_colors: u32,
}

impl GraphColoring {
    fn edge_mut(&mut self, idx: u32) -> &mut Edge {
        unsafe { &mut self.nodes.get_mut(idx as usize).unwrap_unchecked().edge }
    }
    fn color_mut(&mut self, idx: u32) -> &mut Color {
        unsafe { &mut self.nodes.get_mut(idx as usize).unwrap_unchecked().color }
    }
    fn vertex_mut(&mut self, idx: u16) -> &mut Vertex {
        unsafe { &mut self.nodes.get_mut(idx as usize).unwrap_unchecked().vertex }
    }
    fn edge(&self, idx: u32) -> Edge {
        unsafe { self.nodes.get(idx as usize).unwrap_unchecked().edge }
    }
    fn color(&self, idx: u32) -> Color {
        unsafe { self.nodes.get(idx as usize).unwrap_unchecked().color }
    }
    fn vertex(&self, idx: u16) -> Vertex {
        unsafe { self.nodes.get(idx as usize).unwrap_unchecked().vertex }
    }
    fn pick_min_vertex(&self) -> Option<(u16, u16)> {
        let mut idx = self.vertex(0).right;
        if idx == 0 {
            return None;
        }
        let mut fewest_colors = self.max_colors as _;
        let mut most_edges = 0;
        let mut bestidx = idx;
        loop {
            let vertex = self.vertex(idx);
            if vertex.count_colors < fewest_colors
                || (vertex.count_colors == fewest_colors && vertex.count_edges > most_edges)
            {
                if vertex.count_colors == 0 {
                    return Some((0, 0));
                }
                if vertex.count_colors == 1 {
                    return Some((idx, 1));
                }
                fewest_colors = vertex.count_colors;
                most_edges = vertex.count_edges;
                bestidx = idx;
            }
            idx = vertex.right;
            if idx == 0 {
                break;
            }
        }
        Some((bestidx, fewest_colors))
    }
    fn disconnect_color(&mut self, color_idx: u32, color: Color) {
        for idx in color_idx + 1..=color.last_edge {
            let edge = self.edge(idx);

            let opposite_edge_idx = edge.opposite_edge;
            let opposite_color_idx = edge.opposite_color;
            let opposite_color = self.color(opposite_color_idx);

            debug_assert!(opposite_edge_idx <= opposite_color.last_edge);
            debug_assert!(opposite_edge_idx >= opposite_color_idx);

            if opposite_edge_idx < opposite_color.last_edge {
                // swap nodes at opposite_edge_idx and opposite_color.last_edge
                // that means our pointer has to change, as well as last_edges oppoosite_edge has to change
                let last_edge_idx = opposite_color.last_edge;
                let last_edge = self.edge(last_edge_idx);
                let last_edge_opposite_idx = last_edge.opposite_edge;
                self.edge_mut(last_edge_opposite_idx).opposite_edge = opposite_edge_idx;
                *self.edge_mut(opposite_edge_idx) = Edge {
                    opposite_edge: last_edge_opposite_idx,
                    opposite_color: last_edge.opposite_color,
                    opposite_vertex: last_edge.opposite_vertex,
                };
                *self.edge_mut(last_edge_idx) = Edge {
                    opposite_edge: idx,
                    opposite_color: color_idx,
                    opposite_vertex: color.vertex,
                };
                // self.edge_mut(last_edge_idx).opposite_edge = idx;
                // self.edge_mut(last_edge_idx).opposite_color = color_idx;
                self.edge_mut(idx).opposite_edge = last_edge_idx;
            }

            self.color_mut(opposite_color_idx).last_edge -= 1;
            self.vertex_mut(opposite_color.vertex).count_edges -= 1;

            debug_assert_eq!(
                self.edge(idx).opposite_edge,
                self.color(edge.opposite_color).last_edge + 1
            );
        }
    }
    fn reconnect_color(&mut self, color_idx: u32, color: Color) {
        for edge_idx in (color_idx + 1..=color.last_edge).rev() {
            let edge = self.edge(edge_idx);

            debug_assert_eq!(
                edge.opposite_edge,
                self.color(edge.opposite_color).last_edge + 1
            );

            self.color_mut(edge.opposite_color).last_edge += 1;

            let color = self.color(edge.opposite_color);
            self.vertex_mut(color.vertex).count_edges += 1;
        }
    }

    #[inline]
    fn remove_adjacent(&mut self, color_idx: u32, color: Color) {
        for edge_idx in (color_idx + 1..=color.last_edge).rev() {
            let edge = self.edge(edge_idx);

            let color1_idx = edge.opposite_color;
            let color1 = self.color(color1_idx);

            self.disconnect_color(color1_idx, color1);

            self.color_mut(color1.up).down = color1.down;
            self.color_mut(color1.down).up = color1.up;

            let vertex = self.vertex_mut(color1.vertex);

            vertex.count_colors -= 1;
            vertex.count_edges -= (color1.last_edge - color1_idx) as u16;
        }
    }

    fn reconnect_adjacent(&mut self, color_idx: u32, color: Color) {
        for edge_idx in color_idx + 1..=color.last_edge {
            let edge = self.edge(edge_idx);

            let color1_idx = edge.opposite_color;
            let color1 = self.color(color1_idx);

            self.reconnect_color(color1_idx, color1);

            self.color_mut(color1.up).down = color1_idx;
            self.color_mut(color1.down).up = color1_idx;
            let vertex = self.vertex_mut(color1.vertex);
            vertex.count_colors += 1;
            vertex.count_edges += (color1.last_edge - color1_idx) as u16;
        }
    }

    fn check(&mut self) -> bool {
        let (vertex_idx, count) = match self.pick_min_vertex() {
            None => {
                return true;
            }
            Some(x) => x,
        };

        if count == 0 {
            return false;
        }

        // self.num_checks += 1;

        let vertex_idx = vertex_idx as u32;

        let mut idx = self.color(vertex_idx).down;
        while idx != vertex_idx {
            let color = self.color(idx);
            self.disconnect_color(idx, color);
            idx = color.down;
        }

        let mut allowance = count as u32 - self.allowance;

        let vertex = self.vertex(vertex_idx as _);

        self.vertex_mut(vertex.left).right = vertex.right;
        self.vertex_mut(vertex.right).left = vertex.left;

        idx = vertex.down;

        let has_allowance = self.allowance > 0;

        let x = count as u32 - self.allowance.saturating_sub(1);
        let num_tasks = NUM_TASKS.load(Ordering::Relaxed);
        let parallel = num_tasks < MAX_THREADS as u32
            && NUM_TASKS
                .compare_exchange_weak(
                    num_tasks,
                    num_tasks + x - 1,
                    Ordering::SeqCst,
                    Ordering::Relaxed,
                )
                .is_ok();
        if parallel {
            let mut tasks = Vec::new();
            while idx != vertex_idx {
                let color = self.color(idx);

                if has_allowance && allowance == 0 {
                    self.allowance -= 1;
                }

                if (idx + 1..=color.last_edge).all(|edge_idx| {
                    self.vertex(self.edge(edge_idx).opposite_vertex)
                        .count_colors
                        > 1
                }) {
                    self.remove_adjacent(idx, color);
                    tasks.push(self.clone());

                    self.reconnect_adjacent(idx, color);
                }

                if has_allowance && allowance == 0 {
                    self.allowance += 1;
                    break;
                }

                idx = self.color(idx).down;

                allowance -= 1;
            }

            idx = self.color(vertex_idx).up;
            while idx != vertex_idx {
                let color = self.color(idx);
                self.reconnect_color(idx, color);
                idx = color.up;
            }

            self.vertex_mut(vertex.left).right = vertex_idx as _;
            self.vertex_mut(vertex.right).left = vertex_idx as _;
            let o = tasks.par_drain(..).any(|mut i| i.check());
            NUM_TASKS.fetch_sub(x - 1, Ordering::Relaxed);
            o
        } else {
            while idx != vertex_idx {
                let color = self.color(idx);

                if has_allowance && allowance == 0 {
                    self.allowance -= 1;
                }

                if (idx + 1..=color.last_edge).all(|edge_idx| {
                    self.vertex(self.edge(edge_idx).opposite_vertex)
                        .count_colors
                        > 1
                }) {
                    self.remove_adjacent(idx, color);

                    if self.check() {
                        return true;
                    }

                    self.reconnect_adjacent(idx, color);
                }

                if has_allowance && allowance == 0 {
                    self.allowance += 1;
                    break;
                }

                idx = self.color(idx).down;

                allowance -= 1;
            }

            idx = self.color(vertex_idx).up;
            while idx != vertex_idx {
                let color = self.color(idx);
                self.reconnect_color(idx, color);
                idx = color.up;
            }

            self.vertex_mut(vertex.left).right = vertex_idx as _;
            self.vertex_mut(vertex.right).left = vertex_idx as _;
            false
        }
    }

    fn new<T, F>(vertices: &Vec<T>, adjacent: F, max_colors: u32) -> GraphColoring
    where
        F: Fn(T, T) -> bool,
        T: Hash + Eq + Copy,
    {
        let mut this = GraphColoring {
            nodes: vec![Node::default()],
            allowance: max_colors,
            // num_checks: 0,
            max_colors,
        };

        let mut vertex_idxs = HashMap::new();

        // add vertex nodes
        for &v in vertices {
            let vertex_idx = this.nodes.len() as u16;
            let left_idx = vertex_idx - 1;
            let right_idx = 0;
            let vertex = Vertex {
                up: vertex_idx as _,
                down: vertex_idx as _,
                left: left_idx,
                right: right_idx,
                count_colors: 0,
                count_edges: 0,
            };
            vertex_idxs.insert(v, vertex_idx);
            this.nodes.push(Node { vertex });
            this.vertex_mut(left_idx).right = vertex_idx;
            this.vertex_mut(right_idx).left = vertex_idx;
        }

        let mut edge_to_idx = HashMap::new();

        // add colors
        for &a in vertices {
            let vertex_a_idx = vertex_idxs[&a];
            for k in 0..max_colors {
                let color_a_idx = this.nodes.len() as _;
                let up_idx = this.vertex(vertex_a_idx).up;
                let down_idx = vertex_a_idx as _;
                let color_a = Color {
                    up: up_idx,
                    down: down_idx,
                    vertex: vertex_a_idx,
                    last_edge: color_a_idx,
                };
                this.nodes.push(Node { color: color_a });
                this.color_mut(up_idx).down = color_a_idx;
                this.color_mut(down_idx).up = color_a_idx;
                this.vertex_mut(vertex_a_idx).count_colors += 1;
                // and edges
                for &b in vertices {
                    if a == b {
                        continue;
                    }
                    if adjacent(a, b) {
                        let edge_a_idx = this.nodes.len() as _;
                        let edge_a = match edge_to_idx.get(&(b, a, k)) {
                            Some(&(edge_b_idx, color_b_idx, vertex_b_idx)) => {
                                this.edge_mut(edge_b_idx).opposite_color = color_a_idx;
                                this.edge_mut(edge_b_idx).opposite_edge = edge_a_idx;
                                this.edge_mut(edge_b_idx).opposite_vertex = vertex_a_idx;
                                Node {
                                    edge: Edge {
                                        opposite_color: color_b_idx,
                                        opposite_edge: edge_b_idx,
                                        opposite_vertex: vertex_b_idx,
                                    },
                                }
                            }
                            None => {
                                edge_to_idx
                                    .insert((a, b, k), (edge_a_idx, color_a_idx, vertex_a_idx));
                                Node::default()
                            }
                        };
                        this.nodes.push(edge_a);
                        this.color_mut(color_a_idx).last_edge = edge_a_idx;
                        this.vertex_mut(vertex_a_idx).count_edges += 1;
                    }
                }
            }
        }

        this
    }

    fn chromatic_number(n: u32, d: u32, max_colors: u32) -> bool {
        if d % 2 == 1 {
            return max_colors >= 2;
        }
        let mut g = GraphColoring::new(
            &(0_u32..1 << n)
                .filter(|&i| i.count_ones() % 2 == 0)
                .collect(),
            |a, b| (a ^ b).count_ones() == d,
            max_colors,
        );
        let out = g.check();
        // println!("Num checks: {}", g.num_checks);
        out
    }
}

fn chromatic(n: u32, d: u32) -> u32 {
    for k in 2.. {
        if GraphColoring::chromatic_number(n, d, k) {
            return k;
        }
    }
    panic!("You're never gonna reach this");
}

fn main() {
    let start = Instant::now();
    rayon::ThreadPoolBuilder::new()
        .num_threads(MAX_THREADS)
        .build_global()
        .unwrap();
    for n in 2..=8 {
        for d in 1..n {
            println!("{},{} -> {}", n, d, chromatic(n, d));
        }
    }
    println!("Finished in: {:?}", start.elapsed());
}

```

Try it online!

Formulates the decision problem as an exact cover problem and then uses dancing links to solve it.

Specifically, rows correspond to coloring a vertex a color. The columns correspond to the conditions that each vertex is covered by exactly one color, and that each edge has at most one vertex for any given color.

There are two graph coloring specific optimizations:

* Colors are chosen in order. That is, when choosing the color for a vertex, only one of the colors that haven't yet been chosen must be considered. Without this optimization, proving that `f(8,6)` is not `5` takes 415 million steps, with the optimization it takes around 1 million steps (and it's presumably even more effective for proving the chromatic number is not 6, since it's pruning more colors in that case).
* Ties are broken by finding the vertex with the maximum number of unassigned neighbors. This is also a pretty good optimization, without it (but with the previous) 4,225,666,594 steps are required to prove the chromatic number is not 6, with it only 299,285,005 steps are necessary.

If you run it on your own computer, make sure to run `cargo add rayon` and compile with the `RUSTFLAGS=-Ctarget-cpu=native` environment variable.
> 5 votes

# Answer
# Python 3 + Z3, `8,5`

```
import z3

def check(nodes, d, limit):
    solver = z3.SolverFor('QF_FD')
    for node in nodes:
        solver.add(1 <= node, node <= limit)
    l = len(nodes)
    for i in range(l):
        for j in range(l):
            cnt = bin(i ^ j).count('1')
            if d-1 <= cnt <= d:
                solver.add(nodes[i] != nodes[j])
    return solver.check() == z3.sat

def solve(n, d, lower=1):
    if d % 2: return 2
    nodes = [z3.Int(f'a{i}') for i in range(2**(n-1))]
    upper = (lower + 1) * 2
    while lower + 1 < upper:
        mid = lower + 1
        if mid == lower: mid += 1
        result = check(nodes, d, mid)
        print(n, d, mid, result)
        if result: upper = mid
        else: lower = mid
    return upper

def main():
    from time import time
    start = time()
    n = 2
    memo = [[0], [0]]
    while True:
        memo.append([0])
        for d in range(1, n):
            if d + 1 < n: sol = solve(n, d, memo[n-1][d] - 1)
            else: sol = solve(n, d)
            print(n, d, '->', sol, '( elapsed:', time() - start, ')')
            memo[n].append(sol)
        n += 1

main()

```

Output:

```
2 1 -> 2 ( elapsed: 5.245208740234375e-06 )
3 1 -> 2 ( elapsed: 6.246566772460938e-05 )
3 2 2 False
3 2 3 False
3 2 -> 4 ( elapsed: 0.012233257293701172 )
4 1 -> 2 ( elapsed: 0.012252330780029297 )
4 2 4 True
4 2 -> 4 ( elapsed: 0.019064903259277344 )
4 3 -> 2 ( elapsed: 0.01909017562866211 )
5 1 -> 2 ( elapsed: 0.01910543441772461 )
5 2 4 False
5 2 5 False
5 2 6 False
5 2 7 False
5 2 -> 8 ( elapsed: 6.083156585693359 )
5 3 -> 2 ( elapsed: 6.083175420761108 )
5 4 2 False
5 4 3 False
5 4 -> 4 ( elapsed: 6.109014987945557 )
6 1 -> 2 ( elapsed: 6.109039783477783 )
6 2 8 True
6 2 -> 8 ( elapsed: 6.180561542510986 )
6 3 -> 2 ( elapsed: 6.180585145950317 )
6 4 4 False
6 4 5 False
6 4 6 False
6 4 7 True
6 4 -> 7 ( elapsed: 34.04813623428345 )
6 5 -> 2 ( elapsed: 34.048160791397095 )
7 1 -> 2 ( elapsed: 34.04817223548889 )
7 2 8 True
7 2 -> 8 ( elapsed: 34.29183101654053 )
7 3 -> 2 ( elapsed: 34.29185700416565 )
7 4 7 False
7 4 8 True
7 4 -> 8 ( elapsed: 35.03852438926697 )
7 5 -> 2 ( elapsed: 35.0385627746582 )
7 6 2 False
7 6 3 False
7 6 -> 4 ( elapsed: 35.16324186325073 )
8 1 -> 2 ( elapsed: 35.1632719039917 )
8 2 8 True
8 2 -> 8 ( elapsed: 35.805861949920654 )
8 3 -> 2 ( elapsed: 35.80588483810425 )
8 4 8 True
8 4 -> 8 ( elapsed: 37.375497817993164 )
8 5 -> 2 ( elapsed: 37.37552309036255 )
8 6 4 False

```

Looking at the timing, there were a couple of points where Z3 struggled badly:

* ~5 seconds to prove `5,2` is not `7`-colorable
* ~30 seconds to prove `6,4` is not `6`-colorable
* ?? seconds to prove `8,6` is not `5`-colorable
    + Given that the answer is 7, it will require a major breakthrough to beat `8,6` in a minute. I'm pretty confident that naively plugging the graph into any SAT/SMT solver won't cut it.

Initially I tried binary search on the number of colors, but I realized that Z3 takes a pretty long time to provide a `k`-coloring when `k` is larger than optimal, so I replaced it with a sequential search from the lower bound. The lower bound is the same as alephalpha's:

> memoizes the result for `f[n,d]` as a lower bound for `f[n+1,d]`.

An additional contribution of this answer is that, for even `d`, the graph has two connected components that are isomorphic, so we only need to compute the answer on one of them.

Proof:

* If `d` is even, this means `a` and `b` have equal parity (in terms of the number of ones), i.e. there is no path from an even node to an odd node and vice versa. Also, since `d < n`, there is always a way to flip two bits of a node in two steps (e.g. `10111...` and then `01111...`), so the graph has exactly two connected components.
* "Hamming distance of `a` and `b` is `d`" is the same as "`a^b` has `d` ones". Assume `a` and `b` are even. Then the two are connected iff (if and only if) `a^b` has `d` ones. Now consider two odd nodes `a^1` and `b^1`. These two are connected iff `(a^1)^(b^1) == a^b` has `d` ones. The same holds when `a` and `b` are odd, so the two connected components have an isomorphism of `a <=> a^1`.

The single connected component can be constructed with the rule of "there is an edge between `a` and `b` iff `a^b` has `d` or `d-1` ones". Proof:

* Take the connected component of even nodes from the original graph. We can remove the least significant bit from all nodes to get the labels of 0 to `2**(n-1)`. The removed bit is the parity of the rest; I will call it the parity bit.
* Given the two nodes `a` and `b` in the original space, "`a^b` has `d` ones" has two possibilities:
    + `a` and `b` have the same parity bit: `(a/2)^(b/2)` has `d` ones.
    + `a` and `b` have different parity bit: `(a/2)^(b/2)` has `d-1` ones.
* The converse is also true:
    + `(a/2)^(b/2)` must have `d` or `d-1` ones; otherwise `a^b` cannot have `d` ones.
    + if `(a/2)^(b/2)` has `d` ones, `a/2` and `b/2` have the same parity, so `a^b` has `d` ones.
    + if `(a/2)^(b/2)` has `d-1` ones, `a/2` and `b/2` have different parity, so `a^b` has `d` ones.

Also, I have set the upper bound to be `lower_bound * 2` (where the lower bound is `f(n-1,d)`), so in some cases the code skips one calculation when the graph is not `upper_bound - 1`-colorable. Proof:

* The graph for `n,d` equals two disjoint copies of that of `n-1,d` plus extra edges in between. The nodes of `n,d` can be split by their first bit, and observe the follows:
    + `0{a} ^ 0{b}` (where `a` and `b` contains `n-1` bits each) has `d` or `d-1` ones iff `{a} ^ {b}` does. The same holds when 0 is replaced with 1.
    + Therefore, the induced subgraph of `n,d` by selecting all nodes with the first bit of 0 (or 1) is `f(n-1,d)`-colorable.
* Take a coloring of `n-1,d` using `k` colors. There exists an `2k`-coloring of `n,d`: Color the first half using colors `1` to `k`. Color the rest using colors `k+1` to `2k`.
> 4 votes

# Answer
# Wolfram Language (Mathematica), 370 bytes, `8,5` in a minute on TIO

```
f[n_, d_] :=
 f[n, d] =
  Block[{c, k}, k = If[n < d + 1, 1, f[n - 1, d]];
   While[! SatisfiableQ[
      Array[BooleanCountingFunction[{1}, Table[c[#, i], {i, k}],
          "CNF"] &, 2^n, 0, And] &&
       Array[If[
          DigitCount[BitXor[#, #2], 2, 1] ==
           d, ! c[#, #3] || ! c[#2, #3], True] &, {2^n, 2^n, k}, {0,
         0, 1}, And]], k++]; k]

```

Try it online!

Uses Mathematica's built-in SAT solver, and memoizes the result for `f[n,d]` as a lower bound for `f[n+1,d]`.
> 3 votes

# Answer
# Wolfram Language (Mathematica 13.0), 392 bytes, `11,6` in a minute on my laptop

Just implementation.

Use `VertexChromaticNumber` instead of `IGraphM`IGChromaticNumber` to get vertex-chromatic number, \\$ \color{red}{\text{some results are not correct.}} \\$

```
GetChromaticNumber[n_, d_] :=
 Module[{nodes, edges, g}, nodes = Tuples[{0, 1}, n];
  edges =
   Select[Subsets[nodes, {2}], HammingDistance[#[[1]], #[[2]]] == d &];
  g = Graph[UndirectedEdge @@@ edges];
  VertexChromaticNumber[g]]

(*To use the function,enter the two integers as arguments.For \
example:*)
Do[Print[{n, d} -> GetChromaticNumber[n, d]], {n, 2, Infinity}, {d, 1,
   n - 1}]

```

\\$ \begin{array}{c|ccccccccccc} n\backslash d & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 2 & 2 & - & - & - & - & - & - & - & - & - \\ 3 & 2 & 4 & - & - & - & - & - & - & - & - \\ 4 & 2 & 4 & 2 & - & - & - & - & - & - & - \\ 5 & 2 & 8 & 2 & 4 & - & - & - & - & - & - \\ 6 & 2 & 8 & 2 & 7 & 2 & - & - & - & - & - \\ 7 & 2 & 8 & 2 & 8 & 2 & 4 & - & - & - & - \\ 8 & 2 & 8 & 2 & 8 & 2 & 7 & 2 & - & - & - \\ 9 & 2 & 15❌ & 2 & 16 & 2 & 11 & 2 & 4 & - & - \\ 10 & 2 & 17❌ & 2 & 33 & 2 & 20 & 2 & 7 & 2 & - \\ 11 & 2 & 19❌ & 2 & 56 & 2 & 35 & 2 & 12 & 2 & 4 \\ \end{array} \\$

---

`VertexChromaticNumber` function was Introduced in 13 (13.0)

Whereas TIO Mathematica version is 12.0.1

```
Print["Mathematica version: ", $Version];
Print["Operating system: ", $OperatingSystem];

Mathematica version: 12.0.1 for Linux x86 (64-bit) (October 16, 2019)
Operating system: Unix

```
> 1 votes

# Answer
# Python 3 \+ PySAT, `8,5`

```
from pysat.solvers import Cadical153 as Solver
from pysat.card import CardEnc
from pysat.formula import IDPool
import time

chromatic_dict = {}

def colorable(n, d, k):
    s = Solver()
    pool = IDPool(start_from=(k << n) + 1)

    for i in range(1 << n):
        cnf = CardEnc.equals(lits=[(i * k) + l + 1 for l in range(k)], vpool=pool)
        s.append_formula(cnf.clauses)

    for i in range(1 << n):
        for j in range(i + 1, 1 << n):
            if (i ^ j).bit_count() == d:
                for l in range(k):
                    s.add_clause([-(i * k) - l - 1, -(j * k) - l - 1])

    return s.solve()

def chromatic(n, d):
    if (n - 1, d) in chromatic_dict:
        k = chromatic_dict[(n - 1, d)]
    else:
        k = 1
    while not colorable(n, d, k):
        k += 1
    chromatic_dict[(n, d)] = k
    return k

if __name__ == "__main__":
    n = 1
    start_time = time.time()
    while True:
        n += 1
        for d in range(1, n):
            chromatic_number = chromatic(n, d)
            time_elapsed = time.time() - start_time
            print(f"[{time_elapsed}] {n},{d} -> {chromatic_number}")

```

A port of My Mathemactica answer, using PySAT with CaDiCaL SAT solver.
> 1 votes

---
Tags: fastest-code, graph-theory
---


title: Split a string on unnested commas

text:
# Question
Title: Split a string on unnested commas
Create the shortest program/function/whatever that splits an inputted string along un-nested commas. A comma is considered nested if it is either within parentheses, brackets, or braces.

## Input and output

Output should be a list or a string joined with linebreaks. The input may contain any characters. All testcases will have valid/balanced parentheses, brackets, and braces. There will also not be two adjacent commas, nor will there be commas at the start or end. Also, all inputs will be valid, printable ASCII characters from ' ' to '~' (no tabs or linebreaks).

## Test cases:

```
"asd,cds,fcd"->["asd","cds","fcd"]
"(1,2,3)"->["(1,2,3)"]
"(1),{[2,3],4}"->["(1)","{[2,3],4}"]
"(1),[2]{3}"->["(1)","[2]{3}"]
"(1),((2,3),4)"->["(1)","((2,3),4)"]
"(1),(4,(2,3))"->["(1)","(4,(2,3))"]

```

## Example program:

```
function f(code){
  code = code.split(',');
  let newCode = [];
  let last = "";
  for (part of code){
    if (last.split("(").length == last.split(")").length && last.split("[").length == last.split("]").length && last.split("{").length == last.split("}").length){
      last = part;
      newCode.push(part);
    }
    else{
      last += "," + part;
      newCode[newCode.length - 1] = last;
    }
  }
  return newCode;
}
```

```
<input id=in oninput="document.getElementById('out').innerText=f(this.value).join('\n')">
<p id=out></p>
```

# Answer
> 5 votes
# Vyxal, 109 bitsv2, 13.625 bytes

```
¦ƛt:\,=nøβ∧∨;1€ṅ

```

Try it Online!

```
¦ƛt:\,=nøβ∧∨;1€ṅ
¦                 # prefixes
 ƛ                # map:
  t               #   tail
   :              #   duplicate
    \,=           #   is equal to ","?
       n          #   the prefix
        øβ        #   does it have balanced brackets?
          ∧       #   logical and
           ∨      #   logical or
            ;     # end map
             1€   # split on 1
               ṅ  # join inner lists

```

# Answer
> 10 votes
# Excel (ms365), 186 bytes

Formula in `B1`:

```
=TEXTSPLIT(@REDUCE(VSTACK(A1,0),SEQUENCE(LEN(A1)),LAMBDA(a,b,LET(c,MAX(a),d,MID(@a,b,1),IF(d=",",IF(c,a,VSTACK(REPLACE(@a,b,1,"|"),c)),VSTACK(@a,c+IFERROR(FIND(d,")}]|[{(")-4,)))))),"|")

```

The idea I started of with here was that I needed a ticker-system. `REDUCE()` gave me the option to keep this ticker counting and thus decide if a comma was nested within paranthesis or not. A fair chance that this specific idea lead me to use quite a bit of bytes.

I do believe there will be a fair bit of golfing possible here.

# Answer
> 7 votes
# JavaScript (ES6), 79 bytes

*-2 thanks to @tsh*

*70 bytes if we assume there's no linefeed in the input and use it as a separator in the output (also suggested by tsh)*

The code includes the unprintable character `SOH`.

```
s=>s.replace(/(,)|([([{])|[)\]}]/g,(s,c,o)=>(c?d:o?++d:d--)?s:``,d=0).split``

```

Try it online!

## Commented

### Regular expression

```
regex = /(,)|([([{])|[)\]}]/g
//       \_/ \_____/ \__/
//        |     |      |
//        |     |      +---> closing character (not captured)
//        |     +----------> opening character (captured)
//        +----------------> comma (captured)

```

### Function

```
s =>          // s = input string
s.replace(    // replace in s:
  regex,      //   we match either a comma, an opening character,
              //   or a closing character (see above)
  (           //
    s,        //   s = matched character
    c,        //   c = defined if this is a comma
    o         //   o = defined if this is an opening character
  ) =>        //
  ( c ?       //   if this is a comma:
      d       //     leave the nesting depth unchanged
    :         //   else:
      o ?     //     if this is an opening character:
        ++d   //       pre-increment the depth
      :       //     else:
        d--   //       post-decrement the depth
  ) ?         //   if the above test returns a non-zero depth:
    s         //     leave the character unchanged
  :           //   else:
    '\1',     //     replace it with SOH
  d = 0       //   start with d = 0
).split('\1') // end of replace(); split on SOH characters

```

# Answer
> 6 votes
# Retina 0.8.2, 34 bytes

```
!`([({[]()|[]})](?<-2>)|\2,|[^,])+

```

Try it online! Link includes test cases. Explanation:

```
!`

```

Output the matches themselves rather than the count of matches, which is the default for a match stage, a match stage being the default for a single-line program.

```
([({[]()|[]})](?<-2>)|\2,|[^,])+

```

Match as many as possible of...

```
[({[]()

```

... an opening bracket, which increases the nesting level, tracked in `$#2`, ...

```
[]})](?<-2>)

```

... an assumed matching closing bracket, which decreases the nesting level, ...

```
\2,

```

... a comma, but only if we are nested, ...

```
[^,]

```

... or failing that, any non-comma.

The same regex would work in Retina 1 but you would have to use a `L`ist stage instead for the the same length.

# Answer
> 6 votes
# Funciton, 1396 bytes

(The byte count uses UTF-16 and includes the BOM. UTF-8 is bigger, unfortunately.)

**Try it online!**

```
  ┌┐ ╓─╖     ┌──┐
 ┌┘├─╢Ṕ╟─┐ ┌─┤ ┌┴╖
┌┘┌┴╖╙┬╜┌┴╖│┌┴╖│♯║
│┌┤·╟┐└─┤·╟┤│♭║╘╤╝┌┐
││╘╤╝└─┐╘╤╝│╘╤╝┌┴╖└┤╔═╗
││ ├──┐└─┘ └┐└─┤?╟─┼╢4║
││╔╧╗┌┴┐    └┐ ╘╤╝ │╚═╝
││║2║└┬┘    ┌┴╖┌┴╖┌┴╖┌─╖╔═══════╗
││║0║┌┴─────┤·╟┤·╟┤·╟┤ʘ╟╢1063382║
││║9║│ ┌─╖  ╘╤╝╘╤╝╘╤╝╘╤╝║7738808║
││║7║└─┤‼╟┐  │ ┌┘┌┐├──┴┐║3063189║
││║1║  ╘╤╝│  │┌┴╖└┴┼─┐ │║1329769║
││║5║  ┌┴╖│ ┌┴┤?╟──┘╔╧╗│║3925556║
││║1║┌─┤·╟┘┌┴┐╘╤╝   ║0║│║879404 ║
││╚═╝│ ╘╤╝ └┬┘┌┴╖┌┐ ╚═╝│╚═══════╝
││  ┌┘ ┌┴╖  └┬┤·╟┤├────┘
│└┐┌┴╖┌┤«║  ┌┘╘╤╝└┘
│┌┴┤»║│╘╤╝ ┌┴╖┌┴╖
││ ╘╤╝│┌┴╖┌┤?╟┤Ṕ╟┐
││  │ └┤·╟┘╘╤╝╘╤╝│
││  │  ╘╤╝ ┌┴╖┌┴╖│╔═══╗
││  └───┘ ┌┤«╟┤·╟┼╢−21║
││┌───────┘╘═╝╘╤╝│╚═══╝
│└┤           ┌┴╖└┐
│ └───────────┤?╟┬┘
│             ╘╤╝│
└────────────────┘

```

Oh boy, what an ungolfable language. I tried really hard to move things around to eke out a few bytes but this is the most compact arrangement I was able to find.

Funciton has two ways of representing collections: “sequences” and “lists”. I’m taking the challenge statement literally and made a function that returns a *list* of the results.

**Here’s how the function () works:**

* The function takes three parameters:
    + `s`, the input string;
    + `n`, a running count of currently-open parentheses/brackets/braces; and
    + `l`, the list we’re constructing.
* The function must initially be called with `n` = 0 and `l` = 1. The integer 1 here represents a one-element list containing a 0, and 0 in turn represents the empty string.
* If `s` is empty, we just return `l`.
* Otherwise, let `c` be the first character of `s`, and let `i` be the index of `c` within the string `",([{)]}"` (this is the big box on the right). `i` is −1 if the character is not in there.
* Now perform a recursive call with the following parameters:
    + `s` becomes the rest of the string with the first character removed.
    + If `i` \> 0, then: { if `i` \< 4, then we’re looking at an opening parenthesis, so increment `n`; else, we’re looking at a closing parenthesis, so decrement `n`; } else, we’re looking at a comma (`i` = 0) or something else (`i` = −1), so leave `n` unchanged.
    + If `i` bitwise-or `n` is 0, this means that `i` = 0 (we’re seeing a comma) and `n` = 0 (we are not in a parenthesis), so append an empty string to `l`. Otherwise, append `c` to the last string in `l`.

**An interesting golfing trick I used:** See the −21 in the bottom-right? That’s used to do a shift-right by 21 on the input string `s` (this removes its first character). This construct uses the raw syntax () which means it can also compute a “less-than” operation. Since `s` is certainly non-negative, it will never be less than −21, so this will always return 0. I re-use that 0 as the empty string to be appended to the list when a comma is encountered. This allowed me to save an entire `0` literal box, as well as the loop-de-loop I would otherwise need to swallow the less-than result.

To actually run this code, you need a program that calls the function, so here’s one provided for convenience. It’s not golfed and it’s not included in the byte count because the challenge only asked for the function.

```
                ╔═══╗
                ║ 0 ║
                ╚═╤═╝
          ╔═══╗ ┌─┴─╖ ╔═══╗
          ║ 1 ╟─┤ Ṕ ╟─╢   ║
          ╚═══╝ ╘═╤═╝ ╚═══╝
                ┌─┴─╖
                │ ⌡ ║
                ╘═╤═╝
                ┌─┴─╖
                │ ʝ ╟─
                ╘═╤═╝
                ╔═╧══╗
                ║ 10 ║
                ╚════╝

```

This program calls  with stdin, 0, and 1; uses  to convert the list to a sequence; and then uses `ʝ` to join the strings with newlines (ASCII #10).

# Answer
> 5 votes
# Java 11, 157 bytes

```
s->{var t="";for(var p:(s+",x").split(","))if(t.split("[\\[({]",-1).length==t.split("[)}\\]]",-1).length){if(t!="")System.out.println(t);t=p;}else t+=","+p;}

```

Inspired by @Dadsdy's JavaScript answer, so make sure to upvote him/her as well!

Outputs the parts on separated newlines to STDOUT.

Try it online.

**Explanation:**

```
s->{                    // Method with String parameter and no return-type
  var t="";             //  Temp-String, starting empty
  for(var p:(s+",x")    //  ††Concat ",x" to the input
            .split(","))//  Then split it on ",", and loop over the parts:
    if(t.split("[\\[({]",-1).length==t.split("[)}\\]]",-1).length){
                        //   †If String `t` has balanced brackets:
      if(t!="")         //    †††If `t` is NOT empty (so it's not the first iteration):
        System.out.println(t);
                        //     Print the current `t` with newline
      t=p;}             //    Replace the `t` with the current `p` for the next iteration
      else              //   Else:
        t+=","+p;}      //    Append a "," and the current `p` to `t` for the next iteration

```

†: The `-1` in the `String#split` are to include empty Strings, when a part `p` starts with an opening bracket or ends with a closing bracket.
††: We concat an `,` to the input-String before splitting, in order to have an additional iteration of the loop. The additional `x` (could have been any character) is a golfed shortcut for `,-1` in the split of the input.
†††: In Java you'd almost always have to use `String#equals` when comparing Strings. In this case however, where we only want to skip the first iteration when `t` is still empty, we can use `!=""` to check whether not just the value but also the reference is the same. This is possible here, because String literals point to the same reference point in memory, so the `""` in both `t=""` and `!=""` are the same in memory.

# Answer
> 5 votes
# K (ngn/k), 49 bytes

```
{x@.i@=i-!#i:&~(x=44)&~+\+/(6#1 -1)*"()[]{}"=\:x}

```

Try it online!

# Answer
> 4 votes
# 05AB1E, ~~23~~ ~~21~~ 20 bytes

-3 thanks to @Kevin Cruijssen

```
',¡.œ',δý.ΔεžuS¢ιË}P

```

Try it online!

Try all testcases.

## Explanation

```
',        push a comma
¡         and split the implicit input by it
.œ        push all partitions, all possible ways to split it to continuous parts
',δý      and join each partition with commas.
.Δ        now keep (and implicitly output) the first partition such that:
 ε        for each of its parts
  žu       push "()<>[]{}"
  S        list of characters, ["(", ")", "<", ...]
  ¢        count each of the characters in the current part
  ι        uninterleave it, put the count of the even indices (opening brackets) and the odd ones (closing brackets) in two lists
  Ë        and check if the two lists are equal - the number of opening brackets of each type is equal to the number of closing ones.
 }
 P        take the product, which functions as and.

```

# Answer
> 4 votes
# Thunno 2, 29 bytes

```
ðX',/ıxs+',+ẊDøB?ðX:"";;€ḣ€ṫæ

```

Attempt This Online!

### Thunno 2, 18 bytes (non-competing)

```
ƒıtD',=nøB&|;1µ/€J

```

This uses the `µ/` command which I added literally 5 minutes ago, so obviously non-competing.
Port of AndrovT's Vyxal answer.

#### Explanation

```
ðX         # Store " " in x
  ',/     '# Split the input on commas
     ı     # Map over this list:
      xs+  #  Add the current string to x
',+Ẋ      '#  Add a comma and store in x
    D      #  Duplicate the resulting string
     øB?   #  If the brackets are balanced:
        ðX #   Store " " in x
:          #  Else:
 ""        #   Push an empty string
   ;       #  End if
    ;      # End map
     €ḣ    # Remove the first character from each
       €ṫ  # Remove the last character from each
         æ # Remove any empty strings

```

```
ƒ          # Prefixes
 ı         # Map:
  t        #  Tail
   D       #  Duplicate
    ',=   '#  Equals ","?
       n   #  Push character again
øB         #  Has balanced brackets?
  &        #  Logical AND
   |       #  Logical OR
    ;      # End map
     1µ/   # Split on 1s
        €J # Join inner lists

```

# Answer
> 4 votes
# JavaScript (Node.js), 75 ~~86~~ ~~98~~ bytes

> -12 bytes after realizing the string is balanced, so there is always the correct matching ending character for each type of block (and removing some unnecessary parentheses)

> -11 bytes after the added possibility to output the list as a string joined with linebreaks

(Solution without regex)
Nice challenge :)

```
s=>[...s].map(c=>c==","&!(a+=("{[()]}".indexOf(c)+4)%7-3)?`
`:c,a=0).join``

```

Try it online!

---

A little explanation:
We parse each character of the input string.
For each character, the code `("{[()]}".indexOf(c)+4)%7-3` gives
`+1, +2 or +3` respectively for `{ [ (`,
`-3, -2 or -1` respectively for `) ] }`, and `0` if it's another character.
We increment (or decrement) our *"nesting height counter"* using this result.
If the counter is `0` (meaning, when we are currently outside of a block) and the current character is a `,` then we replace it with a `\n`.
A `,` at heights higher than 0 is kept without transformation.
Then at the end, we join everything to get the wanted output.

# Answer
> 4 votes
# Charcoal, 28 bytes

```
≔⁰θＦＳ«≧⁺⁻№([{ι№}])ιθ¿θι≡,ι⸿ι

```

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

```
≔⁰θ

```

Start with zero nesting level.

```
ＦＳ«

```

Loop over the characters.

```
≧⁺⁻№([{ι№}])ιθ

```

Adjust the nesting level depending on whether the characters is an open or close bracket.

```
¿θι≡,ι⸿ι

```

Output the character if it is nested or not equal to a comma, but replace an unnested comma with a newline.

Alternative approach, also 28 bytes:

```
⭆θ⎇›⁼ι,⊙⪪()[]{}²↨Ｅλ№…θκν±¹¶ι

```

Try it online! Link is to verbose version of code. Explanation: Inspired by @AndrovT's Vyxal answer.

```
 θ                              Input string
⭆                               Map over characters
  ⎇                             Ternary
     ι                          Current character
    ⁼                           Equals
      ,                         Literal string `,`
   ›                            Is greater than
         ()[]{}                 Literal string of brackets
        ⪪      ²                Split into pairs of brackets
       ⊙                        Any pair satisfies
                  λ             Current pair of brackets
                 Ｅ              Map over brackets
                   №            Count of
                       ν        Current bracket in
                     θ          Input string
                    …           Truncated to length
                      κ         Outer index
                ↨       ±¹      Has a non-zero difference
                          ¶     If true then newline
                           ι    Else current character
                                Implicitly print

```

# Answer
> 3 votes
# Javascript, ~~140~~ ~~132~~ 114 Bytes

Thanks to @KevinCruijssen for -8 Bytes!

```
c=>(n=[],l="",(c+',').split`,`.map(p=>l=a(/[([{]/)>a(/[)\]}]/)?l+','+p:(l&&n.push(l),p)),n);a=r=>l.split(r).length

```

TIO

# Answer
> 3 votes
# ATOM ~~103~~ 100 bytes, ~~99~~ 96 chars

```
{a=*/",";i=0;*∀{a.i{(*/"("+*/"["+*/"{")!=(*/")"+*/"]"+*/"}")}:a.i+=","+a.(i+1);a-(i+1),i+=1};a}

```

#### Version 2

Saving a few characters by storing i+1 as a separate variable

```
{a=*/",";i=0;*∀{j=i+1;a.i{(*/"("+*/"["+*/"{")!=(*/")"+*/"]"+*/"}")}:a.i+=","+a.j;a-j,i=j};a}

```

## Usage

```
s="(1),{[2,3],4}";

s INTO {a=*/",";i=0;*∀{a.i{(*/"("+*/"["+*/"{")!=(*/")"+*/"]"+*/"}")}:a.i+=","+a.(i+1);a-(i+1),i+=1};a}

```

### Try it online

## Explaination

It begins by splitting the original string by the comma into an array. It creates an iterator, and goes through each element in the created array. If the number of opening and closing symbols do not match, it will merge the current array element with the next one. If they do match, it will continue onwards. By the end of the iteration, all array elements should be correct, and it returns the final result.

### Commented and organized code

```
{
  a=*/","; # Split the input by the comma
  i=0; # Declare an iterator
  * FOREACH { # Repeat the following function based on the length of the string
    a.i INTO {(*/"("+*/"["+*/"{")!=(*/")"+*/"]"+*/"}")}: # Check if the opening and closing characters match in the current item
      a.i+=","+a.(i+1); # If there is not a match, add the next element to the current one
      a-(i+1), # Remove the next element from the array and continue the loop
    i+=1 # Else, increment the counter
  };
  a # Return the final array
}

```

# Answer
> 3 votes
# Scala, ~~140~~ 131 bytes

Golfed version. Try it online!

```
s=>(""/:(s+",x").split(",")){(t,p)=>if(t.split("[\\[({]").length==t.split("[)}\\]]").size){if(t.nonEmpty)println(t);p}else t+","+p}

```

Ungolfed version. Try it online!

```
object Main extends App {
  type N = (String) => Unit

  val n: N = (s: String) => {
    var t = ""
    for (p <- (s + ",x").split(",")) {
      if (t.split("[\\[({]", -1).length == t.split("[)}\\]]", -1).length) {
        if (t.nonEmpty) println(t)
        t = p
      }
      else t += "," + p
    }
  }

  val testCases = Array("asd,cds,fcd", "(1,2,3)", "(1),{[2,3],4}")
  for (testCase <- testCases) {
    println(s"Input: $testCase")
    println("Output: ")
    n(testCase)
    println()
  }
}

```

# Answer
> 3 votes
# Python, 110 bytes

```
f=lambda i,p=1,a=[],c="":i and f(i[1:],p+((q:=i[0])in"([{")-(q in")]}"),a+[c][(x:=q!=p*","):],(c+q)*x)or a+[c]

```

Attempt This Online!

Defines a recursive function `f`. The parameter `p` is the number of open parenthesis plus one, `a` is the accumulator for the output list and `c` is the accumulator for the current string.

If `i` is nonempty we recurse, possibly adding or subtracting one from the parenthesis count `p`. If `p` is equal to 1 and we are on top of a comma we append `c` to `a` and clear the value of `c`. Otherwise we append `q=i[0]` to `c`.

If `i` is empty we just return `a+[c]`

# Answer
> 3 votes
# SNOBOL 4, 126 bytes

I haven't really tried to golf this beyond using single-letter names. Well, I guess there is one little trick. Parsing lists of items separated by commas is usually something like `item arbno(',' item)` (i.e., an item followed by an arbitrary number of repetitions of a comma and another item. Here I've cheated a little bit instead, and added a comma to the beginning of the input, so we can parse the resulting list with code like: `arbno(',' item)`

```
 L = ARBNO(ARBNO(NOTANY('([{}])')) | '(' *L ')' | '[' *L ']' | '{' *L '}')
 I = ',' INPUT
 I ARBNO(',' L . OUTPUT) RPOS(0)
END

```

Each item in the result is printed on a new line.

Then there's the cheating version that semi-sorta works, and reduces the size to 72 bytes:

```
 REPLACE(',' INPUT, "[]{}", "()()" ) ARBNO(',' BAL . OUTPUT) RPOS(0)
END

```

SNOBOL has a built-in function to match strings with balanced parentheses (but not brackets or braces). This replaces brackets/braces with parens, then matches and prints those out (which will otherwise match the correct output). For example, for the test input: `(1),{[2,3],4}`, this prints out:

```
(1)
((2,3),4)

```

General explanation:

Regular expressions are based on SNOBOL patterns.

* `NOTANY('abcd')` is about the same as `[^abcd]` in a regex
* `arbno(foo)` is about like `foo*` in a regex
* RPOS(0) is like `$` at the end of a regex--matches only if the rest of the pattern matches the whole string.

`string1 string2` concatenates the two strings.

`string pattern` attempts to match the pattern against the string. The result will be the matched substring.

Then a rather strange SNOBOL thing. `string pattern . variable` matches `pattern` against `string`, then assigns the resulting substring to `variable`. In our case, we assign to `output`, so this prints out each matching substring.

On, I almost forgot. Formatting. SNOBOL is roughly concurrent with FORTRAN, and uses similar formatting: the only things that can go in column 0 or labels (that can be used as targets of jumps). Lines without labels have to start with a space character.

# Answer
> 3 votes
# Jelly, 22 bytes

```
=“([{“}])”§_/)Ä<=”,$œp

```

Try it online!

Jelly and multiple brackets + non-brackets are not friends

```
             )            For each character in the input:
=                         is it equal to each of
 “([{“}])”                ["([{", "}])"]?
          §               Sum the results from each half,
           _/             and take their difference,
=“([{“}])”§_/)            yielding 1 for opening, -1 for closing, or else 0.
              Ä           Cumulative sum, for depths.
               <          Is each character's depth strictly less than
                =”,$      whether or not it's a comma?
                    œp    Split the input around those positions.

```

# Answer
> 3 votes
# Python, 120 118 112 bytes

```
def q(s):
 d,*L,p=0,''
 for c in s:d+=c in'{[(';d-=c in'}])';p,L=[[p+c,L],['',L+[p]]][1>d!=c==',']
 return L+[p]

```

Attempt This Online!

I realize this loses to the current Python answer by 2 bytes but I liked that it was an uncomplicated implementation of the most intuitive algorithm and wanted to add it.

6 bytes saved thanks to xnor.

Ungolfed it's pretty self-explanatory:

```
def split_string(s: str) -> list[str]:
  depth = 0
  piece = ''
  L = []

  for c in s:
    depth += c in '{[('
    depth -= c in '}])'

    if depth == 0 and c == ',':
      L += [piece]
      piece = ''

    else:
      piece += c

  return L + [piece]

```

Note that the last `+ [piece]` depends on the promise that the string doesn't end on `,`.

Also, I switched to a function because I realized that with `input` and `print` the code doesn't actually output a list, but rather prints something that would be as difficult to work with as the input. :) Otherwise, the solution would be the winning Python one at **105** bytes (ATO):

```
d,*L,p=0,''
for c in input():d+=c in'{[(';d-=c in'}])';p,L=[[p+c,L],['',L+[p]]][1>d!=c==',']
print(L+[p])

```

# Answer
> 3 votes
# APL (Dyalog Unicode), 44 bytes

```
x[⍸1=(x=',')-+\(x∊'({[')-x∊')}]']←⊆'","'⋄,/x

```

Try it on TryAPL.org!

# Answer
> 2 votes
# Arturo, 81 bytes

```
$=>[i:0loop split&'c->'i+dec/??index"([{^_^}])"c<=3prints(∧c=","0=i)?->"\n"->c]

```

Try it!

```
$=>[                       ; a function; assign arg to &
    i:0                    ; assign 0 to i
    loop split&'c->        ; loop over input string; assign current letter to c
        'i+                ; increment i in place by...
        dec                ; ...one less than...
        index"([{^_^}])"c  ; index of c in the string literal
        ?? ... 3           ; if this is null, replace it with 3
        <=3                ; duplicate 3
        / ... 3            ; integer divide by 3
        prints             ; print the following w/o newline
        (∧c=","0=i)?       ; is c a comma and is i 0?
        ->"\n"             ; newline
        ->c                ; otherwise, c
]                          ; end function

```

# Answer
> 2 votes
# Java (JDK), 107 ~~110~~ ~~122~~ bytes

> -12 bytes after the added possibility to output the list as a string joined with linebreaks
> -3 bytes thanks to *ceilingcat*

Port of my JS answer, see explanations here

```
s->{var r="";int a=0;for(var c:s.toCharArray())r+=c==44&(a+=("{[()]}".indexOf(c)+4)%7-3)==0?10:c;return r;}

```

Try it online!

# Answer
> 1 votes
Python:

```
import re

def split_string(s):
    return re.split(r',(?![^(){}[\]]*[)\]}])', s)

```

JavaScript:

```
function splitString(s) {
    return s.split(/,(?![^(){}[\]]*[)\]}])/);
}

```

Ruby:

```
def split_string(s)
  s.split(/,(?![^(){}[\]]*[)\]}])/)
end

```

Java:

```
import java.util.regex.Pattern;

public class SplitString {
    public static String[] splitString(String s) {
        return s.split(",(?![^(){}\\[\\]]*[)\\]}])");
    }
}

```

C++:

#include <iostream>
#include <regex>
#include <vector>

std::vector<std::string> splitString(const std::string& s) {
    std::regex regex(",(?![^(){}\\[\\]]*[)\\]}])");
    std::sregex_token_iterator iterator(s.begin(), s.end(), regex, -1);
    std::sregex_token_iterator end;
    return std::vector<std::string>(iterator, end);
}
```
</code></pre>

# Answer
> 0 votes
# , 44 bytes

```
','&(,<;._1~1,=*0=6+/\@(>-2*3>])'}])([{'i.])

```

Try it online!

# Answer
> 0 votes
# Perl 5 (`-p`), 42 bytes

```
s/([({[]([^({[]|(?1))*[]})])(*SKIP)^|,/ /g

```

or +1 byte to avoid catastrophic backtracking

```
s/([({[]([^({[]|(?1))*?[]})])(*SKIP)^|,/ /g

```

Try it online!

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


title: Give the fool's Fibonacci sequence

text:
# Question
Title: Give the fool's Fibonacci sequence
Recently I asked for tips on improving some code-golf of mine. The code was *supposed* to output every third value of the Fibonacci sequence starting with 2:

```
2,8,34,144,610,2584,10946,46368,196418,832040

```

However, I made a mistake in deriving my formula, and my code output a different sequence which is accurate for the first couple terms and then begins to diverge:

```
2,8,34,140,578,2384,9834,40564,167322,690184

```

My sequence is defined by:

$$ f(0) = 0 \\ $$ $$ f(1) = 2 \\ $$ $$ f(n) =\displaystyle 2 + 3f(n-1) + 4f(n-2) + 2\sum\_{0}^{n-3}f\\ $$

or in terms of my original Haskell code:

```
z=zipWith(+)
g=z((*2)<$>0:0:g)$z(0:g)$(*2)<$>scanl(+)1g

```

Your task is to implement a of integers, which has my incorrect sequence as every third value. The other values can be whatever you want them to be, it simply must have the above sequence as every third value. The required subsequence can begin at the 0th, 1st, or 2nd index, and may begin with either 0 or 2 whichever you please.

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

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

```
{-2/z,x,y}/[;0;2;8] -3!

```

Try it online!

Given `n`, returns the `n`th term (0-indexed) of the given sequence triplicated, i.e. `0, 0, 0, 2, 2, 2, 8, 8, 8, 34, 34, 34, ...`. To start with 2 instead, change `0;2;8` to `2;8;34` or replace the space with `1+` for +1 byte.

The OP's sequence can be simplified as follows:

$$ \begin{aligned} a\_n &= a\_{n-1} + 2a\_{n-2} + 2\sum\_{k=0}^{n-1}a\_k + 2 \\ a\_{n-1} &= a\_{n-2} + 2a\_{n-3} + 2\sum\_{k=0}^{n-2}a\_k + 2 \\ a\_n - a\_{n-1} &= a\_{n-1} + 2a\_{n-2} - a\_{n-2} - 2a\_{n-3} + 2a\_{n-1} \\ a\_n &= 4a\_{n-1} + a\_{n-2} - 2a\_{n-3} \end{aligned} $$

Now we want to find a sequence whose every third term satisfies the above, i.e. the original sequence satisfies

$$ a\_n = 4a\_{n-3} + a\_{n-6} - 2a\_{n-9} $$

but it turns out that this recurrence is irreducible, at least in integers. So the code simply evaluates the "every third term" sequence at index `floor(n/3)`.
> 8 votes

# Answer
# Python, 51 bytes

```
f=lambda n:n>3and 4*f(n-3)+f(n-6)-2*f(n-9)or(n>0)*2

```

Attempt This Online!

Test harness borrowed from @bsoelch.

### How?

Taking the difference f(n)-f(n-3) gets rid of the sum.
> 4 votes

# Answer
# Charcoal, 44 bytes

```
Ｆ²⊞υι≔Ｅ²ιηＦＮ⊞η⁻⌈⊞ＯυΣ…⮌υ²↨¹Ｅ✂⮌η⁵Ｌη³×κ§υ×³λＩ⌈η

```

Try it online! Link is to verbose version of code. Outputs \\$ f(n) \\$ where \\$ f(2)=2 \\$. Explanation:

```
Ｆ²⊞υι

```

Start with the first two terms of the Fibonacci sequence (\\$ 0 \\$-indexed).

```
≔Ｅ²ιη

```

Start with the first two terms of the Wheat Wizard sequence (\\$ 0 \\$-indexed).

```
ＦＮ

```

Calculate \\$ n \\$ new terms.

```
⊞η⁻⌈⊞ＯυΣ…⮌υ²↨¹Ｅ✂⮌η⁵Ｌη³×κ§υ×³λ

```

Calculate \\$ F(n) \\$ and \\$ f(n)=F(n)-\sum\_{i=0}^{\lfloor(n-5)/3\rfloor}F(3i)f(n-5-3i) \\$.

```
Ｉ⌈η

```

Output the \\$ n \\$th additional term. This results in the following sequence:

$$ 1, 2, 3, 5, 8, 13, 21, 34, 53, 87, 140, 219, 359, 578, 903, 1481, 2384, 3725, 6109, 9834, 15365, 25199, 40564, 63379, 103943, 167322, 261431, 428753, 690184, $$

29 bytes for the boring version with all the values triplicated:

```
Ｆ³⊞υ²ＦＮ⊞υΣ×✂⮌υ²χ³⟦⁴¦¹±²⟧Ｉ§υ±³

```

Attempt This Online! Link is to verbose version of code. Outputs the first `n` terms. Explanation:

```
Ｆ³⊞υ²

```

Start with `3` `2`s.

```
ＦＮ

```

Generate `n` more terms.

```
⊞υΣ×✂⮌υ²χ³⟦⁴¦¹±²⟧

```

Calculate the next term using @loopywalt/@Bubbler's formula.

```
Ｉ§υ±³

```

Output the `n`th term.
> 3 votes

# Answer
# sclin, 39 bytes

```
[0 2 8]"dup [2_1 4] * +/ +`1dp"itr flat

```

Try it here! Outputs an infinite list:

$$ 0,2,8,2,8,34,8,34,140,34,140,578,140,578,2384,... $$

For testing purposes:

```
; 100tk >A
[0 2 8]"dup [2_1 4] * +/ +`1dp"itr flat

```

## Explanation

Prettified code:

```
[0 2 8] ( dup [2_ 1 4] * +/ +` 1dp ) itr flat

```

Based on a simplified variant of the original equation (first found by @loopy walt and @Bubbler):

$$ f(n)=4f(n-1)+f(n-2)−2f(n-3) $$

* `[0 2 8] (...) itr` creates an infinite series of modifications starting from 0, 2, 8
    + `dup [2_1 4] *` vectorized-multiply each term by -2, 1, 4
    + `+/` sum
    + `+` 1dp` append as new term, discard oldest term
* `flat` flatten, which conveniently also creates a 2-term gap
> 3 votes

# Answer
# Python, ~~96~~ ~~72~~ 66 bytes

*-6 bytes, thanks to @xnor*

```
f=lambda n:n>0and 2+3*f(n-3)+4*f(n-6)+2*sum(map(f,range(0,n-8,3)))

```

Attempt This Online!
> 2 votes

# Answer
# Pyth, 21 bytes

```
L&b+2su+@G1G3*2_%3yMb

```

Try it online!

Defines a function `y`, which when given `N` returns the Nth term in the sequence $$ 0, 2, 2, 2, 8, 8, 8, 34, 34, 34, 140, 140, 140, 578, 578, 578, 2384, 2384, 2384, \dots $$

### Explanation

```
L                        # define y(b)
 &b                      # short circuiting and, if b==0: return 0
                  yMb    # map range(b) over y
                %3       # take every third element
               _         # reverse the list
             *2          # and double it
      u     3            # reduce range(3) over lambda G,H with the list as the starting value
       +@G1G             #   add the second element of G to the beginning of G
     s                   # sum
   +2                    # add 2

```
> 0 votes

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

```
2λ‚āR*λ·«OÌ}€Ð

```

Outputs the infinite sequence starting with \\$2\\$, where all values occur three times in a row.

Try it online.

**Explanation:**

```
 λ          # Start a recursive environment,
            # to output the infinite sequence
2           # Starting with a(0)=2
            # Where every following a(n) is calculated as:
  ‚         #  Pair the last two implicit values together: [a(n-2),a(n-1)]
            #  (uses a(n-2)=0 in the first iteration: [0,2])
   āR       #  Push pair [2,1]
     *      #  Multiply the values at the same positions: [2*a(n-2),a(n-1)]
      λ     #  Push a list of all terms thus far: [a(0),a(1),...,a(n-1)]
       ·    #  Double each: [2*a(0),2*a(1),...,2*a(n-1)]
        «   #  Append the lists together: [2*a(n-2),a(n-1),2*a(0),2*a(1),...,2*a(n-1)]
         O  #  Take its sum
          Ì #  And increase it by 2
 }          # After the recursive sequence has been generated:
  €Ð        # Triplicate each value in place
            # (after which the infinite list is output implicitly as result)

```
> 0 votes

# Answer
# Haskell, 76 bytes

```
z=zipWith(+)
g=z((*2)<$>0:0:g)$z(0:g)$(*2)<$>scanl(+)1g
f=[x|x<-g,_<-[1..3]]

```

I don't really know Haskell that well, but I do enjoy loopholes. This is a direct ripoff of the code in the question, with each element repeated three times. Direct link for good measure.

Try it online!
> 0 votes

# Answer
# C (gcc), 62 bytes

```
b,c;main(a){for(a++;;)printf("0,0,%u,",a=-2*c+(c=b)+4*(b=a));}

```

Try it online!

New approach to a complete program, using the f(n)=4*f(n-1)+f(n-2)-2*f(n-3) formula used in other solutions.

It starts outputting the sequence at 8, not 0 or 2 as the challenge states.

I feel like this could be improved upon even further.

# C (gcc), ~~74~~ ~~69~~ ~~65~~ 63 bytes

```
a,b,t;main(c){for(;t=b+(c+=b);printf("0,0,%u,",a=3*a+2*t))b=a;}

```

Try it online!

After many reworks, this is what I came up with from following the same algorithm to its conclusion.

This implementation

* ~~Depends on undefined behaviour (sequencing)~~
* Is a complete program, not a fragment.
* And computes the sequence explicitly, outputting zeros on all but every third number.

It may be shorter if we loop once per number output, instead of once every three numbers.
> 0 votes

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


title: Otteretto Classic game scoring method

text:
# Question
Title: Otteretto Classic game scoring method
## Brief description of the game

In the game Otteretto Classic (which you can test directly in your browser; try it!) the player has to form palindromic sequences using adjacent cells on a square grid. Each cell has one of five possible colours, which we will denote by the letters \\$\mathrm A, \ldots, \mathrm E\\$.

The user creates a sequence by sliding the mouse or finger, joining cells one by one, and then releasing the mouse button or lifting the finger to end the sequence. Each time a cell is added, the game updates the score of the sequence that has been built so far. This is actually a partial score, because new cells may be added later. Also, those future cells must make the final sequence palindromic, but that condition cannot be evaluated at this point, so it is ignored when computing the current partial score of the sequence.

Interestingly, the tutorial of the game does not fully specify the scoring method. All it says (slightly rephrased here) is that

* longer sequences are worth more points than shorter ones;
* more complicated sequences are worth more points than simpler ones.

In addition, since future cells are unknown, we may add

* the (partial) score can only depend on the previous and current cells.

The tutorial gives the following examples. For each sequence, all partial scores are indicated:

```
ABA    ->  1 4 9
AABAA  ->  1 2 6 12 15
CABAC  ->  1 4 9 16 25

```

The following images represent the sequence \\$\mathrm A \mathrm B \mathrm A\\$ being built in the actual game (with \\$\mathrm A\\$ corresponding to yellow and \\$\mathrm B\\$ to purple). The score is the number shown in the lower part of each image.

## The scoring method

Based on the above examples and a few others, it appears that the game computes the score according to the rules described next. Note that these rules have only been inferred by me from observing the game, and therefore might not be correct; but in any case they are the applicable rules for the purpose of this challenge.

Let \\$x\\$ be a sequence of length \\$n\\$, formed by \\$x\[1\], \ldots, x\[n\]\\$, where each \\$x\[k\]\\$ takes one of the five possible values \\$\mathrm A, \ldots, \mathrm E\\$. For each \\$k = 1,\ldots,n\\$, let \\$r\[k\]\\$ be the number of times that a cell differs from the preceding one in the (prefix) subsequence \\$x\[1\], \ldots, x\[k\]\\$, considering the first cell as differing from the (non-existing) "preceding" one. For example, given the sequence \\$\mathrm A \mathrm B \mathrm A \mathrm A \mathrm B \mathrm B \mathrm C \mathrm C\\$,

```
x[k] =   A B A A A B B C C
  k  =   1 2 3 4 5 6 7 8 9
r[k] =   1 2 3 3 3 4 4 5 5

```

Equivalently, \\$r\[k\]\\$ can be seen as an integer label for each run of equal values.

With this definition, for any \\$k = 1, \ldots, n\\$ the \\$k\\$-th partial score \\$S\[k\]\\$ is obtained as:

1. \\$S\[1\] = 1\\$.
2. For \\$k \geq 2\\$: \\$S\[k\] = S\[k-1\] + u\[k\]\\$, where:

a. \\$u\[k\]\ = r\[k\]\\$ if the current cell has the *same* value as the preceding one (\\$x\[k\]=x\[k-1\]\\$).

b. \\$u\[k\]\ = r\[k\] + k - 1\\$ if the current cell has a *different* value from the preceding one (\\$x\[k\] \neq x\[k-1\]\\$).

Equivalently, each cell's contribution to the score is the label of the run it belongs to (\\$r\[k\]\\$), plus the \\$0\\$-based cell index (\\$k-1\\$) if the cell starts a new run.

Observe that this computation satisfies the stated features that the score increases if the sequence is "longer" or "more complicated", where "complicated" is defined by comparing each cell with the preceding one.

## The challenge

Given a sequence \\$x\\$ of length \\$n \geq 1\\$, output its \\$n\\$ partial scores \\$S\[1\], \ldots, S\[k\]\\$.

## Additional rules

* The letters \\$\mathrm A, \ldots, \mathrm E\\$ can be replaced by other characters of your choice. The input can be a string, a list or array of characters or numbers, or any similar structure. There have to be \\$5\\$ distinct elements available to represent the original colours of the game.
* As usual, programs or functions are allowed. Input and output means are flexible.
* Code golf. Shortest answer in bytes wins.

## Test cases

```
A             ->  1
ABA           ->  1 4 9
DDDD          ->  1 2 3 4
AABAA         ->  1 2 6 12 15
CABAC         ->  1 4 9 16 25
EBBBE         ->  1 4 6 8 15
DEBBBE        ->  1 4 9 12 15 24
CCAABBA       ->  1 2 6 8 15 18 28
AABCDEEA      ->  1 2 6 12 20 30 35 48
CCAAAAABB     ->  1 2 6 8 10 12 14 24 27
DCCAAAAABB    ->  1 4 6 12 15 18 21 24 36 40
EDEADDCEEBB   ->  1 4 9 16 25 30 42 56 63 80 88
BBCAADDAACBB  ->  1 2 6 12 15 24 28 40 45 60 77 84
BBAACDDCAABB  ->  1 2 6 8 15 24 28 40 54 60 77 84

```

# Answer
# Nekomata, 7 bytes

```
pNᵉ#ĉ#*

```

Attempt This Online!

```
pNᵉ#ĉ#*
pN        For each nonempty prefix:
  ᵉ#        Length
      *     Times
    ĉ#      Number of runs of consecutive equal elements

```
> 3 votes

# Answer
# JavaScript (ES6), 37 bytes

*The method was first found by Luis felipe De jesus Munoz so make sure to upvote this answer as well!*

Expects an array of characters.

```
a=>a.map(v=>(s+=a!==(a=v))*++i,i=s=0)

```

Try it online!

### Commented

```
a =>              // a[] = input array, re-used to store the previous
                  //       character
a.map(v =>        // for each character v in a[]:
  ( s +=          //   increment s if ...
    a !== (a = v) //   ... v is not equal to the previous character
  )               //   we have to use !== to make sure that the test always
                  //   gives true on the first iteration, even for the edge
                  //   case where a[] is a singleton
  * ++i,          //   increment i and multiply s by i
  i = s = 0       //   start with i = 0 and s = 0
)                 // end of map()

```
> 7 votes

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

Expects the input to be an array of characters

---

Basically, `r[k]*k` where `k` is the current length of array and `r[k]` the number of times that a cell differs from the preceding one.

```
(x,t=1)=>x.map((a,i)=>(t+=i&&a!=x[i-1])&&-~i*t)

```

Try it online!
> 5 votes

# Answer
# , ~~31~~ 16 bytes

```
(#*1+1#.2~:/\])\

```

Try it online!

*-15 by porting alephalpha's excellent idea*!!
> 3 votes

# Answer
# Charcoal, 18 bytes

```
ＩＥθ×⊕κ⊕ＬΦ…θκ⁻λ§θ⊕μ

```

Try it online! Link is to verbose version of code. Explanation: Port of my Retina answer.

```
  θ                 Input string
 Ｅ                  Map over characters
     κ              Current index
    ⊕               Incremented
   ×                Multiplied by
          θ         Input string
         …          Truncated to
           κ        Current index
        Φ           Filtered where
             λ      Current character
            ⁻       Does not equal
               θ    Input string
              §     Indexed by
                 μ  Inner index
                ⊕   Incremented
       Ｌ            Take the length
      ⊕             Incremented
Ｉ                   Cast to string
                    Implicitly print

```
> 2 votes

# Answer
# 05AB1E, 7 bytes

```
ηεÔgyg*

```

Port of *@alephalpha*'s Nekomata's answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

`Ô` could alternatively be `γ` and `yg` could alternatively be `N>` or  for the same byte-counts.

**Explanation:**

```
η        # Get the prefixes of the (implicit) input-string
 ε       # Map each prefix to:
  Ô      #  Connected uniquify the characters in the string
   g     #  Pop and push the length of this string
    yg   #  Also push the length of the prefix itself
      *  #  Multiply the two together
         # (after which this list of integers is output implicitly as result)

  γ      #  Split the string into equal adjacent groups of characters

    N>   #  Push the 0-based map-index, and increase it by 1

    }    # Close the map
     ā   # Push a list in the range [1,length] (without popping the list itself)

```
> 2 votes

# Answer
# Ruby, 43 bytes

```
->l{a=b=0;l.map{|x|(b+=(l!=l=x)?1:0)*a+=1}}

```

Try it online!
> 2 votes

# Answer
# Retina, 30 bytes

```
.(?<=(\2*(.))+)
$.($#1*$>:&*)

```

Try it online! Link includes test cases. Explanation: Uses ~~@Arnauld's~~ @LuisfelipeDejesusMunoz's observation that the partial score is the product of the letter's index and the number of runs so far.

```
.(?<=(\2*(.))+)

```

For each letter, count the number of runs so far.

```
$.($#1*$>:&*)

```

Replace it with the product of that with the letter's 1-based index.
> 1 votes

# Answer
# Jelly, 10 bytes

```
Ż⁻ƝµJ’×+ÄÄ

```

A monadic Link that accepts a list of characters\*, and yields a list of the partial scores.

* or, indeed, non-zero numbers, or even lists.

**Try it online!** Or see the test-suite.

### How?

```
Ż⁻ƝµJ’×+ÄÄ - Link: list of characters L  e.g. A  A  A  B  B  C  A  A
Ż          - prefix a zero                 0  A  A  A  B  B  C  A  A
  Ɲ        - for neighbouring pairs:
 ⁻         -   not equal?                     1  0  0  1  0  1  1  0
   µ       - start a new monadic chain - f(S=that)
    J      -   range of length                1  2  3  4  5  6  7  8
     ’     -   decrement                      0  1  2  3  4  5  6  7
      ×    -   multiply by {S}                0  0  0  3  0  5  6  0
        Ä  -   cumulative sums {S}            1  1  1  2  2  3  4  4
       +   -   add                            1  1  1  5  2  8 10  4
         Ä -   cumulative sums                1  2  3  8 10 18 28 32

```
> 1 votes

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

```
lambda x,t=[7]:(lambda m:[*map(lambda i,a:(lambda m:t)(t.__setitem__(0,t[0]+(i and a!=(x[i-1]if i else 0))))and-~i*t[0],*zip(*enumerate(x)))])(t.__setitem__(0,1))

```

"Port" of `Luis felipe De jesus Munoz`'s answer. Try its test cases. `t=[7]` can be replaced with any other one-digit number for no extra cost. Explanation / readable version in TIO header and my painful debugging helper below

```
_queue = [];function print(...args) {_queue.push([args[0], args.slice(1)])}function release(l) {args_ = [];isStart = true;for (let i of _queue) {args_.push((isStart?l:'')+(i[0][0]=='.'?i[0].slice(1):'\n'+i[0]));for (let j of i[1]) {args_.push(j)}isStart=false}console.log(...args_)}

f=(x,t=1)=>x.map((a,i)=>{
        print('inner',t,a,i)
        p = [ t+=(i&&a!=x[i-1]) , -~i*t ]
        ret = p[0] && p[1];
        print('.returning',t,a,i,p[0],p[1],ret)
return ret});(l=>{f(Array.from(l));release(l)})('DDDD')

```

## Python 3.8 (pre-release), 131 bytes, non-reusable

```
lambda x,t=[1]:[*map(lambda i,a:(lambda m:t)(t.__setitem__(0,t[0]+(i and a!=(x[i-1]if i else 0))))and-~i*t[0],*zip(*enumerate(x)))]

```

Omits `t.__setitem__(0,1)`. Test cases
> 1 votes

# Answer
# Python, 61 bytes

```
lambda l:len(list(__import__('itertools').groupby(l)))*len(l)

```

The standard library `itertools.groupby`, with one argument, produces a lazy iterator over consecutive runs in the input (which are encoded as a pair of the value and another lazy iterator over the run - it's much more useful with the second argument in general, but...). Converting to list explicitly is required to measure the length (i.e. how many such runs there are).
> 1 votes

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