Solutions

HackerRank: Connecting Towns

HackerRank: Connecting Towns

Welcome to the Shire… Well at least welcome to Middle Earth, we don’t actually need to travel through the shire in the next HackerRank problem with Connecting Towns. The problem reads

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4…Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Note
Gandalf has to pass all the towns Ti for i=1 to n-1 in numerical order to reach Tn.
For each Ti , Ti+1 there are only Ni distinct routes Gandalf can take.

Input Format
The first line contains an integer T, T test-cases follow.
Each test-case has 2 lines. The first line contains an integer N (the number of towns).
The second line contains N – 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1

Output Format
Total number of routes from T1 to Tn modulo 1234567
http://en.wikipedia.org/wiki/Modular_arithmetic

Solving the math of Connecting Towns

There are two things we need to get our heads around. There is the first part which is how many paths there are, and then there is the second part of the modulo.

The former problem of the paths is rather simple as it is a simple combinatorics problem and the total number of paths are just the product of the paths of each leg of the journey

The problem of the modulo operator can be treated in different ways. Since we are using Python as implementation language we can completely ignore it, as it can handle arbitrarily large integers. However, we can also solve it as we have done for Project Euler problem 48.

In general we have the formula

Which means that for every time we multiply with the next set of paths we can also take the modulo, which means we will keep the total size of the integer down significantly.  If it actually matters in Python I don’t know.

Implementing Connecting towns in Python

Let us implement the one with modulo arithmetic. However since we know that both a and b in the previous formula will be smaller than the modulo. Therefore a%c = a and b%c= b, so we only need to take modulo of the result during the iterations. Therefore the function we need to implement is

def connectingTowns(n, routes):
    paths = 1
    for i in routes:
        paths = (paths * i) % 1234567
    return paths

and that should solve the problem.

Posted by Kristian in HackerRank, 0 comments
HackerRank: Minimum Height Triangle

HackerRank: Minimum Height Triangle

It is always fun to work with triangles in any kind of setting not least problem solving in HackerRank. The problem Minimum Height Triangle is no exception. The problem reads

Given integers b  and a, find the smallest integer h, such that there exists a triangle of height h, base b, having an area of at least a.

image

In case we should have forgotten the primary school mathematics. The area of a triangle is given by

This can be isolated such that we get the height of the triangle instead as

Since we want the minimum integer size we then need to ceil that such that we get

This can be implemented in Python as

def lowestTriangle(base, area):
    return math.ceil(2 * area / base)

I usually write somewhat longer posts. But to be honest, I don’t know what to add to this problem.

Posted by Kristian in HackerRank, 0 comments
HackerRank: Handshake

HackerRank: Handshake

Time to shake hands with a lot of people in the next HackerRank challenge called Handshake. The problem reads

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Input Format
The first line contains the number of test cases T, T lines follow.
Each line then contains an integer N, the total number of Board of Directors of Acme.

Output Format

Print the number of handshakes for each test-case in a new line.

Continue reading →

Posted by Kristian in HackerRank, 3 comments
HackerRank: Maximum Draws

HackerRank: Maximum Draws

Second round of the fundamental mathematics problems on HackerRank is called Maximum draws.  It asks the following

Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

Input Format
The first line contains the number of test cases T.
Next T lines contains an integer N which indicates the total pairs of socks present in the drawer.

Output Format
Print the number of Draws (x) Jim makes in the worst case scenario.

Continue reading →

Posted by Kristian in HackerRank, 0 comments
HackerRank: Find the Point

HackerRank: Find the Point

I finally found the math problems on HackerRank which makes me so happy. So let’s getting cracking on the first one called Find the Point. It asks us to

Consider two points,  and . We consider the inversion or point reflection, of point  across point   to be a  rotation of point  around .

Given  sets of points  and , find  for each pair of points and print two space-separated integers denoting the respective values of  and  on a new line.

Continue reading →

Posted by Kristian, 2 comments
HackerRank: Utopian Trees

HackerRank: Utopian Trees

I found another fun little problem at HackerRank called Utopian trees. It is not an easy due to the input constraints. Given how small they are I am pretty sure it could be solved by bruteforce.  The problem description is

The Utopian Tree goes through 2 cycles of growth every year. Each spring, it doubles in height. Each summer, its height increases by 1 meter.

Laura plants a Utopian Tree sapling with a height of 1 meter at the onset of spring. How tall will her tree be after n growth cycles?

Given that the number of test cases is smaller than 10 and the number of cycles are less than 60, it should be pretty obvious that it can be bruteforced. However, there is also a nice analytical solution to this.  Continue reading →

Posted by Kristian in HackerRank, 0 comments
Shenzhen I/O: Carbine Target Illuminator

Shenzhen I/O: Carbine Target Illuminator

Once again we are going to make equipment for military use. Someone in the company is not going to be happy about it. This time it is a Carbine Target illuminator, so we can see the bad guys before we shoot them. With the use of radar we are going to measure the distance to the bad guy by counting the number of cycles between output and input to the radar. Based on that we will turn on the laser sight and or the flood light in the following configuration.

Shenzhen I/O - Carbine target Illuminator - specification Continue reading →

Posted by Kristian in Shenzhen IO, 1 comment
Hackerrank: Forming a magic Square

Hackerrank: Forming a magic Square

I must admit that this problem actually took me a good while to solve. Once you have the right insight on forming a magic Square it is really straight forward. But until that point I was just stuck. Anyway, before rambling on lets get to the actual problem.

We define a magic square to be an  matrix of distinct positive integers from 1 to nwhere the sum of any row, column, or diagonal (of length n) is always equal to the same number (i.e., the magic constant).

Consider a  matrix, s, of integers in the inclusive range [1, 9]. We can convert any digit, a, to any other digit, b, in the range [1, 9] at cost .

Given , convert it into a magic square at minimal cost by changing zero or more of its digits. Then print this cost on a new line.

Note: The resulting magic square must contain distinct integers in the inclusive range [1, 9].

Continue reading →

Posted by Kristian in HackerRank, 0 comments
Shenzhen I/O: Personal Sandwich Maker

Shenzhen I/O: Personal Sandwich Maker

Yeah, this time we are going to make a personal sandwich maker. What could possibly go wrong when making food? Nothing right! This one took me a while to crack, or rather it was fairly easy to make solution. But it took me quite a few tries to make a good one.

The sandwich maker print board have an xbus input where it gets a number from 1 to 3 which is three different modes

  1. Normal sandwich
  2. Hold the cheese
  3. Extra mustard

Continue reading →

Posted by Kristian in Shenzhen IO, 0 comments