programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Grid algorithm

Terry Flint
Greenhorn
Posts: 20
I had my first lecture on algorithms today and the instructor had an exercise he wanted us to work on in class. I thought I'd be able to get around it, given it was first lecture after all, but I was one of the ones who couldn't complete it (not quite the only one). First off, here's the simple example he gave to get the idea into our heads:

Write down a grid, say, 4£4, of the numbers 0, 1, 2,..., that has the property that each number in the grid is the smallest number not appearing above it in the same column, or to its left in the same row.

Naturally, this produces the following table:

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0

So far, so good. He then extracted the idea to make a more general algorithm:

Write down an n * n grid, of the numbers 0, 1, 2,,..., that has the property that each number in the grid is the smallest number not appearing above it in the same column, or to its left in the same row.

He asked us to code this in java. Obviously, he wanted it to be a method which would have the parameter int n.
This n will then be used to produce a grid of n*n. I don't know if a 2D array or a 2D ArrayList is more appropriate for this.
I've now started to think an ArrayList makes more sense, because I don't even know if I can reassign an array to a different size.

I am frankly to ashamed of the abominable coding I tried to do in class to show it, and I want to start from scratch.
I don't want outright solutions, but I do want hints on how to do this. I imagine I will be needing two nested for loops to cycle through the array/ArrayList.
I notice that if the square is at [i][j], all the left cells will have the same i value and a lesser j value, and all of the above cells will have the same j value and a lesser i value (I think).
I thought I'd be able to use booleans to check for whether a cell was above or left, but the way I was doing it, that required associating a boolean with an int, which just made no sense.

Now, since facepalming and headdesking doesn't seem to work to well, I thought I'd admit that I need some help.
What should I do? By the way, links to online courses and documentation on algorithms like this would be appreciated if they are available (Beginner level stuff obviously).

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Step 1) Turn off your computer.
Step 2) Get some paper, pencils, and one or more very large erasers.
Step 3) write down how YOU would do this.
Step 4) Revise the above steps multiple times, making them simple and simpler, until a 10yr old child can understand and follow them.
Step 5) When you are done with the above, revise it some more.

ONLY when you have completed steps 1-5 should you consider writing even one line of java code.