David Kalnischkieshttps://david.kalnischkies.de/blog/tags/EDSPstaticsite2021-12-09T12:14:11Zapt-get a life: posts tagged EDSPAPT for Advent of Codehttps://david.kalnischkies.de/blog/2021/apt-for-advent-of-code2021-12-09T12:14:11Z2021-12-09T12:14:11Z
<figure>
<img alt='Screenshot of my Advent of Code 2021 status page as of today' width='480' height='185' src='https://david.kalnischkies.de/blog/2021/apt-for-advent-of-code-small.png' title='The things I did to earn some of these stars…'></img>
<figcaption class="credits"><a href="https://adventofcode.com/">Advent of Code 2021</a></figcaption>
</figure>
<p><a href="https://adventofcode.com/">Advent of Code</a>, 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.</p>
<p>I usually write <em>boring</em> 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 <a href="https://old.reddit.com/r/adventofcode/comments/rbj87a/2021_day_8_solutions/hns59a2/">Microsoft Excel</a>…
so, after solving a puzzle the <em>easy</em> way yesterday, this time
I thought: <strong>CHALLENGE ACCEPTED!</strong> as I somehow remembered an old 2008
article about <a href="https://web.archive.org/web/20150905115613/http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku/">solving Sudoku with aptitude</a>
(Daniel Burrows via archive.org as the blog is long gone)
and the good same old <em>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</em> (<a href="https://etbe.coker.com.au/2008/08/19/ownership-local-se-linux-policy/">Russell Coker</a>).</p>
<p><a href="https://adventofcode.com/2021/day/8">Day 8</a> has a rather lengthy
problem description and can reasonably be approached in a bunch of
different way. One <em>unreasonable</em> 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.)</p>
<p><strong>Be warned: I am spoiling Part 2 in the following, so solve it yourself
first if you are interested.</strong></p>
<p>I will try to be reasonable consistent in naming things in the following
and so have chosen: The input we get are lines like <code>acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf</code>.
The letters are <code>wires</code> mixed up and connected to the segments of the
displays: A group of these letters is hence a <code>digit</code> (the first 10)
which represent one of the digits 0 to 9 and (after the pipe) the four
<code>display</code>s 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 <code>segment</code>s
form which digit, we just don't know the wiring in the back.</p>
<p>So we should identify which wire maps to which segment!
We are introducing the packages <code>wire-X-connects-to-Y</code> for this which
each provide & conflict<sup id="fnref:4-1"><a class="footnote-ref" href="#fn:4-1">1</a></sup> with the virtual packages <code>segment-Y</code> and
<code>wire-X-connects</code>.
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.</p>
<p>As an example: wire <code>a</code>'s possible association with segment <code>b</code> is
described as:</p>
<div class="codehilite"><pre><span></span><code><span class="k">Package</span><span class="w">: </span><span class="s">wire-a-connects-to-b</span>
<span class="k">Provides</span><span class="w">: </span><span class="s">segment-b, wire-a-connects</span>
<span class="k">Conflicts</span><span class="w">: </span><span class="s">segment-b, wire-a-connects</span>
</code></pre></div>
<p>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!</p>
<p>What we need now is to translate the 10 digits (and 4 outputs) from
something like <code>acedgfb</code> into <code>digit-0-is-eight</code> and not, say
<code>digit-0-is-one</code>. A clever solution might realize that a <code>one</code> 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 <code>digit-0-is-N</code> (im)possible choice available as a package and
apply constraints: A given <code>digit-N</code> can only display one number and
each <code>N</code> is unique as <code>digit</code> – so for both we deploy Provides
& Conflicts again.</p>
<p>We also need to reason about the segments in the digits: Each of the
digit packages gets Depends on <code>wire-X-connects-to-Y</code> where <code>X</code> is each
possible wire (e.g. <code>acedgfb</code>) and <code>Y</code> each segment forming the digit
(e.g. <code>cf</code> for <code>one</code>). The different choices for <code>X</code> are or'ed together,
so that either of them satisfies the <code>Y</code>.</p>
<p>We know something else too through: The segments which are not used by
the digit can not be wired to any of the <code>X</code>s. We model this with
Conflicts on <code>wire-X-connects-to-Y</code>.</p>
<p>As an example: If <code>digit-0</code>s <code>acedgfb</code> would be displaying a one
(remember, it can't) the following package would be installable:</p>
<div class="codehilite"><pre><span></span><code><span class="k">Package</span><span class="w">: </span><span class="s">digit-0-is-one</span>
<span class="k">Version</span>: <span class="m">1</span>
<span class="k">Depends</span>: <span class="nf">wire-a-connects-to-c</span> <span class="o">|</span> <span class="nf">wire-c-connects-to-c</span> <span class="o">|</span> <span class="nf">wire-e-connects-to-c</span> <span class="o">|</span> <span class="nf">wire-d-connects-to-c</span> <span class="o">|</span> <span class="nf">wire-g-connects-to-c</span> <span class="o">|</span> <span class="nf">wire-f-connects-to-c</span> <span class="o">|</span> <span class="nf">wire-b-connects-to-c</span>,
<span class="nf">wire-a-connects-to-f</span> <span class="o">|</span> <span class="nf">wire-c-connects-to-f</span> <span class="o">|</span> <span class="nf">wire-e-connects-to-f</span> <span class="o">|</span> <span class="nf">wire-d-connects-to-f</span> <span class="o">|</span> <span class="nf">wire-g-connects-to-f</span> <span class="o">|</span> <span class="nf">wire-f-connects-to-f</span> <span class="o">|</span> <span class="nf">wire-b-connects-to-f</span>
<span class="k">Provides</span><span class="w">: </span><span class="s">digit-0, digit-is-one</span>
<span class="k">Conflicts</span><span class="w">: </span><span class="s">digit-0, digit-is-one,</span>
<span class="err"> 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,</span>
<span class="err"> 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,</span>
<span class="err"> 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,</span>
<span class="err"> 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,</span>
<span class="err"> 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</span>
</code></pre></div>
<p>Repeat such stanzas for all 10 possible digits for <code>digit-0</code> and then
repeat this for all the other nine <code>digit-N</code>. We produce pretty much the
same stanzas for <code>display-0</code>(<code>-is-one</code>), just that we omit the second
Provides & Conflicts from above (<code>digit-is-one</code>) as in the display
digits can be repeated. The rest is the same (modulo using <code>display</code>
instead of <code>digit</code> as name of course).</p>
<p>Lastly we create a package dubbed <code>solution</code> which depends on all 10
<code>digit-N</code> and 4 <code>display-N</code> – all of them virtual packages apt will have
to choose an installable provider from – and we are nearly done!</p>
<p>The resulting <code>Packages</code> file<sup id="fnref:4-2"><a class="footnote-ref" href="#fn:4-2">2</a></sup> we can give to <code>apt</code> while requesting to
install the package <code>solution</code> 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!</p>
<div class="codehilite"><pre><span></span><code>$ ./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.
</code></pre></div>
<p>We are only interested in the numbers on the display through, so grepping
the apt output (<code>-V</code> is our friend here) a bit should let us end up with
what we need as calculating<sup id="fnref:4-3"><a class="footnote-ref" href="#fn:4-3">3</a></sup> is (unsurprisingly) not a strong suit of
our package relationship language so we need a few shell commands to
help us with the rest.</p>
<div class="codehilite"><pre><span></span><code>$ ./skip-aoc <span class="s1">'acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf'</span> -qq
<span class="m">5353</span>
</code></pre></div>
<p>I have written the <a href="./skip-aoc">skip-aoc</a> script as a testcase for apt,
so to run it you need to place it in
<code>/path/to/source/of/apt/test/integration</code> 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 <a href="/blog/2011/External_dependency_solvers_in_APT">any apt
version since
~2011</a>.</p>
<p>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:
<code>parallel -I '{}' ./skip-aoc '{}' -qq < input.txt | paste -s -d'+' - | bc</code></p>
<p>(You may want to run <code>parallel</code> with <code>-P</code> 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…)</p>
<p>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!</p>
<p>Thankfully that is as easy as installing <code>apt-cudf</code> (and with it <code>aspcud</code>)
which the script is using via <code>--solver aspcud</code> 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.</p>
<p>Be careful however: Just because <code>aspcud</code> 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
<code>exim4 | postfix | nullmailer</code>. They are all <abbr title="Mail Transport Agent">MTA</abbr>s
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
<a href="https://blog.jak-linux.org/2021/11/21/apt-z3-solver-basics/">another solver</a>
as I write this which might deal with more of these issues.</p>
<p>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.</p>
<p><strong>Disclaimer</strong>: Originally posted in the <a href="https://old.reddit.com/r/adventofcode/comments/rbj87a/2021_day_8_solutions/hnqvl66/">daily megathread</a>
on reddit, the version here is just <em>slightly</em> 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.</p>
<div class="footnote">
<hr>
<ol>
<li id="fn:4-1">
<p>If you would upload those packages somewhere, it would be good
style to add <code>Replaces</code> as well, but it is of minor concern for apt
so I am leaving them out here for readability. <a class="footnote-backref" href="#fnref:4-1" title="Jump back to footnote 1 in the text">↩</a></p>
</li>
<li id="fn:4-2">
<p>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. <a class="footnote-backref" href="#fnref:4-2" title="Jump back to footnote 2 in the text">↩</a></p>
</li>
<li id="fn:4-3">
<p>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. <a class="footnote-backref" href="#fnref:4-3" title="Jump back to footnote 3 in the text">↩</a></p>
</li>
</ol>
</div>
<p><small><a rel="canonical" href="https://david.kalnischkies.de/blog/2021/apt-for-advent-of-code">This article</a> was written by David Kalnischkies on <a href="https://david.kalnischkies.de">apt-get a life</a> and republished here by pulling it from a syndication feed. You should check there for updates and more articles about apt and EDSP.</small></p>
External dependency solvers in APThttps://david.kalnischkies.de/blog/2011/External_dependency_solvers_in_APT2011-07-30T10:42:17Z2011-07-30T10:42:17Z
<p>Back in April I talked about <a href="One_week_in_Paris">me being in Paris</a>,
I returned in May but kept more or less silent about it.</p>
<p>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).</p>
<p>All you need is: <ul> <li>APT in a 0.8.16~ version (debian-experimental has
them, ubuntu-oneric too)</li> <li>apt-cudf from debian-experimental</li> <li>an
external solver like aspcud from debian-unstable/testing</li> </ul></p>
<p>And you are ready to have some fun, try e.g. <code>apt-get install awesome
--solver aspcud</code></p>
<p>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.</p>
<p>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…</p>
<p>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.</p>
<p>(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 ! <span class="emoji" data-unicode="1F609" title=";)">😉</span> )</p>
<p><small><a rel="canonical" href="https://david.kalnischkies.de/blog/2011/External_dependency_solvers_in_APT">This article</a> was written by David Kalnischkies on <a href="https://david.kalnischkies.de">apt-get a life</a> and republished here by pulling it from a syndication feed. You should check there for updates and more articles about EDSP.</small></p>
One week in Parishttps://david.kalnischkies.de/blog/2011/One_week_in_Paris2011-04-05T16:00:27Z2011-04-05T16:00:27Z
<p>(I can't help myself, the title sounds like a good remake of bad stuff - I mean, the
remake is bad, but <a href="https://en.wikipedia.org/wiki/Double_negative#Two_negatives_resolving_to_a_positive">double bad is good</a>, isn't it?)</p>
<p>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…</p>
<p>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 <a
href="http://www.irill.org/">IRILL</a> on <a
href="http://www.mancoosi.org/">mancoosi</a>. In a nutshell: Defining and
organizing dependency solving battles by defining a protocol all solvers have
to understand and what the response should be.</p>
<p>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
<acronym title="External Dependency Solver Protocol">EDSP</acronym> which
defines an intermediate scenario format which is near to <acronym title="Common Upgradeability Description Format">CUDF</acronym>,
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".</p>
<p>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.</p>
<p>Time will tell, so far at least from the water-level observation one-man-team
here. <span class="emoji" data-unicode="1F609" title=";)">😉</span></p>
<p><small><a rel="canonical" href="https://david.kalnischkies.de/blog/2011/One_week_in_Paris">This article</a> was written by David Kalnischkies on <a href="https://david.kalnischkies.de">apt-get a life</a> and republished here by pulling it from a syndication feed. You should check there for updates and more articles about EDSP.</small></p>