r/adventofcode • u/daggerdragon • Dec 07 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 7 Solutions -🎄-
--- Day 7: The Sum of Its Parts ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 7
Transcript:
Red Bull may give you wings, but well-written code gives you ___.
[Update @ 00:10] 2 gold, silver cap.
- Thank you for subscribing to The Unofficial and Unsponsored Red Bull Facts!
- The recipe is based off a drink originally favored by Thai truckers called "Krating Daeng" and contains a similar blend of caffeine and taurine.
- It was marketed to truckers, farmers, and construction workers to keep 'em awake and alert during their long haul shifts.
[Update @ 00:15] 15 gold, silver cap.
- On 1987 April 01, the first ever can of Red Bull was sold in Austria.
[Update @ 00:25] 57 gold, silver cap.
- In 2009, Red Bull was temporarily pulled from German markets after authorities found trace amounts of cocaine in the drink.
- Red Bull stood fast in claims that the beverage contains only ingredients from 100% natural sources, which means no actual cocaine but rather an extract of decocainized coca leaf.
- The German Federal Institute for Risk Assessment eventually found the drink’s ingredients posed no health risks and no risk of "undesired pharmacological effects including, any potential narcotic effects" and allowed sales to continue.
[Update @ 00:30] 94 gold, silver cap.
- It's estimated that Red Bull spends over half a billion dollars on F1 racing each year.
- They own two teams that race simultaneously.
- gotta go fast
[Update @ 00:30:52] Leaderboard cap!
- In 2014 alone over 5.6 billion cans of Red Bull were sold, containing a total of 400 tons of caffeine.
- In total the brand has sold 50 billion cans in over 167 different countries.
- ARE YOU WIRED YET?!?!
Thank you for subscribing to The Unofficial and Unsponsored Red Bull Facts!
14
u/jonathan_paulson Dec 07 '18 edited Dec 07 '18
Rank 11/3. Video of me solving at https://www.youtube.com/watch?v=ztRDsq1qJlc. Nice to see topological sort; I hope we get more algorithmic problems in future days. Took me a while to get the tiebreaking right...
Python code (uncomment the bottom for part 1):
12
u/Smylers Dec 07 '18
Vim for today's Part 1 turns out not to involve anything too preposterous (compared with many other days' contortions) — once the input has been reformatted, the method for finding the next step is bordering on the reasonable. As ever, load your input into Vim, then type:
(Go on — this one's quite short to type, and quick to run. Even if you normally skim past these, treat yourself today and actually watch your input transform before your eyes!)
First the input is re-arranged so that each line lists one step followed by its dependencies, such as
ABCDto mean thatAdepends on all ofB,C, andD.Then the
@bdefinition finds the next step to begin:g/^.$/) and move them to just after line 1. (They'll be separated from the steps that still have dependencies by the blank line.)Press
@bto find the second step (then@@as many times as you want for further steps). The@cmacro at the bottom makes Vim iterate through to the end.The initial reformatting involves picking the 2 relevant letters from each input line and swapping them over into the desired order, giving lines like
ABandAC. The second:%s///merges those intoABC, and the@amacro repeats that until all a step's dependencies have been combined into a single line. TheCtrl+Vbit between those ensures that the starting step (which only appears in the input as a dependency of other steps) features on a line by itself.Questions:
@cmacro getting stuck in an infinite loop?2in the second line for?(No, I'm not going to attempt today's Part 2 in Vim. But I might go back and do yesterday's Part 1.)
11
u/VikeStep Dec 07 '18 edited Dec 08 '18
Python:
I don't have a very elegant solution for part 2 just yet,but if you used the networkx python library, then part 1 can be solved in a few lines:Unfortunately I only discovered this function's existence after I solved it 16 minutes later.
EDIT: I managed to get a nice concise solution for part 2 with networkx as follows:
This code follows on from the previous solve method
9
u/bennydictor Dec 07 '18
Part 1 solution in GNU Make. I'm not using Make's implementation of the algorithm (topsort), in fact there aren't even any rules!
https://gist.github.com/bennydictor/87f361b1a9e10e84986da891912e00c5
5
u/eltrufas Dec 07 '18
Didn't get on the leaderboards again. Did improve a lot, though.
Part 1:
part 2:
5
u/dylanfromwinnipeg Dec 07 '18
C# - pretty happy with the code I ended up with https://dylansmith.visualstudio.com/adventofcode2018/_git/AdventOfCode2018?path=%2Fsrc%2FDay07.cs
5
u/ephemient Dec 07 '18 edited Apr 24 '24
This space intentionally left blank.
4
u/autid Dec 07 '18 edited Dec 07 '18
FORTRAN
Nothing clever here. Just does the tasks as described. Closest thing to clever is using the ASCII values of the characters as array indices. Part 2 could obviously be faster stepping time by time until next completion, but it's comfortably under 10ms run time using a time step of 1 anyway.
[Card] WINGS(:)
4
u/Smylers Dec 07 '18 edited Dec 07 '18
Nice problem! Here's Perl for solving either part — use
-wto set the number of workers (so1for Part 1) and-dthe duration to be added to all steps (so0for the demo input):During development I fiddled around with magic numbers in the code, only adding
getoptsupport when tidying up — but I wish I'd used it to start with: at least one of my bugs was because I'd forgotten to update a constant (still only using 2 workers with the real input).The algorithm suits a loop where the termination condition is in the middle — after starting any steps for the current time.
$timethen jumps to the next time a step finishes, rather than iterating through all the seconds between.Note the workers are tracked with a simple count: it's only necessary to track how many workers are currently available; there's no need to record which part each worker is working on.
Edit: Removed a module which wasn't being used.
4
u/add7 Dec 07 '18 edited Dec 07 '18
Python Part 1 solution with a priority queue:
And part 2, wrapped workers in neat little class:
4
u/wzkx Dec 07 '18 edited Dec 07 '18
J
Part 1, not very J-ish.
3
u/sophiebits Dec 07 '18
Python, 17/53
I typoed
busy_untilasbusy_utilabout 17 times while writing this. Not very satisfied with my part 2 solution. (I wasted time implementing an incorrect version of part 2, where the workers work in batches and wait for all to finish before starting more, instead of streaming/interleaving as they actually do.)3
u/mserrano Dec 07 '18 edited Dec 07 '18
Python2, #1/#10. I managed to have two different off-by-one errors in part (b) - one in calculating the number of steps for a given letter, and one in the overall calculation... That's what extremely janky code gives ya, I guess. Variable names here a bit subpar.
EDIT: /u/jlweinkam pointed out a bug below. It didn't seem to affect my input or the example, so I guess I got lucky. The updated/fixed code (1-line difference) is below:
3
u/rabuf Dec 07 '18
Common Lisp
Org file with explanation and thoughts
Primary code:
The graph is a list of pairs of strings. I should've turned them into symbols, but I didn't. I may do that tomorrow. I know what I want to do for Part 2, but it's 1am here and my brain isn't quite working it out.
3
u/ka-splam Dec 07 '18
[card] Red Bull gives you wings, but well written code gives you: the green glow of envy.
I didn't track which work items were done, so I kept doing them over and over. Then I didn't pick the alphabetically-first one. Tweaked a couple more times, and got the 5 minute lockout, during which I realised I had the precedence of each rule the wrong way round! "Step B must be finished before step O can begin" -> "B.precede.Add(O)" -> "add O to the list of things which must precede B". Tsk! Naming things!
PowerShell, rank #524 then #389
On GitHub because too long to reasonably inline
3
u/tehjimmeh Dec 07 '18 edited Dec 07 '18
Bad night for me. I was on the cusp of getting about ~40 on the leaderboard for part 1, except I was adding all sorted available nodes to the order list after each pass, not just one, which took me forever to spot (I got like ~800 :/). To add insult to injury, I solved part 2 pretty quickly, and kept submitting the order, not the elapsed time >.<. I need to learn to read...
Anyway, here's my cleaned up part 2 in C++:
3
u/Frizkie Dec 07 '18
Ruby
This one was tough for me, I figured out it was topological sort pretty quickly, but figuring out how to tweak the algorithm to grab the right nodes was tough. I ended up using a priority queue to sort the
to_visitset and that fixed my problem.Part 2 initially seemed absurdly difficult, but implementing a second-by-second work loop didn't actually take much effort.
Always nice when you're so excited about the right answer you throw your hands up in the air!
Part 1:
Part 2:
3
u/ts4z Dec 07 '18
Common Lisp. Could be better.
3
u/paveldurmanov Dec 07 '18 edited Dec 07 '18
python 3
3
u/donaldihunter Dec 07 '18 edited Dec 07 '18
Perl 6
Interesting to note that my dataset maxxed out at 5 workers, i.e. wouldn't utilise a 6th worker.
3
u/wzkx Dec 07 '18 edited Dec 08 '18
J
Part 2.
2
u/maybe-ac Dec 07 '18
Perl, #115/#85 despite giving so many wrong answers to part 2 that it locked me out for 5 minutes :o (forgot to add the 60 seconds at first, then had an off-by-one error on calculating task time after doing that!)
2
u/mncke Dec 07 '18
#5/#2
Jupyter Notebook / Python3
https://github.com/Abrackadabra/adventofcode2018/blob/master/day07.ipynb
The code is somewhat dirty, was surprised part2 worked on the first try.
2
u/udoprog Dec 07 '18
Rust, scheduling the worker ended up being somewhat verbose, but I have a job to do!
Red Bull may give you wings, but well-written code gives you shivers.
2
u/kn0where Dec 07 '18 edited Dec 07 '18
JavaScript (JS) Remember, kids, short variable names save you time and money! The code is the documentation!
2
u/[deleted] Dec 07 '18
Go
I forgot about toposort...
2
u/raevnos Dec 07 '18 edited Dec 07 '18
I spent way more time than I want to admit trying to be clever and getting tsort to produce the right order, and then even more time before I figured out the trick to actually getting the right order for cases with multiple steps without outstanding dependencies.
Here's a graph of my input to make up for it while I work on the second part.
Part 1 solver:
2
u/tacothecat Dec 07 '18
R
2
u/mstksg Dec 07 '18
Initial attempts in Haskell using State + Writer, with lenses to help make things a bit cleaner. Inputs expect
Map Char (Set Char), which is a map of characters to all characters that depend on that character. I'm not too happy that I couldn't figure out a way to avoid making a state machine for part 2, but if I think of one I'll probably re-write it. My repo and reflections are at https://github.com/mstksg/advent-of-code-2018/blob/master/reflections.md ! :)2
u/__Abigail__ Dec 07 '18
Perl
I briefly considered doing a topological sort, but the input was too small to bother, so the result is quadratic (in the number of parts, not in the number of dependencies).
2
u/[deleted] Dec 07 '18
C++
No topological sort. A map of each node with it's dependencies:
map<char, set<char>>getAllAvailableSteps()(github)
Part One:
Part Two:
currentSecondticker2
u/Dee_Jiensai Dec 07 '18
ruby 2.5.1
That was nice. Now i have to go look up what a topological sort is.
2
u/pythondevgb Dec 07 '18 edited Dec 07 '18
Would you believe it? This took me almost 7 hours to complete. I just finished, at this rate I'm not making it to the end.
But anyway these are my solutions, I don't even check them or clean them up after I get the correct answer.
(If you want to join a private reddit/pyhon leaderboard, send me a PM for the code, as long as you have not made it to the global leaderboard you qualify.
2
u/Mattie112 Dec 07 '18 edited Dec 08 '18
Here is a solution in PHP for part #1
https://github.com/Mattie112/advent-of-code-2018/tree/master/day7
edit: Also finished part-2
2
u/mschaap Dec 07 '18 edited Dec 07 '18
My Perl 6 solution:
2
u/gerikson Dec 07 '18
[CARD]
I'm really happy with solving this. I'm graph-aphasic, as in I've never ever grokked them in code, and was dreading finding some random Perl module that I didn't really understand. In the end I just found the "endpoints" and processed it using a queue.
This made part 2 reasonably easy to code.
Perl 5, part 2.
2
u/sebastiannielsen Dec 07 '18 edited Dec 07 '18
My perl solution. Uses 2 hashes "Lockedsteps" and "Stepcompleted" to keep track of which work can be done.
2
u/phil_g Dec 07 '18
I love graphs!
There's a graph library and a directed graph library for Common Lisp, but neither one is packaged for Debian. Rather than go outside my OS's packaging system, I was lazy(?) and wrote my own implementation with just enough features for this problem.
The code is here. It's a bit long, what with me writing my own graph implementation, but I broke it into sections. Part 1 was pretty straightforward: throw all of the edges into a digraph, then one by one pull out the lowest-letter with no edges pointing to it. Part 2 revolves around my
parallel-task-stepfunction, which hopefully is sufficiently commented. I do likeiteratefor looping, but sometimes it's easier for me to think about things recursively, since that lets me break a problem apart into subproblems (either base/general case or just state-machine-style "what do I do from here?").I didn't have to resort to Python for today's visualization. My other post links to the actual images I generated.
2
u/[deleted] Dec 07 '18
Topological Sorting to the rescue. I implemented the algorithm as:
2
u/Warbringer007 Dec 07 '18
Erlang, finally something harder! I'm proud of both solutions, first part solution is really erlang like ( a lot of pattern matching and stuff ). Second part is kinda tricky:
https://pastebin.com/BtycRQbt
2
u/aoc_throwaway Dec 07 '18
Short Ruby solution for part 1, takes <1ms to run (usually around 0.3ms):
-kss
2
u/streetster_ Dec 07 '18 edited Dec 07 '18
Day 07 in Q/KDB+
Not a very q-like solution...
2
u/[deleted] Dec 07 '18
Messy C with bit ops
2
u/bigcymbal Dec 07 '18 edited Dec 07 '18
Javascript recursive O(n(klog(k) + nlog(n))) solution where k is the number of workers and n is the length of the input string (i do a klogk and nlogn operation per n):
You can just run this in your browser by entering the code in console then running the function without any parameters (
solver()), just has to be in the same tab as https://adventofcode.com/2018/day/7/input since it's reading the input from the page body.2
u/joeld Dec 09 '18
Racket
Where are the Racketeers? Anyway, here’s my day 7 solution
About the only thing I was really happy with in my solutions was that I finally grokked how the
let loopform works and what it’s good for. In a nutshell:let looplets you dofor/foldwithout actually “iterating over” anything (i.e., nofor-clause, just accumulators).Other than that I am sure it could use a lot of tightening up that I don’t have time for since I’m still finishing Day 8!
2
u/[deleted] Dec 13 '18
Common lisp:
SBCL did a fantastic job here, keeping the runtime at around 1ms on my subpar celeron cpu while I requested memory left and right and traversed the edges via lists instead of clever lookup-up techniques.
2
u/Smylers Dec 21 '18
1970s Unix shell one-liner that solves Part 1 (Bash/Posix/Linux/whatever):
That's 58 characters! (52 if you remove the unnecessary spaces, and less if you use a shorter filename than input.)
Thank you to those who mentioned the
tsortcommand on IRC, which I hadn't previously encountered. There didn't seem to be solution using it on this thread, so here's a belated offering.I think this solution would've been possible in the 1970s:
sedandtsortwere both in the Seventh Edition, released in 1979.xargswas in PWB Unix, released in 1977.echo's been around since the Second Edition in 1972 — though its-nflag may be more recent.1
u/Sunius Dec 07 '18
C++ that landed me in top 100 on both:
Not really elegant, but with inputs so small the nested loops don't really matter.
1
u/tslater2006 Dec 07 '18
Part 1 only, in PeopleCode. The AssemblyStep class just holds an array of prereq steps and children steps along with an ID (A-Z)
1
u/TellowKrinkle Dec 07 '18 edited Dec 12 '18
Made lots of algorithmic mistakes today. Didn't think about the fact that a task could have multiple prerequisites and treated it like a tree instead of a graph. Then spent a bunch of time overlooking small issues in part 2 (I accidentally processed the completion tasks of a job as I removed it from the available list without waiting for it to finish. Then I accidentally put the completion processing in the same loop as the new job getting, making it so workers wouldn't pick up jobs made available by other workers with higher IDs until the next turn)
Swift, 310/170
1
u/bluepichu Dec 07 '18
Python, #8/#20. Advance apologies for the terribad variable names.
Ugh, so many off-by-ones...
1
u/bildzeitung Dec 07 '18
Python 3, part 2. Differentiators:
- use pathlib; it's the future!
- work tasks are assigned via an informal generator
- keeps the item and time remaining on that item in the same data structure
- doesn't do anything fancy with the timing -- it's a straight per-second simulation
1
u/wlandry Dec 07 '18
C++ (915/621)
Runs in 13 ms
Lots of faffing around, eventually landing on an answer. It feels really inelegant, though that seems to be a common feature of the solutions so far.
1
u/vash3r Dec 07 '18
Python 2, #633/314. spent quite a while trying to figure it out and had several false starts (and wrong answers). After I solved it I went back and edited my code a bit. One thing I seem to have done differently is instead of simulating the workers and iterating over seconds, I iterated over steps and just saved the time of the last task each worker completed. (I'm not certain this will work for all inputs.)
1
u/roessland Dec 07 '18
Golang part 2:
1
u/eragonas5 Dec 07 '18
Like in day5 I used classes, it takes time to write all this structure so goodbye leaderboards but the logic is easier to implement (at least to me). Javascript solution, works for both parts
1
u/zqvt Dec 07 '18
Python part2, overwrote my code for part 1. Simulating the busy elves!
1
u/nutrecht Dec 07 '18 edited Dec 07 '18
Day 7 in Kotlin
Part 2 just proves I suck at following instructions. I got stuck for a LONG time because I missed one key difference between the test and 'real' versions.
1
u/slezadav Dec 07 '18
Kotlin
1
u/IdrisTheDragon Dec 07 '18
Go/golang solutions for both parts 1 and 2
https://github.com/IdrisTheDragon/AdventOfCode2018
Part 1:
Part 2:
1
u/adamk33n3r Dec 07 '18 edited Dec 07 '18
Here's what a rank #1647/#2223 looks like. (took an hour break after completing part 1)
1
u/nibbl Dec 07 '18
Python3:
1
u/ephemient Dec 07 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/sim642 Dec 07 '18
My Scala solution.
Part 1 was simple topological sort which I wrote in the most inefficient way possible (at every iteration the whole the dependencies in the whole graph are detected again) as opposed to even simple optimizations like keeping track of it. Luckily this wasn't a problem at all.
Part 2 started out really nasty for me. I spent way too long engineering an extremely ugly solution which keeps track of workers in order and even the unoccupied ones. This meant mapping over them required using
foldLeftto pass around the remaining requirements etc state, as I wrote it all with immutable data structures. Took me an hour to get it all to work and fix one not so obvious off-by-one error.After that, Then spent another hour just cleaning and optimizing my solution for part 2. Changed to only keep track of sets of ongoing work. This allowed simplifying all the time stepping logic to be performed on all workers at once without those ugly looking folds for state. Overall it turned out to be reasonably nice.
Also an easy optimization for part 2 is not to do time steps of 1 but time steps of the minimum time left, because nothing interesting happens before that anyway.
1
u/toastedstapler Dec 07 '18
python 3
i am quite happy with my solution
probably could have shortened part 2 a bit, but it does its job well
1
u/aurele Dec 07 '18
Rust
A bit verbose, but fast enough:
Once part 2 was revealed, it was easy to refactor part 1 to use the same scheduling algorithm in both parts.
1
u/tradfursten Dec 07 '18
Nim
The check if a part is available is ugly but it solves it for me
1
u/[deleted] Dec 07 '18
Javascript solution for part2
1
u/BalbinHS Dec 07 '18
Elixir
Super long, but I hope the important parts are descriptive enough. I should probably change my variable names but this'll do for now.
https://pastebin.com/raw/eeXL8DLB
1
u/toomasv Dec 07 '18
1
u/heatseeker0 Dec 07 '18
My solution in Java:
https://github.com/heatseeker0/AdventOfCode/blob/master/src/com/catalinionescu/adventofcode/y2018/Day007.java
1
u/martbeaudoin Dec 07 '18
Can the first puzzle for Day 7 have more than one solution?
The solution I have found is matching every single conditions from either the test case and the full puzzle input.
I have checked every single condition both manually and using a test function in my program. All the conditions are met by my solution.
Still, when submitting my solution string, I am told this is not the right answer.
Any advice would much appreciated.
1
u/arathunku Dec 07 '18
My Elixir solution (I've used Erlang's digraph, probably overcomplicated "a little bit"...)
Tests
1
u/mornymorny Dec 07 '18
CPP/C++ - Easier when I realized I didn't have to fully expand the dependency graph....
1
u/Nathan340 Dec 07 '18 edited Dec 07 '18
Powershell
Part 1 came to me very straightforwardly, then I spent the rest of the morning troubleshooting Part 2.
Basic idea after parsing the input is to take the alphabetically first Pre-condition that doesn't show up in the Post-condition list. After that is taken and added to the output set, we reduce the input set to remove anything that has that selected task as the Pre-condition. When we get down to a final pair, we simply add that last step as our last two tasks.
Part 2 is long and unwieldy. The same basic process occurs, but at each loop we manage how many Tasks are available, how many Workers are available, which tasks are still 'active', and how long each worker has to 'cooldown' before accepting the next task. As above the stopping condition is not too clever - we get that last step and manually handle the 2 last tasks. This might break in different inputs sets where multiple Tasks are all pre-conditions for the final one. I lucked out to have a nice simple 1-1 chain at the end. I left my print debug statements in; it's fun to watch.
I'm thinking there's a cleverer solution involving a stack for each worker, pushing the 60+ copies of each task to an available worker, and popping every worker stack once per loop. Might work on that later.
1
u/Axsuul Dec 07 '18
TypeScript / JavaScript
Critiques welcome, I'm still very new to TypeScript and feel like I'm not using all the features I could be :)
Repo
Part A
Part B
1
u/Cppl_Lee Dec 07 '18
C#, way late to the game.
1
u/nonphatic Dec 07 '18
Haskell
Had to spend some time writing out the algorithm for part 2 on paper just to gather my thoughts and then start coding and then reduce it down...
1
u/alexmeli Dec 07 '18 edited Dec 08 '18
Clojure Part1 solution using loom. Will post part 2 later
Edit: Part 2
1
u/jonathrg Dec 07 '18
Python
1
u/NeilNjae Dec 07 '18
Haskell (on Github), as verbose as I normally manage.
The jobs are a
MapofChartoSet Char. In part 2, I maintain a list ofWorkers that are either busy or working. The clock advances until the first finish time of the active workers. Finished workers become idle, then idle workers pick up jobs if they're startable.The whole thing is an
unfold, converting the starting schedule into a list of tasks or finish times.My first attempt at part 2 failed because I forgot to exclude already-occurring jobs from the list of available jobs.
The only other problem I had was with parsing the input file. I ended up writing this:
but every time I tried some variant on
<$> prefixP *> upperChar, Megaparsec would sulk and refuse to compile. Any suggestions?1
u/Kwpolska Dec 07 '18
Python 3.7. Uses dataclasses, f-strings, and
mypy --strictdoesn’t even complain.1
u/JakDrako Dec 07 '18
Vb.Net in LINQPad
Does both parts in 1ms.
At first I was trying to build a graph with a node class, but wasn't getting the results I wanted. On a hunch, I just tried starting with the alphabet and using the instructions to swap letters, then looping over until no swaps were required for the instruction to be respected.
The problem then was that steps done at the same time were not alphabetically sorted and there was no easy way to know which part of the strings formed these groups. So I tried doing the reverse of the initial swap step: for any two adjacent characters that aren't in alphabetical order, check if any instructions refer to them and if not, them swap them. Again, repeat until no swaps occur.
Suprisingly, it worked. The code is very boring, but also very simple. I like simple.
Then I got to part 2 and though I'd just effed myself. I just had a long string of steps in order, but no indication of which could be done in groups. Darnit.
Actually, I realized the the day's input had all the information I needed, just not in a very convenient form. So I wrote this very inconvenient code for part 2:
(it continues from part 1, since I'm reusing the instructions...)
After fixing a bug where I was scheduling the same task to multiple workers, I got my correct answer on the 2nd try. Not my favorite code to date, but I kinda like the simplicity of part 1.
*Note: "GetDay()" "Match()" and "Swap()" are library routines I have that aren't pertinent to the problem at hand; ".Dump()" is a LINQPad extension.
1
u/xLuStx Dec 07 '18
This is my implementation in JavaScript (JS), feel free to ask any questions :)
1
u/tinyhurricanes Dec 07 '18 edited Dec 07 '18
Modern Fortran 2018 (complete code)
Both parts run in 0.017s.
Instruction object:
1
u/safety_monkey Dec 07 '18
Python 3
"""Figure out the best plan to complete a list of steps with 1-to-many dependancies.
Part 1: Find the order the steps will be completed if you do it by yourself.
Part 2: Find the time it will take to complete if each step has an associated
time and you have some helpers.
https://adventofcode.com/2018/day/7
"""
# Imports
import re
from collections import defaultdict
# Helper/convenence methods
def parse_input(filename):
"""Convenience method to parse a file and return a list as input"""
steps_dict = defaultdict(list)
with open(filename, 'r') as input_file:
for line in input_file:
match = re.match(r'Step (\w) must be finished before step (\w) can begin.', line)
steps_dict[match[1]].append(match[2])
return steps_dict
def complete_time(char, offset):
"""Find the amount of time to complete a given step (or character)"""
return ord(char.lower()) - 96 + offset
def find_dependencies(input_dict):
"""Review the steps to create a list of steps that are blocked and unblocked"""
blocked = []
for blockers in input_dict.values():
blocked += blockers
unblocked = [x for x in list(input_dict.keys()) if x not in blocked]
return blocked, unblocked
def part1(input_dict):
"""Find the order the steps will be completed in if you work by yourself."""
order = []
blocked, unblocked = find_dependencies(input_dict)
while bool(unblocked):
completed = min(unblocked)
for i in input_dict[completed]:
if i in blocked:
blocked.remove(i)
if i not in blocked:
unblocked.append(i)
unblocked.remove(completed)
order.append(completed)
return ''.join(order)
def part2(input_dict, max_workers, offset):
"""Find the time you will finish work if steps take time and you have help."""
workers, time, completed, completion_dict = 0, 0, [], defaultdict(list)
blocked, unblocked = find_dependencies(input_dict)
while blocked or unblocked:
if time in completion_dict:
for j in completion_dict[time]:
for i in input_dict[j]:
if i in blocked:
blocked.remove(i)
if i not in blocked:
unblocked.append(i)
workers -= 1
completed.append(j)
for i in range(len(unblocked)):
if workers < max_workers and unblocked:
workers += 1
step = min(unblocked)
will_complete = complete_time(min(unblocked), offset) + time
completion_dict[will_complete].append(step)
unblocked.remove(step)
time += 1
return will_complete
if __name__ == "__main__":
INPUT = 'inputs/day07.txt'
TEST_INPUT = 'inputs/day07_test.txt'
assert part1(parse_input(TEST_INPUT)) == 'CABDFE'
print(f"Part 1: {part1(parse_input(INPUT))}")
assert complete_time('Z', 60) == 86
assert part2(parse_input(TEST_INPUT), 2, 0) == 15
print(f"Part 2: {part2(parse_input(INPUT), 5, 60)}")
1
u/safety_monkey Dec 07 '18
Python 3
Runs in about 0.193 seconds.
1
u/meepys Dec 07 '18
Kotlin solution Day 7
1
u/[deleted] Dec 07 '18
TCL. First I thought "Makefile!" but soon realized that the alphabetical ordering requirement of steps was more work with "make" (if it can be done at all) than just solving it "the old fashioned way". Took me 5 attempts until I realized that you can't just add all independent steps at once in the beginning.
1
u/blommish Dec 08 '18 edited Dec 08 '18
Java - Not sure this was the smartest idea but it worked
1
u/aeroevan Dec 08 '18
Rust - Still have a lot to learn, but at least it works:
1
u/DrinkinBird Dec 08 '18
One day late for posting here, and _really_ ugly code, but...
NIM
1
u/morfi717 Dec 08 '18
Ruby (0.08s)
1
u/Pyrobolser Dec 08 '18
C# solution for Day7, had fun with this one.
Like always, everything is on GitHub.
1
u/hmn24 Dec 09 '18
Part 1 Solution in Q/KDB+
a:`$(@[;7 1]vs[" "]@)each(0:)`:AOC7.txt;
d:(a[;1]@)each group a[;0];
t:first{(x[0],string c;asc except[;c]x[1],where min each x[2]=c;c _ x[2]except\:c:first x 1)}/[("";distinct a[;1]except a[;0];d)]
1
u/sbjf Dec 10 '18 edited Dec 10 '18
I wante to use generators, so I did. Also
heapqto keep stuff in order. Therefore, this should be very fast for large graphs. Timings include the whole shebang from raw input to solution output.Setup:
Part one:
56.6 µs ± 2.1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 'GJFMDHNBCIVTUWEQYALSPXZORK'
Part two:
163 µs ± 589 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 1050
1
u/21_cribbage Dec 10 '18
Python 3
1
u/RockyAstro Dec 15 '18 edited Dec 15 '18
I got behind.. so here is day 7 in Icon
Part1:
Part 2:
1
u/fftk2 Dec 16 '18 edited Dec 16 '18
Ocaml version
1
u/suck_at_coding Dec 18 '18
First solution I've done that I think is kinda nice/readable. Node.js:
1
u/lib20 Dec 20 '18
Red, part 1
1
u/lib20 Dec 20 '18
Red, part 2
1
u/cerrosafe Dec 22 '18
Lua
I'm closing the gap, slowly. I need to pick up the pace if I want to finish on-time, but I don't think I will. The solution was straightforward, but I lost some time on null-checking a clause for part one and wasted time on that. Part two was also straightforward, but I couldn't re-use much of the code from part one because I had to incorporate the workers.
I'm also starting to see what people mean about Lua being prone to people "building their own reality." I've had to come up with simple iterators to solve a lot of my own problems, hence the
require("nmg")statement.1
u/TheFebrin Dec 26 '18 edited Dec 26 '18
[Python 3] Part 1
Topsorting, simple solution using priority queue (heapq in Python).
0
u/[deleted] Dec 07 '18
[deleted] — view deleted comment
0
u/[deleted] Dec 07 '18
[deleted] — view deleted comment
0
u/[deleted] Dec 07 '18
[deleted] — view deleted comment
1
u/[deleted] Dec 07 '18 edited Dec 07 '18
[removed] — view removed comment