A Better Frog Crossing Algorithm

Question

I am solving the following problem from Codility:

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river. You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes. 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.

I used the following solution but only got a score of 81:

The code is in C#.

using System;
using System.Collections.Generic;

class Solution {
    public int solution(int X, int[] A) {
        bool[] tiles = new bool[X];

        for (int i = 0; i < A.Length; i++)
        {
            tiles[A[i] - 1] = true;

            bool complete = true;

            for (int j = 0; j < tiles.Length; j++)
            {
                if (!tiles[j])
                {
                    complete = false;
                    break;
                }
            }

            if (complete)
                return i;
        }

        return -1;
    }
}

My algorithm runs at O(NX). What could be a better algorithm that will only require O(N)?

Answer 1

Change your code to something like this:

public int solution(int X, int[] A) 
{
    bool[] tiles = new bool[X];
    int todo = X;

    for (int i = 0; i < A.Length; i++)
    {
        int internalIndex = A[i] - 1;
        if (internalIndex < X && !tiles[internalIndex])
        {
            todo--;
            tiles[internalIndex] = true;
        }

        if (todo == 0)
            return i;
    }

    return -1;
}

This algorithm only requires O(A.length) time, since it always keeps track of how many "holes" we still have to fill with leaves.

How is this done here?

todo is the number of leaves still required to build the "bridge" of leaves. Whenever a leaf falls down, we first check whether there not already is a leaf at the position it falls down. If not, we decrement todo, fill the hole and go on. As soon as todo reaches 0, the entire river is covered ;)

Answer 2

That is my variant base on HashSet. The result is here

public int solution(int X, int[] A)
{
  HashSet<int> hash = new HashSet<int>();

  for(int i=0;i<A.Length;i++)
  {
    if(A[i]<=X)
      {
          hash.Add(A[i]);

           if(hash.Count == X)
             return i;
      }
  }
  return -1;
}

Answer 3

whilst i agree you get a score of 100 it does not satisfy all test cases

for the sample data of 1, 3, 1, 4, 2, 3, 5, 4

if you try and find 3 it should return 5 but the answer given throws an exception

a corrected version is, as the leaf failing at position 2 is fulfilled after the forth minute

    public int solution(int X, int[] A)
    {
                int steps = -1;
        bool[] tiles = new bool[X];

        int todo = X;
        for (int i = 0; i < A.Length; i++)
        {
            steps += 1;
            int internalIndex = A[i] - 1;
            if (internalIndex < tiles.Length)
            {
                if (!tiles[internalIndex])
                {

                    todo--;

                    tiles[internalIndex] = true;

                }
            }
            if (todo == 0)

                return steps;
        }
        return -1;
    }

Answer 4

This gets me 100/100

public int solution(int X, int[] A)
{
    int z = -1;

    long combA = ((long) X)*(((long) X) + 1)/2;
    long sumA = 0;

    int[] countA = new int[X];

    for (int i = 0; i < A.Length; i++)
    {
        countA[A[i] - 1] += 1;

        if (countA[A[i] - 1] > 1)
        {
            countA[A[i] - 1] = 1;
        }
        else
        {
            sumA += A[i];
        }


        if (sumA == combA)
        {
            z = i;
            break;
        }

    }

    return z;
}

Answer 5

Here is an easy C++ solution:

int solution(int X, vector<int> &A)
{
  vector<bool> removed( X );

  for( size_t i = 0; i < A.size(); i++ )
  {
    if( removed[ A[i] - 1 ] == false )
    {
      removed[ A[i] - 1 ] = true; 
      X--;

      if(X == 0)
      {
        return i;
      } 
    }
  }

  return -1; 
}

Answer 6

100% Score : PHP code for FrogRiverOne : Ajeet Singh

function solution($X, $A) {
    for ($i = 0; $i < count($A); $i++){        
        if (!isset($position_achieved[$A[$i]])){
            $X--;   // reduce X by one position is achieved
            $position_achieved[$A[$i]] = true;
        }
        if (!$X){
            return $i;
        }
    }
    return -1;    
}

Answer 7

Here's a Python solution I came up with (100/100 on Codility):

def solution(X, A):
    N = len(A)
    count = [0] * (X+1)
    steps = 0
    for k in xrange(N):
        if not count[A[k]]:
            count[A[k]] = 1
            steps += 1
            if steps == X:
                return k
    return -1

Answer 8

Ruby solution (100/100 on Codility):

def solution(x, a)

  check_array = (0..a.length).to_a
  check_array.each { |i| check_array[i]=0 }

  a.each_with_index do |element, i|

      if (check_array[element]==0)
          check_array[element]=1
          x -= 1
      end

      return i if (x==0)
  end

  return -1

end

Answer 9

I happened upon this exercise a bit late. I see a lot of languages covered except C90. Like many I did find a solution by creating a secondary array. I used typical calloc and then free. My first solution is similar to others posted:

int solution(int X, int A[], int N)
{
    int *n = calloc(X, sizeof(*A));
    int index;

    for (index = 0; index < N; index++) {
        if (n[A[index] - 1] == 0) {
            n[A[index] - 1] = 1;
            if (--X == 0) {
                free(n);
                return index;
            }
        }
    }

    free(n);
    return -1;
}

I realized that I could get away without the second array altogether since we are dealing with signed integers and the codility site also says Elements of input arrays can be modified . It also says each element of array A is an integer within the range [1..X] . Since the original input array A will always have positive numbers I can use that to my advantage. I can use the sign bit of the ints in the array int A[] to denote whether I have seen a particular leaf position already (or not). The new version of the code uses the function abs to deal with the absolute value in each array element for indexing purposes. I set the sign bit to indicate I have visited a particular leaf position already, and I check the actual value at an index without using abs to know if I have visited the position already. My final solution looked like:

int solution(int X, int A[], int N)
{

    int index;
    int leaftimeidx;

    for (index = 0; index < N; index++) {
        leaftimeidx = abs(A[index]) - 1;

        if (A[leaftimeidx] > 0) {
            A[leaftimeidx] *= -1;

            if (--X == 0)
                return index;
        }
    }
    return -1;
}

Both variants of my solution passed all the tests.

Answer 10

here is my solution in C99, probably not the most elegant. but i hope is readable and understandable. here is the link to my test. https://codility.com/demo/results/demoNGRG5B-GMR/

int solution(int X, int A[], int N) {

    if (X <= 1) return 0; //if we only need to go 1 step we are already there
    if (N == 0) return -1;//if we don't have timing we can't predict 

    int B[X+1];

    for (int i=0; i <= X; i++) {
        B[i] = -1; //i set default value to -1 so i can see later if we missed a step. 
    }

    for (int i=0; i < N; i++) {
        if (A[i] <= X && (B[A[i]] == -1 || B[A[i]] > i)) B[A[i]] = i; //prepare my second array here with timing data 
    }

    int max_min = 0; //store the highest timing later on.

    for (int i=1; i <= X; i++) {
        if (B[i] == -1) return -1; //if we have any elements with -1 then we didn't cross the river
        if (max_min < B[i]) max_min = B[i]; //keep setting the highest timing seen the steps.
    }

    return max_min;
}

Answer 11

100% with C#

 using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Threading.Tasks;
 using System.Collections;

  public int solution(int X, int[] A)
{
    // write your code in C# 5.0 with .NET 4.5 (Mono)

    int N = A.Length;
    int step = 0;
    List<int> k = new List<int>();


    for (int i = 0; i < X; i++)
    {
        k.Add(0);
    }

    //Inserts an element into the ArrayList at the specified index.
    for (int i = 0; i < N; i++)
    {
        int diff = A[i] - 1;

        k[diff] = A[i];

        if (i >= X-1 && (k.Contains(0) == false))
        {
           return i;

        }

    }


    return -1;

}

Answer 12

Below is another approach using Dictionary:

public int solution(int X, int[] A) {
        int result = -1;
         Dictionary<int, int> jumps = new Dictionary<int, int>();
            int res =  (X*(X+1))/2;
            int sum = 0;

            for (int i = 0; i < A.Length; i++)
            {
                if (!jumps.ContainsKey(A[i]))
                {
                    sum = sum + A[i];
                    jumps.Add(A[i],i);
                    if (sum == res)
                    {
                        result = i;
                        break;
                    }
                }
            }
            return result;
    }

The code above is creating the sum of integers up to X i.e if X=5 then we count (1+2+3+4+5) using Gauss formula (X*(X+1))/2, this will allow us to know later if total hops are added or happened. This value will be compared with the sum of distinct steps been added to the dictionary. As per the description "The frog can cross only when leaves appear at every position across the river from 1 to X. " I tried using the list instead of dic but it failed on some of the performance tests, and here comes the power of Dictionay object when we do lookup via key.

Answer 13

This runs in O(N) and returns 100%:

    public int solution(int X, int[] A) {
            Hashtable spaces = new Hashtable();
            int counter = 0;
            foreach(int i in A)
            {
                //Don't insert duplicate keys OR 
                //keys greater than requested path length
                if (!spaces.ContainsKey(i) && i <= X)
                    spaces.Add(i, i);

                //If Hashtable contents count = requested number of leaves,
                //then we're done
                if (spaces.Count == X)
                    return (counter);

                counter++;
            }

            return -1;
    }

Answer 14

This was my 100% solution with the time complexity of O(N). Remember that you are allowed to use Generics and Linq in those assignments.

public int solution(int X, int[] A)
{
    SortedSet<int> leaves = new SortedSet<int>();
    for (int i = 0; i < A.Length; i++)
    {
        leaves.Add(A[i]);
        if (leaves.Count() == X) return i;
    }
    return -1;
}

Answer 15

Here is the solution in Python3

def solution(target, data_list):
    check_set = set()
    for i, value in enumerate(data_list):
        if value <= target:
             check_set.add(target)
        if len(check_set) == data_list:
            return i

    return -1

Answer 16

    public static int solution(int X, int[] A)
    {
        HashSet<int> hash = new HashSet<int>();

        for (int i = 0; i < A.Length; i++)
        {
            if (A[i] <= X)
            {
                hash.Add(A[i]);

                if (hash.Count == X)
                    return i;
            }
        }
        return -1;
    }