#!/usr/bin/env python3
"""Reproduce the maps in 'three ways to dig a cave' with Python 3."""

import math
import random
from collections import deque

WIDTH, HEIGHT = 28, 15
DIRECTIONS = [(0, -1), (1, 0), (0, 1), (-1, 0)]


def border(x, y):
    return x in (0, WIDTH - 1) or y in (0, HEIGHT - 1)


def wall_map():
    return [["#"] * WIDTH for _ in range(HEIGHT)]


def random_walk():
    rng = random.Random(19)
    grid = wall_map()
    x, y = WIDTH // 2, HEIGHT // 2
    grid[y][x] = "."
    floors = 1
    snapshots = {}
    for _ in range(100000):
        dx, dy = rng.choice(DIRECTIONS)
        nx, ny = x + dx, y + dy
        if not (1 <= nx < WIDTH - 1 and 1 <= ny < HEIGHT - 1):
            continue
        x, y = nx, ny
        if grid[y][x] == ".":
            continue
        grid[y][x] = "."
        floors += 1
        if floors in (50, 140):
            snapshots[floors] = [row[:] for row in grid]
        if floors == 140:
            return snapshots
    raise RuntimeError("The digger did not reach its target")


def cellular_cave():
    rng = random.Random(13)
    grid = [["#" if border(x, y) or rng.random() < 0.45 else "."
             for x in range(WIDTH)] for y in range(HEIGHT)]
    initial = [row[:] for row in grid]
    for _ in range(5):
        following = wall_map()
        for y in range(1, HEIGHT - 1):
            for x in range(1, WIDTH - 1):
                walls = sum(grid[yy][xx] == "#"
                            for yy in range(y - 1, y + 2)
                            for xx in range(x - 1, x + 2))
                following[y][x] = "#" if walls >= 5 else "."
        grid = following
    return initial, grid


def value_noise():
    rng = random.Random(13)
    spacing = 5
    nodes = [[rng.random() for _ in range(math.ceil((WIDTH - 1) / spacing) + 1)]
             for _ in range(math.ceil((HEIGHT - 1) / spacing) + 1)]

    def smooth(t):
        return t * t * (3 - 2 * t)

    def lerp(a, b, t):
        return a + (b - a) * t

    field = []
    for y in range(HEIGHT):
        row = []
        for x in range(WIDTH):
            ix, iy = x // spacing, y // spacing
            tx, ty = smooth(x % spacing / spacing), smooth(y % spacing / spacing)
            top = lerp(nodes[iy][ix], nodes[iy][ix + 1], tx)
            bottom = lerp(nodes[iy + 1][ix], nodes[iy + 1][ix + 1], tx)
            row.append(lerp(top, bottom, ty))
        field.append(row)
    return field


def noise_cave(field, cutoff):
    return [["#" if border(x, y) or field[y][x] >= cutoff else "."
             for x in range(WIDTH)] for y in range(HEIGHT)]


def distances(grid, start):
    found = {start: 0}
    queue = deque([start])
    while queue:
        x, y = queue.popleft()
        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy
            if (0 <= nx < WIDTH and 0 <= ny < HEIGHT
                    and grid[ny][nx] != "#" and (nx, ny) not in found):
                found[nx, ny] = found[x, y] + 1
                queue.append((nx, ny))
    return found


def components(grid):
    unseen = {(x, y) for y in range(HEIGHT) for x in range(WIDTH)
              if grid[y][x] != "#"}
    groups = []
    while unseen:
        group = set(distances(grid, min(unseen)))
        groups.append(group)
        unseen -= group
    return sorted(groups, key=len, reverse=True)


def keep_largest(grid):
    groups = components(grid)
    if not groups:
        raise ValueError("The cave has no floor")
    kept = groups[0]
    result = [["." if (x, y) in kept else "#" for x in range(WIDTH)]
              for y in range(HEIGHT)]
    first = distances(result, min(kept))
    entrance = max(first, key=lambda p: (first[p], p))
    second = distances(result, entrance)
    exit_tile = max(second, key=lambda p: (second[p], p))
    result[entrance[1]][entrance[0]] = "<"
    result[exit_tile[1]][exit_tile[0]] = ">"
    return result


def examples():
    walk = random_walk()
    initial, smoothed = cellular_cave()
    noise = value_noise()
    return {
        "digger: 50 floor tiles": walk[50],
        "digger: 140 floor tiles": walk[140],
        "cellular: initial scatter": initial,
        "cellular: five passes": smoothed,
        "noise: floor below 0.45": noise_cave(noise, 0.45),
        "noise: floor below 0.60": noise_cave(noise, 0.60),
        "cellular: largest region, with stairs": keep_largest(smoothed),
    }


if __name__ == "__main__":
    for label, grid in examples().items():
        print(label)
        print("\n".join("".join(row) for row in grid))
        print()