text:
Maximal 2-distance Sets
In the plane (\$\mathbb R^2\$) we can have at most five distinct points such that the distances from each point to every other point (except itself) can assume at most two distinct values.
An example of such an arrangement is a regular pentagon - the two different distances are marked with red and blue:

Challenge
Given a number \$n = 1,2,3,\ldots\$ find the size \$s_n\$ of the largest 2-distance set in \$\mathbb R^n\$.
Definitions

We measure the Euclidean distance \$d(a, b) = \sqrt{\sum_{i=1}^n (a_i - b_i)^2}\$.
A set \$S \subseteq R^n\$ is a 2-distance set if the number of distinct distances \$| \{ d(a,b) \mid a,b \in S, a \neq b\}| = 2\$.

Details
Any output format defined in sequence is allowed.
Examples
  n =  1, 2, 3,  4,  5,  6,  7,  8
s_n =  3, 5, 6, 10, 16, 27, 29, 45

This is OEIS A027627, and these are all the terms that we know so far. Answers to this challenge are expected to be able to find any term of this sequence - given enough ressources - not just the first eight.

Since the question is tagged code-golf, it's implicit that the scoring criterion is shortest code in bytes.

@xnor Yes in theory without all the limitations the algorithms should find the value for any term.

This is an interesting problem, and it looks like the references in OEIS have enough info to be able to solve it. Unfortunately I have no time right now.

i do not understand specially the case n=1 or R^1  why s_1 is 3?

@RosLuP Consider the points $1,2,3$, the only possible distances are 1 and 2.

Mathematica, 220 218 bytes
For[n=1,1>0,n++,For[m=1,1>0,m++,x=Array[a,{m,n}];d=Table[(Norm[x[[i]]-x[[j]]]^2-1)*(Norm[x[[i]]-x[[j]]]^2-y)==0,{i,1,m-1},{j,i+1,m}];If[Not[CylindricalDecomposition[Flatten@{d,y>0},Flatten@{y,x}]],Break[]]];Print[m-1]]

Try it online! Un-golfed version:
For[ n = 1, 1>0, n++,
  For[ m = 1, 1>0, m++,
   x = Array[a, {m, n}];
   d = Table[(Norm[x[[i]] - x[[j]]]^2 - 1)*(Norm[x[[i]] - x[[j]]]^2 -
         y) == 0, {i, 1, m - 1}, {j, i + 1, m}];
   If[Not[
      CylindricalDecomposition[Flatten@{d, y > 0}, Flatten@{y, x}]],
      Break[]]
  ];
  Print[m - 1]
]

In this code, we apply a key tool from real algebraic geometry. A semialgebraic set is a subset of \$\mathbb{R}^d\$ defined by polynomial equalities and inequalities. We may identify the set of 2-distance subsets of \$\mathbb{R}^n\$ of cardinality \$m\$ with a semialgebraic subset of \$\mathbb{R}^{mn+2}\$. We force one of the distances to equal 1 without loss of generality, which means our semialgebraic set is a subset of \$\mathbb{R}^{mn+1}\$. We denote the other distance (squared) by \$y\$.
For which values \$Y\subseteq\mathbb{R}\$ of \$y\$ does there exists a size-\$m\$ subset of \$\mathbb{R}^n\$ with squared distances \$\{1,y\}\$? This can be answered with the help of Tarski--Seidenberg, which says that the projection of any semialgebraic set is semialgebraic. In our case, this means there is some univariate polynomial \$p\$ and relation \$*\in\{=,<,\leq\}\$ such that \$Y=\{y\in\mathbb{R}:p(y)*0\}\$. This projection may be accomplished using cylindrical algebraic decomposition (CAD), which enjoys an implementation in Mathematica.
Given a set of polynomial equalities and inequalities, as well as an ordered list of variables, Mathematica's implementation returns either an explicit description of every point in the corresponding semialgebraic set, or False if the set is empty. In the above code, we run CAD for increasingly larger values of \$m\$ until we get False, at which point we know that \$s_n=m-1\$. Sadly, the runtime of CAD is doubly exponential in the number of variables, and so we shouldn't expect this approach to determine \$s_9\$ any time soon. In fact, a minute of runtime only gives \$s_1=3\$.

I didn't expect an answer so soon:) Thanks for all the links, I never heard about semialgebraic sets. Did you try to verify $s_2$ or $s_3$, if so, how long did it take?

(And how can you specify the input to the program? Or does it iterate over all $n$?)

@flawr - It's currently running for $s_2$. The code just iterates over all $n$.

Both True can be 1>0 to save 2 bytes.


text:
CahartcreS awppnig (Character Swapping)
Intro/Background
I was looking at "You Had One Job" pictures lately, and noticed an old favourite of mine:

And I said to myself: "I need a program that can generate text like that".
So I devised a set of rules for character swapping and wrote a CGCC challenge!
The Challenge
Given a single string as input, output a string with its inner characters swapped. This can be done by:

Leaving the first letter as is
Swapping each pair of characters thereafter
Leaving the last letter as is. If the string is of an odd length (i.e. the length of the string mod 2 is 1), leave the last two letters as they are.

Example Inputs/Outputs
School -> Shcool
Somebody -> Smobedoy
Character -> Cahartcer
CGCC -> CCGC
Stack Exchange! -> SatkcE cxahgne!
Never gonna give you up -> Nvereg noang vi eoy uup

Walkthrough on swapping
School (Length: 6)
S
 hc
   oo
     l
Shcool

Somebody (Length: 8)
S
 mo
   be
     do
       y
Smobedoy

Character (Length: 9)
C
 ah
   ar
     tc
       er
Cahartcer

Stack Exchange! (Length: 15)
S
 at
   kc
     E
       cx
         ah
           gn
             e!
SatkcE cxahgne!

Rules

Input/output can be taken/given in any convenient format
The input will not contain newlines
Minimum input length is 4
Input will only contain printable ASCII characters

Scoring
This is code-golf, so the answer with the lowest bytes wins.
Sorry about the last test case everyone. It's fixed now

Are we allowed to modify the input and make it the output?

@JL2210 As stated in the challenge, input and output can be taken and given in any convient format. So if modifying the input and making it the output makes this challenge easier, then go ahead and do so!

Bonus challenge: make a program that still works when ran through the swapping process.

I'm not familiar with the convention in Python, strings are immutable, while lists are not. Can I take a list and output a list instead of string?

@justhalf As stated in the challenge, input and output can be taken and given in any convenient format. So if taking and outputting a list is easier for you, feel free to do so.

Why no explaining the rickroll testcase?

@Joao-3 because it'd be too long an explanation to be useful.

Haskell, 31 bytes
f(a:b:c:d:e)=a:c:f(b:d:e)
f x=x

Try it online!
Avoids having to special-case omitting the first character by having extracting it be part of the recursive definition.

brainfuck, 28 bytes
,.,[>,>,[<.[-]<.>>>]<<[.>]>]

Try it online!
First, we print the first character. Then we read the second character and enter the main loop. (,.,[)
When entering the main loop, we expect the first character of a pair to be in the current cell, and we read the next two into the next two cells (>,>,). The tape then looks like this:
[pair1] [pair2] [nextpair1] [0]
                     ^

Then, if nextpair1 exists, we know there's going to be at least one character after the current pair, so we can output the two characters in this current pair in reverse ([<.[-]<.>>>]) – the triple > at the end moves us to the location after nextpair1 to break out of the loop. Otherwise, we're at the end of the string, so we go back to pair1 (<<) and print as many characters as we received in order ([.>]).
The main loop will end here if this was the end of the string (>]). If not, recall that we ended at the [0] in the diagram above after the check to see if nextpair1 existed. So the <<[.>] would have brought the pointer to pair2 (which was cleared) instead of pair1, and then >] restarts the main loop, but with the cursor pointing at nextpair1, which is exactly what we want.

Wow. That's really impressive.

Retina, 12 bytes
V`^.|..(?=.)

Try it online! Link includes test cases. Explanation: V reverses each match. The first character is matched separately, then characters are matched in pairs as long as there is still one character left that is unreversed.

Jelly, 8 7 bytes
Ḣ,Ṫjṭ2/

Try it online!
A full program taking a string as its argument and printing the swapped string. Thanks to @JonathanAllan for saving a byte!
Explanation
Ḣ       | Head
 ,Ṫ     | Paired with tail
   j    | Join with:
    ṭ2/ | The remainder, pair wise reduced by tacking the left item in the pair to the end of the right

Damn this is awesome

Ḣ,Ṫjṭ2/ saves a byte. (I like the nine: J’!Œœ§Ṃœ?)

Python 2, 49 bytes
f=lambda s:s[3:]and s[:3:2]+f(s[1:5:2]+s[4:])or s

Try it online!
Based off my Haskell answer. I tried a more direct port using splatted input, but it was clunky:
57 bytes
f=lambda a,b,c,*d:d[1:]and a+c+f(b,*d)or a+b+c+''.join(d)

Try it online!

@Mr.Xcoder Thanks, fixed.

Do you need the f= part?
In this answer it doesn't include the f= part.

@justhalf I do because I have a recursive call to f.

Ah, I see. Anyway, nice trick with the recursion! I can only match your second version with my answer due to the return and the function definition.

APL (Dyalog Extended), 27 20 bytesSBCS
Anonymous tacit prefix function. Requires ⎕IO←0.
⊢⊇⍨∘⍋≢⌊1+⍳∘≢+2×2|⍳∘≢

Try it online!
Explanation and walk-through for "Somebody" and "Character":
⍳∘≢ the indices of the length; [0,1,2,3,4,5,6,7], [0,1,2,3,4,5,6,7,8]
2| two-mod of that; [0,1,0,1,0,1,0,1], [0,1,0,1,0,1,0,1,0]
2× twice that; [0,2,0,2,0,2,0,2], [0,2,0,2,0,2,0,2,0]
⍳∘≢+ add the indices of the length to that; [0,3,2,5,4,7,6,9], [0,3,2,5,4,7,6,9,8]
1+ increment that; [1,4,3,6,5,8,7,10], [1,4,3,6,5,8,7,10,9]
≢⌊ the minimum of the length and that; [1,4,3,6,5,8,7,8], [1,4,3,6,5,8,7,9,9]
⍋ the grade (the indices that would sort it) of that; [0,2,1,4,3,6,5,7], [0,2,1,4,3,6,5,7,8]
⊢⊇⍨∘ use that to reorder the string; "Smobedoy", "Cahartcer"

Perl 6 -p, 26 bytes
s:g[^.||)>..$||..]=$/.flip

Try it online!

Seems to fail for odd number of chars. For instance heidi and heidila.

@KjetilS. Thanks, fixed.

Ruby, 42 bytes
f=->s{s[/(.)(.)(.)(.+)/]?$1+$3+f[$2+$4]:s}

Try it online!

If you want, cribbing the Retina solution directly saves 5 bytes or you could enable -p mode to drop it all the way down to 30 bytes.

This would be unfair, it's a completely different idea.

Understandable. It seems histocrat has taken that approach for their Ruby solution, and even shorter than my suggestion.

Brain-Flak, 48 40 bytes
({}<{({}<({}<>)>)<>}<>{{({}<>)<>}{}}<>>)

Try it online!
This doesn't work for strings that contain null bytes (unless the null byte is the first byte of the string).
Explanation
({}<...>) Store the first element for later
  {({}<({}<>)>)<>}... Move the stack over in twos (preserving the order of each pair moved)
    <>{...{}}<>
      {({}<>)<>} Move everything back in ones

The one complex part is the <>{...{}}<>.  Since moving over in twos can pick up an extra zero from the bottom of the stack we need to removing when bringing things back.  Conveniently our main loop will stop when it hits a zero, so when it hits a zero we destroy that zero and, if the next thing is not zero we try again.
This means we will only stop if there are two zeros in a row, which since the input cannot contain zeros, will only occur at the bottom of the stack.  In the process we will get rid of any zeros that are present, which fixes our extra zero issue.
Works for all inputs, 114 112 bytes
({}<([](())){({}[()]<(()[{}])>)}({}{}<([]){{}({}<({}<>)>)<>([])}>{}<>){(<{}({}<{}>)>)}{}([]){{}({}<>)<>([])}<>>)

Try it online!
Nearly all of the code is devoted to making this work for even length inputs.

C++ (clang), 117 ... 82 80 bytes
#import<map>
#define f(s)for(int i=1;i<s.size()-2;)s[i++]^=s[i++]^=s[i+1]^=s[i];

Try it online!
Saved 11 bytes thanks to @AZTECCO!!!
Saved 2 bytes thanks to @ceilingcat!!!

Haskell, 40 bytes
f(a:b:c:d)=b:a:f(c:d)
f x=x
g(a:b)=a:f b

Try it online!
xnor has a shorter version of this answer that combines f and g into a single function.

Python 3, 62 bytes
lambda x:x[0]+re.sub("(.)(.)",r"\2\1",x[1:-1])+x[-1]
import re

Try it online!

05AB1E, 14 bytes
¦¨2ô€RJ¹θ¹н.ÁJ

Try it online!
¦¨2ô€RJ¹θ¹н.ÁJ
¦¨             # Delete the first and last letter
  2ô           # Break into groups of 2
    €R         # Reverse each of them
      J        # Join it back together
       ¹θ¹н    # Push the last and first letter of the input
           .Á  # Rotate stack, so the first letter is first
             J # Join the items in the stack

€R can be í. Also, by using the ć builtin with a swap, you won't need the ¹н.Á portion: ćs¨2ôíJ¹θJ (10 bytes)

Japt, 11 bytes
h1Ué ¤ò mÔq

Try it
h1Ué ¤ò mÔq     :Implicit input of string U
h1              :Overwrite from the 1st (0-indexed) character on with
  Ué            :  Rotate U to the right
     ¤          :  Slice off the first 2 characters
      ò         :  Split into pairs
        m       :  Map
         Ô      :    Reverse
          q     :  Join

Ruby -pl, 27 bytes
gsub /^.|..(?=.)/,&:reverse

Try it online!
Alternate solution with the same bytecount, but a regex nobody else has used yet:
gsub /(^|.)(.(?=.))/,'\2\1'

Try it online!

-l mode is not needed at all; the program works just fine with just -p.

J, 24 19 bytes
C.~[:}:_2<@|.\#\@}.

Try it online!
Creates the boxed indexes representing the cyclic form of the permutation we need (bookeeping), and then applies it C. to the input.

JavaScript (Node.js), 40 bytes
f=s=>s[3]?s[0]+s[2]+f(s[1]+s.slice(3)):s

Try it online!
JavaScript (Node.js), 41 40 bytes
-1 bytes thanks to Arnauld
s=>s.replace(/(?!^)(.)(.)(?=.)/g,"$2$1")

Try it online!

You can use (?!^) instead of (?<=.). See this answer on SO.

Actually I think @histocrat's regex might be even shorter still.

Gema, 15 characters
\A?=?
??\P?=$2?

The only interesting point here is the use of

\P       Position -- leave input stream here after the template matches

Sample run:
bash-5.0$ echo -n 'School' | gema '\A?=?;??\P?=$2?'
Shcool

Try it online! | Try all test cases online!

C (clang), 51 48 bytes
f(char*s,z){*++s^=*s^=s[1]^=*++s;z>5&&f(s,z-2);}

Try it online!
A recursive solution that modifies the original string
Saved 3 thanks to @ceilingcat suggestion to use ^=

Python 3, 57 bytes
def f(s):s[1:-2:2],s[2:-1:2]=s[2:-1:2],s[1:-2:2];return s

Try it online!
Accepts a list and returns a list.
The idea is to simply take the alternating slices and swap them.
Do let me know if the boilerplate stuff can be shortened in Python submissions.

x86-16 machine code, 13 bytes
Unassembled listing:
 46         INC  SI         ; skip first char
 8B FE      MOV  DI, SI     ; point DI to string
 D1 E9      SHR  CX, 1      ; divide counter by 2 with round down
 49         DEC  CX         ; skip last char
        CLOOP:
 AD         LODSW           ; load next two chars
 86 E0      XCHG AH, AL     ; reverse chars
 AB         STOSW           ; store next two chars
 E2 FA      LOOP CLOOP      ; keep looping
 C3         RET             ; return to caller

Input/output string in [SI], length in CX.
PC-DOS test program output:

Fortran (GFortran), 125 bytes
character(99)a,b(99)
read('(a)'),a
j=len_trim(a)
b=[a(1:1),(a(i+1:i+1),a(i:i),i=2,j-1,2),a(j:j)]
print*,(b(i)(1:1),i=1,j)
end

Try it online!
Shame string manipulation in Fortran is so wordy as every substring needs two references. The main magic is mapping a to a character array via:
[a(1:1),            ! Prepend first char
(a(i+1:i+1),a(i:i), ! Swap a(i+1) for a(i)
  i=2,j-1,2)        ! For i in 2..n-1
,a(j:j)]            ! Append last char

J, 48 bytes
Man, I love J
(1{.]),([:,[:(|."1)_2[\1}.]}.~_1-2|#),]{.~_1-2|#

Try it online!

Burlesque, 17 bytes
rt2cog_j)<-++.+RT

Try it online!
rt  # Rotate the string left
2co # Split into chunks of 2
g_j # Take pair of first and last out
)<- # Reverse each chunk
++.+# Join everything back together
RT  # Rotate the string right

For even length input only you can shave a single character:
RT2col_)<-++.+RT

Zsh, 74 71 bytes
Found a more idiomatic Zsh solution. Try it online!
w=$1;printf $w[1]${w[2,$#w-1]//(#m)(?)(?)/$MATCH[2]$MATCH[1]}${w:$#w-1}

74 bytes:
w=$1;printf $w[1];for i ({2..$[$#w-2]..2})printf $w[i+1]$w[i];<<<${w:$i+1}

SNOBOL4 (CSNOBOL4), 104 bytes
 P =LEN(1)
 INPUT P . F REM . S
S S P . X P . Y REM . S
 F =F Y X
 GT(SIZE(S),2) :S(S)
O OUTPUT =F S
END

Try it online!

Charcoal, 20 bytes
§θ⁰Ｆ⪪✂θ¹±¹¦¦¦²⮌ι§θ±¹

Try it online! Link is to verbose version of code. Works with strings of at least 2 characters. Explanation:
§θ⁰

Print the first character of the string.
Ｆ⪪✂θ¹±¹¦¦¦²

Split the inner slice of the string into 2-character substrings.
⮌ι

Print each substring reversed.
§θ±¹

Print the last character of the string.

Pip, 17 15 bytes
a@-,2JWVRVUWTMa

Try it online!
Seems like there's gotta be a shorter way, but I haven't found it yet. Well, this is a bit shorter. Also, I think it's the longest run of capital-letter builtins I've ever used. :^P
Explanation
a@-,2JWVRVUWTMa
   ,2            Range(2): [0; 1]
  -              Negate: [0; -1]
a@               Use those values to index into the input string, giving a list
                 containing the first and last characters
     J           Join that list on the following expression:
              a  The input string
            TM   With first and last characters trimmed off
          UW     Unwoven into a list of two strings: the characters at even indices, and
                 the characters at odd indices
        RV       Reverse, putting the string of odd-indices characters first
      WV         Weave back together

Worked example with input abcdefg:
a                "abcdefg"
 @-,2            ["a" "g"]
            TMa  "bcdef"
          UW     ["bdf" "ce"]
        RV       ["ce" "bdf"]
      WV         "cbedf"
     J           "acbedfg"

Red, 95 76 bytes
func[s][prin take s t: take/last s
foreach[a b]s[prin any[b""]prin a]prin t]

Try it online!
Directly prin(t)s the characters instead of returning a string.

Java (JDK), 43 bytes
s->s.replaceAll("(?<=.)(.)(.)(?=.)","$2$1")

Try it online!
Without much API, 60 bytes
s->{for(int i=1;i<s.length-2;)s[i]^=s[++i]^(s[i]=s[i++-1]);}

Try it online!

As @Arnauld suggested to @ShieruAsakoto, you should be able to use (?!^) instead of (?<=.).

Actually I think @histocrat's regex might be even shorter still.

Keg, 16 bytes (SBCS)
The same program as below, with extra simplifying-ops added.
,(!½!2%¬-|$,,)(,

Try it online!
Keg -ir, 18 bytes
You know, Jono's challenges are definitely easily doable in Keg.
,(!2/1!2%--|$,,)(,

Try it online!
Explanation
                   # Take an input from STDIN
,                  # Step 1. Output the first item.
 (!2/              # Repeat half of the length-of-stack times
     1!2%--        # subtract by 1 if that's odd
           |$,,    # Swap & output the two items
               )(, # Output the remaining items

Wren, 73 bytes
Did some simple optimizations
Fn.new{|x|x[0]+(1..x.count-3).map{|y|x[y%2==0?y-1:y+1]}.join()+x[-2..-1]}

Try it online!

Emacs, 7 keystrokes
C-f <f3> C-f C-t M-0 <f4> C-/

or 9 keystrokes without fn-keys
C-f C-x ( C-f C-t M-0 C-x ) C-/

C-f move forward one character
<f3> start keyboard macro
C-f
C-t transpose the character under the cursor with the one before it
M-0 call the next command with numeric argument 0
<f4> run this macro and end definition, with argument 0, this macro is run indefinitely until a break occurs, i.e. when C-f goes past the last character
C-/ undo the last change, i.e. the last transpose, so that the end condition is fulfilled; this saves some keystrokes over vim because u undo after a recursive macro call undos all the runs of the macro instead of the last change

Rust, 52 bytes
|s:&mut[u8]|for i in 1..s.len()/2{s.swap(2*i-1,2*i)}

Try it online!
An anonymous function, takes a mutable reference to a bytestring and mutates it in place.

Brachylog, 12 bytes
~bġ₂↔ᵐ↔ᵗ↔ʰcb

Try it online!
Doesn’t feel like a very efficent use of bytes…
Explanation
~b              Append an unknown character at the beginning of the input
  ġ₂            Split the input into groups of 2 characters
    ↔ᵐ          Reverse the order of the 2 characters for all groups
      ↔ᵗ        Reverse again only for the last one
        ↔ʰ      Reverse again only for the first one
          c     Concatenate into a string again
           b    Behead: remove the unknown character

The way ġ₂ works is that it will construct groups of 2 consecutive characters from left to right, so we need to pair the first character with something random, to avoid it getting swapped with the second character. If the length of the string is even, then the last group will only have 1 character instead of 2 (since we added a random character), instead of having the predicate fail. The rest of the program (↔ etc.) works as expected on a group of only one character.

Forth (gforth), 67 bytes
: f 2dup 1 -3 d+ bounds do i 1+ c@ i c@ i 1+ c! i c! 2 +loop type ;

Try it online!
Overwrites the input string
Code Explanation
: f          \ start a new word definition
  2dup       \ make a copy of the string address and length
  1 -3 d+    \ add 1 to address and subtract 3 from length (skip first and last)
  bounds     \ get the starting and ending address of shortened string
  do         \ loop from addr+1 to addr+length-3
    i 1+ c@  \ get value at next char
    i c@     \ get value at current char
    i 1+ c!  \ write current char to next char
    i c!     \ write next char to current char
  2 +loop    \ end loop, move 2 chars ahead
  type       \ output string (using copied address & length)
;            \ end word definition

Perl 5, 26 bytes
s/(?<=.)(.)(.)(?=.)/$2$1/g

Try it online!
Look-behind and look-ahead to the rescue.

ShieruAsakoto and histocrat seem to have shorter regexes.

C# (Mono), 212 bytes
using System;class b{static void Main(string[] z){var s=z[0];Action<string>w=Console.Write;w(s[0].ToString());int i;var l=s.Length;for(i=2;i<=l-2;i+=2)w(new string(new char[]{s[i],s[i-1]}));w(s.Substring(i-1));}}

Try it online!
Because why not?

Vyxal Ṫ, 6 bytes
ḣ2ẇR÷Ṙ

Try it Online!
Note that the test suite simulates the Ṫ flag.
-3 thanks to lyxal

Try it Online! for 6

Try it Online! for a test suite for the 6 byter

Ly, 19 bytes
ispro[y,[pfo0]po]lo

Try it online!
ispro[y,[pfo0]po]lo
isp                  # Read input onto the stack, stash the last char and delete it
   ro                # Reverse the stack, print the first char
     [          ]    # Loops until the stack is empty
      y,             # Push the stack length and decrement by 1
        [p  0]p      # If-then, code runs if there's 2+ entries on the stack
          fo         # Flip the top two entries and print the top of stack
               o     # Print the top of the stack
                 lo  # Restore the "last char" from back cell and print

ispro...why is checking if the input is professional useful here? :P +1 from me

Thunno 2 j, 7 bytes
Ṫsḣ²ṃ$h

Try it online!
Explanation
Ṫsḣ²ṃ$h  # Implicit input
Ṫs       # Extract the last character
  ḣ      # Remove the first character
   ²     # Break into pairs
    ṃ    # Reverse each inner pair
     $h  # Push the first character
         # of the input again
         # Join the stack into a string
         # Implicit output

Tsh? Isn't that the username of someone who golfs in javascript? What you doing golfing in javascript? I thought you golfed in thonnu 2. Goofy ahh nerd.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Average number of strings with Levenshtein distance up to 3
The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one.  Given a binary string \$S\$ of length \$n\$, we are a interested in the number of different strings of length \$n\$ which have distance at most \$3\$ from \$S\$.
For example, if \$S = 0000\$ there are four strings with Levenshtein distance exactly \$3\$ from \$S\$, six with distance exactly \$2\$, four with distance exactly \$1\$ and exactly one with distance \$0\$. This makes a total of \$15\$ distinct strings with distance at most \$3\$ from the string \$0000\$. The only string with distance greater than \$3\$ is \$1111\$.
However, this number depends on the value of \$S\$. For example if \$S = 0010\$ then the number of distinct strings with distance at most \$3\$ is \$16\$, in other words all of them.
For this task the input is a value of \$n \geq 3\$. Your code must output the average number of binary strings of length \$n\$ which have Levenshtein distance at most \$3\$ from a uniform and randomly sampled string \$S\$.  Your answer can be output in any standard way you choose but it must be exact.
Examples
n = 3. Average = 8
n = 4. Average = 15 1/2
n = 5. Average = 28 13/16
n = 6. Average = 50 15/16
n = 7. Average = 85 23/64
n = 8. Average = 135 27/32
n = 9. Average = 206 77/256
n = 10. Average = 300 181/256
n = 11. Average = 423 67/1024
n = 12. Average = 577 99/256
n = 13. Average = 767 2793/4096.
n = 14. Average = 997 3931/4096.
n = 15. Average = 1272 3711/16384.

Score
Your score is the highest value of \$n\$ you can reach.

GAP and the automata package
The average number is the number of pairs of words of length \$n\$ with Levenshtein distance up to three, divided by \$2^n\$.
It is not very difficult to construct an nondeterministic finite automaton over the alphabet of pairs of bits that accepts the word \$(a_1,b_1)(a_2,b_2)\dots(a_n,b_n)\$ iff the binary words \$a_1a_2\dots a_n\$ and \$b_1b_2\dots b_n\$ have Levenshtein distance up to three. My version uses 14 states. This automaton can be transformed into a minimal deterministic one, which has 39 states. From its transition function we can get a matrix that describes the number of ways we can get from one state to another. Now counting the number of ways we can get from the initial state to some accepting state is just a matter of multiplication.
The implicit recurrance could be simplified because some values are always equal, and it might be solved to give a closed formula, but it seems to be good enough as is.
LoadPackage("automata");

nfa := Automaton("nondet", 14, 4,
     [[[1,5,9],[2,7,11],3,4,[5,13],[7,13],[7,14],14,
       [9,13],[11,13],[11,14],14,13,14],
      [[2,5,10],[3,7,12],4,0,[7,14],[5,14],0,7,
       [10,14],[12,14],12,0,14,0],
      [[2,6,9],[3,8,11],4,0,[6,14],[8,14],8,0,
       [11,14],[9,14],0,11,14,0],
      [[1,6,10],[2,8,12],3,4,[8,13],[6,13],14,[8,14],
       [12,13],[10,13],14,[12,14],13,14] ],
     [1], [1..14] );

dfa := MinimalizedAut(nfa);

size := NumberStatesOfAutomaton(dfa);;

mat := NullMat(size, size);;
for row in TransitionMatrixOfAutomaton(dfa) do
  for i in [1..size] do
    mat[i][row[i]] := mat[i][row[i]]+1;
  od;
od;

init := 0 * [1..size];;
init[InitialStatesOfAutomaton(dfa)[1]] := 1;;

fin := 0 * [1..size];;
for i in FinalStatesOfAutomaton(dfa) do
  fin[i] := 1;
od;

f := function(n)
  local res, intpart, fraction;
  res := init * mat^n * fin / 2^n;
  intpart := Int(res);
  fraction := res-intpart;
  Print("n = ", n, ". Average = ", intpart);
  if fraction <> 0 then
    Print(" ",fraction);
  fi;
  Print(".\n");
end;

Try it online!
Put it in a file, start gap and read the file with a command like Read("l3.gap");, then try something like f(20); or for i in [0..100] do f(i); od;.
Here are some results:
n = 0. Average = 1.
n = 1. Average = 2.
n = 2. Average = 4.
n = 3. Average = 8.
n = 4. Average = 15 1/2.
n = 5. Average = 28 13/16.
n = 6. Average = 50 15/16.
n = 7. Average = 85 23/64.
n = 8. Average = 135 27/32.
n = 9. Average = 206 77/256.
n = 10. Average = 300 181/256.
n = 11. Average = 423 67/1024.
n = 12. Average = 577 99/256.
n = 13. Average = 767 2793/4096.
n = 14. Average = 997 3931/4096.
n = 15. Average = 1272 3711/16384.
n = 16. Average = 1594 3985/8192.
n = 17. Average = 1968 48645/65536.
n = 18. Average = 2398 65249/65536.
n = 19. Average = 2889 64891/262144.
n = 20. Average = 3443 16339/32768.
n = 30. Average = 13385 268434611/268435456.
n = 40. Average = 34128 68719475971/137438953472.
n = 50. Average = 69670 281474976708241/281474976710656.
n = 60. Average = 124013 36028797018963093/72057594037927936.
n = 70. Average = 201155 295147905179352821071/295147905179352825856.
n = 80. Average = 305098 75557863725914323416001/151115727451828646838272.
n = 90. Average = 439840 309485009821345068724773101/
309485009821345068724781056.
n = 100. Average = 609383 9903520314283042199192993177/
19807040628566084398385987584.
n = 1000. Average = 660694208
669692879491417075592765655662501131600878007315958504652343992731469406953085\
076558248986759809911329746670573470716765741965803557696277249036098418660925\
245910485926514436588817162816398196367372136384565404686473871329212422972447\
846496629816432160699779855408885478776864478289024177325353755091/
133938575898283415118553131132500226320175601463191700930468798546293881390617\
015311649797351961982265949334114694143353148393160711539255449807219683732185\
049182097185302887317763432563279639273474427276913080937294774265842484594489\
5692993259632864321399559710817770957553728956578048354650708508672.
n = 10000. Average = 666066942458
[fractional part removed]

Pari/GP, 51 bytes
All the eigenvalues of the matrix are integers (could I have known or expected that?), and I found this formula for \$n\ge 2\$:
f(n)=(40+6*n-4*n^2)/2^n-83/2+331/12*n-6*n^2+2/3*n^3

Try it online!

Wow!  Can this be extended to larger values than 3 easily? It looks like the part you did by hand is the original NFA.  I hope this doesn't put other people off answering in different languages.

It should be possible, I wouldn't say easily, but also not too difficult. I think I'd create the NFA by program. The number of states will increase exponentially: the possibility of insertions and deletions means that the words get out of sync, so $a_i$ has to be compared with e.g. $b_{i-1}$, so the state needs to remember the last value. The nice thing about distance 3 is that there is at most one insertion and one deletion. For bigger distances, the strings can get more out of sync, and more history has to be preserved in the state.

12 states are enough for the NFA: states 3 and 13 can be joined, and states 4 and 14 can also be joined. Of course that doesn't change the DFA and therefore makes almost no difference. (This is a result of thinking about generalisation.)

That sounds promising.. If you feel I should ask a separate question about generalisation please do let me know as I am very interested in it.

The bounty is definitely yours as soon as I am allowed to give it.  What is the matrix explicitly? It would be interesting to see if we can see why the eigenvalues are integers.

To see the matrix, replace the footer in the first TIO link with Print(mat);. By construction it is a matrix with nonnegative integers as entries, all rows sums equal to 4 and some symmetries from related states.

Thank you very much.

What is your current thinking about how hard n=4 would be? I am tempted to ask a follow-up question.

I think $n=4$ would not be difficult, but I'm not completely sure if the computation of the DFA is feasible. I wonder if it is too similar for a question here. BTW, I like your other Levenshtein question. I always like variations of questions I've put a lot of effort into.

Thank you in relation to the other question. I am hopeful for some more interesting answers to that. I will wait a bit before posing the n = 4 version which might help its acceptance. I like to ask variants of hard questions for exactly the reason you suggest.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
How Shuffled is this Sequence?
Given a sequence \$S\$ with length \$n\$ of exactly one each of whole numbers from \$1\$ to \$n\$, your task is to return a number \$\sigma\$ indicating how shuffled it is.
Definition of shuffledness
Humans perceive shuffling randomness locally [Citation Needed], so the shuffledness of a sequence is based on the ability to find various patterns within each sliding window \$W\$ of 5 consecutive elements of the sequence (\$W = \{S_x, S_{x+1},  S_{x+2}, S_{x+3}, S_{x+4}\}\$ for some \$x\$- these will overlap, as each \$x\$ that is at least \$4\$ less than \$n\$ is considered). For each window of 5 elements, add a point for each test of the following that fails: (Note the 1-indexing due to the use of mathematical notation)

Apply the following tests to the whole window:

\$W\$ is monotonic
\$W\$ is in ascending order
Some permutation of \$W\$ is a run of sequential integers (e.g. 1, 2, 3, 4, 5)
For all \$W_i\$ where \$i>1\$, \$W_i = W_{i-1}+k\$ for some integer \$k\$.

This corresponds to regular linear intervals

For all \$W_i\$ where \$i>1\$, \$W_i = W_{i-1}+ax+k\$ for some integers \$k, a\$, where \$x=i\$.

This corresponds to regular quadratic intervals (which could also be linear)

Apply the same tests for subwindows where 1 or 2 elements have been removed (if any one of those reduced windows passes a particular test, this step passes. Only count one failure when a test fails for all reduced windows.
Apply the same tests for windows with some pair of adjacent elements optionally swapped (this step will pass if all tests passed for the whole unmodified window) Replace test 3 with the following:

\$W\$ is an ascending or descending sequence of sequential integers (e.g. 5, 4, 3, 2, 1)

Notes

Ascending sequential sequences will pass every test for all windows and therefore be scored as \$0\$
Descending sequential sequences will pass all tests except the "ascending" one for all windows and will therefore be scored as \$3(n-4)\$
The naive maximum shuffledness is \$15(n-4)\$

Examples

[1, 5, 3, 2, 4]

All elements:

Passes test 3
Fails all other tests (+4)

Elements removed:

Passes tests 1, 2, 5 with [1, 2, 4] (remove 5 and 3)
Passes test 3 with [5, 3, 2, 4] (remove 1)
Fails test 4 (+1)

Elements swapped:

Fails all tests (+5)

Test 3 fails because it requires the elements to be in order for this case only

\$\therefore \sigma = 10\$

[1, 2, 4, 3, 5]

All elements:

Passes test 3
Fails all other tests (+4)

Elements removed:

All tests pass with [1, 2, 3] (remove 4, 5)

Elements swapped:

Passes all tests (swap 4, 3)

\$\therefore \sigma = 4\$

[3, 6, 9, 12, 15]  (a sliding window)

All elements:

Passes tests 1, 2, 4, 5
Fails test 3 (+1)

Elements removed: same (+1)
Elements swapped: same (+1) (no swap)
\$\therefore \sigma = 3\$

[8, 12, 13, 11, 6] (a sliding window)

All elements:

Passes test 5 (\$a=-3, k=4\$)
Fails all other tests (+4)

Elements removed:

Passes tests 1, 2, 5 with [8, 12, 13] (remove 11, 6)
Passes test 3 with [12, 13, 11] (remove 8, 6)
Fails test 4 (+1)

Elements swapped: same as all elements (+4) (no swap)
\$\therefore \sigma = 9\$

[2, 4, 6, 1, 3, 5] (whole sequence)

First window: ([2, 4, 6, 1, 3])

All elements: Fails all tests (+5)
Elements removed:

Passes tests 1, 2, 4, 5 with [2, 4, 6]
Passes test 3 with [2, 1, 3]

Elements swapped: Fails all tests (+5)

Second window: ([4, 6, 1, 3, 5])

All elements: Fails all tests (+5)
Elements removed:

Passes tests 1, 2, 4, 5 with [1, 3, 5]
Passes test 3 with [4, 6, 5]

Elements swapped: Fails all tests (+5)

\$\therefore \sigma = 20\$

Rules and such

Standard IO rules, loopholes, etc
You must handle sequences of up to 1000 elements long
You may assume \$S\$ is at least 5 elements long
No validation necessary. You may assume that all inputs contain exactly one each of every whole number from \$1\$ to \$n\$
Shortest code wins!

In the first example, how can it fail all tests for the elements swapped bit?

How is $W_x$ defined?

@NickKennedy The swapped elements test requires the run to actually be in order

@flawr $W_x$ is the $x$th element of $W$

@Beefster I'd suggest adding that in a small comment, or writing something like $W = (W_1,W_2,\ldots)$. (It was confusing for me as $x$ is an unusual variable to use for indexing.)

Jelly, 71 65 bytes
J4Ṭ;-+ʋ€ịṭ@Wẋ¥€3ṭœcJ;2/Ṣṭ,`Ɗ€€ƲḊ,UṢƑ€o\ƲI,I$E€ƊIỊẠƊ3ƭ€€€»/€¬µ5ƤFS

Try it online!
A monadic link taking a list if integers and returning an integer. I’m sure this can be shortened further.
Explanation
...µ5Ƥ   | Run the main chain (below) for each 5-integer-long infix of the list
      F  | Flatten list
       S | Sum

Main chain
This generates the lists for the each set of tests. To deal with the variation in test 3, there are 3 copies made of each innermost list. For the first and second sets of tests, the last copy of each innermost list is sorted, while for the third set of tests it is not.
Main chain part 1 (generates swapped lists for third set of tests)
J                | Sequence along list [1,2,3,4,5]
 4    ʋ€         | Do the following as a dyad for each of 1,2,3,4 with 1,2,3,4,5 as the right argument:
  Ṭ              | - Convert to logical list with 1 at the relevant index [[1],[0,1],[0,0,1],[0,0,0,1]]
   ;-            | - Concatenate -1 to this
     +           | - Add (to [1,2,3,4,5])
        ị        | Index into original list
         ṭ@      | Tack onto end the original list
           Wẋ¥€3 | Repeat each inner list 3 times

Main chain part 2 (generates lists for first and second sets of tests)
ṭ             Ʋ  | Tack output of part 1 onto the following:
 œcJ             | - Combinations of lengths 1,2,3,4,5
    ;2/          | - Pairwise reduce using concatenation
           Ɗ€€   | - Following as a monad for each innermost list:
       Ṣ         |   - Sort
        ṭ,`      |   - Tacked onto the list paired with itself
               Ḋ | - Remove first (i.e. the combinations of lengths 1 and 2)

Main chain part 3 (runs the tests)
                   3ƭ€€€     | For each innermost list, do one of the following three in turn:
       Ʋ                     | - Tests 1 and 2
,U                           |   - Pair with reversed list
  ṢƑ€                        |   - Check whether each invariant if sorted
     o\                      |   - Cumulative or
              Ɗ              | - Tests 4 and 5
        I                    |   - Increments (test 4)
         ,I$                 |   - Paired with increments of increments (test 5)
            E€               |   - Check if all equal for each of these
                  Ɗ          | - Test 3
               I             |   - Increments
                Ị            |   - Absolute value <= 1
                 Ạ           |   - All
                        »/€  | Reduce each using max - picks the best results for each test for each set of tests
                           ¬ | Not (vectorises)


text:
Swaps to Sort an Array
You are given an array \$A\$, which may contain duplicate elements. In each swap, you may swap the value of any two indices \$i, j\$ (i.e. switch the values of \$A_i\$ and \$A_j\$). What is the least amount of swaps needed to sort the array, and what are the corresponding swapped indices?
Scoring
This is code-golf, so shortest code wins. However, your program must terminate in reasonable time (less than 10 seconds) for any array \$A\$ with less than 1000 elements.
Input
The array \$A\$, in any necessary form.
Output
A list of swaps, with each swap being a pair of numbers, in sequential order - first pair in list is swapped first, in any necessary form.
In the output, the numbers should all represent indices. You may output the answer either one-indexed or zero-indexed, but my samples will use one-indexing.
The answer might not be unique. However, your answer should still have the same length as the optimal sequence of swaps.
Test cases
[4,3,2,1] => [(1,4),(2,3)]
[1,3,2,3] => [(2,3)]
[1,2,1,3,2,3] => [(2,3),(4,5)]
[1,2,3,4] => []
[4,2,5,1,3,3] => [(2,6),(1,5),(1,4),(2,3)]

Yes, yes, and yes (although there may be more than one optimal sequence, yours should still have the same length as the optimal sequence)

Can you please add more and longer test cases?

@Jonah Done. Although the samples may be quite a bit suggestive...

Per @Neil's comment on my answer, can you please add the test case 4,5,2,1,3,3 with expected length 4. (1 5)  (0 4)  (0 3)  (1 2) is one possible (0-indexed) solution.  This test case ensures that you can't just use the same algorithm that works for the "no repeats" case.

@BaaingCow are you sure this is possible within 10 seconds when there are multiple identical numbers, as per comments below the J and Jelly answers?

On second thought, it seems that my reference solution is wrong - whoops :| My code also returns an swap sequence of length 5 for 4,5,2,1,3,3. Are challenges with no reference solution allowed?

An more readable algorithm is available at https://stackoverflow.com/questions/15152322/compute-the-minimal-number-of-swaps-to-order-a-sequence/15152602#15152602 However, it doesn't handle arrays with duplicates well. So it could perhaps be tweaked to do that. Or another approach is necessary.

@BaaingCow You don't need a reference solution, but you do need correct test cases.  I believe my edited answer is now correct, and I included a reference version of the algorithm.  It found shorter solutions for both of the longer test cases you had previously posted.

Jelly, 51 43 bytes
ṪµṢ,$Ḣ©€E¬a="ʋṚƊ×\ẸÞṪTḢ,®ṛ¦Ẹ}¡@¥
WÇẸÐ¿FĖẠƇÄ

Try it online!
A pair of links which when called as a monad returns a list of pairs of 1-indexed indices to swap. Based on the clever J algorithm developed by @Jonah, so be sure to upvote that one too!
Explanation
Helper link
Takes a list containing a list of the remaining items to be sorted, optionally preceded by the most recent swap. Takes full advantage of the way that Ḣ (Head) and Ṫ (tail) pop items from a list, which for someone from an R background was something I found took some getting used to when I started using Jelly!
Ṫ                                 | Tail (yields the list of remaining items, and also removes this from the list that Ð¿ is collecting up)
 µ                                | Start a new monadic chain
  Ṣ,$                             | Pair the sorted list with the unsorted remaining items
     Ḣ©€                          | Take the head of each, removing from the list and storing each in turn in the register (so the register is left holding the head of the unsorted list)
               Ɗ                  | Following as a monad
             ʋṚ                   | - Following as a dyad, using a list of the remaining sorted and unsorted lists (in that order) as right argument
        E                         |   - Equal (i.e. the head of the unsorted and sorted lists matches)
         ¬                        |   - Not
          a                       |   - And:
              ="                  |     - Equal to zipped right argument (effectively a logical list indicating which of the remainder of the sorted list matched the head of the unsorted and vice-versa)
                ×\                | Cumulative product
                  ẸÞ              | Sort by whether any true
                    Ṫ             | Tail
                     T            | Convert to list of truthy indices
                      Ḣ           | Head (will be 0 if the head of the unsorted and sorted lists matches)
                               ¥  | Following as a dyad, using the remaining unsorted list as right argument
                       ,          | Pair the index to swap with:
                              @   | - Following with arguments reversed:
                           Ẹ}¡    |   - Run following once if index to swap is nonzero:
                        ®ṛ¦       |     - Replace item at index to swap with the original head of the unsorted list that was stored in the register

Main link, takes a list to be sorted
W           | Wrap in a further list
  ẸÐ¿       | While any non-zero, do the following collecting up intermediate results
 Ç          | - Call helper link
     F      | Flatten (will remove the now empty initial list)
      Ė     | Enumerate (pair the index of each with the item)
       ẠƇ   | Keep only those without zeros
         Ä  | Cumulative sum of each pair

Original algorithm that fails with repeated values, 16 bytes
ỤịƬ€`Ṣ€ŒQTịƲṡ€2Ẏ

Try it online!
A monadic link taking a list of integers and returning a list of lists of integers representing the 1-indexed swaps.
Explanation
Ụ                 | Grade the list z up, i.e., sort its indices by their corresponding values.
  Ƭ€`             | For each member of the resulting list, do the following until no new values, using the list of indices itself as the right argument. Keep all intermediate values.
 ị                | - Index into list
           Ʋ      | Following as a monad:
     Ṣ€           | - Sort each list
       ŒQ         | - Logical list, true for original copy of each unique value
         T        | - Indices of truthy values
          ị       | - Index into list
            ṡ€2   | Split each into overlapping sets of 2
               Ẏ  | Join outer together

Inefficient algorithm that is too slow for long lists with lots of repeats, 27 bytes
ĠŒ!€ŒpµFịƬ€`Ṣ€ŒQTịƲṡ€2Ẏ)LÞḢ

Try it online!

Looks like this fails on the same one that mine does: 4 5 2 1 3 3 (courtesy of Neil)

@Jonah indeed. I’ve tried testing the Cartesian product of all permutations of identical ones but it fails for the last two examples because there are too many possibilities. I’ll give it some more thought.

Yep.  I'm stuck on exactly the same thing.

@Jonah what do you think of what I’ve done? I noticed that the problem arose when the items that ultimately needed swapping with the duplicates were not in ascending order from left-to-right, so sort the duplicates on that basis. I’m not sure it will always work though.

I believe this one 4,5,2,1,3,3,10,9,7,6,8,8 can be done in 8.  Ie, sometimes you need it to go one way, sometimes the other way.  Try it online!

@Jonah quite right. I’ll leave my two previous answers up for now; one works for any lists without duplicates, the other works for any list but becomes very slow with multiple repeated values.

My only other idea, which I don't have time to explore atm, is to first remove the "clumped dups", then solve, then add back in the swaps for the clumped dups, because (I think) the clumped dups always move as a chunk of swaps.

@Jonah I haven’t checked, but would this work even for multiple sets of clumped dups which partially swap with each other?

Okay I believe I have a correct algorithm that is fast in all cases.  See my (very ungolfed) edit.  In addition, note that the longer test case anwers provided in the OP were incorrect: My algorithm found shorter solutions.

@Jonah Very clever! I’ve rewritten your algorithm in Jelly. The implementation is different in places, but the overall idea is the same.

Thanks Nick!  I was kinda hoping you'd do a Jelly one -- was curious how compact it would be.  My J solution could be golfed further but I think it will be somewhat long no matter what because these procedural algorithms aren't a great fit for J.

J, 126 bytes
[:>[:{:"1@}./:~(({.@I.@:~:>@{.)({:@](|.@:{`[`]}~;])[,[:(0{*/,&I.{.)(<0{i.@$)*"1{"0 1=|.@])(,:>@{.))^:(-.@-:>@{.)^:a:;&(0 2$'')

Try it online!
Here is the same code in a more procedural form, if you're looking for an explanation of algorithm.
f=. 3 :0
sorting=.y NB. copy of input we'll mutate
sorted=./:~y
swaps=.0 2$''
for_j. i.#y do.
  correct=.j{sorted
  cur=.j{sorting
  if. cur = correct do.
    continue.
  end.
  NB. correctly fill the current idx j
  valid_idxs=.(j<i.#sorting)
  good_j=. valid_idxs * correct = sorting
  NB. will any of these be the correct desitnation for the current elm?
  good_dest=. valid_idxs * cur = sorted
  both=.good_j * good_dest
  use=.(1 e.both) { good_j ,: both
  swap_with=. {.I.use
  swaps=.swaps,(j, swap_with)
  sorting=.(sorting {~ swap_with, j) (j, swap_with)} sorting
end.
swaps
)

Try it online!

original answer, doesn't work for repeats
J, 18 bytes
[:;(2]\])&.>@C.@/:

Try it online!
NOTE: Thanks to Neil for pointing out this currently fails on the test case 4 5 2 1 3 3.

/: Grade up, ie, return the permutation that puts the list into order
C.@ Convert that to cyclic permutation form, which uses boxes
&.> For each of those boxed lists, ie, permutation cycles...
(2]\]) Return all consecutive pairs of two elements.  This gives us the swaps, and it works because J gives the cycle list in descending order.
[:; raze the list of boxes.  This gives us all the swap pairs as a single list of pairs, ie, an N x 2 matrix.

Wow. Can you explain how it works, and what strategy you used to solve this?

@BaaingCow Done.

@BaaingCow Btw, my swaps with this method are all listed in descending order (ie, 3 1 for swapping 1 and 3).  lmk if that's not acceptable, and I'll reverse them.  It only adds a few bytes.

Suppose your input is 4,5,2,1,3,3 (or whatever the ambiguous equivalent would be for your code). What's to stop the code outputting 1,4;4,6;6,2;2,3;3,5?

Excellent catch, @Neil .  The problem is there are multiple valid grade ups bc of the repeats, and they can lead to solns of different length.  I could brute force all of them, which seems excessive.  I think it would be enough to brute force the endpoints of runs of repeats.  Is that the best I could do?

Is this also why the test echo 1 test 3 3 2 3 fails? It should be just 1,3 shouldn't it?  Not 1,3 ; 1,2.

@KjetilS. Yep, basically the algorithm is unreliable for any list with repeats.

@LuisMendo Indeed.  I have edited it with a now much uglier but at least correct solution.  I will re-golf it later.

That was some byte count increase :-)

Wolfram Language (Mathematica), 219 188 184 bytes
F@A_:=MinimalBy[##&@@@f/@#[[1]]&@*(FindPermutation@A~PermutationProduct~#&)/@GroupElements@PermutationGroup[Cycles@*List/@Join@@((f=Partition[#,2,1]&)/@Values@PositionIndex@A)],Length]

Try it online!
-31 bytes thanks to @Chris
-4 bytes by making the code much faster (no more GroupSetwiseStabilizer slowness)
Thanks to @NickKennedy for pointing out that the first version failed on non-unique list entries. The present version is a tour-de-force that calculates the permutation group that leaves the list unchanged, then tries each element of this group to see if it can be used to shorten the result.
This code still goes very slowly on massively duplicated lists.
Explicit code:
A = {4,5,2,1,3,3,10,9,7,6,8,8}
  (* compute the indices of equal elements *)
Q = Values[PositionIndex[A]]
  (* compute the permutation group that leaves A invariant *)
G = PermutationGroup[Cycles@*List /@ Join @@ (Partition[#, 2, 1] & /@ Q)]
  (* find the permutation that sorts A and combine it with every element of G *)
F = PermutationProduct[FindPermutation[A], #] & /@ GroupElements[G]
  (* convert every resulting permutation to the desired form *)
J = Join @@ (Partition[#, 2, 1] & /@ #[[1]]) & /@ F
  (* pick the shortest solutions *)
MinimalBy[J, Length]

Fails the same edge cases that Jonah’s and mine do - see comments above.

Thanks @NickKennedy! Fixed.

well done. However, you’ve now run into the same issue that Jonah and I had with using permutations - the runtime becomes very long for longer inputs with duplicates such as the last two sets in the original question. This answer certainly won’t handle a 1000 length list with lots of duplicates. I’m still waiting to hear from the OP about this, but my suspicion is you can choose between duplicates and a quick run time but can’t have both.

@NickKennedy my suspicion is that this problem needs to be solved in GAP by someone who is well versed in group theory. Maybe there are some group-theoretical shortcuts to be had. Not an easy problem.

not sure if you’ve seen, but there are now working solutions in J and Jelly


text:
Polyglot self-interpreter time
Your task is to make a program which interprets the language it is run in, but also works in many languages.
Let's say you make a Brainfuck-Underload self-interpreglot, as it will be called. Run in Brainfuck, this program should be a Brainfuck interpreter; run in Underload, it should be a Underload interpreter.
Your program should work like the hypothetical given above: given a list of languages L1, L2, L3, L4... up to Ln, it should be an L1 interpreter in L1, an L2 interpreter in L2, an L3 interpreter in L3, up to being an Ln interpreter in Ln.
Your program can handle errors in any way. However, it must never output to STDERR (or closest equivalent) if the input given for interpretation has no errors.
It must output to STDOUT (or closest equivalent) and take input from STDIN (or again, closest equivalent).
You can choose any interpretation of a given language, e.g. if your polyglot works in Brainfuck, it can interpret Brainfuck with finite or unbounded tape. You must specify what interpretations you choose to use for each language.
Programs must have at least 2 characters for this challenge to prevent empty programs from competing.
Functions such as exec and eval are allowed.
Only a Turing-complete subset of a language has to be interpreted.
Different languages have to be interpreted, not different language versions.
Your score is C/(L^3), where C is code length, computed in bytes with UTF-8 encoding, and L is the amount of languages. The lowest score wins: if two winning answers have the same score the one posted earlier wins.
Have fun.

Are functions such as exec and eval allowed? Does the entire language spec have to be interpreted or just a turing complete subset?

Yes and yes. Mostly for non-esoteric languages.

@FlipTack's second question was an "either/or" not a "yes/no"! :D

"In languages without any method of input (e.g. ///) programs may get input through an insertion into the source code" does this make the empty program a valid submission in some languages? https://codegolf.meta.stackexchange.com/a/10553/89930

GolfScript/MathGolf/CJam/Paradoc/FlogScript, 1 byte, score = 1/125 = 0.008
For all stack-based languages, input may be implicitly pushed onto the stack.
The most boring (yet probably the optimal) answer.
Going forward to see what is the most common character choice for an evaluation operator...
~

TIO for MathGolf
TIO for CJam
TIO for GolfScript
What other languages have ~ as an evaluation built-in?

Microscript II

Not adding this language to the polyglot. Because I'm too lazy.
Explanation
~    Evaluate the input

Jelly, 05AB1E, GolfScript 8 bytes, score = \$\frac 8 {27} \approx 0.296\$
.Vq;~
ɠV

Try it online Jelly!
Try it online 05AB1E!
Try it online GolfScript!
In all cases, takes a program in the relevant language from STDIN and executes it, with any output going to STDOUT.

The scoring has been updated, so this is now 23/27 ~ 0.851

Sorry about that. The challenge keeps changing :-/

Keg and Python 3, 19 characters, score = \$ \frac{19}{8} \$
exec(input())
"ø¿ß"

Try it online! (Keg)
Try it online! (Python 3)
Uses the same approach as Nick first did, but with Keg instead.
I'll have to figure out how to add another language to get competitive again.

Clojure/Common Lisp/scheme/bash/ksh/posix sh/zsh/csh/yash/tcsh, 34 33 bytes, score = 33/1000 = 0.033
as low as 0.000327480423 points, see comment
"w";eval $SHELL;exit
(eval(read))

Try it online!
Alternative for 31 bytes but does not work on clojure:
"w";eval $SHELL
#x1(eval(read))

Use (print "hoo") as input and it should work for all lisps.
Try pwd for shells.
lisp
Simple. These lisp dialects seem to all be similar enough to all work for this.
Unfortunately, there is not a TIO for scheme. The only one of these I know is Common Lisp, which I am still learning.
Are the different implementations of CL different enough to be counted separate? Because then. . .
shells
Just evaluates itself, then exits so it won't try to do the lisp part.

This   meta question verifies that a language is defined by its implementations, so my score could be 34/(47^3) = 0.000327480423 with 37 implementations, assuming each one worked -- not to mention different shells

GolfScript/Keg, 6 bytes, score = 3/4 = 0.75
Do we have to use at least one practical language? It doesn't seem to say that in the spec.
ß.~\;

Golfscript
ß     # Odd undefined ops
 .    # Copy the input
  ~   # Evaluate it
   \; # Discard the unevaluated copy

Keg
ß     # Take input & evaluate the input
 .    # Output the result as a number
  ~   # Push a random number
   \; # Escape the ; character

PHP/Python 3/Javascript, 130 bytes, score = 130/27 ~ 4.814
[1//eval(input())
];eval("\x24a=\"/\";eval(`\x24{\x24a}/bin/echo 'eval(fgets(fopen(\"php://stdin\",\"r\")));'`);eval(prompt());");

Try it online - PHP
Try it online - Python 3
For javascript run it in the browser's console, as prompt is not defined in node.
NOTE - you can also put a brainfuck+ook self interpreter in there but it's too big.
Explanation:
Python - the // operator is integer division, so the interpreter tries to calculate it, so it executes eval(input()), and then it errors out (which is allowed according to Should submissions be allowed to exit with an error?).
Javascript - the // is interpreted as a comment, so it gets the array [1]. Then it evals
$a="/";eval(`${$a}/bin/echo 'eval(fgets(fopen("php://stdin","r")));'`);eval(prompt());

And, then
`${$a}/bin/echo 'eval(fgets(fopen("php://stdin","r")));'`

evaluates to //bin/echo 'eval(fgets(fopen("php://stdin","r")));', which then gets executed and ignored (as a comment), and then it runs eval(prompt()) to execute the input.
PHP - //eval(input()) is interpreted as a comment, so it get's the array [1] like in JS and does nothing with it. Then it evals
$a="/";eval(`${$a}/bin/echo 'eval(fgets(fopen("php://stdin","r")));'`);eval(prompt());

but in here
`${$a}/bin/echo 'eval(fgets(fopen("php://stdin","r")));'`

Is executed from the shell, and translates to //bin/echo 'eval(fgets(fopen("php://stdin","r")));' which returns eval(fgets(fopen("php://stdin","r")));. Then that gets evaled, which executes the code from the input. then it tries evaluating prompt() which doesn't exist and errors out.
PS - This is my first post here, so if I've done anything wrong/missed something please let me know.


text:
Determine if a number is less than another
Introduction
Your job is to write a function or program that detects if a number a is less than a number b.
But... You are not allowed to use built-in alternatives for equals, less than, greater than, less than or equal to, greater than or equal to, or not equal to operators. (Writing your own implementation is allowed.) Similar alternative methods/alternatives in other languages that are designed to replace those operations are also restricted.
You are allowed to use operators that are not banned, e.g. bitwise operators and the not operator (but it would be better if your answer did not have the not operator).
Challenge
Simply return a truthy or falsy value (or something that evaluates in the language to true or false like 0 or 1) to indicate whether a is less than b. The winner of the challenge can be determined by the shortest code. External sources are not allowed, but anonymous functions are. Explaining your answer is not mandatory, but encouraged.
Example using Javascript:
(a,b)=>!!Math.max(0,b-a) //remove the !! for truthy and falsy numbers
/*Explanation
(a,b)                    Parameters a and b
     =>                  Function is
       !!                returns true if truthy and false if falsy
         Math.max(0,b-a) returns the greater number, 0 or b-a
*/

Examples of Input and Output
Input | Output
------|-------
1, 3  | true
2, 2  | false
3, 2  | false

Welcome to the site!  The challenge you have linked is very old and not really a good example of a challenge. I have currently voted to close that challenge and I am voting to close your challenge for the same reason. In the future you can visit our sandbox (linked in the sidebar) to get feedback ahead of time.

The core of the issue is that what consitutes a certain operation (e.g. == or <) is not very clear and varies wildly from language to language.

Related meta post in Things to avoid when writing challenges.

@a'_' That returns true for 3, 2 even though 3 is not less than 2...

@a'_' well you could use logical negation (decided that was too much) and bitwise operators.

@a'_' Some languages don't have a negate operator and some can do it in less than 5 bytes (see answer below) and I can't think of a javascript solution without the not operator that returns true or false.

I would try to avoid the “operator” word to make clear that bultin methods and functions would also be too boring. (For example: (1).__lt__(3), 1.<(3), @cmpn{1;3;true;false;false}.)

@a'_' that is true...

@a'_' I didn't add the restriction back but it's not encouraged now.

@WheatWizard What should I change and how should I change it; or should I just delete this question?

Thanks for taking the time to improve the question.  However in my opinion it is not salvageable. The very core idea of do X but these X Y Z are banned is very very hard to make clear and concrete.  And even if you did, "do X without Y" is a challenge type that we have already kind of done to death.  I would recommend putting your effort coming up with a fresh idea rather than trying to patch this one up.

When you have a new idea the sandbox is the best place to start, since you can get feedback risk free before you post.

APL (Dyalog Unicode), 2 bytesSBCS
Anonymous tacit prefix function. Requires ⎕IO←0
⊃⍒

Try it online!
⍒ gives the "grade". The indices into the argument that would stably sort it in descending order

If the first element is less than the second, it gives [1,0]
If the the elements are equal, it gives [0,1]
If the second element is less than the second, it gives [0,1]

⊃ picks the first element of that

If the first element is less than the second, it gives 1
If the the elements are equal, it gives 0
If the second element is less than the second, it gives 0

Hm, I guess this answer isn't useful.


text:
Can you calculate the average Levenshtein distance exactly?
The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one.
The challenge is to compute the average Levenshtein distance between two independent and uniformly random chosen binary strings of length n each.  Your output must be exact but can be given in any easy to understand human readable form.
Examples:
These are the answer for n up to 24.
1 1/2
2 1
3 47/32
4 243/128
5 1179/512
6 2755/1024
7 12561/4096
8 56261/16384
9 124329/32768
10 2175407/524288
11 589839/131072
12 40664257/8388608
13 174219279/33554432
14 742795299/134217728
15 1576845897/268435456
16 13340661075/2147483648
17 14062798725/2147483648
18 59125997473/8589934592
19 123976260203/17179869184
20 259354089603/34359738368
21 8662782598909/1099511627776
22 72199426617073/8796093022208
23 150173613383989/17592186044416
24 1247439983177201/140737488355328

Score
Your score is the highest value of  you can reach. Where humanly possible, I will run your code on my Linux machine for 10 minutes and then kill the job to get the score.
Notes
As always this should be a competition per language. I will maintain a leaderboard that shows the best score for each language used in an answer.  I will also give a bounty of 50 points for the first answer to get to n = 20.
My CPU is an Intel(R) Xeon(R) CPU X5460.
Leaderboard

n = 18 in Python+numba by Shamis (timing pending...).
n = 19 in Java by Bob Genom (278 seconds).
n = 19 in C by ngn (257 seconds).
n = 21 in Rust by Anders Kaseorg (297 seconds). 150 point bonus awarded.

@LuisMendo I managed to update it from my phone.

This formulation of the question allows you to pre-create a table of output values.

If you prohibit tables, it will be possible to derive a mathematical function from the table that will give the correct result for the selected n.

Interesting, even the limiting form of the average distance is not known precisely, so I doubt a closed form is known.

@КириллМалышев The standard loophole rules prohibit precomputimg the answers, if you manage to work out a closed formula, then you deserve both the win and the bounty that I will give you.

"As always this should be a competition per language" why on earth would a [fastest-code] competition be per-language? To prevent people from creating magic languages that excel at calculating the average Levenshtein distance exactly and nothing else and easily winning? We're supposedly comparing the programs' performance and ignoring their code in [fastest-code], similarly to how we ignore the programs' performance and compare their code in [code-golf] challenges. The equivalent of per-language things in [code-golf] is probably a per-CPU competition in [fastest-code] or something.

@mypronounismonicareinstate My reasoning is that we are testing the ability of the coder not the different programming languages. If you can make a Python program that is faster than anyone else’s then that is great. It’s fairly obvious that hand optimised assembly is always the fastest programming language. To compare with code-golf, we are comparing the performance and ignoring the length of the code.

@Anush “It’s fairly obvious that hand optimised assembly is always the fastest programming language.” This is actually false, because most assembly nowadays is actually more like C bytecode than the actual primitives the processor will execute. You've got microcode, vectorisation…

@wizzwizz4 Also optimal register allocation by hand is not very easy.

I noticed that my solution does not scale very well on your test computer:
(n my  yours factor)-> {(v4 17 148  452  3.1), (v3 16 271  483  1.7),  (v1 15 139  224  1.6)}.
Can you confirm this?

Rust, score ≈ 22
This uses a dynamic programming approach (I’ve added an explanation here) whose running time seems to scale as approximately \$\tilde O(2^{1.5n})\$, rather than the \$\tilde O(2^{2n})\$ of a brute-force search.  On my Ryzen 7 1800X (8 cores/16 threads), it gets through \$1 \le n \le 21\$ in 1.7 minutes, \$1 \le n \le 22\$ in 5.1 minutes.
Now using SIMD for the inner loop.
src/main.rs
use fxhash::FxBuildHasher;
use itertools::izip;
use rayon::prelude::*;
use std::arch::x86_64::*;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::mem;
use typed_arena::Arena;

#[global_allocator]
static ALLOC: mimallocator::Mimalloc = mimallocator::Mimalloc;

type Distance = i8;
type Count = u32;
type Total = u64;

#[derive(Debug)]
struct Distances(__m128i);

impl PartialEq for Distances {
    fn eq(&self, other: &Distances) -> bool {
        unsafe {
            let x = _mm_xor_si128(self.0, other.0);
            _mm_testz_si128(x, x) != 0
        }
    }
}

impl Eq for Distances {}

impl Hash for Distances {
    fn hash<H: Hasher>(&self, state: &mut H) {
        unsafe {
            _mm_extract_epi64(self.0, 0).hash(state);
            _mm_extract_epi64(self.0, 1).hash(state);
        }
    }
}

fn main() {
    let splat0 = unsafe { _mm_set1_epi8(0) };
    let splat1 = unsafe { _mm_set1_epi8(1) };
    let splatff = unsafe { _mm_set1_epi8(!0) };
    let splat7f = unsafe { _mm_set1_epi8(0x7f) };
    let seq = unsafe { _mm_set_epi8(15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0) };
    let grow0 = unsafe {
        _mm_set_epi8(
            -0x80, 0, 0x20, 0, 0x8, 0, 0x2, 0, 0, 0x40, 0, 0x10, 0, 0x4, 0, 0x1,
        )
    };
    let grow1 = unsafe {
        _mm_set_epi8(
            0, 0x40, 0, 0x10, 0, 0x4, 0, 0x1, -0x80, 0, 0x20, 0, 0x8, 0, 0x2, 0,
        )
    };

    for n in 1 as Distance.. {
        if n > 31
            || (n as Count).leading_zeros() < n as u32
            || (n as Total).leading_zeros() < 2 * n as u32
        {
            break;
        }

        let total: Total = (0u32..1 << (n - 1))
            .into_par_iter()
            .map(|a| {
                let mut a_sym = a.reverse_bits();
                a_sym ^= (a_sym >> 31).wrapping_neg();
                a_sym >>= 32 - n as usize;
                if a_sym < a {
                    return 0;
                }

                let arena = Arena::<Distances>::new();
                let stride = (n as usize + 16) / 16 * 16;
                let idx = |i: Distance, j: Distance| i as usize + stride * j as usize;
                let both = |[x, y]: [Distance; 2]| x.max(y);
                let mut worst = vec![[stride as Distance; 2]; idx(0, n + 1)];
                for j in 0..=n {
                    worst[idx(n, j)] = [n - j; 2];
                }
                for i in (0..n).rev() {
                    worst[idx(i, n)] = [n - i; 2];
                    let good = (a >> i & 1) as usize;
                    let bad = good ^ 1;
                    for j in (0..n).rev() {
                        worst[idx(i, j)][good] = both(worst[idx(i + 1, j + 1)]);
                        worst[idx(i, j)][bad] = 1 + worst[idx(i + 1, j)][bad]
                            .min(both(worst[idx(i, j + 1)]))
                            .min(both(worst[idx(i + 1, j + 1)]));
                    }
                }
                let worst: &[Distances] = arena.alloc_extend(
                    worst
                        .into_iter()
                        .map(both)
                        .collect::<Box<[Distance]>>()
                        .chunks(16)
                        .map(|chunk| {
                            Distances(unsafe {
                                _mm_loadu_si128(chunk as *const [i8] as *const __m128i)
                            })
                        }),
                );

                let mut states: HashMap<&[Distances], Count, FxBuildHasher> = HashMap::default();
                let mut new_states = HashMap::default();

                states.insert(
                    arena.alloc_extend(
                        (0..n + 1)
                            .step_by(16)
                            .map(|i| Distances(unsafe { _mm_add_epi8(_mm_set1_epi8(i), seq) })),
                    ),
                    1,
                );

                let bvs: Vec<_> = [a, !a]
                    .iter()
                    .map(|b| {
                        arena.alloc_extend((0..n + 1).step_by(16).map(|i| unsafe {
                            let x = _mm_set1_epi16(((b << 1) >> i) as i16);
                            Distances(_mm_xor_si128(
                                _mm_cmpeq_epi8(
                                    _mm_or_si128(
                                        _mm_and_si128(x, grow0),
                                        _mm_and_si128(_mm_alignr_epi8(x, x, 1), grow1),
                                    ),
                                    splat0,
                                ),
                                splatff,
                            ))
                        }))
                    })
                    .collect();

                for j in 1..=n {
                    new_states.reserve(2 * states.len());
                    let worst_slice = &worst[idx(0, j) / 16..idx(0, j + 1) / 16];
                    for (state, count) in states.drain() {
                        for bv in &bvs {
                            let mut x = j;
                            let mut y = n.into();
                            let mut bound = n;

                            let new_state: &mut [Distances] =
                                arena.alloc_extend(izip!(&**bv, state, worst_slice).map(
                                    |(&Distances(bc), &Distances(yc), &Distances(wc))| unsafe {
                                        let o = _mm_min_epi8(
                                            _mm_add_epi8(yc, splat1),
                                            _mm_sub_epi8(
                                                _mm_insert_epi8(_mm_slli_si128(yc, 1), y, 0),
                                                bc,
                                            ),
                                        );
                                        y = _mm_extract_epi8(yc, 15);
                                        let o = _mm_sub_epi8(o, seq);
                                        let o = _mm_min_epi8(o, _mm_set1_epi8(x));
                                        let o = _mm_sub_epi8(splat7f, o);
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 1));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 2));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 4));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 8));
                                        let o = _mm_sub_epi8(splat7f, o);
                                        x = _mm_extract_epi8(o, 15) as i8 + 16;
                                        let o = _mm_add_epi8(o, seq);
                                        let z = _mm_add_epi8(o, wc);
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 1));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 2));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 4));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 8));
                                        bound = bound.min(_mm_extract_epi8(z, 0) as i8);
                                        Distances(o)
                                    },
                                ));

                            let bound = unsafe { _mm_set1_epi8(bound) };
                            for (i, Distances(x)) in (0..).step_by(16).zip(&mut *new_state) {
                                *x = unsafe {
                                    _mm_min_epi8(
                                        *x,
                                        _mm_sub_epi8(
                                            bound,
                                            _mm_abs_epi8(_mm_add_epi8(_mm_set1_epi8(i - j), seq)),
                                        ),
                                    )
                                };
                            }

                            *new_states.entry(&*new_state).or_insert(0) += count;
                        }
                    }
                    mem::swap(&mut states, &mut new_states);
                }

                let control = unsafe { _mm_insert_epi8(splatff, (n % 16).into(), 0) };
                Total::from(
                    states
                        .into_iter()
                        .map(|(state, count)| unsafe {
                            count
                                * _mm_extract_epi8(
                                    _mm_shuffle_epi8(state[n as usize / 16].0, control),
                                    0,
                                ) as Count
                        })
                        .sum::<Count>(),
                ) * if a_sym == a { 1 } else { 2 }
            })
            .sum();

        let shift = total.trailing_zeros();
        println!(
            "{} {}/{}",
            n,
            total >> shift,
            (1 as Total) << (2 * n as u32 - 1 - shift),
        );
    }
}

Cargo.toml
[package]
name = "levenshtein"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[profile.release]
lto = true
codegen-units = 1

[dependencies]
fxhash = "0.2.1"
itertools = "0.8.2"
mimallocator = "0.1.3"
rayon = "1.3.0"
typed-arena = "2.0.0"

Running
RUSTFLAGS='-C target-cpu=native' cargo build --release
target/release/levenshtein

Output
(With cumulative timing data prepended by ts -s %.s.)
0.000008 1 1/2
0.000150 2 1/1
0.000219 3 47/32
0.000282 4 243/128
0.000344 5 1179/512
0.000413 6 2755/1024
0.000476 7 12561/4096
0.000538 8 56261/16384
0.000598 9 124329/32768
0.000660 10 2175407/524288
0.000721 11 589839/131072
0.000782 12 40664257/8388608
0.000843 13 174219279/33554432
0.006964 14 742795299/134217728
0.068070 15 1576845897/268435456
0.310136 16 13340661075/2147483648
1.062122 17 14062798725/2147483648
3.586745 18 59125997473/8589934592
11.265840 19 123976260203/17179869184
33.691822 20 259354089603/34359738368
101.514674 21 8662782598909/1099511627776
307.427106 22 72199426617073/8796093022208
956.299101 23 150173613383989/17592186044416
3077.477731 24 1247439983177201/140737488355328
10276.205241 25 5173410986415247/562949953421312
34550.754308 26 5356540527479769/562949953421312

Static core2 build for Anush

A really great first answer!  I look forward to timing it.

I have no idea why my AMD 8350 is so much slower than your CPU.  In theory it should be roughly half the speed.

@Anush Curious. This is the with revised version I posted after your first comment (using a_sym to cut down the search space by a factor of 4)? And a current version of Rust (HashMap was replaced with a faster implementation a few months ago)?

Yes I am using the latest version and rustc 1.40.0 (73528e339 2019-12-16). I will see if I can find another computer to test it on.

For interest I made a static compilation and ran it on my computer and two others. For mine it gets to n=19.  On Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz it gets to n = 18 and on Intel(R) Xeon(R) CPU           X5460  @ 3.16GHz it gets to n = 16.  Could you statically compile on your machine and give me the compiled executable to test by any chance?

@Anush I tried a static build with musl and it was also slow—I think musl comes with a very slow memory allocator. Try this revision, which uses mimalloc instead of the system allocator. Here’s a static binary if you need it.

@Anush …which made me realize, if memory allocation overhead is an issue, then typed-arena is even better. This version is another 31% faster (new static binary).

I gave up on my computer which just seems very slow for this sort of multi-threaded code for some mysterious reason (the amd 8350 is made up of 4 "modules" that each consist of 2 integer processing units and one floating point unit so I can't see why it is less than half the speed). I found a server with an Intel CPU and your code is now eligible for the 50 point bounty.

Would you mind writing a few words about your method please? It's not obvious to me how you have formulated the problem to make it amenable to dynamic programming for example.

Could you make me a static binary again please? My CPU is -march=core2 -msse4.1 in terms of gcc features if that makes a difference.

@Anush I converted the inner loop to SIMD and added a new static binary.

A very nice speedup!

Java, score ≈ 19
My solution is a recursive approach. It is still \$\tilde O(2^{2n})\$ of a brute-force search. In other words: if n increase by 1 runtime increase by a factor of 4 (even when using multi-threading).
Which is obviously not enough to compare with Anders Kaseorg's code.
I observed and used some symmetries to squeeze out some (linear) factors.
import java.util.stream.IntStream;
// version 5.1
public class AvgLD51_MT {

    public static void main(String[] argv) {
        long t0=System.currentTimeMillis();
        for (int n=1; ;n++) {
            int VP = (1 << n) - 1; // 1m;
            int VN = 0; // 0m;
            int max=1<<(n-1);
            final int N=n;
            long sum=IntStream.range(0, max).mapToLong(p-> {
                int rp = Integer.reverse(p)>>>(32-N);
                int np = VP & ~rp;
                if (p <= rp && p <= np) {
                    if (p == rp || p == np) {
                        return 2*buildX(N, p, 0, 1, VP, VN);
                    } else {
                        return 4*buildX(N, p, 0, 1, VP, VN);
                    }
                }
                return 0;
            }).parallel().sum();
            long gcd=gcd(sum, (1L<<(2*n)));
            System.out.printf("%f   %d  %d  %d/%d\n", (double)(System.currentTimeMillis()-t0)/(1000), n, sum, sum/gcd, (1L<<(2*n))/gcd);
            sum*=2;
        }
    }

    /**
     * Myers (, Hyyrö) injected into my recursive buildX function (see version 4).
     * Pattern p is fixed. Text t is generated by recursion.
     *
     * Myers (, Hyyrö) bit-parallel LevenshteinDistance
     * taken and inferred (for gulfing e.g. m==n) from:
     * https://www.win.tue.nl/~jfg/educ/bit.mat.pdf
     * http://www.mi.fu-berlin.de/wiki/pub/ABI/RnaSeqP4/myers-bitvector-verification.pdf
     * https://www.sciencedirect.com/science/article/pii/S157086670400053X
     * https://www.researchgate.net/publication/266657812_Thread-cooperative_bit-parallel_computation_of_Levenshtein_distance_on_GPU
     */
    static long buildX(int n, int p, int t, int j, int VP, int VN){
        final int HMASK = 1 << (n - 1); // 10^(m-1)
        final int VMASK = (1<<n)-1;
        long score=0;
        int Bj, D0, HP, HN, VP1, VN1, X;

        // assume a 0 at Tj
        Bj= ~p;
        // compute diagonal delta vector
        D0 = ((VP + (Bj & VP)) ^ VP) | Bj | VN;

        // update horizontal delta values
        HN = VP & D0;
        HP = VN | ~(VP | D0);
        // Scoring and output
        // carry = rev(n, j)*(Integer.bitCount(HP & HMASK) - Integer.bitCount(HN & HMASK));
        X = (HP << 1) | 1;
        VN1 = (HN << 1) | ~(X | D0);
        VP1 = X & D0;
        if (j!=HMASK) {
            // update vertical delta values
            score = buildX(n, p, t, 2*j, VN1, VP1);
        } else {
            score = n + Integer.bitCount(VMASK & VN1) - Integer.bitCount(VMASK & VP1);
        }

        // assume a 1 at Tj
        Bj= p;
        // compute diagonal delta vector
        D0 = ((VP + (Bj & VP)) ^ VP) | Bj | VN;

        // update horizontal delta values
        HN = VP & D0;
        HP = VN | ~(VP | D0);
        // Scoring and output
        // carry += rev(n, j)*(Integer.bitCount(HP & HMASK) - Integer.bitCount(HN & HMASK));
        X = (HP << 1) | 1;
        VN1 = (HN << 1) | ~(X | D0);
        VP1 = X & D0;
        if (j!=HMASK) {
            // update vertical delta values
            return score + buildX(n, p, t, 2*j, VN1, VP1);
        } else {
            return n + score + Integer.bitCount(VMASK & VN1) - Integer.bitCount(VMASK & VP1);
        }
    }

    static long gcd(long numerator, long denominator) {
        long gcd = denominator;
        while (numerator != 0) {
            long tmp=numerator; numerator=gcd % numerator; gcd=tmp;
        }
        return gcd;
    }
}

Version 5.1
Like version 5 but is multi-threaded by using streams.
0.000000    1   2   1/2
...
0.748000    15  6307383588  1576845897/268435456
2.359000    16  26681322150 13340661075/2147483648
10.062000   17  112502389800    14062798725/2147483648
35.387000   18  473007979784    59125997473/8589934592
156.396000  19  1983620163248   123976260203/17179869184
572.525000  20  8299330867296   259354089603/34359738368

Version 5
Myers code directly injected into my recursive buildX function. As a consequence no extra call of LevenshteinDistance is needed any more.
0.000000    1   2   1/2
...
2.134000    15  6307383588  1576845897/268435456
7.571000    16  26681322150 13340661075/2147483648
32.705000   17  112502389800    14062798725/2147483648
119.952000  18  473007979784    59125997473/8589934592
523.186000  19  1983620163248   123976260203/17179869184

Version 4.1
Like version 4 but is multi-threaded by using streams.
0.000000    1   2   1/2
...
0.764000    13  348438558   174219279/33554432
1.525000    14  1485590598  742795299/134217728
4.417000    15  6307383588  1576845897/268435456
15.445000   16  26681322150 13340661075/2147483648
63.199000   17  112502389800    14062798725/2147483648
259.179000  18  473007979784    59125997473/8589934592

Version 4
Uses Myers, Hyyrö bit-parallel LevenshteinDistance.
0.000000    1   2   1/2
...
8.203000    15  6307383588  1576845897/268435456
35.326000   16  26681322150 13340661075/2147483648
148.577000  17  112502389800    14062798725/2147483648
629.084000  18  473007979784    59125997473/8589934592
2615.031000 19  1983620163248   123976260203/17179869184

Version 3
Copied and uses getLevenshteinDistance(..) from apache StringUtils.
BTW: Using the threshold variant made no difference for me. (Used threshold=bitCount(s^t))
0.000000    1   2   1/2
...
60.190000   15  6307383588  1576845897/268435456
271.020000  16  26681322150 13340661075/2147483648
1219.544000 17  112502389800    14062798725/2147483648

Version 2
Found more symmetries on recursion.
0.000000    1   2   1/2
...
105.389000  15  6307383588  1576845897/268435456
447.617000  16  26681322150 13340661075/2147483648
2105.316000 17  112502389800    14062798725/2147483648

Version 1
0.000000    1   2   1/2
0.068000    2   16  1/1
0.070000    3   94  47/32
0.071000    4   486 243/128
0.073000    5   2358    1179/512
0.074000    6   11020   2755/1024
0.076000    7   50244   12561/4096
0.086000    8   225044  56261/16384
0.111000    9   994632  124329/32768
0.223000    10  4350814 2175407/524288
0.640000    11  18874848    589839/131072
1.842000    12  81328514    40664257/8388608
7.387000    13  348438558   174219279/33554432
29.998000   14  1485590598  742795299/134217728
139.217000  15  6307383588  1576845897/268435456
581.465000  16  26681322150 13340661075/2147483648

Thank you.  I look forward to timing it.

Got to 15 on my test CPU in 224 seconds (983 for n  = 16). I notice the code uses a single thread. Can it be made multi-threaded?

I'm still in the mode of tuning the core algorithm. If done I'll try to progress to multi-threaded. BTW: How did you get the values for your "answer for n up to 23."

For up to 16 I just used my slow Python code and for the rest I used Anders Kaseorg's code.  Very glad to hear improvements are planned!

You sir just made my day. The bit-parallel distance works like a charm. I am up two levels just by using it.

You have achieve a great speedup! But I still want to know what Kaseorg had done in terms of dynamic programming.

@Shamis: Because the alphabet is "0", "1" I thought there must be some specialized LevenshteinDistance version for binary numbers. Then I found Myers solution in the net and gave it a try.

@Anush: From my findings diving 2 weeks into the field of Levenshtein Dist: A chance to reach O(2^(1.5n)), is by building and using a (see) "Levenshtein automaton" for each word w. Which are 2^n automatons a[w] which can be build easy (they say) in time O(|w|) each. Each a[w] is applied to 2^n words stored in a compressed trie dictionary. The time for this is proportional to the number of nodes in the trie. I guess, when stepping from n-1 to n, maintaining and applying the dictionary can be done (e.g. by using dynamic programming) in at least O(2^(0.5n)). Does that sound plausible for you?

Very interesting. I hope someone is brave enough to try implementing this in a non-Rust programming language!

I think that I know what Anders did. However my implementation, while working, is not nearly as fast as even my original solution even though it should/could be faster in theory.

C
// gcc -O3 -pthread -march=native a.c && ./a.out
#define _GNU_SOURCE
#include<stdio.h>
#include<unistd.h>
#include<pthread.h>
#define _(a...){return({a;});}
#define $(x,a...)if(x){a;}
#define P(x,a...)if(x)_(a)
#define W(x,a...)while(x){a;}
#define F(i,n,a...)for(I i=0,n_=(n);i<n_;i++){a;}
#define S static
typedef void V;typedef int I;typedef long long L;typedef struct{I x,r;pthread_barrier_t*b;}A;
S I n,x1,msk,nt;S L f1(I,I,I,I);
S L gcd(L x,L y)_(W(x,L z=x;x=y%x;y=z)y)S I rev(I x)_(I r=0;F(i,n,r+=(x>>i&1)<<(n-1-i))r)
S L f0(I x,I j,I vp_,I vn_,I pm)_(I d0=(((pm&vp_)+vp_)^vp_)|pm|vn_,hp=vn_|~(d0|vp_),hp1=hp<<1|1,vp=(d0&vp_)<<1|~(d0|hp1),vn=d0&hp1;f1(x,j,vp,vn))
S L f1(I x,I j,I vp_,I vn_)_(P(!--j,__builtin_popcount(msk&vp_)-__builtin_popcount(msk&vn_))f0(x,j,vp_,vn_,x)+f0(x,j,vp_,vn_,~x))
S V*f2(A*a)_(I x=a->x;L s[3]={};W(x<x1,I rx=rev(x),nx=msk&~rx;$(x<=rx&&x<=nx,s[(x!=rx)+(x!=nx)]+=f1(x,n+1,msk,0))x+=nt)
 a->r=s[0]+2*s[1]+4*s[2];pthread_barrier_wait(a->b);NULL)
S L f3()_(L r=(L)n<<2*n;pthread_barrier_t b;pthread_barrier_init(&b,0,nt);A a[nt];pthread_t t[nt];
 F(i,nt,cpu_set_t c;CPU_ZERO(&c);CPU_SET(i,&c);pthread_attr_t h;pthread_attr_init(&h);pthread_attr_setaffinity_np(&h,sizeof(cpu_set_t),&c);
  a[i].x=i;a[i].r=0;a[i].b=&b;pthread_create(t+i,0,(V*(*)(V*))f2,a+i))
 F(i,nt,pthread_join(t[i],0);r+=a[i].r)pthread_barrier_destroy(&b);r)
I main()_(nt=2*sysconf(_SC_NPROCESSORS_CONF);
 W(1,n++;x1=1<<(n-1);msk=(1<<n)-1;L p=f3(),q=1ll<<2*n,d=gcd(p,q);printf("%d %lld/%lld\n",n,p/d,q/d);fflush(stdout))0)

Could you ungolf the code please? I look forward to timing it but what n do you get to?

This isn't Code Golf.

I think this is just how ngn writes C code -- it's not golfed.

Python ~ 15, 17, 18 Requiem for a Dream.
So far for my attempt to decipher the algorithm. Just one simple symmetry as a result. Upside is that I managed to get up to 19. Downside is obviously a shattered hope XD.
To add an insult to an injury, I think that Bob Genom already has it. (Noticed after I dismantled my previous horror of a solution to something readable-ish.) It also might be that what I considered annoying edge cases might actually be a result of me overcomplicating things. Dear oh dear.
Still I think that some way of caching the Levenstein computation might be the way to go. Just not the one I tried last time.
7.215967655181885 16 13340661075 / 2147483648
24.544007539749146 17 14062798725 / 2147483648
93.72401142120361 18 59125997473 / 8589934592
379.6802065372467 19 123976260203 / 17179869184

Added Multiprocessing. The most expensive thing at the time are locks. And I have yet to figure a way to bypass the need for them. My manual attempts are slower than the Pool.Starmap which makes me slightly sad.
Tried a block processing approach with an attempt to gain another linear factor, however for some reason this slowed down the code by a lot. Overoptimization seems to backfire.
1.640207052230835 13 174219279 / 33554432
1.9370124340057373 14 742795299 / 134217728
3.1867198944091797 15 1576845897 / 268435456
9.054970979690552 16 13340661075 / 2147483648
37.539693117141724 17 14062798725 / 2147483648
158.5456690788269 18 59125997473 / 8589934592

Thanks to Bob Genom's answer and using his latest distance algorithm I managed to up the speed.
Also I noted that one of the attempts at a linear symmetry backfired - the code runs faster after I removed it. Probably something to do with ranges?
...............
0.6873703002929688 13 174219279 / 33554432
2.0464255809783936 14 742795299 / 134217728
7.808838605880737 15 1576845897 / 268435456
33.9985032081604 16 13340661075 / 2147483648
145.6884548664093 17 14062798725 / 2147483648

Took me quite a while and I have run into quite the Python limitations. My attempt to parallelize was ground to a halt by the GIL. Figuring out how to make processes talk to each other will take a while.
I have few more ideas to try, however my brain is starting to melt. I spent last two hours by juggling indices - my current approach is to embed symmetries directly into the loops. Recursion was much slower and Numba doesn't like to interact with Python objects. For some reason it sees nothing to parallelize in this code and I have no clue whether the parallel part does anything since the CPU is only at 20% capacity.
This approach is still bruteforcing, however with the embedded symmetries it takes the computation down a notch - many of the combinations are not even considered.
I took the liberty to start from 2nd floor. I do not consider that as a cheating since it is negligible time-wise. And it introduces a swath of very vexing edge cases.
If I have time, I will try to do these:
Rewrite the code in something faster, probably C.
Try to figure out a decent way to use parallelization, maybe in C.
And a bit of a caching. That one will be tricky, especially in combination with the embedding.
0.0 2 1 / 1
0.483562707901001 3 47 / 32
0.483562707901001 4 243 / 128
0.483562707901001 5 1179 / 512
0.483562707901001 6 2755 / 1024
0.483562707901001 7 12561 / 4096
0.5001938343048096 8 56261 / 16384
0.5334563255310059 9 124329 / 32768
0.6999850273132324 10 2175407 / 524288
1.3333814144134521 11 589839 / 131072
3.7170190811157227 12 40664257 / 8388608
15.165801048278809 13 174219279 / 33554432
62.91589903831482 14 742795299 / 134217728
266.3912649154663 15 1576845897 / 268435456

I would love to try and give a GPU a go for this task. However I failed miserably for nowXD.
from numba import jit, cuda, prange
import time
import multiprocessing as mp

@jit(nopython=True, fastmath=True, nogil=True)#, parallel=True)
def LevenshteinDistance(n, p, t):
        np=~p
        HMASK = (1 << (n - 1))
        VP = (1 << n) - 1
        VN = 0
        score = n
        for j in range(0,n):
            if (t & (1<<j)) != 0:
                Bj = p
            else:
                Bj = np
            D0 = ((VP + (Bj & VP)) ^ VP) | Bj | VN
            HN = VP & D0
            HP = VN | ~(VP | D0)

            if ((HP & HMASK) != 0):
             score += 1;
            elif ((HN & HMASK) != 0):
             score -= 1;
            X = (HP << 1) | 1
            VN = X & D0
            VP = (HN << 1) | ~(X | D0)
        return score

@jit(nopython=True, fastmath=True)#, parallel=True)
def dispatchLev(i, level):
    halfSize = 1 << (level - 1) - 1
    iRange = halfSize
    levelSize = 1 << (level - 1)
    mask = levelSize - 1
    halfSize = levelSize >> 1
    rangeUpper = iRange - i
    indexI = i + halfSize
    baseI = indexI << 1
    sum = 0
    for indexJ in range(0, rangeUpper):
        baseJ = indexJ << 1
        if (mask ^ indexJ) == indexI:
            a = LevenshteinDistance(level, baseI + 1, baseJ)
            b = LevenshteinDistance(level, baseI, baseJ + 1)
            sum += a + b
        else:
            a = LevenshteinDistance(level, baseI + 1, baseJ)
            b = LevenshteinDistance(level, baseI, baseJ + 1)
            sum += 2 * (a + b)

    return sum

def computeSum(level):
    levelSize = 1 << (level - 1)
    halfSize = levelSize >> 1
    curSum = 0
    iRange = halfSize
    test = [(x, level) for x in range(0, iRange)]
    if len(test) > 1:
        a = myPool.starmap(dispatchLev, test)
        curSum += sum(a)
        #for x, level in test:
        #    curSum += dispatchLev(x,level)

    else:
        a = dispatchLev(0, level)
        curSum += a
    return curSum

def gcd(num, den):
    gcdRet = den
    tmp = 0
    while num != 0:
        tmp = num
        num = gcdRet % num
        gcdRet = tmp

    return gcdRet

if __name__ == '__main__':
    t1 = time.time()
    print("beginning")
    prevSum = 16
    bruteForceCarry = 6
    levelMask = 0
    target = 20
    curSum = 0
    bruteForce = 0
    myPool = mp.Pool(mp.cpu_count())
    processArray = []
    resultArray = []

    for level in range(3, target):
        levelSize = 1 << level
        halfSize = levelSize >> 1
        bruteForce = computeSum(level)
        diagonal = computeDiagonal(level)
        bruteForceCarry = 2 * bruteForceCarry + bruteForce
        curSum = prevSum + bruteForceCarry
        curSum = curSum * 2
        t2 = time.time()
        wholeSize = levelSize * levelSize
        divisor = gcd(curSum, wholeSize)
        a = int(curSum / divisor)
        b = int(wholeSize / divisor)
        print(t2 - t1, level, a, "/", b)
        prevSum = curSum

Thanks! It might be fun to try pypy and then cython too.

I am currently rewriting the code in C, I want to see how much is it Python being slow and how much it is the limitation of the approach I have chosen.

I asked an expert and they said "numba won't automatically parallelise loops, you have to opt-in with prange and then guarantee all the safety yourself". See http://numba.pydata.org/numba-doc/latest/user/performance-tips.html#parallel-true

I tried that more than once actually. Did seemingly the same thing as they did. And if I am not terribly wrong, there is no inherent conflict in the code. I am currently not caching any values. The version that used Pool.Apply was working without issues. However after refactoring everything, the Pool decided that it doesn't want to be friends with Numba.

The gitter for numba https://gitter.im/numba/numba has experts who are very happy to help. It would be worth asking there.

The main question is, can anyone work out what the dynamic programming algorithm is that Kaseorg has used?

Would this all be easier in Julia? I am following your investigations with great interest.

Not sure, don't know that one. At the start I chose Python since I use it at work and I can use it reasonably fast. I rewrote first computation with C and it was not that much faster than Numba actually.
However when I once again began digging into the issue, I have run into the restrictions that the Numba imposes on the type safety. In the end, I have yet to find a way to make Python code thread unsafe so most of the time is still spend in locks.
I already spent more time than intended, so I opted for posting the partial results. Work waits and sleeps is also nice :-(.

authors: Кирилл Малышев