A Developer Boy Sorts Out a Messy Line
Tags: javascript, algorithms, beginners
Published: 2019-12-09 03:46:53

---
title: A Developer Boy Sorts Out a Messy Line
published: true
description: I applied bubble sort for a HackerRank challenge
tags: #javascript, #algorithms, #beginners
cover_image: https://images.unsplash.com/photo-1471110235758-047f8825f69a?ixlib=rb-1.2.1&ixid=eyJhcHBfaWQiOjEyMDd9&auto=format&fit=crop&w=2550&q=80
---

*Header image: [Photo by Roman Arkhipov on Unsplash](https://unsplash.com/photos/wEFvY8mi1zc)*

### Preface
This post will cover the [New Year Chaos HackerRank challenge](https://www.hackerrank.com/challenges/new-year-chaos/problem) covering arrays. It will also apply the bubble sort algorithm, which I've talked about [previously here](https://dev.to/bebopvinh/a-developer-boy-and-his-bubble-sort-16gg).

*Note: Too lazy to read? Here are the goods on [PythonTutor](http://pythontutor.com/visualize.html#code=function%20minimumBribes%28q%29%20%7B%0A%20%20%20%20let%20k%20%3D%20q.length%0A%20%20%20%20let%20totalBribes%20%3D%200%0A%20%20%20%20let%20currentSwaps%0A%20%20%20%20let%20noSwap%0A%20%20%20%20while%20%28k%20%3E%200%29%20%7B%0A%20%20%20%20%20%20%20%20currentSwaps%20%3D%200%0A%20%20%20%20%20%20%20%20noSwap%20%3D%20true%0A%20%20%20%20%20%20%20%20for%20%28let%20i%20%3D%200%3B%20i%20%3C%20k%3B%20i%2B%2B%29%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20let%20j%20%3D%20i%20%2B%201%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20%28q%5Bi%5D%20%3E%20q%5Bj%5D%29%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20%28currentSwaps%20%3D%3D%202%29%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%22Too%20chaotic%22%29%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20noSwap%20%3D%20false%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20swapValues%28q,%20i,%20j%29%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B%2BcurrentSwaps%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B%2BtotalBribes%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%20else%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20currentSwaps%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20if%20%28noSwap%29%20break%0A%20%20%20%20%20%20%20%20k--%0A%20%20%20%20%7D%0A%20%20%20%20console.log%28totalBribes%29%0A%7D%0Afunction%20swapValues%28array,%20i,%20j%29%20%7B%0A%20%20%20%20%5Barray%5Bi%5D,%20array%5Bj%5D%5D%20%3D%20%5Barray%5Bj%5D,%20array%5Bi%5D%5D%0A%7D%0A%0AminimumBribes%28%5B2,%201,%205,%203,%204%5D%29&cumulative=false&curInstr=90&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=js&rawInputLstJSON=%5B%5D&textReferences=false)*

### 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.

```javascript
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":
```javascript
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

```javascript
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!