We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Lily's Homework
  5. Discussions

Lily's Homework

Sort by

recency

|

268 Discussions

|

  • djiloumnov
     + 0 comments

    Solution in JS: function getNumberSwaps(arr, arrMap, sortedArr) { let numberOfSwaps = 0; for (let i = 0; i < sortedArr.length; i++) { if (sortedArr[i] !== arr[i]) { const tmp = arr[i]; const idxSource = arrMap[sortedArr[i]];

            arr[i] = arr[idxSource];
        arr[idxSource] = tmp;

        arrMap[tmp] = idxSource;
        arrMap[sortedArr[i]] = i;

        numberOfSwaps++;
    }
}

return numberOfSwaps;

    }

    function lilysHomework(arr) { const ascArr = arr.toSorted((a, b) => a - b); const descArr = arr.toSorted((a, b) => b - a);

    const arrMap = {};
arr.forEach((num, idx) => {
    arrMap[num] = idx
});
return Math.min(getNumberSwaps([...arr], { ...arrMap }, ascArr), getNumberSwaps(arr, arrMap, descArr));

    }

    `

  • wifivop476
     + 0 comments

    It's possible that a swap could move 2 numbers from where they start, to where they need to be, in a single swap with capzcut. Does this method take that into account? Simply comparing a sorted array to the original array, does not tell how many swaps it would take to get to the sorted array.

  • zettix1
     + 0 comments

    Pedantic.

    class Result {

    /*
     * Complete the 'lilysHomework' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static int countSwaps(List<List<Integer>> indexToValueList) {
        int totalSwaps = 0;        
        Map<Integer, Integer>  indexToIndex = new HashMap<>();
        Set<Integer> startPositions = new HashSet<>();
        for (int i = 0; i <  indexToValueList.size(); i++) {
            indexToIndex.put(i,indexToValueList.get(i).get(0) );
        }
        startPositions.addAll(indexToIndex.values());
        int idx = 0;
        while (! startPositions.isEmpty()) {
            int currentSwaps = 0;
            int startPos = idx;
            int nextPos = indexToIndex.get(idx);
            startPositions.remove(startPos);
            int curpos = startPos;
            while (nextPos != startPos) {
                currentSwaps++;
                startPositions.remove(nextPos);
                nextPos = indexToIndex.get(nextPos);
                curpos = nextPos;

            }
            while (! startPositions.contains(idx)) {
                idx++;
                if (idx >= indexToIndex.size()) {
                    break;
                }
            }
            totalSwaps += currentSwaps;
        }
        return totalSwaps;
    }
    
    public static int lilysHomework(List<Integer> arr) {
         
        class SortByValueUp implements Comparator<List<Integer>>  {
        
        @Override
        public int compare(List<Integer> a, List<Integer> b) {
            int va = a.get(1);
            int vb = b.get(1);
            if (va > vb) {
                return 1;
            }
            if (va < vb) {
                return -1;
            }
            return 0;
          }
      }
      
      class SortByValueDown implements Comparator<List<Integer>> {
          
        @Override
        public int compare(List<Integer> a, List<Integer> b) {
            int va = a.get(1);
            int vb = b.get(1);
            if (va < vb) {
                return 1;
            }
            if (va > vb) {
                return -1;
            }
            return 0;  
          }
      }
      
    // Write your code here
        // minimum is sorted.  How many swaps to sort?
        // A sort is a permutation.  After sorting, count number
        // of things not in place.  All others must swap, and
        // swaps can be a cycle, e.g.:  a<->b, b<->c, c<->d, d<->a
        // or a mirror: a<->b.  4 swaps fix 4 in a ring, mirror fixes 2.
        // Hence we count the loops lengths, e.g. swaps.
        List<List<Integer> > indexToValueList1 = new ArrayList<>();
        List<List<Integer> > indexToValueList2 = new ArrayList<>();
        for (int i = 0; i < arr.size(); i++) {
            List<Integer> entry = new ArrayList<>();
            entry.add(i);
            entry.add(arr.get(i));
            indexToValueList1.add(entry);
            indexToValueList2.add(entry);
        }
        Collections.sort(indexToValueList1, new SortByValueUp());
        Collections.sort(indexToValueList2, new SortByValueDown());
        int s1 = countSwaps(indexToValueList1);
        int s2 = countSwaps(indexToValueList2);
        if (s1 < s2) {
            return s1;
        }
        return s2;
    }
}

  • anthonyabunassar
     + 2 comments

    In Python (I tried the simplest thing, and it worked):

    def lily_internal(a: list[int], reverse: bool=True):
    targets = {n: i for i, n in enumerate(sorted(a, reverse=reverse))}
    swaps = 0
    for i, n in enumerate(a):
        while i != targets[n]:
            # Swap the current value into the correct place.
            a[targets[n]], a[i] = n, a[targets[n]]
            swaps += 1
            n = a[i]
    return swaps

def lilysHomework(a: list[int]):
    # lily_internal() is destructive, so send a copy the first time.
    return min(lily_internal(list(a), False), lily_internal(a, True))

  • pickled_onion
     + 0 comments

    Js solution, hope this helps! 

    function countSwap(arr, sortedArr) {
    let swapCount = 0
    const visited = []
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === sortedArr[i][0]) {
            visited[i] = true
            continue
        }
        let pCount = 0; // permutations
        let j = i;
        while(!visited[j]) {
            pCount ++
            visited[j] = true
            j = sortedArr[j][1]
        }
        if (pCount > 1) swapCount += pCount - 1  // this math based on Permutation Cycle Decomposition
    }
    
    return swapCount
}
function lilysHomework(arr) {
    // Write your code here
    const pArr = arr.map((e, i) => [e, i]) // add position to arr
    const aSorted = mergeSort(pArr, true) // ascending sorting, you can choose any sort algo
    const dSorted = mergeSort(pArr, false) // descending sorting
    
    let aSwapCount = countSwap(arr, aSorted)
    let dSwapCount = countSwap(arr, dSorted)
    
    return Math.min(aSwapCount, dSwapCount)
}