Day 9 Part 1

4 files changed, 2169 insertions, 0 deletions

diff --git a/Day9/CHANGELOG.md b/Day9/CHANGELOG.md
new file mode 100644
index 0000000..a9461e3
--- /dev/null
+++ b/Day9/CHANGELOG.md
@@ -0,0 +1,5 @@
+# Revision history for Day9
+
+## 0.1.0.0 -- YYYY-mm-dd
+
+* First version. Released on an unsuspecting world.
diff --git a/Day9/Day9.cabal b/Day9/Day9.cabal
new file mode 100644
index 0000000..d4161a1
--- /dev/null
+++ b/Day9/Day9.cabal
@@ -0,0 +1,35 @@
+cabal-version:      2.4
+name:               Day9
+version:            0.1.0.0
+
+-- A short (one-line) description of the package.
+-- synopsis:
+
+-- A longer description of the package.
+-- description:
+
+-- A URL where users can report bugs.
+-- bug-reports:
+
+-- The license under which the package is released.
+-- license:
+author:             Andreas Grois
+maintainer:         andi@grois.info
+
+-- A copyright notice.
+-- copyright:
+-- category:
+extra-source-files: CHANGELOG.md
+
+executable Day9
+    main-is:          Main.hs
+
+    -- Modules included in this executable, other than Main.
+    -- other-modules:
+
+    -- LANGUAGE extensions used by modules in this package.
+    -- other-extensions:
+    build-depends:    base ^>=4.16.3.0,
+                      containers
+    hs-source-dirs:   app
+    default-language: Haskell2010
diff --git a/Day9/app/Main.hs b/Day9/app/Main.hs
new file mode 100644
index 0000000..59c797c
--- /dev/null
+++ b/Day9/app/Main.hs
@@ -0,0 +1,129 @@
+module Main (main) where
+
+import System.Environment ( getArgs )
+import Text.Read (readMaybe)
+import Data.Bifunctor (bimap)
+import Data.Maybe (fromMaybe)
+import qualified Data.Set as Set
+import Control.Monad.Zip (MonadZip(mzip))
+import Control.Exception (assert)
+
+main :: IO ()
+main = getArgs >>= readFile . head >>= print . solveDay9
+
+solveDay9 :: String -> String
+solveDay9 = formatDay9Result . fmap solveDay9Parts . parseDay9Input
+
+formatDay9Result :: Maybe (Int, Int) -> String
+formatDay9Result Nothing = "Failed to read input for day9."
+formatDay9Result (Just (p1, p2)) = "Part 1: " ++ show p1 ++ ", Part 2: " ++ show p2
+
+-- Imho it's stupid that Haskell by default imports Right and Left.
+-- Also, that there's no dedicated Result type, and rather Either is used.
+data Direction = MoveUp | MoveRight | MoveDown | MoveLeft
+
+data MultiCommand = MultiCommand Direction Word -- using Word here gives a "is >= 0" check in readMaybe for free (I think).
+newtype Command = Command Direction
+
+parseDay9Input :: String -> Maybe [MultiCommand]
+parseDay9Input = mapM readInputLine . lines
+
+readInputLine :: String -> Maybe MultiCommand
+readInputLine ('U':' ':n) = MultiCommand MoveUp <$> readMaybe n
+readInputLine ('R':' ':n) = MultiCommand MoveRight <$> readMaybe n
+readInputLine ('D':' ':n) = MultiCommand MoveDown <$> readMaybe n
+readInputLine ('L':' ':n) = MultiCommand MoveLeft <$> readMaybe n
+readInputLine _ = Nothing
+
+solveDay9Parts :: [MultiCommand] -> (Int, Int)
+solveDay9Parts =  bimap solveDay9Part1 solveDay9Part2 . dup . unMultiCommands
+    where dup a = (a,a)
+
+unMultiCommands :: [MultiCommand] -> [Command]
+unMultiCommands = concatMap unMultiCommand
+
+unMultiCommand :: MultiCommand -> [Command]
+unMultiCommand (MultiCommand _ 0) = []
+unMultiCommand (MultiCommand d n) = Command d:unMultiCommand (MultiCommand d (n-1))
+
+data AllowedRelativeOffset = MinusOne | Zero | PlusOne
+newtype RelativeTail = RelativeTail (AllowedRelativeOffset, AllowedRelativeOffset)
+newtype AbsoluteHead = AbsoluteHead (Int, Int)
+newtype AbsoluteTail = AbsoluteTail (Int, Int) deriving (Eq, Ord)
+
+data RopePosition = RopePosition AbsoluteHead RelativeTail
+startingRopePosition :: RopePosition
+startingRopePosition = RopePosition (AbsoluteHead (0,0)) (RelativeTail (Zero, Zero))
+
+solveDay9Part1 :: [Command] -> Int
+solveDay9Part1 = length . Set.fromList . tailPositions . ropePositions -- building a set is cheaper than making sure every element in the list is unique.
+
+tailPositions :: [RopePosition] -> [AbsoluteTail]
+tailPositions = map tailPosition
+    where tailPosition (RopePosition (AbsoluteHead (x,y)) (RelativeTail (dx, dy))) = AbsoluteTail (applyOffset x dx, applyOffset y dy)
+          applyOffset i MinusOne = i-1
+          applyOffset i Zero = i
+          applyOffset i PlusOne = i+1
+
+ropePositions :: [Command] -> [RopePosition]
+ropePositions = scanl applyCommand startingRopePosition -- this could also be `tail . scanl applyCommand startingRopePosition` but that would ignore starting pos.
+
+data VirtualRelativeOffset = VMinusTwo | VMinusOne | VZero | VPlusOne | VPlusTwo
+newtype VirtualRelativeTail = VirtualRelativeTail (VirtualRelativeOffset, VirtualRelativeOffset)
+
+-- Where, after applying the command to the head, the tail would be if it weren't connected.
+virtualizeRelativeTail :: RelativeTail -> Command -> VirtualRelativeTail
+virtualizeRelativeTail (RelativeTail (x,y)) (Command MoveUp) = VirtualRelativeTail (virtualFromRelativeOffset x, decrementOffset y)
+virtualizeRelativeTail (RelativeTail (x,y)) (Command MoveDown) = VirtualRelativeTail (virtualFromRelativeOffset x, incrementOffset y)
+virtualizeRelativeTail (RelativeTail (x,y)) (Command MoveRight) = VirtualRelativeTail (decrementOffset x, virtualFromRelativeOffset y)
+virtualizeRelativeTail (RelativeTail (x,y)) (Command MoveLeft) = VirtualRelativeTail (incrementOffset x, virtualFromRelativeOffset y)
+
+-- Makes the tail realize it's still connected to the head.
+realizeVirtualTail :: VirtualRelativeTail -> RelativeTail
+realizeVirtualTail v = fromMaybe (realizeVirtualTailByMoving v) (tryRealizeVirtualTailWithoutMoving v)
+
+tryRealizeVirtualTailWithoutMoving :: VirtualRelativeTail -> Maybe RelativeTail
+tryRealizeVirtualTailWithoutMoving (VirtualRelativeTail (x,y)) = RelativeTail <$> mzip (tryRealizeOffsetWithoutMoving x) (tryRealizeOffsetWithoutMoving y)
+
+tryRealizeOffsetWithoutMoving :: VirtualRelativeOffset -> Maybe AllowedRelativeOffset
+tryRealizeOffsetWithoutMoving VMinusOne = Just MinusOne
+tryRealizeOffsetWithoutMoving VZero = Just Zero
+tryRealizeOffsetWithoutMoving VPlusOne = Just PlusOne
+tryRealizeOffsetWithoutMoving _ = Nothing
+
+realizeVirtualTailByMoving :: VirtualRelativeTail -> RelativeTail
+realizeVirtualTailByMoving (VirtualRelativeTail (x,y)) = RelativeTail (moveOffsetTowardsZero x, moveOffsetTowardsZero y)
+
+moveOffsetTowardsZero :: VirtualRelativeOffset -> AllowedRelativeOffset
+moveOffsetTowardsZero VMinusTwo = MinusOne
+moveOffsetTowardsZero VMinusOne = Zero
+moveOffsetTowardsZero VZero = Zero
+moveOffsetTowardsZero VPlusOne = Zero
+moveOffsetTowardsZero vPlusTwo = PlusOne
+
+virtualFromRelativeOffset :: AllowedRelativeOffset -> VirtualRelativeOffset
+virtualFromRelativeOffset MinusOne = VMinusOne
+virtualFromRelativeOffset Zero = VZero
+virtualFromRelativeOffset PlusOne = VPlusOne
+
+decrementOffset :: AllowedRelativeOffset -> VirtualRelativeOffset
+decrementOffset MinusOne = VMinusTwo
+decrementOffset Zero = VMinusOne
+decrementOffset PlusOne = VZero
+
+incrementOffset :: AllowedRelativeOffset -> VirtualRelativeOffset
+incrementOffset MinusOne = VZero
+incrementOffset Zero = VPlusOne
+incrementOffset PlusOne = VPlusTwo
+
+applyCommandToAbsoluteHead :: AbsoluteHead -> Command -> AbsoluteHead
+applyCommandToAbsoluteHead (AbsoluteHead (x,y)) (Command MoveUp) = AbsoluteHead (x,y+1)
+applyCommandToAbsoluteHead (AbsoluteHead (x,y)) (Command MoveDown) = AbsoluteHead (x,y-1)
+applyCommandToAbsoluteHead (AbsoluteHead (x,y)) (Command MoveRight) = AbsoluteHead (x+1,y)
+applyCommandToAbsoluteHead (AbsoluteHead (x,y)) (Command MoveLeft) = AbsoluteHead (x-1,y)
+
+applyCommand :: RopePosition -> Command -> RopePosition
+applyCommand (RopePosition head tail) c = RopePosition (applyCommandToAbsoluteHead head c) (realizeVirtualTail $ virtualizeRelativeTail tail c)
+
+solveDay9Part2 :: [Command] -> Int
+solveDay9Part2 = undefined
\ No newline at end of file
diff --git a/Day9/input b/Day9/input
new file mode 100644
index 0000000..757d633
--- /dev/null
+++ b/Day9/input
@@ -0,0 +1,2000 @@
+R 1
+D 1
+L 1
+D 1
+R 2
+L 1
+U 2
+D 1
+U 2
+L 1
+U 1
+L 2
+D 1
+U 2
+L 1
+R 1
+D 1
+L 2
+D 2
+L 2
+R 1
+L 2
+U 2
+R 2
+L 2
+U 2
+L 1
+D 1
+L 2
+U 1
+R 1
+D 2
+L 2
+U 1
+R 1
+D 1
+U 2
+L 1
+D 2
+U 1
+D 1
+R 2
+D 1
+L 2
+D 1
+L 1
+R 1
+D 2
+L 1
+R 2
+D 2
+U 2
+R 2
+D 2
+R 2
+L 2
+D 2
+L 2
+D 1
+U 2
+R 1
+D 2
+L 2
+R 2
+L 1
+D 1
+U 2
+D 1
+R 2
+U 2
+R 2
+D 1
+L 1
+U 2
+D 1
+U 1
+D 2
+U 1
+R 1
+U 2
+D 1
+L 2
+U 1
+L 2
+D 2
+R 1
+U 2
+L 1
+D 2
+R 1
+U 1
+D 1
+L 2
+U 1
+R 1
+D 2
+U 2
+L 1
+U 2
+D 2
+R 1
+U 2
+R 1
+U 2
+R 1
+D 2
+U 1
+D 2
+L 2
+D 2
+L 2
+D 2
+R 1
+U 1
+D 3
+U 1
+R 2
+U 3
+D 1
+U 2
+D 2
+U 2
+D 1
+U 2
+R 2
+L 2
+U 1
+L 3
+D 1
+R 3
+D 3
+R 2
+L 1
+U 3
+D 1
+U 2
+R 2
+D 1
+R 3
+D 2
+R 3
+D 1
+U 3
+L 3
+R 2
+U 3
+L 3
+U 2
+L 3
+D 1
+R 3
+U 3
+R 2
+D 1
+U 3
+R 3
+D 1
+L 2
+D 2
+L 2
+D 3
+R 2
+U 3
+L 3
+D 2
+U 3
+L 2
+U 3
+D 1
+L 1
+D 3
+R 1
+D 3
+U 1
+L 3
+U 1
+D 2
+U 1
+D 1
+U 2
+D 3
+L 1
+U 1
+R 1
+U 3
+D 3
+R 1
+L 2
+R 3
+L 3
+U 1
+D 2
+R 2
+U 2
+D 3
+U 2
+D 3
+L 1
+R 3
+D 3
+R 2
+U 3
+D 3
+L 2
+R 3
+D 3
+R 2
+L 1
+R 3
+D 2
+R 1
+D 3
+L 1
+U 1
+D 2
+R 1
+D 1
+L 1
+R 2
+L 1
+U 1
+L 2
+D 2
+L 2
+D 1
+L 2
+U 3
+D 1
+R 3
+L 2
+R 1
+L 2
+R 3
+U 2
+L 4
+R 3
+L 1
+R 2
+D 2
+L 4
+U 3
+L 1
+D 1
+L 3
+U 2
+L 3
+U 2
+L 1
+R 2
+L 3
+U 1
+D 2
+R 1
+L 4
+R 4
+L 4
+U 2
+D 2
+R 2
+L 2
+U 2
+R 1
+D 3
+L 4
+R 2
+U 1
+L 4
+R 1
+L 1
+D 4
+R 3
+D 1
+R 2
+L 2
+R 3
+L 1
+U 1
+D 3
+U 2
+R 1
+L 1
+D 3
+R 2
+U 2
+R 3
+U 2
+D 1
+R 4
+U 4
+D 3
+U 3
+R 2
+U 1
+L 1
+U 4
+D 1
+R 4
+D 4
+L 3
+U 4
+R 4
+L 1
+R 1
+U 2
+R 4
+D 2
+R 1
+U 2
+L 1
+D 1
+L 3
+R 3
+L 3
+D 3
+L 4
+D 2
+U 2
+D 3
+R 1
+U 1
+D 3
+U 1
+R 3
+D 2
+L 3
+R 2
+D 1
+L 3
+D 3
+U 3
+D 4
+L 2
+U 3
+D 5
+L 2
+D 2
+R 2
+L 3
+D 5
+U 4
+R 1
+D 5
+R 1
+D 1
+L 2
+R 4
+U 2
+D 3
+R 5
+L 2
+R 2
+D 1
+R 2
+U 5
+L 4
+U 5
+D 1
+L 2
+U 2
+R 2
+D 4
+U 3
+L 2
+D 1
+U 4
+L 4
+D 3
+L 3
+D 3
+R 1
+U 1
+R 1
+U 1
+R 2
+D 3
+R 5
+U 1
+D 2
+L 5
+U 5
+L 4
+D 4
+U 4
+L 1
+R 5
+U 2
+L 3
+U 2
+D 3
+L 5
+D 5
+L 2
+U 2
+D 4
+U 3
+D 3
+L 1
+D 2
+R 2
+D 1
+R 4
+L 3
+D 1
+U 4
+L 1
+R 2
+L 4
+D 5
+R 3
+D 1
+L 5
+D 5
+U 3
+R 2
+D 4
+L 2
+R 2
+D 3
+R 3
+U 2
+R 5
+U 4
+R 3
+L 1
+D 2
+U 1
+L 1
+R 2
+U 4
+D 4
+L 1
+R 1
+U 4
+L 3
+U 5
+R 3
+L 4
+D 3
+U 1
+R 4
+U 1
+L 1
+U 3
+R 4
+L 5
+D 1
+U 4
+R 5
+L 1
+R 4
+D 2
+L 6
+D 5
+U 5
+L 5
+R 6
+D 1
+U 2
+R 1
+U 4
+D 6
+L 6
+D 6
+U 6
+D 4
+U 4
+D 1
+U 3
+L 5
+D 6
+R 1
+L 1
+D 2
+L 4
+D 4
+L 4
+R 4
+U 2
+L 3
+D 4
+R 3
+D 4
+U 5
+R 4
+U 1
+R 6
+L 3
+R 2
+U 1
+L 1
+R 2
+D 3
+R 6
+D 6
+U 1
+D 3
+U 4
+D 5
+L 5
+U 3
+D 6
+L 5
+R 5
+U 1
+R 4
+D 2
+L 2
+R 4
+L 5
+R 4
+L 3
+D 5
+R 6
+L 6
+U 1
+R 5
+U 6
+D 2
+R 2
+D 1
+L 6
+U 4
+L 1
+R 5
+L 1
+R 2
+D 1
+L 4
+U 4
+L 1
+R 3
+U 5
+L 2
+D 6
+U 5
+R 6
+D 6
+U 3
+L 3
+U 3
+L 4
+D 5
+U 2
+D 4
+U 5
+R 6
+U 5
+D 2
+U 6
+D 3
+L 3
+D 6
+L 5
+R 2
+D 6
+R 7
+D 3
+L 7
+D 3
+U 2
+R 7
+U 2
+L 6
+R 7
+D 3
+R 7
+U 5
+R 7
+L 5
+R 7
+L 7
+U 4
+D 4
+U 1
+D 3
+U 1
+D 5
+R 3
+U 1
+D 2
+U 1
+L 4
+U 2
+L 6
+D 7
+U 1
+D 4
+U 6
+L 4
+R 4
+D 4
+R 6
+D 7
+R 1
+D 7
+L 4
+R 4
+L 1
+U 1
+R 6
+L 7
+D 7
+L 5
+U 7
+D 3
+L 6
+D 6
+U 4
+R 1
+L 2
+D 4
+R 3
+L 1
+R 7
+D 1
+L 2
+U 1
+D 2
+R 1
+U 3
+D 4
+L 3
+U 6
+L 4
+R 2
+L 1
+U 6
+D 1
+R 5
+U 2
+D 2
+L 7
+U 2
+R 5
+D 2
+R 4
+D 4
+R 3
+L 2
+R 3
+U 7
+L 5
+R 7
+U 2
+L 7
+D 3
+U 6
+D 4
+U 4
+D 6
+U 3
+L 6
+R 4
+D 2
+R 4
+D 2
+R 3
+L 5
+D 1
+U 7
+D 4
+L 4
+U 2
+D 2
+U 7
+L 5
+R 6
+U 8
+L 7
+D 2
+U 1
+R 6
+D 4
+L 4
+R 7
+D 1
+L 6
+D 7
+R 7
+U 3
+L 6
+U 1
+L 8
+D 6
+U 8
+L 7
+U 5
+D 8
+L 2
+D 3
+L 8
+U 1
+D 5
+L 4
+R 6
+D 8
+L 6
+U 5
+R 3
+U 7
+R 6
+U 3
+L 3
+D 4
+R 4
+L 2
+R 6
+D 3
+R 3
+L 8
+U 2
+D 6
+U 3
+D 8
+U 6
+D 4
+U 8
+R 7
+D 2
+U 6
+D 6
+R 1
+U 3
+D 3
+R 1
+U 3
+R 1
+D 7
+L 8
+R 8
+U 7
+R 3
+L 8
+U 2
+L 8
+D 4
+U 4
+R 1
+D 3
+R 4
+U 3
+L 7
+U 2
+R 7
+D 2
+U 4
+D 3
+L 8
+D 5
+L 3
+U 4
+D 6
+L 5
+D 2
+U 1
+R 6
+L 4
+R 6
+U 5
+R 8
+U 8
+D 7
+L 5
+D 2
+L 8
+U 2
+D 1
+R 1
+L 7
+U 4
+R 2
+U 7
+D 6
+R 6
+L 5
+U 8
+D 7
+R 8
+L 8
+D 6
+U 6
+R 1
+D 5
+L 7
+R 8
+L 4
+D 3
+L 2
+U 5
+R 9
+L 8
+D 8
+L 2
+R 4
+L 7
+R 5
+L 1
+R 8
+D 8
+L 4
+U 2
+D 7
+L 7
+D 6
+R 8
+L 3
+D 7
+U 1
+R 6
+D 6
+U 6
+L 9
+D 1
+R 7
+L 5
+R 5
+U 5
+D 4
+L 8
+U 4
+D 8
+R 4
+D 6
+U 3
+D 7
+L 5
+D 6
+R 9
+U 4
+R 6
+L 3
+U 4
+D 9
+L 7
+R 5
+D 9
+L 6
+U 7
+L 7
+R 4
+D 5
+R 7
+L 5
+R 3
+U 8
+L 6
+U 5
+L 9
+R 8
+U 4
+D 2
+L 4
+D 7
+R 7
+D 4
+L 4
+U 2
+L 3
+R 1
+D 3
+U 6
+R 1
+U 8
+R 2
+L 4
+D 3
+L 5
+U 4
+R 7
+L 2
+R 7
+L 9
+D 9
+U 5
+L 4
+U 1
+D 1
+U 6
+D 1
+L 6
+D 7
+U 5
+D 9
+R 9
+D 5
+U 9
+L 3
+R 5
+D 10
+R 1
+U 7
+D 6
+L 3
+U 5
+R 1
+D 5
+R 8
+U 3
+L 1
+D 2
+R 1
+L 6
+R 8
+D 9
+U 9
+D 4
+R 1
+U 8
+L 5
+U 4
+D 7
+L 1
+R 4
+L 6
+D 4
+R 5
+D 1
+R 10
+D 5
+R 7
+U 6
+R 5
+U 2
+L 8
+R 1
+U 3
+L 5
+U 4
+L 3
+D 3
+U 6
+D 10
+L 3
+D 7
+L 5
+D 4
+U 6
+R 9
+U 5
+D 5
+R 2
+L 7
+U 8
+D 5
+R 9
+L 6
+R 8
+U 9
+L 4
+R 10
+D 10
+L 9
+R 8
+L 4
+R 5
+L 9
+D 1
+L 3
+R 9
+U 2
+L 5
+R 2
+U 1
+R 4
+D 10
+U 3
+D 8
+L 9
+D 8
+L 5
+D 4
+U 2
+L 8
+R 5
+U 4
+D 1
+L 4
+U 7
+D 9
+R 3
+D 7
+R 9
+L 6
+R 6
+U 8
+L 10
+U 5
+D 4
+R 5
+L 6
+D 7
+L 10
+R 1
+L 9
+U 6
+D 9
+R 7
+L 7
+D 6
+U 6
+R 1
+D 7
+L 1
+R 9
+D 9
+R 3
+L 5
+D 4
+R 3
+L 5
+D 11
+U 1
+R 6
+D 8
+R 4
+D 3
+R 9
+U 3
+D 8
+U 7
+R 2
+U 10
+R 4
+L 4
+D 10
+R 8
+U 11
+R 7
+D 7
+R 9
+D 11
+U 6
+R 7
+D 10
+L 4
+D 5
+L 7
+D 3
+L 4
+D 4
+U 4
+R 3
+L 9
+D 4
+L 8
+U 5
+R 7
+L 2
+D 4
+R 11
+U 10
+D 3
+R 8
+D 3
+R 10
+L 8
+U 6
+R 4
+D 10
+R 7
+D 3
+R 2
+U 1
+D 5
+L 8
+U 2
+R 1
+U 8
+R 11
+L 3
+U 10
+L 5
+D 3
+L 6
+U 10
+L 11
+D 4
+L 5
+D 1
+L 4
+D 1
+L 3
+R 7
+U 7
+R 4
+L 1
+U 10
+D 11
+L 1
+R 1
+U 9
+D 6
+L 9
+D 1
+L 4
+D 11
+L 5
+U 2
+L 5
+D 8
+U 10
+D 5
+U 10
+L 8
+R 11
+D 10
+U 11
+R 4
+U 6
+D 11
+R 1
+L 4
+U 12
+L 8
+U 12
+D 4
+L 7
+U 7
+L 8
+D 3
+U 1
+L 12
+D 5
+U 3
+D 6
+R 7
+U 1
+D 12
+R 6
+U 3
+D 3
+R 12
+U 5
+R 3
+U 8
+L 6
+R 6
+U 3
+L 4
+D 8
+L 5
+D 12
+U 1
+L 9
+R 4
+L 1
+D 6
+U 9
+L 5
+R 3
+L 9
+D 8
+R 6
+D 3
+U 6
+L 1
+D 7
+U 5
+D 1
+L 11
+R 7
+D 11
+L 3
+U 6
+R 9
+D 12
+R 11
+L 5
+R 8
+L 2
+U 10
+R 6
+U 10
+L 9
+U 1
+L 1
+R 8
+L 7
+R 3
+U 4
+L 3
+R 8
+L 9
+R 11
+L 9
+D 11
+U 1
+L 12
+R 6
+L 3
+R 3
+D 12
+U 9
+L 9
+D 8
+R 4
+L 7
+R 1
+U 2
+R 4
+U 4
+R 11
+U 7
+D 11
+U 3
+D 6
+U 7
+L 2
+D 4
+U 9
+R 3
+L 8
+R 9
+L 4
+R 5
+L 7
+D 3
+R 8
+L 6
+U 10
+R 3
+L 6
+D 8
+U 3
+D 9
+L 1
+U 13
+R 12
+L 13
+R 2
+U 8
+R 1
+D 11
+R 5
+L 4
+U 5
+L 3
+D 13
+U 2
+D 1
+U 2
+L 9
+D 3
+R 6
+U 13
+L 3
+U 5
+R 2
+D 2
+L 5
+U 4
+R 6
+D 1
+U 9
+L 7
+R 11
+U 10
+D 12
+R 10
+U 7
+R 5
+L 2
+R 13
+L 13
+D 3
+R 7
+U 1
+L 1
+D 2
+L 9
+U 12
+D 7
+U 13
+L 12
+U 13
+D 7
+U 7
+D 8
+L 2
+U 6
+D 2
+U 6
+L 8
+U 4
+D 11
+U 11
+L 11
+R 10
+L 10
+R 6
+D 13
+U 2
+L 7
+U 8
+D 1
+R 6
+L 7
+R 9
+L 8
+R 9
+L 6
+R 7
+D 12
+R 11
+L 8
+R 1
+D 5
+R 5
+L 10
+U 6
+L 8
+D 9
+L 5
+U 4
+D 12
+U 8
+L 13
+U 6
+D 10
+R 5
+L 13
+D 7
+L 13
+R 5
+L 10
+D 13
+L 9
+R 3
+D 8
+U 9
+D 10
+U 10
+D 7
+L 5
+R 5
+D 9
+L 7
+R 10
+D 13
+R 1
+U 2
+R 6
+U 14
+R 10
+D 6
+U 13
+D 14
+U 5
+D 1
+U 8
+R 4
+U 9
+R 13
+L 4
+D 2
+R 8
+U 2
+D 12
+U 3
+R 6
+U 6
+D 11
+R 7
+L 12
+R 9
+U 7
+D 1
+R 14
+L 11
+U 4
+D 13
+U 5
+L 7
+R 14
+L 1
+U 6
+D 3
+L 1
+U 13
+D 8
+U 14
+D 5
+U 14
+L 1
+R 1
+D 5
+U 7
+L 8
+R 6
+U 1
+D 2
+R 14
+U 13
+L 10
+U 8
+D 13
+U 6
+R 2
+D 4
+R 6
+U 7
+D 10
+L 6
+U 5
+L 3
+D 9
+U 13
+D 8
+U 3
+R 3
+L 12
+D 5
+R 8
+U 7
+R 11
+U 6
+D 7
+R 13
+U 1
+D 9
+U 10
+D 3
+L 5
+R 12
+L 4
+D 13
+R 7
+D 12
+R 11
+D 9
+R 5
+U 13
+R 3
+D 4
+U 10
+R 3
+U 6
+L 4
+R 1
+U 4
+L 9
+D 11
+U 5
+D 3
+U 13
+D 1
+L 1
+D 13
+L 2
+R 9
+L 4
+R 2
+U 9
+D 9
+U 12
+L 14
+R 2
+L 9
+R 5
+U 2
+D 3
+R 13
+U 5
+D 1
+U 15
+R 6
+D 14
+R 8
+L 9
+D 14
+L 6
+R 8
+U 14
+R 11
+L 3
+D 15
+U 5
+R 1
+L 7
+R 12
+D 1
+R 4
+D 13
+U 9
+D 2
+L 3
+U 10
+R 10
+D 2
+R 6
+U 13
+D 7
+R 5
+U 5
+L 12
+U 6
+R 1
+L 7
+U 9
+D 15
+L 8
+U 9
+L 5
+R 3
+L 9
+U 6
+L 11
+D 8
+L 11
+D 13
+U 3
+R 6
+D 2
+L 10
+R 15
+U 2
+D 8
+R 6
+D 6
+L 8
+D 7
+U 2
+D 14
+U 4
+R 6
+D 15
+L 12
+R 4
+D 3
+U 7
+D 10
+L 8
+U 7
+R 10
+U 11
+D 2
+R 10
+D 10
+U 13
+R 8
+L 2
+U 12
+R 9
+U 12
+R 5
+U 10
+L 6
+R 3
+D 10
+L 10
+U 6
+L 4
+R 3
+D 9
+R 15
+D 14
+L 11
+R 5
+U 2
+R 14
+L 15
+R 3
+D 3
+L 4
+U 10
+D 14
+L 9
+D 5
+L 16
+U 12
+L 4
+D 15
+L 10
+R 14
+D 4
+R 12
+L 7
+U 5
+R 3
+L 6
+U 16
+L 5
+U 8
+D 8
+L 6
+D 3
+U 14
+R 1
+L 13
+U 4
+D 11
+R 5
+L 11
+D 7
+R 1
+L 14
+U 10
+L 5
+D 15
+U 14
+L 4
+D 7
+U 3
+R 1
+U 2
+R 3
+D 16
+U 7
+R 7
+D 13
+R 7
+D 5
+U 7
+R 16
+U 4
+L 3
+R 9
+U 1
+D 2
+R 5
+D 3
+U 8
+R 5
+L 13
+U 13
+L 2
+R 9
+L 14
+D 10
+R 1
+U 1
+R 14
+U 14
+R 2
+L 1
+R 12
+L 1
+D 6
+R 2
+D 7
+R 11
+L 5
+D 8
+R 15
+D 12
+R 12
+L 8
+D 10
+R 2
+D 12
+U 15
+L 9
+D 4
+U 3
+L 8
+D 3
+U 9
+D 16
+L 2
+U 14
+R 15
+D 14
+U 12
+D 6
+U 14
+R 11
+D 12
+R 2
+U 13
+L 2
+R 1
+D 6
+U 13
+D 15
+U 1
+R 14
+L 16
+D 8
+R 13
+L 14
+R 3
+D 8
+L 6
+R 16
+D 6
+L 13
+R 2
+L 11
+D 2
+U 1
+R 15
+L 9
+U 1
+R 12
+L 9
+D 7
+L 8
+U 2
+L 14
+R 7
+U 8
+D 15
+R 8
+D 13
+L 15
+R 11
+D 17
+U 2
+R 14
+L 9
+U 11
+D 6
+U 4
+D 8
+U 16
+D 5
+L 3
+D 11
+L 7
+U 11
+L 4
+D 5
+L 5
+D 2
+U 8
+R 17
+D 17
+U 12
+R 4
+L 13
+R 15
+L 10
+U 2
+L 10
+R 6
+D 1
+U 6
+L 3
+D 8
+R 4
+D 1
+L 4
+D 13
+R 1
+U 3
+L 1
+U 9
+D 13
+U 2
+D 13
+R 6
+D 8
+R 6
+D 13
+R 4
+D 10
+L 10
+U 8
+D 1
+R 6
+U 14
+R 3
+L 10
+U 15
+L 11
+U 13
+L 4
+U 5
+L 16
+R 16
+U 11
+R 14
+D 7
+U 5
+R 9
+L 5
+U 12
+R 16
+U 10
+D 5
+R 17
+L 3
+D 5
+U 13
+R 3
+U 3
+L 14
+U 1
+L 8
+R 2
+D 3
+U 9
+D 7
+L 1
+D 5
+R 16
+D 12
+R 1
+U 2
+L 16
+U 3
+R 18
+D 11
+R 3
+L 17
+R 7
+L 6
+D 13
+L 5
+R 12
+D 3
+U 1
+L 1
+U 5
+L 8
+R 11
+L 13
+D 14
+R 17
+D 17
+L 2
+U 7
+D 18
+R 3
+D 2
+U 6
+D 9
+R 3
+U 3
+R 5
+D 16
+R 9
+D 13
+U 8
+D 17
+R 4
+L 6
+R 7
+D 2
+R 15
+U 10
+R 15
+D 6
+L 8
+R 17
+D 5
+L 9
+U 18
+D 10
+U 3
+L 6
+U 10
+D 10
+U 16
+R 6
+D 18
+U 10
+D 8
+U 14
+R 3
+U 14
+L 16
+R 3
+D 5
+L 2
+R 4
+D 9
+L 13
+R 17
+L 8
+D 2
+R 16
+D 18
+L 11
+D 15
+U 5
+D 7
+U 14
+D 13
+U 7
+L 13
+D 13
+R 1
+D 15
+R 11
+L 1
+U 6
+D 14
+L 6
+U 8
+D 15
+R 8
+L 12
+D 17
+R 8
+L 17
+D 16
+R 9
+D 19
+U 4
+R 9
+U 10
+L 3
+U 3
+D 5
+R 2
+U 6
+L 16
+D 8
+R 4
+L 16
+R 15
+U 6
+L 8
+D 6
+L 6
+R 1
+L 8
+D 13
+L 1
+U 7
+R 16
+L 16
+U 1
+L 18
+D 16
+L 8
+U 2
+D 1
+R 2
+D 10
+U 8
+D 2
+R 18
+U 14
+D 15
+R 15
+U 3
+D 1
+U 17
+L 17
+D 15
+L 14
+R 6
+L 18
+U 19
+L 6
+U 17
+L 1
+D 2
+U 17
+R 11
+L 3
+R 3
+L 12
+U 1
+L 9
+U 13
+D 15
+U 12
+R 1
+L 5
+D 17
+L 14
+D 13
+L 2
+D 10
+U 5
+R 13
+L 19
+D 1
+R 12
+U 17
+R 15
+D 19
+U 12
+D 16
+R 2
+U 3
+R 15
+L 13
+U 11
+D 19
+R 10
+D 19
+L 2
+U 12
+R 5
+L 13
+U 13
+R 1
+D 11
+R 17
+D 7
+U 4
+D 14
+L 13
+R 8
+L 8
+D 8