title: Solve the Rotation puzzle

text:
# Question
Title: Solve the Rotation puzzle
On some old Nokia phones, there was a variation of the fifteen puzzle called Rotation. In this variation, instead of sliding one tile at a time, you rotated four tiles at a time in one direction.

In this game, you'd start out with a board like this:

```
4 9 2
3 5 7
8 1 6

```

And by rotating the lower-left block twice clockwise and the upper-left block once clockwise, you'd get this:

```
4 9 2
8 3 7
1 5 6

4 9 2
1 8 7
3 5 6

1 4 2
8 9 7
3 5 6

```

and the `1` tile would be in the top-left corner where it's supposed to be. Eventually, after a few more moves, you'd end up with:

```
1 2 3
4 5 6
7 8 9

```

which is the "original" configuration.

Your task is to build a program that will take as input a 3x3 grid of numbers from 1 to 9 (in any format you choose) and return as output a sequence of moves representing the moves you must take to return the board back to its original configuration (again, in any format you choose). The legal moves are defined as moving the \[top/bottom\]-\[left/right\] block of 4 tiles \[clockwise/counterclockwise\].

Your program must be able to solve all possible 3x3 grids (all permutations are solvable).

The shortest code to do this wins.

# Answer
# GolfScript, 39/83 bytes

```
# Optimized for size:

{.4rand.p.2/+>`{?1420344440`=}+$..$>}do

# Optimized for speed:

6,(7++:t;~{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*

```

### Speed vs size

The size-optimized version randomly chooses clockwise rotations until the desired permutation is achieved. This is sufficient, since a counterclockwise rotation is equivalent to three consecutive clockwise rotations of the same square.

The speed-optimized version does the same, except for the following:

1. If the number 1 is in the upper left corner, it doesn't rotate the upper left square anymore.
2. If the number 9 is in the lower right corner, it doesn't rotate the lower right square anymore.
3. The steps for swapping positions 7 and 8 are hardcoded, so there are two positions that allow the loop to break.

Aside from changing the algorithm, the speed-optimized version achieves the rotation in a straightforward manner, while the size-optimed version uses GolfScript's built-in sort by mapping. It also hardcodes the final state (for comparison) instead of sorting the state in every iteration.

The speed-optimized version requires fewer iterations and every iteration is much faster by itself.

### Benchmarks

I have used the following code to randomize the positions of the numbers and perform test runs, uncommenting the line corresponding to the version to be tested:

```
[{[
    0:c;10,1>{;2 32?rand}$
    #{c):c;.4rand.2/+>`{?1420344440`=}+$..$>}do
    #6,(7++:t;{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*
],c+}\~*]

$.0='Min: '\+puts .-1='Max: '\+puts ..{+}*\,/'Avg: '\+puts .,2/='Med: '\+

```

The output shows the minimum and maximum number of steps it took to order the numbers, the the average and the median of all runs, as well as the elapsed time in seconds:

```
$ TIME='\n%e s' time golfscript rotation-test-size.gs <<< 100
Min: 4652
Max: 2187030
Avg: 346668
Med: 216888

21500.10 s
$
$ TIME='\n%e s' time golfscript rotation-test-speed.gs <<< 1000
Min: 26
Max: 23963
Avg: 3036
Med: 2150

202.62 s

```

On my machine (Intel Core i7-3770), the mean execution time of the size-optimized version was 3.58 minutes. **The mean execution time of the speed-optimized version was 0.20 seconds. Thus, the speed-optimized version is approximately 1075 times faster.**

The speed-optimized version yields 114 times less rotations. Performing each rotation is 9.4 times slower, which is mainly due to how the state is updated.

### I/O

The output consists of 3-bit numbers. The MSB is set for counterclockwise rotations, the middle bit is set for lower squares and the LSB is set for right squares. Thus, 0 (4) is the upper left square, 1 (5) the upper right one, 2 (6) the lower left and 3 (7) the lower right one.

The speed-optimized version prints all rotations on a single line. The size-optimized version prints one rotation per line, followed by the final position of the numbers.

For the speed-optimized version, the input has to yield an array containing the numbers from 1 to 9 when evaluated. For the size-optimized version, the input has to be a string without final newline; it does not get evaluated.

Example runs:

```
$ echo -n '253169748' | golfscript rotation-size.gs
3
0
123456789
$ golfscript rotation-speed.gs <<< '[5 4 7 1 2 9 3 8 6]'
2210300121312212222212211121122211122221211111122211211222112230764

```

### Size-optimized code

```
{               #
  .             # Duplicate the state.
  4rand         # Push a randomly chosen integers between 0 and 3.
  .p            # Print that integer.
  .2/+          # Add 1 to it if it is grater than one. Possible results: 0, 1, 3, 4
  >`            # Slice the state at the above index.
  {             # Push a code block doing the following:
    ?           # Get the index of the element of the iteration in the sliced state.
    1420344440` # Push the string "14020344440".
    =           # Retrieve the element at the position of the computed index.
  }+            # Concatenate the code block with the sliced state.
  $             # Sort the state according to the above code block. See below.
  ..$>          # Push two copies of the state, sort the second and compare the arrays.
}do             # If the state is not sorted, repeat the loop.

```

Updating the state is achieved in the following fashion:

Rotation 2 yields the integer 3 after adding 1. If the state is “123456789”, slicing the state yields “456789”.

Right before executing “$”, the topmost elements of the stack are:

```
[ 1 2 3 4 5 6 7 8 9 ] { [ 4 5 6 7 8 9 ] ? "1420344440" = }

```

“$” executes the block once for every element of the array to be sorted, after pushing the element itself.

The index of 1 in “\[ 4 5 6 7 8 9 \]” is -1 (not present), so the last element of "1420344440" is pushed. This yields 48, the ASCII code corresponding to the character 0. For 2 and 3, 48 gets pushed as well.

The integers pushed for 4, 5, 6, 7, 8 and 9 are 49, 52, 50, 48, 51 and 52.

After sorting, the first element of the state will be one of the elements yielding 48; the last will be one of those yielding 52. The built-in sort is unstable in general, but I've verified empirically that it is stable in this particular case.

The result is “\[ 1 2 3 7 4 6 8 5 9 \]”, which corresponds to a clockwise rotation of the lower left square.

### Speed-optimized code

```
6,(7++:t;       # Save [ 1 2 3 4 5 7 ] in variable “t” and discard it.
~               # Interpret the input string.
{               #
  :s            # Duplicate the current state.
  (1=           # Unshift the first element and push 1 if it is equal to 1 and 0 otherwise.
  .@            # Duplicate the boolean and rotate the unshifted array on top of it.
  7=9=          # Push 1 if the eighth element of “s” is equal to 9 and 0 otherwise.
  +4\-          # Add the booleans and subtract their sum from 4.
  rand          # Push a randomly chosen integers between 0 and the result from above.
  +.            # Add this integer to the first boolean and duplicate it for the output.
  .2/+          # Add 1 to the result if it is grater than one. Possible results: 0, 1, 3, 4
  @.            # Rotate the state on top of the stack and duplicate it.
  @>:s          # Slice the state at the integer from above and save the result in “s”.
  ^             # Compute the symmetric difference of state and sliced state.
  [             # Apply a clockwise rotation to the sliced array:
    3s=         # The fourth element becomes the first.
    0s=         # The first element becomes the second.
    2s=         # The third element remains the same.
    4s=         # The fifth element becomes the fourth.
    1s=         # The second element becomes the fifth.
  ]             # Collect the results into an array.
  +             # Concatenate with array of elements preceding the slice.
  s|            # Perform set union to add the remaining elements of “s”.
  .             # Duplicate the updated state.
  )9<           # Pop the last element; push 0 if it is equal to 9 and 1 otherwise.
  \t            # Swap the popped state on top and push [ 1 2 3 4 5 7 ].
  >             # Push 0 if the state begins with [ 1 2 3 4 5 6 ] and 1 otherwise.
  |             # Take the logical OR of the booleans.
}do             # If the resulting boolean is 1, repeat the loop.
.$              # Duplicate the state and sort it.
>30764`*        # If the state was not sorted, 7 and 8 are swapped, so push "30764".

```

Observe that the rotations 3, 0, 7, 6 and 4 swap the elements in positions 7 and 8, without altering the positions of the remaining seven elements.
> 7 votes

# Answer
# Python with Numpy – 158

```
from numpy import*
A=input()
while any(A.flat>range(1,10)):i,j,k=random.randint(0,2,3);A[i:i+2,j:j+2]=rot90(A[i:i+2,j:j+2],1+2*k);print"tb"[i]+"lr"[j]+"wc"[k]

```

Input has to be of the following format:

```
array([[1,2,5],[4,3,6],[7,8,9]])

```

Each output line is a move encoded in strings like `trw` or `blc` and to be read as follows:

* `t`: top
* `b`: bottom
* `l`: left
* `r`: right
* `c`: clockwise
* `w`: counter-clockwise (widdershins)

---

This program performs random moves until the target configuration is reached. Under the approximative assumption that every move has an independent probability of 1/9! to hit the target configuration¹, the number of rotations before a solution is exponentially distributed with a mean (i.e., the average number of moves) of 9! ≈ 3.6·10⁵. This is in accordance with a short experiment (20 runs).

¹ 9! being the total number of configurations.
> 4 votes

# Answer
# C++ fewest moves solution -- breadth first (1847 chars.)

After a bit more thought, I think I have this done much more efficiently and more sensibly. This solution, while it is certainly not winning this golf, is so far the only one that will attempt to find the shortest number of rotations that will solve the board. So far, it solves every random board I've thrown at it in nine or fewer moves. It also performs significantly better than my last one and, hopefully, addresses Dennis's comments below.

From the previous solution, the largest change was to move the key history from the board state (BS) into a new class that stores the history at a given depth (DKH). Any time the application makes a move, it checks the history at that depth and all depths prior to see if it's ever been evaluated, if so, it won't be added to the queue again. This seems to significantly reduce the storage on the queue (by removing all this history from the board state itself) and therefore reduces pretty much all the stupid pruning I had to do to keep the code from running out of memory. Plus it runs a lot faster since there is much less to copy onto the queue.

Now, it's a simple breadth first search on the various board states. Plus, as it turns out, my want to change the key set (currently stored as set of numbers in base-9, each of which are computed by BS::key as the base-9 representation of the board) over to a bitset having 9! bits seems to be needless; though I did find out how to compute a key in the "factorial number system" which could have been used to compute the bit in the bitset to test/toggle.

So, the newest solution is:

```
#include <iostream>
#include <list>
#include <set>
#include <vector>
using namespace std;
struct BS{
#define LPB(i) for(int*i=b;i-b<9;i++)
struct ROP{int t, d;};
typedef vector<ROP> SV;
typedef unsigned int KEY;
typedef set<KEY> KH;
BS(const int*d){const int*x=d;int*y=b;for(;x-d<9;x++,y++)*y=*x;}
BS(){LPB(i)*i=i-b+1;}
bool solved(){LPB(i)if(i-b+1!=*i)return 0;return 1;}
void rot(int t, int d){return rot((ROP){t,d});}
void rot(ROP r){rotb(r);s.push_back(r);}
bool undo(){if (s.empty())return false;ROP &u=s.back();u.d*=-1;rotb(u);s.pop_back();return true;}
SV &sol(){return s;}
KEY key(){KEY rv=0;LPB(i){rv*=9;rv+=*i-1;}return rv;}
int b[9];
SV s;
void rotb(ROP r){int c=r.t<2?r.t:r.t+1;int bi=(r.d>0?3:4)+c;const int*ri=r.d>0?(const int[]){0,1,4}:(const int[]){1,0,3};for(int i=0;i<3;i++)swap(b[bi],b[c+ri[i]]);}
};
ostream &operator<<(ostream &o, BS::ROP r){static const char *s[]={"tl","tr","bl","br"};o<<s[r.t]<<(r.d<0?"w":"c");return o;}
struct DKH{
~DKH(){for(HV::iterator i=h.begin();i<h.end();++i)if(*i!=NULL)delete *i;}
void add(int d,BS b){h.resize(d+1);if(h[d]==NULL)h[d]=new BS::KH();h[d]->insert(b.key());}
bool exists(BS &b){BS::KEY k=b.key();size_t d=min(b.sol().size(),h.size()-1);do if (h[d]->find(k)!=h[d]->end())return true;while(d--!=0);return false;}
typedef vector<BS::KH *> HV;HV h;
};
static bool solve(BS &b)
{
const BS::ROP v[8]={{0,-1},{0,1},{1,-1},{1,1},{2,-1},{2,1},{3,-1},{3,1}};
DKH h;h.add(0,b);
list<BS> q;q.push_back(b);
while (!q.empty())
{
BS qb=q.front();q.pop_front();
if (qb.solved()){b=qb;return true;}
int d=qb.sol().size()+1;
for (int m=0;m<8;++m){qb.rot(v[m]);if (!h.exists(qb)){h.add(d,qb);q.push_back(qb);}qb.undo();}
}
return false;
}
int main()
{
BS b((const int[]){4,9,2,3,5,7,8,1,6});
if (solve(b)){BS::SV s=b.sol();for(BS::SV::iterator i=s.begin();i!=s.end();++i)cout<<*i<<" ";cout<<endl;}
}

```
> 4 votes

# Answer
# CJam - 39

```
l{4mr_o_1>+_@m<_[Z0Y4X]\f=\5>+m>__$>}g;

```

Another random solver :)
It takes a string such as 492357816 and outputs a (long) series of digits from 0 to 3, each representing a clockwise rotation of a block: 0=top-left, 1=top-right, 2=bottom-left, 3=bottom-right.

Brief explanation:

`4mr` generates a random number from 0 to 3
`_1>+` increments the number if it's greater than 1 (so we end up with 0, 1, 3 or 4 - the starting indexes of the 4 blocks)
`m<` rotates the string to the left (such as 492357816 -\> 923578164, not the block rotation) in order to bring the block to rotate in the first position
`[Z0Y4X]\f=` does the block rotation which affects the first 5 characters, such as 12345 -\> 41352;
X=1, Y=2, Z=3 so \[Z0Y4X\] is actually \[3 0 2 4 1\] and those are the 0-based indexes of the rotated tiles
`5>` copies the rest of the string
`m>` rotates the (modified) string back to the right
`__$>` checks if the string is sorted (it's the stopping condition)
> 1 votes

# Answer
# Mathematica, 104 chars

We can interpret the task in the language of permutation groups. The four rotations are just four permutations that generate the symmetric group S9, and the task is just to write a permutation as a product of the generators. Mathematica has a built-in function to do this.

```
i={1,2,5,4};GroupElementToWord[PermutationGroup[Cycles/@({i}+#&/@i-1)],Input[]~FindPermutation~Range@9]

```

**Example:**

Input:

```
{4, 9, 2, 8, 3, 7, 1, 5, 6}

```

Output:

```
{-2, -3, -4, 2, 4, 1, 4, -1, -2, 3, 2, -4, 3, 4, -3, -3, -4, -4, -2, -2, -3, -2, 3, -1}

```
* `1`: top-left clockwise
* `2`: top-right clockwise
* `3`: bottom-right clockwise
* `4`: bottom-left clockwise
* `-1`: top-left counterclockwise
* `-2`: top-right counterclockwise
* `-3`: bottom-right counterclockwise
* `-4`: bottom-left counterclockwise
> 1 votes

---
Tags: code-golf, sliding-puzzle
---


title: What can you do in a 4k data URI?

text:
# Question
Title: What can you do in a 4k data URI?
**Bounty is over, thephpdeveloper wins with Conway's Game of Life**

The web platform today is advancing at a rapid rate. Features like CSS3 animations, transforms, drop shadows and gradients, `<canvas>`, `<audio>` and `<video>` tags, SVG, WebGL, and many more mean that you can do far more in the browser, and in far less code, than ever before. Of course, many developers don't get to use those new features, because the sites and applications they work on need to be backwards compatible with ancient, moth-eaten browsers like IE6.

So, what happens if you take the harness off? Allow yourself to use any and all new features that you like? Live a little, go crazy, use weird bleeding edge features that only 1% of your users will be able to take advantage of?

Of course, with unlimited resources and the ability to talk to a server, you can do all manner of things—load megabytes of code and libraries and videos, and so on—but challenges aren't very interesting without constraints. The major constraint for this contest is: what can you do in a single, self-contained, 4k `data:` URI? Self-contained means it must not refer to any external resources, connect to any servers using WebSockets or XHR, or anything of the sort. If you want to embed resources like PNGs or MP3s, feel free to include data URIs within your data URI, or come up with some other clever way of embedding sub-resources. 4k means 4096 bytes, properly URI-encoded, ASCII text (you may use a base64 encoded data URI if you choose, to avoid URI encoding, but usually URI encoded text will be smaller than base64 for plain text).

To provide inspiration, the theme of the contest is StackOverflow memes. Create a unicorn-jousting game, a Jon Skeet fact generator, a freehand-circle based drawing program, or anything to do with one of the popular StackOverflow & meta.so memes.

I would encourage entries that are interactive in some way; not just a simple animation or static image, they should respond to user input, whether through events, CSS hover, scrolling, browser window resizing, or any other way you can think of. This is not a hard requirement, though; great demos that are not interactive will be considered, though interactivity would be preferred.

Your entry must run in at least one public release of at least one of the 5 major browsers (IE, Firefox, Chrome, Safari, Opera). Only mainline releases (not builds from branches or builds that require patches), with no special configuration settings, plugins, or anything else that does not come with the stock browser are allowed. Nightly builds, betas, and release candidates are fine. Please specify in your entry which browsers you've tested your entry with. There are no limitations on what technologies you may use within those constraints; you may do a pure SVG animation, a pure CSS animation, something in JavaScript using WebGL, or heck, even something that uses XML and XSLT if that strikes your fancy. If you can cram it into a valid data URI, with no external dependencies, and get a browser to run it, it's fair game.

To add to the competition here, on Monday, March 21, I will open a bounty on this question. How can I afford a bounty when I have only 101 rep? Well, all rep I gain from upvotes to this question between now and Monday will go into the bounty (up to the limit of 500 allowed for a single bounty; it would be pretty hard for me to hit that limit, though, given the rep cap). Entries will be accepted for 6 days after that; all entries must be in at least 24 hours before the bounty expires, to give me time to check them all out and evaluate them. At that point, I will accept the highest voted answer, and give the bounty to my favorite answer (which may or may not be the same as the highest voted). My criteria for awarding the bounty will include beauty, fun, clever technique, interesting use of new features, interactivity, and size. People should vote based on any criteria they want, as long as the entries meet the rules.

Here are some sources of inspiration, to get you started:

* Chrome Experiments, a collection of demonstrations of the modern web platform
* Mozilla Hacks, a blog about the modern web platform with many demos of new features in Firefox 4
* JS1k, a contest for 1k JavaScript demos
* 10k Apart, a webapp in 10k contest
* gl64k, a demo contest currently running for 64k WebGL demos
* Shader Toy, a set of demos of what you can do with WebGL shaders

Format for entries:

> **Name of entry**
>
> ```
> data:text/html,Your%20data%20URI
> ```
>
> *Works in Firefox 4 RC, Chrome 10, and Opera 11*
>
> Description of your entry; what it does, why it's neat, what clever techniques you used.
>
> ```
> <script>
>   // code in expanded form to more easily see how it works
> </script>
>
> ```
>
> Any credits for inspirations, any code you might have borrowed from, etc.

(StackExchange appears not to accept data URIs in links, so you'll need to embed it directly in a `<pre>` tag)

# Answer
# SO meme: Everything is a meme

> Everything is a meme. enough said.

## Conway's Game of Life, HTML5+CSS3+JS,

### 3,543 3,561 3,555 bytes

```
data:text/html,<!DOCTYPE%20html>%0A<html><head><title>Conway's%20Game%20of%20Life%20by%20Sam-Mauris%20Yong</title><style>body{margin:20px;padding:0;font:12px/1.6%20tahoma,sen-serif;}.clr{clear:both}#ftr{padding:10px;border-top:1px%20solid%20#DDD;margin-top:10px}input[type="submit"],input[type="button"],a.btn,a.btn:visited{color:#999;-moz-border-radius:5px;-webkit-border-radius:5px;border:1px%20solid%20#EEE;color:#333;cursor:pointer;padding:4px%208px;text-decoration:none;border:1px%20solid%20#EEE;background-color:#DDD}input[type="submit"]:hover,input[type="button"]:hover,a.btn:hover{background-color:#666;border:1px%20solid%20#EEE;color:#EEE;text-shadow:#000%201px%201px%200}a.btn.%20a.btn:visited{padding:5px%208px}input[type="submit"]:focus,input[type="button"]:focus,a.btn:focus{outline:none;border:1px%20solid%20#099}</style></head><body><h1>Conway's%20Game%20of%20Life</h1><canvas%20id="c"%20width="800"%20height="600"></canvas><div%20class="clr"></div><div%20style="margin-top:5px;"><input%20type="button"%20value="Start"%20id="ctrlStart"><input%20type="button"%20value="Stop"%20id="ctrlStop"><input%20type="button"%20value="Next"%20id="ctrlNext"></div><div%20id="ftr"><i>App%20requires%20awesome%20browsers%20supporting%20HTML5.</i><br>Written%20by%20@<a%20href="http://twitter.com/thephpdeveloper">thephpdeveloper</a>%20aka%20Sam-Mauris%20Yong.</div><script>eval(function(p,a,c,k,e,r){e=function(c){return(c<a?'':e(parseInt(c/a)))+((c=c%a)>35?String.fromCharCode(c+29):c.toString(36))};if(!''.replace(/^/,String)){while(c--)r[e(c)]=k[c]||e(c);k=[function(e){return%20r[e]}];e=function(){return'\\w+'};c=1};while(c--)if(k[c])p=p.replace(new%20RegExp('\\b'+e(c)+'\\b','g'),k[c]);return%20p}('7%20$(b){j%20Q.R(b)}7%20p(b){j%20S(b)}5%20k=$("c");5%20a=k.T("U");5%209={x:V,y:W};5%20s=10;5%206=t%20B(9.x);5%20X=Y;5%20i=-1;l(i++<6.h-1){6[i]=t%20B(9.y)}7%20C(b,c){a.D="Z";a.E(b*s,c*s,s,s);a.F="11";a.G(b*s,c*s,s,s)}7%20u(b){5%20c=t%2012();4(g(b)=="H"){4(g(b.h)!="I"){5%20c=[]}13(5%20d%2014%20b){4(g(b[d])=="H"){c[d]=u(b[d])}v{4(g(b[d])=="15"){c[d]=b[d]}v{4(g(b[d])=="16"){c[d]=b[d]}v{4(g(b[d])=="17"){((b[d]==m)?c[d]=m:c[d]=n)}}}}}}j%20c}7%208(b){j%20g(b)=="I"||!b?n:m}7%20J(b,d){5%20c=0;4(b>0){4(8(6[b-1][d])){c++}4(d>0){4(8(6[b-1][d-1])){c++}}4(d<9.y-1){4(8(6[b-1][d+1])){c++}}}4(b<9.x-1){4(8(6[b+1][d])){c++}4(d>0){4(8(6[b+1][d-1])){c++}}4(d<9.y-1){4(8(6[b+1][d+1])){c++}}}4(d>0){4(8(6[b][d-1])){c++}}4(d<9.y-1){4(8(6[b][d+1])){c++}}j%20c}7%20K(){5%20d=u(6);5%20c=0;l(c<6.h){5%20f=0;l(f<6[c].h){5%20b=6[c][f];5%20e=J(c,f);4(e<2||e>3){d[c][f]=n}4(e==3){d[c][f]=m}f++}c++}6=d}7%20o(){a.D="#18";a.E(0,0,p(k.19),p(k.1a));5%20b=0;l(b<6.h){5%20c=0;l(c<6[b].h){a.F="#1b";a.G(b*s,c*s,s,s);4(6[b][c]){C(b,c)}c++}b++}}5%20q;7%20w(){K();o()}7%20L(){q=M.1c(w,1d)}7%20N(){q=M.1e(q)}7%20z(c){4(r){5%20b=O.P((c.1f-p(k.1g))/s);5%20d=O.P((c.1h-p(k.1i))/s);6[b][d]=!6[b][d];o()}}5%20r=n;o();k.1j=7(b){r=m};k.1k=7(b){z(b)};k.1l=7(b){z(b);r=n};$("1m").A=N;$("1n").A=w;$("1o").A=L;',62,87,'||||if|var|space|function|evalbool|max|||||||typeof|length||return||while|true|false|draw||time_var|dodrawing||new|deepObjCopy|else|next|||editorDraw|onclick|Array|drawCell|fillStyle|fillRect|strokeStyle|strokeRect|object|undefined|countAliveNeighbours|update|start|window|stop|Math|floor|document|getElementById|parseInt|getContext|2d|80|60|lastSpace|null|black||white|Object|for|in|string|number|boolean|fff|width|height|ccc|setInterval|250|clearInterval|pageX|offsetLeft|pageY|offsetTop|onmousedown|onmousemove|onmouseup|ctrlStop|ctrlNext|ctrlStart'.split('|'),0,{}))</script></body></html>

```

This is Conway's Game of Life written myself for HTML5 with canvas and CSS3. I wrote it for fun during the period of 10K Apart competition but I did not submit this for the competition.

Base64 encoded version spans over 4.61KB of data, whereas the original version is ~3543 bytes.

**To compress the size**: Javascript code minified by YUI online compressor, then by Dean Edwards' packer. CSS Code minified by YUI online compressor. Uses jQuery library from Google API Library. Valid HTML5 and CSS3 (experimental version of the w3 validator).

To play:

* Black box represents a live cell, white represents dead cell.
* Click on a box to mark a live cell, click again to mark it dead.
* Press `<Start>` to run the simulation, `<Stop>` to pause, and `<Next>` to show the next step
* Runs awesome on Internet Explorer 9, Firefox 4 (and Firefox 3 as well), Safari 5, and Google Chrome.

The human-readable (robots shall die) version:

```
<!DOCTYPE html>
<html>
    <head>
        <title>Conway's Game of Life by Sam-Mauris Yong</title>
        <style>
            body{
                margin:20px;
                padding:0;
                font:12px/1.6 tahoma,sen-serif;
            }
            .clr{
                clear:both
            }
            #ftr{
                padding:10px;
                border-top:1px solid #DDD;
                margin-top:10px
            }
            input[type="submit"],input[type="button"],a.btn,a.btn:visited{
                color:#999;
                -moz-border-radius:5px;
                -webkit-border-radius:5px;
                border:1px solid #EEE;
                color:#333;
                cursor:pointer;
                padding:4px 8px;
                text-decoration:none;
                border:1px solid #EEE;
                background-color:#DDD
            }
            input[type="submit"]:hover,input[type="button"]:hover,a.btn:hover{
                background-color:#666;
                border:1px solid #EEE;
                color:#EEE;
                text-shadow:#000 1px 1px 0
            }
            a.btn,a.btn:visited{
                padding:5px 8px
            }
            input[type="submit"]:focus,input[type="button"]:focus,a.btn:focus{
                outline:none;
                border:1px solid #099
            }
        </style>
    </head>
    <body>
        <h1>Conway's Game of Life</h1>
    <canvas id="c" width="800" height="600"></canvas>
    <div class="clr"></div><div style="margin-top:5px;">
        <input type="button" value="Start" id="ctrlStart">
        <input type="button" value="Stop" id="ctrlStop">
        <input type="button" value="Next" id="ctrlNext">
    </div>
    <div id="ftr">
        <i>App requires awesome browsers supporting HTML5.</i>
        <br>
        Written by @<a href="http://twitter.com/thephpdeveloper">thephpdeveloper</a> aka Sam-Mauris Yong.
    </div>
    <script>
        function $(i){
            return document.getElementById(i);
        }
        function p(v){
            return parseInt(v);
        }
        var k = $("c");
        var a = k.getContext('2d');

        var max = {
            x: 80,
            y: 60
        };

        var s = 10;
        var space = new Array(max.x);
        var lastSpace = null;
        var i = -1;
        while(i++ < space.length - 1){
            space[i]= new Array(max.y);
        }

        function drawCell(x,y){
            a.fillStyle = "black";
            a.fillRect(x * s, y * s, s, s);
            a.strokeStyle = "white";
            a.strokeRect(x * s, y * s, s, s);
        }

        function deepObjCopy (dupeObj) {
            var retObj = new Object();
            if (typeof(dupeObj) == 'object') {
                if (typeof(dupeObj.length) != 'undefined')
                    var retObj = [];
                for (var objInd in dupeObj) {
                    if (typeof(dupeObj[objInd]) == 'object') {
                        retObj[objInd] = deepObjCopy(dupeObj[objInd]);
                    } else if (typeof(dupeObj[objInd]) == 'string') {
                        retObj[objInd] = dupeObj[objInd];
                    } else if (typeof(dupeObj[objInd]) == 'number') {
                        retObj[objInd] = dupeObj[objInd];
                    } else if (typeof(dupeObj[objInd]) == 'boolean') {
                        ((dupeObj[objInd] == true) ? retObj[objInd] = true : retObj[objInd] = false);
                    }
                }
            }
            return retObj;
        }

        function evalbool(v){
            return typeof(v) == 'undefined' || !v ? false : true;
        }

        function countAliveNeighbours(x,y){
            var l = 0;
            // left side
            if(x > 0){
                if(evalbool(space[x-1][y])){
                    l++;
                }
                if(y > 0){
                    if(evalbool(space[x-1][y-1])){
                        l++;
                    }
                }
                if(y < max.y-1){
                    if(evalbool(space[x-1][y+1])){
                        l++;
                    }
                }
            } // left side

            // right side
            if(x < max.x - 1){
                if(evalbool(space[x+1][y])){
                    l++;
                }
                if(y > 0){
                    if(evalbool(space[x+1][y-1])){
                        l++;
                    }
                }
                if(y < max.y-1){
                    if(evalbool(space[x+1][y+1])){
                        l++;
                    }
                }
            }
            // right side

            if(y > 0){
                if(evalbool(space[x][y-1])){
                    l++;
                }
            }

            if(y < max.y-1){
                if(evalbool(space[x][y+1])){
                    l++;
                }
            }

            return l;
        }

        function update(){
            var t = deepObjCopy(space);
            var x = 0;
            while(x < space.length){
                var y = 0;
                while(y < space[x].length){
                    var cell = space[x][y];
                    var nalive = countAliveNeighbours(x,y)

                    if(nalive < 2 || nalive > 3){
                        t[x][y] = false;
                    }
                    if(nalive==3){
                        t[x][y] = true;
                    }

                    y++;
                }
                x++;
            }
            space = t;
        }

        function draw(){
            a.fillStyle = "#fff";
            a.fillRect(0, 0, p(k.width), p(k.height));
            var x = 0;
            while(x < space.length){
                var y = 0;
                while(y < space[x].length){
                    a.strokeStyle = "#ccc";
                    a.strokeRect(x*s, y*s, s,s);
                    if(space[x][y]){
                        drawCell(x, y);
                    }
                    y++;
                }
                x++;
            }
        }

        var time_var;

        function next(){
            update();
            draw();
        }

        function start(){
            time_var = window.setInterval(
            next, 250);
        }

        function stop(){
            time_var = window.clearInterval(time_var);
        }
        function editorDraw(e){
            if(dodrawing){
                var x = Math.floor((e.pageX-p(k.offsetLeft))/s);
                var y = Math.floor((e.pageY-p(k.offsetTop))/s);
                space[x][y] = !space[x][y];
                draw();
            }
        }
        var dodrawing = false;

        draw();
        k.onmousedown = function(e){
            dodrawing=true;
        }
        k.onmousemove = function(e){
            editorDraw(e);
        }
        k.onmouseup = function(e){
            editorDraw(e);
            dodrawing=false;
        }
        $("ctrlStop").onclick = stop;
        $("ctrlNext").onclick = next;
        $("ctrlStart").onclick = start;
    </script>
</body>
</html>

```

A class in history:

1. Modified to remove dependency from jQuery as well as URI-encoding all spaces. Improved code in many ways (that I can't remember of).
2. Fixed bug in calculation of alive neighbours and refactored some code to reduce size.
> 34 votes

# Answer
Sorry to dig up an old thread, but I saw this challenge on the side bar and I just couldn't resist. I don't mind that the challenge is over really, it was just fun coming up with something.

Maybe we could have another round?

Anyway, my submission:

## Edit

Sorry to dig this up *again*, but it was bothering me for ages that I couldn't get this under 1KB. Now I've done it!

# Interactive, Shaded Cube:

## 960 987 1082 1156 1182 1667 1587 bytes!, HTML+CSS3+JS

```
data:text/html,<script>X='position:absolute;',S=Math,l=S.sin,V=S.cos,D='style',$='getElementsByTagName',E=H=G=(L=K=99)/2,q=-G,j=1e4,Y=',';function _(p,r,D){A=[],B=l(r),C=V(r);for(z=6;z--;)v=z*3,A.unshift({x:l(D)*(B*p[v+1]+C*p[v+2])+V(D)*p[v]+K,y:C*p[v+1]-B*p[v+2]+K});return A}function R(a,b,c){F=x[v++],a=N[a],b=N[b],c=N[c];F.setAttribute(D,X+'-webkit-transform:matrix('+(a.x-b.x)/L+Y+(a.y-b.y)/L+Y+(c.x-b.x)/L+Y+(c.y-b.y)/L+Y+b.x+Y+b.y+');opacity:'+(((b.y-a.y)/(b.x-a.x)-(c.y-a.y)/(c.x-a.x)<0)^(a.x<b.x^a.x>c.x)));F[$]('b')[0][D].background='rgb(0,'+(d(a,c)+d(a,b))+',0)';return R}function d(P,O){W=P.x-O.x,Q=P.y-O.y;return S.sqrt(W*W+Q*Q)|0}onload=function(){P=document;for(o=6;o--;)P.body.appendChild(P.createElement('P')).innerHTML='<b '+D+'="'+X+'width:99;height:99"></b>';x=P[$]('p');onmousemove=function(e){J=e.pageX-K;U=e.pageY-K};setInterval(function(){N=_([q,q,q,G,G,q,q,G,q,q,q,G,G,q,G,G,G,G],E+=J/j,H+=U/j);R(2,0,3)(5,1,2)(0,2,1)(4,3,0)(3,4,5)(1,5,4)})}</script>

```

Move your mouse.

Works in Chrome (18.something, but should work on most recent ones).

I golfed this pretty well, I saved a few characters using a trick I thought was pretty cool: Say you have the following:

```
function g(x){alert("hello "+x+"!")}
g("dave");g("martin");g("alice");g("rose");g("bob");g("helen");g("jo");

```

characters can be saved by returning the function within itself and doing the following:

```
function g(x){alert("hello "+x+"!");return g}
g("dave")("martin")("alice")("rose")("bob")("helen")("jo");

```

Savings depends on how many function calls you have. This is probably better for obfuscation rather than golfing though.

I also saved a characters by replacing `1000` with `1e4`, giving the `Math` class, and some of its functions, aliases. Using variables for repeated strings (quite hard to find some of these saves). Also, I had the word `style` in my code a few times; some of them were strings and others were identifiers like `element.style.whatever`. Assigning the string to a variable (`D='style`) allowed me to replace the strings with `D` and to replace the identifiers like so `element[D].whatever`.

Latest Edit: sorry to bring up an old comp', but some ideas how to shorten this just came to me!
> 22 votes

# Answer
## JavaScript 489 chars

This plays Guess a Number game.

```
data:text/html,<!DOCTYPE%20html><html><body><h1>Guess the number between 0 and 100</h1><p id="p">good luck</p><form><input id="i" type="text"></input></form><br><button onclick="h()">Try</button><script>var r=Math.round(100*Math.random());function h(){var a=document.getElementById("i").value;var anum="/(^\d+$)/";var res="is not a number!";if (!isNaN(a)){if(a<r) res="higher";else if(r<a) res="lower";else res="you win";}document.getElementById("p").innerHTML=res;}</script></body></html>

```

I worked it out with this code:

```
<!DOCTYPE html>
<html>
<head>
</head>
<body onload="g()">
<p id="p"></p>

<script>
f=function(x){
var y=x.replace(" ","%20");
window.location.assign("data:text/html,"+y);
}
g=function(){
var a="<!DOCTYPE html><html><body><h1>Guess the number between 0 and 100</h1><p id=\"p\">good luck</p>"+
"<form><input id=\"i\" type=\"text\"><\/input></form>"
+"<br><button onclick=\"h()\">Try<\/button><script>"
+document.getElementById("s").innerHTML+
"<\/script><\/body><\/html>";
f(a);
}
</script>
<script id="s">
var r=Math.round(100*Math.random());
function h(){
var a=document.getElementById("i").value;
var anum="/(^\d+$)/";
var res="is not a number!";
if (!isNaN(a)){
if(a<r) res="higher";
else if(r<a) res="lower";
else res="you win";
}
document.getElementById("p").innerHTML=res;
}
</script>

</body>
</html>

```
> 2 votes

---
Tags: popularity-contest, javascript
---


# Question
Title: Moving CSS rules from a CSS file to inline attributes
The goal is to take CSS rules from a regular CSS file and apply them to their respective targets in an HTML file, but by placing the rules in the `style=""` attribute (using the `<style>` tag would be too simple) and removing the `class=""` and `id=""` attributes.

Rules:

* Only ids `#id` and classes `.class` selectors must be supported, without more complex rules (parent selector `#a #b` or multiple classes `.a.b`, etc.)
* Reducing rules is not required, for example the rules `#a{color:red} .b{color:blue}` applied to `<div id="a" class="b"></div>` can output `<div style="color:blue;color:red;"></div>` and the browser will only use the last rule (hereby red)
* The paths to input files can be transmitted by command line arguments or hard-coded in the script/program
* You can't call an external library, you can only include classes or functions built in the language (or from another language if needed)
* Standard “loopholes” are forbidden
* You program must produce the expected result but also works with other input files (to avoid hard-coded solution)
* The output does not need to be saved to any file
* Shortest code wins

## Inputs:

### CSS file

```
#h1 {color:Red;}
#bigger {font-size:1.1em;}
.code {font-family:Monospace;}
.golf {background-color:LightGreen;}

```

Only ids and classes are used in order to keep it simple.

### HTML file

```
<!DOCTYPE html>
<html>
<head><title>Hello World!</title></head>
<body>
<h1 id="h1">Hello World!</h1>
<ol>
    <li class="code">Code</li>
    <li id="bigger" class="golf">Golf</li>
    <li class="code golf">Code golf</li>
</ol>
</body>
</html>

```

## Expected output:

```
<!DOCTYPE html>
<html>
<head><title>Hello World!</title></head>
<body>
<h1 style="color:Red">Hello World!</h1>
<ol>
    <li style="font-family:Monospace;">Code</li>
    <li style="font-size:1.1em;background-color:LightGreen;">Golf</li>
    <li style="font-family:Monospace;background-color:LightGreen;">Code golf</li>
</ol>
</body>
</html>

```

Example on jsfiddle.

# Answer
> 2 votes
### bash + sed ~~133~~ ~~185~~ 179

```
sed -re 's/ass="([^"]*) ([^"]*)"/ass="\1" class="\2"/g;'"$(
    sed -re 's/^#/id§/;s/^\./class§/;
        s/(.*)§(\S*) \{(.*)\}/s@\1="\2"@style="\3"@g/' $CSS
      )"';s/yle="(.*)" style="/yle="\1/g' $HTML

```
~~```
sed -re 's/class="([^"]*) ([^"]*)"/class="\1" class="\2"/g;
    '"$(sed -re 's/^#/id /;s/^\./class /;
        s/(\S*) (\S*) \{(.*)\}/s@\1="\2"@style="\3"@g/' $CSS
    )"';s/style="(.*)" style="/style="\1/g' $HTML

```~~

In this (specific) case, this will render:

```
<!DOCTYPE html>
<html>
<head><title>Hello World!</title></head>
<body>
<h1 style="color:Red;">Hello World!</h1>
<ol>
    <li style="font-family:Monospace;">Code</li>
    <li style="font-size:1.1em;background-color:LightGreen;">Golf</li>
    <li style="font-family:Monospace;background-color:LightGreen;">Code golf</li>
</ol>
</body>
</html>

```

# Answer
> 3 votes
# Python - ~~508~~, ~~501~~, 483

The idea is to read all the rules then apply them by using xpath functions, too bad it can't select nodes with multiple classes (I didn't find own to target `class="code golf"`).

## Golfed

```
import sys,xml.etree.ElementTree as E
r=E.parse(sys.argv[2])
def a(e,f):e.set('style',(e.attrib.get('style')or'')+f)
for l in open(sys.argv[1]):
 s=l.replace("\n",'').split(' ');b=s[0];c=s[1][1:-1]
 if(b[:1])=='#':
  for e in r.findall('.//*[@id=\''+b[1:]+'\']'):a(e,c);e.attrib.pop('id')
 else:
  for e in r.findall('.//*[@class]'):
   d=e.attrib.get('class').split(' ')
   if b[1:]in d:
    a(e,c);e.set('class',' '.join(d[1:]))
    if len(d) == 1: e.attrib.pop('class')
E.dump(r)

```

## Usage

`python script.py input.css input.html`

## Ungolfed code

```
import sys, xml.etree.ElementTree as ET
root = ET.parse(sys.argv[2])

# append rules to style="" attribute
def a(e,f):
    e.set('style',(e.attrib.get('style')or'') + f)

# CSS file
for l in open(sys.argv[1]):
    split = l.replace("\n", '').split(' ')
    selector = split[0]
    rules = split[1][1:-1]

    # #id
    if (b[0:1]) == '#':
        for e in root.findall('.//*[@id=\''+selector[1:]+'\']'):
            a(e,rules)
            # remove id
            e.attrib.pop('id')
    # .class
    else:
        for e in root.findall('.//*[@class]'):
            d=e.attrib.get('class').split(' ')
            if selector[1:] in d:
                a(e,rules)
                e.set('class', ' '.join(d[1:]))
                # remove class
                if len(d) == 1:
                    e.attrib.pop('class')

ET.dump(root)

```

# Answer
> 3 votes
# JavaScript - 589 (573)

It's 573 when processed by a minifier.

Not smaller then the Python version, but processes CSS using DOM objects instead of text strings. This should be able to process more complex CSS selectors also. But then the `id` and `class` attributes are not handled at the moment.

```
x=document
x.write('<link rel="stylesheet" href="'+c+'"/>')
window.onload=function(){
var s,p,n,t,i,j,r=x.styleSheets[0].cssRules,d=x.getElementById('i').contentWindow.document
for(i=0;i<r.length;i++){s=r[i].selectorText
p=r[i].cssText.match(/\{\s*(.*?)\s*\}/)
n=d.querySelectorAll(s)
for(j=0;j<n.length;j++){t=n[j].getAttribute('style')==null?'':n[j].getAttribute('style')
n[j].setAttribute('style',(t+p[1]).replace(': ',':'))
n[j].removeAttribute(s.charAt(0)=='#'?'id':'class')
}}alert(new XMLSerializer().serializeToString(d))}
x.write('<iframe src="'+h+'" id="i"></iframe>')

```

Runs in Firefox if you put the script, the files to process and this web page in the same folder:

```
<html><body>
<script type="text/javascript">
var c='css2inline.css',
    h='css2inline-input.html'
</script>
<script type="text/javascript" src="a.js"></script>
</body></html>

```

Replace `c` and `h` with CSS and HTML files, open this page and an alert shows the HTML.

**Note** The resulting HTML is a serialization of the DOM tree. That causes the result to be not exactly formatted as requested, but it represents the same HTML. Your call to say if you find it correct or not.

Expanded:

```
// Add CSS to current document.
x = document
x.write('<link rel="stylesheet" href="'+c+'"/>')

window.onload = function(){
    var s,p,n,t,i,j,
        r = x.styleSheets[0].cssRules,

        // Get the HTML to process.
        d = x.getElementById('i').contentWindow.document

    // Loop through CSS rules.
    for(i = 0; i < r.length; i++){

        // Get CSS selector from rule.
        s = r[i].selectorText

        // Get text with CSS properties.
        p = r[i].cssText.match(/\{\s*(.*?)\s*\}/)

        // Get DOM nodes matching the CSS selector.
        n = d.querySelectorAll(s)

        // Add CSS properties to style of selected nodes.
        for(j = 0; j < n.length; j++){

            // Preserve current value.
            t = n[j].getAttribute('style') == null ? '' : n[j].getAttribute('style')

            // Add rule properties.
            n[j].setAttribute('style',(t + p[1]).replace(': ',':'))

            // Remove id/class attribute from element.
            n[j].removeAttribute(s.charAt(0) == '#' ? 'id' : 'class')
        }
    }
    // Output serialized document.
    alert(new XMLSerializer().serializeToString(d))
}

// Create document with input HTML.
x.write('<iframe src="'+h+'" id="i"></iframe>')

```

# Answer
> 1 votes
# Lua - ~~340~~ 335

```
f='(%w+)'a={}b={}for l in io.lines(arg[2])do i=l:sub(1,1)t=i=='#'and a or b
k,v=l:match(f..' {(.-)}')t[k]=v end
for l in io.lines(arg[1])do
c=''g='class="(.-)"'h='style="'l=l:gsub('id='..f,function(v)l:gsub(g,function(e)c=e:gsub(f,b)end)return h..a[v]..c..'"'end)l=l:gsub(g,function(e)return #c<1 and h..e:gsub(f,b)..'"'end)print(l)end

```

**Usage:** execute from the command line `lua script.lua input.html input.css`

---
Tags: code-golf
---


title: Write a square-counting program

text:
# Question
Title: Write a square-counting program
A well-known puzzle involves counting how many squares can be made using the points on a 3x3 grid:

```
.  .  .
.  .  .
.  .  .

```

The answer is 6 — four small squares, one large square, and one square formed from the top, left, bottom, and right pegs, with edges along the *diagonals* of the squares.

Your task is to build a program that counts the total number of squares that can be formed from a set of points.

Your program will take input in one of two formats (of your choosing):

* An `M` by `N` grid consisting of either `.` or . `.` represents a point on the grid that a square can be a corner of, and all spaces on the grid are exactly one unit apart horizontally or vertically.
* A list of coordinate pairs representing points that a square can be on.

and return the *number* of distinct squares that can be formed using the points provided. Your program must return a correct solution for every possible input.

---

For example, take the input above but where the center square is missing:

```
...
. .
...

```

There are only two possible squares here (the big one and the diagonal one), so the program should return `2`.

---

The shortest code to do this in any language wins.

# Answer
> 7 votes
# Python, 95

Takes a list of coordinates from stdin.

```
l=input();print(sum((c-d+b,d+c-a)in l and(a-d+b,b+c-a)in l for a,b in l for c,d in l)-len(l))/4

```

Explanation:

> For each pair of points `(a,b)` and `(c,d)`, check if the square with additional points `(c-d+b,d+c-a)` and `(a-d+b,b+c-a)` is in the list. This counts each square 4 times, and each point once (when `(a,b) = (c,d)`), so subtracting the number of points and dividing by 4 gives the number of squares.

---
Tags: code-golf
---


title: Build a drug testing scheduler

text:
# Question
Title: Build a drug testing scheduler
In this problem on Puzzling.SE, I ask a question about determining the amounts of drug to use in a clinical test to minimize total drug usage and fulfill the requirements of the testing procedure.

The problem is as follows, for those of you who currently don't have access to the private beta:

> A medical researcher is trying to test the effect of a certain drug on mice. He is supposed to collect data for all doses from 1 to `2N` units, but only has the data collection resources for `N` tests. He has decided to only test dose amounts that are not multiples or factors of each other (for example, if he decided to use a dose of 15 units for a specific test, that would preclude tests for 1, 3, 5, 30, 45, etc. units). Moreover, because the drug is relatively expensive, he wants to use as little of the drug as he can manage to run these tests.
>
> How can he arrange the dosage amounts so that he ends up using all `N` test packages, **and the total units of dosage used in the tests are as low as possible**?

The original problem states `N = 25`. Your task is to build a program than can answer this question for *any* number of tests up to `N = 2500`.

Your program will take a number `N` from 1 to 2500 as input, and return a set of `N` integers between `1` and `2N` inclusive such that none of the `N` numbers are multiples of each other, each number from `1` to `2N` is a factor or multiple of at least one of the numbers in the set, and the sum of all the numbers in the set is as low as you can manage.

Your program must return a valid result for each value of `N` to be valid.

Your program will be scored by the sum of all the returned numbers for each scenario from `N = 1` to `N = 2500`. In the event of a tie, the shorter solution will win.

# Answer
## Javascript 5,955,958,211

I'm not sure if it is the optimal solution.
I used a brute-force method.

```
function f(n) {
  var o=[];
  for(var i=n;i--;) o.push(2*n-i); //init array from n+1 to 2*n

  for(i=n;i>0;i--) { //bruteforce on number from n to 1
    var index=0;
    var nbFactor=0;
    for(j=0;j<n;j++) {
      if((o[j]/i)%1==0) {
        index=j;
        nbFactor++;
      }
    }
    if(nbFactor==1) { //if there is only 1 factor, replace it by the new number
      o[index]=i;
    }
  }
  return o.sort(function(a,b){return a-b;});
}

```

Golfed (130) :

```
function f(n){o=[];for(i=n;i++<2*n;)o.push(i);for(i=n;i;i--){for(d=c=j=0;j<n;j++)if((o[j]/i)%1==0)d=j,c++;if(c==1)o[d]=i}return o}

```

Here is the result found by my algorithm for `25` :

> \[8, 12, 14, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 30, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49\]

Little piece of code to compute the score (takes approx. 200 seconds on Chrome) :

```
var result=0;
var t = Date.now();
for(var j=1;j<2501;j++) {
  result += f(j).reduce(function(r,e){return r+e;});
}
console.log("Score : " + result + "\nCompute time : " + ((Date.now()-t)/1000) + " seconds");

```
> 3 votes

# Answer
# JavaScript - 5,955,958,211

A tiny bit of pre-processing to generate the factors of 1 ... 5000

```
var factors = [];

for( var i = 1; i <= 5000; i++ )
{
    factors[i] = [];
    for( var j = 1; j <= i; j++ )
    {
        if ( i % j == 0 )
            factors[i].push(j);
    }
}

```

The main function:

```
function find_min_doses( N, DEBUG )
{
    var output = [];
    var factorCount = [];
    for( var i = 1; i <= 2*N; i++ )
    {
        factorCount[i]=0;
        for( var j = 0; j < factors[i].length; j++ )
        {
            factorCount[factors[i][j]]++;
        }
    }
    var changed = false;
    do
    {
        if ( DEBUG && changed )
        {
            console.log( output.sort( function(a,b){ return a-b; } ).toString()
                         + " = "
                         + output.reduce( function(p,c){ return p+c; } )
                       );
        }
        changed = false;

        var count = 0;
        for( var i = 1; i <= 2*N; i++ )
        {
            if ( factorCount[i] == 1 )
            {
                if ( count < N )
                {
                    output[count++] = i;
                }
                else
                {
                    for( var j = 0; j < factors[i].length; j++ )
                        factorCount[factors[i][j]]--;
                }
            }
        }

        for( var i = 0; i < N; i++ )
        {
            var o = output[i];
            var f = factors[o];
            for( var j = 0; j < f.length; j++ )
            {
                var v = f[j];
                if ( factorCount[v] == 2 )
                {
                    output[i]=v;
                    for( var k = 0; k < f.length; k++ )
                    {
                        factorCount[f[k]]--;
                    }
                    changed = true;
                    break;
                }
            }
        }
    }
    while( changed );

    return output.reduce( function(p,c){ return p+c; } );
}

```

A test harness:

```
var total = 0;
var time = new Date();
for ( var i = 1; i <= 2500; i++ )
{
    total += find_min_doses( i );
}
console.log( "Score: " + total + "\nTime: " + ((new Date()-time)/1000) + " seconds." );

```

**Output (Chrome)**

```
Score: 5955958211
Time: 1.438 seconds.

```

**Output (FireFox)**

```
Score: 5955958211
Time: 66.107 seconds.

```
> 2 votes

# Answer
# Prolog - 5,955,958,211 (?)

Its far too slow to run all 2500 test cases but it will find the optimal solution(s) in every case.

**Golfed - 370 Characters**

```
a([]).
a([_]).
a([H,N|T]):-H<N,a([N|T]).
s([],0).
s([H|T],S):-s(T,X),S is X+H.
e(_,[]).
e(V,[H|T]):-H mod V>0,e(V,T).
d([]).
d([H|T]):-e(H,T),d(T).
b(N,L):-T is 2*N,between(1,T,L).
l([H|T],M):-l(T,H,M).
l([],M,M).
l([H|T],C,M):-X is min(H,C),l(T,X,M).
m(R,M):-findall(T,s(R,T),L),l(L,M).
f(N):-length(R,N),maplist(b(N),R),a(R),d(R),m(R,M),s(R,M),write(R),nl,write(M),nl.

```

**Ungolfed**

```
ensure_sorted([]).                    % Ensures that the values of
ensure_sorted([_]).                   % a list are in ascending order.
ensure_sorted([Head,Next|Tail]):-
    Head<Next,
    ensure_sorted([Next|Tail]).

sum([Head|Tail],Total):-              % Calculate the sum of
    sum(Tail,Temp),                   % a list
    Total is Temp+Head.

ensure_not_divisor(_,[]).             % Ensure that the value
ensure_not_divisor(Val,[Head|Tail]):- % is not a divisor of
    Head mod Val > 0,                 % any numbers of the list.
    ensure_not_divisor(Val,Tail).

ensure_no_divisors([]).
ensure_no_divisors([Head|Tail]):-     % For each value of the list
    ensure_not_divisor(Head,Tail),    % ensure that it is not a divisor
    ensure_no_divisors(Tail).         % of the succeeding values.

btwn(N,List):-                        % Restrict the values to be
    Temp is 2*N,                      % between 1 and 2N
    between(1,Temp,List).

list_min([Head|Tail],Min):-           % Find the minimum value of
    list_min(Tail,Head,Min).          % the list.
list_min([],Min,Min).
list_min([Head|Tail],Current_Min,Min):-
    Temp is min(Head,Current_Min),
    list_min(Tail,Temp,Min).

min_sum(R,Min):-                      % For all the valid answers
    findall(Temp,sum(R,Temp),List),   % find the minimum sum.
    list_min(List,Min).

func(N):-
    length(R,N),                      % A list of N unknown values
    maplist(btwn(N),R),               % Restrict each value to integers 1..2N
    ensure_sorted(R),                 % Ensure the list is sorted.
    ensure_no_divisors(R),            % Ensure that each value is not a divisor of a higher value.
    min_sum(R,Min),                   % Find the minimum sum of all answers
    sum(R,Min),                       % Restrict the answer to have the minimum sum.
    write(R),nl,                      % Output the doses (and a newline).
    write(Min),nl.                    % Output the score (and a newline).

```
> 2 votes

# Answer
# Python – 7,818,751,250

As a last-place reference answer, consider the following:

```
def f(n):
    return range(n+1, n*2+1)

```

For any `N`, choosing unit sizes from `N+1` to `2N` will ensure that no number is a multiple or factor of any other, simply by virtue of the fact that they're too close together. The smallest nontrivial multiple of `N+1` is `2N+2`, and the largest nontrivial factor of `2N` is `N`, and no nontrivial multiple or factor of any number will fall between those two.

However, there will always be solutions that do much better than this – simply replacing `2N-2` with `N-1` already will always yield a better solution.
> 1 votes

---
Tags: code-challenge, optimization
---


title: Riffle Shuffle Golf Time

text:
# Question
Title: Riffle Shuffle Golf Time
Anyone who has spent any time around a deck of playing cards will recognize the riffle shuffle. The deck is cut in half and the two stacks are riffled simultaneously into the same pile before being tidied up in a sometimes visually appealing way.

This code-golf challenge is to write a function/method/(language equivalent) that performs the riffle shuffle on an array/stack/(language equivalent) of any size in the language of your choice.

As input, your function will except an array (language equivalent), plus how many times to run the shuffle. When done, it will return the shuffled array.

Your riffle shuffle function must implement the following algorithm:

1. Divide the `deck` into two `stacks`

A `stack` must have a minimum of 40% of the total `cards` in the `deck` and a maximum of 60%
2. Choose a random `stack` to start with
3. Drop 1 - 7 cards from the bottom of the `starting stack` to the top of the newly shuffled `deck`
4. Drop 1 - 7 cards from the bottom of the `other stack` to the top of the newly shuffled `deck`
5. Repeat #3 and #4 until only one `stack` remains
6. Drop the remaining `cards` from the remaining `stack` on top of the newly shuffled `deck`

Smallest character count will be chosen as the answer in 1 week (May 29th).

This is the sample deck of cards to use:

```
[
'AH', '2H', '3H', '4H', '5H', '6H', '7H', '8H', '9H', '10H', 'JH', 'QH', 'KH',
'AC', '2C', '3C', '4C', '5C', '6C', '7C', '8C', '9C', '10C', 'JC', 'QC', 'KC',
'KD', 'QD', 'JD', '10D', '9D', '8D', '7D', '6D', '5D', '4D', '3D', '2D', 'AD',
'KS', 'QS', 'JS', '10S', '9S', '8S', '7S', '6S', '5S', '4S', '3S', '2S', 'AS'
]

```

Your answer should contain:

* Code-golfed code
* What the sample deck looks like after being shuffled twice
* Un-golfed code

# Answer
> 1 votes
# Python (131)

Waaaay too long, even for something that came to be after a "careful" reading of the rules:

```
Drop 1 - 7 cards from the bottom of the starting stack to the top of the newly shuffled deck

```

Doens't actually say this should be random, so I'll just always drop 1 card.

```
Divide the deck into two stacks

A stack must have a minimum of 40% of the total cards in the deck and a maximum of 60%

```

Sure. I'll just always do about 50%.

Anyways, the code:

```
def s(d):
 b=[d.pop()for _ in range(len(d)/2)];r=[];b,d=(b,d)if id(4)%2 else(d,b)
 while b and d:r+=[b.pop(),d.pop()]
 return r+b+d

```

Sample output:

```
In [17]: s(s([
    ...: 'AH', '2H', '3H', '4H', '5H', '6H', '7H', '8H', '9H', '10H', 'JH', 'QH', 'KH',
    ...: 'AC', '2C', '3C', '4C', '5C', '6C', '7C', '8C', '9C', '10C', 'JC', 'QC', 'KC',
    ...: 'KD', 'QD', 'JD', '10D', '9D', '8D', '7D', '6D', '5D', '4D', '3D', '2D', 'AD',
    ...: 'KS', 'QS', 'JS', '10S', '9S', '8S', '7S', '6S', '5S', '4S', '3S', '2S', 'AS'
    ...: ]))
Out[17]:
['AD',
 'KH',
 'AC',
 'KS',
 '2D',
 'QH',
 '2C',
 'QS',
 '3D',
 'JH',
 '3C',
 'JS',
 '4D',
 '10H',
 '4C',
 '10S',
 '5D',
 '9H',
 '5C',
 '9S',
 '6D',
 '8H',
 '6C',
 '8S',
 '7D',
 '7H',
 '7C',
 '7S',
 '8D',
 '6H',
 '8C',
 '6S',
 '9D',
 '5H',
 '9C',
 '5S',
 '10D',
 '4H',
 '10C',
 '4S',
 'JD',
 '3H',
 'JC',
 '3S',
 'QD',
 '2H',
 'QC',
 '2S',
 'KD',
 'AH',
 'KC',
 'AS']

```

This is actually the code as I wrote it, I didn't specifically golfed any code. If you just want an explanation, please say so.

# Answer
> 0 votes
# Cobra - 307

Don't have access to a compiler atm, so this *should* work, but I'll be able to check later.

```
def f(d,n) as List<of int>
    r=Random()
    x=d.count
    for m in n
        p=q=[]
        for c in x
            if c%2>0,p.add(d.pop)
            else,q.add(d.pop)
        if r.next(0,2)>0,a,b=p,q
        else,a,b=q,p
        for c in x
            for z in r.next(0,7),if a.count>0,d.add(a.pop)
            for z in r.next(0,7),if b.count>0,d.add(b.pop)
    return d

```

# Answer
> 0 votes
# Python 84

## Golfed:

```
def s(d):
 e=len(d)/2;B=d[:e];C=d[e:];D=[]
 for x in range(e):D+=B[x],C[x]
 return D

```

## Output Deck:

```
['AH', 'AC', 'KD', 'KS', '2H', '2C', 'QD', 'QS', '3H', '3C', 'JD', 'JS', '4H', '4C', '10D', '10S', '5H', '5C', '9D', '9S', '6H', '6C', '8D', '8S', '7H', '7C', '7D', '7S', '8H', '8C', '6D', '6S', '9H', '9C', '5D', '5S', '10H', '10C', '4D', '4S', 'JH', 'JC', '3D', '3S', 'QH', 'QC', '2D', '2S', 'KH', 'KC', 'AD', 'AS']

```

## Un-golfed:

```
def Shuffle(Deck):
    Stack1 = Deck[:len(Deck)/2]            # 2nd Half of Deck
    Stack2 = Deck[len(Deck)/2:]            # 1st Half of Deck
    Output = []                            # Initialize Output List
    for index in range(len(Deck)/2):
        Output.append(Stack1[index])       # Append Output List with element from Stack1
        Output.append(Stack2[index])       # Append Output List with element from Stack2
    return Output                          # Return Output

```

Uses the same loopholes as @synthetica.

# Answer
> 0 votes
# Python, 69 chars (actually takes number of times to shuffle as input)

If one follows the algorithm, always picking 1 card at each step of 1-7 cards (as it wasn't explicitly said to have to be random), then with an array like:

```
[1, 2, 3, 4, 5, 6]

```

We have one of two results depending on which stack is picked first:

```
[1, 2, 3] [4, 5, 6] ==> [1, 4, 2, 5, 3, 6]
[4, 5, 6] [1, 2, 3] ==> [4, 1, 5, 2, 6, 3]

```

The following algorithm accomplishes this `n` times, using `id(b)%9>4` as a source of binary randomness\[1\]:

```
def s(d,n):
 for i in range(n):b=d[:];F=id(b)%9>4;d[F::2]=b[26:];d[1-F::2]=b[:26]

```

Sample output:

```
>>> o = ['AH', '2H', '3H', '4H', '5H', '6H', '7H', '8H', '9H', '10H', 'JH',
 'QH', 'KH', 'AC', '2C', '3C', '4C', '5C', '6C', '7C', '8C', '9C', '10C', 'JC',
 'QC', 'KC', 'KD', 'QD', 'JD', '10D', '9D', '8D', '7D', '6D', '5D', '4D', '3D',
 '2D', 'AD', 'KS', 'QS', 'JS', '10S', '9S', '8S', '7S', '6S', '5S', '4S', '3S',
 '2S', 'AS']
>>> d = o[:]; s(d, 2); d
['KD', 'KS', 'AH', 'AC', 'QD', 'QS', '2H', '2C', 'JD', 'JS', '3H', '3C', '10D', '10S', '4H', '4C', '9D', '9S', '5H', '5C', '8D', '8S', '6H', '6C', '7D', '7S', '7H', '7C', '6D', '6S', '8H', '8C', '5D', '5S', '9H', '9C', '4D', '4S', '10H', '10C', '3D', '3S', 'JH', 'JC', '2D', '2S', 'QH', 'QC', 'AD', 'AS', 'KH', 'KC']
>>> d = o[:]; s(d, 2); d
['AC', 'AH', 'KS', 'KD', '2C', '2H', 'QS', 'QD', '3C', '3H', 'JS', 'JD', '4C', '4H', '10S', '10D', '5C', '5H', '9S', '9D', '6C', '6H', '8S', '8D', '7C', '7H', '7S', '7D', '8C', '8H', '6S', '6D', '9C', '9H', '5S', '5D', '10C', '10H', '4S', '4D', 'JC', 'JH', '3S', '3D', 'QC', 'QH', '2S', '2D', 'KC', 'KH', 'AS', 'AD']

```

\[1\] This gives about a 44.4%/55.5% skew:

```
>>> r = {0: 0, 1: 0}
>>> for i in range(1000000):
        r[int(id(i)%9>4)]+=1
>>> r
{0: 555517, 1: 444483}

```

For two extra characters we can get a much better 50.5%/49.5% result:

```
>>> r = {0: 0, 1: 0}
>>> for i in range(1000000):
        r[int(id(i)%99>49)]+=1
>>> r
{0: 505050, 1: 494950}

```

---
Tags: code-golf, function
---


title: Giant Babylonian Matrices

text:
# Question
Title: Giant Babylonian Matrices
### Introduction

The Babylonians had a clever method for finding square roots. To find the square root of a number `N`, you start with a `guess`, then refine it by repeatedly evaluating a line of computer code (or papyrus scroll equivalent):

```
guess = (guess + N/guess) / 2

```

If the guess is smaller than sqrt(N), N/guess must be larger than sqrt(N), so averaging these two terms should get you closer to the true answer. It turns out this method converges fairly quickly to the correct answer:

```
N = 7
guess = 1
guess = 4.0
guess = 2.875
guess = 2.65489
guess = 2.64577
guess = 2.64575
guess = 2.64575

```

### Extension

Does an equivalent algorithm exist for matrices? Throwing all mathematical rigor aside, if we wish to find the 'square root' of a square matrix `M`, we may again start with a `guess`, then refine it by repeatedly evaluating a line of code:

```
guess = (guess + inverse(guess)*M) / 2

```

where inverse() is the matrix inverse function, and * is matrix multiplication. Instead of 1, our initial guess is an identity matrix of the appropriate size.

However, convergence is no longer guaranteed - the algorithm diverges for most (but not all) inputs. If M produces a convergent series, it is a **Babylonian matrix**. Furthermore, the converged value is actually the real square root of the matrix (i.e., `guess*guess = M`).

### Example

Here's an example using a 2x2 matrix, showing convergence of the series:

```
M = [[7,2],[3,4]]
guess = [[1.,      0.      ], [0.,       1.     ]]  <-- 2x2 identity matrix
guess = [[4.,      1.      ], [1.5,      2.5    ]]
guess = [[2.85294, 0.558824], [0.838235, 2.01471]]
guess = [[2.60335, 0.449328], [0.673992, 1.92936]]
guess = [[2.58956, 0.443035], [0.664553, 1.92501]]
guess = [[2.58952, 0.443016], [0.664523, 1.92499]]
guess = [[2.58952, 0.443016], [0.664523, 1.92499]]

```

After only a few iterations, the series converges to within 1e-9. After a while, it grows unstable as rounding errors add up, but the initial stability is demonstrated, which is sufficient.

### Task

Your job is to find a square matrix `M`, populated by the integers 1 through 9, which, when given an initial guess of an identity matrix of the proper size, converges successfully. Matrices should be submitted as comma-delimited text (or attached text files, if they are too large), with either brackets or newlines separating subsequent rows.

### Rules

Even though the matrix M and starting guess use integers (mainly for display convenience), all arithmetic should be conducted using double-precision floating point. Integer-specific operators (such as 3/2 evaluating to 1) are prohibited.

Divide-by-zero errors, singular matrices, and over/underflows cannot be used to coerce a sequence into 'converging'. The values must be proper floating-point numbers at all times to be considered to have converged.

The algorithm is considered to have converged if an iteration produces no change larger than 1e-9, in any individual cell.

You may use external mathematics libraries for matrix inversion (no need to reinvent the wheel).

### Win Condition

The winner is the largest submitted valid Babylonian matrix made of integers 1-9, after one week. You must also submit the code you used to find the matrix.

# Answer
We produce such a matrix of any dimension `n`. It is simply a matrix of all 1's except 2's on the diagonal.

```
r = range(n)
M = [[1 + (i==j) for i in r] for j in r]

```

Example:

```
n=5
M=[[2 1 1 1 1]
   [1 2 1 1 1]
   [1 1 2 1 1]
   [1 1 1 2 1]
   [1 1 1 1 2]]

 #Within 10 steps, the procedure converges to the matrix's square root
  [[ 1.28989795  0.28989795  0.28989795  0.28989795  0.28989795]
   [ 0.28989795  1.28989795  0.28989795  0.28989795  0.28989795]
   [ 0.28989795  0.28989795  1.28989795  0.28989795  0.28989795]
   [ 0.28989795  0.28989795  0.28989795  1.28989795  0.28989795]
   [ 0.28989795  0.28989795  0.28989795  0.28989795  1.28989795]]

```

In general, the procedure converges for matrices with positive real eigenvalues. This is because if we work in the basis of eigenvectors of the original matrix, it and all its iterates are diagonal matrices, and we can view the procedure as applying the Babylonian method to each individual diagonal entry. The starting matrix is the still the identity in this basis.

Since the Babylonian method converges only if the original value was positive, the matrix version converges when every eigenvalue is real and positive. I'm not sure what happens for complex eigenvalues.

I constructed the given matrix to have positive eigenvalues as follows. First, start with the matrix of all ones, which is rank-1, and so has a single eigenvalue (of n) and all others 0. Then, add the identity, which shifts the eigenvalues up by 1 to get (n+1,1,1,...,1). Iterating makes the eigenvalues converge to (sqrt(n+1),1,1,...,1). Note that the 1's are unchanged by each iteration.
> 5 votes

# Answer
Here's a 10x10 Babylonian matrix as a first target:

```
[[9, 8, 6, 5, 1, 1, 6, 7, 1, 6],
 [8, 7, 4, 9, 9, 5, 4, 8, 5, 9],
 [7, 1, 8, 8, 6, 8, 6, 6, 4, 1],
 [7, 8, 9, 9, 5, 1, 1, 6, 9, 9],
 [6, 9, 3, 4, 1, 9, 1, 7, 4, 9],
 [9, 1, 1, 1, 5, 4, 5, 6, 7, 1],
 [8, 6, 8, 2, 4, 4, 6, 8, 2, 2],
 [5, 4, 9, 3, 3, 5, 5, 6, 4, 1],
 [2, 4, 4, 8, 6, 8, 3, 3, 7, 6],
 [3, 9, 9, 7, 7, 9, 6, 5, 1, 8]]

```

which converges to

```
[[3.20594, 1.60102, 0.237288, -0.0745693, -1.07811, -0.255869, -0.0182269, 1.70256, 0.355871, 1.11176],
 [0.62321, 1.19922, -0.514309, 2.2604, 1.96759, 1.41485, -0.066537, 1.37868, -0.613093, 1.35704],
 [0.919805, 0.453479, 2.54444, 0.717525, -0.00569383, 1.54527, 0.131113, 0.916813, 0.443482, -0.0251371],
 [0.163383, -0.597711, 0.751538, 3.69952, 2.37728, -0.578767, 1.24375, -0.0922065, 0.749781, 0.623908],
 [2.27446, 2.7975, 0.171454, -1.6263, -1.12639, 1.22686, -2.69745, 2.36239, 1.6901, 2.1349],
 [0.669566, -1.57916, -0.722141, 1.35884, 2.43496, 2.25887, 2.01205, 0.241215, 0.342665, -0.714146],
 [0.50365, 0.472729, 1.37547, 0.32966, 1.36842, 0.0550458, 2.90591, 0.520055, -0.257277, -0.347814],
 [0.205106, 0.286162, 1.89821, 0.141372, 0.521793, 0.0638244, 1.65691, 1.04034, 0.81816, -0.30955],
 [0.0679229, 1.01126, 0.553701, 0.627696, -0.0400446, 1.21608, -0.397756, 0.35419, 2.38639, 1.08573],
 [-0.200249, 2.31035, 1.89905, -0.124084, 0.0398479, 0.454703, 1.08552, -0.152166, 0.408594, 2.31063]]

```

and was found with this Mathematica code:

```
n = 10;
M = RandomInteger[{1, 9}, {n, n}];
guess = IdentityMatrix[n] // N;
result = NestList[(# + Inverse[#].M)/2 &, guess, 32];
ListPlot[Transpose[Flatten /@ result], Joined -> True]
M // MatrixForm

```
> 0 votes

---
Tags: code-challenge, math, sequence
---


title: Print the Golden Ratio

text:
# Question
Title: Print the Golden Ratio
This was fun! However with only three digits, the fun was over way too soon. This challenge is similar, but we'll keep the fun going.

## The Challenge

> Print as many digits of the Golden Ratio φ as possible. The Golden Ratio is defined as the number that satisfies φ = (φ + 1)/φ and the first 100 digits are given by:
>
> 1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911375...
>
> *This challenge is **not** about computing φ!* It's about printing as many digits as possible without using any method for doing that twice. So find as many creative ways to get your digits as you can!

## Restrictions

By itself, printing the digits of φ would be a bit too simple, so here are the rules:

1. **You have to construct the number *in order* from left to right**, either by printing it piece by piece or by constructing a string from left to right and printing it at the end - you could even generate an array of digit characters and then join it and print it, as long as you do it in order. In the following rules "print" and "output" may refer to any of those processes (e.g. if you're building a string, and the string contains `1.6` that counts as having `1.6` already printed).
2. For your code **you get a budget of *15 characters per digit***. The period does not count towards that budget, but has to be printed as well. Note that the restriction is only on total code size: you may use more than 15 characters for any digit as long as you don't use more on average. In fact, you may build up a "debt" in characters and "pay it off" later. E.g. to print `1.618` you have **60** characters.
3. **Standard-library includes/imports do not count towards the code size.** But you can't give those includes shorthand aliases for free!
4. **You must not use the digit you are currently generating, nor any you have already printed.** E.g. `1` may appear nowhere in your source code, because it's the very first digit. The code that outputs the `8` in `1.618` may use any or all of the digits `[0234579]`, but none of `[168]`. For this purpose, **all literals that are equivalent to a *single* digit are treated *as that digit***. So if your language can represent `9` as `'\t'` you are not allowed to use that anywhere, where you couldn't use an `9` instead.
5. **You must not produce multiple digits at once.** It should be possible to clearly split your code into chunks that generate one digit a time.
6. **You must not refer to any *built-in* function, mathematical/boolean/bit-wise/string operator, variable or constant which you have used in code that generated an earlier digit.** Exceptions are integer-to-string conversion, string concatenation and printing functions which you might need for every single digits. Note that it doesn't matter by which *name* you refer to any built-in: just because you alias a built-in `PI` to both `p` and `q` doesn't mean you get to use `p` once and `q` once. Likewise, you *are* allowed to use a name twice if it refers to two different built-ins, like string `length` and array `length`.

If your programming language doesn't have functions use your best judgement on what the equivalent would be - e.g. for bash scripting, invoking other programs should follow the rules imposed on functions
7. **Your submission must be written in a single language.** So no executing another language's interpreter to get access to that language's built-ins as well.

## Implications

The following points are all implied by the above rules, but I add them here to avoid questions that have already come up in the sandbox:

* You're not allowed to overwrite parts of your output by printing some backspaces (usually `'\b'`) in between.
* Loops which generate/output multiple digits are forbidden. (Loops that compute a single digit are fine, though.)
* Using an obfuscated version `(1 + √5)/2` or dividing Fibonacci numbers to obtain more than a single digit is forbidden.
* You cannot precalculate the 10 digits and store them in 10 variables and then just refer to those, because those variable references don't *generate* the digit - the code that fills the variable does, so this is a violation of rule 6.
* In fact, you can't reuse any previous (or intermediate results), because that would mean two digits would share code for being *generated*.
* Otherwise, you can use any means whatsoever (which do not have to purely mathematical) to generate the digits. (And you should!)
* In fact there is no need to calculate anything, if you can pull out the correct digits from many different places using your standard library.
* You *may* use an operator multiple times while generating a single digit, so `2+2+2` is fair game to generate the first `6` (although it's unlikely the shortest).
* You *may* use any literal as often as you want, because they are not built-in constants. So as long as you don't have to print `5`, you can as many `5`s in your code as you want.
* You can't hardcode the output, because that would involve using the digits you are outputting.

In short: don't use any method of generating digits twice and don't use the digit you are currently outputting or any have already printed.

If you do spot a loophole which allows you to get a (quasi-)infinite score, please don't ruin the challenge by exploiting it, but let me know so I can see if the loophole can be fixed without breaking anything.

## Scoring

The program that prints the highest number of digits correctly wins. In case of a tie the shorter code breaks the tie.

Please add an ungolfed commented version that identifies which part of your code generates which digit.

PS: If anyone beats the 100 digits above, here are some more.

# Answer
> 19 votes
# PHP, 100 digits

I'm probably bending the rules a bit here, but PHP has dozens of constants to choose from:

```
<?php
echo TRUE . '.' . PM_STR . DNS_A . MSG_EOR . LC_ALL . T_FMT . LOCK_UN . SQL_DATE
. E_NOTICE . IMG_WBMP . INI_ALL . E_PARSE . SOCKET_EBADF . LOG_USER .
IMAGETYPE_JPC . IMG_PNG . GLOB_MARK . LOCK_NB . LOG_NDELAY . D_FMT . PHP_ZTS .
GLOB_ERR . AM_STR . SQL_DOUBLE . SOL_TCP . FILE_APPEND . LOG_ERR . SORT_ASC .
SOCK_RAW . LOG_INFO . LC_TIME . SQL_FLOAT . SORT_DESC . INFO_MODULES . E_ERROR .
IMG_GIF . SQL_REAL . LOG_DEBUG . DNS_NS . CODESET . CAL_FRENCH . CURLE_OK .
LDAP_OPT_RESTART . LOCK_SH . XML_PI_NODE . SQLITE_INTERRUPT . MYSQLI_ASYNC .
CURLM_OK . SNMP_NULL . SQLITE_NOMEM . LC_MESSAGES . IMG_JPG . SO_KEEPALIVE .
SOCKET_ENXIO . LOCK_EX . D_T_FMT . ENT_QUOTES . LOG_NOTICE . SOCK_RDM .
INPUT_ENV . CURLAUTH_NTLM . INPUT_SESSION . AF_INET . IMG_JPEG . SQL_CONCURRENCY
. SEEK_SET . SOCKET_EIO . LC_CTYPE . PHP_URL_QUERY . LOG_KERN . INI_SYSTEM .
IMAGETYPE_BMP . SEEK_END . JSON_HEX_QUOT . LOG_PID . LIBXML_DTDATTR .
XML_DOCUMENT_NODE . PHP_DEBUG . LOG_CRIT . ENT_IGNORE . LC_NUMERIC .
DOM_NOT_SUPPORTED_ERR . PHP_URL_FRAGMENT . FILE_TEXT . IMAGETYPE_TIFF_II .
LOG_CONS . LOG_EMERG . UPLOAD_ERR_CANT_WRITE . MSG_PEEK . SQLITE_OK . FNM_PERIOD
. AF_UNIX . CURLPROTO_FTPS . STREAM_NOTIFY_FAILURE . MYSQL_BOTH .
CURLE_FTP_ACCESS_DENIED . MSG_OOB . FTP_TEXT . LC_MONETARY .
CURLE_COULDNT_CONNECT . SQLITE_BUSY . "\n";

```

This probably isn't very portable code, but it works fine on my system. Here's the code that generated it:

```
<?php
$phi = "6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911375";
echo "<?php\necho TRUE . '.' . ";
$consts = get_defined_constants();
foreach($consts as $k=>$v) if (preg_match('/\d|TRUE|PHP_EOL/',$k)) unset($consts[$k]);
for ($p=0;$p<strlen($phi);$p++) {
  $d = ord($phi[$p]) - 48;
  $min = 999;
  foreach($consts as $k=>$v) {
    if (strlen("$v")==1 && $v==$d && strlen($k)<$min) {
      $min = strlen($k);
      $maxk = $k;
    }
  }
  if ($min==999) break;
  echo "$maxk . ";
  unset($consts[$maxk]);
}
echo "\"\\n\";\n";

```

# Answer
> 11 votes
## Perl - 37 digits

```
use Math::Trig;
use POSIX;

print
  !0,'.',chop$=||$=,A==A,2**3,$|,++$^F,75/5/5,pi*pi%\_,4+4,a^Y,w&'?',~"\xcb",$^=~y/_//c,
  ord"\b",unpack(h,"\t").@{[c,c,c,c]},$#{[b..j]},"$^W"|'$',$^H>>log$^H,cos()- -cos,$[,
  $-=sqrt%SIG,$%=$],$+[*$=~/($)/],split('',$~).map(glob,"{,,,}{,}"),index(\L,L),
  exp(exp)<<exp,ceil(sinh acosh$^C).keys{stat$0},rindex(\R,R),($s=ssssss)=~s/s//g,
  $?=acos(--$z),$^T=pack(u,$^T.$^T.TTTT),B~~B,C<=C,length$^V,

```

392 bytes currently, (10.6 per digit).

Output:

```
1.618033988749894848204586834365638117

```

---

**Self-imposed Restrictions**

I've added a few additional restrictions to limit the use of language features that would trivialize the problem. For example, array dereference `@{...}` and array final index `$#{...}` are only used once. Each array used is generated in a different manner (compare `[c,c,c,c]`, `[b..j]`, `split('',$~)`, `map(glob,"{,,,}{,}")`). Additionally, no symbol or bareword is used more than once, although this is explicitly allowed in the challenge description. I think it's a good idea for perl (or any language with int-only special variables (are there any others?)), because it limits the number of implicit int conversions.

---

**Pieces**

```
!0                       # returns 1
'.'
chop$=||$=               # $= is 60, chop the 0, returns 6
A==A                     # returns 1 (because 0==0)
2**3                     # returns 8
$|                       # auto flush, returns 0
++$^F                    # max system filehandle pre-incremented, returns 3
75/5/5                   # returns 3
pi*pi%\_                 # pi² mod a large value, returns 9
4+4                      # returns 8
a^Y                      # bitwise 'a' xor 'Y', returns 8
w&'?'                    # bitwise 'w' and '?', returns 7
~"\xcb"                  # bitwise inversion of char 203, returns 4
$^=~y/_//c               # count non-underscores in $^, returns 9

ord"\b"                  # returns 8
unpack(h,"\t")           # unpack "\t" as a hex nibble, returns 9
@{[c,c,c,c]}             # anonymous array, returns 4 in scalar context
$#{[b..j]}               # final index of the range b..j, returns 8
"$^W"|'$'                # bitwise '0' or '$', returns 4
$^H>>log$^H              # $^H is 256, log$^H is ~5, returns 8
cos()- -cos              # cos(undef) is 1, subtract -1, returns 2
$[                       # array start index, returns 0

$-=sqrt%SIG              # set $- to sqrt(23), returns 4
$%=$]                    # set $% to the version number, returns 5
$+[*$=~/($)/]            # match end on *$ (aka *main::$), returns 8
split('',$~)             # split "STDOUT" into chars, returns 6 in scalar context
map(glob,"{,,,}{,}")     # an array of 8 empty strings, returns 8 in scalar context
index(\L,L)              # finds 'L' in 'SCALAR(...)', returns 3

exp(exp)<<exp            # 2.718281828 << 1, returns 4
ceil(sinh acosh$^C)      # ceil(2.30129...), returns 3
keys{stat$0}             # stat$0 is an array with 13 entries, which has 6 keys when
                         # interpreted as a hash, returns 6 in scalar context
rindex(\R,R)             # finds 'R' in 'SCALAR(...)' in reverse, returns 5
($s=ssssss)=~s/s//g      # replace the every 's' in 'ssssss' with nothing, returns 6

$?=acos(--$z)            # set $? to 3.14159... implicit int conversion, returns 3
$^T=pack(u,$^T.$^T.TTTT) # set $^T to "8,30P,...", returns 8
B~~B                     # returns 1 (because B represents the same thing as B)
C<=C                     # returns 1 (because 0<=0)
length$^V                # string length of $^V, returns 7

```

# Answer
> 8 votes
### Python 2.7, 19 digits, 231 relevant chars

```
from math import ceil, pi, trunc, gamma, sin

print ''.join(map(str,
[33-32,
chr(46),
~-7,
8>>3,
trunc(gamma(4.3)),
'x'.find('x'),
22/7,
range(4).pop(),
len('am I phi?'),
52%44,
2*4,
5|2,
ord('/'),
'\b',
5+2+2,
2<<2,
eval("5+2+2"),
ceil(pi),
'\b',
'\b',
str(sin(5))[5],
5&52]))

```

# Answer
> 6 votes
# Ruby 2.1 for 54 digits, 808 characters

```
#!ruby -rdate -rdigest -ropenssl -rprime -rset -rsocket
print 2/2,?.,9-3,3&5,2*4,2^2,7%4,55>>4,5+4,2<<2,-~7,5|2,2**2,(2r+2+5).to_i,(2.2+5).ceil,(55r/5-2).floor,(2.2*2).to_i,(2r*2*2).ceil,(2.2**2).floor,2.to_bn<<2,__LINE__,$<.to_i,IO::LOCK_NB,Errno::EIO::Errno,File::APPEND,'aaaaaa'.size,?a.encoding.name.sub(/\D+/,''),%w[a a a].size,%w[a b c d].to_set.size,%w[a a a].count,Socket::AF_NS,Date.jd(Date::ITALY).wday,*Digest::MD5.digest(?j).scan(/\d/),Set[?a,?b,?c].count,SignalException.new('FPE').signo,Float::ROUNDS,begin
exit false
rescue Object
$!.status
end,Process::RLIMIT_NPROC,:aaaaaaa.size,Prime.first,?/.next,{a:p,b:p,c:p}.size,STDIN.lineno,?a.crypt('at')[/\d/],{a: :a}.find_index([:a,:a]),/b/=~'aaaaaaaaab',[?a,?b].index(?b),:aaaaaaab=~/b/,?\t.ord,'aaaaaaaab'=~/b/,open(?/).pos,'aaaaab'.index(?b),?\a.bytes{|b|break b},'aaaaaaa'.rindex(?a),%w[a a].map.size

```

This program works with `ruby 2.1.0p0 (2013-12-25 revision 44422) [x86_64-openbsd]`. Systems other than OpenBSD 5.5 might have different values for a few digits.

## Interpretations

The restrictions of this challenge, especially restriction 6, are not precise for Ruby. So I add my own interpretations:

1. **The parentheses, dot and double-colon are not operators.** The parentheses just change the order of operations. The dot calls methods, as in `$<.fileno`, and the double colon gets constants, as in `IO::LOCK_NB`. The name of the method or constant is part of the operation. Because `()` `.` `::` are not operators, I do not apply restriction 6 to them. I may reuse them to generate more digits.
2. **A method with a different implementation is a different method.** For example, `Array#count` and `Enumerable#count` are not the same function for restriction 6. Both methods act the same, but `Array#count` overrides `Enumerable#count` with a different implementation. If I use `Array#count` to generate one digit, I may use `Enumerable#count` to generate another digit.
3. **Class#new is one method.** In Ruby, `Mutex.new`, `Random.new`, `Time.new` and so on refer to the same method, `Class#new`. I use `SignalException.new` to generate one digit. Because of restriction 6, I may never again use `Class#new`.
4. **Constants for classes or modules are still constants.** In Ruby, class names like `Float` and `IO` are constants! I use `IO::LOCK_NB` to generate one digit. Because of restriction 6, I may never again use `IO`. This interpretation binds only Ruby, and not other languages where package names are not constants.
5. **Literals are not constants.** Though 2 is a mathematical constant (independent of any variables), it is not a constant in Ruby. I do not apply restriction 6 to literals, and I may reuse the literal 2 for more than one digit.
6. **Literals are not operators.** I do not apply restriction 6 to the brackets or quotes that form literal arrays, hashes, regular expressions, or strings, as in `[]` `{}` `//` `''`. I may always use such literals to generate more digits.
7. **Two constants with the same value are the same constant.** `File::APPEND` and `IPSocket::LOCK_UN` are two names for the same number 8. Restriction 6 says, "it doesn't matter by which *name* you refer to any built-in." Because `File::APPEND` and `IPSocket::LOCK_UN` differ only by name, they must be the same constant, so I may not use them for two digits.
8. **Two digits may not refer to the same global variable.** This closes a loophole. Restriction 6 only applies to functions, operators and constants. Restriction 4 only applies to literals. `$SAFE` is a built-in global variable, not a function, operator, constant, nor literal. `$SAFE` has the value 0. With the loophole, I can reuse `$SAFE` to generate every digit 0 in the program. I close the loophole by interpreting restriction 6 to also restrict global variables.

## Comments

The first line is `#!ruby -rdate -rdigest -ropenssl -rprime -rset -rsocket`. Ruby parses this line and loads six parts of its standard library, as if by `require 'date'`, `require 'digest'` and so on. I do not count these 56 characters, because restriction 3 exempts "standard library imports/includes".

The rest of the program calls `print` with a long list of arguments, to convert them to strings and print them in order. The arguments are these:

1. `1` from `2/2`: division *Fixnum#/*
`.` from `?.`: literal single-character string
2. `6` from `9-3`: subtraction *Fixnum#-*
3. `1` from `3&5`: bitwise and *Fixnum#&*
    * By interpretation 5, I may use `3` again.
4. `8` from `2*4`: multiplication *Fixnum#\**
5. `0` from `2^2`: bitwise exclusive-or *Fixnum#^*
6. `3` from `7%4`: modulus *Fixnum#%*
7. `3` from `55>>4`: right shift *Fixnum#\>\>*
8. `9` from `5+4`: addition *Fixnum#+*
9. `8` from `2<<2`: left shift *Fixnum#\<\<*
10. `8` from `-~7`: negation of complement *Fixnum#-@ Fixnum#~*
    * Subtraction *Fixnum#-* and negation *Fixnum#-@* are different methods.
11. `7` from `5|2`: bitwise or *Fixnum#|*
12. `4` from `2**2`: exponentiation *Fixnum#\***
13. `9` from `(2r+2+5).to_i`: rational addition *Rational#+ Rational#to\_i*
    * By interpretation 2, *Fixnum#+* and *Rational#+* are different methods. They both add numbers, but they have different implementations, starting from different types for the left number.
    * Rational literals like `2r` are new in Ruby 2.1. `2r+2` calls *Rational#+* and returns another rational; `2r+2+5` calls *Rational#+* again.
    * Ruby prints rationals like `2/1` and floats like `2.0`. To fix this, I convert to integer: *to\_i* rounds toward zero, *ceil* rounds up, *floor* rounds down.
14. `8` from `(2.2+5).ceil`: float addition *Float#+ Float#ceil*
    * By interpretation 1, I may use parentheses `()` and dot `.` again.
15. `9` from `(55r/5-2).floor`: rational division and subtraction *Rational#/ Rational#- Rational#floor*
16. `4` from `(2.2*2).to_i`: float multiplication *Float#\* Float#to\_i*
17. `8` from `(2r*2*2).ceil`: rational multiplication *Rational#\* Rational#ceil*
18. `4` from `(2.2**2).floor`: rational exponentiation *Rational#\***
19. `8` from `2.to_bn<<2`: left shift with OpenSSL big number *Fixnum#to\_bn OpenSSL::BN#\<\<*
20. `2` from `__LINE__`: magic constant for current line number
21. `0` from `$<.to_i`: file descriptor of standard input *IO#to\_i*
22. `4` from `IO::LOCK_NB`: flag for non-blocking file lock
    * This is the first of many constants to depend on system. OpenBSD has 4.
    * By interpretation 4, I may no longer use `IO`. By interpretation 7, I may no longer use any constant with the value of 4.
23. `5` from `Errno::EIO::Errno`: number for input/output error
24. `8` from `File::APPEND`: flag to append to a file
    * This is a loophole around interpretation 4. I may not use `IO`, but `File` inherits constants from `IO`, so `File::APPEND` is a different way to get `IO::APPEND`.
25. `6` from `'aaaaaa'.size`: length of string *String#size*
26. `8` from `?a.encoding.name.sub(/\D+/,'')`: part of name of encoding *String#encoding Encoding#name String#sub*
    * By interpretation 6, I may use string quotes again.
    * Since Ruby 2.0, the default encoding is UTF-8. I take the name "UTF-8" and substitute /\D+/ matching "UTF-" with an empty string. This yields "8".
27. `3` from `%w[a a a].size`: length of array *Array#size*
28. `4` from `%w[a b c d].to_set.size`: number of elements in set *Array#to\_set Set#size*
29. `3` from `%w[a a a].count`: count all elements *Array#count*
    * The difference between *Array#size* and *Array#count* is that the latter takes optional arguments to choose which elements to count. I pass no arguments, so it counts all elements.
30. `6` from `Socket::AF_NS`: number for NS address family
31. `5` from `Date.jd(Date::ITALY).wday`: weekday number for Friday 15 October 1582, when Italy switched to Gregorian calendar *Date::jd Date#wday*
32. `6` from `*Digest::MD5.digest(?j).scan(/\d/)`: first ASCII digit in binary MD5 digest of "j" *Digest::MD5::digest String#scan*
    * *String#scan* returns an array of all matches. The `*` passes the array elements as arguments to `print`. This array is \["6"\].
33. `3` from `Set[?a,?b,?c].count`: count all elements *Set::\[\] Enumerable#count*
    * By interpretation 2, *Array#count* and *Enumerable#count* are different methods.
34. `8` from `SignalException.new('FPE').signo`: number of SIGFPE *Class#new SignalException#signo*
35. `1` from `Float::ROUNDS`: rounding mode, here 1 for round-to-nearest
36. `1` from `begin` (newline) `exit false` (newline) `rescue Object` (newline) `$!.status` (newline) `end`: exit status for failure
    * This is the same value as `SystemExit.new(false).status`, but by interpretation 3, I may no longer call *Class#new*. Instead I raise and rescue a SystemExit.
37. `7` from `Process::RLIMIT_NPROC`: number for resource limit for number of processes for one user
38. `7` from `:aaaaaaa.size`: length of symbol *Symbol#size*
39. `2` from `Prime.first`: first prime number *Enumerable#first*
40. `0` from `?/.next`: next string after "?" *String#next*
41. `3` from `{a:p,b:p,c:p}.size`: length of hash *Hash#size String#p*
42. `0` from `STDIN.lineno`: current line number for standard input *IO#lineno*
    * By interpretation 8, I may not reuse `$<`. I use `STDIN`. The difference is that `$<` is a global variable and `STDIN` is a constant. A program may set `$<` to a different input, but `STDIN` is always the original value of `$<`.
43. `3` from `?a.crypt('at')[/\d/]`: first ASCII digit in encrypted password *String#crypt String#\[\]*
    * System with different crypt() function will give different result.
44. `0` from `{a: :a}.find_index([:a,:a])`: index of first key :a, value :a in hash *Enumerable#find\_index*
    * I use a hash, not an array, because *Array#find\_index* is an alias for *Array#index*, which I plan to use soon.
45. `9` from `/b/=~'aaaaaaaaab'`: index where string matches /b/ *Regexp#=~*
46. `1` from `[?a,?b].index(?b)`: index of first "b" in array *Array#index*
47. `7` from `:aaaaaaab=~/b/`: index where symbol matches /b/ *Symbol#=~*
48. `9` from `?\t.ord`: ASCII value of tab "\t" *String#ord*
49. `8` from `'aaaaaaaab'=~/b/`: index where string matches /b/ *String#=~*
    * By interpretation 2, *Regexp#=~* and *String#=~* are different methods.
50. `0` from `open(?/).pos`: position in file after opening root directory "/" as a file *Kernel#open IO#pos*
51. `5` from `'aaaaab'.index(?b)`: index of first "b" in string *String#index*
52. `7` from `?\a.bytes{|b|break b}`: ASCII value of alert "\a" *String#bytes*
    * This works by iterating the bytes in "\a", but breaking the loop by returning the first byte.
53. `6` from `'aaaaaaa'.rindex(?a)`: index of last "a" in string *String#rindex*
54. `2` from `%w[a a].map.size`: size of enumerator that maps from array *Array#map Enumerator#size*

# Answer
> 5 votes
# Java, 21 digits, 276 characters

```
class C{public static void main(String[]a){System.out.print((3&5)+"."+(2|4)+Byte.BYTES+2*4+"".length()+(7-4)+~-4+(7+2)+(2<<2)+(int)Math.sqrt('@')+(2^5)+(int)Math.pow(2,2)+32%23+Byte.SIZE+('$'>>2)+Float.BYTES+Long.BYTES+Integer.BYTES+Double.BYTES+Short.BYTES+Math.round(.2));}}

class C {
  public static void main(String[] a) {
    System.out.print(
      (3&5)+       // 1
      "."+         // .
      (2|4)+       // 6
      Byte.BYTES+  // 1
      2*4+         // 8
      "".length()+ // 0
      (7-4)+       // 3
      ~-4+         // 3
      (7+2)+       // 9
      (2<<2)+      // 8
      (int)Math.sqrt('@')+  // 8
      (2^5)+       // 7
      (int)Math.pow(2,2)+   // 4
      32%32+       // 9
      Byte.SIZE    // 8

      // rest of explanation to come later today
    );
  }
}

```

# Answer
> 4 votes
# Ruby, 74 chars, 10 digits

It's just a start; I have to go so I will improve it later.

```
$><<[3-2,?.,3+3,?..size,2**3,$*.size,24/8,7%4,[*7..77][2],2*4,7.next].join

```

I have 76 characters saved up for later, when it will get more difficult!

# Answer
> 3 votes
# Ruby, 17 digits, 168 bytes

```
$><<[-~0,'.',9-3,3/3,2**3,$.,25%22,'   '=~/$/,2+7,2<<2,"10".oct,2|5,[2,2,2,2].size,[*$....2*5].last,(2^5).succ,'a'.to_i(25).pred,'aaaa'.count('a'),eval(55.chr.next)]*''

```

Ungolfed:

```
$><<[
  -~0,                # 1
  '.',                # .
  9-3,                # 6
  3/3,                # 1
  2**3,               # 8
  $.,                 # 0
  25%22,              # 3
  '   '=~/$/,         # 3
  2+7,                # 9
  2<<2,               # 8
  "#{'a'.hex}".oct,   # 8
  2|5,                # 7
  [2,2,2,2].size,     # 4
  [*$....2*5].last,   # 9
  (2^5).succ,         # 8
  'a'.to_i(25).pred,  # 9
  'aaaa'.count('a'),  # 4
  eval(55.chr.next)   # 8
]*''

```

Haven't been forced to do anything particularly clever yet, I may come back and add digits.

# Answer
> 2 votes
# Golfscript, 17 digits

A straightforward attempt. Golfscript may have a lot of non-alphanumeric one-letter built-ins, but it doesn't have many built-ins as a whole!

```
".",                         # 1: string length (separate from array length)
'.'
3 3+                         # 6: addition
''[49]+                      # 1: string concatenation
-9~                          # 8: bitwise not
2!                           # 0: boolean not
7 4%                         # 3: modulus
4(                           # 3: decrement
7))                          # 9: increment
257 2/2/2/2/2/               # 8: division
4 2*                         # 8: multiplication
22 5- 5- 5-                  # 7: subtraction
2 2?                         # 4: power
[2 5] 2 base                 # 9: base conversion
[2 2 2 2 2 2 2 2],           # 8: array length (separate from str length)
[2 2 2 2 2 2 2 2 2 5]5?      # 9: array.find()
2 2+                         # 4: addition
"2 2*2*"~                    # 8: eval

```

# Answer
> 2 votes
# Julia - 23 digits in 345 characters (15 per digit exactly)

```
print(div(2,2),'.','/'+7,length(" "),2^3,size([])[end],isqrt(9),int(cbrt(27)),54-45,'h'$'P',[2:22][7],endof("2222222"),count(isodd,[5,5,5,5]),search("Hello man",'n'),nextpow2(5),rsearch("Love boat",'t'),sizeof('й'),("I"summary(b"H"))[22],iceil(float(pi)),iround(cosh(e)),ifloor(exp(catalan)),cmp(5,5),itrunc(5sin(one(Int))),uint(erfcx(-ones())))

```

Output: 1.6180339887498948482045

I interpreted characters and strings as usable, so long as I did not re-use a specific character or string (characters in a string could be re-used, as long as the string was not); however, I did not permit myself to use the int value of a character directly. There is one non-ASCII character (й).

In a more readable fashion (not actual code):

```
1> div(2,2)
.> '.'
6> '/'+7
1> length(" ")
8> 2^3
0> size([])[end]
3> isqrt(9)
3> int(cbrt(27))
9> 54-45
8> 'h'$'P'
8> [2:22][7]
7> endof("2222222")
4> count(isodd,[5,5,5,5])
9> search("Hello man",'n')
8> nextpow2(5)
9> rsearch("Love boat",'t')
4> sizeof('й')
8> ("I"summary(b"H"))[22]
4> iceil(float(pi))
8> iround(cosh(e))
2> ifloor(exp(catalan))
0> cmp(5,5)
4> itrunc(5sin(one(Int)))
5> uint(erfcx(-ones()))

```

# Answer
> 1 votes
# Bash, 5 digits in 65 chars

I will update this soon! For now, it just prints `1.6180`, and does not contain any digits.

```
false
tr -d ' '<<<$?.`wc -c<<<abcde``nl<<<' '``kill -l FPE`$(())

```

## Explanation

The following methods are used to generate the digits:

1: exit status of `false`

6: string length

1: `nl` abuse

8: `kill` signal numbers

0: numeric value of an empty expression

# Answer
> 1 votes
# Mathematica 9 8 digits, in 86 83 78 characters.

```
10`8FromDigits@#/10^Length@#&@{a/a,3!,-I I,2π/(45°),#&''[],Prime@2,Sqrt@9,4+5}

```

Output:

```
1.6180339

```

# Answer
> 0 votes
## C++ 12.4 chars per line, was 14 chars per line for each digit

Fixed my mistake of reusing operators.

```
#include <iostream>
#include <math.h>
#define S std::string
#define C(x) std::cout<<x
int main()
{
C(cos(0));
C(char(46));
C('j'%'d');
C('\0'+3-2);
C(sqrt('@'));
C(log(1));
C('c'/'!');
S s("xyz");
C(s.size());
return 0;
}

```

Not sure if using chars like this counts as char literals or not? If this code is acceptable it can be continued forever and char debt will be paid back.

```
#include <iostream>
#define C(x) std::cout<<x
int main()
{
C('b'-'a');//1
C(char(46));//.
C('g'-'a');//6
C('b'-'a');//1
C('i'-'a');//8
C('a'-'a');//0
C('d'-'a');//3
C('d'-'a');//3
C('j'-'a');//9
//etc
return 0;
}

```

---
Tags: code-challenge, number, restricted-source
---


title: Open source optical lattice clock

text:
# Question
Title: Open source optical lattice clock
A recent question showed how Mathematica could be used to make a beautiful optical lattice clock image. The image looks like this.

This challenge is to reproduce this image as closely as possible using as short code as possible using only easily available open source tools (and without just downloading the image or parts of it).

**Rules** As it is not reasonable to ask for a pixel by pixel reproduction this is a popularity contest. However, please up-vote code that is a short (in the style of code-golf) and which produces an accurate and beautiful reproduction of the image.

# Answer
### POV-Ray, 512 characters

Here's my try. I didn't manage to replicate the lighting, so I've decided to keep the variation of highlight positions rather than to put the lights further away to keep the background brighter.

The area shadow is rather low-quality. I might as well turn it off completely (and save precious characters), but if someone is willing to donate some computing power and crank up the shadow quality and/or the dither quality, I'll gladly accept.

```
#include"functions.inc"
camera{location<-3,5,-6>right x look_at 0 focal_point 0 aperture 1 blur_samples 9}
#macro s(p)sphere{pi*p+y/3 1 pigment{rgb<2,8,2>/9}finish{phong .5 phong_size 5 specular 1 roughness .001}}#end
#macro l(p,c)light_source{p c/8 area_light 9*x,9*z,3,3}#end l(<6,6,0>,<8,4,8>)l(<0,6,0>,<4,8,8>)
isosurface{function{y/3+pow(cos(x)*cos(z),2)/2}contained_by{box{-9,100}}pigment{tiling 1 color_map{[.9 rgb 1][1 rgb 0]}scale .5/pi}}
s(0)s(<0,0,-1>)s(<-1,0,0>)s(<0,0,2>)s(<2,0,1>)s(<2,0,3>)

```

### Result:

### ungolfed:

```
#version 3.7;
#include "functions.inc"
global_settings{assumed_gamma 1}
camera{
  location <-3,5,-6>
  right x //set the aspect ratio
  look_at 0
  focal_point 0 aperture 1 blur_samples 9
}

#macro l(p,c) // position, color
  light_source{
    p c/8
    area_light 9*x,9*z,3,3
  }
#end
l(<6,6,0>,<8,4,8>)
l(<0,6,0>,<4,8,8>)

isosurface{
  function{y/3+pow(cos(x)*cos(z),2)/2}
  contained_by{box{-9,100}}
  pigment{
    tiling 1
    color_map{[.9 rgb 1][1 rgb 0]}
    scale .5/pi
  }
}
#macro s(p) //position
  sphere{
    pi*p+y/3 1
    pigment{rgb<2,8,2>/9}
    //phong for the wide highlights, specular for the small ones.
    finish{phong .5 phong_size 5 specular 1 roughness .001}
  }
#end
s(0)
s(<0,0,-1>)
s(<-1,0,0>)
s(<0,0,2>)
s(<2,0,1>)
s(<2,0,3>)

```

P.S.: I've only counted the five line-breaks to round the character count to a perfectly round number.
> 17 votes

---
Tags: popularity-contest, graphical-output
---