title: How many paths are available?

text:
# Question
Title: How many paths are available?
# Objective

Find out how many possible (unique) paths you can take to get from the top left of a NxN grid to the bottom right.

The program will receive either 1 integer (or 2 for -20 points bonus) as input for the gridsize.
Input has to be anywhere in the range of 1..2000.
Output will be a string containing the number of possible paths in either decimal or hex format.

### Moving

You can only move in 2 directions, right and down.

### Example

This example will show the possible paths in a 2x2 grid so you can see what correct paths are.
I gave each line a different color, the output for a 2x2 grid will be 6.

### This will be a big number

Indeed, it will be a big number, huge, enormous, gigantic or any other word you can come up with. Just to keep the fun in the challenge you are not allowed to use any plugins, libraries, native functions or any other thing I forgot to name that allows you to handle integers that would exceed an int64. So come up for a creative way to handle this.

### Restrictions

As said before you cant use anything simular to BigInteger in C# for example.
Write an algorithm to solve this problem rather than a built-in function that would destroy the challenge.

## Scoring

This is codegolf so obviously the score is based on the length of your code.

### Achievements

* **Y U NO SQR()** \- The program accepts non square grids ex. \[4,3\], \[100,20\] etc. **Reward: -20 points + invisible baby panda**
* **Need for Speed!** \- The size of the grid will not result in a significant difference in the runtime where 1 second is considered significant. **Reward: -20 points + Invisible bamboo for the baby panda** *(you dont want him to starve right?)*
* **IT'S OVER NINE THOUSAANNNNDD** \- The program accepts gridsizes over 9000 **Reward: -20 points + Invisible unicorn costume (baby panda size)** *Coz asians love cosplay*

### Assumptions

You can assume the following:

* The input will never be a negative integer.
* The input will always be \>0 and never \>2000.
* You will always start at \[0,0\] and move to \[N,N\]

These baby pandas are sad and lonely, I cant take care of them all by myself so I need your help. Get on with it and claim your own baby panda while theyre still fresh ^.^ (instant delivery guaranteed.)

Happy coding :D

# Answer
## GolfScript (62 - 40 = 22 points)

```
~.),{!}%1/\@+{1,\{0@2$[\]zip{{+}/.10/\10%}%\[.](<+}%}*~]-1=-1%

```

This program takes two inputs in the form `w h` from stdin and outputs the result to stdout. The largest intermediate value is `w+h`; although GolfScript has native big integers, this uses an array of single decimal digits for the calculations.

Bonuses claimed: non-square grids and grid sizes over 9000.

Online demo

### Dissection

```
# Stack: 'w h'
~
# Stack: w h
.),{!}%1/\@+
# Stack: [[1] [0] ... [0]] w+h  (where the array contains h [0]s)
# Loop w+h times:
{
    # Stack: nth row of Pascal's triangle. Put [0] on the stack underneath it.
    1,\
    # Update to get the (n+1)th row.
    {
        # Stack: [prev] [curr]
        # We need the 0 for the carry in
        0@2$
        # Stack: [curr] 0 [prev] [curr]
        # Group digits of prev and curr
        [\]zip
        # Simple addition
        {
            # Stack: [curr] carry-in [a b]
            # Although if the zip was of two arrays of different length,
            # it might just be [a] instead of [a b]
            {+}/.10/\10%
            # Stack: [curr] carry-out=(carry-in+a+b)/10 digit=(carry-in+a+b)%10
        }%
        # Stack: [curr] carry-out [sum]
        # We want to append the carry-out to the sum iff it's not 0
        \[.](<+
        # Stack: [curr] [sum]
    }%
    # Stack: ... [last of previous row] [next row]
}*
# Stack: garbage [[1] ... [result in little-endian]]
~]-1=-1%
# Stack: [result in big-endian]

```
> 2 votes

# Answer
# C, 201-20-20=161

Completely refactored since rev 0. Bonuses claimed: non-square and over 9000.

```
#define B i%w][j]
char a[22000][5999];n,m,i,j,w=21669,c;main(){scanf("%d%d",&n,&m);
for(a[w/2][w/4]=1;i<w*(n+m);i+=2)for(j=5418;j--;a[1+B-=c*10)c=(a[1+B=(a[B+a[2+B+c)%48+48)>57;
printf("%s",a[w/2+n-m]);}

```

**Algorithm**

Calculating a number like 4000!/(2000!)^2 using multiplication and division seemed rather complicated to me. Instead I went for an approach based on iterating through the rows of Pascal's triangle, using only addition.

Here's an example using an `int32` type, just to show the algorithm clearly:

```
int a[999],n,m,i,w=997;
main(){
  scanf("%d %d",&n,&m);
  a[w/2]=1;
  for(i=0;i<w*(n+m);i+=2)a[i%w+1]=a[i%w]+a[i%w+2];
  printf("%d",a[w/2+n-m]);
}

```

Where n+m is the number of rows of Pascal's triangle (counting the `1` at the top as row zero.) At the end of the program, a\[\] contains rows x and x-1 of Pascal's triangle, the even row in the even cells, and the odd row in the odd cells.

It's important that `w` is an odd number, so that on each pass through the array it alternates between writing to the odd and even cells. Also, it is important to ensure that the 1 used to initialise the array is not overwritten on the first pass. This requires that `w/2` be even. I will explain this later.

This program will give the right answer, up to about n=m=16, after which the integer type overflows.

**Ungolfed code**

This works in the same way, but uses an array of `char` to store the decimal digits (in big endian format.) In order to minimise the code needed to print the answer, the calculations are performed using the ASCII values (add 48 to each value.)

Note that the value of `w` is enough to hold rows 9000 and 8999 the same time (a total of 9001+9000=18001 big numbers.) We actually get as far as row 18000 of Pascal's triangle, so by that stage there will not be enough space in the array to hold all 9001+9000 big numbers, and some wrapping around will occur. But this does not affect the central cell of row 9000, which is the only cell we are interested in.

Besides adding whitespace, I have explicitly spelt out the `#define` and ungolfed `w/4` to the correct value of 5417. This value is chosen because 18000C9000 has 5417 digits.

```
char a[22000][5999];
n,m,i,j,w=21669,c;
main(){
  scanf("%d%d",&n,&m);
  for(a[w/2][5417]=1;i<w*(n+m);i+=2)                       //Initialise array with a 1 in least significant bit of the middle cell of [a]. Loop through the numbers of each row of Pascal's triangle.
    for(j=5418;j--;a[1+i%w][j]-=c*10)                      //Loop through the digits of each number. The code to subtract 10 from the digit if carry flag `c` is executed after the following line.
      c=(a[1+i%w][j]=(a[i%w][j]+a[2+i%w][j]+c)%48+48)>57;  //Update the cell with a digit that is the sum of the ones to the left and right, taking into account the carry, and using mod 48 arithmetic in order to store the number as its ASCII code. The return value of the assigment to a[1+i%w][j] is compared with ASCII 57 (`9`) and if it is greater the carry flag `c` is set.
  printf("%s",a[w/2+n-m]);
}

```

**Output**

My first program took about an hour to print 4000C2000. This one can handle more digits and a higher number of rows to comply with the over 9000 rule. Consequently it takes about 15 hours to print 4000C2000 and would take several days to print 18000C9000.

For 2000x2000 it prints the following (formatted to 80 columns for clarity.) This can be verified to be correct here: http://www.wolframalpha.com/input/?i=4000C2000

```
First 50 rows of 80 zeros (total 4000) omitted
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000001662897875033835069539536
82646038155801622559738864034512798427681344501750925293497511985938004836061174
06787175851646432467983900275415704358907838322828226892377078626044702804227263
60225612674740415245206094268141079326236405795693301673758014841914146088010797
10165776274135023159100265188426666848338060694979313461996523028997743355283203
07681570747572865349817098575890269928612521344100050157521073022188690505729147
51382188762791861883958161617214384992392748400481691029679535864524592128327086
43054316262086765263594646961335049751537926540975614276702537605304524934071255
73064101385096253973516475386956779128378613359541658838021140118989221026997673
52312197112642059780157612212146003819787455505953360709346068359603711700350715
41788401648588967587345651743656288974543012791416766391390825096496908159194487
46858927217899313004799502582220660617063988223169179908327236982684836052004811
13856792890524143074688488766572261180609865630282282923756619604128170737791195
46057911790152387847927530536412500605466256862821891455217494809727772321234293
80354002249110229834175370966913440248688425483608677217484634416362795730488526
6233145705056647940287649067948285761750402006009891416640

```
> 2 votes

# Answer
# Javascript, 318 - 20 = 298

```
N=prompt(),Z=6e3,D=N*2,O=Array(D),W=Array(D);function p(n){while(n.length<Z)n="0"+n;return n}function a(a,b){r="",c=0,i=Z;while(i-->0){v=a[i]- -b[i]+c,r=(v%10)+r,c=~~(v/10)}return r}O[0]=p("1");for(x=1;x<=D;x++){for(y=0;y<=x;y++)if(x==1||y==0||y==x)W[y]=p("1");else W[y]=a(O[y-1],O[y]);O=W;W=Array(D)}console.log(O[N])

```

It's simple add only big number and pascal's triangle.

You can run this at your browser's console, but I don't recommend. You'd better run it from command line using Node.js. If you run this with Node.js, you need to modify `N=prompt()` to `N=YOUR_NUMBER`.

It took about an hour to calculate N=2000 using Node.js (with `Z=2e3`). I don't know how long will it take with `Z=6e3`.

Since `18000C9000` is less than 6000 decimal digits, this can calculate more than N=9000. And of course digit limit can be extended.

## Output (`N=2000, Z=2e3`, 80 columns per row)

```
0000000000000000000000000000000000000000000000000000000000000000000000000000000
( 9 more zero rows)
0000000166289787503383506953953682646038155801622559738864034512798427681344501
7509252934975119859380048360611740678717585164643246798390027541570435890783832
2828226892377078626044702804227263602256126747404152452060942681410793262364057
9569330167375801484191414608801079710165776274135023159100265188426666848338060
6949793134619965230289977433552832030768157074757286534981709857589026992861252
1344100050157521073022188690505729147513821887627918618839581616172143849923927
4840048169102967953586452459212832708643054316262086765263594646961335049751537
9265409756142767025376053045249340712557306410138509625397351647538695677912837
8613359541658838021140118989221026997673523121971126420597801576122121460038197
8745550595336070934606835960371170035071541788401648588967587345651743656288974
5430127914167663913908250964969081591944874685892721789931300479950258222066061
7063988223169179908327236982684836052004811138567928905241430746884887665722611
8060986563028228292375661960412817073779119546057911790152387847927530536412500
6054662568628218914552174948097277723212342938035400224911022983417537096691344
0248688425483608677217484634416362795730488526623314570505664794028764906794828
5761750402006009891416640

```
> 2 votes

# Answer
# JavaScript (ECMAScript 6 & Typed Arrays) - Score: 269 - 20 = 249

```
g=(a,b)=>b?g(b,a%b):a;f=x=>{for(r=[i=0];i<x;)r[i]=++i+x;for(i in r){k=+i+1;for(j in r){r[j]/=d=g(k,r[j]);k/=d}}return r.reduce((x,y)=>{y+='';z=Int8Array(x[l='length']+y[l]);for(a=x[l];a--;)for(b=y[l];b--;){d=z[p=a+b+1]+x[a]*y[b];z[p]=d%10;z[p-1]+=d/10|0}return z},'1')}

```

**Score:**

* 269 Characters
* Can handle large grid sizes (above 9,000) for bonus -20 points (and does the calculation for 10,000x10,000 grid in hundreds of seconds rather than in hours).

**Input:**

Run `f(x)` where `x` is the grid size.

**Output:**

A Typed Array (of Int8) where each array element contains a digit of the answer (or wrap the output in `[...result].join('')` to convert it to a string.)

**Explanation:**

Unlike the other answers, this does not rely on calculating Pascal's Triangle.

Instead it calculates C(n,k) = n!/(k!(n-k)!) and, for a n-by-n grid then the answer is C(2n,n) = (2n)!/(n!n!) however, (2n)!/n! can be simplified to the product of the numbers (n+1)...(2n) and then the division by n! can be done by cancelling common factors from those numbers before calculating the product.

```
g=(a,b)=>b?g(b,a%b):a;

```

is a function to calculate the greatest common divisor of two numbers.

```
f=x=>{
  for(r=[i=0];i<x;)r[i]=++i+x;
  for(i in r){
    k=+i+1;
    for(j in r){
      r[j]/=d=g(k,r[j]);
      k/=d
    }
  }
  return r.reduce((x,y)=>{..},'1')
}

```

The first for-loop creates an array `r` of the numbers (x+1)...(2x). The second for-loop goes through the numbers 1...x and then (in the nested for-loop) finds common divisors with values in `r` and cancels them. The return value then reduces `r` and multiplies all the values together.

The function called by reduce is:

```
(x,y)=>{
  y+='';
  z=Int8Array(x[l='length']+y[l]);
  for(a=x[l];a--;)
    for(b=y[l];b--;){
      d=z[p=a+b+1]+x[a]*y[b];
      z[p]=d%10;
      z[p-1]+=d/10|0
    }
  return z
}

```

Which creates a Typed Array to store each digit of the number and then performs long multiplication to calculate the result.

**ECMAScript 5 Version:**

(Chrome Friendly and a few additional modifications for performance - such as preventing multiplication by 1)

```
l='length'
function M(x,y){var r=new Uint8Array(x[l]+y[l]);for(a=x[l];a--;)for(b=y[l];b--;){d=r[p=a+b+1]+x[a]*y[b];r[p]=d%10;r[p-1]+=d/10|0}return r}
function g(a,b){return b?g(b,a%b):a;}
function f(x){for(r=[i=0];i<x;)r[i]=++i+x;for(i in r){k=+i+1;for(j in r){r[j]/=d=g(k,r[j]);k/=d}}return r.reduce(function(p,c){return c<2?p:M(p,c+'')},new Uint8Array([1]))}

```

**Tests:**

20x20 Grid:

```
time=new Date();result=f(20);console.log("Time Taken: " + (new Date()-time)/1e3 + " seconds");[...result].join('').replace(/^0+/,'');
"137846528820"
"Time Taken: 0.001 seconds"

```

10,000x10,000 Grid:

```
time=new Date();result=f(10000);console.log("Time Taken: " + (new Date()-time)/1e3 + " seconds");[...result].join('').replace(/^0+/,'');
"[encoded data, 6019 characters]"
"Time Taken: 219.353 seconds"

```
> 2 votes

---
Tags: code-golf
---


title: Executable Sonnet

text:
# Question
Title: Executable Sonnet
Write a program that is a sonnet, and when run prints out a sonnet.

By "sonnet" I mean:

* 14 lines
* Each line, when read aloud, has 10 syllables

Symbols can be ignored, or pronounced in whatever reasonable way you want.

Popularity contest, most upvotes wins.

# Answer
> 5 votes
## Linux shell script

Cheating, I know.

### Edit: a version that rhymes:

(Thanks @professorfish for the idea of using the options of `cat`)

```
#!/bin/cat -bAse
In thee thy summer, ere thou be distilled:
Make sweet some vial; treasure thou some place
With beauty's treasure ere it be self-killed.
That use is not forbidden usury,
Which happies those that pay the willing loan;
That's for thy self to breed another thee,
Or ten times happier, be it ten for one;
Ten times thy self were happier than thou art,
If ten of thine ten times refigured thee:
Then what could death do if thou shouldst depart,
Leaving thee living in posterity?
   Be not self-willed, for thou art much too fair
   To be death's conquest and make worms thine heir.

```

First line pronounced as "shebang slash bin slash cat negative base". The line numbers and `$` in the output are to be ignored when reading aloud.

Taken from Shakespeare's Sonnet VI.

### Old version:

```
#!/usr/bin/env cat
For slander's mark was ever yet the fair;
The ornament of beauty is suspect,
A crow that flies in heaven's sweetest air.
So thou be good, slander doth but approve
Thy worth the greater, being wooed of time;
For canker vice the sweetest buds doth love,
And thou present'st a pure unstained prime.
Thou hast passed by the ambush of young days
Either not assailed, or victor being charged;
Yet this thy praise cannot be so thy praise,
To tie up envy, evermore enlarged,
   If some suspect of ill masked not thy show,
   Then thou alone kingdoms of hearts shouldst owe.

```

First line pronounced as "she-bang slash use-r slash bin slash env cat".

Taken from Shakespeare's Sonnet LXX.

---
Tags: popularity-contest
---


title: Avoid the evil integers!

text:
# Question
Title: Avoid the evil integers!
You are developing some code to generate ID numbers. Policy requires that no ID numbers include the digit sequence *666*.

Create a function (or your language's equivalent) which takes a positive integer parameter and returns the next integer that does not include *666* when that integer is expressed in decimal. (60606 is fine, 66600 is not.)

Your code must not use a loop that adds one until it finds a result that fits the rules.

```
f(1) returns 2.
f(665) returns 667.
f(665999999) returns 667000000 without having looped a million times.
(Following examples added since the question was first posed.)
f(666666666) also returns 667000000.
f(66600) returns 66700.
f(456667) returns 456670.

```

UPDATE:
Replacing 666 with 667 won't work if there's more than one 666 in the input.

# Answer
> 53 votes
# Python, no string manipulation

```
def f(n):
    n += 1
    p = 1
    m = n
    while m:
        if m % 1000 == 666:
            n += p - n % p
        p *= 10
        m /= 10
    return n

```

Works by finding powers of 10, `p`, where 666 appears, and adding `p - n % p` to `n` which replaces `666xxxxx` with `66700000`.

# Answer
> 50 votes
# JavaScript (updated to work with all test cases)

The little-known truth is that there are actually four `6`s, but one of the betrayed the others and polymorphed into code form to eradicate them from the ~~world~~ digits of the numbers. Here is that traitorous six:

```
    x=prompt(''+
  'Enter number');
 alert(      ( (~x[
'ind'+
'exOf']('666')))?(x
.replace(/666(.*)$/,
function    (mat,g){
return       '667'+g
 ['re'+      'place'
 ](/./g,0)})):((+x+
    1+'').replace(
     666,667)));

```

Here is an explanation. First, beautify the code and remove useless stuff like `''+'string'` and `((code))`:

```
x = prompt('Enter number');
alert(
    ~x['indexOf']('666')
        ?
    x.replace(/666(.*)$/, function(mat,g) {
        return '667' + g['replace'](/./g,0)
    })
        :
    (+x+1+'').replace(666, 667)
);

```

Convert weird notations (like `~indexOf` and `['replace']`) into more common ones:

```
x = prompt('Enter number');
alert(
    x.indexOf('666') > -1
        ?
    x.replace(/666(.*)$/, function(mat, g) {
        return '667' + g.replace(/./g, 0)
    })
        :
    ((parseInt(x) + 1) + '').replace(666, 667)
);

```

And now simply understand that the algorithm goes like this:

* If there is already a 666 in the input,

+ replace it with a 667.
    + replace every digit after that with a 0.
* else,

+ add one to the number.
    + NOTE: we are now guaranteed to have either no 666, a 666 at the end of the string, or a 666 somewhere else that already has zeroes going to the end (think "carrying" when doing "manual" addition).
    + if there's a 666, replace it with a 667.

---

**Old version (doesn't work for `666666666`)**:

```
    s='Enter number';x
  =prompt(           ''+
 s);x=+x+
(-~![]);
x=(''+x).replace('666',
666+([][         +[]]+[])
[+[]]['l         ength'[
 'repla'+       'ce'](
  / /g,'')]);alert(x)

```

To understand this, let's first beautify it:

```
s = 'Enter number';
x = prompt('' + s);
x = +x + (-~![]);
x = ('' + x).replace('666',666+([][+[]]+[])[+[]]['l         ength'['repla'+'ce'](/ /g,'')]);
alert(x);

```

Now let's remove useless things like `'' + string` and `'str' + 'ing'`, remove the unnecessary `s` variable, and change weirdness like `-~![]` into `1`:

```
x = prompt('Enter number');
x = +x + 1;
x = ('' + x).replace('666', 666+"undefined"[0]['l         ength'['replace'](/ /g,'')]);
alert(x);

```

`'l ength'['replace'](/ /g,'')` is simply `"length"`:

```
x = prompt('Enter number');
x = +x + 1;
x = ('' + x).replace('666', 666+"undefined"[0].length);
alert(x);

```

And `"undefined"[0]` is `"u"`, and `"u".length` is `1`:

```
x = prompt('Enter number');
x = +x + 1;
x = ('' + x).replace('666', 666 + 1);
alert(x);

```

Now we're done! It should be pretty easy to understand now.

# Answer
> 20 votes
# Applescript

This site doesn't have enough Applescript answers. Lets banish some demons!

```
property demon : "666"
property trinity : 1

on exorcise above possessed
    set possessed to possessed as text
    set relic to AppleScript's text item delimiters
    set AppleScript's text item delimiters to demon
    set deliverance to possessed's first text item
    if possessed is deliverance then
        set deliverance to possessed + trinity
    else
        set AppleScript's text item delimiters to trinity
        set compellingPower to ¬
            (count of possessed's characters) - ¬
            (count of deliverance's characters) - ¬
            (count of demon's characters)
        set deliverance to ¬
            deliverance & ¬
            demon + trinity & ¬
            last text item of (((10 ^ compellingPower) as integer) as text)
    end if
    set AppleScript's text item delimiters to relic
    return deliverance
end exorcise

log (exorcise above 666)
log (exorcise above 66666666)
log (exorcise above 1266612)
log (exorcise above 1212)

```

Log output:

```
(*667*)
(*66700000*)
(*1266700*)
(*1213*)

```

---

I'd wanted to get some of the more powerful quotes from The Exorcist into this, but that would have made this posted decidedly NSFW. You can read the IMDB page instead.

# Answer
> 15 votes
## Perl

You said we must not increment in a loop. I'm not using any mathematical operators at all! Here is a pure regex-substitution approach (no guarantees it's safe for your sanity).

```
#!/usr/bin/perl

$_ = <>;

s/$/ ~0123456789/;
s/(?=\d)(?:([0-8])(?=.*\1(\d)\d*$)|(?=.*(1)))(?:(9+)(?=.*(~))|)(?!\d)/$2$3$4$5/g;
s/9(?=9*~)(?=.*(0))|~| ~0123456789$/$1/g;
s/(?!^)\G\d|(666)\d/${1}0/g;
s/666/667/g;

print($_)

```

The first three substitutions increment the number by one. I did solve that problem myself once, but it included a substitution that had to be looped until no more substitutions were made, so I used Andrew Cheong's approach instead.

The fourth substitution turns all digits following a `666` into zeros. The final substitution turns the remaining `666` into a `667`.

As a bonus this will work with multiple integers in the input as long as they are separated by non-digit characters.

# Answer
> 8 votes
# LiveScript

This is bending the rules. You see, you said I must not use a loop that **adds one** until it finds a correct result. So I **subtract minus one** instead!

```
nextId = (id) ->
  while (id + 1).toString!indexOf('666') != -1
    id -= -1
  id + 1

```

A golfed version in **~~53~~ ~~48~~ 45 bytes** for fun:

```
n=(i)->(while~(i+1+'')indexOf(\666)=>i-=-1);i+1

```

Thanks to user1737909 for helping golf it further.

## Tests

Requires Node.js with the `LiveScript` npm module or a compatible assert library.

```
assert = require \assert

assert.equal nextId(1), 2
assert.equal nextId(665), 667
assert.equal nextId(665999999), 667000000
assert.equal nextId(66600), 66700
assert.equal nextId(456667), 456670

```

# Answer
> 6 votes
# Ruby

This is (I think) the first answer that works for 666666666. (Except the cheaty subtracting -1 answer. ;) )

```
x = gets.chomp.to_i + 1
p (x..x.to_s.gsub('666', '667').to_i).select{|i| !(i.to_s.index '666') }.min

```

I'm in a hurry now; explanation will be added later.

**Update**: much more efficient version (almost constant runtime I believe):

```
x = gets.chomp
if x.index '666'
    # replace ex. 6661234 with 6670000
    puts x.sub(/666(.*)/){ "667#{"0" * $1.length}" }
else
    # old algorithm (guaranteed to result in
    # 0 or 1 666s now)
    puts (x.to_i+1).to_s.sub(/666/, "667")
end

```

# Answer
> 4 votes
**PowerShell**

```
($args[0]+1 -replace '(?<=666.*).','0') -replace '666', '667'

```

# Answer
> 4 votes
# J

Finally, a good use for `E.`!

```
(({.~ , '667' {.!.'0'~ #@[ - ]) '666'&E. i. 1:) @ ": @ >:

```

In essence, we find the first position in which the argument has a full `666`, and we replace that substring and everything after with `66700000...` until the end.

Explained in detail:

* `":@>:` \- Increment by one and convert to string.
* `'666'&E.` \- Make a vector of booleans, true in each place that '666' begins in the string.
* `i.1:` \- Find the index of the first true in the vector, else return the length of the vector.
* `#@[-]` \- Length of the string (which is also the length of the vector) minus the result of `i.`.
* `'667'{.!.'0'~` \- Take a substring of '667' with a length of that result, padding on the right with '0' if necessary.
* `{.~` \- Take a substring with the length of the original result from `i.`.
* `,` \- Append the two together.

In use:

```
   f =: (({.~,'667'{.!.'0'~#@[-])'666'&E.i.1:)@":@>:
   f 1              NB. this leaves okay numbers untouched
2
   f 665999999      NB. properly handles multiple increments
667000000
   f 16266366646666 NB. only takes effect at sets of 3 sixes
16266366700000

```

And since this isn't a code golf, this doesn't have to get golfed to hell with crazy optimizations. Everybody wins!

# Answer
> 3 votes
# C#

## 148 137 chars

Was able to shave off a few chars thanks to @recursive

```
public static int f(int b){b++;var z=new Regex("666\\d*");var q=z.Replace(b+"","667",1);return int.Parse(q.PadRight((b+"").Length,'0'));}

```

Ungolfed:

```
public static int f(int b)
{
    b++;
    var z = new Regex("666[\\d]*");
    var q = z.Replace(b+"", "667", 1);
    return Int32.Parse(q.PadRight((b+"").Length, '0'));
}

```

Fiddle: http://dotnetfiddle.net/XB83bf

# Answer
> 2 votes
# Python

```
def next_id(id_num):
  id_num_p1=str(id_num+1)
  pieces=id_num_p1.split('666')
  if len(pieces)==1:
    return id_num+1
  next_id_str=pieces[0]+'667'+'0'*(len(id_num_p1)-len(pieces[0])-3)
  return int(next_id_str)

```

# Answer
> 2 votes
# Perl

```
$_++;$_.=$/;s:666(.*):667 .'0'x($+[1]-$-[1]):e

```

Inline code which changes the content inside `$_`, a pretty standard ideology in perl. Can be used in conjunction with `-p` flag like this:

```
$ perl -p % <<< 66666
66700

```

# Answer
> 2 votes
# J

No strings, loops or conditionals:

```
   next =: 3 :'<.(y+1)(+-|~)10^<:666 i:~666,1000|<.(y+1)%10^i.<.10^.>:y'

   next 1
2
   next 665
667
   next 665999999
667000000
   next 666666666
667000000
   next 66600
66700

```

Similarly to cardboard\_box's solution, this separates the number into groups of three digits by dividing by powers of ten. It uses the index of the first occurrence of 666 to round the number up appropriately.

# Answer
> 2 votes
# Haskell (70 characters)

Here is a simple implementation in Haskell.

```
import Data.List
import Data.Char

nextid :: Integer -> Integer
nextid = foldl' ((+).(*10)) 0 . purge . map digitToInt . show . (+1)
  where purge (6:6:6:xs) = 6 : 6 : 7 : map (const 0) xs
        purge (x:xs)     = fromIntegral x : purge xs
        purge []         = []

```
* Firstly, it uses `map digitToInt . show` to convert a possibly evil ID to a list of digits.
* Next, `purge` matches the evil pattern and replaces it with its good equivalent.
* Finally, `foldl' ((+).(*10)) 0` reduces the list of digits to one `Integer`.

Let's see if it works!

```
ghci> nextid 1
2
ghci> nextid 665
667
ghci> nextid 665999999
667000000
ghci> nextid 666666666
667000000
ghci> nextid 66600
66700
ghci> nextid 456667
456670
ghci> nextid 6660239486660239466
6670000000000000000

```

Looks good. And just for fun a golfed version.

```
f=read.w.show.(+1);w('6':'6':'6':t)="667"++(t>>"0");w(h:t)=h:w t;w t=t

```

# Answer
> 1 votes
# Java

Isn't it enough to do this?

```
private static int nextId(int currentId) {
    String currentIdStr = String.valueOf(currentId);
    return currentIdStr.contains("666") ? Integer.parseInt(currentIdStr.replace("666", "667")) : ++currentId;
}

```

# Answer
> 1 votes
## R

Replacing 666 with 667 works.

```
f <- function(x) {
  x <- as.integer(x + 1)
  if (grepl(666, x)) {
    k <- regexpr(666, x)
    cat(substring(x, 1, k + 1), 7, rep(0, nchar(x) - k - 2), sep = "")
  }
  else cat(x)
}

```

Results

```
> f(1)
2
> f(665)
667
> f(665999999)
667000000
> f(666666666)
667000000
> f(66600)
66700
> f(126660)
126670
> f(126661)
126670
> f(666666666)
667000000

```

# Answer
> 1 votes
***AWK***

```
awk '{i=index(++$0,"666")}
      i{a=substr($0,1,i-1)
       b=substr($0,i+3)
       gsub(/./,0,b)
       $0=a"667"b}
      1
' <<_INPUT_
1
665
665999999
666666666
66600
_INPUT_

```

gives

```
2
667
667000000
667000000
66700

```

***edit: 2nd solution***

```
awk -F666 -vOFS=667 '{++$0;$1=$1}
    NF-1{for(gsub(/./,0,$2);NF>2;--NF){$2=$2 0 0 0
               for(i=length($NF);i;--i)$2=$2 0}}1
' <<_INPUT_
1
665
665999999
666666666
66600
1236661
_INPUT_

```

yields

```
2
667
667000000
667000000
66700
1236670

```

# Answer
> 1 votes
3 Different JavaScript answers:

# 1. JavaScript (ECMAScript 6)

```
f=x=>(a=b=c=0,[c?'0':a+(a=b)+(b=i)==666?(c='7'):i for(i of ""+(x+1))].join('')*1)

```

Converts the number to a string then iterates over each character until it finds `666` then it changes that last `6` to a `7` and outputs `0` for all following characters.

# 2. JavaScript (ECMAScript 6 Draft)

Recursive function without string manipulation:

```
g=(x,y=x+1,p=1)=>y?g(y%1e3==666?y*p+p:y>x?y:x,y/10|0,p*10):x

```

Or more verbosely:

```
function g(x,y=x+1,p=1)
{
  if ( y == 0 )
    return x;
  else if ( y % 1000 == 666 )
    return g( y*p+p, Math.floor(y/10), p*10 );
  else
    return g( Math.max(y, x), Math.floor(y/10), p*10 );
}

```

Tests:

```
g(5) // 6
g(65) // 66
g(665) // 667
g(66599) // 66700
g(66666) // 66700
g(6656665665) // 6656670000

```

# 3. JavaScript

Using regular expressions:

```
function h(x)(""+(x+1)).replace( /^(.*?)(666)(.*)$/, function(a,b,c,d)(b+667+d.replace(/./g,0)) )*1

```

Or (the same but using ECMAScript 6)

```
h=x=>(""+(x+1)).replace(/^(.*?)(666)(.*)$/,(a,b,c,d)=>b+667+d.replace(/./g,0))*1

```

# Answer
> 0 votes
## Java

```
public static int f(int i) {
    i++;
    i += findAdjustment(i);
    return i;
}

private static int findAdjustment(int i) {
    if (i < 666) {
        return 0;
    }
    int adjustment = findAdjustment(i / 10);
    if (adjustment != 0) {
        // Leftmost 666 found, fix adjustment by current last digit
        return adjustment * 10 - i % 10;
    } else if (i % 1000 == 666) {
        return 1; // This is leftmost 666, need to be corrected by 1
    } else {
        return 0; // no adjustment needed
    }
}

```

Using recursive function to find leftmost 666 and calculation how much to adjust the number when popping the call stack again.

# Answer
> 0 votes
# Python:

```
def f(b):
    b = `b+1`
    while '666' in b: b = b.replace('666','667',1)
    return int(b)

```

Or:

```
 f=lambda b:int(`b+1`.replace('666','667'))

```

# Answer
> 0 votes
## Batch

Simple iterated string manipulation.

```
@echo off

setLocal enableDelayedExpansion
set /a inp=%1+1
for /f usebackq %%a in (`powershell "&{'%inp%'.length-1}"`) do (
    set a len=%%a-2
    set chars=%%a
)

for /l %%b in (0, 1, %len%) do (
    if "!inp:~%%b,3!"=="666" (
        set inp=!inp:~0,%%b!667
        set /a a=%%b+3
        for /l %%c in (!a!, 1, %chars%) do set inp=!inp!0
        goto :break
    )
)

:break

echo %inp%

```

It starts at the first three characters of the number (as a string), and works its way to the end until it finds 666, it then replaces that 666 with 667, and loops to the length of the string adding zeros.

The test cases all produce the correct results.

# Answer
> 0 votes
# Python

```
import re
def exorcise(number):
    number = str(number+1)
    i = re.compile("^(\d*?)(666)(\d*)$")
    if re.match(i,number):
        n = re.match(i,number).groups()
        return int(n[0]+"667"+"".join(["0"*len(n[2])]))
    return int(number)

```

# Answer
> 0 votes
# perl, 45 bytes

A single regex with the /e flag does all the work here:

```
$_=<>+1;s/666(.*)$/"667".0 x length$1/e;print

```

# Answer
> 0 votes
# perl, 36 just a sub, no bytes

A shorter version than my last solution, using a mix of arithmetic and regex ops.

```
sub{($_[0]+1)=~s/666(.*)/667$1/r-$1}

```

# Answer
> 0 votes
## SQL

To be precise, SQL Server 2012 Transact-SQL.

```
create function dbo.GoodIntegers( @i bigint )
returns bigint
as begin
    declare @s varchar(20) = cast( @i+1 as varchar(20) ) ;
    declare @badindex int = charindex( '666', @s ) ;
    declare @rv bigint  = cast (
        iif( @badindex = 0 ,
            @s ,
            concat( left( @s, @badindex - 1 ), '667', replicate( '0', len( @s ) - @badindex - 2 ) )
        ) as bigint
    ) ;
    return @rv ;
end ; -- function dbo.GoodIntegers

```

# Answer
> 0 votes
# Julia

```
function f(x::Int)
    y = string(x+1)
    n = length(y)
    z = string(^("0",n))
    ~ismatch(r"6{3}", y) ?
    int(y) :
    while ismatch(r"6{3}",y)
        m = match(r"6{3}", y)
        y = string(y[1:m.offset+1], '7', z[m.offset+3:n])
    end
    int(y)
end

```

REPL results

```
julia> f(1)
2

julia> f(665)
667

julia> f(665999999)
667000000

julia> f(666666666)
667000000

julia> f(66600)
66700

julia> f(456667)
456670

```

# Answer
> 0 votes
# C#

Am I doing it right

```
static int F(int n)
{
    n++;

    int a = 666;
    int b = 1;

    while (n >= b)
    {
        if (((n - a) / b) % 1000 == 0)
        {
            n += b;
        }

        a *= 10;
        b *= 10;
    }

    return n;
}

```

# Answer
> 0 votes
## vba

```
Function f(num As Long) As Long
Dim SixPos As Long
Dim s As String
s = CStr(num)
SixPos = InStr(s, "666")
If SixPos = 0 Then
    s = CStr(num + 1)
    SixPos = InStr(s, "666")
End If
If SixPos Then
    Mid(s, SixPos + 2, 1) = "7"
    If Len(s) > SixPos + 2 Then
        Mid(s, SixPos + 3, Len(s) - SixPos + 3) = String$(Len(s) - SixPos + 3, "0")
    End If
End If

f = CLng(s)

End Function

```

In action:

```
Sub demo()
Debug.Print f(1) 'returns 2.
Debug.Print f(665) 'returns 667.
Debug.Print f(665999999) 'returns 667000000 without having looped a million times.
'(Following examples added since the question was first posed.)
Debug.Print f(666666666) 'also returns 667000000.
Debug.Print f(66600) 'returns 66700.
Debug.Print f(456667) 'returns 456670.
End Sub

```

result:

```
2
667
667000000
667000000
66700
456670

```

# Answer
> 0 votes
**C**

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

int next(int a)
{
    for(int b=a+1,c=0,d=0; b>665 ;b/=10, c++)
        if(b%1000==666) {d=c; a=b;}

    a++;
    while(d --> 0) a*=10;

    return a;
}

void main(int a, char *v[])
{
    int c = a>1?atoi(v[1]):0;

    printf("%d\n",next(c));
}

```

OK - no bounds checking and far too much whitespace but it's not golf. Also a fun bit of formatting in "while (d --\> 0)".

# Answer
> 0 votes
## C++

I know this isn't code-golf, but (a) some people have suggested that it is a good golf challenge, and (b) this is my first challenge/golf answer, I thought it would be fun, and if I do this here I don't get shown up in an actual golf challenge for being a terrible golfer. X)

Basically, replaced '666' with '667' works if you do it for the first instance in the number and then write out trailing 0s.

Golfed (175 155 chars):

```
#include<sstream>
int f(int x){std::stringstream s,o;s<<++x;x=0;for(char c=s.get();!s.eof();c=s.get())o<<((x+=c=='6')++==3?'7':--x>3?'0':c);o>>x;return x;}

```

Ungolfed:

```
#include<sstream>
int f(int x){
    std::stringstream s,o;
    s<<++x;    // Increment to next int.
    x=0;       // Reusing this to count 6s
    for(char c=s.get();!s.eof();c=s.get()){    // For each digit
        if (c=='6'){
           ++x;    // Count sixes...
        }
        if(x==3) {  // Devil's number!
            c='7'; // Output 7 here.
            ++x;   // Increment once more.
        } else if (x > 3) {
            c='0';    // Already replaced 666 with 667, so write out 0s
        }
        o<<c;   // Append digit
    }
    o>>x; // Get int
    return x;
}

```

# Answer
> 0 votes
# Ruby

```
n=(gets.chomp.to_i+1).to_s
i=n.index("666")
if i!=nil
    n=n[0..i+1]+"7"+"0"*(n.length-i-3)
end
puts n

```

# Answer
> 0 votes
**PHP**, 115 characters

```
<?php
function n($n){$p=strpos(++$n,'666');return($p>=0?substr($n,0,$p). 667 .str_repeat(0,-strlen($n)+$p+3):$n);}
?>

```

ungolfed:

```
<?php
function n($n)
{
    $p = strpos(++$n, '666');

    return($p >= 0
    ?
        substr($n, 0, $p) . 667 . str_repeat(0, -strlen($n) + $p + 3)
    :
        $n
    );
}
?>

```

# Answer
> 0 votes
# Javascript (E6) 47 ~~64~~

Even if it's not golf

Assuming positive 32 bit integers. NB +a is string concat, -a is numeric sub

```
F=x=>-(~x+'').replace(/666(.*)/,(s,a)=>667+a-a)

```

**Usage**

;\[ F(6666), F(1), F(665), F(665999999), F(666666666), F(66600), F(456667) \]

```
[6670, 2, 667, 667000000, 667000000, 66700, 456670]

```

# Answer
> -2 votes
# PHP

```
echo preg_match('/666/', $n+1)?preg_replace('/666/', '667', $n+1):$n+1;

```

---
Tags: popularity-contest, generation, counting
---


title: Convert JSF**k to normal JS

text:
# Question
Title: Convert JSF**k to normal JS
Many of you already know JSF\**k. For those who don't, it's a script that basically turns any JavaScript code into something written using only `[]()!+`.

Your task is to build, using any language of your choice, a program which converts JSF\**k into unobfuscated JavaScript.

* **Input**: A string with valid JSF\**k code.
* **Output**: A string with the regular JavaScript code that has been previously JSF\**ked to generate the input.

For this challenge, consider that the input string has only been JSF\**ked once.

This is a contest, so the shortest code, in bytes, wins.

# Answer
# Javascript - 68 55 51

```
alert(/\n(.+)/.exec(eval(prompt().slice(0,-2)))[1])

```

Alternatively: (same length)

```
alert(/.+(?=\n})/.exec(eval(prompt().slice(0,-2))))

```

Runs in the console of your browser. Only guaranteed to work with code generated by jsfuck.com with the 'Eval Source' option ticked.

Ungolfed:

```
alert(
    /\n(.+)/.exec(                 // regex to extract code from inside outer function braces {}
        eval(prompt().slice(0,-2)) // remove the final set of parens () and evaluate the code
                                   // this results in a function, which will be converted to a string as 'exec' expects a string
    )[1]                           // get the first capture group
)

```
> 14 votes

# Answer
# JavaScript, 122, works with any input

```
s=prompt().slice(0,-2)
i=s.length
while(i--){if((l=s.slice(i)).split(')').length==l.split('(').length)break}alert(eval(l))

```

Pretty simple; it just goes back in the string until the parentheses (`(` and `)`) are balanced. The last three characters of the JSF output are *always* `)()`, so slicing off the last 2 parens and then finding the matching paren for the other will always work. (It works with input with `[]` too.)
> 7 votes

---
Tags: code-golf
---


title: Pi language interpreter

text:
# Question
Title: Pi language interpreter
# Introduction

From Esolangs.org :

> **Pi** is based on the brainfuck language and uses the same instructions as it. Pi works by calculating pi digits and introducing errors in some random digits of them, encoding obfuscated brainfuck instructions. Instructions are encoded as below:
>
> ```
> '>' '<' '+' '-' '.' ',' '[' ']'
>  0   1   2   3   4   5   6   7   8
>
> ```
>
> But, as we need to identify which pi digits are incorrect, we move each instruction in the table one position to the right starting at the position that is initially over the correct pi digit that is where we are inserting the instruction. For example, if the pi digit in the position we are inserting the instruction is 4, the table would be moved as follows:
>
> ```
> '>' '<' '+' '-'     '.' ',' '[' ']'
>  0   1   2   3   4   5   6   7   8   9
>
> ```
>
> Then the instruction would be converted to a digit that would be inserted replacing the correct digit.

# Brainfuck explanation

Brainfuck is not very difficult.
Imagine an infinite byte array, initialized to zero, and a pointer on a value of this array.

* `>` increments the pointer
* `<` decrements the pointer
* `+` increments the pointed value
* `-` decrements the pointed value
* `.` prints the pointed value
* `,` sets the pointed value (value is taken from stdin)
* `[` defines the beginning of a loop, this loop is entered if current value is not zero
* `]` is the end of the loop

# Objective

In any language, write an interpreter for the esoteric **Pi** language.

* Correct pi digits must be taken from `http://pastebin.com/raw.php?i=gUbdbzLr`, no URL shortener allowed. (JavaScript is allowed to run from pastebin.com domain but the full URL must appear in the code)
* Only `[]<>+-.` equivalent have to be handled, you can ignore inputs (`,` equivalent)
* The input string length will be below 100,000
* You can write a full program and take the input string from stdin, or write a function and take the input string from argument.
* You don't have to support *inifinite* array (100 bytes is fine), but you have to support negative pointers.
* In case of overflow, wrap the value : `-1 => 255` and `256 => 0`.

# Examples

```
3.14159265358979323842264332327250288412716939927513582397492459230721640628220899867803480534311206298214838653322233664709084463955358323172235940832848311725028410370193853110525964460294895293032196422880097562591344612147514823378178346528120090214562856642346134861345532264821332360736034914137372428700663631558417448152392396222925459170536432789259026051133013014882046252138214295194153160243205227036275959395309212613732192261379310211855807440237946274952735182575273489122743848301134912983467436444065634308652133494633522473749030217386093370277033921317659317670238267581846066440

```

This input value must return `Hello World!`

```
3.14152322358878323222264326032220288236031386837182584807480228230223643448624338864343482343244432222334808651322320664708322260855054333172535843232848113435028410274433852444334335

```

Taken from here and converted to Pi, outputs `6*7=42` (don't forget to upvote this awesome answer)

```
3.1415826535887832384626433832785028846644334334334433443333333344433433434334433333434470302114801731130077382277380418061543333433343344443434333434433344433344334443443702032238007311300810737227041222326030211380073113008107373170312223223233332323222222222322232222332222324738807122323233223233222322223322322322223222232332332443434334343434352222232232233332232232222332222332225222232232332322223223232222222232223233223344343443443344434433334333344333343333334343333343433344433434344443334433443344432232222223223332222222223322223232333222232222332232223323223223222232222222322222243434444443335434534343343433333344343333333434343434333443333343444433343444333333334353232233222223222322233322223333323332232223222323222322322222232322232322323335333333334453423522233222232232344334433335722222764333434443343444434344333334434343444334348644444433433343333333444434343443434333334334443704811648806122222233222232222232222222222232222232222232233444433433444443442222333222323322333222223223223333225222223222222223222232322223232332233222332253333333343443333443344333443334343334443433333334343334343333343433444433343433422223223222232222222222222323223232332322332233223322222323332222232322222322233322354343343333335333533333433333334334333333433334434333433334434333334334333344344443334442223233322233233222223323223223233222333222232233222222233222222223222323223234434333443443432422232223322232353344433434654434444334732222222324737038217381103711688856808272107

```

This one is taken from my answer here and can be used to test input if you decide to handle it.

# Winning criteria

This is a , lowest score wins !

### Score computation :

* 1 byte = 1 point
* +100 points if you choose to take the pi digits from a local file.
* -50 points if you handle inputs (`,`) too (single ASCII character per input; if your language does not support STDIN, prompt for input once and then read a character at a time from that input).
* -100 points if you compute the pi digits yourself.

# Answer
> 2 votes
## Mathematica, 362 bytes - 100 (π) = 262

```
f=(c=Which[#>#2,#,#<#2,#+1,0<1,9]&@@@Thread@{d=(r=RealDigits[##][[1]]&)@#,r@@{Pi,10,(g=Length)@d}};b=0&~Array~100;l=b[[#]]&;p=50;i=0;j={};While[++i<=g@c,{++p&,--p&,++b[[p]]&,--b[[p]]&,j~AppendTo~FromCharacterCode@l@p&,0&,If[l@p>0,j~PrependTo~i,d=1;While[d>0,Switch[c[[++i]],7,++d,8,--d]]]&,If[l@p>0,i=j[[1]],j=Rest@j]&,0&}[[c[[i]]]][];b[[p]]=l@p~Mod~256];j<>"")&

```

I didn't look at the other Mathematica solution at all to write this. If I hardcode the input variable (which the other answer currently does), I'll save another 5 characters.

This snippet defines a function `f` though, which takes the input as a string, like

```
f = (c = Which[# > #2, #, # < #2, # + 1, 0 < 1, 9] & @@@
     Thread@{d = (r = RealDigits[##][[1]] &)@#,
       r @@ {Pi, 10, (g = Length)@d}};
   b = 0 &~Array~100;
   l = b[[#]] &;
   p = 50;
   i = 0;
   j = {};
   While[++i <= g@c,
    {
       ++p &,
       --p &,
       ++b[[p]] &,
       --b[[p]] &,
       j~AppendTo~FromCharacterCode@l@p &,
       0 &,
       If[l@p > 0,
         j~PrependTo~i
         ,
         d = 1;
         While[d > 0,
          Switch[c[[++i]],
           7, ++d,
           8, --d
           ]
          ]
         ] &,
       If[l@p > 0,
         i = j[[1]],
         j = Rest@j] &,
       0 &
       }[[c[[i]]]][];
    b[[p]] = l@p~Mod~256
    ];
   j <> "") &

```

# Answer
> 3 votes
# PHP, 532 - 50 = 482

```
<?php $P=file_get_contents("http://pastebin.com/raw.php?i=gUbdbzLr");$I=trim(fgets(STDIN));$i=2;$l=strlen($I)-1;$A=$R=array_fill(0,999,0);$a=$r=0;while($i<$l){$X=intval($I[$i]);$Z=intval($P[$i]);if($X==$Z){$i++;continue;}$O=($X>$Z)?$X-1:$X;switch($N[$X]){case 0:$A[$a]=($A[$a]+1)%256;break;case 1:$A[$a]-=$A[$a]==-1?-256:1;break;case 2:$a+=$a==998?-998:1;break;case 3:$a-=$a==0?-998:1;break;case 4:echo chr($A[$a]);break;case 5:$A[$a]=fgetc(STDIN);break;case 6:$R[$r++]=$i;break;case 7:$A[$a]==0?$R[$r--]=0:$i=$R[$r-1];break;}$i++;}

```

`allow_url_fopen` should be 1. Run this in command line like `php 28718.php`, because it takes input from STDIN.

Array size is 999. It handles negative pointers, overflow, and `,`. So I can get -50 points.

Tested with the code above, and

```
3.14159265358979323846262338227250282419716929927510782090492459233781640638623899262833482534311206728234808621328230264709314460935058223872535941812844111745008410220193853110552964262292895493028192443881097266523344712047564223378672316522123190934562856693346034261045422624821339160726424914827372058703665631558217288153092396282225439171532436789559536003133023024882044652108412695192151163943305737036565959095309212611738393261379210511254207426237992274952735388572272489222793813301174910983367536244265624308632129494679502473713070247986034370277453921711629317375838467480846766440513202056822724526351082178577132275778260917362717672046844093122295323014624928531103079228968920892354501995011202902196586203421812981362477473130996451870724134999399337297803995104973473281603634859504445345544690330263252250825304468003522193158817101

```

from http://blog.progopedia.com/2011/mar/14/pi-programming-languages/. Can I have more test code?

## Readable

```
<?php
// get pi digits
$P = file_get_contents("http://pastebin.com/raw.php?i=gUbdbzLr");

// input
$I = trim(fgets(STDIN));
$i = 2;
$l = strlen($I)-1;

// bf init
$A = $R = array_fill(0, 999, 0);
$a = $r = 0;

while($i < $l) {
  $X = intval($I[$i]);
  $Z = intval($P[$i]);
  if($X == $Z) { $i++; continue; }

  // operations
  $O = ($X > $Z) ? $X - 1 : $X;

  // bf process
  switch($O) {
    case 0: $a += $a == 998 ? -998 : 1; break;
    case 1: $a -= $a == 0 ? -998 : 1; break;
    case 2: $A[$a] = ($A[$a] + 1) % 256; break;
    case 3: $A[$a] -= $A[$a] == -1 ? -256 : 1; break;
    case 4: echo chr($A[$a]); break;
    case 5: $A[$a] = fgetc(STDIN); break;
    case 6: $R[$r++] = $i; break;
    case 7: if($A[$a] == 0) $R[$r--] = 0; else $i = $R[$r-1]; break;
  }
  $i++;
}

```

# Answer
> 3 votes
**Update 2 (on hold)**

This code does not accommodate nested loops. Under revision.

Mathematica: 415 (bytes) - 100 (pi -- apparently this counts) - 50 (input) = 265

Handles overflow, only prompts user once when first `,` is encountered.

```
v@u_ := (
  f = RealDigits[##][[1]] &;
   q@x_ := q@x = 0;
   r@x_ := q@x~Mod~256;
   z = Length;
   n = Input;
   k = StringSplit[#, ""] &;
   i = k["><+-.,[]"][[If[#1 < #2, #1 + 1, #1]]] & @@@
     Select[Transpose@{d = f[u], f[Pi, 10, z@d]}, ! Equal @@ ## &];
   j = 1;
   p = 1;
   y = 1;
   w = 1;
   FromCharacterCode@
    Last@Reap@
      While[j <= z@i,
       Switch[i[[j]], "[", l = j, "]", If[r@p != 0, j = l - 1], ">",
        p++, "<", p--, "+", q[p]++, "-", q[p]--, ".", Sow[r@p], ",",
        If[y-- == 1, c = k@ToString@n[]];
        q@p = ToCharacterCode[c[[w++]]][[1]]]; j++]);

```

**Original**

Mathematica: 439 bytes - 50 (input) - 100 (pi calc) = 289. Updated to accept interactive input at start.

Readable:

```
in = StringSplit["><+-.,[]", ""][[#]] &;
c = Input[];
s1 = Cases[
  SequenceAlignment[
    (rd = RealDigits)[
      N[Sum[(i!)^2*2^(i + 1)/(2 i + 1)!, {i, 0, Infinity}],
     StringLength@c - 1]][[1]],
    rd[ToExpression@c][[1]]] /. {{r_}, {w_}} :>
     in@If[r > w, w + 1, w], _String] //. {h___, "[", b___, "]",
       t___} :> {h, {b}, t};
p = 1;
rt[x_] := rt[x] = 0;
sc[l_] :=
  Scan[Switch[#, ">", p++, "<", p--, "+", rt[p]++, "-", rt[p]--, ".",
     Sow[rt[p]], ",", Input[], lp_List, While[rt[p] != 0, sc[#]]] &, l];
FromCharacterCode@Last@Reap@sc@s1

```

> {"Hello World! "}

Dense:

```
in=StringSplit["><+-.,[]",""][[#]]&;c=Input[];s1=Cases[SequenceAlignment[(rd=RealDigits)[N[Sum[(i!)^2*2^(i+1)/(2 i+1)!,{i,0,Infinity}],StringLength@c-1]][[1]],rd[ToExpression@c][[1]]]/.{{r_},{w_}}:>in@If[r>w,w+1,w],_String]//.{h___,"[",b___,"]",t___}:>{h,{b},t};p=1;rt[x_]:=rt[x]=0;sc[l_]:=Scan[Switch[#,">",p++,"<",p--,"+",rt[p]++,"-",rt[p]--,".",Sow[rt[p]],",",Input[],lp_List,While[rt[p]!=0,sc[#]]]&,l];FromCharacterCode@Last@Reap@sc@s1

```

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


title: Regex that matches any regex

text:
# Question
Title: Regex that matches any regex
Your task is to write a regular expression that matches *any valid regular expression* and no invalid expression.

You may pick any regex flavour for your answer, but you have to match regular expressions of that *same* flavour.

This is regex-golf, so the shortest regex wins.

You can't invent your own regex language for this. That would be an example of a standard loophole.

# Answer
> 10 votes
# Not possible in Ruby!

I wanted to write a regular expression in Ruby that matches valid regular expressions in Ruby, but I must conclude that writing one is not possible.

At first, Ruby seems like a good choice. If I want to check for matching parentheses, I can write a recursive expression like `(?<mparen>([^()]|\(\g<mparen>\))*)` where *mparen* matches zero or more things that are either not parentheses, or are a set of parentheses with *mparen* inside.

So I listed things that are valid and not valid in Ruby regular expressions. Then I found things that I cannot check with regular expressions.

## Empty ranges of characters

In Ruby, `[a-b]` is a valid, but `[b-a]` is not valid, because `a` comes before `b`. This rule is common to several flavors of regular expressions:

```
$ ruby21 -e '/[b-a]/'
-e:1: empty range in char class: /[b-a]/
$ perl -e 'qr/[b-a]/'
Invalid [] range "b-a" in regex; marked by <-- HERE in m/[b-a <-- HERE ]/ at -e line 1.
$ sed '/[b-a]/!d'
sed: 1: "/[b-a]/!d": RE error: invalid character range

```

So how do I write a regular expression that matches `a-b` but not `b-a`, and works with any range? I can't.

I would like to write `(?<begin>.)-[\k<begin>-z]` using a backreference to the first character. This would become `a-[a-z]` or `b-[b-z]` or so on. (Later I would change `z` to the highest character, but for now I test lowercase letters.) This fails because I can't use backreferences in ranges! `[\k<begin>-z]` is the same as `[<>-z]`, as the range `>-z` includes the letters `begkin`.

I can write in 202 characters:

```
a-[a-z]|b-[b-z]|c-[c-z]|d-[d-z]|e-[e-z]|f-[f-z]|g-[g-z]|h-[h-z]|i-[i-z]|j-[j-z]|k-[k-z]|l-[l-z]|m-[m-z]|n-[n-z]|o-[o-z]|p-[p-z]|q-[q-z]|r-[r-z]|s-[s-z]|t-[t-z]|u-[u-z]|v-[v-z]|w-[w-z]|x-[x-z]|y-[yz]|z-z

```

This covers 26 lowercase letters, but only in their literal forms. Octal and hex escapes are also part of the regular expression syntax. Now `a` is also `\141` and `\x61`, and `z` is also `\172` and `\x7a`. My regular expression would need to match `\141-\172` and `\x61-\x7a`, and also `a-\172` and `\x61-z` and so on.

```
(a|\\141|\\x61)-([a-z]|\\1(4[2-7]|[5-7][0-7])|\\x(4[1-9a-fA-F]|[5-7]\h))

```

I would not try to extend this to the 1112064 codepoints of Unicode.

## Missing capture groups

A regular expression is not valid if it has a backreference to an undefined capture group. For example, `(?<a>)\k<b>` is not valid because it has no capture group *b*. So, my regular expression for valid regular expressions would need to check `\k<b>` against the set of valid names. I can't think of a way to do this in one regular expression.

The answer is not `(?<=\(\?<b>.*)\\k<b>`. This would use the lookbehind feature to match `\k<b>` if there was a `(?<b>` earlier in the string. It fails because variable quantifiers like `*` are not valid in lookbehind expressions.

Another problem happens with subexpression calls. It is valid for two capture groups to share the same name, but it is not valid for a subexpression call to use a multiplex name. So `(?<a>)(?<a>)` is valid but `(?<a>)(?<a>)\g<a>` is not.

## Encoding troubles

A valid regular expression must also be valid in its character encoding. If the encoding is UTF-8, then `\xc4\x80` is valid but `\x80\x80` is not. My regular expression for regular expressions would also need to validate UTF-8. It is valid to mix octal and hex escapes, so `\xc4\200` and `\304\x80` are valid too.

Ruby has other encodings. My regular expression would also need to validate EUC-JP, Windows-31J, GB18030, and every other ASCII-compatible encoding known to Ruby. That's not possible! My regular expression can't know which encoding to validate.

Is `\200` a valid regular expression? `Regexp.new '\200'.encode('binary')` is valid, but `Regexp.new '\200'.encode('utf-8')` is not valid. My regular expression can't see the encoding tag. It can only see the four ASCII characters in `\200`, so it can't decide whether `\200` is valid.

I might fix this if I decree that my regular expression for regular expressions only works with one encoding. I might pick 'us-ascii', which has only 128 characters. This does not fix my problem with capture groups.

---
Tags: code-golf, regular-expression
---


# Question
Title: Write a Vim command that reads as English text
Once you grok vi, your muscle memory learns tricks like `ggVGx` to delete all the text in a file. Trouble is, `ggVGx` is not an English word, so it makes a terrible mnemonic.

This challenge is about constructing a single Vi\[m\] command that can be reasonably read as an English word, phrase or sentence. One point per letter.

Modifier keys such as `meta`/`alt`, `control`, and `shift` should be written as they are in VimScript, e.g. `<C-c>` so we can read them, but will be pronounced as two consecutive letters: `cc`, for a score of 2.

Vim commands that start with `:` are only count toward your scrore if they build a word out of non-words. So `:%s/aword/anotherword/gi` would only add 3 to your score, for `sgi` (and only then if `sgi` is part of an actual English word or phrase, such as `hasgills`. Similarly `:help` would add zero to your score.

No user-defined mappings. Your answer should work on a fresh install of Vim with no .vimrc or other gizmos.

Finally, the command has to do something other than throw an error.

Example Entry:

# cap (3)

`cap`, change a paragraph

# Answer
> 10 votes
Score 60

`:s/foo/bar/incerepellingliceingreeceIgrillripeninggreenpepperinniceice`

> since repelling lice in Greece I grill ripening green pepper in nice ice

You can repeat flags arbitrarily in the `:s` command so this can get as long as you care to come up with a sentence/phrase/word using only the letters c,e,g,i,I,n,p,l,r and starting with an s.

# Answer
> 5 votes
`I think this a really cheesy answer.`

Prints " think this is a really cheesy answer.", score of 36. If you count "anything typed in insert mode" as one point, we can construct arbitrarily long cheesy strings like this:

`I think really cheesy answers are accidents. No really, they're accidents. I mentioned they're accidents, right?`

Where each cc in "accident" is the `<Ctrl-C>` insert mode command. The following i puts us back in insert mode for an additional two characters whenever we write "accident". If we have to end in normal mode, we can finish the paragraph with:

`But I really like soccer!`

Which leaves insert mode, moves to the end of the last word, and replaces the last character with a !.

# Answer
> 4 votes
Vim's text objects provide a variety of three-letter words (of which `cap` is one).

```
grep -E '^[cdv][ai][wspbt]$' /usr/share/dict/words

```
* `cab`
* `cap`
* `cat`
* `caw`
* `cis`
* `cit`
* `dab`
* `dap`
* `das`
* `dat`
* `daw`
* `dib`
* `dip`
* `dis`
* `dit`
* `vas`
* `vat`
* `vaw`
* `vip`
* `vis`

I only found one four letter command that is a word:

* `guib`

I opted not to include insert mode commands such as `a`, `r`, `s` where the remainder of the "word" is just text typed into the document. Otherwise, you would have to accept *any* word starting with one of those letters.

# Answer
> 4 votes
Haven't spent much time, but found at least one 6-letter word which is a valid command: toggle (go to next letter 'o', then jump to beginning of file, then second line and to the end of a first word there). I am sure there could be a lot of other words combined from movement commands.

Found another one. This one at least does something (and is 7 letters): forgery (go to 'o', replace with 'g', go to end of word, replace with 'y').

More words and phrases:

```
Brand new
Entangled<space>
Su<cc>ulents

```

---
Tags: code-bowling, vim
---


# Question
Title: Write biSp in point-free form using as few terms as possible
The Haskell function `biSp` has type signature

```
biSp :: (a -> c) -> (b -> d) -> (c -> d -> e) -> a -> b -> e

```

and (for those who prefer combinator calculus) can be defined as

```
biSp g h f x y = f (g x) (h y)

```

Your task is to implement `biSp` in point-free form (equivalently: as a combinator without any lambdas) using only two primitives:

```
(.) :: (b -> c) -> (a -> b) -> a -> c
flip :: (a -> b -> c) -> b -> a -> c

```

or

```
(.) f g x = f (g x)
flip f x y = f y x

```

For those with a background in combinator calculus, these are respectively the B and C combinators.

You may define helper functions so long as they are point-free. Your score is the total number of terms in all right-hand-side expressions.

### Testing

You can test a Haskell solution without installing any software using Ideone. By providing an explicit type alongside the definition you ensure a compile-time error if the function is incorrect. E.g. using the `:pl` reference implementation (online demo):

```
biSp :: (a -> c) -> (b -> d) -> (c -> d -> e) -> a -> b -> e
biSp = flip . ((flip . ((.) .)) .) . flip (.)
main = putStrLn "Compiled ok"

```

# Answer
> 8 votes
# 7 terms

We again define a helper combinator `BBQ = B B (C B)`, which has reduction rule

```
BBQ w x y z = x y (w z)

```

Then `biSp = BBQ BBQ BBQ`

```
  BBQ BBQ BBQ g h f x y
= BBQ g (BBQ h) f x y
= BBQ h f (g x) y
= f (g x) (h y)

```

Online demo

By brute force, this is the only 7-term solution and there is no smaller solution.

### 8 terms

There are a handful of 8-term solutions. Firstly, the obvious

```
C BBQ BBQ BBQ

```

which reduces in one step to `BBQ BBQ BBQ`.

Then there are three solutions of the form `X X X` with a five-term `X`:

* `X = B (B B) C B` which reduces in one step to `BBQ`
* `X = C B (C B) B` which reduces in one step to `BBQ` and allows the further extraction, for no net gain or loss, of a helper combinator `Q = C B`
* `X = C (B C (B B))`

There is one solution of the form `X X` with a six-term `X`:

* `X = C B (B B (C B))` (again, with an equivalent version which extracts `Q = C B`)

And there is one solution which can only be written in 8 terms with two helper combinators:

```
Q = C B
X = Q (Q Q B)
biSp = X X

```

# Answer
> 3 votes
## 9 terms

Define a helper combinator `BBQ = B B (C B)`, which has reduction rule

```
BBQ w x y z = x y (w z)

```

Then we have three options:

1. `C (B B BBQ) BBQ`
2. `B (C B BBQ) BBQ`
3. `C (B (C BBQ) BBQ)`

To show the equivalence of the first two:

```
  C (B B BBQ) BBQ g h f x y
= B B BBQ g BBQ h f x y
= B (BBQ g) BBQ h f x y

  B (C B BBQ) BBQ g h f x y
= C B BBQ (BBQ g) h f x y
= B (BBQ g) BBQ h f x y

```

We can then continue:

```
= BBQ g (BBQ h) f x y

```

That then gives the equivalence with the third:

```
  C (B (C BBQ) BBQ) g h f x y
= B (C BBQ) BBQ h g f x y
= C BBQ (BBQ h) g f x y
= BBQ g (BBQ h) f x y

```

Finally

```
= BBQ h f (g x) y
= f (g x) (h y)

```

In Haskell this is (picking one of the options):

```
bbq = (.) (.) (flip (.))
biSp = flip ((.) (.) bbq) bbq

```

Online demo

# Answer
> 3 votes
## 9 terms

This uses an intermediate combinator which I shall call `Par` for *parity*, because of the way it groups its arguments. `Par = B C (B B)` has reduction rule

```
Par w x y z = (w y) (x z)

```

Then `biSp = C (B Par (C Par))`. To demonstrate:

```
  C (B Par (C Par)) g h f x y
= B Par (C Par) h g f x y
= Par (C Par h) g f x y
= C Par h f (g x) y
= Par f h (g x) y
= f (g x) (h y)

```

In Haskell this is

```
par = (.) flip ((.) (.))
biSp = flip ((.) par (flip par))

```

Online demo

# Answer
> 1 votes
## 10 terms

```
         1  2     3  4   5  6   7  8   9  10
biSp = flip . ((flip . ((.) .)) .) . flip (.)

```

Another reference solution, that from ghci-on-acid's `:pl` command.

# Answer
> 0 votes
**10 terms**

```
        1   2    3   4   5    6   7   8
biSp = cf ((.) (cf ((.) (.))) . flip (.))

      9   10
cf = (.) flip

```

***Another 10 term solution***

```
        1   2  3  4  5  6 7  8
biSp = fc ((.) . fc) . fc . fc

       9  10
fc = flip (.)

```

---
Tags: restricted-source, atomic-code-golf, functional-programming, haskell, combinatory-logic
---


title: Saying a number in the shortest way

text:
# Question
Title: Saying a number in the shortest way
A string of digits (positive integer) can be converted to plain English in various ways. For instance, 115 can be read as "hundredfifteen", "oneonefive", "elevenfive", "twoonesfive". So question's challenge is to output the shortest string representation for a given digits string.

Rules:

* The input string can start with a zero and the output should account for that.
* Maximum length of input is 18. So you deal with numbers less than a Quintillion.
* You should use only the following mathematical words for numbers in your output: zero, one, ..., nine, ten, eleven, ..., twenty, ..., ninety, hundred, million, billion, trillion. You can use their plural forms for sequences (i.e. "fivetens" for 1010101010). No synonyms (i.e. "oh" for 0) or slang (i.e. legs for 11) are allowed. You don't need to include a "one" prefix for cases like 100, just "hundred" is fine.
* You don't need to put spaces between different words in your output.
* The output shouldn't be ambigous. This means, from the output string one should be able to determine the input unambigously. So for 705 you can't output "seventyfive" since it may be the output of 75 also. You may use "and" if that'll remove ambiguity, otherwise you don't need to include "and" in your output.
* Winner is the entry that will have the shortest code length excluding import statements and if not some user finds out a deficit in the code (i.e. a shorter representation than the program spits out for a particular input ).
* Please post your output for the following test cases to make evaluation easier: 1234, 00505, 122333, 565577555555666888, 1000010, 10001000, 10101010.
* No reading from an input file, so usage of a dictionary or hash map should count towards your code length.

**edit1**: Changed the competition type to code-golf per comments and added test cases.

**edit2**: Restricted the words that can be used in the output. Thanks to @PeterTaylor for the examples.

# Answer
# 4

This is cheeky and a cheat. I wrote this script about a year ago based off of this comic (tad of profanity).

The idea goes like this. Given any number as a string, adding the number of characters will eventually condense to 4. `Four` itself is 4 letters long and thus the end of the line.

For example:

* 10 -\> 'ten'
* 'ten' -\> 3 (letters long)
* 3 -\> 'three'
* 'three' -\> 5 (letters long)
* 5 -\> 'five'
* 'five' -\> 4 (letters long)

I verified up to 100,000. Very hacky but got the job done:

```
to20 = [
        'zero'
        ,'one'
        ,'two'
        ,'three'
        ,'four'
        ,'five'
        ,'six'
        ,'seven'
        ,'eight'
        ,'nine'
        ,'ten'
        ,'eleven'
        ,'twelve'
        ,'thirteen'
        ,'fourteen'
        ,'fifteen'
        ,'sixteen'
        ,'seventeen'
        ,'eighteen'
        ,'nineteen'
        ]

by10s = ['twenty'
         ,'thirty'
         ,'forty'
         ,'fifty'
         ,'sixty'
         ,'seventy'
         ,'eighty'
         ,'ninety'
         ]

by10powers = [
             'hundred'
             ,'thousand'
             ]

def cosmetize(number):

    # the number is too damn high!
    if number >= 100000:
        return "Too high"

    numstr = str(number)

    # Do ones
    if number < 10:
        return to20[number]

    # Pshh.. who needs zero anymore?
    to20[0] = ''

    # Do tens
    numstr10 = numstr[-2:]
    if int(numstr10) < 20:
        numstr10 = to20[int(numstr10)]
    else:
        numstr10 = by10s[int(numstr10[0])-2] + to20[int(numstr10[1])]
    if number < 100:
        return numstr10

    # Do hundreds
    numstr100 = numstr[-3]
    if numstr10 == '':
        numstr10 = ""
        numstr100 = to20[int(numstr100)] + by10powers[0]
    elif int(numstr[-2:]) > 19:
        numstr100 = to20[int(numstr100)] + by10powers[0]
        numstr100 += 'and'
    else:
        numstr100 = 'and'
    if number < 1000:
        return numstr100 + numstr10

    # Do thousands
    numstr1000 = numstr[:-3]
    if numstr100 == 'hundred':
        numstr100 = ""
    if int(numstr1000) < 20:
        numstr1000 = to20[int(numstr1000)] + by10powers[1]
    else:
        numstr1000 = by10s[int(numstr1000[0])-2] + by10powers[1]

    return numstr1000 + numstr100 + numstr10

i = 0
mx = []
z = 0
while i < 100000:
    length = cosmetize(i)
    x = [length]
    while not len(length) == 4:
        length = cosmetize(len(length))
    i += 1

# No inifinite loop? what magic is this?
print "OMG"

```
> 7 votes

# Answer
# Python - (191 - 38) = 153 bytes

This code has the worst case length of 18 for input of `000000000000000000`. I'm not sure if this is system dependant. If it's not, I could remove a couple characters.

```
from string import*
from math import*
s=digits+lowercase+uppercase
c=raw_input()
b=len(s)
a=int(c)
print'-'*(len(c)-len(c.lstrip('0')))+''.join(s[a/b**i%b]for i in range(int(log(a,b)),-1,-1))

```

For the last line I have to give credit to this fellow. Example outputs:

```
> 1234
9j
> 00505
--3Z
> 122333
6Vn
> 565577555555666888
5haShÄøŠé
> 1000010
êÌõ
> 10001000
48Šõ
> 10101010
4ewª

```

Disclaimer: This answer is not a serious answer and it's not trying to compete. This is taking advantage of ambiguity of the rules.
> 2 votes

---
Tags: code-golf, number, optimization
---


title: Frogger-ish game

text:
# Question
Title: Frogger-ish game
How about giving the good ol' arcade game Frogger a revival, Code Golf-style!

Your task is to create a version of this classic game, with as few characters of code as possible. Use the language of your choice (libraries, like *jQuery* etc., are allowed).

## Requirements

* You have 3 lives, and lose 1 life from:
    + moving outside the game scene.
    + getting hit by a vehice.
    + jumping in to water.
    + jumping to an already occupied home.
    + running out of time.
* The frog moves with arrow keys.
* There is a bug "teleporting" with set intervals between the five homes (the spaces between the grass at the top).
* You get *10* points when moving a step forward, *200* bonus points when catching a bug and *500* points when reaching an empty home.
* A timer ticks down, faster every level (the vehicles, frogs and logs should move faster as well each level).
* There should be 5 lanes of vehicles, and 3 lanes with logs and 2 with turtles.
* Each lane should move in a randomly chosen speed (within reasons).
* When an available home gets occupied, a frog appears at the starting point and you control that one from that point.
* When all five homes have been occupied, the timer restarts and the homes become empty. When the game ends, points from all levels are calculated and shown.

## Additional info

Start screen, music and highscore table is not needed. You also don't need to mimic the design to the pixel. Want it black and white? Want it really minimalistic? Or a cube instead of a frog or car? Works fine! Just keep the code tight. Shortest code wins!

# Answer
> 3 votes
# Python 3.3 - Ungolfed

I have not golfed this at all, as I was more interested in just getting a good-looking game working first. I am actually totally new to Tk, so if anyone has any suggestions, I would really appreciate them. The speeds now work properly. Let me know if you would like to see additional features, e.g. colors.

## Code

```
import tkinter as tk
import queue
import random

class Lane():
 def __init__(self, row=-1, lanetype="none", direction=0, speed=0, width=0, maxnumber=0, replenish=0, length=0, gap=0):
  self.row = row
  self.type = lanetype
  self.direction = direction
  self.speed = speed
  self.width = width
  self.maxnumber = maxnumber
  self.replenish = replenish
  self.length = length
  self.gap = gap
  self.lanelastupdate = 0
  self.objects = []
  if(self.type == "car"):
   for index in range(self.width):
    if(len(self.objects) == self.maxnumber):
     break
    if((self.maxnumber - len(self.objects) == self.width - index) or random.random() < self.maxnumber/self.width):
     self.objects.append([index*self.direction + int((self.width-1)/2 - (self.width-1)*self.direction/2), self.row])
  if(self.type == "log" or self.type == "turtle"):
   if(self.direction == 1):
    start = 0
   else:
    start = self.width - 1
   lengthcounter = 0
   gapcounter = 0
   for index in range(self.width):
    if(lengthcounter < self.length):
     self.objects.append([start + index*self.direction, self.row])
     lengthcounter += 1
    else:
     gapcounter += 1
     if(gapcounter == self.gap):
      lengthcounter = 0
      gapcounter = 0
 ### end of __init__ ###
### end of Lane class ###

class Frogger():
 def __init__(self):
  # configure 'global' variables
  self.directions = ['Up', 'Down', 'Left', 'Right']
  self.width = 25
  self.height = 13
  self.frogstart = [12, 12]
  self.pointsforup = 10
  self.pointsforhome = 500
  self.pointsforbug = 200
  self.timerthreshold = 1000
  self.timerstart = 60
  self.speedchange = 2
  self.waterbordertop = 1
  self.waterborderbottom = 5
  self.minspeed = 10
  self.maxspeed = 15
  self.minbugspeed = 50
  self.maxbugspeed = 100
  self.timerspeed = 20

  # configure program state variables
  self.q = queue.Queue(maxsize=1)
  self.updateticks = 0

  # configure game variables
  self.gameover = False
  self.speedup = 0
  self.timer = self.timerstart
  self.lives = 3
  self.score = 0
  self.frogposition = [0, 0]
  self.frogposition[0] = self.frogstart[0]
  self.frogposition[1] = self.frogstart[1]
  self.highest = 12
  self.movedup = False

  # configure the lanes of cars, logs, and turtles
  self.init_lanes()

  # configure the homes and the bug
  self.init_special()

  # configure TK window
  self.root = tk.Tk()
  self.label = tk.Label(text="Score: "+str(self.score)+" Lives: "+str(self.lives)+" Time: "+str(self.timer))
  self.label.pack()
  self.text = tk.Text(self.root, width=self.width, height=self.height, font=("Courier New", 14))
  self.text.bind("<Key>", self.key_event)
  self.text.focus_set()
  self.text.pack()

  # configure drawing sprites
  self.init_sprites()

  # run the game
  self.update_clock()
  self.process_world()
  self.root.mainloop()
 ### end of init ###

 def init_sprites(self):
  self.symbols = {"frog":chr(0x238), "rightcar":chr(187), "leftcar":chr(171), "turtle":chr(920), "log":chr(685), "bug":chr(1217), "grass":chr(993), "freehome":chr(164), "fullhome":"@", "road":"-", "water":chr(0x2248), "saferow":"*"}
  self.sprites = {value:key for key, value in self.symbols.items()}
  self.text.tag_configure("frog", foreground="chartreuse", background="dark green")
  self.text.tag_configure("rightcar", foreground="yellow", background="black")
  self.text.tag_configure("leftcar", foreground="yellow", background="black")
  self.text.tag_configure("turtle", foreground="orange red", background="cyan")
  self.text.tag_configure("log", foreground="sienna", background="cyan")
  self.text.tag_configure("bug", foreground="maroon", background="green")
  self.text.tag_configure("grass", foreground="orange", background="green")
  self.text.tag_configure("freehome", foreground="forest green", background="green")
  self.text.tag_configure("fullhome", foreground="red", background="green")
  self.text.tag_configure("road", foreground="gray", background="black")
  self.text.tag_configure("water", foreground="navy", background="cyan")
  self.text.tag_configure("saferow", foreground="pink", background="black")
 ### end of init_sprites ###

 def update_clock(self):
  self.timer -= 1
  self.label.configure(text="Score: "+str(self.score)+" Lives: "+str(self.lives)+" Time: "+str(self.timer))
  if(self.gameover == False):
   self.root.after(max(1, self.timerthreshold - self.speedup), self.update_clock)
 ### end of update_clock ###

 def key_event(self, event):
  direction = event.keysym
  if(direction in self.directions):
   try:
    self.q.put(direction, block=False)
   except:
    pass
 ### end of key_event ###

 def process_world(self):
  # acquire user input and process it if necessary
  if(self.q.qsize() > 0):
   self.move_frog(self.q.get())

  # update the state of non-frog objects
  self.update_world()

  # draw the world
  self.draw_world()

  # schedule another pass unless the game is over
  if(self.gameover == False):
   self.root.after(self.timerspeed, self.process_world)
  else:
   self.root.after(self.timerspeed, self.gameover_screen)
 ### end of process_world ###

 def move_frog(self, d):
  x = self.frogposition[0]
  y = self.frogposition[1]
  if(d == 'Up'):
   y -= 1
  elif(d == 'Down'):
   y += 1
  elif(d == 'Left'):
   x -= 1
  else:
   x += 1
  if(x >= 0 and y >= 0 and x < self.width and y < self.height):
   self.frogposition[0] = x
   self.frogposition[1] = y
   self.movedup = False
   if(d == 'Up' and y < self.highest):
    self.movedup = True
 ### end of move_frog ###

 def gameover_screen(self):
  self.label2 = tk.Label(text="Game over! Your score was: " + str(self.score))
  self.label2.pack()
 ### end of gameover_screen ###

 def update_world(self):
  # update the internal timer
  self.updateticks += 1

  # check for loss conditions
  if((self.timer == 0) or self.hit_by_car() == True or self.in_water() == True or self.home_twice() == True or self.in_grass() == True):
   self.process_death()
   return

  # credit good moves up
  if(self.movedup == True):
   self.score += self.pointsforup
   self.highest = self.frogposition[1]
   self.movedup = False

  # check for win condition
  if(self.at_home() == True):
   self.process_victory()
   return

  # check for total win
  if(self.all_done() == True):
   self.process_win()
   return

  # update the positions of the cars, logs, and turtles
  self.update_positions()
 ### end of update_world ###

 def all_done(self):
  if(len([x for x in self.homes if x[1]==False])==0):
   return True
  return False
 ### end of all_done ###

 def process_win(self):
  self.gameover = True
  return
 ### end of process_win ###

 def process_death(self):
  self.lives -= 1
  if(self.lives < 1):
   self.gameover = True
   return
  self.frogposition[0] = self.frogstart[0]
  self.frogposition[1] = self.frogstart[1]
  self.highest = 12
  self.timer = self.timerstart
 ### end of process_death ###

 def hit_by_car(self):
  for lane in self.lanes:
   if(lane.type != "car"):
    continue
   for car in lane.objects:
    if(car == self.frogposition):
     return True
  return False
 ### end of hit_by_car

 def in_water(self):
  if(self.frogposition[1] < self.waterbordertop or self.frogposition[1] > self.waterborderbottom):
   return False
  for lane in self.lanes:
   if(lane.type == "turtle"):
    for turtle in lane.objects:
     if(turtle == self.frogposition):
      return False
   elif(lane.type == "log"):
    for log in lane.objects:
     if(log == self.frogposition):
      return False
  return True
 ### end of in_water

 def home_twice(self):
  for h in self.homes:
   if(h[0] == self.frogposition and h[1] == True):
    return True
  return False
 ### end of home_twice

 def in_grass(self):
  if(self.frogposition[1] == 0 and self.at_home() == False):
   return True
  return False
 ### end of in_grass

 def at_home(self):
  for h in self.homes:
   if(h[0] == self.frogposition):
    return True
  return False
 ### end of at_home ###

 def process_victory(self):
  self.score += self.pointsforhome
  if(self.bugposition == self.frogposition):
   self.score += self.pointsforbug
  for h in self.homes:
   if (h[0] == self.frogposition):
    h[1] = True
    break
  self.timer = self.timerstart
  self.frogposition[0] = self.frogstart[0]
  self.frogposition[1] = self.frogstart[1]
  self.highest = 12
  self.speedup += self.speedchange
 ### end of process_victory ###

 def init_lanes(self):
  random.seed()
  self.lanes = []
  self.lanes.append(Lane(row=11, lanetype="car", maxnumber=10, replenish=0.1, direction=1, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=10, lanetype="car", maxnumber=8, replenish=0.2, direction=-1, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=9, lanetype="car", maxnumber=5, replenish=0.6, direction=1, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=8, lanetype="car", maxnumber=9, replenish=0.4, direction=-1, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=7, lanetype="car", maxnumber=6, replenish=0.3, direction=1, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=5, lanetype="turtle", direction=-1, length=3, gap=4, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=4, lanetype="log", direction=1, length=3, gap=3, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=3, lanetype="log", direction=-1, length=8, gap=9, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=2, lanetype="turtle", direction=1, length=2, gap=6, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
  self.lanes.append(Lane(row=1, lanetype="log", direction=-1, length=4, gap=4, width=self.width, speed=random.randint(self.minspeed, self.maxspeed)))
 ### end of init_lanes

 def init_special(self):
  self.bugposition = [2, 0]
  self.buglastupdate = 0
  self.bugspeed = random.randint(self.minbugspeed, self.maxbugspeed)
  self.homes = [[[2, 0], False], [[7, 0], False], [[12, 0], False], [[17, 0], False], [[22, 0], False]]
 ### end of init_special ###

 def update_positions(self):
  if(self.updateticks - self.buglastupdate >= self.bugspeed - self.speedup):
   self.buglastupdate = self.updateticks
   while(True):
    freeslots = [x for x in self.homes if x[1] == False]
    if(len(freeslots)==0):
     self.bugposition = [-1,-1]
     break
    if(len(freeslots)==1):
     self.bugposition = freeslots[0][0]
     break
    newhomeindex = random.randint(0, 4)
    if(self.homes[newhomeindex][0] != self.bugposition and self.homes[newhomeindex][1] == False):
     self.bugposition = self.homes[newhomeindex][0]
     break

  for lane in self.lanes:
   lanemovedfrog=False
   if(self.updateticks - lane.lanelastupdate >= lane.speed - self.speedup):
    lane.lanelastupdate = self.updateticks
   else:
    continue
   for o in lane.objects:
    if(o == self.frogposition and lanemovedfrog==False):
     self.move_frog(self.directions[int(0.5*lane.direction + 2.5)])
     lanemovedfrog=True
    o[0] += lane.direction
    if((o[0] < 0) or (o[0] >= self.width)):
     lane.objects.remove(o)
   if(lane.type == "car" and len(lane.objects) < lane.maxnumber and random.random() < lane.replenish):
    lane.objects.append([int((self.width-1)/2 - (self.width-1)*lane.direction/2), lane.row])
   if(lane.type == "log" or lane.type == "turtle"):
    if(lane.direction == 1):
     start = min([x[0] for x in lane.objects])
     nxt = min([x for x in range(start, self.width) if (len([y for y in lane.objects if y[0] == x]) == 0)])
     if(start >= lane.gap or (nxt - start) < lane.length):
      lane.objects.append([0, lane.row])
    else:
     start = max([x[0] for x in lane.objects])
     nxt = max([x for x in range(start, -1, -1) if (len([y for y in lane.objects if y[0] == x]) == 0)])
     if(self.width - start - 1 >= lane.gap or (start - nxt) < lane.length):
      lane.objects.append([self.width - 1, lane.row])
   lane.objects.sort()
 ### end of update_positions ###

 def draw_world(self):
  self.text.state = "normal"
  self.text.delete('1.0', str(self.width + 1) + '.' + '0')
  drawstr = ""
  # draw home row
  newstr = self.symbols["grass"] * self.width
  for h in self.homes:
   if(h[1] == False):
    if(self.bugposition == h[0]):
     newstr = self.str_replace(newstr, h[0][0], self.symbols["bug"])
    else:
     newstr = self.str_replace(newstr, h[0][0], self.symbols["freehome"])
   else:
    newstr = self.str_replace(newstr, h[0][0], self.symbols["fullhome"])
  drawstr += newstr
  drawstr += "\n"

  # draw water rows
  for index in range(self.waterborderbottom - self.waterbordertop + 1):
   newstr = self.symbols["water"] * self.width
   for lane in self.lanes:
    if(lane.row == index + self.waterbordertop):
     for o in lane.objects:
      if(lane.type == "log"):
       newstr = self.str_replace(newstr, o[0], self.symbols["log"])
      elif(lane.type == "turtle"):
       newstr = self.str_replace(newstr, o[0], self.symbols["turtle"])
   drawstr += newstr
   drawstr += "\n"

  # draw safe row
  drawstr += self.symbols["saferow"] * self.width
  drawstr += "\n"

  # draw car rows
  for index in range(len([l for l in self.lanes if l.type == "car"])):
   newstr = self.symbols["road"] * self.width
   for lane in self.lanes:
    if(lane.row == self.waterborderbottom + 2 +index):
     for o in lane.objects:
      if(lane.direction == 1):
       newstr = self.str_replace(newstr, o[0], self.symbols["rightcar"])
      elif(lane.direction == -1):
       newstr = self.str_replace(newstr, o[0], self.symbols["leftcar"])
   drawstr += newstr
   drawstr += "\n"

  # draw safe row
  drawstr += self.symbols["saferow"] * self.width

  # do actual drawing
  self.text.insert('1.0', drawstr)

  # draw frog
  self.text.delete(str(1 + self.frogposition[1]) + '.' + str(self.frogposition[0]))
  self.text.insert(str(1 + self.frogposition[1]) + '.' + str(self.frogposition[0]), self.symbols["frog"])

  # apply colors
  for sprite in self.sprites.keys():
   self.highlight_pattern(sprite, self.sprites[sprite])

  # turn off editability
  self.text.state = "disabled"
 ### end of draw_world ###

 def str_replace(self, targetstr, index, char):
  return targetstr[:index] + char + targetstr[index+1:]
 ### end of str_replace ###

 def highlight_pattern(self, sprite, tag):
  start = self.text.index("1.0")
  end = self.text.index("end")
  self.text.mark_set("matchStart", start)
  self.text.mark_set("matchEnd", start)
  self.text.mark_set("searchLimit", end)
  count = tk.IntVar()
  while True:
   index = self.text.search(sprite, "matchEnd", "searchLimit", count=count, regexp=False)
   if(index == ""):
    break
   self.text.mark_set("matchStart", index)
   self.text.mark_set("matchEnd", "%s+%sc" % (index, count.get()))
   self.text.tag_add(tag, "matchStart","matchEnd")
 ### end of highlight_pattern ###
### end of Frogger class ###

# Run the game!!!
frogger = Frogger()

```

# Answer
> 1 votes
## C++ 1710

I started an ASCII console version. The frog can move. Still working on other requirements. Haven't yet done object detection or scoring. Frog moves with keys w,a,s,d.

```
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define P(x) cout<<x<<endl
#define R 13
#define C 25
string bank="=========================";
string water="~~~~~~~~~~~~~~~~~~~~~~~~~";
string road="-------------------------";
string log="LOG";
string car="CAR";
string frog="FROG";
string leaf="LEAF";
string rows[R];
bool gameover=false;
int frogX,frogY;

void insertObject(string obj, int row, int pos)
{
    string tmp=rows[row].erase(pos,obj.size());
    tmp.insert(pos,obj);
    rows[row]=tmp;
}

void newBoard()
{
int r,r2;
for(int i=0;i<R;i++)
{
    r=rand()%2+1;//1-3
    if(i==0||i==6||i==12)
    {
        rows[i]=bank;
    }
    else if(i>0&&i<6)
    {
        rows[i]=water;
        for(int j=0;j<r;j++)
        {
            r2=rand()%21;
            insertObject(log, i, r2);
        }
    }
    else
    {
        rows[i]=road;
        for(int j=0;j<r;j++)
        {
            r2=rand()%21;
            insertObject(car, i, r2);
        }
    }
}
insertObject(frog, 12, (int)(C-4)/2);
frogX=(int)(C-4)/2;
frogY=12;
insertObject(leaf, 0, (int)(C-4)/2);
}

void showBoard()
{
#ifdef WIN32
system("cls");
#else
system("clear");
#endif
for(int i=0;i<R;i++)
{
    P(rows[i]);
}
}

void playGame()
{
char c;
int i=0;
while(!gameover)
{
cin>>c;
switch(c)
{
case 'a':
    if(frogX!=0)frogX--;
    break;
case 'w':
    if(frogY!=0)frogY--;
    break;
case 'd':
    if(frogX<21)frogX++;
    break;
case 's':
    if(frogY!=12)frogY++;
    break;
default:
    break;
}
insertObject(frog, frogY, frogX);
showBoard();
i++;
if(i>12) gameover=true;
}
}

int main()
{
    srand(time(0));
    char play='y';
    while(play=='y')
    {
        newBoard();
        showBoard();
        playGame();
        P("Play Again (y/n)?");
        cin>>play;
    }

    return 0;
}

```

---
Tags: code-golf, graphical-output, game
---


# Question
Title: Super fast sampling from a tricky random distribution
This is a micro-optimization challenge. The task is to sample from the maximally skewed stable distribution F(x;1,-1,Pi/2,0). See Table 1 of http://arxiv.org/pdf/0908.3961v2.pdf . It is easiest to describe how to do this using the following C code which uses the Mersenne Twister RNG C code from here .

```
#include <stdio.h>
#include <stdlib.h>
#include "mtwist.h"
#include <math.h>

int main(void) {
   int i;
   volatile double x;
   mt_seed();
   double u1;
   double u2;
   double w1;
   double w2;
   for(i = 0; i < 100000000; ++i) {
     u1 = mt_drand();
     u2 = mt_drand();
     w1 = M_PI*(u1-1/2.0);
     w2 = -log(u2);
     x = tan(w1)*(M_PI_2-w1)+log(w2*cos(w1)/(M_PI_2-w1));
   }
   return EXIT_SUCCESS;
}

```

I compile with

```
gcc -Wall -O3 random.c mtwist-1.5/mtwist.c -o random -lm

```

The running time is 20 seconds taking `5,000,000` iterations per second.

There are two obvious ways of making this fast. The first is to choose a very fast uniform random number generator. If you choose to use anything but the Mersenne twister then you must run it through the Diehard tests and check the P-values provided. Use the code here http://www.stat.fsu.edu/pub/diehard/ to do this. Your uniform random number generator must pass at least 15 of these tests.

The second way is to find fast micro-optimizations for the transcendental functions, perhaps using some CPU specific features. For example in my case these features of the AMD FX-8350 CPU.

**Rules** The code must maintain at least 32 bits of accuracy throughout. The code should be compilable on ubuntu using easy to install free software only. Please provide full compile and run instructions. You should also provide a diehard log for any non Mersenne twister RNGs as was done for Build a random number generator that passes the Diehard tests . Note the very simple RNG that passes 15 tests in that link.

**Scores** You can report your score as the time taken by the code above divided by the time taken by your code on your own machine. For running your code you can use any compiler and compilation options you like. To test the code above you should use gcc 4.8 or later with -O3. If any submission take less than one second I will increase N by factors of 10 until the fastest submission takes longer than 1 second.

**Test machine** My test machine was a standard 8GB RAM ubuntu install on an AMD FX-8350 Processor. Your machine can be anything that supports gcc 4.8 or later.

The Intel optimization manual says

> If there is no critical need to evaluate the transcendental functions using the extended precision of 80 bits, applications should consider an alternate, software-based approach, such as a look-up-table-based algorithm using interpolation techniques. It is possible to improve transcendental performance with these techniques by choosing the desired numeric precision and the size of the look-up table, and by taking advantage of the parallelism of the SSE and the SSE2 instructions.

According to this very helpful table,`fcos` has latency 154 and `fptan` has latency `166-231` on my AMD FX 8350.

# Answer
# GMPY2

Abuse of GMP. @OP the slowest part of the code is printing the numbers, if leaving them in memory is fine the code would be much much faster.

```
import math
import random
import gmpy2
from gmpy2 import mpz, mpfr

gmpy2.get_context().precision = 11 # 32 bits of accuracy

N = 100000000
random_state = gmpy2.random_state()
pi = math.pi
half_pi = pi / 2
size = 0
for i in range(N):
    u1 = gmpy2.mpfr_random(random_state)
    u2 = gmpy2.mpfr_random(random_state)
    w1 = gmpy2.mul(pi, gmpy2.sub(u1,1/2))
    w2 = -gmpy2.log(u2)
    a = gmpy2.mul(gmpy2.tan(w1), gmpy2.sub(half_pi, w1))
    b = gmpy2.div(gmpy2.log(gmpy2.mul(w2, gmpy2.cos(w1))), gmpy2.sub(half_pi, w1))
    x = gmpy2.add(a, b)

```
> 1 votes

# Answer
# Nimrod (Score = 1.71, 4.8 vs. 8.2 seconds)

Observe that x-\>\[\[cos x, -sin x\], \[sin x, cos x\]\] is a group isomorphism between \[0, 2\*pi) (with respect to addition modulo 2\*pi) and the rotation matrices (as a subgroup of SL(2, R)).

Because `w1` is effectively of the form `pi*k/2^32`, where `k` is a signed 32-bit integer, we can split k in two 16-bit words, `h` and `l` and always represent `w1` as the sum of `pi*h/2^16+pi*l/2^32` and tabulate rotation matrices for both addends in `2*sizeof(double)*2^16` bytes each. We can then derive `sin(w1)` and `cos(w1)` from the product of the two rotation matrices per the isomorphism above (and `tan(w1)` as `sin(w1)/cos(w1)`).

The code below is in Nimrod, but should be directly portable to C, with the necessary renaming to integer and float types (`float64` in Nimrod corresponds to `double` in C, and `int` corresponds to `intptr_t`, i.e. 64-bit on most modern architectures) and essentially no change in runtime. It currently does not print anything, but uses a volatile variable as described in my earlier comment to avoid the code being optimized away.

Further speedups may come from looking at how to make the computation of the natural logarithm cheaper (and, of course, replace the Mersenne Twister with a different RNG, but that's not very interesting).

Compile with `nimrod cc -d:release random.nim`.

Compile with `-d:validate` instead to check floating point errors with respect to the normal sin/cos calculations.

Update: Added an option to use an Xorshift RNG, enabled by compiling with `-d:xorshift`. This reduces runtime by approximately a quarter. Also fixed RNG generation to avoid `u1 == 0` or `u2 == 0`.

```
import math, mersenne, unsigned

# It is sufficient to represent the rotation matrix
# [ [ cos x, -sin x], [sin x, cos x] ]]
# by just the values in the left column/bottom row.

type RotMat = tuple[sine, cosine: float64]

var tab1, tab2: array[65536, RotMat]

for i in 0..65535:
  tab1[i] = (sin(pi*float64(i-32768)/float64(65536)),
             cos(pi*float64(i-32768)/float64(65536)))
  tab2[i] = (sin(pi*float64(i)/float64(65536*65536)),
             cos(pi*float64(i)/float64(65536*65536)))

proc `*`(x, y: RotMat): RotMat {.inline.} =
  result.cosine = x.cosine*y.cosine-x.sine*y.sine
  result.sine = x.cosine*y.sine+x.sine*y.cosine

proc sincos(x: int): RotMat =
  let r1 = tab1[(x shr 16) and 65535]
  let r2 = tab2[x and 65535]
  return r1*r2

when defined(xorshift):
  type RNGState = object
    x, y, z, w: uint32

  proc getNum(s: var RNGState): int =
    let t = s.x xor (s.x shl 11)
    s.x = s.y; s.y = s.z; s.z = s.w
    s.w = s.w xor (s.w shr 19) xor t xor (t shr 8)
    result = int(s.w)

  var rng = RNGState(x: 1)
else:
  var rng = newMersenneTwister(1)

const maxRand = 1 shl 32

for i in 1..100_000_000:
  var t1, t2: int
  while true:
    t1 = rng.getNum; if t1 != 0: break
  let u1 = t1/maxRand
  while true:
    t2 = rng.getNum; if t2 != 0: break
  let u2 = t2/maxRand
  let w1 = pi*(u1-1/2)
  let w2 = -ln(u2)
  when defined(original):
    let (sw1, cw1) = (sin(w1), cos(w1))
  else:
    let (sw1, cw1) = sincos(t1)
  var x {.volatile.} = sw1/cw1*(pi/2-w1)+ln(w2*cw1/(pi/2-w1))
  when defined(validate):
    var x2 = sin(w1)/cos(w1)*(pi/2-w1)+ln(w2*cos(w1)/(pi/2-w1))
    echo sw1-sin(w1)
    echo cw1-cos(w1)
    echo x-x2

```
> 1 votes

# Answer
# Numpy (score = 1.8)

In response to my previous code not being fast enough (I admit it was very slow), I used numpy which is extremely fast at working with large arrays of numbers and uses low level number libraries (BLAS). This is almost a direct translation of your code, but already is noticeably faster and has the bonus of being very readable.

```
import math
from numpy import *

pi = math.pi
half_pi = pi / 2

for i in range(10000):
    u1 = random.rand(10000)
    u2 = random.rand(10000)

    w1 = pi * (u1 - 1/2)
    w2 = -log(u2)

    a = half_pi - w1
    x = tan(w1)*a + log(w2*cos(w1)/a)

print("done")

```

I am running on i7 4770 with 8 gb RAM. Your code (including -O3 in GCC): 21.8 sec, my code: 11.8 sec.
> 1 votes

---
Tags: fastest-code, random
---