Day 4: It's Lovely Weather for a Sleigh Ride Together

Computer Science Level 5

Sam and Linda are taking a sleigh ride in a snowy forest. After taking a frolic in the fresh winter snow, they decide that they should head back. Unfortunately for Sam and Linda, the sun is starting to go down, and it is getting colder each minute.

Can you construct an algorithm that determines the minimum amount of time it will take Sam and Linda to get home?

Details and Assumptions:

For the purpose of this question, we can take the forest to be a $70 \ \times \ 70$ grid, with trees positioned at a collection of fixed coordinates (as stated below). Trees occupy the entire grid square in which they are positioned. Sam and Linda can travel one grid square directly North, South, West, or East of their current grid square (not diagonal) per minute. They cannot pass through trees, they are forced to go around them. Assume that Sam and Linda start off at the coordinate $(65, \ 4)$ and that they are trying to get to coordinate $(7, \ 62)$ . Also assume that the $x$ - and $y$ -coordinates both range from $1$ to $70$ .

This is the list of coordinates where trees are located.

This problem is part of The 12 Days of Math-Mas 2018

The answer is 144.

4 solutions

Darryl Dennis
Dec 12, 2018

My Python code is intended to provide a list of values indicating the minimum number of steps ( length of time) required to arrive at each cell in the entire forest. I stopped the code after the home destination was reached. For my own amusement and interest I am expanding the problem to print out a detailed set of directions to follow for one of the possible routes home. My intention is to have the code determine and print out a serial set of steps to make the trip. My output should look something like start,N,N,W,W,W,W,W,S,S ... S,S,home. I hope to develop the code to provided detailed directions for any trip that is possible from one location to another within a grid like the one provided.

By my calculations there are 997,920 possible unique (distinct in some way from any of the other) routes, each of which would take 144 minute, that Sam and Linda could have taken home. I did up a excel sheet showing the cells along the routes that Sam and Linda would have to travel to make the trip in 144 minutes. As It turned out on the Excel sheet the Y values from the table (north/South) are inverted ie larger values are lower.

ew, ns = 72, 72;
forest = [[0 for x in range(ew)] for y in range (ns)]; # array to hold tree locations from file
trees= "[list of tree coordinates]"
step = 0

def found_home(int):
     print(step," Minutes is the shortest time requiered to get home.")
     import csv
     csvfile = "file location for txt file"
     with open(csvfile, "w") as output: # write forest list to file for use with Excel chart this is not actualy required for solution
     writer = csv.writer(output, lineterminator='\n')
     writer.writerows(forest)

    quit()  
    return; 

for x in range(ns):    # fill outside edge with trees
     for y in range(ew):
         if x == 0 or x == 71 or y == 0 or y == 71:
              forest[x][y]= -1
    for i in range(len(trees)):
    forest[trees[i][0]][trees[i][1]] = -1

forest[65][4] = 1 # starting point
forest[7][62] = 1000 #ending point

while True: 
    step += 1

    for x in range(1,71):          
        for y in range(1,71):
           if forest[x][y] == step:

              if forest[x-1][y] == 0:
                  forest[x-1][y]= step+1

             if forest[x-1][y] == 1000:
                  found_home(step)
             if forest[x+1][y] == 0:
                  forest[x+1][y]= step+1

              if forest[x+1][y] == 1000:
                 found_home(step)
              if forest[x][y-1] == 0:
              forest[x][y-1]= step+1

              if forest[x][y-1] == 1000:
                 found_home(step)    
             if forest[x][y+1] == 0:
                  forest[x][y+1]= step+1

            if forest[x][y+1] == 1000:
                found_home(step)

Jack Ceroni
Dec 8, 2018

Essentially, the program that I made uses a cellular automata that "spreads" across a $70 \ \times \ 70$ grid until it reaches the target coordinate, with each iteration of spread adding $1$ minute to the timer. This is the code that I wrote to solve the problem (in Python):

grid_block = "[List of Tree Coordinates]"
timer = 0
store = [[65, 4]]
while ([7, 62] not in store):
    y = store
    store = []
    for a in y:
        movement = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        for i in movement:
            if ([a[0]+i[0], a[1]+i[1]] not in grid_block):
                if (a[0]+i[0] > 0 and a[0]+i[0] <= 70):
                    if (a[1]+i[1] > 0 and a[1]+i[1] <= 70):
                        if ([a[0]+i[0], a[1]+i[1]] not in store):
                            store.append([a[0]+i[0], a[1]+i[1]])
    print(store)
    timer = timer + 1
print(timer)

with open('trees.txt') as f:
    tree_coords = eval(f.read())


def calculate_min_time(tree_coords: list, start: tuple, end: tuple) -> int:
    grid = [[1 for _ in range(70)] for _ in range(70)]
    for coord in tree_coords:
        grid[coord[1] - 1][coord[0] - 1] = 0
    if start == end:
        return 0
    done = False
    visited = [start]
    routes = [start]
    mins = 0
    while not done:
        mins += 1
        new_routes = []
        choices = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        for route in routes:
            for choice in choices:
                try:
                    new_y, new_x = route[0] + choice[0], route[1] + choice[1]
                    if (new_y, new_x) == end:
                        return mins
                    if grid[new_y][new_x] and (new_y, new_x) not in visited:
                        new_routes.append((new_y, new_x))
                        visited.append((new_y, new_x))
                except IndexError:
                    pass
        routes = new_routes.copy()


print(calculate_min_time(tree_coords, (3, 64), (61, 6)))

Eli Lopez - 2 years, 6 months ago

@Eli Lopez You can post your own solution to the problem, with this code

Jack Ceroni - 2 years, 6 months ago

David Hammond
May 7, 2019

import bisect

# x, y coordinates of the trees
# @source https://pastebin.com/raw/DaQ1enpG
tree_coordinates = [[54, 5], [1, 58], [27, 54], [58, 7], [37, 43], [12, 65], [70, 43], [56, 44], [44, 10], [20, 49], [3, 65], [16, 69], [2, 70], [36, 22], [34, 17], [46, 36], [46, 65], [28, 10], [48, 52], [31, 57], [6, 64], [50, 17], [45, 3], [12, 43], [7, 31], [13, 28], [6, 70], [58, 19], [30, 30], [36, 60], [33, 39], [29, 59], [22, 4], [44, 25], [22, 15], [21, 55], [50, 68], [2, 20], [31, 56], [29, 6], [2, 4], [27, 7], [5, 13], [13, 16], [35, 18], [59, 34], [22, 45], [50, 14], [42, 17], [70, 33], [25, 69], [28, 25], [60, 48], [21, 69], [70, 35], [66, 38], [7, 27], [17, 36], [17, 56], [40, 68], [36, 47], [57, 24], [4, 32], [69, 5], [13, 37], [42, 68], [51, 42], [65, 13], [32, 12], [8, 69], [52, 38], [28, 54], [41, 50], [46, 60], [31, 65], [20, 34], [30, 11], [52, 41], [68, 14], [24, 24], [7, 7], [55, 23], [5, 56], [7, 16], [58, 57], [1, 11], [49, 3], [22, 52], [40, 27], [15, 27], [41, 13], [38, 41], [55, 53], [11, 32], [60, 60], [25, 58], [42, 51], [54, 52], [57, 10], [24, 4], [14, 9], [67, 63], [14, 13], [9, 42], [23, 14], [48, 18], [40, 59], [20, 57], [51, 66], [27, 58], [69, 29], [63, 28], [45, 40], [21, 13], [46, 46], [27, 67], [54, 20], [59, 29], [47, 9], [23, 32], [21, 7], [1, 61], [42, 46], [49, 31], [16, 68], [15, 37], [23, 5], [67, 29], [58, 34], [55, 56], [32, 14], [27, 56], [17, 21], [44, 42], [20, 13], [38, 70], [62, 22], [17, 63], [1, 44], [35, 23], [27, 6], [63, 61], [42, 50], [15, 33], [11, 22], [59, 48], [26, 47], [30, 19], [48, 20], [47, 34], [61, 27], [31, 17], [35, 15], [65, 17], [56, 15], [51, 5], [14, 38], [26, 49], [34, 20], [64, 62], [7, 55], [49, 56], [6, 21], [30, 67], [26, 25], [16, 29], [11, 52], [56, 65], [7, 11], [61, 35], [39, 53], [23, 44], [52, 59], [36, 5], [54, 65], [49, 43], [24, 67], [38, 58], [48, 38], [54, 46], [57, 57], [62, 24], [43, 13], [47, 56], [25, 49], [61, 49], [42, 61], [63, 12], [46, 47], [34, 54], [54, 42], [11, 28], [48, 39], [31, 35], [62, 10], [68, 51], [69, 49], [39, 11], [10, 7], [21, 54], [11, 34], [15, 8], [38, 6], [28, 60], [56, 37], [61, 19], [1, 7], [44, 17], [16, 25], [34, 46], [42, 26], [47, 61], [43, 45], [43, 22], [17, 14], [53, 62], [44, 47], [11, 17], [68, 46], [30, 24], [9, 68], [65, 60], [56, 49], [16, 54], [28, 20], [46, 48], [46, 20], [39, 55], [21, 58], [28, 55], [26, 15], [46, 6], [50, 54], [38, 19], [55, 2], [8, 52], [2, 35], [69, 12], [64, 57], [57, 3], [27, 40], [15, 7], [35, 9], [65, 61], [66, 59], [43, 25], [48, 59], [52, 32], [31, 34], [53, 68], [36, 14], [60, 17], [49, 51], [53, 6], [48, 27], [43, 18], [39, 51], [32, 55], [41, 41], [41, 28], [59, 31], [28, 39], [27, 41], [69, 43], [65, 67], [27, 57], [32, 9], [49, 55], [56, 33], [2, 9], [43, 20], [45, 5], [69, 35], [22, 53], [23, 49], [31, 27], [23, 60], [22, 22], [23, 26], [59, 57], [30, 33], [68, 27], [31, 59], [45, 44], [29, 19], [3, 28], [7, 58], [39, 13], [6, 37], [8, 39], [21, 39], [45, 30], [2, 60], [14, 39], [67, 15], [36, 17], [38, 64], [26, 21], [47, 68], [70, 49], [51, 47], [36, 38], [22, 63], [2, 28], [16, 2], [57, 14], [69, 16], [20, 60], [52, 9], [26, 59], [7, 36], [11, 53], [36, 55], [43, 56], [6, 27], [27, 64], [64, 18], [17, 50], [17, 64], [34, 26], [14, 48], [27, 20], [54, 45], [65, 51], [12, 46], [42, 4], [55, 3], [26, 26], [33, 5], [20, 38], [11, 43], [2, 66], [25, 68], [30, 7], [23, 31], [22, 33], [22, 18], [45, 1], [66, 11], [43, 11], [63, 64], [46, 32], [59, 55], [6, 55], [53, 59], [42, 37], [53, 41], [52, 1], [11, 45], [38, 54], [6, 16], [48, 10], [60, 32], [29, 69], [45, 48], [56, 60], [37, 40], [69, 50], [16, 47], [39, 48], [23, 29], [4, 34], [30, 51], [70, 44], [50, 20], [53, 14], [66, 18], [19, 43], [3, 35], [5, 16], [21, 32], [64, 16], [44, 16], [21, 9], [8, 14], [9, 20], [6, 29], [64, 17], [27, 5], [48, 35], [42, 5], [28, 6], [22, 19], [3, 46], [39, 1], [6, 14], [27, 39], [3, 29], [69, 8], [25, 20], [38, 17], [4, 52], [25, 46], [23, 58], [45, 14], [17, 25], [21, 20], [23, 41], [10, 63], [56, 36], [12, 3], [15, 42], [52, 50], [64, 54], [5, 63], [2, 6], [50, 25], [33, 51], [20, 28], [27, 16], [70, 23], [13, 21], [23, 9], [18, 57], [25, 32], [47, 32], [26, 61], [10, 46], [62, 21], [62, 17], [11, 6], [17, 26], [23, 43], [60, 66], [53, 23], [69, 46], [55, 42], [24, 15], [16, 48], [31, 18], [33, 66], [20, 58], [66, 16], [2, 42], [51, 52], [10, 38], [27, 32], [39, 5], [34, 58], [29, 22], [33, 32], [29, 65], [63, 25], [33, 40], [23, 67], [7, 30], [48, 66], [16, 21], [44, 67], [16, 49], [4, 54], [3, 55], [8, 62], [47, 50], [59, 9], [52, 19], [3, 70], [61, 25], [68, 64], [40, 33], [56, 8], [31, 28], [23, 3], [55, 16], [42, 3], [54, 68], [10, 40], [17, 70], [49, 22], [67, 57], [69, 34], [65, 5], [46, 17], [23, 52], [31, 58], [44, 51], [59, 47], [22, 28], [30, 15], [51, 44], [29, 53], [70, 34], [41, 69], [69, 22], [24, 28], [70, 64], [19, 11], [66, 6], [64, 6], [41, 2], [51, 60], [41, 65], [14, 2], [35, 50], [24, 26], [62, 49], [46, 13], [24, 27], [27, 14], [63, 58], [47, 29], [41, 1], [26, 28], [52, 40], [28, 56], [1, 68], [39, 18], [35, 66], [47, 44], [38, 39], [18, 1], [39, 28], [42, 42], [46, 50], [24, 29], [60, 20], [1, 46], [19, 50], [54, 10], [2, 37], [56, 7], [65, 30], [67, 26], [13, 24], [18, 9], [3, 45], [45, 37], [43, 48], [51, 24], [36, 45], [23, 56], [49, 33], [42, 47], [39, 31], [70, 57], [30, 66], [22, 8], [58, 49], [30, 57], [31, 29], [15, 34], [27, 61], [49, 15], [61, 61], [65, 45], [44, 5], [6, 54], [31, 51], [42, 11], [69, 2], [21, 63], [48, 7], [47, 64], [67, 47], [43, 59], [3, 9], [13, 27], [60, 59], [52, 56], [47, 7], [62, 36], [1, 21], [25, 47], [11, 54], [54, 53], [28, 30], [16, 59], [45, 67], [21, 50], [37, 13], [21, 41], [66, 13], [51, 38], [46, 41], [44, 39], [51, 26], [33, 67], [37, 48], [64, 50], [2, 55], [1, 34], [37, 22], [60, 69], [12, 62], [34, 60], [61, 36], [24, 25], [4, 44], [69, 39], [5, 44], [2, 23], [59, 15], [61, 52], [56, 64], [34, 70], [70, 26], [70, 11], [26, 6], [14, 66], [46, 44], [40, 53], [58, 29], [39, 30], [38, 21], [42, 18], [13, 35], [30, 28], [34, 42], [25, 34], [62, 5], [7, 17], [14, 25], [34, 28], [32, 31], [21, 56], [30, 63], [40, 61], [68, 25], [8, 25], [23, 27], [67, 43], [33, 16], [13, 60], [9, 64], [21, 22], [9, 3], [2, 40], [6, 25], [9, 69], [3, 41], [70, 51], [42, 15], [49, 45], [45, 50], [40, 67], [31, 5], [70, 37], [25, 9], [58, 64], [52, 57], [69, 65], [43, 54], [10, 32], [43, 38], [67, 19], [62, 60], [23, 33], [52, 65], [61, 69], [21, 57], [22, 16], [31, 15], [1, 43], [57, 32], [18, 66], [33, 52], [55, 20], [59, 70], [15, 51], [53, 16], [4, 15], [43, 47], [22, 5], [32, 63], [2, 33], [45, 35], [29, 56], [62, 7], [68, 20], [4, 11], [33, 38], [9, 59], [18, 25], [60, 27], [10, 17], [15, 20], [37, 49], [2, 14], [49, 6], [59, 69], [45, 25], [10, 28], [10, 29], [6, 52], [23, 51], [33, 50], [35, 65], [6, 10], [48, 13], [7, 18], [64, 3], [16, 46], [63, 8], [22, 42], [21, 52], [38, 8], [14, 30], [11, 20], [61, 9], [55, 34], [40, 8], [63, 32], [17, 48], [49, 57], [22, 27], [40, 24], [23, 18], [47, 23], [36, 33], [12, 13], [49, 38], [22, 24], [45, 18], [23, 48], [5, 20], [2, 44], [21, 4], [1, 2], [15, 38], [11, 25], [52, 45], [58, 5], [68, 47], [55, 29], [36, 1], [47, 28], [18, 68], [46, 1], [8, 20], [14, 24], [57, 28], [58, 59], [18, 29], [47, 20], [28, 62], [65, 15], [63, 13], [28, 2], [37, 39], [28, 69], [26, 13], [57, 49], [21, 68], [43, 42], [66, 62], [1, 26], [36, 58], [6, 15], [57, 67], [26, 10], [67, 37], [46, 43], [9, 4], [2, 51], [59, 51], [20, 24], [48, 69], [16, 31], [51, 65], [37, 30], [4, 20], [2, 65], [33, 8], [29, 16], [47, 45], [67, 62], [66, 14], [7, 40], [16, 65], [60, 58], [32, 24], [48, 34], [27, 18], [16, 64], [54, 58], [9, 38], [20, 4], [59, 59], [64, 49], [63, 62], [60, 14], [23, 64], [4, 41], [32, 61], [10, 57], [56, 57], [13, 65], [46, 54], [45, 24], [70, 55], [49, 53], [29, 1], [39, 24], [33, 33], [10, 20], [31, 69], [17, 69], [4, 43], [10, 23], [20, 62], [60, 37], [25, 12], [60, 52], [52, 46], [7, 10], [38, 62], [64, 31], [9, 46], [40, 16], [58, 9], [30, 21], [55, 14], [58, 46], [65, 64], [62, 45], [44, 24], [54, 37], [65, 10], [28, 45], [38, 60], [50, 36], [59, 17], [39, 20], [43, 65], [6, 46], [7, 23], [5, 42], [32, 23], [56, 66], [52, 55], [27, 2], [11, 12], [66, 43], [25, 60], [27, 42], [69, 58], [57, 64], [68, 42], [41, 54], [40, 41], [15, 4], [65, 37], [19, 8], [70, 22], [52, 62], [16, 50], [54, 50], [46, 8], [45, 52], [7, 64], [51, 32], [20, 46], [32, 38], [62, 68], [43, 51], [36, 66], [21, 5], [57, 25], [49, 50], [47, 69], [8, 26], [41, 23], [4, 17], [60, 40], [16, 22], [10, 2], [30, 8], [5, 47], [12, 54], [61, 37], [62, 67], [46, 24], [2, 61], [55, 35], [38, 4], [29, 48], [59, 46], [44, 32], [50, 29], [24, 18], [48, 48], [15, 1], [2, 16], [41, 55], [53, 50], [56, 69], [24, 52], [41, 20], [58, 54], [45, 8], [12, 60], [45, 23], [55, 12], [32, 22], [1, 40], [5, 64], [51, 39], [14, 12], [23, 12], [58, 12], [10, 5], [44, 59], [59, 64], [62, 52], [68, 28], [56, 2], [21, 45], [39, 34], [20, 70], [61, 10], [30, 65], [52, 69], [28, 13], [64, 10], [51, 10], [43, 58], [64, 51], [70, 42], [69, 70], [38, 47], [62, 30], [3, 6], [61, 29], [47, 2], [35, 27], [38, 34], [34, 45], [17, 52], [42, 66], [64, 56], [68, 35], [16, 27], [62, 42], [54, 69], [66, 42], [44, 64], [27, 11], [45, 31], [12, 38], [33, 58], [48, 36], [67, 70], [67, 13], [41, 52], [40, 35], [68, 9], [21, 26], [47, 19], [14, 69], [64, 37], [47, 12], [64, 12], [5, 57], [54, 27], [25, 36], [1, 66], [40, 20], [17, 47], [38, 14], [46, 14], [20, 8], [60, 38], [18, 17], [45, 21], [25, 63], [48, 54], [45, 15], [34, 50], [47, 35], [64, 29], [53, 12], [22, 59], [29, 52], [29, 9], [29, 8], [47, 1], [20, 3], [33, 46], [20, 67], [49, 39], [21, 28], [41, 68], [17, 15], [29, 7], [28, 70], [60, 9], [23, 50], [1, 20], [13, 4], [21, 43], [2, 41], [60, 22], [54, 41], [11, 42], [38, 3], [6, 33], [58, 41], [37, 60], [37, 41], [38, 28], [43, 5], [14, 43], [61, 65], [32, 59], [53, 53], [46, 26], [7, 54], [36, 68], [48, 42], [27, 36], [66, 48], [54, 25], [1, 55], [45, 65], [61, 8], [9, 9], [5, 4], [40, 40], [70, 65], [25, 19], [65, 54], [32, 53], [55, 65], [39, 69], [20, 7], [4, 56], [50, 65], [15, 46], [20, 55], [14, 33], [9, 70], [66, 64], [4, 69], [8, 11], [26, 63], [40, 48], [52, 66], [45, 6], [51, 41], [40, 5], [70, 8], [2, 7], [24, 35], [9, 23], [69, 42], [53, 58], [22, 13], [67, 67], [57, 22], [61, 23], [61, 62], [56, 47], [3, 54], [59, 52], [62, 54], [16, 44], [60, 43], [16, 60], [52, 25], [41, 63], [4, 47], [62, 66], [43, 29], [3, 60], [3, 26], [11, 62], [57, 20], [54, 35], [24, 5], [63, 70], [30, 41], [33, 10], [58, 18], [67, 5], [43, 55], [63, 55], [39, 15], [47, 60], [52, 44], [13, 40], [39, 32], [50, 57], [68, 4], [42, 48], [39, 58], [25, 21], [20, 11], [14, 20], [36, 18], [30, 14], [60, 54], [27, 31], [44, 13], [34, 55], [1, 60], [42, 25], [8, 50], [26, 52], [40, 26], [43, 27], [7, 5], [39, 9], [18, 49], [40, 36], [59, 14], [19, 30], [26, 32], [14, 34], [4, 60], [70, 39], [23, 36], [46, 49], [27, 63], [8, 63], [66, 26], [50, 55], [55, 27], [58, 2], [64, 5], [34, 15], [6, 48], [24, 63], [20, 48], [25, 43], [61, 13], [55, 39], [65, 68], [44, 28], [53, 32], [42, 14], [27, 4], [42, 70], [33, 31], [19, 49], [14, 5], [47, 4], [44, 30], [32, 56], [1, 28], [12, 25], [23, 37], [60, 50], [28, 18], [16, 3], [67, 6], [42, 16], [41, 56], [61, 64], [56, 25], [23, 11], [68, 52], [65, 34], [38, 24], [19, 24], [50, 62], [40, 56], [6, 43], [33, 30], [8, 60], [6, 13], [42, 62], [6, 50], [18, 38], [48, 43], [1, 52], [12, 69], [30, 58], [38, 45], [9, 22], [46, 58], [4, 22], [24, 64], [22, 62], [46, 15], [44, 37], [12, 58], [51, 9], [27, 23], [70, 6], [58, 70], [15, 12], [9, 27], [55, 25], [17, 27], [62, 56], [10, 41], [40, 9], [13, 44], [61, 57], [65, 8], [48, 63], [9, 31], [13, 2], [40, 31], [58, 58], [33, 7], [67, 60], [29, 23], [51, 15], [18, 59], [49, 30], [29, 21], [49, 66], [14, 40], [57, 30], [42, 40], [2, 12], [21, 67], [26, 45], [44, 7], [63, 29], [52, 21], [69, 24], [29, 66], [2, 54], [12, 19], [45, 61], [58, 52], [10, 49], [59, 63], [38, 69], [11, 33], [67, 4], [53, 5], [67, 3], [61, 63], [28, 17], [23, 4], [48, 60], [35, 4], [25, 70], [24, 61], [23, 22], [53, 21], [18, 43], [22, 10], [29, 39], [69, 41], [63, 1], [60, 70], [38, 20], [3, 58], [59, 42], [14, 22], [24, 20], [24, 30], [9, 65], [67, 30], [28, 12], [10, 43], [51, 28], [18, 60], [31, 6], [35, 25], [57, 8], [59, 5], [22, 44], [52, 22], [48, 37], [18, 34], [44, 65], [5, 29], [62, 26], [35, 22], [68, 30], [55, 33], [10, 52], [31, 21], [62, 25], [19, 40], [45, 17], [5, 33], [4, 18], [25, 24], [27, 60], [50, 9], [50, 2], [51, 25], [16, 28], [24, 43], [56, 23], [67, 35], [69, 45], [40, 46], [2, 17], [1, 45], [9, 6], [33, 49], [70, 3], [68, 6], [19, 34], [9, 63], [40, 17], [43, 66], [41, 11], [36, 39], [69, 13], [13, 23], [40, 23], [64, 13], [13, 57], [10, 37], [61, 68], [32, 26], [2, 21], [28, 29], [34, 3], [42, 36], [43, 35], [55, 48], [46, 33], [11, 48], [20, 15], [49, 8], [69, 31], [50, 41], [6, 23], [52, 49], [41, 51], [64, 27], [56, 38], [33, 70], [35, 2], [18, 31], [53, 17], [70, 66], [57, 27], [1, 4], [31, 66], [21, 65], [54, 62], [43, 70], [5, 18], [43, 60], [10, 16], [48, 25], [3, 10], [31, 62], [52, 43], [28, 48], [16, 34], [53, 70], [37, 55], [52, 52], [29, 15], [38, 46], [54, 23], [51, 30], [66, 30], [59, 40], [59, 41], [19, 12], [12, 9], [40, 29], [31, 47], [62, 13], [22, 60], [50, 45], [50, 31], [37, 17], [37, 61], [50, 13], [4, 5], [53, 49], [29, 49], [47, 53], [36, 24], [22, 20], [48, 29], [11, 69], [33, 21], [13, 36], [59, 24], [20, 64], [17, 5], [62, 70], [40, 51], [58, 67], [29, 12], [49, 29], [7, 42], [37, 38], [64, 60], [9, 12], [51, 2], [29, 17], [25, 35], [44, 14], [4, 4], [28, 57], [12, 36], [52, 64], [56, 11], [41, 5], [10, 50], [69, 10], [69, 19], [14, 31], [55, 55], [15, 56], [54, 67], [38, 59], [3, 24], [13, 69], [55, 1], [13, 46], [42, 54], [70, 32], [5, 22], [51, 53], [45, 32], [37, 6], [14, 58], [32, 7], [11, 58], [10, 58], [21, 64], [43, 53], [43, 17], [41, 40], [70, 54], [27, 44], [45, 39], [27, 8], [9, 14], [10, 13], [36, 67], [16, 33], [22, 11], [62, 23], [38, 22], [24, 34], [1, 32], [44, 70], [7, 33], [15, 11], [28, 21], [29, 44], [28, 38], [34, 8], [36, 57], [26, 53], [13, 3], [24, 66], [66, 58], [35, 33], [18, 4], [15, 68], [20, 5], [8, 13], [59, 53], [25, 1], [37, 57], [2, 62], [50, 10], [48, 47], [65, 7], [4, 55], [70, 50], [38, 9], [57, 68], [70, 1], [18, 7], [38, 65], [56, 9], [41, 26], [28, 67], [64, 32], [4, 63], [5, 60], [31, 55], [66, 61], [10, 31], [40, 15], [14, 44], [8, 51], [53, 33], [68, 26], [16, 6], [8, 64], [49, 24], [62, 27], [32, 60], [46, 40], [39, 40], [36, 29], [4, 23], [51, 43], [52, 60], [39, 26], [11, 4], [7, 38], [50, 3], [68, 57], [4, 25], [59, 62], [30, 27], [5, 36], [11, 24], [63, 21], [12, 18], [58, 13], [57, 29], [67, 33], [69, 48], [19, 52], [14, 63], [31, 70], [64, 19], [56, 20], [49, 14], [5, 70], [38, 50], [1, 42], [42, 49], [42, 41], [33, 4], [68, 43], [46, 69], [4, 7], [10, 54], [6, 45], [23, 28], [36, 21], [28, 52], [27, 22], [5, 15], [51, 50], [56, 22], [38, 44], [42, 52], [62, 20], [48, 55], [32, 54], [10, 66], [2, 34], [50, 51], [34, 51], [31, 49], [64, 43], [58, 15], [28, 42], [41, 39], [67, 1], [5, 3], [45, 2], [28, 26], [13, 51], [44, 29], [19, 67], [22, 67], [22, 70], [45, 27], [55, 68], [29, 60], [25, 22], [64, 63], [35, 11], [47, 67], [39, 8], [11, 70], [60, 11], [15, 14], [36, 54], [17, 43], [52, 42], [53, 48], [31, 32], [45, 38], [14, 53], [61, 3], [49, 63], [46, 62], [51, 59], [29, 57], [11, 16], [53, 29], [11, 10], [5, 27], [9, 60], [2, 27], [53, 27], [4, 70], [7, 21], [25, 52], [15, 5], [11, 56], [59, 45], [34, 7], [18, 53], [64, 59], [64, 65], [12, 37], [1, 24], [7, 1], [2, 46], [19, 26], [66, 9], [43, 12], [54, 48], [17, 33], [31, 22], [40, 32], [47, 70], [12, 66], [53, 51], [47, 6], [41, 46], [66, 24], [54, 18], [26, 29], [46, 19], [13, 39], [59, 25], [25, 2], [2, 48], [66, 39], [4, 49], [56, 34], [63, 65], [62, 50], [36, 53], [55, 58], [21, 40], [9, 62], [14, 10], [6, 18], [40, 65], [15, 53], [49, 18], [49, 44], [46, 38], [1, 54], [50, 37], [25, 67], [1, 53], [7, 4], [28, 8], [42, 60], [26, 68], [46, 57], [18, 5], [25, 4], [55, 18], [1, 57], [19, 53], [60, 41], [12, 24], [67, 11], [63, 23], [3, 67], [7, 47], [41, 21], [43, 68], [24, 54], [58, 40], [20, 35], [26, 56], [13, 67], [54, 24], [1, 41], [48, 44], [40, 3], [40, 10], [23, 2], [7, 12], [21, 62], [34, 6], [17, 49], [64, 69], [21, 66], [46, 21], [30, 12], [29, 64], [13, 66], [44, 4], [54, 66], [31, 2], [31, 53], [41, 59], [33, 20], [33, 48], [11, 26], [60, 23], [69, 7], [26, 48], [67, 54], [15, 22], [62, 19], [39, 36], [64, 66], [10, 65], [54, 19], [61, 42], [38, 16], [25, 17], [57, 39], [10, 61], [31, 25], [37, 56], [6, 8], [46, 3], [29, 27], [23, 66], [34, 32], [62, 3], [27, 68], [22, 41], [29, 11], [56, 10], [51, 16], [53, 37], [6, 60], [30, 69], [44, 26], [68, 36], [55, 32], [64, 39], [31, 45], [60, 47], [13, 56], [70, 59], [38, 43], [10, 59], [20, 45], [37, 27], [49, 13], [27, 35], [2, 22], [39, 41], [35, 40], [70, 36], [53, 60], [47, 58], [38, 5], [60, 26], [37, 4], [60, 30], [9, 61], [13, 11], [20, 25], [50, 47], [24, 21], [37, 59], [47, 33], [64, 8], [52, 28], [19, 6], [27, 62], [10, 64], [46, 34], [60, 33], [69, 68], [11, 36], [56, 67], [42, 65], [3, 34], [47, 62], [18, 42], [25, 66], [65, 47], [68, 45], [5, 2], [1, 70], [19, 66], [8, 48], [53, 40], [54, 59], [5, 31], [38, 33], [25, 54], [40, 60], [63, 68], [45, 22], [15, 19], [33, 18], [47, 25], [36, 30], [5, 52], [53, 38], [10, 3], [18, 65], [10, 26], [47, 38], [10, 69], [18, 8], [8, 65], [57, 33], [30, 4], [22, 7], [64, 14], [4, 35], [46, 11], [65, 18], [48, 41], [22, 54], [34, 40], [18, 64], [39, 10], [47, 65], [8, 43], [47, 31], [13, 20], [61, 53], [11, 46], [11, 1], [17, 58], [24, 23], [67, 34], [4, 48], [67, 25], [63, 4], [19, 44], [42, 39], [46, 63], [66, 37], [59, 50], [41, 66], [31, 14], [9, 33], [42, 10], [66, 7], [33, 69], [23, 25], [48, 9], [53, 64], [8, 31], [53, 66], [30, 36], [31, 19], [61, 38], [31, 7], [17, 1], [36, 46], [24, 6], [19, 37], [36, 41], [35, 60], [38, 51], [57, 65], [8, 58], [67, 49], [69, 57], [13, 22], [11, 30], [47, 21], [23, 21], [31, 10], [5, 24], [45, 47], [19, 36], [23, 59], [25, 39], [18, 70], [58, 50], [50, 60], [20, 20], [65, 57], [46, 59], [14, 62], [23, 20], [44, 61], [41, 8], [40, 42], [62, 59], [39, 52], [13, 61], [52, 27], [10, 48], [30, 31], [18, 3], [49, 17], [50, 50], [8, 30], [18, 15], [21, 1], [56, 48], [65, 27], [14, 45], [64, 15], [20, 43], [34, 13], [43, 37], [51, 70], [64, 64], [49, 1], [66, 21], [28, 53], [61, 56], [35, 45], [1, 23], [26, 35], [11, 11], [17, 2], [19, 31], [23, 54], [69, 9], [26, 69], [69, 67], [15, 64]]

class Map(object):
  def __init__(self, N, trees):
    self.N = N
    # (N + 2) x (N + 2) empty map with borders along 
    # x = { 0, N + 1 } and y = { 0, N + 1 }
    self.locations = [([1]*(N + 2) if (i == 0 or i == (N + 1)) 
      else [1] + [0]*N +[1]) for i in range(N + 2)]
    for coord in trees:    
      self.locations[coord[0]][coord[1]] = 1    
  def visited(self, node):
    return self.locations[node.x][node.y]
  def visit(self, node):
    self.locations[node.x][node.y] = 1

class Node(object):
  def __init__(self, x, y):
    self.x = x # x coordinate
    self.y = y # y coordinate
    self.g = 0 # the cost of the path from the start node to this node
    self.h = 0 # a heuristic function that estimates the cost of the cheapest 
               # path from this node to the goal
  def __lt__(self, other):
    return (self.g + self.h) < (other.g + other.h)
  def __eq__(self, other):
    return self.x == other.x and self.y == other.y

# A* search algorithm (https://en.wikipedia.org/wiki/A*_search_algorithm)
def A_star(start, target, map):
  map.visit(start)
  open = [ start ]
  while len(open) > 0:
    node = open.pop(0)    
    if (node == target):
      return node.g
      break
    for neighbor in [ Node(node.x - 1, node.y), Node(node.x + 1, node.y), 
                      Node(node.x, node.y - 1), Node(node.x, node.y + 1)]:
      if not map.visited(neighbor):
        map.visit(neighbor)
        neighbor.g = node.g + 1
        neighbor.h = abs(target.x - neighbor.x) + abs(target.y - neighbor.y)
        bisect.insort(open, neighbor)  

if __name__ == "__main__":
  start = Node(65, 4)
  target = Node(7, 62)  
  map = Map(70, tree_coordinates)
  print("Answer:", A_star(start, target, map))

Alan Enrique Ontiveros Salazar
Dec 27, 2018

It's just a standard BFS problem:

var grid = []
var visited = []
var dist = []

for(var i = 0; i <= 70; ++i){
    grid[i] = [];
    visited[i] = [];
    dist[i] = [];
    for(var j = 0; j <= 70; ++j){
        grid[i][j] = '.';
        visited[i][j] = false;
        dist[i][j] = -1;
    }
}

//points is the array given in the txt file
points.forEach(p => grid[p[0]][p[1]] = '#')

function valid(x,y){
    return 1 <= x && x <= 70 && 1 <= y && y <= 70 && grid[x][y] == '.' && !visited[x][y]
}

var start = {x:65, y:4}
var end = {x:7, y:62}
var queue = [start]

visited[start.x][start.y] = true;
dist[start.x][start.y] = 0;

var movs = [[1,0],[-1,0],[0,1],[0,-1]]

for(var i = 0; i < queue.length; ++i){
    var curr = queue[i];
    if(curr.x == end.x && curr.y == end.y) break;
    for(var m = 0; m < 4; ++m){
        var dest = {x:curr.x+movs[m][0], y:curr.y+movs[m][1]};
        if(valid(dest.x, dest.y)){
            visited[dest.x][dest.y] = true;
            dist[dest.x][dest.y] = dist[curr.x][curr.y] + 1;
            queue.push(dest);
        }
    }
}

console.log(dist[end.x][end.y]);

Day 4: It's Lovely Weather for a Sleigh Ride Together

The answer is 144.

4 solutions

0 pending reports