Ask HN: How do you solve hard problems if you can't make incremental progress?

http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-solvers.html

by ntoshev • 16 years ago

65 48 16 years ago

ravimohan.blogspot.com

vital101• 16 years ago

I generally try to step away from the problem for awhile. Even if it's only for 10 minutes. I come back with a fresh perspective that usually helps me get through it.

thecombjelly• 16 years ago

I try to attack the problem persistently and creatively. Often I will walk around and just ask random people what they think. Sometimes even describing the problem in non technical terms for the non techies to understand. People usually have some ideas that you haven't thought of. I've found that any idea can set you off on a path to solve the problem.

kmak• 16 years ago

The part I don't understand is, for this particular problem, it is well-known enough that a simple visit to Wikipedia would've been enlightening.

I remember reading up on it awhile ago, and it seems like the Wikipedia entry already had the dancing links algorithm by then.

ntoshev2• 16 years ago

I have a programming problem, and I'm pretty sure I'm aware of the basic components of the solution... it's just that I get swamped in complexity pretty quickly when I try out different combinations.

I know this is a very meta question but this is not the only case. I'll solve it eventually but I'd like to ask for common strategies.

Edit: Some of my strategies are: to absorb more information about similar stuff while I put solving it on back burner, to try to describe the problem clearly, to bounce the problem off other people.

-------------------------

Okay, here is the specific question: I have a map of categories of things (a few words) and descriptions what these categories mean (longer text). I also have another list of category names that sometimes uses different words or abbreviations, and I need to match the second list to the first one precisely.

I know all about tf-idf, vector space similarity between a document and a term, wordnet as a source of semantic relations between words, and it's ok to have a human map some of these. The problem is I don't know when a matching score is good enough and when I need to fall back to a human.

sandaru1• 16 years ago

Use Levenshtein distance - http://en.wikipedia.org/wiki/Levenshtein_distance

ntoshev2• 16 years ago

Thanks, my boolean approximation for abbreviations so far is:

  def abbr(short, full):
      return re.match(''.join(c+'.*' for c in short), full)

Actually what I'm doing now seems to be working, so far I can't see any pattern in the things my algo can't match by itself.

Also thanks to ramanujan, who deleted his comment for some reason, but besides pointing out orgmode which I want to check, his proposition reminded me that I'm trying to deal with my dataset incrementally while a batch mode might work better.

NEPatriot• 16 years ago

I look for inspiration from the world around me and focus on trying to always find the simplest solution with the least resistance.

dwwoelfel• 16 years ago

Use Poyla's methods of problem solving described in his book: How to Solve It (http://www.amazon.com/o/ASIN/0691023565)

He deals specifically with mathematical problems, but the same ideas apply to computer science.

For an outline of the method see this Wikipedia article:

http://en.wikipedia.org/wiki/How_to_Solve_It

RodgerTheGreat• 16 years ago

And if you're specifically trying to design an algorithm, you might look into "How to Solve It by Computer" by R.G. Dromey, which was inspired by the former:

http://www.amazon.com/Solve-Computer-Prentice-Hall-Internati...

josh33• 16 years ago

This is very high level, but: take a step back and remember who it is you are trying to serve/help with the problem you are solving. If it is a particular market/industry, often the answer can be found by trying to focus on how to help them than by trying to solve a problem. I think there is something about focusing on a problem that makes it bigger, whereas focusing on a solution can make the solution more evident.

gridspy• 16 years ago

I often find it instructive to solve a simple example problem by hand. This can give you the insight needed to solve it computationally

gfodor• 16 years ago

There are multiple meanings of incremental progress. Just fleshing out a test suite is only one means of defining progress.

Goladus2• 16 years ago

Avoid stress and distractions. Do not multitask. Take breaks to eat (healthy foods), exercise, and sleep. Feel free to discuss the problem with friends and colleagues but minimize emotional investment with other people. Read books and articles on the subject. Study existing tools and study similar problems. If you can't make incremental progress on a solution you can incrementally increase your chance to solve it all at once by getting smarter and getting better tools.

No facebook, television, hacker news, video games, twitter, dating, drinking.

I would not say this is a particularly healthy lifestyle in the long run. When possible incremental progress will make it easier to live a happy fulfilling life. But if you really need to solve something...

wisty3• 16 years ago

Multi-tasking can be OK ... depending on the person. Some people love it, some fall apart.

But yeah, "Avoid stress and distractions. Do not multitask. Take breaks to eat (healthy foods), exercise, and sleep. Feel free to discuss the problem with friends and colleagues but minimize emotional investment with other people."

I'll add:

Make progress, even if it's not progress. I teach english. If my students are stuck, I tell them to answer the question in their native language. Or just guess. Or say something that isn't even relevant. There are 3 reasons why I say this: 1) you look busy, so your boss will be happy, 2) you feel better and might subconsciously clear the block just by not stressing over it, and 3) you start filling in the jigsaw pieces around the block, which might make the solution easier to reach.

timwiseman2• 16 years ago

Research has repeatedly shown that virtually no one can multitask effectively (http://arstechnica.com/old/content/2006/03/6417.ars has a laymen's summary of some for one place).

The closest thing to an exception I know of is listening to music. I will listen to music while working on hard problems, but then I tend to choose music I know well and I use it to block out more distracting sounds rather than pay much attention to it.

myth_drannon• 16 years ago

TRIZ - http://en.wikipedia.org/wiki/TRIZ -"TRIZ is a methodology, tool set, knowledge base, and model-based technology for generating innovative ideas and solutions for problem solving."

Generations of Soviet engineers were educated on that methodology. Many western companies use it as well.

wisty3• 16 years ago

I don't know much about TRIZ, but it seems the core idea is to "look for trade-offs, and find a creative way to avoid them". It also has a lot of general problem-solving tools .... but most methodologies do.

jhg• 16 years ago

Woah... "Creativity as an Exact Science". TRIZ needs to be submitted to HN as a separate item. It can make for one interesting discussion.

mikexstudios• 16 years ago

Good idea. I just submitted it: http://news.ycombinator.com/item?id=1222192

smallhands• 16 years ago

Why not pay somebody to solve it!!!!.

brk• 16 years ago

I don't know why this comment is being modded down, this is a good idea (IMO). Maybe not always possible in every scenario, but worth considering.

I've been doing more things with mturk, elance, RAC, and so on lately. For a recent tradeshow we did I had someone on elance doing a short video production for me for $150. The money was a no-brainer and allowed to concentrate on other stuff. I also hired someone on elance (for $500) to write an xcode framework for me for an iPhone app idea. I could probably figure it out myself, but (I'm hoping) it will be easier and more efficient to get started in iPhone app programming by having someone more knowledgeable than I put together the basics so I can see how it's done. (Yes, I know there are a ton of xcode examples on line, I just wanted something specific that I could build off of).

Depending on the price/problem, outsourcing a solution might be an excellent use of time/resources, and may also teach you something new seeing how another person tackled the issue.

sfk• 16 years ago

"I don't know why this comment is being modded down, this is a good idea (IMO)."

Because some people do not think about everything in monetary terms.

anigbrowl2• 16 years ago

Because the probability of success asymptotically approaches zero as each vendor tries out the same idea and offers slightly less for the solution :)

oomkiller2• 16 years ago

I'm not sure if I'm unique in this regard, but I seem to have the ability to fully visualize complex systems and problems. The key for me is understanding the problem fully, as I have to pull all of the pieces together. I find it difficult sometimes because other people aren't used to working this way, so they try to feed you bite-sized pieces, where what I really want is the entire problem.

anigbrowl2• 16 years ago

You're not, but as you say this approach imposes its own difficulties. A piecemeal approach often, though not necessarily, gets faster results.

jacquesm3• 16 years ago

Could you put some lower bound on what you consider 'complex' ?

It seems a bit of an outlandish claim to make without a reference point, what's complex to you may be simple to others and vice versa. So a bit of extra data as to the kind of complex systems and problems you visualize would help.

oomkiller2• 16 years ago

Sorry if it seems outlandish, I'm not really sure how quantify "complex". One personal example though is I designed a national emergency management network (Utilizing XMPP/PubSub, AMQP, Rails, etc) in my head without writing anything down. That may seem special or it may not, I just find it rare, at least in my (diminutive) peer group. I've also designed all of these huge dreamy systems growing up, I have pictures and diagrams I drew in 5th grade :) They sure are funny to look back at!

diN0bot• 16 years ago

norvig actually does make incremental progress in understanding the problem/solution space in terms of constraints, bounds and correctness.

michael_dorfman• 16 years ago

Many (perhaps most) hard problems don't need to be solved from scratch; rather, it is a matter of applying a well-known solution that somebody has already found.

The example in the article is a good one: there's absolutely no need to attempt to design a Sudoku-solving-algorithm from scratch (except as an exercise), and it is pitiful to see Ron Jeffries flailing around aimlessly in TDD-land when a simple trip to Google would have done the trick.

The difficult part, the part that comes with experience, is recognizing which class of problems the specific problem you are grappling with resembles. In the case of Sudoku, it's an "exact cover problem", and once you realize this, all kinds of solutions present themselves.

In this way, the "incremental progress" is not made on attempting to solve the problem incrementally, but by incrementally sifting through probably solution-spaces for known algorithms.

blizkreeg• 16 years ago

Well said! Few hard problems are solved entirely from scratch, unless it is to boost one's ego. In almost every field, the key is to identify problems with similar patterns or constraints.

msie• 16 years ago

The link mentions a Norvig-Jeffries showdown on writing a Sudoku solver. Kinda unfair since Norvig pretty much wrote the book on it. :P

andrewcooke• 16 years ago

yeah, i think this needs to be better understood. norvig was not "solving" much of anything there. he was simply writing out a solution for a problem he had solved many times before.

that doesn't mean he's not a smart guy, but it's wrong to infer, from comparing those articles, that he doesn't make mistakes.

kvs• 16 years ago

How about solving related or similar problems? The way one may approach those problems may give insight into incremental steps necessary to solve the hard problem.

Tichy• 16 years ago

Isn't the Norvig solution completely straightforward? Just the basic back propagation algorithm?

So maybe in some cases it just helps to read the literature a little bit...

For example at the Google Code Competition (forgot the proper name), I am not very good, but I learned some things from reading solutions of older competitions. I think there even is a book dedicated to solving that kind of problem. It would probably help a lot with writing a Sudoku solver, too.

Edit: not to take away from the Norvig solution, it is probably beautifully crafted. But come on - it IS the straightforward solution? Or what am I missing?

jacquesm3• 16 years ago

Explain the problem to someone that doesn't know anything about it.

Usually that 'clicks' at some point and I realize what I'd been missing all along. The less the person knows about computers/programming (my usual subject matter) the better it seems to work.

andrewljohnson2• 16 years ago

This "rubber duck" strategy is great for debugging too.

One person plays the rubber duck and sits there and says (at most) "uhuh, uhuh" while the programmer with the bug explains the problem. Nine times out of 10, the bugged programmer will do a facepalm and fix the bug immediately while explaining the problem.

You actually don't need a person at all for this, or a rubber duck... just the willingness to explain your bug aloud to yourself when you have one.

jacquesm3• 16 years ago

That's a really funny name for it. I don't think I'll alert my favorite 'victims' to it though, it might backfire :)

simsam• 16 years ago

i sometimes browse this site: asknature.org

it is often a very strange approach and cannot be replicated by humans, but i like the ideology.

leif• 16 years ago

For hard (math) problems, which is where I find it hardest to make incremental progress, I usually just walk away, make myself some tea, or look for another problem. Anything that stops me from consciously thinking about it allows my subconscious to sort through the information, and eventually, the answer will hopefully float to the top. If that doesn't happen after long enough, when I do go back, I'll at least have gotten out of the circles I had been thinking myself into.

Ask HN: How do you solve hard problems if you can't make incremental progress?

Related Stories