Sorting parcels (a 2-dimensional array)
Pages: 12
Hello everybody,
for a school project I need to develop a program which reads a number of coordinates from a .txt file
, stores them in a 2d array and later "moves" them to their "destination" step by step (so first east and then north or sth. like this) however, for each cell in the array there should be a line in a new .txt file where it is written in which direction said cell has thrown the parcel.
All parcels have to be swapped (or not) at the same time and there always has to be exactly one parcel in each cell.
So far the reading and storing in an array works, but now I've got no idea on how to get the sorting to work. Problem is that our task will be a 100x100 array, so it has to be time efficient too...
Does anybody here have an idea on how to accomplish this? (I don't want code, just some ideas ;) ).
(If something is not clear from my description please feel free to ask as I'm terribly bad at describing things)
Thank you in advance,
Courecity
for a school project I need to develop a program which reads a number of coordinates from a .txt file
|
|
, stores them in a 2d array and later "moves" them to their "destination" step by step (so first east and then north or sth. like this) however, for each cell in the array there should be a line in a new .txt file where it is written in which direction said cell has thrown the parcel.
|
|
All parcels have to be swapped (or not) at the same time and there always has to be exactly one parcel in each cell.
So far the reading and storing in an array works, but now I've got no idea on how to get the sorting to work. Problem is that our task will be a 100x100 array, so it has to be time efficient too...
Does anybody here have an idea on how to accomplish this? (I don't want code, just some ideas ;) ).
(If something is not clear from my description please feel free to ask as I'm terribly bad at describing things)
Thank you in advance,
Courecity
Last edited on
What level course is this? Because it isn't that simple of a problem. That and your problem statement is not very clear.
This is similar to solving a Rubik's cube, swapping adjacent cells (right?) until they are in the final location?
What algorithm are you considering to help solve the problem?
This is similar to solving a Rubik's cube, swapping adjacent cells (right?) until they are in the final location?
What algorithm are you considering to help solve the problem?
You're right, I *might* have chosen the wrong sub-forum to post this question, as it is a pretty advanced course.
Sorry for being unclear, basically imagine a city where the houses are aligned perfectly in a square. Now some drones are delivering one parcel to each house, but they messed up and delivered the parcels to the wrong adresses. Now every houseowner climbs onto his roof, collects the parcel and has a look where its destination point is. After that they throw it to one of their neighbours either east, west, north, south or he doesn't throw it at all (but all of them do their action at the same time) so that again every owner has a parcel. Now this is repeated until every parcel is at its destination. So it's not like a rubics cube, as one could decide to throw his parcel north while his neighbour in the same row decides to throw it west.
As for the algorithm I thought about using a simple Bubblesort as a foundation because it only compares neighbouring cells, but the runtime of this algorithm is too bad to actually solve this problem in an adequate amount of time, so thats basically my question here, do you know a faster algorithm which I could use as a foundation?
Sorry for being unclear, basically imagine a city where the houses are aligned perfectly in a square. Now some drones are delivering one parcel to each house, but they messed up and delivered the parcels to the wrong adresses. Now every houseowner climbs onto his roof, collects the parcel and has a look where its destination point is. After that they throw it to one of their neighbours either east, west, north, south or he doesn't throw it at all (but all of them do their action at the same time) so that again every owner has a parcel. Now this is repeated until every parcel is at its destination. So it's not like a rubics cube, as one could decide to throw his parcel north while his neighbour in the same row decides to throw it west.
As for the algorithm I thought about using a simple Bubblesort as a foundation because it only compares neighbouring cells, but the runtime of this algorithm is too bad to actually solve this problem in an adequate amount of time, so thats basically my question here, do you know a faster algorithm which I could use as a foundation?
Nevertheless, I think you can safely ignore bubblesort.
What algorithms have you been reviewing in class? Chances are good that one of them is the basis for the solution to this problem. (If you are unsure, list them, and I'll help you choose one.)
Last edited on
| What algorithms have you been reviewing in class? Chances are good that one of them is the basis for the solution to this problem. |
Sadly not this time, as this is an extra task for those who are interested in doing a bit more than which is taught in school, but we basically had all kinds of sorting algorithms (Mergesort, Insertionsort, Combsort, of course Bubblesort, ...), as well as the Bellman-Ford-Algorithm, Djisktras algorithm and DFS and BFS.
We touched on that topic while covering the Bellman-Ford algorithm, but we didn't cover it extensively.
I admit I haven't spent too much time looking at it, but now that I am, I wonder if we're not over-complicating it.
The bubble-sort might actually be along the right lines...
Here are the issues:
A parcel cannot be moved except to an immediately adjacent cell, and only by swapping with that cell.
This means that you cannot reduce time to any less than the minimum distance a parcel must move.
For example, your cell (2 2) must move to cell (0 0), making a minimum number of four swaps required. This characteristic is the same as with the bubble sort.
The trick, as you noted originally, is adapting the bubble logic to your 2D, simultaneous-action problem.
The primary issue, I think, will be that you are now working in two dimensions and not just one, so it may be possible (and I don't know this for sure, since I haven't thought any about it yet) to choose a direction at each juncture that will solve the problem with more moves than another direction might have.
What you need to do is design an algorithm that allows you calculate every possible choice and identify the one that performs best. (Essentially, you need to compute a Cayley graph.)
Once you have that data for a number of different problems (you can generate any number of them with random combinations), you can make a conjecture about how to choose the best paths. (And this is where dynamic programming may come in, but since you haven't touched on it, I suspect a greedy algorithm might do.)
If I've got free time I'll play with it too.
The bubble-sort might actually be along the right lines...
Here are the issues:
A parcel cannot be moved except to an immediately adjacent cell, and only by swapping with that cell.
This means that you cannot reduce time to any less than the minimum distance a parcel must move.
For example, your cell (2 2) must move to cell (0 0), making a minimum number of four swaps required. This characteristic is the same as with the bubble sort.
The trick, as you noted originally, is adapting the bubble logic to your 2D, simultaneous-action problem.
The primary issue, I think, will be that you are now working in two dimensions and not just one, so it may be possible (and I don't know this for sure, since I haven't thought any about it yet) to choose a direction at each juncture that will solve the problem with more moves than another direction might have.
What you need to do is design an algorithm that allows you calculate every possible choice and identify the one that performs best. (Essentially, you need to compute a Cayley graph.)
Once you have that data for a number of different problems (you can generate any number of them with random combinations), you can make a conjecture about how to choose the best paths. (And this is where dynamic programming may come in, but since you haven't touched on it, I suspect a greedy algorithm might do.)
If I've got free time I'll play with it too.
Ah shit, I just realized that I misunderstood a bit of the task. The cells do not have to swap with their adjacent cells, they just can't give thier parcels to a diagonal cell...
That means cell1 could give its parcel to its western neighbour, but the neigbour doesn't hav to hand its parcel over to cell1.
That means cell1 could give its parcel to its western neighbour, but the neigbour doesn't hav to hand its parcel over to cell1.
No, but I thought that
Upon reading the task again carefully I discovered that it doesn't have to swap parcels with said cell, but there still mustn't be more than one parcel per cell.
| A parcel cannot be moved except to an immediately adjacent cell, and only by swapping with that cell. |
Upon reading the task again carefully I discovered that it doesn't have to swap parcels with said cell, but there still mustn't be more than one parcel per cell.
So it is still a cell-swap, but with any two cells?
And only in north-south or east-west direction?
And only in north-south or east-west direction?
Last edited on
As I said, I'm terribly bad at explaining stuff... Here's a graphical version of how the parcels could be sorted for my example.
https://gyazo.com/71a4a9168ea1d9d283de886fc74c2c5e
https://gyazo.com/71a4a9168ea1d9d283de886fc74c2c5e
Okay, so I've been looking at this. My current understanding is this:
1. Any cell can move it's parcel to any adjacent neighbor (NSEW).
2. Every cell must have exactly one parcel -- an outgoing parcel must be balanced with an incoming parcel.
3. The goal of the assignment is to find an optimal solution -- defined as the minimum number of simultaneous transitions... at least cost.
optimal solution vs any solution
The whole point behind algorithms is to find "optimal solutions". In many instances, there may be more than one optimal solution, and for many classes of problems we don't actually know what the true optimal solution is (or if it exists). The point is to find a reasonably close to optimal solution.
cost analysis
The purpose is because these algorithms are applied to doing things that cost money. In your example problem, that translates to the amount of time the entire group of people must be standing on the roof chucking boxes at each other. Ideally, a person should have to throw and catch as few boxes as possible...
Hence, I am not enamored of your professor's solution because it minimizes transitions without regard to cost. (I am defining cost as the total number of individual moves. For example, to swap two cells requires a single transition composed of two simultaneous moves -- the cost is 2.)
Here's an ASCII infographic for you :O)
You will notice that the current cost of the board can be calculated as what I've (blithely) called "chaos": the sum of the distances each parcel must travel. This "chaos" has a 1:2 ratio with the maximal number of moves needed to solve the system.
You'll notice that your professor's solution increases the amount of chaos (or cost) in the system. I haven't given any thought as to why his algorithm does that... (and I don't care). You'll also notice that solution 2, while it does not increase the amount of chaos, nevertheless increases the final cost to worse than your professor's solution!
Solution 1 is an optimal solution because it has minimal cost.
methodology
For such a small dataset, it is possible to simply calculate every solution to find the optimal one. But as you know, this is an O(nⁿ) problem, so adding a few rows is exponentially detrimental to a brute-force computation.
The goal, then, is to try to develop a method that only moves us closer to an optimal solution -- that is, it should not ever decrease the "chaos".
For example, a common subproblem is a parcel two steps out of place in the same direction, but the adjacent parcel is already in its final location. By simply swapping the two, you do not increase the "chaos" of the system, but you do move it toward a solvable state.
Some backtracking is acceptable.
Well, I hope this helps move you along. Let me know what you think.
Do this by identifying subproblems that can be solved easily. Be prepared to backtrack.
1. Any cell can move it's parcel to any adjacent neighbor (NSEW).
2. Every cell must have exactly one parcel -- an outgoing parcel must be balanced with an incoming parcel.
3. The goal of the assignment is to find an optimal solution -- defined as the minimum number of simultaneous transitions... at least cost.
optimal solution vs any solution
The whole point behind algorithms is to find "optimal solutions". In many instances, there may be more than one optimal solution, and for many classes of problems we don't actually know what the true optimal solution is (or if it exists). The point is to find a reasonably close to optimal solution.
cost analysis
The purpose is because these algorithms are applied to doing things that cost money. In your example problem, that translates to the amount of time the entire group of people must be standing on the roof chucking boxes at each other. Ideally, a person should have to throw and catch as few boxes as possible...
Hence, I am not enamored of your professor's solution because it minimizes transitions without regard to cost. (I am defining cost as the total number of individual moves. For example, to swap two cells requires a single transition composed of two simultaneous moves -- the cost is 2.)
Here's an ASCII infographic for you :O)
the initial state 0,1 1,0 0,2 1,1 2,0 1,2 2,2 2,1 0,0 chaos 12 your professor's solution: 4 transitions, 20 moves □ → ← □ □ ↓ □ → ← → ← □ □ ↓ ← □ □ ↑ □ → ← → ← □ □ → ↑ → ← □ □ → ← □ □ □ chaos 14 chaos 10 chaos 4 chaos 0 solution 1: 4 transitions, 14 moves → ← □ □ □ □ □ □ □ ↓ □ □ → ← □ □ □ □ ↓ □ □ ↑ □ □ □ → ← → ← □ ↑ → ← □ □ □ chaos 8 chaos 6 chaos 2 chaos 0 solution 2: 4 transitions, 22 moves → ← □ ↓ ← □ → ↓ □ ↓ □ □ → ← ↓ ↓ ↑ ← ↑ ← □ ↑ □ □ □ □ ↑ → → ↑ □ → ← □ □ □ chaos 8 chaos 6 chaos 2 chaos 0 |
You will notice that the current cost of the board can be calculated as what I've (blithely) called "chaos": the sum of the distances each parcel must travel. This "chaos" has a 1:2 ratio with the maximal number of moves needed to solve the system.
You'll notice that your professor's solution increases the amount of chaos (or cost) in the system. I haven't given any thought as to why his algorithm does that... (and I don't care). You'll also notice that solution 2, while it does not increase the amount of chaos, nevertheless increases the final cost to worse than your professor's solution!
Solution 1 is an optimal solution because it has minimal cost.
methodology
For such a small dataset, it is possible to simply calculate every solution to find the optimal one. But as you know, this is an O(nⁿ) problem, so adding a few rows is exponentially detrimental to a brute-force computation.
The goal, then, is to try to develop a method that only moves us closer to an optimal solution -- that is, it should not ever decrease the "chaos".
For example, a common subproblem is a parcel two steps out of place in the same direction, but the adjacent parcel is already in its final location. By simply swapping the two, you do not increase the "chaos" of the system, but you do move it toward a solvable state.
Some backtracking is acceptable.
Well, I hope this helps move you along. Let me know what you think.
Do this by identifying subproblems that can be solved easily. Be prepared to backtrack.
Heh, just found a good example.
The correct solution depends on what the actual costs are. Does it cost more to have more transitions or more moves?
0,0 2,0 0,2 1,1 1,2 0,1 1,0 2,1 2,2 chaos 8 4 transitions, 14 moves (more time, less work) □ ↓ □ □ □ □ □ → ↓ □ ↓ ↓ □ ↑ □ → ← □ ↓ ↑ ← □ ↑ ↑ □ □ □ □ □ □ ↑ □ □ □ □ □ chaos 8 chaos 6 chaos 4 chaos 0 3 transitions, 20 moves (less time, more work) → ↓ □ → ← □ □ ↓ □ ↑ ↓ □ ↓ ← ← ↓ ↑ ↓ ↑ ← □ → → ↑ ↑ □ ↑ chaos 10 chaos 6 chaos 0 |
The correct solution depends on what the actual costs are. Does it cost more to have more transitions or more moves?
OK, good, that makes life a lot easier.
Here's a suggested strategy: try to equalize things according to the most most number of 'arrows', preferring opposing arrows when possible.
That is, every parcel that needs moving must move in some combination of directions: north, south, east, and west; which are representable with simple arrows: ↑, ↓, →, and ←.
So parcel 0,0 at 1,2 needs to move {N,W,W}, or {↑,←,←} (order is not important).
The cells 2,0 (parcel 0,1) and 0,2 (parcel 1,0) both have double arrows. Swap them in the direction they need to go.
Also, cells 2,1 and 2,2 (parcels 2,2 and 2,1) have a single, opposing angles. Fix them too.
That leaves your board as:
How you proceed from here is up to you, but the same strategy applies best: cells 0,1 and 1,1 (parcels 1,0 and 0,2) both have opposing arrows: swap them.
Repeat and repeat:
This strategy works pretty well in general.
Circles, unless they are a complete path, are typically a more expensive version of simpler swaps.
Hope this helps.
Here's a suggested strategy: try to equalize things according to the most most number of 'arrows', preferring opposing arrows when possible.
That is, every parcel that needs moving must move in some combination of directions: north, south, east, and west; which are representable with simple arrows: ↑, ↓, →, and ←.
So parcel 0,0 at 1,2 needs to move {N,W,W}, or {↑,←,←} (order is not important).
Example (with 'arrows') ┌─────┬─────┬─────┐ │ 0,0 │ 1,1 │ 1,0 │ │ │ ↓ │ ←←↓ │ ├─────┼─────┼─────┤ │ 2,0 │ 0,2 │ 1,2 │ │ │ →↑ │ │ ├─────┼─────┼─────┤ │ 0,1 │ 2,2 │ 2,1 │ │ →↑↑ │ → │ ← │ └─────┴─────┴─────┘ |
The cells 2,0 (parcel 0,1) and 0,2 (parcel 1,0) both have double arrows. Swap them in the direction they need to go.
Also, cells 2,1 and 2,2 (parcels 2,2 and 2,1) have a single, opposing angles. Fix them too.
That leaves your board as:
┌─────┬─────┬─────┐ │ 0,0 │ 1,0 │ 1,1 │ │ │ ←↓ │ ←↓ │ ├─────┼─────┼─────┤ │ 0,1 │ 0,2 │ 1,2 │ │ →↑ │ →↑ │ │ ├─────┼─────┼─────┤ │ 2,0 │ 2,1 │ 2,2 │ │ │ │ │ └─────┴─────┴─────┘ |
How you proceed from here is up to you, but the same strategy applies best: cells 0,1 and 1,1 (parcels 1,0 and 0,2) both have opposing arrows: swap them.
Repeat and repeat:
┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐
│ 0,0 │ 0,2 │ 1,1 │ │ 0,0 │ 1,1 │ 0,2 │ │ 0,0 │ 0,1 │ 0,2 │
│ │ → │ ←↓ │ │ │ ↓ │ │ │ │ │ │
├─────┼─────┼─────┤ ├─────┼─────┼─────┤ ├─────┼─────┼─────┤
│ 0,1 │ 1,0 │ 1,2 │ │ 1,0 │ 0,1 │ 1,2 │ │ 1,0 │ 1,1 │ 1,2 │
│ →↑ │ ← │ │ │ │ ↑ │ │ │ │ │ │
├─────┼─────┼─────┤ ├─────┼─────┼─────┤ ├─────┼─────┼─────┤
│ 2,0 │ 2,1 │ 2,2 │ │ 2,0 │ 2,1 │ 2,2 │ │ 2,0 │ 2,1 │ 2,2 │
│ │ │ │ │ │ │ │ │ │ │ │
└─────┴─────┴─────┘ └─────┴─────┴─────┘ └─────┴─────┴─────┘
step 2 step 3 step 4
(done) |
This strategy works pretty well in general.
Circles, unless they are a complete path, are typically a more expensive version of simpler swaps.
Hope this helps.
Last edited on
Pages: 12