# Question
Title: Output every halting program (write a parallel interpreter)
The goal of this challenge is to (eventually) output *every* possible halting program in a language of your choice. At first this may sound impossible, but you can accomplish this with a very careful choice of execution order.

Below is an ASCII diagram to illustrate this. Let the columns represent a numbering of every possible program (each program is a finite number of symbols from a finite alphabet). Let each row represent a singular step in execution of that program. An `X` represent the execution performed by that program at that time-step.

```
 step#  p1 p2 p3 p4 p5 p6
     1  X  X  X  X  X  X
     2  X  X  X  X  X
     3  X  X     X  X
     4  X  X     X  X
     5  X  X     X
     6     X     X
     7     X     X
     8     X     X
     9     X     X
     ∞     X     X

```

As you can tell, programs 2 and 4 don't halt. If you were to execute them one-at-a-time, your controller would get stuck in the infinite loop that is program 2 and never output programs 3 and beyond.

Instead, you use a dovetailing approach. The letters represent a possible order of execution for the first 26 steps. The `*`s are places where that program has halted and is outputted. The `.`s are steps that haven't been executed yet.

```
 step#  p1 p2 p3 p4 p5 p6
     1  A  C  F  J  N  R  V
     2  B  E  I  M  Q  *  Z
     3  D  H  *  P  U
     4  G  L     T  Y
     5  K  O     X
     6  *  S     .
     7     W     .
     8     .     .
     9     .     .
     ∞     .     .

```

## Requirements for the target language

The target language (the one being parallel-interpreted) must be Turing-complete. Other than that, it can be *any* language that's Turing-complete, including Turing-complete subsets of much larger languages. You are also free to interpret things like cyclic tag system rules. You are also allowed to create a language to test, as long as you can show why it is Turing-complete.

As an example, if you choose to test brainfuck, then it is best to test just the `[]-+<>` subset, since input is not supported and output is just thrown away (see below).

When it comes to the "controller" program (which you are golfing), there's no special requirements. Normal language restrictions apply.

## How to create an infinite list of programs

The majority of programming languages can be represented as a series of symbols from a finite alphabet. In this case, it is relatively easy to enumerate a list of every possible program in order of increasing length. The alphabet you use should be representative of the *requirements* of the target language. In most cases, this is printable ASCII. If your language supports Unicode as an additional feature, you should not test every possible combination of Unicode characters, just ASCII. If your language only uses `[]-+<>` then don't test out the various combinations of "comment" ASCII characters. Languages like APL would have their own special alphabets.

If your language is best described in some non-alphabetic way, like Fractran or Turing Machines, then there are other equally valid methods of generating a list of all possible valid programs.

## Interpreting an ever-growing list of programs

The key part of this challenge is to write a parallel interpreter for a growing list of programs. There are some basic steps for this:

* Add a finite number of programs to the list
* Interpret each program on the list individually for a finite period of time. This can be accomplished by performing one instruction step for each. Save all of the states.
* Remove all terminating/error-throwing programs from the list
* Output the cleanly halted\* programs
* Add some more programs to the list
* Simulate each program in turn, picking up execution of older programs where it left off
* Remove all terminating/error-throwing programs from the list
* Output the cleanly halted\* programs
* repeat

**\*You should only output programs that halt cleanly.** This means that there were no syntax errors or uncaught exceptions thrown during execution. Programs which ask for input should also be terminated without outputting them. If a program produces output, you shouldn't terminate it, just throw the output away.

## More rules

* You must not spawn new threads to contain the tested programs, as this offloads the work of parallelization onto the host OS / other software.
* Edit: To close potential future loopholes, you are not allowed to `eval` (or any related function) a part of the *tested* program's code. You *can* `eval` a codeblock from the interpreter's code. (The BF-in-Python answer is still valid under these rules.)
* This is
* The language you write your submission in **does not** need to be the same as the language you are testing/outputting.
* You should assume that your available memory is unbounded.
* When proving Turing-completeness, you may assume that input is hardcoded into the program, and output can be read off the program's internal state.
* If your program outputs itself, it is probably wrong or a polyglot.

# Answer
# Brainfuck in Python, 567 bytes

A relatively simple solution, as Brainfuck is hardly the most difficult language to write an interpreter for.

This implementation of Brainfuck has the data pointer starting at 0, only allowed to take a positive value (considered an error if it tries to go to the left of 0). The data cells can take on values from 0 to 255 and wrap. The 5 valid instructions are `><+[]` (`-` is unnecessary due to the wrapping).

I think the output is all correct now, however it is difficult to be sure that it is printing every possible solution so I may be missing some.

```
o="><+]["
A="[]if b%s1<0else[(p,a+1,b%s1,t+[0],h)]"
C="[(p,h[a]+1,b,t,h)if t[b]%s0else(p,a+1,b,t,h)]"
I=lambda s,i:i*">"if""==s else o[o.find(s[0])+i-5]+I(s[1:],i*o.find(s[0])>3)
s="";l=[]
while 1:
 s=I(s,1)
 r=[];h={}
 for i in range(len(s)):
    if s[i]=="[":r+=[i]
    if s[i]=="]":
     if r==[]:break
     h[r[-1]]=i;h[i]=r[-1];r=r[:-1]
 else:
    if r==[]:
     l+=[(s,0,0,[0],h)];i=0
     while i<len(l):
        p,a,b,t,h=l[i]
        if a>=len(p):print p;l[i:i+1]=[]
        else:l[i:i+1]=eval([A%("+","+"),A%("-","-"),"[(p,a+1,b,t[:b]+[(t[b]+1)%256]+t[b+1:],h)]",C%">",C%"=="][o.find(p[a])]);i+=1

```

The first few ouputs:

```
>
+
>>
+>
><
>+
++
[]
>>>
+>>

```

And a list of the first 2000: http://pastebin.com/KQG8PVJn

And finally a list of the first 2000 outputs with `[]` in them: http://pastebin.com/iHWwJprs
(all the rest are trivial as long as they're valid)

Note that the output is not in a sorted order, though it may appear that way for many of them, as the programs that take longer will be printed later.
> 12 votes

# Answer
# Bitwise Cyclic Tag in CJam, ~~98~~ ~~87~~ ~~84~~ 77 bytes

```
L{Z):Z2b1>_,,1>\f{/([\:~]a2*}+{)~[\({1+(:X+\_0=Xa*+}{0+\1>}?_{]a+}{];p}?}%1}g

```

Since this is an infinite loop, you can't directly test this in the online interpreter. However, here is an alternative version that reads the number of iterations from STDIN for you to play around with. To test the full program, you'll need the Java interpreter.

BCT is a minimalist variant of Cyclic Tag Systems. A program is defined by two binary strings: a (cyclic) list of instructions and an initial state. To make my life easier when printing the programs, I have defined my own notation: each of the strings is given as a CJam-style array of integers, and the entire program is surrounded in `[[...]]`, e.g.

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

```

I'm also disallowing empty initial states or empty instruction lists.

Instructions in BCT are interpreted as follows:

* If the instruction is `0`, remove the leading bit from the current state.
* If the instruction is `1`, read another bit off the instruction list, call that `X`. If the leading bit from the current state is `1`, append `X` to the current state, otherwise do nothing.

If the current state ever becomes empty, the program halts.

The first few halting programs are

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

```

If you want to see more, check out the version in the online interpreter I linked above.

## Explanation

Here is how the code works. To keep track of the dovetailing we will always have an array on the stack which contains all the programs. Each program is pair of an internal representation of the program code (like `[[0 1 0] [1 0]]`) as well as the current state of the program. We'll only use the latter to do the computation, but we'll need to remember the former to print the program once it halts. This list of programs is simply initialised to an empty array with `L`.

The rest of the code is an infinite loop `{...1}g` which first adds one or more programs to this list and the computes one step on each program. Programs that halt are printed and removed from the list.

I'm enumerating the programs by counting up a binary number. The leading digit is stripped off to ensure that we can get all programs with leading 0s as well. For each such truncated binary representation, I push one program for each possible splitting between instructions and initial state. E.g. if the counter is currently at `42`, its binary representation is `101010`. We get rid of leading `1` and push all non-empty splittings:

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

```

Since we don't want empty instructions or states, we start the counter at 4, which gives `[[[0] [0]]]`. This enumeration is done by the following code:

```
Z):Z    e# Push Z (initially 3), increment, and store in Z.
2b1>    e# Convert to base 2, remove initial digit.
_,      e# Duplicate and get the number of bits N.
,1>     e# Turn into a range [1 .. N-1].
\       e# Swap the range and the bit list.
f{      e# Map this block onto the range, copying in the bit list on each iteration.
  /     e#   Split the bit list by the current value of the range.
  (     e#   Slice off the first segment from the split.
  [
    \:~ e#   Swap with the other segments and flatten those.
  ]     e#   Collect both parts in an array.
  a2*   e#   Make an array that contains the program twice, as the initial state is the
        e#   same as the program itself.
}
+       e# Add all of these new programs to our list on the stack.

```

The rest of the code maps a block onto the list of programs, which performs one step of the BCT computation on the second half of these pairs and removes the program if it halts:

```
)~     e# Remove the second half of the pair and unwrap it.
[      e# We need this to wrap the instructions and current state back in an array
       e# again later.
\(     e# Bring the instruction list to the top and remove the leading bit.
{      e# If it's a 1...
  1+   e#   Append a 1 again (the instructions are cyclic).
  (:X+ e#   Remove the next bit, store it in X and also append it again.
  \_0= e#   Bring the current state to the top, get its first bit.
  Xa*+ e#   Append X if that bit was 1 or nothing otherwise.
}{     e# Else (if it's a 0...)
  0+   e#   Append a 0 again (the instructions are cyclic).
  \1>  e#   Discard the leading bit from the current state.
}?
_      e# Duplicate the current state.
{      e# If it's non-empty...
  ]a+  e#   Wrap instructions and state in an array and add them to the program
       e#   pair again.
}{     e# Else (if it's empty)...
  ];p  e# Discard the instructions and the current state and print the program.
}?

```
> 12 votes

# Answer
# subleq OISC in Python, ~~317~~ 269 bytes

```
import collections
g=0
P={}
while 1:
    P[g]=[[0],collections.defaultdict(int,enumerate(list(int(x)for x in reversed(str(g)))))]
    g+=1
    for o,[a,p]in P.items():
        i=a[0]
        p[i+p[i+1]]-=p[i+p[i]]
        if p[i+p[i+1]]<=0:a[0]+=p[i+2]
        else:a[0]+=3
        if a[0]<0:print o;del P[o]

```

https://esolangs.org/wiki/Subleq

A subleq program is an extensible list of integers (p) and an instruction pointer (i). This subleq variant uses relative addressing, which the wiki talk page suggests is required for turing completeness with bounded values. Each tick, the operation `p[i+p[i+1]]-=p[i+p[i]]` is performed, and then `i+=p[i+2]` if the operation result was \<=0, otherwise `i+=3`. If i is ever negative, the program halts.

This implementation tests every program whose initial state is comprised of one-digit non-negative integers (0-9) with an initial instruction pointer of 0.

```
Output:
21 (which represents the program [1 2 0 0 0 0 0...]
121
161
221
271
351
352
461
462
571
572
681
682
791
792

```

The output is reversed, for golfing reasons. The spec above could be restated in reverse, but then would not match the code used in the implementation, so I've not described it that way.

EDIT: The first program that exhibits simple unbounded growth is 14283, which decrements the value at memory location 6 and writes an explicit 0 (as opposed to the implicit 0 in every cell) to the next negative cell, every three ticks.
> 10 votes

# Answer
# BrachylogPost correspondence problem, 10 bytes

```
≜;?{~c}ᵐ\d

```

Try it online!

Function which is a generator that generates all possible Post correspondence problems for which brute-forcing solutions eventually halts. (Brute-forcing solutions to the Post correspondence problem is known to be a Turing-complete operation.) The TIO link contains a header that converts a generator to a full program, and prints each output immediately as it's generated (thus, when TIO kills the program due to consuming more than 60 seconds of execution time, the output produced so far is visible).

This uses a formulation of the problem in which the strings are given as strings of digits, leading zeroes are not permitted except for `0` itself, solutions to the problem involving leading zeroes are not accepted, and a string of digits can be represented as either the number, or minus the number. Clearly, none of this has any impact on the Turing-completeness of the language (because there's no need for a Post correspondence problem to use the digit zero at all).

This program works via generating all possible solutions to problems, then working backwards to find the original programs that are solved by them. As such, an individual program can be output many times. It's unclear whether this invalidates the answer or not; note that all halting programs will eventually be output at least once (in fact, infinitely many times, as any program which has solutions has infinitely many solutions), and non-halting programs will never be output.

## Explanation

```
≜;?{~c}ᵐ\d
≜           Brute-force all numbers:
 ;?           Pair {the number} with {itself}
   {  }ᵐ      For each pair element:
    ~c          Brute-force a partition of that element into substrings
        \     such that the two elements each have the same number of substrings
        \     and group together corresponding substrings
         d    and remove duplicated pairs {to produce a possible output}

```
> 8 votes

# Answer
# SK combinator calculus in Haskell, 249 bytes

```
data C=H|S|K|C:$C deriving(Eq,Show)
n(a:$b)=m a*n b
n a=m a
m S=1
m K=1
m(S:$a)=n a
m _=0
f H=[S,K,S:$H,K:$H,S:$H:$H]
f a=[S:$b:$c:$d|b:$d:$(c:$e)<-[a],d==e,n b*n c*n d>0]++[K:$a:$H|n a>0]++do b:$c<-[a];[d:$c|d<-f b]++[b:$d|n b>0,d<-f c]
l=H:(f=<<l)

```

Try it online!

### How it works

The call-by-value evaluation rules for the SK combinator calculus are as follows:

(a) S*xyz**xz*(*yz*), for *x*, *y*, *z* in normal form;
(b) K*xy**x*, for *x*, *y* in normal form;
(c) *xy**x**y*, if *x**x*′;
(d) *xy**xy*′, for *x* in normal form, if *y**y′*.

Since we are only interested in halting behavior, we expand the language slightly by introducing a symbol H that is not in normal form, but to which all normal forms “evaluate”:

(a) S*xyz**xz*(*yz*), for *x*, *y*, *z* in normal form;
(b′) K*x*H ↦ *x*, for *x* in normal form;
(c) *xy**x**y*, if *x**x*′;
(d) *xy**xy*′, for *x* in normal form, if *y**y′*;
(e) S ↦ H;
(f) K ↦ H;
(g) SH ↦ H;
(h) KH ↦ H;
(i) SHH ↦ H.

We consider any application H*x* to be a run-time error to be treated as if it were an infinite loop, and we order evaluations such that no H is produced by (e)–(i) except in a context where it will be ignored (top level, any K*x*☐, any ignored K☐, any ignored S*x*☐ for *x* in normal form, any ignored S☐H). This way we do not affect the halting behavior of the usual terms lacking H.

The benefits of these modified rules are that every normalizable term has a unique evaluation path to H, and that every term has a finite number of possible preimages under ↦. So instead of using the dovetailing approach, we can do a much more efficient breadth-first search of all reverse evaluation paths from H.

`n` checks whether a term is in normal form, `f` finds all possible preimages of a term, and `l` is a lazy infinite list of normalizable terms produced by breadth-first search from H.
> 7 votes

# Answer
# slashes in Python, ~~640~~ 498 bytes

```
g=2
P={}
while 1:
    b=bin(g)[3:]
    P[b]=[[0],['',''],[b]]
    g+=1
    for d,[a,b,c]in P.items():
        s=c[0]
        if a[0]:
            if s.count(b[0]):s=s.replace(b[0],b[1],1)
            else:a[0]=0
        else:
            if s[0]=='0':
                if len(s)==1:del P[d];continue
                s=s[2:]
            else:
                b[0]=b[1]=''
                a[0]=1
                t=p=0
                while t<2:
                    p+=1
                    if p>=len(s):break
                    if s[p]=='0':
                        if p+1>=len(s):break
                        b[t]+=s[p+1]
                        p+=1
                    else:t+=1
                if t<2:del P[d];continue
        c[0]=s
        if len(s)==0:print d;del P[d]

```

https://esolangs.org/wiki////

A slashes program is a string, in this interpreter limited to the characters '/' and '\\'. In this implementation, / is '1' and \ is '0' to allow for some golfing with the use of python's bin(x). When the interpreter encounters a \\, the next character is output and both characters are removed. When it encounters a /, it looks for search and replace patterns as /search/replace/ including escaped characters within the patterns (\\ represents \ and \\/ represents /). That replace operation is then performed on the string repeatedly until the search string is no longer present, then interpretation continues from the beginning again. The program halts when it is empty. A program will be killed if there is an unclosed set of /patterns or a \ with no character after it.

```
Example output and explanations:
01 outputs '1' and halts
00 outputs '0' and halts
0101 outputs '11' and halts
0100 ...
0001
0000
010101
010100
010001
010000 ...
101110 replaces '1' with '', leaving '00', which outputs '0' and halts

```
> 6 votes

# Answer
# Treehugger in Java, ~~1,299~~ ~~1,257~~ ~~1,251~~ ~~1,207~~ ~~1,203~~ ~~1,201~~ ~~1,193~~ ~~1,189~~ 934 bytes

```
import java.util.*;class M{static class N{N l,r;byte v;}static class T extends Stack<N>{{push(new N());}int i,h;char[]s;}static void s(T t){if(t.i<t.s.length){int i=1,c=94-t.s[t.i],C;N P=t.peek(),T=c>33?P.l:P.r,S=new N();if(c==34|c==32)t.push(T==null?c>33?P.l=S:(P.r=S):T);if(c==0)do t.pop();while(t.size()<1);if(c==3&(P.v+=c<52&c>48?50-c:0)==0|c==1&P.v!=0)for(;i>0;i-=C*C<2?C:0)C=t.s[t.i+=c-2]-92;else++t.i;}else t.h=1;}static char[]n(char[]a){var b="<^>[+-]";int q=a.length,i=q,j;for(;i-->0;a[i]=60)if((j=b.indexOf(a[i]))<6){a[i]=b.charAt(j+1);return a;}a=Arrays.copyOf(a,q+1);a[q]=60;return a;}public static void main(String[]a){var z=new ArrayList<T>();for(char[]c={};;){T t=new T();if(b(t.s=c))z.add(t);c=n(c.clone());for(T u:z)try{s(u);if(u.h>0){z.remove(u);System.out.println(u.s);break;}}catch(Exception e){z.remove(u);break;}}}static boolean b(char[]c){int i=0;for(var d:c)if((i+=d>90&d<94?92-d:0)<0)return 0>0;return i==0;}}

```

Thanks to ceilingcat for saving ~250 bytes
> 6 votes

# Answer
## "Purple without I/O" in Ceylon, 662

```
import ceylon.language{l=variable,I=Integer,m=map,S=String}class M(S d){l value t=m{*d*.hash.indexed};l I a=0;l I b=0;l I i=0;I g(I j)=>t[j]else 0;value f=m{97->{a},98->{b},65->{g(a)},66->{g(b)},105->{i},49->{1}};value s=m{97->((I v)=>a=v),98->((I v)=>b=v),65->((I v)=>t=m{a->v,*t}),66->((I v)=>t=m{b->v,*t}),105->((I v)=>i=v)};I&I(I)x{throw Exception(d);}I h(I v)=>f[v]?.first else x;shared void p(){(s[g(i)]else x)(h(g(i+1))-h(g(i+2)));i+=3;}}shared void run(){value a='!'..'~';{S*}s=expand(loop<{S*}>{""}((g)=>{for(c in a)for(p in g)p+"``c``"}));l{M*}r={};for(p in s){r=[M(p),*r];for(e in r){try{e.p();}catch(x){print(x.message);r=r.filter(not(e.equals));}}}}

```

Purple is a self-modifying one-instruction language which was asked to interpret here. As input and output are not relevant for this task, I removed the `o` symbol's meaning from the interpreter, such that the (potentially) valid symbols are just `a`, `b`, `A`, `B`, `i` and `1` (the last one just for reading, not for writing).

But as Purple is self-modifying (and using its source code as data), potentially also programs containing other than those characters are useful, so I **opted to allow all printable (non-whitespace) ASCII characters in the code (other ones might be useful as well, but are not as easily printed).**

(You can modify the interpreter to instead take as string of allowed characters as a command line argument – switch the commented line defining `a` below. Then the length becomes 686 bytes.)

My "parallel" interpreter thus creates all finite strings from those characters (in increasing length and lexicographical order) and tries each of them.

Purple will halt without error whenever the command to be read from the tape for execution is not valid – thus there are no invalid programs and many, many halting ones. (Most halt even at the first step, only some of the programs with length 3 come to the second step (and will halt then), the first non-halting ones have length 6.

I think the very first non-halting program in the order tried by my interpreter is `aaaiaa`, which in the first step sets the `a` register to 0 (which it already was), and the second and every following step sets the instruction pointer back to 0, causing it to execute `iaa` again.

I reused part of the code written for my interpreter of "standard" Purple, but due to the removal of input and output, my parallel interpreter becomes even slightly shorter than that, while including the additional logic for executing multiple programs at once.

Here is a commented and formatted version:

```
// Find (enumerate) all halting programs in (a non-I/O subset of) Purple.
//
// Question:  https://codegolf.stackexchange.com/q/51273/2338
// My answer: https://codegolf.stackexchange.com/a/65820/2338

// We use a turing-complete subset of the Purple language,
// with input and output (i.e. the `o` command) removed.

import ceylon.language {
    l=variable,
    I=Integer,
    m=map,
    S=String
}

// an interpreting machine.
class M(S d) {
    // The memory tape, as a Map<Integer, Integer>.
    // We can't modify the map itself, but we
    // can replace it by a new map when update is needed.
    l value t = m {
        // It is initialized with the code converted to Integers.
        // We use `.hash` instead of `.integer` because it is shorter.
        *d*.hash.indexed
    };

    // three registers
    l I a = 0;
    l I b = 0;
    l I i = 0;

    // get value from memory
    I g(I j) =>
            t[j] else 0;

    // Map of "functions" for fetching values.
    // We wrap the values in iterable constructors for lazy evaluation
    //  – this is shorter than using (() => ...).
    // The keys are the (Unicode/ASCII) code points of the mapped
    // source code characters.
    value f = m {
        // a
        97 -> { a },
        // b
        98 -> { b },
        // A
        65 -> { g(a) },
        // B
        66 -> { g(b) },
        // i
        105 -> { i },
        // 1
        49 -> { 1 }
    };

    // Map of functions for "storing" results.
    // The values are void functions taking an Integer,
    // the keys are the ASCII/Unicode code points of the corresponding
    // source code characters.
    value s = m {
        // a
        97 -> ((I v) => a = v),
        // b
        98 -> ((I v) => b = v),
        // Modification of the memory works by replacing the map with
        // a new one.
        // This is certainly not runtime-efficient, but shorter than
        // importing ceylon.collections.HashMap.
        // A
        65 -> ((I v) => t = m { a->v, *t }),
        // B
        66 -> ((I v) => t = m { b->v, *t }),
        // i
        105 -> ((I v) => i = v)
    };

    // Exit the interpretation, throwing an exception with the machine's
    // source code as the message.  The return type is effectively `Nothing`,
    // but shorter (and fits the usages).
    I&I(I) x {
        throw Exception(d);
    }

    // accessor function for the f map
    I h(I v) =>
            f[v]?.first else x;

    // a single step
    shared void p() {
        (s[g(i)] else x)(h(g(i + 1)) - h(g(i + 2)));
        i += 3;
    }
}

// the main entry point
shared void run() {
    // the alphabet of "Purple without I/O".
    value a = '!'..'~';
    //// possible alternative to use a command line argument:
    // value a = process.arguments[0] else '!'..'~';

    // an iterable consisting of all programs in length + lexicographic order
    {S*} s =
            // `expand` creates a single iterable (of strings, in this case)
            // from an iterable of iterables (of strings).
             expand(
        // `loop` creates an iterable by applying the given function
        // on the previous item, repeatedly.
        // So here we start with the iterable of length-zero strings,
        // and in each iteration create an iterable of length `n+1` strings
        // by concatenating the length `n` strings with the alphabet members.
        loop<{S*}>{ "" }((g) =>
                {
                    for (c in a)
                        for (p in g)
                            p + "``c``"
                }));

    // This is a (variable) iterable of currently running machines.
    // Initially empty.
    l {M*} r = {};

    // iterate over all programs ...
    for(p in s) {
        // Create a machine with program `p`, include it
        //  in the list of running machines.
        //
        // We use a sequence constructor here instead of
        //  an iterable one (i.e. `r = {M(p, *r)}` to prevent
        // a stack overflow when accessing the deeply nested
        // lazy iterable.
        r = [M(p), *r];
        // iterate over all running machines ...
        for(e in r) {
            try {
                // run a step in machine e.
                e.p();
            } catch(x) {
                // exception means the machine halted.
                // print the program
                print(x.message);
                // remove the machine from the list for further execution
                r = r.filter(not(e.equals));
            }
        }
        // print(r.last);
    }
}

```
> 4 votes

---
Tags: code-golf, interpreter
---


title: Get me back down to 1 rep!

text:
# Question
Title: Get me back down to 1 rep!
# This is not an invitation for you to downvote everything I've posted. Just sayin' ;)

# Challenge

Figure out how I can get myself back down to 1 reputation.

Details will follow input format, then followed by output.

# Input

Input will consist of the my current reputation, the number of questions I have posted with an accepted answer (that is not my own), the number of questions I have posted without an accepted answer that have a valid answer that is not my own, and the number of answer downvotes that I have cast.

# Details

Accepting an answer that is not my own gives me 2 rep. Unaccepting an answer takes away 2 rep from me. Undownvoting an answer gives me 1 rep (we assume that all of my answer votes are not locked in at the moment), and downvoting an answer makes me lose 1 rep (we assume there are enough answers on PPCG for me to not care about the number of answers that I can downvote). We also ignore potential serial vote reversal. Most of my reputation is going to have to be given away by bounties because I don't want to go around downvoting 5000 answers.

The challenge is to find the shortest way to get me back down to 1 rep using the shortest code. Please keep in mind that I need at least 125 rep to downvote and at least 75 rep to start a bounty. By "shortest way", I mean the way requiring the least actions, where each accept and downvote and their reverse actions and each bounty is a separate action. Note that it is impossible to award a bounty of more than +500 rep at once. Also note that you can only give out bounties in 50 rep increments.

If there is no way to get back down to 1 rep, then output some consistent error message. The error message may be output through crashing.

# Output

Output the number of undownvotes, downvotes, accept-votes, unaccept-votes, and bounty actions I need to perform in any consistent order in any reasonable list format.

# Test Cases

```
reputation, accepted_answers, no_accept_questions, answer_downvotes -> accepts, unaccepts, downvotes, undownvotes, bounties

101, 3, 2, 10 -> 0, 0, 0, 0, 1 // This one's easy, just give out a 100 rep bounty.
102, 3, 2, 10 -> 0, 1, 0, 1, 1 // Unaccept to get to 100, then undownvote to get to 101, then give a +100 bounty
103, 3, 2, 10 -> 0, 1, 0, 0, 1 // First unaccept one of those answers and then give out a 100 rep bounty or vice versa
3, 1, 0, 0 -> 0, 1, 0, 0, 0 // Unaccept that answer and lose the 2 rep
1000, 0, 1, 0 -> 1, 0, 1, 0, 2 // Accept an answer to get to 1002, then downvote an answer to get to 1001, then give out two +500 bounties

```

# Rules

* Standard Loopholes Apply
* "Post a bunch of spam and get suspended" is not an answer, nor is anything similar
* In the case of a tie between shortest methods, output one possible shortest method
* This is , so the shortest code in bytes wins!

# Answer
> 3 votes
## Mathematica, 302 bytes

Golfed version:

```
Unprotect@Null;Null=0;f[1,_,_,_]={,,,,};f[r_,a_,n_,d_]:=(f[r,a,n,d]=l={∞,,,,};f[r,a,n,d]=#&@@MinimalBy[{If[r>74,{,,,,1}+f[r-50Min[⌈r/50⌉-1,10],a,n,d],l],If[r>124,{,,1,,}+f[r-1,a,n,d+1],l],If[d>0,{,,,1,}+f[r+1,a,n,d-1],l],If[a>0,{,1,,,}+f[r-2,a-1,n+1,d],l],If[n>0,{1,,,,}+f[r+2,a+1,n-1,d],l]},Tr])

```

Normal version:

```
Unprotect@Null; Null = 0;
f[1, _, _, _] = {, , , ,};
l = {\[Infinity], , , ,};
f[r_, a_, n_, d_] := (
  f[r, a, n, d] = l;
  f[r, a, n, d] = # & @@ MinimalBy[{
      If[r > 74, {, , , , 1} +
        f[r - 50 Min[\[LeftCeiling]r/50\[RightCeiling] - 1, 10], a, n,
          d], l],
      If[r > 124, {, , 1, ,} + f[r - 1, a, n, d + 1], l],(*
      downvote one more *)
      If[d > 0, {, , , 1,} + f[r + 1, a, n, d - 1], l],
      (* un-downvote *)
      If[a > 0, {, 1, , ,} + f[r - 2, a - 1, n + 1, d], l],
      (* un-accept. -2 rep *)
      If[n > 0, {1, , , ,} + f[r + 2, a + 1, n - 1, d], l]
      (* accept. +2 rep *)
      }, Tr]
  )

```

Note:

1. Test this on https://sandbox.open.wolframcloud.com/ \- paste the code, press `Shift+Enter`, then enter `f[101,3,2,10]` for example for first test case, then press `Shift+Enter`.
2. Use `Block[{Null=0}, ...]` can save some bytes, but I haven't test that.
3. Sometimes `$IterationLimit=$RecursionLimit=∞` is necessary to get correct result.
4. The function will return `{∞,0,0,0,0}` or similar (that is, the sum of elements in list is infinite) when it is impossible, and a list with format similar to that in the sample output when it is possible.

---
Tags: code-golf
---


title: The dot is chasing me!

text:
# Question
Title: The dot is chasing me!
## Your Task

Write a program that displays a dot that moves toward the position of your mouse at 4 pixels per second. The dot must be 100 pixels big and the window must fill the computer screen.

## Input

None

## Output

A window showing an animated dot moving towards the mouse at a fixed, non-changing speed.

## Scoring

This is , so the shortest code in bytes wins.

# Answer
# Mathematica, 89 bytes

```
Graphics[Disk[Dynamic[MousePosition["Graphics",{0,0}]],.1],PlotRange->10,ImageSize->1000]

```
> 3 votes

# Answer
# HTML + JavaScript, 140 bytes

Infinite speed

```
t=c.getContext`2d`
c.onmousemove=e=>(x=e.clientX,y=e.clientY)
setInterval(_=>t.clearRect(0,0,1e5,1e5)||t.fillRect(x,y,10,10),9)
```

```
<canvas id=c>
```

Non-cheaty, 188 bytes

```
x=y=0,t=c.getContext`2d`
c.onmousemove=e=>(z=e.pageX,w=e.pageY)
f=_=>t.clearRect(0,0,1e5,1e5)||(m=((a=z-x)**2+(b=w-y)**2)**.5)|t.fillRect(x+=a/m,y+=b/m,10,10)
setInterval(f,9)
```

```
<canvas id=c>
```

Larger and faster:

```
x=y=0,s=3,t=c.getContext`2d`
c.onmousemove=e=>(z=e.pageX,w=e.pageY)
f=_=>t.clearRect(0,0,1e5,1e5)||(m=((a=z-x)**2+(b=w-y)**2)**.5)|t.fillRect(x+=s*a/m,y+=s*b/m,10,10)
setInterval(f,9)
```

```
<canvas id=c height=999 width=999>
```
> 5 votes

# Answer
## Python 3 + Tkinter, 264 262 259 254 bytes

```
import tkinter as t,numpy as n
f=t.Tk()
p=n.array([1,1])
q=n.array([0.]*2)
c=t.Canvas(f)
c.pack()
def s(e):p[:]=e.x,e.y
c.bind("<Motion>",s)
z=c.create_oval(0,0,2,2)
def r():d=p-q;u=(d*d.T+.1)**-0.5;c.move(z,*u*d);q[:]+=u*d;c.after(9,r)
r()
f.mainloop()

```

Thanks to @Gryphon for saving 2 bytes, to @Jonathan Allan for another one, and to @Challenger5 for five. Changed `1e-9` to `.1` for another two.
> 5 votes

# Answer
# Python 2 + Pygame, 178 Bytes

-2 bytes thanks to @ASCII-only, because I was being an idiot

-12 bytes thanks to @officialaimm, also because I was being an idiot

-11 bytes thanks to @JonathanAllan, for telling me the default window size was the screen size

-2 bytes thanks to @WheatWizard, also because I was being an idiot

-18 bytes thanks to @nore, because I didn't have to use the if/else statements

-24 bytes thanks to @nore, who reminded me to put the whole loop on one line.

-42 bytes thanks to @WheatWizard

-3 bytes thanks to @ASCII-only

```
from pygame.locals import*
from pygame import*
init()
a=display.set_mode()
b=c=0
while 1:a.fill((0,0,0));x,y=mouse.get_pos();draw.rect(a,(9,9,9),
(b,c,b+10,c+10));display.update()

```

This is definitely no longer the best way to do this, so I may come out with a version that's better suited to the new requirements of the question. The dot is 10 pixels by 10 pixels. The screen size is the size of the computer screen. If you can see the dot, I'm impressed, as it is almost the exact same colour as the background, to save on byte counts for RGB colours.
> 3 votes

---
Tags: code-golf, animation
---


title: Pad a file with zeros

text:
# Question
Title: Pad a file with zeros
Your task today will be to take an existing file and append zeros to it until it reaches a certain size.

You must write a program or function which takes the name of a file in the current directory `f` and a number of bytes `b`. While maintaining the original content of `f`, you must write zeroes ***(null bytes, not ascii 0s)*** to the end so that its new size is `b` bytes.

You may assume that `f` only has alphanumeric ascii in its name, that you have full permissions over it, that it initially is not larger than `b`, but may be as large as `b`, and that there is infinite free disk space.

You may not assume `f` is nonempty, or that it does not already contain null bytes.

Other existing files should not be modified and new files should not exist after execution ends.

## Test Cases

```
Contents of f | b  | Resulting contents of f
12345         | 10 | 1234500000
0             | 3  | 000
[empty]       | 2  | 00
[empty]       | 0  | [empty]
123           | 3  | 123

```

# Answer
> 20 votes
# Bash + coreutils, 13

```
truncate -s$@

```

Input from the command-line - the first parameter is the file size and the second is the filename.

From `man truncate`:

> If a FILE is shorter, it is extended and the extended part (hole) reads as zero bytes.

Try it online.

# Answer
> 4 votes
# Groovy, ~~54~~ ~~47~~ ~~43~~ 41 bytes

```
{a,b->(c=new File(a))<<'\0'*(b-c.size())}

```

*-6 thanks to manatwork's idea of removing the loop; that was my original idea, don't know why I thought it wouldn't work and opted for a loop... It definitely works, just tested it.*

# Ungolfed:

```
{
    a,b->                    // Two inputs: a is the File name, b is the desired size.
    File c = new File(a)     // Make and store the file.
    c << '\0'*(b-c.size())   // Append the difference between b and c.size() in nullbytes.
}
                             // Usually a close would be required, but, in Groovy,
                             // because private data isn't so protected, if a File
                             // Object goes out of scope, the attached Stream is
                             // automatically flushed to disk.

```

# Answer
> 3 votes
# APL (Dyalog), ~~33~~ 17 bytes

```
⎕⎕NRESIZE⍞⎕NTIE¯1

```

Try it online!

# Answer
> 3 votes
# Python 2, ~~59~~ ~~57~~ 54 bytes

<sup>-5 bytes thanks to chepner</sup>

```
def g(n,b):f=open(n,'a');f.write('\0'*b);f.truncate(b)

```

# Answer
> 3 votes
# PHP, 66 bytes

```
for($p=fopen($f=$argv[1],a);filesize($f)<$argv[2];)fputs($p,"\0");

```

Takes input from command line arguments; run with `-nr`.

---

These 55 bytes might, but most probably will not, work:

```
fseek($p=fopen($argv[1],"w+"),$argv[2]);fputs($p,"\0");

```

# Answer
> 2 votes
# Java (Oracle JRE), 55 bytes

```
f->b->new java.io.RandomAccessFile(f,"rw").setLength(b)

```

The spec of `setLength(int)` says that the appended bytes are undefined, but practically the Oracle JRE appends only the `0` byte (that's why I specified it).

The resource is automatically closed by the JVM so we don't need to do it ourself.

## Test

```
public class Pcg125661 {
  interface F {
    B f(String f);
  }
  interface B {
    void b(int b) throws java.io.IOException;
  }
  public static void main(String[] args) throws java.io.IOException {
    F a = f->b->new java.io.RandomAccessFile(f,"rw").setLength(b);
    a.f("a").b(100);
  }
}

```

# Answer
> 1 votes
# AHK, 48 bytes

```
FileGetSize,s,%1%
2-=s
Loop,%2%
FileAppend,0,%1%

```

`1` and `2` are the first two parameters in an AHK script.
`FileGetSize` works in bytes by default.
It's not exciting, but it's simple: Get the size, subtract it from the desired size, and add that many zeroes.

# Answer
> 1 votes
# Perl 6, 40 bytes

```
{$_=$^a.IO;.open(:a).put("\0"x($^b-.s))}

```

`$^a` and `$^b` are the parameters to the function--the file name and the length, respectively.

# Answer
> 1 votes
# Python 2, 68 bytes

```
def g(f,b):
 with open(f,'r+')as c:c.write('\x00'*(b-len(c.read())))

```

Try it online! (When printing the file's content, the code replaces null bytes with ASCII 0's for visibility.)

# Answer
> 1 votes
## PowerShell, 69 bytes

```
param($f,$s)@(gc $f -en by)+,[byte]0*($s-(gi $f).length)|sc $f -en by
#     ^ filename
#        ^desired size
#                 ^ get content as byte stream
#           ^force it to an array even if there's 0 or 1 byte
#                          ^append a byte array of nulls..
#                                       ^..desired size - file size
#                            write to file with -encoding byte ^

```

`$f` for the file, `$s` for the destination size, save as .ps1 and run

```
.\Add-NullBytesToFile.ps1 .\test.txt 10

```

---

It's a shell, so there should be a really small loop adding 1 byte with `>>` output redirection and append, right? Well, no, because `>>` only outputs UCS2-LE multibyte encoding so there's no way to add a single byte to a file with it .. unless you're using PSv5.1 and you can change that but that makes it too long to be competitive:

```
$PSDefaultParameterValues['Out-File:Encoding']='utf8';while((gi $f).length-lt$c){[byte]0>>$f}

```

Maybe there's a .Net Framework approach? There should be, but I can't make it actually write any bytes, or error. But it's longer anyway:

```
param($f,$s)[io.file]::WriteAllBytes($f,[byte[]](,0)*($c-(gi $f).length), $True)

```

# Answer
> 1 votes
## Mathematica 50 Bytes

Import/Export

```
Export[#,Import[#,c="Byte"]~Join~Table[0,{#2}],c]&

```

Usage

```
%["test1", 5]

```

# Answer
> 1 votes
# C, 56 bytes

```
fseek(f,0,2);int i;for(;ftell(f)<b;)putc(0,f);fclose(f);

```

The program finds the file's size, and how many bytes to append. The file then adds `fs - b` extra bytes to the end.

# Answer
> 1 votes
# q, 29 bytes

Function which takes file name in format `:/foo/bar.baz` and length as an integer.

```
{hopen[x](0|y-hcount x)#0x00}

```

Example:

```
{hopen[x](0|y-hcount x)#0x00}[`:test.txt;100]

```

# Answer
> 1 votes
# C#, 90 bytes

```
using System.IO;s=>n=>File.AppendAllText(s,new string('\0',(int)new FileInfo(s).Length-n))

```

---
Tags: code-golf, file-system
---


# Question
Title: How many carries do I need to add these two numbers?
## Task

Given two positive integers, output the number of carries needed to add them together in long addition in base 10.

## Examples

```
¹¹¹   <-- carries
 999
+  1
----
1000

```

Three carries are needed.

```
 ¹
 348
+ 91
----
 439

```

One carry is needed.

## Testcases

```
999,   1 -> 3
398,  91 -> 1
348,  51 -> 0
348,  52 -> 2
  5,  15 -> 1
999, 999 -> 3
505, 505 -> 2

```

## Scoring

This is . Shortest answer in bytes wins. Standard loopholes apply.

# Answer
# Mathematica, ~~46~~ 39 bytes

```
x=Tr@*IntegerDigits;(x@#+x@#2-x@+##)/9&

```

**input**

> \[348,51\]

*-7 bytes from JungHwan*
> 21 votes

# Answer
# JavaScript (ES6), 50 bytes

~~Fixed~~ Stolen from ovs' solution

```
f=(a,b,c=0)=>a|b|c&&c+f(a/10,b/10,a%10+b%10+c>=10)

```

### Explanation

```
f=(a,b,c=0)=>                                      Function taking two numbers and optional carry
             a|b|c                                 If a number or the carry are nonzero
                  &&                               Then
                    c+f(a/10,b/10,a%10+b%10+c>=10) Return carry plus all other carries

```

### Carry explanation

```
a%10+b%10+c     Sum of mod 10 of the numbers and c - remember these are not floordiv'ed
           >=10 Greater than or equals to 10 (we can't use greater than 9 here)

```

```
f=(a,b,c=0)=>a|b|c&&c+f(a/10,b/10,a%10+b%10+c>=10)
console.log([[999,1],[398,91],[348,51],[348,52],[5,15],[999,999],[256,64],[190192,90909]].map(test=>`${(test[0]+'').padStart(6,' ')}, ${(test[1]+'').padStart(6,' ')} -> ${f(...test)}`).join('\n'));
```
> 6 votes

# Answer
# C (gcc), 65 bytes

```
i,l;f(a,b){for(i=l=0;a+b;a/=10,b/=10)i+=a%10+b%10+l>9?l=1:0;a=i;}

```

Try it online!
> 5 votes

# Answer
# Jelly,  ~~13 12 11~~  9 bytes

-1 byte by porting Jenny\_mathy's Mathematic answer.
-2 more bytes by better golfing :p

```
;SN$DFS:9

```

**See the test suite**.

### How?

```
;SN$DFS:9 - Main link: list of numbers, [a,b]     e.g.   [348,53]
   $      - last two links as a monad
 S        -   sum                                            401
  N       -   negate                                        -401
;         - concatenate                             [348,53,-401]
    D     - convert to decimal lists     [[3,4,8],[5,3],[-4,0,-1]]
     F    - flatten                           [3,4,8,5,3,-4,0,-1]
      S   - sum                                               18
       :9 - integer divide by nine                             2

```

---

My 12 byte solution...

```
:⁵+
DUSç\>9S

```

A monadic link taking a pair of integers and returning the number of carries as an integer.

~~*There is probably a shorter way though!*~~ There was!

**Try it online!** or see the test suite.

### How

```
:⁵+ · Link 1: perform a carry: right-column's-digit-sum, a; left-colum's-digit-sum; b
 ⁵  · literal 10
:   · a integer-divided by 10 - the carry amount
  + · add to b

DUSç\>9S · Main link: list of summands        e.g. [348,52]
D        · convert to decimal lists                [[3,4,8],[5,2]]
 U       · upend (reverse each)                    [[8,4,3],[2,5]]
  S      · sum (add the digits up)                 [10,9,3]
    \    · cumulative reduce with:
   ç     ·   last link (1) as a dyad               [10,10,4]
      9  · literal 9
     >   · greater than?                           [ 1, 1,0]
       S · sum                                     2

```
> 5 votes

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

```
f=(a,b,d=1)=>a+b<d?0:(a%d+b%d>=d)+f(a,b,d*10)

```

Saved 1 byte by adding an extra do-nothing iteration for carries into 1's place. Saved 7 bytes by appropriating @xnor's carry check. I also had a more elegant 45-byte version but it suffers from floating-point inaccuracy; it would work great translated to a language with exact decimal arithmetic:

```
f=(a,b,c=a+b)=>c<1?0:a%1+b%1-c%1+f(a/10,b/10)

```
> 4 votes

# Answer
# Python, 48 bytes

```
f=lambda a,b,m=1:m<1e99and(~a%m<b%m)+f(a,b,m*10)

```

Try it online!

For each place value `m=1, 10, 100, ..., 10**99`, checks if there is a carry at that place value. The overflow check `a%m+b%m>=m` is shortened to `~a%m<b%m`.

A nicer 45-byte variant where floats `a` and `b` shifted down instead

```
f=lambda a,b:a+b and(a%1+b%1>=1)+f(a/10,b/10)

```

sadly runs into float precision issues.
> 4 votes

# Answer
# Python 2, 55 bytes

```
f=lambda a,b,c=0:c+a+b and c+f(a/10,b/10,a%10+b%10+c>9)

```

Try it online!
> 3 votes

# Answer
# 05AB1E, ~~11~~ 10 bytes

```
|DO‚€SOÆ9÷

```

Try it online!
> 2 votes

# Answer
# Neim, 10 bytes

```
₁₂λ

```

Explanation:

```
            ppend the two inputs into a list
             oin them together
             um the characters
   ₁₂         Push the first input, then the second
             Ad.
             um the characters
             ubtract
             Integer diision by
        λ     nine (variable)

```

Try it!

Alternative solution, also 10 bytes:

```
DS9

```

Explanation:

```
             ppend the two inputs into a list
 D            Duplicate
              oin
              um
    S          Swap
              um
              um the characters
              ubtract
              integer diide by
        λ       nine (variable)

```

Try it!
> 2 votes

# Answer
# PHP\>=7.1, 81 Bytes

```
for([,$x,$y]=$argv,$i=1;($x+$y)/$i|0;$i*=10)$d+=$c=$x/$i%10+$y/$i%10+$c>9;echo$d;

```

-2 Bytes removing `|0` In this case the loop runs until `$i` is `INF`

Test Cases
> 1 votes

# Answer
# Braingolf, 20 bytes

```
VR{.M}d<d&+v+d&+c-9/

```

Try it online!

Uses the same method as everyone else.

Could've saved a byte or 2 had I had the foresight to allow `d` to use the greedy modifier, then I could've replaced `d<d` with `&d` ah well, next time.

## Explanation

```
VR{.M}d<d&+v+d&+c-9/  Implicit input from commandline args
VR                    Create stack2 and return to stack1
  {..}                Foreach loop, runs on each item in stack1
   .M                 Duplicate and move duplicate to stack2
      d<d             Split both items on stack into digits
         &+           Sum entire stack
           v+         Switch to stack2 and sum last 2 items on stack
             d&+      Split result into digits and sum all digits
                c     Collapse stack2 into stack1
                 -    Subtract last item from 2nd to last
                  9/  Divide by 9
                      Implicit output of last item on stack

```
> 0 votes

---
Tags: code-golf, arithmetic
---


title: Finding approximate correlations

text:
# Question
Title: Finding approximate correlations
Consider a binary string `S` of length `n`. Indexing from `1`, we can compute the Hamming distances between `S[1..i+1]` and `S[n-i..n]` for all `i` in order from `0` to `n-1`. The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. For example,

```
S = 01010

```

gives

```
[0, 2, 0, 4, 0].

```

This is because `0` matches `0`, `01` has Hamming distance two to `10`, `010` matches `010`, `0101` has Hamming distance four to `1010` and finally `01010` matches itself.

We are only interested in outputs where the Hamming distance is at most 1, however. So in this task we will report a `Y` if the Hamming distance is at most one and an `N` otherwise. So in our example above we would get

```
[Y, N, Y, N, Y]

```

Define `f(n)` to be the number of distinct arrays of `Y`s and `N`s one gets when iterating over all `2^n` different possible bit strings `S` of length `n`.

## Task

For increasing `n` starting at `1`, your code should output `f(n)`.

## Example answers

For `n = 1..24`, the correct answers are:

```
1, 1, 2, 4, 6, 8, 14, 18, 27, 36, 52, 65, 93, 113, 150, 188, 241, 279, 377, 427, 540, 632, 768, 870

```

## Scoring

Your code should iterate up from `n = 1` giving the answer for each `n` in turn. I will time the entire run, killing it after two minutes.

Your score is the highest `n` you get to in that time.

In the case of a tie, the first answer wins.

## Where will my code be tested?

I will run your code on my (slightly old) Windows 7 laptop under cygwin. As a result, please give any assistance you can to help make this easy.

My laptop has 8GB of RAM and an Intel i7 5600U@2.6 GHz (Broadwell) CPU with 2 cores and 4 threads. The instruction set includes SSE4.2, AVX, AVX2, FMA3 and TSX.

## Leading entries per language

* **n = 40** in **Rust** using CryptoMiniSat, by Anders Kaseorg. (In Lubuntu guest VM under Vbox.)
* **n = 35** in **C++** using the BuDDy library, by Christian Seviers. (In Lubuntu guest VM under Vbox.)
* **n = 34** in **Clingo** by Anders Kaseorg. (In Lubuntu guest VM under Vbox.)
* **n = 31** in **Rust** by Anders Kaseorg.
* **n = 29** in **Clojure** by NikoNyrh.
* **n = 29** in **C** by bartavelle.
* **n = 27** in **Haskell** by bartavelle
* **n = 24** in **Pari/gp** by alephalpha.
* **n = 22** in **Python 2 + pypy** by me.
* **n = 21** in **Mathematica** by alephalpha. (Self reported)

---

# Future bounties

I will now give a bounty of 200 points for any answer that gets up to **n = 80** on my machine in two minutes.

# Answer
> 9 votes
# Rust + CryptoMiniSat, n ≈ 41

### `src/main.rs`

```
extern crate cryptominisat;
extern crate itertools;

use std::iter::once;
use cryptominisat::{Lbool, Lit, Solver};
use itertools::Itertools;

fn make_solver(n: usize) -> (Solver, Vec<Lit>) {
    let mut solver = Solver::new();
    let s: Vec<Lit> = (1..n).map(|_| solver.new_var()).collect();
    let d: Vec<Vec<Lit>> = (1..n - 1)
        .map(|k| {
                 (0..n - k)
                     .map(|i| (if i == 0 { s[k - 1] } else { solver.new_var() }))
                     .collect()
             })
        .collect();
    let a: Vec<Lit> = (1..n - 1).map(|_| solver.new_var()).collect();
    for k in 1..n - 1 {
        for i in 1..n - k {
            solver.add_xor_literal_clause(&[s[i - 1], s[k + i - 1], d[k - 1][i]], true);
        }
        for t in (0..n - k).combinations(2) {
            solver.add_clause(&t.iter()
                                   .map(|&i| d[k - 1][i])
                                   .chain(once(!a[k - 1]))
                                   .collect::<Vec<_>>()
                                   [..]);
        }
        for t in (0..n - k).combinations(n - k - 1) {
            solver.add_clause(&t.iter()
                                   .map(|&i| !d[k - 1][i])
                                   .chain(once(a[k - 1]))
                                   .collect::<Vec<_>>()
                                   [..]);
        }
    }
    (solver, a)
}

fn search(n: usize,
          solver: &mut Solver,
          a: &Vec<Lit>,
          assumptions: &mut Vec<Lit>,
          k: usize)
          -> usize {
    match solver.solve_with_assumptions(assumptions) {
        Lbool::True => search_sat(n, solver, a, assumptions, k),
        Lbool::False => 0,
        Lbool::Undef => panic!(),
    }
}

fn search_sat(n: usize,
              solver: &mut Solver,
              a: &Vec<Lit>,
              assumptions: &mut Vec<Lit>,
              k: usize)
              -> usize {
    if k >= n - 1 {
        1
    } else {
        let s = solver.is_true(a[k - 1]);
        assumptions.push(if s { a[k - 1] } else { !a[k - 1] });
        let c = search_sat(n, solver, a, assumptions, k + 1);
        assumptions.pop();
        assumptions.push(if s { !a[k - 1] } else { a[k - 1] });
        let c1 = search(n, solver, a, assumptions, k + 1);
        assumptions.pop();
        c + c1
    }
}

fn f(n: usize) -> usize {
    let (mut solver, proj) = make_solver(n);
    search(n, &mut solver, &proj, &mut vec![], 1)
}

fn main() {
    for n in 1.. {
        println!("{}: {}", n, f(n));
    }
}

```

### `Cargo.toml`

```
[package]
name = "correlations-cms"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
cryptominisat = "5.0.1"
itertools = "0.6.0"

```

### How it works

This does a recursive search through the tree of all partial assignments to prefixes of the Y/N array, using a SAT solver to check at each step whether the current partial assignment is consistent and prune the search if not. CryptoMiniSat is the right SAT solver for this job due to its special optimizations for XOR clauses.

The three families of constraints are

*S**i**S**k* \+ *i**D**ki*, for 1 ≤ *k**n* − 2, 0 ≤ i ≤ *n**k*;
*D**ki*1*D**ki*2 ∨ ¬*A**k*, for 1 ≤ *k**n* − 2, 0 ≤ *i*1 \< *i*2*n**k*;
¬*D**ki*1 ∨ ⋯ ∨ ¬*D**ki**n**k* − 1*A**k*, for 1 ≤ *k**n* − 2, 0 ≤ *i*1 \< ⋯ \< *i**n**k* − 1*n**k*;

except that, as an optimization, *S*0 is forced to false, so that *D**k*0 is simply equal to *S**k*.

# Answer
> 9 votes
# Rust, n ≈ ~~30 or~~ 31 or 32

On my laptop (two cores, i5-6200U), this gets through *n* = 1, …, 31 in 53 seconds, using about 2.5 GiB of memory, or through *n* = 1, …, 32 in 105 seconds, using about 5 GiB of memory. Compile with `cargo build --release` and run `target/release/correlations`.

### `src/main.rs`

```
extern crate rayon;

type S = u32;
const S_BITS: u32 = 32;

fn cat(mut a: Vec<S>, mut b: Vec<S>) -> Vec<S> {
    if a.capacity() >= b.capacity() {
        a.append(&mut b);
        a
    } else {
        b.append(&mut a);
        b
    }
}

fn search(n: u32, i: u32, ss: Vec<S>) -> u32 {
    if ss.is_empty() {
        0
    } else if 2 * i + 1 > n {
        search_end(n, i, ss)
    } else if 2 * i + 1 == n {
        search2(n, i, ss.into_iter().flat_map(|s| vec![s, s | 1 << i]))
    } else {
        search2(n,
                i,
                ss.into_iter()
                    .flat_map(|s| {
                                  vec![s,
                                       s | 1 << i,
                                       s | 1 << n - i - 1,
                                       s | 1 << i | 1 << n - i - 1]
                              }))
    }
}

fn search2<SS: Iterator<Item = S>>(n: u32, i: u32, ss: SS) -> u32 {
    let (shift, mask) = (n - i - 1, !(!(0 as S) << i + 1));
    let close = |s: S| {
        let x = (s ^ s >> shift) & mask;
        x & x.wrapping_sub(1) == 0
    };
    let (ssy, ssn) = ss.partition(|&s| close(s));
    let (cy, cn) = rayon::join(|| search(n, i + 1, ssy), || search(n, i + 1, ssn));
    cy + cn
}

fn search_end(n: u32, i: u32, ss: Vec<S>) -> u32 {
    if i >= n - 1 { 1 } else { search_end2(n, i, ss) }
}

fn search_end2(n: u32, i: u32, mut ss: Vec<S>) -> u32 {
    let (shift, mask) = (n - i - 1, !(!(0 as S) << i + 1));
    let close = |s: S| {
        let x = (s ^ s >> shift) & mask;
        x & x.wrapping_sub(1) == 0
    };
    match ss.iter().position(|&s| close(s)) {
        Some(0) => {
            match ss.iter().position(|&s| !close(s)) {
                Some(p) => {
                    let (ssy, ssn) = ss.drain(p..).partition(|&s| close(s));
                    let (cy, cn) = rayon::join(|| search_end(n, i + 1, cat(ss, ssy)),
                                               || search_end(n, i + 1, ssn));
                    cy + cn
                }
                None => search_end(n, i + 1, ss),
            }
        }
        Some(p) => {
            let (ssy, ssn) = ss.drain(p..).partition(|&s| close(s));
            let (cy, cn) = rayon::join(|| search_end(n, i + 1, ssy),
                                       || search_end(n, i + 1, cat(ss, ssn)));
            cy + cn
        }
        None => search_end(n, i + 1, ss),
    }
}

fn main() {
    for n in 1..S_BITS + 1 {
        println!("{}: {}", n, search(n, 1, vec![0, 1]));
    }
}

```

### `Cargo.toml`

```
[package]
name = "correlations"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
rayon = "0.7.0"

```

Try it online!

I also have a slightly slower variant using very much less memory.

# Answer
> 6 votes
## C++ using the BuDDy library

A different approach: have a binary formula (as binary decision diagram) that takes the bits of `S` as input and is true iff that gives some fixed values of `Y` or `N` at certain selected positions. If that formula is not constant false, select a free position and recurse, trying both `Y` and `N`. If there is no free position, we have found a possible output value. If the formula is constant false, backtrack.

This works relatively reasonable because there are so few possible values so that we can often backtrack early. I tried a similar idea with a SAT solver, but that was less successful.

```
#include<vector>
#include<iostream>
#include<bdd.h>

// does vars[0..i-1] differ from vars[n-i..n-1] in at least two positions?
bdd cond(int i, int n, const std::vector<bdd>& vars){
  bdd x1 { bddfalse };
  bdd xs { bddfalse };
  for(int k=0; k<i; ++k){
    bdd d { vars[k] ^ vars[n-i+k] };
    xs |= d & x1;
    x1 |= d;
  }
  return xs;
}

void expand(int i, int n, int &c, const std::vector<bdd>& conds, bdd x){
  if (x==bddfalse)
    return;
  if (i==n-2){
    ++c;
    return;
  }

  expand(i+1,n,c,conds, x & conds[2*i]);
  x &= conds[2*i+1];
  expand(i+1,n,c,conds, x);
}

int count(int n){
  if (n==1)   // handle trivial case
    return 1;
  bdd_setvarnum(n-1);
  std::vector<bdd> vars {};
  vars.push_back(bddtrue); // assume first bit is 1
  for(int i=0; i<n-1; ++i)
    if (i%2==0)            // vars in mixed order
      vars.push_back(bdd_ithvar(i/2));
    else
      vars.push_back(bdd_ithvar(n-2-i/2));
  std::vector<bdd> conds {};
  for(int i=n-1; i>1; --i){ // handle long blocks first
    bdd cnd { cond(i,n,vars) };
    conds.push_back( cnd );
    conds.push_back( !cnd );
  }
  int c=0;
  expand(0,n,c,conds,bddtrue);
  return c;
}

int main(void){
  bdd_init(20000000,1000000);
  bdd_gbc_hook(nullptr); // comment out to see GC messages
  for(int n=1; ; ++n){
    std::cout << n << " " << count(n) << "\n" ;
  }
}

```

To compile with debian 8 (jessie), install `libbdd-dev` and do `g++ -std=c++11 -O3 -o hb hb.cpp -lbdd`. It might be useful to increase the first argument to `bdd_init` even more.

# Answer
> 4 votes
# Clingo, n ≈ ~~30 or 31~~ 34

I was a little surprised to see five lines of Clingo code overtake my brute-force Rust solution and come really close to Christian’s BuDDy solution—it looks like it would beat that too with a higher time limit.

### `corr.lp`

```
{s(2..n)}.
d(K,I) :- K=1..n-2, I=1..n-K, s(I), not s(K+I).
d(K,I) :- K=1..n-2, I=1..n-K, not s(I), s(K+I).
a(K) :- K=1..n-2, {d(K,1..n-K)} 1.
#show a/1.

```

### `corr.sh`

```
#!/bin/bash
for ((n=1;;n++)); do
    echo "$n $(clingo corr.lp --project -q -n 0 -c n=$n | sed -n 's/Models *: //p')"
done

```

# Answer
> 2 votes
# Pari/GP, 23

By default, Pari/GP limits its stack size to 8 MB. The first line of the code, `default(parisize, "4g")`, sets this limit to 4 GB. If it still gives a stackoverflow, you can set it to 8 GB.

```
default(parisize, "4g")
f(n) = #vecsort([[2 > hammingweight(bitxor(s >> (n-i) , s % 2^i)) | i <- [2..n-1]] | s <- [0..2^(n-1)]], , 8)
for(n = 1, 100, print(n " -> " f(n)))

```

# Answer
> 2 votes
## Clojure, 29 in ~~75~~ 38 seconds, 30 in 80 and 31 in 165

Runtimes from **Intel i7 6700K**, memory usage is less than 200 MB.

project.clj (uses com.climate/claypoole for multithreading):

```
(defproject tests "0.0.1-SNAPSHOT"
  :description "FIXME: write description"
  :dependencies [[org.clojure/clojure "1.8.0"]
                 [com.climate/claypoole "1.1.4"]]
  :javac-options ["-target" "1.6" "-source" "1.6" "-Xlint:-options"]
  :aot [tests.core]
  :main tests.core)

```

Source code:

```
(ns tests.core
  (:require [com.climate.claypoole :as cp]
            [clojure.set])
  (:gen-class))

(defn f [N]
  (let [n-threads   (.. Runtime getRuntime availableProcessors)
        mask-offset (- 31 N)
        half-N      (quot N 2)
        mid-idx     (bit-shift-left 1 half-N)
        end-idx     (bit-shift-left 1 (dec N))
        lower-half  (bit-shift-right 0x7FFFFFFF mask-offset)
        step        (bit-shift-left 1 12)
        bitcount
          (fn [n]
            (loop [i 0 result 0]
              (if (= i N)
                result
                (recur
                  (inc i)
                  (-> n
                      (bit-xor (bit-shift-right n i))
                      (bit-and (bit-shift-right 0x7FFFFFFF (+ mask-offset i)))
                      Integer/bitCount
                      (< 2)
                      (if (+ result (bit-shift-left 1 i))
                          result))))))]
    (->>
      (cp/upfor n-threads [start (range 0 end-idx step)]
        (->> (for [i      (range start (min (+ start step) end-idx))
                   :when  (<= (Integer/bitCount (bit-shift-right i mid-idx))
                              (Integer/bitCount (bit-and         i lower-half)))]
               (bitcount i))
             (into #{})))
      (reduce clojure.set/union)
      count)))

(defn -main [n]
  (let [n-iters 5]
    (println "Calculating f(n) from 1 to" n "(inclusive)" n-iters "times")
    (doseq [i (range n-iters)]
      (->> n read-string inc (range 1) (map f) doall println time)))
  (shutdown-agents)
  (System/exit 0))

```

A brute-force solution, each thread goes over a subset of the range (2^12 items) and builds a set of integer values which indicate detected patterns. These are then "unioned" together and thus the distinct count is calculated. I hope the code isn't too tricky to follow eventhough it uses threading macros a lot. My `main` runs the test a few times to get JVM warmed up.

Update: Iterating over only half of the integers, gets the same result due to symmetry. Also skipping numbers with higher bit count on lower half of the number as they produce duplicates as well.

Pre-built uberjar (v1) (3.7 MB):

```
$ wget https://s3-eu-west-1.amazonaws.com/nikonyrh-public/misc/so-124424-v2.jar
$ java -jar so-124424-v2.jar 29
Calculating f(n) from 1 to 29 (inclusive) 5 times
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 41341.863703 msecs"
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 37752.118265 msecs"
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 38568.406528 msecs"
[ctrl+c]

```

Results on different hardwares, expected runtime is `O(n * 2^n)`?

```
i7-6700K  desktop: 1 to 29 in  38 seconds
i7-6820HQ laptop:  1 to 29 in  43 seconds
i5-3570K  desktop: 1 to 29 in 114 seconds

```

You can easily make this single-threaded and avoid that 3rd party dependency by using the standard for:

```
(for [start (range 0 end-idx step)]
  ... )

```

Well the built-in pmap also exists but claypoole has more features and tunability.

# Answer
> 1 votes
# Mathematica, n=19

press alt+. to abort and the result will be printed

```
k = 0;
For[n = 1, n < 1000, n++,
Z = Table[HammingDistance[#[[;; i]], #[[-i ;;]]], {i, Length@#}] & /@
Tuples[{0, 1}, n];
Table[If[Z[[i, j]] < 2, Z[[i, j]] = 0, Z[[i, j]] = 1], {i,
Length@Z}, {j, n}];
k = Length@Union@Z]
Print["f(", n, ")=", k]

```

# Answer
> 1 votes
# Mathematica, 21

```
f[n_] := Length@
     DeleteDuplicates@
      Transpose@
       Table[2 > Tr@IntegerDigits[#, 2] & /@
         BitXor[BitShiftRight[#, n - i], Mod[#, 2^i]], {i, 1,
         n - 1}] &@Range[0, 2^(n - 1)];
Do[Print[n -> f@n], {n, Infinity}]

```

For comparison, Jenny\_mathy's answer gives `n = 19` on my computer.

The slowest part is `Tr@IntegerDigits[#, 2] &`. It is a shame that Mathematica doesn't have a built-in for Hamming weight.

---

If you want to test my code, you can download a free trial of Mathematica.

# Answer
> 1 votes
# Haskell, (unofficial n=20)

This is just the naive approach - so far without any optimizations. I wondered how well it would fare against other languages.

How to use it (assuming you have haskell platform installed):

* Paste the code in one file `approx_corr.hs` (or any other name, modify following steps accordingly)
* Navigate to the file and execute `ghc approx_corr.hs`
* Run `approx_corr.exe`
* Enter the maximal `n`
* The result of each computation is displayed, as well as the cumulative real time (in ms) up to that point.

Code:

```
import Data.List
import Data.Time
import Data.Time.Clock.POSIX

num2bin :: Int -> Int -> [Int]
num2bin 0 _ = []
num2bin n k| k >= 2^(n-1) = 1 : num2bin (n-1)( k-2^(n-1))
           | otherwise  = 0: num2bin (n-1) k

genBinNum :: Int -> [[Int]]
genBinNum n = map (num2bin n) [0..2^n-1]

pairs :: [a] -> [([a],[a])]
pairs xs = zip (prefixes xs) (suffixes xs)
   where prefixes = tail . init . inits
         suffixes = map reverse . prefixes . reverse

hammingDist :: (Num b, Eq a) => ([a],[a]) -> b
hammingDist (a,b) = sum $ zipWith (\u v -> if u /= v then 1 else 0) a b

f :: Int -> Int
f n = length $ nub $ map (map ((<=1).hammingDist) . pairs) $ genBinNum n
--f n = sum [1..n]

--time in milliseconds
getTime = getCurrentTime >>= pure . (1000*) . utcTimeToPOSIXSeconds >>= pure . round

main :: IO()
main = do
    maxns <- getLine
    let maxn = (read maxns)::Int
    t0 <- getTime
    loop 1 maxn t0
     where loop n maxn t0|n==maxn = return ()
           loop n maxn t0
             = do
                 putStrLn $ "fun eval: " ++ (show n) ++ ", " ++ (show $ (f n))
                 t <- getTime
                 putStrLn $ "time: " ++ show (t-t0);
                 loop (n+1) maxn t0

```

# Answer
> 1 votes
# A Haskell solution, using popCount and manually managed parallelism

Compile: `ghc -rtsopts -threaded -O2 -fllvm -Wall foo.hs`

(drop the `-llvm` if it doesn't work)

Run : `./foo +RTS -N`

```
module Main (main) where

import Data.Bits
import Data.Word
import Data.List
import qualified Data.IntSet as S
import System.IO
import Control.Monad
import Control.Concurrent
import Control.Exception.Base (evaluate)

pairs' :: Int -> Word64 -> Int
pairs' n s = fromIntegral $ foldl' (.|.) 0 $ map mk [1..n]
  where mk d = let mask = 1 `shiftL` d - 1
                   pc = popCount $! xor (s `shiftR` (n - d)) (s .&. mask)
               in  if pc <= 1
                     then mask + 1
                     else 0

mkSet :: Int -> Word64 -> Word64 -> S.IntSet
mkSet n a b = S.fromList $ map (pairs' n) [a .. b]

f :: Int -> IO Int
f n
   | n < 4 = return $ S.size $ mkSet n 0 mxbound
   | otherwise = do
        mvs <- replicateM 4 newEmptyMVar
        forM_ (zip mvs cpairs) $ \(mv,(mi,ma)) -> forkIO $ do
          evaluate (mkSet n mi ma) >>= putMVar mv
        set <- foldl' S.union S.empty <$> mapM readMVar mvs
        return $! S.size set
   where
     mxbound = 1 `shiftL` (n - 1)
     bounds = [0,1 `shiftL` (n - 3) .. mxbound]
     cpairs = zip bounds (drop 1 bounds)

main :: IO()
main = do
    hSetBuffering stdout LineBuffering
    mapM_ (f >=> print) [1..]

```

# Answer
> 1 votes
## A C version, using builtin popcount

Works better with `clang -O3`, but also works if you only have `gcc`.

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned long pairs(unsigned int n, unsigned long s) {
  unsigned long result = 0;

  for(int d=1;d<=n;d++) {
    unsigned long mx = 1 << d;
    unsigned long mask = mx - 1;

    unsigned long diff = (s >> (n - d)) ^ (s & mask);
    if (__builtin_popcountl(diff) <= 1)
      result |= mx;
  }
  return result;

}

unsigned long f(unsigned long  n) {
  unsigned long max = 1 << (n - 1);
#define BLEN (max / 2)
  unsigned char * buf = malloc(BLEN);
  memset(buf, 0, BLEN);
  unsigned long long * bufll = (void *) buf;

  for(unsigned long i=0;i<=max;i++) {
    unsigned int r = pairs(n, i);
    buf[r / 8] |= 1 << (r % 8);
  }

  unsigned long result = 0;

  for(unsigned long i=0;i<= max / 2 / sizeof(unsigned long long); i++) {
    result += __builtin_popcountll(bufll[i]);
  }

  free(buf);

  return result;
}

int main(int argc, char ** argv) {
  unsigned int n = 1;

  while(1) {
    printf("%d %ld\n", n, f(n));
    n++;
  }
  return 0;
}

```

# Answer
> 0 votes
# Python 2 + pypy, n = 22

Here is a really simple Python solution as a sort of baseline benchmark.

```
import itertools
def hamming(A, B):
    n = len(A)
    assert(len(B) == n)
    return n-sum([A[i] == B[i] for i in xrange(n)])

def prefsufflist(P):
    n = len(P)
    return [hamming(P[:i], P[n-i:n]) for i in xrange(1,n+1)]

bound = 1
for n in xrange(1,25):
    booleans = set()
    for P in itertools.product([0,1], repeat = n):
        booleans.add(tuple(int(HD <= bound) for HD in prefsufflist(P)))
    print "n = ", n, len(booleans)

```

---
Tags: math, combinatorics, fastest-code
---


title: Alphabet Spiral

text:
# Question
Title: Alphabet Spiral
You are to write a program or function that outputs this exact text:

```
OPQRSTU
NQPONMV
MREDCLW
LSFABKX
KTGHIJY
JUVWXYZA
IHGFEDCB

```

May also be lowercase and trailing spaces and newlines are allowed.

Standard loopholes are disallowed

This is , so smallest byte count wins.

# Answer
# MATL, ~~28~~ 26 bytes

```
1Y2tIL)P0v7lYLP2:JTF-JQ&()

```

**Try it online!**

### Explanation

```
1Y2     % Push string 'AB...Z'
tIL)    % Duplicate, remove last: gives 'AB...Y'
P       % Flip: gives 'YX...A'
0       % Push 0. Char 0 is treated as space
v       % Concatenate into a column vector of char
7lYL    % 7x7 numeric array: clockwise spiral of numbers from 1 to 49
P       % Flip vertically to make it anti-clockwise
2:      % Push [1 2]. Will be attached vertically after the last col
JqJh    % Index "[end-1, end]", to be used as row index
JQ      % Index "end+1", to be used as column index
&(      % Assign [1 2] to those positions. The rest of the new col will contain 0
)       % Index into the char vector. Indexing is modular and 1-based, so 0 as an
        % index refers to the last value of the char vector, which is char 0, or
        % equivalently space. So the 0 values in the numeric array give spaces.
        % Implicitly display

```
> 16 votes

# Answer
# Python 2, 69 bytes

```
print'''OPQRSTU
NQPONMV
MREDCLW
LSFABKX
KTGHIJY
JUVWXYZA
IHGFEDCB'''

```

Just do it...
> 5 votes

# Answer
# Bubblegum, 47 bytes

A hex dump, courtesy of `xxd`:

```
00000000: 520a adf6 2e08 7444 c41e c8ff 4096 ca2d  R.....tD....@..-
00000010: 8832 2297 8cd7 1bb1 fe10 43ce 39cc 8e5f  .2".......C.9.._
00000020: 31f7 3d63 432e d3f3 3873 ecf7 7641 a3    1.=cC...8s..vA.

```

(This is just the spiral, “compressed”.)

Try it online.
> 2 votes

# Answer
# Fourier, ~~143~~ 141 bytes

Not a particularly interesting answer except that it stores newlines (ASCII code 10) as the variable T... Uses isaacg's golfing program.

```
79a^a^a^a^a^a^a10a~T78a81avavavava86aTa77a82a69avava76a87aTa76a83a70a65a^a75a88aTa75a84a71a^a^a^a89a10a74a85a^a^a^a^a^a65aTa73avavavavavavava

```

~~Try it online~~

**Try it online!**
> 1 votes

# Answer
# Python 3, 72 bytes

```
print('OPQRSTU\nNQPONMV\nMREDCLW\nLSFABKX\nKTGHIJY\nJUVWXYZA\nIHGFEDCB')

```

Not exactly interesting, but it still works!
> 1 votes

# Answer
## PHP, 130 bytes

```
for($p=30,$s=1,$r=_;$i<51;$r[$p]=chr(90-abs(25-$i++)),$p+=$s*(9-$d))if(!$n||!$c=++$c%$n)($d=8-$d)?$n++:$s=-$s;echo wordwrap($r,8);

```

literally draws the spiral. Run with `-r`

**breakdown**

```
for($p=30,$s=1,$r=_;    // initialize position to 3*9+3, $s(ign) to +1, $r(esult) to string
                        // implicit $c(ount)=$d(irection)=$i(ndex)=le($n)gth=0
    $i<51;              // loop $i from 0 to 50
    $r[$p]=chr(90-abs(25-$i++)),// 2. set current position in string to correct character
    $p+=$s*(9-$d))              // 3. move cursor
    if(!$n||!$c=++$c%$n)        // 1. if 1st iteration ($n==0) or ++$c has rotated around $n
        ($d=8-$d)                   // negate $direction (0=horizontal, 8=vertical)
            ?$n++                   // if vertical: increase length
            :$s=-$s                 // else invert sign
        ;
                        // output: wrap to lines of 8 characters
echo wordwrap($r,8);    // having left spaces avoids need to provide 3rd and 4th parameter

```

Easy to extend: For more alphabet, append `%50` after `$i++`, replace `51` with the wanted number, modify `8-$d`, `9-$d`, `$p=30` and the `wordwrap` width to the new dimensions.
> 1 votes

# Answer
# JavaScript ES6, 62 bytes

```
a=>`OPQRSTU
NQPONMV
MREDCLW
LSFABKX
KTGHIJY
JUVWXYZA
IHGFEDCB`

```

## Try it

```
let f=a=>`OPQRSTU
NQPONMV
MREDCLW
LSFABKX
KTGHIJY
JUVWXYZA
IHGFEDCB`;

console.log(f());
```
> 1 votes

# Answer
# Ruby, 63 bytes

In this case, nothing I found beats the boring answer...

```
puts"OPQRSTU
NQPONMV
MREDCLW
LSFABKX
KTGHIJY
JUVWXYZA
IHGFEDCB"

```

My best solution that didn't print the literal string only, but still has to directly hardcode some of it, is **110 bytes**:

```
w=[*?B..?Q].reverse*''
puts [*?O..?U]*'',[?N,w[0,5],?V]*'',"MREDCLW
LSFABKX
KTGHIJY",[?J,*?U..?Z,?A]*'',w[8,8]

```
> 0 votes

# Answer
# ///, 57 bytes

```
OPQRSTU
NQPONMV
MREDCLW
LSFABKX
KTGHIJY
JUVWXYZA
IHGFEDCB

```

Try it online!

Just another boring answer. Move on!
> 0 votes

# Answer
# C#, ~~151~~ ~~145~~ ~~136~~ 130 bytes

```
namespace a{class P{static void Main(){System.Console.Write("OPQRSTU\nNQPONMV\nMREDCLW\nLSFABKX\nKTGHIJY\nJUVWXYZA\nIHGFEDCB");}}}

```

Again, a boring one that does the trick.

Saved 6 bytes thanks to auhmaan.
> 0 votes

# Answer
# Lua, 69 bytes

```
print([[OPQRSTU
NQPONMV
MREDCLW
LSFABKX
KTGHIJY
JUVWXYZA
IHGFEDCB]])

```

At least it works!
> 0 votes

# Answer
# 05AB1E, 46 bytes

```
•ûk2šÄ>¸©W$V-ÏfQ*LnHO”Ïmsqšƒ1ËUðhd@ý(™š•36B1¡»

```

Try it online!

Won't win by any means, but it does work.
> 0 votes

# Answer
# Windows batch, 84 bytes

```
@for %%p in (OPQRSTU NQPONMV MREDCLW LSFABKX KTGHIJY JUVWXYZA IHGFEDCB) do @echo %%p

```

Simple enough `for` loop to loop through the strings.
> 0 votes

# Answer
# Japt, ~~54~~ 52 bytes

```
`opqÏ
nqpmv
mdclw
lsfabkx
ktgjy
juvwxyza
ihgfcb

```

Try it online

---

## Explanation

Simply a compressed string of the spiral in lowercase.
> 0 votes

# Answer
# Modern Pascal 2.0, 122 bytes

```
 Write('OPQRSTU'+#13#10+'NQPONMV'+#13#10+'MREDCLW'+#13#10+'LSFABKX'+#13#10+'KTGHIJY'+#13#10+'JUVWXYZA'+#13#10+'IHGFEDCB');

```

***Explanation*** Simply embed CRLF into the string, and display it.

// Author of Modern Pascal
> 0 votes

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


title: Am a I square repdigit?

text:
# Question
Title: Am a I square repdigit?
## Your Task

You will write a program or function to return a truthy value if the integer inputted to it is a square repdigit, and a falsy value if it is not. A repdigit is an integer that contains only one digit (e.g. `2`, `44`, `9999`). For the purpose of this challenge, a square repdigit is a repdigit that is the square of a different repdigit.

## Input

An integer, in base 10.

## Output

A truthy/falsy value that reflects whether the input is a square repdigit

## Examples

```
0 --> falsy
1 --> falsy
2 --> falsy
4 --> truthy
9 --> truthy
11 --> falsy

```

## Scoring

This is , lowest bytes wins.

# Answer
> 9 votes
# Neim, ~~6~~ ~~3~~ 2 bytes

```
+

```

Abuses the way that Neim deals with lists.

`+` pushes the numeric literal `49` to the stack.

Then,  attempts to pop a list from the stack, and Neim implicitly converts `49` to `[4 9]`. It then pops another element, which is the input, provided implicitly. Finally, it checks that the input is in the list.

Try it!

# Answer
> 7 votes
# Befunge, ~~20~~ ~~17~~ 10 bytes

```
&4-:5-*!.@

```

Try it online!

*Thanks @ovs for -7 bytes!*

## How?

```
&4-:5-*!.@    Initial pointer direction >  (Input: 9   )
&             Get input as integer         (Stack: 9   )
 4-           Subtract 4                   (Stack: 5   )
   :          Duplicate                    (Stack: 5, 5)
    5-        Subtract 5                   (Stack: 5, 0)
      *       Multiply                     (Stack: 0   )
       !      NOT                          (Stack: 1   )
        .     Print as integer             (Stack:     )
         @    End of program

```

## Proof that `4` and `9` are the only valid square repdigits

The last two digits of any repdigit\>10 squared are two different values, except `8..8`:

```
 n    n^2 % 100
--------------
1..1     21
2..2     84
3..3     89
4..4     36
5..5     25
6..6     36
7..7     29
8..8     44
9..9     01

```

`88^2 = 7744`, and the last three digits of `8..8^2` is `544`.

# Answer
> 4 votes
# Mathematica, 11 bytes

```
#==4||#==9&

```

# Answer
> 1 votes
# Jelly, 4 bytes

```
e4,9

```

Try it online!

~~Note: if you disprove me, I'll edit. This returns a truthy result only if the input is 4 or 9.~~

Junghuan Min ninja'd a proof...

# Answer
> 1 votes
# C#, JavaScript, Java, 12 bytes

```
n=>n==4|n==9

```

For Java replace `=>` with `->`.

Or a version more in the spirit of the challenge, C# only, for 61 bytes:

```
g=n=>n.Replace(n[0]+"","")==""
n=>g(n)&g(System.Math.Sqrt(n))

```

# Answer
> 0 votes
# 05AB1E, 5 bytes

```
49S¹å

```

Try it online!

# Answer
> 0 votes
# APL (Dyalog), 5 bytes

Just tests for membership of {4,9}

```
∊∘4 9

```

Try it online!

# Answer
> 0 votes
# Braingolf, 19 bytes

```
.pl3e1:0|>e1:0|<+1-

```

Try it online!

This is as far as I can tell actually the shortest way to check "is `n` 4 **or** 9?"

Will output `1` if input is `4` or `9`, otherwise will output `0`

## Explanation

```
.pl3e1:0|>e1:0|<+1-  Implicit input from commandline args
.p                   Duplicate, pop duplicate, push prime factors
  l3e                If there are exactly 3 items in stack..
                     (2 prime factors plus original input)
     1               ..Push 1
      :              Else
       0             ..Push 0
        |            Endif
         >           Move last item to start
          e          If 2 prime factors are equal..
           1         ..Push 1
            :        Else
             0       ..Push 0
              |      Endif
               <     Move first item to end
                +    Sum last 2 items
                 1-  Subtract 1
                     Implicit output.

```

# Answer
> 0 votes
# Batch, ~~65 58 53~~ 46 bytes

I have code-copying issues.

```
@if %1 neq 4 if %1 neq 9 echo 0&exit/b
echo 1

```

Return 1 for truthy value, 0 for falsely value.

# Answer
> 0 votes
# PHP, 22 bytes

```
<?=$argn==4||$argn==9;

```

Try it online!

# Answer
> 0 votes
# Python, 18 bytes

```
lambda n:n in[4,9]

```

Try it online!

# Answer
> 0 votes
# Python 3, ~~39~~ 25 bytes

Solution can be shorter for sure.

old:

```
n=input();print(n in ['0','1','4','9'])

```

Try it online!

new:

```
print(input()in['4','9'])

```

Try it online!

---

From this: "a square repdigit is a repdigit that is the square of a different repdigit."

Let z='ζζζζ...' be the square repdigit.

**Case 1 z\<10:**

~~0² = 0~~

~~1² = 1~~

2² = 4

3² = 9

4² to 9² are not square repdigits.

**Case z\>10:**

Lets assume there is an y∈ℕ with y²=z and y='xxxxx..'

We have just tested all single digits, so if there is an y with y² = z, then it has to be y\>10.

So we can write y = x\[10°+10¹\] + x\[10²+10³+...\]

Then it is: y² = x²\[10°+10¹\]² + r = x² \[10° + 2\*10¹\] + r, with r only containing summands of power \>1.

Comparing z='ζζζ..' with y² we get: x²=ζ and 2x²=ζ, hence x=0.

⇒ The only square repdigits are ~~0,1,~~ 4 and 9.

# Answer
> 0 votes
# Javascript, 17 bytes

```
a=>!((a-4)*(a-9))

```

```
f=
a=>!((a-4)*(a-9))

for (i=0;i<12;i++) console.log(''+i+' -> '+f(i))
```

---
Tags: code-golf, number-theory
---


# Question
Title: Output the Wikipedia article for Kolmogorov Complexity
Your job is to output the html of the current version (at the time of this writing) of the Wikipedia page for Kolmogorov complexity: https://en.wikipedia.org/w/index.php?title=Kolmogorov\_complexity&oldid=781950121&action=raw (backup)

This is , so the shortest code wins.

# Answer
> 3 votes
# 7zip file manager: 12,156 bytes

hex dump: here

## how to use:

`7zip e [savedfileName]`

I'm posting this because it's about as small as you can get it without using HTTP calls.

# Answer
> 1 votes
# Bubblegum, 12,290 bytes

**Hexdump of solution.**

Try it online! (you have to paste the hexdump yourself, it's too long to fit in 30k chars)

---
Tags: code-golf, kolmogorov-complexity, compression
---


# Question
Title: How to simplify ternary expressions in Javascript
I have an expression that could be expressed as either of :

```
a += (A ? B ? x : C ? y : D : D);

a += (A && B ? x : A && C ? y : D);

```

where A,B,C are expressions of 5-10 bytes each, and x and y are single character literals (3-4 bytes). D is another chain of ternaries (without the branching problem).

I'm getting stuck trying to eliminate the duplication of D or A. If I was using `if`, it would be something like this:

```
if (A)
    if (B)
        x
    else if (C)
        y
else D

```

Obviously I could do `((z=A) && B ? x : z && C ? y : D)`...but any other more creative suggestions?

The actual code looks something like:

```
if (r%4<2&&r>3&&c<22&&c>1)
    if ((i-r)%8==6)
        '\\'
    else if ((i+r)%8==1)
        '/'
else

```

D is something like:

```
(i+r) % 8 == 3 ? '/' :
    (c-r+16) % 8 == 4 ? '\\' :

```

# Answer
> 2 votes
If you know that `x` and `y` cannot contain falsy values, as your code examples suggest, you can do the following to eliminate duplicate evaluation of `A` or `D`:

```
a += A && (B && x || C && y) || D;

```

Demo code and test cases in the following snippet:

```
// return x
test(1,1,0); // A and B
test(1,1,1); // A and B (and C)

// return y
test(1,0,1); // A and C

// return D
test(0,0,0); //
test(0,0,1); // C
test(0,1,0); // B
test(0,1,1); // B and C
test(1,0,0); // A

function test(A, B, C) {
  var x = 'x', y = 'y', D = 'D';
  a = A && (B && x || C && y) || D;
  expected = (A && B ? x : A && C ? y : D);
  var ws = ' ';
  console.log(
    [
      A && 'A' || ws,
      B && 'B' || ws,
      C && 'C' || ws
    ].join(ws),
    ' ==> a = ' + a,
    a === expected ?
      'Passed' :
      'Failed, expected ' + expected
  );
}
```

Otherwise, if falsy values are possible, you could do this:

```
a += [D, x, y][A && (B && 1 || C && 2) || 0];

```

Demo code and test cases in the following snippet:

```
// return x
test(1,1,0); // A and B
test(1,1,1); // A and B (and C)

// return y
test(1,0,1); // A and C

// return D
test(0,0,0); //
test(0,0,1); // C
test(0,1,0); // B
test(0,1,1); // B and C
test(1,0,0); // A

function test(A, B, C) {
  var x = false, y = 0, D = '';
  A = !!A; B = !!B; C = !!C;
  a = [D, x, y][A && (B && 1 || C && 2) || 0];
  expected = (A && B ? x : A && C ? y : D);
  var ws = ' ';
  console.log(
    [
      A && 'A' || ws,
      B && 'B' || ws,
      C && 'C' || ws
    ].join(ws),
    ' ==> a = ' + xyD(a, x, y, D),
    a === expected ?
      'Passed' :
      'Failed, expected ' + xyD(expected, x, y, D)
  );
}

function xyD(result, x, y, D) {
  return result === x ? 'x' :
         result === y ? 'y' :
         result === D ? 'D' : '<error>' ;
}
```

# Answer
> 1 votes
Since short-circuiting is not required here, you can also do:

```
d=D;a+=A?B?x:C?y:d:d;

```

If short-circuiting were required, since your `B` and `C` are truthy values, you can do:

```
a+=(A?B?x:C?y:0:0)||D;

```

If short-circuiting were required and your `B` and `C` are not truthy values:

```
d=_=>D;a+=A?B?x:C?y:d():d();

```

---
Tags: tips, javascript
---


title: Create a BijectiveBrain

text:
# Question
Title: Create a BijectiveBrain
## Create a bijective function between the syntactically valid BF programs and the natural numbers

This means that you will assign each BF program a nonnegative integer (0,1,2,...) in such a way that each number gets a BF program without syntax errors (and without whitespace or comments).

Note that something like Binaryf\***, for two reasons. Both `+>` and `>` map to 2, and no valid program maps to `6` (since `[` is not a valid BF program).

You may either create two programs, one to map BF programs to numbers, one to map numbers to valid BF programs (which will be inverses) (in which case your score is the sum of their lengths), or you can create one program which does both tasks (in which case your score is just length of that one program).

**Note:** The program(s) must run in polynomial time (in terms of the length of the input). (This rule is to prevent boring brute force approaches.)

This is , so the shortest program(s) wins!

# Answer
> 1 votes
## Haskell, 215+242=457

I haven't significantly golfed this. Its more of a example.

From BF to number

```
c '>'=1
c '<'=2
c '+'=3
c '-'=4
c '.'=5
c ','=6

i 0 ""=0
i 0 ('[':t)=7+7*(i 1 t)
i 0 (h:t)=(c h)+7*(i 0 t)

i b (']':t)=0+8*(i (b-1) t)
i b ('[':t)=7+8*(i (b+1) t)
i b (h:t)=(c h)+8*(i b t)

main=interact(show.i 0)

```

From number to BF

```
c 1='>'
c 2='<'
c 3='+'
c 4='-'
c 5='.'
c 6=','

i 0 0=""
i 0 n = case divMod n 7 of
    (m,0)->'[':i 1 (m-1)
    (m,x)->(c x):i 0 m
i b n = case divMod n 8 of
    (m,0)->']':i (b-1) m
    (m,7)->'[':i (b+1) m
    (m,x)->(c x):i b m

main=interact(i 0.read)

```

It works through a combination of Bijective numeration and Mixed radix.

The encoder has two modes: no unmatched brackets mode and unmatched brackets mode.

If there are no unmatched brackets, 0 maps to the empty program, and each of the characters `><+-.,[` is mapped to a number from 1 to 7. `]` is not included since a BF program can not have `]` until it an unmatched bracket. This digit becomes the least significant digit, and is in base 7.

Once there are unmatched brackets, the digits are in base 8, with `]` assigned to `0`. In particular, there is no number assigned to the ending the program (since you can not end the program while there are unmatched brackets). Once all brackets are matched, it returns to no unmatched brackets mode. To output `0` exactly while in this mode, you must match all brackets, and then end.

Example: `.-,.><++.,[>]` -\> 4228460766 -\> `.-,.><++.,[>]`

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


title: Reversed language name

text:
# Question
Title: Reversed language name
You should code a piece of code that looks like it outputs the language name but actually outputs the name reversed.

E.g. a Python program should look like it outputs `Python` but should actually output `nohtyP`.

The winner is the answer with the most upvotes in a week!

# Answer
> 83 votes
# PHP, 3 bytes

```
PHP

```

Try it online!

It looks like it outputs the language name, but it's actually the letters in reversed order.

# Answer
> 26 votes
# Cubix

Because Cubix doesn't always need to be indecipherable

```
begin;
print "Cubix" > output;
end@?;

```

Try it online!

Watch it running

# Answer
> 24 votes
# R, 8 bytes

Took me a while to figure this one out, but I think I've solved it!

```
cat("R")

```

# Answer
> 20 votes
# HTML, 11 Bytes

```
HTML

```

-4 Bytes hardcoding the unicode character in a html file

# HTML, 12 Bytes

```
HTML

```

The browser do the rest in a html file

```
HTML
```

# Answer
> 18 votes
# C++

```
#include <iostream>
int main()
{
    char C = 1;
    std::string CPP;
    for(C++; C++ < 42; C++)
        CPP += "C++";
    std::cout << CPP[C++];
    std::cout << CPP[C++];
    std::cout << CPP[C++];
    return 0;
}

```

Try it online!

# Answer
> 14 votes
# Braingolf, 20 bytes

```
"Braingolf"@@@@@@@@@

```

Try it online!

`@` Prints a character as ASCII, however because `"Braingolf"` pushes the string in order, the last item on the stack is `f`, so the first `@` prints `f`, and so on.

Because of this quirk, the first `Hello, World!` program in Braingolf was actually:

```
"!dlroW ,olleH"@@@@@@@@@@@@@

```

Sidenote: Braingolf backwards is `Flogniarb`, which might actually be a better language name than Braingolf!

# Answer
> 14 votes
# \>\<\>, 8 bytes

```
"><>">o<

```

Try it online!

Fun fact, this actually reverses the name of the language. The name, however, is a palindrome. Which is extra funny to me, because 'paling' (which almost spells the start of 'palindrome') is a kind of eel in Dutch.

# Answer
> 10 votes
# C (gcc), ~~20~~ 18 bytes

*-2 bytes thanks to cleblanc.*

Specification says nothing about any output on STDERR so...

```
main(){puts("C");}

```

Try it online!

# Answer
> 9 votes
# Jelly, 8 bytes

```
“Jelly”U

```

Try it online!

"U" is a meaningless enough atom for "reverse an array" that 99% of programmers will likely assume that this program will output "Jelly". Maybe not so much code-golfers, though.

# Answer
> 6 votes
# APL (Dyalog), 24 bytes

Outputs on STDERR. This is a simple identity reduction, but APL goes right-to-left!

```
{⍺⊣⍞←⍵}/' APL'

```

Try it online!

---

Alternate, tacit, self-documenting version:

```
Print←⍞∘←
Identity←⊣
All←/
Identity∘Print All' APL'

```

Try it online!

---

A.P.L.: An Interactive Approach (pun intended). Let's ask for the three letters and input them in proper order:

```
⎕⎕⎕
'A'
'P'
'L'

```

Works because APL evaluates from right to left and thus asks for the rightmost letter first, but we enter the "A" first, etc.

Try it online!

# Answer
> 5 votes
# J, 3 bytes

Jumping on the language-is-palindrome bandwagon:

```
'J'

```

# Answer
> 3 votes
# q, 5 bytes

a one letter language name makes this problem trivial

```
1"q";

```

Output:

```
q

```

# Answer
> -1 votes
# Bash, 10 bytes

```
rev<<<Bash

```

Try it online!

---
Tags: popularity-contest, underhanded
---