Konoha開発状況
こんにちは、chenjiです。
今回は、2012年6月現在のKonohaの開発状況をお知らせします。
Konohaは、2007年にバージョン0が公開されて以来、機能拡張や独自シンタックスの追加など、進化を続けてきています。途中で、言語名がKonohaからKonohaScriptへと変更されたこともありました。現在はKonohaという元の名前に戻っています。
（ブログタイトルも、それに合わせて変更しました。）
2012年に入ってから、Konohaは大幅な転換期を迎えました。
これまでの度重なる機能追加により、Konoha本体のバイナリサイズがかなりファットになってきていました。そこで、Konoha本体のもつ機能を言語としての最小限の機能にとどめ、他の拡張機能は全てモジュールとして提供する方針に転換しました。また、Konohaのメジャーバージョンも1から2へとバージョンアップしました。
以下、新しくなった情報を幾つか載せます。
開発レポジトリ
GitHubに開発メインラインを置いています。
https://github.com/konoha-project/konoha
開発者用メーリングリスト
Konoha言語の開発者向けMLです。Konohaのバグ報告や、言語仕様に関する議論を行なっています。
Google グループ
Apacheモジュール開発記
こんばんは。
最近はApacheモジュール開発に勤しんでおります。
//... static int test_handler(request_rec *r) { //... ap_rputs("some text", r); r->content_type = "text/html; charset=UTF-8"; //... return OK; } //...
Content-Typeヘッダを指定するには、request_rec構造体のcontent_typeフィールドに文字列を設定します。
そして、ap_rputsや、ap_rprintfを用いてレスポンステキストを出力します。
ところが、上記のように
- ap_rputsでレスポンス出力
- r->content_typeの指定
という順序で書いた場合、レスポンスの文字列がある大きさを超えた場合に、自動的にレスポンスが
チャンクとして送られてしまい、以降のcontent_typeの指定が無視されます。そのため、上記の順序で
記述した場合、自動的にtext/plainとなってしまいます。
これに気がつくのに半日かかりましたorz
教訓：Apacheモジュールでは、HTTPのヘッダをコンテンツより前に出力しよう。
考えてみれば当たり前のことですね。
GO FOR IT総括
こんにちは、chen_jiです。
ここ一週間、「GO FOR IT」に取り組んできましたが、なんとか提出だけは(1)から(5)までの全問題について
行うことが出来ました。なかなかやりがいのある問題が揃っていたので、楽しくチャレンジすることができました。
序盤ゆっくりしたせいで、後半のアクの強い問題に時間を費やすことができなかったのが少々心残りですが、
とりあえず目標は達成できたかな、という感覚です。
これまでに掲載したコードは、提出したものと同様のものになります。
また、ブログだけでは見づらいと思いますので、GitHubにレポジトリを作成しました。
GO FOR IT関連は本日で最後になります。
ここまでお読みいただき、ありがとうございました。
ではまた、通常営業に戻ります。
GO FOR ITに挑戦 (5) 申告制エレベータ
こんにちは、chen_jiです。
GO FOR IT最後の問題にチャレンジしましたが、残念ながら締め切りが迫っていますので、未完成の現段階で公開します。
問題
こちらをご参照下さい。
解答
i)の解答
#!/usr/local/bin/konoha """ 5-1.k license BSD author chen_ji <wakamori111 at gmail.com> """ using konoha.io.*; class User { int id; int time; int take; int out; User(int id, int time, int take, int out) { _id = id; _time = time; _take = take; _out = out; } } OPEN = 0; CLOSE = 1; UP = 2; DOWN = 3; WAIT = 4; class Elevator { int id; int floors; int movetime; int iotime; int capacity; int currenttime; boolean open; User[] users; Elevator(int id, int floors, int movetime, int iotime, int capacity) { _id = id; _floors = floors; _movetime = movetime; _iotime = iotime; _capacity = capacity; _users = []; } void declareUsers(String users_str) { foreach (String user_str in users_str.split("\n")) { String[] params = user_str.split(","); User user = new User((to int)params[0], (to int)params[1], (to int)params[2], (to int)params[3]); users.add(user); } } boolean operate(Tuple<int, int, int[]>[] steps, User[] passengers, int floor, int curtime, boolean open) { if (users.size == 0) { return true; } if (open) { int[] getonuserids = []; foreach (User user in users) { if (user.time <= curtime) { if (user.take == floor) { getonuserids.add(user.id); } } else { break; } } steps.add((CLOSE, getonuserids.size, getonuserids)); foreach (int userid in getonuserids) { foreach (User user in users) { if (user.id == userid) { passengers.add(user); } } } if (operate(steps, passengers, floor, curtime + iotime, !open)) { return true; } } int destination; if (passengers.size > 0) { destination = passengers[0].out; } else { destination = users[0].take; } if (floor != destination) { int time; if (floor < destination) { steps.add((UP, destination, new int[0])); time = (destination - floor) * movetime; } else { steps.add((DOWN, destination, new int[0])); time = (floor - destination) * movetime; } if (operate(steps, passengers, destination, curtime + time, open)) { return true; } } else { if (passengers.size > 0) { User getoffuser = passengers.pop(); steps.add((OPEN, 1, [getoffuser.id])); for (int i = 0; i < users.size; i++) { if (users[i].id == getoffuser.id) { users.remove(i); break; } } if (operate(steps, passengers, floor, curtime, !open)) { return true; } } else { if (curtime < users[0].time) { int waittime = users[0].time - curtime; steps.add((WAIT, users[0].time - curtime, new int[0])); if (operate(steps, passengers, floor, curtime + waittime, open)) { return true; } } else { steps.add((OPEN, 0, new int[0])); if (operate(steps, passengers, floor, curtime, !open)) { return true; } } } } return false; } String toStringStep(int time, int floor, String door, int[] passengers) { String step_str = ""; step_str += (to String)id + "," + (to String)time + ","; step_str += (to String)floor + "," + door + ","; for (int i = 0; i < 5; i++) { if (i < passengers.size) { step_str += (to String)passengers[i]; } else { step_str += "0"; } if (i < 4) { step_str += ","; } } return step_str; } String outputSteps(Tuple<int, int, int[]>[] steps) { String steps_str = ""; int time = 0; int floor = 1; String door = "E"; int[] passengers = []; foreach (Tuple<int, int, int[]> step in steps) { switch (step[0]) { case OPEN: door = "B"; steps_str += toStringStep(time, floor, door, step[2]) + "\n"; if (step[1] > 0) { foreach (int i in step[2]) { for (int j = 0; j < passengers.size; j++) { if (passengers[j] == i) { passengers.remove(j); continue; } } } } break; case CLOSE: time += iotime; door = "E"; steps_str += toStringStep(time, floor, door, step[2]) + "\n"; if (step[1] > 0) { foreach (int i in step[2]) { passengers.add(i); } } break; case UP: time += (step[1] - floor) * movetime; floor = step[1]; break; case DOWN: time += (floor - step[1]) * movetime; floor = step[1]; break; case WAIT: time += step[1]; break; } } return steps_str.trim(); } String work() { Tuple<int, int, int[]>[] steps = []; User[] passengers = []; operate(steps, passengers, 1, 0, false); return outputSteps(steps); } } void main(String[] args) { if (args.size != 1) { ERR << "Usage: konoha " + $script.name + " input.csv" << EOL; exit(1); } InputStream input_csv = new InputStream(args[0]); elevator = new Elevator(1, 10, 2, 5, 1); elevator.declareUsers(input_csv.read().decode().trim()); OUT << elevator.work() << EOL; }
ii)の解答
#!/usr/local/bin/konoha """ 5-2.k license BSD author chen_ji <wakamori111 at gmail.com> """ using konoha.io.*; using konoha.math.*; class User { int id; int time; int take; int out; User(int id, int time, int take, int out) { _id = id; _time = time; _take = take; _out = out; } } class Movement { int id; int time; int floor; boolean open; int[] passengers; Movement(int id, int time, int floor, boolean open, int[] passengers) { _id = id; _time = time; _floor = floor; _open = open; _passengers = passengers; } } class Checker { String input; String output; User[] users; Movement[] movements; Checker(String input, String output) { _input = input; _output = output; users = []; foreach (String user_str in input.split("\n")) { String[] params = user_str.split(","); User user = new User((to int)params[0], (to int)params[1], (to int)params[2], (to int)params[3]); _users.add(user); } movements = []; foreach (String step_str in output.split("\n")) { String[] params = step_str.split(","); Movement movement = new Movement((to int)params[0], (to int)params[1], (to int)params[2], params[3] == "B", [(to int)params[4], (to int)params[5], (to int)params[6], (to int)params[7], (to int)params[8]]); movements.add(movement); } } boolean checkUserisCorrect(User user) { boolean found = false; foreach (Movement move in movements) { if (!found) { if (user.id in? move.passengers) { if (move.time < user.time) { print user, move; return false; } if (move.floor != user.take) { print user, move; return false; } found = true; } } else { if (user.id in? move.passengers) { if (move.floor != user.out) { print user, move; return false; } return true; } } } print user; return false; } boolean checkDeclaration() { foreach (User user in users) { if (!checkUserisCorrect(user)) { print user; return false; } } return true; } boolean checkOperation() { boolean open = false; int prevfloor = 1; int prevtime = 0; foreach (Movement move in movements) { if (move.open == open) { print move; return false; } if (move.open) { if (move.floor != prevfloor && (move.time - prevtime) / Math.abs(move.floor - prevfloor) < 2) { print move; return false; } } else { if (move.time - prevtime < 5) { print move; return false; } } open = move.open; prevfloor = move.floor; prevtime = move.time; } return true; } int getUserDeclarationTime(User user) { boolean found = false; int starttime = 0; foreach (Movement move in movements) { if (!found) { if (user.id in? move.passengers) { starttime = user.time; found = true; } } else { if (user.id in? move.passengers) { return move.time - starttime; } } } return -1; } int getTotalTime() { int totaltime = 0; foreach (User user in users) { totaltime += getUserDeclarationTime(user); } return totaltime; } } void main(String[] args) { if (args.size != 2) { ERR << "Usage: konoha " + $script.name + " input.csv output.csv" << EOL; exit(1); } InputStream input_csv = new InputStream(args[0]); InputStream output_csv = new InputStream(args[1]); Checker checker = new Checker(input_csv.read().decode().trim(), output_csv.read().decode().trim()); if (checker.checkDeclaration()) { OUT << "All declarations are correctly satisfied." << EOL; } else { OUT << "Not satisfied declarations exist." << EOL; } if (checker.checkOperation()) { OUT << "All operations are correct." << EOL; } else { OUT << "Incorrect operations exist." << EOL; } OUT << "total declaration time: " << checker.getTotalTime() << EOL; }
iii)の解答
ここの途中です。
#!/usr/local/bin/konoha """ 5-3.k license BSD author chen_ji <wakamori111 at gmail.com> """ using konoha.io.*; class User { int id; int time; int take; int out; User(int id, int time, int take, int out) { _id = id; _time = time; _take = take; _out = out; } } OPEN = 0; CLOSE = 1; UP = 2; DOWN = 3; WAIT = 4; class Elevator { int id; int floors; int movetime; int iotime; int capacity; int maxtime; User[] users; Elevator(int id, int floors, int movetime, int iotime, int capacity) { _id = id; _floors = floors; _movetime = movetime; _iotime = iotime; _capacity = capacity; _maxtime = 0; _users = []; } void declareUsers(String users_str) { //OUT << "users: " << EOL; //OUT << users_str << EOL; foreach (String user_str in users_str.split("\n")) { String[] params = user_str.split(","); User user = new User((to int)params[0], (to int)params[1], (to int)params[2], (to int)params[3]); users.add(user); } } int selectDestination(User[] passengers) { int[] num_dist = new int[floors + 1]; int max_idx = 0; foreach (User user in passengers) { num_dist[user.out] += 1; if (num_dist[user.out] > num_dist[max_idx]) { max_idx = user.out; } } return max_idx; } int selectDeparture(int time) { int[] num_user = new int[floors + 1]; int max_idx = 0; foreach (User user in users) { if (user.time <= time) { num_user[user.take] += 1; if (num_user[user.take] > num_user[max_idx]) { max_idx = user.take; } } } return max_idx; } boolean operate(Tuple<int, int, int[]>[] steps, User[] passengers, int floor, int curtime, int totaltime, boolean open) { if (totaltime >= maxtime) { return false; } if (users.size == 0) { return true; } if (open) { int[] getonuserids = []; //foreach (User passenger in passengers) { // if (passenger.out == floor) { // getonuserids.add(passenger.id); // } //} foreach (User user in users) { if (user.time <= curtime) { //print user.time, curtime; if (user.take == floor && getonuserids.size < capacity&& !(user in? passengers)) { getonuserids.add(user.id); } } else { break; } } steps.add((CLOSE, getonuserids.size, getonuserids)); foreach (int userid in getonuserids) { //print users, userid; foreach (User user in users) { if (user.id == userid) { passengers.add(user); } } } if (operate(steps, passengers, floor, curtime + iotime, totaltime, !open)) { return true; } steps.pop(); for (int i = 0; i < getonuserids.size; i++) { passengers.pop(); } } int[] destinations; if (passengers.size > 0) { destination = selectDestination(passengers); } else { destination = selectDeparture(curtime); } //if (passengers.size > 0) { // destinations = makeRandomDestinations(passengers); //} else { // destinations = makeRandomDeparture(curtime); //} if (floor != destination) { int time; if (floor < destination) { steps.add((UP, destination, new int[0])); time = (destination - floor) * movetime; } else { steps.add((DOWN, destination, new int[0])); time = (floor - destination) * movetime; } //print steps, passengers, destination, open; if (operate(steps, passengers, destination, curtime + time, totaltime, open)) { return true; } steps.pop(); } else { if (passengers.size > 0) { int[] getoffuserids = []; foreach (User passenger in passengers) { if (passenger.out == floor && getoffuserids.size < capacity) { getoffuserids.add(passenger.id); } } foreach (int getoffuserid in getoffuserids) { for (int i = 0; i < passengers.size; i++) { if (passengers[i].id == getoffuserid) { passengers.remove(i); break; } } } steps.add((OPEN, getoffuserids.size, getoffuserids)); foreach (int getoffuserid in getoffuserids) { for (int i = 0; i < users.size; i++) { if (users[i].id == getoffuserid) { users.remove(i); break; } } } //print getoffuserids; //print users; //print steps, passengers, floor, curtime, open; if (operate(steps, passengers, floor, curtime, totaltime, !open)) { return true; } } else { if (curtime < users[0].time) { int waittime = users[0].time - curtime; steps.add((WAIT, users[0].time - curtime, new int[0])); if (operate(steps, passengers, floor, curtime + waittime, totaltime, open)) { return true; } } else { steps.add((OPEN, 0, new int[0])); if (operate(steps, passengers, floor, curtime, totaltime, !open)) { return true; } // steps.add((CLOSE, 1, [users[0].id])); // passengers.add(users[0]); // operate(steps, passengers, floor, curtime + iotime, !open); } } } return false; } String toStringStep(int time, int floor, String door, int[] passengers) { String step_str = ""; step_str += (to String)id + "," + (to String)time + ","; step_str += (to String)floor + "," + door + ","; for (int i = 0; i < 5; i++) { if (i < passengers.size) { step_str += (to String)passengers[i]; } else { step_str += "0"; } if (i < 4) { step_str += ","; } } return step_str; } String outputSteps(Tuple<int, int, int[]>[] steps) { String steps_str = ""; int time = 0; int floor = 1; String door = "E"; int[] passengers = []; //for (int index = 0; index < steps.size; index++) { // Tuple<int, int, int[]> step = steps[index]; foreach (Tuple<int, int, int[]> step in steps) { switch (step[0]) { case OPEN: door = "B"; steps_str += toStringStep(time, floor, door, step[2]) + "\n"; if (step[1] > 0) { foreach (int i in step[2]) { for (int j = 0; j < passengers.size; j++) { if (passengers[j] == i) { passengers.remove(j); continue; } } } } break; case CLOSE: time += iotime; door = "E"; steps_str += toStringStep(time, floor, door, step[2]) + "\n"; if (step[1] > 0) { foreach (int i in step[2]) { passengers.add(i); } } break; case UP: time += (step[1] - floor) * movetime; floor = step[1]; break; case DOWN: time += (floor - step[1]) * movetime; floor = step[1]; break; case WAIT: time += step[1]; break; } } return steps_str.trim(); } String work() { Tuple<int, int, int[]>[] steps = []; User[] passengers = []; _maxtime = 100; while (!operate(steps, passengers, 1, 0, 0, false)) { _maxtime += 100; } //for (int i = 0; i < steps.size; i++) { // print i, steps[i]; //} //print steps; return outputSteps(steps); } } void main(String[] args) { if (args.size != 1) { ERR << "Usage: konoha " + $script.name + " input.csv" << EOL; exit(1); } InputStream input_csv = new InputStream(args[0]); elevator = new Elevator(1, 10, 2, 5, 5); elevator.declareUsers(input_csv.read().decode().trim()); OUT << elevator.work() << EOL; }
実行結果
i)の解答
$ ./5-1.k input_i.csv 1,226,3,B,0,0,0,0,0 1,231,3,E,1,0,0,0,0 1,233,4,B,1,0,0,0,0 1,238,4,E,0,0,0,0,0 1,263,2,B,0,0,0,0,0 1,268,2,E,2,0,0,0,0 1,270,3,B,2,0,0,0,0 1,275,3,E,0,0,0,0,0 1,282,1,B,0,0,0,0,0 1,287,1,E,3,0,0,0,0 1,301,8,B,3,0,0,0,0 1,306,8,E,0,0,0,0,0 1,466,5,B,0,0,0,0,0 1,471,5,E,4,0,0,0,0 1,475,3,B,4,0,0,0,0 1,480,3,E,0,0,0,0,0 1,499,10,B,0,0,0,0,0 1,504,10,E,5,0,0,0,0 1,512,6,B,5,0,0,0,0 1,517,6,E,0,0,0,0,0 1,544,7,B,0,0,0,0,0 1,549,7,E,6,0,0,0,0 1,561,1,B,6,0,0,0,0 1,566,1,E,0,0,0,0,0 1,593,1,B,0,0,0,0,0 1,598,1,E,7,0,0,0,0 1,616,10,B,7,0,0,0,0 1,621,10,E,0,0,0,0,0 1,663,10,B,0,0,0,0,0 1,668,10,E,8,0,0,0,0 1,684,2,B,8,0,0,0,0 1,689,2,E,0,0,0,0,0 1,691,3,B,0,0,0,0,0 1,696,3,E,9,0,0,0,0 1,700,5,B,9,0,0,0,0 1,705,5,E,0,0,0,0,0 1,803,4,B,0,0,0,0,0 1,808,4,E,10,0,0,0,0 1,818,9,B,10,0,0,0,0
ii)の解答
$ ./5-2.k input_i.csv output_i.csv All declarations are correctly satisfied. All operations are correct. total declaration time: 153
iii)の解答
$ ./5-3.k input_iii_iv.csv 1,46,4,B,0,0,0,0,0 1,51,4,E,1,0,0,0,0 1,61,9,B,1,0,0,0,0 1,66,9,E,0,0,0,0,0 1,106,10,B,0,0,0,0,0 1,111,10,E,2,0,0,0,0 1,117,7,B,2,0,0,0,0 1,122,7,E,0,0,0,0,0 1,148,6,B,0,0,0,0,0 1,153,6,E,3,0,0,0,0 1,157,8,B,3,0,0,0,0 1,162,8,E,4,0,0,0,0 1,164,9,B,4,0,0,0,0 1,169,9,E,0,0,0,0,0 1,179,4,B,0,0,0,0,0 1,184,4,E,5,0,0,0,0 1,188,6,B,5,0,0,0,0 1,193,6,E,6,0,0,0,0 1,199,9,B,6,0,0,0,0 1,204,9,E,0,0,0,0,0 1,218,2,B,0,0,0,0,0 1,223,2,E,7,11,0,0,0 1,237,9,B,7,0,0,0,0 1,242,9,E,0,0,0,0,0 1,254,3,B,11,0,0,0,0 1,259,3,E,8,13,0,0,0 1,261,4,B,8,13,0,0,0 1,266,4,E,14,0,0,0,0 1,268,3,B,14,0,0,0,0 1,273,3,E,0,0,0,0,0 1,277,5,B,0,0,0,0,0 1,282,5,E,9,0,0,0,0 1,284,4,B,9,0,0,0,0 1,289,4,E,15,0,0,0,0 1,297,8,B,15,0,0,0,0 1,302,8,E,0,0,0,0,0 1,306,6,B,0,0,0,0,0 1,311,6,E,10,16,0,0,0 1,321,1,B,10,0,0,0,0 1,326,1,E,17,0,0,0,0 1,340,8,B,16,0,0,0,0 1,345,8,E,0,0,0,0,0 1,349,10,B,17,0,0,0,0 1,354,10,E,12,19,0,0,0 1,364,5,B,12,0,0,0,0 1,369,5,E,24,0,0,0,0 1,375,2,B,19,0,0,0,0 1,380,2,E,25,28,0,0,0 1,382,1,B,24,25,0,0,0 1,387,1,E,22,0,0,0,0 1,405,10,B,28,0,0,0,0 1,410,10,E,26,0,0,0,0 1,416,7,B,22,0,0,0,0 1,421,7,E,0,0,0,0,0 1,423,6,B,26,0,0,0,0 1,428,6,E,23,0,0,0,0 1,432,4,B,23,0,0,0,0 1,437,4,E,30,0,0,0,0 1,441,6,B,30,0,0,0,0 1,446,6,E,0,0,0,0,0 1,450,8,B,0,0,0,0,0 1,455,8,E,29,31,32,37,0 1,465,3,B,32,37,0,0,0 1,470,3,E,18,20,21,39,0 1,476,6,B,20,21,0,0,0 1,481,6,E,0,0,0,0,0 1,483,5,B,31,39,0,0,0 1,488,5,E,33,35,41,43,0 1,494,8,B,18,41,0,0,0 1,499,8,E,0,0,0,0,0 1,513,1,B,29,43,0,0,0 1,518,1,E,38,47,0,0,0 1,530,7,B,33,0,0,0,0 1,535,7,E,46,51,0,0,0 1,539,5,B,47,46,0,0,0 1,544,5,E,56,0,0,0,0 1,548,3,B,35,0,0,0,0 1,553,3,E,48,57,58,59,0 1,563,8,B,38,57,58,0,0 1,568,8,E,62,64,0,0,0 1,580,2,B,56,59,0,0,0 1,585,2,E,40,44,61,65,0 1,589,4,B,51,62,0,0,0 1,594,4,E,53,0,0,0,0 1,600,7,B,44,61,0,0,0 1,605,7,E,63,0,0,0,0 1,617,1,B,48,0,0,0,0 1,622,1,E,66,0,0,0,0 1,632,6,B,53,66,0,0,0 1,637,6,E,45,50,52,54,60 1,645,10,B,40,60,0,0,0 1,650,10,E,55,69,75,0,0 1,658,6,B,55,69,75,0,0 1,663,6,E,68,73,0,0,0 1,667,4,B,63,68,0,0,0 1,672,4,E,70,0,0,0,0 1,678,1,B,52,73,0,0,0 1,683,1,E,0,0,0,0,0 1,685,2,B,50,70,0,0,0 1,690,2,E,72,81,0,0,0 1,698,6,B,72,81,0,0,0 1,703,6,E,0,0,0,0,0 1,709,3,B,64,0,0,0,0 1,714,3,E,76,78,83,0,0 1,722,7,B,45,78,0,0,0 1,727,7,E,74,0,0,0,0 1,731,5,B,65,0,0,0,0 1,736,5,E,67,71,79,0,0 1,740,3,B,74,67,0,0,0 1,745,3,E,0,0,0,0,0 1,755,8,B,54,71,0,0,0 1,760,8,E,77,0,0,0,0 1,764,10,B,76,0,0,0,0 1,769,10,E,84,89,0,0,0 1,785,2,B,83,0,0,0,0 1,790,2,E,87,0,0,0,0 1,800,7,B,84,87,0,0,0 1,805,7,E,93,0,0,0,0 1,809,9,B,79,0,0,0,0 1,814,9,E,27,34,36,42,49 1,830,1,B,77,27,0,0,0 1,835,1,E,94,0,0,0,0 1,847,7,B,42,49,0,0,0 1,852,7,E,95,96,0,0,0 1,856,5,B,34,94,0,0,0 1,861,5,E,0,0,0,0,0 1,865,3,B,89,0,0,0,0 1,870,3,E,88,90,91,0,0 1,872,4,B,90,91,0,0,0 1,877,4,E,0,0,0,0,0 1,885,8,B,93,0,0,0,0 1,890,8,E,0,0,0,0,0 1,894,10,B,36,0,0,0,0 1,899,10,E,0,0,0,0,0 1,915,2,B,95,0,0,0,0 1,920,2,E,0,0,0,0,0 1,928,6,B,96,0,0,0,0 1,933,6,E,92,99,0,0,0 1,935,5,B,88,92,0,0,0 1,940,5,E,98,0,0,0,0 1,948,1,B,99,98,0,0,0 1,953,1,E,0,0,0,0,0 1,969,9,B,0,0,0,0,0 1,974,9,E,80,82,85,86,97 1,988,2,B,82,85,0,0,0 1,993,2,E,0,0,0,0,0 1,1003,7,B,86,97,0,0,0 1,1008,7,E,0,0,0,0,0 1,1010,8,B,80,0,0,0,0 1,1015,8,E,0,0,0,0,0 1,1023,4,B,0,0,0,0,0 1,1028,4,E,100,0,0,0,0 1,1040,10,B,100,0,0,0,0
追記 (2012/02/20)
匿名さんより、コメント欄から「iiiの回答の定員が守られていない」と間違いのご指摘を頂きました。ありがとうございます。
どうやら、「最大乗車人数５人」という条件を、「一度の開閉で乗車／降車できる最大人数５人」と勘違いしていたようです。
とりあえず、以下の修正で定員が守られるようになりました。あわせて、ii)の回答も修正しています。
diff --git a/5/5-2.k b/5/5-2.k index 82cc0b2..deeb3a6 100755 --- a/5/5-2.k +++ b/5/5-2.k @@ -9,6 +9,8 @@ author chen_ji <wakamori111 at gmail.com> using konoha.io.*; using konoha.math.*; +MAX_PASSENGER_NUM = 5 + class User { int id; @@ -112,6 +114,7 @@ class Checker boolean open = false; int prevfloor = 1; int prevtime = 0; + int[] passengers = []; foreach (Movement move in movements) { if (move.open == open) { print move; @@ -123,11 +126,30 @@ class Checker print move; return false; } + foreach (int passenger_id in move.passengers) { + if (passenger_id == 0) continue; + if (passenger_id in? passengers) { + passengers.remove(passengers.indexOf(passenger_id)); + } else { + print move; + return false; + } + } } else { if (move.time - prevtime < 5) { print move; return false; } + foreach (int passenger_id in move.passengers) { + if (passenger_id == 0) continue; + if (!(passenger_id in? passengers) && + passengers.size < MAX_PASSENGER_NUM) { + passengers.add(passenger_id); + } else { + print move; + return false; + } + } } open = move.open; prevfloor = move.floor; diff --git a/5/5-3.k b/5/5-3.k index 4b0930f..b9dd27c 100755 --- a/5/5-3.k +++ b/5/5-3.k @@ -105,7 +105,8 @@ class Elevator foreach (User user in users) { if (user.time <= curtime) { //print user.time, curtime; - if (user.take == floor && getonuserids.size < capacity&& + if (user.take == floor && + getonuserids.size + passengers.size < capacity && !(user in? passengers)) { getonuserids.add(user.id); }
GO FOR ITに挑戦 (4) 旋律に隠された特徴
こんばんは、chen_jiです。
GO FOR ITへの挑戦も、残すところ後二つとなりました。そして、コンテストの締め切りまで、残すところ12時間を切りました。果たして全部解けるのでしょうか…。
4回目の本日は、「4) 旋律に隠された特徴」を解いてみました。（正確には解ききれなかったのですが。）
回を増すごとに難易度が上がっている気がします。後ろから順番に解いていったほうが良かったのかもしれません。
問題
本家のページをご参照下さい。
解答
今回は、すべてKonohaScriptでコーディングしました。
i), ii)の解答
Aの譜面と、Bの譜面の特徴量が異なり、Aの譜面とCの譜面の特徴量が同一となるようなプログラムを書きます。
まず、３つの譜面を見て、どの成分を特徴量に反映させるのか考えなければなりませんが、親切なことに、問題分の中にヒントが書かれています。
ヒント) 隣り合う音符同士の関係に注目してください。
隣り合う音符に注目すると良いらしいので、前音とのピッチの差分を求め、その合計値を算出することにしました。すると、もっともらしい値が出たのですが、AとBの特徴量が一致してしまいました。
そこで、差分の絶対値の合計値を算出することにして、さらに、全音が休符の場合は、もう一つ前の音との差分を考えることにしました。すると、AとCの特徴量が一致したので、これでよしということにしました。
#!/usr/local/bin/konoha """ 4-1and2.k license BSD author chen_ji <wakamori111 at gmail.com> """ using konoha.io.*; using konoha.math.*; // accidental string SHARP = "s"; DSHARP = "x"; FLAT = "b"; DFLAT = "d"; // note class class Note { boolean rest; boolean dotted; int pitch; int length; String accidental; Note(String pitch, String length, String accidental) { if (pitch == "") { _rest = true; _pitch = 0; } else { _rest = false; _pitch = (to int)pitch; } if (length.endsWith(".")) { _dotted = true; _length = (to int)length.substring(0, length.size - 1); } else { _dotted = false; _length = (to int)length; } if (accidental == "") { _accidental = ""; } else { _accidental = accidental; } considerAccidental(); considerLength(); } void considerAccidental() { int diff = 0; switch (pitch % 7) { case 0: case 1: diff = 0; break; case 2: case -1: diff = 1; break; case 3: case 4: case -2: diff = 2; break; case 5: case -3: case -4: diff = 3; break; case 6: case -5: diff = 4; break; case -6: diff = 5; break; } if (pitch >= 0) { _pitch += (pitch / 7) * 5 + diff; } else { _pitch -= ((-pitch / 7) * 5 + diff); } switch (accidental) { case SHARP: _pitch += 1; break; case DSHARP: _pitch += 2; break; case FLAT: _pitch -= 1; break; case DFLAT: _pitch -= 2; break; default: break; } } void considerLength() { _length = 64 / length; if (dotted) { _length *= 1.5; } } } // score class class Score { InputStream sfile; Note[] notes; Score(Path scorefile) { _sfile = new InputStream(scorefile); createScore(); } void createScore() { String input = sfile.read().decode().trim(); String[] notes_str = input.split(","); notes = []; foreach (String note_str in notes_str) { String[] attr = note_str.split(":"); notes.add(new Note(attr[0], attr[1], attr[2])); } } } // extractor class class Extractor { Score score; Extractor(Score score) { _score = score; } int extractFeature() { int feature_val = 0; Note pre_note = null; foreach (Note note in score.notes) { if (note.rest) { continue; } else if (pre_note != null) { feature_val += Math.abs(note.pitch - pre_note.pitch); } pre_note = note; } return feature_val; } } void main(String[] args) { if (args.size != 1) { ERR << "Usage: konoha " + $script.name + " input.score" << EOL; exit(1); } Score score = new Score(args[0]); Extractor extractor = new Extractor(score); OUT << "feature value: " << extractor.extractFeature() << EOL; }
iii)の解答
#!/usr/local/bin/konoha """ 4-3.k license BSD author chen_ji <wakamori111 at gmail.com> """ using konoha.io.*; using konoha.math.*; // accidental string SHARP = "s"; DSHARP = "x"; FLAT = "b"; DFLAT = "d"; // note class class Note { boolean rest; boolean dotted; int pitch; int length; String rawpitch; String rawlength; String accidental; Note(String pitch, String length, String accidental) { if (pitch == "") { _rest = true; _pitch = 0; } else { _rest = false; _pitch = (to int)pitch; } _rawpitch = pitch; if (length.endsWith(".")) { _dotted = true; _length = (to int)length.substring(0, length.size - 1); } else { _dotted = false; _length = (to int)length; } _rawlength = length; _accidental = accidental; considerAccidental(); considerLength(); } void considerAccidental() { int diff = 0; switch (pitch % 7) { case 0: case 1: diff = 0; break; case 2: case -1: diff = 1; break; case 3: case 4: case -2: diff = 2; break; case 5: case -3: case -4: diff = 3; break; case 6: case -5: diff = 4; break; case -6: diff = 5; break; } if (pitch >= 0) { _pitch += (pitch / 7) * 5 + diff; } else { _pitch -= ((-pitch / 7) * 5 + diff); } switch (accidental) { case SHARP: _pitch += 1; break; case DSHARP: _pitch += 2; break; case FLAT: _pitch -= 1; break; case DFLAT: _pitch -= 2; break; default: break; } } void considerLength() { _length = 64 / length; if (dotted) { _length *= 1.5; } } String toString() { return rawpitch + ":" + rawlength + ":" + accidental; } } // score class class Score { InputStream sfile; Note[] notes; Score(Path scorefile) { if ((to String)scorefile != "") { _sfile = new InputStream(scorefile); createScore(); } } void createScore() { String input = sfile.read().decode().trim(); String[] notes_str = input.split(","); notes = []; foreach (String note_str in notes_str) { String[] attr = note_str.split(":"); notes.add(new Note(attr[0], attr[1], attr[2])); } } String toString() { String score_str = ""; foreach (Note note in notes) { score_str += note.toString(); score_str += ","; } if (score_str != "") { score_str = score_str.substring(0, score_str.size - 1); } return score_str; } } class Composer { int start_pitch; int end_pitch; int measure_min; int measure_max; int feature_val; Composer(int start_pitch, int end_pitch, int measure_min, int measure_max, int feature_val) { _start_pitch = start_pitch; Note end_note = new Note((to String)end_pitch, "1", ""); _end_pitch = end_note.pitch; _measure_min = 64 * measure_min; _measure_max = 64 * measure_max; _feature_val = feature_val; } Note[] generateRandomNotes() { Note[] notes = []; Tuple<int, String>[] rand_pitches = []; for (int i = -6; i < 8; i++) { rand_pitches.add((i, "")); if (i == -5 || i == -4 || i == -2 || i == -1 || i == 0) { rand_pitches.add((i, FLAT)); } else if (i == 1 || i == 2 || i == 4 || i == 5 || i == 6) { rand_pitches.add((i, SHARP)); } } rand_pitches.shuffle(); foreach (Tuple<int, String> pitch in rand_pitches) { String pitch_str; boolean isRest; if (pitch[0] == 7) { pitch_str = ""; isRest = true; } else { pitch_str = (to String)pitch[0]; isRest = false; } Note note = new Note(pitch_str, generateLength(isRest), pitch[1]); notes.add(note); } return notes; } boolean setNote(Note[] notes, int total_val, int total_length) { if (total_val > feature_val || total_length > measure_max) { return false; } if (total_length >= measure_min) { if (notes[notes.size - 1].pitch == end_pitch) { if (total_val == feature_val) { return true; } } else { return false; } } Note[] rand_notes = generateRandomNotes(); foreach (Note note in rand_notes) { Note pre_note = notes[notes.size - 1]; int diff = 0; if (note.rest) { if (pre_note.rest) { continue; } diff = 0; } else { if (pre_note.rest) { pre_note = notes[notes.size - 2]; } diff = Math.abs(note.pitch - pre_note.pitch); } notes.add(note); if (setNote(notes, total_val + diff, total_length + note.length)) { return true; } notes.pop(); } return false; } Score generate() { Note start_note = new Note((to String)start_pitch, generateLength(), ""); Note[] notes = [start_note]; setNote(notes, 0, start_note.length); Score score = new Score(); score.notes = notes; return score; } String generateLength(boolean isRest) { int count = Int.random(6); int length = 1; for (int i = 0; i < count; i++) { length *= 2; } if (isRest) { return (to String)length; } return (to String)length + ((Int.random(2) == 0) ? "." : ""); } } void main(String[] args) { int feature_val = 51; if (args.size == 1) { feature_val = (to int)args[0]; } Composer composer = new Composer(-2, -2, 3, 4, feature_val); String str = composer.generate().toString(); OUT << str << EOL; }
実行結果
i)の解答
こちらのページで指定された文字列を入力として受け付けるようになっています。Aの譜面を書き込んだファイルa.scoreを用意して、以下のコマンドを実行します。
$ ./4-1and2.k a.score feature value: 24 $ ./4-1and2.k b.score feature value: 26 $ ./4-1and2.k c.score feature value: 24
このように、
- Aの特徴量≠Bの特徴量
- Aの特徴量=Cの特徴量
という、問題文の条件が満たされていることが分かります。
ii)の解答
i)の解答と同様のプログラムを実行させ、D、E、Fの譜面を同様に入力してみます。
$ ./4-1and2.k d.score feature value: 26 $ ./4-1and2.k e.score feature value: 28 $ ./4-1and2.k f.score feature value: 22
よって、「Bの特徴量＝Dの特徴量＝26」の関係が成り立つので、答えは「D」ということになります。
iii)の解答
この問題に相当手こずりました。私の最終的な結論としては、答えは「ない」というのが答えです。（間違ってたらごめんなさい。）
まず、Gの譜面の特徴量をこれまでと同様に求めます。
$ ./4-1and2.k g.score feature value: 51
特徴量が「51」となりましたので、問題分の条件に合致する譜面で、さらに特徴量が51となればよさそうです。
しかし、ここで問題があります。それは、条件の２つ目の項目
譜面上の位置 -2 で与えられるGの音ではじまり、同じ音で終わります。
という点です。つまり、最初の音符と最後の音符が同じピッチでなければなりません。
ところが、私の特徴量の求め方は、「全音とのピッチの差分の絶対値の合計値」を求める方法です。そうなると、開始音と終了音のピッチが一致している以上、差分の絶対値の合計値は、必ず「偶数」となってしまいます。
したがって、上記のiii)の解答のプログラムは、実行すると終了しません（笑）
しかもたちの悪いことに、特に考えなしに、単純なバックトラックで譜面のパターンを求めているため、探索自体に時間がかかります。特徴量に奇数を指定したとしても、結構時間のかかるときがあります。その結果、解答が出ないのはアルゴリズムが悪いからだと考え続け、この結論に至るまでに無駄な時間を費やしてしまいました。
一応、実行結果を以下に載せます。
$ ./4-3.k 51 （答えは出ません）
特徴量を「51」から「50」に変更してみます。運がよければすぐに解が出ますが、たまに時間がかかります。
$ ./4-3.k 50 -2:2.:,4:16:,6:2:s,-1:16:b,-6:16:,-4:8.:b,-6:16.:,-2:32:,:4:,-2:2:,-2:1: $ ./4-3.k 50 > out.score && ./4-1and2.k out.score feature value: 50
GO FOR ITに挑戦 (3) 暗号検索の高速化
こんばんは、chen_jiです。
前回に引き続き、GO FOR ITに挑戦中です。今回は、「3) 暗号検索の高速化」を解いてみました。
ダ・ヴィンチ・コードはまだ観たことがないのですが、この問題のように、縦読み的な暗号が隠されているのでしょうか？ちょっと興味が湧きました。
今回は、問題文が長文ですので、引用は割愛します。問題の詳細は本家をご覧下さい。
解答
i)の解答
文字列探索のアルゴリズムに、Sundayのアルゴリズム（別名：quick search）を採用しました。*1
読みやすさを重視してとのことですが、読みやすいコードを書くのは難しいので、まずは最初に動作したpythonのコードを以下に載せます。
#!/usr/bin/env python # -*- coding: utf-8 -*- """ 3-1.py license BSD author chen_ji <wakamori111 at gmail.com> """ import sys # table size (ascii) CSIZE = 256 # make displacement table def make_qs_table(pattern, size): qs_table = [size + 1] * CSIZE for i in xrange(size): qs_table[ord(pattern[i])] = size - i return qs_table # quick search def qs_search(buff, pattern): n = len(buff) m = len(pattern) qs_table = make_qs_table(pattern, m) i = 0 while i < n - m: j = 0 while j < m: if buff[i + j] != pattern[j]: break j += 1 if j == m: # found return i else: i += qs_table[ord(buff[i + m])] if buff[i:] == pattern: return i return -1 def find(buff, word, skip_count): l = len(buff) for column in xrange(skip_count): search_buff = '' cur = column while cur < l: search_buff += buff[cur] cur += skip_count r = qs_search(search_buff, word) if r >= 0: print str(skip_count) + ',' + str(r * skip_count + column + 1) return True return False if __name__ == '__main__': args = sys.argv if len(args) != 2: print 'Usage: ' + args[0] + ' keyword' sys.exit(1) keyword = args[1] print 'keyword:', keyword rand_str = raw_input('search string: ') l = len(rand_str) print print "order:", for i in xrange(l): if find(rand_str, keyword, i + 1): break rkeyword = keyword[::-1] print "reverse order:", for i in xrange(l): if find(rand_str, rkeyword, i + 1): break
ii)の解答
アルゴリズムを工夫して、高速化するということなので、以下の点について高速化を行いました。
一点目は、今までpythonでプロトタイピングしていたところを、我々の実装言語であるKonohaScriptに置き換えたことです。アルゴリズムの高速化ではありませんが、静的型付けによる最適化である程度の実行速度の改善を達成出来ました。
二点目は、探索対象の文字列マトリックスを、これまで縦向きに結合して、新たな文字列を生成していたところを、インデックスの計算に置き換えたことで、オブジェクトの生成数を減少させたことです。これもアルゴリズムの改善というよりは、言語の使い方の改善といったところですが、それなりに高速化しました。
本来ならば、文字列探索のアルゴリズムをより高速なものに置き換えたり、逆向きの検索を考慮して検索するべきだと思うのですが、最初にquick searchを選択してしまったため、アルゴリズムの改善はまた時間のあるときに行いたいと思います。
作成したKonohaScriptのプログラムを以下に載せます。
#!/usr/local/bin/konoha """ 3-2.k license BSD author chen_ji <wakamori111 at gmail.com> """ using konoha.io.*; // table size (ascii) CSIZE = 256 // make displacement table int[] make_qs_table(String pattern, int size) { int[] qs_table = new int[CSIZE]; qs_table.setAll(size + 1); for (int i = 0; i < size; i++) { qs_table[(to int)pattern[i].encode()[0]] = size - i; } return qs_table; } int[] qs_table; // quick search int qs_search(String buff, int column, int skip_count, String pattern) { int i = column; int n = 0; while (i < buff.size) { n++; i += skip_count; } int m = pattern.size; int i = 0; while (i < n - m) { int j = 0; while (j < m) { if (buff[column + (i + j) * skip_count] != pattern[j]) { break; } j++; } if (j == m) { // found return i; } else { i += qs_table[(to int)buff[column + (i + m) * skip_count].encode()[0]]; } } int j = column + i * skip_count; String last = ""; while (j < buff.size) { last += buff[j]; j += skip_count; } if (last == pattern) { return i; } return -1; } // find pattern boolean find(String buff, String word, int skip_count) { for (int column = 0; column < skip_count; column++) { int r = qs_search(buff, column, skip_count, word); if (r >= 0) { OUT << skip_count << "," << (r * skip_count + column + 1) << EOL; return true; } } return false; } void main(String[] args) { if (args.size != 1) { OUT << "Usage: " + $script.name + " keyword" << EOL; System.exit(1); } String keyword = args[0]; qs_table = make_qs_table(keyword, keyword.size); OUT << "keyword: " << keyword << EOL; OUT << "search string: "; OUT.flush(); String rand_str = IN.read().decode(); int l = rand_str.size; OUT << EOL << "order: "; OUT.flush(); for (int i = 1; i <= l; i++) { if (find(rand_str, keyword, i)) { break; } } String rkeyword = ""; for (int i = keyword.size - 1; i >= 0; i--) { rkeyword += keyword[i]; } qs_table = make_qs_table(rkeyword, rkeyword.size); OUT << "reverse order: "; OUT.flush(); for (int i = 1; i <= l; i++) { if (find(rand_str, rkeyword, i)) { break; } } }
実行結果
問題文の方法で生成したアスキー文字列rand_strを書き込んだファイルrand_str.txtを用意し、パイプで渡す形で実行します。
ついでにtimeコマンドで、キーワード「alpha」を検索したときの実行時間を測ってみます。
i)の解答
$ time cat rand_str.txt | ./3-1.py alpha keyword: alpha search string: order: 81,7262 reverse order: 30,101572 cat rand_str.txt 0.00s user 0.00s system 9% cpu 0.018 total ./3-1.py alpha 9.51s user 0.01s system 99% cpu 9.536 total
ii)の解答
$ time cat rand_str.txt | ./3-2.k alpha keyword: alpha search string: order: 81,7262 reverse order: 30,101572 cat rand_str.txt 0.00s user 0.00s system 16% cpu 0.016 total ./3-2.k alpha 5.46s user 0.03s system 99% cpu 5.496 total
番外編
ii)と同じプログラムを、KonohaScriptのLLVMバックエンドで実行してみたところ、以下のようになりました。
（KonohaScriptのLLVMバックエンドについては、id:atdxfe:20110908:1315492807に詳しいです。）
$ time cat rand_str.txt | kl ./3-2.k alpha keyword: alpha search string: order: 81,7262 reverse order: 30,101572 cat rand_str.txt 0.00s user 0.00s system 1% cpu 0.151 total kl ./3-2.k alpha 3.04s user 0.04s system 99% cpu 3.080 total
LLVMの最適化により、更に高速化したいみたいです。
*1: Sunday, Daniel M. A very fast substring search algorithm. (http://dl.acm.org/citation.cfm?id=79184)
GO FOR ITに挑戦 (2) 実数の階乗
こんばんは、chen_jiです。
前回に引き続き、「GO FOR IT」の2問目を解いてみました。
問題
2) 実数の階乗
ある検索サイトに5!と入力するとその計算結果である120が表示されます。
その検索サイトに2.5!と入力するとなんと3.32335097と表示されます。
さらにその検索サイトに(-1.9)!と入力すると-10.5705641と表示されます。
きっとそれらの仕組みはとても難しくて企業秘密に違いないので是非ともこれらを実行するプログラムを作ってほしい。
ただし、君のPCは古いのでネットワークや便利で高度な数学関数は入っていません。
入っている数学関数はsin,cos,tan,log,pow,floorなどの初歩的な関数のみです、残念ながら。i)入力された整数a(0<=a<=10)の階乗を求めるプログラムを作ってください。
ii)入力された実数a(0<=a<=10)の階乗を求めるプログラムを作ってください。
iii)入力された実数a(-1.9<=a<=-1.1)の階乗を求めるプログラムを作ってください。
解答
i)の解答
再帰を使って簡単に書けました。
#!/usr/bin/env python # -*- coding: utf-8 -*- """ 2-1.py license BSD author chen_ji <wakamori111 at gmail.com> """ import math import random import sys def fact(n): if n <= 1: return 1 else: return n * fact(n - 1) if __name__ == '__main__': a = random.randint(0, 10) args = sys.argv if len(args) == 2: a = int(args[1]) print "a:", a print "fact(a):", fact(a)
ii), iii)の解答
こちらは、使用できる数学関数に制限があるため、悩みましたが、結局
を誤差1e-10の範囲で計算し、それらの結果を用いて「ワイエルシュトラスの乗積表示」よりガンマ関数を計算して求める方針をとりました。
総乗の計算時にスタックオーバーフローを引き起こさないために、末尾再帰最適化を使っています。
#!/usr/bin/env python # -*- coding: utf-8 -*- """ 2-2and3.py license BSD author chen_ji <wakamori111 at gmail.com> """ import math import random import sys class tail_recursive(object): """tail recursion decorator""" def __init__(self, func): self.func = func self.firstcall = True self.CONTINUE = object() def __call__(self, *args, **kwd): if self.firstcall: func = self.func CONTINUE = self.CONTINUE self.firstcall = False try: while True: result = func(*args, **kwd) if result is CONTINUE: # update arguments args, kwd = self.argskwd else: # last call return result finally: self.firstcall = True else: # return the arguments of the tail call self.argskwd = args, kwd return self.CONTINUE @tail_recursive def fact(n, acc=1): if n == 0: return acc else: return fact(n - 1, acc * n) def term(n): return 1 / n - math.log((n + 1) / n) def sigma(f, s, diff=1e-10): r = 0 i = s while True: d = f(float(i)) if d < diff: return r else: r += d i += 1 def euler(): return sigma(lambda n: 1 / n - math.log((n + 1) / n), 1) def napier(): return sigma(lambda n: 1 / fact(n), 0) # Napier's constant E = napier() # Euler's constant GAMMA = euler() @tail_recursive def product(n, x, acc=1): """Calculate product x from 1 to n""" if n == 0: return acc else: return product(n - 1, x, acc * f(x, n)) def f(x, m): return (1 + x / m) * (E ** (-x / m)) def rfact(x): return 1 / ((x + 1) * (E ** (GAMMA * (x + 1))) * product(1000000, x + 1)) if __name__ == '__main__': a = random.uniform(0, 10) args = sys.argv if len(args) == 2: a = float(args[1]) print "a:", a print "rfact(a):", rfact(a)
実行結果
i)の場合
$ ./2-1.py 8 a: 8 fact(a): 40320
ii), iii)の場合
誤差0.01%程度には収まっているみたいです。
$ ./2-2and3.py 2.5 a: 2.5 rfact(a): 3.32341286338 $ ./2-2and3.py -1.9 a: -1.9 rfact(a): -10.5704925589
