Frog crossover algorithm

Question

I solve the following problem from Codility:

The little frog wants to get to the other side of the river. Currently, the frog is in position 0 and wants to get into position X. The leaves fall from a tree to the surface of the river. You are given a non-empty zero index A, consisting of N integers representing falling leaves. A [K] represents the position in which 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. A frog can cross only when leaves appear in each position across the river from 1 to X.

I used the following solution, but only got 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 works in O (NX). What could be the best algorithm that only requires 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 (!tiles[internalIndex]) { todo--; tiles[internalIndex] = true; } if (todo == 0) return i; } return -1; } 

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

How is this done here?

todo - the number of leaves still needed to create a bridge of leaves. Whenever a leaf falls, we first check to see if there are more leaf in the position in which it falls. If not, we reduce todo , fill the hole and continue. As soon as todo reaches 0 , the whole river is covered;)

Answer 2

while I agree that you get 100 points, it does not satisfy all test cases

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

if you try to find 3, it should return 5, but the answer gives an exception

There is a corrected version, since a sheet that does not work in position 2 is executed after the fourth 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 3

It 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 4

Here is a simple 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 5

100% Rating: 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 6

This is my variant base on HashSet. Result 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 7

Here's the Python solution I came across (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

It happened a little later. I see many languages ​​besides the C90 . Like many, I found a solution by creating a secondary array. I used a 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 leave without a second array at all, since we are dealing with significant integers, and the codility site also says Elements of input arrays can be modified . He 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 this to my advantage. I can use the signed int bit in the int A[] array to indicate that I have already seen the specific position of the sheet (or not). The new version of the code uses the abs function to process the absolute value in each element of the array for indexing purposes. I set the sign bit to indicate that I have already visited a specific position of the sheet, and I check the actual value by index without using abs to find out if I have already visited the position. My final decision looked like this:

 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 versions of my solution passed all the tests.

Answer 10

here is my solution in the C99, perhaps not the most elegant. but I hope this is clear 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% 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

The following is a different approach using a 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 creates the sum of the integers up to X, i.e. if X = 5, then we calculate (1 + 2 + 3 + 4 + 5) using the Gaussian formula (X * (X + 1)) / 2, this will let us know later if full jumps are added or occur. This value will be compared with the sum of the various steps that have been added to the dictionary. According to the description, “A frog can cross only when leaves appear in each position across the river from 1 to X.” I tried to use this list instead of dic, but it did not work on some performance tests, and here the Dictionay object's ability arises when searching through the key.