Half a dozen of greedy problems

A small collection of greedy problems, as found in week three of edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego.

Kind of disappointing this third week of the course, since they removed the access to their online problem verifier for the unregistered user. Besides, these kind of problems loose large part of their appeal if you already know they could be solved following a greedy approach. The spoiler is too big, you just have to verify the greedy step is safe. Still, let's have a look of them. As usual, I provide my full python code on GitHub.

Changing Money

Task: Find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.

Solution: Start from considering the higher denomination, it is safe to remove that value from the input until we can, since obviously that leads to the minimum possible result.

This is the core loop of the algorithm:
for coin in DENOMINATIONS:
    counter = leftover // coin  # 1
    if counter > 0:
        result += counter
        leftover %= coin   # 2

    if leftover == 0:
        break
1. It would be boring subtracting one coin after the other till we can, better to integer-divide the amount for the current denomination.
2. The modulo of the above division gives the amount that still have to be reduced to coins.

Maximizing the Value of a Loot

Task: Implement an algorithm for the fractional knapsack problem

Solution: Sort the input values, a list of tuples of value and weight, accordingly to their value per unit. Then get the required quantity from it.

There is a simple way to sort it in that way when python is you implementing language:
loot = sorted(items, key= lambda item: item[0]/item[1])
Notice that I'm keeping the natural ordering, form smallest to greater, so I would check the values from right to left.

Maximizing Revenue in Online Ad Placement

Task: Given two same sized integer sequences, partition them into pairs such that the sum of their products is maximized, and return such value.

Solution: There is no trick with negative values, you could just sort both sequences and multiply the items with the same index between them. Conceptually, we should start from the highest values down to the lowest one. Actually, it is all the same.

To extract the same-index components from two (or more) iterables in python we could use the handy zip() function:
for p, c in zip(profits, clicks):
    result += p * c

Collecting Signatures

Task: Given a list of 2-tuples representing segments, find the minimum number of points such that each segment contains at least one point.

Solution:
segments.sort(key=lambda item: item[1])  # 1

results = [segments[0][1]]  # 2
for segment in segments:
    if segment[0] > results[-1]:
        results.append(segment[1])  # 3
1. Sort the segments in natural order for the ending point of each segment. Notice the python way of specifying which component has to be used to sort the list.
2. Initialize the result list with the first point, ending of the first (sorted) segment.
3. When we find an ending point of a segment that is more to the right of the last one, we add it to the result list. We can easily prove that this is a safe move, so our greedy algorithm is OK.

Maximizing the Number of Prize Places in a Competition

Task: Given a positive integer, find the sum of integers largest in size equals to the given input and containing only unique values.

Solution: The simpler case is when we can use the natural sequence until the input value is reached. This approach works for 6
6 = 1 + 2 + 3
but it doesn't work, for instance, for 2 or 8
2 = 2
8 = 1 + 2 + 5
The key point is that, before adding an element to the result list, we should ensure we keep enough space for another element that should be bigger that the current one.
So, for instance. We get 2 in input, we would like to put 1 in the result list, but if we do that we are left with another 1 that we can't add, since no duplicated are allowed, so we skip it and add 2 instead, completing our job.
In case of 8, 1 and 2 could be safely added to the result list. When we consider 3, our leftovers are 5, if we put 3 in the list, we are left with a 2, that is useless, so we discard 3 and put in the result list 5 instead.

So we modify our pushing in the result list of all the elements in the natural sequence with this check:
if unassigned - i <= i:
    results.append(unassigned)
    break
When we enter the "if", we have reached the last element in the result list.

Maximizing Your Salary

Task: Compose the largest number out of a set of integers.

Solution: The trick is that the integers in input could be 1, 2, or 3 digits wide. If they were all one-digit numbers, the job would have been easy, just sort them in reversed natural order, and join them up.

Here we have to sort them in a way that '2' is to the left of '21', so that the input ['21', '2'] would lead to a result of 221.

My idea was to compare the numbers in the input list as all of them had 3 digits, extending the shorter ones duplicating the rightmost digit as required. So, I would think of the previous example as ['211', '222'], and that would lead to the expected result.

To that in python, I have created a filler function and used it in sorting in this way:
def filler(token):
    while len(token) < 3:
        token += token[-1]
    return token

# ...

tokens.sort(key=filler, reverse=True)
Again, please have a look on GitHub for details.

Go to the full post

Last Digit of the Sum of Fibonacci Numbers

Another couple of problems in the same lot of the one previously discussed. Now we have to calculate the last digit of the (full or partial) sum of Fibonacci numbers.

Also these problems are presented in the the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, week 2, so I suggest you to give them a try and then comparing your solutions with my python scripts.

Last Digit of the Sum of Fibonacci Numbers

Given an integer 𝑛, find the last digit of the sum 𝐹0 + 𝐹1 + · · · + 𝐹𝑛.

Considering that n could be as big as 10^14, the naive solution of summing up all the Fibonacci numbers as long as we calculate them is leading too slowly to the result.

We'd better take notice of the hint about experimenting a bit with small test cases looking if we can extrapolate anything interesting. Actually, after a while I find out that the sum of the first n Fibonacci number is just one shorter than the sum of Fibonacci of n + 2. Another useful consideration is that, since we need just the last digit, we could use the result of the previous exercise and limit our loop following the Pisano period.

Putting all together, this is my solution:
PISANO = 60  # 1


def solution(number):
    if number < 2:
        return number

    number %= PISANO

    results = [1, 1]
    for _ in range(number):
        results.append((results[-1] + results[-2]) % 10)  # 2

    return (results[-1] - 1) % 10  # 3
1. Instead of giving the result for the requested number, I check the modulo 60, being that the Pisano period for 10.
2. I'm not interested in the actual Fibonacci number, just it's last digit, so here I apply modulo 10 to the brand new calculated one. In this way I avoid scaling to big numbers.
3. I apply the modulo operator once again to get rid of the unfortunate case of possibly negative results.

Naive, Pisano script, and test case for both, are on GitHub.

Last Digit of the Partial Sum of Fibonacci Numbers

Given two non-negative integers π‘š and 𝑛, where π‘š ≤ 𝑛, find the last digit of the sum πΉπ‘š + πΉπ‘š+1 + ... + 𝐹𝑛.

The trick used in the previous problem won't work here, and I couldn't think of any similar clever approach. So I resorted to make full use of Pisano, hoping that it was enough.
PISANO = 60


def solution(left, right):
    assert not left > right  # 1

    fib_mods = [0, 1]  # 2
    for _ in range(PISANO - 2):
        fib_mods.append((fib_mods[-1] + fib_mods[-2]) % 10)

    left %= PISANO  # 3
    right %= PISANO
    if right < left:
        right += PISANO

    result = 0
    for i in range(left, right + 1):
        result += fib_mods[i % PISANO]  # 4
    return result % 10  # 5
1. Not strictly required by the problem, where we can assume the input data is clean.
2. I fill this list with all the Fibonacci number modulo 10 in the range of the Pisano period.
3. I don't need to loop on all the actual requested numbers, I can safely stay in the limit of the Pisano period. With one major caveat, the right limit should not become smaller that left.
4. Loop on the interval, ensuring that I stay in the Pisano limits.
5. Return the last digit of the sum, as required.

Also for this problem I have pushed naive, Pisano script, and test case for both, on GitHub. See the github folder for all the stuff about week 2 exercises.

Go to the full post

Fibonacci modulo with Pisano period

Dealing with Fibonacci numbers becomes easily unmanageable for big numbers. However, if we are not interested to the full number, but just to its modulo, there is a handy trick that would help us.

The thing is that if we have a look at the Fibonacci sequence after applying to each element a modulo operator, we would notice that we always get periodic sequences.
Modulo 2 leads to a infinite repetition of three elements: 0, 1, 1
Modulo 3 to eight elements: 0, 1, 1, 2, 0, 2, 2, 1
Modulo 10 to sixty, et cetera.

There is no known way to get the length period given the modulo - called Pisano period - but we know that each Pisano period starts with "0, 1" and this signature is found just at the beginning of a period.

On this fact, the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, week 2, proposes three problems. I strongly suggest you to take the course before going on reading this post, getting back here to compare your solution with mine.

Here is the first one, Calculate Fibonacci modulo m.

Given two integers 𝑛 and π‘š, output 𝐹𝑛 mod π‘š.

The issue is that n could be up to 10^18. Less preoccupying the upper limit for m, fixed in 10^5.

A first naive solution would consist in calculating the required Fibonacci number, applying the modulo operator to it, return the result. Easy-peasy. However my naive python implementation started to get too slow for mere values about 10^5.

To use the Pisano period we have firstly to get its length. The only reasonable way I could think of, was looking for the modulo sequence checking for first repetition of the starting signature "0, 1".
def pisano(modulo):
    previous = 1
    current = 1

    result = 1
    while not (previous == 0 and current == 1):  # 1
        buffer = (previous + current) % modulo  # 2
        previous = current
        current = buffer

        result += 1

    return result
1. Loop until the starting signature is found
2. Get the next Fibonacci-modulo number

Let's now write a function to get a Fibonacci-modulo number. We could use instead a plain Fibonacci function and then apply the modulo operator to its result. This custom function saves the cost of adding big numbers between them.
def fibonacci(number, modulo):
    if number < 2:
        return number

    results = [1, 1]
    for _ in range(number - 2):
        results.append((results[-1] + results[-2]) % modulo)

    return results[-1]
Now, the solution itself is almost trivial.
def solution(number, modulo):
    return fibonacci(number % pisano(modulo), modulo)
Full python code, for both the trivial and Pisano case, and test case on GitHub.

Go to the full post

HackerRank DFS: Connected Cell in a Grid

In this HackerRack problem, we are given in input an n x m matrix containing as elements just 0s and 1s. We should give as output the size of the largest available region.

As suggested in the name of the problem, we should think of a solution that refers to graphs, and more specifically on the Depth First Search algorithm on them.

To better understand what are we required to get, let's have a look at the provided example:
[1, 1, 0, 0]
[0, 1, 1, 0]
[0, 0, 1, 0]
[1, 0, 0, 0]
This matrix has two so called "regions", one takes just the 1 in the bottom left corner, the other all the remaining ones. Obviously, the largest one is the latter, so we are expected to return 5.

Notice that two 'alive' cells are considered connected if they have distance one, horizontally, vertically, or diagonally.

Following the hint, I implemented my python solution applying the DFS on each cell in the matrix.
def solution(matrix):
    result = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            result = max(result, connected(matrix, i, j))  # 1
    return result
1. The result is initialized to zero, when connected() return a value higher than the current result, it takes the place of the current better solution found.

Now I just have to write the connected() function. Based on DFS, it would recursively call itself looking for all the cell connected to the current one. Slight variation, it would return the size of the group. For efficiency reasons, I decided to implement it in a disruptive way. The matrix would be modified to keep track of the visited cells. This is usually not a good idea, but in a problem like this, we can live with it.
def connected(matrix, i, j):
    if not (0 <= i < len(matrix)) or not (0 <= j < len(matrix[0])):
        return 0  # 1

    if matrix[i][j] != 1:
        return 0  # 2

    result = 1  # 3
    matrix[i][j] = 0  # 4

    for ii in range(i-1, i+2):
        for jj in range(j-1, j+2):
            if i != ii or j != jj:
                result += connected(matrix, ii, jj)  # 5

    return result
1. If we are stepping out the matrix borders, there's nothing to do. Just return zero.
2. If the current cell is not "alive", it is not part of any group, return zero.
3. Otherwise, count it for the current group.
4. This is the soft spot I talked about above. Instead of keeping track of the visited node, I simply set it to "dead". It won't harm to the algorithm, since we would count each node just once, still it could be surprising for the caller seeing the matrix changed.
5. Go and visit all the nodes connected to the current one. The two for-loops select the indices in the current cell adjacency, the "if" excludes the current one. We will check if the selected position refers to an actual connected node in (1) and (2) and then apply the recursion.

And that's it. Full python code and test case I used to help me getting the solution is on GitHub.

Go to the full post

HackerRank Recursion: Davis' Staircase

The point of this HackerRank problem is calculating a sort of uber-Fibonacci number. Since we want to have an efficient solution, we should immediately think to a dynamic programming approach, or at least to some kind of memoization.

Let's call Davis number the number of ways we can climb a staircase, with the rule that we can take 1, 2, or 3 steps at a time.

First thing, we want to identify the base cases. That's pretty easy.
  1. Our staircase has just one step, we have only one way to climb it, taking 1 step.
  2. We can climb it in a single two-step jump, or we can take 1 step, then falling back to the previous case. Total of two ways of climbing.
  3. A single three-step jump is a way to get on top, otherwise we can take one step and falling back to case (2) or take a two-step jump and fall back to case (1). This means 1 + 2 + 1 = 4 ways of climbing this staircase.
The generic case is determined by the three precedent ones, something like this:
result = davis_number(n-1) + davis_number(n-2) + davis_number(n-3)
Given that, I skipped the step of writing a plain recursive solution to the problem, and I moved directly to write a Python script that uses a cache to get the result via DP.

I cached the basic step results as identified above in a list (and I define a constant that make explicit the requirement stating that a staircase could not have more that 36 steps):
cache = [1, 2, 4]
MAX_STEPS = 36
And then I wrote my solution:
def solution(steps):
    assert 0 < steps <= MAX_STEPS  # 1
    if steps <= len(cache):  # 2
        return cache[steps - 1]

    for _ in range(steps - len(cache)):  #3
        cache.append(cache[-1] + cache[-2] + cache[-3])

    return cache[-1]  # 4
1. Without this assertion, the code would become unstable for negative input values (maybe an IndexError exception, maybe simply a wrong result) and would take a very long time for large positive input values. Better a predictable AssertionError instead.
2. The result has been already calculated, and it is available in the cache. Just return it.
3. Let's calculate the required value. To do that, we need to calculate all the previous values, so we extend the cache calculating in order all of them.
4. Finally, we return the rightmost element in the cache, that is, the required Davis' number.

If MAX_STEPS was a bigger number, it could be a good idea to predetermine the full size for the cache, filling it with zeroes, and pushing the actual values when the solutions are created. This would require an extra variable to keep track of the current last Davis number in cache, and would make the code slightly more complicated. Here I found better to keep the code simple.

Full Python script and testcase on GitHub.

Go to the full post

HashMap.computeIfAbsent() behavior in Java 9

If in your code you are using computeIfAbsent(), be aware that it has changed its behavior in Java 9. Now you get a ConcurrentModificationException if the mapping function changes the map.

So, for instance, this Fibonacci calculator works fine in Java 8:
class Fibonacci {
    private static final Map<Integer, Long> cache = new HashMap<>();
    static {
        cache.put(0, 0L);
        cache.put(1, 1L);
    }

    public long calculate(int x) {
        return cache.computeIfAbsent(x, n -> calculate(n - 1) + calculate(n - 2));
    }
}
But not if you try to run it in Java 9.

As the computeIfAbsent()'s javadoc states quite clearly, "This method will, on a best-effort basis, throw a ConcurrentModificationException if it is detected that the mapping function modifies this map during computation". If you have a look at the code, you will see that line 1139 is:
if (mc != modCount) { throw new ConcurrentModificationException(); }
And the mc counter is increased a bit below to keep track of any changes in the map due to mappingFunction.

My way out to this issue has been refactoring the Fibonacci calculation to get rid of computeIfAbsent(). Something like that:
public long calculate(int x) {
    if (cache.containsKey(x)) {
        return cache.get(x);
    }

    long lhs = cache.containsKey(x - 1) ? cache.get(x - 1) : calculate(x - 1);
    long rhs = cache.containsKey(x - 2) ? cache.get(x - 2) : calculate(x - 2);
    long result = lhs + rhs;

    cache.put(x, result);
    return result;
}
Well, it's not a beauty. At least it works.

Go to the full post

CodeEval Lowest Unique Number revised

Given a list of numbers, find the pne that is unique and have the smallest value. I have just provided a python solution to this CodeEval problem, but there was something in it that bothered me. So here I provide an alternative solution.

The soft spot in my previous solution was the combined sorting of the buffer counter dictionary added to a call to index() on the data list. I could live with the sorting, but I felt as unbearable the re-scan the data list to get the actual index. The Counter object knew it on its initialization, why don't use it at that time?

The refactoring ends up with code that is less readable than the first version and the performance gain, in this specific problem is minimal. It would make sense if the problem would require to accept in input long sequences of numbers. Anyway, here it is.
NOT_FOUND = 0  # 1
FOUND_MANY = -1

def solution(line):
    data = [int(x) for x in line.split()]  # 2
    result = [0] * 9  # 3
    for i, number in enumerate(data):  # 4
        result[number-1] = i+1 if result[number-1] == NOT_FOUND else FOUND_MANY  # 5

    for index in result:  # 6
        if index > NOT_FOUND:
            return index
    return 0
1. I am going to flag the items in the buffer with zero to mean that the relative number was not found, and with a minus one when multiple instance were found.
2. As in the original solution, I convert the input string in a list of integers.
3. Instead of using a Counter collection, here I have a list of integers, reporting for each number in [1..9] the first reference index in data.
4. First loop. I scan each element in data. I need both its position and value, so I use the enumerate builtin to get them.
5. The need for switch from 0-based to 1-based indices leads to this painful line. I have to decrease number, to make it a 0-based index in the buffer list named result, and I have to increase i so that it becomes an 1-based index, as required by the problem.
6. Second loop. I scan each index as stored in the result buffer, as soon as I find a valid value I return it as a solution. If there is no valid index in that list, zero is returned instead.

I pushed the changes on GitHub.

Go to the full post

CodeEval Lowest unique number

We have a string in input containing numbers is the range [1 .. 9]. We want to get the index (following the unsettling Pascal habit of giving one for the first element) of the lowest unique number available, if such a beast exists, otherwise zero. This is the CodeEval problem #103.

So, for instance, given these two sequences:
3 3 9 1 6 5 8 1 5 3
9 2 9 9 1 8 8 8 2 1 1
In the first case we should return 5, index of the unique 6 in the list, and in the second case we return 0, since there is no unique number.

Here is the core of my python solution.
data = [int(x) for x in line.split()]  # 1
counter = Counter(data)  # 2
for key, value in sorted(counter.items()):  # 3
    if  value == 1:  # 4
        return data.index(key) + 1
return 0  # 5
1. I convert the input string to a list of integer.
2. I use a collections Counter object to count the number in the list. Now counter is a dictionary where the key is any number passed in input and the associated value is its numerosity.
3. I sort the items in the counter, so that I start checking from the lowest value on, and I loop on all of them.
4. As soon as I find an item in the counter dictionary that has value 1 (meaning, its key is unique) I return the first element in data with such value. I have to add one to the position returned by the index() method because I have to convert the C-style index to a Pascal one, as required by the problem.
5. I fall off the for loop without finding my egg.

Full python script on GitHub.

Go to the full post

CodeEval Pass Triangle

We are given as input a sequence of integers that we should think representing a triangle. We should return the maximum value we can get adding all values from the top vertex of the triangle down to the bottom, chosing a path moving always downwards between adjacent elements. This is CodeEval problem #89.

For example, if this is the triangle we get as input:
5
  9 6
 4 6 8
0 7 1 5
The expected solution is 5 + 9 + 6 + 7 = 27

I started thinking in the Dynamic Programming direction. Seeing that for a minimal triangle the result comes out comparing the two lower elements and then adding the bigger one to the higher one, I simply applied this rule to all the elements, starting from the bottom line up to the second from top.

Here is my python code:
def solution(data):  # 1
    for i in range(len(data) - 1, 0, -1):  # 2
        for j in range(len(data[i])-1):  # 3
            data[i-1][j] += max(data[i][j], data[i][j+1])  # 4
    return data[0][0]  # 5
1. The solution function is called passing as input parameter a list of list of integers. The first list contains just a value, the triangle top element. As usual, we can assume that the data we receive is as expected. No check is required.
2. The loop variable in this for-loop goes from the last line (3, in the example case) down to 1. This is the line from which I'm reading the values, I'm going to write in the line above.
3. Here the loop variable of the for-loop represents the index of the first element I'm comparing.
4. Calling max() I see which one is the selected value, and I add it to the element in the line above.
5. Finally I just have to return the top element, that now contains the result.

Notice that my code is destructive, since I use the input data as working area. This is usually considered not a problem, or even good, in this context (less code, cheaper and faster). Not so if the user of the function would like to do something else with its data!

The complete python script is on GitHub.

Go to the full post

CodeEval Query Board

We have a square matrix of fixed size, and we receive a bunch of commands in input to operate on it. Two of them are about setting values on it, the other two perform a query and return an integer result.
This problem is quite simple, more detail on CodeEval #87, still, I'm writing a few lines about it because it gave me a way to exercise with a couple of Python features.

Mapping command names with function names

We receive the description of what to do as a string like this "SetCol 32 20". The first element is the name of the command we want to perform on our matrix. It looks like it has been written thinking in a Pascal-based language, but I want to use Python, so I convert it in a standard compliant name using a dictionary:
ID_2_NAME = {'SetRow': 'set_row', 'SetCol': 'set_col', 'QueryRow': 'query_row', 'QueryCol': 'query_col'}
A couple of notation here. Firstly, as usually happen in these kind of problem, we don't have to care about error handling. In real life, we should expect bad data in input.
Secondly, I have decided to wrap matrix and related functionality in a class. Using free functions instead, I would have mapped the names with the functions, something like this:
SIZE = 256
board = # ...

def set_row(i, value):
    for j in range(SIZE):
        board[i][j] = value

# ...
ID_2_FUN = {'SetRow': set_row, # ...

# call set_row(15, 7)
command = 'SetRow'
ID_2_FUN[command](15, 7)
The use of a class led me to follow a different path. But this way was interesting, too.

Defining the Board class

The Board initializer just sets the size and the bidimensional list used as matrix:
def __init__(self, size=256):  # 1
    self.size = size
    self.board = [[0 for _ in range(size)] for _ in range(size)]  # 2
1. I decided not to fix the size, as I would have done in a more hasty implementation, but just to default it to the dimension, as required by CodeEval.
2. The matrix is built up on the fly with a double list comprehension. The for loop variables are not used, so I named them both with the idiomatic underscore. The external, right side, for-loop creates all the rows. The internal, left side, for-loop creates a list filled with zeroes and attach it to each row.

There is almost nothing to say about set_row() and set_col(), it's just a for-loop on the passed row or column to set each element to the specified value, see on GitHub if you want to compare your implementation with mine.

The two query functions are again logically equivalent, we just have to sum all the values for a specified row or column. However, in case of column, we have to perform an explicit for-loop, where for the row we could use the built-in sum() function:
def query_row(self, i):
    return sum(self.board[i])

Calling the Board methods

Let see again a typical command line, "SetCol 32 20". We have to split it, so that we get as first element the command name, and then the function parameters. Once I all these elements, we could get help from getattr() to call the right method with its parameters:
board = Board()
# ...

command, *params = line.split()  # 1
res = getattr(board, ID_2_NAME[command])(*[int(p) for p in params])  # 2
if res is not None:  # 3
    print(res)
1. We extract in the list params all the elements next to the first one. Beware, they are all strings here.
2. ID_2_NAME maps the command name, for instance SetCol, to the method name, set_col. Using getattr() we are actually calling the method on the passed object, same of board.set_col() here. On the right, I convert the parameters in params to integer and I extract them to single elements from the list, by the star operator.
3. The setters do not return anything. Or better, being Python functions, they return None. We are not interested in printing it. But we want to print what the query methods return.

The full Python script is on GitHub.

Go to the full post

CodeEval Balanced Smileys

This problem is part of the family of the ones asking to check if parentheses in a sentence are balanced. See for instance the simpler matching brackets one.

In this version, happy ':)' and sad ':(' smileys could be part of the the sentence, so that we have to think if a parentheses has to be considered in the balancing or skipped, being the representation of the mouth of the smiley.

I found it as CodeEval #84 problem, but it is a repost, originally coming from Facebook Hacker Cup 2013 Hackathon.

I came to a solution inferior to the one published by the Hacker Cup editors, so I just threw mine in the dustbin and I spent some time pondering on the other one, coming out with a slightly different variation. [By the way, I would suggest you to do the same. When you see a piece of code you don't fully understand, play around with it, adapt it to your style, make it yours.]

The base problem is pretty simple. We loop on each character in the string, any time we see an open bracket, we push it in a stack (or we emulate a push in a stack, using just a counter). When we see a close bracket, we pop from the stack the matching open bracket. In the end, the stack should be empty. If we try to pop when the stack is empty, the sentence is unbalanced.

Having to care to the smileys, we need a second (virtual) stack, where we push also the dubious open brackets, the one that could have a double interpretation.

Looking at the code should clarify the sense of this solution:
min_open = 0  # 1
max_open = 0  # 2
for i in range(len(msg)):  # 3
    if msg[i] == '(':  #4
        max_open += 1
        if i == 0 or msg[i-1] != ':':  # 5
            min_open += 1
    elif msg[i] == ')':  # 6
        if i == 0:
            return False
        min_open = min_open - 1 if min_open else 0
        if msg[i-1] != ':':  # 7
            if max_open == 0:
                return False
            max_open -= 1
return True if min_open == 0 else False  # 8
1. Emulate the first stack. It keep track of the "clean" open brackets only.
2. The second "dirty" stack, containing also the brackets that could be seen as mouth for a sad smiley.
3. Loop an all the character in the sentence.
4. Open bracket, push it to the "dirty" stack (i.e. increase the max_open counter), and ...
5. ... only if it couldn't be seen as the mouth of a smiley, push it to the "clean" stack (i.e. increase the min_open counter)
6. Close bracket, if we are at the beginning, the sentence is unbalanced. Otherwise, pop the matching open bracket from the "clean" stack. If it was already empty, the sentence could be unbalanced. Not sure, however, because it could be a happy smiley. So ...
7. If the bracket could be seen as the mouth of a happy smiley, the "dirty" stack empty means the sentence is unbalanced, otherwise, pop a bracket from it.
8. Completed the loop, the sentence is balanced only if the "clean" stack is empty.

The full python script is on GitHub.

Go to the full post

Calling a Stored Function from JDBC

The code we should write to call a stored procedure or function via JDBC is slightly different from the one we write to perform a SQL SELECT. A CallableStatement is used instead of a Statement plus a ResultSet to set the parameter, execute the call, and extract the result.

To check it, I have firstly created a stored function in my Oracle 12 instance, on the HR schema. It takes a SQL CHAR in input, and returns the same string with 'suffix' appended:
create or replace FUNCTION foo (val CHAR)
RETURN CHAR AS
BEGIN
    RETURN val || 'suffix';
END;
I ensured it works as I expected running this query:
SELECT foo('hello') FROM DUAL;
The I have written a couple of tests to see how to get the same result in Java. Not just one, because we can use either the JDBC escape and the PL/SQL block syntax to achieve the same result, being the first
{? = call foo(?)
and the latter
begin ? := foo(?); end;
The core of both tests is in these few lines:
cs = conn.prepareCall(call);  // 1
cs.registerOutParameter(1, Types.CHAR);  // 2
cs.setString(2, "aa");
cs.execute();
String result = cs.getString(1);  // 3
1. Assuming conn is a good java.sql connection to the HR user on my Oracle database, and call is either the JDBC escape or the PL/SQL block string showed above, the prepareCall() should return a good CallableStatement.
2. The callable statement has to know the type of the output parameter is a character string. Then we set the other parameter, with the string that we want to pass as input.
3. After executing the callable statement, we get the first (and only) result as a string.

The actual code, that you could find on GitHub, class GettingStartedTest methods callFoo(), testFunctionCallJdbcEscape(), and testFunctionCallPlSqlBlock(), is a bit more verbose because I have to provide all the standard boilerplate, initializing, testing, cleaning up.

Reference: Oracle Database JDBC Developer's Guide 12c Release 2 (12.2) 2.8 Stored Procedure Calls in JDBC Programs

Go to the full post