title: Gerrymander North Carolina

text:
# Question
Title: Gerrymander North Carolina
# The challenge

How well can you gerrymander North Carolina into 13 voting districts?

In this challenge, you use the following files to draw different maps for Republicans and Democrats.

**File 1:** NC\_2016\_presidential\_election.csv

**File 2:** NC\_county\_adjacency.csv

File 1 gives county-level voting data from the 2016 presidential election (based on this and that), while File 2 gives adjacency information between counties (based on this). For File 2, the first entry of each row is adjacent to the other entries in that row. For example, Alexander is adjacent to Alexander, Caldwell, Catawba, Iredell and Wilkes. (Note that every county is adjacent to itself.)

# Admissibility

Your code should be written in a way that can gerrymander arbitrary maps. In particular, your code must take each of the following as inputs:

* A set \\$C\\$ of counties and a set \\$P\\$ of parties.
* Weights \\$(v\_{cp})\\$ that count voters in county \\$c\in C\\$ who vote for party \\$p\in P\\$. (E.g., File 1.)
* A connected graph \\$G\\$ with vertex set \\$C\\$. (E.g., File 2.)
* A number of districts \\$k\\$.
* A party \\$p^\star\in P\\$ to gerrymander in favor of.

The output must be an assignment of counties to districts such that the counties in each district induce a connected subgraph of \\$G\\$. For example, for the counties in Files 1 and 2 (listed in alphabetical order), the following is one of 13! sequences that specify the partition of counties into districts pictured below:

```
3,5,5,10,5,5,13,11,10,8,9,12,1,12,13,13,3,9,3,12,13,12,9,8,13,10,13,13,4,4,8,11,11,5,7,9,11,12,11,13,4,11,7,12,12,11,1,13,4,12,7,13,3,13,9,12,12,11,12,2,12,1,1,7,8,11,13,3,13,13,8,13,3,11,9,3,10,10,3,1,9,8,10,1,5,5,12,12,13,10,11,6,11,11,5,8,5,7,5,12

```

(This map is loosely based on the current map of U.S. congressional districts in North Carolina.)

# Scoring

Your score is determined by how your code performs for various problem instances.

Given a district assignment, let \\$d\\$ denote the number of districts for which party \\$p^\star\\$ receives the plurality of votes cast, and let \\$a\\$ and \\$b\\$ denote the minimum and maximum number of voters in a district, respectively. Then the score for the district assignment is given by

$$ \text{assignment score} = d - \frac{b}{a}. $$

For example, if \\$p^\star\\$ is the Republican party, then the district assignment described above has \\$d=10\\$, \\$a=247739\\$, and \\$b=527337\\$, leading to a score of about \\$7.87\\$.

To compute your score, gerrymander North Carolina (as specified in Files 1 and 2) into \\$k=13\\$ districts in favor of the Republican party, and then in favor of the Democratic party. Let \\$S\_1\\$ denote the sum of these two assignment scores. Next, gerrymander 10 different modifications of North Carolina, each obtained by removing one of the following counties from Files 1 and 2:

```
Cleveland,Davidson,Hyde,Johnston,Madison,Montgomery,Pender,Scotland,Warren,Wilkes

```

(Since North Carolina is biconnected, each of these are acceptable problem instances.) For each modification, gerrymander into \\$k=13\\$ districts in favor of the Republican party, and then in favor of the Democratic party. Let \\$S\_2\\$ denote the sum of these 20 assignment scores. Then the score of your submission is given by

$$ \text{submission score} = S\_1+\frac{S\_2}{10}. $$

In addition to your code, you are encouraged to provide an illustration of your two maps that gerrymander all of North Carolina for Republicans and for Democrats. (DRA2020 might be a helpful resource.)

# Answer
# C++, score = 33.526203, all test cases in 2min34s

<sup>(of course, the score can be improved by running the program for more time; please do not do that to claim a victory or something)</sup>

That score is usually 11 won districts for the Republicans and from 9 to 11 for the Democrats.

In this revision, the score decreased significantly, because I found some *really* large bugs in the input parsing. My program also verifies its solution now.

```
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <streambuf>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <bitset>
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <map>
#include <deque>
#include <string>

constexpr uint64_t rotl(uint64_t x, char k)
{
    return (x<<k) | (x>>(64-k)); //typo of the day: replace the >> with <<
}
uint64_t xs128()
{
    static uint64_t s_0 = 0, s_1 = 1;
    const uint64_t s0 = s_0;
    uint64_t s1 = s_1;
    uint64_t res = s0 + s1;
    s1 ^= s0;
    s_0 = rotl(s0, 24) ^ s1 ^ (s1 << 16);
    s_1 = rotl(s1, 37);
    return res >> 4;
}
std::vector<std::string> getCsvLine(std::istream& str)
{
    https://stackoverflow.com/a/1120224 - saved some time writing a parser...
    std::vector<std::string> result;
    std::string line; std::getline(str,line);
    std::stringstream lineStream(line);
    std::string cell;
    while(std::getline(lineStream,cell, ','))
        result.push_back(cell);
    return result;
}
struct county
{
    int good = 0;
    int sum = 0;
    std::vector<int> others;
    std::string name;
};
struct district
{
    int good = 0;
    int sum = 0;
    std::vector<int> others;
    void operator += (county& rhs)
    {
        good += rhs.good; sum += rhs.sum;
        for(int i = 0; i < others.size(); i++)
            others[i] += rhs.others[i];
    }
    void operator -= (county& rhs)
    {
        good -= rhs.good; sum -= rhs.sum;
        for(int i = 0; i < others.size(); i++)
            others[i] -= rhs.others[i];
    }
};
//seems like exactly 100 districts exist, below CHAR_MAX
std::vector<std::vector<char>> graph;
std::vector<char> curdistrict;
std::vector<county> counties;
std::vector<district> districts;
std::vector<char> marks;
bool pluralityCheck(const district& d)
{
    return d.good > *std::max_element(d.others.begin(), d.others.end());
}
int n, k, excluded;
double getFitness(std::vector<char>& dmap)
{
    std::vector<district> districts(k);
    for(district& d : districts)
        d.others.resize(counties[excluded==0?1:0].others.size());
    for(int i = 0; i < n; i++)
        if(i != excluded) districts[dmap[i]] += counties[i];
    double score = 0;
    int min = INT_MAX, max = INT_MIN;
    for(int i = 0; i < k; i++)
        score += pluralityCheck(districts[i]),
        min = std::min(min, districts[i].sum), max = std::max(max, districts[i].sum);
    score -= double(max) / min;
    return score;
}
void dfs(char v, char color)
{
    marks[v] = color;
    for(int to : graph[v])
        if(marks[to] != color && curdistrict[to] == curdistrict[v])
            dfs(to, color);
}
bool dfsFor(char at, char target, char color)
{
    marks[at] = color;
    if(at == target) return true;
    if(at == excluded) return false;
    bool ans = false;
    for(int to : graph[at])
        if(marks[to] != color && curdistrict[to] == curdistrict[at])
            ans |= dfsFor(to, target, color);
    return ans;
}
bool isCutpoint(int v)
{
    static int call = 0;
    char color = call + 1;
    call = (call + 1) % 255;
    if(color == 1) for(char& el : marks) el = 0; //reset every 256 calls
    marks[v] = color;
    int calls = 0;
    for(char to : graph[v])
    {
        if(curdistrict[to] != curdistrict[v]) continue;
        if(marks[to] == color) continue;
        calls++;
        if(calls == 2) break;
        dfs(to, color);
    }
    return calls != 1; //0 -> kills a district, >=2 -> a cutpoint -> splits a district
}
std::map<std::string, int> dnamemap;
double solve(int n, int k, int target, int excluded)
{
    ::n = n; ::k = k; ::excluded = excluded;
    marks = std::vector<char>(n);
    curdistrict = std::vector<char>(n, -1); graph = std::vector<std::vector<char>>(n);
    districts = std::vector<district>(k); counties = std::vector<county>(n);
    dnamemap = std::map<std::string, int>();
    std::ifstream data("NC_2016_presidential_election.csv");
    getCsvLine(data); //skip header
    for(int i = 0; i < n; i++)
    {
        std::vector<std::string> row = getCsvLine(data);
        dnamemap[row[0]] = i;
        counties[i].name = row[0];
        if(i == excluded) continue;
        for(int j = 1; j < row.size(); j++)
        {
            int v = std::stoi(row[j]);
            if(j - 1 == target)
                counties[i].good = v;
            else counties[i].others.push_back(v);
            counties[i].sum += v;
        }

    }
    data = std::ifstream("NC_county2.csv"); //no header
    //NC_county2.csv is obtained by cat NC_county_adjacency.csv | sort | tr -d '\r'
    //the default counties file caused not one but TWO horrible parsing bugs
    //they silently increased the score.
    //There were \r\n line endings instead of \n, and my program mishandled them.
    //and *the worst*. It seems to be in alphabetic order, but it actually simply isn't.
    for(int i = 0; i < n; i++)
    {
        std::vector<std::string> row = getCsvLine(data);
        if(i == excluded) continue;
        for(int j = 1; j < row.size(); j++)
        {
            if(row[j] == row[0]) continue;
            int to = dnamemap[row[j]];
            if(to == excluded) continue;
            graph[i].push_back(to);
        }
    }
    for(district& d : districts)
        d.others.resize(counties[excluded==0?1:0].others.size());
    int di = 0;
    for(int i = 0; di < k; i++) if(i != excluded) curdistrict[i] = di++;
    for(int it = n; it --> 0;)
        for(int i = 0; i < n; i++)
        {
            if(i == excluded || curdistrict[i] != -1) continue;
            for(int to : graph[i])
            {
                if(to == excluded || curdistrict[to] == -1) continue;
                curdistrict[i] = curdistrict[to];
                break;
            }
        }
    if(excluded >= 0) curdistrict[excluded] = -1;
    for(int i = 0; i < n; i++) printf("%d ", curdistrict[i]);
    printf("%d\n", excluded);
    for(int i = 0; i < n; i++) if(excluded != i) districts[curdistrict[i]] += counties[i];
    double temp = 3;
    int its = 2e7;
    std::vector<char> bestplacement = curdistrict;
    std::vector<district> bestdistricts = districts;
    int lastimprovement = 0;
    double bestscore = getFitness(curdistrict);
    int perblock = 2e4; //max number of iterations without improvement
    double delta = 1.01 * temp / its;
    double curscore = bestscore;
    double withoutimprovement = 0;
    for(int it = 0; it < its; it++)
    {
        temp -= delta;
        if(it % 1048576 == 0)
            printf("it=%d, cs=%lf       \r", it, curscore);
        int i = xs128() % n;
        while(i == excluded) i = xs128() % n;
        if(isCutpoint(i)) continue; //<- around 50% of program time
        std::vector<int> nearby;
        bool ok = false;
        for(int to : graph[i])
            if(curdistrict[to] != curdistrict[i] && curdistrict[to] != -1) ok = true;
        if(!ok) continue;
        int nd = -1;
        while(nd == curdistrict[i] || nd == -1)
            nd = curdistrict[graph[i][xs128() % graph[i].size()]];
        //calculate new min size, new max size etc.
        //can be done via std::set and other tree-based stuff, but it's much simpler to use a normal arrays (for k=13)
        //*might* use a segment tree to optimize later, but it's not spending a lot of time here
        char oldmaj1 = pluralityCheck(districts[curdistrict[i]]);
        char newmaj1 = pluralityCheck(districts[nd]);
        int maxs = INT_MIN, mins = INT_MAX;
        for(int i = 0; i < k; i++)
            maxs = std::max(maxs, districts[i].sum), mins = std::min(mins, districts[i].sum);
        double pen1 = double(maxs) / mins;
        districts[curdistrict[i]] -= counties[i];
        districts[nd] += counties[i];
        char oldmaj2 = pluralityCheck(districts[curdistrict[i]]);
        char newmaj2 = pluralityCheck(districts[nd]);
        maxs = INT_MIN, mins = INT_MAX;
        for(int i = 0; i < k; i++)
            maxs = std::max(maxs, districts[i].sum), mins = std::min(mins, districts[i].sum);
        double pen2 = double(maxs) / mins;
        double delta = pen1 - pen2 + (oldmaj2 + newmaj2 - oldmaj1 - newmaj1);
        if(delta <= 0 && (temp <= 0 || ldexpf(std::exp(delta / temp), 60) < xs128()))
        {
            districts[nd] -= counties[i], districts[curdistrict[i]] += counties[i];
        }
        else
        {
            curdistrict[i] = nd;
            curscore += delta;
            if(curscore > bestscore)
            {
                bestscore = curscore; lastimprovement = it;
                bestplacement = curdistrict; withoutimprovement = 0;
                bestdistricts = districts;
            }
        }
        if(curscore < bestscore) withoutimprovement += bestscore - curscore;
        if(it - lastimprovement > perblock || withoutimprovement > 3e4)
        {
            //restart at best score so far
            withoutimprovement = 0;
            lastimprovement = it;
            curdistrict = bestplacement;
            districts = bestdistricts;
            curscore = bestscore;
        }
    }
    for(int i = 0; i < n; i++)
        printf("%d ", curdistrict[i]);
    printf("\n");
    for(district& d : districts)
    {
        printf("%d total, maj=%d, %d good; rest:", d.sum, (int)pluralityCheck(d), d.good);
        for(int el : d.others) printf(" %d", el);
        printf("\n");
    }
    for(int i = 0; i < n; i++) //verify validness
    for(int j = i+1; j < n; j++)
    {
        if(i == excluded || j == excluded) continue;
        if(curdistrict[i] != curdistrict[j]) continue;
        for(char& el : marks) el = 0;
        bool good = dfsFor(i, j, 1);
        if(!good) printf("invalid: i=%d, j=%d, d=%d!\n", i, j, curdistrict[i]);
    }
    double score = getFitness(curdistrict);
    printf("%lf\n", score);
    return score;
}
int main()//int64_t argc, char*argv[])
{
    //randomly choose and recolor vertices
    //do not recolor a vertex if it is a cutpoint (more known as an articulation point or cut vertex) or alone
    //to check, DFS over same-colored vertices from it. If != 1 calls were done, it's alone or a cutpoint
    //initial state: all counties belong to district 0, but first 13 belong to district i (dumb but why bother)
    //for each district maintain the voters for both parties and total number
    //oh, and don't merely randomly recolor: use Simulated Annealing (TM) (it actually improves a lot!)
    setbuf(stdout, 0);
    int k = 13, n = 100;
    std::vector<int> toExclude { -1, 22, 28, 47, 50, 57, 61, 70, 82, 92, 97 }; //the final score computing
    //std::vector<int> toExclude { -1 };
    double score = 0;
    for(int el : toExclude)
    {
        double s = 0;
        s += solve(n, k, 0, el);
        s += solve(n, k, 1, el);
        if(el == -1) score += s;
        else score += s / 10;
    }
    printf("%lf\n", score);
}

```

Uses (attempts to use) simulated annealing to improve from a dumb assignment by making random changes if they do not ruin things (that is, destroy or split districts). Restarts from the best known assignment when either 20000 iterations passed without an improvement or the accumulated difference between the best score and the current score since the last improvement exceeds 30000. Can be compiled with `clang++ hax.cpp -Ofast -march=native -flto -no-pie -o a.out`. Assumes files `NC_2016_presidential_election.csv` and `NC_county2.csv` are in the current directory, where `NC_county2.csv` is the `NC_county_adjacency.csv`, but with its lines *actually* sorted in alphabetical order, and with Unix (`\n`) line endings.

Quoting from the question, "you are encouraged to provide an illustration". I am definitely encouraged (I would really like to know whether or not the code has no bugs), but I have no idea how to create an illustration. I also have no idea how to export the output into a format readable by the linked website.

Assignment information on the normal map for the Democrats, then for the Republicans:

```
begin assignment for target=0, excluded=-1
Alamance,4
Alexander,8
Alleghany,8
Anson,12
Ashe,8
Avery,5
Beaufort,6
Bertie,6
Bladen,9
Brunswick,9
Buncombe,5
Burke,10
Cabarrus,8
Caldwell,8
Camden,7
Carteret,9
Caswell,0
Catawba,10
Chatham,12
Cherokee,10
Chowan,7
Clay,10
Cleveland,10
Columbus,2
Craven,9
Cumberland,2
Currituck,7
Dare,7
Davidson,12
Davie,8
Duplin,6
Durham,12
Edgecombe,6
Forsyth,3
Franklin,7
Gaston,10
Gates,7
Graham,10
Granville,0
Greene,6
Guilford,4
Halifax,7
Harnett,12
Haywood,10
Henderson,10
Hertford,7
Hoke,2
Hyde,7
Iredell,8
Jackson,10
Johnston,12
Jones,6
Lee,12
Lenoir,6
Lincoln,11
Macon,10
Madison,10
Martin,6
McDowell,5
Mecklenburg,11
Mitchell,5
Montgomery,12
Moore,12
Nash,7
New Hanover,9
Northampton,7
Onslow,9
Orange,0
Pamlico,9
Pasquotank,7
Pender,9
Perquimans,7
Person,0
Pitt,6
Polk,10
Randolph,4
Richmond,12
Robeson,2
Rockingham,0
Rowan,8
Rutherford,10
Sampson,9
Scotland,2
Stanly,8
Stokes,0
Surry,3
Swain,10
Transylvania,10
Tyrrell,7
Union,8
Vance,7
Wake,1
Warren,7
Washington,6
Watauga,5
Wayne,9
Wilkes,8
Wilson,6
Yadkin,8
Yancey,10
end assignment for target=0, excluded=-1
begin assignment for target=1, excluded=-1
Alamance,0
Alexander,1
Alleghany,11
Anson,7
Ashe,11
Avery,10
Beaufort,6
Bertie,6
Bladen,8
Brunswick,12
Buncombe,10
Burke,10
Cabarrus,7
Caldwell,11
Camden,9
Carteret,6
Caswell,0
Catawba,1
Chatham,2
Cherokee,4
Chowan,9
Clay,4
Cleveland,4
Columbus,12
Craven,9
Cumberland,8
Currituck,6
Dare,6
Davidson,0
Davie,7
Duplin,9
Durham,0
Edgecombe,9
Forsyth,1
Franklin,6
Gaston,4
Gates,9
Graham,10
Granville,6
Greene,6
Guilford,11
Halifax,6
Harnett,8
Haywood,10
Henderson,4
Hertford,9
Hoke,2
Hyde,6
Iredell,7
Jackson,4
Johnston,8
Jones,9
Lee,2
Lenoir,9
Lincoln,10
Macon,4
Madison,10
Martin,9
McDowell,10
Mecklenburg,5
Mitchell,10
Montgomery,2
Moore,2
Nash,9
New Hanover,12
Northampton,9
Onslow,12
Orange,2
Pamlico,9
Pasquotank,6
Pender,12
Perquimans,6
Person,0
Pitt,6
Polk,4
Randolph,0
Richmond,7
Robeson,8
Rockingham,0
Rowan,2
Rutherford,4
Sampson,12
Scotland,2
Stanly,2
Stokes,11
Surry,11
Swain,10
Transylvania,4
Tyrrell,6
Union,7
Vance,6
Wake,3
Warren,9
Washington,6
Watauga,11
Wayne,9
Wilkes,1
Wilson,9
Yadkin,1
Yancey,10
end assignment for target=1, excluded=-1
```
> 10 votes

---
Tags: code-challenge, graph-theory, optimization, algorithm
---


# Question
Title: Spanning paths in a tournament on n nodes
The goal of this challenge is to extend the On-Line Encyclopedia of Integer Sequences (OEIS) sequence A038375.

> Maximal number of spanning paths in tournament on n nodes.

A tournament on \\$n\\$ vertices is a directed graph where for each pair of vertices \\$(v\_i, v\_j)\\$ there is either a directed edge \\$v\_i \rightarrow v\_j\\$ or a directed edge \\$v\_j \rightarrow v\_i\\$.

A spanning path or Hamiltonian path is an ordering of all of the vertices of a graph, \\$(v\_1, v\_2, ..., v\_n)\\$ such that there is an edge \\$v\_i \rightarrow v\_{i+1}\\$ for all \\$i\<n\\$.

# Example

In the above tournament, there are five Hamiltonian paths:

* \\$(1,2,4,3)\\$
* \\$(1,4,3,2)\\$
* \\$(2,4,3,1)\\$
* \\$(3,1,2,4)\\$
* \\$(4,3,1,2)\\$

Moreover, it is not possible to construct a tournament on four vertices with more than five Hamiltonian paths, so \\$A038375(4) = 5\\$.

---

The way to win this challenge is to write a program that can compute the largest value of A038375 deterministically in under 10 minutes on my machine, a 2017 MacBook Pro with 8GB RAM and a 2.3 GHz i5 processor.

In the case of a tie at the end of ten minutes, the winning code will be the one that got its final value fastest.

# Answer
# C++ (gcc), \\$N=10\\$

```
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <ctime>
//a rewrite for vector<int>
struct vi
{
	int l,a[9];
	const int& operator[](int u) const {return a[u];}
	int& operator[](int u) {return a[u];}
};
bool operator < (const vi&a,const vi&b)
{
	for(int i=0;i<a.l;++i) if(a[i]!=b[i]) return a[i]<b[i];
	return 0;
}
bool operator == (const vi&a,const vi&b)
{
	for(int i=0;i<a.l;++i) if(a[i]!=b[i]) return 0;
	return 1;
}
std::vector<vi> g[13];
void dfs(int x,int u,const vi&c,int*w)
{
	++w[u];
	if(c[x]&u)
		for(int o=c[x]&u;o;o^=o&-o)
			dfs(__builtin_ctz(o),u^(o&-o),c,w);
}
void dfsf(int x,int u,const vi&c,int*w)
{
	++w[u];
	if((~c[x])&u)
		for(int o=(~c[x])&u;o;o^=o&-o)
			dfsf(__builtin_ctz(o),u^(o&-o),c,w);
}
int main()
{
	g[0].push_back(vi());
	for(int i=0;i<9;++i)
	{
		for(auto t:g[i])
		{
			int m1=0,m=0;
			for(int j=0,r;j<i;++j)
			{
				if((r=__builtin_popcount(t[j]))>m1) m=0,m1=r;
				if(r==m1) m|=1<<j;
			}
			for(int e=0;e<(1<<i);++e) if(__builtin_popcount(e)>m1
			||(__builtin_popcount(e)==m1&&((e&m)==m))) //ensure the node has the highest degree
			{
				vi u; u.l=i+1;
				for(int p=0;p<=i;++p) //enumerate position
				{
					bool s=(p==0); int x;
					#define yield(l,c) do{if((x=(c))>u[l]&&!s) goto skip; else s|=x<u[l],u[l]=x;}while(0)
					for(int a=0;a<p;++a)
						yield(a,((t[a]>>p)<<(p+1))|(t[a]&((1<<p)-1))|((!((e>>a)&1))<<p));
					yield(p,((e>>p)<<(p+1))|(e&((1<<p)-1)));
					for(int a=p;a<i;++a)
						yield(a+1,((t[a]>>p)<<(p+1))|(t[a]&((1<<p)-1))|((!((e>>a)&1))<<p));
					skip:;
					#undef yield
				}
				g[i+1].push_back(u);
			}
		}
		std::sort(g[i+1].begin(),g[i+1].end());
		g[i+1].erase(std::unique(g[i+1].begin(),g[i+1].end()),g[i+1].end());
		int sz=g[i+1].size();
		std::vector<vi> h(sz);
		#pragma omp parallel for
		for(int w=0;w<sz;++w)
		{
			vi u=g[i+1][w],v;
			auto sw=[&](int x,int y) {
				std::swap(v[x],v[y]);
				for(int s=0;s<v.l;++s)
				{
					int&o=v[s];
					if(((o>>x)^(o>>y))&1) o^=(1<<x)|(1<<y);
				}
			};
			for(int x=0;x<=i;++x)
				for(int y=x+1;y<=i;++y)
				{
					{v=u;sw(x,y);u=std::min(u,v);}
					for(int z=y+1;z<=i;++z)
					{
						{v=u;sw(x,y);sw(y,z);u=std::min(u,v);}
						{v=u;sw(x,y);sw(x,z);u=std::min(u,v);}
						{v=u;sw(y,z);sw(x,z);u=std::min(u,v);}
						{v=u;sw(y,z);sw(x,y);u=std::min(u,v);}
						{v=u;sw(x,z);sw(x,y);u=std::min(u,v);}
						{v=u;sw(x,z);sw(y,z);u=std::min(u,v);}
					}
					{v=u;sw(x,y);u=std::min(u,v);}
				}
			h[w]=u;
		}
		std::sort(h.begin(),h.end());
		h.erase(std::unique(h.begin(),h.end()),h.end());
		g[i+1]=h;
	}
	std::cout<<"pre ("<<clock()*1./CLOCKS_PER_SEC<<"s)\n";
	for(int o=0;o<=9;++o)
	{
		int mx=0;
		const int s=g[o].size();
		#pragma omp parallel for reduction(max:mx)
		for(int t=0;t<s;++t)
		{
			int a[9<<9],b[9<<9];
			memset(a,0,sizeof(int)*(o<<o));
			memset(b,0,sizeof(int)*(o<<o));
			for(int i=0;i<o;++i)
				dfs(i,((1<<o)-1)^(1<<i),g[o][t],a+(i<<o)),
				dfsf(i,((1<<o)-1)^(1<<i),g[o][t],b+(i<<o));
			int r[9][9],c=(1<<o)-1,vx[1<<9];
			for(int p=0;p<o;++p)
			{
				int*A=a+(p<<o),vn=0;
				for(int x=0;x<=c;++x) if(A[x]) vx[vn++]=x;
				for(int q=0;q<o;++q) if(p!=q)
				{
					int*B=b+(q<<o),su=0;
					for(int u=0;u<vn;++u)
						su+=A[vx[u]]*B[c^vx[u]];
					r[p][q]=su;
				}
			}
			int m1=0,m=0;
			for(int j=0,pc;j<o;++j)
			{
				if((pc=__builtin_popcount(g[o][t][j]))>m1) m=0,m1=pc;
				if(pc==m1) m|=1<<j;
			}
			for(int i=0;i<(1<<o);++i) if(__builtin_popcount(i)>m1
			||(__builtin_popcount(i)==m1&&((i&m)==m)))
			{
				int tot=(o==0);
				for(int j=0;j<o;++j)
					if(i&(1<<j))
					{
						tot+=a[j<<o];
						for(int ii=c^i;ii;ii^=ii&-ii)
							tot+=r[j][__builtin_ctz(ii)];
					}
					else tot+=b[j<<o];
				mx=std::max(mx,tot);
			}
		}
		std::cout<<"a("<<o+1<<") = "<<mx<<" ("<<clock()*1./CLOCKS_PER_SEC<<"s)\n";
	}
}

```

Try it online!

Compile with `g++` and `-Ofast -funroll-all-loops -ffast-math -fno-stack-protector -march=native -fopenmp`. Note that OpenMP is used for parallelism.

Output on my modest computer:

```
pre (5.217s)
a(1) = 1 (5.218s)
a(2) = 1 (5.218s)
a(3) = 3 (5.219s)
a(4) = 5 (5.221s)
a(5) = 15 (5.221s)
a(6) = 45 (5.222s)
a(7) = 189 (5.223s)
a(8) = 661 (5.225s)
a(9) = 3357 (5.318s)
a(10) = 15745 (18.634s)

```

The run time may differ a lot because of the use of OpenMP parallelism.

---

Explanation for \\$N=9\\$ version:

This code is two-fold. First, it will try to generate all tournament graphs up to isomorphism. Then, it will count the number of hamilton paths on these generated graphs. Adjacency matrices of graphs are stored as arrays of bitmasks (i.e. arrays of uint) for performance reasons.

The second part is relatively easier. We can just use depth-first-search to search for all possible paths and use bitmasks to speed up. The time complexity is \\$O(\text{no. of paths in all graphs})\\$. It's also possible to use bitmask dynamic programming to do it, with \\$O(2^NN^2)\\$. The above code used the former while the latter one should be faster when N goes higher. OpenMP parallelization is used to speed it up.

The first part is harder. My approach is incremental: first generating all tournament graphs of \\$t\\$ nodes, then add one node to be tournament graphs of \\$t+1\\$ nodes. The trick here is to find an order for adding nodes. Here, instead of adding any node, we restrict the added node to have the greatest degree in the result graph. Therefore, a graph won't be generated too many times.

Graph-isomorphism isn't a easy thing to check too. Therefore we're not really trying to make every graph unique, but to have some degree of tolerance. I have two strategies used here. First, the newest \\$t+1\\$-th node won't be directly assigned number \\$t\\$. Instead, we try all the possible numbers from \\$0\\$ to \\$t\\$ and take the result graph with the smallest lexicographic order (you can use early-stopping when comparing lexicographic order, so not much overhead). After generating all \\$t+1\\$-node graphs in this way, we remove the found duplicates by sorting and making them unique. This alone can cut down the number of found graphs for \\$N=9\\$ to around \\$3\times 10^6\\$.

The second strategy is that, after found such candidates, we further try to remove duplicates by trying to swap every two nodes and see if we can get a graph with smaller lexicographic order. We then proceed by sorting and making them unique. These two strategies cut down the number of found graphs for \\$N=9\\$ to around \\$10^6\\$. (This strategy alone is more powerful than I thought, cutting down to around \\$1.1\times 10^6\\$)

---

Explanation for \\$N=10\\$ version:

Some improvements are made upon the \\$N=9\\$ version. First, instead of swapping two positions, three positions are swapped to achieve a better result. This successfully cut the number of graphs generated at \\$N=9\\$ to less than \\$5 \times 10^5\\$ (~50% improvement). OpenMP parallelization is also introduced here to speed up.

Generating all graphs for \\$N=10\\$ sounds unfeasible, so instead I try to expand the last step. We still try to add one node for graphs with \\$9\\$ nodes, but instead of actually generating these new graphs, we can actually count the hamilton paths in them directly!

Consider the relationship between a hamilton path and the new node. The new node can be the first end of the path so we need to find an edge from the new node and continue the path from that node. The new node can also be the second end so we can find an edge to the new node and trace back the path starting from that node.

Of course, the new node can be in the middle of the path. In this case, we can enumerate the two nodes in front and on the back of it. We can then enumerate the subset of nodes both halves of the path contain and then multiply them to get the result.

Notice that the contribution is the same for every pair of nodes adjacent to the new node regardless of other edges to the new node, so we can get that precalculated for every two nodes.

In order to get the number of paths starting and ending on each node covering a certain subset of nodes, we can use depth-first-search from each starting and ending point. (A bitmask dynamic programming could work too, but I guess it's slower)
> 7 votes

# Answer
# JavaScript (Node.js), \\$N=8\\$

Simple brute-force. Finds \\$a(8)=661\\$ in approximately 45 seconds on my laptop. Computing \\$a(9)\\$ with this code would take several hours.

```
function search(n) {
  let m = Array(n).fill(0),
      max = 0;

  function count(m) {
    let res = 0;

    for(let y = 0; y < n; y++) {
      (function path(y, visited) {
        if((visited |= 1 << y) == (1 << n) - 1) {
          res++;
          return;
        }
        for(let msk = m[y] & ~visited, b; msk; msk ^= b) {
          path(31 - Math.clz32(b = msk & -msk), visited);
        }
      })(y);
    }
    return res;
  }

  (function build(x, y) {
    if(y == n - 1) {
      max = Math.max(max, count(m));
    }
    else {
      for(let j = (x == y + 1 ? 1 : 0); j <= (x == n - 1 && !y ? 0 : 1); j++) {
        m[y] = m[y] & ~(1 << x) | j << x;
        m[x] = m[x] & ~(1 << y) | (j ^ 1) << y;
        x + 1 < n ? build(x + 1, y) : build(y + 2, y + 1);
      }
    }
  })(1, 0);

  return max;
}

```

Try it online!
> 6 votes

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


title: Find a Similar Number

text:
# Question
Title: Find a Similar Number
We consider two integers to be *similar* if, when written in decimal, have the same length, and if we compare characters in any two positions for both decimal strings, the comparison results (less, equal or greater) must be the same in both strings.

Formally, for two number that can be written as decimal strings \\$a\_1a\_2\cdots a\_n\\$, \\$b\_1b\_2\cdots b\_m\\$, they're *similar* if and only if \\$n=m\\$ and \\$a\_i\<a\_j\ \leftrightarrow b\_i\<b\_j\\$ (\\$\leftrightarrow\\$ means if and only if) for all \\$ i,j \in \[1,n\]\\$.

For example, 2131 and 8090 are *similar*. 1234 and 1111, 1234 and 4321 are **not** *similar*.

# The challenge

For a given positive integer, find a different non-negative integer *similar* to it. You can assume at least one such integer exists.

* Your implementation shouldn't be too inefficient. It must be at least able to pass the samples in around one hour on an average computer. (If it doesn't end in a few seconds, consider providing a screenshot running it)
* Your code can take the input and output as integers, strings or lists of digits. Standard loopholes are forbidden.

Since this is a , the shortest code in bytes wins!

# Examples

It's (quite) possible to have different outputs on these inputs as long as inputs and outputs are different and *similar*.

```
1 - 0
3 - 9
9 - 1
19 - 23
191 - 121
1111 - 2222 (0 is not considered valid)
2020 - 9393
2842 - 1321
97892 - 31230
113582 - 113452
444615491 - 666807690
87654321000 - 98765432111
98765432111 - 87654321000
526704219279 - 536714329379
99887766553210 - 88776655443210

```

Sample inputs as a list:

```
1,3,9,19,191,1111,2020,2842,97892,113582,444615491,87654321000,98765432111,526704219279,99887766553210

```

# Answer
# Python 3, ~~58~~ 52 bytes

```
lambda n:[9-(9in n)-sum(x>d for x in{*n})for d in n]

```

Try it online!

**Input**: The number `n`, as a list of digits.
**Output**: A similar number, as a list of digits.

*-6 bytes thanks to @xnor!*

**How**:
Reverses the list of unique digits, then maps them to `9,8,7,...` or `8,7,6,...` depending on whether `n` contains the digit 9 or not. For example:

```
               | n = 1827 | n = 7899
Reverse unique |   8721   |   987
Maps to        |   9876   |   876
Results        | m = 6978 | m = 6788

```

### Old solution

### Python 3, 80 bytes

```
f=lambda n,i=9:(i in n)^(i-1in n)and[[d,d^i^~-i][i-2<d<=i]for d in n]or f(n,i-1)

```

Try it online!

**Input**: The number `n`, as a list of digits.
**Output**: A similar number, as a list of digits.

*-1 byte thanks to @KevinCruijssen!*

**How**
The solution tries to find a pair of consecutive digits \\$(i-1,i)\\$ such that one digit appears in \\$n\\$, and the other doesn't. It then replaces all occurrences of one digit with the other.
The pair of digits are searched from \\$(8,9)\\$ downward, in order to discourage replacing 1 with 0.
> 15 votes

# Answer
# JavaScript (ES6), 55 bytes

I/O format: list of digits.

```
a=>a.map(d=>d-=-!/9/.test(a)|!a.includes(d-=d>(a<'2')))

```

Try it online!

### Commented

```
a =>                // a[] = input array of digits
  a.map(d =>        // for each digit d in a[]:
    d -=            //   update d:
      -!/9/.test(a) //     if a[] doesn't include any 9, increment d
      |             //     (this does d = d - (-1 | whatever) = d - (-1) = d + 1)
                    //     otherwise, decrement d if:
      !a.includes(  //     - a[] does not include d - 1
        d -= d >    //     - and d is greater than 0 if the leading digit is not 1,
          (a < '2') //       or greater than 1 otherwise (so that it doesn't result
      )             //       in a leading zero)
  )                 // end of map()

```
> 9 votes

# Answer
# 05AB1E, ~~20~~ ~~16~~ 10 bytes

```
êRāTα:DIQ-

```

-6 bytes after being inspired by *@SurculoseSputum* partially incorrect approach.

I/O as a list of digits.

Try it online or verify all test cases.

**Explanation:**

```
ê          # Sort and uniquify the digits in the (implicit) input-list
           #  i.e. [2,8,4,2] → [2,4,8]
 R         # And reverse it
           #  → [8,4,2]
  ā        # Push a list in the range [1, length] (without popping)
           #  → [1,2,3]
   Tα      # Take the absolute difference with 10
           #  → [9,8,7]
     :     # Replace in the (implicit) input-list the sorted unique digits with [9,8,...]
           #  → [7,9,8,7]
      D    # Duplicate it
       IQ  # Check whether it's equal to the input-list (1 if truthy; 0 if falsey)
           #  → 0 (falsey)
         - # Subtract that from each digit
           #  → [7,9,8,7]
           # (after which the resulting list is output implicitly)

```

---

**Original ~~20~~ 16 bytes approach:**

```
∞IK.Δ‚εSæ2ùÆ.±}Ë

```

-4 bytes thanks to *@petStorm*.

I/O as regular integers.

Try it online or verify the smaller test cases (larger ones time out).

**Explanation:**

```
∞              # Push an infinite list of positive integers: [1,2,3,...]
 IK            # Remove the input-integer itself from the list
.Δ             # Then find the first value in this list which is truthy for:
  ‚            #  Pair the current value with the (implicit) input-integer
               #   i.e. input=2842 and y=1321 → [2842,1321]
   ε           #  Map both to:
    S          #   Convert them to a list of digits
               #    → [[2,8,4,2],[1,3,2,1]]
     æ         #   Take the powerset of this list of digits
      2ù       #   Only leave the pairs
               #    → [[[2,8],[2,4],[2,2],[8,4],[8,2],[4,2]],
               #       [[1,3],[1,2],[1,1],[3,2],[3,1],[2,1]]]
        Æ      #   Reduce each inner pair by subtracting
               #    → [[-6,-2,0,4,6,2],
               #       [-2,-1,0,1,2,1]]
         .±    #   Take the signum of each (-1 if a<0; 0 if a==0; 1 if a>0)
               #    → [[-1,-1,0,1,1,1],
               #       [-1,-1,0,1,1,1]]
           }Ë  #  After the inner map: check if the pair of lists are the same
               #   → 1 (truthy)
               # (after we've found our value, it is output implicitly as result)

```
> 6 votes

# Answer
# K (oK), 27 bytes

```
{((9-9=|/x)-!#?x)(?x@>x)?x}

```

Try it online!

Takes the input as a list ot digits.

Inspired by Kevin Cruijssen's 05AB1E and Surculose Sputum's Python solutions - please don't forget to upvote them!
> 4 votes

# Answer
# Charcoal, ~~24~~ 19 bytes

```
⭆θ⁻⁺⁸¬№θ9ＬΦγ∧›λι№θλ

```

Try it online! Link is to verbose version of code. Now based on @SurculoseSputum's newer answer. Explanation:

```
 θ                  Input as a string
⭆                   Map over characters and join
       θ            Input as a string
      № 9           Count `9`s
     ¬              Logical Not (i.e. does not contain `9`)
   ⁺⁸               Add `8`
          Φγ        Filter on printable ASCII
              λ     ASCII character
             ›      Greater than
               ι    Input character
            ∧       Logical And
                  λ ASCII character
                №θ  Occurs in input
         Ｌ          Length of matches
  ⁻                 Subtract from the `8` or `9`
                    Implicitly print

```

Previous 24-byte version based on @SurculoseSputum's older answer:

```
≔⌈Φχ¬№θＩιη⪫⪪θ⎇⁼η⁹⌈θＩ⊕ηＩη

```

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

```
≔⌈Φχ¬№θＩιη

```

Find the highest digit not present in the input number.

```
⎇⁼η⁹⌈θＩ⊕η

```

If that digit is less than 9 then increment it (which will give a digit in the input number) otherwise take the highest digit of the input number.

```
⪫⪪θ...Ｉη

```

Replace the digit from the input number with the digit not in the input number.
> 3 votes

# Answer
# , 14 bytes

Port of the 10-byte 05AB1E answer.

```
♥f<~|J▄5sO#o═╥

```

Uncompressed:

```
 oFU_:kkT-zrZ:a=-

```
> 3 votes

# Answer
# Erlang (escript), 143 bytes

Port of Surculose Sputum's Python answer.

```
u([])->[];u([H|T])->[H]++u([A||A<-T,A/=H]).
i(X)->case X of true->1;_->0end.
f(A)->[9-i(lists:member(9,A))-lists:sum([i(X>D)||X<-u(A)])||D<-A].

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 79 bytes

Port of @SurculoseSputum answer

```
#/.MapThread[Rule,{a=Union@#,Range[0,9][[-Tr[1^a]-(d=Boole[Max@a>8]);;-1-d]]}]&

```

Try it online!
> 2 votes

# Answer
# , 29 24 16 bytes

```
9-9&e.+\:~@~.i.]

```

Try it online!

*-8 thanks to FrownyFrog!*

*Thanks to Bubbler for catching some bugs. All are now fixed.*

Inspired by Surculose's sweet answer, be sure to upvote him.
> 2 votes

# Answer
# Bash \+ Unix utilities, ~~77~~ 74 bytes

```
tee t|tr "`rs -T|sort -ur|xargs`" "`grep -q 9 t;seq $[8+$?] -1 0|xargs`"<t

```

Try the test suite online!

Input is a list of integers on stdin (space-separated digits).

Output is in the same format, on stdout.

This is an implementation of Surculose Sputum's nice method: List the unique digits that appear in the input, sort them in decreasing order, and then replace them in the original input either with \\$8, 7, 6, \dots\\$ (if \\$9\\$ appears in the input) or with \\$9, 8, 7, \dots\\$ (if \\$9\\$ does not appear in the input).
> 1 votes

# Answer
This is a port of @Surculose Sputum's solution in APL2.

```
U←((A⍳A)=⍳⍴A)/A←,A
((9∊A)⌽⌽⍳10)[U[⍒U]⍳A]

```

It presupposes that `A` is a vector of numbers and that `⎕IO=0`
> -1 votes

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


title: Rectangle of text

text:
# Question
Title: Rectangle of text
Your program gets a text as an input, at least 8 characters long, and always consisting of even number of characters. (no need to evaluate correctness of input).

Your goal is to display that text as a rectangle. For example, given `HelloWorld` as an input, display

```
Hell
d  o
lroW

```

Rules:

* Text goes around clockwise (starting position as you like)
* It will form a closed rectangle, sides 1 character wide.
* The rectangle will have to encompass the most area inside. (just to rule out the trivial answer of displaying the text in two lines)
* No other characters are printed besides the text itself and the necessary padding spaces and line feeds.

As code-golf, shortest code wins.

Winner is selected not sooner than 10 days after first valid answer.

# Answer
### GolfScript, 56 53 40 38 characters

```
1/..,4/):l<n@l>{)" "l*2>@(n@.,l-}do-1%

```

You may test the script online.
> 5 votes

# Answer
## Ruby ~~112~~ 100

I'm new to Ruby and this is my first code golf. I drew upon memowe's perl implementation and tried to make a Ruby version of it. This is ~~112~~ 100 characters and assumes you assign a string to x. Looking forward to seeing others.

```
l=x.size
puts x[0..w=l/2-h=l/4]
1.upto(h-1){|i|puts x[-i]+' '*(w-1)+x[w+i]}
puts x[w+h..l-h].reverse

```

Edited to implement suggestions. I think it's 100 characters now. Thanks guys!
> 7 votes

# Answer
**PostScript 50 binary, 113 ASCII**

This uses graphical output. Hexdump of the program using binary tokens:

```
$ hexdump -C textRect_binary.ps
00000000  74 5b 30 20 39 5b 74 92  62 34 92 36 92 38 92 10  |t[0 9[t.b4.6.8..|
00000010  32 92 19 5d 7b 92 2c 7b  32 92 19 7d 92 83 92 3e  |2..]{.,{2..}...>|
00000020  92 6e 7d 92 49 5d 39 20  39 92 6b 91 c7 39 92 8e  |.n}.I]9 9.k..9..|
00000030  92 c3                                             |..|
00000032

```

Download to try it. Using Ghostscript, the to-be-rendered text can be passed to the program as follows:

```
gs -st=helloworld textRect_binary.ps

```

Graphical output looks like this:

The same code using ASCII tokens looks like this:

```
t[0 9[t length
4 div dup
ceiling
2 copy]{cvi{2 copy}repeat
exch neg}forall]9 9 moveto/Courier 9 selectfont
xyshow

```

The strategy is to use `xyshow` for defining where we move after showing each character before showing the next character. We're starting in the lower left corner, moving clockwise, i.e. first up, then right, then down then left. We're always moving 9 units, so first we have a relative movement of `0 9`, then `9 0`, then `0 -9`, then `-9 0`. We can get from one pair of these numbers to the next with the sequence `exch neg`.

We need to build an array for `xyshow` that holds these pairs of numbers, one pair for each character. This means, if we have `helloworld` as example string, which has 10 characters, we want to go up twice, then right thrice, then down twice and left thrice. We get these values (two and three) by dividing the string length by 8, once rounding to the floor, once to the ceiling.

So, we copy `0 9` twice, then switch to the relative x/y coordinates using `exch neg`, copy those thrice and so on.

This commented code shows what happens on the stack:

```
t[0 9                % t [ 0 9
[t length            % t [ 0 9 [ length
4 div dup            % t [ 0 9 [ length/4 length/4
ceiling              % t [ 0 9 [ length/4=height width
2 copy]              % t [ 0 9 [height width height width]
{%forall             % t [ 0 9 ... x y height_or_width
  cvi                % t [ 0 9 ... x y height_or_width_integer
  {2 copy}           % t [ 0 9 ... x y height_or_width_integer {2 copy}
  repeat             % t [ 0 9 ... x y .. x y
  exch neg           % t [ 0 9 ... x y .. y -x
}forall]             % t [0 9 ... -9 0]
9 9 moveto/Courier 9 selectfont
xyshow

```
> 7 votes

# Answer
## Perl (~~124~~ ~~118~~ 109+3=112)

This formerly was pretty straightforward. Counted all command line options as 1 character each.

```
-nlE
$w=(@s=split//)/2-($h=int@s/4);say@s[0..$w--];say$s[1-$_].$"x$w.$s[$w+$_]for+2..$h;say+reverse@s[@s/2..@s-$h]

```

Example:

```
$ perl -nlE '$w=(@s=split//)/2-($h=int@s/4);say@s[0..$w--];say$s[1-$_].$"x$w.$s[$w+$_]for+2..$h;say+reverse@s[@s/2..@s-$h]'
abcdefghijklmnopqrstuvwxyz
abcdefgh
z      i
y      j
x      k
w      l
v      m
utsrqpon

```
> 5 votes

# Answer
# Brainfuck - 194 187

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

```
> 5 votes

# Answer
# Mathematica 156 199 344

**Edit** : This is a major rewrite of earlier code. It works essentially the same, but now takes as input a string of length \< 120 chars and automatically sizes the square.

It could still be golfed a bit but will not get down to the size of the earlier, and buggier, versions.

```
f@s_ := ({a, t, w, q} = {Automatic, Text, Quotient[StringLength@s, 2],
 Quotient[StringLength[s], 4] + 1};z = StringSplit[StringInsert[s <> ConstantArray[" ", 0],
 "*", {q, 2 q, 3 q}], "*"];
Graphics[{t[z[[1]], {0, q}],t[z[[2]], {q, 0}, a, {0, -1}],t[z[[3]], {0, -q}, a, {-1, 0}],
t[z[[4]], {-q, 0}, a, {0, 1}]},ImageSize -> 500,BaseStyle -> {FontFamily -> "Courier", 21},
PlotRange -> 34,ImagePadding -> 22])

```

**Examples**

```
f["Hello Code Golf World!"]
f["January, February, March,April, May, June, July"]
f["This text is normal, this goes downwards,this is upside-down, and this is upwards"]

```
> 4 votes

# Answer
# Perl + Regexes: 104 (101+3)

(counting code + switches)

Here is a solution using nice Regexes, and a bit of Perl:

```
perl -plE'$w=($l=length)/2-($h=int$l/4);s/..{$w}\K.*/"\n".reverse$&/e;$"x=--$w;s/.\K(.*)(.)$/$"$2\n$1/while--$h'

```

This will only operate correctly on *one* input line.

Inspired by memowe, but essentially without any arrays.
> 2 votes

# Answer
# PostScript (106)

This is inspired by dude's Mathematica solution.

```
0{= =
4 add dup
t length mod 4
lt{-90 rotate}if}0[0 3 -3 0 9 9]concat
0 moveto/Courier 5 selectfont
t kshow

```

With Ghostscript call this like

```
gs -st=hello! boxtext.ps

```

It produces output like.

It uses `kshow` to show the glyphs one by one. After enough glyphs for one side have been shown, everything is rotated by -90 degrees before continuing with the remaining glyphs.

To know when enough glyphs have been shown on the side, we increment a counter by 4 each time a glyph is shown. If the counter value modulo the string length is less than 4, then we know we have to rotate:

```
char  counter  mod 6  compared to 4
 h       4       4          =
 e       8       2          <   => rotate
 l      12       0          <   => rotate
 l      16       4          =
 o      20       2          <   => rotate
 !      24       0          <   => rotate

```

Commented and un-golfed source code:

```
0                      % n
{%kshow                % n char1 char2
  = =                  % n
  4 add dup            % n' n'
  t length mod         % n' (n' mod t_length)
  4 lt                 % n' bool
  {-90 rotate}if       % n'
}                      % n kshowProc
% First 0 for moveto. We add it here to take
% advantage of the surrounding self delimiting tokens.
0                      % n kshowProc 0
% We change the graphics state so that the drawn
% text is at a nice size and not off screen.
[0 3 -3 0 9 9]concat   % n kshowProc 0
0                      % n kshowProc 0 0
moveto                 % n kshowProc
/Courier 5 selectfont  % n kshowProc
t                      % n kshowProc text
kshow                  % n

```
> 2 votes

# Answer
# Python 3(120)

```
s=input()
n=len(s)
h=n//4
q=(n+2)//4-1
p=print
p(s[:q+2])
for i in range(1,h):p(s[n-i]+' '*q+s[q+1+i])
p(s[n-h:q+h:-1])

```

## Test

### input:

```
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz

```

### output:

```
abcdefghijklmn
z            o
y            p
x            q
w            r
v            s
u            t
t            u
s            v
r            w
q            x
p            y
o            z
nmlkjihgfedcba

```
> 2 votes

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

```
g4/Dîsï‚>4∍IŽ9¦SΛ

```

Port of my Charcoal answer.

Try it online.

**Explanation:**

```
g            # Get the length of the (implicit) input-string
 4/          # Divide it by 4
   D         # Duplicate it
    î        # Ceil the copy
     sï      # Swap, and floor the other one
       ‚     # Pair the two together
        >    # Increase both by 1
         4∍  # And extend it to size 4
I            # Push the input-string
Ž9¦          # Push compressed integer 2460
   S         # And convert it to a digit-list: [2,4,6,0]
Λ            # Use the Canvas builtin with these three arguments
             # (which is implicitly output immediately as result)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ž9¦` is `2460`.

The Canvas builtin takes three arguments:

1. The length of the lines. For this we use the list of four values we created at the start: \\$\left\[ \left\lceil\frac{L}{4}\right\rceil+1, \left\lfloor\frac{L}{4}\right\rfloor+1, \left\lceil\frac{L}{4}\right\rceil+1, \left\lfloor\frac{L}{4}\right\rfloor+1 \right\]\\$.
2. The characters we want to display, which is the input-string.
3. The directions in which to draw, which is `[2,4,6,0]`. These directions map to `[→,↓,←,↑]`.

For a more detailed explanation of the Canvas builtin, see this 05AB1E tip of mine.
> 2 votes

# Answer
## Python 2.x: 137

I'm new to code golfing and quite sure this can be improved…

```
def s(t):c=len(t);w=1+c/4;h=(c-w-w)/2;u=w+h;n='\n';print t[:w]+n+n.join(map(((w-2)*' ').join,zip(t[:w+u-1:-1],t[w:u])))+n+t[w+u-1:u-1:-1]

```

Visual testing code:

```
from itertools import chain
from string import letters
for i in range(8,101,2):
    t = ''.join(chain(letters))[:i]
    print '%d: %s' % (i, t)
    s(t)
    print '-----'

```

Something of interest: This solution depends on integer math. If you just do the math symbolically, you'll find that `h=(c-w-w)/2 => h=w-2`, but if you substitute that result every other result will be missing two lower-left characters.
> 1 votes

# Answer
# K, 84

```
{-1'(*r;((|r 3),\:(w-2)#" "),'r 1;|(r:(0,+\(w;h;w;h:_(l-2*w:-_-(1+(l:#x)%4))%2))_x)2);}

```

.

```
k){-1'(*r;((|r 3),\:(w-2)#" "),'r 1;|(r:(0,+\(w;h;w;h:_(l-2*w:-_-(1+(l:#x)%4))%2))_x)2);}"HelloWorld"
Hell
d  o
lroW

k){-1'(*r;((|r 3),\:(w-2)#" "),'r 1;|(r:(0,+\(w;h;w;h:_(l-2*w:-_-(1+(l:#x)%4))%2))_x)2);}"Hellooooooooooooooo Worlddddd!"
Hellooooo
!       o
d       o
d       o
d       o
d       o
d       o
lroW oooo

```
> 1 votes

# Answer
# Scala (135)

The following snippet assumes that `x` contains the string to format, and should be pasted in the scala REPL:

```
val (h,w)=((x.size+3)/4,println(_:Any));val s=x.grouped(h)toSeq;w(s(0));for((l,r)<-s(1)zip(s(3)reverse))w(r+" "*(h-2)+l);w(s(2)reverse)

```

If you don't have scala installed, you can quickly check it using this online Scala interpreter: http://www.simplyscala.com/. Just paste the following text end press evaluate:

```
val x="HelloWorld"
val (h,w)=((x.size+3)/4,println(_:Any));val s=x.grouped(h)toSeq;w(s(0));for((l,r)<-s(1)zip(s(3)reverse))w(r+" "*(h-2)+l);w(s(2)reverse)

```
> 1 votes

# Answer
# Charcoal, ~~16~~ 12 bytes

```
Ｂ⊕Ｌ⪪θ⁴⊕⊘⊘Ｌθθ

```

-4 bytes thanks to *@Neil*.

Try it online (verbose) or try it online (pure).

**Explanation:**

Draw a box using the characters in the implicit input-string:

```
Box(..., ..., q);
Ｂ...θ

```

With a width \\$\left\lceil\frac{L}{4}\right\rceil+1\\$ (where \\$L\\$ is the length of the input), by splitting the input-string into parts of size 4 and getting this list's length incremented by 1:

```
Incremented(Length(Split(q,4)))
⊕Ｌ⪪θ⁴

```

And height \\$\left\lfloor\frac{L}{4}\right\rfloor+1\\$:

```
Incremented(IntDivide(Length(q),4))
⊕⊘⊘Ｌθ

```
> 1 votes

# Answer
## PHP (149)

The text to print should be in a variable named `$x`.

```
@$s=substr;echo$s($x,-$w=($l=strlen($x)/2)-$h=$i=$l-2>>1).'
';while($i--)echo$x[$l+$i].str_repeat(' ',$w-2).$x[$h-$i-1].'
';echo$s(strrev($x),$l,$w);

```
> 0 votes

# Answer
# **JAVA - 320**

```
public class A{
public static void main(String[] a){
String s=a[0];
int l=s.length(),h=l/2,f=h-1,i=0;
for(i=0;i<f;i++)
System.out.print(s.charAt(i));
System.out.print("\n"+s.charAt(l-1));
for(i=0;i<f-2;i++)
System.out.print(" ");
System.out.println(s.charAt(h-1));
for(i=l-2;i>h-1;i--)
System.out.print(s.charAt(i));}}

```

**Note : -** Input is taken from command line

Input : - HelloWorld

Output : -

```
Hell
d  o
lroW

```

Input : - abcdefghijklmnopqrstuvwxyz

Output : -

```
abcdefghijkl
z          m
yxwvutsrqpon

```
> 0 votes

---
Tags: code-golf
---


title: Doubling cascade

text:
# Question
Title: Doubling cascade
First, a mathematical interlude, short, and worth your while:

If `0 < a < 4`, the *logistic function* `f(x) = ax(1-x)` maps the interval \[0,1\] inside itself. This means that one can play the iteration game; for instance, if a=2, the initial value 0.3 becomes 0.42, then 0.4872, etc.

As the parameter `a` increases, the quadratic function `f` becomes more complicated in the following sense:

* `0 < a < 1` all initial values iterate toward 0.
* `1 < a < 3` 0 becomes repelling, but there is a new fixed point (a-1)/a that attracts all iterations.
* `3 < a < 1+sqrt(6)` the new fixed point becomes repelling, but a cycle of 2 attracting points appears.
* `3.44949... < a < 3.54409...` the 2-cycle becomes repelling, but a cycle of 4 attracting points appears.
* etc.

Feigenbaum noticed that the lengths of these parameter intervals decrease at a rate that gets closer and closer to `4.6692...`, the **Feigenbaum constant**. The wonderful discovery is that this period 2 *bifurcation* sequence is a general phenomenon shared by any function that (like the quadratic parabola) is increasing, then decreasing. This was one of the first reports on the *universality of chaos*.

Now for the challenge! Write the shortest possible code that *computes* the Feigenbaum constant to an accuracy of your choice. The point here is **not** to cheat the system by encoding a number that you googled, but to actually have the computer find the value. For reference, here is the constant to 30 digits:

**4.669201609102990671853203821578**

# Answer
## Javascript, ~~141~~ ~~138~~ ~~135~~ 131 bytes, 8 digits

It's something I guess. It should be improveable quite a bit. If anyone needs a start: how to calculate Feigenbaum. And if you rather want to know how to do it code-wise, check out this.

Copy paste the following code in your console. Calculates **4.6692016***68823243* (so not really precise).

```
b=1;c=0;e=3.2;for(i=2;i<13;i++){z=b-c;a=b+z/e;j=4;while(j--){x=y=0;k=2**i;while(k--){y=1-2*y*x;x=a-x*x;}a-=x/y}e=z/(a-b);c=b;b=a;e}

```

```
b=1;c=0;e=3.2;for(i=2;i<13;i++){z=b-c;a=b+z/e;j=4;while(j--){x=y=0;k=2**i;while(k--){y=1-2*y*x;x=a-x*x;}a-=x/y}e=z/(a-b);c=b;b=a;e}
console.log(e)
```
> 3 votes

# Answer
# APL (Dyalog Unicode), 79 bytes

```
⊃⊃{⌽u,a,c÷u←b-⍨a←⍺{⍵-÷/⍵{(⍺-×⍨⊃⍵),1-2××/⍵}⍣⍺⊢0}⍣≡b+c÷⊃e b c←⍵}/(⌽2*1+⍳17),⊂*3↑1

```

Try it online!

Outputs **4.669201609**074452565738237725929176 (10 digits). You can increase the number 17 near the end to get more correct digits; the largest number that fits within 1 minute of TIO is 22, which gives **4.6692016091029**76931847851885076037 (14 digits).

Dyalog APL has 128-bit floating point numbers, which gives more precision needed to get closer to the constant. Otherwise, the number simply diverges after certain number of iterations.

The algorithm itself is the same as this Python sample code, which was already referenced in Thomas W's JS answer and others.

### Ungolfed with comments

```
func←{
  i←⍺      ⍝ Input: ⍺ ← iterations of inner-inner loop
  e b c←⍵  ⍝ Input: ⍵ ← d, a_1, a_1-a_2
  a←b+c÷e  ⍝ Initial value of a ← a_1+(a_1-a_2)÷d
  g←{      ⍝ One iteration of a:
    x y←0     ⍝ Initialize x, y to 0
    h←{       ⍝ One iteration of x,y:
      x y←⍵      ⍝ Extract x,y
      y←1-2×x×y  ⍝ Next value of y
      x←⍺-x×x    ⍝ Next value of x (here ⍺ is outer a)
      x,y        ⍝ Return x,y
    }
    x y←⍵ h⍣⍺⊢x y  ⍝ Iterate h ⍺ times (here ⍺ is outer i)
    ⍵-x÷y          ⍝ Return next value of a
  }
  a←i g⍣≡ a      ⍝ Iterate g until a does not significantly change
  (c÷a-b),a,a-b  ⍝ Return next value of d, a_1, a_1-a_2
}
⍝ Reduce from right over iteration counts starting with (2.7,1,1) and
⍝ extract the value of d
⊃⊃ func/ (⌽2*1+⍳17),⊂*3↑1

```
> 4 votes

# Answer
# Python, 127 bytes

```
c,b,e=0,1,2
for i in range(2,13):a=b+(b-c)/e;exec(("x=y=0;"+"y,x=1-2*y*x,a-x*x;"*2**i+"a=a-x/y;")*17);d,c,b=(b-c)/(a-b),b,a;e=d

```

Credit goes for @ThomasW with his javascript answer.

Add `print(d)` to output **4.669201673141983**. Takes a few seconds, due to the long strings being calculated before execution.
> 2 votes

# Answer
# Charcoal, 84 bytes

```
Ａ¹βＡ⁰εＡ³·²δＦ…²¦¹³«Ａ⁺β∕⁻βεδαＦχ«Ａ⁰ξＡ⁰ψＦＸ²ι«Ａ⁻¹××ψ²ξψＡ⁻α×ξξξ»Ａ⁻α∕ξψα»Ａ∕⁻βε⁻αβδＡβεＡαβ»Ｉδ

```

Try it online! Link to verbose code for explanation.

Uses algorithm from here.

Prints **4.66920**0975097843 (6 digits)
> 1 votes

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


# Question
Title: Decode Arabic to Arabic Presentation Form
# Objective

Given an Arabic string consisting of ISO/IEC 8859-6 Arabic letters (U+0621–063A, 0640–064A), decode it to Arabic Presentation Forms-B (U+FE70–FEFF).

# Behavior of Arabic letters

ISO/IEC 8859-6 Arabic letters change their displayed form to letters in Arabic Presentation Forms-B, which are categorized to **isolated**, **initial**, **medial**, or **final** letters.

* If a letter is the first letter or follows another letter in isolated or final form:

+ If it is also the last letter or it lacks an initial form, it is in **isolated** form.
    + Otherwise, it is in **initial** form.
* Otherwise, if the letter is not the last letter, its medial form is available, and the next letter is not `ء`(U+0621), it is in **medial** form.
* Otherwise, the letter is in **final** form.
* `ـ` (U+0640) is a special case. It doesn't have a presentation form, and always will be mapped to itself. It will be assumed to appear only where a letter in medial form could appear.

Note that Arabic letters are written right-to-left.

# Mapping

Note that we don't care about ligatures (U+FEF5–FEFC).

# Rule

If the string contains a letter not within U+0621–063A nor U+0640–064A, the challenge falls in *don't care* situation.

# Example

The following word:

```
الله (U+0627 U+0644 U+0644 U+0647)

```

is decoded to:

```
ﺍﻟﻠﻪ (U+FE8D U+FEDF U+FEE0 U+FEEA)

```

The following word:

```
تكبر (U+062A U+0643 U+0628 U+0631)

```

is decoded to:

```
تكبر (U+FE97 U+FEDC U+FE92 U+FEAE)

```

The following word:

```
سلـام (U+0633 U+0644 U+0640 U+0627 U+0645)

```

is decoded to:

```
ﺳﻠـﺎﻡ (U+FEB3 U+FEE0 U+0640 U+FE8E U+FEE1)

```

The following word:

```
شيء (U+0634 U+064A U+0621)

```

is decoded to:

```
ﺷﻲﺀ (U+FEB7 U+FEF2 U+FE80)

```

# Answer
> 3 votes
# 05AB1E, ~~110~~ 107 bytes

```
1ƵFLŽ$§R©+ε•7Ö›±ćY¨Γ∊%•ƵBвNåi1‚1ª]˜4ô®¸šIŽ6d-D₂›6*-èRćURviy2èDiyнsë0ëyθDΘIN>èŽ6dQ~i\y1è1ë0]Xs_i¦}н)IŽ6ηDŠkǝ

```

-3 bytes due to looser I/O rules.

I/O as a list of code-point integers.

Try it online or verify all test cases.

**Explanation:**

```
1                   # Push a 1 (which we'll use later on)

```

We start by creating the lookup table:

```
 ƵF                 # Push compressed integer 116
   L                # Pop and push a list in the range [1,116]
    Ž$§             # Push compressed integer 25156
       R            # Reverse it to 65152
        ©           # Store this value in variable `®` (without popping)
         +          # Add it to each value in the list, to make the range [65153,65268]
ε                   # Map each value to:
 •7Ö›±ćY¨Γ∊%•       #  Push compressed integer 35731296019285847629599
             ƵB     #  Push compressed integer 112
               в    #  Convert the larger integer to base-112 as list:
                    #   [1,3,5,7,13,19,41,43,45,47,109,111]
 Nåi                #  If the map-index is in this list:
    1‚1ª            #   Pair it with a 1, and add a second 1 to this list
]˜                  # Close the map and if-statement, and flatten the list of values
  4ô                # Split it into parts of size 4
    ®¸š             # Prepend [65152] (from variable `®`) in front of this list

```

Which will now hold the following list:

```
[[65152],[65153,65154,1,1],[65155,65156,1,1],[65157,65158,1,1],[65159,65160,1,1],[65161,65162,65163,65164],[65165,65166,1,1],[65167,65168,65169,65170],[65171,65172,1,1],[65173,65174,65175,65176],[65177,65178,65179,65180],[65181,65182,65183,65184],[65185,65186,65187,65188],[65189,65190,65191,65192],[65193,65194,1,1],[65195,65196,1,1],[65197,65198,1,1],[65199,65200,1,1],[65201,65202,65203,65204],[65205,65206,65207,65208],[65209,65210,65211,65212],[65213,65214,65215,65216],[65217,65218,65219,65220],[65221,65222,65223,65224],[65225,65226,65227,65228],[65229,65230,65231,65232],[65233,65234,65235,65236],[65237,65238,65239,65240],[65241,65242,65243,65244],[65245,65246,65247,65248],[65249,65250,65251,65252],[65253,65254,65255,65256],[65257,65258,65259,65260],[65261,65262,1,1],[65263,65264,1,1],[65265,65266,65267,65268]]

```

Which corresponds to the following table:

```
ISO 8859-6   Isolated      Final         Initial       Medial
1569[0621]   65152[FE80]
1570[0622]   65153[FE81]   65154[FE82]   1[n\a]        1[n\a]
1571[0623]   65155[FE83]   65156[FE84]   1[n\a]        1[n\a]
1572[0624]   65157[FE85]   65158[FE86]   1[n\a]        1[n\a]
1573[0625]   65159[FE87]   65160[FE88]   1[n\a]        1[n\a]
1574[0626]   65161[FE89]   65162[FE8A]   65163[FE8B]   65164[FE8C]
1575[0627]   65165[FE8D]   65166[FE8E]   1[n\a]        1[n\a]
1576[0628]   65167[FE8F]   65168[FE90]   65169[FE91]   65170[FE92]
1577[0629]   65171[FE93]   65172[FE94]   1[n\a]        1[n\a]
1578[062A]   65173[FE95]   65174[FE96]   65175[FE97]   65176[FE98]
1579[062B]   65177[FE99]   65178[FE9A]   65179[FE9B]   65180[FE9C]
1580[062C]   65181[FE9D]   65182[FE9E]   65183[FE9F]   65184[FEA0]
1581[062D]   65185[FEA1]   65186[FEA2]   65187[FEA3]   65188[FEA4]
1582[062E]   65189[FEA5]   65190[FEA6]   65191[FEA7]   65192[FEA8]
1583[062F]   65193[FEA9]   65194[FEAA]   1[n\a]        1[n\a]
1584[0630]   65195[FEAB]   65196[FEAC]   1[n\a]        1[n\a]
1585[0631]   65197[FEAD]   65198[FEAE]   1[n\a]        1[n\a]
1586[0632]   65199[FEAF]   65200[FEB0]   1[n\a]        1[n\a]
1587[0633]   65201[FEB1]   65202[FEB2]   65203[FEB3]   65204[FEB4]
1588[0634]   65205[FEB5]   65206[FEB6]   65207[FEB7]   65208[FEB8]
1589[0635]   65209[FEB9]   65210[FEBA]   65211[FEBB]   65212[FEBC]
1590[0636]   65213[FEBD]   65214[FEBE]   65215[FEBF]   65216[FEC0]
1591[0637]   65217[FEC1]   65218[FEC2]   65219[FEC3]   65220[FEC4]
1592[0638]   65221[FEC5]   65222[FEC6]   65223[FEC7]   65224[FEC8]
1593[0639]   65225[FEC9]   65226[FECA]   65227[FECB]   65228[FECC]
1594[063A]   65229[FECD]   65230[FECE]   65231[FECF]   65232[FED0]
1601[0641]   65233[FED1]   65234[FED2]   65235[FED3]   65236[FED4]
1602[0642]   65237[FED5]   65238[FED6]   65239[FED7]   65240[FED8]
1603[0643]   65241[FED9]   65242[FEDA]   65243[FEDB]   65244[FEDC]
1604[0644]   65245[FEDD]   65246[FEDE]   65247[FEDF]   65248[FEE0]
1605[0645]   65249[FEE1]   65250[FEE2]   65251[FEE3]   65252[FEE4]
1606[0646]   65253[FEE5]   65254[FEE6]   65255[FEE7]   65256[FEE8]
1607[0647]   65257[FEE9]   65258[FEEA]   65259[FEEB]   65260[FEEC]
1608[0648]   65261[FEED]   65262[FEEE]   1[n\a]        1[n\a]
1609[0649]   65263[FEEF]   65264[FEF0]   1[n\a]        1[n\a]
1610[064A]   65265[FEF1]   65266[FEF2]   65267[FEF3]   65268[FEF4]

not in the list:
1600[0640]                                             1600[0640]

```

After that, we'll use the input to get a quartet from this list:

```
I                   # Push the input-list of codepoint integers
 Ž6d                # Push compressed integer 1569
    -               # And subtract it from each integer in the list
     D              # Duplicate this list
      ₂›            # Check which are larger than 26 (1 if truthy; 0 if falsey)
        6*          # Multiply that by 6 (6 if truthy; 0 if falsey)
          -         # And subtract that from the values in the list as well
           è        # Then index it into our list of quartets

```

And now we apply the rules specified in the challenge description on these quartets of `[isolated, final, initial, medial]`.

```
R                   # Reverse the list
 ć                  # Extract the head; pop and push remainder-list and head separated
  U                 # Pop the head, and store it in variable `X`
                    # (`X` now holds the last letter)
   R                # Reverse the list back
v                   # Loop `y` over each remaining quartet:
 i                  #  If the top of the stack is 1 (it's an isolated or final form):
                    #  (which is always truthy for the first letter, since we pushed a 1 at the start)
  y2è               #   Get the initial form of `y`
     D              #   Duplicate it
      i             #   If it's 1, thus no initial form is available:
       yн           #    Push the isolated form of `y` instead
         s          #    And swap so the 1 is at the top for the next iteration
      ë             #   Else, thus an initial form is available:
       0            #    Push a 0 for the next iteration
 ë                  #  Else (it's an initial or medial form instead):
  yθ                #   Get the medial form of `y`
    DΘ              #   Duplicate it, and 05AB1E-truthify it (1 if 1; else 0)
    I               #   Push the input-list of codepoints again
     N>             #   Use the loop-index+1
       è            #   To index into this list for the next letter codepoint
        Ž6d         #   Push compressed integer 1569
           Q        #   And check if this next codepoint is equal to it (1 if truthy; 0 if falsey)
            ~i      #   If either of the two checks is truthy:
              \     #    Discard the duplicated medial form that's on the stack
               y1è  #    Get the final form of `y`
                  1 #    And push a 1 for the next iteration
             ë      #   Else (it's a medial, and the next character is NOT `ء` (U+0621)):
              0     #    Push a 0 for the next iteration
]                   # Close the loop and all inner if-else statements
 X                  # Push the last letter from variable `X`
  s_i               # If we ended with a 0 (thus an isolated or medial form)
     ¦              #  Remove the first item from `X`
    }н              # After the if-statement: pop and push the first item of `X`
                    # (so the isolated form if we ended with an isolated or final form,
                    #  or the final form if we ended with an initial or medial form)
)                   # Wrap all values on the stack into a list
 I                  # Push the input-list of codepoints again
  Ž6η               # Push compressed integer 1600
     DŠ             # Duplicate it, and triple swap (`®`,1600,1600 to 1600,`®`,1600)
       k            # Get the index of 1600 inside the codepoints list (-1 if not present)
        ǝ           # And insert the 1600 at that index in our created list
                    # (which doesn't work on negative indices)
                    # (after which this list of codepoint integers is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `ƵF` is `116`; `Ž$§` is `25156`; `•7Ö›±ćY¨Γ∊%•` is `35731296019285847629599`; `ƵB` is `112`; `•7Ö›±ćY¨Γ∊%•ƵBв` is `[1,3,5,7,13,19,41,43,45,47,109,111]`; `Ž6d` is `1569`; or `Ž6η` is `1600`.

# Answer
> 4 votes
# JavaScript (ES6),  ~~231 ... 148~~  146 bytes

I/O format: list of code points

```
a=>a.map(t=(c,i)=>c%32?(g=A=>n^c%49?g([x=n%32<26,k*x,x&=454642>>n++*25%54%26,x].map(x=>x&&++k)):A[t=t>1^2*(a[i+1]>1569)]||A[t^=2])(n=k=0)+65151:c)

```

Try it online!

```
a =>                             // a[] = input array
a.map(t = (c, i) =>              // for each code point c at position i in a[]:
  c % 32 ?                       //   if c is not 0x0640:
    ( g = A =>                   //     g is a recursive function taking a list A[]
        n ^ c % 49 ?             //       if we haven't reached the correct character:
          g(                     //         do a recursive call:
            [                    //           build a list describing the existence of:
              x = n % 32 < 26,   //           - isolated: if not in range 0x063B-0x0640
              k * x,             //           - final: same as isolated, except for the
                                 //             first entry which is undefined
              x &=               //           - initial: we use a lookup bit-mask
                454642 >> n++    //             with the following hash formula:
                * 25 % 54 % 26,  //               ((n * 25) mod 54) mod 26
              x                  //           - medial: same as initial
            ].map(x => x && ++k) //           turn it into a list of indices
          )                      //         end of recursive call
        :                        //       else:
          A[                     //         output the relevant entry from A[]:
            t =                  //           update t:
              t > 1 ^ 2 * (      //             (previous was initial or medial) XOR
                a[i + 1] > 1569  //             2 * (this is not the last letter
              )                  //             and the next letter is not 0x0621)
          ] ||                   //         if A[t] is not defined:
            A[t ^= 2]            //           use A[t ^ 2] instead
    )(n = k = 0)                 //     initial call to g with n = k = 0
    + 65151                      //     add 0xFE7F
  :                              //   else:
    c                            //     output c unchanged
)                                // end of map()

```

---
Tags: code-golf, unicode
---


# Question
Title: Chase the Easter Bunny and collect his eggs
Chat room: https://chat.stackexchange.com/rooms/106513/easter-bunny-challenge

Git repo: https://github.com/AJFaraday/easter\_bunny\_hunt

The garden is a 2-dimensional grid with 49 rows and 49 columns.

The Easter Bunny™ is in the center of the garden, minding his own business, holding on to 100 Easter eggs. He'll hop away from where the most people are.

When the Easter Bunny™ hops, we all know he'll leave behind an Easter egg.

Grab an Easter egg for 1 point. Grab the Easter Bunny for 10 points.

The game starts with 4 kids, one in each corner of the garden.

The kids can take 1 step each turn, in one of the 4 cardinal directions (North, South, East or West). When they've each taken a step (or decided not to), the bunny will take a move.

The bunny can hop to any position up to 4 spaces away in both the x and y axes. It will decide where it will hop to by the position of the kids.

The bunny can see kids within 5 spaces of it in any direction (I'm using square distances for simplicity). For each axis, (ignoring the kids in a line with it) it will move away from the most kids it can see. e.g.

* If it can see 1 kid to the right, and none to the left. it will hop 1 step to the west.
* If it can see 3 below, and 1 above, it will hop 2 step north.
* If there are 2 north, 1 south, and 2 west. it will hop directly to a space 1 step south and 2 steps west.

Important quirks:

* The bunny ignores kids on the same row when working out it's north/south hop, and in the same column for it's east/west.
* If it can't see any kids, it will stay still until it can.
* If the left/right and up/down counts are equal, it will reamin rooted to the spot, like a rabbit in the headlights.

The game ends when:

* The Easter Bunny™ leaves the garden.
* The Easter Bunny™ drops his last egg.
* The kids catch the bunny.
* The game reaches the configurable turn limit

## Config

You can edit conig.js to change two things about the run:

* `match_limit` will allow you to end the game when you decide (competition will use 1,000 turns)
* `turn_time` (ms) will set the interval when the game is rendering.

## How to hunt the bunny?

Your code will take the form of an array of 4 JS functions, which will each control a kid starting in these positions (in this order):

* North West (0, 0)
* North East (0, 48)
* South East (48, 48)
* South West (48, 0)

The functions should each have this fingerprint:

```
function(api) {
}

```

api is your function's interface to the game (see below).

### The API

The api object presents these four movement functions:

* `api.north()`
* `api.east()`
* `api.south()`
* `api.west()`

If any of these are called during your function, the kid will take one step in that direction (or the last called of these four directions). If none of thess are called during your function, the kid will stand still.

It also provides information about the state of the game with these methods:

* `api.my_storage()` \- an object you can use to store data and functions for just this kid.
* `api.shared_storage()` \- an object you can use to store data and functions for the whole team.
* `api.turn()` \- Returns a number of turns taken in this game so far.
* `api.bunny()` \- Returns an object of bunny-related info

{ x: 24, y: 24, eggs\_left: 100 }
* `api.kids()` tells you where all the kids are

\[ {x: 0, y: 0, me: true}. ... \]
* `api.eggs()` tells you qhere all the eggs are

\[ {x: 25, y: 25} \]

### Template

Teams.push( { name: 'template', shared\_storage: {}, functions: \[ function(api) { // NW kid }, function(api) { // NE kid }, function(api) { // SE kid }, function(api) { // SW kid } \] } );

* `name` must be a single-word identifier, if you want to run just a single entry.
* `shared_storage` sets the initial state of `api.shared_storage`, it can be used to set data and functions for your team.
* The array `functions` is the behaviour of the 4 kids chasing the bunny.

### How to participate

Change my\_entry to your own team name.

* `git clone https://github.com/AJFaraday/easter_bunny_hunt.git`
* `cd easter_bunny_hunt`
* `npm install -g terser`
* `cp template.js teams/my_entry.js`
* (Write your team code)
* `script/run.sh my_entry` to watch the game
* `script/run.sh` to see all results (if you import more entries)

When you're happy with the result, copy it in to an answer like so:

```
# my_entry - 10 points

Any description you want to add goes here

    Teams.push(
      {
        name: 'template',
        shared_storage: {},
        functions: [
          function(api) {
            // NW kid
          },
          function(api) {
            // NE kid
          },
          function(api) {
            // SE kid
          },
          function(api) {
            // SW kid
          }
        ]
      }
    );

```

### Competition rules

Official scoreboard will be updated roughly once a day.

This will run until the 19th of April, one week after Easter Sunday (in the traditions which celebrate Easter Sunday on the 12th of April this year).

# Answer
> 5 votes
# The Run of Doom, score 109

```
var kid_api = function (api) {
    var bunny = api.bunny();
    var kids = api.kids();
    for (var i = 0;i<kids.length;i++) {
        if(kids[i].me) {
            var me = kids[i];
            if (me.x < 24) {
                return api.east();
            } else if (me.x > 24) {
                return api.west();
            } else {
                var s = api.shared_storage();
                var my_data = s[i];
                if (!my_data) {
                    return;
                }else if (my_data.backaway == bunny.eggs_remaining) {
                    return;
                }else if(bunny.y == me.y + my_data.y && bunny.eggs_remaining != 1) {
                    s[2] = Object.assign({}, s.opposites[my_data.func])
                    s[0] = Object.assign({}, s.opposites[my_data.func])
                    s[2-i].backaway = bunny.eggs_remaining;
                    s[i].backaway = 1;
                    api[s[i].func]();
                } else if (me.y + my_data.y < 0 || me.y + my_data.y > 49) {
                    s[i] = null;
                } else {
                    api[my_data.func]();
                }
            }
        }
    }
}
Teams.push(
  {
    name: 'the_run_of_doom',
    shared_storage: {
        2: {"func": "north", "y": -1},
        0: null,
        "opposites": {
            "south":{"func": "north", "y":-1},
            "north":{"func":"south", "y":1}
        },
    },
    functions: [
      kid_api,
      function(api) {
        // NE kid
      },
      kid_api,
      function(api) {
        // SW kid
      }
    ]
  }
);

```

Uses only two kids: one that starts on the north side, and one that starts on the south side (this version uses NW and SE, but it could be rewritten to use NE and SW, or NE and SE, or NW and SW fairly easily). With a little more effort, one could do this with any combination of two kids.

A score of 110 isn't possible, since the game always ends immediately after the bunny drops the last egg, so I believe this answer is unbeatable.

# Answer
> 2 votes
# random - 0 to 33 points

Totally random kids!

```
Teams.push(
  {
    name: 'random',
    shared_storage: {
      sequence: 'abcd',
      take_step: function(api) {
        var char = api.shared_storage().sequence[Math.floor(Math.random() * 5)];
        if(char) {
          api[api.my_storage()['key'][char]]();
        }
      }
    },
    functions: [
      function(api) {
        // NW kid
        if(!api.my_storage()['key']) {
          api.my_storage()['key'] = {'a': 'east', 'b': 'south', 'c': 'west', 'd': 'north'}
        }
        api.shared_storage().take_step(api);
      },
      function(api) {
        // NE kid
        if(!api.my_storage()['key']) {
          api.my_storage()['key'] = {'a': 'east', 'b': 'south', 'c': 'west', 'd': 'north'}
        }
        api.shared_storage().take_step(api);
      },
      function(api) {
        // SE kid
        if(!api.my_storage()['key']) {
          api.my_storage()['key'] = {'a': 'east', 'b': 'south', 'c': 'west', 'd': 'north'}
        }
        api.shared_storage().take_step(api);
      },
      function(api) {
        // SW kid
        if(!api.my_storage()['key']) {
          api.my_storage()['key'] = {'a': 'east', 'b': 'south', 'c': 'west', 'd': 'north'}
        }
        api.shared_storage().take_step(api);
      }
    ]
  }
);

```

---
Tags: code-challenge, javascript, ai-player
---


title: 2D interpolation

text:
# Question
Title: 2D interpolation
Given required values for an expression with 2 variables, output a short expression which fulfill these values

# Input

You may take the input in any reasonable format, e.g. `f(x,y)=z`, `{(x, y): z}`, `[[[x,y],z]]`, but please write what format is your input is taken in

# Output

Your output needs the be a valid infix expression for two variables, and it has to output the correct value when rounding the output to three digits after the comma, but the current value isn't rounded during calculation. The following symbols/operators are allowed:

## symbols

```
x - the first input variables
y - the second input variables
pi - 3.1415 (4 digit precision)
e - 2.7182 (4 digit precision)
every possible numeric constant (1, 0.12, 42, 13.241)

```

## operators

```
+ sum of two values, in the format a+b
- difference of two values, in the format a-b
* multiplication of two values, in the format a*b
/ division of two values, in the format a/b
^ power of two values, in the format a^b
|| absolute value, in the format |a|
() parentheses, in the format (a)
floor the floor of a value, in the format floor(a)
ceil the ceil of a value, in the format ceil(a)

```

if I forgot anything that you think is important tell me in the comments please.

# Example Testcases

other expressions are okay if they result in the correct values

```
f(0.12, 0.423) = 3.142
f(0.89, 0.90) = 3.142
|
\/
pi (3.1415 gets rounded to 3 digits after the comma - 3.142)

f(0.12, 0.423) = 0.543
f(0.89,0.9)=1.79
|
\/
x+y

```

# Score

Your score is the average length of expression for the following input: https://pastebin.com/tfuBjpc6 , where each batch of inputs (a different function) is separated by a newline. You can transform the format to any format your program accept.

Good luck!

# Answer
> 1 votes
# C++ (gcc), score: 39.2533

Interpolate `x`s or `y`s and `f`s with lagrange interpolation.

```
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <set>
using namespace std;
string ml(const string& a,const string& b) {
	if(a.size()<b.size()) return a;
	return b;
};
string prt(double x,int g,int d=0) {
	char buf[100],buf2[100];
	sprintf(buf,"%%+.%dlf",g);
	sprintf(buf2,buf,x);
	string s=buf2;
	while(s.size()&&s.back()=='0') s.pop_back();
	if(s.size()&&s.back()=='.') s.pop_back();
	if(s=="-0") s="+0";
	if(s=="+3.1415") s="+pi";
	if(s=="-3.1415") s="-pi";
	if(s=="+2.7182") s="+e";
	if(s=="-2.7182") s="-e";
	return s;
};
int main()
{
	double tl=0; int tc=0;
	while(1)
	{
		double x[5],y[5],f[5];
		int bad=0;
		char s[2][20];
		for(int j=0,k;j<5;++j)
		{
			if(scanf("%s %s",s[0],s[1])==EOF) {
				bad=1; break;
			}
			s[0][strlen(s[0])-1]=0;
			sscanf(s[0]+2,"%lf",x+j);
			for(k=0;s[1][k]!=')';++k) ;
			s[1][k]=0;sscanf(s[1],"%lf",y+j);
			sscanf(s[1]+k+2,"%lf",f+j);
		}
		if(bad) break;
		set<double> dx,dy;
		for(int j=0;j<5;++j) dx.insert(x[j]),dy.insert(y[j]);
		string ans; ans.resize(2000);
		auto work=[&](double*d,char s) {
			double md=0;
			stringstream ss;
			double p[5];
			memset(p,0,sizeof p);
			for(int j=0;j<5;++j)
			{
				double w=f[j];
				md=max(md,fabs(d[j]));
				for(int k=0;k<5;++k) if(j!=k)
					w/=d[j]-d[k];
				double q[5];
				memset(q,0,sizeof q);
				q[0]=w;
				for(int k=0;k<5;++k) if(j!=k)
					for(int s=4;s>=0;--s)
						q[s]=(s?q[s-1]:0)-q[s]*d[k];
				for(int k=0;k<5;++k) p[k]+=q[k];
			}
			for(int j=0;j<5;++j)
			{
				double prec=1.0/10000/pow(md,j);
				int u=0;
				while(prec<1) prec*=10,++u;
				string w=prt(p[j],u);
				if(w=="+0") continue;
				ss<<w;
				if(j) ss<<"*"<<s;
				if(j>=2) ss<<"^"<<j;
			}
			string o=ss.str();
			if(o.size()&&o[0]=='+') o.erase(o.begin());
			if(!o.size()) o="0";
			if(o.size()<ans.size()) ans=o;
		};
		if(dx.size()==5) work(x,'x');
		if(dy.size()==5) work(y,'y');
		tl+=ans.size(); ++tc;
		cout<<ans<<"\n";
	}
	cerr<<setprecision(4)<<fixed;
	cerr<<tl/tc<<"\n";
}

```

The output looks like:

```
-265.3786-74.29574*x+344.81918*x^2+225.130398*x^3+36.610661*x^4
35.1581-3.27602*y+0.113946*y^2+0.412073*y^3-0.080117*y^4
-14.961
0.3769+0.50931*x-0.172598*x^2-0.0317501*x^3+0.0113617*x^4
-9.3762-1.54567*y+9.224426*y^2+5.413074*y^3+0.8106773*y^4
-3.7267-3.1155*x+0.011054*x^2-0.002775*x^3-0.0010706*x^4
1
4
31.8856+38.31442*x-0.94623*x^2-24.221891*x^3-8.086617*x^4
0.4856+0.08145*y+0.084768*y^2+0.0113*y^3+0.0001758*y^4

```

# Answer
> -1 votes
# C (gcc), 798 bytes, score: 3.323226 or 16.521740

There are two versions of the code. The less cheaty version will output an expression in form of `x * y * 0 + z`, while the more cheaty version will output an expression in form of `z`.

Obviously creating a "real" solution would bump the score down, but given that it's just a tiny gain and as far as I can tell it's a NP-complete problem, it's simply not worth doing it (some edge cases where you tell a 7-long number that's for instance `x+1`, then you lose a few points, but it's not significant this much).

```
cheaty/ Average length: 11618 / 3496: 3.323226
less cheaty/ Average length: 57760 / 3496: 16.521740

```

The code:

```
float round(float x) {
    float v = (int)(x * 1000 + .5);
    return (float)v / 1000;
}

char * find_constants(float f) {
	float x = round(f);
	static char buf[16];
	if(x == 3.142) return "pi";
	if(x == 2.718) return "e";
	sprintf(buf, "%.3g", f);
	return buf;
}

int main(void) {
	float x, y, z;
	long total_len = 0, amount = 0;
	while(scanf("%f %f %f", &x, &y, &z) == 3) {
		#ifdef LESS_CHEATY
			total_len += strlen(find_constants(x))+strlen(find_constants(y))+strlen(find_constants(z))+4;
			// printf("%s*%s*0+%s\n", find_constants(x), find_constants(y), find_constants(z));
		#else
			total_len += strlen(find_constants(z));
			// printf("%s\n", find_constants(z));
		#endif
		amount++;
	}
	printf("Average length: %d / %d: %f\n", total_len, amount, (float)total_len / (float)amount);
}

```

Try me online!

---
Tags: math, code-challenge, test-battery, expression-building
---


title: Modify The Stack

text:
# Question
Title: Modify The Stack
Let's say you have a stack, which at the start contains `a b c` in this order (`a` is on the top). You are given the required output stack, in any reasonable format (a list, a string, etc.), e.g. `[a, c, b]` (here `a` is on the top, below it `c` and below it `b`). You can also take the input reversed if you want, e.g. `[b, c, a]` where a is in the top

Your task is to output the **shortest** sequence of operations to achieve that stack formation, and you may assume that there is such sequence, and it's shorter than 10 moves:

* `s` \- swap the top two elements of the stack, `a b c -> b a c`
* `d` \- duplicate the top element of the stack, `a b c -> a a b c`
* `t` \- swap (or rotate) the top three elements of the stack, `a b c -> b c a`

You may call the input/operations whatever you want, as long as it's consistent.

### Examples

```
['a', 'c', 'b'] -> st
([a b c] [b a c] [a c b])
['a','a','b','c'] -> d
['a','b','a','b','c'] -> sdtsdt
([a b c] [b a c] [b b a c] [b a b c] [a b b c] [a a b b c] [a b a b c]) (sdttdt is also valid)
['c','b','a'] -> ts

```

This is an example ungolfed algorithm which solves it: https://pastebin.com/9UemcUwj

# Score

This is a codegolf, so the shortest answer wins. good luck!

# Answer
# Python 2, 117 bytes

Simple BFS brute-force algorithm, outputs to STDERR.

```
t=input()
l=[('abc','')]
for s,o in l:s==t>exit(o);l+=(s[1:3]+s[0]+s[3:],o+'t'),(s[0]+s,o+'d'),(s[1::-1]+s[2:],o+'s')

```

Try it online!

Combined with Surcoloses way of generating the new stacks, this gets to 97 bytes: Try it online!
> 8 votes

# Answer
# JavaScript (ES6), 79 bytes

Expects `460` instead of `abc`. Output format: \\$1\\$ = **s**wap, \\$2\\$ = **d**uplicate and \\$3\\$ = ro**t**ate.

Same logic as the main version, but with a less readable input format which was chosen to optimize the lookup table.

```
f=s=>([a,b,c]=s,d=s.slice(3))?a-b?f(c+a+b+d)+3:f(b+c+d)+2:[[13,31,3,1,33][s%7]]

```

Try it online!

---

# JavaScript (ES6),  ~~100 ... 84~~  81 bytes

Expects `012` instead of `abc`. Output format: \\$1\\$ = **s**wap, \\$2\\$ = **d**uplicate and \\$3\\$ = ro**t**ate.

```
f=s=>([a,b,c]=s,d=s.slice(3))?a-b?f(c+a+b+d)+3:f(b+c+d)+2:[[3,33,31,,,13,1][s&7]]

```

Try it online!

## How?

This solves the problem by starting with the input string and transforming it back into `"012"`.

### Step 1

The first step of the algorithm is to reverse *duplicate* and *rotate* operations until the string is exactly 3-character long.

We can notice that given an input string of length \\$n\\$, there are necessarily \\$n-3\\$ *duplicate*.

We can reverse a *duplicate* operation whenever the first 2 characters of the string are equal.

If the first 2 characters are not equal and the string is still longer than 3 characters, it means that we have to reverse a *rotate*. (It can't be a *swap* because the first 2 characters would still be different.)

We need to reverse at most 2 consecutive *rotate* before we can reverse the next *duplicate*. (If it still doesn't work after 2 reversed *rotate*, it means that the input is invalid.)

### Step 2

Once we have a string \\$s\\$ which is 3-character long, we use a lookup table to figure out how `"012"` can be turned into \\$s\\$ with as few operations as possible:

```
"012" : no operation
"021" : "st" because t(s("012")) = t("102") = "021"
"102" : "s"  because s("012") = "102"
"120" : "t"  because t("012") = "120"
"201" : "tt" because t(t("012")) = t("120") = "201"
"210" : "ts" because s(t("012")) = s("120") = "210"

```

The lookup table works by coercing the string to an integer an applying a modulo \\$8\\$.

```
 string | mod 8
--------+-------
  "012" |   4
  "021" |   5
  "102" |   6
  "120" |   0
  "201" |   1
  "210" |   2

```

## Commented

```
f = s =>               // s = input string
  (                    //
    [a, b, c] = s,     // split the first 3 characters as a, b and c
    d = s.slice(3)     // d = all remaining characters after the 3 first ones
  ) ?                  // if d is not empty:
    a - b ?            //   if a is not equal to b:
      f(c + a + b + d) //     reverse a 'rotate' by re-ordering the first 3 characters
      + 3              //     append a "3"
    :                  //   else:
      f(b + c + d)     //     reverse a 'duplicate' by removing the leading character
      + 2              //     append a "2"
  :                    // else:
    [                  //   make sure the following result can be coerced to a string:
      [                //     lookup table:
        3              //       0: "120" -> "t" encoded as "3"
        33,            //       1: "201" -> "tt" encoded as "33"
        31,            //       2: "210" -> "ts" encoded as "31"
        ,              //       3: not used
        ,              //       4: "012" -> no operation
        13,            //       5: "021" -> "st" encoded as "13"
        1              //       6: "102" -> "s" encoded as "1"
      ]                //
      [s & 7]          //     compute s mod 8
    ]                  //

```
> 8 votes

# Answer
# Haskell, ~~111~~ 110 bytes

```
g s=[b|(a,b)<-zip f o,a==s]!!0
f="abc":(f>>=k)
k w@(a:b:c:s)=[b:c:a:s,a:w,b:a:c:s]
o="":[x++[w]|x<-o,w<-"tds"]

```

Try it online!

Finds the position of the target stack in an infinite list of possible stacks `f`, then uses the result to index into the infinite list of operations `o`.
> 6 votes

# Answer
# Python 3.8, 105 bytes

```
f=lambda r,i=0,j=1,s="abc",*l:(t:=i%4)and f(r,i//4,j,s[t>1:t]+s[0]+s[t:],*l,t)or f(r,j,j+1)if s!=r else l

```

Try it online!

**Input**: A string representing the goal stack, where the first character of the string is the top of the stack.
**Output**: A tuple of `0,1,2` representing `d,s,t` respectively.

This is a brute-force recursive search that simply tries all possible operation sequences of increasing size.

---

***102 bytes*** *if the solution doesn't have to deal with the edge case `"abc"`*

```
f=lambda r,i=0,j=1,s="abc",*l:(t:=i%4)and f(r,i//4,j,s[t>1:t]+s[0]+s[t:],*l,t)or(s==r)*l or f(r,j,j+1)

```

Try it online!

---

**How**:

Given the stack `s` as a string, and an operation `t = 1, 2, or 3` reperesenting `d, s, t` respectively, the resulting stack is:

```
s[t>1:t]+s[0]+s[t:]

```

A sequence of operations can be encoded as a single integer `j`, and decoded using division and mod. The solution simply increment `j`, then test if `j` can produces the goal stack. This guarantees that the result sequence is the shortest.

The argument `i` keeps track of the remaining operations in the current sequence. `l` is the tuple of operations performed.
> 6 votes

# Answer
# Retina 0.8.2, ~~88~~ ~~82~~ 79 bytes

```
^(.)(\1[a-c]+)
$2d
}`^(.)(.)(\1|\2)([a-c]+)
$3$1$2$4t
abc

ac|bac?
s
a

bc?|c
t

```

Try it online! Link includes test cases. Uses @xnor's direct approach. Explanation:

```
^(.)(\1[a-c]+)
$2d

```

If the first two characters are the same, then they must have just been duplicated, so output a `d` and remove the first character. (The `[a-c]` ensures that the outputs collect in reverse order.)

```
^(.)(.)(\1|\2)([a-c]+)
$3$1$2$4t

```

If the third character is one of the first two, then try rotating the stack.

```
}`

```

Repeat the above stages until the three characters are all different, in which case they should be the last three.

```
abc

```

If they are `abc` then there is nothing left to do.

```
ac|bac?
s

```

`acb`, `bac`, and `cba` all need a swap. For `bac` this completes the operations; `acb` needs a rotation after the swap, while `cba` needs a rotation before the swap. Leaving a `b` or `c` behind will achieve this later.

```
a

```

Remove any remaining `a`s as they have nothing left to contribute.

```
bc?|c
t

```

Any remaining `b`s and `c`s indicate rotations, except that `bc` is just one rotation.

Previous brute-force 82-byte solution:

```
$
¶abc:
{`^(.+)¶(.+¶)*\1:(.*)(¶.+)*$
$3
(.)(.)(.)(.*:.*)
$2$1$3$4s¶$1$&d¶$2$3$1$4t

```

Try it online! Link includes test cases. Edit: Saved 6 bytes thanks to @someone. Explanation:

```
$
¶abc:

```

Append the initial position to the input.

```
{`

```

Repeat until a solution is found.

```
^(.+)¶(.+¶)*\1:(.*)(¶.+)*$
$3

```

If the input matches an output stack, delete everything except the output sequence.

```
(.)(.)(.)(.*:.*)
$2$1$3$4s¶$1$&d¶$2$3$1$4t

```

For each position, compute the three positions arising from applying each of the three operators.
> 5 votes

# Answer
# 05AB1E, ~~21~~ ~~18~~ 17 bytes

```
g…sŠD×æé.Δ₁`r.V)Q

```

-1 byte by taking the input as `256` () for `abc` respectively, instead of `ABC` (`žR`) I had prior.

Takes the input in reversed order using the characters `256` for `abc` respectively.
Outputs `s` for swap; `D` for duplicate; and `Š` for triple swap/rotate.

Try it online or verify all test cases.

**Explanation:**

```
g           # Get the length of the (implicit) input-list
 …sŠD       # Push the string "sŠD"
     ×      # Repeat it the length amount of times
      æ     # Take the powerset of this
       é    # Sort them by length
            #  i.e. input-length=3 → ["","s","Š","D","s","Š","D","s","Š","D","sŠ","sD","ŠD","ss","Šs","Ds","sŠ","ŠŠ","DŠ","sŠ","sD","ŠD","DD","sD","ŠD","ss","Šs","Ds","ss","Šs","Ds","sŠ","ŠŠ","DŠ","sŠ","ŠŠ","DŠ","sŠ","sD","ŠD","DD","sD","ŠD","DD","sD","ŠD","sŠD","sŠs","sDs","ŠDs","sŠŠ","sDŠ","ŠDŠ","ssŠ","ŠsŠ","DsŠ","sŠD","sDD","ŠDD","ssD","ŠsD","DsD","sŠD","ŠŠD","DŠD","sŠD","sŠs","sDs","ŠDs","sss","Šss","Dss","sŠs","ŠŠs","DŠs","sŠs","sDs","ŠDs","DDs","sDs","ŠDs","sŠŠ","sDŠ","ŠDŠ","ssŠ","ŠsŠ","DsŠ","sŠŠ","ŠŠŠ","DŠŠ","sŠŠ","sDŠ","ŠDŠ","DDŠ","sDŠ","ŠDŠ","ssŠ","ŠsŠ","DsŠ","ssŠ","ŠsŠ","DsŠ","sŠD","sDD","ŠDD","ssD","ŠsD","DsD","sŠD","ŠŠD","DŠD","sŠD","sDD","ŠDD","DDD","sDD","ŠDD","ssD","ŠsD","DsD","ssD","ŠsD","DsD","sŠD","ŠŠD","DŠD","sŠD","ŠŠD","DŠD","sŠD","sŠDs","sŠDŠ","sŠsŠ","sDsŠ","ŠDsŠ","sŠDD","sŠsD","sDsD","ŠDsD","sŠŠD","sDŠD","ŠDŠD","ssŠD","ŠsŠD","DsŠD","sŠDs","sŠss","sDss","ŠDss","sŠŠs","sDŠs","ŠDŠs","ssŠs","ŠsŠs","DsŠs","sŠDs","sDDs","ŠDDs","ssDs","ŠsDs","DsDs","sŠDs","ŠŠDs","DŠDs","sŠDs","sŠDŠ","sŠsŠ","sDsŠ","ŠDsŠ","sŠŠŠ","sDŠŠ","ŠDŠŠ","ssŠŠ","ŠsŠŠ","DsŠŠ","sŠDŠ","sDDŠ","ŠDDŠ","ssDŠ","ŠsDŠ","DsDŠ","sŠDŠ","ŠŠDŠ","DŠDŠ","sŠDŠ","sŠsŠ","sDsŠ","ŠDsŠ","sssŠ","ŠssŠ","DssŠ","sŠsŠ","ŠŠsŠ","DŠsŠ","sŠsŠ","sDsŠ","ŠDsŠ","DDsŠ","sDsŠ","ŠDsŠ","sŠDD","sŠsD","sDsD","ŠDsD","sŠŠD","sDŠD","ŠDŠD","ssŠD","ŠsŠD","DsŠD","sŠDD","sDDD","ŠDDD","ssDD","ŠsDD","DsDD","sŠDD","ŠŠDD","DŠDD","sŠDD","sŠsD","sDsD","ŠDsD","sssD","ŠssD","DssD","sŠsD","ŠŠsD","DŠsD","sŠsD","sDsD","ŠDsD","DDsD","sDsD","ŠDsD","sŠŠD","sDŠD","ŠDŠD","ssŠD","ŠsŠD","DsŠD","sŠŠD","ŠŠŠD","DŠŠD","sŠŠD","sDŠD","ŠDŠD","DDŠD","sDŠD","ŠDŠD","ssŠD","ŠsŠD","DsŠD","ssŠD","ŠsŠD","DsŠD","sŠDsŠ","sŠDsD","sŠDŠD","sŠsŠD","sDsŠD","ŠDsŠD","sŠDss","sŠDŠs","sŠsŠs","sDsŠs","ŠDsŠs","sŠDDs","sŠsDs","sDsDs","ŠDsDs","sŠŠDs","sDŠDs","ŠDŠDs","ssŠDs","ŠsŠDs","DsŠDs","sŠDsŠ","sŠDŠŠ","sŠsŠŠ","sDsŠŠ","ŠDsŠŠ","sŠDDŠ","sŠsDŠ","sDsDŠ","ŠDsDŠ","sŠŠDŠ","sDŠDŠ","ŠDŠDŠ","ssŠDŠ","ŠsŠDŠ","DsŠDŠ","sŠDsŠ","sŠssŠ","sDssŠ","ŠDssŠ","sŠŠsŠ","sDŠsŠ","ŠDŠsŠ","ssŠsŠ","ŠsŠsŠ","DsŠsŠ","sŠDsŠ","sDDsŠ","ŠDDsŠ","ssDsŠ","ŠsDsŠ","DsDsŠ","sŠDsŠ","ŠŠDsŠ","DŠDsŠ","sŠDsŠ","sŠDsD","sŠDŠD","sŠsŠD","sDsŠD","ŠDsŠD","sŠDDD","sŠsDD","sDsDD","ŠDsDD","sŠŠDD","sDŠDD","ŠDŠDD","ssŠDD","ŠsŠDD","DsŠDD","sŠDsD","sŠssD","sDssD","ŠDssD","sŠŠsD","sDŠsD","ŠDŠsD","ssŠsD","ŠsŠsD","DsŠsD","sŠDsD","sDDsD","ŠDDsD","ssDsD","ŠsDsD","DsDsD","sŠDsD","ŠŠDsD","DŠDsD","sŠDsD","sŠDŠD","sŠsŠD","sDsŠD","ŠDsŠD","sŠŠŠD","sDŠŠD","ŠDŠŠD","ssŠŠD","ŠsŠŠD","DsŠŠD","sŠDŠD","sDDŠD","ŠDDŠD","ssDŠD","ŠsDŠD","DsDŠD","sŠDŠD","ŠŠDŠD","DŠDŠD","sŠDŠD","sŠsŠD","sDsŠD","ŠDsŠD","sssŠD","ŠssŠD","DssŠD","sŠsŠD","ŠŠsŠD","DŠsŠD","sŠsŠD","sDsŠD","ŠDsŠD","DDsŠD","sDsŠD","ŠDsŠD","sŠDsŠD","sŠDsŠs","sŠDsDs","sŠDŠDs","sŠsŠDs","sDsŠDs","ŠDsŠDs","sŠDsŠŠ","sŠDsDŠ","sŠDŠDŠ","sŠsŠDŠ","sDsŠDŠ","ŠDsŠDŠ","sŠDssŠ","sŠDŠsŠ","sŠsŠsŠ","sDsŠsŠ","ŠDsŠsŠ","sŠDDsŠ","sŠsDsŠ","sDsDsŠ","ŠDsDsŠ","sŠŠDsŠ","sDŠDsŠ","ŠDŠDsŠ","ssŠDsŠ","ŠsŠDsŠ","DsŠDsŠ","sŠDsŠD","sŠDsDD","sŠDŠDD","sŠsŠDD","sDsŠDD","ŠDsŠDD","sŠDssD","sŠDŠsD","sŠsŠsD","sDsŠsD","ŠDsŠsD","sŠDDsD","sŠsDsD","sDsDsD","ŠDsDsD","sŠŠDsD","sDŠDsD","ŠDŠDsD","ssŠDsD","ŠsŠDsD","DsŠDsD","sŠDsŠD","sŠDŠŠD","sŠsŠŠD","sDsŠŠD","ŠDsŠŠD","sŠDDŠD","sŠsDŠD","sDsDŠD","ŠDsDŠD","sŠŠDŠD","sDŠDŠD","ŠDŠDŠD","ssŠDŠD","ŠsŠDŠD","DsŠDŠD","sŠDsŠD","sŠssŠD","sDssŠD","ŠDssŠD","sŠŠsŠD","sDŠsŠD","ŠDŠsŠD","ssŠsŠD","ŠsŠsŠD","DsŠsŠD","sŠDsŠD","sDDsŠD","ŠDDsŠD","ssDsŠD","ŠsDsŠD","DsDsŠD","sŠDsŠD","ŠŠDsŠD","DŠDsŠD","sŠDsŠD","sŠDsŠDs","sŠDsŠDŠ","sŠDsŠsŠ","sŠDsDsŠ","sŠDŠDsŠ","sŠsŠDsŠ","sDsŠDsŠ","ŠDsŠDsŠ","sŠDsŠDD","sŠDsŠsD","sŠDsDsD","sŠDŠDsD","sŠsŠDsD","sDsŠDsD","ŠDsŠDsD","sŠDsŠŠD","sŠDsDŠD","sŠDŠDŠD","sŠsŠDŠD","sDsŠDŠD","ŠDsŠDŠD","sŠDssŠD","sŠDŠsŠD","sŠsŠsŠD","sDsŠsŠD","ŠDsŠsŠD","sŠDDsŠD","sŠsDsŠD","sDsDsŠD","ŠDsDsŠD","sŠŠDsŠD","sDŠDsŠD","ŠDŠDsŠD","ssŠDsŠD","ŠsŠDsŠD","DsŠDsŠD","sŠDsŠDsŠ","sŠDsŠDsD","sŠDsŠDŠD","sŠDsŠsŠD","sŠDsDsŠD","sŠDŠDsŠD","sŠsŠDsŠD","sDsŠDsŠD","ŠDsŠDsŠD","sŠDsŠDsŠD"]
.Δ          # Then find the first string which is truthy for:
  ₁         #  Push the builtin 256
   `        #  Pop and push them separated to the stack
    r       #  Reverse the stack, so the order is [6,5,2,string]
     .V     #  Execute the string as 05AB1E code
       )    #  Wrap all values on the stack into a list
        Q   #  And check that it's equal to the (implicit) input-list

```
> 3 votes

# Answer
# Ruby, 126 bytes

```
->s{*w='',321;(a,b,*w=w;w<<a+?d<<b*10+(k=b%10)<<a+?s<<b+k*10-(z=b%100)+z/10<<a+?t<<b+k*100-(x=b%1000)+x/10)until w[1]==s;w[0]}

```

Try it online!
> 2 votes

---
Tags: code-golf, stack
---