Advent of Code 2018 day 1 part 2: find the first repeated number after some increases and decreases











up vote
3
down vote

favorite












Here is 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?




And here is my solution:



module Main where

import Data.List.Split

parseString :: Integer -> String -> Integer
parseString acc s =
let num = read $ tail s :: Integer
operator = head s
in if operator == '+'
then acc + num
else acc - num

findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])
findFreq curr acc = (0, curr, acc)
findFreq curr acc (x:xs) =
let next = parseString curr x
in if next `elem` acc
then (next, 0, )
else let f = acc ++ [next]
in findFreq next f xs

findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
findRepeatingFrequency init nums xs =
let (found, acc, lst) = findFreq init nums xs
in if found > 0
then found
else findRepeatingFrequency acc lst xs

main :: IO ()
main = do
file <- readFile "input.txt"
let input = filter (not . null) $ splitOn "n" file
print (findRepeatingFrequency 0 input)


This is seriously slow.



Can anyone give me pointes as to how this can be done better?



I'm also keen to know specifically why this is so slow.










share|improve this question




























    up vote
    3
    down vote

    favorite












    Here is 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?




    And here is my solution:



    module Main where

    import Data.List.Split

    parseString :: Integer -> String -> Integer
    parseString acc s =
    let num = read $ tail s :: Integer
    operator = head s
    in if operator == '+'
    then acc + num
    else acc - num

    findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])
    findFreq curr acc = (0, curr, acc)
    findFreq curr acc (x:xs) =
    let next = parseString curr x
    in if next `elem` acc
    then (next, 0, )
    else let f = acc ++ [next]
    in findFreq next f xs

    findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
    findRepeatingFrequency init nums xs =
    let (found, acc, lst) = findFreq init nums xs
    in if found > 0
    then found
    else findRepeatingFrequency acc lst xs

    main :: IO ()
    main = do
    file <- readFile "input.txt"
    let input = filter (not . null) $ splitOn "n" file
    print (findRepeatingFrequency 0 input)


    This is seriously slow.



    Can anyone give me pointes as to how this can be done better?



    I'm also keen to know specifically why this is so slow.










    share|improve this question


























      up vote
      3
      down vote

      favorite









      up vote
      3
      down vote

      favorite











      Here is 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?




      And here is my solution:



      module Main where

      import Data.List.Split

      parseString :: Integer -> String -> Integer
      parseString acc s =
      let num = read $ tail s :: Integer
      operator = head s
      in if operator == '+'
      then acc + num
      else acc - num

      findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])
      findFreq curr acc = (0, curr, acc)
      findFreq curr acc (x:xs) =
      let next = parseString curr x
      in if next `elem` acc
      then (next, 0, )
      else let f = acc ++ [next]
      in findFreq next f xs

      findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
      findRepeatingFrequency init nums xs =
      let (found, acc, lst) = findFreq init nums xs
      in if found > 0
      then found
      else findRepeatingFrequency acc lst xs

      main :: IO ()
      main = do
      file <- readFile "input.txt"
      let input = filter (not . null) $ splitOn "n" file
      print (findRepeatingFrequency 0 input)


      This is seriously slow.



      Can anyone give me pointes as to how this can be done better?



      I'm also keen to know specifically why this is so slow.










      share|improve this question















      Here is 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?




      And here is my solution:



      module Main where

      import Data.List.Split

      parseString :: Integer -> String -> Integer
      parseString acc s =
      let num = read $ tail s :: Integer
      operator = head s
      in if operator == '+'
      then acc + num
      else acc - num

      findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])
      findFreq curr acc = (0, curr, acc)
      findFreq curr acc (x:xs) =
      let next = parseString curr x
      in if next `elem` acc
      then (next, 0, )
      else let f = acc ++ [next]
      in findFreq next f xs

      findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
      findRepeatingFrequency init nums xs =
      let (found, acc, lst) = findFreq init nums xs
      in if found > 0
      then found
      else findRepeatingFrequency acc lst xs

      main :: IO ()
      main = do
      file <- readFile "input.txt"
      let input = filter (not . null) $ splitOn "n" file
      print (findRepeatingFrequency 0 input)


      This is seriously slow.



      Can anyone give me pointes as to how this can be done better?



      I'm also keen to know specifically why this is so slow.







      performance programming-challenge haskell






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 51 mins ago









      200_success

      127k15148412




      127k15148412










      asked 9 hours ago









      dagda1

      1795




      1795






















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          5
          down vote



          accepted










          Small things



          Data.List.Split



          I don't see the need for this module. I see what you're going for with splitOn "n", however Haskell has a function in Prelude called lines:



          words :: String -> [String]

          Prelude> lines "testnphrase, pleasenignore"
          ["test","phrase, please","ignore"]


          parseString



          I think it's cleaner to instead first parse your input into an Integer format and then use [Integer] everywhere instead of [String]. This simplifies your parsing and also gives you a more general function. Note that my implementation is a partial function.



          parseInt :: String -> Integer
          parseInt (op:s) =
          case op of
          '+' -> read s
          '-' -> (-1) * read s
          -- There is a hole here: this will error if 'op'
          -- (the first character) isn't '+' or '-'


          Return values



          The type of findFreq is



          findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])


          I see no reason why it can't return a single Integer. Perhaps you returned all values to debug initially, but once that's done you should switch back.



          It also seems to me like you were using 0 as an "error value," which is appropriate in other languages but generally frowned upon in Haskell. In this case, you can instead use Maybe to indicate failure and change your type signature to



          findFreq :: Integer -> [Integer] -> [String] -> Maybe Integer


          Like I mention later, this isn't necessary since we can condense and fix some logic, but I would recommend using Maybe instead in the future.




          curr and acc



          You do some switching around with your variables curr and acc which confused me a bit. I'd keep acc as the accumulation value for your frequency everywhere and call the list of visited values something like seenFreqs or prevFreqs.



          Correctness



          Repeating frequencies of 0



          Your code currently assumes the repeated frequency is the first nonzero repeated frequency. Thus, it fails for the +1, -1 test case. You could change the code to



          findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
          findRepeatingFrequency init nums xs =
          let (found, acc, lst) = findFreq init nums xs
          in found


          to accommodate that.



          This breaks your way of going through the list again if you don't find a repeat the first time, but fortunately there's a less obfuscated way to avoid your checking and continue: you can use cycle, which creates an infinite list consisting of the input list repeated infinitely.



          cycle :: [a] -> [a]

          Prelude> take 20 $ cycle [1,2,3,4]
          [1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]


          You can call findRepeatingFrequency on cycle input to prevent having to do the cycling yourself in the function.



          Efficiency



          Things go wrong for efficiency in findFreq. There are two problem points that make your code asymptotically inefficient.



          First, in the following line



            in if next `elem` acc


          elem is an O(n) operation. You're calling it for each of the n elements in your input list, meaning that your function is at least O(n^2) (and it turns out that this is the final complexity).



          I checked the number of iterations required for my sample input and it took 142991 iterations to find a repeated frequency. An O(n^2) runtime is going to require about 10 billion iterations for the lookups alone. Ouch.



          Second is a more insidious mistake that is easy to overlook. In this line,



             else let f = acc ++ [next]


          Appending to a list is an O(n) operation. Lists in Haskell are implemented as linked lists, and appending to the back of one cannot be amortized to O(1) like one might in Python's list or Java's ArrayList. You need to travel all the way to the back to add in a link.



          Fixing the second issue actually isn't very hard since you don't care about the ordering of the list. You can switch it to



             else let f = next : acc


          to return to O(1) inserts.



          Fixing the lookups, however, requires a change of data structure.



          Introducing Data.Set



          Data.Set provides unordered sets with O(log n) lookup and insert time. Yeah, it's O(log n), but the total runtime for me when I checked the implementation was less than a second.



          I'm including a sample implementation of day 1 below that I've tested and confirmed on my inputs if you want to compare. However, you said you wanted pointers, so here's the pointers I'll give.




          • You can keep your code mostly the same (although I'd recommend making the style changes I suggested)

          • You will want to use two functions from Data.Set: member and insert.

          • Your end result will look a lot like a fold but with some differences in end conditions (kind of like findFreq)


          Sample implmentation



          Finally, here's a sample implementation.



          module Main where

          import Data.Set (Set)
          import qualified Data.Set as S

          -- This is a partial function
          parseInt :: String -> Integer
          parseInt (op:s) =
          case op of
          '+' -> read s
          '-' -> (-1) * read s
          -- There is a hole here, assuming valid input

          findRepeatingFrequency :: Integer -> Set Integer -> [Integer] -> Integer
          findRepeatingFrequency acc seen (x:xs) =
          if acc `S.member` seen
          then acc
          else findRepeatingFrequency (acc + x) (S.insert acc seen) xs

          partOne :: [Integer] -> Integer
          partOne = sum

          partTwo :: [Integer] -> Integer
          partTwo ints = findRepeatingFrequency 0 S.empty $ cycle ints

          main :: IO ()
          main = do
          file <- readFile "input.txt"
          let input = filter (not . null) $ words file
          let ints = map parseInt input
          print $ partOne ints
          print $ partTwo ints





          share|improve this answer










          New contributor




          cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.


















            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ifUsing("editor", function () {
            StackExchange.using("externalEditor", function () {
            StackExchange.using("snippets", function () {
            StackExchange.snippets.init();
            });
            });
            }, "code-snippets");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "196"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f208832%2fadvent-of-code-2018-day-1-part-2-find-the-first-repeated-number-after-some-incr%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            5
            down vote



            accepted










            Small things



            Data.List.Split



            I don't see the need for this module. I see what you're going for with splitOn "n", however Haskell has a function in Prelude called lines:



            words :: String -> [String]

            Prelude> lines "testnphrase, pleasenignore"
            ["test","phrase, please","ignore"]


            parseString



            I think it's cleaner to instead first parse your input into an Integer format and then use [Integer] everywhere instead of [String]. This simplifies your parsing and also gives you a more general function. Note that my implementation is a partial function.



            parseInt :: String -> Integer
            parseInt (op:s) =
            case op of
            '+' -> read s
            '-' -> (-1) * read s
            -- There is a hole here: this will error if 'op'
            -- (the first character) isn't '+' or '-'


            Return values



            The type of findFreq is



            findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])


            I see no reason why it can't return a single Integer. Perhaps you returned all values to debug initially, but once that's done you should switch back.



            It also seems to me like you were using 0 as an "error value," which is appropriate in other languages but generally frowned upon in Haskell. In this case, you can instead use Maybe to indicate failure and change your type signature to



            findFreq :: Integer -> [Integer] -> [String] -> Maybe Integer


            Like I mention later, this isn't necessary since we can condense and fix some logic, but I would recommend using Maybe instead in the future.




            curr and acc



            You do some switching around with your variables curr and acc which confused me a bit. I'd keep acc as the accumulation value for your frequency everywhere and call the list of visited values something like seenFreqs or prevFreqs.



            Correctness



            Repeating frequencies of 0



            Your code currently assumes the repeated frequency is the first nonzero repeated frequency. Thus, it fails for the +1, -1 test case. You could change the code to



            findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
            findRepeatingFrequency init nums xs =
            let (found, acc, lst) = findFreq init nums xs
            in found


            to accommodate that.



            This breaks your way of going through the list again if you don't find a repeat the first time, but fortunately there's a less obfuscated way to avoid your checking and continue: you can use cycle, which creates an infinite list consisting of the input list repeated infinitely.



            cycle :: [a] -> [a]

            Prelude> take 20 $ cycle [1,2,3,4]
            [1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]


            You can call findRepeatingFrequency on cycle input to prevent having to do the cycling yourself in the function.



            Efficiency



            Things go wrong for efficiency in findFreq. There are two problem points that make your code asymptotically inefficient.



            First, in the following line



              in if next `elem` acc


            elem is an O(n) operation. You're calling it for each of the n elements in your input list, meaning that your function is at least O(n^2) (and it turns out that this is the final complexity).



            I checked the number of iterations required for my sample input and it took 142991 iterations to find a repeated frequency. An O(n^2) runtime is going to require about 10 billion iterations for the lookups alone. Ouch.



            Second is a more insidious mistake that is easy to overlook. In this line,



               else let f = acc ++ [next]


            Appending to a list is an O(n) operation. Lists in Haskell are implemented as linked lists, and appending to the back of one cannot be amortized to O(1) like one might in Python's list or Java's ArrayList. You need to travel all the way to the back to add in a link.



            Fixing the second issue actually isn't very hard since you don't care about the ordering of the list. You can switch it to



               else let f = next : acc


            to return to O(1) inserts.



            Fixing the lookups, however, requires a change of data structure.



            Introducing Data.Set



            Data.Set provides unordered sets with O(log n) lookup and insert time. Yeah, it's O(log n), but the total runtime for me when I checked the implementation was less than a second.



            I'm including a sample implementation of day 1 below that I've tested and confirmed on my inputs if you want to compare. However, you said you wanted pointers, so here's the pointers I'll give.




            • You can keep your code mostly the same (although I'd recommend making the style changes I suggested)

            • You will want to use two functions from Data.Set: member and insert.

            • Your end result will look a lot like a fold but with some differences in end conditions (kind of like findFreq)


            Sample implmentation



            Finally, here's a sample implementation.



            module Main where

            import Data.Set (Set)
            import qualified Data.Set as S

            -- This is a partial function
            parseInt :: String -> Integer
            parseInt (op:s) =
            case op of
            '+' -> read s
            '-' -> (-1) * read s
            -- There is a hole here, assuming valid input

            findRepeatingFrequency :: Integer -> Set Integer -> [Integer] -> Integer
            findRepeatingFrequency acc seen (x:xs) =
            if acc `S.member` seen
            then acc
            else findRepeatingFrequency (acc + x) (S.insert acc seen) xs

            partOne :: [Integer] -> Integer
            partOne = sum

            partTwo :: [Integer] -> Integer
            partTwo ints = findRepeatingFrequency 0 S.empty $ cycle ints

            main :: IO ()
            main = do
            file <- readFile "input.txt"
            let input = filter (not . null) $ words file
            let ints = map parseInt input
            print $ partOne ints
            print $ partTwo ints





            share|improve this answer










            New contributor




            cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.






















              up vote
              5
              down vote



              accepted










              Small things



              Data.List.Split



              I don't see the need for this module. I see what you're going for with splitOn "n", however Haskell has a function in Prelude called lines:



              words :: String -> [String]

              Prelude> lines "testnphrase, pleasenignore"
              ["test","phrase, please","ignore"]


              parseString



              I think it's cleaner to instead first parse your input into an Integer format and then use [Integer] everywhere instead of [String]. This simplifies your parsing and also gives you a more general function. Note that my implementation is a partial function.



              parseInt :: String -> Integer
              parseInt (op:s) =
              case op of
              '+' -> read s
              '-' -> (-1) * read s
              -- There is a hole here: this will error if 'op'
              -- (the first character) isn't '+' or '-'


              Return values



              The type of findFreq is



              findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])


              I see no reason why it can't return a single Integer. Perhaps you returned all values to debug initially, but once that's done you should switch back.



              It also seems to me like you were using 0 as an "error value," which is appropriate in other languages but generally frowned upon in Haskell. In this case, you can instead use Maybe to indicate failure and change your type signature to



              findFreq :: Integer -> [Integer] -> [String] -> Maybe Integer


              Like I mention later, this isn't necessary since we can condense and fix some logic, but I would recommend using Maybe instead in the future.




              curr and acc



              You do some switching around with your variables curr and acc which confused me a bit. I'd keep acc as the accumulation value for your frequency everywhere and call the list of visited values something like seenFreqs or prevFreqs.



              Correctness



              Repeating frequencies of 0



              Your code currently assumes the repeated frequency is the first nonzero repeated frequency. Thus, it fails for the +1, -1 test case. You could change the code to



              findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
              findRepeatingFrequency init nums xs =
              let (found, acc, lst) = findFreq init nums xs
              in found


              to accommodate that.



              This breaks your way of going through the list again if you don't find a repeat the first time, but fortunately there's a less obfuscated way to avoid your checking and continue: you can use cycle, which creates an infinite list consisting of the input list repeated infinitely.



              cycle :: [a] -> [a]

              Prelude> take 20 $ cycle [1,2,3,4]
              [1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]


              You can call findRepeatingFrequency on cycle input to prevent having to do the cycling yourself in the function.



              Efficiency



              Things go wrong for efficiency in findFreq. There are two problem points that make your code asymptotically inefficient.



              First, in the following line



                in if next `elem` acc


              elem is an O(n) operation. You're calling it for each of the n elements in your input list, meaning that your function is at least O(n^2) (and it turns out that this is the final complexity).



              I checked the number of iterations required for my sample input and it took 142991 iterations to find a repeated frequency. An O(n^2) runtime is going to require about 10 billion iterations for the lookups alone. Ouch.



              Second is a more insidious mistake that is easy to overlook. In this line,



                 else let f = acc ++ [next]


              Appending to a list is an O(n) operation. Lists in Haskell are implemented as linked lists, and appending to the back of one cannot be amortized to O(1) like one might in Python's list or Java's ArrayList. You need to travel all the way to the back to add in a link.



              Fixing the second issue actually isn't very hard since you don't care about the ordering of the list. You can switch it to



                 else let f = next : acc


              to return to O(1) inserts.



              Fixing the lookups, however, requires a change of data structure.



              Introducing Data.Set



              Data.Set provides unordered sets with O(log n) lookup and insert time. Yeah, it's O(log n), but the total runtime for me when I checked the implementation was less than a second.



              I'm including a sample implementation of day 1 below that I've tested and confirmed on my inputs if you want to compare. However, you said you wanted pointers, so here's the pointers I'll give.




              • You can keep your code mostly the same (although I'd recommend making the style changes I suggested)

              • You will want to use two functions from Data.Set: member and insert.

              • Your end result will look a lot like a fold but with some differences in end conditions (kind of like findFreq)


              Sample implmentation



              Finally, here's a sample implementation.



              module Main where

              import Data.Set (Set)
              import qualified Data.Set as S

              -- This is a partial function
              parseInt :: String -> Integer
              parseInt (op:s) =
              case op of
              '+' -> read s
              '-' -> (-1) * read s
              -- There is a hole here, assuming valid input

              findRepeatingFrequency :: Integer -> Set Integer -> [Integer] -> Integer
              findRepeatingFrequency acc seen (x:xs) =
              if acc `S.member` seen
              then acc
              else findRepeatingFrequency (acc + x) (S.insert acc seen) xs

              partOne :: [Integer] -> Integer
              partOne = sum

              partTwo :: [Integer] -> Integer
              partTwo ints = findRepeatingFrequency 0 S.empty $ cycle ints

              main :: IO ()
              main = do
              file <- readFile "input.txt"
              let input = filter (not . null) $ words file
              let ints = map parseInt input
              print $ partOne ints
              print $ partTwo ints





              share|improve this answer










              New contributor




              cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.




















                up vote
                5
                down vote



                accepted







                up vote
                5
                down vote



                accepted






                Small things



                Data.List.Split



                I don't see the need for this module. I see what you're going for with splitOn "n", however Haskell has a function in Prelude called lines:



                words :: String -> [String]

                Prelude> lines "testnphrase, pleasenignore"
                ["test","phrase, please","ignore"]


                parseString



                I think it's cleaner to instead first parse your input into an Integer format and then use [Integer] everywhere instead of [String]. This simplifies your parsing and also gives you a more general function. Note that my implementation is a partial function.



                parseInt :: String -> Integer
                parseInt (op:s) =
                case op of
                '+' -> read s
                '-' -> (-1) * read s
                -- There is a hole here: this will error if 'op'
                -- (the first character) isn't '+' or '-'


                Return values



                The type of findFreq is



                findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])


                I see no reason why it can't return a single Integer. Perhaps you returned all values to debug initially, but once that's done you should switch back.



                It also seems to me like you were using 0 as an "error value," which is appropriate in other languages but generally frowned upon in Haskell. In this case, you can instead use Maybe to indicate failure and change your type signature to



                findFreq :: Integer -> [Integer] -> [String] -> Maybe Integer


                Like I mention later, this isn't necessary since we can condense and fix some logic, but I would recommend using Maybe instead in the future.




                curr and acc



                You do some switching around with your variables curr and acc which confused me a bit. I'd keep acc as the accumulation value for your frequency everywhere and call the list of visited values something like seenFreqs or prevFreqs.



                Correctness



                Repeating frequencies of 0



                Your code currently assumes the repeated frequency is the first nonzero repeated frequency. Thus, it fails for the +1, -1 test case. You could change the code to



                findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
                findRepeatingFrequency init nums xs =
                let (found, acc, lst) = findFreq init nums xs
                in found


                to accommodate that.



                This breaks your way of going through the list again if you don't find a repeat the first time, but fortunately there's a less obfuscated way to avoid your checking and continue: you can use cycle, which creates an infinite list consisting of the input list repeated infinitely.



                cycle :: [a] -> [a]

                Prelude> take 20 $ cycle [1,2,3,4]
                [1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]


                You can call findRepeatingFrequency on cycle input to prevent having to do the cycling yourself in the function.



                Efficiency



                Things go wrong for efficiency in findFreq. There are two problem points that make your code asymptotically inefficient.



                First, in the following line



                  in if next `elem` acc


                elem is an O(n) operation. You're calling it for each of the n elements in your input list, meaning that your function is at least O(n^2) (and it turns out that this is the final complexity).



                I checked the number of iterations required for my sample input and it took 142991 iterations to find a repeated frequency. An O(n^2) runtime is going to require about 10 billion iterations for the lookups alone. Ouch.



                Second is a more insidious mistake that is easy to overlook. In this line,



                   else let f = acc ++ [next]


                Appending to a list is an O(n) operation. Lists in Haskell are implemented as linked lists, and appending to the back of one cannot be amortized to O(1) like one might in Python's list or Java's ArrayList. You need to travel all the way to the back to add in a link.



                Fixing the second issue actually isn't very hard since you don't care about the ordering of the list. You can switch it to



                   else let f = next : acc


                to return to O(1) inserts.



                Fixing the lookups, however, requires a change of data structure.



                Introducing Data.Set



                Data.Set provides unordered sets with O(log n) lookup and insert time. Yeah, it's O(log n), but the total runtime for me when I checked the implementation was less than a second.



                I'm including a sample implementation of day 1 below that I've tested and confirmed on my inputs if you want to compare. However, you said you wanted pointers, so here's the pointers I'll give.




                • You can keep your code mostly the same (although I'd recommend making the style changes I suggested)

                • You will want to use two functions from Data.Set: member and insert.

                • Your end result will look a lot like a fold but with some differences in end conditions (kind of like findFreq)


                Sample implmentation



                Finally, here's a sample implementation.



                module Main where

                import Data.Set (Set)
                import qualified Data.Set as S

                -- This is a partial function
                parseInt :: String -> Integer
                parseInt (op:s) =
                case op of
                '+' -> read s
                '-' -> (-1) * read s
                -- There is a hole here, assuming valid input

                findRepeatingFrequency :: Integer -> Set Integer -> [Integer] -> Integer
                findRepeatingFrequency acc seen (x:xs) =
                if acc `S.member` seen
                then acc
                else findRepeatingFrequency (acc + x) (S.insert acc seen) xs

                partOne :: [Integer] -> Integer
                partOne = sum

                partTwo :: [Integer] -> Integer
                partTwo ints = findRepeatingFrequency 0 S.empty $ cycle ints

                main :: IO ()
                main = do
                file <- readFile "input.txt"
                let input = filter (not . null) $ words file
                let ints = map parseInt input
                print $ partOne ints
                print $ partTwo ints





                share|improve this answer










                New contributor




                cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.









                Small things



                Data.List.Split



                I don't see the need for this module. I see what you're going for with splitOn "n", however Haskell has a function in Prelude called lines:



                words :: String -> [String]

                Prelude> lines "testnphrase, pleasenignore"
                ["test","phrase, please","ignore"]


                parseString



                I think it's cleaner to instead first parse your input into an Integer format and then use [Integer] everywhere instead of [String]. This simplifies your parsing and also gives you a more general function. Note that my implementation is a partial function.



                parseInt :: String -> Integer
                parseInt (op:s) =
                case op of
                '+' -> read s
                '-' -> (-1) * read s
                -- There is a hole here: this will error if 'op'
                -- (the first character) isn't '+' or '-'


                Return values



                The type of findFreq is



                findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])


                I see no reason why it can't return a single Integer. Perhaps you returned all values to debug initially, but once that's done you should switch back.



                It also seems to me like you were using 0 as an "error value," which is appropriate in other languages but generally frowned upon in Haskell. In this case, you can instead use Maybe to indicate failure and change your type signature to



                findFreq :: Integer -> [Integer] -> [String] -> Maybe Integer


                Like I mention later, this isn't necessary since we can condense and fix some logic, but I would recommend using Maybe instead in the future.




                curr and acc



                You do some switching around with your variables curr and acc which confused me a bit. I'd keep acc as the accumulation value for your frequency everywhere and call the list of visited values something like seenFreqs or prevFreqs.



                Correctness



                Repeating frequencies of 0



                Your code currently assumes the repeated frequency is the first nonzero repeated frequency. Thus, it fails for the +1, -1 test case. You could change the code to



                findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
                findRepeatingFrequency init nums xs =
                let (found, acc, lst) = findFreq init nums xs
                in found


                to accommodate that.



                This breaks your way of going through the list again if you don't find a repeat the first time, but fortunately there's a less obfuscated way to avoid your checking and continue: you can use cycle, which creates an infinite list consisting of the input list repeated infinitely.



                cycle :: [a] -> [a]

                Prelude> take 20 $ cycle [1,2,3,4]
                [1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]


                You can call findRepeatingFrequency on cycle input to prevent having to do the cycling yourself in the function.



                Efficiency



                Things go wrong for efficiency in findFreq. There are two problem points that make your code asymptotically inefficient.



                First, in the following line



                  in if next `elem` acc


                elem is an O(n) operation. You're calling it for each of the n elements in your input list, meaning that your function is at least O(n^2) (and it turns out that this is the final complexity).



                I checked the number of iterations required for my sample input and it took 142991 iterations to find a repeated frequency. An O(n^2) runtime is going to require about 10 billion iterations for the lookups alone. Ouch.



                Second is a more insidious mistake that is easy to overlook. In this line,



                   else let f = acc ++ [next]


                Appending to a list is an O(n) operation. Lists in Haskell are implemented as linked lists, and appending to the back of one cannot be amortized to O(1) like one might in Python's list or Java's ArrayList. You need to travel all the way to the back to add in a link.



                Fixing the second issue actually isn't very hard since you don't care about the ordering of the list. You can switch it to



                   else let f = next : acc


                to return to O(1) inserts.



                Fixing the lookups, however, requires a change of data structure.



                Introducing Data.Set



                Data.Set provides unordered sets with O(log n) lookup and insert time. Yeah, it's O(log n), but the total runtime for me when I checked the implementation was less than a second.



                I'm including a sample implementation of day 1 below that I've tested and confirmed on my inputs if you want to compare. However, you said you wanted pointers, so here's the pointers I'll give.




                • You can keep your code mostly the same (although I'd recommend making the style changes I suggested)

                • You will want to use two functions from Data.Set: member and insert.

                • Your end result will look a lot like a fold but with some differences in end conditions (kind of like findFreq)


                Sample implmentation



                Finally, here's a sample implementation.



                module Main where

                import Data.Set (Set)
                import qualified Data.Set as S

                -- This is a partial function
                parseInt :: String -> Integer
                parseInt (op:s) =
                case op of
                '+' -> read s
                '-' -> (-1) * read s
                -- There is a hole here, assuming valid input

                findRepeatingFrequency :: Integer -> Set Integer -> [Integer] -> Integer
                findRepeatingFrequency acc seen (x:xs) =
                if acc `S.member` seen
                then acc
                else findRepeatingFrequency (acc + x) (S.insert acc seen) xs

                partOne :: [Integer] -> Integer
                partOne = sum

                partTwo :: [Integer] -> Integer
                partTwo ints = findRepeatingFrequency 0 S.empty $ cycle ints

                main :: IO ()
                main = do
                file <- readFile "input.txt"
                let input = filter (not . null) $ words file
                let ints = map parseInt input
                print $ partOne ints
                print $ partTwo ints






                share|improve this answer










                New contributor




                cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.









                share|improve this answer



                share|improve this answer








                edited 6 hours ago





















                New contributor




                cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.









                answered 6 hours ago









                cole

                1664




                1664




                New contributor




                cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.





                New contributor





                cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.






                cole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Code Review Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.





                    Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                    Please pay close attention to the following guidance:


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f208832%2fadvent-of-code-2018-day-1-part-2-find-the-first-repeated-number-after-some-incr%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    What visual should I use to simply compare current year value vs last year in Power BI desktop

                    How to ignore python UserWarning in pytest?

                    Alexandru Averescu