brad
BAN USERdef get_count_0s(a):
if not a:
return -1
return _get_count_0s(a, 0.5, 0, len(a) - 1)
def _get_count_0s(a, t, beg_i, end_i):
if beg_i == end_i:
if a[beg_i] == 1:
return beg_i # it’s the index
return beg_i + 1
mid_i = (beg_i + end_i) // 2
if a[mid_i] < t: # must look higher
return _get_count_0s(a, t, mid_i + 1, end_i)
return _get_count_0s(a, t, beg_i, mid_i - 1) # must look lower
print(get_count_0s([0] * 9 + [1] * 8))
I decided to receive the input as an array of open space nodes.
def update_guard_distances(open_space_nodes):
for open_space_node in open_space_nodes:
open_space_node.get_distance_to_guard()
MAX = 10000000
class Node():
def __init__(self, label, neighbors, connected_to_guard=False, dist_to_guard=None):
self.label = label
self.open_neighbors = neighbors
self.connected_directly_to_guard = connected_to_guard
self.distance_to_guard = dist_to_guard
def get_distance_to_guard(self):
# base case
if self.connected_directly_to_guard:
self.distance_to_guard = 1
# recursive case / need to populate
elif not self.distance_to_guard:
closest_distance_to_guard = MAX
for neighbor in self.open_neighbors:
closest_distance_to_guard = min(closest_distance_to_guard, 1 + neighbor.get_distance_to_guard())
self.distance_to_guard = closest_distance_to_guard
# has been populated
return self.distance_to_guard
a = Node('a', [])
b = Node('b', [])
c = Node('c', [])
d = Node('d', [], True)
a.open_neighbors.append(d)
e = Node('e', [d])
d.open_neighbors.append(a)
d.open_neighbors.append(e)
nodes = [a, b, c, d, e]
update_guard_distances(nodes)
for node in nodes:
if node.distance_to_guard:
print(node.distance_to_guard)
I decided to receive the input as an array of open space nodes.
{{
def update_guard_distances(open_space_nodes):
for open_space_node in open_space_nodes:
open_space_node.get_distance_to_guard()
MAX = 10000000
class Node():
def __init__(self, label, neighbors, connected_to_guard=False, dist_to_guard=None):
self.label = label
self.open_neighbors = neighbors
self.connected_directly_to_guard = connected_to_guard
self.distance_to_guard = dist_to_guard
def get_distance_to_guard(self):
# base case
if self.connected_directly_to_guard:
self.distance_to_guard = 1
# recursive case / need to populate
elif not self.distance_to_guard:
closest_distance_to_guard = MAX
for neighbor in self.open_neighbors:
closest_distance_to_guard = min(closest_distance_to_guard, 1 + neighbor.get_distance_to_guard())
self.distance_to_guard = closest_distance_to_guard
# has been populated
return self.distance_to_guard
a = Node('a', [])
b = Node('b', [])
c = Node('c', [])
d = Node('d', [], True)
a.open_neighbors.append(d)
e = Node('e', [d])
d.open_neighbors.append(a)
d.open_neighbors.append(e)
nodes = [a, b, c, d, e]
update_guard_distances(nodes)
for node in nodes:
if node.distance_to_guard:
print(node.distance_to_guard)
}}
Assuming we are given the coordinates of the 0 that may be surrounded. Otherwise, we would check every single 0, keeping track of the 0s that have already been checked.
def island_of_0s_is_completely_surrounded_by_1s(bool_m, row_of_0, col_of_0):
unexplored = [(row_of_0, col_of_0)]
visited = []
for row in bool_m:
visited.append([0] * len(bool_m[0]))
while unexplored:
cur_row, cur_col = unexplored.pop()
if bool_m[cur_row][cur_col] == None:
return False
visited.append((cur_row, cur_col))
append_if_valid(cur_row-1, cur_col, unexplored, bool_m)
append_if_valid(cur_row, cur_col-1, unexplored, bool_m)
append_if_valid(cur_row+1, cur_col, unexplored, bool_m)
append_if_valid(cur_row, cur_col+1, unexplored, bool_m)
return True
def append_if_valid(row, col, candidates_to_explore, matrix):
if (row, col) not in candidates_to_explore and row >= 0 and col >=0 and row < len(matrix) and col < len(matrix[0]):
if matrix[row][col] != 1:
candidates_to_explore.append((row, col))
print island_of_0s_is_completely_surrounded_by_1s([[1, 1, 1], [1, None, 0]], 1, 2)
# even more efficient way
def get_longest_consecutive_alpha_path_using_graph(m):
directed_graph_of_letters_indices = {}
# first create a directed graph of letter indices
for i in range(len(m)):
for j in range(len(m[0])):
directed_graph_of_letters_indices[(i, j)] = []
# loop through all 9 cases
for row in range(i-1, i+2):
for col in range(j-1, j+2):
if row >= 0 and col >= 0 and row < len(m) and col < len(m[0]):
if ord(m[i][j]) - 1 == ord(m[row][col]): # only put next consecutive neighbor in
directed_graph_of_letters_indices[(i, j)].append((row, col))
max_depth = 0
solutions_dict = {}
for key in directed_graph_of_letters_indices:
# do depth first search and put any solutions in solutions dict
if key not in solutions_dict:
max_depth = max(max_depth, 1 + get_greatest_depth(directed_graph_of_letters_indices, key, solutions_dict))
return max_depth
def get_greatest_depth(g, source, solutions_dict):
if source[0] == 0:
print source
if source in solutions_dict:
return solutions_dict[source]
neighbors = g[source]
max_depth = 0
for neighbor in neighbors:
max_depth = max(max_depth, 1 + get_greatest_depth(g, neighbor, solutions_dict))
solutions_dict[source] = max_depth
return max_depth
m = [['a', 'z', 'i', 'h', 'f'],
['b', 'j', 'd', 'e', 'g'],
['a', 'c', 'f', 'e', 'f'],
['a', 'z', 'd', 'e', 'f'],
]
print get_longest_consecutive_alpha_path_using_graph(m)
# more efficient way
solution_matrix = []
def _get_longest_efficient(root_str, m, row, col):
# base case
if row < 0 or col < 0 or row >= len(m) or col >= len(m[0]) or (row, col) in root_str: # can't look here
return 0
if root_str and ord(m[root_str[-1][0]][root_str[-1][1]]) + 1 != ord(m[row][col]): # not ascending
return 0
if solution_matrix[row][col] != 1:
return solution_matrix[row][col]
# recursive case
root_str.append((row, col))
max_length = 1
for i in range(row - 1, row + 2):
for j in range(col - 1, col + 2):
max_length = max(max_length, 1 + _get_longest_efficient(root_str, m, i, j))
solution_matrix[row][col] = max_length
return max_length
def get_longest_consecutive_alpha_path_more_efficient(m):
longest = 0
# initialize solution matrix
for row in m:
solution_matrix.append([1] * len(row))
# for all beginning points, explore and try to find longest
for i in range(len(m)):
for j in range(len(m[0])):
cur_len = _get_longest_efficient([], m, i, j)
longest = max(cur_len, longest)
return longest
def _get_longest_inefficient(root_str, m, row, col):
# base case
if row < 0 or col < 0 or row >= len(m) or col >= len(m[0]) or (row, col) in root_str: # can't look here
return 0
if root_str and ord(m[root_str[-1][0]][root_str[-1][1]]) + 1 != ord(m[row][col]): # not ascending
return 0
# recursive case
root_str.append((row, col))
max_length = 1
for i in range(row - 1, row + 2):
for j in range(col - 1, col + 2):
max_length = max(max_length, 1 + _get_longest_inefficient(root_str, m, i, j))
return max_length
def get_longest_consecutive_alpha_path_inefficient(m):
longest = 0
# for all beginning points, explore and try to find longest
for i in range(len(m)):
for j in range(len(m[0])):
cur_len = _get_longest_inefficient([], m, i, j)
longest = max(cur_len, longest)
return longest
m = [['a', 'z', 'i', 'h', 'f'],
['b', 'j', 'd', 'e', 'g'],
['a', 'c', 'f', 'e', 'f'],
['a', 'z', 'd', 'e', 'f'],
]
print get_longest_consecutive_alpha_path_inefficient(m)
Repbilliejeckley, SEO at Flipkart
Spent 2002-2008 testing the market for spit-takes in Los Angeles, CA. Spent 2001-2004 deploying how to get boyfriend back by ...
this solution is O(n log n + kn) where n is the amount of floats and k is the max amount of elements in a range of 1.
- brad June 16, 2015