tag:blogger.com,1999:blog-101281872024-02-07T18:10:53.586+01:00From the Fiber Trenches to the CloudsUnknownnoreply@blogger.comBlogger41125tag:blogger.com,1999:blog-10128187.post-50785517397384538702023-04-16T16:20:00.003+02:002023-04-16T16:20:34.164+02:00Google Code Jam 2023 in Lisp<p>Since 2009, I have occasionally participated in Google's <i>Code Jam</i> competitions, usually programming in Lisp. Google decided to <a href="https://developers.googleblog.com/2023/02/celebrate-googles-coding-competitions.html">discontinue it along with their other coding competitions</a>. So this year there was a <a href="https://codingcompetitions.withgoogle.com/codejam/archive/2023">"Farewell Round"</a> held on a single day (yesterday), actually four rounds (A, B, C, D) held during the same long (four-hour) timeslot. Because I didn't feel very competitive or confident, I mainly tackled the problems from the "A" round, assuming that those were the easiest ones.</p><p>Thanks to the generous timeslot, I managed to solve all five problems in Round A. You can find them on the <a href="https://gitlab.leinen.ch/insertsomethingwitty/gcj2023/">gcj2023 project</a> on my personal GitLab server.</p><p><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000c95b94/0000000000cad7cf">Colliding Encoding</a>: The task is to check whether there are collisions (duplicates) in a list of word after encoding with a lossy cipher function (mapping 26 alphabetic letters to 10 decimal digits). I map the strings, sort them, and walk through the result comparing neighboring entries—iff there's a match, then there are collisions. Code: <a href="https://gitlab.leinen.ch/insertsomethingwitty/gcj2023/-/blob/main/a/1.lisp">a/1.lisp</a></p><p><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000c95b94/0000000000cad086">Illumination Optimization</a>: Given a set of lampposts at positions <i>X<sub>i</sub></i> along a road, how many lightbulbs of illumination radius <i>R</i> are needed to light the entire stretch of road from 0 to <i>M?</i> You go through the lamppost positions in order and skip those that are already illuminated by the previous lamp. My solution (<a href="https://gitlab.leinen.ch/insertsomethingwitty/gcj2023/-/blob/main/a/2.lisp">a/2.lisp</a>) tries both directions, in case one is "more optimal" than the other :-)</p><p><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000c95b94/0000000000cada38">Rainbow Sort:</a> On first read, I found it a bit confusing, because it talks about colors, card positions, and ordering numbers, all represented as integers; so I put it off until after the others. In the end it turned out to be quite easy. My solution (<a href="https://gitlab.leinen.ch/insertsomethingwitty/gcj2023/-/blob/main/a/3.lisp">a/3.lisp</a>) is a simple recursive function using a hash table to store colors that have already been seen.</p><p><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000c95b94/0000000000cad9c2">ASCII Art:</a> I quickly figured out that there must be a solution that involves just computation and no searching or construction. But it took me quite a bit of time (easily more than an hour) and trial/error until I removed all off-by-one errors. The solution (<a href="https://gitlab.leinen.ch/insertsomethingwitty/gcj2023/-/blob/main/a/4.lisp">a/4.lisp</a>) ended up simple enough, and solved all sets on the first attempt.</p><p><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000c95b94/0000000000cad9c1">Untie:</a> Here again, I quickly figured out that I can simply ignore all sub-sequences that have no repetitions. For every repeated sequences of length <i>N,</i> you can always fix the tie by flipping <i>⌊N/2⌋</i> symbols. I convinced myself that this is always possible without creating additional collision, thanks to the fact that you have two symbols to choose from. The trickiest part is that we're dealing with a circle rather than a sequence with start and end. My approach was to start at a point where the symbol changes—if there is no such point, then this is a special situation of a circular sequence of the total length of the sequence, and in this case actually you need to flip <i>⌈N/2⌉</i> symbols. Other than that, my recursive solution (<a href="https://gitlab.leinen.ch/insertsomethingwitty/gcj2023/-/blob/main/a/5.lisp">a/5.lisp</a>) looks relatively simple, and solved all cases on the first attempt.</p><p>By solving all problem sets in time, I ended up in rank 734 for that round, which made me quite happy! With some (but too little) time remaining, I tried my hand at two problems from more difficult rounds, but didn't manage to solve either of them in time.</p><p><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000c95433/0000000000cacb87">Game Sort</a> (Round C): This didn't look <i>that</i> hard, but my code consistently solved only the tiny sample set, and failed at even the small set on all my attempts. Maybe I take my broken code (<a href="https://gitlab.leinen.ch/insertsomethingwitty/gcj2023/-/blob/main/c/1.lisp">c/1.lisp</a>) up and try to find and fix what's wrong with it—or probably rather with my initial understanding of the problem and its possible solution.</p><p><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000c9607c/0000000000cad2ce">Spacious Sets</a> (Round B): My first iteration of code solved the small set, but ran into a timeout on the large set. I had to revise it to avoid quadratic complexity. I first thought of "memoization" to optimize away repeated iterations; in the process of implementing that, I discovered a nice linear initial pass (which has to be done in both directions—the problem has some structural similarities with <i>Illumination Optimization</i> above) that allowed the computation for a given pivot element to be done in constant time (adding two pre-computed numbers and 1). To my surprise, even with this probably very close to optimal solution, my program ran out of time! It turned out that I had another <i>O(N²)</i> issue in an innocuous part of the code that simply constructs a mapping from indexes in the original unordered sequence to the position in the sorted sequence that I use for the computation. I had to replace the trivial code using <span style="font-family: courier;">POSITION</span> with my own <span style="font-family: courier;">FAST-POSITION</span> trivially implementing binary search on the <b>sorted</b> output vector. The code (<a href="https://gitlab.leinen.ch/insertsomethingwitty/gcj2023/-/blob/main/b/3.lisp">b/3.lisp</a>) doesn't look great, but it works! I only really started after the end of the competition, though; otherwise I might have gotten four points for the small set...</p><p>So that was Google Code Jam's Farewell Round! Thanks a lot to Google for organizing those events over twenty years, and especially to the many Googlers for coming up with great problems, ironing them out, and providing tons of challenging data sets! I had a lot of fun—along with quite a bit of frustration; but that goes along with the challenge, I guess.</p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-32042512967398294852021-06-10T23:33:00.000+02:002021-06-10T23:33:00.819+02:00AI/ML Hype: If even Google doesn't get it right, then...?<p> I'm a happy and frequent user of Google Photos, which I use to back up, share, and edit the many photos that I take on my smartphone.</p><p>This morning, the mobile app greeted me with a new feature: It suggested that six of my photos were incorrectly oriented, and offered me to fix that by rotating them.</p><p>I checked, and out of those six photos, five were totally fine as they were. (I'm a bit pedantic and usually fix any wrong orientation quickly by hand, which Google Photos makes quite easy.)</p><p>The sixth was indeed misoriented, but the rotation suggested by the tool was also wrong.</p><p>First I laughed. If Google—of all people!—sends me twelve predictions via a highly popular app, and gets eleven of those wrong, how can anybody really expect that Artificial Intelligence/Machine Learning will solve real problems and eventually pay back all the investments being made in it? And note that the problem class here is basically image classification, which is one of the few narrow domains where ML has been particularly effective.</p><p>And then I dutifully corrected Google's mispredictions by rotating the proposed images until they were correct (correct <i>again, </i>in five of the six cases). So maybe if a few million other nice/gullible people help poor Google out, then maybe one day, it will actually become helpful even to pedants like me.</p><p>This suddenly recalled a question Prof. Mireille Hildebrandt asked at a large EU event last week ("Leading the Digital Decade", <a href="https://www.youtube.com/watch?v=IVQNaRD1BfI&t=11684s" target="_blank">video</a>):</p><blockquote style="border: none; margin: 0 0 0 40px; padding: 0px;"><p style="text-align: left;"><i>What is a digitally skilled population? Is it a population capable of using AI and other digital systems? That's the usual way to talk about citizens: users. Or is it, perhaps, a population that is open to be used by these systems as data engines?</i></p></blockquote>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-7520396642590380032020-05-03T11:43:00.003+02:002020-05-03T11:46:25.809+02:00Google Code Jam 2020 in Lisp—Round 1CWell, that was slightly embarrassing and frustrating...<br />
<br />
After a relatively promising <a href="https://blog.simon.leinen.ch/2020/04/google-code-jam-2020-in-lispround-1b.html">attempt at round 1B</a>, I entered <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4">round 1C</a> yesterday as the last chance to advance to round 2. Again, three nice problems, with the third one looking too hard for me at first sight, at least for the general solution. My "plan" after reading the problem descriptions was roughly: Solve problems 1 and 2 and, time permitting, submit a solution for the easy first input set of problem 3. That would have been a good plan, except I took a bit too long to code problem 1, and I got completely stuck trying to debug my Lisp solution for problem 2.<br />
<h3>
Problem 1: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/0000000000317409">Overexcited Fan</a></h3>
<div>
The problem turned out to be even easier than I first thought. I should have spent more time designing the algorithm before starting to code it. I had an <a href="https://github.com/sleinen/gcj2020/blob/bc8e5b820480e060058d47b9311a8bb2a7123241/1c/1.lisp">OK solution</a>, but it was more complex than necessary and took me 53 minutes. That's much longer than it should have, given the overall time limit of 2 hours 30 for the three tasks. After the round, I simplified this to <a href="https://github.com/sleinen/gcj2020/blob/master/1c/1.lisp">a more elegant solution</a>.</div>
<h3>
Problem 2: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003179a1">Overrandomized</a></h3>
<div>
Here I had the correct inspiration to work with letter frequencies, in particular first-digit letter frequencies. Unfortunately <a href="https://github.com/sleinen/gcj2020/blob/master/1c/2.lisp">my Lisp solution</a> would always result in "RE" (runtime error) when submitted, even though it ran fine both against the sample data set and against some additional data sets that I have <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003172d1">generated</a>. At this point I ran out of time.</div>
<div>
After the round, I tried for some time to get my Lisp program working, but without any possibility to get diagnostic output, I didn't find where the problem lied. I even started from scratch using a different implementation technique, but the result was the same: My program would run fine against the sample and my self-generated tests, but throw "RE" when faced with the competition/training data. Very frustrating. <b>If anyone finds the error(s), please let me know!</b></div>
<div>
At one point I reimplemented my <a href="https://github.com/sleinen/gcj2020/blob/master/1c/2.cpp">solution in C++</a>, and it successfully solved all data sets as soon as I got it to compile. I then <a href="https://github.com/sleinen/gcj2020/blob/master/1c/2.c">"backported" it to C</a>, which simplified it further (in the C++ version I used both "traditional" arrays and "library" vectors—for sorting—which makes that version quite ugly.</div>
<h3>
Problem 3: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003172d1">Oversized Pancake Choppers</a></h3>
<div>
After reading the problem description, I assumed (probably correctly) that a full solution would beyond my capabilities for solving, at least under this time pressure. But the easy set seemed quite tractable: If there are only 2 or 3 diners, then the set of solution possibilities is quite bounded. Indeed it took me <i>only</i> (competitive coders can laugh now) about 15 minutes to write a <a href="https://github.com/sleinen/gcj2020/blob/b86e212a5403b90d20ce19d624ecfcc920db748a/1c/3.lisp">stupid solution</a> that worked for this limited case. But that's academic because I had run out of time in problem 2, so this happened after the round was over.</div>
<h3>
Conclusion</h3>
<div>
With only the first and easiest problem solved in time, I ranked in the 8000s, much below my rank in 1B—and hopelessly below the cut-off at 1500.</div>
<div>
In problem 1 and (my constrained/stupid solution for) problem 3 I had no problems with Common Lisp as a coding language. But I failed to get my problem 2 Lisp solution working, while later attempts in C++ and C worked right away (and showed that I had analyzed the problem correctly).</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-16292321120837694652020-04-19T23:44:00.002+02:002020-05-03T12:32:21.466+02:00Google Code Jam 2020 in Lisp—Round 1BAlthough I had quite a bit of trouble surviving this year's <a href="https://blog.simon.leinen.ch/2020/04/google-code-jam-2020-in.html">qualification round</a>, I was allowed to participate in online round 1, which, as usual, is held as three different sub-rounds to accommodate participants from various time zones. The first (1A) was in the middle of the night in my time zone, so I skipped it and didn't even get around to reading the problems. But today I attempted round 1B. The problems were again very cute and interesting, and while I struggled with the limited time, I ended up being quite satisfied, even though I missed qualification this time.<br />
<h3>
Problem 1: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b62">Expogo</a></h3>
<div>
I wrote a relatively simple <a href="https://github.com/sleinen/gcj2020/blob/master/1b/1.lisp">implementation</a> using search with memoization (caching) and a bit of pruning of implausible search regions, and that was sufficient for all three data sets. According to the after-round summary, there's also a constructive solution. I had suspected so, but couldn't find it.</div>
<h3>
Problem 2: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b63">Blindfolded Bullseye</a></h3>
<div>
This is a nice search problem that involves some geometry. I think I started with a reasonable search strategy, but then ran out of time when it came to doing the geometry... So I gave up trying to find a "good" solution, and coded the trivial brute-force <a href="https://github.com/sleinen/gcj2020/blob/master/1b/2.lisp">solution</a> for solving the easiest data set. That was worth only 3 points, but those 3 points improved my final ranking by more than 1'000.</div>
<h3>
Problem 3: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b64">Join the Ranks</a></h3>
<div>
This didn't look too impossible, but given the high amounts of points awarded for this, I suspected that this would be beyond my skills and decided to focus on the other two problems.</div>
<h3>
Conclusion</h3>
<div>
With a full solution for problem 1, a half(?)-done good solution for problem 2, and the few extra points for the trivial data set of problem 2, I finally ranked #1996 [edited for final result]. As only the first 1500 contestants qualify for round 2, this was not sufficient. But I'm quite happy with how it went, and am looking forward to round 1C, about two weeks from now. And unlike during the qualification round, I didn't run into any issues with coding in Lisp—even though I haven't been using it professionally for several years now.</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-34772561764404337422020-04-07T15:05:00.000+02:002020-04-20T00:20:02.875+02:00Google Code Jam 2020 in Lisp—Qualification RoundThis year I registered for <a href="https://codingcompetitions.withgoogle.com/codejam">Google Code Jam</a> again. The new platform supports Common Lisp (SBCL) again, so I started writing my solutions for the Qualification Round in SBCL. Although I managed to qualify for Online Round 1, it didn't work as well as I'd hoped.<br />
The Qualification Round this year had five problems, which took me a while to notice—I had to scroll horizontally to see the fifth problem. I attempted all five, but only managed to write working solutions for three of them.<br />
<h3>
Problem 1: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020993c">Vestigium</a></h3>
<div>
That was an easy one, but for some reason I didn't manage to code it correctly in Common Lisp. Even though my <a href="https://github.com/sleinen/gcj2020/blob/master/qr/qr1.lisp">code</a> looked totally straightforward, it only produced an <i>RE</i> (Runtime Error) when run against the data set. Finally I rewrote the <a href="https://github.com/sleinen/gcj2020/blob/master/qr/qr1.cc">solution in C++</a>, and that worked on first try.</div>
<h3>
Problem 2: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9f">Nesting Depth</a></h3>
<div>
The task was to generate appropriate numbers of correctly nested parentheses. Obviously this type of problem is familiar to Lispers, and this time my straightforward code actually worked. My sloppiness resulted in an invalid attempt, as I initially left out the <span style="font-family: "courier new" , "courier" , monospace;">(solve)</span> call at the end of the <a href="https://github.com/sleinen/gcj2020/blob/master/qr/qr2-nest.lisp">script</a>.</div>
<h3>
Problem 3: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9">Parenting Partnering Returns</a></h3>
<div>
It occurred to me relatively early that the problem maps to the problem of partitioning (two-coloring) the interval graph. However, all my attempts of <a href="https://github.com/sleinen/gcj2020/blob/master/qr/qr3-parenting.lisp">coding</a> this simple graph traversal algorithm in Common Lisp ended in <i>REs</i> (Runtime Exceptions) again. Very frustrating!</div>
<h3>
Problem 4: <span id="goog_1928287122"></span><a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9e">ESAb ATAd</a><span id="goog_1928287123"></span></h3>
<div>
This was my favorite problem, and I came up with a <a href="https://github.com/sleinen/gcj2020/blob/master/qr/qr4-esab-atad.lisp">simple and near-optimal solution</a> pretty quickly. It would have worked the first time, had I not (again) forgotten to add the correct <span style="font-family: "courier new" , "courier" , monospace;">(solve)</span> call after the development phase.</div>
<h3>
Problem 5: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0">Indicium</a></h3>
<div>
That one was definitely too hard for me! After the deadline, I read the analysis and took it up again. I managed to code a super-efficient <a href="https://github.com/sleinen/gcj2020/blob/master/qr/qr5-indicium.lisp">method</a> to generate latin squares with arbitrary possible traces at will, based on "circulating" matrices. The only cases that I cannot solve in this way are <i>odd</i>-sized with traces of is <i>n+2 </i>or <i>n<sup>2</sup>-2</i>.<br />
<h3>
Conclusion</h3>
</div>
<div>
Finally I advanced with 49 points (from 100, with 30 required), and ranked #6318 of about 44000 participants. My Lisp development and graph algorithm skills have become a bit rusty, and I'm not very optimistic about being able to survive Online Round 1.</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-47275546245709910262019-07-22T19:15:00.002+02:002019-07-22T23:16:07.016+02:00Compiling Emacs on Mac OS against X11 libraries<h3>
Motivation</h3>
My place of work has been using Apple as the main, and now basically the only, supported platform for office use. As a long-time (GNU) Emacs user and occasional contributor, I usually compile GNU Emacs from the development (master) sources, which are now thankfully available over Git.<br />
I already feel bad for using a proprietary OS rather than something based on GNU/Linux or another free or at least open source system. For this and other reasons, I try to at least use system <i>libraries</i> from the free/open source community rather than Apple's, for example for the GUI. So rather than Apple's Carbon UI, I build Emacs against X11 libraries. Previously I could do this with the Gtk toolkit, but the maintainers of the Mac OS port of Gtk I was using stopped supporting its X11 drivers. So I reverted to the older "Lucid" toolkit with X11. (Yes, maybe I'm weird to cling to the X Window System in spite of the obstacles... that's probably because X was an important part of my socialization to Free Software and distributed systems.)<br />
<h3>
Howto</h3>
<div>
The prerequisites are</div>
<div>
<ul>
<li>a bunch of packages from <a href="https://brew.sh/">Homebrew</a> (not all of which may be relevant):</li>
<ul>
<li>autoconf autogen automake cairo d-bus dbus fontconfig freetype gcc gdk-pixbuf gettext git glib gmp gnutls gobject-introspection graphite2 harfbuzz imagemagick intltool ispell jansson jpeg json-glib libffi libpng librsvg libtasn1 libtiff libtool libunistring libxml2 little-cms2 netpbm nettle openjpeg openshift-cli osinfo-db osinfo-db-tools pcre pcre2 pkg-config readline shared-mime-info texinfo zlib</li>
</ul>
<li>an X11 (<a href="https://www.xquartz.org/">XQuartz</a>) installation with development headers</li>
<li>The Xcode development environment with its CLI tools installed.</li>
</ul>
</div>
<div>
I clone Emacs into /var/tmp/emacs/emacs according to the instructions on the <a href="https://www.emacswiki.org/emacs/EmacsFromGit">Emacs from Git</a> page of the Emacs Wiki. Then I mkdir /var/tmp/emacs/gbuild, cd there, and run</div>
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">../emacs/configure --verbose \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> --with-x --with-x-toolkit=lucid --with-ns=no \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> --without-makeinfo \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> LIBXML2_CFLAGS=-I/usr/local/opt/libxml2/include/libxml2 \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> LIBXML2_LIBS='-L/usr/local/opt/libxml2/lib -lxml2' \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> --with-jpeg=no --with-gif=no --with-tiff=no \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> --x-libraries=/usr/local/opt/freetype/lib:/usr/X11/lib \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> --x-includes=/usr/local/opt/freetype/include:/usr/X11/include \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> --with-xpm=no \</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> PKG_CONFIG_PATH=/usr/local/lib/pkgconfig:/usr/X11/lib/pkgconfig</span><br />
<span style="font-family: inherit;">This gives me the following configuration:</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;">Configured for 'x86_64-apple-darwin18.6.0'.</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Where should the build process find the source code? ../emacs</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> What compiler should emacs be built with? gcc -g3 -O2</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Should Emacs use the GNU version of malloc? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> (The GNU allocators don't work with this system configuration.)</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Should Emacs use a relocating allocator for buffers? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Should Emacs use mmap(2) for buffer allocation? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> What window system should Emacs use? x11</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> What toolkit should Emacs use? LUCID</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Where do we find X Windows header files? /usr/local/opt/freetype/include:/usr/X11/include</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Where do we find X Windows libraries? /usr/local/opt/freetype/lib:/usr/X11/lib</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lXaw3d? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lXpm? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -ljpeg? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -ltiff? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use a gif library? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use a png library? yes -L/usr/local/Cellar/libpng/1.6.37/lib -lpng16 -lz</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lrsvg-2? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use cairo? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -llcms2? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use imagemagick? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs support sound? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lgpm? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -ldbus? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lgconf? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use GSettings? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use a file notification library? yes (kqueue)</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use access control lists? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lselinux? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lgnutls? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lxml2? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lfreetype? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use HarfBuzz? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lm17n-flt? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lotf? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lxft? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lsystemd? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -ljansson? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use -lgmp? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs directly use zlib? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs have dynamic modules support? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs use toolkit scroll bars? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs support Xwidgets (requires gtk3)? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs have threading support in lisp? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs support the portable dumper? yes</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Does Emacs support legacy unexec dumping? no</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"> Which dumping strategy does Emacs use? pdumper</span><br />
<span style="font-family: inherit;">Then I can build Emacs using</span><br />
<span style="font-family: "courier new" , "courier" , monospace;">make bootstrap</span><br />
<span style="font-family: inherit;">This produces an intermediate "temacs" binary referencing many shared objects:</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;">: 1leinen@macsl[leinen]; objdump -macho -dylibs-used /var/tmp/emacs/gbuild/src/temacs</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;">/var/tmp/emacs/gbuild/src/temacs:</span><br />
<span style="font-family: "courier new" , "courier" , monospace; font-size: xx-small;"><span style="white-space: pre;">/opt/X11/lib/libpng16.16.dylib (compatibility version 43.0.0, current version 43.0.0)
/usr/lib/libz.1.dylib (compatibility version 1.0.0, current version 1.2.11)
/opt/X11/lib/libXaw3d.8.dylib (compatibility version 9.0.0, current version 9.0.0)
/opt/X11/lib/libXmu.6.dylib (compatibility version 9.0.0, current version 9.0.0)
/opt/X11/lib/libXt.6.dylib (compatibility version 7.0.0, current version 7.0.0)
/opt/X11/lib/libSM.6.dylib (compatibility version 7.0.0, current version 7.1.0)
/opt/X11/lib/libICE.6.dylib (compatibility version 10.0.0, current version 10.0.0)
/opt/X11/lib/libXext.6.dylib (compatibility version 11.0.0, current version 11.0.0)
/opt/X11/lib/libX11.6.dylib (compatibility version 10.0.0, current version 10.0.0)
/opt/X11/lib/libX11-xcb.1.dylib (compatibility version 2.0.0, current version 2.0.0)
/opt/X11/lib/libxcb.1.dylib (compatibility version 3.0.0, current version 3.0.0)
/opt/X11/lib/libXft.2.dylib (compatibility version 6.0.0, current version 6.2.0)
/opt/X11/lib/libXrender.1.dylib (compatibility version 5.0.0, current version 5.0.0)
/usr/local/opt/dbus/lib/libdbus-1.3.dylib (compatibility version 23.0.0, current version 23.11.0)
/opt/X11/lib/libXrandr.2.dylib (compatibility version 5.0.0, current version 5.0.0)
/opt/X11/lib/libXinerama.1.dylib (compatibility version 2.0.0, current version 2.0.0)
/opt/X11/lib/libXfixes.3.dylib (compatibility version 5.0.0, current version 5.0.0)
/usr/local/opt/libxml2/lib/libxml2.2.dylib (compatibility version 12.0.0, current version 12.9.0)
/usr/lib/libncurses.5.4.dylib (compatibility version 5.4.0, current version 5.4.0)
/usr/local/opt/freetype/lib/libfreetype.6.dylib (compatibility version 24.0.0, current version 24.1.0)
/opt/X11/lib/libfontconfig.1.dylib (compatibility version 11.0.0, current version 11.2.0)
/usr/local/opt/harfbuzz/lib/libharfbuzz.0.dylib (compatibility version 20504.0.0, current version 20504.0.0)
/usr/local/opt/gnutls/lib/libgnutls.30.dylib (compatibility version 55.0.0, current version 55.0.0)
/usr/local/opt/little-cms2/lib/liblcms2.2.dylib (compatibility version 3.0.0, current version 3.8.0)
/usr/local/opt/jansson/lib/libjansson.4.dylib (compatibility version 16.0.0, current version 16.1.0)
/usr/local/opt/gmp/lib/libgmp.10.dylib (compatibility version 14.0.0, current version 14.2.0)
/usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1252.250.1)</span></span><br />
<span style="font-family: inherit;">...and an src/emacs that hopefully doesn't crash. Oops... why am I saying that?</span><br />
<span style="font-family: inherit;">Well, yesterday I used a simpler method that didn't specify </span><span style="font-family: "courier new" , "courier" , monospace;">/usr/local/opt/freetype </span><span style="font-family: inherit;">explicitly anywhere, but relied on autoconf/pkgconfig to find it. Unfortunately this created a "DLL hell" situation where an older version of the freetype dynamic library from </span><span style="font-family: "courier new" , "courier" , monospace;">/opt/X11/lib</span><span style="font-family: inherit;"> was used instead of the newer on in </span><span style="font-family: "courier new" , "courier" , monospace;">/usr/local/opt/freetype/lib</span><span style="font-family: inherit;">, leading to crashes when Emacs tried to use certain fonts. Thanks to </span>YAMAMOTO Mitsuharu for helping me find the error in my old build process!Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-55918943508673527382019-04-07T15:52:00.001+02:002019-04-07T16:11:50.922+02:00Google Code Jam 2019 in Lisp (again) - Qualification RoundLike most years, I registered for Google Code Jam again, because it's fun. The qualification round is usually easy for me to survive, but presents an opportunity to de-rust the brain, get used to coding and interacting with the competition platform.<br />
Google introduced a new platform last year with a big change: Previously you got input and submitted output for checking, now you submit code, and Google runs it against input to check whether it generates the correct results. I suspect that a major driver for this change was the desire to curb cheating. The new platform also allows "interactive" problems, where your code interacts (via stdout/stdin) with a "judge" process, which is cool.<br />
One sad effect of last year's move to the new platform was that I could no longer use Lisp—only a couple programming languages were supported. Thus I mostly used C last year.<br />
This year I thought it was the same, and coded the first two problems, <i><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231">Foregone Solution</a></i> and <i><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881da">You Can Go Your Own Way</a>,</i> in C. As I started the third, I somehow noticed that more programming languages are supported this year, including Lisp (SBCL) and Clojure. So I changed to Common Lisp for problems three and four, <i><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881da">Cryptopangrams</a></i> and <i><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881da">Dat Bae</a>.</i><br />
After fighting a little with the way the platform runs Lisp programs (I hadn't even known about SBCL's <span style="font-family: "courier new" , "courier" , monospace;">--script</span> option), I managed to submit working versions for all problems.<br />
When the ratings came out, it turned out that I had gotten the two difficult problems right including the (hidden) large datasets, but for the two easy problems, my results for the large inputs were bad: <i>Wrong Answer</i> for <i><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231">Foregone Solution</a> </i>and <i>Runtime Error </i>for <i><a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881da">You Can Go Your Own Way</a>.</i><br />
For the first, I had used strncpy() with a limit of MAXDIGITS, and forgot that if there are actually MAXDIGITS characters to copy, then strncpy() won't copy the terminating NUL, so I had to write that <a href="https://github.com/sleinen/code-jam-2019/commit/f02eb4ec212dcd3609879e9a9b34e03aea1d6896">NUL byte to the end of the string</a>, which I had failed to do.<br />
For the second, I didn't read the problem description well, and thought that the problem size was limited to a 1000x1000 maze, where in fact it was 50000x50000 for the large set. Because I statically assigned vectors based on the maze edge length, this caused overruns. Easy to fix by <a href="https://github.com/sleinen/code-jam-2019/commit/31a35378ee2072b6bb3e1c047a57f6578071a84f">changing a #define from 1000 to 50000</a>.<br />
Both bugs would have been unlikely in Lisp, where strings don't have to be NUL-terminated and dynamic allocation of data structures is more natural than fixed allocation.<br />
Anyway, I lost 1+10 points to these stupid bugs, which gave me an overall score of 89. Of the more than 35500 participants, only one other person and I had this particular score. My rank was 1147, which is somewhat encouraging. But I was lucky to find good and easy-to-program approaches for each of the problems, and that will become (much) harder in the coming rounds.<br />
For <i><a href="https://github.com/sleinen/code-jam-2019/blob/master/qr/qr1-foregone.c">Foregone Solution,</a></i> I noticed quickly that <i>xx4x44x</i> can be trivially split into <i>xx3x33x</i> and <i>0010110.</i> For <i><a href="https://github.com/sleinen/code-jam-2019/blob/master/qr/qr2-maze.c">You Can Go Your Own Way,</a></i> it took me a bit longer to come up with the "complement" solution, i.e. when Lydia has walked <i>SSESEESE</i>, then I can simply walk <i>EESESSES</i> and be sure that we both arrive at the same destination (because the maze is square) and never make the same move. With <i><a href="https://github.com/sleinen/code-jam-2019/blob/master/qr/qr3-crypt.lisp">Cryptopangrams,</a></i> I quickly had the correct intuition that I should compute the GCD of adjacent cryptosymbols to extract the common prime, and hacked together a version that would solve the two simple sample cases. But as I repeatedly failed the smaller input sets, I noticed that there are complications when symbols are repeated. This was when I resorted to pencil and paper—it would probably have been a good idea to start this earlier!—, and it took me a while to turn this into code. But when I thought I had it right, the system still wouldn't accept my solutions! That's when I found out that I have to actually <i>call</i> the <span style="font-family: "courier new" , "courier" , monospace;">(solve)</span> function at the end of my program—doh!<br />
For <i><a href="https://github.com/sleinen/code-jam-2019/blob/master/qr/qr4-db.lisp">Dat Bae,</a></i> I implemented the <a href="https://github.com/sleinen/code-jam-2019/blob/687deb17b5bdb6572274d963c6f0c14bc9540553/qr/qr4-db.lisp#L12-L19">interaction with the Python-written sample judge</a> using a subprocess, which allowed me to run local tests. The easier set (F=10 guesses for broken bits in up to 1024 total bits) was solved by numbering all 1024 bits. It took me a break to find that I could easily bring the number of guesses down to F=5 due to the constraint that not more than 15 bits are broken: This allowed me to use a smaller pattern (e.g. 0...31) and repeat it, without introducing any ambiguities.Unknownnoreply@blogger.com0Zürich47.3770582 8.559990500000026321.8550237 -32.748603499999973 72.8990927 49.868584500000026tag:blogger.com,1999:blog-10128187.post-70422192503211349262017-11-11T08:36:00.005+01:002017-11-11T08:39:20.393+01:00You say "the internet", I say "the Internet"...My friend Nick Feamster recently <a href="https://twitter.com/feamster/status/928706778103209984">twote</a> something that resonated with me:<br />
<blockquote class="tr_bq">
I still bristle whenever I read Internet with a lowercase "i". The Internet is one specific instance of an "internetwork". People who write editorial style guides for tech should be required to take a networking class, or at least a history of networking class.</blockquote>
<span style="font-size: xx-small;">(The perspicacious reader will note that this happened after the 280calypse)</span><br />
Having been involved for many years with the Internet, and the Internet Engineering Task Force, and the Internet Society, my first thought was "YES! Exactly this happens to me all the time."<br />
But then I read the whole tweet, and much of the discussion, and found that I agree <i>even more</i> with <a href="https://twitter.com/heatheremerrick">Heather E. Merrick</a>, who <a href="https://twitter.com/heatheremerrick/status/928728781363191808">responded</a>:<br />
<blockquote class="tr_bq">
The AP Style Guide used to call for this but they grew up in 2016.</blockquote>
...especially after she countered Nick's <a href="https://twitter.com/feamster/status/928731005648887809">remark</a> that AP's editors "should clue up on history, and the use of proper nouns" with this <a href="https://twitter.com/heatheremerrick/status/928731290215489536">explanation</a>:<br />
<blockquote class="tr_bq">
They used to, and then they wised up to the reality that language is not in the hands of any one person or industry but The People, who enjoy using a lowercase "i," hence the update to the Stylebook.</blockquote>
<a href="https://twitter.com/ratulm">Ratul Mahajan</a> put it more succinctly (<a href="https://twitter.com/ratulm/status/928712062540308480">adding</a> a friendly health tip):<br />
<blockquote class="tr_bq">
inevitable success disaster</blockquote>
So you built the "Internet", and other people write about the "internet". My pro tip: Take it as a <b>huge compliment: </b>The thing you built has become an important part of their environment. Too vital to be considered some brand name anymore. But of course if you want to be sad about people "minimizing" your invention, that's your choice. Here's a kleenex for you!<br />
Yes, I'll continue to write Internet with a capital I. Just like I write the name of my employer as "SWITCH" as we're told to, even though everybody always does it wrong and writes "Switch". But I stopped getting mad at those people, it's just not helpful. Instead I thank them for letting <i>me</i> continue to use the "correct" spelling.<br />
When they tell me I have to stop, I'll just turn their internet off, that'll show them.<br />
<br />
"...let's turn the turning off off", OK?Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-33042769656904375622017-04-30T14:53:00.001+02:002017-04-30T14:53:44.670+02:00Google Code Jam 2017 in Lisp: Round 1B/1COnline round 1 was done on three dates again this year. The first (1A) fell in the middle of the night so I skipped it.<br />
<h3>
Round 1B <a href="https://code.google.com/codejam/contest/8294486/dashboard#s=p0">Problem A: Steed 2: Cruise Control</a></h3>
I attempted the second, 1B, but I was distracted by important household chores. That's also why I didn't make any sketches. The first problem was easy enough, and I found a solution while fixing a meal for a kid who'd just returned from boy scout camp. The basic idea is that the horses all queue up behind the slowest one, so the arrival time is the latest arrival time at the destination point for all horses. The solution (<a href="https://github.com/sleinen/code-jam-2017/blob/master/1b/A.lisp">A.lisp</a>) worked fine on the first attempt of the small dataset, and also on the large one.<br />
<h3>
Round 1B <a href="https://code.google.com/codejam/contest/8294486/dashboard#s=p1">Problem B: Stable Neigh-bors</a></h3>
<div>
The large dataset, where the unicorn's mane can have mixed colors, looked significantly more complex than the small one, where there are only three colors. I attempted a straightforward greedy algorithm, but somehow <a href="https://github.com/sleinen/code-jam-2017/blob/master/1b/B.lisp">got it wrong</a>. Because I didn't feel in a good state of mind, I decided to give up at that point. Otherwise I would have attempted the small dataset of <a href="https://code.google.com/codejam/contest/8294486/dashboard#s=p2">Problem C: Pony Express</a>. The "large dataset" cases of both problem B and problem C looked just too difficult to me.</div>
<h3>
Round 1C <a href="https://code.google.com/codejam/contest/3274486/dashboard#s=p0">Problem A: Ample Syrup</a></h3>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQgTSDPIv1WRcVVyz_E0Q59J7ppGVgcsxwPpeVnut6rjwUrePXZR_oiAIzJIMRAjRXjzExSV523LhR1mvmb1Nbdg96of-A05MMmtmeN-EEQzOvV3L6-0fN7pHTKrlO4RDWutax/s1600/IMG_20170430_142202.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="141" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQgTSDPIv1WRcVVyz_E0Q59J7ppGVgcsxwPpeVnut6rjwUrePXZR_oiAIzJIMRAjRXjzExSV523LhR1mvmb1Nbdg96of-A05MMmtmeN-EEQzOvV3L6-0fN7pHTKrlO4RDWutax/s200/IMG_20170430_142202.jpg" width="200" /></a></div>
<div>
A quick analysis suggested to me that the radius of the pancakes isn't relevant, because only the bottom (largest) one "counts", so I need to pick the pancakes with the largest lateral surface. Of course that reasoning was wrong, because we also need to pick <i>which</i> will be the bottom pancake. This error cost me two bad attempts, but I managed to reuse most of the initial code by adding a loop around it that tries various base pancakes. The code is in <a href="https://github.com/sleinen/code-jam-2017/blob/master/1c/A.lisp">A.lisp</a> and, again, worked fine for both the small and the large dataset.</div>
<h3>
Round 1C <a href="https://code.google.com/codejam/contest/3274486/dashboard#s=p1">Problem B: Parenting Partnering</a></h3>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQcGhhizOwkKmDz4rxz_iS4ltzE2baLOlVMf98cw4mmBcN8dOwrHO2J8geW0MpyCnqv1N76DGN6irLHSmnaJhpTUBbSR8Y7FI6IpdxOZUlYnjR_L3DgX_kSaxWbGoCQlhA7Ev6/s1600/IMG_20170430_142142.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="243" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQcGhhizOwkKmDz4rxz_iS4ltzE2baLOlVMf98cw4mmBcN8dOwrHO2J8geW0MpyCnqv1N76DGN6irLHSmnaJhpTUBbSR8Y7FI6IpdxOZUlYnjR_L3DgX_kSaxWbGoCQlhA7Ev6/s320/IMG_20170430_142142.jpg" width="320" /></a></div>
<div>
The optimization problem looked a bit tricky (but doable) in the general case, but the "small dataset" case was very specialized and easy enough to attack. There are only 1 or 2 activities in total. Either each partner has one, or one partner has all 1 or 2. If each partner has one, then the optimal solution always involves two exchanges. If one partner has the only one activity, the solution is even more trivially two exchanges. If one partner has (all) two activities, then the optimal solution is two if those activities can be arranged on the same "half-circle" (12 hours or 720 minutes) of the day, otherwise four. I coded these cases in <a href="https://github.com/sleinen/code-jam-2017/blob/master/1c/B.lisp">B.lisp</a> and was successful on the small dataset. In hindsight I'm surprised that it took me so long, more than 45 minutes between my submissions for A and for B-small.</div>
<h3>
Round 1C <a href="https://code.google.com/codejam/contest/3274486/dashboard#s=p2">Problem C: Core Training</a></h3>
<div>
Next, I decided to try the small dataset of problem C. While I thought B-large might be in reach for me, I was sure that C-small was easy and could be coded quickly. (I had and still have no idea how I could successfully approach C-large.)</div>
<div>
In particular, I thought that the training budget should always be spent on the worst (lowest-<i>p</i>) cores first. So I wrote this trivial loop, ahem, recursion, that spends as much as possible on those worst cores until either the budget is used up, or the worst cores become improved enough to be as good as the next-better core, or the cores reach <i>p=1</i>. But all my attempts were rejected, and embarrassingly I still don't know why. Probably my reasoning was again oversimplified. Or it was something about the Lisp representation of floating point numbers. Anyway, the non-functioning code is in <a href="https://github.com/sleinen/code-jam-2017/blob/master/1c/C.lisp">C.lisp</a>.</div>
<h3>
Conclusion</h3>
<div>
This was the end of my participation in Google Code Jam 2017, because with rank #1850 I didn't make the cut—only the top 1000 in each of the round 1 sub-rounds make it to round 2. Even if I had been successful with the small dataset of C, I wouldn't have made the top 1000. Had I successfully solved the large dataset of B with some time to spare, then it might have worked.</div>
<div>
It was mostly fun to code these small problems in Lisp. My Lisp skills are getting a bit rusty though. And I'm still not as comfortable with the SBCL/SLIME combination as I am with Allegro Common Lisp and its Emacs interface, but as I had mentioned in previous posts, I wanted to use completely free/open source software. And the awesome Allegro debugger wouldn't have been of much help here anyway.</div>
<div>
And I love the problems! Kudos to the Googlers who come up with them.</div>
<div>
<div>
How did the other Lispers fare? Badly as far as I can see. There haven't been many <a href="https://www.go-hero.net/jam/17/languages/Lisp">Lisp submissions in 2017</a> anyway, compared with <a href="https://www.go-hero.net/jam/16/languages/Lisp">2016</a>.</div>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-77433805213531135562017-04-28T15:19:00.001+02:002017-05-02T14:00:17.005+02:00Enabling BBR on Ubuntu Xenial<br />
<a href="http://queue.acm.org/detail.cfm?id=3022184">BBR</a> (Bottleneck Bandwidth and RTT) is a novel congestion control scheme for TCP. It was developed by several Google engineers and has been in use on Google.com and Youtube. See the <a href="http://kb.pert.geant.net/PERTKB/BbrTcp">PERT KB</a> for more background.<br />
Here's how you can enable it on a machine running Ubuntu 16.04 LTS "Xenial Xerus".<br />
<i>Note: This is mostly useful for systems that send fairly large TCP flows. And the configuration is incompatible with other packet schedulers such as <a href="https://www.bufferbloat.net/projects/codel/wiki/">fq_codel</a>, so consider the tradeoff.</i><br />
<h3>
Upgrade Linux Kernel to ≥4.9</h3>
<div>
The BBR implementation was merged into the master branch of the Linux kernel before the 4.9 release. Xenial uses the 4.4 kernel by default, but you can install a newer one (4.10 as of this writing) from a preview repository of the "hardware enablement" kernel provided by Canonical:</div>
<div>
<pre style="background-color: #f0f0f0; color: #777777; font-size: 1.2em; line-height: 1.3; margin-bottom: 20px; overflow: auto; padding: 10px;">sudo apt install -y --install-recommends \
linux-generic-hwe-16.04-edge</pre>
</div>
<h3>
Enable fq Packet Scheduler</h3>
<div>
BBR fundamentally requires a packet scheduler that can "pace" outgoing packets per flow. Enable this by adding an "up" clause (shown in boldface below) to each interface in its corresponding configuration file, e.g. <span style="font-family: "courier new" , "courier" , monospace;">/etc/network/interfaces.d/eth0.cfg</span>:</div>
<div>
<br /></div>
<div>
<div>
<pre style="background-color: #f0f0f0; color: #777777; font-size: 1.2em; line-height: 1.3; margin-bottom: 20px; overflow: auto; padding: 10px;">auto eth0
iface eth0 inet dhcp
<b>up tc qdisc replace dev $IFACE root fq pacing
</b>iface eth0 inet6 auto</pre>
</div>
</div>
<h3>
Make BBR the Default Congestion Control Algorithm for TCP</h3>
<div>
<div>
<pre style="background-color: #f0f0f0; color: #777777; font-size: 1.2em; line-height: 1.3; margin-bottom: 20px; overflow: auto; padding: 10px;">echo net.ipv4.tcp_congestion_control=bbr | \
sudo tee /etc/sysctl.d/90-bbr
</pre>
</div>
<h3>
Activate by Rebooting</h3>
</div>
<div>
A reboot should now enable all necessary components: the recent kernel, a pacing-capable packet scheduler, and BBR as the default.</div>
<div>
You can check whether BBR is actually in effect by using the <span style="font-family: "courier new" , "courier" , monospace;">ss -i</span> command while having at least one TCP connection open—which is already guaranteed to be the case if you are logged in over SSH.</div>
<div>
<pre style="background-color: #f0f0f0; color: #777777; line-height: 1.3; margin-bottom: 20px; overflow: auto; padding: 10px;"><span style="font-size: x-small;">$ ss --tcp -i
State Recv-Q Send-Q Local Address:Port Peer Address:Port
ESTAB 0 1848 2001:620:5ca1:2f0:f816:3eff:fe9c:71af:ssh 2001:620:0:69::107:57795
<b>bbr</b> wscale:5,7 rto:208 <b>rtt:6.078/0.237</b> ato:48 mss:1182 cwnd:12 bytes_acked:156685 bytes_received:10033 segs_out:851 segs_in:977 send 18.7Mbps lastrcv:4 lastack:4 <b>pacing_rate 87.2Mbps</b> unacked:4 retrans:0/13 rcv_rtt:12 rcv_space:28560
ESTAB 0 0 2001:620:5ca1:2f0:f816:3eff:fe9c:71af:ssh 2001:620:0:69::107:61315
<b>bbr</b> wscale:5,7 rto:220 <b>rtt:18.674/25.752</b> ato:40 mss:1182 cwnd:11 bytes_acked:8025 bytes_received:5125 segs_out:86 segs_in:122 send 5.6Mbps lastsnd:470176 lastrcv:480332 lastack:470068 <b>pacing_rate 60.5Mbps</b> rcv_rtt:12 rcv_space:28560</span><span style="font-size: 1.2em;">
</span></pre>
</div>
<div>
The "-i" part of the output mentions "bbr" and includes some BBR-specific metrics as well as the <i>pacing rate</i> applied to each outbound TCP flow.</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-45900203892457649222017-04-09T16:41:00.001+02:002017-04-10T10:27:13.495+02:00Google Code Jam 2017 in Lisp: Qualification Round<div dir="ltr" style="text-align: left;" trbidi="on">
In 2016 I was quite happy with my performance in GCJ, even though I didn't make it past <a href="http://blog.simon.leinen.ch/2016/05/google-code-jam-2016-in-lisp-round-1b1c.html">Round 1</a>. So despite being quite busy, I registered for <a href="https://plus.google.com/u/0/108344941685220406637">the 2017 edition</a> as well. The <a href="https://code.google.com/codejam/contest/3264486/dashboard#s=a">Qualification Round</a> happened yesterday. It lasted for 27 hours, starting at 1AM in my time zone. I looked at the puzzles after breakfast, and as usual found them intriguing. I initially skipped the first one (Oversized Pancake Flipper) because I knew it must be easy but I didn't find an obvious approach right away. The general approach I took was to first read the problem (out loud if a family member would be willing to listen :-), then think about it while scribbling in a notebook, then when I thought I had an efficient (should be "efficient enough") solution code it up in Lisp more or less top-down. For your amusement, I'm sharing <a href="https://goo.gl/photos/83dxAaCM5G34VTrP9">the entirety of my this year's notes</a>, including errors and culs-de-sac.<br />
<h3 style="text-align: left;">
<a href="https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=1">B. Tidy Numbers</a></h3>
<div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiDQbTBmMXQRMwVIIAIsWa2WlYsnaHOBxDpPlYB1QC_5wMnB2JYjDudfDMlbRMP-M6PVuy3wtYgFIga8tt_5bZ_SimlLNdJkjgVBZ9AIa_OYeFGtdQyrI_ahmXlzFh4P4dS1Wx6/s1600/IMG_20170409_111824.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="155" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiDQbTBmMXQRMwVIIAIsWa2WlYsnaHOBxDpPlYB1QC_5wMnB2JYjDudfDMlbRMP-M6PVuy3wtYgFIga8tt_5bZ_SimlLNdJkjgVBZ9AIa_OYeFGtdQyrI_ahmXlzFh4P4dS1Wx6/s200/IMG_20170409_111824.jpg" width="200" /></a></div>
This seemed easy and linear, and I didn't have to do much scribbling. We're looking for the largest Tidy Number that's less than or equal to the input number. We represent the input as a vector of digits. Then we start from the left and look at consecutive pairs of numbers. As long as <i>d<sub>i</sub>≤d<sub>i+1</sub></i> we're happy. If <i>d<sub>i</sub>>d<sub>i+1</sub>,</i>
we need to "fix it up". Fixing it up means usually means changing <i>d<sub>i</sub></i> to <i>d<sub>i</sub>-1</i> and replacing everything to the right with nines. We cannot run into <i>d<sub>i</sub>=0</i>, because there are no leading zeroes and we have already checked that the prefix of the number up to and including digit <i>i</i> is Tidy, so the digits cannot become lower. The local fixup may result in the overall number not being Tidy anymore, i.e.
we may have made d<sub>i</sub><d<sub>i-1</sub>. So we need to recurse (or reiterate, but hey we're thinking in Lisp, right?) on the result. We also may have introduced a leading zero that should be removed. So we remove those. The resulting code is in <a href="https://github.com/sleinen/code-jam-2017/blob/master/qr/B.lisp">B.lisp</a>. The code is recursive but not purely functional, because it munches the array using <samp>(setf (aref ...) ...)</samp>. That's ugly and might have made debugging harder, but then the code should be easy enough to not need debugging. And probably this (half-) destructive approach saves a few cycles...<br />
<h3 style="text-align: left;">
<a href="https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=2">C. Bathroom Stalls</a></h3>
</div>
<div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgeLzf-ic1boT1mWyCEFhsurHVAxlFhFXTHH6eEWks2xleYVGq8YiMII_5qZh0BE92y6pzZt4tIS3pECgBMEKBZ6e8yr2fsPJfdlDf2xMg6MG1kEEL3ZnFm-p-1EzLZUESvoG35/s1600/IMG_20170409_111834.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgeLzf-ic1boT1mWyCEFhsurHVAxlFhFXTHH6eEWks2xleYVGq8YiMII_5qZh0BE92y6pzZt4tIS3pECgBMEKBZ6e8yr2fsPJfdlDf2xMg6MG1kEEL3ZnFm-p-1EzLZUESvoG35/s200/IMG_20170409_111834.jpg" width="139" /></a></div>
This was definitely the one I had the most (and longest) fun with. It took me several hours (mostly unfocused/doing other things) to get to the breakthrough, which would of course have killed me in a "real" time-limited round.</div>
<div>
At first I drew up some simple/small examples. Starting from initial settings with (N=) 7, 6, 5, or 4 spaces, I added all N respective occupants K in order, to get an intuitive picture of how the game plays out. But I didn't find the <i>general</i> pattern.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhOJlz8dmT3PW6VALYqbEmf0N6z2xsTnABL7m42wKb7TMNxdQZMCVw-vc3vTXtxgnbfkCQIKLkkFPCCoq0bT6MU7TJ70pY5FIbpP2m0jE_HpoEDQzpgjER5c97HIg43WntVFwOm/s1600/IMG_20170409_111846.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="125" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhOJlz8dmT3PW6VALYqbEmf0N6z2xsTnABL7m42wKb7TMNxdQZMCVw-vc3vTXtxgnbfkCQIKLkkFPCCoq0bT6MU7TJ70pY5FIbpP2m0jE_HpoEDQzpgjER5c97HIg43WntVFwOm/s320/IMG_20170409_111846.jpg" width="320" /></a></div>
Pretty quickly, I had a complete understanding of the case where <i>N=2<sup>i</sup>-1:</i> The first person (K=1=2<sup>0</sup>) has <i>2<sup>i-1</sup>-1</i> space to the left and to the right, the next two (<i>2<sup>1</sup></i>) persons each have <i>2<sup>i-2</sup>-1</i> space to the left and right, and so on. But how to generalize this to <i>N</i>s that do not have this form?<br />
At any "round of the game" (K), there is a set of "extents" of free space. In each round, the largest of the current extents is "split": If the size of this largest extent is odd and larger than one, that is, of the form <i>2x+1,</i> then it will be split into two extents of size <i>x.</i> That was the "easy" case that covers the problem completely when <i>N=2<sup>i</sup>-1.</i><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiF5t2nLggAUcy1UzACWEwShByjVy0nCi-l_zZo49LoUY05GScvbCgL3nca2qYBv0WkdBc3-GzzO0di2qXCpMFooyurT2oRyUvfd0qwQqz7lJS_cgnSAqHjr0m-XsK3v9FAyvJK/s1600/IMG_20170409_111859.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="136" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiF5t2nLggAUcy1UzACWEwShByjVy0nCi-l_zZo49LoUY05GScvbCgL3nca2qYBv0WkdBc3-GzzO0di2qXCpMFooyurT2oRyUvfd0qwQqz7lJS_cgnSAqHjr0m-XsK3v9FAyvJK/s200/IMG_20170409_111859.jpg" width="200" /></a></div>
But for other kinds of <i>N,</i> I still had no good idea of the pattern how the overall set of extents develops. In a desperate attempt, I tried to draw this up as a tree for <i>N=6.</i> That looked somewhat promising, but I still couldn't figure out the general pattern. At least it shows the special case of the size-2 extent, which doesn't really get split into two extents but degenerates into a single size-1 extent. Hm, this seems complicated.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjh6HS7fx7J6yzVvjdU6pnPwetnodugepHrcL43sTfX3aXNYwwQyrkKsZDEkfem3UEPtSPk9xmC9FT3AtnMexzLWK8UiVleg7l9XX9ZFoJGQtdV47iDvp2wPgV3BX44Nb3ZR0c5/s1600/IMG_20170409_112443.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjh6HS7fx7J6yzVvjdU6pnPwetnodugepHrcL43sTfX3aXNYwwQyrkKsZDEkfem3UEPtSPk9xmC9FT3AtnMexzLWK8UiVleg7l9XX9ZFoJGQtdV47iDvp2wPgV3BX44Nb3ZR0c5/s320/IMG_20170409_112443.jpg" width="299" /></a></div>
In an even more desperate attempt, I decided that I needed to look at a bigger example and started drawing up the tree for <i>N=230. </i>Nothing very particular about that number, except that I wanted to start with an even number because that seems to be the more complicated case.<br />
Now that led to the breakthrough. In this non-trivial example, I saw that each level of the tree only contained (a maximum of) two different values with a difference of one.<br />
So a complete and useful description of a given level of the tree is the distribution between these two different values. This is what I wrote up in the right-hand column: On level 1 (after the first split) we have extents of 1x114 and 1x115, on level 2, 1x56 and 3x57, on level 3, 1x27 and 7x28, on level 4, 9x13 and 7x14, and so on. Generalizing to level 0, we can say that we start with 1x230 (1x<i>N</i>) and 0x231.<br />
But how does one get from level <i>j</i> to level <i>j+1?</i> Well, each odd extent splits into two equal extents, and each even one splits into one that's half the original number and one that's one lower. That leads to the two cases below the large (partially written-out) tree. (I started writing the cases with <i>m</i> and <i>n</i> and then replaced that with <i>a</i> and <i>b, </i>respectively, but didn't do so all the way because I had enough to write the code.) The code is in <a href="https://github.com/sleinen/code-jam-2017/blob/master/qr/C.lisp">C.lisp,</a> and I'm quite happy with it. Initially I had switched the even and odd cases, which led to wrong results on the tiny example under the problem description. First I panicked, but by simply running a few examples under <samp>(trace minmax-1)</samp> I could locate the error. I knew the code was O(log(N)) efficient, so I fed it the small, still-small, and large cases with confidence, and each was processed in less than 10 milliseconds.<br />
<h3 style="text-align: left;">
<a href="https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=0">A. Oversized Pancake Flipper</a></h3>
</div>
<div>
At this point I was fairly certain to have passed the mark with just two problems done, assuming that at least one of my "large" data set solutions were correct. But it nagged me that I hadn't turned in A, which was supposedly the easiest puzzle. I thought about it again and came up with the following reasoning: The basic operator (multi-pancake flip) is commutative—it doesn't matter whether I flip 4–6 and then 3–5, or the other way round. That means we should be able to strictly process the pancakes in some order, e.g. from left to right. The operator is also an inversion... applying it twice returns the original state and, because of the commutative property, never makes sense.</div>
<div>
So we can just go to the row of pancakes left-to-right. If the current pancake is –, we turn it and the others to its right. If the current pancake is + we leave it. Then we shift one place to the right and repeat. When we're at the end of the row (which is <i>K</i> places before the end because of the flipper restriction), we're done. The last pancakes must then all be + or we lose.</div>
<div>
The code is in <a href="https://github.com/sleinen/code-jam-2017/blob/master/qr/A.lisp">A.lisp</a>. Again, this is written recursively but destructively: The flipping is done by modifying elements in the vector (string). Probably the code would be more elegant if rewritten using a list instead of a vector, and constructing a fresh list when flipping.</div>
<div>
When reading the initial state of pancakes, I skipped the <tt>reverse</tt> (or <tt>nreverse</tt>) step because it really doesn't matter whether we operate on a mirror image.<br />
<h3 style="text-align: left;">
<a href="https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=3">D. Fashion Show</a></h3>
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIqjIxs3EYbb2jmPMKp4ZNLXj_na14LsXOrJPCBBGcpRGnHg-5B3Sa8ByimZM0eEpDClmtbGZinWnUr46WVhYroj6q6NsNFRohGW5A7r0X6NmLwZyo-mTQgsGWiUQZK9xl3BSb/s1600/IMG_20170409_161314.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIqjIxs3EYbb2jmPMKp4ZNLXj_na14LsXOrJPCBBGcpRGnHg-5B3Sa8ByimZM0eEpDClmtbGZinWnUr46WVhYroj6q6NsNFRohGW5A7r0X6NmLwZyo-mTQgsGWiUQZK9xl3BSb/s200/IMG_20170409_161314.jpg" width="150" /></a></div>
<div>
Wow, that problem sure seemed from a different league. Fewer than 1'000 contestants even got the small solution right, whereas all other problems had at least 13'000 correct solutions. My mental analysis and scribbling didn't get me very far. You cannot have more than one non-+ in the same row or column, not more than one non-x in the same diagonal. If you want to have an o (twice the value of a + or x), then all the other non-empty models in the same row/column need to be +, all on the same diagonal need to be x.</div>
<div>
There's also a parallel to the N-queens problem, in that in both cases you cannot have more than one "thing" (where thing means "queen" or "non-+/x") per row/column/diagonal. But where N-queens only has one "thing", the queen, in this case the things are different (non-+/non-x), and what's more we need to maximize some value.</div>
<div>
So I couldn't figure out a useful approach, and the fact that some initial models have been placed makes the reasoning even harder. So I gave up before even trying very hard.</div>
<h3 style="text-align: left;">
Conclusion</h3>
<div>
The next morning I checked my results for the large data sets and found them all correct. I ranked in <a href="https://code.google.com/codejam/contest/3264486/scoreboard?c=3264486#sp=4411">the 4'400s</a>, but then I started late. My 65 points would have been sufficient to enter the top 1000 if I had finished everything in 2h15. That would have been somewhat unlikely, even if I had started immediately and had been fully focused. The first sub-round of round 1 will start at 3AM local time, so I'll probably skip it and try 1B a week later, and then probably 1C. Let's see!</div>
<div>
I didn't have too much trouble with the SLIME/SBCL combination; for more than 25 years I have mostly been using Allegro and its Emacs interface when programming, and this is still much easier for me, especially when debugging. But for the contest I really wanted to use a Free/Open Source Lisp.</div>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-44882657013884734002016-05-08T15:12:00.003+02:002016-05-08T15:12:31.218+02:00Google Code Jam 2016 in Lisp: Round 1B/1C<div dir="ltr" style="text-align: left;" trbidi="on">
After <a href="http://blog.simon.leinen.ch/2016/04/google-code-jam-2016-in-lisp-round-1a.html">failing to qualify in round 1A</a> in this year's Google Code Jam, I had two more chances to advance to round 2.<br />
<h3 style="text-align: left;">
Round 1B</h3>
In round 1B, I only managed to solve the first problem, <a href="https://code.google.com/codejam/contest/11254486/dashboard#s=p0">Getting The Digits</a>. It took me quite some time, but eventually I found the recommended approach to count letters that are specific to a single digit (e.g. <b>Z</b> occurs in no other digits than <b>ZERO</b>), then eliminate those digits; initially all the even digits have unique characters (0:Z, 2:W, 4:U, 6:X, 8:G), but after those have been eliminated, this holds for other digits as well: (1:O, 3:T, 5:F, 7:S) and finally (9:I). The program is ugly in that this sequence of letter/digit combinations is hard-coded; a good program would extract the letters by itself so that it could be ported more easily to other languages etc. My Lisp code is <a href="https://github.com/sleinen/code-jam-2016/blob/master/1B/A.lisp">here</a>.<br />
<br />
Anyway, both of the other problems resisted my analysis. I should have been able to solve <a href="https://code.google.com/codejam/contest/11254486/dashboard#s=p1">Close Match</a>, but I couldn't decide whether it should be solved from left to right or right to left, and ended up spinning in circles. The final problem, <a href="https://code.google.com/codejam/contest/11254486/dashboard#s=p2">Technobabble</a>, is beyond my current capabilities: I neither succeeded in mapping the problem description to the correct graph problem (minimum edge cover on a bipartite graph), nor would I have been able to code an efficient solution to that problem. As an undergraduate I was good at these kinds of things, but lacked practice over the past 20 years or so.<br />
<br />
With only one problem set solved, I ranked #4259 and was very far from qualifying. The other Lispers didn't fare much better in this round, except for <a href="https://www.go-hero.net/jam/16/name/orivej">orivej</a>, who advanced by ranking #847. He or she only used Lisp for the first problem, and Python for the third.<br />
<h3 style="text-align: left;">
Round 1C</h3>
<div>
Again I was able to solve the first (and easiest) problem, <a href="https://code.google.com/codejam/contest/4314486/dashboard#s=p0&a=2">Senate Evacuation</a>. There are many viable approaches, and it took me a bit too long to find one. Here's my slightly embellished <a href="https://github.com/sleinen/code-jam-2016/blob/master/1C/A.lisp">A.lisp</a> (<a href="http://code.google.com/codejam/contest/scoreboard/do?cmd=GetSourceCode&contest=4314486&problem=5753053697277952&io_set_id=1&username=insertsomethingwitty">raw submission</a>).</div>
<div>
<br /></div>
<div>
After 35 minutes, I attacked the second problem, <a href="https://code.google.com/codejam/contest/4314486/dashboard#s=p1&a=2">Slides!</a> After lots of scribbling of graphs and diagonal matrices, I found a method to construct slides for an arbitrary <i>M</i> below the maximum that maps nicely to binary numbers. The resulting code (<a href="https://github.com/sleinen/code-jam-2016/blob/master/1C/B.lisp">B.lisp</a>, cleaned up from the <a href="http://code.google.com/codejam/contest/scoreboard/do?cmd=GetSourceCode&contest=4314486&problem=5744014401732608&io_set_id=1&username=insertsomethingwitty">actual submission</a>) is short and sweet and even turns out to work. But again it has taken me much too long to get there.</div>
<div>
<br /></div>
<div>
With only 16 minutes left, I looked at the final problem, <a href="https://code.google.com/codejam/contest/4314486/dashboard#s=p2&a=2">Fashion Police</a>. I knew I didn't have the slightest chance to solve the problem properly, so I started coding a brute-force algorithm that might solve the small dataset. But that was not as small as it looked, and the problem not as simple as I thought, so I failed. Well, anything else would have been a miracle.</div>
<div>
<br /></div>
<div>
My final rank was in this round #1326. I didn't qualify, but I was quite happy with this honorable (for me) result. To qualify, I would have had to finished my two working programs in 1h39'30" instead of 2h13'46". Maybe with more practice I'd be able to save those 34 minutes somewhere—but it looks like a long shot!</div>
<div>
<br /></div>
<div>
Looking at the other Lispers in the contest: This round saw an awesome result from <a href="https://www.go-hero.net/jam/16/name/lpetru">lpetru</a>, who handed in a perfect score (100 points, all problem sets solved), landing him or her on rank #98. And so far he or she submitted <b>all</b> solutions in Lisp. I know whom to root for in round 2!</div>
<h3 style="text-align: left;">
Final remarks</h3>
<div>
Again it was lots of fun to participate in Google Code Jam. It was exhausting and sometimes frustrating (especially in round 1B). But it's good to have those old brain cells work outside their comfort zone. So I'll probably try again and hope that I'll eventually manage to reach round 2. See you next year!</div>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-19831985906457978522016-04-17T16:04:00.000+02:002016-05-08T22:34:13.662+02:00Google Code Jam 2016 in Lisp: Round 1A<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: left;">
Having survived (like 96% of all Lispers and 81.5% of the wider population) the <a href="http://blog.simon.leinen.ch/2016/04/google-code-jam-2016-qualification.html">Qualification Round</a>, I'm trying to pass the first "real" round. As expected, things are getting much more serious now! Round 1 is held in three sub-rounds, and you can participate in each, or until you advance to round 2. In each sub-round, the 1'000 highest-ranking contestants advance to round 2.</div>
<div>
<br /></div>
<div>
Where the qualification round had consisted of four problems (subjectively, two easy and two somewhat tricky) with 27 hours time to solve them, round 1 is three problems (an easier one and two quite tricky ones) that have to be solved within 2h30. From previous participations I knew that I would likely run into the time limit.<br />
<br /></div>
<h3 style="text-align: left;">
Getting off to a good start</h3>
<div>
<br /></div>
<div>
Although the first sub-round, Round 1A, started at 3AM in my time zone, I decided to give it a try. I went to bed somewhat early and asked one of my sons, who was going out, to wake me up a bit before three, which he dutifully did. (Thank you!)</div>
<div>
<br /></div>
<div>
The first puzzle (<a href="https://code.google.com/codejam/contest/4304486/dashboard#s=p0">The Last Word</a>) went quite well. Somehow I convinced myself quickly that it is sufficient to put the next letter in front if it is greater than or equal to the first letter of the current substring, and at the end if it is smaller. My straightforward <a href="http://code.google.com/codejam/contest/scoreboard/do?cmd=GetSourceCode&contest=4304486&problem=5630113748090880&io_set_id=1&username=insertsomethingwitty">Lisp implementation can be found here</a>.</div>
<div>
<br /></div>
<div>
The second task (<a href="https://code.google.com/codejam/contest/4304486/dashboard#s=p1">Rank and File</a>) was cute. After a bit of scribbling and thinking, I suddenly realized that it's sufficient to look for <i>numbers that occur an odd number of times,</i> sort those numbers and be done with it. I coded this up fairly quickly as well (<a href="http://code.google.com/codejam/contest/scoreboard/do?cmd=GetSourceCode&contest=4304486&problem=5631989306621952&io_set_id=1&username=insertsomethingwitty">Lisp source here</a>).</div>
<div>
<br /></div>
<div>
So I was done with the first two problems after 44'22" with no penalties. I was also reasonably certain that I got both the large input sets right as well. (In the <a href="http://blog.simon.leinen.ch/2016/04/google-code-jam-2016-qualification.html">Qualification Round</a> I had <i>wrongly</i> believed so as well, but in the critical case of <a href="https://code.google.com/codejam/contest/6254486/dashboard#s=p2">problem C</a>, the difference between small and large input was qualitative rather than quantitative.)<br />
<br /></div>
<h3 style="text-align: left;">
Problem C: close, but no cigar</h3>
<div>
<br /></div>
<div>
With 1h45 left, I attacked the last problem, <a href="https://code.google.com/codejam/contest/4304486/dashboard#s=p2">BFFs</a>. This is a great problem—very simple in its formulation, yet requiring good (but not impossible) analysis, and also a bit of programming skills. It would be a nice recruitment interview problem.</div>
<div>
<br /></div>
<div>
This is pretty clearly a graph problem. The input set is a rather special set of directed graph with out-degree 1 (the <i>BFF</i> function). This must somehow be mapped to another kind of graph that represents a circle with some constraints. But this mapping is not that straightforward. Studying the sample inputs on the problem page, I quickly found that there are two different types of circle: One is a complete cyclic sub-graph of the input—that's easy to find given the simple type of input graph. The other possibility is to have a "core" circular graph of two nodes (a "couple" of mutual BFFs), with "extensions" of other nodes (kids) that (BFF-) point towards the nodes of the core. I wrote the code for both cases and tested it successfully against the tiny example on the problem page. My code looked for the maximum cycle, and the maximum graph of the second type, and would return the size of the bigger one.</div>
<div>
<br /></div>
<div>
To my great disappointment, the system told me that my solution for the small input set was <i>incorrect.</i> I couldn't figure out what was wrong, and time ran out on me. It was 5h30, and I had finished at rank #2137, with correct solutions for the first two problems and none for the third.</div>
<div>
<br /></div>
<div>
I went to bed slightly frustrated, and of course couldn't sleep right away but continued to think about the problem... what if the entire class consists of happy couples, i.e. mutual BFFs? Then I could put everybody in the circle. Hmmm... that's a case I had somehow missed! In fact the second type of graph (couple with "inbound" extensions) can occur arbitrarily often in the circle. Having understood my error, I could finally sleep.</div>
<div>
<br /></div>
<div>
In the next morning I had to write the code, although the contest was over. Although I had coded (correctly, I think) a good part of the necessary logic the night before, it took me several hours to get the algorithm right for the <i>actual</i> solution. I was too ambitious and wanted to write a really efficient solution ("early optimization..."), although a stupid <i>O(N<sup>2</sup>)</i> approach would probably have worked even for the maximum problem size of a 1'000 kids class. Probably I was also tired. Also, I saw that I don't know how to do proper debugging in SBCL, and had written the code in a way that made debugging somewhat hard. Finally I got the code right, see <a href="https://github.com/sleinen/code-jam-2016/blob/master/1A/C.lisp">C.lisp</a> here. Although the code is not particularly compact, I'm happy with it because at least <i>I</i> can read and understand it (for how long is another question), and it is <i>O(N)</i> with a pretty low constant factor for what that is worth—it runs in 20 milliseconds on the large practice set including I/O.<br />
<br />
<h3 style="text-align: left;">
What about the other Lispers?</h3>
</div>
<div>
<br /></div>
<div>
The per-language <a href="https://www.go-hero.net/jam/16/languages/Lisp">dashboard for Lisp</a> on go-hero.net shows that none of us advanced in sub-round 1A. A very honorable mention goes to <a href="https://www.go-hero.net/jam/16/name/vii">vii</a>, who ended up on rank #1019 with correct solutions for all problems and input sets, but with a few penalties landing him or her 2'33" above the qualifying threshold. Good job & better luck next time! I'm sure he or she has what it takes.</div>
<div>
<br /></div>
<h3 style="text-align: left;">
Will I continue to use Lisp (and SBCL)?</h3>
<div>
<br /></div>
<div>
While coding the last problem (BFFs), I sometimes thought that the program would have been easier to write in another language, even in C. I couldn't find an elegant recursive approach, and I always found writing iterative code in Lisp a bit awkward; I never really mastered <span style="font-family: "courier new" , "courier" , monospace;">loop</span> or any of the other "modern" iteration constructs—why learn them when <span style="font-family: "courier new" , "courier" , monospace;">do</span> will do? But the primary reason why I would have preferred another language was data structures. I built my graph from "node" objects (expressed as defstructs) with pointers, which was natural enough and worked well. But in another language I would have used a convenient vector representation... in Lisp the syntax for dereferencing vectors is so verbose and awkward that I was worried getting things wrong. And I felt that in the short time, I couldn't write a nice data type abstraction to hide the intricacies of such a vector representation.</div>
<div>
<br /></div>
<div>
What about <a href="http://www.sbcl.org/">SBCL</a>? As mentioned before, I normally use Franz Inc's excellent <a href="http://franz.com/products/allegrocl/">Allegro Common Lisp</a>, but I wanted to use a "real" open source system for the contest. I'm slowly getting used to <a href="https://common-lisp.net/project/slime/">SLIME</a> after more than 20 years of Franz's Emacs-Lisp interface. But when I had to debug my final BFFs solution, I felt almost blind because I wasn't able to look at local variables from within a backtrace, something that works quite nicely with Allegro. So I had to resort to the equivalent of printf()s (<span style="font-family: "courier new" , "courier" , monospace;">warn</span>), which made me feel a bit dirty. Probably I should learn how others debug under SBCL, I'm sure there's a better way! <i>[Edited to add: (declaim (optimize (debug 3))) seems to go a long way!]</i></div>
<div>
<br /></div>
<div>
In the weeks before the contest, I had toyed with the idea to use <a href="https://golang.org/">Go</a> this year, but I didn't have the time to learn the language well enough to make this viable. And overall, Lisp has treated me quite well this year. Also I've been using it for about 30 years now. So I don't feel like quitting mid-contest.</div>
<div>
<br /></div>
<div>
There are still two opportunities for me to try to advance to round 2. Timezone-wise they are much more convenient for me. On the other hand, I need some luck to find a good solution for the medium-tough problem as quickly as in 1A, and a bit more to find a good solution for the tough problem <i>at all</i>. But I'm an eternal optimist...</div>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-80795305586235675502016-04-10T21:38:00.001+02:002016-04-11T10:07:44.738+02:00Google Code Jam 2016 Qualification Round in Lisp<div dir="ltr" style="text-align: left;" trbidi="on">
This year I registered for <a href="https://code.google.com/codejam">Google Code Jam</a> again. The <a href="https://code.google.com/codejam/contest/6254486/scoreboard?c=6254486">qualification round</a> was this weekend, and I submitted solutions in Lisp. This time I used SBCL with GNU Emacs and SLIME as the IDE, rather than Allegro Common Lisp with GNU Emacs and Franz Inc's emacs-lisp interface.<br />
<a href="https://code.google.com/codejam/contest/6254486/dashboard">The puzzles</a> were lots of fun, as usual. A (Counting Sheep) and B (Revenge of the Pancakes) were easy. When I looked at C (Coin Jam), I found it tricky, so I put that aside and did D (Fractiles) next. Explaining the problem to my 19-year-old son helped me find a good approach. After implementing it and submitting the solutions, I turned back to puzzle C. My solution looked complex, and I suspected that there would be a more elegant way. Still I was happy with the solution as it produced a result for the large set very quickly, so I submitted the results and was done. My solutions can be found <a href="https://www.go-hero.net/jam/16/name/insertsomethingwitty">here</a>.<br />
<h3 style="text-align: left;">
So how did I fare?</h3>
<div>
The round went on for 27 hours, and I started somewhere in the middle due to timezone. So after I was done with my solutions, I had to wait until the next day to see the final score. The "small" problem datasets are checked immediately after submission, so I already knew I had all of those right before I went to bed. Since they already accounted for 37 points, and I needed 40 to advance to the next round, I could be pretty optimistic that I had passed—having <i>any</i> large dataset correct would get me more than the three missing points.</div>
<div>
The intermediate scoreboard put me on rank #1189; this is assuming (for everybody) that all the "large" solutions that were submitted would be correct. I was pretty sure that mine were all correct, so I had hopes that my final rank would be even higher.</div>
<div>
But my final rank was #2748, because it turned out that my "large" solution for D (Fractiles) was incorrect. This was a big disappointment, because I was very confident in my solution approach. And it turned out that my error was a stupid one in one of the "easy" parts of the implementation; the decision whether the number of grad students (S) is sufficient to clean enough tiles in the base-length-K and complexity C artwork to detect whether there's any gold tile. The correct test would be</div>
<pre> (if (< (* s c) k)
"IMPOSSIBLE"
</pre>
...but I used:
<br />
<pre> (let ((min-s (truncate k c)))
(if (< s min-s)
"IMPOSSIBLE"
</pre>
My test was too lax, and I sometimes output a "solution" when I should have printed <tt>IMPOSSIBLE</tt>. This stupid mistake cost me >2000 ranks. It would be nice if I managed to avoid this in the next round. But realistically I'll make even more of these mistakes because the problems will be harder and the time pressure much higher.<br />
<h3 style="text-align: left;">
How did the other Lispers do?</h3>
<div>
On www.go-hero.net there are statistics about GCJ participants and submissions, and it's easy to find all <a href="https://www.go-hero.net/jam/16/languages/Lisp">submissions for this round that used Lisp</a>. We Lispers were quite successful this weekend, with 26 out of 27 proceeding to the next round, a success rate of 96% compared to 81.5% for the entire population.<br />
The highest ranking Lisper was <a href="https://www.go-hero.net/jam/16/name/lpetru">Ipetru</a> at #594 with all solutions in Lisp (and of course all correct). I looked at his solutions for C and D, and they are so incredibly compact that I couldn't believe my eyes. D used the same approach as I had, just very elegantly written—the code proper is about two lines; much harder to hide stupid mistakes in there! C used a completely different approach, deterministically generating Jamcoins rather than checking candidates as I had.<br />
The second-ranking Lisper was <a href="https://www.go-hero.net/jam/16/name/DarkKnight.">DarkKnight.</a> at #720. He only wrote one solution in Lisp. In fact he used different languages for all solutions, and I mean all 8 solutions, not all 4 puzzles! bc, OCaml, Lisp, Racket, Lua, Perl, Octave, R. Impressive! :-)</div>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-82785277195315292792015-02-13T17:44:00.002+01:002015-02-13T17:44:45.090+01:00BloFELD<div dir="ltr" style="text-align: left;" trbidi="on">
<p> <a href="https://panopticlick.eff.org/">Panopticlick</a> illustrates that even without cookies etc., modern browsers usually send enough specific-enough information to Web servers so that you can be tracked. The various useful standard HTTP headers effectively work like a fingerprint of your browser/OS/hardware combination. </p>
<p> When I look at the Panopticlick results of my favorite browser (I get 22.26 bits of "identifying information", while more senior users have reported scores up to full 24 :-), one thing that stands out is a long list of "System Fonts". Arguably it is useful for me when Web sites know what fonts I have installed on my system, so that they can present Web pages with fonts that I actually have rather than having to send me the fonts as well. So the intention is good, but the implementation discloses too much of my typographic tastes. What can we do to fix this? </p>
<p> Well, that should be quite obvious: Instead of my browser sending the full list of fonts, it could send a Bloom filter that matches the fonts that I have. When a Web server wants to render a document for me, it can check for some candidate fonts whether I have them. Bloom filters are approximative and will sometimes generate false positives, but one Comic Sans Web page in 1'000 or so should be a small price to pay to get my <strike>virginit</strike>privacy back. </p>
<p> You may respond that a priori the Bloom filter discloses as much of my privacy as the full list of fonts. But! I can simply send a new Bloom filter ("salted" differently) to each site I visit. Voilà how I'll defeat all traceability of Web visits, undermine the business model of the Internet economy, and destroy the entire Western civilization. Muahaha! </p>
<div align="right"><p> -- BloFELD <br />
(Bloom Filter-Enabled Limited Disclosure) </p></div>
<p> (Apologies to smb and Bill Cheswick, who seem to have fully baked and <a href="https://mice.cs.columbia.edu/getTechreport.php?techreportID=483">published</a> a better version of this idea in 2007, and to the probably numerous others) </p>
<br /></div>Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-10128187.post-65756723500693257022015-02-06T11:42:00.000+01:002015-02-06T12:12:15.797+01:00Ceph Deep-Scrubbing Impact Study<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<h3 style="text-align: left;">
Context</h3>
<p> I help operate two geographically separate OpenStack/<a href="http://ceph.com/">Ceph</a> clusters
consisting of 32 servers each, of which 16 (per cluster) are dedicated
<a href="http://ceph.com/docs/master/man/8/ceph-osd/">OSD</a> servers. Each OSD server currently has six OSDs. Each OSD runs
on a dedicated 4TB SAS disk. Each server also has SSDs, which are
mostly used for OSD write journals. </p>
<p> We monitor our systems using the venerable Nagios.
My colleague Alessandro has written many specific
checks for infrastructure services such as Ceph. Some of them
periodically check the logs for possibly non-harmless messages. It can be interesting to try to understand these messages and get down to their root cause. Here's one from early this morning (edited for readability): </p>
<blockquote class="tr_bq">
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">monitor writes:<br />
> Service: L_check_logfiles<br />
> State: WARNING<br />
> Output: WARN - WARNING - (30 warnings in check_logfiles.protocol-2015-02-06-03-35-35) - File=/var/log/ceph/ceph.log Message=2015-02-06 03:35:26.877633 <span style="color: orange;">osd.1</span> [2001:db8:625:ca1e:100::1021]:6800/219476 2257 : [WRN] <span style="color: orange;">slow request 30.185039 seconds old</span>, received at 2015-02-06 03:34:56.692108: osd_op(client.1932427.0:27645811 rbd_data.1fd765491f48ea.00000000000000a9 [stat,set-alloc-hint object_size 8388608 write_size 8388608,write 52720648192] 5.4220493a ack+ondisk+write e9526) v4 currently no flag points reached ...<br /></span></blockquote>
<p> The "Output" line tells us that a write operation to osd.1 was stuck in a queue for 30+ seconds around 03:35. Why did that happen in the middle of the night, when utilization is low?</p>
<h3> Graphite to the Rescue </h3>
<p> Lately we have set up a <a href="https://collectd.org/">CollectD</a>/<a href="http://graphite.wikidot.com/">Graphite</a> monitoring
infrastructure for each site. It collects data in ten-second
intervals. The ten-second samples are only retained for three
hours, then aggregated to one-minute samples that are retained for
24 hours, and so on. Because this event happened at night, I missed
the fine-grained samples, so all the graphs shown here have one-minute temporal
resolution.</p>
<p> The event is visible from the "#Ceph" dashboard on our Graphite installation. I extracted a few graphs from it and focused them on the event in question. </p>
<p> Here is a graph that shows block I/O (actually just "I") operations per second of all OSD processes summed up for each OSD server: </p>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFj1j5fc0djfIfdD7zNGUcjAJfXQnUw4wpsqcEGsyXO8OesqwunEDed4TYOB4njuU9DlYLdhlry3JYLgh4p072AVNpdjxbDZ-Ft0N4uKNWZxz3Quq7GFmv6G6ZbW3zTxReiEm3/s1600/20150206-top-osd-read.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFj1j5fc0djfIfdD7zNGUcjAJfXQnUw4wpsqcEGsyXO8OesqwunEDed4TYOB4njuU9DlYLdhlry3JYLgh4p072AVNpdjxbDZ-Ft0N4uKNWZxz3Quq7GFmv6G6ZbW3zTxReiEm3/s1600/20150206-top-osd-read.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<p> These patterns (a few OSD servers reading heavily) indicate
"scrubbing" activity (scrubbing checks existing data for
correctness). </p>
<p> We can look at the block I/O read rates on the individual OSD
disks on ceph21: </p>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEip-TESPz5ndzmBz3PCQ9AMeOJqMTOTHo8E0v_uskbYhfCd0rt6o09Q5JHYOEBBBidfpzUKMRNWJAE9IpwgCUyXad8YWvIi_6jrM_iZdo5RoUt4bD65nP-jtAXRUVvIMt-pAmT-/s1600/20150206-ceph21-top-read-sd.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEip-TESPz5ndzmBz3PCQ9AMeOJqMTOTHo8E0v_uskbYhfCd0rt6o09Q5JHYOEBBBidfpzUKMRNWJAE9IpwgCUyXad8YWvIi_6jrM_iZdo5RoUt4bD65nP-jtAXRUVvIMt-pAmT-/s1600/20150206-ceph21-top-read-sd.png" /></a></div>
<p> and see that /dev/sdc, /dev/sdd and /dev/sde were quite busy, while the other three OSD disks were mostly idle. </p>
<p> The busy devices correspond to osd.0, osd.1 and osd.2: </p>
<pre> $ ssh ceph21 'mount | egrep "/dev/sd[cde]"'
/dev/sde1 on /var/lib/ceph/osd/ceph-0 type xfs (rw,noatime)
/dev/sdc1 on /var/lib/ceph/osd/ceph-2 type xfs (rw,noatime)
/dev/sdd1 on /var/lib/ceph/osd/ceph-1 type xfs (rw,noatime)
</pre>
<p> So we have strong confirmation that osd.1 (which was slow) was being scrubbed (heavily read from). If we look for "scrub" messages in the OSD log around that time, we see that there were in fact three deep-scrubs finishing between 03:38:11 and 03:38:40: </p>
<pre> $ ssh ceph21 'fgrep scrub &lt;(gzip -dc /var/log/ceph/ceph-osd.*.log.1.gz) | sort -n' | egrep ' 03:[345]'
2015-02-06 03:38:11.058160 7f3376f7f700 0 log [INF] : 5.13a deep-scrub ok
2015-02-06 03:38:36.608224 7ffe093c4700 0 log [INF] : 5.111 deep-scrub ok
2015-02-06 03:38:40.711687 7f29ac56c700 0 log [INF] : 5.15a deep-scrub ok
</pre>
<p> The OSD logs unfortunately don't tell us when these scrubs were started, but from looking at the the graphs, in particular the second one, we can guess with high confidence that they all started between 03:21 and 03:22. </p>
<p> Now we can check which OSDs these PGs map to, and we find that,
indeed, they respectively include OSDs 0, 1, and 2: </p>
<pre style="text-align: left;"> $ ceph pg dump all | egrep '\&lt;(5\.1(3a|11|5a))\&gt;' | awk '{ print $1, $14 }'
dumped all in format plain
5.15a [0,56,34]
5.13a [1,64,70]
5.111 [2,66,86]
</pre>
<h3 style="text-align: left;"> Conclusions </h3>
<ul>
<li> Deep-scrubbing has an impact on Ceph performance </li>
<li> It can happen that, on a given server, multiple OSDs are busy
performing deep scrubs <em>at the same time</em></li>
<li> When three deep-scrubs happen in parallel on the same server, the
impact can be very visible and lead to >30s queues. This also seems
to affect <em>write</em> OPs, not just reads. </li>
</ul>
<p> I am somewhat surprised by this, as I would have thought that the
impact is mostly due to "per-spindle" limitations (random read
op/s), but maybe there's another bottleneck. One possibly
interesting observation is that the three disks in question are
connected to the same SAS host adapter, namely the one at PCI
address 05:00.0 (there's a second host adapter on 83:00.0): </p>
<span style="font-family: Courier New, Courier, monospace; font-size: small;"><pre>$ ssh ceph21 'ls -l /dev/disk/by-path/*-lun-0'
$ ssh zhdk0021.zhdk.cloud.switch.ch 'cd /dev/disk/by-path && /bin/ls -l *-lun-0 | cut -c 38-'
pci-0000:05:00.0-sas-0x4433221100000000-lun-0 -> ../../sdc
pci-0000:05:00.0-sas-0x4433221101000000-lun-0 -> ../../sde
pci-0000:05:00.0-sas-0x4433221102000000-lun-0 -> ../../sdd
pci-0000:05:00.0-sas-0x4433221103000000-lun-0 -> ../../sdf
pci-0000:83:00.0-sas-0x4433221100000000-lun-0 -> ../../sdg
pci-0000:83:00.0-sas-0x4433221101000000-lun-0 -> ../../sdh
pci-0000:83:00.0-sas-0x4433221102000000-lun-0 -> ../../sdi
pci-0000:83:00.0-sas-0x4433221103000000-lun-0 -> ../../sdj
pci-0000:83:00.0-sas-0x4433221104000000-lun-0 -> ../../sdk
pci-0000:83:00.0-sas-0x4433221105000000-lun-0 -> ../../sdl
pci-0000:83:00.0-sas-0x4433221106000000-lun-0 -> ../../sdm
pci-0000:83:00.0-sas-0x4433221107000000-lun-0 -> ../../sdn
</pre></span>
<p> Maybe that SAS adapter was the bottleneck in this case.</p>
<h3 style="text-align: left;"> Possible avenues for improvement </h3>
<h4> Better foreground/background I/O isolation </h4>
<p> Ceph could do a (much) better job isolating actual user I/O from "background" I/O caused by tasks such as scrubbing or rebalancing. See Loïc Dachary's post on <a href="http://dachary.org/?p=3268">Lowering Ceph scrub I/O priority</a> for something that can be configured on recent-enough versions of Ceph. (Thanks for the pointer, Harry!) </p>
<h4> Better scrub scheduling </h4>
<p> Ceph could do a (much) better job spreading out deep-scrubs over time. The effect described here is not an isolated occurrence - earlier I had observed periods of massive deep-scrubbing, with multi-day periods of no deep-scrubbing at all between them. For example, this is the block read-rate graph across our other Ceph cluster over the past 60 hours: </p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg0RFJNJOPA_JUo4xkf_IHuO1IweXx0LECRqYtyntQKt8FFLqtI_xDAGElf_EetUDfSxj-qh7nD4sKxY-DTMyV_Fc1VZvPJelDbqFtfj7vM0PL0dh9MVVKEinJ6RbMZy22oQxKi/s1600/cluster2-osd-read-60h.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg0RFJNJOPA_JUo4xkf_IHuO1IweXx0LECRqYtyntQKt8FFLqtI_xDAGElf_EetUDfSxj-qh7nD4sKxY-DTMyV_Fc1VZvPJelDbqFtfj7vM0PL0dh9MVVKEinJ6RbMZy22oQxKi/s1600/cluster2-osd-read-60h.png" /></a></div>
<p> You see that all the deep-scrubbing is done across one 20-hour period. Crazy! This should be evenly spread out over a week (the global deep-scrub interval). </p>
<h4> OSD/controller mapping on our hosts </h4>
<p> We could do a better job distributing (consecutive) OSDs across controllers. While we're at it, we should also make sure that journals are distributed nicely across all SSDs, and that we never get confused by changing kernel device names for our SAS disks. And I want a pony. </p>
<p> Any other ideas? </p>
</div>Unknownnoreply@blogger.com0Zurich, Switzerland47.377027753482416 8.5601914356811947.374339753482417 8.55514893568119 47.379715753482415 8.56523393568119tag:blogger.com,1999:blog-10128187.post-30990078555048024942014-06-25T18:52:00.000+02:002014-06-26T15:42:12.076+02:00Riding the SDN Hype Wave<div dir="ltr" style="text-align: left;" trbidi="on">
In case you haven't noticed, <i>Software-Defined Networking</i> has become the guiding meme for most innovation in networks over the past few years. It's a great meme because it sounds cool and slightly mysterious. The notion was certainly inspired by <i>Software-Defined Radio,</i> which had a relatively well-defined meaning, and has since spread to other areas such as <i>Software-Defined Storage</i> and, coming soon, the <i>Software-Defined Economy.</i><br />
As a networking veteran who has fought in the OSI and ATM wars, I like making fun of these fads like the next person—buzzword bingo anyone? But actually, I consider the SDN hype a really good thing. Why? Because, to quote Cisco CTO Padmasree Warrior, <a href="http://blogs.cisco.com/news/networking-is-cool-againand-thats-good-for-cisco/">"networking is cool again"</a>, and that's not just good for her company but a breath of fresh air for the industry as a whole.<br />
What I like in particular is that SDN (because nobody knows exactly what it means and where its limits are...) legitimates ideas that would have quickly been rejected before ("it has been known for years that this doesn't scale/that this-and-that needs to be done in hardware/..."). Of course this also means that many tired ideas will get another chance by being rebranded as SDN, but personally I think that this does less damage.<br />
<h3 style="text-align: left;">
SDN Beyond OpenFlow</h3>
<div>
The public perception of SDN has been pretty much driven by OpenFlow's vision of separating forwarding plane (the "hardware" function) and control plane, and using external software to drive networks, usually using a "logically centralized" control approach.</div>
<div>
The Open Networking Forum attempts to codify this close association of SDN and OpenFlow by publishing <a href="https://www.opennetworking.org/sdn-resources/sdn-definition">their own SDN definition</a>. OpenFlow has huge merits as a <i>concrete</i> proposal that can be (and is) implemented and used in real systems. Therefore it deserves a lot of credit for making people take the "SDN" vision seriously. But I think the SDN meme is too beautiful to be left confined to OpenFlow-based and "logically centralized" approaches. I much prefer JR Rivers's (Cumulus Networks) suggestion for what SDN should be: <i>"<a href="http://vimeo.com/87216036#t=14m48s">How can I write software to do things that used to be super hard and do them super easy?</a>"</i> That's certainly more inclusive!</div>
<h3 style="text-align: left;">
x86 as a Viable High-Speed Packet Processing Platform</h3>
<div>
Something that I <i>definitely</i> consider an SDN approach is to revisit generic computing hardware (mostly defined as "x86" these days) and see what you can do in terms of interesting packet processing on such platforms. It turns out that these boxes have come a long way over the past few years! In particular, recent Intel server CPUs (Sandy Bridge/Ivy Bridge) have massively increased memory bandwidth compared to previous generations, CPU cores to spare. On the interface front, most/all of today's 10 Gigabit Ethernet adapters have many helpful performance features such as multiple receive/transmit queues, segmentation offload, hardware virtualization support and so on. So is it now possible to do line-rate 10Gb/s packet processing on this platform?</div>
<div>
The dirty secret is that even the leading companies in ASIC-based backbone routers are already using regular multi-core CPUs for high-performance middleboxes such as firewalls (as opposed to previous generations that had to use expensive-to-design and program network processors, FPGAs and/or ASICs).</div>
<div>
Intel has its DPDK (Data Plane Development Kit) to support high-performance applications using their network adapters and processors, and there are several existence proofs now that you can do interesting packet processing on multiple 10Gb/s interfaces using one core or less per interface—and you can get many of those cores in fairly inexpensive boxes.</div>
<h3 style="text-align: left;">
Snabb Switch</h3>
<div>
One of my favorite projects in this space is Luke Gorrie's <a href="https://github.com/SnabbCo/snabbswitch">Snabb Switch</a>. If CPU-based forwarding approaches are at the fringe of SDN, Snabb Switch is at the fringe of CPU-based forwarding approaches... hm, maybe I just like being different.</div>
<div>
Snabb Switch is based on the Lua scripting language and on the excellent LuaJIT implementation. It runs entirely in user space, which means that it can avoid all user/kernel interface issues that make high-performance difficult, but also means that it has to implement its own device drivers in user space! Fortunately Lua is a much friendlier platform for developing those, and one of Luke's not-so-secret missions for Snabb is that "writing device drivers should be fun again".</div>
<div>
The Snabb Switch project has gained of traction over the year or so since its inception. A large operator is investigating its use in an ambitious backbone/NFV project; high-performance integration with the QEMU/KVM hypervisor has been upstreamed; and the integration into OpenStack Networking is making good progress, with some hope of significant parts being integrated for the "Juno" release. And my colleague and long-time backbone engineering teammate Alex Gall is developing a standalone <a href="https://www.youtube.com/watch?v=Jbn3aNkud6Y">L2VPN (Ethernet over IPv6) appliance</a> based on Snabb Switch, with the ultimate goal of removing our only business requirement for MPLS in the backbone. Now that should convince even the curmudgeons who fought in the X.25 wars, no?</div>
<div>
The final proof that Snabb Switch's world domination is inevitable is that it was featured in the <a href="http://blog.ipspace.net/2014/06/snabb-switch-and-nfv-on-openstack-in.html">pilot episode of Ivan Pepelnjaks new <i>Software Gone Wild</i> podcast</a>.</div>
<div>
<span style="font-size: x-small;">(In fact that is the very reason for <i>this</i> post, because yours truly also had a (small) appearance in that episode, and I had to give up the address of my blog... and now I'm afraid that some of the venerable readers of Ivan's blog will follow the link and find that nothing has been posted here lately, even less so related to networking. Welcome anyway!)</span></div>
<h3 style="text-align: left;">
Come on in, the water's fine!</h3>
<div>
So turn your bullshit detectors way down, embrace the hype, and enjoy the ride! There are plenty of good ideas waiting to be implemented once we free ourselves from the rule of those ASIC-wielding vertically integrated giga-companies...</div>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-79640803851203018312012-05-13T17:20:00.000+02:002012-05-14T14:21:44.165+02:00<div dir="ltr" style="text-align: left;" trbidi="on">
<h1>
Hello World with ØMQ (ZeroMQ), Part I </h1>
<h2>
Why I am interested in ØMQ </h2>
Several months ago, I stumbled across an <a href="http://twit.cachefly.net/floss0195.mp3">interview</a> with
Pieter Hintjens about <a href="http://www.zeromq.org/">ØMQ
(ZeroMQ)</a> in <a href="http://twit.tv/show/floss-weekly/195">episode
195</a> of <i>FLOSS Weekly</i> by Randal L. Schwartz. From what I got
from the interview, ØMQ is a pretty powerful "message queue" system
that is somehow implemented in a light-weight way as a linkable
library. There are also many language bindings, including all
fashionable and many exotic languages (but, sadly, not Common
Lisp). <br />
I had heard about message queue systems for a long time, but have
never really used any, and they always seemed a little scary. The
currently popular message queue system seems to be RabbitMQ, and
despite the cute name, I hear that it is somewhat big. At the same
time, I'm sure that message queues serve a useful purpose, and may
be a great basis for distributed systems with fewer reinvented wheels
and, thus, better behavior (including performance), so they probably
deserve a closer look. And ØMQ seems to be successful in several
respects, and at the same time "lightweight" enough for me to understand something. This makes it an attractive system to
investigate. <br />
<h2>
First steps </h2>
I have finally found time to start reading the <a href="http://zguide.zeromq.org/page:all">ØMQ Guide</a> during a train
ride from Geneva to Zurich. <br />
The <a href="http://zguide.zeromq.org/page:all#Fixing-the-World">introduction ("Fixing the world")</a> at first looks a little
pompous, but is in fact full of very good thoughts, both original
and convincing, about big problems in programming large distributed
software systems. Apparently ØMQ aspires at solving an important part
of these problems. Judging from the introduction, the people who
wrote this seem very smart. And from the interview, I know that the
designers have had a lot of practical experience building real
systems, and they knew the deficiencies (but also the achievements) of
other messaging systems before they started rolling their own. <br />
<h3>
Walking through the "Hello World" example </h3>
So now I'm reading through the <a href="http://zguide.zeromq.org/page:all#Ask-and-Ye-Shall-Receive">first, "Hello World", example </a>in
the guide, trying to understand as much as possible about ØMQ's
concepts. The example starts with the server side (which responds
"World"). I cut & paste the complete code to a file <tt>server.c</tt>, which
compiles easily enough on my Ubuntu 12.04 system with
<tt>libzmq-dev</tt> installed: <br />
<pre> : leinen@momp2[zmq]; gcc -c server.c
: leinen@momp2[zmq]; gcc -o server server.o -lzmq
: leinen@momp2[zmq];
</pre>
When trying to understand an ØMQ API call, I first guess a little
what the names and arguments could mean, then I look at the respective
man page to validate my guesses and to learn the parts that I was
unable to guess. <br />
<pre> void *context = zmq_init (1);
</pre>
Why is the result type <samp>void *</samp>, rather than something like
<samp>ZqmContext *</samp>? I'll explain in a mpment why I would strongly prefer the latter. <br />
And wouldn't it be nice if the size of the thread pool (the <samp>1</samp> in the
call) could be left undefined? The ØMQ system could either optimize
it dynamically, or it could be controlled by standardized external
configuration. But maybe this isn't really practical anyway. <br />
<pre> // Socket to talk to clients
void *responder = zmq_socket (context, ZMQ_REP);
</pre>
The socket call is simple enough, taking just one argument beyond
the necessarily required context - the socket type (here: <samp>ZMQ_REP</samp>),
"which determines the semantics of communication over the socket." So
what does <tt>ZMQ_REP</tt> mean, and what other types are available? Aha, "REP"
is for "reply", and the complementary type is <tt>ZMQ_REQ</tt>, for "request".
So these must be for the standard request/response pattern in
classical client/server protocols. <br />
Other types include <samp>ZMQ_PUB/ZMQ_SUB</samp> for pub/sub protocols,
<samp>ZMQ_PUSH/ZMQ_PULL</samp> for processing pipelines, and a few others related
to, if I understand correctly, load balancing, request routing
etc. <br />
That's a great choice of patterns to support, because
they cover a huge subspace of socket applications in real
applications. <br />
<pre> zmq_bind (responder, "tcp://*:5555");
</pre>
In passing, I notice that this call doesn't take a "context"
argument. This probably means that it gets the context from the
socket (here: "responder"). Convenient. But, coming back to my previous complaint, <tt>responder</tt> is also of type <samp>void *</samp>. So what happens when someone is only slightly confused and passes <tt>context</tt> to <tt>zmq_bind</tt>? The compiler certainly has no way of catching this. In fact, when I deliberately introduce this error, I find that even the library doesn't catch this at runtime! I just get a server program that mysteriously sits there and doesn't listen on any TCP port. That is really not nice. Maybe real programmers don't make these kinds of mistakes, but I have my doubts. As an old Lisper, I'm certainly not religious about static type checking. But type checking <em>at some point</em> would really be beneficial. <br />
OK, back to the <samp>zmq_bind</samp> call. We have a responding socket, so we need to bind it to a
"listening" port. The API uses URL-like strings to specify endpoint
addresses (<samp>tcp://*:5555</samp>). This is fine, although I'm slightly
worried whether the API developers try to adhere to any standards here
(is there a standard for "tcp" URLs?), or whether they just make
things up. <br />
The URL-like string approach is certainly superior to what people
using the C socket API have to put up with: Use the right sockaddr
structures, use getaddrinfo() (and NOT use gethostbyname() anymore!
:-), do address resolution error handling by hand, etc. <br />
<h3>
ØMQ could support IPv6, but does it? </h3>
One can easily imagine that the library just Does The Right Thing
(DTRT) concerning multiple network-protocol support, e.g. that the
above call results in a socket that accepts connections over both IPv4
and IPv6 if those are supported. <br />
<h4>
Not just yet, it seems. </h4>
Unfortunately this doesn't seem to be the case however: When I run
the compiled server.c binary under system-call tracing, I get <br />
<pre> : leinen@momp2[zmq]; strace -e bind ./server
bind(16, {sa_family=AF_INET, sin_port=htons(5555), sin_addr=inet_addr("0.0.0.0")}, 16) = 0
C-c C-c: leinen@momp2[zmq];
</pre>
So this is obviously an IPv4-only socket. Still, if I look inside
libzmq.a (in GNU Emacs in case you are curious, though <samp>nm |
grep</samp> would also work), I notice that it references getaddrinfo,
but not gethostbyname. So there is at least some chance that someone
thought of IPv6. Maybe one has to set special options, or maybe the
people who built the Ubuntu (or Debian) package forgot to activate
IPv6, or whatever? <br />
Looking at the man page of <tt>zmq_tcp</tt>, ("ØMQ unicast transport
using TCP"), it only talks about "IPv4 addresses". The way I
interpret this is that they only support IPv4 right now, but at least
they don't ignore the existence of IPv6, otherwise they would have
just said "IP addresses" and still meant IPv4 only. So there is at
least a weak hope that IPv6 could once be supported. <br />
When I briefly had connectivity (because the train stopped at a
station with WiFi), I googled for [zmq ipv6] and found a few entries
that suggest that there has been some work on this. Maybe the most
promising result I got from Google was this: <br />
<cite>
[zeromq-dev] IPv6 support - Grokbase<br />
<a href="http://grokbase.com/t/zeromq/zeromq-dev/118fjjmpmc/ipv6-support">http://grokbase.com/t/zeromq/zeromq-dev/118fjjmpmc/ipv6-support</a><br />
15 Aug 2011 – (5 replies) Hi all, Steven McCoy's IPv6 patches were merged into the master. The change should be completely backward compatible.<br />
</cite>
<br />
So this fairly new. I also noticed that the libzmq in my
brand-new Ubuntu 12.04 is only version 2.11.11, and some other Google
hits suggest that IPv6 support is planned for ØMQ 3.0. So when I get
home I'll check whether I can find ØMQ 3 or better, and use that in
preference to the Ubuntu package. <br />
<h3>
What about multi-transport support? </h3>
So we learned that multiple network-layer support (e.g. IPv4 and
IPv6) seems possible, and even planned. What about support for
multiple different transports? This is certainly not possible using
low-level sockets, and it seems difficult, but not impossible, to
provide this transparently using a single ZMQ-level socket. For
example, a server endpoint could listen requests on both TCP and SCTP
connections. <br />
I have a hunch that ØMQ doesn't support this, because the standard
interface has only a single scalar socket-type argument. In some
sense this is a pity, because having a single socket that supports
multiple protocols would make it easier to write programs that live in
a multi-protocol world, just like support for multiple network
protocols in a single socket makes it easier to write programs that
live in a world with multiple such protocols, like IPv4 and IPv6 these
days. <br />
Conceptually, ØMQ looks powerful enough to support this without
too much pain. It might also be possible to build "Happy Eyeballs"
functionality into the library, so that in such multi-protocol
contexts, the library could make sure that a reasonably
well-performing substrate is always used, so that developers using the
library don't have to worry about possible problems when they add
multi-protocol support. <br />
<h2>
Swiss trains go too fast, or Switzerland is too small </h2>
So I only got through a whopping two lines of Hello World code for
now. But I hope my sidelines and confused thoughts didn't turn you
off, and you still agree with me that ØMQ is something worth watching.
I sure hope I'll find the time to continue exploring it. </div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-73247882057064031772012-02-07T22:52:00.002+01:002012-02-07T22:53:48.035+01:00Chrome Beta for Android, first impressions<div dir="ltr" style="text-align: left;" trbidi="on">
So Google published a beta of <a href="http://chrome.blogspot.com/2012/02/introducing-chrome-for-android.html">Chrome for Android</a>. It's only available for Android 4.0 "Ice Cream Sandwich", which caused many complaints. I find this somewhat understandable because Chrome uses fancy graphics, e.g. for the interface of changing between multiple tabs. What I have a harder time understanding is why they restricted it to a handful of countries in Android Market. Fortunately the comments on a <a href="https://plus.google.com/104629412415657030658/posts/d82636G5qm3">Google+ post</a> contain hints on how this can be circumvented - thanks, <a href="https://plus.google.com/109682994934265354442">+AJ Stang</a>!<br />
First impressions from using this for a few minutes on a Nexus S: The multiple-tabs feature seems very powerful, and the UI for changing between them seems to work really well on a small mobile device. Being able to use the Chrome development tools (profiler, DOM inspector etc.) over USB is also quite cool. It does seem a little slower than the standard Web browser in Android though. As a heroic experiment on myself I'm making this my default browser for now.</div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-66643880487321269812012-02-03T18:11:00.004+01:002012-02-03T18:18:42.236+01:00The inexorable growth of bandwidth, or lack thereof<div dir="ltr" style="text-align: left;" trbidi="on">
I moved offices recently, so I threw away some old posters. One of them was an <a href="http://archive.geant.net/upload/pdf/GEANT_3_posters_in_1_Dec_2001_20031029154921.pdf">old map of the GÉANT backbone</a>. On a first look, I was wondering how old it was - the main backbone links were all 10Gb/s, much like <a href="http://www.geant.net/Media_Centre/Media_Library/Media%20Library/1083_GEANT_Topology_June_11.pdf">today</a> (a few links have been updated to 2-3*10Gb/s or 40Gb/s last year). To my surprise, the poster was from 2001. So for ten of the last eleven years, the standard backbone link capacity for large research backbones has stagnated at 10 Gb/s. (I know other things have changed... these things have become more "hybrid" and stuff.)<br />
In a similar vein, the standard network interface for a standard 1RU or 2RU rackmount server has been Gigabit Ethernet (1Gb/s) in 2001, and it is still GigE in 2012 - although servers generally have at least two and commonly four of them. You can get servers with 10GE interfaces, but this is not the norm.<br />
The main reason is probably that the upgrades to 10Gb/s or GigE in 2001 were "too early", or based on too optimistic assumptions of future growth. Anybody remember <a href="http://www.dtc.umn.edu/~odlyzko/isources/index.html">Sidgmore's law</a>?<br />
But I think that demand has eventually caught up, and that we're on the brink of moving beyond these steps. For servers, it seems clear that GigE will be replaced by 10GE. For this to happen, it needs to be on the motherboard, and probably in the twisted-pair variety. For backbones, the preferred option in most circles seems to be to move to 100GE. Personally I think that 40GE or even 10GE, in connection with link bundling (as is already done in the commercial world) could be interesting alternative options, also for research networks.</div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-9098111924432981792010-09-02T10:36:00.000+02:002010-09-02T10:36:54.780+02:00Traceroute puzzleWhich ISPs appear in the following traceroute, and where do they interconnect?<br />
<br />
<pre> 1 swiCE3-10GE-1-4.switch.ch (130.59.36.210) 0 msec # local AS: 559
2 bb1.tor.primus.ca (195.69.145.154) [AS 3549] 108 msec
3 216.254.129.3 (216.254.129.3) [AS 6407] 108 msec
4 www.primus.ca (216.254.141.10) [AS 6407] 104 msec
</pre>Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-10128187.post-65627682369011449202010-07-29T14:00:00.000+02:002010-07-29T14:00:33.996+02:00This Blog now speaks IPv6Google just posted an announcement on <a href="http://googleappengine.blogspot.com/2010/07/app-engine-and-ipv6-round-2.html">Google App Engine Blog: App Engine and IPv6, Round 2</a>. This announces that <tt>ghs.google.com</tt> now has an IPv6 address, although, as with many other Google hostnames, the IPv6 address is only visible if your organisation or ISP has been "<a href="http://www.google.com/intl/en/ipv6/">whitelisted" for IPv6/AAAA records in Google's DNS</a>.<br /><br />In addition, Google have added an alternate name, <tt>ghs46.google.com</tt>, that announces both traditional IP (IPv4) and IPv6 addresses even for non-whitelisted users. This allows users of Google Apps to "opt-in" to IPv6. One example where you can do this is if you have your blog hosted on Blogger, but use your own domain name - like this blog. I have already changed <tt>blog.simon.leinen.ch</tt> to point to <tt>ghs46</tt>, so if you have IPv6 connectivity, you might already have loaded this blog post over IPv6.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-47420562040076134482010-05-24T13:16:00.002+02:002010-05-24T14:34:20.173+02:00GCJ 2010: Load Testing in Common Lisp (wrong)I thought a little about this problem, and then had the idea that the optimal strategy would be to do a binary search between L and P in log-C space. So the required number of tries would be<br />
<br />
<pre>(defun min-tests (l p c)
(max 0 (ceiling (log (- (log p c) (log l c)) 2))))
</pre><br />
This gave the correct results for the tiny input set on the problem description page, but unfortunately failed on even the small competition set. At this point I gave up and passed on to <a href="http://blog.simon.leinen.ch/2010/05/gcj-2010-making-chess-boards-in-common.html">C (Making Chess Boards)</a>, which was more fun anyway.<br />
<br />
Later I noticed that <a href="http://www.go-hero.net/jam/10/name/s10wh34d">someone else</a> solved the small set in Lisp in an identical way, except they computed the log-C distance differenty:<br />
<br />
<pre>(defun min-tests (l p c)
(max 0 (ceiling (log (log )/ p l) c) 2))))
</pre><br />
With this modification, my code successfully solved the small practice set! Just shows that floating-point arithmetic should never be trusted.<br />
<br />
Unfortunately this fails on the large input set, probably because the approach is too simplistic.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-33958613382737621402010-05-23T19:18:00.000+02:002010-05-23T19:18:31.474+02:00GCJ 2010: Making Chess Boards in Common Lisp (Online Round 1C)I was on the right track with this one, but made a logical mistake and wasn't able to fix it before time ran out. I fixed my code in the half hour after the deadline, and it was able to solve the small input set. After about another hour, I had improved the logic so that it solved the large input set quickly enough. The code that I have now is easily fast enough for solving this puzzle (4 seconds for the large set), although it is not optimal.<br />
<br />
The general approach is as follows: We compute a "scores" matrix from the bottom right up towards the top left. Each entry in the score matrix contains the size of the maximum proper chess board starting at the corresponding spot in the board matrix, towards the bottom right.<br />
<br />
We keep another matrix that contains, for each position, the maximum score towards the bottom or right.<br />
<br />
Then it's easy to find the largest boards that we can cut out, in the proper order. As we cut out squares, we recompute parts of the score and max-score matrices. My code recomputes a little than is actually necessary - that's a possible area of improvement.<br />
<br />
<pre>(defun solve-case (caseno in)
(let* ((m (read in)) (n (read in)))
(let ((board (make-array (list m n)))
(score (make-array (list m n)))
(maxscore (make-array (list m n)))
(cuts '())
(cut 0))
(dotimes (i m)
(let ((line (read-line in)))
(dotimes (j-hi (floor n 4))
(let ((digit (parse-integer line :start j-hi :end (1+ j-hi) :radix 16)))
(dotimes (j-lo 4)
(let ((j (+ (* j-hi 4) j-lo)))
(setf (aref board i j)
(if (logbitp (- 3 j-lo) digit) 1 0))))))))
(update-scores board score maxscore m n 0 0 m n)
(let (last-width (last-i 0) (last-j 0))
(loop
(let ((width (aref maxscore 0 0)))
(when (zerop width)
(return))
(when (eql width 1)
(push (cons width (- (* m n) cut)) cuts)
(return))
(multiple-value-bind (imax jmax)
(if (eql last-width width)
(find-first-from board score m n last-i last-j width)
(find-first-from board score m n 0 0 width))
(assert imax)
(setq last-i imax last-j jmax last-width width)
(cut-out board m n imax jmax width)
(incf cut (* width width))
(let ((old (assoc width cuts)))
(if old
(incf (cdr old))
(push (cons width 1) cuts)))
(update-scores board score maxscore m n imax jmax (+ imax width) (+ jmax width))))))
(format t "Case #~D: ~D~%" (1+ caseno) (length cuts))
(dolist (sizes (reverse cuts))
(format t "~D ~D~%" (car sizes) (cdr sizes))))))
(defun find-first-from (board score m n i0 j0 width)
(declare (ignore board))
(do ((i i0 (1+ i)))
((>= i m))
(do ((j (if (= i i0) j0 0) (1+ j)))
((>= j n))
(when (= (aref score i j) width)
(return-from find-first-from (values i j))))))
(defun cut-out (board m n i j width)
(declare (ignore m n))
(let ((start (aref board i j)))
(dotimes (ioff width)
(dotimes (joff width)
(let ((old (aref board (+ i ioff) (+ j joff))))
(assert (not (eql old '-)))
(assert (evenp (+ start old ioff joff))))
(setf (aref board (+ i ioff) (+ j joff)) '-)))))
(defun update-scores (board score maxscore m n imin jmin imax jmax)
(declare (type (simple-array t (* *)) board score maxscore))
(declare (optimize (speed 3) (safety 0) (debug 0)))
(let (dirty)
(do ((i (1- imax) (1- i)))
((or (< i 0)
(and (< i imin) (not dirty))))
(setq dirty nil)
(do ((j (1- jmax) (1- j)))
((< j 0))
(let ((oldscore (aref score i j))
(newscore
(cond ((eq (aref board i j) '-) 0)
((or (= i (1- m)) (= j (1- n))) 1)
(t (if (eql (aref board i j) (aref board (1+ i) (1+ j)))
(let ((here (aref board i j)))
(if (and (eql here (aref board (1+ i) (1+ j)))
(eql (- 1 here)
(aref board i (1+ j)))
(eql (- 1 here)
(aref board (1+ i) j)))
(1+ (min (aref score (1+ i) (1+ j))
(aref score i (1+ j))
(aref score (1+ i) j)))
1))
1)))))
(unless (eql oldscore newscore)
(setf (aref score i j) newscore)
(setq dirty t)))
(let* ((oldmax (aref maxscore i j))
(newmax (aref score i j)))
(when (and (< (1+ i) m) (> (aref maxscore (1+ i) j) newmax))
(setq newmax (aref maxscore (1+ i) j)))
(when (and (< (1+ j) n) (> (aref maxscore i (1+ j)) newmax))
(setq newmax (aref maxscore i (1+ j))))
(unless (eql oldmax newmax)
(setf (aref maxscore i j) newmax)
(setq dirty t)))))))
</pre>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-10128187.post-83359834807234457222010-05-23T18:59:00.002+02:002010-05-23T19:05:42.385+02:00GCJ 2010: Rope Intranet in Common Lisp (Online Round 1C)I failed at online round 1 this year, although I tried twice in sub-rounds 1B and 1C. The first puzzle in sub-round 1C, <a href="http://code.google.com/codejam/contest/dashboard?c=619102#s=p0">Rope Intranet</a> was easy, and I handed in the correct solutions for both the small and the large input in less than ten minutes. Here is the straightforward code:<br />
<br />
<pre>(defun solve (file)
(with-open-file (in file)
(let ((ncases (read in)))
(dotimes (caseno ncases)
(solve-case caseno in)))))
(defun solve-case (caseno in)
(let ((n (read in)))
(let ((wires (make-array (list n))))
(dotimes (i n)
(setf (aref wires i)
(cons (read in) (read in))))
(let ((sol (intersections wires)))
(format t "Case #~D: ~D~%" (1+ caseno) sol)))))
(defun intersections (wires)
(let ((result 0))
(do ((i 0 (1+ i)))
((>= i (length wires))
result)
(do ((j (1+ i) (1+ j)))
((>= j (length wires)))
(when (intersectsp (aref wires i) (aref wires j))
(incf result))))))
(defun intersectsp (w1 w2)
(if (< (car w1) (car w2))
(> (cdr w1) (cdr w2))
(< (cdr w1) (cdr w2))))
</pre>Unknownnoreply@blogger.com0Segantinistrasse 36, 8049 Zurich, Switzerland47.405098 8.500947147.4014675 8.4936516 47.4087285 8.5082425999999991