A very common unanswerable question I see on StackOverflow is of the form “my CS homework assignment is to solve problem X and I don’t even know how to get started. How do I get started?” That’s too vague and unfocussed for a site like StackOverflow, which is for specific technical questions that have specific answers.
My recent post on the similarly vague problem of how to debug small programs has gotten a lot of hits and great comments; thanks all for that. In light of that I thought I might do an irregular series each highlighting some basic problem-solving techniques for beginner programmers, CS students and the like.(Of course these apply to expert programmers too, but expert programmers often already know these techniques.) So, how do you get started?
Pólya famously said that the way to solve the problem was: (1) understand the problem, (2) come up with a plan, (3) execute the plan, and finally (4) review your work. It’s that second step that concerns me today; if you don’t understand what the problem is even asking you to do then get some clarification from your instructor.
I see a lot of beginner code that was clearly written with no particular plan in mind. But making a plan is itself a problem; how do you attack that problem?
One of my favourite techniques for doing so is to again take the advice of Pólya:
If you can’t solve a problem then there is an easier problem you can solve. Find it.
What good is that?
- The solution to the simpler problem might be adaptable to solve the harder problem. Now you have a plan: solve the easier problem, look for an adaption.
- Conversely, the inability to adapt the simpler problem to the harder problem might shed light on precisely what makes the harder problem harder. Come up with a plan to tackle the specific thing that makes the problem harder.
- Solving simpler problems that you know you can do is good practice and builds confidence. And you’re more likely to be successful if you start with code that already correctly solves a problem.
- If you fail to solve the harder problem you can always submit the solution to the simpler problem for partial credit.
Let me give you an example. Suppose your homework assignment is to build a lookup mechanism mapping one million English words to their definitions. You are required to implement the lookup as a binary search tree optimized such that the most commonly looked-up words are always close to the root of the tree. And suppose you don’t know where to begin. Here’s one path you could go down to simplify the problem:
- Solve the problem for a dictionary of ten words. Scale it up from there, or figure out why your solution does not scale up.
- Maybe that’s still too hard. Build a binary search tree lookup mechanism that maps ten words to definitions that is not optimized. Once you’ve got that, try to figure out how to optimize it.
- Maybe that’s still too hard. Build a binary search tree lookup mechanism that maps ten integers to integers that is not optimized. Then later figure out how to replace the integers with strings.
- If that’s still too hard, can you build a binary search tree just of single integers, with no mapping? Add the mapping later.
- If that’s still too hard, can you build a binary tree just of single integers even if its not a search tree? Make it a search tree later.
- Can you build a linked list of integers?
- How about an array of integers?
- Can you write “Hello world” in this language?
It might sound a bit silly to go that far, but it’s not. When you’re writing twenty-line programs for assignments every program begins its life as “Hello world”. In industry that’s not the case; the number of times I’ve started new shipping code from a blank page and written static void Main(){ is exactly one, and even that was a rare privilege. Almost all the code you write for assignments will start from “Hello world”, so get good at writing it.
There are lots of ways to make a problem simpler; I already mentioned:
- Decrease problem size requirements.
- Neglect optimizations.
- Simplify data structures.
But there are lots more ways to simplify a coding problem. For example:
- Reduce dimensionality. If you have a problem about drawing rectangles can you reduce it to a problem about drawing lines? Or even points?
- Cut features. If your problem requires reading a dictionary file from disk, instead hard-code the strings into your program.
Readers, what are your favourite general techniques for reducing the complexity of a problem?
Fabulous adventures in coding 
Quite obviously, rising from what you wrote above – perhaps the problem can be solved with recursion. Identify base cases to the problem and solve those trivially. Then allow a recursive algorithm to break the problem into enough smaller chunks that they eventually match one of the base cases. Then combine the results.
Indeed, I thought this was what Eric’s article was going to be about.
A “hard” problem pretty much always is really a collection of easier problems. Just as navigating cross-country is really just a matter of navigating between shorter intervals that together make up an entire cross-country trip, so too hard problems are really just a bunch of easier problems put together.
Some of the time, an “easier” problem is the requirement for study and research. I.e., you need to learn something new. But even there, that’s simply an element of figuring out what easier problems make up your hard problem.
If you don’t know how to solve the hard problem A, the first step is finding the parts that can be described as “well, if I knew how to do B, C, and D, then I’d be able to solve A”. Either you know how to do B, C, and D — in which case, you’re golden — or you don’t. If you don’t, then you deconstruct the ones you don’t know further.
Fact is, except maybe for the most brilliant or the savants, none of us can do a truly hard problem as a single unit. The average human brain just can’t keep that much stuff in active working memory at a time.
And we see this in programming all the time. If you try to implement your program as a single big method, you’re doomed. If it works at all, it will be impossible to understand and maintain. Successful programmers break their programs into small, comprehensible pieces, preferably in ways that are independent of each other.
It’s all the same!
The problem comes when someone who doesn’t really understand the overall problem breaks it into parts B, C and D, where B and D are easy to solve, and C is impossible (or maybe just extremely unwise or inefficient)
This is a fantastic post, and I hope to see the future ones!
On my blog, I also wrote a post about rules for problem-solving, or more accurately for figuring out how to read math papers (then tried to generalize to the real world). My advice was as follows:
1) Understand notation for what it is. If you’re given a task, know that the words and notation they use may have specific meanings, so you have to understand them from the very beginning or else it’s too easy to get lost. Notation is almost everything when it comes to math paper, and understanding the words used in communication is in the real world.
2) Break everything up into much smaller tasks. Look for a natural order to solve those tasks in (looking at dependencies and such), then make sure that, when you’ve completed one task, you look back at it and truly understand how it works so that if a future piece depends on it, you understand what could go wrong.
I know that sounds like more of a rehash of what you wrote, but it’s how I learned about the Pumping Lemma and began to understand what it means to be a “regular” language. For anyone interested, the link to that post is here:
http://thecappsblog.blogspot.com/2013/10/on-problem-solving.html
That’s not one of the finest efforts in problem definition I’ve seen you come up with, Eric. (And I speak as one who is still staggered by the A*/Sudoku posts.)
First step: analyse the problem. Is it intractable with limited space and time? Hardly. Is it likely to fail when scaled? Again, dubious, given the fact that this is a natural language requirement.
Go find a suitable O(logN) algorithm. A Patricia Tree springs to mind.
(Also, incidentally, consider the source of the request. If it’s a Web page, you can let the client do the basic hashing for you.)
That’s not a requirement. It’s micro-management.
That’s not a requirement either. The requirement would be something like “the top ten thousand popular definitions can be accessed at a cost of N, for some suitable unit value for N.”
I maintain that a simple Dictionary would do the trick. Failing that, a Patricia Tree would be fine.
And if the requirement is to beat the simple solution handily (again, by a ratio of N for a set S of weighted inputs), then measure, measure, measure.
It’s unlikely you’d need it, but you could implement a cache on top of the lookup. Do that and measure again.
My take on this is sorta “don’t listen to people who tell you what the requirements are…” Well, obviously, not quite that. But talk about the requirements first, before diving in.
You might have missed the point of this entire post Peter. The post is to help students who post their homework assignments to StackOverflow because they can’t get started on them. The problem I give as an example is a near-verbatim statement of a real homework problem that a CS student posted on SO a few days ago.
The point of such an assignment is not actually to solve a real-world problem, and it is likely being given as the precursor to a lecture on splay trees. Criticizing the problem statement or suggesting that it be negotiated with the client is a non-starter; the “client” is the professor who is trying to teach the student how to manipulate binary trees, not someone who actually needs a dictionary built.
I might, I might; I accept that.
My claim is that, in terms of a real-life problem, this is not a very good example. Well, hang on, it’s a very good example.
Why? Because my main thrust is that you should examine the requirements first, and consider the solutions second. The fact that the “client” is a professor who will go on to explain splay trees is not relevant, and IMHO damaging for the 80% of klutzes like me who will proceed to real-world problems where, quite frankly, an analysis of the requirements is exponentially more useful than being directed towards the next step in the course.
I would suggest that this example is more to do with poor teaching (why not just go straight on to splay trees? Why torture your students) than it is to do with your ostensible (and I must say very welcome) goal of teaching IT graduates how to “think” about problems.
Or, to put it another way, the student’s “client” is most likely to respond to a sub-optimal implementation of artificial requirements by saying “Ha ha! I expected you to use a splay tree! (Or whatever.)
I see no didactic value in this whatsoever. I will continue to claim that the requirements are ill-posed.
I had a few of these kinds of questions when I was a student, and I disagree that they are bad assignment questions.
However, whether they are or not, the student has little or no ability to change or refine the question, or go back to the lecturer to get a better statement of requirements. The lecture probably has a thousand people in it and the lecturer isn’t going to spend time one-on-one with individuals.
But this article isn’t about writing good assignment questions, and it isn’t aimed at lecturers. It’s for the student, who is tasked with answering the question as-is. Eric was perfectly clear about the intent here.
But the goal from the description clearly was to come up with some kind of rebalancing tree (and no, Patricia trees wouldn’t solve the given problem to begin with; also there are no artificial limitations in the instructions that would limit you to implement a good solution) to begin with!
Now you may argue that it’s “torture” to force your students to try to come up with some idea for this themselves instead of frontal teaching them the “correct” solution, but in my opinion that’s the best way people actually learn things.
After they spent some time thinking about the problem and trying different things, they’ll have a much easier time understanding the preferred solution and its pros and cons.
There was no indication that the question was posed to the students before the relevant material was taught. I think it’s far more likely that the question is part of an assignment to review the previous module of work. That’s how it always was for me.
This is awfully general, but another useful approach is to divide the problem into multiple steps, then solve just one of them.
So suppose you need to build a lookup mechanism mapping words to their definitions based on a particular XML file containing words and definitions.
(1) Read the word::definition data from the XML file.
(2) Perform lookups.
You could then start by coding (1): write code to read the idiosyncratic XML file. Or you might start with (2): perform a lookup on data that was just hard-coded into the source code.
Both are needed, and you can often get started by picking whichever seems easier to you. True, an advanced programmer might allow the design of one to impact the other: perhaps because of the design of your lookup table you can use a pull-dom for reading XML will enable you to avoid processing the entire file in most cases… but if you were an advanced programmer then you wouldn’t be stuck. Solving the pieces in isolation and then putting them together often works well. And many problems can be broken down into many more than 2 steps.
(Oops, forgot to highlight that the problem space in this case is generally invariant. That’s to say, the lookup is probably 999 reads to one write. Which is also an important issue, obviously.)
I may have grown too pragmatic. Ten years ago I’d actually be thinking about the problem, now all I can think is “Dictionary<string>.”
Or <string, string> for those who care about little details like whether it compiles…
🙂
I like to simplify problems with an oracle.
The Oracle just knows the answers to the hardest part of the problem. The easiest oracle to write looks like
Console.Writeline(Question);
Console.Readline(Answer);
The oracle might be a hard coded answer (based on knowning what the inputs will be.) Sometimes the oracle is just an algorithm that is too slow for production.
Over time the oracle knows less and less because the production code computes more and more.
That’s a good idea, thanks!
I’d add to each item in the list of successively simpler problems, “and if not, can you at least write pseudocode to do it?”
In the real world, if I don’t know where I’m going I would either consult or write a design document. Assignment questions are too simple to require them, but a pseudocode version of the algorithm serves the same purpose.
This would help better with the “understanding the course material and concepts required to solve the problem” side, not the “starting with a big screen of whitespace, how do I start writing code?” side, which the article already covers well.
Also, seriously, what IDE were you using that one time you did write a Main method? Even Visual Studio can write that for you.
I usually can’t even remember what the arguments are supposed to be in whatever language I’m coding in, since I read it once in the language spec and never, ever need to do it.
Unfortunately, some people love to give interview questions like “write a program to do [some simple task]” which requires writing a main, in order to prove you are not a complete muppet.
One lady I knew (well, my ex-wife) once complained to me about her inability to use any of the fancy formulae she had memorised from the textbook on physics to solve any real-life problem: she would not see any connection between the ‘abstract math’ of the book and the ‘normal’ real-world problem…
The point I’m making is: you don’t tell someone who asks your help that not everyone is made to be a programmer; is there a ‘diplomatic’, ‘politically correct’, etc., way of saying it? Anyone?
Besides, problem-solving, including breaking down a complex issue into simpler parts, seeing similarities between different cases, and being able to reason from the abstract to the specific and vice versa is not just a programming skill: it’s a general life skill. If people lack it, what’s wrong with the world?
And finally, another story (don’t know if it’s true or not): a young compozer comes to Mozart and asks him to explain how to write symphonies. Mozart says, you’re young, my firend: why don’t you start, say, with ballads? The youngster says, ‘But you’ve written your first symphony when you were only 7!’ And Mozart says, ‘Yes, but I haven’t asked anyone how to do it.’
For me personally I always start by breaking down my problem into small chucks by making comments for example
//1. declare collections object
//2. load values into collection
//3 search collection for specific values.
But I always try to make my comments generic so that I can easily scrap the code that I have written and start again with a different strategy.
But if the problem I feel is complex I always start with a pen and paper to try and come up with some approaches
I do that too. As well as being a good way to sort out the ideas in your head, it’s great value if you get interrupted and have to pick up the task a little later.
Also, you wind up with clear, documented code.
Pingback: Dew Drop – March 24, 2014 (#1749) | Morning Dew
I’ve found that the best help to me is building a set of general design principles to support the use of unit testing. There are any number of buzz words for it, but it’s the simple act of decomposing the problem into a set of atomic, encapsulated, and (a personal preference of mine) stateless operations, where possible. I then write unit tests against those operations, and more often than not I write unit tests against compositions of those operations. This process builds productive code and unit tests (woo hoo!), all while helping me get a better understanding of the problem scope as a further compose those operations (in unit tests) into an increasingly complete solution.
I love it when people to this.
Particularly because writing for the unit test encourages you to think about error cases more – since you are going to write a method failure test case in ten minutes anyway, you consider what happens when the method fails, and chuck an exception or return code or whatever in there.
I’ve seen plenty of code where this didn’t happen, and complex operations just don’t tell the caller if something went wrong, leaving code effectively untested and problems difficult to diagnose in the field.
Or as René put it so well:
…”The first was never to accept anything for true which I did not clearly know to be such; that is to say, carefully to avoid precipitancy and prejudice, and to comprise nothing more in my judgment than what was presented to my mind so clearly and distinctly as to exclude all ground of doubt.
The second, to divide each of the difficulties under examination into as many parts as possible, and as might be necessary for its adequate solution.
The third, to conduct my thoughts in such order that, by commencing with objects the simplest and easiest to know, I might ascend by little and little, and, as it were, step by step, to the knowledge of the more complex; assigning in thought a certain order even to those objects which in their own nature do not stand in a relation of antecedence and sequence.
And the last, in every case to make enumerations so complete, and reviews so general, that I might be assured that nothing was omitted.”
http://en.wikipedia.org/wiki/Discours_de_la_methode
I’m not advocating waste, but I have been told that paper is cheap… In regards to your statements about breaking a problem down into its parts, its important to document the breakdown someplace besides inside your own head. Writing it down gives me a chance to review my thoughts and refine them.
I keep a notebook at my desk all day long while I program doing exactly what Eric stated in the article, breaking problems down. As I complete portions of the problem, I can check them off and see progress. I’ve been developing software for over 10 years, and the paper technique along with breaking down problems helps me get work done faster.
Hogan
These techniques are related to what Pólya advises “If you can’t solve a problem, then there is an easier problem you can solve: find it.” Or “If you cannot solve the proposed problem, try to solve first some related problem. Could you imagine a more accessible related problem?”
“Simply” put, Complex problems are composed of smaller “simpler” problems. It’s also analogous to learning “difficult” subjects. We start to tackle them by first learning simpler concepts for if we start learning complex issues first we would never understand them.
I like to start with what’s new. A recent workflow monitoring application had to respond to events as they happened. Most of the app I’d done many times before – database, web front end, logging, audit, recovery etc. What was new was the data push. Once I’d written the bare minimum to get a string from source to destination (“Hello World”, as it happened) I knew the project was a goer. All the other stuff could be added to that.
For a student this may translate as “Does this look like a previous assignment but with X instead of Y?” If so start with the solution to that problem. If the lectures preceeding this assignment covered, say, trees in depth, you’ll want to focus on using trees in the solution. Start by investigating how trees could be used in this context. Add the stuff about “one million” and “optimized” once the “tree” bit is operational.
Page great reduction in complexity is to throw out the problem of writing things in a programming language. Do not use an editor and a compiler, but use a white board, magnets, paper clips, a hand full of pencil sharpeners or whatever it takes to make you understand what the problem is and how an algorithm solves it.
In the given dictionary problem, using pieces of paper with words on them and using your fingers as pointers, may make you understand the problem much better.
Pingback: Os 10 melhores links de 2014 - André Alves de Lima
Pingback: Logic Building Part 2: Bigger Problems to Smaller Ones! – Learn Coding Basics!
Pingback: Problem Solving Rules 3: Simplify – Marks in the Sand
Pingback: 从链表中删除节点，LeetCode，超出时间限制错误。 | 开发者交流平台