Witam, to mój pierwszy post i proszę z góry o nie hejtowanie i konstruktywne odpowiedzi nawet jeśli kogoś urażę czymś :)
Borykam się od paru dni z dość nietypowym problemem (prawdopodobnie banalnie prostym).
Mianowicie, mam do wykonania algorytm który będzie miał na wejściu dane z pliku w 4 linijkach.
Wpierw należy je załadować z pliku i odpowiednio przerobić co wstępnie poczyniłem, chodź w jednym miejscu nie do końca jestem pewny wykonania tego prawidłowo (nawiąże w kodzie do tego).
Plik z danymi wygląda np:
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
Pierwsza linia zawiera długość cyklu tudzież list z wartościami poniżej.
Druga zawiera wagi poszczególne ustawione od 1 - 10
Trzeci i czwarty jest to odpowiednia kolejnośc ustawienia wag.
Początkowe ustawienie wag jest według drugiego wiersza.
Czwarty wiersza jest to ustawienie docelowe które chcemy osiągnąć zmieniająć ustawienie z drugiego wiersza obliczając najniższy nakład konieczny do przesunięcia wag by osiągnać docelowy czwarty wiersz.
Bardziej szczegółowo i dokładnie opisane jest to tu:
https://drive.google.com/file/d/1Yn3yEPB0oCbjeDQrai5a_XdFCyxJV7l0/view?usp=sharing
Znalazłem również docelowe rozwiązania tego problemu w 3 językach (C++, Java, Pascal) i próbowałem opierać się na nich i tym co wczesniej stworzyłem osiągnąć podobny cel ale utknałem w paru miejscach.
https://github.com/mostafa-saad/MyCompetitiveProgramming/tree/master/Olympiad/POI/official/2009/code/slo/prog
Mój kod póki co wyglądał następująco:
class BajtackieZoo:
def __init__(self, fileName):
self.data = self.readData(fileName)
self.n = self.insertElementToIdx(self.data[1], self.data[2])
self.n1 = self.insertElementToIdx(self.data[1], self.data[3])
def readData(self, dataFile):
with open(dataFile, 'rb') as f:
self.dataStore = []
lines = f.readlines()
for line in lines:
self.dataStore.append([int(v) for v in line.split()])
return self.dataStore
def insertElementToIdx(self, list1, list2):
newList = []
data1, data2 = list(list1), list(list2)
[newList.insert(i, data1[data2[i]-1]) for i in range(0, len(list1))]
return newList
f = BajtackieZoo('slo1.in')
print(f.n, f.n1)
Przez moment myślałem że SUPER osiągnałem dużo bo podstawiłem WAGI pod odpowiednie numery czy to z USTAWIENIA TRZECIEGO WIERSZA czy DOCELOWEGO CZWARTEGO WIERSZA, ale w zasadzie tu utknałem na pewien czas gdyż nie do końca jestem pewny czy konieczne jest ten krok w tym zadaniu i po znalezieniu kodów które załączyłem na GITHUBie w JAVA/C++/PASCAL tego przykładu, zrozumiałem ze chyba nie do końca dobrze to zrobiłem i funkcja insertElementToIdx(self, list1, lsit2) w zasadzie niczego nie wnosi, wiec postanowiłem spróbować przeanalizowac kody z tych 3 języków (pliki: SLO.CPP , SLO1.JAVA, SLO2.PAS, SLO3.CPP) i spróbować to na Python'a wklepać i chyba nie do końca udolnie mi to idzie.
Wiem że zaraz poleje się pewnie fala krytyki, ale nie do końca rozumiem w tych plikach linii:
SLO1.JAVA
[26] static boolean[] vis = new boolean[MAXN];
[[41] wagi[a] = Integer.parseInt(input.nextToken());
[42] minw = Math.min(minw, wagi[a]);
[46] orig[a] = Integer.parseInt(input.nextToken())-1;
[49] perm[Integer.parseInt(input.nextToken())-1] = orig[a];
I [53] + reszta zaimplementowanie tego w Python.
To znaczy rozumiem prawie wszystko z tego, no ale gdybym wszystko co konieczne rozumiał to bym nie prosił o pomoc, nie oczekuje gotowego rozwiązania żeby nie było, oczekuje raczej wsparcia lub nakierowania i wyjaśnienia, za co będę niezmiernie wdzięczny.
Kod który napisałem i wkleiłem wyżej to pierwsza wersja, tak jak wspominałem próbowałem przeskalować 1:(prawie)1 opierając się na kodach które tu podałem pod linkiem , wrzucę go najwyżej poleje się na mnie fala krytyki.
class slo1:
def __init__(self, fileName):
self.readData(fileName)
def readData(self, dataFile):
INF = 1000000000
MAXN = 1000000
wagi = []
orig = []
perm = []
# Tak jak ww. [26] lini kodu tu próbowałem w Python'ie ustawić Boolean w taki sposób
vis = [False for i in range(MAXN)]
minw = INF
with open(dataFile, 'rb') as f:
self.dataStore = []
lines = f.readlines()
for line in lines:
self.dataStore.append([int(v) for v in line.split()])
LC = int((str(self.dataStore[0])).strip("[]"))
# Wczytanie WAG
for i in range(0, LC):
wagi.append(self.dataStore[1][i])
minw = min(wagi)
print('[DEBUG INFO:] (wagi == dataStore[1])', wagi == self.dataStore[1])
print('[DEBUG INFO:] (minw)', minw)
# Wczytanie pierwszego ustawienia
for i in range(0, LC):
orig.append(self.dataStore[2][i])
print('[DEBUG INFO:] (orig == dataStore[2])', self.dataStore[1], self.dataStore[2])
# Wczytanie (próba nieudolna) wczytania drugiego ustawienia - tu w ogóle nie jestem przekonany do tego co zrobiłem (myślałem nad itertools i permutation)
for i in range(0, LC):
perm.insert(orig[i], self.dataStore[3][i])
print('[DEBUG INFO:] (perm == dataStore[3])', perm, self.dataStore[3])
# A tu próbowałem 1:1 spróbować osiągnąć podobny efekt petli i obliczeń, niestety nie działa
wynik = 0
for pocz in range(0, LC):
if not vis[pocz]:
minc = INF
suma = 0
dl = 0
cur = pocz
while True:
if wagi[cur-1] < minc:
minc = wagi[cur-1]
suma = suma + wagi[cur-1]
cur = perm[cur-1]
vis[cur] = True
dl = dl + 1
if cur == pocz:
break
if suma+(dl-2)*minc<suma+minc+(dl+1)*minw:
wynik = wynik+suma+(dl-2)*minc
else:
wynik = wynik+suma+minc+(dl+1)*minw;
print(wynik)
Zoo = slo1('slo1.in')
Jeśli ktoś miał by chwile i ochotę odpowiedzieć na ten post byłbym wdzięczny, powtórze że nie oczekuje gotowego rozwiązania i uwierzcie mi że wiele stron w tym stack'a i tutaj przeglądałem i innych z tutorialami i wieloma funkcjami , po prostu NIE MAM POMYSŁU i być może po prostu jestem debilem.