[2020, Day 22, Part 2] Is there a way to speed up the state checking?

• AdventOfCode2020

  23 29 2.6 Rust

  Solutions to all 25 AoC 2020 problems in Rust :christmas_tree:

A solution that will work with very high probability (which I used here) is to store a hashset of hashes, HashSet. E.g you compute a hash for the two queues and see if that hash has already been seen. There is a very, very, small probability of a hash collision, but in practice this works.

• advent-of-code-2020

  1 5 0.0 Go

  Advent of code 2020 using Golang (by CodingNagger)

Personally, I had a map with string keys and boolean values unique to each game. Upon starting a new round, I would compute the state under string form, something like "1,2,3|8,9,7" where 1,2,3 are the cards for player 1 and 8,9,7 the cards from player 2. If the map contains that key I end the game with a player 1 win if not I add a new entry. There you get a complexity of O(1) to lookup values. My code is there: https://github.com/CodingNagger/advent-of-code-2020/blob/master/pkg/days/day22/computer.go

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

Suggest a related project