# Question
Title: Are You the One? (Mastermind Derivative)
I've got a tough one for you!

My girlfriend recently came across a new show on MTV (USA). It's a terrible show, and everyone on it is trashy, but the "game" is pretty interesting. From Wikipedia:

> **Are You The One?** follows 20 people who are living together in Hawaii to find their perfect match. If the 10 men and 10 women are able to correctly choose all ten perfect matches in ten weeks, they will gain $1 million to split among them.

Now for the game portion (also from Wikipedia):

> Each episode the cast will pair up with who they believe their perfect match is to compete in a challenge. The winners of the challenge will go on a date, and have a chance to test their match in the truth booth. The cast members will choose one of the winning couples to go to the truth booth to determine if they are a perfect match or not. **This is the only way to confirm matches.** Each episode ends with a matching ceremony where the couples will be told how many perfect matches they have, but not which matches are correct.

**TL;DR:** This is a Mastermind derivative ( M(10,10) to be specific). The rules of the game are as follows:

1. You start with 2 sets of 10, let's call them Set A: {A,B,C,D,E,F,G,H,I,J} and Set 2: {1,2,3,4,5,6,7,8,9,10}
2. The computer creates a solution (not visible to you) in the form of {A1,B2,C3,D4,E5,F6,G7,H8,I9,J10}, where the members in set A are mapped 1-to-1 to set 2. Another example of a solution could be {A2,B5,C10,D8,E1,F7,G6,H4,I9,J3}.
3. Before your first turn, you get to ask if a single, particular pair of your choice is correct. Your question would be in the form of {A1} (e.g. {C8}), and you receive either a 1 (meaning correct) or 0 (meaning your guess is incorrect).
4. Your first actual turn. You make your first guess in the form of {A1,B2,C3,D4,E5,F6,G7,H8,I9,J10}, or any permutation of your choice. **Your guess cannot contain multiples of any item i.e. a guess of {A1,A2,A3,A4,A5,B6,B7,B8,B9,B10} is NOT a valid guess.** After each turn, the computer tells you the **number of correct matches, but NOT which matches are correct.**
5. Repeat steps 3 and 4 until you get every match correct (i.e. a response of 10), or until your 10 moves are up (whichever is sooner). If you solve it before or on your 10th turn, you win $1 million. Otherwise, you lose, and some people (or letters and numbers) go home alone to spend eternity with their 10 cats.

This is NOT a shortest code contest. **The person who can solve a random matching in the least *average* number of guesses will be the winner.** Clever game playing and calculation speed will also likely factor in. I am assuming the average number of turns will almost certainly be greater than 10, so the odds of you winning the $1 million prize (presumably paid by MTV, not me) is slim. Just *how* impossible is it for the cast to win the grand prize?

Note: Putting it in the {A1, B2, ...} format is not necessarily required. I simply used that form in the question to make it absolutely clear what the puzzle is. If you do not put it in this form, please just explain how to call it.

*Good luck!*

# Answer
> 6 votes
## Python 2 (run faster if run using Pypy)

**Believed to almost always guess the correct pairing in 10 rounds or lower**

My algorithm is taken from my answer for mastermind as my hobby (see in Ideone). The idea is to find the guess which minimize the number of possibilities left in the worst case. My algorithm below just brute force it, but to save time, it just pick random guess if the number of possibilities left is larger than `RANDOM_THRESHOLD`. You can play around with this parameter to speed things up or to see better performance.

The algorithm is quite slow, on average 10s for one run if run using Pypy (if using normal CPython interpreter it's around 30s) so I can't test it on the whole permutations. But the performance is quite good, after around 30 tests I haven't seen any instance where it can't find the correct pairing in 10 rounds or lower.

Anyway, if this is used in real life show, it has plenty of time before the next round (one week?) so this algorithm can be used in real life =D

So I think it's safe to assume that on average this will find the correct pairings in 10 guesses or lower.

Try it yourself. I might improve the speed in the next few days (EDIT: it seems difficult to further improve, so I'll just leave the code as is. I tried only doing random pick, but even at `size=7`, it fails in 3 of the 5040 cases, so I decided to keep the cleverer method). You can run it as:

```
pypy are_you_the_one.py 10

```

Or, if you just want to see how it works, input smaller number (so that it runs faster)

To run a full test (warning: it'll take very long for `size` \> 7), put a negative number.

Full test for `size=7` (completed in 2m 32s):

```
...
(6, 5, 4, 1, 3, 2, 0): 5 guesses
(6, 5, 4, 2, 0, 1, 3): 5 guesses
(6, 5, 4, 2, 0, 3, 1): 4 guesses
(6, 5, 4, 2, 1, 0, 3): 5 guesses
(6, 5, 4, 2, 1, 3, 0): 6 guesses
(6, 5, 4, 2, 3, 0, 1): 6 guesses
(6, 5, 4, 2, 3, 1, 0): 6 guesses
(6, 5, 4, 3, 0, 1, 2): 6 guesses
(6, 5, 4, 3, 0, 2, 1): 3 guesses
(6, 5, 4, 3, 1, 0, 2): 7 guesses
(6, 5, 4, 3, 1, 2, 0): 7 guesses
(6, 5, 4, 3, 2, 0, 1): 4 guesses
(6, 5, 4, 3, 2, 1, 0): 7 guesses
Average count: 5.05
Max count    : 7
Min count    : 1
Num success  : 5040

```

If `RANDOM_THRESHOLD` and `CLEVER_THRESHOLD` are both set to a very high value (like 50000), it'll force the algorithm to find the optimal guess that minimizes the number of possibilities in the worst case. This is very slow, but very powerful. For example, running it on `size=6` asserts that it can find the correct pairings in maximum 5 rounds.

Although the average is higher compared to using the approximation (which is 4.11 rounds on average), but it always succeeds, even more with one round left to spare. This further strengthen our hypothesis that when `size=10`, it should almost always find the correct pairings in 10 rounds or less.

The result (completed in 3m 9s):

```
(5, 4, 2, 1, 0, 3): 5 guesses
(5, 4, 2, 1, 3, 0): 5 guesses
(5, 4, 2, 3, 0, 1): 4 guesses
(5, 4, 2, 3, 1, 0): 4 guesses
(5, 4, 3, 0, 1, 2): 5 guesses
(5, 4, 3, 0, 2, 1): 5 guesses
(5, 4, 3, 1, 0, 2): 5 guesses
(5, 4, 3, 1, 2, 0): 5 guesses
(5, 4, 3, 2, 0, 1): 5 guesses
(5, 4, 3, 2, 1, 0): 5 guesses
Average count: 4.41
Max count    : 5
Min count    : 1
Num success  : 720

```

The code.

```
from itertools import permutations, combinations
import random, sys
from collections import Counter

INTERACTIVE = False
ORIG_PERMS = []
RANDOM_THRESHOLD = 100
CLEVER_THRESHOLD = 0

class Unbuffered():
    def __init__(self, stream):
        self.stream = stream

    def write(self, data):
        self.stream.write(data)
        self.stream.flush()

    def __getattr__(self, attr):
        self.stream.getattr(attr)
sys.stdout = Unbuffered(sys.stdout)

def init(size):
    global ORIG_PERMS
    ORIG_PERMS = list(permutations(range(size)))

def evaluate(solution, guess):
    if len(guess) == len(solution):
        cor = 0
        for sol, gss in zip(solution, guess):
            if sol == gss:
                cor += 1
        return cor
    else:
        return 1 if solution[guess[0]] == guess[1] else 0

def remove_perms(perms, evaluation, guess):
    return [perm for perm in perms if evaluate(perm, guess)==evaluation]

def guess_one(possible_perms, guessed_all, count):
    if count == 1:
        return (0,0)
    pairs = Counter()
    for perm in possible_perms:
        for pair in enumerate(perm):
            pairs[pair] += 1
    perm_cnt = len(possible_perms)
    return sorted(pairs.items(), key=lambda x: (abs(perm_cnt-x[1]) if x[1]<perm_cnt else perm_cnt,x[0]) )[0][0]

def guess_all(possible_perms, guessed_all, count):
    size = len(possible_perms[0])
    if count == 1:
        fact = 1
        for i in range(2, size):
            fact *= i
        if len(possible_perms) == fact:
            return tuple(range(size))
        else:
            return tuple([1,0]+range(2,size))
    if len(possible_perms) == 1:
        return possible_perms[0]
    if count < size and len(possible_perms) > RANDOM_THRESHOLD:
        return possible_perms[random.randint(0, len(possible_perms)-1)]
    elif count == size or len(possible_perms) > CLEVER_THRESHOLD:
        (_, next_guess) = min((max(((len(remove_perms(possible_perms, evaluation, next_guess)), next_guess) for evaluation in range(len(next_guess))), key=lambda x: x[0])
                               for next_guess in possible_perms if next_guess not in guessed_all), key=lambda x: x[0])
        return next_guess
    else:
        (_, next_guess) = min((max(((len(remove_perms(possible_perms, evaluation, next_guess)), next_guess) for evaluation in range(len(next_guess))), key=lambda x: x[0])
                               for next_guess in ORIG_PERMS if next_guess not in guessed_all), key=lambda x: x[0])
        return next_guess

def main(size=4):
    if size < 0:
        size = -size
        init(size)
        counts = []
        for solution in ORIG_PERMS:
            count = run_one(solution, False)
            counts.append(count)
            print '%s: %d guesses' % (solution, count)
        sum_count = float(sum(counts))
        print 'Average count: %.2f' % (sum_count/len(counts))
        print 'Max count    : %d' % max(counts)
        print 'Min count    : %d' % min(counts)
        print 'Num success  : %d' % sum(1 for count in counts if count <= size)
    else:
        init(size)
        solution = ORIG_PERMS[random.randint(0,len(ORIG_PERMS)-1)]
        run_one(solution, True)

def run_one(solution, should_print):
    if should_print:
        print solution
    size = len(solution)
    cur_guess = None
    possible_perms = list(ORIG_PERMS)
    count = 0
    guessed_one = []
    guessed_all = []
    while True:
        count += 1
        # Round A, guess one pair
        if should_print:
            print 'Round %dA' % count
        if should_print:
            print 'Num of possibilities: %d' % len(possible_perms)
        cur_guess = guess_one(possible_perms, guessed_all, count)
        if should_print:
            print 'Guess: %s' % str(cur_guess)
        if INTERACTIVE:
            evaluation = int(raw_input('Number of correct pairs: '))
        else:
            evaluation = evaluate(solution, cur_guess)
            if should_print:
                print 'Evaluation: %s' % str(evaluation)
        possible_perms = remove_perms(possible_perms, evaluation, cur_guess)

        # Round B, guess all pairs
        if should_print:
            print 'Round %dB' % count
            print 'Num of possibilities: %d' % len(possible_perms)
        cur_guess = guess_all(possible_perms, guessed_all, count)
        if should_print:
            print 'Guess: %s' % str(cur_guess)
        guessed_all.append(cur_guess)
        if INTERACTIVE:
            evaluation = int(raw_input('Number of correct pairs: '))
        else:
            evaluation = evaluate(solution, cur_guess)
            if should_print: print 'Evaluation: %s' % str(evaluation)
        if evaluation == size:
            if should_print:
                print 'Found %s in %d guesses' % (str(cur_guess), count)
            else:
                return count
            break
        possible_perms = remove_perms(possible_perms, evaluation, cur_guess)

if __name__=='__main__':
    size = 4
    if len(sys.argv) >= 2:
        size = int(sys.argv[1])
        if len(sys.argv) >= 3:
            INTERACTIVE = bool(int(sys.argv[2]))
    main(size)

```

# Answer
> 4 votes
# Fast Multi-Threaded C++ Version

I know it's been a while since this thread was active, but I have a cool addition to share: Here's a C++ implementation of the minimax algorithm for *Are You The One?*, which uses multi-threading to speed up the evaluation of each possible guess.

This version is much faster than the Python version (over 100x faster when original Python version is set to maximum `RANDOM_THRESHOLD` and `CLEVER_THRESHOLD`). It doesn't use any random guessing, but rather evaluates all permutations and submits as its guess the permutation that eliminates the greatest number of possible solutions (given the worst-case response).

For smaller games, calling "ayto -n" will run the game on all n! possible hidden matchings, and will give you a short summary of the results at the end.

Since it's still intractable to evaluate all 10! possible hidden matchings, if you call "ayto 10", for example, the simulator makes its fixed first three guesses, then runs minimax to choose its guess and assumes that it was given the worst-case evaluation. This leads us down a "worst-case path" to a hidden vector that is presumably in the class of vectors that takes the algorithm a maximum number of guesses to identify. This conjecture has not been tested.

Up to *n = 9*, there hasn't been a simulation that has taken more than *n* turns to solve.

To test this yourself, an example compilation would be the following:

```
g++ -std=c++11 -lpthread -o ayto ayto.cpp

```

Here's a small example with output:

```
$ ./ayto -4
Found (0, 1, 2, 3) in 2 guesses.
Found (0, 1, 3, 2) in 3 guesses.
Found (0, 2, 1, 3) in 2 guesses.
Found (0, 2, 3, 1) in 3 guesses.
Found (0, 3, 1, 2) in 2 guesses.
Found (0, 3, 2, 1) in 2 guesses.
Found (1, 0, 2, 3) in 1 guesses.
Found (1, 0, 3, 2) in 3 guesses.
Found (1, 2, 0, 3) in 3 guesses.
Found (1, 2, 3, 0) in 3 guesses.
Found (1, 3, 0, 2) in 3 guesses.
Found (1, 3, 2, 0) in 3 guesses.
Found (2, 0, 1, 3) in 3 guesses.
Found (2, 0, 3, 1) in 3 guesses.
Found (2, 1, 0, 3) in 3 guesses.
Found (2, 1, 3, 0) in 3 guesses.
Found (2, 3, 0, 1) in 3 guesses.
Found (2, 3, 1, 0) in 3 guesses.
Found (3, 0, 1, 2) in 3 guesses.
Found (3, 0, 2, 1) in 3 guesses.
Found (3, 1, 0, 2) in 3 guesses.
Found (3, 1, 2, 0) in 3 guesses.
Found (3, 2, 0, 1) in 3 guesses.
Found (3, 2, 1, 0) in 3 guesses.
***** SUMMARY *****
Avg. Turns: 2.75
Worst Hidden Vector: (0, 1, 3, 2) in 3 turns.

```

## Code

```
/* Multithreaded Mini-max Solver for MTV's Are You The One? */

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <map>
#include <thread>
#include <cmath>

#define TEN_FACT (3628800)
#define NUM_CHUNKS (8)

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::string;
using std::map;
using std::pair;
using std::find;
using std::abs;
using std::atoi;
using std::next_permutation;
using std::max_element;
using std::accumulate;
using std::reverse;
using std::thread;

struct args {
    vector<string> *perms;
    vector<string> *chunk;
    pair<string, int> *cd;
    int thread_id;
};

void simulate_game(const string &hidden, map<string, int> &turns_taken,
                   bool running_all);
bool picmp(const pair<string, int> &p1, const pair<string, int> &p2);
double map_avg(const map<string, int> &mp);
int nrand(int n);
int evaluate(const string &sol, const string &query);
vector<string> remove_perms(vector<string> &perms, int eval, string &query);
pair<string, int> guess_tb(vector<string> &perms, vector<string> &guessed_tb, int turn);
pair<string, int> guess_pm(vector<string> &perms, vector<string> &guessed, int turn);
void make_chunks(vector<string> &orig, vector<vector<string> > &chunks, int n);
string min_candidate(pair<string, int> *candidates, int n);
void get_score(struct args *args);
int wc_response(string &guess, vector<string> &perms);
bool prcmp(pair<int, int> x, pair<int, int> y);
void sequence_print(string s);
struct args **create_args(vector<string> &perms, pair<string, int> *cd, vector<string> &chunk, int thread_id);

vector<string> ORIGPERMS;

int main(int argc, char **argv)
{
    int sz;
    map<string, int> turns_taken;
    const string digits = "0123456789";
    bool running_all = false;

    if (argc != 2) {
        cout << "usage: 'ayto npairs'" << endl;
        return 1;
    } else {
        if ((sz = atoi(argv[1])) < 0) {
            sz = -sz;
            running_all = true;
        }
        if (sz < 3 || sz > 10) {
            cout << "usage: 'ayto npairs' where 3 <= npairs <= 10" << endl;;
            return 1;
        }
    }

    // initialize ORIGPERMS and possible_perms
    string range = digits.substr(0, sz);
    do {
        ORIGPERMS.push_back(range);
    } while (next_permutation(range.begin(), range.end()));

    if (running_all) {
        for (vector<string>::const_iterator it = ORIGPERMS.begin();
             it != ORIGPERMS.end(); ++it) {
            simulate_game(*it, turns_taken, running_all);
        }
        cout << "***** SUMMARY *****\n";
        cout << "Avg. Turns: " << map_avg(turns_taken) << endl;
        pair<string, int> wc = *max_element(turns_taken.begin(),
                                            turns_taken.end(), picmp);
        cout << "Worst Hidden Vector: ";
        sequence_print(wc.first);
        cout << " in " << wc.second << " turns." << endl;
    } else {
        string hidden = ORIGPERMS[nrand(ORIGPERMS.size())];
        simulate_game(hidden, turns_taken, running_all);
    }

    return 0;
}

// simulate_game:  run a single round of AYTO on hidden vector
void simulate_game(const string &hidden, map<string, int> &turns_taken,
                   bool running_all)
{
    vector<string> possible_perms = ORIGPERMS;
    pair<string, int> tbguess;
    pair<string, int> pmguess;
    vector<string> guessed;
    vector<string> guessed_tb;
    int e;
    int sz = hidden.size();

    if (!running_all) {
        cout << "Running AYTO Simulator on Hidden Vector: ";
        sequence_print(hidden);
        cout << endl;
    }

    for (int turn = 1; ; ++turn) {
        // stage one: truth booth
        if (!running_all) {
            cout << "**** Round " << turn << "A ****" << endl;
            cout << "Num. Possibilities: " << possible_perms.size() << endl;
        }
        tbguess = guess_tb(possible_perms, guessed_tb, turn);
        if (!running_all) {
            cout << "Guess: ";
            sequence_print(tbguess.first);
            cout << endl;
            e = tbguess.second;
            cout << "Worst-Case Evaluation: " << e << endl;
        } else {
            e = evaluate(hidden, tbguess.first);
        }
        possible_perms = remove_perms(possible_perms, e, tbguess.first);

        // stage two: perfect matching
        if (!running_all) {
            cout << "Round " << turn << "B" << endl;
            cout << "Num. Possibilities: " << possible_perms.size() << endl;
        }
        pmguess = guess_pm(possible_perms, guessed, turn);

        if (!running_all) {
            cout << "Guess: ";
            sequence_print(pmguess.first);
            cout << endl;
            e = pmguess.second;
            cout << "Worst-Case Evaluation: " << e << endl;
        } else {
            e = evaluate(hidden, pmguess.first);
        }
        if (e == sz) {
            cout << "Found ";
            sequence_print(pmguess.first);
            cout << " in " << turn << " guesses." << endl;
            turns_taken[pmguess.first] = turn;
            break;
        }

        possible_perms = remove_perms(possible_perms, e, pmguess.first);
    }
}

// map_avg:  returns average int component of a map<string, int> type
double map_avg(const map<string, int> &mp)
{
    double sum = 0.0;

    for (map<string, int>::const_iterator it = mp.begin();
         it != mp.end(); ++it) {
        sum += it->second;
    }

    return sum / mp.size();
}

// picmp:  comparison function for pair<string, int> types, via int component
bool picmp(const pair<string, int> &p1, const pair<string, int> &p2)
{
    return p1.second < p2.second;
}

// nrand:  random integer in range [0, n)
int nrand(int n)
{
    srand(time(NULL));

    return rand() % n;
}

// evaluate:  number of black hits from permutation or truth booth query
int evaluate(const string &sol, const string &query)
{
    int hits = 0;

    if (sol.size() == query.size()) {
        // permutation query
        int s = sol.size();
        for (int i = 0; i < s; i++) {
            if (sol[i] == query[i])
                ++hits;
        }
    } else {
        // truth booth query
        if (sol[atoi(query.substr(0, 1).c_str())] == query[1])
            ++hits;
    }

    return hits;
}

// remove_perms:  remove solutions that are no longer possible after an eval
vector<string> remove_perms(vector<string> &perms, int eval, string &query)
{
    vector<string> new_perms;

    for (vector<string>::iterator i = perms.begin(); i != perms.end(); i++) {
        if (evaluate(*i, query) == eval) {
            new_perms.push_back(*i);
        }
    }

    return new_perms;
}

// guess_tb:  guesses best pair (pos, val) to go to the truth booth
pair<string, int> guess_tb(vector<string> &possible_perms,
                           vector<string> &guessed_tb, int turn)
{
    static const string digits = "0123456789";
    int n = possible_perms[0].size();
    pair<string, int> next_guess;

    if (turn == 1) {
        next_guess.first = "00";
        next_guess.second = 0;
    } else if (possible_perms.size() == 1) {
        next_guess.first = "0" + possible_perms[0].substr(0, 1);
        next_guess.second = 1;
    } else {
        map<string, double> pair_to_count;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                pair_to_count[digits.substr(i, 1) + digits.substr(j, 1)] = 0;
            }
        }

        // count up the occurrences of each pair in the possible perms
        for (vector<string>::iterator p = possible_perms.begin();
             p != possible_perms.end(); p++) {
            int len = possible_perms[0].size();
            for (int i = 0; i < len; i++) {
                pair_to_count[digits.substr(i, 1) + (*p).substr(i, 1)] += 1;
            }
        }

        double best_dist = 1;
        int perm_cnt = possible_perms.size();
        for (map<string, double>::iterator i = pair_to_count.begin();
             i != pair_to_count.end(); i++) {
            if (find(guessed_tb.begin(), guessed_tb.end(), i->first)
                == guessed_tb.end()) {
                // hasn't been guessed yet
                if (abs(i->second/perm_cnt - .5) < best_dist) {
                    next_guess.first = i->first;
                    best_dist = abs(i->second/perm_cnt - .5);
                    if (i->second / perm_cnt < 0.5) // occurs in < half perms
                        next_guess.second = 0;
                    else                            // occurs in >= half perms
                        next_guess.second = 1;
                }
            }
        }
    }

    guessed_tb.push_back(next_guess.first);

    return next_guess;
}

// guess_pm:  guess a full permutation using minimax
pair<string, int> guess_pm(vector<string> &possible_perms,
                           vector<string> &guessed, int turn)
{
    static const string digits = "0123456789";
    pair<string, int> next_guess;
    vector<vector<string> > chunks;
    int sz = possible_perms[0].size();

    // on first turn, we guess "0, 1, ..., n-1" if truth booth was correct
    // or "1, 0, ..., n-1" if truth booth was incorrect
    if (turn == 1) {
        int fact, i;
        for (i = 2, fact = 1; i <= sz; fact *= i++)
            ;
        if (possible_perms.size() == fact) {
            next_guess.first = digits.substr(0, sz);
            next_guess.second = 1;
        } else {
            next_guess.first = "10" + digits.substr(2, sz - 2);
            next_guess.second = 1;
        }
    } else if (possible_perms.size() == 1) {
        next_guess.first = possible_perms[0];
        next_guess.second = possible_perms[0].size();
    } else {
        // run multi-threaded minimax to get next guess
        pair<string, int> candidates[NUM_CHUNKS];
        vector<thread> jobs;
        make_chunks(ORIGPERMS, chunks, NUM_CHUNKS);
        struct args **args = create_args(possible_perms, candidates, chunks[0], 0);

        for (int j = 0; j < NUM_CHUNKS; j++) {
            args[j]->chunk = &(chunks[j]);
            args[j]->thread_id = j;
            jobs.push_back(thread(get_score, args[j]));
        }
        for (int j = 0; j < NUM_CHUNKS; j++) {
            jobs[j].join();
        }

        next_guess.first = min_candidate(candidates, NUM_CHUNKS);
        next_guess.second = wc_response(next_guess.first, possible_perms);

        for (int j = 0; j < NUM_CHUNKS; j++)
            free(args[j]);
        free(args);
    }

    guessed.push_back(next_guess.first);

    return next_guess;
}

struct args **create_args(vector<string> &perms, pair<string, int> *cd, vector<string> &chunk, int thread_id)
{
    struct args **args = (struct args **) malloc(sizeof(struct args*)*NUM_CHUNKS);
    assert(args);
    for (int i = 0; i < NUM_CHUNKS; i++) {
        args[i] = (struct args *) malloc(sizeof(struct args));
        assert(args[i]);
        args[i]->perms = &perms;
        args[i]->cd = cd;
    }

    return args;
}

// make_chunks:  return pointers to n (nearly) equally sized vectors
//                from the original vector
void make_chunks(vector<string> &orig, vector<vector<string> > &chunks, int n)
{
    int sz = orig.size();
    int chunk_sz = sz / n;
    int n_with_extra = sz % n;
    vector<string>::iterator b = orig.begin();
    vector<string>::iterator e;

    for (int i = 0; i < n; i++) {
        int m = chunk_sz;    // size of this chunk
        if (n_with_extra) {
            ++m;
            --n_with_extra;
        }
        e = b + m;
        vector<string> subvec(b, e);
        chunks.push_back(subvec);
        b = e;
    }
}

// min_candidate:  string with min int from array of pair<string, ints>
string min_candidate(pair<string, int> *candidates, int n)
{
    int i, minsofar;
    string minstring;

    minstring = candidates[0].first;
    minsofar = candidates[0].second;
    for (i = 1; i < n; ++i) {
        if (candidates[i].second < minsofar) {
            minsofar = candidates[i].second;
            minstring = candidates[i].first;
        }
    }

    return minstring;
}

// get_score:  find the maximum number of remaining solutions over all
//             possible responses to the query s
//             this version takes a chunk and finds the guess with lowest score
//             from that chunk
void get_score(struct args *args)
{
    // parse the args struct
    vector<string> &chunk = *(args->chunk);
    vector<string> &perms = *(args->perms);
    pair<string, int> *cd = args->cd;
    int thread_id = args->thread_id;

    typedef vector<string>::const_iterator vec_iter;
    int sz = perms[0].size();

    pair<string, int> best_guess;
    best_guess.second = perms.size();
    int wc_num_remaining;
    for (vec_iter s = chunk.begin(); s != chunk.end(); ++s) {
        vector<int> matches(sz + 1, 0);
        for (vec_iter p = perms.begin(); p != perms.end(); ++p) {
            ++matches[evaluate(*s, *p)];
        }
        wc_num_remaining = *max_element(matches.begin(), matches.end());
        if (wc_num_remaining < best_guess.second) {
            best_guess.first = *s;
            best_guess.second = wc_num_remaining;
        }
    }

    cd[thread_id] = best_guess;

    return;
}

// wc_response:  the response to guess that eliminates the least solutions
int wc_response(string &guess, vector<string> &perms)
{
    map<int, int> matches_eval;

    for (vector<string>::iterator it = perms.begin(); it!=perms.end(); ++it) {
        ++matches_eval[evaluate(guess, *it)];
    }

    return max_element(matches_eval.begin(), matches_eval.end(), prcmp)->first;
}

// prcmp:  comparison function for pair<int, int> types in map
bool prcmp(pair<int, int> x, pair<int, int> y)
{
    return x.second < y.second;
}

void sequence_print(const string s)
{
    for (string::const_iterator i = s.begin(); i != s.end(); i++) {
        if (i == s.begin())
            cout << "(";
        cout << *i;
        if (i != s.end() - 1)
            cout << ", ";
        else
            cout << ")";
    }
}

```

# Answer
> 3 votes
## CJam -19 turns- An Idiot's Strategy

This is not a serious answer but a demonstration. This is an idiot's solution where he does not take into account the number of correct pairings information provided from the second part of the turn. With completely random pairings, this takes an average of 27 weeks. This answer is insuffienct as I have said but indicates that the odds for an intellegent group (much more intellegent that this program) is likely not as slim as you might expect. The more intellegent algorithms i've written, however take alot more time to run so I can' actually get answers from them.

**Update:** The code below was updated to use state that it should remove ones that don't work if the only correct ones are ones we already knew were correct. It was also editted to show my random "correct answer" generator. The average result is now only 19. It is still a dumb solution but it is better than the previous marginally.

```
A,{__,mr=_@@-}A*;]sedS*:Z;

ZS/:i:G;                               "Set the input (goal) to G";
{UU@{G2$==@+\)}%~;}:C;                 "This is the tool to count how many of an array agree with G";
{:Y;1$1$<{Y-}%Yaa+@@)>{Y-}%+}:S;       "for stack A X Y, sets the Xth value in the array to Y";
{:Y;1$1$<2$2$=Y-a+@@)>+}:R;            "for stack A X Y, removes Y from the Xth value in the array";

1:D;                                   "Set turn counter to one. if zero exits loop";

A,]A*                                  "array of arrays that has all possible values for an ordering";

{                                      "start of loop";

_V=(\;_GV=={V\SV):V;}{V\R}?            "Guesses a number for the first unknown. If right sets the pair; else erases it";

_[{(_,_{mr=}{;;11}?:Y\{Y-}%}A*;]_C     "guesses random possible arrangement and determines how many are right, error=11";
\_{+}*45-:Y{Y;{_11={;BY-}{}?}%}{}?\    "error correct by including the missing number";

_V={;V:X>{X\RX):X;}%~LV}{}?            "if all new are wrong, makes sure they aren't guessed again";
_A={Dp0:D;;p;}{D):D;;;}?               "If all are right, prints it an tells loop to exit.  Else increments counter";

D}g                                    "repeat from start of loop";

```

---
Tags: code-challenge, game
---


title: Non-idempotent Python

text:
# Question
Title: Non-idempotent Python
Write a few lines of Python code, `X`, that does not reference any global variables, such that

```
def method():
    X
    print(a)

method()

```

prints `1` but

```
def method():
    X
    X
    print(a)

method()

```

prints `2`.

---

So, I hate to be a stickler, but it seems like `vars` and `locals` are actually global variables in Python:

```
def test_global_1():
    global vars, locals
    vars = lambda: 2
    locals = lambda: 3

def test_global_2():
    print(vars())
    print(locals())

test_global_1()
test_global_2()

```

---

Also, it looks like people would like to see objective winning criteria for puzzles like this. Code length doesn't really feel right here so perhaps we could make a system of brownie points for various novel features of the code? I'm not sure exactly what these could be but here's a start:

* +1 for really truly no globals (no `vars` or `locals`)
* +1 for being the first to post a particular technique
* +1 for the shortest solution posted
* +1 for a solution involving only a single Python statement
* +1 for interesting "hacks" like joining at lexical non-boundaries
* +1 for not using exceptions

And if you can think of more you could edit this question to add to the list.

Can this problem be solved without using exceptions *and* without using globals like `vars` and `locals`? I suspect it can, though I haven't figured out exactly how yet...

# Answer
> 12 votes
```
def method():
    if 'a' not in vars():a=0
    a+=1
    if 'a' not in vars():a=0
    a+=1
    print(a)

```

Initializes the variable `a` to `0` only if it's not already initialized in the variables table. Then, increments it.

More briefly (thanks to histocrat for `len`):

```
def method():
    a=len(vars())+1
    a=len(vars())+1
    print(a)

```

If the two copies of `X` could be on the same line, we could do

```
a=0;a+=1;a

```

which doubles to

```
a=0;a+=1;aa=0;a+=1;a

```

with the "sacrificial lamb" `aa` eating up the second variable assignment.

# Answer
> 9 votes
# Python

Thought of this solution, since `try` and `except` was the first way I thought of to determine if a variable existed yet or not.

```
def method():
    try:a+=1
    except:a=1
    print(a)

```

# Answer
> 5 votes
# Python 2

```
def method():
    exec'';locals()['a']=locals().get('a',0)+1
    exec'';locals()['a']=locals().get('a',0)+1
    print a

method()

```

Basically, when `exec` is encountered in Python 2, it causes a special flag (`0x01`) to be removed from `method.func_code.co_flags`, which makes `locals` assignments have an effect. I exploited this to implement `nonlocal` support in Python 2 (see line 43 for the xor that modifies the flag).

# Answer
> 2 votes
My first idea (and then smooshing it) was:

```
def method():
    a=2if'a'in vars()else 1
    a=2if'a'in vars()else 1
    print(a)

```

But histocrat's answer seems optimal.

# Answer
> 1 votes
My attempt. Uses the math module to track if X is run once or twice.

```
def module():
  import sys
  if 'math' in sys.modules:
    a+=1
  else:
    a=1
  import math

  import sys
  if 'math' in sys.modules:
    a+=1
  else:
    a=1
  import math

  print(a)

module()

```

# Answer
> 0 votes
```
def method():
    #### X-block
    try:a
    except NameError:a=1
    else:a=2
    ####
    print(a)

```

The `try` block checks if the variable a is defined.
If variable not defined,(this is only when X-block is present once) then `NameError` Exception is raised.
If variable is defined, (this is when X-block is present twice) then `else` will be entered .

# Answer
> 0 votes
```
def method(a=[]):
  a.append(a)
  print len(a)

```

Edited in response to comment: a is a list of empty lists of length n, where n is the number of time you've called method. Calling this method twice prints 1 then 2.

---
Tags: popularity-contest, python, programming-puzzle
---


title: Enter your name via a D-pad

text:
# Question
Title: Enter your name via a D-pad
# The puzzle:

Consider a console/hand-held game with a d-pad where you are required to enter a name of sorts. This appeared in many older games before the use of QWERTY was popularised in consoles (e.g. I believe the Wii uses a QWERTY keyboard layout for input). Typically, the on-screen keyboard looks to the effect of\*:

Default:

```
0 1 2 3 4 5 6 7 8 9
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 _ + ^ =

```

With the case switched:

```
0 1 2 3 4 5 6 7 8 9
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 - + ^ =

```

That is, all alphanumeric keys and the following:

`_`: A single space
`-`: A hyphen
`+`: Switch case for the next letter only
`^`: Toggle caps lock (that is, switch the case of all letters)
`=`: Enter, complete

\*Obviously I replaced keys like "BKSP" and "ENTER" with shorter versions

And then the hardware would include a d-pad (or some form of control where you could go `up`, `down`, `left` and `right`)

The screen also typically let you move from one side directly to the other. That is, if you were focussed on the letter `J`, pressing `right` would allow you to move to the letter `A`.

Whenever I was entering my name, I'd always try to work out the quickest way to do so.

# Goal:

Your program will take string input which may include any alphanumeric character including a space and hyphen, and your goal is to **output the shortest amount of *key presses*** on the d-pad to output the required string.

# Considerations:

You do not need to include the key pressed for *pressing* the actual character.
Focus always starts at the `A`
Enter `=` must be *pressed* at the end

# Example:

`input: Code Golf`
`output: 43`

**Explained:**
`A` -\> `C` = 2
`C` -\> `^` = 6 (moving to the left)
`^` -\> `o` = 5
`o` -\> `d` = 2
`d` -\> `e` = 1
`e` -\> `+` = 5
`+` -\> `_` = 1
`_` -\> `+` = 1
`+` -\> `G` = 3
`G` -\> `o` = 3
`o` -\> `l` = 3
`l` -\> `f` = 5
`f` -\> `=` = 6

Note that it is quicker to hit the `+` twice for a `_` and a `G` than it is to hit `^` once, then swap back.

The winning submission (I'll allow at least 1w) will be the shortest solution (in bytes). As this is my first question, I hope this is clear and not too hard.

# Answer
# Ruby (369 bytes)

Takes input from command line.

```
K="0123456789"+('A'..'Z').to_a.join+" +^="
Q=K.downcase.sub' ','-'
def d x,y
t,s=(x/10-y/10).abs,(x%10-y%10).abs
[t,4-t].min+[s,10-s].min
end
def v s,i,l,a
return l if s.empty?
c,r=s[0],s[1..-1]
j=K.index(c.upcase)||36
return v(r,j,l+d(i,j),a)if a.include?c
s,p=d(i,37)+d(37,j),d(i,38)+d(38,j)
[v(r,j,l+s,a),v(r,j,l+p,a==K ? Q : K)].min
end
puts v("#{ARGV[0]}=",10,0,K)

```

Saved a bunch of bytes thanks to @Charlie :)
> 5 votes

# Answer
# Swift 1.2, ~~812~~ ~~588~~ 670 bytes

Edit: Removed 224 bytes by replacing the large arrays of numbers with a Range and converting it to an Array instead.

Edit2: Added looping vertically

```
typealias S=String
typealias I=Int
var A:(I)->S={S(UnicodeScalar($0))},B:(I)->(I,I)={a in(a%10,a/10)},a=Array(48...57).map{A($0)},b=[a+(Array(65...90)+[32,43,94,61]).map{A($0)},a+(Array(97...122)+[45,43,94,61]).map{A($0)}],z=Process.arguments
z.removeAtIndex(0)
func C(e:I,f:I)->I{let(a,b)=B(e),(c,d)=B(f)
return min(abs(d-b), abs(4-(d-b)))+min(abs(c-a),abs(10-(c-a)))}
func D(c:S,_ e:I=10,_ f:Bool=false,_ g:Bool=false)->I{if count(c)==0{return C(e,39)}
let h=c.startIndex,i=c.endIndex,j=S(c[h])
if let k=find(b[f ?1:0],j){return C(e,k)+D(c[advance(h,1)..<i],k,(g ?(!f):f),false)}else{return min(C(e,37)+D(c,37,!f,true),C(e,38)+D(c,38,!f,false))}}
print(D(" ".join(z)))

```

To run, put the code in a `.swift` file and run it with `swift <filename> <your name>`

---

This uses the simple approach where the two 'keyboards' are stored as arrays.

`B:(I)->(I,I)={a in(a%10,a/10)}` Converts an index from the array to an x,y position on the virtual keyboard.

`func C(e:I,f:I)->I{let(a,b)=B(e),(c,d)=B(f)
 return abs(d-b)+min(abs(c-a),abs(10-(c-a)))}` Takes a start/end index and returns the minimum number of moves to get from once to the other (accounting for horizontal wrap)

`func D(c:S,_ e:I=10,_ f:Bool=false,_ g:Bool=false)->I` Is the main recursive function that does most of the calculations. It calculates the distance from the current position to the target character, unless the case should change, then it calculates **both** the *shift* **and** the *caps lock* methods and takes the smallest.

Running `swift codegolf.swift Code Golf` prints `43`
> 9 votes

# Answer
# Python ~~679~~ ~~661~~ ~~619~~ ~~602~~ ~~589~~ ~~576~~ ~~539~~ ~~520~~ ~~496~~ 482 Bytes

Run this and it will ask for a input (without prompt text). For the input `Code Golf` it prints `43`.

```
a=input()+'=';b=0;c="0123456789abcdefghijklmnopqrstuvwxyz-+^=";d=0;e=[0,1];f='+';g='^';h=[i.isupper()or i==' 'for i in a];i=abs;p=lambda z:all([i==b for i in z]);q=0
def l(z):global s;k=c.index(z.lower().replace(' ','-'));s=[k%10,int(k/10)];m,n=s;return sum([min(i(m-e[0]),i(10-(m-e[0]))),min(i(n-e[1]),i(4-(n-e[1])))])
def o(z):global d,e;d+=l(z);e=s
for r in a:
 if p(h[q:q+3]):o(g);b^=1
 if p(h[q:q+2]):
  if l(f)<l(g):o(f)
  else:o(g);b^=1
 if p([h[q]]):o(f)
 o(r);q+=1
print(d)

```

---

Full program:

```
input = input() + '='
capsOn = False

keys = "0123456789abcdefghijklmnopqrstuvwxyz-+^="
totalKeys = 0
caret = [0, 1]

shiftKey = '+'
capsKey = '^'

cases = [char.isupper() or char == ' ' for char in input]

def locate(char):
    """
        Find the location of the char on the keyboard
        regardless of case
    """
    location = keys.find(char.replace(' ', '-').lower())
    return [location % 10, int(location / 10)]

def dist(key):
    """
        Calculate the min dist to a char
    """
    nx, ny = locate(key)
    return sum([min(abs(nx - caret[0]), abs(10 - (nx - caret[0]))), min(abs(ny - caret[1]), abs(4 - (ny - caret[1])))])

def moveTo(char):
    """
        Move the caret to the char, ignoring case and
        adds the dist to the tally
    """
    global totalKeys, caret
    totalKeys = totalKeys + dist(char)

    print(keys[caret[0] + caret[1] * 10], '->', char, '=', dist(char))

    caret = locate(char)

diffCase = lambda case: all([i == capsOn for i in case])

for ind, ch in enumerate(input):
    if diffCase(cases[ind:ind + 3]): # use caps
        moveTo(capsKey)
        capsOn ^= 1
    elif diffCase(cases[ind:ind + 2]): # use closest
        if dist(shiftKey) < dist(capsKey):
            moveTo(shiftKey)
        else:
            moveTo(capsKey)
            capsOn ^= 1
    elif diffCase([cases[ind]]): # use shift
        moveTo(shiftKey)

    moveTo(ch) # apply the move

print('Total:', totalKeys)

```

---

## Extended output from the full program:

```
Code Golf
a -> C = 2
c -> ^ = 6
^ -> o = 5
o -> d = 2
d -> e = 1
e -> + = 5
+ -> _ = 1
- -> + = 1
+ -> G = 3
g -> o = 3
o -> l = 3
l -> f = 5
f -> = = 6
Total: 43

```

---

> Saved a byte thanks to @justin https://codegolf.stackexchange.com/a/18983/42736
> 4 @xnor https://codegolf.stackexchange.com/a/40791/42736 19 thanks to @Alex
> 4 votes

# Answer
# C 675 Bytes

Takes input from command line argument. Uses recursive main:

```
#define Y(_) (!isdigit(_)?!isalpha(_)?3:1+(toupper(_)-65)/10:0)
#define X(_) (!isdigit(_)?!isalpha(_)?_-32&&_-45?_-43?9-(_==94):7:6:(toupper(_)-5)%10:_-48)
x,y,z;char*s;main(a,_,p,q,r){a<2?s[_]?!isdigit(s[_])&&((s[_]-32&&!isupper(s[_]))||!a)&&((s[_]-45&&!islower(s[_]))||a)?q=x,r=y,main(3,43),p=z,x=X(43),y=Y(43),main(3,s[_]),p+=z,x=X(s[_]),y=Y(s[_]),main(a,_+1),p+=z,x=q,y=r,main(3,94),q=z,x=X(94),y=Y(94),main(3,s[_]),q+=z,x=X(s[_]),y=Y(s[_]),main(!a,_+1),q+=z,z=(q<p?q:p):(main(3,s[_]),q=z,x=X(s[_]),y=Y(s[_]),main(a,_+1),z+=q):(main(3,61)):(a<3?s=((char**)_)[1],x=0,y=1,main(1,0),printf("%d",z):(x=X(_)-x,y=Y(_)-y,x+=10*(x<0),y+=4*(y<0),z=(x>5?10-x:x)+(y>2?4-y:y)));}

```
> 3 votes

---
Tags: code-golf
---


title: Bowl Filled with Water

text:
# Question
Title: Bowl Filled with Water
You should write a program or function which receives the volume of a bowl and the volume of the water in it as input and outputs or returns an ASCII representation of a bowl with water in it with the desired volumes.

A bowl has the following structure:

```
 \     /
  \___/

```

The bowl has at least one `_` character. The count of `\`'s and `/`'s are also positive and they are equal due to symmetry.

The volume of the bowl is the total number of `_` and `space` characters between the `\`'s and `/`'s plus one for every pair of `\` and `/`. This means the above bowl has the volume of `10`:

```
 \     /  =>  xxxxx x (the last one is for the \/ pair)
  \___/        xxx x (the last one is for the \/ pair)

```

Note that two different bowl could have the same volume. E.g. both the following bowls have a volume of 18:

```
\       /
 \     /      \         /
  \___/        \_______/

```

We can pour some water into the bowl. The water is represented as a row of `~` characters instead of spaces inside the bowl. The bottom row has no spaces so it can not contain the `~`'s. This means our example can be filled with water in only one way:

```
 \~~~~~/
  \___/

```

Other bowls could be filled in multiple ways:

```
 \~~~~~/   \     /
  \   /     \~~~/
   \_/       \_/

```

The volume of the water in a bowl is the volume of the bowl rows **below** the `~` characters. The above examples have water volumes of `4, 6 and 2` respectively.

## Input

* Two positive integers, the volume of the bowl and the volume of the water.
* You can choose the order of the two numbers.
* The two integer can be inputted in any common list format (list, tuple, array, etc.) or as two separate integers.
* At least one valid bowl-water configuration is guaranteed for the input values.

## Output

* The ASCII representation of a bowl with water where the bowl and water volumes match the input.
* If you choose to return the result instead of printing, it should be returned as single string (or your language's closest alternative).
* Any trailing whitespace is allowed.
* No unnecessary leading whitespace is allowed.
* If there are multiple correct configurations you are free to choose which one you output but you can only output one of them.

## Examples

Each input integer pair is followed by its one or more possible outputs.

```
6 2
\~~~/
 \_/

10 4
\~~~~~/
 \___/

24 8
\        /
 \~~~~~~/
  \    /
   \__/

42 12 //either of the two output is correct
\           /
 \         /
  \~~~~~~~/
   \     /
    \   /
     \_/

\               /
 \~~~~~~~~~~~~~/
  \___________/

90 68
\~~~~~~~~~~~~~~~~~~~~~/
 \                   /
  \                 /
   \               /
    \_____________/

102 42
\                     /
 \                   /
  \~~~~~~~~~~~~~~~~~/
   \               /
    \             /
     \___________/

```

This is code golf so the shortest entry wins.

# Answer
> 6 votes
# CJam, ~~72~~ ~~70~~ 69 bytes

```
q~:QW=3m*{:,2ff*),)ff+}%{::)1fbQ=}=~W%ee_,S*W'_t@,~'~t.{S\+.*"\/".+N}

```

Try it online in the CJam interpreter.

Run time and memory usage are **O(scary)**, so the last three test cases should be verified using the Java interpreter (and extra heap space).

### Example run

```
$ time java -Xmx4G -jar cjam-0.6.5.jar bowl.cjam <<< '[42 102]'
\                     /
 \                   /
  \~~~~~~~~~~~~~~~~~/
   \               /
    \             /
     \___________/

real    0m40.669s
user    3m13.100s
sys     0m11.690s

```

### How it works

```
q~:Q     e# Read from STIDN, evaluate and save the result in Q.
W=       e# Select the last element of Q (bowl volume B).
3m*      e# Push all vectors of {0,...,B-1} × {0,...,B-1} x {0,...,B-1}.

{        e# For each vector [X Y Z]:
  :,     e#   Push [[0 1 ... X-1] [0 1 ... Y-1] [0 1 ... Z-1]].
  2ff*   e#   Multiply each coordinate by 2.
  ),)    e#   Pop the last vector, compute its length and increment.
  ff+    e#   Add the result to each component of each vector.
}%       e# Result: [[Z Z+2 ... Z+2(X-1)] [Z Z+2 ... Z+2(Y-1)]]

{        e# Find:
  ::)    e#   Increment each coordinate (to account for the volume in "\/").
  1fb    e#   Sum the coordinate of both vectors.
  Q=     e#   Compare the result to Q (desired volumes).
}=       e# If they match, push the array and break.

~        e# Dump both vectors on the stack.
W%       e# Reverse the rightmost one (corresponds to the bowl volume).
ee       e# Enumerate its coordinates.
         e# [Z+2(Y-1) ... Z+2 Z] -> [[0 Z+2(Y-1)] ... [Y-2 Z+2] [Y-1 Z]].
_,S*     e# Compute the length (Y) and push a string of Y spaces.
W'_t     e# Replace the last space with an underscore.
@        e# Rotate the leftmost vector (corresponds to the water volume) on top.
,        e# Compute its length (X).
~'~t     e# Replace the space at index X from the right with a tilde.

.{       e# For each enumerates coordinate and the corresponding character:
  S\+    e#   Append the character to the string " ".
  .*     e#   Vectorized repetition: [1 2] " ~" -> [" " "~~"]
  "\/".+ e#   Append the first (second) solidus to the first (second) string.
  N      e#   Push a linefeed.
}

```

# Answer
> 2 votes
# C, 231 229 bytes

Early submission :) There's lots more golfing to do here.

```
v,V,w,h,H,i,j;main(c,a)char**a;{V=atoi(a[1]);v=atoi(a[2]);for(;++H;)for(h=0;h++<H;){for(w=1;h*h+w*h-h<v;++w);if(H*H+w*H-H==V){for(;H--;){printf("%*s",++i,"\\");for(j=0;j++<w-1+2*H;)putchar(H?H==h?'~':32:95);puts("/");}exit(0);}}}

```

Ungolfed:

```
int v,V,w,h,H,i,j;
int main(int c, char **a)
{
    V=atoi(a[1]); /* Volume of bowl */
    v=atoi(a[2]); /* Volume of water */

    for(;++H;) /* Make the bowl taller */
    {
        for(h=0;h++<H;) /* Make the water taller */
        {
            for(w=1;h*h+w*h-h<v;++w); /* Make the bowl wider until the water volume matches */
            if(H*H+w*H-H==V) /* if the bowl volume matches, then we're good */
            {
                for(;H--;) /* Print out the bowl, one line at a time */
                {
                    printf("%*s",++i,"\\"); /* Print the left edge */
                    /* Print the inside (either with air/water, the top of the water, or the bottom of the bowl */
                    for(j=0;j++<w-1+2*H;)
                        putchar(H?H==h?'~':32:95);
                    /* Print the right edge of the bowl */
                    puts("/");
                }
                exit(0); /* die, we're done */
            }
        }
    }
}

```

# Answer
> 2 votes
# Javascript ES5, 364 bytes

This is what i could come up with quickly during my lunch, help me golf it out while my shift ends!

## Source

```
function V(x,v) { // calculate volume of bowl/water
    for(i=v,j=x;i--;j+=2) {
      v+=j;
    }
    return v
}
function B(x,y,l) { // draw bowl/water
    for(s="",h=y,w = x+2*y;y--;s+="\n")
        for(i=w;i--;) {
            f= i>h-y-1 && w-i > h-y;
            s+=i==h-y-1?"/":
                w-i == h-y? "\\":
                y==l-1 && f? "~" :
                !y && f?"_":" "
        }
    return s;
}
n=prompt().split(" ");
b=+n[0]; // bowl volume
w=+n[1]; // water volume
for(x=b;x;x--)  // loop through possible widths
  for(y=b;y;y--)  // loop through possible heights
    if(V(x,y)==b) // check if we found bowl volume
       for(y2=y;y2;y2--) { // check possible water heights
         v = V(x,y2-1);
         if(v==w){ // see if volume matches
          alert(B(x,y,y2));
          x=1;break;
         }
       }

```

## Golfed:

*(ran through minifier to compress, lunch shift ended)*

```
function V(f,r){for(i=r,j=f;i--;j+=2)r+=j;return r}function B(r,y,n){for(s="",h=y,w=r+2*y;y--;s+="\n")for(i=w;i--;)f=i>h-y-1&&w-i>h-y,s+=i==h-y-1?"/":w-i==h-y?"\\":y==n-1&&f?"~":!y&&f?"_":" ";return s}for(n=prompt().split(" "),b=+n[0],w=+n[1],x=b;x;x--)for(y=b;y;y--)if(V(x,y)==b)for(y2=y;y2;y2--)if(v=V(x,y2-1),v==w){alert(B(x,y,y2)),x=1;break}

```

# Answer
> 2 votes
# Perl, ~~227~~ 172 bytes

Run with -n option:

```
/ /;for$h(1..$`){for$w(1..$`){for$l(1..($h*($w+$h)==$`)*$h){if($l*($w+$l)==$'){for(0..$h-1){print$"x$_."\\".($_<$h-1?$_==$h-$l-1?"~":$":"_")x($w+($h-$_-1)*2)."/
"}exit}}}}

```

Thanks to Dennis for help golfing this down.

Calculates bowl volume as height * (width + height), where width is the number of `_` characters and height is the number of `\` characters.

Each combination of height and width is tested in a pair of nested loops until the correct bowl volume is found, then another loop over possible water height levels is done to find if a the correct water volume is possible with that width.

It is possible to remove the third loop by just calculating the water level using the quadratic formula with a as 1, b as the width and c as the negative of the desired water volume, and checking if it's an integer, but that takes more bytes than just doing a loop. Here it is anyway (183 bytes):

```
/ /;for$h(1..$`){for$w(1..$`){if($h*($w+$h)==$`){$l=(sqrt($w*$w+4*$')-$w)/2;if(int$l==$l){for(0..$h-1){print$"x$_."\\".($_<$h-1?$_==$h-$l-1?"~":$":"_")x($w+($h-$_-1)*2)."/
"}exit}}}}

```

# Answer
> 2 votes
# Python 2, 162 bytes

```
V,W=input()
r=1
while r*r<V:a=V/r-r;k=1;exec"if(a+k)*k==W*(V%r<1):i=1;exec\"print' '*~-i+'\%s/'%(' _~'[(i==r)-(i==r-k)]*(a+2*(r-i)));i+=1;\"*r;r=V\nk+=1\n"*r;r+=1

```

A little messy, but here's my first attempt. It tries all possible numbers of rows `r`, setting the number of base underscores to be `a = V/r-r`. Then it tries all possible water level heights `k` and checks if the bowl is valid, printing it if so.

# Answer
> 1 votes
## Python 2.7, ~~284~~ ~~270~~ 260 Bytes

```
def f(b,w,i=1,e='while s<%s:j+=2;s+=j'):
 while 1:
    i+=1;j=s=i;exec e%w
    if s==w:p=j;exec e%b
    if s==b:break
 h=(j-i)/2+1;t=w=i+(h-1)*2+1
 for j in range(h):r,s,t=((' '*(t-2),'_'*(i-1))[j==h-1],'~'*(t-2))[j==h-(p-i)/2-2],(w-t)/2,t-2;print" "*s+"\\"+r+"/"+" "*s

```

This basically calculates the height and width of the bucket and water and prints them.

Tried hard to remove the ugly while loop part at the start(wherein I calculate the height of the bucket and the height from where water should be drawn. Right now, all lines in the code except for the last one are for calculating the width and height). Still trying :P
Testing it for different cases -

```
>>> execfile("buckets.py")
(6, 2)
\~~~/
 \_/

(10, 4)
\~~~~~/
 \___/

(24, 8)
\        /
 \~~~~~~/
  \    /
   \__/

(42, 12)
\           /
 \         /
  \~~~~~~~/
   \     /
    \   /
     \_/

(90, 68)
\~~~~~~~~~~~~~~~~~~~~~/
 \                   /
  \                 /
   \               /
    \_____________/

(102, 42)
\                     /
 \                   /
  \~~~~~~~~~~~~~~~~~/
   \               /
    \             /
     \___________/

```

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


title: Pair Capacitors

text:
# Question
Title: Pair Capacitors
Capacitors are notorious for being manufactured with high tolerances. This is acceptable in many cases, but some times a capacity with tight tolerances is required. A common strategy to get a capacity with the exact value you need is to use two carefully measured capacitors in parallel such that their capacities add up to something in the range you need.

The goal in this challenge is, given a (multi) set of capacities, to pair the capacitors such that the total capacity of each pair is in a given range. You also need to find the best set of pairings, that is, the set of pairings such that as many pairs as possible are found.

## Constraints

1. Input comprises in a format of choice
    * an unordered list of capacities representing the (multi) set of *capacitors you have*
    * a pair of capacities representing the lower and upper bound of the *target range* (inclusive)
2. all capacities in the input are positive integers smaller than 230, the unit is pF (not that that matters).
3. In addition to the list of capacities in the input, the set of *capacitors you have* also contains an infinite amount of capacitors with a value of 0 pF.
4. Output comprises in a format of choice a list of pairs of capacities such that the sum of each pair is in the *target range* specified. Neither the order of pairs nor the order of capacities within a pair is specified.
5. No capacity in the output may appear more often than it appears in the set of *capacitors you have*. In other words: The pairs you output must not overlap.
6. There shall be no possible output satisfying conditions 4 and 5 that contains more pairs of capacities than the output your program produces.
7. Your program shall terminate in O(*n*!) time where *n* is the length of the list representing the set of *capacitors you have*
8. Loopholes shall not be abused
9. The *target range* shall not be empty

## Scoring

Your score is the length of your solution in octets. If your solution manages to solve this problem in polynomial time O(*n**k*) for some *k*, divide your score by 10. I do not know if this is actually possible.

## Sample input

* range 100 to 100, input array `100 100 100`, valid output:

```
0 100
0 100
0 100

```
* range 100 to 120, input array `20 80 100`, valid output:

```
0 100
20 80

```

the output `20 100` is not valid
* range 90 to 100, input array `50 20 40 90 80 30 60 70 40`, valid output:

```
0 90
20 80
30 70
40 60
40 50

```
* range 90 to 90, input array `20 30 40 40 50 60 70 80 90`, valid output:

```
0 90
20 70
30 60
40 50

```
* range 90 to 110, input array `40 60 50`, valid output:

```
40 60

```

# Answer
# CJam, 5.6

This is a direct re-implementation of the algorithm in orlp's answer. If you upvote my answer, please make sure that you also upvote this answer. I also suggest that the answer with the original algorithm is accepted, because I very much doubt that I would have figured out how to solve this elegantly in O(n\*log(n)).

```
l~_,0a*+${(\)@_2$+4$~2$\>{;;\;\+}{<{;+}{oSop}?}?_,1>}g;;

```

Try it online

Sample input:

```
[90 100] [50 20 40 90 80 30 60 70 40]

```

Explanation:

```
l~      Get and interpret input.
_,      Get length of resistor list.
0a*+    Append the same number of 0 values.
$       Sort the list.
{       Loop until less than 2 entries in list.
  (       Pop off first value.
  \)      Pop off last value.
  @_      Pull first value to top, and copy it.
  2$      Copy last value to top.
  +       Add first and last value.
  4$~     Copy specified range to top, and unwrap the two values.
  2$      Copy sum to top.
  \>      Swap and compare for sum to be higher than top of range.
  {       It's higher.
    ;;\;    Some stack cleanup.
    \+      Put first value back to start of resistor list.
  }
  {       Not higher, so two cases left: value is in range, or lower.
    <       Compare if sum is lower than bottom of range.
    {       It's lower.
      ;+      Clean up stack and put last value back to end of resistor list.
    }
    {       Inside range, time to produce some output.
      o       Output first value.
      So      Output space.
      p       Output second value and newline.
    }?      Ternary operator for comparison with lower limit.
  }?      Ternary operator for comparison with upper limit.
  _,      Get length of remaining resistor list.
  1>      Check if greater 1.
}g      End of while loop for processing resistor list.
;;      Clean up stack, output was generated on the fly.

```
> 1 votes

# Answer
# Python 2, 11.5

A Python golf for once:

```
(a,b),l=input()
l=[0]*len(l)+sorted(l)
while l:
 e=l[0]+l[-1]
 if a<=e<=b:print l[0],l[-1]
 l=l[e<=b:len(l)-(a<=e)]

```

I add one 0 pF capacitor for every regular one, there are never any more needed. Then we sort the capacitors and keep pairing the lowest and highest capacitor. If the sum is within the allowable range we print it, if it is above the range we discard the highest, if it's below discard the lowest.

Example input / output:

```
[[90,100], [20,30,40,40,50,60,70,80,90]]

0 90
20 80
30 70
40 60
40 50

```
> 6 votes

---
Tags: code-golf, set-partitions, restricted-complexity
---


title: A fiercer four-square cipher

text:
# Question
Title: A fiercer four-square cipher
### Background

One-hundred and thirteen years ago, amateur cryptographer Félix Delastelle published his work on the four-square cipher, a digraphic substitution cipher that accepts two permutations of a 25-letter alphabet as keys and encodes messages consisting of those letters.

Like most pen-and-paper ciphers, the four-square cipher does not have any cryptographic value today, but at the time of its invention, it had a significant advantage over its monographic counterparts.

One-hundred and thirteen years later, Alice Delastelle decides to improve the four-square cipher by increasing the alphabet's size and the number of keys.<sup>\[citation needed\]</sup>

### Key setup

The alphabet contains the following characters (starting with space):

```
 !"#$%&'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ

```

Given a pass phrase, we construct a permutation of this alphabet as follows:

1. Keep only the first occurrence of each character.
2. Append the unused characters from the alphabet, in their natural order.

After turning four pass phrases into four keys, we split each key into a square of side length 7 and arrange the four resulting squares so that they form one big square.

For example, if the pass phrases were

```
PROGRAMMING PUZZLES & CODE GOLF
POPULARITY CONTESTS & CODE BOWLING
CORRECT HORSE BATTERY STAPLE
DON'T TELL EVE!!!

```

the keys would be constructed and arranged like this:

```
PROGAMI  POULARI
N UZLES  TY CNES
&CDF!"#  &DBWG!"
$%'()*+  #$%'()*
,-./:;<  +,-./:;
=>?@BHJ  <=>?@FH
KQTVWXY  JKMQVXZ

CORET H  DON'T E
SBAYPL!  LV!"#$%
"#$%&'(  &()*+,-
)*+,-./  ./:;<=>
:;<=>?@  ?@ABCFG
DFGIJKM  HIJKMPQ
NQUVWXZ  RSUWXYZ

```

### Encryption

Given a plaintext message such as

```
ALICE LOVES BOB.

```

we append 0 or 1 spaces to make its length even and split it into character pairs:

```
["AL" "IC" "E " "LO" "VE" "S " "BO" "B."]

```

For each character pair, we locate the the first character in the first square (reading order) and the second in the fourth.

Then, we choose the characters in the remaining squares such that the four selected characters form a rectangle whose sides are parallel to the sides of the squares.

Finally, we replace the character pair by the selected characters of the second and third square.

For our example string, this yields

```
["PP" "A@" "E " "YT" "ZE" "EH" "=T" "<-"]

```

resulting in the following ciphertext:

```
PPA@E YTZEEH=T<-

```

### Task

Write a program or function that accepts four pass phrases and a plaintext, uses the above variant of the four-square cipher to encrypt it and returns the resulting ciphertext.

Details:

* The five input strings will consist solely of characters of the mentioned alphabet.
* The five input strings can be read in any order, as such, a single string delimited by newlines or as an array of five strings.
* You may assume that none of the strings is empty.
* The output must be a single string.

If you choose to print the output to STDOUT, you may print only the characters of the ciphertext and (optionally) a trailing newline.
* Standard rules apply.

### Test cases

In all test cases, the first four strings correspond to the key squares in reading order and the last input string to the plaintext.

**Input**

```
PROGRAMMING PUZZLES & CODE GOLF
POPULARITY CONTESTS & CODE BOWLING
CORRECT HORSE BATTERY STAPLE
DON'T TELL EVE!!!
ALICE LOVES BOB.

```

**Output**

```
PPA@E YTZEEH=T<-

```

**Input**

```
 !"#$%&'()*+,-./:;<=>
 !"#$%&'()*+,-./:;<=>?@ABCDE
 !"#$%&'()*+,-./:;<=>?@ABCDEFGHIJKL
 !"#$%&'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRS
HELLO, WORLD!

```

**Output**

```
LALLR)#TROKE !

```

**Input**

```
,'K AB-Q=?@("W$>XM).C#<I:G!OLP*+;SZJTU%NED/&VFHRY
:,-D$C<SU=IYHFVA;! JG/M&L+WT%#.Q@(N*R")EZOBKX?'>P
L()JX,BND?Z<>P*FU%=O@&KIC+A!Y:;$SWHR.EMG'/T"QV #-
<->CI")AP Q:+U;O/F(KH&ER!MW?X'VJLZ#.$,BSGN@TD%*Y=
SPIN THE PPCG WHEEL OF BLAME!

```

**Output**

```
#>TE,VK+,ZQ(&<F@RA.NL@DM%NAC&>

```

**Input**

```
& %(,-#)$@?/=>'*"<:;!.+
=/$- ?;',@#!(&<")%.:>+*
&%-/<?.;$'#:=!( ,>"+*)@
=,<-*?#.'@/;>%!+:(& ")$
HNRA#JX$H %JAV+"GTS,

```

**Output**

```
GOOD LUCK, HAVE FUN.

```

# Answer
> 4 votes
# CJam, ~~52~~ ~~50~~ ~~49~~ ~~47~~ ~~46~~ 44 bytes

```
l2/qN/'[,32>A,s-f|2/f{~@S+2<.#_7f%_W%.m.m.=}

```

The input order is lines `5, 2, 3, 1, 4`. Try it online.

*(-1 byte thanks to @MartinBüttner, -2 bytes thanks to @Dennis)*

## Explanation

```
l2/           Read the message and split into chunks of 2
qN/           Read rest of input and split by newlines (pass phrases)
'[,32>        Generate " !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ"
A,s-          Remove digits 0123456789
f|            Setwise OR with each pass phrase to remove duplicates, giving keys
2/            Split keys into two pairs
f{ ... }      For each message chunk...
  ~             Unwrap key pairs
  @S+2<         Add a space to the message chunk then cap to length 2
  .#            Find the two chars in keys 1, 4
  _7f%          Copy indices and perform modulo 7 on both
  _W%           Copy and reverse
  .m.m          Vectorised subtraction twice
  .=            Apply both indices to keys 2, 3

```

For the indices, we want to swap the least significant digits, base 7. For instance, for the first example `AL` are indices `4` and `7` in keys 1 and 4 respectively. In base 7, this is `[0 4]` and `[1 0]`. Swapping the least significant digits gives `[0 0]` and `[1 4]`, i.e. `0` and `11`, and this corresponds to `P` and `P` in keys 2 and 3 respectively.

However, instead of base converting, the code does the following:

```
[4 7]     A: Initial indices
[4 0]     B: Indices mod 7
[0 4]     C: Reverse of B

[4 -4]    B-C
[0 11]    A-(B-C)

```

# Answer
> 6 votes
# Pyth, 74 71 bytes

```
L+%eb7*7/hb7Jcms+oxdN{d--CMr33 91`MTd.z2ssm@VeJ,ydy_dCmxLhdedC,hJ.tcz2d

```

Could probably be optimized a lot. I use a **lot** of zipping.

Takes input in the following order:

```
ALICE LOVES BOB.
PROGRAMMING PUZZLES & CODE GOLF
DON'T TELL EVE!!!
POPULARITY CONTESTS & CODE BOWLING
CORRECT HORSE BATTERY STAPLE

```

# Answer
> 4 votes
# Pyth - 88 86 83 ~~78~~ ~~76~~ ~~75~~ 72 bytes

*8 bytes saved thanks to @orlp*.

Waaay too long, I'm pretty unhappy with this, but just posting it while I look for a better way to handle the squares.

```
Jm+oxdN{d-+d-CMr33 91`MTd.zsms@VtPJ,+*7hKs.DR7xV,hJeJdeK+*7@K2@K1C.tcz2d

```

Try it online here.

---
Tags: code-golf, cryptography
---


title: 64 bit ASCII weaving

text:
# Question
Title: 64 bit ASCII weaving
### Input

Two integers:

* A non-negative integer ***W*** in the range 0 to 2^64-1, specifying the weave.
* A positive integer ***S*** in the range 1 to 255, specifying the side length.

These can be taken in whichever order suits you.

### Output

An ***S*** by ***S*** ASCII representation of the requested weave (***S*** newline separated strings of ***S*** characters with an optional trailing newline). The weave is defined by the weave number ***W*** as follows:

Convert ***W*** to binary and split into 8 bytes. The first (most significant) byte defines the top row, from left (most significant bit) to right. The next byte defines the next row, and so on for 8 rows. The weave number defines an 8 by 8 square which should be tiled over the required area starting from the top left. That is, its top left corner should correspond to the top left corner of the area to be covered.

Every `0` should be displayed as a `|` and every `1` should be displayed as a `-`

### Examples

Input: `0 8`

Ouput:

```
||||||||
||||||||
||||||||
||||||||
||||||||
||||||||
||||||||
||||||||

```

---

Input: `3703872701923249305 8`

Output:

```
||--||--
|--||--|
--||--||
-||--||-
||--||--
|--||--|
--||--||
-||--||-

```

---

Input: `3732582711467756595 10`

Output:

```
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--

```

---

Input: `16141147355100479488 3`

Output:

```
---
|||
---

```

---

# Leaderboard Snippet

*(using Martin's template)*

```
var QUESTION_ID=54123;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
```

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

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

# Answer
# K, 20

```
{y#y#'"|-"8 8#0b\:x}

```

.

```
             0b\:x    // convert to binary
         8 8#         // reshape into an 8x8 boolean matrix
     "|-"             // index into this char vector using the booleans as indices
  y#'                 // extend horizontally
y#                    // extend vertically

```

.

```
k){y#y#'"|-"8 8#0b\:x}[3703872701923249305j;10]
"||--||--||"
"|--||--||-"
"--||--||--"
"-||--||--|"
"||--||--||"
"|--||--||-"
"--||--||--"
"-||--||--|"
"||--||--||"
"|--||--||-"

k){y#y#'"|-"8 8#0b\:x}[3703872701923249305j;8]
"||--||--"
"|--||--|"
"--||--||"
"-||--||-"
"||--||--"
"|--||--|"
"--||--||"
"-||--||-"

```
> 10 votes

# Answer
# CJam, ~~33~~ 31 bytes

```
q~:X;2b64Te["|-"f=8/{X*X<z}2*N*

```

Test it here.

## Explanation

```
q~      e# Read and eval input.
:X;     e# Store the side length in X and discard it.
2b      e# Convert to base 2.
64Te[   e# Left-pad to length 64 with zeroes.
"|-"f=  e# Select '|' for 0 and '=' for 1.
8/      e# Split into chunks of 8 bits.
{       e# Do the following twice:
  X*    e#   Repeat lines X times (to ensure we have enough of them).
  X<    e#   Truncate them to exactly X lines.
  z     e#   Transpose the grid.
        e#   The transpose ensures that the second pass tiles the columns, and that the
        e#   grid is oriented correctly again after both passes are done.
}2*
N*      e# Join lines by newline characters.

```
> 13 votes

# Answer
# Java, ~~110~~ ~~109~~ 107 Bytes

My code is in the form of an anonymous lambda function that takes a `long` and an `int` then returns a `String`.

```
(w,s)->{String b="";for(int j,i=s--;i-->0;b+='\n')for(j=s;j>=0;)b+=(w>>8*(i%8)+j--%8)%2<1?'|':45;return b;}

```

Complete testable class

```
import java.util.function.BiFunction;
public class AsciiWeave {
    public static void main(String[] args){
        BiFunction<Long,Integer,String> weave =
            (w,s)->{String b="";for(int j,i=s--;i-->0;b+='\n')for(j=s;j>=0;)b+=(w>>8*(i%8)+j--%8)%2<1?'|':45;return b;}}
        ;
        System.out.println(weave.apply(Long.valueOf(args[0]),Integer.valueOf(args[1])));
    }
}

```
> 5 votes

# Answer
# Matlab, ~~86~~ 80 bytes

```
function f(W,S)
a='|-';x=de2bi(typecast(W,'uint8'))+1;s=8-mod(0:S-1,8);a(x(s,s))

```

Thanks to Hoki for his suggestion, which led me to save me 6 bytes.

Example:

```
>> W = uint64(3732582711467756595)
W =
  3732582711467756595
>> S = uint8(10)
S =
   10
>> f(W,S)
ans =
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--

```
> 4 votes

# Answer
# J, 28 bytes

```
'|-'{~]$"1]$8 8$_64{.#.inv@[

```

Usage:

```
   3732582711467756595 ('|-'{~]$"1]$8 8$_64{.#.inv@[) 10
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--

```

Explanation (right to left):

```
#.inv@[   binary representation vector of S
_64{.     padded with 0-s from the right to length 64
8 8$      reshaped in an 8 by 8 matrix
]$"1]$    tiled to a W by W size
'|-'{~    select | or - based on matrix element values

```

Try it online here.
> 3 votes

# Answer
# Julia, 145 bytes

```
f(w,s)=(A=map(i->i=="1"?"-":"|",reshape(split(lpad(bin(w),64,0),""),8,8))';for i=1:s A=hcat(A,A)end;for i=1:s println(join(A[i>8?i%8:i,1:s]))end)

```

This creates a function that accepts two integers and prints to stdout.

Ungolfed + explanation:

```
function f(w,s)
    # Convert w to binary, left-padded with zeros to length 64
    b = lpad(bin(w), 64, 0)

    # Create an 8x8 array of | and -
    A = transpose(map(i -> i == "1" ? "-" : "|", reshape(split(b, ""), 8, 8)))

    # Horizontally concatenate A to itself s times
    for i = 1:s
        A = hcat(A, A)
    end

    # Print the rows of A, recycling as necessary
    for i = 1:s
        println(join(A[i > 8 ? i % 8 : i, 1:s]))
    end
end

```

This is pretty long and I'm sure it can be made much shorter. Working on it.
> 3 votes

# Answer
# CJam, ~~30~~ ~~28~~ 27 bytes

```
q~_2m*W%/ff{8f%8bm>"|-"=}N*

```

Try it online in the CJam interpreter.
> 3 votes

# Answer
## Python, 77

```
lambda w,s:''.join('|-'[w>>~n/s%8*8+~n%s%8&1]+'\n'[~n%s:]for n in range(s*s))

```

For each of the `s*s` values of `n`:

* Compute the coordinates via divmod `(i,j)=(n/s,n%s)`
* Compute the location in the tiling as `(i%8,j%8)`
* Compute the appropriate bit position as `8*(i%8)+(j%8)`
* Extract that bit of `w` by shifting `w` that many spaces with right and take the last bit with `&1`.
* Join one of '|-' at that position
* Add the newline at the end of every row whenever `n%s==0`

Actually, all that ends up getting the tiling backwards, since it reads `w` from the end. We fix this by using `~n` in place of `n`. I tried a recursive approach instead, but it turned out slightly longer.

The expression `w>>~n/s%8*8+~n%s%8&1` is a miracle of operator precedence.
> 2 votes

# Answer
# C, 160 135 bytes

```
i;main(s,v)char**v;{s=atoi(v[2]);for(;i++<s*s+s;)putchar(i%(s+1)?strtoull(v[1],0,10)&1ull<<63-(i/(s+1)*8+(i%(s+1)-1)%8)%64?45:'|':10);}

```

Some more golfing can be done here and need an explanation, but I don't have time at the moment :)

## Ungolfed:

```
i;

main(s,v)
char**v;
{
    s=atoi(v[2]);
    for(;i++<s*s+s;)
        putchar(i%(s+1) ? /* print dash or pipe, unless at end of row, then print newline */
            /* Calculating which bit to check based on the position is the tough part */
            strtoull(v[1],0,10) & 1ull << 63-(i/(s+1)*8+(i%(s+1)-1)%8)%64 ? /* If bit at correct index is set, print dash, otherwise pipe */
                45 /* dash */
                : '|' /* pipe */
            : 10); /* newline */
}

```
> 1 votes

# Answer
# Python 2, 132 Bytes

Certainly not the most elegant solution, and it's barely shorter than C, but it's a start.. Input is taken comma-separated.

```
k,n=input()
k=[`['|-'[int(x)]for x in'{0:064b}'.format(k)]`[2::5][i*8:i*8+8]*n for i in range(8)]*n
for j in range(n):print k[j][:n]

```
> 1 votes

# Answer
# Pyth, ~~31~~ 30 bytes

```
L<*QbQjbyyMcs@L"|-".[Z64jvz2 8

```

The input should be on two lines, ***W*** then ***S***.

Try it here

## Explanation

```
L                              # define y(b):
  *Qb                          #   b, repeated Q (the second input) times
 <   Q                         #   cut to length Q

                        jvz2   # convert the first input to binary
                   .[Z64       # pad with 0's to length 64
             @L"|-"            # map the digits to the appropriate character
            s                  # convert the list of characters to a string
           c                 8 # chop into 8 strings
         yM                    # extend each string to the correct size
        y                      # extend the list of strings to the correct size
      jb                       # join with newlines

```
> 1 votes

---
Tags: code-golf, ascii-art, base-conversion, tiling
---


title: A Kingdom Hearts VGM challenge

text:
# Question
Title: A Kingdom Hearts VGM challenge
I'm a *huge* video game music fan. One of my favorite OSTs is that from Kingdom Hearts, by Yoko Shimomura.

# The challenge

Create a program or function that takes two arguments in any format: an abbreviated Kingdom Hearts game and a boss in that game. It must return the name of the song that plays for that boss. The program should handle any input case, but you can decide what case the output will be. You may assume the input is always valid. Here is a list of all the valid inputs:

```
Game   Boss                       Song

1      Ansem                      Guardando nel Buio
1      Riku                       Forze de Male
1      Sephiroth                  One Winged Angel
1      Kurt Zisa                  The Deep End
1      Unknown                    Disappeared
2      Organization XIII          The 13th Struggle, Dilemma, Reflection
2      Xemnas I                   A Fight to the Death
2      Xemnas II                  Darkness of the Unknown
2      Sephiroth                  One Winged Angel
2      Lingering Sentiment        Rage Awakened
CoM    Organization XIII          The 13th Struggle
CoM    Marluxia 1                 Graceful Assasin
CoM    Marluxia 2                 Scythe of Petals
CoM    Marluxia 3                 Lord of the Castle
CoM    Riku Replica               The Force in You
CoM    Ansem                      Revenge of Chaos
BBS    Master Xehanort            Black Powder
BBS    Terra vs Master Xehanort   Rage Awakened
BBS    Vanitas                    Enter the Darkness
BBS    Ventus vs Vanitas          The Key
BBS    Vanitas Remnant            Enter the Void
BBS    Terranort                  Dismiss
BBS    Mysterious Figure          Dark Impetus
Coded  Riku                       Riku
Coded  Pete                       Rowdy Rumble
Coded  Maleficent                 Vim and Vigor
Coded  Sora's Heartless           Guardando nel Buio
Coded  Roxas                      The Other Promise
Days   Xion                       Vector to the Heavens
Days   Riku                       Another Side
DDD    Anti Black Coat Nightmare  Dread of Night
DDD    Ansem I                    L'Eminenza Oscura I
DDD    Ansem II                   L'Eminenza Oscura II
DDD    Xemnas                     L'Oscurita dell'Ignoto
DDD    Young Xehanort             L'Impeto Oscuro
DDD    Armored Ventus Nightmare   Eye of Darkness
DDD    Julius                     The Encounter

```

# Scoring

Your score is *not* your byte count. You do not need to implement the entire list, but you *must* implement at least 10 items. Your score is `byte count / # of items implemented`. For instance, say you write a 90-byte program that implements 25 items of the above table. Your score would be `90/25=3.6`. Lowest score wins.

# Bonus

* -1 off your score of you implement an additional item, from Final Fantasy:

```
Game    Boss        Song

XV      Behemoth    Omnis Lacrima

```

**AND** make it so that any other requested bosses from `XV` return `TBD`.
* -0.5 if your code also takes in the games `1.5` and `2.5`, which take the same bosses as `1` and `2` but return the song name followed by `(Orchestrated)`.
* Another -0.5 if your program accepts bosses from `CoM` and `Days` when given `1.5` and accepts bosses from `Coded` and `BBS` when given `2.5`. It must return the songs followed by `(Orchestrated)`.

If you know of any other significant bosses I left out, let me know in the comments.

Also, I'm hoping I'm not the only person here who has *memorized* all of these songs...

# Answer
> 5 votes
# Ruby ~~134~~ 131/10=13.1

```
->g,b{"Rowdy Rumble|Dread of Night|Riku|One Winged Angel|Rage Awakened|Vim and Vigor|The Key|The 13th Struggle".split(?|)[b.ord%8]}

```

This is a lambda function, which takes arguments for the game and the boss. The argument for the game is actually ignored by the code, but the OP has clarified that the argument cannot be eliminated.

In fact it only uses the first letter of the boss's name. the ASCII code is taken modulo 8 (this gives the same answer for a given letter, regardless of case) and one of 8 song titles is returned. As two song titles appear twice, this covers a total of 10 elements:

```
Game   Boss                      Array  Song
                                 index
Coded  Pete                         0   Rowdy Rumble
DDD    Anti Black Coat Nightmare    1   Dread of Night
Coded  Riku                         2   Riku
1      Sephiroth                    3   One Winged Angel
2      Sephiroth                    3   One Winged Angel
2      Lingering Sentiment          4   Rage Awakened
BBS    Terra vs Master Xehanort     4   Rage Awakened
Coded  Maleficent                   5   Vim and Vigor
BBS    Ventus vs Vanitas            6   The Key
CoM    Organization XIII            7   The 13th Struggle

```

It was a lucky coincidence that the Ascii codes for L and T give the same result modulo 8, so both incidences of Rage Awakened could be covered.

Call the function as in this test program:

```
f=->g,b{"Rowdy Rumble|Dread of Night|Riku|One Winged Angel|Rage Awakened|Vim and Vigor|The Key|The 13th Struggle".split(?|)[b.ord%8]}
B=gets                  #get boss name from stdin
puts f.call("dummy",B)  #call function, and output return value to stdout

```

# Answer
> 2 votes
# Pyth, 144/10 = 14.4

```
@c"|L'Impeto Oscuro|Riku|Eye of Darkness|Disappeared||Another Side|Forze de Male|Dread of Night|Rowdy Rumble|One Winged Angel"\|%.hrzZ11

```

Incredibly simple hash table, with the 'coincidence' of re-using the song 'One Winged Angel' twice. The above program recognizes the following items correctly:

```
ddd young xehanort            | L'Impeto Oscuro
coded riku                    | Riku
ddd armored ventus nightmare  | Eye of Darkness
1 mysterious figure           | Disappeared
days riku                     | Another Side
1 riku                        | Forze de Male
ddd anti black coat nightmare | Dread of Night
coded pete                    | Rowdy Rumble
1 sephiroth                   | One Winged Angel
2 sephiroth                   | One Winged Angel

```

---
Tags: code-challenge, kolmogorov-complexity
---


title: Code close to the challenge: Inception

text:
# Question
Title: Code close to the challenge: Inception
This is a sequel to this challenge: Code close to the challenge: Sum of integers

The challenge in this one is a bit harder, and also makes for a cool title (Which is why I picked it):

> Calculate the Levenshtein distance between two strings

Just like last challenge, your score in this challenge is the Levenshtein distance between your code and the quote above.

So now for the details!

Your program will take 2 inputs, both strings with no trailing spaces or newlines, and will output the Levenshtein distance between them. Levenshtien distance is defined as the number of of additions, deletions, and substitutions necessary to transform one string to another. For more information on how to calculate it, see the Wikipedia page linked above. To test if your program works, use this calculator. Your program must output nothing but the Levenshtein distance between the two strings. It will be disqualified if anything else is outputted. **Example I/O:**

```
Inputs:
test
test2
Output:
1

Inputs:
222
515
Output:
3

Inputs:
Test
test
Output:
1

```

**Your code may not have no-ops or comments.**

# Answer
# Frink, distance 24

```
Calculate[the,Levenshtein]:=editDistance[the,Levenshtein]

```

To use this, you would call Calculate with the two strings, and since this is returning, you also need to surround the call with `print[]`. If this isn't allowed, my score is 30.

Example:

```
Calculate["kitten","spork"]        -> returns 6
print[Calculate["kitten","spork"]] -> prints 6.

```

You need to download Frink, as the web interpreter doesn't allow defining functions. It should run on all systems, considering it's a Java applet. Download instructions here..

---

Psst. Hey! Here's a Levenshtein implementation in Symbolic, something I'm working on: `k=λ:Δ(ί,ί)`.
> 9 votes

# Answer
# R, distance 35

```
Calculate=function(the,Levenshtein)adist(between<-the,two<-Levenshtein)

```

This creates a function `Calculate` with parameters `the` and `Levenshtein`. It uses the R built-in function `adist` to compute the distance. The string parameters in `adist` are essentially `the` and `Levenshtein` renamed to `between` and `two`.
> 6 votes

# Answer
# PHP4.1, distance ~~32~~ ~~22~~ ~~15~~ 14

Very basic one, nothing exciting.

```
<?=$Calculate_the=Levenshtein($distance,$between_two_strings);

```

Or a shorter version:

```
<?=$ulatethe=Levenshtein($istance,$etweentwostrin);

```

For this to work, you need to send/set a POST/GET/COOKIE/session variable with the keys:

* `distance` (`istance` for the shorter one)
* `between_two_strings` (`etweentwostrin` for the shorter one)

The arguments are in that order.

Test the score on http://ideone.com/QzNZ8T

Example:

```
http://localhost/distance.php?distance=string1&between_two_strings=string2

```
> 5 votes

# Answer
# PHP, distance 44

```
function Calculate($two,$strings){echo levenshtein($two,$strings);}

```

Use the built-in `levenshtein` function from PHP standard library and named the arguments in order to try to minimize the distance.
> 2 votes

# Answer
# Pip, distance 50

Uses no builtin Levenshtein function!

```
xINg?#JgMN[1+(fac:b@>1)1+(fe:a@>1b)(a@0NEb@0)+(fec)]

```

This code implements the recursive Levenshtein algorithm; as such, it is extremely slow, taking a few seconds even for strings of length 5. I wouldn't recommend running the program through itself to check it!

Here's my base code, with whitespace and comments:

```
; Note: a Pip program is an implicit function f, which is called with the command-line
; arguments. The args are stored in the list g, as well as being assigned to the local
; variables a-e.

; Is one of the args the empty string? (NB x is initialized to "")
x IN g ?
 ; If so, join args together and take the length (i.e., length of the non-empty string).
 # J g
 ; If not, take the min of the following:
 MN [
  ; Recursively call f with the first character of a removed; add 1 to the result
  (f a@>1 b) + 1
  ; Recursively call f with the first character of b removed; add 1 to the result
  (f a b@>1) + 1
  ; Recursively call f with the first characters of both removed; iff the two characters
  ; were not equal, add 1 to the result
  (f a@>1 b@>1) + (a@0 NE b@0)
 ]

```

The main change in the final version is assigning some values to temporary variables `c` and `e`, which appear in the challenge string and thus reduce the Levenshtein distance a bit.
> 2 votes

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