Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
kenken1
#python 3.5.2 _n = 9 _regions = """ 1 2 2 3 4 5 5 5 6 1 7 8 8 4 9 9 10 6 7 7 11 11 11 11 12 10 13 14 14 15 15 16 17 12 10 13 18 19 20 21 16 17 17 22 23 18 19 20 21 16 24 25 22 23 18 26 26 27 27 24 25 28 28 29 29 30 31 32 32 32 32 28 33 33 30 31 34 34 34 35 35""" _operations = "+10 +14 +8 +11 +11 +10 +11 +9 +7 +15 +30 +9 +7 +10 +6 +6 +20 +21 +6 +9 +10 +6 +17 +7 +10 +7 +12 +17 +8 +13 +8 +30 +10 +10 +10" actions = [] def get_combo_list(r, n, listvar, leftToChoose=-1, combo=None, source=None): # print('call with '+str(r)+' of '+str(n)+' left='+str(leftToChoose)+' combo='+str(combo)+' source='+str(source)) if combo is None: # print('option 1 depth '+str(depth)) combination = [] source = [] for i in range(0,n): source.append(i+1) get_combo_list(r, n, listvar, r, combination, source) elif leftToChoose > 0: # print('option 2 depth '+str(depth)) for i in range(0,len(source)): e = source[i] newcombo = combo.copy() newcombo.append(e) if leftToChoose == 1: listvar.append(newcombo) else: index = i+1 if index < len(source): newsource = source.copy()[i+1:] get_combo_list(r, n, listvar, leftToChoose-1, newcombo, newsource) # setval # rempos # mark def add_action(actions, op, v, row, col): actions.append((op, v, row, col)) def create_regions(ops, cell_str, n): regions = {} cells = cell_str.split() for i in range(0,n): for j in range(0,n): index = i*n + j key = int(cells[index]) if key in regions.keys(): cell_list = regions[key] else: cell_list = [] cell_list.append((i,j)) regions[key] = cell_list operations = ops.split() i = 1 for o in operations: oper = o[0] res = int(o[1:]) cell_list = regions[i] regions[i] = (oper, res, cell_list) i += 1 return regions _regions = """ 1 2 2 3 4 5 5 5 6 1 7 8 8 4 9 9 10 6 7 7 11 11 11 11 12 10 13 14 14 15 15 16 17 12 10 13 18 19 20 21 16 17 17 22 23 18 19 20 21 16 24 25 22 23 18 26 26 27 27 24 25 28 28 29 29 30 31 32 32 32 32 28 33 33 30 31 34 34 34 35 35""" _operations = "+10 +14 +8 +11 +11 +10 +11 +9 +7 +15 +30 +9 +7 +10 +6 +6 +20 +21 +6 +9 +10 +6 +17 +7 +10 +7 +12 +17 +8 +13 +8 +30 +10 +10 +10" # Create a 2-dimensional array of size nxn that initially holds 1-n for every cell def create_possibles(n): res = [] for i in range(0,n): row = [] for j in range(0,n): poss = [] for p in range(1,n+1): poss.append(p) row.append(poss) res.append(row) return res # Create a 2-dimensional array of size nxn that initially holds 0 for every cell def create_values(n): res = [] for i in range(0,n): row = [] for j in range(0,n): row.append(0) res.append(row) return res def show_poss(possibles): n = len(possibles) for row in range(0,n): s = '' for col in range(0,n): p = possibles[row][col] for i in range(1,n+1): if i in p: s = s + str(i) else: s = s + ' ' s = s + " | " print(s) # Create a deep copy of a square 2-dimensional array def copy_possibles(possibles): n = len(possibles) poss2 = [] for rr in range(0,n): row = [] for cc in range(0,n): p = (possibles[rr][cc]).copy() row.append(p) poss2.append(row) return poss2 # Return the total number of possible values in the possibles array def get_possibles_number(possibles): n = len(possibles) res = 0 for rr in range(0,n): for cc in range(0,n): res += len(possibles[rr][cc]) return res def is_poss(possibles, p, row, col): if p in possibles[row][col]: return True else: return False def remove_poss(possibles, p, row, col): if p in possibles[row][col]: (possibles[row][col]).remove(p) return True return False def add_poss(possibles, p, row, col): if p not in possibles[row][col]: (possibles[row][col]).append(p) def remove_poss_from_row_col(possibles, p, row, col): n = len(possibles) for i in range(0,n): remove_poss(possibles, p, row, i) remove_poss(possibles, p, i, col) def remove_all_poss(possibles, row, col): (possibles[row][col]).clear() #recursive def calc_possibles_commutative_region(op, goal_res, cell_list, possibles, good_permutations=None, res_so_far=-999, curr_perm=[]): if res_so_far == -999: #first time call good_permutations = [] if op == '+': so_far = 0 elif op == '*': so_far = 1 else: so_far = res_so_far #get coordinates of the first cell in the list row = cell_list[0][0] col = cell_list[0][1] poss = possibles[row][col] for p in poss: curr_perm.append(p) if op == '+': so_far2 = so_far + p elif op == '*': so_far2 = so_far * p possibles2 = copy_possibles(possibles) remove_poss_from_row_col(possibles2, p, row, col) if len(cell_list) > 1: calc_possibles_commutative_region(op, goal_res, cell_list[1:], possibles2, good_permutations=good_permutations, res_so_far=so_far2, curr_perm=curr_perm) elif so_far2 == goal_res: good_permutations.append(curr_perm.copy()) del curr_perm[len(curr_perm)-1] if res_so_far == -999: #first time call, all recursion is over for row, col in cell_list: remove_all_poss(possibles, row, col) for perm in good_permutations: for i in range(0, len(perm)): val = perm[i] row = cell_list[i][0] col = cell_list[i][1] add_poss(possibles, val, row, col) # make a deep copy of a list of native types def copy_list(in_array): out_list = [] for e in in_array: out_list.append(e) return out_list # Return a list of all combinations of the given length choosing from numbers between 1 and n. def get_all_combinations(length, n, poss=None): p = poss if p is None: p = [ x for x in range(1, n+1) ] if length == 1: return p res = [] for i in range(0,len(p)-length+1): firstElement = p[i] combinations2 = get_all_combinations(length-1, n, p[(i+1):]) for c in combinations2: combo = [firstElement] if length == 2: combo.append(c) else: for e in c: combo.append(e) res.append(combo) return res def get_all_permutations_recursive(length, n): if length == 1: return [ [x] for x in range(1, n+1) ] else: perms_b = get_all_permutations(length-1, n) all_perms = [] for v in range(1, n+1): for prev in perms_b: cp = copy_list(prev) cp.append(v) all_perms.append( cp ) return all_perms # does not work if length>2, but I do not need it to # division and subtraction are binary def get_all_permutations(length, n, poss=None): p = poss if p is None: p = [ x for x in range(1, n+1) ] if length == 1: return p res = [] for i in range(0,len(p)-length+1): firstElement = p[i] p2 = copy_list(p) p2.pop(i) combinations2 = get_all_combinations(length-1, n, p2) for c in combinations2: combo = [firstElement] if length == 2: combo.append(c) else: for e in c: combo.append(e) res.append(combo) return res def calc_possibles_noncommutative_region(op, goal_res, cell_list, possibles, good_permutations=None, res_so_far=-999, curr_perm=[]): if len(cell_list) != 2: return i = 0 cellPoss0 = copy_list(possibles[cell_list[i][0]][cell_list[i][1]]) remove_all_poss(possibles, cell_list[i][0], cell_list[i][1]) i = 1 cellPoss1 = copy_list(possibles[cell_list[i][0]][cell_list[i][1]]) remove_all_poss(possibles, cell_list[i][0], cell_list[i][1]) for a in cellPoss0: for b in cellPoss1: if op == '-': if (a-b) == goal_res or (b-a) == goal_res: print((a,b)) i = 0 add_poss(possibles, a, cell_list[i][0], cell_list[i][1]) i = 1 add_poss(possibles, b, cell_list[i][0], cell_list[i][1]) elif op == '/': if (a/b) == goal_res or (b/a) == goal_res: i = 0 add_poss(possibles, a, cell_list[i][0], cell_list[i][1]) i = 1 add_poss(possibles, b, cell_list[i][0], cell_list[i][1]) # Set value and adjust the possibilites in the same row and column def set_value(values, v, row, col, possibles): n = len(possibles) values[row][col] = v for i in range(0, n): remove_poss(possibles, v, i, col) remove_poss(possibles, v, row, i) possibles[row][col] = [v] # add_poss(possibles, v, row, col) def process_all_regions(reg, values, possibles): for i in range(1, len(reg)+1): if reg[i][0] in ['+', '*']: calc_possibles_commutative_region(reg[i][0], reg[i][1], reg[i][2], possibles) elif reg[i][0] in ['-', '/']: calc_possibles_noncommutative_region(reg[i][0], reg[i][1], reg[i][2], possibles) def process_all_single_possibles(values, possibles, n): for row in range(0, n): for col in range(0, n): if len(possibles[row][col]) == 1: v = possibles[row][col][0] set_value(values, v, row, col, possibles) def get_row_as_list_of_coordinates(row, n): res = [] for i in range(0,n): res.append((row,i)) return res def get_col_as_list_of_coordinates(col, n): res = [] for i in range(0,n): res.append((i,col)) return res # return a list of the cells that are not set, along with their possible values # [ [1,2,3,8,9], ((0,0), [1,2,3]), ((0,2), [2,3,8]), ((0,3), [3,8,9]) ] def get_possibles_in_coordinate_list(coordinates, values, possibles, n): res = [1] netposs = [] for c in coordinates: v = values[c[0]][c[1]] if v == 0: poss = possibles[c[0]][c[1]].copy() res.append((c,poss)) for p in poss: if not (p in netposs): netposs.append(p) res[0] = netposs return res # If only one cell in the list can have a given value, then assign that value to the cell. def process_single_poss_in_coordinate_list(coordinates, possibles, values, n): plist = get_possibles_in_coordinate_list(coordinates, values, possibles, n) for v in plist: count,row,col = 0,0,0 for c in coordinates: if is_poss(possibles, v, c[0], c[1]): count += 1 row = c[0] col = c[1] if count == 1: set_value(values, v, row, col, possibles) def process_rows(possibles, values, n): for row in range(0,n): rlist = get_row_as_list_of_coordinates(row, n) process_single_poss_in_coordinate_list(rlist, possibles, values, n) def process_cols(possibles, values, n): for col in range(0,n): rlist = get_col_as_list_of_coordinates(col, n) process_single_poss_in_coordinate_list(rlist, possibles, values, n) # Return True if all the possiblities are in the given list def has_all(poss, n): if len(poss) == 0: return False poss.sort() prev = -666 count = 0 for i in poss: if i != prev: prev = i count += 1 return (count == n) # Return True if # Every row has every value set or possible # No cells have zero possibles # No duplicate values in rows or columns # Else return False def puzzle_ok(possibles, values): n = len(possibles) for row in range(0,n): vals = [] poss = [] for col in range(0,n): if values[row][col] > 0: vals.append(values[row][col]) poss.append(values[row][col]) if len(possibles[row][col]) == 0: return False for p in possibles[row][col]: poss.append(p) if has_all(poss, n) == False: return False v1 = -1 for v2 in vals: if v1 == v2: return False for col in range(0,n): vals = [] poss = [] for row in range(0,n): if values[row][col] > 0: vals.append(values[row][col]) poss.append(values[row][col]) if len(possibles[row][col]) == 0: return False for p in possibles[row][col]: poss.append(p) if has_all(poss, n) == False: return False v1 = -1 for v2 in vals: if v1 == v2: return False return True def add_poss_group(poss, poss_group): for v in poss_group: if v not in poss: poss.append(v) def overlap(p1, p2): res = [] for v in p1: if v in p2: res.append(v) return res # If a combination of x possibles is repeated in x cells, remove those possibles from the other cells. def process_possible_combos_helper(coordList, possibles, values): n = len(possibles) poss = get_possibles_in_coordinate_list(coordList, values, possibles, n) netposs = poss.pop(0) cellNum = len(poss) if cellNum == 0: return for i in range(0,cellNum): #c = poss[i][0] p = poss[i][1] maxlen = len(p) indexList = [i] possGroup = [] if (i+1) < cellNum: for j in range(i+1,cellNum): a = len(p) p2 = poss[j][1] b = len(p2) o = overlap(p, p2) c = len(o) maxlen = max(maxlen,a,b,c) if (a<=b and c==a) or (b<a and c==b): indexList.append(j) add_poss_group(possGroup, o) changed = False if len(indexList) == maxlen: for k in range(0,cellNum): if k not in indexList: for gp in possGroup: c = poss[k][0] row = c[0] col = c[1] rr = remove_poss(possibles, gp, row, col) changed = changed or rr if changed: return def process_possible_combos(possibles, values): n = len(possibles) for i in range(0,n): coordList = get_row_as_list_of_coordinates(i, n) process_possible_combos_helper(coordList, possibles, values) coordList = get_col_as_list_of_coordinates(i, n) process_possible_combos_helper(coordList, possibles, values) def process_puzzle(possibles, values, regions): possNum1 = get_possibles_number(possibles) n = len(possibles) cont = True while cont: process_all_regions(regions, values, possibles) process_all_single_possibles(values, possibles, n) process_rows(possibles, values, n) process_cols(possibles, values, n) process_possible_combos(possibles, values) possNum2 = get_possibles_number(possibles) if possNum1 == possNum2: cont = False else: possNum1 = possNum2 guess_stack = [] # Create a deep copy of a square 2-dimensional array def copy_state_to_stack(possibles, stackObj): n = len(possibles) for row in range(0,n): for col in range(0,n): stackObj.append((possibles[row][col]).copy()) # return the coordinates for a cell with the shortest possibles list def find_cell_to_guess(possibles): n = len(possibles) res = (-1,-1) nn = n + 1 for row in range(0,n): for col in range(0,n): g = len(possibles[row][col]) if g < nn and g > 1: nn = g res = (row,col) return res def restore_possibles(possibles, values, guessStack): n = len(possibles) startIndex = len(guessStack) -1 -1 -1 -(n*n) for row in range(0,n): for col in range(0,n): values[row][col] = 0 possibles[row][col] = (guessStack[startIndex + row*n + col]).copy() def advance_last_guess(possibles, values, guessStack): print('entering advance last guess') n = len(possibles) stackLen = len(guessStack) if stackLen == 0: print('Guess stack is empty.') return index = guessStack[stackLen - 1] guesses = guessStack[stackLen - 2] coordinates = guessStack[stackLen - 3] print('index is ' +str(index) + ', guesses are ' + str(guesses) + ', coordinates are ' + str(coordinates)) newIndex = index + 1 if newIndex < len(guesses): guessStack[stackLen - 1] = newIndex newGuess = guesses[newIndex] restore_possibles(possibles, values, guessStack) print('guess is ' + str(newGuess) + ' from list ' + str(guesses) + ' for cell ' + str(coordinates) + ' stack length is ' + str(len(guessStack))) set_value(values, newGuess, coordinates[0], coordinates[1], possibles) else: count = n*n + 3 j = stackLen - count while count > 0: guessStack.pop(j) count -= 1 advance_last_guess(possibles, values, guessStack) def process_guess_method(possibles, values, regions, guessStack, maxIterations): #maxIterations = 2 possNum = get_possibles_number(possibles) puzzleStillGood = True n = len(possibles) while possNum > (n*n): if puzzleStillGood == False: advance_last_guess(possibles, values, guessStack) else: guessCell = find_cell_to_guess(possibles) guesses = possibles[guessCell[0]][guessCell[1]] copy_state_to_stack(possibles, guessStack) guessStack.append(guessCell) guessStack.append(guesses) guessStack.append(0) #index of current guess print('guess is ' + str(guesses[0]) + ' from list ' + str(guesses) + ' for cell ' + str(guessCell) + ' stack length is ' + str(len(guessStack))) set_value(values, guesses[0], guessCell[0], guessCell[1], possibles) process_puzzle(possibles, values, regions) puzzleStillGood = puzzle_ok(possibles, values) possNum = get_possibles_number(possibles) if maxIterations > 0: maxIterations -= 1 else: return reg = create_regions(_operations, _regions, _n) #print (reg) possibles = create_possibles(_n) values = create_values(_n) #remove_poss(possibles, 3, 0, 0) if False: show_poss(possibles) i = 5 calc_possibles_commutative_region(reg[i][0], reg[i][1], reg[i][2], possibles) print('-------------------------------') show_poss(possibles) if False: remove_poss(possibles, 3, 0, 0) #remove_poss(possibles, 9, 0, 0) show_poss(possibles) i = 1 calc_possibles_noncommutative_region('/', 3, reg[i][2], possibles) print('-------------------------------') show_poss(possibles) if False: p6 = get_all_permutations(3, 5) print( len(p6) ) print( p6 ) if False: p6 = get_all_combinations(3, 5) print( len(p6) ) print( p6 ) #print( get_all_combinations(2, 7) ) if False: #remove_poss(possibles, 9, 0, 0) show_poss(possibles) process_puzzle(possibles, values, reg) print('-------------------------------') show_poss(possibles) #set_value(values, 5, 0, 1, possibles) #9 process_puzzle(possibles, values, reg) print('cell to guess is ' + str(find_cell_to_guess(possibles))) process_guess_method(possibles, values, reg, guess_stack, 5) print('-------------------------------') show_poss(possibles) print(get_possibles_number(possibles)) print( puzzle_ok(possibles, values) ) if False: cc = [] get_combo_list(1, 9, cc) print(cc) if True: #remove_poss(possibles, 9, 0, 0) show_poss(possibles) process_puzzle(possibles, values, reg) print('-------------------------------') show_poss(possibles) print(get_possibles_number(possibles)) print( puzzle_ok(possibles, values) )
run
|
edit
|
history
|
help
0
even odd
Ej2_PYTHON_203700377.
linked_lists
word repeat
N. Py
(P3) Starsza data
E
Exercise 4 for lesson 2
binarySearch.py
DISPLAY