I was solving money transfer problem.
1st way
def optimise_transfer(data):
ans = process_data(data)
ans = [int(i[1]) for i in ans]
print(ans)
ans = [i-100 for i in ans]
def dfs(ans,start):
while start<len(ans) and ans[start]==0:
start+=1
if start==len(ans):
return 0
transfer=int(10e9)
for i in range(start+1,len(ans)):
if ((ans[start]<0 and ans[i]>0) or (ans[start]>0 and ans[i]<0)):
ans[start]+=ans[i]
transfer = min(transfer, dfs(ans,start+1)+1)
ans[start]-=ans[i]
return transfer if transfer!=int(10e9) else 0
val = dfs(ans,0)
print(val)2nd way (the way i normally do it)
needa check why it doesnt update the global variable
min_transfers = float('inf')
def optimise_transfer(data):
ans = process_data(data)
ans = [int(i[1]) for i in ans]
print(ans)
ans = [i-100 for i in ans]
def dfs(ans, start, current_transfers):
global min_transfers
while start < len(ans) and ans[start] == 0:
start += 1
if start == len(ans):
min_transfers = min(min_transfers, current_transfers)
return
for i in range(start + 1, len(ans)):
if ((ans[start] < 0 and ans[i] > 0) or (ans[start] > 0 and ans[i] < 0)):
ans[start] += ans[i]
dfs(ans[:], start + 1, current_transfers + 1) # Pass a copy of ans to avoid modifying the original
ans[start] -= ans[i]
dfs(ans, 0, 0)
print(min_transfers)
# Example usage:
optimise_transfer(data)
