Addresses in databases

Whenever I see something like this:

• Address Line 1:
• Address Line 2:
• Address Line 3:
• City:
• Country:
• Post Code:

I want to find the database designer and smack them.

What is it about addresses that make people think that they don't need normalising?

No! Of course! The solution to storing addresses is to create a table and force all addresses to fit into five lines plus a postal code. Brilliant. Really smart.

There is one mandatory field in the address: country. That's the only one. Everyone lives in a country. I don't want to get into stupid arguments like "Wales isn't a country it's a principality", etc., when you put it in an address it's a country.

You know something people know? How many lines there are in their address. So don't force them to have 3, 4, 5, xty mumble-jillion, or however many you think is sufficient.

This is what I want to see from now on:

Address

If you do the post / zip / whatever code search thing, then great, but be sure to store the address lines in a sensible manner.

address_id	line_id	text
1	1	My House Name
1	2	My Street Name
1	3	My City Name
1	4	My Post Code
1	5	My Country

Re: quick idea

It's not trivial. There is no easy way to convert a file like jpg/png/gif into icon format. Arbitraried!

No coding Sundays

I've decided that I'm going to not code on Sundays.

I'll try and cut out Stack Overflow too, except for next Sunday because that is my 99th consecutive day. I NEED MY BADGE.

Sundays will be given over to something else. Anything else.

It's not that I've stopped loving coding. I think I love it too much. I'm going to see what else there is.

Quick idea

I think it should be trivial to make an png/jpeg/gif/bmp -> icon creator

I'm going to work to one.

Solving Sudoku

I was chatting with my manager the other day, just shooting the breeze, and we got on to how he knocked together a python script to prove to his girlfriend that programmatically solving sudoku puzzles is easy.

I disagreed for a moment and then realised I was thinking of generating sudoku puzzles, which we agreed isn't easy.

I had tried to make a sudoku helper app before, to practice MVVM and WPF, but had messed up in some calculation or other. Probably at the point where I was calculating which block a square was in. Anyway I had deleted that one, but my boss had spurred my interest in doing it again.

I'm a better programmer than I was that first time - I understand both WPF and MVVM better now, so this little solver is pretty sweet. (Unless you look at the code.)

It has all the features I need. I can fill in the known numbers, delete mistakes, and click a button to solve the unknowns (once the knowns are in place).
Sometimes you don't even need the button, since the programme eliminates possibilities as you type. One puzzle I tried was solved before I typed in all the known numbers!

So my amazing solver has two simple algorithms doing the solving:

1. Each square has an event that fires when its number of possible values reaches 1, either programmatically or by user intervention. This event is subscribed to by all the squares related to it (row, column, block), and so each related square will remove this value from their possible values list. This can cause a chain reaction of updates, solving the sudoku puzzle when enough knowns are typed in.
2. If elimination alone doesn't do the job then the second algorithm is just a button click away. I might have over thought this one:
1. Create a list of squares that have at least 2 possible values, sorted in ascending order of number of possible values
2. Take the first square and find all the squares in the same block
3. Add theses squares to a checked block list
4. Flatten the lists of potential values into one list
5. Find any unique values in that list
6. If there are any unique values then these represent solved squares so break out of the loop and update the squares related to those values.
7. If there isn't a unique value then repeat 3, 4 and 5 for the row, then the column of the current square.
8. If after that there still isn't a unique value, move onto the next square that hasn't been checked yet.

If at the end of the second algorithm a number hasn't been updated then the programme lets the user know that it needs more knowns, otherwise it starts the second algorithm again until all the squares are filled.

I know what you're thinking. You're thinking that if a user makes a mistake inputting a value, then when they delete it and input a new value the possible values list for the related squares will be wrong. Fear not! Deleting a value fires an event that does the opposite of inserting a value, so things go back to the way they were. Phew!

If you want to look at the code it's on github here: http://github.com/Mellen/SudokuSolver

The code is c#. The project is a Visual Studio 10 project, that runs on the .NET 4.0 framework. It even has a couple of unit tests. Yes, I'm that guy. I unit test toy projects.

The executable is available from github: SudokuSolver1.0.2.zip. It requires .NET version 4.0.

Anyway! This was a fun little diversion. I makes me happy that I got it right the second time.

Thinking about learning

So, my lack knowledge needs to take a bit of a beating.

If I'm to get significantly better at writing C#, I need to understand the specification.

It seems like a daunting task, but I think if I try and tackle a point at a time, writing small programmes to demostrate my understanding, I'll get a much deeper understanding of how my programmes hang together and how to write them better.

Wish me luck!

Learning to see patterns in my own behaviour

So, a week and a half ago I was looking at a question on Stack Overflow (Algorithm to calculate the number of combinations to form 100 ). I set about solving it in Haskell, and came up against a block to my success:

Given a list of numbers xs and another number n, generate a list of all the possible combinations lists of length n that contain the numbers from xs.

So, given the list [1,2] and the number 3, the function should generate this list of lists: [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]

I was pretty sure that this had been done before, but because I'm trying to get better at deducing algorithms, I'm stubborn, and I'm doing this for fun I decided to figure out the algorithm for myself.

It wasn't as easy as it seemed.

I sat down and wrote out the outputs for a few different sets of inputs, I looked at them, I looked some more. I could see a couple of patterns, namely that (length of xs)ⁿ is the length of the final output and that you could create a rectangle of answers with width length of xs and height (length of xs - 1)ⁿ. Neither of these were helpful.

I left the problem alone for a while, hoping that time would give me perspective. I was surprised how hard I was finding it to find the pattern.

Today I came back to it with a fresh brain and time to kill. I took a walk to the park, sat down, started to write out the output where the input is a list of length 3, and n as 3. As I was writing, I had the realisation that the way to solve this was to figure out the algorithm of how to write it down. The problem in my previous examples of output was that I hadn't written it in a good enough pattern. I started writing out the output for a different input a list of length 4, with n of 4 (256 items, for those keeping count). This time I was very systematic about how I wrote out the output. I got to the 44th list in the list and stopped to see if I could see it yet. I could: the last element in the individual lists was repeating every 4 items.

I stood up and, as is my wont when I am thinking, I started pacing. I must have looked a little unhinged, as I was pacing in a small circle around my bag.

It took me a few minutes, but eventually I figured out how to represent what I was seeing in my written output as an algorithm: the first time through, each item of xs is appended to an empty list, for each subsequent time through, each item in xs is appended to each list in the list of lists.

In Haskell, I came up with this function to do the work:

makeallsets :: Integral a => [a] -> a -> [[a]] makeallsets xs n = mas (addtoonelist [] xs) xs (n - 1) where mas yss _ 0 = yss mas yss xs (n + 1) = mas (addtoeachlist yss xs) xs n where addtoeachlist [] xs = [] addtoeachlist (ys:yss) xs = (addtoonelist ys xs) ++ (addtoeachlist yss xs) addtoonelist ys [] = [] addtoonelist ys (x:xs) = (x : ys) : (addtoonelist ys xs)

This allowed me to create an answer to the Stack Overflow problem. (Although there's no point posting it for 3 very good reasons: 1. it's not in the target language (which is Scala); 2. It uses the brute force approach; 3. There is already a better answer.)

Score 1 for perseverance!

P.s. if anyone would like to show me a better way, I'd be very glad to hear it.

Update to ToDoList

I have made an update to the ToDoList WPF application I wrote some time ago.

ToDoList version 1.2.0.0

Changes:

• Created a ViewModel for the To Do List object and To Do List items.
• Setup templates in the MainWindow XAML that display the ViewModel.
• Added in an edit window.
• Added in a context menu for items that allows for editing, deletion and marking as done.
• Added in edit and delete functionality.

I think the final addition will be to allow users to view done items. I'll get around to this at some point :D

Memoizing functions in c++

I was thinking about memoization, and how I'd not yet used it. I thought this was a bad thing simply because not using it might lead to me forget about it. So I'm putting together this blog post to help me solidify the concept.

A long while a go I realised a simple fact about square numbers: x² = (x-1)² + (x-1) + x, x ∈ N. I.e. for any positive integer its square is the square of the previous integer plus the previous integer plus itself. (e.g. 17*17 = 16*16 + 16 + 17)

This is something that is unlikely to be interesting or useful, except that I can use it to demonstrate memoization.

From the above formula you can write a recursive function:

int square(int n)
{
    if(1 == n)
    {
        return 1;
    }
    return (square(n - 1) + (n - 1) + n);
}

As you can see this is a very long winded way to get the square of a number, and not a function that would ever be used in reality, but it is a good candidate for memoization.

Memoization in this instance is very easy. Simply add in a static map<int, int> and update it for each number you haven't calculated yet:

int square(int n)
{
 static std::map<int, int> results;
 if(1==n)
 {
  return 1;
 }
 if(0 == results[n])
 {
  results[n] = square(n-1) + n-1 + n;
 }
 return results[n];
}

It might be that you'll want to make the results variable on the heap with some sort of smart pointer, so that it automatically deletes itself, but other than that this second version should give a performance increase over the original.

I carried out some simple timing tests with std:clock(). The programme had to calculate the squares from 1 to 32767 using the memoized and non memoized functions, in a loop:

toggle test code

#include <map>
#include <ostream>
#include <ctime>

int calcSqr(int);
int calcSqrSlow(int);

int main()
{
 clock_t start1 = std::clock();
 for(int i = 1; i <= 32767; ++i)
 {
  calcSqrSlow(i);
 }
 clock_t start2 = std::clock();
 std::cout << "Ticks taken (slow): " << start2 - start1 << std::endl;
 clock_t start3 = std::clock();
 for(int i = 1; i <= 32767; ++i)
 {
  calcSqr(i);
 }
 clock_t start4 = std::clock();
 std::cout << "Ticks taken (memo): " << start4 - start3 << std::endl;
 return 0;
}

int calcSqrSlow(int n)
{
 if(1 == n)
 {
  return 1;
 }
 
 return (calcSqrSlow(n - 1) + (n - 1) + n);
}

int calcSqr(int n)
{
 static std::map<int, int> results;
 
 if(1==n)
 {
  return 1;
 }
 
 if(0 == results[n])
 {
  results[n] = calcSqr(n-1) + n-1 + n;
 }
 
 return results[n];
}

Ticks taken for the normal function: 3120
Ticks taken for the memoized function: 78

Obviously this test was biased towards the memoized function, but I really did it to show the potential benefits of memoizing a function where the results can be reused.

SVG + Javascript drag and zoom

Recently I've been working on a project that uses SVG (Scalable Vector Graphics).

I have been using SVGWeb (http://code.google.com/p/svgweb/) so that the SVG will work in all the major browsers.

It is a fantastic library and I am so grateful to the people who work on it.

The things I found difficult were figuring out how to get zooming with the mouse wheel and dragging to work. I had it working in Firefox, using its native SVG renderer, however SVGWeb does things differently. It took me a while to work out how. I'm going to share what I found here. (Hooking the mouse wheel is actually explained on the SVGWeb mailing list: Mouse Wheel Events.)

With dragging, I knew I needed to store the old X and Y values of the position of the mouse and take the difference between them and the new mouse position. For some reason setting global variables for the old X and Y values didn't quite work - the delta was very small, approximatley 7.5 times too small.

With zooming, the SVGWeb library doesn't pick up the mouse wheel event. The way to get around this is to attach the mouse wheel event to the container tag (e.g. div) that is surrounding the object tag that is holding the SVG on the HTML page.

On to the code!

I did not come up with the Javascript - I took it from various places; mostly the SVGWeb mailing list entry above and the "photos" demo that comes with SVGWeb.

This is the main HTML and Javascript for the page that is holding the SVG:

toggle code

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
        <title>SVG Example</title>
        <meta name="svg.render.forceflash" content="true" />
        <link rel="SHORTCUT ICON" href="favicon.ico" />
    </head>
    <body onload="loaded()">
        <div id="svgContainer">
            <!--[if IE]>
            <object id="svgImage" src="example.svg" classid="image/svg+xml" width="100%" height="768px">
            <![endif]-->
            <!--[if !IE]>-->
            <object id="svgImage" data="example.svg" type="image/svg+xml" width="100%" height="768px">
            <!--<![endif]-->
            </object>
        </div>
        <script type="text/javascript" src="svg/src/svg.js" data-path="svg/src/" ></script>
        <script type="text/javascript">
            function loaded()
            {
                hookEvent("svgContainer", "mousewheel", onMouseWheel);
            }
            function hookEvent(element, eventName, callback)
            {
              if(typeof(element) == "string")
                element = document.getElementById(element);
              if(element == null)
                return;
              if(element.addEventListener)
              {
                if(eventName == 'mousewheel')
                  element.addEventListener('DOMMouseScroll', callback, false); 
                element.addEventListener(eventName, callback, false);
              }
              else if(element.attachEvent)
                element.attachEvent("on" + eventName, callback);
            }
            function cancelEvent(e)
            {
                e = e ? e : window.event;
                if(e.stopPropagation)
                    e.stopPropagation();
                if(e.preventDefault)
                    e.preventDefault();
                e.cancelBubble = true;
                e.cancel = true;
                e.returnValue = false;
                return false;
            }
            function onMouseWheel(e)
            {
                var doc = document.getElementById("svgImage").contentDocument;   
                e = e ? e : window.event;
                doc.defaultView.onMouseWheel(e);
                return cancelEvent(e);
            }
        </script>
    </body>
</html>

This is the SVG and Javascript:

toggle code

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg version="1.0" xmlns="http://www.w3.org/2000/svg" onload="loaded()" id="svgMain" >
    <script type="text/javascript" language="javascript">
    <![CDATA[
        var isDragging = false;
        var mouseCoords = { x: 0, y: 0 };
        var gMain = 0;
        
        function loaded()
        {
            var onloadFunc = doload;

            if (top.svgweb) 
            {
                top.svgweb.addOnLoad(onloadFunc, true, window);
            }
            else 
            {
                onloadFunc();
            }
        }
        
        function doload()
        {
            hookEvent('mover', 'mousedown', onMouseDown);
            hookEvent('mover', 'mouseup', onMouseUp);
            hookEvent('mover', 'mousemove', onMouseMove);
            hookEvent('mover', 'mouseover', onMouseOver);
            gMain = document.getElementById('gMain');
            gMain.vScale = 1.0;
            gMover = document.getElementById('mover');
            gMover.vTranslate = [50,50];
            setupTransform();
        }
        
        function onMouseDown(e)
        {
            isDragging = true;
        }
        
        function onMouseUp(e)
        {
            isDragging = false;
        }
        
        function onMouseOver(e)
        {
            mouseCoords = {x: e.clientX, y: e.clientY};
        }
        
        function onMouseMove(e)
        {
            if(isDragging == true)
            {
                var g = e.currentTarget;
                var pos = g.vTranslate;
                var xd = (e.clientX - mouseCoords.x)/gMain.vScale;
                var yd = (e.clientY - mouseCoords.y)/gMain.vScale;
                g.vTranslate = [ pos[0] + xd, pos[1] + yd ];
                g.setAttribute("transform", "translate(" + g.vTranslate[0] + "," + g.vTranslate[1] + ")");
            }
            
            mouseCoords = {x: e.clientX, y: e.clientY};
            
            return cancelEvent(e);
        }
        
        function setupTransform() 
        {
            gMain.setAttribute("transform", "scale(" + gMain.vScale + "," + gMain.vScale + ")");
        }
        
        function hookEvent(element, eventName, callback)
        {
            if(typeof(element) == "string")
                element = document.getElementById(element);
            if(element == null)
                return;
            if(eventName == 'mousewheel')
            {
                element.addEventListener('DOMMouseScroll', callback, false); 
            }
            else
            {
                element.addEventListener(eventName, callback, false);
            }
        }
        
        function cancelEvent(e)
        {
            e = e ? e : window.event;
            if(e.stopPropagation)
                e.stopPropagation();
            if(e.preventDefault)
                e.preventDefault();
            e.cancelBubble = true;
            e.cancel = true;
            e.returnValue = false;
            return false;
        }
        
        function onMouseWheel(e)
        {
            e = e ? e : window.event;
            var wheelData = e.detail ? e.detail * -1 : e.wheelDelta / 40;
            
            if((gMain.vScale > 0.1) || (wheelData > 0))
            {
                gMain.vScale += (0.02 * wheelData);
            }
            
            setupTransform();
            
            return cancelEvent(e);
        }
    ]]>
    </script>
    <g id="gMain">
        <g transform="translate(50,50)" id="mover">
            <circle stroke-width="2" stroke="black" cx="0" cy="0"  r="20" fill="red"/>
            <text font-family="verdana" text-anchor="middle" transform="translate(0,40)" fill="black" stroke-width="1" font-size="12" >Drag me!</text>
        </g>
    </g>
</svg>

There is some overlap in the Javascript presented there, this is just to keep things simple if you're copy/pasting this to test for your self.

This Javascript in the main file passes the mouse wheel event info to the SVG document:

function onMouseWheel(e)
{
   var doc = document.getElementById("svgImage").contentDocument;    
   e = e ? e : window.event;
   doc.defaultView.onMouseWheel(e);
   return cancelEvent(e);
}

The rest of the important Javascript is in the SVG document.
To get dragging to work, first define a global object to hold position information:

var mouseCoords = { x: 0, y: 0 };

When the mouse moves over the desired element, update the object:

function onMouseOver(e)
{
    mouseCoords = {x: e.clientX, y: e.clientY};
}

There also needs to be a global boolean to switch dragging on and off. I called mine isDragging. Toggle dragging when the mouse is up or down on the element.

function onMouseDown(e)
{
    isDragging = true;
}
       
function onMouseUp(e)
{
    isDragging = false;
}

When moving the mouse with dragging on, change the position of the element and update the object. Notice that the delta is being divided by the scale. This prevents the movement from becoming erratic.

function onMouseMove(e)
{
    if(isDragging == true)
    {
        var g = e.currentTarget;
        var pos = g.vTranslate;
        var xd = (e.clientX - mouseCoords.x)/gMain.vScale;
        var yd = (e.clientY - mouseCoords.y)/gMain.vScale;
        g.vTranslate = [ pos[0] + xd, pos[1] + yd ];
        g.setAttribute("transform", "translate(" + g.vTranslate[0] + "," + g.vTranslate[1] + ")");
    }
   
    mouseCoords = {x: e.clientX, y: e.clientY};
   
    return cancelEvent(e);
}

And that's how it works.

Pomodoro!

I've been feverishly subscribing to blogs recently after I realised I'm only really reading channel9.

I've got so much reading to do it's unreal. I've got through about 50 .NET posts so far and I've got 50 more to go, before I'm caught up. I've also got about 50 PHP posts to read too.

In my .NET blogs I came across this entry: You say tomato i say pomodoro at the developing for .NET blog. The post outlines a simple way to help manage your time effectively. It has inspired me to create a little timer app and a todo list app.

The timer app is really simple: it's a picture of a tomato with a button on it that minimises the app to the notification area and sets a timeout period. Once the period is reached (the length is set in the config file) then the app pops back up and plays a sound at you. I've put the code over at GitHub: code for Pomodoro timer.

The todo list app is equally simple, just a list view and list item entry controls. On close it writes to a file. The source is also at GitHub: code for To Do List.

update

I've uploaded the binaries for each, so you don't have to compile them!

To Do List executable
Pomodoro executable

dec2int and foldl

So, I'm trying to learn Haskell (as well as about functional programming) and I have a book I'm using: Programming in Haskell by Graham Hutton.

At the end of each chapter there are exercises.

Chapter 7 is about higher-order functions and one of the exercises is to create a function dec2int which is of the type dec2int :: [Int] -> Int and takes a list of decimal numbers (i.e. numbers 0 to 9); so given the input [1,2,5,7] dec2int would output 1257. The other stipulation is that the function must use foldl.

Step 1 - define dec2int recursively

My first thought in solving this problem was that I wanted to have a working dec2int function.

dec2int [] = 0 dec2int (x:xs) = x*10^(length xs) + dec2int xs

Not very efficient, obviously, as it has to call length for each call to the function, but it works and gives a general idea as to how to write the function.

Step 2 - define dec2int to the letter but not the spirit of the problem

I spent quite some time trying to understand foldl as it's described in the book. foldl's type is foldl :: (a->b->a)->a->[b]->a. A recursive definition looks like this (taken from the book)

foldl f v [] = v foldl f v (x:xs) = foldl f(f v x) xs

So the function f that's passed into foldl has to take a default value, a current value, and return a value that can be used in the function in place of the default value.

My first successful attempt at this does not seem to me to be in keeping with the spirit of the problem:

xANDpos :: [a] -> [(a,Int)] xANDpos [] = [] xANDpos (x:xs) = (x,len):xNp len xs where len = length xs xNp _ [] = [] xNp (pos + 1) (x:xs) = (x,pos):xNp pos xs dec2int :: [Int] -> Int dec2int xs = foldl dec2int' 0 (xANDpos xs) where dec2int' n (x,pow) = n + x*10^pow

f in this instance is dec2int'. xANDpos is a function that takes a list of something and returns a list of tuples of something and its position in the list, if the list were reversed. Not the best name for the function.

I don't think this is in the spirit of the problem because, while it does accomplish the goal, it adds an extra section of recursion when recursion is meant to be being handled by foldl.

Step 3 - this time with spirit

It took some time, but I finally realised that my first function wasn't the only way to get to the answer. The final version is a lot simpler than the second, and therefore more beautiful.

dec2int :: [Integer] -> Integer dec2int = foldl d2i 0 where d2i n x = n*10 + x

This is also a lot quicker - it doesn't traverse the list multiple times. As you can see, I've changed the type of the function, slightly, to allow for bigger numbers to be produced.

Here is a worked example of how the function functions:

dec2int [3,7,0,4,2] = foldl d2i 0 [3,7,0,4,2] = foldl d2i(d2i 0 3 = 0*10 + 3) [7,0,4,2] = foldl d2i(d2i 3 7 = 3*10 + 7) [0,4,2] = foldl d2i(d2i 37 0 = 37*10 + 0) [4,2] = foldl d2i(d2i 370 4 = 370*10 + 4) [2] = foldl d2i(d2i 3704 2 = 3704*10 + 2) [] = foldl d2i 37042 [] = 37042

The function can also be written as a one liner, using lambda: dec2int = foldl(\n x -> n * 10 + x) 0 however I think the other version is more readable.

The problem I encountered here was that my first assumption was incorrect, i.e. the function I came up with in step 1 was not the only way to solve the problem using recursion.

Lesson learned!