title: Where'd that germ go?

text:
# Question
Title: Where'd that germ go?
# Introduction

You are a biologist studying the movement patterns of bacteria. Your research team has a bunch of them in a petri dish, and you are recording their activity. Unfortunately, you are seriously underfunded, and can't afford a video camera, so you just take a picture of the dish at regular intervals. Your task is to make a program that traces the movements of the germs from these pictures.

# Input

Your inputs are two 2D arrays of characters in any reasonable format, representing consecutive pictures of the petri dish. In both arrays, the character `.` represents empty space, and `O` represents a germ (you can choose any two distinct characters if you want). Also, the "after" array is obtained from the "before" array by moving some germs one step in one of the four cardinal directions; in particular, the arrays have the same shape. The germs move simultaneously, so one of them may move to a space that already contained another germ, if it moves out of the way. It is guaranteed that the borders of the "before" array contain only empty spaces, and that there is at least one germ. Thus, the following is a valid pair of inputs:

```
Before  After
......  ......
.O..O.  ....O.
.OO.O.  .OO.O.
......  ..O...

```

# Output

Your output is a single 2D array of characters in the same format as the inputs. It is obtained from the "before" array by replacing those germs that have moved with one of `>^<v`, depending on the direction of movement (you can also use any 4 distinct characters here). There may be several possible outputs, but you shall give only one of them. In the above example, one possible correct output is

```
......
.v..O.
.>v.O.
......

```

Unnecessary movement is allowed in the output and germs can swap places, so the following is also valid:

```
......
.v..v.
.>v.^.
......

```

# Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

I'm interested in relatively efficient algorithms, but I don't want to ban brute forcing entirely. For this reason, there's a **bonus of -75%** for solving the last test case within 10 minutes on a modern CPU (I'm unable to test most solutions, so I'll just trust you here). **Disclaimer:** I know that a fast algorithm exists (search for "disjoint paths problem"), but I haven't implemented it myself.

# Additional test cases

```
Before
......
.O..O.
..OO..
......
After
......
..O...
...OO.
..O...
Possible output
......
.>..v.
..vO..
......

Before
.......
.OOOOO.
.O..OO.
.OO..O.
.OOOOO.
.......
After
.......
..OOOOO
.O...O.
.O...O.
.OOOOOO
....O..
Possible output
.......
.>>>>>.
.O..>v.
.Ov..v.
.O>>v>.
.......

Before
..........
.OOO..OOO.
.OOOOOOOO.
.OOO..OOO.
..........
After
..O.......
.OOO..O.O.
..OOOOOOOO
.O.O..OOO.
.......O..
Possible output
..........
.>^O..O>v.
.^O>>>vO>.
.O>^..>vO.
..........

Before
............
.OO..OOOOOO.
.OO......OO.
...OOOOOO...
.O.OOOOOO.O.
...OOOOOO...
.OOOOOOOOOO.
............
After
..........O.
.OO..OOOOO..
.O...O...O..
.O.OOOOOOO..
.O.OOOOOO..O
...OO..OO...
....OOOOOOOO
.OOO........
Possible output
............
.OO..v<<<<^.
.v<......^<.
...OOO>>>...
.O.OOO^OO.>.
...OOv^OO...
.vvvO>>>>>>.
............

Before
................
.OOOOOO.OOOOOOO.
..OO..OOOOOOOOO.
.OOO..OOOO..OOO.
..OOOOOOOO..OOO.
.OOOOOOOOOOOOOO.
................
After
................
..OOOOO.OOOOOOOO
..OO..OOOOOOOOO.
..OO..OOOO..OOOO
..OOOOOOOO..OOO.
..OOOOOOOOOOOOOO
................
Possible output
................
.>>>>>v.>>>>>>>.
..OO..>>^>>>>>v.
.>>v..OOO^..OO>.
..O>>>>>>^..OOO.
.>>>>>>>>>>>>>>.
................

Before
..............................
.OOO.O.O.....O.....O.O.O..O...
..OOO.O...O..OO..O..O.O.......
.....O......O..O.....O....O...
.O.OOOOO......O...O..O....O...
.OO..O..OO.O..OO..O..O....O...
..O.O.O......OO.OO..O..OO.....
..O....O..O.OO...OOO.OOO...O..
.....O..OO......O..O...OO.OO..
........O..O........OO.O.O....
..O.....OO.....OO.OO.......O..
.O.....O.O..OO.OO....O......O.
..O..OOOO..O....OO..........O.
.O..O...O.O....O..O....O...OO.
....O...OO..O.......O.O..OO...
........O.O....O.O....O.......
.OO.......O.OO..O.......O..O..
....O....O.O.O...OOO..O.O.OO..
.OO..OO...O.O.O.O.O...OO...O..
..............................
After
..............................
.OOOOO.......OO.....O..O......
...OO..O...O...O....OO....O...
....O.O......O..OO...OO...O...
.OO.OOOO......OO..O..O........
O.O.OO..O..O..O..OO...O...OO..
.OO.....O....OO.O..O.OO.O.....
......O.....O.....OOO.OO...O..
....O..OOOO..O..O..O.O.O.OO...
..O......O.O........O...O.O...
.O.....OOO.....OO.OO...O...O..
.......OOO..O.O.O...........O.
.O...O.....O...OOOO..O.O....O.
.O..O.O..O.....O......O....OO.
....O..O..O.O......O.....O....
........OOO....O......O..O....
.OO......O..OO..OOO.....O..O..
..O.O....OO..O...OO...O...OO..
.O..OO....O..O...O.O.O.OO.....
..............O............O..
Possible output
..............................
.OOO.O.v.....>.....>.v.O..v...
..>>^.v...>..^>..v..O.v.......
.....<......>..>.....O....O...
.O.<O><O......O...O..O....v...
.<O..O..v<.O..O^..O..>....>...
..<.^.v......OO.O^..>..<O.....
..^....v..v.Ov...>>^.<OO...O..
.....<..OO......O..O...Ov.v<..
........>..O........O^.v.^....
..^.....Ov.....OO.OO.......O..
.^.....^.^..O>.vO....v......O.
..<..Ov^^..O....><..........O.
.O..O...>.v....O..^....^...OO.
....O...<v..O.......<.^..v<...
........O.O....O.v....O.......
.OO.......<.Ov..O.......O..O..
....O....O.<.^...O^v..O.v.OO..
.O^..<<...O.>.v.>.^...<O...v..
..............................

```

# Answer
> 3 votes
# Octave, ~~494~~ 496 bytes - 372 byte bonus = 124 bytes

```
function o=G(b,a)
y='.O<^v>';s=(b>46)+0;t=a>46;v=t;f=s;t(:,2:end,2)=t(:,1:end-1);t(2:end,:,3)=t(1:end-1,:,1);t(1:end-1,:,4)=t(2:end,:,1);t(:,1:end-1,5)=t(:,2:end,1);t=reshape(t,[],5);m=size(s,1);p=[0 -m -1 1 m];
function z(n)
f(n+p(s(n)))--;q=find(t(n,:));w=n+p(q);d=min(f(w));q=q(f(w)==d);j=randi(numel(q));s(n)=q(j);f(n+p(q(j)))++;end
for g=find(s)' z(g);end
while any((f~=v)(:)) L=find(s);k=zeros(size(s));for h=L' k(h)=f(h+p(s(h)));end;c=find(k>1);g=c(randi(numel(c)));z(g);end
o = y(s+1);end

```

There's still a lot of golfing to be done on this answer, but I wanted to get the ungolfed explanation in.

I saw this as a Constraint Satisfaction Problem, so I went with my favorite local search heuristic, Min-conflicts. The idea is, given a starting placement with each germ in a reachable destination, select a random germ that occupies the same destination cell as one or more other germs and move it to a valid cell that has a minimum of other germs already there. Repeat as necessary until the placement matches the goal.

Interestingly, this algorithm is not guaranteed to terminate (if the goal is unreachable it will continue indefinitely, for instance) but if it does terminate it is guaranteed to produce a valid solution.

Here's the code:

```
function output = germs(before, after)

%before = ['......';'.O..O.';'.OO.O.';'......'];
%after = ['......';'....O.';'.OO.O.';'..O...'];

symbs = '.O<^v>';
start = (before > 46) + 0;                   %should be called current_board
target = after > 46;                         %destinations on current cell == O
goal = target;
conflicts = start;
target(:, 2:end,2) = target(:, 1:end-1);     %destinations on cell to left
target(2:end, :,3) = target(1:end-1, :,1);   %destinations on cell above
target(1:end-1, :,4) = target(2:end, :,1);   %destinations on cell below
target(:, 1:end-1,5) = target(:, 2:end,1);   %destinations on cell to right
target=reshape(target,[],5);
m = size(start,1);                           %number of rows = offset to previous/next column
offsets = [0 -m -1 1 m];                     %offsets of neighbors from current index

function moveGerm(n)
   conflicts(n+offsets(start(n)))--;         %take germ off board
   move = find(target(n, :));                %get valid moves for this germ
   neighbors = n + offsets(move);            %valid neighbors = current position + offsets
   minVal = min(conflicts(neighbors));       %minimum number of conflicts for valid moves
   move = move(conflicts(neighbors)==minVal);
   mi = randi(numel(move));                  %choose a random move with minimum conflicts
   start(n) = move(mi);                      %add move type to board
   conflicts(n + offsets(move(mi)))++;       %add a conflict on the cell we move to
end

% Generate an initial placement
for g = find(start)'
   moveGerm(g);                              %make sure all germs are moved to valid cells
end

% Repeat until board matches goal
while any((conflicts ~= goal)(:))
   germList = find(start);                   %list of all our germs
   cost = zeros(size(start));                %calculate conflicts for each germ
   for h = germList'
      cost(h) = conflicts(h + offsets(start(h)));
   end
   conflicted = find(cost > 1);              %find those germs that occupy the same cell as another
   g = conflicted(randi(numel(conflicted))); %choose a random germ to move
   moveGerm(g);
end

output = symbs(start+1);                     %use moves as indices into symbol array for output

end

```

Output for the last test case:

```
>> gtest
ans =

..............................
.OO>.O.v.....>.....>.v.O..v...
..>^O.v...>..^>..v..O.v.......
.....v......>..>.....O....O...
.O.<^<OO......>...O..O....v...
.<O..O..v<.O..^<..O..>....>...
..<.^.v......OO.O^..<..<O.....
..^....v..v.Ov...>>>.^OO...O..
.....<..OO......O..O...Ov.<<..
........>..O........O^.v.>....
..^.....OO.....OO.OO.......O..
.^.....^.O..O>.vO....v......O.
..<..Ov^^..O....OO..........O.
.O..O...>.v....O..^....^...OO.
....O...<v..O.......<.^..v<...
........O.O....O.v....O.......
.OO.......<.OO..O.......O..O..
....O....O.<.O...O^<..O.v.OO..
.O^..<<...O.>.v.>.>...<O...v..
..............................

Elapsed time is 0.681691 seconds.

```

The average elapsed time was less than ~~9 seconds~~ 1 second\* on a 5 year old Core i5, qualifying for the bonus.

~~I'm trying to get this working on ideone, but I'm having what I believe to be scoping issues with the way it handles nested functions. (Here's the non-working ideone link for reference: http://ideone.com/mQSwgZ)~~
The code on ideone is now working. I had to force all of the variables to global, which was unnecessary running it locally.

\*I had a note in my ungolfed version that one of the steps was inefficient, so I tried it to see if I could speed up execution and for 2 added bytes the execution time is now down to under a second. Code and sample output has been updated and the input on ideone has been changed to the last test case.

# Answer
> 3 votes
# Python, 1171 bytes - 878.25 byte bonus = 292.75 bytes

```
from itertools import *;from random import *;R=range;L=len;O=choice;G='O'
def A(a,b):a.append(b)
def D(y,z):
 a=[];b=[];c=[]
 for i in R(L(y)):
  A(c,[])
  for j in R(L(y[0])):
   k=[(i,j),y[i][j]==G,z[i][j]==G,[],0];A(c[i],k)
   for l,m in [(0,1),(1,0)]:
    try:
     n=c[i-l][j-m]
     if k[2]&n[1]:A(n[3],k)
     if k[1]&n[2]:A(k[3],n)
    except:pass
   if k[1]&~k[2]:A(a,k)
   elif k[2]&~k[1]:A(b,k)
 d={}
 for i in a:
  j=[[i]]
  while j:
   k=j.pop();l=[e[0] for e in k]
   while True:
    m=k[-1];n=[o for o in m[3] if o[0] not in l]
    if not n:
     if m in b:A(d.setdefault(i[0],[]),k)
     break
    for o in n[1:]:p=k[:];A(p,o);A(j,p)
    A(k,n[0]);A(l,n[0][0])
 e={}
 for i in a:e[i[0]]=O(d[i[0]])
 def E():return sum(any(k in j for k in i) for i,j in combinations(e.values(),2))
 f=E()
 for i in count():
  t=3**-i/L(a);j=O(a);k=e[j[0]];e[j[0]]=O(d[j[0]]);l=E()
  if not l:break
  else:
   if l>f and random()>t:e[j[0]]=k
   else:f=l
 for i in e.values():
  for j in R(L(i)-1):i[j][4]=i[j+1]
 for i in c:
  for j in R(L(i)):
   k=i[j]
   if 1&~k[1]:i[j]='.'
   elif not k[4]:i[j]=G
   else:l,m=k[0];n,o=k[4][0];i[j]='v>^<'[abs((l-n+1)+2*(m-o))]
 return c

```

Ideone link: http://ideone.com/0Ylmwq

Takes anywhere from 1 - 8 seconds on the last test case on average, qualifying for the bonus.

This is my first code-golf submission, so it's probably not the best-golfed program out there. Nevertheless, it was an interesting challenge and I quite enjoyed it. @Beaker deserves a mention for reminding me that heuristic-based searches are a thing. Before he posted his solution and inspired me to redo mine, my brute force search was waaaay too long to qualify for the bonus on the last test case (it was on the order of 69! iterations, which is a 99-digit number...).

I didn't want to straight-up copy Beaker's solution, so I decided to use simulated annealing for my search heuristic. It seems slower than min-conflict for this problem (likely because it's an optimization algorithm rather than a constraint-satisfaction one), but it's still well within the 10-minute mark. It also had the benefit of being fairly small, code-wise. I spent a lot more bytes on transforming the problem than I did on finding a solution to it.

## Explanation

My solution is probably fairly inefficient byte-wise, but I had trouble conceptualizing how to solve the problem as-is and so I ended up having to transform it into a different problem that was easier for me to understand. I realized that there are four possiblities for each cell on the grid:

* It had no germ before or after, which means we can ignore it
* It had a germ before but not after, which means we have to find a move for it.
* It had no germ before but one after, which also means we have to find a move for it.
* It had a germ before and after, which means we might have to find a move for it, but then again maybe not.

After decomposing the data into those classes, I was able to further transform the problem. It was immediately obvious to me that I had to find a way to supply a germ from the "before but not after" set to a cell in the "after but not before" set. Further, germs can only move one space, so the only way for them to affect further-away cells is by "pushing" an unbroken path of germs into that cell. That meant the problem became finding X vertex-disjoint paths on a graph, where each cell with a germ was a vertex in said graph, and the edges represented adjacent cells.

I solved that problem that by first building the graph explained above. I then enumerated *every* possible path from each cell in Before and each cell in After, then randomly assigned each cell in Before one of its possible paths. Finally, I used simulated annealing to semi-randomly mutate the potential solution until I eventually find a solution that has no conflicts for any of the paths.

## Annotated version

```
from itertools import *;from random import *;

# redefine some built-in functions to be shorter
R=range;L=len;O=choice;G='O'
def A(a,b):a.append(b)

# The function itself.  Input is in the form of two 2d arrays of characters, one each for before and after.
def D(y,z):
 # Declare the Before-but-not-after set, the After-but-not-before set, and a temp cell array
 # (the cells are temporarily stored in a 2d array because I need to be able to locate neighbors)
 a=[];b=[];c=[]

 # Build the graph
 for i in R(L(y)):
  # Append a row to the 2d temp array
  A(c,[])

  for j in R(L(y[0])):
   # Define the interesting information about the cell, then add it to the temp array
   # The cell looks like this: [position, does it have a germ before?, does it have a germ after?, list of neighbors with germs, final move]
   k=[(i,j),y[i][j]==G,z[i][j]==G,[],0];A(c[i],k)
   for l,m in [(0,1),(1,0)]:
    # Fill up the neighbors by checking the above and left cell, then mutually assigning edges
    try:
     n=c[i-l][j-m]
     if k[2]&n[1]:A(n[3],k)
     if k[1]&n[2]:A(k[3],n)
    except:pass

   # Decide if it belongs in the Before or After set
   if k[1]&~k[2]:A(a,k)
   elif k[2]&~k[1]:A(b,k)

 # For each cell in the before set, define ALL possible paths from it (this is a big number of paths if the grid is dense with germs)
 # This uses a bastard form of depth-first search where different paths can cross each other, but no path will cross itself
 d={}
 for i in a:
  j=[[i]]  # Define the initial stack of incomplete paths as the starting node.
  while j:
   # While the stack is not empty, pop an incomplete path of the stack and finish it
   k=j.pop();l=[e[0] for e in k]
   while True:
    # Set the list of next possible moves to the neighbors of the current cell,
    # ignoring any that are already in the current path.
    m=k[-1];n=[o for o in m[3] if o[0] not in l]

    # If there are no more moves, save the path if it ends in an After cell and break the loop
    if not n:
     if m in b:A(d.setdefault(i[0],[]),k)
     break

    # Otherwise, set the next move in this path to be the first move,
    # then split off new paths and add them to the stack for every other move
    for o in n[1:]:p=k[:];A(p,o);A(j,p)
    A(k,n[0]);A(l,n[0][0])

 # Perform simulated annealing to calculate the solution
 e={}
 for i in a:e[i[0]]=O(d[i[0]])  # Randomly assign paths for the first potential solution

 # Define a function for calculating the number of conflicts between all paths, then do the initial calculation for the initial potential solution
 def E():return sum(any(k in j for k in i) for i,j in combinations(e.values(),2))
 f=E()

 # Do the annealing
 for i in count():
  # The "temperature" for simulated annealing is calculated as 3^-i/len(Before set).
  # 3 was chosen as an integer approximation of e, and the function e^(-i/len) itself was chosen because
  # it exponentially decays, and does so slower for larger problem sets
  t=3**-i/L(a)

  j=O(a)              # Pick a random Before cell to change
  k=e[j[0]]           # Save it's current path
  e[j[0]]=O(d[j[0]])  # Replace the current path with a new one, randomly chosen
  l=E()               # Recalculate the number of conflicts

  if not l:break  # If there are no conflicts, we have a valid solution and can terminate
  else:           # Otherwise check the temperature to see if we keep the new move
   if l>f and random()>t:e[j[0]]=k  # Always keep the move if it's better, and undo it with probability 1 - T if it's worse
   else:f=l                         # If we don't undo, remember the new conflict count

 # Set each of the cells' final moves based on the paths
 for i in e.values():
  for j in R(L(i)-1):i[j][4]=i[j+1]

 # Build the output in the form of a 2d array of characters
 # Reuse the temp 2d array from step since its the right size
 for i in c:
  for j in R(L(i)):
   k=i[j]
   # Cells that are empty in the before array are always empty in the output
   if 1&~k[1]:i[j]='.'
   # Cells that aren't empty and don't have a move are always germs in the output
   elif not k[4]:i[j]=G
   # Otherwise draw the move
   else:l,m=k[0];n,o=k[4][0];i[j]='v>^<'[abs((l-n+1)+2*(m-o))]
 return c

```

---
Tags: code-golf, grid, path-finding
---


title: Secret Santa - Revisited

text:
# Question
Title: Secret Santa - Revisited
Christmas is fast approaching and along with it, arranging the annual family Secret Santa. I'd like to try and get a head start on this, but making sure couples don't buy for each other keeps causing problems and despite doing this for years there's still the problem that `Bob` is pretty rubbish at buying gifts for most of the giftees, `Erin` will likely be disappointed, but he knows that `Frank` likes Talisker, so he's a good match for him. This makes none of the existing simple solutions acceptable for my needs.

To make my life easier, your task is to write a function (or closest alternative in your language) that when given an array of arrays (or closest alternative in your chosen language), returns (or outputs) a pairing of 'gifters' to 'giftees' in the shortest possible code in bytes, such that the following conditions are met:

* Each name is paired with another, randomly selected, name from the input data (Note that it may not always be possible to randomise the output based on the provided conditions)
* Names will be provided with a list of flags that represent an adjacency matrix with the ordering consistent, so that column `n` refers to the same person as row `n`.
* If the conditions cannot be met, return something falsy in your language.
* If there are multiple solutions, your program must be able to generate them all if run many times.

You can assume you will never be presented with duplicate names as we need to be able to tell which family member is which, but you may be presented with data that includes spaces to differentiate `Bob Senior` from `Bob Junior`! It should complete all the supplied test cases within an hour for pretty large families, such as 100 unique names in the source data (please see the example data sets below, you must be able to parse all of these within the allocated time).

## Example input:

```
santa([
    ["Alice", 0, 0, 1, 1, 1, 1, 1],
    ["Bob",   0, 0, 0, 0, 0, 1, 0],
    ["Carla", 1, 1, 0, 0, 0, 1, 1],
    ["Dan",   1, 1, 0, 0, 0, 1, 1],
    ["Erin",  1, 1, 0, 0, 0, 1, 1],
    ["Frank", 1, 1, 1, 1, 1, 0, 1],
    ["Gary",  1, 1, 1, 1, 1, 1, 0]
]);
// might return something like:
[
    ["Alice", "Erin"],
    ["Bob", "Frank"],
    ["Carla", "Alice"],
    ["Dan", "Gary"],
    ["Erin", "Bob"],
    ["Frank", "Dan"],
    ["Gary", "Carla"]
]

```

```
santa([
    ["Alice", 0, 1, 1, 1, 0, 1],
    ["Bob",   0, 0, 1, 1, 0, 1],
    ["Carla", 0, 1, 0, 1, 0, 1],
    ["Dan",   0, 1, 1, 0, 0, 0],
    ["Erin",  0, 0, 1, 0, 0, 1],
    ["Frank", 1, 1, 1, 1, 1, 0]
]);
false

```

```
santa([
    ["Alice", 0, 1, 1],
    ["Bob",   1, 0, 1],
    ["Carla", 1, 1, 0]
]);
[
    ["Alice", "Bob"],
    ["Bob", "Carla"],
    ["Carla", "Alice"]
]

```

Depending on language, input can be in other formats, for instance details on `STDIN` *could* be provided as:

```
script <<< 'Alice,0,0,1,1,1,1,1
Bob,0,0,0,0,0,1,0
Carla,1,1,0,0,0,1,1
Dan,1,1,0,0,0,1,1
Erin,1,1,0,0,0,1,1
Frank,1,1,1,1,1,0,1
Gary,1,1,1,1,1,1,0'

```

Output can also be provided in any sensible format, whichever is easiest for your language. Acceptable formats include an array of arrays (as above) or perhaps a hash/`Object`/associative array or even just printing the parings to `STDOUT`:

```
Alice:Dan
Bob:Erin
Carla:Bob
Dan:Alice
Erin:Frank
Frank:Carla

```

If in doubt, please ask and provide examples of required input format and expected output format with your answer.

Reference JavaScript implementation.

Larger data sets: 100, 100, 200, 200 - many solutions, 200 - only one solution.

Reference implementation completes all these in \<4s on my machine.

Above sets generated with this script.

# Answer
# Javascript ES6, 191

This solution returns all possible pairings as a list of list of pairs:

```
f=l=>(h=l=>l.length,n=l.map(i=>i.shift()),o=[],(r=s=>(g=h(s))<h(n)?l[g].map((e,x)=>e&&r([...s,x])):o.push([...s]))([]),o.filter(i=>h([...new Set(i)])==h(n)).map(l=>l.map((t,f)=>[n[f],n[t]])))

```

Example run:

```
>> example = f([
    ["Alice", 0, 0, 1, 1, 1, 1, 1],
    ["Bob",   0, 0, 0, 0, 0, 1, 0],
    ["Carla", 1, 1, 0, 0, 0, 1, 1],
    ["Dan",   1, 1, 0, 0, 0, 1, 1],
    ["Erin",  1, 1, 0, 0, 0, 1, 1],
    ["Frank", 1, 1, 1, 1, 1, 0, 1],
    ["Gary",  1, 1, 1, 1, 1, 1, 0]])

<< Array [ Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], 26 more… ]

>> example[0]

<< Array [ "Alice:Carla", "Bob:Frank", "Carla:Alice", "Dan:Bob", "Erin:Gary", "Frank:Dan", "Gary:Erin" ]

```
> 3 votes

---
Tags: code-golf
---


# Question
Title: Find the results of the poll with the Borda count method
In a preference ballot there are many ways to decide who won. One of which is the Borda count method, where we give everyone point based on their places on the ballot.

For example, in these results:

```
  10  5  7  2
_____________
1  a  d  a  c
2  b  a  d  b
3  c  c  b  a
4  d  b  c  d

```

The results are

```
1: a : 87
2: d : 60
3: b : 55
4: c : 45

```

Because

```
4*10 is 40
5*3 is 15
7*4 is 28
2*2 is 4
40 + 15 + 28 + 4 is 87

```

Or is words: We give first place 4 points , second 3, third 2, etc.

So `a` is in first place 17 times, so they get 68 points then they get 15 points for being in second 5 times and 4 points for being in third 2 times for a total of 87 points.

Because this process is a pain, I need you write a program that finds the results for me, but since I have limited space on my PC, your program will have to be as small as possible.

## Your Challenge

Write a program or function the takes an input in this format

*```
Number of Ballots : placings, Number of Ballots : placings, Etc...

```*

and will output the results in this format:

```
1: a: 90
2: b: 80
Etc...

```

Rules:

This is Code Golf, so the shortest answer that does the task wins

Standard Loopholes Apply

Example:

```
Input:
3: A B C, 2: C B A, 1: C A B

Output:
1: A: 13
2: C: 12
3: B: 11

```

This is my first challenge, so please give me all the criticism you so desire, I won't take it offensively.

# Answer
# CJam, 78 bytes

```
q", "%{S%}%_0=,1-:L;{(1<i*}%e_W%L/L{)}%:C;{C.*}%e_$e`$W%C.+{W%{": "}%e_W(<N+}%

```

Try it Online.

Holy crap! How did I do this?

When I saw that CJam had a run length encode/decode function, I wondered why someone would use it. Today I found out. Essentially, what this program does is create a string containing each letter once for each vote. Then it sorts the string and uses run length encode to find out how many votes each letter got, and then formats the data.
> 1 votes

# Answer
# Python 2, 248 bytes

```
x={}
for a,b in[y.split(':')for y in raw_input().split(', ')]:
 for d,e in[(c,(len(b)/2-i)*int(a)) for i,c in enumerate(b[1::2])]:x[d]=x.setdefault(d,0)+e
for i,(f,g) in enumerate(sorted(x.items(),key=lambda t:-t[1]),1):print '%d: %s : %d'%(i,f,g)

```

Reads the from the standard input (for example, `echo '3: A B C, 2: C B A, 1: C A B' | python borda.py`).
> 2 votes

# Answer
# Perl 5, 131 bytes

```
for(split/, /,$ARGV[0]){($n,@v)=split/:? /;$s{$v[@v-$_]}+=$n*$_ for 1..@v}$,=": ";map{say++$i,"$_ ",$s{$_}}sort{$s{$b}<=>$s{$a}}@v

```

Use as `perl -E'the string above' 'the input string'`
> 1 votes

---
Tags: code-golf
---


title: The Traveling O

text:
# Question
Title: The Traveling O
The world is a five by five array of cells. **It wraps on all sides.** It can be visualized like...

```
XXXXX
XXXXX
XXOXX
XXXXX
XXXXX

```

You are an O. You love to travel the world, and you do so according to the following rules (let C be the current day):

* On prime days, you feel nostalgic. Return to where you started yesterday.
* On odd days, you feel homesick. Move one horizontal step closer to home, if possible, and one vertical step closer to home, if possible. Ignore world wrapping for the purpose determining closeness.
* On even days, you feel adventurous. Move C / 2 steps south.
* On square days, you feel adventurous. Move to the east wall.
* On Fibonacci days, the world expands southward by one row.
* On triangular days, the world expands eastward by one column.

If two or more of the above rules would apply at the same time, apply them in the order listed. For example, on an odd prime day, first return to where you started yesterday, and then move one step closer to home.

You live at the center of the (initial) world, i.e. position (2,2), zero-indexed from the Northwest corner. You begin your journey there on day one.

**Input**

A single integer, N.

**Output**

Your X and Y coordinate on the Nth day, zero-indexed from the Northwest corner, separated by a single space.

**Test Case With Explanation**

Given an input of `3`, the correct output is:

```
2 3

```

We can work through this one day at a time. Starting on day 1, we need to apply the following moves:

1. Odd, square, Fibonacci, and triangular
2. Prime, even, and Fibonacci
3. Prime, odd, Fibonacci, and triangular

In visual form:

```
     Day 1       Day 2       Day 3
XXXXX      XXXXXX      XXXXXX      XXXXXXX
XXXXX      XXXXXX      XXXXXX      XXXXXXX
XXOXX  ->  XXXXOX  ->  XXXXXX  ->  XXXOXXX
XXXXX      XXXXXX      XXOXXX      XXXXXXX
XXXXX      XXXXXX      XXXXXX      XXXXXXX
           XXXXXX      XXXXXX      XXXXXXX
                       XXXXXX      XXXXXXX
                                   XXXXXXX

```

**Additional Test Cases**

Courtesy of Martin Büttner's reference solution (please note that you should output only a single coordinate, not all of them):

```
Input:  1     2     3     4     5     6     7     8     9     10    11    12    13    14     15    16    17    18    19    20    21    22    23
Output: 4 2   2 3   3 2   6 4   2 2   2 5   2 2   2 6   7 5   7 0   6 4   6 0   5 3   5 10   4 9   9 6   3 8   3 6   2 7   2 6   2 5   2 4   2 4

```

This is code golf. The shortest submission wins.

# Answer
> 4 votes
## Pyth, ~~157~~ ~~156~~ 153 bytes

```
=Z=b5aYA,2 2FNtUhQI&!tPN<1NA@Y_2)Iq*2/N2NA,G%+H/N2b)EL-+b<b2<2bAyM,GH)J@N2Iq/NJJA,tZH)=TU2W<hTNIqNeT=hbBE=TX_T1sT))=J0W!<NJIqN/*JhJ2=hZBE=hJ))aY(GH;jd,GH

```

You can try it out here.

This was a fun problem to golf! I'm still getting used to Pyth, but it's a really great language.

# Answer
> 12 votes
# Haskell, 394 bytes

```
z=0<1
p d y c|all((0<).mod d)[2..d-1]=y|z=c
g x=x-signum(x-2)
e d(x,y)h|odd d=(g x,g y)|z=(x,mod(y+div d 2)h)
s d c@(_,y)w|d==(floor$sqrt$fromIntegral d)^2=(w-1,y)|z=c
f d a b m|b>d=m|b==d=(+1)<$>m|z=f d b(a+b)m
d%m@(w,h)|elem d[div(n*n-n)2|n<-[1..d+1]]=(w+1,h)|z=m
i=fst.c
j=snd.c
c d|d<1=((2,2),(5,5))|z=(s d(e d(p d(i$d-2)$i$d-1)$snd$j$d-1)$fst$j$d-1,d%(f d 1 1$j$d-1))
main=readLn>>=print.i

```

It can definitely be optimised and also after quickly checking for correctness ~~it looks like I'm getting different results than the one posted~~. I'll come back and check more thoroughly my code when I have more time ^^

Nice problem by the way!

EDIT: edited my solution taking into account the precious advice given by Zgarb. It now works perfectly!

EDIT2: thanks to nimi I have made the code even smaller. I am now also doing the checks for even and odd in one function instead of two which overall decreases the count from 446 to 414 bytes.

EDIT3: further improved from 414 to 400 bytes. Thanks nimi for another 2 bytes, you're on fire! :)

EDIT4: 4 more bytes by nimi :)

# Answer
> 5 votes
# C, ~~425~~ 396 bytes

```
typedef struct{int x,y,b,r}c;S,p,n;s(d){return(S=sqrt(d))*S==d;}c m(d){if(!d)return(c){2,2,4,4};c q,l=m(d-1);for(p=1,n=d;--n;p=p*n*n%d);if(p&&d>1)q=m(d-2),l.x=q.x,l.y=q.y;if(d%2)l.x-=l.x>2?1:l.x<2?-1:0,l.y-=l.y>2?1:l.y<2?-1:0;else l.y+=d/2,l.y=l.y>l.b?l.y-l.b-1:l.y;if(s(d))l.x=l.r;if(s(5*d*d+4)||s(5*d*d-4))l.b++;if(s(8*d+1))l.r++;return l;}main(i){scanf("%d",&i);printf("%d %d",m(i).x,m(i).y);}

```

There are parts to this that could be improved, but it works for the test cases.

---

## Explanation

```
typedef struct {
    int x,y,b,r
} c; //c will hold the information for each day

//determines if a number is a perfect square
S,p,n;
s(d) {
    return (S=sqrt(d))*S==d;
}

c m(d) {
    if(!d)
        return (c){2,2,4,4}; //returns the initial information if the day is 0

    c q,l=m(d-1); //gets the information for the previous day
    for (p=1,n=d;--n;p=p*n*n%d); //tests if the number is prime

    if (p&&d>1)
        q=m(d-2),l.x=q.x,l.y=q.y; //changes the position to what it was at the end of the day 2 days ago if the day is prime
    if (d%2)
        l.x-=l.x>2?1:l.x<2?-1:0,l.y-=l.y>2?1:l.y<2?-1:0; //moves the position towards (2,2) if the day is odd
    else
        l.y+=d/2,l.y=l.y>l.b?l.y-l.b-1:l.y; //moves down if the day is even
    if (s(d))
        l.x=l.r; //moves east if the day is a perfect square
    if (s(5*d*d+4)||s(5*d*d-4))
        l.b++; //expands world down if the day is a fibonacci number
    if (s(8*d+1))
        l.r++; //expands world right if the day is a triangular number
    return l;
}

main(i) {
    scanf("%d",&i);
    printf("%d %d",m(i).x,m(i).y);
}

```

# Answer
> 3 votes
# Perl 5, 284 bytes

```
@s=([2,2]);@n=(2,2);@f=(0,1);$w=$h=5;for(1..<>){$f[$_+1]=$f[$_]+$f[$_-1];$t[$_]=$_*($_+1)/2;$s[$_]=[@n];@n=@{$s[$_-1]}if(1 x$_)!~/^1$|^(11+?)\1+$/;($_%2)&&($n[0]-=($n[0]<=>2),$n[1]-=($n[1]<=>2))or$n[1]=($n[1]+$_/2)%$h;$n[0]=$w-1if(int sqrt$_)**2==$_;$h++if$_~~@f;$w++if$_~~@t}say"@n"

```

283 bytes, plus 1 for `-E` flag instead of `-e`

Same code but with more whitespace, more parentheses, and longer variable names:

```
@start=([2,2]);
@now=(2,2);
@fibonacci=(0,1);
$width = ($height=5);
for my $iterator (1 .. <>) {
  $fibonacci[$iterator+1] = $fibonacci[$iterator] + $fibonacci[$iterator-1];
  $triangular[$iterator] = $iterator * ($iterator+1) / 2;
  $start[$iterator] = [@now];
  @now = @{ $start[$iterator-1] } if ((1 x $iterator) !~ /^1$|^(11+?)\1+$/); # prime
  $now[0] -= ($now[0] <=> 2) , $now[1] -= ($now[1] <=> 2) if ($iterator % 2 != 0); # odd
  $now[1] = ($now[1] + $iterator / 2) % $height if ($iterator % 2 == 0); # even
  $now[0] = $width - 1 if ((int sqrt $iterator) ** 2 == $iterator); # square
  $height ++ if $iterator ~~ @fibonacci;
  $width ++ if $iterator ~~ @triangular;
}
say "@now";

```

I am confident that this can be golfed further.

# Answer
> 2 votes
# Javascript, 361 359 bytes

```
N=>{for(c=1,x=y=v=w=j=k=2,h=z=5;c<=N;c++,j=v,k=w,v=x,w=y){m=Math;p=(n,c)=>n%c!=0?c>=n-1?1:p(n,++c):0;[x,y]=c==2||p(c,2)&&c!=1?[j,k]:[x,y];p=x=>x+(x<2?1:x>2?-1:0);c%2?[x,y]=[p(x),p(y)]:y+=c/2;m.sqrt(c)==~~m.sqrt(c)?x=z-1:0;f=(n,c,d)=>d<c?0:d==c?1:f(c,n+c,d);f(1,2,c)||c==1?h++:0;t=(n,c)=>n*++n/2==c?1:--n*n/2>c?0:t(++n,c);t(1,c)?z++:0;x%=z;y%=h}return x+" "+y}

```

The code use Destructuring assignment. It's only supported in Firefox and Safari right now.

## Explanation

```
N=>{
// C => the day, x,y => position, v,w => position at the start of the day,
// j,k => position of yesterday
for(c=1,x=y=v=w=j=k=2,h=z=5;c<=N;c++,j=v,k=w,v=x,w=y){
    m=Math;

    // Prime Function for C > 2. Recursive call to save a loop.
    p=(n,c)=>n%c!=0?c>=n-1?1:p(n,++c):0;
    // Assign x and y to yesterday
    [x,y]=c==2||p(c,2)&&c!=1?[j,k]:[x,y];

    // Function to move closer to home
    p=x=>x+(x<2?1:x>2?-1:0);
    c%2?[x,y]=[p(x),p(y)]:y+=c/2;

    // Square check
    m.sqrt(c)==~~m.sqrt(c)?x=z-1:0;

    // Fibonnacci function for C > 1
    f=(n,c,d)=>d<c?0:d==c?1:f(c,n+c,d);
    f(1,2,c)||c==1?h++:0;

    // Triangle function
    t=(n,c)=>n*++n/2==c?1:--n*n/2>c?0:t(++n,c);
    t(1,c)?z++:0;

    // Stay in bounds
    x%=z;y%=h
}
// Output
return x+" "+y}

```

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


# Question
Title: Symmetric boolean functions as Zhegalkin polynomials
Let \\$\mathbb{B} = \mathbb{Z}\_2 = \\{0, 1\\}\\$ be the set of booleans. A *symmetric boolean function* in \\$n\\$ arguments is a function \\$f\_S : \mathbb{B}^n \to \mathbb{B}\\$ that checks if the number of its true arguments is in \\$S\\$, i. e. a function \\$f\_S\\$ such that

$$f\_S(\alpha\_1, \alpha\_2, \ldots, \alpha\_n) = \left(\sum\_{1 \le i \le n}\alpha\_{i}\right) \in S$$

or equivalently

$$f\_S(\alpha\_1, \alpha\_2, \ldots, \alpha\_n) = |\\{ i : \alpha\_i \\}| \in S. $$

These functions are called symmetric boolean function because they are all the boolean function that do not depend on argument order.

The set of boolean numbers forms a *field*, conventionally denoted \\$GF(2)\\$, where multiplication is logical and (\\$\wedge\\$) and addition is exclusive or (\\$\oplus\\$). This field has the properties that \\$-\alpha = \alpha\\$, \\$\alpha / \beta = \alpha \wedge \beta\\$ (for all \\$\beta \neq 0\\$), \\$\alpha \oplus \alpha = 0\\$ and \\$\alpha \wedge \alpha = \alpha\\$ for all \\$\alpha\\$ in addition to the field properties. For convenience, I am going to write \\$\oplus\\$ as \\$+\\$ and leave out \\$\wedge\\$ in the next paragraphs. For example, I will write \\$\alpha \oplus \beta \oplus \alpha \wedge \beta\\$ as \\$\alpha + \beta + \alpha\beta\\$.

Every boolean function can be expressed as a polynomial over the field of boolean numbers. Such a polynomial is called a *Zhegalkin polynomial,* the representation is canonical, i. e. there is exactly one polynomial that represents a given boolean function. Here are some examples for boolean functions and their corresponding Zhegalkin polynomials:

* \\$\alpha \vee \beta = \alpha + \beta + \alpha\beta\\$
* \\$\alpha \wedge \neg\beta = \alpha + \alpha\beta\\$
* \\$(\alpha \to \beta) \oplus \gamma = 1 + \alpha + \gamma + \alpha\beta\\$
* \\$\neg(\alpha \wedge \beta) \vee \gamma = 1 + \alpha\beta + \alpha\beta\gamma\\$
* \\$f\_{\\{1, 4\\}}(\alpha, \beta, \gamma, \delta) = \alpha + \beta + \gamma + \delta + \alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta + \alpha\beta\gamma\delta\\$
where the triple terms \\$(\alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta)\\$ are required because otherwise we would have \\$f(1,1,1,0) = 1\\$, and \\$3 \not\in \\{1, 4\\}\\$.

One observation we can make is that due to symmetry, the Zhegalkin polynomial for a symmetric boolean function always has the form

$$f\_S(\alpha\_1, \alpha\_2, \ldots, \alpha\_n) = \sum\_{i \in T\_{S,n}}t\_{n,i}$$

where \\$\sum\\$ denotes summation with exclusive or and \\$t\_{n, i}\\$ is the sum of all product terms that use \\$i\\$ out of the \\$n\\$ arguments to \\$f\_S\\$ and \\$T\_{S,n} \subseteq \\{0, 1, \ldots, n\\}\\$ is a set describing those \\$t\_{n, i}\\$ we need to construct \\$f\_S(\alpha\_1, \alpha\_2, \ldots, \alpha\_n)\\$. Here are some examples for \\$t\_{n, i}\\$ so you can get an idea what they look like:

* \\$t\_{4, 1} = \alpha + \beta + \gamma + \delta\\$
* \\$t\_{3, 2} = \alpha\beta + \alpha\gamma + \beta\gamma\\$
* \\$t\_{4, 4} = \alpha\beta\gamma\delta\\$
* for all \\$n\\$: \\$t\_{n, 0} = 1\\$

We can thus describe an \\$f\_S\\$ in \\$n\\$ arguments completely by \\$n\\$ and \\$T\_{S, n}\\$. Here are some test cases:

* \\$T\_{\\{1, 4\\}, 4} = \\{1, 3, 4\\}\\$
* \\$T\_{\\{2, 3, 4\\}, 4} = \\{2, 4\\}\\$
* \\$T\_{\\{2\\}, 4} = \\{2, 3\\}\\$
* \\$T\_{\\{1, 2\\}, 2} = \\{1, 2\\}\\$ (logical or)
* \\$T\_{\\{2, 3\\}, 3} = \\{2\\}\\$ (median function)

The task in this challenge is to compute \\$T\_{S, n}\\$ given \\$S\\$ and \\$n\\$. You can choose an appropriate input and output format as you like. This challenge is *code-golf,* the shortest solution in octets wins. As a special constraint, your solution must run in polynomial time \\$O(n^k)\\$ where \\$n\\$ is the \\$n\\$ from the input.

# Answer
> 7 votes
## Dyalog APL, 15 bytes

```
{2|⍺⌹⍉∘.!⍨0,⍳⍵}

```

Matrix division, basically. Takes input like `0 0 1 1 1 {2|⍺⌹⍉∘.!⍨0,⍳⍵} 4` for T4({2,3,4}).

```
{              }        Dyadic function:
              ⍵         Right argument          4
             ⍳          Index vector            1 2 3 4
           0,           Append 0                0 1 2 3 4
      ∘.                Outer product           ——————————
          ⍨             |With itself              1 0 0 0
        !               |By binomial coeff.       2 1 0 0
     ⍉                  Matrix transpose          3 3 1 0
                        Result at this step: ->   4 6 4 1
   ⍺                    Left argument
    ⌹                   Matrix division (A⌹B is A^-1 B, not A B^-1)
                        (implicitly converts ⍺ to column vector)
 2|                     Modulo 2

```

Since the transposed matrix of binomial coefficients is lower triangular with determinant 1, its inverse will only contain integers. So to matrix-divide over **F2** we can just matrix-divide over the reals, then mod by 2.

Matrix division is an O(n^3) operation, and calculating each of the O(N^2) binomial coefficients is well below O(n^3), so this runs in O(N^5).

Try it on TryAPL.

# Answer
> 1 votes
# R, 115 bytes

```
function(S,n)which(abs(solve(sapply(1:n,function(k)(sapply(1:n,function(j)choose(j,k)%%2))),is.element(1:n,S)))==1)

```

The key is realizing that the sum of t's that evaluate to a T value is just the choose function. A slightly ungolfed version that doesn't calculate in polynomial time is below, but illustrates the derivation of the t's a little better (just run the middle line).

```
function(S,n)which(abs(solve(
sapply(1:n,function(k)(sapply(1:n,function(j)sum(apply(combn(c(rep(T,j),rep(F,max(0,k-j))),k),2,all))%%2))),
is.element(1:n,S)))==1)

```

# Answer
> 1 votes
## CJam (25 24 bytes)

```
{_,{1$_,,2$~f&:!.*:^t}/}

```

This is an anonymous function which takes an array of `0` or `1` which serves as an indicator function for \\$S\\$ and returns an array of `0` or `1` which serves as an indicator function for \\$T\\$. E.g. to find \\$T\_{\\{1, 4\\}, 4}\\$ you pass `[0 1 0 0 1]` and it returns `[0 1 0 1 1]`.

Online demo

### Explanation

Recall that \\$t\_{n,i}\\$ is the sum of all product terms that use \\$i\\$ out of the \\$n\\$ arguments to \\$f\_S\\$. Suppose that \\$s\\$ of the \\$n\\$ arguments are true. Then we have three cases for \\$t\_{n,i}(\alpha\_0, \ldots, \alpha\_{n-1})\\$:

* \\$i \> s\\$ : none of the terms is true, so \\$t\_{n, i}(\alpha\_0, \ldots, \alpha\_{n-1}) = 0\\$
* \\$i = s\\$ : exactly one of the terms is true, so \\$t\_{n, i}(\alpha\_0, \ldots, \alpha\_{n-1}) = 1\\$
* \\$i \< s\\$ : there are \\$\binom{s}{i}\\$ terms which are true, so \\$t\_{n, i}(\alpha\_0, \ldots, \alpha\_{n-1}) = \binom{s}{i} \bmod 2\\$

If we let \\$\sigma\\$ be the indicator function for \\$S\\$ and \\$\tau\\$ be the indicator function for \\$T\_{S, n})\\$, we therefore get the matrix identity

$$\begin{pmatrix}1 & 0 & 0 & \ldots & 0 \\ \binom{1}{0} & 1 & 0 & \ldots & 0 \\ \binom{2}{0} & \binom{2}{1} & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & 0 \\ \binom{n}{0} & \binom{n}{1} & \binom{n}{2} & \ldots & 1 \end{pmatrix} \begin{pmatrix}\tau(0) \\ \tau(1) \\ \tau(2) \\ \vdots \\ \tau(n) \end{pmatrix} = \begin{pmatrix}\sigma(0) \\ \sigma(1) \\ \sigma(2) \\ \vdots \\ \sigma(n) \end{pmatrix} $$

which is dead easy to solve because the coefficient matrix is already in row-reduced echelon form.

Note that this is quite a well-known matrix, because it's the binomial coefficients modulo 2, which famously forms a Sierpiński triangle. I calculate them using Lucas' theorem and bit-twiddling as `2$~f&:!`

---
Tags: code-golf, math, number-theory, binary, restricted-complexity
---


title: Signal-Interrupting Quines

text:
# Question
Title: Signal-Interrupting Quines
Quining has a long history - if you haven't heard of it, click the tag and read up a little on it.

## Your Task

Output an infinite series of `1`s (with no other spacing \[newlines, spaces, etc.\]) UNTIL SIGINT (typically CTRL-C) is called. When it is called, output the program source.

## Rules

* It must be a valid quine:
* You may use any language.
* As this is a code golf, the shortest answer wins!

# Answer
> 4 votes
## Python 3, 76 bytes

```
s="while 1:\n try:print(end='1')\n except:-print('s=%r;exec(s)'%s)";exec(s)

```

Note that the byte count includes a trailing newline. This also uses `-print` to error out after quining.

# Answer
> 4 votes
# Pyth, 25 bytes

```
.xf!p1)jN*2]".xf!p1)jN*2]

```

A modification of the standard Pyth quine to add a try-except function.

# Answer
> 3 votes
# AutoIt, ~~488~~ ~~429~~ 362 bytes

My brain hurts, this is too meta.

```
$1=BinaryToString
$2=Chr(34)
$s="FileWrite('a','#include<Misc.au3>'&@LF&'Do'&@LF&'ToolTip(1)'&@LF&'Until _IsPressed(Chr(49)&Chr(66))')+RunWait(@AutoItExe&' a')"
Execute($s)
$x="$1=BinaryToString\n$2=Chr(34)\n%sExecute($s)\n$x=%s\nClipPut(StringFormat($x,$1(0x223D7324)&$s&$1(0x0A0D22),$2&$x&$2))"
ClipPut(StringFormat($x,$1(0x223D7324)&$s&$1(0x0A0D22),$2&$x&$2))

```

This is quite interesting in the way that it compiles a child-process which in return keeps outputting 1 to the ToolTip API until ESC is pressed. If ESC is pressed, the child process kills itself and the parent (this quine) resumes execution and dumps it's source *to the clipboard*. You have to run this from the editor.

BTW: This creates an auxiliary file 'a' on your disk.

# Answer
> 3 votes
# C, ~~239~~ ~~221~~ ~~206~~ 172 Bytes

Definitely could be a lot shorter, but I had to post something on PPCG *eventually*.

```
*s="*s=%c%s%c,r;h(s){r=1;}main(){signal(2,h);while(!r)printf(%c1%c);printf(s,34,s,34,34,34);}",r;h(s){r=1;}main(){signal(2,h);while(!r)printf("1");printf(s,34,s,34,34,34);}

```

Compiles with gcc 5.2.1 (with various warnings).

# Answer
> 1 votes
## Haskell, 206 bytes

```
import Control.Exception;main=catch(putStr o)e;o='1':o;e::SomeException->IO();e _=putStr(s++show s);s="import Control.Exception;main=catch(putStr o)e;o='1':o;e::SomeException->IO();e _=putStr(s++show s);s="

```

# Answer
> 1 votes
# C#, 339 Bytes

```
using d=System.Console;class c{static bool k=1>0;static void Main(){d.CancelKeyPress+=delegate{k=1<0;var s="using d=System.Console;class c{{static bool k=1>0;static void Main(){{d.CancelKeyPress+=delegate{{k=1<0;var s={0}{1}{0};d.WriteLine(s,(char)34,s);}};while(k){{d.Write(1);}}}}}}";d.WriteLine(s,(char)34,s);};while(k){d.Write(1);}}}

```

# Answer
> 1 votes
# Perl 5.10+, 64 bytes

```
perl -E '$_=q{$SIG{INT}=sub{say"\$_=q{$_};eval";die};{print 1;redo}};eval'

```

Requires Perl 5.10+ for `say`, which can be enabled with either `-M5.010` or `-E`.

## How it works

This is yet another variation of the following quine, which I seem to use on every quine challenge:

```
$_=q{say"\$_=q{$_};eval"};eval

```

Broken down:

```
perl -E '
    $_=q{                        # store contents of quine in $_
        $SIG{INT}=sub{           # install handler for SIGINT
            say"\$_=q{$_};eval"; # print quine
            die                  # break out of eval
        };
        {
            print 1;             # print "1"
            redo                 # restart block
        }
    };
    eval                         # eval $_, executing its contents as code
'

```

---
Tags: code-golf, quine
---


title: Will the tower balance?

text:
# Question
Title: Will the tower balance?
# Introduction

Given an ASCII tower and the force of the wind, write a program or function to determine if the tower will balance or which way it will fall.

For example the first tower balances but the second falls over toward the left.

```
  # #            # #
  ###            ###
 ###            ###
 # #            # #
#####          #####
 ###            ###
 ###              #

```

This is my first challenge. I hope you enjoy it.

# Directions

The tower consists of connected blocks represented by `#` and forms a rigid object. Each block is a square with a width and height of one unit and has a constant density. There are two forces that act on the tower, its weight and the wind force. All forces act on each block individually and pass through the center of the block.

* Due to its weight, each block has a downward force of one unit acting on it.
* Also, each block *that does not have another block adjacent to it on its windward side* has a force on it acting horizontally in the direction of the wind. The magnitude of this force is given as an input.
* The direction of the wind is indicated by an ASCII flag somewhere in the input. There will be a flag in the input if and only if the wind is not zero. The flag does not affect any forces.

The flag will look exactly as it appears below.

```
Flag design and corresponding wind direction:

 o~~        ~~o
 |~~        ~~|

--->        <---

```

To clarify, the tower is a solid object and will not break apart and is not attached to the ground. However, your program should calculate the forces for each block individually to determine whether the tower balances.

# Example

```
  o~~
  |~~
  # #              > >
  ###              >##
 ###              >##
 # #              > >
#####            >####
 ###              >##
 ###              >##

Wind force: 1    Wind direction: --->

```

The wind is blowing right and will push on the blocks shown with a `>` on the above right. Note that the wind acts on the inside of holes.

Assume the lower left corner of the tower has coordinates `(0,0)`. The moment around the left base of the tower at `(0,0)` is 71 units clockwise so the tower will not fall left. The moment around the right base of the tower at (0,3) is 8 units clockwise so the tower will fall right.

If the wind was blowing toward the left, the respective moments would be 2 units clockwise and 61 units counterclockwise at the same points, so the tower would balance.

# Input

* Your program or function must take two inputs, a decimal number and a newline-separated string.
* The decimal number will be greater than zero and represents the force exerted by the wind on each exposed block as in the example.
* The string will represent the tower from top to bottom and may contain spaces, `#|o~` characters, and newlines. You may optionally assume a trailing newline and/or pad the tower with trailing spaces to form a rectangle.
* The tower will have at least one `#` on the bottom row.
* You may input the number and string in either order.
* If the magnitude of the wind force is non-zero, there will be a flag somewhere in the input, either on the ground or connected to the tower. The flag will have the exact form shown above.
* The `#` blocks will form a connected shape that may contain holes. In other words, all blocks will be adjacent to another other block unless there is only one block.

# Output

* One of the characters `B`, `L`, or `R`, depending on whether the tower will balance, fall towards the left (counterclockwise), or fall towards the right (clockwise).
* The output may have an optional trailing newline.

This is ; standard rules and loopholes apply.

# `B` Test Cases:

```
Wind: 1
    ~~o
    ~~|
      # #
      ###
     ###
     # #
    #####
     ###
     ###

Wind: 0
##
# ##
###

Wind: 1.7
o~~
|~~
#
##

Wind: 0.768
      o~~
      |~~
      # #
      ###
     ###
     # #
    #####
     ###
     ###

Wind: 0.1
#
#
#
#
#
# o~~
# |~~

Wind: 0
#

Wind: 0
############

Wind: 144
               o~~
############   |~~

Wind: 0
#######
 ##
 #
 ##

Wind: 0
                ############
           ############
       ############
    ############
   ############
 ############
############

Wind: 41
                 ############
            ############
        ############
     ############
    ############
  ############     ~~o
 ############      ~~|

```

# `L` Test Cases:

```
Wind: 0
#####
   #

Wind: 42
                 ############
            ############
        ############
     ############
    ############
  ############     ~~o
 ############      ~~|

Wind: 4
########
    ###
 ~~o# ##
 ~~|#  #

Wind: 3
########
    ###
 o~~# ##
 |~~   #

```

# `R` Test Cases:

```
Wind: 1
      o~~
      |~~
      # #
      ###
     ###
     # #
    #####
     ###
     ###

Wind: 2
o~~
|~~
#

Wind: 0.001
                 ############
            ############
        ############
     ############
    ############
  ############     o~~
 ############      |~~

Wind: 145
               o~~
############   |~~

Wind: 1
#
#
#
#
#
# o~~
# |~~

Wind: 0.26
#######
 ##
 #   o~~
 ##  |~~

```

# Reference Solution (JavaScript)

Try it online.

```
function balanced(tower, wind) {
    var rows = tower.split('\n').reverse(); // Reverse so row index matches height of row.
    var height = rows.length;
    var leftEdge = rows[0].indexOf('#'); // Find bottom left corner of tower.
    var rightEdge = rows[0].lastIndexOf('#') + 1; // Find bottom right corner of tower.
    var leftMoment = 0, rightMoment = 0; // Moments around the bottoms corners of tower.
    wind *= tower.indexOf('~o')>-1 ? -1 : 1; // Find direction of the wind.

    // Sum the moments for each block in the tower.
    for (var i = height - 1; i >= 0; i--) {
        rows[i].split('').map(function(ch, index, arr) {
            if (ch=='#') {
                // If there's not a block toward the windward side of the current one.
                if ((wind < 0 && arr[index-1] != '#') || (wind > 0 && arr[index+1]!='#')) {
                    // Add moments from wind.
                    leftMoment += (i+0.5)*-wind;
                    rightMoment += (i+0.5)*-wind;
                }

                leftMoment += leftEdge - (index + 0.5);
                rightMoment += rightEdge - (index + 0.5);
            }
        }, 0);
    }
    if (leftMoment > 0) return 'L';
    else if (rightMoment < 0) return 'R';
    else return 'B';
}

```

# Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
var QUESTION_ID=62673,OVERRIDE_USER=45393;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# JavaScript (ES6), 239 bytes

I golfed down my reference implementation. I was able to save bytes by changing the for loop to a `map`, using `&&` and `||` to short-circuit if statements, and using the `,` operator to fit everything on one statement so as to avoid an explicit return in the function.

```
(a,b)=>((c=a.split`
`.reverse(),d=c[f=g=0].indexOf`#`,e=c[0].lastIndexOf`#`+1),a.match`o~`&&(b*=-1),c.map((h,i)=>h.replace(/#/g,(j,k,l)=>(b>0&l[k-1]!='#'|b<0&l[k+1]!='#'&&(f+=(i+=0.5)*b,g+=i*b),f+=d-k-0.5,g+=e-k-0.5))),f>0?'L':g<0?'R':'B')

```

It might still be possible to golf this more. Suggestions are welcome.
> 2 votes

# Answer
# JavaScript ES6, ~~297~~ 293 bytes

Basically a compressed version of the given implementation.

```
b=(n,e)=>{r=n.split`
`.reverse(),t=r.length,a=r[0].indexOf`#`,f=r[i=l=0].lastIndexOf`#`+1;e*=n.indexOf`~o`>-1?-1:1;for(d=t-1;d>=0;d--)r[d].split``.map((n,r,t)=>{(j="#")==n&&((0>e&&j!=t[r-1]||e>0&&j!=t[r+1])&&(i+=(d+.5)*-e,l+=(d+.5)*-e),i+=a-(r+.5),l+=f-(r+.5))},0);return i>0?"L":0>l?"R":"B"}

```

Semi-expanded:

```
b = (n, e) => {
    r = n.split `
`.reverse(), t = r.length, a = r[0].indexOf `#`, f = r[i = l = 0].lastIndexOf `#` + 1;
    e *= n.indexOf `~o` > -1 ? -1 : 1;
    for (d = t - 1; d >= 0; d--) r[d].split ``.map((n, r, t) => {
        (j = "#") == n && ((0 > e && j != t[r - 1] || e > 0 && j != t[r + 1]) && (i += (d + .5) * -e, l += (d + .5) * -e), i += a - (r + .5), l += f - (r + .5))
    }, 0);
    return i > 0 ? "L" : 0 > l ? "R" : "B"
}

```
> 1 votes

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


# Question
Title: How many decimals are there before I'd need to add 1 when rounding?
When you round a number, if the next digit is `>= 5` you add 1. For example:

```
3.1415926535 rounded to 1dp is 3.1
3.1415926535 rounded to 4dp is 3.1416    <-- Note the 5 changed to 6
3.1415926535 rounded to 5dp is 3.14159

3.1415926535 rounded to 9dp is 3.141592654  <-- Note the 3 changed to 4

```

You challenge is to receive an integer as input and output the number of decimal places before which you would have to round the square root of the number - i.e. the number of decimal places before anumber digit which is `>= 5` occurs.

The integer will be between 0 and 100,000 inclusive so for the edge case of 59752 you need to support 17 decimal points (to check the 17th).

If you programming language can't change the number of decimal points, you can display a "?" message to the user.

Example:

```
Input    Root                     Output

    5 -> 2.23 606797749979     -> 2
   41 -> 6.40312423 743284     -> 8      (Largest gap under 100)
  596 -> 24.4131112314 674     -> 10     (Largest gap under 1000)
59752 -> 244.44222221212112029 -> 16     (Largest gap under 100000)

```

Do what you want on perfect squares.

This is so shortest code wins.

---

For anyone interested, the number 310,617 is the biggest under 1,000,000 and has 18 before you reach a digit `>= 5`.

# Answer
> 2 votes
# CJam, 17 bytes

```
rie40mQsJ~>'4f>1#

```

Try it online.

# Answer
> 2 votes
# Pyth, 13 bytes

```
f<5e@=*QC\d2Z

```

Test suite

Start with `Q` equal to the input. At each time step, multiply `Q` by 100, calculated as `chr('d')`. Take its square root. Take this mod 10. If the result is greater than `5`, terminate. Print the number of iterations it took to terminate, 0-indexed.

In detail:

```
f<5e@=*QC\d2Z
                   Q = eval(input())
f           Z      Filter for the first truthy result over the infinite sequence
                   starting at Z (= 0)
     =*Q           Q *=
        C\d             chr('d') (= 100)
                   ---------------------
    @  Q   2          Q ^ (1/2)
   e                            % 10
 <5               5 <

```

# Answer
> 1 votes
# Mathematica 60 bytes

```
(Position[Drop@@RealDigits[N[Sqrt@#,99]],x_/;x>4][[1,1]]-1)&

```

---

**Example**

```
(Position[Drop@@RealDigits[N[Sqrt@#, 99]], x_ /; x > 4][[1, 1]] - 1) &[59752]

```

> 16

# Answer
> 1 votes
# CJam, ~~29~~ ~~26~~ 28 bytes

```
rimqs_'.+'.#)>{'5<}%0#]W'?er

```

Try it Online.

Puts a "?" if the number does not appear that can be rounded up (perfect square or too long).

# Answer
> 1 votes
## Pyth, 22 bytes

```
J`%@Q2 1x.e<\4@Jbr2lJ1

```

Explanation

```
                       - Autoassign Q to evaluated input
   @Q2                 - Get the square root of Q
J`%    1               - Get the stuff after the decimal point and put it in a string. Store in J
         .e      r2lJ  - Create a range between 2 and the length of the string (forget about the 0. bit) and enumerate over it
              @Jb      - Get the current decimal place
           <\4         - Is it bigger than 4
        x            1 - Find the position of the first True value

```

I'm absolutely certain this can be golfed. If the input doesn't have a digit higher than 4, it will print -1. Supports 17dp.

# Answer
> 1 votes
## Javascript, 59 bytes

```
f=a=>(a=/\.(.*?)[5-9]/.exec(Math.sqrt(a)),a?a[1].length:'?')

```

Returns `?` for 59752 because JavaScript only uses double precision.

# Answer
> 1 votes
# Linux shell, 52 bytes

```
dc -e'34k?vp'|cut -d. -f2|sed 's/.[5-9\s].*//'|wc -m

```

I tried for a pure `dc` solution, but failed. Precision is adjustable (first number).

As the OP kindly specifies that "you can do what you want on perfect squares", in this case this solution outputs the precision + 1, in this case 35.

# Answer
> -2 votes
# Ruby, 46 Bytes

This may not be valid, as it only fits 16 digits.

```
p (gets.to_i**0.5).to_s.split('.')[1]=~/[5-9]/

```

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


title: Build a poisoned wine testing scheduler

text:
# Question
Title: Build a poisoned wine testing scheduler
Recently at Puzzling.SE, there was a problem that I wrote about determining which two bottles out of a larger number are poisoned when the poison only activates if both components are drunk. It ended up being quite the ordeal, with most people managing to get it down to 18 or 19 prisoners using completely different algorithms.

The original problem statement is as follows:

> You are the ruler of a medieval kingdom who loves throwing parties. The courtier who tried to poison one of your wine bottles last time was furious to learn that you managed to identify which bottle he had poisoned out of 1,000 with just ten prisoners.
>
> This time he's a bit craftier. He's developed a **composite poison** `P`: a binary liquid that's only deadly when two individually harmless components mix; this is similar to how epoxy works. He's sent you another crate of 1,000 wine bottles. One bottle has component `C_a` and another one has component `C_b`. (`P = C_a + C_b`)
>
> Anyone who drinks both components will die on the stroke of midnight on the night they drank the final component, regardless of when in the day they imbibed the liquid. Each poison component stays in the body until the second component activates, so if you drink one component one day and another component the next, you will die on midnight at the end of the second day.
>
> You have two days before your next party. What is the minimum number of prisoners you need to use for testing in order to identify which two bottles are tainted, and what algorithm do you need to follow with that number of prisoners?
>
> ---
>
> **Bonus**
> Additionally, suppose that you had a fixed limit of 20 prisoners at your disposal, what's the maximum number of bottles you could theoretically test and come to an accurate conclusion about which bottles were affected?

Your task is to build a program to solve the bonus problem. Given `n` prisoners, your program will devise a testing schedule that will be able to detect the two poisoned bottles among `m` bottles, where `m` is as large as possible.

Your program will initially take as input the number `N`, the number of prisoners. It will then output:

* `M`, the number of bottles you will attempt to test. These bottles will be labelled from `1` to `M`.
* `N` lines, containing the labels of the bottles each prisoner will drink.

Your program will then take as input which prisoners died on the first day, with the prisoner on the first line being `1`, the next line being `2`, etc. Then, it will output:

* `N` more lines, containing the labels of the bottles each prisoner will drink. Dead prisoners will have blank lines.

Your program will then take as input which prisoners died on the second day, and output two numbers, `A` and `B`, representing which two bottles your program thinks contains the poison.

An example input for two prisoners and four bottles might go as such, if bottles `1` and `3` are poisoned:

```
> 2      // INPUT: 2 prisoners
4        // OUTPUT: 4 bottles
1 2 3    // OUTPUT: prisoner 1 will drink 1, 2, 3
1 4      // OUTPUT: prisoner 2 will drink 1, 4
> 1      // INPUT: only the first prisoner died
         // OUTPUT: prisoner 1 is dead, he can't drink any more bottles
3        // OUTPUT: prisoner 2 drinks bottle 3
> 2      // INPUT: prisoner 2 died
1 3      // OUTPUT: therefore, the poisoned bottles are 1 and 3.

The above algorithm may not actually work in all
cases; it's just an example of input and output.

```

Your program's testing schedule must successfully determine each possible pair of poisoned bottles in order for it to be a valid submission.

Your program will be scored on the following criteria, in order:

* The maximum number of bottles it can discern for the case `N = 20`.
* The number of bottles for the case `N = 21`, and successively higher cases after that.
* The length of code. (Shorter code wins.)

# Answer
# **Python 2.7.9 — 21 bottles**

Assuming that ESultanik's speculation is right on what the input is when multiple prisoners die

```
r=raw_input;s=str;j=s.join;p=int(r());z=range;q=z(p);x=z(p+1)
print s(p+1)+"\n"+j("\n",(j(" ",(s(a) for a in x if a!=b)) for b in q))
v=r().split();d=[s(a) for a in q if s(a) not in v];d+=[p]if len(d)==1 else [];
print "\n"*p,;r();print j(" ",[s(a) for a in d])

```

Algorithm: every prisoner drinks from every bottle except their number (1st prisoner doesn't drink first bottle). If they don't die, their number bottle is poisoned. If only one prisoner survives, the extra bottle is poisoned.
> 6 votes

# Answer
# Perl 5, 66 bottles

## (72 bottles for 21 prisoners)

The prisoners are divided optimally into 2 groups. The bottles are grouped in sets.

Each prisoner of group 1 will drink from all sets except for one. There will be 1 or 2 survivors. The 1 or 2 sets that weren't drank by them will continue to day 2.

On day 2 the remaining prisoners (including the survivors) drink from all remaining bottles except for one.
When 2 prisoners survive then the bottles they didn't drink are poisoned.
If only 1 prisoner remains then the bottle they all drank is also suspicious.

The code includes extra functionality to facilitate testing. When the poisened bottles are added as additional parameters, then it won't ask for input about who died.

```
($p,$f,$l)=@ARGV;
$p=9if!$p;
$m=$p-(2*int($p/4))+1;
$n=$p-$m+2;
$b=$m*(($n+1)/2);
@M=(1..$m);
print"Prisoners: $p\nBottles: $b\n";
# building the sets of items
for$x(@M){
    $j=$k+1;$k+=($n+1)/2;
    $s=join",",($j..$k);
    $A[$x]=$s
}
# assigning the sets to the actors
for$x(@M){
    @T=();
    for$j(@M){if($x!=$j){push@T,split/,/,$A[$j]}}
    print"Prisoner $x drinks @T\n";
    $B[$x]=join",",@T
}
if(!$f||!$l){
    # manual input
    print"Who dies: ";
    $_=<STDIN>;chomp;
    @D=split/ /;
    %h=map{($_,1)}@D;
    @S=grep{!$h{$_}}(@M)
}
else{
    # calculate who dies based on the parameters
    for$x(@M){
        $d=0;
        map{if($_==$f||$_==$l){$d++}}split/,/,$B[$x];
        if($d>1){push@D,$x}else{push@S,$x}
    }
}
for(@D){print"Prisoner $_ dies\n"}

# calculate the remaining items
for(@S){push@R,split/,/,$A[$_]}@R=sort{$a<=>$b}grep{!$g{$_}++}@R;

# different set of actors if there were 1 or 2 sets remaining
if(@S>1){@S=($S[0],$m+1..$p,$S[1],0)}else{@S=($m+1..$p)};

$i=0;@B=@D=();
# assign an item to each actor
for$x(@S){
    @T=();
    for($j=0;$j<@R;$j++){
        if($i!=$j){push@T,$R[$j]}
    }$i++;
    print"Prisoner $x drinks @T\n"if$x>0;
    $B[$x]=join",",@T
}

if(!$f||!$l){
    # manual input
    print"Who dies: ";
    $_=<STDIN>;chomp;
    @D=sort split/ /;
    if(@D<@S-1){push@D,0} # because the set that noone drinks isn't manually put in
    %h=map{($_,1)}@D;
    @L=grep{!$h{$_}}(@S);
}
else{
    # calculate who dies based on the parameters
    @D=();
    for$x(@S){
        $d=0;
        map{if($_==$f||$_==$l){$d++}}split/,/,$B[$x];
        if($d>1){push@D,$x}else{push@L,$x}
    }
}

for(@D){print"Prisoner $_ dies\n"if$_>0}

# calculate the remaining items
for(@L){push@F,split/,/,$B[$_]}
map{$c{$_}++}@F;
for(keys%c){push(@Z,$_)if$c{$_}==1}
@R=sort{$a<=>$b}@Z;

print"Suspected bottles: @R"

```

## Test

```
$ perl poisened_bottles.pl 20
Prisoners: 20
Bottles: 66
Prisoner 1 drinks 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 2 drinks 1 2 3 4 5 6 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 3 drinks 1 2 3 4 5 6 7 8 9 10 11 12 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 4 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 5 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 6 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 7 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 8 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 9 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 10 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 61 62 63 64 65 66
Prisoner 11 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
Who dies: 2 3 4 5 6 7 8 9 10
Prisoner 2 dies
Prisoner 3 dies
Prisoner 4 dies
Prisoner 5 dies
Prisoner 6 dies
Prisoner 7 dies
Prisoner 8 dies
Prisoner 9 dies
Prisoner 10 dies
Prisoner 1 drinks 2 3 4 5 6 61 62 63 64 65 66
Prisoner 12 drinks 1 3 4 5 6 61 62 63 64 65 66
Prisoner 13 drinks 1 2 4 5 6 61 62 63 64 65 66
Prisoner 14 drinks 1 2 3 5 6 61 62 63 64 65 66
Prisoner 15 drinks 1 2 3 4 6 61 62 63 64 65 66
Prisoner 16 drinks 1 2 3 4 5 61 62 63 64 65 66
Prisoner 17 drinks 1 2 3 4 5 6 62 63 64 65 66
Prisoner 18 drinks 1 2 3 4 5 6 61 63 64 65 66
Prisoner 19 drinks 1 2 3 4 5 6 61 62 64 65 66
Prisoner 20 drinks 1 2 3 4 5 6 61 62 63 65 66
Prisoner 11 drinks 1 2 3 4 5 6 61 62 63 64 66
Who dies: 1 12 14 15 16 17 18 20 11
Prisoner 1 dies
Prisoner 11 dies
Prisoner 12 dies
Prisoner 14 dies
Prisoner 15 dies
Prisoner 16 dies
Prisoner 17 dies
Prisoner 18 dies
Prisoner 20 dies
Suspected bottles: 3 63

```

## Test without manual input

```
$ perl poisened_bottles.pl 7 2 5
Prisoners: 7
Bottles: 12
Prisoner 1 drinks 3 4 5 6 7 8 9 10 11 12
Prisoner 2 drinks 1 2 5 6 7 8 9 10 11 12
Prisoner 3 drinks 1 2 3 4 7 8 9 10 11 12
Prisoner 4 drinks 1 2 3 4 5 6 9 10 11 12
Prisoner 5 drinks 1 2 3 4 5 6 7 8 11 12
Prisoner 6 drinks 1 2 3 4 5 6 7 8 9 10
Prisoner 2 dies
Prisoner 4 dies
Prisoner 5 dies
Prisoner 6 dies
Prisoner 1 drinks 2 5 6
Prisoner 7 drinks 1 5 6
Prisoner 3 drinks 1 2 6
Prisoner 1 dies
Suspected bottles: 2 5

```
> 3 votes

# Answer
As is tradition, I will post a last-place reference answer.

# Python — 7 bottles

```
prisoners = int(raw_input())

bottles = 0
while (bottles * (bottles + 1) / 2 - 1) <= prisoners:
    bottles += 1

print bottles

pairs = []
for i in range(bottles):
    for j in range(i + 1, bottles):
        pairs += [str(i + 1) + " " + str(j + 1)]

for i in range(prisoners):
    if i < len(pairs):
        print pairs[i]
    else:
        print

dead_prisoner = raw_input()

for i in range(prisoners):
    print
raw_input() # discard the second day entirely

if dead_prisoner == "":
    print pairs[-1]
else:
    print pairs[int(dead_prisoner) - 1]

```

Make each prisoner drink one possible pair of bottles except for the pair of the last two. If any prisoner dies, the pair that that prisoner drank were the poisoned ones. Otherwise, it was the last two bottles that were poisoned.

For allotments of at least `n(n-1)/2 - 1` prisoners, you can do up to `n` bottles. For `n = 7`, this lower limit is `20`.

We only actually need *one* day for this solution to work. A two-day solution with a similar scope might get up to 20 bottles for `N = 20`, but it's too much work for a trivial answer.
> 2 votes

---
Tags: code-challenge, puzzle-solver
---