Code Golf: Decision Tree

Question

In Google Code Jam 2009, Round 1B, there is a problem called Decision Tree that lent itself to rather creative solutions.

Post your shortest solution; I'll update the Accepted Answer to the current shortest entry on a semi-frequent basis, assuming you didn't just create a new language just to solve this problem. :-P

Current rankings:

• 107 Perl
• 121 PostScript (binary)
• 132 Ruby
• 154 Arc
• 160 PostScript (ASCII85)
• 170 PostScript
• 192 Python
• 196 JavaScript
• 199 Common Lisp
• 212 LilyPond
• 273 Scheme
• 280 R
• 281 sed w/ bc
• 312 Haskell
• 314 PHP
• 339 m4 w/ bc
• 346 C
• 381 Fortran
• 462 Java
• 718 OCaml
• 759 F#
• 1554 sed
• C++ not qualified for now

Foti

While meta.stackexchange.com/questions/20912/so-weekly-code-golf indicates a modest consensus in favor of code gold right now, I don't like the formulation here. At a minimum I would suggest coping the spec locally. – Stonecrop

I agree, I think you need to recreate the question here so that it is similar, but not worded exactly as the Google Code Jam question. – Isabellaisabelle

I'll try to come up with a way to word the problem that doesn't violate Google's copyright. :-D – Suellen

A bit off topic responce to dmckee; I didn't post mine this week's code golf since I saw my latest question wasn't ranked high. I guess people need time to chill between golfs :) – Anacrusis

code.google.com/codejam/contest/scoreboard?c=186264 nobody from the US in the top 50?! – Watersick

Is there a code golf where Perl hasn't come up on top ? There should be a better way of deciding a winner, from number of chars. – Disrepute

Actually, since the invention of GolfScript, there have been many a contest where the winning solution was a GolfScript one. :-P – Suellen

Scala anyone? May easily be a runner-up... – Judy

Answer 1

Perl in 107 characters

say("Case #$_:"),
$_=eval"''".'.<>'x<>,
s:[a-z]+:*(/ $&\\s/?:g,s/\)\s*\(/):/g,
eval"\$_=<>;say$_;"x<>for 1..<>

Newlines for legibility; none of them is necessary or counted in.

It uses features found only in the latest versions of Perl, so run with perl -M5.010 or later.

I used to be a Perl noob too, so this works almost the same as the ruby one. Original version 126 chars, optimizations by peutri.

Backlinks:

Word Aligned - Power Programming

Crashing

"Newlines for legibility;" (...) HA! – Vociferous

Answer 2

sed in 1554 chars (pure) / 281 (with bc)

Yes, seriously.

Usage: sed -r -f thisfile.sed < input.in > output.out

(works on GNU sed)

1d
/ /!{x
s/^$/Case #Y:/
:i
s/9Y/Y0/
ti
s/#Y/#0Y/
s/:/:0123456789/
s/(.)Y(.*):[0-9]*\1(.).*/\3\2Y:/
x
G
s/.*\n|Y//gp
z
:p
N
/[()]/s/ |\n//g
y/()/JK/
tp
H
d}
G
s/\n[^J]*/ %/
s/[^JK]*$//
:c
s/J1?([.-9]+)(.*)K/\2@\1/
/%@/by
:b
/J/s/T//
s/J([^JK]*)K/TC\1B/
tb
/ (.+) .*%\1C/{s/%[^C]*/%/
s/T.*B//
by}
s/%.*T/%/
:y
y/CB/JK/
tc
s/.\.0*\b//g
:r
/@.*@/{s/\w*@\w*$/C&B/
s/C(\w)(.*B)/\1C\2~/
s/"[^"]*/&0/g
:t
s/(\w)(C.*)(\w)B(.*~)/\1\2B\3\4\1\3/
T
s/~(10|2[01]|3[0-2]|4[0-3]|5[0-4]|6[0-5]|7[0-6]|8[0-7]|9.)/&Q/
s/(.)(.)Q/\2\1/
s/~0\w/`00/
s/~1\B/`0/
s/~22/`04/
s/~23/`06/
s/~24/`08/
s/~33/`09/
s/~25/`10/
s/~26|~34/`12/
s/~27/`14/
s/~28|~44/`16/
s/~29|~36/`18/
s/~35/`15/
s/~45/`20/
s/~37/`21/
s/~38|~46/`24/
s/~55/`25/
s/~39/`27/
s/~47/`28/
s/~56/`30/
s/~48/`32/
s/~57/`35/
s/~49|~66/`36/
s/~58/`40/
s/~67/`42/
s/~59/`45/
s/~68/`48/
s/~77/`49/
s/~69/`54/
s/~78/`56/
s/~79/`63/
s/~88/`64/
s/~89/`72/
s/~99/`81/
s/`(.)(.)/~\1'\2/
bt
:
s/(~.)'/\1/
s/..'/K&/
/K/bk
:v
s/=(,?.)'/\1/
s/,/1'/
t
s/B(.*)~/\1B"/
tr
s/"(\w*)0/A\1/g
/A.*A/{s/A[^A]*$/J&K/
:k
s/([^A])(J.*)([^A])K/\2K\1\3/
s/K(10|2[01]|3[0-2]|4[0-3]|5[0-4]|6[0-5]|7[0-6]|8[^9]|9.)/&Q/
s/(.)(.)Q/\2\1/
s/K0/=/
s/K11/=2/
s/K12/=3/
s/K13|K22/=4/
s/K14|K23/=5/
s/K15|K24|K33/=6/
s/K16|K25|K34/=7/
s/K(17|26|35|44)/=8/
s/K(18|27|36|45)/=9/
s/K(19|28|37|46|55)/W0/
s/K(29|38|47|56)/W1/
s/K(39|48|57|66)/W2/
s/K49|K58|K67/W3/
s/K59|K68|K77/W4/
s/K69|K78/W5/
s/K79|K88/W6/
s/K89/W7/
s/K99/W8/
s/W/=,/
/'/bv
s/\b=/K:/
tk
s/[:JK]A?//g
s/,/,0123456789GF/
s/(.),.*\1(.).*F/\2/
s/G/,0/
tk}
/A.*A/bv}
s/\w*C.*A//
tr
s/.*@/./

This solution omits the leading zero in front of the decimal point, and does not handle cases where the answer is 1.00. Luckily, the GCJ judge accepts the lack of a zero, and does not have any cases where the answer is 1.00.

To include the leading zero, change the last line to s/.*@/0./; and to handle a 1.00 case, append the line s/^$/1/.

Here's a solution that outsources the multiplication to bc:

1d
/ /!{x
s/\n.*//
s/.*/echo 0&+1|bc/e
x
g
s/.*/Case #&:/p
:p
N
/[()]/s/ |\n//g
y/()/JK/
tp
H
d}
G
s/\n[^J]*/ %/
s/[^JK]*$//
:c
s/J([.-9]+)(.*)K/\2*\1/
/%\*/s/.*%.(.*)/echo \1|bc -l/e
:b
/J/s/T//
s/J([^JK]*)K/TC\1B/
tb
/ (.+) .*%\1C/{s/%[^C]*/%/
s/T.*B//
b}
s/%.*T/%/
:
y/CB/JK/
tc

Hippy

Your family is worried about you. Go outside a little – Serried

Answer 3

LilyPond: 212 characters

Craziness! Utter ridiculousness!! LilyPond, with its built-in Scheme interpreter, manages to outdo Scheme by more than FIFTY BYTES! Holy acrobatic flying mooses in tights!!

x=#lambda
w=#read
#(letrec((v(x(a)(map a(iota(w)1))))(c(x(f q)(*(car q)(if(any list? q)(c
f((if(memq(cadr q)f)caddr cadddr)q))1)))))(v(x(i)(w)(set! @(w))(format
#t"Case #~a:
~{~y~}"i(v(x i(w)(c(v(x i(w)))@)))))))

Usage: lilypond thisfile.ly <input.in >output.out 2>/dev/null

Credit goes to cky for writing the Scheme solution this was based on, though this version is now substantially different. Seriously, though, the Scheme could be golfed a bit further...

Hippy

Answer 4

PostScript: 170 (regular) / 160 (ASCII85) / 121 (binary)

My shortest (regular) PostScript solution so far, provided that you rename the input file to "r" (170 characters, including newlines); uses a GhostScript-specific procedure (=only):

1[/:{repeat}/!{exch token{\ exch known{/<>}if]pop]]3 index mul
!}if}(]){token pop}/?(r)(r)file([){?]}>>begin
1[{(Case #)2{=only}:(:)=[/|[def[{[/\<<[{[/}:>>def |]! =}:}for

Usage: cp input.in r; gs -q -dNOPROMPT -dNODISPLAY -dBATCH thisfile.ps > output.out

Here's a binary version of this in 121 bytes (backslashes and unprintable characters escaped):

1[/!{\x92>\x92\xab{\\\x92>\x92`\x92p{]\x92u}if]]3\x92X\x92l!}if}(]){\x92\xab\x92u}/r(r)\x928\x92A([){r]}>>\x92\r1[{(Case #)\x92v=only[/:\x928[\x923=[{[/\\<<[{[/}\x92\x83>>\x923:]! =}\x92\x83}\x92H

If characters outside the ASCII printable range are disallowed, PS has built-in ASCII85 encoding of binary sources. We therefore have the following 160-byte solution in all ASCII printable characters:

1[([){r]}/r(r)<~OuSUj0-P\*5*Dsn>`q:6@$5JU?'9>YBkCXV1Qkk'Ca"4@Apl(5.=75YP')1:5*?@0>C.bc@<6!&,:Se!4`>4SH!;p_OuQ[/1Herh>;'5D4Bm/:07B"95!G,c3aEmO4aiKGI?I,~>cvx exec

Hippy

Surely, then, for the other interpretable languages such as Perl, you could also compress the entire source into a string and then decompress it from that. Would that work out smaller, or would the source code get bloated by the decompression machinery? – Nullipore

@Chris: The binary in PS is just shorthand for commonly used operator names; it's not actually compression of the source. ASCII85, on the other hand, is expansion of the source; but in this case, the expansion of the binary shortcuts is still less than the original. I imagine decompression machinery would bloat source code in many cases... – Hippy

Answer 5

Ruby in 132

Improved by leonid. Newlines are essential.

def j
'1
'..gets
end
j.map{|c|s=j.map{gets}*''
puts"Case #%d:"%c,j.map{gets;eval s.gsub(/[a-z]+/,'*(/ \&\b/?').gsub /\)\s*\(/,'):'}}

Ruby in 136

def j;1..gets.to_i;end;j.map{|c|m=j.map{gets}*"";puts"Case ##{c}:";j.map{gets;p eval m.gsub(/[a-z]+/,'*(/ \0\s/?').gsub /\)\s*\(/,'):'}}

I just learned about *"" being equivalent to .join"". Also realised that map could be used in a few places

Ruby in 150

1.upto(gets.to_i){|c|m=eval("gets+"*gets.to_i+"''");puts"Case ##{c}:";1.upto(gets.to_i){gets;p eval m.gsub(/[a-z]+/,'*(/ \0\s/?').gsub /\)\s*\(/,'):'}}

I am just a noob to ruby, so there is probably still a lot of room for improvement

Crashing

Wow. What does a regex in a condition even do, anyway? What does it operate on? – Stanleystanly

If it works like Perl, it evaluates as true if it matches, false otherwise. – Driscoll

If it doesn't match it evaluates to nil which works like false. – Foti

I should add that it causes lots of these warnings (eval):1: warning: regex literal in condition but stdout still gets the correct result – Foti

Anyone want to rewrite this in golfscript? golfscript.com/golfscript Might be the winner then... – Kalynkam

@CodeJoust, Maybe. It's not just a rewrite though as golfscript has no support for regex or floats – Foti

Answer 6

Python in 192

import re;S=re.sub;R=raw_input;I=input;c=0;exec r"c+=1;L=S('\) *\(',')or ',S('([a-z]+)','*(\' \\1 \'in a and',eval(('+R()'*I('Case #%s:\n'%c))[1:])));exec'a=R()+\' \';print eval(L);'*I();"*I()

Crashing

Answer 7

Common Lisp, 199 bytes

Wrapped every 80 characters:

(defun r()(read))(dotimes(i(r))(format t"~&Case #~D:"(1+ i))(r)(set'z(r))(dotime
s(a(r))(r)(print(do((g(mapcar'read(make-list(r))))(p 1(*(pop c)p))(c z(if(find(p
op c)g)(car c)(cadr c))))((not c)p)))))

Spaced and indented:

(defun r () (read))
(dotimes (i (r))
  (format t "~&Case #~D:" (1+ i))
  (r)
  (set 'z (r))
  (dotimes (a (r))
    (r)
    (print
      (do ((g (mapcar 'read (make-list (r))))
           (p 1 (* (pop c) p))
           (c z (if (find (pop c) g)
                    (car c)
                    (cadr c))))
          ((not c) p)))))

Driscoll

Darn CL and its pop function! :-P Scheme, sadly (for code golfing), doesn't have such succinct means to modify a list. – Suellen

Answer 8

Arc, 143 154 characters

Very similar to the CL one, but Arc sure has terse identifiers. Wrapped every 40 chars:

(for i 1((= r read))(prn"Case #"i":")(r)
(= z(r))(repeat(r)(r)(loop(= g(n-of(r)(r
))c z p 1)c(= p(*(pop c)p)c(if(pos(pop c
)g)c.0 cadr.c)))prn.p))

Indented:

(for i 1 ((= r read))
  (prn "Case #" i ":")
  (r)
  (= z (r))
  (repeat (r)
    (r)
    (loop (= g (n-of (r) (r))
             c z
             p 1)
       c
       (= p (* (pop c) p)
          c (if (pos (pop c) g)
                (c 0)
                (cadr c))))
    (prn p)))

Backlink: Word Aligned - Power Programming

Driscoll

Answer 9

JavaScript in 196 bytes

r='replace'
q=readline
for(n=0,t=q();t-n++;){for(print('Case #'+n+':'),d='',x=q();x--;d+=q());for(x=q();x--;)print(eval(d[r](/([a-z]+)/g,'*({'+q()[r](/ /g,':1,z')+':1}.z$1?')[r](/\) *\(/g,'):')))}

Usage: $ smjs thisfile.js <input.in

With contributions by Hyperlisk.

Hippy

Answer 10

C - 346 bytes

Compile with gcc -w

#define N{int n=atoi(gets(A));for(;n--;)
T[999];F[99];char*t,*f,*a,A[99];float p(){float
d,m=1;for(;*t++^40;);sscanf(t,"%f %[^ (]",&d,A);if(*A^41){for(f=F;m**f;){for(;*f&&*f++^32;);for(a=A;*a&&*f==*a;f++,a++);m=*a||*f&64;}d*=!m*p()+m*p();}return
d;}main(I)N{printf("Case #%d:\n",I++);t=T;N
for(gets(t);*++t;);}N gets(F),t=T,printf("%f\n",p());}}}

Crashing

Answer 11

PHP in 314

<?php function q(){return trim(fgets(STDIN));}for($n=q($x=0);$x++<$n;){for($s=q($t='');$s--;$t.=q());echo"Case #$x:\n";for($z=q();$z--;){$l=explode(' ',q());$l[0]=0;printf("%f\n",eval('return'.preg_replace(array('/\(/','/(\w+),/','/(\d\)*),\((\d)/','/^./'),array(',(','*(in_array("$1",$l,1)?','$1:$2'),$t).';'));}}

Upswell

Answer 12

FORTRAN - 381

Save as a.F95
Compile with f95 a.F95

#define _ ENDDO
#define A READ(t(k:l-1),*),a
#define Q j=1,n;READ"(A)",s
#define R READ*,n;DO
#define S k+SCAN(t(k:),'()')
CHARACTER(999)s,t,u;R i=1,n;t="";PRINT"('Case #'i0':')",i
R Q;t=TRIM(t)//s;_;R Q;d=1;k=1;DO;k=S;l=S-1
IF(t(l:l)>"(")EXIT;A,u;d=d*a;k=l;m=0
IF(INDEX(s," "//TRIM(u)//" ")>0)CYCLE;DO;IF(')'>t(k:k))m=m+2;m=m-1;k=k+1
IF(1>m)EXIT;k=S-1;_;_;A;d=d*a;PRINT*,d;_;_;END

By using the default format, each of the results starts with 2 spaces, but the google judge permits it. Thanks google judge!

EXPANDED VERSION

CHARACTER(999)s,t,u
READ*,n
DO i=1,n
    t=""
    PRINT"('Case #'I0':')",i
    READ*,n
    DO j=1,n
        READ"(A)",s
        t=TRIM(t)//s
    ENDDO
    READ*,n
    DO j=1,n
        READ"(A)",s
        d=1
        k=1
        DO
            k=k+SCAN(t(k:),'()')
            l=k+SCAN(t(k:),'()')-1
            IF(t(l:l)>"(")THEN
                READ(t(k:l-1),*),a
                d=d*a
                PRINT*,d
                EXIT
            ELSE
                READ(t(k:l-1),*),a,u
                d=d*a
                k=l
                m=0
                IF(INDEX(s," "//TRIM(u)//" ")>0)CYCLE
                DO
                    IF(')'>t(k:k))m=m+2
                    m=m-1
                    k=k+1
                    IF(1>m)EXIT
                    k=k+SCAN(t(k:),'()')-1
                ENDDO
            ENDIF
        ENDDO
    ENDDO
ENDDO
END

Crashing

Answer 13

Haskell, 312 characters

Here's another aproach to Haskell. I left the dirty work to the Prelude's lex. The wrapping around it is Text.ParserCombinators.ReadP. Importing it cost 36 characters on its own—ugh!

The parser is a Features -> SExp -> Cuteness function, which spares me most of the type declarations in quibble's/yairchu's solution.

import Text.ParserCombinators.ReadP
main=f(\t->do putStrLn$"Case #"++show t++":";s<-r g;r$print.fst.head.($id=<<s).readP_to_S.d.tail.words=<<g)
d x=do"("<-e;w<-e;c<-do{f<-e;y<-d x;n<-d x;u$if elem f x then y else n}<++u 1.0;e;u$c*read w
f x=do n<-g;mapM x[1..read n]
e=readS_to_P lex
r=f.const
g=getLine
u=return

It used to use Control.Monad's join, forM_ and replicateM, but it turns out it takes less space to redefine them approximately than to import.

I also abandoned the Prelude's readParen in favor of just calling lex before and after. In the current version, there is no need to verify the closing parenthesis: on a valid input it will always be there. On the other hand, it is vital to check the opening one: since the number is only converted after the whole subexpression has been read, a lot of backtracking would be needed to align to the correct parse.

On a theoretical machine with infinite memory and time to spare, the "("<- part might be dropped (4 characters' gain, 308 in total). Unless the call to read just aborts. On mine, the stack just overflows pretty fast.

Driscoll

Answer 14

Java in 467 bytes

This uses the javascript interpreter contained in java 6.

import java.util.*;class D{static{Scanner c=new
Scanner(System.in);int n=c.nextInt(),i=0,l;while(i++<n){l=c.nextInt();String
s="(";while(l-->=0)s+=c.nextLine();System.out.println("Case #"+i+":");l=c.nextInt();while(l-->0)try{c.next();System.out.println(new
javax.script.ScriptEngineManager().getEngineByName("js").eval(s.replace(")","))").replaceAll("\\) *\\(",":(").replaceAll("[a-z]+","*(/ $0 /.test('"+c.nextLine()+" ')?")));}catch(Exception
x){}}System.exit(0);}}

Thanks Varan, Chris and pfn (indirectly) for helping me shorten it.
Please see my other (even shorter!) java answer.

Festivity

You can shorten it further by using js (lowercase) as the engine name. – Suellen

Answer 15

m4 with echo and bc, 339 bytes

This solution is a complete and utter hack, and it gives me a headache. It contains, among other things, escaped double quotes, unescaped double quotes, unescapable backquote and single quote pairs (including a nested pair seven quotes deep), unquoted regular expressions, outsourcing decimal multiplication to bc, and the use of craZy caSE to circumvent macro expansion. But it had to be done, I guess. :p

This adds an "ultimate macroizing" solution to the previous kinds of solutions (iterated loops, recursion w/ lambda mapping, labels and branches, regexp and eval, etc.)

I think a good term for this is "macroni code" :D

(wrapped every 60 characters, for clarity)

define(T,`translit($@)')define(Q,`patsubst($@)')define(I,0)Q
(T(T(T(Q(Q(Q(Q(Q(Q(T(include(A),(),<>),>\s*>,>>),>\s*<,>;),\
([a-z]+\)\s*<,`*ifElsE<rEgExp<P;``````` \1 ''''''';0>;0;<'),
^<,`defiNe<````I';iNcr<I>>\\"Case `#'I:\\"defiNe<`A'''';'),^
[0-9]*),.+ [0-9]+.*,`dEfiNE<```P';`\& '''>A'),<>;N,`(),n'),E
,e),()),.*,`syscmd(`echo "\&"|bc -l')')

Usage: $ cp input.in A; m4 thisfile.m4 > output.out

I'm an m4 n00b, though, having learned it only an hour before writing this. So there's probably room for improvement.

Hippy

Answer 16

Pure java in 440 bytes

A shorter java solution that doesn't use any eval trick. Can be reduced to 425 by removing System.exit(0) if stderr output is ignored.

import java.util.*;enum A{_;Scanner c,d;float p(String a){return
d.nextFloat()*(d.hasNext("\\D+")?a.contains(' '+d.next()+' ')?p(a)+0*p(a):0*p(a)+p(a):1);}{c=new
Scanner(System.in);for(int n=c.nextInt(),i=0,l;i++<n;){String
s="";for(l=c.nextInt();l-->=0;)s+=c.nextLine();System.out.println("Case #"+i+":");for(l=c.nextInt();l-->0;){c.next();d=new
Scanner(s.replaceAll("[()]"," "));System.out.println(p(c.nextLine()+' '));}}System.exit(0);}}

Festivity

It's possible to import statics as of 1.5.0 (java.sun.com/j2se/1.5.0/docs/guide/language/static-import.html). You can possibly use this on System.out and perhaps save a bit of code. – Nullipore

Yes, but the import statement would be "import static java.lang.System.*;" which is longer than the savings it brings. The code ends up taking 467 bytes. Unless you can write the import in a shorter way. – Bryant

Credits: pfn (no "main"), nabb (class->enum), Utkarsh (while->for) – Bryant

You can avoid the main method, but it doesn't make it runnable then without using a loader :) – Nullipore

Actually it IS runnable, just try it. Static initializers are executed before it even looks for a "main" method. The previous version of my answer (from 2009) was also runnable, with no "main". – Bryant

Oh right -- Eclipse doesn't want to run it, but maybe it'd work okay from the command line then :) – Nullipore

I don't know how you'd even redirect the input in Eclipse – Bryant

Answer 17

OCaml in 718 bytes

I'm an OCaml n00b, so this is probably much longer than it needs to be.

Usage: ocaml thisfile.ml <input.in >output.out

#load"str.cma";;open List;;open String;;open Str;;let x=length and
y=Printf.printf and e=global_replace and h=float_of_string and b=regexp and
k=index and r=read_line and a=read_int and w s m c=sub s(c+1)(m-c-1);;for i=1to
a()do y"Case #%d:\n"i;let t=let n=a()in let rec g d j=if j>n then d else
g(d^(r()))(j+1)in e(b" ")""(e(b"\\b")"^"(g""1))and n=a()in let rec z j=if j>n
then()else let q=tl(split(b" ")(r()))in let rec g l j s p=let o=k s '('and c=k
s ')'in if j then let f=w s c o in if contains f '('then let m=k s '^'in let
c=index_from s(m+1)'^'in g 0(mem(w s c m)q)(w s(x s)c)(h(w s m o)*.p)else h f*.p
else if o<c then g(l+1)j(w s(x s)o)p else g(l-1)(l=1)(w s(x s)c)p in y"%f\n"(g
0(0=0)t 1.);z(j+1)in z 1done

Hippy

Answer 18

C++ in 698 bytes
Compile with 'g++ -o test source.cpp -include iostream -include vector -include sstream'

#define R(x,f,t) for(int x=f;x<t;x++){
#define S(x) x.size()
#define H string
#define U while
#define I if
#define D cin>>
#define X t.substr(p,S(t))
using namespace std;
int main(){int h,l,n,a,p,Y,W;D h;for(int q=1;q<=h;q++){D l;H s;char c;D c;R(i,0,l)H L;getline(cin,L);R(j,0,S(L))I (L[j]==41||L[j]==40)s+=32;s+=L[j];I(L[j]==40)s+=32;}}D a;printf("Case #%d:\n",q);R(i,0,a)H N;D N;D n;vector<H>f;R(j,0,n)D N;f.push_back(N);}H t=s;float P=1;p=0;U(p<S(t)-1){p=0;U(t[p]!=48&&t[p]!=49)p++;t=X;stringstream T(t);float V;T>>V;H F;T>>F;P*=V;I(F[0]==41)break;Y=0;R(j,0,S(f))if(F==f[j])Y=1;}p=t.find(40)+1;t=X;p=0;I(Y==0){W=1;U (W>0){I(t[p]==40)W++;I(t[p]==41)W--;p++;}t=X;p=0;}}cout<<P<<endl;}}return 0;}

EDIT: I'm sorry; I thought it was ok for the includes (eg, C works even w/o including basic libraries), while I'm sure it would be if I decleared the defines this way. I'm not home now, and I won't be for some time: I won't be able to modify it. Just ignore my submission.

Embryectomy

The includes on the compilation command line feel like cheating. If you go that path, you might just as well put all the defines there too, which the other languages haven't done. (see for example Scheme, Haskell, Java, CL, C) – Driscoll

OTOH, you probably don't need the newline after the using namespace (-1), and could declare q with the other ints (-2). You might also try not to return 0 at the end; though it's dubious C++, I recall it works with most compilers anyway. – Driscoll

The c++ standard explicitly states (3.6.1): "If control reaches the end of main without encountering a return statement, the effect is that of executing 'return 0'" – Glia

Answer 19

Scheme (Guile 1.8)

Here's my version at 278 bytes (with improvements from KirarinSnow to bring it down to 273), after stripping off all the newlines (except ones in string literals, of course). It only works on Guile 1.8 (since in standard Scheme, define is a syntax, not an object, but Guile represents it as an object anyway).

(define ! define)
(!(c f p w . r)(if(null? r)(* p w)(apply c f(* p w)((if(memq(car r)f)cadr caddr)r))))
(!(d . l)(map display l))
(!(r . x)(read))
(! n(r))
(do((i 1(1+ i)))((> i n))(r)(let((t(r)))(d"Case #"i":
")(do((a(r)(1- a)))((= a 0))(r)(d(apply c(map r(iota(r)))1 t)"
"))))

Isochroous

Answer 20

F#: 759 significant chars (Wow, I'm bad at this ;) )

Minimized version

open System.Text.RegularExpressions
type t=T of float*(string*t*t)option
let rec e=function x,T(w,Some(s,a,b))->e(x,if Set.contains s x then a else b)*w|x,T(w,_)->w
let rec h x=Regex.Matches(x, @"\(|\)|\d\.\d+|\S+")|>Seq.cast<Match>|>Seq.map (fun x -> x.Value)|> Seq.toList
let rec p=function ")"::y->p y|"("::w::x::y->match x with ")"->T(float w,None),y|n->let a,f=p y in let b,g=p f in T(float w,Some(n,a,b)),g
let solve input =
    Regex.Matches(input,@"(\(((?<s>\()|[^()]|(?<-s>\)))*\)(?(s)(?!)))\s+\d+\s+((\S+\s\d(.+)?\s*)+)")
    |>Seq.cast<Match>
    |>Seq.map(fun m->fst(p(h(m.Groups.[1].Value))), [for a in m.Groups.[3].Value.Trim().Split([|'\n'|])->set(a.Split([|' '|]))])
    |>Seq.iteri(fun i (r,c)->printfn"Case #%i"(i+1);c|>Seq.iter(fun x->printfn"%.7F"(e(x, r))))

Readable version

open System.Text.RegularExpressions

type decisionTree = T of float * (string * decisionTree * decisionTree) option
let rec eval = function 
    | x, T(w, Some(s, a, b)) -> eval(x, if Set.contains s x then a else b) * w
    | x, T(w, _) -> w

// creates a token stream
let rec tokenize tree =
    Regex.Matches(tree, @"\(|\)|\d\.\d+|\S+")
    |> Seq.cast<Match>
    |> Seq.map (fun x -> x.Value)
    |> Seq.toList

// converts token stream into a decisionTree
let rec parse = function
    | ")"::xs -> parse xs
    | "("::weight::x::xs ->
        match x with
        | ")" -> T(float weight, None), xs
        | name ->
            let t1, xs' = parse xs
            let t2, xs'' = parse xs'
            T(float weight, Some(name, t1, t2)), xs''

// uses regex to transform input file into a Seq<decisionTree, list<set<string>>, which each item in our 
// list will be tested against the decisionTree
let solve input =
    Regex.Matches(input, @"(\(((?<s>\()|[^()]|(?<-s>\)))*\)(?(s)(?!)))\s+\d+\s+((\S+\s\d(.+)?\s*)+)")
    |> Seq.cast<Match>
    |> Seq.map (fun m -> fst(parse(tokenize(m.Groups.[1].Value))), [for a in m.Groups.[3].Value.Trim().Split([|'\n'|]) -> set(a.Split([|' '|])) ])
    |> Seq.iteri (fun i (tree, testCases) ->
            printfn "Case #%i" (i+1)
            testCases |> Seq.iter (fun testCase -> printfn "%.7F" (eval (testCase, tree)))
        )

Paediatrician

Answer 21

R in 280 bytes

Note: On the standard distribution of R (as of v. 2.9.2), this program does not pass the large input and fails on just Case 28 (which is nested to 99 levels), generating a "contextstack overflow". To fix this, modify the line in src/main/gram.c that reads

#define CONTEXTSTACK_SIZE 50

and replace the 50 with something like 500. Then recompile. Et voilà!

n=0
g=gsub
eval(parse(text=g('[^
]* [0-9]+( [^
]*|
)','f=c(\\1)
cat(eval(d),"
")
',g('
\\(','
cat("Case #",n<-n+1,":
",sep="")
d=expression(',g('" "','","',g(')\\s*\\(',',',g(' *("[a-z]+")\\s*\\(','*ifelse(\\1%in%f,',g('([a-z]+)','"\\1"',paste(readLines('A'),collapse='
')))))))))

Usage (requires renaming input): cp input.in A; R -q --slave -f thisfile.R >output.out

Hippy

Answer 22

C in 489 bytes

Code wrapped at 80 chars, there are actually just 3 lines.

Save in a.c and compile with: gcc -w a.c -o a

#define S int I,N;scanf("%d\n",&N);for(I=-1;++I<N;)
#define M 1000
char B[M],Z[M],Q[M]={' '},*F[M],*V;float W[M],H;int J,C,L[M],R[M];t(){V=strtok(0
," \n()");}p(){int U=C++;F[U]=0;if(!V)t();sscanf(V,"%f",W+U);t();if(V&&*V>='a')s
trcpy(Q+1,V),V=0,F[U]=strdup(strcat(Q," ")),L[U]=p(),R[U]=p();return U;}main(){S
{printf("Case #%d:\n",I+1);*B=0;{S strcat(B,gets(Z));}V=strtok(B," \n(");C=0,p()
;{S{strcat(gets(B)," ");for(J=0,H=W[0];F[J];J=strstr(B,F[J])?L[J]:R[J],H*=W[J]);
printf("%f\n",H);};}}}

Incensory

Answer 23

Haskell, 514 bytes (I suck?).

Based on quibble's solution:

import Control.Monad
import Text.ParserCombinators.Parsec
data F=N|F String(Float,F)(Float,F)
r=return
f=many1 letter>>= \i->w>>d>>= \t->d>>=r.F i t
d=char '('>>w>>many1(oneOf".0123456789")>>= \g->w>>(f<|>r N)>>= \p->char ')'>>w>>r(read g,p)
w=many$oneOf" \n"
g=getLine
l=readLn
m=replicateM
main=l>>= \n->forM_[1..n]$ \t->putStrLn("Case #"++show t++":")>>l>>=(`m`g)>>=(\(Right q)->l>>=(`m`p q)).parse d"".join
z(p,f)=(p*).y f
y N _=1
y(F n t f)x=z(if n`elem`x then t else f)x
p q=fmap(drop 2.words)g>>=print.z q

Petro

Are you sure all those leading definitions actually make your code shorter? Some of them seem unnecessary. – Vange

Which ones do you have in mind? From the imports, Control.Monad is needed for forM_, replicateM and join, Parsec is needed for pretty much anything else. From the toplevels, it seems to me they all save some characters. – Driscoll

How about using Text.Parsec instead? – Horsemanship