How ever much I like paper, rock and scissor we only use paper and scissor in the problem of cutting paper squares. Continue reading →

# Python

## 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

RohantoRivendellto meet Frodo but there is no direct route fromRohan(T_{1}) toRivendell(T_{n}).But there are towns T

_{2},T_{3},T_{4}…T_{n-1}such that there are N_{1}routes from Town T_{1}to T_{2}, and in general, N_{i}routes from T_{i}to T_{i+1}for i=1 to n-1 and 0 routes for any other T_{i}to T_{j}for j ≠ i+1Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Note

Gandalf has to pass all the towns T_{i}for i=1 to n-1 in numerical order to reach T_{n}.

For each T_{i}, T_{i+1}there are only N_{i}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 i^{th}integer denotes the number of routes, N_{i}, from the town T_{i}to T_{i+1}

Output Format

Total number of routes from T_{1}to T_{n}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.

## 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.

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.

## 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 FormatPrint the number of handshakes for each test-case in a new line.

## 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.

## 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.

## 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

2cycles of growth every year. Each spring, itdoublesin height. Each summer, its height increases by1meter.Laura plants a Utopian Tree sapling with a height of

1meter 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 →

## 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 x

_{1}and moves at a rate of v_{1}meters per jump. The second kangaroo starts at location x_{2}and moves at a rate of v_{2}meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they’ll ever landat the same location at the same time?

Input Format

A single line of four space-separated integers denoting the respective values of x_{1}, v_{1}, x_{2}and v_{2}

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