def frog_jump(x, arr):
  mem = (1 << x) - 1
  for i, j in enumerate(arr):
    if j > x:
      continue

    bit = 1 << (j - 1)
    if mem & bit != 0:
      mem -= bit

    if mem == 0:
      return i
  return -1

#Challenge

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

The function should return 6, because In second 6 a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

#Solution

The challenge here was finding an efficient way to represent the leaves that've already dropped, and when all the leaves we need have dropped. You could store them in an array of booleans and use the index to map leaf positions. The approach I landed on was using the most efficient storage structure available, individual bits.

Now when most people see bit manipulations in an algorithm, they have a tendency to close their eyes and look away in horror (ノдヽ). Don't! there's nothing too complicated about the general algorithm.

First we create a counter, mem, which stores the leaves that we need to drop and whether it's dropped or not. 1 << x is the same as \(2^x\) which is equivalent to \(1\) followed by \(5\) zeroes (I.E. \(100000\)). Subtracting one from this is a common way to toggle all the bits before it to the on state (I.E. \(011111\)). So mem has five bits each mapping to some leaf, with \(1\) meaning this leaf hasn't dropped yet and \(0\) meaning this leaf has dropped.

In the loop we convert each leaf that's dropped to the bit flag that will change the associated bit in mem. eg.

1 << 0: 00001
1 << 1: 00010
1 << 2: 00100
1 << 3: 01000
1 << 4: 10000

Then we use a simple AND gate to check whether that leaf has already fallen or not.

    11111
AND 00100
    -----
    00100 != 0

If mem hasn't seen the leaf drop before, we subtract this bit flag from mem causing it's value in the binary representation to become 0.

    11111
    00100
SUB -----
    11011 != 0

Once all the leaves have dropped, mem will be 0 and we can exit the algorithm. The original problem asked for the second at which all the leaves the frog needs to reach X will have dropped, with the array indices representing the leaves. So we return the current loop index.

#Analysis

The part of this solution that has the most apparent performance benefit is how we determine the terminating condition. A simple zero check is all we need to know whether all the leaves we need have dropped or not. That's the benefit of storing problem states in individual bits. It may seem difficult to know when a compact representation like binary makes sense, but the runtime gains are immense. See unique-number. Therefore it's worth learning how to use them, even if you'll rarely get the chance to apply them.

Our algorithm runs in linear time because bitwise operations run in constant time. Operations like AND gating a number, shifting bits around with <<, commonly have low level opcodes in your processor. This lets you use them with generally no performance cost.