aboutsummaryrefslogtreecommitdiff
path: root/Puzzle19.hs
blob: 522e3080dea0065303156cc96f645a286de01f3b (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import Data.Map (Map)
import qualified Data.Map as Map
import Data.List.Split (splitOn)
import Data.List (elemIndex)
import Data.Maybe (fromJust)

walk :: (Int, Int) -> (Int, Int) -> [Char] -> [Char]
walk (x, y) (x', y') xs
  | w == ' ' = xs
  | w == '|' || w == '-' = walk (x', y') (2 * x' - x, 2 * y' - y) xs
  | w `elem` alphabet = w:(walk (x', y') (2 * x' - x, 2 * y' - y) xs)
  | w == '+' = walk (x'', y'') (2 * x'' - x, 2 * y'' - y) xs
    where w = pmap Map.! (x, y)
          x1 = y' - y + x
          y1 = x' - x + y
          x2 = y - y' + x
          y2 = x - x' + y
          (x'', y'') = if Map.findWithDefault ' ' (x1, y1) pmap == ' '
                         then (x2, y2)
                         else (x1, y1)

walk' :: (Int, Int) -> (Int, Int) -> Int -> Int
walk' (x, y) (x', y') n
  | w == ' ' = n
  | w `elem` ("|-" ++ alphabet) = walk' (x', y') (2 * x' - x, 2 * y' - y) (n + 1)
  | w == '+' = walk' (x'', y'') (2 * x'' - x, 2 * y'' - y) (n + 1)
    where w = pmap Map.! (x, y)
          x1 = y' - y + x
          y1 = x' - x + y
          x2 = y - y' + x
          y2 = x - x' + y
          (x'', y'') = if Map.findWithDefault ' ' (x1, y1) pmap == ' '
                         then (x2, y2)
                         else (x1, y1)

alphabet :: [Char]
alphabet = ['A'..'Z']

solve1 = walk (0, y0) (1, y0) []
  where y0 = fromJust $ elemIndex '|' input

solve2 = walk' (0, y0) (1, y0) 0
  where y0 = fromJust $ elemIndex '|' input

pmap :: Map (Int, Int) Char
pmap = parseInput input

parseInput :: [Char] -> Map (Int, Int) Char
parseInput xs = mat2Map $ splitOn "\n" xs

mat2Map :: [[a]] -> Map (Int, Int) a
mat2Map xs = Map.fromList $ mconcat $ fmap f $ zipWith (,) [0 .. length xs - 1] xs
  where f (x, ys) = zipWith (,) ((\y -> (x,y)) <$> [0 .. length ys]) ys

input = input1

input0 = "     |          \n     |  +--+    \n     A  |  C    \n F---|----E|--+ \n     |  |  |  D \n     +B-+  +--+ "

input1 = "                                                               |                                                                                                                                         \n       +-------------------------------------------------------|-----------------------------+ +-------+ +-------+           +-+   +-------------------------------------------------------------+       \n       |                                                       |                             | |       | |       |           | |   |                                                             |       \n       |     +-------+                     +---------------+   |                     +-------|---------|-+       |         +-|-----------------------------------------+                         |       \n       |     |       |                     |               |   |                     |       | |       |         |         | | |   |                                   |                         |       \n       |     |       +---------------------|-----------------------------------------|-------|-----+   |         |         | +-|---+                         +-----------------------------------------+ \n       |     |                             |               |   |                     |       | |   |   |         |         |   |                             |         |                         |     | \n       |     | +---------------------------|---+ +-------+ +---|---+               +-|-------|-------------------------------+ |                             |         |                     +-+ |     | \n       |     | |                           |   | |       |     |   |               | |       | |   |   |         |         | | |                             |         |                     | | |     | \n   +---------|---------------------------------|---------|---------|---------------|---------------|---|-------------------|-|-------------------------------|-------+ |                     | | |     | \n   |   |     | |                           |   | |       |     |   |               | |       | |   |   |         |         | | |                             |       | |                     | | |     | \n   |   +-----|-------------------------------------------------|---|---------------------------|-------|-------------------------------------------------------------------------------+     | | |     | \n   |         | |                           |   | |       |     |   |               | |       | |   |   |         |         | | |                             |       | |               |     | | |     | \n   |         | |                           |   +---------|-----|---+               | |       | | +-----+         |     +---|-+ +-----------------------------|---------|---------------|-----|-----+   | \n   |         | |                           |     |       |     |                   | |       | | | |             |     |   |                                 |       | |               |     | | | |   | \n   |         | |                           |   +-+ +-----------|-----------+       | |       | | +-------------+ |     |   |                     +-------------------+ |               | +-----|---|---+ \n   |         | |                           |   |   |     |     |           |       | |       | |   |           | |     |   |                     |           |         |               | |   | | | |     \n   |         | |                       +-------|---|-----------|-----------|-------------------|---|-------------|-------------------------------|-----------|---------|---------------+ |   | | | |     \n   |         | |                       |   |   |   |     |     |           |       | |       | |   |           | |     |   |                     |           |         |                 |   | | | |     \n   |         | |                       |   |   |   +-----|-----------------|-----------------|-+   |           | |     |   |                     |           |         |                 |   | | | |     \n   |         | |                       |   |   |         |     |           |       | |       |     |           | |     |   |                     |           |         |                 |   | | | |     \n   |         | |                       |   |   |         |   +-+           |       | |       |     |           | |     |   |                     |           |         |                 |   | | | |     \n   |         | |                       |   |   |         |   |             |       | |       |     |           | |     |   |                     |           |         |                 |   | | | |     \n   |         | |                       |   |   |         |   |             |       | |       |     |           | |     |   |                     |           |         |   +-+           |   | | | |     \n   |         | |                       |   |   |         |   |             |       | |       |     |           | |     |   |                     |           |         |   | |           |   | | | |     \n   |         | |                       |   |   |         |   |             |       | |       |     |           | |     |   |   +-----------------|-----------|-----+   |   | |           |   | | | |     \n   |         | |                       |   |   |         |   |             |       | |       |     |           | |     |   |   |                 |           |     |   |   | |           |   | | | |     \n   +-+ +-------------------------------+   |   +---------|-----------------|-------|---------------------------|---------------|-------+         |           |     |   |   | |           |   | | | |     \n     | |     | |                           |             |   |             |       | |       |     |           | |     |   |   |       |         |           |     |   |   | |           |   | | | |     \n   +-|-|---+ | |         +---------------+ |   +-------------|-------------|---------+       |     |   +---------|---------|---|---------------+ |           |     |   |   | |     +-----|-------------+ \n   | | |   | | |         |               | |   |         |   |             |       |         |     |   |       | |     |   |   |       |       | |           |     |   |   | |     |     |   | | | |   | \n +-+ | |   +---------------------+       | |   | +-------------------------|-----------------+     |   |       | |     |   |   |       |       | |           |     |   |   | |     |     +---+ | | |   | \n |   | |     | |         |       |       | |   | |       |   |             |       |               |   |       | |     |   |   |       |       | |           |     |   |   | |     |           | | |   | \n | +-|-|-----------------|-----------------|---|-|-------|---|---------------------|---------------|---|-------|---------------------------------|-------------------+ |   | |     |           | | |   | \n | | | |     | |         |       |       | |   | |       |   |             |       |               |   |       | |     |   |   |       |       | |           |     | | |   | |     |           | | |   | \n | | | |     | |         |       |       | |   | +---------------------------------|-------+       |   |       | |     |   |   |       |       | |           |     | | |   | |     +-----------+ | |   | \n | | | |     | |         |       |       | |   |         |   |             |       |       |       |   |       | |     |   |   |       |       | |           |     | | |   | |                   | |   | \n | | | |     | |         |       |       | |   |         |   |             |       |       |   +---|-----------|-|-----+   |   |       +-------|-------------------+ | |   | |                   | |   | \n | | | |     | |         |       |       | |   |         |   |             |       |       |   |   |   |       | |         |   |               | |           |       | |   | |                   | |   | \n +-|-----+   | |         |     +-|-------|-----|-------------|-------------|---------------------------|-------|-----------|---|---------------|-|-----------------+ | |   | |                   | |   | \n   | | | |   | |         |     | |       | |   |         |   |             |       |       |   |   |   |       | |         |   |               | |           |     | | |   | |                   | |   | \n +-------+ +-|-|---+     |     | |       | |   |         |   |             |       |       |   |   |   |   +---|---------------|---------------|---------------+   | | |   | |                   | |   | \n | | | |   | | |   |     |     | |       | |   |         |   |             |       |       |   |   |   |   |   | |         |   |               | |           | |   | | |   | |                   | |   | \n | +-|-|-+ | | |   |     |     | +-------|-|---|-------+ |   |             |       |       |   |   |   |   |   | |         |   |               | |           | |   | | |   | |                   | |   | \n |   | | | | | |   |     |     |         | |   |       | |   |             |       |       |   |   |   |   |   | |         |   |               | |           | |   | | |   | |                   | |   | \n | +---|---|-|-+ +-------|-----|-----------|---|-------------|-------------|---------------|-----------|-------|-|-------------|-----------+   | | +-------------------|-----|-+                 | |   | \n | | | | | | |   | |     |     |         | |   |       | |   |             |       |       |   |   |   |   |   | |         |   |           |   | | |         | |   | | |   | | |                 | |   | \n | +-+ | | +-|-----|-----------|---------|-|---|-------+ |   |       +---------+   |       |   |   |   |   |   | |         |   +-----------|-----|-----------------|-----------|-+               | |   | \n |     | |   |   | |     |     |         | |   |         |   |       |     |   |   |       |   |   |   |   |   | |         |               |   | | |         | |   | | |   | | | |               | |   | \n |     | | +-----|-------------|---------|-----|---------------------------|-----------------------|-------|-----------------------------+ |   | | |         | |   | | |   | | | |               | |   | \n |     | | | |   | |     |     |         | |   |         |   |       |     |   |   |       |   |   |   |   |   | |         |             | |   | | |         | |   | | |   | | | |               | |   | \n |     | | | |   | |     |     |         | |   +---------|---|-------+     |   |   |       |   |   |   |   |   | |         |             | |   | | |     +---+ |   | | |   | | | |               | |   | \n |     | | | |   | |     |     |         | |             |   |             |   |   |       |   |   |   |   |   | |         |             | |   | | |     |     |   | | |   | | | |               | |   | \n +---+ | | | +---|-|-----|-----|-------------------------|---|-------------|-------|-------|-------|---|-------|-|---------|-------------|-|---|---|---+ |     |   | | |   | | | |               | |   | \n     | | | |     | |     |     |         | |             |   |             |   |   |       |   |   |   |   |   | |         |             | |   | | |   | |     |   | | |   | | | |               | |   | \n     | | | |     | |     |     |         | |             | +---------------|---|-------------------|-----------+ |         |             | |   | | |   | |     |   | | |   | | | |       +---+   | |   | \n     | | | |     | |     |     |         | |             | | |             |   |   |       |   |   |   |   |     |         |             | |   | | |   | |     |   | | |   | | | |       |   |   | |   | \n     | | | |   +---------|-----|---------|-----------------|-|---------+   |   |   |       |   |   |   |   |     |         |             | |   | | |   | |     |   | | |   | | | |       |   |   | |   | \n     | | | |   | | |     |     |         | |             | | |         |   |   |   |       |   |   |   |   |     |         |             | |   | | |   | |     |   | | |   | | | |       |   |   | |   | \n     | | | |   +-|-|-----------|---------|---------------+ +-|---+ +-------+   |   |       |   |   |   |   |     |         |             | |   | | |   | |     |   | | |   | | | |       |   |   | |   | \n     | | | |     | |     |     |         | |                 |   | |   |       |   |       |   |   |   |   |     |         |             | |   | | |   | |     |   | | |   | | | |       |   |   | |   | \n     | | | |     | |     |     |         | |                 |   | |   |     +-------------|-------|---|---------|---------|-------------|-|---|-|-|-----------|---|-------+ | | +-------|---|---|-|---+ \n     | | | |     | |     |     |         | |                 |   | |   |     | |   |       |   |   |   |   |     |         |             | |   | | |   | |     |   | | |     | |         |   |   | |     \n     | | | |     | |     |     |         | |                 |   | |   |     | |   |       |   |   |   +-----------------------------------|---|-|---------------+ | | |     | |         |   |   | |     \n     | | | |     | |     |     |         | |                 |   | |   |     | |   |       |   |   |       |     |         |             | |   | | |   | |     | | | | |     | |         |   |   | |     \n     | | | |   +-|-|-----------|-------+ | |                 |   | | +-|-----|-----------------|---|-------|-----|---------|-------------|-|---|---|---|-----------|-|-|-----|-------------+ |   | |     \n     | | | |   | | |     |     |       | | |                 |   | | | |     | |   |       |   |   |       |     |         |             | |   | | |   | |     | | | | |     | |         | | |   | |     \n     | | | |   | | |     |     |       | | |                 |   | | | | +-------+ |       |   |   |       |     |         |             | |   | | |   | |     | | +---|-----|-|---+     | | |   | |     \n     | | | |   | | |     |     |       | | |                 |   | | | | |   | | | |       |   |   |       |     |         |             | |   | | |   | |     | |   | |     | |   |     | | |   | |     \n     | | | |   | | |     |     |       | | |                 | +---+ +---|---|---|---------|---+   |       |     |         |             | |   | | |   | |     | |   | |     | |   |     | | |   | |     \n     | | | |   | | |     |     |       | | |                 | | |     | |   | | | |       |       |       |     |         |             | |   | | |   | |     | |   | |     | |   |     | | |   | |     \n     | | | |   | | |   +-|-----------------|-----------------|-|-----+ | |   | | | |       |       |       |     |         |             | |   | | |   | |     | |   | |     | |   |     | | |   | |     \n     | | | |   | | |   | |     |       | | |                 | | |   | | |   | | | |       |       |       |     |         |             | |   | | |   | |     | |   | |     | |   |     | | |   | |     \n     | | | |   | | |   +-|-------+     +---|-----------------|---|-+ | | |   | | | | +-----|-------|-------------|---------|-------------|-|-----|-|-----|---+ | |   | |     | |   |     | | |   | |     \n     | | | |   | | |     |     | |       | |                 | | | | | | |   | | | | |     |       |       |     |         |             | |   | | |   | |   | | |   | |     | |   |     | | |   | |     \n     | | | | +-|---|-------------------+ | |             +-------+ | | | |   | | | | | +---|---------------------|---------|-------------|-|---|---|---+ |   | | |   | |     | |   |     | | |   | |     \n     | | | | | | | |     |     | |     | | |             |   | |   | | | |   | | | | | |   |       |       |     |         |             | |   | | |     |   | | |   | |     | |   |     | | |   | |     \n     | | | | | | | |   +-+     | |   +-|---|-------------|---|-----|-|-|-|---|-|---|-|-|---|-------+       |     |         |             | |   | | |     |   | | |   | |     | |   |     | | |   | |     \n     | | | | | | | |   |       | |   | | | |             |   | |   | | | |   | | | | | |   |               |     |         |             | |   | | |     |   | | |   | |     | |   |     | | |   | |     \n     | | | | | | | |   +---------|-------|-|-------------|-----+   | | | |   | | | | | |   |               |     |         |             | |   | | |     |   | | |   | |     | |   |     | | |   | |     \n     | | | | | | | |           | |   | | | |             |   |     | | | |   | | | | | |   |               |     |         |             | |   | | |     |   | | |   | |     | |   |     | | |   | |     \n     | | | | | | | |           | |   | | | |             |   |     | | +-|-------|-|-----------------------|---+ |         |       +---------------|---------|-|-|-----------|-----|-----|-|-|-----|---+ \n     | | | | | | | |           | |   | | | |             |   |     | |   |   | | | | | |   |               |   | |         |       |     | |   | | |     |   | | |   | |     | |   |     | | |   | |   | \n   +-|---------|-|-------------------|-----|-------------|---|-----|-|---|-----|-|-----|-------------------|---|-|---------|-------------------|-|-+     |   +---------|-------|-+ |     | | |   | |   | \n   | | | | | | | | |           | |   | | | |             |   |     | |   |   | | | | | |   |               |   | |         |       |     | |   | |       |     | |   | |     | | | |     | | |   | |   | \n   | | | | | | | | |           | |   | | | |             |   |     | | +-----|---|-|-----+ |               |   | |         |       |     | |   | |       |     | |   | | +-----|-+ |     | | |   | |   | \n   | | | | | | | | |           | |   | | | |             |   |     | | | |   | | | | | | | |               |   | |         |       |     | |   | |       |     | |   | | |   | |   |     | | |   | |   | \n   | | | | | | | | |           | |   | | | |             |   |     | | | |   | | | +---|-|-|---------------------------------------------------|-----------+   | |   | | |   | |   |     | | |   | |   | \n   | | | | | | | | |           | |   | | | |             |   |     | | | |   | | |   | | | |               |   | |         |       |     | |   | |       | |   | |   | | |   | |   |     | | |   | |   | \n   | | | | | | | | |           | |   | | | |             |   |     | | | |   | | |   | | | |               |   | |         |       |     | |   | | +-+   | |   | |   | | |   | |   |     | | |   | |   | \n   | | | | | | | | |           | |   | | | |             |   |     | | | |   | | |   | | | |               |   | |         |       |     | |   | | | |   | |   | |   | | |   | |   |     | | |   | |   | \n   | | | | | | | | |   +---------|---|-|-|-+             |   |     | | | |   | | |   | | | |               |   | |         |       |     | |   | | | |   | |   | |   | | |   | |   |     | | |   | |   | \n   | | | | | | | | |   |       | |   | | |               |   |     | | | |   | | |   | | | |               |   | |         |       |     | |   | | | |   | |   | |   | | |   | |   |     | | |   | |   | \n   | | | | | | +---|---|-------------|-|---------------------|-------|-|-|---|---|---|---------------------|---|-----------|-------|-----|-|-----|-+ |   +-|-+ | |   | | |   | |   |     | | |   | |   | \n   | | | | | |   | |   |       | |   | | |               |   |     | | | |   | | |   | | | |               |   | |         |       |     | |   | |   |     | | | |   | | |   | |   |     | | |   | |   | \n   | | | | | |   | | +-------+ +-----|-|-----------------------+   | | | |   | | |   | | | |               |   | +---------|-------------|-----|-|-----------|---|-+ | | |   | |   |     | | | +-----+ | \n   | | | | | |   | | | |     |   A   | | |               |   | |   | | | |   | | |   | | | |               |   |           |       |     | |   | |   |     | | | | | | | |   | |   |     | | | | | | | | \n   | | | | | |   | | | |     |   |   +-|-----------------|-----|-------|-|-------|---|-|---|-------------------|-----------|-------|-----|-----------|-------|-----|-|-|-----|-----------|---------|-+ | \n   | | | | | |   | | | |     |   |     | |               |   | |   | | | |   | | |   | | | |               |   |           |       |     | |   | |   |     | | | | | | | |   | |   |     | | | | | |   | \n   | | | | | |   +-|---------|---|-------|-------------------|---------|-|---|-|-----|---+ |               |   |           |       |     | |   | | +-------|-+ | | | | | |   | |   |     | | | | | |   | \n   | | | | | |     | | |     |   |     | |               |   | |   | | | |   | | |   | |   |               |   |           |       |     | |   | | | |     |   | | | | | |   | |   |     | | | | | |   | \n   | | | | | |     | | |     |   |     | |               |   | |   | | | |   | | |   | |   |               | +-|---------------------------|-------|-|-----+ +-----+ | | |   | | +-------|-----|-|-|-+ | \n   | | | | | |     | | |     |   |     | |               |   | |   | | | |   | | |   | |   |               | | |           |       |     | |   | | | |       | | |   | | |   | | | |     | | | | | | | | \n   | | | | | |     | +-|-+   +---------|-|-------------------|-|---|---|-|---|---------|---------------------|-------------|-------|-----|-------|-|---------+ | |   | | |   | | | |     | | | | | | | | \n   | | | | | |     |   | |       |     | |               |   | |   | | | |   | | |   | |   |               | | |           |       |     | |   | | | |         | |   | | |   | | | |     | | | | | | | | \n   | | | | | |     |   | |       |     | |               |   | |   | | | |   | | |   | |   |               | | |           |       |     | |   | | | |   +-------|---|-----+ | | | |     | | | | | | | | \n   | | | | | |     |   | |       |     | |               |   | |   | | | |   | | |   | |   |               | | |           |       |     | |   | | | |   |     | |   | | | | | | | |     | | | | | X | | \n   | | | | | |     |   | |       |     | |               |   | |   | | | |   | | |   | |   | +---------------|-|-------------------|-----------|---+ |   |     | |   | | | | | | | |     | | | | | | | | \n   | | | | | |     |   | |       |     | |               |   | |   | | | |   | | |   | |   | |             | | |           |       |     | |   | |   |   |     | |   | | | | | | | |     | | | | | | | | \n   | | | | | |     |   | |       |     | |               +---|-|-----|---|-----------|-|-------------------------------------------|-------------|-------------|-----|-|-+ | | | | |     | | | | | | | | \n   | | | | | |     |   | |       |     | |                   | |   | | | |   | | |   | |   | |             | | |           |       |     | |   | |   |   |     | |   | |   | | | | |     | | | | | | | | \n +-|---------|-----------------+ |     | |                   | |   | | | |   | | |   | |   | |             | | |           |       |     | |   | |   |   |     | |   | |   | | | | |     | | | | | | | | \n | | | | | | |     |   | |     | |     | |                   | |   | | | |   | | |   | |   | |             | | |           |       |     | |   | |   |   |     | |   | |   | | | | |     | | | | | | | | \n | | | | | | |     |   | |     | |     | |                   | |   | | | |   | | |   | |   | |             | | | +---------|-------|-----|-|-+ | |   |   |     | |   | |   | | | | |     | | | | | | | | \n | | | | | | |     |   | |     | |     | |                   | |   | | | |   | | |   | |   | |             | | | |         |       |     | | | | |   |   |     | |   | |   | | | | |     | | | | | | | | \n | | | | | | |     |   | |     | |     | |                   | |   | | | |   | | |   | |   | |             | | | |         |     +-|-------|---|-----|---|-----------|-----+ | | | |     | | | | | | | | \n | | | | | | |     |   | |     | |     | |                   | |   | | | |   | | |   | |   | |             | | | |         |     | |     | | | | |   |   |     | |   | |     | | | |     | | | | | | | | \n | | | +-----------|---|-|-----|-|-----|---------------------------|-|-|-|---|-|-|---|-------|-----------------|-|---------|-----|-------+ | | | |   |   |   +-------|-----+ | | | |     | | | | | | | | \n | | |   | | |     |   | |     | |     | |                   | |   | | | |   | | |   | |   | |             | | | |         |     | |       | | | |   |   |   | | |   | |   | | | | |     | | | | | | | | \n +-------|-|---------------------|---------------------------------|-----|---|-|-----|-----|-+             | | | |         |     | |     +---|-+ +---+   |   | +-|---|-----|---|---|-+   | | | | | | | | \n   | |   | | |     |   | |     | |     | |                   | |   | | | |   | | |   | |   |               | | | |         |     | |     | | |           |   |   |   | |   | | | | | |   | | | | | | | | \n   | |   | | |     |   | |     | |     | | +-+           +---|-|---+ | | | +-|---+   | |   |               | | | |         |     | |     | | |         +-|---|---|---------|---|-----+   | | | | | | | | \n   | |   | | |     |   | |     | |     | | | |           |   | |     | | | | | |     | |   |               | | | |         |     | |     | | |         | |   |   |   | |   | | | | |     | | | | | | | | \n   +-|-----|-|-----|---|-|-------------|-|-------------+ |   | |     | | | | | |     | |   |   +-----------|-|-------------|-----------------|---------|-|-------|---|-----|-+ | | +-+   | | | | | | | | \n     |   | | |     |   | |     | |     | | | |         | |   | |     | | | | | |     | |   |   |           | | | |         |     | |     | | |         | |   |   |   | |   |   | |   |   | | | | | | | | \n     |   | | |     |   | |   +-|-------+ | | |         | |   | |     | | | | | +-----|-|-------|-----------|-|-------------------|-|-------|-----------+ |   |   |   | |   |   | |   |   | | | | | | | | \n     |   | | |     |   | |   | | |       | | |         | |   | |     | | | | |       | |   |   |           | | | |         |     | |     | | |           |   |   |   | |   |   | |   |   | | | | | | | | \n +-+ |   +---------|-----|---|-----------|---|-----------|---|-|-----------|-|-------|---------|-----+     | | | |         |     | |     | | |           |   |   +---|-|---|---------+   | | | | | | | | \n | | |     | |     |   | |   | | |       | | |         | |   | |     | | | | |       | |   |   |     |     | | | |         |     | |     | | |           |   |       | |   |   | |       | | | | | | | | \n +---|-----|-----+ |   | |   | | |       | | |         | |   | |     | | | | +-------|-------------+ |     | | | |         |     | |     | | |           |   |       | |   |   | |       | | | | | | | | \n   | |     | |   | |   | |   | | |       | | |         | |   | |     | | | |         | |   |   |   | |     | | | |         |     | |     | | |           |   |       | |   |   | |       | | | | | | | | \n +---|-----------------|-----|-|-----------|-----------|-|---|-------|---|-|---------|-|-----------|-------------|---------------|-|-----|-|-------------|-----------+ |   |   | |       | | | | | | | | \n | | |     | |   | |   | |   | | |       | | |         | |   | |     | | | |         | |   |   |   | |     | | | |         |     | |     | | |           |   |         |   |   | |       | | | | | | | | \n | | |     | |   | |   | |   | | |       | | |         | |   +-------|-+ | |         | +---|---------+     | | | |         |     | |     | | |         +-|-----------------------|-----------|---|---+ | \n | | |     | |   | |   | |   | | |       | | |         | |     |     |   | |         |     |   |   |       | | | |         |     | |     | | |         | |   |         |   |   | |       | | | | | |   | \n +-|-|-------|-----|---|-----|---|-------|-|-----------|-------------|---|-----------------|---------------|-|-|-----+     |     | |     | +-----------|-+   |         | +-|---------+   | | | | | |   | \n   | |     | |   | |   | |   | | |       | | |         | |     |     |   | |         |     |   |   |       | | | |   |     |     | |     |   |         |     |         | | |   | |   |   | | | | | |   | \n   | |   +-|-----|-----+ |   | | |       | | |         | |     |     |   | |       +-|-------------|------------Z|---|-----------------------+         |     |         | | |   | |   |   | | | | | |   | \n   | |   | | |   | |     |   | | |       | | |         | |     |     |   | |       | |     |   |   |       | | | |   |     |     | |     |             |     |         | | |   | |   |   | | | | | |   | \n   | |   | | |   | |     | +-+ | +-----------------------------|-----|-----|---------------|---|---------------|-----+     |     | +-------------------|-----------------|-|---|-|-------|-|-+ | | |   | \n   | |   | | |   | |     | |   |         | | |         | |     |     |   | |       | |     |   |   |       | | | |         |     |       |             |     |         | | |   | |   |   | |   | | |   | \n +-|-+   | | |   | |     | |   | +---------------------+ |     |     |   | |       | |     |   +---|-------|-|-------------|-------------|-------------|-----|-------------|-----|-----+ | |   | | |   | \n | |     | | |   | |     | |   | |       | | |           |     |     |   | |       | |     |       |       | | | |         |     |       |             |     |         | | |   | |   | | | |   | | |   | \n | |     | | |   | |     | |   | |   +---|-+ |           |     |     |   | |       | |     |       |       | | | |         |     |       |             |     |         | | |   | |   | | | |   | | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |     |   | |       | |     |       |       | | | |         |     |       |             |     |         | | |   | |   | | | |   | | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |     +---|---------|-|-------------|---------|-|-|-------------------------------------|-----|---+     | | |   | +-----|-------+ | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |         | |       | |     |       |       | | | |         |     |       |             |     |   |     | | |   |     | | | |     | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |         | |       | |     |       |       | | | |         |     |       |             |     |   |     +-------|-----+ +-------+ | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |         | |       | |     |       |       | | | |         |     |       |             |     |   |       | |   |         | |   | | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |         | |       | |     |       |       | | | |         |     |       |             |     |   |       | |   |         | |   | | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |         | |       | |     |       |       | | | |         |     |       |             |     |   |       | |   |         | |   | | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |         | |       | |     |       |       | | | |         |     |       |             |     |   |       | |   |         | |   | | |   | \n | |     | | |   | |     | |   | |   |   |   |           |     |         | |       | |     |       |       | | | |         |     |       |             |     |   |       | |   |         | |   | | |   | \n | +-----+ | |   | |     | +---|-----|-------|---------------------------|-+       | |     |       |       | | | |         |     |       |             |     |   |       | |   |         | |   | | |   | \n |         | |   | |     |     | |   |   |   |           |     |         |         | |     |       |       | | | |         |     |       |             |     |   |       | |   |         | |   | | |   | \n | +---------|-----|-----|-----|-+   |   |   |           |     +---------------------------|-------|-------|-|-|-----+     |     |       |             |     |   |       | |   |         | |   | | |   | \n | |       | |   | |     |     |     |   |   |           |               |         | |     |       |       | | | |   |     |     |       |             |     |   |       | |   |         | |   | | |   | \n | |       | |   | |     |     |     |   |   |           |               |         | |     |       |       | | | |   |     |     |       +-------------|--I--------+     | |   |         | |   | | |   | \n | |       | |   | |     |     |     |   |   |           |               |         | |     |       |       | | | |   |     |     |                     |     |   | |     | |   |         | |   | | |   | \n | |       | |   | |     |     |     |   |   |         +-----------------+         | |     |       |       | | | |   |     |     |                     |     |   | |     | |   |         | |   | | |   | \n | |       | |   | |     |     |     |   |   |         | |                         | |     |       |       | | | |   |     |     |                     |     |   | |     | |   |         | |   | | |   | \n | |       | |   | |     | +---|-------------------------|---------------------------|-----|---+   |       | | | |   |     |     |                     |     |   | |     | +-+ |     +-+ | |   | | |   | \n | |       | |   | |     | |   |     |   |   |         | |                         | |     |   |   |       | | | |   |     |     |                     |     |   | |     |   | |     | | | |   | | |   | \n | |       | |   | |     | |   |     |   | +-|---------|-|---------------------------|-----|---+   |       | | | |   |     |     |                     |     |   +-----------|-|-----+ | | |   | | |   | \n | |       | |   | |     | |   |     |   | | |         | |                         | |     |       |       | | | |   |     |     |                     |     |     |     |   | |       | | |   | | |   | \n +-|-------------|---------|---------|---|-|-|---------|-|---------------------------------|-------|-------|-|-------------------------------------+ +-|-----|---------------|-|---+   | | |   | | |   | \n   |       | |   | |     | |   |     |   | | |         | |                         | |     |       |       | | | |   |     |     |                 | | |     |     |     |   | |   |   | | |   | | |   | \n   |       | |   | |     | |   |     |   +---+         | +---------------------------------|---------------|-----------------------------------+   +-|-----------------------------+   | | |   | | |   | \n   |       | |   | |     | |   |     |     |           |                           | |     |       |       | | | |   |     |     |             |     | |     |     |     |   | |       | | |   | | |   | \n   |       | +-+ +-------------------|-----|---------------+                       | |     |   +---|-------|-|---|---|-----------|-------------|-----|-+     |   +-+     |   | |       | | |   | | |   | \n   |       |   |   |     | |   |     |     |           |   |                       | |     |   |   |       | | | |   |     |     |             |     |       |   |       |   | |       | | |   | | |   | \n   |       |   |   +-----+ +---------|-----------------|---|-----------------------+ |     |   |   +-----------|-|---|-------------------------------|-------|-----------|-------------+ | |   | | |   | \n   |       |   |               |     |     |           |   |                         |     |   |           | | | |   |     |     |             |     |       |   |       |   | |         | |   | | |   | \n   +-------|---|---------------------------|---------------------------------------------------|---------------|-|---|-----------|-------------+     |       |   |       |   | |         | |   | | |   | \n           |   |               |     |     |           |   |                         |     |   |           | | | |   |     |     |                   |       |   |       |   | |         | |   | | |   | \n           +-------------------|-----|-----|---------------|-----------------------------------|-------------|-------------------|-------------------|-------|---------------|-|---------|-----|-+ |   | \n               |               |     |     |           |   |                         |     |   |           | | | |   |     |     |                   |       |   |       |   | |         | |   |   |   | \n               |         +-----------------|-----------+   |                         |     |   |           | | | |   |     |     |                   +-------|---|-----------------+     | |   |   |   | \n               |         |     |     |     |               |                         |     |   |           | | | |   |     |     |                           |   |       |   | |   |     | |   |   |   | \n               |         +-----------|U----|---------------+                         |     |   |           | | | |   |     |     |                           |   |       +-----|---|-------|---|-------+ \n               |               |     |     |                                         |     |   |           | | | |   |     |     |                           |   |           | |   |     | |   |   |     \n             +-|---------------------|-----------------------------------------------|-+   |   |           | | | |   |     |     |                           |   |           | |   |     | |   |   |     \n             | |               |     |     |                                         | |   |   |           | | | |   |     |     |                           |   |           | |   |     | |   |   |     \n             | |               |     |     |                                         | |   |   |           | | | |   |     |     |                         +-----+           | |   |     | |   |   |     \n             | |               |     |     |                                         | |   |   |           | | | |   |     |     |                         | |               | |   |     | |   |   |     \n             | |               |     |     |           +-----------------------------|-----|---|--------S--|-|---|---------------|---------------------------|---------------+ | +-+     +-|-------+     \n             | |               |     |     |           |                             | |   |   |           | | | |   |     |     |                         | |                 | |         |   |         \n             | |               |     |     |           |                             | |   |   |           | +-------------+     +---------------------------+               +---+         |   |         \n             | |               |     |     |           |                             | |   |   |           |   | |   |                                     |                 | |           |   |         \n             | |               |     |     |         +-|-----------------------------|-----|---|-----------|-----|-------------------------------------------+     +---------|-|-----------------------+ \n             | |               |     |     |         | |                             | |   |   |           |   | |   |                                     | |     |         B |           |   |       | \n   +---------|-|---------------------|-----------------------------------------------|-+   | +-----------------------|---------------------------------------------|-----------------+     |   |       | \n   |         | |               |     |     |         | |                             |     | | |           |   | |   |                                     | |     |         | |     |     |   |       | \n Y +---------|-----------------------+     +-----------------------------------------+     +-|-------------|-----|---|---------------------------------------|-----|-----+ +-+ +-+   |     |   |       | \n |           | |               |                     | |                                     | |           |   | |   |                                     | |     |     | |     |   |     |   |       | \n |           | |               |   +-----------------+ +-------------------------------------+ |           |   +-+   +-------------------------------------|-|-------------|-----|-------+ |   |       | \n |           | |               |   |                                                           |           |                                               | |     |     | |     |   |   | |   |       | \n |       +---+ |               |   |                                                           +--------------------------------------------W----------------|-----|-----+ +-----+   +-----+   +-------+ \n |       |     |               |   |                                                                       |                                               | |     |                     |               \n +-------+     +---------------+   +-----------------------------------------------------------------------+                                               +-+     +---------------------+               \n                                                                                                                                                                                                         "