Programming Challenge #6

[oaktree]

Here’s another fun Programming Challenge: Service Lane

Source: https://www.hackerrank.com/challenges/service-lane

---

Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The length of the service lane is N units. The service lane consists of N segments of equal length and different width.

Calvin can enter to and exit from any segment. Let’s call the entry segment as index i and the exit segment as index j. Assume that the exit segment lies after the entry segment (i <= j) and . Calvin has to pass through all segments from index i to index j (both inclusive).

Calvin has three types of vehicles - bike, car, and truck - represented by 1, 2 and 3, respectively. These numbers also denote the width of the vehicle.

You are given an array width of length N, where width[k] represents the width of the kth segment of the service lane. It is guaranteed that while servicing he can pass through at most 1000 segments, including the entry and exit segments.

• If , width[k] = 1, only the bike can pass through the kth segment.
• If , width[k] = 2, the bike and the car can pass through the kth segment.
• If , width[k] = 3, all three vehicles can pass through the kth segment.

Given the entry and exit point of Calvin’s vehicle in the service lane, output the type of the largest vehicle which can pass through the service lane (including the entry and exit segments).

T test cases follow. Each test case contains two integers, i and j, where i is the index of the segment through which Calvin enters the service lane and j is the index of the lane segment through which he exits.

Constraints

2 <= N <= 1000
1 <= T <= 1000
0 <= i < j < N
2 <= j - i + 1 <= min(N,1000)
1 <= width[k] <= 3, where 0 <= k < N

Output Format

For each test case, print the number that represents the largest vehicle type that can pass through the service lane.

Note: Calvin has to pass through all segments from index i to index j (both inclusive).

---

Sample Input

8 5
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7

Sample Output

1
2
3
2
1

Explanation

Below is the representation of the lane:

   |HIGHWAY|Lane|    ->    Width

0: |       |--|            2
1: |       |---|           3
2: |       |-|             1
3: |       |--|            2
4: |       |---|           3
5: |       |--|            2
6: |       |---|           3
7: |       |---|           3

1. (0, 3): Because width[2] = 1, only the bike can pass through it.
2. (4, 6): Here the largest allowed vehicle which can pass through the 5th segment is the car and for the 4th and 6th segment it’s the truck. Hence the largest vehicle allowed in these segments is a car.
3. (6, 7): In this example, the vehicle enters at the 6th segment and exits at the 7th segment. Both segments allow even trucks to pass through them. Hence the answer is 3.
4. (3, 5): width[3] = width[5] = 2. While the 4th segment allows the truck, the 3rd and 5th allow up to a car. So 2 will be the answer here.
5. (0, 7): The bike is the only vehicle which can pass through the 2nd segment, which limits the strength of the whole lane to 1.

---

I’m excited to see what you guys come up with. My solution(s) will be up shortly.

@oaktree out.

[Cromical]

Good job and great article! Keep it up!

[Khaos]

Here’s a Python solution:

import sys

def GetMinSize(widthList, start, end):
    requiredWidthsList = widthList[start:end + 1]
    return min(requiredWidthsList)

def Main():
    n,t = raw_input().strip().split(' ')
    n,t = [int(n),int(t)]
    width = map(int,raw_input().strip().split(' '))
    for a0 in xrange(t):
        i,j = raw_input().strip().split(' ')
        i,j = [int(i),int(j)]
        print(GetMinSize(width, i, j))
    
if __name__ == "__main__":
    sys.exit(Main())

[oaktree]

// c++
#include <vector>
#include <iostream>
#include <algorithm>

int main(){
    int n, t;
    std::cin >> n >> t;
    std::vector<int> width(n);
    
    for (auto& w : width) std::cin >> w;
    
    int i,j;
    while(t-- > 0) {
        std::cin >> i >> j;
        std::cout << *std::min_element(width.begin() + i,
                                       width.begin() + j + 1) // +1 bcs j is included
                  << std::endl;
    }
    return 0;
}

Basically, all one must do is find the minimum from i to j in width.

[0x00pf (pico)]

A pure C version (no error checking)

#include <stdio.h>
#include <stdlib.h>

int main (){
  int  n, t, k, i, j, r;
  char *w;

  scanf ("%d %d", &n, &t);

  w = (char*) malloc (n);

  for (i = 0; i < n; scanf("%hhd ", &w[i++]));
  for (k = 0; k < t; k++)    {
      scanf ("%d %d", &i, &j);
      for (r = w[i++]; i <= j; r = r < w[i] ? r : w[i], i++);
      printf ("%d\n", r);
    }

  return 0;
}

[oaktree]

Why do this…

w = (char*) malloc (n);

rather than…

w = (int*)malloc(n);

that?

After all, you’re collecting integers.

[0x00pf (pico)]

The values for the width array were 1,2,3. We just need to bits to store the information. C ensures that a char takes 1 byte so it just saves memory… A int array will use 2 bits out of 32 in best case…

Note: It should be better to say that a char can store the minimal addressable element by the processor… in other words, it contains a byte, but a byte may be bigger than 8 bits

[oaktree]

That’s a great idea! By why not uint8_t for expressiveness?

[0x00pf (pico)]

Sure. I’m old school. unit8_t is pretty common nowadays but it was not always available some time ago. If you work with old systems char is safer, but indeed you are right.

[0x00pf (pico)]

In order to complete the table in The Price of Scripting, I will add a couple more implementations:

Lua

#!/usr/bin/lua
n, t = io.read ("*n", "*n")

w= {}
for i=0, n - 1 do
    w[i] = io.read("*n")
end

for k=1, t do
    i,j = io.read("*n", "*n")
    print (math.min(table.unpack(w, i, j)))
end

Perl

#!/usr/bin/perl
use List::Util qw( min max );

($n, $t) = split(/\s+/, <>);
@w = split (/\s+/, <>);
while (($i, $j) = split (/\s+/, <>))
{
    print min( @w[$i..$j]) . "\n";
}

Java

My Java is a bit rusty

import java.io.*;
import java.util.*;

public class c6 
{
    public static void main (String[] args) 
    {
        int k;
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int t = in.nextInt();
	int[]  w = new int[n];
	for (k = 0; k < n; k++) w[k] = in.nextInt();
	for (k = 0; k < t; k++)
	    {
		int i = in.nextInt();
		int j = in.nextInt();
		int r = 3;
		for (int l = i; l < j + 1; l++) if (w[l] < r) r = w[l];
		System.out.println (r);
	    }
    }
}