代码高尔夫：决策树

Question

代码高尔夫：决策树

language-agnosticrosetta-stone

18

在Google Code Jam 2009年的1B轮比赛中，有一个名为"决策树"的问题，它适合采用非常创造性的解决方案。

发布你的最短解决方案；我会定期更新已接受的答案，将其更新为当前最短的条目，但前提是你没有刚刚创建一种新语言来解决这个问题。 :-P

当前排名:

107 Perl（Perl）
121 PostScript (binary)（PostScript二进制）
132 Ruby（Ruby）
154 Arc（Arc）
160 PostScript (ASCII85)（PostScript ASCII85）
170 PostScript（PostScript）
192 Python（Python）
196 JavaScript（JavaScript）
199 Common Lisp（通用Lisp）
212 LilyPond（LilyPond）
273 Scheme（Scheme）
280 R（R语言）
281 sed w/ bc（带有bc的sed）
312 Haskell（Haskell）
314 PHP （PHP）
339 m4 w/ bc（带有bc的m4）
346 C（C语言）
381 Fortran（Fortran）
462 Java（Java）
718 OCaml（OCaml）
759 F#（F#）
1554 sed（sed）
C++暂不符合要求

- C. K. Young

22

虽然http://meta.stackexchange.com/questions/20912/so-weekly-code-golf目前显示对于代码高尔夫有一定的共识，但我不喜欢这里的表述。至少我建议在本地复制规范。 - dmckee --- ex-moderator kitten

1

我同意，我认为你需要在这里重新创建问题，使其类似，但不是与Google Code Jam问题措辞完全相同。 - pdavis

2

对dmckee的回复有点离题；我没有发布本周的代码高尔夫，因为我看到我的最新问题排名不高。我想人们需要在高尔夫之间放松一下 :) - LiraNuna

http://code.google.com/codejam/contest/scoreboard?c=186264 前50名竟然没有来自美国的选手？！ - Chris S

有没有一种代码高尔夫比赛，其中Perl没有获胜？应该有更好的方法来决定获胜者，而不是根据字符数。 - Rook

显示剩余3条评论

23个回答

16

107个字符的Perl代码

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

为了提高可读性而添加换行符；其中没有一个是必需的或计数的。

它使用仅在最新版本的Perl中才能找到的功能，因此请使用perl -M5.010或更高版本运行。

我以前也是Perl新手，因此这个版本与ruby版本几乎相同。原始版本126个字符，由peutri进行了优化。

反向链接：

Word Aligned - Power Programming

- John La Rooy

5

换行符以提高可读性；（...）哈！ - Alaor

14

LilyPond：212个字符

太疯狂了！太不可思议了！LilyPond内置的Scheme解释器，竟然比Scheme多出超过50个字节！天啊，这是飞行驯鹿穿着紧身衣进行杂技表演！！

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编写的Scheme解决方案，尽管这个版本现在已经有了很大的不同。但是，Scheme还可以更进一步地压缩...

- KirarinSnow

12

后记：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

- KirarinSnow

那么，对于其他可解释的语言，比如Perl，您肯定也可以将整个源代码压缩成字符串，然后从中进行解压缩。这样做会更小吗？还是源代码会因为解压缩机制而变得臃肿？ - Chris Dennett

1

@Chris：PS中的二进制只是常用运算符名称的简写；它实际上并不是源代码的压缩。另一方面，ASCII85是源代码的扩展；但在这种情况下，二进制快捷方式的扩展仍然比原始代码少。我想解压机器在许多情况下会使源代码膨胀... - KirarinSnow

11

在 132 中使用 Ruby

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

我刚学到了*“”等价于.join”。同时意识到在一些地方可以使用map。

150个Ruby示例

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

我只是Ruby的新手，所以可能还有很大的改进空间。

- John La Rooy

哇，条件语句中的正则表达式到底是做什么用的？它作用于什么上面？ - DigitalRoss

如果它像Perl一样工作，那么如果匹配成功则返回true，否则返回false。 - JB.

如果不匹配，则评估为nil，其作用类似于false。 - John La Rooy

我应该补充说明，它会导致很多这样的警告 (eval):1: 警告：条件中的正则表达式文字但是标准输出仍然得到了正确的结果。 - John La Rooy

有人想用Golfscript重写这个吗？ http://www.golfscript.com/golfscript/ 也许会成为赢家… - CodeJoust

@CodeJoust，或许可以。但这并不仅是一个重写，因为GolfScript不支持正则表达式或浮点数。 - John La Rooy

9

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

这段代码是 Python 在 192 题目中的一个例子。它使用了正则表达式和其他技术来进行字符串操作。该代码可以根据输入数据计算并输出结果。

- John La Rooy

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

- JB.

1

该死的CL和它的pop函数！:-P遗憾的是（对于代码高尔夫而言），Scheme没有这样简洁的方法来修改列表。 - C. K. Young

6

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

- John La Rooy

6

JavaScript 196字节版本

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贡献。

- KirarinSnow

6

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

反向链接: Word Aligned - 强大编程

- JB.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- KirarinSnow · Accepted Answer

纯文本中的sed（1554个字符）/带有bc的sed（281个字符）

是的，你没看错。

用法：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