title: May the 4th be with you!

text:
# Question
Title: May the 4th be with you!
In honor of Star Wars day, write a program to display the following text, scrolling like the Star Wars opening crawl:

```
It  is  a  period  of  civil war.  Rebel
spaceships,   striking  from   a  hidden
base,  have   won  their  first  victory
against the evil Galactic Empire.

During  the battle,  Rebel spies managed
to  steal  secret  plans to the Empire's
ultimate   weapon,  the  Death Star,  an
armored   space  station   with   enough
power to destroy an entire planet.

Pursued by the Empire's sinister agents,
Princess  Leia  races  home  aboard  her
starship,  custodian of the stolen plans
that  can save  her people  and  restore
freedom to the galaxy...

```

You may output an animated GIF or have your program display it. The output must show the following:

* The text must start from the bottom of the image/display
* It must scroll upwards until it reaches the top. It must take at least `30` seconds for a piece of text to reach the top. The animation must continue until all the text reaches the top.
* In this distance, the text must get smaller until it is less than `1/3` the size (length and font)
* The text must be slanted to follow this angle.
* The text must be left and right justified. The text given is already justified for monospaced fonts, however, you may remove the extra spaces (not newlines) and justify it yourself.
* The text must be yellow
* The background must be black

This video shows the opening crawl.

Good luck, and *May the fourth be with you*!

# Answer
# HTML, 762

```
<div><pre>It  is  a  period  of  civil war.  Rebel
spaceships,   striking  from   a  hidden
base,  have   won  their  first  victory
against   the   evil   Galactic  Empire.

During  the battle,  Rebel spies managed
to  steal  secret  plans to the Empire's
ultimate   weapon,  the  Death Star,  an
armored   space  station   with   enough
power   to  destroy  an  entire  planet.

Pursued by the Empire's sinister agents,
Princess  Leia  races  home  aboard  her
starship,  custodian of the stolen plans
that  can save  her people  and  restore
freedom to the galaxy...</pre></div><style>pre{transform:perspective(300px)rotateX(25deg);position:absolute;left:99px;color:yellow;animation:a 30s linear}@keyframes a{100%{font-size:0px}}body{background:black}</style>

```

Kind of choppy (read: **extremely** choppy :P).

Here's a JSFiddle (with `-webkit-` vendor prefixes added so it works in Chrome).
> 8 votes

# Answer
# HTML/CSS, 1047

I could golf this a lot more by deleting the `-webkit` prefixes etc., but this will do for the time being:

```
<html><head><style>body{font-family:sans-serif;background:#000;margin:0
auto;height:400px;width:800px;text-align:justify;position:relative;perspective:
150px;-webkit-perspective:150px;}div{font-size:63px;line-height:63px;color:#ee6;
position:absolute;-webkit-transform:rotateX(70deg);transform:rotateX(70deg);}p{
position:relative;-webkit-animation:s 90s linear forwards;animation:s 90s linear
forwards;}@-webkit-keyframes s{from{top:800px;}to{top:-2000px;}}@keyframes
s{from{top:800px;}to{top:-2000px;}}</style><body><div><p>It is a period of civil
war. Rebel spaceships, striking from a hidden base, have won their first victory
against the evil Galactic Empire.</p><p>During the battle, Rebel spies managed to
steal secret plans to the Empire's ultimate weapon, the DEATH STAR, an armored
space station with enough power to destroy an entire planet.</p><p>Pursued by
the Empire's sinister agents, Princess Leia races home aboard her starship,
custodian of the stolen plans that can save her people and restore freedom to
the galaxy...</p></div>

```

**Live demo**
> 36 votes

# Answer
# HTML+CSS+SVG 1614 1625

I wanted to be visually correct, too. SVG used for masking and animation. HTML+CSS used for transforms. I didn't check if the text gets to exactly 1/3 size.

Recommended viewing in Chrome due to `-webkit-` prefix. Requires CSS 3D transforms to work; you may need to open `chrome://flags` and pick 'Override software rendering list'.

Included in bytecount are newlines and blanks.

Update 1: Adding support for Firefox and other browsers that don't need prefixes. Added 11 bytes even after further cleanup. Cleanup was possible because browsers luckily interpret SVG using HTML-crunching parsers as opposed to XML-compilant parsers.

Live

```
<div id=a>
<div id=b>
<svg width=760 height=1000>
<g mask=url(#m)>
<g transform=translate(0,0)>
<animateTransform attributeName=transform type=translate dur=50 fill=freeze from=0,700 to=0,-450 />
<foreignObject width=760 height=800>
<div style=width:740; >
<p>It is a period of civil war. Rebel
spaceships, striking from a hidden
base, have won their first victory
against the evil Galactic Empire.</p>
<p>During the battle, Rebel spies managed
to steal secret plans to the Empire's
ultimate weapon, the DEATH STAR, an
armored space station with enough
power to destroy an entire planet.</p>
</div>
<p>Pursued by the Empire's sinister agents,
Princess Leia races home aboard her
starship, custodian of the stolen plans
that can save her people and restore
freedom to the galaxy...</p>
</foreignObject>
</g>
</g>
<defs>
<linearGradient id=g x1=0 y1=0% x2=0 y2=100%>
<stop offset=0% />
<stop offset=25% />
<stop offset=35% stop-color=#fff />
<stop offset=100% stop-color=#fff />
</linearGradient>
<mask id=m>
<rect width=100% height=100% fill=url(#g) />
</mask>
</defs>
</svg>
</div>
</div>
<style>
body {
margin: 0;
width: 100%; height: 100%;
perspective: 700px;
-webkit-perspective: 700px;
background: url(http://vucica.net/s.php);
}
#a {
position: absolute;
width: 100%;
height: 700px;
bottom: 0;
transform-style: preserve-3d;
}
#b {
margin: auto auto auto auto;
width: 760px; height: 100%;
font-family: Courier; font-weight: bold; text-align: justify; font-size: 24pt;
color: yellow;
overflow: hidden;
transform: rotateX(45deg);
-webkit-transform: rotateX(45deg);
}
svg {
position: absolute;
width: 760px;
height: 100%;
}

```
> 19 votes

# Answer
## PerlMagick, 661 program + 547 text file = 1208

Too late for the anniversary, but OP said 'animated GIF', so...

TL;DR: a link to animated GIF (5 Mb, 480\*240, 1360 frames) (there's a false start each time I try this link now - it's not in the file, maybe try to download it first. And some slight flickering... maybe I'll explain it later, - not a piece of cake, the whole IM and GIF idea ;) ).

With newlines and indentation for readability:

```
use Image::Magick;
$i=Image::Magick->new(
    depth=>8,
    page=>'480x440+20+0',
    background=>'#000',
    fill=>'#ff0',
    font=>'UbuntuMono-R.ttf',
    pointsize=>22
);
$i->Read('text:-');
$j=$i->Clone;
$i->Extent(y=>-440);
for(1..680){
    ($i->[2*$_]=$j->Clone)->Extent(y=>$_-440);
    ($i->[2*$_-1]=$i->[2*$_]->Clone)
        ->Composite(image=>$i->[2*$_-2],compose=>'Blend',blend=>50)
}
$i->Distort(method=>'Perspective','virtual-pixel'=>'Background',
    points=>[0,0,180,180,480,0,300,180,0,420,0,420,480,420,480,420]);
$i->Extent(geometry=>'480x240+0+200');
$g=Image::Magick->new(size=>'480x150');
$g->Read('gradient:#000-#fff');
$i->Composite(image=>$g,compose=>'Multiply');
$i->Set(delay=>10,loop=>0);
$i->Animate()

```

It reads text from STDIN, but geometry is hard-coded, so probably any other text would not be a good idea. It could be shorter, but I added fading to the text as it gets to the top, and, moving up by single pixel resulted in a choppy animation, so I did some interpolation. It eats 2.2 Gb of RAM and takes 2-3 minutes on a 8 y.o. desktop (and probably won't work for Windows folks), so here's how to get a GIF: replace (or add to) the last line (creates 200+ Mb file):

```
$i->Write('out.miff')

```

And then run

```
convert -size 8x1 gradient:black-yellow palette8.png
convert +dither out.miff -remap palette8.png out+.gif
convert +dither out+.gif -layers optimize out++.gif

```

Trade-offs between quality (palette size etc.) and final GIF size are obvious. Calling `$i->Remap` from PerlMagick directly doesn't work, there's probably a bug, it takes hours long as it (I think) tries `+remap` first. Actually, reasonable (only slightly bigger) GIF size can be achieved without global palette but using `$i->Quantize` which reduces each frame local palette to required size. Oh, and without any palette optimizations i.e. saving GIF from above script 'as is' produces about 9 Mb GIF file.
> 4 votes

---
Tags: code-golf, graphical-output, kolmogorov-complexity, animation
---


title: Sort an array only using recursion

text:
# Question
Title: Sort an array only using recursion
Your task is to write a **function** that sorts an array.

---

Your **function**:

* Cannot call other functions (excluding itself, of course);
* Must receive an array of integers as input, and it must return the ordered array. Feel free to add other parameters as input, if you need them.
* Cannot use **any** kind of loop (for, while...) except recursion;
* Cannot access the internet;
* Can be overloaded if you need it.

---

Code-Golf here. Shortest code wins, as usual.

Happy coding!

# Answer
## APL (36)

```
{⍵≡⍬:⍬⋄(∇z/m),p,∇m/⍨~z←(p←⊃⍵)≥m←1↓⍵}

```

It's quicksort:

* `⍵≡⍬`: if the list is equal to the empty list
* `:⍬`: then return the empty list
* : otherwise:
    + `m←1↓⍵`: `m` is the list minus its first element
    + `p←⊃⍵`: `p` (pivot) is the first element
    + `z←(p←⊃⍵)≥m`: `z` is a bitmask of those values of `m` that are smaller than `p`.
    + `∇m/⍨~z` select the inverse of `z` from `m` (= larger numbers) , and sort it recursively
    + `p,`: pivot
    + `∇z/m`: select `z` from `m` (= smaller or equal numbers) and sort it recursively
> 5 votes

# Answer
## GolfScript (42 41)

```
{.,2={[.(+].~>=}*.,2>{(\S+)\S\+(\S+}*}:S;

```

Note: this assumes that `bool{...}*` is acceptable as an `if` without `else`. (Technically it's a loop). Replacing it with `bool{...}{}if` would add 3 chars twice.

This is a pessimisation of an already bad sorting algorithm presented in an exercise of *Introduction to Algorithms*, by Cormen, Leiserson, and Rivest. From memory, their version is

```
sort(A, off, len):
    if (len == 2) special case.
    if (len > 2):
        third = floor(len / 3)
        sort(A, off, len - third)
        sort(A, off + third, len - third)
        sort(A, off, len - third)

```

But all that mucking around with thirds uses characters. I do

```
sort(A, off, len):
    if (len == 2) special case.
    if (len > 2):
        sort(A, off, len - 1)
        sort(A, off + 1, len - 1)
        sort(A, off, len - 1)

```
> 4 votes

# Answer
## Haskell - 51

Standard insertion sort in Haskell. I hoped I would beat golfscript for once but alas, I could not.

I could save two chars if I left out the \[\] from first line and require the user to pass an extra empty array as parameter, but since it makes no difference I opt not to do so.

Actually I'm not sure if foldr is allowed. It's a higher order function that sort of automates one family of recursion. If it's not drop a comment and I'll do my best to fix this.

```
s=foldr(%)[]
e%[]=[e]
e%(s:t)|e<s=e:s:t|e>=s=s:e%t

```
> 4 votes

# Answer
**C - 137 char (including whitespaces)**

```
int*s(int*a,z,x,c){if(c){if(a[c-1]>a[c]){int t=a[c];a[c]=a[c-1];a[c-1]=t;}if(c>=z-1)c=-1;s(a,z,x,c+1);}if(x<z&&!c)s(a,z,x+1,1);return a;}

```

expanded version

```
int* s(int *a,z,x,c)  // this give a warning because of not specified type, but default is int so it's ok
{
    if (c)
    {
        if (a[c-1] > a[c])
        {
            int t = a[c];
            a[c] = a[c-1];
            a[c-1] = t;
        }
        if (c >= z-1)
            c = -1;

        s(a, z, x, c+1);

    }

    if (x < z && !c)
        s(a, z, x+1, 1);

    return a;
}

```

If you want to test it add:

```
int anArray[10] = {10, 1, 123,121,34,12,43,65,86,34};
s(anArray, 10, 1, 1);
printArray(anArray);

void printArray(int *arr)
{
    for(int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
        printf("\n");
    }
    printf("\n");
}

```
> 4 votes

# Answer
## Python 3 and 2 - ~~129~~ 125 bytes

```
def s(a,i,m,o,l):
 if i<l:return s(a,i+1,[m,i][a[m]<a[i]],o,l)
 if l-o:a[o],a[m]=a[m],a[o];return s(a,o+1,-1,o+1,l)
 return a

```

This is called as `s(list,0,-1,0,list_length)`.

The `i<len(a)` part simply runs through the array, finding the index of the max value. Then, we swap the value at that index with the current index (which I decided to call offset (`o`)).

This works even for an empty list and a one element list.

Note:Since it wasn't specified, I sorted descending. If the order should be ascending, replace the `<` at `a[m]<a[i]` with `>`.
> 3 votes

# Answer
### GolfScript, 47 46 characters

```
{.,1>{.,3<{.~>{[~\]}*}{(\S(@[\]S~@+S+}if}*}:S;

```

The code became quite long in the end without using all those useful operators. You can try it online.

```
{
  .,1>{               # if length(array)>1
    .,3<{             # if length(array)<3
      .~>             #   copy array, expand and compare
      {               #   if two elements have wrong order
        [~\]          #     swap
      }*              #   end if
    }{                # else (recursive sort)
      (\S             #   remove first element, recursively sort rest of array
      (@              #   take first element and first element (smallest) of rest of array
      [\]S            #   sort those two
      ~               #   take smaller one
      @+S             #   concat other with rest of array and sort again
      +               #   join results
    }if               # end if
  }*
}:S;

```
> 1 votes

# Answer
## Ruby - 69 characters

```
f=->(a){a[1]?(b,c=a.shift,f.(a);b>c[0]?[c.shift]+f.([b]+c):[b]+c):a}

```

Explanation:

```
f=->(a){
  a[1]?                     # if array length is larger than 1
    (
      b,c=a.shift,f.(a);    # recurse on the tail of the array
      b>c[0]?               # compare the head with the first item in the sorted array
        [c.shift]+f.([b]+c) # bigger - sort the array with the original head and concat with its own head
        :[b]+c              # add the head back to the sorted array
     )
    :a                      # array with 1 item or less - returns itself
}

```
> 1 votes

# Answer
**Javascript - 147 characters**

```
function s(a,i,j,l){(!l)&&(i=0,j=1,l=a.length);if(i<l){(n=a[i],m=a[j],1)&&(m<n)&&(a[i]=m,a[j]=n);return (j<l)?s(a,i,j+1,l):s(a,i+1,i+2,l)}return a}

```

Expanded:

```
function s(a,i,j,l) {
  (!l) && (i=0,j=1,l=a.length)
  if(i<l) {
    if(j<l) {
      if(a[j] < a[i]) {
        var t = a[i];
        a[i] = a[j];
        a[j] = t;
      }
      return s(a,i,j+1,l);
    }
    return s(a,i+1,i+2,l);
  }
  return a;
}

```
> 1 votes

# Answer
# Python (78)

**Edit:**

```
def s(a,b,i):d=a[:1]>b[i:];b[i:i]=a[:d];return a and s(a[d:],b,[i+1,0][d])or b

```

Golfed into a one-liner by replacing `if` clause with Boolean `d` and actions that do nothing unless `d` is 1. Now sorts descending.

Also, used list slicing and comparisons to shorten the condition, taking advantage of the empty list being smaller than nonempty ones.

I'm still hoping for a shorter way to do `[i+1,0][d]`. One can do equal with `i+=1;i-i*d`. Operator precedence is annoying here. I'd like to do something like `(i+1)*!d`, where `!` is some higher-precedence way to complement `d`. Unfortunately, `1^d` is too low-precedence.

---

Old version: (108 chars)

```
def s(a,b,i):
 if not a:return b
 if b[i:]and a[0]>b[i]:i+=1
 else:b[i:i]=a[:1];a=a[1:];i=0
 return s(a,b,i)

```

Call this as `s(a,[],0)`, where `a` is the list to sort. In the recursion, `a` is the remaining list to sort and `b` is the part that's been sorted so far. Elements from `a` are pushed into `b`, which is maintained sorted. The index `i` tracks where we're looking to put the current element of `a`.

The line `if not a:return b` is horrendously wasteful. I'll try to golf it into something better when I get a chance.
> 1 votes

# Answer
# C, 114, characters

```
int*f(int*a,int s,int i){int*c=a+i,*d=c+1;return s>1?*c>*d&&(*c^=*d,*d^=*c,*c^=*d),i+2<s?f(a,s,i+1):f(a,s-1,0):a;}

```

ungolfed:

```
int*f(int*a,int s,int i){
    int*c=a+i,*d=c+1;
    return s>1
                ?   *c>*d
                        &&(*c^=*d,*d^=*c,*c^=*d), //xor-swap
                    i+2<s
                        ?f(a,s,i+1) // swap the biggest number to the end of the array
                        :f(a,s-1,0) // last element of array is the biggest & sorted
                :a;
}

```

**Explaination**
This solution uses a bubble-sort. The result of every iteration of the bubble sort is that the largest element is at the end of the array, so we don't need to sort that part anymore and reduce the size of the array after every iteration. The algorithm is finished if we get to sort an array of the length 1.

Instead of swapping using a temporary variable I'm using a xor-swap. This only works on integers.

**Further Golfing:**
I have to write `int` a lot and it wastes a lot of characters, but I can't remove these like seen in the other C solution by @LombaX, because GCC throws an error if I do.

An other thing I could do which may result in a shorter code size is using a `int*` parameter as output instead of the return variable. The memory for the `int*` output parameter could be provided by the user of the function. In this solution I wouldn't have to swap and there would probably be a better algorithm.
> 0 votes

# Answer
## C 142 bytes

Golfed

```
void s(int *a, int i,int j,int n)
{if((i+1)>=n)return;int t=0;if(a[i]>a[j]){t=a[i];a[i]=a[j];a[j]=t;}j++;
if((j+1)>=n){j=i+1;i++;}s(a,i,j,n);}

```

Ungolfed source: sorts in ascending order by swapping elements using i,j as indices.

```
void rec_sort(int *a, int i,int j,int n)
{
    if((i+1)>=n) return;
    int t=0;
    if(a[i]>a[j])
    {
        t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    j++;
    if((j+1)>=n)
    {
        j=i+1;
        i++;
    }
    rec_sort(a, i, j, n);
}

```
> 0 votes

# Answer
# Python 2: 116

A simple bubble sort implementation

```
def s(l,i,d):
 n=i+1
 if n==len(l):return l if d else s(l,0,1)
 if l[i]>l[n]:l[i:i+2]=l[n],l[i];d=0
 return s(l,n,d)

```
> 0 votes

---
Tags: code-golf, sorting
---


title: Duct tape can fix Mother's Day

text:
# Question
Title: Duct tape can fix Mother's Day
Based on the Duct tape can fix anything question, that was too broad, with very similar rules. Only this time the objective is very specific:

# The challenge

Your mission is to make a program that displays `hello mom` -- without ever writing a single line of code.

You can only use code which is already written for you, both in questions and answers from StackOverflow. All you can do is duct tape it all together the best you can. And of course, it's very important that we provide appropriate attribution so that we don't get our rights terminated.

---

# Rules

1. You must include links to the questions/answers you used in your answer.
2. You *may not* modify the code you find, with the following exceptions:

a. You may rename variables, functions, and methods. (This doesn't mean you can change a method *invocation*, by changing, say `scanner.nextInt()` to `scanner.nextLine()` and claiming that you're changing a method name. The change must be in the definition or reference to the same entity.). *The solution should still work if variables, functions or methods would be renamed again, so renaming code to contain `hello mom` as a variable name does not count.*

b. You may adjust indentation appropriately.

c. You can assume that the proper modules are loaded for the code snippets to work. (e.g., `import` statements for Java and Python, `using` statements for C# and C++, and their equivalents in all languages) If the code snippet includes the `import`s for you, you can move them to the top of the code.

d. If the language requires the code to be in some kind of method body to execute (e.g., `public static void main(String[] args)` for Java, `static int Main(string[] args)` for C#, and so on), you can wrap your code in the appropriate method. But the *contents* of that main method must remain unmodified.
3. You must supply an explicit list of any variable/method/function/class rename-ings performed.
4. You can't take snippets of snippets (meaning if you take a code block from a post, you take the whole thing)
5. Provide a brief description of what the code does for people who aren't intimate with the language you're using.
6. You must use snippets posted before this challenge was started.
7. Popularity contest, so the most upvotes wins!

# Deadline

I will accept the the submission that has the most votes around the end of mothersday (midnight of the UTC-11 timezone), but later submissions can still get votes.

# Answer
# Brainfuck

Oh god why did I do this to myself?

It is actually possible to find each BF symbol by itself as a code snippet in some answer somewhere. The interesting bit was piecing together bits of other people's code, each representing a block of BF instructions. Unfortunately there are basically no unmatched `[` and `]` symbols out there, so I had to cheat a bit for those, and I had to get an awful lot of mileage out of a funky Haskell snippet which had a bunch of pluses in it. There are probably others out there. Beyond that, here's some Frankensteined code:

```
byte x = 1;
byte y = 2;
byte z = x + y;   // ERROR: Cannot implicitly convert type 'int' to 'byte'
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
[
int a = (b > 10) ? some_value
                 : another_value;
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
int a = (b > 10) ? c : d;
byte x = 1;
byte y = 2;
byte z = x + y;   // ERROR: Cannot implicitly convert type 'int' to 'byte'
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
?"<<-"
]
exec >{space}> (command)
byte z = (int) x + (int) y;
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
find . -type f -print -exec cat {} \;
git reset .
byte x = 1;
byte y = 2;
byte z = x + y;   // ERROR: Cannot implicitly convert type 'int' to 'byte'
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
System.out.print("B");
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
fatal: Failed to resolve 'HEAD' as a valid ref.
while read p; do
echo $p
done < $filename
static HMODULE hMod = NULL;
  static bool once = false;
  if (!once++)
    hMod = LoadLibrary("xxx");
 if (originalValue.length > size) {
static HMODULE hMod = NULL;
  static bool once = true;
  if (once--)
    hMod = LoadLibrary("xxx");
$ cd /usr/local/wherever
$ grep timmy accounts.txt
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}
ls -ld $(find .)
git commit --amend -m "New commit message"
wget -q -O - $line
git rebase --interactive $parent_of_flawed_commit
find . -type f -user 'user1' -maxdepth 1

```

And, since my mother is British, the output is quite simply `hello mum`

# Bibliography:

https://stackoverflow.com/questions/17845014/what-does-the-regex-mean

`[` and `]`, with apologies

https://stackoverflow.com/a/21460161/2581168

```
find . -type f -print -exec cat {} \;

```

https://stackoverflow.com/questions/6161328/what-exactly-does-this-do-exec-command

```
exec >{space}> (command)

```

https://stackoverflow.com/questions/20130538/what-is-in-haskell

```
addop = do {symb "+"; return Op Add}  +++ do {symb "-"; return Op Sub}

```

https://stackoverflow.com/questions/21947452/why-is-printing-b-dramatically-slower-than-printing

```
System.out.print("B");

```

https://stackoverflow.com/questions/941584/byte-byte-int-why

```
byte x = 1;
byte y = 2;
byte z = x + y;   // ERROR: Cannot implicitly convert type 'int' to 'byte'

```

https://stackoverflow.com/a/160295/2581168

```
int a = (b > 10) ? c : d;

```

And

```
int a = (b > 10) ? some_value
                 : another_value;

```

https://stackoverflow.com/questions/13273002/what-does-mean-in-r

```
?"<<-"

```

https://stackoverflow.com/questions/3450420/bool-operator-and

```
static HMODULE hMod = NULL;
static bool once = false;
if (!once++)
    hMod = LoadLibrary("xxx");

```

And

```
static HMODULE hMod = NULL;
static bool once = false;
if (!once--)
    hMod = LoadLibrary("xxx");

```

https://stackoverflow.com/questions/22776085/in-which-case-will-size-originalvalue-length-in-string-constructor-string

```
if (originalValue.length > size) {

```

https://stackoverflow.com/questions/3797795/does-mean-stdout-in-bash

```
wget -q -O - $line

```

https://stackoverflow.com/questions/179123/how-do-i-edit-an-incorrect-commit-message-in-git/179147#179147

```
git commit --amend -m "New commit message"

```

And

```
git rebase --interactive $parent_of_flawed_commit

```

https://stackoverflow.com/questions/14763413/grep-ls-output-across-tabs/14763499#14763499

```
find . -type f -user 'user1' -maxdepth 1

```

https://stackoverflow.com/questions/945288/saving-current-directory-to-bash-history

```
$ cd /usr/local/wherever
$ grep timmy accounts.txt

```

https://stackoverflow.com/questions/348170/undo-git-add-before-commit/682343#682343

```
fatal: Failed to resolve 'HEAD' as a valid ref.

```
> 63 votes

# Answer
# Java

Start with these:

https://stackoverflow.com/a/19509316/1768232

```
String myStr = "hello";
String myStr1 = "hello";

```

https://stackoverflow.com/a/8341513/1768232

```
String[] history = new String[] { "hey", "you", "Mom" };

```

https://stackoverflow.com/a/23300004/1768232

```
String editednames = titleCase(name);

```

https://stackoverflow.com/a/20698093/1768232

```
myString = myString.toLowerCase();

```

https://stackoverflow.com/a/19393222/1768232

```
System.out.println(Name + " " + Income);

```

https://stackoverflow.com/a/1181979/1768232

```
public static <T> T last(T[] array) {
   return array[array.length - 1];
}

```

Add the required `class` and `public static void main(String[] args){ }` as allowed in Rule #2d (not around the static method), and change some variable / method names in exactly 3 of 6 snippets:

* Change `name` -\> `history` in the third snippet
* Change `editednames` -\> `myString` in the third snippet
* Change `Name` -\> `myStr` in the fifth snippet
* Change `Income` -\> `myString` in the fifth snippet
* Change `last` -\> `titleCase` in the sixth snippet

Resulting program:

```
public class DuctTape {
  public static void main(String[] args) {
    // https://stackoverflow.com/a/19509316/1768232
    String myStr = "hello";
    String myStr1 = "hello";

    // https://stackoverflow.com/a/8341513/1768232
    String[] history = new String[] { "hey", "you", "Mom" };

    // https://stackoverflow.com/a/23300004/1768232
    String myString = titleCase(history);

    // https://stackoverflow.com/a/20698093/1768232
    myString = myString.toLowerCase();

    // https://stackoverflow.com/a/19393222/1768232
    System.out.println(myStr + " " + myString);
  }

  // https://stackoverflow.com/a/1181979/1768232
  public static <T> T titleCase(T[] array) {
    return array[array.length - 1];
  }
}

```

Output:

```
hello mom

```
> 34 votes

# Answer
# C#

Possibly crazy, roundabout, and convoluted way to get to the (exact) result - with only variable renames and without any literal "mom" in any of the code.

Reading the "if you take a code block from a post, you take the whole thing" rule very literally probably didn't help - but made it more fun.

```
using System;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Text.RegularExpressions;

public class Program
{
    void Main()
    {
        // Step 1
        var n = 3;
        var helloAndGoodbye = "12345678900"
                    .Select((c, i) => new { letter = c, group = i / n })
                    .GroupBy(l => l.group, l => l.letter)
                    .Select(g => string.Join("", g))
                    .ToList();

        // Step 2
        string place = "world";
        string greet = String.Format("Hello {0}!", place);

        // Step 3
        byte[] b1 = System.Text.Encoding.UTF8.GetBytes (greet);
        byte[] b2 = System.Text.Encoding.ASCII.GetBytes (greet);

        // Step 4
        string encryptionKey = "test";
        var md5 = MD5.Create();
        var keyBytes = Encoding.UTF8.GetBytes(encryptionKey);
        byte[] encryptionKeyBytes = md5.ComputeHash(keyBytes);

        // Step 5
        string strName = md5.GetType().Name;
        if(strName == "Person")
        {
            //My Code
        }

        // Step 6
        string HashAlgorithm = new string(strName.Take(n).ToArray());

        // Step 7
        int previousYear = DateTime.Now.AddYears(-1).Year;

        // Step 8
        string myString = previousYear.ToString();

        // Step 9
        string totallyRandomString = new string(myString.Take(n).ToArray());

        // Step 10
        int myInt = System.Convert.ToInt32(totallyRandomString);

        // Step 11
        int x = myInt << 1 + 1;

        // Step 12
        PasswordDeriveBytes DerivedPassword =
                    new PasswordDeriveBytes(place, b1, HashAlgorithm, x);
        byte[] KeyBytes = DerivedPassword.GetBytes(32);

        // Step 13
        string base64 = Convert.ToBase64String(KeyBytes);
        byte[] bytes = Convert.FromBase64String(base64);

        // Step 14
        var split = base64.Split('/');
        var last = split[split.Length -1];
        var prev = split[split.Length -2];

        // Step 15
        string truncatedToNLength = new string(last.Take(n).ToArray());

        // Step 16
        Regex rgx = new Regex("[^a-zA-Z0-9 -]");
        greet = rgx.Replace(greet, "");

        // Step 17
        var newString = greet.Replace(place.ToString(), truncatedToNLength);

        // Step 18
        var searchStr = newString.ToLower();
            searchStr = searchStr.Trim();

        // Step 19
        Console.WriteLine(searchStr);
    }
}

```

### .NET Fiddle

http://dotnetfiddle.net/PbjhPn

http://dotnetfiddle.net/bg20wb (with redundant lines in code blocks removed)

### Short explanation

Basically, we get "Hello world!" from a simple string format. Now we need "mom" to replace it. For that, we use the Base64 encoded result of running 804 iterations of PBKDF1 using MD5 with "world" as password and "Hello world!" as salt. That yields a string "ciSf5cCls1l/**MoM**...". We extract that "MoM" and use it as a replacement for "world". Then we clean up the string.

How do we get to 804? The previous year clipped to three characters (= "201"), and then multiplied by 4.

### Long explanation and attributions

**1:** We start with a bit of rule-following overkill. The integer 3 is a very very important constant in this program. Here we assign that integer to `n`. We must include the entire block from the source. It may be redundant, but it will compile just fine, as long as we rename the `split` variable that we'll be needing later. Source

Replaced variable names:

```
split              > helloAndGoodbye

```

**2:** Set up starting string ("Hello world!"). Source

This is a very personal message to our mom. So we obviously need some cryptography to deal with those NSA types. For that, we'll need some parameters, which we prepare now.

**3:** Convert `greet` ("Hello world!") to byte array for salting. Source

```
myString           > greet

```

**4:** Although we're using cryptography, we don't actually need to instantiate the MD5 class. We do, however, need the string "MD5" assigned for one of our parameters to be used further down - and that's not easy to find in usable code. So we'll take another... "shortcut"... Once again, entire code block included as per rules, although we only need the second line. Source

**5:** Now we need the name of the type of the `md5` variable (`MD5CryptoServiceProvider`). The `if` is yet another redundancy. Source

```
entity             > md5

```

**6:** Get the first 3 (ooh, there's our constant!) characters of the type name. Source

```
s                  > strName
truncatedToNLength > HashAlgorithm

```

**7:** Code-trolling: Using `DateTime.Now` would mean this would only work until 2019. To make it a bit more future proof, we use the previous year. Then it will work until 2020 ;-)Source

**8:** Convert our `previousYear` to string. Source

```
myInt              > previousYear

```

**9:** Hey, code reuse! ;-) Get the first 3 (our constant!) characters of our year. Source

```
s                  > myString
truncatedToNLength > totallyRandomString

```

**10:** Aaaaaaaand... convert the result back to integer. Source

```
myString           > totallyRandomString

```

**11:** Eric Lippert makes every answer better. Multiply by 4 in a roundabout way. Source

```
y                  > myInt

```

**12:** Send `place` (password) and `greet` (salt) through PBKDF1 using MD5 with `x` (which is now `201*4 = 804`) iterations. Source

```
Password           > place
SaltValueBytes     > b1
PasswordIterations > x

```

**13:** Jon Skeet also makes every answer better. Convert our derived password to base 64. We throw out the `bytes` array. Source

```
bytes (first occurrence) > KeyBytes

```

**14:** What a crazy random happenstance! We now have a `base64` with "MoM" in it. Conveniently, right before "MoM" is a single '/'. So split the string with that character as delimiter: Source

```
filePath          > base64

```

**15:** Hey, our favorite piece of code reuse tape! Get the first 3 (constant!) letters of `last`. Source

```
s                 > last

```

**16:** Remove "!". Source

```
str               > greet

```

**17:** MoM is our world - so make the string reflect that (replace "world" with "MoM"). Source

```
someTestString   > greet
someID           > place
sessionID        > truncatedToNLength

```

**18:** Finally, convert to lower case. Trim for good measure (or possibly because it's part of the duct tape block). Source

```
wordToSearchReplacemntsFor > newString

```

**19:** Output to console. Source

```
_surface         > searchStr

```

### A bit of "bonus material"/commentary

* At first I tried every combination of built-in cryptographic hashes (each combined with HMAC) and inputs ("world", "Hello world!", "Hello world", "hello world" etc.) to see if something would miraculously give a usable output to derive "mom" from - before taking the easy route of just looking for a number of iterations of PDKDB1 (or 2) that would be useful.
* Wasn't quite happy with the use of the year as input for the 201\*4 = 804 iterations. At first I tried to find some useful code for `HttpStatusCode.Created` (201) to use as input - with a "troll excuse" along the lines of "we've created our 'Hello world!' string, so a good practice would be to use a 'Created' status code" here. Unfortunately, I never found a usage of the `HttpStatusCode` enumeration that didn't introduce a dependency on most of the ASP.NET WebAPI framework.
* The start of the code (the "Hello world!" string format) was never looked at again after I first added it. If I had, yeah, I might have realized that the assignment of `place` was actually in a different block in the source - so I could have simply assigned my derived "mom" to `place` rather than using "world" and later replacing it. Ah well.
> 28 votes

# Answer
# Befunge 98

My code:

```
var abc = function(){};
display: table-*
display: table-*
display: table-*
display: table-*
display: table-*
display: table-*
display: table-*
display: table-*
+
+
+
+
+
+
+
, new {area = ""}
byte z = x + y;
byte z = x + y;
byte z = x + y;
byte z = x + y;
byte z = x + y;
byte z = x + y;
byte z = x + y;
byte z = x + y;
display: table-*
+
+
+
+
+
+
+
+
, new {area = ""}
"1,23,4"
  String[] temp = data.split("\\s+\\^,?\"'\\|+");
List<Set<Integer>> foo;
"1,23,4"
+
: base(name)
: base(name)
, new {area = ""}
, new {area = ""}
10001.10010110011
10001.10010110011
10001.10010110011
+
+
+
, new {area = ""}
"1,23,4"
  String[] temp = data.split("\\s+\\^,?\"'\\|+");
"1,23,4"
, new {area = ""}
"1,23,4"
[5326, 4223, 1204]
Runnable prs = new Runnable() {
    public void run() {
        Document doc = null;
        try {
            doc = Jsoup.connect("http://play.radio.com/").get();

        } catch (IOException e) {

            e.printStackTrace();
        }
        parser.postDelayed(prs, 10000);
    }
};
"1,23,4"
$selector.append("somestuff");
$selector.append("somestuff");
-new Date().getTimezoneOffset()/60;
: base(name)
10001.10010110011
10001.10010110011
10001.10010110011
+
+
+
 [0000] push        ebp
 [0001] mov         ebp,esp
 [0003] push        edi
 [0004] push        esi
 [0005] push        ebx
 [0006] sub         esp,1Ch
 [0009] xor         eax,eax
 [000b] mov         dword ptr [ebp-20h],eax
 [000e] mov         dword ptr [ebp-1Ch],eax
 [0011] mov         dword ptr [ebp-18h],eax
 [0014] mov         dword ptr [ebp-14h],eax
 [0017] xor         eax,eax
 [0019] mov         dword ptr [ebp-18h],eax
*[001c] mov         esi,1
 [0021] xor         edi,edi
 [0023] mov         dword ptr [ebp-28h],1
 [002a] mov         dword ptr [ebp-24h],0
 [0031] inc         ecx
 [0032] mov         ebx,2
 [0037] cmp         ecx,2
 [003a] jle         00000024
 [003c] mov         eax,esi
 [003e] mov         edx,edi
 [0040] mov         esi,dword ptr [ebp-28h]
 [0043] mov         edi,dword ptr [ebp-24h]
 [0046] add         eax,dword ptr [ebp-28h]
 [0049] adc         edx,dword ptr [ebp-24h]
 [004c] mov         dword ptr [ebp-28h],eax
 [004f] mov         dword ptr [ebp-24h],edx
 [0052] inc         ebx
 [0053] cmp         ebx,ecx
 [0055] jl          FFFFFFE7
 [0057] jmp         00000007
 [0059] call        64571ACB
 [005e] mov         eax,dword ptr [ebp-28h]
 [0061] mov         edx,dword ptr [ebp-24h]
 [0064] lea         esp,[ebp-0Ch]
 [0067] pop         ebx
 [0068] pop         esi
 [0069] pop         edi
 [006a] pop         ebp
 [006b] ret
10001.10010110011
+
: base(name)
, new {area = ""}
"1,23,4"
List<Set<Integer>> foo;

"1,23,4"
+
10001.10010110011
10001.10010110011
10001.10010110011
+
+
+
, new {area = ""}
, new {area = ""}
def logme(func):
    def wrapped(*args):
        for arg in args: print str(arg)
        func(*args)
    return wrapped

@logme
def my_func(*args):
    res = 1
    for arg in args :
        print "Multiplying %s by %s" % (arg, res)
        res*=arg
    print res
    return res

```

This works because the first `v` (in the first line) sends the IP downward. So we are basically executing this program:

```
dddddddd+++++++,bbbbbbbbd++++++++," L"+::,,111+++," ","[R           }"$$-:111+++             *                            1+:,"L "+111+++,,d     @

```

Which does this:

* `dddddddd+++++++,` pushes `104` and prints
* `bbbbbbbbd++++++++,` pushes `101` and prints
* `" L"+,` pushes `32` and the ascii value of `L`, then adds them, duplicates twice, and prints twice
* To the one that was duplicated, `111+++,` adds 3 and prints
* `" ",` prints a space. `"[R }"$$-:111+++` pushes a `9` and duplicates it, then adds 3 to the top value
* `*` multiplies the top two values
* `1+:,` increments that number, duplicates, and prints
* `"L "+111+++,` prints `o`. `,` prints the `m` from earlier, and `d @` pushes `13` (which does nothing) and ends the program.
> 24 votes

# Answer
# Java

```
import java.util.*;

public class HelloMom {

     public static void main(String[] args) {
         Hashtable<String, String> ht = new Hashtable<String, String>();

        ht.put("Answer", "42");
        ht.put("Hello", "World");    // First value association for "Hello" key.
        ht.put("Hello", "Mom");      // Second value association for "Hello" key.

        for (Map.Entry<String, String> e : ht.entrySet()) {
          System.out.println(e);
        }
    }
}

```

# Output

```
Answer=42
Hello=Mom

```

There is a pesky = in there, but this is the best I could do

https://stackoverflow.com/a/1050075/573421
> 14 votes

# Answer
# C

Most of this code comes from an answer to Find the beginning of the first word that is a palindrom \[sic\] posted by BLUEPIXY, which outputs the word `mom`. At lines 21 and 22, the `hello` is printed by a code snippet at the end of an answer to printf(“%%%s”,“hello”) by user142019 (who fortunately added a semicolon at the end), and the space between the words comes from an answer to How to print space with padding in c by M Oehm.

### Output:

```
%hello        mom

```

I wasn't able to eliminate the extra spaces or the percent character, unfortunately :(

### Source code:

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

int isPalindrome(const char *str){
    const char *front, *back;
    front=str;
    back =str + strlen(str)-1;
    for(;front<back;++front,--back){
        while(!isalpha(*front))++front;//isalnum?
        while(!isalpha(*back))--back;
        if(front > back || tolower(*front)!=tolower(*back))
            return 0;
    }
    return 1;
}

int main(){
    const char *data="Hello mom and dad, how is it going?";
    char *p, *src;
    printf("%%%s", "hello");
    printf("        ");
    p=src=strdup(data);
    for(;NULL!=(p=strtok(p, " \t\n,.!?"));p=NULL){
        if(isPalindrome(p)){
            printf("%s\n", p);
            break;
        }
    }
    free(src);
    return 0;
}

```
> 11 votes

# Answer
# Java

```
import java.io.ByteArrayOutputStream;
import java.io.FileDescriptor;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Random;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author LH
 */
public class Kopierpaste
{

    //https://stackoverflow.com/questions/15182496/why-does-this-code-using-random-strings-print-hello-world
    //randomizer code for the first String
    public static String randomString(int i)
    {
        Random ran = new Random(i);
        StringBuilder sb = new StringBuilder();
        for (int n = 0;; n++)
        {
            int k = ran.nextInt(27);
            if (k == 0)
            {
                break;
            }

            sb.append((char) ('`' + k));
        }

        return sb.toString();
    }

    public static void main(String[] nope)
    {
        //catching a System.out() based code snippet
        //https://stackoverflow.com/questions/4183408/redirect-stdout-to-a-string-in-java
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        System.setOut(new PrintStream(baos));
        //same as randomizer
        //getting hello, world inside a ByteArray
        System.out.println(randomString(-229985452) + " " + randomString(-147909649));

        //undo the redirecct of System.out()
        //https://stackoverflow.com/questions/4183408/redirect-stdout-to-a-string-in-java && https://stackoverflow.com/a/14716148/1405227
        System.setOut(new PrintStream(new FileOutputStream(FileDescriptor.out)));

        //stringify the out of first part
        //https://stackoverflow.com/questions/4183408/redirect-stdout-to-a-string-in-java
        String text = baos.toString();

        //getting rid of the world part
        //https://stackoverflow.com/a/17008136/1405227
        String firstWord = text.substring(0, text.indexOf(' '));

        //needing the word Mom
        //https://stackoverflow.com/a/8341513/1405227
        //history -> a
        String[] a = new String[]
        {
            "hey", "you", "Mom"
        };

        //stitching the array together in a certain fashion ([elem1, elem2, elem3]
        //https://stackoverflow.com/a/2822736/1405227
        //myarray->a
        String b = Arrays.toString(a);

        //getting rid of the ,s
        //https://stackoverflow.com/a/7552284/1405227 stripping annoying bullcrap out
        //result ->c
        //yourString ->b
        String c = b.replaceAll("[-+.^:,]", "");

        //getting the Mom] part
        //https://stackoverflow.com/a/15317037/1405227
        //sentence -> c
        String lastToken = c.replaceAll(".* ", "");

        //getting rid of more crap
        //https://stackoverflow.com/a/18599016/1405227
        //message -> lastToken
        lastToken = lastToken.replaceAll("\\W", "");

        //finally out
        //https://stackoverflow.com/a/19393222/1405227
        //name -> firstWord
        //income -> lastToken
        System.out.println(firstWord + " " + lastToken);
    }
}

```

Documentation and source links are in the comments ( starting with // )

clean list of sources used
> 7 votes

---
Tags: popularity-contest, restricted-source, duct-tape-coding
---


# Question
Title: Ordering an integer array - Lowest to Highest - No Tools Challenge
**Here's the challenge:**

Order an Array from the Lowest to the Highest digit from a number, which is conveniently represented in an array. The trick here is that you cannot use any array methods, nor other sorts of loopholes. You have to stick to the basics (Arrays, Mathematical Operators /not Math Class/, no recursion. You can use any variable type of your chosing (eg: String, int), and evidently repetitive cicles, you can't however use "advanced" expressions, such as ArrayList or ParseInt for Java)

For an user input of `2014`, the output should be `0124` Yes, the 0 must be represented

**Scoring Method**

Simply a codegolf challenge, shortest code wins.

**Origin of the challenge:**

I've been reading quite a bit of codegolf for a while, and decided to create a challenge based on an issue that I had with java to order the digits of a number. I did manage to get a solution, but I wasn't quite pleased with it (it took a significant ammount of bytes which I wanted to avoid), I am interested in creative, short awnsers to counter my own =)

# Answer
In Racket, without explicit recursion :-P

```
(define Y (lambda (f) ((lambda (x) (x x)) (lambda (x) (lambda (y) ((f (x x)) y))))))
(define a (Y (lambda (f) (lambda (c) (cond ((null? c) c)
                                           ((null? (cdr c)) c)
                                           ((> (car c) (cadr c))
                                            (f (cons (cadr c) (cons (car c) (cddr c)))))
                                           (#t (cons (car c) (f (cdr c)))))))))
(define b (Y (lambda (f) (lambda (c) (let ((s (a c))) (if (equal? s c) c (f s)))))))

```

Call:

```
(b '(2 0 1 4))

```

where

* `Y` is the Y-Combinator
* `a` is one iteration of Bubble Sort
* `b` is the bubble sort algorithm
> 1 votes

---
Tags: code-golf
---


# Question
Title: Find the next subpermutation of base-64 digits
Permutations of a set have a natural order called lexicographic order in which two permutations are compared by comparing the first position at which they differ. For the purposes of this question we're working with base 64 and the order of the digits is

```
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

```

Note that this is not the same order as their ASCII values.

This ordering can be extended naturally to handle subpermutations of a given length.

### Task

Write a program, function or named verb which takes as input (via stdin in the case of a program or as an argument otherwise) a 12-character subpermutation of the base-64 alphabet given above, and which produces (respectively to stdout or as the return value) the lexicographically next 12-character subpermutation. If working with typed input you may use strings or character arrays holding the ASCII values of the digits listed above.

Your solution should be relatively efficient; and in particular, it is **forbidden** to loop through base-64 numbers testing them until you find one which doesn't repeat any digits.

It is only required that your program handle 12-character subpermutations, but you do not need to verify that the input is 12 characters in length; if it handles other lengths too you may wish to mention that in your answer.

If the input is the lexicographically greatest subpermutation, the output should wrap round to the lexicographically smallest subpermutation.

### Test cases

```
Input           Output
ABCDEFGHIJKL    ABCDEFGHIJKM
ABCDEFGHIJK+    ABCDEFGHIJK/
ABCDEFGHIJK/    ABCDEFGHIJLK
ABCDEFGHIJLK    ABCDEFGHIJLM
ABCD/9876542    ABCD/9876543
ABCD/9876543    ABCD/987654+
ABCD/987654+    ABCD/98765+E
ABCD/98765+E    ABCD/98765+F
ABCDEF+/9875    ABCDEF+/9876
ABCDEF+/9876    ABCDEF/GHIJK
ABCDEF/GHIJK    ABCDEF/GHIJL
ABCDEF/GHIJL    ABCDEF/GHIJM
ABCDEFG+/987    ABCDEFG/HIJK
A+/987654321    A/BCDEFGHIJK
/+9876543210    ABCDEFGHIJKL

```

# Answer
### GolfScript, 115 characters

```
:I,,0\{26,{65+.32+}%$10,{`}%'+/'++:A,1$-@*\)I<)A@-?+}/1I,,{A,\-*}/\)1$%\I,,{A,\-/\.2$%\2$/@\}%*>A\{1$=\[1$]-\}%\0<+

```

It passes all the test cases and works also for subpermutations of size other than 12 and for full permutations as well.

Online tester

*Annotated Code:*

```
:I                        # save input to variable I

### get the numerical index of the (sub)permutation
,,0\                      # push 0 (accumulator) and [0 .. <Length I>-1]
{                         # loop over

  ### construct the alphabet A
  26,{65+.32+}%$          # A-Z and a-z
  10,{`}%                 # 0-9
  '+/'++                  # append '+/'
  :A                      # save to variable A

  ,1$-                    # length of alphabet (i.e. 64) minus loop variable
                          # i.e. 64 -> 63 -> 62 -> 61 -> ...
                          # (this is the number of possible characters at
                          # the current position)
  @*                      # multiply the accumulator by this value
  \)I<                    # get anything from the input up to the current character
  )                       # extract the current character of input
  A@-                     # remove anything from the alphabet which was in the rest,
                          # i.e. the already processed chars cannot be used any more
  ?                       # find the index of the current input character
  +                       # add to the accumulator
}/

### calculate the total number of (sub)permutations
1                         # push 1 (accumulator)
I,,{                      # loop for i = 0 .. <Length I>-1
  A,\-                    # length of alphabet minus loop variable
  *                       # multiply to accumulator
}/

### at this point the stack is <Index of input (sub)permutation>
###   <Total number of (sub)permutations>
\)                        # increment the index (i.e. next (sub)permutation)
1$%                       # warp around for the last possible (sub)permutation
\                         # swap back order

### backwards transformation into the (sub)permutation space
I,,{                      # map for each index [0 .. <Length I>-1]
  A,\-/                   # divide the weight factor by length of alphabet minus
                          # loop variable
  \.2$%                   # take index % new weight factor
  \2$/                    # and index / new weight factor (result for the map operation)
  @\                      # re-order stack
}%
*>                        # get rid of 0 1 on the stack

### back to the alphabet
A\                        # push the full alphabet under the index array
{                         # map on the index array
  1$=                     # take the i-th element of the alphabet
  \[1$]-\                 # and reduce the alphabet by this characters
}%

\0<                       # transforms the remaining alphabet into an empty string
+                         # make string from array by joining with the empty string

```
> 2 votes

# Answer
### GolfScript, 77 70 characters

Another more direct approach in GolfScript which happens to work in the general case also.

```
:I{)26,{65+.32+}%$10,{`}%'+/'++:^2$-:S\?).S,<{S[=]+0}*1$!!*}do^1$-+I,<

```

Also this solution can be tested online.
> 1 votes

# Answer
# Ruby: Whittled down to 658 Characters

```
class B;def initialize(g)@l=12;@b=(("A".."Z").to_a+("a".."z").to_a+("0".."9").to_a+["+","/"]
).each_with_index.map{|x,i|{x=>i}}.inject(:update);@g=g;@i=@b.invert;@m=@l.times.map{|i|
@i[@b.length-i-1]}.join;end;def n;c(@g)?@g:r;end;def c(s);@b[s[-1]]==@b.length-1?(return false
):s==@m?r: f(s,s[-1]) ?s[-1]=f(s,s[-1]):f(s,s[-2])?r: (s[-1]=f(s);f(s,s[-2])?s[-2]=f(s,s[-2]):r)
true;end;def h(s)v=s.split("").map{|x|@b[x]};v.index(v.compact.max)end;def r;@g==@m?@g=@l.times.map{
|j| @i[j]}.join: (v=@g[0..h(@g)-1];c(v);u=@g[h(@g)..-1].length;u.times{v+=f(v)};@g=v);end
def f(s,a=@i[0])(@b[a]..@b.length-1).each{|p|unless !!s[@i[p]];return @i[p]end};false;end;end

```

Running test cases:

```
puts "      IN   *******   OUT"
["ABCDEFGHIJKL","ABCDEFGHIJK+","ABCDEFGHIJK/","ABCDEFGHIJLK","ABCD/9876542",
"ABCD/9876543","ABCD/987654+","ABCD/98765+E","ABCDEF+/9875","ABCDEF+/9876",
"ABCDEF/GHIJK","ABCDEF/GHIJL","ABCDEFG+/987","A+/987654321","/+9876543210"
    ].each do |v|
    t = B.new(v.dup)
    puts " #{v}   #{t.n}"
end

```

Outputs:

```
      IN   *******   OUT
 ABCDEFGHIJKL   ABCDEFGHIJKM
 ABCDEFGHIJK+   ABCDEFGHIJK/
 ABCDEFGHIJK/   ABCDEFGHIJLK
 ABCDEFGHIJLK   ABCDEFGHIJLM
 ABCD/9876542   ABCD/9876543
 ABCD/9876543   ABCD/987654+
 ABCD/987654+   ABCD/98765+E
 ABCD/98765+E   ABCD/98765+F
 ABCDEF+/9875   ABCDEF+/9876
 ABCDEF+/9876   ABCDEF/GHIJK
 ABCDEF/GHIJK   ABCDEF/GHIJL
 ABCDEF/GHIJL   ABCDEF/GHIJM
 ABCDEFG+/987   ABCDEFG/HIJK
 A+/987654321   A/BCDEFGHIJK
 /+9876543210   ABCDEFGHIJKL

```

For the long understandable version of this code see my github post https://github.com/danielpclark/b64challenge

This code was tested with Ruby version 1.9.3. I can only vouch for is version.
> 0 votes

---
Tags: code-golf, number, permutations
---


title: Counting to now

text:
# Question
Title: Counting to now
**This is the goal:** count from 0 all the way to the current epoch time while the epoch time is still advancing in the fastest time possible. An example of how you'd do it could be as what is shown here in Python 2.7:

```
from time import time
start, end, count = None, None, 0
while count <= time():
    if start == None: start = time()
    count += 1
    end = time()

```

The above code took 10 minutes and 8 seconds to run through on an 8-core AMD with 16 GB of RAM. You must do it faster than that without skipping numbers and starting from zero.

# Scoring

Achieving a lower time than what Python did is the goal in addition to using the least amount of code too, but special attention will be given to the following:

* Code that takes the precise epoch time sourced from your counting to display something mentioning historical events or irrelevant ones that can be found on Wikipedia. (10 points)
* Getting the current epoch time from a source other than your own. (5 points)
* Your application continues to count alongside the epoch time after it catches up. (5 points)

50 points will be awarded to the person who achieves the lowest time and additional bonus points will be awarded from above if they're met.

# Deadline

The contest closes June 1st.

# Answer
# Java : 140

**No bonuses, ~60ms runtime**

Sets the start time in `j` and doesn't check time again until `j` is reached. Once it is, it keeps counting up to current time. Generally it only needs to check the time twice, since it runs in well under a second.

```
class N{public static void main(String[]a){for(int i=0,j=t();i++<j||i<t(););}static int t(){return (int)(System.currentTimeMillis()/1000);}}

```

Line breaks for clarity:

```
class N{
    public static void main(String[]a){
        for(int i=0,j=t();i++<j||i<t(););
    }
    static int t(){return (int)(System.currentTimeMillis()/1000);}
}

```
> 1 votes

# Answer
# C, about 5 seconds

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

int main(){
  time_t t=0, margin=0x40000000;
  int i;
  while (margin) {
    for (i=0;i<margin;i++) t++;
    while (margin && time(NULL)-t < margin) margin /= 2;
  }
  printf("t=%ld, time=%ld\n",t,time(NULL));
  return 0;
}

```
> 1 votes

---
Tags: code-challenge
---


# Question
Title: Reverse order of words in a string inplace
## The Task

* You are given a mutable string that matches `[a-z]+( [a-z]+)*`.
* You must mutate it into the string which contains the same words, but in reverse order, so that "hello there everyone" becomes "everyone there hello".
* You are not permitted to use more than a constant amount of additional memory (so no copying the entire string or any whole word into a buffer you just allocated).
* There are no time constraints. Being hopelessly inefficient will not harm your score.
* If your language of choice does not permit mutation of strings, arrays of characters are an acceptable substitute.

## Your Score

* Your score is counted purely on the number of assigments you make to string elements (small scores are best). If you use a library function that writes to the string, its writes also count.
* Suppose the number of assignments you need for input *s* is *n(s)*. Then your score is the maximum (pedantically, supremum) over all inputs *s* (matching the regex specified above) of *n(s)/length(s)*. If you cannot calculate this precisely, you can use the lowest upper bound that you can prove.
* You can break a tie if you can prove that your algorithm uses asymptotically fewer assignments (this can happen even if you have the same score, see below). If you can't do this, you can break a tie by showing that you use less additional memory. However, the first tie-break condition always takes precedence.
* For some inputs every character needs to change, so it is not possible to score less than 1.
* I can think of a simple algorithm with score 2 (but I'm not entering it).

### Notes on suprema and ties

* A supremum of a set of numbers is the smallest number that is not smaller than any of them. This is much like the maximum of a set, except that some infinite sets like {2/3, 3/4, 4/5, 5/6, ...} have no single maximum element, but will still have a supremum, in this case 1.
* If you manage to "save" only a constant number of assignments over my algorithm of score 2 (say), your score will still be 2, because you'll get arbitrarily close to 2 the larger your input gets. However, you win on the tie-break if it comes to that.

# Answer
> 4 votes
## Python, Score: ~~2~~ ~~1.5~~ 1.25

This is the **direct** combination between primo's answer and my answer. So credits to him also!

The proof is still in progress, but here is the code to play with! If you can find a counter example of score greater than 1.25 (or if there is a bug), let me know!

Currently the worst case is:

```
a a ... a a dcb...cbd

```

where there are exactly **n** of each the letters "a", "b", "c", and " " (space), and exactly two "d"s. The length of the string is **4n+2** and the number of assignments is **5n+2**, giving a score of **5/4 = 1.25**.

The algorithm works in two steps:

1. Find `k` such that `string[k]` and `string[n-1-k]` are word boundaries
2. Run any word reversing algorithm on `string[:k]+string[n-1-k:]` (i.e., concatenation of first `k` and last `k` chars) with small modification.

where `n` is the length of the string.

The improvement this algorithm gives comes from the "small modification" in Step 2. It's basically the knowledge that in the concatenated string, the characters at position `k` and `k+1` are word boundaries (which means they are spaces or first/last character in a word), and so we can directly replace the characters in position `k` and `k+1` with the corresponding character in the final string, saving a few assignments. **This removes the worst case from the host word-reversal algorithm**

There are cases where we can't actually find such `k`, in that case, we just run the "any word reversal algorithm" on the whole string.

The code is long to handle these four cases on running the word reversal algorithm on the "concatenated" string:

1. When `k` is not found (`f_long = -2`)
2. When `string[k] != ' ' and string[n-1-k] != ' '` (`f_long = 0`)
3. When `string[k] != ' ' and string[n-1-k] == ' '` (`f_long = 1`)
4. When `string[k] == ' ' and string[n-1-k] != ' '` (`f_long = -1`)

I'm sure the code can be shortened. Currently it's long because I didn't have clear picture of the whole algorithm in the beginning. I'm sure one can design it to be represented in a shorter code =)

Sample run (first is mine, second is primo's):

```
Enter string: a bc def ghij
"ghij def bc a": 9, 13, 0.692
"ghij def bc a": 9, 13, 0.692
Enter string: ab c d e f g h i j k l m n o p q r s t u v w x y z
"z y x w v u t s r q p o n m l k j i h g f e d c ab": 50, 50, 1.000
"z y x w v u t s r q p o n m l k j i h g f e d c ab": 51, 50, 1.020
Enter string: a b c d e f g hijklmnopqrstuvwx
"hijklmnopqrstuvwx g f e d c b a": 38, 31, 1.226
"hijklmnopqrstuvwx g f e d c b a": 38, 31, 1.226
Enter string: a bc de fg hi jk lm no pq rs tu vw xy zc
"zc xy vw tu rs pq no lm jk hi fg de bc a": 46, 40, 1.150
"zc xy vw tu rs pq no lm jk hi fg de bc a": 53, 40, 1.325
Enter string: a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd
"dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a": 502, 402, 1.249
"dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a": 502, 402, 1.249

```

You can see that the score is almost the same, except for the worst case of the host word-reversal algorithm in the third example, for which my approach yields score of less than 1.25

```
DEBUG = False

def find_new_idx(string, pos, char, f_start, f_end, b_start, b_end, f_long):
    if DEBUG: print 'Finding new idx for s[%d] (%s)' % (pos, char)
    if f_long == 0:
        f_limit = f_end-1
        b_limit = b_start
    elif f_long == 1:
        f_limit = f_end-1
        b_limit = b_start+1
    elif f_long == -1:
        f_limit = f_end-2
        b_limit = b_start
    elif f_long == -2:
        f_limit = f_end
        b_limit = b_start

    if (f_start <= pos < f_limit or b_limit < pos < b_end) and char == ' ':
        word_start = pos
        word_end = pos+1
    else:
        if pos < f_limit+1:
            word_start = f_start
            if DEBUG: print 'Assigned word_start from f_start (%d)' % f_start
        elif pos == f_limit+1:
            word_start = f_limit+1
            if DEBUG: print 'Assigned word_start from f_limit+1 (%d)' % (f_limit+1)
        elif b_limit <= pos:
            word_start = b_limit
            if DEBUG: print 'Assigned word_start from b_limit (%d)' % b_limit
        elif b_limit-1 == pos:
            word_start = b_limit-1
            if DEBUG: print 'Assigned word_start from b_limit-1 (%d)' % (b_limit-1)
        i = pos
        while f_start <= i <= f_limit or 0 < b_limit <= i < b_end:
            if i==f_limit or i==b_limit:
                cur_char = 'a'
            elif i!=pos:
                cur_char = string[i]
            else:
                cur_char = char
            if cur_char == ' ':
                word_start = i+1
                if DEBUG: print 'Assigned word_start from loop'
                break
            i -= 1

        if b_limit <= pos:
            word_end = b_end
            if DEBUG: print 'Assigned word_end from b_end (%d)' % b_end
        elif b_limit-1 == pos:
            word_end = b_limit
            if DEBUG: print 'Assigned word_end from b_limit (%d)' % (b_limit)
        elif pos < f_limit+1:
            word_end = f_limit+1
            if DEBUG: print 'Assigned word_end from f_limit+1 (%d)' % (f_limit+1)
        elif pos == f_limit+1:
            word_end = f_limit+2
            if DEBUG: print 'Assigned word_end from f_limit+2 (%d)' % (f_limit+2)
        i = pos
        while f_start <= i <= f_limit or 0 < b_limit <= i < b_end:
            if i==f_limit or i==b_limit:
                cur_char = 'a'
            elif i!=pos:
                cur_char = string[i]
            else:
                cur_char = char
            if cur_char == ' ':
                word_end = i
                if DEBUG: print 'Assigned word_end from loop'
                break
            i += 1
    if DEBUG: print 'start, end: %d, %d' % (word_start, word_end)
    word_len = word_end - word_start
    offset = word_start-f_start
    result = (b_end-offset-(word_end-pos)) % b_end
    if string[result] == ' ' and (b_start == -1 or result not in {f_end-1, b_start}):
        return len(string)-1-result
    else:
        return result

def process_loop(string, start_idx, f_start, f_end, b_start, b_end=-1, f_long=-2, dry_run=False):
    assignments = 0
    pos = start_idx
    tmp = string[pos]
    processed_something = False
    count = 0
    while pos != start_idx or not processed_something:
        count += 1
        if DEBUG and count > 20:
            print '>>>>>Break!<<<<<'
            break
        new_pos = find_new_idx(string, pos, tmp, f_start, f_end, b_start, b_end, f_long)
        if DEBUG:
            if dry_run:
                print 'Test:',
            else:
                print '\t',
            print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos])
        if dry_run:
            tmp = string[new_pos]
            if new_pos == dry_run:
                return True
        elif pos == new_pos:
            break
        elif tmp == string[new_pos]:
            pass
        else:
            tmp, string[new_pos] = string[new_pos], tmp
            assignments += 1
        pos = new_pos
        processed_something = True
    if dry_run:
        return False
    return assignments

def reverse(string, f_start, f_end, b_start, b_end=-1, f_long=-2):
    if DEBUG: print 'reverse: %d %d %d %d %d' % (f_start, f_end, b_start, b_end, f_long)
    if DEBUG: print
    if DEBUG: print ''.join(string)
    assignments = 0
    n = len(string)
    if b_start == -1:
        for i in range(f_start, f_end):
            if string[i] == ' ':
                continue
            if DEBUG: print 'Starting from i=%d' % i
            if any(process_loop(string, j, f_start, f_end, -1, f_end, dry_run=i) for j in range(f_start, i) if string[j] != ' '):
                continue
            if DEBUG:
                print
                print 'Finished test'
            assignments += process_loop(string, i, f_start, f_end, -1, f_end)
            if DEBUG: print
            if DEBUG: print ''.join(string)
        for i in range(f_start, (f_start+f_end-1)/2):
            if (string[i] == ' ' and string[n-1-i] != ' ') or (string[i] != ' ' and string[n-1-i] == ' '):
                string[i], string[n-1-i] = string[n-1-i], string[i]
                assignments += 2
    else:
        for i in range(f_start, f_end)+range(b_start, b_end):
            if string[i] == ' ' and i not in {f_end-1, b_start}:
                continue
            if DEBUG: print 'Starting from i=%d' % i
            if any(process_loop(string, j, f_start, f_end, b_start, b_end, f_long, i) for j in range(f_start, f_end)+range(b_start, b_end) if j<i and (string[j] != ' ' or j in {f_end-1, b_start})):
                continue
            assignments += process_loop(string, i, f_start, f_end, b_start, b_end, f_long)
            if DEBUG: print
            if DEBUG: print ''.join(string)
        for i in range(f_start, f_end-1):
            if (string[i] == ' ' and string[n-1-i] != ' ') or (string[i] != ' ' and string[n-1-i] == ' '):
                string[i], string[n-1-i] = string[n-1-i], string[i]
                assignments += 2
    return assignments

class SuperList(list):
    def index(self, value, start_idx=0):
        try:
            return self[:].index(value, start_idx)
        except ValueError:
            return -1

    def rindex(self, value, end_idx=-1):
        end_idx = end_idx % (len(self)+1)
        try:
            result = end_idx - self[end_idx-1::-1].index(value) - 1
        except ValueError:
            return -1
        return result

def min_reverse(string):
    assignments = 0
    lower = 0
    upper = len(string)
    while lower < upper:
        front = string.index(' ', lower) % (upper+1)
        back = string.rindex(' ', upper)
        while abs(front-lower - (upper-1-back)) > 1 and front < back:
            if front-lower < (upper-1-back):
                front = string.index(' ', front+1) % (upper+1)
            else:
                back = string.rindex(' ', back)
            if DEBUG: print lower, front, back, upper
        if front > back:
            break
        if DEBUG: print lower, front, back, upper
        if abs(front-lower - (upper-1-back)) > 1:
            assignments += reverse(string, lower, upper, -1)
            lower = upper
        elif front-lower < (upper-1-back):
            assignments += reverse(string, lower, front+1, back+1, upper, -1)
            lower = front+1
            upper = back+1
        elif front-lower > (upper-1-back):
            assignments += reverse(string, lower, front, back, upper, 1)
            lower = front
            upper = back
        else:
            assignments += reverse(string, lower, front, back+1, upper, 0)
            lower = front+1
            upper = back
    return assignments

def minier_find_new_idx(string, pos, char):
    n = len(string)
    try:
        word_start = pos - next(i for i, char in enumerate(string[pos::-1]) if char == ' ') + 1
    except:
        word_start = 0
    try:
        word_end = pos + next(i for i, char in enumerate(string[pos:]) if char == ' ')
    except:
        word_end = n
    word_len = word_end - word_start
    offset = word_start
    result = (n-offset-(word_end-pos))%n
    if string[result] == ' ':
        return n-result-1
    else:
        return result

def minier_process_loop(string, start_idx, dry_run=False):
    assignments = 0
    pos = start_idx
    tmp = string[pos]
    processed_something = False
    while pos != start_idx or not processed_something:
        new_pos = minier_find_new_idx(string, pos, tmp)
        #print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos])
        if pos == new_pos:
            break
        elif dry_run:
            tmp = string[new_pos]
            if new_pos == dry_run:
                return True
        elif tmp == string[new_pos]:
            pass
        else:
            tmp, string[new_pos] = string[new_pos], tmp
            assignments += 1
        pos = new_pos
        processed_something = True
    if dry_run:
        return False
    return assignments

def minier_reverse(string):
    assignments = 0
    for i in range(len(string)):
        if string[i] == ' ':
            continue
        if any(minier_process_loop(string, j, dry_run=i) for j in range(i) if string[j] != ' '):
            continue
        assignments += minier_process_loop(string, i)
    n = len(string)
    for i in range(n/2):
        if string[i] == ' ' and string[n-i-1] != ' ':
            string[i], string[n-i-1] = string[n-i-1], string[i]
            assignments += 2
        elif string[n-i-1] == ' ' and string[i] != ' ':
            string[i], string[n-i-1] = string[n-i-1], string[i]
            assignments += 2
    return assignments

def main():
    while True:
        str_input = raw_input('Enter string: ')
        string = SuperList(str_input)
        result = min_reverse(string)
        n = len(string)
        print '"%s": %d, %d, %.3f' % (''.join(string), result, n, 1.0*result/n)
        string = SuperList(str_input)
        result2 = minier_reverse(string)
        print '"%s": %d, %d, %.3f' % (''.join(string), result2, n, 1.0*result2/n)

if __name__ == '__main__':
    main()

```

---

## Python, Score: 1.5

The exact number of assignments can be approximated by the formula:

```
n <= 1.5*length(string)

```

with the worst case being:

```
a b c d e f g h i jklmnopqrstuvwxyzzz

```

with 55 assignments on string with length 37.

The idea is similar to my previous one, it's just that in this version I tried to find prefix and suffix at word boundaries with length difference at most 1. Then I run my previous algorithm on that prefix and suffix (imagine them as being concatenated). Then continue on unprocessed part.

For example, for the previous worst case:

```
ab| a b| c

```

we will first do word reversal on "ab" and " c" (4 assignments) to be:

```
c | a b|ab

```

We know that at the boundary it used to be space (there are many cases to be handled, but you can do that), so we don't need to encode the space at the boundary, this is the main improvement from the previous algorithm.

Then finally we run on the middle four characters to get:

```
c b a ab

```

in total 8 assignments, the optimal for this case, since all 8 characters changed.

This eliminates the worst case in previous algorithm since the worst case in previous algorithm is eliminated.

See some sample run (and comparison with @primo's answer - his is the second line):

```
Enter string: i can do anything
"anything do can i": 20, 17
"anything do can i": 17, 17
Enter string: a b c d e f ghijklmnopqrs
"ghijklmnopqrs f e d c b a": 37, 25
"ghijklmnopqrs f e d c b a": 31, 25
Enter string: a b c d e f ghijklmnopqrst
"ghijklmnopqrst f e d c b a": 38, 26
"ghijklmnopqrst f e d c b a": 32, 26
Enter string: a b c d e f g h i jklmnozzzzzzzzzzzzzzzzz
"jklmnozzzzzzzzzzzzzzzzz i h g f e d c b a": 59, 41
"jklmnozzzzzzzzzzzzzzzzz i h g f e d c b a": 45, 41
Enter string: a b c d e f g h i jklmnopqrstuvwxyzzz
"jklmnopqrstuvwxyzzz i h g f e d c b a": 55, 37
"jklmnopqrstuvwxyzzz i h g f e d c b a": 45, 37
Enter string: ab a b a b a b a b a b a b a c
"c a b a b a b a b a b a b a ab": 30, 30
"c a b a b a b a b a b a b a ab": 31, 30
Enter string: ab a b a b a b a b a b a b a b c
"c b a b a b a b a b a b a b a ab": 32, 32
"c b a b a b a b a b a b a b a ab": 33, 32
Enter string: abc d abc
"abc d abc": 0, 9
"abc d abc": 0, 9
Enter string: abc d c a
"a c d abc": 6, 9
"a c d abc": 4, 9
Enter string: abc a b a b a b a b a b a b c
"c b a b a b a b a b a b a abc": 7, 29
"c b a b a b a b a b a b a abc": 5, 29

```

primo's answer is generally better, although in some cases I can have 1 point advantage =)

Also his code is much shorter than mine, haha.

```
DEBUG = False

def find_new_idx(string, pos, char, f_start, f_end, b_start, b_end, f_long):
    if DEBUG: print 'Finding new idx for s[%d] (%s)' % (pos, char)
    if f_long == 0:
        f_limit = f_end-1
        b_limit = b_start
    elif f_long == 1:
        f_limit = f_end-1
        b_limit = b_start+1
    elif f_long == -1:
        f_limit = f_end-2
        b_limit = b_start
    elif f_long == -2:
        f_limit = f_end
        b_limit = b_start

    if (f_start <= pos < f_limit or b_limit < pos < b_end) and (char == ' ' or char.isupper()):
        word_start = pos
        word_end = pos+1
    else:
        if pos < f_limit+1:
            word_start = f_start
            if DEBUG: print 'Assigned word_start from f_start (%d)' % f_start
        elif pos == f_limit+1:
            word_start = f_limit+1
            if DEBUG: print 'Assigned word_start from f_limit+1 (%d)' % (f_limit+1)
        elif b_limit <= pos:
            word_start = b_limit
            if DEBUG: print 'Assigned word_start from b_limit (%d)' % b_limit
        elif b_limit-1 == pos:
            word_start = b_limit-1
            if DEBUG: print 'Assigned word_start from b_limit-1 (%d)' % (b_limit-1)
        i = pos
        if not (i < f_limit and b_limit < i):
            i -= 1
        while f_start <= i < f_limit or 0 < b_limit < i < b_end:
            if i!=pos:
                cur_char = string[i]
            else:
                cur_char = char
            if cur_char == ' ' or cur_char.isupper():
                word_start = i+1
                if DEBUG: print 'Assigned word_start from loop'
                break
            i -= 1

        if b_limit <= pos:
            word_end = b_end
            if DEBUG: print 'Assigned word_end from b_end (%d)' % b_end
        elif b_limit-1 == pos:
            word_end = b_limit
            if DEBUG: print 'Assigned word_end from b_limit (%d)' % (b_limit)
        elif pos < f_limit+1:
            word_end = f_limit+1
            if DEBUG: print 'Assigned word_end from f_limit+1 (%d)' % (f_limit+1)
        elif pos == f_limit+1:
            word_end = f_limit+2
            if DEBUG: print 'Assigned word_end from f_limit+2 (%d)' % (f_limit+2)
        i = pos
        if not (i < f_limit and b_limit < i):
            i += 1
        while f_start <= i < f_limit or 0 < b_limit < i < b_end:
            if i!=pos:
                cur_char = string[i]
            else:
                cur_char = char
            if cur_char == ' ' or cur_char.isupper():
                word_end = i
                if DEBUG: print 'Assigned word_end from loop'
                break
            i += 1
    if DEBUG: print 'start, end: %d, %d' % (word_start, word_end)
    word_len = word_end - word_start
    offset = word_start-f_start
    return (b_end-offset-(word_end-pos)) % b_end

def process_loop(string, start_idx, f_start, f_end, b_start, b_end=-1, f_long=-2, dry_run=False):
    assignments = 0
    pos = start_idx
    tmp = string[pos]
    processed_something = False
    count = 0
    while pos != start_idx or not processed_something:
        count += 1
        if count > 20:
            if DEBUG: print 'Break!'
            break
        new_pos = find_new_idx(string, pos, tmp, f_start, f_end, b_start, b_end, f_long)
        #if dry_run:
        #    if DEBUG: print 'Test:',
        if DEBUG: print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos])
        if pos == new_pos:
            break
        elif dry_run:
            tmp = string[new_pos]
            if new_pos == dry_run:
                return True
        elif tmp == string[new_pos]:
            pass
        elif tmp == ' ':
            if b_start!=-1 and new_pos in {f_end-1, b_start}:
                tmp, string[new_pos] = string[new_pos], tmp
            else:
                tmp, string[new_pos] = string[new_pos], '@'
            assignments += 1
        elif string[new_pos] == ' ':
            if b_start!=-1 and new_pos in {f_end-1, b_start}:
                tmp, string[new_pos] = string[new_pos], tmp
            else:
                tmp, string[new_pos] = string[new_pos], tmp.upper()
            assignments += 1
        else:
            tmp, string[new_pos] = string[new_pos], tmp
            assignments += 1
        pos = new_pos
        processed_something = True
    if dry_run:
        return False
    return assignments

def reverse(string, f_start, f_end, b_start, b_end=-1, f_long=-2):
    if DEBUG: print 'reverse: %d %d %d %d %d' % (f_start, f_end, b_start, b_end, f_long)
    if DEBUG: print
    if DEBUG: print ''.join(string)
    assignments = 0
    if b_start == -1:
        for i in range(f_start, (f_start+f_end)/2):
            if DEBUG: print 'Starting from i=%d' % i
            if any(process_loop(string, j, f_start, f_end, -1, f_end, dry_run=i) for j in range(f_start, i)):
                continue
            assignments += process_loop(string, i, f_start, f_end, -1, f_end)
            if DEBUG: print
            if DEBUG: print ''.join(string)
    else:
        for i in range(f_start, f_end):
            if DEBUG: print 'Starting from i=%d' % i
            if any(process_loop(string, j, f_start, f_end, b_start, b_end, f_long, i) for j in range(f_start, i)):
                continue
            assignments += process_loop(string, i, f_start, f_end, b_start, b_end, f_long)
            if DEBUG: print
            if DEBUG: print ''.join(string)
    for i in range(len(string)):
        if string[i] == '@':
            string[i] = ' '
            assignments += 1
        if string[i].isupper():
            string[i] = string[i].lower()
            assignments += 1
    return assignments

class SuperList(list):
    def index(self, value, start_idx=0):
        try:
            return self[:].index(value, start_idx)
        except ValueError:
            return -1

    def rindex(self, value, end_idx=-1):
        end_idx = end_idx % (len(self)+1)
        try:
            result = end_idx - self[end_idx-1::-1].index(value) - 1
        except ValueError:
            return -1
        return result

def min_reverse(string):
    # My algorithm
    assignments = 0
    lower = 0
    upper = len(string)
    while lower < upper:
        front = string.index(' ', lower) % (upper+1)
        back = string.rindex(' ', upper)
        while abs(front-lower - (upper-1-back)) > 1 and front < back:
            if front-lower < (upper-1-back):
                front = string.index(' ', front+1) % (upper+1)
            else:
                back = string.rindex(' ', back)
            if DEBUG: print lower, front, back, upper
        if front > back:
            break
        if DEBUG: print lower, front, back, upper
        if abs(front-lower - (upper-1-back)) > 1:
            assignments += reverse(string, lower, upper, -1)
            lower = upper
        elif front-lower < (upper-1-back):
            assignments += reverse(string, lower, front+1, back+1, upper, -1)
            lower = front+1
            upper = back+1
        elif front-lower > (upper-1-back):
            assignments += reverse(string, lower, front, back, upper, 1)
            lower = front
            upper = back
        else:
            assignments += reverse(string, lower, front, back+1, upper, 0)
            lower = front+1
            upper = back
    return assignments

def minier_find_new_idx(string, pos, char):
    n = len(string)
    try:
        word_start = pos - next(i for i, char in enumerate(string[pos::-1]) if char == ' ') + 1
    except:
        word_start = 0
    try:
        word_end = pos + next(i for i, char in enumerate(string[pos:]) if char == ' ')
    except:
        word_end = n
    word_len = word_end - word_start
    offset = word_start
    result = (n-offset-(word_end-pos))%n
    if string[result] == ' ':
        return n-result-1
    else:
        return result

def minier_process_loop(string, start_idx, dry_run=False):
    assignments = 0
    pos = start_idx
    tmp = string[pos]
    processed_something = False
    while pos != start_idx or not processed_something:
        new_pos = minier_find_new_idx(string, pos, tmp)
        #print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos])
        if pos == new_pos:
            break
        elif dry_run:
            tmp = string[new_pos]
            if new_pos == dry_run:
                return True
        elif tmp == string[new_pos]:
            pass
        else:
            tmp, string[new_pos] = string[new_pos], tmp
            assignments += 1
        pos = new_pos
        processed_something = True
    if dry_run:
        return False
    return assignments

def minier_reverse(string):
    # primo's answer for comparison
    assignments = 0
    for i in range(len(string)):
        if string[i] == ' ':
            continue
        if any(minier_process_loop(string, j, dry_run=i) for j in range(i) if string[j] != ' '):
            continue
        assignments += minier_process_loop(string, i)
    n = len(string)
    for i in range(n/2):
        if string[i] == ' ' and string[n-i-1] != ' ':
            string[i], string[n-i-1] = string[n-i-1], string[i]
            assignments += 2
        elif string[n-i-1] == ' ' and string[i] != ' ':
            string[i], string[n-i-1] = string[n-i-1], string[i]
            assignments += 2
    return assignments

def main():
    while True:
        str_input = raw_input('Enter string: ')
        string = SuperList(str_input)
        result = min_reverse(string)
        print '"%s": %d, %d' % (''.join(string), result, len(string))
        string = SuperList(str_input)
        result2 = minier_reverse(string)
        print '"%s": %d, %d' % (''.join(string), result2, len(string))

if __name__ == '__main__':
    main()

```

---

## Python, Score: asymptotically 2, in normal case much less

*old code removed due to space constraint*

The idea is to iterate through each index, and for each index `i`, we take the character, calculate the new position `j`, memorize the character at position `j`, assign the character at `i` to `j`, and repeat with character at index `j`. Since we need the space information to calculate the new position, I encode old space as the uppercase version of the new letter, and new space as '@'.

# Answer
> 14 votes
## Perl, score 1.3̅

For each non-space character one assignment is performed, and for each space character two assignments. ~~Because space characters cannot amount to more than one half the total number of characters, the worst case score is *1.5*.~~

The algorithm hasn't changed, but I can prove a lower upper bound. Let us make two observations:

1. Spaces directly across from spaces do not need to be swapped.
2. Single character words directly across from spaces are not swapped during the main phase, but only once at the end.

It can then be seen that the theoretical 'worst case' with asymptotically 1/2 spaces is not worst case at all: `ab c d e f g h i ...`

```
$ echo ab c d e f g h i j k l m n o p q r s t u v w x y z|perl reverse-inplace.pl
z y x w v u t s r q p o n m l k j i h g f e d c ab
swaps: 51; len: 50
ratio: 1.02

```

In fact, it's quite a good case.

In order to prevent observation one and two above, each one-character word would need to be repositioned into the middle of a word three or more characters long. This would suggest a worst case containing asymptotically 1/3 spaces: `a bcd a bcd a ... bc`

```
$ echo a bcd a bcd a bcd a bcd a bcd a bc|perl reverse-inplace.pl
bc a bcd a bcd a bcd a bcd a bcd a
swaps: 45; len: 34
ratio: 1.32352941176471

```

Or equivalently, only two-character words: `a bc de fg hi jk ...`

```
$ echo a bc de fg hi jk lm no pq rs tu vx xy|perl reverse-inplace.pl
xy vx tu rs pq no lm jk hi fg de bc a
swaps: 49; len: 37
ratio: 1.32432432432432

```

Because the worst case contains asymptotically 1/3 spaces, the worst case score becomes *1.3̅*.

```
#!perl -l
use warnings;

$words = <>;
chomp($words);
$len = length($words);
$words .= ' ';
$spaces = 0;
# iterate over the string, count the spaces
$spaces++ while $words =~ m/ /g;

$origin = 0;
$o = vec($words, $origin, 8);
$cycle_begin = $origin;
$swaps = 0;

# this possibly terinates one iteration early,
# if the last char is a one-cycle (i.e. moves to its current location)
# one-cycles previous to the last are iterated, but not swapped.
while ($i++ < $len - $spaces || !$was_cycle) {
  $w_start = rindex($words, ' ', $origin);
  $w_end = index($words, ' ', $origin);
  $pos = ($origin - $w_start) - 1;
  $target = $len - ($w_end - $pos);
  $t = vec($words, $target, 8);

  if ($t == 32) {
    $target = $len - $target - 1;
    $t = vec($words, $target, 8);
  }

  # char is already correct, possibly a one-cycle
  if ($t != $o) {
    $swaps += 1;
    vec($words, $target, 8) = $o;
  }

  $origin = $target;
  $o = $t;
  if ($origin == $cycle_begin) {
    if ($i < $len - $spaces) {
      # backtrack through everything we've done up to this point
      # to find the next unswapped char ...seriously.
      $origin += 1;
      if (vec($words, $origin, 8) == 32) {
        $origin += 1;
      }
      $bt_origin = 0;
      $bt_cycle_begin = 0;
      while ($bt_cycle_begin < $origin) {
        $w_start = rindex($words, ' ', $bt_origin);
        $w_end = index($words, ' ', $bt_origin);
        $pos = ($bt_origin - $w_start) - 1;
        $target = $len - ($w_end - $pos);
        $t = vec($words, $target, 8);

        if ($t == 32) {
          $target = $len - $target - 1;
          $t = vec($words, $target, 8);
        }

        if ($target == $bt_cycle_begin) {
          $bt_origin = ++$bt_cycle_begin;
          if (vec($words, $bt_origin, 8) == 32) {
            $bt_origin = ++$bt_cycle_begin;
          }
        } else {
          $bt_origin = $target;
        }

        if ($target == $origin) {
          $origin += 1;
          if (vec($words, $origin, 8) == 32) {
            $origin += 1;
          }
          $bt_origin = $bt_cycle_begin = 0;
        }
      }
    }

    $cycle_begin = $origin;
    $o = vec($words, $origin, 8);
    $was_cycle = 1;
  } else {
    $was_cycle = 0;
  }
}

for $i (0..$len/2-1) {
  $mirror = $len - $i - 1;
  $o = vec($words, $i, 8);
  $m = vec($words, $mirror, 8);
  # if exactly one is a space...
  if (($o == 32) ^ ($m == 32)) {
    $swaps += 2;
    vec($words, $mirror, 8) = $o;
    vec($words, $i, 8) = $m;
  }
}

chop($words);
print $words;
print "swaps: $swaps; len: $len";
print 'ratio: ', $swaps/$len;

```

***Edit:** Added a swap counter, and the ratio.*

Input is taken from stdin. Sample usage:

```
$ echo where in the world is carmen sandiego|perl reverse-inplace.pl
sandiego carmen is world the in where
swaps: 35; len: 37
ratio: 0.945945945945946

```

---

**Method**

To begin, the first character of the string is moved to its final destination. The character just replaced is then moved to its destination, etc. This continues until one of two conditions is met:

1. **The character should be swapped with a space.**
When this occurs, the character is *not* swapped with the space, but rather into the mirror position of the space. The algorithm continues from that position.
2. **A cycle has been reached.**
When the target returns to the initial starting position of the current cycle, the next unswapped character (or rather, any unswapped character would do) needs to be found. To do this under constant memory constraints, all swaps that have been made up to this point are back-tracked.

After this phase, each non-space character has been moved at most once. To finish, all space characters are swapped with the characters at their mirror positions, requiring two assignment operations per space.

# Answer
> 7 votes
### Ruby, score 2

As a starter a very basic algorithm. It first reverses the whole string and then reverses each word in the string again. In the worst case (one word, even number of characters) the score becomes 2.

```
def revstring(s, a, b)
  while a<b
    h = s[a]
    s[a] = s[b]
    s[b] = h
    a += 1
    b -= 1
  end
  s
end

def revwords(s)
  revstring(s, 0, s.length-1)
  a = 0
  while a<s.length
    b = a+1
    b += 1 while b<s.length and s[b]!=" "
    revstring(s, a, b-1)
    a = b+1
  end
  s
end

```

Usage:

```
> revwords("hello there everyone")
"everyone there hello"

```

# Answer
> 5 votes
**C++: Score 2**

```
#include<iostream>
#include<algorithm>

void rev(std::string& s)
{
    std::reverse(s.begin(),s.end());
    std::string::iterator i=s.begin(),j=s.begin();
    while(i!=s.end())
    {
        while(i!=s.end()&&(*i)==' ')
            i++;
        j=i;
        while(i!=s.end()&&(*i)!=' ')
            i++;
        std::reverse(j,i);
    }
}

int main()
{
    std::string s;
    getline(std::cin,s);
    rev(s);
    std::cout<<s;
}

```

# Answer
> 2 votes
**C : Score 2**

This just flips the entire string once then reverses each word.

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

void reverse(char *s,unsigned n){
    char c;
    unsigned i=0,r=1;
    while(i < n){ //no swap function in C
        c=s[i];
        s[i++]=s[n];
        s[n--]=c;
    }
}

unsigned wordlen(char *s){
    unsigned i=0;
    while (s[i] != ' ' && s[i]) ++i;
    return i;
}

int main(int argc, char **argv) {
    char buf[]="reverse this also";
    char *s=buf;
    unsigned wlen=0,len=strlen(s)-1;
    reverse(s,len);  //reverse entire string
    while(wlen<len){  // iterate over each word till end of string
      wlen=wordlen(s);
      reverse(s,wlen-1);
      s+=wlen+1;
      len-=wlen;
    }
    printf("%s\n",buf);
    return 0;
}

```

# Answer
> 2 votes
# Rebol

```
reverse-words: function [
    "Reverse the order of words. Modifies and returns string (series)"
    series [string!] "At position (modified)"
  ][
    first-time: on
    until [
        reverse/part series f: any [
            if first-time [tail series]
            find series space
            tail series
        ]
        unless first-time [series: next f]
        first-time: off
        tail? series
    ]

    series: head series
]

```

I'm unclear on the scoring for this. There is no direct string assignment in this code. Everything is handled by the one `reverse/part` which does in-place reversing within and initially on the whole the string.

Some detail on the code:

* Loop through string (`series`) until it reaches the `tail?`
* First time in loop do full reverse of string - `reverse/part series tail series` (which is same as `reverse series`)
* Then reverse every word found on further iterations - `reverse/part series find series space`
* Once exhausted word finds then return `tail series` so that it will reverse last word in string - `reverse/part series tail series`

Rebol allows traversing of a string via an internal *pointer*. You can see this at `series: next f` (move pointer to after space so beginning of next word) and `series: head series` (resets pointer back to the head).

See Series for more info.

Usage example in Rebol console:

```
>> reverse-words "everyone there hello"
== "hello there everyone"

>> x: "world hello"
== "world hello"

>> reverse-words x
== "hello world"

>> x
== "hello world"

>> reverse-words "hello"
== "hello"

```

# Answer
> 1 votes
### Python: score 2

Almost identical to Howard's algorithm, but does the reversal steps in reverse (first flips words then flips the whole string). Additional memory used is 3 byte-size variables: `i`, `j`, and `t`. Technically, `find` and `len` are using some internal variables, but they could just as easily re-use `i` or `j` without any loss of function.

*quick edit:* saving on string assignments by only swapping when characters differ, so I can grab some extra points from note #2.

```
from sys import stdin

def word_reverse(string):
    # reverse each word
    i=0
    j=string.find(' ')-1
    if j == -2: j=len(string)-1
    while True:
        while i<j:
            if string[i] != string[j]:
                t = string[i]
                string[i] = string[j]
                string[j] = t
            i,j = i+1,j-1
        i=string.find(' ', i)+1
        if i==0: break
        j=string.find(' ', i)-1
        if j == -2: j=len(string)-1
    # reverse the entire string
    i=0
    j=len(string)-1
    while i<j:
        if string[i] != string[j]:
            t = string[i]
            string[i] = string[j]
            string[j] = t
        i,j = i+1,j-1
    return string

for line in stdin.readlines():
    # http://stackoverflow.com/a/3463789/1935085
    line = line.strip() # no trailing newlines ore spaces to ensure it conforms to '[a-z]+( [a-z]+)*'
    print word_reverse(bytearray(line))

```

# Answer
> 1 votes
## Batch

I'll admit to not fully understand the scoring (I think it's two).. but I will say - ***it does the thing***.

```
@echo off

setLocal enableDelayedExpansion
set c=
set s=

for %%a in (%~1) do set /a c+=1 & echo %%a >> f!c!

for /L %%a in (!c!, -1, 1) do (
    set /p t=<f%%a
    set s=!s!!t!
    del f%%a
)

echo !s!

```

Input is taken as first standard input value, and so needs to be surrounded by quotation marks -
call: `script.bat "hello there everyone"`
out: `everyone there hello`.

Maybe someone else can score me (assuming I haven't, in some other way, disqualified myself).

# Answer
> -2 votes
# Javascript

```
function reverseWords(input) {
    if (input.match(/^[a-z]+( [a-z]+)*$/g)) {
        return input.split(' ').reverse().join(' ');
    }
}

```

Usage:

```
> reverseWords('hello there everyone');
'everyone there hello'

```

I get the strange feeling I missed something...

---
Tags: code-challenge
---