It's the first week of a new year, and it's the sort of day that one feels like saying: I'm going to do X every week for the rest of the year. Then you realize that you likely don't really. But what the hell, let's give it a shot:
I'm going to gather ideas from a bunch of places, and then write up a challenge. The problems are language neutral, so maybe I'll try some in a few different languages, or different problems in different languages.
There are a few versions of "99 Lisp/Prolog/Whatever Programming Problems" floating around, and I'll take my inspiration for the first few from them.
Goldbach's conjecture states:
Every even integer greater than 2 can be written as the sum of two primes.
Write a function that, given a even integer greater than 2, returns a pair of primes that sums to the given integer.
my @result = goldbach( 6 ); # result 3, 3 my @result = goldbach( 10 ); # result 3, 7 -or- 5, 5
First week, so I need to work out the plan. I'll post my solutions after at least 24 hours, but I'll just link to them without notes or solution details on this page. I'll link to anyone else's solution that requests it, you can also link to your solutions/etc. in comments. I'll defer posting comments that contain too much information until at least after the first 24 hours.
I'll always provide my solutions, but I'll stress that I make no suggestion at all that mine are good or completely correct. In particular, I'm planning on trying these problems in a variety of languages, some of which I am likely to suck at. (The only language I can reasonably claim to not suck in is Perl.)
Long overdue for an update. This will thus be scattershot. Our mosaic/collage article was published last month in The Perl Review, and LiveText++ paid for everyone at YAPC::NA to get a free copy with their registration bag-thing. Got a bit of author email, and at the conference a gentleman from Perl Seminar New York found me and gave me a photo collage he found in a travel magazine. (Which, used non-square photos, something I would like to support, but allowed adjacent duplicates.)
YAPC was good this year. I didn't find it as intellectually rewarding as the previous two, but I don't think that's necessarily a reflection on the conference. I'm just not that interested in AJAX, try as I might, and there were a number of AJAX talks. Also, a lot of the cooler things I have seen in previous years. MJD's talk would have been awesome if I hadn't read his book (I sat in for a while - interesting, but familiar.) As with last year, the best talk were pmichaud's Rule and Parser talks. I missed out on the APL talk, though, because I misunderstood the abstract. Ahh well. Overall, still an awesome week, well worth it. A great break, and a change of scene.
I started working on two projects at YAPC, which I've barely touched since coming back ($work has been quite consuming). They are: converting the guts of the mosaic code to use C via-XS. I figure I can likely get a hundredfold performance boost that way. Learning curve is quite interesting. Like everything over the last week, I've just been reading lightly during downtime.
The other project is to write a Huffman compressor in C++ -- part of my longer term goal to write one in ten different languages. I've done it in Perl5 and Perl6 (as much as possible). Would like to do it in PIR, then perhaps some of: OCaml, Haskell, Ruby, Python, Eiffel, Scheme. Part of me is tempted to toss Fortran in there. It's long past due for me to take a world tour of languages. Huffman compression is interesting, yet simple enough. The Perl5 implementation took an hour or two - so add in the learning curve of a new language, and you've got a good sized project. Solving the same problem multiple times has the upside of allowing direct comparison of approaches. I'll be careful to try to approach the problem fresh each time, so that I'm not writing Perl in Haskell, etc.
I have refactored quite a lot, and allowed the colourspace to be selected at mosaic build time. This lets me use the same tile index file and experiment with various colourspaces and weightings without rebuilding the index. I've built up the corpus to about 80 000 tiles, and since the vectors are held in RAM, I needed to move off my laptop and onto a machine with more RAM.
Here is a mosaic from a photo I took on Georgian Bay:
Here is a close up of a transition area (sky -> trees -> water):
The repeat limit was manhattan distance of 40, the build order was shuffled. I used the YCbCr colourspace, which I think performs way, way better than HSV/HSL. YCbCr is, I think, the 8-bit version of YUV, and I think that it does a good job of mapping colour perceptually. It gives two components to chroma, rather than HSVs one, which makes for a clean color match. I found that RGB tended to favour blue disproportionately... in fact primaries seemed to match more strongly. The YUV/YCbCr matching gives a softer, more 'real' and slightly more impressionistic feel, I think. I intend to run this again with just RGB, for a straight comparison of the two.
HSL/HSV also represent chroma as a loop... which means that at the 360-0 boundary, the maximum span, there is great similarity. This resulted in poor matches near the boundary. The two dimensional chroma space of YUV/YCbCr place perceptual extremes at the edges, with no wrapping. This means that matches appear good throughout the perceived colour gamut. I'm not a graphics expert in the least, so you'll excuse some heavy misuse of jargon and some similarly heavy glossing.
For those who want the full 4.3MB bomb, here is the full-size version (3750x6450 pixels). Be forewarned, I just selected the images based on license characteristics, I didn't review all 80k tiles for appropriateness, etc.
I think that the fine detail improves considerably as I add to the corpus, but obviously that is RAM limited. Each tile requires an in-RAM 75 element array to represent the vector. It also extends the runtime of the match linearly... this mosaic ran overnight, for about 9 hours.
I didn't mention this earlier, but my article on Sudoku Generation was printed in the Spring edition of The Perl Review. The first page of the article is available in PDF And of course the whole thing is available to download for subscribers. For subscribers only, the actual code from my generator is posted on the TPR website (password required).
I haven't gotten my physical copy in the mail yet, though. I also haven't gotten any author email telling me I'm brilliant or that I missed something obvious. So that is half good news, half disappointing.
I've sort of stalled on my Sudoku Grader project... I did complete the Locked Candidate detector, and flesh out the outer framework of the Grader, but I haven't gotten much farther. I might pick it up again in a month or so. I'm trying to follow AudreyT's approach, and be productive in hobby-coding by optimizing for fun. The big downside of that is that when you hit a patch of boring refactoring, you tend to stall.
Update: When I got home, it had arrived. It looks pretty good, I think.
I need to (and plan to) launch this blog in earnest. I thought that I would quickly mention that Daniel and I have been working on a photo mosaic generator in Perl with GD, using the Flickr API to harvest thumbnails for the corpus. I'll try to doc things out here, but Daniel has posted examples and some explaination on his LJ already.
Here's my favourite example so far:
I am most of the way through the HSV chunk that he mentioned... I am including the abilty to weight the HSV so that you can choose which component is more important.
more added later:
Someone on Daniel's blog suggested YUV instead of HSV:
my $y = 0.299 * $r + 0.587 * $g + 0.114 * $b; my $u = -0.147 * $r - 0.289 * $g + 0.436 * $b; my $v = 0.615 * $r - 0.515 * $g - 0.100 * $b;
That actually has the additional benefit of being easier to calculate.
I'm pretty torn about my system of weighting dimensions of the colour space. I'm curently scaling my vectors in those dimensions when I create the vectors, rather than weighting differently in the vector distance calculation phase. That makes loads of sense, since it avoids millions of calculations... but the way I have things set up, it applies the scaling at tile index time, rather than index load time. I'm thinking that I should just always index in RGB, then transform the space and scale the vectors during the pre-matching phase (what Daniel and I have been calling phase 2a).
Okay, I'm not torn anymore. That last paragraph untore me.
