[Python][CheckiO] Open Labyrinth

Basically this task can be solved applying DFS algorithm.

If there's anything confusing, please refer to "Disposable teleports"

Link: http://bradyisstudying.blogspot.tw/2014/04/checkiopython-disposable-teleports.html

--

Some tricks are used for this task.

(1) map refinement to avoid 2x2 quad dead-lock

(2) path recording to avoid circular dead-lock

There is a strong relation between (1) and (2) and I believe (2) is a more general solution.

I will review my code sooner or later to make it more clear and intuitive

--

Following is the "raw" source code which is counter-intuitive, confusing, and containing lots of redundant code right now.LOL

  
 def is_north_valid(cur_pos, maze_map):  
   if cur_pos[0] - 1 < 0:  
     return False  
   if maze_map[ cur_pos[0] - 1][cur_pos[1]] == 0:  
     return True  
   return False

  
 def is_south_valid(cur_pos, maze_map):  
   if cur_pos[0] + 1 >= len(maze_map):  
     return False  
   if maze_map[ cur_pos[0] + 1][cur_pos[1]] == 0:  
     return True  
   return False

  
 def is_east_valid(cur_pos, maze_map):  
   if cur_pos[1] + 1 >= len(maze_map):  
     return False  
   if maze_map[ cur_pos[0]][cur_pos[1]+1] == 0:  
     return True  
   return False 

 
 def is_west_valid(cur_pos, maze_map):  
   if cur_pos[1] - 1 < 0:  
     return False  
   if maze_map[ cur_pos[0]][cur_pos[1]-1] == 0:  
     return True  
   return False 

 
 def get_num_to_go(cur_pos, maze_map):  
   count = 0  
   if is_south_valid(cur_pos, maze_map):  
     count += 1  
   if is_north_valid(cur_pos, maze_map):  
     count += 1  
   if is_west_valid(cur_pos, maze_map):  
     count += 1  
   if is_east_valid(cur_pos, maze_map):  
     count += 1  
   return count 

 
 def suggest_go(cur_pos, maze_map, prev_dir, direct):  
   num_to_go = get_num_to_go(cur_pos, maze_map)  
   if num_to_go > 1 and prev_dir == direct:  
     return False  
   else:  
     return True  

 def never_go(cur_pos, record_map, direct):  
   record = record_map[ cur_pos[0] ][ cur_pos[1] ]  
   #print(record)  
   #print(direct)  
   if direct not in record:  
     return True  
   else:  
     return False 

 
 def which_dir(cur_pos, l_path, maze_map, record_map, pop):  
   #print ('qq: '+str(record_map[9][5]))  
   if pop == False:  
     prev_dir = ''  
     if len(l_path) > 0:  
       prev_dir = l_path[ len(l_path) - 1 ]  
     if is_south_valid(cur_pos, maze_map) == True and prev_dir != 'N' and never_go(cur_pos, record_map, 'S') == True:  
       l_path.append('S')  
       record_map[ cur_pos[0] ][ cur_pos[1] ].append('S')  
       pop = False  
       cur_pos[0] += 1  
       return 'south'    
     elif is_east_valid(cur_pos, maze_map) == True and prev_dir != 'W' and never_go(cur_pos, record_map, 'E') == True:  
       l_path.append('E')  
       record_map[ cur_pos[0] ][ cur_pos[1] ].append('E')  
       pop = False  
       cur_pos[1] += 1  
       return 'east'  
     elif is_west_valid(cur_pos, maze_map) == True and prev_dir != 'E' and never_go(cur_pos, record_map, 'W') == True:  
       l_path.append('W')  
       record_map[ cur_pos[0] ][ cur_pos[1] ].append('W')  
       cur_pos[1] -= 1  
       pop = False  
       return 'west'  
     elif is_north_valid(cur_pos, maze_map) == True and prev_dir != 'S' and never_go(cur_pos, record_map, 'N') == True:  
       l_path.append('N')  
       record_map[ cur_pos[0] ][ cur_pos[1] ].append('N')  
       cur_pos[0] -= 1  
       pop = False  
       return 'north'  
     else:  
       #return 'dead'  
       print('d')  
       pop = True  
       return which_dir(cur_pos, l_path, maze_map, record_map, pop)  
   else: # pop case  
     prev_dir = l_path.pop()  
     prev_2_dir = l_path[ len(l_path) - 1 ]  
     if prev_dir == 'S':  
       cur_pos[0] -= 1  
       if is_east_valid(cur_pos, maze_map) == True and prev_2_dir != 'W':  
         l_path.append('E')  
         record_map[ cur_pos[0] ][ cur_pos[1] ].append('E')  
         cur_pos[1] += 1  
         pop = False  
         return 'east'  
       elif is_west_valid(cur_pos, maze_map) == True and prev_2_dir != 'E':  
         l_path.append('W')  
         record_map[ cur_pos[0] ][ cur_pos[1] ].append('W')  
         cur_pos[1] -= 1  
         pop = False  
         return 'west'  
       elif is_north_valid(cur_pos, maze_map) == True and prev_2_dir != 'S':  
         l_path.append('N')  
         record_map[ cur_pos[0] ][ cur_pos[1] ].append('N')  
         cur_pos[0] -= 1  
         pop = False  
         return 'north'  
       else:  
         #return 'dead'  
         pop = True  
         return which_dir(cur_pos, l_path, maze_map, record_map, pop)  
     elif prev_dir == 'E':  
       cur_pos[1] -= 1  
       if is_west_valid(cur_pos, maze_map) == True and prev_2_dir != 'E':  
         l_path.append('W')  
         record_map[ cur_pos[0] ][ cur_pos[1] ].append('W')  
         cur_pos[1] -= 1  
         pop = False  
         return 'west'  
       elif is_north_valid(cur_pos, maze_map) == True and prev_2_dir != 'S':  
         l_path.append('N')  
         record_map[ cur_pos[0] ][ cur_pos[1] ].append('N')  
         cur_pos[0] -= 1  
         pop = False  
         return 'north'  
       else:  
         #return 'dead'  
         pop = True  
         return which_dir(cur_pos, l_path, maze_map, record_map, pop)  
     elif prev_dir == 'W':  
       cur_pos[1] += 1  
       if is_north_valid(cur_pos, maze_map) == True and prev_2_dir != 'S':  
         l_path.append('N')  
         record_map[ cur_pos[0] ][ cur_pos[1] ].append('N')  
         cur_pos[0] -= 1  
         pop = False  
         return 'north'  
       else:  
         #return 'dead'  
         pop = True  
         return which_dir(cur_pos, l_path, maze_map, record_map, pop)  
     elif prev_dir == 'N':  
       cur_pos[0] += 1  
       #return 'dead'  
       pop = True  
       return which_dir(cur_pos, l_path, maze_map, record_map, pop) 

 
 def only_one_exit(row, col, maze_map):  
   count = 0  
   exit_code = 0  
   if maze_map[row][col-1] == 0:  
     exit_code = 1  
     count += 1  
   if maze_map[row+1][col-1] == 0:  
     exit_code = 2  
     count += 1  
   if maze_map[row-1][col] == 0:  
     exit_code = 3  
     count += 1  
   if maze_map[row-1][col+1] == 0:  
     exit_code = 4  
     count += 1  
   if maze_map[row+2][col] == 0:  
     exit_code = 5  
     count += 1  
   if maze_map[row+2][col+1] == 0:  
     exit_code = 6  
     count += 1  
   if maze_map[row][col+2] == 0:  
     exit_code = 7  
     count += 1  
   if maze_map[row+1][col+2] == 0:  
     exit_code = 8  
     count += 1  
   if count == 1:  
     return [True, exit_code]  
   else:  
     return [False, exit_code]  

 def refine_map(maze_map):  
   #case 1 : quad all zero  
   # 1 1 1 1   
   # 1 0 0 1  
   # 1 0 0 1  
   # 1 1 1 1  
   for row in range(2, len(maze_map) - 2): #dont need to touch (1,1) and (10, 10)  
     for col in range(2, len(maze_map) - 2):  
       if maze_map[row][col] == 0 and maze_map[row][col+1] == 0 and maze_map[row+1][col] == 0 and maze_map[row+1][col+1] == 0:  
         #print ('found quad: '+ str(row) +' '+ str(col))  
         l_map_scanner = only_one_exit(row, col, maze_map)  
         if l_map_scanner[0] == True:  
           #print ('found quad with one exit: '+ str(row) +' '+ str(col))  
           if l_map_scanner[1] == 1 or l_map_scanner[1] == 7:  
             maze_map[row + 1][col] = 1  
             maze_map[row + 1][col + 1] = 1  
           if l_map_scanner[1] == 2 or l_map_scanner[1] == 8:  
             maze_map[row][col] = 1  
             maze_map[row][col + 1] = 1  
           if l_map_scanner[1] == 3 or l_map_scanner[1] == 5:  
             maze_map[row][col + 1] = 1  
             maze_map[row + 1][col + 1] = 1  
           if l_map_scanner[1] == 4 or l_map_scanner[1] == 6:  
             maze_map[row ][col] = 1  
             maze_map[row + 1][col] = 1  
   return maze_map  

 def get_record_map(dim):  
   l_record_map = [ ]  
   ll_record_map = [ ]  
   for row in range(0, dim):  
     for col in range(0, dim):  
       l_record_map.append([ ])  
     ll_record_map.append(l_record_map)  
     l_record_map = [ ]  
   return ll_record_map  

 def checkio(maze_map):  
   l_path = [ ]  
   cur_pos = [1, 1]  
   maze_map = refine_map(maze_map)  
   record_map = get_record_map(len(maze_map))  
   #print(maze_map)  
   #for i in range(0, 50):  
   while cur_pos != [10, 10]:  
     dir = which_dir(cur_pos, l_path, maze_map, record_map, False)  
     #print(dir)  
   return ''.join(l_path)   

[Python][CheckiO]Feed Pigeons

Simple task, but the problem description is a lil bit hard to understand.

Therefore I made a representative figure as follows.

In the 1st minute, only one pigeon can be fed.

In the 2nd minute, besides the original pigeon(came in the 1st minute), another two pigeons come.

In the 3rd minute, another three comes beside to the original three (came in the 1st and 2nd minute)

--

According to the aforementioned description, we know the number of new pigeons is exactly the same as the delta of time (in minute)

After understanding the rules above, it is easy to calculate how many pigeons can be fed

--

Following is the source code:

 def add_new_pigeons(minute):  
   return minute 

 
 def calculate_total_pigeons(minute):  
   total = 0  
   for m in range(1, minute+1):  
     total += m  
   return total 

 
 def checkio(food):  
   minute = 1   
   while (food > 0):  
     new_group = add_new_pigeons(minute)  
     total_pigeons = calculate_total_pigeons(minute)  
     food -= total_pigeons  
     if food < 0:  
       new_pigeons = new_group - abs(food)  
       if new_pigeons < 0: # none of the new pigenons gets fed  
         new_pigeons = 0  
       return calculate_total_pigeons(minute - 1) + new_pigeons  
     elif food == 0:  
       return total_pigeons  
     minute += 1  

[Python][CheckiO] Radiation search

In order to solve this task, I use recursive flood fill algorithm to search the neighbor with same value.

Be attention to the usage of recursion, especially the push and pop operation of context (use return function in a suitable time).

Some tricks are used in this task.

(1) expand the matrix in order to avoid list boundary access violation

(2) use another matrix (traversed_mask) to avoid re-filling the region

--

Source code is listed as follows.

 #flood fill algorithm  

 def get_dim(matrix):  
   return len(matrix[0]) 

 
 def expand_matrix(dim, matrix):  
   ll_expanded_matrix = [ ]  
   l_expanded_row = []   
   for i in range(0, dim):  
     l_expanded_row.append(-1)  
   ll_expanded_matrix.append(l_expanded_row)  
   l_expanded_row = [-1] #point to another new list  
   for row in range(0, dim-2): #because dim is for expanded matrix  
     for col in range(0, dim-2):  
       l_expanded_row.append(matrix[row][col])  
     l_expanded_row.append(-1) #tail -1  
     ll_expanded_matrix.append(l_expanded_row)  
     l_expanded_row = [-1] #point to another new list  
   for i in range(0, dim):  
     l_expanded_row.append(-1)  
   ll_expanded_matrix.append(l_expanded_row)  
   return ll_expanded_matrix 

 
 def gen_traversed_mask(dim):  
   l_mask = [ ]  
   ll_mask = [ ]  
   for row in range(0, dim):  
     for col in range(0, dim):  
       l_mask.append(0)  
     ll_mask.append(l_mask)  
     l_mask = [ ]  
   return ll_mask 

 
 def is_same_union(x, y, matrix):  
   if matrix[y][x] == matrix[y-1][x] or matrix[y][x] == matrix[y+1][x] or matrix[y][x] == matrix[y][x+1] or matrix[y][x] == matrix[y][x-1]:  
     return True  
   else:  
     return False 

 
 def flood(x, y, target, dim, traversed_mask, matrix, count):  
   if x > 0 and x < dim - 1 and y > 0 and y < dim - 1 and traversed_mask[y][x] == 0:  
     if matrix[y][x] == target and is_same_union(x, y, matrix) == True:  
       count += 1  
     else:  
       return count  
     traversed_mask[y][x] = 1  
     count = flood(x-1, y , target, dim, traversed_mask, matrix, count)  
     count = flood(x+1, y , target, dim, traversed_mask, matrix, count)  
     count = flood(x , y-1, target, dim, traversed_mask, matrix, count)  
     count = flood(x , y+1, target, dim, traversed_mask, matrix, count)  
   return count  

 def checkio(matrix):  
   count = 0  
   ll_result = [ ]  
   dim = get_dim(matrix)+2 # add two for expanded matrix  
   expanded_matrix = expand_matrix(dim, matrix)  
   traversed_mask = gen_traversed_mask(dim)  
   for row in range(1, dim-1):  
     for col in range(1, dim-1):  
       count = flood(col, row, expanded_matrix[row][col], dim, traversed_mask, expanded_matrix, count)  
       ll_result.append([count, expanded_matrix[row][col]])  
       traversed_mask = gen_traversed_mask(dim)  
       count = 0  
   ll_result = sorted( ll_result, key=lambda l_result: l_result[0], reverse=True)  
   return ll_result[0]  

[Python][CheckiO] How much gold

In order to solve this problem, we need to calculate the following proportion

(a1) gold-tin

(a2) gold-copper

(a3) gold-iron

Once we got (a1), (a2), and (a3), we can calculate the proportion of gold applying the following equation:

gold = ( (a1)+(a2)+(a3) - 1 ) / 2

Therefore we can divide this question into three sub-questions (a1) (a2) (a3).

Firstly, we can categorize the given proportion into two classes.

(b1) proportion consists of "gold"

       Ex. gold-tin proportion

(b2) proportion doesn't consist of "gold"

       Ex. copper-iron proportion

If the given proportion belongs to (b1), we just return it

However, when it belongs to (b2), we return (1 - given_proportion)

And following is the source code

 from fractions import Fraction  

 METALS = ('gold', 'tin', 'iron', 'copper')  

 def get_proportion(ele1, ele2, ele3, ele4, alloys):  
   #print(ele1+','+ele2+','+ele3+','+ele4)  
   if ele1+'-'+ele2 in alloys:  
     return alloys[ele1+'-'+ele2]  
   elif ele2+'-'+ele1 in alloys:  
     return alloys[ele2+'-'+ele1]  
   elif ele3+'-'+ele4 in alloys:  
     return 1 - alloys[ele3+'-'+ele4]  
   elif ele4+'-'+ele3 in alloys:  
     return 1 - alloys[ele4+'-'+ele3]  
   else:  
     assert(0)  

 def checkio(alloys):  
   #step 1. find proportion of gold-tin, gold-iron, and gold-copper  
   gold_tin = get_proportion('gold', 'tin', 'iron', 'copper', alloys)  
   gold_iron = get_proportion('gold', 'iron', 'tin', 'copper', alloys)  
   gold_copper = get_proportion('gold', 'copper', 'tin', 'iron', alloys)  
   #step 2.   
   return Fraction(gold_tin + gold_iron + gold_copper - 1, 2)  

[Python][CheckiO] Solve Disposable teleports

Firstly I thought it was the Eular Circuit problem, so it took me couples of days to review the Eular Path and the Eular Circuit. During the implementation, I found it was not that hard and could be solved applying DFS algorithm.


Here's the source code

 def list_sub(l_a, l_b):  
   return [i for i in l_a if not i in l_b or l_b.remove(i)] 

 
 def bi_direction_list_sub(l_a, l_b):  
   l_valid_path = [ ]  
   for i in l_a:  
     rev_i = (i % 10) * 10 + (i // 10)  
     if not i in l_b:  
       if not rev_i in l_b:  
         l_valid_path.append(i)  
   return l_valid_path 

 
 def get_map_list(teleports_string):  
   l_map = [ int(i) for i in teleports_string.split(',')]  
   l_map_bi_direction = [i for i in l_map]  
   for p in l_map:  
     p_rev = (p % 10) * 10 + (p // 10)  
     l_map_bi_direction.append(p_rev)  
   sorted(l_map_bi_direction)  
   return l_map_bi_direction 

 
 def get_path(l_tel, l_ret, last_path, last_pop):  
   l_working_path = bi_direction_list_sub(l_tel, l_ret)  
   sorted(l_working_path)  
   for p in l_working_path:  
     if str(p)[0] == str(last_path)[ len(str(last_path)) - 1 ]:  
       if every_node_be_traversed(l_ret) == False:  
         if p > last_pop:  
           return p  
   return 'dead'  

 def every_node_be_traversed(l_ret):  
   l_traversed_node = [str(path)[0] for path in l_ret]  
   for i in range(1, 9):  
     if not str(i) in l_traversed_node:  
       return False  
   if str(l_ret[len(l_ret) - 1])[1] != '1':  
     return False  
   return True  

 def remove_path_from_candidate(l_tmp_tel, path):  
   rev_path = (path % 10) * 10 + (path // 10 )  
   if path in l_tmp_tel:  
     l_tmp_tel.remove(path)  
   if rev_path in l_tmp_tel:  
     l_tmp_tel.remove(rev_path) 

 
 def add_candidate(l_tmp_tel, path):  
   rev_path = (path % 10) * 10 + (path // 10 )  
   if not path in l_tmp_tel:  
     l_tmp_tel.append(path)  
   if not rev_path in l_tmp_tel:  
     l_tmp_tel.append(rev_path)

  
 def checkio(teleports_string):  
   l_ret = [ ]  
   l_tel = get_map_list(teleports_string)  
   l_tmp_tel = [i for i in l_tel]  
   last_path = 1  
   last_pop = 1  
   while every_node_be_traversed(l_ret) == False:  
     path = get_path(l_tmp_tel, l_ret, last_path, last_pop)  
     if path == 'dead': #dead end  
       if len(l_ret) == 0:  
         last_path = 1  
         last_pop = 1  
       else:  
         last_pop = l_ret.pop()  
         add_candidate(l_tmp_tel, last_pop)  
         if str(last_pop)[0] == '1':  
           last_path = 1  
           last = 1  
           continue  
         else:  
           last_path = l_ret[ len(l_ret) - 1]  
       continue  
     last_pop = 1  
     last_path = path  
     l_ret.append(path)  
     remove_path_from_candidate(l_tmp_tel, path)  
     l_tmp_tel = sorted(l_tmp_tel)  
     l_str_ret = [str(i)[0] for i in l_ret]  
   ret = ''.join(l_str_ret)+'1'  
   return ret  

[Python][CheckIO] Solve Ghosts age

莫名其妙一個簡單的題目寫了兩天於是紀念一下

 def is_fibonacci(num):  
   cur = 0  
   prev1 = 1  
   prev2 = 0  
   while cur < num:  
     cur = prev1 + prev2  
     prev2 = prev1  
     prev1 = cur  
   if num == cur:  
     return True  
   else:  
     return False  

 def checkio(opacity):  
   if opacity == 10000:  
     return 0  
   cur = 10000  
   last_fibonacci = 1  
   for yrs in range(1, 5000):  
     if is_fibonacci(yrs) == True:  
       if cur - yrs == opacity:  
         return yrs  
       else:  
         cur -= yrs  
         last_fibonacci = yrs  
     else:  
       if cur + 1 == opacity:  
         return yrs  
       else:  
         cur += 1  

[Python] Formatted Binary

>>> '{0:08b}'.format(6)
00000110

Just to explain the parts of the formatting string:

• {} places a variable into a string
• 0 takes the variable at argument position 0
• : adds formatting options for this variable (otherwise it would represent decimal 6)
• 08 formats the number to eight digits zero-padded on the left
• b converts the number to its binary representation

ref. http://stackoverflow.com/questions/10411085/converting-integer-to-binary-in-python