March 5th — The Bannock Edition

This week, in a very special Learning Tuesday, I take a break from math and code and take on bannock. I think what got it into my head was the Festival du Voyageur that's held every year in Winnipeg. I'm a big fan of plain scones and bannock (Jessica likes to comment on my taste for "bland" things...) and thought I'd try my hand at them.

Most of the recipes online are pretty similar; I used this one.

However, my bannock making took a detour when I realized we were out of butter. On the bright side — we did have whipping cream and a butter churn so I decided to have a go and making my own butter. For future reference: making butter with a churn is in absolutely no way the lazier alternative to going to the grocery store. It took about thirty minutes of turning the crank and the occasional shake of the churn but eventually I did get butter. I pretty much felt like a wizard once the cream actually turned into butter! Next time I feel like whipping up a batch of bannock, however, I might just run to Safeway for my dairy needs...

My arm workout complete, I moved onto Phase Two: actually making bannock. If you've read the recipe, you'll see it's pretty dead simple. To go for a camping feel (making bannock over a fire is a camping staple) I used a cast iron skillet. I don't actually cook with cast iron very often, I'm always a little nervous that I'm going to burn everything. To save time, I baked another three pieces. Now the recipe said to cook it as one large piece but if I had the thing would have been **GIGANTIC**. Most of a baking sheet. The biscuits also rise quite a bit so I'd definitely make future batches thinner than the 3/4" to 1" they suggest. Half an inch, at most.

They turned alright! The darker one is the one that was pan-fried (I ate one biscuit while cooking). I've never made bread before, outside of using a bread machine, but bannock wasn't any more difficult than pancakes. Probably easier even since the batter is less finicky. (In none of the recipes I looked at did I come across the bannock analogue to "Make sure you mix thoroughly but leave some lumps") Good to know that when I feel like some scones, bannock is available as an easier, yummy substitute. (I haven't tried any of the baked ones yet so I don't know if there's a big different between and the fried ones)

February 28th 2013 — Overtime!

This past week has been more C and more Project Euler. In fact, it took me so long to finish the second question that Learnin' Tuesday had to spill into Wednesday :o

The first one that I worked on was problem 102, which was basically a geometry question. You were given a file full of co-ordinates that form triangles on a Cartesian plane and had to determine if the origin -- point (0, 0) -- is inside the triangle.

This one was fun because I was able to scratch my head for a bit and then code a workable solution without having to read up on a bunch of math I barely knew :P My first idea was to draw lines that were radiating out from the origin and if each one crosses one of the triangle's lines, then O is inside. I thought that this would be a little finicky to code, though, figuring out where to draw the lines to, etc.

Instead I came up with this: your original triangle is formed by the points ABC. If make three new triangles (AOB, AOC and COB), the angles of new triangles will add up to the original angles if O is contained by ABC. Like so:

So angle a2 (from AOB) and angle a1 (from AOC). will add up to angle A.

I did have to look up the formula for calculating the angles of a triangle if you know all three sides.

Of course, I hadn't been so focused on the angles, I would have realized that another solution would have been to add the areas of the three sub-triangles and they would total up to the area of ABC.

The first time I ran my program, I got the wrong answer. I scratched my head for a bit. My code looked sound and I thought my logic was, too. I tested my code on a small subset of the triangles Euler provided and it worked. It turned out I was being burned by floating point calculations. I thought I'd taken this into account in my program, but I had to tweak one of my comparisons. Before that, my answer was out by one.

**Hungarian Algorithm**

The other one I did was problem 345 - Matrix Sums. Given a matrix, select elements so that each selection is the only one picked in its row and column and the elements picked have the highest sum possible.

Obviously brute-force could be done, but what would I learn from that? I thought about a greedy algorithm that tries likely values, which would be a little less brute-force but it seemed like there might be a better solution. After some research I realized they had given an abstract version of an assignment problem, which is a type of optimization problem. I'd read *about* this sort of problem, probably in the context of the folklore surrounding George Dantzig. He's the source of the urban legend/inspirational story about the student who shows up late to class, copies down the problems written on the board thinking they're the homework assignment, solves them and later finds out they were two hitherto unsolved questions. (I think when the story makes its rounds Einstein is often the student in question)

In any case, it turns out the Hungarian algorithm was the solution to my problem. The idea is that if you have a bunch of tasks that need doing and a bunch of workers who can do those tasks but have different costs for each task, the Hungarian algorithm (AKA the Kuhn-Munkres or just the Munkres algorithm) will find the minimal cost. To calculate the maximal cost, which is what we want, you can just multiple all the entries in the matrix by -1.

I started by coding in Python based on this description, which is high level and easy to understand, but is very hand-wavy in step three where it says, "no more lines have been drawn than necessary". My first stab at this was to fall-back to brute-force and try different ways figure out the minimum number of lines to cover rows and columns with. This worked for 5x5 test matrices but sucked for the 15x15 problem (I like it run for 10 or 15 minutes before killing my program). I wasn't too surprised since I figured that would be falling back to a non-polynomial solution.

I read more webpages about the algorithm (frustratingly, a lot the pages link back to a site that is no longer available) and found this description, which is a different phrasing of the method and provides an algorithmic way of marking the rows. This time I wrote a C program (I didn't bother looking at any of the code on that page, I just built my code from the verbal description) and after a bit of debugging, got the answer. The program executes instantly, which is nice :) I also am happy with my code, which I implemented as a state machine to go from step to step and makes the program pretty clean.

While I was able to implement the algorithm based on the description, I don't know **why** it comes up with the optimal solution. So linear programming and optimization is something to revisit, maybe, once I've got some graph theory and linear algebra under my belt.

I was thinking of taking a break from Project Euler problems, but after solving 345, I am at 74 questions answered. One more and I level up and get a new badge on the site :D I might have to look for one that appears to be easy pickings...

February 19th 2013 — Long Weekend

Learnin' Tuesday Monday! Due to a scheduling conflict (my local climbing gym was closed yesterday -- our regular climbing night -- for a holiday so tonight is climbing night) I did my studying last night and over the weekend.

Math and C merged together into an ugly mess. First, I finished another chapter in **Applied Mathematics for Database Professionals**. Next up: relations and functions (in terms of set theory). Over the weekend I did a couple of Project Euler problems that I hadn't previously solved. One of them was Problem 54, which just has you determine the winners of poker hands. Nothing difficult or even really mathematical about it. Just a programming exercise, really. I did it in Python because I didn't want to spend too much time on it. I might use my Python code as a prototype for a C version at some point.

Problem 51 was trickier, especially to come up with a reasonably fast implementation. I spent a lot of time futzing around. The main issue was that I didn't want to sit down and write data structures in C. A hash table/dictionary would have been very handy but instead I wrote a bunch of gross code with a lot of looping over arrays. I see a later exercise in Learn C The Hard Way has you implement a hashmap so I may work that exercise and then redo #51. I spent a few hours on Monday hacking away with a few different approaches. I'm not too happy with how my code turned out.

**** Project Euler Spoiler Warning ****

My solution was somewhat brute force. A lot of people in the forums (after you complete a question in Project Euler you unlock a forum for it where you can discuss your answers) said that if you are searching for dix digit primes, the replacement pattern must be 3 digits. If you replace 2 or 4 digits, at least one of the generated numbers will be divisible by 3 and hence not a prime number. I can't figure out the reasoning behind this. I'm sure there's some property of integers that I don't know. But it sure reduces the size of the set of numbers you need to test.

**** End o' Spoilers ****

The next Euler program I'm going to do, I think, is #102, a geometry problem. Or ostensibly a geometry problem. I haven't looked at it too closely yet. I think I shall also work on less math-y programming problems from some of my old university textbooks.

February 14th — Interlude: Project Euler

Project Euler is a popular site among coders who are trying to pick up a new programming langauge (or who think math is neat). They give you a math problem and you write a solution in your language of choice and submit your answer for glory! There are often brute force ways to solve a problem but ideally you'll figure out a more clever way to do things. I did a number of them a while back. The difficulty escalates quickly, for me at least. One favourite of mine was a question that had you write a Sudoku Solver

I did a number My intention, once I begin poking at Haskell, is to go back over them. I might do some of the non-trivial ones in C as well.

Today at lunch I logged in to take a look at the problems.

***SPOILERS***

Mind you, the first problem is so trivial it's hard to imagine someone being upset by spoilers :P

It asks you to find the sum of all the numbers of 3 or 5 that are below 1000. The brute force way would be to write a loop that runs from 3 to 999 (they specify **below **1000!) and check to see if the number if divisible by 3 or 5 and keep a running sum. One wrinkle is that you don't want to count numbers that divisible by 3 **and **5 twice. You might do something like this in C:

```
int j;
int sum = 0;
for (j = 3; j < 1000; j++) {
if (j % 3 == 0)
sum += j;
if (j % 5 == 0 && j % 3 != 0)
sum += j;
}
printf("Answer: %d", sum);
```

The first time I did this I probably did the native version, but I can't rememeber. This time, however, I decided to give it a think. The numbers divisible by 3 are: 3, 6, 9, 12, 15, ... and the numbers divisble by 5 and 5, 10, 15, 20, ... but those are finite arithmetic progressions and there's a formula for that! This is pretty simple math, the breakthrough for me was remembering the name of what I wanted to google for and that a formula for the sum existed :P

Cue the helpful wikipedia article! The formula is: Sn = n / 2 (a1 + an). Where a1 is first number in the sequence and an is the last. For the numbers divisble by 3, the largest number below 1000 that meets that criteria is 999 (the 333rd in the sequence). Likewise for 5, the largest number is the 199th (995). So all we have to do is calculate those sums using the formula: 166833 for numbers divisible by 3 and 99500 for numbers divisible by 5. Of course, we need to remove the duplciates, but that's just the same sequence based on 15. So we sum the numbrs below 1000 that are divisible by 15. In this case, the largest number is 990 and it's the 66th in the sequence, which somes to 33165.

166833 + 99500 + 33165 = 233168 :D

I was able to do this one without writing a program!

February 12th 2013 — Time for some C

Most of my development at work is in high level programming langauges (high level means more abstract, less concerned with the minutiae of how computers work) -- primarily C# and SQL with a bit of Python here and here. The occasional bit of Objective-C. However, there's a case to be made for knowing C, a language that's closer to hardware so to speak. But understanding what's going on at a low level and being able to reason about it is a useful skill (or perhaps frame of mind). Also, tons and tons of open source software is written in C.

So last night I began working through Zed Shaw's Learn C The Hard Way, a tutorial for people who've learned another language, but doesn't have much experience with low level stuff, text editors and the unix shell. This meant I was pretty familiar with the material of the first seven exercises, although getting introduced to Valgrind, a tool for detecting errors in your C code, was new and I bet will be useful.

I'll continue on through Zed's tutorial, and likely the K&R C book.

I have an interesting self-education project that could be done in C and I'd love to know C well enough to hack on nethack or some other roguelike.

There are so, so many topics in software I want to study. Books I have to work through include the Structure & Interpretation of Computer Programs (one of the classics of our field), Learn You A Haskell For Great Good (Haskell is a programming language I'm pretty sure I'm too stupid to actually learn) and perhaps even eventually The Art of Computer Programming (another classic, one of the books we programmers claim to have read, but probably haven't...)

I want to beef up my web development skills. I do a lot of it at work, but nothing terribly deep. I think Natural Language Processing sounds fun.

So. Much. To. Learn.

I am hoping to scrounge some time to work through more of LCTHW this weekend.

Future Learnin' Tuesdays I have in mind include practicing my French and, in the spring, bike maintenance.

February 5th 2013 — The First Learnin' Tuesday

There are literally a zillion things I want want to learn about but I'm also super good about procrastinating.

The other day I decided that I needed to set aside some time to actually pursue some of these things so I declared **Learnin' Tuesday**! Tuesdays because that seems to be the night of the week where I usually don't have anything going on. I'll try to spend more than just one evening, but Tuesday will hopefully be a minimum.

The first week I started reviewing my basic logic and set theory using Applied Mathematics For Database Professionals. My math skills have really deteriorated since university and I thought this would be a good way to approach math since I'm at least partially a database guy. In parallel, I've been reviewing the relevant chapters of my univesity discrete math textbook and have also begun working through An Introduction To Mathematical Reasoning.

My very talented friend Yuy drew a comic to commemorate the first Learnin' Tuesday:

In terms of math topics, I'm going to continue working through Math for Database Pros and Mathematical Reasoning. Some other topics I'd like to look into are graph theory, stats and probability, all of which are somewhere germaine to software development.