薄いブログ

技術の雑多なことを書く場所

ErlangでいろんなSortを書いてみる part1

2ヶ月ぶりの更新になります。

最近Haskellで様々なソートを
実装してみたというブログ記事を読みました。

自分がやったことある関数型言語って何があったかなと
思い出してみると、そういえば
「Erlang」
があったなとふと思い出しました。

それで僕もErlangでソートを実装してみるかと思い
実装してみたわけです。

バブルソート:

sort([]) -> [];
sort(List) ->
	Sorted = bubble_sort(List),
	[Min|More] = lists:reverse(Sorted),
	[Min|sort(lists:reverse(More))].
	
bubble_sort([]) -> [];
bubble_sort(List) when length(List) == 1 -> List;
bubble_sort([X,Y|More]) when X > Y -> [X|bubble_sort([Y|More])];
bubble_sort([X,Y|More]) -> [Y|bubble_sort([X|More])].

シェイカーソート:

shaker_sort([]) -> [];
shaker_sort(List) when length(List) < 2 -> List;
shaker_sort(List) ->
	Upped = shaker_sort(up, List),
	[Min|More] = lists:reverse(Upped),
	Downed = shaker_sort(down, More),
	[Max|Other] = lists:reverse(Downed),
	lists:reverse([Max|lists:reverse([Min|shaker_sort(Other)])]).

shaker_sort(up, []) -> [];
shaker_sort(up, List) when length(List) < 2 -> List;
shaker_sort(up, [X,Y|More]) when Y > X ->
	[Y|shaker_sort(up,[X|More])];
shaker_sort(up, [X|More]) ->
	[X|shaker_sort(up, More)];

shaker_sort(down, []) -> [];
shaker_sort(down, List) when length(List) < 2 -> List;
shaker_sort(down, [X,Y|More]) when Y < X ->
	[Y|shaker_sort(down, [X|More])];
shaker_sort(down, [X|More]) ->
	[X|shaker_sort(down, More)].

選択ソート:

selection_sort([]) -> [];
selection_sort(List) ->
	Min = lists:min(List),
	[Min|selection_sort(List -- [Min])].

挿入ソート:

insertion_sort([], Sorted) -> Sorted;
insertion_sort([Head|More], Sorted) ->
	insertion_sort(More, insert(Sorted, Head)).

insert([],Value) -> [Value];
insert([Head|_] = List,Value) when Head > Value -> [Value|List];
insert([Head|More], Value) -> [Head|insert(More, Value)].

今回はこの4つを実装しました。
実際に実装してみるとぜんぜん覚えてなくてびっくりしました。

他のソートを実装して、またブログに上げます。

では今回はこのへんで。

AOJ0047 Cup Game

3つのカップがふせて置かれています。カップの置かれている場所を、順にA,B,C と呼ぶことにします。最初はA に置かれているカップの中にボールが隠されているとします。入れ替える２つのカップの位置を保存したデータがあります。このデータを読み込んで、最終的にどの場所のカップにボールが隠されているかを出力して終了するプログラムを作成してください。ただし、カップの位置を入れ替える際には、中に入っているボールも一緒に移動するものとします。

という問題を今回は短くしてみました。

#include <stdio.h>

int main(void)
{
	char cups[4] = {0};
	char swap_a, swap_b;
	int i;
	
	cups[0] = 1;
	
	while (scanf(" %c,%c", &swap_a, &swap_b) != EOF){
		if (cups[swap_a - 'A'] == 1){
			cups[swap_b - 'A'] = 1;
			cups[swap_a - 'A'] = 0;
			continue;
		}
		if (cups[swap_b - 'A'] == 1){
			cups[swap_a - 'A'] = 1;
			cups[swap_b - 'A'] = 0;
		}
	}
	
	for (i = 0; i < 4; i++){
		if (cups[i] == 1){
			 break;
		}
	}
	
	printf("%c\n", 'A' + i);
	
	return (0);
}

こんなかんじで若干残念に書いたわけですよ。
この時点で464byte

ここで色々犠牲にすることによって

p;main(s,a,b){for(;~scanf("%X,%X",&a,&b);p=(p<=s?s-p:p)%3)s=a+b-20;p=!printf("%c\n",65+p);}

91byteまで削ることができました。
結構無茶をしたので解説できないです。

この問題の1位は23byteで、"C"だけを返すソースで憤慨しました。
1月3日に訂正されたようです。情報有り難うございます。

まだまだ、頑張らないといけないです。

Code Golf イントロダクション

Code Golf

僕が趣味(?)としているコードゴルフについて
お書きしたいと思います。

コードゴルフとは

より少ないバイト数で所与の課題をプログラミングする遊び。
より少ない打(鍵)数を競うところがゴルフに似ているところからの命名。

とりあえず、プログラムのコードを短く書けば良いそれだけのこと。
見づらいとか、非生産的であるとか、役に立たないだとかと言われるけど、
僕はコードゴルフを通して得るものもあると思います。
何より"楽しい"。それで僕はいいと思っています。

とりあえずプログラムのコードを短く書いてみましょう。(唐突
例えば1〜Nまでの合計を出すプログラムを書くとしましょう。

#include <stdio.h>

int main(void)
{
    int n;
    int i;
    int sum;

    scanf("%d", &n);

    sum = 0;
    for (i = 1; i <= n; i++){
        sum += i;
    }

    printf("%d\n", sum);

    return (0);
}

これが一般的なソースだと思います。
これをどんどん短くしていこうと思います。

// #include <stdio.h> は省略可
main(){
// 型を指定しないと自動でintになるので省略可
    int n, sum;                     
    // まとめて宣言
    scanf("%d", &n);    
    for (sum = 0; n; sum += n--);
    // nの値が0になると終了
    printf("%d\n", n);
    return 0;                       
    // 0を返さなければいけない
}

これで結構短くなりました(やったね!
しかし、まだまだ短く出来ます、この状態ではニワカです。

main(s,n){  
// main関数の第1引数に渡すと1で初期化される。argcとして扱われる。
    for(scanf("%d",&n);n-1;s+=n--);
    // 1式にscanf渡して悪いと誰が言った。
    printf("%d\n",s);
    return 0;
    // 0を返さなければいけない。
}

もうちょっと短くできる。

main(s,n){
    for(scanf("%d",&n);n-1;s+=n--);
    return !printf("%d\n",s);
    // printfの戻り値は表示した文字数。否定して0を返すようにする。
}

とここまで短くすればよいでしょう。(なにが良いのかわからない

main(n){n=scanf("%d",&n)/printf("%d\n",n*-~n/2);}

これが僕が短くできる限界です。

このように最初のコードと比べると、見づらい、意味がわからない、短い。
こういうソースを見て「美しい!!」となる方はぜひCodeGolfをやってみてください。
そして、互いに競いあいましょう。

まだまだ僕もニワカなので努力しなければいけないです。