Just another lambdabananacamel,

Every year or so I come back to the problem of writing a crossword puzzle compiler/player. I think Javascript would be the most promising for a web-based player, though I've given it a go in Java and Perl too. Modeling the problem is interesting in an Object Oriented language - I would find myself getting bogged down with "Lines" and the similarities between rows (Across) and columns (Down). I have a suspicion that OO Roles might be a more expressive way to model this. Anyway, given that I've not been writing much about Haskell ¹, this is a good time to redress the balance.

In the OO implementations, Cells would refer to the "Light" (group of adjacent cells running Across/Down) that they're in. And the Light would of course refer to the cells... this idea filled me with terror in Haskell, as it involves "Tying the Knot", which seems terribly clever and confusing. As it happens, you can often get away with having mutual references in Functional Programming, as they just spontaneously turn out not to be necessary. So far, this seems to be the case, though I think that if I take it to the point of navigating the grid from a UI, I may need an explicit structure to manage this, like a zipper.

This is a "literate Haskell" post. You should be able to save it as "crossword.lhs" and run it with runghc or ghci (calling the main function to test it). We start off with some imports: the List and Char modules (which I've naughtily not specified) and the handy join function to flatten a list.

> import Data.List
> import Data.Char
> import Control.Monad (join)

They say that much of the work in Haskell is defining the types. Direction is an Enum for the direction of a Light. Cell is either a Block (a black square) or a Cell (either blank, or already filled in). I guess I could model Block | Blank | Cell but don't yet see an advantage to that.

> data Direction = Across | Down
>     deriving (Show, Eq, Ord)
> 
> data Cell = Cell  (Maybe Char) Coord
>           | Block              Coord
>     deriving (Show, Eq)
>
> type Coord  = (Int, Int)
>
> coord (Cell _ c) = c
> coord (Block  c) = c

Directions can be sorted (which may come in useful for showing Across clues before Down ones), and this can be done automatically by deriving Eq and Ord. But how would we sort a Cell? We'll do it by the (x,y) coordinates, which means I can't use automatic derivation. Perhaps I could swap the order of arguments and still use that, but for now I defined a custom compare.

> instance Ord Cell
>     where compare l r = compare (coord l) (coord r)

Lights (distinct from Clues, which may be spread over 1 or more Lights) are a list of cells in a given direction. (It would be nice to specify that the cells really are contiguous, not sure if this is something that fundeps would be useful for?)

> data Light     = Light [Cell] Direction
>     deriving (Show, Eq, Ord)
>
> -- we'll sometimes want to know the first cell in a Light:
> headC (Light (c:_) _) = c

Of course Lights are numbered... but with the algorithm that I'm using, we don't know the number (like 5 Across) at the time we create it. I created a new type, LightN, but perhaps I should have modeled with a Maybe Int instead.

> data LightN    = LightN Int Light
>     deriving Show

Now we need some test data. I started with a grid from the wonderful Araucaria, Cryptic Crossword No. 24298.

> grid = textToCells [ 
>     "TRIPOD#        ",
>     "# # # # # # # #",
>     "PARSIFAL#RESCUE",
>     "# # # # # # # #",
>     "###            ",
>     "# # # # # ### #",
>     "ANNA###        ",
>     "# # # # # # # #",
>     "        ###PARE",
>     "# ### # #U# # #",
>     "         S  ###",
>     "# # # # #E# # #",
>     "      #INFERNAL",
>     "# # # # #U# # #",
>     "FRAGMENT#L     "
>     ]

We're going to want to output the grid, lights, and other objects, so let's define some functions to do that.

> showCell (Block _)         = '#'
> showCell (Cell (Just c) _) = c
> showCell _                 = ' '

> showLightN :: LightN -> String
> showLightN (LightN n l@(Light cs d)) =
>        show n ++ " " 
>     ++ show d 
>  -- ++ " " ++ show (coord $ headC l) 
>     ++ ": "
>     ++ show (map showCell cs)
>     ++ " (" ++ (show $ length cs) ++ ")"
>     

Similarly, we want to parse the list of strings above into a list of crossword cells. textToCells threads the row and column number with every character in the grid by zipping the list with the infinite list [1..], which I think is quite cute, though there are no doubt more elegant versions (list comprehensions?)

> charToCell :: Char -> Coord -> Cell
> charToCell '#' = Block
> charToCell ' ' = Cell Nothing
> charToCell  c
>     | isAlpha c = Cell (Just c)
>     | otherwise = error $ "Invalid character '" ++ [c] ++ "'"
> 
> textToCells :: [[Char]] -> [[Cell]]
> textToCells                     = zipWith  makeRow       [1..] 
>     where makeRow  row          = zipWith (makeCell row) [1..] 
>           makeCell row col char = charToCell char (row,col)

But working out what cells are is the easy part! We now want to know which cells form a light — i.e. groups of more than 1 non-block cell in either direction Across/Down. To get data for both directions, it's easiest to run in two passes, one in the normal direction, the other transposed. (I did consider trying to do both at the same time, but it hurt my brain: a one pass solution involving magical fumplicative arroids or somesuch is left as an exercise to the very clever reader).

> lights dir grid = concatMap 
>                     (flip lightsInLine dir) 
>                     $ rot dir grid
>     where rot Across = id
>           rot Down   = transpose
>
> lightsInLine :: [Cell] -> Direction -> [Light]
> lightsInLine cells dir = 
>     let l  = filter isMultiCell 
>                $ groupBy areCells cells
>     in  map (\c -> Light c dir) l
>
> areCells x y = isCell x && isCell y 
> isCell (Cell _ _) = True
> isCell  _         = False
> 
> isMultiCell (x:y:_) | areCells x y = True
> isMultiCell _ = False

So... where have we got with all of this modeling? Well, we can now find all the Across and Down lights. But then we'll want to number them. To do that, we'd have to sort them (by the coordinate). Across and Down lights can have the same number (like 5 Across and 5 Down in our example grid) so we want to group by lights that have the same head cell. Then we can thread the light number again, using the zipWith ... [1..] trick:

> allLights = join $ zipWith (map . LightN) [1..] gs
>         where gs = groupBy eqHead ls
>               ls = sort $ (lights Across grid)
>                        ++ (lights Down   grid)
>               eqHead l r = (headC l) == (headC r)

And finally, we can see the result of all the hard work, with a list of all the lights, and their current (partial) solutions:

> main = mapM_ putStrLn $ map showLightN allLights

Obviously this is only a start on the problem. For modeling, we now need a concept of a Clue (Clue String [Light]) and a solution - should the solution belong to the clue? or to the [Light]s that it's made up of. How do we link the answer grid (where the lights contain the correct characters) with the play grid, which contains the current letters that the player believes to be right? And how do we update the cells, lights, and grid while playing (or creating) a crossword?

Suggestions on these questions, and improvements or advice on the current code are greatly appreciated!

---

1. I had a complaint about this from a Planet Haskell reader: and though the FAQ does suggest that it's ok, or even encouraged to write about other things, perhaps I should also write a little about Haskell... ;-)

   back

First of all, a disclaimer: I know "larsen" (Stefano Rodighiero) not just as an ex-colleague (he is one of the most respected senior programmers at DADA in Italy), or through the Italian Perl community, but also as a good friend. But of course, those were excellent reasons to look forward to his book: an introduction to Perl in a pocket series of roughly the same format and price point as the UK Teach Yourself series. The community's perl.it website lists various resources including tutorials and books in English and Italian, but till now they haven't recommended an introductory book in Italian. I think that could be about to change.

Modern Perl good practices

I've seen a lot of criticism of introductory books for propagating the kind of cowboy Perl that gives the language a bad name. Right from the first chapter, Larsen introduces:

• CPAN for installing modules
• make test
• the Perl Community: where to find out more, get help, and improve your skills
• strict and warnings
• perldoc

He continues with this throughout: every chapter finishes with a list of PODs and other resources to learn more. Variables are my'd and code is well formatted. Small sections going into good practices are dotted strategically throughout the text, rather than consigned to an unread appendix: for example, commenting and POD are detailed by page 55.

Teaching

The first half of the book, Chapters 2-4 cover basic string and array operations, control structures (with foreach covered before C-style for, references and subroutines, scope, context, subroutine references, map/grep (with an example on Schwartzian Transform) and exceptions. The book also covers Perl 5.10 features like say (which it uses throughout) and given/when. This is obviously quite a whistlestop tour, but is clearly structured, with concepts introduced as they are needed, and with explicatory diagrams where helpful. Chapters 5-6 introduce packages and OO programming. While it's a short overview, it covers the bases with inheritance, DESTROY, AUTOLOAD (though is that a good thing? ;-), and some good practices like Module::Starter and Class::Accessor. Chapter 7 is a nice 25-page section on Regular Expressions with helpful diagrams, examples and reference tables. Pleasingly, he finishes off by mentioning Regexp::Common and cases not to use regexes for (HTML::TokeParser) Finally, Chapter 8 takes us through Perl and the outside world. This is a mere 10 or so pages on file system tasks, and the same again split between CGI and GUI programming. Given the importance of Perl for sysadmin glue and web programming, this could be considered the book's principal (only?) weakness. On the other hand, trying to teach these disciplines in a short introduction would make it a completely different book, and would have left out the excellent introduction to the core matter. The interested reader who has absorbed the contents of the book will have a much better base to learn the next steps in whichever direction they need to go, so on balance, this is very much the right decision. But it doesn't quite stop there. The appendix lists many main books like the classic O'Reilly Camel Book Conway's Object Oriented Perl, Dominus's Higher Order Perl etc. It also gives a short guide to how to choose between the multiple modules available on CPAN, and a brief overview of some useful modules and frameworks: (Catalyst, TT etc.) Even if you disagree with some of the featured choices (I did ;-) at least you know that the student has enough pointers to learn better for themselves: as if to confirm that point, the book ends with a 2-page reminder on the Perl community and the resources it offers.

Look and feel

Briefly, the typography is excellent, very clean and easy to read. The diagrams are well laid out, and my only minor quibble are the little grey icons which are unattractive and hard to distinguish from each other (they each have a different symbol and apparently have distinct meanings, but I ended up parsing them as "interesting note"). There are some oddities with punctuation that lead me to suspect the editorial proofreading may not have been especially thorough? Likewise, there are some minor errors in the diagrams on regexes, which is a shame as those are otherwise very useful for a learner.

Conclusion

I think it's excellent news for the state of Perl in Italy that this book has been published. For a mere EUR 7.90 an Italian reader can now pick up a compelling and thorough introduction to Perl in their native language. Apparently it is in general release in Italian bookshops, otherwise you can buy it online from one of the links on the Pocket Perl site.

On Saturday I gave an updated version of my Functional Pe(a)rls talk. This time around I cut the whistlestop tour of builtin FP techniques in Perl (map/grep/join) and added a section on Monads - what they are and how to implement them. I'd originally worried that the slides might have been over-academic and hard to understand, but luckily Dave Cantrell had presented closures that morning, and lots of people had spoken about the cool and evil things you can do with Devel::Declare. Also the Monad talk did handwave over some minor details (like munit/join :-) and it helped to play a little for laughs - I should probably subtitle the talk

"Imperative programming... in Pure Perl!"

I think the talk went down well and I also won a book (of maps of Old London Town) from the nice people at Nestoria for "Best Topic", which I guess means I can refer to it as an "award-winning" talk.

I've uploaded the slides of my award-winning talk on functional programming in Perl to slideshare ;-)

The conference

Mark Keating, the Shadowcat team, all the volunteers, sponsors, and Josette's O'Reilly bookstall, and of course the speakers, delivered a fantastic event which was not only free, but even had free beer! (Courtesy of Venda and Shadowcat, we drank the pub out of Witchfinder ale within 30 minutes, but the free booze was flowing till around 10pm, which was incredibly generous and appreciated -- less so the following morning).

It was great to see some quality talks, a uniformly excellent lineup of lightning talks (including one which broached Italy's candidacy for YAPC::EU::2010), meet up with old friends and colleagues, and put some more names to nicks and faces.

Update 2009-02-06: Mark uploaded the videos from room 1 this week, and today they're up on yapc.tv, including Functional Perls. Yay, mdk++, andy.sh++! The sound is better than many conference videos, so you can hear me um and er in high quality, but the slides aren't included on the video, so you may wish to follow along on slideshare or download the slides.

I'll be at the London Perl Workshop tomorrow: it's a free 1-day conference, and was lots of fun last time I attended. I'll be talking on "Functional Pe(a)rls", an extended and updated version of the talk I gave at the Italian workshop, and I'll be discussing Sub::Curried and Monads in Perl. See you there ;-)

I've never studied Python, but I'd quite like to at some point in the future. It seems very much like Perl with a different set of design criteria. Yeah, there are differences, but compare with C, Lisp, COBOL, and you can see why Perl and Python are clustered together in the "P languages" (Perl/Python/P^HRuby etc.)

Actually, that's one of the main reasons I've not expended signifant effort into learning Python - I can hurt my brain far more by trying to learn C or Haskell. But I'm sure it would be a good thing to do at some point. Here are a few notes on first impressions: these are just that, impressions, and may not be factually accurate: if you want to know full and correct details about Python, there are many excellent blogs that will clarify.

2008-09-25 Thanks for the excellent comments, I'll fold in corrections below!

Whitespace

This is the one wart that Perl programmers fairly consistently bring up. I'm coming around to the idea that it's a good idea, but I do think that:

1. it's not entirely necessary, as most good code is indented anyway
2. Haskell does it better, with some excellent whitespace inferencing rules, but the possibility to drop back to an explitly { braces; and; semicolons } style if you need it

Things that you miss out on include multiline strings (2008-09-25: Bill Mill points that """syntax""" does indeed allow multiline strings, thanks), and multiline well, anything, for example lambdas, but that's OK because...

Functional Programming

Python has likened to an easy version of Lisp, and it has the same kind of functional goodies as Perl. At some point Guido wanted to remove (I think) reduce, grep, map from the core language, and there was much gnashing of teeth. I think he backed down, but the idea that he suggested it is interesting. He also wanted to get rid of lambdas, which seems utterly crazy, as even the Java people are now thinking about adding them. But lambdas are still deprecated, and are considered not the "pythonic" way of doing things. Hence they are discouraged and restricted to single lines. Hmmmm.

(2008-09-25: Bill Mill points out that map remains; reduce got moved to Standard Lib, as comprehensions already do the right thing; and grep doesn't exist. Is that called "filter" in Python? Of course comprehensions can already to map/grep too)

On the other hand, python has list comprehensions which work equally well on lazy generators! Very nice indeed. It also has a much fuller destructuring bind than Perl's (which only works on single-level lists). So some good, some bad, and some interesting syntax and features. I doubt there's a clear "winner", some more discussion on Perl/Python (via Lisp of course) in Paul Graham's Revenge of the Nerds post.

Oh, and Python has continuations! With a builtin yield command. Perl has the Coro module, which is a fantastic piece of work, but rather complicated with confusing documentation. The yield command itself is in Coro::Generator but it has a number of limitations, like not being able to clone a continuation. There was a lovely post on creating monadic "do-notation" using continuations only, and I ported it to Perl with much swearing only to find that though it worked great for simple monads, it failed utterly for the List monad (important as it's what list comprehensions are built on) precisely because of this. Apparently the Perl internals don't really mesh with this, so it's unlikely that we'll be getting it for Perl 5 any time soon. Point to Python.

(2008-09-25: dolio points out I'm confusing generators and coroutines. Yup, I do that, sorry! I think one can be implemented in terms of each other (and vice-versa?), and that some literature does also blur the distinction, but could be wrong about that too? And yes, Ruby has callcc, but apparently the Monad example I was reading can't be easily ported to Ruby because the continuations/coroutines/thingies generated by yield aren't clonable)

OO

Python's OO looks serviceable enough, and method prototypes and so on are nice. Perl is really catching up here though with projects like Moose, which truly does deliver on being a "postmodern object system". Sure, the syntax could do with some work in places, but the new buzz around Devel::Declare and Method::Signatures means that this is coming on well too.

Will on Geekup posted some nice examples of "declarators on attributes", which I think are similar to lvalue tied methods, but look rather better designed. (From Damian Conway's talk Contextual::Return may fix the problems Perl has with this kind of nice syntax. I say may as with Damian's talks it's hard to tell whether they truly are a massive advance in usability and functionality or crack-fueled insanity). Actually, declarators deserve their own section:

@Declarators

These are really nice syntax for modifying subroutine declarations. Of course, there's nothing you can't do in Perl, but it's prettier than direct symbol table hacking. And less hackish than bloody :attributes. Still, nothing a bit of Devel::Declare or similar sugar couldn't fix :-)

But talking about declarators, I have to ask:

Is Python really more readable?

One of the Python slogans is something like "executable pseudocode", as if you can just write out readable summaries of code which are readable but compile. From the python examples I was looking at (admittedly, these may have been complex, with features like @declarators) I couldn't make head or tail of it. Now I'm not trying to suggest that Python is naturally unreadable, or that Perl is naturally readable. But I would say that

1. If you know language X but not language Y, then you may find X more readable than Y.
2. This may hold even if X happens to be Perl, or Y happens to Python :-)

This may be a good time to pimp my Readable Perl slides up, for those people that insist on joking that the phrase is oxymoronic.

Community

Both Perl and Python communities seem to be vibrant, productive (of modules, apps, blogs, and conferences), and to have a mix of helpful and friendly, and snobbish and trollish. So pretty much situation normal for perhaps underrated "scripting" languages :-)

Some differences I've heard mentioned include (with no figures or such to back them up...):

• Python conferences are apparently full of people talking about cool projects they've done. At Perl conferences, people often talk about syntax and technical problems and... oh, yeah, I used this to do this project but I don't have time to talk about it now...
• I've very rarely heard Perl programmers talk badly about Python. Well OK, we always whine about the whitespace, but I know that jerakeen and Dean have said generally positive things about it. I've had Python people telling me bad things about Perl, despite not knowing anything about modern Perl, which I think is fairly silly, unless they are doing it only for postmodern ironic reasons (which is an excuse apparently).
• Of course this may be because Perl programmers pick on PHP and Java instead. But that's OK because we're being postmodern and ironic.
• I have an (utterly uninformed) hunch that Python conferences are better attended, but that this may be in part due to there being fewer of them.
• Python has Guido. Perl has @Larry (in the plural). (I'm not sure that this isn't overrated, $Larry probably gets the deciding vote).

There is a constant meme that Python is somehow more "modern" than Perl. This is almost never qualified, I remember in this interesting book on programming language design that it was mentioned that the fact that Python's regular expressions lived in an external module was a more modern design that Perl's, which had them as builtins. Perhaps Perl not building in support for declarators and list comprehensions is more modern too? I'm sure if I say this often enough, it'll be a good substitute for actually making sense :-)

But Python does seem to get more buzz, with things like Google's AppEngine supporting Python before Perl. Hey ho. I still think that there are many more Perl jobs going, for what that's worth.

Modules

CPAN is a big advantage for the Perl community, and I believe that Python's module ecosystem is somewhat less complete. But it looks very impressive nonetheless:

Off the top of my head, there's Twisted, Python's equivalent to POE; Django (Catalyst); and PyGame (possibly comparable to SDL_Perl?) as fairly high-profile complex libraries that show, to be honest, that both languages are pretty healthy with regards to module support.

(2008-09-25: Bill Mill points out PyPI link, and admits it's "still no CPAN, but it's coming along", which is more or less what I was trying to suggest ;-)

So...

Python looks like a great language, with many of the same strengths of Perl. If you've looked at Perl and it didn't really click, try Python. And vice-versa. If you've not used a dynamic language and want to try, then use one. Honestly, you'll love it. (And if you don't, try the other one. Or Ruby. Or go crazy and learn Haskell.)

I went to my 3rd Italian Perl Workshop, IPW2008 at the end of last week. It seems to have been the most successful Italian conference to date, and it certainly succeeded at being both a national workshop and an international event. It hadn't occurred to me before that these are actually two orthogonal aims.

An international event

The organizers managed to pull out all the stops with sponsorship. There's always various random swag, books for the auction, cheap/free use of rooms from the University. And in recent years, the conference has had just enough money to be completely free of charge, even with its (excellent) coffee and biscuit break. But this year, the "platinum", "gold" and "silver" sponsors contributed enough money to pay travel and accomodation for speakers of international calibre:

• Tim Bunce
• Rafaël Garcia-Suarez
• Marcus Ramberg
• Matt Trout

Other international attendees included Michel "XML::Twig" Rodriguez (though he lives in nearby Lucca and spoke in Italian); Bruno (a Pole who lives in Spain... or Amsterdam or something... I'm confused, especially as to why he attended the Pisa workshop :-); a bevy of Norwegians from Opera's HR team; and another Norwegian expat who was completely unrelated; an Indian postgrad studentessa; and me, I guess.

Hmmm, 4 Norwegians, 3 Brits, 2 French. I wouldn't have expected quite that many Norwegians, largely because I'd never have thought that Opera, based in Oslo, would have been recruiting at a workshop in Italy. But it's on their "world tour" as several of the core Perl team for their social network are Italian. And they really capitalised on the opportunity, sending 3 perlisti and 2 HR, all of whom were very visible throughout, sponsored a competition for a Wii, and hired an interview room for recruiting sessions during the workshop. I'll be really interested to see how successful they, and the other recruiting companies (Wind, Dada, A-Tono) have been. It's very positive that Italian companies using Perl are getting involved like this.

Oh, the talks! Matt spoke about Devel::Declare, which rocks. I finally got to see Tim Bunce's Perl Myths talk in the flesh, and also his demo of Devel::NYTProf which is so beautiful it makes me want to cry. Marcus introduced Catalyst, and I missed the others, for various reasons.

A national event

There's a danger that the focus on the exotic allure of geeks arriving by luxurious Ryanair jet could distract from the fact that this is also the event for Italian programmers. Having two tracks, and a general policy of not scheduling 2 "guests" against each other worked very well here.

The first day's Italian talks concentrated on beginner and intermediate topics, including dakkar's tutorial and regex theory, and Flavio Poletti on writing IRC bots, though there was some crossover, as rgs also presented on coding style in English. The perl.it guys are really keen on appealing to new programmers, which is fantastic. (There was a little gnashing of teeth about how the recent Pycon in Italy had even more attendees despite being a younger conference.)

Not that it was all for beginners: emi spoke about Linux wifi captive portal setup; emazep showed a fantastic UI for constructing complex DB queries, running on Catalyst with jQuery; grubert presented a news portal prototyped in 2 months with the awesome power of CPAN; [LucaS] finally presented his workgroup software IGSuite, yay! Cosimo spoke about scaling and the Dogpile Effect at Opera. Sadly I missed the "GUI track" completely with Mattia Barbon, the author of WxPerl, and nids talking about Perl/TK. And finally I had to give an emergency talk myself to fill in a gap (went OK, trailed off towards the end).

More info

IPW2008 slides and photos are already being posted, and larsen is collating blog posts to link to from the main perl.it page.

One of the questions in a recent survey on rec.arts.int-fiction asked if we preferred "story" or "puzzle" interactive fiction. Though it's not as much of a binary choice as the wording implied, there are two extremes of a continuum, and many people have a preference towards one end or the other.

I'm not a very big IF player, but I did get into the competition in 2004, when I played and voted on every z-code game and many of the others. My favourite games were Blue Chairs and Gamlet. Both had great writing, lots to do, and, when they tried to do puzzles (Blue Chairs's midsection, the second half of Gamlet) lost it completely, requiring judicious use of the walkthrough to be able to continue the story.

I completely bypassed the puzzle-based scifi game, All Things Devours, the first time around: I'd found it an unappealing combination of boring, hard, and confusing (I died repeatedly, without ever having understood what it was I was meant to do). It turns out ATD placed 3rd, just after Blue Chairs, and after reading some rave reviews of it, I decided to give it another shot. That time I managed to get into the lab (previously I'd missed the buttons that opened it) and managed to blow myself up once or twice before getting bored.

Now the premise of the game sounds interesting: you have to travel back in time, but while you're there, you can't meet your future self or Bad Things will happen. My problem was that I couldn't even work out how to use the time machine...

Just recently, interest in IF briefly sparked again, I decide to give ATD another go. I'm momentarily put off by the fact that setting the "timer" doesn't mean the one on the time travel device, but the one on the bomb I'm carrying. Oops. So I have to set the panel? But what to? I try random numbers between 1 and 500 and end up dying. So I resort to a walkthrough. It's a number of seconds (why the game can't tell me this, given that the PC I'm controlling invented it, I don't know). I calculate the right number of seconds, press the button, and vow to actually pay attention to the time reported in the status bar. Then I start wandering around and, yes, the game is actually very clever (as I've heard, but not experienced first hand up until now), you die if you see your future self, or if that self discovers part of her world universe in an inconsistent state. My resolve to stick at this with a map and a list of times and object locations vanishes after dying twice.

I'm not trying to criticize ATD by the way: people whose opinions I trust have said great things about it, and I have tried really hard (well, fairly hard, but a number of times at least) to get it. It's just much further inclined to the puzzle end of things than I'm comfortable with, hey ho. If you've not played ATD, then go and play it now, you might well love it (but play Blue Chairs too!)

Oddly, I love Spider and Web, and that has some really difficult puzzles too. Now some of them I got by myself: getting in and out of the scanweb, and that puzzle. But others (the clattering lockpick) completely baffled me. I don't get the world model well enough to know when my actions will do the right thing, especially when they're about timing (which is an odd thing to do without detailed visual/sensory stimulation to work with). But, in the main, though I don't really get on with puzzles, you're given a gentle training in the use of the gadgets. And I loved how the game deflates your progressive attempts to do things like learning how to shut down the scanweb to sneak across the gun. So having to resort to a walkthrough to work out the frustrating "boring" puzzles is actually worthwhile: because it gives you a payoff including more clever and fun puzzles, the NPC interaction, and the aha moments of the unreliable narration. OK, so the endgame doesn't work for me: yes, it's nice to see what use the PC actually made of various gadgets and hiding places, but now you're working without the training wheels of the interrogator to tell you what you "actually" did. (I'm torn between wishing on the one hand that the dash through the facility was more "on rails"; and on the other that I'd taken a deep breath, mapped it, and realised that the basic principle was "look at all the places that have been signalled in unreliable narrations" and solved the puzzle/story myself).

But no matter, the first half of Spider and Web has set things up, it's earnt the right to have a cruel and boring timed puzzle. I'm not sure it quite deserves the final lab puzzle though, oh well...

The r.a.i-f thread I linked above has some more discussion about the dichotomy/continuum of puzzle/story IF. If you haven't already read/played modern IF, then it's worth looking at a number of different styles before making an opinion on this varied form! (And if you play IF, where do you fall in the continuum?)

(Cross posted from my use.perl blog)

The Italian Perlmongers are finalising their preparations for IPW 2008, Pisa. I managed to get to the last 2 while I was working in Florence, and the organizers have always managed to get a great venue, coffee breaks with unusually nice biscuits, and put on a fantastic mix of talks and a lively hallway track.

Like all the national conferences, talks in previous years have been largely in the local language, with maybe a handful in English from expats and visitors. This year though, the organizers have also managed to get great sponsorship from Opera, Booking.com and others and as well as making the conference free, they're able to sponsor some fantastic guest speakers. Bepi has already confirmed:

• Marcus Ramberg of Catalyst fame (speaking in English. Or possibly Norwegian :-)
• Rafael Garcia Suarez, Perl 5.10 pumpking (speaking in English... or French -- or Spanish? ;-)
• ... other speakers to be advised (Update Oops, I pre-announced one of the speakers currently in discussion with Bepi, must have misunderstood the email, apologies to all, but I do hope that does get confirmed as it's tremendously exciting).
• And looking at the talk schedule, it looks like Andrew Shitov (ash) from Moscow.pm and organizer of the Russian Perl Workshop will be talking on distributed programming with WWW::Page and Gearman, as part of his European tour (also in English)

All in all, there has never been a better time to go to an Italian Perl Workshop as a visitor, even if you don't speak Italian. It's all looking quite tempting, though I already have YAPC::EU the month before, hmmm...

Some notes on logistics if you're thinking of travelling to Pisa from outside Italy:

• Pisa airport flies various low-cost routes (Ryanair, Easyjet and others) as well as some real airlines (I like the Meridiana Gatwick-Pisa flight). Some airlines fly to nearby Florence, Bologna, or Rome, and Pisa is a convenient transport hub with trains from these cities, and Europe (Paris, Vienna, Geneva). The conference page summarizes travel options to Pisa.
• Some useful links for accomodation in Pisa
• The most important tourist sites in Pisa are conveniently clumped together in the "Campo dei Miracoli": the leaning tower, the Duomo and the Baptistery.
• Florence is about 1h30 away by train or coach. Damn I miss Florence...

I recently posted some things to Perl's CPAN that I've previously discussed in this blog.

• After my post on AUTOLOAD hate, I released the module discussed in it as Sub::Auto.
• I finally released Attribute::Cached briefly discussed in my Readable Perl slides).
• Already mentioned Sub::Curried today.

Debolaz asked in #moose about the best way to create:

a list of numbers like 10,25,50,100,250,500,1000,etc without tracking any other state than the number itself

Nope, this isn't A020179 but the much more prosaic A112024. Debolaz wanted this sequence, or something similar to it, for the same reason the US used it for currency - the numbers are human meaningful, and are useful as the numbers get exponentially bigger: in his case, for the labels for a chart. This may not be the most interesting of sequences, but, as autarch pointed out, there are many algorithms that work, and exploring some of them is fun and/or instructive.

First steps

My first idea was as follows:

• if the number is a power of 10, multiply by 2.5
• otherwise multiply by 2

Of course, knowing whether the number is a power of 10 is the only problem here. The most trivial way is to treat it as a string, and check if it begins with "1".

sub seq_1 {
    my $n = shift;
    my $val = 10;
    my @ret;
    for (1..$n) {
        push @ret, $val;
        $val *= $val =~ /^1/ ?
                2.5
              : 2;
    }
    return @ret;
}

say for seq_1(10);

autarch suggested dividing by 10 until you get to 1 (or not) as an alternative. So we were back to a state variable like the position of the element in the sequence.

Mappy

Rather than doing it recursively, you can calculate the value from each position trivially:

    map { 10 * 10**(int $_/3) * [1,2.5,5]->[$_ % 3] } 0..10

That is to say

    10    10    10    100    100    100
*    1   2.5     5      1    2.5      5
=   10    25    50    100    250    500

i.e
10 * 10 ^
     0     0     0      1      1      1
*
     1   2.5     5      1    2.5      5

Not much else to say really, though I think indexing into [1,2.5,5] with the modded value is cute. awwaid suggested an improvement:

    map { 10**(int $_ / 3 +2) * 2**($_ % 3 -2) } -1..9

Which hurt my head for a while: it comes from the realization that the sequence is actually

    10   100   100   100   1000   1000
/    1     4     2     1      4      2

Recursive

frodwith suggested a recursive solution with an explicit parameter:

 sub your_seq {
  my $n = shift;
  return 10 unless $n;
  my @prev = your_seq($n-1);
  return (@prev, $prev[-1] * ($n % 3 == 1 ? 2.5 : 2));
}

That has a rather odd recursion style: turning it into tail-recursive style, and then eliminating the recursion using the techniques from Higher Order Perl are left as an exercise to the reader.

Is Perl an acceptable Haskell?

Finally though, it is possible to do this without any additional state, by turning the function into a little state machine. On the first iteration, the value is multiplied by 2.5 and sets the next iteration to be one that multiplies by 2, leaving the next iteration to multiply by 2 but queue up the original (x2.5) function next. Instead of actually writing a state machine, I decided I'd rather have an infinite cycle of the 3 functions, and iterate through them. Haskell has this as a builtin, but we have to define it in Perl

sub cycle {
    my @list = @_;
    my @curr = @list;
    return sub {
        @curr = @list unless @curr;
        return shift @curr;
        };
}

Now we can create a list of functions that multiply by 2.5, 2, 2:

cycle([ map { times($_) } @multipliers ])

Where "times" is a function that given one multiplier, returns a function that multiplies by that number. That is to say, it's the * operator "curried". And by great coincidence, I just uploaded Sub::Curried to CPAN, so we'll use that:

curry times ($x,$y) { $x * $y }

We'll use the "curry" declarator for the rest of this example, largely because of the automatic argument unpacking magic (I love Matt Trout's Devel::Declare). Now that we have a sequence, we need to write something similar to Haskell's scanr, that repeatedly applies a transformation, returning a list of the intermediate values.

curry scan_iterator ($it, $start) {
    my $next = $start;
    return sub {
        my $ret = $next;
        $next = $it->()->($next); # prepare next value;
        return $ret;
        };
};

And as Perl doesn't like infinite calculations, we may as well transform a slice of this sequences into an array:

curry iterator_to_array ($it, $count) {
    return map { $it->() } 1..$count;
};

At which point we can put the whole thing together like so:

say for iterator_to_array(
        scan_iterator(
            mk_seq( [2.5, 2, 2] )
        )->(10) # start value
    )->(12); # number of iterations

I've uploaded the final source code as an example for Sub::Curried. Elegant? Overcomplicated? You decide!

Update:

• Joeri Samson pointed out a thinko (multiple/power)
• augustuss suggests the haskell version: scanl (*) 10 $ cycle [2.5,2,2] Much neater than my faffy version. But we can do the same in Perl (we just need to define scanl and rename iterator_to_array to "take". Link to complete source code is updated.

  say for take 12 => scanl(times)->(10 => cycle [2.5, 2, 2] );

  Notice how (times) with no arguments is equivalent to a function reference, due to the autocurrying!