On Sep 16, 4:08 am, "Chris K. Jester-Young" <[email protected]> wrote:
> Relating to the contest analysis for Decision Tree:
>
> 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 codegolf" (where 1B-A refers to the Decision Tree
> problem):http://1b-a.pastebin.com/:-P
>
> Cheers,
> Chris.
The original idea was to transform the decision tree into a Python
tuple or list by adding quotation marks and commas at the appropriate
spots. This could then be explored recursively as mentioned above.
The solution presented here takes trivial another step further by
transforming the decision tree into an expression that could simply be
evaluated against a feature list
Here is a description of how to do this in Python:
let us define a function f
def f(a,yes,no):
if a in features:
return yes
return no
now transform the sample using regular expressions to this
L="""(0.2 *f("furry",
(0.81 *f("fast",
(0.3),
0.2)
)
,0.1 *f("fishy",
(0.3 *f("freshwater",
(0.01),
0.01)
)
,0.1)
)
)"""
surprisingly this transformation can be performed using just 2
substitutions!
now we are ready to try it out
features=['furry','freshwater']
eval(L)
0.032400000000000005
Here is the 217 byte Python version after alc helped squeezed a couple
more bytes from it
import re
S=re.sub
R=raw_input
I=input
c=0
exec r"c+=1;print'Case #%s:'%c;L=S('([a-z]+)','*(lambda*x:x[2-(x[0]in
a)])(\'\\1\',',S('\) *\(','),',eval(('+R()'*I())[1:])));exec'a=R
().split()[2:];print eval(L);'*I();"*I()
Cheers,
gnibbler
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
