In [8]:
heatMapHelper('Volume', 'Volume that Requires Max Steps', 'Max Steps Volume', 1, df = df)
from math import gcd as GCD
import matplotlib as mpl
import matplotlib.pyplot as plt
import numpy as np
from numpy import nan as NaN
import pandas as pd
import seaborn as sns
#Fill a pitcher.
def fill(p) :
q = p.copy()
q[1] = q[2]
return(q)
#Completely empty a pitcher.
def empty(p) :
q = p.copy()
q[1] = 0
return(q)
#Transfer the contents of pitcher 1 to pitcher 2,
#until pitcher 1 is empty or pitcher 2 is filled
#to the top—whichever comes first.
def transfer(p1, p2):
q1 = p1.copy()
q2 = p2.copy()
#Remaining space in pitcher 2.
feasible = q2[2] - q2[1]
#Until pitcher1 is empty.
if q1[1] < feasible :
q2[1] += q1[1]
q1[1] = 0
#Pitcher 2 is filled.
else :
q2[1] = q2[2]
q1[1] -= feasible
return(q1, q2)
#Checks all states in the next step with statesMatrix.
def nextStep(states, statesMatrix, steps):
new_states = []
steps += 1
for state in states:
A = state[0]
B = state[1]
#If it hasn't existed, fill A to create a new state.
if np.isnan(statesMatrix[A[2]][B[1]]):
statesMatrix[A[2]][B[1]] = steps
new_states.append([fill(A), B])
#If it hasn't existed, fill B to create a new state.
if np.isnan(statesMatrix[A[1]][B[2]]) :
statesMatrix[A[1]][B[2]] = steps
new_states.append([A, fill(B)])
#If it hasn't existed, empty A to create a new state.
if np.isnan(statesMatrix[0][B[1]]) :
statesMatrix[0][B[1]] = steps
new_states.append([empty(A), B])
#If it hasn't existed, empty B to create a new state.
if np.isnan(statesMatrix[A[1]][0]) :
statesMatrix[A[1]][0] = steps
new_states.append([A, empty(B)])
#If the amount in A is LESS than REMAINING in B, and if it hasn't existed, empty A into B to create a new state.
if A[1] < B[2]-B[1]:
if np.isnan(statesMatrix[0][A[1]+B[1]]) :
statesMatrix[0][A[1]+B[1]] = steps
new_states.append(transfer(A, B))
#If the amount in A is GREATER than REMAINING in B, and if it hasn't existed, pour A into and fill B to create a new state.
if A[1] >= B[2]-B[1]:
if np.isnan(statesMatrix[A[1]+B[1]-B[2]][B[2]]) :
statesMatrix[A[1]+B[1]-B[2]][B[2]] = steps
new_states.append(transfer(A, B))
#If the amount in B is LESS than REMAINING in A, and if it hasn't existed, empty B into A to create a new state.
if B[1] < A[2]-A[1]:
if np.isnan(statesMatrix[A[1]+B[1]][0]) :
statesMatrix[A[1]+B[1]][0] = steps
new_states.append(list(reversed(transfer(B, A))))
#If the amount in B is MORE than REMAINING in A, and if it hasn't existed, pour B into and fill A to create a new state.
if B[1] >= A[2]-A[1]:
if np.isnan(statesMatrix[A[2]][A[1]+B[1]-A[2]]) :
statesMatrix[A[2]][A[1]+B[1]-A[2]] = steps
new_states.append(list(reversed(transfer(B, A))))
#As long as there are new states to check, keep parsing through the array.
if len(new_states) > 0 :
return(nextStep(new_states, statesMatrix, steps))
#Done!
else:
return(statesMatrix)
#Get the volume that requires the most steps in the matrix.
def getSteps(statesMatrix, a, b, print_max):
volumes = []
for i in range(a+1):
#i <= b can be in either A or B. Therefore check rows and columns.
if i <= b :
volumes.append(min(min(statesMatrix[i]),
min(statesMatrix.transpose()[i])))
# b < i <= a can only be in A.
else :
volumes.append(min(statesMatrix[i]))
v = [i for i in range(len(volumes)) if volumes[i] == max(volumes)][0]
s = max(volumes)
if print_max :
print(str(v) + " liters takes " + str(s) + " steps.")
print()
return(volumes, [v,s])
A = ['A', 0, 10]
B = ['B', 0, 3]
statesMatrix = np.array([[NaN for b in range(B[2]+1)] for a in range(A[2]+1)])
#Initial state.
statesMatrix[0][0] = 0
states = [[A, B]]
statesMatrix = nextStep(states, statesMatrix, 0)
fiddler = getSteps(statesMatrix, A[2], B[2], True)
5 liters takes 12.0 steps.
A = ['A', 0, 100]
B = ['B', 0, 93]
statesMatrix = np.array([[NaN for b in range(B[2]+1)] for a in range(A[2]+1)])
#Initial state.
statesMatrix[0][0] = 0
states = [[A, B]]
statesMatrix = nextStep(states, statesMatrix, 0)
extra_credit = getSteps(statesMatrix, A[2], B[2], True)
50 liters takes 190.0 steps.
#Maximum of a or b.
n = 200
df = pd.DataFrame(columns=['A', 'B', 'Volume', 'Steps'])
for b in range(1, n+1) :
for a in range(b, n+1) :
if GCD(a,b) == 1:
#Initialize
#Pitcher = [name, current volume, capacity]
A = ['A', 0, a]
B = ['B', 0, b]
statesMatrix = np.array([[NaN for b in range(B[2]+1)] for a in range(A[2]+1)])
#Initial state.
statesMatrix[0][0] = 0
states = [[A, B]]
statesMatrix = nextStep(states, statesMatrix, 0)
volume, max_steps = getSteps(statesMatrix, A[2], B[2], False)[1]
df.loc[len(df)] = [a, b, volume, max_steps]
if a!=b :
df.loc[len(df)] = [b, a, volume, max_steps]
else:
df.loc[len(df)] = [a, b, NaN, NaN]
if a!=b :
df.loc[len(df)] = [b, a, NaN, NaN]
df['Ratio'] = df['Steps'] / (df['A'] + df['B'])
def heatMapHelper(m, title, colorbartitle, i, df = df):
sns.set()
fig = plt.figure(figsize = (13, 10))
ax = fig.add_subplot(xlim = (0.5, 200.5),
ylim = (0.5, 200.5))
heatmap = plt.scatter(x = df['A'],
y = df['B'],
c = df[m],
cmap = 'viridis_r',
marker = "s",
s = 5,
alpha = 0.8,)
#norm = mpl.colors.LogNorm())
#Title setup.
ax.set_title(title, fontsize = 24)
#X-axis setup.
ax.set_xlabel('Volume of Pitcher A', fontsize = 20)
#Y-axis setup.
ax.set_ylabel('Volume of Pitcher B', fontsize = 20)
ax.tick_params(axis = 'both', which = 'major', labelsize = 16)
#Colorbar.
f ='%.0f'
if i != 3:
f ='%.0f'
lp = -85
else:
f ='%.2f'
lp = -90
cb = plt.colorbar(heatmap, format = f)
cb.set_label(colorbartitle,
labelpad = lp,
rotation = 90,
fontsize = 20)
cb.ax.tick_params(labelsize = 16)
fig.savefig("2024.03.29." + str(i) + ".png", bbox_inches = 'tight');
heatMapHelper('Volume', 'Volume that Requires Max Steps', 'Max Steps Volume', 1, df = df)
heatMapHelper('Steps', 'Minimum Number of Steps to Achieve any Volume', 'Steps', 2, df = df)
heatMapHelper('Ratio', 'Ratio of Minimum Number of Steps to Sum of Pitcher Volumes', 'Ratio of Steps to Total Volume', 3, df = df)
