New Year Chaos

Minimum Bribes in Go

Problem Statement

It is New Year’s Day and People are in line for the Wonderland Roller Coaster Ride. Each person holds a sticker which indicates their initial position at the queue from 1to n. Any person can bribe the person directly in front of them to swap positions but they still holds the original sticker.

1. one person can bribe at most two others
2. if anyone has bribed most than two people, the queue is too chaotic. And we no longer care about anything.

Find the minimum number of bribes that took placed to get the queue at such as current state.

Considerations

Let’s find the details that matters for our algorithm to solve. If all the people were in the line wearing one sticker relate to their initial position. We can safely assume that their initial position corresponds to a sorted collection.

Sorted slice (People at their initial position)

Then each person started to bribes to the person directly in front of them in order to swap positions.

Bribed slice (Unsorted slice)

So we are in charged of finding the minimum numbers of bribes that happened to our initial slice to be at unsorted state.

This problem reminds of the Larry’s slice problem but not quite. I tried the algorithm but the swapping technique neither the way to calculate the number of inversions were right for this problem to be solved.

Remember our algorithm has to calculated the minimum numbers of swaps that occur in the Slice to be unsorted.

The algorithm

1. Initialize the number of bribes to 0.
2. Iterate over the slice.
3. If the current element is less than the previous element, then there is an inversion.
4. Count the number of elements that are greater than the current element.
5. If the number of inversions is greater than 2, then the Slice is too chaotic and we return.
6. Otherwise, swap the current element with the first element that is greater than it.
7. Increment the number of bribes by the number of inversions.
8. Repeat steps 2–7 until the array is sorted.

Minimum Bribes Go

In line 41 minimumBribes is using the sort.IsSorted() function to check if the array is sorted. This function takes an array as input and returns true if the array is sorted in ascending order, and false otherwise. isSorted is receiving a type that implements the sort.Interface . That type enables to sort the Slice of int32 in ascending order.

Impementing de sort.Interface

The function swaping() uses the copy() function to copy elements from one slice to another. This function takes three arguments: the destination slice, the source slice, and the number of elements to copy. The reason behind using copy() instead of append() here is that it can lead to many unnecessary allocations.

Swapping function

Resources

Larry’s array

sort

How to Concatenate Two or More Slices in Go

How to use the copy function

New Year Chaos | HackerRank

I asked Google Bard to exaplin my code.