A CP Solution for XKCD NP Complete Restaurant Order

I’ve been messing around with Constraint Programming (CP) the past week. A few people at work have tried it out on some real world problems lately but it didn’t seem to stand up when given a lot of data and variables. This seemed sad as the declarative nature of CP attracts me and it strikes me there must be a set problems that it could be used for and it deserved a look.

The first CP model I wrote by myself is stupidly simple but since my non techie fiance understood the code I figure it is a good example. The problem is as described by XKCD below, select some appetizers from the menu so that the total cost adds up to $15.05.

NP Complete

I modeled the problem in Minizinc, a declarative language for modeling CP problems. I am just learning so if you know Minizinc and I’ve done something dumb don’t judge me too harshly.

Firstly we declare a bunch of variables that the solver needs to find values for. We provide the solver a domain in which the variables must lie, zero to ten for all variables in this case. Each of these variables represents the number of times as part of a solution we buy an item to add up to $15.05.

var 0..10: fruit;
var 0..10: fries;
var 0..10: salad;
var 0..10: wings;
var 0..10: sticks;
var 0..10: sampler;

Then we declare a constraint, something that the solver must meet to solve the problem. And in this case we say that a sum of the cost of the items (converted to cents) multiplied by the number of items in the solution must equal the required 1505 cents (that English version could be taken a couple of ways, the maths below makes better sense).

constraint fruit*215 + fries*275 + salad*335 + wings*355 + sticks*420 + sampler*580 == 1505;

We tell the solver to solve to satisfy.

solve satisfy;

And provide a format in which to output the solution.

output ["fruit=", show(fruit), "\t fries=", show(fries), 
        "\t salad=", show(salad), "\t wings=", show(wings),
        "\t sticks=", show(sticks), "\t sampler=", show(sampler)];

Running the model gives us:

$ minizinc --all-solutions xkcd.mzn
fruit=7     fries=0     salad=0     wings=0     sticks=0     sampler=0
----------
fruit=1     fries=0     salad=0     wings=2     sticks=0     sampler=1
----------
==========

So there we go, all the possible solutions to the poor waiters problem! We know it is all of the solutions because of the “==========” minizinc cryptically places at the end of its output. Of course this problem is easy to brute force with a couple of for loops, there aren’t that many combinations.

But it is a start along what I hope will be a fruitful path.

Update: as people have noted on HN and Reddit I originally screwed up transcribing the price for salad which produced a couple of extra solutions. Fixed that now.

WTForms and Cherrypy 3.1

I have been trialling WTForms, a HTML form input and validation library for Python with a project I am working on. Much to my irritation however WTForms and Cherrypy don’t play nicely in one small area. Using wtforms.FileField with the validator wtforms.validators.Required will always fail.

Cherrypy in 3.1 (but not 3.2 interestingly) uses the Python built in cgi.FieldStorage to handle file uploads. In Python 2.6 and 2.7 at least this is beause the code for cgi.FieldStorage.__nonzero__ [1] only checks self.list and ignores self.file which is where the data is (at least for Cherrypy 3.1). No idea why this is the case, google gives no love on the why of this issue.

There has been an issue raised with the WTForms guys about the same case with Pylons but the long and the short of it is the developers don’t want to add special cases for the various frameworks. Special cases are the bane of a coder’s existence, they bloat otherwise lean and understandable code and cause maintenance nightmares so I do understand.

So what about me? Moving to Cherrypy 3.2 is an option but I don’t want to deal with the worry of that migration right now. An easy fix on my end is to write a custom validator and use it in place of the built in one. But what about the next project and the dozens of other people on my team who have to remember to use the custom validator for file upload? I might need to continue looking at form libraries, at least there is a lot of them!

[1] http://hg.python.org/cpython/file/9f8771e09052/Lib/cgi.py line 602

Cardinal Pell

Status

Poor Cardinal Pell you’re right. Your church is unfairly being singled out for criticism and we should take your word that decades of systemic failures by your organisation have been rectified.

Eclipse

EclFinally, after gathering dust on my shelf for a couple of months I played a game of Eclipse. The epic space 4x strategy game is often described as Twilight Imperium (TI) light, which lets face it isn’t fair as almost anything is lighter than TI’s 8+ hour epic sessions.

It is hard to judge based on a single 2 player game but it seems like Eclipse fullfills the epic space strategy need in me without the pain associated with TI. Each person’s turn is quicker, the choices you make are simpler but contain a similar strategic depth.

And it plays through in 1/2 the time (30 mins per player) once you know what you are doing, the length of a TI game means it is always hard to get a session going.

Looking forward to another game soon with more players.

Chin Chin

Wow, so um wow! A week ago we went to eat at a darling of the Melbourne food scene, Chin Chin. I don’t follow the trends and new hot things in the local scene very closely but had still managed to hear it is a great place, though little else beyond that.

What the place turned out to be was amazing and well deserving of the buzz it has generated. After waiting an hour to get a table* we ordered the “Feed Me” set menu at $66pp where as we discovered they just keep bringing out dishes of wonderful Thai food until you beg for mercy. We definitely got our money’s worth and tried many dishes we probably wouldn’t have picked otherwise but enjoyed heartily.

I cannot recount all the dishes we ate because of this, it is now one big long beautiful blur. However overall the salads were probably the highlight, so wonderfully flavoured many with a well balanced chilli bite. I will certainly be heading back there, probably taking friends from out of town to show off a shining example of what the food scene in Melbourne has to offer.

* They take your mobile number and SMS you when your table is ready.

Github, Rails and Interface Design

All the excitement over the Rails and Github hack reminded me about Scott Meyers (author of Effective C++ et al.) who has talked about the subject of interface design many times (including in the aforementioned book) and his perspective puts the ball squarely in the Rails team’s court.

Let’s make the reasonable assumption that your clients—the people using your interfaces— are trying to do a good job. They’re smart, they’re motivated, they’re conscientious. They’re willing to read some documentation to help them understand the system they’re using. They want things to behave correctly.

That being the case, if they make a mistake when using your interface, it’s your fault. We’re assuming they’re doing their best—they want to succeed. If they fail, it’s because you let them. So, if somebody uses your interface incorrectly, either they’re working hard at it (less likely) or your interface allowed them to do something easy that was not correct (more likely). This puts the shoe on the foot not used to wearing it: it means that responsibility for interface usage errors belongs to the interface designer, not the interface user.

Source: Scott Meyers: The Most Important Design Guideline?

Izakaya Den

Finally visited Izakaya Den this evening after wanting to go for *ages*. I am a bit of a fan of the genre after being introduced to dining izakaya style in Japan and have often heard that the den it is the best one in Melbourne. The four of us enjoyed: Octopus with pickled kohliabi and wakame (best wakame I’ve ever had), Crispy school prawns, Duck liver parfait (probably my favourite for the evening), BBQ Ox Tongue (garnered some amusement and was delicious), Barramundi Fillet (the skin was especially good), Kurobuta Pork Belly, Pepper Stuffed Mince Duck and two plates of Seasame Stir Fried Mushrooms (which were freaking win). For dessert we shared a Black Sesame Brulee, Warm Tofu Cake (unsurprisingly not so great), Japanese Trifle, and an Apple Millefeuille (made of layers of dehydrated apple and a excellent apple sorbet).

For a laugh read Ed’s review of the place, he gets distracted along the way and provides much amusement.

Cheese 1

Status

Cheese from Richmond Hill Cafe & Larder for Rob’s birthday, Roy de Vallees (Sheep and goat’s milk semi hard cheese, Basque Pyrenees, France) savoury, salty a great table cheese. Le Conquerant (traditional camembert, Normandy, France) a fantastic camembert, the girls went nuts for it. Bleu des Basques (semi firm sheep’s milk blue, Basque Pyrenees, France) the stand out cheese from the bunch, rich and earthy and a bit salty.

Eating the Odd Bits

Odd Bits by Jennifer McLaganAs I told Thanh Do of the excellent Melbourne food blog I Eat Therefore I Am the other day, I had a bit of a boring anglo-Australian upbringing largely devoid of the odd bits of animals. The exception to this was beef/ox tongue, which I am ashamed to say was greeted with great disgust by my sister and myself. Our mother eventually hid the source of the meat when she served it lest we refuse to eat it. So I am afraid so say I have only the faintest of recollections as to its taste, let alone how it was prepared. How did you prepare it mum?

Since then I’ve dined on many so called odd bits, though always in restaurants. Chicken’s feet are a regular favourite at yum cha, dim sum for those of you in America. I also love a good lambs fry, though I rarely see it on the menu in Melbourne.

Thus after hearing about Jennifer McLagan’s new book Odd Bits I thought it was high time I start cooking some of these items at home. Nose to tail eating has a couple of attractions for me, it provides my foodie self more ingredients and flavours to enjoy and cook with, and my eating sustainably self a warm fuzzy feeling inside.

So to the book. It is beautifully presented with wonderful photos throughout, each “odd bit” introduced with a couple of paragraphs then sections on purchasing and preparation. Interspersed through the book are quotes by notable people of the food world lauding the tastes, smells and sights offered by the various pieces of animal under discussion. These quotes strike me as a useful aid for tempting the more recalcitrant diners in your home to trying the recipes contained in its pages.

The recipes themselves are excellent, with a low complexity and many of them taking familiar recipes and adding an “odd bits” twist. There is a surprising number of the “odd bits” which are actually familiar items, lamb ribs and necks for example already appear on my shopping list as do shanks and oxtail. I also love that some of the recipes have a delightful tongue in cheek title such as Headcheese for the Unconvinced of which my girlfriend and sister count themselves members of.

I will blog about it as soon as I cook some of the recipes, probably something in the liver or tongue sections given I’m somewhat familiar with those ingredients and flavours!

Update: I do remember our mother also did liver at one stage which was met with similar incredulity and ox tail braised in tomato sauce which went down pretty well from memory.

Lake Tali Karng: Fun and games in the hills

Last weekend we hiked through the Alpine National Park to Lake Tali Karng with our friends Cath & Rob, it was beautiful and turned into a slight misadventure. Rob is a dedicated hiker and Cath is fairly experience as well, whereas Li and I are pretty inexperienced, I haven’t hiked since high school & the scouts.

So we this in mind we planned an easy two day hike, downhill all the way in an area Rob had visited last November. We left a car at the bottom of the walk at the end of the sealed road on the Wellington River and drove to the high plains and left a car at MacFarlanes Saddle. It was bright and sunny Saturday lunchtime when we started hiking across the plains heading towards the lake. We chatted and took in the beautiful grasslands around us then stopped a couple of hours in for a break and some late lunch.

Another hour of walking got us to Gillios Track a steep rocky descent from 1300 metres to the lake at around 900 metres. This descent was hard work, loose rocks and tight chicanes with a pack on ones back isn’t easy, especially when you aren’t use to it. I had a touch of trouble at this point, my left ankle is weak having being twisted badly several times in the past. So this descent was made harder by trying to avoid a twist, which I did with a few very minor exceptions.

Great relief was felt all round when we reached the lake, all sweaty with our legs shaking from the descent. Our reward for all that hard work, Lake Tali Karng, sparkled in the late afternoon sun a beautiful blue green. We trekked around the lake till we reach the western edge and setup camp in the vicinity of a group of men boisterously swimming in the lake. Slightly disappointed not to be alone with the lake we made the best of things and greeted them warmly, which was returned in kind.

They turned out to be a group of Serbians, all originally refugees from the war in the 1990s. After we swam, we setup camp and Rob cooked our dinner on the tiny camp stove. The Serbians lit a fire and started laying out a vast array of food. We were a little uncomfortable about the fire as it was explicitly disallowed due to the damage wood collection does to the surrounding bushland.

However since it was a minor infraction we didn’t make an issue of it and they invited to join us in consuming not only the vast array of food they had but a considerable amount of homemade plum brandy as well. We gladly obliged and chatted with them into the night, staying up far later (and far drunker) than we would have on our own. In all likelihood it contributed to the events that followed the next day.

In the morning we slept relatively late for a camping trip, enjoying the extended twilight being surrounded by mountains provides. I cooked breakfast (a mediocre rice pudding) while the camp was disassembled. We then walked around the lake to visit the falls at the eastern end of the lake. The falls were beautiful and the water tasted wonderful and we filled our bottles, replacing the suspect lake water which we had been consuming. We then returned to the camp site and set off for the car at around 12pm.

Lake Tali Karng was created by a big land slide across a valley around 1500 years ago and as we left the lake we hiked down this rock fall. The area we were journeying through is aptly called the Valley of Destruction and it was almost as difficult a descent as down Gillios Track was the day before. It was quite slow going and my ankle continued to threaten a severe twist a worrying problem given the 18km and 14 river crossing ahead of us. I used a Gandalf-esk stick to assist and avoided severe injury for the two or so hours it took us to get through the valley.

A few hours into the hike we reached what looked like a fork, one a 4×4 track heading up a hill and another trail marked by ribbons. We followed the ribbons for 10-15 minutes before becoming suspicious that the ribbons weren’t for us but for one of the many running groups or schools that use the area. We turned around to return to the fork and I read some writing on one of the ribbons as we passed. “Remove 15/4/2012 GGS” could be read and I passed on the remove and date to my companions, annoyingly as you will see leaving out the GGS part.

Once we reached the fork we broke for a rest while Rob went down the 4×4 track to see if this was the trail we needed to follow. We swatted march flies (YUCK) while chatting, expecting Rob to return shortly. He returned 30 minutes later to the pronouncement that he was 95% sure that what we had thought was a 4×4 track was infact the trail. We followed with some small trepidation, not wanting after all to be lost in the wilderness.

This is where the hike became a bit less fun, the not knowing for sure where we were didn’t do great things for our moral and the trail was a lot of PUDS (Pointless Up and Downs[1]) which was a bit tiresome. Another hour in, 4 hours into the hike in total, we reached another fork. This one was marked with a sign and was either the 4×4 track we thought we had ecountered earlier or one further along. It brought on more worry as if it was the first 4×4 track we were only 1/3 our way through the hike and had burnt 4 hours of what was suppose to be a six hour hike. At some stage during this part I mentioned the GGS on the ribbon, which Rob said likely stood for Geelong Grammar School.

Shortly afterwards another set of signs confirmed our fears. We still had 12kms and 14 river crossings left to do and only 4 hours of good light to do it in, being about 4pm by this stage. We stood around looking worried and Rob explained our options. We might make it if we hiked faster, and if we didn’t make it with the light we might chance the last section with headlamps. Or we could go as far as we could and camp. Rob would then go ahead alone to the cars and phone coverage so he could let our families know we were fine.

We decided either way we needed to move faster, to which Li responded that she couldn’t possibly do any more than she was already doing. A pack shuffle was initiated, with Rob taking Cath’s small pack as well as his own and Cath taking Li’s. We then set off at a faster pace, hoping to beat loss of the sun.

This section was a blur, we ate lightly and only stopped to remove our shoes for river crossings. The crossings themselves were a mixed blessing, the water was reviving while the rocks underfoot were slippery and painful on our sore feet. I focused on the person’s feet in front of me, part of me despairing while another part of me thinking of the tale I would tell once we returned. This XKCD comic did cross my mind at the time: http://xkcd.com/77/.

From what I saw and still remember the Wellington River was beautiful, each point we crossed worthy of it’s own day of camping and exploring. We saw several frogs, walked past many good swimming holes and missed examining many sights including a few amazing rock formations.

At 8pm as the light faded, we reached the last crossing and the car. After some tired rejoicing Rob and I left the girls to bathe while we collected the other car from the top of the mountian. It took us over an hour and a half to return to the girls, being that we were tired and driving on mountain dirt roads at night. As we drove up the mountain I turned my phone on and recieved a flurry of messages from my worried sister.

I messaged her that we were alive and safe but not to expect us for several hours yet. To this she responed with great relief and informed me we had been reported missing not 5 minutes previously. Amusment and apologies followed, and a few other family memebers sent messages of love.

Once we returned to the girls, who were a touch worried sitting in the dark by the river, we set off for home. We stopped off in Traralgon at midnight for dinner and consumed too much McDonalds, something I am not proud of but it was good at the time and the only food available. We then set off down the freeway for home, stopping at around 2am for a hours sleep for safety’s sake.

Li and I made it home by 4am and stumbled into bed after being thoroughly inspected by the cat, presumably we smelt very interesting after all our adventures. Once the sun rose we let our respective employers know some of what had transpired and returned to bed for some much needed sleep.

[1] A new term for Li and I which was explained to us on the hike when Li pronounced her frustration at the PUDS.