https://github.com/EJEHardenberg/SmartDesk
I've started a new project! Working on it with one of my friends who graduated last year, he's working on the Networking component and I'm working on the graphical component. It's a very promising idea in my head, and will get a lot of experience with system programming. I'm looking forward to it.
:)
Saturday, February 9, 2013
Sunday, January 20, 2013
EEG and Cairo
Using the outline in this video:
http://www.youtube.com/watch?v=ZmxmeRry2uY
And an arduino board from a friend, I plan to create a small program that will display the output of the eeg onto the screen.
As my recent kick is with C, I think I'll do that. My current plan is to create a couple different programs, one that handle the graphics and another that will handle getting information from the eeg. That way I can develop one while I assemble the EEG. I think I'll be using Cairo Graphics or OpenGL not sure which yet, I've selected Cairo because it seems like its easy to work with from the examples I've seen. And then I'll have a memory mapped file, or named pipe between the two programs so that they can share data quickly and efficiently.
http://www.linuxquestions.org/questions/programming-9/mmap-tutorial-c-c-511265/
Hopefully this all works out nicely, and if I don't manage to assemble an EEG, then at least I've worked with graphics and memory mapped files. Which I think could become a key staple to learning some parrallel processing techniques.
http://www.youtube.com/watch?v=ZmxmeRry2uY
And an arduino board from a friend, I plan to create a small program that will display the output of the eeg onto the screen.
As my recent kick is with C, I think I'll do that. My current plan is to create a couple different programs, one that handle the graphics and another that will handle getting information from the eeg. That way I can develop one while I assemble the EEG. I think I'll be using Cairo Graphics or OpenGL not sure which yet, I've selected Cairo because it seems like its easy to work with from the examples I've seen. And then I'll have a memory mapped file, or named pipe between the two programs so that they can share data quickly and efficiently.
http://www.linuxquestions.org/questions/programming-9/mmap-tutorial-c-c-511265/
Hopefully this all works out nicely, and if I don't manage to assemble an EEG, then at least I've worked with graphics and memory mapped files. Which I think could become a key staple to learning some parrallel processing techniques.
Thursday, January 17, 2013
Brain Fuck Interpreter. I made one
https://github.com/EJEHardenberg/BF_Interpret
So After a couple of days I've scrapped together my small amount of knowledge of C and created a BrainFuck interpreter.
It was pretty simple since all you're really doing is manipulating a Turing Machine. But creating the interactive bits was fun and a good thought exercise.
There are a few ways to run it once you've compiled it.
Just run it with no arguments:
Gets you the interpreter. Where you can type in all the BF commands you'd like, or comments as long as they don't include 'q' becuase 'q' is the quit key.
arguments of -f filename will read in a file and that file will be fed to the BF translator and outputted according to whatever program you decide.
arguments of anything else: will be taken as BF code and interpreted.
It's a pretty basic program, but it was a good exercise, and I'm going to refactor the code a bit. A friend of mine pointed out that the headers should be just declarations and not full blown source code.
So After a couple of days I've scrapped together my small amount of knowledge of C and created a BrainFuck interpreter.
It was pretty simple since all you're really doing is manipulating a Turing Machine. But creating the interactive bits was fun and a good thought exercise.
There are a few ways to run it once you've compiled it.
Just run it with no arguments:
Gets you the interpreter. Where you can type in all the BF commands you'd like, or comments as long as they don't include 'q' becuase 'q' is the quit key.
arguments of -f filename will read in a file and that file will be fed to the BF translator and outputted according to whatever program you decide.
arguments of anything else: will be taken as BF code and interpreted.
It's a pretty basic program, but it was a good exercise, and I'm going to refactor the code a bit. A friend of mine pointed out that the headers should be just declarations and not full blown source code.
Friday, November 30, 2012
KD Tree Range Bounded Algorithm
Searching a K-d Tree is simple enough, its just a basic binary search based off the axis you're splitting by on your nodes. Doing a nearest neighbor search is one of the most basic operations you can do on a K-d Tree and is typically what you use this type of tree for. But because of the geometric properties of the tree itself and how each node creates a splitting plane for the space, we can make an awesome algorithm that returns points in the tree that are within a specific region of space.
This is for a 2 dimensional tree and space, but could be extended to 3 easily, and probably up to k dimensions after having a headache for a while:
So First off we need to be able to define a Region in space. Because the K-d Tree splits on planes, essentially we're going to define a box in K space, so it makes sense to have our regions be square in some fashion. So here's the code to construct a region:
public class Region{
double xleft = -Float.MAX_VALUE;
double xright = Float.MAX_VALUE;
double ybottom = -Float.MAX_VALUE;
double ytop = Float.MAX_VALUE;
//Creates a region containing the entire coordinate plane
public Region(){
}
//Creates a Region defined by the four locations of its sides
public Region(double left, double right, double top, double bottom){
//Assume we might mess up and not put them in the right order for lefts and rights
if(left < right){
xleft = left;
xright = right;
}else{
xleft = right;
xright = left;
}
if(bottom < top){
ybottom = bottom;
ytop = top;
}else{
ybottom = top;
ytop = bottom;
}
}
public Region setLeft(double left){
this.xleft = left;
return this;
}
public Region setRight(double right){
this.xright = right;
return this;
}
public Region setTop(double top){
this.ytop = top;
return this;
}
public Region setBottom(double bottom){
this.ybottom = bottom;
return this;
}
//Checks to see if this Region contains the point
public boolean fullyContains(Node node){
float y =node.getY();
float x = node.getX();
return ybottom <= y && y <= ytop && xleft <= x && x <= xright;
}
public boolean fullyContains(Region r){
return xleft <= r.xleft && r.xright <= xright && r.ytop <= ytop && ybottom <= r.ybottom;
}
public boolean intersects(Region r){
return !(xright < r.xleft) && !(r.xright < xleft) && !(r.ytop < ybottom) && !(ytop < r.ybottom);
}
Once you've collected these lists for each node you do need to add all together. But why write an arraylist merging function when you can do it all at once with a flatten. Observe:
private static ArrayList<Node> flatten(ArrayList<Node> nodes){
//Flatten each nodes subtree out.
ArrayList<Node> temp = new ArrayList<Node>();
for(Node node : nodes){
temp = node.collectTree(temp);
}
return temp;
}
Once you have this, its easy to collect the results of your search and report all of them in one list to a client. There is one important thing I'd like to mention though, in the collectTree function, notice the containment check at the end. This ensures no duplicate nodes are added to the list. If you didn't have this, you would report the subtree of any subtree returned by the search at least twice. Or precisely, the leaves would be reported for whatever depth they were away from the subtree that was reported.
The project I've used this in is located at:
Tree Class
Region
This is for a 2 dimensional tree and space, but could be extended to 3 easily, and probably up to k dimensions after having a headache for a while:
So First off we need to be able to define a Region in space. Because the K-d Tree splits on planes, essentially we're going to define a box in K space, so it makes sense to have our regions be square in some fashion. So here's the code to construct a region:
public class Region{
double xleft = -Float.MAX_VALUE;
double xright = Float.MAX_VALUE;
double ybottom = -Float.MAX_VALUE;
double ytop = Float.MAX_VALUE;
//Creates a region containing the entire coordinate plane
public Region(){
}
//Creates a Region defined by the four locations of its sides
public Region(double left, double right, double top, double bottom){
//Assume we might mess up and not put them in the right order for lefts and rights
if(left < right){
xleft = left;
xright = right;
}else{
xleft = right;
xright = left;
}
if(bottom < top){
ybottom = bottom;
ytop = top;
}else{
ybottom = top;
ytop = bottom;
}
}
}
I've made some assumptions about not being able to tell my left from my right but the key point that we'll take advantage of in the algorithm later is that a Region's default is to be the entire coordinate space. Next we need to add some helping functions to alter the region
public Region setLeft(double left){
this.xleft = left;
return this;
}
public Region setRight(double right){
this.xright = right;
return this;
}
public Region setTop(double top){
this.ytop = top;
return this;
}
public Region setBottom(double bottom){
this.ybottom = bottom;
return this;
}
//Checks to see if this Region contains the point
public boolean fullyContains(Node node){
float y =node.getY();
float x = node.getX();
return ybottom <= y && y <= ytop && xleft <= x && x <= xright;
}
public boolean fullyContains(Region r){
return xleft <= r.xleft && r.xright <= xright && r.ytop <= ytop && ybottom <= r.ybottom;
}
public boolean intersects(Region r){
return !(xright < r.xleft) && !(r.xright < xleft) && !(r.ytop < ybottom) && !(ytop < r.ybottom);
}
Now it's important that the setLeft,Right,Top, and Bottom sections return a Region, we'll see why in a bit. But the more interesting part of this code is the intersects function. To see if two Regions intersect, you could do an 8 part boolean expression checking all the possible combinations of the two Regions intersecting. OR you can be clever about it. The expression to see if two Regions don't intersect is far easier than the larger expression we just talked about. You just check if it's right side is strictly less than the other regions is the left side. You do this for all 4 sides and then you negate the expression. By deMorgans laws your OR's become not ands and pow. Your intersects function is quick, efficient and done. Now lets get to the actual algorithm:
private ArrayList<Node> boundedSearch(Region sRegion,ArrayList<Node> results,int depth,Region bRegion){
int axis = depth % coordinates.length;
if(this.isLeaf()){
if(sRegion.fullyContains(this)){
results.add(this);
}
}else{
//Subtree we need to redefine our bounding region bRegion
if(axis == 0){
//We are splitting on the x axis
if(sRegion.fullyContains(bRegion)){
//We are in the region so we report ourselves
results.add(this);
}else{
if(sRegion.fullyContains(this)){
results.add(this);
}
}
if(sRegion.intersects(bRegion)){
if(this.left != null){
//Search down the left with our splitting line as a bound on the right
return this.left.innerBoundedSearch(sRegion,results,depth+1,bRegion.setRight(this.getCoordinate(axis)));
}else{
//Null link return results
return results;
}
}
if(sRegion.intersects(bRegion)){
if(this.right != null){
//Search down the left with a splitting line as a bound on the left
return this.right.innerBoundedSearch(sRegion,results,depth+1,bRegion.setLeft(this.getCoordinate(axis)));
}
}
}else{
//We are splitting on the y axis
if(sRegion.fullyContains(bRegion)){
//We are in the region so we report ourselves
results.add(this);
}else{
if(sRegion.fullyContains(this)){
results.add(this);
}
}
if(sRegion.intersects(bRegion)){
if(this.left != null){
//Search down the left with our splitting line as a bound on the right
return this.left.innerBoundedSearch(sRegion,results,depth+1,bRegion.setTop(this.getCoordinate(axis)));
}else{
//Null link return results
return results;
}
}
if(sRegion.intersects(bRegion)){
if(this.right != null){
//Search down the left with a splitting line as a bound on the left
return this.right.innerBoundedSearch(sRegion,results,depth+1,bRegion.setBottom(this.getCoordinate(axis)));
}
}
}
}
return results;
}
Alright, (one day I'll figure out how to display code nicer on these blog posts.) Let me describe how the algorithm works. The basic idea is that as you recurse down the tree, the splitting planes of the node you're visiting becomes a sides of a bounded region. This bounded region begins as the entire coordinate axis, then becomes half of that, then half of that, and etc etc. So each time you're creating a smaller and smaller space in which nodes can exist. Once this bounded region is contained within the search region, then we can report that entire sub tree as being contained. If we reach a leaf node, its a simple check to see if it is contained within the tree.
I find that thinking of this geometrically is much easier than staring at just the code and trying to understand what it does. There is some work you have to do after the results is returned. You do need to collect all the leaves in the subtrees and add them to the results.
public ArrayList<Node> collectTree(ArrayList<Node> results){
//Traverse the tree and put all children in there
if(this.left!= null){
results = this.left.collectTree(results);
}
if(this.right!=null){
results = this.right.collectTree(results);
}
if(!results.contains(this)){
results.add(this);
}
return results;
}
Once you've collected these lists for each node you do need to add all together. But why write an arraylist merging function when you can do it all at once with a flatten. Observe:
private static ArrayList<Node> flatten(ArrayList<Node> nodes){
//Flatten each nodes subtree out.
ArrayList<Node> temp = new ArrayList<Node>();
for(Node node : nodes){
temp = node.collectTree(temp);
}
return temp;
}
Once you have this, its easy to collect the results of your search and report all of them in one list to a client. There is one important thing I'd like to mention though, in the collectTree function, notice the containment check at the end. This ensures no duplicate nodes are added to the list. If you didn't have this, you would report the subtree of any subtree returned by the search at least twice. Or precisely, the leaves would be reported for whatever depth they were away from the subtree that was reported.
The project I've used this in is located at:
Tree Class
Region
Thursday, September 6, 2012
Budget Buddy Transactions and such
I'm working on the Edit button right now, which will allow you to change a transactions Name, Amount, Or Date. The trick is going to be updating the account to reflect the change. But once thats done I can get into the meat of the program itself, which isn't its checkbook, but tagging transactions and reporting spending habits based on them.
Sunday, September 2, 2012
SQL foreign key issue. Errno 150 in BudgetBuddy
Budget buddy is coming along, Im working on the transactions page. I worked for a couple hours trying to get an htaccess file to work before realizing that my apache server wasn't set up right, and then had to rework a bunch of code to make the site work again. Alot of relative linking was going awry. Luckily a bit of GIT magic brought me back to working correctly so, its ok!
Coding today took a fun detour for about 10 minutes while I tried to figure out why I couldn't apply a foreign key to my database after successfully applying one before. Heres what I had as a problem and how I solved it:
3 Tables, userinfo which has a primary key of userid, accounts which has a userid associated with it and a name (as well as an amount), and then a transactions table I had just made. So I successfully altered transactions to reference userid from userinfo so that it cascades for both updating and deleting. And if anyone doesn't know how to do it, this is the page I go to everytime I need it: This site is good for foreign key info
But then I went to apply the accountname from transactions to be a foreign key from accounts and started getting this errono-150 bit. Completely unhelpful, saying I couldn't create a table such and such. This unhelpful bit led me to google the error number and I quickly stumbled onto this link. After looking at a couple of the reasons for error I figured it was because the account names weren't indexed. I hadn't told them to be primary keys because multiple users could have an account called "Checking". But then I read up on indexing and then used the mysql documentation on create index to add an index to my table. Tried to alter it again, and viola, foreign key accepted.
I hope that if anyone gets an error similar to the one I experienced that they find this blog and use the good couple of links to fix it!
On a side note:
Has anyone ever noticed that viola, when pronounced with a bit of an accent should probably be spelt walah?
Coding today took a fun detour for about 10 minutes while I tried to figure out why I couldn't apply a foreign key to my database after successfully applying one before. Heres what I had as a problem and how I solved it:
3 Tables, userinfo which has a primary key of userid, accounts which has a userid associated with it and a name (as well as an amount), and then a transactions table I had just made. So I successfully altered transactions to reference userid from userinfo so that it cascades for both updating and deleting. And if anyone doesn't know how to do it, this is the page I go to everytime I need it: This site is good for foreign key info
But then I went to apply the accountname from transactions to be a foreign key from accounts and started getting this errono-150 bit. Completely unhelpful, saying I couldn't create a table such and such. This unhelpful bit led me to google the error number and I quickly stumbled onto this link. After looking at a couple of the reasons for error I figured it was because the account names weren't indexed. I hadn't told them to be primary keys because multiple users could have an account called "Checking". But then I read up on indexing and then used the mysql documentation on create index to add an index to my table. Tried to alter it again, and viola, foreign key accepted.
I hope that if anyone gets an error similar to the one I experienced that they find this blog and use the good couple of links to fix it!
On a side note:
Has anyone ever noticed that viola, when pronounced with a bit of an accent should probably be spelt walah?
Saturday, September 1, 2012
A break from BudgetBuddy for some evolutionary computation
http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-simple-substitution-cipher/#python-code
I just found this bit of code to break a simple substitution cipher. Its an extremely simple hill climbing algorithm but I'm wondering if I couldn't improve on it by using different methods. I wonder how ALPS or another evolutionary tactic would fare against solving ciphers.
I just found this bit of code to break a simple substitution cipher. Its an extremely simple hill climbing algorithm but I'm wondering if I couldn't improve on it by using different methods. I wonder how ALPS or another evolutionary tactic would fare against solving ciphers.
Subscribe to:
Posts (Atom)