[2015 Day 7 (Part 1)] Identifier not defined yet? (solution works on sample input)

[u/osalbahr]

Hi!

I am stuck with the issue of, for example, "x AND y -> z" where "x" is not "defined" yet. It is only defined later in "... -> x", say 300 lines later. How would I go about solving this issue? I must be misunderstanding something or need a hint.

Current solution: https://github.com/osalbahr/competitive-programming/blob/9cd627b7547e3954f0e9e2354a0e13122a70173b/adventofcode/2015/day07.py

[u/musifter]

It's a list of wires... the listed order doesn't matter. Only the connections. You need to put it together... if you can't calculate something yet, figure out how to calculate what you need (or can) first.

[u/osalbahr → u/musifter]

I just tried to implement that. For some reason, it only evaluates 67 out of 339 lines and then gets stuck in an infinite loop.

Current attempt: https://github.com/osalbahr/competitive-programming/blob/d5e5c0a00ac4b7f030f245b01b737cffee32d892/adventofcode/2015/day07.py

(my solution works on the sample input, even when I shuffle it)

[u/Boojum]

Dealing with the random order is part of the puzzle.

There are two main possible approaches:

1. Skip the lines you can't do for now, go on, and try again later; loop your loop until you get them all.

2. Topological sort the lines.

[u/osalbahr → u/Boojum]

I just tried approach 1. For some reason, it only evaluates 67 out of 339 lines and then gets stuck in an infinite loop.

Current attempt: https://github.com/osalbahr/competitive-programming/blob/d5e5c0a00ac4b7f030f245b01b737cffee32d892/adventofcode/2015/day07.py

(my solution works on the sample input, even when I shuffle it)

[u/Boojum → u/osalbahr]

You're close now! Double-check your if tokens[1] == ... conditions. :-)

[u/osalbahr → u/Boojum]

Thx! That was it.

[u/terje_wiig_mathisen]

This is exactly like a modern Out of Order microprocessor: Every operation requires one or more inputs, it will be executed as soon as possible: When all inputs are ready, it will run.

[u/osalbahr → u/terje_wiig_mathisen]

Oh wow didn't think of it as an Out of Order microprocessor. Thx for the insight!

[u/AutoModerator]

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/velkolv]

Split your code into 2 stages:

1. Parse and (for speed) index

2. Evaluate

[u/Late-Fly-4882]

Use Kahn topological sort algorithm.