The Fix34 Problem

The Fix34 problem is as follows: Return an array that contains exactly the numbers as the given array, but rearranged so that every 3 is immediately followed by a 4. Do not move the 3’s, but every other number can move. The array contains the same number of 3’s and 4’s, every 3 has a number after it that is not a 3, and a 3 appears in the array before any 4. It is straight-forward if using imperative paradigm with array points and stuff, but not so easy using recursion. I also wanted to do as much “functional programming” way as possible, which means no side-effects.

Here is my attempt of solving it “the hard way” as a mind exercise for myself. During the implementation I found that under certain conditions there is no way to keep the position of 3’s as you can see later.

The Solution

In the simplest case, we will either encounter a 3 first and before a 4. When that happens, we will swap the value right after the 3 with the 4. For example, [3, 1, 2, 4] will become [3, 4, 2, 1] once we processed the value 4.

There can also be 4’s appearing before 3’s. For example: [3, 1, 2, 4, 4, 3, 1] should become [3, 4, 2, 1, 1, 3, 4].

Then there can be multiple 3’s or 4’s that can appear in the sequence with the patching 4’s and 3’s appearing much later on. For example: [3, 1, 3, 1, 4, 4]. Under the imperative programming paradigm, we can keep track of the indexes of the 3’s and 4’s. With functional paradigm, since we don’t want side-effects, we can use some sort of state to track the unmatched values and pass the state along to the recursive calls.

Designing the State

It is not hard to see that the program when run has 3 possible states: 1. MoreThrees: Having one or more unbalanced 3’s and waiting for matching 4’s. For example, when it hits the first value in [3, 1, 2, …] it goes into MoreThrees. 2. MoreFours: Having one or more unbalanced 4’s and waiting for 3’s. For example, when it processed the second 4 in [3, 1, 2, 4, 4, …] it goes into MoreFours. 3. Balanced: Have processed matching 3’s and 4’s. The program starts with this stage.

The following code segment shows the data structure of the states:

trait Fix34State
sealed case class MoreThrees(staging: Seq[Int], stagingQ: Queue[Seq[Int]]) extends Fix34State
sealed case class MoreFours(staging: Seq[Int], stagingQ: Queue[Seq[Int]]) extends Fix34State
sealed case class Balanced() extends Fix34State

Besides the three states, we also want to pass the values that are already processed (i.e. their positions will no longer change) and the values yet to be processed along with the recursion calls.

The following code segment shows the data structure of the execution state:

case class State(processed: Seq[Int], state: Fix34State, remaining: Seq[Int])

With the above definitions, we can write the following function. It is important for it to be a tail-recursion to avoid stack overflow.

@tailrec
def fix34RecSwap(inState: State): State

Within the function, we can decompose the program behavior into the following four scenarios:

Terminating Behavior

The program terminates when it encounters a Nil list. The behavior is the most straight-forward case.

inState.remaining match {
    case Nil =>
    inState.state match {
        case Balanced() => inState
        case _ => throw new IllegalArgumentException("Number of 3s and number of 4s do not match")
    }

Balanced State Behavior

When in Balanced state, the program will stay in this state if the next value encountered is neither 3 nor 4, and switch to MoreThrees state or MoreFours state when it encounters a 3 or 4. If so, it will put the current value into the intermediate place (staging) instead of adding them to the processed values list.

val newState = inState.state match {
    case Balanced() =>
        if (head == 3) {
        State(
            processed = inState.processed,
            state = MoreThrees(Vector(head), Queue.empty),
            remaining = tail)
        } else if (head == 4) {
            State(
            processed = inState.processed,
            state = MoreFours(Vector(head), Queue.empty),
            remaining = tail)

        } else State(
        processed = inState.processed :+ head,
        state = Balanced(),
        remaining = tail
        )

MoreThrees State Behavior

When in MoreThrees state, we know there are already some values stored in the staging.

If the next value is neither 3 or 4, it simply adds the value to the staging.

If it encounters a 3, it means one more 4 is needed to match all the 3’s. The matching is assumed to be FIFO, so we can start a new segment of values starting with this 3, and put the old segment of values into the queue in staging. This implies the “degree” of unmatched 3’s has increased by 1. At the end of this processing, the program will remain in MoreThrees state.

If it encounters a value 4, it means a match has been found and the “degree” of unmatched 3’s should decrease by 1. At this point two possible things will happen:

1. All the unmatched 3’s are matched by 4’s, and the program goes back to “Balanced” stage. If so, the staging should become empty.
2. There are still unmatched 3’s, and the program remains in “MoreThrees” state.

In each of the two cases, we will expect that one segment of data in the staging will have the value behind the 3 swapped with the incoming 4 and the whole segment can be considered processed.

case MoreThrees(s, sq) =>
if (head == 3)
    State(
    processed = inState.processed,
    state = MoreThrees(Vector(head), sq :+ s),
    remaining = tail)
else if (head == 4) {
    if (sq.isEmpty) { // The last segment in staging, so this brings the state back to Normal
    val valueToAppend =
        if (s.size == 1) Vector(s.head, head)
        else Vector(s.head, head) :++ s.tail.tail :+ s.tail.head
    State(
        processed = inState.processed :++ valueToAppend,
        state = Balanced(),
        remaining = tail)
    }
    else { // Take first item in the Q and match it with the 4
    val (segment, remainingQ) = sq.dequeue
    assert(segment.size>1, "The segment being matched by a 4 has less than 2 elements. Actual:" + segment.size)
    assert(segment.head == 3, "The segment being matched by a 4 does not start with 3. Actual:" + segment.head)
    State(
        processed = inState.processed :++
        Vector(segment.head, head) :++ segment.tail.tail,
        state = MoreThrees(s :+ segment.tail.head, remainingQ),
        remaining = tail)
    }
}
else State(
    processed = inState.processed,
    state = MoreThrees(s :+ head, sq),
    remaining = tail)

MoreFours State Behavior

The behavior of the MoreFours state is similar to that of MoreThrees state. The program will keep track of unmatched 4’s and data after that until a matching 3 appears, and when that happens it will swap the value behind 3 with the accumulated 4, and move a segment of values in FIFO order. It will add the 3 and the swapped 4 after it into staging and wait for their turn to be moved to processed list.

case MoreFours(s, sq) =>
if (head == 4)
    State(
    processed = inState.processed,
    state = MoreFours(Vector(head), sq :+ s),
    remaining = tail)
else if (head == 3) {
    assert(tail.size > 1)
    if (sq.isEmpty) { // The last segment in staging, so this brings the state back to Normal
    State(
        processed = inState.processed :+
        tail.head :++ s.tail :+ head :+ s.head,
        state = Balanced(),
        remaining = tail.tail)
    }
    else { // Take first item in the Q and match it with the 4
    val (segment, remainingQ) = sq.dequeue
    assert(segment.head == 4, "The segment being matched by a 3 does not start with 4. Actual:" + segment.head)
    State(
        processed = inState.processed :+
        tail.head :++ s.tail,
        state = MoreFours(s :+ head :+ segment.head, remainingQ),
        remaining = tail.tail)
    }
} else State(
    processed = inState.processed,
    state = MoreFours(s :+ head, sq),
    remaining = tail
)

Speical Case - Valid but Invalid

The objective of the constraints set in the problem description is to make sure the positions of 3’s won’t change after the logic. However it never states a 4 cannot be immediately after a 3, and when that happens and the 4 is at a different level of nesting from the 3 the position of the 3 will still be shifted. For example, given [3, 4, 4, 3, 4, 3, 2], if positions of 3’s can change, we should get [3, 4, 3, 4, 3, 4, 2]. However with this implementation, the input is considered invalid.

  "A Fix34 (Swap) function" when {
    "given an array where a 4 is immediately after a 3 but they are at different levels of nesting" should {
      "fail with IllegalArgumentException" in {
        assertThrows[IllegalArgumentException] {
          Fix34.fix34Swap(Seq(3, 4, 4, 3, 4, 3, 2))
        }
      }
    }

Source Code

Code

Test Code

• << Let’s Play! - My Play Framework Learning Journey (10) - Using Jackson Directly for Json Processing
• >> What I Learned from the Migration of this Website to Azure App Service