DEV Community

loading...

Discussion on: Understanding Time Complexity with the First Puzzle of Advent of Code

Collapse
lauravuo profile image
Laura Vuorenoja

I actually implemented the latter "set version" with golang map strucuture, but still it was slower than looping the array. This puzzled me but then I realized that I was looping over the map structure when going through the values. And that is actually quite slow. So after changing the loop over the array and just "finding the result" from the map, I had found a solution that I was happy with :)

Collapse
lauravuo profile image
Laura Vuorenoja

Or almost happy 😂 Now I realized that there's no need to read all of the values at all. The file can be read line by line and the read values can be saved to the map until the match is found...

Collapse
annisalli profile image
Anniina Sallinen Author • Edited

Interesting! I'm not familiar with Golang, but googled and read that you can check the membership with

exists := set["Foo"] 
Enter fullscreen mode Exit fullscreen mode

If you know which number you're looking for (calculating 2020 - x = y), and I read the example above correctly, couldn't you just

exists := set[y] 
Enter fullscreen mode Exit fullscreen mode

Do you need to save the read values to a map, I'm not so sure? 🤔

Thread Thread
lauravuo profile image
Laura Vuorenoja

Yes, I mean that I use the map structure instead of set (I think go does not have sets 🤔 ). Let me paste here my pseudolike code:

func findValue: int
  cache := new key-value-storage
  for line = read-next-line from file:
    nbr := convert line to nbr
    want := 2020 - nbr
    if cache[want]:
      return want * nbr
    cache[nbr] = nbr
  return 0
Enter fullscreen mode Exit fullscreen mode

So I mean "saving to a map" this line cache[nbr] = nbr. Of course the value could be anything, only the key counts ☺️

Thread Thread
annisalli profile image
Anniina Sallinen Author • Edited

Ohh yeah now I see 😊