title: Quickly divide in Manufactoria

text:
# Question
Title: Quickly divide in Manufactoria
## Background

Manufactoria has been marketed as a game, but we code-golfers can see it for what it really is: a two-dimensional programming language. The Manufactoria programming language is based around a single queue, which contains a series of colorful markers. The instruction pointer moves around the game board using conveyor belts, and it encounters a series of writers and branches which read from and write to the queue.

The language is very easy to understand, so the quickest way to learn it is to play the first few levels of the game (linked above).

# Challenge

Your challenge is to create a program that can divide one number by another number in the least amount of time.

The input to the program will be a string of X blue markers followed by Y red markers. The required output will be a string of red markers with a length of X/Y.

The game board to be used is found in this official contest level:

http://pleasingfungus.com/Manufactoria/?ctm=Divide\_and\_Conquer;Input\_will\_be\_X\_blues\_followed\_by\_Y\_reds,\_output\_X/Y\_reds;bbbbbbrr:rrr|bbbrrr:r|bbbbr:rrrr|r:|bbbbbbbbbbbbrrrr:rrr|bbbbbbbbbbbbrrr:rrrr|bbbbbbbbbrrr:rrr|bbbbbbbbbbrr:rrrrr;13;3;0

It is 13x13 (the maximum size) and it is pre-equipped with the correct tests (see the scoring section).

# Scoring

The score of your program is the total amount of time that it takes for the program to pass all of the tests in the official contest level. The total time is given on the level-complete screen.

While running the tests, you will most likely have to use the 50x accelerate slider in the bottom left in order to receive the results quickly (time acceleration does not affect the score).

Here is a list of division problems that are involved in the tests:

```
 6/2 = 3
 3/3 = 1
 4/1 = 4
 0/1 = 0
12/4 = 3
12/3 = 4
 9/3 = 3
10/2 = 5

```

# Example I/O

```
12/3=4
in:  BBBBBBBBBBBBRRR
out: RRRR

10/2=5
in:  BBBBBBBBBBRR
out: RRRRR

9/3=3
in:  BBBBBBBBBRRR
out: RRR

0/1=0
in:  R
out:

```

# Answer
## Score 3:29

Might as well special case dividing by 1,2,3,4. Makes it a *lot* faster.

http://pleasingfungus.com/Manufactoria/?lvl=34&code=c9:13f2;c10:13f2;c11:13f2;p12:2f7;y13:2f0;p11:2f0;c11:4f3;c10:3f0;p11:5f0;c10:5f0;c9:5f0;c11:6f3;p11:7f0;c10:7f0;p11:3f0;r10:6f1;q8:5f4;q8:6f1;q9:6f1;c7:5f3;c7:6f3;q10:2f0;r10:1f3;r10:4f1;q9:3f4;q9:4f1;c9:2f3;c8:3f3;c8:4f3;r10:8f1;q10:9f6;q9:9f1;q9:8f4;q9:7f4;c8:8f3;c8:9f3;c8:10f3;c8:11f3;c8:12f3;c8:13f2;c7:7f2;c8:7f3;r11:9f3;r11:10f0;r10:10f0;r9:10f3;r9:11f2;p11:11f6;r11:12f1;g11:8f3;b10:11f2;c16:10f2;q17:10f6;q17:11f3;g18:11f0;c12:11f1;c12:10f2;c13:10f2;c14:10f2;c15:10f2;c17:12f0;p16:12f4;c16:11f3;c16:13f1;q15:12f0;r15:13f1;c14:12f3;c14:13f0;c13:13f0;q17:7f6;q17:9f1;q18:9f6;q18:8f5;q17:6f1;g16:6f2;y18:6f0;p17:5f5;r18:5f0;c16:5f0;p15:5f0;r15:6f3;b15:7f2;p16:7f6;r16:8f1;q14:5f0;y14:4f3;g14:6f1;p13:5f0;p13:6f0;p13:7f0;p13:8f0;p13:9f1;g12:9f0;c17:8f1;&ctm=Divide\_and\_Conquer;Input\_will\_be\_X\_blues\_followed\_by\_Y\_reds,\_output\_X/Y\_reds;bbbbbbrr:rrr|bbbrrr:r|bbbbr:rrrr|r:|bbbbbbbbbbbbrrrr:rrr|bbbbbbbbbbbbrrr:rrrr|bbbbbbbbbrrr:rrr|bbbbbbbbbbrr:rrrrr;13;3;0;
> 6 votes

# Answer
## Score: 15:51

Does division by repeated subtraction. Uses a Y amongst the R to keep track of how much divisor we've subtracted so far. Uses Gs to count the quotient.

For instance, the state at the start of each outer loop (right after the initial G writer) for 12/4 is:

```
BBBBBBBBBBBB RRRR G
BBBBBBBB RRRR GG
BBBB RRRR GGG
RRRR GGGG

```

When there are no Bs left, the gadget at the bottom left strips Rs and then outputs #G-1 Rs.

The inner loop strips one B at a time and uses Y to keep track of position. Starting at the outer loop:

```
BBBBBBBB RRRR GG
BBBBBBB RYRRR GG
BBBBBB RRYRR GG
BBBBB RRRYR GG
BBBB RRRR GG

```

The inner loop is the 3x4 box in the lower right. The layout of the rest can probably be improved a bit, but the inner loop is tight.

http://pleasingfungus.com/Manufactoria/?lvl=34&code=c11:13f2;g12:2f3;p12:3f7;c13:3f3;p13:4f3;b12:4f2;r14:4f3;p14:7f7;r13:7f2;q14:8f7;g13:8f2;p14:9f4;r13:10f2;p14:10f7;b15:10f0;q14:11f7;p15:11f3;r16:11f1;p15:8f0;r15:9f1;c16:8f0;c13:2f0;c15:2f0;c16:2f0;c17:2f0;c11:3f3;c11:4f3;c11:6f3;c11:7f3;c11:8f3;c11:9f3;c11:5f3;p11:10f7;q11:11f6;q11:12f7;r10:12f2;c10:10f2;q16:10f5;y14:6f3;q14:5f3;g15:5f1;c15:4f1;c15:3f1;c17:9f1;c17:8f1;c17:7f1;c17:6f1;c17:5f1;c17:4f1;c17:3f1;y16:9f1;g17:10f1;q14:2f4;g14:1f3;&ctm=Divide\_and\_Conquer;Input\_will\_be\_X\_blues\_followed\_by\_Y\_reds,\_output\_X/Y\_reds;bbbbbbrr:rrr|bbbrrr:r|bbbbr:rrrr|r:|bbbbbbbbbbbbrrrr:rrr|bbbbbbbbbbbbrrr:rrrr|bbbbbbbbbrrr:rrr|bbbbbbbbbbrr:rrrrr;13;3;0;
> 4 votes

# Answer
### Score 20:35

A completely different approach - less parts but considerably slower.

http://pleasingfungus.com/Manufactoria/?lvl=34&code=p12:2f3;g11:2f3;b11:3f3;c12:4f2;c11:4f2;c13:2f3;c13:3f3;c13:4f3;c12:5f3;c11:5f1;c10:5f2;c9:8f3;c9:9f3;c10:11f2;c11:11f1;c11:9f1;c11:10f1;c11:12f2;c13:8f0;c11:8f0;c13:7f0;c14:7f0;c14:6f3;c12:7f3;y14:5f0;y10:6f1;y11:7f1;g12:6f2;g9:11f2;g10:10f0;q9:10f3;q13:5f7;q13:6f7;b11:6f1;b10:9f1;p10:7f1;r9:7f2;p10:8f4;p12:8f3;q12:12f3;r13:12f0;r8:10f2;c12:9f3;c12:10f3;c12:11f3;&ctm=Divide\_and\_Conquer;Input\_will\_be\_X\_blues\_followed\_by\_Y\_reds,\_output\_X/Y\_reds;bbbbbbrr:rrr|bbbrrr:r|bbbbr:rrrr|r:|bbbbbbbbbbbbrrrr:rrr|bbbbbbbbbbbbrrr:rrrr|bbbbbbbbbrrr:rrr|bbbbbbbbbbrr:rrrrr;13;3;0;
> 2 votes

---
Tags: fastest-code, manufactoria
---


title: Zebra stripe command output

text:
# Question
Title: Zebra stripe command output
I have a script:

```
$ cat ~/zebra.pl
#!/bin/perl
use Term::ANSIColor;

$Term::ANSIColor::EACHLINE = "\n";

my $zebra = 1; # Are zebras black with white stripes, or white with black stripes?!

my $black = color('white on_black');
my $blue = color('white on_blue');

while (<>){
    chomp($_);

    $zebra = $zebra == 1 ? 0 : 1;

    ($zebra == 1 && print $blue) || print $black;

    print $_;

    ($zebra == 1 && print $black) || print $blue;

    print "\n";
}

print color('reset');

```

Usage:

```
some-command | zebra

```

The output consists of alternating lines that have black and blue backgrounds, respectively. The script seems needlessly long and complex. I'm wondering how much shorter it could be.

# Answer
# Sed: 45 characters

```
1~2s/^/\e[40;37m/;2~2s/^/\e[44;37m/;s/$/\e[m/

```

Usage:

```
some-command | sed $'1~2s/^/\e[40;37m/;2~2s/^/\e[44;37m/;s/$/\e[m/'

```
> 5 votes

# Answer
# C#: 105 84

Easy. You just need some sort of marker, and your infinite loop. From there, things are rather easy.

(Assumes `using System;`, this is just a method body.)

```
bool b=false;while(true){Console.WriteLine((b?"Blue":"Black")+" background!");b=!b;}

```
> 1 votes

# Answer
# Awk: 56 52 characters

```
{x="\x1b[37;4";y=NR%2;print x (y?0:4)"m"$0x 4*y"m"}

```

```
{x="\x1b[37;4%dm";printf x"%s"x"\n",NR%2?0:4,$0,NR%2*4}

```
> 1 votes

---
Tags: code-golf
---


# Question
Title: Generate numerical permutations with conditions and template metaprogramming
This, but via template metaprogramming:

```
template <int n> struct insanity { int[][n] permutations; }

```

Generate all numbers with n digits (0-9) such that each digit is either:

1. Zero
2. The first digit
3. Already present
4. Greater than the maximum digit to the left

Don't worry about leading zeros either way.

Valid examples:

```
012333
012391

```

Invalid examples:

```
012945

```

(Is this even possible?)

Winning code will be explainable and concise, but I'll take a clear short answer over the shortest.

Clarification on conditions: Shortest code with a complete explanation for what's going on. "Complete" means: Explain it to someone who knows how templates work, but not how TMP works.

# Answer
> 4 votes
Success!!!! It only took me 3 hours or so. (Note: Requires C++11 support)

## 4,410 characters (including output functions)

### Compiled on GCC 4.7.2 (Ideone)

```
#include<iostream>
#include<type_traits>

int constexpr powOf10(size_t power)
{
    return power == 0 ? 1 : 10 * powOf10(power - 1);
}

template<int... digits>
struct buildNumber;

template<int first, int... digits>
struct buildNumber<first, digits...> : std::integral_constant<int, first * powOf10(sizeof...(digits)) + buildNumber<digits...>::value>
{
};

template<>
struct buildNumber<> : std::integral_constant<int, 0>
{
};

template<int... digits>
struct areAllDigits;

template<int first, int... digits>
struct areAllDigits<first, digits...>
{
    static bool constexpr value = first > 0 && first < 10 && areAllDigits<digits...>::value;
};

template<int first>
struct areAllDigits<first>
{
    static bool constexpr value = first>0 && first < 10;
};

template<class T>
struct buildNumberT;

template<int... digits>
struct digitContainer
{

};

template<int... digits>
struct buildNumberT<digitContainer<digits...>> : buildNumber<digits...> {};

template<class T1, class T2>
struct concatCtr;

template<int... digits1, int... digits2>
struct concatCtr<digitContainer<digits1...>, digitContainer<digits2...>>
{
    typedef  digitContainer<digits1..., digits2...> type;
};

template<int number, size_t digit>
struct breakIntoDigits
{
    typedef typename concatCtr<digitContainer<number / powOf10(digit)>, typename breakIntoDigits<number % powOf10(digit), digit - 1>::ctr>::type ctr;
};

template<int number>
struct breakIntoDigits<number, 0>
{
    typedef digitContainer<number> ctr;
};

template<int needle, int... haystack>
struct contains;

template<int needle, int first, int... haystack>
struct contains<needle, first, haystack...>
{
    static bool constexpr value = needle == first || contains<needle, haystack...>::value;
};

template<int needle>
struct contains<needle>
{
    static constexpr bool value = false;
};

template<int... values>
struct max;

template<int first, int... rest>
struct max<first, rest...>
{
    static constexpr int value = first > max<rest...>::value ? first : max<rest...>::value;
};

template<>
struct max<>
{
    static int constexpr value = 0;
};

template<class container, int... digits>
struct ruleChecker;

template<int current, int... allPrevious, int... rest>
struct ruleChecker<digitContainer<allPrevious...>, current, rest...>
{
    static bool constexpr value = (current == 0 || sizeof...(allPrevious) == 0 || contains<current, allPrevious...>::value || current > max<allPrevious...>::value) && ruleChecker<digitContainer<allPrevious..., current>, rest...>::value;
};

template<class container>
struct ruleChecker<container>
{
    static bool constexpr value = true;
};

template<class ctr1, class ctr2>
struct ruleCheckerT;

template<class ctr1, int... set2>
struct ruleCheckerT<ctr1, digitContainer<set2...>> : ruleChecker<ctr1, set2...>{};

template<int number, int length>
struct isValidNumber : ruleCheckerT<digitContainer<>, typename breakIntoDigits<number, length>::ctr>
{
};

template<int number, int length>
struct generateList
{
    typedef typename std::conditional<number % powOf10(length) == 0,
        digitContainer<>,
        typename concatCtr<
            typename generateList<number + 1, length>::container,
            typename std::conditional<isValidNumber<number, length>::value,
                    digitContainer<number>,
                    digitContainer<>
                >::type
            >::type
        >::type container;
};

template<int number>
struct generateList<number, 1>
{
    typedef typename concatCtr<
        typename generateList<number + 1, 1>::container,
        typename std::conditional<isValidNumber<number, 1>::value,
                digitContainer<number>,
                digitContainer<>
            >::type
        >::type container;
};

#define DEFINE_ENDPOINT_FOR_LENGTH(length) template<> struct generateList<powOf10(length), (length)>{typedef digitContainer<> container;}

template<int length>
struct insanity
{
    static_assert(length > 0, "Length must be greater than 0.");
    typedef typename concatCtr<typename generateList<1, length>::container, digitContainer<0>>::type numberList;
};

template<int first, int... rest>
void outputContainer(digitContainer<first, rest...> values)
{
    std::cout<<first<<'\n';
    outputContainer(digitContainer<rest...>{});
}

void outputContainer(digitContainer<> empty)
{
    std::flush(std::cout);
}

```

## Explanation

`insanity` is the entry point, as used in the OP. `buildNumber` builds a number from a list of digits; `breakIntoDigits` does the opposite; it takes a number and breaks it into `length` digits. `areAllDigits` is just a helper I used earlier. It isn't used in the final code. It's `value` property is true if all the numbers passed to it are base-10 digits. It generates a list of valid numbers (validated by `isValidNumber`) and puts them in a `digitContainer` (originally I was only going to use this for digits, but I decided to use it for both things).

## Limitations

* It can only calculate up to the point the compiler errors out from template recursion depth.
* You need to define an ending point for each length because otherwise it keeps instantiating templates up to the limit because of std::conditional. You define an ending point for each length by typing `DEFINE_ENDPOINT_FOR_LENGTH(i)` where `i` is the length.

---
Tags: code-challenge, c++, compile-time
---


# Question
Title: Counting ways of scoring k points in n games with half-points for draws
**If a game can result in a win, worth one point; a draw, worth half a point; or a loss, worth no points; how many ways are there of scoring `k` points in `n` games?**

Applicable scenarios include NFL and chess.

* Input is via stdin, and consists of `n` and `k` on separate lines.
* `n` will be a non-negative integer. `(n ≤ 16)`
* `k` will be either a non-negative integer or a non-negative integer plus a half. `(k ≤ n)`
* Output is to stdout. It may, but does not have to, include a trailing newline.

### Test cases

In each case, the first two lines are user-supplied input and the third line is the program output.

```
10
4.5
8350

16
8
5196627

16
13.5
13328

12
12
1

```

# Answer
> 4 votes
## Perl 59 bytes

```
@0=map"$v"+($v=$u)+($u=$_),@0,0,0for(@0=1)x<>;print@0[<>*2]

```

Iteratively generates each row of the triangle of trinomial coefficients up to *n*, and then prints the correct term, *2k*.

---

## Ruby 73 bytes

```
r=*1
gets.to_i.times{r<<0<<u=v=0;r.map!{|t|v+(v=u)+u=t}}
p r[gets.to_f*2]

```

Largely equivalent to the Perl solution above.

---

## Python 84 bytes

```
r=[1]
exec"r=map(sum,zip(r+[0],[0]+r,[0,0]+r))+[1];"*input()
print r[int(input()*2)]

```

Same method as both solutions above.

---

## PHP 91 bytes

```
<?for($n=+fgets(STDIN);(${$j--}+=$$j+${$j-1})?:$n--*$j=$i+=2;${0}=1);echo${fgets(STDIN)*2};

```

Despite being the longest, this was actually the most fun to work on.

# Answer
> 3 votes
## R - 81

```
cat(sum(rowSums(do.call(expand.grid,replicate(scan(n=1),0:2,s=F)))==2*scan(n=1)))

```

A bit longer (106) but I also enjoyed writing it as a recursion:

```
Z=function(n,k)if(n<1|k<0)0 else if(n<2&k<3)1 else Z(n-1,k)+Z(n-1,k-1)+Z(n-1,k-2);Z(scan(n=1),2*scan(n=1))

```

# Answer
> 3 votes
## C# (189 bytes)

Collaborative results from @glthomas, @recursive, @PeterTaylor and @primo

**Best Solution (189 Bytes)**
@glthomas and @recursive each found an additional 2 Bytes over the weekend. (We're convinced that this is the optimal solution using .Net 4.0 and compiling in VS 2010)!

```
using S=System.Console;class C{static void Main(){S.Write(G(G(),2*G()));}
static float G(float L=-1,float T=1){return L<0?float.Parse(S.ReadLine())
:T==0?1:--L<0?0:G(L,T)+G(L,T-1)+G(L,T-2);}}

```

**Improved Solution (193 Bytes)**

```
using System;class C{static void Main(){Func<float,float,float>W=null;W=(n,k)=>n<0?
k*float.Parse(Console.ReadLine()):k==0?1:--n<0?0:W(n,k)+W(n,k-1)+W(n,k-2);
Console.Write(W(W(-1,1),W(-1,2)));}}

```

The additional Byte was saved by combining the input acquisition and static recursive method into a single multipurpose `Func<>`. Input acquisition is triggered when we pass in a negative value of `n`

**Original Solution (195, 194)**

```
using K=System.Console;class C{static void Main(){K.Write(T(int.Parse(K.ReadLine
()),2*float.Parse(K.ReadLine())));}static float T(int n,float k){return k==1?1:--
n<0?0:T(n,k)+T(n,k-1)+T(n,k-2);}}

```

# Answer
> 1 votes
## C# (210 209 chars)

More efficient: iterative approach (209 chars):

```
using K=System.Console;class C{static void Main(){int
n=int.Parse(K.ReadLine()),k=(int)(2*float.Parse(K.ReadLine())),j;var t=new
int[k+3];for(t[2]=1;n-->0;)for(j=k+2;j>1;)t[j]+=t[--j]+t[j-1];K.Write(t[k+2]);}}

```

Less efficient: recursive approach (210 chars);

```
using K=System.Console;class C{static void Main(){int
n=int.Parse(K.ReadLine()),k=(int)(2*float.Parse(K.ReadLine()));K.Write(T(n,k));}static
int T(int n,int k){return k<1?k+1:--n<0?0:T(n,k)+T(n,k-1)+T(n,k-2);}}

```

Note that if `k` is non-integral, it should be supplied in a format applicable to the locale. In my case that means that I have to format the input using `,` as the decimal separator.

# Answer
> 1 votes
## GolfScript (39 chars)

```
'.'/(~2*@,+[1]@{[0.@0+{@2$2$++@@}/+]}*=

```

Online demo

Based on my answer to a previous question about *binomial* coefficients.

# Answer
> 1 votes
## APL (22)

```
+/(2×⎕)=+⌿(N⍴3)⊤⍳3*N←⎕

```

It's not exactly efficient though (set your workspace size to a couple of gigabytes if you want it to actually work up to N=16).

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


title: Fix unbalanced brackets

text:
# Question
Title: Fix unbalanced brackets
Consider the alphabet **A** =`"()[]{}<>"`. Think of the characters in the alphabet as opening and closing brackets of 4 different types. Let's say that a string over the alphabet **A** is balanced if

* it is empty *-or-*
* it is not empty *-and-* the number of opening and closing brackets of each type match *-and-* each opening bracket has a corresponding closing bracket of the same type to the right of it *-and-* the substring between each pair of corresponding brackets is balanced.

For example, the strings `""`, `"()"`, `"<[]>"`, `"{}{}[[]]"` are balanced, but the strings `"("`, `"{>"`, `")("`, `"<>>"`, `"[(])"` are not balanced.

*Task:* Given a (possibly unbalanced) input string **S** over the alphabet **A**, find all possible ways to insert minimal number of brackets to make the string balanced. More precisely,

*Input:* any string **S** over the alphabet **A**.
*Output:* all possible balanced strings of the shortest length over the same alphabet containing **S** as a subsequence.

Some examples (a string to the left of an arrow denotes an input, the list of strings to the right of the arrow denotes the corresponding output):

* `""``""`
* `"()[]"``"()[]"`
* `"["``"[]"`
* `">"``"<>"`
* `"{}]"``"[{}]", "{}[]"`
* `"<<"``"<><>", "<<>>"`

Note that:

* The output always contains at least one string.
* The output contains only those types of brackets that occur in the input string.
* All strings in the output are of the same length.
* If an input string is balanced, then the output consists of the same single string.

*Implementation requirements:*

* Your implementation may be in any programming language and should be as short as possible (in terms of character count or byte count - which one is less). You may represent the source in ASCII, Unicode or any other alphabet normally used in your language. If a program in your language has a shorter standard encoding as a sequence of bytes (like x86 assembly), you may choose to claim its length based on byte count, although you may submit the program in a hexadecimal form (e.g. `7E-FF-02-...`) and/or a textual form using standard mnemonics. If browsers cannot represent characters that you used in the program, you may submit a graphical image of the source and/or a sequence of keystrokes that can be used to type it, but still may claim its length based on character count.
* Any required whitespace or newline characters are included in the character count. If you want, you may submit both an "official", shortest version that is used to claim the length and a "non-official", human-readable version with additional spaces, newlines, formatting, comments, parentheses, meaningful identifier names, etc.
* The implementation may be a complete program/script, a function (along with any helper functions or definitions, if needed), a functional expression (e.g. lambda, anonymous function, code block, several built-in functions combined with a function composition operator, etc) or any similar construct available in your language.
* You may use any standard library functions that normally available in your language, but any required `import`, `using`, `open` or other similar constructs or fully qualified names must be included in the source unless your language imports them by default.
* The program may **not** communicate with any Internet services to obtain the result, intermediate data, or to download some parts of the algorithm.
* If your language supports some form of compressed expressions (like `Uncompress["..."]` in *Mathematica*) you may use them to make the program shorter.
* If your language does not support strings or you do not want to use them, you may use character or integer arrays (or other collections) instead. If your language does not support integers (e.g. lambda-calculus), you may use a suitable encoding for them (like Church numerals).
* For input and output you may use whatever mechanism you prefer: standard input/output streams, user prompt, console output, function parameters and return value, Turing machine tape, reading/writing memory blocks, etc.
* You may assume that an input is well-formed (e.g. that it does not include any characters except `()[]{}<>`) and do not need to validate it. The program behavior may be undefined if the input is not well-formed.
* The output strings may be printed delimited by commas, semicolons, spaces, newlines or other delimiters normally used in your language, with or without surrounding quotation marks, or returned as an array, list, sequence, a single delimited string or any other suitable collection.
* The output strings may be returned in any order, but must not contain duplicates.
* The program execution time must be polynomial with respect to the length of its **output**.

# Answer
# Tcl, 212 characters.

```
eval [zlib i [encoding convertt unicode 兕櫭ッﰌꞟ膸줙ꎠ？곚ၻ菇몐䞝Ӫ᷇ꌃ齷靤녂閉璓陷ョ䎅汚组䕿䎢犄ﲕⷑ稑䞙⠧赧용㽫硣ꖠᓋ蘊湏뢈鱰蒺䡎ྚ嬣᪢꼍ⴚ벎艚㶼큔㱅麓傧ᶘ쳖岠ꇻ퇇䯺蛼෪ᾜ❂᠗移ﺶ䱔엻똆诖ꙧꈦ屪蘦㝖ᝎﴝ䏐駺鞜䓲䣎娯෺顡瑼曾⛁⩤暪鬙쩘覥喼\ud88eႂ嬲꫺\udfdf쒚쾟⒆鱔壌杗殰킞茶嵊䴪ꥁ⽠濶켖덼㘕拘⛇끓ᛱ㐼\ud927碀꣟禝悕衫瀇辸幇鬫瞽\udf90䵸㿕]]

```

You count characters, so I use 1 character for 2 bytes. (Except the invalid characters, that I replaced now)
The zlib is pretty self explanatory. `i` is just the the abbreviation of `inflate`.
`eval`. Well. I don't have to explain that?

After decoding it becomes

```
proc v i {set ::m {};t $i
set r [list [split $i {}]]
lmap c [split $::m {}] {set c [dict get {\{ \} \} \{ {[} \] \] {[} ( ) ) ( < > > <} $c]
lmap a $r[set r {}] {for {set i 0} \$i<=[llength $a] incr\ i {lappend r [linsert $a $i $c]}}}
lsort -u [lmap a [lmap a $r {join $a {}}] {if {![t $a]} continue set\ a}]
}
proc t i {if {{}ne$i} {lmap r {{^(.*){(.*?)}(.*)$} {^(.*)\((.*?)\)(.*)$} {^(.*)<(.*?)>(.*)$} {^(.*)\[(.*?)\](.*)$}} {if {[regexp $r $i - 1 2 3]} {return [expr {[t $1$3]&[t $2]}]}};append ::m $i} {return 1};list 0}

```

Which will be passed to `eval`.
It defines 2 commands: `v`, the main program, and `t` which checks the input and place unmatched braces in the global variable `m`. `v` calls `t` with the input, insert the corresponding brace at all possible positions and use `t` again to filter the valid ones out.

**Input**: 1. Parameter for `v`
**Output**: A Tcl list with each possible valid permutation. They have all the same length.

Example:

```
% v <<
<<>> <><>

```
> 4 votes

---
Tags: code-golf, string, subsequence, balanced-string
---


# Question
Title: Convert this character based table into html one
Take a following character table:

```
-------------------------------------------------------
|       |1233456 | abc    | xyz    |        |         |
|-------|--------|--------|--------|--------|---------|
|       |abcdefgh| 1234567|        | 12345  |         |
|   abc |xyzabcqw|        |        |        |         |
|       |zzzz    |        |        |        |         |
|-------|--------|--------|--------|--------|---------|

```

It can have a variable number of columns or rows. Column width and row height can vary. Cells can be empty or have text, but the row height is optimized to wrap the text. So, second row has three lines because second cell content in second row is three lines high.

Input is ASCII text as shown in example. Cells can not contain | or - characters. Cell content should be escaped, but no need to worry about rowspan and colspan, since the table structure is always simple (every row same number of columns and every column same number of rows).

Output should be well-formed xhtml. Html table should reflect the table structure, content and line breaks. So, resulting html based on the sample input above is the following:

```
<table>
<tr>
    <td></td>
    <td>1233456</td>
    <td>abc</td>
    <td>xyz</td>
    <td></td>
    <td></td>
</tr>
<tr>
    <td>abc</td>
    <td>abcdefgh<br/>xyzabcqw<br/>zzzz</td>
    <td>1234567</td>
    <td></td>
    <td>12345</td>
    <td></td>
</tr>
</table>

```

Shortest code which takes this table and turns it into an xhtml table wins.

# Answer
# Ruby: 233 characters

```
BEGIN{puts"<table>";f=[]};if/^[-|]+$/ then if f!=[] then puts"<tr>\n#{f[1..-2].map{|i|"    <td>#{i.join"<br/>"}</td>"}*$/}\n</tr>\n";f=[]end else$F.each_index{|i|f[i]||=[];f[i]<<CGI.escapeHTML($F[i])if$F[i]>""}end;END{puts"</table>"}

```

Sample run:

```
bash-4.2$ ruby -naF' *\| *' -r cgi -e 'BEGIN{puts"<table>";f=[]};if/^[-|]+$/ then if f!=[] then puts"<tr>\n#{f[1..-2].map{|i|"    <td>#{i.join"<br/>"}</td>"}*$/}\n</tr>\n";f=[]end else$F.each_index{|i|f[i]||=[];f[i]<<CGI.escapeHTML($F[i])if$F[i]>""}end;END{puts"</table>"}' table.txt
<table>
<tr>
    <td></td>
    <td>1233456</td>
    <td>abc</td>
    <td>xyz</td>
    <td></td>
    <td></td>
</tr>
<tr>
    <td>abc</td>
    <td>abcdefgh<br/>xyzabcqw<br/>zzzz</td>
    <td>1234567</td>
    <td></td>
    <td>12345</td>
    <td></td>
</tr>
</table>

```

(Out of contest CW, due to the shameless amount of used command line options.)
> 2 votes

# Answer
# K, 186

Haven't put any effort into golfing this.

```
{-1',/(,"<",g;,/{,/(,"<tr>";x;,"</tr>")}'{("<td>",/:*:'x),\:"</td>"}'{{$[1<+/~""~/:x;,"<br/>"/:x;x@&~""~/:x]}'+x}'-1_'/:1_'/:f@&~()~/:f:$`$"|"\:''1_'(&"-"in/:x)_x;,"</",g:"table>");}

```

.

```
k)t
"-------------------------------------------------------"
"|       |1233456 | abc    | xyz    |        |         |"
"|-------|--------|--------|--------|--------|---------|"
"|       |abcdefgh| 1234567|        | 12345  |         |"
"|   abc |xyzabcqw|        |        |        |         |"
"|       |zzzz    |        |        |        |         |"
"|-------|--------|--------|--------|--------|---------|"

k){-1',/(,"<",g;,/{,/(,"<tr>";x;,"</tr>")}'{("<td>",/:*:'x),\:"</td>"}'{{$[1<+/~""~/:x;,"<br/>"/:x;x@&~""~/:x]}'+x}'-1_'/:1_'/:f@&~()~/:f:$`$"|"\:''1_'(&"-"in/:x)_x;,"</",g:"table>");} t
<table>
<tr>
<td></td>
<td>1233456</td>
<td>abc</td>
<td>xyz</td>
<td></td>
<td></td>
</tr>
<tr>
<td>abc</td>
<td>abcdefgh<br/>xyzabcqw<br/>zzzz</td>
<td>1234567</td>
<td></td>
<td>12345</td>
<td></td>
</tr>
</table>

```
> 2 votes

# Answer
# GNU Awk: 277 characters

```
BEGIN{split("38&60<62>34\"39'",e,/\W/,c)
FS=" *\\| *"
print"<table>"}/^[-|]+$/&&n{print"<tr>"
for(i=2;i<n;i++)print"    <td>"f[i]"</td>"
print"</tr>"
delete f
next}{for(i=1;i<6;i++)gsub(c[i],"\\&#"e[i]";")
for(i=2;i<n=NF;i++)$i&&f[i]=f[i](f[i]?"<br>":"")$i}END{print"</table>"}

```

Note that the above code requires `gawk` version 4.0 or never, because

* `delete` for an entire array is GNU extension
* `split()`'s 4th parameters was implemented in version 4.0

## Without HTML escaping: 201 characters

As there is not specified how HTML escaping should happen (whether the use of built-in or third party functions is allowed, the set of characters to escape, whether using entity names or character codes matters), I believe this challenge was neater without the escaping:

```
BEGIN{FS=" *\\| *"
print"<table>"}/^[-|]+$/&&n{print"<tr>"
for(i=2;i<n;i++)print"    <td>"f[i]"</td>"
print"</tr>"
delete f
next}{for(i=2;i<n=NF;i++)$i&&f[i]=f[i](f[i]?"<br>":"")$i}END{print"</table>"}

```

Sample run:

```
bash-4.1$ awk -f table.awk table.txt
<table>
<tr>
    <td></td>
    <td>1233456</td>
    <td>abc</td>
    <td>xyz</td>
    <td></td>
    <td></td>
</tr>
<tr>
    <td>abc</td>
    <td>abcdefgh<br>xyzabcqw<br>zzzz</td>
    <td>1234567</td>
    <td></td>
    <td>12345</td>
    <td></td>
</tr>
</table>

```
> 0 votes

---
Tags: code-golf, printable-ascii
---


title: Normal distribution values

text:
# Question
Title: Normal distribution values
Write the shortest program possible which outputs a table of Normal distribution values

```
phi(z) = Integral[t from -infty to z of e^(-t^2/2) /sqrt(2 pi) dt]

```

for `z` from 0.00 to 3.99, giving values accurate to 4 decimal places.

The canonical format for such a table appears to be:

```
    0.00    0.01    0.02    0.03    0.04    0.05    0.06    0.07    0.08    0.09
0.0 0.5000  0.5040  0.5080  0.5120  0.5160  0.5199  0.5239  0.5279  0.5319  0.5359
0.1 0.5398  0.5438  0.5478  0.5517  0.5557  0.5596  0.5636  0.5675  0.5714  0.5753
0.2 0.5793  0.5832  0.5871  0.5910  0.5948  0.5987  0.6026  0.6064  0.6103  0.6141
0.3 0.6179  0.6217  0.6255  0.6293  0.6331  0.6368  0.6406  0.6443  0.6480  0.6517
0.4 0.6554  0.6591  0.6628  0.6664  0.6700  0.6736  0.6772  0.6808  0.6844  0.6879
0.5 0.6915  0.6950  0.6985  0.7019  0.7054  0.7088  0.7123  0.7157  0.7190  0.7224
0.6 0.7257  0.7291  0.7324  0.7357  0.7389  0.7422  0.7454  0.7486  0.7517  0.7549
0.7 0.7580  0.7611  0.7642  0.7673  0.7704  0.7734  0.7764  0.7794  0.7823  0.7852
0.8 0.7881  0.7910  0.7939  0.7967  0.7995  0.8023  0.8051  0.8078  0.8106  0.8133
0.9 0.8159  0.8186  0.8212  0.8238  0.8264  0.8289  0.8315  0.8340  0.8365  0.8389
1.0 0.8413  0.8438  0.8461  0.8485  0.8508  0.8531  0.8554  0.8577  0.8599  0.8621
1.1 0.8643  0.8665  0.8686  0.8708  0.8729  0.8749  0.8770  0.8790  0.8810  0.8830
1.2 0.8849  0.8869  0.8888  0.8907  0.8925  0.8944  0.8962  0.8980  0.8997  0.9015
1.3 0.9032  0.9049  0.9066  0.9082  0.9099  0.9115  0.9131  0.9147  0.9162  0.9177
1.4 0.9192  0.9207  0.9222  0.9236  0.9251  0.9265  0.9279  0.9292  0.9306  0.9319
1.5 0.9332  0.9345  0.9357  0.9370  0.9382  0.9394  0.9406  0.9418  0.9429  0.9441
1.6 0.9452  0.9463  0.9474  0.9484  0.9495  0.9505  0.9515  0.9525  0.9535  0.9545
1.7 0.9554  0.9564  0.9573  0.9582  0.9591  0.9599  0.9608  0.9616  0.9625  0.9633
1.8 0.9641  0.9649  0.9656  0.9664  0.9671  0.9678  0.9686  0.9693  0.9699  0.9706
1.9 0.9713  0.9719  0.9726  0.9732  0.9738  0.9744  0.9750  0.9756  0.9761  0.9767
2.0 0.9772  0.9778  0.9783  0.9788  0.9793  0.9798  0.9803  0.9808  0.9812  0.9817
2.1 0.9821  0.9826  0.9830  0.9834  0.9838  0.9842  0.9846  0.9850  0.9854  0.9857
2.2 0.9861  0.9864  0.9868  0.9871  0.9875  0.9878  0.9881  0.9884  0.9887  0.9890
2.3 0.9893  0.9896  0.9898  0.9901  0.9904  0.9906  0.9909  0.9911  0.9913  0.9916
2.4 0.9918  0.9920  0.9922  0.9925  0.9927  0.9929  0.9931  0.9932  0.9934  0.9936
2.5 0.9938  0.9940  0.9941  0.9943  0.9945  0.9946  0.9948  0.9949  0.9951  0.9952
2.6 0.9953  0.9955  0.9956  0.9957  0.9959  0.9960  0.9961  0.9962  0.9963  0.9964
2.7 0.9965  0.9966  0.9967  0.9968  0.9969  0.9970  0.9971  0.9972  0.9973  0.9974
2.8 0.9974  0.9975  0.9976  0.9977  0.9977  0.9978  0.9979  0.9979  0.9980  0.9981
2.9 0.9981  0.9982  0.9982  0.9983  0.9984  0.9984  0.9985  0.9985  0.9986  0.9986
3.0 0.9987  0.9987  0.9987  0.9988  0.9988  0.9989  0.9989  0.9989  0.9990  0.9990
3.1 0.9990  0.9991  0.9991  0.9991  0.9992  0.9992  0.9992  0.9992  0.9993  0.9993
3.2 0.9993  0.9993  0.9994  0.9994  0.9994  0.9994  0.9994  0.9995  0.9995  0.9995
3.3 0.9995  0.9995  0.9995  0.9996  0.9996  0.9996  0.9996  0.9996  0.9996  0.9997
3.4 0.9997  0.9997  0.9997  0.9997  0.9997  0.9997  0.9997  0.9997  0.9997  0.9998
3.5 0.9998  0.9998  0.9998  0.9998  0.9998  0.9998  0.9998  0.9998  0.9998  0.9998
3.6 0.9998  0.9998  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999
3.7 0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999
3.8 0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999  0.9999
3.9 1.0000  1.0000  1.0000  1.0000  1.0000  1.0000  1.0000  1.0000  1.0000  1.0000

```

# Answer
> 3 votes
# Mathematica 132 136 127

If `Erfc` is acceptable, here's my attempt, accurate to 6 places:

```
t=Table;TableForm[Partition[t[0.5 Erfc[-x/Sqrt[2]],{x,0,3.99,.01}],10],
TableHeadings->{t[k,{k,0,3.9,.1}],t[k,{k,0,.09,.01}]}]

```

# Answer
> 2 votes
## GolfScript (124 chars)

```
10:&,~]'    0.0'*40,{n\:I&/'.'I&%&,{'   '\I&*+&8?:^*100/:x^54,-2%{:i*x.{*^/}:$~$i).)*/^\-}/$3989423$15000500+`5<(49-'.'@}%}/

```

Note: the only whitespace in there are two tab characters. MarkDown is turning them into triple-spaces.

The interesting part (i.e. the calculation) is done in `x.8` fixpoint using identity 26.2.10 of *Abramowitz and Stegun (1972)*. The program runs in under 2 seconds on my machine.

# Answer
> 1 votes
## Perl - ~~137~~ 133 bytes

```
print"\t0.0$_"for 0..9;for($f=2.506628;$i++<80;$f*=-++$i){printf'
%.1f',$x,s;;+\$x**$i/$i/$f;;printf"\t%.4f",eval,$x+=.01for(.5.$_)x10}

```

(both \t should be replaced with a literal tab character.)

Uses a Taylor Series expansion<sup>\[1\]</sup>, adding one term per row, which seems to be good enough. The script produces the output exactly as expected, ~~although each row does have a trailing whitespace~~. Runs in about 60ms on my lappy.

Edit as per comment by Peter Taylor.

\[1\] http://mathworld.wolfram.com/NormalDistributionFunction.html (formula 10)

# Answer
> 1 votes
## c -- 372

Just for interest this is an implementation of Peter's Monte Carlo suggestion from the comments

```
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define P printf
#define F(c,n) for(c=0;c<n;++c)
long c=9e9,i,j,k;double a[400],b=.01,t;
double B(){return sqrt(-2*log(drand48()))*cos(2*M_PI*drand48());}main()
{srand48(time(0));F(i,c){t=B();F(k,400)a[k] += t<b*k;}P("%4c",' ');F(j,10)
P("%4.2f    ",b*j);F(i,40){P("\n%3.1f ",10*i*b);F(j,10)
P("%6.4f  ",a[10*i+j]/c);}}

```

Lots of repetitive code. A very straight forward implementation, ungolfed it looks like

```
#include "stdio.h"
#include "stdlib.h"
#include "math.h"

long c=9e9, i, j, k;  /* demands longs longer than 32 bits */

double a[400], bw=.01, t;

double B/*oxMuller*/(){
 /* normal distribution, centered on 0, std dev 1 */
  return sqrt(-2*log(drand48())) * cos(2*M_PI*drand48());
}

main(){
  srand48(time(0));
  for(i=0; i<c; ++i) { /* compute the probabilities by MC integration */
    t=B/*oxMuller*/();
    for(k=0; k<400; ++k) a[k] += t<bw*k;
  }
  /* Print the table */
  printf("%4c",' ');
  for(j=0; j<10; ++j) printf("%4.2f    ",bw*j);
  for(i=0; i<40; ++i) {
    printf("\n%3.1f ",10*i*bw);
    for(j=0; j<10; ++j) printf("%6.4f  ",a[10*i+j]/c);
  }
  printf("\n"); /* make the end pretty */
}

```

It is slow, about 60 seconds to do 100,000,000 throws with absolutely all the optimization bells and whistles turned on (`-m64 -Ofast`) on my 2.2 GHz Core 2 Duo laptop. Worse, it needs circa 50 times that many to provide real confidence that you have the right value in each and every bin. As written I'm asking for even more.

That seems too long to me, but I suspect that I underestimate how much work `drand48` is doing (and I have sacrificed about a factor of 2 in the random number generation at the alter of small code).

It also demands that long is a bit bigger than 32 bits (thus the `-m64` above).

# Answer
> 1 votes
# k

This is based on the Zelen and Severo algorithm here. 162 characters. Can improve the character count significantly by reducing precision.

```
+`q`p!(q;{abs(x>0)-(exp[-.5*x*x]%sqrt 2*acos -1)*t*.31938153+t*-.356563782+t*1.781477937+t*-1.821255978+1.330274429*t:1%1+.2316419*abs x}(q:0.1*!391)+\:0.01*!100)

```

Runs in about 15ms on a Pentium E2160.

---
Tags: code-golf, math, kolmogorov-complexity
---


# Question
Title: Printing all numbers from N to M in one single expression
Given the integers N and M, can you print all numbers from N to M comma-seperated? The hitch is to use one single expression.

The output for *N=23* and *M=42* should look like this:

```
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42

```

I'll start with Ruby:

```
puts (23..42).to_a.join(', ')

```

# Answer
# k

17 chars. Expression returns 1 but prints output to `stdout`

```
1@", "/:$23_!1+42

```

To return a string with the comma seperated values, simply use:

```
", "/:$23_!1+42

```
> 3 votes

# Answer
## Sage CLI, 14

Edit: Sage has a `range` shorthand.

```
`[n..m]`[1:-1]

```
> 2 votes

# Answer
# Tcl, 63 bytes

```
puts "$n,[join [lmap a [lrepeat [expr {$m-$n}] 0] {incr n}] ,]"

```
> 1 votes

# Answer
# Bash, 21 bytes

```
echo {23..42}|tr \  ,

```
> 1 votes

# Answer
# Ruby: 18 characters

```
$><<[*23..42]*", "

```

Sample run:

```
bash-4.1$ ruby -e '$><<[*23..42]*", "'
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42

```

## Forcing the rules: 10 characters

As seen in the other answers:

* variables instead of numeric literals
* comma only instead of comma and space
* no output, just generated value

```
[*n..m]*?,

```

Sample run:

```
irb(main):001:0> n=23
=> 23

irb(main):002:0> m=42
=> 42

irb(main):003:0> [*n..m]*?,
=> "23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42"

```
> 1 votes

# Answer
# Python: 39

```
print(",".join(map(str,range(23,42))))

```
> 0 votes

# Answer
### J, 28 characters

```
echo(,', ',])&":/[23}.i.>:42

```
* `i.43` creates an array of 43 values `0..42`. Unfortunately, we have to compute `43`.
* `23}.` drops first 23 of them, leaving `23..42`. If precomputation is allowed, `23+i.20` fares better byte-wise (-3 characters)
* `,', ',]` concatenates both arguments with `', '` between them
* `...&":` does that after converting both arguments to strings
* `.../` does that as a reduction step.
* `echo` is a built-in to perform standard output. If simply returning is enough, you can drop this (-4 characters)
> 0 votes

# Answer
## R: 17 characters

```
cat(n:m,sep=", ")

```

Example:

```
> n=23
> m=42
> cat(n:m,sep=", ")
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42

```
> 0 votes

---
Tags: rosetta-stone
---


# Question
Title: Fourth of July Edition: Print lines of a file containing multiples of a specific number
Create a program which takes one command-line argument, `n`, which will be an integer less than 2147483648 (2^31), and then reads a file `input.txt` and prints the lines of `input.txt` which contain any substring which is a positive (non-zero) multiple of `n`. You may choose to ignore multiples greater than 2147483647.

### Test case

If `input.txt` contains

```
1. Delaware Dec. 7, 1787
2. Pennsylvania Dec. 12, 1787   1682
3. New Jersey   Dec. 18, 1787   1660
4. Georgia  Jan. 2, 1788    1733
5. Connecticut  Jan. 9, 1788    1634
6. Massachusetts    Feb. 6, 1788    1620
7. Maryland Apr. 28, 1788   1634
8. South Carolina   May 23, 1788    1670
9. New Hampshire    June 21, 1788   1623
10. Virginia    June 25, 1788   1607
11. New York    July 26, 1788   1614
12. North Carolina  Nov. 21, 1789   1660
13. Rhode Island    May 29, 1790    1636
14. Vermont Mar. 4, 1791    1724
15. Kentucky    June 1, 1792    1774
16. Tennessee   June 1, 1796    1769
17. Ohio    Mar. 1, 1803    1788
18. Louisiana   Apr. 30, 1812   1699
19. Indiana Dec. 11, 1816   1733
20. Mississippi Dec. 10, 1817   1699
21. Illinois    Dec. 3, 1818    1720
22. Alabama Dec. 14, 1819   1702
23. Maine   Mar. 15, 1820   1624
24. Missouri    Aug. 10, 1821   1735
25. Arkansas    June 15, 1836   1686
26. Michigan    Jan. 26, 1837   1668
27. Florida Mar. 3, 1845    1565
28. Texas   Dec. 29, 1845   1682
29. Iowa    Dec. 28, 1846   1788
30. Wisconsin   May 29, 1848    1766
31. California  Sept. 9, 1850   1769
32. Minnesota   May 11, 1858    1805
33. Oregon  Feb. 14, 1859   1811
34. Kansas  Jan. 29, 1861   1727
35. West Virginia   June 20, 1863   1727
36. Nevada  Oct. 31, 1864   1849
37. Nebraska    Mar. 1, 1867    1823
38. Colorado    Aug. 1, 1876    1858
39. North Dakota    Nov. 2, 1889    1812
40. South Dakota    Nov. 2, 1889    1859
41. Montana Nov. 8, 1889    1809
42. Washington  Nov. 11, 1889   1811
43. Idaho   July 3, 1890    1842
44. Wyoming July 10, 1890   1834
45. Utah    Jan. 4, 1896    1847
46. Oklahoma    Nov. 16, 1907   1889
47. New Mexico  Jan. 6, 1912    1610
48. Arizona Feb. 14, 1912   1776
49. Alaska  Jan. 3, 1959    1784
50. Hawaii  Aug. 21, 1959   1820

```

then `find_multiples 4` will print the entire file, and `find_multiples 40` will print

```
10. Virginia    June 25, 1788   1607
17. Ohio    Mar. 1, 1803    1788
21. Illinois    Dec. 3, 1818    1720
32. Minnesota   May 11, 1858    1805
40. South Dakota    Nov. 2, 1889    1859
41. Montana Nov. 8, 1889    1809

```

# Answer
> 4 votes
## Perl, 67 chars

```
open F,"input.txt";print grep/(\d+)(?(?{!$^N+$^N%$ARGV[0]})(*F))/,<F>

```

Please note that the given character count is taking advantage of one of Perl's more horrific features, namely that a special variable of the form `$^X` can be written in two characters instead of three, by replacing the `^X` with a literal ctrl-*X* character.

And, of course, this solution wouldn't be possible without a couple of Perl's arguably-equally-terrifying regex extensions that allows one to embed actual code inside of a regex pattern. (But at least those features are clearly documented as being potentially scary.)

\[EDITED to fix bug in argument-handling due to not reading the description carefully enough.\]

# Answer
> 2 votes
# Mathematica

```
dates=Import["input.txt"]
f[digits_]:=FromDigits/@Flatten[Table[Partition[digits,k,1],{k,1,Length[digits]}],1]
g[oneline_]:={FromDigits[oneline[[1]]],Complement[Union[Flatten[f/@oneline]],{0}]}
h[n_,{a_,b_}]:={a,MemberQ[Mod[#,n]&/@b,0]};

w[k_]:=Column@dates[[Cases[h[k,g[#]]&/@ToExpression@(Characters /@ (StringCases[#, DigitCharacter ..] & /@ dates)),{j_,True}:>j]]]

```

`f` removes all non-digits;

`g` finds all the numbers that can be found in a single date line.

`h` checks to see whether Mod\[x, n\] is true for any of the numbers returned by `g`.

`w` calls the subroutines and formats the output.

**Examples**

```
n=40
w[n]

```

---

```
 n=51
 w[n]

```

---

```
 n=71
 w[n]

```

# Answer
> 2 votes
# Ruby 2.0, 129 chars

With some help from @chron:

```
IO.foreach('input.txt'){$><<$_ if$_.gsub(/\d+/).any?{(0..s=$&.size).any?{|i|(1..s).any?{|j|(v=$&[i,j].to_i)%$*[0].to_i<1&&v>0}}}}

```

That long line broken up a bit:

```
IO.foreach('input.txt') {
    $> << $_ if $_.gsub(/\d+/).any? {
        (0..s=$&.size).any? { |i|
            (1..s).any? { |j|
                (v=$&[i,j].to_i) % $*[0].to_i < 1 && v>0 }}}}

```

Example:

```
$ ruby july4.rb 40
10. Virginia    June 25, 1788   1607
17. Ohio    Mar. 1, 1803    1788
21. Illinois    Dec. 3, 1818    1720
32. Minnesota   May 11, 1858    1805
40. South Dakota    Nov. 2, 1889    1859
41. Montana Nov. 8, 1889    1809

$ ruby july4.rb 71
29. Iowa    Dec. 28, 1846   1788

```

# Answer
> 2 votes
# Q, 94

```
-1@m(&){0|/{(x>0)&0=x mod"I"$.z.x 0}"J"$sublist[;x]'[a cross a:(!)1+(#)x]}'[m:(0:)`input.txt];

```

There's undoubtedly a more graceful way to find substrings in q.

```
$ q find_multiples.q 40 -q
10. Virginia    June 25, 1788   1607
17. Ohio    Mar. 1, 1803    1788
21. Illinois    Dec. 3, 1818    1720
32. Minnesota   May 11, 1858    1805
40. South Dakota    Nov. 2, 1889    1859
41. Montana Nov. 8, 1889    1809

```

.

```
$ q find_multiples.q 51 -q
19. Indiana Dec. 11, 1816   1733
25. Arkansas    June 15, 1836   1686
37. Nebraska    Mar. 1, 1867    1823

```

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


title: Strings: Microsoft interview

text:
# Question
Title: Strings: Microsoft interview
You are given an array of strings , you have to construct a single array containing all of them so that the same array of strings can be reconstructed from the large array. The strings may contain any ASCII character. How to determine length of the single large array?

Example= let `a = ["asd";"dfg";"rew"]`. Problem is to combine them in a single string in such a way that it can reconstructed. How to figure out the size of the string which will store the concatenation ?

# Answer
This was a very common in style in Apple \]\[ binaries. The high bit of the first character of each word was set. You know you can do this since ASCII was specifically mentioned and the high bit is *never* set for ASCII. This technique relies on strings that know their own length. We can assume this is the case, since the strings can "contain any ASCII" characters, so C style (null terminated) strings can't work.

For your example, using Python

```
>>> a = ["asd", "dfg", "rew"]
>>> ''.join(chr((ord(s[0])) | 128) + s[1:] for s in a)
'\xe1sd\xe4fg\xf2ew'

```

converting back to the original list

```
>>> (''.join('\x80'+chr((ord(c)) & 127) if c>'\x7f' else c for c in '\xe1sd\xe4fg\xf2ew')).split('\x80')[1:]
['asd', 'dfg', 'rew']

```
> 6 votes

# Answer
# JavaScript, 6

This evaluates to a function. Works in Firefox.

```
uneval

```
> 0 votes

---
Tags: string, puzzle-solver, data-structures
---


title: Compact a Befunge program

text:
# Question
Title: Compact a Befunge program
Befunge is a 2-dimensional esoteric programming language. The basic idea is that (one-character) commands are placed on a 2-dimensional grid. Control flow walks across the grid, executing commands it passes over, and changing direction when it hits an arrow (`>^<v`). Commands are stack-based; see this list. See also http://esolangs.org/wiki/Befunge.

The specification for Befunge-98 is available.

# Problem

Write a program that transforms a Befunge program into a more compact representation. For example, the following program prints `0`:

```
>   0   v

>   @   .

^       <

```

In this case, it could be compacted without changing the program's behavior by removing rows of spaces, to give

```
>0v
>@.
^ <

```

More sophisticated transformations could rotate or mirror sequences of commands and eliminate unnecessary control-flow commands in order to compact the program. For example, with this program:

```
>12345v
      6
v....7<
.
.
.
@

```

you might tuck the end of the program into the hole:

```
>12345v
>...@ 6
^....7<

```

For the first example, the most compact program possible is

```
>0.@

```

You may use any transformations as long as the output program gives the same result.

# Input programs

Input programs are valid Befunge-98 programs.

You may assume that the input program is deterministic. That is, it does not use commands that read external state: the user input commands `&` and `~`, the randomizer `?`, and the self-modifying code commands `p` and `g`.

You may assume the input program terminates.

# Scoring

This is not a code golf, but a problem to write a program that performs code golfing.

The input is a set of test cases (Befunge programs that satisfy the input restrictions above). The total score is the sum of the scores for the test cases.

## Score for each test case

The score is the area of the convex hull of the non-empty cells in the output program, where each cell is treated as a square whose four corners are lattice points in the Cartesian plane. For example, a program of

```
>   v
 @  <

```

gets a score of 9.5.

If your program does not terminate in a reasonable amount of time and memory on a particular input, the score is that of the input program. (This is because you could trivially add a time-limiting wrapper that outputs the input program unchanged if your program doesn't terminate in time.)

If the test-case program has a different result (or fails to terminate) after processing with your program, the score is the score of the input program plus a penalty of 100 points.

# Answer
> 13 votes
I spent a long plane ride coding this one up. I've written a pseudo befunge compiler which runs the befunge program, extracts basic blocks, and lays them out in a compact representation.

Link to the program.

When run on this 99 bottles program:

```
92+9*                           :. v  <
>v"bottles of beer on the wall"+910<
,:
^_ $                             :.v
            >v"bottles of beer"+910<
            ,:
            ^_ $                     v
>v"Take one down, pass it around"+910<
,:
^_ $                           1-v
                                 :
        >v"bottles of beer"+910.:_          v
        ,:
        ^_ $                          ^
                    >v" no more beer..."+910<
                    ,:
                    ^_ $$ @

```

It generates the following output:

```
92+9*:.019+"llaw eht no "v
v  _v# :"bottles of beer"<
>    ,:    v
^  _v#     <
    >$:.019+"reeb f"v
 v _  v#:"bottles o"<
 >     ,:  v
 ^ _  v#   <
      >$019+"dnuo"v
     v"pass it ar"<
     >" ,nwod eno"v
 v _    v#:"Take "<
 >       ,:v
 ^ _    v# <
        >$1-:v
 v _      v# <
 >         :.019+"reeb "v
  v_  v#   :"bottles of"<
  >        ,v
  ^_  v#   :<
      >    $019+"llaw"v
           v" on the "<
           >"reeb fo "v
^  _^#      :"bottles"<
          >019+"...r"v
v  _v#:" no more bee"<
>    ,:    v
^  _v#     <
    >$$@

```

It actually isn't much more compact than the source, but it will probably do better on larger/sparser programs.

The program is laid out with a routing area on the left and basic block contents on the right. A basic block is usually laid out in an even number of rows so the entrance and exit adjoin the routing area. At the end of each basic block, the gadget `#^_v` and variants, laid out right-to-left, do the conditional branch and route flow into columns. At the start of each basic block, these columns are routed into the rows for the destination basic block.

In addition, if the output is short it just generates the output explicitly, like this:

```
"output">:#,_@

```

I haven't done anything to optimize the basic blocks themselves, just the layout. Todo.

So where are the tests?

# Answer
> 1 votes
# Sed, 5 chars

So, even if this is not codegolf, here's a solution that will have a rather good codelength to score ratio, but not necessarily a good score.

```
/^$/d

```

It simply removes blank lines.

---
Tags: code-challenge, optimization, stack, optimized-output, befunge
---


title: Generate cyclic numbers in decimal

text:
# Question
Title: Generate cyclic numbers in decimal
The formula on the wiki article for cyclic numbers can be used to generate cyclic numbers in any base. Using this formula, or any other appropriate formula, **compute** the first ten cyclic numbers in base 10. (The numbers cannot simply be stored and read out, even if the encoding is obscure or novel.)

Repeated cyclic numbers, for example 142857142857, should be avoided if possible.

Output can include `0.` if desired, but it is not required. Each number to be delimited by line, space, comma, etc.

The program which is the shortest and which follows the rules as closely as possible will be declared the winner.

# Answer
> 6 votes
## GolfScript (30 29 chars)

As `xxd` output:

```
0000000: 2207 1113 171d 2f3b 3d61 6d22 7b2e 2831  "...../;=am"{.(1
0000010: 305c 3f2e 402f 2b60 283b 6e7d 25         0\?.@/+`(;n}%

```

This illustrates the importance of making codegolf problems take input so that the results can't be effectively hard-coded.

# Answer
> 4 votes
## GolfScript (45 44 43 chars but less hard-coded)

```
110,{:^(.[-1{.10*^%}^*]?={10^(?.^/+`(;n}*}/

```

This implementation just uses a bound on the possible primes and performs a naïve (but golfed) primitive root check to filter.

Online demo

# Answer
> 2 votes
### GolfScript, 60 53 50 characters

```
107,{))9)1$?.(@)/+`(;.,,{)1$~*`1$.+\?0<}%0-!\n+*}%

```

A plain loop, checking strings for cyclical identity.

Output:

```
142857
0588235294117647
052631578947368421
0434782608695652173913
0344827586206896551724137931
0212765957446808510638297872340425531914893617
0169491525423728813559322033898305084745762711864406779661
016393442622950819672131147540983606557377049180327868852459
010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567
009174311926605504587155963302752293577981651376146788990825688073394495412844036697247706422018348623853211

```

# Answer
> 2 votes
## Python 77 bytes

```
p=0;exec"p+=2\nif len(set(10**i%~p for i in range(p)))/p:print-10**p/~p\n"*54

```

Output:

```
142857
588235294117647
52631578947368421
434782608695652173913
344827586206896551724137931
212765957446808510638297872340425531914893617
169491525423728813559322033898305084745762711864406779661
16393442622950819672131147540983606557377049180327868852459
10309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567
9174311926605504587155963302752293577981651376146788990825688073394495412844036697247706422018348623853211

```

# Answer
> 1 votes
# Mathematica 51 67

```
Cases[Range@110,p_/;10~MultiplicativeOrder~p==p-1:>Round[10^(p-1)/p]]

```

> {142857, 588235294117647, 52631578947368421, 434782608695652173913, 344827586206896551724137931, 212765957446808510638297872340425531914893617, 169491525423728813559322033898305084745762711864406779661, 16393442622950819672131147540983606557377049180327868852459, 10309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567, 9174311926605504587155963302752293577981651376146788990825688073394495412844036697247706422018348623853211}

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


title: Parse a Python string literal

text:
# Question
Title: Parse a Python string literal
The challenge is to parse a string like Python does and print the contents of the string.

* **Input (command-line argument or stdin)**: a string literal (e.g. `"hello"`) (or multiple literals, see *string literal concatenation* below)
* **Output (stdout)**: the contents of the string (e.g. `hello`)

**Rules for parsing the string:**

* A string literal is enclosed in matching pairs of single quotes (`'a'`), double quotes (`"a"`), triple single quotes (`'''a'''`) or triple double quotes (`"""a"""`). The first reoccurrence of the type of quotes that opened the string ends the string.
* **Backslash escapes:** `\'` within a string becomes `'`, `\"` becomes `"` and `\\` becomes `\`. You do not need to implement any other backslash escapes. A backslash that is not part of an escape sequence stays a backslash.
* **String literal concatenation:** The contents of adjacent string literals are concatenated. For example, `"hello" 'world'` becomes `helloworld`.
* The input may contain spaces that are not part of any literal.
* You do not need to support any other kind of whitespace, neither within nor outside literals.

**Additional rules:**

* **`eval`, `exec` and similar stuff is not allowed** for parsing the literal or parts of it.
* You may assume that the input is valid.
* You may assume a maximum input length of 1023 characters.

**Examples:**

* `"hello" ' world'` -\> `hello world`
* `"""\"""'\\\A"""` -\> `"""'\\A`
* `( '''"""'''"""'''""" )` (without parentheses, but with spaces) -\> `"""'''`

Shortest code wins.

# Answer
> 5 votes
## Perl, 54 characters

```
#!/usr/bin/perl -p
s/ |("""|'''|"|')((\\?.)*?)\1/$2/g;s/\\(["'\\])/$1/g

```

Just as I was posting this, I noticed that it's almost identical to Jan Dvorak's Ruby solution. I'm a little put out by how similar it is, in fact, but I'm going to say "Great minds think alike" and let it go at that.

This program highlights a weird corner case in counting characters in Perl scripts: By my reading, the presence of single-quotes in the script means that I need to count the `-p` option as two characters towards my total. Typically, when computing Perl script sizes, the initial dash character on the options is considered to be free, on the justification that it can be bundled with the `-e` that introduces the program proper ... but then you also have to account for any extra escapes you need to enter the script on the command-line. The single-quotes require lots of escaping, so to avoid that penalty I have to count it as a script run from a file, and therefore I get the `#!/usr/bin/perl` for free, but not any option characters. It's a little confusing.

# Answer
> 3 votes
## C, 178 characters

```
char*p,*q,b[1024];d;main(t){for(p=q=gets(b);*p=*q++;)
d?*p==92&!(*q-*p&&*q-34&&*q-39)?*p++=*q++:*p-d||t&&*q-d|q[1]-d?++p:
(d=0,q+=2*t):*p-32?d=*p,t=*q==d&q[1]==d,q+=2*t:0;puts(b);}

```

This is one of those C solutions where everything is done inside a ternary-operator chain gang.

The program works by copying characters back into the same buffer, overwriting the metacharacters. `d` holds the delimiter when inside of a string, and `t` is true if the delimiter is a triple-quote.

# Answer
> 3 votes
### Ruby, ~~74~~ 73 characters

```
puts gets.gsub(/('''|"""|'|")((\\?.)*?)\1|./,'\2').gsub /\\([\\'"])/,'\1'

```

The core here are two regexes: The first one determines the string boundaries and selects the contents only. The alteration is there to remove everything not inside strings, and it also drops unclosed strings.  ~~Backslashes are treated as possesive-optional followed by anything. Thus,~~  Since the regex engine will not backtrack into `(\\?.)` for valid inputs (thanks @breadbox), a sole backslash cannot match there. Quotes are handled via lazy repetition. The second regex then strips a backslash before each escapeable character. The regex depends on the engine to always pick the leftmost alternative first.

I have also considered a state-machine approach, but it turned out quite big (19 states x 4 character classes) compared to the regex solution. I can still post the state machine if anyone is interested.

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


title: Code that changes itself

text:
# Question
Title: Code that changes itself
**Forward:**

Depending on what language you use and what user you are logged in as this challenge could be dangerous so proceed with Caution! You could delete something, fork bomb yourself, or worse...

**Challange:**

Write a program of n bytes which creates n copies of itself on disk, modifies the first byte of the first copy to an 8-bit value of your choosing, modifies the second byte of the second copy to an a bit-value of your choosing, ... , modifies the nth byte of the nth copy of the program to an 8-bit value of your choosing, and then executes all n of the modified copies synchronously starting with the first and ending with the last, the program should print "alive", then program should then exit.

**Scoring: Lowest Score Wins**

Score = (-1 * (Number of times "alive" is printed)) + number of bytes in your program

**RULES**

1. Infinite loops in the program or one of its creations will disqualify an answer.
2. Number of times alive is printed has to be less than 1024.

**Why this interests me:**

I think a lot about the relationships between biology and analogies between living things and computer programs. One of the qualities of living things is that they know how to reproduce. One of the factors of replication that make evolution possible is that the replication is not perfect. If one were to design artificial life it should have a very compact method of reproducing itself. This is why I am turning to the code golf community to see what sort of strange ideas are out there. Sorry for all the edits to this question.

# Answer
> 8 votes
## Perl, 167 - 973 = -806 ~~142 - 55 = 87~~

Here's an entry in the proper spirit of this code challenge:

```
if($ARGV[0]=~s/r/X/){open F,$0;for(@x=split//,join"",<F>){
$c=$_++;open F,">$0~".++$x;print F@x;$_=$c}sleep 1;
fork||exit exec"perl $0~$_ @ARGV"for 1..@x}print"alive\n"

```

I forkbombed myself a few times in the process of writing this script. As a result, this version comes with a couple of safety features. First off is the `sleep 1` just before the spawning loop. That leaves enough idle processing time to allow one to type `killall perl`, if and when such measures become necessary. The second safety feature is that the spawn loop is disabled by default. To run in full power, you need to supply the word `reproduce` as an argument on the command line.

(Seriously, it's embarrassing to acknowledge the number of times I've had to do a hard reboot today because of some bug in my script, before I finally got the balance right.)

The program ends up producing several thousand imperfect copies of itself, from which about one in eight succeeds in printing `alive`. Most of the copies have syntax errors and so don't get run. A handful of scripts run but produce invalid output.

Here's a sample test run. (Note that, due to the `sleep`, it takes several seconds before the spawning finally grinds to a halt and all the scripts stop running.)

```
$ mkdir run
$ cp changer run/
$ cd run
$ ls -l
total 4
-rw-r--r-- 1 breadbox breadbox 167 2013-07-19 21:35 changer
$ perl changer
alive
$ perl changer reproduce 2> /dev/null >> out
$ ls -l out
-rw-r--r-- 1 breadbox breadbox 2608 2013-07-19 21:35 out
$ ls -l out
-rw-r--r-- 1 breadbox breadbox 6404 2013-07-19 21:35 out
$ ls -l out
-rw-r--r-- 1 breadbox breadbox 9370 2013-07-19 21:35 out
$ ls -l out
-rw-r--r-- 1 breadbox breadbox 9370 2013-07-19 21:35 out
$ ls -l | wc -l
7691
$ grep -c alive out
973
$ cd ..
$ rm -r run/
$

```

Finally, I should note that the script has a bit of nondeterminism -- a common enough circumstance when starting up lots of child processes. As a result, the number of `alive`s that get output varies a bit with each run. The highest count I've seen so far is 984, so I believe that it's not in any danger of exceeding the 1024 limit.

# Answer
> 5 votes
Here is my submission:

It's a program of o Bytes. It created 0 copies of itself and modified all 0 bytes. It prints out Alive 0 times for a total socre of -1\*0+0=0

Feel free to smack me for this submission :)

---
Tags: code-challenge
---


title: Golfing Relay Race

text:
# Question
Title: Golfing Relay Race
You need to write a program in any language that will produce (source code for) a program in a different language. That program will produce a 3rd program in another language and so on.

You should aim to create many programs; you aren't limited to 3. You can re-use a language, but it won't be counted in the scoring.

Your entry is the source code of the first program, together with a list of the languages of subsequent programs produced in the order they are produced. For easy reading maybe include each program's output/source.

Scoring will be the length of the source code of the first program divided by the number of different languages used.

---

To prevent solutions such as `1` (that has been pointed out in the comments) I suggest the following extra rule:

The output of one program must not be valid code in the language of that program.

# Answer
## Clojure → C → Python 2.7 → BASIC → Bash

**Score: 13.40**

```
(println"int main(){puts(\"print'PRINT\\\"echo\\\"'\");return 0;}")

```

Here is the breakdown:

1. Clojure

```
(println"int main(){puts(\"print'PRINT\\\"echo\\\"'\");return 0;}")

```
2. C

```
int main(){puts("print'PRINT\"echo\"'");return 0;}

```
3. Python 2.7

```
print'PRINT"echo"'

```
4. BASIC

```
PRINT"echo"

```
5. Bash

```
echo

```

---

I guess a simpler alternative would be

```
print'echo'

```

in Python 2.7, which outputs Bash code. This has a score of **5.5**, but isn't as fancy as what's above.
> 3 votes

# Answer
My first time for that kind of challenge:

## R \> Julia \> BrainF\**k - 91 characters - Score: 30.33

The initial R code:

```
cat("'+'^8","\"[>\"","'+'^9","'>'","'+'^13","'>'","'+'^4","'<'^3","\"-]>.>+.>+.\"",sep="*")

```

It produces the following Julia code:

```
'+'^8*"[>"*'+'^9*'>'*'+'^13*'>'*'+'^4*'<'^3*"-]>.>+.>+."

```

Which produces:

```
++++++++[>+++++++++>++++++++++++++>++++<<<-]>.>+.>+.

```

which equates to:

```
Hi!

```

in BrainF\**k.

**NB:** None of the three programs is valid in any of the two other languages.
> 12 votes

---
Tags: code-challenge
---


title: quine-ish tic-tac-toe

text:
# Question
Title: quine-ish tic-tac-toe
Write a program in your chosen language which plays a perfect game of tic-tac-toe on a 3 * 3 board against a human player. However, **every move has to be a different program**, generated from the previous iteration.

How and in what form you evaluate human input, is up to you, but it has to be read from the standard input. Similarly, you are free to choose a method how you will determine which player starts (for example, you ask first, or you allow the human to enter an invalid move to signal that the computer starts, or other ideas).

Validating moves is not necessary, you can assume a fairly playing human opponent.

Basically, you have program which corresponds to a state of the board. The state is printed in any recognizable way, but at least the following level of detail is expected:

```
X..
00X
x..

```

After the human player entered his moves, your program has to generate the next iteration of itself as a source file in the same language (either to standard output or to a file) and terminate. You are not allowed to store information anywhere else outside of that source file. (it is not necessary for your program to build and run the generated program, it can be done by the user - however, it's not forbidden). When the generated program is built and run, it will behave similarly, display the state, wait for user input, etc.

At the end of the game, you have to print the result (whether you won or it's a tie) in any unambiguously identifiable way.

**By perfect play I mean the program must not lose, and if there is a possibility to force a win, it should win.**

**Shortest code wins**, winner is selected at least 10 days after the first valid entry.

You get a 10% reduction in the score if your program can handle the building and launching of its next iteration. (I know, it's most probably not worth it) Of course, the program itself must be terminated by the time the next iteration accepts the moves from the user.

If you use some strange uncommon tricks, please post a short explanation with your code.

# Answer
> 13 votes
## Perl, 933 characters

```
$m=<<'';$_='         ';
sub h{/^(?:...)*(\d)\1\1/|/^.?.?(\d)..\1..\1/|/(\d)...\1...\1/|/^..(\d).\1.\1/&&$1}
sub r{substr($_,$p-1,1)=pop}sub p{my$w=pop;my@b=(0,h==$w||h&&-1);if(!$b[1]&&/ /){$b[1]=-9;
while(/ /g){local($_,$p)=($_,pos);r$w;$r=-(p($w^1))[1];@b=($p,$r)if$r>$b[1]}}@b}
if(($w=h||!/ /)||!@ARGV){$w--&&print+(nobody,X,O)[$w]," wins\n";s/(...)/$1\n/g;
tr/ 23/.XO/;print}else{$w=3;$w^=1for/\d/g;($p=pop)?r($w^1)&&!h&&(($p)=p$w)&&r$w:s/ /2/;
print"\$m=<<'';\$_='$_';\n$m\n$m"}

sub h{/^(?:...)*(\d)\1\1/|/^.?.?(\d)..\1..\1/|/(\d)...\1...\1/|/^..(\d).\1.\1/&&$1}
sub r{substr($_,$p-1,1)=pop}sub p{my$w=pop;my@b=(0,h==$w||h&&-1);if(!$b[1]&&/ /){$b[1]=-9;
while(/ /g){local($_,$p)=($_,pos);r$w;$r=-(p($w^1))[1];@b=($p,$r)if$r>$b[1]}}@b}
if(($w=h||!/ /)||!@ARGV){$w--&&print+(nobody,X,O)[$w]," wins\n";s/(...)/$1\n/g;
tr/ 23/.XO/;print}else{$w=3;$w^=1for/\d/g;($p=pop)?r($w^1)&&!h&&(($p)=p$w)&&r$w:s/ /2/;
print"\$m=<<'';\$_='$_';\n$m\n$m"}

```

Please note that the blank line in the middle of the script is actually required to be there. (The line breaks at the end of the long lines are not required, other than for legibility, and are not included in the character count.)

Usage: When the program is run without arguments, it displays the current game state. Since at the start the board is empty, the output will be:

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

```

Run the program with an argument between 1 and 9 to claim that square as your move. The program will make its own move and then output a replacement script with the new state. Thus, for example:

```
$ perl ./qttt 5 > ./qttt-2
$ perl ./qttt-2
O..
.X.
...

```

On the very first turn only, you may give a move of `0` to indicate that the computer should take the first move. Note that the first player will always be `X`.

When the game is over, the display output will include a note to that effect:

```
$ perl ./qttt-4 6 > ./qttt-5
$ perl ./qttt-5
O wins
OXX
OOX
X.O

```

The program works by doing a standard minimax search of the game tree. (Tic-tac-toe is a small enough game that a full game tree can be generated on every run.) The exception to this is when the computer moves first -- in this case the initial move to the upper left corner is hard-coded.

Note that this program works in the fashion of a proper quine -- at no point does the script access its own source file in order to produce its output.

---
Tags: code-golf
---


# Question
Title: Avoid duplicate entries using a sign change
This anecdote contains the following intriguing exchange:

> "Fine, Fred," Avi interrupted. "Then how would you change this to avoid duplicate entries?"
>
> "Oh, just change that one there to a negative one."

While this claim is not accurate in context, I do wonder if there's some plausible code for which that makes sense.

Your challenge is to write code (a program, a function, whatever) that fits this criteria:

1. Merges two input lists into one, keeping duplicates. \[edit: You can optionally assume that they are integers, and/or that the lists themselves are unique. You can't assume the integers are positive (the one answer that does this is grandfathered in).\]
2. A literal "1" appears somewhere in the code. If you change this to a literal "-1", the code does the same thing but removing duplicates.
3. The code does not simply branch off of the 1/-1. We're not looking for `if (1 < 1) removeDuplicates()` or `[do_nothing, merge_with_dups, merge_without_dups][1].call()`, for example.

Input and output can be in any reasonable format you choose. One example might be

`[1,2],[2,3]->[1,2,2,3]` before the sign change, and `[1,2,3]` after.

This is a popularity contest. It is **not code golf**, unless you want to show off. I'll accept the highest-voted answer in about two weeks.

# Answer
### JavaScript

Take a conventional algorithm and write it with a bug:

```
function merge(a, b) {
  var ai = 0, bi = 0, oi = 0;
  var o = [];
  while (ai < a.length && bi < b.length) {
    var v = a[ai] < b[bi] ? a[ai++] : b[bi++];
    if (v !== o[oi + 1]) {
      o[oi++] = v;
    }
  }
  while (ai < a.length) o[oi++] = a[ai++];
  while (bi < b.length) o[oi++] = b[bi++];
  return o;
}

```

This code contains exactly one literal `1`. If it is changed to `-1`, then duplicates will be removed. It can be used on any comparable values.
> 11 votes

# Answer
## APL 22/23

Prompts for screen input via ←⎕ and returns an ordered merged list with or, if the leading one is set negative, without duplicates.

```
(~1=0,-2=/v)/v←v[⍋v←⎕]

⎕:
    (1 2),(2 3)
1 2 2 3

(~¯1=0,-2=/v)/v←v[⍋v←⎕]

⎕:
    (1 2),(2 3)
1 2 3

```

Byte counters please note that the single byte APL characters have been converted to UTF8 to render properly on this site.
> 5 votes

# Answer
# k (18)

Should work for any valid type of list

```
{(*1#(::;?:))@x,y}

```

Example:

```
k){(*-1#(::;?:))@x,y}[1 2 3 4;3 4 5 6]
1 2 3 4 5 6
k){(*1#(::;?:))@x,y}[1 2 3 4;3 4 5 6]
1 2 3 4 3 4 5 6

```
> 4 votes

# Answer
## Python

```
def merge(a, b):
    return a + [i for i in b if i not in a*- 1]

```
> 2 votes

# Answer
## Bash

In the spirit of the context, this program removes the duplicates if you add a minus sign before the lowercase `l` on the `grep` line. If you add a minus sign before the uppercase `I` on the previous line, or before the digit `1` on the next line, the program doesn't behave differently.

The input files contain one integer per line (this is the usual representation of lists as text files). They must be passed as two arguments. The resulting list is written to standard ouptut.

```
# Create temp file for working
temp=$(mktemp -d)
# Copy left and right file to merge into same
cp $1 $temp/l
cp $2 $temp/r
cd $temp

while read num
do
  # I remove the output
  set `grep -Lax -e $num l ` <r> /dev/null
  if [ $# != 1 ]
  then echo $num >>r
  fi
done <l

cp r /dev/stdout
cd
rm -r $temp

```

Feel free to use this program as an example of your best code in an interview. All I ask is that you don't say that it's my best code.
> 2 votes

# Answer
## Tcl

In the spirit of the quote

```
foreach item $list1 {
    if {$item in $list2} {set item [expr {$item * 1}]}
    lappend list2 $item
}
foreach item $list2 {
    if {$item >= 0} {lappend result $item}
}

```

If it is a duplicate, multiply it with (-)1, after that filter out negative values.
> 1 votes

# Answer
I'm beginner in PHP I don't know if it's correct

```
$list1=explode(',',$_GET['list1']);
$list2=explode(',',$_GET['list2']);
$list_merged=array_merge($list1,$list2);
print_r($list_merged);
$list_unique=array_unique($list_merged);
print_r($list_unique);

```
> -2 votes

---
Tags: array, popularity-contest, source-layout
---


# Question
Title: Total number of cells in R numeric dataframe
## Problem statement

The task is to write the shortest R statement to count the cells (rows * cols) in an instance of the R type `numeric data.frame`. For example, the `data.frame` which would be displayed as

```
  a    b  c
1 1 2000 NA
2 2 2000 NA
3 3 2000 1
4 4 2000 Inf

```

has 12 cells.

## Input

The `data.frame` is supplied in variable `x`. You may assume that it contains only numbers, boolean, `NA`, `Inf` (no strings and factors).

## Test cases

Example code to construct your own `data.frame`:

```
x <- merge(data.frame(a = 1:100),
    merge(data.frame(b = 2000:2012),
    data.frame(c = c(NA, 10, Inf, 30))))

```

The expected output is 15600.

## Appendix

Curious if someone can beat my solution :-) I don't want to take the fun from you so I will not reveal it now, I will only show you md5sum of my solution so that you later trust me in case you invent the same :-)

d4f70d015c52fdd942e46bd7ef2824b5

# Answer
> 12 votes
Naive:

```
> nrow(x)*ncol(x)
[1] 15600

```

First idea:

```
> prod(dim(x))
[1] 15600

```

Best I can do so far:

```
> length(!x)
[1] 15600

```

SimonO10 on the R chat had an idea (`sum(!(F&x))`), which I modded to get:

```
> sum(T|x)
[1] 15600

```

Note this doesn't work on factors, but you excepted those.

# Answer
> 12 votes
My best two attempts so far only got me down to 11 characters. I'd *love* to see fewer than @Spacedman's 10!

```
>sum( `[<-`(x,,,1) )
[1] 15600

>sum(!(F&x))
[1] 15600

```

# Got it!

```
sum(x^0)
[1] 15600

```

---
Tags: code-golf, r
---


# Question
Title: The number of possible numeric outcomes of parenthesizations of 2^2^...^2
Consider an expression `2^2^...^2` with `n` operators `^`. Operator `^` means exponentiation ("to the power of"). Assume that it has no default assosiativity, so the expression needs to be fully parenthesized to become unambiguous. The number of ways to parenthesize the expression are given by Catalan numbers `C_n=(2n)!/(n+1)!/n!`.

Sometimes different parenthesizations give the same numeric outcome, for example `(2^2)^(2^2)=((2^2)^2)^2`, so the number of different possible numeric outcomes for a given `n` is less than `C_n` for all `n>1`. The sequence starts as `1, 1, 2, 4, 8, ...` as opposed to Catalan numbers `1, 2, 5, 14, 42, ...`

The problem is to write the fastest program (or function) that accepts `n` as an input and returns the number of different possible numeric outcomes of the expression `2^2^...^2` with `n` operators `^`. The performance should not significantly deteriorate as `n` grows, so direct calculation of high power towers is probably a bad idea.

# Answer
# Python 2.7

This approach takes advantage of the following considerations:

Any integer can be represented as a sum of powers of two. The exponents in the powers of two can also be represented as powers of two. For example:

```
8 = 2^3 = 2^(2^1 + 2^0) = 2^(2^(2^0) + 2^0)

```

These expressions that we end up with can be represented as sets of sets (in Python, I used the built-in `frozenset`):

* `0` becomes the empty set `{}`.
* `2^a` becomes the set containing the set representing `a`. E.g.: `1 = 2^0 -> {{}}` and `2 = 2^(2^0) -> {{{}}}`.
* `a+b` becomes the concatenation of the sets representing `a` and `b`. E.g., `3 = 2^(2^0) + 2^0 -> {{{}},{}}`

It turns out that expressions of the form `2^2^...^2` can easily be transformed into their unique set representation, even when the numerical value is much too large to be stored as an integer.

---

For **`n=20`**, this runs in **8.7s** on CPython 2.7.5 on my machine (a bit slower in Python 3 and much slower in PyPy):

```
"""Analyze the expressions given by parenthesizations of 2^2^...^2.

Set representation:  s is a set of sets which represents an integer n.  n is
  given by the sum of all 2^m for the numbers m represented by the sets
  contained in s.  The empty set stands for the value 0.  Each number has
  exactly one set representation.

  In Python, frozensets are used for set representation.

  Definition in Python code:
      def numeric_value(s):
          n = sum(2**numeric_value(t) for t in s)
          return n"""

import itertools

def single_arg_memoize(func):
    """Fast memoization decorator for a function taking a single argument.

    The metadata of <func> is *not* preserved."""

    class Cache(dict):
        def __missing__(self, key):
            self[key] = result = func(key)
            return result
    return Cache().__getitem__

def count_results(num_exponentiations):
    """Return the number of results given by parenthesizations of 2^2^...^2."""
    return len(get_results(num_exponentiations))

@single_arg_memoize
def get_results(num_exponentiations):
    """Return a set of all results given by parenthesizations of 2^2^...^2.

    <num_exponentiations> is the number of exponentiation operators in the
    parenthesized expressions.

    The result of each parenthesized expression is given as a set.  The
    expression evaluates to 2^(2^n), where n is the number represented by the
    given set in set representation."""

    # The result of the expression "2" (0 exponentiations) is represented by
    # the empty set, since 2 = 2^(2^0).
    if num_exponentiations == 0:
        return {frozenset()}

    # Split the expression 2^2^...^2 at each of the first half of
    # exponentiation operators and parenthesize each side of the expession.
    split_points = xrange(num_exponentiations)
    splits = itertools.izip(split_points, reversed(split_points))
    splits_half = ((left_part, right_part) for left_part, right_part in splits
                                           if left_part <= right_part)

    results = set()
    results_add = results.add
    for left_part, right_part in splits_half:
        for left in get_results(left_part):
            for right in get_results(right_part):
                results_add(exponentiate(left, right))
                results_add(exponentiate(right, left))
    return results

def exponentiate(base, exponent):
    """Return the result of the exponentiation of <operands>.

    <operands> is a tuple of <base> and <exponent>.  The operators are each
    given as the set representation of n, where 2^(2^n) is the value the
    operator stands for.

    The return value is the set representation of r, where 2^(2^r) is the
    result of the exponentiation."""

    # Where b is the number represented by <base>, e is the number represented
    # by <exponent> and r is the number represented by the return value:
    #   2^(2^r) = (2^(2^b)) ^ (2^(2^e))
    #   2^(2^r) = 2^(2^b * 2^(2^e))
    #   2^(2^r) = 2^(2^(b + 2^e))
    #   r = b + 2^e

    # If <exponent> is not in <base>, insert it to arrive at the set with the
    # value: b + 2^e.  If <exponent> is already in <base>, take it out,
    # increment e by 1 and repeat from the start to eventually arrive at:
    #   b - 2^e + 2^(e+1) =
    #   b + 2^e
    while exponent in base:
        base -= {exponent}
        exponent = successor(exponent)
    return base | {exponent}

@single_arg_memoize
def successor(value):
    """Return the successor of <value> in set representation."""
    # Call exponentiate() with <value> as base and the empty set as exponent to
    # get the set representing (n being the number represented by <value>):
    #   n + 2^0
    #   n + 1
    return exponentiate(value, frozenset())

def main():
    import timeit
    print timeit.timeit(lambda: count_results(20), number=1)
    for i in xrange(21):
        print '{:.<2}..{:.>9}'.format(i, count_results(i))

if __name__ == '__main__':
    main()

```

(The memoization decorator's concept is copied from http://code.activestate.com/recipes/578231-probably-the-fastest-memoization-decorator-in-the-/ .)

Output:

```
8.667753234
0...........1
1...........1
2...........1
3...........2
4...........4
5...........8
6..........17
[...]
19.....688366
20....1619087

```

Timings for different `n`:

```
 n    time
16    0.240
17    0.592
18    1.426
19    3.559
20    8.668
21   21.402

```

Any `n` above 21 results in a memory error on my machine.

I'd be interested if anyone can make this faster by translating it into a different language.

**Edit:** Optimized the `get_results` function. Also, using Python 2.7.5 instead of 2.7.2 made it run a bit faster.
> 9 votes

# Answer
## C#

This is a translation of flornquake's Python code to C# using a lower level addition routine which provides a moderate speedup over a direct translation. It's not the most optimised version I have, but that is quite a bit longer because it has to store the tree structure as well as the values.

```
using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox {
    class PowerTowers {
        public static void Main() {
            DateTime start = DateTime.UtcNow;
            for (int i = 0; i < 17; i++)
                Console.WriteLine("{2}: {0} (in {1})", Results(i).Count, DateTime.UtcNow - start, i);
        }

        private static IList<HashSet<Number>> _MemoisedResults;

        static HashSet<Number> Results(int numExponentations) {
            if (_MemoisedResults == null) {
                _MemoisedResults = new List<HashSet<Number>>();
                _MemoisedResults.Add(new HashSet<Number>(new Number[] { Number.Zero }));
            }

            if (numExponentations < _MemoisedResults.Count) return _MemoisedResults[numExponentations];

            HashSet<Number> rv = new HashSet<Number>();
            for (int i = 0; i < numExponentations; i++) {
                IEnumerable<Number> rhs = Results(numExponentations - 1 - i);
                foreach (var b in Results(i))
                    foreach (var e in rhs) {
                        if (!e.Equals(Number.One)) rv.Add(b.Add(e.Exp2()));
                    }
            }
            _MemoisedResults.Add(rv);
            return rv;
        }
    }

    // Immutable
    struct Number : IComparable<Number> {
        public static Number Zero = new Number(new Number[0]);
        public static Number One = new Number(Zero);

        // Ascending order
        private readonly Number[] _Children;
        private readonly int _Depth;
        private readonly int _HashCode;

        private Number(params Number[] children) {
            _Children = children;
            _Depth = children.Length == 0 ? 0 : 1 + children[children.Length - 1]._Depth;

            int hashCode = 0;
            foreach (var n in _Children) hashCode = hashCode * 37 + n.GetHashCode() + 1;
            _HashCode = hashCode;
        }

        public Number Add(Number n) {
            // "Standard" bitwise adder built from full adder.
            // Work forwards because children are in ascending order.
            int off1 = 0, off2 = 0;
            IList<Number> result = new List<Number>();
            Number? carry = default(Number?);

            while (true) {
                if (!carry.HasValue) {
                    // Simple case
                    if (off1 < _Children.Length) {
                        if (off2 < n._Children.Length) {
                            int cmp = _Children[off1].CompareTo(n._Children[off2]);
                            if (cmp < 0) result.Add(_Children[off1++]);
                            else if (cmp == 0) {
                                carry = _Children[off1++].Add(One);
                                off2++;
                            }
                            else result.Add(n._Children[off2++]);
                        }
                        else result.Add(_Children[off1++]);
                    }
                    else if (off2 < n._Children.Length) result.Add(n._Children[off2++]);
                    else return new Number(result.ToArray()); // nothing left to add
                }
                else {
                    // carry is the (possibly joint) smallest value
                    int matches = 0;
                    if (off1 < _Children.Length && carry.Value.Equals(_Children[off1])) {
                        matches++;
                        off1++;
                    }
                    if (off2 < n._Children.Length && carry.Value.Equals(n._Children[off2])) {
                        matches++;
                        off2++;
                    }

                    if ((matches & 1) == 0) result.Add(carry.Value);
                    carry = matches == 0 ? default(Number?) : carry.Value.Add(One);
                }
            }
        }

        public Number Exp2() {
            return new Number(this);
        }

        public int CompareTo(Number other) {
            if (_Depth != other._Depth) return _Depth.CompareTo(other._Depth);

            // Work backwards because children are in ascending order
            int off1 = _Children.Length - 1, off2 = other._Children.Length - 1;
            while (off1 >= 0 && off2 >= 0) {
                int cmp = _Children[off1--].CompareTo(other._Children[off2--]);
                if (cmp != 0) return cmp;
            }

            return off1.CompareTo(off2);
        }

        public override bool Equals(object obj) {
            if (!(obj is Number)) return false;

            Number n = (Number)obj;
            if (n._HashCode != _HashCode || n._Depth != _Depth || n._Children.Length != _Children.Length) return false;
            for (int i = 0; i < _Children.Length; i++) {
                if (!_Children[i].Equals(n._Children[i])) return false;
            }

            return true;
        }

        public override int GetHashCode() {
            return _HashCode;
        }
    }
}

```
> 5 votes

---
Tags: fastest-code, combinatorics, sequence
---


title: Who brings the croissants?

text:
# Question
Title: Who brings the croissants?
This question is inspired by a similar question first asked on StackOverflow by Florian Margaine, then asked in variant forms on CS by Gilles and on Programmers by GlenH7.

This time, it's a code golf, with specific metrics for success!

In an office of ten people, it's someone's turn to buy croissants every morning. The goal is to produce a schedule that lists whose turn it is on any given day, subject to the following constraints:

1. Presence. Each person is away from the office on business or vacation on average ~20% of the time. Each time you schedule a person who is away, lose one point per person who didn't get to eat croissants. For simplicity, generate the away-schedule with the random number generator `seed = (seed*3877 + 29573) % 139968`, starting with `42*(10*i + 1)` as the initial (unused) seed, where `i` is the zero-indexed number of the employee; whenever `seed` is below 27994, that person will be away. Note that if everyone is away, you can assign anyone and not lose points.
2. Fairness. Each person will keep track of whether they have bought more or fewer croissants than the average. A person who never buys more than 10 more than the average will give you one point (they understand that someone has to buy first, and they'll of course go above the average). Otherwise, let `k` be the farthest above the average that a person has gotten in `n` days of buying; that person will give you `1 - (k-10)/100` points. (Yes, this may be negative.)
3. Randomness. The employees get bored if they can predict the sequence. Gain ten times the number of bits of information revealed a typical choice; assume that the employees can search for repetitive patterns and know the order of how long it's been since each of them bought croissants.
4. Non-repetitiveness. Employees hate buying croissants two days in a row. Each time this happens, lose a point.
5. Brevity. if `b` is the number of bytes of the gzipped\* version of your solution, reduce your score by `b/50`.

The solution should be an output of letters or numbers (0-9 or A-J) indicating who should buy croissants on each day. Run the algorithm for five hundred days (two years of work); give yourself a point if the output is in 10 rows of 50.

You *only* need to produce the sequence, not calculate the score. Here is a reference program in Matlab (or Octave) that picks people completely at random except for avoiding people who are away:

```
function b = away(i)
b=zeros(500,1); seed=42*(10*i+1);
for j=1:500
  seed=mod((seed*3877+29573),139968);
  b(j)=seed<27994;
end
end

A=zeros(500,10);
for i=1:10
  A(:,i)=away(i-1);
end
for i=1:10
  who = zeros(1,50);
  for j=1:50
    k = 50*(i-1)+j;
    who(j)=floor(rand(1,1)*10);
    if (sum(A(k,:)) < 10)
      while (A(k,who(j)+1)==1)
        who(j)=floor(rand(1,1)*10);
      end
    end
  end
  fprintf(1,'%s\n',char(who+'A'));
end

```

Here is a sample run:

```
HHEADIBJHCBFBGBIDHFFFHHGGHBEGCDGCIDIAEHEHAJBDFIHFI
JFADGHCGIFHBDFHHJCFDDAEDACJJEDCGCBHGCHGADCHBFICAGA
AJAFBFACJHHBCHDDEBEEDDGJHCCAFDCHBBCGACACFBEJHBEJCI
JJJJJBCCAHBIBDJFFFHCCABIEAGIIDADBEGIEBIIJCHAEFDHEG
HBFDABDEFEBCICFGAGEDBDAIDDJJBAJFFHCGFBGEAICEEEBHAB
AEHAAEEAJDDJHAHGBEGFHJDBEGFJJFBDJGIAJCDCBACHJIJCDF
DIJBHJDADJCFFBGBCCEBEJJBAHFEDABIHHHBDGDBDGDDBDIJEG
GABJCEFIFGJHGAFEBHCADHDHJCBHIFFHHFCBAHCGGCBEJDHFAG
IIGHGCAGDJIGGJFIJGFBAHFCBHCHAJGAJHADEABAABHFEADHJC
CFCEHEDDJCHIHGBDAFEBEJHBIJDEGGDGJFHFGFJAIJHIJHGEBC

```

which gives a total score of -15.7:

```
presence:    0    (Nobody scheduled while away)
fairness:    6.6  (~340 croissants bought "unfairly")
randomness: 33.2  (maximum score--uniformly random)
no-repeat: -51.0  (people had to bring twice 51 times)
size:       -5.5  (275 bytes gzipped)
format:      1    (50 wide output)

```

Here is the reference Scala method I'm using to compute the score

```
def score(output: String, sz: Either[Int,String], days: Int = 500) = {
  val time = (0 until days)
  def away(i: Int) =
    Iterator.iterate(42*(10*i+1))(x => (x*3877+29573)%139968).map(_<27994)
  val everyone = (0 to 9).toSet
  val aways =
    (0 to 9).map(i => away(i).drop(1).take(days).toArray)
  val here = time.map(j => everyone.filter(i => !aways(i)(j)))
  val who = output.collect{
    case x if x>='0' && x<='9' => x-'0'
    case x if x>='A' && x<='J' => x-'A'
  }.padTo(days,0).to[Vector]
  val bought =
    time.map(j => if (here(j) contains who(j)) here(j).size else 0)
  val last = Iterator.iterate((0 to 10).map(_ -> -1).toMap){ m =>
    val j = 1 + m.map(_._2).max
    if (bought(j)==0) m + (10 -> j) else m + (who(j) -> j)
  }.take(days).toArray

  def log2(d: Double) = math.log(d)/math.log(2)
  def delayEntropy(j0: Int) = {
    val n = (j0 until days).count(j => who(j)==who(j-j0))
    val p = n.toDouble/(days-j0)
    val q = (1-p)/9
    -p*log2(p) - 9*q*log2(q)
  }
  def oldestEntropy = {
    val ages = last.map{ m =>
      val order =  m.filter(_._1<10).toList.sortBy(- _._2)
      order.zipWithIndex.map{ case ((w,_),i) => w -> i }.toMap
    }
    val k = last.indexWhere(_.forall{ case (k,v) => k == 10 || v >= 0 })
    (k until days).map{ j => ages(j)(who(j)) }.
      groupBy(identity).values.map(_.length / (days-k).toDouble).
      map(p => - p * log2(p)).sum
  }

  def presence =
    time.map(j => if (here(j) contains who(j)) 0 else -here(j).size).sum
  def fairness = {
    val ibought = (0 to 9).map{ i =>
      time.map(j => if (i==who(j)) bought(j) else 0).
        scan(0)(_ + _).drop(1)
    }
    val avg = bought.scan(0)(_ + _).drop(1).map(_*0.1)
    val relative = ibought.map(x => (x,avg).zipped.map(_ - _))
    val worst = relative.map(x => math.max(0, x.max-10))
    worst.map(k => 1- k*0.01).sum
  }
  def randomness =
    ((1 to 20).map(delayEntropy) :+ oldestEntropy).min*10
  def norepeat = {
    val actual = (who zip bought).collect{ case (w,b) if b > 0 => w }
    (actual, actual.tail).zipped.map{ (a,b) => if (a==b) -1.0 else 0 }.sum
  }
  def brevity = -(1/50.0)*sz.fold(n => n, { code =>
    val b = code.getBytes
    val ba = new java.io.ByteArrayOutputStream
    val gz = new java.util.zip.GZIPOutputStream(ba)
    gz.write(b, 0, b.length); gz.close
    ba.toByteArray.length + 9 // Very close approximation to gzip size
  })
  def columns =
    if (output.split("\\s+").filter(_.length==50).length == 10) 1.0 else 0

  val s = Seq(presence, fairness, randomness, norepeat, brevity, columns)
  (s.sum, s)
}

```

(there is a usage note^).

The winner is the one with the highest score! Actually, there will be two winners: a globally optimizing winner and a short-notice winner for algorithms where earlier selections do not depend vacations that will happen in the future. (Real office situations are in between these two.) One entry may of course win both (i.e. it is short-notice but still outperforms other entries). I'll mark the short-notice winner as the "correct" winner, but will list the globally optimizing winner first on the scoreboard.

Scoreboard:

```
Who            What                   Score   Short-notice?
============== ====================== ======= ===
primo          python-miniRNG          37.640  Y
Peter          Golfscript-precomputed  36.656  N
Rex            Scala-lottery           36.002  Y
Rex            Matlab-reference       -15.7    Y

```

*I'm using gzip 1.3.12 with no options; if there are multiple files, I cat them together first.

\**A list prepared in advance is not considered short-notice unless it would be swapped out for a better list if an away-day appeared the day before; if this is a major issue (e.g. an unanticipated away day causes reversion to an algorithm that performs horribly) I'll define precise criteria.

^ If you use gzip, pass in the size as `Left(287)`; otherwise if your code is in `code` (`val code="""<paste>"""` is useful here), use `Right(code)`)

# Answer
> 3 votes
## Python (37.640 points)

```
i=61
r=[420*n+42for n in range(10)]
for n in r:
 o=''
 for n in r*5:
    r=[(n*3877+29573)%139968for n in r]
    f=[n<27994for n in r]
    l=i
    while~-all(f)*f[i%10]or(i-l)%10<1:i=i**3%1699
    o+=str(i%10)
 print o

```

*The second level of indentation is with literal tab characters.*

Score breakdown:

```
presence:    0.0
fairness:    8.618
randomness:  31.502
no-repeat:   0.0
size:       -3.48
format:      1.0

```

The PRNG i'm using is a simplified version of Keith Randall's solution to the Diehard challenge, which despite its extreme brevity, passes all 15 tests. The solution is short notice: the absentee list is calculated on the day of, and all previous attendance is forgotten. The only thing which is recorded is who bought on the previous day, so that repetition may be avoided.

I suspect that the fairness score could be improved by keeping a queue of individuals who should have bought, but didn't, and adding them into the rotation as soon as possible. I'm not sure if this would lead to an overall improvement, though, due to a lower score for size.

About the randomness upper-bound, it is certainly higher than 32. Replacing line 7 with `i=i**3%1699` (removing the attendance and repetition constraints) results in a randomness score of `32.966`.

**Update:**
Most of the improvement comes from better zip compression, by renaming variables, and reusing constructs such as `for n in r` numerous times.

# Answer
> 2 votes
## GolfScript (36.656 points)

```
presence:    0
fairness:    9.498
randomness: 31.778
no-repeat:   0
size:       -5.62*
format:      1

```

* The Lempel-Ziv step is actually bad for this program: it would only be `5.46` (including the 9-character "penalty" from the Scala code) if strategy `HUFFMAN_ONLY` where used. (By my Huffman tree calculations, it should be 1839 bits, which suggests that there are 34 bytes of overhead - more than I remember from the last time I read the gzip file format spec, but my memory could be off).

```
'45274749890953461384092895296161282397696128454780712395638361237579450740141057012045098236468567830463395138297694808909654367173131250582012342078481734627820869476489062315253101230346792585956785940285674601914907495382306749019845658361271737890123953439852610678507814707530469358317402346278901984267190129362162512915678681507567831843423709082970928201432569730525454784512915686709218065814323413439817345681607567947860143456038712392671909236989193072045789650183645701325105856402426275'50/n*

```

# Answer
> 1 votes
### Scala (36.002 points)

Code (run in REPL):

```
val (p,d,s)=(0 to 9,0 to 499,Array.fill(10)(0d))
val h=p.map{i=>var s=42*(i*10+1);d.map{_=>s=(s*3877+29573)%139968;s>27993}}
val n=d.map{j=>h.count(_(j))}
var q=0
d.map{j=>val t=s.map(_+util.Random.nextGaussian);t(q)+=9;p.map{i=>if(h(i)(j))t(i)-=9};val k=t.indexWhere(_==t.min);q=k;s(k)+=0.3;k}.mkString.grouped(50).foreach(println)

```

Example output (for which score was calculated):

```
71756902145841391934765437292035652843760984098583
86397265015640974915628232730106147281529836713094
08565240287124932136398520876027407943071218763914
50987680167146425903575318020863656749795382985435
07941018246493815719641937560694585402820150738727
13126926431856275181072676938295301345412807480484
81839634956059251426350709373902682797204746548906
16175895303731651486209495295428383160620710851569
74013482373647246513814672019837413985207414790529
39206976935168020524260381937139452108673574826406

```

Score breakdown:

```
presence:    0
fairness:    9.094
randomness: 31.448
no-repeat:   0
size:       -5.54
format:      1

```

Short-notice: yes, here-list `h` is used on the day of selection only.

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