Euler Problem 52
It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.
My Solution
def permuted_multiples(x):
def check_equal_multiples(x):
x_2 = str(2*x)
x_3 = str(3*x)
x_4 = str(4*x)
x_5 = str(5*x)
x_6 = str(6*x)
list_nums = [''.join(sorted(x_2)),''.join(sorted(x_3)),''.join(sorted(x_4)),''.join(sorted(x_5)),''.join(sorted(x_6))]
return len(set(list_nums))==1
while not check_equal_multiples(x):
x+=1
return x
permuted_multiples(x=1)
Answer: 142857
Euler Problem 81
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.
$$
\begin{pmatrix}
\color{red}{131} & 673 & 234 & 103 & 18\\
\color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\
630 & 803 & \color{red}{746} & \color{red}{422} & 111\\
537 & 699 & 497 & \color{red}{121} & 956\\
805 & 732 & 524 & \color{red}{37} & \color{red}{331}
\end{pmatrix}
$$
Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
My Solution
import numpy as np
matrix = np.loadtxt("data/p81_matrix.txt", delimiter=",")
def min_path_sum(matrix):
# initialize state matrix
state_matrix = np.empty((matrix.shape))
state_matrix[0][0] = matrix[0][0]
height = matrix.shape[0]
width = matrix.shape[1]
# Dynamic programming approach, loop through matrix and update states.
for i in range(0,height):
for j in range(0,width):
# check edge cases
if ((i==0)&(j==0)):
pass
elif (i==0):
state_matrix[i][j] = state_matrix[i][j-1] + state_matrix[i][j]
elif (j==0):
state_matrix[i][j] = state_matrix[i-1][j] + state_matrix[i][j]
else:
# take min of prior two states and add new value
state_matrix[i][j] = min(state_matrix[i][j-1], state_matrix[i-1][j]) + matrix[i][j]
return state_matrix[height-1,width-1]
min_path_sum(matrix)
Answer: 427337