lewis manuel wrote:... The second fact was that the column and row is always increasing
lewis manuel wrote:The key things that caught my attention in this problem was the fact that matrix M it always N X N. Meaning it has the same length in any direction(3 * 3, 4 * 4). The second fact was that the column and row is always increasing. Meaning each array in in each row is always sorted. Because of this fact, I figured it would best to use the BinarySearch to cut the amount of indexes I need to visit. What you do think?
There are three kinds of actuaries: those who can count, and those who can't.
OK, but that's likely to limit the size of test arrays. I really like the fact that you've added a createMatrix() method though, because that allows you to generate as many as you like for testing.lewis manuel wrote:I've edited my code(not the algorithm mind you) so it can accept input from the user(with some exception checking) and so that other people can test it if they want to.
But that isn't your "worst case" scenario, which is something you always want to think about when testing.The largest test I've done so far is a 100 * 100 matrix with each element incremented by 10 and the number I was looking for was 780(it found it pretty fast). Feel free to mess with my code if you so desire.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
lewis manuel wrote:Here is how it looks:
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:There will also be similar "worst case" matrices when it can't contain duplicate values.
There are three kinds of actuaries: those who can count, and those who can't.
There are three kinds of actuaries: those who can count, and those who can't.
There are three kinds of actuaries: those who can count, and those who can't.
Carey Brown wrote:I find this puzzle intriguing and feel that the solution lies in being able to narrow down the row AND column, most likely by logic which determines if a subset of a row or a subset of a column is to be processed next.
In order to test this it would be very helpful to have a method to create the worst case scenario matrix of a given size.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Carey Brown wrote:I find this puzzle intriguing and feel that the solution lies in being able to narrow down the row AND column, most likely by logic which determines if a subset of a row or a subset of a column is to be processed next.
In order to test this it would be very helpful to have a method to create the worst case scenario matrix of a given size.
Well, I gave two versions above which could be replicated for any n.
I also think that the solution lies in diagonals and may well be of order O(logn), and my reasoning is as follows:
Suppose you need to find a number x.
1. If you do a binary chop on the main top-left bottom-right diagonal - which must also be in numeric sequence - you will either find x, in which case the job is done, or (more likely) you will find two diagonal positions containing numbers less than and greater than x. Let's say that those two squares are at p,p and p+1,p+1.
Given the constraints of the matrix, you now know that the number cannot be in the sub-squares 1,1-p,p or p+1,p+1-n,n - indexing from 1 - so if it exists, it must be in the other two. And since the same top/bottom left/right ascending constraint applies to those squares, you can apply the same algorithm recursively to each, until you either find n or end up with only two positions left to check.
HIH
Winston
Carey Brown wrote:I'm not entirely sure I understand your top-left/bottom right approach. If you try my matrix generator you will find that matrices that follow the rules don't necessarily break down along clean top-left/bottom-right lines.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:Using diagonals (which I assume you agree must be in numerical order)...
Winston Gutkowski wrote:By which I assume you mean that the last position in one row could be greater than the first position in the next (correct me if I'm wrong), which is what I meant by "overlap" in my previous post.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Carey Brown wrote:[the diagonal: 15,25,31,32,26,23,18 (if this is what you mean) is not necessarily in numeric order.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Carey Brown wrote:
Winston Gutkowski wrote:Using diagonals (which I assume you agree must be in numerical order)...
In this matrix
the diagonal: 15,25,31,32,26,23,18 (if this is what you mean) is not necessarily in numeric order.
Winston Gutkowski wrote:I did say "top-left bottom-right diagonal", but maybe I didn't make it clear enough.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:Ooops. Just found a huge hole in my "solution": The "remaining" areas may not be squares.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Carey Brown wrote:So, I could do a binary search on the row to the right of 17, and if not found, try a binary search on the row to the left of 32.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:I'm now trying to work out if there's any easy way of narrowing that search down, given that we're no longer dealing with squares.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
lewis manuel wrote:The solution that I came up with is similar to yours (check out my modified solution). Good job man!
Well I have to go to sleep. I'll have a new problem for you guys tomorrow.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Aha! I think I may have found it.
(...) O(n)
Now I just have to prove it.
Winston
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:Hmm... given an N x M rectangle of squares, and if we can go either to the
right one square or down one square, how many paths are there to bottom
right, starting from upper left?
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |