# Question
Title: Check for occurences of string in other string
# Challenge

I'm sure you read the title, and came in to farm your rep, thinking its kids' stuff, but think again! You have to challenge each other in the *shortest* code to count the occurences of a string in another. For example, given the following input:

> aaaabbbbsssffhd

as a string, and the string

> s

should output

> 3

# Rules

Just before you smile and say, "Hey, I'll use ----," read this:

* No use of external libraries, or your language's API. You have to implement it manually. Which means you can't use your language's built-in function or method for counting occurences
* No file I/O
* No connecting with a server, website, et cetera
* In a case of \`ababa\`, where it starts with \`aba\` and if you read the last 3 letters it's also \`aba\`, you only count one*****

*Thank you @ProgramFOX for that (the last rule)!*
***Hint**: When you count occurences, you can remove the ones you counted to avoid disobeying this rule

I think the last 2 rules are just for rule benders!

# Winning Criterion

As previously stated the winner is the code with the less bytes used. The winner will be announced five days later (15 June 2014)

# My Small Answer

Here's my C++ answer, where it assumes that the `li` variable holds the string to check occurences in, and `l` is the string to look for in `f`:

### Ungolfed

```
int c = 0;
while (li.find(lf) != string::npos)
{
    int p = li.find(lf);
    int l = p + lf.length() - 1;
    for (p = p; p <= l; p++)
    {
        li[p] = static_cast<char>(8);
    }
    ++c;
}

```

Of course, to use `std::string`, you have to include the string header file!

### Golfed

```
int c=0;while(li.find(lf)!=string::npos){int p=li.find(lf);int l=p+lf.length()-1;for(p=p;p<=l;p++){li[p]=static_cast<char>(8);}++c;}

```

### Result

The variable `c` is going to be the value of how many times the string was found

---

### Enjoy!

# Winner

After a long wait @Dennis answer wins with only 3 bytes, written in GolfScript

# Answer
> 7 votes
# GolfScript, 3 bytes

```
/,(

```

Assumes string and substring are on the stack.

Try it online.

### How it works

```
/  # Split the string around occurrences of the substring.
,  # Get the length of the split array.
(  # Subtract 1.

```

# Answer
> 7 votes
## JavaScript 32

Nothing really interesting here...

```
(p=prompt)().split(p()).length-1

```

`split` main purpose is to create an array from a string using the delimiter in argument.

# Answer
> 2 votes
# J (7)

`No use of external libraries` Check! `, or your language's API.` Check...? I don't know what an language API is. `You have to implement it manually` Check! `No file I/O` Check! `No connecting with a server, website, et cetera` Check!

```
+/a E.b

```

How it works:

`E.` is `WindowedMatch`: the J Refsheet gives `'re' E. 'reread'` as example. This gives `1 0 1 0 0 0`. Then, the only thing left to do is simply adding this with `+/` (basically `sum`).

I don't think this counts as using `your language's built-in function or method for counting occurences`, but that's disputable.

EDIT: Just to be clear:

```
   +/'aba'E.'ababa'
2

```

# Answer
> 1 votes
# Python 2.x - 49 23 22 bytes

This is assuming variable input is okay. Both strings can be of any length.

Shortened @avall.

```
a='s'
b='aaaabbbbsssffhd'
print~-len(b.split(a))

```

49 bytes version, counts every instance of the substring ('aba' is in 'ababa' twice).

```
a='s'
b='aaaabbbbsssffhd'
print sum(a==b[i:i+len(a)]for i in range(len(b)))

```

# Answer
> 1 votes
# C# - 73

```
//a = "aba";
//b = "ababa";

Console.Write(b.Split(new string[]{a},StringSplitOptions.None).Length-1);

// output = "1"

```

# Answer
> 0 votes
# Powershell 32

```
($args[0]-split$args[1]).count-1

```

Works like this:

```
PS C:\MyFolder> .\ocurrences.ps1 ababa aba
1

```

**Explanation:** Uses `-split` to separate the first argument by the second one, returns the size of the array resulting from the split (minus 1)

# Answer
> 0 votes
# Mathematica ~~26~~ 23

Works like Dennis' algorithm, but wordier:

```
Length@StringCases[a,b]

```

Three chars shaved off by Szabolics.

# Answer
> 0 votes
# Applescript, 106 bytes

Applescript is a fun, but silly language to golf in.

```
on run a
set AppleScript's text item delimiters to (a's item 1)
(count of (a's item 2)'s text items)-1
end

```

Run with `osascript`:

```
$ osascript instr.scpt s aaaabbbbsssffhd
3
$

```

# Answer
> 0 votes
# C# - 66 Bytes

```
//s = "aba"
//t = "ababa"

Console.Write(t.Split(new[]{s},StringSplitOptions.None).Length-1);

//Output: 1

```

# Answer
> 0 votes
# C ~~130~~ 120

Note: will probably crash if called with incorrect arguments.

```
r;main(int c,char**a){char*p=*++a,*q,*t;while(*p){for(q=a[1],t=p;*q&&*q==*t;q++)t++;*q?p++:(p=t,r++);}printf("%d\n",r);}

```

Ungolfed (kinda):

```
int main(int argc, char *argv[]) {
    int result = 0;
    char *ptr = argv[1];
    while (*ptr) {
        char *tmp, *tmp2 = ptr;
        // str(n)cmp
        for (tmp = argv[2]; *tmp; tmp++, tmp2++)
            if (*tmp != *tmp2)
                break;
        if (*tmp) {
            ptr++;
        } else {
            result++;
            ptr += tmp;
        }
    }
    printf("%d\n", result);
}

```

Old version with `strstr` and `strlen`: 103

```
l;main(int c,char**a){char*p=a[1];l=strlen(a[2]);while(c++,p>l)p=strstr(p,a[2])+l;printf("%d\n",c-5);}

```

# Answer
> 0 votes
# Delphi XE3 (113)

Takes 2 strings, removes substring from string and substracts new length from old length followed by a division of the substring length.

```
function c(a,b:string):integer;begin c:=(Length(a)-Length(StringReplace(a,b,'',[rfReplaceAll])))div Length(b)end;

```

Testing:

> c('aaaabbbbsssffhd','s') = 3
> c('aaaabbbbsssffhd','a') = 4
> c('ababa','aba') = 1
> c('ababa','c') = 0

# Answer
> 0 votes
# Lua (48)

So i thought I could just submit another answer, this time in lua. Its very possible this could be improved a lot, im very new to this.

```
print((a.len(a)-a.len(a.gsub(a,b,"")))/b.len(b))

```

# Answer
> 0 votes
# Fortran 90: 101

Standard abuse of implicit typing, works for any length arrays `a` and `b`, though one should expect that `len(a) < len(b)`.

```
function i();i=0;k=len(trim(b))-1;do j=1,len(trim(a))-k;if(a(j:j+k)==b(1:1+k))i=i+1;enddo;endfunction

```

This function must be `contain`ed within a full program to work. `a` and `b` are received from stdin and can be entered either on the same line (either comma or space separated) or on different lines. Compile via `gfortran -o main main.f90` and execute as you would any other compiled program.

```
program main
   character(len=256)::a,b
   read*,a,b
   print*,i()
 contains
   function i()
     i=0
     k=len(trim(b))-1
     do j=1,len(trim(a))-k
        if(a(j:j+k)==b(1:1+k))i=i+1
     end do
   end function
end program main

```

Tests:

```
>ababa aba
2

```

I could make the above return 1 if I add 4 characters (`,k+1`) for the `do` loop

```
> aaaabbbbbsssffhd s
3

```

# Answer
> 0 votes
## C++ 225

```
int n,k,m;
int main()
{
string s1,s2;
cin>>s1;
cin>>s2;
int x=s1.size(),y=s2.size();
if(x>=y)
{
for(int i=0;i<x;i++)
{
k=0,m=0;
for(int j=0;j<y;j++)
{
if(s2[j]==s1[i+m])
{
    k++,m++;
}
else break;
}
if(k==y)
{
n++;
i+=(y-1);
}
}
}
cout<<n<<endl;
return 0;
}

```

# Answer
> 0 votes
## Java (38)

```
System.out.print(a.split(b).length-1);

```

(The question did not require a complete program or function.)

# Answer
> 0 votes
# Cobra - 25

```
print a.split(b).length-1

```

# Answer
> 0 votes
# K/Kona 6

```
+/y~'x

```

where `x` is the string and `y` the substring. `~` is the negate operator, with `'`, it is applied to every element in `x`; it will return `0` if it does not match and `1` if it does match. Since it is applied element-wise, the result of `y~'x` is a vector, the `+/` then sums the result giving the total number of occurrences.

Unfortunately, this method requires that `y` is only one character, otherwise we will be comparing a multi-character string to a single character string, resulting in a `length error`.

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


# Question
Title: Sort numbers represented in an unknown base
Given a list of strings, sort the list as numbers without knowing what base is used. The values of the digits are also unknown (it is possible that `'1'` \> `'2'`).

Since the values of digits are unknown, use Benford's Law (or First Digit's Law) to determine the relative value of the digits. For distributions that follow Benford's Law, lower valued digits appear as a leading digit more frequently than higher valued digits.

**Rules**

* This is
* The list of strings can come from a source of your choosing (stdin, variable, file, user, etc.)
* Strings are limited to ASCII characters.
* Characters that do not appear as a leading character have the highest values. (assume there are no zeros, and sort strictly by leading frequency.)
* Characters that appear as leading digits the same number of times as other characters are weighted equally.

**Example**

*Unsorted*

```
['c','ca','ac','cc','a','ccc','cx','cz','cy']

```

*Sorted*

```
['c','a','cc','ca','cz','cy','cx','ac','ccc']

```

*Note:* In the example, `'cz'`,`'cy'` and `'cx'` can appear as the 5th, 6th and 7th elements in any order since the digits `'x'`,`'y'` and `'z'` are equally weighted.

# Answer
# Python, 59 ~~108~~ ~~112~~

```
sorted(a,None,lambda x:(-len(x),map(zip(*a)[0].count,x)),1)

```

Input is provided as the list `a`, and this expression produces the sorted list (+2 characters to assign to a variable). This sorts the list *in reverse* by negated length and then by frequency.
> 7 votes

# Answer
# Ruby, 65

```
f=->a{a.sort_by{|s|[s.size,s.chars.map{|c|a.count{|t|t[0]!=c}}]}}

```

Sorts lexicographically on the string's size, then each character's frequency as not the leading digit.
> 3 votes

# Answer
## Java (261)

```
void s(String[]s){int[]a=new int[128];for(String t:s)a[t.charAt(0)]++;java.util.Arrays.sort(s,(o,p)->{int j=o.length()-p.length();if(j!=0)return j;for(int i=0;i<Math.min(o.length(),p.length());i++){j=a[p.charAt(i)]-a[o.charAt(i)];if(j!=0)return j;}return 0;});}

void s(String[] s) {
    int[] a = new int[128];
    for (String t : s) {
        a[t.charAt(0)]++;
    }
    java.util.Arrays.sort(s, (o, p) -> {
        int j = o.length() - p.length();
        if (j != 0) {
            return j;
        }
        for (int i = 0; i < Math.min(o.length(), p.length()); i++) {
            j = a[p.charAt(i)] - a[o.charAt(i)];
            if (j != 0) {
                return j;
            }
        }
        return 0;
    });
}

```

The methods takes an array of strings, and sorts the array in place. Nothing fancy about the implementation, but it does make use of the lambda expressions added to Java 8.
> 0 votes

# Answer
# Javascript (E6) 147

```
F=i=>(f={},i.map(x=>(f[x[0]]=-~f[x[0]])),i.map(x=>[x,[...x].map(y=>1e9-~f[y]+'')]).sort((a,b,d=a[0].length-b[0].length)=>d||a[1]<b[1]).map(x=>x[0]))

```

**Limit**

Frequency values up to 1000000000: for sorting, the frequency values are merged in a big padded string

**Ungolfed**

```
F=i=>(
  f={}, //init frequency map
  i.map(x => (f[x[0]]=-~f[x[0]])), // build frequency map
  i.map(x => [x, [...x].map(y=>1e9-~f[y]+'')]) // add frequency info to each element of input list
 .sort((a,b,d=a[0].length-b[0].length)=>d || a[1]<b[1]) // then sort by lenght and frequency
 .map( x => x[0]) // throw away frequency info
)

```

*Sidenote* `X-~` increment by 1 even if the original number X is undefined or NaN

**Usage**

```
F(['c','ca','ac','cc','a','ccc','cx','cz','cy'])

```

Output: `["c", "a", "cc", "ca", "cx", "cz", "cy", "ac", "ccc"]`
> 0 votes

---
Tags: code-golf
---


title: Testing Keyboards

text:
# Question
Title: Testing Keyboards
## My Problem

At my current place of employment, I single-handedly (ok dual-handedly because I'm missing no limbs) maintain approximately 700 laptops. Due to the nature and frequency of their use, I often find they are returned with a bit of damage. For this problem, my primary concern is when a laptop is returned with a broken or defunct keyboard. When the hardware repairman fixes these broken keyboards, it becomes necessary to test them. The test involves using each...and...every...single...key. What a drag right? The problem is, sometimes I lose track of if I typed a key or not.

## A solution?

Write a program/script that:

1. Takes user input
2. Upon submission (in whatever way you deem fit), determines whether each key was pressed.
3. Outputs yes or no or any way to indicate that either I was successful in pressing all the keys or not. (Indicate in your answer the two possible outputs if it's not something obvious).

Assumptions:

1. Uppercase, lowercase, both? Whichever way you deem fit. As long as it's \[A-Z\], \[a-z\] or \[A-Za-z\]. Same goes with numbers and other symbols. (So if `=` was typed in, `+` doesn't matter). Your choice if you want to include shifted characters or not.
2. You needn't worry about tabs or spaces
3. No needs for function keys, CTRL, ALT, Esc or any other keys that don't output something on the screen
4. This assumes an EN-US keyboard and the laptops **do not** include a numpad.
5. OS agnostic, whatever language you prefer
6. It doesn't matter if the key has been pressed multiple times (for when the tester just gets lazy and starts button smashing like it's Mortal Kombat)

Here's a potential input set that would return true (or yes, or "You did it!")

```
`1234567890-=qwertyuiop[]\asdfghjkl;'zxcvbnm,./

```

Winner is determined by the least number of characters.

# Answer
# GolfScript, 6 bytes

```
.&,94=

```

If all ASCII characters with codes between 33 and 127 are present, it prints 1. Otherwise, it prints 0.

This approach will fail if the input contains other characters (including a final newline), which has been allowed by the OP and is also true for the existing GolfScript solution.

### Usage

```
$ echo -n '!"#$%&'"'"'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~' |
> golfscript <(echo '.&,94=')
1

```

### How it works

```
.&  # Compute the intersection of the input string with itself. This removes duplicates.
,   # Compute the length of the resulting string.
94= # Push 1 if the length is 94, otherwise push 0.

```
> 1 votes

# Answer
## GolfScript, 11

Printable ASCII isn’t that interesting…

```
127,32,-^,!

```

## Ruby, 68

With flag `-rset` for 4 characters.

```
p Set.new(?`..?z)+(?,..?9)+%w{[ ] \\ ; '}==Set.new(gets.split'')

```

and

## Python 3, 76

```
print(set("`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./")==set(input()))

```
> 6 votes

# Answer
## JavaScript - 62 70

```
alert(!(47-prompt().match(/([',-\/\d;=a-z\[-\]`]?)(?!.*\1)/g).length))

```

And a bit shorter:

```
alert(!!prompt().match(/([',-\/\d;=a-z\[-\]`])(?!.*\1)/g)[46])

```
> 3 votes

# Answer
# CJam - 9

```
',33>q-!

```

It checks for the "shifted" characters too (including uppercase letters).
Try it at http://cjam.aditsu.net/

Note: there is an invisible character (with code 127) after the apostrophe.
> 2 votes

# Answer
# PHP

```
    foreach (str_split("`1234567890-=qwertyuiop[]\asdfghjkl;'zxcvbnm,./") as $v) {
        if (strpos($_GET['i'],$v)!==false)die(NO);
    }

```

`$_GET['i']` is the input
> 2 votes

# Answer
# Python 72:

```
f=lambda x:set(x)==set("`1234567890-=qwertyuiop[]\asdfghjkl;'zxcvbnm,./")

```
> 1 votes

# Answer
# Haskell, 41 (two solutions)

```
interact(\y->show$all(`elem`y)[' '..'`'])

```

or (point-free style)

```
interact$show.(`all`[' '..'`']).flip elem

```

Need to input at least these characters:

```
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`

```

in any order, any number of times. Extra characters are allowed. Run in an interpreter. Must hit Enter when you are done, but if you hit Enter before you are done, you can keep entering characters, and press Enter again. Will print `True` if you have hit every character, otherwise it won't print anything.
> 1 votes

# Answer
# Perl, 70 characters

```
say[sort grep!$s{$_}++,<>=~/\S/g]~~[sort"',-./;=[\]`"=~/./g,0..9,a..z]

```

Usage:

```
echo `134223423567890-=qwertyuiop[]\asdfghjkl;'zxcvbnm,./ | perl -E 'say[sort grep!$s{$_}++,pop=~/\S/g]~~[sort"',-./;=[\]`"=~/./g,0..9,a..z]'

```

Prints 1 if all keystrokes present, else prints nothing.
> 0 votes

# Answer
# C, 97 characters

```
main(long a,char**u){a=0xfb0000000750003d;for(u++;**u;a|=2L<<*(*u)++-39);a=48+!~a;write(1,&a,1);}

```

Need to call the program with argument containing at least the letters:

```
`1234567890-=AZERTYUIOPQSDFGHJKLMWXCVBN[]\;',./

```

and get answer 1 (true). The charset can be changed by changing the initialization value of a.
> 0 votes

---
Tags: code-golf, keyboard
---


title: Prepare data for JS renderer

text:
# Question
Title: Prepare data for JS renderer
It's asked to write a script to generate a source data to feed a JavaScript renderer.

## JS Renderer documentation

The JS renderer is this script:

```
function o(x){
  r=x.split(' ');
  (d=document).write('<style>i{position:absolute;width:10;height:10;background:#000}</style>');
  for(i=0;i<r.length;++i){c=r[i].split(',');d.write('<i style=top:'+(e=eval)(c[0])+';left:'+e(c[1])+'></i>')
  }
}

```

It takes as input a list of X/Y coordinates separated by spaces and commas and prints on DOM the points as **10×10** pixel squares.

For example, if you call the script with:

```
o('0,0 10,0 20,0 30,0 40,0 20,10 20,20 0,30 10,30 20,30 30,30 40,30 0,50 10,50 20,50 30,50 40,50');

```

It will print:

Notice that the values can be expressed as calculations, so it will accept:

```
o('10*2,50/5');

```

## Your task

Write a script that, given as input a string of characters (`[A-Z0-9 ]`; uppercase letters, numbers, spaces) prints on **`stdout`** the coordinates to feed the JS renderer.

### Rules

* The "line-height" of the characters should be of at least 50px
* Your script doesn't need to run the JS parser
* The expected output format is: `x,y x,y x,y x,y`
* The shortest code wins

**Bonus**: if you could reduce the length of the JS renderer without changing the behavior would be great **:)**

# Answer
> 3 votes
## Mathematica - 164 bytes

I'm happy to agree if you call this cheating, but it wasn't ruled out in the question. I let Mathematica rasterise the string and then throw away all white pixels and generate instructions from the rest:

```
 g=""<>MapIndexed[If[#<1,"",{h,w}=ToString/@(10#2);h<>","<>w<>""]&,ImageData@Rasterize[#,RasterSize->(n=5StringLength@#),ImageSize->n]/.{(1.)..}->0/.{_,_,_}->1,{2}]&

```

It could probably be golfed down even further. Especially the `/.{(1.)..}->0/.{_,_,_}->1` looks suspiciously like it could be simplified.

Slightly ungolfed:

```
g[str_] := (
    n = 5*StringLength[str];
    pixels = ImageData[Rasterize[str, RasterSize->n, ImageSize->n]]
                /. {1., 1., 1.} -> 0
                /. {_, _, _} -> 1;
    StringJoin[
      MapIndexed[
        If[#1 < 1,
           "",
           {h, w} = Map[ToString, 10*#2];
           h <> "," <> w <> ""
        ] &,
        pixels,
        {2}
      ]
    ]
);

```

This will handle really any characters in the string, and you can tweak the size by adjusting the `5` (which means letters are 5 pixels wide, which meets your requirement of them being 50 actual pixels tall).

Here is some example output using a resolution of `7`:

And here using a resolutiong of `9`:

And `12`:

(The screenshots are somewhat minified to fit SE's column width, of course.)

# Answer
> 3 votes
# APL, 196 chars

```
f←37 5 3⍴(555/2)⊤95x⊥32-⍨⎕UCS'ne,[9fkO!|UUmYb~qu"*5n2wJgBe1P~P+E)$?ZGHb4{W(:edC2JdpirhX4I@m/K/q,ww <=:N%(euf9AJ"'
⎕←1↓∊{⍕¨' '⍺','⍵}/¨↑,/{10×(2↑4×⍵-1)∘+¨1-⍨a/⍥,⍳⍴a←⍉f[(' ',⎕A,∊⍕¨0,⍳9)⍳⍵⌷s;;]}¨⍳⍴s←⍞

```

Dialect is Nars2000.

The first line produces the font, which I took from this page. I've encoded it in base 95 as printable ASCII characters, so the first line decodes it and turns it into a 37×5×3 bitmap.

The second line reads a line of input. For each character it extracts the right bitmap from the font, produces a list of coordinates of the 'on' bits, adds an offset to the first coordinate (x) depending on the position in the string, multiplies by 10, formats the result as required, and outputs it.

Here is the output for `HELLO WORLD 9`

```
0,0 0,10 0,20 0,30 0,40 10,20 20,0 20,10 20,20 20,30 20,40 40,0 40,10 40,20 40,30 40,40 50,0 50,20 50,40 60,0 60,20 60,40 80,0 80,10 80,20 80,30 80,40 90,40 100,40 120,0 120,10 120,20 120,30 120,40 130,40 140,40 160,10 160,20 160,30 170,0 170,40 180,10 180,20 180,30 240,0 240,10 240,20 240,30 240,40 250,30 260,0 260,10 260,20 260,30 260,40 280,10 280,20 280,30 290,0 290,40 300,10 300,20 300,30 320,0 320,10 320,20 320,30 320,40 330,0 330,20 330,30 340,10 340,20 340,40 360,0 360,10 360,20 360,30 360,40 370,40 380,40 400,0 400,10 400,20 400,30 400,40 410,0 410,40 420,10 420,20 420,30 480,0 480,10 480,20 480,40 490,0 490,20 490,40 500,0 500,10 500,20 500,30 500,40

```

And here it is turned into an image:

It could probably be golfed a bit more here and there, but the main gain would come from a smarter font encoding.

I can explain the code in more detail if anyone asks.

# Answer
> 1 votes
# Javascript (E6) 274

(261 function + 13 console output)

Not so short, *but* any font, any size, any character

```
F=(m,f="50",F="Georgia")=>{d=1024;e=document.createElement("canvas");c=e.getContext("2d");e.height=e.width=d;c.font=f+"px "+F;c.fillText(m,0,f);
i=c.getImageData(0,0,d,d).data;q='';for(p=d*d*4;p;p-=4)i[p-1]&&(q+=(p>>12)+'0,'+((p>>2)&(d-1))+'0 ');return q.trim()}

```

**Ungolfed**

```
function F(m, f="50", F="Georgia") {
  d = 1024
  e = document.createElement("canvas")
  c = e.getContext("2d")
  e.height = e.width=d
  c.font = f + "px " + F
  c.fillText(m,0,f);
  i = c.getImageData(0,0,d,d).data;
  q=''
  for (p = d*d*4; p; p-=4)
    i[p-1] && (q += (p >> 12)+'0,'+((p>>2) & (d-1))+'0 ');
  return q.trim()
}

```

**Usage**

`console.log(F('HELLO WORLD'))`

`console.log(F('Bonjour, monde',30,'Garamond'))`

---
Tags: code-golf
---


# Question
Title: Program that encodes a message into its own text
Write a program that encodes given text into its own text, provided as input, without disrupting its logic. The program must also work as a decoder, restoring the original message from its text. It must retain its encoding/decoding functions after transformation.

More formally speaking, the required program P must perform the following transformations with the given message text M:
**P(M,P)-\>P\*<br>P\*(P\*)-\>M**

Here **P\*** is the transformed program, which also must satisfy the above rules, that is:
**P\*(M2,P\*)-\>P\****
**P\**(P\**)-\>M2**
and so on... Each subsequent encoding doesn't erase previously encoded text, so P\** carries two messages - M and M2.

The easiest way for the program to distinguish between encoding/decoding modes is by the presence of the extra argument M, but the final decision is up to you, provided it is clearly stated. The program **may** read it's own text from the file. If the chosen language doesn't have means for this, the source text can be passed to the program in any other way.

There are trivial solutions, of course, so this is rather a popularity contest. Nevertheless, I impose restriction forbidding comments in the program text.

# Answer
> 8 votes
# Perl

This is a one-liner in Perl just because it's possible.

```
if($ARGV[0]){open(F,__FILE__);while(<F>){print;print"$ARGV[0]\n"if/^_/;}}else{print<DATA>;}
__DATA__

```

The messages are written after `__DATA__`, most recent first.

# Answer
> 4 votes
# Python

You know what? Why not make it a single expression?

```
P = (lambda M,P=None:(lambda t:P[:74]+repr(M)[1:-1]+"'))"if P else M[74:-3])(''))
Pc = "(lambda M,P=None:(lambda t:P[:74]+repr(M)[1:-1]+\"'))\"if P else M[74:-3])(''))"
P2c = P('Hi there, mate!', Pc)
print "Encode tests:"
print " P2 = P('Hi there, mate!', Pc) =", P2c
exec 'P2 = ' + P2c
print " P2(\"Test 2's the best.\", P2c) =", P2("Test 2's the best.", P2c)

print "Decode tests:"
print "P2(P2) =", P2(P2c)
print "P(P2)  =", P(P2c)
print "P2(P)  =", P2(Pc)
print "P(P)   =", P(Pc)

```

---

Old message; The function P takes the arguments as specified and outputs the resulting code / decoded text.

```
def P(data,func=None):
    text = ""
    if func:
        return func[:35]+data+'"\n'+'\n'.join(func.split('\n')[2:])
    return data[35:].split('\n')[0][:-1]

# The source code.
Pc = """def P(data,func=None):
    text = ""
    if func:
        return func[:35]+data+'"\\n'+'\\n'.join(func.split('\\n')[2:])
    return data[35:].split('\\n')[0][:-1]"""

P2c = P('Hi there, mate!', Pc)
print "Encode test:"
print "P('Hi there, mate!', P) ->"
print P2c

# This is outputted by P('Hi there, mate!', code-of-P)
def P2(data,func=None):
    text = "Hi there, mate!"
    if func:
        return func[:35]+data+'"\n'+'\n'.join(func.split('\n')[2:])
    return data[35:].split('\n')[0][:-1]

print "P2('Text 2', P2) -<"
print P2('Text 2', P2c)

print "Decode test:"
print "P2(P2) =", P2(P2c)
print "P(P2)  =", P(P2c)
print "P2(P)  =", P2(Pc)
print "P(P)   =", P(Pc)

```

# Answer
> 2 votes
## JavaScript

```
var transform = function (p, m) {
    var _M_ = '';
    var source = arguments.callee.toString();
    var msgre = /(_M_ = ').*(';)/;
    var regex = new RegExp(source.replace(/[.*+?^$\[\]{}()\\|]/g, "\\$&").replace(msgre, "$1(.*)$2"));

    var a = p.toString().match(regex);

    if (!a) {
        throw "first argument must be a transform function"
    } else {
        a = a[1];
    }

    if (typeof m == "undefined") {
        return eval("[" + a.split("|")[0] + "]").map(x=>String.fromCharCode(x)).join("");
    } else {
        a = m.toString().split("").map(x => x.charCodeAt(0)) + (a.length ? "|" + a: a);
        return eval("(" + source.replace(msgre, "$1" + a + "$2") + ")");
    }
}

```

Not sure if I understand the problem statement correctly: my decoder will decode **any** program and return the latest message that is encoded in the given program.

Test code:

```
P1 = transform(transform, "first message");
P2 = P1(P1, "second message");

console.log(P1(P1));
console.log(P2(P2));

console.log(P2(P1));
console.log(P1(P2));

// Unspecified behavior
console.log(transform(transform))

```

# Answer
> 2 votes
## Batch

```
@echo off

setLocal enableDelayedExpansion
for /f %%a in (%0) do set a=%%a

if "%~1"=="e" (
    set /a a+=1
    echo !a! %~2 >> %0
    echo message encoded as !a!
) else if "%~1"=="d" for /f "skip=12 tokens=1*" %%a in (%0) do if "%%a"=="%~2" echo %%b

goto :EOF

```

Note there needs to be a carriage return after 'the last line' of `goto :EOF`.

This takes two inputs from stdin. The first of which is what you want to do; `e`, or `d` (encode and decode). The second input depends on the first - if the first input is `e`, then the second input will be the message that you want to encode - if it is `d`, then the second input will be the number of the message you wish to decode (that will be provided after encoding a message).

```
H:\uprof>ed.bat e "Just a message"
message encoded as 1

H:\uprof>ed.bat d 1
Just a message

```

# Answer
> 0 votes
# Cobra

```
use System.Diagnostics
class Program
    var message as int[]? = nil
    def decode(program as String)
        temp = List<of String>(program.split('\n'))
        temp.insert(4, '\t\tEnvironment.exit(0)')
        temp.add('\t\tmessage = \'\'')
        temp.add('\t\tfor i in .message, message += Convert.toString(i to char)')
        temp.add('\t\tFile.writeAllText(\'message.txt\', message)')
        program = temp.join('\n')
        File.writeAllText('decode.cobra', program)
        process = Process()
        process.startInfo.fileName = 'cmd.exe'
        process.startInfo.arguments = '/C cobra decode.cobra'
        process.start
    def encode(message as String, program as String)
        temp = List<of String>()
        for i in message.toCharArray, temp.add(Convert.toString(i to int))
        message = '@' + Convert.toString(c'[')
        for n in temp.count-1, message += temp[n] + ','
        message += temp.pop + ']'
        temp = List<of String>(program.split('\n'))
        temp.insert(26,'\t\t.message = .message ? [message]')
        program = temp.join('\n')
        File.writeAllText('encode.cobra', program)
    def main
        #call methods here
        #.encode(message, program)
        #.decode(program)

```

While the *idea* is trivial, the *execution* of said idea is less-so.

## Encoding

Encoding a message in the program will add the line `.message = .message ? x` immediately after `def main`. This line checks if `.message` is nil, and if so, then it sets `.message` to an integer array containing the character code values of each character in the message; the nil-check and positioning avoid overwriting the new message with an older one. The new program is saved to `encode.cobra`

## Decoding

Decoding the program will add three lines at the end of the main method which cause the program to convert the char codes in `.message` to a string, which is then saved to `message.txt` when the new program is run. The new program is then saved to `decode.cobra` and the compiler is invoked on it.

`decode.cobra` is used like a temporary file and cannot be used to encode or decode another message, use the original or `encode.cobra`

---
Tags: popularity-contest, self-referential
---


title: The Love Letter Mystery

text:
# Question
Title: The Love Letter Mystery
At Hackerrank.com, the love letter mystery is a simple programming problem, which I already solved.

My solution involved calculating the palindrome and counting the number of operations to do it. On Hackerrank, they have another approach, which I don't understand completely:

> Given a string, you have to convert it into a palindrome using a certain set of operations.
>
> Let's assume that the length of the string is L, and the characters are indexed from 0 to L-1. The string will be palindrome, only if the characters at index i and the characters at index (L-1-i) are same. So, we need to ensure that the characters for all such indices are same.
>
> Let's assume that one such set of indices can be denoted by A' and B'. It is given that it takes one operation in decreasing value of a character by 1. So, the total number of operations will be |A'-B'|.We need to calculate this for all such pairs of indices, which can be done in a single for loop. Take a look at the setter's code.

I understand everything up until they mention that the total number of operations are **|A'-B'|, the absolute value between the two indices.** Why is that? For some reason, my head is being thicker (than usual).

Thanks!

======== EDIT ==========

Hey guys, thanks for your input. I thought that this stackexchange site would had been more appropiate than stackoverflow. Is there any stackexchange site where this question is more appropiate?

# Answer
The algorithm might make more sense with a sample implementation to look at (here, in Python):

```
S = raw_input()
L = len(S)
T = 0
for i in range(L/2):
  A = ord(S[i])
  B = ord(S[L-1-i])
  T += abs(A-B)
print T

```

Let's review the problem description. Each character decrement (e.g. `--'b' == 'a'`) counts as a single operation. The problem is to determine the number of operations required to transform the input string into a palindrome.

The algorithm iterates over half the string, and compares the ordinal value of the character at the current index with that of the character across from it (in its mirrored position). If they are not the same, the one that is larger needs to be decremented, but it doesn't actually need to be checked which is which. Taking the absolute value of the difference will produce the correct number of operations needed regardless.

I think a source of confusion might be the wording, *"Let's assume that **one such set of indices** can be denoted by A' and B'."* I believe that the author intended *A'* and *B'* to refer to the *characters* at each of these indices, and not the indices themselves. If they had actually meant to refer to the indices, the algorithm would return the same value for any given string length, which is obviously incorrect.

A golfed version might look like this:

```
s=map(ord,raw_input())
print sum(abs(s[i]-s[~i])for i in range(len(s)/2))

```

I suspect Ruby might be a bit shorter, because indexing a string returns the ordinal value, rather than the individual character.
> 3 votes

---
Tags: algorithm, palindrome
---


# Question
Title: Not-endless Recursion without a base case
Write a recursive function/program, to calculate either the **Factorial** or the **Fibonacci** number of a given non-negative integer, without explicitly implementing the base case(s).

Your program/function must return/output the correct value in a reasonable time.

**You cannot**

1. Use `if` statement anywhere in your program/function, nor `switch` nor short-if-syntax (`?:`). Not even loops. Basically all control-flow statements are forbidden.
2. Use `try, catch` or exceptions of any kind.
3. Terminate the program (anything like `exit(1)`).
4. Use external sources (file, web, etc.)
5. Avoid recursion and return the proper value otherwise. (Your function must be recursive).
6. Use any of the standard loopholes.

**You can**

* Use polymorphism, create threads, wrap the Integer type with your own class, or use any other mechanism your language or runtime has. (I can think of a solution that uses the *lazy-evaluation*, for instance). The function/program can be written as more than one function, using Mutual Recursion, if it helps you.

Please provide a **short** explanation of what you did.

Be creative! The winning answer is the one with the most upvotes by 2014-06-23 (a week from today).

**EDIT**:

Some clarifications:

Using Pattern Matching in Functional Programming Languages is OK since it's considered as Polymorphism. The solution should be trivial though, so I guess it won't have the chance to win, since it is a . It is still a legitimate answer.

Although some may say it's flow control in disguise, using *lazy evaluation*, (or *short circuit evaluation*) is allowed as well.

# Answer
# C - factorial

simple as that

```
int not_factorial(int n){return 1;}
int factorial(int n)
{
    int (*maybe_factorial[])(int) = {factorial, not_factorial};
    return n*maybe_factorial[!(n-1)](n-1);
}

```

the function factorial is almost like a basic recursive approach but not\_factorial only returns 1.
If I create an array of function pointers (0: fac, 1: not\_fac), then I can control which one should be executed at the next call:
`maybe_factorial[0](n-1)` calls factorial
`maybe_factorial[1](n-1)` calls not\_factorial.
`!(n-1)` means `if n > 1 return 0 else return 1`
> 12 votes

# Answer
# Javascript

Just a quick idea to get things going, nothing too fancy:

```
var t = [1];

function factorial (n) {
    var h = arguments[1] ||  1;
    t.push (t[t.length-1] * h);
    return t[n] || factorial (n,h+1);
}

```

This should be considered a program rather than a function, because it depends on a variable that is outside the function's scope (and it only works once), but I'll try to edit it later as a proper closure.

The trick here relies on the combination of JS's lazy evaluation and the fact that undefined object properties are merely an `undefined` value rather than a reason to throw an error. Rather than doing a boring recursion down from `n` to 0, I've decided to add a "secret" second parameter (`arguments[1]`) as a counter from 1 to `n`. Each iteration multiplies the last element of the `t` array by the counter, to fill the array with all the factorial values, and once the array has an `n`th element I stop the recursion and return it.
> 5 votes

# Answer
# Haskell

```
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

```

Thanks to pattern matching, there is no need for control structures in this function.

As Tal mentionned, this is a textbook example for functional languages, one of the first shown when learning them.
> 4 votes

# Answer
# C++

```
#include <iostream>
using namespace std;

template <int K>
class Int
    {
    public :
        int Fact(void);
    };

template<>
int Int<0>::Fact()
    {
    return 1;
    }

template<int K>
int Int<K>::Fact()
    {
    Int <K-1> x;
    return K*x.Fact();
    }

int main(void)
    {
    Int<5> A;

    cout << A.Fact() << endl;
    }

```
> 4 votes

# Answer
# Python

```
f = lambda n: int(n==0) or n*f(n-1)

```

We exploit the short-circuiting behavior of `or`. For `n=0`, the base-case check returns true, which is converted to the int `1`, and otherwise, the `or` expression evaluates to the recursive expression.
> 4 votes

# Answer
# Scala

Would this be the lazy solution the OP alluded to?

```
// Factorial
lazy val fac: Stream[Int] = 1 #:: Stream.from(1).map{i => i * fac(i - 1)}
// Fibonacci
lazy val fib: Stream[Int] = 0 #:: 1 #:: Stream.from(2).map{i => fib(i - 1) + fib(i - 2)}

```

Creates a lazily evaluated stream. The first elements are hard-coded, but subsequent elements are defined recursively, with no control flow. As a side effect, values are memo-ised.
> 1 votes

# Answer
## Tcl

Well, if we can't use `if` or `switch` or `for` or `while` to test then it looks like we'll have to implement our own **if**.

I personally feel re-implementing `if` is a bit more impressive than polymorphism because polymorphism (or function overloading) is still using built in language feature. What I'm doing is implementing a feature from scratch!

```
# First we write functions called 0 and 1
proc 0 {a b} {uplevel 1 $b}
proc 1 {a b} {uplevel 1 $a}

# Now we try to implement IF, we'll call it _I_F_
proc _I_F_ {statement a b} {
    uplevel 1 [list [expr $statement] $a $b]
}

# Now lets write a recursive countdown function
# using our scratchbuilt if:
proc countdown {number} {
    puts $number
    _I_F_ "$number>0" "count [expr $number-1]" "puts done"
}

# Lets see if it works:
countdown 10 ;# should count down to 0

```

Notes:

* `uplevel` is like evel only it allows you to execute the code in any stack level you chose.
* Tcl always expects a function name to be the first word of a statement. Therefore if you want to evaluate something like `$a>$b` or `$a==$b` you can't because you can't start a statement with a variable. That's what `expr` is for - it's a function that evaluates expressions.
* Comparison expressions such as `$a<$b`, like in other languages, return true or false. In tcl true is canonically 1 and false is canonically 0. So the `expr $statement` returns 0 or 1.
* We then construct a statement using `list` which, depending on the `expr` will start with 0 or 1 and uplevel it. This in turn executes either the function `0` or the function `1`.
> 1 votes

---
Tags: popularity-contest, restricted-source
---


title: Regex that only matches itself

text:
# Question
Title: Regex that only matches itself
There are some pretty cool challenges out there involving regex (Self-matching regex, Regex validating regex)

This may well be impossible, but is there a regex that will ONLY match itself?

NOTE, delimiters must be included:

for example `/thing/` must match `/thing/` and not `thing`. The only match possible for your expression must be the expression itself. Many languages allow the implementation of a string in the place of a regular expression. For instance in Go

```
package main

import "fmt"
import "regexp"

func main() {

    var foo = regexp.MustCompile("bar")
    fmt.Println(foo.MatchString("foobar"))
}

```

but for the sake of the challenge, let the expression be delimited (starting symbol, expression, ending symbol ex: `/fancypantpattern/` or `@[^2048]@`), if you want to argue quotes as your delimiter, so be it. I think given the apparent difficulty of this problem it won't make much of a difference.

## To help you along:

Quick hack I put together for rubular.com (a webpage for ruby regex editing):

```
var test = document.getElementById("test")
,regex = document.getElementById("regex")
,delimiter="/"
,options = document.getElementById("options")
,delay = function(){test.value = delimiter + regex.value + delimiter + options.value}
,update = function(e){
    // without delay value = not updated value
    window.setTimeout(delay,0);
}
regex.onkeydown = update;
options.onkeydown = update;

```

Even though this is technically 'code golf' I will be very impressed if anyone can find an answer/ prove it is impossible.

**Link is now fixed. Sorry to all**

Winning answer thus far: jimmy23013 with 40 characters

# Answer
## PCRE flavor, 261 289 210 184 127 109 71 53 51 44 40 bytes

Yes, it is possible!

```
<^<()(?R){2}>\z|\1\Q^<()(?R){2}>\z|\1\Q>

```

Try it here. (But `/` is shown to be the delimiter on Regex101.)

Please refrain from making unnecessary edits (updates) on the Regex101 page. If your edit doesn't actually involve improving, trying or testing this regex, you could fork it or create new ones from their homepage.

The version works more correctly on Regex101 (44 bytes):

```
/^\/()(?R){2}\/\z|\1\Q^\/()(?R){2}\/\z|\1\Q/

```

Try it here.

This is much simpler than the original version and works more like a traditional quine. It tries to define a string without using it, and use it in a different place. So it can be placed very close to one end of the regex, to reduce the number of characters needing more characters to define the matching pattern and repeated more times.

Explanations:

* `\Q^\/()(?R){2}\/\z|\1\Q` matches the string `^\/()(?R){2}\/\z|\1\Q`. This uses a quirk that `\Q...\E` doesn't have to be closed, and unescaped delimiters work in `\Q`. This made some previous versions work only on Regex101 and not locally. But fortunately the latest version worked, and I golfed off some more bytes using this.
* `\1` before the `\Q` matches the captured group 1. Because group 1 doesn't exist in this option, it can only match in recursive calls. In recursive calls it matches empty strings.
* `(?R){2}` calls the whole regex recursively twice, which matches `^\/()(?R){2}\/\z|\1\Q` for each time.
* `()` does nothing but capture an empty string into group 1, which enables the other option in recursive calls.
* `^\/()(?R){2}\/\z` matches `(?R){2}` with delimiters added, from the beginning to the end. The `\/` before the recursive calls also made sure this option itself doesn't match in recursive calls, because it won't be at the beginning of the string.

51 bytes with closed `\Q...\E`:

```
/\QE\1|^\/(\\)Q(?R){2}z\/\E\1|^\/(\\)Q(?R){2}z\/\z/

```

Try it here.

### Original version, 188 bytes

Thanks to Martin Büttner for golfing off about 100 bytes!

```
/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.\2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{11}$/

```

Try it here.

Or 210 bytes without `\Q...\E`:

```
/^(?=.{194}\\2\\.\)\{2}\.\{12}\$\/D$)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{194}\2\\\2\\2\2\\\2\\\2\.\2\\\2\)\2\\\2\{2}\2\\\2\.\2\\\2\{12}\2\\\2\$\2\\\2\/D\2\$\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{12}$/D

```

Try it here.

Expanded version:

```
/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)        # Match things near the end.
((?=(.2.|))                               # Capture an empty string or \2\ into group 2.
   \2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.
   \2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)      # 1st line escaped.
   \2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\) # 2nd line escaped.
){2}
.{11}$/x

```

Extensions like `(?=` and `\1` have made the so-called "regular" expressions no longer regular, which also makes quines possible. Backreference is not regular, but lookahead is.

Explanation:

* I use `\2\` in place of `\` to escape special characters. If `\2` matches the empty string, `\2\x` (where `x` is a special character) matches the `x` itself. If `\2` matches `\2\`, `\2\x` matches the escaped one. `\2` in the two matches of group 1 can be different in regex. In the first time `\2` should match the empty string, and the second time `\2\`.
* `\Q\2\)){2}.{11}$\E\/\z` (line 1) matches 15 characters from the end. And `.{11}$` (line 7) matches 11 characters from the end (or before a trailing newline). So the pattern just before the second pattern must match the first 4 or 3 characters in the first pattern, so `\2\.\2\|\2\)\2\)` must match `...\2\)` or `...\2\`. There cannot be a trailing newline because the last character should be `)`. And the matched text doesn't contain another `)` before the rightmost one, so all other characters must be in the `\2`. `\2` is defined as `(.2.|)`, so it can only be `\2\`.
* The first line makes the whole expression matches exactly 188 characters since everything has a fixed length. The two times of group 1 matches 45\*2 characters plus 29 times `\2`. And things after group 1 matches 11 characters. So the total length of the two times `\2` must be exactly 3 characters. Knowing `\2` for the second time is 3 characters long, it must be empty for the first time.
* Everything except the lookahead and `\2` are literals in group 1. With the two times `\2` known, and the last few characters known from the first line, this regex matches exactly one string.
* Martin Büttner comes up with the idea of using lookahead to capture group 2 and make it overlap with the quine part. This removed the characters not escaped in the normal way between the two times of group 1, and help avoided the pattern to match them in my original version, and simplified the regex a lot.

## Regex without recursions or backreferences, 85 bytes

Someone may argue that expressions with recursions or backreferences are not real "regular" expressions. But expressions with only lookahead can still only match regular languages, although they may be much longer if expressed by traditional regular expressions.

```
/(?=.*(\QE\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\E\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\z/

```

Try it here.

610 bytes without `\Q...\E` (to be golfed):

```
/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}(.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\(.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

```

Try it here.

The idea is similar.

```
/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)
((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)
(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}
  (.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}
    (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\
    (.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}
  (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

```

## The basic regular expression

If lookahead is not allowed, the best I can do now is:

```
/\\(\\\(\\\\){2}/

```

which matches

```
\\(\\\(\\

```

If `{m,n}` quantifier is not allowed, it is impossible because nothing which can only match one string, can match a string longer than itself. Of course one can still invent something like `\q` which only matches `/\q/`, and still say expressions with that regular. But apparently nothing like this is supported by major implementations.
> 670 votes

---
Tags: code-golf, string, decision-problem, regular-expression, pattern-matching
---


title: Tower of Hanoi Sort

text:
# Question
Title: Tower of Hanoi Sort
Write a function/subroutine to sort a list of integers, Tower of Hanoi style.

You will be given a stack of integers. This is the main stack.

You are also given two more helper stacks. These helper stacks have a unique property though: every element must be smaller than or the same size as the element underneath it. The main stack has no such restriction.

You are tasked with sorting the main stack in place, putting the largest integers underneath. Your function/subroutine will return (or equivalent) the number of moves it made in sorting the stack.
Note: you must sort the main stack **in place**, no sorting onto another stack and calling that the answer. However, if you for some reason cannot do so, you may simulate the mutable stacks, but remember that this is Tower of Hanoi sort; there are only 3 pegs and only 1 peg may be unordered.

Your function/subroutine can inspect any stack at any time, but it can only make a move by popping and pushing. A single move is a pop from one stack which is pushed to another.

Test your function/subroutine for each permutation of the first 6 natural numbers. In other words, test your function/subroutine for `{1},{2},...,{6},{1,1},{1,2},...,{1,6},{2,1},...` (this should be a total of `6<sup>1</sup>+6<sup>2</sup>+...+6<sup>6</sup>` or `55986` possibilities (thanks to Howard for correcting my math)). The function/subroutine that moves elements the least number of times wins.

# Answer
# Java - optimal solution (1080544 moves)

This solution builds a shortest path tree from the target and backwards, then traverses the path from the initial state to the target. Lots of room for speed improvement, but it still completes all 55986 problems in about a minute.

Assuming the algorithm is correctly implemented, this should be the theoretically best solution.

```
import java.util.*;

public class HanoiSort {

    public static void main(String[] args) {
        int sumNumMoves = 0;
        for (int size = 1; size <= 6; ++size) {
            Collection<List<Integer>> initMainStacks = generateInitMainStacks(Collections.<Integer>emptyList(), size);
            for (List<Integer> initMainStack : initMainStacks) {
                sumNumMoves += solve(initMainStack);
            }
        }
        System.out.println(sumNumMoves);
    }

    /*
     * Recursively create initial main stacks
     */
    private static Collection<List<Integer>> generateInitMainStacks(List<Integer> mainStack, int remainingSize) {
        Collection<List<Integer>> initMainStacks;
        if (remainingSize > 0) {
            initMainStacks = new ArrayList<>();
            for (int number = 1; number <= 6; ++number) {
                List<Integer> nextMainStack = new ArrayList<>(mainStack);
                nextMainStack.add(number);
                initMainStacks.addAll(generateInitMainStacks(nextMainStack, remainingSize - 1));
            }
        } else {
            List<Integer> initMainStack = new ArrayList<>(mainStack);
            initMainStacks = Collections.singleton(initMainStack);
        }
        return initMainStacks;
    }

    private static final List<Integer> EMPTY_STACK = Collections.emptyList();

    /*
     * Create a shortest path tree, starting from the target state (sorted main stack). Break when the initial state
     * is found, since there can be no shorter path. This is akin to building a chess endgame tablebase.
     *
     * Traverse the path from initial state to the target state to count the number of moves.
     */
    private static int solve(List<Integer> initMainStack) {
        List<List<Integer>> initState = Arrays.asList(new ArrayList<>(initMainStack), EMPTY_STACK, EMPTY_STACK);
        List<Integer> targetMainStack = new ArrayList<>(initMainStack);
        Collections.sort(targetMainStack);
        List<List<Integer>> targetState = Arrays.asList(new ArrayList<>(targetMainStack), EMPTY_STACK, EMPTY_STACK);
        Map<List<List<Integer>>,List<List<Integer>>> tablebase = new HashMap<>();
        Deque<List<List<Integer>>> workQueue = new ArrayDeque<>();
        tablebase.put(targetState, null);
        workQueue.add(targetState);
        while (!tablebase.containsKey(initState)) {
            assert !workQueue.isEmpty() : initState.toString();
            List<List<Integer>> state = workQueue.removeFirst();
            Collection<List<List<Integer>>> prevStates = calcPrevStates(state);
            for (List<List<Integer>> prevState : prevStates) {
                if (!tablebase.containsKey(prevState)) {
                    tablebase.put(prevState, state);
                    workQueue.add(prevState);
                }
            }
        }

        int numMoves = 0;
        List<List<Integer>> state = tablebase.get(initState);
        while (state != null) {
            ++numMoves;
            state = tablebase.get(state);
        }
        return numMoves;
    }

    /*
     * Given a state, calculate all possible previous states
     */
    private static Collection<List<List<Integer>>> calcPrevStates(List<List<Integer>> state) {
        Collection<List<List<Integer>>> prevStates = new ArrayList<>();
        for (int fromStackNo = 0; fromStackNo < 3; ++fromStackNo) {
            List<Integer> fromStack = state.get(fromStackNo);
            if (!fromStack.isEmpty()) {
                int number = fromStack.get(0);
                for (int toStackNo = 0; toStackNo < 3; ++toStackNo) {
                    if (toStackNo != fromStackNo) {
                        List<Integer> toStack = state.get(toStackNo);
                        if ((toStackNo == 0) || toStack.isEmpty() || (toStack.get(0) >= number)) {
                            List<List<Integer>> prevState = new ArrayList<>(state);
                            List<Integer> prevFromStack = new ArrayList<>(fromStack);
                            prevFromStack.remove(0);
                            prevState.set(fromStackNo, prevFromStack);
                            List<Integer> prevToStack = new ArrayList<>(toStack);
                            prevToStack.add(0, number);
                            prevState.set(toStackNo, prevToStack);
                            prevStates.add(prevState);
                        }
                    }
                }
            }
        }
        return prevStates;
    }

}

```
> 6 votes

# Answer
## Python,  3983838 3912258 moves over 55986 inputs

This is ***very*** inefficient.

I'll add the total number of moves after the OP clarifies whether they are for all of those cases or for specific other cases.

---

```
from itertools import product       # Required for testing
import time                         # Required if you want to see it in action.

from pycallgraph import PyCallGraph
from pycallgraph.output import GraphvizOutput

def main( l ):
    ################### Data ###################
    global a , b , c , d , copy , total_moves
    total_moves = 0

    a = [ x for x in l ]  # Input stack, order doesn't matter, we'll try to empty this one
    b = []                # Usable stack, restricted by order, we'll try to get the final sorted order here
    c = []                # Usable stack, restricted by order, but we'll try to keep it as empty as possible

    d = { 'a':a , 'b':b , 'c':c }  # Passing the stacks to the nested functions by their names as a string
    copy = [ x for x in a ]        # reference copy, read-only

    ################### Functions ###################
    def is_correct( stack ):
        if d[ stack ] == sorted( copy , reverse = True ):
            return True
        else:
            return False

    def reverse_exchange( source , destination , keep = 0 ):
        #
        # keep is the number of elements to keep at the bottom of the source stack
        # The remaining top elements are moved to the destination stack
        # We first move the top elements to stack a
        # and from a to c so that the order is preserved
        # effectively splitting the source stack into two
        #

        i = 0
        while len( d[ source ] ) > keep :
            move( source , 'a' )
            i += 1
        else:
            while i > 0:
                move( 'a' , destination )
                i -= 1

    # def validate( source , destination ):
    #   #
    #   # Validates the give move
    #   #
    #   if len( d[ source ] ) == 0:
    #       return False
    #   if destination == 'a' or len( d[ destination ] ) == 0:
    #       return True
    #   else:
    #       if d[ destination ][ len( d[ destination ] ) - 1 ] >= d[ source ][ len( d[ source ] ) - 1 ]:
    #           return True
    #       else:
    #           return False

    def move( source , destination ):
        global total_moves
        # if validate( source , destination ):
        d[ destination ].append( d[ source ].pop() )

        total_moves += 1

            # Uncomment the following to view the workings step-by-step
            # print '\n'
            # print a
            # print b
            # print c
            # print '\n'
            # time.sleep(0.1)

        return True
        # else:
        #   return False

    ################### Actual logic ###################
    while ( not is_correct( 'a' ) ):

        copy_b   = [x for x in b ]                         # Checking where the topmost element of a
        top_of_a = a[ len(a) - 1 ]                         # should be inserted
        copy_b.append( top_of_a )                          #
        sorted_copy_b = sorted( copy_b , reverse = True )  #

        reverse_exchange( 'b' , 'c' , sorted_copy_b.index( top_of_a ) )                                                  # Sandwiching the top-most element
        move( 'a' , 'b' )                                                                                # to proper position in b
        while (len(b) > 0 and len(c) > 0 and len(a) > 0) and (sorted (b , reverse = True)[0] <= a[len(a) - 1] <= c[0]):  #  # Optimization
            move( 'a' , 'b' )                                                                                #  #
        reverse_exchange( 'c' , 'b' )                                                                                # b is always sorted, c is always empty

        if is_correct( 'b' ):                     # Just moving b to a
            while ( not is_correct( 'a' ) ):      # The entire program focuses on "insertion sorting"
                reverse_exchange( 'b' , 'c' , 1 ) # elements of a onto b while keeping c empty
                move( 'b' , 'a' )                 #
                if len(c) > 0 :                       #
                    reverse_exchange( 'c' , 'b' , 1 ) # Slightly more efficient
                    move('c' , 'a' )                  #

    return total_moves

# with PyCallGraph( output= GraphvizOutput() ):

    ################### Test cases #############
i = 0
for elements in xrange( 1 , 7 ):
    for cartesian_product in product( [ 1 , 2 , 3 , 4 , 5 , 6 ] , repeat = elements ):
        input_list = [ int( y ) for y in cartesian_product ]
        i += main(input_list)
        print i
print i

```

---

### Explanation

What, comments not good enough for you?

---

Note to OP: Thanks for not making this code-golf.
> 5 votes

# Answer
# C - 2547172 for 55986 inputs

There is a lot of room for improvement here. For my own sanity, I simplified this so that it was only possible to inspect the top element of each stack. Lifting this self-imposed restriction would allow optimizations like determining the final order in advance and trying to minimize the number of moves required to achieve it. A compelling example is that my implementation has worst case behavior if the main stack is already sorted.

## Algorithm:

1. Fill both auxiliary stacks (room for optimization here, possibly assigning to which stack based on some kind of pivot).
2. Merge sort the auxiliary stacks back onto the main stack.
3. Repeat 1-2 until the main stack is sorted (but in reverse).
4. Reverse the main stack (more room for optimization, shuffling a lot of the same elements repeatedly).

## Analysis:

* Additional space complexity is O(n) (for the two auxiliary stacks), which is good, since that was a requirement of the problem.
* Time complexity is O(n^2) by my count. Corrections are welcome.

---

```
#include <assert.h>
#include <stdio.h>

#define SIZE 6

int s0[SIZE + 1];
int s1[SIZE + 1];
int s2[SIZE + 1];

int
count(int *stack)
{
    return stack[0];
}

int
top(int *stack)
{
    return stack[stack[0]];
}

void
push(int *stack, int value)
{
    assert(count(stack) < SIZE && "stack overflow");
    assert((stack == s0 || count(stack) == 0 || value <= top(stack)) && "stack order violated");
    stack[++stack[0]] = value;
}

int
pop(int *stack)
{
    int result = stack[stack[0]];
    assert(count(stack) > 0 && "stack underflow");
    stack[stack[0]] = 0;
    stack[0]--;
    return result;
}

int permutations;

void
permute(int len, int range, void (*cb)(void))
{
    int i;
    if(len == 0)
    {
        permutations++;
        cb();
        return;
    }
    for(i = 1; i <= range; i++)
    {
        push(s0, i);
        permute(len - 1, range, cb);
        pop(s0);
    }
}

void
print(void)
{
    int i;
    for(i = 1; i <= count(s0); i++)
    {
        printf("%d ", s0[i]);
    }
    printf("\n");
}

int save[SIZE + 1];

void
copy(int *src, int *dst)
{
    int i;
    for(i = 0; i <= SIZE; i++)
    {
        dst[i] = src[i];
    }
}

int total;

void
move(int *src, int *dst)
{
    total++;
    push(dst, pop(src));
}

void
merge(void)
{
    while(1)
    {
        if(count(s1) == 0 && count(s2) == 0)
        {
            break;
        }
        else if(count(s1) == 0 || (count(s2) > 0 && top(s2) < top(s1)))
        {
            move(s2, s0);
        }
        else
        {
            move(s1, s0);
        }
    }
}

void
reverse(void)
{
    while(1)
    {
        while(count(s2) == 0 || top(s0) == top(s2))
        {
            move(s0, s2);
        }
        if(count(s0) == 0 || top(s2) < top(s0))
        {
            while(count(s2) > 0)
            {
                move(s2, s0);
            }
            break;
        }
        while(count(s0) > 0 && (count(s1) == 0 || top(s0) <= top(s1)))
        {
            move(s0, s1);
        }
        while(count(s2) > 0)
        {
            move(s2, s0);
        }
        merge();
    }
}

void
sort(void)
{
    while(1)
    {
        if(count(s0) == 0)
        {
            merge();
            reverse();
            break;
        }
        else if(count(s1) == 0 || top(s1) >= top(s0))
        {
            move(s0, s1);
        }
        else if(count(s2) == 0 || top(s2) >= top(s0))
        {
            move(s0, s2);
        }
        else
        {
            merge();
        }
    }
}

void
helper(void)
{
    copy(s0, save);
    sort();
    copy(save, s0);
}

int
main(void)
{
    permute(1, 6, helper);
    permute(2, 6, helper);
    permute(3, 6, helper);
    permute(4, 6, helper);
    permute(5, 6, helper);
    permute(6, 6, helper);
    printf("%d\n", permutations);
    printf("%d\n", total);
    return 0;
}

```
> 5 votes

# Answer
## Python: ~~1,688,293~~ ~~1,579,182~~ ~~1,524,054~~ ~~1,450,842~~ 1,093,195 moves

The main method is `main_to_help_best`, which is to move some selected elements from main stack to helper stack. It has a flag `everything` which defines whether we want it to move everything into the specified `destination`, or whether we want to keep only the largest in `destination` while the rest in the other helper.

Supposing we are moving to `dst` using helper `helper`, the function can roughly be described as follows:

1. Find the positions of largest elements
2. Move everything on top of the top-most largest element to `helper` recursively
3. Move the largest element to `dst`
4. Push back from `helper` to main
5. Repeat 2-4 until the largest elements are in `dst`
6. a. If `everything` is set, recursively move elements in main to `dst`
b. Otherwise, recursively move elements in main to `helper`

The main sort algorithm (`sort2` in my code) will then call `main_to_help_best` with `everything` set to `False`, and then move the largest element back to main, then move everything from the helper back to main, keeping it sorted.

More explanation embedded as comments in the code.

Basically the principles that I used are:

1. Keep one helper to contain the maximum element(s)
2. Keep another helper to contain any other elements
3. Don't do unnecessary moves as much as possible

Principle 3 is implemented by not counting the move if the source is the previous destination (i.e., we just moved main to help1, then we want to move from help1 to help2), and further, we reduce the number of movement by 1 if we are moving it back to the original position (i.e. main to help1 then help1 to main). Also, if the previous `n` moves are all moving the same integer, we can actually reorder those `n` moves. So we also take advantage of that to reduce the number of moves further.

This is valid since we know all the elements in the main stack, so this can be interpreted as seeing in the future that we're going to move the element back, we should not make this move.

Sample run (stacks are displayed bottom to top - so the first element is the bottom):

```
Length 1
Moves: 0
Tasks: 6
Max: 0 ([1])
Average: 0.000

Length 2
Moves: 60
Tasks: 36
Max: 4 ([1, 2])
Average: 1.667

Length 3
Moves: 1030
Tasks: 216
Max: 9 ([2, 3, 1])
Average: 4.769

Length 4
Moves: 11765
Tasks: 1296
Max: 19 ([3, 4, 2, 1])
Average: 9.078

Length 5
Moves: 112325
Tasks: 7776
Max: 33 ([4, 5, 3, 2, 1])
Average: 14.445

Length 6
Moves: 968015
Tasks: 46656
Max: 51 ([5, 6, 4, 3, 2, 1])
Average: 20.748

--------------
Overall
Moves: 1093195
Tasks: 55986
Average: 19.526

```

We can see that the worst case is when the largest element is placed on the second bottom, while the rest are sorted. From the worst case we can see that the algorithm is O(n^2).

The number of moves is obviously minimum for `n=1` and `n=2` as we can see from the result, and I believe this is also minimum for larger values of `n`, although I can't prove it.

More explanations are in the code.

```
from itertools import product

DEBUG = False

def sort_better(main, help1, help2):
    # Offset denotes the bottom-most position which is incorrect
    offset = len(main)
    ref = list(reversed(sorted(main)))
    for idx, ref_el, real_el in zip(range(len(main)), ref, main):
        if ref_el != real_el:
            offset = idx
            break

    num_moves = 0
    # Move the largest to help1, the rest to help2
    num_moves += main_to_help_best(main, help1, help2, offset, False)
    # Move the largest back to main
    num_moves += push_to_main(help1, main)
    # Move everything (sorted in help2) back to main, keep it sorted
    num_moves += move_to_main(help2, main, help1)
    return num_moves

def main_to_help_best(main, dst, helper, offset, everything=True):
    """
    Moves everything to dst if everything is true,
    otherwise move only the largest to dst, and the rest to helper
    """
    if offset >= len(main):
        return 0
    max_el = -10**10
    max_idx = -1
    # Find the location of the top-most largest element
    for idx, el in enumerate(main[offset:]):
        if el >= max_el:
            max_idx = idx+offset
            max_el = el
    num_moves = 0
    # Loop from that position downwards
    for max_idx in range(max_idx, offset-1, -1):
        # Processing only at positions with largest element
        if main[max_idx] < max_el:
            continue
        # The number of elements above this largest element
        top_count = len(main)-max_idx-1
        # Move everything above this largest element to helper
        num_moves += main_to_help_best(main, helper, dst, max_idx+1)
        # Move the largest to dst
        num_moves += move(main, dst)
        # Move back the top elements
        num_moves += push_to_main(helper, main, top_count)
    # Here, the largest elements are in dst, the rest are in main, not sorted
    if everything:
        # Move everything to dst on top of the largest
        num_moves += main_to_help_best(main, dst, helper, offset)
    else:
        # Move everything to helper, not with the largest
        num_moves += main_to_help_best(main, helper, dst, offset)
    return num_moves

def verify(lst, moves):
    if len(moves) == 1:
        return True
    moves[1][0][:] = lst
    for src, dst, el in moves[1:]:
        move(src, dst)
    return True

def equal(*args):
    return len(set(str(arg.__init__) for arg in args))==1

def move(src, dst):
    dst.append(src.pop())
    el = dst[-1]
    if not equal(dst, sort.lst) and list(reversed(sorted(dst))) != dst:
        raise Exception('HELPER NOT SORTED: %s, %s' % (src, dst))

    cur_len = len(move.history)
    check_idx = -1
    matched = False
    prev_src, prev_dst, prev_el = move.history[check_idx]
    # As long as the element is the same as previous elements,
    # we can reorder the moves
    while el == prev_el:
        if equal(src, prev_dst) and equal(dst, prev_src):
            del(move.history[check_idx])
            matched = True
            break
        elif equal(src, prev_dst):
            move.history[check_idx][1] = dst
            matched = True
            break
        elif equal(dst, prev_src):
            move.history[check_idx][0] = src
            matched = True
            break
        check_idx -= 1
        prev_src, prev_dst, prev_el = move.history[check_idx]
    if not matched:
        move.history.append([src, dst, el])
    return len(move.history)-cur_len

def push_to_main(src, main, amount=-1):
    num_moves = 0
    if amount == -1:
        amount = len(src)
    if amount == 0:
        return 0
    for i in range(amount):
        num_moves += move(src, main)
    return num_moves

def push_to_help(main, dst, amount=-1):
    num_moves = 0
    if amount == -1:
        amount = len(main)
    if amount == 0:
        return 0
    for i in range(amount):
        num_moves += move(main, dst)
    return num_moves

def help_to_help(src, dst, main, amount=-1):
    num_moves = 0
    if amount == -1:
        amount = len(src)
    if amount == 0:
        return 0
    # Count the number of largest elements
    src_len = len(src)
    base_el = src[src_len-amount]
    base_idx = src_len-amount+1
    while base_idx < src_len and base_el == src[base_idx]:
        base_idx += 1

    # Move elements which are not the largest to main
    num_moves += push_to_main(src, main, src_len-base_idx)
    # Move the largest to destination
    num_moves += push_to_help(src, dst, base_idx+amount-src_len)
    # Move back from main
    num_moves += push_to_help(main, dst, src_len-base_idx)
    return num_moves

def move_to_main(src, main, helper, amount=-1):
    num_moves = 0
    if amount == -1:
        amount = len(src)
    if amount == 0:
        return 0
    # Count the number of largest elements
    src_len = len(src)
    base_el = src[src_len-amount]
    base_idx = src_len-amount+1
    while base_idx < src_len and base_el == src[base_idx]:
        base_idx += 1

    # Move elements which are not the largest to helper
    num_moves += help_to_help(src, helper, main, src_len-base_idx)
    # Move the largest to main
    num_moves += push_to_main(src, main, base_idx+amount-src_len)
    # Repeat for the rest of the elements now in the other helper
    num_moves += move_to_main(helper, main, src, src_len-base_idx)
    return num_moves

def main():
    num_tasks = 0
    num_moves = 0
    for n in range(1, 7):
        start_moves = num_moves
        start_tasks = num_tasks
        max_move = -1
        max_main = []
        for lst in map(list,product(*[[1,2,3,4,5,6]]*n)):
            num_tasks += 1
            if DEBUG: print lst, [], []
            sort.lst = lst
            cur_lst = lst[:]
            move.history = [(None, None, None)]
            help1 = []
            help2 = []
            moves = sort_better(lst, help1, help2)
            if moves > max_move:
                max_move = moves
                max_main = cur_lst
            num_moves += moves

            if DEBUG: print '%s, %s, %s (moves: %d)' % (cur_lst, [], [], moves)
            if list(reversed(sorted(lst))) != lst:
                print 'NOT SORTED: %s' % lst
                return
            if DEBUG: print

            # Verify that the modified list of moves is still valid
            verify(cur_lst, move.history)
        end_moves = num_moves - start_moves
        end_tasks = num_tasks - start_tasks
        print 'Length %d\nMoves: %d\nTasks: %d\nMax: %d (%s)\nAverage: %.3f\n' % (n, end_moves, end_tasks, max_move, max_main, 1.0*end_moves/end_tasks)
    print '--------------'
    print 'Overall\nMoves: %d\nTasks: %d\nAverage: %.3f' % (num_moves, num_tasks, 1.0*num_moves/num_tasks)

# Old sort method, which assumes we can only see the top of the stack
def sort(main, max_stack, a_stack):
    height = len(main)
    largest = -1
    num_moves = 0
    a_stack_second_el = 10**10
    for i in range(height):
        if len(main)==0:
            break
        el = main[-1]
        if el > largest: # We found a new maximum element
            if i < height-1: # Process only if it is not at the bottom of main stack
                largest = el
                if len(a_stack)>0 and a_stack[-1] < max_stack[-1] < a_stack_second_el:
                    a_stack_second_el = max_stack[-1]
                # Move aux stack to max stack then reverse the role
                num_moves += help_to_help(a_stack, max_stack, main)
                max_stack, a_stack = a_stack, max_stack
                if DEBUG: print 'Moved max_stack to a_stack: %s, %s, %s (moves: %d)' % (main, max_stack, a_stack, num_moves)
                num_moves += move(main, max_stack)
                if DEBUG: print 'Moved el to max_stack: %s, %s, %s (moves: %d)' % (main, max_stack, a_stack, num_moves)
        elif el == largest:
            # The maximum element is the same as in max stack, append
            if i < height-1: # Only if the maximum element is not at the bottom
                num_moves += move(main, max_stack)
        elif len(a_stack)==0 or el <= a_stack[-1]:
            # Current element is the same as in aux stack, append
            if len(a_stack)>0 and el < a_stack[-1]:
                a_stack_second_el = a_stack[-1]
            num_moves += move(main, a_stack)
        elif a_stack[-1] < el <= a_stack_second_el:
            # Current element is larger, but smaller than the next largest element
            # Step 1
            # Move the smallest element(s) in aux stack into max stack
            amount = 0
            while len(a_stack)>0 and a_stack[-1] != a_stack_second_el:
                num_moves += move(a_stack, max_stack)
                amount += 1

            # Step 2
            # Move all elements in main stack that is between the smallest
            # element in aux stack and current element
            while len(main)>0 and max_stack[-1] <= main[-1] <= el:
                if max_stack[-1] < main[-1] < a_stack_second_el:
                    a_stack_second_el = main[-1]
                num_moves += move(main, a_stack)
                el = a_stack[-1]

            # Step 3
            # Put the smallest element(s) back
            for i in range(amount):
                num_moves += move(max_stack, a_stack)
        else: # Find a location in aux stack to put current element
            # Step 1
            # Move all elements into max stack as long as it will still
            # fulfill the Hanoi condition on max stack, AND
            # it should be greater than the smallest element in aux stack
            # So that we won't duplicate work, because in Step 2 we want
            # the main stack to contain the minimum element
            while len(main)>0 and a_stack[-1] < main[-1] <= max_stack[-1]:
                num_moves += move(main, max_stack)

            # Step 2
            # Pick the minimum between max stack and aux stack, move to main
            # This will essentially sort (in reverse) the elements into main
            # Don't move to main the element(s) found before Step 1, because
            # we want to move them to aux stack
            while True:
                if len(a_stack)>0 and a_stack[-1] < max_stack[-1]:
                    num_moves += move(a_stack, main)
                elif max_stack[-1] < el:
                    num_moves += move(max_stack, main)
                else:
                    break

            # Step 3
            # Move all elements in main into aux stack, as long as it
            # satisfies the Hanoi condition on aux stack
            while max_stack[-1] == el:
                num_moves += move(max_stack, a_stack)
            while len(main)>0 and main[-1] <= a_stack[-1]:
                if main[-1] < a_stack[-1] < a_stack_second_el:
                    a_stack_second_el = a_stack[-1]
                num_moves += move(main, a_stack)
        if DEBUG: print main, max_stack, a_stack
    # Now max stack contains largest element(s), aux stack the rest
    num_moves += push_to_main(max_stack, main)
    num_moves += move_to_main(a_stack, main, max_stack)
    return num_moves

if __name__ == '__main__':
    main()

```
> 3 votes

# Answer
# Java -- 2129090 2083142 moves on 55986 arrays

The ideone link.

The framework to ensure the algorithm is correct:

```
private final Deque<Integer> main = new ArrayDeque<Integer>();
private final Deque<Integer> help1 = new ArrayDeque<Integer>();
private final Deque<Integer> help2 = new ArrayDeque<Integer>();

private int taskCount = 0;
private int opCount = 0;

private void sort(List<Integer> input) {
    taskCount++;
    main.addAll(input);
    sortMain();
    verify();
    main.clear();
}

private void verify() {
    if (!help1.isEmpty()) {
        throw new IllegalStateException("non-empty help1\n" + state());
    }
    if (!help2.isEmpty()) {
        throw new IllegalStateException("non-empty help2\n" + state());
    }
    int last = 0;
    for (int i: main) {
        if (last > i) {
            throw new IllegalStateException("unsorted main: " + main);
        }
        last = i;
    }
}

private void done() {
    System.out.println();
    System.out.print(opCount + "/" + taskCount);
}

private void move(Deque<Integer> from, Deque<Integer> to) {
    if (from == to) throw new IllegalArgumentException("moving from/to " + from);
    Integer i = from.pop();
    if (to != main && !to.isEmpty() && i > to.peek()) {
        throw new IllegalStateException(
                from + " " + i + " -> " + to);
    }
    to.push(i);
    opCount++;
}

private String name(Deque<Integer> stack) {
    return stack == help1 ? "help1" :
           stack == help2 ? "help2" :
           "main";
}

private String state() {
    return "main:  " + main +
            "\nhelp1: " + help1 +
            "\nhelp2: " + help2;
}

```

The actual algorithm:

```
private void ensureMain(Deque<Integer> stack) {
    if (stack != main) {
        throw new IllegalArgumentException("Expected main, got " + name(stack) + "\n" + state());
    }
}

private void ensureHelp(Deque<Integer> stack) {
    if (stack == main) {
        throw new IllegalArgumentException("Expected help, got main\n" + state());
    }
}

private void ensureHelpers(Deque<Integer> stack1, Deque<Integer> stack2) {
    ensureHelp(stack1);
    ensureHelp(stack2);
}

private void sortMain() {
    int height = main.size();
    int topIndex = height;
    while (topIndex == height && height > 1) {
        topIndex = lastIndexOfLargest(height, main);
        height--;
    }
    if (topIndex == height) {
        // is already sorted
        return;
    }
    // split stack at largest element
    int part1Count = topIndex;
    int part2Count = height - topIndex;
    // move largest and first part to help 1
    moveFromMain(part1Count+1, help1, help2);
    // merge both parts to help 2, leaving largest on 1
    mergeToHelp(part2Count, main, part1Count, help1, help2);
    // move largest to main
    move(help1, main);
    // move remaining to main
    moveToMain(height, help2, help1);
}

/** Moves elements from main to helper, sorting them */
private void moveFromMain(int amount, Deque<Integer> target, Deque<Integer> help) {
    if (amount < 1) return;
    ensureHelpers(target, help);
    int topIndex = lastIndexOfLargest(amount, main);
    int part1Count = topIndex;
    int part2Count = amount - topIndex - 1;
    // move first part to help
    moveFromMain(part1Count, help, target);
    // move largest to target
    move(main, target);
    // merge both parts to target
    mergeToHelp(part2Count, main, part1Count, help, target);
}

/** Moves elements from helper to main, keeping them sorted */
private void moveToMain(int amount, Deque<Integer> source, Deque<Integer> help) {
    if (amount < 1) return;
    ensureHelpers(source, help);
    moveHelper(amount-1, source, help);
    move(source, main);
    moveToMain(amount-1, help, source);
}

/** Moves elements between helpers */
private void moveHelper(int amount, Deque<Integer> source, Deque<Integer> target) {
    pushToMain(amount, source);
    popFromMain(amount, target);
}

/** Merges top of main and helper to other helper */
private void mergeToHelp(int mainAmount, Deque<Integer> main, int helpAmount, Deque<Integer> help, Deque<Integer> target) {
    ensureMain(main);
    ensureHelpers(help, target);
    if (mainAmount < 0) mainAmount = 0;
    if (helpAmount < 0) helpAmount = 0;
    while (mainAmount > 0 || helpAmount > 0) {
        // while there is something to merge
        int largestMain = valueOfLargest(mainAmount, main);
        int largestHelp = valueOfLargest(helpAmount, help);
        if (largestMain > largestHelp) {
            // largest is in main
            int index = firstIndexOfLargest(mainAmount, main);
            if (index > 0) {
                // move excess to help:
                int mainTop = index;
                int helpTop = elementsSmallerThan(help, largestMain);
                if (helpTop > 0) {
                    // 1. move top of help to target
                    moveHelper(helpTop, help, target);
                    // 2. merge old top with excess from main
                    mergeToHelp(mainTop, main, helpTop, target, help);
                } else {
                    moveFromMain(mainTop, help, target);
                }
                mainAmount -= mainTop;
                helpAmount += mainTop;
            }
            move(main, target);
            mainAmount--;
        } else {
            // largest is at bottom of help
            int helpTop = helpAmount - 1; // largest is at bottom
            // move top to main
            pushToMain(helpTop, help);
            mainAmount += helpTop;
            // move largest to target
            move(help, target);
            helpAmount = 0;
        }
    }
}

private void pushToMain(int amount, Deque<Integer> from) {
    for (; amount > 0; amount--) move(from, main);
}

private void popFromMain(int amount, Deque<Integer> to) {
    for (; amount > 0; amount--) move(main, to);
}

private int firstIndexOfLargest(int height, Deque<Integer> stack) {
    if (height == 0) throw new IllegalArgumentException("height == 0");
    int topValue = 0;
    int topIndex = 0;
    int i = 0;
    for (Integer e: stack) {
        if (e > topValue) {
            topValue = e;
            topIndex = i;
        }
        if (++i == height) break;
    }
    return topIndex;
}

private int lastIndexOfLargest(int height, Deque<Integer> stack) {
    if (height == 0) throw new IllegalArgumentException("height == 0");
    int topValue = 0;
    int topIndex = 0;
    int i = 0;
    for (Integer e: stack) {
        if (e >= topValue) {
            topValue = e;
            topIndex = i;
        }
        if (++i == height) break;
    }
    return topIndex;
}

private int valueOfLargest(int height, Deque<Integer> stack) {
    int v = Integer.MIN_VALUE;
    for (Integer e: stack) {
        if (height-- == 0) break;
        if (e > v) v = e;
    }
    return v;
}

private int elementsSmallerThan(Deque<Integer> stack, int value) {
    int i = 0;
    for (Integer e: stack) {
        if (e >= value) return i;
        i++;
    }
    return i;
}

```

The testcase:

```
public static void main(String[] args) throws Exception {
    HanoiSort hanoi = new HanoiSort();
    int N = 6;
    for (int len = 1; len <= N; len++) {
        Integer[] input = new Integer[len];
        List<Integer> inputList = Arrays.asList(input);
        int max = N;
        for (int i = 1; i < len; i++) max *= N;
        for (int run = 0; run < max; run++) {
            int n = run;
            for (int i = 0; i < len; n /= N, i++) {
                input[i] = (n % N)+1;
            }
            try {
                hanoi.sort(inputList);
            } catch (Exception e) {
                System.out.println(inputList);
                e.printStackTrace(System.out);
                return;
            }
        }
    }
    hanoi.done();
}

```
> 1 votes

# Answer
**C/C++ Didn't measure moves** (pegs :p1, p2, p3) Don't know how to add C++ code that uses STL(formating issue). Loosing parts of code due to html tag formats in code.

1. Get n : count of top sorted elements in p1
2. Do a hanoi move of them (n) to p3 using p2(keeps the sorted property)
3. Move the next m elems (atleast 1) in reverse order from p1 to p2.
4. Merge move (n+m) data in p2 & p3 to p1.

```
     4.1 merge sort p2 & P3 (reverse) to p1
     4.2 move (n+m) to p3
     4.3 hanoi p3 to p1 using p2

```
5. Call hanoi sort recursively which will sort atleast n+m+1 elements now.
6. Stop when n = size of p1.

```

#include
#include
using namespace std;
/******************************************************************************
   Show the vector (Had to chance cout
*******************************************************************************/

void show(vector p, string msg)
{
   vector::iterator it;
   printf(" %s \n", msg.c_str());
   for(it = p.begin(); it  &fr, vector &inter, vector &to, int n) {
   int d1;
   if (n  &p1, vector &p2, vector &p3) {
   int d3, d2, d1;
   int count,n;
   bool d2_added;

   d2 = p2.back(); p2.pop_back();
   // data will be descending in p1
   d2_added = false;
   while (p3.size() > 0) {
      d3 = p3.back(); p3.pop_back();
      if (d2_added == false && d2  0) {
      d1 = p1.back();p1.pop_back();
      p3.push_back(d1);
      --count;
   }
   //Move back with hanoi from p3 to p1
   // use p2 as inter
   hanoi(p3, p2, p1, n);
}
/*******************************************************************************
   Gets the count of first sorted elements
*******************************************************************************/
int get_top_sorted_count(vector &p1) {
   vector::iterator it;
   int prev = 0;
   int n =1;

   for (it = --p1.end(); it >= p1.begin(); --it){
     if (it == --p1.end()) {
    prev = *it;
        continue;
     }
     if (*it  &p1, vector &p2, vector &p3) {
    int n, d1;
    n = get_top_sorted_count(p1);
    if (n == p1.size()) {
       return;
    }
    hanoi(p1, p2, p3, n);
    p2.push_back(p1.back());
    p1.pop_back();
    merge_move(p1, p2, p3);
    hanoi_sort(p1, p2, p3);
}
/*******************************************************************************
    Sorts baed on hanoi
*******************************************************************************/
int main (void)
{
  vector p1, p2, p3;
  p1.push_back(5);
  p1.push_back(4);
  p1.push_back(7);
  p1.push_back(3);
  p1.push_back(8);
  p1.push_back(2);
  show(p1, "...Bef Sort...");
  hanoi_sort(p1, p2, p3);
  show(p1, "...Aft Sort...");
}

```
> -1 votes

---
Tags: code-challenge, sorting, stack
---