Yes! Another new programming contest: Orchard Planting
On a grid you have to place trees (dots). If there are four trees in a line, you’ll get a point. But: more then 4 trees in a line is illegal. What are the best solutions for N=11 to 60 trees?
Up to now I haven’t found a good method of constructing solutions yet, but I do have a very fast scorer which is a bit faster than O(N^2). There are some ideas brewing, which I obviously won’t disclose here (maybe after the contest).
I’m looking forward to competing with you, good luck all!
Yesterday I decided to (finally) upgrade to IOS 5. This new firmware for the iPhone/iPod Touch and iPad adds a lot of new features, including iCloud, iMessage and more.
At first the upgrade seemed to be a huge success, everything worked and I loved the fact that all my apps were being updated runtime, all at once. But then I realized that all my contacts were gone! I could see all the names in the ‘missed calls’ section, but it said “No contacts” when calling/texting. I tried the “Recovery” option, but nothing seemed to help…
Until I tried this:
- Go to Settings
- Disable ‘Contacts’ (slide)
- At this moment, all the contacts on my phone appeared again!
- Re-enable ‘Contacts’
- Now iCloud asks if you want to combine the results, yes we do!
This restored all my contacts and synchronized them with iCloud. It seems that (for some reason) the initial merge with iCloud failed or something.
If you have this problem too, please let me know if this fix helps.
This year I’ll be presenting at Devoxx in Antwerp, Belgium. In my opinion it currently is the best Java conference in the world. It’ll be my first talk in English.
The titel of the talk is: What Shazam doesn’t want you to know.
During the talk I’ll be explaining how Shazam works and how you can recreate this in Java yourself. But that’s not all.. I’m also including the grand challenge of teaching everybody how the Fourier Transformation works, without going into math (I’m math-illiterate).
Wish me luck, I’m really looking forward to it!
Are you coming to Devoxx? Or do you have hints/tips for me, let me know!
A couple of months ago I’ve started using and mining bitcoins. If you don’t know what bitcoin is yet, please watch the following video:
Mining for bitcoins has become harder and harder. But as a pro, the price of the bitcoin has also increased quite a lot. Since I’ve started mining I’ve mined about 40 bitcoins (in pools). This is now worth about 9 dollars per bitcoin: 360 dollars!
Mostly I’ve used my GPU for mining, this gives me the greatest speed. I found the Diablo Miner works best in my case, I even pushed some improvements into the codebase to let it work through proxies. But since a couple of days I’ve had a bitcoin miner in Java applet form running on this website! This is currently giving me about the same amount of bitcoins. Still, it is only about 0.01 bitcoin per day. Which comes down to 10 dollar cents a day. But still this is more then I earn for ads!
I’ve removed the bitcoin applet from my main page (it can scare visitors if the CPU runs to 100%). But you can still use it on this website:
So, don’t hesitate to hang around here for a while, with this page open :-) Lets see how much bitcoins my visitors can generate!
Oh, to see the current ‘exchange rate’ of the Bitcoin, you can always view it on Mt Gox.
This weekend I wrote my first Android application: Love or Hate
The idea behind the game is very simple. When you start it the application goes online and looks at the most recent tweets containing the following phrases:
- “I love it when”
- “I hate it when”
The application now displays some user information (username/profile picture) and shows parts of the tweet. The words “love” and “hate” are removed and the user has to guess which of the two words was in the original tweet.
The backend of this is only Twitter itself. And connecting to Twitter was really easy. I’ve used JTwitter, a small API that helps searching Twitter. The code itself to find the tweets was only about 20 lines.
So that leaves me with the Android/telephone part. The first problem is the lack of Android phone. I don’t have one… But luckely when you install the Android SDK and Eclipse with the Android plugin, everything is ready, including an emulator. The first important thing I learned was to leave the emulator running. You don’t have to close the emulator to deploy a new version. This will greatly improve development speed. But as I learned when teaming up with two colleagues Ron and Jan-Kees, having an Android device is much easier still.
The next discovery was: Android isn’t at all like Swing. It mostly evolves around XML layouts. So creating a GUI feels much more like creating an XHTML web application then working with a Java GUI. Creating the GUI was much harder then I thought it would be. And this application still has a very bad GUI. It must be a disaster creating applications that run correctly fullscreen on all different devices! This is probably an area where Apple has a huge advantage offering only two different screen sizes (iPhone/iPad). After fiddling a long time I got the application looking like I could get away with it. Not great, but everything was on it.
One good thing about Android development is the use of externalized Strings. If you follow their advice and put all text in the string.xml file it becomes very easy to release the application in multiple languages. As a quick test I’ve released my application in English (default), Dutch and French.
Releasing to the Market
Of course I could have stopped here, but I wanted to release something to the Android Market. Even though the application looks ugly, it is playable and my colleagues even enjoyed playing it for a short while. The first step is creating a signed zipaligned APK file. This was very easy using the Eclipse plugin. Just click on “Export as signed Android application” and you are done. It even performs the zipalign step, in which it optimizes the APK file for the release.
To get you application in the market you need to have a Android Market account. Opening one costs 25 euro (only one time, not per application), and although I don’t think I’ll even see that return on investment, I’ve decided to do it anyway. The only thing left for me was to upload the application, including a lot of artwork (screenshots/icons/thumbnails/misc descriptions).
Adding ads from
Now that I’ve invested 25 euro’s, I decided I need some way to try and earn some money back. This actually proved to be the easiest thing in the whole project. With just 5 or 6 lines of code you can add AdMob ads in your application. You can read about it here.
After one day I’m pretty surprised: Already 350 people have downloaded the application and I’ve already earned > 50 cents from AdMob (2% ROI).
I’ve really enjoyed doing something new, and I might do more Android hobby-projects in the future. If you have any ideas, please tell me :-)
This weekend I was invited to a friends wedding. She asked if I could film everything that happened. This was basically the first time I’ve filmed something. I decided to edit everything together with some music. Here is the result:
It was a very nice day and I had a blast filming and editing everything. It is very rewarding! I really have to do this more often, but coming up with ideas to film is hard…
Yay! There is a new Virtual Source Programming Contest: “God’s Dice”
After a bit of a messy start of the contest, within hours three people had a 100% score (almost, 99.99% due to some rounding errors). This sparked James, the organizer, to change the rules a bit. Now the contest is running smoothly, the loophole is removed.
The goal of the contest is this:
- Take a cube, with all sides length 1
- Place N (9 to 88) points anywhere on the surface of the cube
- Now calculate the surface area of all triangles between your points
- Your score is: totalSurfaceArea * (smallestTriangleSurfaceArea ^ 2)
So basically you need to create triangles as large as possible, BUT, all triangles need to be large. One smaller triangle will exponentially screw up the score.
Up to now I’ve only written a scorer and a basic random searcher just to get myself on the leaderboard. Now it is time to do something a bit smarter, maybe just a better search algorithm, but I’ll probably need something a lot smarter, incorporating geometric knowledge. For example, moving one point changes all triangles involved. So we could test only these triangles to see if they improve (instead of re-testing the whole cube).
And I’ve got some other idea’s, which I won’t share obviously for the contest sake!
When browsing through the posts on DZone I noticed a couple of new Wordpress plugins. When I tried them (on my live website of course) everything failed and produced errors. And of course I didn’t do a proper backup before I started… sigh.
Anyway, I was able to login with FTP, find the broken file and fix it (PHP, blegh)! But then I started experimenting with other parts of the website and tried some different WordPress themes. I’ve had the previous theme for a couple of years now. Time for something new! What do you guys think about this new one?
The photo in the header, with the zebra’s, was taking during my holiday in South Africa last year.
Edit: The zebra picture made it look like a website of the WNF, so I changed it!
The complete (online) collection can be found here: https://picasaweb.google.com/roy.van.rijn/ZuidAfrika
For years and years I’ve also been using this avatar:
A lot of people have asked me why I’m using that avatar instead of a normal photo. I’ve been using this image since my teen years, when I had acne all over the place. I’ve just kept using it, and now people actually recognize it.
I’ve drawn that cartoon image myself, no idea what it resambles, just something unidentified creature. It was actually drawn over a photo of our family pet dog Dana. Which my parents are probably going to have to put down pretty soon. She is now very old and sick, it is just a matter of days…
Crowdflow wants to have your iPhone data, to generate pretty heatmaps!
Why am I telling you this? Because they are using my backup-data-extractor code! See their most recent blog entry.
The images they produce look very good, much better then the KML file in Google Earth!
Be sure to help them soon, because Apple is working on deleting most location-data with the next iPhone update. After that, probably the next update, they’ll encrypt the location data so it is much harder/impossible to read.
Wow, great news!
After my previous blogpost a lot of people mailed me about the usability of my ‘iPhone location data to Google Earth’ tool. It was a command-line tool, and you needed to have Java 6 installed. The main goal was to show how it is done in Java, for other developers.
The result of their effort: http://markolson.github.com/js-sqlite-map-thing/
To use it, drag the backup files into the upper part of the website. It will parse the files, locate the data and display the track on Google Maps!
The source code can be found here: https://github.com/markolson/js-sqlite-map-thing
Today I noticed the following post on Slashdot: Apple Logging Locations of All iPhone Users
And the article they are referring to can be found here
First I was amazed, how can Apple do this? But on second thought, they aren’t sending it yet to anybody, it is just something on the phone (and also on the phone’s backup). My next reaction was: I want to see my own map! But to my disappointment it only works on Apple Mac’s, not Windows/Linux.
(Re-)building it in Java
Because their code is open source and well explained on the website I decided to make my own version, in Java (cross platform!). Now, just a couple of hours since I read the article, I’ve got it working and it can be used as a base for extention. So I’d like to share the code!
Step 1: Getting the correct file
This step was the hardest part, technically. The backup Apple makes doesn’t just have all the files as they are on your iPhone. Instead they all have names like: “b4d1c79c2f5fc1da044c18d1066b80b39b575590”. They do however store the information in two files: Manifest.mbdb and Manifest.mbdx.
The MBDB file only contains information about the original files, and the MBDX file contains pointers into the MBDB file with the Hex-filenames used in the backup. So we need to parse both files to be able to connect the original filename to the Hex-filename.
Luckely somebody already did this in Python and posted it on stackoverflow. I took their idea and translated it into Java code.
When this was fully translated it could resolve all the filenames. This meant I could map the target file “Library/Caches/locationd/consolidated.db” to the hex-filename “4096c9ec676f2847dc283405900e284a7c815836”.
Step 2: Reading the SQLLite file
The contents of “4096c9ec676f2847dc283405900e284a7c815836” is just a SQLLite file. For this I decided to use SQLJet, a framework that can read(/and write) SQLLite files. Using just a couple of lines of code I had all the data I need: timestamp, latitude, longitude (and more! speed, course, confidence, altitude etc).
Step 3: What to do with the geo data?
The implementation created by Pete Warden has a nice map and timeline. But at this time I wanted to have results as fast as possible. That is why chose to just output a KML file. KML is a file format used by Google Earth and other applications.
The results are far from nice (just plain ugly) but fun: click here for a screenshot
Running the code
The above code is mainly created for developers, the resulting JAR can’t be executed. But I’m aware people will want to just have the KML file, and not go through the code. That is why I’ve uploaded an executable JAR. You can get it here: runnableiPhoneJTrack.zip (813 KB)
To run the program, extract the three JAR-files and type:
This outputs a file named iPhoneData.kml, which can be loaded for example in Google Earth.
Playing with the code
I’ve pushed my code onto GitHub: https://github.com/royvanrijn/iPhoneJTrack
Feel free to add features and send me pull requests!
Today in our project we suddenly had 10 failing unit-tests on our integration server (Hudson). Opening Hudson and looking at the first failed build I was in for a surprise. The only code changed that commit was mine!
Quickly I looked around and went into overdrive mode:
I need to fix this bug before somebody sees it!
I’m always yelling at people who break the build, and now it has happend to me…!
Looking at the SVN comment it only said: “cleaned up some code” (or something)
That isn’t very helpfull of myself…
The second scare
Then I noticed I changed only one file. The change should be contained and easy to fix. But then I had a moment of relief and scare at the same time:
- Phew, it isn’t my fault… removing empty lines should not break builds…
- But… why the heck does removing an empty line break the build!?
After looking around in the code, and the failing tests a collegue and me found the culprit: statefull static.
In our application we’ve introduced a static class called GlobalContext. In this class we keep session information, things like the MapState (we have a map, which has dimensions, view extents, etc). And throughout the code we read this information and mutate it. To unit-test the code we added setters to inject mock MapState’s into the GlobalContext.
Running all the unit tests in Eclipse always runs them synchronously, and everything is fine. But this goes horribly wrong when running Maven and/or the Hudson build. Surefire takes all test classes and runs them parallel! So when one test is busy reading the state of our static class, another test is setting different information in the same static class! This causes NPE’s and other weird values. Until now we have been lucky the tests all ran correctly, but after my commit, the execution-order appearantly changed.
The only way to fix this is removing the static-ness of the GlobalContext. Since we are also using Spring we can just put an instance of the MapState in Spring and inject that into the classes that use it. That way, when doing tests you can inject the mock-instance into the instances you are testing! This solves everything…
Even better, get rid of the GlobalContext at all. It contained a couple of instances that could easily be injected into the other objects. This makes it much clearer to see which objects depend on which other objects and makes the code a heck of a lot easier to test.
This got me thinking, in which cases should you use static? Obviously “public static final”-fields are useful. And maybe static functions in Utility classes, which have no state and only mutate data. But are there cases when you really need static state? I’ve been thinking about this for a day now, but I can’t come up with any good usecase. Do you know any? Mail me, comment below!
So for now, my new rule: Don’t use static unless you have a very good reason, and never ever have static (mutable) state!
p.s. And people, stop using SimpleDateFormat as fields, they are not threadsafe and cause weird exceptions and weird dates! I was lucky to catch one in our code today before weird errors occured.
Today somebody posted a comment:
‘Could you write a post giving more details on why you think
checked exceptions are “the embodiment of evil”?’
So here it is.
As you can see I haven’t written a post in a long time (sorry). This post is also not going to be very comprehensive. Of course I could explain everything, but I’d rather link to another site which sums it up very nicely:
Basically, I don’t want to be forced to handle exceptions. Also, having to catch checked exceptions makes code unreadable, complex and harder to change/refactor.
Of course I’m also aware that with runtime exceptions you are likely to forget to catch some exceptions, which is also very bad. That is why our application(s) catch and log all runtime exceptions and mail them to the developers. Execptions are always something very bad and should not be functional, exceptions should be… exceptions. Once they happen, all hell should break out and it should be fixed.
Follow up on the previous blogpost.
Yesterday I wrote an algorithm in Java to generate de Bruijn sequences. But I had a breakthrough after reading:
K. Cattell, F. Ruskey, J. Sawada, M. Serra, C.R. Miers, Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2)
It has an algorithm which generates Lyndon words in CAT. CAT stands for Constant Amortized Time. This means that it isn’t really constant time, but approaches it very much. Calculating the worst-case scenario isn’t worth it. For example using an ArrayList in Java. The time to do insertions is said to be O(1), and this is true…. until the array underneath needs to be resized. During this resize it’ll take some more time. So the algorithm isn’t really constant time, but constant amortized time.
This is the program I ended up with. It is very very small. One of my most beautiful pieces of code. And it even supports non-binary alphabets (use the k-parameter).
Update June 7th 2012:
I just stumbled across this interesting read: http://www.learner.org/courses/mathilluminated/units/2/textbook/07.php
The keypad example from that link can be easily calculated with the code above:
generateDeBruijnSequence(9, 5).length() = 59049 :-)
Not so long ago I encountered something called the de Bruijn sequence. For now I’ll only use this for an alphabet of (0,1), binary. But everything said here could also be applied to other alphabets. In this post I’ll describe what this sequence is, and how you can generate them, using Lyndon words.
What is a de Bruijn sequence?
Well, it is a sequence (again, in this case binary) which contains all combinations/permutations of a specific length. And it does this only once.
For example: B(2,4)
- 000100110101111 (000)
This sequence contains all possible permutations you can make in binary of length 4. The last part (000) is optional, and needed it you do not want the sequence looped. As you can see, the length of this sequence is 16. All sequences will have length 2^N.
How do you construct these sequences?
The next thing I wanted to know is how to construct these sequences. The first hit I got was from the MathWorld website. It states:
Surprisingly, it turns out that the lexicographic sequence of Lyndon words of lengths divisible by N gives the lexicographically smallest de Bruijn sequence (Ruskey).
It seems that the next step is generating Lyndon words. Lyndon words are the lexographically smallest rotation of a word. I haven’t yet found a proper way to do this (I know there are) so here is what I do:
And here is what I used to generate the smallestLyndonRotation (Java):
How does it work? Well, for example the input is: 0010.
It loops over all rotations (using some bit-masking):
And finds the smallest lexographically (0001) and returns this.
The above pseudo code will spit out the following numbers:
These are all the Lyndon words for N=4.
Splitting, reducing the Lyndon words
Now if we put the Lyndon words together we get:
- 000000010011010101111111 (our sequence)
- 0000100110101111 (de Bruijn sequence)
We aren’t quite there yet… but there is some resemblance. There is one more step left, we have to reduce/split the Lyndon words into its smallest unique part.
Lets take the Lyndon words again:
- 0000 -> 0 (4x)
- 0001 -> 0001
- 0011 -> 0011
- 0101 -> 01 (2x)
- 0111 -> 0111
- 1111 -> 1 (4x)
Results in: 0000100110101111, the sequence!
And that is it! If we’ve created the smallest possible de Bruijn sequence for B(2,4).
Here are some more sequences: