Knot Hash — Haskell — #adventofcode Day 10
Series
This post is part of the series Advent of Code 2017
- Reflections on #aoc2017
- The Halting Problem — Python — #adventofcode Day 25
- Electromagnetic Moat — Rust — #adventofcode Day 24
- Coprocessor Conflagration — Haskell — #adventofcode Day 23
- Sporifica Virus — Rust — #adventofcode Day 22
- Fractal Art — Python — #adventofcode Day 21
- Particle Swarm — Python — #adventofcode Day 20
- A Series of Tubes — Rust — #adventofcode Day 19
- Duet — Haskell — #adventofcode Day 18
- Spinlock — Rust/Python — #adventofcode Day 17
- Permutation Promenade — Julia — #adventofcode Day 16
- Dueling Generators — Rust — #adventofcode Day 15
- Disk Defragmentation — Haskell — #adventofcode Day 14
- Packet Scanners — Haskell — #adventofcode Day 13
- Digital Plumber — Python — #adventofcode Day 12
- Hex Ed — Python — #adventofcode Day 11
- > Knot Hash — Haskell — #adventofcode Day 10 <
- Stream Processing — Haskell — #adventofcode Day 9
- I Heard You Like Registers — Python — #adventofcode Day 8
- Recursive Circus — Ruby — #adventofcode Day 7
- Memory Reallocation — Python — #adventofcode Day 6
- A Maze of Twisty Trampolines — C++ — #adventofcode Day 5
- High Entropy Passphrases — Python — #adventofcode Day 4
- Spiral Memory — Go — #adventofcode Day 3
- Corruption Checksum — Python — #adventofcode Day 2
- Inverse Captcha — Coconut — #adventofcode Day 1
- Advent of Code 2017: introduction
Today’s challenge asks us to help a group of programs implement a (highly questionable) hashing algorithm that involves repeatedly reversing parts of a list of numbers.
!!! commentary I went with Haskell again today, because it’s the weekend so I have a bit more time, and I really enjoyed yesterday’s Haskell implementation. Today gave me the opportunity to explore the standard library a bit more, as well as lending itself nicely to being decomposed into smaller parts to be combined using higher-order functions.
You know the drill by know: import stuff we’ll use later.
module Main where
import Data.Char (ord)
import Data.Bits (xor)
import Data.Function ((&))
import Data.List (unfoldr)
import Text.Printf (printf)
import qualified Data.Text as T
The worked example uses a concept of the “current position” as a pointer to a location in a static list. In Haskell it makes more sense to instead use the front of the list as the current position, and rotate the whole list as we progress to bring the right element to the front.
rotate :: Int -> [Int] -> [Int]
rotate 0 xs = xs
rotate n xs = drop n' xs ++ take n' xs
where n' = n `mod` length xs
The simple version of the hash requires working through the input list, modifying the working list as we go, and incrementing a “skip” counter with each step. Converting this to a functional style, we simply zip up the input with an infinite list [0, 1, 2, 3, ...] to give the counter values. Notice that we also have to calculate how far to rotate the working list to get back to its original position. foldl lets us specify a function that returns a modified version of the working list and feeds the input list in one at a time.
simpleKnotHash :: Int -> [Int] -> [Int]
simpleKnotHash size input = foldl step [0..size-1] input' & rotate (negate finalPos)
where
input' = zip input [0..]
finalPos = sum $ zipWith (+) input [0..]
reversePart xs n = (reverse $ take n xs) ++ drop n xs
step xs (n, skip) = reversePart xs n & rotate (n+skip)
The full version of the hash (part 2 of the challenge) starts the same way as the simple version, except making 64 passes instead of one: we can do this by using replicate to make a list of 64 copies, then collapse that into a single list with concat.
fullKnotHash :: Int -> [Int] -> [Int]
fullKnotHash size input = simpleKnotHash size input'
where input' = concat $ replicate 64 input
The next step in calculating the full hash collapses the full 256-element “sparse” hash down into 16 elements by XORing groups of 16 together. unfoldr is a nice efficient way of doing this.
dense :: [Int] -> [Int]
dense = unfoldr dense'
where
dense' [] = Nothing
dense' xs = Just (foldl1 xor $ take 16 xs, drop 16 xs)
The final hash step is to convert the list of integers into a hexadecimal string.
hexify :: [Int] -> String
hexify = concatMap (printf "%02x")
These two utility functions put together building blocks from the Data.Text module to parse the input string. Note that no arguments are given: the functions are defined purely by composing other functions using the . operator. In Haskell this is referred to as “point-free” style.
strip :: String -> String
strip = T.unpack . T.strip . T.pack
parseInput :: String -> [Int]
parseInput = map (read . T.unpack) . T.splitOn (T.singleton ',') . T.pack
Now we can put it all together, including building the weird input for the “full” hash.
main = do
input <- fmap strip getContents
let simpleInput = parseInput input
asciiInput = map ord input ++ [17, 31, 73, 47, 23]
(a:b:_) = simpleKnotHash 256 simpleInput
print $ (a*b)
putStrLn $ fullKnotHash 256 asciiInput & dense & hexify
Webmentions
You can respond to this post, "Knot Hash — Haskell — #adventofcode Day 10", by:
liking, boosting or replying to a tweet or toot that mentions it; or
sending a webmention from your own site to https://erambler.co.uk/blog/day-10/
Comments
Powered by Cactus Comments 🌵