# Question
Title: Maximal discrepancy-2 sequence with minimal entropy
### Background

As noted in the PPCG challenge Compress a maximal discrepancy-2 sequence – which inspired this challenge – the authors of the paper Computer-Aided Proof of Erdős Discrepancy Properties found a maximal discrepancy-2 sequence, namely

```
-1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1,  1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1, -1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1,  1, -1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1,  1, -1,  1, -1,  1, -1, -1, -1, -1,  1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1,  1, -1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1,  1, -1, -1,  1, -1,  1, -1,  1, -1, -1,  1, -1,  1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1, -1,  1,  1,  1, -1, -1, -1,  1,  1,  1, -1,  1, -1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1, -1,  1, -1,  1, -1, -1,  1, -1,  1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1, -1,  1, -1,  1,  1, -1,  1, -1,  1, -1, -1,  1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1,  1, -1,  1,  1, -1,  1, -1,  1, -1,  1,  1, -1, -1, -1,  1, -1,  1, -1, -1,  1,  1,  1,  1, -1, -1,  1, -1, -1, -1,  1,  1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1,  1,  1, -1, -1,  1, -1, -1, -1,  1, -1,  1,  1,  1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1, -1, -1,  1,  1,  1, -1,  1, -1, -1,  1,  1, -1, -1,  1,  1,  1, -1, -1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1,  1,  1, -1, -1, -1,  1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1, -1,  1,  1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1, -1, -1,  1,  1,  1,  1, -1, -1,  1, -1, -1,  1,  1,  1, -1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1, -1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1, -1,  1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1, -1,  1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1,  1, -1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1, -1, -1,  1,  1,  1, -1, -1, -1,  1,  1, -1,  1,  1, -1, -1, -1, -1,  1,  1,  1, -1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1, -1,  1,  1, -1, -1, -1, -1,  1,  1,  1, -1,  1,  1, -1, -1,  1,  1, -1, -1, -1, -1,  1,  1, -1,  1,  1,  1, -1, -1,  1,  1, -1, -1, -1,  1,  1,  1, -1, -1, -1, -1,  1, -1,  1, -1,  1,  1, -1,  1,  1, -1,  1,  1, -1,  1, -1,  1, -1, -1, -1, -1,  1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1, -1,  1, -1,  1, -1, -1,  1, -1,  1, -1,  1, -1,  1,  1,  1,  1, -1, -1, -1,  1, -1,  1, -1,  1,  1, -1, -1,  1, -1, -1,  1, -1,  1, -1,  1, -1,  1,  1, -1,  1, -1,  1,  1,  1, -1, -1,  1, -1,  1, -1, -1,  1, -1, -1,  1, -1,  1,  1,  1, -1, -1,  1, -1,  1,  1,  1, -1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1, -1,  1,  1, -1, -1, -1,  1,  1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1, -1,  1,  1,  1, -1,  1, -1, -1,  1,  1, -1, -1,  1, -1,  1, -1,  1,  1,  1, -1, -1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1, -1,  1,  1, -1, -1, -1,  1, -1,  1,  1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1,  1, -1,  1, -1, -1, -1, -1,  1,  1, -1, -1,  1, -1,  1,  1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1,  1,  1, -1, -1, -1, -1,  1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1, -1, -1,  1,  1,  1,  1, -1, -1, -1,  1,  1, -1, -1, -1,  1, -1,  1, -1,  1,  1, -1,  1, -1,  1,  1,  1, -1, -1,  1, -1,  1,  1, -1, -1,  1, -1,  1, -1, -1,  1, -1,  1, -1,  1,  1, -1, -1, -1,  1,  1,  1, -1,  1,  1

```

However, this is not the the only discrepancy-2 sequence of the length 1160; apart from the obvious variation of negating every term of the sequence, the are many valid variations that involve negating a pair of terms, and possibly entirely unrelated approaches that also lead to maximal sequences. The papers's authors made several design decisions that sped up their algorithm, but would a different set of decisions lead to a more compressible sequence? Let's find out!

### Definitions

Let \\$k\\$ and \\$n\\$ be positive integers. A finite sequence \\$x\_1, \dots, x\_n\\$ over \\$\\{-1, 1\\}\\$ is of discrepancy \\$d\\$ if

$$ \max\_{1\leq k\leq m\leq n} \left| \sum\_{1\leq jk\leq m} x\_{jk} \right| \leq d $$

In other words, the partial sums of the subsequences resulting of taking every \\$k\\$th term of \\$x\\$ all lie in the interval \\$\[-d, d\]\\$.

The sequence provided by the authors is of discrepancy **2**, as can be verified programmatically. For the first three values of \\$k\\$, we get the following subsequences and partial sums.

```
k = 1: -1,  1,  1, -1,  1, -1, -1,  1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1, ...
(sums) -1,  0,  1,  0,  1,  0, -1,  0,  1,  0,  1,  2,  1,  2,  1,  0,  1,  0, ...

k = 2:      1,     -1,     -1,      1,     -1,      1,      1,     -1,     -1, ...
(sums)      1,      0,     -1,      0,     -1,      0,      1,      0,     -1, ...

k = 3:          1,         -1,          1,          1,         -1,         -1, ...
(sums)          1,          0,          1,          2,          1,          0, ...

```

Later terms of the sequences of partial sums never reach **-3** or **3**.

In contrast, **1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1** is *not* a discrepancy-2 sequence.

```
k = 1:  1, -1, -1,  1,  1, -1, -1,  1,  1, -1, -1,  1
(sums)  1,  0, -1,  0,  1,  0, -1,  0,  1,  0, -1,  0

k = 2:     -1,      1,     -1,      1,     -1,      1
(sums)     -1,      0,     -1,      0,     -1,      0

k = 3:         -1,         -1,          1,          1
(sums)         -1,         -2,         -1,          0

k = 4:              1,              1,              1
(sums)              1,              2,              3

```

### Task

Write a full program or a function that takes no input, prints or returns a single discrepancy-2 sequence with 1160 terms, and abides to the following rules.

* You can use any kind of iterable (arrays, strings, etc.) that consists of exactly two different symbols: one representing **-1** and one representing **1**.
* Your output must be consistent, i.e., every time your code is run, it must output the same sequence.
* You must include the output of your program in your answer.
* Hardcoding your output sequence is allowed.
* To prevent trivial brute-force solutions, your code must finish in under a minute. For borderline-compliant solutions, I'll determine the official run time on my own machine (Intel Core i7-3770, 16 GiB RAM, openSUSE 13.2) or a sufficiently similar one if I cannot test your code on mine.
* Any built-in that is itself a valid submission to this challenge or a variation that takes the discrepancy as input (e.g., `FindMaximalDiscrepancySequence`) may not be in your answer. All other built-ins – including built-ins that calculate the discrepancy of a sequence – are allowed.

While finding a suitable sequence is a big part of the task, only your implementation contributes to your score. In other words, this is , and may the shortest code in bytes win!

### Validation

You can use this Python script to verify the output of your submission. It expects a string of comma-separated **-1**'s and **1**'s.

# Answer
> 2 votes
# C (gcc), 416 bytes

```
f(i){for(i=1160;i--;)putchar(L"\x72ca563b\xd24f18ad\xa70acd36\x59a6b345\xd669d0cb\x729b4962\xcd34ba65\x6359a2d2\x2e5c6936\x592ad729\xda652af1\xe69b4934\xc70adb50\xcc3b30dc\x96934dac\x69b1c6c3\x5b49369c\x3692ed26\xc9c6d329\xda4cf493\xa6716962\x6d349b43\xf26d349a\xa6934f22\xab14f235\xa569a4d5\xb4d26996\xd1a652e9\x9a6d2671\xa4e54bb4\x750e938d\xd369369a\x469b4d22\x69b0dacd\xb345a4f2\xb49a4d36i"[i/32]>>i%32&1?43:45);}

```

*-a ton of bytes thanks to ceilingcat!*

Try it online!

# C (gcc), 416 bytes

```
f(i){for(i=1160;i--;)putchar(L"\x72ca563b\xd24f18ad\xa70acd36\x59a6b345\xd669d0cb\x729b4962\xcd34ba65\x6359a2d2\x2e5c6936\x592ad729\xda652af1\xe69b4934\xc70adb50\xcc3b30dc\x96934dac\x69b1c6c3\x5b49369c\x3692ed26\xc9c6d329\xda4cf493\xa6716962\x6d349b43\xf26d349a\xa6934f22\xab14f235\xa569a4d5\xb4d26996\xd1a652e9\x9a6d2671\xa4e54bb4\x750e938d\xd369369a\x469b4d22\x69b0dacd\xb345a4f2\xb49a4d36i"[i/32]>>i%32&1?45:43);}

```

Try it online!

# C (gcc), 1148 bytes, non-competing

```
#include <limits.h>
#include <stdint.h>
#include <stdio.h>

#define DISCREPANCY 2
#define NTERMS 1160

#define NBITS(x) (sizeof(x) * CHAR_BIT)

static int terms[NTERMS];

/* non-branching abs */
static inline int abs_(int x)
{
    return (x ^ (x >> (NBITS(x) - 1))) - (x >> (NBITS(x) - 1));
}

/* generate and print terms */
int main(void)
{
    register int result = 0, iter, incr;

    for(iter = 0; iter < NTERMS; iter++)
        terms[iter] = 1;

    for(incr = NTERMS; incr > 0; incr--)
    {
        result = 0;

        for(iter = incr - 1; iter < NTERMS; iter += incr)
        {
            result += terms[iter];
            if(abs_(result) > DISCREPANCY)
            {
                /* undo change */
                /* result -= terms[iter]; */
                /* change term to fit requirements */
                terms[iter] = -terms[iter];
                /* do correct change */
                result += 2 * terms[iter];
            }
        }
    }

    for(iter = 0; iter < NTERMS; iter++)
    {
        if(iter == NTERMS-1)
            printf("%d\n", terms[iter]);
        else
            printf("%d, ", terms[iter]);
    }
}

```

This is my half-brute-force half-calculating solution but it breaks when you check every third term. I hope to improve it to the point where it generates a correct solution. Replace the `1` with `-1` on line 24 to negate the sequence. Please feel free to help me make this correct.

Try it online!

---
Tags: code-golf, math, sequence, combinatorics, compression
---


# Question
Title: Summing a sub-square of a quarter of an infinite chessboard
# Description of the problem

Imagine a quarter of an infinite chessboard, as in a square grid, extending up and right, so that you can see the lower left corner. Place a 0 in there. Now for every other cell in position `(x,y)`, you place the smallest non-negative integer that hasn't showed up in the column `x` or the row `y`.

It can be shown that the number in position `(x, y)` is `x ^ y`, if the rows and columns are 0-indexed and `^` represents bitwise `xor`.

## Task

Given a position `(x, y)`, return the sum of all elements below that position and to the left of that position, inside the square with vertices `(0, 0)` and `(x, y)`.

# The input

Two non-negative integers in any sensible format. Due to the symmetry of the puzzle, you can assume the input is ordered if it helps you in any way.

# Output

The sum of all the elements in the square delimited by `(0, 0)` and `(x, y)`.

# Test cases

```
5, 46 -> 6501
0, 12 -> 78
25, 46 -> 30671
6, 11 -> 510
4, 23 -> 1380
17, 39 -> 14808
5, 27 -> 2300
32, 39 -> 29580
14, 49 -> 18571
0, 15 -> 120
11, 17 -> 1956
30, 49 -> 41755
8, 9 -> 501
7, 43 -> 7632
13, 33 -> 8022

```

# Answer
> 8 votes
# Perl 6, 19 bytes

```
{sum [X+^] 0 X..@_}

```

Try it online!

The sum of the bitwise xor between all numbers in the range 0 to all inputs.

# Answer
> 7 votes
# Python 2, 49 bytes

```
lambda x,y:sum(k/-~x^k%-~x for k in range(~x*~y))

```

Try it online!

The usual div-mod trick for iterating over two ranges. Unfortunately, since we want inclusive ranges, we need to raise each input by 1, which we do with `-~`. Thanks to Bubbler for saving 2 bytes by cancelling the minuses on `-~x*-~y`.

Python 3 would be a byte longer using `//`. I tried to use the 3.8 walrus operator to cut down on the `-~x` repetition, without success.

**55 bytes**

```
f=lambda m,n:m|n>0and(m^n)+f(m-1,n)+f(m,n-1)-f(m-1,n-1)

```

Try it online!

A cute recursion, but unfortunately longer. This doesn't use anything particular about XOR -- this same method can be used to add up any two-variable function over a rectangle. The base case `m|n>0` terminates with zero when either `m` or `n` becomes negative, or (harmlessly) when both are zero.

This will time out on larger test cases due to the huge degree of recursive branching.

**52 bytes**

```
f=lambda m,n,b=1:m|n>0and(m^n)+f(m,n-1)*b+f(m-1,n,0)

```

Try it online!

A similar shorter recursion. The idea is that we can recursively travel left or down, but once we've gone left, we set to flag `b` to zero and ignore the results of any further travel down. The result is that we travel to each cell in the rectangle exactly one, like this:

```
O < O < O < O
            v
O < O < O < O
            v
O < O < O < O

```

**Other ideas**

Here are some partial ideas that didn't lead to decent golfs, but maybe someone can make use of them.

The one-dimensional summation (on a half-open range)

```
w=lambda i,n:sum(i^j for j in range(n))

```

can be expressed recursively as

```
w=lambda i,n:i+n and 4*w(i/2,n/2)+n%2*(n^i^1)+n/2

```

(Python 2 used for floor division.)

We also have an efficient formula

$$f(m-1,n-1) = \sum\_{i=0}^{\infty} {\frac{m n - |m \odot 2^{i}||n \odot 2^{i}|}{2} 2^i}$$

where \\$ \odot k\\$ is the symmetric modulo-\\$(2k)\\$ operator mapping to the range from \\$-k\\$ to \\$k\\$. This summation can be truncated where \\$2^i\\$ is bigger than the inputs, since further terms will be zero.

# Answer
> 5 votes
# Wolfram Language (Mathematica), 28 bytes

```
Array[BitXor,{##}+1,0,Plus]&

```

Try it online!

# Answer
> 4 votes
# Ruby, 36 bytes

```
->x,y{(0..y+x*y+=1).sum{|r|r/y^r%y}}

```

Try it online!

# Answer
> 3 votes
# APL (Dyalog Extended), 15 bytes

```
+/,{⊥≠/⊤⍵}¨⍳1+⎕

```

Try it online!

Full program.

### How it works

```
+/,{⊥≠/⊤⍵}¨⍳1+⎕
              ⎕  ⍝ Take a pair [x y] from stdin
           ⍳1+   ⍝ Generate indices from [0 0] to [x y] inclusive
   {     }¨      ⍝ For each pair,
       ⊤⍵        ⍝   Convert two numbers into two-column bit matrix
                 ⍝   (each column is binary representation of each number)
     ≠/          ⍝   Reduce each row with not-equals (XOR)
    ⊥            ⍝   Convert the resulting binary representation back to integer
+/,              ⍝ Sum all elements and implicit print

```

# Answer
> 3 votes
# 05AB1E, 6 bytes

```
Ý`δ^˜O

```

Try it online or verify all test cases.

**Explanation:**

```
Ý       # Push a list in the range [0,value] for each value in the (implicit) input-pair
 `      # Push both these lists separated to the stack
  δ     # Apply double-vectorized:
   ^    #  XOR them together
    ˜O  # And then take the flattened sum
        # (after which the result is output implicitly)

```

# Answer
> 3 votes
# , ~~23~~ 17 bytes

-6 bytes thanks to Bubbler!

```
1#.1#.XOR/&(i.,])

```

Try it online!

# K (oK), 25 bytes

```
{+/2/'~=/'(64#2)\''+!1+x}

```

Try it online!

Most probably can be golfed further.

# Answer
> 2 votes
# Jelly, 7 bytes

```
^þ/;RSS

```

Try it online!

A monadic link taking a pair of integers and returning an integer.

A couple of alternative 7-byters:

`Ż€^þ/SS` `‘Ḷ^þ/SS`

# Answer
> 2 votes
# Burlesque, 18 bytes

```
psqrzMPcp{q$$r[}ms

```

Try it online!

```
ps   # Parse to arr of ints
qrz  # Boxed range [0,N]
MP   # Map push
cp   # Cartesian product
{
 q$$ # Boxed xor
 r[  # Reduce by
}ms  # Map sum

```

# Answer
> 2 votes
# C (gcc), 48 bytes

```
R;f(x,y){R=++x*++y;for(y=0;--R;y+=R%x^R/x);x=y;}

```

Try it online!

# Answer
> 2 votes
# Japt `-x`, 6 bytes

```
ô ï^Vô

```

Try it

```
ô ï^Vô     :Implicit input of integers U & V
ô          :Range [0,U]
  ï        :Cartesian product with
    Vô     :Range [0,V]
   ^       :Reduce each pair by XORing
           :Implicit output of sum of resulting array

```

# Answer
> 2 votes
# Java 8, 58 bytes

```
(x,y)->{int t=++x*-~y;for(y=0;--t>0;)y+=t%x^t/x;return y;}

```

Port of *@xibu*'s C answer, so make sure to upvote him!

Try it online.

**Explanation:**

```
(x,y)->{        // Method with two integer parameters and integer return-type
  int t=++x     //  Increase `x` by 1 first with `++x`
        *-~y;   //  Create a temp integer `t`, with value `x*(y+1)`
  for(y=0;      //  Reset `y` to 0 to reuse as result-sum
      --t>0;)   //  Loop as long as `t-1` is larger than 0,
                //  decreasing it before every iteration with `--t`
    y+=         //   Increase the result-sum by:
       t%x      //    `t` modulo-`x`
          ^     //    Bitwise XOR-ed with:
           t/x; //    `t` integer-divided by `x`
  return y;}    //  And then return the result-sum `y`

```

# Answer
> 2 votes
# Clojure, 72 bytes

```
(defn s[x y](apply +(for[a(range(inc x))b(range(inc y))](bit-xor a b))))

```

Ungolfed:

```
(defn sumxy[x y]
  (apply + (for [a (range (inc x))
                 b (range (inc y)) ]
              (bit-xor a b))))

```

Tests:

```
(println (s  5 46) " <-> "  6501)
(println (s  0 12) " <-> "    78)
(println (s 25 46) " <-> " 30671)
(println (s  6 11) " <-> "   510)
(println (s  4 23) " <-> "  1380)
(println (s 17 39) " <-> " 14808)
(println (s  5 27) " <-> "  2300)
(println (s 32 39) " <-> " 29580)
(println (s 14 49) " <-> " 18571)
(println (s  0 15) " <-> "   120)
(println (s 11 17) " <-> "  1956)
(println (s 30 49) " <-> " 41755)
(println (s  8  9) " <-> "   501)
(println (s  7 43) " <-> "  7632)
(println (s 13 33) " <-> "  8022)

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES6), 41 bytes

Takes input as `(x)(y)` (or the other way around). Computes the sum recursively, the obvious way.

```
x=>g=(y,Y=y)=>~x&&(x^y)+g(y?y-1:x--&&Y,Y)

```

Try it online!

# Answer
> 1 votes
# Python 3, ~~59~~ 58 bytes

Saved a byte thanks to Neil and HyperNeutrino!!!

```
lambda x,y:sum(a^b for a in range(x+1)for b in range(y+1))

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~61~~ 52 bytes

Saved 9 bytes thanks to Arnauld!!!

```
b;s;f(x,y){for(s=b=y;~x;b--||(b=y,x--))s+=x^b;s-=y;}

```

Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), 33 bytes

```
Sum[i~BitXor~j,{i,0,#},{j,0,#2}]&

```

Try it online!

# Answer
> 1 votes
# Japt `-x`, 8 bytes

```
ò@Vò^XÃc

```

Try it

# Answer
> 1 votes
# Zsh, 31 bytes

```
eval '<<<$[' +{0..$1}^{0..$2} ]

```

Try it online!

Uses `eval` to expand the `<<<$[` `]` after expanding the lists. The TIO link adds `set -x` so you can see what the brace expansion looks like.

# Answer
> 1 votes
# Perl 5 `-pa`, 36 bytes

```
map{//;map$\+=$_^$',0..$F[0]}0..<>}{

```

Try it online!

Takes in inputs on separate lines.

# Answer
> 1 votes
# Oracle SQL, 126 bytes

This isn't a golfing language and it doesn't have a bitwise XOR operator but:

```
SELECT SUM(x+y-2*BITAND(x,y))FROM(SELECT LEVEL-1 x FROM T CONNECT BY LEVEL<x+2),(SELECT LEVEL-1 y FROM T CONNECT BY LEVEL<y+2)

```

Assumes that there is a table `T` with columns `X` and `Y` containing one row that has the input values.

So for the inputs:

```
CREATE TABLE t(x,y) AS SELECT 5,46 FROM DUAL;

```

This outputs:

> ```
> | SUM(X+Y-2*BITAND(X,Y)) |
> | ---------------------: |
> |                   6501 |
>
> ```

*db\<\>fiddle here*

---

As an aside, its only 81 characters in PostgreSQL:

```
SELECT sum(a#b)FROM t,generate_series(0,t.x)AS x(a),generate_series(0,t.y)AS y(b)

```

*db\<\>fiddle here*

But its less fun as that has a built-in XOR operator and series generation.

# Answer
> 1 votes
# Julia 1.0, 33 bytes

```
(x,y)->sum(i⊻j for i=0:x,j=0:y)

```

Try it online!

# Answer
> 1 votes
# C (gcc), 51 bytes

```
d,r;f(x,y){for(d=y;~d||(x--,d=y),~x;)r+=x^d--;d=r;}

```

Try it online!

---
Tags: code-golf, integer, bitwise
---


# Question
Title: Your Oscilloscope has ExPloDEd ! Make a sine wave
**\[ CODE GOLF\]**

---

# BAM! - Fire and Smoke

**Your Oscilloscope has exploded from one too many waves.**

---

Re-create these waves assuming the following:

* All waves are **Sine Waves**
* An amplitude of **`1`** spans **`3 lines`** (*Therefore and amplitude of `2` would span `5 lines`*) *\[Vertically\]*
* We want to see **`100`** characters worth of sine (*Can be any char*) *\[Horizontally\]*
* **`12`** characters per Period is a frequency of **`1Hz`**

```
[Amplitude of 1 and Frequency of 1Hz with a Span of 45 Characters]
>SinASCII('a1','f1')

   ...         ...         ...             >
...   ...   ...   ...   ...   ...   ...    >[cont. for 100 char]
         ...         ...         ...       >

```

---

# Inputs

Inputs can be in any format but must be explicitly stated if different from standard (*below*) and must contain:

* Amplitude
* Frequency

**Test inputs:** `[('a2', 'f0.5'), ('a4', 'f1'), ('a6', 'f2'), ('a1','f0.25')]`

---

## This is a CODE GOLF Challenge

**Some Clarification**

Because sine is a continuous function, the values must be discretized: For the case of `amplitude of 1` and `frequency of 1Hz` the "Crest" of the sine wave must be on `line 1` and the "Trough" of the sine wave must be on `line 3`.

To achieve the intermediate points, the wave points are set corresponding to ranges associated to the sections of the wave and these ranges will be relative to the amplitude.

Wikipedia - Crest and Trough

# Answer
> 2 votes
# Jelly, 21? 23 bytes

21 bytes if we may use a non-space character for the background.

```
×Ɱȷ2×30°ÆS×+1.Ḟ+Ṭ€o⁶z⁶Y

```

A full program accepting frequency (a float) and amplitude (an integer) which prints the result using `1` as the wave and  as the background.
Note: Since there is no mention of phase I have assumed we may pick any (I also asked for clarification).

**Try it online!**

# Answer
> 2 votes
# Python 3, <sup>~~128~~ \\$\cdots\\$ ~~107~~</sup> 103 bytes

Added a byte to fix and error kindly pointed out by blueteeth.
Saved ~~23~~ 27 bytes thanks to Jonathan Allan!!!
Added a byte to fix a fudge kindly pointed out by Jonathan Allan.

```
lambda a,f:[[' .'[~j<=a*sin(f*i*pi/6)+.5<-j]for i in range(100)]for j in range(~a,a)]
from math import*

```

Try it online!

Inputs an integral amplitude and a float for frequency.
Uses a period of 12 characters for 1Hz.
Returns a list of lists of characters.

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


# Question
Title: (RGS 2/5) How many strings can you count within these character classes?
# Task

Given a string composed of ASCII printable characters, return how many strings could fit the given pattern with character literals and regex-like ranges.

# Pattern string

The pattern string follows this grammar (the | means an option and the * means 0 or more occurrences of whatever was immediately to the left):

```
pattern := '' | pattern_string
pattern_string := (SAFE_CHAR | ASCII_RANGE) pattern_string*
ASCII_RANGE := '[' CHAR '-' CHAR ']'

```

where `CHAR` is any ASCII character in the range `[32, 127]` and `SAFE_CHAR` is any `CHAR` except the three characters `[`, `-` and `]`.

## Examples

Examples of pattern strings would be `a`, `[0-*]4fj`, `[a-z][4-9]D[d-B]`.

# Input

The pattern string. You can assume all ranges are well-formed and that all the second characters in the ranges have their ASCII codepoints `>=` than the corresponding first characters in the range.

# Output

The integer corresponding to the number of strings that match the given pattern string.

# Test cases

```
"" -> 1
"a" -> 1
"[*-0]" -> 7
"[0-9][0-9]" -> 100
"[a-z]d[A-z]" -> 1508
"[<->]" -> 3
"[!-&]" -> 6
"[d-z]abf[d-z]fg" -> 529
"[[-]]" -> 3
"[a-a][b-b]cde[---]" -> 1
"[0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1]" -> 4096
"[--[][--]]" -> 2303
"[[-[].[]-]]" -> 1

```

You can check this Python reference implementation that I used to generate the test cases.

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

---

This is the second challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is still 400 reputation in prizes! (See 6 of the rules)

Also, as per section 4 of the rules in the linked meta post, the "restricted languages" for this second challenge are: 05AB1E, , Jelly, Japt, Gaia, MathGolf and Stax, so submissions in these languages are not eligible for the final prize. But *they can still be posted!!*

Otherwise, this is still a regular challenge, so enjoy!

# Answer
> 14 votes
# CP-1610 machine code (Intellivision),  ~~23~~  22 DECLEs1 ≈ 28 bytes

*As per the exception described in this meta answer, the exact score is **27.5 bytes** (220 bits)*

A routine taking a null-terminated string as an inline argument through **R4** and returning the result in **R1**.

```
**2B9 001** |         MVII    #1,     R1
**2A0** | @@read  MVI@    R4,     R0
**080** |         TSTR    R0
**204 00F** |         BEQ     @@rtn
**378 05B** |         CMPI    #'[',   R0
**22C 007** |         BNEQ    @@read
**2A0** |         MVI@    R4,     R0
**00C** |         INCR    R4
**320** |         SUB@    R4,     R0
**020** |         NEGR    R0
**008** |         INCR    R0
**004 11C 1DC** |         CALL    MULT
**091** |         MOVR    R2,     R1
**220 012** |         B       @@read
**0A7** | @@rtn   JR      R4

```

### A note about subroutine calls

The CP-1610 instruction for calling subroutines is `JSR Rx, $address`. This instruction saves the return address in `Rx` instead of pushing it on the stack as many other CPUs do.

This allows to pass a block of arguments that immediately follows the function call. This is a common practice in CP-1610 programming and that's what we use here.

```
        JSR     R4,     count     ; call to subroutine through R4
        STRING  "[*-0]", 0        ; argument
        ...                       ; we will return here

```

Obviously, the subroutine is responsible for reading the correct number of arguments and eventually jumping to the expected return address.

### Full commented test code

```
        ROMW    10                ; use 10-bit ROM width
        ORG     $4800             ; map this program at $4800

PNUM    QEQU    $18C5             ; EXEC routine: print a number
MULT    QEQU    $1DDC             ; EXEC routine: signed multiplication

        ;; ------------------------------------------------------------- ;;
        ;;  main code                                                    ;;
        ;; ------------------------------------------------------------- ;;
main    PROC

        SDBD                      ; set up an interrupt service routine
        MVII    #isr,   R0        ; to do some minimal STIC initialization
        MVO     R0,     $100
        SWAP    R0
        MVO     R0,     $101

        EIS                       ; enable interrupts

        MVII    #$200,  R3        ; R3 = backtab pointer

        JSR     R4,     count     ; test cases
        STRING  "", 0
        CALL    print
        JSR     R4,     count
        STRING  "a", 0
        CALL    print
        JSR     R4,     count
        STRING  "[*-0]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[0-9][0-9]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[a-z]d[A-z]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[<->]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[!-&]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[d-z]abf[d-z]fg", 0
        CALL    print
        JSR     R4,     count
        STRING  "[[-]]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[a-a][b-b]cde[---]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[--[][--]]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[[-[].[]-]]", 0
        CALL    print

        DECR    R7                ; done: loop forever

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  prints the result of a test case                             ;;
        ;; ------------------------------------------------------------- ;;
print   PROC

        PSHR    R5                ; save the return address on the stack

        MOVR    R1,     R0        ; R0 = number to print
        MVII    #4,     R1        ; R1 = number of digits
        MOVR    R3,     R4        ; R4 = backtab pointer
        ADDI    #5,     R3        ; advance by 5 characters for the next one
        PSHR    R3                ; save R3
        CLRR    R3                ; R3 = attributes (black)
        CALL    PNUM              ; invoke the EXEC routine
        PULR    R3                ; restore R3

        PULR    R7                ; return

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  ISR                                                          ;;
        ;; ------------------------------------------------------------- ;;
isr     PROC

        MVO     R0,     $0020     ; enable display

        CLRR    R0
        MVO     R0,     $0030     ; no horizontal delay
        MVO     R0,     $0031     ; no vertical delay
        MVO     R0,     $0032     ; no border extension
        MVII    #$D,    R0
        MVO     R0,     $0028     ; light-blue background
        MVO     R0,     $002C     ; light-blue border

        JR      R5                ; return from ISR

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  our routine                                                  ;;
        ;; ------------------------------------------------------------- ;;
count   PROC

        MVII    #1,     R1        ; initialize R1 to 1

@@read  MVI@    R4,     R0        ; R0 = current character
        TSTR    R0                ; end of string?
        BEQ     @@rtn             ; if yes, return

        CMPI    #'[',   R0        ; is this a '['?
        BNEQ    @@read            ; if not, just go on with the next character

        MVI@    R4,     R0        ; R0 = ASCII code of the starting character
        INCR    R4                ; skip the '-'
        SUB@    R4,     R0        ; subtract the ASCII code of the ending character
        NEGR    R0                ; negate
        INCR    R0                ; increment
        CALL    MULT              ; compute R2 = R0 * R1
        MOVR    R2,     R1        ; and save the result in R1

        B       @@read            ; go on with the next character

@@rtn   JR      R4                ; return

        ENDP

```

### Output

*screenshot from jzIntv*

---

*1. A CP-1610 opcode is encoded with a 10-bit value (0x000 to 0x3FF), known as a 'DECLE'.*

# Answer
> 8 votes
# Haskell, ~~50~~ 48 bytes

```
f[]=1
f('[':a:b:c:s)=length[a..c]*f s
f(a:s)=f s

```

Try it online!

# Answer
> 5 votes
# JavaScript (Node.js),  ~~66 65~~  60 bytes

```
s=>(s.replace(/\[.../g,s=>r*=([,b]=Buffer(s))[3]-b+1,r=1),r)

```

Try it online!

### Commented

```
s => (                      // s = input string
  s.replace(                // find in s all occurrences of
    /\[.../g,               // '[' followed by 3 characters
    s =>                    // given the matched string s:
      r *=                  //   multiply r by:
        ([, b] = Buffer(s)) //     the difference between
        [3]                 //     the ASCII code of the 4th character
        - b                 //     and the ASCII code of the 2nd one
        + 1,                //     + 1
      r = 1                 //   start with r = 1
  ),                        // end of replace()
  r                         // return r
)                           //

```

---

# JavaScript (Node.js),  ~~65~~  64 bytes

A recursive solution.

```
f=s=>s?-~([g,b,,c]=Buffer(s),!(g^=91)*(c-b))*f(s.slice(g?1:5)):1

```

Try it online!

### Commented

```
f = s =>             // f is recursive function taking a string s
  s ?                // if s is not empty:
    -~(              //   add 1 to the result of the multiplication below
      [g, b,, c] =   //     g, b, c = ASCII codes of 1st, 2nd and 4th characters
        Buffer(s),   //
      !(g ^= 91) *   //     true if g is a '[', or false otherwise
      (c - b)        //     multiply it by the width of the ASCII range
    ) *              //   multiply by ...
    f(               //   ... the result of a recursive call
      s.slice(g ? 1  //     discard 1 character if it was not a group
                : 5) //     or 5 if it was
    )                //   end of recursive call
  :                  // else:
    1                //   stop recursion

```

# Answer
> 5 votes
# MATL, ~~22~~ 21 bytes

*1 byte saved thanks to @DeathIncarnate*

```
'\[.-.'XX"@gHKh)dQ]vp

```

Try it online! Or verify all test cases.

### How it works

```
'\[.-.'    % Push this string, to be used as regexp
XX         % Implicit input. Cell array of substrings that match the regexp
"          % For each
  @g       %   Push current substring
  HKh      %   Push 2, then 4, concatente horizontally: gives [2 4]
  )        %   Index: gives a string of two chars
  d        %   Consecutive difference (of code points)
  Q        %   Add 1
]          % End
v          % Concatenate all stack contents vertically (result may be empty)
p          % Product. Implicit display

```

# Answer
> 5 votes
# C (gcc), ~~58~~ ~~56~~ ~~54~~ ~~52~~ 50 bytes

```
f(char*s){s=*s?*s++-91?f(s):(s[2]-*s+1)*f(s+4):1;}

```

Try it online!

Thanks to @S.S. Anne for 2 bytes, and to @Arnauld for 2 more bytes!

This is a recursive solution in C.

# Answer
> 4 votes
# C (gcc), ~~77~~ \\$\cdots\\$ ~~59~~ 58 bytes

Saved 2 bytes thanks to Kevin Cruijssen!!!
Saved ~~11~~ 13 bytes thanks to Arnauld!!!

```
r;f(char*s){for(r=1;*s;)r*=*s++-91?1:1-*s+(s+=3)[-1];s=r;}

```

Try it online!

# Answer
> 4 votes
# 05AB1E, ~~31~~ ~~21~~ ~~20~~ 19 bytes

```
ü5ε2ι`Çs…[-]Q*ÆÄ>}P

```

-10 bytes thanks to an alternative approach suggested by @ExpiredData.
-2 bytes and a bugfix for `[[-[].[]-]]` thanks to *@Grimmy*.

Try it online or verify all test cases.

**Explanation:**

```
ü5          # Push all substrings of length 5 of the (implicit) input-string
  ε         # Map each substring abcde to:
   2ι       #  Uninterleave it into 2 blocks: [ace, bd]
     `      #  Push both strings separated to the stack
      Ç     #  Convert the top (bd) to a list of ASCII codepoint integers [B,D]
   s        #  Swap to get the other string (ace) at the top again
    …[-]Q   #  Check if it's equal to "[-]" (1 if truthy; 0 if falsey)
         *  #  Multiply the codepoints by that ([B,D] if truthy; [0,0] if falsey)
   ÆÄ       #  Take the absolute difference between those two (D-B if truthy; 0 if falsey)
     >      #  And increase this by 1
  }P        # After the map: take the product (which will of course be 1 for empty lists)
            # (after which this is output implicitly as result)

```

# Answer
> 4 votes
# Python 3, ~~77 75~~ 73 bytes

```
f=lambda s:s==''or'['!=s[0]and f(s[1:])or(ord(s[3])-ord(s[1])+1)*f(s[5:])

```

Try it online!

*-2 bytes thanks to @Arnauld*
*-2 bytes thanks to @KevinCruijssen*

# Answer
> 3 votes
# Raku, 37 bytes

```
{[*] map {137+[R-] .ords},m:g/\[.../}

```

Try it online!

# Answer
> 3 votes
# GolfScript, 40 38 36 29 27 bytes

```
1{\(91={(\(;(@-)}1if@*1$}do

```

Try it online!

With a bit of teamwork, Grimmy and I have this baby down fairly low. it's a shame my goofy integer trick is no longer here :( Check edits for a neat little GS trick.

```
1{\(91={(\(;(@-)}1if@*1$}do # Regex Counter
1                           # Our stack is now [str 1]
 {                      }do # Pop the top value after a run. If it's true, loop.
 {\                     }do # Swap the top two element of the stack. [1 str]
 { (91={        }1if    }do # Pop the first char and see if it's "[".
 {     {        }       }do # If so, do the following.
 {     {(\(;(@  }       }do # Get rid of the garbage in our block, leaving just the params
 {     {      - }       }do # Find the difference
 {     {      -)}       }do # Increment
 {               1      }do # If the if statement fails, instead push a 1.
                             # At this point, our stack is [1 str dif] (dif may be 1)
 {                  @   }do # Bring our 1 up. [str dif 1]
 {                   *  }do # Multiply our 1 by dif. [str dif*1]
 {                    1$}do # Duplicate our string. [str dif*1 str]
                             # At this point, if our string is empty, our stack is
                             # ["" dif*1 ""], and we see the output. If it ISN'T
                             # empty, then dif*1 is our new 1, and the next loop
                             # works with this loop's dif instead of with a 1.
                             # This functionally multiplies all the values together.

```

# Answer
> 3 votes
# , 73 bytes

```
function(s,i=el(gregexpr("\\[.-",s)),u=utf8ToInt(s))prod(u[i+3]-u[i+1]+1)

```

Try it online!

Today I learned that to include the character `[` in a regexp, you need to escape it twice: `\\[`.

# Answer
> 3 votes
# C++ (gcc), 70 bytes

```
int f(char*s){int r=1;for(;*s;)r*=*s++-91?1:1-*s+(s+=3)[-1];return r;}

```

Try it online!

# Answer
> 3 votes
# Pyth, 21 bytes

```
*Fmhs.+CMtd:Q"\[.-."1

```

Try it online!

Standard regex match with `:Q"\[.-."1`. Then, we remove the leading `[` with `td` and convert to characters with `CM`.

Next, the clever part: `.+` gives deltas between the code points, and `s` adds up the deltas. This gives just the difference between the first and last characters, ignoring the `-`.

Finally, `h` adds one, and `*F` multiplies everything together.

# Answer
> 3 votes
# brainfuck, ~~134~~ ~~125~~ 119 bytes

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

```

A commented version can be found below. Saved 9 bytes thanks to @S.S.Anne.

You can try it online, where you can check the "memory dump" to see that the final output is the correct result. In practice only works for tests where final result is `<= 255`.

You are welcome to golf my code, just keep it commented please. Then use this Python script on TIO to do the byte count and remove comments.

```
Init a cell with 91
-[+[+<]>>+]<+++
<+>>>,>+<
Mem: accumulator = 1 | left bracket = 91 | 0 | ^input char | 1 | 0
[ If something was read
Subtract the 91 from this char
<<[->+>-<<]
>>
Mem: accumulator | 0 | 91 | ^input minus 91 | 1 | 0
Use non destructive flow control to check if the input char was the beginning of a range
[ If the ascii code point was not 91 then this is a safe character
Zero out the input char
[+]
Move the acc to the right
<<<[->+<]>>>
Remove the else flag
>-] (end if)
>
[ Else the character starts a range and layout is
Mem: acc | 0 | 91 | 0 | ^1 | 0
>,<,,
Mem: acc | 0 | 91 | 0 | ^right char | left char
Subtract the two and add one
>[-<->]<+
Mem: acc | 0 | 91 | 0 | ^diff plus one | 0
                    A   B                C
Multiply the accumulator by the diff plus one
The diff plus one will be juggled around A and B
<<<<[ While the acc is still nonzero
->>>>
[-<+<<+>>>]
<[->+<]
<<<
] (end while)
Mem: ^0 | acc | 91 | 0 | diff plus one | 0
>>>>>
] (end else)
Mem: 0 | acc | 91 | 0 | ? | ^0 | 0
Reset workplace
+<
, Try reading again
Mem: acc | 91 | 0 | ^input char | 1 | 0
]
<<<.

```

# Answer
> 3 votes
# BBC BASIC V, 92 bytes

```
DEFFNf(X$):O=1:FORI=1TOLEN(X$):IFMID$(X$,I,1)="["THENO=O*(1+ASC(MID$(X$,I+3,1))-ASC(MID$(X$,I+1,1))):I=I+5
NEXT:=O

```

Defines a function that takes a single string argument and returns an integer. Note BBC BASIC V (as implemented on the Acorn Archimedes and RISC PC) was a tokenised language, so commands like `MID$` are a single byte. Unfortunately I can't find an online implementation of this, but RPCEmu can be used to test this.

# Answer
> 3 votes
# SNOBOL4 (CSNOBOL4), ~~138~~ 133 bytes

```
	I =INPUT
	P =1
	A =&ALPHABET
	L =LEN(1)
N	I '[' L . X L L . Y REM . I	:F(O)
	A X @S
	A Y @E
	P =P * (E - S + 1)	:(N)
O	OUTPUT =P
END

```

Try it online!

# Answer
> 3 votes
# Husk, 22 bytes

```
ΠmöLu…Ċ2mtf·=Ċ"[-]"2X5

```

**Try it online!**

### How?

```
ΠmöLu…Ċ2mtf·=Ċ"[-]"2X5 - string S
                    X5 - sublists of length five
          f            - filter by predicate:
           ·           -   compose two functions:
             Ċ     2   -     2-gaps (every 2nd element) (e.g. "[a-e]" -> "[-]")
            = "[-]"    -     equal to "[-]"?
        m              - map with:
         t             -   tail (e.g. "[a-e]" -> "a-e]")
 m                     - map with:
  ö                    -   compose four functions:
      Ċ2               -     2-gaps (every 2nd element) (e.g. "a-e]" -> "ae")
     …                 -     fill (e.g. "ae" -> "abcde" -- Note: "xx" -> "xx")
    u                  -     remove duplicates (e.g. "xx" -> "x")
   L                   -     length
Π                      - product

```

# Answer
> 3 votes
# Shakespeare Programming Language, ~~493~~ 398 bytes

-2 bytes thanks to Jonathan Allan

-87 bytes (!) thanks to Jo King

```
,.Ajax,.Ford,.Act I:.Scene I:.[Enter Ajax and Ford]Ajax:You cat.Scene V:.Ajax:Is I as big as the sum ofThe cube ofa big big cat the cube ofThe sum ofA big cat a cat?If notLet usScene X.Remember you.Open mind.Ford:Open mind.Open mind.You is the sum ofA cat the difference betweenYou I.Ajax:Recall.You is the product ofyou I.Scene X:.Ford:Open mind.Ajax:Is I worse zero?If notLet usScene V.Open heart

```

Try it online!

Ford is initialized as `1`. Ajax reads through the input. When he encounters a `[`, Ford reads the next and Ajax the third next character, and Ford is multiplied by the difference + 1. When Ajax reaches the end of the input, Ford opens his heart, printing his value.

The shortest representation I found of 91 (the ASCII code of `[`) is \\$91=(2\times2)^3+(2+1)^3\\$ but there might be something better.

With spaces and comments:

```
,.Ajax,.Ford,.                                         A = F = 0
Act I:.Scene I:.
[Enter Ajax and Ford]
Ajax: You is a cat.                                    F = 1
Scene V:.
Ajax: Is I as big as the sum of                        if not(A == 91) (with 91=64+27)
The cube of a big big cat                              (2*2)^3 (=64)
the cube of The sum of A big cat a cat?                (2+1)^3 (=27)
If not Let us Scene X.                                 go to Scene X
Remember you.                                          F[2] = F
Open mind.                                             F = stdin
Ford: Open mind. Open mind.                            A = stdin
You is the sum of A cat the difference between You I.  A = 1 + A -F
Ajax: Recall.                                          F = F[2]
You is the product of you I.                           F = F * A
Scene X:.
Ford: Open mind.                                       A = stdin
Ajax: Is I worse zero? If not Let us Scene V.          if not(A<0) go to Scene V
Open heart                                             print(F)

```

# Answer
> 2 votes
# Haskell, ~~66~~ 64 bytes

Non-regex solution.

```
f[]=1
f('[':a:b:c:d:s)=(1+(g c)-(g a))*f s
f(a:s)=f s
g=fromEnum

```

You can try it online! Uses the algorithm in my Python reference implementation.

# Answer
> 2 votes
# Burlesque, 29 bytes

```
"\[.-."~?{)**{3 1}si^p.-+.}mp

```

Try it online!

```
"\[.-."~?  # List of all RegEx matches
{
 )**         # Ord()
 {3 1}si     # Select values at indices 3 & 1 (start,end)
 ^p          # Unbox
 .-          # Difference
 +.          # Increment
}mp          # Map product (returns 1 for empty)

```

# Burlesque, 24 bytes

```
s1r1{@\x01\x7fr\jCB}\m{g1~=}fl

```

Try it online!

Solution that generates all possible strings and counts the number of matches.

WARNING: May take infinite time and memory.

# Answer
> 2 votes
# Java 8, ~~80~~ 76 bytes

```
r->{int c=1,i=r.length;for(;i-->1;)c*=r[i]==93?r[--i]-r[i-=2]+1:1;return c;}

```

-4 bytes thanks to *@ExpiredData*.

Try it online.

**Explanation:**

```
r->{               // Method with character-array parameter and integer return-type
  int c=1,         //  Count-integer, starting at 1
      i=r.length;  //  Index integer, starting at the length of the input
  for(;i-->1;)     //  Loop as long as the index is larger than 1,
                   //  and decrease the index every iteration by 1 right after this check
    c*=            //   Multiply the count by:
       r[i]==93?   //    If the `i`'th character of the input is a ']':
        r[--i]     //     Take the `i-1`'th character, by decreasing `i` with 1 first
        -r[i-=2]   //     And decrease it by the `i-3`'th character,
                   //     due to the earlier `--i` and by first decreasing `i` with 2 first
        +1         //     And add 1 to that difference
                   //     (NOTE: We've only decreased `i` by 3 instead of 4 here, but this
                   //      doesn't matter, since it will always be the '[' character of the
                   //      previous block in the next iteration, and thus multiplying by 1
                   //      in the else block)
       :           //    Else (single character match):
        1;         //     Keep the count the same by multiplying with 1
  return c;}       //  And then return this count as result

```

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), ~~80~~ 76 bytes

```
r=>{int c=1,i=r.Length;for(;i-->1;)c*=r[i]==93?r[--i]-r[i-=2]+1:1;return c;}

```

Try it online!

Port of @KevinCruijssen's Java answer

# Answer
> 2 votes
# Befunge-98 (PyFunge), 30 bytes

```
1v;>.@;  <
*>#^~'[-#^_~~$~\1--

```

Try it online!

### Explanation

```
1v
 >

```

Push `1` to the stack and move east in the second line

```
 >.@
#^~

```

Input character (`~`), if no input is left print the TOS (`.`) and quit the execution (`@`).

```
'[-#^_

```

Subtract `[` from the input, if the input is `[` continue east, otherwise go north.

```
1v;>.@;  <
 >

```

Case input ≠ `[`: Go back to the start of the second line.

```
*>        ~~$~\1--

```

Case input = '\[': Take the next three characters of input, discard the `-`, and compute the difference between the two remaining chars, multiply this to the current result.

Animation of the code for input `a[0-9]`:

# Answer
> 2 votes
# Python 3.8 (pre-release), 87 bytes

-5 byte thanks to @SurculoseSputum

```
lambda s:math.prod(ord(m[3])-ord(m[1])+1for m in re.findall(r'\[.-.',s))
import re,math

```

Try it online!

# Answer
> 2 votes
# Whitespace, 149 bytes

```
[S S S T    N
_Push_1][N
S S N
_Create_Label_LOOP][S N
S _Duplicate][S N
S _Duplicate][T N
T   S _Read_STDIN_as_character][T   T   T   _Retrieve_input][S N
S _Dupe][S S S T    S T S N
_Push_10][T S S T   _Subtract][N
T   S S S N
_If_0_Jump_to_Label_DONE][S S S T   S T T   S T T   N
_Push_91][T S S T   _Subtract][N
T   S S N
_If_0_Jump_to_Label_BLOCK_FOUND][N
S N
N
_Jump_to_Label_LOOP][N
S S S N
_Create_Label_BLOCK_FOUND][S N
S _Duplicate][S N
S _Duplicate][T N
T   S _Read_STDIN_as_character][T   T   T   _Retrieve][S N
S _Duplicate][S N
S _Duplicate][S N
S _Duplicate][T N
T   S _Read_STDIN_as_character][T   N
T   S _Read_STDIN_as_character][T   T   T   _Retrieve][S N
T   _Swap_top_two][T    S S T   _Subtract][S S S T  N
_Push_1][T  S S S _Add][T   S S N
_Multiply][S N
S _Duplicate][T N
T   S _Read_STDIN_as_character][N
S N
N
_Jump_to_Label_LOOP][N
S S S S N
_Create_Label_DONE][S N
N
_Discard][T N
S T _Print_as_integer]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

Since Whitespace inputs one character at a time, the input should contain a trailing newline (`\n`) so it knows when to stop reading characters and the input is done.

Try it online (with raw spaces, tabs and new-lines only).

**Explanation in pseudo-code:**

```
Integer count = 1
Start LOOP:
  Integer c = read STDIN as character
  If(c == '\n'):
    Jump to Label DONE
  If(c == '['):
    Jump to Label BLOCK_FOUND
  Go to next iteration of LOOP

Label BLOCK_FOUND:
  Integer a = read STDIN as character
  Read STDIN as character (without saving it)
  Integer b = read STDIN as character
  Integer diff = b - a
  diff = diff + 1
  count = count * diff
  Read STDIN as character (without saving it)
  Go to next iteration of LOOP

Label DONE:
  Print count as integer to STDOUT

```

# Answer
> 2 votes
# Julia 1.0, ~~62~~ 60 bytes

```
s->prod(map(x->x[2][1]-x[1][1]+1,eachmatch(r"\[(.)-(.)",s)))

```

-2 bytes thanks to Robin Ryder

Try it online!

# Answer
> 2 votes
# CJam, 23 bytes

```
1q{('[={(\(;(@-)@*\}&}h

```

Try it online!

First time programming in CJam.

```
1q{('[={(\(;(@-)@*\}&}h
1q                             Push 1, then push the input, stack = [ 1, str ]
  {('[={(\(;(@-)@*\}&}h        Execute this  while the top of the stack is truthy
   ('[=                        Pop the first char and test for equality
                    &          If it is truthy...
       {(\(;(@-)@*\}           Execute this:
        (\(;(@                   Get the two values of the character class to the top of the stack
                                 E.g "0-9]..." -> "9", "0", ...
              -)                 Subtract 2nd element char code by first and increment, stack = [1, str, diff]
                @                Get the 1 to the top of the stack, stack = [ str, 1, diff]
                 *               Multiply top 2 elements, stack = [ str, diff ]
                  \              Swap the top 2, so the string is back on top
  {                  }h        If the string is not empty, run this again. Else print the output

```

# Answer
> 2 votes
# x86-16 machine code, 25 bytes

```
B3 01       MOV  BL, 1          ; init multiplier
        C_LOOP:
AC          LODSB               ; AL = [SI], SI++
3C 20       CMP  AL, 32         ; is char less than 32
7C 10       JL   DONE           ; if so, exit
3C 5B       CMP  AL, '['        ; is char '['?
75 F7       JNZ  C_LOOP         ; if not, keep looping
AD          LODSW               ; AL = CHR_L
92          XCHG AX, DX         ; DL = CHR_L
AC          LODSB               ; AL = CHR_R
2A C2       SUB  AL, DL         ; AL = CHR_R - CHR_L
98          CBW                 ; AH = 0
40          INC  AX             ; AL = AL + 1
93          XCHG AX, BX         ; AX = multiplier
F7 E3       MUL  BX             ; multiplier *= CHR_R - CHR_L + 1
93          XCHG AX, BX         ; BX = multiplier
EB EA       JMP  C_LOOP         ; keep looping
        DONE:
C3          RET                 ; return to caller

```

As a callable function, input string in `[SI]`. Output in `BX`.

**Example test program I/O:**

# Answer
> 2 votes
# Labyrinth,  ~~53~~  50 bytes

```
1 @!{""
}    ;
,:_91-,,;,-
"    ;    `
""";;)~}*{)

```

**Try it online!**

### How?

Sets the top of the auxiliary stack to 1 and consumes characters from STDIN, if these are `[` the next three characters are consumed and the top of the auxiliary stack is multiplied by one more than the difference in ordinals of the relevant two characters. Once the EOF is reached this value is printed.

```
  1 pop main (0); * 10; + 1 (=1) -> main
  } pop main -> auxiliary  (i.e. set initial cumulative product to 1)
A , read a character, C, ord(C) -> main
    3-neighbours, top of stack is non-zero so turn
  : copy top of main -> main
  _ zero -> main
  9 pop main; * 10; + 9 (=90) -> main
  1 pop main; * 10; + 1 (=91) -> main
  - pop main (a=91); pop main (b=ord(C)); b-a -> main
B   4-neighbours
    if top of main is zero (i.e. we read a '[') then go straight:
  ,   read a character, L, ord(L) -> main  (i.e. L of [L-R])
  ,   read a character, x='-', ord(x) -> main
  ;   pop main (i.e. discard the '-' of [L-R])
  ,   read a character, R, ord(R) -> main  (i.e. R of [L-R])
  -   pop main (a=ord(R)); pop main (b=ord(L)); b-a -> main
  `   pop main; negate -> main
  )   pop main; increment -> main  (i.e. ord(R)-ord(L)+1)
  {   pop auxiliary -> main  (i.e. get current cumulative product)
  *   pop main (a); pop main (b); b*a -> main
  }   pop main -> auxiliary  (i.e. set new cumulative product)
  ~   pop main (0); bitwise NOT (~0=-1) -> main
  )   pop main; increment -> main
      3-neighbours, top of stack is zero so go straight
  ;   pop main (i.e. discard the zero, leaving infinite zeros on main)
  ;   pop main (i.e. discard another zero, sill leaving infinite zeros on main)
  """" no-ops taking us back to the first , instruction at "A"
B   elif top of main is negative (i.e. we read something <'[') then turn left:
  ;   pop main (i.e. discard the result)
  "   no-op
C     3-neighbours
      if top of main (the duplicate of ord(C)) is negative (i.e. EOF) then turn left:
  {     pop auxiliary -> main  (i.e. get cumulative product)
  !     pop main; print as decimal
  @     exit program
C     elif top of main is positive then turn right:
  "     no-op
        we hit a wall so turn around
  "     no-op
        3-neighbours, top of stack is non-zero so turn
  ;     pop main (i.e. discard this leaving infinite zeros on main)
  -     pop main (a=0); pop main (b=0); b-a=0 -> main
        4-neighbours (same location as B but facing down), top of main is zero so go straight
  ;     pop main (i.e. discard one of the infinite zeros off of main)
  )     pop main; increment (=1) -> main
        3-neighbours, top of stack is positive so turn right
  ;     pop main (i.e. discard this 1)
  ;     pop main (i.e. discard one of the infinite zeros off of main)
  """"  no-ops taking us back to the first , instruction at "A"
C     (N.B. elif top of main is zero cannot happen)
B   elif top of main is positive (i.e. we read something >'[') then turn right:
  ;   pop main (i.e. discard the result)
  )   pop main (duplicate of ord(C)); increment -> main
      3-neighbours top of main is positive so turn right:
  ;   pop main (i.e. discard that)
  ;   pop main (i.e. discard one of the infinite zeros off of main)
  """"  no-ops taking us back to the first , instruction at "A"

```

The complicated 4-neighbour `-`, along with the dead-end `"`, is a 3 byte save over the easier to follow:

```
1
}
,:_91-,,;,-
;    ;    `
""""")~}*{)
     {
    @!

```

# Answer
> 1 votes
# Charcoal, 31 bytes

```
≔⪪⮌Ｓ¹θ≔¹ηＷθＦ⁼⊟θ[≧×Ｌ…·⊟θ∧⊟θ⊟θηＩη

```

Try it online! Link is to verbose version of code. Explanation:

```
≔⪪⮌Ｓ¹θ

```

Input the pattern string, reverse it, and split it into individual characters. This allows characters to be consumed within an expression by using `Pop(q)`.

```
≔¹η

```

Start off with 1 matching string.

```
Ｗθ

```

Repeat until all of the input characters have been processed.

```
Ｆ⁼⊟θ[

```

Is this a character range?

```
≧×Ｌ…·⊟θ∧⊟θ⊟θη

```

If so then multiply the result by the length of the inclusive range between the next character and the next but three (this saves a byte over converting to ordinals manually). The characters are consumed so that a range that starts or ends at `[` does not get misinterpreted as a second range.

```
Ｉη

```

Output the result.

# Answer
> 1 votes
# Wren, 124 bytes

+10 bytes due to fixing a bug.

```
Fn.new{|i|i.count<4?1:(i.count..1).map{|x|i[x-1]+i[x-3]+i[x-5]=="]-["?1+i[x-2].bytes[0]-i[x-4].bytes[0]:1}.reduce{|a,b|a*b}}

```

Try it online!

# Answer
> 1 votes
# QuadS, 28 bytesSBCS

```
×/1--/∘⎕UCS¨⍵
\[(.).(.)
\1\2

```

Try it online!

QuadS is a language based on Dyalog APL's `⎕S` (PCRE search operator). Regex operations (2nd and 3rd lines in this case) are written in plain ASCII using PCRE syntax, and post-processing (1st line) can contain arbitrary APL expression.

### How it works

```
×/1--/∘⎕UCS¨⍵  ⍝ Post-processing function
           ¨⍵  ⍝ On each match,
       ⎕UCS    ⍝   Convert to Unicode codepoint and
    -/∘        ⍝   take the difference (e.g. [a-c] -> -2)
  1-           ⍝ 1 minus each of the above
×/             ⍝ Product over all of the above (1 if no matches)
\[(.).(.)  ⍝ PCRE regex to match
\1\2       ⍝ Extract the two significant chars from each match

```

# Answer
> 1 votes
# Pyth, 34 bytes

```
K1WgJxz\[0=*Kh-C@z+J3C@zhJ=>z+J5;K

```

Try it online!

I think this is my first Pyth submission.

# Answer
> 1 votes
# Retina, ~~77~~ 74 bytes

```
L`\[.-.
%/^\[/+/^.(.).\1/(3L$`
$.'$*
3`.
$&$&
)3T`p`_p`.
¶

~`^
.+¶$$.(1$*

```

Try it online! Link includes test cases. Explanation:

```
L`\[.-.

```

List only the ranges themselves (without the close brackets).

```
%

```

Process each range separately.

```
/^\[/+

```

Repeat while the buffer begins with a `[`.

```
/^.(.).\1/(
)

```

If the second and fourth characters are the same...

```
3L$`
$.'$*

```

... then replace that range with its length followed by a `*`...

```
3`.
$&$&
3T`p`_p`.

```

... otherwise duplicate the 3rd character and shift it back by 1 ASCII code point.

Join all of the ranges back together again.

```
^
.+¶$$.(1$*

```

Prefix `$.(1*` to turn the result (if any) into a Retina multiplication, and `.+` on its own line to turn that into a substitution command.

```
~`

```

Evaluate the result of the substitution command on the previous result, thus performing the multiplication.

# Answer
> 1 votes
# Jelly, 18 bytes

```
ṡ5Œœ€Ḣ“[-]”Ƒ$ƇOI‘P

```

Try it online!

A full program taking a string and printing an integer.

Thanks to @Grimmy for pointing out a problem with `[[-[].[]-]]`

# Answer
> 1 votes
# 05AB1E, 17 bytes

Port of Mathgeek's GolfScript answer

```
Δć91QićV¦ćY->ˆ]¯P

```

Takes input as an array of codepoints. The header code does the conversion.

```
Δ             ]     # loop until top-of-stack (initially: the input) doesn’t change:
 ć                  #  extract the first character
  91Qi        ]     #  if that character is '[' (ASCII 91):
      ćV            #   extract the first character (range start), store it in Y
        ¦           #   drop the first character ('-')
         ć          #   extract the first character (range end)
          Y-        #   subtract Y
            >       #   add 1
             ˆ      #   append to the global array
               ¯P   # output the product of the global array (1 if empty)

```

Try it online! or verify all test cases.

# Answer
> 1 votes
# Perl 5 `-p`, 42 bytes

```
$\=1;s/\[(.)-(.)]/$\*=1+ord($2)-ord$1/ge}{

```

Try it online!

# Answer
> 1 votes
# Go, ~~106~~ 98 bytes

```
func f(s string)int{r,i:=1,1
for;i<len(s);i++{if s[i-1]==91{r*=1+int(s[i+2]-s[i])
i+=3}}
return r}

```

*-8 bytes thanks to RGS for catching a cleanup that I missed.*

Try it online!

# Answer
> 1 votes
# , 22 bytes

```
ṡ5µm2⁼“[-]”ȧOḊm2I‘µ€PḢ

```

**Try it online!**

### How?

Effectively this is using M as if it were Jelly 4 years ago (except we need the trailing  as M does not have the same full-program printing as Jelly did or does). Gotta love loopholes :)

```
ṡ5µm2⁼“[-]”ȧOḊm2I‘µ€PḢ - Link: list of characters
ṡ5                     - all slices of length five
  µ               µ€   - for each:
   m2                  -   modulo two slice ("[a-e]" -> "[-]")
      “[-]”            -   "[-]"
     ⁼                 -   equal?
            O          -   ordinals
           ȧ           -   logical AND
             Ḋ         -   dequeue (N.B. 0Ḋ -> [])
              m2       -   modulo two slice ([97,45,101,93] -> [97,101])
                I      -   deltas           ([97,101] -> [5])
                 ‘     -   increment        ([5] -> [6])
                    P  - product (e.g. [[2],[],[4]] -> [8])
                     Ḣ - head (e.g. [8] -> 8)

```

# Answer
> 1 votes
# Ruby `-n`, 45 bytes

```
x=1;gsub(/\[(.)-(.)/){x*=1+$2.ord-$1.ord};p x

```

Try it online!

# Answer
> 1 votes
# x86 machine code, 30 bytes

Hexdump:

```
33 d2 f7 f0 8a 11 41 84 d2 75 01 c3 80 fa 5b 75
f3 8a 51 02 2a 11 42 f7 e2 83 c1 04 eb e6

```

Disassembly:

```
33 D2                xor         edx,edx
F7 F0                div         eax,eax
again:
8A 11                mov         dl,byte ptr [ecx]   ; load byte
41                   inc         ecx                 ; advance pointer
84 D2                test        dl,dl               ; check for end of string
75 01                jne         cont                ; not end? - continue
C3                   ret                             ; end of string? - return
cont :
80 FA 5B             cmp         dl,5Bh              ; check for ASCII_RANGE
75 F3                jne         again               ; not ASCII_RANGE? - continue
8A 51 02             mov         dl,byte ptr [ecx+2] ;
2A 11                sub         dl,byte ptr [ecx]   ; find range size
42                   inc         edx                 ;
F7 E2                mul         eax,edx             ; eax = eax * size
83 C1 04             add         ecx,4               ; skip the ASCII_RANGE part
EB E6                jmp         again               ; continue

```

A `fastcall` function: gets the pointer to the input in `ecx` and returns the result in `eax`. A pretty straightforward algorithm, which only uses `eax`, `edx` and `ecx` \- no need to save and restore registers!

It initializes `eax` to 1 and `edx` to 0 by dividing the 64-bit value `edx:eax` by `eax`.

---

To test this with Visual Studio, use the following C++ test program:

```
#include <iostream>

int __declspec(naked) __fastcall doit(const char* s)
{
    _asm
    {
        xor edx, edx;
        div eax;
    again:
        mov dl, [ecx];
        inc ecx;
        test dl, dl;
        jne cont;
        ret;
    cont:
        cmp dl, '[';
        jne again;
        mov dl, [ecx + 2];
        sub dl, [ecx];
        inc edx;
        mul edx;
        add ecx, 4;
        jmp again;
    }
}

int main()
{
    std::cout << doit("[d-z]abf[d-z]fg");
}

```

---
Tags: code-golf, string, combinatorics
---


title: L tromino tiling

text:
# Question
Title: L tromino tiling
*Inspired by this challenge from puzzling.SE.*

Polyominoes are fun - you can fill all sorts of shapes with them. But as soon as you have limits on what polyominoes you can use, you sadly start running into shapes you *can't* fill.

Today we'll be looking at the L tromino - a shape made up of three conjoined squares, in such a way that all three squares are of the same size, and there is a corner which they all share. It looks like this:

Now, given a shape made out of equal-size squares as input, the challenge is to find out whether that shape can be filled using only non-overlapping L-trominoes that are placed entirely within the input figure. You may have any number of these trominoes, and you may rotate each of them by any integer multiple of 90°.

### Rules

* The challenge is to make a program or function.
* Your program will recieve as input a two-dimensional list of values.
* Each entry in the list will contain one of two consistent values of your choice - one to signify that a square should be filled, and the other to signify that it shouldn't.
* You may assume there will be at least one row and at least one column, and that every row and every column will contain at least one cell that needs to be filled. You may also either assume that all rows have been padded to be of equal length, or that they contain nothing after their last filled cell - you may also independently assume either of those for the columns. That is to say, with `1` as squares you need to fill, and `0` as squares you need to not fill, you only need to be able to handle one of these four inputs (if given one of the others, your program's behaviour is undefined):

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

1 1
1 1 1
0 1

1 1 0
1 1 1
  1

1 1
1 1 1
  1

```
* To fill some square, you must also fill two other squares. Exactly two of the three squares filled must be diagonally adjacent to (sharing a corner with) eachothers, and they must both be orthogonally adjacent to (sharing a side with) the third.
* You may assume the input shape is contiguous.
* You may assume the input's dimensions will be no greater than 5x5.
* You may not assume the number of rows and the number of columns in the input will be equal. Originally, all this question's test cases featured inputs with an equal number of rows and columns. This was a result of poorly chosen test cases and was not intended to indicate that this would be the case for all inputs.
* Your program either needs to output a single consistent value of your choice if filling exactly the squares specified by the input with L-trominoes is possible, and any other value if it is impossible, or vice versa. For example, you may decide to output `false` if the input shape can be filled, in which case that is the only acceptable output for shapes that can be filled, and any output except `false` is acceptable for input shapes that can't be filled.
* However, the output of your program must not vary between runs given identical input, if said input is valid. That means if you have output `2` for some particular valid input, any later runs with exactly that input must also output `2`.
* This is - make your code as short as you can.

### Examples

The examples use `1` and `0` to represent squares that should and shouldn't be filled respectively, uses `true` as the only output for fillable shapes, and `false` as the only output for non-fillable shapes.

```
1  -> false

0 1
1 1 -> true

1 1 1
1 1 1
1 1 1 -> false

0 1 0
1 1 1
0 0 1  -> false

1 0 0
1 1 1
0 1 1  -> true

1 1 0
1 0 1
1 1 1
1 0 1  -> false

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1  -> true

0 1 1 1
1 1 0 1
1 1 1 1
0 1 1 0  -> true

0 1 1 1
1 1 1 1
1 1 1 0
0 1 1 0  -> true

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 0  -> true

1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1  -> false

1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1  -> true

```

# Answer
# JavaScript (ES6),  ~~196 ... 185~~  182 bytes

Takes input as a binary matrix. Returns a Boolean value.

```
f=m=>!/1/.test(m)||m.some((r,y)=>r.some((v,x)=>v&&[0,1,2,3].some(d=>([X,V]=(g=d=>[v=x+--d%2,R=m[y+--d%2]||0,R[v]])(d))[2]&g(d+1&3)[2]&&(r[x]=V[X]=R[r[x]=V[X]=R[v]=0,o=f(m),v]=1)&o)))

```

Try it online!

This algorithm is too slow for the penultimate test case on TIO, but it does find the answer on my laptop in about 90 seconds.

### How?

This is a brute force search that looks for all possible trominos in the input matrix and attempts to remove them (one at a time) until the matrix is cleared or all combinations are proven to fail.

Given a reference cell at \\$(x,y)\\$ (in blue below) and a direction \\$0\le d\le 3\\$:

* We invoke the helper function \\$g\\$ with \\$d\\$ to get a first neighbor cell (in yellow) whose coordinates are `x+(d-2)%2` and `y+(d-1)%2`.
* We invoke \\$g\\$ again with \\$(d+1)\bmod 4\\$ to get a second neighbor cell (in red).

This gives:

### Commented

```
f = m =>                         // f is a recursive function taking the matrix m[]
  !/1/.test(m) ||                // stop if m[] does not contain any 1 anymore (success)
  m.some((r, y) =>               // otherwise, for each row r[] at position y in m[]:
    r.some((v, x) =>             //   for each value v at position x in r[]:
      v &&                       //     abort right away if this cell is already empty
      [0, 1, 2, 3].some(d =>     //     otherwise, for each direction d:
        ( [X, V] = (             //       get the 1st neighbor cell
            g = d => [           //       g is a helper function taking a direction
                                 //       and returning the corresponding neighbor cell:
              v = x + --d % 2,   //         save the x-coordinate in v
              R = m[y + --d % 2] //         extract the row R[]
                  || 0,          //         (0 is used as a default object to prevent
                                 //         an access to an undefined row)
              R[v]               //         get the value of the cell
            ]                    //         return the tuple [v, R, value]
          )(d)                   //
        )[2] &                   //       get the value of the 1st neighbor cell
        g(d + 1 & 3)[2]          //       get the value of the 2nd neighbor cell
        && (                     //       if both neighbor cells are set, this is a
          r[x] = V[X] = R[       //       valid L-tromino:
            r[x] =               //         remove it by clearing the current cell
            V[X] = R[v] = 0,     //         and its 2 neighbors
            o = f(m),            //         save the result of a recursive call in o
            v                    //         and restore the tromino
          ] = 1                  //
        ) & o                    //         yield the result of the recursive call
      )                          //     end of loop over the directions
    )                            //   end of loop over the columns
  )                              // end of loop over the rows

```
> 8 votes

# Answer
# Python 3, ~~136~~ 131 bytes

```
lambda S:g(int((len(S)*'{:0<6}').format(*S),2))<1
g=lambda b:b*all(b>>i&t^t or g(t<<i^b)for i in range(30)for t in(67,131,193,194))

```

Try it online!

**Input:** A list of strings, each string must be a binary string. The length of the strings can be different.
**Output:** `True` if the shape can be tiled, `False` otherwise.

*-5 bytes thanks to @Lynn*!

## Big idea:

As with most code golf solutions, this is a brute-force recursive search. The program simply tries to remove an L-tromino from the shape, then recurs on the new shape.

By representing the shape using a bitboard (one integer, where each bit represents whether a cell is occupied or not), we can:

* Use bit-wise AND to check if an L-tromino fits within a shape
* Use bit-wise XOR to remove an L-shaped part from the shape.

## Program explanation

Constructing the bitboard:

```
int(
    (len(S)*'{:0<6}').format(*S)  # left pad each row with '0' to length 6
                                  # then concat all rows together
,2)               # interpret the result string as binary integer

```

Recursive function that returns 0 if the shape can be tiled, or a positive integer if the shape cannot be tiled.

```
g=lambda b:\  # receive a bitboard as argument
    b *              # tilable if b is 0
    all(             # tilable if any of the following is False, i.e. all(...)==0
        b>>i&t^t or      # tromino doesn't fit shape or
        g(t<<i^b)        # the remaining is not tilable, i.e. g(...)==0
        for i in range(30)        # for each position in shape
        for t in(67,131,193,194)  # for each tromino orientation
    )

```

## More details

**Bitboard layout**

The following diagram specifies which cell in the shape correspond to which bit in the bitboard:

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

```

The size of the bitboard is 5 x 6, which is enough to store 5 x 5 shapes. If the shape has less than 6 columns, it is padded with `0` to the left. For example:

```
 111         ...111
 1.1  ---->  ...1.1  ----> ...111 ...1.1 ...11.  ---->  0x7146
 11.         ...11.

shape        padded          bitboard (binary)          bitboard (hex)

```

(**Note:** `0` is denoted by `.` for visual clarity)

Since each shape has at most 5 columns as specified in the problem, there will always be an empty column to the left of the bitboard. This will be important to prevent wrap-around later.

Each tromino orientation can be represented by 1 bitboard:

```
          ......   ......   ......   ......
          ......   ......   ......   ......
tromino   ......   ......   ......   ......
          .....1   ....1.   ....11   ....11
          ....11   ....11   .....1   ....1.

bitboard     67      131      193      194
(decimal)

```

**Check if a tromino fits within the shape**

To check if an L-tromino `t` fits inside a certain position in shape `b`, we can use bit-wise AND:

```
......               ......                      ......
......   shift to    ....1.    AND tromino       ....1.
......   position    ...11.    with shape        ...11.
.....1   --------->  ......  -----+-------->     ......
....11               ......       |              ......
   t                 t << 13      |          (t << 13) & b
                                  |
                     ......       |
                     ...1..       |
                     ..111.  -----+
                     ...1..
                     ......
                        b

```

We can see that the tromino fits inside the shape if and only if `(t << i) & b == (t << i)` (where `i` is the desired position). This is equivalent to:

```
(b >> i) & t == t

```

**Remove an L-shaped region from the shape**

We can use bit-wise XOR to remove a tromino from the shape:

```
 ......         ..1111           ..1111
 ....1.         ..1111           ..11.1
 ...11.   XOR   ..1111   ---->   ..1..1
 ......         ..1111           ..1111
 ......         ..1111           ..1111
t << 13            b               b2

```
> 5 votes

# Answer
# APL (Dyalog Unicode), 81 bytesSBCS

```
L←⊂⍤2⊢4 2 2⍴∘.≠⍨⍳4
{∧/~,⍵:1⋄∨/∇¨⍵∘{r c l←-⍵⋄⍺>c⌽r⊖(⍴⍺)↑L⊃⍨-l}¨⍸{∧/∘,¨L≤⊂⍵}⌺2 2⊢⍵}

```

Try it online!

Monadic dfn that takes a binary matrix and gives 1 if it can be tiled with L-triominoes, 0 otherwise.

A brute-force recursive search by removing one triomino at a time. Uses the fact that every orientation of an L-triomino fits within a 2x2 box, so the code tests all 2x2 submatrices of the input array to search for possible L-triomino placements. The Stencil operator  fits perfectly for this purpose.

The algorithm becomes much faster if we limit the branches to the first 5 placements (which is guaranteed to include all possible placements that includes the top-left cell) at the cost of 8 bytes `(⊢↑⍨5⌊≢)`:

```
L←⊂⍤2⊢4 2 2⍴∘.≠⍨⍳4
{∧/~,⍵:1⋄∨/∇¨⍵∘{r c l←-⍵⋄⍺>c⌽r⊖(⍴⍺)↑L⊃⍨-l}¨(⊢↑⍨5⌊≢)⍸{∧/∘,¨L≤⊂⍵}⌺2 2⊢⍵}

```

Try it online!

### Ungolfed with comments

```
⍝ 4 rotations of L-triomino; looks like
⍝ ┌───┬───┬───┬───┐
⍝ │0 1│1 0│1 1│1 1│
⍝ │1 1│1 1│0 1│1 0│
⍝ └───┴───┴───┴───┘
L←,{0@(⊂⍵)⊢2 2⍴1}¨⍳2 2
                  ⍳2 2  ⍝ Indexes of 2-by-2 matrix
   {      ⊢2 2⍴1}¨      ⍝ For each, modify [1 1][1 1] so that
    0@(⊂⍵)              ⍝   that position becomes 0
  ,                     ⍝ Flatten top level

⍝ Main function; 1 if L-triomino tiling is possible, 0 otherwise
f←{
  ⍝ If no cells left, return True
  ∧/~,⍵: 1
    ~,⍵     ⍝ Boolean negation of flattened input matrix
  ∧/        ⍝ All; reduce by And
       : 1  ⍝ If true, return 1

  ⍝ Get possible placements as (row_idx, col_idx, L_idx) triples
  places←⍸{∧/∘,¨L≤⊂⍵}⌺2 2⊢⍵
          {         }⌺2 2⊢⍵  ⍝ Map over 2x2 submatrices...
           ∧/∘,¨L≤⊂⍵  ⍝ Can each of L be placed on a submatrix?
                L≤⊂⍵  ⍝   Compare each cell of each of L with each cell of the submatrix
                      ⍝   so that L(1) vs. ⍵(0) gives False and anything else gives True
           ∧/∘,¨      ⍝   Reduce by And on all cells of each comparison matrix
         ⍸            ⍝ Indexes of ones
  places←             ⍝ Assign to places

  ⍝ For each possible placement, remove the cells and
  ⍝ recursively try L-triomino placements
  ⍝ If no possible placement, ∨/ automatically gives False
  ∨/∇¨⍵∘{r c l←-⍵⋄⍺>c⌽r⊖(⍴⍺)↑L⊃⍨-l}¨places
      ⍵∘{                         }¨places  ⍝ Map each on the places...
         r c l←-⍵⋄                  ⍝ Dissect the placement; negate due to built-in rotation direction
                             L⊃⍨-l  ⍝ Fetch the target L-triomino
                        (⍴⍺)↑       ⍝ Overtake to fit the size of input matrix
                    c⌽r⊖            ⍝ Rotate to move the L-triomino to correct position
                  ⍺>                ⍝ Remove L-triomino cells from input matrix
    ∇¨  ⍝ Recursively test for L-triomino placements
  ∨/    ⍝ True if at least one is successful
}

```
> 3 votes

# Answer
# Ruby, ~~146 112~~ 108 bytes

```
->m{g=->q{[7,11,13,14].any?{|x|t=x/4|x%4>>~m[0].size;t*=2until t>=q||q&t==t&&g[q-t];t<=q}};g[(m*?0).to_i 2]}

```

Try it online!
> 1 votes

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


title: Embedding Sets of Sets

text:
# Question
Title: Embedding Sets of Sets
**Setup:** For two sets \\$A,B\\$, we say \\$A \subseteq B\\$ if every element in \\$A\\$ is also in \\$B\\$.

Another way of saying this, is that we can order the elements of \\$A,B\\$ into two lists \\$L\_A,L\_B\\$, such that \\$L\_A\[i\] = L\_B\[i\]\\$ where \\$i\\$ ranges over the indices of \\$L\_A\\$.

We proceed to extend this idea, to define the relation \\$\preceq\\$. For two sets of sets, \\$A,B\\$, we say that \\$A\preceq B\\$ if we can arrange their elements into lists \\$L\_A,L\_B\\$, such that \\$L\_A\[i\]\subseteq L\_B\[i\]\\$ for all indices of \\$L\_A\\$.

**Task:** Make a program/function which takes two sets of sets, `A,B`, determines if `A ⪯ B` as defined in the set up, and then appropriately returns Truthy or Falsy.

**Input:** You may give `A` and `B` to your input as sets. It is up to you how you wish have your function take `A` and `B`, be it separately, as a tuple, etc.

If you so choose, or if your language forces your hand, you can enter your input as lists, frozen sets or even submit elements one by one. Likewise, you may choose the datatype to represent the sets inside `A` and `B`.

For simplicity's sake, one may assume the elements of the sets in `A` and `B` are all integers.

**Output:** You can define whatever conditions you want to indicate your Truthy and Falsy inputs, as long as these conditions are independent of the output. (e.g. you can say "if my program never halts, this means Falsy")

**Examples**, with (1,0) indicating (Truthy, Falsy) respectively

```
A = {{4004,1}}, B = {{4},{4004,1}} => 1
# L_A = [{4004,1}], L_B = [{4004,1},{4}]

A = {{1,2},{5},{8}}, B = {{3,5},{6},{8},{7}} => 0
# {1,2} is not a subset of any set in B

A = {{4,44},{44,444},{4}}, B = {{4,44,444},{4,14},{4,40,44}} => 1
# L_A = [{4,44},{44,444},{4}], L_B = [{4,40,44},{4,44,444},{4,14}]

A = {{1,2,4},{6}}, B = {{1,2},{4},{6}} => 0
# {1,2,4} is not the subset of a single set in B, only the union of B

A = {{1},{1,2},{2}}, B = {{1,3},{2,3},{1,2}} => 1
# L_A = [{1},{1,2},{2}], L_B = [{1,3},{1,2},{2,3}]

A = {{-1},{8},{}}, B = {{-1,8,2},{8,-1,0}} => 0
# There are three elements in A, but only 2 in B, so the last item in L_A will not
# be paired with a superset, even for the empty set, {}. (vacuity be damned)

A = {{-1},{8},{}}, B = {{0,8},{9,-1},{100}} => 1
# L_A = [{-1},{8},{}], B =[{0,8},{9,-1},{100}]

A = {{1,2}{3,4}}, B = {{1,2,3,4},{}} => 0
# {1,2} and {3,4} are each subsets of {1,2,3,4}, and are not subsets of any other
# set in B, thus in the list, one of these will not be paired with their superset

```

# Answer
# Python 3, ~~84~~ ~~62~~ 58 bytes

Recursive function, `A` is a list of sets and `B` is a `frozenset`; returns false if \\$A\preceq B\\$ and true otherwise.

```
f=lambda A,B:A and all(A[0]-b or f(A[1:],B-{b})for b in B)

```

@PoonLevi and @SurculoseSputum helped save a great amount of bytes.

Explanation:

If `A` and `B` satisfy the relationship described, then this recursive statement makes sense:

```
The first set in A is contained in some i-th element of B and A', B' also satisfy the relationship, where
A' is A without the first set
B' is B without the said i-th element

```

Because I am returning the reverse, I am actually ensuring that, if the first element of `A` is contained in some element of `B`, then `A'` and `B'` cannot satisfy the relationship.

Try it online!
> 12 votes

# Answer
# Japt `-e`, ~~15~~ ~~13~~ 10 bytes

```
Vcà mÍdeUn

```

Try it
> 3 votes

# Answer
# , 32 bytes

```
#@[e.[:#@~.@>@,@{[:<@I.0=#@-.&>/

```

Try it online!

Left arg is A, right is B.

* `#@[` Is the len of A?...
* `e.` an element of?...
* `[:#@~.@>@,@{` any of the lengths, after deduping, of the cartesian product of...
* `[:<@I.` the indexes with value 1 in each row of the matrix defined by...
* `0=` elements that equal zero of...
* `#@-.&>/` the function table `/` (like a multiplication table) defined by "the length after set substraction", i.e., whose `(i,j)` element is the length of the j-th element of B set subtracted from the i-th element of A.
> 3 votes

# Answer
# Python 3, ~~110~~ 107 bytes

Simply try to match A with all permutations of B.

Take input as 2 lists of sets, and output False if \\$A \preceq B\\$, and True otherwise. (Note that the truthiness is reversed).

```
lambda A,B:len(A)>len(B)or all(any(a-b for a,b in zip(A,P))for P in permutations(B))
from itertools import*

```

Try it online!
> 2 votes

# Answer
# Jelly, 16 bytes

```
fƑ"Ạ¥ⱮŒ!}Ẹa,LÞƑ¥

```

Try it online!

A dyadic link taking `A` as its left argument and `B` as its right. Returns `1` for true and `0` for false.

Added 6 bytes to more correctly handle the situation when the length of A is more than the length of B. The previous test case worked only because the extra set was empty.

## Explanation

```
    ¥ⱮŒ!}        | Using each permutation of B in turn as the right argument:
fƑ"              | - Check whether A is invariant when filtered pairwise to that permutation of B
   Ạ             | - All true
         Ẹ       | Any true
          a    ¥ | And the following is true for the original arguments:
           ,     | - Pair
            LÞƑ  | - Invariant when sorted by length

```
> 2 votes

# Answer
# Julia 1.0, 61 bytes

```
f(a,b)=a==[]||any(a[1]⊆x&&f(a[2:end],setdiff(b,x)) for x=b)

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6),  ~~79~~  77 bytes

Takes input as `(B)(A)`, where \\$B\\$ is a list of sets and \\$A\\$ is a list of lists. Returns a falsy value (*false* or *undefined*) if \\$A\preceq B\\$, or *true* otherwise.

```
B=>g=([a,...A],u)=>a&&B.every((b,i)=>u>>i&1|a.some(v=>!b.has(v))|g(A,u|1<<i))

```

Try it online!
> 1 votes

# Answer
# Charcoal, 37 bytes

```
⊞υＡＦυ«≔⊟ιθ≔⊟ιι¬ιＦιＦθ¿¬⁻κλ⊞υ⟦⁻ι⟦κ⟧⁻θ⟦λ

```

Try it online! Link is to verbose version of code. Takes input as a list of list of lists and outputs nothing if `A` is not a subset of `B`, otherwise the number of ways it found to verify that `A` is a subset of `B` as a string of `-`s (would be +1 byte to output just a single `-`). Explanation:

```
⊞υＡＦυ«

```

Perform a breadth-first search starting with the original input.

```
≔⊟ιθ≔⊟ιι

```

Extract the latest pair of sets to check.

```
¬ι

```

If `A` is (now) empty then it is a subset of `B`.

```
ＦιＦθ¿¬⁻κλ

```

Find all pairs of sets in `A` and `B` such that one is a subset of the other.

```
⊞υ⟦⁻ι⟦κ⟧⁻θ⟦λ

```

For each such pair, add the sets with those elements removed to the search.
> 1 votes

# Answer
# Ruby, ~~60~~ 45 bytes

```
->a,b{a.all?{|x|b.any?{|y|f[a-[x&y],b-[y]]}}}

```

Try it online!

### How:

Recursively check: for every `x` in `a`

```
->a,b{a.all?{|x|                            }

```

there is at least a `y` in `b`

```
                b.any?{|y|                }

```

Such that removing `x⋂y` from `a` and `y` from `b`, the condition is still valid.

```
                          f[a-[x&y],b-[y]]

```

## Sorry, what?

A and B are sets of sets. If A is empty, the function returns true. If B is empty and A is not empty, then the function returns false. So far, so good.

Otherwise, let's check what happens if we remove the sets as specified:

* if x⊆y then x⋂y==x. We remove x from A and y from B, then check if the remaining sets satisfy the initial condition recursively, until A or B is empty.
* if x⊄y but x⋂y is contained in A, we remove it anyway. We will check the same x again on a different y in the next iteration. We need to remove an item from A and B, we are just removing them in a different order, and that won't affect the final result.
* if x⊄y and x⋂y is not contained in A, we can continue: x won't be removed in the next iterations, and the check will fail as soon as B is empty.
> 1 votes

# Answer
# 05AB1E, 11 bytes

Outputs 0 if A⪯B, a positive integer otherwise.

```
δKøœεÅ/˜g}ß

```

Try it online!
> 1 votes

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