title: Make a Number Expression

text:
# Question
Title: Make a Number Expression
Few years ago, an esoteric programming language named 아희(Aheui) was created. Well, actually you don't need to know about this language or Korean characters.

Aheui uses stacks and a queue, but this time we use **one stack** and ignore other stacks and queue. You can **push a number** between 2 and 9 into a stack. You can do **arithmetic operations** by popping two numbers and pushing result. And you can **duplicate** a top number.

So, when I need a big number in Aheui, making a number was not an easy work. Push, push, multiply, duplicate, push, multiply, push, add…. It takes too much time and sometimes waste of bytes. I need a shortest expressions.

## Summary

Your task is to write a function or a program which takes a number `n (0 <= n <= 1000000)` and returns concatenation of tokens.

Tokens are basically a postfix notation. Tokens are consisted of

* Number between 2 and 9, which means "push number into stack"
* `+`, `-`, `/`, `*`, which means "pop two numbers from stack, do arithmetic operation, push the result into stack". All calculations are in integer.
* `>`, which means "duplicate a top number"

Tokens will be concatenated with empty string, so `5 5 +` will be `55+`.

After calculations, `n` must be on the top of the stack.

### Sample input and output

```
INPUT = 0
OUTPUT = 22-
(or 33-, 44-, whatever)

INPUT = 1
OUTPUT = 22/
(or 32-, 33/, whatever)

INPUT = 5
OUTPUT = 5
(We don't need calculations, just push)

INPUT = 64
OUTPUT = 88*
(or 8>*)

INPUT = 1337
OUTPUT = 75*2+>*48*-
(This may not be a shortest solution)

```

## Scoring

This is a list of test cases. Test cases are seperated by a new line character. You may write a test script which converts those bunch of numbers to string of tokens, or you can do it by your hand.

Let

* `S` = size of complete function or program
* `O` = length of converted strings
* `I` = size of test cases (In this case, `I = 526`)

Then your score will be `S * (O / I)`. Sizes are in bytes.

`S` includes function declarations, `#include`s, `import`s, whatever. Test script is not counted.

## Scoring example

Let `S` is `150`.

### Sample Test cases

```
0
1
5
64
1337

```

### Sample Output

```
22-22/588*75*2+>*48*-

```

In this case, `I = 9`, and `O = 21`. So your score is `150 * (21 / 9) = 350`.

## Rules

* Standard "loopholes" are forbidden.
* Lowest score wins.
* If there is a tie, smaller code size wins.
* Winner will be selected after three weeks (2014-08-04).

---

I wrote a validator in Node.js. Put `input.txt` and `output.txt` in same directory, and run `node validator.js`.

And I found two-year-old similar question. But scoring is different (this question includes code size in score), and this question can't use 1. So I hope it's not a duplicate.

# Answer
> 3 votes
# Javascript, Score = 1663.46768

```
function X($){S=Math.sqrt;function J(A){return A.join("")}function M(A,B){return A.length<B.length?A:B}function D(q){var w="",e,r,t,y;for(e=9;e>1;e--){r=~~(q/e);t=r*e-q;if(t==0)y=J([G(r),e,"*"]);else y=J([G(r),e,"*",G(-t),"+"]);if(w=="")w=y;w=M(w,y)}return w}function Q(a){var s=~~S(a),d=a-s*s,f=J([G(s),">*",G(d),"+"]),g;s=Math.ceil(S(a));d=s*s-a;g=J([G(s),">*",G(d),"-"]);return M(f,g)}function G(z){var x,c,v,b,n,m;if(z==0)return"22-";if(z==1)return"22/";if(z>1&&z<10)return""+z;if(z>9&&z<19){x=~~(z/2);c=z-x;return J([x,c,"+"])}for(v=9;v>1;v--){b=~~(z/v);if(b>1&&b<10&&b*v==z)return J([v,b,"*"])}n=S(z);if(~~n==n)return J([G(n),">*"]);return M(D(z),Q(z))}return G($)}

```

This is my attempt for my question, and this is output. Code size is 671, and output size is 1304. Score is 1663.46768 (rounded up to 5 decimal places).

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


title: PI window encryption

text:
# Question
Title: PI window encryption
This is a simple encryption method that uses PI digits to encode a message, the method is simple:

The key is just a positive integer that indicates where the window starts then:

Given a string to encrypt, containing only lowercase letters, no spaces, you take its length, then you find the Nth digit of PI and then proceeds to shift every letter to the right for the amount indicated by the digit.

For example, if the key is `2` and I want to encode `house`, I take a window of 5 digits from the second one: `14159` and then it becomes:

```
h -> i
o -> s
u -> v
s -> x
e -> n

```

a.- Your program/function/algorithm will receive two parameters, an string composed only of lowercase letters with no spaces and the key, which will be just a positive integer between 1 (1 refers to 3) and 1000, which could be more or less as I'm not quite sure how long does it take to compute PI with said accuracy because:

b.- You must compute PI yourself in your code, here is a neat webpage to compare with: Pi Day. The input should never have you calculate PI beyond the 1000 digit, meaning that length(message)+key \<= 1000.

By computing Pi, I mean not harcode it in your code (silly for a code golf) nor use any embedded constant in your code nor any trigonometric identity (2\*acos(0)) nor any web reference.

c.- The output will be just the encrypted string.

This is a code golf question, shorter code wins!

I'll be accepting the winning answer at July 14th, 2014.

# Answer
> 3 votes
# CJam - 51

```
l_,li(2e4,-2%{2+_2/@*\/2e2000+}*Ab><]z{~+_'z>26*-}%

```

Example input:

```
zebra
20

```

Output:

```
dkdxe

```

This works for (string length) + key \<= 2000, but is quite slow for the online interpreter (still fast with the java interpreter).

Here's a version that works up to 200 and you can try at http://cjam.aditsu.net/ without waiting too long:

```
l_,li(2e3,-2%{2+_2/@*\/2e200+}*Ab><]z{~+_'z>26*-}%

```

# Answer
> 5 votes
# Python - 370

Ok, nice one, finally got the pi thing working with thanks to link1 and link2.

```
from decimal import *
def f(s,n):
 j=len(s)
 getcontext().prec=j+n+5
 d=Decimal
 e=d(0)
 for k in range(0,j+n+5):
  e+=(d(16)**(-k)*(d(4)/(8*k+1)-d(2)/(8*k+4)-d(1)/(8*k+5)-d(1)/(8*k+6)))
 c=`e`.split("'")[1].replace('.','')
 t=''
 for i,l in enumerate(s):
  o=ord(l)
  for v in[0,32]:
   if 64+v<o<91+v:
    l=chr(((o-65-v)+int(c[i+n-1]))%26+65+v)
  t+=l
 print t

```

Example output:

```
>>> f('house',2)
isvxn

```

and another:

```
Wimt fcy d dnyh uhkvkv qhvadil

```

> \>\>\> f('This was a very secret message',1)

# Answer
> 1 votes
# JavaScript - 167 ~~173~~ ~~176~~

Thanks to **Michael** for the clever representation of powers of 16.

This can calculate PI up to the 16-th digit.

```
function e(s,o){for(p=i=n=r='',m=1;s[+i];m<<=4,n>o?r+=String.fromCharCode(s.charCodeAt(i)-+-(1e15*p+'')[o+i++]):0)p-=(4/((d=8*n++)+1)-2/(d+=4)-1/++d-1/++d)/m;return r}

```

The test case:

```
> e("house",2)
"isvxn"

```

# Answer
> 1 votes
## Python - 321 304 288 285

```
from decimal import*
d=Decimal
s,n=raw_input(),input()
l=len(s)
getcontext().prec=n+l
print''.join([chr((v-97)%26+97)for v in map(sum,zip(map(ord,s),map(int,str(sum([(d(4)/(8*k+1)-d(2)/(8*k+4)-d(1)/(8*k+5)-d(1)/(8*k+6))/16**k for k in range(0,l+n)])).replace('.','')[n-1:n+l])))])

```

Most of the golfed version is easy to read and understand. The final line is ungolfed below:

```
# Calculate PI using the BBP formula.
pi = 0
for k in range(0,l+n):
    pi += (d(1)/(16**k))*((d(4)/(8*k+1))-(d(2)/(8*k+4))-(d(1)/(8*k+5))-(d(1)/(8*k+6)))

# Remove the decimal point in PI.
pi = str(pi).replace('.','')

result = []
# For the ASCII sum of each pair of letters in `s` and its digit in PI
for v in sum(zip(map(ord, s), map(int, pi))):
    result.append((v-97)%26+97)

# Convert all the ordinal values to characters
print ''.join(map(chr, result))

```

EDIT #1: simplified my module arithmetic.

EDIT #2: refactored the BBP formula.

# Answer
> 0 votes
# Haskell - 265 ~~267~~ bytes (no IO)

```
p=g(1,0,1,1,3,3)where g(q,r,t,k,n,l)=if 4*q+r-t<n*t then n:g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l) else g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
e i s=zipWith(\k c->toEnum$fromIntegral k+fromEnum c::Char)(take(length s)$drop(fromIntegral$i-1)p)s

```

`p` is a golfed version of the algorithm that can be found at http://rosettacode.org/wiki/Pi#Haskell

`e` is the encoding function :

```
λ> e 2 "house"
"isvxn"

```

It does not loop around if an index is outside of the lowercase alphabet. This means that some other characters can slip in the encoded string :

```
"Sfufv#Kork(mq}nns j{i&sv&xitmujtu&vey|h{xljej|35.)(\"%(\"\"&\" %\"\"$()$ ''\"&'!)$'(\"&($(\"& !$'&)]hrs\"ow olih7$Tdkhnsj ns&qpdlw}oplwmxbipn#o{ur!vhbp\"mitj/"

```

Unfortunately, it takes several seconds with offsets greater than `10 000` to compute the output. Fortunately, when using the same offset multiple times, the digits only have to be computed the first time.

# Bonus - Decoding

```
d i s=zipWith(\k c->toEnum$fromEnum c-fromIntegral k::Char)(take(length s)$drop(i-1)p)s

```

Again if we test with `isvxn` :

```
λ> d 2 "isvxn"
"house"

```

# Answer
> 0 votes
# CoffeeScript - 148 Chars/Bytes

*My first ever Code Golf*

*Unfortunately It does not support wrapping (So a z would end up being punctuation)*

> e=(m,k)-\>(m.split('').map (v,i)-\>String.fromCharCode v.charCodeAt()+parseInt Math.PI.toString().replace('.','').slice(k-1,m.length+k-1)\[i\]).join('')

Demo on CSSDeck

Called with:

> alert e 'house', 2
>
> > isvxn

---
Tags: code-golf, pi
---


# Question
Title: Shortest conditional to run a specific statement: C code golf
Currently I have the code (expanded for your benefit):

```
<number> != <number> ? printf("|\\"); : <number>;

```

The idea here, is to do this condition in the least number of characters. This is currently, roughly the same number of characters it would take to be doing the exact same thing using an if statement, due to the fact, that I am fulfilling the second argument of the ternary operator **which does not need to be filled**, it is simply filled, as otherwise the statement does not run. (the final number is really a variable).

Is there any possible way to do the same conditional but shorter? (in C)

# Answer
```
if(x!=y)printf("foo\n");
x!=y?printf("foo\n"):0;
x==y||printf("foo\n");

```

Yes, you can save some characters with the ternary operator or with the shortcutting logic operators (`&&` and `||`). All three of the above do the same thing. Which you can use depends on things like the return type of `printf` and whether you need the return value.

Does that answer your question?
> 5 votes

# Answer
A year late but one whole character shorter.

```
x-y&&printf("foo\n");

```
> 2 votes

---
Tags: code-golf, c
---


# Question
Title: Conway's Game of Life with smallest *set* of source characters
The goal of this challenge is to write a program that will simulate a single round of Conway's Game of Life on an existing grid.

## Input format:

Input will be read from stdin. The input will consist of a line containing two numbers, `r` and `c`, separated by a single space. These will be the number of rows and columns of the input grid, respectively.

Following the dimensions will be the grid itself, one row per line. Each character in the row will either be a `.` (meaning a dead cell) or a `#` (meaning a living cell).

## Output format:

Output will be written to stdout. The output should be formatted exactly the same way as the input (including the width and height). It should consist of the state of the grid after simulating one generation. In this way, it should be possible to simulate as many generations as desired by piping the output of one run of your program into it again in a new run. Note that your program must actually perform the simulation and cannot use external resources such as other programs or network access.

Grid boundaries are to be considered dead zones.

## Sample input:

```
5 6
......
..#...
..#...
..#...
......

```

## Sample output:

```
5 6
......
......
.###..
......
......

```

## Scoring

Programs will be scored on the total *unique* bytes in the program's source. The smaller the score, the better.

Here is the scoring system that will be used to judge entries (Python):

```
data = open(fname, "rb").read()
unique = set(data)
score = len(unique)
print("Score for %s: %d" % (fname, score))

```

If two entries happen to tie, then the total length in bytes of the source will be used as a tiebreaker.

Of course, there have to be some limitations as to what programming languages may be used. Clearly I cannot allow Whitespace or Brainf\*ck in this challenge or there would be no chance for other languages. Therefore, I will implement a whitelist of allowed languages. If you wish to use a language that is not present in the whitelist, post a comment and I will decide whether to add it to the list.

## Language Whitelist

* Assembly
* C
* C#
* C++
* Go
* Haskell
* Java
* Lisp
* Lua
* Objective-C
* Perl
* PHP
* Python
* Ruby
* Rust
* Swift

The winner will be decided on August 1 at 11:59pm EST.

## UPDATE:

As of August 1st, the winner is @mniip with a Lua solution consisting of only 9 unique characters.

# Answer
# Lua 5.2 - 9 characters

The only chars used are `load"\045`:

```
load"load\"load\\\"load\\\\\\\"load\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05504\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505o\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055ad\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\04\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505o\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055ad\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\04\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0505\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\0550\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05504\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050do\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0505\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0500\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\0550\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050do\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0500\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05504\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050do\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505o\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055ad\\\\\\\\\\\\\\\\040\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0500\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050do\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0500\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505o\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055ad\\\\\\\\\\\\\\\\040\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\040\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05504\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05504\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050do\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0500\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050do\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0555\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\0550\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\050\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\045\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050do\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\045\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\044\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050do\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\050\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\050\\\\\\\\\\\\\\\\04\\\\\\\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\050\\\\\\\\\\\\\\\\04\\\\\\\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050a\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\050\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0500\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\0555\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05504\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0555\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0555\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\04\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505o\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\040\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\0500\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\055\\\\\\\\05\\\\04\\05\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\0555\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055a\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\040\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0555\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\050\\\\\\\\\\\\\\\\05\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0555\\\\\\\\\\\\\\\\0\\\\\\\\0540\\\\\\\\\\\\\\\\050\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050a\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\0555\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\04\\\\05\\055o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\040\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0555\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\054\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\05\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050a\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\0555\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055o\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\054\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\05\\\\055\\\\\\\\\\\\\\\\04\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\04\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\\0\\\\\\\\05\\\\04\\05\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\050\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0554\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\05505\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\055\\\\\\\\054\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\0550\\\\\\\\04\\\\05\\055\\\\\\\\\\\\\\\\\\\\\\\\04\\\\05\\055\\\\\\\\04\\\\05\\0550d\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\"\\\\\\\"\\\\\\\"\\\\\\\"\\\"\\\"\\\"\"\"\""""

```

The thing was generated using this simple script:

```
local data = io.read"*a"
while data:match'[^load\\"045]' do
    data = 'load"' .. data:gsub('[^load045]', function(x)
            if x == '\\' or x == '"' then
                return '\\' .. x
            else
                return ('\\%03d'):format(x:byte())
            end
        end) .. '"""'
end
print(data)

```

The GOL implementation is not really interesting, just a usual loop with extra cols/rows in the grid instead of bound checking.
> 7 votes

# Answer
# C: 41 distinct characters, 372 total

I didn't try very hard to reduce the number of distinct characters.

```
f,h,i,o,c,m,n;main(){scanf("%d %d",&h,&f);printf("%d %d\n",h,f);char a[h+1+1][f+1+1];for(i=1-1;i<h;a[i][1-1]=a[i][f]=1-1,i++)scanf("%s",a[i+1]+1);for(i=1-1;i<f;a[1-1][i]=a[h][i]=1-1,i++);for(i=1;i<h+1;i++){for(o=1;o<f+1;o++){c=1-1;for(n=-1;n<1+1;n++){for(m=-1;m<1+1;c+=a[i+n][o+m]=='#'&&(m||n),m++);}putchar(a[i][o]=='#'? (c>1&&c<4?'#':'.'):c==3?'#':'.');}putchar('\n');}}

```

You can see the non-reduced version here.
> 0 votes

---
Tags: code-challenge
---


# Question
Title: Difference of expressions when evaluated in different orders
We all know the standard order of operations for math functions (PEMDAS), but what if we instead evaluated expressions left-to-right?

## The Challenge

Given a string through standard input or through command line args, find the difference between the traditional evaluation (PEMDAS) and the in-order (left-to-right) evaluation of that expression.

## Details

* You will be given a string in a format such as:

```
"1 + 2 * 3 ^ 2 - 11 / 2 + 16"

```
* To simplify things, there will be:

+ a space between each number and operator
    + no leading or trailing spaces
    + no decimal numbers or negative numbers (non-negative integers only)
    + no operators beyond +(plus), -(minus), \*(multiply), /(divide), ^(exponentiation)
    + no parens to worry about
    + you may remove the spaces if it's easier for you to handle, but no other modification of the input format will be allowed.
* You must provide the **absolute value** of the difference between the two evaluations of the string
* Your division can either be **floating-point or integer division** \- both will be accepted
* Your program **can not use any sort of expression evaluation library**.

*To clarify - any sort of **built-in** eval function in which your language evaluates a string that is valid code for the same language **IS** acceptable*
* Explanations of your code are preferred
* Shortest code by byte count wins
* Winner will be chosen Saturday (July 19, 2014)

## Examples:

**A: 1 + 2 * 3 ^ 2 - 11 / 2 + 16 (using floating-point division)**

* In traditional order of operations:

```
1 + 2 * 3 ^ 2 - 11 / 2 + 16   -->   1 + 2 * 9 - 11 / 2 + 16   -->

1 + 18 - 5.5 + 16             -->   29.5

```
* In-order traversal yields:

```
1 + 2 * 3 ^ 2 - 11 / 2 + 16   -->   3 * 3 ^ 2 - 11 / 2 + 16   -->

9 ^ 2 - 11 / 2 + 16           -->   81 - 11 / 2 + 16          -->

70 / 2 + 16                   -->   35 + 16                   -->

51

```
* Resulting difference: 51 - 29.5 = **21.5**

**B: 7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2 (using integer division)**

* In traditional order of operations:

```
7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->   7 - 1 * 9 + 41 / 3 + 2 * 9 * 2   -->

7 - 9 + 13 + 18 * 2                  -->   7 - 9 + 13 + 36                  -->

47

```
* In-order traversal yields:

```
7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->   6 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->

18 ^ 2 + 41 / 3 + 2 * 9 * 2          -->   324 + 41 / 3 + 2 * 9 * 2         -->

365 / 3 + 2 * 9 * 2                  -->   121 + 2 * 9 * 2                  -->

123 * 9 * 2                          -->   1107 * 2                         -->

2214

```
* Resulting difference: 2214 - 47 = **2167**

# Answer
### GolfScript, 84 characters

```
' '/.{?}:^;(~\2/{~~\~}/\{\?}:^;-1%'^'{[`{2$?0<!{@~\~@~`}*}+/]}:C~-1%'*/'C'+-'C~~-abs

```

This version does integer division and therefore yields a different result for the first test case. You may try the code here.

```
> 1 + 2 * 3 ^ 2 - 11 / 2 + 16
21

> 7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2
2167

```

*Code with comments:*

```
' '/.            # split the input at spaces and save a copy for each evaluation

# LTR evaluation
{?}:^;           # define ^ to be the power operator
(~\              # convert the left most string (first operand) into a number
2/{              # loop over the rest in pairs of two
  ~              #   split pair
  ~              #   evaluate second item of tuple (i.e. numeric operand)
  \~             #   apply the operator to two items on stack
}/               # end loop

# standard evaluation
\{\?}:^;         # redefine ^ to be the rtl power operator
-1%              # -1%  .... -1% reverse the input in order to handle right associativity
'^'
{                # {...}:C~ define code-block C and apply it to the string '^'
  [`{            # stringify the argument in order to add it to the internal
                 # code-block. afterwards loop over the input array and collect
                 # the results in an array
    2$?0<!       # if the second top item on the stack is one of the provided operators
    {
      @~         #   take the first operand and convert to number
      \~         #   take the second operand and convert to number
      @~         #   apply the operator
      `          #   stringify result
    }*           # end if
  }+/]
}:C~
-1%

'*/'C            # afterwards apply the same code-block for operators * and /
'+-'C            # and then for operators + and -
~~               # flatten the resulting array and convert the result to a number

-abs             # take absolute difference between the two evaluation methods

```
> 2 votes

# Answer
## Haskell, 281 256 characters

```
(x:o:y:z)%p|p o=(show(m o(read x)$read y::Float):z)%p|1<3=x:o:(y:z)%p;z%_=z
m"+"=(+);m"-"=(-);m"*"=(*);m"/"=(/);m"^"=(**);m _= \a->abs.(a-)
l=(%(\_->1<3))
t e=foldl(%)e$map(\w->(`elem`w).head)["^","*/","+-"]
d e=l$l e++"~":t e
main=interact$concat.d.words

```

Brief explaintaion:

* `%` reduces an expression, so long as the operator meets some predicate `p`
* `show(m o(read x)$read y::Float)` applies an operator to the two string arguments, producing a string result
* `m` maps a string to an operator; note the string `"~"` is mapped to absolute difference
* `l` computes left-to-right order by applying `%` once, with a predicate that is always true
* `t` computes traditional order by repeatedly applying `%` with tests that match operators first of higher precedence, then lower
* `d` computes the two values, then forms a new expression with operator `~` and computes that

Runs:

```
& echo "1 + 2 * 3 ^ 2 - 11 / 2 + 16" | runhaskell 34599-EvalOrder.hs
21.5

& echo "7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2" | runhaskell 34599-EvalOrder.hs
2178.3333

```

*(Second result differs from example above because this code always computes in floating point.)*
> 2 votes

# Answer
# Perl 204 (203 + 1 for the `-p` flag)

LOL using `eval` got boring (`s/\^/**/g;$_=eval"("x(()=/\d+/g).s/(\d+)/\1)/rg."-($_)"`) as I saw Calvin's Hobbies's comment on the eric\_lagergren's answer so here's an non-eval method:

```
$d='([-\d.]+)';$s=$t=$_;map{$o=$_;$s=~s|$d (.) $d|($1*$3,$1+$3,0,$1-$3,$1**$3,$1/$3)[ord($2)%6]|e,$t=~s|$d ([\\$o]) $d|($1*$3,$1+$3,'',$1-$3,$1**$3,$1/$3)[ord($2)%6]|eg for$t=~/./g}'^/*-+'=~/./g;$_=$s-$t

```

**Ungolfed:**

```
# shortcut
$d = '([-\d.]+)';

# initial values for the traditional and sequential evaluation
$s = $t = $_;

# split the list of operators and loop throught them
map {
    # store current operator in $o
    $o=$_;

    # repeatedly evaluate the input string until the calculations are done
    for($t=~/./g) {
        # Here is an array with calculated all operators and I pick the correct element
        # ord($2)%6 is never 2 so I put 0 in that position of the array
        $s=~s|$d (.) $d|($1*$3,$1+$3,0,$1-$3,$1**$3,$1/$3)[ord($2)%6]|e;
        $t=~s|$d ([\\$o]) $d|($1*$3,$1+$3,'',$1-$3,$1**$3,$1/$3)[ord($2)%6]|eg
    }
} ('^/*-+'=~/./g);

# subtract the traditional evaluation form the in-order one
$_ = $s - $t

```

This solution uses floating point calculations.

**Output:**

```
$ PS1='\n\$ '

$ ./order.pl <<<"1 + 2 * 3 ^ 2 - 11 / 2 + 16"
21.5
$ ./order.pl <<<"7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2"
2178.33333333333

```
> 2 votes

# Answer
## Python 208

```
d=x=input();z=2;u='('*(((len(x)-len(x.replace(' ','')))/2)+1);d=x=d.replace(r'^','**');x=x.split();p=u+''.join(")".join(x[i:i+z]) for i in range(0,len(x),z))+")";m=eval(p)-eval(d);m=m*-1 if 0>m else m;print m;

```

---

Calvin'sHobbies comment::

```
import re;e=input().replace('^','**');print abs(eval(e)-eval(e.count(' ')/2*'('+re.sub('(\d) ',r'\1)',e)))

```

---

**Explanation:**

```
# variable d  =  x, and x  =  user input

d = x = input()

# variable z = 2

z = 2

# I take the length of the string 'x' (aka the equation we're solving) with
# *all* whitespaces removed (it's the 'len(x.replace(' ', '')...' part) and
# subtract that from 'len(x)' which is the vanilla length of our equation
# I divide the total by two and add one for reasons I'll explain in a minute
# the '(' * part means to make a string with as many '(' as I get from multiplying
# so '(' * 5 = '(((((', '(' * 3 = '((('

u = '(' * (((len(x) - len(x.replace(' ', ''))) / 2) + 1)

# Here I replace the caret with **, because in Python ^ == **
# I also split the string by whitespaces, but only for x;

d = x = d.replace(r'^','**'); x = x.split();

# I set the variable p = to the result of joining the list (aka array) that
# I just made with the .split() in the above section first with a ')' on every
# second character (e.g. [1,2,3,4,5,6] would be 1,2),3,4),... etc. I do it like
# this because in our math equation we'll (hopefully) follow the pattern of
# num op num op num op... etc. I insert parenthases because I'm using PEMDAS
# to my advantage by grouping each set of numbers in the order I want them
# to be completed. The initial ''.join simply rejoins all elements into a
# complete string (basically removes the commas that are left over from
# converting a list -> string). I add a '(' to the end because every 2nd
# character would skip the final one

p = u + ''.join(")".join(x[i:i + z]) for i in range(0, len(x), z)) + ")"

# I eval() both p and d. eval() will run arbitrary code, so you can pass it a
# string and it will act as if the string is code, so while print '1+1' would
# usually result in TypeError (or Value? I forget), print eval('1+1') would
# print '2', I have to do them separately because eval() thinks I wanna
# subtract two string for whatever reason

m = eval(p) - eval(d)

# Here I make use of Python's ternary operators by saying this:
# if 0 > m:
#   m = m * -1
# else:
#   m
# which means that if m is negative, multiply it by -1 to make it
# a positive number so we can get the absolute value. If it's not negative
# then we can just have m and not do anything with it

m = m * -1 if 0 > m else m

# Print m :)

print m

```
> 0 votes

---
Tags: code-golf, math, number, arithmetic
---


title: Spiral in the grid

text:
# Question
Title: Spiral in the grid
Write a program which enumerates points on a regular grid in the form of a spiral. The output should be the indices of the points (row-major) and the spiral should start at 0 and proceed anti-clockwise.

Here is an illustration of the problem:

**Specifications:**

* Write a program which accepts two integers and writes the result to standard out.
* Input: width and height of the grid (range is \[1,1024\])
* Output: indices of grid points in the correct order

**Goal:**

* Entry with fewest characters wins.
* Would also be interested in elegant entries for "classic" programming languages.

**Examples:**

* width=3, height=3 =\> 0 1 2 5 8 7 6 3 4
* width=4, height=3 =\> 0 1 2 3 7 11 10 9 8 4 5 6

# Answer
> 7 votes
# CJam - 18

```
q~1$*,/{(S*S@zW%}h

```

Try it at http://cjam.aditsu.net/

The input should contain the 2 numbers separated by space.

**Explanation:**

`q~` reads and evaluates the input
`1$*` copies the width and multiplies by height
`,/` generates the array with all the numbers in order, and splits it in rows
`{…}h` repeats the block until the condition (at the end of the block) is false
`(S*S` takes the first row of the grid and adds spaces to separate the numbers
`@zW%` takes the rest of the grid and rotates it (`z` = transpose, `W%` = reverse)
The remaining grid becomes the loop condition; the loop terminates when the grid is empty.

# Answer
> 3 votes
### Ruby — ~~96~~ 81

@Ventero knocks off 15 characters with some splatting combined with a really clever default argument!

```
g=->a=p,*r{a ?a+g[*r.transpose.reverse]:[]}
f=->w,h{g[*[*0...w*h].each_slice(w)]}

```

Examples:

```
f[3,3]  # => [0, 1, 2, 5, 8, 7, 6, 3, 4]
f[4,3]  # => [0, 1, 2, 3, 7, 11, 10, 9, 8, 4, 5, 6]

```

Here's an ungolfed solution in Ruby using just one method for those who are interested:

```
def spiral(width, height, matrix = [*[*0...width * height].each_slice(width)])
  matrix.empty? ? [] : matrix.shift + spiral(0, 0, matrix.transpose.reverse)
end

```

# Answer
> 2 votes
## My PHP version. 349 276 characters.

Same as below but I found out something surprising. In PHP, for loops can have multiple expressions in both pre and post iteration. I never knew that and suddenly they are far more powerful/complex than I thought they were. So could not resist rewriting my first attempt to make use of that.

Anyway, new and improved code here - 73 characters shorter than the first:

```
<?php $a=4;$b=3;$c=-1;$d=$a*$b;$e=$a;$f=($b-1);function c($g,$k){
global $c,$d;for($l=0;$l<$g;$c=$c+$k,++$l,--$d,print $c.' ');}while($d>0)
{$m=1;$g=$e;c($g,$m);--$e;if($f>0){$m=$a;$g=$f;c($g,$m);--$f;if($e>0)
{$m=-1;$g=$e;c($g,$m);--$e;if($f>0){$m=-$a;$g=$f;c($g,$m);--$f;}}}}?>

```

which can be seen here:

### Original attempt below

No where near as cool as the 18 chars of CJam (which I shall be googling about in a minute) but this is the full php program that takes the width and height as the first two parameters.

```
<?php $a=4;$b=3;$c=-1;$d=$e=0;$f=($b*$a);function calc($g,$h,$j,$k){for($l=$g;
$l<$h;++$l){$k=$k+$j;echo' '.$k;}return($k);}while($f>0){if($d<$a){$c=calc($d,$a,1,$c);
$f=$f-($a-$d);++$e;if($e<$b){$c=calc($e,$b,$a,$c);$f=$f-($b-$e);++$d;
if($d<$a){$c=calc($d,$a,-1,$c);$f=$f-($a-$d);++$e;
if($e<$b){$j=0-$a;$c=calc($e,$b,$j,$c);$f=$f-($b-$e);}}}}++$d;}?>

```

You can see it in action here: http://codepad.org/qPUWwY2J (above paste has had extra line breaks so it all shows on the page without side scrolling.)

I think this puzzle was a great question and I must admit that starting on 0 caused some issues for me. I have checked lots of different grids and it seems to work well although takes a bit of time to work through large grids.

My answer simply recognizes that moving left and right is adding +1 or -1 to the start number used, and up or down just adds or subtracts the original width. It then simply steps down the height and width counters for each pass. All of the output is in a function that I just send the change, step count and start number to. I reckon I could get a few more characters off by not declaring variables, but not 300 or so.

Great puzzle, had some tricky bits but I enjoyed it, thank you.

# Answer
> 2 votes
# Mathematica - 97 characters

```
w=4;h=3;Flatten@NestList[Reverse@Transpose@Rest@#&,Partition[Range[w h],w],2Min[w,h]-2][[;;,1]]-1

```
* First generate the grid.
* Iteratively drop the first row and rotate (transpose + reverse) the remaining matrix.
* The number of iterations until we end with 1-dimensional matrix is `2*min(w,h)-2`.
* Collect the dropped first rows into an array.
* Subtract 1 because Mathematica starts indices with 1.

# Answer
> 1 votes
## JavaScript - 225 Characters

```
w=8,h=8
{for(a=[0],x=y=b=r=t=l=s=0;a.length<w*h;){if(s==0&&x+r+1==w&&++b+1||s==1&&y+t+1==h&&++r+1||s==2&&x==l&&++t+1||s==3&&y==b&&++l+1)s=(s+1)%4
s==0&&++x+1||s==1&&++y+1||s==2&&--x+1||--y
a.push(x+w*y)}alert(a.join(' '))}

```

And ungolfed:

```
w = 8 // width of grid
h = 8 // height of grid
for(a = [0], // array
    x =      // x pos
    y =      // y pos
    b =      // bottom rows done
    r =      // right rows done
    t =      // top rows done
    l =      // left rows done
    s = 0;    // current side 0: b, 1: r, 2: t, 3: l
  a.length < w*h;) {
    if (s==0 && x+r+1==w && ++b+1 ||
        s==1 && y+t+1==h && ++r+1 ||
        s==2 &&     x==l && ++t+1 ||
        s==3 &&     y==b && ++l+1 ){
        s=(s+1)%4
    }

    s==0 && ++x+1 ||
    s==1 && ++y+1 ||
    s==2 && --x+1 ||
            --y

    a.push(x+w*y)
}
alert(a.join(' '))

```

The code sets the grid size in `w` and `h`. It stores current coordinates in `x` and `y`. It navigates in direction `s`, and stores the number of rows already filled on the sides in `b`, `r`, `t` and `l`.

A demo is at http://jsfiddle.net/L2ReA/

---
Tags: code-golf
---


# Question
Title: Maximum number of PEP8 violations in a single line
Your task is to write a file which contains a line with many pep8 violations.

**The rules:**

* We use pep8 version 1.5.7 and the default settings.
* Calling pep8 with other command line options or using a custom rc file is not allowed.
* Maximum line length 120 characters. You can violate E501, sure, but the line which your score is calculated on has to be \<= 120 characters.
* Your module can have other lines before or after, but only one line contributes to your score.
* Your file can contain SyntaxErrors or any kind of garbage, it needn't import or run.

**Example of scoring:**

The following module `thing.py` has a score of 2, because it contains a line (line 1) with 2 pep8 violations.

```
 spam='potato'

```

**To check a score:**

```
~$ mktmpenv
(tmp-ae3045bd2f629a8c)~/.virtualenvs/tmp-ae3045bd2f629a8c$ pip install pep8==1.5.7
(tmp-ae3045bd2f629a8c)~/.virtualenvs/tmp-ae3045bd2f629a8c$ echo -n "spam='potato'" > thing.py
(tmp-ae3045bd2f629a8c)~/.virtualenvs/tmp-ae3045bd2f629a8c$ pep8 thing.py
thing.py:1:5: E225 missing whitespace around operator
thing.py:1:14: W292 no newline at end of file

```

# Answer
> 11 votes
# 241

if you want the most error, just go crazy with semicolon

```
$ cat test.py
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

$ cat test.py | wc -m
120

$ pep8 test.py | wc -l
241

```

most of the error are:

```
test.py:1:119: E231 missing whitespace after ';'
test.py:1:119: E702 multiple statements on one line (semicolon)

```

with those error at the end:

```
test.py:1:120: E703 statement ends with a semicolon
test.py:1:121: W292 no newline at end of file

```

# Answer
> 7 votes
# 123

Yes, more violations than characters!

```
$ curl -s http://pastebin.com/raw.php?i=RwLJfa0Q | cat
 (  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =
$ curl -s http://pastebin.com/raw.php?i=RwLJfa0Q | wc -m
 120
$ curl -s http://pastebin.com/raw.php?i=RwLJfa0Q | pep8 - | wc -l
 123

```

The trick is that an `=` after a `(` makes pep think you're doing a keyword in a function call (e.g. `foo(bar=12)`). In this context, doing `[TAB]=` triggers both

```
killpep.py:1:3: E223 tab before operator
killpep.py:1:3: E251 unexpected spaces around keyword / parameter equals

```

And doing `=[TAB]` triggers both

```
killpep.py:1:5: E224 tab after operator
killpep.py:1:5: E251 unexpected spaces around keyword / parameter equals

```

Gleefully enough, you can just chain these.

This gives a violation count of one per character. I need `(` to set it up, but not providing the `)` gives us:

```
killpep.py:2:1: E901 TokenError: EOF in multi-line statement

```

That's 120. No newline = 121. It managed to trigger the "line too long" error, so that's 122. Finally, using one character to start with a space (thanks eric\_lagergren) gives 2 violations instead of 1:

```
killpep.py:1:2: E111 indentation is not a multiple of four
killpep.py:1:2: E113 unexpected indentation

```

Victory!

---
Tags: code-challenge, python
---


# Question
Title: Introspective Programming: Code that analyzes its source and its output
Write a program that outputs the total number of characters and the frequency of each character in its source *and* its output. You must follow the format illustrated in the example.

## Example

If your code was

```
abb1

```

Its output would have to be

```
My source has 4 characters.
1 is "a"
2 are "b"
1 is "1"
Besides unquoted numbers, my output has 383 characters.
34 are "
"
79 are " "
63 are """
2 are "'"
2 are ","
4 are "."
2 are "1"
2 are "B"
2 are "I"
2 are "M"
39 are "a"
4 are "b"
6 are "c"
4 are "d"
38 are "e"
3 are "g"
5 are "h"
4 are "i"
4 are "m"
3 are "n"
8 are "o"
3 are "p"
2 are "q"
38 are "r"
12 are "s"
8 are "t"
7 are "u"
3 are "y"
It's good to be a program.

```

(Output must go to stdout.)

Notice, for example, that the output contains two capitalized m's. One for `My` and one for `2 are "M"`. This must hold true for all characters so the output does not contradict itself in any way.

Unquoted numbers are ignored in the output to avoid unsatisfiable frequency sets. For example, `1 is "1"` is incorrect if both 1's are counted. It should read `2 are "1"`, but then there is only one 1 again.

## Format Clarifications

* "is" must be used for single character occurrences.
* "are" must be used for multiple character occurrences.
* "is" should never appear in the list of output characters because it would be superfluous. `1 is 'Z'` refers to the Z in itself, so the entire line can be removed.
* The three full-sentence phrases must appear in order with the character frequency lists in between (as the example shows). So your output will start with `My source...` and end with `...be a program.`. Note that there is no newline at the end of the output.
* The character frequency lists themselves may be in any order.
* Newlines count as one character (in case they are \r\n).

## Format Checker

The following Python script takes your code and its output as strings and asserts that the output has no contradictions. It provides a useful error message if something is wrong. You can run it online at http://ideone.com/6H0ldu by forking it, replacing the CODE and OUTPUT strings, then running it. It will never give false positives or negatives (assuming its error free).

```
#Change the CODE and OUTPUT strings to test your program

CODE = r'''abb1'''

OUTPUT = r'''My source has 4 characters.
1 is "a"
2 are "b"
1 is "1"
Besides unquoted numbers, my output has 383 characters.
34 are "
"
79 are " "
63 are """
2 are "'"
2 are ","
4 are "."
2 are "1"
2 are "B"
2 are "I"
2 are "M"
39 are "a"
4 are "b"
6 are "c"
4 are "d"
38 are "e"
3 are "g"
5 are "h"
4 are "i"
4 are "m"
3 are "n"
8 are "o"
3 are "p"
2 are "q"
38 are "r"
12 are "s"
8 are "t"
7 are "u"
3 are "y"
It's good to be a program.'''

#######################################################

import re

amountPattern = r'(\d+) (is|are) "(.)"\n'

class IntrospectionException(Exception):
    pass

def getClaimedAmounts(string, errorOnIs):
    groups = re.findall(amountPattern, string, re.DOTALL)

    for amount, verb, char in groups:
        if verb == 'is':
            if errorOnIs:
                raise IntrospectionException('\'1 is "%s"\' is unnecessary' % char)
            elif amount != '1':
                raise IntrospectionException('At "%s", %s must use "are"' % (char, amount))
        elif verb == 'are' and amount == '1':
            raise IntrospectionException('At "%s", 1 must use "is"' % char)

    amounts = {}
    for amount, verb, char in groups:
        if char in amounts:
            raise IntrospectionException('Duplicate "%s" found' % char)
        amounts[char] = int(amount)
    return amounts

def getActualAmounts(string):
    amounts = {}
    for char in string:
        if char in amounts:
            amounts[char] += 1
        else:
            amounts[char] = 1
    return amounts

def compareAmounts(claimed, actual):
    for char in actual:
        if char not in claimed:
            raise IntrospectionException('The amounts list is missing "%s"' % char)
    for char in actual: #loop separately so missing character errors are all found first
        if claimed[char] != actual[char]:
            raise IntrospectionException('The amount of "%s" characters is %d, not %d' % (char, actual[char], claimed[char]))
    if claimed != actual:
        raise IntrospectionException('The amounts are somehow incorrect')

def isCorrect(code, output):
    p1 = r'^My source has (\d+) characters\.\n'
    p2 = r'Besides unquoted numbers, my output has (\d+) characters\.\n'
    p3 = r"It's good to be a program\.$"
    p4 = '%s(%s)*%s(%s)*%s' % (p1, amountPattern, p2, amountPattern, p3)

    for p in [p1, p2, p3, p4]:
        if re.search(p, output, re.DOTALL) == None:
            raise IntrospectionException('Did not match the regex "%s"' % p)

    claimedCodeSize = int(re.search(p1, output).groups()[0])
    actualCodeSize = len(code)
    if claimedCodeSize != actualCodeSize:
        raise IntrospectionException('The code length is %d, not %d' % (actualCodeSize, claimedCodeSize))

    filteredOutput = re.sub(r'([^"])\d+([^"])', r'\1\2', output)

    claimedOutputSize = int(re.search(p2, output).groups()[0])
    actualOutputSize = len(filteredOutput)
    if claimedOutputSize != actualOutputSize:
        raise IntrospectionException('The output length (excluding unquoted numbers) is %d, not %d' % (actualOutputSize, claimedOutputSize))

    splitIndex = re.search(p2, output).start()

    claimedCodeAmounts = getClaimedAmounts(output[:splitIndex], False)
    actualCodeAmounts = getActualAmounts(code)
    compareAmounts(claimedCodeAmounts, actualCodeAmounts)

    claimedOutputAmounts = getClaimedAmounts(output[splitIndex:], True)
    actualOutputAmounts = getActualAmounts(filteredOutput)
    compareAmounts(claimedOutputAmounts, actualOutputAmounts)

def checkCorrectness():
    try:
        isCorrect(CODE, OUTPUT)
        print 'Everything is correct!'
    except IntrospectionException as e:
        print 'Failed: %s.' % e

checkCorrectness()

```

## Scoring

This is code-golf. The submission with the fewest characters wins. Submissions must pass the format checker to be valid. Standard loopholes apply, *though you may read your own source code and/or hardcode your output*.

# Answer
> 2 votes
# CJam - 189

```
{`"_~"+:T;"Besides unquoted numbers, my output has &It's good to be a program.&My source has & characters.
"'&/~_]:X2=T,X3=3i({T_&:B{TI/,(" are ":AM`I*N}fIXK=]o
XBA`N+f+2*+s:T,X3=}fK'q];}_~

```

Try it at http://cjam.aditsu.net/

Output:

```
My source has 189 characters.
3 are "{"
3 are "`"
6 are """
4 are "_"
3 are "~"
4 are "+"
5 are ":"
5 are "T"
2 are ";"
3 are "B"
8 are "e"
9 are "s"
2 are "i"
3 are "d"
17 are " "
6 are "u"
2 are "n"
2 are "q"
8 are "o"
6 are "t"
3 are "m"
2 are "b"
7 are "r"
4 are ","
2 are "y"
2 are "p"
3 are "h"
7 are "a"
5 are "&"
4 are "I"
3 are "'"
2 are "g"
2 are "."
2 are "M"
3 are "c"
2 are "
"
2 are "/"
3 are "]"
5 are "X"
2 are "2"
4 are "="
3 are "3"
2 are "("
2 are "A"
2 are "*"
2 are "N"
3 are "}"
3 are "f"
2 are "K"
Besides unquoted numbers, my output has 988 characters.
3 are "B"
108 are "e"
11 are "s"
3 are "i"
5 are "d"
214 are " "
8 are "u"
4 are "n"
3 are "q"
9 are "o"
9 are "t"
5 are "m"
4 are "b"
108 are "r"
3 are ","
4 are "y"
4 are "p"
6 are "h"
108 are "a"
3 are "I"
3 are "'"
4 are "g"
5 are "."
3 are "M"
7 are "c"
102 are "
"
2 are "{"
198 are """
2 are "`"
2 are "_"
2 are "~"
2 are "+"
2 are ":"
2 are "T"
2 are ";"
2 are "&"
2 are "/"
2 are "]"
2 are "X"
2 are "2"
2 are "="
2 are "3"
2 are "("
2 are "A"
2 are "*"
2 are "N"
2 are "}"
2 are "f"
2 are "K"
It's good to be a program.

```

# Answer
> 11 votes
## Ruby, 269 (311, 367) characters

I have three different solutions for this challenge. Each of them uses a different set of tricks:

**"Proper" solution, 367 characters:**

The longest solution is more or less just a proof of concept that it's possible to solve this challenge without any tricks - and is not nearly fully golfed. It's a true quine (i.e. it generates its own source code instead of reading it from a file) and actually calculates all the numbers it prints (code length, output length, character occurences). Due to the way the quine works, all the code has to be on a single line and inside a string literal.

```
eval r="S='eval r=%p'%r;O=-~$.;q=\"My source has \#{S.size}\"+(X=' characters.\n')+S.chars.uniq.map{|c|[k=S.count(c),k>O ? :are: :is,?\"+c+?\"]*' '}*$/+'\nBesides unquoted numbers, my output has ';r=(w=q+X+s=\"It's good to be a program.\").scan(D=/\\D/).uniq;$><<q<<(w+v=r.map{|c|j=' are \"\n\"';(-~(w+j*r.size).count(c)).to_s+(j[~O]=c;j)}*$/+$/).scan(D).size<<X+v+s"

```

**Partially hardcoded output, 311 characters:**

The next shortest solution uses two tricks, but is still a true quine: \- No character occurs exactly once in the source code. That way, I don't need to decide whether I should print `is` or `are` in the first half of the output. It also makes it a bit easier to calculate the total output size (though I don't actually need to do that). \- The total output size is hardcoded. Since this only depends on the number of distinct characters in the source code (and in the general case, how many of those characters occur only once), it's easily to calculate it in advance.

Note that the code is preceeded by two very significant newlines, which StackExchange wouldn't show in the code block. For that reason, I have added an additional line in front if those newlines, which is *not* part of the code.

```
#

eval R="I=$/+$/+'eval R=%p'%R;?\\4>w='%d are \"%s\"';B=\"My source has \#{I.size}\#{X=\" characters.\n\"}\#{z=(m=I.chars.uniq).map{|x|w%[I.count(x),x]}*$/}\nBesides unquoted numbers, my output has 1114\"+X;$><<B+m.map{|c|w%[(B+z+$M=\"\nIt's good to be a program.\").gsub!(/\\d++(?!\")/,'').count(c),c]}*$/+$M"

```

**Shortest solution, 269 characters:**

The shortest solution additionally hardcodes its own source length. By using variable names that are/aren't already part of the source code, it's possible to find a "fixpoint" where all characters in the source code (including the digits from the hardcoded lengths!) occur at least twice.

This solution also saves a few more characters by simply reading its own source code from the code file, instead of generating it. As a nice side effect, this makes the code much more "readable" (but who cares about readable code in a ...), as now the code doesn't have to be inside a string literal anymore.

```
U='%d are "%s"'
O=IO.read$0
?\126>B="My source has 269#{X=" characters.
"}#{z=(m=O.chars.uniq).map{|c|U%[O.count(c),c]}*$/}
Besides unquoted numbers, my output has 1096"+X
$><<B+m.map{|c|U%[(B+z+$M="
It's good to be a program.").gsub!(/\d++(?!")/,"").count(c),c]}*$/+$M

```

---

I also modified the test script a little bit to reduce the copy-pasting necessary to check the code. By replacing the definitions of `CODE` and `OUTPUT` with

```
import subprocess

CODE = open("packed.rb").read()
OUTPUT = subprocess.check_output(["ruby", "packed.rb"])

print CODE
print len(CODE)

```

the script now automatically runs my code, reads its output, and grabs the source code from the code file.

---

Here's the output generated by the shortest code:

```
My source has 269 characters.
3 are "U"
7 are "="
3 are "'"
4 are "%"
6 are "d"
17 are " "
11 are "a"
9 are "r"
9 are "e"
11 are """
11 are "s"
6 are "
"
4 are "O"
2 are "I"
10 are "."
6 are "$"
2 are "0"
2 are "?"
2 are "\"
2 are "1"
2 are "2"
3 are "6"
2 are ">"
4 are "B"
3 are "M"
2 are "y"
9 are "o"
10 are "u"
12 are "c"
4 are "h"
2 are "9"
2 are "#"
4 are "{"
2 are "X"
8 are "t"
4 are "}"
2 are "z"
6 are "("
7 are "m"
5 are "n"
2 are "i"
2 are "q"
6 are ")"
4 are "p"
4 are "|"
2 are "["
4 are ","
2 are "]"
2 are "*"
4 are "/"
3 are "b"
7 are "+"
2 are "<"
3 are "g"
2 are "!"
Besides unquoted numbers, my output has 1096 characters.
2 are "U"
2 are "="
3 are "'"
2 are "%"
5 are "d"
238 are " "
120 are "a"
120 are "r"
120 are "e"
222 are """
11 are "s"
114 are "
"
2 are "O"
3 are "I"
5 are "."
2 are "$"
2 are "0"
2 are "?"
2 are "\"
2 are "1"
2 are "2"
2 are "6"
2 are ">"
3 are "B"
3 are "M"
4 are "y"
9 are "o"
8 are "u"
7 are "c"
6 are "h"
2 are "9"
2 are "#"
2 are "{"
2 are "X"
9 are "t"
2 are "}"
2 are "z"
2 are "("
5 are "m"
4 are "n"
3 are "i"
3 are "q"
2 are ")"
4 are "p"
2 are "|"
2 are "["
3 are ","
2 are "]"
2 are "*"
2 are "/"
4 are "b"
2 are "+"
2 are "<"
4 are "g"
2 are "!"
It's good to be a program.

```

---
Tags: code-golf, quine
---


# Question
Title: Output nth term in Catalan type sequence
Given a number, starting with 1, create new numbers (children) by taking the last digit, n, and concatenating 1 through n+1.

This seems to be a much better explanation of the sequence A071159.

> Integers whose decimal expansion start with 1, do not contain zeros and each successive digit to the right is at most one greater than the previous.
>
> 1, 11, 12, 111, 112, 121, 122, 123, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1221, 1222, 1223, 1231, 1232, 1233, 1234, 11111, 11112, ...

Personally I find the description for the sequence rather unhelpful, and find it is easier to understand with a graph.

```
                              1
          11-------------------------------------12
      111----112                     121---------122----------123
1111-1112    1121-1122-1123    1211-1212    1221-1222-1223    1231-1232-1233-1234

```

I find the graph rather interesting as it is very self-repeating. For instance, the left-most node on a branch is always identical to the root node. Might be easier to see on this graph.

# Challenge

Submit a solution that can output the nth item of sequence A071159.

# Rules

Your submission should be able to calculate any item before number 23713. A071159(23713) is the first time a `10` would appear as a single digit (12345678910; comma-separated 1,2,3,4,5,6,7,8,9,10).

# Answer
## GolfScript (29 chars)

```
~([1]{.{.10*)\10%{.)}*}%|}9*=

```

This is a pretty naïve implementation, although reasonably fast.

```
~(         # Evaluate input, decrement to get a 0-based index
[1]        # Initial row of tree
{          # Loop: stack is the first n rows of the tree as an array
  .        # Duplicate the array
  {        # Map: extend each element of the array into its children
    .10*)  # Get the first child; stack is   rows x 10x+1
    \10%   # How many more children does x have?
    {.)}*  # Those children are found by successive incrementation
  }%       # End map
  |        # Add the new unique elements (i.e. the new bottom row) to the rows
}9*        # Repeat 9 times, so that the array has 23713 correct values and one incorrect
=          # Array lookup

```
> 3 votes

# Answer
# Python 2 (83) (86)

```
r=[1]
exec"r=[1]+[i+w*10for w in r for i in range(1,w%10+2)];"*9
print r[input()-1]

```

Explanation to come.

A completely different approach of counting up an testing for membership in the sequence (87 chars). Take ridiculously long for larger numbers,

```
n=0
k=input()
while k:n+=1;k-=all(0<int(b)<2+int(a)for a,b in zip('0'+`n`,`n`))
print n

```
> 2 votes

# Answer
# JAVA (146)

I know I'm not winning this, but oh well:

```
public class a{public static void main(String[]a){float b=Float.parseFloat(a[0]);float c=1;for(int i=2;i<=b;i++)c*=(i+b)/i;System.out.print(c);}}

```

Just straightforward from Wikipedia, any tips for further golfing this will be appreciated.
> 1 votes

# Answer
## Powershell (136)

```
$n=Read-Host;$x=,'1';$a=1;While($x.length-lt$n){$b=[int]$x[$a-1].Substring($x[$a-1].length-1);1..($b+1)|%{$x+=$x[$a-1]+$_};$a++}$x[$n-1]

```

Probably some wasted characters here, but I'm still learning. $a traverses the list as it's being built (each level of the tree). $b takes the last digit of the current item, then the loop after that adds on 1 to $b+1 to the end of the current item and adds it to the array $x.

Loop is a bit inefficient, as the $n-1 index is necessary because it doesn't always stop on the nth number of the sequence that you want.

But hey, it's my first draft. And it replicated the correct sequence output based on the input here.

Also an input of 23713 produces an output of 12345678910.
> 1 votes

# Answer
## Haskell (73)

```
c=1:((\n->[10*n+d|d<-[1..n`mod`10+1]])=<<)c;main=readLn>>=print.((0:c)!!)

```

And ungolfed:

```
step n = [ 10*n + d | d <- [1 .. lastDigit+1] ]
    where lastDigit = n `mod` 10

soln = 1 : concatMap step soln

main = do
    n <- readLn
    let nthTerm = soln !! (n - 1)
    print nthTerm

```

soln is a list containing the entire A071159 sequence.

The step function is not very interesting, just a straightforward list comprehension that takes a number to the list of its children in the OP's tree.

The main function's only trick is to do 1-based indexing of \[1,11,12,...\] by using 0-based indexing on \[0,1,11,12,...\], saving a character.

The real fun is in the recursive definition of soln, which does the breadth-first traversal of the OP's tree. A couple characters are saved by replacing concatMap with its generalization =\<\<.
> 1 votes

---
Tags: code-golf, math, combinatorics, sequence
---


title: Shortest test for primality for byte

text:
# Question
Title: Shortest test for primality for byte
Write a function which gets as input a number (`0 <= n <= 255`) stored in 32-bit variable and returns non-zero integer if `n` is prime number and `0` otherwise.
Consider`n = 0` and `n = 1` as non-primes.

Arrays and pointers are not allowed.

**Score:**
1 - for `| & ^ ~ >> <<` operators
1.1 - for `+ - < > <= >= == != ! && ||` operators and branches & loops
1.2 - for `*` operator
2 - for `/ %` operators
10 - for casting to/using other types (other than 32-bit integer)
Score for operators inside loops is score * max iterations count.

Answer with lowest score wins. If many answers with identical score, wins first one.

# Answer
# Python (4)

```
f = lambda n: (3622934801701902697686555901643181168549895964810913375391936802953324275884 >> n) & 1

```

Damn casting. No trickery here, just magic. Number generated with J: `#.x:1 p: i._256`. Output:

```
for i in enumerate(map(f,range(256))):
    ...:     print i
    ...:
(0, 0L)
(1, 0L)
(2, 1L)
(3, 1L)
(4, 0L)
(5, 1L)
(6, 0L)
(7, 1L)
(8, 0L)
(9, 0L)
(10, 0L)
(11, 1L)
(12, 0L)
(13, 1L)
(14, 0L)
(15, 0L)
(16, 0L)
(17, 1L)
(18, 0L)
(19, 1L)
(20, 0L)
(21, 0L)
(22, 0L)
(23, 1L)
(24, 0L)
(25, 0L)
(26, 0L)
(27, 0L)
(28, 0L)
(29, 1L)
(30, 0L)
(31, 1L)
(32, 0L)
(33, 0L)
(34, 0L)
(35, 0L)
(36, 0L)
(37, 1L)
(38, 0L)
(39, 0L)
(40, 0L)
(41, 1L)
(42, 0L)
(43, 1L)
(44, 0L)
(45, 0L)
(46, 0L)
(47, 1L)
(48, 0L)
(49, 0L)
(50, 0L)
(51, 0L)
(52, 0L)
(53, 1L)
(54, 0L)
(55, 0L)
(56, 0L)
(57, 0L)
(58, 0L)
(59, 1L)
(60, 0L)
(61, 1L)
(62, 0L)
(63, 0L)
(64, 0L)
(65, 0L)
(66, 0L)
(67, 1L)
(68, 0L)
(69, 0L)
(70, 0L)
(71, 1L)
(72, 0L)
(73, 1L)
(74, 0L)
(75, 0L)
(76, 0L)
(77, 0L)
(78, 0L)
(79, 1L)
(80, 0L)
(81, 0L)
(82, 0L)
(83, 1L)
(84, 0L)
(85, 0L)
(86, 0L)
(87, 0L)
(88, 0L)
(89, 1L)
(90, 0L)
(91, 0L)
(92, 0L)
(93, 0L)
(94, 0L)
(95, 0L)
(96, 0L)
(97, 1L)
(98, 0L)
(99, 0L)
(100, 0L)
(101, 1L)
(102, 0L)
(103, 1L)
(104, 0L)
(105, 0L)
(106, 0L)
(107, 1L)
(108, 0L)
(109, 1L)
(110, 0L)
(111, 0L)
(112, 0L)
(113, 1L)
(114, 0L)
(115, 0L)
(116, 0L)
(117, 0L)
(118, 0L)
(119, 0L)
(120, 0L)
(121, 0L)
(122, 0L)
(123, 0L)
(124, 0L)
(125, 0L)
(126, 0L)
(127, 1L)
(128, 0L)
(129, 0L)
(130, 0L)
(131, 1L)
(132, 0L)
(133, 0L)
(134, 0L)
(135, 0L)
(136, 0L)
(137, 1L)
(138, 0L)
(139, 1L)
(140, 0L)
(141, 0L)
(142, 0L)
(143, 0L)
(144, 0L)
(145, 0L)
(146, 0L)
(147, 0L)
(148, 0L)
(149, 1L)
(150, 0L)
(151, 1L)
(152, 0L)
(153, 0L)
(154, 0L)
(155, 0L)
(156, 0L)
(157, 1L)
(158, 0L)
(159, 0L)
(160, 0L)
(161, 0L)
(162, 0L)
(163, 1L)
(164, 0L)
(165, 0L)
(166, 0L)
(167, 1L)
(168, 0L)
(169, 0L)
(170, 0L)
(171, 0L)
(172, 0L)
(173, 1L)
(174, 0L)
(175, 0L)
(176, 0L)
(177, 0L)
(178, 0L)
(179, 1L)
(180, 0L)
(181, 1L)
(182, 0L)
(183, 0L)
(184, 0L)
(185, 0L)
(186, 0L)
(187, 0L)
(188, 0L)
(189, 0L)
(190, 0L)
(191, 1L)
(192, 0L)
(193, 1L)
(194, 0L)
(195, 0L)
(196, 0L)
(197, 1L)
(198, 0L)
(199, 1L)
(200, 0L)
(201, 0L)
(202, 0L)
(203, 0L)
(204, 0L)
(205, 0L)
(206, 0L)
(207, 0L)
(208, 0L)
(209, 0L)
(210, 0L)
(211, 1L)
(212, 0L)
(213, 0L)
(214, 0L)
(215, 0L)
(216, 0L)
(217, 0L)
(218, 0L)
(219, 0L)
(220, 0L)
(221, 0L)
(222, 0L)
(223, 1L)
(224, 0L)
(225, 0L)
(226, 0L)
(227, 1L)
(228, 0L)
(229, 1L)
(230, 0L)
(231, 0L)
(232, 0L)
(233, 1L)
(234, 0L)
(235, 0L)
(236, 0L)
(237, 0L)
(238, 0L)
(239, 1L)
(240, 0L)
(241, 1L)
(242, 0L)
(243, 0L)
(244, 0L)
(245, 0L)
(246, 0L)
(247, 0L)
(248, 0L)
(249, 0L)
(250, 0L)
(251, 1L)
(252, 0L)
(253, 0L)
(254, 0L)
(255, 0L)

```
> 4 votes

# Answer
The most obvious solution scores 32.3.

Test Ideone

```
int p(int v) {
  return (v > 1)
  & (v == 2 || (v % 2))
  & (v == 3 || (v % 3))
  & (v == 5 || (v % 5))
  & (v == 7 || (v % 7))
  & (v == 11 || (v % 11))
  & (v == 13 || (v % 13));
}

```
> 1 votes

---
Tags: arithmetic, optimization, atomic-code-golf
---


# Question
Title: Shortest expression for {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}
Given list of integers `{0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}`. For those who interested these numbers are used in weekday calculation.

Weekday = `(m[n] + d + y + y>>2 + y/400 - y/100) % 7;`, where `m[n]` \- expression I'm searching, `d` \- day of month, `y` \- `year - (month <= 2)`.

Construct expression consisting of arithmetic, logic and bitwise operators, which will output for positive integer `n` integer `m` so that `m % 7` equals n-th number in the list.

Branches, ternary operators, table lookups and pointers are not allowed.

**Score:**
1 - for `| & ^ ~ >> <<` operators
1.1 - for `+ - < > <= >= == != ! && ||` operators
1.2 - for `*` operator
1.4 - for `/ %` operators

Answer with lowest score wins.

Personally I have found:

> `(41*n)>>4+((n+61)>>4)<<2` with score 6.4. I thought this will be hard to find so provided own expression to start with.

# Answer
> 34 votes
# 2 2.2

I love arbitrary precision arithmetic.

```
0x4126030156610>>(n<<2)

```

Or, if you don't like hex,

```
1146104239711760>>(n<<2)

```

Test:

```
print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]

```

# Answer
> 33 votes
## 2.0

```
(127004 >> i) ^ 60233

```

or (score 2.2) :

```
(i * 3246) ^ 130159

```

All found with brute force :-)

# Answer
> 8 votes
## 35.3

I suspect this may be the least efficient method to create the list:

```
1.7801122128869781e+003 * n -
1.7215267321373362e+003 * n ^ 2 +
8.3107487075415247e+002 * n ^ 3 -
2.0576746235987866e+002 * n ^ 4 +
1.7702949291688071e+001 * n ^ 5 +
3.7551387326116981e+000 * n ^ 6 -
1.3296432299817251e+000 * n ^ 7 +
1.8138635864087030e-001 * n ^ 8 -
1.3366764519057219e-002 * n ^ 9 +
5.2402527302299116e-004 * n ^ 10 -
8.5946393615396631e-006 * n ^ 11 -
7.0418841304671321e+002

```

I just calculated the polynomial regression. I'm tempted to see what other terrible method could be attempted.

Notably, I could save 3.3 points if the result was rounded. At this point, I don't think that matters.

# Answer
> 5 votes
## 3.2

Zero based solution:

```
7 & (37383146136 >> (i*3))

```

One based solution:

```
7 & (299065169088 >> (i*3))

```

I initially thought that the `%7` operation would be counted as well and `%` being an expensive operation here, I tried to solve it without it.

I came to a result of 3.2 like this:

```
// Construction of the number
// Use 3 bits per entry and shift to correct place
long c = 0;
int[] nums = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
for (int i = nums.Length - 1; i >= 0; i--)
{
    c <<= 3;
    c += nums[i];
}
// c = 37383146136

// Actual challenge
for (int i = 0; i < 13; i++)
{
    Console.Write("{0} ",7 & 37383146136 >> i*3);
}

```

I'd be interested in optimizations using this approach (without `%`). Thanks.

# Answer
> 0 votes
# Python (3)

Since there are quite a few of these questions these days, I decided to make a program to automatically solve them in 3 (or 2) tokens. Here's the result for this challenge:

```
G:\Users\Synthetica\Anaconda\python.exe "C:/Users/Synthetica/PycharmProjects/PCCG/Atomic golfer.py"
Input sequence: 0 3 2 5 0 3 5 1 4 6 2 4
f = lambda n: (72997619651120 >> (n << 2)) & 15
f = lambda n: (0x426415305230L >> (n << 2)) & 15
f = lambda n: (0b10000100110010000010101001100000101001000110000 >> (n << 2)) & 15

Process finished with exit code 0

```

Proof that this works:

```
f = lambda n: (72997619651120 >> (n << 2)) & 15

for i in range(12):
   print i, f(i)

0 0
1 3
2 2
3 5
4 0
5 3
6 5
7 1
8 4
9 6
10 2
11 4

```

---
Tags: math, arithmetic, date, atomic-code-golf
---


# Question
Title: Find a route between two Wikipedia articles
# Introduction

Recently, I was skyping with a bunch of friends and we got bored and had nothing to do, so we "invented" a "game" (some people in the comments pointed out that this game is playable online and very popular, so we definetely didn't invent it, although I hadn't seen it before). The reason I put the word "game" in quotation marks is because it's not an actual computer game, but it's played on Wikipedia.

It's really easy to play: Someone chooses some Wikipedia article as the goal. Let's assume *Code Golf* for this example. All the players then have to start from a random article (by pressing *Random Article* in the sidebar or going to this URL) and have to get to the "goal" as quick as possible using **only linked articles of the article you are currently at**. Rules include:

* The search function is not allowed (obviously)
* You may only click links in the article's main text (specifically all text inside `<div id="bodyContent">`)
* If your random page or any other page you encounter has no valid links (dead links, loops, etc) or no links at all you may roll again.

# The challenge

Here's where you come in: unfortunately I'm pretty bad at this game, but I'm also a dirty cheater. So I want you to implement this bot for me. I'm also a programmer, so naturally my hard disk is full of stuff like code, libraries and such and I only have a few bytes of memory to spare. Therefore this challenge is Code Golf, the answer with the least **bytes** wins.

## Implementation Details:

* Of course you don't have to implement an intelligent bot that knows connections between topics and automatically detects the optimal route. Brute forcing is more than enough for the purpose of this challenge
* In the actual game, time counts. Your program shouldn't take longer than 1 hour to find the article (this is to avoid loopholes like random searchers that will "eventually" find the goal)
* If no path to the goal can be found (e.g. dead links or a loop) you can choose what to do from the list below:
    + Quit (score remains the same)
    + Get another random article and try again and do nothing on loops (score -= 10)
    + Get another random article on a dead link or a loop (detect loops automatically) (score -= 50)
    + (By "score" I mean your byte count here)
* Another 20 bonus bytes will be subtracted if you "trace" the route, so you print the title of every individual page you visit.
* Standard network libraries may be used (to avoid loopholes like "I crafted my own network library which crawls wikipedia articles")
    + The only thing network-related your program should do is send a HTTP request to download a wikipedia page
* If your program finds the page, it should quit, but somehow signalize that it finished (printing the character "f" or the title of the page is enough)
* Standard loopholes are to be avoided

**Have fun golfing!**

*(This is my first question here, so please point out obvious loopholes and caveats in the comments before exploiting them - thanks :D)*

# Answer
## Python 373 -\> 303

It reads the Wikipedia destination from `input()` (user input) and should be in the format of `/wiki/dest`. So, something like `/wiki/Code_golf` or `/wiki/United_States`. It also uses one space for the indents and `http://enwp.org` instead of Wikipedia's full URL to save bytes.

* -50 because if it finds a broken URL it gets a new random URL.
* -20 because it prints the title of each URL visited (could change title -\> URL, but title is cleaner and actually makes my source larger).

It hangs every once and a while, and I can't figure out why. Perhaps because of Wikipedia rate limits?

I found the Boston Red Sox Wikipedia page in 9 minutes 20 seconds, and the United States page in under 10 seconds, so it shouldn't take *too* long to find Code Golf...

```
from mechanize import*;from lxml.html import*;from random import*;a=Browser();a.set_handle_robots(0);i='http://enwp.org/Special:Random';t=input();d={};k=a.open
def f(o):
 if o!=i:d[o]=o
 if o in d:f(i)
 try:v=fromstring(k(o).read()).xpath('//div[@id="content"]//a/@href')
 except:f(i)
 print a.title()
 if t in v:k(t);print 'f';exit()
 else:f(choice(v)) if v else f(i)
f(i)

```
> 12 votes

---
Tags: code-golf
---


# Question
Title: Compact coding of integer into bitstring
I want to compactly code positive integers `x` into bits, in a manner allowing decoding back into the original integers for a stateless decoder knowing the maximum value `m` of each `x`; it shall be possible to uniquely decode the concatenation of encodings, as is the case in Huffman coding.
<sub>\[The above introduction motivates the rest, but is not part of the formal definition\]</sub>

Notation: for any non-negative integer `i`, let `n(i)` be the number of bits necessary to represent `i` in binary; that is the smallest non-negative integer `k` such that `i>>k == 0`

```
  i :   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  ..
n(i):   0   1   2   2   3   3   3   3   4   4   4   4   4   4   4   4   5   5   5   ..

```

I want a function `F(x,m)` defined for `0<x` and `x<=m`, with output a string of '`0`' or '`1`', having these properties:

1. `F(x,m)` has length less than `2*n(x)` or `2*n(m)-1`, whichever is smaller.
2. If `x<y` then:
    * `F(x,m)` is no longer than `F(y,m)`;
    * `F(x,m)` and `F(y,m)` differ at some position over the length of `F(x,m)`;
    * there's a `0` in `F(x,m)` at the first such position.
3. When for a certain `m` properties 1 and 2 do not uniquely define `F(x,m)` for all positive `x` at most `m`, we reject any encoding giving a longer `F(x,m)` than some otherwise acceptable encoding, for the smallest `x` for which the length do not match.

Note: In the above, implicitly, `0<x`, `0<y`, `0<m`, `x<=m`, and `y<=m`, so that `F(x,m)` and `F(y,m)` are defined.

It is asked the shortest program that, given any `x` and `m` meeting the above constraints and up to 9 decimal digits, outputs an `F(x,m)` consistent with the above rules. The following C framework (or its equivalent in other languages) is not counted:

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define C(c) putchar((c)?'1':'0') // output '0' or '1'
#define S(s) fputs((s),stdout)    // output a string
typedef unsigned long t;          // at least 32 bits
void F(t x,t m);                  // prototype for F
int main(int argc,char *argv[]){
 if(argc==3)F((t)atol(argv[1]),(t)atol(argv[2]));
 return 0;}
void F(t x,t m) {   // counting starts on next line
}                   // counting ends before this line

```

---

Comment: Property 1 aggressively bounds the encoded length; property 2 formalizes that unambiguous decoding is possible, and canonicalizes the encoding; I assert (without proof) this is enough to uniquely define the output of `F` when `m+1` is a power of two, and that property 3 is enough to uniquely define `F` for other `m`.

Here is a partial table (handmade; the first version posted was riddled with errors, sorry):

```
  x     :   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
F(x,1)  : empty
F(x,2)  :   0       1
F(x,3)  :   0       10      11
F(x,4)  :   0       10      110     111
F(x,5)  :   0       10      110     1110    1111
F(x,6)  :   0       100     101     110     1110    1111
F(x,7)  :   0       100     101     1100    1101    1110    1111
F(x,8)  :   0       100     101     110     11100   11101   11110   11111

F(x,15) :   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111

```

# Answer
> 1 votes
# Python 3, 163 bytes

```
n=int.bit_length
R=range
def F(x,m,c=0):
 for i in R(x):L=2*n(m)-2;D=1<<L;r=n(D-c-sum(D>>min(2*n(x+1)-1,L)for x in R(i+1,m)))-1;v=c;c+=1<<r
 return bin(v)[2:L+2-r]

```

Ignore the `c=0` parameter, that's a golf trick.

This greedily chooses the shortest possible representation for each number, subject to the condition that the remaining numbers are still representable. Therefore, by construction, it exactly satisfies the desired properties. It is actually not that hard to modify this code to support a different set of coding rules, as a result.

For example, here are the outputs up to `m=15`:

```
m\x |   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
----+----------------------------------------------------------------------------------------------------------------------------
1   |
2   |   0       1
3   |   0       10      11
4   |   0       10      110     111
5   |   0       10      110     1110    1111
6   |   0       100     101     110     1110    1111
7   |   0       100     101     1100    1101    1110    1111
8   |   0       100     101     110     11100   11101   11110   11111
9   |   0       100     101     110     11100   11101   11110   111110  111111
10  |   0       100     101     1100    1101    11100   11101   11110   111110  111111
11  |   0       100     101     1100    1101    11100   11101   111100  111101  111110  111111
12  |   0       100     101     1100    11010   11011   11100   11101   111100  111101  111110  111111
13  |   0       100     101     1100    11010   11011   11100   111010  111011  111100  111101  111110  111111
14  |   0       100     101     11000   11001   11010   11011   11100   111010  111011  111100  111101  111110  111111
15  |   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111

```

# Answer
> 2 votes
# Python, 171

```
def F(x,m):
 a=0;b=[9]
 while len(b)<m:
    if 4**len(bin(len(b)))*2>64*a<4**len(bin(m)):
     if(a&a+1)**a:b+=[a];a+=1
     else:a*=2
    else:a=b.pop()*2
 return bin((b+[a])[x])[2:]

```

Note that lines that appear to begin with 4 spaces actually begin with a tab.

Testing, with bitpwner's test script:

```
         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15
F(x,1)   0
F(x,2)   0        1
F(x,3)   0        10       11
F(x,4)   0        10       110      111
F(x,5)   0        10       110      1110     1111
F(x,6)   0        100      101      110      1110     1111
F(x,7)   0        100      101      1100     1101     1110     1111
F(x,8)   0        100      101      110      11100    11101    11110    11111
F(x,9)   0        100      101      110      11100    11101    11110    111110   111111
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111
F(x,12)  0        100      101      1100     11010    11011    11100    11101    111100   111101   111110   111111
F(x,13)  0        100      101      1100     11010    11011    11100    111010   111011   111100   111101   111110   111111
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111

```

Explanation:

This is all based on the observation that between two consecutive elements of the code, F(x,m) and F(x+1,m), we always add one to the binary number, then multiply by two some number of times. If these steps are followed, then it is a valid code. The rest simply tests to make sure it is short enough.

Golfs: 175 -\> 171: changed 2\**(2\*... to 4\**

# Answer
> 1 votes
# Python - 370

Creates a huffman tree, balances it to fit the rules, then does a walk through the tree to get the final values.

```
def w(n,m,c,p=""):
    try:[w(n[y],m,c,p+`y`)for y in 1,0]
    except:c[n[0]]=p
d=lambda x:len(x)>1and 1+d(x[1])
v=lambda x,y:v(x[1],y-1)if y else x
def F(x,m):
    r=[m];i=j=0
    for y in range(1,m):r=[[m-y],r]
    while d(r)>len(bin(m))*2-6-(m==8):g=v(r,i);g[1],g[1][0]=g[1][1],[g[1][0],g[1][1][0]];i,j=[[i+1+(d(g)%2<1&(1<i<5)&(m%7<1)),j],[j+1]*2][d(g)<5]
    c={};w(r,m,c);return c[x]

```

For a more succinct solution that is based on the emergent pattern, look at isaacg's answer.
It's a good example of how a completely different approach can solve the problem.

Test:

```
chars = 8
maxM = 15
print " "*chars,
for m in range(1,maxM+1):
    p = `m`
    print p+" "*(chars-len(p)),
print
for m in range(1,maxM+1):
    p = "F(x,"+`m`+")"
    print p+" "*(chars-len(p)),
    for x in range(1,maxM+1):
        try:
            q = `F(x,m)`[1:-1]
            print q+" "*(chars-len(q)),
        except:
            print
            break

```

Results:

```
         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15
F(x,1)
F(x,2)   0        1
F(x,3)   0        10       11
F(x,4)   0        10       110      111
F(x,5)   0        10       110      1110     1111
F(x,6)   0        100      101      110      1110     1111
F(x,7)   0        100      101      1100     1101     1110     1111
F(x,8)   0        100      101      1100     1101     1110     11110    11111
F(x,9)   0        100      101      1100     1101     1110     11110    111110   111111
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111
F(x,12)  0        100      101      11000    11001    11010    11011    11100    11101    11110    111110   111111
F(x,13)  0        100      101      11000    11001    11010    11011    11100    11101    111100   111101   111110   111111
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111

```

---
Tags: code-golf
---