Sorting parcels (a 2-dimensional array)

[Courecity72]

This is AMAZING! Thank you very much!
But how would I define these arrows?

[dhayden]

Damn Damn damn. Now you guys have got me thinking about this problem. :)

Here's a straightforward to get a decent result:
- bubble sort each row: exchange east-west pairs until every package is in the right column.
- bubble sort each column: exchange north-south pairs until each package is in the right place.

You can do some optimizations to this: for example, if two adjacent rows are sorted, then you can exchange N-S to move pieces closer.

The only other thought is fairly obvious: you can quickly compute a lower bound on the best solution by finding the farthest distance that must be travelled.

[Duthomhas]

The simple 2D bubblesort is inefficient [O(nⁿ)].

The lower bound is the minimum cost (number of steps) -- the sum of these costs I've called the "chaos".

Remember, this is an optimizations algorithm (or dynamic algorithm), requiring consideration of multiple cost branches... so a straightforward algorithm will do well, but the purpose is to find an optimal solution.

Finding said solution should also be done optimally, but you could simply brute-force it and still have a valid algorithm. (Turning in a brute-force algorithm will get you a failing grade, though.)

[dhayden]

The simple 2D bubblesort is inefficient [O(nⁿ)].

I think I"m looking at it differently. This looks to me like a hardware problem where the goal is to minimize the time required to get the answer, not the total number of swaps. In other words, imagine that at each clock tick, you can do a bunch of simultaneous exchanges. The goal to minimize the number of ticks, not the number of exchanges. I think you've called the ticks "transitions" and the number of exchanges "cost". Have I got that right?

If the goal is to minimize the transitions then a bubblesort is O(n²) since it's simply 2 O(n²) sorts. In fact, since you can do simultaneous swaps, bubble sort might actually be O(n).

That certainly isn't optimal and I'll think of other ways to do it.

[Duthomhas]

IDK if anyone is still thinking about this, but I made a toy y'all might like:

parcels.tcl
https://drive.google.com/file/d/0B899E-_p1Gt-R1ZqS2wtWkhjbUk/view?usp=sharing

You'll need a wish interpreter (version 8.6) to use it. If you are on *nix, you should have it already. If you are on Windows (or your Linux box doesn't have it), you'll need to get it.

Two options:
  • ActiveTcl http://www.activestate.com/activetcl
  • Tclkit http://tclkits.rkeene.org/fossil/wiki/Downloads

Enjoy!

[Courecity72]

@Duoas : This is amazing! I wrote a bit of code too, but it doesn't really work. Would you mind having a look at it?

#include <iostream>                             
#include <fstream>                              
#include <string>
#include <sstream>
#include <vector>


static const int ARRAY_SIZE = 3;

struct Parcel
	{
		int goalY;
		int goalX;
		bool exchanged;
		bool atDest;
	};

Parcel city[ARRAY_SIZE][ARRAY_SIZE];
Parcel cityMap[ARRAY_SIZE][ARRAY_SIZE];
//std::pair <int, int> *city = 0; dyn. Array
void sortArray(bool isSorted);
bool arrayCheck();
int cellCheck(int cellY, int cellX);



//_________________//INT MAIN()//_________________//
int main()
{
	std::string filename;
	std::cout << "Please enter the name of the file to open:"<<std::endl;
	std::cin >> filename;
	std::vector<std::string> teile;
	std::ifstream file;                          
	file.open(filename, std::ios::in);      

	while(!file)
		{
			std::cout << "Error: Couldn't open file!\n\n";
			std::cout << "Please enter the name of the file to open:"<<std::endl;
			std::cin >> filename;
			file.open(filename, std::ios::in);
		}
	
	                                     
		std::string zahl;
		int x = 0;
		int y = 0;
		unsigned int i = 1;
		
		while (file.good()) 
		{              
			
			std::getline(file, zahl);
			std::string buffer; //Buffer-String
			std::stringstream stream(zahl); 
			
			
			
			while (stream >> buffer)
				teile.push_back(buffer);
		}

		
		
		
		while (i < teile.size())
		{
			y = std::stoi(teile[i]);
			i++;
			x = std::stoi(teile[i]);
			i++;
			city[y][x].goalY = std::stoi(teile[i]);
			city[y][x].exchanged = false;
			i++;
			city[y][x].goalX = std::stoi(teile[i]);
			i++;
		}
	
		for (int i = 0; i < ARRAY_SIZE; ++i)
		{
			for (int j = 0; j < ARRAY_SIZE; ++j)
			{
				std::cout << city[i][j].goalY << '/';
				std::cout << city[i][j].goalX << ' ';
				cityMap[i][j].goalY = city[i][j].goalY; 
				cityMap[i][j].goalX = city[i][j].goalX;
			}
			std::cout << std::endl;
		}

		std::cout << std::endl;
		sortArray(false);

	

	std::cin.ignore();
	std::cin.get();
	return 0;
}



//_________________//SORT//_________________//
void sortArray(bool isSorted)
{
	int swapDir = 0;

	while(!isSorted)
	{
		for (int i = 0; i < ARRAY_SIZE; i++) 
		{
			for (int j = 0; j < ARRAY_SIZE; j++) 
			{
							
				swapDir = cellCheck(i,j);

				switch (swapDir)
				{
				case 1: std::swap(city[i][j].goalY,city[i - 1][j].goalY);
						std::swap(city[i][j].goalX,city[i - 1][j].goalX); //North
						city[i][j].exchanged = true;
						city[i - 1][j].exchanged = true;
					break;
				case 2: std::swap(city[i][j].goalY,city[i + 1][j].goalY);
						std::swap(city[i][j].goalX,city[i + 1][j].goalX); //South
						city[i][j].exchanged = true;
						city[i + 1][j].exchanged = true;
					break;
				case 3: std::swap(city[i][j].goalY,city[i][j + 1].goalY);
						std::swap(city[i][j].goalX,city[i][j + 1].goalX); //East
						city[i][j].exchanged = true;
						city[i][j + 1].exchanged = true;
					break;
				case 4: std::swap(city[i][j].goalY,city[i][j - 1].goalY);
						std::swap(city[i][j].goalX,city[i][j - 1].goalX); //West
						city[i][j].exchanged = true;
						city[i][j - 1].exchanged = true;
					break;
				default: 
					break;
				}
			}
		}
		
//_________________//Direction//_________________//
		
		for (int n = 0; n < ARRAY_SIZE; n++)
		{
			for (int k = 0; k < ARRAY_SIZE; k++)
			{
			
				if (!city[n][k].exchanged)
				{
					std::cout << "_";
				}
				else if (cityMap[n][k].goalY == city[n + 1][k].goalY && cityMap[n][k].goalX == city[n + 1][k].goalX && (n + 1) < ARRAY_SIZE)
				{
					std::cout << "S";
				}
				else if (cityMap[n][k].goalY == city[n - 1][k].goalY && cityMap[n][k].goalX == city[n - 1][k].goalX && (n - 1) > -1)
				{
					std::cout << "N";
				}
				else if (cityMap[n][k].goalY == city[n][k + 1].goalY && cityMap[n][k].goalX == city[n][k + 1].goalX && (k + 1) < ARRAY_SIZE)
				{
					std::cout << "E";
				}
				else if (cityMap[n][k].goalY == city[n][k - 1].goalY && cityMap[n][k].goalX == city[n][k - 1].goalX && (k - 1)>-1 )
				{
					std::cout << "W";
				}

				
			}

		}
		
		
//_________________//Array//_____________________//

		std::cout << std::endl << std::endl;
		for (int i = 0; i < ARRAY_SIZE; i++) 
		{
			for (int j = 0; j < ARRAY_SIZE; j++) 
			{
			
				std::cout << city[i][j].goalY << "/";
				std::cout << city[i][j].goalX << " " ;
				cityMap[i][j].goalY = city[i][j].goalY; 
				cityMap[i][j].goalX = city[i][j].goalX;
				city[i][j].exchanged = false;				
			}

			std::cout << std::endl;
		}

		
		std::cout<<std::endl;
		isSorted = arrayCheck();
		
		std::cin.get();
	}
  }

//_________________//CELL CHECK//_________________//
  int cellCheck(int cellY, int cellX)
{
	int direction = 0;
	int nWestX = cellX - 1; 
	int nEastX = cellX + 1; 
	int nNorthY = cellY - 1; 
	int nSouthY = cellY +1;  

	if (city[cellY][cellX].goalY <= nNorthY - 1 && nNorthY - 1 >= 0 )
	{
		if( !city[nNorthY][cellX].exchanged && !city[cellY][cellX].exchanged)
		{
			
				direction = 1;
			
		}
	}

	else if (city[cellY][cellX].goalY >= nSouthY + 1 && nSouthY + 1 < ARRAY_SIZE)
	{
		
		if (!city[nSouthY][cellX].exchanged && !city[cellY][cellX].exchanged)
		{
			
				direction = 2;
			
		}
		

	}

	else if (city[cellY][cellX].goalX >= nEastX + 1 && nEastX + 1 < ARRAY_SIZE)
	{

		if (!city[cellY][nEastX].exchanged && !city[cellY][cellX].exchanged && nEastX < ARRAY_SIZE)
		{
		
				direction = 3; 
			 
		}

	}

	else if (city[cellY][cellX].goalX <= nWestX - 1 && nWestX - 1 >= 0 )
	{
		if (!city[cellY][nWestX].exchanged && !city[cellY][cellX].exchanged && nWestX >= 0 )
		{
			direction = 4;	
		}
	}

	else
	{
		if(city[cellY][cellX].goalY <= city[nNorthY][cellX].goalY && nNorthY >= 0 )
		{
			if (!city[nNorthY][cellX].exchanged && !city[cellY][cellX].exchanged)
			{
				direction = 1; 
			}
		}

		else if(city[cellY][cellX].goalY >= city[nSouthY][cellX].goalY && nSouthY < ARRAY_SIZE)
		{
			if (!city[nSouthY][cellX].exchanged && !city[cellY][cellX].exchanged)
			{
					direction = 2; 				 
			}
		}

		else if(city[cellY][cellX].goalX >= city[cellY][nEastX].goalX && nEastX < ARRAY_SIZE)
		{
			if (!city[cellY][nEastX].exchanged && !city[cellY][cellX].exchanged)
			{				
					direction = 3; 				
			}
		}

		else if(city[cellY][cellX].goalX <= city[cellY][nWestX].goalX && nWestX >= 0)
		{
			if (!city[cellY][nWestX].exchanged && !city[cellY][cellX].exchanged)
			{				
				direction = 4; 				
			}
		}
	}

	
	return direction;
}

//_________________//TEST//_________________//
bool arrayCheck()
{
	int errors = 0;
	for (int i = 0; i < ARRAY_SIZE;i++)
	{
		for (int j = 0; j < ARRAY_SIZE; j++)
		{
			if (city[i][j].goalY != i || city[i][j].goalX != j)
			{
				errors++;
				city[i][j].atDest = false;
			}
			else if (city[i][j].goalY == i || city[i][j].goalX == j)
			{
				city[i][j].atDest = true;
			}

		}
	}
	if (errors != 0)
	{
		return false;
	}
	else
	{
		return true;
	}
}

[Courecity72]

The problem I'm facing atm is that it gets stuck in an infinite loop because it swaps the same two parcels over and over again...

[Duthomhas]

When you wish to swap a cell, you should never move it opposite its arrow. It is okay to move it perpendicular, but again, never against the direction it wishes to go.

[Courecity72]

But how would I check for this?

[Duthomhas]

Okay, here's some commentary for you.

I am not sure why you have two city maps. (I think the additional one is messing up your clarity.) You only need one.

I am also unsure of your extra fields in the Parcel:

struct Parcel
	{
		int goalY;
		int goalX;
		bool exchanged;  //?
		bool atDest;     //?
	};

You do not need to track whether or not a parcel has been exchanged.
You only need to care if it is at its final destination (the 'goal') or not. (And you do not need a flag to remember that.)

What might be useful is directional tokens¹. As part of the algorithm, you will encounter the need to move parcels that are already in their correct row or column.

For your initial example:

0,1   1,0   0,2 
 →    ↓ ←       
                
1,1   2,0   1,2 
 →    ↓ ←       
                
2,2   2,1   0,0 
 →→        ↑↑ ←←

That parcel in cell 2,2 has to move a total of four cells. It needs to move now if you are to obtain your the potential best result of four moves.

One way to start (and this is not the only one) is to make sure that each cell with arrows does move at least one cell.

0,1▶◀1,0   0,2                 1,0   0,1   0,2 
 →    ↓ ←                        ↓              
                                                
1,1▶◀2,0   1,2        -->      2,0   1,1   0,0 
 →    ↓ ←    ▼                   ↓          ↑ ←←
             ▲                                  
2,2▶◀2,1   0,0                 2,1   2,2   1,2 
 →→        ↑↑ ←←                 →     →     ↑  

The next thing to notice is that we now have a clear loop -- almost.
Fortunately, we can borrow arrows from the last cell with arrows and carry them along to cells without arrows. (You can do this in any order, but here are the two choices.):

1,0   0,1   0,2                 1,0   0,1   0,2 
 ↓    [←]                        ↓    [←]   [←] 
                                                
2,0   1,1   0,0                 2,0   1,1   0,0 
 ↓    [↑]   []←                  ↓          ↑[] 
                                                
2,1   2,2   1,2                 2,1   2,2   1,2 
 →     →     ↑                   →     →     ↑  

Conveniently, we can now move cells along that complete loop.
(The resulting configuration requires only two simple transitions to solve.)

The purpose of the toy I made for you was so that you² could play with these patterns and see how to design your algorithm to choose to move cells.

1. The arrows can easily be calculated instead of stored as additional fields. Do whichever is more convenient; I doubt there is any computational difference either way.

2. I actually made it so I could play with it, but it was cool enough I decided to share. :O)

Hope this helps.

[Courecity72]

I get what you mean, but I'm somehow not able to translate it to code... Well, guess I'm just too dumb ;)
Thanks anyways!

[Duthomhas]

It's a tough question.

And you are right: the hard part is telling the computer how to analyze the board and decide what to do next.

The purpose of the toy I posted was for that very objective -- so that I can use my brain to learn how to solve the problem best, what metrics help me to understand the next move, etc. Now that I have a better understanding of the steps to solve the problem, I can begin to write code that will:
- analyze the board
- decide on a course of action
- perform that action

You'll notice the little "undo" button on the toy as well. This is because the solution to the problem is not straight-forward -- it requires you to choose among a number of possibilities. The "best" answer takes some fiddling. What this means is that you need to keep track of multiple states of the board (meaning, you'll need a good amount of memory):
- the current state plus all "undo" states leading to the current state
- the best answer so far.
Straight to code that is a vector<board> for each of those:

  vector <board> current;
  vector <board> best;

Your algorithm should modify the current. When it finally solves the problem, if current.size() < best.size() then copy current to best.

Once your algorithm has finished all the ways it wants to permute current, the best should be returned.

The board itself does not need to be very large in memory. A carefully-indexed vector of pairs of coordinates should do:

struct parcel
{
  int row;
  int col;
  parcel( int row = 0, int col = 0 ): row(row), col(col) { }
};

struct board: public vector <parcel>
{
  int rows;
  int cols;

  // index a parcel by row and column:
  parcel& operator () ( int row, int col ) { return (*this)[ row * cols + col ]; }
};

Etc. Hope this helps.