選択範囲を最初にuntabifyしてしまってから、行頭のスペースの数が一番少ないところにあわせてそのスペースを取り去るというもの。最初は「バッファから選択範囲の文字列を取り出して加工して書き戻そう」と思ったのですけど、「選択範囲の文字列を変更」という関数がなんなのかわからなかったのでこうなりました。どうも「編集範囲を制限してからその範囲に処理を行う」というやり方の方がEmacsらしいようです。
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]をつけてください。
今日の帰宅車内ハック。といっても武蔵野線は混んでいて座れなかったのでりんかい線の中だけなのですけど。先日作った双方向リストに見やすい表示機能をつけて、Dancing Linksのremoveとrestoreを実装しました。 肝心の双方向リストのソースコードがなくなっていてうちひしがれかけたのですけど、改めて書いてみるとすんなり書けてしまいました。やっぱり最初に作るときが一番大変ですが、一度できるとできたときの「Aha!」によって重要なところは脳に刻み込まれるのでソースがなくなってももう一度作ることができるわけです。そんなことはどうでもいいか。
一応できました。後は非破壊的クイックソートとのパフォーマンスの差を調べてみたいところです。
後輩のQuickSortの課題を見ていて思ったのですけど、QuickSortは分割したリストのために新たに領域を確保していいかどうかによって難易度がだいぶ異なりますよね。高級言語は「QuickSortがこんなに簡単に書ける」なんてことを主張することがありますが、与えられた配列をその配列(+定数サイズ)の領域だけでソートするCとかで書かれたアルゴリズムを「真・クイックソート」だとすれば、新たな領域の確保を伴うQuickSortはちっとも早くないので「似非クイックソート」かもしれません。
で「似非クイックソート」なら簡単に書けるという話題で、ラボから赤坂某所への電車で書いたJavaのコード。
import java.util.Iterator;
import java.util.Vector;
public class Test {
public static void main(String[] args) {
Vector<Integer> vec = new Vector<Integer>();
vec.add(5);
vec.add(1);
vec.add(2);
vec.add(4);
vec.add(3);
print(vec);
vec = sort(vec);
print(vec);
}
private static void print(Vector<Integer> vec){
System.out.print("{");
for (Iterator<Integer> iter = vec.iterator(); iter.hasNext();) {
Integer element = iter.next();
System.out.print(element);
if(iter.hasNext()){
System.out.print(", ");
}
}
System.out.print("}");
}
private static Vector<Integer> sort(Vector<Integer> vec) {
if(vec.size() < 2){
return vec;
}
Integer pivot = vec.get(0);
Vector<Integer> less = new Vector<Integer>();
Vector<Integer> more = new Vector<Integer>();
for(int i = 1; i < vec.size(); i++){
Integer v = vec.get(i);
if(v < pivot){
less.add(v);
}else{
more.add(v);
}
}
Vector<Integer> result;
result = sort(less);
result.add(pivot);
result.addAll(more);
return result;
}
}
この通り非常に簡単(？) 似非クイックソートは高級言語だとかなり短く書けるのですけど、まぁJavaはそれほど高級じゃないということでしょう。Pythonなら4行で実装できますし。
def sort(a):
if len(a) > 1:
return sort([x for x in a[1:] if x < a[0]]) + a[:1] + sort([x for x in a[1:] if x >= a[0]])
return a
print sort([5,4,1,3,2])
まぁ、冗談はさておきまともに書いても15行程度でしょうか。
def sort(aList):
if len(aList) < 2: return aList
pivot = aList.pop()
less = []
more = []
for item in aList:
if item < pivot:
less.append(item)
else:
more.append(item)
less = sort(less)
more = sort(more)
less.append(pivot)
return less + more
Schemeだと「リストを結合する関数」と「条件を満たす要素だけを取り出す関数(filter?)」を「車輪の再開発」してもこんな感じでしょうか。
(define (get less aList pivot)
(if (null? aList)
()
(if (less (car aList) pivot)
(cons (car aList) (get less (cdr aList) pivot))
(get less (cdr aList) pivot))))
(define (join list1 list2)
(if (null? list1)
list2
(cons (car list1) (join (cdr list1) list2))))
(define (sort aList)
(let
((less (lambda (x y) (< x y)))
(more (lambda (x y) (>= x y))))
(if (null? aList)
()
(join (sort (get less (cdr aList) (car aList)))
(cons (car aList)
(sort (get more (cdr aList) (car aList))))))))
この後、「真・クイックソート」をJavaやPythonで実装すると後輩の目標を奪ってしまうのでSchemeでやろうとしてかなり苦しみました。 一度「一方向の連結リストじゃダメなんじゃないか」と考えて双方向リストを実装してみたり。
(define (makeDoublyLinkedList aList prev)
(if (null? aList)
()
(if (null? (cdr aList))
(cons (car aList) (cons () prev))
(let ((c (cons (car aList) ())))
(set-cdr! c
(cons
(makeDoublyLinkedList (cdr aList) c)
prev))
c))))
(define (getNext dList)
(car (cdr dList)))
(define (getPrev dList)
(cdr (cdr dList)))
(define dl (makeDoublyLinkedList '(1 2 3) ()))
(car dl) ;-> 1
(car (getNext dl)) ;-> 2
(car (getPrev (getNext dl))) ;-> 1
僕にとって関数型言語はパズル用言語なので、letやsetを使うのは自分的に禁止だったのですが、この手のモノをやるのには必要不可欠ですね。あと、LispやSchemeは確かにツリー状のモノを扱うのには適していますが、双方向リストのような本質的にループだらけの構造は逆に書きづらいかもしれません。
で、とりあえず破壊的ソートは「与えられたリストのcarをピボットにしてピボットより小さいモノをピボットの前に移動する」って所までできました。あとはピボットの前と後ろとを再帰的にソートしていけばいいのですけど…ここまで書いて設計がまずい気がしてきました。
(define (sort! head tail)
(if (null? head)
()
(find head (cdr head) tail (lambda (x) (< x (car head))))))
(define (shiftOne head tail)
(display "shiftOne")
(display tail)
(display "\n")
(if (null? tail)
tail
(if (null? (car (cdr tail)))
(begin
(set-car! (cdr tail) (car tail))
(set-car! tail ())
head)
(shiftOne head (cdr tail)))))
(define (shift wholeList)
(display "shift")
(if (null? (car wholeList))
wholeList
(shift (shiftOne wholeList wholeList))))
(define (find aList start end condition)
(if (equal? start end)
()
(if (condition (car start))
(begin
; rotation
(let ((x (car start)))
(set-car! start ())
(set-car! (shift aList) x))
; partial sort required
(find aList (cdr start) end condition))
(find aList (cdr start) end condition))
))
うーん。「リストのこの範囲にこの処理を行う」だとか「この値を手前のこの位置に移動して間の物はずらす」だとかを定義して、それを組み合わせるほうがよさそうです。でももう26時半だしなぁ。
凡例{ ●: 単一エントリーへのリンク, □: そこから最新記事までを一覧表示, ■: そこから最新記事までをwindow.openで開く}(comming soon)
2006年06月03日
