Coding Problem: Counting Valleys

View original at HackerRank

Problem Verbatim: Hackerrank wants us to solve for how many valleys Gary enters into and exits on his hike. Note: this is not how many times Gary went down a step, that would be quite simple. This program should calculate how many times Gary entered below sea-level and then exited.

We will always be provided an array containing two types of values: D (Down) and U (Up).

Example Input

UDDDUDUU

_/\            _
      \        /
        \/ \/

Example Output
1

Background: Let’s read this array from left to right. Gary begins at sea-level and moves up one space, therefore he has entered a mountain in the program. Given that the program is only asking for valleys, we don’t need to tally the mountains encountered on the trip.

The next move is down one space, leaving us at sea-level. So far, Gary has gone up one space and then down one space. We can better represent this as variables:

up = 1
down = 1

Given that Gary has traveled up as many spaces as he has traveled down, we know that Gary is currently at sea-level. Another way of writing that might be:

up = 1
down = 1

if up = down then it’s true Gary is at sea level

By moving down a space, Gary has now left sea-level and entered a valley, which will be the first one tallied in this program. Instead of returning to sea-level, Gary traverses down deeper into the valley one space, and then up one space.

At this point in the journey, Gary has gone down 3 spaces and up 2. We can represent this like:

up = 2
down = 3

Because down is greater than up, we know that Gary must still be in the valley. We’ll continue this logic until Gary has completed his journey. By the end of the array, we’ll have:

Up = 4
Down = 4

Meaning Gary has returned to sea level and exited the valley, the only valley we have recorded Gary entering on his journey.

Pseudocode
Our code should do the following:
1. Determine whether Gary is at sea-level
2. Determine whether Gary has entered a valley
3. Track the total amount of up spaces and down spaces
4. Determine if Gary has left the valley
5. Tally the total amount of valleys Gary enters on his trip
Python3 solution:

Coding Problem: Sock Merchant program (Finding Pairs)

HackerRank

View the original problem at HackerRank

Problem Verbatim: Given a series of numbers, find the number of times unique pairs appear and return the total pairs as an integer.

The story behind this problem disguises a fairly straightforward task. John works at a clothing store and needs to sort a pile of socks by color, with an integer representing each color. Given an array of numbers, find the total amount of unique pairs in the array.

Example Input:

n = 7 (Size of the array)

color_array = [10, 20, 40, 10, 30, 20, 10]

Example Output:
pairs = 2

Background
First off, the fact that each number represents a color is excess information. Regardless of the array being:

color_array = [10, 20, 40, 10, 30, 20, 10]

or

color_array = [“blue”, “green”, “red”, “blue”, “white”, “green”, “blue”]

The program should run regardless because, essentially, this is a frequency program.

Let’s continue with our array, but let’s make it a little bigger:

color_array = [10, 20, 40, 10, 30, 20, 10, 20, 50, 10, 30, 10, 40, 50, 20]
n = 15

Looking at this array, we see that there are five 10’s, four 20’s, two 30’s, two 40’s, and two 50’s. A better way of writing this would be:

10: 5, 20: 4, 30: 2, 40: 2, 50: 2

Hopefully this format is beginning to look familiar. In this example, we are representing the frequency of our values in a dictionary, the key being the integer and the value being the frequency.

Remember, however, that we are looking for unique pairs. For this, simply divide each value by 2.

{ 10: 2.5, 20: 2, 30: 1, 40: 1, 50: 1 }

Almost there. We still need to account for odd frequencies, like the integer 10. Because we can’t have half a pair, we’ll need to round down. That’s simple with the floor function.

floor(2.5) = 2

Alright! Let’s put this all together.

Pseudocode



In Python 3: