I did it by using a regular expression to find a node in the tree which is one level higher than a leaf node
i.e. ( 0.5 ) is a leaf node ( 0.5 fluffy (1.0) (0.25) ) is the next simplest tree node. The key to identifying this tree is the ( () () ) pattern of brackets. I then used string substitution to substitute (0.5) or (0.125) in place of that tree based on whether or not the current animal had the fluffy attribute or not. Keep repeating this and you're left with just a leaf node, which contains the answer for that animal. The algorithm is pretty horrible in that I essentially parse the whole tree once for every animal in the input, but even in Ruby it was fast enough to solve the small and large input. Sadly it took me until 20 minutes after the round ended to finish the code. I qualified from round 1C though, so all was not lost! On Tue, Sep 15, 2009 at 7:08 PM, Chris K. Jester-Young <[email protected]> wrote: > > Relating to the contest analysis for Decision Tree: > >> The hard part here was parsing the tree. The easiest way to do this is by >> using a technique called recursive descent. > > In (especially, but certainly not limited to) dynamic languages, > there's an even easier technique, which is to use regular expressions > to transform the S-expressions into JSON expressions, then slurp it in > using any JSON library. Of course, if you're using a Lisp-based > language, then parsing is as simple as (read). > > I'm mentioning this because the analysis for Alien Language noted a > trivial transformation of the input into regular expressions; I > thought that the transformation described above would also be trivial > and worth mentioning in the analysis. :-D > > As an aside, some of us on the #gcj channel are participating in a "1B- > A code golf" (where 1B-A refers to the Decision Tree problem): > http://1b-a.pastebin.com/ :-P > > Cheers, > Chris. > > > -- Paul Smith http://www.nomadicfun.co.uk [email protected] --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
