# Question
Title: Solve quadratic equation using only 3 variables and arithmetic
Write function which solves equation of degree less than or equal to 2 (`ax^2 + bx + c = 0`).

# Input

Function should get 3 parameters - floating point numbers which are coefficients of this equation. Coefficients may be zero (that means function must able to solve `bx + c = 0` and `c = 0` too).
Coefficients are between `-1000` and `1000` with 3 significant decimal digits but maximum 3 digits after comma, for example, `999.` or `3.14` or `0.233` but not `1001` or `0.0123`.

# Rules

* You may use only `+ - * / % & | xor ~ && || ! < > >= <= == != << >>` operators
* No built-in functions (that means no square root or power or similar functions)
* No variables except 3 function parameters
* You can't use complicated expressions - only statements of the form `a = b @ c` or `a = @ b` are allowed (`@` \- any allowed operator and `a, b, c` \- any variables, may be same or constants)
* No loops, recursion, goto's, custom types
* Casts and type conversion between integral data types are allowed
* Using features of dynamic typing (changing floating point number to array/object/something else that is not number) is not allowed
* If's are allowed with one or none operators in condition (`if (a) {...} else {...}` or `if (a==b) {...} else {...}`). Note that `if` itself and its condition scores separately
* You may use `try{}catch{}`

# Output

* Output should be passed by reference to input variables, if your language doesn't have such feature, you anyway should put result to input variables and print their values
* In variable `a` \- number of real roots - 0, 1, 2, 3 (value greater than 2 stands for infinitely many roots)
* In variables `b` and `c` \- 1st and 2nd roots (if none or infinitely many roots than any values, if one root then `c` \- any value)
* Note that 2 equal roots is not the same as 1 root
* Precision should be at least 3 significant decimal digits

# Score

* Score is `[number of operators]` \+ `[number of if's]`. Assignment operators have score 0.
* Answer with lowest score wins.
* In case of same score answer with greater precision wins. If precision is same then first answer wins.
* `if(a != 0)` and `if(a == 0)` has score 1 (instead of 2) because `if(a)` or `if(a)else{}` can be used, however not all languages support it.
* For each `catch{}` +2 to score
* Use of 1 temporary variable of numeric type is +20 to score.

# Answer
> 6 votes
## Hybrid of iterative approaches; score: 62

I originally posted an answer which purely used Newton-Raphson; however, in the cases of large `b` and `c` this requires a lot of iterations. Consider only the most interesting quadratics: those which have two solutions. If we normalise them to the form `x^2 + bx + c = 0` then we can plot the number of iterations required for various approaches as a function of `b` and `c`. For example, we can modify the continued fraction route to get the direct approach:

```
c = -c;
a = b * 0.5;
while (loopCount-- > 0) { // This loop would be unrolled in the final solution
    a = a + b;
    a = c / a;
}
// Roots are a and -c/a

```

That gives a loop count diagram of

```
2236...................6322
2224n.................n4222
22236.................63222
22224n...............n42222
222236...............632222
222224m.............m422222
2222236.............6322222
2222224j...........j4222222
22222234P.........P43222222
22222223d.........d32222222
222222222t.......t222222222
2222222225Z.....Z5222222222
22222222219/////91222222222
/////////////./////////////
222222222*********222222222
222222222*********222222222
22222222***********22222222
22222223***********32222222
2222223*************3222222
2222224*************4222222
222223***************322222
222224***************422222
22223*****************32222
22224*****************42222
2223*******************3222
2224*******************4222
223*********************322

```

where `c` is negative in the first row and increases downwards, `b` increases from left to right, `*` means negative discriminant, `/` means only one root was within tolerance in 62 iterations, `.` means no root was within tolerance in 62 iterations, and numbers are in base-62 with digits `0-9a-zA-Z`. This is pretty decent for a certain range, but fails completely for another range.

bmarks' original implementation is similar to (but not the same; this is a reimplementation from the continued fraction):

```
a = b;
while (loopCount-- > 0) {
    a = c / a;
    a = b - a;
}
// Roots are -a, -c/a (which is better than a-b)

```

with loop count diagram

```
1117...................7111
1112n.................n2111
11117.................71111
11112n...............n21111
111117...............711111
111112m.............m211111
1111117.............7111111
1111112j...........j2111111
11111115Q.........Q51111111
11111111d.........d11111111
111111113u.......u311111111
1111111116/...../6111111111
1111111111a/////a1111111111
1111111111111.1111111111111
111111111*********111111111
111111111*********111111111
11111111***********11111111
11111112***********21111111
1111111*************1111111
1111112*************2111111
111111***************111111
111113***************311111
11111*****************11111
11113*****************31111
1111*******************1111
1113*******************3111
111*********************111

```

My naïve N-R was quite bad, but the really interesting thing to note about it is where the worst areas are:

```
njfdcccccccccccccccccccdfjn
njgcbbbbbbbbbbbbbbbbbbbcgjn
njgc9999999999999999999cgjn
njgc9777777777777777779cgjn
njgc9666666666666666669cgjn
njgc9544444444444444459cgjn
njgc9521111111111111259cgjn
njgc9534444444444444359cgjn
njgc9535555555555555359cgjn
njgc9536777777777776359cgjn
njgc9536888888888886359cgjn
njgc9536899999999986359cgjn
njgc95368aaaaaaaaa86359cgjn
njgc95368aaaaaaaaa86359cgjn
njgc95368*********86359cgjn
njgc95369*********96359cgjn
njgc9536***********6359cgjn
njgc9536***********6359cgjn
njgc953*************359cgjn
njgc954*************459cgjn
njgc95***************59cgjn
njgc94***************49cgjn
njgc9*****************9cgjn
njgc8*****************8cgjn
njgc*******************cgjn
njgb*******************bgjn
njf*********************fjn

```

So the thing to do is to hybridise. For the areas where it's good, I use the continued fraction; for the rest, I use N-R, but I've done some optimisation: I've experimentally found two cutoffs and three initial values which converge in 5 iterations to a worst-case mixed error `abs(value - correct_value) / (1 + abs(correct_value)` of 0.000052. (Thanks to Martin Büttner for the idea of doing a case split). The final loop count (mixing the two cases into one diagram) is:

```
111555555555555555555555111
111233333333333333333332111
111133333333333333333331111
111125555555555555555521111
111115555555555555555511111
111112333333333333333211111
111111333333333333333111111
111111255555555555552111111
111111144444444444441111111
111111112111111111111111111
111111113222222222211111111
111111111333333333111111111
111111111444444444111111111
111111111111111111111111111
111111111*********111111111
111111111*********111111111
11111111***********11111111
11111112***********21111111
1111111*************1111111
1111112*************2111111
111111***************111111
111113***************311111
11111*****************11111
11113*****************31111
1111*******************1111
1113*******************3111
111*********************111

```

and the code is

```
solve_quad(&float a, &float b, &float c) {
    float t; // 20 points
    if (a != 0) { // 21
        if (c == 0) {
            // x(x+b) = 0
            b = -b; // 22
            a = 2;
        }
        else {
            // Normalise so that we're solving x^2 + bx + c = 0 and have `a` free to use
            // Hereon, mentions of b and c in comments refer to these normalised values.
            b = b / a; // 22
            c = c / a; // 23

            // Three cases:
            //   b^2 < 4c: negative determinant, no solutions
            //   b^2 < -4c: use Newton-Raphson
            //   Otherwise: use the continued fraction method that bmarks was the first to post

            a = b / 2; // 24
            a = a * a; // 25
            if (a < c) { // 26
                a = 0;
            }
            else {
                t = a + c; // 27
                if (t < 0) { // 28
                    c = a - c; // 29, c holds the determinant

                    // Carefully optimised case split:
                    if (c < 0.05) // 30
                        a = 0.025;
                    else if (c < 250) // 31
                        a = 2;
                    else a = 193;

                    t = c / a; a = a + t; a = a / 2; // 34
                    t = c / a; a = a + t; a = a / 2; // 37
                    t = c / a; a = a + t; a = a / 2; // 40
                    t = c / a; a = a + t; a = a / 2; // 43
                    t = c / a; a = a + t; a = a / 2; // 46

                    // At this point a ~= sqrt(determinant)
                    t = b / 2; // 47
                    a = a + t; // 48
                    t = t * t; // 49
                    c = t - c; // 50
                    // At this point a ~= b/2 + sqrt(determinant) and c holds its original value
                }
                else {
                    a = b;

                    a = c / a; a = b - a; // 52
                    a = c / a; a = b - a; // 54
                    a = c / a; a = b - a; // 56

                    // At this point a ~= b/2 + sqrt(determinant)
                }

                b = -a; // 57
                c = c / b; // 58
                a = 2;
            }
        }
    }
    else {
        // bx + c = 0
        if (b != 0) { // 59
            a = 1;
            c = -c; // 60
            b = c / b; // 61
        }
        else {
            // c = 0
            if (c != 0) a = 0; // 62
            else a = 3;
        }
    }
}

```

# Answer
> 6 votes
## C, 60

I happen to use the same square root algorithm (Newton) as Peter. However, I think we need to use two different starting values in order to get away with even 8 iterations. The maximum value of `b²/4-c` (the normalised discriminant) is for `b = -c = 1000`. The minimum value is for `b = 0.001; c = 0` (in fact, there are smaller values but these would be beyond the significant digits of b and c). If we split the range of values at `20`, we can use `0.1` as the starting guess for the lower range and `100` as the starting guess for the upper range and always converge in 8 steps. If I could be bothered to keep searching I think I could get this down to 7, and with a few more subdivisions probably even below 6 while still saving operations (but I can't be bothered right now).

```
void qe(&float a, &float b, &float c)
{
    float t; // 20
    if (a)   // 21
    {
        b = b / a;  // 22
        c = c / a;  // 23
        b = b / -2; // 24
        t = b * b;  // 25
        c = t - c;  // 26
        if (c<0)    // 28
        {
            a = 0;
        }
        else
        {
            if (c<20)  // 30
                a = .1
            else
                a = 100

            t = c / a; // 31
            a = a + t; // 32
            a = a / 2; // 33

            t = c / a; // 34
            a = a + t;
            a = a / 2;

            t = c / a; // 37
            a = a + t;
            a = a / 2;

            t = c / a; // 40
            a = a + t;
            a = a / 2;

            t = c / a; // 43
            a = a + t;
            a = a / 2;

            t = c / a; // 46
            t = a + t;
            t = t / 2;

            t = c / a; // 49
            t = a + t;
            t = t / 2;

            t = c / a; // 52
            t = a + t;
            t = t / 2;

            a = 2;
            c = b + t; // 55
            b = b - t; // 56
        }
    }
    else if (b) // 57
    {
        a = 1;
        b = b / c; // 58
        b = -b;    // 59
    }
    else if (c) // 60
    {
        a = 0;
    }
    else
    {
        a = 3;
    }
}

```

# Answer
> 3 votes
## C# (46)

Used a different way of computing sqrt(x) (continued fractions http://en.wikipedia.org/wiki/Methods\_of\_computing\_square\_roots#Generalized\_continued\_fraction)

It fails for b=0 due to large rounding errors. I'm not sure how to fix that, but I hope I can help fellow contestants with a new way of doing the square roots.

Edit: Thanks to @Peter Taylor for the suggestion on how to handle b=0.

Edit 2: Thanks to @steveverrill for pointing out that there are only \>2 solutions if c is also 0, thus requiring an extra if check.

```
       public static void doStuff(ref double a, ref double b, ref double c)
    {
        if (a == 0) //1
        {
            if (b == 0) //2
            {
                if (c == 0){ //3
                   a = 3;
                }
                else {
                   a = 0;
                }
            }
            else
            {
                b = -1 / b;//4
                b = c * b;//5
                a = 1;
            }
        }
        else
        {
            b = b / a;//6
            c = c / a;//7
            if (b == 0) //8
            {
                b = 1 + 1E-7;// still just one constant; since 0.001/1000>1E-7, b can never equal this value normally
                c = c + 0.25; //9
            }
            a = 2 * c;//10
            a = a / b;//11
            a = b - a;//12
            a = c / a; a = b - a;//14
            a = c / a; a = b - a;//16
            a = c / a; a = b - a;//18
            a = c / a; a = b - a;//20
            a = c / a; a = b - a;//22
            a = c / a; a = b - a;//24
            a = c / a; a = b - a;//26
            a = c / a; a = b - a;//28
            a = c / a; a = b - a;//30
            a = c / a; a = b - a;//32
            a = c / a; a = b - a;//34
            a = 2 / a;//35
            a = c * a;//36
            a = b - a;//37
            if (b == 1 + 1E-7) //38
            {
                b = 0;
                c = c - 0.25;//39
            }
            if (a == 0) //40
            {
                b = -1.0 / 2 * b;//41
                c = b;
                a = 2;
            }
            else
            {
                if (a < 0) //42
                {
                    a = 0;
                }
                else
                {
                    b = -1.0 / 2 * b;//43
                    a = a / 2;//44
                    c = b - a;//45
                    b = b + a;//46
                    a = 2;
                }
            }
        }
    }

```

# Answer
> 2 votes
# C, 46 excluding handling a=0 cases, with "fast squareroot" (not "fast inverse squareroot")

**I hope I've scored what I've done so far correctly. I don't know how much more I'll do on this because:**

1. I'm not sure if casting's legal, or how to score it (the union used in another answer is more efficient, but I've not used them before.)
2. I'm a little unclear on the meaning of "2 equal roots are not the same as 1 root." I assume this means that a quadratic will always have either 0 o 2 real roots (which may or may not be equal) and a linear equation (a=0) will have 1 root. I would point out the only infinite case is a=b=c=0. If a=b=0 and c is nonzero, there are no roots.

**Anyway, my main reason for posting is that I wanted to show that it's possible to define a "fast squareroot"** (which is more suitable for the needs of this question than simply copying the famous "fast inverse squareroot" as per some other answers.) Instead of subtracting `i>>1` from a constant, we add `i>>1` to a constant.

The principle of the algorithm is as follows: Assume a float is stored in an imaginary little computer as `2^AAA*1.BBBB` (the 2 and 1 are not stored. AAA is known as the exponent and BBBB as the fraction.)

Performing a rightshift on the number `2^100*1.0000`=16 gives `2^010*1.0000`=4 which is exactly the correct square root. Repeating the process gives `2^001*1.0000`=2. So far we have seen perfectly accurate results.

Now we have an odd power of 2. When we try to calculate the square root of the number 2 by rightshifting, the odd digit of the exponent underflows into the fraction and we get `2^000*1.100` which in decimal is 1.5, an error of approximately +6% on the correct value of sqrt(2)=1.414.

Moving to practical implemenations the 32-bit IEEE float (and the 64-bit, 128 bit etc.) has a bias on the exponent, so we have to add a constant to the raw shifted value. Careful choice of this constant enables the error to be limited to a range of approximately +/-3% which is a pretty good starting guess for The Newton-Raphson method. I found the constant by trial and error (there is room for some improvement, on my test cases it is more likely to give a positive error than a negative error.)

Three iterations of Newton-Raphson cleans it up very well (and may be more than necessary.)

```
void quad(float &a, float &b, float &c) {
  printf("a=%f b=%f c=%f",a,b,c);

  int i;                             //score 20

  c=c/a;                              // c/a
  b=b/a;
  b=b/-2;                             // -b/2a
  a=b*b;
  a=a-c;                              // (b/2a)^2-c/a), score 25

  if (a<0) a=0; else{                 // score 27

    i  = * ( int * ) &a;
    i  = i >>1;
    i  = i+0x1FB90000;
    c  = * ( float * ) &i;            //sqrt( (-b/2a)^2-c/a ) score 31

    i  = * ( long * ) &a;             //don't lose the value (b/2a)^2-c/a
    a=a/c;
    c=c+a;
    a=c/2;
    c  = * ( float * ) &i;            //second iteration
    c=c/a;
    a=a+c;
    a=a/2;
    c  = * ( float * ) &i;            //third iteration
    c=c/a;
    a=a+c;
    a=a/2;                            //score 43 after 3 iteratations

    c=b-a;                            //-b/2a in each
    b=b+a;
    a=2;                              //score 46
  }
}

```

# Answer
> 1 votes
# C++ (~~29 45~~ 44)

Note that each `return` can be removed, simply by using else branch.. it's just more readable. The same with `if(!sth)` can be simply changed using else and empty if branch....

**edit:** Now, with casts allowed, this answer should be correct.

```
void quadr(float &a, float &b, float &c) {
    b = - b;                //1
    if(!(b && c)) {         //3
        if(!a) {            //4
            a = 3;          //
            return;
        }
        a = 1;              //
        return;
    }
    if(!a) {                //5
        a = 1;              //
        b = c / b;          //6
        return;
    }

    b = b / a;              //7
    c = c / a;              //8
    c = c * 4;              //9
    a = b * b;              //10
    a = a - c;              //11
    c = a / 2;              //12

    int t = *(int*)&a;      //32
    t = t >> 1;             //33
    t = 0x5f3759df - t;     //34
    a = *(float*)&t;        //

    c = c * a;              //35
    c = c * a;              //36
    c = 1.5f - c;           //37
    a = a * c;              //38

    a = 1 / a;              //39
    if(!a) {                //40
        a = 0;              //
        return;
    }
    c = b - a;              //41
    b = b + a;              //42
    c = c / 2;              //43
    b = b / 2;              //44
    a = 2;                  //
}

```

I might have missed some case, feel free to prove me wrong :)

# Answer
> 1 votes
# C - ~~50~~ 48

I use the 32-bit float shortcut for getting a good initial seed for the square root. That allows me to get away with just a few iterations of Newton's method. I haven't found a set of coefficients yet that yield unacceptable results (outside the specified precision).

Also, I am not sure how the spec treats pointer operations. For all I know this is disallowed, but hey, I had fun!

```
void primitiveQuad(float *a, float *b, float *c) {
    if(0.0 == *a) { // 1
        if(0.0 != *b) { // 2
            *a = 1.0;
            *b = -1.0/(*b); // 3
            *b = (*b)*(*c); // 4
        }
        else if(*c) // 5
            *a = 0.0;
        else
            *a = 3.0;
    }
    else {
        *b = (*b)/(*a); // 6
        *c = (*c)/(*a); // 7
        *c = 4.0*(*c); // 8
        *a = (*b)*(*b); // 9
        *a = (*a) - (*c); // 10
        *c = *a; // store discriminant here for later
        if(0.0 > *a) // 11
            *a = 0.0;
        else {
            int x = *((int*)(a)); // 31
            x = x - (0x800000); // 32
            x = x >> 1; // 33
            x = x + (0x20000000); // 34
            *a = *((float*)(&x));
            {
                // add precision here through iterations

                // iteration
                x = *((int*)(a));
                *a = (*c)/(*a); // 35
                *a = *a + *((float*)(&x)); // 36
                *a = 0.5*(*a); // 37

                // iteration
                x = *((int*)(a));
                *a = (*c)/(*a); // 38
                *a = *a + *((float*)(&x)); // 39
                *a = 0.5*(*a); // 40

                // iteration
                x = *((int*)(a));
                *a = (*c)/(*a); // 41
                *a = *a + *((float*)(&x)); // 42
                *a = 0.5*(*a); // 43

            }
            *b = 0.0 - *b; // 44
            *c = *b;
            *b = *b + *a; // 45
            *c = *c - *a; // 46
            *b = 0.5*(*b); // 47
            *c = 0.5*(*c); // 48
            *a = 2.0;
        }
    }
}

```

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


title: Don't. Even. Blink

text:
# Question
Title: Don't. Even. Blink
> Your life could depend on this. Don't blink. Don't even blink. Blink and you're dead. They are fast. Faster than you can believe. Don't turn your back, don't look away, and don't blink! **Good luck.**

Weeping Angels are an alien race that cannot move while being observed by another being (even another Angel). They feed by sending their victims back in time. You (The Doctor) are trapped in a room with some, and you need to get to your TARDIS.

---

### Task

Write a program that will, given an ASCII representation of a rectangular room, output a path that will lead you to safety. If any Angel can attack — *at any time during your progress* — then that path is not safe. An Angel can attack if it can see you while not being seen by you or another Angel.

### Input

Input is two parts. First, the direction you're facing (NSEW). Then on succeeding lines, a representation of the room, showing start/end locations, and the location/facing of all Angels.

The sample below shows that there is one angel facing west, and you start facing south.

```
S
..........
....D.....
..........
..........
..........
..........
..........
..........
.........W
..........
...T......

```
* **`.`** \- Empty space
* **`D`** \- The Doctor (starting position)
* **`T`** \- The TARDIS (end position)
* **`N,S,E,W`** \- An Angel, facing the direction specified (north, south, east, west)

### Line of sight

You can see any space withing 45 degrees of the direction you're facing. Line of sight is obstructed if there is another entity along a direct horizontal, vertical, or 45-degree diagonal. Any other diagonal does **not** obstruct the view. Angels' line of sight works in the same way. For example, in the following, `-` represents your field of view, assuming you're facing south.

```
........
...D....
..---...
.-----..
-------.
---N----
---.--N-
---.----

```

### Output

The output is a string representing the path you will take to exit. If there are multiple safe paths, choose any one. If no path is safe, output `0`. If the map is malformed, do whatever you like, including crashing out. Consider it malformed if the room is not rectangular, there is no exit, etc. If there are no Angels, it's not malformed, simply easy.

For each step, you can do one of two things: move in a NSEW direction, or turn to a NSEW direction (without changing positions). To move, simply output the letter for that direction. To turn to face a direction, output `F` followed by the appropriate letter. For example, the following output:

```
SSFESSSSSSSW

```

is a safe path for the sample given in the input section. You move south twice, face east to keep the angel in sight, then move south seven more times and west once to enter the TARDIS.

### Test Cases

1) You can go around the east-facing Angel to get to the TARDIS. Unless you step directly between them, they lock each other in place, so it doesn't matter which way you're facing at any point.

```
W
...D....
........
........
........
.E.....W
........
........
...T....

```

2) You lose. There's no way to get past them. They can see each other until you step between them. At that point, you can't face them both and you're done. Might as well just shut your eyes and get it over with.

```
S
...D....
........
........
........
E......W
........
........
...T....

```

### Winning

Standard golf rules and loopholes apply, least bytes wins. I'll try to get some more test cases soon, but feel free to suggest your own in the meantime.

<sup>Image and quote from Doctor Who. </sup>

# Answer
> 6 votes
# Python – ~~559 565 644~~ 633

```
M=input()
I=1j
Q={"S":I,"N":-I,"E":1,"W":-1}
A=[]
e=enumerate
for y,l in e(M[2:].split()):
 for x,c in e(l):
    P=x+y*1j
    if c=="D":D=(P,Q[M[0]])
    elif c=="T":T=P
    elif c!=".":A+=[(P,Q[c])]
def s(D,h,r=[]):
 def L(X,p,d):
    S=[p+d*(i+j*I)for i in range(x+y)for j in range(-i+1,i)if j]
    for f in[1,1+I,1-I]:
     i=0
     while i<x+y>1>(S[-1]in[a[0]for a in[D]+A]+[T])*i:i+=1;S+=[p+i*f*d]
    return X[0]in S
 if y>=D[0].imag>=(D[0]in[a[0]for a in A])<all(any(L(a,*b)for b in[D]+A)for a in A if L(D,*a))>(D in r)<=D[0].real<=x:
    r+=[D]
    if D[0]==T:print h;exit()
    for n in"SWEN":s((D[0]+Q[n],D[1]),h+n,r);s((D[0],Q[n]),h+"F"+n,r)
s(D,"")
print"0"

```

Input has to be provided like this:

```
"W\n...D....\n........\n........\n........\nE......W\n........\n........\n...T....\n"

```

Essentially it’s this approach applied to finding all states (position and direction) the Doctor can safely reach, storing how he got there and printing the way in case of success. Positions and directions are realised with complex numbers.

I could probably safe some chars using Sage’s complex number arithmetics, but that would run extremely long.

I first thought I could save six characters by having the Doctor turn into a specific direction after reaching the Tardis, but I realised that this could result in wrong solutions. Also I first misread the rules.

Here is a mostly ungolfed version:

```
Map = input()

I = 1j
string_to_dir = {"S":I,"N":-I,"E":1,"W":-1}

Angels = []
Pos = 0
direction = string_to_dir[Map[0]]
for y,line in enumerate(Map[2:].split()):
    for x,char in enumerate(line):
        Pos = x+y*1j
        if char == "D":
            Doctor = (Pos, direction)
        elif char == "T":
            Tardis = (Pos, direction)
        elif char != ".":
            Angels += [(Pos,string_to_dir[char])]

reachables = []

def display(LoS, Doctor):
    string = ""
    for y,line in enumerate(Map[2:].split()):
        for x,char in enumerate(line):
            if x+y*1j == Doctor[0]:
                string += "D"
            elif x+y*1j in LoS:
                if char in ".D":
                    string += "*"
                else:
                    string += "X"
            elif char != "D":
                string += char
            else:
                string += "."

        string += "\n"
    print string

def LoS(angel,Doctor):
    p,d = angel
    Sight = []
    for i in range(x+y):
        for j in set(range(-i+1,i))-{0}:
            Sight += [p+d*i+d*j*I]
    for line in [d, (1+I)*d, (1-I)*d]:
        for i in range(1,x+y):
            Pos = p + i*line
            Sight += [Pos]
            if Pos in [angel[0] for angel in Angels+[Doctor, Tardis]]:
                break
    return Sight

def search(Doctor, history):
    global reachables

    Sight = sum([LoS(angel, Doctor) for angel in [Doctor]+Angels],[])

    if (
                all(angel[0] in Sight for angel in Angels if Doctor[0] in LoS(angel, Doctor))
            and not (Doctor in reachables)
            and (0<=Doctor[0].imag<=y)
            and (0<=Doctor[0].real<=x)
            and (Doctor[0] not in [angel[0] for angel in Angels])
        ):

        reachables += [Doctor]

        if Doctor[0] == Tardis[0]:
            print history
            exit()
        for new_direction in "SWEN":
            search((Doctor[0]+string_to_dir[new_direction], Doctor[1]), history + new_direction)
            search((Doctor[0], string_to_dir[new_direction]), history + "F" + new_direction)

search(Doctor, "")
print "0"

```

# Test Cases

Test case 1:

```
SSSFSWWWSSSSFWEFSEFWE

```

Test case 2:

```
0

```

VisualMelon’s test case:

```
SSFWSSSSSFSWWSSWWWFWEEEEFSEFWEFSE

```

# Answer
> 10 votes
## C# ~~1771~~ ~~2034~~ ~~1962~~ ~~1887~~ 1347bytes

*Re-wrote the blocking LOS checking in 1 loop, making it much tidier, and about 450bytes shorter*

```
using C=System.Console;using T=System.Math;struct P{int x,y,d;static void Main(){int v=C.ReadLine()[0],w,h,i,o=0,x=0,y=0,O,E,F,e=46;var R=C.In.ReadToEnd().Replace("\r","");var M=new int[w=R.IndexOf("\n"),h=(R.Length+1)/(w+1)];for(;o<h;o++)for(i=0;i<w;i++)if((M[i,o]=R[o+o*w+i])==68)M[x=i,y=o]=e;System.Func<int,int,int,bool>S=null;S=(X,Y,D)=>{var Z="SSSE_WNNNE_W___E_W";int I=0,H=0,L=0,J=Y,K=M[X,Y],B;M[X,Y]=D>0?D:K;for(H=0;H<9;H++)for(I=X,J=Y;H!=4&(I+=H%3-1)<w&I>=0&(J+=H/3-1)<h&&J>=0;){if(((B=M[I,J])==Z[H]|B==Z[H+9])&(D<1||!S(I,J,0)))goto W;if(B!=e)break;}for(B=I=-1;++I<w;B=1)for(J=0;J<h;J++)if(I!=X&J!=Y&(((B=M[I,J])==87&I>X&(H=T.Abs(J-Y))<I-X)|(B==69&I<X&H<X-I)|(B==78&J>Y&(L=T.Abs(I-X))<J-Y)|(B==83&J<Y&L<Y-J))&(D<1||!S(I,J,0)))goto W;W:M[X,Y]=K;return B>1;};P a,p=new P{x=x,y=y,d=v};var A=new System.Collections.Generic.List<P>();System.Action q=()=>{if(((E=M[p.x,p.y])==e|E==84)&!A.Contains(p)&!S(p.x,p.y,p.d))A.Add(p);};q();for(o=0;(O=A.Count)!=o;o=O)for(i=O;i-->o;){p=A[i];if((E=M[p.x,p.y])==84)for(R="";;p=a){i=0;n:a=A[i++];O=T.Abs(p.y-a.y)+T.Abs(a.x-p.x);if(O==1&p.d==a.d)R=(a.y-p.y==1?"N":p.y-a.y==1?"S":a.x-p.x==1?"W":"E")+R;else if(O<1)R="F"+(char)p.d+R;else goto n;if(i<2)goto Z;}if(E==e){if(p.x-->0)q();p.x+=2;if(p.x<w)q();p.x--;if(p.y-->0)q();p.y+=2;if(p.y<h)q();p.y--;for(F=0;F<4;q())p.d="NESW"[F++];}}R="0";Z:C.WriteLine(R);}}

```

This is a complete program that expects the input to terminate with an EOF and be passed to STDIN. It (hopefully) prints the shortest path to the TARDIS, or "0" if no path exists. It uses a shoddy Breadth First Search to follow all possible routes, then it backtracks from the TARDIS to The Doctor to assemble the output.

Formatted code:

```
using C=System.Console;
using T=System.Math;

struct P
{
    int x,y,d;

    static void Main()
    {
        int v=C.ReadLine()[0],w,h,i,o=0,x=0,y=0,O,E,F,e=46;
        var R=C.In.ReadToEnd().Replace("\r","");
        var M=new int[w=R.IndexOf("\n"),h=(R.Length+1)/(w+1)];

        for(;o<h;o++)
            for(i=0;i<w;i++)
                if((M[i,o]=R[o+o*w+i])==68)
                    M[x=i,y=o]=e;

        System.Func<int,int,int,bool>S=null;
        S=(X,Y,D)=>
        {
            var Z="SSSE_WNNNE_W___E_W";

            int I=0,H=0,L=0,J=Y,K=M[X,Y],B;
            M[X,Y]=D>0?D:K;

            for(H=0;H<9;H++)
                for(I=X,J=Y;H!=4&(I+=H%3-1)<w&I>=0&(J+=H/3-1)<h&&J>=0;)
                {
                    if(((B=M[I,J])==Z[H]|B==Z[H+9])&(D<1||!S(I,J,0)))
                        goto W;
                    if(B!=e)
                        break;
                }

            for(B=I=-1;++I<w;B=1)
                for(J=0;J<h;J++)
                    if(I!=X&J!=Y&(((B=M[I,J])==87&I>X&(H=T.Abs(J-Y))<I-X)|(B==69&I<X&H<X-I)|(B==78&J>Y&(L=T.Abs(I-X))<J-Y)|(B==83&J<Y&L<Y-J))&(D<1||!S(I,J,0)))
                        goto W;
        W:
            M[X,Y]=K;
            return B>1;
        };

        P a,p=new P{x=x,y=y,d=v};
        var A=new System.Collections.Generic.List<P>();
        System.Action q=()=>{if(((E=M[p.x,p.y])==e|E==84)&!A.Contains(p)&!S(p.x,p.y,p.d))A.Add(p);};
        q();

        for(o=0;(O=A.Count)!=o;o=O)
            for(i=O;i-->o;)
            {
                p=A[i];
                if((E=M[p.x,p.y])==84)
                    for(R="";;p=a)
                    {
                        i=0;
                    n:
                        a=A[i++];

                        O=T.Abs(p.y-a.y)+T.Abs(a.x-p.x);
                        if(O==1&p.d==a.d)
                            R=(a.y-p.y==1?"N":p.y-a.y==1?"S":a.x-p.x==1?"W":"E")+R;
                        else if(O<1)
                            R="F"+(char)p.d+R;
                        else goto n;

                        if(i<2)
                            goto Z;
                    }
                if(E==e)
                {
                    if(p.x-->0)q();
                    p.x+=2;if(p.x<w)q();p.x--;
                    if(p.y-->0)q();
                    p.y+=2;if(p.y<h)q();p.y--;

                    for(F=0;F<4;q())
                        p.d="NESW"[F++];
                }
            }
        R="0";
    Z:
        C.WriteLine(R);
    }
}

```

Output for example input

```
SFESWSSSSSSS

```

Output for test case 1)

```
WSWSWSSSESESE

```

Output for test case 2)

```
0

```

I present, as requested, a new test case:

```
S
..E..DS....
...........
...........
...........
...........
...........
...........
...........
....SSSSS.W
.......T...

```

My program outputs

```
SESESESESFNSSSSWW

```

WozzeC's Test Case 1:

```
EEEEFWSSSFNWWN

```

WozzeC's Test Case 2:

```
FSEEEESFWSSSSWFNWWWNFENNEES

```

# Answer
> 2 votes
# C# ~~1454, 1396, 1373, 1303~~ 1279

```
class P{static int x,d,y=x=d=55,o=170,X=0,Y=0,u,k=3;static string[,]t=new string[o,o];static int[,]m=new int[o,o];static string e=" NS ETD W      .",q="0";static void Main(string[]s){m[0,1]=m[1,8]=-1;m[0,2]=m[1,4]=1;u=e.IndexOf(s[0][0]);for(;k<s[0].Length;k++){var c=s[0][k];if(c=='D'){X=x;Y=y;}if(c=='\\'){y++;x=d;k++;}else m[y,x++]=e.IndexOf(c);}k=A(X,Y,1);if((k&u)!=0){W(X,Y,k,"");}System.Console.Write(q);}static void W(int x,int y,int h,string s){t[y,x]=s;for(int i=1;i<9;i*=2){int l=y+m[0,i],g=x+m[1,i];if(m[l,g]==5)q=t[l,g]=s+e[i];else if(m[l,g]==15){m[l,g]=6;m[y,x]=15;int n=A(g,l,1),U;for(int j=1;j<9;j*=2){var z=t[l,g]??s;if((n&h&j)!=0&z.Length>=s.Length){U=u;u=j;W(g,l,n,s+((u!=j)?"F"+e[j]:"")+e[i]);u=U;}}m[y,x]=6;m[l,g]=0;}}}static int A(int x,int y,int L){int r=15,a,b,c,f=0,g,h,R,B;for(a=1;a<d-5;a++){g=1;for(b=y-a;b<=y+a;b++)for(c=x-a;c<=x+a;c++){B=m[b,c];R=0;bool W=(c+a-x)%a==0,V=(b+a-y)%a==0,z=W&V;if(B>0&B<9&B!=6&B!=5&g!=16&!((W|V)&(f&g)!=0)){h=R;if(b==y-a){R=1;if(c==x-a){h=4;R=9;}else if(c==x+a){h=8;R=5;}B&=h&2;}else if(b==y+a){R=2;if(c==x-a){h=4;R=10;}else if(c==x+a){h=8;R=6;}B&=h&1;}else if(c==x-a){B&=4;R=8;}else if(c==x+a){B&=8;R=4;}else B=0;if(B!=0){if(L==1&&A(c,b,0)==15)r&=R;if(L==0)return R;}}if(z){if(B<9&B>0&!(c==x&y==b))f|=g;g*=2;}}}return r;}}

```

Right. So I decided to give this a go, and boy did it take a while. It's built up mostly using logical operators.

* North = 1 = N
* South = 2 = S
* East = 4 = E
* West = 8 = W
* Doctor = 6 = D
* TARDIS = 5 = T
* 15 = . \<-All free spaces

To avoid having to check for Null etc. I decided to use a field of \[MAX\_SIZE\*3\]\*\[MAX\_SIZE\]\*3 and put the game board close to the center.

Loop checks are done inside and out all the way to 50(MAX\_SIZE). So something like this:

```
22222
21112
21D12
21112
22222

```

When a E W S or N is found I do the same check on their part. If anything is found looking at the Angels (Not the Doctor) they return 15 as free passage. If they are not looked upon they return in which way the Doctor should face to be safe. i.e N would return 2 for south. Unless it is NW or NE in which case it would return 6(2+4) and 10(2+8) respectively.

If two angels are watching the Doctor the return values from these would be "ANDed" so in the test example 2 crunchpositions 4 AND 8 would turn into 0. Meaning that the position is bad and should be avoided.

Expanded code:

```
class P
{
    static int x,d,y=x=d=55,o=170,X=0,Y=0,u,k=3;
    static string[,] t = new string[o, o];
    static int[,] m = new int[o, o];
    static string e = " NS ETD W      .", q="0";
    static void Main(string[]s)
    {
        m[0, 1]=m[1, 8]=-1;
        m[0, 2]=m[1, 4]=1;
        u=e.IndexOf(s[0][0]);
        for (;k<s[0].Length;k++)
        {
            var c = s[0][k];
            if (c == 'D') { X = x; Y = y; }
            if (c == '\\') { y++; x = d; k++; }
            else m[y, x++] = e.IndexOf(c);
        }
        k=A(X,Y,1);
        if ((k&u)!=0)
        {
            W(X, Y, k,"");
        }
        System.Console.Write(q);
    }
    static void W(int x,int y,int h,string s){
        t[y, x] = s;
        for (int i = 1; i < 9; i*=2)
        {
            int l = y+m[0, i], g = x+m[1, i];
            if (m[l, g] == 5)
                q = t[l, g] = s + e[i];
            else if (m[l, g] == 15)
            {
                m[l, g] = 6;
                m[y, x] = 15;
                int n = A(g, l,1),U;
                for (int j = 1; j < 9; j *= 2)
                {
                    var z = t[l, g]??s;
                    if ((n & h & j) != 0 & z.Length>=s.Length)
                    {
                        U = u;
                        u = j;
                        W(g, l, n,s+((u != j) ? "F" + e[j] : "") + e[i]);
                        u = U;
                    }
                }
                m[y, x] = 6;
                m[l, g] = 0;
            }
        }
    }
    static int A(int x, int y,int L)
    {
        int r = 15,a,b,c,f=0,g,h,R,B;
        for (a = 1; a < d - 5; a++)
        {
            g = 1;
            for (b = y - a; b <= y + a; b++)
                for (c = x - a; c <= x + a; c++)
                {
                    B=m[b, c];
                    R=0;
                    bool W=(c+a-x)%a==0,V=(b+a-y)%a==0,z=W&V;
                    if (B>0&B<9&B!=6&B!=5&g!=16&!((W|V)&(f&g)!=0))
                    {
                        h=R;
                        if (b==y-a)
                        {
                            R=1;
                            if(c==x-a){h=4;R=9;}
                            else if(c==x+a){h=8;R=5;}
                            B&=h&2;
                        }
                        else if (b==y+a)
                        {
                            R=2;
                            if(c==x-a){h=4;R=10;}
                            else if (c==x+a){h=8;R=6;}
                            B&=h&1;
                        }
                        else if(c==x-a){B&=4;R=8;}
                        else if(c==x+a){B&=8;R=4;}
                        else B=0;
                        if (B!=0)
                        {
                            if(L==1&&A(c,b,0)==15)r&=R;
                            if (L==0)return R;
                        }
                    }
                    if (z)
                    {
                        if (B < 9 & B > 0 & !(c==x&y==b))
                           f |= g;
                        g *= 2;
                    }
                }
        }
        return r;
    }
}

```

# Test results

1 Example: FNSSSWNNNWSSSWSSSSENNESES

2 Example: No way out

VisualMelon Example: FNSSSSSSSWNNNNNNNWSSSSSSSSSEEEE

My Test case1: FSSENEEEFWSSFNSWWN

My Test case2: FSEEEESFWSSSSFNWWWWNFENNFSEES

As can be seen my Doctor loves strutting around like a douche to show the Angels how fun it is to move around. I can make the software find the shortest path, but it takes longer and needs more code.

# Test cases for you guys

```
S
D....
..NE.
.WTS.
.S...

```

Another one:

```
E
D....
WNNN.
...E.
.WTE.
.SSE.
.....

```

---
Tags: code-golf
---


title: Golf String's format() inverse

text:
# Question
Title: Golf String's format() inverse
Invert the Format method.

The `Format` method of the String class (or equivallent, such as `sprintf`) is available in most languages. It basically takes a "Format" string which may contain placeholders with some extra formatting, and zero or more values to be inserted instead of those placeholders.

Your task is to implement the inverse function in your language of choice.

# API

Method name should be either `format1` or `deformat`.

**Input**: 1st parameter will be the "Format" string, just like in the original format method. 2nd parameter will be the parsed string (see examples below). No other parameters are needed nor allowed.

**Output**: an array (or your language-of-choice's equivalent) of values that were extracted correspondingly with the placeholders in the format.

The placeholders are `{0}`, `{1}`, `{2}`, etc.

In case of bad format you may throw an error, or return whatever you like.

In case of invalid input, you may throw an error, or return whatever you like. Invalid input is such that cannot be generated by String.Format using same format string, for example: `'{0}{0}', 'AAB'`.

# Examples

```
deformat('{0} {1}', 'hello world') => ['hello', 'world']
deformat('http{0}://', 'https://') => ['s']
deformat('http{0}://', 'http://') => [''] // array of one item which is an empty string
deformat('{0}{1}{0}', 'ABBA') => ['A', 'BB']

```

# Ambiguity

In case of ambiguity you may return any suitable answer. For example:

```
deformat('{0} {1}', 'Edsger W. Dijkstra')
// both ['Edsger', 'W. Dijkstra'] and ['Edsger W.', 'Dijkstra'] are applicable.

```

# Some More Rules

* To make it easier, there's no need to actually support formatting. You can forget all about leading zeros, decimal point or rounding issues. Just generate the values as strings.
* To make it non-trivial, **Regular Expressions are not allowed**.
* You don't need to take care of curly braces in input (i.e. 2nd input parameter will not contain any `{`s or `}`s).

# Winning

This is ! (should be read as "This is Sparta!") the correct function having shortest length wins. Standard loopholes are forbidden.

# Answer
> 3 votes
# Haskell, 220 characters

```
import Data.Map;f""""=[empty]
f('{':b)d=[insert k m b|(k,('}':a))<-lex b,(m,c)<-[splitAt n d|n<-[0..length d]],b<-f a c,notMember k b||b!k==m]
f(x:b)(y:d)|x==y=f b d;f _ _=[];format1 x y=elems$mapKeys((0+).read)$f x y!!0

```

Breaks if you use multiple representations for the same pattern (`{1}` vs `{01}`) - doesn't enforce their equality, discarding matches for all but one representation instead.

19 characters can be saved by omiting `mapKeys((0+).read)$` if proper ordering of matches above 10 patterns doesn't matter, or if padding to the same length may be required, or if string ordering of patterns is acceptable. In any case, if a pattern is omitted from the first argument, it is omitted from the result as well.

Removing `!!0` from the end makes `format1` return the list of all solutions, rather than just the first one.

before golfing:

```
import Data.Map
import Control.Monad

cuts :: [a] -> [([a],[a])]
cuts a=[splitAt n a | n <- [0..length a]]

f :: String -> String -> [Map String String]
-- empty format + empty parsed = one interpretation with no binding
f "" "" = [empty]
-- template-start format + some matched = branch search
f ('{':xs) ys = do
    let [(key, '}':xr)] = lex xs
    (match, yr) <- cuts ys
    b <- f xr yr
    guard $ notMember key b || b!key == match
    return $ insert key match b
-- non-empty format + matching parsed = exact match
f (x:xs) (y:ys) | x == y = f xs ys
-- anything else = no interpretation
f _ _ = []

deformat :: String -> String -> [String]
deformat x y = elems $ mapKeys ((0+).read) $ head $ f x y

```

# Answer
> 2 votes
# Ruby, 312 characters

```
class String
def-@
self[0,1].tap{self[0,1]=''}end
end
def format1 f,s,r=[]
loop{if'{'==c=-f
n,f=f.split('}',2)
[*1..s.length,0].each{|i|next if'{'!=f[0]&&s[i]!=f[0]
if u=format1((g=f.gsub("{#{n}}",q=s[0,i])).dup,s[i..-1],r.dup)
r,s,f=u,s[i..-1],g
r[n.to_i]=q
break
end}else
c!=-s&&return
end
""==c&&break}
r
end

```

5 characters could be saved by preferring zero-length matches, making the `ABBA` solution `['', 'ABBA']`, rather than the question's preferred solution. I chose to interpret the examples as an implied part of the specification.

# Answer
> 1 votes
# Python, 208 chars, albeit incomplete.

```
def format1(i,o):
 i+=" ";o+=" ";x=y=0;s=[]
 while x<len(i):
  if i[x]=="{":
   try:y+=len(s[int(i[x+1])])
   except:
    s+=[""]
    while o[y]!=i[x+3]:s[int(i[x+1])]+=o[y];y+=1
   x+=3
  x+=1;y+=1
 return s

```

The function sweeps both strings simultaneously, until it finds a opening brace in the input string, signifying a placeholder.

Then, it assumes the placeholder has already been expanded, and tries to advance the index of the output string past it by looking in the list of values found so far.

If it hasn't been expanded, it adds a new entry to the list of values, and starts adding in characters from the output string until it reaches the character after the placeholder in the input string.

When it gets to the end of the input string, it returns the values found so far.

---

It works well for simple inputs, but it has a number of issues:

* It requires a known delimiter after each placeholder in the input, so it doesn't work with placeholders right next to each other i.e. "{0}{1}". This is why I needed to append a space char to both strings.
* It assumes the first instances of each placeholder are in order e.g. "{**0**}{**1**}{1}{0}{**2**}".
* It only works for the first 10 placeholders as it assumes they are all 3 chars long.
* It doesn't handle ambiguous cases at all :(

# Answer
> 1 votes
# C++11 code, 386 characters

```
#include <string>
#include <map>
using namespace std;using _=map<int,string>;using X=const char;_ format1(X*p,X*s,_ k=_()){_ r;while(*p!='{'){if(!*p||!*s){return*p==*s?k:r;}if(*p++!=*s++)return r;}int v=0;while(*++p!='}'){v=v*10+(*p-48);}p++;if(k.find(v)!=k.end()){return format1((k[v]+p).c_str(),s,k);}while((r=format1(p,s,k)).empty()){k[v]+=*s++;if(!*s){return*p==*s?k:r;}}return r;}

```

The format1 function have 2 strings as input (const char\*) and returns an hashmap with keys integer (the pattern) and value is the identified string. If nothing is found or any error, an empty hashmap is returned.

Usage:

```
for (auto v : format1("{1} {2}", "one two")){
    cout << v.first << "=" << v.second << endl;
}

```

Output:

```
1=one
2=two

```

Example 2:

```
auto v = format1("{1} {2}", "one two");
cout << v[1] << " and " << v[2] << endl;

```

Output:

```
one and two

```

The patterns are in decimal representation, inputs bigger than `MAXINT` will overflow but it still works.

Even though there are smaller solutions in other programming languages, this is the smallest C++ - yet! :)

This is the code before golfing:

```
#include <string>
#include <map>
using namespace std;

using res = map<int,string>;

res format1(const char* p, const char* s, res k=res()){
    res r; // intermediate result, empty until the end
    // match until first '{'
    while (*p != '{'){
        if (!*p || !*s){
            // exit case
            return ((*p == *s) ? k : r); // == 0
        }
        if (*p++ != *s++)
               return r;
    }

    // *p == '{'
    int v = 0;
    while(*++p != '}'){
        v = v*10 + (*p - '0');
    }
    p++; // advance past '}'

    // match back-references
    if (k.find(v) != k.end()){
       return format1((k[v]+p).c_str(), s, k);
    }

    // recursive search
    while ( (r=format1(p, s, k)).empty() ){
        k[v] += *s++;
        if (!*s){
            return *p == *s ? k : r;
        }
    }
    return r;
}

```

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


# Question
Title: Create a program that output's itself as a series of punch cards
Create a program that output's itself as a series of punch cards:

**Rules:**

* You can use any programming language.
* The output (i.e. punch cards) can be ASCII art.
* Each line of code must be able to be punched into a single 80 column x 9 row punch card - i.e. you can only use 80 characters.
* To fit in the 9 rows you need to encode your characters using 4-bit BCD.
* Extra kudos if you use an old programming language like FORTRAN.

**Background**

# Answer
> 2 votes
# Ruby - 925

I'll get the ball rolling. Run as "ruby hammer.rb hammer.rb".

Golfed

```

def z x
l=x.unpack u='C*'
d=[]
(0..9).each do|i|d<<[].fill(48+i,0,80);end
d<<a=[].fill(32,0,80)
d<<a.dup
h=Hash.new
i=0;' abcdefghi'.unpack(u).each do|c|h[c-32]=[i,11];h[c]=[i,11,0];i+=1;end
i=0;' jklmnopqr'.unpack(u).each do|c|h[c-32]=[i,10];h[c]=[i,10,11];i+=1;end
i=0;'  stuvwxyz'.unpack(u).each do|c|h[c-32]=[i,0];h[c]=[i,0,10];i+=1;end
h[47]=[1,0]
i=0;'0123456789-&'.unpack(u).each do|c|h[c]=[i];i+=1;end
i=0;'  :#@\'="'.unpack(u).each do|c|h[c]=[i,8];i+=1;end
i=0;'  [.<(+|'.unpack(u).each do|c|h[c]=[i,8,11];i+=1;end
i=0;'  ]$*);^'.unpack(u).each do|c|h[c]=[i,8,10];i+=1;end
i=0;'  \,%_>?'.unpack(u).each do|c|h[c]=[i,8,0];i+=1;end
h[32]=[]
i=0;l.slice(0,80).each do|c|h[c].each do|r|d[r][i]=215;end;i+=1;end
puts'    %s'%('_'*81)
puts'   /%-80s |'%l.pack(u)
puts'  / %s |'%d[11].pack(u)
puts' /  %s |'%d[10].pack(u)
(0..9).each do|i|puts'|   %s |'%d[i].pack(u);end
puts'|%s|'%('_'*84)
end
ARGF.each do|l|z l.chop;end

```

Ungolfed

```

def punch029(line) # line is array of ASCII characters in ordinal (integer) form
  chad=[]
  (0..9).each do |i| chad<<[].fill(48+i,0,80) end
  chad<<[].fill(32,0,80)
  chad<<[].fill(32,0,80)

  r10 = 10-10
  r11 = 11-1
  r12 = 12-1
  # Reward "bad" input characters with all-row multi-punch.
  # hash = Hash.new( [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] )
  #
  #   OR
  #
  # Reward "bad" input characters by letting Ruby puke. (Jam the machine.)
  hash = Hash.new
  '0123456789-&'.unpack('C*').each_with_index do|c,i| hash[c]=[i] end
  ' ABCDEFGHI'.unpack('C*').each_with_index do|c,i| hash[c]=[i,r12] end
  ' JKLMNOPQR'.unpack('C*').each_with_index do|c,i| hash[c]=[i,r11] end
  ' /STUVWXYZ'.unpack('C*').each_with_index do|c,i| hash[c]=[i,r10] end
  '  :#@\'="'.unpack('C*').each_with_index do|c,i| hash[c]=[i,8] end
  '  [.<(+|'.unpack('C*').each_with_index do|c,i| hash[c]=[i,8,r12] end
  '  ]$*);^'.unpack('C*').each_with_index do|c,i| hash[c]=[i,8,r11] end
  '  \,%_>?'.unpack('C*').each_with_index do|c,i| hash[c]=[i,8,r10] end
  ' abcdefghi'.unpack('C*').each_with_index do|c,i| hash[c]=[i,r12,r10] end
  ' jklmnopqr'.unpack('C*').each_with_index do|c,i| hash[c]=[i,r11,r12] end
  '  stuvwxyz'.unpack('C*').each_with_index do|c,i| hash[c]=[i,r10,r11] end
  hash[32] = []              # fix space

  hole = 215
  line.slice(0,80).each_with_index do |c, index|
    hash[c].each do |row| chad[row][index] = hole end
  end

  puts '    %s' % ('_'*81)
  puts '   /%-80s |' % line.pack('C*')
  puts '  / %s |' % chad[11].pack('C*')
  puts ' /  %s |' % chad[10].pack('C*')
  (0..9).each do |i|
    puts '|   %s |' % chad[i].pack('C*')
  end
  puts "|%s|" % ('_'*84)
end
#        1         2         3         4         5         6         7         8
#2345678901234567890123456789012345678901234567890123456789012345678901234567890

ARGF.each do |line|
  punch029(line.chomp.unpack('C*'))
end

```

---
Tags: popularity-contest, graphical-output
---


title: DNA: Deoxyribonucleic ASCII

text:
# Question
Title: DNA: Deoxyribonucleic ASCII
Given a sequence of the bases Adenine, Cytosine, Guanine and Thymine (encoded as `ACGT`), you're to produce an ASCII art representation of a corresponding double strand of DNA.

The strand will extend vertically. The left-hand strand is the one you are given as input. The right-hand strand will be its complement. For those not familiar with DNA, `A` is paired with `T` and `C` is paired with `G`. Furthermore, there is backbone structure on either side of the double strand which is identical for all bases. So if you were given the input `TAGCAT` the large-scale structure of the ASCII art would be:

```
BTAB
BATB
BGCB
BCGB
BATB
BTAB

```

where `B` represents the backbone. Now each of these letters stands for an entire molecule and you're to reproduce the actual molecular structure.

## The Bases

Use the following templates1 for each of the bases (each one is displayed together with its complementary base and the two backbone molecules):

1Credits to Peter Taylor for helping out with the ASCII layout.

**Adenine**

```
 O    O
  \\ /
    P
   / \
--O   O
     /                                         |
    <            N      NH2 ..... O      *     |
     \         // \    /           \\   /      |
      +--O    //   ----             ----       |
      |   \   |   //  \\           /   \\      |
      |    >--N--<      N ...... HN      >  ---+
      |   /       \    /           \    /  /   |
      +---         N===             ---N--<    |
      |                            //      \   |
      |                           O         O--+
      |                                         \
      |                                          >
      |                                         /
                                               O   O--
                                                \ /
                                                 P
                                                / \\
                                               O    O

```

**Cytosine**

```
 O    O
  \\ /
    P
   / \
--O   O            NH2 ..... O      N
     /            /           \\   / \\        |
    <         ----             ----   \\    ---+
     \       //  \\           /   \\   |   /   |
      +--O  <      N ...... HN      >--N--<    |
      |   \  \    /           \    /       \   |
      |    >--N---             ===N         O--+
      |   /      \\           /                 \
      +---         O ..... H2N                   >
      |                                         /
                                               O   O--
                                                \ /
                                                 P
                                                / \\
                                               O    O

```

**Guanine**

```
 O    O
  \\ /
    P
   / \
--O   O
     /                                         |
    <            N      O ..... H2N            |
     \         // \   //           \           |
      +--O    //   ----             ----       |
      |   \   |   //   \           //  \\      |
      |    >--N--<      NH ...... N      >  ---+
      |   /       \    /           \    /  /   |
      +---         N===             ---N--<    |
      |                \           //      \   |
      |                 NH2 ..... O         O--+
      |                                         \
      |                                          >
      |                                         /
                                               O   O--
                                                \ /
                                                 P
                                                / \\
                                               O    O

```

**Thymine**

```
 O    O
  \\ /
    P
   / \
--O   O     *      O ..... H2N      N
     /       \   //           \    / \\        |
    <         ----             ----   \\    ---+
     \       //   \           //  \\   |   /   |
      +--O  <      NH ...... N      >--N--<    |
      |   \  \    /           \    /       \   |
      |    >--N---             ===N         O--+
      |   /      \\                             \
      +---         O                             >
      |                                         /
                                               O   O--
                                                \ /
                                                 P
                                                / \\
                                               O    O

```

## Constructing the Double Strand

These repeat vertically, such that there are no gaps in the backbone structure. This means that the bounding boxes of these four templates will overlap.

The bottom end of the left and top end of the right backbone will connect to the `O` of an `OH`.

The free `O` at the top end of the left and bottom end of the right backbone will have a free bond going inwards, indicated by `--`.

**Example** `ATG`

```
 O    O--
  \\ /
    P
   / \
--O   O                                        OH
     /                                         |
    <            N      NH2 ..... O      *     |
     \         // \    /           \\   /      |
      +--O    //   ----             ----       |
      |   \   |   //  \\           /   \\      |
      |    >--N--<      N ...... HN      >  ---+
      |   /       \    /           \    /  /   |
      +---         N===             ---N--<    |
      |                            //      \   |
      |                           O         O--+
      |                                         \
      |                                          >
      |                                         /
 O    O                                        O   O--
  \\ /                                          \ /
    P                                            P
   / \                                          / \\
--O   O     *      O ..... H2N      N          O    O
     /       \   //           \    / \\        |
    <         ----             ----   \\    ---+
     \       //   \           //  \\   |   /   |
      +--O  <      NH ...... N      >--N--<    |
      |   \  \    /           \    /       \   |
      |    >--N---             ===N         O--+
      |   /      \\                             \
      +---         O                             >
      |                                         /
 O    O                                        O   O--
  \\ /                                          \ /
    P                                            P
   / \                                          / \\
--O   O                                        O    O
     /                                         |
    <            N      O ..... H2N            |
     \         // \   //           \           |
      +--O    //   ----             ----       |
      |   \   |   //   \           //  \\      |
      |    >--N--<      NH ...... N      >  ---+
      |   /       \    /           \    /  /   |
      +---         N===             ---N--<    |
      |                \           //      \   |
      |                 NH2 ..... O         O--+
      |                                         \
      |                                          >
      |                                         /
      OH                                       O   O--
                                                \ /
                                                 P
                                                / \\
                                             --O    O

```

**More Examples:**

Here are the MD5 hashes of several more examples (without extraneous leading or trailing spaces):

```
ATG      2e4a906c44a96fe84134bf4346adf11c (this is the above example)
C        e3648b8960967463784818c3eee57246
TTT      6028a90b05775905ef1a00e7a45463c5
TAGCAT   3b834d2b7b9adc4113ffabd52d354c41
GATTACA  a19463f965c641d071e07da59d64a418

```

Let me know if you think any of these are wrong.

If you're unsure how to check your results' hashes reliably, try this online MD5 generator. Make sure that there is no trailing line break.

## Further Notes

You *may* use leading or trailing spaces as you see fit. Of course, if you use leading spaces it has to be the same amount in each line.

If I have made any mistakes in copying the chemical structure, the above templates are still normative for the purposes of this challenge.

You may write a function or a program which takes the input *string* as a parameter, command-line argument via STDIN or expects it to be stored in a variable. Write the resulting ASCII art to STDOUT.

This is code golf, so the shortest answer (in bytes) wins.

# Answer
# Perl 5 (510)

Perl's fine with null bytes, so please use the hexdump provided for running this.

This works by printing out different parts of the DNA strand, with parts being one or more lines. An O or H is appended to the top line of each component to ensure valid output.

Assumes input is in the variable `$_`.

Golfed version:

```
use Compress::Zlib;@f=(eval uncompress q+xœÍUËnÃ ¼ó{³””¬”slqäù |xšÅ<
MÔv¤(1b¼;Ì„]8× `?CÐË×ÂÜ/¥Àîº¤Â—¼ÃÍ"6p!ÇvDÿ@k
‘®^ÝÀ
²>ÈB$ì¡ÌHBýi`ã\qþˆRn^‚¢6WéJ±íRCXÀ\Cj[ëzÖKg-µ€˜*Rt®abš3‘ª¤°È†"]ÖSX‰G2ôœÂV<<#9_ÐŽG´8Oa3uE'ÇC%…¹—tLºšÂBCQ‹¡NÈ»*/
V×AÛVÔÖAr©KûÊhát°DÃÁZÿÁ>;       kM‚2(9áýIP
t'A”¿žg
q= Š[~yÌ²ùNÇsNsŽŽG×œ:IÏqŠÙl)˜ùð
ì…çÎÁ«:eôu?<(-  é æ ŽRxNSÜAM1Â• —)š—%+);s/./$y.=$f[$u?8:9].$f[$q=(-65+ord$&)%15].($u++?"    O":H).$f[$q+1]/ge;($y.=$f[10])=~s/@/\\/g;print$y

```

Ungolfed version:

```
use Compress::Zlib;
# load parts to @f; see below for list of parts
@f=(eval uncompress q+ .... +);
# for each chracater in input ($_)
s/./
    # append either the one or two backbone molecules
    # then append most of the first line of the base, followed by an O or H
    # then append the rest of the base
    $y .= $f[$u?8:9] . $f[$q = (-65+ord$&)%15] . ($u++?"    O":H) . $f[$q+1]
/ge;
# append the last backbone molecule, then replace
#  @ with \
($y .= $f[10])=~s/@/\\/g;
print $y

```

`(-65+ord$&)%15` conveniently results in `A=>0, C=>2, T=>4, G=>6`, which is perfect as the program needs two elements in the array for each letter.

The center part, top part, and bottom part are stored in indices `8-10` in that order.

List of Parts (uses @ instead of \ to avoid a ton of escaping):

```
'--O   O                                        O',
'
     /                                         |
    <            N      NH2 ..... O      *     |
     @         // @    /           @@   /      |
      +--O    //   ----             ----       |
      |   @   |   //  @@           /   @@      |
      |    >--N--<      N ...... HN      >  ---+
      |   /       @    /           @    /  /   |
      +---         N===             ---N--<    |
      |                            //      @   |
      |                           O         O--+
      |                                         @
      |                                          >
',
'--O   O            NH2 ..... O      N          O',
'
     /            /           @@   / @@        |
    <         ----             ----   @@    ---+
     @       //  @@           /   @@   |   /   |
      +--O  <      N ...... HN      >--N--<    |
      |   @  @    /           @    /       @   |
      |    >--N---             ===N         O--+
      |   /      @@           /                 @
      +---         O ..... H2N                   >
',
'--O   O     *      O ..... H2N      N          O',
'
     /       @   //           @    / @@        |
    <         ----             ----   @@    ---+
     @       //   @           //  @@   |   /   |
      +--O  <      NH ...... N      >--N--<    |
      |   @  @    /           @    /       @   |
      |    >--N---             ===N         O--+
      |   /      @@                             @
      +---         O                             >
',
'--O   O                                        O',
'
     /                                         |
    <            N      O ..... H2N            |
     @         // @   //           @           |
      +--O    //   ----             ----       |
      |   @   |   //   @           //  @@      |
      |    >--N--<      NH ...... N      >  ---+
      |   /       @    /           @    /  /   |
      +---         N===             ---N--<    |
      |                @           //      @   |
      |                 NH2 ..... O         O--+
      |                                         @
      |                                          >
',
'      |                                         /
 O    O                                        O   O--
  @@ /                                          @ /
    P                                            P
   / @                                          / @@
',
' O    O--
  @@ /
    P
   / @
',
'      |                                         /
      OH                                       O   O--
                                                @ /
                                                 P
                                                / @@
                                             --O    O'

```

Hexdump:

```
0000000 7375 2065 6f43 706d 6572 7373 3a3a 6c5a
0000010 6269 403b 3d66 6528 6176 206c 6e75 6f63
0000020 706d 6572 7373 7120 782b cd9c cb55 c36e
0000030 1020 f3bc 7b15 94b3 ac94 7394 716c 04e4
0000040 20f9 7c7f 9a78 3cc5 4d0a 76d4 28a4 6231
0000050 3bbc 84cc 385d 00d7 3f60 d043 d7cb dcc2
0000060 1c2f c0a5 08ee ba0f c2a4 bc97 cdc3 3622
0000070 2170 1004 76c7 ff44 6b40 910a 0216 ae01
0000080 8d5e 0fdd 0dc0 3eb2 42c8 ec24 cca1 481e
0000090 9042 08fd 8169 6012 5ce3 fe71 5288 5e6e
00000a0 0c82 36a2 e957 084a edb1 4352 c058 435c
00000b0 5b6a ebad d67a 4b10 2d67 80b5 2a98 108d
00000c0 1052 ae74 0c61 9a62 1b01 9133 a4aa c8b0
00000d0 2286 d65d 5853 4789 f432 c29c 3c56 233c
00000e0 1839 d05f 478e 38b4 614f 1e33 0775 2745
00000f0 c71e 2543 b985 1306 7497 ba4c c29a 4342
0000100 510e a18b 4e0e bbc8 082a 0715 0d2f d756
0000110 db41 5616 7fd4 41d6 a972 4b10 0efb 68ca
0000120 7fe1 b074 c344 1ec1 ff5a 1ec1 3b3e 1a09
0000130 6b09 824d 2832 e139 49fd 0f50 740a 4127
0000140 9411 9ebf 6704 710d 3dad 8a09 175b 797e
0000150 cc12 90b2 4ef9 73c7 4e0b 7311 8e8e d747
0000160 1b9c 493a 71cf d98a 296c f998 0df0 85ec
0000170 cee7 abc1 1a3a f465 3f75 283c 2d07 0907
0000180 a0e9 20e6 528e 7813 534e 41dc 314d 95c2
0000190 97a0 2917 979a 2b25 3b29 2f73 2f2e 7924
00001a0 3d2e 6624 245b 3f75 3a38 5d39 242e 5b66
00001b0 7124 283d 362d 2b35 726f 2464 2926 3125
00001c0 5d35 282e 7524 2b2b 223f 2020 2020 224f
00001d0 483a 2e29 6624 245b 2b71 5d31 672f 3b65
00001e0 2428 2e79 243d 5b66 3031 295d 7e3d 2f73
00001f0 2f40 5c5c 672f 703b 6972 746e 7924
00001fe

```
> 2 votes

# Answer
# Python 3, 1008 bytes

Decomposite to smaller blocks and then compress using python's zlib and encode the binary data with asii85 encoding. Before compressing, the size is 629 and after compression and encoding, the size is 260.

Smaller blocks:

```
    N      NH2            NH2 ...   *      O .....      N      O ..     O    O              ---+
  // \    /              /           \   //           // \   //          \\ /              /   |
 //   ----           ----             ----           //   ----             P            --<    |
 |   //  \\         //  \\           //   \          |   //   \           / \              \   |
 N--<      N ..    <      N .....   <      NH ....   N--<      NH .    --O   O              O--+
     \    /         \    /           \    /              \    /             /                   \
      N===           N---             N---                N===             <                     >
                        \\               \\                   \             \                   /
                          O .....          O                   NH2           +--O              O   O--
                                                                             |   \              \ /
                                                                             |    >--            P
                                                                             |   /              / \\
                                                                             +---              O    O

```

The program reads from STDIN. It may have trailing spaces at the end of each line and may have empty lines at the end.

```
import zlib,base64
D=input()
B=b'GasbU3tfFR$q,H5@dA9CAl@Bd?/ZcRUN$!!66MJ3&IN+RbL6[r)7K,3-8;3.^a\'7XZD_Lh;(7`.g>%[1,o(<9L\\neaPK"9^lCg7teknAd\\HXFNbL!)l/pG]YNpRS-C]sXR5A[A[#C&pnT;I-Q$Bj@n$L"ODZk8M_YcM#\\5PaLq3@UfJmfm[)$+#H,A\\B+b`mL9^OQ/cET-@`YRD_DJ6mXMD">9HHep\\%LnL8&\\G?fDdbs20%[J\'jMG[Qp'
B=[b.split('\n')for b in zlib.decompress(base64.a85decode(B)).decode().split('\n\n')]
C=dict(zip('/\\<>', '\\/><'))
a=[(6,14),(6,28),(10,40)]
b=[(4,12),(4,26),(6,40)]
P=[a,b,b,a]
H=[18,14,14,18]
J=''.join
R=range
L=len
F=[[' ']*54 for _ in R(5+18*L(D))]
e=enumerate
y=0
def t(b,p):
 for i,r in e(b):
  for j,c in e(r):
   if' '!=c:F[y+p[0]+i][p[1]+j]=c
O=['OH']
U=['--']
t(O,(4,47))
t(U,(0,7))
for i in map('ACTG'.index,D):
 a,b,c=P[i];t(B[4],(0,0));t(B[i],a);q=B[(i+2)%4];t([J(C.get(z,z)for z in l[::-1]).replace('2HN', 'H2N')for l in[r+' '*(max(map(L,q))-L(r))for r in q]],b);t(B[5],c)
 for j in R(y+13,y+H[i]):F[j][6]='|'
 for j in R(y+5,y+c[0]):F[j][47]='|'
 y+=H[i]
t(O,(0,6))
t(U,(4,45))
for l in F:print(J(l))

```

Checksum matched using this script

And here's the ungolfed version:

```
import zlib, base64

flip_char_map = dict(zip('/\\<>', '\\/><'))

def flip_char(c):
    return flip_char_map.get(c, c)

def pad(block):
    w = max(map(len, block))
    return [line + ' ' * (w - len(line)) for line in block]

def flip(block):
    return [''.join(map(flip_char, line[::-1])).replace('2HN', 'H2N') for line in pad(block)]

blocks = b'GasbU3tfFR$q,H5@dA9CAl@Bd?/ZcRUN$!!66MJ3&IN+RbL6[r)7K,3-8;3.^a\'7XZD_Lh;(7`.g>%[1,o(<9L\\neaPK"9^lCg7teknAd\\HXFNbL!)l/pG]YNpRS-C]sXR5A[A[#C&pnT;I-Q$Bj@n$L"ODZk8M_YcM#\\5PaLq3@UfJmfm[)$+#H,A\\B+b`mL9^OQ/cET-@`YRD_DJ6mXMD">9HHep\\%LnL8&\\G?fDdbs20%[J\'jMG[Qp'
blocks = [b.split('\n') for b in zlib.decompress(base64.a85decode(blocks)).decode().split('\n\n')]

poss = [
    [(6, 14), (6, 28), (10, 40)],
    [(4, 12), (4, 26), (6, 40)],
    [(4, 12), (4, 26), (6, 40)],
    [(6, 14), (6, 28), (10, 40)],
]

heights = [18, 14, 14, 18]

get_id = 'ACTG'.index
dna = input()
height = sum(heights[get_id(x)] for x in dna)
field = [[' '] * 54 for _ in range(height + 5)]

def put(block, pos):
    i, j = pos
    for di, row in enumerate(block):
        for dj, c in enumerate(row):
            if c != ' ': field[y + i + di][j + dj] = c

y = 0
put(['OH'], (4, 47))
put(['--'], (0, 7))
for p in dna:
    i = get_id(p)
    h = heights[i]
    pos = poss[i]
    put(blocks[4], (0, 0))
    put(blocks[i], pos[0])
    put(flip(blocks[(i + 2) % 4]), pos[1])
    put(blocks[5], pos[2])
    for j in range(y + 13, y + h):
        field[j][6] = '|'
    for j in range(y + 5, y + pos[2][0]):
        field[j][47] = '|'
    y += h
put(['OH'], (0, 6))
put(['--'], (4, 45))

for line in field: print(''.join(line).rstrip())

from hashlib import md5
import sys
result = '\n'.join(map(str.rstrip, map(''.join, field))).encode()
print(md5(result).hexdigest(), file=sys.stderr)

```
> 5 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity, chemistry
---


# Question
Title: fit 22 (perhaps 23) of a specific 3d pentacube into a 5x5 cube
**Update:** It seems that the original question at math.SE was solved, there should be no 23 pieces solution.

The original problem is stated here over at math.SE

The task is writing a program that fits 22 copies (or perhaps 23) of the following pentacube into a 5x5x5 cube (back and front view).

The pentacube must be placed within the grid (no 45° orientations and shifts of 0.5 etc.) of the big cube and can be rotated around any of the x,y,z axes in 90° steps.

### Known up to now:

According to the math.SE question there is a solution for 22 pieces, but it is unknown whether there is a solution for 23 pieces. (24 again seems to be impossible).

### Winning criteria

Rotatation and mirroring of one solution count all as the same solution. Finding *all* solutions means that the program must show that the solutions provided are really all possible solutions. You will get (points will add up)

* 10 points for finding any 22 piece solution
* 20 points for finding two or more 22 piece solutions
* 50 points for finding all 22 piece solution
* 100 points for finding a 23 piece solution
* 200 points for finding two or more 23 piece solutions
* 500 points for finding all 23 piece solutions or showing that there is no 23 piece solution
* 1 point per vote

If two people have the same amount of points the one that postet first will win. Please explain your approach and show the solution/s (at least one if there is one.) Please also include your score (except votes) and the runtime in your answer. I discourage hardcoding answers. If you find solutions 'by hand' or if you find a mathematical proof you can also submit them, but please state this explicitly if you do so.

**UPDATE**: In the original post in math.SE now 64 solutions for 22 pieces have been found (non exhausive, and perhaps some of them are rotations/mirrorings of others). So I discourage just copying these solutions - but as long as you found them on your own this is ok!

# Answer
## Plane-based analysis, 30+ points

The basic idea is explained in the comment at the top of the class. This runs for about 8 minutes on my desktop and finds 90560 22-tile solutions, possibly including symmetrical ones; since a cube has only 48 isometries, that corresponds to at least 1887 distinct solutions. However, it doesn't guarantee that there are no more: only that if there are any more, they don't have two opposite exterior faces which contain 3 cubies each of 8.

Two sample solutions:

```
ddbee dubb. ruut. rlktt llkk.
adbbe aduee rrutt lrkjj lookj
aa.ff qa.f. .q.vv ioov. iiojj
ggchf qgcfh qqssv impnv mipnn
gcchh gcssh ...s. .m.pn mmppn

.ggff qqgf. .q.uu .llpu oolpp
bgddf bgvdf qqvu. ooiup ollip
bbdee rbdve rrvv. .mijj mmiij
hhcea rhcae .rstt kmsnt mknjj
hccaa hc.a. .sst. ks.nt kknn.

```

Checking for 23-tile solutions with the same principle is a matter of changing `tilesInPlane2` to 7; it runs for about one minute and finds no solutions.

I suggest redirecting stdout to a file and watching the progress reports on stderr.

```
import java.util.*;

// Overall approach follows a strategy proposed by Ed Pegg.
// If we place one 8-tile board on plane 0 sticking into plane 1,
// and one 8-tile board on plane 4 sticking into plane 3,
// what can fit into plane 2 sticking into planes 1 and 3?
// Since an 8-tile plane occupies at least 16/25 of the adjacent plane, we're looking to fit 4/7 of the tiles from
// plane 2 into the gaps left by the tiles from plane 0, and then the remaining 3/7 into the gaps left
// by the tiles from plane 4.
public class CodeGolf36250 {
    // Bit mask: 25 bits indicating the "main" plane, 25 bits indicating the "adjacent" plane
    static final long mainPlane = (1L << 25) - 1;
    static final long adjPlane = ((1L << 25) - 1) << 25;

    static final int tilesInPlane2 = 6;
    static final int tilesInPlanes2_3 = (tilesInPlane2 + 1) / 2; // Half rounded up

    public static void main(String[] args) {
        Set<Long> primitives = new HashSet<Long>();
        for (int x = 0; x < 4; x++) {
            for (int y = 0; y < 4; y++) {
                int tl = x + y * 5;
                // We consider only positions where we put 3 cubies in the main plane and 2 in the adjacent plane.
                // Diagram format: main plane, adj plane
                // So we have
                //  c000 c100   c001 c101
                //  c010 c110   c011 c111
                long c000 = 1L << tl, c100 = c000 << 1, c010 = c000 << 5, c110 = c100 << 5;
                long c001 = c000 << 25, c101 = c100 << 25, c011 = c010 << 25, c111 = c110 << 25;
                // ##  .#  |  ##  #.  |  #.  #.  |  .#  .#
                // #.  #.  |  .#  .#  |  ##  .#  |  ##  #.
                primitives.add(c000 + c100 + c010 + c101 + c011);
                primitives.add(c000 + c100 + c110 + c001 + c111);
                primitives.add(c000 + c010 + c110 + c001 + c111);
                primitives.add(c100 + c010 + c110 + c101 + c011);
                // ##  .#  |  ##  ..  |  ##  #.  |  ##  ..
                // #.  .#  |  #.  ##  |  .#  #.  |  .#  ##
                primitives.add(c000 + c100 + c010 + c101 + c111);
                primitives.add(c000 + c100 + c010 + c011 + c111);
                primitives.add(c000 + c100 + c110 + c001 + c011);
                primitives.add(c000 + c100 + c110 + c011 + c111);
                // #.  .#  |  #.  ##  |  .#  #.  |  .#  ##
                // ##  .#  |  ##  ..  |  ##  #.  |  ##  ..
                primitives.add(c000 + c010 + c110 + c101 + c111);
                primitives.add(c000 + c010 + c110 + c001 + c101);
                primitives.add(c100 + c010 + c110 + c001 + c011);
                primitives.add(c100 + c010 + c110 + c001 + c101);
            }
        }

        // Building full sets of tiles in the two planes uses far too much memory in the intermediate numbers
        // (in particular, the 5-tile sets).
        // It's much more efficient to see what coverings of the main plane we get and then for the high-count
        // sets we care about, to expand them to the adjacent plane.
        List<Set<TileSet>> nTiles = new ArrayList<Set<TileSet>>();
        nTiles.add(new HashSet<TileSet>()); // 0 tiles
        nTiles.get(0).add(new TileSet());
        for (int n = 1; n < 9; n++) {
            Set<TileSet> next = new HashSet<TileSet>();
            for (TileSet board : nTiles.get(n - 1)) {
                for (long prim : primitives) {
                    if ((board.sum & prim) == 0) {
                        TileSet newBoard = new TileSet();
                        newBoard.addAll(board);
                        newBoard.add(prim & mainPlane);
                        next.add(newBoard);
                    }
                }
            }
            nTiles.add(next);
            System.err.println(n+" tiles: " + next.size());
        }

        // Needed for the expansion.
        Map<Long, Set<Long>> primsByMainPlane = new HashMap<Long, Set<Long>>();
        for (Long prim : primitives) {
            Set<Long> group = primsByMainPlane.get(prim & mainPlane);
            if (group == null) primsByMainPlane.put(prim & mainPlane, group = new HashSet<Long>());
            group.add(prim);
        }

        Map<Long, Set<TileSet>> boards8ByAdjGaps = new HashMap<Long, Set<TileSet>>();
        for (TileSet board8 : nTiles.get(8)) {
            for (TileSet expandedBoard8 : expand(board8, primsByMainPlane)) {
                long expansion = (~expandedBoard8.sum) & adjPlane;
                Set<TileSet> boards8 = boards8ByAdjGaps.get(expansion);
                if (boards8 == null) boards8ByAdjGaps.put(expansion, boards8 = new HashSet<TileSet>());
                boards8.add(expandedBoard8);
            }
        }
        System.err.println(boards8ByAdjGaps.size() + " distinct gap sets in plane next to full one");

        long solutions = 0;
        int progress = 0;
        for (TileSet board : nTiles.get(tilesInPlane2)) {
            // Each board is only expanded once, but we don't keep them all around so we save a lot of memory
            for (TileSet plane2 : expand(board, primsByMainPlane)) {
                for (Map.Entry<Long, Set<TileSet>> plane0 : boards8ByAdjGaps.entrySet()) {
                    solutions += countSolutions(plane0.getKey(), plane0.getValue(), plane2, boards8ByAdjGaps);
                }
            }

            progress++;
            // Progress reports are always good for long processes...
            if (progress % 1000 == 0) System.err.println("Progress: " + progress + "; solutions: " + solutions);
        }
    }

    private static Set<TileSet> expand(TileSet board, Map<Long, Set<Long>> primsByMainPlane) {
        Set<TileSet> bexps = new HashSet<TileSet>();
        bexps.add(new TileSet());
        for (Long tileBase : board) {
            Set<TileSet> nextBexps = new HashSet<TileSet>();
            for (TileSet bexp : bexps) {
                for (Long texp : primsByMainPlane.get(tileBase)) {
                    if ((bexp.sum & texp) == 0) {
                        TileSet nextBexp = new TileSet();
                        nextBexp.addAll(bexp);
                        nextBexp.add(texp);
                        nextBexps.add(nextBexp);
                    }
                }
            }
            bexps = nextBexps;
        }
        return bexps;
    }

    private static int countSolutions(long gaps1, Set<TileSet> planes0, TileSet plane2, Map<Long, Set<TileSet>> boards8ByAdjGaps) {
        int solutions = 0;
        int fitTiles = 0;
        long unfitTiles = 0;
        for (Long tile : plane2) {
            if ((tile & adjPlane) == (tile & gaps1)) fitTiles++;
            else unfitTiles |= tile;
        }

        if (fitTiles >= tilesInPlanes2_3) {
            for (Map.Entry<Long, Set<TileSet>> planes4 : boards8ByAdjGaps.entrySet()) {
                long gaps3 = planes4.getKey();
                if ((unfitTiles & adjPlane) == (unfitTiles & gaps3)) {
                    // The Cartesian product of planes0 and planes4.getValue() are all solutions with the same
                    // plane2
                    for (TileSet plane4 : planes4.getValue()) {
                        for (TileSet plane0 : planes0) {
                            printSolutions(plane0, plane2, unfitTiles, plane4);
                            solutions++;
                        }
                    }
                }
            }
        }

        return solutions;
    }

    private static void printSolutions(TileSet plane0, TileSet plane2, long unfitTiles, TileSet plane4) {
        char[][][] cube = new char[5][5][5];
        // plane0's main plane is 0
        char tileName = 'a';
        for (Long tile : plane0) {
            populatePlane(cube[0], tile & mainPlane, tileName);
            populatePlane(cube[1], tile >> 25, tileName);
            tileName++;
        }
        for (Long tile : plane4) {
            populatePlane(cube[4], tile & mainPlane, tileName);
            populatePlane(cube[3], tile >> 25, tileName);
            tileName++;
        }
        for (Long tile : plane2) {
            populatePlane(cube[2], tile & mainPlane, tileName);
            // The tricky bit: up or down? We look to unfitTiles.
            populatePlane(cube[(unfitTiles & tile) == 0 ? 1 : 3], tile >> 25, tileName);
            tileName++;
        }

        // Print as plane0 plane1 plane2 plane3 plane4
        for (int y = 0; y < 5; y++) {
            for (int z = 0; z < 5; z++) {
                for (int x = 0; x < 5; x++) {
                    System.out.print(cube[z][y][x] == 0 ? '.' : cube[z][y][x]);
                }
                System.out.print(' ');
            }
            System.out.println();
        }
        System.out.println();
        System.out.println();
    }

    private static void populatePlane(char[][] plane, long values, char tile) {
        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 5; y++) {
                if ((values & (1 << (x + 5*y))) != 0) {
                    if (plane[y][x] != 0) throw new IllegalStateException("Collision!");
                    plane[y][x] = tile;
                }
            }
        }
    }

    static class TileSet extends HashSet<Long> {
        private long sum = 0;

        @Override
        public boolean add(Long val) {
            if ((val & sum) != 0) throw new IllegalArgumentException();
            sum |= val;
            return super.add(val);
        }
    }
}

```
> 6 votes

---
Tags: code-challenge
---


# Question
Title: In what base this string equals the following decimal value?
**your task is...**

Given a string **x** and a positive integer **y**, to determine whether there is a positive integer **b** and an injective mapping from the distinct characters in **x** to the digits of base **b** which permit us to interpret **x** as an integer equal to **y**.

**details:**

If there is more than one base which works, you **don't** have to output **all of them**, just one.
The answer should be a function for those languages that support it, otherwise, code snippet
Your program should accept 0-9 and (a-z **or** A-Z) which are 36 characters. You don't have to care about kanji or snowman.
(e.g. 6 doesn't have to mean 6, it's just a symbol. basically you get a number in unknown base with unknown symbols and you have to substitute them to get **y**)

**for example:**

`(foo,4)` returns either **2** or **3** because

* f=1, o=0 -\> 1002=410
* f=0, o=1 -\> 0113=410

`(10,10)` any integer greater than 4 but not 9 because

* 1=2, 0=0 -\> 205=1010
* 1=1, 0=4 -\> 146=1010
* 1=1, 0=3 -\> 137=1010
* 1=1, 0=2 -\> 128=1010
* 1=1, 0=0 -\> 1010=1010
* 1=0, 0=10 -\> 0111=1010
* above base 10, 1=0, 0=10 -\> 01x=1010 for every `x > 10`

`(611,1)` returns **0** which means there is no possible base for `611` meaning 110

**bonus:**

You have to output every possible base, not just one. I know it can be infinite,
indicate it somehow. `2,3,...` for example.
Answers with bonus gain a **0.7 multiplier**.

# Answer
## Mathematica, 183 bytes * 0.7 = 128.1

```
f[s_,n_]:=(For[i=2,1>0,++i,d=(l=Length)@(g=IntegerDigits)[n,i];Which[Count[c=Characters@s,c[[-1]]]>1&&d==1,Return@0,l@c>=d&&And@@Unequal@@@(t=Thread)@Union@t@{g[n,i,l@c],c},Print@i]])

```

Less golf

```
f[s_, n_] := (
  For[i = 2, 1 > 0, ++i,
   d = (l = Length)@(g = IntegerDigits)[n, i];
   Which[
    Count[c = Characters@s, c[[-1]]] > 1 && d == 1,
    Return@0,
    l@c >= d && And @@
      Unequal @@@
       (t = Thread)@
        Union@
         t@
          {g[n, i, l@c], c},
    Print@i
    ]
   ]
  )

```

I don't actually recommend running this, because quick and infinite output is a bit tricky to abort in Mathematica sometimes. To get only the first result, change `Print` to `Result` (which is even a character longer). If you're using the version as is, a final `0` output will indicate that no further bases will be found (similar to the returning case).

The first part of the `Which` simply aborts the loop when no base can possibly be found (it might be possible to shorten this). The second loop is the interesting check. These are the steps taken:

* Convert `n` to digits in the current base (Mathematica can handle arbitrarily large bases.)
* Zip those digits up with the characters, basically creating the mapping at each position.
* `Union` throws out duplicates - these are uninteresting because they just point to a consistent mapping.
* Transpose the mapping, so I get a list of digits and a list of characters.
* If there are no duplicates in either, we have an injective mapping and print the base.
> 1 votes

---
Tags: code-golf
---


title: Horror Movie Search Party

text:
# Question
Title: Horror Movie Search Party
**Plot**: Jimmy is missing; we have to find him. We should split up.

**Plot twist**: Jimmy is already dead.

But, our cast doesn't know that, so they need to search the whole area anyway. There is an N columns x M rows (1\<=M,N\<=256) grid of cells, either marked as "S" for the starting point, "." for open space, or "#" for an obstacle. This is the **map**.

There are 0\<=p\<=26 **costars**, 0\<=q\<=26 **extras**, and 1 **star**. Everyone is initially in the cell marked S.

## The Rules

Each person has a sight radius shown below:

```
 ...
.....
..@..
.....
 ...

```

The star is denoted by "@", the costars by capital letters, starting with "A", and the extras by lowercase letters, starting with "a". Initially, the sight radius surrounding the starting point is already marked as searched. If this constitutes the entire open space of the map, the game ends. Each turn, **in the following order**:

1. Each person simultaneously makes a king move (either standing still, or moving to one of the 8 neighboring cells).
2. All of the cells in the sight radius around each person are counted as searched.
3. If a costar cannot see anyone else, she dies. If an extra cannot see either a costar, the star, or at least 2 other extras, he dies. **These happen simultaneously** -- that is, there can be no chain reaction of deaths on a single turn; the above conditions are checked, and everyone who is going to die dies at once.
4. If all of the open space on the map has been searched, the search is over.

## Notes

Multiple people can be on the same square at any point, and these people can see each other.

Obstacles never impede sight, only movement; people can see each other across the, er... lava?

The open spaces on the map are guaranteed to be connected by king moves.

The initial "S" is also considered to be open space, rather than an obstacle.

Any king move that lands on an open space is valid. For instance, the following move is legal:

```
....      ....
.@#. ---> ..#.
.#..      .#@.
....      ....

```

## Input

The input will be in the format

```
N M p q
[N cols x M rows grid with characters ".", "#", and "S"]

```

Sample inputs:

```
6 5 0 0
......
......
..S...
......
......

```

and

```
9 9 1 1
S.......#
.......##
......##.
..#####..
...##....
...##....
...#.....
....#..#.
.........

```

p and q are the numbers of costars and extras, respectively.

## Output

The output should be, for each turn, the moves that are made, with directions indicated by

```
789
456
123

```

The order of the moves does not matter, as they are all enacted simultaneously. Not listing a move for a person is fine, and is equivalent to moving him in direction 5. Moves should be listed in the following format:

```
@9 A2 a2 B7.

```

"." denotes the end of your moves for a turn.

After the map has been searched, the final line of output should be three integers, separated by spaces: the number of turns that it took you to finish searching the board, the number of living costars, and the number of living extras. For the first example input

```
6 5 0 0
......
......
..S...
......
......

```

the following is valid output:

```
@4.
@6.
@6.
@6.
4 0 0

```

A final note: the star cannot die and the open space on the map is guaranteed to be connected, so the search will always succeed eventually.

## Scoring

Your score is the **total number of turns** taken over a set of benchmark tests; you're welcome to submit your own test case along with your answer. The sum of the number of living costars over the benchmark set will be used as a tie-breaker, and in the event there is still a tie, the sum of the number of living extras will be used.

## Test Set and Controller

Currently, 5 maps are online at https://github.com/Tudwell/HorrorMovieSearchParty/. Anyone submitting an answer may also submit a test case, which I reserve the right to reject for any reason (if I reject your map for some reason, you may submit another). These will be added to the test set at my discretion.

A Python **(tested in 2.7.5)** controller is provided on github as **controller.py**. A second controller there, **controller\_disp.py**, is identical except that it shows graphical output during the search (requires Pygame library).

**Usage**:

```
python controller.py <map file> <your execution line>

```

I.e.:

```
python controller.py map1.txt python solver.py map1.txt

```

The controller has output (to your program's **stdin**) of the form

```
Turn 1
@:2,3 A:2,3 B:2,3.
##...##
#ooo..#
ooooo..
ooooo..
ooooo..
#ooo...
##.....
###....
----------------------------------------

```

This is the turn number (turn 1 is before you have moved), a '.'-terminated list of all the actors and their x,y coordinates (the upper left character is (0,0)), a representation of the entire board, and a line with 40 '-'s. It then waits for input (from your program's **stdout**) of the form

```
@9 A2 B7.

```

This is the output format specified above. The controller outputs a 'o' for open space that has been searched, '.' for open space that has not been searched, and '#' for obstacles. It includes only living people in its list of people and their coordinates, and tracks all rules of the game. The controller will exit if an illegal move is attempted. If the moves for a given turn finish the search, the output is not as above; instead it is of the form

```
Finished in 4 turns
4 1 0

```

"4 1 0" here denotes 4 total turns, 1 living costar, and 0 living extras. You do not need to use the controller; feel free to use it or modify it for your own entry. If you decide to use it and encounter problems, let me know.

Thanks to @githubphagocyte for helping me write the controller.

**Edit:** For a randomized entry, you can choose any run on a particular map as your score for that map. Note that due to the scoring requirements, you should always choose the fewest turns, then the fewest dead costars, then the fewest dead extras for each map.

# Answer
## Ruby, Safety First + BFS + Randomness, Score ≤ 1458

I'm not sure how you'll be scoring random submissions. If all answers have to be deterministic, let me know and I'll pick a seed or get rid of the randomness altogether.

Some features and shortcomings of this solution:

* No one ever dies. At the start I group all the actors such that everyone is safe. The characters in each of these groups move in unison. That's good for keeping everyone alive but not optimally efficient.
* Each of the groups searches for the nearest unexplored spot on the map via breadth-first search and takes the first move of that branch of the search. If there is tie between multiple optimal moves a random one is picked. This is to ensure that not all groups always head in the same direction.
* This program doesn't know about field-of-view. It actually tries to move to every unexplored cell. Taking this into account might considerably increase the performance, since then you could also quantify the quality of each move by how many cells it will uncover.
* The program doesn't keep track of information between turns (except the actor groups). That makes it quite slow on the larger test cases. `map5.txt` takes between 1 and 13 minutes to complete.

Some results

```
Map     Min turns    Max turns
map1        46           86
map2        49          104
map3       332          417
map4       485          693
map5       546          887

```

Now here is the code:

```
start = Time.now

map_file = ARGV.shift
w=h=p=q=0
File::open(map_file, 'r') do |file|
    w,h,p,q = file.gets.split.map(&:to_i)
end

costars = p > 0 ? (1..p).map {|i| (i+64).chr} : []
extras = q > 0 ? (1..q).map {|i| (i+96).chr} : []
groups = []

costars.zip(extras).each do |costar, extra|
    break unless extra
    groups << (costar + extra)
    costars.delete(costar)
    extras.delete(extra)
end

costars.each_slice(2) {|c1, c2| groups << (c1 + (c2 || '@'))} unless costars.empty?
extras.each_slice(3) {|c1, c2, c3| groups << (c1 + (c2 || '') + (c3 || '@'))} unless extras.empty?
groups << '@' unless groups.join['@']

#$stderr.puts groups.inspect

directions = {
    1 => [-1, 1],
    2 => [ 0, 1],
    3 => [ 1, 1],
    4 => [-1, 0],
    5 => [ 0, 0],
    6 => [ 1, 0],
    7 => [-1,-1],
    8 => [ 0,-1],
    9 => [ 1,-1]
}

loop do
    break unless gets # slurp turn number
    coords = {}
    input = gets
    input.chop.chop.split.each{|s| actor, c = s.split(':'); coords[actor] = c.split(',').map(&:to_i)}
    #$stderr.puts input
    #$stderr.puts coords.inspect
    map = []
    h.times { map << gets.chomp }

    gets # slurp separator
    moves = groups.map do |group|
        x, y = coords[group[0]]
        distances = {[x,y] => 0}
        first_moves = {[x,y] => nil}
        nearest_goal = Float::INFINITY
        best_move = []
        active = [[x,y]]
        while !active.empty?
            coord = active.shift
            dist = distances[coord]
            first_move = first_moves[coord]
            next if dist >= nearest_goal
            [1,2,3,4,6,7,8,9].each do |move|
                dx, dy = directions[move]
                x, y = coord
                x += dx
                y += dy
                next if x < 0 || x >= w || y < 0 || y >= h || map[y][x] == '#'
                new_coord = [x,y]
                if !distances[new_coord]
                    distances[new_coord] = dist + 1
                    first_moves[new_coord] = first_move || move
                    active << new_coord if map[y][x] == 'o'
                end

                if dist < distances[new_coord]
                    distances[new_coord] = dist + 1
                    first_moves[new_coord] = first_move || move
                end

                if map[y][x] == '.'
                    if dist + 1 < nearest_goal
                        nearest_goal = dist + 1
                        best_move = [first_moves[new_coord]]
                    elsif dist + 1 == nearest_goal
                        best_move << first_moves[new_coord]
                    end
                end
            end
        end

        #if group['@']
        #    distances.each{|k,v|x,y=k;map[y][x]=(v%36).to_s(36)}
        #    $stderr.puts map
        #end

        dir = best_move.sample
        group.chars.map {|actor| actor + dir.to_s}
    end * ' '
    #$stderr.puts moves
    puts moves
    $stdout.flush
end

#$stderr.puts(Time.now - start)

```

There are a few commented out debug outputs in there. Especially the `if group['@']` block is quite interesting because it prints out a visualisation of the BFS data.

**Edit:** Significant speed improvement, by stopping the BFS if a better move has already been found (which was kinda the point of using BFS in the first place).
> 8 votes

---
Tags: code-challenge, graph-theory, path-finding
---