emu in blogjava

:: 管理 ::

171 隨筆 :: 103 文章 :: 1052 評(píng)論 :: 2 Trackbacks

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" }

????
{"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 閱讀(1233) 評(píng)論(1) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

評(píng)論

# emu的解法 2005-08-16 10:03 emu

也是送分題。但是要在規(guī)定時(shí)間內(nèi)麻利的分析處理全部字符串形成規(guī)則和判斷就靠熟練了。
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;
}
}
回復(fù) 更多評(píng)論

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 沒忍住手癢做了一道題，結(jié)果還沒作對(duì)。差點(diǎn)被燕潘考倒了 1000分模擬題CraneWork 500分模擬題 MaximalPalindromeSubstrings 250分模擬題 SalesRouting SecretSum (code jam china round2 500分真題) FactorialSystem (code jam china round2 300分真題) RecurringNumbers (code jam china 1000分真題) google中國編程挑戰(zhàn)賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國編程挑戰(zhàn)賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊(cè)

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

評(píng)論