10 Replies - 839 Views - Last Post: 24 October 2014 - 02:06 PM

#1 Cod3Monky   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 18-October 14

Number of paths coordinate system

Posted 18 October 2014 - 11:02 AM

Hey everybody,

I've been pondering about this algorithm for about a week but I'm still
not able to write a "fast" working method/algorithm to solve the Number-of-paths-exercise we were
given in my class ://>

so here's the task:
Write an efficient java program "Paths" which solves the following task:
- Read input n ∈ N and give output a(n) which is the number of paths from (0,0) to (n,0)
it is not allowed to go over the diagonal (m,m) and also not below the x-axis (m,0)
here are the allowed steps:
u = (1,1), U = (1,4), d = (1,−1), D = (1,−4) and H = (1,0)
steps are performed in a two-dimensional-coordinate-system!

Well don't get me wrong, I may be new here and the first thing I do is asking to solve an exercise, but
I'm pretty much "new" to such exercises. I'm studying Software Engineering atm for 1.5years but we never talked about
programming algorithms and I never faced the problem that my code is not efficient enough.

I already made some guesses, maybe they're useful to build this program.
Thinking about the paths and the steps you are allowed to perform I decided to first draw some examples.
I used some tiny numbers like 3, 4, 5 hoping to find a sheme...
The next idea was to get "all" steps possible and erase the one which go beyond the allowed area like
building a binary truthtable with lets say five inputs which represent the steps.
But for now I don't really know where to start. I mean i cannot start programming unless I managed to
find a fitting, working, efficient algorithm for n=1000 or sth. like that.

I hope there's someone out there who is familiar with algorithms ://>
Thanks alot guys!

Is This A Good Question/Topic? 0
  • +

Replies To: Number of paths coordinate system

#2 Jordy2254   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 48
  • Joined: 18-October 14

Re: Number of paths coordinate system

Posted 18 October 2014 - 11:15 AM

If you give a post of your current algorithm, i will have a look at it and then post a improved version or explain how to make it more efficient, don't really understand what your meaning overly to be honest.

Thank in advance
Jordan
Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11225
  • View blog
  • Posts: 19,245
  • Joined: 19-March 11

Re: Number of paths coordinate system

Posted 18 October 2014 - 11:30 AM

View PostCod3Monky, on 18 October 2014 - 01:02 PM, said:

Well don't get me wrong, I may be new here and the first thing I do is asking to solve an exercise, but
I'm pretty much "new" to such exercises.


You're fine there - that's where most of us start.


Quote

I already made some guesses, maybe they're useful to build this program.


And here, you're way ahead of the curve. :)/>


Okay, so we're on a Cartesian plane, and we are exploring a space bounded above the the x=y diagonal, and bounded below by the x axis, so open at the right. And we want to get to a point on the x axis, using a constrained set of moves and remaining within the bounded space.

First thing I do here is I draw pictures to make sure I understand the problem correctly. A whiteboard is great for this, but a scrap of paper and a pencil will do. Pick points on the axis and see if you can draw lines to get there. Obviously, there's one path that's going to go by a sequence of H moves. And then I can replace H moves with u-H-d moves, and that can happen recursively, and so forth. So I suggest you start playing like that. Sooner or later I think this will be pretty much a closed-form calculation, and not a typical path-finding exploratory algorithm. That is, you should be able to write an expression that evaluates directly to an answer for any given y. But first, you have to find the combinations that are important to the problem.

So get thee to a whiteboard! :)/>
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11225
  • View blog
  • Posts: 19,245
  • Joined: 19-March 11

Re: Number of paths coordinate system

Posted 18 October 2014 - 11:39 AM

View PostJordy2254, on 18 October 2014 - 01:15 PM, said:

If you give a post of your current algorithm, i will have a look at it and then post a improved version or explain how to make it more efficient, don't really understand what your meaning overly to be honest.

Thank in advance
Jordan



You'd kind of have to understand the algorithm in order to improve it. :)

To this end, you're allowed to ask questions if there are things you don't understand - in fact, interrogating the questioner is an important part of helping them figure out what exactly they mean to do.

As I understand it, we're on a discrete Cartesian plane, so we're moving on lattice points. We are allowed to move in the space between the X axis and the x=y diagonal, inclusive. We can change position by applying one of a set of vectors to our current position. These allow us to move right by one step without changing y, or to move right by one step and change y by +/-1 or by +/-4. So if we're looking for (0,1) our only path is the single move (H). However, if we're looking for (0,2), we can get there by (H,H) or by (u,d).

Does this help clarify?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12366
  • View blog
  • Posts: 45,478
  • Joined: 27-December 08

Re: Number of paths coordinate system

Posted 18 October 2014 - 11:57 AM

I'd like to make a few clarifications. So are we bounded in the first quadrant of the Cartesian plane? So if I'm at (0, 0) initially, then taking d = (1, -1) to put me at (1, -1) would be illegal, correct?

Similarly, if n = 3 and I take U = (1, 4), then I'm above 3 in the y-coordinate, so that's illegal? For n = 3, you can enumerate the paths pretty easily. Would you mind posting your enumeration so we have some samples to go on?

Quote

The next idea was to get "all" steps possible and erase the one which go beyond the allowed area

This is almost certainly the wrong way to do this. Enumerating all steps will take exponential time on n, with complexity Theta(5^n).
Was This Post Helpful? 1
  • +
  • -

#6 Jordy2254   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 48
  • Joined: 18-October 14

Re: Number of paths coordinate system

Posted 18 October 2014 - 12:01 PM

View Postjon.kiparsky, on 18 October 2014 - 11:30 AM, said:

First thing I do here is I draw pictures to make sure I understand the problem correctly. A whiteboard is great for this, but a scrap of paper and a pencil will do.
So get thee to a whiteboard! :)/>/>

You'd kind of have to understand the algorithm in order to improve it. :)


Whiteboards are amazing for this, i have a hunk of paper next to my desk for random ideas when gaming and pre-working out an algorithm :3,

As for the algorithm, i'll try and make sense of it tomorrow if it hasn't been resolved already, as im tired and off to bed shortly.

As for asking for the code that was just to see how he's tackled it already,

Thanks
Jordan
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12366
  • View blog
  • Posts: 45,478
  • Joined: 27-December 08

Re: Number of paths coordinate system

Posted 18 October 2014 - 12:37 PM

Also, in digging some more, I came up with Motzkin Numbers. So if the line y = x is the upper bound, then (1, 4) and (1, -4) won't come into play until n >= 8. So your first seven terms will actually be the Motzkin numbers. This should help you check your work a bit.

If one must stay above the x-axis, then d and D can only be used if u and U have been used first respectively. And d must follow u, as D must follow U. In fact, you can use at most floor(n/4) instances of U.

Computing a closed form solution (or even defining a recurrence) is a bit beyond my math skills. But hopefully this will give you some insights into designing an algorithm.

Also, I'm going to move this to Computer Science for better discussion since this is more topical/advanced/theoretical.
Was This Post Helpful? 0
  • +
  • -

#8 Cod3Monky   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 18-October 14

Re: Number of paths coordinate system

Posted 19 October 2014 - 07:53 AM

Alright guys thanks alot!
At the moment im pondering about some ideas using my whiteboard (which really kinda helps to get an overview!)
For now it'd be the best to just try writing down or at least illustrate some concrete
ways to solve the task.
I'll let you know the results in a few hours!
Was This Post Helpful? 0
  • +
  • -

#9 Cod3Monky   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 18-October 14

Re: Number of paths coordinate system

Posted 19 October 2014 - 03:28 PM

public class Paths {

	/**
	 * 
	 */
	static int countPaths = 0;

	public static void point(int a, int b, int x, int y) {
		if (a == x && b == y) {
			countPaths++;
			return;
		} else if (a < b || b < 0 || a > x)
			return;
		point(a + 1, b + 1, x, y);
		point(a + 1, b + 4, x, y);
		point(a + 1, b - 1, x, y);
		point(a + 1, b - 4, x, y);
		point(a + 1, b, x, y);
	}

	public static void main(String[] args) throws Exception {
		point(0, 0, 10, 0); 
		System.out.println("output: " + countPfade);
	}
}



Okay that's what I tried so far ://>/>
Sadly its not efficient enough to solve for n>=20 or sth. like that...
Any1 got some improvements?
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12366
  • View blog
  • Posts: 45,478
  • Joined: 27-December 08

Re: Number of paths coordinate system

Posted 19 October 2014 - 04:08 PM

Recursion is expensive. You should check if the point is feasible before recursing.
Was This Post Helpful? 0
  • +
  • -

#11 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: Number of paths coordinate system

Posted 24 October 2014 - 02:06 PM

I think your main problem is that you are performing redundant calculations. For example, you have 2 ways to get to (2,1).

(0,0) -> (1,1) -> (2,1)
(0,0) -> (1,0) -> (2,1)

This means that you call point(2,1,20,0) twice, so all the recursive work that is involved in computing this call is performed twice. As we move further in the recursion, the more paths lead to the same point which means you redunantly calculate those points even more. To avoid these redundant calculations you can use a technique called memoization. Basically, you maintain a datastructure (usually a multi-dimensional array) that contains answers to calculations that you have already computed. At the beginning of the function see if you have performed the calculation for your current input and if so return the result. Otherwise, perform the calculation as usual and store the result in the structure. For the above example, the first time point(2,1,20,0) is called you will perform the calculation, but the second time, you will be able to just lookup the result that you have already computed.

Another slight inefficiency is that you start from (0,0) and check all paths to (20,z) for every z between 0 and 20. These include lots of paths that you could have skipped altogether. It would be better to start at (20,0) and work your way back to (0,0). This way you would not be spending time on irrelevant paths.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1