title: ASCII Exact Cover with Rectangles

text:
# Question
Title: ASCII Exact Cover with Rectangles
# Challenge

Given a rectangular area arrange a group of rectangles such that they cover the rectangular area entirely.

# Input

* An integer denoting the height.
* An integer denoting the width.
* The dimensions of the rectangles consisting of the following form: `axb,cxd,...` where `a,b,c,` and `d` are integers - any reasonable format is acceptable.

# Output

An exact cover of the rectangular area.

Rectangles used to cover the area are represented in the following way:

`2x3`

```
00
00
00

```

or

```
000
000

```

`1x3`

```
0
0
0

```

or

```
000

```

Each rectangle is represented using a character `0-9` where `0` is used for the first rectangle inputted `1` for the second and so on. The max number of rectangles given in input is therefore 10.

# Test Cases

### Input 1

```
5
7
4x2,3x2,3x2,5x2,5x1

```

### Output 1

```
0000111
0000111
2233333
2233333
2244444

```

### Input 2

```
4
4
3x2,2x1,2x2,2x2

```

### Output 2

```
0001
0001
2233
2233

```

### Input 3

```
2
10
4x2,3x2,3x2

```

### Output 3

```
0000111222
0000111222

```

# Clarifications

* The dimensions of the rectangles used to cover the region are interchangeable e.g. for `axb` `a` could be the height or width same goes for `b`.
* If there are multiple solutions any of them is acceptable (just display 1).
* Assume all inputs are valid.
* You can have a full program or a function (inputs may be treated broadly as 3 separate arguments).
* Output to stdout (or something similar).
* This is so shortest answer in bytes wins.

# Answer
> 1 votes
# Python 3, 262 bytes

```
from numpy import*
def g(h,w,t,m,i):
 if[]==t:print(m);return
 u,v=t[0]
 for _ in'12':
  for r,c in argwhere(m<0):
   if(m[r:r+u,c:c+v]<0).all()and u+r<=h and v+c<=w:e=copy(m);e[r:r+u,c:c+v]=i;g(h,w,t[1:],e,i+1)
  u,v=v,u
f=lambda h,w,t:g(h,w,t,zeros((h,w))-1,0)

```

Called like: `f(4,4,[(3,2),(2,1),(2,2),(2,2)])`. It uses a brute force, recursive function that prints all solutions (uses fewer bytes).

# Answer
> 4 votes
# APL (Dyalog Unicode), 76 bytes

```
⎕CY'dfns'
{⍺⍴v+.×(X m)⌿m←⊃⍪/(⍺∘{⍪↑,(⍳⍺)↓¨⊂⌽⊖⍺↑⍵⍴1}¨⊢∘⌽\2/⍵),⍤1¨2/↓∘.=⍨v←⍳≢⍵}

```

Try it online!

Dyalog APL comes with a built-in Exact Cover solver `X`, so the main part of the code is construction of the **constraint matrix**.

A constraint matrix is a boolean matrix where a column indicates a **constraint**, and a row indicates an **action** that satisfies some of the constraints. In the case of rectangle cover, an action is positioning of a specific rectangle at certain position and orientation, which satisfies two kinds of constraints: a specific rectangle is consumed, and the certain cells are covered by that rectangle.

For example, consider positioning a `2×3` rectangle in a `4×4` rectangular space. There are 12 ways to place it inside the space:

```
Horizontally
OOO. .OOO
OOO. .OOO
.... ....
.... ....

.... ....
OOO. .OOO
OOO. .OOO
.... ....

.... ....
.... ....
OOO. .OOO
OOO. .OOO

Vertically
OO.. .OO. ..OO
OO.. .OO. ..OO
OO.. .OO. ..OO
.... .... ....

.... .... ....
OO.. .OO. ..OO
OO.. .OO. ..OO
OO.. .OO. ..OO

```

If it is the second rectangle out of four rectangle pieces, a part of the constraint matrix would look like this (where type 1 constraints mark the rectangle used, and type 2 mark the cells occupied):

```
            <--           Type 2           -->
<-Type 1->  <-r1-->  <-r2-->  <-r3-->  <-r4-->
0 1 0 0     1 1 0 0  1 1 0 0  1 1 0 0  0 0 0 0
0 1 0 0     0 1 1 0  0 1 1 0  0 1 1 0  0 0 0 0
0 1 0 0     0 0 1 1  0 0 1 1  0 0 1 1  0 0 0 0
0 1 0 0     0 0 0 0  1 1 0 0  1 1 0 0  1 1 0 0
0 1 0 0     0 0 0 0  0 1 1 0  0 1 1 0  0 1 1 0
0 1 0 0     0 0 0 0  0 0 1 1  0 0 1 1  0 0 1 1
...

```

In the actual code, the fact that "there will always be a solution" is abused for the sake of golfing. It actually generates a matrix where type 2 comes before type 1, and the rectangle pieces are allowed to be partially overflowed to the top left. It still works since using an overflowed piece will always fail to cover the entire rectangular area.

```
⍝ Load dfns library to use the function X
⎕CY'dfns'

⍝ An inline function; ⍺←area (w,h), ⍵←n pieces
{
  v←⍳≢⍵    ⍝ Generate 0..n-1
  ↓∘.=⍨    ⍝ Generate Type 1 constraints as a nested array
  2/       ⍝ Two copies of each, to match with two orientations of each rect
  ,⍤1¨     ⍝ Concatenate row-wise with
  (...)    ⍝ the Type 2 constraints:
  2/⍵      ⍝   Two copies of each rectangle
  ⊢∘⌽\     ⍝   Flip the rows and columns at odd (0-based) indices
  ⍺∘{...}¨ ⍝   Generate boolean matrices for each rectangle:
  ⍺↑⍵⍴1    ⍝     Create the rectangle-shaped 1s, 0-filled to the size of the space
  ⌽⊖       ⍝     Reverse in both dimensions, so the 1s go to the bottom right
  (⍳⍺)↓¨⊂  ⍝     The above with leading rows/columns dropped in all possible ways
           ⍝     (all combinations of 0..h-1 rows and 0..w-1 columns dropped)
  ⍪↑,      ⍝     Format the result as Type 2 constraint sub-matrix
  m←⊃⍪/    ⍝ Vertically concatenate all the constraint sub-matrices
           ⍝ generated for each rectangle
  (X m)⌿m  ⍝ Solve the Exact Cover problem, and extract the rows
           ⍝ (the collection of rectangles that actually cover the area)
  v+.×     ⍝ Number the cells by the containing rectangle's 0-based index
  ⍺⍴       ⍝ Reshape the cells to the shape of the area
}

```

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


title: What is the Subspace Dimension?

text:
# Question
Title: What is the Subspace Dimension?
## Challenge

Given the Cartesian coordinates of two or more distinct points in Euclidean n-space (\\$\mathbb{R}^n\\$), output the minimum dimension of a flat (affine) subspace that contains those points, that is 1 for a line, 2 for a plane, and so on.

For example, in 3-space (the 3-dimensional world we live in), there are a few possibilities:

1. The points are not coplanar, e.g. `(0,0,0),(0,0,1),(0,1,0),(1,0,0)`. The full 3 dimensions would be needed to describe the points, so the output would be `3`
2. The points are coplanar but not all collinear, e.g. `(0,0,0),(1,0,0),(0,1,0),(1,1,0)`. The points lie on a 2-dimensional surface (a plane), so the output would be `2`.
3. The points are collinear, and there is more than one, e.g. `(0,0,0),(1,0,0)`. They all lie on a line (1-dimensional), so the output is `1`.
4. One or zero points are given. You do not have to handle these degenerate cases.

As @user202729 pointed out in sandbox, this is equivalent to the rank of the matrix whose column vectors are the given points if one of the points is the zero vector.

I encourage upvoting answers that don't have built-ins do most of the work, but they are valid answers.

## Details

1. The coordinates of each point will always be integers, so errors due to excessive floating-point roundoff are not acceptable
2. Again, you do not have to handle fewer than 2 points
3. The dimension `n` will be at least 2
4. The set of points can be taken in any format that encodes equivalent information to a list of n-tuples. Your program/function may also take `n` as input if you desire.
5. Note that the subspace may not necessarily pass through the origin\*
6. This is , so shortest bytes wins

\*Mathematically, if we require the subspace to pass through the origin, then it would be more specifically called a "linear subspace", not just flat.

## Testcases

```
n points -> output
2 (1,0),(0,0) -> 1
2 (0,1),(0,0) -> 1
2 (6,6),(0,-2),(15,18),(12,14) -> 1
2 (0,0),(250,500),(100001,200002) -> 1
2 (0,0),(250,500),(100001,200003) -> 2
2 (3,0),(1,1),(1,0) -> 2
3 (0,0,0),(0,0,1),(0,1,0),(1,0,0) -> 3
3 (0,0,0),(1,0,0),(0,1,0),(1,1,0) -> 2
3 (0,0,0),(1,0,0) -> 1
4 (1,2,3,4),(2,3,4,5),(4,5,6,7),(4,4,4,4),(3,3,3,3),(2,2,2,2) -> 2
5 (5,5,5,5,5),(5,5,6,5,5),(5,6,5,5,5),(6,5,5,5,5),(5,4,3,2,1) -> 4

```

Related Challenges:

# Answer
# MATL, 12 bytes

```
t1Y)-X$&Yvoz

```

Input is a matrix, where each row defines a point.

Try it online! Or verify all test cases.

### Explanation

The code uses the singular value decomposition of a matrix, which is done symbolically to prevent floating-point issues. The rank of a matrix equals the number of non-zero singular values.

```
t      % Implicit input: matrix of integer values. Duplicate
1Y)    % Get the first row
-      % Subtract, with broadcast. This subtracts this row from each row
X$     % Convert to symbolic matrix. Note that integers, are represented
       % exactly as floating-point values up to ±2^53.
&Yv    % Single-output singular value decomposition. Gives a vector with
       % the singular values
o      % Convert to floating point. Note that 0 is represented exactly
       % as a floating-point value
z      % Number of nonzeros. Implicit output

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), 23 bytes

```
MatrixRank@*Differences

```

Try it online!

Alternative: (23 bytes, 21 characters)

```
MatrixRank[#&@@#-#]&

```

Try it online!

`SingularValueDecomposition` in Mathematica is already 26 bytes long.
> 4 votes

# Answer
# APL (Dyalog Unicode), 17 bytes

```
≢⍸1≠1+2⊃8415⌶2-⌿⎕

```

Try it online!

Happens to be a mix of existing MATL and Mathematica solutions. Performs Singular Value Decomposition on pairwise differences of the rows, and counts nonzero eigenvalues in the result of SVD. Since APL does not have symbolic computation, we use "significantly different from zero" test instead.

### How it works

```
≢⍸1≠1+2⊃8415⌶2-⌿⎕
             2-⌿⎕  ⍝ Pairwise row differences of the input
      2⊃8415⌶      ⍝ The second matrix (diagonal matrix of eigenvalues) in SVD
  1≠1+             ⍝ Check if each number is significantly different from zero
≢⍸                 ⍝ Count ones

```
> 2 votes

# Answer
# Julia 0.7, 18 bytes

```
m->rank(m.-m[:,1])

```

Try it online!

Analogous approach in R is slightly longer (3 bytes saved by Giuseppe):

# , ~~27~~ 24 bytes

```
function(m)qr(m-m[,1])$r

```

Try it online!
> 2 votes

# Answer
# JavaScript (ES6), 187 bytes

There's probably a much shorter way. This is using the matrix rank method.

```
m=>m[m=m.map(r=>r.map((v,i)=>v-m[0][i])),n=0].map((_,i)=>(R=m.find((r,k)=>r[i]&&r[j=~k]^(r[j]=1)))&&m.map(r=>++j*r[i]&&R.map((v,k)=>r[k]-=k>i&&v*r[i]),n++,R=R.map((v,k)=>k>i?v/R[i]:v)))|n

```

Try it online!
> 2 votes

---
Tags: code-golf, math, matrix, linear-algebra
---


title: Tents and Trees feasibility

text:
# Question
Title: Tents and Trees feasibility
Sequel to Verify Tents and Trees solution.

## Background

**Tents and Trees** (try here) is a puzzle played on a square (or rectangular) grid, where the objective is to place tents horizontally or vertically adjacent to each of the trees, so that no two tents touch each other in 8 directions (horizontally, vertically, and diagonally) and the number of tents on each row/column matches the given clues.

### Example puzzle and solution

In these examples, trees are `T` and tents are `A`.

```
Puzzle
  2 0 2 0 2 1
2 . T . T . .
1 . . . . T .
1 T . T . . .
2 . . . . . T
1 T . . . . .
0 . . . . . .

Solution
  2 0 2 0 2 1
2 . T A T A .
1 A . . . T .
1 T . T . A .
2 A . A . . T
1 T . . . . A
0 . . . . . .

```

## Challenge

Given a grid with some trees, determine whether it is possible to place tents next to each of the trees so that they don't touch each other in 8 directions. Ignore the number clues in this challenge.

You may take the input in any reasonable way to represent a matrix containing two distinct values to represent a tree and an empty space respectively.

You can choose to follow your language's convention of truthy/falsy, or use two distinct values for true/false respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

This uses the same notation as the above example; `T` for trees and `.` for empty spaces.

### Truthy

```
. . .
. . .
. . . (empty board)

T .

. T .
. . T

. .
T T
. .

. T .
T . T
. T .

. . .
T T .
. T T
. . .

. T . .
. . . T
T T . .
. . . .

. T . . . .
. . . . . .
. . T . . T
. T . T . .
T . T . . .
. T . . T .

```

### Falsy

```
(No space to place a tent)
T

T . T

T . T
. T .

. . . .
. T T T
T . . .

. T .
T T .
. T .

T . T
. . .
. T .

T . . . .
. . T . .
. T . T .
T . T . .
. T . . .

. . . . .
. T . . .
. T T . .
. . T T .
. . . . .

```

# Answer
# Python 3.8 (pre-release), ~~253~~ 244 bytes

```
from itertools import*
f=lambda b,h,w:all(set(t:=[i%w+i//w*1jfor i,e in enumerate(b)if e])&set(s:=[*map(sum,zip(t,T))])or~any(abs(a-b)<2for a,b in combinations(s,2))+all(h>a.imag>-1<a.real<w for a in s)for T in product(*[[1,1j,-1,-1j]]*sum(b)))

```

Try it online!

*-6 bytes thanks to @user202729 (chain comparisons)*

*-3 bytes thanks to @ovs (`1jfor`; `…or a+1^b``…or~a+b` for "implies" boolean operator)*

```
# Itertools for combinations and product
from itertools import*
f=lambda b,h,w: all(
    # Test if a given set of tent position deltas works:
    # Positions are complex numbers: real part increasing to the right, imaginary part increasing down
    # (De Morgan shortened, so many expressions negated)
        # No tree is on a tent:
            # t:=Tree positions (1s)
            set(t:=[i%w+i//w*1j for i,e in enumerate(b)if e])
            # s:=Tent positions as sum of tree positions and deltas
            & set(s:=[*map(sum,zip(t,T))])
        # and difference between all distinct pairs oftrees is at least 2:
            or any(abs(a-b)<2for a,b in combinations(s,2))
        # and all trees are within rectangular boundary
            # (Using Python 2's quirky complex floordiv doesn't work since those return complex nums,
            # which don't have a total order.
            # Plus Python 38 has saves so much here; using 2 would be a waste anyway)
            >= all(h > a.imag > -1 < a.real < w for a in s)
    # For each possible delta (four directions, distance 1)
    # sum(b) is the number of tents since each tent contributes 1
    for T in product(*[[1,1j,-1,-1j]]*sum(b))
)

```
> 5 votes

# Answer
# Charcoal, 82 bytes

```
ＷＳ⊞υι≔⟦⟦⟧⟧θＦＬυＦ⌕Ａ§υιT«≔⟦⟧ηＦθ«υＦλ«Ｊ§μ⁰§μ¹A»Ｆ⁴«ＪκιＭ✳⊗μ¿›⁼.ＫＫ№ＫＭA⊞η⁺λ⟦⟦ⅈⅉ⟧⟧»⎚»≔ηθ»ＩＬθ

```

Try it online! Link is to verbose version of code. Takes input as newline-terminated strings and outputs the number of solutions. Explanation:

```
ＷＳ⊞υι

```

Read in the grid.

```
≔⟦⟦⟧⟧θ

```

Start with 1 solution for 0 tents.

```
ＦＬυＦ⌕Ａ§υιT«

```

Loop over the positions of the trees.

```
≔⟦⟧η

```

No tent positions for this tree found so far.

```
Ｆθ«

```

Loop over the tent positions for the previous trees.

```
υ

```

Print the grid.

```
Ｆλ«Ｊ§μ⁰§μ¹A»

```

Print the tents for this partial solution.

```
Ｆ⁴«

```

Check the four orthogonal directions.

```
ＪκιＭ✳⊗μ

```

Move to the relevant adjacent square.

```
¿›⁼.ＫＫ№ＫＭA

```

If this square is empty and is not bordered by a tent, ...

```
⊞η⁺λ⟦⟦ⅈⅉ⟧⟧

```

... then append its position to the previous partial solution and add it to the list of new partial solution.

```
»⎚

```

Clear the canvas after testing this tree.

```
»≔ηθ

```

Save the new solutions as the current solutions.

```
»ＩＬθ

```

Print the final number of solutions.
> 4 votes

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


title: Counting painted sides of cubic shapes

text:
# Question
Title: Counting painted sides of cubic shapes
Sandbox

Many of us have seen math problems where a shape made of unit cubes is dipped in paint, and the answer is the number of painted sides. We'll generalize that problem in this challenge.

# Input

A 3-dimensional matrix of 0s and 1s.

# Output

A non-negative integer

# Challenge

Given a n by m by k matrix of 0s and 1s, we can view the matrix as a 3D shape by considering a n by m by k rectangular prism broken up into n * m * k unit cubes, and the unit cubes corresponding to the 0 values in the matrix are removed.

For example, the matrix \[\[\[1,0\],\[0,0\]\],\[\[1,1\],\[0,1\]\]\] represents the shape

Given such a shape, the challenge is to output the number of painted sides on the shape if the whole shape is dunked in paint.

# Test Cases

```
[[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,0,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]]] -> 54

[[[1,0],[0,0]],[[1,1],[0,1]]] -> 18

[[[1]],[[0]],[[1]]] -> 12

[[[1,1,1,1,1,1],[1,1,1,1,1,1],[1,1,1,1,1,1],[1,1,1,1,1,1]],[[1,1,1,1,1,1],[1,0,0,0,0,1],[1,0,0,0,0,1],[1,1,1,1,1,1]],[[1,1,1,1,1,1],[1,0,0,0,0,1],[1,0,0,0,0,1],[1,1,1,1,1,1]],[[1,1,1,1,1,1],[1,0,1,1,0,1],[1,0,1,1,0,1],[1,1,1,1,1,1]],[[1,1,1,1,1,1],[1,0,1,1,0,1],[1,0,0,1,0,1],[1,1,1,1,1,1]],[[1,1,1,1,1,1],[1,1,1,1,1,1],[1,1,1,1,1,1],[1,1,1,1,1,1]]] -> 168

[[[0,0,0],[0,1,0],[0,0,0]],[[0,1,0],[1,0,1],[0,1,0]],[[0,0,0],[0,1,0],[0,0,0]]] -> 30

[[[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]],[[1,1,1,1,1],[1,0,0,0,1],[1,0,0,0,1],[1,0,0,0,1],[1,1,1,1,1]],[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]],[[1,1,1,1,1],[1,0,0,0,1],[1,0,0,0,1],[1,0,0,0,1],[1,1,1,1,1]],[[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]] -> 150

[[[1,1,0,1,1],[1,1,0,1,1],[1,1,0,1,1]],[[1,1,0,1,1],[1,1,0,1,1],[1,1,0,1,1]],[[1,1,0,1,1],[1,1,0,1,1],[1,1,0,1,1]],[[1,1,0,1,1],[1,1,0,1,1],[1,1,0,1,1]]] -> 104

[[[0,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,0,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]]] -> 54

```

# Answer
# APL (Dyalog Unicode), ~~55~~ 48 bytes

```
≢⍸↑2≠/¨⊢∘g\3⍴⊂2=2(g⊣(⌈∧⊢)/,)⍣6⍣≡(1,g←⍉⍤2⍉∘⌽)⍣6~⎕

```

Try it online!

-7 bytes thanks to @ngn.

Improvements:

* `2 3 1⍉``⍉⍤2⍉`: Replace "cycle the axes once" with "swap 1st and 3rd axes, then 2nd and 3rd"
* `{⍵(g⍵)(g g⍵)}``⊢∘g\3⍴⊂`: A scan that ignores the left arg and applies `g` to the right arg, so it works like this:

```
3⍴⊂x gives (x x x)
⊢∘g\3⍴⊂x gives (x)(x ⊢∘g x)(x ⊢∘g x ⊢∘g x)
which is the same as (x)(g x)(g g x) because:
  x ⊢∘g x
→ x ⊢ g x
→ x ⊢ (g x)
→ g x

```

---

# APL (Dyalog Unicode), 55 bytes

```
{≢⍸↑2≠/¨⍵(g⍵)(g g⍵)}2=2(g⊣(⌈∧⊢)/,)⍣6⍣≡(1,g←2 3 1⍉⌽)⍣6~⎕

```

Try it online!

A full program that takes a 3D array. Uses the flood fill already used here. Another key idea is `g←2 3 1⍉⌽`, which effectively cycles through all six sides when applied with `⍣6` (repeat six times).

### How it works

```
{≢⍸↑2≠/¨⍵(g⍵)(g g⍵)}2=2(g⊣(⌈∧⊢)/,)⍣6⍣≡(1,g←2 3 1⍉⌽)⍣6~⎕

~⎕                ⍝ Logical negation of the input
(1,g←2 3 1⍉⌽)⍣6   ⍝ Pad with a layer of ones on all six sides
2(g⊣(⌈∧⊢)/,)⍣6⍣≡  ⍝ Flood fill from the outside, changing 1s to 2s:
2(        ,)      ⍝   Prepend 2 on the last axis
   ⊣(⌈∧⊢)/        ⍝   Pairwise lcm(max(x,y),y) over the last axis
                  ⍝   Effectively, propagate 2 to an adjacent 1 on the right
  g               ⍝   Cycle the orientation once
            ⍣6⍣≡  ⍝   Repeat 6 times until the flood fill is complete
2=                ⍝ Map 2s to 1s, and anything else to 0s
{⍵(g⍵)(g g⍵)}     ⍝ Construct 3 arrays so that each axis becomes the last axis
2≠/¨              ⍝ Extract faces (where 0 and 1 are adjacent) for each array
≢⍸↑               ⍝ Count ones in all arrays

```
> 6 votes

# Answer
# Wolfram Language (Mathematica), ~~103~~ 102 bytes

```
Count[x=ImageData@FillingTransform@Image3D@#~ArrayPad~1;x~Differences~#&/@{1,{0,1},{0,0,1}},1.|-1.,4]&

```

Try it online!

To use `FillingTransform` (replace all the inner `0` with `1`), I have to convert the data to `Image3D` and convert it back. The rest is just to count the number of nonzero consecutive differences etc.
> 5 votes

# Answer
# Python 2, 493 bytes

```
A=lambda*z:0<sum(abs(a-b)for a,b in zip(*z))<2
R=lambda c:reduce(lambda a,b:a|b,c)
def C(c,d,h,w):
 a=[[{(i/w/h,i/w%h,i%w)}for i in range(d*h*w)if c[i]-v]for v in[1,0]]
 for r in a:
	i=0
	for j in range(len(r)**2):i=j/len(r);c=[[f for f in r[i:]if any(A(j,k)for k in f for j in r[i])^j]for j in[0,1]];r[i:]=(c[0]and[R(c[0])])+c[1]
 a[0]=[s for s in a[0]if all(0<e[i]<[d,h,w][i]-1for i in[0,1,2]for e in s)]
 p,q=[sum(6-sum(A(x,y)for x in r)for y in r)for r in[k and R(k)for k in a]]
 print q-p

```

Try it online!

Takes input as a flattened array along with depth, height, and width.

### How?

1. Find 6-connected components of `0`s and of `1`s
2. Remove the components of `0`s which contain a `0` on the outer edge
3. Take 6 times the number of `1`s minus the number of `1`s that border each other to get the number of `1`s that are exposed to any `0`. This includes `0`s on the inside (internal `0`s / air pockets), so:
4. Subtract (6 times the number of internal `0`s minus the number of internal `0`s that border each other) to get the number of internal `0`s that are exposed to any `1`. This subtracts all of the faces on the inside.
5. Done!

```
# Are the arguments adjacent via 6-connectivity?
A=lambda *z:0<sum(abs(a-b)for a,b in zip(*z))<2

R=lambda c:reduce(lambda a,b:a|b,c)

def C(c,d,h,w):
    a=[
        [
            {(i/w/h,i/w%h,i%w)}
            for i in range(d*h*w)
            if c[i]-v
        ]
        for v in[1,0]

    ]
    # a[0]: set of coordinates of all 0s
    # a[1]: set of coordinates of all 1s
    # Find connected components:
    for r in a:
        i=0
        for j in range(len(r)**2):
            # for each index i
            i=j/len(r);
            # do len(r) passes:
            # c[0]: all components with index > i+1 that are adjacent to component i
            # c[1]: all components with index > i+1 that are not adjacent to component i
            c=[
                [f for f in r[i:]if any(A(j,k)for k in f for j in r[i])^j]
                for j in[0,1]
            ];
            # Replace components i and higher with:
            r[i:]=(
                # If c[0] is nonempty, then the union of c[0]
                c[0]and[R(c[0])]
            )+c[1] # append c[1]
    # a[0]: set of connected components of 0s
    # a[1]: set of connected components of 1s
    # Remove all of a[0] that border the outside:
    a[0]=[
        # Filter for:
        s for s in a[0]if
        all(
            # The coordinates along each axis are between 1 and that axis's length minus 2, inclusive
            0<e[i]<[d,h,w][i]-1
            for i in[0,1,2]
            # For all points
            for e in s
        )
    ]
    # a[0] now: set of connected components of 0s that do not border the outside
    p,q=[
        sum(
            6- # cube contributes 6 sides
            sum(A(x,y)for x in r) # minus the number of adjacent cells
            for y in r # for each cube
        )
        for r in # for each connected component
        [k and R(k)for k in a]
    ]
    print q-p

```
> 5 votes

# Answer
# Python 3 with `NumPy`, ~~177~~ 161 bytes

*-16 bytes thanks to @fireflame241 !*

```
f=lambda l:g(pad(pad(l,1)-2,1)+2,1,1,1)
def g(l,*i):l[i]+=2;return l[i]%2if l[i]-2else sum(g(l,*(t*d+i))for d in eye(3,3,0,int)for t in[1,-1])
from numpy import*

```

Try it online!

### Big idea:

DFS over all outer empty cells. Every time an outer empty cell touches a cube, adds 1 to the counter.

### Explanation:

* `0` denotes air (empty cell), odd positive numbers denote walls, and even positive numbers denotes paint.
* First, pad everything with a layer of 0 (air), so all outer air cells are connected: `pad(l,1)`
* Then, pad everything with a layer of 2 (paint), which acts as a barrier to prevent out of bound search later. To do this, subtracts `2` from all cells, pad everything with 0, then adds 2 back: `pad(arr - 2, 1) + 2`
* Start DFS at `l[1,1,1]`, which is guaranteed to be an outer air cell.
* At each DFS step (function `g`):
    + If current cell is paint, stops recursion.
    + If current cell is wall, adds 1 to counter, and stops recursions.
    + If current cell is air, changes it to paint, and recurs on the 6 neighbors.
> 5 votes

# Answer
# MATL, ~~37~~ ~~36~~ 35 bytes

```
e7BYa~6&1ZIt1)-tz6*yZybfX[hhtZPq~z-

```

Input is a row vector of zeros and ones, and a row vector of three integers with dimensions from inner nesting level to outer.

Try it online! Or verify all test cases.

### Explanation

The code initially adds a frame of empty space around the 3D array. Any cell that is not space connected to that frame is filled. This has the effect of filling any holes in the original 3D shape.

The number of painted faces is the number of cubes in that filled shape times 6, minus the number of cubes that touch some other cube (two cubes touching means a face is not accessible to the paint; pairs are counted twice).

To detect which cubes touch, all pairwise distances between the cubes are computed, and two cubes touch if their distance is 1.

```
e      % Implicit inputs: vector or zeros and ones, and 3-element vector specifying
       % size along each dimension. Reshape the first according to the second. This
       % produces the 3D array
7BYa   % Pad the 3D array with a frame of zeros along the three dimensions
~      % Negate. This changes 0 to 1 and vice versa (*)
6&1ZI  % Label connected components using 6-connectivity in 3D (so no diagonals)
       % This considers the zeros in (*) as background, and nonzeros as foreground.
       % The foreground cells are labelled with a different integer according to
       % indicate the component. There will be an outer component that will include
       % the added frame and any space surrounding the shape, and potentially more
       % components if the shape has inner holes
t1)-   % Duplicate Subtract the upper-right-front entry from each entry. This
       % makes the outer connected component (originally the space surrounding the
       %  shape) equal to 0, and other components or brackground become nonzero.
       % So now the shape plus any inner holes in it are nonzero (**)
tz6*   % Duplicate. Number of nonzeros times 6. This is the maximum number of faces
       % of unit cubes that could be painted (some won't actually get pointed,
       % namely any face that touches any other face) (***)
yZy    % Duplicate from below: pushes a copy of (**). Get its size as a length-3
       %  vector
bf     % Bubble up: moves the original copy of (**) to the top. Push linear indices
       % of its nonzero entries. Linear indices run down, then accros (left to
       % right), then front to bottom
X[     % Convert linear indices to a set of three indices assuming an array of the
       % specified size. Gives three column vectors
hh     % Concatenate veftically twice. This gives a 3-column matrix where each row
       % contains the coordinates of a cube in (**)
tZP    % Duplicate. Pairwise distances between rows of the 3-column matrix and
       % those of its copy
q~     % Subtract 1, negate. This gives 1 for distances equal to 1, and 0 otherwise
z      % Number of nonzeros
-      % Subtract from (***). Implicit display

```
> 4 votes

# Answer
# JavaScript (ES6),  ~~295~~  291 bytes

```
a=>a.map((s,z)=>s.map((r,y)=>r.map((v,x)=>v|!(g=(x,y,z,R=a[z]&&a[z][y])=>R&&1/R[x]?R[x]?0:R[x]++|[0,1,2,3,4,5].some(n=>(i=n&1||-1,g(n&6?x:x+i,n&2?y+i:y,n&4?z+i:z)))|--R[x]:1)(x,y,z)))).map((s,z,a)=>s.map((r,y)=>r.map((v,x)=>n+=v&&!r[x+1]+!((q=s[y+1])&&q[x])+!((q=a[z+1])&&q[y][x]))),n=0)|n*2

```

Try it online!

NB: This is a bit too slow to reliably complete the 6th test case on TIO.
> 3 votes

# Answer
# 05AB1E, 75 bytes

```
-.øε0δ.ø©}ε®Ù.ø}D€øDø€ø««εÁÁεN3@iD0ÚPi1V}YiγÁεN2@id}}À˜}}}ÀÀ2V}€`€ü2€`ʒË≠}g

```

Dang, this was hard in 05AB1E.. But it works now. 05AB1E and matrices are already a bad combination, so add an additional dimension and it's a complete disaster, haha..

Try it online or verify all test cases.

**Explanation:**

Step 1: Surround the entire input 3D matrix with a layers of empty cells (0s) in each dimension:

```
-                    # Transform all values into 0s by subtracting the values in the
                     # (implicit) input 3D-matrix by the values in the (implicit) input
 .ø                  # Surround the (implicit) input-matrix with this 2D-matrix of 0s as
                     # both leading and trailing item
   ε                 # Map each 2D matrix of the 3D matrix to:
     δ               #  For each row of the 2D matrix:
    0 .ø             #   Surround it with a leading and trailing 0
        ©            #  Store the modified 2D matrix in variable `®` (without popping)
   }ε                # After the map: map over each 2D matrix in the 3D matrix again:
     ®Ù              #  Uniquify the last 2D matrix that was stored in `®`,
                     #  so we'll have a row of 0s wrapped inside a list
       .ø            #  Surround each 2D matrix with this row of 0s
    }                # And close this map as well

```

(Note: the z-axis actually contains two surrounding empty cells instead of one, but this doesn't really matter for the rest of the program.)

Step 2: Get a list of all strings of cells along the x, y, and z axes respectively:

```
D                    # Duplicate the current 3D-matrix, which of itself already contains
                     # all strings of cells along the x-axis
 €                   # Map each 2D matrix of the 3D matrix to:
  ø                  #  Zip/transpose; swapping rows/columns
D                    # Duplicate as well, which are the strings of cells along the y-axis
 ø                   # Zip/transpose; swapping rows/columns of this 3D matrix
  €                  # Map each 2D matrix of the 3D matrix to:
   ø                 #  Zip/transpose; swapping rows/columns
                     # And we now also have the strings of cells along the z-axis
««                   # Merge all three lists together

```

This will result in a 3D matrix with three inner 2D matrices (one for each dimension), which are each lists of strings of cells.

Step 3: Fill all inner bubbles with 1s:

```
ε                    # Map each 2D matrix of the 3D matrix to:
 ÁÁ                  #  Rotate the rows of the matrix twice towards the left
   ε                 #  Map each string of cells in the current 2D matrix to:
    N3@i             #   If the 0-based index is >= 3:
        D            #    Create a copy of the string of cells
         0Ú          #    Remove all leading and trailing empty cells
           Pi  }     #    If there are now only filled cells left:
             1V      #     Set flag `Y` to 1
         Yi          #    If flag `Y` is 1:
           γ         #     Split the string of cells into groups of equal adjacent values
            Á        #     Rotate these groups once towards the left
             ε       #     Map each group to:
              N2@i } #      If the 0-based index is >= 2:
                  d  #       Fill all empty cells (1 remains 1, 0 becomes 1)
             }À      #     After the map: rotate the groups back to the right
               ˜     #     And flatten it to a single string of cells again
   }}}ÀÀ             #  After the map: rotate the rows twice back towards the right
        2V           #  Reset flag `Y` back to 2 for the next iteration
}                    # Close the map

```

We basically skip the first and last strings of cells, since we know those are surrounding layers of empty cells we added in step 1. In addition, we also don't want to modify the second and second to last strings of cells, since those are the outer layers of the initial input 3D matrix. We do however want to start checking from the second string of cells onward until we find a solid string of filled cells (minus the surrounding empty cells). For all strings of cells after we've encountered such a solid string of filled cells, we want to transform them into solid strings of filled cells as well (minus the surrounding empty cells) to fill the bubble.

Step 4: Now that we've filled the bubbles, we want to get a list of all pairs of cells:

```
€`                   # Flatten the 3D matrix containing the three list of strings of
                     # cells one level down to a single list of strings of cells
  €                  # Map each string of cells to:
   ü2                #  Create overlapping pairs of cells
     €`              # And flatten this list of list of pairs one level down as well to a
                     # list of pairs

```

Step 5: Filter out any pairs of two empty or two filled cells, so we only have pairs containing one of each:

```
ʒ                    # Filter this list of paired cells by:
 Ë≠                  #  Check that both values in the pair are NOT the same
}                    # Close the filter

```

Step 6: Get the amount of pairs left containing both a filled and empty cell, and output it as result:

```
g                    # Pop and push the length of the filtered list
                     # (after which it is output implicitly as result)

```

Try it online with each of these steps output separately.
> 2 votes

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


# Question
Title: Which languages are optimal for problems that require "reading" input while also writing to it like a stack
When encountering a problem whose input is meant to be read sequentially, *but you may also want to push back onto the input like a stack*, which languages have the optimal boilerplates for doing so, and how?

For example, from Create a Boolean Calculator, we have a string like:

```
1AND0OR1XOR1

```

We want to "pop" 5 chars `1AND0`, compute it to be `0`, then "push" it back to form:

```
0OR1XOR1

```

Then, repeat until there's only 1 char left. In this case:

```
0

```

It's trivial to write `while` loops and such, but this seems common enough in codegolf problems that there must be canonical forms. I wasn't able to find a question specifically about this setup though, and going through each question by language was difficult.

# Answer
The approach you're asking seems like reduce/left fold in general. Many languages have this, such as Python (`reduce(f,seq)` or `functools.reduce(f,seq)`), APL (`f⍨/⌽seq`), Jelly (`f/seq`), and Haskell (`foldl f start seq`).

As a Python example, let's assume we already have the input parsed as a list `seq=[1, 'AND', 0, 'OR', 1, 'XOR', 1]`. Then `reduce(f,seq)` is equivalent to

```
f(f(f(f(f(f(1, 'AND'), 0), 'OR'), 1), 'XOR'), 1)

```

The trouble here is that we need to take 3 arguments at a time. A way this could be done is by grouping most of the sequence into pairs `seq2=[1, ['AND',0], ['OR',1], ['XOR',1]]`, so `reduce(f,seq)` would be equivalent to

```
f(f(f(1, ['AND',0]), ['OR',1]), ['XOR',1])

```

This could work well in Jelly because it has a builtin `s` that could help split into pairs (output looks funny strings are internally lists of chars).

However, a loop-based approach would work better in Python by assigning to a slice of an array:

```
seq=[1, 'AND', 0, 'OR', 1, 'XOR', 1]
while len(seq)>1:
  seq[1:3] = [f(*seq[1:3])]
print(seq[0])

```

This would output `f(f(f(1, 'AND', 0), 'OR', 1), 'XOR', 1)`.

As @AdHocGarfHunter notes in the comments, recursion is a good idea too:

```
# (ungolfed)
def r(s):
  if len(s)>1:
    return r(f(*s[:3]) + s[3:])
  else:
    return s[0]

```

APL has little boilerplate for this: `{1=⍴⍵:⊃⍵⋄∇(3↓⍵),f3↑⍵}` ( is the recursion). Jelly does too, with `1` byte recursion.
> 3 votes

---
Tags: code-golf, tips
---


title: Fibonacci’s sexagesimals

text:
# Question
Title: Fibonacci’s sexagesimals
Leonardo da Pisano *a.k.a* Fibonacci was instrumental in bringing the Hindu-Arabic numeral system into Europe. Before that, mathematicians there worked in base sixty with Roman numerals.

For example, the square root of two might be approximated as: *one and twenty-four parts of sixty and fifty-one parts of three-thousand-six-hundred*, and written as: *i xxiv li*, with the scaling determined by context. At the time, “nothingness” was known (*i.e.* zero), but had no standard representation in this number system.

Had Fibonacci ignored these new-fangled decimal digits he encountered during his travels, he surely would have addressed the deficiencies in the current system. This improved system we'll call *Fibonacci’s sexagesimals*.

Your task is to write a program, function or code snippet which takes a floating point number in ASCII or binary format and outputs in base sixty Roman numerals. The input can be file, console, command line or function argument and output can be file or console, whichever is easiest.

The output can be upper or lower case, and must include these improvements:

* use *n* or *N* to indicate *null* meaning a place has no value, *i.e.* “zero” (a problem with the system)
* use *e* or *E* to indicate *et* corresponding to the sexagesimal point (another problem with the system)
* use a middle dot · or an asterisk * to separate groups of Roman numerals (yet another problem with the system)

Assume the input will be floating point with mantissa not greater than *lix·lix·lix·lix·lix*. Fractions less than *n·e·n·n·n·n·i* can be ignored. So, provided the input has these restrictions, at most ten groups of Roman numerals with one *e* can be outputted.

Numbers less than *i* must have a leading *n·e* to ensure the context is clear.

Some examples: `input`*output*

* `0`*n*
* `1`*i*
* `60`*i·n*
* `0.1`*n·e·vi*
* `3600`*i·n·n*
* `10.5`*x·e·xxx*
* `16777215`*i·xvii·xl·xx·xv*
* `3.1415926536`*iii·e·viii·xxix·xliv·n·xlvii*

The output must avoid unnecessary leading  in the mantissa part, isolated *e*, or trailing *·n* in the fractional part of the output. So for example, *n·n·n·n·i*, *i·e*, and *i·e·n·n·n·n·n* are incorrect outputs for an input of `1`.

Differences of plus or minus *n·e·n·n·n·n·i* in the output are within tolerances and acceptable.

The input is any legal floating point in the language of your choice, so can include positive or negative exponents as long as the input doesn't fall outside the range specified above.

And finally, Roman numeral built-ins **are** allowed!

# Answer
# Python 3, ~~323~~ ~~319~~ 320 bytes

This answer implements Fibonacci's sexagesimals with the delimiter `*` and without regard for Kolmogorov complexity in the lists of Roman numerals (for now, at least). Attempts were made to join the `while` and `for` loop under which the Roman numerals are generated under one loop, but those attempts have not yet met with success. Any golfing tips and suggestions are welcome and appreciated.

**Edit:** Bug fixing and golfing.

**Edit:** More bug fixing.

```
def f(x):
 v=divmod;f=x%1;n=int(x);d=",I,II,III,IV,V,VI,VII,VIII,IX".split(",");t=",X,XX,XXX,XL,L".split(",");z=["N"];a=f>0;s=z*0**n+["E"]*a
 while n:n,m=v(n,60);j,k=v(m,10);s=[z,[t[j]+d[k]]][m>0]+s
 for i in range(5*a):m,f=v(f*60,1);j,k=v(int(m),10);s+=[z,[t[j]+d[k]]][m>0]
 while s[-1:]==z*a:s.pop()
 return"*".join(s)

```

**Ungolfed:**

```
def f(x):
    integ = int(x)
    frac = x % 1
    units=",I,II,III,IV,V,VI,VII,VIII,IX".split(",")
    tens=",X,XX,XXX,XL,L".split(",")
    zero = ["N"]
    output = []
    a = frac != 0
    if integ == 0:
        output += z
    if a:
        output += ["E"]
    while integ > 0:
        integ, digit = divmod(integ, 60)
        j, k = divmod(int(digit), 10)
        if digit:
            output += [tens[j], units[k]]
        else:
            output += zero
    for i in range(5*a):
        digit, frac = divmod(frac*60, 1)
        j, k = divmod(int(digit), 10)
        if digit:
            output += [tens[j], units[k]]
        else:
            output += zero
    while output[-1:] == zero * a:
        output.pop()
    return "*".join(output)

```
> 1 votes

# Answer
# C – 584 bytes

Non-competing (obviously), but to serve as inspiration:

```
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
char*f(int z){static char r[8];char*l[]={"","I","II","III","IV","V","VI","VII","VIII","IX"},*h[]={"","X","XX","XXX","XL","L"};if(!z)return"N";sprintf(r,"%s%s",h[z/10],l[z%10]);return r;}int main(int c,char**v){char*s="";int i,j,z[10],k=60;long x;double d,y;y=modf(atof(v[1]),&d);x=d;for(i=4;i>=0;i--){z[i]=x%k;x/=k;}for(i=5;i<=9;i++){z[i]=(y*=k);y-=z[i];}for(i=0;!z[i]&&i<4;i++);for(;i<5;i++){printf("%s%s",s,f(z[i]));s="*";}for(j=9;!z[j]&&j>=i;j--);if(i<=j)printf("*E");for(;i<=j;i++)printf("*%s",f(z[i]));printf("\n");return 0;}

```

Save as `fs.c`, build with `gcc -o fs fs.c -lm`, and run as `./fs <arg>`.

Test cases:

```
$ ./fs 0
N
$ ./fs 1
I
$ ./fs 60
I*N
$ ./fs 0.1
N*E*VI
$ ./fs 3600
I*N*N
$ ./fs 10.5
X*E*XXX
$ ./fs 16777215
I*XVII*XL*XX*XV
$ ./fs 3.1415926536
III*E*VIII*XXIX*XLIV*N*XLVII

```

Largest mantissa and fraction:

```
$ ./fs 777599999
LIX*LIX*LIX*LIX*LIX
$ ./fs 0.999999998713992
N*E*LIX*LIX*LIX*LIX*LIX

```

I'm using `double` as the working type, so the largest mantissa and fraction combined exceeds the native accuracy of that type. If I used `long double` instead it could handle it.
> 3 votes

# Answer
# APL (Dyalog Unicode), 90 bytes (using classic `⎕AV`)

```
⎕CY'dfns'
'(·E)?(·N)*·$'⎕R''∊'·',⍨¨¯5(↓,'E',↑)'N'@(0=≢¨)⊢roman'I'⍴⍨¨d↑⍨-6⌈≢d←60⊥⍣¯1⌊⎕×60*5

```

Try it online!

A full program that takes a number (actually any expression that evaluates to a single number is fine) from stdin and prints the result to stdout. Uses uppercase letters and middle dot as digit separator. The middle dot allows to shorten the regex at the end (since it doesn't need to be escaped, unlike `*`), and the middle dot *is* in the classic character set.

### How it works

```
⎕CY'dfns'  ⍝ Load the dfns library to access `roman`

⌊⎕×60*5  ⍝ Multiply input by 60^5 and floor (to do things over integers)
60⊥⍣¯1   ⍝ Convert to base 60 using as many base-60 digits as needed
d←       ⍝ Assign to d
d↑⍨-6⌈≢  ⍝ Pad with zeros to get 6 digits if there were fewer
'I'⍴⍨¨   ⍝ Convert each number to that many copies of 'I'
⊢roman   ⍝ Normalize the Roman numeral

'N'@(0=≢¨)   ⍝ Insert 'N' at zero digits (normalized result is empty)
¯5(↓,'E',↑)  ⍝ Insert 'E' at 5 places from the end
∊'·',⍨¨      ⍝ Append a center dot to each numeral and flatten

'(·E)?(·N)*·$'⎕R''  ⍝ Regex replace to remove trailing E/Ns

```
> 2 votes

# Answer
# JavaScript (Node.js), 537 531 430 bytes

*-101 bytes (**big**) thanks to **Bubbler**!*

Usage of some math (logarythms in this case, to calculate starting value for the "for" loop) and a code converting decimal numbers to roman numerals from here (w3resource). Actually, the task took me more time than I expected it to take and gave a lot of additional intuition while working with numeral systems other than the decimal one. Great one :)

Function itself is an anonymous one declared with arrow function declaration.

```
n=>{if(n==0||n==1)return"NI"[n];k="",j=-`${n-(n|0)}.`.split`.`[1].length||0;j<-5?j=-5:"";with(Math){l=m=ceil(log(n)/log(60))}for(;l>j;l--){x=n%60**l/60**(l-1)|0;x==0&&l==m?(k+="I*"):"";l==0&&j<0?(k+="E*"):"";d=`${+x}`.split``,o=" X XX XXX XL L LX LXX LXXX XC  I II III IV V VI VII VIII IX".split` `,h="",i=2;while(i--)h=(o[+d.pop()+(i*10)]||"")+h;k+=x==0?"N*":`${Array(+d.join("")+1).join("M")+h}*`;}return k.substr(0,k.length-1)}

```

Try it online!
> 1 votes

# Answer
# Haskell (~~333~~ ~~322~~ 315 bytes)

I'm not clear whether the last sexagesimal digit is supposed to be rounded when I do or whether truncation is allowed; this truncates, I think the Python3 one might too?

```
d n f 0=n;d n f x=f x
x!n=60*(x-fromInteger n)
f 0=[];f x=(\n->n:f(x!n))$floor x
l 0=[];l x=(\(d,m)->l d++[m])$divMod x 60
v=[50,40,10,9,5,4,1]
n&i|n==0=""|n>=v!!i=words"l xl x ix v iv i"!!i++(n-v!!i)&i|True=n&(i+1)
q=foldl1(\a x->a++'.':x).map(d"n"(&0))
p x=(\n->d"n"(q.l)n++d""((".e."++).q.take 5.f)(x!n))$floor x

```

(-9 bytes, thanks H.PWiz! -2 bytes by eliminating `where` for `(\->)$`, -5 more by inventing this `d` function and golfing `a++"."++x` to `a++'.':x`.)

Ungolfed:

```

-- this function gets called `d` for default
onZero :: (Eq n, Num n) => z -> (n -> z) -> n -> z
onZero def f x
 | x == 0    = def
 | otherwise = f x

-- this function gets called `f`
fracPart :: RealFrac a => a -> [Integer]
fracPart x
  | x == 0    = []
  | otherwise = n : fracPart (60 * (x - fromInteger n))
    where n = floor x

-- this function gets called `l`
leadPart :: Integral n => n -> [Integer]
leadPart x
  | x == 0    = []
  | otherwise = leadPart div ++ [ mod ]
    where (div, mod) = x `divMod` 60

-- these get called `v`
romanValues :: [Integer]
romanValues = [50, 40, 10, 9, 5, 4, 1]

-- these get inlined with `words`, and correspond to the values above
romanLetters :: [String]
romanLetters = ["l", "xl", "x", "ix", "v", "iv", "i"]

-- this becomes (&)
romanNumeralLoop :: Integer -> Int -> String
romanNumeralLoop n i
 | n == 0                  = ""
 | n >= (romanValues !! i) = (romanLetters !! i) ++ romanNumeralLoop (n - (romanValues !! i)) i
 | otherwise               = romanNumeralLoop n (i + 1)

-- this becomes `q`
concatRomanWithDots :: [Integer] -> String
concatRomanWithDots numbers = concatWithDots (map toRoman numbers)
  where
    toRoman = onZero "n" (\x -> romanNumeralLoop x 0)
    concatWithDots = foldl1 concatDot
    concatDot acc item = acc ++ "." ++ item

-- this becomes `p`
solve x = onZero "n" elseRomanizeLeadPart n ++ onZero "" elseRomanizeFracPart f
  where
    n = floor x
    f = 60 * (x - fromInteger n)
    elseRomanizeLeadPart l = concatRomanWithDots (leadPart l)
    elseRomanizeFracPart f = ".e." ++ concatRomanWithDots (take 5 (fracPart f))

```

The method of converting integers to roman numerals was stolen shamelessly from Thomas Ahle on StackOverflow and just golfed a little.
> 0 votes

---
Tags: code-golf, math, base-conversion, roman-numerals
---


title: Solve the dress problem

text:
# Question
Title: Solve the dress problem
# Background

Peter's Father, the Teacher of a dance-club, asks Peter a question:
Given are two natural numbers (\\$\mathbb{N}\\$ \\$x\\$ and \\$y\\$).

\\$x\\$ is the number of the garment types (e.g. shorts, shirts\\$\dots\\$) we have

\\$y\\$ is number of colors (e.g. green, blue, \\$\dots\\$) of each garment we have.

In the dance class, every one should be in a unique dress.

# Example:

But:

Now tell me: For every given \\$x\\$ and \\$y\\$, what is the maximum number of people who an visit our class?

Can you help Peter?

# Challenge

The input should be two natural numbers (\\$\forall x,y\in\mathbb{N}\\$) separated by a comma`,`. The input can also be your languages equivalent for a list which has two elements.

The Output should be an Integer, the maximum number of people who can visit the dance-class.

# Test cases

```
In:1,0
Out:0

In:0,0
Out:0

In:[2,2]
Out:4

In:3,2
Out:9

```

# Rules

* This is so the shortest code wins

# Answer
> 2 votes
# Perl 5 `-p`, 20 bytes

```
/,/;$_=$`*$'&&$'**$`

```

Try it online!

# Answer
> 2 votes
Both answers don't work for 0-inputs, I'm waiting for it to be clarified.

# Husk, 2 bytes

Takes input as `colors, garment types`

Try it online!

## Explanation

```
Inputs: 2, 3

 π  (x, y) 1..x 's cartesian power by y.
           [1, 2] -> [[1,1],[1,2],[2,1],[1,3],[2,2],[3,1],[2,3],[3,2],[3,3]]
L   (x) Length of x.
           -> 9
    Implicit output

```

# 05AB1E, 4 bytes

Takes input as the specified format.

```
и<²β

```

Try it online!

## Explanation

Example inputs: 2, 3

и    Repeat: ["3", "3"]
 <   Decrement: [2, 2]
  ²β From base (second input): 9
```

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


title: Make a Ramanujan magic square

text:
# Question
Title: Make a Ramanujan magic square
# Background

As you maybe know Ramanujan made this magic square by \\$4x4\\$ Matrix:

This works like all magic squares.
But the special thing in this square is that his birthdate is hidden in the first row, the 22\\$^{nd}\\$ Dec 1887.

# Challenge

****Can you make one for your birthdate?****

# Input

The User will give Input in this format: DD/MM/yyYY.
The input can't be a list of 3 numbers(\[DD,MM,yyYY\]).

Here is the formula to make a square for your birthdate

# Output

The output should be a "unnormal" or special square, in your languages equivalent for a list. Note: These are not really magic squares, because as Abigail mentioned tin some dates there are duplicate numbers, but every row, column and diagonal there will e the same number of sum

# Test cases:

```
In: 20/08/2000
Out:
[20, 8, 20, 0]
[1, 19, 5, 23]
[6, 22, 2, 18]
[21, -1, 21, 7]

In: 10/01/2020
Out:
[10, 1, 20, 20]
[21, 19, -2, 13]
[-1, 12, 22, 18]
[21, 19, 11, 0]

In: 10/05/2020
Out:
[10, 5, 20, 20]
[21, 19, 2, 13]
[3, 12, 22, 18]
[21, 19, 11, 4]

In: 00/00/0000
Out:
[0, 0, 0, 0]
[1, -1, -3, 3]
[-2, 2, 2, -2]
[1, -1, 1, -1]

```

# Rules

This is , so the shortest code wins

# Answer
> 6 votes
# JavaScript (Node.js),  ~~88~~  84 bytes

*Saved 4 bytes thanks to @NahuelFouilleul*

```
d=>`-BWe
fV?0
@/gU
Xd.A`.replace(/./g,c=>d.substr((n=Buffer(c)[0])/7-6,2)-3+n%7+' ')

```

Try it online!

### How?

Each value in the matrix is encoded as a character whose ASCII code is:

$$7k+o+42$$

where \\$k\\$ is the 0-indexed position of the variable in the input string and \\$o-3\\$ is the offset to add.

*Example:*

For `MM-2`, the position is \\$3\\$:

```
"DD/MM/yyYY"
    ^
 0123456789

```

and the offset is\\$-2\\$, leading to:

$$7\times3+(-2+3)+42=64$$

which is `'@'`.

# Answer
> 4 votes
# APL (Dyalog Unicode), 66 bytes

```
{4 4⍴(∊(⊣,-)¨3-⍨1011304⊤⍨8⍴6)+,(⊢⍪⌽∘⊖⍪⌽⍪⊖)2 2⍴10⊥⍉⍎¨4 2⍴'/'⎕R''⊢⍵}

```

Try it online!

### How?

The key insight is that the rows correspond to a single 2×2 matrix that has been mirrored vertically, horizontally, not at all, or both.

```
{4 4⍴(∊(⊣,-)¨3-⍨1011304⊤⍨8⍴6)+,(⊢⍪⌽∘⊖⍪⌽⍪⊖)2 2⍴10⊥⍉⍎¨4 2⍴'/'⎕R''⊢⍵} ⍝ Anonymous inline function
  ⍵            ⍝ Input, e.g. '22/12/1887'
  '/'⎕R''      ⍝ Replace '/' with '', giving e.g 22121887
  10⊥⍉⍎¨4 2⍴   ⍝ Reshape and execute to give vector (22,12,18,87)
  2 2⍴         ⍝ Reshape to 2×2 matrix (22 12)(18 87)
  (⊢⍪⌽∘⊖⍪⌽⍪⊖)  ⍝ Mirror the matrix in 4 ways to get the 4 rows
  ,            ⍝ Flatten to a row vector
  1011304⊤⍨8⍴6 ⍝ Base 6 encoding of 3 3 4 0 1 5 4 4
  3-⍨          ⍝ Subtract 3 from each: 0 0 1 ¯3 ¯2 2 1 1
  ∊(⊣,-)¨      ⍝ Append the negative to each and flatten: 0 0 0 0 1 ¯1 ¯3 3 ¯2 2 2 ¯2 1 ¯1 1 ¯1
  +            ⍝ Add these constants to each element
  4 4⍴         ⍝ Reshape to give a 4×4 matrix

```

# Answer
> 4 votes
# K (ngn/k), ~~53~~ 51 bytes

**Solution:**

```
{4 4#x,(3-7\5330941200)+(x:.'4 2#x^"/")@4\14962353}

```

Try it online!

**Explanation:**

Probably further golfable...

```
{4 4#x,(3-7\5330941200)+(x:.'4 2#x^"/")@4\14962353} / the solution
{                                                 } / lambda taking implicit x
                                        4\14962353  / decode 14962353 into base 4 => 3 2 1 0 1 0 3 2 2 3 0 1
                                       @            / use that to index into
                        (             )             / do all this together
                                 x^"/"              / x except (^) "/"
                             4 2#                   / reshape as 4x2 grid
                           .'                       / 'value each', convert e.g. "20" to 20
                         x:                         / save back into x
                       +                            / add to
       (              )                             / do this together
          7\5330941200                              / decode 5330941200 into base 7 => 2 4 6 0 5 1 1 5 2 4 2 4
        3-                                          / subtract from 3 => 1 -1 -3 3 -2 2 2 -2 1 -1 1 -1
     x,                                             / prepend x
 4 4#                                               / reshape into 4x4 grid

```

**Extra:**

* -1 byte with `^"/"` (except "/") instead of dropping indices 5 and 2 (`_/5 2`)
* -1 byte with `3-7\5330941200` instead of `-3+7\8510346000`

# Answer
> 3 votes
# 05AB1E, ~~27~~ ~~26~~ 24 bytes

```
þ2ôÀā+āδ-˜•ItíË€ß•.I4ô

```

-2 bytes by porting *@JonathanAllan*'s Jelly answer, so make sure to upvote him as well!

Try it online or verify all test cases.

---

**Old ~~27~~ 26 bytes approach:**

```
þ2ôÂD2ôR˜Â)•CV¤½‘àý•S4ä3-+

```

Try it online or verify all test cases.

**Explanation:**

```
þ         # Leave the digits of the (implicit) input-string: "dd/MM/YYyy" to "ddMMYYyy"
 2ô       # Split it into parts of size 2: [DD,MM,yy,YY]
À         # Rotate it once towards the left: [MM,yy,YY,DD]
 ā        # Push a list in the range [1,length] (without popping): [1,2,3,4]
  +       # Add the values at the same indices: [MM+1,yy+2,YY+3,DD+4]
ā         # Push [1,2,3,4] again
 δ        # Apply double-vectorized on these lists:
  -       #  Subtract
          # (results in: [[MM,MM-1,MM-2,MM-3],[yy+1,yy,yy-1,yy-2],[YY+2,YY+1,YY,YY-1],
          #  [DD+3,DD+2,DD+1,DD]])
   ˜      # Flatten it:
          #  [MM,MM-1,MM-2,MM-3,yy+1,yy,yy-1,yy-2,YY+2,YY+1,YY,YY-1,DD+3,DD+2,DD+1,DD]
    ā     # Push a list in the range [1,length] (without popping) again: [1,...,16]
•IZΔmλR•  # Push compressed integer 19556972234337
 .I       # Get the 19556972234337'th permutation of the [1,16] list
   è      # Index each into the list of values (modular 0-based, so 16 is the first):
          #  [DD,MM,yy,YY,YY+1,yy-1,MM+3,DD+3,MM-2,DD+2,YY+2,yy-2,yy+1,YY-1,DD+1,MM-1]
    4ô    # And split it into parts of size 4 again
          # (after which the result is output implicitly

þ2ô       # Same as above: [DD,MM,yy,YY]
Â         # Bifurcate this list (short for Duplicate & Reverse copy)
          #  [DD,MM,yy,YY] → [YY,yy,MM,DD]
 D        # Duplicate it
  2ô      # Split it into pairs
          #  [YY,yy,MM,DD] → [[YY,yy],[MM,DD]]
    R     # Reverse the pairs
          #  [[YY,yy],[MM,DD]] → [[MM,DD],[YY,yy]]
     ˜    # Flatten it back again to a quartet
          #  [[MM,DD],[YY,yy]] → [MM,DD,YY,yy]
      Â   # Bifurcate that as well
          #  [MM,DD,YY,yy] → [yy,YY,DD,MM]
       )  # And wrap all list on the stack into a list
          #  → [[DD,MM,yy,YY],[YY,yy,MM,DD],[MM,DD,YY,yy],[yy,YY,DD,MM]]
•CV¤½‘àý• # Push compressed integer 3333420615514242
 S        # Convert it to a list of digits: [3,3,3,3,4,2,0,6,1,5,5,1,4,2,4,2]
  4ä      # Split it into 4 equal-sized parts: [[3,3,3,3],[4,2,0,6],[1,5,5,1],[4,2,4,2]]
    3-    # Subtract 3 from each: [[0,0,0,0],[1,-1,-3,3],[-2,2,2,-2],[1,-1,1,-1]]
      +   # Add the values in the lists together:
          #  [[DD,MM,yy,YY],
          #   [YY+1,yy-1,MM-3,DD+3],
          #   [MM-2,DD+2,YY+2,yy-2],
          #   [yy+1,YY-1,DD+1,MM-1]]
          # (after which the result is output implicitly

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•IZΔmλR•` is `19556972234337` and `•CV¤½‘àý•` is `3333420615514242`.

# Answer
> 2 votes
# Jelly,  ~~27~~  26 bytes

```
ḟṂs2Vṙ1+J$_Ɱ4F“Œñḳ⁶.C’œ?ṁƲ

```

A monadic Link accepting the list of characters as specified which yields a list of lists of integers.

**Try it online!**

### How?

```
ḟṂs2Vṙ1+J$_Ɱ4F“Œñḳ⁶.C’œ?ṁƲ - Link: list of characters, D    e.g. "01/09/2000"
 Ṃ                         - minimum                             '/'
ḟ                          - filter discard                      "01092000"
  s2                       - split into twos                     ["01","09","20","00"]
    V                      - evaluate                            [1,9,20,0]
     ṙ1                    - rotate left 1                       [9,20,0,1]
         $                 - last two links as a monad:
        J                  -   range of length                   [1,2,3,4]
       +                   -   add                               [10,22,3,5]
           Ɱ4              - map across [1..4] with:
          _                -   subtract                          [[9,21,2,4],[8,20,1,3],[7,19,0,2],[6,18,-1,1]]
                         Ʋ - last four links as a monad - f(x):
             F             -   flatten                           [9,21,2,4,8,20,1,3,7,19,0,2,6,18,-1,1]
              “Œñḳ⁶.C’     -   base 250 integer = 19644039699318
                      œ?   -   nth permutation                   [1,9,20,0,1,19,6,4,7,3,2,18,21,-1,2,8]
                        ṁ  -   mould like (x)                    [[1,9,20,0],[1,19,6,4],[7,3,2,18],[21,-1,2,8]]

```

# Answer
> 2 votes
# perl -nl -M5.010, 106 bytes

```
/.(\d\d).(\d\d)/;$,=$";say$`,$1,$2,$';say$'+1,$2-1,$1-3,$`+3;say$1-2,$`+2,$'+2,$2-2;say$2+1,$'-1,$`+1,$1-1

```

Try it online!

## How does it work?

```
/.(\d\d).(\d\d)/;

```

This lines parses the input. It matches the `/MM/yy` part of the input, leaving `MM` in `$1` (the first capture) and `yy` in `$2`. `DD` is available in `$``  (the "prematch"), and `YY` is available in `$'` ("postmatch").

```
$, = $";

```

This sets the output field separator equal to the list separator, the latter is by default a space. This makes that our output numbers are separated by a space.

```
say $`    , $1    , $2    , $';
say $' + 1, $2 - 1, $1 - 3, $` + 3;
say $1 - 2, $` + 2, $' + 2, $2 - 2;
say $2 + 1, $' - 1, $` + 1, $1 - 1

```

Print out the 16 required numbers. In the top row, it will keep any leading spaces, as the values are printed "as is".

# Answer
> 1 votes
# Charcoal, 46 bytes

```
Ｅ⪪+5?IJ>2.3-K=@H,4⁴⪫Ｅι◧Ｉ⁺⁻﹪℅λχ³§Ｉ⪪⪫⪪θ/ω²÷℅λχ²

```

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

```
Ｅ⪪+5?IJ>2.3-K=@H,4⁴

```

Split the string literal `+5?IJ>2.3-K=@H,4` into chunks of 4 characters and loop over each chunk, which represents a row of the magic square.

```
⪫Ｅι◧Ｉ...²

```

Loop over each character, and pad each result to 2 characters and join them together to form the row.

```
⁺⁻﹪℅λχ³§...÷℅λχ

```

Take the ASCII code of the character and divmod it by 10. Subtract 3 from the remainder to give a value in the range `-3`..`3` and add the date part given by the quotient (this is offset by 4 but that works due to Charcoal's cyclic indexing).

```
Ｉ⪪⪫⪪θ/ω²

```

Delete the `/`s from the input string, split the result into pairs of digits and take their value.

# Answer
> 1 votes
# Perl 5 \+ `-pF/\/?(\d\d)/ -Mbigint`, 74 bytes

```
$_="1357
7531
3175
5713";s!.!$F[$&]-3+(3333420615514242=~/./g)[$i++].$"!ge

```

Try it online!

Verify all test cases online!

## Explanation

The `-F` flag, splits the input into `@F` as `('',22,'',12,'',18,'',87)`. In the code `$_` is set to a string containing the index of `@F` that we need the number from, then `s///` replaces any char (`.` \- this excludes newline) with the the corresponding value from `@F` minus `3`, plus the digit from `3333420615514242` at the `$i`ndex, appending `$"` (space).

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


title: Pre-order + post-order to in-order

text:
# Question
Title: Pre-order + post-order to in-order
# Task

Given the pre-order and post-order traversals of a full binary tree, return its in-order traversal.

The traversals will be represented as two lists, both containing *n* distinct positive integers, each uniquely identifying a node. Your program may take these lists, and output the resulting in-order traversal, using any reasonable I/O format.

You may assume the input is valid (that is, the lists actually represent traversals of some tree).

This is , so the shortest code in bytes wins.

# Definitions

A **full binary tree** is a finite structure of **nodes**, represented here by unique positive integers.

> A full binary tree is either a **leaf**, consisting of a single **node**:
>
> ```
>                                       1
>
> ```
>
> Or a **branch**, consisting of one **node** with two **subtrees** (called the *left* and *right subtrees*), each of which is, in turn, a full binary tree:
>
> ```
>                                       1
>                                     /   \
>                                   …       …
>
> ```

Here’s a full example of a full binary tree:

```
                                        6
                                      /   \
                                    3       4
                                   / \     / \
                                  1   8   5   7
                                     / \
                                    2   9

```

---

The **pre-order traversal** of a full binary tree is recursively defined as follows:

> * The pre-order traversal of a **leaf** containing a node **n** is the list \[**n**\].
> * The pre-order traversal of a **branch** containing a node **n** and sub-trees **(L, R)** is the list \[**n**\] + **preorder**(**L**) + **preorder**(**R**), where + is the list concatenation operator.

For the above tree, that’s **\[6, 3, 1, 8, 2, 9, 4, 5, 7\]**.

---

The **post-order traversal** of a full binary tree is recursively defined as follows:

> * The post-order traversal of a **leaf** containing a node **n** is the list \[**n**\].
> * The post-order traversal of a **branch** containing a node **n** and sub-trees **(L, R)** is the list **postorder**(**L**) + **postorder**(**R**) + \[**n**\].

For the above tree, that’s **\[1, 2, 9, 8, 3, 5, 7, 4, 6\]**.

---

The **in-order traversal** of a full binary tree is recursively defined as follows:

> * The in-order traversal of a **leaf** containing a node **n** is the list \[**n**\].
> * The in-order traversal of a **branch** containing a node **n** and sub-trees **(L, R)** is the list **inorder**(**L**) + \[**n**\] + **inorder**(**R**).

For the above tree, that’s **\[1, 3, 2, 8, 9, 6, 5, 4, 7\]**.

---

In conclusion: given the pair of lists **\[6, 3, 1, 8, 2, 9, 4, 5, 7\]** (pre) and **\[1, 2, 9, 8, 3, 5, 7, 4, 6\]** (post) as input, your program should output **\[1, 3, 2, 8, 9, 6, 5, 4, 7\]**.

# Test cases

Each test case is in the format `preorder, postorder → expected output`.

```
[8], [8] → [8]
[3,4,5], [4,5,3] → [4,3,5]
[1,2,9,8,3], [9,8,2,3,1] → [9,2,8,1,3]
[7,8,10,11,12,2,3,4,5], [11,12,10,2,8,4,5,3,7] → [11,10,12,8,2,7,4,3,5]
[1,2,3,4,5,6,7,8,9], [5,6,4,7,3,8,2,9,1] → [5,4,6,3,7,2,8,1,9]

```

# Answer
> 5 votes
# Perl, ~~69~~ ~~66~~ ~~62~~ ~~56~~ 53 bytes

Includes +1 for `-p`

Takes postorder followed by preorder as one line separated by space on STDIN (notice the order of pre and post). Nodes are represented as unique letters (any character that is not space or newline is OK).

```
inpost.pl <<< "98231 12983"

```

`inpost.pl`:

```
#!/usr/bin/perl -p
s%(.)(.)+\K(.)(.+)\3(\1.*)\2%$4$5$3$2%&&redo;s;.+ ;;

```

Using the original purely numeric format needs a lot more care to exactly identify a single number and comes in at 73 bytes

```
#!/usr/bin/perl -p
s%\b(\d+)(,\d+)+\K,(\d+\b)(.+)\b\3,(\1\b.*)\2\b%$4$5,$3$2%&&redo;s;.+ ;;

```

Use as

```
inpostnum.pl <<< "11,12,10,2,8,4,5,3,7 7,8,10,11,12,2,3,4,5"

```

# Answer
> 4 votes
# Haskell, ~~84~~ 83 bytes

```
(a:b:c)#z|i<-1+length(fst$span(/=b)z),h<- \f->f i(b:c)#f i z=h take++a:h drop
a#_=a

```

# Answer
> 2 votes
## JavaScript (ES6), 100 bytes

```
f=(s,t,l=t.search(s[1]))=>s[1]?f(s.slice(1,++l+1),t.slice(0,l))+s[0]+f(s.slice(l+1),t.slice(l)):s[0]

```

I/O is in strings of "safe" characters (e.g. letters or digits). Alternative approach, also 100 bytes:

```
f=(s,t,a=0,b=0,c=s.length-1,l=t.search(s[a+1])-b)=>c?f(s,t,a+1,b,l)+s[a]+f(s,t,l+2+a,l+1,c-l-2):s[a]

```

# Answer
> 2 votes
# APL (Dyalog Extended), 31 bytes

```
{0::⍵⋄∊2⌽∇¨⍵⊂⍨¯⍸1 2,2⊃⍋⍵}⍤⌽⍤⍳⊇⊣

```

Try it online!

An anonymous infix function that takes the preorder on its left and the postorder on its right.

### How it works

This solution uses multiple APL-specific features.

Given the input `[7,8,10,11,12,2,3,4,5], [11,12,10,2,8,4,5,3,7]`, it first computes the index of () each number in the right arg inside the left arg. The index is 1-based by default. This allows to work on a single array instead of two arrays. We will manipulate the array of "indices" until the very end.

```
      pre←7 8 10 11 12 2 3 4 5 ⋄ post←11 12 10 2 8 4 5 3 7
      pre ⍳ post
4 5 3 6 2 8 9 7 1

```

Then take the reverse :

```
      ⌽4 5 3 6 2 8 9 7 1
1 7 9 8 2 6 3 5 4

```

At this point, we can identify the root and left and right branches: `1` is the root, `7 9 8` (after 1 and before 2) are on the right branch, and `2 6 3 5 4` are on the left branch. Each branch can be handled recursively (where the first element is the root of the branch, and that +1 splits the left and right branches). So we create a recursive inline function `{...}` where  denotes the argument and  is the recursive call.

Inside it, we will eventually split the array `1 7 9 8 2 6 3 5 4` to 3 subarrays `(1)(7 9 8)(2 6 3 5 4)`. We can use "partition" , which splits the array at ones as the starting point, so giving `1 1 0 0 1 0 0 0 0` will do.

```
      1 1 0 0 1 0 0 0 0⊂1 7 9 8 2 6 3 5 4
┌─┬─────┬─────────┐
│1│7 9 8│2 6 3 5 4│
└─┴─────┴─────────┘

```

`2⊃⍋⍵` is a short way to extract the index of the second smallest element.  is called "grade up", which is related to sorting but doesn't sort the elements directly; instead, it tells us which element should go where in the sorted array. So the result looks like `[index of the smallest, index of the 2nd smallest, ..., index of the largest]`. Naturally, taking the second element from that gives `index of the 2nd smallest`.

```
      {2⊃⍋⍵}1 7 9 8 2 6 3 5 4
5

```

It gives the position of the third 1 in the partition marker. The first and second are trivial (1 and 2). So we concatenate (`,`) the 5 with `1 2`, and convert it to the counts (`¯⍸`) giving `[count of 1s, count of 2s, ...]`:

```
      {¯⍸1 2,2⊃⍋⍵}1 7 9 8 2 6 3 5 4
1 1 0 0 1

```

in Extended accepts short markers, so we can use the above to partition :

```
      {⍵⊂⍨¯⍸1 2,2⊃⍋⍵}1 7 9 8 2 6 3 5 4
┌─┬─────┬─────────┐
│1│7 9 8│2 6 3 5 4│
└─┴─────┴─────────┘

```

Now it's time for recursive call. `2⊃⍋⍵` on a single-element array will error, so we guard it with `0::⍵` (catch any error and return the argument as-is). On the result, the left branch should be on the left of the root, so we rotate the result twice to the left `2⌽`, and flatten it .

```
      {0::⍵⋄∊2⌽∇¨⍵⊂⍨¯⍸1 2,2⊃⍋⍵} 1 7 9 8 2 6 3 5 4
4 3 5 2 6 1 8 7 9

```

Finally, we convert each of the "indices" to the number at that index in the preorder (the left arg).

```
      4 3 5 2 6 1 8 7 9 ⊇ pre
11 10 12 8 2 7 4 3 5

```

---

For comparison, porting the Haskell answer is quite longer:

# APL (Dyalog Extended), 42 bytes

```
{0::⍺⋄l←⍵⍳2⊃⍺⋄(⍵∇⍨l↑1↓⍺),(⊃⍺),(l↓1↓⍺)∇l↓⍵}

```

Try it online!

# Answer
> 1 votes
# Python 3.8 (pre-release), 85 bytes

```
f=lambda a,b:a==b and a or f(a[1:(i:=a.find(b[-2]))],b[:i-1])+a[0]+f(a[i:],b[i-1:-1])

```

Try it online!

Input is 2 strings, each string can contain any character.

### Explanation:

Consider the input:

```
Preorder  631829457
Postorder 129835746

```

We can split each input into 3 parts (the root, the left subtree, and right subtree) as follows:

* The first character in the preorder traversal must be the root. Similarly, the last character in the postorder traversal must also be the root.
* Since `4` is the second-to-last character in the postorder string, we know that 4 must be the root of the right subtree. This means that `4` must be the first character in the preorder string of the right subtree.

```
Preorder  6 | 31829 | 457
Postorder     12983 | 574 | 6

```

We can then recurs on the left and right part.

---
Tags: code-golf, array, binary-tree, tree-traversal
---