Yet again I've java in my studies at ITU. The current assignment Peter, Thomas and I are working on is to implement an assistant that helps a user solve the classic N-Queens problem using Reduced ordered Binary Decision Diagrams (RoBDDs or simply BDDs).
There's many(!) ways to solve that problem, but using BDDs does seem like a very intriguing approach. The only problem: it requires a BDD engine. We could of course write our own (and actually I'm currently working on that), but in the assignment we were given, there was actually a fully functioning BDD library ready for us to use. Only, it was in java... (NOTE: I don't have any problem with java and I'm not religious in any ways, but usually .NET is my weapon of choice).
"No problem, we'll just use J# to handle it like last time" was the initial reaction.
But, alas, the library was already a compiled jar, no source included. Naturally we could get all the source from sourceforge and port it to J#, but the time seemed right to try a new clever approach!
Luckily Peter found the right solution: Enter IKVM! IKVM is a great set of tools to interact between java and .NET and it works like a charm.
The two main tools is a command-line program that allows you to run compiled java files in .NET instead of java's virtual machine. The other tool that proved to be really useful to us, will allow you to take a JAR and transform it into a .NET DLL.
All I had to do was to call it command-line with the name of the JAR file and the name of the .NET output file, and run it - and in no time I had a working .NET dll that I could reference directly in my .NET projects.
In order for the referencing programs to work though, it's important to have two of the IKVM dlls' included in the "bin" folder or in the GAC (namely the "IKVM.GNU.ClassPath.dll" and "IKVM.Runtime.dll").
Great work, IKVM guys. Keep doing your magic!
And the programming assignement? Well, here is how far we've gotten so far. Keep in mind that it's work in progress. After the hand-in deadline I'll make a new post about how we did it.
I'm also considering trying out other of the known approaches to solve the same problem and comparing them. Drop a comment if you'd be interested in knowning what works best :-)
Thursday, April 26, 2007
Monday, April 16, 2007
DPLL in C# - Satisfying problems in CNF
Time for another AI post! These last couple of weeks I've been working with two fellow C# guru's, Peter Thygesen and Thomas Gravgaard on an assignment in our AI class, on implementing a couple of specific parts of the DPLL algorithm, such as the methods for choosing split symbols, finding unit clauses and identifying pure symbols.
"What's DPLL good for?" I hear you cry...Well, it's simple really - or actually it isn't all that simple but I'll try to explain it anyway.Suppose you have a boolean statement in CNF (conjunctive normal form) and you want to test if it's satisfiable, that is - if a certain configuration exist, that will make it true - then you can run the DPLL algorithm to find out. The DPLL basically searches the solution space, but during the search uses the unit-clauses and pure symbols to prune the search space.In other words (and hopefully more understandable words) if you have a problem that you can formulate as a boolean problem (A and B or C implies D), then you can change that formulation into conjunctive normal form ((A or B or C) and (A or D or E) ... ) and when thats done you can determine if it's actually possible to assign values to the variables that will make this true.The way the algorithm works is basically to pick a symbol (=variable) and assign it true or false, and then for each options recursively call itself until all variables are assigned. In order to minimize the search space it uses a couple of simple rules to shortcut through this search, like finding out which clauses only contained one unassigned symbol. It's also very important in what order it assigns variables.
Another challenge in this assignment was that the code provided for the assignment that we should use as a basis for our work and for testing was all in java (typical university assignment). We're all C# people but too lazy to rewrite everything in C#, so luckily we got the java-code working in J# and were able to base our code on it anyway (and I wouldn't be surprised if our execution performance is higher that if we had used java).
Read our project here.
"What's DPLL good for?" I hear you cry...Well, it's simple really - or actually it isn't all that simple but I'll try to explain it anyway.Suppose you have a boolean statement in CNF (conjunctive normal form) and you want to test if it's satisfiable, that is - if a certain configuration exist, that will make it true - then you can run the DPLL algorithm to find out. The DPLL basically searches the solution space, but during the search uses the unit-clauses and pure symbols to prune the search space.In other words (and hopefully more understandable words) if you have a problem that you can formulate as a boolean problem (A and B or C implies D), then you can change that formulation into conjunctive normal form ((A or B or C) and (A or D or E) ... ) and when thats done you can determine if it's actually possible to assign values to the variables that will make this true.The way the algorithm works is basically to pick a symbol (=variable) and assign it true or false, and then for each options recursively call itself until all variables are assigned. In order to minimize the search space it uses a couple of simple rules to shortcut through this search, like finding out which clauses only contained one unassigned symbol. It's also very important in what order it assigns variables.
Another challenge in this assignment was that the code provided for the assignment that we should use as a basis for our work and for testing was all in java (typical university assignment). We're all C# people but too lazy to rewrite everything in C#, so luckily we got the java-code working in J# and were able to base our code on it anyway (and I wouldn't be surprised if our execution performance is higher that if we had used java).
Read our project here.
Friday, April 13, 2007
Just overwhelmed
Since Monday I've been practically flooded with interesting job offers. It's quite a wonderful situation to be in - to be able to pick and choose like this (and potentially to have 5 months with full pay to make a selection in). I've even considered using these next months to work on my own, blogging and building a second-life empire - or perhaps make my own little code-piece shop online?
It's overwhelming and a little bit scary. Whichever job I choose will probably be interesting and fun but it will also mean to not go down all the other interesting roads. I wish somebody had implemented Save & Load features in life, like in computer games. Imagine hitting a button, saving your state and then always being able to restore it later. That way all options could be carefully explored and enjoyed. Ah well. I haven't found that button yet, so I suppose I'll have to make a choice sooner or later. Until I do, more job offers are welcome.
I finished writing a CV (right now it's in Danish, English translation is on the way). See it here.
It's overwhelming and a little bit scary. Whichever job I choose will probably be interesting and fun but it will also mean to not go down all the other interesting roads. I wish somebody had implemented Save & Load features in life, like in computer games. Imagine hitting a button, saving your state and then always being able to restore it later. That way all options could be carefully explored and enjoyed. Ah well. I haven't found that button yet, so I suppose I'll have to make a choice sooner or later. Until I do, more job offers are welcome.
I finished writing a CV (right now it's in Danish, English translation is on the way). See it here.
Tuesday, April 10, 2007
Looking for New Adventures
It's been a wonderful easter, where I didn't get any of the programming projects done, that I had hoped I'd get done.
But no worries... My employement situation had an interesting shift today which means that I now will have a lot of free time to blog, program my personal pet projects and write a good CV.
This also means that in a while I might be tempted by interesting job-offers. Here's a short list of some of the things I'm looking for in a company:
I'll post a CV, when I have one ready (havn't used it for the last 6½ years, so it probably needs a small update).
But no worries... My employement situation had an interesting shift today which means that I now will have a lot of free time to blog, program my personal pet projects and write a good CV.
This also means that in a while I might be tempted by interesting job-offers. Here's a short list of some of the things I'm looking for in a company:
- Interesting work! This is by far the most important bullet. I love to do research and explore cutting edge technologies. But I might want to avoid those "maintain this old-fashioned asp based finance system" jobs.
- Innovation, Innovation, Innovation! I have a lot of creativity and I want to use it. I want to be in a company that has room for my ideas, and that isn't so big that it's forgotten how to be innovative.
- ISV. Independent software vendor sounds really good to me.. I don't feel like making those big consultancy bucks anyway. It's nice to work on a product suite where you have a lot of co-influence on the shape of the product, instead of a lot of small projects with angry customers barking at you all the time. But of course, if the right offer appears I might consider it anyway.
- And of course: friendly colleagues, good atmosphere, right salary, benefits, education, etc. is also very(!) important.
I'll post a CV, when I have one ready (havn't used it for the last 6½ years, so it probably needs a small update).
Tuesday, April 3, 2007
Back from Budapest
After spending a nice relaxing week in Budapest, seeing the sights and enjoying the spa's, I'm back in full force. One working day left, and then a loooong eastern which will be an excellent time to blog and code a bit more than what has been usual for the last couple of weeks.
I hope to get somewhere with the Poker Bot tournament, work on the DPLL group-assignment I'm in and perhaps also play around a bit with BDD's. For those who don't know what a BDD is, I'll post about it later. Until then, check out these really cool demo's at Configit Software, an ITU startup that uses BDD's in real life!
I hope to get somewhere with the Poker Bot tournament, work on the DPLL group-assignment I'm in and perhaps also play around a bit with BDD's. For those who don't know what a BDD is, I'll post about it later. Until then, check out these really cool demo's at Configit Software, an ITU startup that uses BDD's in real life!
Subscribe to:
Posts (Atom)