title: Finding sum-free partitions

text:
# Question
Title: Finding sum-free partitions
## Executive summary

Given input `k`, find a partition of integers `1` to `n` into `k` sum-free subsets for the largest `n` you can within 10 minutes.

## Background: Schur numbers

A set `A` is *sum-free* if its self-sum `A + A = { x + y | x, y in A}` has no elements in common with it.

For every positive integer `k` there is a largest integer `S(k)` such that the set `{1, 2, ..., S(k)}` can be partitioned into `k` sum-free subsets. This number is called the kth Schur number (OEIS A045652).

For example, `S(2) = 4`. We can partition `{1, 2, 3, 4}` as `{1, 4}, {2, 3}`, and that is the unique partition into two sum-free subsets, but we can't now add a `5` to either part.

## Challenge

Write a **deterministic program** which does the following:

* Take a positive integer `k` as input
* Write the current Unix timestamp to stdout
* Outputs a sequence of partitions of `1` to `n` into `k` sum-free subsets for increasing `n`, following each sequence with the current Unix timestamp.

The winner will be the program which prints a partition for the largest `n` within 10 minutes on my computer when given input `5`. Ties will be broken by the quickest time to find a partition for the largest `n`, averaged over three runs: that's why the output should include timestamps.

Important details:

* I have Ubuntu Precise, so if your language is not supported I will be unable to score it.
* I have an Intel Core2 Quad CPU, so if you want to use multithreading there's no point using more than 4 threads.
* If you want me to use any particular compiler flags or implementation, document that clearly in your answer.
* You shall not special-case your code to handle the input `5`.
* You are not required to output every improvement you find. E.g. for input `2` you could output only the partition for `n = 4`. However, if you don't output anything in the first 10 minutes then I will score that as `n = 0`.

# Answer
> 8 votes
## Python 3, sort by greatest number, n = ~~92~~ 121

**Thanks to Martin Büttner for a suggestion that unexpectedly improved the maximum `n` reached.**

Last output:

```
[2, 3, 11, 12, 29, 30, 38, 39, 83, 84, 92, 93, 110, 111, 119, 120]
[1, 4, 10, 13, 28, 31, 37, 40, 82, 85, 91, 94, 109, 112, 118, 121]
[5, 6, 7, 8, 9, 32, 33, 34, 35, 36, 86, 87, 88, 89, 90, 113, 114, 115, 116, 117]
[14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108]
[41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81]

```

The algorithm is the same as my previous answer, quoted below:

> There are k bins that have both the numbers in it so far and the numbers that can't go in it anymore. At each depth in the iteration (it's basically a depth-first search), the bin ordering is shuffled and the next number (nextN) is (sequentially) put into the bins that can take it and then goes one step deeper. If there are none, it returns, backing up one step.

...with one exception: the bin ordering is *not* shuffled. Instead, it is *sorted* in such a way that the bins with the *greatest number* come first. This reached `n = 121` in 8 seconds!

Code:

```
from copy import deepcopy
from random import shuffle, seed
from time import clock, time
global maxN
maxN = 0
clock()

def search(k,nextN=1,sets=None):
    global maxN
    if clock() > 600: return

    if nextN == 1: #first iteration
        sets = []
        for i in range(k):
            sets.append([[],[]])

    sets.sort(key=lambda x:max(x[0]or[0]), reverse=True)
    for i in range(k):
        if clock() > 600: return
        if nextN not in sets[i][1]:
            sets2 = deepcopy(sets)
            sets2[i][0].append(nextN)
            sets2[i][1].extend([nextN+j for j in sets2[i][0]])
            nextN2 = nextN + 1

            if nextN > maxN:
                maxN = nextN
                print("New maximum!",maxN)
                for s in sets2: print(s[0])
                print(time())
                print()

            search(k, nextN2, sets2)

search(5)

```

# Answer
> 7 votes
# Python 3, 121, \< 0.001s

Improved heuristic thanks to Martin Buttner means we don't even need randomness.

Output:

```
1447152500.9339304
[1, 4, 10, 13, 28, 31, 37, 40, 82, 85, 91, 94, 109, 112, 118, 121]
[2, 3, 11, 12, 29, 30, 38, 39, 83, 84, 92, 93, 110, 111, 119, 120]
[5, 6, 7, 8, 9, 32, 33, 34, 35, 36, 86, 87, 88, 89, 90, 113, 114, 115, 116, 117]
[14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108]
[41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81]
1447152500.934646 121

```

Code:

```
from copy import deepcopy
from random import seed, randrange
from time import clock, time
from cProfile import run

n = 5

seed(0)

def heuristic(bucket):
    return len(bucket[0]) and bucket[0][-1]

def search():
    best = 0
    next_add = 1
    old_add = 0
    lists = [[[],set()] for _ in range(n)]
    print(time())
    while clock() < 600 and next_add != old_add:
        old_add = next_add
        lists.sort(key=heuristic, reverse=True)
        for i in range(n):
            if next_add not in lists[i][1]:
                lists[i][0].append(next_add)
                lists[i][1].update([next_add + old for old in lists[i][0]])
                if next_add > best:
                    best = next_add
                next_add += 1
                break

    for l in lists:
        print(l[0])
    print(time(), next_add-1, end='\n\n')

search()

```

---

# Python 3, 112

## Sort by sum of first 2 elements + skew

```
[40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79]
[7, 8, 9, 10, 11, 12, 13, 27, 28, 29, 30, 31, 32, 33, 80, 81, 82, 83, 84, 85, 86, 100, 101, 102, 103, 104, 105, 106]
[3, 4, 14, 19, 21, 26, 36, 37, 87, 92, 94, 99, 109, 110]
[2, 5, 16, 17, 20, 23, 24, 35, 38, 89, 90, 96, 97, 108, 111]
[1, 6, 15, 18, 22, 25, 34, 39, 88, 91, 93, 95, 98, 107, 112]
1447137688.032085 138.917074 112

```

I copied El'endia Starman's data structure, which consists of a list of pairs, where the first element of the pair is the elements in that bucket, and the second is the sums of that bucket.

I start with the same "track what sums are availible" approach. My sorting heuristic is simply the sum of the smallest two elements in a given list. I also add a small random skew to try different possibilities.

Each iteration simply places each the new number in the first avalible bin, similar to random greedy. Once this fails, it simply restarts.

```
from copy import deepcopy
from random import seed, randrange
from time import clock, time

n = 5

seed(0)

def skew():
    return randrange(9)

best = 0
next_add = old_add = 1
while clock() < 600:
    if next_add == old_add:
        lists = [[[],[]] for _ in range(n)]
        next_add = old_add = 1
    old_add = next_add
    lists.sort(key=lambda x:sum(x[0][:2]) + skew(), reverse=True)
    for i in range(n):
        if next_add not in lists[i][1]:
            lists[i][0].append(next_add)
            lists[i][1].extend([next_add + old for old in lists[i][0]])
            if next_add > best:
                best = next_add
                for l in lists:
                    print(l[0])
                print(time(), clock(), next_add, end='\n\n')
            next_add += 1
            break

```

# Answer
> 7 votes
# Java 8, n = 142 144

Last output:

```
@ 0m 31s 0ms
n: 144
[9, 12, 17, 20, 22, 23, 28, 30, 33, 38, 41, 59, 62, 65, 67, 70, 72, 73, 75, 78, 80, 83, 86, 91, 107, 115, 117, 122, 123, 125, 128, 133, 136]
[3, 8, 15, 24, 25, 26, 31, 35, 45, 47, 54, 58, 64, 68, 81, 87, 98, 100, 110, 114, 119, 120, 121, 130, 137, 142]
[5, 13, 16, 19, 27, 36, 39, 42, 48, 50, 51, 94, 95, 97, 103, 106, 109, 112, 118, 126, 129, 132, 138, 140, 141]
[2, 6, 11, 14, 34, 37, 44, 53, 56, 61, 69, 76, 79, 84, 89, 92, 101, 104, 108, 111, 124, 131, 134, 139, 143, 144]
[1, 4, 7, 10, 18, 21, 29, 32, 40, 43, 46, 49, 52, 55, 57, 60, 63, 66, 71, 74, 77, 82, 85, 88, 90, 93, 96, 99, 102, 105, 113, 116, 127, 135]

```

Performs a seeded random search distributed over 4 threads. When it can't find a partition to fit `n` in it tries to free up space for `n` in one partition at a time by dumping as much as it can out of it into the other partitions.

edit: tweaked the algorithm for freeing up space for `n`, also added ability to go back to a previous choice and choose again.

note: the output is not strictly deterministic because there are multiple threads involved and they can end up updating the best `n` found so far in jumbled order; the eventual score of 144 is deterministic though and is reached fairly quickly: 30 seconds on my computer.

Code is:

```
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;

public class SumFree {

    private static int best;

    public static void main(String[] args) {
        int k = 5; // Integer.valueOf(args[0]);
        int numThreadsPeterTaylorCanHandle = 4;

        long start = System.currentTimeMillis();
        long end = start + TimeUnit.MINUTES.toMillis(10);

        System.out.println(start);

        Random rand = new Random("Lucky".hashCode());
        for (int i = 0; i < numThreadsPeterTaylorCanHandle; i++) {
            new Thread(() -> search(k, new Random(rand.nextLong()), start, end)).start();
        }
    }

    private static void search(int k, Random rand, long start, long end) {
        long now = System.currentTimeMillis();
        int localBest = 0;

        do {
            // create k empty partitions
            List<Partition> partitions = new ArrayList<>();
            for (int i = 0; i < k; i++) {
                partitions.add(new Partition());
            }

            Deque<Choice> pastChoices = new ArrayDeque<>();
            int bestNThisRun = 0;

            // try to fill up the partitions as much as we can
            for (int n = 1;; n++) {
                // list of partitions that can fit n
                List<Partition> partitionsForN = new ArrayList<>(k);
                for (Partition partition : partitions) {
                    if (!partition.sums.contains(n)) {
                        partitionsForN.add(partition);
                    }
                }

                // if we can't fit n anywhere then try to free up some space
                // by rearranging partitions
                Set<Set<Set<Integer>>> rearrangeAttempts = new HashSet<>();
                rearrange: while (partitionsForN.size() == 0 && rearrangeAttempts
                        .add(partitions.stream().map(Partition::getElements).collect(Collectors.toSet()))) {

                    Collections.shuffle(partitions, rand);
                    for (int candidateIndex = 0; candidateIndex < k; candidateIndex++) {
                        // partition we will try to free up
                        Partition candidate = partitions.get(candidateIndex);
                        // try to dump stuff that adds up to n into the other
                        // partitions
                        List<Integer> badElements = new ArrayList<>(candidate.elements.size());
                        for (int candidateElement : candidate.elements) {
                            if (candidate.elements.contains(n - candidateElement)) {
                                badElements.add(candidateElement);
                            }
                        }
                        for (int i = 0; i < k && !badElements.isEmpty(); i++) {
                            if (i == candidateIndex) {
                                continue;
                            }

                            Partition other = partitions.get(i);

                            for (int j = 0; j < badElements.size(); j++) {
                                int candidateElement = badElements.get(j);
                                if (!other.sums.contains(candidateElement)
                                        && !other.elements.contains(candidateElement + candidateElement)) {
                                    boolean canFit = true;
                                    for (int otherElement : other.elements) {
                                        if (other.elements.contains(candidateElement + otherElement)) {
                                            canFit = false;
                                            break;
                                        }
                                    }

                                    if (canFit) {
                                        other.elements.add(candidateElement);
                                        for (int otherElement : other.elements) {
                                            other.sums.add(candidateElement + otherElement);
                                        }
                                        candidate.elements.remove((Integer) candidateElement);
                                        badElements.remove(j--);
                                    }
                                }
                            }
                        }

                        // recompute the sums
                        candidate.sums.clear();
                        List<Integer> elementList = new ArrayList<>(candidate.elements);
                        int elementListSize = elementList.size();
                        for (int i = 0; i < elementListSize; i++) {
                            int ithElement = elementList.get(i);
                            for (int j = i; j < elementListSize; j++) {
                                int jthElement = elementList.get(j);
                                candidate.sums.add(ithElement + jthElement);
                            }
                        }

                        // if candidate can now fit n then we can go on
                        if (!candidate.sums.contains(n)) {
                            partitionsForN.add(candidate);
                            break rearrange;
                        }
                    }
                }

                // if we still can't fit in n, then go back in time to our last
                // choice (if it's saved) and this time choose differently
                if (partitionsForN.size() == 0 && !pastChoices.isEmpty() && bestNThisRun > localBest - localBest / 3) {
                    Choice lastChoice = pastChoices.peek();
                    partitions = new ArrayList<>(lastChoice.partitions.size());
                    for (Partition partition : lastChoice.partitions) {
                        partitions.add(new Partition(partition));
                    }
                    n = lastChoice.n;
                    Partition partition = lastChoice.unchosenPartitions
                            .get(rand.nextInt(lastChoice.unchosenPartitions.size()));
                    lastChoice.unchosenPartitions.remove(partition);
                    partition = partitions.get(lastChoice.partitions.indexOf(partition));
                    partition.elements.add(n);
                    for (int element : partition.elements) {
                        partition.sums.add(element + n);
                    }
                    if (lastChoice.unchosenPartitions.size() == 0) {
                        pastChoices.pop();
                    }
                    continue;
                }

                if (partitionsForN.size() > 0) {
                    // if we can fit in n somewhere,
                    // pick that somewhere randomly
                    Partition chosenPartition = partitionsForN.get(rand.nextInt(partitionsForN.size()));
                    // if we're making a choice then record it so that we may
                    // return to it later if we get stuck
                    if (partitionsForN.size() > 1) {
                        Choice choice = new Choice();
                        choice.n = n;
                        for (Partition partition : partitions) {
                            choice.partitions.add(new Partition(partition));
                        }
                        for (Partition partition : partitionsForN) {
                            if (partition != chosenPartition) {
                                choice.unchosenPartitions.add(choice.partitions.get(partitions.indexOf(partition)));
                            }
                        }
                        pastChoices.push(choice);

                        // only keep 3 choices around
                        if (pastChoices.size() > 3) {
                            pastChoices.removeLast();
                        }
                    }

                    chosenPartition.elements.add(n);
                    for (int element : chosenPartition.elements) {
                        chosenPartition.sums.add(element + n);
                    }
                    bestNThisRun = Math.max(bestNThisRun, n);
                }

                if (bestNThisRun > localBest) {
                    localBest = Math.max(localBest, bestNThisRun);

                    synchronized (SumFree.class) {
                        now = System.currentTimeMillis();

                        if (bestNThisRun > best) {
                            // sanity check
                            Set<Integer> allElements = new HashSet<>();
                            for (Partition partition : partitions) {
                                for (int e1 : partition.elements) {
                                    if (!allElements.add(e1)) {
                                        throw new RuntimeException("Oops!");
                                    }
                                    for (int e2 : partition.elements) {
                                        if (partition.elements.contains(e1 + e2)) {
                                            throw new RuntimeException("Oops!");
                                        }
                                    }
                                }
                            }
                            if (allElements.size() != bestNThisRun) {
                                throw new RuntimeException("Oops!" + allElements.size() + "!=" + bestNThisRun);
                            }

                            best = bestNThisRun;
                            System.out.printf("@ %dm %ds %dms\n", TimeUnit.MILLISECONDS.toMinutes(now - start),
                                    TimeUnit.MILLISECONDS.toSeconds(now - start) % 60, (now - start) % 1000);
                            System.out.printf("n: %d\n", bestNThisRun);
                            for (Partition partition : partitions) {
                                // print in sorted order since everyone else
                                // seems to to that
                                List<Integer> partitionElementsList = new ArrayList<>(partition.elements);
                                Collections.sort(partitionElementsList);
                                System.out.println(partitionElementsList);
                            }
                            System.out.printf("timestamp: %d\n", now);
                            System.out.println("------------------------------");
                        }
                    }
                }

                if (partitionsForN.size() == 0) {
                    break;
                }
            }
        } while (now < end);
    }

    // class representing a partition
    private static final class Partition {

        // the elements of this partition
        Set<Integer> elements = new HashSet<>();

        // the sums of the elements of this partition
        Set<Integer> sums = new HashSet<>();

        Partition() {
        }

        Partition(Partition toCopy) {
            elements.addAll(toCopy.elements);
            sums.addAll(toCopy.sums);
        }

        Set<Integer> getElements() {
            return elements;
        }
    }

    private static final class Choice {
        int n;
        List<Partition> partitions = new ArrayList<>();
        List<Partition> unchosenPartitions = new ArrayList<>();
    }
}

```

# Answer
> 5 votes
## C, Random Greedy, n = 91

Just to provide a baseline solution, this iterates over `n`, keeping track of the bins and their sums and adds `n` to a random bin where it doesn't appear as a sum yet. It terminates once `n` appears in all `k` sums, and if the resulting `n` was better than any previous attempt, prints it to STDOUT.

The input `k` is provided via a command-line argument. The maximum possible `k` is currently hardcoded to 10 because I was too lazy add dynamic memory allocation, but that could be fixed easily.

I guess I could go hunting for a better seed now, but this answer is probably not particularly competitive anyway, so meh.

Here is the partition for `n = 91`:

```
1 5 12 18 22 29 32 35 46 48 56 59 62 69 72 76 79 82 86 89
2 3 10 11 16 17 25 30 43 44 51 52 57 64 71 83 84 90 91
6 8 13 15 24 31 33 38 40 42 49 54 61 63 65 77 81 88
9 14 19 21 27 34 37 45 60 67 70 73 75 78 80 85
4 7 20 23 26 28 36 39 41 47 50 53 55 58 66 68 74 87

```

And finally, here is the code:

```
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_K 10
#define MAX_N 1024

int main(int argc, char **argv) {
    if (argc < 2)
    {
        printf("Pass in k as a command-line argument");
        return 1;
    }

    printf("%u\n", (unsigned)time(NULL));

    int k = atoi(argv[1]);

    int sizes[MAX_K];
    int bins[MAX_K][MAX_N];
    int sums[MAX_K][2*MAX_N];
    int selection[MAX_K];
    int available_bins;

    int best = 0;

    srand(1447101176);

    while (1)
    {
        int i,j;
        for (i = 0; i < k; ++i)
            sizes[i] = 0;
        for (i = 0; i < k*MAX_N; ++i)
            bins[0][i] = 0;
        for (i = 0; i < k*MAX_N*2; ++i)
            sums[0][i] = 0;
        int n = 1;
        while (1)
        {
            available_bins = 0;
            for (i = 0; i < k; ++i)
                if (!sums[i][n])
                {
                    selection[available_bins] = i;
                    ++available_bins;
                }

            if (!available_bins) break;

            int bin = selection[rand() % available_bins];

            bins[bin][sizes[bin]] = n;
            ++sizes[bin];
            for (i = 0; i < sizes[bin]; ++i)
                sums[bin][bins[bin][i] + n] = 1;

            ++n;
        }

        if (n > best)
        {
            best = n;
            for (i = 0; i < k; ++i)
            {
                for (j = 0; j < sizes[i]; ++j)
                    printf("%d ", bins[i][j]);
                printf("\n");
            }
            printf("%u\n", (unsigned)time(NULL));
        }
    }

    return 0;
}

```

# Answer
> 3 votes
# C++, 135

```
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int> > subset;
vector<int> len, tmp;
set<int> sums;

bool is_sum_free_with(int elem, int subnr) {
    sums.clear();
    sums.insert(elem+elem);
    for(int i=0; i<len[subnr]; ++i) {
        sums.insert(subset[subnr][i]+elem);
        for(int j=i; j<len[subnr]; ++j) sums.insert(subset[subnr][i]+subset[subnr][j]);
    }
    if(sums.find(elem)!=sums.end()) return false;
    for(int i=0; i<len[subnr]; ++i) if(sums.find(subset[subnr][i])!=sums.end()) return false;
    return true;
}

int main()
{
    int k = 0; cin >> k;

    int start=time(0);
    cout << start << endl;

    int allmax=0, cnt=0;
    srand(0);

    do {
        len.clear();
        len.resize(k);
        subset.clear();
        subset.resize(k);
        for(int i=0; i<k; ++i) subset[i].resize((int)pow(3, k));

        int n=0, last=0, c, y, g, h, t, max=0;
        vector<int> p(k);

        do {
            ++n;
            c=-1;
            for(int i=0; i++<k; ) {
                y=(last+i)%k;
                if(is_sum_free_with(n, y)) p[++c]=y;
            }

            if(c<0) --n;

            t=n;

            while(c<0) {
                g=rand()%k;
                h=rand()%len[g];
                t=subset[g][h];
                for(int l=h; l<len[g]-1; ++l) subset[g][l]=subset[g][l+1];
                --len[g];
                for(int i=0; i++<k; ) {
                    y=(g+i)%k;
                    if(is_sum_free_with(t, y) && y!=g) p[++c]=y;
                }
                if(c<0) subset[g][len[g]++]=t;
            }

            c=p[rand()%(c+1)];
            subset[c][len[c]++]=t;

            last=c;

            if(n>max) {
                max=n;
                cnt=0;
                if(n>allmax) {
                    allmax=n;
                    for(int i=0; i<k; ++i) {
                        tmp.clear();
                        for(int j=0; j<len[i]; ++j) tmp.push_back(subset[i][j]);
                        sort(tmp.begin(), tmp.end());
                        for(int j=0; j<len[i]; ++j) cout << tmp[j] << " ";
                        cout << endl;
                    }
                    cout << time(0) << " " << time(0)-start << " " << allmax << endl;
                }

            }

        } while(++cnt<50*n && time(0)-start<600);

        cnt=0;

    } while(time(0)-start<600);

    return 0;
}

```

Appends the next n to a randomly chosen subset. If that's not possible it removes random numbers from subsets and appends them to others in the hope that that enables appending n somewhere.

I prototyped this in awk, and because it looked promising, I translated it into C++ to speed it up. Using a `std::set` should even speed it up more.

### Output for n=135 (after around 230 seconds on my \[old\] machine)

```
2 6 9 10 13 17 24 28 31 35 39 42 43 46 50 57 61 68 75 79 90 94 97 101 105 108 119 123 126 127 130 131 134
38 41 45 48 51 52 55 56 58 59 62 64 65 66 67 69 70 71 72 74 78 80 81 84 85 87 88 91 95 98
5 12 15 16 19 22 23 25 26 29 33 36 73 83 93 100 103 107 110 111 113 114 117 120 121 124
1 4 11 14 21 27 34 37 40 47 53 60 76 86 89 96 99 102 109 112 115 122 125 132 135
3 7 8 18 20 30 32 44 49 54 63 77 82 92 104 106 116 118 128 129 133

```

I didn't recheck the validity, but it should be alright.

# Answer
> 2 votes
## Python 3, random greedy, n = 61

Last output:

```
[5, 9, 13, 20, 24, 30, 32, 34, 42, 46, 49, 57, 61]
[8, 12, 14, 23, 25, 44, 45, 47, 54]
[2, 6, 7, 19, 22, 27, 35, 36, 39, 40, 52, 53, 56]
[3, 10, 15, 16, 17, 29, 37, 51, 55, 59, 60]
[1, 4, 11, 18, 21, 26, 28, 31, 33, 38, 41, 43, 48, 50, 58]

```

This uses effectively the same algorithm as Martin Büttner's, but I developed it independently.

There are `k` bins that have both the numbers in it so far and the numbers that can't go in it anymore. At each depth in the iteration (it's basically a depth-first search), the bin ordering is shuffled and the next number (`nextN`) is (sequentially) put into the bins that can take it and then goes one step deeper. If there are none, it returns, backing up one step.

```
from copy import deepcopy
from random import shuffle, seed
from time import clock, time
global maxN
maxN = 0
clock()
seed(0)

def search(k,nextN=1,sets=None):
    global maxN
    if clock() > 600: return

    if nextN == 1: #first iteration
        sets = []
        for i in range(k):
            sets.append([[],[]])

    R = list(range(k))
    shuffle(R)
    for i in R:
        if clock() > 600: return
        if nextN not in sets[i][1]:
            sets2 = deepcopy(sets)
            sets2[i][0].append(nextN)
            sets2[i][1].extend([nextN+j for j in sets2[i][0]])
            nextN2 = nextN + 1

            if nextN > maxN:
                maxN = nextN
                print("New maximum!",maxN)
                for s in sets2: print(s[0])
                print(time())
                print()

            search(k, nextN2, sets2)

search(5)

```

# Answer
> 2 votes
# Python, n = 31

```
import sys
k = int(sys.argv[1])

for i in range(k):
    print ([2**i * (2*j + 1) for j in range(2**(k - i - 1))])

```

Ok, so it's obvisouly not a winner, but I felt it belonged here anyway. I've taken the liberty not to include timestamps, since it terminates instantaneously, and since it's not a real contender.

First, note that the sum of any two odd numbers is even, so we can dump all the odd numbers in the first block. Then, since all the remaining numbers are even, we can divide them by 2. Once again, we can throw all the resulting odd numbers in the second block (after re-multiplying them by 2), divide the remaining numbers by 2 (i.e., by 4 overall), throw the odd ones in the third block (after re-multiplying them by 4), and so on... Or, to put in words you guys understand, we put all the numbers whose least-significant set bit is the first bit in the first block, all the numbers whose least-significant set bit is the second bit in the second block, and so on...

For *k* blocks, we run into trouble once we reach *n* = 2*k*, since the least-significant set bit of *n* is
the (*k* \+ 1)-th bit, which doesn't correspond to any block. In other words, this scheme works up
to *n* = 2*k* \- 1. So, while for *k* = 5 we only get a meager *n = 31*, this number grows exponentially with *k*. It also establishes that *S*(*k*) ≥ 2*k* \- 1 (but we can actually find a better lower limit than that quite easily.)

For reference, here's the result for *k* = 5:

```
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
[2, 6, 10, 14, 18, 22, 26, 30]
[4, 12, 20, 28]
[8, 24]
[16]

```

---
Tags: code-challenge, arithmetic, combinatorics, set-partitions
---


# Question
Title: Variant of racetrack with exact finishing point and zero terminal velocity
# Introduction

The challenge is a very interesting variant of the game racetrack and those two challenges:

Source of this challenge is here (in German): c't-Racetrack

This challenge is especially interesting (and different from the two abovementioned challenges) because it combines a huge search-space with some exact conditions that have to be met. Because of the huge search-space exhaustive search techniques are hard to use, because of the exact conditions approximate methods are also not easily usable. Because of this unique combination (plus the underlying intuition from physics) the problem is fascinating (and everything in connection with racing cars is fascinating anyway ;-)

# Challenge

Have a look at the following racetrack (source):

You have to start at `(120,180)` and finish exactly at `(320,220)` ("Ziel" in German) without touching one of the walls.

The car is controlled by acceleration vectors of the form `(a_x,a_y)` \- as an example:

```
(8,-6)
(10,0)
(1,9)

```

The first number is the acceleration for the x-vector, the second for the y-vector. They have to be integers because you are only allowed to use the integer points on the grid. Additionally the following condition has to be met:

```
a_x^2 + a_y^2 <= 100,

```

which means that acceleration in any direction has to be below or equal to `10`.

To see how it works have a look at the following picture (source):

As an example: Starting from `(120,180)` you accelerate by `8` in x-direction and by `-6` in y-direction. For the next step this is your velocity where you add your acceleration `(10,0)` to get (physically correct) your next resulting movement (to point `(146,168)`. The resulting movement is what counts when it comes to examining whether you touched one of the walls. In the next step you again add your next acceleration vector to your current velocity to get the next movement and so on. So at every step your car has a position and a velocity. (In the illustrative picture above the blue arrows are for the velocity, the orange arrows for acceleration and the dark red arrows for the resulting movement.)

As an additional condition you have to have `(0,0)` terminal velocity when you are on the finishing point `(320,220)`.

The output has to be a list of acceleration vectors in the abovementioned form.

The winner is the one who provides a program which finds a solution with the fewest acceleration vectors.

*Tiebreaker*
Additionally it would be great if you can show that this is an optimal solution and whether this is the only optimal solution or whether there are several optimal solutions (and which they are).

It would also be good if you could give a general outline of how your algorithm works and comment the code so that we can understand it.

I have a program which checks whether any given solution is valid and I will give feedback.

*Addendum*
You can use any programming language but I would be especially delighted if somebody used R because I use it a lot in my day job and somehow got used to it :-)

*Addendum II*
For the first time I started a bounty - hopefully this get's the ball rolling (or better: get's the car driving :-)

# Answer
# Python, 24 steps (work in progress)

The idea was to solve the continuous problem first, vastly reducing the search space, and then quantize the result to the grid (by just rounding to the nearest gridpoint and searching the surrounding 8 squares)

I parametrize the path as a sum of trigonometric functions (unlike polynomials, they dont diverge and are easier to keep in check). I also control the velocity directly instead of the acceleration, because its easier to enforce the boundary condition by simply multiplying a weighting function that tends to 0 at the end.
My objective function consists of
-exponential score for acceleration \> 10
-polynomial score for euclidean distance between the last point and the target
-high constant score for each intersection with a wall, decreasing towards the edges of the wall

To minimize the score, i throw it all into Nelder-Mead optimization and wait a few seconds. The algorithm always succeeds in getting to the end, stopping there and not exceeding the maximum acceleration, but it has troubles with walls. The path either teleports through corners and gets stuck there, or stops next to a wall with the goal just across (left image)

During testing, i got lucky and found a path that was squiggled in a promising way (right image) and after tweaking the parameters some more i could use it as a starting guess for a successful optimization.

**Quantization**
After finding a parametric path, it was time to remove the decimal points. Looking at the 3x3 neighborhood reduces the search space from roughly 300^N to 9^N, but its still too big and boring to implement. Before i went down this road, i tried adding a "Snap to Grid" term to the objective function (the commented parts). A hundred more steps of optimization with the updated objective and simply rounding was enough to get the solution.

> \[(9, -1), (4, 0), (1, 1), (2, 2), (-1, 2), (-3, 4), (-3, 3), (-2, 3), (-2, 2), ( -1, 1), (0, 0), (1, -2), (2, -3), (2, -2), (3, -5), (2, -4), (1, -5), (-2, -3), (-2, -4), (-3, -9), (-4, -4), (-5, 8), (-4, 8), (5, 8)\]

The number of steps was fixed and not part of optimization, but since we have an analytical description of the path, (and since the maximal acceleration is well below 10) we can reuse it as a starting point for further optimization with a smaller number of timesteps

```
from numpy import *
from scipy.optimize import fmin
import matplotlib.pyplot as plt
from matplotlib.collections import LineCollection as LC

walls = array([[[0,0],[500,0]],   # [[x0,y0],[x1,y1]]
        [[500,0],[500,400]],
        [[500,400],[0,400]],
        [[0,400],[0,0]],

        [[200,200],[100,200]],
        [[100,200],[100,100]],
        [[100,100],[200,100]],

        [[250,300],[250,200]],

        [[300,300],[300,100]],
        [[300,200],[400,200]],
        [[300,100],[400,100]],

        [[100,180],[120, 200]], #debug walls
        [[100,120],[120, 100]],
        [[300,220],[320, 200]],
        #[[320,100],[300, 120]],
])

start = array([120,180])
goal = array([320,220])

###################################
# Boring stuff below, scroll down #
###################################
def weightedintersection2D(L1, L2):
    # http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
    p = L1[0]
    q = L2[0]
    r = L1[1]-L1[0]
    s = L2[1]-L2[0]
    d = cross(r,s)
    if d==0: # parallel
        if cross(q-p,r)==0: return 1 # overlap
    else:
        t = cross(q-p,s)*1.0/d
        u = cross(q-p,r)*1.0/d
        if 0<=t<=1 and 0<=u<=1: return 1-0*abs(t-.5)-1*abs(u-.5) # intersect at p+tr=q+us
    return 0

def sinsum(coeff, tt):
    '''input: list of length 2(2k+1),
    first half for X-movement, second for Y-movement.
    Of each, the first k elements are sin-coefficients
    the next k+1 elements are cos-coefficients'''
    N = len(coeff)/2
    XS = [0]+list(coeff[:N][:N/2])
    XC =     coeff[:N][N/2:]
    YS = [0]+list(coeff[N:][:N/2])
    YC =     coeff[N:][N/2:]
    VX = sum([XS[i]*sin(tt*ww[i]) + XC[i]*cos(tt*ww[i]) for i in range(N/2+1)], 0)
    VY = sum([YS[i]*sin(tt*ww[i]) + YC[i]*cos(tt*ww[i]) for i in range(N/2+1)], 0)
    return VX*weightfunc, VY*weightfunc

def makepath(vx, vy):
    # turn coordinates into line segments, to check for intersections
    xx = cumsum(vx)+start[0]
    yy = cumsum(vy)+start[1]
    path = []
    for i in range(1,len(xx)):
        path.append([[xx[i-1], yy[i-1]],[xx[i], yy[i]]])
    return path

def checkpath(path):
    intersections = 0
    for line1 in path[:-1]: # last two elements are equal, and thus wrongly intersect each wall
        for line2 in walls:
            intersections += weightedintersection2D(array(line1), array(line2))
    return intersections

def eval_score(coeff):
    # tweak everything for better convergence
    vx, vy = sinsum(coeff, tt)
    path = makepath(vx, vy)
    score_int = checkpath(path)
    dist = hypot(*(path[-1][1]-goal))
    score_pos = abs(dist)**3
    acc = hypot(diff(vx), diff(vy))
    score_acc = sum(exp(clip(3*(acc-10), -10,20)))
    #score_snap = sum(abs(diff(vx)-diff(vx).round())) + sum(abs(diff(vy)-diff(vy).round()))
    print score_int, score_pos, score_acc#, score_snap
    return score_int*100 + score_pos*.5 + score_acc #+ score_snap

######################################
# Boring stuff above, scroll to here #
######################################
Nw = 4 # <3: paths not squiggly enough, >6: too many dimensions, slow
ww = [1*pi*k for k in range(Nw)]
Nt = 30 # find a solution with tis many steps
tt = linspace(0,1,Nt)
weightfunc = tanh(tt*30)*tanh(30*(1-tt)) # makes sure end velocity is 0

guess = random.random(4*Nw-2)*10-5
guess = array([ 5.72255365, -0.02720178,  8.09631272,  1.88852287, -2.28175362,
        2.915817  ,  8.29529905,  8.46535503,  5.32069444, -1.7422171 ,
       -3.87486437,  1.35836498, -1.28681144,  2.20784655])  # this is a good start...
array([ 10.50877078,  -0.1177561 ,   4.63897574,  -0.79066986,
         3.08680958,  -0.66848585,   4.34140494,   6.80129358,
         5.13853914,  -7.02747384,  -1.80208349,   1.91870184,
        -4.21784737,   0.17727804]) # ...and it returns this solution

optimsettings = dict(
    xtol = 1e-6,
    ftol = 1e-6,
    disp = 1,
    maxiter = 1000, # better restart if not even close after 300
    full_output = 1,
    retall = 1)

plt.ion()
plt.axes().add_collection(LC(walls))
plt.xlim(-10,510)
plt.ylim(-10,410)
path = makepath(*sinsum(guess, tt))
plt.axes().add_collection(LC(path, color='red'))
plt.plot(*start, marker='o')
plt.plot(*goal, marker='o')
plt.show()

optres = fmin(eval_score, guess, **optimsettings)
optcoeff = optres[0]

#for c in optres[-1][::optimsettings['maxiter']/10]:
for c in array(optres[-1])[logspace(1,log10(optimsettings['maxiter']-1), 10).astype(int)]:
    vx, vy = sinsum(c, tt)
    path = makepath(vx,vy)
    plt.axes().add_collection(LC(path, color='green'))
    plt.show()

```

To Do: GUI that lets you draw an initial path to get a rough sense of direction. Anything is better than randomly sampling from 14-dimensional space
> 3 votes

---
Tags: code-challenge, path-finding, physics
---


title: Square side pinpointing

text:
# Question
Title: Square side pinpointing
Welcome to my first code-golf challenge! :) Let's hop right into it.

**Challenge:**

Given two floating point vectors, **O** (origin) and **T** (target), you have to create a program to print the values **L** and **R** to STDOUT.

1. **O** is one corner of the square
2. **T** is one corner of the square that is located opposite to **O**
3. **L** is the 2D point (corner) that marks the other point of the uncomplete square
4. **R** is the 2D point (corner) that is opposite to **L**

**Rules**

5. Values for **O** and **T** have to be read from STDIN (see example inputs).
6. Again, **L** and **R**'s values has to be printed to STDOUT.

**Scoring and bonuses**

7. Count the bytes of your program.
8. If your program draws lines that connect between **O** to **L** to **T** to **R**, subtract 15 bytes from the byte count.

**Examples**

First line covers inputs (first square brackets for **O** and next brackets for **T**) and other line represents expected output.

* \[0, 0\] \[3, 3\] Expected: \[0, 3\] \[3, 0\]
* \[0, 0\] \[-2, -2\] Expected: \[-2, 0\] \[0, -2\]
* \[1, -1\] \[4, 2\] Expected: \[1, 2\] \[4, -1\]
* \[0, -1\] \[0, 1\] Expected: \[-1, 0\] \[1, 0\]

**NOTICE**: inputs and outputs can be floating points!

**Important information!**

* Values **O** and **T** can be taken in any format, as long as they come from STDIN (ex. Inside \[\] or ()...), use whatever format you want.
* **L** and **R** can be printed in any order.
* Remember: when (O-\>L-\>T-\>R-\>O) are connected, each side must have the same length!

**Winning**

* This is code-golf so fewest byte answer wins!
* Winner answer will be accepted at sunday 15.11.2015 20:00-22:00 (Finland time) (If I'm not wrong, that date is written like 11.15.2015 in the US, don't get confused).

Happy golfing!

# Answer
> 7 votes
# Seriously, 11 bytes

A port of my TI-BASIC answer. Calculates `mean(X)+i*(X-mean(X))`.

```
,;Σ½;)±+ï*+

```

Explanation:

```
,           Read input
;           Duplicate
Σ½          Half the sum (the mean) of the top copy
;           Copy the mean
)           Rotate stack to the left
            Now there's a copy of the mean on the bottom
±+          Negate mean and add to input list
ï*          Multiply by i
+           Add to mean

```

Input as a list of two complex numbers: `[1-1j,4+2j]`, and output in the same format: `[(4-1j), (1+2j)]`.

# Answer
> 6 votes
## Seriously, 25 bytes

`,i││-++½)+-+½)++-½)±+++½)`

Takes input as a list: `[x1,y1,x2,y2]`

Same strategy as my Python answer, but in Seriously!

Explanation:

```
,      get input
i      flatten list
││     duplicate stack twice, so that we have 4 copies of the input total
-++½)  calculate the first x-value using the formula (x1-y1+x2+y2)/2, and shove it to the end of the stack
+-+½)  calculate the first y-value using (x1+y1-x2+y2)/2, and shove it to the end of the stack
++-½)  calculate the second x-value using (x1+y2+x2-y2)/2, and shove it to the end of the stack
±+++½) calculate the second y-value using (-x1+y1+x2+y2)/2, and shove it to the end of the stack

```

Try it online

# Answer
> 4 votes
## TI-BASIC, 16 bytes

For a TI-83+ or 84+ series calculator.

```
Input X
i∟X+.5sum(∟X-i∟X

```

Unless I misunderstood, OP said they were fine with taking input and output as complex numbers. The `i` here is the imaginary unit, not the statistics variable.

TI-BASIC has a `mean(` function, but annoyingly it doesn't work with complex lists, throwing an `ERR:DATA TYPE`.

Input in the form `{1-i,4+2i}` for `[[1,-1],[4,2]]`. Output is in the form `{4-i 1+2i}` for `[[1,2][4,-1]]`.

# Answer
> 3 votes
# Matlab, ~~51~~ ~~45~~ ~~46~~ ~~45~~ 42 bytes

Now the input is expected in one column vector: `[x0;y0;x1;y1]` (ouput in the same format) I just modified it to be a full program.

```
z=eye(4);disp((.5-z([2:4,1],:))*input(''))

```

Or alternatively

```
z=[1,1;-1,1];disp([z',z;z,z']*input('')/2)

```

Old solution:

The input expects column vectors, e.g. `f([0;0],[3;3])`

```
@(a,b)[0,1;-1,0]*(b-a)*[.5,-.5]+(b+a)*[.5,.5]

```

It also returns two column vectors (as a 2x2 matrix).

# Answer
> 2 votes
# Japt, ~~29~~ 28 bytes

**Japt** is a shortened version of **Ja**vaScri**pt**. Interpreter

```
1o5 mZ=>$eval$(Uq'+)/2-UgZ%4

```

Note that the arrow functions require an ES6-compliant browser, such as the newer versions of Firefox. Input goes in as a 4-item array, e.g. `[1,-1,4,2]`.

### How it works

```
         // Implicit: U = input array
1o5      // Create a range of integers from 1 to 5. Returns [1,2,3,4]
mZ=>     // Map each item Z in this range to:
$eval$(  //  evaluate:
 Uq'+    //   U joined with "+" (equivalent to summing U)
)/2      //  divided by 2,
-UgZ%4   //  minus the item at Z%4 in the input. This translates to [y₁,x₂,y₂,x₁],
         //  which in turn tranlsates to:
         //   [(x₁-y₁+x₂+y₂)/2, (x₁+y₁-x₂+y₂)/2, (x₁+y₁+x₂-y₂)/2, (-x₁+y₁+x₂+y₂)/2]
         //  which is [Lx,Ly,Rx,Ry], or [Rx,Ry,Lx,Ly], depending on the situation.
         // Implicit: Output last expression

```

### How it was golfed

I first tried simply copying @Mego's Python approach. This left me with this 48-byte monster:
(Note: the input should not currently be wrapped in an array.)

```
[U-V+W+X /2,(U+V-W+X /2,(U+V+W-X /2,(V+W+X-U /2]

```

Since each of these items needs to be divided by 2, it's shorter to map the entire array with `mY=>Y/2`:

```
[U-V+W+X,U+V-W+X,U+V+W-X,V+W+X-U]mY=>Y/2

```

Now what? Well, the array is now simply adding three of the inputs and subtracting the fourth, following the pattern `1,2,3,0`. So, we could pack the inputs into an array, then add them together, divide by 2, and subtract the necessary item:

```
[1,2,3,0]mZ=>(Ug0 +Ug1 +Ug2 +Ug3)/2-UgZ

```

Nice, saved a byte! But is it possible to shrink the array at the beginning? Let's try packing it into a string, then splitting it back into an array with `a`:

```
"1230"a mZ=>(Ug0 +Ug1 +Ug2 +Ug3)/2-UgZ

```

Look at that, another byte saved. But is there an even better way? Well, we can use the fact that `[1,2,3,0] ≡ [1,2,3,4] mod 4`:

```
1o5 mZ=>(Ug0 +Ug1 +Ug2 +Ug3)/2-UgZ%4

```

Another two bytes! Now we're going somewhere. But that `Ug0 +Ug1 +Ug2 +Ug3` is hogging a lot of space. What if we reduce the array with addition?

```
1o5 mZ=>Ur(X,Y =>X+Y /2-UgZ%4

```

Wow, that really helped! Now we're down to 29 bytes. And thanks to @ןnɟuɐɯɹɐןoɯ, I was even able to golf another byte off the reduction. But if we could use a built-in to sum the array, it'd be way shorter:

```
1o5 mZ=>Uu /2-UgZ%4

```

19 bytes! Amazing! Unfortunately, Japt does not yet have any such built-ins. I'll add this in when I get a chance. Suggestions are welcome, for either the program or the language!

---

Well, as of v1.4.4, I've implemented quite a few more features into Japt than I had originally planned. Starting with the original plan for the shorter version:

```
1o5 mZ=>Uu /2-UgZ%4

```

First we need to change a few things: Functions are defined with `{`, and the sum function is `x`. This version works as-is:

```
1o5 mZ{Ux /2-UgZ%4

```

Now, `@` is a shorthand for `XYZ{`, allowing us to save a byte by switching from `Z` to `X`. Also, `£` is a shortcut for `m@`, saving another byte:

```
1o5 £Ux /2-UgX%4

```

Recently I implemented a feature where a `U` at the beginning of the program can usually be left out. Due to an implementation mistake, however, this also works with functions:

```
1o5 £x /2-UgX%4

```

Finally, the `g` function now wraps if the index is past the end of the string, allowing us to remove the `%4` for a total of **13 bytes**:

```
1o5 £x /2-UgX

```

And I thought 19 was amazing ;-) Test it online!

# Answer
> 1 votes
# Javascript(Node.js/ES6), 154 bytes

```
process.stdin.on('data',s=>(s=s.toString().split(','),a=s[0]-0,b=s[1]-0,x=s[2]-0,y=s[3]-0,console.log([a+(c=(a+x)/2-a)+(d=(b+y)/2-b),b+d-c,a+c-d,b+d+c])))

```

Getting stdin is the longer part of the code. The input should be the points comma separated :

```
echo "0,0,3,3" | node square.js

```

# Answer
> 1 votes
# CJam, 30 bytes

```
q~_:.+\:.-(W*+_2$.+@@.-].5ff*`

```

Try it online

This takes input as a list of lists, e.g. for the last example:

```
[[0 -1] [0 1]]

```

Explanation:

```
q~      Get and interpret input.
_       Make a copy.
:.+     Reduce the list of two points with vector sum operator.
\       Swap copy of input to top.
:.-     Reduce the list of two points with vector difference operator.
(W*+    Turn (x, y) into orthogonal (y, -x) by popping off first element, inverting
        its sign, and concatenating again. We now have center and offset vector.
_2$     Create a copy of both...
.+      ... and add them.
@@      Rotate original values to top...
.-      ... and subtract them.
]       Wrap the two results...
.5ff*   ... and multiply all values by 0.5.
`       Convert list to string.

```

# Answer
> 1 votes
# , 29 chars / 43 bytes

```
ô(ѨŃ(1,5)ć⇀ë(ïø`+`⸩/2-ï[$%4]⸩

```

`Try it here (Firefox only).`

# Answer
> 1 votes
# ngn APL, 21 bytes

```
⎕←F.5 0J.5×(F←+/,-/)⎕

```

This takes the input as a pair of complex numbers (e.g., `1J¯1 4J2`) and prints the output in the same way (e.g., `4J¯1 1J2`). Try it online in the ngn/apl demo.

# Answer
> 1 votes
# Pyth, 12 bytes

```
.jL.OQ-R.OQQ

```

This takes the input as a pair of complex numbers (e.g., `1-1j, 4+2j`) and prints the output as an array (e.g., `[(4-1j), (1+2j)]`). Try it online.

# Answer
> 0 votes
## Python 3, 102 bytes

```
g=lambda a,b,c,d:((a-b+c+d)/2,(a+b-c+d)/2,(a+b+c-d)/2,(d+b-a+c)/2)
print(g(*map(float,input().split())))

```

Input is taken in the form `x1 y1 x2 y2`, on a single line.

Try it online

# Answer
> 0 votes
# Prolog, 118 bytes

```
p([A,B],[C,D]):-read([E,F,G,H]),I is(E+G)/2,J is(F+H)/2,K is(G-E)/2,L is(H-F)/2,A is I-L,B is J+K, C is I+L, D is J-K.

```

Slightly more readable:

```
p([A,B],[C,D]):-read([E,F,G,H]),
                        I is(E+G)/2,
                        J is(F+H)/2,
                        K is(G-E)/2,
                        L is(H-F)/2,
                        A is I-L,
                        B is J+K,
                        C is I+L,
                        D is J-K.

```

To start the program:

```
p(X,Y).

```

Example input when the known corners are \[1, -1\] \[4, 2\]:
\[1,-1,4,2\]
Example output, where X and Y will contain the unknown corners:
X = \[1.0, 2.0\],
Y = \[4.0, -1.0\]
Try it out online here
**Edit:** Changed to read input from STDIN

# Answer
> 0 votes
# Python 2, 56 bytes

```
i=input()
s=sum(i)/2.0
print s-i[1],s-i[2],s-i[3],s-i[0]

```

Input can be `x1,y1,x2,y2` or `(x1,y1,x2,y2)`

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


title: Is it raining? I can't tell

text:
# Question
Title: Is it raining? I can't tell
These are raindrops:

```
! | . " :

```

These are clouds particles:

```
( ) _ @ $ &

```

I want you to verify, when given a block of text, whether or not it is raining. It is raining if, for every raindrop, there is a cloud particle somewhere above it. There must be one cloud particle for every raindrop. Output a truthy or falsy value denoting your conclusions.

# Valid examples

```
(@@@@@@)
 ( $ &  )
Q   (  )
..  .  !
 : .
  |"   !
    .

```

```
()()()
......

```

```
@_$ &
errrr
h_r-5
.:. .
 "

```

# Invalid examples

```
!
()

```

```
$$$$$
(   )
:::::
.....

```

This is a so the shortest program in *characters* wins.

# Answer
> 4 votes
# APL (30)

```
{∧/∊≤/+⍀¨⍵∘∊¨'!|.":' '()_@$&'}

```

This is a function that takes a character matrix as input, and gives a boolean output.

Test:

```
      ex1 ex2 ex3 ex4 ex5
┌─────────┬──────┬─────┬──┬─────┐
│(@@@@@@) │()()()│@_$ &│! │$$$$$│
│ ( $ &  )│......│errrr│()│(   )│
│Q   (  ) │      │h_r-5│  │:::::│
│..  .  ! │      │.:. .│  │.....│
│ : .     │      │ "   │  │     │
│  |"   ! │      │     │  │     │
│    .    │      │     │  │     │
└─────────┴──────┴─────┴──┴─────┘
      {∧/∊≤/+⍀¨⍵∘∊¨'!|.":' '()_@$&'}¨ex1 ex2 ex3 ex4 ex5
1 1 1 0 0

```

Explanation:

* `⍵∘∊¨'!|.":' '()_@$&'`: for both sets of characters (rain and clouds), and each character in ⍵, see if the character is a member of the set.
* `+⍀¨`: get a running sum for each column and each set
* `≤/`: for each position in ⍵, check that the amount of raindrops does not exceed the amount of cloud particles in the running sum
* `∧/∊`: return the boolean AND of all the elements in the result

# Answer
> 5 votes
# C++11, ~~186~~ 184 bytes

```
#include<map>
int i,c;int main(){std::map<int,int>p;while(~(c=getchar())){for(int m:{40,41,95,64,36,38})p[i]+=c==m;for(int m:{33,124,46,34,58})if(c==m&&!p[i]--)return 1;i=c-10?i+1:0;}}

```

Ungolfed

```
#include <map>
int i, c;
int main()
{
    std::map<int, int> p;
    while (~(c = getchar()))
    {
//        for (int m : { '(', ')', '_', '@', '$', '&'})
        for (int m : { 40, 41, 95, 64, 36, 38})
            p[i] += c == m;
//        for (int m : { '!', '|', '.', '"', ':'})
        for (int m : { 33, 124, 46, 34, 58})
            if (c == m && !p[i]--)
                return 1;
        i = c - '\n' ? i + 1 : 0;
    }
    return 0;
}

```

Basic approach, storing positions of cloud particles in a row and if rain particle is encountered, it checks whether the cloud particle is above it and decreases the counter of cloud particles in that column. The program returns 0 if it's valid and 1 otherwise.

# Answer
> 4 votes
# Snails, 125

```
{t.{t(\(|\)|\_|\@|\$|\&)=(u.,~)d!(.,~)t.!(.,~},!{t(\!|\||\.|\"|\:)ud!(.,~}t(\(|\)|\_|\@|\$|\&)!(d.,~)u.,~},!{t(\!|\||\.|\"|\:

```

The program outputs the area of the grid (or 1 if its area is 0) if it is raining; otherwise 0. If only I had implemented regex-style character classes.

**Ungolfed version** This contains fake instructions for clouds or raindrops instead of writing out all the gibberish. `\whatever` (replaced with `.` in the real program) means a thing that ought to be a raindrop, but can actually be anything because it doesn't matter if we match a non-raindrop to a cloud.

```
{
    t \whatever   ,, Pick a drop in a new column
    {
        t \cloud ,, Find a cloud with
        =(u.,~)  ,, nothing above in the same column marked
        !(d.,~)  ,, but not in an empty column
        t \whatever
        !(d.,~)
    },
    !(t \drop ud !(.,~) )  ,,no drops remaining in column
    t \cloud
    !(d.,~)
    u.,~
},             ,, repeated 0 or more times
! (t \drop)   ,, no drops left

```

# Answer
> 2 votes
# Python 2, 121 bytes

```
def f(i):
 for l in zip(*i.split('\n')):
  s=0
  for p in l:
   s+=p in'()_@$&';s-=p in'!|.":'
   if s<0:return
 return 1

```

Expects the input to be padded to be rectangular.

# Answer
> 1 votes
# Julia, 90 characters

```
s->all(cumsum(map(i->i∈"!|.\":"?-1:i∈"()_@\$&",mapfoldl(collect,hcat,split(s,"
")))').>-1)

```

Unlike the original solution (below), this uses mathematics to determine the solution. `mapfoldl(collect,hcat,split(s,"\n"))` (written above with `\n` replaced with an actual newline to save characters) converts the string into a 2d array of characters. `map(i->i∈"!|.\":"?-1:i∈"()_@\$&",...)` creates an array of numbers, with 1 if the character is a cloud, -1 if the character is rain, and 0 otherwise.

`cumsum(...')` calculates the cumulative sums of the rows (would normally be written `cumsum(...,2)`, but since we don't care about orientation from this point on, transposing only costs one character), and then `all(... .>-1)` checks for a negative number - negatives will only occur if a rain character appears without being preceded by a cloud character.

## Julia, ~~139~~ 136 *characters*

```
s->(t=join(mapfoldl(i->split(i,""),.*,split(s,"
")),"
");while t!=(t=replace(t,r"[()_@$&](.*?)[!|.\":]",s"\g<1>"))end;∩("!|.\":",t)==[])

```

This function first transposes the text so that rows become columns and vice-versa. Note that newlines are present in the code in the form of actual newlines, to save one character per instance.

The function then iteratively replaces cloud/droplet pairs with spaces, and once all such pairs are removed, it returns true if there are any droplets remaining and false otherwise.

`r"[()_@$&](.*?)[!|.\":]"` \- this is a regex that will match cloud/droplet pairs in a lazy manner, with group 1 containing everything between cloud and droplet. Then `s"\g<1>"` tells it to remove the matched cloud and droplets, but keep the stuff in between (necessary as it may contain clouds) - the `\g<1>` is whatever was matched in group 1 of the regex. `∩("!|.\":",t)==[]` will generate the intersection of the droplet characters with the final string, and if it's empty, then none of the droplet characters are present, and it's raining.

# Answer
> 1 votes
## Perl 5, 80

79, plus one for `-E` instead of `-e`

```
@a=();while(<>){@_=split'';(0>($a[$_]+=/[()_@&\$]/-/[!|.":]/)?die:1)for@_}say 1

```

# Answer
> 1 votes
# JavaScript ES6, 112

Test running the snippet below in an EcmaScript 6 compliant browser implementing arrow functions, spread operator and template strings (I use Firefox)

```
f=t=>!t.split`
`.some(r=>[...r].some((c,i)=>(c='!|.":()_@$&'.indexOf(c),n[i]=~c?c<5?~-n[i]:-~n[i]:n[i])<0),n=[])

//TEST
console.log=x=>O.innerHTML+=x+'\n';

test_valid = [
 '(@@@@@@)\n ( $ &  )\nQ   (  )\n..  .  !\n : .\n  |"   !\n    .',
 '()()()\n......',
 '@_$ &\nerrrr\nh_r-5\n.:. .\n "'
]
console.log('Valid');
test_valid.forEach(t=>console.log(t+'\n'+f(t)+'\n'))

test_invalid = ['!\n()','$$$$$\n(   )\n:::::\n.....']
console.log('Invalid');
test_invalid.forEach(t=>console.log(t+'\n'+f(t)+'\n'))
```

```
<pre id=O></pre>
```

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


title: Combined 100 year birthday

text:
# Question
Title: Combined 100 year birthday
I was recently adding up the ages of myself and my wife and kids and realised that at some point in the not-too-distant future our ages will all add up to exactly 100 years.

# Challenge

For an input consisting of a combined (total) age and a list of birth dates, output the date on which the combined ages all add up to the given total.

1. Input combined age (in years) will be a positive integer
2. Input list of birth dates will be a list (whatever format is convenient for your language) of dates that must contain numerical representation of Day, Month and Year. Number of days since a specific epoch is not acceptable. You may assume the list of input dates is sorted in chronological order.
3. Output will be a single date in the same format as input dates
4. For the purposes of the combined age, 1 year is considered to be exactly 365.25 days
5. For some inputs, it will be impossible to find a date after all the birth dates when they all add up to the combined age. For instance consider two birth dates that are 20 years apart, but we want a combined of 10 years. In that case, the output would be the 10th birthday of the older birth date. In other words, individual ages are considered to be 0 for all dates before that individual's birth date
6. The output will be the first date on which the combined ages add up to *at least* the input age
7. You may use built-in functions
8. You must support dates going back as far as 1970/01/01.

### Examples

Here I'm giving all dates in YYYY/MM/DD format, but you may whatever format you like.

```
Input                                               Output

 10  2000/01/01                                     2010/01/01
100  1975/03/05,1978/07/23,2008/11/12,2012/12/20    2018/11/22
100  1975/03/06,1978/07/23,2008/11/12,2012/12/20    2018/11/23
100  1975/03/09,1978/07/23,2008/11/12,2012/12/20    2018/11/23
100  1975/03/10,1978/07/23,2008/11/12,2012/12/20    2018/11/24
  3  1990/08/01,1995/07/02                          1993/08/01
 50  1975/03/05,1978/07/23,2008/11/12,2012/12/20    2001/11/13

```

Note that in the last two examples, the output date lies within the range of input dates, as per rule 5.

# Answer
> 4 votes
# Mathematica ~~138 107~~ 237 bytes

My first attempts were sloppy and unworthy. This should work generally, provided that the birth dates are given in order of earliest to latest, as in the test cases.

The test cases were well-chosen and difficult to implement correctly. The code turned out way longer than I had hoped.

The general logic is to

1. Solve for x (in days) such that the distance from x to each date of birth sums to the target passage of time (e.g 100 years converted to days).
2. If the earliest date + x days \> latest date of birth, remove the latest date of birth and repeat step (1), Else move to (3).
3. Return (earliest date + x days)

---

```
t_~f~d_:=If[DateDifference[a=DateObject[DatePlus[d[[1]],Solve[t 365.25==Tr@(x-Join[{0},
QuantityMagnitude@(DateDifference[d[[1]],#,"Day"]&/@Rest@d)]),{x}][[1,1,2]]]/.
{y_,m_,n_,h_}:>{y,m,n+1}],d[[-1]]]>Quantity[0,"Days"],f[t,Most@d],a]

```

---

# Test Cases

```
f[10, {{2000, 1, 1}}]
f[100, {{1975, 3, 5}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12, 20}}]
f[100, {{1975, 3, 6}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12, 20}}]
f[100, {{1975, 3, 9}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12, 20}}]
f[100, {{1975, 3, 10}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12,  20}}]
f[3, {{1990, 8, 1}, {1995, 7, 2}}]
f[50, {{1975, 3, 5}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12, 20}}]

```

---

# Answer
> 1 votes
## PowerShell, ~~145~~ 125 Bytes

```
param($a,$b)$c=@();$b|%{$c+=date $_};$t=$a*365.25;$d=$c[0];while($t-gt0){$c|%{if($_-le$d){$t--}};$d=$d.AddDays(1)}"{0:d}"-f$d

```

Pretty tricksy challenge, but relatively straightforward once understood.

### Expanded and Commented:

```
param($a,$b)          # Take our input
$c=@()                # Make a new array $c
$b|%{$c+=date $_}     # Change our input array $b of strings into dates, store in $c
$t=$a*365.25          # Target number of days we need to account for
$d=$c[0]              # Our starting date, also our cumulative date for output
while($t-gt0){        # While we still have days remaining
  $c|%{               # Iterate through our birthdays
    if($_-le$d){$t--} # If the birthday is less than our cumulutive day, subtract a day
  }
  $d=$d.AddDays(1)    # We've accounted for another day, so increment our cumulative day
}
"{0:d}"-f$d           # Format output

```

## Example:

Input needs to contain an explicitly formatted array of string-date representations. Output is in `MM/DD/YYYY` format (default for en-us localization in PowerShell).

```
PS C:\Tools\Scripts\golfing> .\combined-100-year-birthday.ps1 50 @('03/05/1975','07/23/1978','11/12/2008','12/20/2012')
11/13/2001

```

Edit -- Golfed 20 bytes by changing how we iterate through birthdays, and by using while instead of do/until

# Answer
> 0 votes
## PHP, 220 bytes

I've added some newlines for readability.

```
function c($y,$s){for($d=$y*365.25;++$i<count($l=array_map(date_create,$s));)$d+=
$l[0]->diff($l[$i])->days;($l[$i-1]>$r=$l[0]->add(new DateInterval(P.ceil($d/$i).D)
))?c($y,array_slice($s,0,-1)):print$r->format('Y/m/d');}

```

`Ideone`

Here is the ungolfed version:

```
function printCombinedBirthday($combinedAgeInYears, $listOfBirthDatesStrings)
{
    $combinedAgeInDays = $combinedAgeInYears * 365.25;
    $listOfBirthDates = array_map('date_create', $listOfBirthDatesStrings);
    $numberOfBirthDates = count($listOfBirthDates);

    for ($i = 0; $i < $numberOfBirthDates; ++$i) {
        $combinedAgeInDays += $listOfBirthDates[0]->diff($listOfBirthDates[$i])->days;
    }

    $combinedAgeInDays = ceil($combinedAgeInDays / $numberOfBirthDates);
    $interval = new DateInterval('P'. $combinedAgeInDays .'D');
    $result = $listOfBirthDates[0]->add($interval);

    if ($listOfBirthDates[$numberOfBirthDates - 1] > $result)
    {
        printCombinedBirthday(
            $combinedAgeInYears,
            array_slice($listOfBirthDatesStrings, 0, -1)
        );
    }
    else {
        echo $result->format('Y/m/d');
    }
}

```

---
Tags: code-golf, date
---


title: Code Billiards (Levenshtein golf)

text:
# Question
Title: Code Billiards (Levenshtein golf)
You must use one language to write programs that perform the following nine tasks, **in any order you want**.

* Convert an inputted number from base 10 to base 36.
    + Sample input: `1000`
    + Sample output: `RS` (output must be upper case)
* Convert each character in a string to its base 10 decimal ASCII codes and print the codes concatenated together.
    + Sample input: `Scrambled 3GG5`
    + Sample output: `839911497109981081011002051717153`
* Determine if an inputted number is divisible by 1738.
    + Return a truthy value if it is and a falsy value if it isn't.
* Determine if a string has the letter `q` in it.
    + Return a truthy value if it does and a falsy value if it doesn't.
* Encode an inputted string of letters with a Caesar cipher of +1.
    + Case must be preserved. Non-letter characters will be printed without modification.
    + Sample input: `Good morning, World!`
    + Sample output: `Hppe npsojoh, Xpsme!`
* Find and print the sum of the prime factors of a number.
    + Sample input: `1320`
    + Sample output: `21`
* Print `PPCG`.
* Print the first `n` positive integers that are divisible by `floor(sqrt(n))`.
    + `n` is an inputted integer.
* Replace every `o` and `O` in an inputted string with .
    + Sample input: `Onomatopoeia`
    + Sample output: `ಠnಠmatಠpಠeia`

---

You will have noticed that this challenge is `Code Billiards`, not `Code Golf`. The objective of this challenge, like in billiards, is to set up your code so it can be modified only slightly for the next challenge. This is why your programs do not have to solve the above tasks in order.

Your score is determined as follows

* Your score goes up by `1` each byte in your programs.
* Your score goes up by `floor(n^(1.5))` if two consecutive programs have a Levenshtein distance of `n`. For example if your first program is `potato` and your second program is `taters`, your score goes up by 12 for 12 bytes and by `11`=`floor(5^(1.5))` for a Levenshtein distance of 5.

---

The objective of this challenge is to have as low a score as possible after all nine programs have been written. Standard CG rules apply.

---

To see the leaderboard, click "Show code snippet", scroll to the bottom and click "► Run code snippet". Snippet made by Optimizer.

```
/* Configuration */

var QUESTION_ID = 63675; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 43444; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

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

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

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

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

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

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

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

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

}
```

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

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

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

table thead {
  font-weight: bold;
}

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

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

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

# Answer
> 8 votes
# Japt, ~~886~~ ~~866~~ ~~766~~ ~~725~~ ~~688~~ 669

Tasks 5 and 6 are killers. Perhaps there are shorter ways to get them done. I think the Levenshtein distances could still be reduced as well.

* Task 3 (divisiblity): `!(U%#ۊ`
7 bytes (arabic char messes up alignment)
* Task 4 ('q' check): `U!=Uk'q` 7 bytes, dist 11
* Task 1 (base conversion): `Us36 u` 6 bytes, dist 14
* Task 2 (ASCII codes): `UmX=>Xc` 7 bytes, dist 14
* Task 7 (see for yourself): `"PPCG"` 6 bytes, dist 18
* Task 9 (ಠ replacement): `Ur"[Oo]",'ಠ` 13 bytes, dist 27
* Task 8 (floor(sqrt(n))): `X=Uq f;XoU*X+1,X` 16 bytes, dist 52
* Task 6 (prime factor sum): `2oU fX=>2oX eY=>X%Y &&!(U%X)r(X,Y =>X+Y` 39 bytes, dist 172
* Task 5 (Caesar cipher): `UmX=>128o mY=>Yd)a k'A i#Z,'A k'a i#z,'a gXc` 44 bytes, dist 216

Here's a snippet that will tell you (one of) the most efficient ways to arrange your programs:

```
function L(s,t) {
  if(s == t) return 0;
  if(s.length === 0) return t.length;
  if(t.length === 0) return s.length;

  var v0 = Array(t.length+1),
      v1 = Array(t.length+1);

  for(var i=0; i<v0.length; i++) v0[i]=i;
  for(i=0; i<s.length; i++) {
    v1[0]=i+1;
    for(var j=0; j<t.length; j++)
      v1[j+1] = Math.min(v1[j]+1, v0[j+1]+1, v0[j]+(s[i]==t[j]?0:1));
    for(j=0; j<v0.length; j++) v0[j]=v1[j];
  }
  return v1[t.length];
}

function run(x) {
  R.innerHTML='';
  var b={}, k=0, min=1/0, item='';
  for(var i in x) {
    for(var j in x.slice(+i+1)) {
      k=b[i+(+i+(+j)+1)]=b[(+i+(+j)+1)+i]=L(x[+i],x[+i+(+j)+1]);
      if(k<min) min=k, item=i+(+i+(+j)+1);
    }
  }
  var order=item, q=10;
  while(order.length < x.length && q--) {
    min=1/0, item='';
    for(i in b) {
      if(b[i]<min) {
        if(i[0]==order.slice(-1) && order.indexOf(i[1])==-1)
          min = b[i], item = i[1];
      }
    }
    order+=item;
  }
  var score=0,y=0;
  function getByteCount(s){return(new Blob([s],{encoding:"UTF-8",type:"text/plain;charset=UTF-8"})).size}
  console.log("Task",(+order[0]+1)+":",y=getByteCount(x[order[0]])),score+=y
  for(i in order.slice(1))
    console.log(" ",y=Math.pow(b[order[i]+order[+i+1]],1.5)|0),score+=y,
    console.log("Task",(+order[+i+1]+1)+":",y=getByteCount(x[order[+i+1]])),score+=y;
  console.log("Total:",score)
}

console.log = function(){R.innerHTML+=Array.prototype.slice.call(arguments).join(' ');R.innerHTML+='<br>'};
```

```
<p>Input programs here, one per line:</p>
<textarea id=O rows="9" style="width:90%"></textarea><br>
<button onclick="run(O.value.split('\n'))">Run</button>
<p id=R></p>
```

With the latest version of Japt (non-competing in this challenge), most tasks get shorter:

* Task 1: `s36 u` 5 bytes
* Task 2: `mc` 2 bytes
* Task 3: `v#ۊ`
4 bytes
* Task 4: `oq` 2 bytes
* Task 5: `;B±B+C²UrF,@Bg1+BbX` 19 bytes
* Task 6: `k â x` 5 bytes
* Task 7: `"PPCG` 5 bytes
* Task 8: `B=U¬f)oU*B+1B` 13 bytes
* Task 9: `ro'ಠ'i` 6 bytes

The optimal order is now 2,4,3,1,6,7,9,8,5, coming in at a whopping score of **217**, less than one-third of the original!

Suggestions welcome!

# Answer
> 7 votes
# Pyth, score 489

Base conversion: 15

```
s@L+s`MTrG1jQ36

```

Caesar Cipher: 13 + 11^1.5

```
u.rGHrBG1z 36

```

Divisible by 1738: 7 + 11^1.5

```
!%Q1738

```

First N positive integers: 8 + 8^1.5

```
*Rs@Q2SQ

```

Sum of prime factors: 4 + 6^1.5

```
s{PQ

```

Appearance of q in string: 4 + 4^1.5

```
}\qz

```

Join all ASCII codes: 5 + 4^1.5

```
jkCMz

```

Print "PPCG": 5 + 5^1.5

```
"PPCG

```

Replace with : 9 + 7^1.5

```
Xz"oO"\ಠ

```

# Answer
> 3 votes
# Java, score 8331

Them levenshtein distances are killing my score here.

(These programs take input as command line arguments)

Program 1 (119):

```
class L{public static void main(String[]a){System.out.print(Integer.toString(Integer.parseInt(a[0]),36).toUpperCase());}}

```

Program 2 (120+561.5=539):

```
class L{public static void main(String[]a){/*System.out.print*/for(char b:a[0].toCharArray())System.out.print((int)b);}}

```

Program 3 (101+491.5=444):

```
class L{public static void main(String[]a){System.out.print/*for*/(Integer.parseInt(a[0])%1738==0);}}

```

Program 4 (108+201.5=197):

```
class L{public static void main(String[]a){System.out.print(/*forInteger.parseInt(*/a[0].indexOf('q')>=0);}}

```

Program 5 (186+1071.5=1293):

```
class L{public static void main(String[]a){for(char b:a[0].toCharArray())System.out.print(Character.isLetter(b)?Character.isUpperCase(b)?b>'Y'?'A':(char)(b+1):b>'y'?'a':(char)(b+1):b);}}

```

Program 6 (327+2281.5=3747):

```
class L{public static void main(String[]a){int i,k=0,j=i=Integer.parseInt(a[0]);for(;i>0;i--)if(p(i)&&j%i==0)k+=i;System.out.print(k);}static boolean p(int n){if(n<2)return 0>0;if(n==2||n==3)return 1>0;if(n%2==0||n%3==0)return 0>0;int i,k=(int)Math.sqrt(n)+1;for(i=6;i<=k;i+=6)if(n%(i-1)==0||n%(i+1)==0)return 0>0;return 1>0;}}

```

Program 7 (336+101.5=368)

```
class L{public static void main(String[]a){/*int i,k=0,j=i=Integer.parseInt(a[0]);for(;i>0;i--)if(p(i)&&j%i==0)k+=i;*/System.out.print("PPCG");}static boolean p(int n){if(n<2)return 0>0;if(n==2||n==3)return 1>0;if(n%2==0||n%3==0)return 0>0;int i,k=(int)Math.sqrt(n)+1;for(i=6;i<=k;i+=6)if(n%(i-1)==0||n%(i+1)==0)return 0>0;return 1>0;}}

```

Program 8 (351+341.5=549):

```
class L{public static void main(String[]a){int i,k=1,j=(int)Math.sqrt(i=Integer.parseInt(a[0]));for(;k<i;k++)/*if(p(i)&&j%i==0)k+=i;*/System.out.println(j*k);}static boolean p(int n){if(n<2)return 0>0;if(n==2||n==3)return 1>0;if(n%2==0||n%3==0)return 0>0;int i,k=(int)Math.sqrt(n)+1;for(i=6;i<=k;i+=6)if(n%(i-1)==0||n%(i+1)==0)return 0>0;return 1>0;}}

```

Program 9 (305+841.5=1075):

```
class L{public static void main(String[]a){int i,k=1,j=0;System.out.print(a[0].replaceAll("o|O",""+(char)3232));}static boolean p(int n){if(n<2)return 0>0;if(n==2||n==3)return 1>0;if(n%2==0||n%3==0)return 0>0;int i,k=(int)Math.sqrt(n)+1;for(i=6;i<=k;i+=6)if(n%(i-1)==0||n%(i+1)==0)return 0>0;return 1>0;}}

```

# Answer
> 3 votes
# Ruby, 1488

Probably a lot of room for improvement here. Spent most of the time calculating the score...

*Sum of prime factors*: 64
```
require'prime';p gets.to_i.prime_division.reduce(0){|s,a|s+a[0]}

```
*Base 36*: 30 + 471.5 = 352
```
puts gets.to_i.to_s(36).upcase

```
*Divisible by 1738*: 22 + 151.5 = 80
```
puts gets.to_i%1738==0

```
*Print PPCG*: 9 + 181.5 = 85
```
puts:PPCG

```
*Does string contain `q`?*: 10 + 81.5 = 32
```
p gets[?q]

```
*Replace `o`*: 23 + 161.5 = 87
```
puts gets.gsub(/o/i,?ಠ)

```
*Ceasar cipher*: 32 + 211.5 = 128
```
puts gets.tr 'A-Za-z','B-ZAb-za'

```
*ASCII codes*: 37 + 261.5 = 169
```
puts gets.chomp.chars.map(&:ord).join

```
*Integers divisible by square root*: 72 + 561.5 = 491
```
puts *(1..1/0.0).lazy.select{|i|i%Math.sqrt(i).floor==0}.take(gets.to_i)

```

# Answer
> 1 votes
## Pyth, score 817

number 1: 24

```
Jjk+UTrG1VjKvz36=+k@JN;k

```

number 2: (9 + 161.5 = 73)

```
Vz=+kCN;k

```

number 3: (5 + 81.5 = 27)

```
/QC"ۊ

```

number 4: (5 + 141.5 = 57)

```
hxz\q

```

number 5: (39 + 371.5 = 264)

```
J+GrG1VzIhxJNKChCNIhxJKpK)EpC-CK26))EpN

```

number 6: (4 + 391.5 = 247)

```
s{PQ

```

number 7: (5 + 41.5 = 13)

```
"PPCG

```

number 8: (12 + 121.5 = 53)

```
VK/@Q2 1*KhN

```

number 9 (13 + 131.5 = 59)

```
j\ಠcj\ಠcz\o\O

```

Not the best, I just started learning pyth today and thought I'd give it a try, number 5 really killed my score, I think I can get a few of them shorter but That will just hurt me more on the distances. Any tips from more experienced pyth users are appreciated.

# Answer
> -1 votes
# Python 3 (currently invalid), 621 bytes

```
from numpy import base_repr
import math
print(base_repr(int(input()),36))
print("".join([str(ord(c)) for c in input()]))
if int(input())%1738 == 0:print(True)
else:print(False)
if "q" in input().lower():print(True)
else:print(False)
t=bytes.maketrans(b"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ",b"bcdefghijklmnopqrstuvwxyzaBCDEFGHIJKLMNOPQRSTUVWXYZA")
print(input().encode("utf-8").translate(t).decode("utf-8"))
print("PPCG")
n=int(input())
for i in range(1,n):
    if i%math.floor(i**0.5)==0:print(i,end=" ")
print("")
y=input()
z=""
for i in y:
    if i.lower()=="o":z+="0"
    else:z+=i
print(z)

```

Not really that good code but somewhat works :D. The sum of prime factors is not working. I always get a different result from your example so I removed it. Also Python does not support the char  so instead it replaces the `o`s with `0`s

IO INFO:

1st input: int in base 10 | Output: that number in base 36

2nd input: a string | Output: Ascii numbers of the string

3rd input: integer | Output: True or False depending if number is dividible by 1738

4th input: string | Output: T or F depending if the string has "q" in it

5th input: string | Output: Caser Cipher +1 of the string

6th: just prints "PPCG" literally

7th input: int n | Output: first n ints divisible by floor(sqrt(n))

8th input: string | Output: Replaced all `o`s with 0 (not with ಠ because python does not support that character, don't get too mad :) )

---
Tags: code-golf, math, number, multiple-holes
---


title: Spherical excess of a triangle

text:
# Question
Title: Spherical excess of a triangle
# Spherical excess of a triangle

As we all know, the sum of angles of any planar triangle is equal to 180 degrees.

However, for a spherical triangle, the sum of angles is always **greater** than 180 degrees. The difference between the sum of the spherical triangle angles and 180 degrees is called **spherical excess** . The task is to compute the spherical excess of a triangle with given vertex coordinates.

## Some background

A spherical triangle is a part of the sphere defined by three great circles of the sphere.

Both sides and angles of spherical triangle are measured in the term of angle measure, because each side can be considered as a intersection of the sphere and some planar angle with vertex at the center of the sphere:

Each three distinct great circles define 8 triangles, but we only take *proper triangles* into consideration, *ie.* triangles whose angle and side measures satisfy

It's convenient to define vertices of a triangle in terms of geographic coordinate system. To compute the length of an arc of sphere given the longitude λ and latitude Φ of its ends we can use formula:

, where

or more explicitely:

(source: https://en.wikipedia.org/wiki/Haversine\_formula)

The two basic formulas that can be used to solve a spherical triangle are:

* the law of cosines:

* the law of sines:

(source: https://en.wikipedia.org/wiki/Spherical\_trigonometry#Cosine\_rules\_and\_sine\_rules)

Given three sides, it's easy to compute the angles using the cosine rule:

Finally, the spherical excess of a triangle is defined:

What's interesting about the relation between the spherical excess of a triangle and its area:

So on a unit sphere, the excess of a triangle is equal to area of that triangle!

## The task

Write a function or a program that will compute spherical excess of a triangle in degrees given the triangle vertices coordinates. The vertex coordinates are provided in terms of geographic coordinate system.

Each vertex should be passed in form `[latitude in degrees][N|S][longitude in degrees][E|W]`. Longitude and `E` or `W` can be skipped when latitude is 90 *ie.* `90N`, `90S`, `10N100E`, `30S20W` are proper vertex descriptions, while `80N` or `55S` are not.

The latitudes and longitudes are always integer in the test cases.

The answers with error less than one degree will be accepted (as in examples below). The result can be rendered as both real or integer therefore, up to your convenience.

**Examples**

Input

```
90N0E
0N0E
0N90E

```

Output

```
89.999989

```

Input

```
90N
0N0E
0N90E

```

Output

```
89.999989

```

Input

```
0N0E
0N179E
90N0E

```

Output

```
178.998863

```

Input

```
10N10E
70N20W
70N40E

```

Output

```
11.969793

```

In all test cases longitude and latitude are integer numbers. Parsing the vertex coordinates is the part of the task, so a vertex must be passed as single string/literal , it's not allowed to pass `80N20E` as four parameters/strings: `80`, `N`, `20`, `E`.

This is guaranteed that vertices are all distinct and neither two of the three vertices make an antipodal points pair.

## Scoring

This is , so the shortest code wins.

# Answer
> 4 votes
# Matlab, ~~288~~ 266 bytes

Here the commented version that should explain what is going on:

```
                                  %parsing the input
for k=1:3;
    s=input('','s');              %request input
    if sum(s>57)<2;               %if we have only one letter, add arbitrary second coordinate
        s=[s,'0E'];
    end;
    S=1-2*(s(s>57)>80);           %calculate the sign of the coordinates
    s(s>57)=44;                   %replace letters with comma
    L(k,:)=eval(['[',s,']']).*S;  %evaluates string as list and multiply with signs
end;
i=[2,3,1];
                                  %calculate the angular distance between each pair of points
a=arrayfun(@distance,L(:,1),L(:,2),L(i,1),L(i,2))*pi/180;
                                  %evaluate the spherical excess
f=@(a,b,c)sum(acos((cos(a)-cos(b).*cos(c))./(sin(b).*sin(c))))-pi;
disp(f(a,a(i),a([3,1,2]))*180/pi)

```

Fully golfed (linebreaks can be removed):

```
for k=1:3;s=input('','s');if sum(s>57)<2;s=[s,'0E'];end;
s(s>57)=44;L(k,:)=eval([91,s,93]).*(1-2*(s(s<48)>80));end;
i=[2,3,1];p=pi/180;a=arrayfun(@distance,L(:,1),L(:,2),L(i,1),L(i,2))*p;
b=a(i);disp((sum(acos((cos(a([3,1,2]))-cos(b).*cos(a))./(sin(b).*sin(a))))-pi)/p)

```

# Answer
> 3 votes
# Ruby, Rev 3 ~~264~~ 255 bytes

Major changes:

New constant `r` = 180/PI defined and used throughout function. `e` had to be initialized to +PI, so excess now counts downwards and is negated before returning.

`t[]` eliminated: Ruby allows the data that was assigned to `t[]` to be directly assigned to `u,v,w.`

Single `i` loop to do the job of two, `?:` ternary operator switches between tasks.

Many other minor changes.

```
include Math
->s{r=180/e=PI
x=y=z=n=[]
9.times{|i|i<6?(u,v,w=eval(?[+s[i%3].gsub(/[NE]/,"/r,").gsub(/[SW]/,"/-r,")+"0]")
i%2<1&&x=y=z=1
n[i/2]=(z*=sin(u))+(y*=cos(v)*w=cos(u))+x*=w*sin(v)):e-=acos((n[i-7]-(c=n[i-6])*d=n[i-8])/sqrt((1-c*c)*(1-d*d)))}
-e*r}

```

# Ruby, Rev 1 ~~283~~ 277 bytes

Requires an array of 3 strings.

```
include Math
->s{x=y=z=n=[]
6.times{|i|t=eval(?[+s[i%3].gsub(/[NE]/,k="*PI/180,").gsub(/[SW]/,"*-1"+k)+"0]")
i%2<1&&x=y=z=1
n[i/2]=(z*=sin(u=t[0]))+(y*=cos(u)*cos(v=t[1]))+(x*=cos(u)*sin(v))}
e=-PI
3.times{|i|e+=acos((n[i-1]-n[i]*d=n[i-2])/sqrt((1-n[i]**2)*(1-d**2)))}
e/PI*180}

```

**Overview**

The lengths of the triangle sides on the unit sphere are equal to the angles between the vectors describing the two points. But we don't need to know that angle. It suffices to know the cosine of the angle, which is easily obtained from cartesian coordinates using the Dot Product.

**Explanation**

The input strings are converted into a string representation of an array, which is then evaluated and stored in `t`, as below. The final zero is not needed if two coordinates are given. If only latitude 90 is given, the zero is interpreted as the longitude.

```
Example:  70N20W --> [70*PI/180,20*-1*PI/180,0]

```

The Dot Products are of the form `a.b=ax*bx+ay*by+az*bz`. As the vectors are all of unit length, the dot product is equal to the cosine of the angle between the vectors.

In order to calculate them a loop is iterated 6 times passing twice through the input data. On even iterations 0,2,4 the variables `x,y,z` are set to 1 to start a new calculation. On each iteration these variables are multiplied by the x,y and z components of each vector, using the longitude and latitude data stored in `t[0],t[1]` (which for golfing reasons is also assigned to `u,v`). The sum of the variables is written to array `n` (the garbage values on even iterations being overwritten by the correct values on odd iterations) so that at the end `n` contains the 3 dot products `[a.b, c.a, b.c]`.

For the cosine rule, we need the cosines of the three included angles between vertices, but we also need the sines. These are obtained as `sqrt(1-cosine**2)`. As the sines are multiplied together the expression can be rearranged so that only one call to `sqrt` is required. The fact that we do not know if the sine was positive or negative does not matter, as the haversine formula always gives the positive sine anyway. The important physical quantity is the distance between the points, which is absolute and therefore always positive.

For each iteration `i=0..2`, we calculate the value for the angle opposite array element `i-1` using the other elements `i` and `i-2`. Negative array subscripts like this are legal in Ruby, they just wrap around to the beginning of the array.

**Ungolfed in test program**

Requires three sets of coordinates on the same line, with spaces between them.

```
include Math
g=->s{
  n=[]         #array for dot products
  x=y=z=1      #it's required to use these variables once before the loop, for some bizarre reason
  6.times{|i|
    t=eval(?[+s[i%3].gsub(/[NE]/,k="*PI/180,").gsub(/[SW]/,"*-1"+k)+"0]")
    i%2<1&&x=y=z=1
    n[i/2]=(z*=sin(u=t[0]))+(y*=cos(u)*cos(v=t[1]))+(x*=cos(u)*sin(v))
  }

  e=-PI        #set e to -PI and begin accumulating angles
  3.times{|i|
    e+=acos((n[i-1]-n[i]*n[i-2])/sqrt((1-n[i]**2)*(1-n[i-2]**2)))
  }

e/PI*180}      #return value

puts g[gets.split]

```

---
Tags: code-golf, geometry, trigonometry
---


title: Convert Brainfuck to another language!

text:
# Question
Title: Convert Brainfuck to another language!
## The Task

Write the shortest program, that accepts script in brainfuck from `STDIN` (or equivalent) and outputs to `STDOUT` (or equivalent) a program written in the SAME language you're using.

For example, if you write in Java, with the input

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

```

The output can be

```
public class B {
    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

```

# Answer
# Brainfuck, 5 bytes

```
+[,.]

```

This sentence circumvents the 30 char answer requirement.
> 5 votes

---
Tags: brainfuck
---


# Question
Title: Write a program which performs brute force letter combination until the word "password" is found
The program should print every letter combination (lowercase or uppercase, it doesn't matter) in alphabetic order. It must start with `a` and the last printed combination should be `password`.

The output should be:

```
a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ... passwora passworb passworc password

```

# Answer
## Perl, 19 chars

```
say for a..password

```

Uses newlines as delimiters, per clarification above. Run with `perl -M5.010` (or just `perl -E 'say for a..password'`) to enable the Perl 5.10+ `say` feature. Per meta, this doesn't count as extra chars.

(If you insist on spaces as delimiters, `$,=$";say a..password` is only two chars longer. However, it's also *very* slow and wasteful of memory, to the point of being unusable in practice, since it tries to build the entire list in memory before printing it.)
> 32 votes

# Answer
## Ruby, 33 chars (optimal but longer version)

```
?a.upto('password'){|c|$><<c+' '}

```

I like the `'a'.upto('password')`; it tells you *exactly* what it's doing. Ruby is great and expressive like that. `:D`

Of course, `print c,' '` would also be much clearer, but using `$>` is two characters shorter.

## Ruby, ~~29~~ 25 chars (slow version)

```
$><<[*?a..'password']*' '

```

This one's shorter, but it prints all of the tokens at once, so it takes a long, long time to run!
> 18 votes

# Answer
## Perl, ~~33~~ ~~32~~ 24 characters

A solution in 32 characters:

```
$_=a;print$_++,$"until/passwore/

```

Not much to say about this one. I could reduce this to 27 characters if I could use newlines instead of spaces to separate the entries.

Ilmari Karonen points out that `..` internally calls `++`, so a better solution (25 characters) would be:

```
print$_,$"for a..password

```

By taking advantage of Perl's command-line options, here's an equivalent 24-character solution:

```
perl -l40e 'print for a..password'

```

The rules for counting perl flags is here, for those who aren't familiar with them.

Of course, Ilmari's 21-character solution is shorter still, but it requires a machine that can allocate an array of 129,052,722,140 strings.
> 6 votes

# Answer
## Perl 6, 20 chars

```
say "a".../password/

```

You don't need other things
> 6 votes

# Answer
# Python 2, 91

```
b=lambda n:n*' 'and b(n/26-(n%26<1))+chr(~-n%26+97)
i=0
exec"i+=1;print b(i);"*129052722140

```
> 5 votes

# Answer
## PHP ~~38~~ ~~37~~ 36 characters

```
<?for($w=a;$w<passwore;)echo$w++,~ß;

```

You have to set the encoding to ISO 8859-1 and disable warnings.
> 4 votes

# Answer
# Ruby (40 characters)

Interpret a string of a-z letters as a number in base 26, with a = 1, b = 2, ..., z = 26.

So "password" can be thought of as the number N =

```
16*(26**7) +
1*(26**6) +
19*(26**5) +
19*(26**4) +
23*(26**3) +
15*(26**2) +
18*(26**1) +
4*(26**0)

```

If we let `s = "a"` (that is: 1) and we make (N-1) calls to `s.succ!`, s will be `"password"` (N). In other words, N = 1 + (N-1).

For an example that will run more quickly, to prove the calculation of N is correct, consider `"pass"` as the target, where N is

```
16*(26**3) +
1*(26**2) +
19*(26**1) +
19*(26**0)

```

and

```
s = "a"
(N-1).times { s.succ! }
puts s #== "pass"

```

Since we want to print `"a"` too, we need

```
s = "`"
N.times { print(s.succ! + " ") }

```

So back to the full "password". `N = 129052722140`, leaving:

```
s=?`;0x1e0c2443dc.times{$><<s.succ!+" "}

```

I hunted for a more compact form of `129052722140 == 0x1e0c2443db` but couldn't find one.

(Updated to fix the lack of printing `"a"`, thanks to Cary.)
> 2 votes

# Answer
**Javascript, 73**

Here is a 73 character version of @Briguys' code, which prints only letter combinations

`for(i=s=0;1982613533018>i++;s=i.toString(36))/\d/.test(s)||console.log(s)`
> 2 votes

# Answer
## APL(Dyalog), ~~46~~ 34

```
{∇{'PASSWORD '≡⍞←⍵:→⋄⍵}¨⎕A∘.,⍵}' '

```

Theoretically, it would print until PASSWORD, but I encountered a work space full error after ZZZZ: 5-dimensional array is just too awesome.

EDIT: Must have been too long since I last fiddled with APL. How dare I missed the identity comparision ()!!!

### Explanation

`{...}`: Declares a function which...
`⎕A∘.,⍵`: Takes the outer product over concatenation (Every combination of an element of the left operand concatenated with an element of the right operand, just like Cartesian Product) between the 26 uppercase alpha (`⎕A`) and the argument ()

`{...}¨`: And for each element of the resulting set, plug that into a function which...
`⍞←⍵`: prints it out
`'PASSWORD '≡` and compare it with `'PASSWORD '`
: If the comparison returns true (`1`), then abort the program.
: Else just return the printed string.

: Finally, the outer function recurse itself.

(Then you are taking outer product over concat between the 26 alpha and the 26 alpha, which gives all the 2-letter combinations, and then outer product over concat between the 2-letter combinations and the 26 alpha, etc... Until you reach PASSWORD which triggers the abort)

`' '`: The spark!! That kick-start the recursive function with the space character.
> 2 votes

# Answer
# Python 2 - ~~153 152 151~~ 149 bytes

```
from itertools import*;R=range
for l in iter(chain(*[product(*((map(chr,R(65,91)),)*n))for n in R(1,9)]).next,tuple("passwore")):print ''.join(l)

```

Saved one byte by using UPPERCASE and one by using newlines instead of spaces.
> 2 votes

# Answer
### Golfscript 41

For lack of `'z'+1 == 'aa'` logic Golfscript can't win this one.

```
168036262484,(;{27base{96+}%' '+.96?0<*}%

```
* `168036262484,` create array from 0 to 168036262483
* `(;` drop the 0
* `{` .. `}%` iterate over array
* `27base` convert element to base 27 array
* `{96+}%` add 96 to each digit
* `' '+` convert to string and add a space to the end
* `.96?0<*` truncate string to zero if it contains char 96
> 1 votes

# Answer
In Ruby, ~~39~~ 40.

```
a=&`
0x1e0c2443dc.times{$><<a.succ!+' '}

```

..or `129052722140`. (Edit: formerly I had `129052722`. I had lost some digits cutting and pasting. Previous hex (`0x7B13032`) was for incorrect number.). Borrowed `a=?`` from @Doorknob to saves a character.
> 1 votes

# Answer
# Javascript: ~~57~~ 56 characters (thanks C5H8NNaO4)

Here's a solution that includes numbers as possible characters ("0", "1", "2", .., "passwor9", "passwora", "passworb", "passworc", "password")

```
for(i=-1;i++<1982613533017;console.log(i.toString(36)));

```

Here's a fiddle for testing (with only the last 100 iterations so it doesn't lock up your browser).
> 1 votes

# Answer
## Haskell, 101

```
main=putStrLn.concat.takeWhile(/="passwore ").tail.concat.iterate(\k->[x:y|x<-['a'..'z'],y<-k])$[" "]

```
> 1 votes

# Answer
## JavaScript ~~80~~ 76

```
for(i=s=0;s!="password";i++){s=i.toString(36).replace(/[0-9]/,'');console.log(s)}

```

fiddle \- stops at "pa".

however this does repeat things.
> 0 votes

# Answer
## Befunge (72)

```
<_v#:/*2+67\+++88*99%*2+76:
^ >$>:#,_84*+,1+:0\:" Lr$W~"67++**1+***6+`#@_

```

Prints strings 'a' to 'password' separated by spaces, then exits.

Below is a version that prints only the first 9\*9 = 81 words ('a' to 'dd'), for comparison. The `99*` is the number of iterations to perform.

```
<_v#:/*2+67\+++88*99%*2+76:
^ >$>:#,_84*+,1+:0\:99*`#@_

```
> 0 votes

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