How to approach

[Patricia Shanahan]

Luc The Perverse wrote:
....

WAIT!

I think I got it (I'm not meaning to imply that you didn't help) - and I
didn't look at anything.

Let's say there are NxN squares, and there are x number of moves.

I can make the square x, y be represented as an integer 0..N * N - 1

So I create a 2D array [N*N][x] of longs which will represent the sum of the
number of unique paths to the given point.

....

You got it. There is an optimization that reduces the memory cost,
but you have a dynamic programming solution to the problem. And you have
the really big savings from exponential to linear increase in time and
memory as the number of moves increases.

Hey thanks everyone. This is more than just a single problem or some points
on a practice problem that doesn't matter anyway. I'm learning how to do
this, and becoming a better programmer - and that is important to me.
Learning new abstract concepts, and having exciting revelations is actually
(though sadly) a bit of a rarity for me.

I think, more than ever after seeing this, that you would benefit from
reading a book on algorithm design.

Patricia

 

[Chris Uppal]

Generally, recursive solutions are good if there is a lot of pruning, so
that you only have to solve some of the subproblems.

I think it could be argued that the principle benefit of a recursive
formulation is that it makes it easy(er) to see and think about options for
early pruning.

-- chris

 

[Chris Uppal]

Except - in a way, they are all the same problem.

[I have read the rest of this thread, but here seems to be as good a place to
reply as any]

I don't think that they will typically be the same problem. It is true that
there are large classes of problems where the only known solution is one form
or another of brute force (a recursive or iterative exploration of the entire
problem space -- possibly with a bit of early pruning).

But when it comes to problems on TopCoder and the like -- i.e. essentially
/puzzles/ -- you can normally expect that there's a better solution to be
found. Otherwise it'd be boring !

So you have to look for short-cuts, or other kinds of cleverness, and that's
where the fun comes in (or frustration, depending on your success). Some
general techniques:
+ Try to formulate the problem in as many different ways as possible.
+ Consider approximations to the problem.
+ Can you find a solution to part of the problem ?
+ Have you seen something a bit similar before (NB: this
one is particularly dangerous since it can lead you
right royally up the garden path)
+ Try to produce a /proof/ that the problem isn't soluble.
Where does the attempt fail ? That's probably the key
insight.
+ Try a brute force solution of a few special cases. Are
there any patterns that give you a hint ?
+ Post it to Usenet ;-)

There's a lot of satisfaction to be had in solving such puzzles, but they are
not (normally) particularly related to the kinds of algorithm problems that
occur in real programming and design. Working on them is probably good
practise for real algorithm design (especially the for first of the above
techniques), but it's no substitute for having a basic grounding in the
algorithmic techniques that are already available (I don't mean having an
expert knowledge of all the millions of published algorithms -- just the
basics, so you can navigate the field with confidence).

Bottom line: if your aim is to get more fun from TopCoder then you have to
practice. If your aim is to be a more knowledgable designer, then buy some
books (/and/ read them ;-)

-- chris

 

[Chris Uppal]

Learning new abstract concepts, and having exciting revelations is
actually (though sadly) a bit of a rarity for me.

It's something of a rarity for everyone. Hence the popularity of puzzles.

-- chris

 

[Luc The Perverse]

It's something of a rarity for everyone. Hence the popularity of puzzles.

Most puzzles get learned once, and then solving them is mundane.

 

[Monique Y. Mudama]

I am going to look at example code from people who successfully did
the problem. I think that is the best way to learn for this
particular case. I have done dynamic programming before in class -
I think my brain just needs a jump start. Plus I am almost
completely inept at looking at other people's code and understanding
it so the practice would be good for me.

I think the best way to get better at understanding other people's
code is to try to add a feature to existing code, or fix a bug in it.

My last job involved a lot of this -- coming into the tail end of the
development cycle for an extremely complex system. All of the easy
parts were implemented; I had to find a way to make the rest fit. It
could be incredibly frustrating, but I got a lot better at it.

 

[Oliver Wong]

I think the best way to get better at understanding other people's
code is to try to add a feature to existing code, or fix a bug in it.

My last job involved a lot of this -- coming into the tail end of the
development cycle for an extremely complex system. All of the easy
parts were implemented; I had to find a way to make the rest fit. It
could be incredibly frustrating, but I got a lot better at it.

I was handed a complex Java project with almost zero documentation. I
managed to pick up large chunks of it pretty quickly simply by writing
JavaDocs for every method I encountered. I'd look at a method, and if I
could figure out what it was doing, I'd put a comment explaining what it was
doing. If I couldn't figure out what it was doing, chances are that it made
calls to other methods. So I would look at those called method calls first,
and try to document what THOSE are doing. Then, I'd go back up and now that
I know what those called methods do, I could take another stab at guessing
at what the calling method does.

Sometimes you'll find a method, write down what it does, and then ask
yourself "Why would anyone ever want THIS behaviour?" (e.g. the method is 30
lines long, and all it does is always returns false). That might be a sign
of a bug in the implementation.

- Oliver

 

[Roedy Green]

I was handed a complex Java project with almost zero documentation. I
managed to pick up large chunks of it pretty quickly simply by writing
JavaDocs for every method I encountered.

I have been hired several times to write JavaDoc. When I find a class
or method I can't understand, I start gradually cleaning up the code,
simplifying it, making sure my changes don't affect the actual output.
I globally rename variables to more meaningful and precise names.

Then gradually the fog clears. Often I find bugs in doing this.

Another tactic is to use a trace and just watch some code work on
typical data. Seeing the actual data and how it transforms gives you
clues on the overall intent.

Adding comments to variables about how they are used, then checking to
see if that is really true is useful. Comments on variables are much
more valuable for overall understanding that comments on procedural
code.

When people write Javadoc they are often fairly good on detail. Where
they screw up is the "obvious" big picture stuff that is very
difficult to reconstruct from code detail.

 

[Monique Y. Mudama]

Adding comments to variables about how they are used, then checking
to see if that is really true is useful. Comments on variables are
much more valuable for overall understanding that comments on
procedural code.

When people write Javadoc they are often fairly good on detail.
Where they screw up is the "obvious" big picture stuff that is very
difficult to reconstruct from code detail.

I find that the comments I most want are those describing "why", not
"what". "What" I can figure out, as you've described. "Why" may
never be uncovered, or not until after one or more well-meaning people
cleaned up the code that seemed so unnecessarily complex.

 

[Thomas Weidenfeller]

I find that the comments I most want are those describing "why", not
"what". "What" I can figure out, as you've described. "Why" may
never be uncovered, or not until after one or more well-meaning people
cleaned up the code that seemed so unnecessarily complex.

Well, it is a mixture. I can point you to Sun JavaDoc where I would have
been very glad if they would have explained more "why", but also
more"what", too. E.g.

http://java.sun.com/j2se/1.5.0/docs/api/java/awt/Toolkit.html#sync()

public abstract void sync()

Synchronizes this toolkit's graphics state. Some window systems may do buffering of graphics events.

This method ensures that the display is up-to-date. It is useful for animation.

Actually, at some point in time I was thinking about creating some web
site with with the most mysterious Java 2 SE methods. That one would
have been on that site.

/Thomas

 

[Chris Uppal]

I was handed a complex Java project with almost zero documentation. I
managed to pick up large chunks of it pretty quickly simply by writing
JavaDocs for every method I encountered. I'd look at a method, and if I
could figure out what it was doing, I'd put a comment explaining what it
was doing.

Suggests an interesting idea for IDEs (or similar). The ability to add notes
to existing code without changing that code. Notes could be public (shared
with the team/world) or private; permanent or ephemeral. Categories might be
useful too.

I know there are similar systems for anotating websites, I wonder if anyone's
thought of using one of them to improve Sun's API documententation...

-- chris