Mercurial > lbo > hg > juliaplay
view python/dp.py @ 9:33a23228ef5c
dp: two more problems
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 19 Feb 2023 15:58:28 +0100 |
parents | 809f7d058647 |
children | 27f59dd007ab |
line wrap: on
line source
import numpy as np from functools import cache @cache def number_of_binary_trees(n): if n == 0: return 1 elif n == 1: return 1 else: N = 0 for i in range(0, n): N += number_of_binary_trees(i) * number_of_binary_trees(n-i-1) return N @cache def number_of_full_binary_trees(n): if n <= 1: return 1 elif n%2 == 0: return 0 else: N = 0 # Only odd numbers possible. for nleft in range(1, n, 2): nright = n-1-nleft N += number_of_full_binary_trees(nleft) * number_of_full_binary_trees(nright) return N @cache def circle_chords(n): if n <= 1: return 0 elif n == 2: return 1 else: N = 0 for i in range(0, n): for j in range(i+1, n): left = j - i - 1 right = n - 2 - left N += 1 + circle_chords(left) * circle_chords(right) return N def subset_sum(s, n, tot): if tot == 0: return True if n < 0 or tot < 0: return False incl = subset_sum(s, n-1, tot-s[n]) if incl: return True excl = subset_sum(s, n-1, tot) return excl def equal_partitions(s): S = sum(s) if len(s) == 0 or S % 2 == 1: return False return subset_sum(s, len(s)-1, S/2) def find_min_matrix_path(mat, i=0, j=0, mem=dict()): # Find min-cost path from (0,0) to mat.shape - (1,1) if (i+1, j+1) == mat.shape: return mat[i, j] if (i,j) in mem: return mem[i,j] if i < mat.shape[0]-1: via_right = find_min_matrix_path(mat, i+1, j, mem) else: via_right = 1e6 if j < mat.shape[1]-1: via_down = find_min_matrix_path(mat, i, j+1, mem) else: via_down = 1e6 if via_right < via_down: mem[i,j] = mat[i,j] + via_right return mem[i,j] else: mem[i,j] = mat[i,j] + via_down return mem[i,j] def count_matrix_paths_with_cost(mat, cost, i=0, j=0): # Dest. is implicitly bottom right corner # Base case: if (i+1,j+1) == mat.shape: return cost == mat[i,j], [[(i,j)]] if i < mat.shape[0]-1: via_right, rp = count_matrix_paths_with_cost(mat, cost - mat[i,j], i+1, j) else: via_right, rp = 0, [] if j < mat.shape[1]-1: via_down, dp = count_matrix_paths_with_cost(mat, cost - mat[i,j], i, j+1) else: via_down, dp = 0, [] paths = [] if via_down+via_right > 0: paths = [[(i,j)] + p for p in rp+dp] return (via_down + via_right, paths) def min_sum_partition(s, n, S1=0, S2=0): if n < 0: return S1, S2 s11, s21 = min_sum_partition(s, n-1, S1+s[n], S2) s12, s22 = min_sum_partition(s, n-1, S1, S2+s[n]) if abs(s11-s21) < abs(s12-s22): print(f"{s[n]} in S1") return s11, s21 else: print(f"{s[n]} in S2") return s12, s22 def rodcut(L, lengths, prices, mem=dict()): if L < min(lengths): mem[L] = ([], 0) return [], 0 if L in mem: return mem[L] best_l, best_p = [], 0 for (l, p) in zip(lengths, prices): if L < l: continue l_, p_ = rodcut(L-l, lengths, prices) if p + p_ > best_p: best_p = p+p_ best_l = [l] + l_ mem[L] = [best_l, best_p] return best_l, best_p @cache def island_death(N, nstep, i=0, j=0): if i < 0 or j < 0 or i >= N or j >= N: return 1 elif nstep <= 0: return 0 else: return 1/4 * ( island_death(N, nstep-1, i-1, j) + island_death(N, nstep-1, i+1, j) + island_death(N, nstep-1, i, j-1) + island_death(N, nstep-1, i, j+1))