# Question
Title: Reaching one's lucky numbers in reputation
A new code-golfer, Joe, just registered to the site. He has 1 reputation but determined to reach all his lucky numbers in reputation exactly. Joe believes in higher powers which will help him to achieve his goal with minimal amount of (his or others) actions. As a new user he also believes that negative reputation is possible.

You should write a program or function which helps Joe to compute how many action should he expect.

## Details

* The actions can change the reputation by the following amounts (all actions are available at every step regardless of stackexchange rules):

```
answer accepted:     +15
answer voted up:     +10
question voted up:    +5
accepts answer:       +2
votes down an answer: −1
question voted down:  −2

```
* Other special reputation changes are disregarded.
* Lucky numbers can be negative and can be reached in any order.
* **Your solution has to solve any example test case under a minute** on my computer (I will only test close cases. I have a below-average PC.).

## Input

* Joe's lucky numbers as a list of integers in a common form of your language.

## Output

* The number of minimum actions needed as a single integer.
* Output could be printed to stdout or returned as an integer.

## Examples

Input =\> Output (Example reputation states)

```
1                     => 0  (1)
3 2 1                 => 2  (1 -> 3 -> 2)
2 10 50               => 7  (1 -> 3 -> 2 -> 12 -> 10 -> 25 -> 40 -> 50)
10 11 15              => 3  (1 -> 11 -> 10 -> 15)
42 -5                 => 7  (1 -> -1 -> -3 -> -5 -> 10 -> 25 -> 40 -> 42)
-10                   => 6  (1 -> -1 -> -3 -> -5 -> -7 -> -9 -> -10)
15 -65                => 39
7 2015 25 99          => 142
-99 576 42 1111 12345 => 885

```

This is code-golf so the shortest entry wins.

# Answer
> 1 votes
## C# - 501 Bytes

*Update* 551 -\> 501 Bytes

```
namespace System.Linq{class A {static void Main(){var i = c(new int[]{10,11,15});Console.WriteLine(i);Console.ReadLine();}private static int c(int[] a){var o=a.OrderBy(x => x).ToArray();int d=1,count=0;for(var i=0;i<a.Length;i++){if(o[i]==d)i++;int c=o[i],b=o.Length>=i+2?o[i+1]-o[i]:3;if(b<=2){i++;c=o[i];}while(d!=c){if(d>c){var e=d-c;if(e>1)d-=2;else d-=1;}else if(c>d){var e=c-d+2;if(e>14)d+=15;else if(e>9)d+=10;else if(e>4)d+=5;else if(e>2)d+=2;}count++;}if(b<=2){d-=b;count++;}}return count;}}}

```

## Ungolfed code

```
namespace System.Linq {
    class Program {
        static void Main(){
            var i = CalculateNumbers(new int[]{10,11,15});
            Console.WriteLine(i);
            Console.ReadLine();
        }
        private static int CalculateNumbers(int[] numbers){
            var ordered = numbers.OrderBy(x => x).ToArray();
            int cur = 1, count = 0;
            for (var i = 0; i < numbers.Length; i++){
                if (ordered[i] == cur) i++;
                int val = ordered[i], next = ordered.Length >= i+2 ? ordered[i + 1] - ordered[i] : 3;
                if (next <= 2){
                    i++;
                    val = ordered[i];
                }
                while (cur != val){
                    if (cur > val){
                        var dif = cur - val;
                        if (dif > 1)
                            cur -= 2;
                        else
                            cur -= 1;
                    } else if (val > cur){
                        var dif = val - cur + 2;
                        if (dif > 14)
                            cur += 15;
                        else if (dif > 9)
                            cur += 10;
                        else if (dif > 4)
                            cur += 5;
                        else if (dif > 2)
                            cur += 2;
                    }
                    count++;
                }
                if (next <= 2){
                    cur -= next;
                    count++;
                }
            }
            return count;
        }
    }
}

```

# Answer
> 16 votes
# Rust, ~~929~~ 923 characters

```
use std::io;use std::str::FromStr;static C:&'static [i32]=&[-2,-1,2,5,10,15];fn main(){let mut z=String::new();io::stdin().read_line(&mut z).unwrap();let n=(&z.trim()[..]).split(' ').map(|e|i32::from_str(e).unwrap()).collect::<Vec<i32>>();let l=*n.iter().min().unwrap();let x=n.iter().max().unwrap()-if l>1{1}else{l};let s=g(x as usize);println!("{}",p(1,n,&s));}fn g(x:usize)->Vec<i32>{let mut s=vec![std::i32::MAX-9;x];for c in C{if *c>0&&(*c as usize)<=x{s[(*c-1)as usize]=1;}}let mut i=1us;while i<x{let mut k=i+1;for c in C{if(i as i32)+*c<0{continue;}let j=((i as i32)+*c)as usize;if j<x&&s[j]>s[i]+1{s[j]=s[i]+1;if k>j{k=j;}}}i=k;}s}fn p(r:i32,n:Vec<i32>,s:&Vec<i32>)->i32{if n.len()==1{h(r,n[0],&s)}else{(0..n.len()).map(|i|{let mut m=n.clone();let q=m.remove(i);p(q,m,&s)+h(r,q,&s)}).min().unwrap()}}fn h(a:i32,b:i32,s:&Vec<i32>)->i32{if a==b{0}else if a>b{((a-b)as f32/2f32).ceil()as i32}else{s[(b-a-1)as usize]}}

```

This was fun!

---

## Commentary on the implementation

So I'm obviously not too happy with the size. But Rust is absolutely terrible at golfing anyway. The performance, however, is wonderful.

The code solves each of the test cases correctly in a near-instantaneous amount of time, so performance is obviously not an issue. For fun, here's a much more difficult test case:

```
1234567 123456 12345 1234 123 777777 77777 7777 777

```

for which the answer is `82317`, which my program was able to solve on my (medium-performance) laptop in **1.66 seconds** (!), even with the recursive brute-force Hamiltonian path algorithm.

## Observations

* First we should build a modified weighted graph, with the nodes being each "lucky" number and the weights being how many changes it takes to get from one reputation level to another. Each pair of nodes must be connected by *two* edges, since going up is not the same as going down in reputation value (you can get +10, for example, but not -10).
* Now we need to figure out how to find the minimum amount of changes from one rep value to another.

+ For getting from a higher value to a lower value, it's simple: just take `ceil((a - b) / 2)` where `a` is the higher value and `b` is the lower value. Our only logical option is to use the -2 as much as possible, and then the -1 once if necessary.
    + A low to high value is a bit more complicated, since using the greatest possible value is not always optimal (ex. for 0 to 9, the optimal solution is +10 -1). However, this is a textbook dynamic programming problem, and simple DP is enough to solve it.
* Once we have calculated the minimum changes from each number to every other number, we are essentially left with a slight variant of TSP (travelling salesman problem). Luckily, there are a small enough number of nodes (a maximum of 5 in the hardest test case) that brute force is sufficient for this step.

## Ungolfed code (heavily commented)

```
use std::io;
use std::str::FromStr;

// all possible rep changes
static CHANGES: &'static [i32] = &[-2, -1, 2, 5, 10, 15];

fn main() {
    // read line of input, convert to i32 vec
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let nums = (&input.trim()[..]).split(' ').map(|x| i32::from_str(x).unwrap())
        .collect::<Vec<i32>>();

    // we only need to generate as many additive solutions as max(nums) - min(nums)
    // but if one of our targets isn't 1, this will return a too-low value.
    // fortunately, this is easy to fix as a little hack
    let min = *nums.iter().min().unwrap();
    let count = nums.iter().max().unwrap() - if min > 1 { 1 } else { min };
    let solutions = generate_solutions(count as usize);

    // bruteforce!
    println!("{}", shortest_path(1, nums, &solutions));
}

fn generate_solutions(count: usize) -> Vec<i32> {
    let mut solutions = vec![std::i32::MAX - 9; count];

    // base cases
    for c in CHANGES {
        if *c > 0 && (*c as usize) <= count {
            solutions[(*c-1) as usize] = 1;
        }
    }

    // dynamic programming! \o/
    // ok so here's how the algorithm works.
    // we go through the array from start to finish, and update the array
    //   elements at i-2, i-1, i+2, i+5, ... if solutions[i]+1 is less than
    //   (the corresponding index to update)'s current value
    // however, note that we might also have to update a value at a lower index
    //   than i (-2 and -1)
    // in that case, we will have to go back that many spaces so we can be sure
    //   to update *everything*.
    // so for simplicity, we just set the new index to be the lowest changed
    //   value (and increment it if there were none changed).
    let mut i = 1us;  // (the minimum positive value in CHANGES) - 1 (ugly hardcoding)
    while i < count {
        let mut i2 = i+1;
        // update all rep-values reachable in 1 "change" from this rep-value,
        //   by setting them to (this value + 1), IF AND ONLY IF the current
        //   value is less optimal than the new value
        for c in CHANGES {
            if (i as i32) + *c < 0 { continue; }  // negative index = bad
            let idx = ((i as i32) + *c) as usize;  // the index to update
            if idx < count && solutions[idx] > solutions[i]+1 {
                // it's a better solution! :D
                solutions[idx] = solutions[i]+1;
                // if the index from which we'll start updating next is too low,
                //   we need to make sure the thing we just updated is going to,
                //   in turn, update other things from itself (tl;dr: DP)
                if i2 > idx { i2 = idx; }
            }
        }
        i = i2;  // update index (note that i2 is i+1 by default)
    }

    solutions
}

fn shortest_path(rep: i32, nums: Vec<i32>, solutions: &Vec<i32>) -> i32 {
    // mercifully, all the test cases are small enough so as to not require
    //   a full-blown optimized traveling salesman implementation
    // recursive brute force ftw! \o/
    if nums.len() == 1 { count_changes(rep, nums[0], &solutions) }  // base case
    else {
        // try going from 'rep' to each item in 'nums'
        (0..nums.len()).map(|i| {
            // grab the new rep value out of the vec...
            let mut nums2 = nums.clone();
            let new_rep = nums2.remove(i);
            // and map it to the shortest path if we use that value as our next target
            shortest_path(new_rep, nums2, &solutions) + count_changes(rep, new_rep, &solutions)
        }).min().unwrap()  // return the minimum-length path
    }
}

fn count_changes(start: i32, finish: i32, solutions: &Vec<i32>) -> i32 {
    // count the number of changes required to get from 'start' rep to 'finish' rep
    // obvious:
    if start == finish { 0 }
    // fairly intuitive (2f32 is just 2.0):
    else if start > finish { ((start - finish) as f32 / 2f32).ceil() as i32 }
    // use the pregenerated lookup table for these:
    else /* if finish > start */ { solutions[(finish - start - 1) as usize] }
}

```

# Answer
> 0 votes
# C++ - 863 bytes, ungolfed

This runs fairly fast, in the same ballpark as the solution written in Rust (about 6 times as fast when compiling with optimisation turned on). I will golf this later this evening (evening in Sweden, that is).

```
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

const int lookup[] = {0, 2, 1, 2, 2, 1, 3, 2, 2, 2, 1, 3, 2, 2, 2};

int distance(int start, int end) {
    return start > end
        ? (start - end + 1) / 2
        : (end - start) / 15 + lookup[(end - start) % 15];
}

int walk(int current, std::vector<int> points) {
    int min = 0;

    if (points.size() == 0) return 0;

    for (int i = 0; i < points.size(); i++) {
        std::vector<int> new_points = points;
        new_points.erase(new_points.begin() + i);

        int d = distance(current, points[i]) + walk(points[i], new_points);

        min = min && min < d ? min : d;
    }

    return min;
}

int main() {
    std::vector<int> points;

    std::string line;
    std::getline(std::cin, line);

    std::stringstream ss(line);
    int i;

    while (ss >> i)
        points.push_back(i);

    std::cout << walk(1, points) << std::endl;

    return 0;
}

```

---
Tags: code-golf, sequence, restricted-time
---


title: Y-Wing Strategy for Sudoku

text:
# Question
Title: Y-Wing Strategy for Sudoku
I recently got a new Sudoku app that produces really hard Sudoku's, which can't be solved using the standard strategies. So I had to learn a few new ones. One of these strategies is the **Y-Wing Strategy**. It is ranked under "Tough Strategies", but it is actually not that hard.

# Example

For this strategy only 4 cells are important. Therefore I ignored all other cells in the images.

We look at all candidates for each cell. In the following example we have a cell with the candidates `3 7` (that means we have already rejected the candidates `1 2 4 5 6 8 9`, for instance because there is a `1` in the same row, a `2` in the same 3x3 box, ...), a cell with the candidates `6 7`, a cell with the candidates `3 6` and a cell with the candidates `2 6`. The Y-Wing strategy will suggest, that the `6` can be removed from the candidates of the downright cell, leaving only a `2` as candidate, which you can fill in. So we found a correct number and are one step closer in solving the full Sudoku.

Why can the `6` be removed?

## Explanation

Let us assume that the `6` is the correct number for the downright cell. Now there is a `6` in this column, therefore we can remove the `6` from the candidates of the top right cell, leaving only a `7`, which we can fill in. The same happens with the down left cell. We can remove the `6` and fill in the `3`. Now if we look at the top left cell we get a contradiction. Because now there's already a `7` in the same row and a `3` in the same column, so we can remove the `7` and the `3` of the candidates, leaving no candidates at all. Which is clearly not possible. Therefore the 6 cannot be the correct number of the downright cell.

More precisely: If we have 4 cells with the candidates `[A B] [A C] [C D] [B C]` (in this order or circular rotated) and the cells are connected (via same row, same column or same 3x3 box) in a circle (Cell 1 is connected to Cell 2, which is connected to Cell 3, which is connected to Cell 4, which is connected to Cell 1), than you can remove `C` from the `[C D]` cell. It is crucial, that the three cells `[A B]`, `[A C]` and `[B C]` only contain two candidates each. Differently the cell `[C D]`, which may contain more or less (`D` can be zero, one or even more candidates).

Notice that I explicitly said they can be connected either way. In the next example you can see the strategy applied again. But this time the 4 cells doesn't form a rectangle. The down left and downright cells are simply connected, because they are in the same 3x3 box. Y-Wing says, that we can remove the `1` as candidate of the top left cell. This time there are still 2 candidates in this cell left, so we didn't actually found a new correct number. But nevertheless the removal of the `1` can open doors to different strategies.

If you want more information about the strategy or want a few more examples, visit sudokuwiki.org.

## Challenge Specifications

You will receive 4 lists as input, representing the candidates of the cells. The four cells are connected like a circle (Cell 1 is connected to Cell 2, which is connected to Cell 3, which is connected to Cell 4, which is connected to Cell 1). You can assume that each list is sorted in ascending order.

Your job is to remove one candidate (by applying the Y-Wing strategy) and returning the resulting candidates lists in the same order. If you can't apply the strategy, just return the same candidates lists.

If there are two possible solutions (you could remove A of cell B or remove C of cell D), than return only one solution. It doesn't matter which one.

The input can be in any native list or array format. You could also use a list of lists or something similar. You can receive the input via STDIN, command-line argument, prompt or function argument and return the output via return value or simply by printing to STDOUT.

This is code-golf. The shortest code (in bytes) wins.

## Test Cases

```
[3 7] [6 7] [2 6] [3 6]       => [3 7] [6 7] [2] [3 6]   # Example 1
[6 7] [2 6] [3 6] [3 7]       => [6 7] [2] [3 6] [3 7]   # Example 1, different order
[2 6] [3 6] [3 7] [6 7]       => [2] [3 6] [3 7] [6 7]   # Example 1, different order
[3 6] [3 7] [6 7] [2 6]       => [3 6] [3 7] [6 7] [2]   # Example 1, different order
[1 2 8] [1 8] [8 9] [1 9]     => [2 8] [1 8] [8 9] [1 9] # Example 2
[3 8] [4 8] [3 4 8] [3 4]     => [3 8] [4 8] [3 8] [3 4]
[1 3 6 7 8] [3 8] [3 4] [4 8] => [1 3 6 7] [3 8] [3 4] [4 8]
[7 8] [7 8] [4 7] [4 8]       => [7 8] [8] [4 7] [4 8] or [7] [7 8] [4 7] [4 8]
[4 7] [7 8] [4 8] [4]         => [4 7] [7 8] [4 8] []    # Fictional example
[3 7] [2 6] [6 7] [3 6]       => [3 7] [2 6] [6 7] [3 6] # Y-Wing can't be applied here
[4 7] [2 7 8] [4 8] [1 4]     => [4 7] [2 7 8] [4 8] [1 4] # -||-

```

# Answer
# CJam, 90 bytes

Ugghhh, this is too long because of the constraint that the other 3 cells should have only 2 candidates.

```
l~_:_(a+2/::&_{,}$2>:&:Y;{:PY&Y{P1<}?~}%:X,3>1${,}$W=_,2>\Y&,1?*{X:_(+2/{~:I=}#)_2$=I-t}&p

```

This expects input as a list of list in CJam format. For ex.:

```
[[2 6] [3 6] [3 7] [6 7]]

```

gives output in a CJam list of list format:

```
[[2] [3 6] [3 7] [6 7]]

```

Will add explanation once I am done golfing..

Try it online here or try the whole test suite here.
> 3 votes

# Answer
# Mathematica, ~~124~~ 110 bytes

```
Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])&

```

**Examples:**

```
In[1]:= yWing = Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])& ;

In[2]:= yWing[{{3, 7}, {6, 7}, {2, 6}, {3, 6}}]

Out[2]= {{3, 7}, {6, 7}, {2}, {3, 6}}

In[3]:= yWing[{{4, 7}, {7, 8}, {4, 8}, {4}}]

Out[3]= {{4, 7}, {7, 8}, {4, 8}, {}}

```
> 3 votes

---
Tags: code-golf, sudoku
---


title: Rock Around the Clock

text:
# Question
Title: Rock Around the Clock
In as few Unicode characters as possible, print the following (144 characters):

```
1, 2, 3 o'clock, 4 o'clock rock,
5, 6, 7 o'clock, 8 o'clock rock,
9, 10, 11 o'clock, 12 o'clock rock,
We're gonna rock around the clock tonight.

```

You must not use any numbers in your code, except the digit `1`.

# Answer
## Javascript - 140 132

```
k=1,s=", ",t=" o'clock",x="";while(k<11)x+=k+++s+k+++s+k+++t+s+k+++t+" rock,\n";alert(x+"We're gonna rock around the clock tonight.")

```

The fact, that 11 is made out of two 1's let me pass the rules I guess.

### Explanation

The k+++s is equal to (k++)+s, so it adds k first to x, then increments k and then it adds s to x. This process will be done three times before it adds the last sentence.
> 48 votes

# Answer
## C# - 186

Best golf language or best golf language?

```
class P{static void Main(){var s="";for(int i=1;i<11;)s+=i+++", "+i+++", "+i+++" o'clock, "+i+++" o'clock rock,\n";System.Console.Write(s+"We're gonna rock around the clock tonight.");}}

```
> 37 votes

# Answer
# Brainfuck (1574)

Not a serious submission, but follows the rules.

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

```

Can be tested here.
> 27 votes

# Answer
# Ruby, 100

```
printf"%i, %i#{", %i o'clock"*r=-~1} rock,
"*-~r+"We're gonna rock around the clock tonight.",*1..$$

```
> 23 votes

# Answer
# Perl 123

```
$s="*, *, * o'(, * o'( ),";print"$s
$s
$s
We're gonna ) around the ( tonight."=~s![(*)]!(clock,rock)[1+1+1&ord$&]||++$i!reg

```

The regular expression matches `(`, `)` and `*`. I used the fact that the ASCII code of `(` is 40, of `)` is 41 and `*` is 42.

The `r` flag of the regular expression enables "in place substitution" and the `e` flag enables code evaluation (similar to `x.replace(/.../, function(m){...})` in JavaScript).

`(clock,rock)` is an array of two "bare words". `$&` is the current match of the regular expression and `ord$&` is it's ASCII value.

Masked by 3 or `1+1+1` the ASCII values are now 0, 1 and 2, so I can use them to retrieve the corresponding array element. As 2 is out of the array, the "short circuit" operator `||` evaluates `++$i`. In the first match `$i` is `undef` so incrementing it I get 1, then 2 and so on...

In simple words. This replaces `*` with it's current occurrence, `(` with "clock" and `)` with "rock".
> 18 votes

# Answer
# Bash+coreutils, 120 ASCII, 92 Unicode

### ASCII:

```
c=clock
f(){ echo $[++i], $[++i], $[++i] o\'$c, $[++i] o\'$c rock,;}
f
f
f
echo We\'re gonna rock around the $c tonight.

```

### Unicode:

```
iconv -t unicode<<<挊挽潬正昻⤨⁻捥潨␠⭛椫ⱝ␠⭛椫ⱝ␠⭛椫⁝屯␧Ᵽ␠⭛椫⁝屯␧潲正㬬㭽㭦㭦㭦捥潨圠履爧潧湮潲正愠潲湵桴挤琠湯杩瑨ਮ|sed 1d|bash

```

### base64 encoded Unicode version (in case unicode renderings get messed up):

```
aWNvbnYgLXQgdW5pY29kZTw8POaMiuaMvea9rOato+aYiuKkqOKBu+aNpea9qOKQoOKtm+akq+Kx
neKQoOKtm+akq+KxneKQoOKtm+akq+KBneWxr+KQp+Kxo+KQoOKtm+akq+KBneWxr+KQp+KBo+a9
suato+OsrOCpveCppuCppuCppuaNpea9qOWcoOWxpeeIp+KBpea9p+a5ruKBoea9suato+aEoOa9
sua5teKBpOahtOKBpeaMpOeQoOa5r+adqeeRqOCornxzZWQgMWR8YmFzaAo=

```
> 16 votes

# Answer
# Brainfuck, 1299

***Bleuuuurgh***. That was terrible. I don't know why I did this, it seemed quite easy at the start. First and probably last Brainfuck script. Try it here.

With some help from an automated code generator, I was able to write a script which reused most of the characters instead of generating each one from scratch. It's only 275 characters shorter than the one automatically generated, posted here.

The output isn't newline-terminated.

I might put a bit of explanation in later on. Essentially, any long line which isn't something like `>>>>>>>` or `<<<<<<<` or `>>.>>.>>.>>.` generates a character or a series of them.

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

```
> 13 votes

# Answer
# Lua - ~~217~~ ~~164~~ ~~154~~ ~~151~~ ~~149~~ 143

Modified the old one to use a loop instead, saves a boat-load of characters. Thanks to TeunPronk for helping me shave off another 10 characters and to WilliamBarbosa for shaving off another 3 characters. 2 more characters can be saved by using the variable `k`. 6 more characters are saved by eliminating the variable `r=" rock,"` since it is used once.

```
o=" o'clock"c=", "w=io.write k=1+1 for i=1,11,k+k do w(i,c,i+1,c,i+k,o,c,i+k+1,o," rock,\n")end w("We're gonna rock around the clock tonight.")

```

Ungolfed,

```
o=" o'clock"
c=", "
w=io.write
k=1+1
for i=1,11,k+k do
   w(i,c,i+1,c,i+k,o,c,i+k+1,o," rock,\n")
end
w("We're gonna rock around the clock tonight.")

```
> 10 votes

# Answer
# CJam - 90 ASCII / 54 Unicode

ASCII:

```
{{T):T}:F~", ":CFCF" o'clock":OCFO" rock,
"}Z*"We're gonna rock around the clock tonight."

```

Unicode:

```
"ξ漰㠬༳ᆧᶃ㸩씪咦⏚騤䖫퍃᰽薂ᴤਥ궋씻㱗㽫Ƶꐥ勋䎔䃱魠ꝯ朐酠礢璿狮꓈执낦덋觫ᥛ琚"GZ)#bBC*b:c~

```

Try them at http://cjam.aditsu.net/
> 8 votes

# Answer
# Python (123)

```
print((1+1+1)*"%i, %i, %i o'clock, %i o'clock rock,\n"%tuple(range(1,11+1+1))+"We're gonna rock around the clock tonight.")

```

# PYG (112)

```
P((1+1+1)*"%i, %i, %i o'clock, %i o'clock rock,\n"%T(R(1,11+1+1))+"We're gonna rock around the clock tonight.")

```
> 8 votes

# Answer
# Brainfuck - 680

test it here: ideone.com/Wi9ftB

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

```

as i promised, here's a better version. my brain feels like.. ooh so that's where the name comes from.

**explanation:** (because it is unmaintainable and i don't want to forget how it works)

firstly you have to choose the best data layout for this challenge. i came up with

`-4 outmost loop` `-3 newline char` `-2 space` `-1 numbers` `1 lowercase #1` `2 lowercase #2` `3 comma, apostrophe, period` `4 condition (outmost loop < 3)` `5 inner loop` `6 second inner loop`

We have to belive this is optimal unless there will be too many shifts (which case you have to rearrange the layout)

After that I used a 4x9x3 loop to set the starting values for newline, number, the two lowercase letter and the comma. (all the smaller ascii codes got 4x9=36 and the two lowercase letter got 4x9x3=108, then I added and substracted some to get their real value)

When the preset is done, the code enters the outmost loop that cycles 3 times. I explain it by pseudocode.

```
for 3 to 1 where i = numbers
    print '++i, '
    while inner_loop != 0              # this is true after the first loop
        while second_inner_loop != 0   # and this is true after the second
            print '10, 11 o'clock, 12' # prints the difference
            condition = 0              # it prevents the printing below
        second_inner_loop += 1
    inner_loop += 1
    while condition != 0
        print '++i, ++i o'clock, ++i'
    print ' o'clock rock,\n'

```

When this section is done I just have to print the last line. But we have an uppercase W that must be produced without using too many characters. At this point we are here:

```
Address  Value  Pointer
     -4      0  <--
     -3     10
     -2     32
     -1     50
      1     99
      2    111
      3     44

```

so I put \[-3\] 4 times to \[-1\] and substract 3 to get 87 (W): `>[>>++++<<-]>>---.`
then erase it `[-]`
and move \[-2\] to this location \[-1\] so space will be close to the lowercase letters. `<[>+<-]`

After that it just prints the letters. lowercase #1 is for the lower part 97-107 and lowercase #2 is for the above region.
> 7 votes

# Answer
## JavaScript, ~~111~~ 107 chars, without using any number.

Execute these snippets in your browser's JS console:

107 (inspired by http://xem.github.io/obfuscatweet/ plus the other JS answer):

```
eval(unescape(escape('').replace(/uD./g,'')))

```

111 (just packing all the string and removing the eval around):

```
unescape(escape('').replace(/uD./g,''))

```
> 6 votes

# Answer
# PHP - 125 129

**Version 1 (129)**

```
$i;while($i<11)echo++$i.", ".++$i.", ".++$i." o'clock, ".++$i." o'clock rock,\n";echo"We're gonna rock around the clock tonight";

```

**Version 2 (125)**

```
while($i++<11)echo"$i, ".++$i.", ".++$i." o'clock, ".++$i." o'clock rock,\n";echo"We're gonna rock around the clock tonight";

```

Clean version:

```
while($i++<11)
    echo "$i, ".++$i.", ".++$i." o'clock, ".++$i." o'clock rock,\n";
echo "We're gonna rock around the clock tonight";

```
> 5 votes

# Answer
# C - 145 - try me

```
main(i){i<11?main(i-~1+1,printf("%d, %d, %d o'clock, %d o'clock rock,\n"
,i++,i,i-~1,i-~1+1)):puts("We're gonna rock around the clock tonight.");}

```

# C - 172 - try me

```
#define l ,__LINE__+~1
#define f ;printf("%d, %d, %d o'clock, %d o'clock rock,\n"
main(){f l
l
l
l)f
l
l
l
l)f
l
l
l
l);puts("We're gonna rock around the clock tonight.");}

```
> 5 votes

# Answer
# Perl, 114 111 110 108

```
$s=", X o'clock";$_="X, X$s$s rock,
"x(1+1+1)."We're gonna rock around the clock tonight.";s/X/++$i/eg;print

```

110:

```
$s=", X o'clock";print(("X, X$s$s rock,
"x(1+1+1)."We're gonna rock around the clock tonight.")=~s/X/++$i/egr)

```

111:

```
print(("X, X, X o'clock, X o'clock rock,
"x(1+1+1)."We're gonna rock around the clock tonight.")=~s/X/++$i/egr)

```

114:

```
($s="X, X, X o'clock, X o'clock rock,
"x(1+1+1)."We're gonna rock around the clock tonight.")=~s/X/++$i/ge;print$s

```
> 5 votes

# Answer
## C++ 261 203

```
#include<iostream>
#define x i++;
#define y std::cout<<
#define z y x y
void m(){for(int i=1;i<11;){z", ";z", ";z" o'clock, ";z" o'clock rock, "<<"\n";}y"We're gonna rock around the clock tonight.";}

```

Edited my first attempt; it worked when I first tested it, but that seems to be a fluke; post-increment in a stream is "undefined behaviour", and it did weird things (including blue screening Windows 7!) when I tried re-running it. I think that using printf instead of std::cout could be used with post-increment to get a shorter program.

Edited again, got it down to 231 by re-implementing the loop. Edited yet again, now down to 203...those #defines weren't all useful in the looping version.

For those wondering how C++ can run a function "m", the entry point can be defined as any function with just a compiler option, as can setting all funcs to be stdcall; I used both switches when compiling the above. If you don't like the redefined entry point, add 3 to my character count.
> 4 votes

# Answer
# Swift - ~~136~~  134

```
var x=1
for;x<11;{print("\(x++), \(x++), \(x++) o'clock, \(x++) o'clock rock,\n")}
print("We're gonna rock around the clock tonight.")

```
> 4 votes

# Answer
## Befunge-98 (~~402~~ 268)

Now a unefunge!

```
".thginot kcolc eht dnuora kcor annog er'eW"a11+/a*1-> #;:,1+" ,",,:,1+" ,",,:,1+" ,kcolc'o "a1-k,:,1+a",kcor kcolc'o "ek,:a11+/a*b1111+++-+-#;_:,a-1+" ,",,:a111++-:*,,1+" ,",,:a111++-:*,,1+" ,kcolc'o "a1-k,:a111++-:*,,1+a",kcor kcolc'o "ek,:a11+/a*b1111+++-+$$$aa*k,@

```
> 3 votes

# Answer
## Java, 228

A hardcoded solution would have probably been shorter.

```
public static void main(String[] a){
        String s = "";
        int i=1,j=1;
        for(i--,j--;i<=11;){
            s += ++i + (j > 1 ? " o'clock rock, ":", ");
            if(j == "one".length()){
                j -= j;
                s +="\n";
            }else
                j++;
        }
        System.out.println(s+"We're gonna rock around the clock tonight");
}

```
> 3 votes

# Answer
## Groovy - 140 139 chars

Golfed, influenced by William Barbosa's answer:

```
s="ock"
i=1
f={->println "${i++}, ${i++}, ${i++} o'cl$s, ${i++} o'cl$s r$s,"}
f();f();f()
println "We're gonna r$s around the cl$s tonight"

```

Ungolfed:

```
s = "ock"
i = 1
f = { ->
    println "${i++}, ${i++}, ${i++} o'cl$s, ${i++} o'cl$s r$s,"}
}

f();f();f()

println "We're gonna r$s around the clock tonight"

```
> 3 votes

# Answer
# Mathematica - 153

```
i=1;
StringReplace[
  StringJoin[
    Riffle[{s="X, X, X o'clock, X o'clock rock,",s,s},"\n"]]<>
    "\nWe're gonna rock around the clock tonight.","X":>ToString[i++]]

```
> 2 votes

# Answer
## C++ 252

```
#define P(x) cout<<x
#define Q cout<<", "
#define N cout<<endl
#define C P(" o'clock")
#define R P(" rock")
#define F P(++i);Q;P(++i);Q;P(++i);C;Q;P(++i);C;R;N;
int i;
main()
{
    F F F
    P("We're gonna rock around the clock tonight.");
}

```
> 2 votes

# Answer
## PowerShell, ~~123~~ ~~118~~ 109

```
1,1,1|%{"$('',''," o'clock"," o'clock rock"|%{"$((++$a))$_,"})"}
"We're gonna rock around the clock tonight."

```

After a horrible start (167) I got rid of a few idioms I didn't even need and at least got it shorter than the reference.
> 2 votes

# Answer
## Java (v2) - 250 241 232 chars

This is a complete running program, influenced by William Barbosa's answer.

Golfed:

```
public class R{
static int o=1;
static String c(){return o+++", "+o+++", "+o+++" o'clock, "+o+++" o'clock rock,\n";}
public static void main (String[] a){System.out.println(c()+c()+c()+"We're gonna rock around the clock tonight");}}

```

Ungolfed:

```
public class R {
    static int o = 1;
    static String c() {
        return o+++", "+o+++", "+o+++" o'clock, "+o+++" o'clock rock,\n";
    }

    public static void main (String[] a) {
        System.out.println(c()+c()+c()+"We're gonna rock around the clock tonight");
    }
}

```
> 2 votes

# Answer
# Cobra - 193

```
class P
    var i=1-1
    def main
        print[.f,.f,.f,"We're gonna rock around the clock tonight."].join("")
    def f as String
        return"[[.i+=1,.i+=1,.i+=1].join(", ")] o'clock, [.i+=1] o'clock rock,\n"

```
> 2 votes

# Answer
# ECMAScript6 - ~~136~~ 135

Doesn't even use the allowed `1` digit:

```
alert([,...a=[s=", ",s,(c=" o'clock")+s,c+" rock,\n"],...a,...a].map((x,i)=>i+x).join("")+"We're gonna rock around the clock tonight.")

```

Tested in Firefox console.
> 2 votes

# Answer
# Golflua -125

Basically a direct translation of my Lua solution:

```
k=1+1o=" o'clock"c=", "~@i=1,11,k+k I.w(i,c,i+1,c,i+k,o,c,i+k+1,o," rock,\n")$w("We're gonna rock around the clock tonight.")

```
> 2 votes

# Answer
## Haskell -- ~~138~~ 137 chars

As a standalone program:

```
r n=show n++s!!n
s=" o'clock rock,\n":c:c:" o'clock, ":s
c=", "
main=putStr$(r=<<)[1..11+1]++"We're gonna rock around the clock tonight."

```

Edit: I used to have a helper function o used to define s by

```
s=o" rock,\n":c:c:o c:s;o=(" o'clock"++)

```

but it turns out to cost 1 extra character. Is there any way to compress all of the "o'clock"s / "rock"s / "ock"s?
> 2 votes

# Answer
## JavaScript, 140

```
a=", x o'clock",b="x, x"+a+a+" rock,\n",b+=b+=b+"We're gonna rock around the clock
tonight.";for(i=1;i<=11+1;)b=b.replace("x",i++);alert(b)

```

I make a string like "x, x, x o'clock x o'clock rock,\n..." Then I replace the "x's" with numbers.
> 2 votes

# Answer
## PHP 258 220 only with Manatwork's help

EDIT: Thank you manatwork, again you did stuff there I didn't know you could do. Thanks!

```
<?php $a='clock';$b=" o'";$c="$b$a rock,";$d=1+1;$e=$d+$d;$f=", ";$g=$e+$e;echo"1$f$d$f",$d+1,"$b$a$f$e$c
",$e+1,$f,$e+$d,$f,$g-1,"$b$a$f$g$c
",$g+1,$f,$g+$d,$f,"11$b$a$f","1$d$c
We're gonna rock around the clock tonight.";

```

I must admit I thought this was going to be quite a dull question but it turned out to be quite fun. I thought I might have a chance with this one in php. Sadly not to be :-(

Edit: Actually it might not be PHP at fault, just that I need to learn more and do a bit practice at code golf - it is actually my own fault :-)

I enjoyed trying anyway.

Original 258 chars:

```
<?php $a='clock';$b=" o'";$c=$b.$a." rock,";$d=1+1;$e=$d+$d;$f=", ";$g=$e+$e;echo"1".$f.$d.$f.($d+1).$b.$a.$f.$e.$c."
".($e+1).$f.($e+$d).$f.($g-1).$b.$a.$f.($g).$c."
".($g+1).$f.($g+$d).$f."11".$b.$a.$f."1".$d.$c."
We're gonna rock around the clock tonight.";?>

```
> 1 votes

# Answer
# PowerShell, ~~156~~ ~~140~~ ~~136~~ ~~129~~ 127

```
for($i=1;$i-lt11){$i++,$i++,"$(($i++)) o'clock","$(($i++)) o'clock rock,"-join', '}"We're gonna rock around the clock tonight."

```

Ungolfed:

```
for($i = 1; $i -lt 11){
    $i++, $i++ , "$(($i++)) o'clock", "$(($i++)) o'clock rock," -join ', '
}
"We're gonna rock around the clock tonight."

```
> 1 votes

# Answer
# PHP 150

No numbers, including the 11 which would not be two 1's stuck together, but the number value eleven.

```
function f(){static $i;echo++$i.", ".++$i.", ".++$i." o'clock, ".++$i." o'clock rock,\n";}f();f();f();echo"We're gonna rock around the clock tonight";

```
> 1 votes

# Answer
## AWK, 164 139

Boring, but my first AWK golf attempt.

```
BEGIN{OFS=", "
k=" o'clock "
r="rock"
print ++t,++t,++t k,++t k r,"\n"++t,++t,++t k,++t k r,"\n"++t,++t,++t k,++t k r",\nWe're gonna "r" around the clock tonight."}

```

`OFS` comes in handy here.

Shorter version:

```
func p(){print ++t,++t,++t k,++t k r OFS}BEGIN{OFS=", "
k=" o'clock"
r=" rock"
p()
p()
p()
print"We're gonna"r" around the clock tonight."}

```
> 1 votes

# Answer
## Haskell -- 155/141 147/133 chars

147 characters as a program:

```
main=putStrLn.(++"We're gonna rock around the clock tonight.").concat.zipWith((++).show)[1..11+1].cycle$[", ",", "," o'clock, "," o'clock rock,\n"]

```

133 characters as `String` expression:

```
(++"We're gonna rock around the clock tonight.").concat.zipWith((++).show)[1..11+1].cycle$[", ",", "," o'clock, "," o'clock rock,\n"]

```
> 1 votes

# Answer
# MATLAB, 199 192 182

```
f=1+1+1+1;a=[1,1+1,f-1,f];b=' o''clock';c=' rock';
for i=1:f-1;fprintf('%g, %g, %g,%s, %g%s%s,\n',a(1:f-1),b,a(f),b,c);a=a+f;end
fprintf('We''re gonna%s around the clock tonight.',c)

```
> 1 votes

# Answer
# Scala, 156

```
for(i<-1 to 11 by 1+1+1+1){println(i+", "+(i+1)+", "+(i+1+1)+" o'clock, "+(i+1+1+1)+" o'clock rock,")};println("We're gonna rock around the clock tonight.")

```
> 1 votes

# Answer
## Python 3, 100 99 Unicode

Using Unicode:

```
t=1+1;eval('瀠楲瑮㌨⠪┢Ⱪ┠≩㈫∪椥漠挧潬正⬢•潲正尬≮┩畴汰⡥慲杮⡥ⰱ㌱⤩∫敗爧潧湮潲正愠潲湵桴汣捯潴楮桧⹴⤢'.encode('utf%i'%(t*t<<t))[t:])

```

Encodes that string as UTF-16, dropping the first 2 bytes, resulting in:

```
 print(3*("%i, %i"+2*", %i o'clock"+" rock,\n")%tuple(range(1,13))+"We're gonna rock around the clock tonight.")

```

Note the initial space to make an even number of ASCII characters.

Checked if there were any illegal digits in there, such as from other languages, looks like I'm safe:

```
>>> set(c for c in """<code>""" if unicodedata.category(c)[0] == 'N')
{'1'}

```
> 1 votes

# Answer
# ECMAScript: 127 characters

```
i=1;alert("%, %, % o'clock, % o'clock rock,\n".repeat(1+1+1).replace(/%/g,x=>i++)+"We're gonna rock around the clock tonight.")

```

Just to promote some ECMAScript 6 features.
> 1 votes

# Answer
## Clojure - 261 244 178 176 chars

I'm a newbie to Clojure... suggestions welcome.

Golfed:

```
(let[i(atom(dec 1))](defn f[](swap! i inc))(defn p[](printf "%d, %d, %d o'clock, %d o'clock rock,\n"(f)(f)(f)(f)))(p)(p)(p)(print"We're gonna rock around the clock tonight."))

```

Ungolfed:

```
(let [i (atom (dec 1))]
  (defn f [] (swap! i inc) )
  (defn p [] (printf "%d, %d, %d o'clock, %d o'clock rock,\n" (f)(f)(f)(f)) )
  (p)(p)(p)
  (print "We're gonna rock around the clock tonight.")
)

```
> 1 votes

# Answer
## Delphi, 186

Ungolfed:

```
var c:int32;

function i:int32;
begin
  c:=c+1;
  i:=c;
end;

begin
  while c<11 do
    writeln(i,', ',i,', ',i,' o''clock, ',i,' o''clock rock,');
  write('We''re gonna rock around the clock tonight.');
end.

```

Golfed:

```
var c:int32;function i:int32;begin c:=c+1;i:=c;end;begin while c<11do writeln(i,', ',i,', ',i,' o''clock, ',i,' o''clock rock,');write('We''re gonna rock around the clock tonight.')end.

```
> 1 votes

# Answer
# Rebmu, 117 chars

```
O{ o'}C{clock}R{rock}S{, }T1 Ndz[igTad11 1[p[{We're going to}r{around the}c{tonight.}]qt]++T]fv[pCB[nSnSnOcSnOcSPrS]]

```

Un-"mushed":

```
o: " o'" c: "clock" r: "rock" s: ", " t: 1 n: dz [ig t ad 11 1 [p ["We're going to" r "around the" c "tonight."] qt] ++ t] fv [p cb [n s n s n o c s n o c sp r s]]

```

Commented:

```
; Define some string constants
o: { o'}
c: {clock}
r: {rock}
s: {, }

t: 1 ; assign one to T

; define a function with no arguments N (N does "DZ" the following)
n: dz [
    ; if T is greater than adding 11 to 1 (IG = If Greater, AD = Add),
    ; print the final message and then quit
    ig t ad 11 1 [
        p [{We're going to} r {around the} c {tonight.}] qt
    ]

    ; increment t but return its old value
    ++ t
]

; loop forever (will be exited by a quit during an invocation of N
; once it gets bigger than 12)
fv [
    ; print the result of combining (CB = Combine) the progressively
    ; increased values with the defined strings (also, SP = space)
    p cb [n s n s n o c s n o c sp r s]
]

```

COMBINE is being incubated in Rebmu, but hopefully on the roadmap for main Rebol/Red, see this article.
> 1 votes

# Answer
# Scala, 142

Based on Leonardo Scattola's answer.

```
for(i<-1 to(11,1+1+1+1))println(f"$i, ${i+1}, ${i+1+1} o'clock, ${i+1+1+1} o'clock rock,");print("We're gonna rock around the clock tonight.")

```
> 1 votes

# Answer
# \>\<\> (Fish), 133

(Uses only printable ascii.)

```
".thginot kcolc eht dnuora kcor annog er'eW"11.
v da-
>:?!\1-&a",kcor kcolc'o y ,kcolc'o y ,y ,y"&
/&+1/
>l?!v:bb*-?!\o
\  &;!+1n:&~/

```

Method:

* Push the last line once and the first one 3 times onto the stack with the numbers changed to the letter "y".
* Print everything from the stack if that's not an "y" while printing the value of an increasing counter if the character is an "y".

2 bytes saved thanks to @Sp3000.
> 1 votes

# Answer
# JavaScript - 138

```
with(console){for(b=1;11>b;)log("%d, %d, %d o'clock, %d o'clock rock,",b++,b++,b++,b++);log("We're gonna rock around the clock tonight.")}

```

Try it in the console (uses `console.log`).

Inspired by izlin's answer, I just shortened it using `console.log` instead of `alert`.
> 0 votes

# Answer
# Java - 219 215 212 208

I know there's some other Java answers, but this should be the shortest...

```
class A{public static void main(String[]z){String o="",c=" o' clock",r=c+" rock,\n",p=", ";for(int i=1;i<=11;)o+=i+++p+i+++p+i+++c+p+i+++r;System.out.println(o+"We're gonna rock around the clock tonight.");}}

```
> 0 votes

# Answer
# Python - 195 chars

```
b=", ";x=" o'clock";y=' rock,\n';c=1;s="";n=1+1+1
for i in range(n):
 for j in range(n):s+=str(c)+b;c+=1
 s=s[:-1-1]+x+b+str(c)+x+y;c+=1
print s+"We're gonna rock around the clock tonight."

```
> 0 votes

# Answer
# Javascript, 179 174

This is not gonna be the shortest one, but just for fun!

Golfed:

```
a="";for(i=1;i<=11+1;i++){a+=i.toString()+(!((i+1)%4)?" o'clock":"")+(!(i%4)?" o'clock rock":"")+", "+(!(i%4)?"\n":"");}alert(a+"We're gonna rock around the clock tonight.");

```

Ungolfed:

```
a="";
for(i=1;i<=11+1;i++){
    a+=i.toString()
        +(!((i+1)%4)?" o'clock":"")
        +(!(i%4)?" o'clock rock":"")
        +", "
        +(!(i%4)?"\n":"");
}
alert(a+"We're gonna rock around the clock tonight.");
a="";

```
> 0 votes

# Answer
# F# - 173 136

Version 2 - 136

```
for x in[1..4..12]do printfn"%d, %d, %d o'clock, %d o'clock rock"x (x+1)(x+2)(x+3)
printfn"We're gonna rock around the clock tonight."

```

Version 1 - 173

```
System.Console.WriteLine("1, 2, 3 o'{0}, 4 o'{0} {1},\n5, 6, 7 o'{0}, 8 o'{0} {1},\n9, 10, 11 o'{0}, 12 o'{0} {1},\nWe're gonna {1} around the {0} tonight.","clock","rock")

```
> 0 votes

# Answer
## Julia - 134

```
r="rock"
for i=1:4:12
    println("$i, $(i+1), $(i+2) $r $(i+3) o'clock $r")
end
println("We're gonna rock around the clock tonight.")

```
> 0 votes

# Answer
# Octave, 125 characters

```
d="%d, %d, %d o'clock, %d o'clock rock,\n";
printf([d d d "We're gonna rock around the clock tonight.\n"],v=1:(a=1+1)*a++*a);

```

I construct `[1 .. 12]` vector using only ones and assignment operator, and pass it as variable argument list to `printf`, taking advantage of fact that `printf (fmt, a, a, a)` and `printf(fmt, [a a a])` are both correct ways of supplying variable argument list to function.
> 0 votes

---
Tags: code-golf, kolmogorov-complexity, restricted-source
---


title: (Somewhat) Pedantic Birthday Paradox

text:
# Question
Title: (Somewhat) Pedantic Birthday Paradox
## Background

The birthday paradox is a popular problem in probability theory which defies (most people's) mathematical intuition. The problem statement is:

> Given *N* people, what is the probability that at least two of them have the same birthday (disregarding the year).

The problem is usually simplified by ignoring leap days entirely. In this case, the answer for *N = 23* is *P(23) ≈ 0.5072972* (as a common example). The linked Wikipedia article explains how to arrive at this probability. Alternatively, this Numberphile video does a really good job.

However, for this challenge we want to do it right and *don't* ignore leap years. This is slightly more complicated, since now the 29th of February needs to be added, but this particular birthday is less likely than all the others.

We'll also use the full leap year rules:

* If a year is divisible by 400 it's a leap year.
* Else, if a year is divisible by 100 it's not a leap year.
* Else, if a year is divisible by 4 it's a leap year.
* Else, it's not a leap year.

Confused? It means that the years 1700, 1800, 1900, 2100, 2200, 2300 are not leap years, but 1600, 2000, 2400 are (as well as any other year divisible by 4). This calendar repeats every 400 years, and we will assume a uniform distribution of birthdays over those 400 years.

The corrected result for *N = 23* is now *P(23) ≈ 0.5068761*.

## The Challenge

Given an integer `1 ≤ N < 100`, determine the probability that among `N` people at least two have the same birthday under consideration of the leap year rules. The result should be a floating-point or fixed-point number, accurate to at least 6 decimal places. It is acceptable to truncate trailing zeroes.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and output the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Your solution must be able to produce output for all 99 inputs in a matter of seconds. This is mainly to rule out Monte Carlo methods with tons of samples, so if you're using a principally fast and exact algorithm in an excessively slow esoteric language, I'm willing to give leeway on this rule.

## Test Cases

Here is the full table of results:

```
 1 => 0.000000
 2 => 0.002737
 3 => 0.008195
 4 => 0.016337
 5 => 0.027104
 6 => 0.040416
 7 => 0.056171
 8 => 0.074251
 9 => 0.094518
10 => 0.116818
11 => 0.140987
12 => 0.166844
13 => 0.194203
14 => 0.222869
15 => 0.252642
16 => 0.283319
17 => 0.314698
18 => 0.346578
19 => 0.378764
20 => 0.411063
21 => 0.443296
22 => 0.475287
23 => 0.506876
24 => 0.537913
25 => 0.568260
26 => 0.597796
27 => 0.626412
28 => 0.654014
29 => 0.680524
30 => 0.705877
31 => 0.730022
32 => 0.752924
33 => 0.774560
34 => 0.794917
35 => 0.813998
36 => 0.831812
37 => 0.848381
38 => 0.863732
39 => 0.877901
40 => 0.890932
41 => 0.902870
42 => 0.913767
43 => 0.923678
44 => 0.932658
45 => 0.940766
46 => 0.948060
47 => 0.954598
48 => 0.960437
49 => 0.965634
50 => 0.970242
51 => 0.974313
52 => 0.977898
53 => 0.981043
54 => 0.983792
55 => 0.986187
56 => 0.988266
57 => 0.990064
58 => 0.991614
59 => 0.992945
60 => 0.994084
61 => 0.995055
62 => 0.995880
63 => 0.996579
64 => 0.997169
65 => 0.997665
66 => 0.998080
67 => 0.998427
68 => 0.998715
69 => 0.998954
70 => 0.999152
71 => 0.999314
72 => 0.999447
73 => 0.999556
74 => 0.999645
75 => 0.999717
76 => 0.999775
77 => 0.999822
78 => 0.999859
79 => 0.999889
80 => 0.999913
81 => 0.999932
82 => 0.999947
83 => 0.999959
84 => 0.999968
85 => 0.999976
86 => 0.999981
87 => 0.999986
88 => 0.999989
89 => 0.999992
90 => 0.999994
91 => 0.999995
92 => 0.999996
93 => 0.999997
94 => 0.999998
95 => 0.999999
96 => 0.999999
97 => 0.999999
98 => 0.999999
99 => 1.000000

```

(Of course, *P(99)* is only *1.0* due to rounding. The probability won't reach exactly *1.0* until *P(367)*.)

# Answer
> 6 votes
# Pyth, 31 ~~34~~ bytes

```
Jt.2425K366-1c.xX0rK-KQ*JQ^+KJQ

```

Demonstration, Test Harness

This works similarly to the old version, except that instead of separately generating the (366 + n * (.2425 - 1)) value and multiplying it on, it starts by generating a list which extends from 366 to 365 - n + 2, then modifies the 366 in place to become (366 + n * (.2425 - 1)), and then takes the product of the list. Also, the constants 366 and -.7575 are used instead of 365 and .2425.

---

Old version:

Pyth, 34 bytes

```
J.2425K365-1c*+hK*QtJ.xrK-hKQ^+KJQ

```

There are two possible ways for there to be no pair of people with the same birthday: everyone to have different birthdays, and no one has a birthday on February 29th, and someone to have a birthday on the 29th, and everyone else to have different birthdays on normal days.

The probability of the first occurring is (365 * 364 * ... 365 - n + 1) / (365.2425^n).

The probability of the second occurring is (365 * 364 * ... 365 - n + 2) * .2425 * n / (365.2425^n)

These can be written together as (365 * 364 * ... 365 - n + 2) * (365 - n + 1 + .2425 * n) / (365.2425^n) = (365 * 364 * ... 365 - n + 2) * (365 + 1 + (.2425 - 1) * n) / (365.2425^n).

This is the probability of no pairs, so the probability of at least one pair is one minus the above number.

```
J = .2425
K = 365
.xrK-hKQ = (365 * 364 * ... 365 - n + 2)
+hK*QtJ = (365 + 1 + n * (.2425 - 1))
^+KJQ = (365.2425 ^ n)

```

# Answer
> 5 votes
# Python, 179 178 144 143 140 136 135 133

```
f=.2425
g=365+f
a=lambda n:(n and(365-n)*a(n-1)or 365)/g
b=lambda n:(n<2and f or(367-n)*b(n-1)+a(n-2)*f)/g
p=lambda n:1-a(n-1)-b(n)

```

`p(n)` gives the result. Change `.2425` to `fractions.Fraction(97,400)` to get an exact result.

# Answer
> 2 votes
# Python ~~155~~ ~~153~~ ~~151~~ ~~142~~ 140 bytes

```
d=146097
b=d/400
c=97/d
e=lambda n:n<2and 1-97/d or e(n-1)*(366-n)/b
f=lambda n:n<2and c or f(n-1)*(367-n)/b+e(n-1)*c
a=lambda n:1-e(n)-f(n)

```

Call `a(n)` for the result. For exact results, wrap `d` in a fraction.

Test here

Uses same technique as here, but with modified constants.

# Answer
> 1 votes
# 80386 machine code, 43 bytes

Hexdump of the code:

```
68 75 6e 33 3b 68 5a eb 07 3b 8b c4 49 d9 e8 d9
e8 d8 00 d9 e8 d9 40 04 de ea d8 c9 d9 00 de eb
e2 f3 d8 ca d9 e8 d8 e1 58 58 c3

```

I started from the following formula (for the complementary probability):

(here `d = 366 * 400 - 303` is the number of days in 400 years)

Here is c++ code that implements it (it's already optimized a little):

```
double it_opt(int k)
{
    double d = 366 * 400 - 303; // number of days in 400 years
    double result = 1; // probability of no coincidences
    const float const1 = float(400 / d);
    const float const2 = float(303 / d);
    double v1 = 1 + const2;
    double v2 = 1;

    for (int i = 0; i < k - 1; ++i)
    {
        v1 -= const1;
        result *= v1;
        v2 -= const2;
    }
    result *= v2;
    return 1 - result;
}

```

The code is arranged so it requires the minimum number of constants - only two (`400 / d` and `303 / d`). I use the `float` type to represent them because it occupies less space (4 bytes per constant). In addition, I didn't want to multiply `const2` by `k - 1` (because that would require converting `k - 1` to `float`); the code subtracts `const2` repeatedly instead.

Here is the assembly language listing:

```
    ; // fastcall convention - parameter k is in ecx
    ; // result must be returned in st
    push dword ptr 0x3b336e75; // const1 = [esp + 4]
    push dword ptr 0x3b07eb5a; // const2 = [esp]
    mov eax, esp;              // use [eax] instead of [esp] - 1 byte less
    dec ecx;                   // calculate k - 1
    fld1;                      // initiaze result = 1
    fld1;                      // initialize v1
    fadd [eax];
    fld1;                      // initialilze v2
myloop:
    fld dword ptr [eax + 4];
    fsubp st(2), st;            // update v1
    fmul st, st(1);             // update result
    fld dword ptr [eax];
    fsubp st(3), st;            // update v2
    loop myloop;                // loop
    fmul st, st(2);             // update result by v2
    fld1;
    fsub st, st(1);             // complement result
    pop eax;                    // restore stack
    pop eax;                    // restore stack
    ret;                        // return

```

---
Tags: code-golf, probability-theory
---


title: Quick! Escape the black hole!

text:
# Question
Title: Quick! Escape the black hole!
It is the year 87,539,319 and solitary space-walking is now commonplace, many people travel into space by themselves, propelled by nothing but a jetpack on their backs, programming their course with a personal computer and keyboard as they go.

You are one such person; you were out on a lovely, peaceful spacewalk, when, all of a sudden, you were ensnared by the gravity of a black hole!

As you plummet towards this black hole, spiraling ever faster inwards, you realise your one chance of survival is to broadcast a distress message, and hope a nearby ship comes to rescue you.

So, you break out your keyboard, and begin typing away a program.

Your program can be in any language, and must print `HELP!` to stdout (your PC broadcasts all stdout far into the depths of space.)

However, as you are near a blackhole, your keyboard is slowly being ripped to shreds!

Assume you are using a QWERTY keyboard like the one below, and that the blackhole is to your left;

Remember, left and right shift are two different keys.

after every keypress, the left-most row of your keyboard (keys covered by left-most red line) is ripped off and flung into the black hole!

So, your first keypress could be any key on the keyboard, but from then onwards none of the *leftmost* `Tab`, `Caps`, `Shift`, `Ctrl` or ``` keys may be used, *at all*. (r-shift and r-ctrl can still be used)

After the next keypress, the keys `1`, `Q`, `A`,`Z` and `Alt` are flung into the abyss, and may not be used thereafter. After that, you lose `Space`, `X`, `S`, `W`, `2` and so forth.

Obviously, you want to complete your program as quickly as possible, so that rescue-time is increased; therefore, this is code-golf, and the shortest program *in key presses* wins!

Each answer should provide a list of keypresses, so, if my answer was this program (in the language squardibblyack)

```
!HELP\.

```

a keylist could look like:

`Shift``!``H``E``L``P` release shift `\``.`

length: 8

I'm worried this challenge might be too difficult, but I'd love to see the kinds of answers submitted!

# Answer
# CJam, 11 keystrokes

The code is

```
"HELP*")9-

```

and the keylist is

`Shift``"``H``E``L``P``*``"``)` release shift `9``-`

and here is a demonstration of how it looks:

and here is how the code works:

```
"HELP*"              "This puts the string HELP* on stack";
       )             "This takes out the last character of the string and puts it
                      on the stack as a character";
        9-           "This simply reduces 9 from the ASCII code of * character
                      present on the stack which makes it an !";
                     "CJam automatically prints everything that is on stack";

```

Try the code here
> 42 votes

# Answer
# rs, 10 keystrokes (assumes the user is using Nano)

Or equivalent editor where `Shift` doesn't select text.

This isn't really a programming language, but if `sed` can be used on Code Golf, then `rs` can be used.

`Right Shift` `!` `Left` `E` `Left` `H` `Right` `L` `P` `Enter`

```
HELP!

```

It just replaces the empty string with "HELP!", effectively printing it to the screen. Roughly equivalent to the sed script:

```
s/^/HELP!/

```

The cool part is that `rs` automatically puts `^/` in front of a replacement pattern where the delimiter (`/`) is not found. Handy for indenting code.
> 3 votes

---
Tags: code-golf, restricted-source
---


title: Counting in pyramids

text:
# Question
Title: Counting in pyramids
You should write a program or function which receives a list of distinct integers as input and outputs or returns the number of occurrences of the input numbers in the following upside-down number pyramid.

Starting from the original list in every step we create a new one with the maximal values of every pair of adjacent numbers (e.g. `5 1 2 6` becomes `5 2 6`). We stop when there is only one number in the list.

The full pyramid for `5 1 2 6` is

```
5 1 2 6
 5 2 6
  5 6
   6

```

The resulting number of occurrences are `3 1 2 4` (for `5 1 2 6` respectively).

## Input

* A list of one or more integers with no repetition. (e.g. `1 5 1 6` is invalid.)

## Output

* A list of positive integers. The `i`th element of the list is the number of occurrences of the `i`th input number in the pyramid.

## Examples

Input =\> Output

```
-5 => 1

8 4 => 2 1

5 9 7 => 1 4 1

1 2 3 9 8 6 7 => 1 2 3 16 3 1 2

6 4 2 1 3 5 => 6 4 2 1 3 5

5 2 9 1 6 0 => 2 1 12 1 4 1

120 5 -60 9 12 1 3 0 1200 => 8 2 1 3 16 1 4 1 9

68 61 92 58 19 84 75 71 46 69 25 56 78 10 89 => 2 1 39 2 1 27 6 5 1 6 1 2 14 1 12

```

This is code-golf so the shortest entry wins.

*Bonus puzzle: can you solve the problem in `O(n*log n)` time?*

# Answer
# Pyth, ~~19~~ 17 bytes

```
m/smmeSb.:QhkUQdQ

```

Check out the Online Demonstration or the complete Test Suite (first 4 byte iterate over the examples).

This one is a little bit more clever than the naive approach. Each number of the triangle can be represented as the maximal value of a connected subset of `Q`. In the first line it uses the subsets of length 1, the second line of the triangle uses the subsets of length 2, ...

### Explanation

```
m/smmeSb.:QhkUQdQ    implicit: Q = input()
   m         UQ         map each k in [0, 1, 2, ..., len(Q)-1] to:
        .:Qhk              all subsets of Q of length (k + 1)
    meSb                   mapped to their maximum
  s                     join these lists together
m               Q    map each d of Q to:
 /             d        its count in the computed list

```

To visualize this a little bit. `m.:QhdUQ` and the input `[5, 1, 2, 6]` gives me all possible subsets:

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

```

And `mmeSk.:QhdUQ` gives me each of their maxima (which corresponds exactly to the rows in the pyramid):

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

```

# Pyth, ~~23~~ 22 bytes

```
|u&aYGmeSd.:G2QQm/sYdQ

```

This is just the simple "do what you're told" approach.

Check out the Online Demonstration or a complete Test Suite (first 4 byte iterate over the examples).

### Explanation

`meSd.:G2` maps each pair of `[(G[0], G[1]), (G[1], G[2]), ...]` to the maximal element.

`Y` is an empty list, therefore `aYG` appends `G` to the `Y`.

`u...QQ` repeatedly applies these two functions (`len(Q)` times) starting with `G = Q` and updating `G` after each run.

`m/sYdQ` maps each element of the input list to their count in the flattened `Y` list.
> 4 votes

# Answer
# Python, 81

```
def f(L):
 if L:i=L.index(max(L));L=f(L[:i])+[~i*(i-len(L))]+f(L[i+1:])
 return L

```

A divide-and-conquer solution. The maximum element `M` seeps all the way down the pyramid, splitting it into a rectangle of `M`'s and two subpyramids.

```
* * * M * *
 * * M M *
  * M M M
   M M M
    M M
     M

```

So, the overall result is the output for the left sublist, followed by the area of the rectangle, followed by the output for the right sublist.

The input variable `L` is reused to stored the result so that the empty list is mapped to the empty list.

The constructs in solution are wordy in Python. Maybe some language with pattern-matching can implement the following pseudocode?

```
def f(L):
 [] -> []
 A+[max(L)]+B -> f(A)+[(len(A)+1)*(len(B)+1)]+f(B)

```
> 13 votes

# Answer
# CJam, ~~23~~ 22 bytes

Still looking for golfing options.

```
{]_,{)W$ew::e>~}%fe=~}

```

This is a CJam function (sort of). This expects the input numbers on stack and returns the corresponding output counts on the stack too. An example:

```
5 1 2 6 {]_,{)W$ew::e>~}%fe=~}~

```

leaves

```
3 1 2 4

```

on stack.

Pretty sure that this is not in `O(n log n)` time.

**Code expansion**:

```
]_                     e# Wrap the input numbers on stack in an array and take a copy
  ,{          }%       e# Take length of the copy and run the loop from 0 to length - 1
    )W$                e# Increment the iterating index and copy the parsed input array
       ew              e# Get overlapping slices of iterating index + 1 size
         ::e>          e# Get maximum from each slice
             ~         e# Unwrap so that there can be finally only 1 level array
                fe=    e# For each of the original array, get the occurrence in this
                       e# final array created by the { ... }%
                   ~   e# Unwrap the count array and leave it on stack

```

Lets take a look at how it works by working up an example of `5 1 2 6`

In the second row, `5 1 2 6` becomes `5 2 6` because `5, 2 and 6` are the maximum of `[5 1], [1 2] and [2 6]` respectively. In the third row, it becomes `5 6` because `5 and 6` are maximum of `[5 2] and [2 6]` respectively. This can also be written as maximum of `[5 1 2] and [1 2 6]` respectively. Similarly for last row, `6` is maximum of `[5 1 2 6]`.

So we basically create the proper length slices starting from slice of length `1`, which is basically the original numbers, each wrapped in an array, to finally a slice of length `N` for the last row, where `N` is the number of input integers.

Try it online here
> 6 votes

# Answer
# Mathematica, 72 bytes

```
Last/@Tally[Join@@NestList[MapThread[Max,{Most@#,Rest@#}]&,#,Length@#]]&

```
> 3 votes

# Answer
# Python, 81

```
lambda L:[sum(x==max(L[i:j])for j in range(len(L)+1)for i in range(j))for x in L]

```

Each entry of the pyramid is the maximum of the sublist atop its upward cone. So, we generate all these sublists, indexed by intervals `[i,j]` with `0 < i < j <= len(L)`, and count how many time each element appears as a maximum.

A shorter way to enumerate the subintervals would likely save characters. A single-index parametrization of the pairs `[i,j]` would be a plausible approach.
> 3 votes

# Answer
# Pip, 56 + 1 = 57 bytes

Not competing much with the CJam voodoo, I'm afraid. Looks like I need a better algorithm. Run with `-s` flag to get space-delimited output.

```
l:gr:0*,#gg:0*g+1WrFir:{c:r@[a--a]c@($<l@c)}M1,#r++(gi)g

```

Ungolfed, with comments:

```
l:g                              l = input from cmdline args
r:0*,#g                          r = current row as a list of indices into l
g:0*g+1                          Repurpose g to store the frequencies
Wr                               Loop until r becomes empty
 Fir:{c:r@[a--a]c@($<l@c)}M1,#r  Redefine r (see below) and loop over each i in it
  ++(gi)                         Increment g[i]
g                                Output g

```

The redefinition of `r` each time through works as follows:

```
{c:r@[a--a]c@($<l@c)}M1,#r
{                   }M1,#r       Map this function to each a from 1 to len(r) - 1:
 c:r@[a--a]                      c is a two-item list containing r[a] and r[a-1]
                l@c              The values of l at the indices contained in c
              $<                 Fold/less-than: true iff l[c[0]] < l[c[1]]
           c@(     )             Return c[0] if the former is greater, c[1] otherwise

```
> 1 votes

# Answer
# APL (24)

```
{+/⍵∘.={⍵≡⍬:⍵⋄⍵,∇2⌈/⍵}⍵}

```

This is a function that takes a list, like so;

```
      {+/⍵∘.={⍵≡⍬:⍵⋄⍵,∇2⌈/⍵}⍵}68 61 92 58 19 84 75 71 46 69 25 56 78 10 89
2 1 39 2 1 27 6 5 1 6 1 2 14 1 12

```

Explanation:

* `{`...`}⍵`: apply the following function to ⍵:
    + `⍵≡⍬:⍵`: if ⍵ is empty, return ⍵
    + `2⌈/⍵`: generate the next list
    + `⍵,∇`: return ⍵, followed by the result of applying this function to the next list
* `⍵∘.=`: compare each element in ⍵ to each element in the result of the function
* `+/`: sum the rows (representing elements in ⍵)
> 1 votes

# Answer
# Haskell, 78 bytes

```
l=length
f x=[l[b|b<-concat$take(l x)$iterate(zipWith max=<<tail)x,a==b]|a<-x]

```

Usage: `f [68,61,92,58,19,84,75,71,46,69,25,56,78,10,89]`-\> `[2,1,39,2,1,27,6,5,1,6,1,2,14,1,12]`.

How it works

```
zipWith max=<<tail   -- apply 'max' on neighbor elements of a list
iterate (...) x      -- repeatedly apply the above max-thing on the
                     -- input list and build a list of the intermediate
                     -- results
take (l x) ...       -- take the first n elements of the above list
                     -- where n is the length of the input list
concat               -- concatenate into a single list. Now we have
                     -- all elements of the pyramid in a single list.
[ [b|b<-...,a==b] | a<-x]
                     -- for all elements 'a' of the input list make a
                     -- list of 'b's from the pyramid-list where a==b.
 l                   -- take the length of each of these lists

```
> 1 votes

# Answer
# JavaScript, 109 bytes

I think I found an interesting way to go about this, but only after I was done realized the code was too long to compete. Oh well, posting this anyway in case someone sees further golfing potential.

```
f=s=>{t=[];for(i=-1;s.length>++i;){j=k=i;l=r=1;for(;s[--j]<s[i];l++);for(;s[++k]<s[i];r++);t[i]=l*r}return t}

```

I'm making use of the following formula here:

> occurrences of i = (amount of consecutive numbers smaller than i to its left + 1) * (amount of consecutive numbers smaller than i to its right + 1)

This way one doesn't need to actually generate the entire pyramid or subsets of it. (Which is why I initially thought it would run in O(n), but tough luck, we still need inner loops.)
> 1 votes

# Answer
## MATLAB : (266 b)

> * the correction of the code costs more bytes, i will struggle how to reduce it later.

```
v=input('');h=numel(v);for i=1:h,f=(v(i)>v(1));l=(v(i)>v(h));for j=h-1:-1:i+1,l=(v(i)>v(j))*(1+l);end,if(i>1),l=l+(v(i)>v(i-1))*l;end;for j=2:i-1,f=(v(i)>v(j))*(1+f);end,if(i<h),f=f+(v(i)>v(i+1))*f;end;s=f+l+1;if(i<h&&i>1),s=s-((v(i)>v(i+1))*(v(i)>v(i-1)));end;s
end

```

## INPUT

a vector must be of the form \[a b c d ...\]

* example:

\[2 4 7 11 3\]

## OUTPUT

pattern occurences.

```
s =

 1

s =

 2

s =

 3

s =

 8

s =

 1

```

## EXPLANATION:

if \[a b c d\] is an input the program calculates result g h i j as

g= (a\>b) + (a\>b)*(a\>c) + (a\>b)*(a\>c)\*(a\>d) = (a\>b)(1+(a\>c)(1+(a\>c) )))

h= (b\>a) + (b\>c) + (b\>a)*(b\>c) + (b\>c)*(b\>d)+(b\>a)*(b\>c)*(b\>d) = ... 'simplified'

i= (c\>b) + (c\>d) + (c\>b)*(c\>d) + (c\>b)*(c\>a)+(c\>d)*(c\>b)*(c\>a) = ..

j= (d\>c) + (d\>c)*(d\>b) + (d\>c)*(d\>b)\*(d\>a) = ...
> 1 votes

# Answer
# J (49)

I suppose there is some room for improvement...

```
[:+/~.="1 0[:;([:i.#)<@:(4 :'(}:>.}.)^:x y')"0 1]

```
> 0 votes

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


title: Generating Euclidean rhythms

text:
# Question
Title: Generating Euclidean rhythms
Did you know that the Euclidean algorithm is capable of generating traditional musical rhythms? We'll see how this works by describing a similar, but slightly different algorithm to that in the paper.

Pick a positive integer `n`, the total number of beats, and a positive integer `k`, the number of beats which are sounded (notes). We can think of the rhythm as a sequence of `n` bits, `k` of which are 1s. The idea of the algorithm is to distribute the 1s as evenly as possible amongst the 0s.

For example, with `n = 8` and `k = 5`, we start with 5 ones and 3 zeroes, each in its own sequence:

```
[1] [1] [1] [1] [1] [0] [0] [0]

```

At any point we will have two types of sequences — the ones at the start are the "core" sequences and the ones at the end are the "remainder" sequences. Here the cores are `[1]`s and the remainders are `[0]`s. As long as we have more than one remainder sequence, we distribute them amongst the cores:

```
[1 0] [1 0] [1 0] [1] [1]

```

Now the core is `[1 0]` and the remainder is `[1]`, and we distribute again:

```
[1 0 1] [1 0 1] [1 0]

```

Now the core is `[1 0 1]` and the remainder is `[1 0]`. Since we only have one remainder sequence, we stop and get the string

```
10110110

```

This is what it sounds like, repeated 4 times:

Here's another example, with `n = 16` and `k = 6`:

```
[1] [1] [1] [1] [1] [1] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0]
[1 0] [1 0] [1 0] [1 0] [1 0] [1 0] [0] [0] [0] [0]
[1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0] [1 0]
[1 0 0 1 0] [1 0 0 1 0] [1 0 0] [1 0 0]
[1 0 0 1 0 1 0 0] [1 0 0 1 0 1 0 0]
1001010010010100

```

Note how we terminated on the last step with two core sequences and no remainder sequences. Here it is, repeated twice:

## Input

You may write a function or a full program reading from STDIN, command line or similar. Input will be two positive integers `n` and `k <= n`, which you may assume is in either order.

## Output

Your task is to output the generated rhythm as an `n` character long string. You may pick any two distinct printable ASCII characters (0x20 to 0x7E) to represent notes and rests.

## Test cases

The following test cases use `x` to represent notes and `.`s to represent rests. Input is given in the order `n`, then `k`.

```
1 1    ->  x
3 2    ->  xx.
5 5    ->  xxxxx
8 2    ->  x...x...
8 5    ->  x.xx.xx.
8 7    ->  xxxxxxx.
10 1   ->  x.........
11 5   ->  x.x.x.x.x..
12 7   ->  x.xx.x.xx.x.
16 6   ->  x..x.x..x..x.x..
34 21  ->  x.xx.x.xx.xx.x.xx.x.xx.xx.x.xx.x.x
42 13  ->  x...x..x..x..x...x..x..x..x...x..x..x..x..
42 18  ->  x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.

```

## Scoring

This is code-golf, so the code in the fewest bytes wins.

# Answer
# CJam, ~~37~~ ~~34~~ ~~30~~ ~~27~~ 24 bytes

*3 bytes saved by user23013.*

```
q~,f>{_(a-W<}{e`:a:e~z}w

```

This takes the input as `k` first, `n` second. It uses `1` and `0` to indicate notes and rests, respectively.

Try it here. Alternatively, here is a test harness which runs all of the given test cases (swapping the input order) and also reformats the output to use `x` and `.` for easier comparison with the reference solutions. (The results appearing in the input of the test harness are discarded before running the code. They could be safely removed without affecting the program.)

## Explanation

```
q~                       e# Read and eval the input, dumping k and n on the stack.
  ,                      e# Create a range [0 .. n-1]
   f>                    e# For each of them, check if it's less than k.
                         e# This gives k 1s and n-k 0s.
     {      }{        }w e# While the first block yields a truthy result, execute
                         e# the second block.
      _                  e# Duplicate the array.
       (a-               e# Remove all instances of core sequences.
          W<             e# Remove one remainder sequence if there is one. This
                         e# gives an empty array (falsy) whenever there are less
                         e# than two remainder sequences.
              e`         e# Run-length encode. I.e. this turns an array into a list
                         e# of pairs of run-length and element.
                :a:e~    e# Wrap each RLE pair in an array and RLD it. This
                         e# partitions the array into cores and remainders.
                     z   e# Zip the two parts, interleaving cores and remainders.

```

This process very deeply nested arrays, but the important part is that all cores (and all remainders) always have the same nested structure, so they are still equal to each other. CJam automatically prints the stack contents at the end of the program and omits array delimiters entirely, hence this structure does not affect the output either.
> 5 votes

# Answer
# Haskell, 125 bytes

```
r=replicate
g z(a:b)(c:d)=g((a++c):z)b d
g z x y=(z,x++y)
f(x,y)|length y>1=f$g[]x y|1<2=concat$x++y
n#k=f(r k "x",r(n-k)".")

```

Usage example: `42 # 13` -\> `x...x..x..x..x...x..x..x..x...x..x..x..x..`.

`f` takes two parameters: core and remainder list. It either zips both lists (via `g`) and calls itself again or stops if the remainder is too short. The main function `#` creates the starting lists and calls `f`.
> 1 votes

# Answer
# Python, 85

```
f=lambda n,k,a='1',b='0':n-k<2and a*k+b*(n-k)or[f(n-k,k,a+b,b),f(k,n-k,a+b,a)][2*k>n]

```

The natural recursive solution. The parameters `(n,k,a,b)` represent a core of `k` `a`'s followed by a remainder of `n-k` `b'`s.

This solution is inefficient because both recursive calls to `f` are evaluated, causing an exponential number of calls.

I tried to compress the conditional invocation of `f` like

```
f(max(n-k,k),min(n-k,k),a+b,[a,b][2*k<n])
f(*[n-k,k,k,n-k,b,a][2*k>n::2]+[a+b])

```

but none turned out shorter.
> 1 votes

---
Tags: code-golf
---


title: Pi is still wrong

text:
# Question
Title: Pi is still wrong
# Pi is Wrong

A common method of computing pi is by throwing "darts" into a 1x1 box and seeing which land in the unit circle compared to the total thrown:

```
loop
   x = rand()
   y = rand()
   if(sqrt(x*x + y*y) <= 1) n++
   t++
pi = 4.0*(n/t)

```

Write a program that *looks* like it should correctly compute pi (using this or other common methods of computing pi) but computes tau (tau = 2\*pi = 6.283185307179586...) instead. Your code must produce at least the first 6 decimal places: 6.283185

Winner is crowned June 6th (one week from today).

# Answer
> 57 votes
# JavaScript

```
alert(Math.atan2(0, -0) - Math.atan2(-0, -0) + Math.atan2(0, 0))

```

Help, I'm trapped in a universe factory, and I'm not sure what I'm doing. `Math.atan2` is supposed to return pi with good values, right? `Math.atan2(0, -0)` returns pi, so if I subtract it, and add it, I should still have pi.

# Answer
> 40 votes
# BASIC

(More specifically, Chipmunk Basic)

This uses an infinite series discovered by Nilakantha Somayaji in the 15th century:

```
' Calculate pi using the Nilakantha series:
'               4       4       4       4
'  pi  =  3 + ----- - ----- + ----- - ------ + ...
'             2x3x4   4x5x6   6x7x8   8x9x10
i = pi = 0
numerator = -4
while i<10000
  i = i + 2
  numerator = -numerator
  pi = pi + numerator / (i * (i+1) * (i+2))
wend
pi = pi + 3
print using "#.##########";pi

```

### Output

```
6.2831853072

```

If you can't figure out what's going on, here are a couple of hints:

> In Chipmunk Basic, the variable ***pi*** is preset to the value of π when the program starts running.

and

> In BASIC, the equals sign is used both for assigning variables and for testing equality. So ***a = b = c*** is interpreted as ***a = (b==c)***.

# Answer
> 15 votes
## C - The length of half a unit circle

One way to compute **π** is simply to measure the distance the point `(1, 0)` travels when rotating around the **origin** to `(-1, 0)` since it will be half the circumference of a **unit circle** (which is ).

However, no `sin(x)` or `cos(x)` is needed since this can be done by *stepping* all the way around the **origin** and **adding the distance the point travels for each step**. The smaller size for each step the more accurate **π** you will get.

**Note:** The stepping will end when y is below zero (which is just as it passes `(-1, 0)`).

```
#include <stdio.h>                          // for printf
#define length(y, x) ((x * x) + (y * y))
int main()
{
    double x, y;
    double pi, tau, step;
    // start at (2, 0) which actually calculates tau
    x  = 2;
    y  = 0;
    // the step needs to be very low for high accuracy
    step = 0.00000001;
    tau = 0;
    while (y >= 0)
    {   // the derivate of (x, y) is itself rotated 90 degrees
        double dx = -y;
        double dy = x;

        tau += length(dx, dy) * step; // add the distance for each step to tau
        // add the distance to the point (make a tiny rotation)
        x += dx * step;
        y += dy * step;
    }
    pi = tau / 2;   // divide tau with 2 to get pi

    /* ignore this line *\                      pi *= 2;    /* secret multiply ^-^ */

    // print the value of pi
    printf("Value of pi is %f", pi); getchar();
    return 0;
}

```

It gives the following output:

```
Value of pi is 6.283185

```

# Answer
> 10 votes
# C

(This ended up being longer than intended, but I'll post it anyways...)

In the 17th century, Wallis published an infinite series for Pi:

(See New Wallis- and Catalan-Type Infinite Products for π, e, and √(2 + √2) for more information)

Now, in order to calculate Pi, we must first multiply by two to factor out the denominator:

My solution then calculates the infinite series for Pi/2 and two and then multiplies the two values together. Note that infinite products are incredibly slow to converge when calculating final values.

output:

```
pi: 6.283182

```

```
#include "stdio.h"
#include "stdint.h"

#define ITERATIONS 10000000
#define one 1

#define IEEE_MANTISSA_MASK 0xFFFFFFFFFFFFFULL

#define IEEE_EXPONENT_POSITION 52
#define IEEE_EXPONENT_BIAS 1023

// want to get an exact as possible result, so convert
// to integers and do custom 64-bit multiplication.
double multiply(double aa, double bb)
{
    // the input values will be between 1.0 and 2.0
    // so drop these to less than 1.0 so as not to deal
    // with the double exponents.
    aa /= 2;
    bb /= 2;

    // extract fractional part of double, ignoring exponent and sign
    uint64_t a = *(uint64_t*)&aa & IEEE_MANTISSA_MASK;
    uint64_t b = *(uint64_t*)&bb & IEEE_MANTISSA_MASK;

    uint64_t result = 0x0ULL;

    // multiplying two 64-bit numbers is a little tricky, this is done in two parts,
    // taking the upper 32 bits of each number and multiplying them, then
    // then doing the same for the lower 32 bits.
    uint64_t a_lsb = (a & 0xFFFFFFFFUL);
    uint64_t b_lsb = (b & 0xFFFFFFFFUL);

    uint64_t a_msb = ((a >> 32) & 0xFFFFFFFFUL);
    uint64_t b_msb = ((b >> 32) & 0xFFFFFFFFUL);

    uint64_t lsb_result = 0;
    uint64_t msb_result = 0;

    // very helpful link explaining how to multiply two integers
    // http://stackoverflow.com/questions/4456442/interview-multiplication-of-2-integers-using-bitwise-operators
    while(b_lsb != 0)
    {
        if (b_lsb & 01)
        {
            lsb_result = lsb_result + a_lsb;
        }
        a_lsb <<= 1;
        b_lsb >>= 1;
    }
    while(b_msb != 0)
    {
        if (b_msb & 01)
        {
            msb_result = msb_result + a_msb;
        }
        a_msb <<= 1;
        b_msb >>= 1;
    }

    // find the bit position of the most significant bit in the higher 32-bit product (msb_answer)
    uint64_t x2 = msb_result;
    int bit_pos = 0;
    while (x2 >>= 1)
    {
        bit_pos++;
    }

    // stuff bits from the upper 32-bit product into the result, starting at bit 51 (MSB of mantissa)
    int result_position = IEEE_EXPONENT_POSITION - 1;
    for(;result_position > 0 && bit_pos > 0; result_position--, bit_pos--)
    {
        result |= ((msb_result >> bit_pos) & 0x01) << result_position;
    }

    // find the bit position of the most significant bit in the lower 32-bit product (lsb_answer)
    x2 = lsb_result;
    bit_pos = 0;
    while (x2 >>= 1)
    {
        bit_pos++;
    }

    // stuff bits from the lowre 32-bit product into the result, starting at whatever position
    // left off at from above.
    for(;result_position > 0 && bit_pos > 0; result_position--, bit_pos--)
    {
        result |= ((lsb_result >> bit_pos) & 0x01) << result_position;
    }

    // create hex representation of the answer
    uint64_t r = (uint64_t)(/* exponent */ (uint64_t)IEEE_EXPONENT_BIAS << IEEE_EXPONENT_POSITION) |
            (uint64_t)( /* fraction */ (uint64_t)result & IEEE_MANTISSA_MASK);

    // stuff hex into double
    double d = *(double*)&r;

    // since the two input values were divided by two,
    // need to multiply by four to fix the result.
    d *= 4;

   return d;
}

int main()
{
    double pi_over_two = one;
    double two = one;

    double num = one + one;
    double dem = one;

    int i=0;

    i=ITERATIONS;
    while(i--)
    {
        // pi = 2 2 4 4 6 6 8 8 ...
        // 2    1 3 3 5 5 7 7 9
        pi_over_two *= num / dem;

        dem += one + one;

        pi_over_two *= num / dem;

        num += one + one;
    }

    num = one + one;
    dem = one;

    i=ITERATIONS;
    while(i--)
    {
        // 2 = 2 4 4 6   10 12 12 14
        //     1 3 5 7    9 11 13 15
        two *= num / dem;

        dem += one + one;
        num += one + one;

        two *= num / dem;

        dem += one + one;

        two *= num / dem;

        dem += one + one;
        num += one + one;

        two *= num / dem;

        dem += one + one;
        num += one + one + one + one;
    }

    printf("pi: %f\n", multiply(pi_over_two, two));

    return 0;
}

```

> The exponent in the double conversion can't actually be ignored. If that's the only change (leave the divide by 2's, the multiply by 4, the integer multiplication) everything surprisingly works.

# Answer
> 8 votes
# Java - Nilakantha Series

The Nilakantha Series is given as:

```
pi = 3 + 4/(2*3*4) - 4/(4*5*6) + 4/(6*7*8) - 4/(8*9*10) ...

```

So for each term, the denominator is constructed by multiplying consecutive integers, with the start rising by 2 each term. Notice that you add/subtract alternating terms.

```
public class NilakanthaPi {
    public static void main(String[] args) {
        double pi = 0;
        // five hundred terms
        for(int t=1;t<500;t++){
            // each i is 2*term
            int i=t*2;
            double part = 4.0 / ((i*i*t)+(3*i*t)+(2*t));
            // flip sign for alternating terms
            if(t%2==0)
                pi -= part;
            else
                pi += part;
            // add 3 for first term
            if(t<=2)
                pi += 3;
        }
        System.out.println(pi);
    }
}

```

After five hundred terms, we get a reasonable estimation of pi:

```
6.283185311179568

```

# Answer
> 4 votes
# C++: Madhava of Sangamagrama

This infinite series is now known as *Madhava-Leibniz*:

Start with the square root of 48 and multiply it by the result of the sum of (-3)<sup>-k</sup>/(2k + 1). Very straightforward and simple to implement:

```
long double findPi(int iterations)
{
    long double value = 0.0;

    for (int i = 0; i < iterations; i++) {
        value += powl(-3.0, -i) / (2 * i + 1);
    }

    return sqrtl(48.0) * value;
}

int main(int argc, char* argv[])
{
    std::cout << "my pi: " << std::setprecision(16) << findPi(1000) << std::endl;

    return 0;
}

```

Output:

```
my pi: 6.283185307179588

```

# Answer
> 3 votes
**Python - An Alternative to Nilakantha series**

This is another infinite series to calculate pi that is fairly easy to understand.

For this formula, take 6 and start alternating between adding and subtracting fractions with numerators of 2 and denominators that are the product of two consecutive integers and their sum. Each subsequent fraction begins its set of integers rising by 1. Carry this out even a few times and the results get fairly close to pi.

```
pi = 6
sign = 1
for t in range(1,500):
i = t+1
   part = 2.0 / (i*t*(i+t))
   pi = pi + sign * part
   sign = - sign # flip sign for alternating terms
print(pi)

```

which gives 6.283185.

# Answer
> -1 votes
```
#include "Math.h"
#include <iostream>
int main(){
    std::cout<<PI;
    return 0;
}

```

Math.h:

```
#include <Math.h>
#undef PI
#define PI 6.28

```

Output: 6.28

#include "Math.h" is not the same as #include , but just by looking at the main file, almost no one would think to check. Obvious perhaps, but a similar issue appeared in a project I was working on, and went undetected for a long time.

---
Tags: popularity-contest, underhanded, pi
---