# Question
Title: Fastest algorithm to take the product of all subsets
Given `n` numbers in an array (you can't assume they are integers), I would like to compute the product of all subsets of size `n-1`.

You can do this by multiplying all the numbers together and then dividing by each one in turn, as long as none of the numbers is zero. However, how quickly can you do this with no division?

> If you don't allow division, what is the minimum number of arithmetic operations (e.g. multiplication and addition) needed to compute the product of all subsets of size n-1?

Clearly you can do it in `(n-1)*n` multiplications.

To clarify, the output is `n` different products and the only operations apart from reading and writing to memory allowed are multiplication, addition and subtraction.

**Example**

If the input has three numbers `2,3,5`, then the output is three numbers `15 = 3*5`, `10 = 2*5` and `6 = 2*3`.

**Winning criterion**

Answers should give an exact formula for the number of arithmetic operations their code will use in terms of `n`. To make life simple, I will just plug `n = 1000` into your formula to judge its score. The lower the better.

If it's too hard to produce an exact formula for your code, you can just run it for `n = 1000` and count the arithmetic operations in the code. An exact formula would be best however.

You should add your score for `n=1000` to your answer for easy comparison.

# Answer
# Python, 3(n-2) operations, score = 2994

```
l = list(map(float, input().split()))
n = len(l)

left = [0] * len(l)
right = [0] * len(l)
left[0] = l[0]
right[-1] = l[-1]
for i in range(1,len(l)-1):
  left[i] = l[i] * left[i - 1]
  right[-i-1] = l[-i-1] * right[-i]

result = [0] * len(l)
result[-1] = left[-2]
result[0] = right[1]
for i in range(1, len(l) - 1):
  result[i] = left[i - 1] * right[i+1]

print(result)

```

The arrays `left` and `right` contain the cumulated products of the array from the left and from the right, respectively.

## EDIT: Proof that 3(n-2) is the optimal number of operations needed for n \>= 2, if we only use multiplication.

We will do that by induction; by the above algorithm, we just have to prove that for n \>= 2, 3(n-2) is a lower bound on the number of multiplications needed.

For n = 2, we need at least 0 = 3(2-2) multiplications, so the result is trivial.

Let n \> 2, and suppose for n - 1 elements, we need at least 3(n-3) multiplications. Consider a solution for n elements with k multiplications. Now, we remove the last of these elements as if it was 1, and simplify all multiplications directly by it. We also remove the multiplication leading to the product of all the other elements, since that one is not needed as it can never be used as an intermediate value to get the product of n-2 of the other elements, since division is not allowed. This leaves us with l multiplications, and a solution for n - 1 elements.

By induction hypothesis, we have l \>= 3(n-3).

Now, let's have a look at how many multiplications were removed. One of them was the one leading to the product of all elements except the last. Moreover, the last element was used directly in at least two multiplications: if it was used in only one, then it was used when multiplying by an intermediate result consisting in some product of the other elements; let's say, without loss of generality, this this intermediate result included the first element in the product. Then, there is no way to get the product of all the elements but the first, since every product that contains the last element is either the last element, or contains the first element.

We thus have k \>= l+3 \>= 3(n-2), proving the claimed theorem.
> 23 votes

# Answer
# Haskell, score 2994

```
group :: Num a => [a] -> [[a]]
group (a:b:t) = [a,b] : group t
group [a] = [[a]]
group [] = []

(%) :: (Num a, Eq a) => a -> a -> a
a % 1 = a
1 % b = b
a % b = a * b

prod_one_or_two :: (Num a, Eq a) => [a] -> a
prod_one_or_two [a, b] = a % b
prod_one_or_two [x] = x

insert_new_value :: (Num a, Eq a) => ([a], a) -> [a]
insert_new_value ([a, b], c) = [c % b, c % a]
insert_new_value ([x], c) = [c]

products_but_one :: (Num a, Eq a) => [a] -> [a]
products_but_one [a] = [1]
products_but_one l =
    do combination <- combinations ; insert_new_value combination
    where
        pairs = group l
        subresults = products_but_one $ map prod_one_or_two pairs
        combinations = zip pairs subresults

```

Try it online!

Say we're given the list `[a,b,c,d,e,f,g,h]`. We first group it into pairs `[[a,b],[c,d],[e,f],[g,h]]`. Then, we recurse on the half-size list `pairs` of their products to get `subresults`

```
[a*b, c*d, e*f, g*h] -> [(c*d)*(e*f)*(g*h), (a*b)*(e*f)*(g*h), (a*b)*(c*d)*(g*h), (a*b)*(c*d)*(e*f)]

```

If we take the first element `(c*d)*(e*f)*(g*h)`, and multiply it by `b` and `a` respectively, we get the product of all but `a` and all but `b`. Doing this for every pair and recursive result with that pair missing, we get out final result. The odd-length case is specially handled by having the odd element passed unpaired to the recursive step, and the product of the remaining elements returned is the product without it.

The number of multiplications `t(n)` is `n/2` for the pairing product, `t(n/2)` for the recursive call, and another `n` for the products with individual elements. This gives `t(n) = 1.5 * n + t(n/2)` for odd `n`. Using a more precise counts for odd `n` and ignoring multiplying with `1` for the base case gives score `2997` for `n=1000`.
> 11 votes

# Answer
# Haskell, score 9974

```
partition :: [Float] -> ([Float], [Float])
partition = foldr (\a (l1,l2) -> (l2, a:l1)) ([],[])

(%) :: Float -> Float -> Float
a % 1 = a
1 % b = b
a % b = a*b

merge :: (Float, [Float]) -> (Float, [Float]) -> (Float, [Float])
merge (p1,r1) (p2, r2) = (p1%p2, map(%p1)r2 ++ map(%p2)r1)

missing_products' :: [Float] -> (Float, [Float])
missing_products' [a] = (a,[1])
missing_products' l = merge res1 res2
    where
        (l1, l2) = partition l
        res1 = missing_products' l1
        res2 = missing_products' l2

missing_products :: [Float] -> [Float]
missing_products = snd . missing_products'

```

Try it online!

A divide-and-conquer strategy, very reminiscent of merge sort. Doesn't do any indexing.

The function `partition` splits the list into as-equal-as-possible halves by putting alternating elements on opposite sides of the partition. We recursively merge the results `(p,r)` for each of the halves, with `r` the list of products-with-one-missing, and `p` the overall product.

For the output for the full list, the missing element must be in one of the halves. The product with that element missing is a one-missing-product for the half it's in, multiplied by the full product for the other half. So, we multiply each product-with-one-missing by the full product of the other half and make a list of the results, as `map(*p1)r2 ++ map(*p2)r1)`. This takes `n` multiplications, where `n` is the length. We also need to make a new full-product `p1*p2` for future use, costing 1 more multiplication.

This gives the general recursion for for the number of operations `t(n)` with `n` even: `t(n) = n + 1 + 2 * t(n/2)`. The odd one is similar, but one of the sublists is `1` larger. Doing out the recursion, we get `n*(log_2(n) + 1)` multiplications, though the odd/even distinction affects that exact value. The values up to `t(3)` are improved by not multiplying by `1` by defining a variant `(%)` of `(*)` that shortcuts the `_*1` or `1*_` cases.

This gives `9975` multiplications for `n=1000`. I believe Haskell's laziness means the unused overall product in the outer layer is not computed for `9974`; if I'm mistaken, I could omit it explicitly.
> 8 votes

# Answer
## O(n log n) operations, score = 9974

Works with a binary tree.

## Python

```
l = list(map(int, input().split()))
n = len(l)

p = [0] * n + l
for i in range(n - 1, 1, -1):
  p[i] = p[i + i] * p[i + i+1]

def mul(x, y):
  if y == None:
    return x
  return x * y

r = [None] * n + [[None]] * n
for i in range(n - 1, 0, -1):
  r[i] = [mul(p[i + i + 1], x) for x in r[i + i]] + [mul(p[i + i], x) for x in r[i + i + 1]]

u = r[1]
j = 1
while j <= n:
  j += j
print(u[n+n-j:] + u[:n+n-j])

```

This also requires list addition operations, and some arithmetic on numbers that are not the input values; not sure if that counts. The `mul` function is there to save n operations for the base case, to avoid wasting them by multiplying by 1. In any case, this is O(n log n) operations. The exact formula is, if only counting arithmetic operations on input numbers, with `j = floor(log_2(n))`: `j * (2^(j + 1) - n) + (j + 1) * (2 * n - 2^(j + 1)) - 2`.

Thanks to @xnor for saving one operation with the idea of not computing the outer product!

The last part is to output the products in order of the missing term.
> 4 votes

# Answer
# Haskell, score 2994

```
group :: [a] -> Either [(a, a)] (a, [(a, a)])
group [] = Left []
group (a : l) = case group l of
  Left pairs -> Right (a, pairs)
  Right (b, pairs) -> Left ((a, b) : pairs)

products_but_one :: Num a => [a] -> [a]
products_but_one [_] = [1]
products_but_one [a, b] = [b, a]
products_but_one l = case group l of
  Left pairs ->
    let subresults =
          products_but_one [a * b | (a, b) <- pairs]
    in do ((a, b), c) <- zip pairs subresults; [c * b, c * a]
  Right (extra, pairs) ->
    let subresult : subresults =
          products_but_one (extra : [a * b | (a, b) <- pairs])
    in subresult : do ((a, b), c) <- zip pairs subresults; [c * b, c * a]

```

Try it online!

### How it works

This is a cleaned up version of xnor’s algorithm that deals with the odd case in a more straightforward way (edit: it looks like xnor has cleaned it up the same way):

\[a, b, c, d, e, f, g\] ↦
\[a, bc, de, fg\] ↦
\[(bc)(de)(fg), a(de)(fg), a(bc)(fg), a(bc)(de)\] by recursion ↦
\[(bc)(de)(fg), a(de)(fg)c, a(de)(fg)b, a(bc)(fg)e, a(bc)(fg)d, a(bc)(de)g, a(bc)(de)f\]

\[a, b, c, d, e, f, g, h\] ↦
\[ab, cd, ef, gh\] ↦
\[(cd)(ef)(gh), (ab)(ef)(gh), (ab)(cd)(gh), (ab)(cd)(ef)\] by recursion ↦
\[(cd)(ef)(gh)b, (cd)(ef)(gh)a, (ab)(ef)(gh)d, (ab)(ef)(gh)c, (ab)(cd)(gh)f, (ab)(cd)(gh)e, (ab)(cd)(ef)h, (ab)(cd)(ef)g\].
> 4 votes

# Answer
# O((n-2)\*n) = O(n2): Trivial Solution

This is just the trivial solution that multiplies together each of the subsets:

# Python

```
def product(array): # Requires len(array) - 1 multiplication operations
    if not array: return 1
    result = array[0]
    for value in array[1:]:
        result *= value
    return result

def getSubsetProducts(array):
    products = []
    for index in range(len(array)): # calls product len(array) times, each time calling on an array of size len(array) - 1, which means len(array) - 2 multiplication operations called len(array) times
        products.append(product(array[:index] + array[index + 1:]))
    return products

```

Note that this also requires `n` list-addition operations; not sure if that counts. If that is not allowed, then `product(array[:index] + array[index + 1:])` can be replaced to `product(array[:index]) * product(array[index + 1:])`, which changes the formula to `O((n-1)*n)`.
> 2 votes

# Answer
# Python, 7540

A tripartite merge strategy. I think I can do even better than this, with a yet large merge. It's O(n log n).

EDIT: Fixed a miscount.

```
count = 0
def prod(a, b):
    if a == 1: return b
    if b == 1: return a
    global count
    count += 1
    return a * b

def tri_merge(subs1, subs2, subs3):
    total1, missing1 = subs1
    total2, missing2 = subs2
    total3, missing3 = subs3

    prod12 = prod(total1, total2)
    prod13 = prod(total1, total3)
    prod23 = prod(total2, total3)

    new_missing1 = [prod(m1, prod23) for m1 in missing1]
    new_missing2 = [prod(m2, prod13) for m2 in missing2]
    new_missing3 = [prod(m3, prod12) for m3 in missing3]

    return prod(prod12, total3), new_missing1 + new_missing2 + new_missing3

def tri_partition(nums):
    split_size = len(nums) // 3
    a = nums[:split_size]
    second_split_length = split_size + (len(nums) % 3 == 2)
    b = nums[split_size:split_size + second_split_length]
    c = nums[split_size + second_split_length:]
    return a, b, c

def missing_products(nums):
    if len(nums) == 1: return nums[0], [1]
    if len(nums) == 0: return 1, []
    subs = [missing_products(part) for part in tri_partition(nums)]
    return tri_merge(*subs)

def verify(nums, res):
    actual_product = 1
    for num in nums:
        actual_product *= num
    actual_missing = [actual_product // num for num in nums]
    return actual_missing == res[1] and actual_product == res[0]

nums = range(2, int(input()) + 2)
res = missing_products(nums)

print("Verified?", verify(nums, res))
if max(res[1]) <= 10**10: print(res[1])

print(len(nums), count)

```

The relevant function is `missing_products`, which gives the overall product and all of the ones with a missing element.
> 2 votes

# Answer
# C++, score: 5990, O(\[2NlogN\]/3)

This implementation uses a binary tree look up table. My first implementation was O(NlogN), but a last minute optimization, which looks up the product of all array elements minus a pair, + 2 multiplications saved the day. I think this could still be optimized a bit further, maybe another 16%...

I've left some debugging traces in, only because it's easier to delete them than to rewrite them :)

\[Edit\] the actual complexity is measured at O(\[2NlogN\]/3) for 100. It is actually a bit worse than O(NlogN) for small sets, but tends towards O(\[NlogN\]/2) as the array grows very large O(0.57.NlogN) for a a set of 1 million elements.

```
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <random>
#include <cstdlib>

using DataType = long double;

using DataVector = std::vector<DataType>;

struct ProductTree
{
    std::vector<DataVector> tree_;
    size_t ops_{ 0 };

    ProductTree(const DataVector& v) : ProductTree(v.begin(), v.end()) {}
    ProductTree(DataVector::const_iterator first, DataVector::const_iterator last)
    {
        Build(first, last);
    }

    void Build(DataVector::const_iterator first, DataVector::const_iterator last)
    {
        tree_.emplace_back(DataVector(first, last));

        auto size = std::distance(first, last);
        for (auto n = size; n >= 2; n >>= 1)
        {
            first = tree_.back().begin();
            last = tree_.back().end();

            DataVector v;
            v.reserve(n);
            while (first != last) // steps in pairs
            {
                auto x = *(first++);
                if (first != last)
                {
                    ++ops_;
                    x *= *(first++); // could optimize this out,small gain
                }
                v.push_back(x);
            }
            tree_.emplace_back(v);
        }
    }

    // O(NlogN) implementation...
    DataVector Prod()
    {
        DataVector result(tree_[0].size());
        for (size_t i = 0; i < tree_[0].size(); ++i)
        {
            auto depth = tree_.size() - 1;
            auto k = i >> depth;
            result[i] = ProductAtDepth(i, depth);
        }
        return result;
    }

    DataType ProductAtDepth(size_t index, size_t depth)
    {
        if (depth == 0)
        {
            return ((index ^ 1) < tree_[depth].size())
                ? tree_[depth][index ^ 1]
                : 1;
        }
        auto k = (index >> depth) ^ 1;

        if ((k < tree_[depth].size()))
        {
            ++ops_;
            return tree_[depth][k] * ProductAtDepth(index, depth - 1);
        }
        return ProductAtDepth(index, depth - 1);
    }

    // O([3NlogN]/2) implementation...
    DataVector Prod2()
    {
        DataVector result(tree_[0].size());
        for (size_t i = 0; i < tree_[0].size(); ++i)    // steps in pairs
        {
            auto depth = tree_.size() - 1;
            auto k = i >> depth;
            auto x = ProductAtDepth2(i, depth);
            if (i + 1 < tree_[0].size())
            {
                ops_ += 2;
                result[i + 1] = tree_[0][i] * x;
                result[i] = tree_[0][i + 1] * x;
                ++i;
            }
            else
            {
                result[i] = x;
            }
        }
        return result;
    }

    DataType ProductAtDepth2(size_t index, size_t depth)
    {
        if (depth == 1)
        {
            index = (index >> 1) ^ 1;
            return (index < tree_[depth].size())
                ? tree_[depth][index]
                : 1;
        }
        auto k = (index >> depth) ^ 1;

        if ((k < tree_[depth].size()))
        {
            ++ops_;
            return tree_[depth][k] * ProductAtDepth2(index, depth - 1);
        }
        return ProductAtDepth2(index, depth - 1);
    }

};

int main()
{
    //srand(time());

    DataVector data;
    for (int i = 0; i < 1000; ++i)
    {
        auto x = rand() & 0x3;          // avoiding overflow and zero vaolues for testing
        data.push_back((x) ? x : 1);
    }

    //for (int i = 0; i < 6; ++i)
    //{
    //  data.push_back(i + 1);
    //}

    //std::cout << "data:[";
    //for (auto val : data)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";

    ProductTree pt(data);
    DataVector result = pt.Prod2();

    //std::cout << "result:[";
    //for (auto val : result)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";
    std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';

    pt.ops_ = 0;
    result = pt.Prod();

    //std::cout << "result:[";
    //for (auto val : result)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";

    std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';

    return 0;
}

```

I'm adding @nore's algorithm, for completeness. It's really nice, and is the fastest.

```
class ProductFlat
{
private:
    size_t ops_{ 0 };

    void InitTables(const DataVector& v, DataVector& left, DataVector& right)
    {
        if (v.size() < 2)
        {
            return;
        }

        left.resize(v.size() - 1);
        right.resize(v.size() - 1);

        auto l = left.begin();
        auto r = right.rbegin();
        auto ol = v.begin();
        auto or = v.rbegin();

        *l = *ol++;
        *r = *or++;
        if (ol == v.end())
        {
            return;
        }

        while (ol + 1 != v.end())
        {
            ops_ += 2;
            *l = *l++ * *ol++;
            *r = *r++ * *or++;
        }
    }

public:
    DataVector Prod(const DataVector& v)
    {
        if (v.size() < 2)
        {
            return v;
        }

        DataVector result, left, right;
        InitTables(v, left, right);

        auto l = left.begin();
        auto r = right.begin();
        result.push_back(*r++);
        while (r != right.end())
        {
            ++ops_;
            result.push_back(*l++ * *r++);
        }
        result.push_back(*l++);
        return result;
    }

    auto Ops() const
    {
        return ops_;
    }
};

```
> 0 votes

# Answer
# dc, score 2994

```
#!/usr/bin/dc -f

# How it works:
# The required products are
#
#   (b × c × d × e × ... × x × y × z)
# (a) × (c × d × e × ... × x × y × z)
# (a × b) × (d × e × ... × x × y × z)
# ...
# (a × b × c × d × e × ... × x) × (z)
# (a × b × c × d × e × ... × x × y)
#
# We calculate each parenthesised term by
# multiplying the one above (on the left) or below
# (on the right), for 2(n-2) calculations, followed
# by the n-2 non-parenthesised multiplications
# giving a total of 3(n-2) operations.

# Read input from stdin
?

# We will store input values into stack 'a' and
# accumulated product into stack 'b'.  Initialise
# stack b with the last value read.
sb

# Turnaround function at limit of recursion: print
# accumulated 'b' value (containing b..z above).
[Lbn[ ]nq]sG

# Recursive function - on the way in, we stack up
# 'a' values and multiply up the 'b' values.  On
# the way out, we multiply up the 'a' values and
# multiply each by the corresponding 'b' value.
[dSalb*Sb
z1=G
lFx
dLb*n[ ]n
La*]dsFx

# Do the last a*b multiplication
dLb*n[ ]n

# And we have one final 'a' value that doesn't have a
# corresponding 'b':
La*n

```

I'm assuming that the integer comparison `z1=` (which terminates the recursion when we reach the last value) is free. This is equivalent to the likes of `foreach` in other languages.

## Demonstrations

```
for i in '2 3 5' '2 3 5 7' '0 2 3 5' '0 0 1 2 3 4'
do printf '%s => ' "$i"; ./127147.dc <<<"$i"; echo
done
2 3 5 => 15 10 6
2 3 5 7 => 105 70 42 30
0 2 3 5 => 30 0 0 0
0 0 1 2 3 4 => 0 0 0 0 0 0

```

A demo with large and small inputs:

```
./127147.dc <<<'.0000000000000000000542101086242752217003726400434970855712890625 1 18446744073709551616'
18446744073709551616 1.0000000000000000000000000000000000000000000000000000000000000000 .0000000000000000000542101086242752217003726400434970855712890625

```
> 0 votes

---
Tags: arithmetic, fewest-operations
---


title: ASCII Reverse Quine

text:
# Question
Title: ASCII Reverse Quine
Okay, so everyone is familiar with the ASCII-table, correct? I'd hope so. I've been going to that site for my asciitable reference for as long as I can remember needing one. We'll be doing some fun source-code manipulating using the ASCII keyspace.

---

# The Task

Your task is to write a program that, when executed, prints the source code with the ASCII decimal of each character reversed. What exactly does this mean? Say this was my sourcecode:

```
#;

```

The ASCII of this would be:

```
(35)(59)

```

After knowing this, we should reverse each to get what the program should output:

```
(53)(95)

```

Which means for a program of `#;` we need to output:

```
5_

```

---

# Constraint 1 (Important)

However, like in most challenges, there's a hefty catch. All characters in your source code must be within the printable ASCII range. If the reverse of the ASCII character does NOT lie within 32-128, the character can't be used. For any character with an ASCII code *greater* than 100, you will reverse it and use the first two digits. For instance:

```
d = 100 => 001 => 00 => \0 => non-ASCII => invalid

```

Another example, of a valid 3-digit ASCII reverse:

```
{ = 123 => 321 => 32 => ' ' => valid

```

If this is unclear, see the "Conversion" part below, if the character is not listed there on the left, it cannot be in your source code.

---

# Constraint 2 (Important)

***In addition to this constraint, the user must also use at least one non-palindromic ASCII character. This means that if you want to use `7`, which is ASCII `55` and converts directly TO `7`, you will have a 2-byte answer at minimum.***

---

# Constraint 3

Your program will take no input, as this is a quine challenge. In addition to this, it must adhere to the specifications of a proper quine defined here:

http://meta.codegolf.stackexchange.com/questions/4877/what-counts-as-a-proper-quine

---

# The Concrete Specification

*Printable ASCII Set (32-126):*

```
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

*Conversions:*

```
  => 23 => (not valid)
! => 33 => ! (valid)
" => 43 => + (valid)
# => 53 => 5 (valid)
$ => 63 => ? (valid)
% => 73 => I (valid)
& => 83 => S (valid)
' => 93 => ] (valid)
( => 04 => (not valid)
) => 14 => (not valid)
* => 24 => (not valid)
+ => 34 => " (valid)
, => 44 => , (valid)
- => 54 => 6 (valid)
. => 64 => @ (valid)
/ => 74 => J (valid)
0 => 84 => T (valid)
1 => 94 => ^ (valid)
2 => 05 => (not valid)
3 => 15 => (not valid)
4 => 25 => (not valid)
5 => 35 => # (valid)
6 => 45 => - (valid)
7 => 55 => 7 (valid)
8 => 65 => A (valid)
9 => 75 => K (valid)
: => 85 => U (valid)
; => 95 => _ (valid)
< => 06 => (not valid)
= => 16 => (not valid)
> => 26 => (not valid)
? => 36 => $ (valid)
@ => 46 => . (valid)
A => 56 => 8 (valid)
B => 66 => B (valid)
C => 76 => L (valid)
D => 86 => V (valid)
E => 96 => ` (valid)
F => 07 => (not valid)
G => 17 => (not valid)
H => 27 => (not valid)
I => 37 => % (valid)
J => 47 => / (valid)
K => 57 => 9 (valid)
L => 67 => C (valid)
M => 77 => M (valid)
N => 87 => W (valid)
O => 97 => a (valid)
P => 08 => (not valid)
Q => 18 => (not valid)
R => 28 => (not valid)
S => 38 => & (valid)
T => 48 => 0 (valid)
U => 58 => : (valid)
V => 68 => D (valid)
W => 78 => N (valid)
X => 88 => X (valid)
Y => 98 => b (valid)
Z => 09 => (not valid)
[ => 19 => (not valid)
\ => 29 => (not valid)
] => 39 => ' (valid)
^ => 49 => 1 (valid)
_ => 59 => ; (valid)
` => 69 => E (valid)
a => 79 => O (valid)
b => 89 => Y (valid)
c => 99 => c (valid)
d => 001 => (not valid)
e => 101 => (not valid)
f => 201 => (not valid)
g => 301 => (not valid)
h => 401 => ( (valid)
i => 501 => 2 (valid)
j => 601 => < (valid)
k => 701 => F (valid)
l => 801 => P (valid)
m => 901 => Z (valid)
n => 011 => (not valid)
o => 111 => (not valid)
p => 211 => (not valid)
q => 311 => (not valid)
r => 411 => ) (valid)
s => 511 => 3 (valid)
t => 611 => = (valid)
u => 711 => G (valid)
v => 811 => Q (valid)
w => 911 => [ (valid)
x => 021 => (not valid)
y => 121 => (not valid)
z => 221 => (not valid)
{ => 321 =>   (valid)
| => 421 => * (valid)
} => 521 => 4 (valid)
~ => 621 => > (valid)

```

---

**ESOLANGS:** If you're using a custom CODEPAGE and wish to use the CODEPAGE definition as the ASCII table, I'll allow it. But you must be thorough in your explanation of why the characters are enumerated as they are (and it must make sense based on an existing code-page diagram). According to this 31/96 (32%) conversions are invalid, therefore it should follow that for a codepage of 255 characters, a consecutive range of 96 characters can be considered as "printable ASCII" if, and only if, it results in 31 (or 32%) or more of those characters being invalid.

---

This is , lowest byte-count wins.

# Answer
> 8 votes
## CJam, 24 bytes

```
{s"_~"+{isW%Y60c~ic}%}_~

```

Try it online!

Prints:

```
 3+;>+" 23NIb-Tc>2c4I4;>

```

A fairly standard generalised quine. The only character we could have used that is forbidden is `<`, which we get with `60c~` instead.

---
Tags: code-golf, restricted-source, quine, printable-ascii
---


title: Surrounded and reversed

text:
# Question
Title: Surrounded and reversed
## The task

In this challenge, your task is to determine whether some string occurs as a substring of a given string both surrounded by another string and reversed.

Your input is a non-empty string **S** of lowercase ASCII letters. If there exist non-empty strings **A** and **B** such that the concatenation **ABA** and the reversal **rev(B)** are both contiguous substrings of **S**, then your output shall be a truthy value. Otherwise, your output shall be a falsy value. The two substrings may occur in any order, and they can even overlap. However, it can be shown that in all truthy cases, you can either find non-overlapping substrings or a solution where **B** is a palindrome.

## Example

Consider the input string `S = zyxuxyzxuyx`. We choose `A = xu` and `B = xyz`, and then we can find the following substrings:

```
S      = zyxuxyzxuyx
ABA    =   xuxyzxu
rev(B) = zyx

```

The choice `A = x` and `B = u` would also be valid. The correct output in this case is truthy.

## Rules and scoring

You can write a full program or a function. Standard loopholes are disallowed. The lowest byte count wins.

## Test cases

Truthy

```
sds
aaxyxaa
aaxyaaayx
hgygjgyygj
zyxuxyzxuyx
cgagciicgxcciac
iecgiieagcigaci
oilonnsilasionloiaammialn
abbccdeeaabccddbaacdbbaccdbaaeeccddb

```

Falsy

```
a
aaxyaa
jjygjhhyghj
abcaabbccaabca
egaacxiagxcaigx
lnsiiosilnmosaioollnoailm
cabbccabdcaddccabbddcaabbdcaddccaadcabbccaabbcadcc

```

### Fun fact

One can construct arbitrarily long falsy strings using four distinct letters, but not using three letters. The fourth falsy test case is the longest possible.

# Answer
# Brachylog, 13 bytes

```
s↔B&sA,B,A~s?

```

Try it online!

## How it works

```
s↔B&sA,B,A~s?
s              the input has substring temp
 ↔B            temp reversed is B
   &           and the input
    sA         has substring A
      ,B,A     A,B,A
          ~s?  is a substring of input

```
> 5 votes

# Answer
# Retina, 40 bytes

```
(.+)(.)+\1.*(?<=(?=(?<-2>\2)+(?(2)A)).*)

```

Try it online!

Big thanks to Martin for fixing a bug with the expression.

Matches **ABA** then the rest of the string. While doing this, it pushes **B**'s characters onto a stack. Looks backwards over the whole string to find **B** in reverse order, by traversing forward again and popping characters off of the stack as it matches them (`(?<-2>\2)+`). Then it makes sure the stack is empty by trying to match a capital letter, which won't be in the input, if the stack still is full.
> 3 votes

# Answer
## Ruby, 53 bytes

```
->s{s.scan(/(?=(.+)(.+)\1)/).any?{|a,b|s[b.reverse]}}

```

Fairly straightforward. The only real trick is the positive lookahead `(?=...)` in the regex, which is used to find all matches and not just non-overlapping ones.

Try it online!
> 2 votes

# Answer
# PHP, 95 bytes

```
<?=($p=preg_match_all)('#(?=(.+)(.+)\1)#',$argn,$t)&&$p(strrev("#".join("|",$t[2])."#"),$argn);

```

Try it online!
> 2 votes

# Answer
# Jelly, 21 bytes

```
Ḣ⁼Ṫȧ
ẆŒṖ€ẎÇÐfẎ€QUẇ€⁸Ṁ

```

Try it online!

Very inefficient.
> 1 votes

---
Tags: code-golf, string, decision-problem
---


title: Optimizing SKI compiler

text:
# Question
Title: Optimizing SKI compiler
The *SKI calculus* is a variant of the Lambda calculus that doesn't use lambda expressions. Instead, only application and the combinators *S*, *K*, and *I* are used. In this challenge, your task is to translate SKI terms into Lambda terms in β normal form.

---

## Input Specification

The input is an SKI term in the following textual representation. You may choose to receive an optional trailing newline. The input is composed of the characters `S`, `K`, `I`, `(`, and `)` and satisfies the following grammar (in ABNF form) with `sterm` being the start symbol:

```
sterm = sterm combinator     ; application
sterm = combinator           ;
sterm = '(' sterm ')'        ; grouping
combinator = 'S' | 'K' | 'I' ; primitives

```

## Output Specification

The output is a lambda term with no free variables in the following textual representation. You may choose to output an optional trailing newline. The output shall satisfy the following grammar in ABNF form with `lterm` being the start symbol:

```
lterm   = lterm operand     ; application
lterm   = ALPHA '.' lterm   ; lambda
lterm   = operand
operand = '(' lterm ')'     ; grouping
operand = ALPHA             ; variable (a letter)

```

## Constraints

You may assume that the input has a β normal form. You may assume that the β normal form uses at most 26 different variables. You may assume that both input and output are representable in 79 characters.

## Sample inputs

Here are a couple of sample inputs. The output is one possible output for the given input.

```
input                        output
I                            a.a
SKK                          a.a
KSK                          a.b.c.ac(bc)
SII                          a.aa

```

## Scoring

The shortest solution in octets wins. Common loopholes are prohibited.

# Answer
> 3 votes
# Haskell, 232 bytes

```
data T s=T{a::T s->T s,(%)::s}
i d=T(i. \x v->d v++'(':x%v++")")d
l f=f`T`\v->v:'.':f(i(\_->[v]))%succ v
b"S"x=l$l.(a.a x<*>).a
b"K"x=l(\_->x)
b"I"x=x
p?'('=l id:p
(p:q:r)?')'=a q p:r
(p:q)?v=a p(l$b[v]):q
((%'a')=<<).foldl(?)[l id]

```

Try it online!

### How it works

This is a different parser frontend to my answer to “Write an interpreter for the untyped lambda calculus”, which also has an ungolfed version with documentation.

Briefly, `Term = T (Char -> String)` is the type of lambda calculus terms, which know how to apply themselves to other terms (`a :: Term -> Term -> Term`) and how to display themselves as a `String` (`(%) :: Term -> Char -> String`), given an initial fresh variable as a `Char`. We can convert a function on terms to a term with `l :: (Term -> Term) -> Term`, and because application of the resulting term simply calls the function (`a (l f) == f`), terms are automatically reduced to normal form when displayed.

# Answer
> 9 votes
# Python 2, 674

```
exec u"""import sys
$ V#):%=V.c;V.c+=1
 c=97;p!,v,t:[s,t.u({})][v==s];r!:s;u!,d:d.get(s,s);s!:chr(%)
 def m(s,x):%=min(%,x);-(%==x)+x
$ A#,*x):%,&=x
 C='()';p!,x,y:s.__$__(%.p/,&.p/);m!,x:&.m(%.m(x));u!,d:A(%.u(d),&.u(d));s!:%.s()+s.C[0]+&.s()+s.C[1:]
 def r(s):x=%.r();y=&.r();-x.b.p(x.a,y).r()if'L'in`x`else s.__$__/
$ L(A):C='.';u!,d:L(d.setdefault(%,V()),&.u(d))
x=V();y=V();z=V()
I=L(x,x)
K=L(y,L/)
S=L(x,L(z,L(y,A(A/,A(z,y)))))
def E():
 t=I
 while 1:
    q=sys.stdin.read(1)
    if q in')\\n':-t
    t=A(t,eval(max(q,'E()')).u({}))
t=E().r()
t.m(97)
print t.s()""".translate({33:u'=lambda s',35:u':\n def __init__(s',36:u'class',37:u's.a',38:u's.b',45:u'return ',47:u'(x,y)'})

```

Note: after `while 1:`, 3 lines are indented with a tab character.

This is basically the code behind http://ski.aditsu.net/ , translated to python, greatly simplified and heavily golfed.

**Reference:** (this is probably less useful now that the code is compressed)

V = variable term
A = application term
L = lambda term
c = variable counter
p = replace variable with term
r = reduce
m = final variable renumbering
u = internal variable renumbering (for duplicated terms)
s = string conversion
(parameter s = self)
C = separator character(s) for string conversion
I,K,S: combinators
E = parse

**Examples:**

```
python ski.py <<< "KSK"
a.b.c.a(c)(b(c))
python ski.py <<< "SII"
a.a(a)
python ski.py <<< "SS(SS)(SS)"
a.b.a(b)(c.b(c)(a(b)(c)))(a(d.a(d)(e.d(e)(a(d)(e))))(b))
python ski.py <<< "S(K(SI))K"
a.b.b(a)
python ski.py <<< "S(S(KS)K)I"
a.b.a(a(b))
python ski.py <<< "S(S(KS)K)(S(S(KS)K)I)"
a.b.a(a(a(b)))
python ski.py <<< "K(K(K(KK)))"
a.b.c.d.e.f.e
python ski.py <<< "SII(SII)"
[...]
RuntimeError: maximum recursion depth exceeded

```

(this ↑ is expected because `SII(SII)` is irreducible)

Thanks Mauris and Sp3000 for helping to kill a bunch of bytes :)

# Answer
> 9 votes
# Ruby, 323 bytes

I can't believe this piece of crap works at all:

```
h={};f=96;z=gets.chop
{?S=>'s0.t0.u0.s0u0(t0u0)',?K=>'k0.l0.k0',?I=>'i0.i0'}.each{|k,v|z.gsub!k,?(+v+?)}
loop{z=~/\((?<V>\w1*0)\.(?<A>(?<B>\w1*0|[^()]|\(\g<B>+\))+)\)(?<X>\g<B>)/
s=$`;t=$';abort z.gsub(/\w1*0/){|x|h[x]=h[x]||(f+=1).chr}if !t
z=$`+?(+$~[?A].gsub($~[?V],$~[?X].gsub(/\w1*0/){|a|s[a]?a:a.gsub(?0,'10')})+?)+t}

```

Using regex substitution to perform β-reduction on raw strings is some Tony-the-Pony stuff. Nonetheless, its output looks correct at least for easy testcases:

```
$ echo 'I' | ruby ski.rb
(a.a)
$ echo 'SKK' | ruby ski.rb
(a.(a))
$ echo 'KSK' | ruby ski.rb
((a.b.c.ac(bc)))
$ echo 'SII' | ruby ski.rb
(a.(a)((a)))

```

Here's it handling `K(K(K(KK)))` with some debug output, which takes about 7 seconds on my laptop, because regular expression recursion is *slow*. You can see its α-conversion in action!

```
$ echo 'K(K(K(KK)))' | ruby ski.rb
"(l0.((k10.l10.k10)((k10.l10.k10)((k10.l10.k10)(k10.l10.k10)))))"
"(l0.((l10.((k110.l110.k110)((k110.l110.k110)(k110.l110.k110))))))"
"(l0.((l10.((l110.((k1110.l1110.k1110)(k1110.l1110.k1110)))))))"
"(l0.((l10.((l110.((l1110.(k11110.l11110.k11110))))))))"
(a.((b.((c.((d.(e.f.e))))))))

```

# Answer
> 3 votes
# Common Lisp, 560 bytes

*"Finally, I found a use for `PROGV`."*

```
(macrolet((w(S Z G #1=&optional(J Z))`(if(symbolp,S),Z(destructuring-bind(a b #1#c),S(if(eq a'L),G,J)))))(labels((r(S #1#(N 97))(w S(symbol-value s)(let((v(make-symbol(coerce`(,(code-char N))'string))))(progv`(,b,v)`(,v,v)`(L,v,(r c(1+ n)))))(let((F(r a N))(U(r b N)))(w F`(,F,U)(progv`(,b)`(,U)(r c N))))))(p()(do((c()(read-char()()#\)))q u)((eql c #\))u)(setf q(case c(#\S'(L x(L y(L z((x z)(y z))))))(#\K'(L x(L u x)))(#\I'(L a a))(#\((p)))u(if u`(,u,q)q))))(o(S)(w S(symbol-name S)(#2=format()"~A.~A"b(o c))(#2#()"~A(~A)"(o a)(o b)))))(lambda()(o(r(p))))))

```

### Ungolfed

```
;; Bind S, K and I symbols to their lambda-calculus equivalent.
;;
;; L means lambda, and thus:
;;
;; -  (L x S) is variable binding, i.e. "x.S"
;; -  (F x)   is function application

(define-symbol-macro S '(L x (L y (L z ((x z) (y z))))))
(define-symbol-macro K '(L x (L u x)))
(define-symbol-macro I '(L x x))

;; helper macro: used twice in R and once in O

(defmacro w (S sf lf &optional(af sf))
  `(if (symbolp ,S) ,sf
       (destructuring-bind(a b &optional c) ,S
         (if (eq a 'L)
             ,lf
             ,af))))

;; R : beta-reduction

(defun r (S &optional (N 97))
  (w S
      (symbol-value s)
      (let ((v(make-symbol(make-string 1 :initial-element(code-char N)))))
        (progv`(,b,v)`(,v,v)
              `(L ,v ,(r c (1+ n)))))
      (let ((F (r a N))
            (U (r b N)))
        (w F`(,F,U)(progv`(,b)`(,U)(r c N))))))

;; P : parse from stream to lambda tree

(defun p (&optional (stream *standard-output*))
  (loop for c = (read-char stream nil #\))
        until (eql c #\))
        for q = (case c (#\S S) (#\K K) (#\I I) (#\( (p stream)))
        for u = q then `(,u ,q)
        finally (return u)))

;; O : output lambda forms as strings

(defun o (S)
  (w S
      (princ-to-string S)
      (format nil "~A.~A" b (o c))
      (format nil (w b "(~A~A)" "(~A(~A))") (o a) (o b))))

```

### Beta-reduction

Variables are dynamically bound during reduction with `PROGV` to new Common Lisp symbols, using `MAKE-SYMBOL`. This allows to nicely avoid naming collisions (e.g. undesired shadowing of bound variables). I could have used `GENSYM`, but we want to have user-friendly names for symbols. That is why symbols are named with letters from `a` to `z` (as allowed by the question). `N` represents the character code of the next available letter in current scope and starts with 97, a.k.a. `a`.

Here is a more readable version of `R` (without the `W` macro):

```
(defun beta-reduce (S &optional (N 97))
  (if (symbolp s)
      (symbol-value s)
      (if (eq (car s) 'L)
          ;; lambda
          (let ((v (make-symbol (make-string 1 :initial-element (code-char N)))))
            (progv (list (second s) v)(list v v)
              `(L ,v ,(beta-reduce (third s) (1+ n)))))
          (let ((fn (beta-reduce (first s) N))
                (arg (beta-reduce (second s) N)))
            (if (and(consp fn)(eq'L(car fn)))
                (progv (list (second fn)) (list arg)
                  (beta-reduce (third fn) N))
                `(,fn ,arg))))))

```

### Intermediate results

Parse from string:

```
CL-USER> (p (make-string-input-stream "K(K(K(KK)))"))
((L X (L U X)) ((L X (L U X)) ((L X (L U X)) ((L X (L U X)) (L X (L U X))))))

```

Reduce:

```
CL-USER> (r *)
(L #:|a| (L #:|a| (L #:|a| (L #:|a| (L #:|a| (L #:|b| #:|a|))))))

```

(See trace of execution)

Pretty-print:

```
CL-USER> (o *)
"a.a.a.a.a.b.a"

```

### Tests

I reuse the same test suite as the Python answer:

```
        Input                    Output              Python output (for comparison)

   1.   KSK                      a.b.c.a(c)(b(c))    a.b.c.a(c)(b(c))
   2.   SII                      a.a(a)              a.a(a)
   3.   S(K(SI))K                a.b.b(a)            a.b.b(a)
   4.   S(S(KS)K)I               a.b.a(a(b))         a.b.a(a(b))
   5.   S(S(KS)K)(S(S(KS)K)I)    a.b.a(a(a(b)))      a.b.a(a(a(b)))
   6.   K(K(K(KK)))              a.a.a.a.a.b.a       a.b.c.d.e.f.e
   7.   SII(SII)                 ERROR               ERROR

```

The 8th test example is too large for the table above:

```
8.      SS(SS)(SS)
CL      a.b.a(b)(c.b(c)(a(b)(c)))(a(b.a(b)(c.b(c)(a(b)(c))))(b))
Python  a.b.a(b)(c.b(c)(a(b)(c)))(a(d.a(d)(e.d(e)(a(d)(e))))(b))

```
* *EDIT* I updated my answer in order to have the same grouping behavior as in aditsu's answer, because it costs less bytes to write.
* The remaining difference can be seen for tests 6 and 8. The result `a.a.a.a.a.b.a` is correct and does not use as much letters as the Python answer, where bindings to `a`, `b`, `c` and `d` are not referenced.

### Performance

Looping over the 7 passing tests above and collecting the results is immediate (SBCL output):

```
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  310,837 processor cycles
  129,792 bytes consed

```

Doing the same test a hundred of times lead to ... "Thread local storage exhausted" on SBCL, due to a known limitation regarding special variables. With CCL, calling the same test suite 10000 times takes 3.33 seconds.

---
Tags: code-golf, repeated-transformation, lambda-calculus, combinatory-logic
---


title: How much reputation did you lose today?

text:
# Question
Title: How much reputation did you lose today?
Assuming StackExchange doesn't decide to restore my account after deleting it due to age restrictions (even though I'm 14 already and almost 15 ಠ\_ಠ), a lot of people on this site just lost reputation from my upvotes being deleted. This happened at around 5:30 PM on June 20th, 2017, UTC.

So, your challenge is to show how much PPCG reputation was lost from my deletion, given the user's PPCG ID.

# Challenge

### Input

A single integer will represent the user's UUID on PPCG.

### Output

A single integer will represent how much reputation the user lost due to this. If the user lost reputation multiple times within the same hour all due to user removals, then it is acceptable if your program returns the number for the wrong user. In the event that the user *gained* reputation from my account being deleted, your program should return a negative number for losing negative reputation. And finally, should I have had no voting on that user (in the past 60 days), your program should return 0.

# Test Cases

```
UUID  -> REP-LOST (Username) # Don't output the username
40695 -> 22 (Downgoat)
12012 -> 148 (Dennis)
8578  -> 61 (Martin Ender)

```

You can check by going to `https://codegolf.stackexchange.com/users/<UUID>/?tab=reputation&sort=post` and looking for `User was removed (learn more)`

Original idea thanks to Uriel with approval

# Note

Thanks to JungHwan Min for this link!

`https://codegolf.stackexchange.com/ajax/users/<UUID>/rep/day/1497916800`

You can fetch raw data of a user's reputation change from this link above.

# Answer
## JavaScript ES6, 132 bytes

```
n=>fetch(`/ajax/users/${n}/rep/day/1497916800`).then(v=>v.text()).then(v=>alert((v.match(/rep-down">-(\d+)[^u]+user w/)||[0,0])[1]))

```

Tested on Safari 10. This uses the new `fetch` API and alerts the output. This is a function so pass the user id as the argument. This will output `0` for no rep changes.

Must be run on PPCG due to CORS (Cross-origin resource sharing), browsers do not allow JavaScript to perform a web request outside of the current domain.
> 9 votes

---
Tags: code-golf
---


title: Flip rows and columns

text:
# Question
Title: Flip rows and columns
# Objective

To flip the rows and columns of a table in a challenge.

# Instructions

You will be passed a "table" of 3 arrays/lists with 3 items each as input. Your job is to flip the rows and columns on it by writing a **program** that can do this efficiently and creatively. You will flip the "table" according to the example below.

# Example

## Input

```
["foo", 5, 0b1011]
[3.14, "bar", 10]
["apple", 90, "monty"]

```

## Output

```
["foo", 3.14, "apple"]
[5, "bar", 90]
[0b1011, 10, "monty"]

```

# Qualification

In order to qualify for winning, you must:

1. Solve the challenge (use the above input for a test case)
2. *Optional:* Post a link to an ideone or repl.it
3. Follow standard loopholes
4. Put a header in the format: `Language, XX bytes`.

This is , so least bytes wins. Good Luck!

# Leaderboard

```
var QUESTION_ID=127611,OVERRIDE_USER=46066;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

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

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

# Answer
> 2 votes
# Math.JS, 1 byte

```
'

```

`'` is a named operator which takes it's left argument and transposes it.

Try it out

# Answer
> 2 votes
# Mathematica, 3 bytes

This character (U+F3C7) is Mathematica's builtin `Transpose` suffix operator.

# Answer
> 1 votes
# Python, 3 bytes

```
zip

```

Note that you must pass the arguments not in a list, but rather as separate arguments, which I believe is acceptable. If not, `lambda x:zip(*x)` works too for a list as a parameter.

If builtins are not allowed (which was not specified), `lambda x:[[b[a]for b in x]for a in range(len(x[0]))]` works, or, since it's specified to be 3 × 3, `lambda x:[[b[a]for b in x]for a in[1,2,3]]` works.

If you're going to enforce the strict IO, then here you go:

```
print(zip(*[input()for i in'3cs'])) # '3cs' because why not, CalcCat

```

# Answer
> 1 votes
# Pyth, 1 byte

```
C

```

Pyth's `C` command transposes the given nested list.

# Answer
> 1 votes
# TI-Basic, 2 bytes

> AnsT

Not eligible for "winning" due to specification #2 but a valid answer nonetheless.

# Answer
> 1 votes
# Python 2, ~~44~~ 51 bytes

*Crossed out 44 is still ~~44~~ :(*

```
for i in zip(*[input()for i in"hi!"]):print list(i)

```

Try it online!

Follows original IO rules. Only works for 3 high input (other heights are not required). Change the length of `"hi!"` to height of input.

# Answer
> 1 votes
# Jelly, 1 byte

```
Z

```

Try it online!

Footer added on the TIO link to make the result easier to see.

This is Jelly's builtin for Zip.

# Answer
> 1 votes
# MacOS bash, 6

```
rs -Tc

```

Works on Linux as well, if `rs` is installed, as TIO:

Try it online.

# Answer
> 0 votes
## Haskell, 26 bytes

```
import Data.List
transpose

```

This is a built-in

---
Tags: code-golf, code-challenge
---


title: Hold'em or Fold'em?

text:
# Question
Title: Hold'em or Fold'em?
Your friend invited you to a high-stakes poker game at the last minute and, as a computer scientist, you've decided to use your skills to gain an edge on the game. Your task will be, given `2 cards` (your hand) and `0, 3, 4 or 5 cards` (the dealt cards), you must decide what the best possible hand you can get will be. If all 7 cards are given as arguments, the answer is pretty clear. If given less, the problem becomes more complex. However, this isn't quite enough to give you the edge you're looking for, you must also calculate the best possible hand from the remaining cards to understand what your opponents could have as well.

---

**Hold'em Refresher**

If you don't know about hold'em, each player in the game starts with 2 cards as their 'hand'. Over the course of 3 'turns', additional cards are revealed to be shared between all players. The first turn, 3 cards are revealed. The second, 1 more, and the third time a final card is revealed. The two cards given first represent your hand, while the latter represents 0, 3, 4, or 5 cards given by the successive turns.

---

**Possible Numbers:**

```
[2,3,4,5,6,7,8,9,T(10),J,Q,K,A]

```

**Possible Suits:**

```
[S,C,H,D]

```

**Full Deck:**

```
[2S,3S,4S,5S,6S,7S,8S,9S,TS,JS,QS,KS,AS, # Spades.
 2C,3C,4C,5C,6C,7C,8C,9C,TC,JC,QC,KC,AC, # Clubs.
 2H,3H,4H,5H,6H,7H,8H,9H,TH,JH,QH,KH,AH, # Hearts.
 2D,3D,4D,5D,6D,7D,8D,9D,TD,JD,QD,KD,AD] # Diamonds.

```

**Hand Rankings:**

```
1:Royal Flush    (A-K-Q-J-10, all from the same suit).
2:Straight Flush (Sequential cards, all from the same suit).
3:Four-of-a-Kind (Self explanatory).
4:Full House     (3-of-a-kind and a 2-of-a-kind).
5:Flush          (All cards are from the same suit).
6:Straight       (Sequential Cards, any suits).
7:3-of-a-Kind    (Self explanatory).
8:2-Pair         (Double 2-of-a-Kind).
9:Pair           (2-of-a-Kind).
10:High Card     (You have absolutely nothing except a single card).

```

---

**Lets take an example or two and walk through them:**

The simple example:

`[AS, AC],[AH,AD,9S,9C,9H]` -\> `3` (Four-of-a-Kind), `3` (Four-of-a-Kind)

The best possible hand you'll have in this setup is the four of a kind hand. The best possible hand your opponents could have is also a 4-of-a-Kind, as you cannot have a KQJ10 in their 2-card hands.

---

`[5C,2C],[6C,4C,JH,JD]` -\> `2` (Straight Flush), `3` (4-of-a-Kind)

You're at risk for a straight flush, but because you have the 2/5C in your hand, nobody else is due to you holding both middle cards. The best they can hope for is having 2 pocket Jacks and getting a Jack on the flop.

---

`[JS,JC],[]` -\> `1` (Royal Flush), `1` (Royal Flush)

No information you can use against them has been given, all you can tell at the moment is that they can only have a royal flush in diamonds/hearts, but it's just as possible that you get the royal flush as they do. In fact, all inputs where the flop has yet to happen should result in a 1-1 answer.

---

`[2C,4S],[3C,7S,9D,AH,JD]` -\> `10` (High Card), `7` (3-of-a-Kind)

This is an example of where you're absolutely screwed, and there's no possibility of a straight or a flush given the river. Meaning the best hand here is pocket aces resulting in a 3-of-a-Kind.

---

# I/O Requirements

* Input must be separated between what is in your hand and what is public knowledge; it'll likely be easier this way regardless of implementation.
    + Cards can be tuples or strings, up to you.
    + The Hand and the Playing Field can be arrays or delimited strings.
* Output must be two indexes from the list of hands I've provided (E.G. \[2,1\]).
    + It may be returned as part of a function, printed to console or output in a suitable manner.
    + There must be two distinct values, one for your best hand, another for the best possible.
* 10 may be represented as a `T` or as `10`, whichever makes sense for you.
* Standard loopholes are disallowed.

# Winning Criteria

* This is , lowest byte-count with a tie-breaker of post date.

# Answer
# Haskell, ~~433 430~~ 425 bytes

-5 bytes thanks to @Laikoni

```
import Data.List
q="23456789TJQKA"
e=elem
l=length
b=map
r p|z,elem 'A'u,elem 'K'u=1|z=2|e 4t=3|v<3=4|w=5|y=6|e 3t=7|v<4=8|v<5=9|1>0=10where u=[n!!0|n<-p];v=l$nub u;t=b(\n->l[x |x<-u,x==n])q;w=all(==(last$p!!0))[last s|s<-p];y=elem""[u\\s|s<-b(take 5.flip drop('A':q))[0..10]];z=y&&w
0%_=[[]]
n%(x:y)=b(x:)((n-1)%y)++n%y
_%_=[]
h#t|let p=h++t;c i=minimum$b r$concat$b(5%)$b(++i)((7-l i)%([n:[s]|n<-q,s<-"SCHD"]\\p))=(c p,c t)

```

Try it online!

Ungolfed (same idea, slightly different structure):

```
import Data.List -- for (\\)
numbers = "23456789TJQKA"

e=elem

rank_hand hand
    |royal_flush=1
    |straight_flush=2
    |four_of_a_kind=3
    |full_house=4
    |flush=5
    |straight=6
    |three_kind=7
    |two_pair=8
    |pair=9
    |1>0=10
    where nums = [head n | n<-hand]
          unique = length $ nub nums
          counts = map (\n->length [x | x<-nums, x==n]) numbers
          pair = unique < 5
          two_pair = unique < 4 -- could also be 3 of a kind, but that's ok
          three_kind = e 3 counts
          flush = all (==(last$hand!!0)) [last s|s<-hand]
          straight = elem "" [nums\\s | s <- map (take 5.flip drop ('A':numbers))[0..10]]
          full_house = unique < 3
          four_of_a_kind = e 4 counts
          straight_flush = straight && flush
          royal_flush = straight_flush && elem 'A' nums && elem 'K' nums

-- taken from https://codegolf.stackexchange.com/a/34496/66460
-- k%l finds combinations of size k from a list l
0%_=[[]]
n%(x:y)=map(x:)((n-1)%y)++n%y
_%_=[]

-- find every combination available to each player, and rank each one.
-- could be golfed a lot more.
h#t=let p=h++t
        a=[n:[s]|n<-numbers,s<-"SCHD"]\\p
        c i=minimum $ map rank_hand $ concat $ map (5%) $ map (++i) ((7-length i)%a)
    in(c p,c t)

```

Very slow, since there's no special casing at all (e.g. if no cards have been shown, a royal flush is always possible.) Most of my golfing effort went into the `rank_hand` function; `#` can be golfed a lot more by combining maps and such.

`hand#table` calculates the optimal scores for you and your opponent. Does no error checking.
> 3 votes

---
Tags: code-golf, combinatorics, permutations, card-games
---


title: Eyeballing the bits

text:
# Question
Title: Eyeballing the bits
Eyeballing the binary values printed as ovals and sticks is not so easy... To help with that, you must write a function (or a program) that prints numbers in custom binary representation.
So I want to take a number, say 3 (`00000011`) and output the bits in user-defined format, for example with space separated pairs:

```
00 00 00 11

```

or, say, in reversed order and with some decorators, e.g.:

```
11_00_00_00

```

Furthermore, there must be possibilty to show '0' and '1' as custom characters to distinguish them better, e.g.:

```
XX oo oo oo

```

So the challenge is to write the code which does that all whithin the following specification.

## Specification

The function takes input like this: **f(A, mask, zeros, ones)**

Parameters:

**A** -- input number -- any (unsigned) integer in range 0-255.
**mask** -- a string parameter which defines the construction of the output.
**zeros** -- a string of the same length, defines 'zero' glyphs for each output slot.
**ones** -- a string of the same length, defines 'one' glyphs for each output slot.

**Rules for the output construction:**

Look at this image with example closely to understand how the output is generated:

So only the *single digits* in the mask are parsed and replaced by corresponding bits of A, other characters are *left as is*. Further, if the value of the taken bit is 1 then it shows up in the final output as "X" and if it is 0 then it shows up as "o". In the above example all four taken bits are "1" so we see "X" in all slots.

If the input number was 128, then, logically, the output would be `X foo bar ooo`. Characters in parameters "zeros" and "ones": any printable ASCII chars, assume they are always char-aligned with the mask.

**Notes**:

* Bits are 0-indexed: 0th bit is the MSB.
* Assume that digits 8,9 are not allowed in the mask string.
* Input Strings include any printable ASCII chars.
* 'Zeros' and 'ones' are char-aligned with the mask.
* For special characters/modifiers in your language: we can assume they will not appear in the input string.

For the clarity, see more examples.

## Input -\> Output examples

Output all 8 bits in common order with a space delimiter, in common oval-and-stick notation:

```
mask  =  "0123 4567"
zeros =  "0000 0000"
ones  =  "1111 1111"

A=1 ->    0000 0001

```

Output in reversed order, in dash-and-glyph notation:

```
mask =    "| 7654 3210 |"
zeros=    "  ---- ----  "
ones =    "  ssss ssss  "

A=1  ->    | s--- ---- |
A=3   ->   | ss-- ---- |
A=128->    | ---- ---s |

```

Diverse notations in one output, e.g. for packed data:

```
mask =       "0 | 123 4567"
zeros=       "    --- ----"
ones =       "X   kkk ssss"

A= 15  ->       | --- ssss
A= 16  ->       | --k ----
A= 32  ->       | -k- ----
A= 128 ->     X | --- ----
A= 255 ->     X | kkk ssss

```

Repeating patterns:

```
mask =    "| 7 66 555 4444 |"
zeros=    "  . .. ... ....  "
ones =    "  0 00 000 0000  "

A= 0 ->    | . .. ... .... |
A= 1 ->    | 0 .. ... .... |
A= 2 ->    | . 00 ... .... |
A= 3 ->    | 0 00 ... .... |
A= 4 ->    | . .. 000 .... |

```

---

## Update

The rules have been slightly simplified - the program must print one number only (not array/list of numbers as it was proposed initially).

# Answer
# Ruby, 48 bytes

```
->a,f,*b{f.gsub(/\d/){b[a[55-$&.ord]][$`.size]}}

```

The zeroes and ones parameters are treated as an array (`*b`) and with the zeroes parameter is stored in `b[0]` and the ones parameter stored in `b[1]`.

The mask parameter `f` has each digit (`/\d/`) substituted with a character from the appropriate array. The special variable `$``, which holds the text leading up to the current match, is (ab)used here to keep track of position.

Ruby's bit indexing calls 0 the least-significant bit, but the challenge calls 0 the most significant bit. ASCII subtraction from 55 (the '7' character) yields a usable Ruby bit index.

Try it online!
> 3 votes

# Answer
# JavaScript (ES6), 57 bytes

```
(A,M,O,I)=>M.replace(/[\d]/g,(d,i)=>(A>>7-d)%2?I[i]:O[i])

```

```
f=
(A,M,O,I)=>M.replace(/[\d]/g,(d,i)=>(A>>7-d)%2?I[i]:O[i])

console.log( f(1, "0123 4567", "0000 0000", "1111 1111") )
console.log( f(3, "| 7654 3210 |", "  ---- ----  ", " ssss ssss ") )
console.log( f(4, "| 7 66 555 4444 |", "  . .. ... ....  ", "  0 00 000 0000  ") )
```
> 2 votes

# Answer
## Mathematica, 131 bytes

```
""<>Table[(f/@{##2})[[x[[i]],i]],{i,Length[x=(f=Characters)@#2/.Table[ToString@i->2+Floor[#/2^(7-i)]~Mod~2,{i,0,7}]/._String->1]}]&

```
> 1 votes

# Answer
# Perl 6, 60 bytes

```
->\a,$_,\o,\z{S:g|\d|{substr (z,o)[a+>(7-$/)%2],$/.from,1}|}

```
> 1 votes

# Answer
## Python, 97 bytes

```
lambda A,M,Z,O:"".join([[Z,O][1&(A>>7-int(d))][i] if d.isdigit() else d for i,d in enumerate(M)])

```
> 1 votes

# Answer
# q/kdb+, ~~86~~ 64 bytes

**Solution:**

```
f:{[A;M;Z;O]@[M;m;:;((-8#0b vs A)"I"$'M m)(Z;O)'m:(&)M in .Q.n]}

```

**Examples:**

```
q)f[1;"0123 4567";"0000 0000";"1111 1111"]
"0000 0001"
q)f[1;"| 7654 3210 |";"  ---- ----  ";"  ssss ssss  "]
"| s--- ---- |"
q)f[15;"0 | 123 4567";"    --- ----";"X   kkk ssss"]
"  | --- ssss"
q)f [0;"| 7 66 555 4444 |";"  . .. ... ....  ";"  0 00 000 0000  "]
"| . .. ... .... |"

```

**Explanation:**

Pull out indices where input mask `M` is a numeral, call it `m` this is where we will be modifying the input mask. Take the numerals out of the string, cast to integers and then index into our 8-bit array to get the correct ordering. Use this 8-bit array to index into either `O` (if 1 is set) or `Z` (if 0 is set), and then index into these lists at the indices given by `m`. Finally apply (`:`) this new list to the original mask at indices `m`.

```
{[A;M;Z;O]                                                   } / lambda function with 4 parameters
          @[ ; ; ;                                          ]  / apply, applies 3rd parameter to 1st parameter at indexes from parameter 2 with parameter 4 :)
                   (-8#0b vs A)                                / convert input number to binary (64 bit), take the last 8 items
                                              m:(&)M in .Q.n   / returns indices where mask is in "0123..789", stores in variable m
                               "I"$'M m                        / index into mask at indices m, then cast these numbers to an integer array
                  (                    )                       / we then index into our 8 bits a these offsets to get the output order
                                        (Z;O)                  / 2-item list of the zeroes and ones mask
                                             '                 / take each item on the left and right and apply them to (Z;O) (ie index in at 0 / 1 and then 123..67)
            M m :                                              / apply *this* list to M at each index given by m

```

**Notes:**

Could shave off a further 14 bytes if we were allowed to give the arguments in the form:

`[A;M;(Z;O)]`

as q allows for up to 3 arguments to be given to a function without being explicitly named (they are `x`, `y` and `z` respectively):

```
f:{@[y;m;:;((-8#0b vs x)"I"$'y m)z'm:(&)y in .Q.n]}

```
> 1 votes

---
Tags: code-golf, string, binary
---


title: Draw the XNOR digital timing diagram

text:
# Question
Title: Draw the XNOR digital timing diagram
Below is a (schematic) Digital timing diagram, for the XNOR logic gate.

```
    ┌─┐ ┌─┐ ┌─────┐ ┌─┐ ┌─┐ ┌───┐
A ──┘ └─┘ └─┘     └─┘ └─┘ └─┘   └──
  ┌───┐ ┌───┐ ┌─┐ ┌─────┐   ┌─┐ ┌─┐
B ┘   └─┘   └─┘ └─┘     └───┘ └─┘ └
    ┌─────┐   ┌─┐   ┌─┐   ┌───┐
X ──┘     └───┘ └───┘ └───┘   └────

```

Your goal is to reproduce it exactly as depicted.

Rules:

* You can either print it or return a multiline string;
* Arbitrary number of traling and/or leading newlines are allowed;
* Trailing (but not leading !) whitespace is allowed;
* If you can not use the extended ASCII box-drawing characters, you may substitute them for the unicode equivalents (at no byte penalty).

This is so the shortest answer in bytes wins.

**Binary Representation**

For your convenience, binary representation of the diagram above is as follows:

```
INP A=0101011101010110
INP B=1101101011100101
  ___
X=A⊕B=0111001001001100

```

**Sample Output**

**Sidenote**

While working on this question, I've implemented two different bash solutions for it, one is 122 characters/bytes long (as depicted above), and another one is exactly 100 bytes long.

I do not have plans to post them (as I don't normally post answers to my own questions), so that is just for reference.

I also believe that at least some sub-100 byte solutions are possible.

# Answer
# 05AB1E, 101 bytes ~~\+ 5 UTF-8 bytes = 116 Total Bytes =~~ ***106 Bytes***

(LEGACY 05AB1E VERSION, NO LONGER ON TIO)

```
•=(Ín§Àoà`œ¯_eè8y1ÜŸ,Ú®:¹$:,õKA–x[Âì0ãXÔfz}y×ì¹Ï½uEÜ5äÀTë@ºQÈ™ñó:ò…Eä•6B"102345"" ┌─┐└┘"‡6ävyN" A B X"èì}»

```

Try it online!

The compression:

```
•=(Ín§Àoà`œ¯_eè8y1ÜŸ,Ú®:¹$:,õKA–x[Âì0ãXÔfz}y×ì¹Ï½uEÜ5äÀTë@ºQÈ™ñó:ò…Eä•
# Pattern, converted to base-6 in base-6=214.

111023102310222223102310231022231112251425142511111425142514251114221022231022231023102222231110231023151114251114251425111114222514251411102222231110231110231110222311111225111114222514222514222511142222
# Actual base-6 pattern.

1110231023102222231023102310222311
1225142514251111142514251425111422
1022231022231023102222231110231023
1511142511142514251111142225142514
1110222223111023111023111022231111
1225111114222514222514222511142222
#Pattern split into chunks of 34.

   ┌─┐ ┌─┐ ┌─────┐ ┌─┐ ┌─┐ ┌───┐
 ──┘ └─┘ └─┘     └─┘ └─┘ └─┘   └──
 ┌───┐ ┌───┐ ┌─┐ ┌─────┐   ┌─┐ ┌─┐
 ┘   └─┘   └─┘ └─┘     └───┘ └─┘ └
   ┌─────┐   ┌─┐   ┌─┐   ┌───┐
 ──┘     └───┘ └───┘ └───┘   └────
# Pattern after replacing 0,1,2,3,4,5 with appropriate blocks.

```

The conversion:

```
6B                                   # Convert back to base-6.
  "102345"" ┌─┐└┘"‡                  # Replace numbers with appropriate counterparts.
                   6ä                # Split into 6 equal parts (the rows).
                     vy           }  # For each row (chunk).
                       N" A B X"èì   # Push label at index [i], prepend to line.
                                   » # Print all separated by newlines.

```

Using the **CP-1252** encoding.
> 5 votes

# Answer
# Bubblegum, 76 bytes

```
00000000: 92d6 3000 5431 1505 1403 50e8 4e0a aafc  ..0.T1....P.N...
00000010: 9f62 15e6 a3ff 61fa dc05 e06d 8b66 cbc7  .b....a....m.f..
00000020: e6b6 cff8 519a b85a 3eb6 b67d 95c0 0feb  ....Q..Z>..}....
00000030: 35b5 521d 7f7e 68af a916 fa20 d999 564d  5.R..~h.... ..VM
00000040: 1f03 d559 59ed 265c f243 42be            ...YY.&\.CB.

```

Try it online!

Uses box-drawing characters from the VT100 alternate character set, which TIO can’t demonstrate. Run in a UNIX terminal for best results. My terminal converts the ACS to UTF-8 on copy-and-paste, so you can see the effect here.

```
anders@change-mode:/tmp$ bubblegum xnor.zlib
    ┌─┐ ┌─┐ ┌─────┐ ┌─┐ ┌─┐ ┌───┐
A ──┘ └─┘ └─┘     └─┘ └─┘ └─┘   └──
  ┌───┐ ┌───┐ ┌─┐ ┌─────┐   ┌─┐ ┌─┐
B ┘   └─┘   └─┘ └─┘     └───┘ └─┘ └
    ┌─────┐   ┌─┐   ┌─┐   ┌───┐
X ──┘     └───┘ └───┘ └───┘   └────
▒┼␍␊⎼⎽@␌␤▒┼±␊-└⎺␍␊:/├└⎻$

```

Well, the challenge didn’t say we need to take the terminal back *out* of ACS mode before returning to the shell. Good luck with that.
> 4 votes

# Answer
# Ruby, 113 bytes

counting printed symbols as one byte as authorised by the challenge (I was surprised to discover they are actually 3 bytes.)

```
6.times{|i|s=' A B X'[i]
'D]zunIWkF]nIRukFH'.bytes{|b|s+='   ┌─┐───┘ └'[(b*2>>i/2*2&6)-i%2*6,2]}
s[1]=' '
puts s}

```

6 lines of output lends itself to an encoding of 6 bits per each character of the magic string. But the magic string characters actually encode for each transition thus:

```
least significant bit 0 New value for A
                      1 Current value for A
                      2 New value for B
                      3 Current value for B
                      4 New value for X
                      5 Current value for X
most significant bit  6 Always 1 (to remain in printable range)

```

This is decoded to find the 2 characters that must be printed for each transition (the first of which is either space or a horizontal line.) The 8-character strings for the upper and lower rows overlap: The last two characters for the upper row `11` are two horizontal lines, which matches with what is needed for the first two characters of the lower row `00`. The 8 characters for the lower row wrap around: they are last 6 and first 2 characters of the symbol string.

**Ungolfed code**

```
6.times{|i|s=' A B X'[i]               #iterate through 6 lines of output. Set s to the 1st character.
  'D]zunIWkF]nIRukFH'.bytes{|b|        #for each byte in the magic string
     s+='   ┌─┐───┘ └'[(b*2>>i/2*2&6)- #add 2 bytes to s, index 0,2,4, or 6 of the symbol string depending on relevant 2 bits of the magic string.
     i%2*6,2]                          #if the second (odd) row of a particular graph, modify index to -6,-4,-2, or 0
  }                                    #(ruby indices wrap around. mystring[-1] is the last character of the string.)
  s[1]=' '                             #replace intitial ─ of the curve with space to be consistent with question
  puts s                               #output line
}

```
> 3 votes

# Answer
## PowerShell, 255 characters, 265 bytes (UTF-8)

```
$a='    012 012 0111112 012 012 01112
A 113 413 413     413 413 413   411
  01112 01112 012 0111112   012 012
B 3   413   413 413     41113 413 4
    0111112   012   012   01112
X 113     41113 41113 41113   41111'
0..4|%{$a=$a-replace$_,('┌─┐┘└'[$_])};$a

```

This works on my computer, but doesn't seem to parse the bytes correctly on TIO...

This sets `$a` to be a multi-line string filled with numbers and spaces, then loops `0..4|%{...}`. Each iteration, we `-replace` the appropriate digit `$_` with the appropriate character `'┌─┐┘└'[$_]` and store it back into `$a`. Then, we just leave `$a` on the pipeline and output is implicit.
> 2 votes

# Answer
## JavaScript (ES6), ~~163~~ ~~158~~ 154 bytes

NB: counting UTF-8 characters as bytes, as authorized by the challenge.

```
_=>[..." A B X"].map((c,i)=>c+" "+[...Array(33)].map((_,j)=>j%2?" ─"[p^i&1]:" ┐┌─└┘ "[p+(p=[27370,42843,12878][i>>1]>>j/2&1)*2+i%2*3]).join``,p=0).join`
`

```

### Demo

```
let f =

_=>[..." A B X"].map((c,i)=>c+" "+[...Array(33)].map((_,j)=>j%2?" ─"[p^i&1]:" ┐┌─└┘ "[p+(p=[27370,42843,12878][i>>1]>>j/2&1)*2+i%2*3]).join``,p=0).join`
`

console.log(f())
```

*Saved 4 bytes thanks to Neil*
> 2 votes

# Answer
## C, ~~213~~ 205 bytes

For a change, the C program size, on this challenge, isn't completely ridiculous compared to other languages.

```
#define X(a) u[i]=C[a],l[i++]=C[(a)+4]
p(n,c){char u[34],l[34],*C=" ┐┌──└┘ ",i=0;while(i<34)X(n&3),n>>=1,X((n&1)*3);printf("  %.33s\n%c %.33s\n",u,c,l);}main(){p(0xD5D4,'A');p(0x14EB6,'B');p(0x649C,'X');}

```

Ungolfed, define expanded, and commented:

```
p(n,c){
    // u is the upper line of the graph, l the lower line
    char u[34],l[34],*C=" ┐┌──└┘ ",i=0;
    while(i<34)
        u[i]=C[n&3],            // using the two LSBs to set the transition char depending on the current and next state
        l[i++]=C[(n&3)+4],      // do for both upper and lower lines
        n>>=1,                  // shift bits right to go to next state
        u[i]=C[(n&1)*3],        // using only the LSB to set the "steady" char depending on current state only
        l[i++]=C[((n&1)*3)+4];  // do for both upper and lower lines
    printf("  %.33s\n%c %.33s\n",u,c,l);
}
main() {
    // Call p for each graph
    // Constants are chosen so the display is consistent with the request.
    // Each bit represents a state, but the order is reversed
    // (leftmost is put on lowest significant bit, after a 0)
    p(0xD5D4,'A');p(0x14EB6,'B');p(0x649C,'X');
}

```

Note: the *C* string must *not* contain unicode characters. All displayable characters must be plain old 8-bit chars (but they may be chosen in the extended range). So basically, the validity of the output depends on your code page.
> 2 votes

# Answer
# tcl, 221 chars, 299 bytes

```
lmap {b _ n u A V} {"   " ┌─────┐ ┌───┐ └───┘ ┌─┐ └─┘} {puts "[set S \ $b][set m $A\ $A] $_ $m $n
A ──┘ [set w $V\ $V][set s \ $S]$w $V$b└──
  $n $n $A $_$b$m
B ┘$b$V$b$w$s$u $V └
$S$_$b$A$b$A$b$n
X ──┘$s$u $u $u$b└────"}

```

can be run on: http://rextester.com/live/VVQU99270
> 1 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity, logic-gates
---


title: Impossible cube maybe

text:
# Question
Title: Impossible cube maybe
# Problem

Given an input `a` where a is a truthy/falsy value output the exact impossible cube below if truthy and the exact normal cube below if falsey.

Input `truthy`:

```
         ___________________________________
        / _______________________________  /|
       / / _____________________________/ / |
      / / /| |                         / /  |
     / / / | |                        / /   |
    / / /| | |                       / / /| |
   / / / | | |                      / / / | |
  / / /  | | |                     / / /| | |
 / /_/___| | |____________________/ / / | | |
/________| | |_____________________/ /  | | |
| _______| | |____________________ | |  | | |
| | |    | | |___________________| | |__| | |
| | |    | |_____________________| | |____| |
| | |   / / _____________________| | |_  / /
| | |  / / /                     | | |/ / /
| | | / / /                      | | | / /
| | |/ / /                       | | |/ /
| | | / /                        | |   /
| | |/_/_________________________| |  /
| |______________________________| | /
|__________________________________|/

```

Input `falsy`:

```
         ___________________________________
        / _______________________________  /|
       / / _____________________________/ / |
      / / /| |                         / /  |
     / / / | |                        / /   |
    / / /| | |                       / / /| |
   / / / | | |                      / / / | |
  / / /  | | |                     / / /| | |
 / /_/___|_|_|____________________/ / / | | |
/__________________________________/ /  | | |
| ________________________________ | |  | | |
| | |    | | |___________________| | |__| | |
| | |    | |_____________________| | |____| |
| | |   / / _____________________| | |_  / /
| | |  / / /                     | | |/ / /
| | | / / /                      | | | / /
| | |/ / /                       | | |/ /
| | | / /                        | |   /
| | |/_/_________________________| |  /
| |______________________________| | /
|__________________________________|/

```

# Rules

* Trailing whitespace allowed.
* Trailing newlines allowed.
* truthy/falsey values may be swapped (truthy for real cube and falsey for impossible cube)
* Input style should be specified
* **Shortest code in bytes wins**

# Answer
# SOGL V0.12, 145 bytes

```
─3n{_⁰
ā"¹K╚=+ƨψ≡tšÆA%εW#žt─M^_ξ0“6²⁰ _*ž}"⁵æκLνbΡ°■=μθΝv╝xxΛTγ►℮ΞyF“'№⁰┐∙ž}"⁸Βλμž╚⅔\Ρ═⁴-θ=╚_>◄4℮`ε║t“'¦⁰ā;∫0 /ž}╬5}'Æ6«@┐2Ο3∙:Aža.?X"≥YΤ%‘5n}L9ž

```

Try it Here!
This program stores the line data as 3 separate base 36-46 numbers and decodes each and `ž`s the values in the main array.
Because of the abusive way of how I draw the diagonal lines, the output has 27 lines of lines with spaces (which is allowed by the OP)

input:
0 - impossible
1 - possible

Explanation:

```
The first line is basically a substitute ⁰ with ─3n{_

ā                   push an empty array (the canvas for the whole cube)
 "...“              pushes 29714643711764388252557994982458231735529743027583646902
      6²─           base-36 decodes it
         3n{     }  for each group of 3 numbers do (where the numbers are X, Y, length)
            _         put all the contents on the stack (in the order X, Y, length)
              _*      get POP amount of underscores
                ž     in the canvas at the positions x;y (the position of the 1st char, 1-indexed) put the underscores

"...“             pushes 19564601770087915522037775830252836261712294966673526596188
     '№─          base-46 decodes it
        3n{    }  for each group of 3 numbers do
           _        put all the contents on the stack
            ┐∙      get an array of "|"s with the length of POP
              ž     in the canvas at the position x;y (position of the top char, 1-indexed) put the vertical bar

"...“                    pushes 124633728256573776407884156928319785312464662536125755768
     '¦─                 base-40 decodes it
        3n{           }  for each group of 3 numbers do
           _               put all the contents on the stack
            ā;             one below the stack put an empty array (canvas for the diagonal line)
              ∫    }       for range(length) do
               0             TMP
                 /           push "/"
                  ž          at the position (iter; 0), 1-indexed put a "/". This extends the array one line upward and causes the extra spaces.
                    ╬5     in the canvas at the position x;y(1-indexed, the top position) put the diagonal line canvas without overriding with spaces

'Æ             push 36
  6«           push 12
    @┐2Ο       push two spaces, encased in vertical bars - "| | |"
        3∙     get an array of 3 of those
          :A   save on variable A
            ž  in the canvas, at the positions 36; 12 put the array

a                 push the variable A
 .?         }     if the input is non-0, then
   X                remove the variable A off of the stack
    "≥YΤ%‘          push "|_|_|__________"
          5n        chop that into an array of strings of length 5
             L9ž  at positions 10;9 insert the top of stack (either the ["| | |","| | |","| | |"] or ["|_|_|","_____","","_____"]) in the canvas

```
> 4 votes

# Answer
# Jelly,  ~~187~~  166 bytes

```
ḣ9;⁾| ṁ5¤oµ€“µ½¿‘¦
“ _/ |/|”;€⁶;”_ṁ"“¡ẇḞ6’D¤ṃ@“Ė⁸ġṾṗ¢œƝṇRK⁹ṄẸŒÐ¤ɓḂı)ḥṆqƓị¹÷ḄƝṁPʠVW1JĊTc;[¤ÆWŒṠṬ#ʋÆ6ẉ⁷ZḷƊḤƑẹẠGḊ|qi×Ƭ®ÐėƁ1(⁸ṪU¹Bgoƭ<Gḋ×c:ȦṚƇĊ¬e*⁽%ḷİ°U’Fs27Ç¹⁸?x€15¦€19Y

```

A full program.

**Try it online!**

### How?

103 bytes are a 101 digit base 250 number, which is a base-8 compression of a possible cube, with trailing spaces added to equalise the row-lengths, without new lines, and without 18 characters from the middle of each row, like this, but without newlines:

```
         _________________
        / _____________  /|
       / / ___________/ / |
      / / /| |       / /  |
     / / / | |      / /   |
    / / /| | |     / / /| |
   / / / | | |    / / / | |
  / / /  | | |   / / /| | |
 / /_/___|_|_|__/ / / | | |
/________________/ /  | | |
| ______________ | |  | | |
| | |    | | |_| | |__| | |
| | |    | |___| | |____| |
| | |   / / ___| | |_  / /
| | |  / / /   | | |/ / /
| | | / / /    | | | / /
| | |/ / /     | | |/ /
| | | / /      | |   /
| | |/_/_______| |  /
| |____________| | /
|________________|/

```

The 8 base-8 digits represent the strings of characters:

```
1      2    3    4    5    6        7        0
"   ", "_", "/", " ", "|", "/ / /", "| | |", "_____"

```

So the compression is then like the below where `1`s, `6`s, `7`s and `0`s are to be replaced by the strings shown above:

```
111000__111/ 00___  /|11 / / 00_/ / |116| |11 / /  |1  6 | |11/ /1|1 671  6| |16 71 6 | |  6  7167 6___|_|_|__6 7/000_/ /  7| 00____ | |  771 7_7__771 | |___7____| |71/ / ___7_  / / 7  6176  7 61 7 / /1761  7/ /1 7 / /11| |1/1  7/_/0__| |  /11| |00__| | /11 |000_|/11

```

The program reverses the process and changes the characters that need changing if the cube should be an impossible one:

```
“ _/ |/|”;€⁶;”_ṁ"“¡ẇḞ6’D¤ṃ@“ ... ’Fs27Ç¹⁸?x€15¦€19Y  Main link: V
                                                     ...splitting this up...
                                                     ...Main link part 1:
“ _/ |/|”;€⁶;”_ṁ"“¡ẇḞ6’D¤ - make the list of strings of characters
“ _/ |/|”                 - list of characters = " _/ |/|"
           ⁶              - literal space character
         ;€               - concatenate €ach -> ["  ","_ ","/ ","  ","| ","/ ","| "]
             ”_           - literal = '_'
            ;             - concatenate -> ["  ","_ ","/ ","  ","| ","/ ","| ", '_']
                        ¤ - nilad followed by link(s) as a nilad:
                 “¡ẇḞ6’   -   base 250 literal = 31111555
                       D  -   convert to decimal list -> [3,1,1,1,1,5,5,5]
                "         - zip with:
               ṁ          -   mould like
                          -   -> ["   ","_","/"," ","|","/ / /","| | |","_____"]

                                                     ...Main link, part 2:
...ṃ@“ ... ’Fs27 - make the rows of a possible cube without the middle repetitions:
...              - part 1, above
     “ ... ’     - the 101 digit base 250 number
   ṃ@            - base decompression with swapped @rguments
            F    - flatten (because the digit values we are using are actually lists)
             s27 - split into chunks of length 27 (into the rows)

                                                     ...Main link part 3:
...Ç¹⁸?x€15¦€19Y - make "impossible" if need be, add the row middles and output
...              - part 2, above
       ?         -  if:
      ⁸          -    chain's left argument = V
   Ç             - ...then: call last link (1) as a monad
                 -          (make it an impossible cube - see link 1, below)
    ¹            - ...else: identity (do nothing)
            €    - for €ach
         ¦       - apply sparsely:
       15        - ...to index: 15
     x€    19    - ...this: repeat €ach nineteen times
               Y - join with newlines
                 - implicit print

ḣ9;⁾| ṁ5¤oµ€“µ½¿‘¦  Link 1, replace characters to make impossible: rows
                 ¦  apply sparsely:
            “µ½¿‘   ...to indexes: code-page indexes = [9,10,11]
                    ...this:
          µ€          for €ach:
ḣ9                      head to index 9
        ¤               nilad followed by link(s) as a nilad:
   ⁾|                     list of characters = ['|',' ']
      ṁ5                  mould like 5 = ['|',' ','|',' ','|']
  ;                     concatenate
         o              logical or (vectorises) with the row
                          (which has the effect of appending the rest of the row)

```
> 9 votes

# Answer
## JavaScript (ES6),  ~~352~~   ~~344~~  333 bytes

*Saved 2 bytes thanks to @YairRand*

```
x=>[...'mnopqrstuvwxyz01~'].reduce((p,c)=>(l=p.split(c)).join(l.pop()),`1yup
1z uux z|
1/z uu_/z |
yqswtqvy|
yys wtyvq|
qs0t sw
ys 0ts w
 snt/v0
v_/x${x?0:'|_|_|'}m/v 0
/~_${b=x?0:'o_'}p/zn
| ~${b}m wnrynuo_0__0ryywp0owryv p0_ vr st0/vrst 0vr/vtn/zrvtqwyzr/_/pow z
wuu__wz
|um|/~xo1yyq0w |z /q o__w| |szp~t111svzr
0qy pu~ox_ny0muxx`)

```

### Demo

```
let f =

x=>[...'mnopqrstuvwxyz01~'].reduce((p,c)=>(l=p.split(c)).join(l.pop()),`1yup
1z uux z|
1/z uu_/z |
yqswtqvy|
yys wtyvq|
qs0t sw
ys 0ts w
 snt/v0
v_/x${x?0:'|_|_|'}m/v 0
/~_${b=x?0:'o_'}p/zn
| ~${b}m wnrynuo_0__0ryywp0owryv p0_ vr st0/vrst 0vr/vtn/zrvtqwyzr/_/pow z
wuu__wz
|um|/~xo1yyq0w |z /q o__w| |szp~t111svzr
0qy pu~ox_ny0muxx`)

flag = true
setInterval(_ => o.innerHTML = f(flag = !flag), 750)
```

```
<pre id=o></pre>
```
> 5 votes

# Answer
# Charcoal, 188 bytes

```
__¶____¶_¶↙¹↓↑⁷↗³Ｐ↓⁶↗²↓↓⁷←↙⁴↓↓↓↙↗⁸↑¹²←Ｐ←×_³⁵↓↙⁹↑←×_³⁴Ｐ↗⁹↓↓¹¹↗→×_³⁴↑¹¹↖Ｐ←×_²⁹↗⁷←Ｐ←×_³¹↙←×_²⁹↓↙⁶↑←_Ｐ↗⁷↓↘Ｐ↓⁹←←Ｐ×_³²↓↓⁹↗→×_³⁰Ｐ↑⁹↖←×_²⁷↗⁶←←↙⁵↘→→↗⁵ＵＯ²¹±²_↗↗Ｐ×_¹⁹←↙|←Ｐ↑²←←↑²ＦＮＵＯ⁵±³ |↑↑Ｐ↑⁴Ｆ²«→→Ｐ↑⁶

```

Try it online! Link is to falsy version; change the input from `0` to `1` for the truthy version. Here is the approximate verbose code for the above program:

```
Print("__\n____\n_\n");

```

Print the part of the back visible through the right "hole".

```
Print(:DownLeft, 1);
Move(:Down);
Print(:Up, 7);
Print(:UpRight, 3);
Multiprint(:Down, 6);
Print(:UpRight, 2);
Move(:Down);
Print(:Down, 7);
Move(:Left);
Print(:DownLeft, 4);

```

Print the right "hole".

```
Move(3, :Down);
Move(:DownLeft);
Print(:UpRight, 8);
Print(:Up, 12);
Move(:Left);
Multiprint(:Left, Times("_", 35));
Move(:Down);
Print(:DownLeft, 9);
Move(:Up);
Print(:Left, Times("_", 34));
Multiprint(:UpRight, 9);
Move(:Down);
Print(:Down, 11);
Move(:UpRight);
Print(Times("_", 34));
Print(:Up, 11);

```

Print the outer edge of the cube.

```
Move(:UpLeft);
Multiprint(:Left, Times("_", 29));
Print(:UpRight, 7);
Move(:Left);
Multiprint(:Left, Times("_", 31));
Move(:DownLeft);
Print(:Left, Times("_", 29));
Move(:Down);
Print(:DownLeft, 6);
Move(:Up);
Print(:Left, "_");
Multiprint(:UpRight, 7);

```

Print the top "hole" of the cube.

```
Jump(1, 2);
Multiprint(:Down, 9);
Move(2, :Left);
Multiprint(Times("_", 32));
Move(:Down);
Print(:Down, 9);
Move(:UpRight);
Print(Times("_", 30));
Multiprint(:Up, 9);
Move(:UpLeft);
Print(:Left, Times("_", 27));

```

Print the front "hole" of the cube.

```
Print(:UpRight, 6);
Move(2, :Left);
Print(:DownLeft, 5);
Jump(3, 1);
Print(:UpRight, 5);
Oblong(21, Negate(2), "_");
Move(2, :UpRight);
Multiprint(Times("_", 19));
Move(:Left);
Print(:DownLeft, "|");
Move(:Left);
Multiprint(:Up, 2);
Move(2, :Left);
Print(:Up, 2);

```

Print the part of the back visible through the front "hole".

```
for (InputNumber()) Oblong(5, Negate(3), " |");

```

Make the cube impossible if necessary.

```
Move(2, :Up);
Multiprint(:Up, 4);
for (2) {
    Move(2, :Right);
    Multiprint(:Up, 6);
}

```

Print the part of the back visible through the top "hole".
> 3 votes

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


title: A Bit of a Pickle

text:
# Question
Title: A Bit of a Pickle
Python's pickle module is used for serialisation, allowing one to dump an object in a way such that it can be later reconstructed. For this, pickle uses a simple stack-based language.

To keep things simple, we will be dealing with a small subset of this language:

```
(              Push a mark to the stack
S'abc'\n       Push a string to the stack (here with contents 'abc')
l              Pop everything up to the last mark, wrapping all but the mark in a list
t              Pop everything up to the last mark, wrapping all but the mark in a tuple
.              Terminate the virtual machine

```

Your task is to implement this subset of the language. Note that `\n` is a literal newline here, and newlines are actually important to the language.

For those familiar with GolfScript or CJam-like languages, `(` and `l/t` operate similarly to `[` and `]` respectively.

# Input

To keep things simple, the input will always be valid. In particular, you may assume the following about the input:

* Strings will only consist of lowercase letters and spaces `[a-z ]`, and will always use single quotes.
* There will be no extraneous characters, with all instructions being as specified above. For example, this means that newlines will only ever occur after strings.
* Every `l/t` has a matching `(` before it and every `(` has a matching `l/t` after it. There will also be at least one `(`.
* There will be exactly one `.`, and it will always be the final character.

You may take input via command line, STDIN or function argument. You may use a single newline-escaped string instead of a multiline string if you wish, but please specify this in your answer.

# Output

Output should be a representation of the final object, printed to STDOUT or returned **as a string**. Specifically:

* Strings are represented by opening and closing single quotes with content in between, e.g. `S'abc' -> 'abc'`. You may not use double quotes for this challenge, even though they are allowed in Python.
* Lists are represented by comma-separated elements surrounded by `[]` (e.g. `['a','b','c']`), while tuples are repsented by comma-separated elements surrounded by `()` (e.g. `('a','b','c')`).
* Spaces don't matter, e.g. `('a', 'b', 'c' )` is okay.
* **You cannot have a comma before the closing bracket.** Note that this is intentionally different from Python syntax rules to make things easier for most languages, and also to make it harder to simply build the list/tuple in Python then output it, due to how the single-element tuple is represented (for this challenge, we need `('a')` as opposed to `('a',)`).

## Examples

The above text might seem daunting, but the following examples should make things a bit clearer.

```
(l.

```

**Possible output:** `[]`

```
(t.

```

**Possible output:** `()`

```
(S'hello world'
l.

```

**Possible output:** `['hello world']`

```
(S'string one'
S'string two'
S'string three'
t.

```

**Possible output:** `('string one', 'string two', 'string three')`

```
(S'a'
(S'b'
S'c'
lt.

```

**Possible output:** `('a',['b','c'])`

```
((S'a'
S'b'
(lS'c'
t(S'd'
tl.

```

**Possible output:** `[('a', 'b', [], 'c'), ('d')]`

```
((S'a'
((S'b'
t(S'c'
lS'd'
(((ltlS'e'
S'f'
lS'g'
tl.

```

**Possible output:** `[('a',[('b'),['c'],'d',[([])],'e','f'],'g')]`

# Rules

* This is , so the code in the fewest bytes wins.
* Any functionality that is designed to work with Python pickles is not allowed.

---

Security note: In real code, only unpickle from sources you trust, or else you might get a nasty `cos\nsystem\n(S'rm -rf'\ntR.` surprise

# Answer
# CJam, 63

```
q{"Slt 1:T;L ]',*'[\+']+ ]',*'(\+')+ [
 0:T; C+"35/T=S/(C#=~}fC

```

Try it online

**Explanation:**

```
q        read the input
{…}fC    for each character C in the input
  "…"    push that long string, containing code to handle various cases
  35/    split it into (two) parts of length 35
  T=     get the T'th part; T is 1 when parsing a string and 0 otherwise
          (T is initially 0 by default)
  S/     split by space into an array of strings
  (      take out the first item (containing special characters to check)
  C#     find the index of C in that string
  =      get the corresponding string from the array
          (when C is not found, # returns -1 which gets the last array item)
  ~      execute that string

```

Now the long string with various pieces of code. Each part has a few characters to check and then a block for handling each one, and the default case.

First part: `Slt 1:T;L ]',*'[\+']+ ]',*'(\+')+ [`

```
Slt      special characters to check
######## first block, corresponding to character 'S'
1:T;     set T=1, causing the next characters to be processed with the 2nd part
L        push an empty string/array, which will be used to collect the string
######## second block, corresponding to character 'l'
]        end array
',*      join with commas
'[\+     prepend a '['
']+      append a ']'
######## third block, corresponding to character 't'
]        end array
',*      join with commas
'(\+     prepend a '('
')+      append a ')'
######## last block, corresponding to other characters (practically, '(' and '.')
[        start array

```

Second part: `(newline) 0:T; C+`

```
newline  special characters to check (only one)
######## first block, corresponding to newline
0:T;     set T=0, switching back to the first part
######## last block, corresponding to any other character (including apostrophe)
C+       append the character to the collecting string

```
> 4 votes

# Answer
# Perl, 149 bytes

I have a bad feeling that this is a poor attempt, but here goes:

```
$/=$,;$"=",";@s=[];/^\(/?$s[@s]=[]:{$p=/S(.*')/?$1:/l|t/?($l="@{pop@s}")|/l/?"[$l]":"($l)":0,push@{$s[-1]},$p}for<>=~/([(lt]|S.*?\n)/g;print$s[0][0];

```

The script has to be saved in a file and it takes input from STDIN.

Explanation:

```
# Set the input record separator to undef so that <> reads all lines at
# once
$/=$,;
# Ensure that elements of lists printed in quotes are separated by commas
$"=",";

# The stack. Initialise the bottom element with an empty array
@s=[];

# Tokens are extracted in the for loop a few lines below. Copied here for
# clarity: Read the entire input and iterate over all valid tokens of the
# pickle language
# for <>=~/([(lt]|S.*?\n)/g;
# the token is a mark - push an empty array to the stack
/^\(/ ? $s[@s]=[]
      # token is a string, push it inside the stack top
      : {$p=/S(.*')/ ? $1
                     # otherwise, remove the top and create list or tuple
                     # from it and push it inside the top element
                     : /l|t/ ? ($l="@{pop@s}") | /l/ ? "[$l]"
                                                     : "($l)"
                             : 0 # dummy value
                             # pushing of the string/list/tuple actually
                             # happens here
                             , push@{$s[-1]},$p}
# read the entire input at once and iterate over all valid tokens
for <>=~/([(lt]|S.*?\n)/g;

# in the end, the bottom element of the stack will be an array with just one
# element which is the string representation of the object
print$s[0][0];

```
> 3 votes

# Answer
# \>\<\>, 88 bytes

```
^"][">}r]
~rl?!;o11.
^0\!\
 &</\?[1&~?=1l","
 1/\ii:"'"=?v44.
>i9%0$.     >r]i~

 ")("\

```

Fun with jumps! Uses the fact that the ASCII codes for the 5 main commands involved, mod 9, are:

```
S -> 2
l -> 0
t -> 8
( -> 4
. -> 1

```

This allows each operation to be handled on its own line, which will be jumped to directly. Also uses the stack of stacks to construct each string and nested list/tuple separately before wrapping them in the required characters.
> 0 votes

# Answer
# Julia + ParserCombinator.jl ~~306~~ 240

With my latest set of revisions I no longer think a pure julia solution would be shorter.

```
using ParserCombinator
v=join
j(t)=v(t,",")
a=Delayed()
s=E"S'"+Star(p".")+Drop(Equal("'\n"))|>x->"'$(v(x))'"
i=Star(a)|E""
l=E"("+i+E"l"|>x->"[$(j(x))]"
t=E"("+i+E"t"|>x->"($(j(x)))"
a.matcher=s|l|t
f(x)=parse_one(x,a+E".")|>first

```

That was interesting. I think the coded is fairly eloquent.

* Output formatting is done at generation
* `a` `l`, `i`, `t`, and `s` are basically CFG rules
* `f` is the function that is called it brings it all together.
* the `Drop(Equal("'\n"))` is annoying -- that would ideally be written as `E"\n"` but the `E` string macro does not handle escape sequences.
* Interestingly this can trivially be converted to returning julia data-structures, it is basically removing the transforms on the RHS of `|>`s and adding `tuple` for the `t` rule
> 0 votes

# Answer
# JavaScript (ES6), 199 bytes

```
s=>(q=x=>(o=[],x.slice(0,-1).map(v=>o=[...o,v.map?q(v):`'${v}'`]),x.pop()<"m"?`[${o}]`:`(${o})`),q(eval(s[r="replace"](/\(/g,"[")[r](/[tl](?![\w ]+'\n)/g,"'$&'],")[r](/S('.+')/g,"$1,").slice(0,-2))))

```

Runs several regex replaces on the input to turn it into valid JS code, then parses that.

## Test Snippet

```
f=
s=>(q=x=>(o=[],x.slice(0,-1).map(v=>o=[...o,v.map?q(v):`'${v}'`]),x.pop()<"m"?`[${o}]`:`(${o})`),q(eval(s[r="replace"](/\(/g,"[")[r](/[tl](?![\w ]*'\n)/g,"'$&'],")[r](/S('.+')/g,"$1,").slice(0,-2))))
```

```
<select oninput="I.value=this.selectedIndex?this.value.replace(/\\n/g,'\n'):'';O.innerHTML=this.selectedIndex?f(I.value):''"><option>---Tests---<option>(l.<option>(t.</option><option>(S'hello world'\nl.<option>(S'string one'\nS'string two'\nS'string three'\nt.<option>(S'a'\n(S'b'\nS'c'\nlt.<option>((S'a'\nS'b'\n(lS'c'\nt(S'd'\ntl.<option>((S'a'\n((S'b'\nt(S'c'\nlS'd'\n(((ltlS'e'\nS'f'\nlS'g'\ntl.</select><br>
<textarea rows=10 cols=20 id=I></textarea><br><button onclick="O.innerHTML=f(I.value)">Run</button><br><pre id=O></pre>
```
> 0 votes

---
Tags: code-golf, interpreter, stack
---


title: Cryptographic quine variant

text:
# Question
Title: Cryptographic quine variant
Create a program that prints the MD5 sum of its source in the form:

```
MD5 sum of my source is: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

```

No cheating - you can't just read the source file and compute its sum. The program must not read any external information.

Of course you can use a MD5 library available for your language.

# Answer
## Python 157 149

```
r='r=%r;import md5;print "MD5 sum of my source is: "+md5.new(r%%r).hexdigest()';import md5;print "MD5 sum of my source is: "+md5.new(r%r).hexdigest()

```

### Output:

```
MD5 sum of my source is: bb74dfc895c13ab991c4336e75865426

```

Verification at ideone
> 13 votes

# Answer
## Python 2, 91 bytes

```
s="import md5;print'MD5 sum of my source is: '+md5.new('s=%r;exec s'%s).hexdigest()";exec s

```

Using the Python quine variant which doesn't require repeating everything twice. Tested on ideone.
> 14 votes

# Answer
# Perl + Digest::MD5, 89 bytes

```
$_=q(use Digest::MD5 md5_hex;say"MD5 sum of my source is: ",md5_hex"\$_=q($_);eval");eval

```

No TIO link because Digest::MD5 is not installed on TIO. Note that this requires the language conformance level to be set to 5.10 or higher (`-M5.010`; this doesn't carry a byte penalty according to PPCG rules.

## Explanation

This is yet another "print a function of the source code" challenge, meaning that it can be trivially solved via a universal quine constructor.

### Universal quine constructor

```
$_=q(…"\$_=q($_);eval");eval

```

We use the `q()` string notation (which nests) to initialize `$_`, the "default" variable that Perl uses for missing arguments. Then we `eval` with a missing argument, so that the string inside the `q()` gets evaluated.

The string inside the `q()` is a description of how to create the entire program; we specify the rest of the program literally, then use an unescaped `$_` to substitute the whole string in for the inside.

The technique thus creates a string with identical contents to the entire program's source; we could print it to produce a quine. We can also do other things to it first, though, making a universal quine constructor.

### The rest of the program

```
use Digest::MD5 md5_hex;say"MD5 sum of my source is: ",md5_hex

```

Very simple: import an MD5 builtin, then print the fixed string specified in the question (it's not worth compressing it, I believe that in Perl the decompressor would take up more space than just stating the string literally), and use the MD5 builtin on the string we got via the universal quine constructor.
> 3 votes

# Answer
# Node.js REPL (version 0.9.3), ~~96~~ 94 bytes

Using the last version of Node.js that existed when this challenge was posted. I've tracked down the November 9, 2012 documentation for Node.js' crypto module, and it did support all the functions I've used here back in the day.

```
function x(s){return require("crypto").createHash("md5").update(s+";x(x)").digest("hex")};x(x)

```

If you don't feel like installing an antique version of Node.js just to test this code, rest assured it also works in the most recent version.

## Node.js REPL (version 7.0.0), 81 bytes

And here is a version using ES6's arrow functions.

```
x=s=>require("crypto").createHash("md5").update(`x=${s};x(x)`).digest("hex");x(x)

```

**Edit**: thanks to Anders Kaseorg for pointing out an error in my Node.js 0.9.3 version, fixing which saved two bytes.
> 1 votes

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