# Question
Title: Calculate Network Average Clustering Coefficient
The clustering coefficient of a graph (or network) is a:

> measure of degree to which nodes in a graph tend to cluster together

The Wikipedia article gives a much better description of how network average clustering coefficient is calculated from local clustering coefficients than I could give.

## The Challenge

Given an adjacency matrix `a` describing an undirected network (or graph) with no self loops, calculate it's network average clustering coefficient.

### Details

* You must write a program/function/procedure/code block which calculates the network average clustering coefficient for any undirected graph with no self loops.
* The output may only contain the coefficient and nothing else.
* You are to assume that your program (or whatever) has access to an adjacency matrix describing the graph through a variable/the stack/file/whatever
* You may not use any inbuilt functionality your language may have to calculate clustering coefficients
* **Shortest code wins**

### Test Examples

Test inputs and outputs can be found in this pastebin

### My solution: GNU Octave, 93 chars

(behind spoiler)

> ```
> f=sum(a);c=0;for i=find(f>1)c+=sum(a(t=find(a(i,:)),t)(:))/(f(i)*(f(i)-1));endfor;c/length(a)
> ```

Which can be tested here, the matrix needs to be in the format `a = [row ; row ; row ; ...]`

# Answer
# Python: 192 Characters (not including whitespace)

```
import itertools
def l(a,i,r):
    s=[b for b in r if a[i][b]]
    k=len(s)
    if k<2:
        return 0
    return 2.0*sum(map(lambda x:a[x[0]][x[1]],itertools.combinations(s,2)))/k/(k-1)
def g(a):
    n=len(a)
    r=range(n)
    return sum([l(a,i,r) for i in r])/n

```

# Example Usage:

```
>>> g([[1, 1, 1], [1, 1, 1], [1, 1, 1]])
1.0
>>> g([[0, 1, 0, 0, 0, 1, 0, 0],
       [1, 0, 1, 1, 1, 0, 1, 0],
       [0, 1, 0, 0, 0, 1, 0, 0],
       [0, 1, 0, 0, 1, 0, 0, 0],
       [0, 1, 0, 1, 0, 1, 1, 0],
       [1, 0, 1, 0, 1, 0, 0, 1],
       [0, 1, 0, 0, 1, 0, 0, 1],
       [0, 0, 0, 0, 0, 1, 1, 0]])
0.233333333333
>>> g([[0, 1, 0, 0, 1],
       [1, 0, 1, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 1, 0, 1],
       [1, 0, 0, 1, 0]])
0.0
>>> g([[0,1,1,1,0,1,1,1,1,0,1,0,0,0,1,0,0,0,0,1],
       [1,0,0,0,1,0,0,0,1,1,1,1,0,1,0,0,1,0,0,1],
       [1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,1,0],
       [1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,0,0,1],
       [0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,0,0,1,0],
       [1,0,1,0,1,0,0,1,0,0,1,1,0,0,0,1,0,1,1,1],
       [1,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,0,0,1,0],
       [1,0,0,1,1,1,1,0,1,1,0,0,0,0,0,0,1,0,0,0],
       [1,1,1,1,1,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0],
       [0,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0],
       [1,1,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0],
       [0,1,0,1,0,1,1,0,0,0,0,0,1,1,1,1,0,1,0,0],
       [0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1],
       [0,1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0],
       [1,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,1,1,1,0],
       [0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,1],
       [0,1,0,0,0,0,0,1,1,0,0,0,1,1,1,0,0,0,1,1],
       [0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,0,0,0,0,0],
       [0,0,1,0,1,1,1,0,1,0,1,0,0,1,1,1,1,0,0,1],
       [1,1,0,1,0,1,0,0,0,0,0,0,1,0,0,1,1,0,1,0]])
0.389888167388
>>> g([[0,1,1],
       [1,0,0],
       [1,0,0]])
0.0

```
> 1 votes

---
Tags: code-golf, graph-theory
---


title: Generate ASCII wilderness map

text:
# Question
Title: Generate ASCII wilderness map
Generate an ASCII wilderness map.

**Example output:**

```
................^^^^
..................^^
...^^^^........o....
.....^^^^...........
....................
........o....TT.....
..TTTT..............
TTTT.TTTT....~~~~~~.
..TT..........~~~~~~
....................

```

**Anti-example (don't do this):**

```
....................
...........T........
...^..........oo....
......^.............
....................
..............TT....
T.T.T.T.T........T..
.................T..
T.T.T.T.T..........T
..............TT...T

```

**Rules:**

1. Must be at least 20x10 characters in size
2. Must be different each run, i.e. random
3. Must contain continuous and varying shape areas of trees 'T', hills '^' and water '~', most of which should consist of more than 5 cells
4. The default, ground character is '.'
5. Must contain at least 2 villages 'o' that are usually not next to each other
6. Must not contain obvious patterns, such as rectangles or evenly spaced areas - "natural look" is the key
7. You don't need to explicitly check that the rules are followed (e.g. no need for anti-rectangle logic), but the great majority of the runs (say, 80%) must produce conforming results
8. With your submission, include an example output

**Scoring:**

Winner has lowest score from formula: `code character count` \- `votes`

# Answer
## APL (~~99~~ 76)

```
F←⍳S←10 20⋄'.T^~^To'[⊃7⌊1++/(⊂7×F∊{?S}¨⍳2),T×{F∊(?S)∘+¨+\{2-?3 3}¨⍳99}¨T←⍳3]

```

~~A bit longer than it needs to be (so that it gives better output) but I'll shorten it when the Golfscript answer comes in.~~

The GolfScript answer was posted so here's a shorter one. I thought of another (rather obvious, in hindsight) way to shorten it so that the output is not much worse than the original program, and it's even shorter than my original backup plan.

(In the old version, I had five bitfields that I was xor-ing with each other, now I have three that I am adding to each other.)

I have replaced the example output with output of the new version, of course.

Explanation:

* `F←⍳S←10 20`: size is 20x10, F is a matrix where each element is its coordinates
* `{F∊(?S)∘+¨+\{2-?3 3}¨⍳99}¨T←⍳5`: generate 3 bitfields, by starting at a random coordinate, and taking 99 random steps to a neighbouring field and then setting that bit on. 99 seems high but it often backtracks as it is random. This makes the maps for the areas.
* `(⊂7×F∊{?S}¨⍳2)`: Add in two villages.
* `⊃7⌊1++/`: sum the areas, giving a matrix where each number represents a certain type. Cap it at 7, because the villages might appear in another area giving high numbers.
* `'.T^~^To'[`...`]`: replace each number with the right character. There are 3 possibly overlapping fields so the highest possible value is 6. (3+3)

Example output:

```
....TTT.TTT...TTT.^^
...TT....TTT....T..^
....T....TT.......^^
...~..o..T..^^...^^.
...~.........^^^^^^^
...~~~~....^^..^^^..
~..~~~......^.^.^^^^
~~.~~~......^^.^^^..
~.~~~~........o.....
~~~~~~..............

```

and

```
.....o........~~..~~
..............~~~~~.
.^T.T..........~~.~.
^T~~TTTTTT.......~~~
~~~~TT.TT.T......~~~
^~^TTT....T.....~~~~
^^^^T.....T...T..~~.
^^^^.......TT.T.....
^^^^.........TT.....
^^^^.........o......

```

Old version:

```
F←⍳S←10 20⋄G←{F∊(?S)∘+¨+\{2-?3 3}¨⍳99}¨T←⍳5⋄'.T^~^To'[⊃7⌊1++/(⊂7×F∊{?S}¨⍳2),T×{(⊃⍵⌽G)∧~⊃∨/1↓⍵⌽G}¨T]

```
> 5 votes

# Answer
**JavaScript - 294 290 characters**

To encourage attempts, I took a crack at this myself. You can try a live demo here (you need to open your browser's JS console). Tested with Chrome and IE8.

```
R=function(a){return Math.random()*a|0};t=["~","T"];t.splice(R(3),0,"^");p=["XXX..","XXXX.","XXXXX"];b="....................";for(i=j=0;10>i;++i)j=i%3?j:R(15),s=b.substr(0,i%3?j+R(2):20),s+=p[R(3)].replace(/X/g,t[i/3|0])+b,k=R(19),console.log(s.substr(0,k)+".o"[i%2*R(2)]+s.substr(k,19-k));

```

Example output:

```
....................
.......~~~..........
........~~~~~.......
...o................
...............TT.TT
..........o....TTTTT
....................
.....^^^.o..........
.....^^^^^..........
..................o.

```

It's not ideal, as there is always only three areas (one of each kind), their maximum size is 5x2 cells and after a few runs, you start to notice limitations in their (and villages') placement. However, it fulfills the rules.
> 4 votes

# Answer
### GolfScript, 97 characters

```
"T~^o"1/{:z{[20:s.*:<rand{.[s~)1-1s]4rand=+}z"o"=!9**]}3*++}%2/:x;<,{"."x{)3$\?)!!*+}/\;-1=}%s/n*

```

Example outputs:

```
.............~......
...........~.~~.....
........~~~~~~......
........~~~.........
.......~~~..........
.......~............
..^^..............T.
^^^^...........o..T.
...^....TTT...^...T^
^........TT.o.^^^.^^
^.......TT.....^^.T.
........T......^.TT.
................TT..
....................
....~~~.............
....~.~.............
..~o~...............
..~.....TTTT........
.......TT..TT.......
....................

```

and

```
.............~......
.............~......
....TTT.....~~TT....
....T.T.....~~TT....
....TT......~~~TT...
.....T.....~~~~T....
.......^^.~~~~......
......^^^..~~.......
......^.^...........
....................
..^^^^..............
..^..^^.............
....^^^^^...........
.......o........TT..
................TT..
....................
......o.............
.............o......
....................
....................

```
> 3 votes

# Answer
## Ruby 1.9 (~~127~~ ~~116~~ ~~112~~ 107)

```
m=?.*o=W=200
29.times{|i|o+=i%9-i/28>0?[-1,1,20].sample: rand(W);m[o%W]='T~^'[i/9]||?o}
puts m.scan /.{20}/

```

The output is a bit plain, but I think it mostly meets the spec!

Some example outputs:

```
....................
........TTTTTTT.....
........T^^^........
.........^..........
.........^..........
.........^^^.o......
....................
.....~.o............
...~~~..............
...~~~~~............

```

Another:

```
.....^^.............
......^^............
.......^^...........
...........o........
....................
..............T~~~..
.............TT~~...
.............T.~....
.............T.~....
.o..^^.......TT~....

```

And again:

```
.....TT.............
..............~.....
..............~.....
..............~~....
..............~~~...
........^^^.........
....o.T...^.........
......TT..^^^.......
..o..TT....^^.......
.....T..............

```

~~Due to the way it's coded, there's almost always a lone tree. I like to imagine it's the Deku tree.~~
> 2 votes

# Answer
# Q (~~116~~ 107 char)

Here's one in Q

```
(-1')20 cut@[199{.[t!`s#'(0 20 20 20;0 0 20 20;0 0 0 20;0 1 2 3)!\:t:"T^~.";(x;rand 30)]}\".";2?200;:;"o"];

```

Sample output

```
...........o........
...~~....TTTT..~~o..
......TTTTTTTTT....T
T...................
......^^^........TTT
...~~~~.............
....................
............^^......
..~~~..^^^^^^.......
....~..............T

```

and

```
..........^^^..^...o
....................
........^.T.........
.......~~...^.......
....................
....TTTTTTTT....^...
..~.................
.o.....^^^^^.......T
............~~~~~~~~
~~~~~....TTT........

```

and

```
....................
...~~~~~~~~~~.....~.
................TT..
....TTTTT..~.TT.TTTT
T................TTT
TTT..........TTTTTTT
TTT....T............
........T.......TToT
TTT..............^^.
...TTT..^.~~~~.o....

```

I can tweak the stochastic matrix to affect the output but I think the above conforms what you're looking for.

/edit: tweaked output

/edit: reduced char count by only adding 2 villages
> 1 votes

# Answer
# K, 84

```
f:{,/{x+!y}'[5?200;5?10]};m::200#".";{@[`m;x;:;y]}'[(f`;f`;f`;2?200);"~T^o"];10 20#m

```

Output:

```
"...................T"
"TTTTT~....TTT...^^^."
"...................^"
"^^..............^^^^"
"^^^..~~~~.......^^o."
".........TTTTT......"
"..~~~~~~........TTTT"
"TTT.~..............."
".........o.....^^^^."
"..........TTTTT....."

```

and

```
"...............~~~.."
".......~~~~~......TT"
"TTTT.^^^^^^^^......."
"....TT......~~......"
"..........^........."
"...........oTTT..^^^"
"^^^^^^..........^^^^"
"^^...TTTTTTT........"
"................o.~~"
"~~~.............T..."

```
> 1 votes

---
Tags: code-golf, ascii-art, random, generation
---


title: Generate Friedman numbers

text:
# Question
Title: Generate Friedman numbers
A Friedman number is a number that can be expressed by applying basic mathematical operations(^,/,\*,+,-) to all it's digits. The operations need not be applied to each individual digit, but all the digits must be involved. That is, 121= 11^2 --\> all digits are involved, but 1 & 1 have been clubbed together to make 11.

Use of parenthesis is allowed, but the trivial solution `x= (x)` is not a valid solution. Also not valid, `x= +x`.

Examples

* 25= 5^2
* 121= 11^2
* 343= (3+4)^3
* 2048 = (8^4)/2+0

Write a program that will take positive two integers and print the number of Friedman numbers in that range(inclusive), and the numbers with the expressions in subsequent lines.

Input -

```
n m    | n, m integers, n>=0, m>n

```

Output -

```
count    | number of Friedman numbers in the given range
fn1 exp1 | Friedman number, expression
fn2 exp2
fn3 exp3
.
.
.

```

Shortest code posted by Sunday 29th July 00:00 Hrs GMT will be the winner.

# Answer
> 3 votes
# Ruby, ~~456 438 408 390 370 349 344~~ 334 bytes

```
g={}
f=->a,b{a.permutation(b).to_a.uniq.flatten.each_slice b}
F,T=$*
([F.to_i,10].max..T.to_i).map{|c|f[a="#{c}".split(''),v=a.size].map{|m|f[[?+,?-,?*,?/,'','**'],v-1].map{|w|(d=(s=m.zip(w)*'').size)==v&&next
0.upto(d){|y|y.upto(d+1){|u|begin(r=eval t="#{s}".insert(y,?().insert(u,?)))==c&&g[r]=t
rescue Exception
end}}}}}
p g.size,g

```

Output:

```
% ruby ./friedman-numbers.rb 1 300
9
{25=>"(5)**2", 121=>"(11)**2", 125=>"5**(2+1)", 126=>"(6)*21", 127=>"(2)**7-1", 128=>"2**(8-1)", 153=>"(3)*51", 216=>"6**(1+2)", 289=>"(9+8)**2"}

```

Also it works relatively fast for larger numbers:

```
% time ruby friedman-numbers.rb 3863 3864
1
{3864=>"(6**4-8)*3"}
ruby friedman-numbers.rb 3863 3864  14.05s user 0.17s system 99% cpu 14.224 total

```

# Answer
> 4 votes
### Python 2.7 - 380 378 372 371 367 363 357 354 352 348 336 chars

Just a simple brute force search.

```
from itertools import*
s=lambda x:[x]['1'>x>'0':]+['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))]
def E(e):
 try:return eval(e.replace("^","**"))
 except:0
A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}
print len(A)
for v in A:print v,A[v]

```

### Example run:

```
1
300
9
128 (2^(8-1))
289 ((9+8)^2)
216 (6^(1+2))
121 (11^2)
153 (3*51)
25 (5^2)
125 (5^(2+1))
126 (6*21)
127 ((2^7)-1)

```

### Explanation:

`s(x)` is a function that takes a string containing a sequence of digits and returns all expressions using those digits in that order.

`[x]['1'>x>'0':]` evaluates to a list containing x if x is '0' or a sequence of digits not starting with '0'; otherwise, it evaluates to an empty list. Basically this handles the case where I join all the digits together.

`['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))]` basically partitions x into two parts (both being of non-zero length), calls s() on each part and joins all the results together with some operator between them, by using product().

`E(e)` is basically a safe eval. It returns the value of e if e is valid and None otherwise.

```
A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}

```

Basically this code tries all the numbers in the range, permutes their digits and tests each expression s() generates for that permutation, ignoring the first expression if x doesn't start with '0', because if x doesn't start with '0' then the first expression will just be x.

### Alternate version - 397 chars

Here is my code if you are required to use fractions:

```
from fractions import*
from itertools import*
s=lambda x:["Fraction(%s)"%x]['1'>x>'0':]+['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))]
def E(e):
 try:return eval(e.replace("^","**"))
 except:0
A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}
print len(A)
for v in A:print v,A[v].replace("Fraction","")

```

# Answer
> 3 votes
### Python3 ~~(436)~~ ~~(434)~~ (443)

It was hard. I can spare some characters if I make output more native.

```
from itertools import*
r={};k=product;m=map
q=lambda n,h=1:["("+i+c+j+")"for(i,j),c in k(chain(*[k(*m(q,f))for f in sum(([(x[:q],x[q:])for q in range(1,len(x))]for x in m("".join,permutations(n))),[])]),list("+-*/^")+[""]*h)]if 1<len(n)else[n]*h
a,b=m(int,m(input,"nm"))
for i,j in chain(*[k(q(str(n),0),[n])for n in range(a,b+1)]):
    try:exec("if eval(%r)==j:r[j]=i"%i.replace("^","**"))
    except:0
print(len(r))
for j,i in r.items():print(i,j)

```

Output

```
n100
m200
6
(2^(8-1)) 128
(3*(51)) 153
((11)^2) 121
(5^(1+2)) 125
(6*(21)) 126
((2^7)-1) 127

```

# Answer
> 1 votes
# Mathematica 456 416 402 404 400 396 chars

```
<< Combinatorica`; l = Length; p = Permutations; f = Flatten; c = Cases;
u[d_, o_, s_] :=
 Fold[#2[[1]] @@ If[s == 1, {#1, #2[[-1]]}, {#2[[-1]], #1}] &,
 d[[1]], Thread@{o, Rest@d}];
q[t_, r_] := {u[t, #, r], u[HoldForm /@ t, #, r]} & /@
p[{Plus, Subtract, Times, Divide, Power}, {l@t - 1}];
v[m_, n_] := (t = Table[Union@
  c[f[{#~q~1, #~q~0} & /@
     f[p /@ c[
        FromDigits /@ # & /@
         f[SetPartitions /@ p@IntegerDigits@j, 1], x_ /; l@x > 1],
       1], 2], {j, _}], {j, m, n}]~f~1; {l@t}~Join~t)

```

**Example**:

```
v[1,300]//TableForm

```

**Output**:

---
Tags: code-golf
---


title: The smallest self-improving program

text:
# Question
Title: The smallest self-improving program
The goal is to write a program that learns from its own mistakes, and improves itself based on it. This means, that later attempts at the problem should be either faster or more accurate, than earlier ones.

To deny trivial solutions, here is a set of rules (they are rather obvious):

* you can choose the problem to be solved, but your choice will be voted upon.
* the program should read input, this means the problem must have input variables, and its output should depend on that input.
* later runs of the algorithm should be better (at least after a certain number of runs) than the previous ones. Better can mean faster, or more optimal, or more accurate.
* the improvement must be real, and not just the disabling of purposefully introduced inhibitors like `if (never_run_before()) sleep(100);`
* the improvement must be caused by your program, and not external factors (like the OS giving faster access to a resource, if it was already opened or more often accessed before)
* the iterations can be either successive runs of the program while you save knowledge to a non-volatile storage, or you can have an interactive program which reads input again and again for successive runs of the algorithm.
* there should be improvement besides the situation where the algorithm runs faster given the exact same input data. (just storing previous results and doing nothing else would be too cheap). This means, there should be some improvement even if there is no repetition in the input data, for example if the task is to solve a maze, the input maze might be different each time.
* the algorithm must be part of your program, so the use of existing machine-learning tools is not allowed (otherwise it would be a too easy win for Matlab and its built-in neural network)

The score is: **number of characters - 5 * score form votes**. It can be negative. Smallest wins. Winner will be selected not sooner than 10 days after the first valid solution, and has to have a positive vote score.

For voters: the golfing is already an independent part of the score, so pleas don't vote based on the amount of golfing, but on the cleverness of the solution and the hardness and originality of the chosen problem (a program playing a game against the user should worth more than a program calculating the digits of pi)

# Answer
# GNU Octave / MATLAB, 14

```
f=@(n)n+sin(n)

```

You don't generally take a standard input with Octave programs, so this is a function which gives an improved estimate of pi after every call on its previous output. Sample run:

```
octave> f=@(n)n+sin(n);
octave> format 'long'
octave> n = 1;
octave> n = f(n)
n =  1.84147098480790
octave> n = f(n)
n =  2.80506170934973
octave> n = f(n)
n =  3.13527633289972
octave> n = f(n)
n =  3.14159261159065
octave> n = f(n)
n =  3.14159265358979

```
> 12 votes

# Answer
## Python, 12

This program golfs itself, improving its own score for this challenge. It takes two iterations to fully optimize itself.

initial program

```
print'print'

```

first output / second program

```
print

```

second output / third program: newline

third output / fourth program: empty

all subsequent programs: empty
> 8 votes

---
Tags: code-challenge
---


title: Perfect Hangman in reverse

text:
# Question
Title: Perfect Hangman in reverse
This is similar to other hang-man style problems already posted, except, in this case, the computer is the one guessing. Computers are logical, smart, and consider self-preservation to be important, so there are a few RULES for how computers will guess.

The user will think of any word, that will be contained in the FULL Ispell word list. some of these may be upwards of 10-15 letters. The wordlist is simply the full ispell wordlist (english, and others, all combined), and may be placed in a folder with the program.

The computer will be given 8 lives. The computer will start by simply asking for an input of however many characters the word is. (example game below). After that, the computer will begin guessing, following the ruleset below!

1. the computer will analyze all possible word outputs, and determine what letter guess has the most possible correct answers, and guess that letter. It will not duplicate any prior guesses.
2. the computer will then ask for an updated word input, determine if it was correct at all, or wrong, and if wrong, will deduct 1 life.
3. Lastly, the computer will state the lives remaining.

```
EXAMPLE GAME
User picks the word "Engineer"
Computer asks for Letter count, User replies 8.
Computer searches for most likely letter to be used in 8 letter words, determines it is letter H (not correct). Guesses H.
User replies _ _ _ _ _ _ _ _
Computer outputs "7 lives remaining" and then picks the next most likely letter, an E
User replies e _ _ _ _ e e _
computer outputs "7 lives remaining" and then recalculates based on its current knowledge what is the most likely next letter.
Game continues until computer will state WIN, or LOSE.

```

SCORING: every program should follow the EXACT same method to arrive at the final answer. If yours follows the order of every other program, you receive -100 points. If yours is different (aka wrong), you receive 1000 points.

each byte of code is worth 1 point. a 30 letter code, is 30 points.

if your code manages to play each step of the game in less than 5 seconds, award yourself -100 points.

The winner will be chosen 1 week from the first answer, and a new question related to this one, will be asked. Obviously those with the best code here will have a head start on the new one!

EDIT: forgot to make note that as in golf, the lowest score wins.

# Answer
# K, 196 215 240 (40 points)

When reduced to a single line it's 240 chars but I've added newlines here for readability. The question doesn't state exactly what the output needs to look like so I've come up with something fairly minimal.

```
r:0#t:#[c:#w:_0:0;"?"]
a:_:'0:`a;
l:8;
while[~(l=0)|(c=0);
  q:{x@&~x in y}[>#:'=,/a:a@&a like\:t;r];
  if[1=#a;-1 a;j:-1"WIN";exit 0];
  -1"Guess ",u:*q;
  r,:u;
  $[|/u=w;[c-:+/u=w;@[`t;&u=w;:;u]];-1($l-:1)," lives remaining"];
  -1 t;
  $[0=l;-1"LOSE";0=c;j;]]

```

The wordlist is a file called a in same directory as the code.

```
$ q hm.k -q
engineer
Guess e
e????ee?
Guess s
7 lives remaining
e????ee?
Guess i
e??i?ee?
engineer
WIN

```

EDIT: It now reanalyses the word on each step and determines which is the most likely letter based on previous guesses.

EDIT2: If there is only one possible answer (after reanalysis) the computer wins, rather than continuing to guess each individual letter
> 4 votes

# Answer
## Haskell, 781 - 100n

Takes the dictionary file name as command line argument. Notices when you try to cheat.

words tested and able to beat this on my 90k English word dictionary: 'zappa' and quite a few words of form '.u..y', such as putty

It used to have nice prompts and more descriptive output but I ended up golfing those away. It sanitizes dictionary file, filtering out words including non-alphabets and making it all lower case. Removing that would save me 48 bytes, but it's functionality I don't like to remove.

I believe this is fast enough for the -100, but I haven't tested it with anything bigger than that 90k words.

Also my first haskell program that really does something in IO. All comments welcome.

```
import System.Environment
import Data.List
import Data.Char
import Data.Ord
import qualified Data.Set as S
import Control.Monad
a=['a'..'z']
r=putStrLn
z=show
k=length
fb False=0
fb True=1
lp l=map fst.filter((==l).snd).zip[1..]
gu m@(g,p,t)l=fmap(\e->
 (l:g,S.filter((==e).lp l)p,t-(fb$null e)))$fmap(lp l)(putStrLn[l]>>getLine)
y m@(g,p,t)=case((S.size)p,t)of{(_,0)->r"I lost :<";(1,_)->r$'=':S.toList p!!0;
(0,_)->r"Cheater >:|";_->r(z t++" turns left.")>>
(gu m$fst.last.sortBy(comparing snd).filter(not.flip elem g.fst).zip a$
S.fold(zipWith(+).(\x->[fb$k`elem`x|k<-a]).nub.sort)(repeat 0)p)>>=y}
cg p=fmap(\h->([],S.filter((==(read h)).k)p,8))(r"Word length?">>getLine)
pd n=fmap(S.fromList.filter(all isAlpha).words.map toLower)(readFile n)
main=getArgs>>=pd.(!!0)>>=cg>>=y

```

**Edit, 868 -\> 830**

Re-thought the input so I was able to golf away the unsafeIO which required not only a long function call but also an import. Took away the stupid prompt nobody has (for this reason I also updated my example run). Made one or two lambdas point-free, the only one remaining is the `(\x->[fb$k`elem`x|k<-a])` which gets longer if made point free.

**Edit, 830 -\> 781**

Huge thanks to leftaroundbout here. Removed some unnecessary `do`s, changed some `return`s to `fmap`s and unpacked tuples at binding. I guess I still didn't understand all his advice, but this already got me a long way forward. Unfortunately I had to include one space for indentation to keep my lines under 80 chars, since now I don't have those `do` blocks with `;`s delimiting expressions.

Run with *hangover*

```
% ./reversehangman /usr/share/dict/british
Word length?
8
8 turns left.
e
______e_
8 turns left.
s
______e_
7 turns left.
d
______e_
6 turns left.
r
______er
6 turns left.
i
______er
5 turns left.
a
_a____er
5 turns left.
n
_an___er
5 turns left.
o
_an_o_er
5 turns left.
w
_an_o_er
=hangover

```
> 3 votes

# Answer
## Python (~~386 352 328 294~~ 300 chars, 100 points)

This was fun to do. Produces an error to stop the program. When inputting please give your word in uppercase.

Put the Ispells word list in a file called "a", no file extensions.

```
import re
a=input()
l=8
b=open('a').read().upper()
c=0
L=map(chr,range(65,91))
while 1:
 E=max((b.count(i),i)for i in L)[1];L.remove(E);print E,'\n',l,"lives remaining";d=c;c=raw_input();l-=d==c;b=''.join(re.findall(c.replace('_','[%s]'%sum(L)),b))
 if len(b)==a:print"WIN",b;Z
 if l==0:print"LOSE";Z

```
> 3 votes

# Answer
## PHP - ~~367 431 402 367 321~~ 312 bytes (-100 for flow, -100 for quick turns, 112 total)

Requires PHP 5.4 (short array syntax) and short open tags (saves 3 bytes!) which is on by default with PHP 5.4.

It takes the number of letters in the word as a command line argument.

Example command line `php -d short_open_tag=1 golf.php 8`

Submitted solution - 312 bytes on disk - there are some deliberate hard newlines in here for pretty output formatting.

```
<?foreach(file('l',2)as$w)$L[]=strlen($w)^$argv[1]?'':$w;for($l=8,$i=[];$l;){$s=$i+count_chars(join($L));arsort($s);$i[$g=key($s)]=0;$h=chr($g);echo"$h
";$r=count_chars($u=trim(fgets(STDIN)));$r[46]||die('WIN');$L=preg_replace($r[$g]||$l--<0?"/^((?!$u).)*$/i":"/.*$h.*/i",'',$L);echo"$l lives remaining
";}?>LOSE

```

Before fat-trimming, with some comments to explain what's going on

```
foreach(file('l',2)as$w) // Words from file called
    $L[]=strlen($w)^$argv[1]?'':$w; // Only words matching wordlen
for($l=8,$i=[];$l;){ // Loop, init lives + used guesses
    $s=$i+count_chars(join($L)); // Character frequency without guesses
    arsort($s); // Most frequent first
    $i[$g=key($s)]=0; // Guess is first item
    $h=chr($g); // Printable output
    echo"$h
"; // Literal newline saves us a byte
    $r=count_chars($u=trim(fgets(STDIN))); // User response
    $r[46]||die('WIN'); // short circuit win, and magic regex below
    $L=preg_replace($r[$g]||$l--<0 ? "/^((?!$u).)*$/i" : "/.*$h.*/i", '', $L);
    echo"$l lives remaining
";
} // End parsing because it's shorter than echoing
?>LOSE

```

Output with "engineer" - Spaces are not allowed, I'm using full stops instead of underscores due to uh... magic.

The program actually knows the word after 3 guesses, but continues 1 guess at a time anyway to save space.

```
e
e....ee.
8 lives remaining
s
e....ee.
7 lives remaining
n
en..nee.
7 lives remaining
i
en.inee.
7 lives remaining
g
enginee.
7 lives remaining
r
engineer
WIN

```

Variation using the same logic as beary605 - 269 bytes, -200 = 69 points.

```
<?$L=file('l',2);for($l=8,$i=[];$l;){$s=$i+count_chars(strtolower(join($L)));arsort($s);$i[$g=key($s)]=0;$h=chr($g);echo"$h
";$r=count_chars($u=trim(fgets(STDIN)));$r[46]||die('WIN');$r[$g]?$L=preg_replace("/^((?!$u).)*$/i",'',$L):$l--;echo"$l lives remaining
";}?>LOSE

```

There's some unaddressed comments about how strictly the output/user prompts needs to be, obviously I have taken liberties here as have other solutions.

**Edits**

> **Edit 1**
> Fatal logic error. I wasn't re-analysing correctly when the computer guessed correctly. This got me solving engineer with 5 lives remaining instead of 2, although at the expense of 64 bytes. I can probably improve this later.
> **Edit 2**
> Drastically improved matching by switching to a regex based filter. Also means I have to use full stops instead of underscores because the user input is essentially feeding regex patterns into the program.
> **Edit 3**
> Remembered to short-circuit evaluation to remove if statements, and use ternary operator to reduce 2 regex statements to 1.
> **Edit 4**
> Removed some verbosity with user prompting. Taking initial input on the command line. Removed an unnecessary staging variable. Removed case sensitivity.
> **Edit 5**
> Sacrificed efficiency for size, xoring word length with user supplied letter count to indicate inclusion. join is an alias of implode. Moved variable initialisation from outside the while loop to inside a for loop initiator saves me a byte!
> 2 votes

---
Tags: code-golf, word-puzzle, word
---


# Question
Title: Generating combinations without recursion
Given a list of strings and a length, give all combinations of that list with the given length. The problem is: **your code must not be recursive.** Yes, it can be done. I have done it myself, when I had no clue what this "recursion" was.

**Input:** A list of strings of an undefined length, and an integer defining the length of the combination. The strings will be at least one character long, and will only contain letters or numbers. The way of input will be specified by you, the programmer.

**Output:** A list of possible combinations as strings, not necessarily distinct (although you can make it that way, if you like). You do not have to sort the list.

**Test Cases:** As said before, the method of input will be specified by you.
`[a,b] 3 -> Nothing`
`[1,0,0] 2 -> 10 10 00`, or `00 10` if distinct.
`[abc,bcd,cde] 2 -> abcbcd abccde bcdcde`

If you even manage to do this, I will commend you. As always, shortest code wins. Good luck.

# Answer
## GolfScript (44 42 32 chars)

```
n%){\,=}+[[]]@1/{`{1$+}+%}%;\,n*

```

This takes input on stdin as a list of newline-separated strings followed by a line containing the desired subset size. It assumes that none of the input strings is empty. It takes some inspiration from Howard's solution, and can be shortened by two chars if using his input format:

```
~{\,=}+[[]]@1/{`{1$+}+%}%;\,n*

```

Output is a newline separated list of concatenations.

E.g.

```
$ golfscript.rb subcombo.gs <<END
> a
> b
> c
> 2
> END
ab
ac
bc

```

Note: this uses a horribly inefficient algorithm. A much nicer implementation in terms of performance is (62 61 chars)

```
n%)~\:S;2\?({2S,?<}{:s.~)&.s+.s^@4*/|}/{:x;S{;x.2/:x;1&},}%n*

```

which uses Gosper's hack.
> 5 votes

# Answer
### GolfScript, 33 35 34 characters

```
~[[]]@{\{.[2$]+.,4$={puts}*}%\}%];

```

Assumes that the input is list of strings and number in GolfScript compatible format (on STDIN). Example:

```
> ["abc" "bcd" "cde"] 2
abcbcd
bcdcde
abccde

```

You can also test this version online.

*Edit:* The first version was broken.
> 4 votes

# Answer
## Mathematica, 21

```
""<>##&@@@Subsets@##&

```

Usage:

```
""<>##&@@@Subsets@##&[{"a", "b", "c", "d"}, {3}]

```

> {"abc", "abd", "acd", "bcd"}
> 4 votes

# Answer
## Mathematica, 34 30 24 characters

```
StringJoin@@@Subsets@@#&

```

where i is input consisting of a list of the strings and the length of combinations. For example,

```
k = {{"abc", "bcd", "cde"},{2}};
StringJoin@@@Subsets@@#&[k]

(* out *)
{"abcbcd", "abccde", "bcdcde"}

```

---

Additional examples:

```
d = {"a", "b", "cd", "e", "fgh"}
m = {d, {2}}
n = {d, {3}}
p = {d, {4}}

StringJoin@@@Subsets@@#&[m]
StringJoin@@@Subsets@@#&[n]
StringJoin@@@Subsets@@#&[p]
(* out *)
{"ab", "acd", "ae", "afgh", "bcd", "be", "bfgh", "cde", "cdfgh", "efgh"}
{"abcd", "abe", "abfgh", "acde", "acdfgh", "aefgh", "bcde", "bcdfgh", "befgh", "cdefgh"}
{"abcde", "abcdfgh", "abefgh", "acdefgh", "bcdefgh"}

```
> 3 votes

# Answer
## J, 50 48 46 44 43 41 35 characters

```
;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1

```

Takes input from the keyboard. I've changed the input format from previous answers. Strings should come first, single-quoted, and separated by semi-colons, followed by the integer.

```
   ;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1
'hello';'mr';'wibble';2
hellomr
hellowibble
mrhello
mrwibble
wibblehello
wibblemr

```

Entering a number larger than the largest possible combination just gives the largest possible combination:

```
   ;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1
hello mr wibble 8
hellomrwibble
hellowibblemr
mrhellowibble
mrwibblehello
wibblehellomr
wibblemrhello

```
> 1 votes

# Answer
### Scala 52

Not a challenge - know your API:

```
def c(l:Seq[_],n:Int)=l combinations n mkString "\n"

```

invocation sample:

```
scala> c(Seq("foo", "bar", "foobar"), 2)
res199: String =
List(foo, bar)
List(foo, foobar)
List(bar, foobar)

```

Now beary605 observes that he didn't thought about library methods *combinations*, so I come up with this one, which doesn't use *combinations*, but maybe he now will come up with a permutation prohibition.

### Scala 63 (without literal combinations method):

```
def c(l:Seq[_],n:Int)=l.permutations.map(_.take(2).toSet).toSet

```
> 1 votes

# Answer
# Java, 208 characters

**No imports, two method calls**, so it should be pretty guaranteed that there are no *implisit* recursive calls neither.

```
class S{public static void main(String[]a){int n=a.length-1,k=Integer.parseInt(a[0]),i=0,j;while(++i<1<<n)if(Integer.bitCount(i)==k){String s="";for(j=0;j<n;)if((i&1<<j++)!=0)s+=a[j];System.out.println(s);}}}

```

Slightly more readable:

```
class S{
    public static void main(String[]a){
        int n=a.length-1,k=Integer.parseInt(a[0]),i=0,j;
        while(++i<1<<n)
            if(Integer.bitCount(i)==k){
                String s="";
                for(j=0;j<n;)
                    if((i&1<<j++)!=0)
                        s+=a[j];
                System.out.println(s);
            }
    }
}

```

Takes input from command line arguments. First arg is the length and the rest is the strings. Outputs each combination on a separate line:

```
$ java S 3 A B C D
ABC
ABD
ACD
BCD

```
> 1 votes

---
Tags: code-golf, combinatorics
---


title: Random with your hands tied

text:
# Question
Title: Random with your hands tied
### Task

Develop some code to generate a psuedo-random number between X and Y (taken as input). Explain why or how it works.

### Conditions

* Do not use any random generating seeds, pre-written randoms, or external source to generate the random number.
* Make something as close to random as you can get. No hard coding of values.

Whoever gets the most upvotes for a new, innovative, out of the box, idea, wins.

# Answer
## C

not sure if the `volatile` keyword is needed (or what other OS dependencies are assumed here)

simply takes the address of a variable, and maps it to \[min, max\]:

```
int rand(int min, int max)
{
  volatile int order = max - min + 1;
  return min + (int)&order % order;
}

```
> 4 votes

# Answer
# Perl

First, here is a solution that was golfed, coming in at 30 characters:

```
$a=<>;$b=<>;print$$%($b-$a)+$a

```

This solution uses the process number of the program as the random seed, similar to using the location of the variables as a seed. It works the best when the min and max are small compared to the process number.

Here is a version that uses command line arguments, with 36 chars:

```
 print$$%($ARGV[1]-$ARGV[0])+$ARGV[0]

```

And here is a version as a subroutine that returns the random value (without printing to screen), with 29 chars:

```
 sub a{$$%($_[1]-$_[0])+$_[0]}

```

Second, I am working on a solution that adheres to the strictest reading of the spec, which is that the program cannot be influenced by anything except the two arguments.
> 1 votes

# Answer
# Mathematica

**Rationale**

Pi is an irrational number. It decimal representation does not repeat.

I strongly suspect that it does not "favor" any of the base ten digits, 0...9, nor any numbers of length when one partitions the decimal into strings of d digits. This suspicion can later be informally checked using the code below.

**Code**

The following will select integers between the integers x and y, where x is less than y.
y need not have the same number digits as x. The routine will begin at the cth digit of Pi. At the end of the procedure, the counter will be at c + n.

```
ClearAll[f]
f[x_,y_,c_,n_]:=
  Module[{diff=y-x,d},
  d=Length[IntegerDigits[diff]];
  Cases[FromDigits/@Most[IntegerDigits[Round[N[Pi,c+n+1]10^(c+n-1)]]][[c;;c+n1]]~Partition~d,
  i_/; i>x-1 && i<y+1]]

```

Suppose we want to generate a large (\> 3000000), pseudo-random list of integers between 7 and 78. Here is how to request it. I've estimated that we'll need to use about 10^7 digits of Pi. We'll begin from position 1, that is, c=1.

```
(results= f[7,78,1, 10^7])//Timing

```

Note how the unsorted and untallied results maintain the order of Pi's digits: 314159... Note also that the result took just under 20 seconds. As we move further along, we'll encounter practical limits to how much we can process in a reasonable amount of time. But since this is merely an exercise in thinking out of the box, we'll ignore this limitation as we proceed.

**Examining the results**

When we tally and plot the results we see that Pi does not particularly favor any numbers in this range:

```
SortBy[Tally[results],First]

```

Notice that the integers between 7 and 78 were chosen more or less with equanimity. Further tests would show this holds up.

```
ListPlot[%]

```

Similar checks should show whether or not Pi plays favorites with any numbers at all, regardless of how many digits it holds. \[I checked for 1, 2, and 3 digit numbers over tens of millions of draws and found no bias starting from the beginning of Pi. A rigorous check would require more systematic examination or theoretical insights.\]
> 1 votes

# Answer
## Python

```
import sha
R=lambda x,y:x+int(sha.new('%d_%d'%(x,y)).hexdigest(),16)%(y-x)

```
> 0 votes

# Answer
# JavaScript

```
function getRandom(x,y) {
    s=document.createElement("SCRIPT");
    s.src="http://search.twitter.com/search.json?q=%22random%22&&callback=t"
    document.getElementsByTagName("HEAD")[0].appendChild(s);
    var c = 0;
    window.t=function (d) {
        g=d.results;
        for(z=0; z<g.length; z++) {
            c+=g[z].id/0xfff;
        }
        console.log(x+c%(y-x))
    };
}

```

This is pretty disgusting really. Queries Twitter, via the JASONP API, for recent tweets containing the word "random", then it uses the ID's of each of the returned tweets to calculate the "random" number.

You might want to wait a few seconds in between each call of the function, also it doesn't return a value, it just outputs one to the console. (Told you it was disgusting).

You can try it here.
> 0 votes

# Answer
## Python 2.x, 454

```
z=lambda n,b:int("0b"+(bin(n)[2:][:-b]or'0'),2)
r=range
g=624
def m(s,t):
 a=[s]
 for i in r(1,g): a+=[1812433253*((a[i-1]^(a[i-1]>>30))+i)]
 for i in r(t):
    i%=g
    if not i:
        q=0
        for c,d in zip(a,a[1:]+[a[0]]):
            u=(z(c,1)+z(d%g,31))
            a[q]=a[(q+397)%g]^(u>>1)
            if u%2:a[q]^=2567483615
            q+=1
    y=a[i]^(a[i]>>11)
    y^=(y<<7&2636928640)
    y^=(y<<15&4022730752)
    y^=(y>>18)
    yield y

```

Mersenne twister algorithm. It can probably be golfed some more.

Usage:

```
>>> list(m(s, t))

```

Where `s` is the seed, and `t` is the number of numbers to generate.
> 0 votes

# Answer
# Python, 32

Similar to ardnew's answer:

```
a,b=input()
print a+id(1)%(b-a)

```
> 0 votes

---
Tags: popularity-contest
---


title: Self-matching regex

text:
# Question
Title: Self-matching regex
**Write a non-trivial regex that matches itself.**

For example, `#.*$` will match a comment outside of a string in python until the end-of-line, and also matches itself in perl regex syntax.

**Rules**:

* The regular expression must do something useful or practical.
* Tell what regex syntax you are using (e.g. perl or POSIX).
* Winner is the highest voted compliant answer.
* Be creative!

# Answer
> 17 votes
```
/(^|[^/])\/(?!\/)(\[.+?]|\\.|[^/\r\n])+\/[gim]{0,3}(?=\s*($|[\r\n,.;})]))/g

```

Stolen from https://github.com/LeaVerou/prism/blob/gh-pages/components/prism-javascript.js. This should match (in JavaScript) all JavaScript regular expressions.

# Answer
> 11 votes
## PYTHON

Below is a self-matching regex generator. You provide two lists, one contains training data that the regex should match (in addition to matching itself), the other contains training data the the regex should *NOT* match:

```
from random import choice, randrange
import re
from itertools import zip_longest, chain, islice
from operator import itemgetter

CHAR_SET = [chr(i) for i in range(128)] + [r"\\", r"\d", r"\D",
                                           r"\w", r"\W", r"\s",
                                           r"\S", r"?:", r"\1",
                                           r"\2", r"\A", r"\b",
                                           r"\B", r"\Z", r"\.",
                                           r"\[", r"\]", r"\(",
                                           r"\)", r"\{", r"\}",
                                           r"\+", r"\|", r"\?",
                                           r"\*"]

CHAR_SAMPLE = []
BREAKPOINT = re.compile(
    r"""
    \(.*?\)|
    \[.*?\]|
    \{.*?\}|
    \w+(?=[\(\[\{])?|
    \S+?|
    \.\*\??|
    \.\+\??|
    \.\?\??|
    \\.|
    .*?
    """,
    re.VERBOSE)

MATCH_BRACKETS = {'(': ')', '[': ']', '{': '}'}
CLOSE_BRACKETS = {')', ']', '}'}
REGEX_SEEDER = [
    r".*?",
    r"(?:.*?)",
    r"\w|\s",
    r"(?<.*?)",
    r"(?=.*?)",
    r"(?!.*?)",
    r"(?<=.*?)",
    r"(?<!.*?)",
    ]

LEN_LIMIT = 100

def distribute(distribution):
    global CHAR_SAMPLE
    for item in CHAR_SET:
        if item in distribution:
            CHAR_SAMPLE.extend([item] * distribution[item])
        else:
            CHAR_SAMPLE.append(item)

def rand_index(seq, stop=None):
    if stop is None:
        stop = len(seq)
    try:
        return randrange(0, stop)
    except ValueError:
        return 0

def rand_slice(seq):
    try:
        start = randrange(0, len(seq))
        stop = randrange(start, len(seq))
        return slice(start, stop)
    except ValueError:
        return slice(0,  0)

#Mutation Functions

def replace(seq):
    seq[rand_index(seq)] = choice(CHAR_SAMPLE)

def delete(seq):
    del seq[rand_index(seq)]

def insert(seq):
    seq.insert(rand_index(seq, len(seq) + 1), choice(CHAR_SAMPLE))

def duplicate(seq):
    source = rand_slice(seq)
    seq[source.stop: source.stop] = seq[source]

def swap(seq):
    if len(seq) < 2: return
    a = rand_index(seq, len(seq) - 1)
    seq[a], seq[a + 1] = seq[a + 1], seq[a]

dummy = lambda seq: None

MUTATE = (
    replace,
    delete,
    insert,
    duplicate,
    swap,
    dummy,
    dummy,
    )

def repair_brackets(seq):
    """Attempts to lower the percentage of invalid regexes by
    matching orphaned brackets"""

    p_stack, new_seq = [], []
    for item in seq:
        if item in MATCH_BRACKETS:
            p_stack.append(item)
        elif item in CLOSE_BRACKETS:
            while p_stack and MATCH_BRACKETS[p_stack[-1]] != item:
                new_seq.append(MATCH_BRACKETS[p_stack[-1]])
                p_stack.pop()
            if not p_stack:
                continue
            else:
                p_stack.pop()
        new_seq.append(item)
    while p_stack:
        new_seq.append(MATCH_BRACKETS[p_stack.pop()])
    return new_seq

def compress(seq):
    new_seq = [seq[0]]
    last_match = seq[0]
    repeat = 1
    for item in islice(seq, 1, len(seq)):
        if item == last_match:
            repeat += 1
        else:
            if repeat > 1:
                new_seq.extend(list("{{{0}}}".format(repeat)))
            new_seq.append(item)
            last_match = item
            repeat = 1
    else:
        if repeat > 1:
            new_seq.extend(list("{{{0}}}".format(repeat)))
    return new_seq

def mutate(seq):
    """Random in-place mutation of sequence"""
    if len(seq) > LEN_LIMIT:
        seq[:] = seq[:LEN_LIMIT]
    c = choice(MUTATE)
    c(seq)

def crossover(seqA, seqB):
    """Recombination of two sequences at optimal breakpoints
    along each regex strand"""

    bpA = [item.start() for item in BREAKPOINT.finditer(''.join(seqA))]
    bpB = [item.start() for item in BREAKPOINT.finditer(''.join(seqA))]
    slObjA = (slice(*item) for item in zip(bpA, bpA[1:]))
    slObjB = (slice(*item) for item in zip(bpB, bpB[1:]))
    slices = zip_longest(
        (seqA[item] for item in slObjA),
        (seqB[item] for item in slObjB),
        fillvalue=[]
        )
    recombinant = (choice(item) for item in slices)
    return list(chain.from_iterable(recombinant))

#Fitness testing

def match_percentage(match):
    """Calculates the percentage a text actually matched
    by a regular expression"""

    if match and match.endpos:
        return (match.end() - match.start()) / match.endpos
    else:
        return 0.001

def fitness_test(seq, pos_matches, neg_matches):
    """Scoring algorithm to determine regex fitness"""

    try:
        self_str = ''.join(seq)
        regex = re.compile(self_str)
    except (re.error, IndexError):
        seq[:] = repair_brackets(seq)
        try:
            self_str = ''.join(seq)
            regex = re.compile(self_str)
        except (re.error, IndexError):
            return 0.001

    pos_score = sum(match_percentage(regex.search(item))
                    for item in pos_matches) / len(pos_matches) / 3

    neg_score = (1 - sum(match_percentage(regex.search(item))
                    for item in neg_matches) / len(neg_matches)) / 3

    self_score = match_percentage(regex.search(self_str)) / 3

    return pos_score + self_score + neg_score

#Population Management

def generate_pop(pos_matches, neg_matches, pop_size):
    sources = (pos_matches, REGEX_SEEDER)
    return [crossover(
        choice(choice(sources)), choice(choice(sources))
        ) for i in range(pop_size)]

def glean_pop(population, cutoff, fit_test, ft_args=()):
    scores = (fit_test(bug, *ft_args) for bug in population)
    ranked = sorted(zip(population, scores), key=itemgetter(1), reverse=True)
    maxItem = ranked[0]
    new_pop = next(zip(*ranked))[:cutoff]
    return maxItem, new_pop

def repopulate(population, pop_size):
    cutoff = len(population)
    for i in range(pop_size // cutoff):
        population.extend([crossover(choice(population), choice(population))
                           for i in range(cutoff)])
    population.extend([population[i][:] for i in range(pop_size - len(population))])

#Simulator
def simulate(pos_matches, neg_matches, pop_size=50, cutoff=10, threshold=1.0):
    population = generate_pop(pos_matches, neg_matches, pop_size)
    while True:
        for bug in population:
            mutate(bug)

        #Scoring step
        max_item, population = glean_pop(
            population,
            cutoff,
            fitness_test,
            (pos_matches, neg_matches)
            )

        #Exit condition:
        max_regex, max_score = max_item
        if max_score >= threshold:
            return max_score, max_regex
        """
        print(max_score, ''.join(max_regex))
        input("next?")"""

        #Repopulation Step:
        population = list(population)
        repopulate(population, pop_size)

```

# Answer
> 6 votes
JavaScript regular expression that matches stuff like it.

```
/^\/\^\\\/\\\^[\\\[\]\/\^\${},\dd]{34}$/

```

You can test it like so:

```
(function test() {
    var re =/^\/\^\\\/\\\^[\\\[\]\/\^\${},\dd]{34}$/;
    var m  =/=([^;]+)/.exec(test)[1];
    return re.exec(m);
})();

```

---
Tags: popularity-contest, regular-expression
---


title: Return the first N primes

text:
# Question
Title: Return the first N primes
With a twist; your algorithm has to be less complex than O(X2) where X is the Nth prime. Your solution post should include the character count and the theoretical complexity in terms of X (or N, which ~= X/ln(X) and so will usually be more efficient)

Here's a hint solution in C# (O(Xln(sqrt(X))), 137 chars):

> `public List<int> P(int n){var r = new List<int>{2}; int i=3; while(r.Count<n) if(!r.TakeWhile(x=>x<Math.Sqrt(i)).Any(x=>i%x==0)) r.Add(i++); else i++; }`

# Answer
> 8 votes
## J, 4 characters

```
p:i.

```

Usage:

```
   p:i.10
2 3 5 7 11 13 17 19 23 29

```

The problem with using J here is that I don't really know how efficient it is. I'd assume that as a language specialising in "mathematical, statistical, and logical analysis of data", that the algorithm used to generate the primes is pretty good.

I did look at the C source for clues, but it turns out that the C source for J is almost as unreadable as J itself. :-)

(The file is called v2.c for anyone who wants to have a look)

# Answer
> 1 votes
## C, 98 characters

The good old sieve method.
We assume the first N primes are among the first N\*24 integers. this works up to 2^32, because ln(2^32)\<24. A general solution would need to estimate prime density, but since I use 32bit integers, I saw no need to generalize.
Complexity analysis (which I may do later) should use a formula instead of the constant 24.

```
i,j,m,*p;
f(n){
    p=calloc(m=n*24,4);
    for(i=2;n;i++)
        if(!p[i])for(n--,printf("%d\n",j=i);p[j+=i]=j<m;);
}

```

# Answer
> 1 votes
## Haskell, ~~47~~ 46

Since the problem definition demands less than `O(X^2)` complexity, where `X ~= N*log(N)`, the following solution is acceptable. Its theoretical complexity is below `O(X^2)`, testing each number below `X` by all its preceding numbers until a divisor is found. For primes only, having `~ X/log(X)` primes overall, the complexity is thus `O(X^2/log(X))`. Most of the composites are multiples of small primes so are only divided few times, so they don't count.

```
p n=take n[n|n<-[2..],all((>0).rem n)[2..n-1]]

Prelude> last $ p 500
3571    (1.60 secs)
Prelude> last $ p 700
5279    (3.31 secs)
Prelude> logBase (5279/3571) (3.31/1.60)  -- in X
1.8597116027280054
Prelude> logBase (7/5) (3.31/1.60)        -- in N
2.1604889825177507

Prelude> last $ p 900
6997    (5.69 secs)
Prelude> logBase (6997/5279) (5.69/3.31)
1.9228821930296973                        -- in X
Prelude> logBase (9/7) (5.69/3.31)
2.155714108637307                         -- in N

```

If the complexity constraint in the problem definition will be amended to below `O(N^1.5)` (as I believe it should) then this solution will not be acceptable. That is why I post it in addition to another Haskell solution which is indeed better than `O(N^1.5)`.

# Answer
> 0 votes
## scala 191

Not the shortest one...

```
object P extends App{
def c(M:Int)={
val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
for(i<-List.range(3,M)
if(p(i))){
var j=2*i;
while(j<M){
if(p(j))p(j)=false
j+=i}
}
(1 to M).filter(x=>p(x))
}
println(c(args(0).toInt))
}

```

Just measuring the method c, like the others do.

But how to prove, that it fulfills the Big-O requierement?

Well, I feed it with numbers, each twice as big as the number before. If it was of O(x²) complexity, it should need about 4 times as long, shouldn't it?

So I just measure it:

```
for p in {10..22}
do
  /usr/bin/time scala P $((2**p))> /dev/null
  echo "N="$((2**p))
done 2>&1 | tee primes.log

```

and then it's just a grep:

```
egrep -o "(^.*user|N=.*|#)" primes.log | tr "\n" "\t" | tr "#" "\n"
0.57user    N=1024
0.54user    N=2048
0.56user    N=4096
0.59user    N=8192
0.62user    N=16384
0.66user    N=32768
0.70user    N=65536
0.77user    N=131072
0.99user    N=262144
1.48user    N=524288
2.59user    N=1048576
5.68user    N=2097152
10.79user   N=4194304

```

So in the beginning there is only a startup overhead of about .55s - later it is a linear growth. For N'=2\*N, t(N') ≈ 2\*t(N).

# Answer
> 0 votes
## Perl: 249 chars

The sieve certainly would have been shorter, but here is an implementation of the Miller-Rabin test:

```
sub p{
  $n=shift;
  $m=$n-1;
  return$n==2||$n==3if$n<=3or!($n&1);
  $s=unpack"%32b*",pack"L",($m&-$m)-1;
  for(1..5){
    next if($x=(int(rand($n-3))+2)**($n>>$s)%$n)==1||$x==$m;
    map{($x=$x**2%$n)==1&&last;$x==$m&&next}(1..$s-1);
  0}
1}
p($_)&&print"$_\n"for(1..$ARGV[0]);

```

Wikipedia says the runtime is O((log(X))^3)

# Answer
> 0 votes
# Ruby (91)

Almost same as the example, so should have similar complexity. Unless I'm still missing something obvious (almost used `select` instead of `take_while` to save a few chars)

```
q=->n{k=[2];p=3;while k.size<n;k<<p if !k.take_while{|x|x*x<=p}.any?{|x|p%x<1};p+=2;end;k}

```

and with some whitespace:

```
q=->n{
  k=[2];
  p=3;
  while k.size<n;
    k<<p if !k.take_while{|x| x*x <= p }.any?{|x| p%x < 1};
    p+=2;
  end;
  k
}

```

# Answer
> -1 votes
# Ruby 37

```
require 'prime'
p Prime.take gets.to_i

```

---
Tags: code-golf, primes, restricted-complexity
---


# Question
Title: Output a Dance Dance Revolution arrow chart
If you're not familiar, Dance Dance Revolution is a rhythm game where you hit four receptors (left, down, up, right) with your feet as arrows scroll up the screen. One of the file formats used to lay out the arrow patterns looks something like this:

```
1000
0100
0000
0011
,

```

A `1` represents a tap note. This chart has a left tap, a down tap, an empty line, and an up-right jump, respectively. The comma at the end indicates the end of a measure, and there can be any number of measures in a song.

Now here's an example of a more complicated chart:

```
1000
0010
0100
0001
0010
0100
2000
0000
,
0010
0001
3100
1001
,

```

The first measure has eight lines, so each line represents an eighth note, but the second measure only has four lines, all of which are quarter notes. All measures are the same duration; measures containing more lines are simply denser. You can assume that all measures will have lengths that are powers of two greater than or equal to 4. So measures can have 4 lines, 8 lines, 16 lines, and so on.

A `2` indicates the start of a hold arrow and a `3` represents its end. You can assume that each `2` will have a corresponding `3` in the same column, without anything between them other than zeroes and/or measure boundaries.

**Your task is to print the stepchart in a more human-readable format.** It's probably best if I just give you an example. Here's the expected output for the chart given above:

```
<
  ^
 v
   >
  ^
 v
<
|
| ^
|
|  >
|
|v

<  >

```

*(If this is confusing to you, perhaps looking at this will help.)*

Left, down, up, and right taps are indicated by `<`, `v`, `^`, and `>`, respectively. Hold arrows are indicated by pipes that trail beneath the starting taps.

Additionally, the chart needs to be stretched so that each measure is the same length: in the above example, the measures have lengths of 8 and 4, so the output shows all measures as if they contained eighths. If you have a chart where all measures are 4 lines long except for one that's 64 lines, the output needs to render all measures as 64 lines long!

**I/O:** Assume the chart exists in a file whose name is given as the first argument to the program (e.g. `python arrows.py input.txt`). Write to standard output. If (and only if) your language of choice doesn't have filesystem access for whatever reason, it's acceptable to load it as a string at the beginning of the program.

**Goal:** The program with the fewest characters will be accepted a week from now, the 17th of August, around 8:00 EST.

# Answer
> 5 votes
## GolfScript ~~132~~ 129

```
','/{n/{},}%{},.{,}%.$):§;;{§\/(}%]zip{~:¥;{['0'4*]¥*~}%}%{+}*zip 1:¤;{0:^;{.^2=5@48=!¤*if\48-^or:^;' <v^>|'=}%¤):¤;}%zip{+}*4/n*

```

Online demo here

# Answer
> 4 votes
## C, 364, 331, 310, 293

```
#define L(A)for(p=b+9;*p;)if(*p-44){A;t++;p+=5;}else{m=t>m?t:m;p[4-5*t]=t;t=0;p+=2;}
c,j,t,m,x;char b[9999],*p;main(int i,char*v[]){read(open(v[1],0),b+9,9999);L()L(x=t?x:m/p[4];for(j=x*4;j-->0;){i=j%4;b[i]=" |"[b[i+5]];c=p[i]&3;p[i]=0;if(c&&c<3)b[i]="<v^>"[i];if(c>1)b[i+5]=3-c;i?:puts(b);})}

```

Limits:

* max input file size of 9990 chars
* max measure of 128

Run:

```
./a.out test.dance

```

output:

```
<
  ^
 v
   >
  ^
 v
<
|
| ^
|
|  >
|
|v

<  >

```

Ungolfed commented version:

```
#define L(A)\
  for(p=b+9;*p;)/* loop through file */\
    if(*p-44){     /* line */\
          A;\
          t++;\
          p+=5;       /* 4 steps+linefeed */\
    }else{         /* comma line */\
          m=t>m?t:m;  /* max measure */\
          p[4-5*t]=t; /* store measure in '\n' char of first line */\
          t=0;\
          p+=2;       /* comma+linefeed */\
    }

c,j,t,m,x;char b[9999],*p; // b[0..4] output, b[5..8]=hold, b[9..9999]=file
main(int i,char*v[]){
    read(open(v[1],0),b+9,9999);
    // pass 1 - determine max measure
    L()
    // pass 2 - process steps and output
    L(x=t?x:m/p[4]; // repeats per line (first line p[4] is measure)
      for(j=x*4;j-->0;){ // 4 steps per repeat
          i=j%4;         // the step
          b[i]=" |"[b[i+5]];
          c=p[i]&3;      // step type 0,1,2,3
          p[i]=0;        // reset step to 0 for future iterations
          if(c&&c<3)b[i]="<v^>"[i];
          if(c>1)b[i+5]=3-c; // set/reset hold
          i?:puts(b);    // every 4th step
      }
    )
}

```

# Answer
> 3 votes
# C - 466 460 438 bytes

```
#define C while(fgets(b,6,f))
p[9]={'>^v<',0,'||||',0,'    '},Y,M,T,R,E,*W,Q,i;char b[9];main(int n,char*v[]){int*f=fopen(v[1],"r");W=malloc(4e5);C if(*b!=44)++T;else{W[++Q-1]=T;Y=T>Y?T:Y;T=0;}fseek(f,0,0);Q=0;C{if(*b!=44){R=0;M=E;for(i=0;i<4;++i){R|=(b[i]>48&&b[i]<51)*255<<i*8;E|=b[i]==50?255<<i*8:0;E&=~(b[i]==51?255<<i*8:0);}p[6]=*p&R|(~R^M)&p[4]|(M&R^M)&p[2];puts(p+6);p[6]=p[4]&~E|p[2]&E;for(i=0;i<Y/W[Q]-1;++i)puts(p+6);}else++Q;}}

```

The output from this, using the given input file, is:

```
<
  ^
 v
   >
  ^
 v
<
|
| ^
|
|  >
|
|v

<  >

```

Should be fairly compliant to most compilers.

# Answer
> 3 votes
## PHP 274 chars

My first code golf. All comments are welcome.

```
<?php
    $i = '1000 0010 0100 0001 0010 0100 2000 0000 0010 0001 3100 1001 ,';
    $f=explode(' ', $i);$a=array("<","v","^",">");$t=-1;foreach($f as$n){if($n==',')return;else{$j=str_split($n);$o=0;foreach($j as$h){switch($h){case 2:$t=$o;case 1:$h=$a[$o];break;case 0:$h=" ";if($t>=0&&$t==$o){$h="|";}break;case 3:$t=4;$h="|";break;}echo$h;$o++;}echo"\n";}}
?>

```

Should I count the `<?php ?>` tags?

Thank you.

# Answer
> 2 votes
# Mathematica 283 chars

The following works with measures of `2^(2 n)` lines.

```
v = Import["a.xls"];
g@p_ := 2~Log~p; t = Transpose; l = Length; s = Sequence;
r_~h~o_ := t[Flatten[
    Riffle[#, x, {2, -1, 2}] /. x -> s @@ ConstantArray[{0, 0, 0, 0},
          2^(g@Max[l /@ v] - g@l@#) - 1] & /@ v, 1]][[r]]
    /. {a___, 2, b__, 3, c___} :>  {a, 2, s @@ Cases[{b}, 0 :> "|"], "|", c}
    /. {0 -> " "} /. {1 | 2 -> o};
t@{1~h~"<", 2~h~"v", 3~h~"^", 4~h~">"} // Grid

```

Data file, imported as `v`, is structured as follows:

```
{{{1,0,0,0},{0,0,1,0},{0,1,0,0},{0,0,0,1},{0,0,1,0},{0,1,0,0},{2,0,0,0},{0,0,0,0}},{{0,0,1,0},{0,0,0,1},{3,1,0,0},{1,0,0,1}}};

```

---
Tags: code-golf
---


# Question
Title: What is the minimum set of characters with which you can write any valid python program?
The proof of the set of characters is that there is a translator which takes any ascii python program as input and produces a limited character set version of the program. The limited character set program can be slower than the original program. It simply has to be possible to produce the same output as the valid python program.

For example, here is a translator that takes any ascii python program as input and writes out a version that doesn't use the character x:

```
import random
import string
with open('in.py') as infile:
    with open('out.py', 'w') as outfile:
        lines = infile.readlines()
        outfile.write("data = '")
        random_string = ''.join(random.choice(string.digits) for x in range(20))
        for line in lines:
            outfile.write(line.encode('string-escape').replace('x', random_string))
        outfile.write("'\n")
        outfile.write("exec data.replace('%s', chr(%s))" % (random_string, ord('x')))

```

note that this will fail if the program happens to have the random string in it already, but for the purposes of this question lets accept that 'any' can be slightly limited. We don't have to consider extremely low probabilities of failure due to random chance or a malicious input program.

# Answer
> 17 votes
I've come up with a 9-character translator using `exec` (also posted at this GitHub gist):

```
def convert_txt(txt):
    """Convert the text of a Python program to minimal Python"""
    s = "+".join(["chr(%s)" % "+".join(["1"] * ord(c))
                            for c in txt])
    return 'exec(%s)' % s

```

The only characters it needs are `()+1cehrx`.

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


title: Draw a tiled cube of any size

text:
# Question
Title: Draw a tiled cube of any size
Draw a tiled cube of any size, in ASCII art.

You will be given three numbers `a`, `b` and `c`, and the program should output an a\*b\*c sized cube.

**Examples**

`3 3 3` -\>

```
    ____ ____ ____
  /____/____/____/|
 /____/____/____/||
/____/____/____/|||
|____|____|____|||/
|____|____|____||/
|____|____|____|/

```

`5 2 3` -\>

```
    ____ ____ ____ ____ ____
  /____/____/____/____/____/|
 /____/____/____/____/____/||
/____/____/____/____/____/||/
|____|____|____|____|____||/
|____|____|____|____|____|/

```

`4 6 5` -\>

```
      ____ ____ ____ ____
    /____/____/____/____/|
   /____/____/____/____/||
  /____/____/____/____/|||
 /____/____/____/____/||||
/____/____/____/____/|||||
|____|____|____|____||||||
|____|____|____|____|||||/
|____|____|____|____||||/
|____|____|____|____|||/
|____|____|____|____||/
|____|____|____|____|/

```

Shortest code wins.

# Answer
## Python, 145 chars

```
a,b,c=map(int,raw_input().split())
for i in range(b+c+1):print(' '*(c-i)+((' /|'[(i>c)+(i>0)]+'_'*4)*(a+1))[:-4]+('|'*(b+c-i))[:b]+'/')[:5*a+c+1]

$ echo "5 6 3" | ./cube.py
    ____ ____ ____ ____ ____
  /____/____/____/____/____/|
 /____/____/____/____/____/||
/____/____/____/____/____/|||
|____|____|____|____|____||||
|____|____|____|____|____||||
|____|____|____|____|____||||
|____|____|____|____|____|||/
|____|____|____|____|____||/
|____|____|____|____|____|/

```
> 12 votes

# Answer
# Mathematica 148 143 139 chars

I decided to use transparent glass tiles.

The following code prints ASCII characters "-" in the form of a cuboid with edges, a, b, and c. The only thing you see in the figure below are hyphens.

```
w_~e~_ := {Arrowheads@Table[{1, p/9, Graphics@Style[Text["-"], Red]}, {p, 9}], White,Arrow@w};
GridGraph[{a, b, c} + 1, VertexSize -> 0, EdgeShapeFunction -> e]

```
> 4 votes

# Answer
## C, 226, 212

```
s(x,y){x<1?:putchar(" |/_\n"[y],s(x-1,y));}i,j,x,y,z;main(){for(scanf("%d%d%d",&x,&y,&z);j<=y+z;s(i,1),s(j++>y,2),s(1,4)){s(z-j,0);for(i=x;s(1,j?j>z?1:2:0),i;i--)s(4,3);i=y+z-j;if(i>j)i=j;if(i>z)i=z;if(i>y)i=y;}}

```

Once again a poor score compared to other langs - so any C golf gurus able to improve?
> 2 votes

# Answer
## Python3 (188)

```
a,b,c=map(int,input().split())
x=a+1
k="_"*4
p=print
l=5*a+c+1
p(" "*c+k.join(" "*x))
r=" "*c+k.join("/"*x)+"|"*b+"/"
exec("r=r[1:];p(r[:l]);"*c+'b-=1;p((k.join("|"*x)+"|"*b+"/")[:l]);'*b)

```

It is beaten already, but idea could help someone-else.
> 1 votes

---
Tags: code-golf, ascii-art
---


# Question
Title: Use a genetic algorithm to recreate a string
AKA: the most complex way to return a string I could think of.

**Requirements:**

**Edit: ** @Griffin, You are correct, the goal is to use crossover/mutation of characters in a string to eventually come up with the same as input, although, "Hello World" was simply an example. Really, I just like to see what the others on the site can come up with.

Golf. Try to keep it short. Have fun, dag nabbit!

**Preferences (not required):** -Using a fixed seed on a random number generator would help others reproduce your results. -Bonus if you test for 'properties' of the string, such as the number of L's in "Hello World", instead of only correct characters (like mine).

Shortest code, or highest voted, wins. One exception: if you manage to create a working version in BrainF\***, you win.

**My take using Java:**

```
import static java.lang.Math.*;import java.util.Arrays;import static java.lang.System.out;import java.util.Random;class G{static char[]c;static Random r;public static void main(String[]a){c=a[0].toCharArray();r=new Random(6);P w=new P(9);int n=0;while(!w.f){w.s();if(w.f)out.println(w.g[w.p].x()+"@gen "+n);n++;}}static class P{boolean f=false;int p=0;M[]g=null;P(int s){if(s>=9)g=new M[s];else g=new M[9];for(int i=0;i<g.length;i++)g[i]=new M(c.length);}void s(){f();if(!f){h();j();}}void f(){for(int i=0;i<g.length;i++){g[i].f(c);if(g[i].l==0){f=true;p=i;}}}void h(){Arrays.sort(g);}void j(){M[]b=new M[g.length];for(int i=0;i<g.length-1;i++){float k=r.nextInt(100);if(k<40)b[i]=new M(g[0],g[1]);else if((k<60)&&(k>40))b[i]=new M(g[0],g[2]);else if((k<80)&&(k>60))b[i]=new M(g[1],g[2]);else if((k<90)&&(k>80))b[i]=new M(g[2],g[3]);else if((k<95)&&(k>90))b[i]=new M(g[2],g[4]);else if((k<99)&&(k>95))b[i]=new M(g[0],g[r.nextInt(g.length)]);else b[i]=new M(g[0],new M(c.length));b[g.length-1]=g[0];}g=b;}}static class M implements Comparable {char[]a=null;int l=0;int q=0;int u=8;int o=20;public int compareTo(Object o){M t=(M)o;if(this.l<t.l)return-1;else if(this.l>t.l)return 1;return 0;}M(int s){a=new char[s];for(int i=0;i<a.length;i++)a[i]=(char)r.nextInt(255);}M(M m,M p){a=new char[m.a.length];for(int i=0;i<m.a.length;i++){a[i]=(r.nextInt(100)>2)?m.a[i]:p.a[i];int z=r.nextInt(100);if(z<u)a[i]=(char)r.nextInt(255);else if(z<o){int b=r.nextInt(6);a[i]=(char)(a[i]^(1<<b));}}}void f(char[]v){l=0;for(int i=0;i<a.length;i++){int d=abs(a[i]-v[i]);l+=d;}}String x(){return new String(a);}}}

```

Example output from my code:

```
Hello World!@gen 3352

```

# Answer
> 2 votes
## APL (98)

```
L←⍴T←⎕UCS'Hello World!'⋄F←{+/2*⍨⍵-T}⋄0{0=F ⍵:⍺,⎕UCS⍵⋄(⍺+1)∇{(F⍵)≤F⊢C←⍵+(2-?3)×(⍳L)=?⍴⍵:⍵⋄C}⍵}L?255

```

Can be shortened, at the expense of easy configurability and of result, I'll do so when this one is beaten.

Output:

```
5940 Hello World!

(or another number between ~4000-~9000).

```

Credit for the algorithm: http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/

Explanation:

* `L←⍴T←⎕UCS'Hello World!'`: The target is the ASCII values (`⎕UCS`) of 'Hello World'. (You can change the string.) `L` is its length.
* `F←{+/2*⍨⍵-T}`: F measures the 'distance' between a candidate and a target. This is the sum of the squares of the difference between each character.
* `0{0=F ⍵:⍺,⎕UCS⍵⋄(⍺+1)∇`...`⍵}L?255`: Starting with a random string (`L?255`), if the distance between the target and the candidate is 0 (i.e. we have it) (`0=F ⍵:`), then output the generation and the string (`⍺,⎕UCS⍵`). Otherwise, mutate the candidate and proceed to the next generation.
* `(F⍵)≤F⊢C←⍵+(2-?3)×(⍳L)=?⍴⍵:⍵⋄C`: Generate a new candidate by selecting a random position and mutating it by one. If the distance to the target is less than the old candidate, return the new candidate, otherwise keep the old candidate.

# Answer
> 2 votes
# pdfTeX, 2663

```
\RequirePackage{xparse}
\ExplSyntaxOn
\tl_new:N \l_my_base_tl
\int_new:N \l_my_len_int
\prop_new:N \l_my_base_prop
\prop_new:N \l_my_trial_a_prop
\prop_new:N \l_my_trial_b_prop
\int_new:N \l_my_diff_a_int
\int_new:N \l_my_diff_b_int
\cs_generate_variant:Nn \tl_replace_all:Nnn { Nno }
\DeclareDocumentCommand{\do}{v}
  {
    \tl_set:Nx \l_my_base_tl { \tl_to_str:n {#1} }
    \tl_replace_all:Nno \l_my_base_tl { ~ } { \c_catcode_other_space_tl }
    \int_zero:N \l_my_len_int
    \tl_map_inline:Nn \l_my_base_tl
      {
        \int_incr:N \l_my_len_int
        \prop_put:NVn \l_my_base_prop \l_my_len_int {##1}
      }
    \my_get_diff:NN \l_my_base_prop \l_tmpa_int
    \int_step_inline:nnnn { 1 } { 1 } { \l_my_len_int }
      { \prop_put:Nnn \l_my_trial_a_prop {##1} { O } }
    \my_term:
    \my_get_diff:NN \l_my_trial_a_prop \l_my_diff_a_int
    \bool_set_false:N \l_tmpa_bool
    \bool_until_do:Nn \l_tmpa_bool
      {
        \prop_set_eq:NN \l_my_trial_b_prop \l_my_trial_a_prop
        \prop_map_inline:Nn \l_my_trial_b_prop
          {
            \prop_get:NnN \l_my_trial_b_prop {##1} \l_tmpa_tl
            \prop_get:NnN \l_my_base_prop {##1} \l_tmpb_tl
            \exp_args:Noo \token_if_eq_charcode:NNF \l_tmpa_tl \l_tmpb_tl
              {
                \int_set:Nn \l_tmpa_int
                  { \exp_after:wN `\l_tmpa_tl + \pdfuniformdeviate 7 - 3 }
                \char_set_lccode:nn { `* }
                  { \int_max:nn { 32 } { \int_min:nn { 127 } { \l_tmpa_int } } }
                \tl_to_lowercase:n
                  { \prop_put:Nnn \l_my_trial_b_prop {##1} { * } }
              }
          }
        \my_get_diff:NN \l_my_trial_b_prop \l_my_diff_b_int
        \int_compare:nT { \l_my_diff_b_int < \l_my_diff_a_int }
          {
            \prop_set_eq:NN \l_my_trial_a_prop \l_my_trial_b_prop
            \int_set_eq:NN \l_my_diff_a_int \l_my_diff_b_int
            \int_compare:nT { \l_my_diff_b_int = 0 }
              { \bool_set_true:N \l_tmpa_bool }
            \my_term:
          }
      }
    \tex_end:D
  }
\cs_new_protected:Npn \my_get_diff:NN #1#2
  {
    \int_zero:N #2
    \prop_map_inline:Nn #1
      {
        \prop_get:NnN \l_my_base_prop {##1} \l_tmpa_tl
        \int_add:Nn #2
          {
            ( \my_char_value:o \l_tmpa_tl - \my_char_value:n {##2} )
            * ( \my_char_value:o \l_tmpa_tl - \my_char_value:n {##2} )
          }
      }
  }
\cs_new:Npn \my_char_value:n #1 { \int_eval:n { `#1 } }
\cs_generate_variant:Nn \my_char_value:n { o }
\cs_new_protected_nopar:Npn \my_term:
  { \iow_term:x { \prop_map_function:NN \l_my_trial_a_prop \use_ii:nn } }
\ExplSyntaxOff
\expandafter\do\noexpand

```

Call as

```
pdflatex Experiment573.tex +Hello, World+

```

where the `+` delimiters are arbitrary (identical). I chose `+` here because many more conventional delimiters have a meaning on the command line. This could be shortened quite a bit: I initially thought I'd need floating point computations, which are not available without the `expl3` programming language, so I loaded and used that, which is quite verbose.

# Answer
> 1 votes
# Python, ~~289~~ 286

```
from random import randint as r
s=map(ord,raw_input()[:-1])
L=len(s)
d=lambda x:sum((a-b)**2 for a,b in zip(x,s))
p=map(list,[(64,)*L]*500)
n=0
while 1:
 n+=1
 for b in p:b[r(0,L-1)]+=r(-5,5)
 if any(i==s for i in p):break
 p=sorted(p,key=d)[:100]
 p+=[i[:]for i in p][:500-100]
print n

```

Starting population is a list of strings: `"@" * length_of_input`. Uses the squared sum of the distance for each character and corresponding target character as the fitness function.

# Answer
> 0 votes
# C# - 432

```
using System;using System.Linq;class M{static void Main(string[] a){var g=a[0];int l=g.Length,P=182,S=P/2,k=0,I=0;var r=new Random();Func<int,string>z=null;z=A=>A==0?"":(char)(r.Next(S)+32)+z(A-1);var p=new string[P];while(k<P)p[k++]=z(l);while(p[k=0]!=g){p=p.OrderBy(s=>s.Select((t,i)=>t==g[i]?0:1).Sum()).ToArray();I++;while(k<S){var Q=p[k].ToCharArray();Q[r.Next(l)]=z(1)[0];p[S+k++]=new string(Q);}}Console.WriteLine(I+" "+g);}}

```

Example output: 171 Hello there :)

Better formatted (character count is higher...)

```
using System;
using System.Linq;
class M
{
    static void Main (string[] a)
    {
        var g = a [0];
        int l = g.Length, P = 182, S = P / 2, k = 0, I = 0;
        var r = new Random ();
        Func<int,string> z = null;
        z = A => A == 0 ? "" : (char)(r.Next (S) + 32) + z (A - 1);
        var p = new string[P];
        while (k<P)
            p [k++] = z (l);
        while (p[k=0]!=g) {
            p = p.OrderBy (s => s.Select ((t,i) => t == g [i] ? 0 : 1).Sum ()). ToArray ();
            I++;
            while (k<S) {
                var Q = p [k].ToCharArray ();
                Q [r.Next (l)] = z (1) [0];
                p [S + k++] = new string (Q);
            }
        }
        Console.WriteLine (I + " " + g);
    }
}

```

*Initialization*

An array of 198 random candidates is created (by use of the recursive random string generation function z)

*Main Loop*

The array is (re)sorted by the number of mismatches within the string (this used less characters than power or absolute value). The bottom half of the population is replaced with mutations (by one char) on the first half (the fitter part of the population).

*Termination*

Once the fittest member is equal to the goal, the number of iterations is printed along with the output string.

This is my first golf submission and likely the last one done with C#. I may also try to regolf this in a terser language later.

---
Tags: code-golf
---


title: Compile Regexes

text:
# Question
Title: Compile Regexes
In this task you have to write a program that reads a regular expression and generates another program that outputs whether an input string is accepted by that regular expression. The output must be a program written in the same language as your submission.

# Input

The input is a regular expression *r* matching the following ABNF (the initial production rule is `REGEX`):

```
REGEX       = *( STAR / GROUP / LITERAL / ALTERNATIVE )
STAR        = REGEX '*'
GROUP       = '(' REGEX ')'
LITERAL     = ALPHA / DIGIT
ALTERNATIVE = REGEX '|' REGEX

```

If the input does not match this grammar, the behavior of your program is undefined.

# Interpretation

Interprete the input as a regular expression, where `*` is the Kleene-star (meaning *repeat left argument zero or more times*), `|` is an alternative, `(` and `)` group and no operator at all concatenated. Grouping takes precedence over star, star takes precedence over concatenation, concatenation takes precedence over alternative.

A string is said to be *accepted* if the regex matches the whole string.

# Output

The program's output is another program written in the same language as your submission that reads a string *s* in an implementation defined way at runtime, outputs whether *r* accepts *s* and then terminates. Output may be done in a user-defined way although there must be only two distinct outputs for accepted and rejected programs.

You may assume that the input of your output program is never longer than 216-1 Bytes.

# Restrictions

Neither your submission nor any program generated by your submission may use builtin functionality or libraries that

* match regexes
* transform regular expressions
* compile regular expressions
* generate parsers from a grammar
* simplify the problem in a way that your submission becomes trivial

# Scoring

The score of your submission is the number of characters it. The submission with the lowest score wins.

# Testcases

All testcases contain a regular expression, a set of accepted strings, a set of rejected strings and an example program in C99 which is a valid output of a (hyptothetical) C99 submission.

## (empty regular expression)

### Accepted strings

1. (empty input)

### Rejected strings

1. foo
2. bar
3. baz
4. quux

### Example program

```
#include <stdio.h>

int main() {
    char input[65536];
    gets(input);

    return input[0] != 0;
}

```

## `(b|)(ab)*(a|)` (`a` and `b` alternating)

### accepted strings

1. `a`
2. `ba`
3. `abababababa`
4. `abab`

### rejected strings

1. `afba`
2. `foo`
3. `babba`

### example program

```
#include <stdio.h>

int main() {
  char input[65536];
  int state = 0;

  for (;;) switch (state) {
    case 0: switch (getchar()) {
      case 'a': state = 1; break;
      case 'b': state = 2; break;
      case EOF: return 0;
      default:  return 1;
    } break;
    case 1: switch (getchar()) {
      case 'b': state = 2; break;
      case EOF: return 0;
      default:  return 1;
    } break;
    case 2: switch (getchar()) {
      case 'a': state = 1; break;
      case EOF: return 0;
      default:  return 1;
    } break;
}

```

## `(0|1(0|1)*)(|A(0|1)*1)` (binary floating point numbers)

### accepted strings

1. 10110100
2. 0
3. 1A00001

### rejected strings

1. 011
2. 10A
3. 1A00
4. 100A010

# Answer
> 8 votes
### Ruby, 641 651 543 characters

```
H=Hash.new{|h,k|[k]}
d=[[i=0,0,[]]]
o=[?(]
L="t,u,v=d.pop;q,r,s=d.pop;o.pop<?|&&(H[r]<<=t)||(H[q]<<=t;H[r]<<=u);d<<[q,u,s+v]"
gets.chop.chars.map{|c|c==?*&&(q,r,s=d.pop;H[r]|=[q,i+=1];d<<=[r,i,s];next)
eval(L)while/[|)]/=~c ?o[-1]>?(:o[-1]==?.
/[|(]/=~c&&d<<[i+=1,i,o<<c&&[]]||c!=?)&&d<<[i+=1,i+1,["s==#{o<<?.;i}&&c=='#{c}'&&#{i+=1}"]]||o[-1]=?.}
eval(L)while o.size>1
H.map{H.map{|k,v|v.map{|v|H[k]|=H[v]}}}
t,u,v=d[0]
$><<"s=#{H[t]};gets.chop.chars.map{|c|s=s.map{|s|#{v*'||'}}-[!0];#{H.map{|k,v|"s&[#{k}]!=[]&&s|=#{v}"}*?;}};p s&[#{u}]!=[]"

```

This ruby version became quite long because of several corner cases in the regex parser (maybe I should try a different approach). It expects the regular expression on STDIN and outputs the corresponding ruby code for the matcher to STDOUT.

The program directly generates code for a NFA-ε which is then executed in the matcher.

**Test case 1:** *(output includes additional newlines and indentation)*

```
>>>

s=[0];
gets.chop.chars.map{|c|
  s=s.map{|s|}-[!0];
};
p s&[0]!=[]

```

**Test case 2:**

```
>>> (b|)(ab)*(a|)

s=[0, 1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
gets.chop.chars.map{|c|
  s=s.map{|s|s==2&&c=='b'&&3||s==6&&c=='a'&&7||s==8&&c=='b'&&9||s==12&&c=='a'&&13}-[!0];
  s&[1]!=[]&&s|=[1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[3]!=[]&&s|=[3, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[0]!=[]&&s|=[0, 1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[5]!=[]&&s|=[5, 6];
  s&[7]!=[]&&s|=[7, 8];
  s&[9]!=[]&&s|=[9, 5, 10, 6, 11, 12, 14];
  s&[4]!=[]&&s|=[4, 9, 5, 10, 6, 11, 12, 14];
  s&[11]!=[]&&s|=[11, 12, 14];
  s&[13]!=[]&&s|=[13, 14];
  s&[10]!=[]&&s|=[10, 11, 12, 14]
};
p s&[14]!=[]

```

**Another example:**

```
>>> a|bc

s=[0, 1, 3, 4];
gets.chop.chars.map{|c|
  s=s.map{|s|s==1&&c=='a'&&2||s==4&&c=='b'&&5||s==6&&c=='c'&&7}-[!0];
  s&[0]!=[]&&s|=[0, 1, 3, 4];
  s&[3]!=[]&&s|=[3, 4];
  s&[5]!=[]&&s|=[5, 6];
  s&[2]!=[]&&s|=[2, 7]
};
p s&[7]!=[]

```

*Edit:* Added a transition to fix the bug PleaseStand noted in the comments. Also changed initialisation of state.

# Answer
> 12 votes
## C, 627 characters

This program treats its first command-line argument as the input and generates C code as its output.

```
#define A(v) F[v]+strlen(F[v])
#define S sprintf
char*B="&&f%d(s)||f%d(s)",*J="&&f%d(s+%d)",*r,F[256][65536];h=2;e(f,n,o,R,C,O,t,g){for(C=O=f;*r;++r)switch(*r){case 40:r++;e(g=h++,C=h++,0,0);r[1]^42?t=g:(t=C,S(A(t),B,g,C=h++),r++);o=!S(A(O),J,t,o);O=C;break;case 41:goto L;case'|':S(A(C),J,n,o);o=!S(A(O=f),"||1");break;default:r[1]^42?S(A(C),"&&s[%d]==%d",o++,*r,O^f||R++):(o=!S(A(O),J,t=h++,o),O=C=h++,g=h++,S(A(g),"&&*s==%d&&f%d(s+1)",*r++,t),S(A(t),B,g,C));}L:S(A(C),J,n,o);}main(int c,char**v){r=v[1];for(e(1,!S(*F,"&&!*s"),0,0);h--;)printf("f%d(char*s){return 1%s;}",h,F[h]);puts("main(int c,char**v){exit(f1(v[1]));}");}

```

Here is its output for `(0|1(0|1)*)(|A(0|1)*1)` (with newlines added):

```
f11(char*s){return 1&&s[0]==49&&f7(s+1);}
f10(char*s){return 1&&s[0]==48&&f9(s+1)||1&&s[0]==49&&f9(s+1);}
f9(char*s){return 1&&f10(s)||f11(s);}
f8(char*s){return 1&&f7(s+0)||1&&s[0]==65&&f9(s+1);}
f7(char*s){return 1&&f0(s+0);}
f6(char*s){return 1&&f2(s+0);}
f5(char*s){return 1&&s[0]==48&&f4(s+1)||1&&s[0]==49&&f4(s+1);}
f4(char*s){return 1&&f5(s)||f6(s);}
f3(char*s){return 1&&s[0]==48&&f2(s+1)||1&&s[0]==49&&f4(s+1);}
f2(char*s){return 1&&f8(s+0);}
f1(char*s){return 1&&f3(s+0);}
f0(char*s){return 1&&!*s;}
main(int c,char**v){exit(f1(v[1]));}

```

If you provide valid input as its first command-line argument, it returns exit status 1. Otherwise, it returns exit status 0.

> $ ./regexcompiler '(0|1(0|1)\*)(|A(0|1)\*1)' \> floatprog.c
> $ gcc -o floatprog floatprog.c
> floatprog.c: In function ‘main’:
> floatprog.c:1:519: warning: incompatible implicit declaration of built-in function ‘exit’ \[enabled by default\]
> $ ./floatprog '1A00001' && echo invalid || echo valid
> valid
> $ ./floatprog '100A010' && echo invalid || echo valid
> invalid

Either program, if you fail to provide the command-line argument, dereferences a null pointer, causing a segmentation fault. A sufficiently long regex will overflow the buffers of this submission, and the size of input to a generated program is limited by the size of the stack. However, all the test cases work.

Note that `e(g=h++,C=h++,0,0);` introduces undefined behavior. If, for example, generated programs do not compile, you can try replacing the statement with `h+=2;e(g=h-1,C=h-2,0,0);`, which is five characters longer.

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


title: Finding variables in code

text:
# Question
Title: Finding variables in code
Given some code in your language as a string, find and display all the variable names.

Examples in pseudocode:

```
a=2
b=3
for(i, 0->9) do b=b-10
if a=b then write "a equals b"

```

Returns: `a b i`

```
abcdefgh=20000000000000
bcdifhgs="hello"
if abcdefgh=bcdifhgs then da44="hax"
if abcdefgh*2=da44 then write da44

```

Returns: `abcdefgh bcdifhgs da44`

```
2=3
3=5
5=7
if 2=7 then exit

```

Returns:

```
a=2
while True do b=3

```

Returns: `a b`

Shortest code wins.

For stack-based languages, display the highest height of the stack.
For memory cell based languages, display all the memory cells that have been changed.

# Answer
> 5 votes
## Python 3, ~~73~~ ~~66~~ 86

Now follows the updated test cases:

```
import sys
print(*set(compile(sys.argv[1],'','exec').co_names)-set(dir(__builtins__)))

```

Note that this also prints the names of non-builtin objects and methods / attributes of objects (e.g. if you use `sys.argv` in the input code it'll print `sys` and `argv`). Still, it does technically fit the test cases.

Assuming we're allowed to simply run the code, it can be done in 66 characters. Note that this fails the `while True` test case and, unlike the above solution, does not print things like `sys` and `argv`:

```
import sys
print(*(lambda:(exec(sys.argv[1]),set(locals())))()[1])

```

# Answer
> 2 votes
## Haskell, 2

```
[]

```

Only if you take the word "variable" literally.

# Answer
> 1 votes
# Ruby

Kind of cheating, I guess... If `code` contains Ruby code, then:

```
pre = global_variables
eval code
(global_variables - pre + local_variables + self.instance_variables - [:code, :pre]).each do |x|
  puts x.to_s
end

```

Example: `code = "a = 3; @b = 5; $c = 6, @@d = 10"`

Output:

```
$c
@b

```

*Works only with global and instance vars so far.*

# zsh

```
set > /tmp/set.1
eval $code
set > /tmp/set.2
diff -a /tmp/set.1 /tmp/set.2 | grep -vE "HISTCMD|LINENO|RANDOM|SECONDS|pipestatus" | grep -E ">[^=]+"

```

Example:

$code = `'zzz=3; xxx="hello"'`

Output

```
> xxx=hello
> zzz=3

```

# Clojure, 53

```
(pr(map #(last %)(re-seq #"\( *def +([a-z-])+"code))

```

Example:

```
user=> (def code "(def a 1) (     def    b     ( +  3 5 )))")
#'user/code
user=> (pr(map #(last %)(re-seq #"\( *def +([a-z-]+)"code)))
("a" "b")nil
user=>

```

# Answer
> 1 votes
## Python 104

```
import sys,re,keyword
print(set(re.findall(r"\b\w+\b",sys.argv[1]))-set(keyword.kwlist+dir(__builtins__)))

```

# Answer
> 1 votes
# HQ9+ (or H9+), 0

Is cheating allowed? In this case, the solution is a program of zero length, because the language has no variables, and has no memory cells, stack or any other form of storage. So it outputs nothing.

First I wanted to write Brainf\*ck, but then I realized the "memory cell" rule.

# Answer
> 1 votes
Python, 111

I am pretty new to code golf.. tips are appreciated, but here is an alternative approach

```
import ast as a
s=set()
v=a.NodeVisitor
v.visit_Name=lambda t,n:s.add(n.id)
v().visit(a.parse(input()))
print s

```

# Answer
> -1 votes
# MATLAB, 12

```
eval('<PROGRAM STRING HERE>');who

```

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


title: Huffman golfing

text:
# Question
Title: Huffman golfing
Write a filter that converts text from standard input to a representation of its Huffman tree on standard output. In as few characters as possible.

* you're free to consider newlines or not
* output format is free, as long as it's some *human-readable* encoding of a tree. s-exps, ascii-art and .png, all good. RPN, .dot, I'll smile or frown, but that ought to be ok. Program cores and/or raw pointers , no way.
* no canonicalization needed; if the characters are at the right depth, that's good enough.

Sample possible output for "this is an example of a huffman tree" (from wikipedia):

```
(((e . (n . (o . u))) . (a . (t . m))) .
 (((i . (x . p)) . (h . s)) . (((r . l) . f) . #\space)))

```

I can't reproduce all possible valid outputs with human-readable representation combinations in here (the margin is a bit too thin), but what should check is which characters end up at which number of bits:

* 3 bits: a e \[space\]
* 4 bits: f h i m n s t
* 5 bits: l o p r u x

If \[newline\] is kept in, it appears appears in the "5 bits" level, but (any) two characters have to drop from there to 6 bits.

# Answer
### GolfScript, 54 34 characters

```
:)1/.&.,({{),)@-,-}$(\(@[[\]]+}*~`

```

The script takes input from STDIN and prints the tree in the following form:

```
[[["a" "e"] [["t" "h"] ["i" "s"]]] [[["n" "m"] [["x" "p"] ["l" "o"]]] [[["u" "r"] "f"] " "]]]

```

You may try the code online.

*Edit:* In contrast to the longer version the character counts are not saved inside the tree but recalculated each time we need them.

*Previous version with comments:*

```
1/           # split text into chars
..&          # create string with unique chars

\`{          # for each char
  {1$=},       # filter the original string for this char
  ,            # count number of occurences
  ]            # build data entry [char count]
}+%          # end of for-each loop

.,           # count number of distinct chars
({           # decrement and loop that many times
  {1=}$        # sort list by count field
  (\(@         # take first two elements of sorted list
  +~           # flatten to stack
  [[           # start new entry
    @+           # add count values
    @@[\]        # join nodes into a new tree
    \            # swap count and tree
  ]]+          # close entry and add back to list
}*           # end of for-loop

~~           # flatten array
;            # discard count
`            # transform to readable

```
> 2 votes

# Answer
# Ruby 1.9 - ~~160~~ ~~138~~ 113

```
f=Hash.new(0);$<.chars{|c|f[c]+=1}
f.all?{a,b,*f=f.sort_by(&:last);*a,i=a;*b,j=b;f<<[a,b,i+j];f[1]}
p f[0][0..-2]

```

Ungolfed:

```
f=STDIN.chars.inject(Hash.new(0)){ |f,c|
        f[c]+=1
        f
}
f=f.to_a.map &:reverse

while f.size > 1
        a, b, *f = f.sort_by &:first
        f = [[a[0]+b[0], a, b], *f]
end

p=->a{ a[1].is_a?(String) ? a[1] : [p[a[1]],p[a[2]]] }
p p[f[0]]

```

Output for `this is an example of a huffman tree`:

```
[[[[["l", "p"], ["r", "u"]], ["s", ["o", "x"]]], [["i", "n"], "e"]], [["a", ["h", "t"]], [["m", "f"], " "]]]

```
> 6 votes

# Answer
## Perl, 148

With the `p` command-line option (counted in):

```
$b{$&}++while/./g;for(@_=map[$b{$_},$_],keys%b;$#
_;@_=([$_[0][0]+$_[1][0],"($_[0][1]$_[1][1])"],@_
[2..$#_])){@_=sort{$$a[0]<=>$$b[0]}@_}$_=$_[0][1]

```

Sample use:

```
$ <<< 'this is an example of a huffman tree' perl -pe '$b{$&}++while/./g;for(@_=map[$b{$_},$_],keys%b;$#_;@_=([$_[0][0]+$_[1][0],"($_[0][1]$_[1][1])"],@_[2..$#_])){@_=sort{$$a[0]<=>$$b[0]}@_}$_=$_[0][1]'
(((ae)(((rx)h)((po)(ul))))(((nm)(ti))((sf) )))

```

Ungolfed:

```
# count characters
$b{$&}++ while /./g;

for(
    # init: convert hash to array of [freq,tree] pairs
    @_ = map [$b{$_},$_], keys %b;
    # as long as there are more than one elements left
    $#_;
    # merge the two leftmost nodes
    @_ = ( [ $_[0][0]+$_[1][0], "($_[0][1]$_[1][1])" ], @_[2..$#_] )
)
{
    # keep array in ascending order at all times
    @_=sort{$$a[0]<=>$$b[0]}@_
}

# set up for print
$_=$_[0][1]

```
> 3 votes

# Answer
## Haskell (~~233~~ ~~228~~ 223)

Not completely shure whether it is valid.

```
import List
data T=Char:=Int|N T T Int
s(x:=_)=show x
s(N a b _)='(':s a++s b++")"
g(_:=a)=a
g(N _ _ a)=a
i[a]=a
i(a:b:x)=t$N a b(g a+g b):x
t=i.sortBy((.g).(compare.g))
main=interact$s.t.map(\x->x!!0:=length x).group.sort

```

Outputs:

* The quick, brown fox jumps over the lazy dog.

```
((((('k''l')('i''j'))(('p''q')('m''n')))((('a''b')('.''T'))(('f''g')('c''d'))))(((('z'('x''y'))'e')((('v''w')('s''t'))'o'))((('r''u')(('\n'',')'h'))' ')))
```
* this is an example of a huffman tree

```
((('a''e')(('h''i')(('o''p')('\n''l'))))((('s''t')('m''n'))((('x'('r''u'))'f')' ')))
```

Output format is like in the question, but whithout whitespace and whithout `,` between the two arms. I assume it's human readable.
> 2 votes

# Answer
Python 3.1.2, 132 chars

```
i=input();n=[(i.count(c),c)for c in set(i)]
while n[1:]:n.sort(key=lambda x:x[0]);(a,b),(c,d),*e=n;n=e+[(a+c,(b,d))]
print(n[0][1])

```

It can't handle the empty string.
> 1 votes

---
Tags: code-golf, binary-tree
---


title: Working Week Completion

text:
# Question
Title: Working Week Completion
I work a standard nine to five. Monday through Friday. I take a half hour for lunch from 12:30 to 13:00.

Write me a program which, when run, calculates the percentage of the working week that I have completed at the current moment.

Rules

* Only count time actually spent working. I am punctual and do not work over lunch.
* No input. You may obtain information like current time/date however is convenient.
* The working week is considered complete from end-of-day Friday to midnight between Sunday and Monday.
* Timezone is the local timezone.
* Output should be a decimal number, eg 66.25498, percentage symbol optional.
* The program should be reasonably future-proof. It should be able to cope with leap years.
* Output resolution should be a second or better. I like to watch the kettle boil.
* Code golf. Shortest code wins.

# Answer
# Q, 111 102

```
0|100*("i"$(27000000*((.z.d)mod 7)-2)+{0|((17:00:00&x)-09:00:00)-0|00:30:00&x-12:30:00}.z.t)%135000000

```
> 4 votes

# Answer
## Python 3, 132

```
from datetime import*
t=datetime.now().timetuple()
m=max(0,t[3]*2+t[4]/30-18)
print(20*min(5,(t[6]+min(15,m-min(8,max(7,m))+7)/15)))

```

The resolution is one minute, or 2/45 of a percent. That's more than enough IMO.
> 5 votes

# Answer
## Excel, 132, 129, 123,119, 117

paste into A2:A4

```
=NOW()
=A2-INT(A2)-.375
=(WEEKDAY(A2,3)*7.5+IF(A3<0,0,IF(A3>TIME(8,0,0),7.5,(A3-IF(A3>.1875,TIME(0,30,0),0))*24)))/37.5

```

format the cell A4 as % to get the correct format

40 hour workweek-Paid lunch:

## 88, 81

```
=NOW()
=A1-INT(A1)-.375
=(WEEKDAY(A1,3)*8+IF(A2<0,0,IF(A2>TIME(8,0,0),8,A2*24)))/40

```
> 5 votes

# Answer
## Perl, 124 chars

OK, simple first solution to set the par:

```
say(($p=((($s,$m,$h,@t)=localtime)[6]+6)%7*20+(($h+=$m/60+$s/3600-9)<0?0:$h<3.5?$h:$h<4?3.5:$h<8?$h-.5:7.5)*8/3)<100?$p:100)

```

Run with `perl -M5.010` to enable the Perl 5.10+ `say` feature. Resolution is one second; if one minute resolution is acceptable, the `+$s/3600` part can be deleted for a total length of **116 chars**.

This solution uses `localtime` to get the day of week and the time of day, so it should work regardless of year changes, leap days or any other calendar peculiarities, at least as long as the seven day week cycle doesn't change. DST changes during the workday would slightly confuse it, but those basically never happen anyway, presumably precisely because that would lead to way too much confusion.

(For testing convenience, note that `localtime` accepts a Unix timestamp as an optional argument.)
> 2 votes

# Answer
# Mathematica 169 168 212 214 211 218 210 190 chars

Long-winded, by code golf Standards.

The following takes into account working weeks crossing month or year boundaries, as well as leap years. It reckons time worked according to hours and minutes.

I couldn't think of a way to avoid spelling out the days of the week. Mathematica returns day of week as a 3 character string, which has to be converted to a number.

```
h = Plus @@ {#1, #2/60, #3/3600} & @@ Take[DateList[], -3]; 100*Min[37.5, (StringTake[DateString[], 3] /. {"Mon" -> 0, "Tue" -> 1, "Wed" -> 2 , "Thu" -> 3, "Fri" -> 4, _ -> 5})*7.5 + Which[h < 12.5, Max[0, h - 9], h < 13, 4, True, 4 + Min[h - 13, 4]]]/37.5

```

---

**De-golfed**

```
(* d returns {year, mo, day, h, m, s}   *)
d = DateList[]

(* finished Days: hours worked *)
f = (StringTake[DateString[],  3] /. {"Mon" -> 0, "Tue" -> 1, "Wed" -> 2 , "Thu" -> 3, "Fri" -> 4, _ -> 5})*7.5

(* time of day in hours *)
h = Plus @@ {#1, #2/60} & @@ Take[d, -3]

(* today: hours Worked. It also computes hours for Sat and Sunday but does not use
them in the final tabulation, which has a maximum of 37.5. *)
t = Which[h < 12.5, Max[0, h - 9], h < 13, 4, _, 4 + Min[h - 13, 4]]

(* hours Worked in week *)
tot = Min[37.5, f + t]

(* % of working week completed *)
100*tot/37.5

```
> 2 votes

# Answer
## VBA 141

Formatted to run from the immediate window. Thanks to Sean Cheshire for pointing out a 10-char improvement!

```
n=(Now-Int(Now))*24:a=(Weekday(Now,3)*7.5+IIf(n>17,7.5,IIf(n>9,IIf(n<12.5,n,IIf(n>13,n-.5,n))-9,0)))/37.5:MsgBox Format(IIf(a>1,1,a),".0%")

```
> 2 votes

# Answer
## R, 115 chars

```
---------1---------2---------3---------4---------5---------6---------7---------8---------9---------0---------1---------2
T=as.POSIXlt(Sys.time()-86400);z=T$h+T$mi/60-9;D=function(x,M)min(M,max(0,x));D(((D(z,8)-D(z-3.5,.5))/7.5+T$w)/5,1)

```

Here is a one-week simulation:

```
week.frac <- function(t) {
   T <- as.POSIXlt(t-86400)
   z <- T$h+T$mi/60-9
   D <- function(x,M)min(M,max(0,x))
   D(((D(z,8)-D(z-3.5,.5))/7.5+T$w)/5,1)
}

time <- seq(from = as.POSIXlt(as.Date("2012-08-20")),
            to   = as.POSIXlt(as.Date("2012-08-27")),
            by   = "min")
week.completion <- sapply(time, week.frac)
plot(time, week.completion, type = "l")

```
> 1 votes

# Answer
## Ruby, 191 116,115 113

The logic is stolen from Fraxtils Python solution.

```
t=Time.now
d=t.wday
m=[0,t.hour*2+t.min/3e1-18].max
p d<1?100:20*[5,(d-1+[15,m-[8,[7,m].max].min+7].min/15)].min

```

If you want to test the code with the unit test, you need this 143 character solution:

```
class Time
def r
m=[0,hour*2+min/3e1-18].max
d=wday
d<1?100:20*[5,(d-1+[15,m-[8,[7,m].max].min+7].min/15)].min
end
end
p Time.now.r

```

---

Not the shortest and most efficient code, but with a unit test ;)

The 191 characters include the newlines (I could make it a one-liner, just replace each newline with a `;`).

```
class Time
def r
i=0
d{|t|i+=t.w}
i/1350.0
end
def d
t=dup
yield t-=1 until t.strftime('%w%T')=='109:00:00'
end
def w
h=hour
wday<1||wday>5||h<9||h>16||h==12&&min>29?0:1
end
end
p Time.now.r

```

And the testcode:

```
require 'test/unit'
class MyTest < Test::Unit::TestCase
  def test_mo
    assert_equal( 20, Time.new(2012,8,13,20).r) #monday
  end
  def test_tue
    assert_equal( 40, Time.new(2012,8,14,20).r) #tuesday
  end
  def test_wed_morning
    assert_equal( 40, Time.new(2012,8,15,7).r)
  end
  def test_wed
    assert_equal( 60, Time.new(2012,8,15,20).r)
  end
  def test_thu
    assert_equal( 80, Time.new(2012,8,16,20).r)
  end
  def test_fri
    assert_equal(100, Time.new(2012,8,17,20).r)
  end
  def test_sat
    assert_equal(100, Time.new(2012,8,18,20).r)
  end
  def test_sun
    assert_equal(100, Time.new(2012,8,19,20).r)
  end
  def test_middle
    assert_equal(50, Time.new(2012,8,15,13,15).r)
  end
end

```
> 1 votes

# Answer
# Python 2 130 chars

```
from datetime import*
t=datetime.now().timetuple();
m=min
a=max
n=t[3]+t[4]/60.0
print m(17,a(9,n))-9-(a(0,m(.5,n-12.5)))+7.5*m(t[6],4)

```

Meh third attempt is weak sauce but I think I've gotten the logic right.
> 0 votes

---
Tags: code-golf, number, date
---