# Question
Title: Find a mirror configuration to match laser destinations
**UPDATED SCORING**: *As this challenge is more difficult than I anticipated, I have adjusted the scoring. A program that can solve a single mirror input is a valid answer. More sophisticated programs get a bonus to their score.*

There have been several puzzles on PPCG to find a laser path in a box of mirrors. In this puzzle, you need to *create* a box of mirrors to match a number of laser destinations.

You are given a box and a specifications where lasers are to enter and exit. Your program needs to place exactly N double-sided mirrors in the box to meet the specification. The mirrors must be angled at 45 degrees but can be forward sloping or back sloping.

### Input

Your program should accept a box grid via STDIN, command line argument, or file in the following format examples:

```
+--G--+     +abcde+
G     |     f/////d
|    /|     a//   c
+-----+     f     |
            +-b-e-+

```

The letter pairs (\[a-zA-Z\] may be used) indicate the input/output of up to 52 lasers. Inside the box will be N `/` mirrors. The box dimensions will be 3 \<= W,H \<= 200. The box is made of `+|-` characters. There may be any number of mirrors in the box including zero.

### Output

The output should match the input, except the `/` characters may be moved and/or changed into `\` characters. Your program should send a correct mirror box string to STDOUT or a file, trailing new line optional. If no placement of mirrors can meet the input specification, output `Impossible\n`. Examples of possible solutions:

```
+--G--+     +abcde+
G  /  |     f \ \ d
|     |     a/ \  c
+-----+     f / //|
            +-b-e-+

```

### Testing example

Input:

```
+abcdefghijklmnopqrstuvwxyA-+
|///////////////            |
|///////////////            |
|                           |
+-Abcdefghijklmnopqrstuvwxya+

```

Example output:

```
+abcdefghijklmnopqrstuvwxyA-+
|\                         \|
|/                        / |
|\\\\\\\\\\\\\\\\\\\\\\\\\\ |
+-Abcdefghijklmnopqrstuvwxya+

```

### Scoring (UPDATED)

This is code-golf with bonuses. You should nominate with your answer how many mirrors your program can solve (N). Your score is the length of your program in bytes divided by N. This allows people to enter with a simple program, but rewards more ambition programmers with a bonus.

Standard loopholes disallowed.

# Answer
> 2 votes
# C# - ~~897~~ 862 bytes

*Found a serious bug with it putting mirrors in places that they can't be. Now it works, hopefully! Also did some light golfing, couldn't leave the while loop in there... shameful.*

Complete program, takes input from STDIN, outputs to STDOUT.

This was a lot of fun, it copes fine with the 7 by 5 problem (and when you remove one of the mirrors, making it impossible), took about 1 hour to solve the 30 by 5.

```
using Q=System.Console;class P{static int w,L;static string S(char[]M,int t,int r,int i,int d,int[]B){var s="";if(r<0)return s;M=(char[])M.Clone();B=(int[])B.Clone();B[i]=1;for(i+=d;M[t]<48|t==i;i=t+(d=t<w?w:t>L-w?-w:t%w<1?1:-1))if(++t>=L){for(i=0;++i<L&r>0;)if(B[i]<1&M[i]<33){M[i]='.';r--;}return r<1?new string(M):s;}int c=M[i];if(c>32)s=c>47|c<46?s=c==M[t]?S(M,t,r,t,0,B):s:S(M,t,r,i,c<47?w/d:-w/d,B);else if((s=S(M,t,r,i,d,B))==""&B[i]<1){M[i]='.';s=S(M,t,r-1,i,w/d,B);if(s==""){M[i]='/';s=S(M,t,r-1,i,-w/d,B);}}return s;}static void Main(){string a,A="",R=A;for(;(a=Q.ReadLine())!=null;A+=a)L+=(w=a.Length);var G=A.ToCharArray();int r=0,i=L;for(;i>0;G[i]=G[i]=='|'?',':G[i])if(G[--i]==47|G[i]==92){r++;G[i]=' ';}a=S(G,0,r,1,w,new int[L]);if(a=="")R="Impossible\n";else for(;i<L;i+=w)R+=a.Substring(i,w)+"\n";Q.Write(R.Replace(".","\\").Replace(",","|"));}}

```

7 by 5 Example:

```
+abcde+
f/////d
a//   c
f     |
+-b-e-+

+abcde+
f   \ d
a/  //c
f/ \ /|
+-b-e-+

```

Impossible version:

```
+abcde+
f ////d
a//   c
f     |
+-b-e-+

Impossible

```

Something different (the program doesn't look at the original mirror layout):

```
+a----+
|//// |
|/////|
|/////|
+----a+

+a----+
| /\\\|
|\\\\\|
|\\/\\|
+----a+

```

30 by 5 solution:

```
+abcdefghijklmnopqrstuvwxyA-+
| \\\\\\\\\\\\\\\\\\\\\\\\ \|
| /                       //|
|\                         \|
+-Abcdefghijklmnopqrstuvwxya+

```

It looks at each laser source in turn, and builds a valid route for it (if it can), and then moves onto the next. It's a pretty simple depth-first search, which has to know which laser source (target) it's looking at, how many mirrors it remain for it to place, the current cell it's "at", the direction it's moving in, and each cell it's visited already (so that it doesn't put a mirror somewhere it's already been). The last 3 are used for assembling the path for the current target, and at reset when the target changes. Once it's got all the lasers linked up, it goes ahead and fills in any gaps it doesn't need left empty (another reason it needs to know everywhere it's visited).

When it's building routes, it favours going "forward" over inserting a mirror, and when it does, it favours a "\\" mirror - this is best seen in the "something different" example above, where it skips the first cell below the top-most 'a', then continually fills out a "\\" if it can find a solution with one, otherwise a "/" (naturally, if skipping the first cell resulted in it being unable to find a solution, then it would back-track and try putting a mirror there instead).

```
using Q=System.Console;

class P
{
    static int w,L;

    // M is cur grid
    // t is target edge thing (0->L)
    // r is mirrors remaining
    // i is pos
    // d is dir
    static string S(char[]M,int t,int r,int i,int d,int[]B)
    {
        var s="";

        if(r<0) // no mirrors left
            return s;

        // clone everything
        M=(char[])M.Clone();
        B=(int[])B.Clone();

        B[i]=1; // can't write to this

        for(i+=d; // move i
            M[t]<48|t==i; // only if target is something sensible (increment if i==t)
            i=t+(d=t<w?w:t>L-w?-w:t%w<1?1:-1)) // reflect, should be fine for w=3
            if(++t>=L) // run off the end
            {
                for(i=0;++i<L&r>0;) // don't need I any more (count through everything)
                    if(B[i]<1&M[i]<33) // not been here & it's open space
                    {
                        M[i]='.'; // doesn't matter
                        r--;
                    }
                return r<1?new string(M):s; // none remaining ? victory : defeat
            }

        int c=M[i];
        if(c>32) // not boring
            s=c>47|c<46? // hit edge
                s=c==M[t]? // hit the correct thing
                    S(M,t,r,t,0,B): // i+0=t, tells it to increment t
                    s
            :S(M,t,r,i,c<47?w/d:-w/d,B); // mirror
        else // boring
            if((s=S(M,t,r,i,d,B))==""&B[i]<1) // fwd
            {
                M[i]='.'; // use . instead of \
                s=S(M,t,r-1,i,w/d,B); // \
                if(s=="")
                {
                    M[i]='/';
                    s=S(M,t,r-1,i,-w/d,B); // /
                }
            }

        return s;
    }

    static void Main()
    {
        string a,A="",R=A; // R is free
        for(;(a=Q.ReadLine())!=null;A+=a) // read input
            L+=(w=a.Length); // note width, accumulate length

        var G=A.ToCharArray();

        int r=0,i=L; // count mirrors (I refuse to make these static)
        for(;i>0; // end on i=0
            G[i]=G[i]=='|'?',':G[i]) // replace | with ,
            if(G[--i]==47|G[i]==92) // remove and count mirrors
            {
                r++;
                G[i]=' '; // storing G[i] doesn't seem to save anything
            }

        // search
        a=S(G,0,r,1,w,new int[L]);

        if(a=="") // defeat
            R="Impossible\n";
        else // victory
            for(;i<L;i+=w) // for each line
                R+=a.Substring(i,w)+"\n";

        Q.Write(R.Replace(".","\\").Replace(",","|")); // swap back | and \
    }
}

```

# Answer
> 2 votes
## Python, 671 654 bytes

**Not a solution, but an attempt, read below.**

```
import random as R
def V(F):
 for S,_x,_y in (F[0],0,1),(F[-1],0,-1),([L[0] for L in F],1,0),([L[-1] for L in F],-1,0):
  for i,C in enumerate(S):
   if not C in '+-|':
    x=_x;y=_y
    if not x: X=i;Y=y
    elif not y: Y=i;X=x
    while F[Y][X] != C:
     if F[Y][X]=='\\':x,y=y,x
     if F[Y][X]=='/':a=x+y;x,y=x-a,y-a
     X+=x;Y+=y
     try:
      if F[Y][X] in '+-|':return False
     except:
      return False
 return True
F=open(input()).read().split('\n')
while 1:
 _=[F[0]]+['\n'.join([L[0]+''.join([R.choice(' \\/')for i in range(len(F[0])-2)])+L[-1] for L in F[1:-1]])]+[F[-1]]
 if V(_):
  for l in _: print l
  break

```

I did not golf this to the max, since I'm not satisfied with the solution. `V` validates a given solution by walking the field `F` for each character `C` it finds on the sideline. Solutions are generated at random. It's ugly, it works for entry1, but takes a Lot of time for the other entries. Since it randomly tries solutions, I don't consider this to be an actual solution for the given problem; but it might help others.

Run: `echo "entry1.txt" | python script.py`

---
Tags: code-golf, grid
---


# Question
Title: Is the word typeable with keys adjacent to each other?
Before reading this I suggest reading this little puzzle: https://puzzling.stackexchange.com/questions/11408/longest-word-with-adjacent-letters-on-a-keyboard

I want you to make a program that takes one argument, a word (only lowercase letters), and outputs "Yes" if the word can be typed with adjacent keys on the keyboard (see the article) and "No" if the word can't be typed with adjacent letters.

Here's the keyboard layout used in this challenge:

```
 ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
 | Q | W | E | R | T | Y | U | I | O | P |
 └─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┘
   | A | S | D | F | G | H | J | K | L |
   └─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴───┘
     | Z | X | C | V | B | N | M |
     └───┴───┴───┴───┴───┴───┴───┘

```

Remember: this is codegolf so the the shortest answer wins!

# Answer
> 9 votes
# Pyth, 66

```
?"Yes".Am>2sm^-.uk2Cm.Dx"qwertyuiopasdfghjkl*zxcvbnm"b9.5dC,ztz"No

```

Try it here.

I was surprised to learn Pyth doesn't have a hypotenuse function, so this will likely be beat by a different language. I'll propose a hypotenuse function to Pyth, so this atrocity won't happen in the future.

### Explanation

I transform the keyboard into this:

```
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
| Q | W | E | R | T | Y | U | I | O | P |
└─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┐
  | A | S | D | F | G | H | J | K | L | * |
  └─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴───┴───┘
    | Z | X | C | V | B | N | M |
    └───┴───┴───┴───┴───┴───┴───┘

```

Which I then encode as `"qwertyuiopasdfghjkl*zxcvbnm"`. **Then I used divmod with modulo 9.5 to figure out the 2D coordinates of every key.** Then I compute distances between consecutive keys, and check if the squared distance \< 2.

# Answer
> 3 votes
# CJam, ~~83~~ ~~75~~ 74 bytes

```
l_1>]z["qwertyuiop asdfghjkl  zxcvbnm "[__B>]z+s_W%+_]zsf{\#)}:*"Yes""No"?

```

Try it online.

### Explanation

The general approach is to produce a big adjacency string containing every pair of adjacent keyboard characters and then check that every pair of adjacent input characters is contained in that string.

I'm quite happy with how I managed to build the adjacency string, which uses very simple and compact logic.

```
l_1>]z          "Read a line of input and create a list of every pair of
                 adjacent input characters. There will be a trailing element
                 of just the final character, but that's okay since any single
                 lowercase letter can be found in the adjacency string.";
["qwertyuiop asdfghjkl  zxcvbnm "
              "^ Create the in-row forward adjacency string.";
[__B>]z         "Create the alternating-row forward adjacency string by
                 interleaving the in-row string with a substring of itself
                 starting with the middle row letters:
                   'q w e r t y u i o p   a s d f g h j k l  zxcvbnm '
                 + ' a s d f g h j k l     z x c v b n m  '[no interleave here]
                 -----------------------------------------------------
                   'qawsedrftgyhujikolp   azsxdcfvgbhnjmk l  zxcvbnm '";
+s              "Append the alternating-row forward adjacency string to the
                 in-row forward adjacency string.";
_W%+            "Append the reverse of the forward adjacency string (the
                 backward adjacency string) to the forward adjacency string.";
_]zs            "Double every character in the adjacency string so every
                 character is adjacent to itself.";
f{\#)}          "Map each pair of input characters to its 1-indexed location in
                 the adjacency string (0 if not found).";
:*              "Calculate the product of each pair's location in the adjacency
                 string. This will be nonzero if and only if every pair of
                 input characters are in fact adjacent.";
"Yes""No"?      "If the product is nonzero, produce 'Yes'; otherwise, produce
                 'No'.";
                "Implicitly print the result.";

```

# Answer
> 2 votes
# J, 77 bytes

```
No`Yes{::~[:*/2>+/"1@(2|@-/\3(|,.<.@%~+-:@|)'qazwsxedcrfvtgbyhnujmikXolX'i.])

```

Usage:

```
   f=.No`Yes{::~[:*/2>+/"1@(2|@-/\3(|,.<.@%~+-:@|)'qazwsxedcrfvtgbyhnujmikXolX'i.])

   f 'redresser'
Yes
   f 'qwergy'
No
   f 'ppcg'
No

```

Method:

For every input letter I generate it's 2D coordinate (similar to the image in the question) based on it's index in the string `'qazwsxedcrfvtgbyhnujmikXolX'`. For every pair of letters in the input I check if their coordinates' Manhattan-distance is smaller than 2. If all are, I output `Yes`, `No` otherwise (by abusing the \` operator).

Try it online here.

# Answer
> 1 votes
# CJam, 75

```
r(1$+]z[1AB]"qwertyuiop asdfghjkl  zxcvbnm"f/:zSff+s_W%+f{\_|#}W&"No""Yes"?

```

Try it here (Firefox here).

Overlooked the Yes/No part... Fixed.

---
Tags: code-golf, puzzle-solver, keyboard
---


# Question
Title: Detect the main order based on sub-lists
The question is simple but the answer maybe not!

suppose that you have the following lists that all of them are ordered (not consecutive):

```
x = ['one', 'two', 'four']
y = ['two', 'three', 'five']
z = ['one', 'three', 'four']

```

as you can see there is a logic in each of the above lists for example in `x` we have the following order that is true `'one'<'two'<'four'` and also for other sub lists.

So the main list contain all the unique elements from preceding lists that contain `['one','two','four','three','five']` and the task is to find the main ordered list :

```
['one', 'two', 'three', 'four', 'five']

```

im not looking for a comprehensive or general answer! because it has not a general answer and it all depend on the number of sub-lists!

So whats your idea for this problem or problems like this?

# Answer
In general, you might want to use a topological sorting algorithm. This procedure runs in O(*n*) where *n* is the sum of the number of elements in each list. Create a directed graph where each node is one of the distinct elements in the input lists. For each pair of elements adjacent in one of the element lists, add an edge between these two elements in the graph from the lesser element to the greater. Finally, topologically sort that graph.
> 1 votes

# Answer
# Python (182)

I think this might be a bit too long. I might try my hand at a J version of the same algorithm.

```
from itertools import*
def f(i):
 o=[]
 while len(i)>1:i=[a for a in i if a];o+=[a[0]for a,b in combinations(i,2)if a[0]==b[0]];[j.pop(0)for j in i if j[0]==o[-1]]
 o+=i[0]
 return o

```

## Example:

**Input:**

```
i = [['one', 'two', 'four'],
     ['two', 'three', 'five'],
     ['one', 'three', 'four']]
print f(i)

```

**Output:**

```
['one', 'two', 'three', 'four', 'five']

```
> 0 votes

# Answer
# Mathematica, 115 bytes

Could probably use some `Thread`s here...

```
Sort[Union@##,Function[{a, b},Less@@Function[c,Mean[Flatten@DeleteCases[FirstPosition@c/@{##},_Missing]]]/@{a,b}]]&

```

Written as a pure function, used via `*code*[<first list>, <second list>, ...]`. I don't see how this is dependent on the number of lists. If there is any ambiguity about the order, it chooses a pseudorandom working case.
> 0 votes

---
Tags: code-golf, sorting
---


title: Overlapping circle

text:
# Question
Title: Overlapping circle
You should write a program or function that given an `N` by `N` equally spaced square grid and a solid inscribed circle outputs or returns the number of grid squares which are overlapped partially or fully by the solid circle.

0-sized overlaps (i.e. when the circle only touches a line) are not counted. (These overlaps occur at e.g. `N = 10`.)

## Example

`N = 8 (64 squares), Slices = 60`

## Input

* An integer `N > 0`. (The grid wil have `N * N` squares.)

## Output

* An integer, the number of solid circle slices.

## Examples

(input-output pairs)

```
Inputs:  1 2 3  4  5  6  7  8  9 10  11  12  13  14  15
Outputs: 1 4 9 16 25 36 45 60 77 88 109 132 149 172 201

```

This is code-golf so shortest entry wins.

# Answer
> 5 votes
# Pyth, ~~27~~ 26

```
-*QQ*4lfgsm^d2T*QQ^%2_UtQ2

```

Try it online: Pyth Compiler/Executor

I use a `2Nx2N` grid and count overlapping `2x2` squares. That is a little bit shorter, since I already know the radius `N`.

And actually I don't count the overlapping squares. I count the non-overlapping squares of the second quadrant, multiply the number by 4 and subtract the result from `N*N`.

### Explanation for the 27 solution:

```
-*QQ*4lfgsm^-Qd2T*QQ^t%2UQ2   implicit: Q = input()
                     t%2UQ    generates the list [2, 4, 6, ..., Q]
                    ^     2   Cartesian product: [(2, 2), (2, 4), ..., (Q, Q)]
                              These are the coordinates of the right-down corners
                              of the 2x2 squares in the 2nd quadrant.
       f                      Filter the coordinates T, for which:
        gsm^-Qd2T*QQ             dist-to-center >= Q
                                 more detailed:
          m     T                   map each coordinate d of T to:
           ^-Qd2                       (Q - d)^2
         s                          add these values
        g        *QQ                 ... >= Q*Q
    *4l                       take the length and multiply by 4
-*QQ                          Q*Q - ...

```

### Explanation for the 26 solution:

I noticed that I use the coordinates only once and immediately subtract the coordinates from `Q`. Why not simply generate the values `Q - coords` directly?

This happens in `%2_UtQ`. Only one char larger than in the previous solution and saves 2 chars, because I don't have to substract `-Q`.

# Answer
> 7 votes
# Python 2, 72

```
lambda n:sum(n>abs(z%-~n*2-n+(z/-~n*2-n)*1j)for z in range(~n*~n))+n+n-1

```

Ungolfed:

```
def f(n):
    s=0
    for x in range(n+1):
        for y in range(n+1):
            s+=(x-n/2)**2+(y-n/2)**2<(n/2)**2
    return s+n+n-1

```

The grid points for an `(n+1)*(n+1)` square. A cell overlaps the circle if its grid point nearest the center is inside the circle. So, we can count grid points, except this misses `2*n+1` grid points at axes (both for even and odd `n`), so we correct for that manually.

The code saves characters by using complex distances to calculate the distance to the center and a loop collapse to iterate over a single index.

# Answer
> 7 votes
# CJam, ~~36 35 34~~ 27 bytes

This turned out to be the same algorithm as xnor's, but I wonder if there is any better one.

```
rd:R,_m*{{2*R(-_g-}/mhR<},,

```

**Code explanation**:

```
rd:R                                "Read the input as double and store it in R";
    ,_                              "Get 0 to input - 1 array and take its copy";
      m*                            "Get Cartesian products";
                                    "Now we have coordinates of top left point of each";
                                    "of the square in the N by N grid";
        {               },,         "Filter the squares which are overlapped by the";
                                    "circle and count the number";
         {        }/                "Iterate over the x and y coordinate of the top left";
                                    "point of the square and unwrap them";
          2*                        "Scale the points to reflect a 2N grid square";
            R(-                     "Reduce radius - 1 to get center of the square";
               _g-                  "Here we are reducing or increasing the coordinate";
                                    "by 1 in order to get the coordinates of the vertex";
                                    "of the square closer to the center of the grid";
                    mhR<            "Get the distance of the point from center and check";
                                    "if its less than the radius of the circle";

```

*UPDATE* : Using the 2N trick from Jakube along with some other techniques to save 7 bytes!

Try it online here

# Answer
> 2 votes
# Pyth,  ~~44~~  36

```
JcQ2L^-+b<bJJ2sm+>*JJ+y/dQy%dQqQ1*QQ

```

Trying to clean it a bit in case I could shave some bytes.

### Explanation

```
                           Q = eval(input())    (implicit)
JcQ2                       calculate half of Q and store in J
L                          define function y(b) that returns
 ^-+b<bJJ2                 (b - J + (1 if b < J else 0)) ^ 2
s                          output sum of
 m                 *QQ      map d over integers 0..(Q*Q-1)
  +
   >*JJ                      J*J is greater than
       +y/dQy%dQ              sum of y(d / Q) and y(d % Q)
                qQ1          or Q is 1; see below

```

I have to explicitly check for `n = 1`, since my algorithm only checks the corner of the square nearest to the center (and none are covered in `n = 1`).

# Answer
> 2 votes
# Octave ~~(74) (66)~~ (64)

Here the octave version. Basically finding all the vertices within the circle and then finding all the squares with one or more valid vertices via convolution. 64 Bytes:

```
x=ndgrid(-1:2/input(''):1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

```

66 Bytes:

```
x=meshgrid(-1:2/input(''):1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

```

74 Bytes:

```
n=input('');x=ones(n+1,1)*(-1:2/n:1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

```

# Answer
> 1 votes
## R - 64

```
function(n)sum(rowSums(expand.grid(i<-0:n-n/2,i)^2)<n^2/4)+2*n-1

```

---
Tags: code-golf, geometry, counting
---


# Question
Title: Implement multiplication by a constant with addition and bit shifts
While looking at the ARM instruction set, you notice that the `ADD` instruction has the so-called "Flexible second operand", which can be abused for quick multiplication. For example, the following instruction multiplies register `r1` by 17 (shifting it left by 4 bits and adding to itself):

```
ADD r1, r1, r1, LSL #4
; LSL means "logical shift left"

```

The subtraction instruction has that feature too. So multiplication by 15 is also easy to implement:

```
RSB r1, r1, r1, LSL #4
; RSB means "reverse subtract", i.e. subtract r1 from (r1 << 4)

```

So this is an excellent optimization opportunity! Certainly, when you write in a C program `x *= 15`, the compiler will translate that to some inefficient code, while you could replace it by `x = (x << 4) - x`, and *then* the compiler will generate better code!

Quickly, you come up with the following cunning plan:

1. Write a program or a subroutine, in any language, that receives one parameter `m`, and outputs a C optimizing macro, like the following (for `m = 15`):

```
#define XYZZY15(x) (((x) << 4) - (x))

```

or (which is the same)

```
#define XYZZY15(x) (-(x) + ((x) << 4))

```
2. ???
3. Profit!

Notes:

* The macro's name is essential: magic requires it.
* Parentheses around `x` and the whole expression are required: ancient C arcana cannot be taken lightly.
* You can assume `m` is between 2 and 65535.
* The input and output can be passed through function parameters, `stdin/stdout` or in any other customary way.
* In C, addition and subtraction have tighter precedence than bit shift `<<`; use parentheses to clarify order of calculations. More parentheses than necessary is OK.
* It is absolutely vital that the C expression be optimal, so e.g. `x+x+x` is not acceptable, because `(x<<1)+x` is better.
* Expressions `x + x` and `x << 1` are equivalent, because both require one ARM instruction to calculate. Also, `(x << 1) + (x << 2)` (multiplication by 6) requires two instructions, and cannot be improved.
* You are amazed to discover that the compiler detects that `(x << 0)` is the same as `x`, so `x + (x << 0)` is an acceptable expression. However, there is no chance the compiler does any other optimizations on your expression.
* Even though multiplication by 17 can be implemented in one instruction, multiplication by 17\*17 cannot be implemented in two instructions, because there is no C expression to reflect that:

```
#define XYZZY289(x) x + (x << 4) + (x + (x << 4) << 4) // 3 operations; optimal

```

In other words, the compiler doesn't do common sub-expression elimination. Maybe you will fix that bug in version 2...

This is code-golf: the shortest code wins (but it must be correct, i.e. produce correct and optimal expressions for all `m`)

Please also give example outputs for `m = 2, 10, 100, 14043 and 65535` (there is no requirement on the length of the expression - it can contain extra parentheses, whitespace and shift left by 0 bits, if that makes your code simpler).

# Answer
> 2 votes
# Python - ~~414~~ ~~393~~ 331

This is my entry, which finds the least possible addition/subtraction operations, and subsequently evaluates to a C expression. Not sure it is optimal as multiplication of subexpressions may offer less operations.

```
import itertools as l
def w(N,s=''):
 for k,v in enumerate(min([t for t in l.product((1,0,-1),repeat=len(bin(N))-1)if sum([v*2**k for k,v in enumerate(t)])==N],key=lambda t:sum(abs(k)for k in t))):
  if v!=0:s+='{:+d}'.format(v)[0];s+='((x)<<{})'.format(k)if k>0 else'(x)'
 return '#define XYZZY{}(x) ({})'.format(N,s.lstrip('+'))

```

For the cases 2, 10, 100, 14043, 65535:

```
#define XYZZY2 (((x)<<1))
#define XYZZY10 (((x)<<1)+((x)<<3))
#define XYZZY100 (((x)<<2)+((x)<<5)+((x)<<6))
#define XYZZY14043 (-(x)-((x)<<2)-((x)<<5)-((x)<<8)-((x)<<11)+((x)<<14))
#define XYZZY65535(x) (-(x)+((x)<<16))

```

The final 65535 took around 11 minutes to compute. Suggestions for improvement (also speedwise) are welcome :-). Thanks to mbomb007 and plg for golfing improvements.

# Answer
> 0 votes
# Python 508

Slightly more characters than my other answer, but this code runs in roughly one second for all cases 2, 10, 100, 14043, 65535.

```
def l(n,k=0,o=0):
 while 1:
  if k==0:
   for j in range(1,n):
    yield(j,);yield(-j,)
   k+=1
  else:
   for j in range(1,n):
    for u in l(j,k-1,1):
     yield(j,)+u;yield(-j,)+u
   k+=1
  if o:break
r=lambda t:sum((1,-1)[k<0]*2**(abs(k)-1)for k in t)
def w(N,s=''):
 g = loop(len(bin(N)))
 while 1:
  a = g.next()
  if r(a)==N:
   for k in a:
    s+='{:+d}'.format(k)[0];s+='((x)<<{})'.format(abs(k-1)) if abs(k)>1 else'(x)'
   return '#define XYZZY{}(x) ({})'.format(N,s.lstrip('+'))""")

```

---
Tags: code-golf, arithmetic, c, optimization, code-generation
---


title: Decide existence of total orderings

text:
# Question
Title: Decide existence of total orderings
In this task, we consider arrays of positive integers such as this:

```
3 18 321 17 4 4 51 1 293 17

```

The input comprises a pair of such arrays both of arbitrary, possibly distinct, positive length. Determine if a total ordering ≤X**N** × **N**, where **N** is the set of positive integers, exists such that both input arrays are in order with respect to ≤X. Notice that (A ≤X B ∧ B ≤X A) ↔ A = B must hold, that is, two numbers are considered equal under ≤X if and only if they are the same number.

For example, if the input was the pair of arrays

```
7 2 1 1 4 12 3
9 8 7 2 5 1

```

then you are supposed to figure out if a total ordering ≤X exists such that

> 7 ≤X 2 ≤X 1 ≤X 1 ≤X 4 ≤X 12 ≤X 3

and

> 9 ≤X 8 ≤X 7 ≤X 2 ≤X 5 ≤X 1.

Your submission may be a subroutine or program that receives two arrays (as specified above) of input in an implementation-defined way, computes whether a total ordering ≤X satisfying the demands mentioned above exists and returns one value representing “yes” or a different value representing “no.” The choice of these values is arbitrary, please document them.

You may assume that the input arrays contain no more than 215 \- 1 elements each and that each of their elements is in the range from 1 to 215 \- 1 inclusive. You may require each arrays to be terminated by a constant sentinel outside of the aforementioned range such as 0. Please specify what sentinel is needed. You may require the lengths of the arrays as additional input if the length cannot be inferred from the arrays themselves (e. g. in languages like C). In addition to the prohibition of standard loopholes, you are not allowed to use topological sorting routines.

This challenge is code golf. The submission with the least amount of characters wins.

# Answer
> 4 votes
# Pyth, 28 22

```
L.AmqdSdmfhTmxhkbek^b2

```

Creates a function `y` that you can call with a tuple containing the two arrays. Returns "True" if a total ordering exists, "False" if not.

A helper program that defines and calls the above function with stdin:

```
L.AmqdSdmfhTmxhkbek^b2y,rw7rw7

```

Try it here.

We first read both arrays. Then we will create all combinations of both arrays. Then for each combination we will assume the first array is authoritative, and check if it's consistent with the second array.

# Answer
> 2 votes
# J, ~~36~~ ~~30~~ 26 bytes

```
[:*/@,(e.~(-:/:~)@#i.)&>/~

```

Let's call the two input lists `a` and `b`. The function checks (with `(e.~(-:/:~)@#i.)`) whether

* `a`'s elements sorted (in regard to `a`) in `b`
* `a`'s elements sorted (in regard to `a`) in `a`
* `b`'s elements sorted (in regard to `b`) in `a`
* `b`'s elements sorted (in regard to `b`) in `b`

Input is a list of two integer vectors.

Result is `1` if an ordering exists `0` otherwise. (Runtime is O(n\*n).)

Usage:

```
   f=.[:*/@,(e.~(-:/:~)@#i.)&>/~

   a=.7 2 1 1 4 12 3 [b=.7 2 1 1 4 12 3 1 [c=.9 8 7 2 5 1
   f a;c
1
   f b;c
0

```

Try it online here.

# Answer
> 2 votes
# GolfScript, 25 bytes

```
:A{:a;A{.a--.{a?}$=!},},!

```

Try this code online.

Takes an array of two (or more!) arrays on the stack; returns 1 (true) if every pair of input arrays has a compatible total order, or 0 (false) otherwise.

It works by looping over every possible pair of input arrays (including each array paired with itself), sorting the elements in the first array according to the position where they first occur in the second one (ignoring those that are not found), and checking that the resulting order matches the original.

While this code can take an arbitrary number of input arrays, it's worth noting that it only checks for *pairwise* consistency. For example, it returns true for the input `[[1 2] [2 3] [3 1]]`, since any two of the three arrays do have a consistent total order. That's enough for the two-input case, though, which is all that the challenge requires.

Here's a de-golfed version with comments:

```
:A         # save input to "A", and leave it on the stack to be looped over
{          # run this outer loop for each input array:
  :a;      #   save this array to "a" (and pop it off the stack)
  A{       #   also run this inner loop for each input array:
    .a--   #     remove all elements not in "a" from this array
    .      #     make a copy of the filtered array
    {a?}$  #     sort it by the first location of each element in "a"
    =!     #     check whether the sorted copy differs from the original
  },       #   select those arrays for which there was a difference
},         # select those arrays for which at least one difference was found
!          # return 1 if no differences were found, 0 otherwise

```

Ps. It would be possible to trivially save one or two bytes by requiring the input to be given directly in the named variable `A`, and/or by changing the output format to an empty array for "yes" and a non-empty array for "no". However, that would seem rather cheesy to me.

# Answer
> 1 votes
# Ruby, 79

```
!!gets(p).scan(r=/\d+/){|s|$'[/.*/].scan(r){s!=$&&~/\b#$& .*\b#{s}\b/&&return}}

```

Expects input to be a two-line file of space-separated numbers. Returns `true` when an ordering exists, `nil` if it doesn't.

# Answer
> 1 votes
# Haskell, 98 bytes

```
import Data.List
a%b=intersect(r a)$r b
r l=map head$group l
c l=nub l==r l
x#y=c x&&c y&&x%y==y%x

```

Returns `True` or `False`. Example usage: `[7,2,1,1,4,12,3] # [9,8,7,2,5,1]` -\> `True`.

How it works: remove consecutive duplicates from the input lists (e.g: `[1,2,2,3,2] -> [1,2,3,2]`. An order exists if both resulting lists do not contain duplicates and the intersection of list1 and list2 equals the intersection of list2 and list1.

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


title: How to recover from DDOS'ed internet

text:
# Question
Title: How to recover from DDOS'ed internet
The internet has failed. DDoS attacks are now rampant and widespread. It is up to you to take control and repair the internet.

Each bot will control 20 nodes in this network. Every node is either *active* or *safe*, has an owner, and has a strength, which starts at 2. Every active node is connected to all other active nodes.

Each turn, you will receive a list of all active nodes with their strength. For each of the active nodes that you own, you either:

1. Designate an *active* node you want to transfer your *entire* strength to, or
2. Save and increase its strength

Then the following happens *in order*:

1. A Node choosing to save its strength will increase its strength by 1.
2. All nodes choosing to transfer their strength will simultaneously transfer their entire strength to the new node.
3. If a node was transferred strength from an enemy node, an attack will ensue. If an enemy *owner* collectively transfers more strength than the original owner (and all other attackers), then that enemy becomes the new owner. The strength of that node then becomes the strength of the attacker. If there is a tie for strength, then the owner will be chosen randomly.
4. All nodes left without any strength will be considered *safe*, and gives 1 point to the owner.

After 100 games of 100 turns, the owner with the most safe nodes across all games wins. **EDIT: I changed it from 2000 to 100 turns, as it ended up that the last 1900 turns were useless**

# IO

You will be passed the list of active nodes (via command line args) like the following:

```
F20 F4 E7 E2 E20 F2

```

`F` designates that the node is a friendly node, and `E` designates that the node is an enemy.

For each of your friendly nodes, you should return an action (via STDOUT) like the following:

```
0,0 1,3 5,0

```

The above would mean that you want to increase your strength of the first node, use your second node to attack the fourth node, and your last node will transfer its strength the first node (and if nobody attacks it, it will become a safe node).

After returning, your program should quit.

# Scoreboard

> accumulator got 3240 points
>
> classy got 2370 points
>
> dumbot got 2262 points
>
> random\_bot got 1603 points
>
> smarter\_random\_bot got 1319 points
>
> steady\_bot got 1097 points

The controller can be found here: https://github.com/nathanmerrill/NetAttack

# Answer
# Accumulator, Python

Let's get this party started! My submission should work both on Python 2 and Python 3.

```
import sys

inputs = [(i, x[0], int(x[1:])) for (i, x) in enumerate(sys.argv[1].split())]

own_nodes = sorted([(s,i) for (i,o,s) in inputs if o == 'F'])
targets = sorted([(s,i) for (i,o,s) in inputs if o == 'E'])

if targets:
    t_copy = targets[:]
    out = ""
    total_str = 0
    attackers = []
    for (s,i) in own_nodes:
        attackers += [i]
        if t_copy:
            total_str += s
            if t_copy[0][0] < total_str - 1:
                j = max([j for j in range(len(t_copy)) if t_copy[j][0] < total_str - 1])
                out += " ".join([str(k) + "," + str(t_copy[j][1]) for k in attackers]) + " "
                attackers = []
                total_str = 0
                t_copy = t_copy[:j] + t_copy[j+1:]
    if attackers:
        if t_copy:
            out += " ".join([str(k) + "," + str(t_copy[0][1]) for k in attackers])
        else:
            out += " ".join([str(k) + "," + str(attackers[0]) for k in attackers])
else:
    out = " ".join([str(i) + "," + str(own_nodes[0][1]) for (s,i) in own_nodes])

print(out.rstrip())
sys.stdout.flush()

```

The idea is really simple. I start enumerating my nodes in ascending order of strength, keeping a running sum of the strengths. When the sum exceeds the strength of the weakest enemy node (+1 for a possible increase), I attack that node and remove it from the pool, reset the sum, and continue. At the end, if the strongest nodes can't find anyone to attack, they'll collect more strength.

*EDIT:* Accumulator is now a bit smarter. Instead of always attacking the weakest enemy node, it accumulates the strength until it could do so, and then attacks the strongest free node it can with that strength. Also, if there are still enemies left at the end, any unassigned nodes will attack the weakest remaining enemy, just in case it decides to transfer its strength away.
> 5 votes

# Answer
# Classy, Python3

```
import random, sys
f,e,p=[],[],[]
for si,s in enumerate(sys.argv[1].split()):
    if s[0]=='F': f+=[(int(s[1:]),si)]
    else: e+=[(int(s[1:]),si)]
f=sorted(f,key=lambda t:t[0]);r=4
f1,f2,f3=f[:len(f)//r],f[len(f)//r:len(f)//r*2],f[len(f)//r*2:]
for fa in f3:
    ea=[t for t in e if t[0]<fa[0]]
    p+=[(fa[1],random.choice(ea)[1])] if ea else [(fa[1],fa[1])]
for fd,fs in zip(f1,reversed(f2)):
    p+=[(fs[1],fd[1])]
    p+=[(fd[1],fd[1])]
if len(e)==0: p=[(fe[1],0) for fe in f]
for t in p: print(t[0],',',t[1],' ',sep='',end='')
sys.stdout.flush()

```

The bot splits its own nodes into 3 categories based on strength and each node acts according to its category.

* Each strong node attacks a random enemy node which it can beat.
* Each middle node supports it's weak node pair.
* Each weak node supports itself.

Result against Accumulator and the two sample bots:

```
smarter_random_bot got 1301 points
random_bot got 1841 points
Accumulator got 2178 points
Classy got 2580 points

```
> 4 votes

# Answer
# Dumbot, Nodejs

```
var input = process.argv.splice(2);
var regexp = new RegExp(" ", "gm");
input = String(input).split(regexp);
var nodes = [];
var targets = [];
for(var i = 0; i < input.length; i++){
    if(input[i].charAt(0) == "F")
        nodes.push(i);
    else
        targets.push(i);
}
var result = "";
var length = nodes.length;
for(var i = 0; i < length; i++){
    if(targets.length>0)
        result += nodes.shift() + "," + targets.shift() + " ";
    else
        result += nodes.shift() + ",0 ";
}
console.log(result);

```

The bot will attack without any thinking or strategy. The main goal is to ensure a lot of safe node right at the beginning. Be aware that this bot make an infinite loop with accumulator.
> 2 votes

# Answer
# SteadyBot, Node.js

```
(new Promise(function(resolve, reject) {
    var input = process.argv[2];
    if(input) {
        resolve(input);
    } else {
        process.stdin.once('data', function(data){
            resolve(data.toString());
        });
    }
})).then(function(input) {
    return input.trim().split(' ');
}).then(function(nodes) {
    var friends = [], enemies = [];
    nodes.forEach(function(value, index) {
        var data = { index: index, strength: parseInt(value.substring(1)) };
        if(value[0] === 'F') {
            friends.push(data);
        } else {
            enemies.push(data);
        }
    });

    function weaknessCompare(a, b) {
        return (a.strength > b.strength) ? -1 : ((a.strength < b.strength) ? 1 : 0);
    }

    friends.sort(weaknessCompare);
    enemies.sort(weaknessCompare);

    if(enemies.length === 0) {
        friends.forEach(function(friend) {
            friend.target = 0;
        });
    } else {
        if(friends.length > 0) {
            var strongest = friends[0];
            for(var i = 0; i < enemies.length; i++) {
                var enemy = enemies[i];
                if(enemy.strength + 1 < strongest.strength) {
                    strongest.target = enemy.index;
                    break;
                }
            };
        }
        if(friends.length > 1) {
            friends[1].target = friends[friends.length - 1].index;
        }
    }

    console.log(friends.map(function(friend) {
        return friend.index + ',' +
                (typeof friend.target === 'number' ? friend.target : friend.index);
    }).join(' '));
});

```
* Assumes enemies won't reinforce large nodes: Largest friendly node attacks strongest enemy it can beat under this assumption.
* Assumes that weakest target will be attacked: Second largest friendly node moves to weakest friendly node each round.
* Wants lots of free strength: Other nodes wait.
> 2 votes

---
Tags: king-of-the-hill
---


title: Programs to build a rat maze

text:
# Question
Title: Programs to build a rat maze
You have been hired as a research assistant, and asked to create a small program that will build rat mazes. The rat box is always 62x22 and has an entrance (a) and exit (A) for the rat, like this (input 1):

```
#######a######################################################
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#################################################A############

```

Your program must fill the box with blocks (#) leaving a path for the rat, like this (output 1):

```
#######a######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
#######                                           ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
#################################################A############

```

This is easy you think! You start writing a small program, full of confidence. However, the Principle Scientist has had a new idea -- he wants two rats to navigate the maze at the same time. Dr Rattanshnorter explains that they have different doors and different exits (input 2):

```
#b#####a######################################################
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            B
#                                                            #
#################################################A############

```

The rats have been trained to move straight through cross intersections but T-intersections leave them hopelessly confused and will invalidate the experiment. You start on your new more complex task when the good Doctor explains one final requirement: the rats are savage to each other so if they see each other at any point, a rat fight will break out and you will both be before the ethics board. You now realise your program should output a maze something like this (output 2):

```
#b#####a######################################################
# ##### ######################################################
# ##### ######################################################
# ##### #######################################           ####
# ##### ####################################### ######### ####
# #####                                           ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
#                                               # ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# #######    B
################################################# ############
#################################################A############

```

By the time rat B reaches the intersection, rat A will be travelling down the corridor to exit A and the rat fight will be avoided.

### Rules:

* Your program should read in (STDIN or file) an input like those above, and output (STDOUT or file) the same data except many spaces will now be hashes (#). You may substitute any single character (such as `;`) instead of `\n` in the input string but the output string still requires `\n` characters. **UPDATED**
* A rat pathway must be one character width wide, except for cross intersections (every space must have zero or two orthogonally adjacent `#` characters). Each rat must have a clear single path, except for cross intersections. No T-intersections are allowed.
* Rats are released simultaneously and move at a constant rate. At no time should two or more rats see each other (be in the same column or row without one of more `#` characters in between).
* If no solution is possible (such as adjacent entrance points), print `Impossible\n` and exit.
* Entrances and exits can be on any sides, however they will never be on the corners.
* If a matched entrance and exit are adjacent (eg: `##aA##`), the rat cannot go directly from `a` to `A`. There must be a small 2 space corridor section inside the maze area.
* On the turn where a rat reaches its exit point (or any time after that), it is no longer visible to other rats.
* Your program may be designed to compute mazes for 1, 2, up to 26 rats.
* Standard loopholes are disallowed.

### Score:

With your solution, nominate how many rats per maze (N) your program can solve. Your score is your code length in bytes divided by this number N.

Please include a sample output in your answer so we can see what your program produces.

# Answer
> 2 votes
# Haskell, 26 rats?, ~5000 bytes

Theoretically, this code should work for any number of rats, but I offer no warranty that it will terminate before the heat death of the universe. It is based on a backtracking algorithm which tries to go the straight path first, and then switch path if the path doesn't work. The number of alternatives is exponential with respect to the length of the path and the number of rats.

I haven't bothered to golf it yet, since it's so large, and since I want to make it faster first.

```
{-# LANGUAGE FlexibleContexts #-}
module Main (main) where

import Control.Lens
import Control.Monad
import Data.Char
import Data.Function
import Data.List
import Data.Maybe

type Pos = (Int,Int)
type Path = [Pos]
type Maze = String
type Input = [(Pos,Char)]
type MazeState = [(Path,Path)]

type ChoiceMonad a = [a]

instance (Num a, Num b) => Num (a,b) where
  (x,y)+(x',y')=(x+x',y+y')
  (x,y)-(x',y')=(x-x',y-y')
  fromInteger n = (fromInteger n,fromInteger n)

parseMaze :: Maze -> Input
parseMaze maze = maze ^@.. inner . filtered (`notElem` "# ")

inner :: IndexedTraversal' Pos Maze Char
inner = lined <.> traversed

main :: IO ()
main = do
    maze <- readFile "Sample2.in"
    putStrLn $ solveAndShow maze

fillMaze :: Maze -> Maze
fillMaze = inner.filtered(==' ').~'#'

updateMaze :: Path -> Maze -> Maze
updateMaze path = inner.indices (`elem` path).filtered(=='#') .~ ' '

isDone :: MazeState -> Bool
isDone = all (null . snd)

showMaze :: Maze -> MazeState -> Maze
showMaze maze path = updateMaze (fst =<< path) $ fillMaze maze

showSolution :: Maze -> ChoiceMonad MazeState -> String
showSolution _    []    = "Impossible"
showSolution maze (x:_) = showMaze maze x

stopCondition :: ChoiceMonad MazeState ->  Bool
stopCondition x = not $ null x || isDone (head x)

solveAndShow :: Maze -> String
solveAndShow maze = showSolution maze . solve $ mazeToState maze

solve :: ChoiceMonad MazeState -> ChoiceMonad MazeState
solve = fromJust . find (not.stopCondition) . iterate fullStep

mazeToState :: Maze -> ChoiceMonad MazeState
mazeToState maze = do
    let startsEnds = paths $ parseMaze maze
        return $ startsEnds & traverse.both %~ (:[])

fullStep :: ChoiceMonad MazeState -> ChoiceMonad MazeState
fullStep = (>>= stepAll)

stepAll :: MazeState -> ChoiceMonad MazeState
stepAll input = do
    pths <- mapM goStep input
    guard $ iall (checkVisible pths) $ map fst pths
    return $ pths
  where
    goStep :: (Path,Path) -> ChoiceMonad (Path,Path)
    goStep (curr:rest,[]) = return (curr:curr:rest,[])
    goStep (curr:these,end:ends)
       | distance curr end == 1 = return (end:curr:these,ends)

       | curr == end = goStep (curr:these,ends)
    goStep (path,end) = do
      next <- twoSteps (head end) path
      prev <- twoSteps next end
      return $ (next:path,prev:end)
    inMaze = inMazeWith input

    twoSteps :: Pos -> Path -> ChoiceMonad Pos
    twoSteps goal path = do
      next <- oneStep goal path inMaze
      guard $ not.null $ oneStep goal (next:path) (\x -> x==next || inMaze x)
      return next

checkVisible :: MazeState -> Int -> Path -> Bool
checkVisible _    _ [] = True
checkVisible pths i xs@(x:_) = checkBack && checkNow
  where
    nBack = 1 + visibleBackwards xs
    --checkBack = none (any (==x).take nBack .fst) pths
    checkBack = hasn't (folded.indices (/=i)._1.taking nBack folded.filtered (==x)) pths
    checkNow  = inone (\i' (x':_,_) -> (i/=i') && (==x') `any` take nBack xs ) pths

-- How long have you stayed on a line
visibleBackwards :: Path -> Int
visibleBackwards as = length . takeWhile ((==headDiff as) .headDiff). filter ((>=2).length) $ tails as
      where headDiff (a:a1:_) = a-a1
            headDiff x        = error $ "Bug: Too short list " ++ show x

inMazeWith :: [(Path, Path)] -> Pos -> Bool
inMazeWith = flip elem . concatMap (\x->snd x ++ fst x)

oneStep :: MonadPlus m => Pos -> Path -> (Pos -> Bool)  -> m Pos
oneStep end (curr:prev:_) inMaze =
  if distance curr end <= 1
     then return end
     else do
    let distance' :: Pos -> Double
        distance' x = fromIntegral (distance x end) + if curr - prev == x - curr then 0 else 0.4
    next <- msum . map return $ sortBy (compare`on`distance') $ neighbors curr

    -- Don't go back
    guard $ next /= prev

    -- Stay in bounds
    guard $ isInBounds next

    let dir = (next - curr)
    let lr = neighbors next \\ [curr,next+dir,end]

    -- If next is blocked, check that the one after that is free
    if inMaze next
      then do
        guard $ not . (\x->(x/=end)&&inMaze x) $ next + dir
        -- Both sides should be blocked as well
        guard $ (==2). length . filter inMaze $ lr
      else do
        -- No neighbors if empty
        guard $ null . filter inMaze $ lr

    -- All neighbors of 'curr', including 'next'
    let neigh' = filter (\i -> inMaze i || i == next) $ neighbors curr
        -- should be an even number
        guard $ even $ length neigh'

    return next
oneStep _ [start] _ = return $ inBounds start
oneStep _ _ _ = error "Too short path given"

toBounds :: (Num a, Eq a) => (a,a) -> a -> a
toBounds (low, high) x
    | x == low  = x + 1
    | x == high = x - 1
    | otherwise = x

distance :: Pos -> Pos -> Int
distance (x1,y1) (x2,y2) = abs(x1-x2)+abs(y1-y2)

-- Moves a pos to the closest one inside the bounds
inBounds :: Pos -> Pos
inBounds = bimap (toBounds (0,21)) (toBounds (0,61))

isInBounds :: Pos -> Bool
isInBounds x = x == inBounds x

neighbors :: Pos -> [Pos]
neighbors pos = [ pos & l %~ p| l <- [_1,_2], p <- [succ,pred]]

paths :: Input -> [(Pos,Pos)]
paths pos = flip unfoldr 'a' $ \x ->
  do (y,_) <- find ((==x).snd) pos
     (z,_) <- find ((==toUpper x).snd) pos
     return ((y,z),succ x)

```

Sample output, 6 rats:

```
##c###B#####b#######C#######F######################f##########
##   #       #       #######                        ##########
####  ######## ###############################################
#####          ###############################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
#############       ##########################################
############# #####  #########################################
D             #    #     #####################################
##############  ## ##### #####################################
#########      #                 #############################
######### ###### # ##### ####### #############################
####      #      #     # #######                        ######
####E######a##########e#d##############################A######

```

# Answer
> 1 votes
# Haskell, 1 rat, 681 Characters

The problem can be trivially solved for all mazes with just one rat. This code also "works" for any number of rats, but doesn't follow any of the constraints on the interactions between *multiple* rats and paths.

```
module Main where
import Control.Lens
import Data.List(unfoldr,find)
import Data.Char(toUpper)
parse=(^@..lined<.>folded.filtered(`notElem`"# "))
main=interact$do i<-(naive=<<).rats.parse;(lined<.>traversed).filtered(==' ').indices (`notElem`i).~'#'
    naive(start,(ex,ey))=start':unfoldr go start' where
     start'=bnds start
     (ex',ey')=bnds(ex,ey)
     go(x,y)
      |(x,y)==(ex',ey')=Nothing
      |x== ex'=ok(x,y`t`ey')
      |otherwise=ok(x`t`ex',y)
     ok z=Just(z,z)
     t x y=if x>y then x-1 else x+1
    bnd(l,h)x |x==l=x+1 |x==h=x-1 |True=x
    bnds=bimap(bnd(0,21))(bnd(0,61))
    rats pos=(`unfoldr`'a')$ \x->
  do (y,_)<-find((==x).snd)pos
     (z,_)<-find((==toUpper x).snd)pos
     return((y,z),succ x)

```

Sample output:

```
#######a######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
#######                                           ############
#################################################A############

```

I'm planning to support many rats, so I wrote generic code, but I haven't found a good algorithm for that yet.

* `parse` extracts a list of all entrances and exits, with their coordinates
* `rats` takes that list and converts it to pairs of coordinates for each rat.
* `bnds` takes a coordinate on an edge and moves it to the nearest coordinate inside the maze.
* `naive` takes a start and end positions and returns a simple path between them.
* `main` then replaces all the white space not in a path with '#'

---
Tags: code-golf, grid, maze
---


# Question
Title: Collatz sequence on a two counter machine
The Collatz sequence starting from a positive integer n is defined in this way:

* if n is even then divide it by 2 (`n' = n / 2`)
* if n is odd then multiply it by 3 and add 1 (`n' = 3n + 1`)

Repeat the above iteration until n reaches 1.

It is not known (it's a major unsolved problem in number-theory) if the sequence will eventually reach the number 1, regardless of which positive integer is chosen initially.

A Two Counter Machine (2CM) is a machine equipped with two registers that can hold a non-negative integer value and can be programmed with the following instruction set:

```
INCX    increase the value of register X
INCY    increase the value of register Y
JMP n   jump to instruction n
DJZX n  if register X is zero jump to instruction n,
        otherwise decrement its value
DJZY n  if register Y is zero jump to instruction n,
        otherwise decrement its value
HALT    halt (and accept)
PRINTX  print the content of register X

```

A 2CM program is simply a sequence of instructions, for example the following program simply copies the content of register X to register Y:

```
cp:   DJZX end
      INCY
      JMP cp
end:  HALT

```

Note that a 2CM is Turing Complete (i.e. it can compute every computable function with a suitable input encoding, but it is irrelevant here). Also note that the instruction set is a little bit different from the one in the Wikipedia article.

## The challenge

Write the shortest 2CM program, that computes and prints the collatz sequence up to 1 and halts (the register X initially contains the starting value `n` and register Y initially contains 0). Note that the **length** of a 2CM program is the number of instructions used (not the length of the text).

For example, when started from X=3 it must print: `3 10 5 16 8 4 2 1` and HALT.

So you can use your favourite language to build a 2CM simulator/interpreter, but the final (shortest) code that you put in the answer *must be in the 2CM language*.

# Answer
# 18 instructions

I was a bit disappointed that I arrived late on scene, as the minimalistic nature of the problem and the language make there (seemingly) only one general approach for a good answer. I got a 19-instruction answer fairly quickly, but I didn't feel like it brought enough to the table to post it. But after much head scratching, my hacky z80 assembly experience came through and I found a way to save an instruction by reusing a block of code for a purpose it wasn't meant for!

```
# Let N be the previous number in the Collatz sequence.

# Print N, and if N==1, halt.
# X=N, Y=0
Main:           PRINTX          # Print N.
                DJZX Done       # X=N-1 (N shouldn't be zero, so this never jumps)
                DJZX Done       # If N-1==0, halt. Otherwise, X=N-2.

# Find the parity of N and jump to the proper code to generate the next N.
# X=N-2, Y=0
FindParity:     INCY
                DJZX EvenNext   # If N%2==0, go to EvenNext with X=0, Y=N-1.
                INCY
                DJZX OddNext    # If N%2==1, go to OddNext with X=0, Y=N-1.
                JMP FindParity

# Find the next N, given that the previous N is even.
# X=0, Y=N-1
EvenNext:       INCX
                DJZY Main       # Y=Y-1 (Y should be odd, so this never jumps)
                DJZY Main       # If Y==0, go to Main with X=(Y+1)/2=N/2, Y=0.
                JMP EvenNext

# Find the next N, given that the previous N is odd.
# X=0, Y=N-1
OddNext:        INCX
                INCX
                INCX
                DJZY EvenNext   # If Y==0, go to EvenNext with X=(Y+1)*3=N*3, Y=0.
                JMP OddNext     # ^ Abuses EvenNext to do the final INCX so X=N*3+1.

# Halt.
Done:           HALT

```
> 12 votes

# Answer
## 19 instructions

I wrote my own interpreter because I'm fancy like that. Here is my solution for my own interpreter:

```
MP
 XE
 XE
HY
 XV
 XO
 JH
WX
VYM
 JW
LYM
 X
 X
OX
 X
 X
 X
 JL
EH

```

And here is what it looks like with syntax compatible to the other interpreter:

```
# x = n, y = 0
main:    printx
         djzx   end
         djzx   end

# x = n - 2, y = 0 on fallthrough
half:    incy
         djzx   even
         djzx   odd
         jmp    half

evloop:  incx
# x = 0, y = n / 2  on jump to even
even:    djzy   main
         jmp    evloop

oddloop: djzy   main
         incx
         incx
# x = 0, y = (n + 1) / 2 on jump to even
odd:     incx
         incx
         incx
         incx
         jmp    oddloop

end:     halt

```
> 5 votes

# Answer
**SCORE: 21**

Here is my attempt:

`main`: prints `X` and jumps to `finish` (if `X==1`).

`divisibility`: makes a distinction if `X%2==0` or `X%2==1`. Also copies `X` to `Y` and makes `X==0`. Jumps to either `isDivisible` (if `X%2==0`) or `isNotDivisible` (if `X%2==1`).

`isDivisible`: loop used when `Y%2==0`. For each decrease of `Y` by 2, it increases `X` by 1. When `Y==0`, jumps to `main`.

`isNotDivisible`: used when `Y%2==1`. It increases `X` by 1.

`notDivLoop`: loop used when `Y%2==1`. For each decrease of `Y` by 1, it increases `X` by 3. When `Y==0`, jumps to `main`.

`finish`: halts

```
main:           PRINTX              # print X
                DJZX main           # here X is always >0 and jump never fires (it is just for decreasing)
                DJZX finish         # if initially X==1 this jumps to finish
                INCX                # establish the previous state of X
                INCX
                                    # continue with X>1

divisibility:   DJZX isDivisible    # if X%2==0, then this will fire (when jumping Y=X)
                INCY
                DJZX isNotDivisible # if X%2==1, this fires (when jumping Y=X)
                INCY
                JMP divisibility    # jump to the beginning of loop

isDivisible:    DJZY main           # this jumps to the main loop with X=X/2
                DJZY main           # this jump will never fire, because X%2==0
                INCX                # for every partition 2 of Y, increase X (making X=Y/2)
                JMP isDivisible     # jump to beginning of loop

isNotDivisible: INCX                # X=0, increase for 1
notDivLoop:     DJZY main           # in each iteration, increase X for 3 (when Y==0, X=3Y+1)
                INCX
                INCX
                INCX
                JMP notDivLoop      # jump to beginning of loop

finish:         HALT                # finally halt

```

Supplied with 3 (using the interpreter supplied by @orlp), the produced result is:

```
3
10
5
16
8
4
2
1

```
> 4 votes

# Answer
# 19 instructions

```
found:    PRINTX       # print input/found number
          DJZX done    # check if n == 1
          DJZX done    # after this point x == n - 2
parity:   INCY         # after this loop y == n // 2
          DJZX even
          DJZX odd
          JMP parity
odd-loop: DJZY found
          INCX
          INCX
odd:      INCX         # we enter mid-way to compute x = 6y + 4 = 3n + 1
          INCX
          INCX
          INCX
          JMP odd-loop
even:     DJZY found   # simply set x = y
          INCX
          JMP even
done:     HALT

```

You can run it using my interpreter.
> 4 votes

---
Tags: sequence, atomic-code-golf
---


title: The Sound of Words

text:
# Question
Title: The Sound of Words
People have written many things allowing one thing to be visualized as another. Now I propose being able to translate letters to music! Its your job to write a program that takes a text file and outputs a sound file with each letter converted to a specific note from `C3-C8`.

*Disclaimer - I don't actually expect the music to sound any good but I hope to be surprised.*

## Specifications

* You take the name of a file as a string and the BPM (beats per minute) as an int
* You make uppercase `A` to be the note `C3`
* And go up a half-step for every character after in this order: `ABCDEFGHIJKLMNOPQRSTUVWXYZ ()-,;.'"abcdefghijklmnopqrstuvwxyz`
* Yes, not every character will be used since that spans too many octaves.
* You translate every character in the file in this way
* Put the notes together at the given BPM as quarter notes
* Either save as a sound file (I'm guessing midi will be the easiest, but anything is ok) or play it
* Any sane input format is fine
* No standard loopholes
* This is code-golf, so shortest code in **bytes** wins!

## Bonuses

* Allow transposing of output - **50 bytes**
* Allow multiple tracks to be superimposed over each other by taking multiple files - **75 bytes**
* Join consecutive letters into one longer note - **50 bytes**

**Edit:** Wow, we have negative scores. I'll be announcing the winner on Saturday.

# Answer
# MATLAB, 159-50-50-75 = -16

Sample input

Sample output

Generates pure sine sound waves, very funky (sawtooth is also possible, with an even better score, but that sounds a bit... *too* funky). Works as a function, so expects it a character array (`['abc';'def']`) with one row per 'track'. I think that is covered under *'any sane input format'*, but if the general consensus is that I need to read a file, I suppose I can change it. Input `i` is text tracks (of equal length), `b` beats per minute and `t` transpose (supply 0 for not transposed). It blends two sines into one by offsetting the sine input, so I got all three bonuses, giving me a negative score.

```
function v(i,b,t)
s=0;for r=1:size(i)
o=[];for k=i(r,:)
o=cat(2,o,sin(55*pi*2^((k-28+t)/12)*(numel(o)/2^13+(0:1/2^13:60/b))));end
s=s+o;end
sound(s/max(s))
end

```

# Version using input file: 211-175=36

Input argument `i` now represents the file name, other parameters unchanged. Might not work on newer releases because I'm getting a warning that `textread` may soon be deprecated. EDIT: textread apparently automatically splits up at whitespaces, so I fixed that. Also, I think I may have accidentally contacted some aliens with the weird sounds made while testing.

```
function v(i,b,t)
i=textread(i,'%s','whitespace','','delimiter','\n');s=0;for r=1:size(i)
o=[];for k=i{r,:}
o=cat(2,o,sin(55*pi*2^((k-28+t)/12)*(numel(o)/2^13+(0:1/2^13:60/b))));end
s=s+o;end
sound(s/max(s))
end

```

Which version do you prefer? :)
> 6 votes

# Answer
## Snap*!* \- 401 - 75 = 326

Try it online here.

I'm using this method of counting bytes for the program.

I added playing multiple sounds at once.

The basic structure is the same as the original (see below), but with the addition of `launch{}`. `launch{}` starts a new thread with the code inside, allowing for concurrency.

The code as text is:

```
set[c v]to[ABCDEFGHIJKLMNOPQRSTUVWXYZ ()-,;.'"abcdefghijklmnopqrstuvwxyz
set[l v]to(list>
ask[BPM]and wait
set tempo to(answer)bpm
repeat until<(answer)=[
ask[notes]and wait
add(answer)to(l
end
delete(last v)of(l
for each(i)of(l
launch{
repeat(length of(i))(#
play note(i(c)(letter(#)of(i)))for(0.25)beats

(i(h)(n))
report(call(JavaScript function ([h][n]) {[return h.indexOf(n)+48]})with inputs(h)(n

```

---

Original code, 308.

Lucky Snap! has MIDI playing built in. ;)

Unfortunately, it doesn't have an `indexOf` function, so i have to make an external JavaScript call, which is pretty expensive.

The `repeat () (#)` block comes from the iteration library.

The code can be written out as text like this, which is how i get 308 bytes:

```
set[c v]to[ABCDEFGHIJKLMNOPQRSTUVWXYZ ()-,;.'"abcdefghijklmnopqrstuvwxyz
ask[BPM]and wait
set tempo to(answer)bpm
ask[notes]and wait
repeat(length of(answer))(#)
play note(i(c)(letter(#)of(answer)))for(0.25)beats

(i(h)(n))
report(call(JavaScript function ([h][n]) {[return h.indexOf(n)+48]})with inputs(h)(n

```
> 4 votes

# Answer
# Mathematica, 219 - 50 - 75 - 50 = 44

```
c=CharacterRange;d=Import;EmitSound[Function[b,Sound[Split@Characters@d@b/.a:{__String}:>SoundNote[StringPosition[c["A","Z"]<>" ()-,;.'\""<>c["a","z"],a[[1]]][[1,1]]+#3-12,60Length@a/#2],{0,60StringLength@d@b/#2}]]/@#]&

```

Takes the list of input files, BPM, and number of half-steps to transpose by as input and plays the sound (from a piano, any other instrument would take more bytes.) Doesn't sound that bad!
> 4 votes

# Answer
# JavaScript (ES6) 377 - 50 - 50 - 75 = 202

First, here's a runnable snippet that uses `<input>` fields instead of file-reads:

```
<b>BMP:</b> <input id="bpm" size=3 placeholder="BMP" value="120"> <b>Transpose:</b> <input size=3 id="transpose" placeholder="Transpose" value="0"><br/><br/><div id="tracks" style="float:left;padding-right:5px;"><input placeholder="Track" class="track"></div><button id="add">Add Additional Track</button><div style="clear:both; padding-top:5px;"></div><button id="play"><b>Play</b></button><script>f=function(s,b,z){C=new (window.AudioContext||window.webkitAudioContext);b=6e4/b;s.map(function(p){var o=C.createOscillator(t=setTimeout);o.connect(C.destination);o.start();p.split("").map(function(c,i){t(function(){o.frequency.value=440*Math.pow(2, ("ABCDEFGHIJKLMNOPQRSTUVWXYZ ()-,;.'\"abcdefghijklmnopqrstuvwxyz".indexOf(c)-21+z)/12)},b*i)});t(function(){o.stop()},p.length*b)})};document.getElementById("play").onclick=function(){f([].map.call(document.getElementsByClassName("track"),function(e){return e.value;}),+document.getElementById("bpm").value,+document.getElementById("transpose").value);};document.getElementById("add").onclick=function(){var i=document.createElement("input");i.placeholder="Track";i.className="track";document.getElementById("tracks").appendChild(document.createElement("br"));document.getElementById("tracks").appendChild(i);};</script>
```

And now, the actual entry:

```
f=(n,b,z)=>{C=new AudioContext;b=6e4/b;s=n.map(m=>(x=new XMLHttpRequest,x.open("GET",m,0),x.send(),x.responseText));s.map(p=>{var o=C.createOscillator(t=setTimeout);o.connect(C.destination);o.start();[...p].map((c,i)=>t(_=>o.frequency.value=440*Math.pow(2,("ABCDEFGHIJKLMNOPQRSTUVWXYZ ()-,;.'\"abcdefghijklmnopqrstuvwxyz".indexOf(c)-21+z)/12),b*i)),t(_=>o.stop(),p.length*b)})}

```

The three arguments are an array of filepath strings to play concurrently, notes per minute, and number of half-steps to transpose all inputs.

With whitespace and comments:

```
f=(n,b,z)=>{
    C=new AudioContext;
    b=6e4/b;

    // fill s with the contents of each file
    s = n.map(m=>(x=new XMLHttpRequest,x.open("GET",m,0),x.send(),x.responseText));

    // play each track
    s.map(p=>{
        var o=C.createOscillator(t=setTimeout);
        o.connect(C.destination);
        o.start();

        // queue up each note with setTimeout
        [...p].map((c,i)=>
            t(_=>
                o.frequency.value=440*
                    Math.pow(2,
                            ("ABCDEFGHIJKLMNOPQRSTUVWXYZ ()-,;.'\"abcdefghijklmnopqrstuvwxyz".indexOf(c)-21+z)/12
                    ),
             b*i)
        );
        // queue up termination of those track
        t(_=>o.stop(),p.length*b)})
}

f(["file:///home/users/apsillers/notes.txt",
   "file:///home/users/apsillers/notes2.txt"],
  240, 5)

```
> 1 votes

---
Tags: code-golf, music, audio
---


title: What language is this?

text:
# Question
Title: What language is this?
I'm working on something and came across this after I interpreted some brainfuck code. It looks like another esoteric language but I'm not sure what. Anyone know?

```
(CB;:9]~}5Yz2Vw/StQr*)M:,+*)('&%$#"!~}|{zyx875t"2~p0nm,+jch'`%

```

# Answer
> 7 votes
After one second of Googling a portion of the string (`5Yz2Vw`), I found the following page:

http://www.xchg.info/wiki/index.php?title=ICTF\_2011\_:\_Challenge\_13\_-\_250\_Points

On that page it's deduced the code is Malbolge.

---
Tags: golfing-language
---