rizTaak
BAN USERLetter/number at each location should be moved to its destination. In the end everything will be in place
def move_to_destination(chars, numbers):
for idx in range(len(numbers)):
if numbers[idx] != idx:
swap(idx, numbers[idx], chars, numbers)
def swap(from_idx, to_idx, chars, numbers):
chars[from_idx], chars[to_idx] = chars[to_idx], chars[from_idx]
numbers[from_idx], numbers[to_idx] = numbers[to_idx], numbers[from_idx]
Do breath first search. Space required is upper bounded by dictionary size. Same for time if we consider inner two loops 'constant' because of 26 letters and maximum length word :)
import string
def dict_distance(dict, source_word, target_word):
processed = {}
horizon = {source_word:0}
keep_going = True
while keep_going:
new_horizon = {}
for key, value in horizon.iteritems():
if key == target_word:
return value
else:
processed[key] = value
for char in string.ascii_lowercase:
for idx in range(0,len(key)):
new_word = key[:idx] + char + key[idx+1:]
if new_word in dict and new_word not in processed and new_word not in new_horizon:
new_horizon[new_word] = value + 1
keep_going = len(new_horizon) > 0
horizon = new_horizon
return None
def zeros_on_right(numbers):
last_unused = len(numbers) - 1
curr_index = 0
while curr_index < last_unused:
if numbers[curr_index] == 0:
numbers[curr_index], numbers[last_unused] = numbers[last_unused], numbers[curr_index]
last_unused -= 1
if numbers[curr_index] != 0:
curr_index += 1
return numbers
def cons_sum(numbers, sum):
start_idx = 0
end_idx = 0
calc_sum = numbers[0]
while start_idx <= end_idx and end_idx < len(numbers):
if calc_sum == sum:
return numbers[start_idx:end_idx+1]
elif calc_sum < sum:
end_idx += 1
if end_idx < len(numbers):
calc_sum += numbers[end_idx]
else:
calc_sum -= numbers[start_idx]
start_idx += 1
if end_idx < start_idx:
end_idx = start_idx
return []
def k_subset_sum(numbers, k, total):
sorted_numbers = sorted(numbers, reverse=True)
return k_subset_sum_internal(sorted_numbers, k, total, [])
def k_subset_sum_internal(numbers, k, total, current_list):
if k == 0:
if sum(current_list) == total:
return current_list
else:
return None
sum_so_far = sum(current_list)
upper_bound = total - sum_so_far - (k - 1)
for num in numbers:
if num <= upper_bound:
current_list.append(num)
result = k_subset_sum_internal(numbers, k - 1, total, current_list)
if result is not None:
return result
current_list.pop()
return None
print k_subset_sum([6,4,5,2,3,1], 4, 10)
k_map = None
def prepare_k_map(permutation):
global k_map
k_map = [[0 for x in range(len(permutation))] for x in range(len(permutation))]
for i in range(len(permutation)):
for j in range(len(permutation)):
k_map[i][j] = sorted(permutation[i:j])
def request(a, b, k):
global k_map
if not (a < len(k_map)):
return None
if not (b < len(k_map)):
return None
ab = k_map[a][b]
if not (k < len(ab)):
return None
return ab[k]
def permute_string(the_string):
string_list = list(the_string)
permute_string_internal('', 0, string_list)
def permute_string_internal(prefix, start_index, string_list):
if start_index < len(string_list):
char_at_start_index = string_list[start_index]
for index in range(start_index, len(string_list)):
char_at_index = string_list[index]
string_list[index] = char_at_start_index
string_list[start_index] = char_at_index
permute_string_internal(prefix + string_list[start_index], start_index + 1, string_list)
string_list[start_index] = char_at_start_index
string_list[index] = char_at_index
else:
print prefix
Repwilliamland1990, Associate at Advent
Gifted in donating shaving cream worldwide. Crossed the country getting my feet wet with the elderly in Salisbury, MD. Have ...
Repdianacloweryd, Developer Program Engineer at Accolite software
I am Diana from Reston USA . I work as an Agricultural and food science technician in Jumbo Sports. I help ...
Repthubmorfin, Android Engineer at ABC TECH SUPPORT
I am currently working as a safety-focused Service Technician from Red Bank. I execute routine maintenance work while advising clients ...
RepHelanZelda, Consultant at Advent
HelanZelda from Atlanta, GA, United States. I have a passion for exploring/sharing new ideas and experiences throughout the interdisciplinary ...
O(n), For every node get max from left branch and get min from right branch and check which one gives min diff compare to the node. Do recursively for each node in a tree and keep latest min result in variable. Both getting min/max from sub trees and recursion can be done in same tree recursion.
- rizTaak February 22, 2016