Code Golf:决策树

Question

在Google Code Jam 2009,第1B轮中,有一个称为决策树的问题,它可以提供相当有创意的解决方案.

发布最短的解决方案; 我会在半频繁的基础上将接受的答案更新为当前最短的条目,假设您不仅仅是为了解决这个问题而创建一种新语言.:-P

目前的排名:

• 107 Perl
• 121 PostScript(二进制)
• 132 Ruby
• 154 弧
• 160 PostScript(ASCII85)
• 170 PostScript
• 192 Python
• 196 JavaScript
• 199 Common Lisp
• 212 LilyPond
• 273 计划
• 280 R
• 281 sed w/bc
• 312 哈斯克尔
• 314 PHP
• 339 m4 w/bc
• 346 C
• 381 Fortran
• 462 Java
• 718 OCaml
• 759 F#
• 1554个SED
• C++现在不合格

Answer 1

sed在1554个字符(纯)/ 281(与bc)

是的,认真的.

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

(适用于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/.*@/./

该解决方案省略了小数点前面的前导零,并且不处理答案为1.00的情况.幸运的是,GCJ法官接受缺少零,并且没有任何答案是1.00的情况.

要包括前导零,请将最后一行更改为s/.*@/0./; 并处理1.00案件,追加该行s/^$/1/.

这是一个将乘法外包给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

Answer 2

Perl,107个字符

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

易读性新线; 没有必要或计入.

它使用仅在最新版本的Perl中找到的功能,因此请运行perl -M5.010或稍后运行.

我曾经也是一个Perl noob,所以这和ruby几乎一样.原始版本126字符,由peutri优化.

反向链接:

字对齐 - 电源编程

Answer 3

LilyPond:212个字符

疯狂!荒谬可笑!LilyPond凭借其内置的Scheme解释器,超过了FIFTY BYTES,超越了Scheme!穿紧身衣的神圣杂技飞行mooses !!

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)))@)))))))

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

幸得CKY写计划的解决方案这是基于,虽然这个版本是现在大不相同.但说真的,这个计划可以进一步打高尔夫球......

Answer 4

PostScript:170(常规)/ 160(ASCII85)/ 121(二进制)

我目前为止最短(常规)PostScript解决方案,前提是您将输入文件重命名为"r"(170个字符,包括换行符); 使用特定于GhostScript的过程(=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

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

这是121字节的二进制版本(反斜杠和不可打印的字符转义):

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

如果不允许ASCII可打印范围之外的字符,则PS具有二进制源的内置ASCII85编码.因此,我们在所有ASCII可打印字符中都有以下160字节的解决方案:

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

Answer 5

Ruby中的132

由leonid改进.换行必不可少.

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中的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*\(/,'):'}}

我刚学会了*""相当于.join"".还意识到地图可以在一些地方使用

Ruby中的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*\(/,'):'}}

我只是一个红宝石的菜鸟,所以可能仍有很大的改进空间

Answer 6

Python中的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()

Answer 7

Common Lisp,199个字节

每80个字符包裹一次:

(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)))))

间隔和缩进:

(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)))))

Answer 8

C - 346个字节

用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());}}}

Answer 9

196字节的JavaScript

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,'):')))}

用法: $ smjs thisfile.js <input.in

有了Hyperlisk的贡献.

Answer 10

Arc,143 154 人物

非常类似于CL,但Arc肯定有简洁的标识符.每40个字符包裹一次:

(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))

缩进:

(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)))

反向链接:字对齐 - 电源编程

Answer 11

PHP中的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).';'));}}