emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
SimpleRouter(赛前模拟题)

Problem Statement
????
A router's job is to route packets of information to the correct computer. In addition, a router may throw out some packets, or handle the packets on its own. In this problem, you are to implement the software for a simple, rule-based router. Each rule in the router will take one of the following forms (quotes and angle brackets for clarity only):
"ACCEPT <IP_RANGE> <PORT_RANGE>"
"REJECT <IP_RANGE> <PORT_RANGE>"
"FORWARD <IP_RANGE> <PORT_RANGE> <DESTINATION> (<PORT>)"
Each <IP_RANGE> is a string of exactly four <NUMBER_RANGE>s, separated by periods, and each <PORT_RANGE> consists of a single <NUMBER_RANGE>. A <NUMBER_RANGE> can take one of three forms. It may be a single integer, a range of integers (in the form "<LOWER_LIMIT>-<UPPER_LIMIT>", where both limits are inclusive), or an asterisk. <DESTINATION> consists of exactly 4 integers, with 3 periods separating them (an IP address). If a FORWARD rule has a <PORT_RANGE> with only a single integer, then the <DESTINATION> may optionally be followed by a single integer, <PORT>.  Each rule tells the router what to do with a packet of information if that packet comes from an IP in the rule's <IP_RANGE> and to a port in the rule's <PORT_RANGE>. An IP is in the <IP_RANGE> if each <NUMBER_RANGE> in the <IP_RANGE> matches the corresponding number in the IP. A <NUMBER_RANGE> matches a number, N, if the <NUMBER_RANGE> is an asterisk, if it is a single number that is the same as N, or if it is a range and N falls within the range, inclusive. The rules for matching a <PORT_RANGE> are the same.  If a rule tells the router to forward the packet, then it should be forwarded to <DESTINATION>. If no <PORT> is specified, the packet should be forwarded to the same port it was received on. Otherwise, it should be forwarded to the specified port. If multiple rules apply to a packet, you should use the one that comes last in the input. If no rules apply, REJECT the packet.  You will be given a String[], rules, representing a number of rules that the router is to follow. You will also be given a String[], packets, each of whose elements represents a packet of data in the form "<SOURCE_IP> <PORT>" (<SOURCE_IP> is formatted the same as <DESTINATION>). You should return a String[] with one element per packet, specifying what to do with the packet with the same index in the input as the return. Each element of the return should be either "ACCEPT", "REJECT", or "<IP>:<PORT>", where <IP> and <PORT> represent the location to which the packet should be forwarded.
Definition
????
Class:
SimpleRouter
Method:
route
Parameters:
String[], String[]
Returns:
String[]
Method signature:
String[] route(String[] rules, String[] packets)
(be sure your method is public)
????

Notes
-
While the input may have extraneous leading zeros, your return should not.
Constraints
-
rules will contain between 1 and 50 elements, inclusive.
-
Each element of rules will be formatted as described in the problem statement.
-
packets will contain between 1 and 50 elements, inclusive.
-
Each element of packets will be formatted as described in the problem statement.
-
Each of the four numbers in an IP address, or a number range in an IP address will be between 0 and 255, inclusive.
-
Each port or number in a port range will be between 1 and 65535 inclusive.
-
In any <NUMBER_RANGE> with two numbers, <LOWER_LIMIT> will be less than or equal to <UPPER_LIMIT>.
Examples
0)

????
{"FORWARD 192.168.000.* 001-100 192.168.0.10",
 "FORWARD 192.168.0.1 80 10.10.95.184 8080",
 "ACCEPT 192.168.*.* 25",
 "REJECT 192.168.5.38 *"}
{"192.168.0.43 80",
 "00192.00168.000.001 00080",
 "192.168.0.1 110",
 "192.168.1.73 80",
 "192.168.1.73 25",
 "206.26.210.5 53",
 "192.168.5.38 25"
 }
Returns:
{ "192.168.0.10:80",
  "10.10.95.184:8080",
  "REJECT",
  "REJECT",
  "ACCEPT",
  "REJECT",
  "REJECT" }
Packet 0 matches rule 0, and gets forwarded according to that rule. Packet 1 matches both rules 0 and 1, so rule 1 is applied. Packets 2, 3, and 5 don't match any rules, so they are rejected. Packet 4 matches rule 2, and is therefore accepted. Packet 6 matches rules 2 and 3, so it gets rejected (rule 3 is applied).
1)

????
{"FORWARD *.*.*.* * 192.168.0.1"}
{"213.148.161.82 9484",
 "172.230.108.145 16627",
 "122.141.122.130 46874",
 "241.145.145.77 26390",
 "139.97.106.125 35305",
 "244.131.151.77 26390"}
Returns:
{ "192.168.0.1:9484",
  "192.168.0.1:16627",
  "192.168.0.1:46874",
  "192.168.0.1:26390",
  "192.168.0.1:35305",
  "192.168.0.1:26390" }

2)

????
{"REJECT *.20-252.114-157.36-91 13171-54085",
 "ACCEPT *.*.73-180.* *",
 "FORWARD 55.63.173.239 * 168.154.33.25",
 "REJECT *.72-73.*.48-191 *",
 "REJECT 20.51.*.* 4579",
 "ACCEPT 70-166.*.*.86-182 *",
 "REJECT 88-190.*.119-157.* 3316-27844",
 "FORWARD *.52-221.134-250.66-207 * 116.94.120.82"}
{"203.11.104.45 44072",
 "154.92.128.87 30085",
 "20.51.68.55 4579",
 "177.73.138.69 14319",
 "112.65.145.82 26287",
 "55.63.173.239 45899"}
Returns:
{ "ACCEPT",
  "ACCEPT",
  "REJECT",
  "116.94.120.82:14319",
  "116.94.120.82:26287",
  "168.154.33.25:45899" }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2005-08-16 09:30 emu 阅读(1216) 评论(1)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# emu的解法 2005-08-16 10:03 emu
也是送分题。但是要在规定时间内麻利的分析处理全部字符串形成规则和判断就靠熟练了。
public class SimpleRouter {

public static void main(String[] args) {
SimpleRouter s = new SimpleRouter();
String[] rules = {"FORWARD 192.168.000.* 001-100 192.168.0.10",
"FORWARD 192.168.0.1 80 10.10.95.184 8080",
"ACCEPT 192.168.*.* 25", "REJECT 192.168.5.38 *"
};
String[] packets = {"192.168.0.43 80",
"00192.00168.000.001 00080",
"192.168.0.1 110",
"192.168.1.73 80",
"192.168.1.73 25",
"206.26.210.5 53",
"192.168.5.38 25"
};
String[] result = s.route(rules, packets);

for (int i = 0; i < result.length; i++)
System.out.println(result[i]);
System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"FORWARD *.*.*.* * 192.168.0.1"};
packets = new String[] {"213.148.161.82 9484",
"172.230.108.145 16627",
"122.141.122.130 46874",
"241.145.145.77 26390",
"139.97.106.125 35305",
"244.131.151.77 26390"
};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);
System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"REJECT *.20-252.114-157.36-91 13171-54085",
"ACCEPT *.*.73-180.* *",
"FORWARD 55.63.173.239 * 168.154.33.25",
"REJECT *.72-73.*.48-191 *",
"REJECT 20.51.*.* 4579",
"ACCEPT 70-166.*.*.86-182 *",
"REJECT 88-190.*.119-157.* 3316-27844",
"FORWARD *.52-221.134-250.66-207 * 116.94.120.82"};
packets = new String[] {"203.11.104.45 44072",
"154.92.128.87 30085",
"20.51.68.55 4579",
"177.73.138.69 14319",
"112.65.145.82 26287",
"55.63.173.239 45899"
};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);

System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"FORWARD *.*.*.* * 00.012.00000.099",
"FORWARD 192.168.0.1 110 00.00.00.00 000001"};
packets = new String[] {"192.168.0.43 80", "00192.00168.000.001 00080",
"192.168.0.1 110", "192.168.1.73 80", "192.168.1.73 25",
"206.26.210.5 53", "192.168.5.38 25"};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);

}


public String[] route(String[] rules, String[] packets) {
String[] result = new String[packets.length];
for (int i = 0; i < packets.length; i++) {
result[i] = getRoute(rules, packets[i]);
}
return result;
}


private String getRoute(String[] rules, String packet) {
for (int i = rules.length - 1; i > -1; i--) {
String m = match(rules[i], packet);
if (m != null) {
// System.out.println("match rule"+i+":"+rules[i]);
return m;
}
}
return "REJECT";
}

private String match(String rule, String packet) {
String[] ruleParts = rule.split(" ");
String[] packetParts = packet.split(" ");
String ip = packetParts[0];
String port = packetParts[1];
String[] ipParts = ip.split("\\.");
if ("ACCEPT".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
return (matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)) ? "ACCEPT" : null;
}
if ("REJECT".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
return (matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)) ? "REJECT" : null;
}
if ("FORWARD".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
if (!(matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)))
return null;

String[] forwardIp = ruleParts[3].split("\\.");

return Integer.parseInt(forwardIp[0], 10) + "." +
Integer.parseInt(forwardIp[1], 10) + "." +
Integer.parseInt(forwardIp[2], 10) + "." +
Integer.parseInt(forwardIp[3], 10) + ":" +
Integer.parseInt((ruleParts.length>4?ruleParts[4]:port),10);
}
return null;
}

private boolean matchPart(String range, String data) {
if ("*".equals(range))
return true;
if (range.indexOf('-') > -1) {
String[] r = range.split("-");
int lower = Integer.parseInt(r[0], 10);
int upper = Integer.parseInt(r[1], 10);
int i = Integer.parseInt(data, 10);
return (lower <= i && upper >= i);
}
if (Integer.parseInt(range) == Integer.parseInt(data))
return true;
return false;
}
}
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: