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 acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf. The letters are wires mixed 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-Y for this which each provide & conflict¹ with the virtual packages segment-Y and 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 b is described as:

Package: wire-a-connects-to-b
Provides: segment-b, wire-a-connects
Conflicts: segment-b, wire-a-connects

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 acedgfb into digit-0-is-eight and not, say digit-0-is-one. A clever solution might realize that a one consists 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-N can only display one number and each N is unique as digit – so 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 wire-X-connects-to-Y where X is each possible wire (e.g. acedgfb) and Y each segment forming the digit (e.g. cf for one). The different choices for X are 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 digit-0s acedgfb would be displaying a one (remember, it can't) the following package would be installable:

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

Repeat such stanzas for all 10 possible digits for digit-0 and then repeat this for all the other nine digit-N. We produce pretty much the same stanzas for display-0(-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 display instead of digit as name of course).

Lastly we create a package dubbed solution which depends on all 10 digit-N and 4 display-N – all of them virtual packages apt will have to choose an installable provider from – and we are nearly done!

The resulting Packages file² we can give to apt while requesting to install the package solution and 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!

$ ./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.

We are only interested in the numbers on the display through, so grepping the apt output (-V is our friend here) a bit should let us end up with what we need as calculating³ is (unsurprisingly) not a strong suit of our package relationship language so we need a few shell commands to help us with the rest.

$ ./skip-aoc 'acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf' -qq
5353

I have written the skip-aoc script as a testcase for apt, so to run it you need to place it in /path/to/source/of/apt/test/integration and 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 parallel with -P to 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 aspcud to 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 aspcud can 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.

Back in April I talked about me being in Paris, I returned in May but kept more or less silent about it.

Nothing has really changed since then, I just want to write down now how somebody can play with other solvers now before it hits possibly a bigger audience (in case someone actually reads changelogs or such silly stuff).

All you need is:

• APT in a 0.8.16~ version (debian-experimental has them, ubuntu-oneric too)
• apt-cudf from debian-experimental
• an external solver like aspcud from debian-unstable/testing

And you are ready to have some fun, try e.g. apt-get install awesome --solver aspcud

You will notice: It's relatively slow, compared to the internal solver. It might not behave like you would expect the internal solver to behave in regards to pinning or alike.

Best example is APT's own external solver 'apt' – yes, you can use the internal solver as an external solver in case you find another program implementing EDSP – which doesn't implement pinning and a few other bits so far. You are right than you think that this one is mostly only useful for debugging. There is another interesting one: 'dump' – imagine what it does…

So, why is this useful you might ask: In case you find a dependency problem you can now dump this problem easily and run different solvers on it. You can also work on developing the next-generation hyper-intelligent solver and be able to use it in day-to-day situations with the tools you usually use. And as a bug-hunter, you can if you have such a dump reproduce the problem more easily and get your hands dirty while fixing the bug. So this EDSP thing is kind of technical preview. It's not planed to drop the internal solver from APT now or in the near future, don't worry. It's mostly here to enable researchers and developers to play with new deployments in real world situations so that at the end they create something which can be used for implementations which can really be used by "normal" end-users.

(and its here to enable me to throw the sentence: "Heh, if you thing the apt solver is so dumb and you could do it so much better: Why don't you do it for the benefit of all of us?" at everyone complaining without hard facts just because they think nobody listens who will hunt them down and force them to solve all these "utterly trivial problems" on their own. Yes, I am looking at YOU ! 😉 )

(I can't help myself, the title sounds like a good remake of bad stuff - I mean, the remake is bad, but double bad is good, isn't it?)

I am back. After my sheeva and then my kindle returned back to me, I returned home, too. Last week was one of the craziest in my life: You are more or less alone in a big city, hundreds of people passing by and you understand nobody. The only language I can really speak is German, but the masochist in me accepts invitations to America where my rusty English allows me to survive, but how he could accept an invitation to Paris in the knowledge that I don't speak a single word of French?!? I learned two words: 'Bonjour' (hello) and 'Sortie' (exit) in this week. As you can see, I am not a fast learner…

Anyway, it's properly more interesting what I did in Paris: Stefano happens to be working for one of the universities of Paris and in this function for IRILL on mancoosi. In a nutshell: Defining and organizing dependency solving battles by defining a protocol all solvers have to understand and what the response should be.

The week was therefore dedicated to working out a way for APT to talk to external solvers, so that we can use the battle survivors as external solvers for (maybe) better solutions. I will write a bit more detailed how this works (or not) after finishing it in a second stay in May, but so far we have an EDSP which defines an intermediate scenario format which is near to CUDF, but doesn't rewrite versionnumbers and alike as this is internal business a solver doesn't need to do to work with APT. So in practice the cudf solvers will most likely use a common preprocessor on this scenario and be happy. A common postprocessor will then reformat the cudf response to a diff style answer which will be passed to APT which reacts on it and does his "magic".

EDSP is currently an early draft and the implementation in APT more or less half-way finished while EDSP<->CUDF translator is promising, too. All in all we will most likely see something soon in May modulo that it will need an ABI-break in APT which needs a lot of time to be allowed in unstable most of the time.

Time will tell, so far at least from the water-level observation one-man-team here. 😉