Lily's homework solution

solution.py

'''
https://www.hackerrank.com/challenges/lilys-homework/problem
題目的大意是給定一個list, 可以透過swap交換元素位置, 問最少交換次數下, 使sum(|arr[i]-arr[i-1]|, i in [1, len(n) - 1])最小
測資看起來是沒有重複的數字.
非常直觀的想法, 只要list是有序, 無論正序或逆序, 那相鄰元素之差一定最小, 整個list的差之和也必然最小,
所以我建立兩個圖,分別用原本的list和正序和逆序的list建圖.

建出來的圖必然成環,且每個node出度和入度都是1(有可能自己連自己),而且照著圖走,list就會排序完.
所以用dfs遍歷正序圖和逆序圖,比較誰走的邊少.
tc是O(2n + nlogn + 2n + 2n) = O(nlogn), sc是O(n)

在hackerrank上跑要設定遞迴限制,測資最多10萬個數字,遞迴10萬次
sys.setrecursionlimit(100000)
'''


def lilysHomework(arr):
    # if submitting to hackerrank, set sys.setrecursionlimit(100000) 
    adjacentList1, adjacentList2, visited1, visited2 = {i:[] for i in arr}, {i:[] for i in arr}, {}, {}
    arrSorted = sorted(arr)
    for from_, to in zip(arr, arrSorted):
        adjacentList1[from_].append(to)
        visited1[from_] = False
        assert len(adjacentList1[from_]) <= 1
    for from_, to in zip(arr, arrSorted[::-1]):
        adjacentList2[from_].append(to)
        visited2[from_] = False
        assert len(adjacentList2[from_]) <= 1

    def dfs(node, adjacentList, visited):
        if visited[node]: return 0
        visited[node] = True
        for neighbor in adjacentList[node]:
            return 1 + dfs(neighbor, adjacentList, visited)
    ans1 = 0 
    for n in arr:
        if not visited1[n]:
            ans1 += dfs(n, adjacentList1, visited1) - 1
    ans2 = 0
    for n in arr:
        if not visited2[n]:
            ans2 += dfs(n, adjacentList2, visited2) - 1
    return min(ans1, ans2)

print(lilysHomework([2,4,5,1,3])==3)
print(lilysHomework([3,1,4,2])==3)
print(lilysHomework([1,5,4,3,2])==2)
print(lilysHomework([3, 4, 2, 5, 1])==2)