A Developer Boy Sorts Out a Messy Line

Header image: Photo by Roman Arkhipov on Unsplash

Preface

This post will cover the New Year Chaos HackerRank challenge covering arrays. It will also apply the bubble sort algorithm, which I've talked about previously here.

Note: Too lazy to read? Here are the goods on PythonTutor

The Problem

People are waiting in line, each individual is represented by an integer at an index. If everyone is honest, each individual would be at the index that is 1 less than their value i.e. first person is at 0, second at 1, etc...

If the line gets messy, and say person 7 is at index 0, and 4 is at index 6, we need to figure out how many "swaps" need to happen minimally to restore order.

Obviously, we can't just look at a number and place them into a new array at an index that is one less of the value. The problem is asking for the amount of swaps, not a sorted array.

The Caveat

If a person needs to swap more than twice, the line is declared "Too chaotic". This will be our secondary break mechanism.

The Core

Bubble sort at the core, missing ways to keep tracking of total amount of bribes and if an element has been swapped more than twice or not.

function minimumBribes(q) {
    //add variables to keep track of bribes
    while (k > 0) {
        let noSwap = true
        for (let i = 0; i < k; i++) {
            //add ways to keep track of how many times an element is swapped
            //reset this count if no swap happens when moving on to the next 
            element
            let j = i + 1
            if (q[i] > q[j]) {
                noSwap = false
                swapValues(q, i, j)
            }
        }
        if (noSwap) break
        k--
    }
    //return the total swaps here.
}

function swapValues(array, i, j) {
    [array[i], array[j]] = [array[j], array[i]]
}

Now with the added counters and logic to break if things are "Too chaotic":

function minimumBribes(q) {
    let k = q.length
    let totalBribes = 0
    //currentSwaps will keep track of how many times an element has been swapped
    let currentSwaps
    //noSwap is the standard flag to break the loop if array is already sorted
    let noSwap
    while (k > 0) {
        //assumes initial values
        currentSwaps = 0
        noSwap = true
        for (let i = 0; i < k; i++) {
            let j = i + 1
            if (q[i] > q[j]) {
                /*if an element at `i` is already swapped twice, we know this 
                crazy line is "Too chaotic". Break out and save our sanity. */
                if (currentSwaps == 2) {
                    console.log("Too chaotic")
                    return
                }
                /* if that's not the case, we swap and increment both counters
                 by 1, also set the noSwap flag to false,
                 so next iteration can happen to check if array is sorted */
                noSwap = false
                swapValues(q, i, j)
                ++currentSwaps
                ++totalBribes
            //if no swap happens, we reset currentSwaps for the next new element
            } else {
                currentSwaps = 0
            }
        }
        if (noSwap) break
        k--
    }
    console.log(totalBribes)
}
function swapValues(array, i, j) {
    [array[i], array[j]] = [array[j], array[i]]
}

Hope this makes sense. Let me know if I screw up somewhere, happy to revise.

BONUS: First attempt at the problem

function minimumBribes(q) {
    let bribes = 0
    for (let i = 0; i < q.length; i++) {
        //if the element at index i is greater than it's current index + 3, we 
        //know it'll be "Too chaotic" to fix
        if (q[i] > i + 3) {
            console.log("Too chaotic")
            return
        //else, add to bribes the difference between the the current element's 
        value and the next index value (i.e. element 7 at index 3)
        } else if (q[i] > i + 1) {
            bribes += q[i] - (i + 1)
        //sometimes, the current element is is smaller than it's index (i.e. 
        element 4 at index 6)
        } else if (q[i] > q[i + 1]) {
            bribes++
        }
    }
    return console.log(bribes)
}

This passed the initial 3 test cases, but failed all the others and gave me a big headache!