Moserei

Suppose you want an element from a list that is minimal in a certain respect. The code you usually see for this is:

import collections
Item = collections.namedtuple("Item", "id cost")
items = [Item(1, 10.00), Item(2, 200), Item(3, 1.0)]

sorted(items, key=lambda item: item.cost)[0]
# Item(id=3, cost=1.0) 

Here is a nicer way to do this using the standard library:

min(items, key=lambda item: item.cost)
# Item(id=3, cost=1.0) 
# or even
import operator as op
min(items, key=op.attrgetter("cost"))
# Item(id=3, cost=1.0) 

This is not only more elegant, but also more efficient because sorting a list is more time consuming than finding the minimal element. When dealing with generators this method uses a lot less memory.

tl;dr: Puzzle had to be solved. Did it in Haskell. Had fun. Code is here :-)

Last week one of my colleagues, Marco, brought a so-called Minotauros cube to work and left it on the counter near the coffee machine. You might call it an obvious attack on the productivity of the whole company.

At least for me it is hard to tolerate to be unable to solve a puzzle. Unfortunately, it is a quite tricky one. Here is a picture; there is only one way of putting the parts back into a cubic shape.

While I am sure that there are solutions and algorithms to solve this kind of puzzle, I wanted to think of something myself. Thus, I abstained from searching and started to think about a way to solve it. I immediately decided to build the solution in Haskell. I have done quite a bit of programming in Haskell in my first year of university but not much recently. But at Polyconf 2015 I got some inspiration to do more functional programming again (I am playing with elm (talk at Polyconf) at the moment, more on that in another post).

It took me some time and fruitless tries experiments until I had a good idea how to structure the solution of the problem. I decided to use a backtracking algorithm which tries to find dead ends as quickly as possible.

01: function solve (shapes, solution)
02:   shape, rest = head, tail of shapes 
03:   for shape' in all rotations of shape
04:     for shape'' in all possible positions of shape'
05:       solution' := solution ++ shape''
06:       if solution' is valid
07:         solution'' := solve (res, solution')
08:         if solution'' is valid
09:           return solution''
10:   return invalid solution

11: solve(all shapes, empty solution)

During the implementation I decided to change the algorithm slightly: It now starts out with a full solution (a shape in which all the coordinates are “occupied”) and consequently “subtracts” instead of “adds” in line 05.

Another problem was the data structure to represent shapes. My first try featured the following type using Data.Array:

import Data.Array
type Shape = Array (Int, Int, Int) Int

It is a quite obvious choice for somebody who lives most of the day in the imperative world, but I also noticed quite quickly that the Array type is a little cumbersome to work with.

I then reconsidered what a truly functional way of representing spatial data would be. I came up with the following:

data Shape = None
           | Point Shape Shape Shape Shape Shape Shape
           --      North South West  East  Above Below

I planned to use this as a three-dimensional doubly linked list. I thought it might be nice to traverse this using pattern matching. While Haskell’s laziness enables us to do so I quickly noticed that using this kind of structure is too much for my mind.

I finally resorted to something easier:

import qualified Data.Set as Set
type Point = (Int, Int, Int)
type Shape = Set.Set Point

As soon as I had made up my mind about the data structure it took me a couple of evenings to create all the necessary functions. The full implementation can be found in this gist.

This experiment and also my recent experience with elm has motivated me to do more strongly typed functional programming again. The power of those compilers is sometimes just incredible. ;-)

Just a quick one:

xargs can help you to start multiple processes simultaneously:

$ time echo $'1\n2' | xargs -n 1 sleep                       

real    0m3.007s
user    0m0.001s
sys     0m0.007s
$ time echo $'1\n2' | xargs -P 2 -n 1 sleep                  

real    0m2.007s
user    0m0.001s
sys     0m0.006s

With -P N or --max-procs=N xargs will start up to N processes at the same time.

Because I did not find a good example (at least not on the first result page :D) for the performance difference between boxed and unboxed types in Haskell, I created one.

--boxed.hs
foo :: Int -> Int
foo 0 = 0
foo n = foo (n - 1)

main = print (foo 500000000)

--unboxed.hs
import GHC.Exts
foo :: Int# -> Int#
foo 0# = 0#
foo n = foo (n -# 1#)

main = print (I# (foo 500000000#))

And here is the quite impressive result:

$ ghc boxed.hs
$ ghc -XMagicHash unboxed.hs
$ time ./boxed
0
./boxed  16,34s user 0,03s system 99% cpu 16,397 total
$ time ./unboxed
0
./unboxed  0,85s user 0,00s system 99% cpu 0,865 total

I use wicked pdf for PDF generation in my rails app foxtrot mike. Wicked pdf has a helper method which copies the content of CSS files into the generated HTML. This does not work in Rails 3.1 because CSS files are generated by Sprockets. Fortunately it is possible to access the compiled asset files. When the asset pipeline is enabled, the application object has an attribute assets which returns a Sprockets::Environment.

The following code includes the contents of application.css in my layout which is used for PDF generation.

  %style{ :type => "text/css" }
    = Rails.application.assets['application.css'].to_s.html_safe

Update: As mentioned in the comments, qpdfview solves the problem.

While I wrote my bachelors thesis a couple of months ago, I really got angry about Evince and the lack of a tab-enabled PDF viewer in Gnome. While I was (trying to) learn for a university course today, this anger returned. The lecturer felt like it was a good idea to arrange the content in more than 15 PDF files.

I ceased the attempt to learn and again started a search for a tabbed document viewer for Gnome. Several users requested a tab feature in evince on Ubuntu brainstorm and received - in my opinion - annoyingly arrogant answers. The technical aspects are not an argument, look at Gedit. The design-user-experience-blah reasons for not implementing this feature may be justified, but one could still implement it as an option and let the user decide. But whatever…

I did not exactly find a tabbed document viewer. But I found an acceptable workaround:

It is based on whatever browser you like (as long as it is supported by mozplugger, Chromium in my case) and embedding evince there. On Ubuntu mozplugger can be installed like so:

sudo aptitude install mozplugger

After you installed mozplugger and restarted your browser it should show up as a plugin. You can then follow the instructions in the blog post linked to above.

Because Evince has no option to hide the toolbar persistently, I removed it completely. To do this, edit ~/.gnome2/evince/evince_toolbar.xml to look like this:

<?xml version="1.0"?>
<toolbars version="1.0">
</toolbars>

I have furthermore configured Gnome to open PDFs in Chromium.