Problem
A rule looks like this:
A NE B
This means this means point A is located northeast of point B.
A SW C
means that point A is southwest of C.
Given a list of rules, check if the sum of the rules validate.
Examples
Example 1:
Input: rules = [
"A N B",
"B NE C",
"C N A"
]
Output: false
Explanation: does not validate, since `A` cannot be both north and south of `C`.
Example 2:
Input: rules = [
"A NW B",
"A N B"
]
Output: true
Solution
Method 1 - BFS
To solve this problem, we need to deduce and verify relative positions of points based on given directional rules. Here’s the approach you can use:
- Graph Representation of Directions:
- Treat this as a graph problem where each point is a vertex and each directional rule is a directed edge with specific constraints.
- Define Constraints:
- Use vectors to represent each directional constraint. For example:
N(North) can be represented as(0, 1).NE(Northeast) can be represented as(1, 1).- Similarly, define vectors for other directions
NW,S,SW,E,W,SE.
- Use vectors to represent each directional constraint. For example:
- Translation to Graph Problem:
- Initialize a dictionary for each point to store its relative position.
- Use vectors to establish constraints and check for consistency.
- Cycle Detection:
- Check for any contradictory cycles within the graph of constraints.
Code
Java
public class Solution {
// Method to check if the given rules are valid
public boolean isValid(String[] rules) {
Map<String, List<String[]>> graph = new HashMap<>();
Map<String, int[]> position = new HashMap<>();
// Build the graph
for (String rule : rules) {
String[] parts = rule.split(" ");
String a = parts[0];
String direction = parts[1];
String b = parts[2];
graph.putIfAbsent(a, new ArrayList<>());
graph.putIfAbsent(b, new ArrayList<>());
graph.get(a).add(new String[] {b, direction});
graph.get(b).add(new String[] {a, oppositeDirection(direction)});
}
// Use BFS to propagate positions
for (String node : graph.keySet()) {
if (!position.containsKey(node)) {
if (!bfs(node, graph, position)) {
return false;
}
}
}
return true;
}
// Method to convert direction to a vector
private int[] directionToVector(String direction) {
switch (direction) {
case "N":
return new int[] {0, 1};
case "S":
return new int[] {0, -1};
case "E":
return new int[] {1, 0};
case "W":
return new int[] {-1, 0};
case "NE":
return new int[] {1, 1};
case "NW":
return new int[] {-1, 1};
case "SE":
return new int[] {1, -1};
case "SW":
return new int[] {-1, -1};
default:
throw new IllegalArgumentException(
"Invalid direction: " + direction);
}
}
// BFS Helper Method
private boolean bfs(String start, Map<String, List<String[]>> graph,
Map<String, int[]> position) {
Queue<String> queue = new LinkedList<>();
queue.add(start);
position.put(start, new int[] {0, 0});
while (!queue.isEmpty()) {
String current = queue.poll();
int[] currentPos = position.get(current);
for (String[] neighbor : graph.get(current)) {
String neighborNode = neighbor[0];
int[] move = directionToVector(neighbor[1]);
int[] newPos = new int[] {
currentPos[0] + move[0], currentPos[1] + move[1]};
if (!position.containsKey(neighborNode)) {
position.put(neighborNode, newPos);
queue.add(neighborNode);
} else {
int[] existingPos = position.get(neighborNode);
if (existingPos[0] != newPos[0]
|| existingPos[1] != newPos[1]) {
return false;
}
}
}
}
return true;
}
// Method to get opposite direction
private String oppositeDirection(String direction) {
switch (direction) {
case "N":
return "S";
case "S":
return "N";
case "E":
return "W";
case "W":
return "E";
case "NE":
return "SW";
case "NW":
return "SE";
case "SE":
return "NW";
case "SW":
return "NE";
default:
throw new IllegalArgumentException(
"Invalid direction: " + direction);
}
}
public static void main(String[] args) {
String[] rules1 = {"A N B", "B NE C", "C N A"};
System.out.println(isValid(rules1)); // Output: false
String[] rules2 = {"A NW B", "A N B"};
System.out.println(isValid(rules2)); // Output: true
}
}
Python
def direction_to_vector(direction):
directions = {
"N": (0, 1),
"S": (0, -1),
"E": (1, 0),
"W": (-1, 0),
"NE": (1, 1),
"NW": (-1, 1),
"SE": (1, -1),
"SW": (-1, -1),
}
return directions[direction]
def is_valid(rules):
graph = defaultdict(list)
vectors = defaultdict(lambda: [0, 0])
# Create the graph and directional vectors
for rule in rules:
a, direction, b = rule.split()
vec = direction_to_vector(direction)
graph[a].append((b, vec))
graph[b].append((a, (-vec[0], -vec[1])))
# Initialize visited dictionary
visited = {}
def bfs(start):
queue = deque([(start, (0, 0))])
visited[start] = (0, 0)
while queue:
current, pos = queue.popleft()
for neighbor, move in graph[current]:
new_pos = (pos[0] + move[0], pos[1] + move[1])
if neighbor in visited:
if visited[neighbor] != new_pos:
return False
else:
visited[neighbor] = new_pos
queue.append((neighbor, new_pos))
return True
# Check each component of the graph
for node in graph:
if node not in visited:
if not bfs(node):
return False
return True
# Example usage:
rules1 = ["A N B", "B NE C", "C N A"]
print(is_valid(rules1)) # Output: False
rules2 = ["A NW B", "A N B"]
print(is_valid(rules2)) # Output: True
Complexity
- ⏰ Time complexity:
O(V + E)whereVis the number of vertices (points) andEis the number of edges (rules). - 🧺 Space complexity:
O(V + E), for storing the graph and position mappings.