Python

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
HackerRank: Kangaroo

HackerRank: Kangaroo

Everybody loves a kangaroo right? Except maybe if you are Australian! Anyway in this post we shall talk both about snakes and mammals, or more specific Python and Kangaroos. I have started on learning a bit of Python and using HackerRank to learn my ways around. I have been solving a few puzzles by now.  The ones I have solved so far, are no where near the complexity of Project Euler. Apart from the fact that quite a few of the project euler problems are actually represented at HackerRank, but with more test cases, so you have to write the code a little more generically. But more about that later, because I will likely solve a few of the Project Euler problems in Python while learning it.

Anyway, the first problem I solved, which might be worth spending a minute or two about, is the problem called Kangaroo.

The short description of the problem is as follows

There are two kangaroos on a number line ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location x1 and moves at a rate of v1 meters per jump. The second kangaroo starts at location x2 and moves at a rate of v2 meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they’ll ever land at the same location at the same time?

Input Format
A single line of four space-separated integers denoting the respective values of x1, v1, x2 and v2

Note: The two kangaroos must land at the same location after making the same number of jumps.

Continue reading →

Posted by Kristian in HackerRank, 0 comments