(task | solution)

This is the kind of task I really enjoy: finding algorithms for simple mathematical challenges! Let’s go—this time in… C++! (Phew!)

You’ll find my .devcontainer and Dockerfile on GitHub. Once again, I don’t want to bloat my system with additional compiler setups. It turns out, this is working like a charm.

Solution to the First Part

Well, the idea is quite easy: We got a list of operands and need to find the correct combination of + and * to get a target result. What we basically need to do is: Loop through all given equations, get all possible permutations of + and * for n given operands, and then do the math.

The first tricky thing here is: They are providing a lot of huge numbers. So using 32-bit integers isn’t sufficient. You not only need 64-bit integers, but also unsigned to work with numbers like 175.033.602.122.656.

But they also hid a little pitfall in the list of possible equations: There is one (exactly one!) duplicate entry. Which makes it hard to find. Would it be ten, 42, or 100 duplicate entries, you would somehow stumble over it. But now it took me a while, and I was close to throwing this task away. I started debugging and I wondered why I am only processing 849 equations instead of 850. At first glance, it looks like one of those classic “indexing starts at zero” bugs. But then I did, what you usually do when filling dictionaries: You check if the entry you want to add already exists. And it does.

And while this wouldn’t lead to a valid equation…

1095: 8 5 9 3 231

This line certainly does

1095: 8 1 2 7 95 8 2 7 2 2 99

And so I found the missing value for the final result…

Solution to the Second Part

Well, the second part took me a while because I was somehow trying to build this concatenation part into the current algorithm. We now have three operators, *, +, and || — but the last one should connect two integers.

Eventually, I had my heureka moment: Concatenation could be implemented as a mathematical operation, too.

If the left number is 123 followed by 45, we need to multiply 123 with 10^2 and then just add 45. Easy math.

Side note: I was cheating a little. I now know that 1095 is a duplicated entry, and I know it would lead to a valid result, so I am adding it hard-coded to get the final result.

Whats up, C++?

Rating: 6/12 – painful

Well, C++ is undoubtedly a powerful language, but for a reason it’s not beating all those scripting languages out there. Simple things are complicated because you have to implement them on your own. 5 out of 12 seems to be unfair for such a grown-up programming language, but this is simply my point of view. For me, right now, there’s no reason to use C++. Which absolutely does not mean that this language is not important! Nevertheless, using it felt like an adult pro developer. ;)