Castle on the Grid

Sort by

recency

|

36 Discussions

|

  • + 0 comments
    #First, build the neighborhood of nodes: for a given position, move in all directions and add possible nodes to the adjacency list
    # Then, do a BFS from start node, until we reach end node, count how many levels of BFS traversal needed 
    
    from collections import defaultdict, deque
    def check_go(i, j, d_i, d_j, grid, ngbs_ij):
        n = len(grid)
        cur_i = i + d_i
        cur_j = j + d_j
        while 0 <= cur_i < n and 0 <= cur_j < n and grid[cur_i][cur_j]=='.':
            ngbs_ij.append((cur_i, cur_j))
            cur_i += d_i
            cur_j += d_j
            
    def build_ngbs(grid):
        ngbs = defaultdict(list)
        n = len(grid)
        for i in range(n):
            for j in range(n):
                if grid[i][j] == '.':
                    #check ngbs
                    check_go(i, j, 0, -1, grid, ngbs[(i,j)])
                    check_go(i, j, 0, +1, grid, ngbs[(i,j)])
                    check_go(i, j, -1, 0, grid, ngbs[(i,j)])
                    check_go(i, j, +1, 0, grid, ngbs[(i,j)])
        return ngbs  
                    
    
    def minimumMoves(grid, startX, startY, goalX, goalY):
        ngbs = build_ngbs(grid)
        q = deque()
        visited = set()
        q.append((startX, startY))
        visited.add((startX, startY))
        level_counter = -1
        while q:
            level_size = len(q)
            level_counter+=1
            for _ in range(level_size):
                node = q.popleft()
                if node==(goalX, goalY):
                    return level_counter
                for neighbor in ngbs[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        q.append(neighbor)
    
  • + 1 comment

    This problm's got issues. Let's take the first test case:

    [s X .] [. X .] [g . .]

    to go from Start to Goal, there are two moves (0,0)->(0,1) and (0,1)->(0,2). But the expected answer is 3. How TF are they counting to get to 3? Can somebody please explain to me? Or, at least, share whatever the author was smoking?

  • + 0 comments

    If you're getting results that seem correct but don't match the expected results (e.g., 1 rather than 3 for sample test 0), it's probably because x and y are not fully specified in the problem description, and you have them reversed. The first row of input is the column x=0 rather than the row y=0. You can swap the X and Y argument names in the minimumMoves function to resolve it.

  • + 0 comments

    solution in C#:

        private static readonly List<(int dx, int dy)> directions = new()
        {
            (1, 0), (-1, 0), (0, 1), (0, -1)
        };
    
        public static int minimumMoves(List<string> grid, int startX, int startY, int goalX, int goalY)
        {
            var len = grid.Count;
            var queue = new Queue<(int cx, int cy, int moves)>();
            var visited = new bool[len, len];
            
            queue.Enqueue((startX, startY, 0));
            visited[startX, startY] = true;
            
            while(queue.Count > 0)
            {
                var (cx, cy, moves) = queue.Dequeue();
                
                if(cx == goalX && cy == goalY)
                {
                    return moves;
                }
                
                foreach(var (dx, dy) in directions)
                {
                    var (nx, ny) = (cx + dx, cy + dy);
                    while (nx >= 0 && nx < len && 
                        ny >= 0 && ny < len && 
                        grid[nx][ny] == '.')
                    {
                        if (!visited[nx, ny])
                        {
                            visited[nx, ny] = true;
                            queue.Enqueue((nx, ny, moves + 1));
                        }
    
                        nx += dx;
                        ny += dy;
                    }
                }
            }
            
            return -1;
        }
    
  • + 0 comments

    i solved by building a graph of points on the grid and calculating distance using dijkstra's algo

    from collections import defaultdict
    import heapq
    
    
    def dijkstra(graph, start):
        distances = {node: float("inf") for node in graph}
        distances[start] = 0
        previous_nodes = {node: None for node in graph}
        priority_queue = [(0, start)]
        
        while priority_queue:
            current_distance, current_node = heapq.heappop(priority_queue)
            if current_distance > distances[current_node]:
                continue
            for neighbor, weight in graph[current_node].items():
                distance = current_distance + weight
                
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous_nodes[neighbor] = current_node
                    heapq.heappush(priority_queue, (distance, neighbor))
        return distances, previous_nodes
     
    
    def minimumMoves(grid, startX, startY, goalX, goalY):
        # Write your code here
        nodes = defaultdict(dict)
        length = len(grid[0])
        # create graph of nodes and edges
        for y, row in enumerate(grid):
            for x, column in enumerate(row):
                if grid[y][x] == "X":
                    continue
                # move up and add edges
                i, j = x-1, y
                # go left
                while i >= 0 and grid[j][i] != "X":
                    nodes[(x, y)][(i, j)] = 1
                    i -= 1
                # go right
                i, j = x+1, y
                while i < length and grid[j][i] != "X":
                    nodes[(x, y)][(i, j)] = 1
                    i += 1
                i, j = x, y-1
                # go down
                while j >= 0 and grid[j][i] != "X":
                    nodes[(x, y)][(i, j)] = 1
                    j -= 1
                # go up
                i, j = x, y+1
                while j < length and grid[j][i] != "X":
                    nodes[(x, y)][(i, j)] = 1
                    j += 1
        maps = dijkstra(nodes, (startY, startX))
        return maps[0][(goalY, goalX)]