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.
performance programming-challenge haskell
add a comment |
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.
performance programming-challenge haskell
add a comment |
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.
performance programming-challenge haskell
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
performance programming-challenge haskell
edited 51 mins ago
200_success
127k15148412
127k15148412
asked 9 hours ago
dagda1
1795
1795
add a comment |
add a comment |
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
andinsert
. - 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
New contributor
add a comment |
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
andinsert
. - 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
New contributor
add a comment |
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
andinsert
. - 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
New contributor
add a comment |
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
andinsert
. - 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
New contributor
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
andinsert
. - 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
New contributor
edited 6 hours ago
New contributor
answered 6 hours ago
cole
1664
1664
New contributor
New contributor
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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