How to get the old index of an element of an array after sorting

Question

0.00/5 (No votes)

See more:

Hello everyone,

I am studying on alghroitms. So, I have found a tradiational problem; which is "Knight's Tour".

Basicly, I have created the solution. However, I cannot format it.

23 8 59 62 25 10 29 54
60 63 24 9 52 55 26 11
7 22 61 58 41 28 53 30
64 37 40 51 56 49 12 27
21 6 57 42 39 46 31 48
36 3 38 45 50 43 16 13
5 20 1 34 15 18 47 32
2 35 4 19 44 33 14 17

This is sample of output. I want to see the output like this
First: G3 (Number 1)
Second: H1 (Number 2)
Third: F2 (Number 3)
and so on.

What is the best way to do this. I sorted the array but, still have problems. I am loosing the old indexes. So I can' t rename them.

Here is my code:
Main.

Java

public static void main(String[] args) {
        At _at =  new At();
        _at.grid = new int[_at.base][_at.base];
        _at.total = (_at.base - 4) * (_at.base - 4);

        for (int r = 0; r < _at.base; r++) {
            for (int c = 0; c < _at.base; c++) {
                if (r < 2 || r > _at.base - 3 || c < 2 || c > _at.base - 3) {
                    _at.grid[r][c] = -1;
                }
            }
        }

        int row = 2 + (int) (Math.random() * (_at.base - 4));
        int col = 2 + (int) (Math.random() * (_at.base - 4));

         _at.grid [row][col] = 1;

        if (_at.solve(row, col, 2)) {
            _at.printResult();
        } else {
            System.out.println("no result");
        }

    }

Horse Class

Java

public class At {

    private final static int TahtaBoyutu = 8;
    public int base = TahtaBoyutu + 4;
    //ArrayList<Integer> hareketler = new ArrayList<>();
    //public final static int[][] aktar = new int[8][8];
    public final static int[][] moves = {{1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2},
    {-2, 1}, {-2, -1}, {-1, -2}};
    public static int[][] grid;
    public int total;

    public boolean solve(int r, int c, int count) {
        if (count > total) {
            return true;
        }

        List<int[]> nbrs = neighbors(r, c);

        if (nbrs.isEmpty() && count != total) {
            return false;
        }

        Collections.sort(nbrs, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[2] - b[2];
            }
        });

        for (int[] nb : nbrs) {
            r = nb[0];
            c = nb[1];
            grid[r][c] = count;
            if (!orphanDetected(count, r, c) && solve(r, c, count + 1)) {
                return true;
            }
            grid[r][c] = 0;
        }

        return false;
    }

    private static List<int[]> neighbors(int r, int c) {
        List<int[]> nbrs = new ArrayList<>();

        for (int[] m : moves) {
            int x = m[0];
            int y = m[1];
            if (grid[r + y][c + x] == 0) {
                int num = countNeighbors(r + y, c + x);
                nbrs.add(new int[]{r + y, c + x, num});
            }
        }
        return nbrs;
    }

    private static int countNeighbors(int r, int c) {
        int num = 0;
        for (int[] m : moves) {
            if (grid[r + m[1]][c + m[0]] == 0) {
                num++;
            }
        }
        return num;
    }

    public boolean orphanDetected(int cnt, int r, int c) {
        if (cnt < total - 1) {
            List<int[]> nbrs = neighbors(r, c);
            for (int[] nb : nbrs) {
                if (countNeighbors(nb[0], nb[1]) == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public void printResult() {
        for (int[] row : grid) {
            for (int i : row) {
                if (i == -1) {
                    continue;
                }
                System.out.printf("%2d ", i);
            }
            System.out.println();
        }
    }

Posted 10-Nov-14 0:26am

FoxRoot

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Garth J Lancaster · Accepted Answer · 2014-11-10T01:29:00

Solution 1

hmmm

why don't you run two for loops across your grid and use the grid value as the index into a linear array (as long as the grid values are unique)

Java

// pseudo code 

for rows = 0..7
  for cols = 0..7
     linear string array[grid[row, col]] = ascii(65+row) concat ascii(48+col) 
  end-for
end-for

for linear-index 1..64
  print linear string array[linear-index]
end-for

Posted 10-Nov-14 1:29am

Garth J Lancaster

Comments

FoxRoot 10-Nov-14 7:42am

I tried this. But it doesn' t work at all. I think I need ArrayList or Generic type. However, couldn't resolve.

Garth J Lancaster 10-Nov-14 7:59am

you fail to understand what 'pseudo code' is - its an idea, expressed in very rough code terms - its never meant to run directly

FoxRoot 10-Nov-14 8:03am

Clearly, I know what puseudo code is. However;

public final static int[][] demo= new int[8][8];

for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
demo[grid[row, col]] = 0; // What to type here? I filled by zeros stil not working.
}
}

FoxRoot 10-Nov-14 7:43am

Could you re-write it in Java please? Because I am newbie
and have some problems.

Garth J Lancaster 10-Nov-14 8:02am

no, I suck mightely at java - you know for loops, arrays - you just have to declare a string array of 65 elements, and look up how to turn an integer into an ascii character or string - iirc, you can go something like char c = (ascii)int .... you also need to know that in ASCII, 65 is 'A', 66 is 'B'... and 48 is '0', 49 is '1'

FoxRoot 10-Nov-14 8:06am

Thanks. Your explanation is so clear. But;

public int[] demo= new int[64];

public void FillIt()
{
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
demo[grid[i, j]] = 1; // Error here
}
}
}

FoxRoot 10-Nov-14 8:10am

public String[] demo= new String[64];

public void FillIt ()
{
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
demo[grid[i, j]] = "a"; // Same error here.
}
}
}

Garth J Lancaster 10-Nov-14 8:27am

I warned you I didn't do a lot in java - you're so close (but those loops should be i < 7, j < 7 shouldn't they ?)

Im not sure if java will allow you to 'nest' array's, so, this

demo[grid[i, j]] = "a";

could also be expressed roughly as

int index = grid[i,j];
demo[index] = something

ok, so, 'something' - this is where you'll need to do a bit of research, or it might even by in your textbook - or google 'ascii table'

you want 0 as an integer row value to be 'A' as a character
you want 1 as an integer row value to be 'B' as a character
you want 0 as an integer col value to be '0' as a character

so the ascii table shows the mapping between integers and characters

ASCII

Integer Character
48 0
49 1
...
65 A
66 B
67 C
...

in each case, you have the integer as i and j - you just add 65 to i, and 48 to j, and turn the integer into a character, and 'concatenate' the result row as character and col as character to get your 'grid reference' like you wanted, and store that string of two characters in the 'demo' array

FoxRoot 10-Nov-14 8:37am

Thank you for the answer but, there are 64 items. 7*7=49. What about others. If a fit every element into 1d array, I will be able to assign the true values(ie. converting ascii is not problem for me.)

Garth J Lancaster 10-Nov-14 8:44am

Yes, but, 0 .. 7 is 8 values - wwhat you have 0..8 is actually a 9 x 9 array

FoxRoot 10-Nov-14 8:48am

Most elements of the new array is either null or -1. Some of them are same as old array. Something is still wrong.

FoxRoot 10-Nov-14 9:12am

public void Doldur ()
{
for (int i = 1; i <=8; i++) {
for (int j = 1; j <=8; j++) {
aktar[grid[i+1][j+1]]= Character.toString((char) (i+64))+ " " + Character.toString((char) (j+48));
}
}
for (int i = 0; i < aktar.length; i++) {
System.out.println(aktar[i]);
}
}

Now it works. Thanks for the psuedo code :) Have a nice day.