Breaking the Order | Coding Challenge & Analysis 1

JavaScript Coding Challenge: Breaking the Order

Given an array of numbers, find the last index before the ordering breaks. Indexing should begin with 0. If the numbers start by increasing, find last index where the numbers are increasing. If the numbers start by decreasing, find the last index where they are decreasing. If there is no break in the ordering, return -1. The array will contain at least 3 numbers and the first two will be increasing or decreasing.

For example, given the array [10, 9, 8, 7, 9, 10], the result should be 3, because the 7 at index 3 is the last index where the numbers are decreasing.

More examples:

[1, 2, 4, 7, 2, 3, 1] -> 3
[1, 2, 3, 4, 5] -> -1
[10, 11, 12, 12, 13] -> 2

If you want to give this challenge a try, stop reading here and go do that now. For my solution and analysis, continue on.

Solution

There are lots of ways to approach this challenge. My first thought was to use findIndex, since the goal is to find the index of a number based on something. However, it's not as straightforward as it first seems. Take the example array [10, 9, 8, 7, 9, 10]. If we're to look at each value individually, as findIndex allows, we don't actually have enough information to deduce the break in the ordering. After all, it's not a number by itself (e.g., 9) that indicates a break in the ordering; it's the fact that a 9 came after a 7. So really, we're looking between the numbers, or at the pairs of numbers. We could still use findIndex and use its second argument, each index of the array, and work things out looking at the current number and one ahead, but then we also have to make sure the index is in bounds and it's just not as elegant as dealing with pairs.

To get the right pairs, we can make a helper function called zip. This is something I use a lot in Haskell and it's a shame that JavaScript doesn't have such a useful function in its standard library. But it's easy to make. The goal of zip is to take in two arrays and "zip" them together, making an array of pairs, where each pair has an element from the first array and an element from the second array. For example, if we zip [1, 2, 3, 4] and [7, 8, 9, 10], we should get [ [1, 7], [2, 8], [3, 9], [4, 10] ]. Disregarding special cases where the arrays are different sizes, we can make zip using map.

const zip = (xs, ys) => xs.map((_, i) => [ xs[i], ys[i] ])

Now, what do we want to zip together? Well, from the array [10, 9, 8, 7, 9, 10], it would be nice to have the consecutive numbers as pairs [ [10, 9], [9, 8], [8, 7], [7, 9], [9, 10] ]. Then we can just get the index of the pair where the numbers stop decreasing and we're done! So, the two arrays we need to zip are: [10, 9, 8, 7, 9] and [9, 8, 7, 9, 10]. The first array is the original, without the last element. The second array is the original, without the first element.

const arr = [10, 9, 8, 7, 9, 10]
const init = arr.slice(0, -1)
const tail = arr.slice(1)

All that's left is to find the index where the ordering is broken. Although, we still need to know how to code where "the ordering is broken". We can't just assume the array will start off increasing or decreasing. The first thing that comes to mind is a conditional based on the start of the array. If the first pair is increasing, then find the index where the pairs stop increasing, and repeat the logic for decreasing. We can put this all together and include the tests.

const zip = (xs, ys) => xs.map((_, i) => [ xs[i], ys[i] ])

const breakingTheOrder = arr => {
  const init = arr.slice(0, -1)
  const tail = arr.slice(1)
  const pairs = zip(init, tail)
  return pairs.findIndex(([x, y]) => {
    const [firstX, firstY] = pairs[0]
    return firstX < firstY
      ? !(x < y)
      : !(x > y)
  })
}

console.log(breakingTheOrder([10, 9, 8, 7, 9, 10]) === 3)
console.log(breakingTheOrder([1, 2, 4, 7, 2, 3, 1]) === 3)
console.log(breakingTheOrder([1, 2, 3, 4, 5]) === -1)
console.log(breakingTheOrder([10, 11, 12, 12, 13]) === 2)

Abstracting the Ordering

Something that came to my mind after coming up with the solution is that the change in ordering doesn't have to be thought of as a condition; it can be a value itself. This also comes from Haskell, which has an Ordering type whose values are LT, EQ, and GT. With this idea in mind, what we really care about is finding the first pair whose ordering value is different from the first pair's ordering value. All we need is a compare function that returns an ordering value given two numbers.

const compare = (x, y) => (
  x < y ? 'LT'
    : x > y ? 'GT'
    : 'EQ'
)

We can now use this function in the final solution.

const zip = (xs, ys) => xs.map((_, i) => [ xs[i], ys[i] ])

const compare = (x, y) => (
  x < y ? 'LT'
    : x > y ? 'GT'
    : 'EQ'
)

const breakingTheOrder = arr => {
  const init = arr.slice(0, -1)
  const tail = arr.slice(1)
  const pairs = zip(init, tail)
  return pairs.findIndex(([x, y]) => {
    const [firstX, firstY] = pairs[0]
    return compare(x, y) !== compare(firstX, firstY)
  })
}

console.log(breakingTheOrder([10, 9, 8, 7, 9, 10]) === 3)
console.log(breakingTheOrder([1, 2, 4, 7, 2, 3, 1]) === 3)
console.log(breakingTheOrder([1, 2, 3, 4, 5]) === -1)
console.log(breakingTheOrder([10, 11, 12, 12, 13]) === 2)

Imperative Solution

For fun, I wanted to try the same solution idea using a more old-school imperative programming style. So, instead of zip and findIndex, we can use a for loop.

The first time I wrote this imperative solution, I had a mistake in it. Can you spot it?

const breakingTheOrder = arr => {
  for (let i = 0; i < arr.length; i++) {
    if (compare(arr[i], arr[i+1]) !== compare(arr[0], arr[1])) {
      return i
    }
  }
  return -1
}

console.log(breakingTheOrder([10, 9, 8, 7, 9, 10]) === 3) // -> true
console.log(breakingTheOrder([1, 2, 4, 7, 2, 3, 1]) === 3) // -> true
console.log(breakingTheOrder([1, 2, 3, 4, 5]) === -1) // -> false
console.log(breakingTheOrder([10, 11, 12, 12, 13]) === 2) // -> true

The mistake is in the indexing. In the last iteration of the loop, arr[i+1] is out of bounds (thus undefined). To correct this, the loop should stop one index earlier.

const breakingTheOrder = arr => {
  for (let i = 0; i < arr.length - 1; i++) {
    if (compare(arr[i], arr[i+1]) !== compare(arr[0], arr[1])) {
      return i
    }
  }
  return -1
}

console.log(breakingTheOrder([1, 2, 3, 4, 5]) === -1) // -> true

But Tim, you could have made the same mistake in the functional code! True, let's see if it plays out differently. Let's say I made the mistake of using the entire array as the first one.

const breakingTheOrder = arr => {
  const init = arr // should be arr.slice(0, -1)
  const tail = arr.slice(1)
  const pairs = zip(init, tail)
  return pairs.findIndex(([x, y]) => {
    const [firstX, firstY] = pairs[0]
    return compare(x, y) !== compare(firstX, firstY)
  })
}

console.log(breakingTheOrder([1, 2, 3, 4, 5]) === -1) // -> false

Now that the code fails in the same way, how would I discover this mistake and debug it? Well, I could easily print out the list of pairs to see if it looks right.

const breakingTheOrder = arr => {
  const init = arr
  const tail = arr.slice(1)
  const pairs = zip(init, tail)
  console.log('pairs:', pairs)
  return pairs.findIndex(([x, y]) => {
    const [firstX, firstY] = pairs[0]
    return compare(x, y) !== compare(firstX, firstY)
  })
}

console.log(breakingTheOrder([1, 2, 3, 4, 5]) === -1) // -> false
// pairs: [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ], [ 5, undefined ] ]

From here, I can easily tell the last pair shouldn't be there, so the arrays need to be the same length to fix it.

In contrast, how would I debug the imperative code?

const breakingTheOrder = arr => {
  for (let i = 0; i < arr.length; i++) { // should be: i < arr.length - 1
    if (compare(arr[i], arr[i+1]) !== compare(arr[0], arr[1])) {
      return i
    }
  }
  return -1
}

console.log(breakingTheOrder([1, 2, 3, 4, 5]) === -1) // -> false

For me, this code is much more difficult to debug. It's hard to decide what to print first: i, arr[i], or arr[i+1]. And then I have to sift through the many lines in the console because the printing is inside a loop.

Now, you may be wondering why the imperative code is shorter than the functional code. Make no mistake, this is not inherent to the paradigm; I simply decided to use more variables in the functional code and wrote the imperative version idiomatically. Here is a more similar comparison:

const zip = (xs, ys) => xs.map((_, i) => [ xs[i], ys[i] ])

const compare = (x, y) => (
  x < y ? 'LT'
    : x > y ? 'GT'
    : 'EQ'
)

const breakingTheOrderFunctional = arr => (
  zip(arr.slice(0, -1), arr.slice(1))
    .findIndex(([x, y]) => compare(x, y) !== compare(arr[0], arr[1]))
)

const breakingTheOrderImperative = arr => {
  for (let i = 0; i < arr.length - 1; i++) {
    if (compare(arr[i], arr[i+1]) !== compare(arr[0], arr[1])) {
      return i
    }
  }
  return -1
}

Final Thoughts

I mentioned Haskell a few times, because it always comes to mind when I'm solving coding challenges like this. When I first learned Haskell and started practicing with challenges on Codewars, it felt really different from any other language I had used–in fact it often felt like cheating. Haskell's built-in library is so well-equipped that you really feel handicapped when you go back to other languages. And this has to do with the power of functional programming, which comes from abstracting patterns and recognizing these patterns in the wild. Once you harness that ability, solving problems becomes really easy. You get to know which functions and techniques come up a lot and how to recognize the situations to use them. Like the concept of zipping a list together with its shifted self (I never would have thought of it before using Haskell!).

With all this talk about Haskell, it's only fair to show the equivalent Haskell solution.

Haskell Solution

import Data.List (findIndex)
import Data.Maybe (fromMaybe)

breakingTheOrder :: [Int] -> Int
breakingTheOrder lst =
  fromMaybe (-1)
  $ findIndex ( \(x, y) -> compare x y /= compare (lst !! 0) (lst !! 1) )
  $ zip (init lst) (tail lst)

main :: IO ()
main = do
  print $ breakingTheOrder [10, 9, 8, 7, 9, 10] == 3
  print $ breakingTheOrder [1, 2, 4, 7, 2, 3, 1] == 3
  print $ breakingTheOrder [1, 2, 3, 4, 5] == -1
  print $ breakingTheOrder [10, 11, 12, 12, 13] == 2

However, if this were really a problem to solve in a Haskell mindset, the problem should be tweaked a bit. Instead of returning -1 in the case where the ordering doesn't break, we can use a Maybe type of value. So, return an index number where the ordering breaks, or nothing. This is naturally what Haskell's findIndex function is built around; maybe finding an index. The new solution is even simpler:

import Data.List (findIndex)

breakingTheOrder :: [Int] -> Maybe Int
breakingTheOrder lst =
  findIndex ( \(x, y) -> compare x y /= compare (lst !! 0) (lst !! 1) )
  $ zip (init lst) (tail lst)

main :: IO ()
main = do
  print $ breakingTheOrder [10, 9, 8, 7, 9, 10] == Just 3
  print $ breakingTheOrder [1, 2, 4, 7, 2, 3, 1] == Just 3
  print $ breakingTheOrder [1, 2, 3, 4, 5] == Nothing
  print $ breakingTheOrder [10, 11, 12, 12, 13] == Just 2

Originally published at https://timjohns.ca.