AoCG2021 Day 25: Stitching maps together

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2020 Day 20, Part 1. (This day is a dreaded one for many of you, I know :P)

Obligatory final "but you're not Bubbler" explanation.

As the train carries you to the destination, you've got some spare time. You open the travel booklet for the vacation spot, and its map is divided into nine pieces... in random order and orientation. Apparently you got a brain teaser version of the booklet or something.

The map pieces are represented as a square grid of zeros and ones, and they are rotated and/or flipped in a random orientation. The four edges of each map piece are the clues: if two pieces have a common edge pattern (one of the four sides), two pieces are stitched together on that edge.

If two pieces look like this:

Piece 1:
#..##
##...
#.#.#
.#.##
....#

Piece 2:
#.###
.....
.#...
##..#
.##..


The right edge of Piece 1 and the top edge of Piece 2 match; you can flip Piece 2 with respect to its main diagonal, and then join the two horizontally.

You can't decide the orientation of the whole map yet, but at least you can assemble the 3x3 map and tell which piece goes to the center. This is the objective of this challenge.

The edge patterns are all distinct; for any given pattern that appears in the input, there are either exactly two pieces (for interior edges) or one (for outer edges) with that pattern. Also, every interior edge pattern is asymmetric, so that you can uniquely join the edges together (modulo orientation as a whole).

Input: A list of nine square grids of zeros and ones, representing the nine map pieces; you can choose any other two distinct values (numbers, chars, or strings) for zeros and ones.

Output: The square grid that corresponds to the center piece (any orientation is fine), or its index (0- or 1-based) in the input.

Standard rules apply. The shortest code in bytes wins.

Test case

Uses #s and .s.

Input:
.###.#
#####.
..#..#
#..##.
.#.###
..####

#...#.
#..#..
.#.#..
.###..
#....#
...#.#

.##...
#..#..
..####
##...#
##.###
#.....

..#.##
#.....
#.##.#
###.##
#....#
#...##

#.#..#
##.#.#
#...#.
#.###.
..#.#.
.##..#

..##.#
#....#
....##
.#.###
.#...#
#.#.#.

....##
##.#.#
.#.###
.#....
.###.#
.#.###

.#....
..#.#.
##....
######
.#..#.
#..##.

..#...
....##
###..#
.#.#..
#####.
.#.##.

Answer: 2nd-to-last piece (8th with 1-indexing)


Charcoal, 51 bytes

Ｆ⁹«≔⟦⟧θＷＳ⊞θκ⊞υ⁺Ｅ²⭆θ§μ±κＥ²§θ±κ»ＩΦ⁹⬤§υι⊙υ∧⁻ιξ∨№νλ№ν⮌λ


Try it online! Link is to verbose version of code. Outputs the 0-indexed index of the of the centre piece. Explanation:

Ｆ⁹«


Loop over the 9 pieces.

≔⟦⟧θＷＳ⊞θκ


Input the piece.

⊞υ⁺Ｅ²⭆θ§μ±κＥ²§θ±κ


Extract the four edges.

»ＩΦ⁹⬤§υι⊙υ∧⁻ιξ∨№νλ№ν⮌λ


Output the index of the piece whose (possibly reversed) edges all appear on other pieces.

• Does this work for flips? The explanation suggests not, and testing it with a manually-flipped #7 seems to give no output... (but quite likely I've not understood...) Dec 25, 2021 at 13:37
• @DominicvanEssen Ah, I didn't spot that part, I'll have to update my answer in that case.
– Neil
Dec 25, 2021 at 20:32
• @DominicvanEssen I think this should work, and I managed to limit the damage to 3 bytes because I can extract the edges more efficiently now.
– Neil
Dec 25, 2021 at 20:51

TypeScript Types, 738 bytes

//@ts-ignore
type a<A>=A extends[0,...infer B]?B:[];type b<C,P=0>=[C]extends[P]?C:b<C|c<C>|e<C>,C>;type c<T,X=[]>=T extends[...infer T,infer A]?c<T,[...X,A]>:X;type d<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type e<G>={[X in keyof G]:G[X]extends infer R?{[Y in keyof R]:G[Y][X]}:0};type f<g,h,i=g,j=h>=[g]extends[never]?Extract<h,[{},[...d<h[1]>,0],[...d<h[2]>,0]]>[0]:i extends i?b<i>extends infer k?k extends k?j extends j?(j[0][0]extends c<k>[0]?[[...j[1],0],j[2]]:c<j[0]>[0]extends k[0]?[a<j[1]>,j[2]]:e<j[0]>[0]extends c<e<k>>[0]?[j[1],[...j[2],0]]:c<e<j[0]>>[0]extends e<k>[0]?[j[1],a<j[2]>]:never)extends infer l?l extends l?f<Exclude<g,i>,h|[k,...l]>:0:0:0:0:0:0;type M<P>=f<Exclude<P[number],P[0]>,[P[0],[0,0],[0,0]]>


Try It Online!

Ungolfed / Explanation

type DecNat<A> = A extends [0, ...infer B] ? B : []

// Get all orientations of a square by repeatedly reflecting Cur
type Orientations<Cur, Prev=0> =
// If Cur == Prev,
[Cur] extends [Prev]
// Return Cur, which must include all orientations
? Cur
// Otherwise, set Prev to Cur and add to Cur its reflection over the lines Y=0 and X=Y
: Orientations<Cur | Reverse<Cur> | TransposeSquare<Cur>, Cur>

type Reverse<T, X=[]> = T extends [...infer T, infer A] ? Reverse<T, [...X, A]> : X

// Filter a union of tuples for those with the smallest length
type Shortest<T, K=keyof T> = T extends T ? keyof T extends K ? T : never : 0

// e.g. [[1, 2], [3, 4]] to [[1, 3], [2, 4]]
type TransposeSquare<Grid> = {
[X in keyof Grid]: Grid[X] extends infer Row ? {
[Y in keyof Row]: Grid[Y][X]
} : 0
}

type Assemble<
// A union of 2d grids of 0s and 1s
RemainingPieces,
// A union of map entries of the form [Piece, X, Y], where X and Y are Nats
CurrentMap,
/* aliases for mapping */
CurrentPiece = RemainingPieces,
MapEntry = CurrentMap
> =
// If there are no more remaining pieces,
[RemainingPieces] extends [never]
// Return the center piece (assumes 3x3)
? Extract<CurrentMap, [{}, [...Shortest<CurrentMap[1]>, 0], [...Shortest<CurrentMap[2]>, 0]]>[0]
: (
// Map over RemainingPieces, binding CurrentPiece
CurrentPiece extends CurrentPiece ?
// Map over the orientations of CurrentPiece, binding OrientedPiece
Orientations<CurrentPiece> extends infer OrientedPiece ? OrientedPiece extends OrientedPiece ?
// Map over CurrentMap, binding MapEntry
MapEntry extends MapEntry ?
// Check each relative position
(
// If the top edge of MapEntry matches the bottom edge of OrientedPiece
MapEntry[0][0] extends Reverse<OrientedPiece>[0]
// [X + 1, Y]
? [[...MapEntry[1], 0], MapEntry[2]]
// If the bottom edge of MapEntry matches the top edge of OrientedPiece
: Reverse<MapEntry[0]>[0] extends OrientedPiece[0]
// [X - 1, Y]
? [DecNat<MapEntry[1]>, MapEntry[2]]
// If the left edge of MapEntry matches the right edge of OrientedPiece
: TransposeSquare<MapEntry[0]>[0] extends Reverse<TransposeSquare<OrientedPiece>>[0]
// [X, Y + 1]
? [MapEntry[1], [...MapEntry[2], 0]]
// If the right edge of MapEntry matches the left edge of OrientedPiece
: Reverse<TransposeSquare<MapEntry[0]>>[0] extends TransposeSquare<OrientedPiece>[0]
// [X, Y - 1]
? [MapEntry[1], DecNat<MapEntry[2]>]
: never
// Bind the above to Position, and if it's not never,
) extends infer Position ? Position extends Position ?
// Recurse:
Assemble<
// Remove CurrentPiece from RemainingPieces
Exclude<RemainingPieces, CurrentPiece>,
// Add OrientedPiece to CurrentMap at Position
CurrentMap | [OrientedPiece, ...Position]
>
// An excessive number of unreachable states
: 0 : 0 : 0 : 0 : 0 : 0
)

type Main<Pieces> =
// Start the map with Pieces[0] as (2, 2), so that coordinates always stay non-negative for 3x3 grids
Assemble<
Exclude<Pieces[number], Pieces[0]>,
[Pieces[0], [0,0], [0,0]]
>


Pari/GP, 114 bytes

a->l=[[m[1,],m[#m,],m[,1]~,m[,#m]~]|m<-a];[i|i<-[1..#a],vecsum([#[1|f<-concat(l),e==f||e==Vecrev(f)]|e<-l[i]])==8]


Try it online!

05AB1E (legacy), 20 bytes

ε4F¬søí}\)}D€íå4ôPƶà


Takes the input-pieces as a list of lines, so the input is a list of list of strings. Outputs the 1-based index of the center piece. (Could alternatively output the 0-based index by replacing the ƶà with 1k.)

Try it online.

Uses the legacy version of 05AB1E, because the zip/transpose builtin ø works on list of strings. In the new version of 05AB1E, this would have been 21 bytes by using the ÅΔ (get the index of the first truthy result), by taking the input-pieces as matrices of 0s/1s: Try it online (the header transforms the input).

Explanation:

ε           # Map over the pieces of the input-list:
4F         #  Loop 4 times:
¬        #   Get the first row (without popping the list of lines)
s       #   Swap so the piece is at the top again
øí     #   Rotate it once clockwise:
ø      #   Zip/transpose; swapping rows/columns
í     #   Reverse each line
}\        #  After the loop: discard the matrix
)       #  Wrap the four edges in a list
}D          # After the map: duplicate the list of edges
€í        # Reverse each edge in the copy
å       # Check for each if it's in the list of edges
# (which unfortunately flattens the entire list)
4ô     # So split it into parts of size 4 again
P    # Check for each if all four were truthy by taking the product
ƶ   #  Multiply each 0/1 by its 1-based index
à  #  Extract the maximum of this list
# OR:
1k  #  Get the 0-based index of the first truthy result (1)
# (after which this index is output implicitly as result)



Wolfram Language (Mathematica), 102 bytes

Pick[#,Total[Outer[Boole[#==#2||#==Reverse@#2]&,e={#[[1]],Last@#,First/@#,Last/@#}&/@#,e,2],{2,4}],8]&


Try it online!

r=range