title: 42 in Rod Logic

text:
# Question
Title: 42 in Rod Logic
Write the shortest possible program which takes a numeric input and outputs the result of adding 42 to the input.

```
f(x) -> x + 42

```

There's only one restriction. Your program can only be composed of rod logic characters...

---

The definition for a rod logic character is a one that is composed purely of straight lines. They come from the crazy Temporally Quaquaversal Virtual Nanomachines talk by Damian Conway. To simplify things **The following will be considered the set of all valid rod logic characters.**

`_` `|` `-` `=` `\` `/` `<` `>` `[` `]` `^` `+`

Damian writes a rod logic program in Perl which takes a numeric input and outputs the result of adding 42 in 170 lines. He might be great at quantum mechanics in Perl, but I'm not sure he's played much code golf. The challenge is to improve on that.

Like Damian's example we'll say that you have access to two predefined functions:

* `__` \- which prints arguments
* `___` \- which reads and returns user input

If these aren't valid function identifiers in your language, you can replace them with other (2 and 3 byte ones)

Shortest program wins.

# Answer
> 9 votes
# Brainfuck, 25

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

```

Counting `,` as `___` (input) and `.` as `__` (output).

Works by adding 7 to the input 6 times.

# Answer
> 8 votes
# CJam, ~~22~~ 21 bytes

CJam only supports single-character function (block) names, all of which must be uppercase letters. I've used `A` in place of `___` and counted it as 3 bytes:

```
]_=__+__+++__++_+A+

```

Test it here.

## Explanation

```
]_=                  "Make an empty array, duplicate, check for equality, pushing 1.";
   __+               "Get two copies and add them, leaving the stack as [1 2].";
      __+++          "Make two copies add it all up, yielding 7.";
           __++      "Make two copies, add them up, yielding 21.";
               _+    "Make a copy add it, yielding 42.";
                 A+  "Read the input and add it.";

```

CJam automatically prints the stack contents at the end of the program.

# Answer
> 3 votes
# JavaScript, 64+3+2=69

```
+[+[++[++[++[+[]==[]][+[]]][+[]]][+[]]+[++[+[]==[]][+[]]]]][+[]]

```

To test it, write a number followed by the whole program in your browser's console.
I didn't explicitly use input and output functions, but I added 3 and 2 bytes to account for them.

**Explanation:**

```
+[] ➜ 0
0==[] ➜ true
++[true][0] ➜ 2
++[2][0] ➜ 3
++[3][0] ➜ 4
4+[2] ➜ "42"
+["42"] ➜ 42
x+[42][0] ➜ x+42

```

# Answer
> 2 votes
# Pyth, 54 + 3 bytes = 57

```
+vz-+^/+\\\\\\/+++\\\\\\\\\\^/++\\\\\\\\/++\\\\\\\\/\\\\

```

Just to show that it can be done in Pyth. `___` isn't valid in Pyth, so I'm using `vz`.

`/` is the only command which returns a number, when used as `/ <string1> <string2>` to mean `string1.count(string2)`, so we use it excessively to create numbers. The 42 is calculated as `2^4 + 3^3 - 1`.

Try it online.

# Answer
> 2 votes
## JavaScript / TypeScript / CoffeeScript, 38 bytes

`_` is a valid identifier in JS.

The question is somewhat unclear but I'm assuming that `___` stores input and `__` stores output.

The newlines are necessary (and counted as 1 byte each) regardless of whether you're running it as JavaScript (for ASI) or CoffeeScript (for compilation to JS).

```
_=[]
___+=++_<<++_<<++_
__=___+_+_+++_

```

### Explanation

```
# assigns empty array to _ which will be coerced to number 0 later
_=[]

# Add 32 to input:
#   0+1 << (0+1)+1 << ((0+1)+1)+1 = 1 << 2 << 3
#    = 1 << 2 << 3
#    = 4 << 3
#    = 32 or 0b00100000
# (Also note that _ = 3 now)
___+=++_<<++_<<++_

# Previous value + 3 + 3 + 4
# Total additions: 32 + 3 + 3 + 4 = 42
__=___+_+_+++_

```

### Demo

This is the best I can try to demonstrate it:

```
function ____(___) {
  _ = []
  ___ += ++_ << ++_ << ++_
  __ = ___ + _ + _ + ++_
  return __
}

document.getElementById('btn').addEventListener('click', function() {
  window.alert(____(+document.getElementById('foo').value));
  return false;
});
```

```
<label>
  Enter a number:
  <input type=number id=foo value=0>
</label>
<button type=button id=btn>Add 42</button>
```

# Answer
> 0 votes
# piet - 14

This might count. All of the lines are straight.

# Answer
> -2 votes
## C++

This is a work in progress... how can I replace () with \[\]? Is it possible?

```
#include <iostream>
using namespace std;

#define _____(a) int main(){a return 0;}
#define ___(y) cin>>y;
#define __(x) cout<<x<<endl;
#define ______(z) z+=42;
#define ________(p) int p;

_____(________(_) ___(_) ______(_) __(_) ___(_))

```

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


# Question
Title: Print an ascii spiral in O(log n) memory
You may write a program or function that receives an *odd, positive integer* `n`, where `n >= 3`, as either a function argument, command line arguments, or on STDIN (or equivalent for your system), and prints to STDOUT (or system equivalent) an ASCII spiral that spins inward clockwise where the **top** edge is exactly `n` characters long. The first right edge should be `n+1` characters long, obviously. For instance,

## Input:

11

## Output:

```
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

```

## The catches:

* Your program must use no more than `O(log n)` memory.
* Your program may only print the characters `*` (ASCII 42),  (ASCII 32), `<CR>` (ASCII 13) and `<LF>` (ASCII 10).
* Your program must print the string, not return it from the function.
* The Big-O restriction is only on **memory**, there are **no** restrictions on **runtime**.
* A trailing newline is optional.
* If your language does not support large integer types, you do not have to support higher than what it does support, but you may not use this as a trick to say "oh, well, I don't have to support above X so I can just make a huge array the maximum size every time"

Standard loopholes are banned, as usual.

# Answer
> 9 votes
# C, ~~125~~ 121 bytes

**Golfed version** This has no variable `k`. The variable `k` is used in the ungolfed version just to aid readability. Also `for` loop conditionals are rearranged and one set of unnecessary `{}` removed. Another set of `{}` can be removed by migrating `puts("")` inside the brackets of the `j` loop in the initialization position, but this would mean a newline at the beginning of the output, so I haven't done it.

```
f(n){int i,j;n/=2;for(i=-n-2;i++-n-1;){if(i){for(j=-n-1;j++-n;)putchar(32+10*(n+(j*j<i*i?i:j+(i!=j|i>0))&1));puts("");}}}

```

Prints an `n` wide by `n+1` high spiral like the example.

**Explanation**

Basically I halve the value of `n` (rounding down) and run two loops: an outer one `i` from `-n/2-1` to `n/2+1` to print the rows (`i=0` is suppressed so we get `n+1` rows) and an inner one `j` from (`-n/2` to `n/2` to print the characters.) We use `expression & 1` to print stripes, and the condition `j*j<i*i` to decide whether to print vertical or horizontal stripes (vertical at the sides where absolute magnitude of `i` is larger, and horizontal at the top and bottom.) An adjustment `+n` is required to help with the correct termination depending on whether `n/2` is odd or even.

`k` is normally 1, and provides an adjustment for the fact that the absolute values of `i` range from 1 to `n/2+1` while the absolute values of `j` range from 0 to `n/2`. If `k` was always 1 we would get concentric rectangles, but it is inverted to 0 when `i==j&i<=0` so that a diagonal row of cells is inverted, producing the spiral.

**ungolfed in test program**

```
f(n){
  int i,j,k;
  n/=2;
  for(i=-n-1;i<=n+1;i++){
    if(i){
       for(j=-n;j<=n;j++){
           k=i!=j|i>0;
           putchar(32+10*(n+(j*j<i*i?i:k+j)&1));
         }
       puts("");
     }
  }
}

int m;
main(){
  scanf("%d",&m);
  f(m);
}

```

**Output**

```
11
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

9
*********
        *
******* *
*     * *
* *** * *
* * * * *
* *   * *
* ***** *
*       *
*********

3
***
  *
* *
***

1
*
*

```

# Answer
> 7 votes
# C, 118 bytes

```
m,p,x,y,d;f(n){for(m=n++/2;p<n*n;x=p%n-m,y=p++/n-m,d=y==x+1&x<0,y-=y>0,d+=x*x>y*y?x:y,putchar(x>m?10:(d+m)%2?32:42));}

```

Code before final golfing:

```
#include <stdio.h>

int m, p, x, y, d;

int f(int n) {
    for (m = n++ / 2; p < n * n; ) {
        x = p % n - m;
        y = p++ / n - m;
        d = y == x + 1 && x < 0;
        y -= y > 0;
        d += x * x > y * y ? x : y;
        if (x > m) {
            putchar(10);
        } else if ((d + m) % 2) {
            putchar(32);
        } else {
            putchar(42);
        }
    }

    return 0;
}

```

The key observation is that the pattern is *almost* a series of concentric squares. With a couple of slight wrinkles:

* The y-size is one larger than the x-size. This is corrected by subtracting 1 from y for the lower half, which essentially repeats the middle row.
* To turn the rectangles into a spiral, the pixels along the `y = x + 1` diagonal need to be inverted up to the middle of the shape.

For the rest, the code is simply looping over all positions, calculating the Chebyshev distance from the center for each position, and emitting one of the two characters depending on the distance being even or odd. And emitting a newline for the last position of each line.

Since there are only a few scalar variables, and characters are emitted one by one, memory usage is obviously constant.

# Answer
> 3 votes
# C++, 926 bytes

```
#include<iostream>
#include<string>
#include<math.h>
#define S string
using namespace std;S N(S x,int y){S z="";for(int q=0;q<y;q++){z+=x;}return z;}int main(){int n=0,t=0,g=0,fi=1;cin>>n;int t1[]={0,0,n,0};int t2[]={0,n-2,n-2,1};for(int k=0;k<n+1;k++){if((k>(n-2)/2)&&(k<(n+5)/2)){if(g==0){S d,e;if(!((n+1)%4)){cout<<N("* ",t2[0])<<"  *"<<N(" *",t2[0])<<endl<<N("* ",(n+1)/2)<<endl<<N("* ",t2[0])<<"***"<<N(" *",t2[0])<<endl;t2[2]=n-8-(n-11);t1[2]=n-4-(n-11);t1[0]--;t2[3]--;t1[3]-=2;}else{cout<<N("* ",t1[0])<<"***"<<N(" *",t2[0])<<endl<<N("* ",(n+1)/2)<<endl<<N("* ",t1[0])<<"*  "<<N(" *",t2[0])<<endl;t2[0]--;t1[2]+=2;t2[2]+=6;t1[3]--;t2[1]-=2;t2[3]-=2;}fi=0;}g=5;}else{t=1-t;int*tR;tR=t?t1:t2;cout<<N("* ",tR[0])<<N(t?"*":" ",tR[2])<<N(" *",tR[3])<<endl;if(fi){if(t){t1[0]+=k==0?0:1;t1[2]-=k==0?2:4;t1[3]++;}else{t2[0]++;t2[2]-=4;t2[3]++;}}else{if(t){t1[0]--;t1[2]+=4;t1[3]--;}else{t2[0]--;t2[2]+=4;t2[3]--;}}}}return 0;}

```

This is not elegant, but it doesn't take up much memory for large n. Furthermore, there are (almost certainly) about 20 characters that can be further golfed, but I can't stand to look at it anymore.

### Short Explanation:

This splits the lines in the spirals into two types: the ones with \****** in the middle, and the ones with \s\s\s\s\s in the middle. Then it is clear that each line is composed of several "\* "s, the middle, and some " \*". Figuring out exactly how many of each thing is simple if you look at the pattern for long enough. The tricky thing was printing the center of the spiral which I basically hard coded using a conditional. This ended up being useful because the \*** and \s\s\s lines switch being odd/even there.

### Tests:

**Input:** `55` (I think the big ones look coolest)

**Output:**

```
*******************************************************
                                                      *
***************************************************** *
*                                                   * *
* ************************************************* * *
* *                                               * * *
* * ********************************************* * * *
* * *                                           * * * *
* * * ***************************************** * * * *
* * * *                                       * * * * *
* * * * ************************************* * * * * *
* * * * *                                   * * * * * *
* * * * * ********************************* * * * * * *
* * * * * *                               * * * * * * *
* * * * * * ***************************** * * * * * * *
* * * * * * *                           * * * * * * * *
* * * * * * * ************************* * * * * * * * *
* * * * * * * *                       * * * * * * * * *
* * * * * * * * ********************* * * * * * * * * *
* * * * * * * * *                   * * * * * * * * * *
* * * * * * * * * ***************** * * * * * * * * * *
* * * * * * * * * *               * * * * * * * * * * *
* * * * * * * * * * ************* * * * * * * * * * * *
* * * * * * * * * * *           * * * * * * * * * * * *
* * * * * * * * * * * ********* * * * * * * * * * * * *
* * * * * * * * * * * *       * * * * * * * * * * * * *
* * * * * * * * * * * * ***** * * * * * * * * * * * * *
* * * * * * * * * * * * *   * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * {-- my program adds a space here btw
* * * * * * * * * * * * * *** * * * * * * * * * * * * *
* * * * * * * * * * * * *     * * * * * * * * * * * * *
* * * * * * * * * * * * ******* * * * * * * * * * * * *
* * * * * * * * * * * *         * * * * * * * * * * * *
* * * * * * * * * * * *********** * * * * * * * * * * *
* * * * * * * * * * *             * * * * * * * * * * *
* * * * * * * * * * *************** * * * * * * * * * *
* * * * * * * * * *                 * * * * * * * * * *
* * * * * * * * * ******************* * * * * * * * * *
* * * * * * * * *                     * * * * * * * * *
* * * * * * * * *********************** * * * * * * * *
* * * * * * * *                         * * * * * * * *
* * * * * * * *************************** * * * * * * *
* * * * * * *                             * * * * * * *
* * * * * * ******************************* * * * * * *
* * * * * *                                 * * * * * *
* * * * * *********************************** * * * * *
* * * * *                                     * * * * *
* * * * *************************************** * * * *
* * * *                                         * * * *
* * * ******************************************* * * *
* * *                                             * * *
* * *********************************************** * *
* *                                                 * *
* *************************************************** *
*                                                     *
*******************************************************

```

**Input:** `3`

**Output:**

```
***
  *
* *
***

```

Note: I am not a computer scientist/CS student, and I don't know how to prove that this uses O(log n) memory. I can only work out what to do based on the links in the question. I would be grateful if someone could confirm/deny if this answer is valid. My logic for this answer's validity is that it never stores any variable of size based on n except the input itself. Instead, a for loop that runs n times computes integer values based on n. There are the same number of those values regardless of the input.

Note2: This doesn't work for n=1 because of my method of dealing with the middle. This would be easy to fix with conditionals, so if anyone is within a few characters of my answer, I'll fix it ;)

Play with it on ideone.

# Answer
> 3 votes
# Haskell, 151 bytes

```
(#)=mod
f n=[[if y<= -(abs$x+1)||y>abs x then r$y#2/=n#2 else r$x#2==n#2|x<-[-n..n]]|y<-[-n-1..n+1],y/=0]
r b|b='*'|1<2=' '
p=putStr.unlines.f.(`div`2)

```

Usage example:

```
*Main> p 9
*********
        *
******* *
*     * *
* *** * *
* * * * *
* *   * *
* ***** *
*       *
*********

*Main> p 11
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

```

Thanks to Haskell's laziness this runs within constant memory. It uses the obvious approach, i.e. looping over `y` and `x` and choosing between `*` and , depending on

* if the current position is above or below a diagonal
* `x` resp. `y` is even or odd
* `n/2` is even or odd

# Answer
> 2 votes
# Common Lisp - 346

```
(lambda(n &aux(d 0))(tagbody $ #6=(#7=dotimes(i n)#4=(princ"*"))#2=(#7#(i d)#5=(princ" ")#4#)#3=(terpri)#1=(#7#(i d)#4##5#)(when(> n 0)(#7#(i(1- n))#5#)#4#)#2##3#(when(> n 3)#1##4##4#(incf d)(decf n 4)(go $))(go /)@(decf d)(incf n 4)(when(> n 3)#2##5##4##3#)/ #1#(when(> n 0)#4#)(when(> n 1)(#7#(i(- n 2))#5#)#4#)#2##3##1##6#(when(> d 0)(go @))))

```

Iterative solution with constant memory usage. The above makes heavy uses of `#n=` and `#n#` reader variables. Even though there are more direct approaches, here I started with a recursive function and modified it to simulate recursion with `goto` statements: this is probably unreadable.

Output for all input values from 0 to 59.

### Original recursive version, with debugging informations

(note: `terpri` means `newline`)

```
(defun spiral (n &optional (d 0) )
  (flet ((prefix ()
           (format t "~4d~4d | " n d)
           (dotimes (i d)
             (princ "a ")))
         (postfix ()
           (dotimes (i d)
             (princ " b"))))
    (when (= d 0) (prefix))
    (dotimes (i n) (princ "c"))
    (postfix)
    (terpri)

    (prefix)
    (when (> n 0)
      (dotimes (i (1- n)) (princ " "))
      (princ "d"))
    (postfix)
    (terpri)

    (when (> n 3)
      (prefix)
      (princ "**")
      (spiral (- n 4) (1+ d))
      (postfix)
      (princ " f")
      (terpri))

    (prefix)
    (when (> n 0)
      (princ "g"))

    (when (> n 1)
      (dotimes (i (- n 2)) (princ " "))
      (princ "h"))
    (postfix)
    (terpri)

    (prefix)
    (dotimes (i n) (princ "i"))
    ))

```

For example:

```
(spiral 8)

   8   0 | cccccccc
   8   0 |        d
   8   0 | **cccc b
   4   1 | a    d b
   4   1 | a ** b b
   0   2 | a a  b b
   0   2 | a a  b b
   0   2 | a a  b f
   4   1 | a g  h b
   4   1 | a iiii f
   8   0 | g      h
   8   0 | iiiiiiii

```

See also this paste with all results from 0 to 59 (not the same as above, this one is more verbose).

### Iterative version, with debugging informations

```
(defun spiral (n &aux (d 0) )
  (flet ((prefix ()
           (format t "~4d~4d | " n d)
           (dotimes (i d)
             (princ "a ")))
         (postfix ()
           (dotimes (i d)
             (princ " b"))))
    (tagbody
     step-in
       (when (= d 0) (prefix))
       (dotimes (i n) (princ "c"))
       (postfix)
       (terpri)

       (prefix)
       (when (> n 0)
         (dotimes (i (1- n)) (princ " "))
         (princ "d"))
       (postfix)
       (terpri)

       (when (> n 3)
         (prefix)
         (princ "**")

         (incf d)
         (decf n 4)
         (go step-in))

       (go skip)

     step-out
       (decf d)
       (incf n 4)
       (when (> n 3)
         (postfix)
         (princ " f")
         (terpri))

     skip
       (prefix)
       (when (> n 0)
         (princ "g"))

       (when (> n 1)
         (dotimes (i (- n 2)) (princ " "))
         (princ "h"))
       (postfix)
       (terpri)

       (prefix)
       (dotimes (i n) (princ "i"))
       (when(> d 0)(go step-out)))))

```

# Answer
> 2 votes
# CJam, 72 bytes

```
li_2/:M;)__*{1$mdM-\M-_2$)=2$0<*@_*@_0>-_*e>mQ_M>2*@@+M+2%+'#S+N+N+=o}/;

```

This is fairly direct conversion of my C solution to CJam. Not as short as you would normally expect from a CJam solution, but this one really suffers from the memory restriction. The common benefits of building up results on the stack that gets dumped automatically at the end, and using fancy list/string operations, all go out the window. This generates and outputs the solution one character at a time. The stack only contains a few integers at runtime, and is empty at the end.

Even though it's not a great display of using a golfing language, it's still considerably shorter than the C code just because the notation is more compact.

Explanation:

```
li    Get input n.
_2/   Calculate n/2.
:M;   Store it in variable M
)__*  Calculate (n+1)*(n+1), which is the total number of output characters.
      Also keep a copy of n+1 on the stack.
{     Start loop over output character positions.
  1$md  Calculate divmod of position with n+1. This gives y and x of position.
  M-    Subtract M from x.
  \M-   Subtract M from y.
  _     Copy y.
  2$)   Calculate x+1.
  =     Check if y == x+1
  2$0<  Check if x < 0.
  *     Multiply the two check results. This is the result of the flip
        condition for the top-left diagonal to turn the rectangles into a spiral.
  @_*   Calculate x*x.
  @_    Get y to top of stack, and copy it.
  0>-   Subtract 1 from y if it is in the bottom half.
  _*    Calculate y*y.
  e>    Take maximum of x*x and y*y...
  mQ    ... and calculate the square root. This is the absolute value of the
        larger of the two.
  _M>   Check if the value is greater M, which means that this is the
        position of a line end.
  2*    Multiply by 2 so that we can add another condition to it later.
  @     Get result of diagonal flip condition to the stack top.
  @     Get max(x,y) to the top.
  +M+   Add the two, and add M to the whole thing. This value being even/odd
        determines if the output is a # or a space.
  2%    Check if value is odd.
  +     Add to line end condition to get a single ternary condition result.
  '#S+N+N+
        Build string "# \n\n".
  =     Use the condition result to pick the output character out of the string.
  o     Output the character.
}/    End loop over output characters.
;     Pop n+1 value off stack, to leave it empty.

```

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


title: Dice adventure in the river Styx

text:
# Question
Title: Dice adventure in the river Styx
You're sitting in the school cafeteria, microwaving your food like you always do around lunch. Suddenly the programming devil rises from the ashes of your burnt food and proposes a challenge:

> Sup guys, I have a challenge.

How did this happen? What did you ever do wrong? Was it that one bad macro in C?

The programming devil demands a game of dice:

> I demand a game of dice.

Strictly speaking, it is not a game of dice. The programming devil just wants you to calculate the mean value of throwing a die `n` times. The programming devil's twist is that the die can, and always will, have a number of faces larger than `n`.

## Challenge:

Write a program which calculates and outputs the mean value of `n` throws with a die with a number of faces greater than `n`.

## Input:

Two positive integers. The first argument determines the number of throws, the second argument the number of faces of the die. There is no empty input - always two integers.

## Output:

The mean value of throwing the dice `n` times rounded to the closest integer.

## Requirements:

* No output if the number of faces of the die is less than or equal to the number of throws.
* The values returned from throwing the die has to be random (*as close as we can get to random, that is*)

The programming devil thinks this is great and will restore the burnt food of the programmer which writes the shortest code in bytes to solve his challenge:

> This is a great challenge. I will restore your food if you propose the shortest program in bytes to me.

# Answer
# Ostrich 0.7.0, ~~18~~ 23 chars

Two solutions, identical in length:

```
:x;.,{;xR*C}%_+*\/o2/+F
\:x{.R*C\}*;]_+*x/o2/+F

```

Edit: +5 characters to each because I forgot to round to the nearest integer.

They both actually simulate rolling the dice (and thus have non-constant output), which seems to be the intent of the challenge.

Explanation of #1:

```
:x;     store the number of faces in x, pop from stack
.,      create range from 0 to [number of rolls] (while keeping #rolls on stack)
{...}%  map over that range...
  ;       discard the number
  xR*     generate a float between 0 and [number of faces]
  C       take ceil, which will make this an int between 1 and [#faces]
_+*     reduce by {+} (_ is the syntax for a single-instruction block) a.k.a. sum
\/      swap top two stack elements (bringing the number of rolls to the top),
          then divide, resulting in the average

```

Explanation of #2:

```
\       bring the number of rolls to the top
:x      store number of rolls in x, but don't pop from the stack
{...}*  that many times...
  .       duplicate the number of faces
  R*C     get the random number as described in #1
  \       stick that under the number of faces again, so [#faces] is still on top
;       discard the extra [#faces]
]_+*    wrap stack in an array, sum
x/      divide by [#rolls]

```
> 2 votes

# Answer
# TI-BASIC, ~~16~~ ~~20~~ 19 bytes

Straightforward. The +8/-1 consensus on meta is that mixing inputs is allowed—so `Ans`, from command-line input, is the number of faces, and `N` is the number of throws.

```
Input N
If N<Ans
int(mean(1.5+int(Ansrand(N

```
> 2 votes

# Answer
# APL, 13 bytes

```
{0⍕⍺÷⍨+/?⍵⍴⍺}

```

This creates an unnamed dyadic function where the left argument  is the number of throws and the right argument  is the number of die faces. Here we sum (`+/`)  random numbers between 1 and  (`?⍵⍴⍺`) and divide that by  (`⍺÷⍨`). The result is rounded to the nearest integer (`0⍕`).

You can try it online.

Note that this still produces output even when the number of throws is greater than the number of faces. But per the challenge rules, that does not constitute valid input (*"The die can, and always will, have a number of faces larger than `n`."*).
> 1 votes

# Answer
# Pyth - 17 bytes

I'm sure it can be shorter, but the checking is stopping me from putting it in a lambda.

```
I>QKvz.RcsmhOQKKZ

```

Try it here online.

## Or if the second interpretation of the rules is correct, 12 bytes.

Same thing but in a lambda.

```
M.RcsmhOHGGZ

```

Try it here online.
> 1 votes

---
Tags: code-golf
---


title: Leap for Leap Seconds!

text:
# Question
Title: Leap for Leap Seconds!
Since today marks the occasion of the 26th leap second ever to occur, your challenge will be to output the date and time of every leap second in GMT or UTC that has occurred so far, as well as the one to occur today.

### Input

There is no input.

### Output

```
1972-06-30 23:59:60
1972-12-31 23:59:60
1973-12-31 23:59:60
1974-12-31 23:59:60
1975-12-31 23:59:60
1976-12-31 23:59:60
1977-12-31 23:59:60
1978-12-31 23:59:60
1979-12-31 23:59:60
1981-06-30 23:59:60
1982-06-30 23:59:60
1983-06-30 23:59:60
1985-06-30 23:59:60
1987-12-31 23:59:60
1989-12-31 23:59:60
1990-12-31 23:59:60
1992-06-30 23:59:60
1993-06-30 23:59:60
1994-06-30 23:59:60
1995-12-31 23:59:60
1997-06-30 23:59:60
1998-12-31 23:59:60
2005-12-31 23:59:60
2008-12-31 23:59:60
2012-06-30 23:59:60
2015-06-30 23:59:60

```

### Rules

Since I doubt there are many built-ins that allow leap-seconds, I'll allow them.

Standard loopholes are disallowed.

Shortest code wins.

Date format must have a zero-padded month and a 4-digit year, as well as military time and a space separating the time from the date. Putting `UTC` at the end is optional. Your choice of dashes or slashes.

EDIT: Yep as predicted, this became an encoding challenge. If only encoding could fix the leap second problem, ...then all our code would be much more practical. Maybe we need some ideas for more fun challenges with practical uses?

# Answer
# CJam, ~~72~~ ~~70~~ ~~69~~ 64 bytes

```
26,"~g¼K&Béx¸¦Ø"240bFbf{<1b2md\1972+'-@6X$4*-'-Z3$" 23:59:60"N}

```

Try it online in the CJam interpreter.

### Idea

We start by encoding each leap second as **2 * (Y - 1972) + D**, where **D** is **1** if it occurs in December and **0** otherwise.

The array of all encoded leap seconds is:

```
[0 1 3 5 7 9 11 13 15 18 20 22 26 31 35 37 40 42 44 47 50 53 67 73 80 86]

```

Let's call this array **L**.

Since the array is in ascending order, we can store the consecutive differences instead of the actual numbers:

```
[1 2 2 2 2 2 2 2 3 2 2 4 5 4 2 3 2 2 3 3 3 14 6 7 6]

```

Treating this array as the digits of a base 15 number, we obtain the integer

```
19238985373462115979359619336

```

which digits in base 240 (cast to characters) are

```
~g¼K&Béx¸¦Ø

```

### Code

```
26,             e# Push I := [0 ... 25].
"~g¼K&Béx¸¦Ø"   e# Push the string from above.
240bFb          e# Convert from base 250 to base 15 to push L.
f{              e# For each J in I:
                e#   Push L.
  <             e#   Replace L with L[:J].
  1b            e#   Push the sum S of the integers in L[:J].
  2md           e#   Push (S / 2) and (S % 2).
  \1972+        e#   Add 1972 to (S / 2).
  '-@           e#   Push '-' and rotate (S % 2) on top.
  6X$4*-        e#   Compute (6 - 4 * (S % 2)).
  '-Z           e#   Push '-' and 3.
  3$            e#   Push a copy of (S % 2).
  " 23:59:60"   e#   Push that string.
  N             e#   Push a linefeed.
}

```
> 25 votes

# Answer
# R, ~~78~~ 75 bytes

Built-ins, you say? Well...

```
message(paste(as.Date(.leap.seconds)-1,"23:59:60\n"),"2015-06-30 23:59:60")

```

R has an automatic variable `.leap.seconds` which contains the date and time of each leap second insertion, given in the system's local time. As of R version 3.2.0, this does not include today, so I've added that manually.

Ungolfed + explanation:

```
# Convert the datetime values to UTC dates. These will be a day past the
# expected output, so we can subtract 1 to get what we want.
dates <- as.Date(.leap.second) - 1

# Paste the UTC time and a newline onto the end of each date
datetimes <- paste(dates, "23:59:60\n")

# Print each time, including today, on its own line
message(datetimes, "2015-06-30 23:59:60")

```

You can try it online!
> 35 votes

# Answer
# HTML, 594 bytes

```
1972-06-30 23:59:60<br>1972-12-31 23:59:60<br>1973-12-31 23:59:60<br>1974-12-31 23:59:60<br>1975-12-31 23:59:60<br>1976-12-31 23:59:60<br>1977-12-31 23:59:60<br>1978-12-31 23:59:60<br>1979-12-31 23:59:60<br>1981-06-30 23:59:60<br>1982-06-30 23:59:60<br>1983-06-30 23:59:60<br>1985-06-30 23:59:60<br>1987-12-31 23:59:60<br>1989-12-31 23:59:60<br>1990-12-31 23:59:60<br>1992-06-30 23:59:60<br>1993-06-30 23:59:60<br>1994-06-30 23:59:60<br>1995-12-31 23:59:60<br>1997-06-30 23:59:60<br>1998-12-31 23:59:60<br>2005-12-31 23:59:60<br>2008-12-31 23:59:60<br>2012-06-30 23:59:60<br>2015-06-30 23:59:60

```

¯\\\_(ツ)\_/¯
> 24 votes

# Answer
# C, ~~160~~ ~~146~~ ~~141~~ 140 bytes

First time posting, not sure what "standard loopholes" are. I have printf warnings of course.

**160 bytes:**

The original idea is to encode leap seconds using two bits per year: one for June and one for December. The encoding is consumed one bit at a time by the inner while loop. Without a 128-bit integer, the outer while loop is necessary. The rest is all bookkeeping and math. :-)

```
int main(){long long X=0x2495288454AAAB,Y=1972,Z=1;while(Y<2000){while(X){if(X&1)printf("%d-%02d-%d 23:59:60\n",Y,6*(2-Z),31-Z);Y+=Z^=1;X>>=1;}X=0x104082000;}}

```

**141 bytes:**

Applying the suggested tips gets it down to 146 bytes. Then I found a way to simplify the outer while condition (from Y\<2000 to just Z), bringing it down to 141 bytes. So close to a tweet!

```
main(Z){long long X=0x2495288454AAAB,Y=1972;while(Z){while(X)X&1?printf("%d-%02d-%d 23:59:60\n",Y,12-6*Z,31-Z):1,Y+=Z^=1,X/=2;X=4362608640;}}

```

**140 bytes:**

I noticed the dash in the date could be eliminated by making the day negative. Can't do it with the month as well due to leading zero in June. But at least it fits in a tweet now!

```
main(Z){long long X=0x2495288454AAAB,Y=1972;while(Z){while(X)X&1?printf("%d-%02d%d 23:59:60\n",Y,12-6*Z,Z-31):1,Y+=Z^=1,X/=2;X=4362608640;}}

```

**Pretty version:**

```
main(Z) {
    long long X = 0x2495288454AAAB, Y = 1972;
    while (Z) {
        while (X)
            X&1 ? printf("%d-%02d%d 23:59:60\n", Y, 12-6*Z, Z-31) : 1,
            Y += Z ^= 1,
            X /= 2;
        X = 4362608640;
    }
}

```

**Bonus version:**

I eliminated the outer loop by bit-shifting one 64-bit integer into another, but it's 150 bytes, due to the rather long "unsigned long long"; if I could use something like "uint64" it would be 138 bytes.

```
main(Z) {
    unsigned long long Y = 1972, X = 0x2495288454AAAB, W = 8520720;
    while (X)
        X&1 ? printf("%d-%02d-%d 23:59:60\n", Y, 12-6*Z, 31-Z) : 1,
        Y += Z^= 1,
        X = X/2 | (W>>=1)<<63;
}

```
> 11 votes

# Answer
## Python 3, 91

Uses the encoding and string formatting by Sp3000, but stores the values in a Python 3 bytes object rather than a magic number.

```
for n in b'()+-/1357:<>BGKMPRTWZ]kqx~':print('%d-%02d-3%d 23:59:60'%(1952+n/2,n%2*6+6,n%2))

```

The encoding only needs 86 of the 256 possible values of a bytes, so a range of printable characters is used to make it look nicer.
> 9 votes

# Answer
# Brainfuck, 806

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

```

You can run it on this online interpreter.
> 7 votes

# Answer
# Python 2, ~~111~~ 104 bytes

```
n=0x6697f252225354422533333330;y=1972
while n:print'%d-%02d-3%d 23:59:60'%(y,n%2*6+6,n%2);y+=n/2%8;n/=16

```

Base encoding and more base encoding.
> 6 votes

# Answer
# GNU sed+date: 112

Common Linux distributions have the leap seconds built-in, too. Using GNU sed and date:

```
sed -n 's/^\([0-9]\+\).*/1899-12-31 \1sec/p' /usr/share/zoneinfo/leap-seconds.list|date -f- +"%Y-%m-%d 23:59:60"

```

# GNU sed+date: 90

Safing a few characters by cutting the path:

```
sed -n 's/^\([0-9]\+\).*/1899-12-31 \1sec/p' /u*/s*/z*/leap*|date -f- +'%Y-%m-%d 23:59:60'

```

# GNU sed+date tuned by Toby Speight: 84

Deeply golfed version proposed in the comments:

```
sed -nr 's/^([0-9]+).*/date -d "1899-12-31 \1sec" "+%F 23:59:60"/ep' /u*/s*/z*/leap*

```
> 5 votes

# Answer
# JavaScript (*ES6*) 125

The newline inside \`\` is significant and counted.

To test, run the snippet below (being EcmaScript 6, Firefox only)

```
alert([..."09:;=DEFIX[01234567?ABGJQS"].map((c,i)=>c.charCodeAt()+1924+(i>10?'-12-31':'-06-30')+' 23:59:60').sort().join`
`)
```
> 3 votes

# Answer
# PHP, 198 bytes

```
foreach([.5,1,2,3,4,5,6,7,8,9.5,10.5,11.5,13.5,16,18,19,20.5,21.5,22.5,24,25.5,27,34,37,40.5,43.5] as$d){$h=(int)$d-ceil($d);echo date("Y-m-d 23:59:60",mktime(0,0,0,-6*$h,31+$h,(int)$d+1972))."\n";}

```

Unfortunately, I don't know if I can insert `\n` in the date function. If so, this is 3 bytes less because of `.""`.
> 2 votes

# Answer
# 8086 machine code + DOS, 92 bytes

Hexdump of the code:

```
BE 3A 01 B1 57 D1 E0 75 03 AD EB F9 72 09 50 BA
47 01 B4 09 CD 21 58 BB 50 01 81 77 FC 01 04 80
37 01 80 3F 31 74 10 83 EB 05 4B FE 07 80 3F 3A
75 05 C6 07 30 EB F3 E2 CC C3 AA 2A 77 B5 6A DD
DF B6 BE FF 7D BF 31 39 37 32 2D 30 36 2D 33 30
20 32 33 3A 35 39 3A 36 30 0D 0A 24

```

To run, write the 92 bytes into a `com`-file and run under 32-bit Windows or DOSBox.

The code uses a bitmap with 87 bits, one per half a year. The bits are arranged into groups of 16, starting from MSB.

Decoding the bitmap:

```
                 ; when the program starts, ax=0 (tested on DOSBox)
myloop:
    shl ax, 1    ; shift the MSB left into the carry flag
    jnz mywork   ; if some bits are left in the register, work normally
    lodsw        ; if all bits were shifted out, load the next 16 bits
    jmp myloop   ; and check the MSB again

```

Because of the code's structure, some bits are lost during decoding, so I had to repeat them. This repeating doesn't bloat the bitmap because I had to pad 87 bits to 96 bits anyway.

After printing (or not printing) the leap second, the code increases the date by half a year, using manipulations on the ASCII codes of the output message.

Source code (can be assembled with `tasm`):

```
    mov si, offset mydata
    mov cl, 57h ; number of iterations

myloop:
    shl ax, 1   ; shift the MSB left into the carry flag
    jnz mywork  ; if some bits are left in the register, work normally
    lodsw       ; if all bits were shifted out, load the next 16 bits
    jmp myloop  ; and check the MSB again
mywork:
    jc myinc_date ; shifted bit 1? - skip printing the message

    push ax
    mov dx, offset mymsg
    mov ah, 9
    int 21h     ; print the message
    pop ax

myinc_date:
    mov bx, offset mymsg + 9 ; pointer to the middle of the message
    xor word ptr [bx - 4], 401h ; change month 06<->12
    xor byte ptr [bx], 1 ; change day 30<->31
    cmp byte ptr [bx], '1'
    je myloop_end ; if 31 December, no need to increase the year
    sub bx, 5 ; pointer beyond the last digit of the year

myinc_year:
    dec bx
    inc byte ptr [bx] ; increase the digit
    cmp byte ptr [bx], '0' + 10
    jne myloop_end ; if the digit was less than 9, done
    mov byte ptr [bx], '0' ; set the digit to 0
    jmp myinc_year ; continue increasing other digits

myloop_end:
    loop myloop
    ret ; terminate the program

; In the following bitmap, the spaces before some LSBs
; show that the least significant 1-bit and all
; following 0-bits are lost during decoding.
mydata:
    dw 02aaah ; 00101010101010     10
    dw 0b577h ; 101101010111011    1
    dw 0dd6ah ; 11011101011010     10
    dw 0b6dfh ; 101101101101111    1
    dw 0ffbeh ; 11111111101111     10
    dw 0bf7dh ; 101111110111110    1

mymsg:
    db '1972-06-30 23:59:60',13,10,'$'

```
> 2 votes

# Answer
# Python 2, ~~123~~ ~~121~~ ~~116~~ ~~114~~ 111

I've managed to get it pretty short, but I'm not sure how much shorter it can get. I tried using `exec`, but the formatting gets to be too costly.

I used a base 16 encoding of the table from the linked Wikipedia page.

Edit: Using hex encoding is shorter than base 36 (see the less golfed version.)

**Try it here**

```
n=0x410208002495288454aaab
for i in range(88):
    if n%2:print"%d-%02d-3%d 23:59:60"%(1972+i/2,i%2*6+6,i%2)
    n/=2

```

Less golfed:

```
s=bin(int('WELD24ZDGIMBWWLFM',36))[2:]
for i in range(44):
    t,s=int(s[0]),s[1:]
    if t:print"%d-06-30 23:59:60"%(i+1972)
    t,s=int(s[0]),s[1:]
    if t:print"%d-12-31 23:59:60"%(i+1972)

```
> 1 votes

# Answer
# Pyth - 88 84 bytes

Converts to char to compress the data and saves the `06-30` versus `12-31` data as binary number.

```
jbm++-2047ed?"-06-30"hd"-12-31"" 23:59:60"C,j33678243 2CM"KKJIHGFEDBA@><:9765421*'#

```

(there is a space there at the end)

Try it here online.
> 1 votes

# Answer
# Python, 204 201

```
e,g,h=0,1972,0
for i in range(1,27):e,g,h={2:1,9:2,10:1,12:2,15:1,16:2,17:1,20:2,21:1,22:7,23:3,24:4,25:3}.get(i,e),g+e,(h,1-h)[i in[2,10,14,17,20,21,22,25]];print`g`+("-06-30","-12-31")[h]+" 23:59:60"

```

You can play with it on repl.it.

Edit: Thoroughly beaten! The compression answers are amazingly short.
> 1 votes

# Answer
# q/kdb+, ~~95~~ ~~94~~ 93 bytes

```
asc 1_" "0:([]raze("DEFGHIJKSUV[^eh";"DMNOQXYZ]lo"){("d"$"m"$-12*95-6h$x)-y}'1 185;`23:59:60)

```

**Explanation**

For each year **\+ 1**, encode for years since 1905 as an ASCII character, e.g.:

```
1972 -> 1973 -> 68 -> D

```

`6h$x` turns `"D"` back to `68`. Since `q`'s date epoch is `2000.01.01`, we subtract `95` and perform the integers-to-date conversion `"d"$"m"$-12*95-6h$x`.

The reason we **\+ 1** above is to subtract the number of days from the start of **next year** to get the *actual year's* 31st December or 30th June, namely 1 or 185 days. Therefore, `"DEFGHIJKSUV[^eh"` represents the years with a leap second in December, and `"DMNOQXYZ]lo"` for those in June. The pairing-subtraction is done via `(a;b){x-y}'(c;d)`, where `a` and `b` are years that will be subtracted by `c` and `d` number of days respectively.

`" "0:([]...)` prepares the results to give us the correct formatting, with a small caveat that a column header will be generated. `1_` drops that header and finally apply `asc` to get the ordering correct.

**edit**: 're-base' to subtracting 95 years instead of 100 (saving 1 character).

**edit 2**: re-ordering the operands' positioning inside the integers-to-date conversion function.
> 1 votes

# Answer
# C, ~~155~~ ~~149~~ 147 bytes

Here's another approach in C, using strings and run length encoding. Not quite as terse as my other C solution, but maybe it can be improved?

**155 bytes:**

Using a string to hold the month/day.

```
main(Y){Y=1972;char*M="06-3012-31",*B="#@DGCDF7D3daTdS#!",b,c;while(b=*B++-33){c=b>>1&7;while(c--)printf("%d-%.5s 23:59:60\n",Y++,M+b%2*5);Y+=(b>>4&7)-1;}}

```

**149 bytes:**

Eliminating the month/day string.

```
main(Y){Y=1972;char*B="#@DGCDF7D3daTdS#!",b,c;while(b=*B++-33){c=b>>1&7;while(c--)printf("%d-%02d-%d 23:59:60\n",Y++,6+b%2*6,30+b%2);Y+=(b>>4&7)-1;}}

```

**147 bytes:**

Eliminating the year initialization.

```
main(Y){char*B="#@DGCDF7D3daTdS#!",b,c;while(b=*B++-33){c=b>>1&7;while(c--)printf("%d-%02d-%d 23:59:60\n",1971+Y++,6+b%2*6,30+b%2);Y+=(b>>4&7)-1;}}

```

**144 bytes:**

If I reencoded the buffer to make the skip count apply before (not after) the run, then I could reorder the statements in the outer while loop, use the comma operator, and eliminate the braces, saving 2 bytes.

I can save another byte by making the day negative (as in my other solution).

**Pretty:**

```
main(Y) {
    char *B = "#@DGCDF7D3daTdS#!", // buffer of bytes encoding runs
         b, // current byte
         c; // current count
    while (b = *B++-33) { // get byte
        c = b>>1&7; // get count
        while (c--) printf("%d-%02d-%d 23:59:60\n", 1971+Y++, 6+b%2*6, 30+b%2); // run
        Y += (b>>4&7)-1; // skip years
    }
}

```

**Explanation:**

Runs are encoded in bytes. Each byte has one bit to say whether it's June or December, 3 bits for a length count, 3 bits for a skip count, and 1 unused high bit.

The skip count is the number of years to skip after a run; it's offset by -1 to allow for two leap seconds in 1972. The length is how many years in a run; it probably could be offset by +1 but it isn't currently.

So a byte means: "Do LENGTH years of JUNE (or DECEMBER) years of leap seconds, then skip SKIP-1 years" before moving to the next byte.

The bytes are offset by 33 to make them readable and avoid fancy encoding.

This means although we have enough skip bits to cover 1998-2005, we're out of ASCII range, so we have an extra zero length run. Also, 1979 appears on its own because the length 1972-1979 is one too long.

There's enough bits in the bytes, so those issues might be fixable ultimately.
> 1 votes

# Answer
# PHP, 164 bytes

```
foreach([.5,1,2,3,4,5,6,7,8,9.5,10.5,11.5,13.5,16,18,19,20.5,21.5,22.5,24,25.5,27,34,37,40.5,43.5]as$d){echo(ceil($d)+1971).($d%2?'-12-31':'-06-30')." 23:59:60\n";}

```

This is just a few modification on @Voitcus's idea
> 1 votes

# Answer
# Python, 221 217

```
def d(x):
 q=x%10
 if x%2==0:
  p,r=q/2,"06-30"
 else:
  p,r=(q-1)/2,"12-31"
 return"%d%d-%s 23:59:60"%(p+197,x/10,r)
for x in [20,21,31,41,51,61,71,81,91,12,22,32,52,73,93,5,24,34,44,55,74,85,57,87,28,58]:print(d(x))

```

# Some Insights

Basically, `d(x)` decompresses a vector of 3 integers from a single 2-digit integer. `d(x)` is constructed as the inverse function (over the 26 leap seconds datetimes) of `c(v)`, which in turn is a compression function that turns a 3-uple such as (1998,12,31) into a number like 85. To derive the list \[20,21...28,58\] I designed another algorithm to verify that the compression function is bijective over the domain. That is, I made sure that the following program doesn't produce duplicates, and I used its output as the list of the program above.

```
dates = [(1972,06,30),
    (1972,12,31),
    (1973,12,31),
    (1974,12,31),
    (1975,12,31),
    (1976,12,31),
    (1977,12,31),
    (1978,12,31),
    (1979,12,31),
    (1981,06,30),
    (1982,06,30),
    (1983,06,30),
    (1985,06,30),
    (1987,12,31),
    (1989,12,31),
    (1990,12,31),
    (1992,06,30),
    (1993,06,30),
    (1994,06,30),
    (1995,12,31),
    (1997,06,30),
    (1998,12,31),
    (2005,12,31),
    (2008,12,31),
    (2012,06,30),
    (2015,06,30)]

def c(v):
    x = (v[0] % 10) * 10
    x += v[2] % 30
    x += 2 * (int(v[0] / 10) - 197)
    return x

for v in dates:
    print(c(v))

```

The compression function `c(v)` was designed to be bijective by using a very simple scheme. Let's take as an example (1998,12,31).

* The expression (v\[0\] % 10) * 10 selects the units of the year (e.g. 1 9 9 **8** --\> 8) and makes it the tenths digit of the output (now x=80).
* There are only two month-day combination in which the leap second thing happens, so I decided to use the day component to distinguish between the 06,30 case and the 12,31 case. The expression v\[2\] % 30 is 0 if the day is 30, and is 1 if the day is 31. In our example, we add 1 to x (hence, now x=81).
* Finally, I observed that this puzzle involves only 5 decades; hence if I map the first decade (the seventies) to 0 and the last decade (the 2010s) to 4 I can do cool stuff. More specifically, if instead of mapping to 0,1,2,3,4 I map to 0,2,4,6,8 I can add this value to the units of x, which due to the previous rule is either 0 or 1. So in the end we have that also this last step doesn't screw the bijection, and we get that the units of a 06,30 case are one of 0,2,4,6,8 and that the units of a 12,31 case are one of 1,3,5,7,9. Hence the bijection is obvious. In our example, 1998 is in the third decade (70s-\>0, 80s-\>1, 90s-\>2) so we add 2\*2=4. So we get x=85.

I wrote the program to verify that this is true, and then I defined `d(x)` as the inverse of `c(v)`. In our example, c((1998,12,31)) is 85 and d(85) correctly prints `1998-12-31 23:59:60`.
> 0 votes

# Answer
**gzip, 114 bytes**

Hexdump:

1f8b080853f9975502006c006dd04b0a80300c84e1bde01dbc40218fa6697aff8309e2a6fa6f3f86cc10adb426a3b95ce62b6a0d398f07d59aeb8e4ed80983701026e1242cc0a9307e1aa11306615211b59710527b3961270cba9994fc7fc944829092faeedc313e7803993cfafb20020000

Create a file with the bytes described above.

Extract using gunzip or another decompression program to get a new file named "l". This file contains the desired output.
> -1 votes

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


# Question
Title: Rolling three dice and show the probabilities
Roll 3 dice, count the two highest two values and add them to the result. *Every 1 must be rolled **once** again.*

Now show the average throw after 1000000 tries and the probabilities for each result occurring:

# Desired Result:

> avg(9.095855)
> 2: 0.0023
> 3: 0.0448
> 4: 1.1075
> 5: 2.8983
> 6: 6.116
> 7: 10.1234
> 8: 15.4687
> 9: 18.9496
> 10: 19.3575
> 11: 16.0886
> 12: 9.8433

# Answer
# Mathematica 150 146 94 115 108

Edit: This version is a suggestion from @belisarius. Much shorter and faster than my own code (found in the earlier versions).

```
r=RandomInteger;t=Tr/@Rest/@Sort/@(5~r~{10^6,3}/. 0:>r[5]);
{Mean@t+2,{#[[1]]+2,#[[2]]/10^4}&/@Sort@Tally@t}//N

```

> {9.09684, {{2., 0.0028}, {3., 0.0456}, {4., 1.1097}, {5., 2.8752}, {6., 6.1246}, {7., 10.122},
> {8., 15.513}, {9., 18.8956}, {10., 19.3514}, {11., 16.074}, {12., 9.8861}}}
> 5 votes

# Answer
## APL ~~110~~ 103

```
r←11⍴0
i←1
l:r←r+(j←1+⍳11)=+/2↑n[⍒n←3↑((3↑x)~1),3↓x←?6⍴6]
i←i+1
→(i≤k←10*6)/l
((+/r×j)÷k)
j,[1.1]r÷10*4

```

I have included the results of three runs to demonstrate the degree of repeatability over 1000000 iterations.

```
9.092186    9.093053    9.093897
  2  0.0022   2  0.0019   2  0.0023
  3  0.0442   3  0.0477   3  0.0452
  4  1.1064   4  1.0755   4  1.0866
  5  2.8808   5  2.887    5  2.8771
  6  6.1472   6  6.1864   6  6.1485
  7 10.1532   7 10.1163   7 10.1575
  8 15.6376   8 15.5511   8 15.5834
  9 18.8736   9 18.918    9 18.873
 10 19.2771  10 19.3763  10 19.3315
 11 15.9702  11 16.0225  11 16.0529
 12  9.9075  12  9.8173  12  9.8419

```
> 4 votes

# Answer
## Python (~~207 194~~ 189)

```
from random import*
a=lambda:randint(13,48)/7
r=range
x=[0]*13
s=0
for i in r(10**6):b=sum(sorted([a(),a(),a()])[1:]);x[b]+=1e-4;s+=b/1e6
print'avg(%f)'%s
for i in r(2,13):print`i`+':',x[i]

```

Algorithm:

```
a is the RNG, x is the list which contains the results, s is the sum. r is for code-golfing purposes.
1. Iterate through steps 2-6 1,000,000 times:
2. Get three random numbers from `a` and put them in a list.
3. Sort the list. (list is now in ascending order)
4. Take the sum of every item but the first item in the list. Call this number b.
5. Increment the (b)th index of x by 1e-4 (1/10000).
6. Increment s by b * 1e-6 (1/1000000).
7. Print out s.
8. For each item in x (excluding the first two), output the item.

```
> 3 votes

# Answer
# APL, 67

```
÷1e2÷+/×/x←⍉↑n,1e4÷⍨+/(n←⊂⍳12)∘.={+/2↑x[⍒x←{⍵=1:?6⋄⍵}¨?3⍴6]}¨⍳1e6⋄x

```

### Explanation

* `⍳1e6` Create array from 1 to milliion,
* `¨` and for each of those
* `{+/2↑x[⍒x←{⍵=1:?6⋄⍵}¨?3⍴6]}` do a roll, re-roll 1s, and sum the high dices:

`?3⍴6` roll 3 dice,
`¨` and for each die
`{⍵=1:?6⋄⍵}` if it is a 1, replace it by a re-roll result, else don't change it.
`x←` Save the result in (local) variable `x`,
`x[⍒x`...`]` sort it in descending order,
`+/2↑` take the first 2 items (high dices) and return the sum.
* `+/(n←⊂⍳12)∘.=` Create array of the no. of times each sum appears,
* `1e4÷⍨` divide by 10000,
* `⍉↑n,` insert a row to the top with numbers 1 to 12, and matrix transpose it. The result would be something like the table in the question.
* `x←` Save that in (global) variable `x`.
* `+/×/` Calculate the average of the million rolls by multiplying the columns, summing those...
* `÷1e2÷` and divide by 100.

The result is displayed (by default)

* `⋄x` Finally, output `x`

### Example output

```
9.097008
 1  0
 2  0.0028
 3  0.0466
 4  1.0914
 5  2.8873
 6  6.0957
 7 10.1242
 8 15.6108
 9 18.8688
10 19.2834
11 16.0979
12  9.8911
```

### Notes

-5 chars if allowed to represent 10% by 0.1 instead of 10
-3 chars if allowed to use probabilistic approach (like o\_o's) instead of explicit re-roll
+12 chars if the "avg()" is required
+2 chars if the "1" row needs to be removed
+8 chars if the colon is required in output
> 2 votes

# Answer
## Python, 262

```
import random
r=random.randint
def f():n=r(1,6);return n if n>1 else r(1,6)
l=[0.0]*13
for i in range(10**6):l[sum(sorted([f(),f(),f()])[1:])]+=1
m=zip(*[range(2,13),l[2:]])
print'avg('+`sum([a*b for a,b in m])/10**6`+')'
for e in m:print`e[0]`+': '+`e[1]/10**4`

```

results:

```
avg(9.098773)
2: 0.0021
3: 0.044
4: 1.0872
5: 2.89
6: 6.0982
7: 10.133
8: 15.5
9: 18.949
10: 19.2908
11: 16.0953
12: 9.9104

```
> 1 votes

# Answer
# C# (599)

```
using System;using System.Collections.Generic;using System.Linq;namespace P{public class D{Random r=new Random(System.DateTime.Now.Millisecond);public static void Main(){var d=new D();d.G();}public int R(){return r.Next(1,7);}public int RD(){var e=new List<int>();for(var i=0;i<=2;i++){var v = R();e.Add(v != 1 ? v : R());}return e.OrderByDescending(d=>d).Take(2).Sum();}public void G(){const double l = 1000000;var t = new Dictionary<int,double>();for(var i=2;i<=12;i++)t.Add(i,0);for(var i=0;i<l;i++){var s=RD();t[s]=t[s]+1;}foreach(var a in t){Console.WriteLine(a.Key+": "+(a.Value)/10000.0);}}}}

```
> 1 votes

# Answer
## Perl (177 169 168)

```
sub r{1+int rand 6}
for(1..1e6){@l=sort map{($q=r)>1?$q:r}(1..3);++$s{$y=$l[1]+$l[2]};$t+=$y}
print"avg(".$t/1e6.")\n";print"$_: ".$s{$_}/1e4."\n"for sort{$a<=>$b}keys%s

```

*(NOTE: one-liner wrapped for clarity)*

stacked output of three consecutive runs:

```
avg(9.09432)  avg(9.094793)  avg(9.092179)
2: 0.002      2: 0.0026      2: 0.0023
3: 0.0448     3: 0.0454      3: 0.0436
4: 1.0872     4: 1.0904      4: 1.0944
5: 2.8834     5: 2.8933      5: 2.8842
6: 6.1387     6: 6.127       6: 6.1854
7: 10.1648    7: 10.177      7: 10.1669
8: 15.498     8: 15.5758     8: 15.508
9: 18.9483    9: 18.8391     9: 18.9236
10: 19.3557   10: 19.278     10: 19.3234
11: 16.0589   11: 16.0863    11: 16.0256
12: 9.8182    12: 9.8851     12: 9.8426

```

### UPDATES

* shortening 1: eliminate `$n=1e6` (insp. by Joe)
* shortening 2: del space in `keys %s`
> 1 votes

# Answer
## R - 98

```
S=sample
D=matrix(S(6,3e6,T),3)
D[D<2]=S(6,3e6,T)
A=colSums(D)-apply(D,2,min)
mean(A)
table(A)/1e4

```

Like some other answers, my output is not in the same format as the OP; I was not sure if it was a strict requirement or not:

```
[1] 9.095695

A
      2       3       4       5       6       7       8       9      10      11      12
 0.0018  0.0426  1.1008  2.8748  6.1438 10.1147 15.5406 18.9276 19.3525 16.0126  9.8882

```
> 1 votes

# Answer
# TI-BASIC, not an entry

This does not meet the spec, because it doesn't show the result distribution or directly roll integers between 1 and 6, but I found a slightly clever algorithm for computing the average in one line. To get the largest two dice rolls, we pad a number larger than any of the dice rolls onto the list of three rolls, and take the median, which will be the average of the middle two numbers (two highest dice rolls). Then we just multiply by 2 to get the sum.

```
2ᴇ~6Σ(median(int(augment(15+36rand(3),{99})/7)),X,1,ᴇ6

```

Based on the speed of SuperJedi224's answer to "Death by Shock Probe", it will take over 12 hours to finish running.
> 1 votes

# Answer
# LUA (307)

```
function r()
  m=math.random(1,6)
  if(m==1)then return math.random(1,6)end
  return m
end
e={}
s=0
o=1000000
for i=2,12 do e[i]=0 end
for t=1,o do
  d={}
  for i=1,3 do d[i]=r() end
  table.sort(d)
  x=d[2]+d[3]
  e[x]=e[x]+1
  s=s+x
end
print("avg("..s/o..")")
for i=2,12 do print(i..": "..e[i]/o*100) end

```

My first one ;)
> 0 votes

# Answer
Seems to be a basic problem with the calculation and results I am seeing here.

If you must reroll the dice (all 3 or just one) when you get a 1 showing up, then the lowest possible sum of die faces you could ever have would be 4. That is, any face that shows a 1 will be rerolled. Which specifically requires that the lowest possible face is a 2. You could avoid the rerolling by generating random values from 2 .. 6, but that might be missing the point.

What this means: If you are reporting values for 2 or 3 as the sum of the faces, these are 1+1 and 2+1 respectively, the specification excludes this possibility.

That is, unless the "you must reroll the dice" only applies to the first instance of a 1. In which case, you may have a 1+1, and 2+1 case (so you'd get sums of 2 and 3 as possible answers).
> 0 votes

# Answer
```
map{@f=(sort((&r,&r,&r)[1,2]));$d[$f[0]+$f[1]]++}(1..1E6);
map{$s+=$d[$_]*$_}(0..$#d);print"avg(".$s/1E6.")\n";map{print"$_:
".$d[$_]/1E4."\n"}(0..$#d);
sub r{$x=1+int(rand 6);$x>1?$x:&r}

    ~/play/golf/dice$ perl dice.pl
    avg(8.000533)
    0: 0
    1: 0
    2: 0
    3: 0
    4: 3.9796
    5: 8.0376
    6: 11.9607
    7: 16.0064
    8: 20.0094
    9: 15.9636
    10: 12.0582
    11: 8.0057
    12: 3.9788

```
> 0 votes

# Answer
Now a more optimized version, with a shifted RNG (no reroll), and shortened statistics calcs, also exploiting the ordering due to the ascii nature of single integers.

```
map{@f=(sort((&r,&r,&r)[1,2]));$i=$f[0]+$f[1];$d[$i]++;$s+=$i}(1..1E6);
print"avg(".$s/1E6.")\n";map{print"$_: ".$d[$_]/1E4."\n"}(0..$#d);
sub r{2+int(rand 5)}

```

As you can see, printing uses almost as much space as computing here. If you'd like a simpler output, this would save characters.

```
avg(8.000901)
0: 0
1: 0
2: 0
3: 0
4: 4.0007
5: 7.9769
6: 11.9652
7: 16.0226
8: 20.0156
9: 16.0389
10: 11.9983
11: 7.9861
12: 3.9957

```
> 0 votes

# Answer
## C ~~222 204~~ 203

204: Updates from ugoren's comment, recycled more global vars, changed `D()` into a macro to save a `return` and three pairs of `()`.

203: Moved the first `printf` into the `for` to save a semicolon.

**See it run in Codepad**

```
#define D (t=rand()%6)?t:rand()%6
j,i,f[11],s,t;M(a,b,c){t=a<b?a:b;t=c<t?c:t;t=a+b+c-t;}main(){for(;j++<1e6;M(D,D,D),s+=t+2)++f[t];for(printf("avg(%f)\n",s/1e6);i<11;++i)printf("%d: %f\n",i+2,f[i]/1e4);}

```

---

```
#define D (t=rand()%6)?t:rand()%6
j,i,f[11],s,t;
M(a,b,c)
{
    t=a<b?a:b;
    t=c<t?c:t;
    t=a+b+c-t;
}
main()
{
    for(;j++<1e6;M(D,D,D),s+=t+2)
        ++f[t];
    for(printf("avg(%f)\n",s/1e6);i<11;++i)
        printf("%d: %f\n",i+2,f[i]/1e4);
}

```

```
avg(9.095219)
2: 0.001600
3: 0.045200
4: 1.100000
5: 2.903400
6: 6.124600
7: 10.112100
8: 15.556000
9: 18.876400
10: 19.358200
11: 16.053800
12: 9.868700
Press any key to continue . . .
```
> 0 votes

# Answer
## C - 200

I didn't bother to re-roll on 1, instead I used the probability distribution (1/36 chance of rolling 1, 7/36 chance of rolling anything else). Hopefully this is acceptable. Newline has been inserted for clarity.

```
#define D 6-rand()%36/7
a,b,c,t,u,w,y[13];
main(v,q){srand(q);for(;v++<=1e6;u=(a=D)<(b=D)?a:b,w+=t=a+b+(c=D)-(u<c?u:c))y[t]++;
printf("avg(%f)\n",w/1e6);for(v=1;++v<13;)printf("%d: %f\n",v,y[v]/1e4);}

```

After compilation (gcc -O3) - 1 run

```
avg(9.096896)
2: 0.002200
3: 0.043100
4: 1.093900
5: 2.891000
6: 6.110100
7: 10.091400
8: 15.605000
9: 18.936500
10: 19.258800
11: 16.047100
12: 9.920800

```
> 0 votes

# Answer
## CoffeeScript, 146

```
r=()->~~(6*Math.random())
t=i=0;s=[];(a=[r()||r(),r()||r(),r()||r()].sort();t+=b=2+a[1]+a[2];s[b]=1e2/z+(s[b]||0))while++i<z=1e6;console.log t/z,s

```

Outputs the average and an object:

```
9.09456
[2: 0.0022, 3: 0.043400000000000216, 4: 1.103199999999895, 5: 2.9063000000017087, 6: 6.142699999999023, 7: 10.075099999989858, 8: 15.533299999977137, 9: 18.94439999996919, 10: 19.328099999968295, 11: 16.106199999975804, 12: 9.814999999990464]

```
> 0 votes

# Answer
## JavaScript (ES6), 149

Algorithm is similar to my CoffeeScript answer; different syntax and semantics. I tried inlining the `q` function here which made no difference.

```
for(r=()=>~~(6*Math.random()),q=()=>r()||r(),t=i=0,s={};++i<(z=1e6);){a=[q(),q(),q()].sort();t+=b=2+a[1]+a[2];s[b]=1e2/z+(s[b]||0)}console.log(t/z,s)

```

### Unminified

```
for (
    r = () => ~~ (6 * Math.random()), // function to generate random number between 0 - 5
      q = () => r() || r(),           // function to roll dice and if 0, re-roll once
      t = i = 0,                      // initialize counter and sum
      s = {};                         // initialize probability object
    ++i < (z = 1e5);                  // increment
) {
    a = [q(), q(), q()].sort();       // roll three dice and perform lexicographical sort
    t += b = 2 + a[1] + a[2];         // take two highest and add 2 since numbers are 0 - 5
    s[b] = 1e2 / z + (s[b] || 0)      // put into probability object as a percent
}
console.log(t / z, s)                 // STDOUT

```
> 0 votes

---
Tags: code-golf, random
---


title: Find the Formula

text:
# Question
Title: Find the Formula
## Introduction

What you have to do is, given an an ASCII diagram of a chemical, output the chemical formula.

## Rules

Your code must not access the internet and may not use a stored library of molecules. You may have a library of elements.

You must verify all of the elements included in the formula are real, with all elements needed to be required found here:

If there are invalid elements in the formula, you must output: `Invalid elements in diagram`.

Order the formulae using the Hill system: carbon then hydrogen then the other elements alphabetically.

Any library/text file of elements is not needed to be included in the byte count.

## Examples

**H2O**

```
H-O-H

```

or

```
H   H
 \ /
  O

```

**CO2**

```
O=C=O

```

**H4N**

```
  H
  |
H-N-H
  |
  H

```

## Winning

The winning code is the shortest program in bytes

## Leaderboard

```
/* Configuration */

var QUESTION_ID = 52630; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";

/* App */

var answers = [], page = 1;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      if (data.has_more) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SIZE_REG = /\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^,]+)/;

function shouldHaveHeading(a) {
  var pass = false;
  var lines = a.body_markdown.split("\n");
  try {
    pass |= /^#/.test(a.body_markdown);
    pass |= ["-", "="]
              .indexOf(lines[1][0]) > -1;
    pass &= LANGUAGE_REG.test(a.body_markdown);
  } catch (ex) {}
  return pass;
}

function shouldHaveScore(a) {
  var pass = false;
  try {
    pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
  } catch (ex) {}
  return pass;
}

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  answers = answers.filter(shouldHaveScore)
                   .filter(shouldHaveHeading);
  answers.sort(function (a, b) {
    var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
        bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  answers.forEach(function (a) {
    var headline = a.body_markdown.split("\n")[0];
    //console.log(a);
    var answer = jQuery("#answer-template").html();
    var num = headline.match(NUMBER_REG)[0];
    var size = (headline.match(SIZE_REG)||[0])[0];
    var language = headline.match(LANGUAGE_REG)[1];
    var user = getAuthorName(a);
    if (size != lastSize)
      lastPlace = place;
    lastSize = size;
    ++place;
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", user)
                   .replace("{{LANGUAGE}}", language)
                   .replace("{{SIZE}}", size)
                   .replace("{{LINK}}", a.share_link);
    answer = jQuery(answer)
    jQuery("#answers").append(answer);

    languages[language] = languages[language] || {lang: language, user: user, size: size, link: a.share_link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang > b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 50%;
  float: left;
}

#language-list {
  padding: 10px;
  width: 50%px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

# Answer
> 1 votes
## PHP, 205 bytes

```
function($f)use($l){for($a=preg_split('#(?=[A-Z])#',eregi_replace('[^a-z]','',$f));++$i<count($a);)if($l[$a[$i]]++===null)die('Invalid elements in diagram');foreach($l as$k=>$v)echo$v?$k.($v>1?$v:''):'';};

```

The array of elements is stored in the `$l` variable in the following form:

```
$l = ['C' => 0, 'H' => 0, 'Ac' => 0, …, 'Zr' => 0];

```

Here is the ungolfed version:

```
function ($formula) use ($elementsList)
{
    $linearFormula = preg_replace('#[^a-z]#i', '', $formula);       // Remove everything except the letters in the formula
    $elementsInFormula = preg_split('#(?=[A-Z])#', $linearFormula); // Split the formula before each uppercase letter, with an additional empty element in the first position

    for ($i = 1; $i < count($elementsInFormula); ++$i)
    {
        // Check if the element is valid
        if (!isset($elementsList[$elementsInFormula[$i]])) {
            die('Invalid elements in diagram');
        }

        // Increment the associated counter
        ++$elementsList[$elementsInFormula[$i]];
    }

    // Print the raw formula
    foreach ($elementsList as $element => $number)
    {
        if ($number > 0) {
            echo $element;
            if ($number > 1) {
                echo $number;
            }
        }
    }
};

```

---
Tags: code-golf, chemistry
---


title: Covering Array Validator

text:
# Question
Title: Covering Array Validator
A covering array is an `N` by `k` array in which each element is one of {0, 1, ..., v-1} (so `v` symbols in total), and for any `t` columns chosen (so an `N` x `t` array) contains all possible `v^t` tuples at least once. The applications of Covering Arrays range from software and hardware testing, interaction testing, and many other fields. A research question (and which will be a follow-up to this question) is to find the minimal Covering Array of given `t`,`k`,and `v`; an analogue of this would be designing a software system with the minimal number of tests required to test all `t`-way interactions of the system. Only for `t=v=2` is the optimal case known for all `k` (some values of `t` and `v` have some optimal CA designs for one value of `k`, but this is not the common case).

Here, we focus on validation of Covering Arrays, as this is a very time-consuming process for very large Covering Arrays.

**Input:** A file that contains the Covering Array. The format is described in **Scoring** below.

**Output:** `Valid` if the input is a valid covering array, and `Invalid` if it is not.

**Goal:** in any language you want, write a program that validates if the input is a covering array in the *fastest* time. I will run programs on my machine, which is a Mac Pro 3.5 Ghz 6-Core Intel Xeon E5 (2013) with 16 GB RAM (1866 MHz).

**Rules:**

1. Any language is allowed, as long as it can read from a file, where the filename is given as input.
2. All you need to print is `Valid` or `Invalid`, nothing else.
3. No third-party libraries; you can only use the libraries/modules that are already built-in to the language.
4. No use of the Internet for validation (i.e., the validation must be done within the program itself).
5. You are allowed to have multi-threading/multi-core solutions. However, I will test it on the machine described above.
6. If your program requires a compilation, describe in your answer what compilation options that you selected (i.e., like `g++ -O3 validator.cpp ca.5.6^7.txt`).

**Scoring**: the total score is the total amount of time in milliseconds to produce all of the valid outputs. I will test your program against a number of CAs, and it reports the total amount of time required to execute validation of all sample CAs as input. The CAs will be selected from this link (the text files are provided there, and is linked to from the first link above also).

The format of the files posted there is provided as follows: the first line of the file is `N`, the name of the file is ca.`t`.`v`^`k`.txt, and the next `N` rows of the file contain `k` space-separated integers.

Fastest code (i.e., lowest score) wins!

**Edit**: after looking at some sample covering arrays on the site, the format is not entirely consistent. If you can change (or provide the file) the format to match the format described above, that would be very helpful.

# Answer
**Python solution**

Uses multiprocessing package to test validity of each v-set of columns selected from the input matrix.

Download from here.

Run:

`$ python main.py ca.t.v^k.txt`
> 0 votes

# Answer
# C, 7.29min for ca.5.4^64.txt on an Intel Core i5-4570 + 8GB ram

### Update: Sometimes gives wrong results

I've compiled it with `gcc -O3 cav.c -o cav`. Simply run it with the CA file's name as first (and only) parameter. In my case: `./cav ca.2.2^4.txt`

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

int t, v, k, N; /* initial parameters */
uint16_t *ca; /* The CA */
uint16_t *cia; /* Column index array - the columns we selected to compare */
uint8_t *combos;
int num_combos; /* Size of the combo 'hash map' (see compareColumns()) */

int ipow(int base, int exp) /* basic integer pow function 'stolen' from StackOverflow ;) */
{
    int result = 1;
    while(exp)
    {
        if(exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}

char compareColumns(int base, int child)
{
    int pos = base, maxpos = k - child, child_dec = child - 1;
    if(child == 0)
    {
        while(pos != maxpos)
        {
            cia[child] = pos++;
            memset(combos, 0, num_combos);
            int rv = 0; /* The offset in the CA for the current row */
            int n;
            for(n = 0; n < N; n++) /* For every row */
            {
                int key = 0; /* This is basically a HashMap key, using the same algorithm that you use for accessing 2D data in a 1D array. */
                int df = 1; /* Dimension factor - needed for the hash-map-key-like algorithm */
                int i;
                for(i = 0; i < t; i++) /* For every selected column */
                {
                    key += df * ca[cia[i] + rv]; /* Calculate the key */
                    df *= v;
                }
                combos[key] = 1; /* Set the 'boolean' at 'key' in the 'hash map' to 1 */
                rv += k;
            }
            if(memchr(combos, 0, num_combos) != NULL) /* If there are still any 0s (any needed combinations that aren't found), exit immediately! */
                return 0;
        }
    }
    else
    {
        while(pos != maxpos)
        {
            cia[child] = pos++;
            if(!compareColumns(pos, child_dec))
                return 0;
        }
    }
    return 1;
}

int main(int argc, char **argv)
{
    /* Fetch user input & allocate memory */
    sscanf(argv[1], "ca.%d.%d^%d.txt", &t, &v, &k);

    FILE *file = fopen(argv[1], "r");
    fscanf(file, "%d", &N);

    int num_vals = k * N, i;
    num_combos = ipow(v, t);

    ca  = (uint16_t*)malloc(num_vals * sizeof(uint16_t));
    cia = (uint16_t*)malloc(t * sizeof(uint16_t));
    combos = (uint8_t*)malloc(num_combos * sizeof(uint8_t));

    for(i = 0; i < num_vals; i++)
    {
        int val;
        fscanf(file, " %d", &val);
        ca[i] = val;
    }
    fclose(file);

    /* The main algorithm implementation */
    if(compareColumns(0, t - 1))
        printf("Valid!\n");
    else
        printf("Invalid!\n");

    /* Free memory */
    free(combos);
    free(cia);
    free(ca);
    return 0;
}

```

I'll try to explain: I'll begin with compareColumns: if it has children (int child), it goes through (allmost) all the columns and kicks off a new call to compareColumns after each step, which itself then walks from the last position of its parent until the end (minus it's own children) of the CA. However, if the function is called with no children (child = 0), it will take all the selected rows and generate something like a hash map key from it. This key will then be used to set a specific cell of the array combos to 1. At the end, it checks if all cells of 'combos' are 1 (i.e. if all combinations appeared at least once). If all cells are 1, it will proceed. If at least one cell is 0, it will abort immediately and print "Invalid!".
> 2 votes

# Answer
## Fantom

Mostly just a brute force solution, except it does a few preliminary checks ahead of time and uses a binary search to find tuples in each sub-array. I think Fantom optimizes most built in stuff, like the sorts and array manipulations, pretty well under-the-hood. *Note*: Replaces "-" with : "0" for simplicity.

## To Run

Download Fantom from the link in the title, and set up your system variables using instructions here. Save in a file called isCA.fan
run as `fan isCA.fan "pathToFile"`

```
class isCA
{
  public static Void main(Str[] args){

    Int start := Duration.nowTicks;
    //Initialize everything
    path := "file:" + args.first
    params := path.split(File.sep.chars.first).last.split('.')
    t := Int.fromStr(params[1])
    params = params[2].split('^')
    v := Int.fromStr(params[0])
    k := Int.fromStr(params[1])
    StrArray := File(Uri.fromStr(path)).in.readAllLines[1..-1]
    array := StrArray.map |Str line -> Str[]| {line.replace("- ", "0 ")[0..-2].split(' ').map |Str s ->Int| {Int.fromStr(s)}}

    //echo("t: $t\n v: $v\nk: $k")

    //Comparison function
    compare := |Int[] a, Int[] b -> Int| {
      Int i := 0
      result := -1
      done := false
      while(i < a.size - 1 && !done){
        if(a[i] != b[i]){
          result = a[i] <=> b[i]
          done = true
        }
        i++
        if(!done){
          return a[i] <=> b[i]
        }
      }
      return result
    }

    //Basic checks to speed up the Not Valid time
    array = array.sort(compare).unique

    //Each column contains each value
    k.times|Int i|{
      vals := Range(0, v, true).toList
      array.each |Int[] row|{
        vals.remove(row[i])
      }
      if(!vals.isEmpty){ respond(false, start)}
    }

    //umm, I guess I'll start with the brute-force method until I think of something better
    vals := Range(0,v,true).toList
    tuples := permutations(vals)
    temp := [,]
    t.times{ temp.add(1)}
    (k - t).times{ temp.add(0) }
    colBins := permutations(temp).unique

    colBins.each |Int[] bin| {
      //Construct columns
      smallArray := array.map |Int[] row -> Int[]|{
        r := [,]
        row.each |Int a, Int index|{ if(bin[index] == 1){r.add(a)}}
        return r
      }

      tList := tuples.dup
      Int cols := t
      //Binary search the array
      while(cols >= v){
        smallArray.sort(compare)
        found := [,]
        tList.each|Int[] tuple, Int index|{
          Int find := smallArray.binarySearch(tuple, compare)
          //echo("Found $tuple at $find in $smallArray")
          if(find >= 0){found.add(index)}
        }
        //Remove first col and try again
        smallArray = smallArray.map|Int[] a -> Int[]| {return a[1..-1]}
        cols--;
        //ignore tuples we already found
        tList = tList.findAll|Int[] list, Int index -> Bool| {!found.contains(index)}
      }

      if(!tList.isEmpty){
        echo("Cols $bin does not contain $tList")
        respond(false, start)
      }

    }
    respond(true, start)
  }

  private static Void respond(Bool b, Int start){
    if(b) echo("Valid")
    else echo("Not Valid")
    echo("Time: " + (Duration.nowTicks() - start))
    Env.cur.exit
  }

  private static Int[][] permutations(Int[] a){
    result := [,]
    recurse([,], a, result)
    return result
  }

  private static Void recurse(Int[] pre, Int[] a, Int[][] results){
    //echo("Recursing $pre\nwith $a")
    if(a.isEmpty) {
      results.add(pre)
      return
    }

    for(Int i := 0; i < a.size; i++){
      d := a.dup
      d.removeAt(i)
      recurse(pre.dup.add(a[i]), d, results )
    }
  }
}

```
> 0 votes

---
Tags: fastest-code
---


title: You call this optimized?

text:
# Question
Title: You call this optimized?
The task is simple, post 2 code snippets that perform the same task, where one seems very optimized at first glance, but actually is significantly slower than the other.

Only one rule:

* Both snippets must finish with the exact same output (for the same given input, if any).

# Answer
> 10 votes
Python 3

Seems fast...

```
 print(0 < 10**100 - 1 < 10**100)

```

Seems slow...

```
 print(10**100 - 1 in range(0, 10**100))

```

But the two run in very similar times! `range` has an efficient implementation of `in`

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


# Question
Title: You call it Centering, I call it Code Golf
*"Let's face it, aligned images are like little gifts from Heaven. Welcome, but unexpected."* \- Geobits

+10000 reputation to whoever wins this challenge.

# Rules:

1) You are to generate a program.

2) Input will be an image, however whether it is passed as a file or a list of numbers is up to you.

3) Output will be a file which when opened in paint (or similar) will show the image aligned.

4) The canvas size will always be between 100 x 100 and 2000 x 2000 pixels. It will always be a rectangle, but not always a square.

5) No hard coding of images or funky URL magic.

6) No external libraries to be used.

# Guide to Centralisation (Joshpbarron Variant)

An image will be defined as centered if the 1st white(255,255,255,\>0 rgba) or transparent(x,y,z,0 rgba) on an axis is equal distance (plus or minus 1 pixel) from the edge of the canvas.

This can be achieved (and will be verified by) the following method.

1) Imagine a bounding box around the object. (Black lines added for help)

2) Move the object around until the edge of the object is equal distance from the appropriate edge of the canvas.

3) Now forget the black lines.

Input:

Output:

More inputs here.

And respective outputs here.

*The +10000 rep is a lie.*

# Answer
> 0 votes
# Python 3, ~~120~~ 205 bytes

**EDIT** : As the output image must have the same size as the input, the script gets longer ...

**EDIT2** : It seems that the rule 6 (no external library) has been added after I answered, so this answer is to be considered invalid anyway :(

```
from PIL.Image import*;from PIL.ImageOps import*
c='RGB';i=open(input()).convert(c);w,h=i.size
o,a=new(c,(w,h),'white'),i.crop(invert(i).getbbox())
e,f=a.size;o.paste(a,((w-e)//2,(h-f)//2));o.save('o.png')

```

The former version just cropped the input image:

```
from PIL.Image import*;from PIL.ImageOps import*
i=open(input()).convert('RGB')
i.crop(invert(i).getbbox()).save('o.png')

```

both scripts read the image file name from stdin, and saves the output image as 'o.png'. for example :

```
python3 script.py <<< s2rMqYo.png

```

It accepts at least PNG images (potentially with an alpha channel) -- Tested 'ok' on the set provided by the asker.

...waiting for my reward ):

# Answer
> 2 votes
## HTML5 + JavaScript (ES5), 515 bytes

That count includes the HTML tags as they are part of the program. If you only count the image processing code, it is **376 bytes** including the function wrapper.

```
<canvas id=o></canvas><script>f=function(p){o=new Image();o.crossOrigin='Anonymous';o.src=p;o.onload=function(){v=document.getElementById('o'),c=v.getContext('2d');v.width=l=w=o.width;v.height=t=h=o.height;c.drawImage(o,0,0);for(k=255,d=c[g='getImageData'](0,0,w,h).data,r=b=i=0;i<d.length;)if((d[i++]<k||d[i++]<k||d[i++]<k)&&d[i++]){x=i/4%w;y=~~(i/4/w);l=l<x?l:x;t=t<y?t:y;b=b>y?b:y;r=r>x?r:x}n=c[g](l,t,r-l+1,b-t+1);c.clearRect(0,0,w,h);c.putImageData(n,(w-r+l)/2,(h-b+t)/2)}}</script><input onblur=f(this.value)>

```

### Input

A URL to an image.

### Security restrictions

Because this program is running in a browser environment, only URLs to CORS-enabled images will work. Imgur is CORS enabled.

IE 10 does not support CORS. I haven't tested in IE 11 yet but it does work in Chrome and Firefox.

### How to run

1. Type/paste in a URL into the input field.
2. De-focus (tab/click out of) from the input field.

### Output

It outputs on the canvas on the page.

As this is a browser-based application, security restrictions prevent automatic download of a file but you can right click and save image in Chrome and Firefox. I haven't tested on IE 11 yet.

### Demo

JavaScript code has been removed from the `script` element and put into the appropriate area to accommodate Stack Snippets:

```
f = function(p) {
  o = new Image();
  o.crossOrigin = 'Anonymous';
  o.src = p;
  o.onload = function() {
    v = document.getElementById('o'), c = v.getContext('2d');
    v.width = l = w = o.width;
    v.height = t = h = o.height;
    c.drawImage(o, 0, 0);
    for (k = 255, d = c[g = 'getImageData'](0, 0, w, h).data, r = b = i = 0; i < d.length;)
      if ((d[i++] < k || d[i++] < k || d[i++] < k) && d[i++]) {
        x = i / 4 % w;
        y = ~~(i / 4 / w);
        l = l < x ? l : x;
        t = t < y ? t : y;
        b = b > y ? b : y;
        r = r > x ? r : x
      }
    n = c[g](l, t, r - l + 1, b - t + 1);
    c.clearRect(0, 0, w, h);
    c.putImageData(n, (w - r + l) / 2, (h - b + t) / 2)
  }
}
```

```
<canvas id=o></canvas>
<input onblur=f(this.value)>
```

# Answer
> 0 votes
# Processing 2 - 323 450

Image is read from the file f.png in the data folder of the sketch. Places the image and determines it's bounds. Calculates the correct position and replaces the image shifted correctly.

```
PImage p=loadImage("h.png");int a,b,c,d,x,y,w,i,n,m,t;a=w=p.width;c=i=p.height;clear();size(w,i,P2D);x=y=b=d=t=0;image(p,0,0);loadPixels();while(x<w*i){if(pixels[x]==color(255))t=1;x++;}x=0;background(255);image(p,0,0);loadPixels();while(y*w+x<w*i){if(pixels[y*w+x]!=color(255)){if(x<a)a=x;if(x>b)b=x;if(y<c)c=y;if(y>d)d=y;}x++;if(x==w){x=0;y++;}}n=(w-(b-a))/2;m=(i-(d-c))/2;clear();if(t>0)background(255);image(p,n-a,m-c);loadPixels();save("g.png");

```

readable version:

```
PImage p=loadImage("h.png");
int a,b,c,d,x,y,w,i,n,m,t;
a=w=p.width;
c=i=p.height;
clear();
size(w,i,P2D);
x=y=b=d=t=0;
image(p,0,0);
loadPixels();
while(x<w*i)
{
 if(pixels[x]==color(255))t=1;
 x++;
}
x=0;
background(255);
image(p,0,0);
loadPixels();
while(y*w+x<w*i)
{
 if(pixels[y*w+x]!=color(255))
 {
   if(x<a)a=x;
   if(x>b)b=x;
   if(y<c)c=y;
   if(y>d)d=y;
 }
 x++;
 if(x==w){x=0;y++;}
}
n=(w-(b-a))/2;
m=(i-(d-c))/2;
clear();
if(t>0)background(255);
image(p,n-a,m-c);
loadPixels();
save("g.png");

```

Example output:

You can get processing here

---
Tags: code-golf, image-processing
---


title: Monopoly Compression

text:
# Question
Title: Monopoly Compression
Given a string representing the current state of a game of Monopoly at the beginning of a player's turn, compress all the necessary data into the smallest output. Answers will be judged by **output size** and **source size**.

Note: There are many regional variations, but all references in this post to property names, etc, are based on this board.

---

## Input:

Input will be given as a single `;` separated string. This string is given to the program in whatever way is customary in your chosen language, whether that's stdin, arguments, etc.

The unformatted input looks like this:

```
numPlayers                     (1 to 8)
whose turn                     (0 to numPlayers-1)
for each player:
    bankrupt?                  (true/false)
    money                      (0 to 2^16-1)
    get-out-of-jail-free cards (0 to 2)
    position                   (0 to 39)
    jail turns                 (-1 to 2)
for 28 properties:
    owner                      (-1 to numPlayers-1)
    mortgaged?                 (true/false)
    improvement level          (0 to 5)
for 16 chance cards in deck:
    card index                 (-1 to 15)
for 16 community chest cards in deck:
    card index                 (-1 to 15)

```

An example *formatted* input is this:

```
3;1;false;1546;0;14;-1;false;7692;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

```

Taken bit by bit:

```
3;1;

```

There are 3 players, and it is player 1's turn (zero-indexed, so the *second* player)

**Players**

```
false;1546;0;14;-1;
false;7692;1;10;1;
true;

```

The first player:

* is not bankrupt
* has $1546 cash on hand
* owns 0 get-out-of-jail-free cards
* is on position 14 (Virginia Ave)
* is not in jail

The second player **is** in jail, and has been for one turn. I'm not sure *why*, since he has a GOoJF card, but he's there.

The third player is bankrupt, and more information is neither required nor given.

**Properties**

```
1;false;1;
1;false;0;
0;true;0;
-1;false;0;
-1;false;0;
-1;false;0;
...

```

Properties are listed in order around the board, starting from Mediterranean and ending at Boardwalk. Properties that cannot be owned are not included in this list, so there will be a total of 28. Improvement level `0` means unimproved. Level `1` is one house, up to level `5` for a hotel. A `-1` for owner means it is not owned by any player.

According to standard rules, a property that is mortgaged *must* be owned and *must not* be improved. A property that is improved *must* be owned and *must not* be mortgaged.

In addition, for a property to be improved, a player *must* own the entire color block. For the purposes of this game, we do not care if properties are being improved "evenly".

Note that these positions are *not* the same as the player positions given above. For instance, a player on the `5` position would be on Reading Railroad, which is the *third* property in the list (since Go, Community Chest, and Income Tax cannot be owned). Player positions run from `0`(Go) clockwise to `39`(Boardwalk).

**Cards**

```
0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;
3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

```

Each of the Chance and Community Chest decks have `16` total cards. The numbers are presented as they appear in the currently shuffled deck. For this example, the first card pulled off the Chance deck will be card `0`, followed by card `1` (whoever shuffled that deck sucks). The first card pulled from Community chest is card `3`, then `12`.

Don't worry about what each card *means* (the card text), except for card `0`. That is the Get Out of Jail Free card for that deck. If a player owns it, it will be at the end of the list, represented as `-1`.

---

## Output:

You must output (to console, stdout, or file) a representation of the game state. This must include all information **required** to represent the game. For example, you could omit (or abbreviate) unowned properties, since they can neither be improved or mortgaged. The input cannot omit them because it is an unindexed list.

Compression should be done in a way that you can compute worst-case output size. This may disqualify certain compression algorithms (unless you can prove the worst case, and give an example of worst-case input).

Unless your source code is *unreasonably* verbose, give an explanation of how the game is represented. Answers consisting of nothing but a golfed program and compressed output are discouraged. For example, if you are omitting certain values, explain how it is possible to derive them from the output.

---

## Scoring/Rules:

Scoring is based both on **worst-case** compression size in **bits**, and source code size in **bytes**:

```
score = (outputBits * 2) + encoderSourceBytes

```

A complete answer must include:

* Output example
* Encoder source
* Decoder source (not counted against score)

All encoders must be complete programs, and standard loopholes are forbidden. Using built-in or external compression libraries is also forbidden.

The winner is the answer with the **lowest** score, as defined above.

# Answer
(An answer was recently edited, which brought this question to my attention, and I decided to give it a try although its an old question.)

# Swift 1.2 - 1016 Points (2\*81 + 854)

The output is at worst 81 bytes, and changes with the amount of players.

Either of the two methods work. The Playground version is slightly longer.

**Compress Playground**

(Assumes `Input.txt` is in the `Playground Documents Directory`)

```
// Compressor e(inputFileName, outputFileName)
import Cocoa;typealias S=String;typealias U=UInt8;func e(a:S,b:S){var d=NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask, true)as![S],g=d[0],r=S(contentsOfFile:"\(g)/\(a)",encoding:4,error:nil)!.componentsSeparatedByString(";"),z=[U](count:4,repeatedValue:0),c=[U](),p:()->Int={r.removeAtIndex(0).toInt()!},f:()->Bool={r.removeAtIndex(0)=="true" ?true:false},j=U(p());c+=[(j<<4)|(U(p()))];for _ in 0..<j{if f(){c+=[255]}else{let(t,g,v)=(UInt16(p()),U(p()),U(p()));c+=[(U(p()))|(g<<2),v,U(t>>8),U(t&255)]}};for _ in 0..<28{c+=[(U(bitPattern:Int8(p()))<<4)|((f() ?1:0)<<3)|(U(p()))]};for h in 0..<16{let y=h>7 ?1:0,x=Int8(p()),w=Int8(p());c+=[(U(bitPattern:x)<<4)|(U(bitPattern:w)&15)];z[y]=z[y]<<1;if x == -1{z[y]|=1};z[y+1]=z[y+1]<<1;if w == -1{z[y+1]|=1}};NSData(bytes:c+z,length:c.count+4).writeToFile("\(g)/\(b)",atomically:true)}

// Decompressor d(inputFileName, outputFileName)
func d(a:S,b:S){var d = NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask,true)as![String],e=d[0],i=NSData(contentsOfFile:"\(e)/\(a)")!,n=[UInt8](count:i.length,repeatedValue:0),o="";i.getBytes(&n,length:i.length);let k=n.removeAtIndex(0),j=k>>4;o+="\(j);\(k&15);";for _ in 0..<j{let h=n.removeAtIndex(0);if h>>7 == 1{o+="true;";continue};let p=n.removeAtIndex(0),b=n.removeAtIndex(0),c=n.removeAtIndex(0);o+="false;\(UInt16(b)<<8|UInt16(c));\(h>>2);\(p);\(h&0b11);"};for _ in 0..<28{let p=Int8(bitPattern:n.removeAtIndex(0)),mortgage=((p>>3)&1)==1 ?"true":"false";o+="\(p>>4);\(mortgage);\(p&7);"};var m=[U](count:4,repeatedValue:0);for i in reverse(0..<4){m[i]=n.removeLast()};for h in 0..<16{var i=h>7 ?1:0,z=n.removeAtIndex(0),x=Int8(z>>4),y=Int8(z&15),isUnowned1=m[i]&128;m[i]=m[i]<<1;let isUnowned2=m[i+1]&128;m[i+1]=m[i+1]<<1;if isUnowned1 != 0 {x=(-1)};if isUnowned2 != 0 {y=(-1)};o+="\(x);\(y);"};o.writeToFile("\(e)/\(b)",atomically:true,encoding:4,error:nil)}

// Test function to compare the files
func t(a:S,b:S)->Bool{let d=NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask,true)as![String],c=d[0],i=S(contentsOfFile:"\(c)/\(a)",encoding:4,error:nil)!,j=S(contentsOfFile:"\(c)/\(b)",encoding:4,error:nil)!;return i==j}
// Usage
e("Input.txt", "Output.bin")  // Encode
d("Output.bin", "Output.txt") // Decode
t("Input.txt", "Output.txt")  // Test -> Should output 'true'

```

**Compress.swift** \- run in Terminal using `swift Compress.swift`

(Assumes `Input.txt` is on the `Desktop`)

```
// Compressor - 854 Bytes
import Cocoa;typealias S=String;typealias U=UInt8;func e(a:S,b:S){var d=NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask, true)as![S],g=d[0],r=S(contentsOfFile:"\(g)/\(a)",encoding:4,error:nil)!.componentsSeparatedByString(";"),z=[U](count:4,repeatedValue:0),c=[U](),p:()->Int={r.removeAtIndex(0).toInt()!},f:()->Bool={r.removeAtIndex(0)=="true" ?true:false},j=U(p());c+=[(j<<4)|(U(p()))];for _ in 0..<j{if f(){c+=[255]}else{let(t,g,v)=(UInt16(p()),U(p()),U(p()));c+=[(U(p()))|(g<<2),v,U(t>>8),U(t&255)]}};for _ in 0..<28{c+=[(U(bitPattern:Int8(p()))<<4)|((f() ?1:0)<<3)|(U(p()))]};for h in 0..<16{let y=h>7 ?1:0,x=Int8(p()),w=Int8(p());c+=[(U(bitPattern:x)<<4)|(U(bitPattern:w)&15)];z[y]=z[y]<<1;if x == -1{z[y]|=1};z[y+1]=z[y+1]<<1;if w == -1{z[y+1]|=1}};NSData(bytes:c+z,length:c.count+4).writeToFile("\(g)/\(b)",atomically:true)}
// Decompressor
func d(a:S,b:S){var d = NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask,true)as![String],e=d[0],i=NSData(contentsOfFile:"\(e)/\(a)")!,n=[UInt8](count:i.length,repeatedValue:0),o="";i.getBytes(&n,length:i.length);let k=n.removeAtIndex(0),j=k>>4;o+="\(j);\(k&15);";for _ in 0..<j{let h=n.removeAtIndex(0);if h>>7 == 1{o+="true;";continue};let p=n.removeAtIndex(0),b=n.removeAtIndex(0),c=n.removeAtIndex(0);o+="false;\(UInt16(b)<<8|UInt16(c));\(h>>2);\(p);\(h&0b11);"};for _ in 0..<28{let p=Int8(bitPattern:n.removeAtIndex(0)),mortgage=((p>>3)&1)==1 ?"true":"false";o+="\(p>>4);\(mortgage);\(p&7);"};var m=[U](count:4,repeatedValue:0);for i in reverse(0..<4){m[i]=n.removeLast()};for h in 0..<16{var i=h>7 ?1:0,z=n.removeAtIndex(0),x=Int8(z>>4),y=Int8(z&15),isUnowned1=m[i]&128;m[i]=m[i]<<1;let isUnowned2=m[i+1]&128;m[i+1]=m[i+1]<<1;if isUnowned1 != 0 {x=(-1)};if isUnowned2 != 0 {y=(-1)};o+="\(x);\(y);"};o.writeToFile("\(e)/\(b)",atomically:true,encoding:4,error:nil)}
func t(a:S,b:S)->Bool{let d=NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask,true)as![String],c=d[0],i=S(contentsOfFile:"\(c)/\(a)",encoding:4,error:nil)!,j=S(contentsOfFile:"\(c)/\(b)",encoding:4,error:nil)!;return i==j}
e("Input.txt", "Output.bin")
d("Output.bin", "Output.txt")
println(t("Input.txt", "Output.txt"))

```

**Sample Input/Output**

```
3;1;false;1534;0;14;0;false;34;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;6;9;4;-1;4;8;4;2;9;5;11;10;14;7;

```

.

```
31 00 0E 05 FE 05 0A 00 22 FF 11 10 08 F0 F0 F0
F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0
F0 F0 F0 F0 F0 F0 01 23 45 67 89 AB CD EF 3C 69
4F 48 42 95 BA E7 00 00 20 00

```
> 4 votes

# Answer
## Pure C (3592 points)

The output is 182 bytes. The size is O(1), so this is the worst case.

This uses sscanf extensively to read the files, and simply dumps the structs to disk.

I had to slightly modify the input, as your example didn't include 28 properties.

For variables, I named them from the first letter of what it is, or if that would conflict, the second (or subsequent) letter. For example, Game, pLayer, pRoperty, etc.

**compress.c** (680 bytes):

```
#import <stdio.h>
#import <stdint.h>
#define T(X) for(int i=0;i<(X);i++)
typedef uint8_t U;typedef struct{U p;U t;U a[16];U e[16];}G;typedef struct{U b;uint16_t m;U c;U p;U t;}L;typedef struct{int8_t o;U m;U i;}R;G g;L l[8];R r[28];main(){FILE *f=fopen("input.txt","r");fscanf(f,"%d;%d;",&g.p,&g.t);T(g.p){l[i].b=(fgetc(f)=='t');while(fgetc(f)!=';');if(!l[i].b){fscanf(f,"%d;%d;%d;%d;",&l[i].m,&l[i].c,&l[i].p,&l[i].t);}}T(28){fscanf(f,"%d;",&r[i].o);r[i].m=(fgetc(f)=='t');while(fgetc(f)!=';');fscanf(f,"%d;",&r[i].i);}T(16){fscanf(f,"%d;",&g.a[i]);}T(16){fscanf(f,"%d;",&g.e[i]);}f=fopen("c.dat","w");fwrite(&g,sizeof(G),1,f);fwrite(&l,sizeof(L),8,f);fwrite(&r,sizeof(R),28,f);}

```

**compress.c (pre-golfed)**

```
#include "m.h"

#define NEXT_FIELD b=strchr(b,';')+1;

G g;
L l[8];
R r[28];

char a[1024];
char *b = a;

main() {
    FILE *i = fopen("input.txt", "r");
    fgets(a, 1024, i);
    fclose(i);

    sscanf(b, "%d;%d;", &g.p, &g.t);
    NEXT_FIELD NEXT_FIELD

    TIMES(g.p) {
        l[i].b = (*b == 't'); NEXT_FIELD
        if(!l[i].b) {
            sscanf(b, "%d;%d;%d;%d;", &l[i].m, &l[i].c, &l[i].p, &l[i].t);
            NEXT_FIELD NEXT_FIELD NEXT_FIELD NEXT_FIELD
        }
    }

    TIMES(28) {
        sscanf(b, "%d;", &r[i].o); NEXT_FIELD
        r[i].m = (*b == 't'); NEXT_FIELD
        sscanf(b, "%d;", &r[i].i); NEXT_FIELD
    }

    TIMES(16) {
        sscanf(b, "%d", &g.a[i]);
        NEXT_FIELD
    }

    TIMES(16) {
        sscanf(b, "%d", &g.e[i]);
        NEXT_FIELD
    }

    FILE *c = fopen("c.dat", "w");
    fwrite(&g, sizeof(G), 1, c);
    fwrite(&l, sizeof(L), 8, c);
    fwrite(&r, sizeof(R), 28, c);
    fclose(c);
}

```

**decompress.c**:

```
#import <stdio.h>
#import <stdint.h>

#define T(X) for(int i = 0; i < (X); i++)
typedef uint8_t U;

typedef struct {
    U p;
    U t;
    U a[16];
    U e[16];
} G;
typedef struct {
    U b;
    uint16_t m;
    U c;
    U p;
    U t;
} L;
typedef struct {
    int8_t o;
    U m;
    U i;
} R;

G g;
L l[8];
R r[28];

main() {
    FILE *c = fopen("c.dat", "r");
    fread(&g, sizeof(G), 1, c);
    fread(&l, sizeof(L), 8, c);
    fread(&r, sizeof(R), 28, c);
    fclose(c);

    FILE *d = fopen("output.txt", "w");

    fprintf(d, "%d;%d;", g.p, g.t);
    T(g.p) {
        fprintf(d, "%s;", l[i].b ? "true" : "false");
        if(!l[i].b){
            fprintf(d, "%d;%d;%d;%d;", l[i].m, l[i].c, l[i].p, l[i].t);
        }
    }
    T(28) {
        fprintf(d, "%d;%s;%d;", r[i].o, r[i].m ? "true" : "false", r[i].i);
    }
    T(16) { fprintf(d, "%d;", g.a[i] != 255 ? g.a[i] : -1); }
    T(16) { fprintf(d, "%d;", g.e[i] != 255 ? g.e[i] : -1); }

    fclose(d);
}

```

**Input / output**:

```
3;1;false;1546;0;14;0;false;7692;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

```

**Compressed** (182 bytes):

```
0301 0001 0203 0405 0607 0809 0a0b 0c0d
0e0f 030c 0704 0502 0d0b 0f06 0809 0a01
0eff 0000 0a06 000e 0000 0000 0c1e 010a
0100 0100 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0100 0101 0000 0001 00ff 0000 ff00
00ff 0000 ff00 00ff 0000 ff00 00ff 0000
ff00 00ff 0000 ff00 00ff 0000 ff00 00ff
0000 ff00 00ff 0000 ff00 00ff 0000 ff00
00ff 0000 ff00 00ff 0000 ff00 00ff 0000
ff00 00ff 0000

```

**Run it!**

```
$ make compress decompress && ./compress && ./decompress && md5 input.txt output.txt
MD5 (input.txt) = fa655a5a17d67b188424ab0dcfdfb825
MD5 (output.txt) = fa655a5a17d67b188424ab0dcfdfb825

```
> 4 votes

---
Tags: code-challenge, compression
---