So, I haven't posted my solution to last weeks puzzle, for a couple of reasons. The big one is that my solution doesn't work yet. I successfully solve a problem, but on closer inspection, it was quite a different one from the one that I posed. And in fact, I can't solve the problem I posed the way I approached it. Thus I need to start over. And I will. But I can't miss this weeks challenge, or I'm hosed.
This week, I'll going for something slightly simpler, though it has virtually infinite room for expansion and optization.
Write a pattern matching engine. Given a pattern and a string, return a boolean match or no match response:
matches = pmatch( pattern, inputstr );
The pattern syntax can be anything other than straight substrings, though you must start by selecting a subset of the PCRE syntax. Start with the '*', '+' and '?' quantifiers, together with character classes and alternations. Ignore capturing, but include grouping. That set of features is probably the minimum set to provide useful matching facilities, but it's not so overwhelming as to require enormous amounts of code. Add to those features as long as it remains interesting.
Some random notes:
It may seem foolish to work at solving a problem so widely and commonly solved, but this is in fact a challenging problem with lots to think about. If you work with regular expressions every day, take this opportunity to look at them from the bottom.
I had fun doing last week's challenge, no other solutions sent or linked yet, but there's no timelimit; I'll accept entries indefinitely. Other program notes: I think that I'm going to try to post challenges on Monday, my solutions on Thursdays.
The Knight's Tour is an old math problem: given a standard chessboard and a single knight, can you move the knight such that you land on every square exactly once. The knight must move as per normal chess rules, you can start and end on any square. A slight variation is a closed tour, where the knight ends up one legal move away from the starting point.
The challenge is to produce a program (in any language) that returns a solution to the puzzle.
None of the following are problem requirements, but worth considering:
Some notes, none of which are promised to be helpful, but have occurred to me as I posed the problem:
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.