title: Be an Epidemiologist!

text:
# Question
Title: Be an Epidemiologist!
## Challenge

You must create a simple model of how disease spreads around a group of people.

## Rules and Requirements

The model must be a 1000 by 1000 2D array with each element being a different person.

The user must input three variables using argv: the probability of transmission (how likely someone is going to infect someone else), chance of mutation and how many periods the simulation should run for.

In the first period (`t=0`), four people should be chosen randomly and infected with the disease.

The way the disease behaves is governed by the following rules:

* The disease can only move vertically and horizontally, moving to the person next door.
* The infection last for 3 periods in every person. You may not factor in immunodeficiencies.
* After a person has been infected three times, they are immune and cannot be infected again.
* The disease is subject to mutation making the previously immune people vulnerable to this new mutated disease. The mutated disease has exactly the same traits and follows the same rules as the original disease.
* If a mutation occurs, the whole disease does not change, just that particular 'packet' upon transmission.
* Once a person has been been infected by one virus, they cannot be infected again until the current infection passes.
* If a person is infected, they are infectious from the start of their infection period to its end.
* There are no levels of immunity - a person is either immune or not.
* To stop memory overload, there is a maximum limit of 800 mutations.

At the end of the specified number of periods, you should output the results.

The results must be a 1000 x 1000 grid showing which people are infected and which people are not. This can be output as a text file, as an image file or graphical output (where #FFFFFF is a healthy person and #40FF00 is an infected person).

Please can you include the language name and a command to run it in your answer.

## Winning

The fastest code to run on my computer wins. Its time will be measured with the following piece of Python code:

```
import time, os
start = time.time()
os.system(command)
end = time.time()
print(end-start)

```

Note that when running this script, I will use the following defaults:

```
Probability of transmission = 1
Chance of mutation = 0.01
Number of periods = 1000

```

# Answer
I was curious what this would look like so I made this quick and dirty hack in JavaScript: http://jsfiddle.net/andrewmaxwell/r8m54t9c/

```
// The probability that a healthy cell will be infected by an adjacent infected cell EACH FRAME.
var infectionProbability = 0.2

// The probability that the infection will mutate on transmission EACH FRAME.
var mutationProbability = 0.00001

// The maximum number of times a cell can be infected by the same infection.
var maxInfections = 3

// The number of frames a cell in infected before it becomes healthy again.
var infectionDuration = 3

// The width and heigh of the board
var size = 400

// The number of cells infected at the beginning.
var startingNum = 4

var imageData, // the visual representation of the board
    cells, // array of cells
    infectionCount // counter that is incremented whenever a mutation occurs

// Just some colors. The colors are re-used as the number of mutations increases.
var colors = [[255,0,0],[255,255,0],[0,255,0],[0,255,255],[0,0,255],[255,0,255],[128,0,0],[128,128,0],[0,128,0],[0,128,128],[0,0,128],[128,0,128],[255,128,128],[255,255,128],[128,255,128],[128,255,255],[128,128,255],[255,128,255]
]

// when a cell is infected, it isn't contagious until the next frame
function infect(person, infection){
    person.infect = true
    person.infectionCounts[infection] = (person.infectionCounts[infection] || 0) + 1
    person.currentInfection = infection
}

// when a mutation occurs, it is given a number and the counter is incremented
function mutation(){
    return infectionCount++
}

function reset(){

    cells = []
    infectionCount = 0
    imageData = T.createImageData(size, size)

    // initialize the cells, store them in a grid temporarily and an array for use in each frame
    var grid = []
    for (var i = 0; i < size; i++){
        grid[i] = []
        for (var j = 0; j < size; j++){
            cells.push(grid[i][j] = {
                infectionTime: 0, // how many frames until they are no longer infected, so 0 is healthy
                infectionCounts: [], // this stores how many times the cell has been infected by each mutation
                neighbors: [] // the neighboring cells
            })
        }
    }

    // store the neighbors of each cell, I just want to minimize the work done each frame
    var neighborCoords = [[0,-1],[1,0],[0,1],[-1,0]]
    for (var i = 0; i < size; i++){
        for (var j = 0; j < size; j++){
            for (var n = 0; n < neighborCoords.length; n++){
                var row = i + neighborCoords[n][0]
                var col = j + neighborCoords[n][1]
                if (grid[row] && grid[row][col]){
                    grid[i][j].neighbors.push(grid[row][col])
                }
            }
        }
    }

    // infect the initial cells
    for (var i = 0; i < startingNum; i++){
        infect(cells[Math.floor(cells.length * Math.random())], 0)
    }
}

function loop(){
    requestAnimationFrame(loop)

    // for each cell marked as infected, set its infectionTime
    for (var i = 0; i < cells.length; i++){
        var p = cells[i]
        if (p.infect){
            p.infect = false
            p.infectionTime = infectionDuration
        }
    }

    for (var i = 0; i < cells.length; i++){
        var p = cells[i]

        // for each infected cell, decrement its timer
        if (p.infectionTime){
            p.infectionTime--

            // for each neighbor that isn't infected, if the probability is right and the neighbor isn't immune to that infection, infect it
            for (var n = 0; n < p.neighbors.length; n++){
                var neighbor = p.neighbors[n]
                if (!neighbor.infectionTime && Math.random() < infectionProbability){
                    var infection = Math.random() < mutationProbability ? mutation() : p.currentInfection
                    if (!neighbor.infectionCounts[infection] || neighbor.infectionCounts[infection] < maxInfections){
                        infect(neighbor, infection)
                    }
                }
            }

            // colors! yay!
            var color = colors[p.currentInfection % colors.length]
            imageData.data[4 * i + 0] = color[0]
            imageData.data[4 * i + 1] = color[1]
            imageData.data[4 * i + 2] = color[2]
        } else {
            imageData.data[4 * i + 0] = imageData.data[4 * i + 1] = imageData.data[4 * i + 2] = 0
        }

        imageData.data[4 * i + 3] = 255
    }

    T.putImageData(imageData, 0, 0)
}

// init canvas and go
C.width = C.height = size
T = C.getContext('2d')
reset()
loop()

```
> 10 votes

# Answer
# C++11, 6-8 minutes

My test run takes about 6-8 minutes in my Fedora 19, i5 machine. But due to the randomness of the mutation, it might as well be faster or take longer than that. I think the scoring criteria needs to be readdressed.

Prints the result as text at the end of completion, healthy person denoted by dot (`.`), infected person by asterisk (`*`), unless `ANIMATE` flag is set to true, in which case it will display different characters for people infected with different virus strain.

Here is a GIF for 10x10, 200 periods.

## Mutation behaviour

Each mutation will give new strain never seen before (so it is possible that one person infects the four neighboring people with 4 distinct strains), unless 800 strains have been generated, in which case no virus will go any further mutation.

The 8-minute result comes from the following number of infected people:

```
Period   0, Infected:      4
Period 100, Infected:  53743
Period 200, Infected: 134451
Period 300, Infected: 173369
Period 400, Infected: 228176
Period 500, Infected: 261473
Period 600, Infected: 276086
Period 700, Infected: 265774
Period 800, Infected: 236828
Period 900, Infected: 221275

```

while the 6-minute result comes from the following:

```
Period   0, Infected:      4
Period 100, Infected:  53627
Period 200, Infected: 129033
Period 300, Infected: 186127
Period 400, Infected: 213633
Period 500, Infected: 193702
Period 600, Infected: 173995
Period 700, Infected: 157966
Period 800, Infected: 138281
Period 900, Infected: 129381

```

## Person representation

Each person is represented in 205 bytes. Four bytes to store the virus type this person is contracting, one byte to store how long has this person been infected, and 200 bytes to store how many times he has contracted each strain of virus (2 bit each). Perhaps there are some additional byte-alignment done by C++, but the total size will be around 200MB. I have two grids to store the next step, so total it uses around 400MB.

I store the location of infected people in a queue, to cut the time required in the early periods (which is really useful up to periods \< 400).

## Program technicalities

Every 100 steps this program will print the number of infected people, unless `ANIMATE` flag is set to `true`, in which case it will print the whole grid every 100ms.

This requires C++11 libraries (compile using `-std=c++11` flag, or in Mac with `clang++ -std=c++11 -stdlib=libc++ virus_spread.cpp -o virus_spread`).

Run it without arguments for the default values, or with arguments like this:

`./virus_spread 1 0.01 1000`

```
#include <cstdio>
#include <cstring>
#include <random>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <deque>
#include <cmath>
#include <functional>
#include <unistd.h>

typedef std::pair<int, int> pair;
typedef std::deque<pair> queue;

const bool ANIMATE = false;
const int MY_RAND_MAX = 999999;

std::default_random_engine generator(time(0));
std::uniform_int_distribution<int> distInt(0, MY_RAND_MAX);
auto randint = std::bind(distInt, generator);
std::uniform_real_distribution<double> distReal(0, 1);
auto randreal = std::bind(distReal, generator);

const int VIRUS_TYPE_COUNT = 800;
const int SIZE = 1000;
const int VIRUS_START_COUNT = 4;

typedef struct Person{
    int virusType;
    char time;
    uint32_t immune[VIRUS_TYPE_COUNT/16];
} Person;

Person people[SIZE][SIZE];
Person tmp[SIZE][SIZE];
queue infecteds;

double transmissionProb = 1.0;
double mutationProb = 0.01;
int periods = 1000;

char inline getTime(Person person){
    return person.time;
}

char inline getTime(int row, int col){
    return getTime(people[row][col]);
}

Person inline setTime(Person person, char time){
    person.time = time;
    return person;
}

Person inline addImmune(Person person, uint32_t type){
    person.immune[type/16] += 1 << (2*(type % 16));
    return person;
}

bool inline infected(Person person){
    return getTime(person) > 0;
}

bool inline infected(int row, int col){
    return infected(tmp[row][col]);
}

bool inline immune(Person person, uint32_t type){
    return (person.immune[type/16] >> (2*(type % 16)) & 3) == 3;
}

bool inline immune(int row, int col, uint32_t type){
    return immune(people[row][col], type);
}

Person inline infect(Person person, uint32_t type){
    person.time = 1;
    person.virusType = type;
    return person;
}

bool inline infect(int row, int col, uint32_t type){
    auto person = people[row][col];
    auto tmpPerson = tmp[row][col];
    if(infected(tmpPerson) || immune(tmpPerson, type) || infected(person) || immune(person, type)) return false;
    person = infect(person, type);
    infecteds.push_back(std::make_pair(row, col));
    tmp[row][col] = person;
    return true;
}

uint32_t inline getType(Person person){
    return person.virusType;
}

uint32_t inline getType(int row, int col){
    return getType(people[row][col]);
}

void print(){
    for(int row=0; row < SIZE; row++){
        for(int col=0; col < SIZE; col++){
            printf("%c", infected(row, col) ? (ANIMATE ? getType(row, col)+48 : '*') : '.');
        }
        printf("\n");
    }
}

void move(){
    for(int row=0; row<SIZE; ++row){
        for(int col=0; col<SIZE; ++col){
            people[row][col] = tmp[row][col];
        }
    }
}

int main(const int argc, const char **argv){
    if(argc > 3){
        transmissionProb = std::stod(argv[1]);
        mutationProb = std::stod(argv[2]);
        periods = atoi(argv[3]);
    }
    int row, col, size;
    uint32_t type, newType=0;
    char time;
    Person person;
    memset(people, 0, sizeof(people));
    for(int row=0; row<SIZE; ++row){
        for(int col=0; col<SIZE; ++col){
            people[row][col] = {};
        }
    }
    for(int i=0; i<VIRUS_START_COUNT; i++){
        row = randint() % SIZE;
        col = randint() % SIZE;
        if(!infected(row, col)){
            infect(row, col, 0);
        } else {
            i--;
        }
    }
    move();
    if(ANIMATE){
        print();
    }
    for(int period=0; period < periods; ++period){
        size = infecteds.size();
        for(int i=0; i<size; ++i){
            pair it = infecteds.front();
            infecteds.pop_front();
            row = it.first;
            col = it.second;
            person = people[row][col];
            time = getTime(person);
            if(time == 0) continue;
            type = getType(person);
            if(row > 0 && randreal() < transmissionProb){
                if(newType < VIRUS_TYPE_COUNT-1 && randreal() < mutationProb){
                    newType++;
                    if(!infect(row-1, col, newType)) newType--;
                } else {
                    infect(row-1, col, type);
                }
            }
            if(row < SIZE-1 && randreal() < transmissionProb){
                if(newType < VIRUS_TYPE_COUNT-1 && randreal() < mutationProb){
                    newType++;
                    if(!infect(row+1, col, newType)) newType--;
                } else {
                    infect(row+1, col, type);
                }
            }
            if(col > 0 && randreal() < transmissionProb){
                if(newType < VIRUS_TYPE_COUNT-1 && randreal() < mutationProb){
                    newType++;
                    if(!infect(row, col-1, newType)) newType--;
                } else {
                    infect(row, col-1, type);
                }
            }
            if(col < SIZE-1 && randreal() < transmissionProb){
                if(newType < VIRUS_TYPE_COUNT-1 && randreal() < mutationProb){
                    newType++;
                    if(!infect(row, col+1, newType)) newType--;
                } else {
                    infect(row, col+1, type);
                }
            }
            time += 1;
            if(time == 4) time = 0;
            person = setTime(person, time);
            if(time == 0){
                person = addImmune(person, type);
            } else {
                infecteds.push_back(std::make_pair(row, col));
            }
            tmp[row][col] = person;
        }
        if(!ANIMATE && period % 100 == 0) printf("Period %d, Size: %d\n", period, size);
        move();
        if(ANIMATE){
            printf("\n");
            print();
            usleep(100000);
        }
    }
    if(!ANIMATE){
        print();
    }
    return 0;
}

```
> 7 votes

# Answer
# C# 6-7 Minutes

# Edit 2

I've finally(5 hours) generated a verbose output for close to 1000 periods(only 840 frames then it crashed) at 1000x1000, every 1 period, however its close to 160MB and requires all the memory on my system to display(IrfanView), not even sure that would work in a browser, may I'll put it up later.

# EDIT

I've spent allot of time on making this more efficient per "Beta Decay"s answer stating "Choose the strain randomly" I have choosin only the random method for choosing who infects who per period, however I've changed the way that's calculated and threaded out every thing, I've updated my posts with the new details.

Coded my closest estimation to this I could, I hope it follows all the rules, it uses a ton of memory on my system(about 1.2GB). The program can output animated gifs(looks cool, really slow) or just a image matching "Beta Decay"s specs. This is a little bit of reinventing the wheel, but definitely looks cool:

---

# Results

(Note: this only differentiates between infected and non infected, ie non-verbose)

## 1000 Periods, 1% Mutation Rate, 100% Spread:

# Examples(Verbose)

Anyway using 100% "Probability of transmission" in non-verbose mode is kind of boring as you always get the same shapes and you can't see the different mutations, if you tweak the parameters around a-bit(and enable verbose mode) you get some cool looking output(animated GIFs display every 10th frame):

## Random - Grid Size: 200, ProbTransmission: 100%, ProbMutation: 1%

## Random - Grid Size: 200, ProbTransmission: 20%, ProbMutation: 1%

# Scoring

I agree with "justhalf" that the scoring criteria may not be fair as every run will differ due to the randomness of mutations and position of random start points. Maybe we could do average of several runs or something like that..., well anyway this is in C# so bounty for me :( anyway.

# Code

Make sure to include the MagickImage library(set to compile x64 bit) otherwise it won't build(http://pastebin.com/vEmPF1PM):

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Drawing;
using System.Drawing.Imaging;
using ImageMagick;
using System.IO;

namespace Infection
{
    class Program
    {
        #region Infection Options
        private const double ProbabilityOfTransmission = .2;
        private const double ChanceOfMutation = 0.01;
        private const Int16 StageSize = 1000;
        private const Int16 MaxNumberOfMutations = 800;
        private const byte MaxInfectionTime = 3;
        private const byte NumberOfPeopleToRandomlyInfect = 4;
        private static int NumberOfPeriods = 1000;
        #endregion Infection Options

        #region Run Options
        private const bool VerbosMode = false;
        private const int ImageFrequency = 10;
        #endregion Run Options

        #region Stage
        private static Int16 MutationNumber = 1;

        private class Person
        {
            public Person()
            {
                PreviousInfections = new Dictionary<Int16, byte>();
                InfectionTime = 0;
                CurrentInfection = 0;
                PossibleNewInfections = new List<short>(4);
            }
            public Dictionary<Int16, byte> PreviousInfections { get; set; }
            public byte InfectionTime { get; set; }
            public Int16 CurrentInfection { get; set; }
            public List<Int16> PossibleNewInfections { get; set; }
        }
        private static Person[][] Stage = new Person[StageSize][];
        #endregion Stage

        static void Main(string[] args)
        {
            DateTime start = DateTime.UtcNow;

            //Initialize stage
            for (Int16 i = 0; i < Stage.Length; i++)
            {
                var tmpList = new List<Person>();
                for (Int16 j = 0; j < Stage.Length; j++)
                    tmpList.Add(new Person());
                Stage[i] = tmpList.ToArray();
            }

            //Randomly infect people
            RandomlyInfectPeople(NumberOfPeopleToRandomlyInfect);

            //Run through the periods(NumberOfPeriods times)
            List<MagickImage> output = new List<MagickImage>();
            while (NumberOfPeriods > 0)
            {
                //Print details(verbose)
                if (VerbosMode && NumberOfPeriods % ImageFrequency == 0)
                {
                    Console.WriteLine("Current Number: " + NumberOfPeriods);
                    Console.WriteLine("Current Mutation: " + MutationNumber);
                    output.Add(BoardToImage());
                }

                Period();
            }

            //Outputs a Animated Gif(verbose)
            if (VerbosMode)
            {
                ImagesToAnimatedGIF(output.ToArray(), Directory.GetCurrentDirectory() + "\\Output.gif");
                System.Diagnostics.Process.Start(Directory.GetCurrentDirectory() + "\\Output.gif");
            }
            //Only outputs the basic result image matching the specs
            SaveBoardToSimpleImage(Directory.GetCurrentDirectory() + "\\FinalState.gif");

            Console.WriteLine("Total run time in seconds: " + (DateTime.UtcNow - start).TotalSeconds);
            Console.WriteLine("Press enter to exit");
            Console.ReadLine();
        }

        #region Image
        private static void SaveBoardToSimpleImage(string filepath)
        {
            using (Bitmap img = new Bitmap(StageSize, StageSize))
            {
                for (int i = 0; i < img.Width; i++)
                    for (int j = 0; j < img.Height; j++)
                        img.SetPixel(i, j, Stage[i][j].CurrentInfection == 0 ? Color.FromArgb(255, 255, 255) :
                            Color.FromArgb(64, 255, 0));
                img.Save(filepath, ImageFormat.Gif);
            }
        }
        private static MagickImage BoardToImage()
        {
            using (Bitmap img = new Bitmap(StageSize, StageSize))
            {
                for (int i = 0; i < img.Width; i++)
                    for (int j = 0; j < img.Height; j++)
                        img.SetPixel(i, j, Stage[i][j].CurrentInfection == 0 ? Color.White :
                            Color.FromArgb(Stage[i][j].CurrentInfection % 255,
                            Math.Abs(Stage[i][j].CurrentInfection - 255) % 255,
                            Math.Abs(Stage[i][j].CurrentInfection - 510) % 255));
                return new MagickImage(img);
            }
        }
        private static void ImagesToAnimatedGIF(MagickImage[] images, string filepath)
        {
            using (MagickImageCollection collection = new MagickImageCollection())
            {
                foreach (var image in images)
                {
                    collection.Add(image);
                    collection.Last().AnimationDelay = 20;
                }
                collection.Write(filepath);
            }
        }
        #endregion Image

        #region Infection
        private static void Period()
        {
            Infect();
            ChooseRandomInfections();
            IncrementDiseaseProgress();
            Cure();

            NumberOfPeriods--;
        }
        private static void Cure()
        {
            Parallel.For(0, Stage.Length, i =>
            {
                for (Int16 j = 0; j < Stage.Length; j++)
                    if (Stage[i][j].CurrentInfection != 0 && Stage[i][j].InfectionTime == MaxInfectionTime + 1)
                    {
                        //Add disease to already infected list
                        if (Stage[i][j].PreviousInfections.ContainsKey(Stage[i][j].CurrentInfection))
                            Stage[i][j].PreviousInfections[Stage[i][j].CurrentInfection]++;
                        else
                            Stage[i][j].PreviousInfections.Add(Stage[i][j].CurrentInfection, 1);

                        //Cure
                        Stage[i][j].InfectionTime = 0;
                        Stage[i][j].CurrentInfection = 0;
                    }
            });
        }
        private static void IncrementDiseaseProgress()
        {
            Parallel.For(0, Stage.Length, i =>
            {
                for (Int16 j = 0; j < Stage.Length; j++)
                    if (Stage[i][j].CurrentInfection != 0)
                        Stage[i][j].InfectionTime++;
            });
        }
        private static void RandomlyInfectPeople(Int16 numberOfPeopleToInfect)
        {
            var randomList = new List<int>();
            while (randomList.Count() < numberOfPeopleToInfect * 2)
            {
                randomList.Add(RandomGen2.Next(StageSize));
                randomList = randomList.Distinct().ToList();
            }
            while (randomList.Count() > 0)
            {
                Stage[randomList.Last()][randomList[randomList.Count() - 2]].CurrentInfection = MutationNumber;
                Stage[randomList.Last()][randomList[randomList.Count() - 2]].InfectionTime = 1;
                randomList.RemoveAt(randomList.Count() - 2);
                randomList.RemoveAt(randomList.Count() - 1);
            }
        }
        private static void Infect()
        {
            Parallel.For(0, Stage.Length, i =>
            {
                for (Int16 j = 0; j < Stage.Length; j++)
                    InfectAllSpacesAround((short)i, j);
            });
        }
        private static void InfectAllSpacesAround(Int16 x, Int16 y)
        {
            //If not infected or just infected this turn return
            if (Stage[x][y].CurrentInfection == 0 || (Stage[x][y].CurrentInfection != 0 && Stage[x][y].InfectionTime == 0)) return;

            //Infect all four directions(if possible)
            if (x > 0)
                InfectOneSpace(Stage[x][y].CurrentInfection, (short)(x - 1), y);

            if (x < Stage.Length - 1)
                InfectOneSpace(Stage[x][y].CurrentInfection, (short)(x + 1), y);

            if (y > 0)
                InfectOneSpace(Stage[x][y].CurrentInfection, x, (short)(y - 1));

            if (y < Stage.Length - 1)
                InfectOneSpace(Stage[x][y].CurrentInfection, x, (short)(y + 1));
        }
        private static void InfectOneSpace(Int16 currentInfection, Int16 x, Int16 y)
        {
            //If the person is infected, or If they've already been infected "MaxInfectionTime" then don't infect
            if (Stage[x][y].CurrentInfection != 0 || (Stage[x][y].PreviousInfections.ContainsKey(currentInfection) &&
                    Stage[x][y].PreviousInfections[currentInfection] >= MaxInfectionTime)) return;

            //If random is larger than change of transmission don't transmite disease
            if (RandomGen2.Next(100) + 1 > ProbabilityOfTransmission * 100) return;

            //Possible mutate
            if (MutationNumber <= MaxNumberOfMutations && RandomGen2.Next(100) + 1 <= ChanceOfMutation * 100)
                lock (Stage[x][y])
                {
                    MutationNumber++;
                    Stage[x][y].PossibleNewInfections.Add(MutationNumber);
                }
            //Regular infection
            else
                lock (Stage[x][y])
                    Stage[x][y].PossibleNewInfections.Add(currentInfection);

        }
        private static void ChooseRandomInfections()
        {
            Parallel.For(0, Stage.Length, i =>
            {
                for (Int16 j = 0; j < Stage.Length; j++)
                {
                    if (Stage[i][j].CurrentInfection != 0 || !Stage[i][j].PossibleNewInfections.Any()) continue;
                    Stage[i][j].CurrentInfection = Stage[i][j].PossibleNewInfections[RandomGen2.Next(Stage[i][j].PossibleNewInfections.Count)];
                    Stage[i][j].PossibleNewInfections.Clear();
                    Stage[i][j].InfectionTime = 0;
                }
            }
            );
        }
        #endregion Infection
    }

    //Fancy Schmancy new random number generator for threaded stuff, fun times
    //http://blogs.msdn.com/b/pfxteam/archive/2009/02/19/9434171.aspx
    public static class RandomGen2
    {
        private static Random _global = new Random();
        [ThreadStatic]
        private static Random _local;

        public static int Next()
        {
            Random inst = _local;
            if (inst == null)
            {
                int seed;
                lock (_global) seed = _global.Next();
                _local = inst = new Random(seed);
            }
            return inst.Next();
        }

        public static int Next(int input)
        {
            Random inst = _local;
            if (inst == null)
            {
                int seed;
                lock (_global) seed = _global.Next();
                _local = inst = new Random(seed);
            }
            return inst.Next(input);
        }
    }
}

```
> 3 votes

---
Tags: fastest-code, simulation
---


# Question
Title: Solve a Tetris Puzzle (pack predefined shapes into optimal form)
The challenge is about finding an optimal solution on how to place a number of given shapes. It is oriented on the principle of Tetris, where it is optimal to pack the given pieces as tight as possible.

An optimal solution means that all shapes could be placed in one rectangle block filling the width of the playground. If there is no optimal solution possible, the code should find a solution where holes are placed as high as possible (thus allowing to have a subpart of the solution being optimal). Empty spaces on top of the solution are also counted as holes (see example at the bottom).

## Rules

* There are predefined Tetris shapes: `I J L S Z O T`
* There could be multiple shapes of the same type available
* There is a playground with a certain width X
* The minimum width is 4, there is no maximum width
* There is no limitation for the height of the playground
* It is possible to rotate the shapes in 4 directions (Up, Left, Right, Down)
* It is NOT possible to mirror the shapes (Turning L into J or S into Z)

Possible shapes:

```
T:      T
       TTT

I:     IIII

J:     JJJ
         J

L:       L
       LLL

S:      SS
       SS

Z:     ZZ
        ZZ

O:     OO
       OO

```

A bit of imagination is needed, but everyone who played Tetris should be familiar with the shapes.

## Example

A call to a solution using Python could look like the following:

`tetrissolver.py <Width> <Shape1> <Shape2> <ShapeN>`

`tetrissolver.py 4 S S T T L`

The result would be some kind of output which shows the optimal solution (tightest possible packaging). Bonus points if the solution also returns if the found solution is optimal.

Possible output of the above input in a text format:

```
LLLT
LSTT
SSST
STSS
TTTS

The found solution is optimal

```

If there is no optimal solution available, the code should find a solution with the least amount of holes in it. Empty spaces on top of the package are counted as holes. The above example with an additional T element could look like the following in the solution (holes marked with X):

```
XTXX
TTTX
LLLT
LSTT
SSST
STSS
TTTS

The found solution is NOT optimal

```

## Solution

The solution should find the most optimal package. Holes should be placed as high as possible. If two solutions generate the same quality of packages (optimal packages if possible, same amount of holes), the smallest solution wins.

# Answer
> 3 votes
# Java - Theoretically Optimal Solution

I needed one of these anyway, so...

Code is viewable here.

The routine should theoretically produce an optimal solution for any input. It typically runs on the order of milliseconds or seconds for \< 100 shapes, and the complexity appears to be roughly O(*n* log2 *n*) for random inputs. Packing hundreds or even thousands of random shapes should complete in a reasonable amount of time.

The worst case performance grows as O(*n**n* *w**w*), where *n* is the number of shapes to pack and *w* is the packing width. Thus this program earns the dubious distinction of having the worst worst case performance of any (non-busy-beaver) algorithm I've ever programmed. :P

### Sample I/O

```
java TetPack 10 J T Z I I J Z O O J T S S O I

IIIIJOOTTT
IIIIJOOSTI
OOSJJZTSSI
OOSSZZTTSI
OOJSZJTZZI
OOJJJJJJZZ

Displayed solution is optimal.

java TetPack 3 T

XTX
TTT

9 J S I O S T T I I I S

XIIIIIIII
TTTSSIIII
TTSSJJJOO
TTSSSSJOO
TSSSSIIII

java TetPack 15 L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J

JJJJLLLLJLJJJJJ
JJJJLLJJJLJJJJJ
LLLLLLJJJLLLJJJ
LLLLLLJJLLLLJJJ
LLLLJJJJLLJLLLL
LLLLJJJJJLJJJLL
LLJJJJJJJLLLLLL
LLJJJJJJJLLLLLL
LLJJJJJLJLLLLLL
JJJJJJLLJJJLJLL
JJJJJJLLLLLLJLL
JJJJJLLLJJLJJLL
LLLJJLLLJJLJJJJ
LLLLLLLLJJLLLJJ
JLLLLLJLJJLLJJJ
JJJLLLJJJLLLJJJ

Displayed solution is optimal.

java TetPack 4 Z T

XZXX
ZZTX
ZTTT

java TetPack 30 J I O J J L T T T I O Z Z S I I O Z T O L L J I I L S Z Z I J I O S L L L L J J J I I O Z L J I L S I S Z I L I J I O J J L T T T I O Z Z S I I O Z T O L L J I I L S Z Z I J I O S L L L L J J J I I O Z L J I L S I S Z I L I

XXIIIIIIIIIIIIIIIIIIIIIIIIIIII
LIIIILIIIILIIIILIIIIJLIIIIJLOO
LIIIILJJJLLIIIILLLJJJLIIIIJLOO
LLJLJLLIJLLLZLJLLLJJJLLZZJJLLI
JJJLJJJILLLZZLJJJLJZZLLIZZZOOI
JJJLLILILZZZJLLSSOOIZZLILZZOOI
JJJJJILILLZZJSSSZOOIOOLILZTLLI
IJJJJILLSSZJJSSZZOOIOOTILLTTLI
IJJJJILSSZZSSZSZTOOIITTTOOTSLI
IJJJJLLZZZSSZZTTTTOOIIJJOOLSSI
ISSZILLLZZOOZTTTTJOOIIJLLLLTSI
SSZZILLOOJOOTZZTTJJJIIJLZZTTOO
LSZLIZZOOJJJTTZZTIIIIIJLLZZTOO
LSSLIJZZOOOOTSSSSSSTZZJJJLIIII
LLSLLJJJOOOOSSSSSSTTTZZLLLIIII

```

---
Tags: code-golf, tetris, packing
---


title: Javascript: Mini Space Invaders

text:
# Question
Title: Javascript: Mini Space Invaders
I'm pretty new to code golfing, so I gave one of my first shots to a space invader clone called "Invas!on". It's a little less than 500 bytes, fully ASCII generated, and covers moving around and shooting at the aliens. There is also a little point system.

My specific question is about generating enemy patterns. I want to generate something like this:

```
...x.x.x.x.x.x...
..x.x.x.x.x.x.x..
...x.x.x.x.x.x...

```

...and so on.

Currently, I'm using this code:

```
for(b=[],j=2;j<136;j+=2)b.push(j),j==14&&(j=41)||j==55&&(j=80)||j==94&&(j=121)

```

It's just a loop that pushes enemy positions into an array `b`. Positions are every two spaces on a line, with a varying margin on both sides.

What is the shortest way to do this?

# Answer
### 58 : -20 bytes(25%) from OP

```
for(b=[],j=2;j<136;j+=j==14||j==94?29:j==55?27:2)b.push(j)

```

This should do the same thing as your code, but without all the ugly parentheses and explicit assignments. Since all you're really doing is adding each time, all you have to do is check how much to add.

I should note that I have no idea where you got the numbers from in the original code. Since it doesn't *seem* to match the pattern you gave, I assume the pattern is just an example (and the actual lines are longer), or there's something going on in your other code (not shown here). Either way, I matched up my positions with yours.

---

For a fixed pattern like this, though, it might be shorter to just encode it in a bitmap-style string or bitmasked integer. Doing it loop-style allows you to vary it a bit easier, but if your pattern is constant it's something to be aware of. For instance, your shown pattern has 51 positions, which are either "on" or "off". This means it needs 51 bits for a straight bitmask, which can fit in a single number:

```
000101010101010000010101010101010000010101010101000 = 0xAAA0AAA82AA8

```

So, if you can unpack that into an array efficiently, you may be able to score some more bytes. *Unfortunately*, I'm no Javascript whiz, so I couldn't get it shorter this way, leaving it at 61 bytes. Others may be able to improve upon this:

```
for(b=[],j=0,m=0xAAA0AAA82AA8;m>0;m>>>=1,j++)if(m&1)b.push(j)

```

So for this *exact* pattern, the first method is shorter (for me). If the pattern wasn't so evenly spaced (allowing simple additions), the second would most likely end up shorter.
> 5 votes

---
Tags: code-golf, tips, javascript
---


title: Swipe Type Converter

text:
# Question
Title: Swipe Type Converter
The next revolution in typing on laptops was released on the first of April, 2014 by SwiftKey. However, I want to be the first person to write a swiping nano clone, but, as I can't find a good swipe-text to real-text library, and I can't wait for them, I'm asking here.

## Task

Write a program that takes in swipe-text and outputs the real-text equivalent. Example:

```
Input: hgrerhjklo
Output: hello

```

When the user does:

Other examples:

```
Input: wertyuioiuytrtjklkjhgfd
Output: world

Input: poiuytrtyuioiugrewsasdfgbhnmkijnbg
Output: programming

Input: poiuygfdzxcvhjklkjhgres
Output: puzzles

Input: cvhjioiugfde
Output: code

Input: ghiolkjhgf
Output: golf

```

## Rules

* The program will take one swiped 'word' in on stdin or argv
* The first and last letter of the swiped input will equate to the first and last letter of the real word
* You can assume the user will make reasonably straight lines, but you can use the sample data to verify this (I made the sample data, and I will make the final test data)
* For ambiguous input, you can make select either output, but I will try to eradicate all ambiguousness from the test data
* This word will be in this word list (but swiped). The word list will be in the current directory, and can be read (newline separated, will be named `wordlist`, no extension).
* The swipe will only contain lowercase alphabetic characters
* The swipe may contain duplicated characters, if the user pauses on a key
* The program must output on stdout (case does not matter)
* The program must return `0` as the return code
* You must provide the run command, compile command (if needed), name and which input path to use
* Standard loopholes apply (they might not help, though)
* No non-builtin libraries allowed
* Deterministic, non golfed / obfuscated solutions preferred
* No file writing, networking, etc.
* Your code must run in one second or less (your code is run once per word)
* The scoring runs are run on a Intel i7 Haswell processor, with 4 virtual code (2 real ones), so you can use threads if you have to
* Maximum code length of 5000 bytes
* The language you use must have a free (non trial) version available for Linux (Arch Linux, if that matters)

## Winning Criterion

* The winner is the most accurate solution (scored by the control program, using the provided test list)
* Popularity is the tie breaker
* The scoring table will be updated every few days
* Time-outs and crashes count as fails
* This challenge will run for two weeks or more, depending on popularity
* The final scoring will use a different, randomly selected list of words (same length, from same word list)

## Other

## Current Score Boards

testlist (logs):

```
Three Pass Optimizer:Errors: 0/250       Fails: 7/250        Passes: 243/250     Timeouts: 0/250
Corner Sim:         Errors: 0/250       Fails: 9/250        Passes: 241/250     Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250       Fails: 17/250       Passes: 233/250     Timeouts: 0/250
Turnaround:         Errors: 0/250       Fails: 18/250       Passes: 232/250     Timeouts: 0/250
Direction Checker:  Errors: 0/250       Fails: 19/250       Passes: 231/250     Timeouts: 0/250
Regex Solver:       Errors: 0/250       Fails: 63/250       Passes: 187/250     Timeouts: 0/250

```

testlist2 (logs):

```
Corner Sim:         Errors: 0/250       Fails: 10/250       Passes: 240/250     Timeouts: 0/250
Three Pass Optimizer:Errors: 2/250       Fails: 14/250       Passes: 234/250     Timeouts: 0/250
Turnaround:         Errors: 0/250       Fails: 16/250       Passes: 234/250     Timeouts: 0/250
Direction Checker:  Errors: 0/250       Fails: 17/250       Passes: 233/250     Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250       Fails: 18/250       Passes: 232/250     Timeouts: 0/250
Regex Solver:       Errors: 0/250       Fails: 67/250       Passes: 183/250     Timeouts: 0/250

```

# Final Run

testlist (logs):

```
Corner Sim:         Errors: 0/250       Fails: 14/250       Passes: 236/250     Timeouts: 0/250
Three Pass Optimizer:Errors: 0/250       Fails: 18/250       Passes: 232/250     Timeouts: 0/250
Direction Checker:  Errors: 0/250       Fails: 20/250       Passes: 230/250     Timeouts: 0/250
Turnaround:         Errors: 0/250       Fails: 23/250       Passes: 227/250     Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250       Fails: 30/250       Passes: 220/250     Timeouts: 0/250
Regex Solver:       Errors: 0/250       Fails: 55/250       Passes: 195/250     Timeouts: 0/250

```

Well done to everybody and hgfdsasdertyuiopoiuy swertyuiopoijnhg!

# Answer
## JavaScript, ES6, Three Pass Optimizer, ~~112 187 235 240 241~~ 243 and ~~231~~ 234 passes

A three pass filter which first figures out critical keys in the keystroke sequence and then passes the sequence through the three filters:

1. A loosely formed RegEx out of the critical keys and helping keys. This gives correct result for majority of the keys (around 150)
2. A strict RegEx made out of just critical keys. This gives correct result for an extra 85 sequences
3. A third filter to figure out ambiguity amongst close answers. This works for 40% ambiguous cases.

**Code**

```
keyboard = {
  x: {},
  y: ['  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'],
};
for (var i in keyboard.y)
  for (var y of keyboard.y[i])
    keyboard.x[y] = +i*7;
p = C => (x=keyboard.x[C],{x, y: keyboard.y[x/7].indexOf(C)})
angle = (L, C, R) => (
  p0 = p(L), p1 = p(C), p2 = p(R),
  a = Math.pow(p1.x-p0.x,2) + Math.pow(p1.y-p0.y,2),
  b = Math.pow(p1.x-p2.x,2) + Math.pow(p1.y-p2.y,2),
  c = Math.pow(p2.x-p0.x,2) + Math.pow(p2.y-p0.y,2),
  Math.acos((a+b-c) / Math.sqrt(4*a*b))/Math.PI*180
)
corner = (L, C, R, N, W) => {
  if (skip) {
    skip = false;
    return [];
  }
  ngl = angle(L, C, R);
  if (ngl < 80) return [C + "{1,3}"]
  if (ngl < 115 && p(L).x != p(R).x && p(L).x != p(C) && p(R).x != p(C).x && Math.abs(p(L).y - p(R).y) < 5) return [C + "{0,3}"]
  if (ngl < 138) {
    if (N && Math.abs(ngl - angle(C, R, N)) < 6) {
      skip = true;
      return [L + "{0,3}", "([" + C + "]{0,3}|[" + R + "]{0,3})?", N + "{0,3}"]
    }
    return [C + "{0,3}"]
  }
  return ["([" + L + "]{0,3}|[" + C + "]{0,3}|[" + R + "]{0,3})?"]
}
f = S => {
  for (W = [S[0] + "{1,2}"],i = 1; i < S.length - 1; i++)
    W.push(...corner(S[i - 1], S[i], S[i + 1], S[i + 2], W))
  return [
    new RegExp("^" + W.join("") + S[S.length - 1] + "{1,3}$"),
    new RegExp("^" + W.filter(C=>!~C.indexOf("[")).join("") + S[S.length - 1] + "{1,3}$")
  ]
}
thirdPass = (F, C) => {
  if (!F[0]) return null
  F = F.filter((s,i)=>!F[i - 1] || F[i - 1] != s)
  FF = F.map(T=>[...T].filter((c,i)=>!T[i - 1] || T[i - 1] != c).join(""))
  if (FF.length == 1) return F[0];
  if (FF.length < 6 && FF[0][2] && FF[1][2] && FF[0][0] == FF[1][0] && FF[0][1] == FF[1][1])
    if (Math.abs(F[0].length - F[1].length) < 1)
      for (i=0;i<Math.min(F[0].length, FF[1].length);i++) {
        if (C.indexOf(FF[0][i]) < C.indexOf(FF[1][i])) return F[0]
        else if (C.indexOf(FF[0][i]) > C.indexOf(FF[1][i])) return F[1]
      }
  return F[0]
}
var skip = false;
SwiftKey = C => (
  C = [...C].filter((c,i)=>!C[i - 1] || C[i - 1] != c).join(""),
  skip = false, matched = [], secondPass = [], L = C.length, reg = f(C),
  words.forEach(W=>W.match(reg[0])&&matched.push(W)),
  words.forEach(W=>W.match(reg[1])&&secondPass.push(W)),
  matched = matched.sort((a,b)=>Math.abs(L-a.length)>Math.abs(L-b.length)),
  secondPass = secondPass.sort((a,b)=>Math.abs(L-a.length)>Math.abs(L-b.length)),
  first = matched[0], second = secondPass[0], third = thirdPass(secondPass.length? secondPass: matched, C),
  second && second.length >= first.length - 1? first != third ? third: second: third.length >= first.length ? third: first
)

// For use by js shell of latest firefox
print(SwiftKey(readline()));

```

The code assumes a variable called `words` is present which is an array of all the words from this page

See the code in action here

See the test cases in action here

Both the above link work only on a latest Firefox (33 and above) (due to ES6).
> 12 votes

# Answer
## Ruby, Regex Solver - ~~30 140 176 180 182~~ 187 and ~~179~~ 183 passes

I'll figure out the score later. Here is very naive solution that doesn't take the keyboard layout into account:

```
words = File.readlines('wordlist').map(&:chomp)

swipe = ARGV.shift
puts words.select {|word| word[0] == swipe[0] &&
                          word[-1] == swipe[-1]}
          .select {|word|
              chars = [word[0]]
              (1..word.size-1).each {|i| chars << word[i] if word[i] != word[i-1]}
              swipe[Regexp.new('^'+chars.join('.*')+'$')]
          }.sort_by {|word| word.size}[-1]

```

It takes input from ARGV and prints the result. I'm just filtering the word list by first and last letter, and them I'm trying all of the remaining words against the input (eliminating duplicate letters and using a regex like `^g.*u.*e.*s$` for "guess") and return the first of those if there are multiple solutions.

Run it like

```
ruby regex-solver.rb cvhjioiugfde

```

Anyone else, feel free to reuse this step as a first filter - I believe it won't throw out any correct words, so this preliminary check can greatly reduce the search space for better algorithms.

**Edit:** Following the OPs suggestion, I'm now selecting the longest of the candidates, which seems to be a decent heuristic.

Also thanks to es1024 for reminding me about duplicate letters.
> 9 votes

# Answer
# C++, Discrete Fréchet Distance - ~~201~~ ~~220~~ ~~222~~ 232 and 232 passes

To me, the problem very much called for the Fréchet Distance which unfortunately is very hard to compute.

Just for fun, I've tried to approach the problem by implementing a discrete approximation described by Thomas Eiter and Heikki Mannila in Computing Discrete Fréchet Distance (1994).

At first, I'm using the same approach as the others for filtering all words in the list which are subsequences of the input (also accounting for multiple sequential occurances of the same character). Then, I'm filling the polygon curve from letter to letter of every word with intermediate points and match it against the input curve. Finally, I divide every distance by the length of the word and take the minimum score.

So far, the method doesn't work as well as I had hoped (It recognizes the code example as "chide"), but this could just be the result of bugs I haven't found yet. Else, another idea would be to use other variations of the fréchet distance ("average" instead of "maximum dog leash length").

**Edit:** Now, I'm using an approximation to the "average dog leash length". This means that I'm finding an ordered mapping between both paths which minimizes the sum of all distances and later divide it by the number of distances.

If the same character appears twice or more often in the dictionary word, I only put one node in the path.

```
#include<iostream>
#include<fstream>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
#include<cmath>

using namespace std;

const double RESOLUTION = 3.2;

double dist(const pair<double, double>& a, const pair<double, double>& b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

double helper(const vector<pair<double, double> >& a,
        const vector<pair<double, double> >& b,
        vector<vector<double> >& dp,
        int i,
        int j) {
    if (dp[i][j] > -1)
        return dp[i][j];
    else if (i == 0 && j == 0)
        dp[i][j] = dist(a[0], b[0]);
    else if (i > 0 && j == 0)
        dp[i][j] = helper(a, b, dp, i - 1, 0) +
                   dist(a[i], b[0]);
    else if (i == 0 && j > 0)
        dp[i][j] = helper(a, b, dp, 0, j - 1) +
                   dist(a[0], b[j]);
    else if (i > 0 && j > 0)
        dp[i][j] = min(min(helper(a, b, dp, i - 1, j),
                           helper(a, b, dp, i - 1, j - 1)),
                       helper(a, b, dp, i, j - 1)) +
                   dist(a[i], b[j]);
    return dp[i][j];
}

double discretefrechet(const vector<pair<double, double> >& a, const vector<pair<double, double> >& b) {
    vector<vector<double> > dp = vector<vector<double> >(a.size(), vector<double>(b.size(), -1.));
    return helper(a, b, dp, a.size() - 1, b.size() - 1);
}

bool issubsequence(string& a, string& b) {
    // Accounts for repetitions of the same character: hallo subsequence of halo
    int i = 0, j = 0;
    while (i != a.size() && j != b.size()) {
        while (a[i] == b[j])
            ++i;
        ++j;
    }
    return (i == a.size());
}

int main() {
    string swipedword;
    cin >> swipedword;

    ifstream fin;
    fin.open("wordlist");
    map<string, double> candidatedistance = map<string, double>();
    string readword;
    while (fin >> readword) {
        if (issubsequence(readword, swipedword) && readword[0] == swipedword[0] && readword[readword.size() - 1] == swipedword[swipedword.size() - 1]) {
            candidatedistance[readword] = -1.;
        }
    }
    fin.close();

    ifstream fin2;
    fin2.open("keypos.csv");
    map<char, pair<double, double> > keypositions = map<char, pair<double, double> >();
    char rc, comma;
    double rx, ry;
    while (fin2 >> rc >> comma >> rx >> comma >> ry) {
        keypositions[rc] = pair<double, double>(rx, ry);
    }
    fin2.close();

    vector<pair<double, double> > swipedpath = vector<pair<double, double> >();
    for (int i = 0; i != swipedword.size(); ++i) {
        swipedpath.push_back(keypositions[swipedword[i]]);
    }

    for (map<string, double>::iterator thispair = candidatedistance.begin(); thispair != candidatedistance.end(); ++thispair) {
        string thisword = thispair->first;
        vector<pair<double, double> > thispath = vector<pair<double, double> >();
        for (int i = 0; i != thisword.size() - 1; ++i) {
            pair<double, double> linestart = keypositions[thisword[i]];
            pair<double, double> lineend = keypositions[thisword[i + 1]];
            double linelength = dist(linestart, lineend);
            if (thispath.empty() || linestart.first != thispath[thispath.size() - 1].first || linestart.second != thispath[thispath.size() - 1].second)
                thispath.push_back(linestart);
            int segmentnumber = linelength / RESOLUTION;
            for (int j = 1; j < segmentnumber; ++j) {
                thispath.push_back(pair<double, double>(linestart.first + (lineend.first - linestart.first) * ((double)j) / ((double)segmentnumber),
                                    linestart.second + (lineend.second - lineend.second) * ((double)j) / ((double)segmentnumber)));
            }
        }
        pair<double, double> lastpoint = keypositions[thisword[thisword.size() - 1]];
        if (thispath.empty() || lastpoint.first != thispath[thispath.size() - 1].first || lastpoint.second != thispath[thispath.size() - 1].second)
        thispath.push_back(lastpoint);

        thispair->second = discretefrechet(thispath, swipedpath) / (double)(thispath.size());
    }

    double bestscore = 1e9;
    string bestword = "";
    for (map<string, double>::iterator thispair = candidatedistance.begin(); thispair != candidatedistance.end(); ++thispair) {
        double score = thispair->second;
        if (score < bestscore) {
            bestscore = score;
            bestword = thispair->first;
        }
        // cout << thispair->first << ": " << score << endl;
    }
    cout << bestword << endl;

    return 0;
}

```

I've compiled the code with clang, but `g++ ./thiscode.cpp -o ./thiscode` should also work fine.
> 7 votes

# Answer
# PHP, Direction Checker, ~~203 213 216 229~~ 231 and ~~229~~ 233 passes

This begins with a simple pass through the dictionary to obtain a list of words whose letters are all present in the input (what Martin did here), and also only checking for `l.*` instead of `l.*l.*` when `l` is duplicated.

The longest word here is then saved in a variable.

Another check is then done, based on the keys at the points where the swipe changes direction (+/0 to - or -/0 to +, in either x or y). The list of possible words is checked against this list of characters, and words that do not match are eliminated. This approach relies on sharp turns in swiping to be accurate.

The longest remaining word is outputted, or if no words are left, the longest word from earlier is outputted instead.

**Edit:** Added all characters in a horizontal line leading up to a change in direction as possible values to check for.

PHP 5.4 is required (or replace all `[..]` with `array(..)`).

```
<?php
function get_dir($a, $b){
    $c = [0, 0];
    if($a[0] - $b[0] < -1.4) $c[0] = 1;
    else if($a[0] - $b[0] > 1.4) $c[0] = -1;
    if($a[1] < $b[1]) $c[1] = 1;
    else if($a[1] > $b[1]) $c[1] = -1;
    return $c;
}
function load_dict(){
    return explode(PHP_EOL, file_get_contents('wordlist'));
}

$coord = [];
$f = fopen('keypos.csv', 'r');
while(fscanf($f, "%c, %f, %f", $c, $x, $y)){
    $coord[$c] = [$x, $y];
}
fclose($f);

$dict = load_dict();
$in = $argv[1];
$possib = [];

foreach($dict as $c){
    if($c[0] == $in[0]){
        $q = strlen($c);
        $r = strlen($in);
        $last = '';
        $fail = false;
        $i = $j = 0;
        for($i = 0; $i < $q; ++$i){
            if($last == $c[$i]) continue;
            if($j >= $r){
                $fail = true;
                break;
            }
            while($c[$i] != $in[$j++])
                if($j >= $r){
                    $fail = true;
                    break;
                }
            if($fail) break;
            $last = $c[$i];
        }
        if(!$fail)
            $possib[] = $c;
    }
}

$longest = '';
foreach($possib as $p){
    if(strlen($p) > strlen($longest))
        $longest = $p;
}

$dir = [[0, 0]];
$cdir = [0, 0];
$check = '/^' . $in[0] . '.*?';
$olst = []; $p = 1;

$len = strlen($in);
for($i = 1; $i < $len; ++$i){
    $dir[$i] = get_dir($coord[$in[$i - 1]], $coord[$in[$i]]);
    $olddir = $cdir;
    $newdir = $dir[$i];
    $xc = $olddir[0] && $newdir[0] && $newdir[0] != $olddir[0];
    $yc = $olddir[1] && $newdir[1] && $newdir[1] != $olddir[1];
    if($xc || $yc){ // separate dir from current dir
        if($yc && !$xc && $dir[$i - 1][1] == 0){
            $tmp = '';
            for($j = $i - 1; $j >= 0 && $dir[$j][1] == 0; --$j){
                $tmp = '(' . $in[$j-1] . '.*?)?' . $tmp;
            }
            $olst[] = range($p, $p + (($i - 1) - $j));
            $p += ($i - 1) - $j + 1;
            $check .= $tmp . '(' . $in[$i - 1] . '.*?)?';
        }else{
            $check .= $in[$i - 1] . '.*?';
        }
        $cdir = $dir[$i];
    }else{
        if(!$cdir[0]) $cdir[0] = $dir[$i][0];
        if(!$cdir[1]) $cdir[1] = $dir[$i][1];
    }
}
$check .= substr($in, -1) . '$/';
$olstc = count($olst);
$res = [];
foreach($possib as $p){
    if(preg_match($check, $p, $match)){
        if($olstc){
            $chk = array_fill(0, $olstc, 0);
            for($i = 0; $i < $olstc; ++$i){
                foreach($olst[$i] as $j){
                    if(isset($match[$j]) && $match[$j]){
                        ++$chk[$i];
                    }
                }
                // give extra weight to the last element of a horizontal run
                if(@$match[$olst[$i][count($olst[$i])-1]])
                    $chk[$i] += 0.5;
            }
            if(!in_array(0, $chk)){
                $res[$p] = array_sum($chk);
            }
        }else{
            $res[$p] = 1;
        }
    }
}
$possib = array_keys($res, @max($res));
$newlong = '';
foreach($possib as $p){
    if(strlen($p) > strlen($newlong))
        $newlong = $p;
}
if(strlen($newlong) == 0) echo $longest;
else echo $newlong;

```
> 6 votes

# Answer
# Python 2, Turnarounds, ~~224 226 230~~ 232 and ~~230~~ 234 passes

This is quite a straight forward approach:

* Find the points where the flow of letters changes direction (plus start and end).
* Output the longest word that includes all these turning points.

```
import sys, csv, re

wordlistfile = open('wordlist', 'r')
wordlist = wordlistfile.read().split('\n')

layout = 'qwertyuiop asdfghjkl  zxcvbnm'
keypos = dict((l, (2*(i%11)+i/11, i/11)) for i,l in enumerate(layout))

#read input from command line argument
input = sys.argv[1]

#remove repeated letters
input = ''.join(x for i,x in enumerate(input) if i==0 or x!=input[i-1])

#find positions of letters on keyboard
xpos = map(lambda l: keypos[l][0], input)
ypos = map(lambda l: keypos[l][1], input)

#check where the direction changes (neglect slight changes in x, e.g. 'edx')
xpivot = [(t-p)*(n-t)<-1.1 for p,t,n in zip(xpos[:-2], xpos[1:-1], xpos[2:])]
ypivot = [(t-p)*(n-t)<0 for p,t,n in zip(ypos[:-2], ypos[1:-1], ypos[2:])]
pivot = [xp or yp for xp,yp in zip(xpivot, ypivot)]

#the first and last letters are always pivots
pivot = [True] + pivot + [True]

#build regex
regex = ''.join(x + ('+' if p else '*') for x,p in zip(input, pivot))
regexobj = re.compile(regex + '$')

#find all words that match the regex and output the longest one
words = [w for w in wordlist if regexobj.match(w)]
output = max(words, key=len) if words else input
print output

```

Run as

```
python turnarounds.py tyuytrghn

```

The solution is not very robust. A single wrong keystroke would make it fail. However, since the set of test cases has very little no misspellings it performs quite well, only getting confused in some cases where it picks too long words.

*Edit:* I changed it a bit to not use the provided key position file but a simplified layout. This makes it easier for my algorithm because in the file the keys are not evenly spaced. I can achieve even slightly better results by including some ad-hoc tiebreakers for ambiguous cases, but that would be over-optimizing for this particular test set. Some fails remain that are not actually ambiguous but that I don't catch with my simple algorithm because it only considers direction changes of more than 90 degrees.
> 6 votes

# Answer
# Python 3, Corner Simulator, 241 and 240 passes

Algorithm:

* Deduplicate (remove consecutive runs of the same character) the input and all the words in the word list (using a dictionary to get the original words back)
* Remove all words that do not start and end with the start and end of the swipe (first pass)
* Make a regex out of all the corners greater than 80 degrees, then remove all words which do not match this (second pass)
* Regex each word (like Regex Solver) against the swipe, then split the swipe into a series of theoretically straight lines, and check if they are straight and could have been produced by a finger moving along that line (`significant_letter` function) (third pass)
* Sort the words by closeness to the straight lines
* Then use length as a tie breaker (longer is better)
* Then use Levenshtein distance as the final tie breaker
* Output word!

Code:

```
# Corner Sim

from math import atan, degrees, pi, factorial, cos, radians
import csv
import re
import sys

keys = {}
key_size = 1.5
for line in open("keypos.csv"):
    k, x, y = map(str.strip, line.split(","))
    keys[k] = float(x), float(y)

def deduplicate(s):
    return s[0] + "".join(s[i + 1] for i in range(len(s) - 1) if s[i + 1] != s[i])

def angle(coord1, coord2):
    x1, y1, x2, y2 = coord1 + coord2
    dx, dy = x2 - x1, y1 - y2
    t = abs(atan(dx/dy)) if dy else pi / 2
    if dx >= 0 and dy >= 0: a = t
    elif dx >= 0 and dy < 0: a = pi - t
    elif dx < 0 and dy >= 0: a = 2 * pi - t
    else: a = t + pi
    return degrees(a)

def significant_letter(swipe):
    if len(swipe) <= 2: return 0
    x1, y1, x2, y2 = keys[swipe[0]] + keys[swipe[-1]]
    m = 0 if x2 == x1 else (y2 - y1) / (x2 - x1)
    y = lambda x: m * (x - x1) + y1
    def sim_fun(x2, y2):
        try: return (x2 / m + y2 - y1 + x1 * m) / (m + 1 / m)
        except ZeroDivisionError: return x2
    dists = []
    for i, key in enumerate(swipe[1:-1]):
        sx, bx = min(x1, x2), max(x1, x2)
        pos_x = max(min(sim_fun(*keys[key]), bx), sx)
        sy, by = min(y1, y2), max(y1, y2)
        pos_y = max(min(y(pos_x), by), sy)
        keyx, keyy = keys[key]
        dist = ((keyx - pos_x) ** 2 + (keyy - pos_y) ** 2) ** 0.5
        a = angle((keyx, keyy), (pos_x, pos_y))
        if 90 <= a <= 180: a = 180 - a
        elif 180 <= a <= 270: a = a - 180
        elif 270 <= a <= 360: a = 360 - a
        if a > 45: a = 90 - a
        h = key_size / 2 / cos(radians(a))
        dists.append((max(dist - h, 0), i + 1, key))
    return sorted(dists, reverse=True)[0][0]

def closeness2(s, t):
    # https://en.wikipedia.org/wiki/Levenshtein_distance
    if s == t: return 0
    if not len(s): return len(t)
    if not len(t): return len(s)
    v0 = list(range(len(t) + 1))
    v1 = list(range(len(t) + 1))
    for i in range(len(s)):
        v1[0] = i + 1
        for j in range(len(t)):
            cost = 0 if s[i] == t[j] else 1
            v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
        for j in range(len(v0)):
            v0[j] = v1[j]
    return v1[len(t)] / len(t)

def possible(swipe, w, s=False):
    m = re.match("^" + "(.*)".join("({})".format(i) for i in w) + "$", swipe)
    if not m or s:
        return bool(m)
    return closeness1(swipe, w) < 0.8

def closeness1(swipe, w):
    m = re.match("^" + "(.*)".join("({})".format(i) for i in w) + "$", swipe)
    unsigpatches = []
    groups = m.groups()
    for i in range(1, len(groups), 2):
        unsigpatches.append(groups[i - 1] + groups[i] + groups[i + 1])
    if debug: print(unsigpatches)
    sig = max(map(significant_letter, unsigpatches))
    if debug: print(sig)
    return sig

def find_closest(swipes):
    level1, level2, level3, level4 = swipes
    if debug: print("Loading words...")
    words = {deduplicate(i.lower()): i.lower() for i in open("wordlist").read().split("\n") if i[0] == level1[0] and i[-1] == level1[-1]}
    if debug: print("Done first filter (start and end):", words)
    r = re.compile("^" + ".*".join(level4) + "$")
    pos_words2 = list(filter(lambda x: bool(r.match(x)), words))
    if debug: print("Done second filter (sharpest points):", pos_words2)
    pos_words = pos_words2 or words
    pos_words = list(filter(lambda x: possible(level1, x), pos_words)) or list(filter(lambda x: possible(level1, x, s=True), pos_words))
    if debug: print("Done third filter (word regex):", pos_words)
    sorted_pos_words = sorted((closeness1(level1, x), -len(x), closeness2(level1, x), x)
                              for x in pos_words)
    if debug: print("Closeness matching (to", level2 + "):", sorted_pos_words)
    return words[sorted_pos_words[0][3]]

def get_corners(swipe):
    corners = [[swipe[0]] for i in range(4)]
    last_dir = last_char = None
    for i in range(len(swipe) - 1):
        dir = angle(keys[swipe[i]], keys[swipe[i + 1]])
        if last_dir is not None:
            d = abs(last_dir - dir)
            a_diff = min(360 - d, d)
            corners[0].append(last_char)
            if debug: print(swipe[i], dir, last_dir, a_diff, end=" ")
            if a_diff >= 55:
                if debug: print("C", end=" ")
                corners[1].append(last_char)
            if a_diff >= 65:
                if debug: print("M", end=" ")
                corners[2].append(last_char)
            if a_diff >= 80:
                if debug: print("S", end=" ")
                corners[3].append(last_char)
            if debug: print()
        last_dir, last_char = dir, swipe[i + 1]
    tostr = lambda x: deduplicate("".join(x + [swipe[-1]]).lower())
    return list(map(tostr, corners))

if __name__ == "__main__":
    debug = "-d" in sys.argv
    if debug: sys.argv.remove("-d")
    swipe = deduplicate(sys.argv[1] if len(sys.argv) > 1 else input()).lower()
    corners = get_corners(swipe)
    if debug: print(corners)
    print(find_closest(corners))

```

Run with `python3 entries/corner_sim.py`
> 4 votes

---
Tags: code-challenge, keyboard
---


title: Draw a Golden Spiral!

text:
# Question
Title: Draw a Golden Spiral!
Given a number `n`, you must output a golden spiral with the number of quarter turns being `n`.

The spiral must be completely black and the background must be completely white. This must be output as a φ⌊n/4⌋\*4 by φ⌊n/4⌋\*4 PNG file (you may output a PPM and convert it later). The shortest code wins.

The radius of the smallest quarter turn should be φ-3.

In geometry, a golden spiral is a logarithmic spiral whose growth factor is φ, the golden ratio.That is, a golden spiral gets wider (or further from its origin) by a factor of φ for every quarter turn it makes.

# Answer
## Mathematica, 169 bytes

All those annoying options. :(

```
f=Export[p=GoldenRatio;"a.png",ParametricPlot[p^(2t-3){Cos[a=t*Pi],Sin@a},{t,0,#/2},PlotRange->{r={m=-p^(#-3),-m},r},PlotStyle->Black,Axes->1<0,ImageSize->p^#~Floor~4]]&

```

This function saves the spiral to `a.png` in wherever your current working directory is.

The result of `f[9]`:

The result of `f[12]`:

I hope I understood all the bits about the scaling correctly.

There's not a whole lot to say about the code. I'm using `ParametricPlot` to draw curve as a parameterised function in `t` which advances by `1/2` for each quarter turn. The rest is done in the options:

* `PlotRange->{r={m=-p^(#-3),-m},r}` makes sure we have an square aspect ratio which *just* covers the outermost point of the spiral.
* `PlotStyle->Black` overwrites Mathematica's blue default colour.
* `Axes->1<0` is just `Axes->False` (and turns off the axes, who knew!).
* `ImageSize->p^#~Floor~4` sets the correct dimensions in pixels, by noticing that `⌊n/4⌋*4` just means "`n` rounded down to the nearest multiple of `4`".
> 7 votes

# Answer
# Python 3 - 290 269

This will get crushed by any kind of built-in parametrics, but I figured I'd post it as an example of a point-by-point solution.

Edit: Thanks for the golfing tips! If you have any more, please make them.

```
from math import *
from PIL import Image as I, ImageDraw as D
n=eval(input())
G=(1+5**.5)/2
w=int(G**(4*(n//4)))
i=I.new("RGB",(w,w),"white")
d=D.Draw(i)
k=pi/180
d.line([(G**(j/90)*cos(j*k)+w/2,G**(j/90)*sin(j*k)+w/2)for j in range(n*90)],fill=0)
i.save("s.png","PNG")

```
> 7 votes

---
Tags: code-golf, math, graphical-output
---


# Question
Title: Construct n-gons with a ruler and compass
**The task** is to draw a regular polygon of n sides using only a compass and an unmarked ruler.

**Input** (n) is one of the following 10 numbers: 3, 4, 5, 6, 8, 10, 12, 15, 16, 17.

**Method**: Because you only have a ruler and compass you can only draw points, lines and circles.

A line can only be drawn:

* through two existing points.

A circle can only be drawn:

* with one point as its centre and with its perimeter passing through a second point.

A point can only be drawn:

* at the intersection of two lines,
* at the intersection(s) of a line and a circle,
* at the intersection(s) of two circles,
* at the outset, when you may draw 2 points to get started.

Through this process (and only through this process) you must draw the n lines of the requested n-gon, along with any working required to get to that stage.

EDIT: The position of intersections must be calculated, but lines and circles may be drawn by any means provided by the language.

**Output** is an image of an n-sided regular polygon, showing working.

**Graphically** there are no restrictions on image size, format, line thickness or anything else not mentioned here. However it must be possible to visually distinguish distinct lines, circles and their intersections. Additionally:

* The n lines that make up your n-gon's sides must be a different colour to your 'working' (i.e. any points, circles or other lines) and a different colour again to your background.
* Working can leave the borders of the drawing area, except points, which must all be within the visible bounds of the image.
* A circle can be a full circle or just an arc (as long as it shows required intersections).
* A line is infinite (i.e. leaves the drawing area) or cut off at the two points it goes through. EDIT: A line may be drawn at any length. Points can only be created where the drawn line visually intersects.
* A point can be drawn as you wish, including not marking it.

**Scoring** is twofold, a submission gets 1 point per input it supports, for a maximum of 10 points. In the event of a draw, shortest byte count wins.

Recognition will be given to submissions that can construct n-gons in the fewest steps or are able to construct n-gons outside of the given range, but it won't help your score.

Background info from Wikipedia

# Answer
# BBC Basic, 8 polygons: 3,4,5,6,8,10,12,15 sides (also 60 sides)

Download emulator at http://www.bbcbasic.co.uk/bbcwin/download.html

I decided not to include 16 sides, simply because my pre-construction was getting rather cluttered. 2 more circles and a line would be needed. BTW 17 sides is very complicated indeed, and would perhaps go best as a separate program.

I got more return for adding 2 circles to my original construction to make the pentagon, as this also gave me access to 10,15 and 60 sides.

```
  GCOL 7                               :REM light grey
  z=999                                :REM width of display (in positive and negative direction)
  e=1                                  :REM enable automatic drawing of line through intersections of 2 circles
  DIM m(99),c(99),p(99),q(99),r(99)    :REM array dimensioning for lines and points
  REM lines have a gradient m and y-intercept c. Points have coordinates (p,q) and may be associated with a circle of radius r.

  REM PRECONSTRUCTION

  ORIGIN 500,500
  p(60)=0:q(60)=0                      :REM P60=centre of main circle
  p(15)=240:q(15)=70                   :REM P15=intersection main circle & horiz line
  t=FNr(60,15)                         :REM draw main circle, set radius, SQR(240^2+70^2)=250 units (125 pixels)
  t=FNl(1,60,15)                       :REM L1=horizontal through main circle
  t=FNc(15,45,1,60,-1)                 :REM define P45 as other intersection of main cir and horiz line. overwrite P15 with itself.

  t=FNr(15,45):t=FNr(45,15)            :REM draw 2 large circles to prepare to bisect L1
  t=FNc(61,62,2,45,15)                 :REM bisect L1, forming line L2 and two new points
  t=FNc(30,0,2,60,-1)                  :REM define points P0 and P30 on the crossings of L2 and main circle
  t=FNr(30,60):t=FNc(40,20,3,60,30)    :REM draw circles at P30, and line L3 through intersections with main circle, to define 2 more points
  t=FNr(15,60):t=FNc(25,5,4,60,15)     :REM draw circles at P15, and line L4 through intersections with main circle, to define 2 more points
  t=FNx(63,3,4):t=FNl(5,63,60)         :REM draw L5 at 45 degrees
  t=FNc(64,53,5,60,-1)                 :REM define where L5 cuts the main circle

  e=0                                  :REM disable automatic line drawing through intersections of 2 circles
  GCOL 11                              :REM change to light yellow for the 5 sided preconstruction
  t=FNx(65,1,4):t=FNr(65,0)            :REM draw a circle of radius sqrt(5) at intersection of L1 and L4
  t=FNc(66,67,1,65,-1)                 :REM find point of intersection of this circle with L1
  t=FNr(0,67)                          :REM draw a circle centred at point 0 through that intersection
  t=FNc(36,24,6,60,0)                  :REM find the intersections of this circle with the main circle

  REM USER INPUT AND POLYGON DRAWING

  INPUT d
  g=ASC(MID$("  @@XT u X @  T",d))-64  :REM sides,first point: 3,0; 4,0; 5,24; 6,20; 8,53; 10,24; 12,0; 15,20
  IF d=60 THEN g=24                    :REM bonus polygon 60, first point 24
  FORf=0TOd
    GCOL12                             :REM blue
    h=(g+60DIVd)MOD60                  :REM from array index for first point, calculate array index for second point
    t=FNr(h,g)                         :REM draw circle centred on second point through first point
    t=FNc((h+60DIVd)MOD60,99,99,60,h)  :REM calculate the position of the other intersection of circle with main circle. Assign to new point.
    GCOL9                              :REM red
    LINEp(g),q(g),p(h),q(h)            :REM draw the side
    g=h                                :REM advance through the array
  NEXT

  END

  REM FUNCTIONS

  REM line through a and b
  DEFFNl(n,a,b)
  m(n)=(q(a)-q(b))/(p(a)-p(b))
  c(n)=q(a)-m(n)*p(a)
  LINE -z,c(n)-m(n)*z,z,c(n)+m(n)*z
  =n

  REM radius of circle at point a passing through point b
  DEFFNr(a,b)
  r(a)=SQR((p(a)-p(b))^2+(q(a)-q(b))^2)
  CIRCLEp(a),q(a),r(a)
  =a

  REM intersection of 2 lines: ma*x+ca=mb*x+cb so (ma-mb)x=cb-ca
  DEFFNx(n,a,b)
  p(n)=(c(b)-c(a))/(m(a)-m(b))
  q(n)=m(a)*p(n)+c(a)
  =n

  REM intersection of 2 circles a&b (if b>-1.) The first step is calculating the line through the intersections
  REM if b < 0 the first part of the function is ignored, and the function moves directly to calculating intersection of circle and line.
  REM inspiration from http://math.stackexchange.com/a/256123/137034

  DEFFNc(i,j,n,a,b)
  IF b>-1 c(n)=((r(a)^2-r(b)^2)-(p(a)^2-p(b)^2)-(q(a)^2-q(b)^2))/2/(q(b)-q(a)):m(n)=(p(a)-p(b))/(q(b)-q(a)):IF e LINE -z,c(n)-m(n)*z,z,c(n)+m(n)*z

  REM intersection of circle and line
  REM (mx+ c-q)^2+(x-p)^2=r^2
  REM (m^2+1)x^2 + 2*(m*(c-q)-p)x + (c-q)^2+p^2-r^2=0
  REM quadratic formula for ux^2+vx+w=0 is x=-v/2u +/- SQR(v^2-4*u*w)/2u or x= v/2u +/- SQR((v/2u)^2 - w/u)

  u=m(n)^2+1
  v=-(m(n)*(c(n)-q(a))-p(a))/u               :REM here v corresponds to v/2u in the formula above
  w=SQR(v^2-((c(n)-q(a))^2+p(a)^2-r(a)^2)/u)

  s=SGN(c(n)+m(n)*v-q(a)):IF s=0 THEN s=1    :REM sign of s depends whether midpoint between 2 points to be found is above centre of circle a
  p(i)=v+s*w:q(i)=m(n)*p(i)+c(n)             :REM find point that is clockwise respect to a
  p(j)=v-s*w:q(j)=m(n)*p(j)+c(n)             :REM find point that is anticlockwise respect to a
  =n

```

The program does a pre-construction before asking for any user input. This is sufficient to define at least 2 points on the main circle which correspond to adjacent vertices of a 3,4,5,6,8,10,12,15 or 60 sided figure. The points are stored in a set of 99-element arrays, in which elements 0-59 are set aside for equally spaced points around the circumference. This is mainly for clarity, the octagon does not fit perfectly into 60 points so some flexibility is needed there (and also for the 16-gon if it were included.) The image looks like the image below, in white and grey, with only the two circles in yellow being exclusively dedicated to shapes with multiples of 5 sides. See http://en.wikipedia.org/wiki/Pentagon#mediaviewer/File:Regular\_Pentagon\_Inscribed\_in\_a\_Circle\_240px.gif for my preferred pentagon drawing method. The jaunty angle is to avoid vertical lines, as the program cannot handle infinite gradients.

The user inputs a number `d` for the number of sides required. The program looks up in the array the index of the first of the two points (the next one is 60/d away in a clockwise direction.)

The program then loops through the process of drawing a circle centred on the second point that passes throug the first, and calculating the new intersection in order to walk its way round the main circle. The construction circles are drawn in blue, and the required polygon is drawn in red. The final images look like this.

I'm quite pleased with them. BBC Basic performs the calculations accurately enough. However its apparent (particularly with 15 and 60 sides) that BBC Basic tends to draw circles with a slightly smaller radius than it should.
> 10 votes

# Answer
## Mathematica, ~~2~~ ~~3~~ 4 polygons, 759 bytes

```
S=Solve;n=Norm;A=Circle;L=Line;c={#,Norm[#-#2]}&{a_,b_List}~p~{c_,d_List}:=a+l*b/.#&@@S[a+l*b==c+m*d,{l,m}]{a_,b_List}~p~{c_,r_}:=a+l*b/.S[n[c-a-l*b]==r,l]{c_,r_}~p~{d_,q_}:={l,m}/.S[n[c-{l,m}]==r&&n[d-{l,m}]==q,{l,m}]q={0,0};r={1,0};a=q~c~r;b=r~c~q;Graphics@Switch[Input[],3,{s=#&@@p[a,b];A@@@{a,b},Red,L@{q,r,s,q}},4,{k={q,r};{d,e}=a~p~b;j={d,e-d};d=k~p~j~c~q;{e,f}=j~p~d;A@@@{a,b,d},L/@Accumulate/@{k,j},Red,L@{q,e,r,f,q}},6,{d={q,r};e=#&@@d~p~a;f=e~c~q;{g,h}=a~p~f;{i,j}=a~p~b;A@@@{a,b,f},L@{#-2#2,#+2#2}&@@d,Red,L@{r,i,g,e,h,j,r}},8,{k={q,r};{d,e}=a~p~b;j={d,e-d};d=k~p~j~c~q;{e,f}=j~p~d;g=e~c~q;h=q~c~e;i=r~c~e;{o,s}=g~p~h;{t,u}=g~p~i;o={o,2s-2o};s={t,2u-2t};{t,u}=o~p~d;{v,w}=s~p~d;A@@@{a,b,d,g,h,i},L/@Accumulate/@{k,j,o,s},Red,L@{q,t,e,v,r,u,f,w,q}}]

```

Random bullet points:

* Input is provided via prompt.
* I'm currently supporting inputs **3**, **4**, **6**, **8**.
* From your options, I chose the following plotting styles:
    + Full circles.
    + Lines from endpoint to endpoint, unless a relevant intersection lies outside, in which case I'll hardcode the extent.
    + No points.
    + Workings are black, polygons are red - not for aesthetic but for golfing reasons.
* There's some serious code duplication between the polygons. I think at some point I'll just do a single construction for all of them, enumerating all lines and points and circles along the way, and then just reduce the `Switch` to select the relevant circles and lines for each construction. That way I could reuse a lot of primitives between them.
* The code contains a lot of boilerplate functions which determine all the relevant intersections, and create circles from two points.
* With that in place, I will be adding more polygons in the future.

Here is the ungolfed code:

```
S = Solve;
n = Norm;
A = Circle;
L = Line;
c = {#, Norm[# - #2]} &
{a_, b_List}~p~{c_, d_List} :=
 a + l*b /. # & @@ S[a + l*b == c + m*d, {l, m}]
{a_, b_List}~p~{c_, r_} := a + l*b /. S[n[c - a - l*b] == r, l]
{c_, r_}~p~{d_, q_} := {l, m} /.
  S[n[c - {l, m}] == r && n[d - {l, m}] == q, {l, m}]
q = {0, 0};
r = {1, 0};
a = q~c~r;
b = r~c~q;
Graphics@Switch[Input[],
  3,
  {
   s = # & @@ p[a, b];
   A @@@ {a, b},
   Red,
   L@{q, r, s, q}
   },
  4,
  {
   k = {q, r};
   {d, e} = a~p~b;
   j = {d, e - d};
   d = k~p~j~c~q;
   {e, f} = j~p~d;
   A @@@ {a, b, d},
   L /@ Accumulate /@ {k, j},
   Red,
   L@{q, e, r, f, q}
   },
  6,
  {
   d = {q, r};
   e = # & @@ d~p~a;
   f = e~c~q;
   {g, h} = a~p~f;
   {i, j} = a~p~b;
   A @@@ {a, b, f},
   L@{# - 2 #2, # + 2 #2} & @@ d,
   Red,
   L@{r, i, g, e, h, j, r}
   },
  8,
  {
   k = {q, r};
   {d, e} = a~p~b;
   j = {d, e - d};
   d = k~p~j~c~q;
   {e, f} = j~p~d;
   g = e~c~q;
   h = q~c~e;
   i = r~c~e;
   {o, s} = g~p~h;
   {t, u} = g~p~i;
   o = {o, 2 s - 2 o};
   s = {t, 2 u - 2 t};
   {t, u} = o~p~d;
   {v, w} = s~p~d;
   A @@@ {a, b, d, g, h, i},
   L /@ Accumulate /@ {k, j, o, s},
   Red,
   L@{q, t, e, v, r, u, f, w, q}
   }
  ]

```

And here are the outputs:
> 16 votes

---
Tags: code-challenge, graphical-output, geometry
---


# Question
Title: Animating the Separation of Fluids by Density
Let the characters `0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ` represent the particles of 36 immiscible fluids, each more dense than the last. So the `0` fluid is the least dense and floats on all the others, while `Z` is the densest and always sinks.

Let `#` represent a solid particle that cannot move at all..

Consider a rectangular grid of some of these 37 characters, with anything out of bounds treated as `#`. Gravity will want to stabilize them with the least dense fluids on top and the most dense on the bottom.

Our procedure for stabilization is:

1. Choose a random grid cell *c* that is not a `#` and has a density greater than that of at least one of the 3 neighboring cells on the layer below it (southwest, south, and southeast) that is not a `#`.
Stop procedure if no such choice exists.
2. Let *d* be a cell randomly sampled from these valid neighboring cells with the least densities.
3. Swap the values at *c* and *d*.
4. Repeat procedure until it has stopped.

# Example

Running the procedure on

```
A01
#10
020

```

might start out step 1 by selecting the `A`. There is only one cell below it with smaller density so the next grid would be

```
101
#A0
020

```

The procedure might continue on as

```
101 100 000 000
#00 #01 #11 #01
A20 A20 A20 A21

```

The last arrangement being stable.

# Challenge

Write a program that takes in a rectangular string of the 37 characters via stdin, command line, or function call. Initially, the given grid should be printed to stdout, but each time `Enter` is hit, one swap (step 3) should be done and the grid reprinted, separated from the last grid by an empty line. When the grid with no more possible swaps is printed (the end of the procedure) the program immediately ends.

* Grid dimensions will be 1×1 at minimum, and have no maximum size (as limited by `Int.Max` or computer memory). The grid is not always square.
* You can assume valid input. The grid will always be perfectly rectangular, containing only uppercase alphanumeric characters and `#`.
* You may use a key besides `Enter` if it is more convenient.
* Your program must follow \[something equivalent to\] the stabilization procedure, including using \[pseudo\]randomness for steps 1 and 2.
* In the input (but not the output) underscores (`_`) may be used instead of newlines.

# Scoring

This is code-golf, so the shortest code in bytes wins. There are bonuses however.

**Bonus 1 - Horizontal periodic boundary conditions: (minus 30 bytes)**

Instead of treating the left and right out of bounds areas as `#`, connect them with PBC. There should be an option in your code where changing something like `0` to `1` or `False` to `True` enables or disables the PBC.

**Bonus 2 - Graphics instead of text: (minus 100 bytes)**

Instead of using blocks of text, use images (of any common truecolor format). Represent `0...Z` with 36 distinct but related colors, e.g. a gradient from white to dark blue, and `#` with some other distinct color like dark red.

The program behaves the same way except now an image is either saved to a file (it may be the same file each time) or displayed to the screen for each grid swap in place of any textual output. The input may still be textual or some valid image, your choice.

Whether you do this bonus or not, giving output examples is highly encouraged.

# Answer
> 0 votes
## Python, 300 298 chars

```
import random
C=random.choice
R=raw_input
G=list(R().replace('_','\n'))
S=w=G.index('\n')
while S:
 print''.join(G);S=[];R()
 for i,c in enumerate(G):
    B=[(d,j)for j,d in enumerate(G[i+w:i+w+3])if'/'<d<c]
    if B:S+=[(i,[i+w+j for d,j in B if d==min(B)[0]])]
 if S:i,B=C(S);j=C(B);G[i],G[j]=G[j],G[i]

```

Run it like `cat inputfile - | fluid.py`. The input file should be a single line using `_` as a line separator.

---
Tags: code-golf, ascii-art, graphical-output
---


title: Give me a haircut!

text:
# Question
Title: Give me a haircut!
This is my head:

```
\         /-- -|
 /   -\  |  |  |
\      \ \  \  |
 --\    | \  | |
    / |--| / / |
 /|-  //--| /  |
| |  ||   //\  |
| \  /|  //  \ |

```

It consists of exactly eight hairs. My hair is too long. Please cut each individual strand to a length I specify.

## Input

The main attraction in this section is the actual head of hair. Here's a **graphical, color-coded representation, along with an animation**, for the lazy:

And here is a **full specification** for what a set of hairs is:

* The individual hairs, which we will call **strands**, will be made out of the `/`, `\`, `|`, and `-` ASCII characters, henceforth known as **atoms**.
* The entire **head** of hear (all of the strands combined) will be `c` columns by `r` rows, where `c` ≥ 1 and `r` ≥ 2.
* Each strand will...
    + start at the last row of the head (row `r` \- 1).
    + have a length `l` where `l` ≥ 2.
* Strands may be parsed with the following method:
    1. Start at the bottom of the strand. This will be a `/`, `|`, or `\` atom, which we will call the **root**. (Strands are parsed from left to right, ordered by the root.)
    2. Find the atom that points towards the root.
        + A `|` atom points up and down. A `-` atom points left and right (but can never point to the root since only roots can be in the bottom row). A `/` atom points left-down and up-right, and a `\` atom does the opposite.
        + There will always be exactly one atom that points towards the root atom.
    3. Find an *unused* atom (one that is not yet part of any strand) that points towards this atom and is also not below this atom (hair can't grow downwards, but sideways is okay).
        + If there are zero, you have reached the end of the strand!
        + If there is one, this is the next atom of the strand. Repeat step 3 with this atom. (This atom is now marked as "used" for the purposes of step 3, since it's part of a strand.)
        + There will never be multiple *unused* atoms here at any point in the head.

The **input format** will be:

* A head of hair. Can be input as-is (multiline input with literal newlines), or with a delimiter of your choice in place of newlines. Note that the head will always be a rectangle; i.e. trailing whitespace will be added as necessary (the weird straight line hair at the right is just to eliminate extra trailing whitespace to avoid confusion).
* A number ≥ 1 specifying how much hair to cut. This will be described in detail in the next section.

You may accept input to a function, use STDIN/STDOUT, etc. (anything reasonable).

## Output

Your output will be the head of hair with the haircut applied. To give a haircut, simply reduce the length of each strand of hair by the amount specified (which will always be 1 or greater), starting from the endpoint of the hair moving towards the root. However, *always* leave the root intact!

Here's a simple example. Say the input for the head is

```
\
 /
|
|

```

With a second input of `2`, you would cut two atoms from the strand and get a result of

```
|
|

```

And with an input of `42`, the output would just be

```
|

```

Note that whitespace before and after the head is completely irrelevant; you can trim extra newlines or you could add more padding. It doesn't matter, as long as the head remains intact. (You may do whatever you want with trailing whitespace as well.)

## Test Cases

For all test cases, the example presented at the very beginning of this post will be used.

Haircut length = 1:

```
          /-   |
 /    \  |     |
\      \ \  \  |
 --\    | \  | |
    / |--  / / |
  |-  //--| /  |
| |  ||   //   |
| \  /|  //  \ |

```

Length of 3:

```
         |
         \     |
 --\    | \    |
    / |--  / / |
  |-  //  | /  |
  |  ||   //   |
| \  /|  //  \ |

```

Length of 7:

```
  |-  /   |
  |  |    /    |
| \  /|  //  \ |

```

Length of 1337:

```
| \  /|  //  \ |

```

## Scoring

This is , so the shortest code in bytes will win!

# Answer
# JavaScript (E6) 195 ~~212 222 232~~

Using a recursive function R to find the path of each strand and marking the positions starting from 1 for the farest from the root. Then it's easy, in a second pass, to substitute the lower marked position with blanks.

```
F=(h,t,
   n=[...h],c=h.search('\n'),
   R=p=>[1,-1,c+2,c+1,c].some((d,i)=>n[p-d]=='--\\|/'[i]?n[p-=d]=1:0)&&R(p)+(R[p]=l++)
  )=>
  n.map((v,p)=>R[p]<t?' ':h[p],n.map((a,p)=>!h[p+c]&a>' '&&R(p,l=0))).join('')

```

**Test** in FireFox/FireBug console

```
head = "\\         /-- -|\n /   -\\  |  |  |\n\\      \\ \\  \\  |\n --\\    | \\  | |\n    / |--| / / |\n /|-  //--| /  |\n| |  ||   //\\  |\n| \\  /|  //  \\ |";
console.log(F(head,0))
console.log(F(head,1))
console.log(F(head,3))
console.log(F(head,7))
console.log(F(head, 1337))

```

*Output*

```
\         /-- -|
 /   -\  |  |  |
\      \ \  \  |
 --\    | \  | |
    / |--| / / |
 /|-  //--| /  |
| |  ||   //\  |
| \  /|  //  \ |

          /-   |
 /    \  |     |
\      \ \  \  |
 --\    | \  | |
    / |--  / / |
  |-  //--| /  |
| |  ||   //   |
| \  /|  //  \ |

         |
         \     |
 --\    | \    |
    / |--  / / |
  |-  //  | /  |
  |  ||   //   |
| \  /|  //  \ |

  |-  /   |
  |  |    /    |
| \  /|  //  \ |

| \  /|  //  \ |

```
> 12 votes

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


title: I'm feeling lucky

text:
# Question
Title: I'm feeling lucky
Write the shortest function that returns the content of the first result of a Google search ("I'm feeling lucky").

Example:

```
lucky('cat');

```

Might return something like:

```
<!DOCTYPE html>
<html>
  <head>
    <title>Cats are cool</title>
    <meta charset="utf-8" />
  </head>
  <body>
    <h1>CAAAAAAAAAAATSSSSSSSSSS!!!!!!!!</h1>
    <p>
      Cats are so cool!
    </p>
  </body>
</html>

```

# Answer
> 12 votes
# Bash, 46 bytes

```
l()(wget -UM -qO- "gogle.de/search?btnI&q=$1")

```

Uses the actual *I'm feeling lucky* feature, just like the other answers.

Gogle blacklists some user agents (including WGet's, cURL's and Java's), but **M** seems to work just fine.

# Answer
> 7 votes
# Ruby, 79 / 145

I borrowed the `btnI` trick from @rink.attendant.6 for this solution. Thanks Beta Decay for shortening it by 2 characters.

```
require'open-uri'
f=->q{URI(URI.escape"http://gogle.de/search?btnI&q="+q).read}

```

I also have a solution which actually gets the first result from the results page, which is 145 bytes.

```
require'open-uri'
f=->q{open(URI.extract(URI(URI.escape"http://google.com/search?q=#{q}").read.split('class="r"')[1])[0].split("&")[0]).read}

```

# Answer
> 5 votes
## PHP, ~~157~~ ~~105/87~~ ~~102/87~~ 100/85

### Using `file_get_contents`

```
<?php function l($q){return file_get_contents("https://google.ca/search?btnI&q=".rawurlencode($q));}

```

Without allowing for spaces in the search term it's only 87 characters:

```
<?php function l($q){return file_get_contents("https://google.ca/search?q=$q&btnI");}

```

### Original versions using cURL

I suppose that short array syntax can be used on PHP 5.4+:

```
<?php function l($q){$ch=curl_init("https://google.ca/search?btnI=1&q=".rawurlencode($q));curl_setopt_array($ch,[19913=>1,52=>1]);return curl_exec($ch);}

```

Otherwise it's five more characters with the normal array initializer, 162:

```
<?php function l($q){$ch=curl_init("https://google.ca/search?btnI=1&q=".rawurlencode($q));curl_setopt_array($ch,[19913=>1,52=>1]);return curl_exec($ch);}

```

Version that **does not allow spaces in the search term**: No need for URL encoding (138):

```
<?php function l($q){$ch=curl_init("https://google.ca/search?q=$q&btnI=1");curl_setopt_array($ch,[19913=>1,52=>1]);return curl_exec($ch);}

```
Ungolfed using constants
```
<?php
function l($q){
$ch = curl_init("https://google.ca/search?btnI=1&q=" . rawurlencode($q));
curl_setopt_array($ch, array(
  CURLOPT_RETURNTRANSFER => 1,
  CURLOPT_FOLLOWLOCATION => 1
  ));
return curl_exec($ch);
}

```

# Answer
> 4 votes
## C#, ~~183~~ ~~180~~ 178

This is my first time ever writing code in C# so it could probably use improvement. Feedback is welcome!

```
string l(string q){return System.Text.Encoding.UTF8.GetString((new System.Net.WebClient()).DownloadData("https://google.ca/search?btnI&q="+System.Web.HttpUtility.UrlEncode(q)));}

```

### Unminified

```
string l(string q) {
    return System.Text.Encoding.UTF8.GetString(
        (new System.Net.WebClient()).DownloadData(
            "https://google.ca/search?btnI&q=" + System.Web.HttpUtility.UrlEncode(q)
        )
    );
}

```

# Answer
> 3 votes
## CJam, 40 bytes

Thought, I'll finally give the `g` method a try

```
{"gogle.de/search?btnI&q="\S/"%20"*+g}:F

```

This creates a method/block `F` which can be used like

```
{"gogle.de/search?btnI&q="\S/"%20"*+g}:F; "cats and dogs"F

```

This is how functions work in CJam ..

Doesn't work in online interpreter, so you will have to download and use the Java one.

Note that Google denies all requests with Java user agent, so you will have to start CJam with an additional flag `-Dhttp.agent=M`

# Answer
> 2 votes
# Python 3 - 78

Uses `gogle.de` for brevity. Run as `f(query)`.

```
f=lambda x:__import__("requests").get("http://gogle.de/search?btnI&q="+x).text

```

If you want to have spaces in your query it's 98 characters.

```
f=lambda x:__import__("requests").get("http://gogle.de/search?btnI&q="+x.replace(" "," %20")).text

```

---
Tags: code-golf
---


# Question
Title: Write a square program that outputs the number of times it has been "unrolled"
Consider a square block of text, N characters wide by N tall, for some odd integer N greater than 1.

As an example let N = 5 and the text be:

```
MLKJI
NWVUH
OXYTG
PQRSF
ABCDE

```

Notice that this is the alphabet (besides Z) spiraled around counter-clockwise from the lower left corner. It's kind of like a rolled up carpet.

"Unrolling" the text by one quarter turn clockwise so `FGHI` are on the same level as `ABCDE` results in:

```
     PONM
     QXWL
     RYVK
     STUJ
ABCDEFGHI

```

This unrolling can be done 7 more times until the text is a single line:

```
         SRQP
         TYXO
         UVWN
ABCDEFGHIJKLM

             UTS
             VYR
             WXQ
ABCDEFGHIJKLMNOP

                WVU
                XYT
ABCDEFGHIJKLMNOPQRS

                   XW
                   YV
ABCDEFGHIJKLMNOPQRSTU

                     YX
ABCDEFGHIJKLMNOPQRSTUVW

                       Y
ABCDEFGHIJKLMNOPQRSTUVWX

ABCDEFGHIJKLMNOPQRSTUVWXY

```

# Challenge

The challenge is to write a program that is an N×N block of text that outputs the number of times it has "unrolled" by a quarter turn when it is rearranged into the unrolling patterns and run.

There are really two contests here: (hopefully it won't be too messy)

1. Do this with the smallest N. (down to a limit of N = 3)
2. Do this with the largest N. (no limit)

There will not be an accepted answer but the winner in each of these categories will receive at least 50 bounty rep from me. In case of ties the oldest answers win.

# Example

If your code block is

```
MyP
rog
ram

```

running it as is should output 0.

Running

```
   rM
   oy
ramgP

```

should output 1.

Running

```
     or
ramgPyM

```

should output 2.

Running

```
       o
ramgPyMr

```

should output 3.

Finally, running `ramgPyMro` should output 4.

# Details

* The output should be printed to stdout (or the closest alternative) by itself. There is no input.
* You may only use printable ASCII (hex codes 20 to 7E, that includes space) in your code.
* Spaces fill the empty space in the unrolling arrangements. (Unless you're unrolling to the left.)
* Only the arrangements from completely square to completely flat need to have valid output. No other arrangements will be run.
* You may not read your own source.
* You may use comments.
* N = 1 is excluded since in many languages the program `0` would work.
* If desired you may unroll to the left rather than the right. So e.g.

```
MyP
rog
ram

```

becomes

```
Pg
yo
Mrram

```

and so on. No extra spaces are added when rolling this way. The lines just end

(Related: Write a Rectangular Program that Outputs the Number of Times it was Rotated)

# Answer
### Golfscript, N \<- \[5,7..\]

```
.   .
 . .
 ..
.  .#
],9\-

```

Fully unrolled:

```
],9\-#  .   .  .  . . ...

```

Explanation:

* `.` (multiple times) - duplicate the input
* `]` \- collect the stack into a single array
* `,` \- take its length
* `9\-` \- subtract it from 9
* `#` \- line comment

Whitespace is a NOP, but any other NOP would have worked just as well.

Fully rolled up, it uses nine copies of the input (contents ignored) as the stack; 9 - 9 = 0; it has not been unrolled.

Each unroll hides one more dot (duplicate) behind the comment, shrinking the stack once, incrementing the output.

Fully unrolled, it uses only the input (contents ignored) as the stack; 9 - 1 = 8; it has been unrolled 8 times.

The same approach works for any N \> 4: Change `9` to the appropriate value of 2\*N+1, then extend the pattern of dots (duplicate) using the same spiral pattern that ensures exactly one dot gets unrolled during each unroll.
> 27 votes

# Answer
## GolfScript, N = 4

This one right rolls as original spec.

```
.. .
...#
.#.~
],8-

```

Here are the unrolls:

```
    ...
    #..
    ..
],8-~#.

       .#.
       ...
],8-~#. ..

          ..
          .#
],8-~#. ....

            ..
],8-~#. ....#.

              .
],8-~#. ....#..

],8-~#. ....#...

```

Try it here
> 13 votes

# Answer
# APL, N = 3

```
201
340
5|0

```

Unrolled:

```
   32
   40
5|001

     43
5|00102

       4
5|001023

5|0010234

```

Try it online.

It calculates the remainder of that number divided by 5. Only the result of last line is printed.

# APL, N = 2

```
⍬∞
≡0

```

Unrolled:

```
  ⍬
≡0∞

≡0∞⍬

```

Try it online.

returns the depth (not to be confused with the dimension or length) of an array:

* `0` is not an array. So the depth is 0.
* `0∞` is an array with two items `0` and  (infinity). It has depth 1.
* `0∞⍬` has another item , which is an empty array with depth 1. So `0∞⍬` has depth 2.

These two programs also works in the online interpreter. I'm not sure if the later one is syntactically correct.

```
⍬0
≡∞

```

```
⍬¯
≡0

```

# APL, for any N \>= 4

For N = 4:

```
∞  ∞
 ∞∞
∞ ∞
⍴1↓∞

```

Fully unrolled:

```
⍴1↓∞  ∞  ∞ ∞ ∞∞∞

```

For N = 5:

```
∞   ∞
 ∞ ∞
 ∞∞
∞  ∞
⍴1↓ ∞

```

Fully unrolled:

```
⍴1↓ ∞   ∞   ∞  ∞  ∞ ∞ ∞∞∞

```

`1↓` removes an item in the array. It also returns the empty array if the argument is scalar.  gets the array length.
> 9 votes

---
Tags: code-challenge, printable-ascii, source-layout
---