Lilys Homework with duplicate elements

gistfile1.txt

function lilysHomework(arr: number[]): number {
    //array is beautiful if and only if it is sorted - ascending or descending
    const ascArr = arr.slice().sort((a,b) => a-b);
    const ascSwaps = minSwapsTo(arr, ascArr);
    const dscArr = arr.slice().sort((a,b) => b-a);
    const dscSwaps = minSwapsTo(arr, dscArr);   
    const swapsRequired = Math.min(ascSwaps, dscSwaps);

    return swapsRequired;
}

function minSwapsTo(arr: number[], targetArr: number[]): number {
    const targetPositions:Map<number,number[]> = new Map();
    for (let ix = 0; ix < targetArr.length; ix++) {
        const locs:number[] = targetPositions.get(targetArr[ix]) || [];
        locs.push(ix);
        targetPositions.set(targetArr[ix], locs);
    }
    
    //find the maximum number of cycles of swaps we can find in getting to target
    let checkPos = 0;
    let cycleCount = 0;
    const donePoses:Set<number> = new Set();
    while (checkPos < arr.length) {
        const cycle: number[] = findShortestCycle(arr, targetPositions, [checkPos]);
        cycleCount++;
        
        //remove positions found in cycle
        for (let ix = 0; ix < cycle.length-1; ix++) {
            const pos = cycle[ix];
            const elem = arr[pos];
            const nextPos = cycle[ix+1];
            
            donePoses.add(pos);
            
            const targetPoses = targetPositions.get(elem);
            targetPositions.set(elem, targetPoses.filter(
                (v) => v !== nextPos
            ));
        }
        
        do {
            checkPos++;
        } while (donePoses.has(checkPos));
    }
    
    return arr.length - cycleCount;
        //minimum number of swaps to reach target positions is reduced by 1 
        // for each cycle of swaps we can perform while reaching target, where 
        // cycle of swaps puts each element into place, and then leaves last 
        // element in correct place already
}

function findShortestCycle(
    arr: number[], 
    targetPositions:Map<number,number[]>, //map of orig element to target positions
    swapSeq: number[] //list of positions followed so far
    ) : number[] | null //returns list of positions in cycle or null if cycle not found starting with this swap sequence
{
    let useLoop = false;
    let shortestSeq:number[] = null;
    do
    {
        useLoop = false;
        
        const startingPos = swapSeq[0];
        const fromPos = swapSeq[swapSeq.length-1];
        const elem = arr[fromPos];
        
        if (swapSeq.length > 1 && fromPos === startingPos) {
            return swapSeq; //reached end of cycle
        }
        
        for (let ix = 1; ix < swapSeq.length-1; ix++) {
            const prevPos = swapSeq[ix];
            if (elem === arr[prevPos]) {
                return null;
                //a cycle returning to previous element other than first cannot be shortest
            }       
        }
            
        const toPoses = targetPositions.get(elem);
        if (toPoses.length == 1)
        {
            //fake recurse as there is only one option and no need to backtrack
            useLoop = true
            const toPos = toPoses[0];
            swapSeq.push(toPos);
        }
        else {
            //properly recurse as we may need to backtrack
            
            const posSeqs:Array<number[]> = [];
            for (const toPos of toPoses) {
                const testSeq = swapSeq.slice();
                testSeq.push(toPos);
                const resultSeq = findShortestCycle(
                  arr,
                  targetPositions,
                  testSeq
                );
                if (resultSeq){
                    posSeqs.push(resultSeq);
                    
                    if (resultSeq.length === swapSeq.length + 1) {
                        break;
                        //can stop looking for more options as no sequence could be shorter with this start
                    }
                }
            }
            
            let shortestLength = Number.MAX_VALUE;
            for (const posSeq of posSeqs) {
                if (posSeq.length < shortestLength) {
                    shortestLength = posSeq.length;
                    shortestSeq = posSeq;
                }
            }
        }
    } while (useLoop);
    
    return shortestSeq;
}