I used to enjoy solving optimization problems in the collage. Then I graduated and moved from one webdev job to another and I realized, that there is not a lot of computer science in webdev. I think it's more of a architecture oriented field, which is not bad, just ... I sometimes miss a good brain twister. However, I came across a task, in work, that required me to solve a subset sum problem. I did not know that, it was a subset sum problem at a time. I tried to apply some greedy algorithm, which was good enough, so I considered this task done.
Few weeks latter I came across the same code and I found a combination of inputs that would result in a wrong answer. Well, that's what you get by implementing a greedy algorithm, I thought, but I wasn't satisfied. The combination of inputs, was so primitive, that I had to search for better solution.
I knew there was a perfect solution: run trough every combination. Not a great idea because of a thing called exponential growth. You know, the thing that gets crazy big really fast. So, could an optimal algorithm, computed in a reasonable time, be reached?
I searched around and found a wikipedia page about subset sum problems. Subset sum problem is a problem of selecting a subset of items which sum equals to some integer. In general, the solution for this problem assumes, that items in subset cannot repeat. However, my problem could repeat items from the set of items. I updated my search query to subset sum with repetition and there are other people wanting to solve the same problem as I do. However, I could not find any wikipedia page on this one.
I read trough stackoverflow questions, various articles and came back to the original wikipedia page. Some sources were useful some less. In the end I came across a pseudo code for solving subset sum. To be honest, pseudo code got me good. After a lot of years of webdev work I realized, that my ability to follow pseudo code is much worse then during my collage years. Once I got a feel how to solve this problem with dynamic programing I implemented it, wrote tests and wrote documentation.
It took me a week or so, to finish the dynamic programming algorithm, because I was doing it outside my work hours, but it was really an enriching journey.
👉 Moral of the story is, try to solve a computer science problem once in a while. It is so refreshing after months of parsing json and communicating with APIs. It also showed me, that my skill to read technical documentation is not as sharp as it used to be.
👉 Experiment and try some new technology or development technique. For example I tackled this problem with TDD and I have to say, it was a perfect tool for this kind of a job. Job where you can define specific examples for inputs and outputs.
👉 Also, if the problem is small enough, write a documentation and try to explain the problem and your solution. This activity can also show you that you still have some gaps in your knowledge. Writing an understandable documentations, is much harder then it seems. It made me appreciate docs, that are easy to follow, more.
You can also plot effectiveness of this solution against running trough all combinations. You may find some interesting results.
Of course, I put my code on github.
Top comments (0)