Discussion on Lily's Homework Challenge

Sort by

recency

|

269 Discussions

|

3 weeks ago+ 0 comments

Sort the Array Track Cycles Count Swaps = (cycle length - 1) I run the test array [3,4,2,5,1] ->output 4, but the expected answer is 2,why?

def lilysHomework(arr): # Write your code here # Create a list of tuples where each tuple is (element, original_index) n = len(arr) arr_with_indices = [(arr[i], i) for i in range(n)]

# Sort the array by the element values
arr_with_indices.sort(key=lambda x: x[0])

# To track visited elements
visited = [False] * n
swaps = 0

for i in range(n):
    # If the element is already visited or already in the correct position, skip it
    if visited[i] or arr_with_indices[i][1] == i:
        continue

    # Start a new cycle
    cycle_size = 0
    j = i
    while not visited[j]:
        visited[j] = True
        j = arr_with_indices[j][1]  # Move to the next element in the cycle
        cycle_size += 1

    # If there is a cycle of size `k`, it takes `k - 1` swaps to sort the cycle
    if cycle_size > 1:
        swaps += cycle_size - 1

return swaps

1 month ago+ 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));

}

2 months ago+ 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.

3 months ago+ 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;
    }
}

3 months ago+ 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))

Sort by

|

269 Discussions

|

Cookie support is required to access HackerRank