2
\$\begingroup\$

Background

This year I've taken on the challenge of Advent of Code. The second challenge of the first day is to calculate a frequency for a special device based on a series of numbers. Here's a quote from the challenge describing the problem.

--- Part Two ---
You notice that the device repeats the same frequency change list over and over. To calibrate the device, you need to find the first frequency it reaches twice.

For example, using the same list of changes above, the device would loop as follows:

Current frequency 0, change of +1; resulting frequency 1.
Current frequency 1, change of -2; resulting frequency -1.
Current frequency -1, change of +3; resulting frequency 2.
Current frequency 2, change of +1; resulting frequency 3.
(At this point, the device continues from the start of the list.)
Current frequency 3, change of +1; resulting frequency 4.
Current frequency 4, change of -2; resulting frequency 2, which has already been seen.

In this example, the first frequency reached twice is 2. Note that your device might need to repeat its list of frequency changes many times before a duplicate frequency is found, and that duplicates might be found while in the middle of processing the list.

Here are other examples:

+1, -1 first reaches 0 twice.
+3, +3, +4, -2, -4 first reaches 10 twice.
-6, +3, +8, +5, -6 first reaches 5 twice.
+7, +7, -2, -7, -4 first reaches 14 twice.

What is the first frequency your device reaches twice?


Solution

I've chosen to solve these challenges with elm and since it's a functional programming language the solution I went with for this problem was a recursive function. This function is named calculateFirstDuplicatedFrequency. It will firstly be called in main with a large list of Ints defined in another module, and some other "empty values" to start it. The function will loop through until it finds the first duplicated accumulated frequency. If there are at least two items in the list, then there is a check for if that current accumulated value is in the combos Set, if it is it will stop the loop (so this is my base case).

If the current frequency isn't in that Set, then it will run calculateFirstDuplicatedFrequency again with the original list, the tail, currently accumulated combos and the current frequency.

If the function is called with a list of just one item, then it will run calculateFirstDuplicatedFrequency again, but sending in the original list as input, making the loop "start over" from the top and iterating over all the items in the list that was sent in the beginning once again.

If calculateFirstDuplicatedFrequency is called with an empty list as its frequencyModifiers, then it will just return 0...

OBS. If you think this snippet is a bit unreadable, you can always look at my github instead

import Set exposing (Set)
import Html exposing (Html, button, div, text)
import Frequency exposing (frequencyInput)

main =
  div []
    [ text "Second puzzle"
    , createText (calculateFirstDuplicatedFrequency frequencyInput frequencyInput Set.empty 0)
    ]

createText : Int -> Html msg
createText finalNumber = 
  div [] [ text (String.fromInt finalNumber) ]


calculateFirstDuplicatedFrequency : List Int -> List Int -> Set Int -> Int -> Int
calculateFirstDuplicatedFrequency originalFrequencies frequenciesModifiers frequencyCombos currentFrequency =
  let 
    createNewFreq = addFrequency currentFrequency
    updateCombos = updateFrequencySet frequencyCombos
    checkFrequencyCombos = checkCombos frequencyCombos
  in 
    case frequenciesModifiers of
      [] ->  0
      [x] ->
        calculateFirstDuplicatedFrequency originalFrequencies originalFrequencies (updateCombos (createNewFreq x)) (createNewFreq x)
      (x::xs) ->
        if checkFrequencyCombos (createNewFreq x) then
          createNewFreq x
        else
          calculateFirstDuplicatedFrequency originalFrequencies xs (updateCombos (createNewFreq x)) (createNewFreq x)

addFrequency : Int -> Int -> Int
addFrequency currentFrequency frequency =
  currentFrequency + frequency

updateFrequencySet : Set Int -> Int -> Set Int
updateFrequencySet frequencyCombos newFreq =
  Set.insert newFreq frequencyCombos

checkCombos : Set Int -> Int -> Bool
checkCombos frequencyCombos frequency =
  Set.member frequency frequencyCombos


Questions

This is my first time using a functional programming language and I have so many questions regarding best practices! But my main concern with this code is:

  1. When I searched for recursive patterns I could not find any examples of recursion where they started the loop over again. Is my solution an okey way to do it?
  2. Is it bad to send as many arguments as I am to calculateFirstDuplicatedFrequency? Is there any way I can refactor this code to take in less arguments? Do I need to?
  3. Have I used let...in in the correct way? It feels so nested and ugly. Are there better ways to keep track of all the paramters?
  4. I feel like the way I handle the empty list case isn't too good. I would like to show some kind of error message, or in some other way say that this function won't work if it's called with an empty List. Do you have any suggestion to how I could handle it?
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.