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); }
