I started doing sudoku in 2005. It was usually in the paper, and I was bored, so I decided to give it a try. I became hooked. As I became more obsessed, I began to wonder to myself, if I could find a way to look at a sudoku problem, and solve it instantly. I thought it was possible, because it has the following properties:

• A sudoku puzzle is an nxn matrix (square)
• All columns and rows add up to the same number: 45
• It is a latin square

So I started trying all sorts of things, to see if a method existed to solve it. I even wrote a guide on how to solve it by pen and paper. Exasperated, I went and talked to my math professor. He told me point-blank, “boy, its not possible, but if you can figure out a way to do it, you’ll be a millionaire!” You see, the problem of solving a sudoku problem is NP-Complete.

Let me explain a little bit about NP-complete problems. They are a type of problem who’s answer can be checked and verified very quickly, but actually coming up with that answer would take quite a long time (I know, I know, deterministic Turing machine, but that would require 2 more definitions and like 4 more paragraphs!) There’s another set of problems that are “Polynomial”, meaning they CAN be solved fairly quickly. All the NP-complete problems are linked to one another, so if you can figure out how to do one in Poly-time, then you can do them all in Poly-time.  However, if you do manage to figure out that algorithm, then you’ve essentially solved the “P vs NP” problem, a “Millennium Prize” problem, netting you $1 million.

So imagine my surprise today, upon reading the Toronto Star, and seeing that an “academic finally cracks the Sudoku code“! I didn’t really believe it, so I checked out the paper. Here’s the algorithm:

1. Find all forced numbers in the puzzle
2. Mark up the puzzle
3. Search iteratively for preemptive sets in all rows, columns, and boxes, taking appropriate crossout action as each new preemptive set is discovered -until
4. either
   a) a solution is found or
   b) a random choice must be made for continuation
5. If 4a), then end; if 4b), then go to step 3.

This is actually the same algorithm I use when I am doing it myself. So, let me reword it for you:

1. Find all the obvious ones (forced, meaning those numbers can go no where else)
2. Now in each square, list all the possible numbers that can go there and write it in that box (the mark ups)
3. Look at the entire puzzle, go through the mark ups, and see which ones cancel each other out. Do this until
4. You end up with squares with only one mark up left (thus it must be the solution) or squares where you have to guess (usually two choices).
5. If there’s only one mark up, that’s the solution. Else, go back to step 3.

If you ever played Nintendo’s Brain Age, their game allows you to use the same system of “markups”, so really, the algorithm is just what people would be doing anyways:

Ram Murty, a Queen’s University mathematics professor who has read the paper – “Pen-and-Paper Algorithm for Solving Sudoku puzzles” – said Crook has “codified what the average mind does when it looks at a Sudoku problem.”

The algorithm doesn’t even do anything to solve the “P vs NP” problem, since this is just a sudoku puzzle of size 9×9. Once you move to bigger ones, it takes longer and longer, which defeats the purpose!  As well, the article brags that the “Sudoku Code” has been cracked, despite the existence of other algorithms to solve sudoku.

I got bored of sudoku a while back, but maybe I’ll try to program a sudoku-solver. Sounds fun.

I just read an excellent article from esquire, called “Signs of Economic Depression“. Its about was about how people should of known about the economic crisis, but they failed to actually anticipate it because they are only taking into account current data. A great example is the following quote:

If you had done this calculation in January 2008, using data from the past sixty years…you would have estimated the chance of a crash in the upcoming quarter to be 3.17 percent, implying about one crash for every eight years of economic activity…But suppose instead that your time horizon is shorter. You decide to look only at data from the past twenty years …you would assess the probability to be just 0.04 percent — meaning one crash for every 624 years.

So by not taking into account all the information available, the economist’s calculation becomes very skewed, which ultimately effected their decisions. I think George Santayana said it best.

Those who cannot learn from history are doomed to repeat it.

Its exactly like approximation a function. If you are approximating a function, and you do not give enough points, then your approximation won’t be as good, which could mislead you when making decisions.

Unfortunately, not enough people do it. Not just regular people, but great leaders too. Hitler (not saying he’s a good person, but a good leader) did not know history, and decided to try and conquer Russia. But like Napoleon before him, he failed due to Russia’s harsh winter conditions.

As Sir Francis Bacon said,

Knowledge is power

So its important to do your research. This is especially true in software engineering, where projects failure rates are very high. However, failing projects might be a good thing, as long as you learn from your mistakes.

When I went to CUSEC, I actually got an interview for Direct Energy’s IS Graduate Program. The interview was surprisingly harder then the Microsoft Interview I had in the past. They asked me questions about software development, software patterns, math riddles, and programming questions.

My programming question was to output the first 10 numbers of the fibonacci sequence. A buddy of mine got the same question on his microsoft interview, so its beginning to look like a fairly common question for tech interviews. With that realization, I decided to try and program each one. Here’s my results:

Iterative Approach

def fib(n):
        first = 0
        second = 1
        for i in range(1, n):
                temp = second
                second = second + first
                first = temp
        return second

Recursive Approach

def fib(n):
        if n == 0:
                return 0
        if n == 1:
                return 1
        return fib(n-1) + fib(n-2)

Dynamic Programming Approach
I just learn this way today! Partly what inspired this post.

val = {0:0, 1:1}
 
def fib(n):
        if n not in val:
                val[n] = fib(n-1) + fib(n-2)
 
        return val[n]

So after I finished each version, I got a bit curious over how fast they were compared to each other. So I started timing each one. (I know, I know, I could just use big-O notation and figure it out easily… but what’s the fun in that?) Here’s my results:

Fibonacci(10)
Iterative: 0.0 seconds
Recursive: 0.0 seconds
Dynamic: 0.0 seconds

They’re pretty much the same. Lets push it harder.

Fibonacci(25)
Iterative: 0.0 seconds
Recursive: 0.15 seconds
Dynamic: 0.0 seconds

And harder…

Fibonacci(30)
Iterative: 0.0 seconds
Recursive: 1.63 seconds
Dynamic: 0.0 seconds

Whoa, only 5 more terms and the recursive version jumps up to 1.63 seconds? That’s some crazy exponential growth! But why does that happen? The recursive version is taken directly from the mathematical definition, which means any number it calculates, its just recalculating each number before it multiple times.

The dynamic version has recursion, but it stores each number, which saves the amount of calculation needed.  Both iterative and dynamic versions seem to be doing pretty good, so lets pit them against one another.

I tried 100, 250, 500, and they’re still the same. At around 700, the iterative version SOMETIMES is faster:

Iterative: 0.0 seconds
Dynamic: 0.01 seconds

However, at 1000, the dynamic version doesn’t work anymore:

RuntimeError: maximum recursion depth exceeded

So far, iterative is winning. I don’t like that. The iterative version just does work over and over again needlessly. So I created a loop that runs each one 1000 times, from 1 to 1000. Here’s the results:

Fibinacci(1) to Fibinacci(1000)
Iterative: 0.22 seconds
Dynamic: 0.01 seconds

Which as you can see, the dynamic version wins over time because it saves each answer. So I guess if I go on another interview, I will know which one works best.

I’ve decided to write about passwords today. So what made me decide to do so? Because yesterday, I locked my keys inside my room. You know what sucked even more? The fact that my landlord didn’t have a spare key. So how did I get back into my room? I brute-forced it. Here’s a few pictures to illustrate my point.

This is what my door knob looks like. Its just a regular one, insert key, turn, open. Simple. Except, I forgot the key, which meant I had to either elegantly pick the lock, or brutishly break it. Since I hadn’t leveled up my lock-picking skills high enough, I decided to go with the latter. Here’s the aftermath.

Notice the lack of a door knob? Yes. I ripped it off with my bare hands (a saw)! In case any of you thieves are planning to rob me this weekend, just remember, the black market value of all my stuff is probably less then the clothes you are wearing, so not worth the effort.

The whole experience got me thinking about passwords. If the lock isn’t strong enough (think bank vault), people like me can brute-force it and break in without knowing the password.

So you gotta really choose a strong password to make sure your stuff is safe. Too many people have simple and easy to remember passwords. Because of this, it is easy to brute-force and break in. Here’s how to calculate how many different possibilities exist for your passwords (how strong it is):

1. First, you look at the letters you’ve used
   Lowercase: 26 possible combinations per letter
   Uppercase: 26 possible combinations per letter
   Numbers: 10 possible combinations per letter
   Punctuation: 30 possible combinations per letter

   Add the possible combinations together.

2. Then you count how many letters are in your password
3. Then take the “possible combinations per letter” and multiply it by itself [numletters] times.

I wanted to say something like “to the power num letters”, but I still havn’t figured out how to express that in wordpress. Damn.

So, for example, IF my password was “anton”, I see that there’s 5 letters, but only lowercase. So that’s 26 to the power 5 possible combinations, which is about 11,881,376 possible combinations. That SEEMS like a lot, but you have to remember we’ve got very powerful computers available. Apparently, this site claims it can do 1 billion passwords per second. So 26 to the power 5? 11 seconds and your account is compromised. Now lets try a password with punctuation, lower case, uppercase, and numbers that has 8 characters. That’ll be 92^8, bringing us up to…

5.13218873 × 10^15 combinations

That’s ALOT of possible combinations.  1 billion passwords per second? That’s about 5,000,000 BILLION combinations! That’s 57 days of crunching.

But not everyone will brute-force. There’s dictionary attacks, which try every word in the dictionary, which is actually quite effective, mainly because people like passwords that are easy to remember. There’s even smart brute-forcing, which means doing things like going through a dictionary, and making variations of the word, changing  a to @, i to !, o to 0, etc… until it finds a combination that works.

So how to find a good password? Leah Culver has a pretty cool technique. Think of a lyric or phrase that’s easy for you to remember. I’ll use Jason Mraz’s song, “Butterfly”:

Let me feel you upside down, slide in, slide out

So the password is, “LmFyUdSiSo” (notice the alternating uppecase?). But that’s not good enough. Its got uppercase and lower case, seemingly random (so no dictionary attacks), but we gotta add numbers or punctuation to make it even harder.

Lets try this:

Let “Upside” be  ^

Let “Slide in” be =>0

Let “Slide out” be <=0

Which transforms our password into “LmFy^d=>0<=0″

It has numbers, punctuation, uppercase, lowercase. It has it all! 57 days? Psft! I’ll be waiting!

Note: please don’t try that password, its my only one… I don’t know what I would do if I ever lost it..

Every few years, I’d hear news of someone finding a prime number and getting awarded big bucks for doing so. Whenever I heard this kinda news, I’d think about how easy it would be to actually find them myself. I mean, it almost seemed too easy:

      1) Remove all even numbers
      2) Remove all multiples of 5
      3) Check all numbers ending in 3, 7, and 9 if they're prime or not.

So if you have a set of n numbers, taking out all the even numbers would leave you with n/2 numbers. Unfortunately, taking out the multiples of 5 didn’t do much, so its actually leaving you with 2n/5 numbers. My algorithm back in the day had also left out one important fact: How do I actually check if they’re prime?

With project euler, I was forced to actually re-evaluate my algorithm, and you know what? It failed spectacularly! However, it led me to something else. Its this SWEET algorithm called the “Sieve of Eratosthenes”.  Here’s how it goes:

     1) Make a list A of all numbers 1 to n.
     2) Make a list B to hold all the primes you find. The first item will be 2.
     3) Remove ALL multiples of 2 from list A.
     4) The first remaining number will be a prime. Add this to B.
     5) Grab that number and remove all multiples of it from list A.
     6) Repeat 4) and 5) until no numbers are left in List A.

It works perfectly (albiet pretty slow)  and it does its job: getting a list of n primes.  Apparently other people thought so themselves, so much in fact, that they actually wrote a poem about it!

Sift the Two’s and sift the Three’s,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Isn’t that cool? It even rhymes!

When I was learning “Computer and Network Security”, I actually learnt about another prime number generator. It uses a few complicated theories, namly Fermat’s little theorem and the Fermat primality test (aww man, I could of used this in my first algorithm!). Its good and it works, but its not as cool as the Sieve.

In other news, I can’t believe I just blogged about prime numbers. I am living up to my blog’s tagline already!