From 0c672ee4c5d50a7e51b0408ae1b87f68c44534a7 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 14 Dec 2017 09:16:23 +0000 Subject: [PATCH] Day 14 part 1 --- src/advent14/advent14.hs | 60 ++++++++ src/advent14/advent14.ipynb | 267 ++++++++++++++++++++++++++++++++++++ 2 files changed, 327 insertions(+) create mode 100644 src/advent14/advent14.hs create mode 100644 src/advent14/advent14.ipynb diff --git a/src/advent14/advent14.hs b/src/advent14/advent14.hs new file mode 100644 index 0000000..940fe7b --- /dev/null +++ b/src/advent14/advent14.hs @@ -0,0 +1,60 @@ +import Data.List.Split (chunksOf) +import Data.Char (ord) +import Text.Printf (printf) +import Data.Bits (xor) + +puzzleKey = "xlqgujun" + + +part1 :: String -> Int +part1 key = sum rowCounts + where hashes = map knotHash $ rowSpecs key + rowCounts = map (countSetBits . binify) hashes + +rowSpecs :: String -> [String] +rowSpecs key = map (((key ++ "-") ++) . show) [0..127] + +countSetBits :: String -> Int +countSetBits = length . filter (== '1') + + +knotHash :: String -> [Int] +knotHash input = densify tied + where (tied, _, _) = foldl step ([0..255], 0, 0) hashTerms + hashTerms = mkHashTerms input + +step :: ([Int], Int, Int) -> Int -> ([Int], Int, Int) +step (original, start, skip) len = (replaced, start', skip + 1) + where replaced = tie original start len + start' = (start + len + skip) `mod` (length original) + +tie :: [a] -> Int -> Int -> [a] +tie original start len = replace original replacement start + where replacement = reverse $ extract original start len + +extract :: [a] -> Int -> Int -> [a] +extract items from len = take len $ drop from $ items ++ items + +replace :: [a] -> [a] -> Int -> [a] +replace original replacement from = take (length original) (start ++ replacement ++ remainder) + where excess = drop (length original - from) replacement + stub = drop (length excess) original + start = take from (excess ++ stub) + remainder = drop (length $ start ++ replacement) original + + +mkHashTerms :: String -> [Int] +mkHashTerms text = take (length chunk * 64) $ cycle chunk + where chunk = map ord text ++ [17, 31, 73, 47, 23] + +hexify :: [Int] -> String +hexify = concatMap (printf "%02x") + +binify :: [Int] -> String +binify = concatMap (printf "%08b") + +densify :: [Int] -> [Int] +densify ns = codes + where chunks = chunksOf 16 ns + compress = foldl1 xor + codes = map compress chunks \ No newline at end of file diff --git a/src/advent14/advent14.ipynb b/src/advent14/advent14.ipynb new file mode 100644 index 0000000..c4d69b6 --- /dev/null +++ b/src/advent14/advent14.ipynb @@ -0,0 +1,267 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": {}, + "outputs": [], + "source": [ + "{-# LANGUAGE NegativeLiterals #-}\n", + "{-# LANGUAGE FlexibleContexts #-}" + ] + }, + { + "cell_type": "code", + "execution_count": 34, + "metadata": {}, + "outputs": [], + "source": [ + "puzzleKey = \"xlqgujun\"" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "metadata": {}, + "outputs": [], + "source": [ + "import Data.List.Split (chunksOf)\n", + "import Data.Char (ord)\n", + "import Text.Printf (printf)\n", + "import Data.Bits (xor)\n", + "import qualified Data.Graph as G" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "metadata": {}, + "outputs": [], + "source": [ + "knotHash :: String -> [Int]\n", + "knotHash input = densify tied\n", + " where (tied, _, _) = foldl step ([0..255], 0, 0) hashTerms\n", + " hashTerms = mkHashTerms input\n", + "\n", + "step :: ([Int], Int, Int) -> Int -> ([Int], Int, Int)\n", + "step (original, start, skip) len = (replaced, start', skip + 1)\n", + " where replaced = tie original start len\n", + " start' = (start + len + skip) `mod` (length original)\n", + "\n", + "tie :: [a] -> Int -> Int -> [a]\n", + "tie original start len = replace original replacement start\n", + " where replacement = reverse $ extract original start len\n", + "\n", + "extract :: [a] -> Int -> Int -> [a]\n", + "extract items from len = take len $ drop from $ items ++ items\n", + "\n", + "replace :: [a] -> [a] -> Int -> [a]\n", + "replace original replacement from = take (length original) (start ++ replacement ++ remainder)\n", + " where excess = drop (length original - from) replacement\n", + " stub = drop (length excess) original\n", + " start = take from (excess ++ stub)\n", + " remainder = drop (length $ start ++ replacement) original \n", + "\n", + "\n", + "mkHashTerms :: String -> [Int]\n", + "mkHashTerms text = take (length chunk * 64) $ cycle chunk\n", + " where chunk = map ord text ++ [17, 31, 73, 47, 23]\n", + "\n", + "hexify :: [Int] -> String\n", + "hexify = concatMap (printf \"%02x\")\n", + "\n", + "binify :: [Int] -> String\n", + "binify = concatMap (printf \"%08b\")\n", + "\n", + "densify :: [Int] -> [Int]\n", + "densify ns = codes\n", + " where chunks = chunksOf 16 ns\n", + " compress = foldl1 xor\n", + " codes = map compress chunks" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "\"d4f76bdcbf838f8416ccfa8bc6d1f9e6\"" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "hexify $ knotHash \"flqrgnkx-0\"" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "```\n", + "##.#.#..-->\n", + ".#.#.#.# \n", + "....#.#. \n", + "#.#.##.# \n", + ".##.#... \n", + "##..#..# \n", + ".#...#.. \n", + "##.#.##.-->\n", + "| | \n", + "V V \n", + "```" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "\"00001010\"" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 8 $ binify $ knotHash \"flqrgnkx-2\"" + ] + }, + { + "cell_type": "code", + "execution_count": 31, + "metadata": {}, + "outputs": [], + "source": [ + "countSetBits = length . filter (== '1')" + ] + }, + { + "cell_type": "code", + "execution_count": 32, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "68" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "countSetBits $ binify $ knotHash \"flqrgnkx-2\"" + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[\"flqrgnkx-0\",\"flqrgnkx-1\",\"flqrgnkx-2\",\"flqrgnkx-3\",\"flqrgnkx-4\",\"flqrgnkx-5\",\"flqrgnkx-6\",\"flqrgnkx-7\",\"flqrgnkx-8\",\"flqrgnkx-9\",\"flqrgnkx-10\",\"flqrgnkx-11\",\"flqrgnkx-12\",\"flqrgnkx-13\",\"flqrgnkx-14\",\"flqrgnkx-15\",\"flqrgnkx-16\",\"flqrgnkx-17\",\"flqrgnkx-18\",\"flqrgnkx-19\",\"flqrgnkx-20\"]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "map ((\"flqrgnkx-\" ++) . show) [0..20]" + ] + }, + { + "cell_type": "code", + "execution_count": 33, + "metadata": {}, + "outputs": [], + "source": [ + "rowSpecs key = map (((key ++ \"-\") ++) . show) [0..127]" + ] + }, + { + "cell_type": "code", + "execution_count": 36, + "metadata": {}, + "outputs": [], + "source": [ + "part1 key = sum rowCounts\n", + " where hashes = map knotHash $ rowSpecs key\n", + " rowCounts = map (countSetBits . binify) hashes" + ] + }, + { + "cell_type": "code", + "execution_count": 37, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "8108" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "part1 \"flqrgnkx\"" + ] + }, + { + "cell_type": "code", + "execution_count": 38, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "8204" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "part1 puzzleKey" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Haskell", + "language": "haskell", + "name": "haskell" + }, + "language_info": { + "codemirror_mode": "ihaskell", + "file_extension": ".hs", + "name": "haskell", + "version": "8.0.2" + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} -- 2.34.1