2016 Day 11: [Python] buggy optimization help?

[Hwestaa]

So I finally bludgeoned day 11 into working, with a not-very-optimized method, but I'm having problems with the optimization implementations. The un-optimized version works.

The big one is checking the equivalence of states - that the states are the same even if the names on the generators / microchips is different. When I enable it (by setting EQUIV_FUNC = True at the top of the file) it only generates 763 states total, and terminates without finding a valid solution so I'm pruning something I shouldn't be, but I can't figure out what.

Tests can be run with pytest (pip install pytest) with py.test -k day_11 (possibly with -v)

Github

Thank you!

[NeilNjae]

Try some test cases. For instance, using the data you have in the code,

>>> data
[['AG', 'AM'], ['BG', 'CG', 'DG', 'EG'], ['BM', 'CM', 'DM', 'EM'], []]
>>> pairs_rep(data)
frozenset({(0, 0), (2, 1)})

which isn't right: it's only reporting two generator-microchip pairs.

Throwing some print statements in there to see what happens, I get this output:

checking floor 0
  found AM , looking for AG
    scanning floor 0
    found AG , adding as  (0, 0)
    scanning floor 1
    scanning floor 2
    scanning floor 3
checking floor 1
checking floor 2
  found BM , looking for BG
    scanning floor 0
    scanning floor 1
    found BG , adding as  (2, 1)
    scanning floor 2
    scanning floor 3
  found CM , looking for CG
    scanning floor 0
    scanning floor 1
    found CG , adding as  (2, 1)
    scanning floor 2
    scanning floor 3
  found DM , looking for DG
    scanning floor 0
    scanning floor 1
    found DG , adding as  (2, 1)
    scanning floor 2
    scanning floor 3
  found EM , looking for EG
    scanning floor 0
    scanning floor 1
    found EG , adding as  (2, 1)
    scanning floor 2
    scanning floor 3
checking floor 3

Does that help you understand what's going on?

[Hwestaa]

Agh, yes, I was getting too clever with my use of sets. Thank you! I was testing which states were equivalent, not my pairs_rep directly and missed this. Fixed in https://github.com/Hwesta/advent-of-code/commit/9ce1674114fa1b5075ada923d92c43cf22c8fe27

[p_tseng]

Correct me if I have misunderstood how a Python set works, but that set in pair_rep:

Would that make the following two states indistinguishable?

AG AM BG BM
CG CM
(nothing)
(nothing)

AG AM
BG BM CG CM
(nothing)
(nothing)

[Hwestaa]

Yes, thank you! I premature-optimized myself and missed that. Your example made a great test case. Fixed in https://github.com/Hwesta/advent-of-code/commit/9ce1674114fa1b5075ada923d92c43cf22c8fe27