Pages

Testing Spring Boot with JUnit5

I decided that is time to move my tests in Spring app from JUnit 4 to Jupiter. It is not too complicated, given that Spring is already supporting JUnit 5, even though the default is still the previous version. However it requires being careful in a couple of steps.

Firstly, I have changed the POM in this way:
<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-test</artifactId>
    <scope>test</scope>
    <exclusions>
        <exclusion>
            <!-- get rid of JUnit 4 -->
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
        </exclusion>
    </exclusions>
</dependency>

<!-- using JUnit 5 instead -->
<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter-engine</artifactId>
    <!-- using the version set by Spring -->
    <scope>test</scope>
</dependency>
I have excluded JUnit 4 from the spring-boot-starter-test dependency, and then I have inserted a new dependency for Jupiter, all of them are obviously in the test scope. Notice that I didn't set the version for JUnit 5, accepting instead the one proposed by Spring. Just to stay on the safe side.

The changes in "normal" testing are quite simple, usually limited in using the right imports for the new library. Something a bit more engaging is to be done for Spring Application test. What I had for JUnit 4 was something like this
@RunWith(SpringRunner.class)
@SpringBootTest
public class MyApplicationTests {
    // ...
In Jupiter, however, the annotation RunWith has been replaced with the more powerful ExtendWith, so the code has to be changed to
@ExtendWith(SpringExtension.class)
@SpringBootTest
public class MyApplicationTests {
    // ...
Not too bad, isn't it?

Go to the full post

Another interesting MOOC for Java developer

I've just completed the EdX MOOC Data Structures and Software Design by University of Pennsylvania. I would suggest it to someone with a high-beginner or lower-intermediate experience as Java software developer. I think that the lessons would sound reasonably interesting even if your level is higher, however you could be get a bit bored by the exercises - kind of too simple. This is why I didn't push anything on my GitHub account. To have some fun, I didn't use any IDE, just solved the problems in the old way, using a dumb editor, compiling and running them from command line :D Homework 11 is, in my opinion, the most interesting one in the course. We have to refactor a poorly written, albeit working, piece of code to make it fast enough to match the requirements.

Go to the full post

A nice Java testing MOOC

I've just finished the first week of the MOOC "Automated Software Testing: Practical Skills for Java Developers" provided by TU Delft on EdX. It looks to me they did a good job. Maybe, if you are a native English speaker, the speakers' accent could sometimes sound a bit weird. However, as continental European, I kind of enjoy it (and I know that my Italian accent sounds even funnier).

The course is focused on Java, JUnit 5, using IntelliJ as IDE.

It looks like a brand new production, so be ready to step into typos and minor mistakes here and there. The most annoying of them, is the one in Question 11 on the Quizzes.

We have to write tests to detect where is the bug in a function named mirrorEnds() that sort of detect how much a string is palindromic. Unfortunately, a wrong solution has to be selected to get the point on it!

If you are taking the course, I suggest you to have a look at the discussion forum to get help.

And, if you want to compare your code with mine, please find my forked repository on GitHub.

Go to the full post

Autowired, Resource, Inject

In chapter three, Introducing IoC and DI in Spring, of Pro Spring 5, I have read the example about Using Setter Injection in the annotation flavor, where for the "renderer" service the Autowired annotation was used in its setter to inject the "provider" bean in its parameter.
A note hints that other annotations, Resource and Inject, could be used, but no example is provided. I thought it was better to practice a bit on them too.

Autowired

The provided example is actually what we usually see in Spring code:
@Override
@Autowired
public void setMessageProvider(MessageProvider provider) {
    this.messageProvider = provider;
}
We should only be aware that Autowired is pure Spring, as its full name documents.

Inject

We could get the same result using the JSR standard annotation Inject:
@Override
@Inject
public void setMessageProvider(MessageProvider provider) {
    this.messageProvider = provider;
}
I had to change the provided build.gradle file for chapter three, setter-injection project, since it didn't have the compile dependency for injection, named misc.inject and defined in the main build.gradle file as
inject         : "javax.inject:javax.inject:1"
Autowired and Qualifier

Say that we have more than one Component implementing the MessageProvider interface. The default one is name "provider", and so it is chosen by Spring in the above examples. But what if I want to inject a different one, for instance "pro2":
@Component("pro2")
class MessageProvider2 implements MessageProvider {

    @Override
    public String getMessage() {
        return "Hello from Message Provider 2!";
    }
}
The Spring commonly used approach is using the Qualifier annotation.
@Override
@Autowired
@Qualifier("pro2")
public void setMessageProvider(MessageProvider provider) {
    this.messageProvider = provider;
}
Both Autowired and Qualifier are Spring specific annotations.

Resource

A JSR standard alternative to the couple Autowired + Qualifier is given by the Resource annotation.
@Override
@Resource(name = "pro3")
public void setMessageProvider(MessageProvider provider) {
    this.messageProvider = provider;
}
Here above, the Component named "pro3" is going to be injected in provider.

Inject and Named

Another JSR standard alternative to Autowired + Qualifier is provided by the couple Inject + Named.
@Override
@Inject
@Named("pro4")
public void setMessageProvider(MessageProvider provider) {
    this.messageProvider = provider;
}
I have pushed to GitHub my changes. You could see there the build.gradle file, my new Components, and the alternative setters.

Go to the full post

HackerRank Array Manipulation

We have an array of integers of a given size, that could be in the order of tenth of millions. It is initialized with all zero elements.
We change it a few times, up to tenth of thousands, adding to given subintervals each time a positive number.
At the end, we want to know which is the highest values stored in the array.

This is a Data Structures HackerRank problem. Here below I show you a naive solution, and a smarter one, both of them using Python as implementation language.

An example

First thing, I wrote a test following the provided example. As a welcomed side effect, it helps me to clarify the problem to myself.
Given an array sized 5, let modify it three times, adding 100 to the first and second element, then 100 to the elements from the second up to the fifth, then again 100 to the third and fourth.

The array should go through these states:
  0   0   0   0   0
100 100   0   0   0
100 200 100 100 100
100 200 200 200 100
At the end, 200 should be the highest value in it.

My test code is:
def test_provided_naive_0(self):
    manipulator = NaiveManipulator(5)
    manipulator.set(1, 2, 100)
    manipulator.set(2, 5, 100)
    manipulator.set(3, 4, 100)
    self.assertEqual(200, manipulator.solution())
As I'm sure you have guessed, I have implemented my naive solution as a class, NaiveManipulator, that is initialized passing the size of the underlying array, and that has a couple of methods, set() to perform a transformation, and solution() to get the requested value at the end.

Let's see its code.
class NaiveManipulator:
    def __init__(self, sz):
        self.data = [0] * sz  # 1
    
    def set(self, first, last, value):
        for i in range(first-1, last):  # 2
            self.data[i] += value  # 3

    def solution(self):
        return max(self.data)
1. The array, initialized with the passed size and with all zero elements, is kept in the member named "data".
2. The indices are given as 1-based, so I convert them in 0-based before using them.
3. Each element in the specified interval is increased by the passed value.
4. Just a call to the built-in function max()

This implementation is really naive. It works fine, but only for limited input data.

A more challenging example

What happens if I have thousands of transformations on a moderately large array, where the subinterval sizes are in the order of the array size?

Let's write a test to see it.
def test_naive(self):
    manipulator = NaiveManipulator(1_000)
    for _ in range(2_000):
        manipulator.set(10, 800, 1)
    self.assertEqual(2_000, manipulator.solution())
It works fine. However, we start seeing how it is getting time consuming. The fact is that in test_naive() we have a for-loop, inside it we call the manipulator set() where there is another for-loop. This algorithm has a O(N*M) time complexity, where N is the number of transformations and M the (average) size of the subintervals. It is enough to have both N and M in the order of thousands to get puny performances by this algorithm.

Be lazy to be faster

Do we really need to increase all the values in the subinterval each time? Why don't we just set where all the increases would start and end, and then perform the increase just once? That could save as a lot of time.

I have refactored my NaiveManipulator to a smarter ArrayManipulator, keeping the same interface, so to nullify the impact on the user code.
class ArrayManipulator:
    def __init__(self, sz):
        self.data = [0] * (sz + 2)  # 1
    
    def set(self, first, last, value):  # 2
        self.data[first] += value
        self.data[last+1] -= value

    def solution(self):  # 3
        return max(itertools.accumulate(self.data))
1. The data array is going to change its meaning. It is not storing the actual value for each element, but the difference between the previous element and the current one. This explains why I need to increase its size by two, since I add a couple of sentinel elements, one at the begin, the other at the end.
2. Instead of changing all the elements in the subinterval, now I change just the first, to signal an increment sized "value", and the one after the last one, to signal that we are getting back to the original value.
3. Large part of the job is now done here. I call accumulate() from the standard itertools library to convert the values stored in the data array to the actual value, then I pass its result to max(), to select its biggest value.

On my machine, this algorithm is about 200 times faster that the previous one on test_naive. Enough to pass the HackerRank scrutiny.

Full python code and test case pushed to GitHub.

Go to the full post

How to close a Spring ApplicationContext

I've just finished reading chapter 2 Getting Started of Pro Spring 5. Nice and smooth introduction to Spring, and to Dependency Injection motivation.

Going through the provided examples, I had just a minor on the code provided. In a couple of cases, the created Spring contexts is stored in plain ApplicationContexts reference. This is normally considered a good way of writing code. We don't want to bring around a fat interface when a slimmer one would be enough. Anyway, ApplicationContext has no close() method declared, leading to an annoying warning "Resource leak: 'ctx' is never closed".

Here is one place where you could see the issue, in class HelloWorldSpringDI:
ApplicationContext ctx =
    new ClassPathXmlApplicationContext("spring/app-context.xml");

MessageRenderer mr = ctx.getBean("renderer", MessageRenderer.class);
mr.render();
An obvious solution would be explicitly cast ctx to ClassPathXmlApplicationContext, and call close() on it. However, we could do better than that. The Spring application contexts close()'s come from the interface Closeable. This means that we could refactor our code wrapping the ApplicationContext usage in a try-with-resource block. We let Java taking care of calling close() when the context goes out of scope.

The resulting code is something like that:
try (ClassPathXmlApplicationContext ctx =
        new ClassPathXmlApplicationContext("spring/app-context.xml")) {
    MessageRenderer mr = ctx.getBean("renderer", MessageRenderer.class);
    mr.render();
}
I pushed on GitHub my patched code for both HelloWorldSpringDI and HelloWorldSpringAnnotated, that is, the other class suffering for the same lack of application context closing.

Go to the full post

The Gradle nature of Pro Spring 5

I've started reading Pro Spring 5: An In-Depth Guide to the Spring Framework and Its Tools. It looks fun and interesting. The first issue I had was on having its code from GitHub working in my STS IDE. Here are a few notes on what I did to solve it, if someone else stumble in the same place.

First step was easy. After navigating through the File menu in this way ...
File
    Import...
        Git
            Project from Git
                GitHub
                    Clone URI
I entered the repository address: https://github.com/Apress/pro-spring-5.git

Second step should have been even easier. Add Gradle Nature to the project. It's just a matter of right-clicking on the project, and from the menu select
Configure
    Add Gradle Nature
Unfortunately, there are a few version numbers in the main "build.gradle" file for the project that are not currently working, leading to a number of annoying exceptions like:
A problem occurred evaluating project ':chapter02:hello-world'.
Could not resolve all files for configuration ':chapter02:hello-world:compile'.
Could not resolve org.springframework:spring-context:5.0.4.BUILD-SNAPSHOT.
Required by:
    project :chapter02:hello-world
Could not resolve org.springframework:spring-context:5.0.4.BUILD-SNAPSHOT.
Could not get resource ...
Could not HEAD ...
Read timed out
org.gradle.tooling.BuildException: Could not run build action ...
I tried to minimize the impact of my changes on the original configuration file.

Basically, when I had an issue, I moved to a newer version, preferring a stable RELEASE to BUILD-SNAPSHOT's or release candidates.

I also had a problem for
io.projectreactor.ipc:reactor-netty:0.7.0.M1
That I moved to
io.projectreactor.ipc:reactor-netty:0.7.9.RELEASE
More complicated was the problem for chapter five. It looks that I have something wrong for aspectJ in my configuration. I didn't to spend too much time on that now, assuming that it would lead to to some detail in that specific area. So I opened the aspectj-aspects gradle build file and commented the dependency to gradle-aspectj and the plugin application for aspectj itself.

Now my build.gradle for chapter five - aspectj-aspects has these lines in:
}

    dependencies {
//      classpath "nl.eveoh:gradle-aspectj:2.0"
    }
}
// apply plugin: 'aspectj'
Sure enough, it won't compile. Still, I finally added the gradle nature to the project and I can go on reading the book. I'll take care of that issue when I'll reach chapter five.

I've forked the original APress repository, and there I pushed my variants for the main build.gradle file, and the one for chapter 5, aspectj-aspects. See there for details.

Go to the full post

A thread-safe DateFormatter via ThreadLocal

The exercise 2-b at the end of chapter two from the book Java 8 Lambdas by Richard Warburton asks to wrap a DateFormatter in a ThreadLocal so to make it thread safe.

We have spotted in legacy code, designed to work in a single thread context, something like:
DateFormatter formatter = // ...

// ...

Calendar cal = Calendar.getInstance();
cal.set(Calendar.YEAR, 1970);
cal.set(Calendar.MONTH, Calendar.JANUARY);
cal.set(Calendar.DAY_OF_MONTH, 1);
String formatted = formatter.getFormat().format(cal.getTime());
We know that DateFormatter, a Swing class used to format java util Date, is non thread safe. And now we plan to use this code in a multithreaded environment. We need to refactor it.

If we need to stick to the DateFormatter, here is a possible solution:
ThreadLocal<DateFormatter> formatter =  // 1
    ThreadLocal.withInitial(  // 2
        () -> new DateFormatter(  // 3
            new SimpleDateFormat("dd-MMM-yyyy", Locale.ENGLISH)));  // 4
1. Wrapping an instance of it in a ThreadLocal saves our day, since each thread has its own copy of the variable.
2. Since Java 8, the withInitial() static method let us create a ThreadLocal passing a Supplier that is going to be used to initialize the object.
3. That's the Supplier. Nothing is passed in, and it returns a new DateFormatter.
4. The DateFormatter will be constructed from this SimpleDateFormat built on the fly specifying the format as a string. Notice the second parameter, I want the dates to be localized in English whichever is the default locale.

Job done. Still it would be nice to ...

Switch to java.time

The classes in java.time have been designed for working correctly in multithreading. So, getting rid of Calendar and DateFormatter for LocalDate and DateTimeFormatter, would lead to code simpler and more robust, like this:
DateTimeFormatter formatter8 = DateTimeFormatter.ofPattern("dd-MMM-yyyy", Locale.ENGLISH);
// ...

LocalDate aDate = LocalDate.of(1970, 1, 1);
String formatted = formatter8.format(aDate);
I have pushed the above Java code in my GitHub repository forked from the one gently provided by the author.
Follow the links to see the Question2 solution and its test case.

Go to the full post

HackerRank Java Dequeue

Given n integers in input, consider each window in it sized m, where m is less or equal to n, and get the number of unique elements in each window. Return the maximum value among them.

This HackerRank Java Challenges problem is named Java Dequeue, a clear hint that a Deque would helpful to solve it elegantly.

The HackerRank settings implies that data are passed us by System.in. To develop a method that could be easily tested, I made it accept an InputStream as parameter, then I passed it through a Scanner, in its own try-with-resource block.
public static int solution(InputStream is) {
    try (Scanner scanner = new Scanner(is)) {
        // ... see below
    }
}
The first two integers we expect in the input stream are the above described n and m. A problem constrain states that m is not bigger than n, I make it clear in the code with an assertion.
int n = scanner.nextInt();
int m = scanner.nextInt();
assert m <= n;
Now I should be ready to get the next n integers and work on them. The big hint in the problem name suggests to push them in a Deque. Actually, we are going to use it as a queue. Since ArrayDeque is documented as "likely to be ... faster than LinkedList when used as a queue", my choice goes for it. To avoid slowdowns due to possible resizings, I create it specifying its capacity to the maximum "m" specified by the problem.

We also need to count the items in each window, and to do that a second container is useful. We'll push any item entering the window in a hash table, storing as value its current count. When an item exits the window we decrease its count in the hash. If the count is zero, we remove it.

We are going to call our method many times in a row, and I don't want to create each time a new deque and hash. It is cheaper to make them class data member, and simply reset them any time the method is called.
public class Solution {
    private static final int MAX_WINDOW_SIZE = 100_000;

    private static Deque<Integer> window = new ArrayDeque<>(MAX_WINDOW_SIZE);
    private static Map<Integer, Integer> counter = new HashMap<>();

    public static int solution(InputStream is) {
        // ... see above

        window.clear();            
        counter.clear();
        
        // ... see below
    }
}
Let's fill up the window for the first time. The hash map 'counter' is set up as described above.
for (int i = 0; i < m; i++) {
    int in = scanner.nextInt();
    window.add(in);
    counter.merge(in, 1, Integer::sum);
}

int result = counter.size();

// ... see below
To count how many different integers are in the current window, I simply check the size of the hash map.

Now it is just a matter of iterating on all the other integer in the input stream.
for (int i = m; i < n && result < m; i++) {
    Integer out = window.remove();
    Integer in = scanner.nextInt();
    window.add(in);

    // ... see below
}

return result;
I have started looping on the m-th item, willing to go up to the n-th. But, wait, if I find a window with all different numbers (meaning, the current result is already equal to "m") I have already found the problem solution. That could save some CPU time.

In the loop, firstly I adjust the window, removing its first element and adding a new last element. The exiting and entering elements are used to modify the counter map. Then I recalculate the result, and I check it against the current solution.
if (out.intValue() != in.intValue()) { // 1
    counter.merge(in, 1, Integer::sum);  // 2
    counter.merge(out, -1, (a, b) -> a == 1 ? null : a + b); // 3
    result = Math.max(result, counter.size()); // 4
}
1. If what enters in the window is the same of what exists from it, I don't have to do anything.
2. I merge the item 'in' in the map. That means, if the map contains 'in', Integer::sum is used to adjust its value (on its current value and the '1' I passed in). Otherwise a new item is created in the map, key 'in', value '1'.
3. Similarly to the previous line, but now I'm performing a sort of 'merge down'. I'm not satisfied by this line I wrote, even though it is kind of fun. Its point is that we know for sure that 'out' is in the map, so we know that we are going to execute the lambda passed to merge(). It would return null if the value associated to 'out' is 1, removing it. Otherwise it would return a + b, but b is set to -1, so it would decrease it. The weak spot is, what if for 'out' is not in the map? Well, merge() would push it in, with value -1. Damn it. There is no way to avoid this inconsistency, since merge() would throw an exception if null is passed as value. End of the story is, I would not use this line in production code.
4. Maybe this check-and-set looks a bit too pythonic, what do you think about it?

Full Java code and test case available on GitHub.

Go to the full post

HackerRank Java Sort

We have a Student class, having an int, a String (the name) and a double data member. We want read a bunch of Students from a data stream, sort them by the double - decreasing, then string, and then int. In the end we'll output just the student names.

This apparently boring little HackerRank problem shows how much more fun is Java since functional programming has been introduced in it.

I won't even talk about setting up the scanner and reading the 'count' number of students expected, and I focus here on the action.

Stream.generate(() -> new Student(sc.nextInt(), sc.next(), sc.nextDouble())) // 1
    .limit(count) // 2
    .sorted(Comparator // 3
        .comparingDouble(Student::getCgpa).reversed() // 4
        .thenComparing(Student::getFname) // 5
        .thenComparingInt(Student::getId)) // 6
    .map(Student::getFname) // 7
    .forEach(System.out::println); // 8
  1. The stream comes up by data provided on the fly, reading them from the scanner - named sc. I read an int, a string, a double from it, I shovel them in the Student ctor, that is used in a lambda as supplier for the stream generated() method
  2. I don't want generate() to be called forever, the stream size is limited by the number of students, that I have previously read in 'count'
  3. I have to sort my stream, to do that I provide a Comparator ...
  4. Firstly I compare (primitive) doubles as provided by the Student.getCgpa() method. But, wait, I don't want the natural order, so I reverse it
  5. Second level of comparison, the Student first name
  6. Third level, the (primitive) int representing the Student id should be used
  7. Almost done. I'm interested in just the names, so I extract them by mapping
  8. Loop on the sorted student names, and print each one on a new line

You could get the full Java code from GitHub.

Go to the full post

HackerRank Java 1D Array (Part 2)

Don't be misled by its puzzling name, this fun little HackerRank problem has its main interest not in its implementation language nor in the use of the array data structure, but in the algorithm you apply to solve it.

There is a one dimensional board. Each cell in it could be set to zero (meaning free) or one. At startup the pawn is placed on the first cell to the left, and its job is going out to the right. It could be moved only moving forward by 1 or 'leap' positions, or backward just by one, but only to free (set to zero) cells.

Having specified the zeros and ones on the board, and the value of leap (non negative and not bigger than the board size), can we say if the game could be won?

I decided to use the Dynamic Programming approach, since the problem splits naturally in a series of simple steps, each of them contributing to the solution. There is one issue that muddies the water, the backward move. The rest of the algorithm is pretty straightforward.

  • Start from the last cell in the board.
  • Determine if a pawn could be placed there and if this would lead to a win.
  • Move to the next one of its left, up to the leftmost one.
  • Then return the win condition for the first cell.

Firstly, I create a cache to store all the intermediate values:

boolean[] memo = new boolean[game.length];
if (game[game.length - 1] == 0)
    memo[memo.length - 1] = true;

They are all initialized to false, but the last one, and only if a pawn could go there.

Having set this initial condition, I could loop on all the other elements, in inverse order

for (int i = memo.length - 2; i >= 0; i--) {
    // ... see below
}

return memo[0];

In the end, the first cell of my cache would contain the solution.

Hold on while reading the following "if", explanation follows.

if (game[i] == 0 && (i + leap >= game.length || memo[i + 1] || memo[i + leap])) {
    memo[i] = true;
    // ... see below
}

First thing, check the current value in the board. If it is not zero, I can't put the pawn there, the cache value stays set to false.

Otherwise, any of the following three conditions lead to true in cache:

  • adding the current position to the leap value pushes the pawn out of the board
  • the next cell in the board is a good one
  • the next leap cell is a good one

Now the funny part. When I set to true a cell, I should ensure that a few cells to the right are marked as good, too. This is due to the backward move. It is a sort of domino effect, that should stop when we find a cell where our pawn can't go.

for (int j = i + 1; j < memo.length && game[j] == 0; j++)
    memo[j] = true;

Full Java code and test case pushed on GitHub.

Go to the full post

Partitioning Souvenirs (patched)

Given a list of integers, we want to know if there is a way to split it evenly in three parts, so that the sum of each part is the same than the other ones.

Problem given in week six of the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego.

My first solution, as you can see in a previous post (please check it out for more background information), was accepted in the MOOC but didn't work in a few cases, as Shuai Zhao pointed out.

So, I added the Shuai test case to my testing suite, and then a couple of other ones, that I felt would help me in writing a more robust solution:
def test_shuai(self):
    self.assertFalse(solution([7, 2, 2, 2, 2, 2, 2, 2, 3]))

def test_confounding_choice(self):
    self.assertFalse(solution([3, 2, 2, 2, 3]))

def test_duplicates(self):
    self.assertTrue(solution([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]))
Firstly, I rewrote the initial check, that now looks in this way:
def solution(values):
    third, module = divmod(sum(values), 3)  # 1
    if len(values) < 3 or module or max(values) > third:  # 2
        return False
1. Add up the passed values, our target is its third, and surely we can't split it there is a remainder after the division. Using divmod() we get both values in a single shot.
2. If we have less than three values in input, a remainder by dividing their sum by three, or if there is a value bigger than a third of the sum, our job is already done.

Then, since I saw that the problem was due to the lack of check in the ownership for values, I added a shadow table to the one I'm using for the Dynamic Programming procedure. I named it 'taken', and it keeps the id of the owner for the relative value for the current row. Zero means the value is currently not taken.
table = [[0] * (len(values) + 1) for _ in range(third + 1)]
taken = [[0] * (len(values) + 1) for _ in range(third + 1)]
As before, I apply the standard DP procedure, looping on all the "valid" elements.
for i in range(1, third + 1):
    for j in range(1, len(values) + 1):
        # ...
Another not a substantial change, it occurred to me that I keep track of a maximum of two positive matches in the table, so, if I have already reached that value, there's no need in doing other checks, just set the current value to two.
if table[i][j-1] == 2:
    table[i][j] = 2
    continue
The next check was already in, I just refactored it out, because the combined if clause in which it was included was getting too complicated, and I added the first use of the taken table.
if values[j-1] == i:
    table[i][j] = 1 if table[i][j-1] == 0 else 2  # 1
    taken[i][j] = j  # 2
    continue

ii = i - values[j-1]  # 3
1. If the current value is the same of the current row value, I have found a match. So I increase its value in the DP table
2. And I mark it as taken for the j value in the current row.
3. If j is not an exact match for i, I split it, looking for the difference in the previous column.

Now it's getting complicated. If there is a good value in the previous column, before using it we have to ensure it is available. And, since it could have been the result of a splitting, we need to check on the full row to do our job correctly.
available = True
taken_id = taken[ii][j-1]  # 1
if taken_id:
    for jj in range(1, j):  # 2
        if taken[ii][jj] == taken_id:  # 3
            if taken[i][jj]:
                available = False
                break
1. The current value id from the taken table is zero if was not used in the 'ii' row.
2. If the current value has a valid id, we need to ensure it has not be already used in current 'i' row.
3. The current jj is marked as used in the ii row for the id we care about, if it is taken also in the i row, we have a problem. We are trying to using in 'i' a value that has been already used. This was the check I missed.

Good, now I can safely going on with my DP algorithm.
if ii > 0 and table[ii][j - 1] > 0 and not taken[i][j - 1] and available:
    table[i][j] = 1 if table[i][j - 1] == 0 else 2
    
    // ...
The annoying thing is that I have to set the taken table too:
taken[i][j] = j  # 1
taken[i][j-1] = j

matcher = values[j-1] + values[j-2]  # 2
if taken_id:
    for jj in range(1, len(values)):  # 3
        if taken[ii][jj] == taken_id:
            taken[i][jj] = j
            matcher += values[jj-1]
if matcher < i:
    for jj in range(j-2, 0, -1):  # 4
        if taken[i][jj] or matcher + values[jj-1] > i:
            continue
        matcher += values[jj-1]
        taken[i][jj] = j
        if matcher == i:
            break
1. This is nice and simple. The current j and the previous one should be marked as j.
2. We have to mark all the other values concurring to generate the current sum. These are two just marked 'j' on this row, all the ones marked as stored in taken_id on 'ii' and, if they are not enough, also the ones free on 'i', to the get the expected result. To perform this last check I need another variable, that I called 'matcher'.
3. Mark on 'i' as 'j' all the items marked taken_id on 'ii'. And adjust matcher.
4. If needed, loop on the left elements looking for the missing values.

And finally:
        # ...
        else:  # 1
            table[i][j] = table[i][j - 1]

return True if table[-1][-1] == 2 else False  # 2
1. This 'else' follows the 'if ii > 0 and ...' above, ensuring the current cell is adjourned correctly if nothing else happened before.
2. The bottom right cell in our DP table should be set to 2 only if we find a correct 3-way split.

See full python code and test cases on GitHub.

Go to the full post