Posts

Showing posts from April, 2017

AOC 2016 - Day 5

Table of ContentsAOC 2016 - Day 5BackgroundProblem - Part 1Solution - Part 1Collection functionProblem - Part 2Solution - Part 2Storing the pieces of the answerCollecting the pieces of the answerProducing the answerSome side notesMutable vs. Immutable data structuresSeq vs. ParallelSeqLessons learnedPS: Solution - Part 2 (Pure functional implementation)Performance comparison with day5part2AOC 2016 - Day 5Problem statement on Advent of Code website.Code for this post can be found on GitHub.BackgroundOn Day 1, we located Easter Bunny headquarters.On Day 2, we broke the code to use the bathroom in Easter Bunny HQ.On Day 3, we helped the EBs' design department by removing invalid triangles from the list.On Day 4, we figured out which rooms in the information kiosk are valid.On Day 5, we will figure out how to get past security doors by calculating the code.Problem - Part 1For Part 1, we are given two pieces of information.The door IDAn increasing integer index, starting at 0.For each …

MD5 in F#, Functionally

Table of ContentsMD5 in F#, FunctionallyOut-of-the-box implementationPlanning the implementationConsiderationsMapping from Wikipedia to F#ImplementationStep 1: Define the shift in each of the 64 roundsStep 2: Calculate the binary integer portion of integer sinesStep 3: Define the typesStep 4: Padding the messageStep 7: The core of the main loop (Yes, I know this is out of order)Step 6: Hash a single 512-bit chunkStep 5: Process the entire message and derive a single MD5 hashTestingPerformanceLessons LearnedMD5 in F#, FunctionallyCode for this post can be found on GitHub.The Advent of Code Day 5 problem presented a very interesting challenge - it required an MD5 hash function to get the final answer.As my goal with the AOC challenges is to increase my knowledge of F#, I chose to:Implement my own version of the MD5 algorithmImplement it functionally (no mutation, if possible)Out-of-the-box implementation.NET has an out-of-the-box implementation of MD5, which can be accessed quite easily…

AOC 2016 - Day 4

Table of ContentsAOC 2016 - Day 4BackgroundProblem - Part 1Solution - Part 1Create the data structureStore each unchanged line of dataExtract the provided sector ID and checksumCalculate the checksumTie it all togetherProblem - Part 2Solution - Part 2Modify the data structureWrite the shift cipher algorithmTie it all togetherTestingLessons LearnedAOC 2016 - Day 4Problem statement on Advent of Code website.Code for this post can be found on GitHub.BackgroundOn Day 1, we located Easter Bunny headquarters.On Day 2, we broke the code to use the bathroom in Easter Bunny HQ.On Day 3, we helped the EBs' design department by removing invalid triangles from the list.On Day 4, we will figure out which rooms on an encrypted information kiosk are valid and which ones are not.Problem - Part 1The kiosk lists one room per line. Each room entry consists of 3 parts.Encrypted name comprised of lowercase letters separated by dashes Always follows by a dashSector IDChecksum Always in square bracketsF…

AOC 2016 - Day 3

Table of ContentsAOC 2016 - Day 3BackgroundProblem - Part 1Solution - Part 1Save the inputValidate a triangleParse and filter the list of trianglesGet the count of valid trianglesProblem - Part 2Solution - Part 2Parse and filter the list of trianglesGet the count of valid trianglesLessons LearnedAOC 2016 - Day 3Problem statement on Advent of Code website.Code for this post can be found on GitHub.BackgroundOn Day 1, we located Easter Bunny headquarters.On Day 2, we broke the code to use the bathroom in Easter Bunny HQ.Problem - Part 1On Day 3, we are walking through a design department and see a list values specifying various triangles. Our job is to be a good citizen and help the design department by identifying the triangles which are "possible".Solution - Part 1The algorithm which determines whether a triangle is "possible" is stated as follows:In a valid triangle, the sum of any two sides must be larger than the remaining side.I rephrased this for myself as foll…

AOC 2016 - Day 2 Alternate Solutions

Table of ContentsAOC 2016 - Day 2 Alternate SolutionsModeling a boardStoring a board in a text fileVerticesEdgesBuilding the boardGeneric solution frameworkGraph data structuresAdjacency MatrixEdge ListAdjacency ListInductive GraphTestingPerformanceObservationsNext stepsAOC 2016 - Day 2 Alternate SolutionsProblem on AOC website.Code for this post can be found on GitHub.This post is a follow-up to my last post on my solution for AOC Day 2 and how I was unhappy with the design (though my initial results were still correct).Since that time, I have implemented a set of five graph data structures to make the solution more robust than simply encoding the minimum solution with a function.These data structures have a few advantages:The data types are much more robust - for the board and the graphs. Instead of talking in terms of raw numbers / strings, I can now speak in terms of Vertices and Edges.The solution's design allows for the underlying data structure to be swapped out as long as …