Pythonで87文字でCollatz角谷問題の(以下略
f = lambda x: x == 2 and 1 or f(x % 2 and x * 3 + 1 or x / 2) + 1; max(map(f, range(2, 101)))
上の行は読みやすいように不要な空白文字を削っていませんが、削れば75文字です。 問題についての詳しい内容はキミならどう書く 2.0 - ROUND 2 - — Lightweight Language Ringをお読みください。
キャッシュを追加してみました。n = 100000で20倍程度速いみたいですね。
c = {}; f = lambda x: c.get(x,0) or c.__setitem__(x, x == 2 and 1 or f(x % 2 and x * 3 + 1 or x / 2) + 1) or c[x]; max(map(f, range(2, 100001)))
こちらも100までにして空白文字を取り除くと119文字です。
__ 関数型言語にも挑戦してみました。Schemeです。
(define (mod x y)
(if (> x y)
(mod (- x y) y)
x))
(define (step x)
(if (= (mod x 2) 1)
(+ 1 (* x 3))
(/ x 2)))
(define (numStep x)
(if (= 1 x)
0
(+ 1 (numStep (step x)))))
(define (maxStep x)
(if (= x 1)
0
(max (numStep x) (maxStep (- x 1)))))
素直な書き方をしてみました。
__ 上のSchemeコードはシンプルすぎて面白くないのでこっちもワンライナーにしてみました。といってもSchemeですから、単に改行を取り除くだけでもワンライナーになってしまって面白くないですね。そこでdefineを取り除いてみました。
(((lambda(f)(lambda(x)(f f x)))(lambda(f x)(if(= x 1)0(max(((lambda(f)(lambda(x)(f f x)))(lambda(f x)(if(= 1 x)0(+ 1(f f((lambda(x)(if(=(modulo x 2)1)(+ 1(* x 3))(/ x 2)))x))))))x)(f f (- x 1))))))100)
lambdaを一文字にする方法ってどうするんでしたっけ。それを使えば上のコードは下のようになるはずです。
(((λ(f)(λ(x)(f f x)))(λ(f x)(if(= x 1)0(max(((λ(f)(λ(x)(f f x)))(λ(f x)(if(= 1 x)0(+ 1(f f((λ(x)(if(=(modulo x 2)1)(+ 1(* x 3))(/ x 2)))x))))))x)(f f (- x 1))))))100)
こちらはλを一文字と見なせば166文字です。λは7つあるので一文字と見なしたくない人は+35してください。
__ 「f f」というあたりがYコンビネータみたいなので、Yコンビネータについて勉強してきました。参考文献はY Combinator。なるほど、上のコードでは元の関数maxStepがmaxStepを呼んでいる部分をf fで置き換えているわけですが、それをf fではなくfで置き換えることを可能にするのがYコンビネータのようです。というわけでYコンビネータを使ったバージョン。
(((λ(Y)(Y(λ(f)(λ(x)(if(= 1 x)0(max((Y(λ(f)(λ(x)(if(= 1 x)0(+ 1(f((λ(x)(if(=(modulo x 2)0)(/ x 2)(+ 1(* x 3))))x)))))))x)(f(- x 1))))))))(λ(g)((λ(f)(g(λ(x)((f f)x))))(λ(f)(g(λ(x)((f f)x)))))))100)
λを1文字として195文字ですね。Yコンビネータのせいでかえって文字数が増えています。
__ Schemeって面白いですね…。
(((lambda(▽^)((lambda(>_<)(>_<(lambda(f)(lambda(^x^)
(▽^ ^x^ 0 (lambda () (max((>_<(lambda(f)(lambda(^x^)
(▽^ ^x^ 0 (lambda () (+ 1(f((lambda(^x^)(▽^ (modulo
^x^ 2)(+ 1(* ^x^ 3))(lambda()(/ ^x^ 2))))^x^))))))))^x^)
(f(- ^x^ 1)))))))))
(lambda(-^)((lambda(^)(-^(lambda(b)((^ ^)b))))
(lambda(^)(-^(lambda(b)((^ ^)b))))))))
(lambda (a b c) (if (= a 1) b (c))))100)
なんか癒されます。λを^で代用する書き方もあるそうですけど、^^にすると顔文字が作りやすそうです。(lambda (x) (+ x 1))が(^^(^x^) (+ ^x^ 1))になります(笑)
__ 404 Blog Not Found:LLR2006 - Round 2, まだまだいくよ～
これなのだが、h(100)ではなくg(h(100))を解いてしまう。
最大のステップ長を求めるんではなくてステップ長が最大になる値を探すんでしたね。勘違いしていました。修正すると以下のようになります。
f = lambda x: x == 2 and 1 or f(x % 2 and x * 3 + 1 or x / 2) + 1; max(((f(x),x) for x in range(2, 101)))
これで最大の値とその位置が(118, 97)と出力されます。空白を削ると87文字ですね。もし「g(h(100))を出力せずにh(100)だけを出力しろ」という場合には末尾に[1]をつけてください。
