# Question
Title: Matrix property X revisited (or the Joy of X)
This challenge is partly an algorithms challenge, partly an optimization challenge and partly simply a fastest code challenge.

A T matrix is fully specified by its first row `r` and first column `c`. Each remaining element of the matrix is just a copy of the element that is diagonally up and left. That is `M[i,j] = M[i-1,j-1]`. We will allow T matrices which are not square. We do however always assume that the number of rows is no more than the number of columns. For example, consider the following 3 by 5 T matrix.

```
10111
11011
11101

```

We say a matrix has property X if it contains two non-empty sets of columns with non-identical indices which have the same (vector) sum. The vector sum of one or more columns is simply an element-wise summation of their columns. That is the sum of two or more columns containing `x` elements each is another column containing `x` elements. The sum of one column is trivially the column itself.

The matrix above trivially has property X as the first and last columns are the same. The identity matrix never has property X.

If we just remove the last column of the matrix above then we get an example which does not have property X and would give a score of 4/3.

```
1011
1101
1110

```

**The task**

The task is to write code to find the highest scoring T matrix with binary entries and which *does not* have property X. For clarity, a matrix with binary entries has the property that each one of its entries is either 0 or 1.

**Score**

Your score will be the number columns divided by the number of rows in your best scoring matrix.

**Tie Breaker**

If two answers have the same score, the one submitted first wins.

In the (very) unlikely event that someone finds a method to get unlimited scores, the first valid proof of such a solution will be accepted. In the even more unlikely event that you can find a proof of optimality of a finite matrix I will of course award the win too.

**Hint**

All the answers at Find highest scoring matrix without property X are valid here but they are not optimal. There are T matrices without property X which are not cyclic.

For example, there is a 7 by 12 T matrix without property X but no such cyclic matrix.

**21/11 would beat all the current answers from this and the previous challenge.**

**Languages and libraries**

You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.

**Bonus** The first answer with a score greater than 2 gets an immediate **200 point** bounty award. Ton Hospel has now achieved this!

---

**Current leader board**

* **C++**. Score 31/15 by Ton Hospel
* **Java**. Score 36/19 by Peter Taylor
* **Haskell**. Score 14/8 by alexander-brett

# Answer
# C++, Score ~~23/12~~ ~~25/13~~ ~~27/14~~ ~~28/14~~ 31/15

Finally a result with ratio \> 2:

```
rows=15,cols=31
1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0
1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1
1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0
1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1
0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1
0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0
0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0
1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1

```

I completely explored 1 to 14 rows. 15 would take too long to completely explore. The results are:

```
1/1   = 1
2/2   = 1
4/3   = 1.333
5/4   = 1.25
7/5   = 1.4
9/6   = 1.5
12/7  = 1.714
14/8  = 1.75
16/9  = 1.778
18/10 = 1.8
20/11 = 1.818
23/12 = 1.917
25/13 = 1.923
28/14 = 2

```

The code given below is an older version of the program. The newest version is at https://github.com/thospel/personal-propertyX.

```
/*
  Compile using something like:
    g++ -Wall -O3 -march=native -fstrict-aliasing -std=c++11 -g propertyX.cpp -lpthread -o propertyX
*/
#include <cstdint>
#include <climits>
#include <ctgmath>
#include <iostream>
#include <vector>
#include <array>
#include <chrono>
#include <mutex>
#include <atomic>
#include <thread>

using namespace std;

const int ELEMENTS = 2;

using uint    = unsigned int;
using Element = uint64_t;
using Column  = array<Element, ELEMENTS>;
using Set     = vector<Column>;
using Sum     = uint8_t;
using Index   = uint32_t;
using sec = chrono::seconds;

int const PERIOD = 5*60;
int const MAX_ROWS = 54;
int const COL_FACTOR = (MAX_ROWS+1) | 1;                // 55
int const ROW_ZERO   = COL_FACTOR/2;                    // 27
int const ROWS_PER_ELEMENT = CHAR_BIT * sizeof(Element) / log2(COL_FACTOR); //11
Element constexpr ELEMENT_FILL(Element v = ROW_ZERO, int n = ROWS_PER_ELEMENT) {
    return n ? ELEMENT_FILL(v, n-1) * COL_FACTOR + v : 0;
}
Element constexpr POWN(Element v, int n) {
    return n ? POWN(v, n-1)*v : 1;
}
Element const ELEMENT_TOP = POWN(COL_FACTOR, ROWS_PER_ELEMENT -1);
int const MAX_COLS = ROWS_PER_ELEMENT * ELEMENTS;       // 22

atomic<Index> col_next;
atomic<uint>  period;
chrono::steady_clock::time_point start;
mutex period_mutex;

uint ratio_row;
uint ratio_col;
mutex ratio_mutex;

auto const nr_threads = thread::hardware_concurrency();
// auto const nr_threads = 1;

struct State {
    State(uint cols);
    void process(Index i);
    void extend(uint row);
    void print(uint rows);
    Index nr_columns() const { return static_cast<Index>(1) << cols_; }

    Column last_;
    Element top_;
    int top_offset_;
    uint ratio_row_ = 0;
    uint ratio_col_ = 1;
    uint cols_;
    array<Sum, MAX_ROWS + MAX_COLS -1> side;
    vector<Set> sets;
};

ostream& operator<<(ostream& os, Column const& column) {
    for (int i=0; i<ELEMENTS; ++i) {
        auto v = column[i];
        for (int j=0; j<ROWS_PER_ELEMENT; ++j) {
            auto bit = v / ELEMENT_TOP;
            cout << " " << bit;
            v -= bit * ELEMENT_TOP;
            v *= COL_FACTOR;
        }
    }
    return os;
}

State::State(uint cols) : cols_{cols} {
    sets.resize(MAX_ROWS+2);
    for (int i=0; i<2; ++i) {
        sets[i].resize(2);
        for (int j=0; j < ELEMENTS; ++j) {
            sets[i][0][j] =  ELEMENT_FILL();
            sets[i][1][j] =  static_cast<Element>(-1) - ELEMENT_FILL(1);
        }
    }
    top_ = POWN(COL_FACTOR, (cols_-1) % ROWS_PER_ELEMENT);
    top_offset_ = ELEMENTS - 1 - (cols_-1) / ROWS_PER_ELEMENT;
}

void State::print(uint rows) {
    for (auto c=0U; c<cols_;c++) {
        for (auto r=0U; r<rows;r++) {
            cout << static_cast<int>(side[cols_-c+r-1]) << " ";
        }
        cout << "\n";
    }
    cout << "----------" << endl;
}

void check(uint cols, uint t) {
    State state(cols);

    Index nr_columns = state.nr_columns();
    while (1) {
        Index col = col_next++;
        if (col >= nr_columns) break;
        state.process(col);

        auto now = chrono::steady_clock::now();
        auto elapsed = chrono::duration_cast<sec>(now-start).count();
        if (elapsed >= period) {
            lock_guard<mutex> lock{period_mutex};
            if (elapsed >= period) {
                cout << "col=" << col << "/" << nr_columns << " (" << 100.*col/nr_columns << "% " << elapsed << " s)" << endl;
                period = (elapsed/PERIOD+1)*PERIOD;
            }
        }
    }
}

void State::process(Index col) {
    last_.fill(0);
    for (uint i=0; i<cols_; ++i) {
        Element bit = col >> i & 1;
        side[i] = bit;
        Element carry = 0;
        for (int j=0; j<ELEMENTS; ++j) {
            auto c = last_[j] % COL_FACTOR;
            last_[j] = last_[j] / COL_FACTOR + carry * ELEMENT_TOP;
            if (j == top_offset_ && bit) last_[j] += top_;
            carry = c;
        }
    }
    // cout << "col=" << col << ", value=" << last_ << "\n";
    extend(0);
}

void State::extend(uint row) {
    // cout << "Extend row " << row << " " << static_cast<int>(side[cols_+row-1]) << "\n";
    if (row >= MAX_ROWS) throw(range_error("row out of range"));

    // Execute subset sum. The new column is added to set {from} giving {to}
    // {sum} is the other set.
    auto const& set_from = sets[row];
    auto const& set_sum  = sets[row + 1];
    auto      & set_to   = sets[row + 2];
    if (set_to.size() == 0) {
        auto size = 3 * set_from.size() - 2;
        set_to.resize(size);
        for (int j=0; j<ELEMENTS; ++j)
            set_to[size-1][j] = static_cast<Element>(-1) - ELEMENT_FILL(1);
    }

    // Merge sort {set_from - last_} , {set_from} and {set_from + last_}
    auto ptr_sum    = &set_sum[1][0];
    auto ptr_low    = &set_from[0][0];
    auto ptr_middle = &set_from[0][0];
    auto ptr_high   = &set_from[0][0];
    Column col_low, col_high;
    for (int j=0; j<ELEMENTS; ++j) {
        col_low   [j] = *ptr_low++  - last_[j];
        col_high  [j] = *ptr_high++ + last_[j];
    }

    auto ptr_end = &set_to[set_to.size()-1][0];
    auto ptr_to  = &set_to[0][0];
    while (ptr_to < ptr_end) {
        for (int j=0; j<ELEMENTS; ++j) {
            if (col_low[j] < ptr_middle[j]) goto LOW;
            if (col_low[j] > ptr_middle[j]) goto MIDDLE;
        }
        // low == middle
        // cout << "low == middle\n";
        return;

      LOW:
        // cout << "LOW\n";
        for (int j=0; j<ELEMENTS; ++j) {
            if (col_low[j] < col_high[j]) goto LOW0;
            if (col_low[j] > col_high[j]) goto HIGH0;
        }
        // low == high
        // cout << "low == high\n";
        return;

      MIDDLE:
        // cout << "MIDDLE\n";
        for (int j=0; j<ELEMENTS; ++j) {
            if (ptr_middle[j] < col_high[j]) goto MIDDLE0;
            if (ptr_middle[j] > col_high[j]) goto HIGH0;
        }
        // middle == high
        // cout << "middle == high\n";
        return;

      LOW0:
        // cout << "LOW0\n";
        for (int j=0; j<ELEMENTS; ++j) {
            *ptr_to++  = col_low[j];
            col_low[j] = *ptr_low++ - last_[j];
        }
        goto SUM;

      MIDDLE0:
        // cout << "MIDDLE0\n";
        for (int j=0; j<ELEMENTS; ++j)
            *ptr_to++ = *ptr_middle++;
        goto SUM;

      HIGH0:
        // cout << "HIGH0\n";
        for (int j=0; j<ELEMENTS; ++j) {
            *ptr_to++ = col_high[j];
            col_high[j] = *ptr_high++ + last_[j];
        }
        goto SUM;
      SUM:
        for (int j=-ELEMENTS; j<0; ++j) {
            if (ptr_to[j] > ptr_sum[j]) {
                ptr_sum += ELEMENTS;
                goto SUM;
            }
            if (ptr_to[j] < ptr_sum[j]) goto DONE;
        }
        // sum == to
        for (int j=-ELEMENTS; j<0; ++j)
            if (ptr_to[j] != ELEMENT_FILL()) {
                // sum == to and to != 0
                // cout << "sum == to\n";
                // cout << set_sum[(ptr_sum - &set_sum[0][0])/ELEMENTS-1] << "\n";
                return;
            }
      DONE:;
    }
    // cout << "Wee\n";
    auto row1 = row+1;
    if (0)
        for (uint i=0; i<row1+2; ++i) {
            cout << "Set " << i << "\n";
            auto& set = sets[i];
            for (auto& column: set)
                cout << column << "\n";
        }

    if (row1 * ratio_col_ > ratio_row_ * cols_) {
        ratio_row_ = row1;
        ratio_col_ = cols_;
        lock_guard<mutex> lock{ratio_mutex};

        if (ratio_row_ * ratio_col > ratio_row * ratio_col_) {

            auto now = chrono::steady_clock::now();
            auto elapsed = chrono::duration_cast<sec>(now-start).count();
            cout << "cols=" << cols_ << ",rows=" << row1 << " (" << elapsed << " s)\n";
            print(row1);
            ratio_row = ratio_row_;
            ratio_col = ratio_col_;
        }
    }

    auto last = last_;

    Element carry = 0;
    for (int j=0; j<ELEMENTS; ++j) {
        auto c = last_[j] % COL_FACTOR;
        last_[j] = last_[j] / COL_FACTOR + carry * ELEMENT_TOP;
        carry = c;
    }

    side[cols_+row] = 0;
    extend(row1);

    last_[top_offset_] += top_;
    side[cols_+row] = 1;
    extend(row1);

    last_ = last;
}

void my_main(int argc, char** argv) {
    if (!col_next.is_lock_free()) cout << "col_next is not lock free\n";
    if (!period.  is_lock_free()) cout << "period is not lock free\n";

    int min_col = 2;
    int max_col = MAX_COLS;
    if (argc > 1) {
        min_col = atoi(argv[1]);
        if (min_col < 2)
            throw(range_error("Column must be >= 2"));
        if (min_col > MAX_COLS)
            throw(range_error("Column must be <= " + to_string(MAX_COLS)));
    }
    if (argc > 2) {
        max_col = atoi(argv[2]);
        if (max_col < min_col)
            throw(range_error("Column must be >= " + to_string(min_col)));
        if (max_col > MAX_COLS)
            throw(range_error("Column must be <= " + to_string(MAX_COLS)));
    }

    for (int cols = min_col; cols <= max_col; ++cols) {
        cout << "Trying " << cols << " columns" << endl;
        ratio_row = 0;
        ratio_col = 1;
        col_next = 0;
        period = PERIOD;
        start = chrono::steady_clock::now();
        vector<thread> threads;
        for (auto t = 1U; t < nr_threads; t++)
            threads.emplace_back(check, cols, t);
        check(cols, 0);
        for (auto& thread: threads)
            thread.join();
    }
}

int main(int argc, char** argv) {
    try {
        my_main(argc, argv);
    } catch(exception& e) {
        cerr << "Error: " << e.what() << endl;
        exit(EXIT_FAILURE);
    }
    exit(EXIT_SUCCESS);
}

```
> 6 votes

# Answer
# Haskell 14/8 = 1.75

```
1 1 0 0 0 1 0 1 1 0 1 1 0 0
1 1 1 0 0 0 1 0 1 1 0 1 1 0
0 1 1 1 0 0 0 1 0 1 1 0 1 1
1 0 1 1 1 0 0 0 1 0 1 1 0 1
0 1 0 1 1 1 0 0 0 1 0 1 1 0
0 0 1 0 1 1 1 0 0 0 1 0 1 1
0 0 0 1 0 1 1 1 0 0 0 1 0 1
0 0 0 0 1 0 1 1 1 0 0 0 1 0

```

## Previously 9/6 = 1.5

```
1 0 1 0 1 1 0 0 1
1 1 0 1 0 1 1 0 0
1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1
1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 0

```

I wrote this, then looked at the answers to the other question and was... discouraged.

```
import Data.List
import Data.Hashable
import Control.Monad
import Control.Parallel.Strategies
import Control.Parallel
import qualified Data.HashSet as S

matrix§indices = [ matrix!!i | i<-indices ]

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

hashNub :: (Hashable a, Eq a) => [a] -> [a]
hashNub l = go S.empty l
    where
      go _ []     = []
      go s (x:xs) = if x `S.member` s
        then go s xs
        else x : go (S.insert x s) xs

getMatrix :: Int -> Int -> [Int] -> [[Int]]
getMatrix width height vector = [ vector § [x..x+width-1] | x<-[0..height-1] ]

hasDuplicate :: (Hashable a, Eq a) => [a] -> Bool
hasDuplicate m = go S.empty m
    where
        go _ [] = False
        go s (x:xs) = if x `S.member` s
            then True
            else go (S.insert x s) xs

hasProperty :: [[Int]] -> Bool
hasProperty matrix =
    let
        base = replicate (length (matrix !! 0)) 0::[Int]
    in
        if elem base matrix then
            False
        else
            if hasDuplicate matrix then
                False
            else
                if hasDuplicate (map (foldl (zipWith (+)) base) (powerset matrix)) then
                    False
                else
                    True

pmap = parMap rseq

matricesWithProperty :: Int -> Int -> [[[Int]]]
matricesWithProperty n m =
    let
        base = replicate n 0::[Int]
    in
    filter (hasProperty) $
    map (getMatrix n m) $
    sequence [ [0,1] | x<-[0..n+m-1] ]

firstMatrixWithProperty :: Int -> Int -> [[Int]]
firstMatrixWithProperty n m = head $ matricesWithProperty n m

main = mapM (putStrLn. show) $ map (firstMatrixWithProperty 8) [1..]

```
> 2 votes

# Answer
# C

Here's an answer which works and is significantly more memory-efficient than the Haskell. Unfortunately, my computer is still too slow to achieve better than 14/8 in any reasonable length of time.

Try compiling with `gcc -std=c99 -O2 -fopenmp -o matrices.exe matrices.c` and running with `matrices.exe width height` or similar. The output is an integer, the bits of which form the basis for the matrix in question, for instance:

```
$ matrices.exe 8 14
...
valid i: 1650223

```

Then, since `1650223 = 0b110010010111000101111`, the matrix in question is:

```
0 0 1 1 1 0 1 0 0 1 0 0 1 1
0 ...
1 ...
0
1
1
1
1

```

If someone with 8 cores and time on their hands wants to run this for a while, I think some good things could result :)

---

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

/*
 * BEGIN WIKIPEDIA CODE
 */
const long long m1  = 0x5555555555555555; //binary: 0101...
const long long m2  = 0x3333333333333333; //binary: 00110011..
const long long m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const long long m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const long long m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const long long m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const long long hff = 0xffffffffffffffff; //binary: all ones
const long long h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
//This uses fewer arithmetic operations than any other known
//implementation on machines with fast multiplication.
//It uses 12 arithmetic operations, one of which is a multiply.
long long hamming(long long x) {
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
    return (x * h01)>>56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
/*
 * END WIKIPEDIA CODE
 */

int main ( int argc, char *argv[] ) {
    int height;
    int width;

    sscanf(argv[1], "%d", &height);
    sscanf(argv[2], "%d", &width);

    #pragma omp parallel for
    for (
        /*
         * We know that there are 2^(h+w-1) T-matrices, defined by the entries
         * in the first row and first column. We'll let the long long i
         * represent these entries, with 1s represented by set bits.
         *
         * The first (0) and last (1) matrix we will ignore.
         */
        long long i = 1;
        i < (1 << (height+width-1))-1;
        i++
    ) {
        // Flag for keeping track as we go along.
        int isvalid = 1;

        /*
         * Start by representing the matrix as an array of columns, with each
         * non-zero matrix entry as a bit. This allows us to construct them and
         * check equality very quickly.
         */
        long *cols = malloc(sizeof(long)*width);
        long colmask = (1 << height)-1;
        for (int j = 0; j < width; j++) {
            cols[j] = (i >> j) & colmask;
            if (cols[j] == 0) {
                //check no zero rows
                isvalid = 0;
            } else {
                //check no duplicate rows
                for (int k = 0; k < j; k++) {
                    if (cols[j] == cols[k]) {
                        isvalid = 0;
                    }
                }
            }
        }

        if (isvalid == 1) {
            /*
             * We'll also represent the matrix as an array of rows, in a
             * similar manner.
             */
            long *rows = malloc(sizeof(long)*height);
            long rowmask = (1 << width)-1;
            for (int j = 0; j < height; j++) {
                rows[j] = (i >> j) & rowmask;
            }

            int *sums[(1 << width)];
            for (long j = 0; j < 1<<width; j++) {
                sums[j] = (int*)malloc(sizeof(int)*height);
            }

            for (
                /*
                 * The powerset of columns has size 2^width. Again with the
                 * long; this time each bit represents whether the
                 * corresponding row is a member of the subset. The nice thing
                 * about this is we can xor the permutation with each row,
                 * then take the hamming number of the resulting number to get
                 * the sum.
                 */
                long permutation = 1;
                (isvalid == 1) && (permutation < (1 << width)-1);
                permutation ++
            ) {
                for (int j = 0; j < height; j++) {
                    sums[permutation][j] = hamming( rows[j] & permutation);
                }
                for (int j = permutation-1; (isvalid == 1) && (j > -1); j--) {
                    if (memcmp(sums[j], sums[permutation], sizeof(int)*height) == 0) {
                        isvalid = 0;
                    }
                }
            }

            for (long j = 0; j < 1<<width; j++) {
                free(sums[j]);
            }

            free(rows);

        }

        if (isvalid == 1) {
            printf ("valid i: %ld\n", i);
        }

        free(cols);
    }

    return 0;
}

```
> 1 votes

---
Tags: code-challenge, math, combinatorics, binary-matrix
---


# Question
Title: An optimization challenge with strange coins
You have `n` coins which each weigh either -1 or 1. Each is labelled from `0` to `n-1` so you can tell the coins apart. You have one (magic) weighing device as well. At the first turn you can put as many coins as you like on the weighing device which is able to measure both negative and positive weights and it will tell you exactly how much they weigh.

However, there is something really strange about the weighing device. If you put coins `x_1, x_2, ..., x_j` on the device the first time, then the next time you have to put coins `(x_1+1), (x_2+1) , ..., (x_j+1)` on the scale with the exception that you of course can't put on a coin numbered higher than `n-1`. Not only that, for every new weighing you get to choose if you also want to put coin `0` on the scale.

> Under this rule, what is the smallest number of weighings that will always tell you exactly which coins weigh 1 and which weigh -1?

Clearly you could just put coin `0` on the device in the first turn and then it would take exactly `n` weighings to solve the problem.

**Languages and libraries**

You can use any language or library you like (that wasn't designed for this challenge). However, I would like to be able to test your code if possible so if you can provide clear instructions for how to run it in Ubuntu that would be very much appreciated.

**Score**

For a given `n` your score is `n` divided by the number of weighings you need in the worst case. Higher scores are therefore better. There is no input to this puzzle but your goal is to find an `n` for which you can get the highest score.

If there is a tie, the first answer wins. In the extremely unlikely situation where someone finds a way to get an infinite score, that person wins immediately.

**Task**

Your task is simply to write code that gets the highest score. Your code will have to both choose an n cleverly and then also optimize the number of weighings for that `n`.

**Leading entries**

* 4/3 7/5 in **Python** by Sarge Borsch
* 26/14 in **Java** by Peter Taylor

# Answer
> 3 votes
# C++, Score ~~23/12~~ ~~25/13~~ ~~27/14~~ ~~28/14 = 2~~ 31/15

The solutions of Matrix property X revisited (or the Joy of X) are directly usable as solutions to this problem. E.g. the solution of 31 rows 15 columns:

```
1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0
1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1
1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0
1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1
0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1
0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0
0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0
1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1

```

row N represent which coins you put on the scale for measurement N. Whatever the results of the weighting you get, there is obviously some set of coin values that gives that weight. If there is another combination too (the solution is not unique) consider how they differ. You must replace a set of coins weighting `1` by coins weighting `-1`. This gives a set of columns that correspond to that flip. There is also set of coins weighting `-1` that you replace by `1`. That is another set of columns. Because the measurements do not change between the two solutions that means the column sums of the two sets must be the same. But the solutions to Matrix property X revisited (or the Joy of X) are exactly these matrices where such column sets do not exist, so there are no duplicates and each solution is unique.

Each actual set of measurements can be described by some `0/1` matrix. But even if some column sets sum to the same vectors it could be that signs of the candidate solution coin values do not exactly correspond to such a set. So I don't know if matrices such as the one above are optimal. But at least they provide a lower bound. So the possibility that 31 coins can be done in less that 15 measurements is still open.

Notice that this is only true for a non fixed strategy where your decision to put coin `0` on the scales depends on the result of the previous weightings. Otherwise you ***will*** have solutions where the signs of the coins correspond with the sets that have the same column sum.

# Answer
> 5 votes
## Score = 26/14 ~= 1.857

```
import java.util.*;

public class LembikWeighingOptimisation {

    public static void main(String[] args) {
        float best = 0;
        int opt = 1;
        for (int n = 6; n < 32; n+=2) {
            long start = System.nanoTime();
            System.out.format("%d\t", n);
            opt = optimise(n, n / 2 + 1);
            float score = n / (float)opt;
            System.out.format("%d\t%f", opt, score);
            if (score > best) {
                best = score;
                System.out.print('*');
            }
            System.out.format(" in %d seconds", (System.nanoTime() - start) / 1000000000);
            System.out.println();
        }
    }

    private static int optimise(int numCoins, int minN) {
        MaskRange.N = numCoins;
        Set<MaskRange> coinSets = new HashSet<MaskRange>();
        coinSets.add(new MaskRange(0, 0));

        int allCoins = (1 << numCoins) - 1;

        for (int n = minN; n < numCoins; n++) {
            for (int startCoins = 1; startCoins * 2 <= numCoins; startCoins++) {
                for (int mask = (1 << startCoins) - 1; mask < (1 << numCoins); ) {
                    // Quick-reject: in n turns, do we cover the entire set?
                    int qr = (1 << (n-1)) - 1;
                    for (int j = 0; j < n; j++) qr |= mask << j;
                    if ((qr & allCoins) == allCoins && canDistinguishInNTurns(mask, coinSets, n)) {
                        System.out.print("[" + Integer.toBinaryString(mask) + "] ");
                        return n;
                    }

                    // Gosper's hack to update
                    int c = mask & -mask;
                    int r = mask + c;
                    mask = (((r^mask) >>> 2) / c) | r;
                }
            }
        }

        return numCoins;
    }

    private static boolean canDistinguishInNTurns(int mask, Set<MaskRange> coinsets, int n) {
        if (n < 0) throw new IllegalArgumentException("n");
        int count = 0;
        for (MaskRange mr : coinsets) count += mr.size();
        if (count <= 1) return true;
        if (n == 0) return false;

        // Partition.
        Set<MaskRange>[] p = new Set[Integer.bitCount(mask) + 1];
        for (int i = 0; i < p.length; i++) p[i] = new HashSet<MaskRange>();
        for (MaskRange range : coinsets) range.partition(mask, p);

        for (int d = 0; d < 2; d++) {
            boolean ok = true;
            for (Set<MaskRange> s : p) {
                if (!canDistinguishInNTurns((mask << 1) + d, s, n - 1)) {
                    ok = false;
                    break;
                }
            }

            if (ok) return true;
        }

        return false;
    }

    static class MaskRange {
        public static int N;
        public final int mask, value;

        public MaskRange(int mask, int value) {
            this.mask = mask;
            this.value = value & mask;
            if (this.value != value) throw new IllegalArgumentException();
        }

        public int size() {
            return 1 << (N - Integer.bitCount(mask));
        }

        public void partition(int otherMask, Set<MaskRange>[] p) {
            otherMask &= (1 << N) - 1;

            int baseline = Integer.bitCount(value & otherMask);
            int variables = otherMask & ~mask;
            int union = mask | otherMask;
            partitionInner(value, union, variables, baseline, p);
        }

        private static void partitionInner(int v, int m, int var, int baseline, Set<MaskRange>[] p) {
            if (var == 0) {
                p[baseline].add(new MaskRange(m, v));
            }
            else {
                int lowest = var & (1 + ~var);
                partitionInner(v,          m, var & ~lowest, baseline, p);
                partitionInner(v | lowest, m, var & ~lowest, baseline + 1, p);
            }
        }

        @Override
        public String toString() {
            return String.format("(x & %x = %x)", mask, value);
        }
    }
}

```

Save as `LembikWeighingOptimisation.java`, compile as `javac LembikWeighingOptimisation.java`, run as `java LembikWeighingOptimisation`.

Many thanks to Mitch Schwartz for pointing out a bug in the first version of the quick-reject.

This uses some fairly basic techniques which I can't rigorously justify. It brute-forces, but only for starting weighing operations which use at most half of the coins: sequences which use more than half of the coins aren't directly transferable to the complementary weighings (because we don't know the total weight), but on a hand-wavy level there should be about the same amount of information. It also iterates through starting weighings in order of the number of coins involved, on the basis that that way it covers dispersed weighings (which hopefully give information about the top end relatively early) without first crawling through a bunch which start with a dense subset at the bottom end.

The `MaskRange` class is a massive improvement on the earlier version in terms of memory usage, and removes GC from being a bottleneck.

```
20      [11101001010] 11        1.818182* in 5364 seconds
22      [110110101000] 12       1.833333* in 33116 seconds
24      [1000011001001] 13      1.846154* in 12181 seconds
26      [100101001100000] 14    1.857143* in 73890 seconds

```

# Answer
> 4 votes
# Python 2, score = 1.0

This is the easy score, in case nobody finds a better score (doubtful). `n` weighings for each `n`.

```
import antigravity
import random

def weigh(coins, indices):
    return sum(coins[i] for i in indices)

def main(n):
    coins = [random.choice([-1,1]) for i in range(n)]
    for i in range(len(coins)):
        print weigh(coins, [i]),

main(4)

```

I imported `antigravity` so the program can work with negative weights.

# Answer
> 2 votes
## Python 3, ~~score = 4/3 = 1.33… (N = 4)~~ score = 1.4 (N = 7)

### Update: implemented brute-force search in "static" solvers set, and got a new result

I think it can be further improved by searching for dynamic solvers, which can use weighting results for further decisions.

Here is a Python code that searches through all static solvers for *small* `n` values (these solvers always weigh the same coin sets, hence "static" name) and determines their worst case number of steps by simply checking that their measurement results allow only one matching coin set in all cases. Also, it keeps track of best score found so far and early prunes solvers which had shown that they are definitely worse than those which were found before. This was an important optimization, otherwise I could not wait for this result with `n` = 7. (But it's clearly still not very well optimized)

Feel free to ask questions if it's not clear how it works…

```
#!/usr/bin/env python3
import itertools
from functools import partial

def get_all_possible_coinsets(n):
    return tuple(itertools.product(*itertools.repeat((-1, 1), n)))

def weigh(coinset, indexes_to_weigh):
    return sum(coinset[x] for x in indexes_to_weigh)

# made_measurements: [(indexes, weight)]
def filter_by_measurements(coinsets, made_measurements):
    return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), coinsets)

class Position(object):
    def __init__(self, all_coinsets, coinset, made_measurements=()):
        self.all_coinsets = all_coinsets
        self.made_measurements = made_measurements
        self.coins = coinset

    def possible_coinsets(self):
        return tuple(filter_by_measurements(self.all_coinsets, self.made_measurements))

    def is_final(self):
        possible_coinsets = self.possible_coinsets()
        return (len(possible_coinsets) == 1) and possible_coinsets[0] == self.coins

    def move(self, measurement_indexes):
        measure_result = (measurement_indexes, weigh(self.coins, measurement_indexes))
        return Position(self.all_coinsets, self.coins, self.made_measurements + (measure_result,))

def get_all_start_positions(coinsets):
    for cs in coinsets:
        yield Position(coinsets, cs)

def average(xs):
    return sum(xs) / len(xs)

class StaticSolver(object):
    def __init__(self, measurements):
        self.measurements = measurements

    def choose_move(self, position: Position):
        index = len(position.made_measurements)
        return self.measurements[index]

    def __str__(self, *args, **kwargs):
        return 'StaticSolver({})'.format(', '.join(map(lambda x: '{' + ','.join(map(str, x)) + '}', self.measurements)))

    def __repr__(self):
        return str(self)

class FailedSolver(Exception):
    pass

def test_solvers(solvers, start_positions, max_steps):
    for solver in solvers:
        try:
            test_results = tuple(map(partial(test_solver, solver=solver, max_steps=max_steps), start_positions))
            yield (solver, max(test_results))
        except FailedSolver:
            continue

def all_measurement_starts(n):
    for i in range(1, n + 1):
        yield from itertools.combinations(range(n), i)

def next_measurement(n, measurement, include_zero):
    shifted = filter(lambda x: x < n, map(lambda x: x + 1, measurement))
    if include_zero:
        return tuple(itertools.chain((0,), shifted))
    else:
        return tuple(shifted)

def make_measurement_sequence(n, start, zero_decisions):
    yield start
    m = start
    for zero_decision in zero_decisions:
        m = next_measurement(n, m, zero_decision)
        yield m

def measurement_sequences_from_start(n, start, max_steps):
    continuations = itertools.product(*itertools.repeat((True, False), max_steps - 1))
    for c in continuations:
        yield tuple(make_measurement_sequence(n, start, c))

def all_measurement_sequences(n, max_steps):
    starts = all_measurement_starts(n)
    for start in starts:
        yield from measurement_sequences_from_start(n, start, max_steps)

def all_static_solvers(n, max_steps):
    return map(StaticSolver, all_measurement_sequences(n, max_steps))

def main():
    best_score = 1.0
    for n in range(1, 11):
        print('Searching with N = {}:'.format(n))
        coinsets = get_all_possible_coinsets(n)
        start_positions = tuple(get_all_start_positions(coinsets))

        # we are not interested in solvers with worst case number of steps bigger than this
        max_steps = int(n / best_score)

        solvers = all_static_solvers(n, max_steps)
        succeeded_solvers = test_solvers(solvers, start_positions, max_steps)

        try:
            best = min(succeeded_solvers, key=lambda x: x[1])
        except ValueError:  # no successful solvers
            continue
        score = n / best[1]
        best_score = max(score, best_score)
        print('{}, score = {}/{} = {}'.format(best, n, best[1], score))
    print('That\'s all!')

def test_solver(start_position: Position, solver, max_steps):
    p = start_position
    steps = 0
    try:
        while not p.is_final():
            steps += 1
            if steps > max_steps:
                raise FailedSolver
            p = p.move(solver.choose_move(p))
        return steps
    except IndexError:  # solution was not found after given steps — this solver failed to beat score 1
        raise FailedSolver

if __name__ == '__main__':
    main()

```

## The output:

```
Searching with N = 1:
(StaticSolver({0}), 1), score = 1/1 = 1.0
Searching with N = 2:
(StaticSolver({0}, {0,1}), 2), score = 2/2 = 1.0
Searching with N = 3:
(StaticSolver({0}, {0,1}, {0,1,2}), 3), score = 3/3 = 1.0
Searching with N = 4:
(StaticSolver({0,1}, {1,2}, {0,2,3}, {0,1,3}), 3), score = 4/3 = 1.3333333333333333
Searching with N = 5:
Searching with N = 6:
Searching with N = 7:
(StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4
Searching with N = 8:
Searching with N = 9:
(I gave up waiting at this moment)

```

This line `(StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4` uncovers the best solver found. The numbers in `{}` braces are the indices of coins to put on weighting device at each step.

---
Tags: math, optimization, fewest-operations
---


title: Who's that PRNG?

text:
# Question
Title: Who's that PRNG?
Given a sequence of 625 32-bit unsigned integers (that is, in the range `[0, 2**32)`), output which of the following pseudorandom number generators generated the sequence:

1. Linear Congruential Generator
2. Xorshift
3. Mersenne Twister

Specifically, the C implementations of these three generators used for this challenge are as follows:

```
#include <stdint.h>

/* all code adapted from the sample implementations on the following Wikipedia pages:
     https://en.wikipedia.org/wiki/Linear_congruential_generator
     https://en.wikipedia.org/wiki/Xorshift
     https://en.wikipedia.org/wiki/Mersenne_Twister
*/

uint32_t lcg_seed;
uint32_t xor_x, xor_y, xor_z, xor_w;

void lcg_srand(uint32_t seed) {
    lcg_seed = seed;
}

uint32_t lcg(void) {
    lcg_seed = ((uint64_t) lcg_seed * 1103515245 + 12345) & ( (uint64_t) 0xFFFFFFFF  );
    return (uint32_t) lcg_seed;
}

void xorshift128_srand(uint32_t x, uint32_t y, uint32_t z, uint32_t w) {
    xor_x = x;
    xor_y = y;
    xor_z = z;
    xor_w = w;
}

uint32_t xorshift128(void) {
    uint32_t t = xor_x;
    t ^= t << 11;
    t ^= t >> 8;
    xor_x = xor_y; xor_y = xor_z; xor_z = xor_w;
    xor_w ^= xor_w >> 19;
    xor_w ^= t;
    return xor_w;
}

enum {
    // Assumes W = 32 (omitting this)
    N = 624,
    M = 397,
    R = 31,
    A = 0x9908B0DF,

    F = 1812433253,

    U = 11,
    // Assumes D = 0xFFFFFFFF (omitting this)

    S = 7,
    B = 0x9D2C5680,

    T = 15,
    C = 0xEFC60000,

    L = 18,

    MASK_LOWER = (1ull << R) - 1,
    MASK_UPPER = (1ull << R)
};

static uint32_t  mt[N];
static uint16_t  index;

// Re-init with a given seed
void mt_Initialize(const uint32_t seed) {
    uint32_t  i;

    mt[0] = seed;

    for ( i = 1; i < N; i++ ) {
        mt[i] = (F * (mt[i - 1] ^ (mt[i - 1] >> 30)) + i);
    }

    index = N;
}

static void mt_Twist() {
    uint32_t  i, x, xA;

    for ( i = 0; i < N; i++ ) {
        x = (mt[i] & MASK_UPPER) + (mt[(i + 1) % N] & MASK_LOWER);

        xA = x >> 1;

        if ( x & 0x1 )
            xA ^= A;

        mt[i] = mt[(i + M) % N] ^ xA;
    }

    index = 0;
}

// Obtain a 32-bit random number
uint32_t mt_ExtractU32() {
    uint32_t  y;
    int       i = index;

    if ( index >= N ) {
        mt_Twist();
        i = index;
    }

    y = mt[i];
    index = i + 1;

    y ^= (mt[i] >> U);
    y ^= (y << S) & B;
    y ^= (y << T) & C;
    y ^= (y >> L);

    return y;
}

```

## Rules

* Input and output may be in any unambiguous, consistent format. If you're not sure if a format would be allowed, feel free to ask.
* All inputs are guaranteed to match exactly one PRNG's output (there will never be a case where an input sequence matches none or more than one PRNG's output).

## Test Cases

Due to post length limits, only 3 test cases are included. A larger list of test cases can be found here. Note that the values are provided in hexadecimal.

```
[CEE63876, DE7E2E77, 54EC3AE4, 92DEBB4D, D0756602, EE9D3B13, 04A42150, 0FE8BF49, 2BD7E04E, BB96756F, B9B2027C, B5750705, 9DD5B35A, E23EF98B, D15ACA68, C1C40E81, 35ABAB26, 2DA1A367, 36462514, 3CA211BD, E79753B2, A49B0F03, B3EA7E80, 64630CB9, BC22F8FE, D535985F, 14B902AC, EE9EBB75, A831A70A, 79C55B7B, F7099D98, 98AC99F1, D9CB29D6, 53C43457, 04C6FB44, 43DFE42D, 05A80D62, D86DBEF3, F9DA87B0, 99839629, 017D9DAE, 0B1B574F, A5586EDC, F2966BE5, B709E6BA, A160196B, D16B9CC8, FF46E161, 3BDFB486, 4CE4E147, BE01BD74, 6A2F329D, 99F29312, C7044AE3, 9A373CE0, 73515B99, 94E2CE5E, FA26B23F, 2883470C, 3ED31855, 7809726A, 64DE335B, 79A3C7F8, 5379E4D1, B9444B36, 92C2AA37, 6A496BA4, 84E6FD0D, FC81E4C2, 470DB2D3, 4F839E10, 45935D09, C40D8B0E, B4F6A92F, FDEC8B3C, 1C8BC0C5, D99B4A1A, E1CEA94B, 17951F28, BAECA441, 3C13EDE6, 0CDC8F27, 4CB105D4, ED1E437D, 1E210272, B8F8F6C3, FB02AB40, 63D09A79, 4178D3BE, B3EA3C1F, 58073B6C, 10B76535, BAEA6DCA, 37807B3B, 11E2A258, 93061FB1, EB299C96, 00719017, 130B8C04, EFAC05ED, 385AEC22, F6F516B3, D4B76470, 915013E9, D45FA86E, C5206B0F, 6C06579C, 4C0D05A5, 9BE1DD7A, 7702A92B, 3DEF5188, E0ED5721, DA205746, 0080AD07, 05EBFE34, 3D27445D, 7D7AA1D2, 44F112A3, 9B64C9A0, 7118C959, 08BD091E, FC7835FF, A1DCDFCC, 1B03A215, 4D2C992A, 9324331B, 0FDE2CB8, C1894A91, B9531DF6, DDC8E5F7, 38A55C64, 59E6FECD, C88B2382, 409BEA93, C48DDAD0, F5F1BAC9, DF4BF5CE, A3909CEF, C43DD3FC, 55D23A85, A035A0DA, 5074190B, CA9233E8, D980FA01, 85DCF0A6, 96C93AE7, B94AA694, 0E02353D, 4D577132, D1649E83, AC759800, D261E839, 7D876E7E, 29C89FDF, 309C342C, D06FCEF5, 1727F48A, 35415AFB, AFAE6718, C53B6571, 3998CF56, 47C0ABD7, C0AEDCC4, D54FE7AD, 486A8AE2, 187A2E73, C61F0130, E8B051A9, DDAA732E, 143F3ECF, 072B005C, CA935F65, 94EE943A, 799AF8EB, 2F95C648, 88DF8CE1, 7B21BA06, 1AAE38C7, E264FEF4, 4F67161D, AF0F7092, 60CB9A63, CB4D1660, BAE3F719, 7EB003DE, EDD379BF, 5ADD388C, 5FB3EBD5, 0D347FEA, F74FF2DB, 196B5178, 00547051, 4DD2B0B6, 3750E1B7, 3CC00D24, AF9EC08D, DF512242, 0F07E253, EC82D790, DAC3D889, 1453208E, 372450AF, 6165DCBC, F7087445, 3464B79A, 19EF48CB, CB1208A8, 4F410FC1, C1C6B366, B327A6A7, A8D30754, 2D0DE6FD, 4FFA9FF2, 919E0643, 010344C0, 59D6F5F9, 370EC93E, 5690C39F, A337ECEC, B387F8B5, 2FAA3B4A, CEC7FABB, 612CEBD8, 510C6B31, A3D8C216, 81718797, EA70ED84, 728B896D, 4096E9A2, 50BD0633, B6D15DF0, 39644F69, 141DFDEE, 8837D28F, 2B86691C, E3E97925, 44F00AFA, 74E908AB, E71EFB08, 08DD82A1, 2DA3DCC6, 632D8487, E02CBFB4, 0EAEA7DD, 6970FF52, 9E53E223, C2B02320, DA72E4D9, 1D7BBE9E, CDF87D7F, B844514C, 72A3F595, 8AE126AA, CD21729B, 870B3638, 119B5611, B5830376, D71A9D77, B3597DE4, E3CE424D, AB93E102, A6119A13, 10229450, 6DC9B649, B9E30B4E, DF71C46F, EA24A57C, 55EE6E05, 98E88E5A, EA00388B, B9D49D68, 0DECE581, 5E913626, 09B7D267, 080A2814, 980158BD, C0CA8EB2, 5D652E03, F16BB180, 63EFC3B9, F4CEE3FE, 1A02A75F, 749A65AC, FFBFE275, 3731420A, 1FD45A7B, 771E3098, 183930F1, C8A974D6, C5442357, 2D11BE44, 051EEB2D, EBA00862, 737D9DF3, 4F8E7AB0, DD2C0D29, 2E7A48AE, 70CA264F, 4DD891DC, CDCF52E5, 0EA641BA, F4ACD86B, 654AEFC8, 32A73861, C066BF86, 61BE9047, 4C034074, A8BDF99D, A75F4E12, 4149E9E3, DA4DEFE0, 19859299, CBE0395E, 5CA7413F, DED22A0C, 7993BF55, 58F28D6A, 1058B25B, 097DDAF8, B71DFBD1, EF241636, B4E61937, 9931AEA4, 1435840D, 58135FC2, B97911D3, 382D1110, E8C35409, E6BBB60E, CC38F82F, 333A2E3C, 884427C5, 9081251A, 2C66E84B, F799F228, C7447B41, 8AFC78E6, 0239BE27, 83B008D4, 5C9C8A7D, FA873D72, 587A15C3, 366EDE40, 1A6C5179, FD87BEBE, 13DE4B1F, 29839E6C, BAD78C35, 207D08CA, 04267A3B, 02423558, BC81B6B1, 06CAE796, EAF87F17, E5514F04, 8ACA0CED, D445E722, 147BF5B3, F9165770, EDC78AE9, A37F536E, DDB63A0F, A2E17A9C, 7E04ECA5, 14D1387A, 44A6682B, 6AD9A488, 97FCAE21, C22A6246, 5E215C07, 32A88134, 0B550B5D, 239A5CD2, 4D6DB1A3, 2AE67CA0, 81DC0059, 309D741E, 199FC4FF, B346C2CC, 5A434915, CA28B42A, 7CB5B21B, 11833FB8, 729C6191, B975E8F6, 887354F7, AB089F64, 1E9485CD, CF8F9E82, BCFE4993, 2D624DD0, 4570B1C9, 719D20CE, ED39EBEF, D16676FC, 63C9A185, 9DEE7BDA, 0CE3580B, A52206E8, ED07D101, 35C87BA6, C46D69E7, 8884A994, 489F7C3D, 17F0AC32, 669CBD83, 48CCCB00, 670C9F39, 57F9597E, A3E3AEDF, 06B3972C, AA8EF5F5, 9E4D8F8A, 177E59FB, D358FA18, 9FA5FC71, 7CFD1A56, 8A4E9AD7, 2FEF9FC4, C14CEEAD, 454885E2, 87780D73, DC28F430, 44F6C8A9, A9ED1E2E, 9EBC0DCF, 1F61235C, AA4A4665, 3A30EF3A, 7095B7EB, 788B1948, 8A9DE3E1, 81AEC506, 6015E7C7, 60DC81F4, E433DD1D, 58E22B92, 867F3963, 8D39C960, DD362E19, B2736EDE, 44A208BF, DA621B8C, BA7292D5, F1439AEA, 8DF871DB, CFDB6478, 85D68751, 93387BB6, C98250B7, 659E5024, A0AB478D, BCC89D42, E4614153, 78824A90, 3D91CF89, F1474B8E, F2349FAF, 19697FBC, 7E3EDB45, 03F0929A, 773587CB, A32CDBA8, B0F6E6C1, 0DB53E66, 3812D5A7, 43480A54, E9CA2DFD, F3C6DAF2, 2B8D2543, 614577C0, F390ACF9, CAE3B43E, E9D2D29F, 10EA4FEC, 54A61FB5, 2362D64A, B59BF9BB, 7B227ED8, E3660231, 0A000D16, FB067697, E9ACB084, 2667906D, 4967E4A2, E031E533, E18650F0, 7C79C669, 3883A8EE, 439BA18F, 78178C1C, C85F6025, 218565FA, 443AC7AB, CF1F4E08, 1C4AD9A1, 0DB3E7C6, 2F5C3387, 635F42B4, A11A6EDD, 81F6BA52, 703E8123, 9A07D620, B5541BD9, 7822299E, DD6E0C7F, B8E4344C, FFE19C95, A10341AA, 7FE0F19B, 35464938, F28C6D11, BB2BCE76, AFD30C77, 05B2C0E4, F839C94D, 8A7E5C02, 2361F913, 624D0750, 4AE6AD49, BC7A364E, 4AE9136F, 2003487C, 2D63D505, C547695A, 171D778B, 927A7068, 04D1BC81, 8182C126, 04EA0167, A0BA2B14, 8DDC9FBD, 28C9C9B2, 0B0B4D03, 7898E480, 29B87AB9, DD06CEFE, C56BB65F, 0CE7C8AC, FEDD0975, E27CDD0A, FA3F597B, 4A5EC398, 6981C7F1, 4C93BFD6, 54E01257, AF488144, F7D9F22D, AB640362, F2697CF3, B1EE6DB0, EE108429, 0602F3AE, 1C14F54F, 21C4B4DC, 0E0439E5, 2D8E9CBA, 4B55976B, 6F5642C8, 1EC38F61, 34F9CA86, 53B43F47, 86F0C374, 6FC8C09D, 99980912, 4E6B88E3, AA10A2E0, 53F5C999, 6869A45E, A3C3D03F, 738D0D0C, 50506655, 6C27A86A, 4E2F315B, F283EDF8, 7A7E12D1, 300FE136, 33258837, 8805F1A4, 43000B0D, 6370DAC2, 2DC070D3, F3828410, A72F4B09, E9F5E10E, 2717472F, B9F3D13C, 86F88EC5, A4B3001A, 585B274B, D3CAC528, 9A585241, BFF103E6, 92B2ED27, 4D9B0BD4, 4296D17D, 11B97872, 28D734C3, 47871140, 33440879, D522A9BE, D66E5A1F, 7F6C016C, AEF3B335, CE5BA3CA, C128793B, 51CDC858, D3B94DB1, A3783296, 6F9B6E17, DD831204, 336413ED, F5FCE222, 51DED4B3, B6214A70, B37B01E9, 892AFE6E, 37E8090F, 51289D9C, 70F8D3A5, 810C937A, D1A6272B, 19EFF788, 23C80521, 86406D46] -> LCG
[7D17504D, 9FED269B, 939C3D03, C8FCFA6C, 0FAE4E06, F9816896, 8B872680, A4878206, D92436EE, 2B133084, 9912A040, 011D96D6, F976435D, 4B53DBE7, 474F626D, AA09E774, E12E35C3, 347746E2, 0817160B, EDC0623A, 7DD0D26C, F31ECB62, 43093C44, AD3657AD, 568EB3D5, 53CE27BD, 592FDA9C, 46BB652B, 65886632, 475956F1, 60859FBC, FD8A3CBA, DB156CCF, 56764782, 1A424A8F, B681CA91, C682BB9A, 222CBE9F, 2A329E67, 925F0CF2, 41D22B48, 064DBDAB, B832DAA3, D26069CB, 023890A4, 69F3D5AD, 473AFDF2, 96C5EAEF, 50BEF523, A7171C24, 3752B059, 8E79B6CE, 29C95DCF, 362092EE, 94523C0B, D7DE2789, B49A3F98, 861F7C07, 83A8BAAB, A56C2738, C06FAAF2, BDED09BC, 7B568148, BFC73CFD, 024229CD, D73760D0, 18A4E7BF, 9E021082, 8D1D4ECE, E1408E5D, DEE614D5, 50EE898B, 37E2D666, D23584A1, 3C9B628E, 181D1647, 396DA2C4, 470339C4, A06BACB8, 503439DC, 041BCA9C, 5A881EC2, A77B7747, 567040AD, 8CE52FD5, 96814E85, EA3CD25D, 3E9D929F, 9BA3891E, 07CA0989, 0B689D17, D9B3FF8F, 5EDF76DE, 090EBACD, 46C11EDE, 00C8DE0E, A504314F, D9A02FF0, 97D9EDF4, D1A769AF, 55ADB49D, 8DAACE77, D544247B, 3F44C56D, 07759744, DC7738AB, 28E4B8A2, 31927F7E, 9AF601BF, FF21C02A, F20D56C4, 50C6AE74, 7A17A62A, 8BC619D2, 13E5C518, 76357C1E, B1D4A204, 0A673565, 3797FC34, EA9FA354, FE4FF881, CDB03630, 454E05EE, 52DC8B10, D3D6FA3A, 9F9B57C6, AACF50AE, 1CFDCAEC, 789EE463, 3DFEA9D1, ED64C4E0, 1F3CD90A, 900E9B72, 58761883, 93FE94A9, 6AF3FB55, 8EC22872, 66988B29, 01A4008F, F4787ABD, 6B665DF8, C905527E, E88493A9, DF1EB196, 86CEBE10, 65BB9A15, A96E54D0, 83D6D26A, 701BC23E, C9C9951A, 12DA9027, 27AA5594, 890E696D, 0CEA5C13, CA77AE01, BF04442E, 45BB17A2, 1BEFD1C2, 6C9F7318, F1276F91, 6CBC7010, 09B8DD84, 9E286818, 54B9C7AB, DB0A01DC, 1491B3C4, C92471E6, 533A73F6, D8B59CAC, 41231BED, AB62F96E, 2B478A37, 5F63230F, 06C6A77D, BAD38742, ADD2B41D, EBEF81F3, D8212EBC, FEEE4B6D, C6A47AF1, 51D39BCF, 80560B87, 0C6F8DC3, E9F90D4D, 2439FE5E, 1403C36D, 647255BB, 45C0AF1D, AEE062F5, A4F2C4EF, 52DB8247, 12237746, BF79483D, 8D9E3681, 03D954CF, 0A498AB5, 7F041361, 0352083E, CAE45BB7, 8CBE7C7C, D37EE991, 40FE1838, A82FCA73, D70D1E96, F31B5787, 4394AE04, 953E8857, 2A78CDC8, 03F6006F, E5F46A9B, 84E93A42, 6813B19A, DB55318F, 9DB338CC, 50453A12, A52FCEE1, D7844A82, D3F57DE6, AA195820, 719AD344, 84BF57AF, FCDD1093, 9C658F70, 3BC26F4B, 45BE45B3, 51F39C1F, E15D875E, C9CD1409, 7EE9435E, B3373BF8, BE5D3DB7, 1F911B29, 2B565836, 21B44E5F, 76537F5B, E18C6AEB, 78820904, FBC776FD, 16836779, 94DA8C70, FC787DC6, 3CC88C2A, 317D9C65, 71842F36, 4E2DFA8D, 36FC86BE, EBBFAAB0, BB12D56E, 9ACAA913, 48D10582, 5E2DCC02, 73B9DB0C, BCF46659, 7CC99950, 4CB40717, F168D436, EEB1A2EC, DE82A573, 32E28D0B, 859C2605, E6595298, 2D3BDA1D, 0B978064, 6F5F231D, 43BE71FC, B0A6A0A4, 07858274, 91540E52, 21D5BC15, A4F39B0B, 8F4E3BC3, BE5992E6, 32E0A42C, 0AF34AB8, F49DF806, 86218AD1, B1D79FFD, 21E1A5F5, 3AA73407, B05A4680, BD7F0F01, 919DDB56, 9299C26E, F095F8FB, B5D7E6EF, CAEFDC68, 9639FDE9, C9349DF5, C3DEFAA2, 7766722D, 2EE91F9D, 435FF480, 77601DA3, 33D3FE78, 55A01A68, E9E71FA8, 9E1D8A32, 329187B7, 67B7A8D7, B67CE1D6, C442A131, 7A502A31, A07BC4BC, F158F334, 20C28F07, DB38288C, A5184973, 93EFCFB7, A761D07A, BD07F052, DA336550, 374C9BD6, 9E077F45, 1C0089B7, 5D587682, 0E99C4D4, ABC16F15, B39406EB, 2DE69A7D, ED994471, 4D802710, 5E30D315, 471C9FDC, 6081E182, 2C75F225, F40524C5, 5744A7E6, 38A6D17D, BBC1E896, 663FD027, 14363091, 1A152653, AE24F8DF, 3602BBD4, 9315B73D, 20813CB2, A9EADA7D, 8A15088F, B487EAAF, 9DCA3421, 620C2CD7, 407F0169, CB26495B, 07810722, 04E8F991, BC24C42C, 45B12E62, 4A0689E1, 0961D541, 93FE75E5, 5FF09BC6, 21C75858, 260B4AFC, 463A4285, 9DCFCF2F, 86D14156, FAF1A7DA, 6E4BFC6B, 8D1EF03A, 81C9CB3E, F67163AA, C7E871AB, BD0DD64C, 72526AE8, 0F433B3B, 8BA27651, 58CE6EDF, B92A4A04, AFA624F9, 372EDFA2, 1CBDF70E, F72CE4F7, 69339707, 28A1864C, DB5701D1, 4BCC4D10, BEB260C1, 9A0502BD, F93FC1A5, D0B2B75F, FD2B71E0, 4F899412, 48BC46AF, 0DF108A8, ABF3DC87, A8D9E4EF, 02FA4665, 87CBBADA, B2E95940, D5702D6E, 056990CB, DFAEE7D6, 2775863A, 733AC4E7, 3A9CED83, 92A42D51, 196B2D69, BCD3CF5F, 61FEDDB3, D283BA78, 92C3C524, B0484914, 27CC09EB, E8532710, 643535DB, 96C7D0A0, D10310C2, A019C655, 6D4FA460, C5A53BB9, 0CE9A6CF, 62ACE269, 72D026F8, 9E44A3E8, DFDAB131, DA60BF09, 2974A55B, 9294187E, 98CD6024, 478A1CC3, CB583714, F93D91E9, 0A0202AA, 1D796B2D, 17931F01, 023476C3, 1839337D, CECF1354, 412B769B, E0089213, 317BF7B4, 8798177C, 9D1D36BA, 3921B700, D70921C7, 906DEFAD, E4B1B3FC, D01C81DD, 4E858500, B16A1BFA, D82D7078, EC0B10C9, 8EC425CD, 6F904A24, DC8D591E, 68B4971E, C7F13D88, 2ADD8E38, 9C2E67D4, 50EE1F28, 1EBD75C0, D8D79461, 37285868, 171F16FA, E2F972AC, 86E9860E, F37765A3, 1C3015F1, 357568C9, FF66419F, B77479AD, 2B776D2F, B5DA7BA8, 787DBE35, 6CD01986, FC5E1F26, 9A3F3C3E, 0F26B55A, E3D68111, EF7D1562, 8CC01A7F, B676E2D8, E1FF230E, E62EEC56, 6AB1010E, 6BD04EA2, 732FF785, E2F2E9EA, 00A93DCB, E9E5C622, E57A9744, 90B28FB8, D9BCBF00, 1EAFA6C3, 2F5ED2E5, 2B9557F9, 17EDA934, 74178CB4, AD07B129, 2CAC11EF, 5672B947, 9EC8ED11, 0ED68918, 42B9C244, 81C2F3D5, 58BB2699, E29FFADF, 6EB8AF2A, F872A573, 797CDB0A, 64289FF8, CF42ADA8, A276D00E, 3D4DEBC1, 1DBA64CF, C74FA53D, D3ADEB7A, 81EC012D, 4FBE91C3, F562B344, 492860A9, A82CE5C8, 13A74987, F3BF2024, F9983BD2, 3655838C, 1F971FB0, 1523A266, 2D5D4DBB, B78EE27F, 104301A1, 187BA15D, DF8C077C, 1FD19BE8, 1797DFBA, D223E55C, 6D2BAF83, FEB67715, 57750D76, 9AB10BC1, AAD6F8A3, E7953C33, 1874830A, 0A896CC6, 17879ED4, 59BD4CB3, E56DF85D, A4C3576A, 8F990C18, 3CF2118C, B6D7A95F, 0811C0E8, 4FAFF43E, E37DF236, E8EB2257, 6E7BA922, 5E45AED7, 52A50B6B, E3ED62F2, 506CF514, 232CDAD8, 59A87385, D1DA70B0, E629FBCA, A39607CD, B9B87C61, BBE5C416, 12BB8F0B, 01004AFE, 7B2165CB, EE71DBCD, 207CD2DF, 23283B94, 53570D07, 33981B13, F5B4DD95, 9722AC2C, 7CF6B4FA, 8F4578F4, DC4E44FC, 5E8FD095, 9717EEDA, 3331A614, 9DF66D2A, BDDD0D79, 95944526, 2B2B5086, 059AF7F4, 507984FB, 67F346A7, 162D85BF, C4DAF5D9, 5818EFE5, A5235C3F, DF593559, CC3E6756, 53C6DEF3, ECBBB210, FA5EA123, C5656DE9, A03102F0, 912B0FD4, 9E73F36B, 7097CF69, 58996509, 91059461, 90ECC581, 5ECEBC72, CDEC2B8F, 70F708CF, 86C10B9D, ADC71A1B, 01DBEC7F, C9A22DFB, 47B14AB1, D233979E, 0C5521B3, D4401837, 196924CC, 57A8CF18, F25524E7, 26001B3A, 761F1472, 67DEC5A6, 3CF7A7A6, 1A08B2C9, 943A897E, 05589DAA, 8413C030, DBD2B481, 9BE3A7FC, 5A97CCE7, 409F95C5, 0EA757EB, 88FDCD84] -> Xorshift
[4BB6DADF, 8EEF8EA3, 06E8FD49, 88A2AF49, E3269CD4, ECA4F09A, 3ADC8EFB, AA4DD059, AC3B1AAE, DA22C244, B67C2EC6, DFD9C12F, B4A6DBAF, 354C372C, 2C6CA407, 0AC93693, 725C7716, B439DF25, 7C04626F, 67824F17, 21EE364D, 77D8D72F, 4BF90371, 7BC3C716, 472A4204, B842AEFE, 38270462, 3B17B189, 22760085, 2A801D85, 8DE334B5, A72580F7, F187AA9B, 2E04DC0C, 8A701C0D, 471B61E6, 98F859D9, 9EBC2F45, 02544E96, C2785B15, 20623FAB, 8001F9B4, 0E438545, CFA2A2A5, 9DA35720, BAA84901, 908758C8, FCF5557F, F905B3B4, BE7DEBCD, FED08B1E, 7E9472CB, AC3A29C1, 5BED194F, B6932F25, 1C95E32D, 67E94371, D7CCB4CE, DF296D87, 6AAEF0F6, 8CFFF867, 093F9F79, FB280F6C, DE7735A8, 684C17B5, A0DA757E, 374EC162, 1764A62D, 82C244F6, 9E4583C7, 56F02388, 0018E400, 815A0F1E, FD80C932, 30EDD175, D37AF8D8, 7C8E4633, 7D8E4E5D, 660A7F79, 4C2C08BD, B6656A5B, CCFD6607, B0AA17FA, 060EE305, DEE9752F, B38BE439, F04EB964, D4E6C330, DCD4F7AB, DF7D83BF, 309047C6, 51FFC819, 9E59C7D6, 46821973, 01B47792, F800809B, 6050BB64, C13CB495, A305F788, 7AD27279, B7F9151F, 9F154C4F, D3F688F1, FF830866, A9C059A3, FFBF160E, EA8D827A, 1F1DA6E8, FDC52EFC, 5325CE11, 765B86EB, A852DC5C, 74ADAF62, 45BFACA5, 8E1FF6C3, 83ADCF0A, 91D6626E, 316008CC, 0DAD4110, C28EA37D, 5F077B03, AF70C5E3, 13A7C50C, 0A737B9D, E236FCBB, DDADB0C5, F4CAA3C8, 73679470, 87AE2E8E, EAA6ADA4, F30CCA79, 2B2FED65, 9B55A25D, 7317A6DB, D505929C, 0F90C693, 5CED397C, C1CB0AB9, C81895F1, 828D68BF, C2D0D855, 70585D86, 1ACD41B1, D8227B76, 1CB6DD69, B71EF185, 3EB11656, 6674378A, BA543682, 895A464E, B9E6CC48, FDAB6657, AB815F3B, A717AF55, 5826ABAB, 7CAF7DA1, 33EB26C0, 9367A48F, 32334888, 6BD35F76, 21F56A13, B7E72B51, 2B110FC2, A7A6ED6F, 1B2E72D1, 855EC1F3, A320F92E, 05609603, 5AA26082, 937BB417, F7A082EF, 370690A8, 074B4C00, EFB2EF14, A449B9F8, 9AA7E8A8, 3AEC4108, E5DDDB2A, C2CC4D30, 8589EB3D, 030ED83E, 4230E9B3, 619B03C0, E2B2BB64, 839A7C40, 2527B162, D03987D6, F8D66424, B950968F, F41E4D21, 9BAEEC89, DB8C65CD, D19F0371, 42507672, F133D6DC, 8FF10301, 6267E094, 339A1D5D, 3DD9DDE3, 139AA839, 440F8A94, 5E10CEAF, 60A1BA78, 02576968, 9AE7D81E, B9BF647E, F1698EC1, 5EC4890B, 88CF1A87, 9F3442AD, 4ED7DB9A, 08BD20C4, DA4B2F8E, 7EE018A9, 41968817, 519BE32C, 26CC3EFD, 1C3CBCBB, 551FC090, D06676D9, 02BF4E3F, 5B331917, AA121020, 840B84DD, 1C04DB26, 42DC049A, 58E92781, 95DA8984, CEDFF185, 149A43E5, 9B4CAAE7, 9E61CFFC, C33F9485, 2ABFE975, 75F8E915, 167D7A60, 1086ABF9, FE0B87DC, 095EFA20, 79FC720C, 99DB743E, 8F4B2F19, 00A9188A, B5DE7C2D, DAF3734B, CCAD1F47, 0C9DB549, 0158D55C, BCD5F151, 72A210D9, ABB80C09, 99934B39, F92DF281, A35193BD, C3CB4E8B, 322DBEE4, 26E2E30D, 36F25EDD, F1C8C5DC, 44B5C836, 878075ED, 1140849C, DEBA2848, 6B8D4AD7, 0209883A, AEFFDC8B, F7862944, F2CAE4AB, 77A1EB21, C77D6350, 4749AA23, 1ECDFD3C, 55D6943C, FC9B102A, 80363E80, C28E5369, 7E4BDC16, 8DDD321E, 46E4B844, 71169596, 6EC788CA, 508E25D4, A3249379, C5493848, 67ECFFDB, F6B03518, D4FE2A7D, D6C8D739, 7A93EC17, 84E2A797, 08CB6F22, D09D5BFF, 7FF783FD, 749A4AA7, 9EE69739, 01BB87ED, CDB15087, 32FE625F, 3C8E72C6, 2386A26E, 0F243847, F9E50890, D10F1EC5, 6E1C032D, CE27B59B, 84F2447B, 62AFD23B, 2361B77C, 1532E2F5, BC65F691, D8106771, BC9F8553, 94B67790, CE7F4B32, E36DAA85, D42336C1, 414ABF42, F5D5E7FA, B17620A4, D42A5D6C, E1118425, 17C4B3F2, EBDCB06E, 1F8F7F65, 0AD89423, 32848E5D, 0A5028D0, 463B71B1, E896017F, C1DA750C, DB89FC54, AF665A17, 11F5A446, 45F2DD58, 9C66340A, F4DB1D19, 87AFFD89, 75CA495D, DE608110, 78EC9F5C, 7840FE7C, 6F4DA231, 1CF2E830, CD521794, CE4F5EBA, 79B79437, 5A91D18E, 95F1D139, D9CA1102, E3822EB3, F7C52D20, F917AEEE, 5EDCD7BF, 4BD3725C, 94EE3441, 713CF5DF, 937E1AA9, 08926562, 084E8DD4, 41100547, 1C706FF6, 2ED60298, 0D2E30BA, 82FECB1F, 831BCCE8, 0CB829DB, 0C522998, E0AD92F6, F8969EA4, 386650CD, CA41F763, 7BB34065, D79B9F81, 967FBB17, 7C2F61B2, 7B4E9B33, 8359EDDA, 3201D25E, 5F41BAA6, D94A1FD8, 6E29F112, EDB7885C, C4F4380D, DAD428C7, 40609A88, 66DF9A6C, D61B84E4, C4C77436, D6F4B201, 1C0AD2D4, 3A69D216, 1DD70F43, C887E79C, 8579D94E, F2D069EA, 17B4926F, 55BE153C, A783F442, C03D53D2, 5ED56627, C114DB61, 9B0BFD2C, 825DDE34, 97523F35, EE476E00, EB2ED50C, 567BB078, 9B70520D, DC96668B, FCFD7253, 0197E3F8, 7785825E, 0B00322C, B510F809, 51FB92EE, B6F7D331, 2DE0AC32, 00B41A7B, A432B1FE, 94ED9578, 4B56F086, F8BEADE1, 8C899DF2, EAB17808, 240BF736, 7CBA75E0, E06E352C, 3BBD94E5, 427CB86A, 31CB345E, C1226EE3, F9F4697B, 8820CBB6, C3F9BB4C, 509D403F, 03990E8E, 6C5CCD8B, 24F235C0, C5FC6E59, 05E627C9, 4B0C0C96, 45A35E8E, BBF14335, 89B957A1, 3E272204, EC501927, 00ADCBC3, 13DC9199, A682B338, BE42D97C, F97E0F28, 8C1A6128, 76ED6951, D7D8B74F, 80A6C9D2, 87111413, 48268EB5, 69DDA6F7, 8900B2E1, DBF809E0, D50D7B42, 9716581E, A7AE9B6E, 52366624, 85BAF9A3, DE28F70A, 890E37EC, 7F82541D, 9BA2C144, 8766E737, EA8B0E73, 6BC46E1A, 04A2D3E8, F01716BB, 3D0F7338, 93282BAA, 3A9E51C0, 7B26AFBD, FA2B6A90, 36DD5832, 18161A71, FDE783A2, FF84185B, C251868E, 957CA33D, 6D2BD402, F7E61B15, BAAD0068, 8413463A, 63F0F132, 55FBBC6A, 58E3298D, 845AA664, 02D242A7, A456CEED, 2C198D04, 89A25422, 3A4CABFB, 9D24D792, DFBB850F, 76E30332, 58B59723, 1B1A6913, 9FB961E8, B363CA07, 9CC01B66, 00E9E1DF, 9AF48078, F67167D2, 5D8EBE54, F0819D2D, A003D04B, BD20E32A, 7647BD73, DE509593, E381BF67, BB5D56E0, 675636A1, 983C7C47, C7D92CF8, 335F0477, A6EE6787, F2A67D0E, 29D7F83A, 3DA85C1F, 8E31E016, 5FBEB7EA, 01F017A9, 021B93ED, 8E2AE731, 3391B82D, 6AFEC318, C1E9610D, B50DE358, 46E16C1F, D7A03E8A, 74E52044, 4797BCBC, 49FC24BC, 119F71CB, 51ADB9AC, 1F7A8641, 373911A6, 79424584, 2D69A297, 32859E0B, FF812B02, 2060307E, 6AD9173E, AFCB84DA, 4F5B70D0, 34A63D93, 6DBD6388, BBD76CFA, 94EE5483, 20214C3F, E45B9B77, 8B3192D9, 109D8CE6, 8EBA320B, 53FA8CE2, 56A4A45A, 61AB8FDB, 3ABFD0EB, F92E5F91, 3CBA25FE, C2E19318, 2E5DC1D6, 751C25DB, 572BBA47, DF53AB19, 407F623F, EB9E4EE6, C98E9BFD, DA77A48F, 79D4B4D2, E4320563, 2C1C4BA4, CDCCD4A9, 5B74662F, 3B74B8C1, B1792883, 88D53BDA, FDFAB951, D2D3F844, 199D47E1, 7500E432, B0C714BD, EC5CCDCB, EC949808, 9B39D67F, 15D138B8, 17FE54A4, AD28C768, FE473BF7, AE29CB10, C987A478, EE50D094, 10ED5447, E2BF7CCF, BDD93708, D57E6C1B, 01079D4B, 6C6C547F, 363A37F3, 6D4D828A, EE1622DE, AF1D8240, B068E4C1, 9C5901F8, 17822119, 3C7837B0, DEFFD993, 28FA9C3A, EAADDC4E, 05705400, 0046CB17, E843346D, 2F33C418, AF1A47BD, E4C12B9E, BC3F9B15, 01E90C74, DE0C8A00, 5D52587A] -> MT

```

# Answer
# Jelly, 23 bytes

```
^Ḋṫ4^^æ«11$æ»31ż&2\ḂS<4

```

Takes an array of integers; returns **\[0, 1\]** for *LCG*, **\[1, 0\]** for *Xorshift*, and **\[0, 0\]** for *MT*.

Try it online! (The permalink might be too long for some browsers.)

### Background

The most random thing about the LCG is that it is considered a PRNG. For starters, the lower **k** bits of the state aren't affected by the higher **32 - k** bits, making it an exceptionally poor choice for most applications. In particular, the LSB of an updated state is only affected by the LSB of the previous one, and since **1103515245** and **12345** are both odd, the generated numbers will follow an even-odd-even-odd pattern.

The flaws of Xorshift are more subtle, but the generated bits still follow simple linear equations. Given five consecutive generated words **w<sub>k</sub>, w<sub>k+1</sub>, w<sub>k+2</sub>, w<sub>k+3</sub>, w<sub>k+4</sub>**, the (non-linear equation)
**w<sub>k+4</sub> = w<sub>k+3</sub> ⊕ w<sub>k+3</sub> \>\> 19 ⊕ w<sub>k</sub> ⊕ w<sub>k</sub> ≪ 11 ⊕ (w<sub>k</sub> ⊕ w<sub>k</sub> ≪ 11) ≫ 8** holds by definition. If we enumerate the bits of the words (**0** being the lowest, **31** being the highest), we can observe that the (linear) equation **w<sub>k,20</sub> ⊕ w<sub>k,31</sub> ⊕w<sub>k+3,31</sub> ⊕ w<sub>k+4,31</sub> = 0** holds. To verify this, it suffices to observe that words that have been shifted to the right cannot affect **w<sub>k+4,31</sub>**, the most significant bit of **w<sub>k+4</sub>**.

That leaves the Mersenne Twister. While there are better (faster, less biased, or both) PRNGs, identifying data generated by MT19937 is a lot more complicated than it was with LCG and Xorshift. Fortunately, we don't have to. If the data doesn't fit any of the two previous patterns, it was generated by the Mersenne Twister.

### How it works

```
^Ḋṫ4^^æ«11$æ»31ż&2\ḂS<4  Main link. Argument: A (array of integers)

 Ḋ                       Dequeue; drop the first integer.
^                        XOR the k-th element of A with the k-th element of the
                         previous result, effectively computing the XOR of all
                         neighboring integers in A.
  ṫ4                     Tail; drop the first three elements of the result.
    ^                    XOR the remaining integers with the corr. integers in A.
      æ«11$              Yield the integers in A, shifted 11 times to the left.
     ^                   XOR the results to both sides.
           æ»31          Shift all results 31 times to the right.
                &2\      Yield A, pairwise reduced by bitwise AND.
               ż         Zip the results to both sides.
                   Ḃ     Bit; compute their parities.
                    S    Sum; add the parities of the results left and right to ż.
                     <4  Compare the sums with 4.
                         This is necessary since A and the various modifications
                         with dropped elements have different lengths, which
                         introduces a few garbage values.

```
> 14 votes

---
Tags: code-golf, sequence, random, classification
---


title: Visualize an Array

text:
# Question
Title: Visualize an Array
Given an array of any depth, draw its contents with borders of `+-|` around each subarray. Those are the ASCII characters for plus, minus, and vertical pipe.

For example, if the array is `[1, 2, 3]`, draw

```
+-----+
|1 2 3|
+-----+

```

For a nested array such as `[[1, 2, 3], [4, 5], [6, 7, 8]]`, draw

```
+-----------------+
|+-----+---+-----+|
||1 2 3|4 5|6 7 8||
|+-----+---+-----+|
+-----------------+

```

For a ragged array such as `[[[1, 2, 3], [4, 5]], [6, 7, 8]]`, draw

```
+-------------------+
|+-----------+-----+|
||+-----+---+|6 7 8||
|||1 2 3|4 5||     ||
||+-----+---+|     ||
|+-----------+-----+|
+-------------------+

```

Notice that there is more space after drawing `[6, 7, 8]`. You may either draw the contents on the top-most, center, or bottom-most line, but whichever you choose, you must remain consistent.

This challenge was inspired by the box verb `<` from J.

## Rules

* This is so the shortest code wins.
* Builtins that solve this are not allowed.
* The input array will contain only nonnegative integer values or arrays. Each array will be homogenous, meaning that its elements will either by only arrays or only integers, but never a mix of both.
* Each subarray may be nested to any depth.
* The output may either by as a string or as an array of strings where each string is a line of output.

## Test Cases

```
[]
++
||
++

[[], []]
+---+
|+++|
|||||
|+++|
+---+

[[], [1], [], [2], [], [3], []]
+-----------+
|++-++-++-++|
|||1||2||3|||
|++-++-++-++|
+-----------+

[[[[[0]]]]]
+---------+
|+-------+|
||+-----+||
|||+---+|||
||||+-+||||
|||||0|||||
||||+-+||||
|||+---+|||
||+-----+||
|+-------+|
+---------+

[[[[[4, 3, 2, 1]]]], [[[3, 2, 1]]], [[2, 1]], [1]]
+---------------------------------+
|+-------------+---------+-----+-+|
||+-----------+|+-------+|+---+|1||
|||+---------+|||+-----+|||2 1|| ||
||||+-------+|||||3 2 1|||+---+| ||
|||||4 3 2 1|||||+-----+||     | ||
||||+-------+|||+-------+|     | ||
|||+---------+||         |     | ||
||+-----------+|         |     | ||
|+-------------+---------+-----+-+|
+---------------------------------+

```

# Answer
# Dyalog APL, 56 bytes

Thanks to ngn for helping removing about a third of the bytes.

```
{⍵≡∊⍵:⍉⍪⍉⍕⍵⋄(⊢,⊣/)⊃,/(1⊖('++','|'⍴⍨≢),'-'⍪⍣2↑)¨↓↑↓¨∇¨⍵}⊂

```

### TryAPL

Define the function, then run each test case and compare to the built-in `]Display` utility.
`[1, 2, 3]`
`[[1, 2, 3], [4, 5], [6, 7, 8]]`
`[[[1, 2, 3], [4, 5]], [6, 7, 8]]`
`[]`
`[[], []]`
`[[], [1], [], [2], [], [3], []]`
`[[[[[0]]]]]`
`[[[[[4, 3, 2, 1]]]], [[[3, 2, 1]]], [[2, 1]], [1]]`

# Explanation

Overall, this is an anonymous function `{...}` atop an enclose . The latter just adds another level of nesting prompting the former to add an outer frame.

The anonymous function with white-space ( is the statement separator):

```
{
    ⍵ ≡ ∊⍵: ⍉ ⍪ ⍉ ⍕ ⍵
    (⊢ , ⊣/) ⊃ ,/ (1 ⊖ ('++' , '|' ⍴⍨ ≢) , '-' ⍪⍣2 ↑)¨ ↓ ↑ ↓¨ ∇¨ ⍵
}

```

Here it is again, but with separated utility functions:

```
CloseBox ← ⊢ , ⊣/
CreateVertical ← '++' , '|' ⍴⍨ ≢
AddHorizontals ← 1 ⊖ CreateVertical , '-' ⍪⍣2 ↑
{
    ⍵ ≡ ∊⍵: ⍉ ⍪ ⍉ ⍕ ⍵
    CloseBox ⊃ ,/ AddHorizontals¨ ↓ ↑ ↓¨ ∇¨ ⍵
}

```

Now let me explain each function:

`CloseBox` takes a table and returns the same table, but with the table's first column appended on the right of the table. Thus, given the 1-by-3 table `XYZ`, this function returns the 1-by-4 table `XYZX`, as follows:
the argument (lit. what is on the right)
`,` prepended to
`⊣/` the leftmost column (lit. the left-reduction of each row)

`CreateVertical` takes a table and returns the a string consisting of the characters which would fit `|`s on the sides of the table, but with two `+`s prepended to match two rows of `-`. Eventually the table will be cyclically rotated one row to get a single `+---...` row above and below. Thus, given any three row table, this function returns `++|||`, as follows:
`'++' ,` two pluses prepended to
`'|' ⍴⍨` a stile reshaped by
the (rows') tally of the argument

`AddHorizontals` takes a list-of-lists, makes it into a table, adds two rows of `-`s on top, adds the corresponding left edge characters on the left, then rotates one row to the bottom, so that the table has a border on the top, left, and bottom. As follows:
`1 ⊖` rotate one row (the top row goes to the bottom) of
`CreateVertical ,` the string `++|||...` prepended (as a column) to
`'-' ⍪⍣2` minus added twice to the top of
the argument transformed from list-of-lists to table

`{`The anonymous function`}`: If the argument is a simple (not nested) list, make it into a character table (thus, given the 3-element list `1 2 3`, this function returns the visually identical 1-by-five character table `1 2 3`). If the argument is not a simple list, ensure the elements are simple character tables; pad them to equal height; frame each on their top, bottom, and left; combine them; and finally take the very first column and add it on the right. As follows:
`{` begin the definition of an anonymous function
`⍵ ≡ ∊⍵:` if the argument is identical to the flattened argument (i.e. it is a simple list), then:
transpose the
columnized
transposed
`⍕ ⍵` stringified argument; else:
`CloseBox` Add the leftmost column to the right of
`⊃ ,/` the disclosed (because reduction encloses) concatenated-across
`AddHorizontals¨` add `-`s on top and bottom of each of
`↓ ↑ ↓¨` the padded-to-equal-height\* of
`∇¨ ⍵` this anonymous function applied to each of the arguments
`}` end the definition of the anonymous function
* Lit. make each table into a list-of-lists, combine the lists-of-lists (padding with empty strings to fill short rows) into a table, then split the table into a list of lists-of-lists
> 4 votes

# Answer
## JavaScript (ES6), ~~223~~ 203 bytes

```
f=(a,g=a=>a[0].map?`<${a.map(g).join`|`}>`:a.join` `,s=g([a]),r=[s],t=s.replace(/<[ -9|]*>|[ -9]/g,s=>s[1]?s.replace(/./g,c=>c>`9`?`+`:`-`):` `))=>t<`+`?r.join`\n`.replace(/<|>/g,`|`):f(a,g,t,[t,...r,t])

```

Port of @MitchSchwartz's Ruby solution. Previous version which worked by recursively wrapping the arrays (and therefore worked for arbitrary content, not just integers):

```
f=(...a)=>a[0]&&a[0].map?[s=`+${(a=a.map(a=>f(...a))).map(a=>a[0].replace(/./g,`-`)).join`+`}+`,...[...Array(Math.max(...a.map(a=>a.length)))].map((_,i)=>`|${a.map(a=>a[i]||a[0].replace(/./g,` `)).join`|`}|`),s]:[a.join` `]

```

Note: Although I'm using the spread operator in my argument list, to obtain the desired output, provide a single parameter of the original array rather then trying to spread the array; this has the effect of wrapping the output in the desired outer box. Sadly the outer box costs me 18 bytes, and space-separating the integers costs me 8 bytes, otherwise the following alternative visualisation would suffice for 197 bytes:

```
f=a=>a.map?[s=`+${(a=a.map(f)).map(a=>a[0].replace(/./g,`-`)).join`+`}+`,...[...Array(Math.max(0,...a.map(a=>a.length)))].map((_,i)=>`|${a.map(a=>a[i]||a[0].replace(/./g,` `)).join`|`}|`),s]:[``+a]

```
> 7 votes

# Answer
## Brainfuck, 423 bytes

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

```

Formatted with some comments:

```
->>+>>,
[
  [>+>+<<-]
  +++++[>--------<-]
  >
  [
    not open paren
    <+>-
    [
      not paren
      [-]<-
    ]
  ]
  >
  [
    paren
    [-]
    <<
    [
      close paren
      >>>>+<<<<
      <<-<[>-<-]>>>
      -
    ]
    <<<
    [
      open paren directly after close paren
      -<<<<<<-<
    ]
    >+>>>
  ]
  <<<[>>+>>>>>+<<<<<<<-]>>>
  >>>>>>,
]
<<+
[
  <<,++>
  [
    -
    [
      >++<
      ,<+[--<<<<<<<+]
      >
    ]
  ]
  <[-<+]
  ->>>>
  [
    <++<<[>>>>>>>+<<<<<<<-]>>>-
    [
      at or before border
      <++>-
      [
        before border
        >>>>+<<<<
        <++<
      ]
      <[<<]
      >
    ]
    <
    [
      after border
      >>+<<
      <<
    ]
    >>>+>+>
    [
      column with digit or space
      <<<-<
    ]
    <[<<]
    >>>>->+>
    [
      middle or bottom
      -
      [
        bottom
        <-<-
        [
          at or before border
          -
          [
            before border
            <
          ]
          <
          [
            at border
            <++<<
          ]
          >
        ]
        <
        [
          after border
          <++++<<
        ]
        >
      ]
      <
      [
        middle
        >+<
        -[.<<<,<]
        <[<<]
      ]
      >
    ]
    <[-<<<<<]
    >>
    [
      border char or space
      -
      [
        not space
        <+>---
        [
          not plus
          <<++>>
          +
          [
            --
            [
              -
              [
                pipe
                <+++++++<++>>,
              ]
            ]
          ]
        ]
      ]
      <+++[<+++++++++++>-]<-.,>>
    ]
    > >>>+>>>>
  ]
  <<-
]

```

Try it online.

Expects input formatted like `(((((4 3 2 1))))(((3 2 1)))((2 1))(1))` with a trailing newline, and produces output of the form:

```
+---------------------------------+
|+-------------+---------+-----+-+|
||+-----------+|+-------+|+---+| ||
|||+---------+|||+-----+|||   || ||
||||+-------+|||||     ||||   || ||
|||||4 3 2 1||||||3 2 1||||2 1||1||
||||+-------+|||||     ||||   || ||
|||+---------+|||+-----+|||   || ||
||+-----------+|+-------+|+---+| ||
|+-------------+---------+-----+-+|
+---------------------------------+

```

The basic idea is to calculate which character to print based on the depth of nesting. The output format is such that the row index of a box's top border is equal to the corresponding array's depth, with symmetry across the middle row.

The tape is divided into 7-cell nodes, with each node representing a column in the output.

The first loop consumes the input and initializes the nodes, keeping track of depth and whether the column corresponds to a parenthesis (i.e., whether the column contains a vertical border), and collapsing occurrences of `)(` into single nodes.

The next loop outputs one row per iteration. Within this loop, another loop traverses the nodes and prints one character per iteration; this is where most of the work takes place.

During the initialization loop, the memory layout of a node at the beginning of an iteration is

`x d 0 c 0 0 0`

where `x` is a boolean flag for whether the previous char was a closing parenthesis, `d` is depth (plus one), and `c` is the current character.

During the character printing loop, the memory layout of a node at the beginning of an iteration is

`0 0 d1 d2 c p y`

where `d1` indicates depth compared with row index for top half; `d2` is similar to `d1` but for bottom half; `c` is the input character for that column if digit or space, otherwise zero; `p` indicates phase, i.e. top half, middle, or bottom half; and `y` is a flag that gets propagated from left to right, keeping track of whether we have reached the middle row yet. Note that since `y` becomes zero after processing a node, we can use the `y` cell of the previous node to gain more working space.

This setup allows us to avoid explicitly calculating the max depth during the initialization phase; the `y` flag is back-propagated to update the `p` cells accordingly.

There is a `-1` cell to the left of the nodes to facilitate navigation, and there is a cell to the right of the nodes that keeps track of whether we have printed the last row yet.
> 4 votes

# Answer
# Ruby, 104 bytes

```
->s{r=s=s.gsub'}{',?|
r=[s,r,s]*$/while s=s.tr('!-9',' ').gsub!(/{[ |]*}/){$&.tr' -}','-+'}
r.tr'{}',?|}

```

Anonymous function that expects a string. For example, `{{{{{4 3 2 1}}}}{{{3 2 1}}}{{2 1}}{1}}` produces

```
+---------------------------------+
|+-------------+---------+-----+-+|
||+-----------+|         |     | ||
|||+---------+||+-------+|     | ||
||||+-------+||||+-----+||+---+| ||
|||||4 3 2 1||||||3 2 1||||2 1||1||
||||+-------+||||+-----+||+---+| ||
|||+---------+||+-------+|     | ||
||+-----------+|         |     | ||
|+-------------+---------+-----+-+|
+---------------------------------+

```

You can use this code for testing:

```
f=->s{r=s=s.gsub'}{',?|
r=[s,r,s]*$/while s=s.tr('!-9',' ').gsub!(/{[ |]*}/){$&.tr' -}','-+'}
r.tr'{}',?|}

a=[]

a<<'[1, 2, 3]'
a<<'[[1, 2, 3], [4, 5], [6, 7, 8]]'
a<<'[[[1, 2, 3], [4, 5]], [6, 7, 8]]'
a<<'[]'
a<<'[[], []]'
a<<'[[], [1], [], [2], [], [3], []]'
a<<'[[[[[0]]]]]'
a<<'[[[[[4, 3, 2, 1]]]], [[[3, 2, 1]]], [[2, 1]], [1]]'

a.map{|s|s.gsub! '], [','}{'
s.tr! '[]','{}'
s.gsub! ',',''
puts s
puts f[s],''}

```

This starts from the middle row and works outwards. First, instances of `}{` are replaced with `|`. Then, while there are still braces, all innermost `{...}` strings are transformed into the appropriate `+-` sequences while characters other than `|{}` are turned into spaces. At the end, the intermediate braces are turned into pipes.
> 3 votes

# Answer
# Ruby, ~~245~~ 241 bytes

The overhead needed to wrap everything in boxes as well as align everything is pretty heavy...

Outputs arrays of strings, with one string per line, as per the spec. Bottom-aligned instead of the top-aligned sample test cases because it saves 1 byte.

Try it online!

```
V=->a{a==[*a]?(k=a.map(&V);k[0]==[*k[0]]?[h=?++?-*((k.map!{|z|z[1,0]=[' '*~-z[0].size+?|]*(k.map(&:size).max-z.size);z};f=k.shift.zip(*k).map{|b|?|+b.reduce{|r,e|r+e[1..-1]}+?|})[0].size-2)+?+,*f,h]:[h="+#{?-*(f=k*' ').size}+",?|+f+?|,h]):a}

```
> 2 votes

# Answer
# PHP+HTML, not competing (~~170~~ ~~141~~ ~~135~~ 130 bytes)

saved 29 bytes inspired by SteeveDroz

```
<?function p($a){foreach($a as$e)$r.=(is_array($e)?p($e):" $e");return"<b style='border:1px solid;float:left;margin:1px'>$r</b>";}

```

not competing because it´s no ascii output and because I let the browser do all the interesting work
> 2 votes

# Answer
# JavaScript (ES6), 221

A non recursive function returning an array of strings (still using a recursive subfunction inside)

```
a=>[...(R=(a,l)=>a[r[l]='',0]&&a[0].map?'O'+a.map(v=>R(v,l+1))+'C':a.join` `)([a],l=-1,r=[],m='')].map(c=>r=r.map(x=>x+v[(k<0)*2+!k--],k=l,1/c?v='-- ':(v='-+|',c>'C'?k=++l:c>','&&--l,c='|'),m+=c))&&[...r,m,...r.reverse()]

```

This works in 2 steps.

Step 1: recursively build a string representation of the nested input array. Example:

`[[[1, 2, 3], [],[4, 5]], [6, 7, 8]]` -\> `"OOO1 2 3,,4 5C,6 7 8CC"`

`O` and `C` mark open and close subarray. Simple numeric subarrays are rendered with the elements separated by space, while if array members are subarrays they are separated by commas. This string keeps track of the multilevel structure of the input array, while I can get the middle row of the output just replacing `OC,` with `|`. While recursively building this temp string, I also find the max depth level and initialize an array of empty strings that will contain the half top part of the output.
Note: the outer box is tricky, I nest the input inside another outer array, then I have drop the first row of output that is not needed

Step 2: scan the temp string and build the output

Now I have an array of empty strings, one for each level. I scan the temp string, keeping track of the current level, that increases for each `O` and decreases for each `C`. I visualize this like that:

```
[[[1, 2, 3], [],[4, 5]], [6, 7, 8]]

OOO1 2 3,,4 5C,6 7 8CC
+                    +
 +            +     +
  +     ++   +
|||1 2 3||4 5||6 7 8||

```

The plus the goes up and down follow the current level

For each char, I add a character to every row of output, following the rules:
\- if digit or space, put a '-' at the current level and below, put a space above
\- else, put a '+' at the current level, put a '-' if below and put a '|' if above

```
OOO1 2 3,,4 5C,6 7 8CC
+--------------------+
|+------------+-----+|
||+-----++---+|     ||
|||1 2 3||4 5||6 7 8||

```

During the temp scan, I also build the middle row replacing `OC,` with `|`

At the end of this step, I have the top half and the middle row, I only have to mirror the top to get the bottom half and I'm done

*Less golfed, commented code*

```
a=>{
   r = []; // output array
   R = ( // recursive scan function
     a, // current subarray
     l  // current level
   ) => (
     r[l] = '', // element of r at level r, init to ""
     a[0] && a[0].map // check if it is a flat (maybe empty) array or an array of arrays
     ? 'O'+a.map(v=>R(v,l+1))+'C' // mark Open and Close, recurse
     : a.join` ` // just put the elements space separated
   );
   T = R([a],-1)]; // build temp string
   // pass the input nested in another array
   // and start with level -1 , so that the first row of r will not be visible to .map

   // prepare the final output
   m = '' // middle row, built upon the chars in T
   l = -1 // starting level
   [...T].map(c => // scan the temp string
         {
            k = l; // current level
            1/c // check if numeric or space
             ? v = '-- ' // use '-','-',' '
             : (
                 v = '-+|', // use '-','+','|'
                 c > 'C'
                   ? k=++l // if c=='O', increment level and assign to k
                   : c>'A'&&--l, // if c=='C', decrement level (but k is not changed)
                 c='|' // any of O,C,comma must be mapped to '|'
               );
            m += c; // add to middle row
            r = r.map( (x,i) => // update each output row
                       // based on comparation between row index and level
                       // but in golfed code I don't use the i index
                       // and decrement l at each step
                       x + v[(k<i)*2+!(k-i)]
                     )
         })
   // almost done!
   return [...r,m,...r.reverse()]

```

)

**Test**

```
F=
a=>[...(R=(a,l)=>a[r[l]='',0]&&a[0].map?'O'+a.map(v=>R(v,l+1))+'C':a.join` `)([a],l=-1,r=[],m='')].map(c=>r=r.map(x=>x+v[(k<0)*2+!k--],k=l,1/c?v='-- ':(v='-+|',c>'C'?k=++l:c>','&&--l,c='|'),m+=c))&&[...r,m,...r.reverse()]

out=x=>O.textContent = x+'\n'+O.textContent

;[[1,2,3]
,[[[1, 2, 3], [4, 5]], [6, 7, 8]]
,[]
,[[], []]
,[[], [1], [], [2], [], [3], []]
,[[[[[0]]]]]
,[[[[[4, 3, 2, 1]]]], [[[3, 2, 1]]], [[2, 1]], [1]]
].forEach(t=>
  out(JSON.stringify(t)+'\n'+F(t).join`\n`+'\n')
)

function update()
{
  var i=eval(I.value)
  out(JSON.stringify(i)+'\n'+F(i).join`\n`+'\n')
}

update()
```

```
#I { width:90%}
```

```
<input id=I value='[[[1, 2, 3], [],[4, 5]], [6, 7, 8]]' oninput='update()'>
<pre id=O></pre>
```
> 2 votes

# Answer
# PHP, 404 Bytes

All solutions works with maximum depth of the array lesser then 10. for greater values the depth must store in an array and not in a string.

```
<?foreach(str_split(json_encode($_GET[a]))as$j){$j!="]"?:$c--;$r=($j==",")?($l=="]"?"":" "):$j;$r=$r=="]"?"|":$r;$r=$r=="["?($v=="]"?"":"|"):$r;if($r!=""){$n.=$r;$d.=+$c;}$v=$l;$l=$j;$j!="["?:$c++;$m>=$c?:$m=$c;}for($x=0;$x<strlen($n);$x++)for($y=0;$y<$m;$y++)$z[$y].=$y==$d[$x]&&$n[$x]=="|"?"+":($y<$d[$x]?"-":($y>$d[$x]&&$n[$x]=="|"?"|":" "));echo join("\n",$z),"\n$n\n".(join("\n",array_reverse($z)));

```

Expanded

```
foreach(str_split(json_encode($_GET[a]))as$j){ # split JSON representation of the array
    $j!="]"?:$c--;
    $r=($j==",")?($l=="]"?"":" "):$j;
    $r=$r=="]"?"|":$r;
    $r=$r=="["?($v=="]"?"":"|"):$r;
    if($r!=""){
      $n.=$r;  # concanate middle string
      $d.=+$c; # concanate depth position
    }
    $v=$l;
    $l=$j;
    $j!="["?:$c++;
    $m>=$c?:$m=$c; # maximum depth of the array
}
for($x=0;$x<strlen($n);$x++)for($y=0;$y<$m;$y++)
$z[$y].=$y==$d[$x]&&$n[$x]=="|"?"+":($y<$d[$x]?"-":($y>$d[$x]&&$n[$x]=="|"?"|":" "));
# Build the strings before the middle string dependent of value middle string and depth
echo join("\n",$z),"\n$n\n".(join("\n",array_reverse($z))); #Output

```

## for 425 Bytes we can make this with REGEX

```
<?$n=($p=preg_filter)("#\]|\[#","|",$r=$p("#\],\[#","|",$p("#,(\d)#"," $1",json_encode($_GET[a]))));preg_match_all("#.#",$r,$e,256);foreach($e[0] as$f){$f[0]!="]"&&$f[0]!="|"?:$c--;$d.=+$c;$f[0]!="|"&&$f[0]!="["?:$c++;$m>=$c?:$m=$c;}for($x=0;$x<strlen($n);$x++)for($y=0;$y<$m;$y++)$z[$y].=$y==$d[$x]&&$n[$x]=="|"?"+":($y<$d[$x]?"-":($y>$d[$x]&&$n[$x]=="|"?"|":" "));echo join("\n",$z),"\n$n\n".(join("\n",array_reverse($z)));

```

Expanded

```
$r=preg_filter("#\],\[#","|",preg_filter("#,(\d)#"," $1",json_encode($_GET[a])));
preg_match_all("#.#",$r,$e,256);
$n=preg_filter("#\]|\[#","|",$r); # concanate middle string
foreach($e[0] as$f){
    $f[0]!="]"&&$f[0]!="|"?:$c--;
    $d.=+$c; concanate depth position
    $f[0]!="|"&&$f[0]!="["?:$c++;
    $m>=$c?:$m=$c; # maximum depth of the array
}
# similar to the other ways
for($x=0;$x<strlen($n);$x++)
for($y=0;$y<$m;$y++)
$z[$y].=$y==$d[$x]&&$n[$x]=="|"?"+":($y<$d[$x]?"-":($y>$d[$x]&&$n[$x]=="|"?"|":" "));
echo join("\n",$z),"\n$n\n".(join("\n",array_reverse($z)));

```

## 455 Bytes for a recursive solution

```
<?function v($x,$t=0,$l=1){global$d;$d.=$t;$s="|";$c=count($x);foreach($x as$k=>$v){if(is_array($v))$e=v($v,$t+1,$k+1==$c);else{$e=$v." "[$k+1==$c];$d.=str_pad("",strlen($e),$t+1);}$s.=$e;}$d.=$l?$t:"";$s.=$l?"|":"";return$s;}$n=v($_GET[a]);$m=max(str_split($d));for($x=0;$x<strlen($n);$x++)for($y=0;$y<$m;$y++)$z[$y].=$y==$d[$x]&&$n[$x]=="|"?"+":($y<$d[$x]?"-":($y>$d[$x]&&$n[$x]=="|"?"|":" "));echo join("\n",$z),"\n$n\n".(join("\n",array_reverse($z)));

```

Expanded

```
function v($x,$t=0,$l=1){
    global$d; # concanate depth position
    $d.=$t;
    $s="|";
    $c=count($x);
    foreach($x as$k=>$v){
        if(is_array($v)){$e=v($v,$t+1,$k+1==$c);}
        else{$e=$v." "[$k+1==$c];$d.=str_pad("",strlen($e),$t+1);}
        $s.=$e;
    }
    $d.=$l?$t:"";
    $s.=$l?"|":"";
    return$s;
}
$n=v($_GET[a]); # concanate middle string
$m=max(str_split($d)); # maximum depth of the array
# similar to the other ways
for($x=0;$x<strlen($n);$x++)
for($y=0;$y<$m;$y++)
$z[$y].=$y==$d[$x]&&$n[$x]=="|"?"+":($y<$d[$x]?"-":($y>$d[$x]&&$n[$x]=="|"?"|":" "));
echo join("\n",$z),"\n$n\n".(join("\n",array_reverse($z)));

```
> 1 votes

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


# Question
Title: Add comments to a Python script and make it a bilingual Python/C++ “program”
Given the following Python 3 script:

```
def greet():
    print("Hello, world!")

greet()

```

***Prepend*** some lines to this text file so that it can be both executed as a Python program as well as compiled and run as a C++ program producing the same output **Hello, world!** (including the newline at the end):

```
$ python3 bilingual.py.cpp
Hello, world!
$ g++ bilingual.py.cpp && ./a.out
Hello, world!

```

The solution will be scored by the count of non-whitespace characters of the entire program, including the Python script:

```
sed 's/\s//g' bilingual.py.cpp|wc -c

```

# Answer
> 11 votes
# Score 116

Prepend:

```
#include<cstdio>
#define print(A)main(){puts(A);}
#define greet()
#define \

```

The preprocessor backslash `\` pulls the nasty `:` containing line into an unused macro. Try it here.

Thanks to edc65's answer for the note about implicit int in C++4.
Thanks to PieCot's answer for suggesting `<cstdio>` over `<stdio.h>`.
Thanks to Leon for suggest I remove the `X` in the original `#define X\`.

# Answer
> 11 votes
# Score 119

(Thx @Linus for the byte count)

(1 byte saved thx @Conor O'Brien) (1 byte saved thx @PieCot)

~~Counting bytes again by hand, I found 113. Maybe it's right this time.~~ No it's not

```
#include <cstdio>
#define def main(){0?
#define print(x) puts(x);}
#define greet()

```

Notes: stdio and puts are still alive and kicking in C++. The missing int type is valid in C++ 4. Test

# Answer
> 7 votes
# Score ~~131 130~~ 134

The lines to be prepended are:

```
#import <iostream>
#define def int main(){0?
#define greet()
#define print(A) 0;std::cout<<A"\n";}

```

And the resulting code:

```
#import <iostream>
#define def int main(){0?
#define greet()
#define print(A) 0;std::cout<<A"\n";}
def greet():
    print("Hello, world!")

greet()

```

## Testing

```
C:\Users\Conor O'Brien\Documents\Programming\golf
λ type bilingual.py.cpp

#import <iostream>
#define def int main(){0?
#define greet()
#define print(A) 0;std::cout<<A"\n";}
def greet():
    print("Hello, world!")

greet()
C:\Users\Conor O'Brien\Documents\Programming\golf
λ sed 's/\s//g' bilingual.py.cpp|wc -c
134

C:\Users\Conor O'Brien\Documents\Programming\golf
λ g++ bilingual.py.cpp 2>nul && a
Hello, world!

C:\Users\Conor O'Brien\Documents\Programming\golf
λ python bilingual.py.cpp
Hello, world!

C:\Users\Conor O'Brien\Documents\Programming\golf
λ

```

# Answer
> 6 votes
## Score ~~110~~ 104

Improving upon Linus' answer:

```
#include <cstdio>
#define print main(){puts
#define greet() ;}//\
def greet():
    print("Hello, world!")

greet()

```

Test as C++

Test as Python

# Answer
> 5 votes
## Score 136

Only for the records:

```
#include <cstdio>
#define def class a{public
#define greet()
#define print(a) };int main(){puts(a);}

```

Another (less efficient) way to handle the colon.

---
Tags: code-golf, python, polyglot, programming-puzzle, c++
---