# Question
Title: Random spanning tree of a rectangular grid
Significantly harder version of Spanning tree of a rectangular grid.

## Background

A spanning tree (Wikipedia) of an undirected graph is a subgraph that is a tree which includes all of the vertices of the original graph. The following is an example of a spanning tree of a 4-by-4 grid graph.

## Task

Given two positive integers `w` and `h`, output **a randomly generated spanning tree of the grid graph** which has `w` vertices horizontally and `h` vertices vertically. Your program/function should be able to generate **every possible spanning tree with nonzero probability**.

One possible algorithm to solve this task is random minimum spanning tree, which calculates the minimum spanning tree of the given graph with randomized edge weights.

## Input and output

The input is two positive integers `w` and `h`.

The output is a representation of a spanning tree. You can choose any representation that can describe such a graph without ambiguity, which includes (but is not limited to):

* ASCII-formatted grid
* A standard graph structure, e.g. adjacency matrix, adjacency list, incidence matrix...
* A list of pairs of numbered vertices

Please specify the output format in your submission.

## Scoring & winning criterion

The standard rules apply. The shortest valid submission in bytes wins.

## Example I/O

### `w=3, h=2`

* ASCII grid

```
+-+-+
| |
+ +-+

```
* Adjacency matrix

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

```
* List-of-vertex-pairs representation

```
[(0, 1), (0, 3), (1, 2), (1, 4), (4, 5)]

```

or

```
[((0, 0), (0, 1)),
 ((0, 0), (1, 0)),
 ((0, 1), (0, 2)),
 ((0, 1), (1, 1)),
 ((1, 1), (1, 2))]

```

### `w=1, h=1`

The graph is a single vertex with no edges, and its only spanning tree is the graph itself.

# Answer
# Python 2, 134 bytes

```
from random import*
w,h=input();w+=1
t={1}
while 1:z=choice([{a,b}for a in t for b in{a-1,a+1,a-w,a+w}-t if b%w>0<b<w*h]);print z;t|=z

```

Try it online!

A small improvement over xnor's answer by using row size `w+1` instead of `w` and not using the zeroth column. For example, the following coordinates are used for the input `3,2`:

```
1-2-3
| | |
5-6-7

```
> 8 votes

# Answer
# Wolfram Language (Mathematica), 146 bytes

```
Block[{c,g=GridGraph@{##}},Graph[Range[1##],Join@@Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g,c@#=#]}]&@1][[2]],Options@g]]&

```

Try it online!

Based on my answer to the question Maze Generation.

Returns a `Graph` object.

For example, `w = 20, h = 20` gives:
> 7 votes

# Answer
### Ruby, 159 bytes

```
->w,h{c=(v=[*1..w].product [*1..h]).product;((f,(a,b)),(g,(d,e))=c.shuffle.map{|z|[z,z.sample]};(c=c-[f,g]+[f+g];p(a,b,d,e))if(a-d).abs+(b-e).abs<2)while c[1]}

```

Try it online!

Uses simple Kruskal's algorithm with a few pessimizations (no union-find, inefficient - and non-uniform! - sampling of the purely virtual edge list, returns via stdout), at a byte cost relatively close to Value Ink's Prim implementation.

Prints each edge as a set of four lines; if you want something slightly more sensible, replace `p(a,b,d,e)` with `p [a,b,d,e]` at the cost of one byte.

Unsqueezed version:

```
->w, h{
 v=[*1..w].product [*1..h]
 c=v.product
 while c.size > 1
  (f, (a, b)), (g, (d, e)) = c.shuffle.map{|z| [z, z.sample]}
  if (a-d).abs + (b-e).abs < 2
   c = c - [f, g] + [f + g]
   p [a,b,d,e]
  end
 end
}

```
> 4 votes

# Answer
# Jelly, 28 bytes

```
,þ;Z$ṡ€2ẎẊḣ1;ẎḟL’ɗÐḟ@ḣ1ʋ¥ƬƊṪ

```

Try it online!

A dyadic link taking the width and height as its arguments and returning a list of pairs of vertices indicating the edges of the random minimum spanning tree. Based on Prim’s algorithm with the edge costs randomised.

## Explanation

```
,þ                           | Outer table using pair function
    $                        | Following as a monad:
  ;                          | - Concatenate to:
   Z                         | - Transposed table
     ṡ€2                     | Split each into overlapping lists of length 2
        Ẏ                    | Join outer lists
         Ẋ                   | Randomise order
                          Ɗ  | Following as a monad:
          ḣ1                 | - First list item (still in a list)
                        ¥Ƭ   | - Repeat following as a dyad, collecting up results, until no new result seen (will have the randomised list of vertex pairs as its right argument)
            ;          ʋ     | - Concatenate to the following as a dyad:
             Ẏ               |   - Join outer lists (making list of vertices seen so far)
                 ɗÐḟ@        |   - Keep only items from the randomised list of edges where the following is false:
              ḟ              |     - Filter out the vertices already used
               L             |     - Length
                ’            |     - Decrement by 1
                     ḣ1      |   - First list item (still in a list)
                           Ṫ | Final iteration of the above

```
> 3 votes

# Answer
# Ruby, ~~185~~ 164 bytes

A huge mess. Outputs a vertex-pair list, where vertex coordinates are complex numbers in the form `x+yi`.

Long story short, it takes all vertices that have already been chosen, randomly picks a neighbor that has not been picked before, and attaches it to the graph, then repeats the process until all vertices have been chosen.

* -4 bytes by optimizing `r>=0&&i>=0` to `r|i>=0` -- If either number is negative, the bit-or will ensure that the combined result is negative.
* -17 bytes by realizing my filter function in the second neighbor check could be switched to a simple set intersection...

```
->w,h,*e{*v=q=0i;d=1,-1,1i,-1i
(q=v.flat_map{|x|d.map{|c|x+c}.select{|e|r,i=e.rect;r|i>=0&&r<w&&i<h}-v}.sample
(v<<q;e<<[(d.map{|c|q+c}&v).sample,q])if q)while q;e}

```

Try it online!

### Explanation

```
->w,h,*e{                                       # Proc taking 2 arguments, e=[]
         *v=q=0i;                               # Add first vertex 0+0i to list
                 d=1,-1,1i,-1i                  # Save 4 cardinal directions
(                                     )while q  # While there is a valid neighbor:
 q=                                             # Set next vertex to:
   v.flat_map{|x|d.map{|c|x+c}                  # Get all neighbors to used vertices
      .select{|e|                               # Filter neighbors by:
                 r,i=e.rect                     # Get real/imaginary components
                 r|i>=0&&r<w&&i<h               # Vertex coordinates are in-bounds
             }
      -v                                        # Filter already-used vertices
    }.sample                                    # Pick a random valid neighbor
 (                                   )if q      # If a neighbor was found:
  v<<q                                          # Add it to the vertex list
  e<<[                                          # Add an edge to the edge list.
      (                                         # First vertex of edge is:
       d.map{|c|q+c}                            # Get vertex neighbors
       &v                                       # Intersect w/ used vertices
      ).sample                                  # Pick one by random
      ,q]                                       # Second vertex of edge is neighbor
                                                # (end while)
e                                               # Return the edge list

```
> 2 votes

# Answer
# K (ngn/k), 64 bytes

```
{e@&~~':i{@[x;&|/x=/:y;:;&/x y]}\e:0N?,/(2':'m),+'2':m:x#i:!*/x}

```

Try it online!

arg: `w,h` pair. result: list of vertex pairs.

`i:!*/x` create the list 0 .. (w\*h)-1 and assign to `i`

`m:x#` reshape to a w-by-h matrix `m`

`2':` pairs of neighbouring rows

`+'` transpose each (make them rows of pairs)

`(` `),` prepend

`2':'m` pairs of neighbouring cells in each row

`,/` concat into a single list

`e:0N?` shuffle and assign to `e` for "edges"

`i{` `}\` scan the edges with the function in `{` `}` and a starting value `i`. the left arg will map vertices to their "tree ids" in the forest. initially the vertex ids and tree ids coincide.

`@[x;&|/x=/:y;:;&/x y]` amend the current forest by merging the tree(s) corresponding to the ends of the new edge

`~':` which forests match the previous ones? boolean list

`e@&~` select from `e` where not
> 2 votes

# Answer
# Python 2, 136 bytes

```
from random import*
w,h=input()
t={0}
while 1:z=choice([{a,b}for a in t for b in{a-~a%w/~w,a+a%w/~w,a-w,a+w}-t if-1<b<w*h]);print z;t|=z

```

Try it online!

Prints edges as two-element set of vertices given by single-number index, terminating with error. The strategy is to to build up the set of vertices `t` in the tree until it contains the whole rectangle rectangle. At each step, we add an edge to the spanning tree consisting of a vertex in `t` and one of its neighbors that's not in `t`, and we add the new vertex to `t`. We search for neighbors by adding one of `{1,-1,w,-w}` to the 1D index with some trickery to avoid unwanted wraparounds, and checking that the result lies within the bounds of the rectangle.

---

# Python 2, 142 bytes

```
from random import*
w,h=input()
t={0}
while 1:z=choice([{a,b}for a in{k/w+k%w*1jfor k in range(w*h)}-t for b in t if(a-b)**4==1]);print z;t|=z

```

Try it online!

Prints edges as two-element sets of complex numbers, terminating with error.
> 2 votes

# Answer
# JavaScript (ES6),  ~~151 147 145~~  143 bytes

Takes input as `(width)(height)`. Returns a list of pairs of numbered vertices.

```
w=>g=h=>(m=1,n=a=[],F=v=>[++v%w&&v,--v%w&&v-1,v+w,v-w].map(V=>V<0|V/w/h|m>>V&1|Math.random()<.5||F(V,m|=1<<V,n=a.push([v,V]))))``|~n+w*h?g(h):a

```

Try it online!

### Commented

```
w =>                        // w = width
g = h => (                  // h = height
  m = 1,                    // m = bitmask of visited vertices
  n =                       // n = number of visited vertices - 1
  a = [],                   // a[] = pairs of connected vertices
  F = v =>                  // F is a recursive function, taking the current vertex v
    [ ++v % w && v,         //   try v + 1 if (v + 1) mod w is not equal to 0
                            //   we temporarily increment v to coerce it to a number
      --v % w && v - 1,     //   decrement v; try v - 1 if v mod w is not equal to 0
      v + w,                //   unconditionally try v + w
      v - w                 //   unconditionally try v - w
    ].map(V =>              //   for each new vertex V:
      V < 0 |               //     abort if V is negative
      V / w / h |           //     abort if V is greater than or equal to w * h
      m >> V & 1 |          //     abort if V was already visited
      Math.random() < .5 || //     abort with 50% probability
      F(                    //     otherwise, do a recursive call:
        V,                  //       using the new vertex
        m |= 1 << V,        //       update the bitmask of visited vertices
        n = a.push([v, V])  //       append [v, V] to a[] and update n
      )                     //     end of recursive call
    )                       //   end of map()
)`` |                       // initial call to F with v = [''] (zero'ish)
~n + w * h ?                // if n is not equal to w * h - 1:
  g(h)                      //   try again
:                           // else:
  a                         //   success: return a[]

```
> 1 votes

# Answer
# Charcoal, ~~77~~ 63 bytes

```
ＮθＮηＪ⊗‽θ⊗‽ηＰ+  ¦+Ｗ‹№ＫＡ+×θη«Ｊ⊗‽θ⊗‽η¿¬℅ＫＫ«≔⌕ＡＫＶ ι¿ι«Ｐ+  Ｐ✳⁻χ⊗‽ι²+

```

Try it online! Link is to verbose version of code. Outputs a whitespace-bordered ASCII grid. Explanation:

```
ＮθＮη

```

Input the width and height.

```
Ｊ⊗‽θ⊗‽ηＰ+  ¦+

```

Jump to a random position and mark it with a `+` surrounded with spaces. (Unfortunately Charcoal's Multiprint operator special-cases a leading `+` so I have to output the `+` separately.)

```
Ｗ‹№ＫＡ+×θη«

```

Repeat until `w*h` `+`s have been output.

```
Ｊ⊗‽θ⊗‽η

```

Jump to a random position.

```
¿¬℅ＫＫ«

```

If the position is vacant,

```
≔⌕ＡＫＶ ι

```

find any neighbouring spaces,

```
¿ι«

```

and if there is at least one, then

```
Ｐ+  Ｐ✳⁻χ⊗‽ι²+

```

surround the current position with spaces, draw a `-` or `|` in a random matching direction, and finally draw a `+` in the current position.
> 1 votes

# Answer
# , 156 bytes

```
function(w,h){b=rbind(x<-1:(s=w*h),c(x+1,1:(s-h)+h))[,1:w*-h][,sample(s+s-h-w)]
y=b[,1]
while(!all(z<-matrix(b%in%y,2)))y=rbind(y,b[,colSums(z)==1][1:2])
y}

```

Try it online!

A function taking the width and height and returning a two-matrix of 1-indexed pairs of points (numbered from top left, moving down and then right). The footer also prints an ASCII representation. Implements Prim’s algorithm.
> 1 votes

---
Tags: code-golf, grid, random, graph-theory
---


title: Counting valid Binary Sudoku boards

text:
# Question
Title: Counting valid Binary Sudoku boards
Sequel of Counting valid Binary Sudoku rows.

## Background

Binary Sudoku, also known as Takuzu, Binario, and Tic-Tac-Logic, is a puzzle where the objective is to fill a rectangular grid with two symbols (0s and 1s for this challenge) under the following constraints:

1. **Each row/column cannot have a substring of `000` or `111`, i.e. one symbol cannot appear three times in a row, horizontally or vertically.**

* A row/column of `1 0 0 0 1 1` violates this rule since it contains three copies of `0` in a row.
2. **Each row/column should contain exactly as many 0s as 1s, i.e. the counts of two symbols must be the same.**

* A row/column of `1 0 1 1 0 1` violates this rule since it has four 1s but only two 0s.
    * Some examples of rows that meet the first two requirements include:

    ```
    [1 0 0 1]
    [1 1 0 0]
    [1 1 0 1 0 0]
    [1 1 0 0 1 0 0 1]

    ```
3. **The entire grid cannot have two identical rows or columns.**

Note that the constraint 2 enforces the grid size to be even in both dimensions.

Here are some examples of completed Binary Sudoku:

```
(4x4)
1 1 0 0
0 1 1 0
1 0 0 1
0 0 1 1

(6x8)
1 1 0 1 0 1 0 0
0 0 1 0 1 0 1 1
0 1 0 1 0 0 1 1
1 1 0 0 1 1 0 0
0 0 1 0 1 1 0 1
1 0 1 1 0 0 1 0

```

## Challenge

Given two positive integer `m` and `n`, calculate the number of distinct valid Binary Sudoku boards of width `2m` and height `2n`. (You may take the values of `2m` and `2n` as input instead of `m` and `n`.)

A253316 is the sequence for square boards.

## Test cases

```
m,n => answer
-------------
1,1 => 2
1,2 => 0
2,2 => 72
2,3 => 96
2,4 => 0
3,3 => 4140
3,4 => 51744
3,5 => 392208
4,4 => 4111116

```

For the input `1,2`, it counts 2-by-4 boards, i.e. boards with four rows of length 2. But we can't have four distinct rows of length 2 to fill the grid (we have only 01 and 10). Therefore, by rule 3, the answer to the input `1,2` is zero. The same argument applies to the input `2,4` (4-by-8 boards).

Reference implementation in Python. This can handle up to `3,5` in a minute. Note that putting `r > c` takes much more time than the same pair swapped, though the results are the same.

## Scoring and winning criterion

Standard rules apply. The shortest submission in bytes wins.

# Answer
# Python 3.8 (pre-release), ~~265~~ ~~250~~ 198 bytes

```
lambda n,m:sum(not(n>len({*s})or m>len(set(z:=[*zip(*s)]))or any(p*3in"".join(v)or v.count("1")*2-len(v)for p in'01'for v in[*s]+z))for s in P(*[[*P(*['01']*m)]]*n))
from itertools import*;P=product

```

Try it online! Takes as input `2n` and `2m`. Thanks to Bubbler for finding a bug in my original answer and for golfing a *massive* 52 bytes off.

## How it works:

The anonymous function we define will be taking `2n` and `2m` as input, generate all binary boards with the specified dimensions and then count how many of those satisfy the restrictions.

### Generating all boards

```
... for s in P(*[[*P(*['01']*m)]]*n))
from itertools import*;P=product

```

is generating all the boards. The `product` function from the library `itertools` can be used to generate the cartesian product of all the arguments it is given. Breaking the nested `P`s down, `P(*['01']*m)` creates a list of length `m` with `'01'`: `['01', '01', ..., '01']` and then the splat operator `*` is used to turn each element of the list into an argument to `P`, so `P(*['01']*m)` generates all valid rows of length `m`. Call it `P1`.

Then we have `P(*[[*P1]]*n)` which takes all valid rows and turns it into a list of all valid rows, with `[*P1]`. We then enclose such a list in another list and multiply by `n`, so that we get a list of length `n` where each value is a list of all valid rows. Then the splat operator `*` is used to provide such a list as a series of arguments to the `itertools.product` function, thus getting all the correct-sized binary sudoku boards. We iterate over those with `s`.

### Checking restrictions on the board

Now we are left with checking the conditions imposed on the board `s` with

```
not(n>len({*s})or m>len(set(z:=[*zip(*s)]))or any(p*3in"".join(v)or v.count("1")*2-len(v)for p in'01'for v in[*s]+z))

```

Instead of verifying if the board satisfies everything, we check if the board doesn't violate any restriction:

* `n>len({*s})or m>len(set(z:=[*zip(*s)]))` checks if there are `n` unique rows, by converting the list of rows into a set; similarly we transpose `s` into `z` and check if there are `m` unique columns;
* then `any(B1 or B2 for v in[*s]+z)` goes over all rows and all columns:

+ `B2 = v.count("1")*2-len(v)` gives 0 when the amount of `1`s is exactly half of the size of the row/column and other non-zero integers when it is not. Regardless of giving a positive or negative result, Python will treat it as a Truthy value.
    + `B1 = p*3in"".join(v) for p in'01'` builds the substrings `"000"` and `"111"` and checks if those are in the row/column

### Wrapping it up

In the end, we just sum all the Truthy values that correspond to all the boards that did not violate any restrictions.
> 4 votes

# Answer
# Wolfram Language (Mathematica), 144 bytes

*Input (2n,2m)*

```
(l=Length)@Select[Tuples[{0,1},g=#],And@@Flatten[{#~Count~1==#~Count~0,Max[l/@Split@#]<3}&/@Flatten[c={#,Transpose@#},1],1]&&l/@(Union/@c)==g&]&

```

Try it online!
> 3 votes

# Answer
# Jelly, 26 bytes

```
IIP;S¬$PȧQƑ
×Ø-ṗ$s€ÇƇZ€$⁺L

```

A dyadic Link accepting `2n` on the left and `2m` on the right (or vice-versa as it's symmetric) which yields the count.

**Try it online!** This will time out even for `(6,4)` (i.e. `m=2` and `n=3`)\*

### How?

I imagine that if one worked out a combinatorial formula it would be much shorter (and quicker and more memory efficient!), but this entry is pure brute-force...

```
IIP;S¬$PȧQƑ - Link 1, (    no row has a run of 3 or more
                       AND no column contains differing type counts
                       AND all the rows are different
                      ): a single board, B
I           - incremental differences (vectorises) - e.g. [-1,1,1,1] -> [2,0,0]
 I          - incremental differences (vectorises)
  P         - product - this will give a list which will contain a zero for any row
                        containing a run of at least three equal items
     $      - last two links as a monad:
    S       -   sum (vectorises) - since we use -1 and 1: zero if the counts are equal
     ¬      -   logical NOT
   ;        - concatenate
       P    - product - this will be non-zero if (no row has a run of 3 or more
                                  AND no column contains differing type counts)
          Ƒ - is (B) invariant under:
         Q  -   de-duplication - i.e are all the rows different?
        ȧ   - logical AND

×Ø-ṗ$s€ÇƇZ€$⁺L - Link: 2n, 2m
×              - multiply -> 2n×2m (size of board)
    $          - last two links as a monad:
 Ø-            -   signs = [-1,1]
   ṗ           - Cartesian power (all lists of length 2n×2m of items -1 and 1)
      €        - for each:
     s         -   split into slices of length 2m (i.e. into rows)
           $   - last two links as a monad:
        Ƈ      -   filter keep those for which:
       Ç       -     call last Link (1) as a monad
          €    -   for each:
         Z     -     transpose
            ⁺  - repeat the last link - i.e. check the results with rows<->columns
             L - length

```

---

* I ran `m=2`, `n=3` locally and it yielded `96` as expected (after over an hour in which it hit 100% memory (16GB Ram) and slowed to a snail's pace while using disk).
> 2 votes

# Answer
# Charcoal, ~~102~~ ~~81~~ 64 bytes

```
Ｎθ≔×θＮη≔ＥＸ²η⪪⭆◧⍘ι²ηΣλθζＦ²≔ＥΦζ⬤κ›⁼№μ0№μ1⁺⊖№κμΣＥ²№μ×³ＩξＥθ⭆κ§ξμζＩＬζ

```

Try it online! Link is to verbose version of code. Takes the actual size as input. Explanation:

```
Ｎθ≔×θＮη

```

Input the width and area.

```
≔ＥＸ²η⪪⭆◧⍘ι²ηΣλθζ

```

Generate all possible grids of `0`s and `1`s of the given width and area.

```
Ｆ²

```

Loop over rows and columns.

```
Φζ⬤κ›⁼№μ0№μ1⁺⊖№κμΣＥ²№μ×³Ｉξ

```

Keep only those grids where each row has an equal number of `0`s and `1`s, is unique, and contains neither `000` nor `111`.

```
≔Ｅ...Ｅθ⭆κ§ξμζ

```

Transpose the rows and columns so that the columns can be checked on the next pass.

```
ＩＬζ

```

Output the number of remaining grids.

Previous much faster 102-byte version:

```
ＮθＮη≔ΦＥＸ²θ⭆◧⍘ι²θΣλ›⁼№ι0№ι1ΣＥ²№ι×³Ｉλζ⊞υ⟦⟧ＦυＦ‹ＬιηＦζＦ¬№ιλ⊞υ⁺ι⟦λ⟧ＩＬΦＥΦυ⁼ＬιηＥθ⭆ι§νλ⬤ι›⁼№λ0№λ1⁺⊖№ιλΣＥ²№λ×³Ｉν

```

Try it online! Link is to verbose version of code. Takes the actual size as input.
> 1 votes

---
Tags: code-golf, binary, sudoku
---


title: Solving the water bucket riddle!

text:
# Question
Title: Solving the water bucket riddle!
# Context

The water buckets riddle or the water jugs riddle is a simple riddle that can be enunciated in a rather general form as:

Given \\$n \> 0\\$ positive integers \\$a\_1, a\_2, \cdots, a\_n\\$ representing the capacities (in units of volume) of \\$n\\$ buckets and a positive integer \\$t \leq \max(a\_1, a\_2, \cdots, a\_n)\\$, find a sequence of *"moves"* that places \\$t\\$ units of volume of water in some bucket \\$i\\$.

To define the valid *"moves"*, let \\$c\_1, c\_2, \cdots, c\_n\\$ represent the units of volume of water each bucket \\$i\\$ contains, with \\$0 \leq c\_i \leq a\_i\ \forall i\\$. Then, at each step you can do any of the following:

* fill a bucket \\$i\\$ entirely, setting \\$c\_i = a\_i\\$
* empty a bucket \\$i\\$ entirely, setting \\$c\_i = 0\\$
* pour a bucket \\$i\\$ over a bucket \\$j\\$, setting

$$\begin{cases} c\_i = \max(0, c\_i - (a\_j - c\_j)) \\ c\_j = \min(a\_j, c\_j + c\_i) \end{cases}$$

i.e you pour bucket \\$i\\$ over bucket \\$j\\$ until bucket \\$i\\$ becomes empty or bucket \\$j\\$ becomes full, whatever happens first (or both if both things happen at the same time).

# Task

Given the bucket capacities and the target measurement, your task is to output a minimal sequence of movements that places \\$t\\$ units of volume of water in one of the buckets.

# Input

The capacities of the buckets are positive integers. You can assume these capacities are unique and ordered. You can take them in a number of reasonable formats, including but not limited to:

* a list of integers
* arguments to a function

Additionally, you will take a positive integer `t` that is not larger than the maximum number present in the input capacity list.

You can assume the input parameters specify a solvable instance of the water buckets problem.

# Output

Your program/function/etc should output the shortest sequence of moves that places `t` units of volume of water in one of the buckets. If several such sequences exist you can output any one sequence. Please note that some moves commute and that also introduces multiple solutions to some problems.

Your program can print the sequence or return it as a list of moves or any other sensible thing.

To identify the moves and the buckets, you can choose any encoding suitable for your needs, as long as it is consistent across test cases and completely unambiguous. A suggestion is, use three letters to identify the three moves, like `"E"` for emptying a bucket, `"F"` for filling and `"P"` for pouring and use numbers to identify the buckets (0-index or 1-indexed or using its total capacity, for example).

With this encoding, to identify a move you always need one letter and a number. In case of a *"pouring"* move, a second integer is also needed. It is up to you to consistently use `"P" n m` as `n` was poured over `m` or `m` was poured over `n`.

# Test cases

We use the encoding above and `"P" n m` means "pour bucket `n` over bucket `m`".

```
[1, 2, 3, 4], 1 -> ['F 1']
[1, 2, 3, 4], 2 -> ['F 2']
[1, 2, 3, 4], 3 -> ['F 3']
[1, 2, 3, 4], 4 -> ['F 4']
[13, 17], 1 -> ['F 13', 'P 13 17', 'F 13', 'P 13 17', 'E 17', 'P 13 17', 'F 13', 'P 13 17', 'E 17', 'P 13 17', 'F 13', 'P 13 17']
[4, 6], 2 -> ['F 6', 'P 6 4']
[1, 4, 6], 2 -> ['F 6', 'P 6 4']
[3, 4, 6], 2 -> ['F 6', 'P 6 4']
[4, 5, 6], 2 -> ['F 6', 'P 6 4']
[4, 6, 7], 2 -> ['F 6', 'P 6 4']
[1, 3, 5], 2 -> ['F 3', 'P 3 1']
[7, 9], 4 -> ['F 9', 'P 9 7', 'E 7', 'P 9 7', 'F 9', 'P 9 7']
[8, 9, 13], 6 -> ['F 9', 'P 9 8', 'P 8 13', 'P 9 8', 'F 13', 'P 13 8']
[8, 9, 13], 7 -> ['F 8', 'P 8 9', 'F 8', 'P 8 9']
[8, 9, 11], 10 -> ['F 8', 'P 8 9', 'F 11', 'P 11 9']
[8, 9, 12], 6 -> ['F 9', 'P 9 12', 'F 9', 'P 9 12']
[8, 9, 12], 5 -> ['F 8', 'P 8 12', 'F 9', 'P 9 12']
[23, 37, 41], 7 -> ['F 41', 'P 41 23', 'P 41 37', 'P 23 41', 'F 41', 'P 41 23', 'P 41 37', 'F 41', 'P 41 37', 'E 37', 'P 41 37', 'E 37', 'P 41 37', 'F 41', 'P 41 37']
[23, 31, 37, 41], 7 -> ['F 23', 'P 23 37', 'F 31', 'P 31 37', 'P 31 41', 'P 37 31', 'P 31 41']

```

You can check a vanilla Python reference implementation here

# Answer
# Python 3, ~~243~~ 239 bytes

*-4 bytes thanks to @JonathanFrech!*

```
def f(a,t,k=1):
 while g(a,t,[0]*len(a),[],k):k+=1
def g(a,t,c,p,k):n=len(a);k,i=k//n,k%n;k,j=k//n,k%n;exec(["c[i]=0","c[i]=a[i]","x=min(a[j]-c[j],c[i]);c[i]-=x;c[j]+=x"][k%3]);p+=k%3,i,j;return g(a,t,c,p,k//3)if k>2else{t}-{*c}or print(p)

```

Try it online!

**Input**: a list of bucket capacities `a`, and the target `t`.
**Output**: to stdout, a list of integers, where each triplet `m,i,j` denotes a move: `m` is the move type (`0,1,2` corresponds to `empty, fill, pour`), and `i`,`j` are the bucket indices (0-index). For move types `empty` and `fill`, the 2nd bucket is ignored.

**How**: Each sequence of moves `p` can be encoded by an integer `k` using modular arithmetic. `g` is a recursive function that checks if the sequence `p` encoded by `k` will result in the target `t`. If so, that sequence is printed to stdout, and a `Falsy` value is returned.

### Old solution using `itertools.product`

### Python 3.8 (pre-release), ~~279~~ 249 bytes

*Whopping -30 thanks to @ovs's double `product` trick!*

```
from itertools import*
P=product
a,t=eval(input())
for r in count():
 for p in P(*tee(P((0,1,2),R:=range(n:=len(a)),R),r)):
  c=[0]*n;[exec(["c[i]=0","c[i]=a[i]","x=min(a[j]-c[j],c[i]);c[i]-=x;c[j]+=x"][m])for m,i,j in p]
  if t in c:print(p);exit()

```

Try it online!

Slow, ugly and can probably be golfed more.

**Input**: from stdin, `a,t` where `a` is the list of bucket capacities, and `t` is the goal.
**Output**: to stdout, the optimal list of moves, each move has the form `(m, i, j)` where:

* `m` is the move type `0,1,2` (empty, fill, pour)
* `i` and `j` are the target buckets' indices (0-index).
* The moves `empty` and `fill` only affects the 1st bucket `i`, and thus the irrelevant 2nd bucket `j` is set to an arbitrary value.
* The move `(2,i,j)` pours the water from bucket `i` to bucket `j`.

**How**: This program simply tries all possible sequence of move, in order of length.

To generate all sequence of `r` moves:

* `product((0,1,2), range(n), range(n))` generates a list of all possible moves by performing the Cartesian product between all move types `0,1,2`, all values of `i` and all values of `j`.
* `tee(product(...), r)` clones the move list into `r` lists.
* `product(*tee(...)) takes the Cartesian product of`r`move lists, which results in all possible sequence of`r\` moves.

To perform a sequence of move `p`:

* `c[i]=0`,`c[i]=a[i]`, and `x=min(a[j]-c[j],c[i]);c[i]-=x;c[j]+=x` respectively handles emptying, filling, and pouring between bucket `i` and `j`. Note that pouring can handle `i==j`, which results in a no-op.
* `exec(["handle E", "handle F", "handle P"][m])` selects the correct handler for move type `m`.
> 6 votes

# Answer
# JavaScript (ES6),  ~~197 191~~  188 bytes

Takes input as `(a)(t)`.

Returns a string of concatenated operations `Fx`, `Ex` or `Px>y`, with 0-indexed buckets.

```
a=>F=(t,N)=>(g=(b,n,o)=>[...b,0].some((V,i,x)=>(x=a[i])-V^t?n&&b.some((v,j,[...B])=>(s='F',B[j]=i-j?x?(v+=V)-(B[s=`P${i}>`,i]=x<v?x:v):a[s='E',j]:0,g(B,n-1,[o]+s+j))):O=o))(a,N)?O:F(t,-~N)

```

Try it online!

The above test link inserts spaces between operations for readability. Some longer test cases have been removed.
> 3 votes

# Answer
# Javascript, 364 bytes

I'm sure this can be golfed much better pretty easily.

```
S=t=>G=>{L=t.length;r=(f,n,a,i,e=0)=>{if(0==n)return f.indexOf(G)>=0&&[];a=(A,B,C,D)=>(X=f.slice(),X[A]=B,X[C]=D,X);for(;e<L;++e){for(K of[0,t[e]])if(F=r(a(e,K),n-1))return[[+!K,e]].concat(F);for(i=0;i<L;++i)if(i!=e&&(O=r(a(e,Math.max(0,f[e]-t[i]+f[i]),i,Math.min(t[i],f[e]+f[i])),n-1)))return[[2,e,i]].concat(O)}};for(T=1;!(E=r(Array(L).fill(0),T));++T);return E}

```

Returns an array of arrays. Each array is in the format `[n, i]` if `n=0` (fill) or `n=1` (empty), or `[2, i, j]` for "pour bucket `i` into bucket `j`". The buckets are always given as indices, starting from 0.

Uses the same basic search method as the other answers. Unminified version:

```
var S = (capacities, target) => {
    let n = capacities.length;
    var waterBuckets = (levels, maxSteps) => {
      if (maxSteps == 0) return levels.indexOf(target) >= 0 ? [] : false;
      let getCopy = () => levels.slice();
      for (let i = 0; i < n; ++i) {
        for (let level of [0, capacities[i]]) {
          let levelsCopy = getCopy();
          levelsCopy[i] = level;
          let res = waterBuckets(levelsCopy, maxSteps - 1);
          if (res) return [[+!level, i]].concat(res);
        }
        for (let j = 0; j < n; ++j) {
          if (i === j) continue;
          let levelsCopy = getCopy();
          levelsCopy[i] = Math.max(0, levels[i] - capacities[j] + levels[j]);
          levelsCopy[j] = Math.min(capacities[j], levels[i] + levels[j]);
          let res = waterBuckets(levelsCopy, maxSteps - 1);
          if (res) return [[2, i, j]].concat(res);
        }
      }
    };
    for (let s = 1;; ++s) {
      let r = waterBuckets(Array(n).fill(0), s);
      if (r) return r;
    }
};

```
> 0 votes

# Answer
# Charcoal, ~~112~~ 104 bytes

```
⊞υＥθ⁰Ｆυ¿¬ⅈ¿№…ιＬθη⪫✂ιＬθＬι¹ «ＦＬθＦ²⊞υ⁺Ｅι⎇⁼κν∧λ§θκμ⟦§EFλκ⟧ＦＬθＦＬθ¿⁻λκ«≔⌊⟦§ιλ⁻§θκ§ικ⟧ε⊞υ⁺Ｅι⎇⁼κν⁺με⎇⁼λν⁻μεμ⟦Pλκ

```

Try it online! Link is to verbose version of code. Could save 6 bytes by including the final bucket state in the output. The code spends most of its time emptying or pouring empty buckets, so don't try it on the harder problems. Explanation:

```
⊞υＥθ⁰

```

Start off with all buckets empty and no operations so far. (Each entry comprises `n` buckets plus an unspecified number of operations.)

```
Ｆυ¿¬ⅈ

```

Perform a breadth-first search until a solution has been printed. (This relies on `t` being positive, as that means that at least one step is necessary.)

```
¿№…ιＬθη⪫✂ιＬθＬι¹ «

```

If one of the first `n` buckets contains `t` then this is a solution in which case output it, otherwise:

```
ＦＬθＦ²

```

Loop over each bucket and whether it's being emptied or filled.

```
⊞υ⁺Ｅι⎇⁼κν∧λ§θκμ⟦§EFλκ⟧

```

Calculate the new bucket values and append the result with the additional operation.

```
ＦＬθＦＬθ¿⁻λκ«

```

Loop over each pair of distinct buckets.

```
≔⌊⟦§ιλ⁻§θκ§ικ⟧ε

```

Calculate the amount that can be poured from one bucket to the other.

```
⊞υ⁺Ｅι⎇⁼κν⁺με⎇⁼λν⁻μεμ⟦Pλκ

```

Calculate the new bucket values and append the result with the additional operation. Adding an extra `¿ε` to the beginning of this block does make the code a bit faster but it wasn't significant enough to be able to solve the harder problems on TIO.
> 0 votes

---
Tags: code-golf, integer, combinatorics, search
---


title: Simulate D Flip-Flop

text:
# Question
Title: Simulate D Flip-Flop
# Objective

Simulate an edge-triggered D Flip-Flop.

# What is D Flip-Flop?

A D flip-flop is an electronic digital device that outputs an inputted **data** (abbr. D) with synchronization to a **clock** (abbr. CLK). Usually CLK is a uniform pulse, but in this challenge, CLK may be not uniform.

# Input

A bitstring with length \\$n\\$ will be given as CLK and another bitstring with length \\$n-1\\$ will be given as D. A bit represents the state of an input during a unit time (tick). CLK leads D by half a tick.

# Output

The output (abbr. Q) is a bitstring with same length and starting timepoint as D. If CLK doesn't start with `01`, the starting bit of Q is implementation-defined. Q is updated upon a rising moment of CLK to the bit of D at the time. On the other times, Q retains its state.

# Examples

The red line indicates a rising moment of CLK.

* Example 1:

* Example 2:

# Rules

* If CLK isn't a tick longer than D, the entire challenge falls into *don't care* situation.
* Though defined as bitstrings, the actual elements of CLK, D, and Q doesn't matter. In this case, if a string is not binary (that is, contains a third character), the entire challenge falls into *don't care* situation.

# Answer
> 2 votes
# 05AB1E, ~~15~~ ~~14~~ 13 bytes

```
εINTS+èÆi©ë®Θ

```

First input is \\$D\\$, second input is \\$CLK\\$.
Output \\$Q\\$ as a list of 0s and 1s.

Try it online or verify both test cases (and pretty-print).

**Explanation:**

```
ε            # Map over the (implicit) input-list D:
  N          #  Push the current map-index
   TS        #  Push 10 as digit-list: [1,0]
     +       #  Add them to the index: [index+1, index]
 I    è      #  Index both of them into the second input CLK
       Æi    #  If they are [1,0]:
         ©   #   Store the current map-value in variable `®` (without popping)
        ë    #  Else:
         ®   #   Push variable `®`
          Θ  #   And check whether it is exactly 1 (1 if truthy, 0 if falsey)
             #   (which is necessary, because `®` is -1 by default)
             # (after which the list is output implicitly as result)

```

# Answer
> 5 votes
# , ~~27~~ 23 bytes

-4 bytes thanks to Bubbler!

```
;@(<@({.\);.1~1,2</\}.)

```

Try it online!

`CLK` is the left argument; `D` is the right one. When `CLK` doesn't start with `01`, the starting bits are the same as the first bit of `D`.

```
                       ;.1  - cut
                          ] - the right argument (D)
   (          )             - where
         2 /\               - the previous element
             [              - of the left argument (CLK)
          <                 - is smaller than the next one
       }.                   - drop
      1                     - the first item
    1,                      - prepend with 1 (for cutting)
               (     )      - for each cut group
                   $        - make a list
                #           - of the same length as the group
                    {.      - with elements same as the first one
                 <@         - and box the list
  ;                         - unbox the sublists and flatten them
[:                          - function composition

```

# K (oK), ~~27~~  23bytes

-4 bytes thanks to ngn!

```
{,/&\'|\'(0,&1_>':x)_y}

```

Try it online!

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

```
∊⊣⊣\¨⍤⊂⍨1,1↓2</⊢

```

Try it online!

A dyadic tacit function whose right arg is CLK and left arg is D. Accepts both as Boolean vectors. The starting bit of Q follows that of D.

### How it works

```
∊⊣⊣\¨⍤⊂⍨1,1↓2</⊢  ⍝ Input: left←D, right←CLK
            2</⊢  ⍝ Detect rising edges of CLK
        1,1↓      ⍝ Treat the very first tick as a rising edge
 ⊣    ⊂⍨          ⍝ Partition D into regions where
                  ⍝   each rising edge marks the start of each region
  ⊣\¨⍤            ⍝ On each region, overwrite all elements with the first one
∊                 ⍝ Enlist; form a simple vector

```

# Answer
> 3 votes
# JavaScript (ES6),  ~~40~~  39 bytes

Takes input as `(clock)(data)`, where *clock* and *data* are arrays of binary digits.

```
C=>D=>D.map(c=>C[i]<C[++i]?p=c:p,i=p=0)

```

Try it online!

# Answer
> 3 votes
# Io, 56 bytes

The space before `:=` is mandatory, otherwise the colon would be part of the undefined identifier.

Argh. Just 1 byte away from Java!

```
method(c,d,q :=0;d map(i,x,q=if(c at(i)<c at(i+1),x,q)))

```

Try it online!

# Explanation

```
method(c, d,                // Take 2 operands, c and d
    q := 0                  // Set the flip flop to 0
    d map (i, x,            // Map every item in d
                            // With the index i and the
                            // current item x
        q = \               // Set the current flip-flop as:
            if(c at(i)      // If the clock at the same index
            < c at(i + 1),  // Is less than the clock at the next index?
                            // I.e. the clock goes from 0 to 1
                x,          // Set the flip-flop as the current item x
                q           // Otherwise, make an identity function.
            )               // The assigned operand result is automatically
    )                       // returned to the map loop, so no
)                           // explicit reference of the flip-flop in the map.

```

# Answer
> 2 votes
# Python 3.8, 57 bytes

```
lambda C,D,x=0:[x:=[x,d][a<b]for d,a,b in zip(D,C,C[1:])]

```

Try it online!

**Input**: 2 lists of 0s and 1s, the first list `C` represents the clock line, and the second list `D` represents the data line.
**Output**: The list `Q` representing the state of the flip-flop through time.

### Explanation

* `for d,a,b in zip(D,C,C[1:])` iterates over the lines, where `d` is the current data bit, `a` is the previous clock bit, and `b` is the current clock bit
* `x` stores the previous state of the flip-flop
* `x:=[x,d][a<b]` updates the state of the flip-flop: if `a<b` is `1` (edge-rise moment), then the state is updated to the current data bit `d`. Otherwise, the state remains the same as previous state.

# Answer
> 1 votes
# Java 8, 55 bytes

```
C->D->{int i=0,p=0;for(int c:D)D[i]=C[i]<C[++i]?p=c:p;}

```

Port of *@Arnauld*'s JavaScript answer, so make sure to upvote him!!

Input as two integer-arrays. Stores the result (\\$Q\\$) in input \\$D\\$ instead of returning a new list to save bytes.

Try it online.

**Explanation:**

```
C->D->{                  // Method with two integer-arrays as parameter and no return-type
  int i=0,               //  Index-integer, starting at 0
      p=0;               //  Previous integer, starting at 0
  for(int c:D)           //  Loop over the digits of input D:
    D[i]=                //   Set the `i`'th value of array D to:
         C[i]            //    If the `i`'th value of array C
             <C[++i]?    //    is smaller than the `i+1`'th value of array C
                         //    (thus C[i] == 0 and C[i+1] == 1)
                     p=c //     Use the current digit `c`,
                         //     and also replace `p` with this digit
                    :    //    Else (they're [0,0], [1,0] or [1,1]):
                     p;} //     Use digit `p` instead

```

# Answer
> 1 votes
# C (gcc), <sup>~~80~~</sup> 67 bytes

```
t;f(c,d,n)int*c,*d;{for(t=*c++;n--;d++)*c++=t^*c&&(t^=1)?*d:c[-1];}

```

Try it online!

Inputs the clock and data as `int` arrays along with the length of the data array.
Returns the output in the clock array starting at one past the beginning.

# Answer
> 1 votes
# Charcoal, 22 bytes

```
≔0ζＦＬη«Ｆ‹§θι§θ⊕ι≔§ηιζζ

```

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

```
≔0ζ

```

Initialise `Q`.

```
ＦＬη«

```

Loop over the elements of `D`.

```
Ｆ‹§θι§θ⊕ι

```

Did `CLK` transition from `0` to `1`?

```
≔§ηιζ

```

If so then set `Q` to `D`.

```
ζ

```

Output `Q`.

---
Tags: code-golf, string, bitwise, electrical-engineering
---


# Question
Title: Find how many ordered pairs of integers share only one digit
# Task

Your task is to make the smallest function/program that can, when gives an number N, return/print:

the number of possible choices `a, b` such that \\$1 \leq a \< b \< N\\$ and `a` and `b` have exactly one common digit in base 10 (there exists a digit, and only one digit, which appears both in `a` and `b`, for example 12 and 23, where 2 appears both in 23 and in 12)

note - 1 and 11 count as having exactly one common digit, as 1 is a digit which appears in both of them, and it's the only one that appears in both of them.

You function/program should work for all n from 1 to 1000.

# Test Cases

```
20 -> 63
40 -> 267
60 -> 575
80 -> 987
100 -> 1503
1000 -> 235431

```

# Rules

This is a code golf so the lowest score in bytes wins. Good luck!

# Answer
> 3 votes
# APL (Dyalog Extended or 18.0), ~~24~~ 22 bytesSBCS

Full program.

```
≢⍸∘.(<∧1=∘≢∘∪∩⍥⍕)⍨1↓⍳⎕

```

Try it online!

prompt for N from the console

first N integers

`1↓` drop the first one (0)

apply the following function using those integers as both left and right argument:

`∘.(``)` apply the following function between all combinations of left and right elements:

`⍥⍕` stringify (make into character list) both arguments, then:

find the intersection between the character lists

find the Unique elements of that

then:

count that

then:

`1=` check if that is equal to 1

and

`<` the left argument is less than the right argument

find the **ɩ**ndices of the trues

count them

# Answer
> 3 votes
# 05AB1E, ~~15~~ ~~14~~ 12 bytes

```
L¨2.Æʒ`ÃÙg}g

```

-2 bytes thanks to *@Shaggy*.

Try it online or verify all test cases.

**Explanation:**

```
L           # Push a list in the range [1, (implicit) input]
 ¨          # Remove the last value to make the range [1, input)
  2.Æ       # Get all non-duplicated combinations of size 2 of this list
     ʒ      # Filter this list of pairs by:
      `     #  Push them separated to the stack
       Ã    #  Only keep the digits of the first number which are also in the second
        Ù   #  Uniquify those remaining digits
         g  #  Get the length of the remaining digits (only 1 is truthy in 05AB1E)
     }g     # After the filter: get the amount of remaining items by taking the length
            # (which is output implicitly as result)

```

# Answer
> 3 votes
# , 39 bytes

```
1#.[:,1=[:(</*([#@~.@-.-.)&":"0/)~1}.i.

```

Try it online!

Interestingly, almost exactly the same as Adam's APL answer, though I arrived at it independently. A bit more verbose in J, though... ಥ\_ಥ

# Answer
> 2 votes
# Jelly, 12 bytes

```
ṖDŒcf/QLƊ€ċ1

```

A monadic Link accepting a non-negative integer which yields a non-negative integer.

**Try it online!**

### How?

```
ṖDŒcf/QLƊ€ċ1 - Link: integer, N   e.g. 1000
Ṗ            - pop (implicit range)    [1,2,3,...,999]
 D           - to decimal (vectorises) [[1],[2],[3],...,[9,9,9]]
  Œc         - unordered pairs         [[[1],[2]],[[1],[3]],...,[[1],[1,9]],[[2],[3]],...,[[9,9,8],[9,9,9]]]
         €   - for each:                   e.g. [[2,5,2],[2,7,0]]
        Ɗ    -   last three links as a monad:
     /       -     reduce by:
    f        -       filter keep                [2,2]
      Q      -     de-duplicate                 [2]
       L     -     length                       1
           1 - literal one
          ċ  - count occurrences       235431

```

# Answer
> 1 votes
# Python 2, 77 bytes

```
lambda n:sum(len(set(`a`)&set(`b`))==1for a in range(1,n)for b in range(1,a))

```

Try it online! Thanks to @SurculoseSputum for translating my Python 3 program into Python 2, helping me golf the v3 and creating a shorter one in Python 2.

## Python 3.8 (pre-release), ~~99~~ 79 bytes

```
lambda n:sum(len({*str(a)}&{*str(b)})==1for a in range(1,n)for b in range(1,a))

```

Try it online!

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

```
f=(a,b=--a)=>a?--b?!~-new Set((a+[,b]).match(/(.)(?=.*,.*\1)/g)).size+f(a,b):f(a):0

```

Try it online!

### How?

To test how many distinct digits the integers \\$a\\$ and \\$b\\$ have in common, we concatenate them with a comma in between and apply the following regular expression:

```
/(.)(?=.*,.*\1)/g

 (.)              // a digit in the first integer
    (?=           // followed by:
       .*         //   some optional digits
         ,        //   a comma (the separator between the 2 integers)
          .*      //   some optional digits
            \1    //   the same digit in the 2nd integer
              )   // end of lookahead

```

We then turn all matches into a set and test whether its size is exactly \\$1\\$. For golfing reasons, we actually decrement the size and test whether the result is \\$0\\$:

```
!~-new Set(...).size

```

When nothing is matched, `match()` returns *null* rather than an empty array, which is usually painful to deal with if we want to apply some array method or property to the result. But we don't have to worry about that here because `new Set(null)` simply generates an empty set, which is what we want.

---

# Non-recursive, 93 bytes

```
n=>{for(t=0;--n;)for(b=n;--b;)t+=new Set((n+[,b]).match(/(.)(?=.*,.*\1)/g)).size==1;return t}

```

Try it online!

# Answer
> 1 votes
# Japt `-x`, ~~16~~ 15 bytes

```
oì à2 Ërf â Ê¶1

```

Try it

# Answer
> 0 votes
# Wolfram Language (Mathematica), 83 bytes

```
(t=0;Do[If[Tr[1^Intersection@@IntegerDigits@{i,j}]==1,t++],{i,#-1},{j,i+1,#-1}];t)&

```

Try it online!

# Answer
> 0 votes
# Java 8, ~~166~~ 156 bytes

```
n->{int r=0,a=n,b,i;for(;a-->2;)for(b=a;b-->1;){var s="";for(var t:(a+s).split(s))if((b+"").contains(t)&!s.contains(t))s+=t;r+=s.length()==1?1:0;}return r;}

```

Try it online.

**Explanation:**

```
n->{                    // Method with integer as both parameter and return-type
  int r=0,              //  Result-counter, starting at 0
      a=n,b,i;          //  Integers a,b,i
  for(;a-->2;)          //  Loop `a` in the range (n, 2]:
    for(b=a;b-->1;){    //   Inner loop `b` in the range (a, 1]:
      var s="";         //    Create an empty String
      for(var t:(a+s).split(s))
                        //    Loop over the digits of `a`:
        if((b+"").contains(t)
                        //     If `b` contains this digit
           &!s.contains(t))
                        //     and the String doesn't contain this digit yet:
          s+=t;         //      Append this digit to the String
      r+=               //    Increase the counter by:
         s.length()==1? //     If the length of the String is 1:
          1             //      Increment the counter by 1
         :              //     Else:
          0;}           //      Leave the counter the same by increasing with 0
  return r;}            //  After the loops, return the counter-integer as result

```

# Answer
> 0 votes
# Charcoal, 25 bytes

```
ＩΣＥＮＬΦι∧λ⁼¹ＬΦχ∧№ＩιＩν№ＩλＩν

```

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

```
   Ｎ                       Input `n` as a number
  Ｅ                        Loop `0<=b<n`
      ι                    `b`
     Φ                     Loop `0<=a<n`
        λ                  `a`
       ∧                   Is non-zero and
           ＬΦχ             Count of digits where
               №ＩιＩν       Digit present in `b`
              ∧            And
                    №ＩλＩν  Digit present in `a`
         ⁼¹                Equals `1`
    Ｌ                      Number of matching values
 Σ                         Sum of numbers
Ｉ                          Cast to string for implicit print

```

---
Tags: code-golf, math
---


# Question
Title: Reconstruct a 3d arrangement of cubes from two of its projections
# Setup

Take the following `4x4x4` cube along with a 2D view of 3 of its faces, with a common `1x1x1` cube highlighted:

The arrows represent the points of view that generated the `V1`, `V2` and `V3` faces drawn underneath the big cube.

Given an arrangement of some `1x1x1` cubes inside the main cube we can try and identify it with only three projections. For example, the arrangement below:

could be represented as follows:

```
V1
X...
....
....
XXXX

V2
X...
X...
X...
X..X

V3
X...
X...
X...
XXXX

```

However, if we consider only projections on `V1` and `V2`, most of the time we can't identify uniquely the arrangement being considered.<sub>(there are arrangements that can't be uniquely identified, even with the 6 projections)</sub>

# Task

Given projections on `V1` and `V2`, output the minimum and maximum number of `1x1x1` cubes that an arrangement could have and still produce the projections `V1` and `V2`.

I'll walk you through 2 examples:

## Explained example 1

```
V1
XXXX
....
....
....

V2
X...
X...
X...
X...

```

These two projections signal some directions along which there must be cubes:

and the output would be `4, 16`; This is the case because both `V3` below represent valid projections on `V3`:

```
V3a
X...
.X..
..X.
...X

```

This is a "diagonal" pattern of cubes in the back plane, when viewed from `V3`; ...

```
V3b
XXXX
XXXX
XXXX
XXXX

```

and this is a full face in the back plane.

## Explained example 2

```
V1
XXXX
XXXX
XXXX
XXXX

V2
XXXX
....
....
....

```

These projections represent the top face of the main cube, so in this case we managed to identify the arrangement uniquely. The output in this case would be `16, 16` (or `16`, see output rules below).

# Input

Your code takes the projections on `V1` and `V2` as input. There are a variety of reasonable ways for you to take this input. I suggest the following to represent each projection:

* An array of length 4 with strings of length 4, two different characters to encode "empty" or "filled", like `["X...", ".X..", "..X.", "...X"]` for the `V3a` above.
* An array/string of length 16, representing the 16 squares of the projection, like `"X....X....X....X"` for `V3a` above.
* An integer where its base 2 expansion encodes the string above; 1 *must* represent the `X` above, so `V3a` above would be `33825 = b1000010000100001`.

For any of the alternatives above, or for any other valid alternative we later decide that is helpful for you guys, you can take any face in any orientation you see fit, as long as it is consistent across test cases.

# Output

The two non-negative integers representing the minimum and maximum possible number of `1x1x1` cubes in an arrangement that projects onto `V1` and `V2` like the input specifies. If the minimum and maximum are the same, you can print only one of them, if that helps you in any way.

# Test cases

(I didn't really know how to format these... if needed, I can reformat them! Please let me know.)

```
XXXX
....
....
....,
X...
X...
X...
X... -> 4, 16

XXXX
XXXX
XXXX
XXXX,
XXXX
....
....
.... -> 16, 16

XXXX
XXXX
XXXX
XXXX,
XXXX
....
..X.
.... -> 16, 20

X..X
.XX.
.XX.
X..X,
X.XX
.X..
..X.
XX.X -> 8, 16

XXXX
XXXX
XXXX
XXXX,
XXXX
XXXX
XXXX
XXXX -> 16, 64

X...
....
....
XXXX,
X...
X...
X...
X..X -> 8, 8

X..X
....
....
XXXX,
X...
X...
X...
X..X -> 8, 12

```

---

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it! If you dislike this challenge, please give me your feedback. Happy golfing!

# Answer
> 10 votes
# APL (Dyalog Unicode), 11 bytes

```
+.(⌈,×)/+⌿¨

```

Try it online!

Takes V1 and V2 as two binary matrices inside a nested vector, and V1 is rotated so that it vertically lines up with V2. Returns doubly nested vector of `(min, max)`.

### How it works

The first column of V1 and the first column of V2 decide the first vertical layer of 4x4 cells. If `n` cells are shaded in V1's column and `m` cells in V2's, the minimum number of shaded cells in the corresponding 4x4 layer is `max(m,n)`, and the maximum is `m * n`.

```
min          |  max
  | 1 0 1 0  |    | 1 0 1 0
-----------  |  -----------
1 | 1 0 0 0  |  1 | 1 0 1 0
1 | 1 0 0 0  |  1 | 1 0 1 0
0 | 0 0 0 0  |  0 | 0 0 0 0
1 | 0 0 1 0  |  1 | 1 0 1 0

```

Therefore, it suffices to count ones in each column, and evaluate sums of the pairwise max (for minimum) and pairwise product (for maximum) of the column sums.

```
+.(⌈,×)/+⌿¨
        +⌿¨  ⍝ In each matrix, evaluate column sums
       /     ⍝ Over the two vectors,
+. ⌈         ⍝ Evaluate the sum of pairwise max
    ,        ⍝ and
+.   ×       ⍝ the sum of pairwise product

```

# Answer
> 10 votes
# Python 3, ~~74~~ 71 bytes

*-3 bytes thanks to @Bubbler!*

```
lambda V:(sum(f(*map(sum,p))for p in zip(*V))for f in[max,int.__mul__])

```

Try it online!

**Input**: a list of faces `[V1,V2]`, each face is a 4x4 list of binary digit. The orientation of each face is as follow (`V2` is rotated 90 degree clock-wise compare to the challenge's default orientation).  **Output**: A tuple of 2 integers, representing the min and max number of blocks.

### Approach

Consider each of the 4 slices of the cube:  We can see that for each slice, the min and max number of block in that slice is respectively the max and the product of the top and left strips.

### Code explanation:

`lambda V:(sum(f(*map(sum,p))for p in zip(*V))for f in[max,int.__mul__])`

* `for f in[max,int.__mul__]` assigns `f` first to the function `max`, then to the integer multiply function.
* `p in zip(*V)` pairs each corresponding strips (aka rows) of the 2 faces together.
* `map(sum,p)` applies the `sum` function to each row in the pair. The result is effectively `(top, left)`.
* `f(*map(...))` computes either `max(top,left)` or `top*left`.
* `sum(f(...))` sums over all slices.

# Answer
> 4 votes
# Jelly, 7 bytes

```
§µ»/,P§

```

A monadic Link accepting a list of the two projections each being a list of lists of 1s and 0s, `[V1, V2]`, with V2 rotated a quarter turn clockwise which yields a list of two integers, `[min, max]`

**Try it online!**

### How?

The same method as Bubbler & Surculose Sputum came up with.

```
§µ»/,P§ - Link: list of two lists of lists of 1s and 0s
§       - sums
 µ      - start a new monadic chain, call that v
   /    - reduce (v) by:
  »     -   maximum (vectorises)
     P  - product of (v) (vectorises)
    ,   - pair
      § - sums

```

# Answer
> 3 votes
# Charcoal, ~~61~~ ~~58~~ 22 bytes

```
≔Ｅ⁴ＥθΣ§λιθＩ⟦ΣＥθ⌈ιΣＥθΠι

```

Try it online! Takes input as a list of lists in a different orientation to the examples. Uses @Bubbler's formula. Explanation:

```
≔Ｅ⁴ＥθΣ§λιθ

```

Transpose the input while taking the count of the number of cubes in each row.

```
Ｉ⟦ΣＥθ⌈ιΣＥθΠι

```

Calculate the minimum and maximum cubes for each row, and then take the totals for all four rows.

---
Tags: code-golf, geometry, 3d
---


title: Four fours puzzle

text:
# Question
Title: Four fours puzzle
The Four fours puzzle is a popular recreational mathematical puzzle that involves using exactly four 4s (and no other number) and a defined set of operations to reach every number from 0 to a given maximum.

In this version, the only following operators are allowed:

* Any grouping symbols may be used
* Addition (`+`), Subtraction (`-`), Multiplication (`*`), Division (`/`)
* Factorial (`!`), Gamma function (`Γ`)
* Exponentiation (`^`), Square root ()
* Concatenation (eg. `44` is two `4`s)
* Decimal point (eg. `4.4` is two `4`s), Overbar (eg. `.4~ = 4/9`)

Standard order of operations applies.

Your program should generate, given an input between 0 and 100 inclusive, a correct solution for that input. If the program outputs an invalid solution to any input, that program is invalid.

For example, with an input of `0`, your program might generate `44-44`.

The use of external modules is not allowed. Only `_.4~` is allowed for the overbar operator - that is, only one `4` can be behind the decimal point.

This is code golf, so shortest solution wins.

---

**Edit**: To be extra clear, the program must output a set of the above operations applied to *exactly* four `4`s - no more, no less. Also, `.4 = 4/10` is a valid term, and counts as using only one `4`.

# Answer
## GolfScript (129 chars\*)

```
[4.`2'√4'24'4!'6'Γ4'1'Γ√4'120'ΓΓ4']2/:F{.F=[[44.`]]*\{`{+{'+*-'1/{:^;.[~@[\]{'()'1/*}%^*@@^~\]\}/}:|~2/~\+|;}+F/}%+}3*\{\0==}+?1=

```

Running time is on the order of 4 minutes on my PC. A moderate speed-up can be obtained at the cost of two characters by adding a uniqueness operation `.&` immediately after the `%+`.

I use pre-coded expressions for `1`, `2`, `4`, `6`, `24`, `120`, and `44`, and build the rest up from those using only `+`, `*`, and `-`. This way I don't need to do any non-integer arithmetic in the program itself. I've tried to get simpler expressions by placing the simpler pre-coded values at the start.

All of those values are required, and it's necessary to support both directions of subtraction (`complex_expression - simple_expression` and vice versa). It's also necessary to include some operations which require parentheses (specifically, `a*(b-c)`), so I bracket all subexpressions indiscriminately.

* I'm counting Unicode code points assuming the program to be UTF-8 encoded, and brushing under the carpet the fact that unless you're using a recent version of Ruby to run the interpreter it's really treating it as ASCII characters. If you're very worried about this, use `G` for Gamma and `v` for sqrt.

Well, strictly I could remove `44` in exchange for `11` as `44/4` and `71` as `√(Γ√4+(ΓΓ4+Γ√4)!)`, but that's not a good trade-off.
> 6 votes

# Answer
## Python 155 bytes

```
ï»¿h={4:'4',24:'4!',6:'â4',.4:'.4',1:'âû4',4/9.:'.4~'}
f={}
def g(r,s='24',y='4!'):f[eval(s)]=y;[g(r-1,s+o+`k`,y+o+h[k])for k in h for o in'/*-+'if r]
g(3)

```

The first three bytes (`\xEF\xBB\xBF`) are the UTF-8 byte order mark, although the file should be saved in an ANSI format. The `û` and `â` will be interpretted as  and `Γ` respectively in cp437 and cp850, which should work on just about any Windows box.

Runtime is about 0.4s on my computer.

Sample usage (name the file `four_fours.py`):

```
$ python
>>> from four_fours import f
>>> f[39]
'4!+4!/.4/4'
>>> f[87]
'4!*4-4/.4~'
>>> for i in range(101): print i, f[i]
0 4!+4!-4!-4!
1 4!+4!/4!-4!
2 4!-4!+Γ4-4
3 4!-4!+4-Γ√4
4 4!+4!/Γ4-4!
.
.
.
96 4!+4!+4!+4!
97 4!*4!/Γ4+Γ√4
98 4!*4+Γ4-4
99 4!*4+4-Γ√4
100 4!*4!/Γ4+4

```

Results for 0..100. Due to the way the hash is iterated, it prefers to use `4!` as often as possible.

Edit: saved a number of bytes by adding `Γ√4 = 1`, which eliminates the need for any groupings, and by removing `√4 = 2`, which was no longer necessary.
> 8 votes

# Answer
## J, 175 161 chars

```
   f=.')',~'(',;@((<;._2'+ - * % .4 .4~ g(r(4)) r(4) 4 g(4) 4! ( ) '){~(143402 A.i.9)
      /:~(12,11,0,6$0 4 4)+(9$4 7 7)#:((,@(+/,-/,*/,%/)~)^:2,0.4 4r9 1 2 4 6 24)&i.)

   f 1
(.4+.4)+(.4%r(4))

   f 42
(r(4)+4)+(g(4)*g(4))

   f 100
(r(4)+r(4))+(4*4!)

```

Checked format is `(v op v) op (v op v)` where `v={0.4 4/9 1 2 4 6 24}` and `op={+ - * /}`

full 0..100 results
> 4 votes

# Answer
# 05AB1E, ~~70~~ 69 bytes

```
•1OF•₂в"(4/9)"ª0.4ª©4ã"+-*/"3ãâε`.ιJ}.Δ.EQ}®¦¨ŽYyç"Γÿ4 Γ4 4! .4~"#:0K

```

Try it online or verify all test cases.

**Explanation:**

Uses a similar approach as some of the other answers. Creates all possible combinations of four of the values \\$\[1,4,6,24,\frac{4}{9},0.4\]\\$ and three of the operators `+-*/` (both of course with duplicates).

```
•1OF•                       # Push compressed integer 71160
     ₂в                     # Convert it to base-26 as list: [4,1,6,24]
       "(4/9)"ª             # Append "(4/9)": [4,1,6,24,"(4/9)"]
       0.4ª                 # As well as 0.4: [4,1,6,24,"(4/9)",0.4]
           ©                # Store this list in variable `®` (without popping)
4ã                          # Create all possible quartets by using the cartesian product times 4
"+-*/"                      # Push the string "+-*/"
      3ã                    # Create all possible triplets by using the cartesian product times 3
â                           # Create all possible pairs of both lists by using the cartesian product
 ε    }                     # Map each pair of lists by:
  `                         #  Push the list and string separated to the stack
   .ι                       #  Interleave them
     J                      #  And join them together
.Δ                          # Find the first which is truthy for:
  .E                        #  Evaluate the expression-string as Python code
                            #  (NOTE: Unfortunately doesn't work with .4 instead of 0.4)
    Q                       #  And check if it equals the (implicit) input-integer
}®                          # After we've found our result: push the list from variable `®`
  ¦¨                        # Remove the first and last items: [1,6,24,"(4/9)"]
    ŽYy                     # Push compressed integer 8730
       ç                    # Convert it to a character with this unicode: "√"
                            # (`√` isn't part of 05AB1E's codepage, hence why this is necessary)
        "Γÿ4 Γ4 4! .4~"     # Push this string, where the `ÿ` is automatically filled with the "√"
                       #    # Split it on spaces: ["Γ√4","Γ4","4!",".4~"]
                        :   # Replace the [1,6,24,"(4/9)"] with ["Γ√4","Γ4","4!",".4~"]
                         0K # And remove all 0s to convert the "0.4"s to ".4"s
                            # (after which the result is output implicitly)

```

See this 05AB1E tip (section *How to compress large integers?* and *How to compress integer lists?*) to understand why `•1OF•` is `71160`; `•1OF•₂в` is `[4,1,6,24]`; and `ŽYy` is `8730`.
> 0 votes

---
Tags: code-golf, math, arithmetic, expression-building
---


title: Four distinct 8-bit integers

text:
# Question
Title: Four distinct 8-bit integers
Submit a well-formed program or function with **usual I/O rules** which satisfy the input, output, and algorithm conditions below. **Shortest submission (in bytes) wins.** As always, standard loopholes are forbidden.

*In short:* Two distinct 8-bit integer inputs must produce two 8-bit integer outputs so that all four numbers are distinct, i.e., not equal.

# Input Conditions

Two distinct 8-bit integers, *a* and *b,* both of which are in 8-bit signed (or unsigned at your discretion) format.

# Output Conditions

Two 8-bit integers, *c* and *d,* which are in the same format as the input (signed or unsigned), such that *a,* *b,* *c,* and *d* are distinct, i.e., no two of them are equal to each other.

# Algorithm Conditions

1. The algorithm must halt for all possible valid inputs.
    * Valid inputs are those where *a* and *b* are distinct. When *a* and *b* are equal, the behaviour of the algorithm is unspecified.
2. The algorithm must be deterministic.
    * Running the algorithm with the same input must produce the same output.
3. The algorithm must satisfy the *output conditions* for all valid inputs.

# Verification

There are two ways to verify your algorithm.

1. Brute force: explicitly check the program for all valid input combinations.
2. Prove/show, by analysis, that a clash is impossible (preferred).

# FAQ

1. What if my programming language doesn't provide 8-bit integers?
2. What if my programming language doesn't support fixed-width integers?

* Only the range of the outputs matter; internal computations may be in any precision. If the outputs can be rounded/scaled to the required integral range, then the programming language is good to go.

---

# Edits

**Edit 1:** Thank you for the submissions! I am glad to see so many creative solutions! Initially, I planned to restrict the algorithm to one-to-one mapping (i.e., invertible), however, decided against it to make the problem simpler. Looking at the enthusiastic response, I will consider submitting a second code golf with the one-to-one mapping requirement.

# Answer
> 8 votes
# JavaScript (Node.js), ~~35~~ ~~31~~ ~~27~~ 23 bytes

*-4 bytes thanks to Arnauld and Kevin Cruijssen*

*-4 bytes thanks to xnor*

```
a=>b=>[c=3^a&1^b&2,c^4]

```

Try it online!

Explanation:

Takes the flipped 1 bit of the first number, and adds the flipped 2 bit of the second number, guaranteeing a number different from both inputs in the 2 least significant bits. Outputs this number, and 4 added to this number

# Answer
> 5 votes
# Perl 6, 20 bytes

```
{grep(.none,^4)[^2]}

```

Try it online!

Outputs the first two numbers from the range 0 to 3 that aren't in the input.

# Answer
> 4 votes
# brainfuck, 69 bytes

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

```

Try it online!

My solution takes the first input and counts it upwards and prints the first two numbers unless they are the second input. So if the first input is A and the second input is B the output will be:
A+2, A+3 if B = A+1 or
A+1, A+3 if B = A+2 or
A+1, A+2 else

This initializes position 1,2,3 of the band as the first input incremented by 1
,[->>->-<<<]
This substracts the second input from positions 2 and 3.
++
Set position 0 to 2, counting the numbers still to print
The band now reads: (2) a+1 a-b+1 a-b+1
>>>[[-]<<<->.>>]
If position 3 is not 0, print out position 1 and decrement position 0
<+<+>
Increment the band in position 1 and 2
[[-]<<->.>]
If position 2 is not 0, print out position 1 and derement position 0
<+<[->.<]
Increment at position 1, Position 0 is now either 1 or 0. If it is 1 print position 1 one more time. ```
</code></pre>

# Answer
> 3 votes
# 05AB1E, ~~9~~ 5 bytes

```
∞IK2£

```

I/O as a pair of integers.

Try it online or verify some more test cases.

**Explanation:**

```
∞      # Push an infinite positive list [1,2,3,...]
 IK    # Remove the values of the input-pair
   2£  # Only leave the first two values
       # (after which the result is output implicitly)

```

# Answer
> 3 votes
# Haskell, 32 bytes

```
a#b=take 2[i|i<-[1..],a/=i,b/=i]

```

Try it online! We pick the first two positive integers that aren't input numbers.

# Answer
> 2 votes
# Charcoal, ~~27~~ 10 bytes

```
Ｉ…⁻Ｅ⁴ιＥ²Ｎ²

```

Try it online! Link is to verbose version of code. Uses the same set difference algorithm as everyone else. Less boring 27-byte version actually tries to produce interesting outputs for all inputs:

```
ＮθＮηＩ﹪⁺÷¹²⁸⊕¬﹪⁻θη¹²⁸⟦θη⟧²⁵⁶

```

Try it online! Link is to verbose version of code. Takes unsigned integers. Explanation: Flips the top bits of the values, unless this would exchange them, in which case adds 64 (modulo 256) instead.

# Answer
> 2 votes
# JavaScript (ES6),  ~~32 27~~  26 bytes

Takes input as `(x)(y)`.

```
x=>y=>[x^=k=y^x^1?1:2,y^k]

```

Try it online!

# Answer
> 2 votes
# Octave, ~~28~~ 22 bytes

```
@(x)setxor(1:4,x)(1:2)

```

Try it online!

### Explanation

Anonymous function that outputs the first 2 entries from the sorted symmetric difference between `[1 2 3 4]` and the input.

# Answer
> 1 votes
# Pyth, 5 bytes

```
>2-Uy

```

Try it online!

# Explanation

```
    y # Repeat the input
   U  # Generate a length range: [0 .. 3]
  -   # Difference with implicit input
>2    # Slice out the last 2 items of the resulting list

```

# Answer
> 1 votes
# Python 3, 27 bytes

```
lambda s:[*{0,1,2,3}-s][:2]

```

Try it online! The input is a set `s` with the integers. We build the set `{0, 1, 2, 3, 4, 5, 6, 7, 8}` and then perform set subtraction to remove, from that set, any input numbers. We then convert to a list and extract two elements.

*Thanks Surculose for saving me 2!*

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

port of @Jo King's answer

```
Complement[Range@4,{##}][[;;2]]&

```

Try it online!

# Answer
> 1 votes
# C (gcc), <sup>~~36~~ ~~34~~</sup> 28 bytes

Saved ~~2~~ 8 bytes thanks to ceilingcat!!!

```
f(x,y){x=(~y&2|~x&1)*257+4;}

```

Try it online!

Uses Paul Mutser's formula.
Returns the two 16-bit values in a 32-bit `int` since there are no tuples *&c* in C.

# Answer
> 1 votes
# Japt, 8 bytes

```
Hõ kU ¯2

```

Try it

# Answer
> 1 votes
# Bash \+ Core utilities, 29 bytes

```
seq 4|egrep -v $1\|$2|head -2

```

Try it online!

Input is passed in two arguments, and the output is printed to stdout.

This prints the first two positive integers that aren't either of the two arguments.

# Answer
> 1 votes
# Python 3.8, <sup>~~31~~</sup> 29 bytes

Saved 2 bytes thanks to xnor!!!

```
lambda x,y:(k:=~x&1|~y&2,k+4)

```

Try it online!

# Answer
> 0 votes
# Erlang (escript), 43 bytes

Outputs the first two numbers from the range 0 to 3 that aren't in the input.

```
f(A)->lists:sublist(lists:seq(0,3)--A,1,2).

```

Try it online!

# Answer
> 0 votes
# , 5 bytes

Takes input as a pair of integers.

```
%G?←√

```

Uncompressed:

```
4k     Range from 1 to 4
  at   Trim out all items that appear in the input
    2< Take the first two items of the output list.

```

# Answer
> 0 votes
# Io, 46 bytes

Port of RGS's Python answer.

```
method(x,list(1,2,3,4)difference(x)slice(0,2))

```

Try it online!

# Answer
> 0 votes
# Alchemist, 60 bytes

```
_->In_x+In_y+2n
n+x+y->Out_z+z+Out_" "
x+0y->z+3y
y+0x->z+3x

```

Try it online!

As with many answers here, prints the first two non-negative integers not in the input. Input is unsigned, since Alchemist doesn't have signed numbers.

I similarly can't just let a variable "go negative" after it hits zero, so I just let an input value `x` also exclude `x+4`, `x+8`, and so on. This has no effect on anything, provided both variables don't hit zero at the same time. Fortunately, if they ever become the same, both outputs will happen before they hit zero.

# Answer
> 0 votes
# Ruby, 22 bytes

```
->*a{([*6..9]-a)[0,2]}

```

Try it online!

Same method as almost everybody.

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


title: KoTH: Highest HP is Eliminated!

text:
# Question
Title: KoTH: Highest HP is Eliminated!
In this challenge, bots must survive as long as possible. In each turn, the bot with the most HP is eliminated.

This challenge is inspired by the Smallest unique number KoTH.

### Results

After 100,000 rounds:

```
Jack: 63390
The Follower: 4942
The Algorithm: 2452
The Randomiser: 140
Toe Tipping: 0
EZ: 0
The Average: 0
LowProfile2: 0
Lower Profile: 0
The Bandwagon: 0
Fair Share: 0
Low Profile: 0

```

### Game Details

* In each game, all bots start with 100 HP
* In each turn:
    + All bots select an amount of HP to lose (minimum 1, inclusive)
    + Each bot loses the amount of HP they returned
    + All bots with 0 HP or less are eliminated
    + The bot with the highest HP is eliminated
    + If there is a tie for highest HP, all bots that tied are eliminated
* The last bot alive wins 1 point
* If all remaining bots are eliminated in the same turn, no points are awarded
* After a number of games (default is 1000), the winner is the bot with the most points

### Bot Format

Each bot should be a JavaScript function, which is run once per turn. This function will be provided three arguments:

* The bot's HP
* The HP of all other bots as of the last turn, or 0 if dead
    + Formatted as an array, will be randomly shuffled for each game
* An object which can be used for storage between turns

The return value of this function should be a number (minimum 1, inclusive), representing the amount of HP to take. If the return value is not a number or is less than 1, it defaults to 1.

### Example Bot

Example Bot tries to keep its HP 2 below the previous turn's average.

```
function(hp, others, storage) {
    var alive = others.filter(bot => bot > 0);
    var avg = alive.reduce((a, b) => a + b, 0) / alive.length;
    return hp - (avg - 2);
}

```

### Controller

```
//Bots go in this object:

const bots = {
    "Example Bot": function(hp, others, storage) {
        var alive = others.filter(bot => bot > 0);
        var avg = alive.reduce((a, b) => a + b, 0) / alive.length;
        return hp - (avg - 2);
    }
};

//games: Number of games to run
//log: An array of bot names to log info about, or empty array for game overviews

function runGames(games = 1000, log = null) {
    let p = performance.now();
    let botData = [];
    for (let bot in bots)
        botData.push({
            name: bot,
            run: bots[bot],
            uid: 0,
            hp: 0,
            points: 0,
            storage: {},
        });
    for (let g = 0; g < games; g++) {
        let uids = new Array(botData.length).fill(0).map((a, b) => b);
        let turn = 0;
        if (log)
            console.log("[0] Starting game " + (g + 1));
        for (let j, i = uids.length - 1; i > 0; i--) {
            j = Math.floor(Math.random() * (i + 1));
            [uids[i], uids[j]] = [uids[j], uids[i]];
        }
        for (let i = 0; i < botData.length; i++) {
            botData[i].uid = uids[i];
            botData[i].hp = 100;
            botData[i].storage = {};
        }
        do {
            let hps = [];
            let max, alive;
            turn++;
            for (let hp, b, i = 0; i < botData.length; i++) {
                b = botData[i];
                if (!b.hp)
                    continue;
                try {
                    hp = Number(b.run(
                        b.hp,
                        botData.map(a => [a.uid, a.hp]).sort((a, b) => a[0] - b[0]).filter(a => a[0] != b.uid).map(a => a[1]),
                        b.storage
                    ));
                    if (log && log.includes(b.name))
                        console.log("[" + turn + "] " + b.name + " (" + b.hp + "): " + hp);
                } catch(e) {
                    hp = 100;
                    if (log && log.includes(b.name))
                        console.warn(b.name + " (" + JSON.stringify(b.storage) + "):\n" + (e.stack || e.message));
                }
                hps[i] = Number.isNaN(hp) ? 1 : Math.max(1, hp);
            }
            for (let i = 0; i < botData.length; i++) {
                if (hps[i]) {
                    botData[i].hp = Math.max(0, botData[i].hp - hps[i]);
                    if (!botData[i].hp && log)
                        console.log("[" + turn + "] Eliminated: " + botData[i].name + " (0)");
                }
            }
            alive = botData.filter(a => a.hp);
            if (alive.length == 1)
                alive[0].points += 1;
            if (alive.length <= 1)
                break;
            max = Math.max(...botData.map(a => a.hp));
            for (let i = 0; i < botData.length; i++) {
                if (botData[i].hp == max) {
                    if (log)
                        console.log("[" + turn + "] Eliminated: " + botData[i].name + " (" + botData[i].hp + ")");
                    botData[i].hp = 0;
                }
            }
            alive = botData.filter(a => a.hp);
            if (alive.length == 1)
                alive[0].points += 1;
            if (alive.length <= 1)
                break;
        } while (1);
    }
    console.log(games + " game(s) completed (" + ((performance.now() - p) / 1000).toFixed(3) + "s):\n" + botData.map(a => [a.name, a.points]).sort((a, b) => b[1] - a[1]).map(a => a[0] + ": " + a[1]).join("\n"));
}

```

### Rules

* Accessing the controller or other bots is not allowed
* There's no time limit, but keep within reason
* Any bots that error are eliminated
* Clarification: Fractional HP is allowed
* Deadline: ~~Wednesday, March 25, 12:00 UTC (8:00 EDT)~~ **Closed to submissions!**

# Answer
> 10 votes
# Jack

Assumes that half of the bots are stupid. So they will kill theirselves or will end up being killed simultaneously with another bot. We just need to make sure to have enough HP to survive it for enough rounds knowing that.

```
function(hp, others, storage) {
    var nrOfBots = others.filter(bot => bot > 0).length;
    var hpToTake = 1;
    if (hp == 100) {
        hpToTake = hp - (Math.round(nrOfBots / 2) + 0.0001);
    }
    return hpToTake;
}

```

# Answer
> 12 votes
# Low Profile

```
function(hp, others, storage) {
    var alive = others.filter(bot => bot > 0);
    return hp - alive.length
}

```

Sets its health to be always equal to the number of bots. Any bot that undercuts this one risks eventually hitting zero health.

# Answer
> 6 votes
# The Follower

```
function(hp, others, storage) {
    if (!storage.prev){
        storage.prev = others.slice();
        return hp * (Math.random() * 0.1 + 0.8);
    }
    let [decSum, decCnt] = others.reduce(([s,n],v2,i) => {
        if (v2 <= 0) return [s, n];
        return [s * (storage.prev[i]-v2), n + 1];
    }, [1,0]);
    storage.prev = others.slice();
    let avg = decSum ** (1 / decCnt);
    while (avg > hp) avg /= 2;
    return hp - avg;
}

```

Uses the geometric mean of the decrements chosen by alive opponents (in the previous turn) to decide its next move. There is no such information at the first turn, so it cuts a very large part of its own HP to be safe.

# Answer
> 4 votes
# The Bandwagon

```
function(hp, others, storage) {
    if (hp > 4)
        return 48;
    return Math.max(...others) - 1.5;
}

```

It's a bit slow to catch onto the trend, and it's not very low profile about it.

It bases its strategy on the assumption that, after 2 turns, it's the endgame. It assumes all the others are going to return 1, and ensures it doesn't die by returning 1.5.

# Answer
> 4 votes
# LowProfile2

```
function(hp, others, storage) {
        var epsilon = 1;
        while (hp + 1 - (epsilon / 2) != hp + 1) {
            epsilon = epsilon / 2;
        }
        var alive = others.filter(bot => bot > 0);
        return hp - alive.length + 1 - epsilon
}

```

Thanks to the discovery of fractional HP, I realized my old integer-based LowProfile submission could be beaten by one using it. I therefore present LowProfile2, which dynamically calculates the very limits of how close to death one can be!

# Answer
> 4 votes
# Toe Tipping

```
function(hp, others, storage) {
    var highestAlive = Math.max(...others);
    var returnVal = highestAlive / 2 - 0.1;
    return Math.min(returnVal, hp-1);
}

```

Looks for the highest bot alive, and returns 0.1 below halve that bot's HP.

# Answer
> 3 votes
# Average

```
function(hp, others, storage) { return Math.floor(hp/3); }

```

Loses a third of its HP every turn, dying in 13 turns if it doesn't end up as highest. (returning zero gets silently interpreted as returning 1 by the controller)

# Answer
> 3 votes
# Lower Profile

```
function(hp, others, storage) {
    var alive = others.filter(bot => bot > 0);
    return hp - alive.length + 1
}

```

Tries to get lower than, but close to, **Low Profile**. But looks like it can't win by itself. :(

With an ally having `+ 2` instead of `+ 1` (I call it Lowest Profile), snipes Low Profile and this bot wins. Try it online!

# Answer
> 3 votes
# The Randomiser

```
function(hp, others, storage) {
    var highestAlive = Math.max(...others);
    var returnVal = highestAlive * Math.random();
    return hp > returnVal ? returnVal
                          : hp * Math.random();
}

```

Returns a random number \\$0\dots hp\\$ of the highest bot alive (if we have enough \\$hp\\$ else a random number \\$0\dots hp\\$ of our \\$hp\\$).

# Answer
> 2 votes
## Fair Share

```
function (hp, others, storage) {
    return hp / (1 + others.filter(bot => bot > 0).length) | 0;
}

```

The more bots are left, the more of its hp it has to ditch in order to try to keep ahead.

# Answer
> 2 votes
# The Algorithm

```
function(hp, others, storage) {
    var rate = (storage.rate || (storage.rate = Math.random() * 0.25 + 0.3));
    var alive = others.filter(bot => bot > 0);
    var avg = alive.reduce((a, b) => a + b, 0) / alive.length;
    return hp > avg * rate ? hp - avg * rate : 1;
}

```

Picks a random value for each game, and will attempt to set its HP to that value multiplied by the current average.

---
Tags: king-of-the-hill, javascript
---


# Question
Title: Take It or Leave It III: A Game Show for Computers
This is the third in a series of puzzles that I will be posting every Monday at Midnight PST, and the final variant of "Take It or Leave It".

The first puzzle is located Here

The second puzzle is located Here

**Context:**

> A reclusive billionaire has created a game show to attract the world's best and brightest programmers. On Mondays at the stroke of midnight, he chooses one person from a pool of applicants to be the contestant of the week, and provides them with a game. You are this week's lucky contestant!

**This week's game:**

> The host provides you with API access to a stack of 15,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $15,000 (no two envelopes contain the same dollar value).
>
> You have 5 commands at your disposal:
>
> 1. Read(): Read the dollar figure in the envelope at the top of the stack.
> 2. Take(): Add the dollar figure in the envelope to your game show wallet, and pop the envelope off the stack.
> 3. Pass(): Pop off the envelope on the top of the stack.
> 4. Oracle(M): Returns the mean value of the next M envelopes in the stack, not including the one you can currently Read().
> 5. End(): Stop the game, and walk away the money currently in your wallet (your final score).

**The Rules:**

> 1. If you use Pass() on an envelope, the money within is lost forever.
> 2. If you use Take() on an envelope containing $X, from that point forward, you may never use Take() on an envelope containing \< $X. Take() on one of these envelopes will add $0 to your wallet.
> 3. If you use Oracle(M) on turn T, envelopes T+1 through T+M's mean will be returned. Oracle() is disabled until turn T+M.
> 4. If you use Take() or Pass() on turn T, $T is removed from your wallet.

Write an algorithm that finishes the game with the maximal amount of money.

Note 1: "Maximal" in this case means the median value in your wallet after N \>= 1000 runs. I expect, though I would love to be proven wrong, that the median value for a given algorithm will converge as N increases to infinity. Feel free to try to maximize the mean instead, but I have a feeling that the mean is more likely to be thrown off by a small N than the median is.

Note 2: This puzzle has a significant difference from the first two iterations (namely, needing to pay for each envelope you take). Feel free to use any strategies from the first puzzles as a base, but be warned: They will probably (read: definitely) get a negative score without some kind of modification.

Edit: The prize condition has been removed, in light of this post on meta.

# Answer
## Java, $3889.5 Median

```
        int highest=0;
        int topp=0,tott=0;
        for(int i=0;i<1000;i++){
            if(Read()>topp&&tott+Read()-i>tott){
                topp=Read();
                tott += Read();
                tott -= i;
                Take();
            }else{
                if(tott-i>i/2){
                    tott -= i;
                    Pass();
                }else{
                    End();
                    break;
                }
            }
            if(highest/1.1>tott){
                End();
                break;
            }
            if(tott>highest)
            highest=tott;
        }

```

Try it Online
> 1 votes

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


title: Polycops and Robbers (Robbers' Thread)

text:
# Question
Title: Polycops and Robbers (Robbers' Thread)
This is the robbers' thread, the cops' thread is here

---

A polyglot is a program, that without modification, can run in multiple languages.

---

# Robbers' Challenge

First, find a vulnerable cop's answer, then try to find languages that the submission works in, if you found any that weren't listed by the cop, then you just cracked their answer. Post an answer linking to the original answer and what languages you found it working on (it must do the same thing on each language). You can then leave a comment on their answer linking back to your answer on this thread.

---

# Winning

Most upvoted answer that actually does crack the cops' code wins

# Answer
# Foo, PotatoLatte's answer

```
puts "Hello World!"

```

Try it online!

Ah, the bane of cops and robbers, Foo.
> 4 votes

# Answer
# Befunge-93, Shieru Asakotu's answer

```
'<?php '//'; #@ SPELL,WITH,ME, ,H,E,L,L,O, ,W,O,R,L,D,"'Hello, World!'"
$a = "'Hello, World!'";
if ([])
 console.log($a); //This should be an easy one to solve
else {
 for ($i = 1; $i < strlen($a) - 1; $i++)
  echo($a[$i]);
}
// ?>'

```

Try it online!

Prints `'Hello, World!'`, quotes included.
> 2 votes

# Answer
# Perl 6, Julia 0.4, , etc., Cortex's answer

```
#|
print("Hello, World!")# w|#(write-line "Hello, World!")

```

Try Perl online!

Try R online!

Try Julia 0.4 online!
> 0 votes

---
Tags: popularity-contest, cops-and-robbers, polyglot
---


# Question
Title: Composition of permutations – the group product
Given two permutations in disjoint cycle form, output their product/composition in disjoint cycle form.

To find the composition, convert the disjoint cycles to permutations in two-line notation. Each number in a disjoint part of a cycle is mapped to the number following it in the same part. It wraps around. So `1 -> 5`, `5 -> 1`, `2 -> 4`, `4 -> 2`. If a number is not found, `3 -> 3`, it is mapped to itself. The first disjoint cycle could also be written `(1 5)(2 4)(3)`. These mappings are converted to two lines, like so (note that the order of **P** and **Q** are reversed):

> \[T\]he product of two permutations is obtained by rearranging the columns of the second (leftmost) permutation so that its first row is identical with the second row of the first (rightmost) permutation. The product can then be written as the first row of the first permutation over the second row of the modified second permutation.

Wikipedia article

---

### Rules:

* Input will be given as a list of lists or similar format
* You may **not** take something like `(1 5)(2 4)` as `[5, 4, 3, 2, 1]`, already in two-line form (mapping index to value)
* Not all numbers have to occur in each group, so you could have `(1 5)·(1 2)`, resulting in `(2 5 1)`.
* Your output should be able to be used as your input.
* You do not need to support input with an empty cycle `(1 5)·()`. That would instead be given as `(1 5)·(1)` or something equivalent.
* Since cycles wrap around, the order doesn't matter as long as the result is correct.
* You can start at zero or one. It doesn't matter, because the results are the same.
* The numbers can be larger than `9`.
* You may not include the same number more than once in the output. So `[[1],[1]]` is not allowed.
* Note that this operation is **not commutative**! I put Q before P, because that's what Wikipedia did. You can choose any order, but specify which if it's different.
* Shortest code wins
* Built-ins are allowed, but if you use one, show a solution without using it as well.

### Examples:

Not all equivalent output possibilities are shown

```
Input
Output

[[1, 5], [2, 4]], [[1, 2, 4, 3]]
[[1, 4, 3, 5]] (or [[4, 3, 5, 1]] or ...)

[[1, 5]], [[1, 2]]
[[2, 5, 1]]

[[10, 2, 3]], [[2]]
[[3, 10, 2]]

[[1]], [[3]]
[[]] (or [[1]] or something equivalent)

[[10,2,3,15],[1,7],[5,6],[14,4,13,11,12]], [[5,6,7,9,14],[2,8,3,10],[1,11]]
[[12, 14, 6, 1], [8, 15, 10, 3, 2], [13, 11, 7, 9, 4]]

(arguments in reverse order from above gives a different answer)
[[5,6,7,9,14],[2,8,3,10],[1,11]], [[10,2,3,15],[1,7],[5,6],[14,4,13,11,12]]
[[9, 14, 4, 13, 1], [10, 8, 3, 15, 2], [7, 11, 12, 5]]

```

# Answer
# , 7 bytes

```
C.@C.@,

```

Try it online!
> 2 votes

# Answer
# Haskell, ~~157~~ 148 bytes

EDIT:

* -9 bytes: That could indeed be golfed more. Removed redundant parentheses around `p++q`. Swapped argument order of `g`. Got rid of `d` by starting `iterate` with `p x`, after which `takeWhile` no longer tied with `fst` \+ `span`. Made `iterate` infix.

Doing this while I'm late... probably can golf some more.

It was simpler, and seemed to be allowed, so the output includes single-element cycles.

```
q#p=g(p++q>>=id)$f q.f p
f p a=last$a:[y|c<-p,(x,y)<-zip(0:c)(c++c),x==a]
g(x:l)p|c<-x:fst(span(/=x)$p`iterate`p x)=c:g[x|x<-l,x`notElem`c]p
g[]p=[]

```

Try it online!

**How it works:**

* `#` is the main function. `q#p` takes two lists of lists of numbers, and returns a similar list. The tests seem to have Q before P so I used the same order.
* `f p` converts the permutation `p` from disjoint cycle form to a function, after which `f q` and `f p` can be composed with the usual composition operator `.`.
    + The list comprehension iterates through the cycles `c`, searching for `a` and finding its successor. If the comprehension finds nothing, `a` is just returned.
    + `zip(0:c)(c++c)` is a list of pairs of elements of `c` and their successors. Since the question lets us "start at one" we can use `0` as a dummy value; it's cheaper to prepend that to `zip`'s first argument than to use `tail` on the second.
* `g l p` takes a list `l` of elements, and a permutation function `p`, and returns the list of cycles touching the elements.
    + Here `c` is the cycle containing the first element `x` of the list, the other elements of `c` are found by iterating from `p x` until `x` is found again. When recursing to find the remaining cycles, all elements of `c` are first removed with a list comprehension.
> 3 votes

# Answer
# Mathematica, 15 bytes

```
##⊙Cycles@{}&

```

Yes Virginia, there is a builtin.... Mathematica supports a permutation data type already in disjoint cycle notation: this pure function takes as input any number of arguments in the form `Cycles[{{1, 5}, {2, 4}}]` and outputs the product permutation, again in `Cycles[]` form. It uses the opposite ordering convention as the OP, so for example,

```
##⊙Cycles@{}&[Cycles[{{1, 2, 4, 3}}], Cycles[{{1, 5}, {2, 4}}]]

```

returns `Cycles[{{1, 4, 3, 5}}]`. The  symbol I used above should really be the 3-byte private-use Unicode symbol U+F3DE to work in Mathematica. Note that Mathematica has a named builtin for this operation, `PermutationProduct`, but that's three bytes longer.
> 3 votes

# Answer
# Python, 220 bytes

```
a,b=eval(input())
p,o=a+b,[]
for i in range(1,1+max(map(max,p))):
 if not any(i in t for t in o):
  u,m=(i,),i
  while 1:
   for t in p[::-1]:
    if m in t:m=t[(t.index(m)+1)%len(t)]
   if m==i:o+=[u];break
   u+=(m,)
o

```
> 1 votes

# Answer
# Python 3.8, 187 bytes

```
q,p=eval(input())
g=lambda p,i:[*(c[c.index(i)-1]for c in p if i in c),i][0]
h=lambda*c:(x:=g(p,g(q,c[0])))in c and(*c[(m:=c.index(min(c))):],*c[:m])or h(x,*c)
exit({*map(h,sum(p|q,()))})

```

Try it online! or Check all test cases!

**Input**: `q` and `p` in that order, each is a set of tuples, from `STDIN`.
**Output**: The product permutation `Q·P` as a set of tuples, to `STDERR`.

### Explanation

The function `g` finds which number maps to the number `i` in the permutation `p` (aka `g` is the inverse permutation of `p`).

```
g=lambda p,i:
[                   # creates a list
  *(                # containing the following
    c[c.index(i)-1] #   the number before i in cycle c
    for c in p      #   for all cycles in permutation
    if i in c       #   if i is in that cycle
  )                 #
  ,i                # adds i to the end of that list
                    #   (in case i is not in any cycle)
][0]                # returns the first element of the list

```

The function `h` takes in a number, and returns the cycle in `Q·P` that contains that number. The returned cycle will be a tuple, formatted in a way such that the smallest element is at index 0.

```
h=lambda*c:                   # input: an incomplete cycle c, as a list
(x:=g(p,g(q,c[0])))           # finds the number x before the first number in c
in c                          # if x is also in c (aka the cycle is complete)
and                           # then returns the following:
(                             #   c as a tuple with min element at index 0
  *c[(m:=c.index(min(c))):],  #   (c, from the min element to the end)
  *c[:m]                      #   (c, from start to the min element)
)
or                            # else (cycle is incomplete) returns the following
h(x,*c)                       #   recursive result when after prepending x to c

```

By applying `h` to all numbers, we can get all cycles in `Q·P`. To prevent duplicate cycles in our result, we simply put all cycles in a set. This works since similar cycles returned by `h` will be formatted to the same tuple (with the smallest element at index 0).
We only needs to consider the numbers appearing in `P` or `Q`, as all other numbers will map to themselves.

```
exit(              # returns through STDERR
  {                # create a set from the followings
    *map(h,        #   map function h to
      sum(p|q,())  #   all numbers in P or Q
    )
  }
)

```
> 1 votes

---
Tags: code-golf, permutations, abstract-algebra
---