Day18ManyWorldsInterpretation.kt

import io.reactivex.Observable
import io.reactivex.Single
import io.reactivex.schedulers.Schedulers
import kotlinx.collections.immutable.PersistentMap
import kotlinx.collections.immutable.PersistentSet
import kotlinx.collections.immutable.persistentSetOf
import kotlinx.collections.immutable.toPersistentMap
import org.assertj.core.api.Assertions.assertThat
import org.junit.Ignore
import org.junit.Test
import java.util.concurrent.ConcurrentHashMap

/**
 *
 */
class Day18ManyWorldsInterpretation {
    /**
     * Nope this does not work for [smallMaze81] and [bigMaze]
     */
    @Ignore
    @Test
    fun silverTest() {
        assertThat(Walker(smallMaze8).computeSteps().also { println(it) }.first).isEqualTo(8)
        assertThat(Walker(smallMaze81).computeSteps().also { println(it) }.first).isEqualTo(81)
        assertThat(Walker(smallMaze86).computeSteps().also { println(it) }.first).isEqualTo(86)
        assertThat(Walker(smallMaze132).computeSteps().also { println(it) }.first).isEqualTo(132)
        assertThat(Walker(smallMaze136).computeSteps().also { println(it) }.first).isEqualTo(136)
    }

    @Test
    @Ignore("This does not finish, I don't know why")
    fun silver() {
        assertThat(Walker(bigMaze).computeSteps().also { println(it) }.first).isEqualTo(6098)
    }

    @Ignore
    @Test
    fun gold() {
        val result = Observable.fromArray(0, 1, 2, 3)
            .flatMapSingle { index -> Walker(bigMaze1698, index).computeStepsAsync() }
            .toList()
            .map { solutions -> solutions.sumBy { it.first } }
            .blockingGet()

        assertThat(result).isEqualTo(1698)
    }

    class Walker(mapString: String, private val index: Int? = 0) {
        private fun parseMapAndPosition(map: String): PersistentMap<Point, Char> {
            return parseMap(map)
                .mapValues { (k, v) -> if (v == '.') ' ' else v }
                .toPersistentMap()
        }

        private val map: PersistentMap<Point, Char> = parseMapAndPosition(mapString)
        private val starts: List<Point> = map.entries.mapNotNull { (k, v) -> if (v == '@') k else null }
        private val start: Point = starts[index ?: 0]

        private fun Point.value(): Char = map.getValue(this)
        private fun Char.isKey() = isLetter() && isLowerCase()

        data class AvailablePoint(val point: Point, val steps: Int)
        data class CacheKey(val point: Point, val collected: Set<Char>)

        private val cache: MutableMap<CacheKey, Single<Pair<Int, String>>> = ConcurrentHashMap()

        fun computeSteps(): Pair<Int, String> {
            return computeStepsAsync().blockingGet()
        }

        fun computeStepsAsync(): Single<Pair<Int, String>> {
            return reachPoints(start, externalKeys(), 0)
        }

        /** Keys which we cannot collect */
        private fun externalKeys(): Set<Char> {
            if (index == null) {
                return emptySet()
            } else {

                return generateSequence(starts.minus(start).toSet()) { points: Set<Point> ->
                    val morePoints = points + points
                        .flatMap { point -> listOf(point.left(), point.up(), point.right(), point.down()) }
                        .filter { point -> point.value() != '#' }
                        .filter { point -> point !in points }
                    if (morePoints.size != points.size) morePoints else null
                }
                    .last()
                    .map { it.value() }
                    .filter { it.isKey() }
                    .toSet()
            }
        }

        /** return the amount of steps which is required to reach the best next position + best other further steps */
        private fun reachPoints(
            start: Point,
            collected: Set<Char>,
            prev: Int,
            spawn: Boolean = false
        ): Single<Pair<Int, String>> {
            return (cache.computeIfAbsent(CacheKey(start, collected)) {
                val reachable: List<AvailablePoint> = reachOutWithWave(start, collected)

                val toReach = reachable.filter { (point, steps) -> point.value() !in collected }
                Observable.fromIterable(toReach)
                    .flatMapSingle { (point, steps) ->
                        reachPoints(point, collected.plus(point.value()), steps)
                            .subscribeOn(Schedulers.computation())
                            .map { it.copy(second = it.second + point.value()) } // adds the path
                    }
                    .toList() // Zip it!
                    .map { list ->
                        list.minBy { it.first } // take better possibility
                            ?: 0 to "*"// no possibilities - end
                    }
                    .cache()// don't forget to cache

            }).let { single -> single.map { it.copy(it.first + prev) } }
        }

        private data class Wave(val points: PersistentSet<Point>, val front: List<AvailablePoint>, val iterations: Int)

        /** A wave starting at [position] and going in all directions unless it encounters a closed door, a wall, or a new key */
        private fun reachOutWithWave(position: Point, collected: Set<Char>): List<AvailablePoint> {
            // check(position.value().let { it.isKey() || it == '@' }) { "Position $position=${position.value()} is not a key!" }
            val seed =
                Wave(points = persistentSetOf(position), front = listOf(AvailablePoint(position, 0)), iterations = 0)
            return generateSequence(seed) { wave: Wave ->
                val keyLocations =
                    wave.front.filter { available -> available.point.value().let { it.isKey() && it !in collected } }
                val growth = wave.front
                    .map { available: AvailablePoint -> available.point }
                    .filter { point: Point -> !point.value().isKey() || point.value() in collected }
                    .flatMap { point -> listOf(point.left(), point.up(), point.right(), point.down()) }
                    .filter { point -> point !in wave.points }
                    .filter { point ->
                        with(point.value()) {
                            when {
                                this == ' ' -> true
                                this == '@' -> true
                                this == '#' -> false
                                isLowerCase() -> true
                                isUpperCase() -> toLowerCase() in collected
                                else -> throw Exception("Cannot deal with ${point.value()}")
                            }
                        }
                    }
                    .map { point -> AvailablePoint(point, wave.iterations + 1) }
                val newFront = growth.plus(keyLocations)

                when {
                    growth.isNotEmpty() -> Wave(
                        wave.points.addAll(newFront.map { it.point }),
                        front = newFront,
                        iterations = wave.iterations + 1
                    )
                    else -> null
                }
            }
                .last()
                .front
                // remove non-keys from the front
                .filter { availablePoint -> availablePoint.point.value().let { it.isKey() && it !in collected } }
        }


        /**
         * Prints the map with available points and the reach
         */
        private fun printDecision(
            map: PersistentMap<Point, Char>,
            position: Point,
            collected: List<Char>,
            reach: List<Point>
        ) {
            val path = reach.filter { map[it] == ' ' || map[it]?.toLowerCase() in collected }
            val toPrint = map
                .putAll(path.map { it to '.' }.toMap())
                .put(position, '@')

            printMap(tiles = toPrint, invertedY = true) {
                when {
                    it?.toLowerCase() in collected -> " " // skip collected stuff
                    else -> "$it"
                }
            }
            println()
        }
    }


    val bigMaze1698 = """
#################################################################################
#...#..j..........#.........#...........#.......#........n......#.....#........m#
#.#.#.#.###########.###.#####.#######O#####.###.#.#########.#.###.#.###.###.###.#
#.#.#.#...............#.Z.......#...#...#...#.#.#.#.......#.#.....#.....#.X.#...#
#.#.#.###########################P#.#.#.#.###.#.###.#####.###.###########.###.###
#.#.#.#.......#.........#......b..#.#.#.#.#.......#...#.#...#.....#.......#.....#
#.#.#.#.###.###.#######.#.#########.###.#.#######.###.#.###.#####.#.#############
#.#.#.#.#...#...#..l#...#.#.......#.#...#.....#.......#.#...#.....#.........#..k#
#.###.#.###.#.#####.#.###.#######.#.#.###.###.#########.#.###.#####.#######.#.#.#
#...#.#...#.#.#...#...#...#.....#.#...#.#...#...#.....#.#.#...#...#...#...#...#.#
#.#.#.#.#.###.#.#U###.###.#.###.#.#####.###.###.#.###.#.#.#.###.#.#####.#.#####F#
#.#.#.#.#...#...#...#.....#.#...#.......#...#g#...#.#.#...#.#...#...#.E.#.....#.#
#.#.#.#.###.#######.#######.###.###Y#.###.###.#####.#.###.###.#####.#.#######.#.#
#.#...#...#...#.....#......a..#...#.#...#.....#.....#...#.....#.......#.....#...#
#.#####D#####.#.#######.#####.###.###.#.#####.#.###.###.#################.#####.#
#.M...#.#...#.#.#c....#...#...#.#...#.#.#...#.#.#.#.#.#.#...............#...#...#
#####.###.#.#.#H#.###.#####.###.###.#.#.#.###.#.#.#.#.#.#.###########.#.###.#.###
#...#.....#.#.#.#...#...#...#.....#.#.#.#...#.#.#.....#.......#.....#.#.#...#.#.#
#.#.#######.#.#.#.#####.#.###.#.###.###.#.#.#.#.#####.#########.###.###.#.###.#.#
#.#.#....x#.#.#...#.....#.#...#.#..i#...#.#.#.#...#...#.........#.....#.#...#...#
#.###K#.#.#.#.#####.#####.#.###.#.###.#####.#.###.#####.###.#########.#.#.#.###.#
#...#.#.#.#.#.....#..r#...#...#.#.#.....#...#.....#.....#...#.......#...#.#.....#
#.#.#.#.###.#.###.#####.#####.#.#.#.###.#.#####.###.#####.#########.#####.#####.#
#.#.#.#.....#.#.........#.....#.#.#...#.#.......#...#...#.#.........#.....#...#.#
###.#.#########.#########.#####.#.#####.#####.###.#.#.#.###.#########.#####.#.#.#
#...#...#.....#.#...........#...#.....#.#..t#.#.#.#.#.#.....#...#.........#.#.#.#
#.#####.#.#.#.#.#####.#####.#########.#.#.#.#.#.#.#.#.#######.###.#########.#.###
#.......#.#.#.#.....#...#.#.....#...#.#.#.#.#...#.#.#.....#.......#...#...#.#...#
#.#########.#.###.#.###.#.#####.#.#.#.#.#.#.#####.#.#####.#########.#.#.#.#.###.#
#.#.....#...#...#.#.#...#...#...#.#...#.#.#.......#.#...#.......#q..#...#...#...#
#.###.#.#.#####.###.###.#.###.###.#####.#.#########.###.#######.#.###########.###
#.....#.#...#.#...#...#.#...#...#...#...#...#...#.#.....#.......#.#...#.....#...#
#######.#.#.#.###.#.#.#.###.###.###.###.#.#.#.#.#.#####.#.#######.#.###.#.#####.#
#.....#.#.#.#.....#.#.#.......#...#.....#.#.#.#.#.#.....#.#...#...#...#.#.....#.#
#.#.###.#.#.###.#####.#####.###.#.#####.#.#.#.#.#.#.#####.#.#.#.#####.#.#####.#.#
#.#.#...#.#...#.#...#.#.....#...#...#...#.#...#.#...#...#...#...#.....#.#.....#.#
###.#.###.###.#.#.#.#.#######.#######.###.#####.#.###.#.#########.#.###.#.###.#.#
#...#.#...#...#.#.#.#...#.....#.....#.#.#.#...#.#.#...#.......#...#.....#...#.#.#
#.###.#####.###.#.#.###.#.#####.###.#.#.#.###.#.###.#######.###.###########.###.#
#...........#.....#.....#.........#....@#@....#...........#...............#w....#
#################################################################################
#.....#.....#.......#.........#........@#@........#.#...................#...#...#
#.###.###.#.#.#####.#.#.#####.#.#####.#.#.#######.#.#.###############.#.#.#.#.#.#
#...#.....#...#.#...#.#...#.#.#.#.#...#.#.......#...#...#...#...#...#.#...#...#.#
###.#####.#####.#.#######.#.#.#.#.#.###.#.#####.###.###.#.###.#.#.#.#.#########.#
#...#...#.#...#.#.....#...#...#...#...#.#.#...#...#.#...#.#...#...#.#.........#.#
#.###.#.###.#.#.#####.#.###.#########.#.#.###.###.###.###.#.#######.###########.#
#.....#.....#.#.....#...#.#.#.......#.#.#.......#.....#...#.#...................#
#############.#####.#####.#.#.#####.#.#.#######.#######.#.#.###.###############.#
#...........#.....#.......#.#...#.#.#.#.#.....#.........#.#...#.#.........#...#.#
#########.#.#####.#.###.###.###.#.#.#.###.#.#.#######T#######.###.#######.#.###.#
#........f#.#...#.#...#.....#...#...#...#.#.#.#.....#.#.......#...#...#...#.#...#
#.#######.###.#.#.#####.#####.###.#####.#.#.#.#.###.#.#.#######.#####.#.###.#.###
#.#.#.....#...#.#.....#.......#...#.....#.#.#.#.#.#...#.#...#.......#.#.#.......#
#.#.#.#####.###.#.###.#########.###.#.###.#.###.#.#####.#.#.#.#####.#.#.#######.#
#.#.#...#...#.#.#...#.#...#...#.#.#.#...#.#...#.#...#...#.#...#...#...#.#.....#.#
#.#.###.#.###.#.###.#.###.#.#.#.#.#.###.#####.#.#.#.#.###.#####.#.#####.#.###.#.#
#.#.....#.#...#...#.#...#...#.#.#...#.#.#.....#.#.#.#.......#...#.#...#....s#.#v#
#.#.#####.#.#.###.###.#.#.###.#.###.#.#.#.#####.###.#####.###.###.#.#.#######.#.#
#.#...#...#.#...#...#.#.#...#.#...#..y#.#.#.........#...#.#...#.....#.........#.#
#.###.#.#######.###.###.#####.###.#####.#.#.#####.###.#.###.#########.###########
#.#...#.........#.#...#.....#...#.#.....#...#...#.#...#...#.#.......#.#.........#
#.#.###########.#.#########.#.###.#.#########.#.#.#.#####.#.#######R###.#######.#
#.#.#.....Q...#...#.........#...#.#.#...#...#.#.#.#.#...#.....#...#.....#...#.C.#
#.###.#.#########.#.###.#######.#.#.#.#.#.#.#.#.#.#.###.#####.#.#.#########.#.###
#...#.#...#...G.#.#...#.#.#.....#.#...#.#.#.#.#.#.#...#...#...#.#.....#.....#.#.#
#.#.#.###.#.###.#.#####.#.#.#.###.#####.#.#.#.#.#.###.#.#.#.#####.###.#.#####.#.#
#.#.#...#.#.#...#.#.....#.#.#.#...#...I.#.#...#.#...#.#.#.#.#.....#.#...#...#...#
#.#S###.#.#.#.#.#.#.#####.#.#.#.###.###.#.#####.#####.#.#.#.###.###.###.#.#.###.#
#.#.....#...#.#.#...#.......#...#...#.#.#.....#.......#.#.#...#.#.#...#.#.#.....#
#.###########.#######.###########.###.#.#.###.#########.#.###.#.#.#.#.#.#.#######
#e#.......#...#.....#.#.......#...#.#...#.#...#...#.#...#.......#...#...#.#.....#
#.#.#######.#.#.#.###.#.###.###.#.#.#.###N#.###.#.#.#.#########.#####.###.#.###.#
#.#.#.......#.#.#.....#...#.#...#.#.....#.#.#...#.#.#.#..p..#...#...#...#h..#.#.#
#.#.#.#########W#########.#.#.###.#####.###.#.###.#.#.#.###.#####.#B#########.#.#
#...#d....#...#.....#...#.#.....#.....#.#...#.#.#.#.#.#...#.#.....#.#.......#...#
###.#####.#.#.#####.#.#.###.#######.#.#.#.###.#.#.#.#.###.#.#.#####.#.#####.#.###
#...#...#...#.....#...#.V.#.#.....#.#.#.#.#...#z#.#...#...#.#...#.#...#.#.L.#.#.#
#.#####.#######.#########.###.###.###.#.#.#.###J#.#####.###.###.#.#####.#.###.#.#
#.............#...............#.....A.#.#.......#........o#.............#....u..#
#################################################################################
""".trimIndent()


    val smallMaze8 = """
#########
#b.A.@.a#
#########"""
    val smallMaze86 = """
########################
#f.D.E.e.C.b.A.@.a.B.c.#
######################.#
#d.....................#
########################"""

    val smallMaze132 = """
########################
#...............b.C.D.f#
#.######################
#.....@.a.B.c.d.A.e.F.g#
########################"""

    /**
     * Shortest paths are 136 steps; one is: a, f, b, j, g, n, h, d, l, o, e, p, c, i, k, m
     */
    val smallMaze136 = """
#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################"""

    /**
     * Shortest paths are 136 steps; one is: a, c, f, i, d, g, b, e, h
     */
    val smallMaze81 = """
########################
#@..............ac.GI.b#
###d#e#f################
###A#B#C################
###g#h#i################
########################"""

    val bigMaze = """
#################################################################################
#...#..j..........#.........#...........#.......#........n......#.....#........m#
#.#.#.#.###########.###.#####.#######O#####.###.#.#########.#.###.#.###.###.###.#
#.#.#.#...............#.Z.......#...#...#...#.#.#.#.......#.#.....#.....#.X.#...#
#.#.#.###########################P#.#.#.#.###.#.###.#####.###.###########.###.###
#.#.#.#.......#.........#......b..#.#.#.#.#.......#...#.#...#.....#.......#.....#
#.#.#.#.###.###.#######.#.#########.###.#.#######.###.#.###.#####.#.#############
#.#.#.#.#...#...#..l#...#.#.......#.#...#.....#.......#.#...#.....#.........#..k#
#.###.#.###.#.#####.#.###.#######.#.#.###.###.#########.#.###.#####.#######.#.#.#
#...#.#...#.#.#...#...#...#.....#.#...#.#...#...#.....#.#.#...#...#...#...#...#.#
#.#.#.#.#.###.#.#U###.###.#.###.#.#####.###.###.#.###.#.#.#.###.#.#####.#.#####F#
#.#.#.#.#...#...#...#.....#.#...#.......#...#g#...#.#.#...#.#...#...#.E.#.....#.#
#.#.#.#.###.#######.#######.###.###Y#.###.###.#####.#.###.###.#####.#.#######.#.#
#.#...#...#...#.....#......a..#...#.#...#.....#.....#...#.....#.......#.....#...#
#.#####D#####.#.#######.#####.###.###.#.#####.#.###.###.#################.#####.#
#.M...#.#...#.#.#c....#...#...#.#...#.#.#...#.#.#.#.#.#.#...............#...#...#
#####.###.#.#.#H#.###.#####.###.###.#.#.#.###.#.#.#.#.#.#.###########.#.###.#.###
#...#.....#.#.#.#...#...#...#.....#.#.#.#...#.#.#.....#.......#.....#.#.#...#.#.#
#.#.#######.#.#.#.#####.#.###.#.###.###.#.#.#.#.#####.#########.###.###.#.###.#.#
#.#.#....x#.#.#...#.....#.#...#.#..i#...#.#.#.#...#...#.........#.....#.#...#...#
#.###K#.#.#.#.#####.#####.#.###.#.###.#####.#.###.#####.###.#########.#.#.#.###.#
#...#.#.#.#.#.....#..r#...#...#.#.#.....#...#.....#.....#...#.......#...#.#.....#
#.#.#.#.###.#.###.#####.#####.#.#.#.###.#.#####.###.#####.#########.#####.#####.#
#.#.#.#.....#.#.........#.....#.#.#...#.#.......#...#...#.#.........#.....#...#.#
###.#.#########.#########.#####.#.#####.#####.###.#.#.#.###.#########.#####.#.#.#
#...#...#.....#.#...........#...#.....#.#..t#.#.#.#.#.#.....#...#.........#.#.#.#
#.#####.#.#.#.#.#####.#####.#########.#.#.#.#.#.#.#.#.#######.###.#########.#.###
#.......#.#.#.#.....#...#.#.....#...#.#.#.#.#...#.#.#.....#.......#...#...#.#...#
#.#########.#.###.#.###.#.#####.#.#.#.#.#.#.#####.#.#####.#########.#.#.#.#.###.#
#.#.....#...#...#.#.#...#...#...#.#...#.#.#.......#.#...#.......#q..#...#...#...#
#.###.#.#.#####.###.###.#.###.###.#####.#.#########.###.#######.#.###########.###
#.....#.#...#.#...#...#.#...#...#...#...#...#...#.#.....#.......#.#...#.....#...#
#######.#.#.#.###.#.#.#.###.###.###.###.#.#.#.#.#.#####.#.#######.#.###.#.#####.#
#.....#.#.#.#.....#.#.#.......#...#.....#.#.#.#.#.#.....#.#...#...#...#.#.....#.#
#.#.###.#.#.###.#####.#####.###.#.#####.#.#.#.#.#.#.#####.#.#.#.#####.#.#####.#.#
#.#.#...#.#...#.#...#.#.....#...#...#...#.#...#.#...#...#...#...#.....#.#.....#.#
###.#.###.###.#.#.#.#.#######.#######.###.#####.#.###.#.#########.#.###.#.###.#.#
#...#.#...#...#.#.#.#...#.....#.....#.#.#.#...#.#.#...#.......#...#.....#...#.#.#
#.###.#####.###.#.#.###.#.#####.###.#.#.#.###.#.###.#######.###.###########.###.#
#...........#.....#.....#.........#...........#...........#...............#w....#
#######################################.@.#######################################
#.....#.....#.......#.........#...................#.#...................#...#...#
#.###.###.#.#.#####.#.#.#####.#.#####.#.#.#######.#.#.###############.#.#.#.#.#.#
#...#.....#...#.#...#.#...#.#.#.#.#...#.#.......#...#...#...#...#...#.#...#...#.#
###.#####.#####.#.#######.#.#.#.#.#.###.#.#####.###.###.#.###.#.#.#.#.#########.#
#...#...#.#...#.#.....#...#...#...#...#.#.#...#...#.#...#.#...#...#.#.........#.#
#.###.#.###.#.#.#####.#.###.#########.#.#.###.###.###.###.#.#######.###########.#
#.....#.....#.#.....#...#.#.#.......#.#.#.......#.....#...#.#...................#
#############.#####.#####.#.#.#####.#.#.#######.#######.#.#.###.###############.#
#...........#.....#.......#.#...#.#.#.#.#.....#.........#.#...#.#.........#...#.#
#########.#.#####.#.###.###.###.#.#.#.###.#.#.#######T#######.###.#######.#.###.#
#........f#.#...#.#...#.....#...#...#...#.#.#.#.....#.#.......#...#...#...#.#...#
#.#######.###.#.#.#####.#####.###.#####.#.#.#.#.###.#.#.#######.#####.#.###.#.###
#.#.#.....#...#.#.....#.......#...#.....#.#.#.#.#.#...#.#...#.......#.#.#.......#
#.#.#.#####.###.#.###.#########.###.#.###.#.###.#.#####.#.#.#.#####.#.#.#######.#
#.#.#...#...#.#.#...#.#...#...#.#.#.#...#.#...#.#...#...#.#...#...#...#.#.....#.#
#.#.###.#.###.#.###.#.###.#.#.#.#.#.###.#####.#.#.#.#.###.#####.#.#####.#.###.#.#
#.#.....#.#...#...#.#...#...#.#.#...#.#.#.....#.#.#.#.......#...#.#...#....s#.#v#
#.#.#####.#.#.###.###.#.#.###.#.###.#.#.#.#####.###.#####.###.###.#.#.#######.#.#
#.#...#...#.#...#...#.#.#...#.#...#..y#.#.#.........#...#.#...#.....#.........#.#
#.###.#.#######.###.###.#####.###.#####.#.#.#####.###.#.###.#########.###########
#.#...#.........#.#...#.....#...#.#.....#...#...#.#...#...#.#.......#.#.........#
#.#.###########.#.#########.#.###.#.#########.#.#.#.#####.#.#######R###.#######.#
#.#.#.....Q...#...#.........#...#.#.#...#...#.#.#.#.#...#.....#...#.....#...#.C.#
#.###.#.#########.#.###.#######.#.#.#.#.#.#.#.#.#.#.###.#####.#.#.#########.#.###
#...#.#...#...G.#.#...#.#.#.....#.#...#.#.#.#.#.#.#...#...#...#.#.....#.....#.#.#
#.#.#.###.#.###.#.#####.#.#.#.###.#####.#.#.#.#.#.###.#.#.#.#####.###.#.#####.#.#
#.#.#...#.#.#...#.#.....#.#.#.#...#...I.#.#...#.#...#.#.#.#.#.....#.#...#...#...#
#.#S###.#.#.#.#.#.#.#####.#.#.#.###.###.#.#####.#####.#.#.#.###.###.###.#.#.###.#
#.#.....#...#.#.#...#.......#...#...#.#.#.....#.......#.#.#...#.#.#...#.#.#.....#
#.###########.#######.###########.###.#.#.###.#########.#.###.#.#.#.#.#.#.#######
#e#.......#...#.....#.#.......#...#.#...#.#...#...#.#...#.......#...#...#.#.....#
#.#.#######.#.#.#.###.#.###.###.#.#.#.###N#.###.#.#.#.#########.#####.###.#.###.#
#.#.#.......#.#.#.....#...#.#...#.#.....#.#.#...#.#.#.#..p..#...#...#...#h..#.#.#
#.#.#.#########W#########.#.#.###.#####.###.#.###.#.#.#.###.#####.#B#########.#.#
#...#d....#...#.....#...#.#.....#.....#.#...#.#.#.#.#.#...#.#.....#.#.......#...#
###.#####.#.#.#####.#.#.###.#######.#.#.#.###.#.#.#.#.###.#.#.#####.#.#####.#.###
#...#...#...#.....#...#.V.#.#.....#.#.#.#.#...#z#.#...#...#.#...#.#...#.#.L.#.#.#
#.#####.#######.#########.###.###.###.#.#.#.###J#.#####.###.###.#.#####.#.###.#.#
#.............#...............#.....A.#.#.......#........o#.............#....u..#
#################################################################################
""".trimIndent()
}