Advent of Code, for those not in the know, is a yearly Advent calendar (since 2015) of coding puzzles many people participate in for a plenary of reasons ranging from speed coding to code golf with stops at learning a new language or practicing already known ones. I usually write boring C++, but any language and then some can be used. There are reports of people implementing it in hardware, solving them by hand on paper or using Microsoft Excel so, after solving a puzzle the easy way yesterday, this time I thought: CHALLENGE ACCEPTED! as I somehow remembered an old 2008 article about solving Sudoku with aptitude (Daniel Burrows via archive.org as the blog is long gone) and the good same old a package management system that can solve [puzzles] based on package dependency rules is not something that I think would be useful or worth having (Russell Coker). Day 8 has a rather lengthy problem description and can reasonably be approached in a bunch of different way. One unreasonable approach might be to massage the problem description into Debian packages and let apt help me solve the problem (specifically Part 2, which you unlock by solving Part 1. You can do that now, I will wait here.) Be warned: I am spoiling Part 2 in the following, so solve it yourself first if you are interested. I will try to be reasonable consistent in naming things in the following and so have chosen: The input we get are lines like
This article was written by David Kalnischkies on apt-get a life and republished here by pulling it from a syndication feed. You should check there for updates and more articles about apt and EDSP.
acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab cdfeb fcadb cdfeb cdbaf. The letters are
wiresmixed up and connected to the segments of the displays: A group of these letters is hence a
digit(the first 10) which represent one of the digits 0 to 9 and (after the pipe) the four
displays which match (after sorting) one of the digits which means this display shows this digit. We are interested in which digits are displayed to solve the puzzle. To help us we also know which
segments form which digit, we just don't know the wiring in the back. So we should identify which wire maps to which segment! We are introducing the packages
wire-X-connects-to-Yfor this which each provide & conflict1 with the virtual packages
wire-X-connects. The later ensures that for a given wire we can only pick one segment and the former ensures that not multiple wires map onto the same segment. As an example: wire
a's possible association with segment
bis described as:
Note that we do not know if this is true! We generate packages for all possible (and then some) combinations and hope dependency resolution will solve the problem for us. So don't worry, the hard part will be done by apt, we just have to provide all (im)possibilities! What we need now is to translate the 10 digits (and 4 outputs) from something like
Package: wire-a-connects-to-b Provides: segment-b, wire-a-connects Conflicts: segment-b, wire-a-connects
digit-0-is-eightand not, say
digit-0-is-one. A clever solution might realize that a
oneconsists only of two segments so a digit wiring up seven segments can not be a 1 (and must be 8 instead), but again we aren't here to be clever: We want apt to figure that out for us! So what we do is simply making every
digit-0-is-N(im)possible choice available as a package and apply constraints: A given
digit-Ncan only display one number and each
Nis unique as
digitso for both we deploy Provides & Conflicts again. We also need to reason about the segments in the digits: Each of the digit packages gets Depends on
Xis each possible wire (e.g.
Yeach segment forming the digit (e.g.
one). The different choices for
Xare or'ed together, so that either of them satisfies the
Y. We know something else too through: The segments which are not used by the digit can not be wired to any of the
Xs. We model this with Conflicts on
wire-X-connects-to-Y. As an example: If
acedgfbwould be displaying a one (remember, it can't) the following package would be installable:
Repeat such stanzas for all 10 possible digits for
Package: digit-0-is-one Version: 1 Depends: wire-a-connects-to-c wire-c-connects-to-c wire-e-connects-to-c wire-d-connects-to-c wire-g-connects-to-c wire-f-connects-to-c wire-b-connects-to-c, wire-a-connects-to-f wire-c-connects-to-f wire-e-connects-to-f wire-d-connects-to-f wire-g-connects-to-f wire-f-connects-to-f wire-b-connects-to-f Provides: digit-0, digit-is-one Conflicts: digit-0, digit-is-one, wire-a-connects-to-a, wire-c-connects-to-a, wire-e-connects-to-a, wire-d-connects-to-a, wire-g-connects-to-a, wire-f-connects-to-a, wire-b-connects-to-a, wire-a-connects-to-b, wire-c-connects-to-b, wire-e-connects-to-b, wire-d-connects-to-b, wire-g-connects-to-b, wire-f-connects-to-b, wire-b-connects-to-b, wire-a-connects-to-d, wire-c-connects-to-d, wire-e-connects-to-d, wire-d-connects-to-d, wire-g-connects-to-d, wire-f-connects-to-d, wire-b-connects-to-d, wire-a-connects-to-e, wire-c-connects-to-e, wire-e-connects-to-e, wire-d-connects-to-e, wire-g-connects-to-e, wire-f-connects-to-e, wire-b-connects-to-e, wire-a-connects-to-g, wire-c-connects-to-g, wire-e-connects-to-g, wire-d-connects-to-g, wire-g-connects-to-g, wire-f-connects-to-g, wire-b-connects-to-g
digit-0and then repeat this for all the other nine
digit-N. We produce pretty much the same stanzas for
-is-one), just that we omit the second Provides & Conflicts from above (
digit-is-one) as in the display digits can be repeated. The rest is the same (modulo using
digitas name of course). Lastly we create a package dubbed
solutionwhich depends on all 10
display-Nall of them virtual packages apt will have to choose an installable provider from and we are nearly done! The resulting
Packagesfile2 we can give to
aptwhile requesting to install the package
solutionand it will spit out not only the display values we are interested in but also which number each digit represents and which wire is connected to which segment. Nifty!
We are only interested in the numbers on the display through, so grepping the apt output (
$ ./skip-aoc 'acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab cdfeb fcadb cdfeb cdbaf' [ ] The following additional packages will be installed: digit-0-is-eight digit-1-is-five digit-2-is-two digit-3-is-three digit-4-is-seven digit-5-is-nine digit-6-is-six digit-7-is-four digit-8-is-zero digit-9-is-one display-1-is-five display-2-is-three display-3-is-five display-4-is-three wire-a-connects-to-c wire-b-connects-to-f wire-c-connects-to-g wire-d-connects-to-a wire-e-connects-to-b wire-f-connects-to-d wire-g-connects-to-e [ ] 0 upgraded, 22 newly installed, 0 to remove and 0 not upgraded.
-Vis our friend here) a bit should let us end up with what we need as calculating3 is (unsurprisingly) not a strong suit of our package relationship language so we need a few shell commands to help us with the rest.
I have written the skip-aoc script as a testcase for apt, so to run it you need to place it in
$ ./skip-aoc 'acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab cdfeb fcadb cdfeb cdbaf' -qq 5353
/path/to/source/of/apt/test/integrationand built apt first, but that is only due to my laziness. We could write a standalone script interfacing with the system installed apt directly and in any apt version since ~2011. To hand in the solution for the puzzle we just need to run this on each line of the input (~200 lines) and add all numbers together. In other words: Behold this beautiful shell one-liner:
parallel -I ' ' ./skip-aoc ' ' -qq < input.txt paste -s -d'+' - bc(You may want to run
-Pto properly grill your CPU as that process can take a while otherwise and it still does anyhow as I haven't optimized it at all the testing framework does a lot of pointless things wasting time here, but we aren't aiming for the leaderboard so ) That might or even likely will fail through as I have so far omitted a not unimportant detail: The default APT resolver is not able to solve this puzzle with the given problem description we need another solver! Thankfully that is as easy as installing
apt-cudf(and with it
aspcud) which the script is using via
--solver aspcudto make apt hand over the puzzle to a "proper" solver (or better: A solver who is supposed to be good at "answering set" questions). The buildds are using this for experimental and/or backports builds and also for installability checks via dose3 btw, so you might have encountered it before. Be careful however: Just because
aspcudcan solve this puzzle doesn't mean it is a good default resolver for your day to day apt. One of the reasons the default resolver has such a hard time solving this here is that or-groups have usually an order in which the first is preferred over every later option and so fort. This is of no concern here as all these alternatives will collapse to a single solution anyhow, but if there are multiple viable solutions (which is often the case) picking the "wrong" alternative can have bad consequences. A classic example would be
exim4 postfix nullmailer. They are all MTAs but behave very different. The non-default solvers also tend to lack certain features like keeping track of auto-installed packages or installing Recommends/Suggests. That said, Julian is working on another solver as I write this which might deal with more of these issues. And lastly: I am also relatively sure that with a bit of massaging the default resolver could be made to understand the problem, but I can't play all day with this maybe some other day. Disclaimer: Originally posted in the daily megathread on reddit, the version here is just slightly better understandable as I have hopefully renamed all the packages to have more conventional names and tried to explain what I am actually doing. No cows were harmed in this improved version, either.
If you would upload those packages somewhere, it would be good
style to add
Replacesas well, but it is of minor concern for apt so I am leaving them out here for readability.
- We have generated 49 wires, 100 digits, 40 display and 1 solution package for a grant total of 190 packages. We are also making use of a few purely virtual ones, but that doesn't add up to many packages in total. So few packages are practically childs play for apt given it usually deals with thousand times more. The instability for those packages tends to be a lot better through as only 22 of 190 packages we generated can (and will) be installed. Britney will hate you if your uploads to Debian unstable are even remotely as bad as this.
- What we could do is introduce 10.000 packages which denote every possible display value from 0000 to 9999. We would then need to duplicate our 10.190 packages for each line (namespace them) and then add a bit more than a million packages with the correct dependencies for summing up the individual packages for apt to be able to display the final result all by itself. That would take a while through as at that point we are looking at working with ~22 million packages with a gazillion amount of dependencies probably overworking every solver we would throw at it a bit of shell glue seems the better option for now.