How to approach

[Luc The Perverse]

I'm on topcoder.com and there are a series of problems that I cannot solve
because I can't come up with an algorithm to do it.

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

Travelling salesman, moving around a chessboard, removing numbers from a
sequence - I see them all as the same trivial method that somehow I am
missing. They all involve choices that branch off and begin from previous
choices and an optimal result where brute force attack is always infeasable
(given the test cases provided).

What do I do? I see about 3 or so options:
1. Buy an algorithm textbook. (A real gamble)
2. Look at and try to decipher the code? (Frustrating, but perhaps the most
educational)
3. Trying to look online for methods for solving classic algorithms.

I don't want to learn how to just solve one problem. I know they are all
connected somehow - I just can't see it.

I know I should know this stuff, and I feel kinda dumb asking - but how
should I proceed?

One of the problems was, given an imaginary chess piece (it was a
combination knight and king I believe), a board nXn dimensions (n provided)
and a starting and ending location, and a number of moves, tell me how many
unique ways there are to get from the starting to ending position (the
return value was a long so the problem stated that the system would ensure
that there were less than 2^63-1 for the given problem.)

If a textbook is the way I need to go about this - then it is alright to
tell me so. But right now I'm leaning away from that option.

 

[Patricia Shanahan]

I'm on topcoder.com and there are a series of problems that I cannot solve
because I can't come up with an algorithm to do it.

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

Travelling salesman, moving around a chessboard, removing numbers from a
sequence - I see them all as the same trivial method that somehow I am
missing. They all involve choices that branch off and begin from previous
choices and an optimal result where brute force attack is always infeasable
(given the test cases provided).

Travelling salesman is an NP-complete problem. Problems in NP have a
fast (polynomial time) way of checking that a claimed solution achieves
a claimed cost. If any of the NP-complete subset has a polynomial time
solution, so do all problems in NP. Unfortunately, nobody knows whether
any of them do. If you find out the answer, don't bother with topcoder.
Collect the $1,000,000 prize from the Clay Institute instead.

Of course, some variations may be easier than the general problem.

I don't want to learn how to just solve one problem. I know they are all
connected somehow - I just can't see it.

I know I should know this stuff, and I feel kinda dumb asking - but how
should I proceed?

One of the problems was, given an imaginary chess piece (it was a
combination knight and king I believe), a board nXn dimensions (n provided)
and a starting and ending location, and a number of moves, tell me how many
unique ways there are to get from the starting to ending position (the
return value was a long so the problem stated that the system would ensure
that there were less than 2^63-1 for the given problem.)

I haven't thought this through, but at first sight it looks to me like a
case for "dynamic programming". I believe that gives a solution in
O(n*n*m*a) where the board is nXn, m is the number of moves, and a is
the number of single moves. "Dynamic programming" is one of several
strategies to consider when looking for an algorithm for an unfamiliar
problem.

If a textbook is the way I need to go about this - then it is alright to
tell me so. But right now I'm leaning away from that option.

It depends on how much you want to improve your algorithm skills. If you
want to learn the strategies, you need a textbook or a really good web
tutorial.

Patricia

 

[Ed Kirwan]

I'm on topcoder.com and there are a series of problems that I cannot solve
because I can't come up with an algorithm to do it.

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

Travelling salesman, moving around a chessboard, removing numbers from a
sequence - I see them all as the same trivial method that somehow I am
missing. They all involve choices that branch off and begin from previous
choices and an optimal result where brute force attack is always infeasable
(given the test cases provided).

Why not jump in?

Think heavy recursion.

Travelling saleschap untried pseudo-code:

void findPath(Node node) {
List nodes = node.getConnectedNodes();
for (Iterator i = nodes.iterator(); i.hasNext() {
Node nextNode = (Node)i.next();
nextNode.setPreviousNode(node);
if (nextNode.getName().equals("New York")) {
recordPath(nextNode);
} else {
findPath(nextNode);
}
}
}

void recordPath(Node node) {
System.out.println("From New York to beginning was via ...");
Node previousNode = node.getPreviousNode();
while (previousNode != null) {
System.out.println(previousNode);
previousNode = previousNode.getPreviousNode();
}
}

Of course, you probably won't get further than three cities from the
start before your stack clutches its chest and keels over.

For the chess problem I'm sure there's a way to map all the next
possible moves of each piece to the getConnectedNodes() method.
Actually, that may well be the most interesting part: essentially
mapping your problem-space to a graph. (Feels like a mathematical
transform.)

Note: also jolly useful for finding circular dependencies in code.

 

[Luc The Perverse]

For the chess problem I'm sure there's a way to map all the next possible
moves of each piece to the getConnectedNodes() method. Actually, that may
well be the most interesting part: essentially mapping your problem-space
to a graph. (Feels like a mathematical transform.)

Note: also jolly useful for finding circular dependencies in code.

Are you telling me Java will solve the problem for me using some kind of
built in mapping function if I just give it the moves?

Oh boy.

Even if so, I still want to learn how to code it without this nifty "do it
for me" thing - in the same way I think you should learn some classic
sorting algorithms before you start using Array.sort

Doesn't mean I wouldn't be interested in learning how to have java do it for
me after that though.

 

[Ed Kirwan]

Are you telling me Java will solve the problem for me using some kind of
built in mapping function if I just give it the moves?

Oh boy.

Well, of course Java won't do it for you; but your algorithm will be
(given a knight at some starting square):
1) Identify all possible destination squares from this position (but
discounting those already visited, perhaps).
2) For each position: move knight, and recurse.

In this sense, the, "All possible destination squares," is just the
getConnectedNodes() of the code snippet.

(Actually, you'll have to create a new TracedNode for each move, which
the original snippet omitted.)

Even if so, I still want to learn how to code it without this nifty "do it
for me" thing - in the same way I think you should learn some classic
sorting algorithms before you start using Array.sort

That sounds like a wise approach. All that recursion is no doubt rampant
wheel-reinvention.

 

[Gordon Beaton]

Are you telling me Java will solve the problem for me using some
kind of built in mapping function if I just give it the moves?

Sounds like a typical Prolog way of doing things. Somewhat simplified
you define the rules, the initial state and the target state, then set
the thing in motion.

Search for "prolog generate and test" for more information.

/gordon

 

[Oliver Wong]

Well, of course Java won't do it for you; but your algorithm will be
(given a knight at some starting square):
1) Identify all possible destination squares from this position (but
discounting those already visited, perhaps).
2) For each position: move knight, and recurse.

In this sense, the, "All possible destination squares," is just the
getConnectedNodes() of the code snippet.

(Actually, you'll have to create a new TracedNode for each move, which the
original snippet omitted.)

You'll also want a "position rater" which tells you how good it is to be
in the position you're currently considering. E.g. a position in which all
your pieces are dead except for your kind is generally very bad, while a
position where all the enemy's pieces except for their king is very good.

Then you can stop the recursion when you realize that this path is
leading you into a very bad position. Search for min-max search or
alpha-beta search (they are two similar approaches).

- Oliver

 

[Roedy Green]

Are you telling me Java will solve the problem for me using some kind of
built in mapping function if I just give it the moves?

see http://mindprod.com/jgloss/rule.html

 

[Patricia Shanahan]

Well, of course Java won't do it for you; but your algorithm will be
(given a knight at some starting square):
1) Identify all possible destination squares from this position (but
discounting those already visited, perhaps).
2) For each position: move knight, and recurse.

In this sense, the, "All possible destination squares," is just the
getConnectedNodes() of the code snippet.

(Actually, you'll have to create a new TracedNode for each move, which
the original snippet omitted.)

This seems to me to be like a recipe for execution time that increases
exponentially with the number of moves. It looks to me as though an
iterative dynamic programming approach would be linear in the product of
board size, number of moves, and number of squares the piece can reach
in one move.

Here's some pseudo-code. All boards are long[n][n].

Create an initial board, with all elements zero except for a one at the
starting point, as new_board.

For each move i from 1 to m do:
old_board := new_board
Create a new_board, with all elements 0.
For each non-zero square old_board[r][c]:
For each square (r1,c1) that can be reached in one move from (r,c):
Add the value of old_board[r][c] to new_board[r1][c1]

The key invariant is that, at the end of iteration i and start of
iteration i+1, each square contains the count of the number of different
ways that square can be reached in exactly i moves. Initially,
there is one way of reaching the starting square, and zero ways of
reaching any other square.

If the required count is for using exactly m moves, the final value of
the destination square in new_board is the answer. If the count is for m
or fewer moves, at the end of each outer loop iteration, add the value
of the destination square to a total.

How would you avoid exponential time, in the recursive solution? I
suspect some sort of memoization might work, but I don't quite see how.
Ignoring board edges, and assuming knight+king, which has 16 possible
moves, at the end of 10 iterations there will be 2^40 different paths.

Patricia

 

[Oliver Wong]

You'll also want a "position rater" which tells you how good it is to
be in the position you're currently considering. E.g. a position in which
all your pieces are dead except for your kind is generally very bad, while
a position where all the enemy's pieces except for their king is very
good.

Then you can stop the recursion when you realize that this path is
leading you into a very bad position. Search for min-max search or
alpha-beta search (they are two similar approaches).

Disregard this advice. My server didn't receive the original post until
now, and I had just assumed from the direction that the thread was going
that the problem was to play chess, not to count the number of legal moves
for a given chess piece.

- Oliver

 

[Ed]

This seems to me to be like a recipe for execution time that increases
exponentially with the number of moves. It looks to me as though an
iterative dynamic programming approach would be linear in the product of
board size, number of moves, and number of squares the piece can reach
in one move. (Snip)

How would you avoid exponential time, in the recursive solution? I
suspect some sort of memoization might work, but I don't quite see how.
Ignoring board edges, and assuming knight+king, which has 16 possible
moves, at the end of 10 iterations there will be 2^40 different paths.

Patricia

I completely agree: the recursive route would not solve any of these
problems of any significant depth; I only offered it as Mister The
Perverse seemed to be looking for a toe-hold before starting to scale
this type of problem; I thought that starting with recursion would be
instructive: it's an elegant solution, but the inevitable
stack-explosions would reveal its limitations. Despite these
limitations, however, I'd have hoped he'd have found new insight into
the problems he's investigating.

..ed

 

[Luc The Perverse]

Disregard this advice. My server didn't receive the original post until
now, and I had just assumed from the direction that the thread was going
that the problem was to play chess, not to count the number of legal moves
for a given chess piece.

No that's ok.

But I'm glad you said something because otherwise I was going to severely
reprimand you (Humor)

 

[Luc The Perverse]

I completely agree: the recursive route would not solve any of these
problems of any significant depth; I only offered it as Mister The
Perverse seemed to be looking for a toe-hold before starting to scale
this type of problem; I thought that starting with recursion would be
instructive: it's an elegant solution, but the inevitable
stack-explosions would reveal its limitations. Despite these
limitations, however, I'd have hoped he'd have found new insight into
the problems he's investigating.

Yes - one of the example problems returns a long whose order is
approximately 60 bits -and it has to execute in less than 2 seconds. A non
exponential algorithm is essential!

 

[Luc The Perverse]

I completely agree: the recursive route would not solve any of these
problems of any significant depth; I only offered it as Mister The
Perverse seemed to be looking for a toe-hold before starting to scale
this type of problem; I thought that starting with recursion would be
instructive: it's an elegant solution, but the inevitable
stack-explosions would reveal its limitations. Despite these
limitations, however, I'd have hoped he'd have found new insight into
the problems he's investigating.

Regarding my original post -

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.

 

[Patricia Shanahan]

Patricia Shanahan wrote:




I completely agree: the recursive route would not solve any of these
problems of any significant depth; I only offered it as Mister The
Perverse seemed to be looking for a toe-hold before starting to scale
this type of problem; I thought that starting with recursion would be
instructive: it's an elegant solution, but the inevitable
stack-explosions would reveal its limitations. Despite these
limitations, however, I'd have hoped he'd have found new insight into
the problems he's investigating.

The bigger point I'm trying to make is that there are a number of
strategies that lead to reasonably efficient algorithms. It is important
not to get stuck on one strategy, such as recursive solutions. Sometimes
that is the best strategy, but often a different one is better.

I don't think studying random algorithm code will lead to a good grasp
of the different strategies, and a feeling for which to use when. A
book, web tutorial, or a course taught by an expert, is more likely to
be effective.

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

Patricia

 

[Patricia Shanahan]

Yes - one of the example problems returns a long whose order is
approximately 60 bits -and it has to execute in less than 2 seconds. A non
exponential algorithm is essential!

Depending on the problem size, I think you have a good chance of getting
there with the dynamic programming approach I posted a few messages ago.

Patricia

 

[Oliver Wong]

I have done dynamic programming before in class - I think my brain just
needs a jump start.

The concept behind dynamic programming is to basically do what you would
do with a recursive solution, except cache values so you don't have to
recompute them.

I've been playing around with AspectJ recently, and one of the "aspects"
I've weaved into an existing program was to intercept expensive method
calls, and cache their values on the first usage, so that later calls would
be intercepted and the cached value would be returned.

I now wonder if a standard library or tool could be written so that you
could generically turn any recursive algorithm into a "dynamic programming"
style algorithm using Aspects.

- Oliver

 

[Patricia Shanahan]

The concept behind dynamic programming is to basically do what you
would do with a recursive solution, except cache values so you don't
have to recompute them.

That is what I would call memoization. Dynamic programming can go a
stage further, and drop the recursive idea completely, producing an
iterative approach, in which you build tables of solutions to subproblems.

Recursion with memoization can be efficient because you only solve
subproblems you actually need. Dynamic programming solves all
subproblems. For example, my suggested approach to this problem
calculates the number of ways of reaching each square in 0 moves, then
the number of ways of reaching each square in 1 move, in 2 moves ...

Full dynamic programming tends to be more efficient, because of the
simple loop structure and data access patterns, when most subproblems
will be needed.

My guess with this one is that, unless the number of moves is small
compared with the board size, most squares are going to be on a path to
the destination, so most subproblems will be needed.

Patricia

 

[Roedy Green]

I don't think studying random algorithm code will lead to a good grasp
of the different strategies, and a feeling for which to use when. A
book, web tutorial, or a course taught by an expert, is more likely to
be effective.

For many problems you don't really need the best solution, just a good
solution. If you can probe a reasonable subset of the solution space
with random attempts, you can find a reasonable solution with a pretty
mindless algorithm.

I remember using a technique like this for finding roots of equations
when there were several answers. You get close with random probing,
then home in with some sort of differential equation solver.

 

[Luc The Perverse]

Depending on the problem size, I think you have a good chance of getting
there with the dynamic programming approach I posted a few messages ago.

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.

I mark every cell that can be reached in [0] as 1 since there is one
unique way to get there from the starting point after 1 move.

Then I repeat for each cell on the board adding the previous set of paths to
the destination cells for each. Repeat until all x are exhausted.

The answer is paths[dest][x-1], or the number of unique paths after x turns
to destination starting from point of origin.

Think it will work?

Actually, I probably only need to mark the first cell as 1 (and expand the
array accordingly) . . . but as Roedy said, it is more important to have
something that works well (at least to begin with) than to focus on the
perfect implementation. Given my position, I would have to agree!

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.