Using standard input I read four rows of data:
- number of elements (elements are numbered from 1 to n)
- n numbers corresponding to cost of moving each element
- n numbers corresponding to current position of each element (from 1 to n)
- n numbers corresponding to the position of each element in the desired state (from 1 to n)
I can swap every two elements I want. Cost of each operation is the sum of masses of that two elements. The program has to return minimum cost required to move elements to the desired state. The data is read using standard input (my_script.py<data.in)
2. My problem
I know the ideal theoretical solution to that problem, I created working python script but it is messy and slow. I am sure the way I convert the data to int values is stupid but I have to idea how to improve that. I am not sure if dividing list to cycles way I did is is OK, or it could be improved as well (graf is directed, but I think it doesn't matter)
method_1 and method_2 are correct mathematically, I don't won't to waste your time and try to explain why, though I am not sure if I implemented it properly.
I am new to almost every aspect of that task (data structures, standard input and so on). The code is messy.
10 3015 4728 4802 4361 135 4444 4313 1413 4581 546 3 10 1 8 9 4 2 7 6 5 4 9 5 3 1 6 10 7 8 2
Script I wrote:
#! /usr/bin/python3 import sys lines =  for line in sys.stdin: stripped = line.strip() if not stripped: break lines.append(stripped) a, b, c, d = lines a = a.split(" ") b = b.split(" ") c = c.split(" ") d = d.split(" ") masses = [int(i) for i in b] unsorted = [int(i) for i in c] sorted = [int(i) for i in d] def dfs_test(masses, unsorted, sorted): segregated =  cycles =  cost = 0 for index, element in enumerate(unsorted): cycle =  if element in segregated: continue if not sorted[index] == element: while element not in cycle: cycle.append(element) segregated.append(element) index = sorted.index(element) element = unsorted[index] else: cycle.append(element) cycles.append(cycle) for cycle in cycles: if len(cycle) == 2: for element in cycle: cost += masses[element-1] if len(cycle) >= 3: sum_mass_cycle =  for element in cycle: sum_mass_cycle.append(masses[element-1]) method_1 = sum(sum_mass_cycle) + (len(cycle) - 2) * min(sum_mass_cycle) method_2 = sum(sum_mass_cycle) + min(sum_mass_cycle) + (len(cycle) + 1) * min(masses) cost += min(method_1, method_2) return cost if __name__ == "__main__": print(dfs_test(masses, unsorted, sorted))