Problem

A rule looks like this:

1

A NE B

This means this means point A is located northeast of point B.

1

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:

1
2
3
4
5
6
7

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:

1
2
3
4
5

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:

  1. 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.
  2. 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.
  3. Translation to Graph Problem:
    • Initialize a dictionary for each point to store its relative position.
    • Use vectors to establish constraints and check for consistency.
  4. Cycle Detection:
    • Check for any contradictory cycles within the graph of constraints.

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

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) where V is the number of vertices (points) and E is the number of edges (rules).
  • 🧺 Space complexity: O(V + E),  for storing the graph and position mappings.