# Question
Title: Find all the Solutions to this Number Puzzle in the Shortest Time Possible
# History

My company sends out a weekly newsletter to everyone within the company. Included in these newsletters is a riddle, along with a shoutout to whomever in the company was the first to email/provide a solution to last week's riddle. Most of these riddles are quite trivial, and honestly pretty dull for a tech company, but there was one, several months back, that caught my attention.

## The Original Riddle:

Given the shape below:

You have the Natural Numbers from 1 to 16. Fit them all into this shape, such that all the contiguous rows and contiguous columns sum up to 29.

For example, one such solution to this puzzle (which was the "canonical" solution I submitted to the newsletter) was the following:

However, in the course of solving it, I found some rather interesting information:

* There are significantly more solutions than just that one; in fact, there are 9,368 Solutions.
* If you expand the ruleset to only require that rows and columns be equal to each other, not necessarily 29, you get 33,608 solutions:
    + 4,440 Solutions for a sum of 27.
    + 7,400 Solutions for a sum of 28.
    + 9,368 Solutions for a sum of 29.
    + 6,096 Solutions for a sum of 30.
    + 5,104 Solutions for a sum of 31.
    + 1,200 Solutions for a sum of 32.

So me and my coworkers (though mostly just my manager, since he was the only other person than me with "General Purpose" programming skills) set out on a challenge, that lasted for most of the month—we had other, actual job-related obligations we had to attend to—to try to write a program which would find every single solution in the fastest way possible.

## Original Statistics

The very first program I wrote to solve the problem simply checked random solutions over and over, and stopped when it found a solution. If you've done Mathematical analysis on this problem, you probably already know that this shouldn't have worked; but somehow I got lucky, and it took the program only a minute to find a single solution (the one I posted above). Repeat runs of the program often took as much as 10 or 20 minutes, so obviously this wasn't a rigorous solution to the problem.

I switched over to a Recursive Solution which iterated through every possible permutation of the puzzle, and discarded lots of solutions at once by eliminating sums that weren't adding up. I.E. if the first row/column I was comparing already weren't equal, I could stop checking that branch immediately, knowing that nothing else permuted into the puzzle would change that.

Using this algorithm, I got the first "proper" success: the program could generate and spit out all 33,608 solutions in about 5 minutes.

My manager had a different approach: knowing based on my work that the only possible solutions had sums of 27, 28, 29, 30, 31, or 32, he wrote a multi-threaded solution which checked possible sums only for those specific values. He managed to get his program to run in only 2 minutes. So I iterated again; I hashed all possible 3/4 digit sums (at the start of the program; it's counted in the total runtime) and used the "partial sum" of a row to look-up the remaining value based on a previously completed row, rather than testing all remaining values, and brought the time down to 72 seconds. Then with some multi-threading logic, I got it down to 40 seconds. My manager took the program home, performed some optimizations on how the program ran, and got his down to 12 seconds. I reordered the evaluation of the rows and columns, and got mine down to 8 seconds.

The fastest either of us got our programs after a month was 0.15 seconds for my manager, and 0.33 seconds for me. I ended up claiming that my program was faster though, since my manager's program, while it did *find* all solutions, wasn't printing them out into a text file. If he added that logic to his code, it often took upwards of 0.4-0.5 seconds.

We've since allowed our intra-personal challenge to subsist, but of course, the question remains: *can* this program be made faster?

That's the challenge I'm going to pose to you guys.

# Your Challenge

The parameters we worked under relaxed the "sum of 29" rule to instead be "all rows/columns' sums equal", and I'm going to set that rule for you guys too. The Challenge, therefore, is: Write a program that finds (and Prints!) all solutions to this riddle in the shortest time possible. I'm going to set a ceiling on submitted solutions: If the program takes more than 10 seconds on a relatively decent computer (\<8 years old), it's probably too slow to be counted.

Also, I have a few Bonuses for the puzzle:

* Can you generalize the solution so that it works for any set of 16 numbers, not just `int[1,16]`? Timing score would be evaluated based on the original prompt number set, but passed through this codepath. (-10%)
* Can you write the code in a way that it gracefully handles and solves with duplicate numbers? This isn't as straightforward as it might seem! Solutions which are "visually identical" should be unique in the result set. (-5%)
* Can you handle negative numbers? (-5%)

You can also *try* to generate a solution that handles Floating-Point Numbers, but of course, don't be shocked if that fails utterly. If you do find a robust solution though, that might be worth a large bonus!

For all intents and purposes, "Rotations" are considered to be unique solutions. So a solution that is just a rotation of a different solution counts as its own solution.

The IDEs I have working on my computer are Java and C++. I can accept answers from other languages, but you may need to also provide a link to where I can get an easy-to-setup runtime environment for your code.

# Answer
> 7 votes
# C - near 0.5 sec

This very naive program give all the solutions in half a second on my 4 years old laptop. No multithread, no hashing.

Windows 10, Visual Studio 2010, CPU core I7 64 bit

Try online on ideone

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

int inuse[16];
int results[16+15+14];

FILE *fout;

int check(int number)
{
    if (number > 0 && number < 17 && !inuse[number-1])
    {
        return inuse[number-1]=1;
    }
    return 0;
}

void free(int number)
{
    inuse[number-1]=0;
}

void out(int t, int* p)
{
    int i;
    fprintf(fout, "\n%d",t);
    for(i=0; i< 16; i++) fprintf(fout, " %d",*p++);
}

void scan()
{
    int p[16];
    int t,i;
    for (p[0]=0; p[0]++<16;) if (check(p[0]))
    {
        for (p[1]=0; p[1]++<16;) if (check(p[1]))
        {
            for (p[2]=0; p[2]++<16;) if (check(p[2]))
            {
                t = p[0]+p[1]+p[2]; // top horiz: 0,1,2
                for (p[7]=0; p[7]++<16;) if (check(p[7]))
                {
                    if (check(p[11] = t-p[7]-p[2])) // right vert: 2,7,11
                    {
                        for(p[9]=0; p[9]++<16;) if (check(p[9]))
                        {
                            for (p[10]=0; p[10]++<16;) if (check(p[10]))
                            {
                                if (check(p[12] = t-p[9]-p[10]-p[11])) // right horiz: 9,10,11,12
                                {
                                    for(p[6]=0; p[6]++<16;) if (check(p[6]))
                                    {
                                        if (check(p[15] = t-p[0]-p[6]-p[9])) // middle vert: 0,6,9,15
                                        {
                                            for(p[13]=0; p[13]++<16;) if (check(p[13]))
                                            {
                                                if (check(p[14] = t-p[13]-p[15])) // bottom horiz:  13,14,15
                                                {
                                                    for(p[4]=0; p[4]++<16;) if (check(p[4]))
                                                    {
                                                        if (check(p[8] = t-p[4]-p[13])) // left vert: 4,8,13
                                                        {
                                                            for(p[3]=0; p[3]++<16;) if (check(p[3]))
                                                            {
                                                                if (check(p[5] = t-p[3]-p[4]-p[6])) // left horiz: 3,4,5,6
                                                                {
                                                                    ++results[t];
                                                                    out(t,p);
                                                                    free(p[5]);
                                                                }
                                                                free(p[3]);
                                                            }
                                                            free(p[8]);
                                                        }
                                                        free(p[4]);
                                                    }
                                                    free(p[14]);
                                                }
                                                free(p[13]);
                                            }
                                            free(p[15]);
                                        }
                                        free(p[6]);
                                    }
                                    free(p[12]);
                                }
                                free(p[10]);
                            }
                            free(p[9]);
                        }
                        free(p[11]);
                    }
                    free(p[7]);
                }
                free(p[2]);
            }
            free(p[1]);
        }
        free(p[0]);
    }
    for(i=0;i<15+16+14;i++)
    {
        if(results[i]) printf("%d %d\n", i, results[i]);
    }
}

void main()
{
    clock_t begin, end;
    double time_spent;
    begin = clock();

    fout = fopen("c:\\temp\\puzzle29.txt", "w");
    scan();
    fclose(fout);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("Time %g sec\n", time_spent);
}

```

# Answer
> 3 votes
# C++ - 300 Milliseconds

Per request, I've added my own code to solve this puzzle. On my computer, it clocks in at an average of 0.310 seconds (310 milliseconds) but depending on variance can run as quickly as 287 milliseconds. I very rarely see it rise above 350 milliseconds, usually only if my system is bogged down with a different task.

These times are based on the self-reporting used in the program, but I also tested using an external timer and get similar results. Overhead in the program seems to add about 10 milliseconds.

Also, my code doesn't *quite* handle duplicates correctly. It can solve using them, but it doesn't eliminate "visually identical" solutions from the solution set.

```
#include<iostream>
#include<vector>
#include<random>
#include<functional>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<thread>
#include<chrono>
#include<fstream>
#include<iomanip>
#include<string>
#include<mutex>
#include<queue>
#include<sstream>
#include<utility>
#include<atomic>
#include<algorithm>

//#define REDUCE_MEMORY_USE

typedef std::pair<int, std::vector<std::pair<int, int>>> sumlist;
typedef std::unordered_map<int, std::vector<std::pair<int, int>>> summap;
typedef std::array<int, 16> solution_space;

class static_solution_state {
public:
    std::array<int, 16> validNumbers;
    summap twosums;
    size_t padding;
    std::string spacing;

    static_solution_state(const std::array<int, 16> & _valid);

    summap gettwovaluesums();
    std::vector<sumlist> gettwovaluesumsvector();
};

static_solution_state::static_solution_state(const std::array<int, 16> & _valid)
    : validNumbers(_valid) {
    twosums = gettwovaluesums();
    padding = 0;
    for (int i = 0; i < 16; i++) {
        size_t count = std::to_string(validNumbers[i]).size();
        if (padding <= count) padding = count + 1;
    }
    spacing.resize(padding, ' ');
}

class solution_state {
private:
    const static_solution_state * static_state;
public:
    std::array<int, 16> currentSolution;
    std::array<bool, 16> used;
    std::array<int, 7> sums;
    size_t solutions_found;
    size_t permutations_found;
    size_t level;
    std::ostream * log;

    solution_state(const static_solution_state & _sstate);
    solution_state(static_solution_state & _sstate) = delete;
    void setLog(std::ostream & out);
    const int & operator[](size_t index) const;

};

solution_state::solution_state(const static_solution_state & _sstate) {
    static_state = &_sstate;
    sums = { 0 };
    used = { false };
    currentSolution = { -1 };
    solutions_found = 0;
    permutations_found = 0;
    level = 0;
}

void solution_state::setLog(std::ostream & out) {
    log = &out;
}

const int & solution_state::operator[](size_t index) const {
    return static_state->validNumbers[currentSolution[index]];
}

int getincompletetwosum(const static_solution_state & static_state, const solution_state & state);
void permute(const static_solution_state & static_state, solution_state & state, volatile bool & reportProgress, const volatile size_t & total_tests, volatile bool & done);
void setupOutput(std::fstream & out);
void printSolution(const static_solution_state & static_state, const solution_state & state);
constexpr size_t factorial(const size_t iter);

const bool findnext2digits[16]{
    false, false, false,
    true, false,
    false, true, false,
    true, false,
    true, false,
    true, false,
    true, false
};

const int currentsum[16]{
    0, 0, 0,
    1, 1,
    2, 2, 2,
    3, 3,
    4, 4,
    5, 5,
    6, 6
};

const int twosumindexes[7][2]{
    { 0, -1},
    { 2, -1},
    { 5, -1},
    { 5, -1},
    { 0,  7},
    { 11, 4},
    { 10, 9}
};

const std::array<size_t, 17> facttable = [] {
    std::array<size_t, 17> table;
    for (int i = 0; i < 17; i++) table[i] = factorial(i);
    return table;
}();

const int adj = 1;

std::thread::id t1id;

int main(int argc, char** argv) {
    //std::ios_base::sync_with_stdio(false);
    std::array<int, 16> values = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
    if (argc == 17) {
        for (int i = 0; i < 16; i++) {
            values[i] = atoi(argv[i + 1]);
        }
    }
    auto start = std::chrono::high_resolution_clock::now();
    const static_solution_state static_state(values);
#if defined(REDUCE_MEMORY_USE)
    const int num_of_threads = max(1u, min(thread::hardware_concurrency(), 16u));
#else
    const int num_of_threads = 16;
#endif
    std::vector<solution_state> states(num_of_threads, static_state);
    for (int i = 0; i < num_of_threads; i++) {
        int start = i * 16 / num_of_threads;
        states[i].permutations_found += start * factorial(16) / 16;
    }
    std::fstream out;
    setupOutput(out);
    std::locale loc("");
    std::cout.imbue(loc);
    volatile bool report = false;
    volatile bool done = false;
    volatile size_t tests = 0;

    std::thread progress([&]() {
        auto now = std::chrono::steady_clock::now();
        while (!done) {
            if (std::chrono::steady_clock::now() - now > std::chrono::seconds(1)) {
                now += std::chrono::seconds(1);

                size_t t_tests = 0;
                for (int i = 0; i < num_of_threads; i++) t_tests += states[i].permutations_found - i * factorial(16) / num_of_threads;
                tests = t_tests;
                report = true;
            }
            std::this_thread::yield();
        }
    });

    if (num_of_threads <= 1) {

        states[0].setLog(out);
        permute(static_state, states[0], report, tests, done);

    }
    else {
        std::vector<std::thread> threads;
#if defined(REDUCE_MEMORY_USE)
        std::vector<std::fstream> logs(num_of_threads);
#else
        std::vector<std::stringstream> logs(num_of_threads);
#endif
        for (int i = 0; i < num_of_threads; i++) {
            threads.emplace_back([&, i]() {
                if (i == 0) t1id = std::this_thread::get_id();
                int start = i * 16 / num_of_threads;
                int end = (i + 1) * 16 / num_of_threads;
#if defined(REDUCE_MEMORY_USE)
                logs[i].open("T"s + to_string(i) + "log.tmp", ios::out);
#endif
                logs[i].imbue(loc);
                states[i].setLog(logs[i]);

                for (int j = start; j < end; j++) {

                    states[i].currentSolution = { j };
                    states[i].level = 1;
                    states[i].used[j] = true;
                    permute(static_state, states[i], report, tests, done);

                }
            });
        }

        std::string buffer;
        for (int i = 0; i < num_of_threads; i++) {
            threads[i].join();
#if defined(REDUCE_MEMORY_USE)
            logs[i].close();
            logs[i].open("T"s + to_string(i) + "log.tmp", ios::in);
            logs[i].seekg(0, ios::end);
            auto length = logs[i].tellg();
            logs[i].seekg(0, ios::beg);
            buffer.resize(length);
            logs[i].read(&buffer[0], length);
            logs[i].close();
            remove(("T"s + to_string(i) + "log.tmp").c_str());
            out << buffer;
#else
            out << logs[i].str();
#endif
        }
    }
    done = true;
    out.close();

    if (num_of_threads > 1) {
        size_t t_tests = 0;
        for (int i = 0; i < num_of_threads; i++) t_tests += states[i].permutations_found - i * factorial(16) / num_of_threads;
        tests = t_tests;
    }

    size_t solutions = 0;
    for (const auto & state : states) {
        solutions += state.solutions_found;
    }

    auto end = std::chrono::high_resolution_clock::now();

    progress.join();

    auto duration = end - start;
    auto secondsDuration = std::chrono::duration_cast<std::chrono::milliseconds>(duration);
    std::cout << "Total time to process all " << tests << " results: " << std::setprecision(3) << std::setiosflags(std::ostream::fixed) << (secondsDuration.count()/1000.0) << "s" << "\n";
    std::cout << "Solutions found: " << solutions << std::endl;
    //system("pause");
    return 0;
}

void permute(const static_solution_state & static_state, solution_state & state, volatile bool & reportProgress, const volatile size_t & total_tests, volatile bool & done) {
    if (done) return;
    if (state.level >= 16) {
        if (reportProgress) {
            reportProgress = false;
            std::cout << "Current Status:" << "\n";
            std::cout << "Test " << total_tests << "\n";
            std::cout << "Contents: {";
            for (int i = 0; i < 15; i++) std::cout << std::setw(static_state.padding - 1) << state[i] << ",";
            std::cout << std::setw(static_state.padding - 1) << state[15] << "}" << "(Partial Sum: " << state.sums[0] << ")" << "\n";
            std::cout << "=====================" << "\n";
        }
        printSolution(static_state,state);
        state.solutions_found++;
        state.permutations_found++;
    }
    else {
        if (state.level == 3) state.sums[0] = state[0] + state[1] + state[2];

        if (!findnext2digits[state.level]) {
            for (int i = 0; i < 16; i++) {
                if (!state.used[i]) {
                    state.currentSolution[state.level] = i;
                    state.used[i] = true;
                    state.level++;
                    permute(static_state, state, reportProgress, total_tests, done);
                    state.level--;
                    state.used[i] = false;
                }
            }
        }
        else {
            int incompletetwosum = getincompletetwosum(static_state, state);
            if (static_state.twosums.find(incompletetwosum) == static_state.twosums.end()) {
                state.permutations_found += facttable[16 - state.level];
            }
            else {
                size_t successes = 0;
                const std::vector<std::pair<int, int>> & potentialpairs = static_state.twosums.at(incompletetwosum);
                for (const std::pair<int, int> & values : potentialpairs) {
                    if (!state.used[values.first] && !state.used[values.second]) {
                        state.currentSolution[state.level] = values.first;
                        state.currentSolution[state.level + 1] = values.second;
                        state.used[values.first] = true;
                        state.used[values.second] = true;
                        state.level += 2;
                        permute(static_state, state, reportProgress, total_tests, done);
                        state.level -= 2;
                        state.used[values.first] = false;
                        state.used[values.second] = false;

                        successes++;
                    }
                }
                state.permutations_found += facttable[16 - state.level - 2] * ((16 - state.level) * (15 - state.level) - successes);
            }
        }
    }
}

int getincompletetwosum(const static_solution_state & static_state, const solution_state & state) {
    int retvalue = state.sums[0];
    int thissum = currentsum[state.level];
    for (int i = 0; i < 2 && twosumindexes[thissum][i] >= 0; i++) {
        retvalue -= state[twosumindexes[thissum][i]];
    }
    return retvalue;
}

constexpr size_t factorial(size_t iter) {
    return (iter <= 0) ? 1 : iter * factorial(iter - 1);
}

void setupOutput(std::fstream & out) {
    out.open("puzzle.txt", std::ios::out | std::ios::trunc);
    std::locale loc("");
    out.imbue(loc);
}

void printSolution(const static_solution_state & static_state, const solution_state & state) {
    std::ostream & out = *state.log;
    out << "Test " << state.permutations_found << "\n";
    static const auto format = [](std::ostream & out, const static_solution_state & static_state, const solution_state & state, const std::vector<int> & inputs) {
        for (const int & index : inputs) {
            if (index < 0 || index >= 16) out << static_state.spacing;
            else out
                << std::setw(static_state.padding)
                << state[index];
        }
        out << "\n";
    };
    format(out, static_state, state, { -1, -1, -1,  0,  1,  2 });
    format(out, static_state, state, { 15,  9, 14, 10, -1,  3 });
    format(out, static_state, state, { -1,  8, -1, 11, 12,  4, 13 });
    format(out, static_state, state, { -1,  5,  6,  7});

    out << "Partial Sum: " << (state.sums[0]) << "\n";
    out << "=============================" << "\n";
}

summap static_solution_state::gettwovaluesums() {
    summap sums;
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) {
            if (i == j) continue;
            std::pair<int,int> values( i, j );
            int sum = validNumbers[values.first] + validNumbers[values.second];
            sums[sum].push_back(values);
        }
    }
    return sums;
}

std::vector<sumlist> static_solution_state::gettwovaluesumsvector() {
    std::vector<sumlist> sums;
    for (auto & key : twosums) {
        sums.push_back(key);
    }

    std::sort(sums.begin(), sums.end(), [](sumlist a, sumlist b) {
        return a.first < b.first;
    });
    return sums;
}

```

# Answer
> 1 votes
# Prolog - 3 minutes

This kind of puzzle seems like a perfect use-case for Prolog. So, I coded up a solution in Prolog! Here it is:

```
:- use_module(library(clpfd)).

puzzle(P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15) :-
    Vars = [P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15],
    Vars ins 1..16,
    all_different(Vars),
    29 #= P0 + P1 + P2,
    29 #= P3 + P4 + P5 + P6,
    29 #= P9 + P10 + P11 + P12,
    29 #= P13 + P14 + P15,
    29 #= P0 + P6 + P9 + P15,
    29 #= P2 + P7 + P11,
    29 #= P4 + P8 + P13.

```

Unfortunately, it's not as fast as I expected. Maybe someone more well-versed in declarative programming (or Prolog specifically) can offer some optimization tips. You can invoke the rule `puzzle` with the following command:

```
time(aggregate_all(count, (puzzle(P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15), labeling([leftmost, up, enum], [P9, P15, P13, P0, P4, P2, P6, P11, P1, P5, P3, P7, P14, P12, P10, P8])), Count)).

```

Try it out online here. You can substitute any number in place of the `29`s in the code to generate all solutions. As it stands, all 29-solutions are found in approximately 30 seconds, so to find all possible solutions should be approximately 3 minutes.

---
Tags: number, fastest-code
---


title: Draw a ladder and slide

text:
# Question
Title: Draw a ladder and slide
Your task is to create a program or function that takes, as input, a natural number (`n`) between 1 and 25 (inclusive) and prints an isometric representation of a slide and ladder with `n` number of rungs.

### Ladder and slide specifications

The ladder is always oriented on the left and the slide on the right. We're viewing it from the ladder side, so part of the slide is obscured at the top three levels. The rungs are represented by four dashes (`----`) and the sides of the ladder and slide by slashes (`/` and `\`). The following is a diagram to represent the patterns of spaces needed for a slide with five rungs.

```
Slide              Blank space count
    /----/\        1234/----/\
   /----/  \       123/----/12\
  /----/    \      12/----/1234\
 /----/ \    \     1/----/1\1234\
/----/   \    \    /----/123\1234\

```

### Examples

```
>>1
/----/\

>>3
  /----/\
 /----/  \
/----/    \

>>4
   /----/\
  /----/  \
 /----/    \
/----/ \    \

>>10
         /----/\
        /----/  \
       /----/    \
      /----/ \    \
     /----/   \    \
    /----/     \    \
   /----/       \    \
  /----/         \    \
 /----/           \    \
/----/             \    \

```

This is code-golf, so the answer with the lowest byte count wins.

Note: trailing white space is acceptable in the output, as long as it doesn't exceed the length of the line.

# Answer
> 17 votes
## Retina, ~~81~~ ~~72~~ 52 bytes

Byte count assumes ISO 8859-1 encoding.

```
.+
$* /\    \
^.

+` /(.+)$
$&¶$%`/  $1
/.{5}
/----/

```

Try it online!

### Explanation

The program consists of four stages, all of which are regex substitutions (with a couple of Retina-specific features). I'll use input `5` as an example for the explanation.

**Stage 1**

```
.+
$* /\    \

```

This turns the input `n` into `n` spaces followed by `/\ \` which will become the top of the ladder/slide:

```
     /\    \

```

For now, we'll just show the slide in full and represent the ladder only by its left-hand `/`.

**Stage 2**

```
^.

```

Unfortunately, `n` spaces are one more than we need, so we remove the first character again. We've now got:

```
    /\    \

```

**Stage 3**

```
+` /(.+)$
$&¶$%`/  $1

```

Time to expand the complete structure. Knowing *where* the top is, is sufficient to build the entire thing, because we can simply extend it one line at a time, moving the ladder and the slide apart by two spaces.

The `+` tells Retina to repeat this stage in a loop until the output stops changing (in this case, because the regex stops matching). As for the regex itself, we simply match the `/` on the last line and everything after it and we also match one space in front of it, which means this can no longer match once `/` has reached the first column.

Here's what we replace this with:

```
 $&    The match itself. We don't want to remove the line we already have.
 ¶     A linefeed, because we want to append a new line.
 $%`   This is a very recent addition to Retina: it's like the normal $` but
      is bounded by linefeeds. That means this inserts everything in front
      of the match which is on the same line. In particular this one space
      less than the indentation of the matched line, hence we are shifting
      the / one column left.
 /     A literal /, representing the left edge of the ladder.
>  <   Two spaces, so that we can shift the slide one column right.
 $1    Capturing group 1 which contains the slide and its separation from
      the ladder.

```

So at each iteration, this adds one line to the string, until we end up with this:

```
    /\    \
   /  \    \
  /    \    \
 /      \    \
/        \    \

```

**Stage 4**

```
/.{5}
/----/

```

All that's left is getting the ladder right. That's really simple, we just match the `/` and the next 5 characters and insert the correct ladder representation, thereby overriding the slide or spaces that are already there:

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

```

# Answer
> 9 votes
# , ~~38, 37, 36, 34, 33, 32, 31, 30~~ 29 bytes

```
Àé r\2é/4é-òhYpX$2P^ò3GEòjlr\

```

Try it online!

~~I *might* catch up with Osabie. One byte shorter than Osabie. `\o/` Tied with 2sable!~~ One byte shorter!

In other news, this is definitely the longest strikethrough header I've ever made.

Explanation:

```
Àé              "Insert 'arg1' spaces
   r\           "Turn the last one into a '\'
     2é/        "Insert 2 '/'
        4é-     "Insert 4 '-'

ò        ò      "Recursivly:
 h              "  Move one to the left
  Yp            "  Duplicate this line
    X           "  Delete one space from the left
     $2P        "  Paste two spaces at the end of this line
        ^       "  Move back to the beginning of this line.

```

This will run until an error occurs, which thanks to the "move left" command ('h'), will be 'arg1' times.

Now we just need to add the inner leg

```
3GE             "Move to the second slash of line 3
   ò    ò       "Recursively: (The second 'ò' is implicit)
    jl          "  Move down and to the right
      r\        "  And replace the character under the cursor with a '\'

```

Non-competing version (28 bytes)

# Answer
> 8 votes
# 2sable, ~~40~~ ~~36~~ ~~32~~ 30 bytes

Hmmm, V is coming awfully close...

```
F¹N-<ð×…/--Â«ðð«N×…\  Â««5F¦}¶

```

Uses the **CP-1252** encoding. Try a 05AB1E compatible version!.

# Answer
> 8 votes
## Pyth, ~~39~~ 35 bytes

```
VQ++*dt-QN"/----/">+*+ddN"\    \\"5

```

Explanation:

```
VQ                                  # Interate over 0 -> Q-1 (Q is the input)
  +                                 # Concatenate the 2 halfs of the slide
   +                                # Concatenate the whitespace block and the ladder
    *d                              # Multiply d (whitespace) by this number \/
      t-QN                          # Calculate the amount of spaces before : input - step of the iterarion -1
          "/----/"                  # Ladder
                  >               5 # Remove the first 5 chars  from the string generated in the following lines
                   +                # Concatenate the whitespace block and the slide
                    *+ddN           # Multiply "+dd" (2 whitespace) by the step of the iterarion to generate the space between the ladder and the slide
                         "\    \\"  # Slide

```

Test here

# Answer
> 7 votes
## PowerShell v2+, ~~99~~ ~~90~~ 82 bytes

```
param($n)1..$n|%{" "*($n-$_)+"/----/"+-join(" "*($_+$i++)+"\    \")[6..(6+$_+$i)]}

```

Takes input `$n`, starts a loop from `1` to `$n` with `|%{...}`. Each iteration, we're constructing a string. We start with the appropriate number of spaces `" "*($n-$_)` and the ladder `"/----/"`.

To that, we add another string that's been sliced `[...]` and `-join`ed back together. The second string is the slide, and we assume that the whole slide is always visible. It's the number of spaces before the slide would start `" "*($_+$i++)`, followed by the slide itself `"\ \"`. This is sliced by a range calculated out to be the part of the "spaces plus slide" that's partially hidden by the ladder.

### Examples

```
PS C:\Tools\Scripts\golfing> .\draw-a-ladder-and-slide.ps1 7
      /----/\
     /----/  \
    /----/    \
   /----/ \    \
  /----/   \    \
 /----/     \    \
/----/       \    \

PS C:\Tools\Scripts\golfing> .\draw-a-ladder-and-slide.ps1 15
              /----/\
             /----/  \
            /----/    \
           /----/ \    \
          /----/   \    \
         /----/     \    \
        /----/       \    \
       /----/         \    \
      /----/           \    \
     /----/             \    \
    /----/               \    \
   /----/                 \    \
  /----/                   \    \
 /----/                     \    \
/----/                       \    \

```

# Answer
> 6 votes
# Python 2 - ~~79~~ ~~76~~ 75 bytes

```
x=input()
for i in range(x):print(x-i)*' '+'/----/'+(i*'  '+'\\    \\')[5:]

```

Thanks to Hubert Grzeskowiak for "disqualifying" me since making my program print actually saved 3 bytes! Thanks also to Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ for saving 1 more byte!

# Answer
> 6 votes
# bash, 61

```
for((;i<$1;)){ printf "%$[$1+i]s\    \^M%$[$1-++i]s/----/\n";}

```

where `^M` is a literal carriage return

```
$ ./ladder 1
/----/\
$ ./ladder 4
   /----/\
  /----/  \
 /----/    \
/----/ \    \
$ ./ladder 10
         /----/\
        /----/  \
       /----/    \
      /----/ \    \
     /----/   \    \
    /----/     \    \
   /----/       \    \
  /----/         \    \
 /----/           \    \
/----/             \    \

```

# Answer
> 6 votes
# Vim, 71 keystrokes

This is such a stupid way of doing it, but it's a bit of fun. Input is given as a text file with a single line containing an integer. This is likely quite golfable, but it'll do for now (*edit: switched style of control characters upon request*):

```
A@qyyPgg<c-v><c-v>GkI <c-v><esc>G$i  <c-v><esc><esc>
Tq"qDI/----/\^[lD@"ddh<c-v>god:%s/     \\/\\    \\<cr>

```

`<c-v>`, `<esc>` and `<cr>` are all individual keystrokes; ctrl+v, escape, and carriage return (enter) respectively. For a simple to digest version with the correct literals, here is the file `ladder.keys` run though `xxd`:

```
00000000: 4140 7179 7950 6767 1616 476b 4920 161b  A@qyyPgg..GkI ..
00000010: 4724 6920 2016 1b1b 5471 2271 4449 2f2d  G$i  ...Tq"qDI/-
00000020: 2d2d 2d2f 5c1b 6c44 4022 6464 6816 676f  ---/\.lD@"ddh.go
00000030: 643a 2573 2f20 2020 2020 5c5c 2f5c 5c20  d:%s/     \\/\\
00000040: 2020 205c 5c0d 0d0a                         \\...

```

To try it out (assuming a nix with the appropriate tools) take the above, run it through `xxd -r` and put in the file `ladder.keys`. Create a file `ladder.txt` with an integer in it. Then do:

```
vim -s ladder.keys -u NONE ladder.txt

```

# Answer
> 5 votes
## JavaScript (ES6), 79 bytes

```
f=
n=>" ".repeat(n).replace(/./g,"$'/$`$`\\    \\\n").replace(/\/...../g,"/----/")
;
```

```
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>
```

Works by taking a string of `n` spaces, then doing some exotic substitution to get the slide with a support, then replacing the support with a ladder.

# Answer
> 4 votes
# Ruby, 61 bytes

```
->n{n.times{|i|puts"%*s\\    \\\r%*s----/"% [n+i,"",n-i,?/]}}

```

### Ungolfed

```
->(num_rows) {
  num_rows.times {|row_idx|
    puts "%*s\\    \\\r%*s----/" % [ num_rows + row_idx, "", num_rows - row_idx, "/" ]
  }
}

```

I could save two bytes by using `'%*s\ \^M%*s----/'` (where `^M` is a literal carriage return) for the format string, but then Ruby prints the warning "`warning: encountered \r in middle of line, treated as a mere space`". ¯\\\_(ツ)\_/¯

### Previous solution (64 bytes)

```
->n{n.times{|i|puts" "*(n+i)+"\\    \\\r"+" "*(n-i-1)+"/----/"}}

```

# Answer
> 3 votes
## Batch, 194 bytes

```
@echo off
for /l %%i in (1,1,%1)do call:l %1 %%i
exit/b
:l
set s=\    \
for /l %%j in (1,1,%2)do call set s=  %%s%%
set s=/----/%s:~7%
for /l %%j in (%2,1,%1)do call set s= %%s%%
echo%s%

```

Turned out to be reasonably straightforward: indent the slide, remove the first 7 characters, indent the ladder, remove the leading space. This last bit does involve a little trickery though!

# Answer
> 2 votes
# Java, 116 bytes

```
c->{for(int i=0;i<c;i++)System.out.format("%"+(5+c-i)+"s%"+(i<3?i*2+1:2*(i-2))+"s%5s\n","/----/","\\",i<3?"":"\\");};

```

Unfortunately, you can't \[easily\] duplicate strings in Java, so I end up abusing the format function.

# Answer
> 2 votes
**Scala, 95 bytes**

```
def l(n:Int)=for(i<- 0 to n-1){println(" "*(n-i-1)+"/----/"+("  "*i+"\\    \\").substring(5))}

```

# Answer
> 2 votes
## Haskell, 81 bytes

```
a n=[1..n]>>" "
f n=[1..n]>>=(\i->a(n-i)++"/----/"++drop 7(a(2*i)++"\\    \\\n"))

```

# Answer
> 0 votes
# eacal, noncompeting, 386 bytes

```
init .
define @ curry push .
define ~ curry exec .--func
alias $ strap
alias ' string
set n set m cast number arg number 0
set s empty string
label l
@ get n
set n ~ dec
@ space
@ get n
$ ~ repeat
$ ' /----/
@ space
@ get m
@ get n
@ ~ sub
@ ~ dec
@ number 2
@ ~ mul
$ ~ repeat
$ ' \
$ newline
@ get n
@ number 0
if ~ more
goto l
@ $
@ regex gm '   ( {4})(?=.$)
@ '  \$1
print ~ replace

```

~~I have officially made the most verbose language possible.~~ I made the comment in jest and in sarcasm. Please calm down. Instructions on how to run in the github repo linked in the header.

## Ungolfed

```
init .
set n set m cast number arg number 0
set s empty string
label loop
    push . get n
    set n exec .--func dec
    push . space
    push . get n
    strap exec .--func repeat
    strap string /----/
    push . space
    push . get m
    push . get n
    push . exec .--func sub
    push . exec .--func dec
    push . number 2
    push . exec .--func mul
    strap exec .--func repeat
    strap string \
    strap newline
    push . get n
    push . number 0
    if exec .--func more
        goto loop

push . strap
push . regex gm string   ( {4})(?=.$)
push . string  \$1
print exec .--func replace

```

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


# Question
Title: Semi-decide Post's Correspondence Problem
The Post's Correspondence Problem (PCP) gives you a list of pairs of strings, P\_1 ... P\_n. Your task is to find a k, and some sequence of k indices such that fst(P\_i1) ... fst(P\_ik) = snd(P\_i1) ... snd(P\_ik)

We're trying to find some sequence of the pairs where the word we build from the first part is equal to the word on the second part. A solution can use any of the pairs any number of times, and in any order.

For example, if our pairs are `(0,110)`, `(11,1)` and `(001,100)` , then one solution is the world `11001110`, with the solution sequence of `2321`:

```
11 001 11 0
1  100 1  110

```

Some will have no solution, such as `(001, 01)`, `(0001, 01)`.

## Input:

An arbitrary number of words, separated by spaces. Each word is of the format `seq1,seq2` where each `seq1` and `seq2` are strings consisting only of 0 or 1, of arbitrary length.

### Example: the above examples would have the following formats:

```
0,110 11,1 001,110

001,01 0001,01

```

## Output:

If there is some sequence of the pairs which solves the PCP, output the word of the solution, followed by a space, followed by the sequence. The pairs are numbered starting at 1.

If there is no such sequence, run forever. (The problem is undecidable, so this will have to do).

### Example output

```
11001110 2321

# second example never halts

```

## Hint:

This is Turing Complete, so you're going to have to use some sort of infinite search.

# Answer
# Python 3, ~~223~~ ~~216~~ ~~199~~ ~~192~~ ~~191~~ ~~189~~ 183 bytes

*Thanks to @KarlKastor for pointing out that I could use `count`*

```
from itertools import*
j=''.join
def f(x):
 for l in count(1):
  for i in product(x,repeat=l):
   *b,=zip(*i);c=j(b[0])
   if c==j(b[1]):print(c,j(str(x.index(k)+1)for k in i));return

```

A function that takes input of a tuple of pairs of strings `x` in the form `((seq1,seq2),(seq1,seq2)...)` and prints the output to STDOUT in the same format as the test cases.

To continuously output solutions rather than just one solution, remove the `return` statement.

**How it works**

The function generates all `l`-length arrangements of the string pairs using `product`, with `l` being initialised at `1`. This list is then unpacked and transposed using `zip`; this leaves a two-element list, where the first element contains all the first strings in the pairs, and the second all the second strings in the pairs. Each element is concatenated to a string using `join`; if these are the same, we have a hit and the string is printed to STDOUT. The sequence of pair indices is then generated by looking up each pair in the original arrangement using `index`; these indices are concatenated to a string, and also printed to STDOUT. If no solution exists for that `l`, `l` is incremented and the process repeated.

Try it on Ideone
> 2 votes

# Answer
# Python 2, ~~220~~ ~~215~~ ~~203~~ ~~199~~ ~~195~~ ~~193~~ 187 bytes

```
from itertools import*
def f(p,o="".join):
 h=lambda s:o(x[s]for x in j)
 for i in count(1):
  for j in product(p,repeat=i):
   if h(0)==h(1):print h(0),o(`p.index(k)+1`for k in j);return

```

### example use:

```
>>> f([("0","110"),("11","1"),("001","100")])
('11110', '221')

```
> 2 votes

# Answer
# Pyth - ~~55~~ 43 bytes

```
Msm@c@cz\ tvd\,H`G;.VZI>Z0B#=Z?qgb0gb1bZB;Z

```

Old version:

```
DgGH=TkV`G=+T@c@czdtvN\,H)RT;JZ.VZI>J0B#=J?qgb0gb1bJB;J

```

Explanation:

```
M                           #define a function g(G,H)
 s                          #join and return the following
  m             `G;         #for each char d in str(G):
     @cz\ tvd               #split input on " " and get the element at index int(d)-1
   @c        \,H            #split that on "," and get the element at index H
-----------------------------------------------------------------------------------

.VZ                  ;      #for b from 0 to infinity
        #             B     #try
         =Z?       bZ       #set var Z (which defaults to 0) to b if
            qgb0gb1         #g(b,0) is equal to g(b,1)
   I>Z0B                    #if Z>0, break
                       Z    #print Z

```

This program iterates from 0 to infinity. Each value is split digit by digit and that sequence is checked to see if it is valid. There is a try block so any sequences that go out of range are ignored, but considering how many sequences contain indexes that go out of bounds, this algorithm is painfully inefficient. But since when is code golf about efficiency?
> 1 votes

# Answer
# Haskell, ~~260~~ ~~253~~ ~~243~~ 230 Bytes

```
import Data.List
c=concat
x=concatMap
l p=x(\n->sequence$replicate n[0..length p -1])[1..]
i p=map(unzip.(map(p!!)))$l p
f p=x(show.(+1))(a l)++" "++(c$fst$a i)
 where a e=e p!!((\(Just x)->x)$findIndex(\x->c(fst x)==c(snd x))$i p)

```

use like: `f([("0","110"),("11","1"),("001","110")])`

This could probably be A LOT shorter, but what the hell...

*-10 bytes thanks to @jmite*

*-13 by replacing fromJust with lambda*
> 1 votes

---
Tags: code-golf, string, search
---


title: Validating a CPR number

text:
# Question
Title: Validating a CPR number
# Validating a CPR number

A Danish CPR number (*Person Identification Number*) is date of birth followed by 4 digits (the last one being a control digit): DDMMYY-XXXX

The final digit validates the CPR number using Modulo 11 by satisfying the following equation:

where the  are the ten digits of the complete ID number, and the coefficients (4, 3, 2, 7, …) are all nonzero in the finite field of order 11.

# Input

A CPR number formatted like this DDMMYY-XXXX where YY indicates a year within the last 100 years (between 1917 and 2016).

# Output

Indication whether CPR number is valid (1 or true) or invalid (0 or false)

# Examples

```
  290215-2353 --> false
  140585-2981 --> true
  311217-6852 --> true
  121200-0004 --> false
  140322-5166 --> false
  111111-1118 --> true

```

# Scoring

This is - fewest bytes win!

# Date validation

All years refer to a period within the last 100 years. A valid date is a date that exists within it's calendar year.

**290215** is not a valid date because 29/2 wasn't a date in 2015.

**301216** is a valid date because 30/12 is a date in 2016.

# Answer
# Python (2), ~~167~~ ~~156~~ ~~155~~ ~~142~~ 141 bytes

```
from time import*
def f(s):
 try:return 1>sum(int(i)*(ord(j)-48)for i,j in zip("43276504321",s))%11;strptime(s[:6],"%d%m%y")
 except:return 0

```

tried to do the date validation without the library, but it's 168 bytes:

```
lambda s:sum(int(i)*(ord(j)-48)for i,j in zip("43276504321",s))%11==0 and int(s[0:2])<([0,32,(29,30)[int(s[4:6])%4==0],32]+[31,32]*2+[32,31]*2+[32]+[0]*99)[int(s[2:4])]

```

*-12 bytes thanks to @GáborFekete*

*-14 bytes thanks to @RootTwo*
> 2 votes

# Answer
# Ruby, ~~145~~ ~~113~~ ~~112~~ 103 + 8 (`-nrdate` flags) = 111 bytes

Returns a date object (truthy) if it's a valid CPR, `false` if it fails the modulo test, and `nil` (falsy) if it fails the date test. Input is STDIN.

*-33 bytes from @Jordan*

```
s=0
$_.size.times{|i|s+=12340567234/10**i%10*$_[i].to_i}
p s%11<1&&Date.strptime($_,"%d%m%y")rescue p p

```

Version that returns literal `true` on valid CPR for +1 byte:

```
s=0
$_.size.times{|i|s+=12340567234/10**i%10*$_[i].to_i}
p Date.strptime($_,"%d%m%y")&&s%11<1 rescue p p

```

Version that returns an error on invalid date instead of `nil`, for -10 bytes but probably invalid:

```
s=0
$_.size.times{|i|s+=12340567234/10**i%10*$_[i].to_i}
p Date.strptime($_,"%d%m%y")&&s%11<1

```
> 2 votes

# Answer
# Mathematica, 130 bytes

```
DateObject[a={10#5+#6+4,10#3+#4,10#+#2}][[1]]==a&&11∣Tr[{4,3,2,7,6,5,4,3,2,1}{##}]&@@IntegerDigits@FromDigits[#~StringDrop~{7}]&

```

Anonymous function. Takes a string as input and returns `True` or `False` as output. The Unicode character is U+2223 DIVIDES, representing `\[Divides]`.
> 1 votes

# Answer
# Ruby + GNU date, ~~112~~ ~~111~~ 103 bytes

-8 bytes from Kevin Lau.

```
->n{s=0
n.size.times{|i|s+=12340567234/10**i%10*n[i].to_i}
n=~/#{"(..)"*3}/
s%11<1&&`date -d#$3#$2#$1`>""}

```

Note that this prints e.g. "`date: invalid date ‘150229’`" to stderr if the date portion is invalid, but it still returns `true` or `false` (it doesn't raise an exception). If that's a disqualifier, though, I can add `⎵2>/dev/null` for a 12-byte penalty.

## Ungolfed

```
v = ->(cpr) {
  sum = 0

  cpr.size.times do |idx|
    sum += 12340567234 / 10**idx % 10 * cpr[idx].to_i
  end

  cpr =~ /#{"(..)" * 3}/
  sum % 11 < 1 && `date -d#$3#$2#$1` > ""
}

```
> 1 votes

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


title: Code Injection works in C# too!

text:
# Question
Title: Code Injection works in C# too!
Given the following C# program outputting `False`, inject a 'malicious' line of code such that the program outputs `True`.

```
class Program
{
    static void Main()
    {
        System.Console.Write("False");
        ;
    }
}

```

Your answer should consist of a string that replaces the second semicolon, and causes the program to output `True`, the whole `True` and nothing but `True` (not even a newline). It must do this if stdout is printed to the console, and if stdout is redirected to a file.

The shortest answer wins.

# Answer
> 18 votes
## 52 characters

```
}static Program(){System.Console.Write(0<1);for(;;);

```

so the whole thing becomes:

```
class Program
{
    static void Main()
    {
        System.Console.Write( "False" );
    }
    static Program()
    {
        System.Console.Write( 0 < 1 );
        for ( ; ; ) ;
    }
}

```

# Answer
> 7 votes
C#, 51 characters

```
Console.Write("\b\b\b\b\b");Console.Write("True ");

```

Will only work on standard output

# Answer
> 2 votes
You can generalize RamonBoza's answer to still work if stdout is redirected to a file.

Assuming the program runs under Mono on Linux, with the assembly `Mono.Posix.dll` loaded:

```
if(Mono.Unix.Native.Syscall.isatty(1))
{
    Console.Write("\rTrue ");
}
else
{
    // Truncate the output file first
    Console.OpenStandardOutput().SetLength(0);
    Console.Write("True");
}

```

I doubt this works on Windows, but there's probably an equivalent to `isatty()`.

# Answer
> 1 votes
**83... WIP**

I was hoping this'd work, but apparently "False" isn't being interned as I'd hoped in my compiler

```
//}unsafe static Program(){fixed(char*f="False"){*(long*)f=0x65007500720054;*(f+4)=' ';}
}unsafe static Program(){fixed(char*f="False")for(int i=5;i-->0;)*(f+i)="True "[i];

```

ungolfed

```
class Program
{
    static void Main(string[] args)
    {
        Console.Write("False");
    }

    unsafe static Program()
    {
        fixed (char* f = "False") for (int i = 5; i-- > 0; ) *(f + i) = "True "[i];
    }
}

```

# Answer
> 1 votes
```
class Program
{
    static void Main()
    {
        System.Console.Write("False");

        System.Console.Clear(); System.Console.Write("True");

        Console.ReadLine();
    }
}

```

# Answer
> 0 votes
Not sure if this is accepted.
The question doesn't say anything about compiler options so I assume I can change the entry point of the app.
55 characters ,3 more than the accepted answer

```
}class P{static void Main(){System.Console.Write(1>0);}

```

Full

```
class Program
{
    static void Main()
    {
        System.Console.Write("False");
    }
    class P
    {
        static void Main() { System.Console.Write(1 > 0); }
    }
}

```

---
Tags: code-golf, c#, programming-puzzle
---


title: Unique Sudoku Finder

text:
# Question
Title: Unique Sudoku Finder
# Challenge:

Given a Sudoku board on standard input, find the minimum number of numbers added to make the board unique.

## Specifics/Rules:

* The input is formatted as follows (all whitespace is significant)

```
516|827|943
278|394|615
349|615|872
---+---+---
98 |4 2|156
465|189|237
12 |5 6|489
---+---+---
892|743|561
634|951|728
751|268|394

```
* The output is formatted with one number per line, formatted like `(x,y):z` \- x and y start from one at the top left and increase down and right; z is the number to be added.

+ In this case these would all be valid outputs: `(3,4):3`, `(3,4):7`, `(5,4):3`, `(5,4):7`, `(3,6):3`, `(3,6):7`, `(5,6):3`, and `(5,6):7`, as any one of these would allow the board to be solved.
* If a unique/solved Sudoku board is entered, the program should not print anything, even a newline.
* The program should run in less than an hour for any board (I suggest testing using a fully blank board, or a board with one random number on it...).

## Scoring:

* Take your total (golfed) code size in characters, *including all whitespace*...

## Bonuses:

**1/2 code size**: If the program prints a single exclamation point and stops upon having a board with no solutions entered.

**1/2 code size**: If the program prints two exclamation points and stops upon having a board with an internal contradiction entered (two numbers the same on the same row/column/square).

# Answer
# Brachylog, 245 bytes /2 = 122.5

```
@n:1a:"-"x:7fF:3a$\:3a@3:4a,Fc~bCh[0:0:0]gO,Co~c[V:O:T]h:F:6f:10ao:ba(h:11a;!);"!!"w!
h"-".|:"|"x:2f.
e(~m["0123456789":.]`;0<.<=9)
:ha#d.
:@3az:ca:5a.
:3a.
hs.:=a,?t:9ac:=fl1
:Im:8f:[[I]]z:ca.
:Jm:J.
:ha.
lg:?c.
b:+a[X:Y],?h:Y:Xr:"(~d,~d):~d
"w

```

**(Note that you have to use the version of the language as of this commit. This code would need some slight changes for it to work properly in the following versions of Brachylog)**

This prints `"!!"` if the given board has internal contradictions (This takes a few seconds in that case however on TIO, so be patient).

I'm not sure I understand the first bonus correctly so I'm not addressing it.

This is obviously non-competing since the language is much more recent than the challenge, however since there are no other answers I'm not sure this matters a whole lot…

### Explanation

* Main predicate:

```
@n                Split the input on line breaks
:1a:"-"x          Transform into a list of lists, each sublist contains a line's values
:7fF              Transform so that cells are [Value:X:Y]
:3a               All values on lines must be different
$\:3a             All values on columns must be different (by transposition)
@3:4a,            All 3*3 block values must be different
Fc~bCh[0:0:0]gO,  Append a fake cell [0:0:0]
Co~c[V:O:T]       Sort the board, the blank cells V will be those before O ([0:0:0])
h:F:6f            Find all subsets of blank cells with specific values for which
                      the board has only one solution
:10ao             Sort the subsets by lengths
:ba               Discard the lengths
(
  h:11a             Print the first subset = an answer
;                 Or (board is already fully determined)
  !                 Terminate
)
;                 Or (Some values don't respect the constraints)
"!!"w!            Print "!!" and terminate

```
* Predicate 1: Remove all "`|`" on lines, transform the `---+---+---` into `-` to remove them after

```
h"-".    If the first char is "-", then Output is "-"
|        Or
:"|"x    Remove all occurences of "|" from the input
:2f.     Output is the result of all outputs of predicate 2 on the filtered string

```
* Predicate 2: Convert one char to an integer, or if blank to a variable between 1 and 9.

```
e                      Take a char of the input string
(
  ~m["0123456789":.]     Output is the index of the char in "0123456789"
  `                      Discard the choice point caused by the ;
;                      Or
  0<.<=9                 Output is an integer between 1 and 9
)

```
* Predicate 3: Impose that all values of the input list of cells must be distinct

```
:ha    Retrieve the head of each cell (i.e. the value) in the input
#d.    Apply a constraint of distinctness to those values

```
* Predicate 4: Apply the distinctness constraint to values in 3\*3 blocks

```
:@3a            Split 3 lines of the board in 3 parts
    z           Zip them together
     :ca:5a.    Concatenate each element of the zip, apply predicate 5 to that

```
* Predicate 5:

```
:3a.    Apply predicate 3 to each element of the input

```
* Predicate 6: Assign values satisfying the constraints to a subset of the blank cells, then with those values there is only one solution to the board.

```
hs.       Output is a subset of the blank cells
:=a,      Assign values to those cells
?t:9ac    Concatenate the values of all cells of the board
:=f       Find all solved boards
l1        There is only 1 such solved board

```
* Predicate 7: Transforms the board such that each cell is now `[V:X:Y]` instead of only `V` (the value).

```
:Im       Take the Ith line of the board
:8f       Transform all elements of the line using predicate 8
:[[I]]z   Zip the result with [I]
:ca.      Concatenate each element of the zip

```
* Predicate 8: Transforms a line such that each cell is now `[V:X]`.

```
:Jm    Take the Jth element of the line
:J.    Output is [That element:J]

```
* Predicate 9: Retrieve the values of cells

```
:ha.   Take the head of each element of the input

```
* Predicate 10: Append the length of a subset at the beginning of it

```
lg     Put the length of the input in a list
:?c.   Concatenate it with the input

```
* Predicate 11: Print one cell

```
b:+a[X:Y],        Increment coordinates by 1 to get X and Y
?h:Y:Xr:          Build the list [X:Y:Value]
"(~d,~d):~d\n"w   Format that list as "('X','Y'):'Value'\n" to STDOUT

```
> 10 votes

---
Tags: code-golf, game, sudoku
---


# Question
Title: Include a JavaScript script with JavaScript
To dynamically include a JavaScript file in a web page, you'd normally insert a `<script>` tag pointing to your script. For example:

```
var js_file= document.createElement("script");
js_file.src='http://example.com/js.js';
document.body.appendChild(js_file);

```

Write JavaScript code will load an external JavaScript file in the current page and:

* Shortest valid answer wins
* The file is hosted on `https://pastebin.com/raw/rV6dDDj9` (content is `console.log('Good job!');`)
* The code must be vanilla JavaScript (no jQuery, etc.)
* Answer validity test is done in the web browser console. Criteria:
    + URL requested and JS file downloaded.
    + Console prints `Good job!`

# Answer
## ~~77~~ ~~75~~ 71 bytes

```
with(document)body.appendChild(createElement`script`).src=`//v.ht/Xa33`
```

Edit: Saved 2 bytes thanks to @jrich. Saved 4 bytes thanks to @Bálint.
> 10 votes

# Answer
## 49 bytes

```
document.write`<script src=//v.ht/KvtI></script>`

```

no one clearly said: you should keep current page content
> 12 votes

# Answer
# 75 bytes

```
document.body.appendChild(document.createElement`script`).src="//v.ht/Xa33"

```

@Neil's answer was quite similar to this, but he found an ingenious shortcut involving `with(...)`. I will not copy it here, because he came up with it.

Thanks to @Bálint for the short URL.
> 3 votes

# Answer
## 72 bytes

`(D=document).body.appendChild(D.createElement`script`).src="//v.ht/Xa33"`

for using more than once(3 call):

92 then always 36

`(D=document)[B="body"][A="appendChild"](D[C="createElement"](s="script")).src="//v.ht/Xa33";
D[B][A](D[C](s)).src="//v.ht/Xa33";
D[B][A](D[C](s)).src="//v.ht/Xa33"`

93 then always 35

`D=document,B=D.body,B.a=B.appendChild,D.c=D.createElement;
B.a(D.c`script`).src="//v.ht/Xa33";
B.a(D.c`script`).src="//v.ht/Xa33";
B.a(D.c`script`).src="//v.ht/Xa33";`

99 then always 30

`D=document,B=D.body,B.a=B.appendChild,D.c=D.createElement,s="script";
B.a(D.c(s)).src="//v.ht/Xa33";
B.a(D.c(s)).src="//v.ht/Xa33";
B.a(D.c(s)).src="//v.ht/Xa33";`

99 then always 26

`D=document,A=e=>D.body.appendChild(e),C=e=>D.createElement(e),s="script";
A(C(s)).src="//v.ht/Xa33";
A(C(s)).src="//v.ht/Xa33";
A(C(s)).src="//v.ht/Xa33";`

87 then always 15

`S=e=>document.body.appendChild(document.createElement("script")).src=e;
S`//v.ht/Xa33`;
S`//v.ht/Xa33`;
S`//v.ht/Xa33`;`

88 then always 22

`S=e=>document.body.appendChild(document.createElement("script"));
S().src="//v.ht/Xa33";
S().src="//v.ht/Xa33";
S().src="//v.ht/Xa33";`
> 1 votes

# Answer
## 89 bytes

```
n=[];for(i in d=document)n.push(i);d.body[n[173]](d[n[41]]`script`).src=`//goo.gl/rPQ0Jk`

```

This is **incredibly** browser-dependent. Actually even worse than that, it pretty much only works on codegolf.stackexchange.com, in the browser console, in FireFox. Ah well.

Please don't get too mad when it (likely) doesn't work on your particular browser configuration, since if it is even slightly different from mine it could fail.

(yeah, probably invalid because of that. Not going to win anyway.)
> 0 votes

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


title: Generate Pascal's Braid

text:
# Question
Title: Generate Pascal's Braid
This is Pascal's Braid:

```
 1 4  15  56   209   780    2911    10864     40545      151316      564719
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
 1 4  15  56   209   780    2911    10864     40545      151316      564719

```

I totally made that up. Blaise Pascal didn't have a braid as far as I can tell, and if he did it was probably made of hair instead of numbers.

It's defined like this:

1. The first column has a single `1` in the middle.
2. The second column has a `1` at the top and at the bottom.
3. Now we alternate between putting a number in the middle or two copies of a number at the top and bottom.
4. If the number goes on the top or the bottom, it will be the sum of the two adjacent numbers (e.g. `56 = 15 + 41`). If you tilt your head a little, this is like a step in Pascal's triangle.
5. If the number goes in the middle, it will be the sum of all three adjacent numbers (e.g. `41 = 15 + 11 + 15`).

Your task will be to print (some part of) this braid.

## Input

You should write a program or function, which receives a single integer `n`, giving the index of the last column to be output.

You may choose whether the first column (printing only a single `1` on the middle line) corresponds to `n = 0` or `n = 1`. This has to be a consistent choice across all possible inputs.

## Output

Output Pascal's Braid up to the `n`th column. The whitespace has to match exactly the example layout above, except that you may pad the shorter line(s) to the length of the longer line(s) with spaces and you may optionally output a single trailing linefeed.

In other words, every column should be exactly as wide as the number (or pair of equal numbers) in that column, numbers in successive columns should not overlap and there should be no spaces between columns.

You may either print the result to STDOUT (or the closest alternative), or if you write a function you may return either a string with the same contents or a list of three strings (one for each line).

## Further Details

You may assume that `n` won't be less than the index of the first column (so not less than `0` or `1` depending on your indexing). You may also assume that the last number in the braid is less than 256 or the largest number representable by your language's native integer type, whichever is *greater*. So if your native integer type can only store bytes, you can assume that the largest `n` is `9` or `10` (depending on whether you use 0- or 1-based `n`) and if it can store signed 32-bit integers, `n` will be at most `33` or `34`.

Standard rules apply. The shortest code wins.

## OEIS

Here are a few relevant OEIS links. Of course, these contain spoilers for different ways to generate the numbers in the braid:

## Test Cases

These test cases use 1-base indexing. Each test case is four lines, with the first being the input and the remaining three being the output.

```
1

1

---
2
 1
1
 1
---
3
 1
1 3
 1
---
5
 1 4
1 3 11
 1 4
---
10
 1 4  15  56   209
1 3 11  41  153
 1 4  15  56   209
---
15
 1 4  15  56   209   780    2911
1 3 11  41  153   571   2131    7953
 1 4  15  56   209   780    2911
---
24
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560

```

# Answer
> 5 votes
# Jelly, ~~31~~ ~~30~~ 29 bytes

```
Q;S⁹o_
3ḶḂç@⁸Ð¡Iµa"Ṿ€o⁶z⁶Zµ€Z

```

This is a monadic link; it accepts a 0-based column index as argument and returns a list of strings.

Try it online!

### How it works

```
Q;S⁹o_                  Helper link.
                        Arguments: [k, 0, k] and [0, m, 0] (any order)

Q                       Unique; deduplicate the left argument.
 ;                      Concatenate the result with the right argument.
  S                     Take the sum of the resulting array.
   ⁹o                   Logical OR with the right argument; replaces zeroes in the
                        right argument with the sum.
     _                  Subtract; take the difference with the right argument to
                        remove its values.
                        This maps [k, 0, k], [0, m, 0] to [0, k + m, 0] and
                        [0, m, 0], [k, 0, k] to [m + 2k, 0, m + 2k].

3ḶḂç@⁸Ð¡Iµa"Ṿ€o⁶z⁶Zµ€Z  Monadic link. Argument: A (array of column indices)

3Ḷ                      Yield [0, 1, 2].
  Ḃ                     Bit; yield [0, 1, 0].
        I               Increments of n; yield [].
      Ð¡                Apply...
   ç@                       the helper link with swapped arguments...
     ⁸                      n times, updating the left argument with the return
                            value, and the right argument with the previous value
                            of the left one. Collect all intermediate values of
                            the left argument in an array.
         µ         µ€   Map the chain in between over the intermediate values.
            Ṿ€          Uneval each; turn all integers into strings.
          a"            Vectorized logical AND; replace non-zero integers with
                        their string representation.
              o⁶        Logical OR with space; replace zeroes with spaces.
                z⁶      Zip with fill value space; transpose the resulting 2D
                        array after inserting spaces to make it rectangular.
                  Z     Zip; transpose the result to restore the original shape.
                     Z  Zip; transpose the resulting 3D array.

```

# Answer
> 12 votes
# Pyth, 44 bytes

The number generation took 20 bytes, and the formatting took 24 bytes.

```
jsMC+Led.e.<bkC,J<s.u+B+hNyeNeNQ,1 1Qm*;l`dJ

```

Try it online!

```
jsMC+Led.e.<bkC,J<s.u+B+hNyeNeNQ,1 1Qm*;l`dJ   input as Q
                   .u          Q,1 1           repeat Q times, starting with [1,1],
                                               collecting all intermediate results,
                                               current value as N:
                                               (this will generate
                                                more than enough terms)
                       +hNyeN                  temp <- N[0] + 2*N[-1]
                     +B      eN                temp <- [temp+N[-1], temp]

now, we would have generated [[1, 1], [3, 4], [11, 15], [41, 56], ...]

jsMC+Led.e.<bkC,J<s                 Qm*;l`dJ
                  s                            flatten
                 <                  Q          first Q items
                J                              store in J
                                     m    dJ   for each item in J:
                                         `     convert to string
                                        l      length
                                      *;       repeat " " that many times

jsMC+Led.e.<bkC,
              C,     transpose, yielding:
[[1, ' '], [1, ' '], [3, ' '], [4, ' '], [11, '  '], ...]
(each element with as many spaces as its length.)
        .e            for each sub-array (index as k, sub-array as b):
          .<bk            rotate b as many times as k

[[1, ' '], [' ', 1], [3, ' '], [' ', 4], [11, '  '], ...]

jsMC+Led
    +Led              add to each sub-array on the left, the end of each sub-array
   C                  transpose
 sM                   sum of each sub-array (reduced concatenation)
j                     join by new-lines

```

# Answer
> 7 votes
# Python 2, 120 bytes

```
a=1,1,3,4
n=input()
y=0
exec"y+=1;t='';x=0;%sprint t;"%(n*"a+=a[-2]*4-a[-4],;v=`a[x]`;t+=[v,len(v)*' '][x+y&1];x+=1;")*3

```

Try it on Ideone.

# Answer
> 7 votes
# MATL, 38 bytes

```
1ti:"yy@oQ*+]vG:)!"@Vt~oX@o?w]&v]&hZ}y

```

**Try it online!**

Computing an array with the (unique) numbers takes the first 17 bytes. Formatting takes the remaining 21 bytes.

## Explanation

### Part 1: generate the numbers

This generates an array with the numbers from the first and second rows in increasing order: `[1; 1; 3; 4; 11; 15; ...]`. It starts with `1`, `1`. Each new number is iteratively obtained from the preceding two. Of those, the second is multiplied by `1` or `2` depending on the iteration index, and then summed to the first to produce the new number.

The number of iterations is equal to the input `n`. This means that `n+2` numbers are generated. Once generated, the array needs to be trimmed so only the first `n` entries are kept.

```
1t      % Push 1 twice
i:      % Take input n. Generage array [1 2 ... n]
"       % For each
  yy    %   Duplicate the two most recent numbers
  @o    %   Parity of the iteration index (0 or 1)
  Q     %   Add 1: gives 1 for even iteration index, 2 for odd
  *+    %   Multiply this 1 or 2 by the most recent number in the sequence, and add
       %    to the second most recent. This produces a new number in the sequence
]       % End for each
v       % Concatenate all numbers in a vertical array
G:)     % Keep only the first n entries

```

### Part 2: format the output

For each number in the obtained array, this generates two strings: string representation of the number, and a string of the same length consisting of character 0 repeated (character 0 is displayed as a space in MATL). For even iterations, these two strings are swapped.

The two strings are then concatenated vertically. So `n` 2D char arrays are produced as follows (using `·` to represent character 0):

```
·
1

1
·

·
3

4
·

··
11

15
··

```

These arrays are then concatenated horizontally to produce

```
·1·4··15
1·3·11··

```

Finally, this 2D char array is split into its two rows, and the first is duplicated onto the top of the stack. The three strings are displayed in order, each on a different line, producing the desired output

```
!       % Transpose into a horizontal array [1 1 3 4 11 15 ...]
"       % For each
  @V    %   Push current number and convert to string
  t~o   %   Duplicate, negate, convert to double: string of the same length consisting
        %   of character 0 repeated
  X@o   %   Parity of the iteration index (1 or 0)
  ?     %   If index is odd
    w   %     Swap
  ]     %   End if
  &v    %   Concatenate the two strings vertically. Gives a 2D char array representing
        %   a "numeric column" of the output (actually several columns of characters)
]       % End for
&h      % Concatenate all 2D char arrays horizontally. Gives a 2D char array with the
        % top two rows of the output
Z}      % Split this array into its two rows
y       % Push a copy of the first row. Implicitly display

```

# Answer
> 6 votes
# Haskell, 101 bytes

```
a=1:1:t
t=3:4:zipWith((-).(4*))t a
g(i,x)=min(cycle" 9"!!i)<$>show x
f n=[zip[y..y+n]a>>=g|y<-[0..2]]

```

Defines a function `f :: Int → [String]`.

* Michael Klein reminded me I didn’t need to call `unlines` on the result, saving 7 bytes. Thanks!
* I saved a byte by replacing `" 9"!!mod i 2` with `cycle" 9"!!i`.
* Three more bytes by writing two corecursive lists instead of using `drop`.
* My girlfriend pointed out I can save two more bytes by starting my answers at `0` instead of `1`.

# Answer
> 3 votes
# C, 183 177 176 bytes

```
#define F for(i=0;i<c;i++)
int i,c,a[35],t[9];p(r){F printf("%*s",sprintf(t,"%d",a[i]),r-i&1?t:" ");putchar(10);}b(n){c=n;F a[i]=i<2?1:a[i-2]+a[i-1]*(i&1?1:2);p(0);p(1);p(0);}

```

## Explanation

C is never going to win any prizes for brevity against a higher level language, but the exercise is interesting and good practice.

The macro F shaves off six bytes at the cost of readability. Variables are declared globally to avoid multiple declarations. I needed a character buffer for sprintf, but since K&R is loose with type checking, sprintf and printf can interpret t\[9\] as a pointer to a 36-byte buffer. This saves a separate declaration.

```
#define F for(i=0;i<c;i++)
int i,c,a[35],t[9];

```

Pretty printing function, where r is the row number. Sprintf formats the number and computes the column width. To save space we just call this three times, one for each row of output; the expression r-i&1 filters what gets printed.

```
p(r) {
    F
        printf("%*s", sprintf(t, "%d", a[i]), r-i&1 ? t
                                                    : " ");
    putchar(10);
}

```

Entry point function, argument is number of columns. Computes array a of column values a\[\], then calls printing function p once for each row of output.

```
b(n) {
    c=n;
    F
        a[i] = i<2 ? 1
                   : a[i-2] + a[i-1]*(i&1 ? 1
                                          : 2);
    p(0);
    p(1);
    p(0);
}

```

Sample invocation (not included in answer and byte count):

```
main(c,v) char**v;
{
    b(atoi(v[1]));
}

```

## Updated

Incorporated the inline sprintf suggestion from tomsmeding. That reduced the count from 183 to 177 characters. This also allows removing the the braces around the printf(sprintf()) block since it's only one statement now, but that only saved one character because it still needs a space as a delimiter. So down to 176.

# Answer
> 2 votes
## PowerShell v2+, 133 bytes

```
param($n)$a=1,1;1..$n|%{$a+=$a[$_-1]+$a[$_]*($_%2+1)};$a[0..$n]|%{$z=" "*$l+$_;if($i++%2){$x+=$z}else{$y+=$z}$l="$_".Length};$x;$y;$x

```

44 bytes to calculate the values, 70 bytes to formulate the ASCII

Takes input `$n` as the zero-indexed column. Sets the start of our sequence array `$a=1,1`. We then loop up to `$n` with `1..$n|%{...}` to construct the array. Each iteration, we concatenate on the sum of (two elements ago) + (the previous element)\*(whether we're odd or even index). This will generate `$a=1,1,3,4,11...` up to `$n+2`.

So, we need to slice `$a` to only take the first `0..$n` elements, and pipe those through another loop `|%{...}`. Each iteration we set helper `$z` equal to a number of spaces plus the current element as a string. Then, we're splitting out whether that gets concatenated onto `$x` (the top and bottom rows) or `$y` (the middle row) by a simple odd-even `if`/`else`. Then, we calculate the number of spaces for `$l` by taking the current number, stringifying it, and taking its `.Length`.

Finally, we put `$x`, `$y`, and `$x` again on the pipeline, and output is implicit. Since the default `.ToString()` separator for an array when printing to STDOUT is a newline, we get that for free.

### Example

```
PS C:\Tools\Scripts\golfing> .\pascal-braid.ps1 27
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560       7865521        29354524
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841       5757961       21489003
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560       7865521        29354524

```

# Answer
> 0 votes
## PHP 265 bytes

```
<?php $i=$argv[1];$i=$i?$i:1;$a=[[],[]];$s=['',''];$p='';for($j=0;$j<$i;$j++){$y=($j+1)%2;$x=floor($j/2);$v=$x?$y?2*$a[0][$x-1]+$a[1][$x-1]:$a[0][$x-1]+$a[1][$x]:1;$s[$y].=$p.$v;$a[$y][$x]=$v;$p=str_pad('',strlen($v),' ');}printf("%s\n%s\n%s\n",$s[0],$s[1],$s[0]);

```

Un-golfed:

```
$a = [[],[]];
$s = ['',''];

$p = '';

$i=$argv[1];
$i=$i?$i:1;
for($j=0; $j<$i; $j++) {
    $y = ($j+1) % 2;
    $x = floor($j/2);

    if( $x == 0 ) {
        $v = 1;
    } else {
        if( $y ) {
            $v = 2 * $a[0][$x-1] + $a[1][$x-1];
        } else {
            $v = $a[0][$x-1] + $a[1][$x];
        }
    }
    $s[$y] .= $p . $v;
    $a[$y][$x] = $v;
    $p = str_pad('', strlen($v), ' ');
}

printf("%s\n%s\n%s\n", $s[0], $s[1], $s[0]);

```

## Python 278 bytes

```
import sys,math;a=[[],[]];s=['',''];p='';i=int(sys.argv[1]);i=1 if i<1 else i;j=0
while j<i:y=(j+1)%2;x=int(math.floor(j/2));v=(2*a[0][x-1]+a[1][x-1] if y else a[0][x-1]+a[1][x]) if x else 1;s[y]+=p+str(v);a[y].append(v);p=' '*len(str(v));j+=1
print ("%s\n"*3)%(s[0],s[1],s[0])

```

# Answer
> 0 votes
## Batch, 250 bytes

```
@echo off
set s=
set d=
set/ai=n=0,j=m=1
:l
set/ai+=1,j^^=3,l=m+n*j,m=n,n=l
set t=%s%%l%
for /l %%j in (0,1,9)do call set l=%%l:%%j= %%
set s=%d%%l%
set d=%t%
if not %i%==%1 goto l
if %j%==1 echo %d%
echo %s%
echo %d%
if %j%==2 echo %s%

```

Since the first and third lines are the same, we just have to build two strings. Here `d` represents the string that ends with the last entry and `s` represents the string that ends with spaces; the last four lines ensure that they are printed in the appropriate order. `i` is just the loop counter (it's slightly cheaper than counting down from `%1`). `j` is the toggle between doubling the previous number before adding it to the current number to get the next number. `m` and `n` contain those numbers. `l`, as well as being used as a temporary to calculate the next number, also gets its digits replaced with spaces to pad out `s`; `s` and `d` are exchanged each time via the intermediate variable `t`.

# Answer
> 0 votes
# Ruby, 120 bytes

Returns a multiline string.

Try it online!

```
->n{a=[1,1];(n-2).times{|i|a<<(2-i%2)*a[-1]+a[-2]}
z=->c{a.map{|e|c+=1;c%2>0?' '*e.to_s.size: e}*''}
[s=z[0],z[1],s]*$/}

```

# Answer
> 0 votes
## Matlab, 223 characters, 226 bytes

```
function[]=p(n)
r=[1;1];e={(' 1 ')',('1 1')'}
for i=3:n;r(i)=sum((mod(i,2)+1)*r(i-1)+r(i-2));s=num2str(r(i));b=blanks(floor(log10(r(i)))+1);if mod(i,2);e{i}=[b;s;b];else e{i}=[s;b;s];end;end
reshape(sprintf('%s',e{:}),3,[])

```

Ungolfed and commented:

```
function[]=p(n)
r=[1;1];                                    % start with first two
e={(' 1 ')',('1 1')'}                       % initialize string output as columns of blank, 1, blank and 1, blank, 1.
for i=3:n;                                  % for n=3 and up!
    r(i)=sum((mod(i,2)+1)*r(i-1)+r(i-2));   % get the next number by 1 if even, 2 if odd times previous plus two steps back
    s=num2str(r(i));                        % define that number as a string
    b=blanks(floor(log10(r(i)))+1);         % get a number of space characters for that number of digits
    if mod(i,2);                            % for odds
        e{i}=[b;s;b];                       % spaces, number, spaces
    else                                    % for evens
        e{i}=[s;b;s];                       % number, spaces, number
    end;
end
reshape(sprintf('%s',e{:}),3,[])            % print the cell array of strings and reshape it so it's 3 lines high

```

# Answer
> 0 votes
# PHP, ~~135~~ ~~124~~ ~~123~~ 120 bytes

```
<?while($i<$argv[1]){${s.$x=!$x}.=${v.$x}=$a=$i++<2?:$v1+$v+$x*$v;${s.!$x}.=str_repeat(' ',strlen($a));}echo"$s
$s1
$s";

```

taking advantage of implicit typecasts and variable variables
a third of the code (37 bytes) goes into the spaces, 64 bytes altogether used for output

**breakdown**

```
$i=0; $x=false; $v=$v1=1; $s=$s1='';    // unnecessary variable initializations
for($i=0;$i<$argv[1];$i++)  // $i is column number -1
{
    $x=!$x; // $x = current row: true (1) for inner, false (empty string or 0) for outer
    // calculate value
    $a=
        $i<2?               // first or second column: value 1
        :$v1+(1+$x)*$v      // inner-val + (inner row: 1+1=2, outer row: 1+0=1)*outer-val
    ;
    ${s.$x}.=${v.$x}=$a;    // replace target value, append to current row
    ${s.!$x}.=str_repeat(' ',strlen($a));    // append spaces to other row
}
// output
echo "$s\n$s1\n$s";

```

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


# Question
Title: Given a truth table, output a Stackylogic program that satisfies it
Stackylogic is a programming language I made up in a previous challenge: **Run Stackylogic**. Read that post for full details and examples, but here is how it works paraphrased:

> Stackylogic takes `0`'s and `1`'s for input and outputs a single `0` or `1` upon completion.
>
> A program consists of lines that only contain the characters `01?` as well as exactly one `<` at the end of one of the lines. Lines may not be empty and the line with the `<` must have at least one `0`, `1`, or `?` before it.
>
> Here's a sample program that computes the NAND of two bits:
>
> ```
> 1
> ?<
> 11
> ?
> 0
>
> ```
>
> Every line in a program is considered a stack, with the bottom on the left and the top on the right. Implicitly, there is an empty stack (i.e. empty line) before the first line in a program and after the last line.
>
> The `<`, called the cursor, marks the stack to start on when a program is run. Execution proceeds as follows:
>
> 1. Pop the top character off the stack the cursor is currently pointing to.
>
> * If the character is `?`, prompt the user for a `0` or a `1` and act as if that was the character.
>     * If the character is `0`, move the cursor one stack up (to the line above the current line).
>     * If the character is `1`, move the cursor one stack down (to the line below the current line).
> 2. If the stack the cursor moves to is empty, output the last value that was popped off a stack (always a `0` or `1`), and end the program.
> 3. Else, if the stack the cursor moves to is not empty, go back to step 1 and repeat the process.

The key thing to realize for this challenge is that all Stackylogic programs equate to a truth table. Some predetermined number of boolean values are input and exactly one boolean is deterministically output.

So your task is to produce a Stackylogic program that satisfies or simulates, i.e. has the same output as any given truth table. But it's not obvious that Stackylogic *can* simulate any truth table, so here's a proof by induction:

> ### Base Case
>
> The two 0-input truth tables are the tables that always output `0` or `1`. The Stackylogic equivalents of these tables are `0<` and `1<` respectively.
>
> ### Inductive Step
>
> Assume Stackylogic can simulate any N-input truth table. Let M = N + 1.
>
> An M-input table, T, can be expressed as two N-input tables, T0 and T1, plus the additional input bit B. When B is 0, the result of T0 is used. When B is 1, the result of T1 is used.
>
> For example, the 3-input truth table corresponding to the pseudocode
>
> ```
> if B:
>     result = x OR y
> else:
>     result = x NAND y
>
> ```
>
> is
>
> ```
> B x y | result
> 0 0 0 | 1
> 0 0 1 | 1
> 0 1 0 | 1
> 0 1 1 | 0
> 1 0 0 | 0
> 1 0 1 | 1
> 1 1 0 | 1
> 1 1 1 | 1
>
> ```
>
> which is really the two 2-input truth tables for NAND and OR stacked atop each other with the muxing bit B.
>
> Let S0 and S1 be the Stackylogic programs that satisfy T0 and T1 respectively (we know these exist based on the first assumption). Program S that satisfies T can then be constructed as:
>
> ```
> [lines of S<sub>0</sub> excluding the cursor, with 0 appended to all lines below the cursor]
> ?<
> [lines of S<sub>1</sub> excluding the cursor, with 1 appended to all lines above the cursor]
> ```
>
> This arrangement effectively muxes between S0 and S1 based on the first input bit (from line `?<`). If it is `0`, the cursor will ride the appended `0`'s up to the original cursor position of S0, which will then be bordered top and bottom by empty stacks, and thus run exactly identical to the original S0. Likewise, if `1` is input, the cursor will ride the `1`'s down to S1's cursor position and proceed to execute it as if it were alone.
>
> For example, Stackylogic programs for OR and NAND are
>
> ```
> ?
> ?<
>
> ```
>
> and
>
> ```
> 1
> ?<
> 11
> ?
> 0
>
> ```
>
> They can be combined to simulate
>
> ```
> if B:
>     result = x OR y
> else:
>     result = x NAND y
>
> ```
>
> like so:
>
> ```
> 1
> ?
> 110
> ?0
> 00
> 0
> ?<
> ?1
> ?
>
> ```
>
> Thus, any truth table can be simulated by a Stackylogic program.

# Challenge

Write a program or function that takes in an N input truth table (N \> 0) in the form of a list of 2N boolean values that represent the outputs of the table in ascending binary order.

Any reasonable input format is alright. e.g. for an OR truth table

```
x y | OR
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

```

any of these styles of inputs would be fine:

`0111`

`0, 1, 1, 1`

```
0
1
1
1

```

`[False, True, True, True]`

Print or return a Stackylogic program that satisfies the truth table, i.e. has the exact same output given the same input. *Any* finite program that satisfies that table is valid output. You do not need to follow the inductive proof's method of construction. The Stackylogic programs do not need to be optimally short.

For example, if the input were `11100111`, one valid output would be

```
1
?
110
?0
00
0
?<
?1
?

```

but there are many others.

**The shortest code in bytes wins.**

See the original Stackylogic challenge if you need an interpreter.

# Answer
# Pyth, 53 bytes

```
L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<

```

Try online

This is an exact implementation of the system described in the challenge for how to implement arbitrary truth tables in Stackylogic. We simply cut the truth table in half, implement it recursively, and then append 0 and 1 as appropriate.

This defines a recursive function, whose return value is `[1, ['0', '?', '1']]`, where the first number is the location of the pointer, and the rest is a stackylogic program.

```
L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<
                                                         Q = eval(input())
L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hb
L                                                 def y(b): return
 ?tb                                              if b[1:] (base case on false)
                                      ,0]`hb      else: [0, str([0])]
                                                  then:
           c2b                                    Cut the input in half
         yM                                       Map y over the halves
        J                                         Store that in J
    ,leh                                          The cursor position is the length
                                                  of the body of the first function
                 .e                 J             enum-map, where k is the index
                                                  and b is the value, over J
                   .e             eb              enum-map, Y is the index and
                                                  Z is the value, over body of b
                     +W         Zk                Add to Z (line) k (the overall
                                                  index, 0 or 1) conditional on
                          -Yhb                    Y (line index) - cursor
                       _Wk                        Negated if k
                      >       0                   > 0
               X0                    \?           Add '?' to the first element
              s                                   Concatenate, giving the body

jXF+yQ\<
    yQ      Call the above on the input
   +  \<    Append a '<'
 XF         Splat the 3 element list into the 'append-at' function,
            adding the curson in the right place
j           Join on newlines and print.

```
> 8 votes

# Answer
# Python 3, ~~352~~ ~~208~~ 205 bytes

~~This is still very ungolfed, and I will try to add an explanation later.~~ *After some modifications, I managed to remove ~~144~~ 147 bytes.*

```
f=lambda x,l=len,r=range:'\n'.join(*x)if l(x)<2 else f([[x[i][j]+['0',''][j<=l(x[i])//2]for j in r(l(x[i]))]+[['?','?<'][l(x)<3]]+[x[i+1][j]+['1',''][j>=l(x[i])//2]for j in r(l(x[i]))]for i in r(0,l(x),2)])

```

A function `f` that takes input of the truth table values as a list of Booleans of the form `['1','1','1','0','0','1'...]`, where `'1'` is truthy and `'0'` is falsey, and returns a Stackylogic program.

Try it on Ideone

If you want to test a produced program, you can use GamrCorps's Convex interpreter here.

**How it works**

This is a recursive function and uses the inductive method described in the question.

At the zero-indexed recursion level `a`, the function creates `n/2` `a+1`-input Stackylogic programs from the `n` `a`-input programs in the list. This is done by joining all adjacent pairs of two programs in the list with `?`; since the cursor is always at the middle element of each constituent program, the required appending of `0` or `1` can be performed by iterating over each line of the programs being joined, and appending if the index of the current line is less than or equal to/greater than or equal to the middle index as appropriate. If the list contains only two programs, the next recursive call will give the final program; since this requires a cursor, joining instead occurs on `?<`.

When the list has length `1`, the list must contain just one element containing the full program. Hence, all lines in the program are joined on a newline, and then returned.

An example helps to illustrate this:

```
Take the input ['1', '1', '1', '0', '0', '1', '1', '1'].

Level  Return value

0  [['1', '?', '1'], ['1', '?', '0'], ['0', '?', '1'], ['1', '?', '1']]
1  [['1', '?', '10', '?', '11', '?', '0'], ['0', '?', '10', '?', '11', '?', '1']]
2  [['1', '?', '10', '?', '110', '?0', '00', '?<', '01', '?1', '101', '?', '11', '?', '1']]
3  '1\n?\n10\n?\n110\n?0\n00\n?<\n01\n?1\n101\n?\n11\n?\n1'

which when printed gives:

1
?
10
?
110
?0
00
?<
01
?1
101
?
11
?
1

```
> 3 votes

---
Tags: code-golf, binary, code-generation, logic-gates, logic
---