I think I went off on a tangent in my last posts but the basic idea through backtracking search is that the computer is able to know where it's been and where it needs to go. This is where recursion and the stack comes in, mainly.
Whenever a function is called, the variables passed get loaded onto either the stack or into registers, depending on the architecture of the computer. The actual implementation details aren't too terribly important, except that the first function also saves a copy of its registers in the stack space. This DETAIL does become vitally important for recursion to work properly. When you go into recursion, you have to go out eventually. It's like running into a forest. You can only run so far before you start running out.
Most programmers know that, if you declare a variable called foo, set it to contain the value "5" as a number, and call another function, foo still contains 5 when you come back. However, things tend to get a little trickier when you're dealing with recursion, because then a function is calling itself. Which means you now have to think of foo as a local variable but also as a local variable that may have a completely different value. They're named the same, they come from the same function, so recursion is a little tricky to think about sometimes, especially when going out of it.
Going out of recursion means the calls you have made are returning, and control is returning to functions that made these calls. These functions and their variables sit lower on the stack, and as control is returned, the functions will keep doing what they need to do with the variables they had started with, despite any changes other function calls might have made.
This is assuming the variables were passed by value, of course. This isn't something you want to do with large objects, and sometimes, you want recursive algorithms to manipulate the data they are passing to copies of themselves, since the whole idea is to break down a problem into parts. Merge sort is a good example. Break an unsorted list into multiple unsorted lists until they are of a certain size, and then sort those lists, and then merge the smaller sorted lists into one big list.
Now what do you do if you want to manipulate the data passed, but you want to also don't want to make the changes permanent? We could do pass-by-value, but what if it's a big object, or a big array? It is also possible to do pass-by-reference and just undo what we did after the function call, and this is generally how a backtracking search gets implemented.
First, you find a partial solution. In the case of the n-queens problem, this can be an empty board. An empty board can be considered a partial solution in much the same way that, if you have an idea of something, then you have a partial solution to that problem (no idea -- nowhere near to getting a solution). From there, you place your queen, make a call, try to place another queen, and if that doesn't work, you return the control to the function that called you and let him clean up the placement of his queen and try again. This would just look like the opposite of what you just did before you make another call. I should probably point out that backtracking search requires a loop to make this possible.
Backtracking search doesn't require a computer though, of course. If you got stuck in a minotaur's labyrinth you would be able to find your way out if you were able to keep track of where you need to look, and where you've already looked.
Monday, March 14, 2011
Tuesday, March 8, 2011
Backtracking search, pt2
The way we would tell a computer to solve this problem is through an algorithm called backtracking search.
Understanding the algorithm requires some knowledge of recursion, and a little bit of intuition about what is going on.
Recursion breaks down a problem into smaller pieces of itself, as is the case for Binary Search, or when previous computations of the problem must be known for further computations of the problem, as is the case with Fibonacci. To do this, recursion calls itself. This saves a copy of the old function on the stack, and, when the new function exits, the old function continues. This functionality is what allows a backtracking search algorithm to undo what it did and to continue on to finding another possible solution. It is what allows the computer, in the n queens problem described in part 1, to take off the queens it needs to when it has not arrived at a solution (or when it has, and it wishes to search for another solution).
Recursion makes algorithms short and sweet. I had to implement backtracking search, recently, to find the number of solutions to a problem where a spider (or crab, or other kind of actor) can move around a board in 8 directions, and I was tasked to find out how many different ways it could move across a board so that it reaches a finish square and touches all squares once.
The entire code base turned out to be fifty-four lines, but it's fifty-four lines of code that seemed to be doing quite a lot. Some of the boards given by the testing program had around 3,000 solutions. I mean, fifty-four lines just to do all of that!
It's pretty amazing.
Understanding the algorithm requires some knowledge of recursion, and a little bit of intuition about what is going on.
Recursion breaks down a problem into smaller pieces of itself, as is the case for Binary Search, or when previous computations of the problem must be known for further computations of the problem, as is the case with Fibonacci. To do this, recursion calls itself. This saves a copy of the old function on the stack, and, when the new function exits, the old function continues. This functionality is what allows a backtracking search algorithm to undo what it did and to continue on to finding another possible solution. It is what allows the computer, in the n queens problem described in part 1, to take off the queens it needs to when it has not arrived at a solution (or when it has, and it wishes to search for another solution).
Recursion makes algorithms short and sweet. I had to implement backtracking search, recently, to find the number of solutions to a problem where a spider (or crab, or other kind of actor) can move around a board in 8 directions, and I was tasked to find out how many different ways it could move across a board so that it reaches a finish square and touches all squares once.
The entire code base turned out to be fifty-four lines, but it's fifty-four lines of code that seemed to be doing quite a lot. Some of the boards given by the testing program had around 3,000 solutions. I mean, fifty-four lines just to do all of that!
It's pretty amazing.
Backtracking search, pt1
I give you a puzzle and I tell you that this puzzle has a million solutions to it. Furthermore, I want you to find all one million solutions. How would you accomplish this? It would likely be a very time-consuming task, and there would be well, quite a bit of things to keep track of.
Let's get a little more specific. I have a chessboard, and I want to know how many configurations of queens I can have, so that one queen occupies a row, and no queen is able to attack one another. Let's go a little simpler. I have a chessboard that is 1x1. How many solutions are there? One, and this is a pretty trivial case. There are no solutions for a 2x2 board and there are no solutions for a 3x3 board, but there are two solutions for a 4x4 board.
How would we find them?
Let's start with an empty board.
....
....
....
....
Let's place a queen in the first row, first column.
Q...
....
....
....
Now, let's go to the second row. Since we cannot place a queen in the first or second column, let's place a queen in the third column.
Q...
..Q.
....
....
Now, for the third row. Where can we place a queen?
The first, second, third, and fourth columns are right now. So we must backtrack. We will take off our queens, and start by placing one at the second column.
.Q..
....
....
....
Our next possible place is the fourth column, second row.
.Q..
...Q
....
....
Now, our next possible place is the first column, third row.
.Q..
...Q
Q...
....
Our last place to check is the 3rd column, last row.
.Q..
...Q
Q...
..Q.
And now we have a solution. This took about seven steps. Quite awhile. There is one more solution to a 4x4 board, but it's just a mirror image. I won't get solving this as you should see the pattern.
So, how would we find all solutions for an 8x8 or even an NxN problem set?
With a computer that can do what we did. Of course.
Let's get a little more specific. I have a chessboard, and I want to know how many configurations of queens I can have, so that one queen occupies a row, and no queen is able to attack one another. Let's go a little simpler. I have a chessboard that is 1x1. How many solutions are there? One, and this is a pretty trivial case. There are no solutions for a 2x2 board and there are no solutions for a 3x3 board, but there are two solutions for a 4x4 board.
How would we find them?
Let's start with an empty board.
....
....
....
....
Let's place a queen in the first row, first column.
Q...
....
....
....
Now, let's go to the second row. Since we cannot place a queen in the first or second column, let's place a queen in the third column.
Q...
..Q.
....
....
Now, for the third row. Where can we place a queen?
The first, second, third, and fourth columns are right now. So we must backtrack. We will take off our queens, and start by placing one at the second column.
.Q..
....
....
....
Our next possible place is the fourth column, second row.
.Q..
...Q
....
....
Now, our next possible place is the first column, third row.
.Q..
...Q
Q...
....
Our last place to check is the 3rd column, last row.
.Q..
...Q
Q...
..Q.
And now we have a solution. This took about seven steps. Quite awhile. There is one more solution to a 4x4 board, but it's just a mirror image. I won't get solving this as you should see the pattern.
So, how would we find all solutions for an 8x8 or even an NxN problem set?
With a computer that can do what we did. Of course.
Tuesday, October 26, 2010
CS301 (Assembly Programming) project
Well, that time has come. Midterms have come, they have gone, and now I'm left with projects.
I wrote an old program 2-3 years ago that did three things. It tested to see if a number was prime. It was able to break down a number into it's factors (think quadratics), as well as its prime factors (for taking the root of a number).
When the project came down my first idea was to make a PC boot block, after some discussion with my teacher I decided that this was far too complex of a task to take on given the time constraints, so I settled on re-writing some parts of this program in Assembly.
I wrote this program in Java, so I have some additional work too. Anything external I decide to use from the program I need to port to c code first. I don't know C, so this has potential to be a pretty interesting project as it is.
I wrote an old program 2-3 years ago that did three things. It tested to see if a number was prime. It was able to break down a number into it's factors (think quadratics), as well as its prime factors (for taking the root of a number).
When the project came down my first idea was to make a PC boot block, after some discussion with my teacher I decided that this was far too complex of a task to take on given the time constraints, so I settled on re-writing some parts of this program in Assembly.
I wrote this program in Java, so I have some additional work too. Anything external I decide to use from the program I need to port to c code first. I don't know C, so this has potential to be a pretty interesting project as it is.
Friday, September 17, 2010
0xb0, 0xea7beef, 0xc3
My CS301 (Assembly Programming Language) teacher has a brilliant style of teaching. In actuality he's a pretty amazing guy all around. Nice guy, always willing to talk shop about Computer Science, and extremely sharp. Sometimes I need to remind myself that he's still just a man. like me.
Our lesson today started out talking about a cat. We have an array of commands. What if we want it to eat, and what if we want to specify what it eats? We have two options. We can have an array of parameters to go with these commands. But what if some commands don't have parameters? What do we do?
Or, and this is a slightly better solution. What if we have one array, and if we want parameters after a command, put them after the command to be processed, and then go on? Now we have one array, and now we have commands and parameters as needed if we know what commands need parameters.
Well, this is still a little bit confusing. How about an example (in my own handrolled pseudocode here)
let cat_cmds be an array of words
initialize cat_cmds to "sleep", "wake", "eat", "Friskies", "Meow", "sleep", "exit"
From here, we can loop through the array, and knowing that the command "eat" will take a parameter, we can step through the array and process the command, and then we can move on. When we reach the exit command, we close down the program.
Why do this convoluted example? Well...
If you change these commands to byte codes, make a function pointer to that array, and then call the function, you have a function out of machine code, because this is how computers are coded.
It was pretty beautiful. I don't think that, if he had simply launched into a lecture about bytecodes without first drawing a parallel that we could have understood a lot easier. It was interesting to learn that this is how computers work under the hood. I think I'm starting to see the big picture. Computers don't really understand anything. They just process information into human readable formats.
Yeah, that's right.
They're dumb as rocks.
Our lesson today started out talking about a cat. We have an array of commands. What if we want it to eat, and what if we want to specify what it eats? We have two options. We can have an array of parameters to go with these commands. But what if some commands don't have parameters? What do we do?
Or, and this is a slightly better solution. What if we have one array, and if we want parameters after a command, put them after the command to be processed, and then go on? Now we have one array, and now we have commands and parameters as needed if we know what commands need parameters.
Well, this is still a little bit confusing. How about an example (in my own handrolled pseudocode here)
let cat_cmds be an array of words
initialize cat_cmds to "sleep", "wake", "eat", "Friskies", "Meow", "sleep", "exit"
From here, we can loop through the array, and knowing that the command "eat" will take a parameter, we can step through the array and process the command, and then we can move on. When we reach the exit command, we close down the program.
Why do this convoluted example? Well...
If you change these commands to byte codes, make a function pointer to that array, and then call the function, you have a function out of machine code, because this is how computers are coded.
It was pretty beautiful. I don't think that, if he had simply launched into a lecture about bytecodes without first drawing a parallel that we could have understood a lot easier. It was interesting to learn that this is how computers work under the hood. I think I'm starting to see the big picture. Computers don't really understand anything. They just process information into human readable formats.
Yeah, that's right.
They're dumb as rocks.
Friday, November 20, 2009
Linux = freedom : part 1
I finished the programming assignment I gave for myself and realized that I really needed to update my blog.
so I just typed into the console, "firefox www.abstract-code.blogspot.com"
and whoop, there I was!
If I was on Windows, I'd have to have double-clicked on firefox, go to my homepage, and then type in my webpage. This might have meant minimizing whatever I was doing at the time, which takes more precious seconds.
People complain about computers trapping them into working more and having less free time to do what they need. However, I don't think the computer is the culprit, Well, it is, but it's not the system itself so much as it is people's unwillingness to seek out and learn how to free themselves of the shackles technology has placed on us.
Technology is created to free our lives. Unfortunately, so many people feel one must be truly gifted to understand and use technology effectively, that they settle for less useful, but more intuitive versions of it, for various reasons. They're not happy, but they feel a need to use it, so they stick with it.
I wasn't much of an exception. While I had access to DOS as a kid, I never used it much. A GUI where I could click around in was a lot simpler, and my own personal reasons for using Windows for so long was because I was never exposed to anything different. My exposure to linux came in college, where so many people used it that I decided to give it a shot. I played with it for awhile, then went back to Windows.
But Windows is very limiting in its power. It's useful, but I feel that I can do more in linux with a few basic commands than I ever was able to in windows.
For example
cd folder1 ; mkdir folder2 ; cd folder2 ; mkdir folder3 ; cd folder3; touch file.txt ;
is a series of commands goes into a folder, makes a folder, goes into that folder, makes another folder, goes into it, and then creates a text file.
There's another way to do this
such as
mkdir folder1 ; mkdir folder1/folder2; mkdir folder1/folder2/folder3; touch folder1/folder2/folder3/file.txt
that seems to be faster, and accomplishes the same thing. Except that you're not really moving anywhere in the system (to do anything in windows, it seems, you have to be in that location physically). Being able to do this is pretty amazing to me because it's a lot faster and a lot less clicking. I feel like I'm actually in control.
so I just typed into the console, "firefox www.abstract-code.blogspot.com"
and whoop, there I was!
If I was on Windows, I'd have to have double-clicked on firefox, go to my homepage, and then type in my webpage. This might have meant minimizing whatever I was doing at the time, which takes more precious seconds.
People complain about computers trapping them into working more and having less free time to do what they need. However, I don't think the computer is the culprit, Well, it is, but it's not the system itself so much as it is people's unwillingness to seek out and learn how to free themselves of the shackles technology has placed on us.
Technology is created to free our lives. Unfortunately, so many people feel one must be truly gifted to understand and use technology effectively, that they settle for less useful, but more intuitive versions of it, for various reasons. They're not happy, but they feel a need to use it, so they stick with it.
I wasn't much of an exception. While I had access to DOS as a kid, I never used it much. A GUI where I could click around in was a lot simpler, and my own personal reasons for using Windows for so long was because I was never exposed to anything different. My exposure to linux came in college, where so many people used it that I decided to give it a shot. I played with it for awhile, then went back to Windows.
But Windows is very limiting in its power. It's useful, but I feel that I can do more in linux with a few basic commands than I ever was able to in windows.
For example
cd folder1 ; mkdir folder2 ; cd folder2 ; mkdir folder3 ; cd folder3; touch file.txt ;
is a series of commands goes into a folder, makes a folder, goes into that folder, makes another folder, goes into it, and then creates a text file.
There's another way to do this
such as
mkdir folder1 ; mkdir folder1/folder2; mkdir folder1/folder2/folder3; touch folder1/folder2/folder3/file.txt
that seems to be faster, and accomplishes the same thing. Except that you're not really moving anywhere in the system (to do anything in windows, it seems, you have to be in that location physically). Being able to do this is pretty amazing to me because it's a lot faster and a lot less clicking. I feel like I'm actually in control.
Make change in your life
Currently Reading: Data Abstractions and Problem Solving with C++: Walls And Mirrors (fourth edition)
I just finished reading the first chapter of this book, and did the first programming exercise it wanted me to do (the fist of two or three I will do, likely), even though I had a basic idea of how to solve it because I actually did write this before.
The problem is to write a function that computes the change a cashier needs to give to a customer. While this is something given to any first year CS student, because it is an awesome way to test a student's division and critical thinking skills, as well as his ability to code leglibly, it is also a real world problem because depending on where a cashier works, it is his till that might be handing out change. Some stores have self-checkout, and with the popularity of cash, not only must a computer register which dominations of coins to give change to, but also what denomination of bills to give change in.
I've solved this problem three times. The first time it was in illegible piece of shite that while I understood it while I was making it, I honestly couldn't understand it today even if I tried (and I have). Granted, I was a first year CS student at the time writing spaghetti in Java and calling my shit gold because it worked. I probably hadn't been coding for more than three months at the time. The concept of maningful variable names or well thought out code was unknown to me at the time.
The second time I solved it was when reading this book the first time (I had gotten to the end of chapter 2 before school got out), and I solved it for change, but not bills, and had used a different function for each computation, when one function would have done just as well. It worked. Except change for anything other than coins was given in a lot of coins. What I mean is that the second version would give 70 dollars worth in quarters when the person should get back a 50 and a 20.
The third time I solved it right, I think, because it includes bills and coins. I know the first one did this too, but it wasn't very well written. Actually, solving it is a simple task, requiring only a few steps
1) Take the amount owed and divide it by the value of the denomination (e.g. $75 / $ 20 = 3).
2) Subtract the denomination, times the quotient from the amount owed. This becomes the new amount (e.g. new amount = $75 - ($20 * 3).
3) Repeat step 1 with the new amount and the lower denomination (e.g. $15 / $10 = 1) until you reach the lowest denomination (which for Americans, is pennies. Unless we do away with them, and then we've fucked ourselves basically).
Design questions of course could be how to handle the data coming in. Since money consist of dollars and cents, it is common to think of handling money in terms of a float (32 bit number that can hold a decimal value, like 2.75, or 1.69, or 13.37, as opposed to integers, which are whole numbers), but this can be prone to roundoff errors and loss of precision. Another way to think of money is in terms of whole numbers, where a penny is 1, and a hundred is 10,000. I suspect this is how modern systems that handle cash deal with money, and while more complex to deal with, it offers a few advantages in that it would be less prone to errors (I remember the first time I solved this problem, I had to add 0.003 to the number just to make sure the correct amount of change was given, every time) because both dollars and cents are being treated as the same data type (in this case, ints, or whole numbers), which would mean the possibility of truncating a float's decimal value when converting to an integer would go away, and the problem is reduced to one of simple place-value.
I just finished reading the first chapter of this book, and did the first programming exercise it wanted me to do (the fist of two or three I will do, likely), even though I had a basic idea of how to solve it because I actually did write this before.
The problem is to write a function that computes the change a cashier needs to give to a customer. While this is something given to any first year CS student, because it is an awesome way to test a student's division and critical thinking skills, as well as his ability to code leglibly, it is also a real world problem because depending on where a cashier works, it is his till that might be handing out change. Some stores have self-checkout, and with the popularity of cash, not only must a computer register which dominations of coins to give change to, but also what denomination of bills to give change in.
I've solved this problem three times. The first time it was in illegible piece of shite that while I understood it while I was making it, I honestly couldn't understand it today even if I tried (and I have). Granted, I was a first year CS student at the time writing spaghetti in Java and calling my shit gold because it worked. I probably hadn't been coding for more than three months at the time. The concept of maningful variable names or well thought out code was unknown to me at the time.
The second time I solved it was when reading this book the first time (I had gotten to the end of chapter 2 before school got out), and I solved it for change, but not bills, and had used a different function for each computation, when one function would have done just as well. It worked. Except change for anything other than coins was given in a lot of coins. What I mean is that the second version would give 70 dollars worth in quarters when the person should get back a 50 and a 20.
The third time I solved it right, I think, because it includes bills and coins. I know the first one did this too, but it wasn't very well written. Actually, solving it is a simple task, requiring only a few steps
1) Take the amount owed and divide it by the value of the denomination (e.g. $75 / $ 20 = 3).
2) Subtract the denomination, times the quotient from the amount owed. This becomes the new amount (e.g. new amount = $75 - ($20 * 3).
3) Repeat step 1 with the new amount and the lower denomination (e.g. $15 / $10 = 1) until you reach the lowest denomination (which for Americans, is pennies. Unless we do away with them, and then we've fucked ourselves basically).
Design questions of course could be how to handle the data coming in. Since money consist of dollars and cents, it is common to think of handling money in terms of a float (32 bit number that can hold a decimal value, like 2.75, or 1.69, or 13.37, as opposed to integers, which are whole numbers), but this can be prone to roundoff errors and loss of precision. Another way to think of money is in terms of whole numbers, where a penny is 1, and a hundred is 10,000. I suspect this is how modern systems that handle cash deal with money, and while more complex to deal with, it offers a few advantages in that it would be less prone to errors (I remember the first time I solved this problem, I had to add 0.003 to the number just to make sure the correct amount of change was given, every time) because both dollars and cents are being treated as the same data type (in this case, ints, or whole numbers), which would mean the possibility of truncating a float's decimal value when converting to an integer would go away, and the problem is reduced to one of simple place-value.
Subscribe to:
Comments (Atom)