Greedy algorithm to fill 2d array

[pieterdehoogd]

Hello, can someone help me with the following problem:
Is there a way to write a greedy algorithm that fills a 2d array with numbers?
Array array[12][12] is empty (all elements are -1) and the numbers 0 to 20 have to be spread around the array. But the last digit of a number can't be in a column if there is another number in that column with the same digit at the end. So for example:
11 and 1 can't be in the same column and 0, 10 and 20 can't be in the same column. The length between elements have to be minimal/the space between elements has to be minimal (so with a greedy algorithm).
Can someone help me with this problem or give some tips about how to do that?

[lastchance]

The length between elements have to be minimal/the space between elements has to be minimal (so with a greedy algorithm)

A "greedy" algorithm would usually be used to find A solution, not necessarily the optimal one. Here it would probably amount to "put the numbers sequentially in the first column they are allowed".

What do you mean by "the space between elements"? Column-wise? Row-wise? Both?

Give an example to clarify your question.

[pieterdehoogd]

By space between elements I mean row- and column wise. So a random example:

4 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 5
Here the space between 4 and 5 is very big.

4 5 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
Here the space between 4 and 5 is minimal.

[lastchance]

What IS the space between 4 and 5 in your first example?
It could be:
2 (or 3) - number of rows
4 (or 5) - number of columns
4 (roughly diagonal)?
7 (gaps along row plus column)?
or what?

And you have all numbers 0-20 to put in, not just 4 and 5. What measure of "space between numbers" do you have in mind.

As it stands your question is so ambiguous as to be meaningless. Just give the original problem (not your paraphrasing of it).

[pieterdehoogd]

Alright, you have an array[12][12], with starting values -1, so:

for(int i = 0; i < 12; i++) {
   for(int j = 0; j < 12; j++) {
      array[i][j] = -1; } }

Now, the array has to be filled with a greedy algorithm with the values 0 to 20. But in a way that the space between the values is less as possible, so for example when you only fill in 2 and 3 (it's an example, in the result should be the values 0-20):

-1 -1 -1 -1 2 3 -1 -1 ....
-1 -1 -1 -1 -1 -1 -1 -1 ....
-1 -1 -1 -1 -1 -1 -1 -1 ....
Now the space is 0 because there are 0 values between 2 and 3.

But when this is the situation:

-1 -1 -1 -1 -1 3 -1 -1 ....
-1 2 -1 -1 -1 -1 -1 -1 ....
-1 -1 -1 -1 -1 -1 -1 -1 ....
Now the space is 3 row-wise and 1 column-wise.

So the values should be as close to each other as possible.

The conditions:
2 values with the same last-digit (for example 0, 10 and 20) (or 1 and 11) can't be in the same column.

[salem c]

So is this a solution?

 1  2  3  4  5  6  7  8  9 10 11 12
13 14 15 16 17 18 19 20 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Or do you also mean rows as well?

[dhayden]

Now the space is 3 row-wise and 1 column-wise.

Okay, but what if the space of another placement was 1 column-wise and 3 row-wise? Which placement would be better? As lastchance said, you need to tell us exactly what "space wise" means. What is the exact formula that determines the "space" between cells? You (and we) need to know that to create a solution.

As lastchance also said, please post the original problem, not your paraphrasing of it. The reason is that the problem often contains important details that you miss or omit.

Here's a hint about computer science homework: every sentence in the assignment matters. They all describe something you need to do. Every single one.

[pieterdehoogd]

Salem c, yes that's an answer

I can post the original problem but it's a very long description and I got 75% of it done.

The original problem in short:
You got a file with subjects and teachers and you have to make a so good as possible schedule. There are a lot of conditions but I got them all in a boolean function which is true when at schedule[i][j] a subject p can be given. But now I have to write a greedy algorithm which fill the subject[n][m] with the subjects which satisfies the conditions. N stays for time and m stays for room: schedule[n][m]. And at every position is the number of the subject or -1 (empty). So for example you can fill it like:

For(int i=0; i<numberOfSubjects; i++) {
   For(int j =0; j<nrHours; j++) {
      For(int k=0; k<nrRooms; k++) {
         If(conditionsTrue(schedule, j, k, i)) {
            Schedule[j][k] = i;
}}}}

Bool conditionsTrue(int schedule[n][m], int row, int column, int subject) { .... }

But now I need a greedy algorithm to fill it...

[lastchance]

The original problem in short:

Could we have the original problem in long, please.

[jonnin]

a greedy algorithm is going to pick the path of least resistance at each iteration. (here, that seems like iterating the empty cells and plopping the next value in the next cell that does not break any rules. That it, that is the algorithm! There may be a better way to iterate the cells, but that is the brute force version).

the problem with them is that doing so can reach a point where you cannot solve it forward from where you got to, eg the travelling salesman problem the greedy algorithm can solve it, sometimes, and in many other cases, it just gets stuck and can't proceed.
if it gets stuck, you either have to back-track or start it over with a different initial condition -- the TSP one specifically works a lot more often if you run it in parallel from each node as the first node, for example (I think it can still get stuck, but its a lot harder to make a problem that it can't solve with the adaptation).

the same looks to be true here (though we lack the details to be sure). If it gets stuck (places all the values it can, then has some numbers yet to place that can't fit with the rules), you have to have a plan to deal with it.
instead, it also looks like this problem can be solved with a smart algorithm that avoids getting stuck in the first place, but that may not be 'greedy'.
Just a warning on what you are asking for and up against.

[dhayden]

Well here were are, 11 messages into the thread and the OP still won't answer basic questions like "post the full description" and "what is "space" between cells. I'm out.