Gap Up and Down

See the original problem on HackerRank.

John has been analyzing stocks and their prices as his latest assignment. Being a beginner in stocks, he has selected a stock HRC and collected the low, high and close prices for n days in the form of arrays:

1. \(low\), where \(low_i\) is the lowest value of the stock on \(i^{th}\) day.
2. \(high\), where \(high_i\) is the highest value of the stock on \(i^{th}\) day.
3. \(close\), where \(\) is the closing value of the stock on \(i^{th}\) day.

Recently, he came across the concept of Gap Up and Gap Down.

The stock is considered Gap Up if on a given day it’s low price is higher than the previous day’s close price, and the stock is considered Gap Down if it’s high price is lower than the previous day’s close price.

Starting from the \(2^{nd}\) day till the \(n^{th}\) day count the number of Gap Up and Gap Down the stock went through during the \(n\) days.

Input Format

The first line contains an integer \(n\), the number of days for which the stock data is given.

The next line contains the array \(low\) represented by \(n\) space-separated integers, where \(low_i\) is the lowest value of the stock on the \(i^{th}\) day.

The next line contains the array \(high\) represented by \(n\) space-separated integers, where \(high_i\) is the highest value of the stock on the \(i^{th}\) day.

The next line contains the array \(close\) represented by \(n\) space-separated integers, where \(close_i\) is the close value of the stock on the \(i^{th}\) day.

Constraints

• \(2 \leq n \leq 10^5\)
• \(1 \leq low_i, high_i, close_i \leq 10^3\)

Output Format

Print two space-separated integers representing the number of Gap Up and Gap Down observed for the stock respectively.

Example

Input:

1
2
3
4

5
5 3 7 7 2
10 9 20 15 10
6 8 16 11 6

Output:

1

0 2

Explanation:

There is no Gap Up observed.

There are two Gap Downs observed:

• highPrice[4] closePrice[3]
• highPrice[5] closePrice[4]

So we print 0 and 2 as our answer.

Solutions

This challenge is quite easy: we run a loop from \(1\) to \(n\) and check the two given conditions:

• \(low[i] > close[i-1]\)
• \(high[i] < close[i-1]\)

We keep two counters, each counting the number of times each condition is true.

In C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void solve(const vector<int>& low, const vector<int>& high, const vector<int>& close)
{
    auto gapUp=0, gapDown=0;
    for (auto i=1u; i<low.size(); ++i)
    {
        gapDown += low[i] > close[i-1];
        gapUp += high[i] < close[i-1];
    }
    
    cout << gapDown << " " << gapUp;
}

To learn something more, we can see and code the combination of patterns zip | map | reduce which emerges from this problem.

In C++, we can use inner_product (equivalent to transform_reduce):

1
2
3
4
5
6

void solve(const vector<int>& low, const vector<int>& high, const vector<int>& close)
{
    auto up = inner_product(next(begin(low)), end(low), begin(close), 0, plus<>{}, greater<>{});
    auto down = inner_product(next(begin(high)), end(high), begin(close), 0, plus<>{}, less<>{});
    cout << up << " " << down;
}

In Python:

1
2
3
4

def solve(low, high, close):
    up=sum(map(lambda (a,b): a>b, zip(low[1:], close)))
    down=sum(map(lambda (a,b): a<b, zip(high[1:], close)))
    print("%d %d" % (up, down))

It’s interesting to see how to use C++20’s ranges to solve this problem:

1
2
3

auto up = ranges::accumulate(view::zip_with(std::greater<>{}, view::tail(low), close), 0);
auto down = ranges::accumulate(view::zip_with(std::less<>{}, view::tail(high), close), 0);
cout << up << " " << down;

Clearly, all the solutions above do two iterations, one for accumulating low and one for high (might be an issue or not, think also about the cache…).

Just for fun, the following one, instead, does only one iteration - using C++20’ ranges:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

auto up = view::zip_with(std::greater<>{}, view::tail(low), close);
auto down = view::zip_with(std::less<>{}, view::tail(high), close);

auto zipped = view::zip(up, down);

auto res = ranges::accumulate(zipped, make_pair(0,0), [](auto p, auto n){
    return make_pair(p.first+n.first, p.second+n.second);
});

cout << res.first << " " << res.second;

Similarly, in Python:

1
2
3
4

up=(map(lambda (a,b): a>b, zip(low[1:], close)))
down=(map(lambda (a,b): a<b, zip(high[1:], close)))
zipped = zip(up, down);
print(reduce(lambda f,s : (f[0]+s[0], f[1]+s[1]) , zipped, (0,0)))

An Haskell soution by alepez, with parser and serialization included:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

main = interact $ ser . compute . de

de s = (ls, hs, cs)
  where
    [ls, hs, cs] = (fmap read) <$> words <$> (drop 1 $ lines s)

ser (gapUp, gapDown) = unwords . map show $ [gapUp, gapDown]

compute :: ([Int], [Int], [Int]) -> (Int, Int)
compute (ls, hs, cs) = (gapUp, gapDown)
  where
    gap op xs = length $ filter op $ zip (tail xs) cs
    gapUp = gap (\(l, c) -> l > c) ls
    gapDown = gap (\(h, c) -> h < c) hs