*Train Tracks Puzzle Solver clear solution for Train Tracks by JimmyCarlos - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
*Train Tracks Puzzle Solver solution in Clear category for Train Tracks by JimmyCarlos
# import time, tkinter as tk  # If you enable this line, you can see the algorithm solving the puzzle in real-time! 

class Board:
    def __init__(self,row_counts,column_counts,start,end,constraints):
        self.row_counts,self.column_counts = row_counts,column_counts  # Given by question. Lists.
        if "tk" in globals(): start,end,constraints = tuple(start),tuple(end),eval(constraints) # Convert input for compatability.

        # Adjust the input. We want start and end pieces to have edges coming off the board.
        self.H,self.W = len(row_counts),len(column_counts)
        for x in (start,end):
            if   x[0] == 0:        constraints[x].add("N")
            elif x[0] == self.H-1: constraints[x].add("S")
            elif x[1] == 0:        constraints[x].add("W")
            elif x[1] == self.W-1: constraints[x].add("E")

        # Create the grid of tiles.
        self.board = [[Tile(R,C) for C in range(self.W)] for R in range(self.H)]

        # Make references to the start and end tiles
        self.start = self.board[start[0]][start[1]]
        self.end = self.board[end[0]][end[1]]
        
        # Link the tiles together
        for R in range(self.H):
            for C in range(0,self.W-1):
                u,v = self.board[R][C],self.board[R][C+1]
                u.adj_tiles["E"],v.adj_tiles["W"] = v,u
        for C in range(self.W):
            for R in range(0,self.H-1):
                u,v = self.board[R][C],self.board[R+1][C]
                u.adj_tiles["S"],v.adj_tiles["N"] = v,u

        # Set all bridges coming off the board as False. If coming off the board, then it links to None.
        for R in range(self.H):
            for C in range(self.W):
                if self.board[R][C] in (self.start,self.end): continue
                for direction in "NESW":
                    if self.board[R][C].adj_tiles[direction] == None:
                        self.board[R][C].locked_positions[direction] = False

        # Use the constraints already given to add in the starting clues.
        for (R,C),directions in constraints.items():
            for direction in directions:
                self.board[R][C].lock_bridge_status(direction,True)
            self.board[R][C].update_possible_positions()

        # Create the tkinter representation of the board.
        if "tk" in globals():
            self.root = tk.Tk()
            self.root.geometry("+0+0")
            screen_height_pixels = self.root.winfo_screenheight()
            screen_height_points =  0.75 * screen_height_pixels # eg. Font Point Size. 
            font_size = int((screen_height_points - 200)//self.H)
            self.label = tk.Label(self.root,text="",font=("Consolas",font_size),justify="left")
            self.label.pack()
            self.update_board_repr()
            self.label.update()

    def __repr__(self): return "Board"

    def update_board_repr(self):
        """Update the tkinter representation of the board to reflect changes made."""
        if "tk" not in globals(): return
        self.label.config(text="\n".join("".join(x.represent_self_as_ascii() for x in row) for row in self.board))
        self.label.update()
        time.sleep(0.5) # Time Delay

    def check_for_single_position_tiles(self):
        """Check all tiles to see if they have only one way of being placed."""
        for R in range(self.H):
            for C in range(self.W):
                tile = self.board[R][C]
                tile.update_possible_positions()
                if len(tile.possible_positions) == 0: raise Exception("Can't place tile at ({},{})".format(R,C))
                if len(tile.possible_positions) == 1:
                    empty_position = {"N":False, "E":False, "S":False, "W":False}
                    if tile.possible_positions[0] == empty_position:
                        tile.make_unlit()
                    else:
                        for direction,status in tile.possible_positions[0].items():
                            tile.lock_bridge_status(direction,status)
                
        
    def check_for_completed_rows_and_columns(self):
        """Check each row and column. If they must all be lit or unlit, then apply it."""
        # Check rows
        for R in range(self.H):
            target = self.row_counts[R]
            lit_cells = [C for C in range(self.W) if self.board[R][C].is_lit == True]
            unknown_cells = [C for C in range(self.W) if self.board[R][C].is_lit == "?"]
            unlit_cells = [C for C in range(self.W) if self.board[R][C].is_lit == False]
            if len(lit_cells) + len(unknown_cells) == target: # Need everything else lit.
                for C in unknown_cells: self.board[R][C].make_lit()
            if len(lit_cells) == target: # Need everything else not lit.
                for C in unknown_cells: self.board[R][C].make_unlit()

            # Exactly one more cell needs to be lit. Tiles that need another one in this line can't be lit.
            if len(lit_cells) + 1 == target:
                for C in unknown_cells:
                    cell = self.board[R][C]
                    # Can pass perpendicularly through
                    if cell.locked_positions["N"] != False and cell.locked_positions["S"] != False: continue
                    # Can attach itself to a lit cell.
                    if cell.locked_positions["E"] != False and cell.adj_tiles["E"] is not None and cell.adj_tiles["E"].is_lit == True: continue
                    if cell.locked_positions["W"] != False and cell.adj_tiles["W"] is not None and cell.adj_tiles["W"].is_lit == True: continue
                    # This tile needs another tile in this line - but we only have one space, ∴ this tile isn't be lit.
                    cell.make_unlit()

            # Exactly all but one more cell needs to be lit. If making a cell unlit makes another cell a dead-end, that cell can't be unlit.
            if len(lit_cells) + len(unknown_cells) - 1 == target:
                for C in unknown_cells:
                    cell = self.board[R][C]
                    # If either perpendicular cell is unknown, and has only 2 openings left, with the current tile being one of them,
                    # then this cell must be lit, or it would make the adj cell a dead-endm, meaning there are 2 not-lit tiles in this line - but we know there's only one!
                    for direction in "WE":
                        adj_cell = cell.adj_tiles[direction]
                        if adj_cell is None: continue # Off the board
                        if adj_cell.is_lit != "?": continue # Adj cell is lit/unlit already.
                        if cell.locked_positions[direction] == False: continue # No path to this adj cell.
                        if len([d for d in "NESW" if adj_cell.locked_positions[d] == "?"]) != 2: continue # More than one way to place this new cell.
                        cell.make_lit()
                        
        # Check columns
        for C in range(self.W):
            target = self.column_counts[C]
            lit_cells = [R for R in range(self.H) if self.board[R][C].is_lit == True]
            unknown_cells = [R for R in range(self.H) if self.board[R][C].is_lit == "?"]
            unlit_cells = [R for R in range(self.H) if self.board[R][C].is_lit == False]
            if len(lit_cells) + len(unknown_cells) == target: # Need everything else lit.
                for R in unknown_cells: self.board[R][C].make_lit()
            if len(lit_cells) == target: # Need everything else not lit.
                for R in unknown_cells: self.board[R][C].make_unlit()

            # Exactly one more cell needs to be lit. Tiles that need another one in this line can't be lit.
            if len(lit_cells) + 1 == target: 
                for R in unknown_cells:
                    cell = self.board[R][C]
                    # Can pass perpendicularly through
                    if cell.locked_positions["W"] != False and cell.locked_positions["E"] != False: continue
                    # Can attach itself to a lit cell.
                    if cell.locked_positions["N"] != False and cell.adj_tiles["N"] is not None and cell.adj_tiles["N"].is_lit == True: continue
                    if cell.locked_positions["S"] != False and cell.adj_tiles["S"] is not None and cell.adj_tiles["S"].is_lit == True: continue
                    # This tile needs another tile in this line - but we only have one space, ∴ this tile isn't be lit.
                    cell.make_unlit()
                
            # Exactly all but one more cell needs to be lit. If making a cell unlit makes another cell a dead-end, that cell can't be unlit.
            if len(lit_cells) + len(unknown_cells) - 1 == target:
                for R in unknown_cells:
                    cell = self.board[R][C]
                    # If either perpendicular cell is unknown, and has only 2 openings left, with the current tile being one of them,
                    # then this cell must be lit, or it would make the adj cell a dead-endm, meaning there are 2 not-lit tiles in this line - but we know there's only one!
                    for direction in "NS":
                        adj_cell = cell.adj_tiles[direction]
                        if adj_cell is None: continue # Off the board
                        if adj_cell.is_lit != "?": continue # Adj cell is lit/unlit already.
                        if cell.locked_positions[direction] == False: continue # No path to this adj cell.
                        if len([d for d in "NESW" if adj_cell.locked_positions[d] == "?"]) != 2: continue # More than one way to place this new cell.
                        cell.make_lit()

    def check_for_ends_that_will_make_loops(self):
        """Look for any pairs of tiles where if a bridge was made between them, then it woulc create a loop."""
        # Find ends of tracks, eg. where exactly one direction has been locked in.
        is_end=lambda x:len([d for d in "NESW" if x.locked_positions[d] == True]) == 1 and x not in (self.start,self.end) 
        end_tiles = {self.board[R][C] for R in range(self.H) for C in range(self.W) if is_end(self.board[R][C])}
        
        # Choose an end of a path, and follow it to the other end.
        # If these ends are adjacent, they cannot be connected, as doing so would create a loop.
        find_adj_tiles=lambda x:[x.adj_tiles[d] for d in "NESW" if x.locked_positions[d] == True and x.adj_tiles[d] is not None]
        while end_tiles:
            # Take a monorail ride to the end of the path.
            path_start = end_tiles.pop()
            last,cur = path_start,find_adj_tiles(path_start)[0]
            while True:
                cur_adj_tiles = find_adj_tiles(cur)
                cur_adj_tiles.remove(last)
                if len(cur_adj_tiles) == 0: break
                last,cur = cur,cur_adj_tiles[0]
                if cur in (self.start,self.end): break

            # Ok, so we've found the end of this path. If this is the start/end of the whole grid then ignore it.
            if cur in (self.start,self.end): continue
            end_tiles.remove(cur)

            # See if the end of this path is adjacent to the start of the path.
            for direction in "NESW":
                if path_start.adj_tiles[direction] == cur:
                    path_start.lock_bridge_status(direction,False)

    def check_for_chokepoints(self):
        """Check the grid for any intersection that must be active or it would mean the start cannot reach the end."""
        # Create an adjDict to link all of the tiles in the board together.
        adjDict = {}
        for R in range(self.H):
            for C in range(self.W):
                tile = self.board[R][C]
                adjDict[tile] = set()
                for direction in "NESW":
                    if tile.adj_tiles[direction] is None: continue # Goes off the board
                    if tile.locked_positions[direction] == False: continue # No path between these tiles
                    adjDict[tile].add(tile.adj_tiles[direction])

        # Find any valid path from the start to the end. Any essential chokepoints will be on any valid path, so we only need to check tiles on this path.
        golden_path = self.BFS_Path(self.start,self.end,adjDict)

        # This strategy creates a boolean list for each tile in the golden path as to whether it must be in the final correct path or might not.
        is_chokepoint = [True for x in golden_path]

        # This stores whether we have found a viable route to each tile in the golden path.
        is_reachable_with_starts_so_far = [False for x in golden_path]
         
        # Now iterate through each tile in the golden path, trying to reach as many tiles as we can, without walking on the golden path.  
        nodesChecked,nodesToCheck,nodesDiscovered = set(),set(),set()
        for i,golden_path_node in enumerate(golden_path):
            # If it is possible to reach any tile on the golden path past this current tile, then this tile is not essential.
            if any(is_reachable_with_starts_so_far[i+1:]): is_chokepoint[i] = False

            # Regardless of it is a chokepoint, use BFS to find all the nodes that can be reached from this tile.
            nodesToCheck.add(golden_path_node)
            while nodesToCheck:
                for node in nodesToCheck:
                    for newNode in adjDict[node]:
                        if newNode in golden_path:
                            is_reachable_with_starts_so_far[golden_path.index(newNode)] = True
                            continue
                        if all(newNode not in S for S in (nodesChecked,nodesToCheck,nodesDiscovered)):
                            nodesDiscovered.add(newNode)
                nodesChecked,nodesToCheck,nodesDiscovered = nodesChecked|nodesToCheck,nodesDiscovered,set()

        # All tiles that are chokepoints must be lit, or there can't be a path at all.
        for is_chokepoint_tile,golden_path_tile in zip(is_chokepoint,golden_path):
            if is_chokepoint_tile: golden_path_tile.make_lit()
        
        # Now look at each intersection between the tiles of the golden path.
        # If they are both chokepoints, then they must be both be part of the final track.
        # But it is not certain they are directly connected!
        # To check, remove the path between them and see if it is now impossible to go from the start to the end.
        for i in range(len(golden_path)-1):
            # If these two tiles are already connected then we don't care about them.
            u,v = golden_path[i],golden_path[i+1]
            direction, = [d for d in "NESW" if u.adj_tiles[d] == v]
            if u.locked_positions[direction] == True: continue

            # If removing this edge makes the board unsolvable then this intersection must be active.
            if not self.BFS_Reachable(self.start, self.end, adjDict, disallowed_edge=(u,v)):
                u.lock_bridge_status(direction,True)
        
    def BFS_Path(self,start,end,adjDict) -> list:
        """Use BFS to find the shortest path from a start to an end. Return an empty list if it can not be done."""
        stepsToReachDict,stepsAway = {start:0},0
        nodesChecked,nodesToCheck,nodesDiscovered = set(),{start},set()
        while nodesToCheck:
            stepsAway += 1
            for node in nodesToCheck:
                for newNode in adjDict[node]:
                    if all(newNode not in S for S in (nodesChecked,nodesToCheck,nodesDiscovered)):
                        nodesDiscovered.add(newNode)
                        stepsToReachDict[newNode] = stepsAway
                    if newNode == end:
                        finalPath,curNode = [newNode],newNode
                        while stepsAway > 0:
                            curNode = [x for x,v in stepsToReachDict.items() if v == stepsAway-1 and curNode in adjDict[x]][0]
                            finalPath.append(curNode); stepsAway -= 1
                        return finalPath[::-1]
            nodesChecked,nodesToCheck,nodesDiscovered = nodesChecked|nodesToCheck,nodesDiscovered,set()
        return []

    def BFS_Reachable(self,start,end,adjDict,disallowed_edge=None) -> bool:
        """Use BFS to find if we can go from the start to the end, not using the edge disallowed."""
        nodesChecked,nodesToCheck,nodesDiscovered = set(),{start},set()
        while nodesToCheck:
            for node in nodesToCheck:
                for newNode in adjDict[node]:
                    if (node,newNode) == disallowed_edge or (newNode,node) == disallowed_edge: continue
                    if newNode == end: return True
                    if all(newNode not in S for S in (nodesChecked,nodesToCheck,nodesDiscovered)):
                        nodesDiscovered.add(newNode)
            nodesChecked,nodesToCheck,nodesDiscovered = nodesChecked|nodesToCheck,nodesDiscovered,set()
        return False

    @property
    def is_complete(self) -> bool:
        """Return if the board is completely solved."""
        tile_complete=lambda x:all(v != "?" for v in x.locked_positions.values())
        return all(tile_complete(self.board[R][C]) for R in range(self.H) for C in range(self.W))

    
class Tile:
    def __init__(self,R,C):
        self.R,self.C = R,C # Reference to the Tile's position in the grid.
        self.locked_positions = {"N":"?", "E":"?", "S":"?", "W":"?"} # True = Path, ? = Unknown, False = No Path
        self.adj_tiles = {"N":None, "E":None, "S":None, "W":None} # References to all tiles adjacent on its ordinals.
        self.is_lit = "?" # True = Lit, ? = Unknown, False = Not Lit
        self.possible_positions = [{"N":True,  "E":True,  "S":False, "W":False}, 
                                   {"N":True,  "E":False, "S":True,  "W":False},
                                   {"N":True,  "E":False, "S":False, "W":True},
                                   {"N":False, "E":True,  "S":True,  "W":False},
                                   {"N":False, "E":True,  "S":False, "W":True},
                                   {"N":False, "E":False, "S":True,  "W":True},
                                   {"N":False, "E":False, "S":False, "W":False}] # List of all possible positions that could fit in this tile
        
    def __repr__(self): return "({},{})".format(self.R,self.C)

    def represent_self_as_ascii(self) -> str:
        """Return what this tile looks like in a single ascii character."""
        if self.is_lit == False: return " " 
        if self.is_lit == "?": return "▒"
        if self.is_lit == True:
            if len([x for x in self.locked_positions.values() if x == True]) != 2: return "█"
            unicode_boxDict = {"NS":"║", "EW":"═", "EN":"╚", "ES":"╔", "SW":"╗", "NW":"╝"}
            return unicode_boxDict["".join(x for x in "ENSW" if self.locked_positions[x] == True)]

    def make_lit(self):
        """Call when we know this tile must be lit. Remove the empty position."""
        self.is_lit = True
        empty_position = {"N":False, "E":False, "S":False, "W":False}
        if empty_position in self.possible_positions: self.possible_positions.remove(empty_position)

    def make_unlit(self):
        """Call when we know this tile must be unlit. Lock in the empty position."""
        self.is_lit = False
        for direction in "NESW": self.lock_bridge_status(direction,False)
        self.update_possible_positions()

    def lock_bridge_status(self,direction,status):
        """If we know if a bridge between two tiles is definitely on or definitely off, lock it in place."""
        assert direction in ("N","E","S","W")
        assert status in (True,False)
        if self.locked_positions[direction] != "?": return # This tile has already been locked.
        if status == True: self.make_lit()
        self.locked_positions[direction] = status
        adj_tile = self.adj_tiles[direction]
        if adj_tile is None: return # Points off the board.
        opposite_direction = {"N":"S", "E":"W", "S":"N", "W":"E"}[direction]
        adj_tile.locked_positions[opposite_direction] = status
        if status == True: adj_tile.make_lit()
        
    def update_possible_positions(self):
        """Check to see if all possible positions are still plausible."""
        is_viable_position=lambda x:all(self.locked_positions[direction] in ("?",status) for direction,status in x.items())
        self.possible_positions = [pp for pp in self.possible_positions if is_viable_position(pp)]


def train_tracks(row_counts,column_counts,start,end,constraints) -> str:
    # Create the board object
    board = Board(row_counts,column_counts,start,end,constraints)
    
    # Main Loop. Each loop applies all three solving strategies to the board.
    while not board.is_complete:
        board.check_for_completed_rows_and_columns()
        board.update_board_repr()
        
        board.check_for_single_position_tiles()
        board.update_board_repr()
        
        board.check_for_ends_that_will_make_loops()
        board.update_board_repr()

        board.check_for_chokepoints()
        board.update_board_repr()

    # Find the path to go from the start to the end.
    path_to_travel = ""
    last,cur = None,board.start
    while cur != board.end:
        for d in "NESW":
            if cur.locked_positions[d] == True and cur.adj_tiles[d] is not last:
                path_to_travel += d
                last,cur = cur,cur.adj_tiles[d]
                break

    return path_to_travel
May 13, 2020
Maya
0 %
You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.