type t (* void *)

関数型言語や英語学習の事とか。

プログラミング一般: 今度のプログラミング勉強会(笑)のパズルとか

どうもこんばんは。近頃私は生きていたり死んでいたりしました。

最近量子将棋とか量子人狼とかそういうのが人気ですしね(?)

今回は主に友人と楽しくプログラミング言語の文句を言うために飲み会をやる、口実となる毎度毎度の課題を書き下す記事です。多分読んでも面白く無いです。

巡回セールスマン問題

 

言わずと知れたNP困難な問題です。

今回は2次元上に存在する点同士を結んで、最初の都市に帰ってくるまでの最短距離を求めるのですが1分以内で求められる最短距離を争いましょうか。時間厳守大事。誰かのPCでLinuxのTerminalでtimeコマンドで時間測りましょうか。

点の数が50個くらい用意すれば十分難しくなるかなぁと。

入力は、

23 1000

234 590

....

みたいに0から1023までの整数が2つ並んだテキストファイルです。

訂正。せっかくだから0から255の8bitで表せる数にしましょう。

50行並びます。一番上の行が始まる点を表します。

10回くらい試して最も短い距離を計算した回数が多い人を勝者としましょうか。

出力はその距離と、点をどのように結んだのかわかる形式で画面に出すことかなぁ。

スネークソート

どこに載っていたのか忘れてしまいましたが、スネークソートはどうでしょう。

これは、例えば

29 31 60 79 21 72 70 69 81

30 3 22 64 42 66 73 32 65

12 54 43 16 2 20 68 63 80

13 4 17 1 41 51 19 15 50

44 39 24 53 28 40 45 46 33

55 5 23 18 61 27 52 8 47

58 25 59 62 11 76 9 48 49

14 57 6 36 75 10 74 35 34

56 38 37 26 67 77 71 7 78

 

みたいに9×9のマス目があった時に、これを

73 74 75 76 77 78 79 80 81

72 43 44 45 46 47 48 49 50

71 42 21 22 23 24 25 26 51

70 41 20  7   8    9 10 27 52

69 40 19  6   1    2 11 28 53

68 39 18  5   4    3 12 29 54

67 38 17 16 15 14 13 30 55

66 37 36 35 34 33 32 31 56

65 64 63 62 61 60 59 58 57

のように、真ん中の(5,5)が1となりそれに対して以上のようにソートする問題です。

マス目で考えた時に、上下左右の交換しかできません。

その交換回数をなるべく短くするコードを書いて、回転回数を争う、というのはどうでしょう。

 

入力はスペースで区切られた数字の列が9行並んでいて、それに対して

(座標) (交換方向)

がズラズラ何らんだテキストを出力にしましょう

座標=num num

交換方向 = left | right | up | down

という文法で、例えば

1 2 right と書けば(1,2)とその右の(2,2)の数字を交換するという意味になることにしましょう。不正な交換できない記述はErrorということで。

もとの問題のテキストとその答えを入力にしてそれが正しくソートされているか分析するツールは僕が作っておきます。そんなに難しそうじゃないし。

 

言語とか?

言語とか共通にしたほうがいいんでしょうか?各々好きな言語使えばいいですかね。

僕はJavaで書くか、OCamlで書く予定ですです。