- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
I'd be curious to see how Andy wrote an app like that in just 800 bytes.
I know when I was doing x86 assembly in school, it was quite a few bytes just to get "hello world" going.
Admin
Obviously, it's a "whither" or WTFs...
Admin
Solving the difficult problem would not be worthy of anything special, as solving NP Complete problems isn't really that hard.
What's hard is solving NP Complete problems efficiently. If you can create a polynomial-time algorithm to solve this THAT would be worth a lot. But just writing an algorithm that finds the optimal solution isn't that big a deal.
Admin
Qualifier (ullamcorper): "finding the fewest-move solution to the general NxN problem is NP-complete."
Not sure what your distinction between "optimal" and "efficient" might be, but if you can write an algorithm to find the optimal solution for any NP-complete problem you care to pick, I'd be deeply impressed. Particularly if you can somehow manage to make it execute in non-polynomial time.
And particularly if, by "optimal," you mean either "most efficient path" or "fewest-move."
Admin
I don't believe you. Why don't you copy-paste your actual code rather than submit something which doesn't compile?
Admin
In other words, for computers, polynomial-time is assumed.
Even if it's not in the rubric ... ;}
Admin
Hilarious Perl code to find an optimal solution: http://pastebin.com/m5e2bfac0
Admin
... NP Complete ...
Are you sure? The way I always solve the puzzle (in hardware and mushware: i.e. puzzle fysically present and by brain power), I think I use an order-of-n algorithm to get the 1 in the correct position, and then the two etc etc. So I'd say this can be solved in N^3 time.
This may not be optimum, but it's fast. (not O(x^n) or something).
This is weird because such "can always be solved in N^3 time" is non-typical for NP-complete problems. It could still be that the test: "can it be done in X moves?" where X < O(N^3) is NP-complete.
Admin
Admin
NP 3N 1xyz, dang I understand 0^10 of this today.
Admin
That and 68K assembly acts like a high-level low-level language (memory to memory moves).
Admin
For all these people talking about the non-existence of efficent/optimal/whatever solutions to an NP-complete problem:
True, it is not possible to find a polynomial-time algorithm to solve an NP-complete problem (on a non-quantum computer, etc)
But you can and people (like Google, for example) regularly do develop "efficient" or "best" solutions to NP-complete problems.
If your client asks you to write some code to efficiently solve a problem like this one, or the Travelling Salesman, or giving directions on a map, you don't say "I'm sorry, there is no efficient solution!" You write something, maybe using A* that does it as optimally as possible.
If you write it using BFS or random trial and error, you then go and research it and find that so far A* is about the most efficient, optimal algorithm.
Then, for extra credit, you develop a better algorithm, publish your research and win Nobel dog prize at Crufts.
Admin
When you pass 30, a year ago is "recently".
When you pass 50, you find yourself saying, "Yeah, that just happened a few days ago ... oh, wait, it was 1973."
Admin
For all these people talking about the non-existence of efficent/optimal/whatever solutions to an NP-complete problem:
True, it is not possible to find a polynomial-time algorithm to solve an NP-complete problem (on a non-quantum computer, etc)
But you can and people (like Google, for example) regularly do develop "efficient" or "best" solutions to NP-complete problems.
If your client asks you to write some code to efficiently solve a problem like this one, or the Travelling Salesman, or giving directions on a map, you don't say "I'm sorry, there is no efficient solution!" You write something, maybe using A* that does it as optimally as possible.
If you write it using BFS or random trial and error, you then go and research it and find that so far A* is about the most efficient, optimal algorithm.
Then, for extra credit, you develop a better algorithm, publish your research and win Nobel dog prize at Crufts.
Admin
BTW, for those now quibbling about "efficient" versus "solution" to the general NxN problem, I posted a brief (but probably overlooked) clarification to my post, indicating that the word "efficient" needed to be inserted to make it valid. My apologies for introducing confusion on that point.
In this case, there is an algorithm that can find SOME solution that operates in efficient time, as you suggest. However, the "difficult" option in the problem description requires, not just any solution, but the most "path effective" or "fewest move" solution.
This is a case of a problem that's easy (polynomial) if you don't care about the number of moves to solve, and only difficult if you you do.
Compare to the Traveling Salesman: if you don't care about how long your trip is, it's usual trivial to find a way to visit every city. It's only when you say "is there a route less than X long?" that things become icky.
To sum up, yes, that's exactly what is NP-complete.
Admin
No, just nobody cares about your flamebaiting. I assume you're talking about the first post which is clearly C#. Maybe you should go back to Visual Basic if you find it too confusing for you?
Admin
Why so hostile, o' Internet Warrior? What is your problem? I asked a simple question and you act like a spoiled little bitch.
Now, I don't know you (fortunately), but you act like you're frustrated in your life. I condone stupidity, but not bad behavior.
Now, run along.
Admin
I wrote another little quick and dirty python script for this. I really hate making copies of lists of lists, but oh well.
Admin
Just because a problem is NP-complete doesn't mean you can't solve DIFFICULT and generalize the code beyond 3x3. It just means you can't do it in polynomial time. Unless, or course, P=NP, which it does. Been meaning to publish that...
Admin
I would cross post this on Stack Overflow ( Wikified, of course ).
Admin
I reckon the collective noun for WTFs should be a 'project'. Everyone knows what you mean if you tell them you've got a 'project of WTFs'
Admin
-Harrow.
Admin
'Course, though, you're absolutely right. (Which is why I find Programming Pragmata such a waste of time.) If a client asks for "optimal" or "efficient", then you don't piss around with comments about NP-complete.
Optimal, for a client, is however you fit their problem space into their solution space, via their cost space. Intellectually, you'd like to provide a solution that scales with the problem space. Practically, you just code the thing, pick up the big bag o'money, and get out of there.
I freely admit that my crass inability with maths lets me down here. However, I'm not sure that A* is a mathematically optimal solution (either along the dimension of size or that of accuracy) for the entire taxonomy of NP-complete problems. I mean, it can be proved to be admissible and computationally optional (it says here, and I agree) -- but that's just terminology.
Is it better than the Christofides algorithm for the Travelling Salesman Problem (triangle inequality, subdivision)? Is it better all the way up and down the taxonomy? If not, at which point does a polynomial transformation between a particular optimal approximation for one NP-complete problem and another NP-complete problem become worthwhile, rather than just relying on A*?
See, these are the sort of things they never taught me at Cambridge. These are the sort of practical solutions I need to be able to track down.
Not some bleedin' crap about sliding plastic squares around in a grid. Particularly when, half the time, there's no solution anyway.
Admin
It should be a Mud of WTF's.
As support i cite my reference as such: http://www.laputan.org/mud/
So yes, it is a Mud of WTF's
Admin
In the 9-square variant, there are only 362880 possible states, and at most 3 useful state transitions. Doing a breadth-first search within that state space is relatively trivial, and if you want to be really fancy you can keep track of which states you've already been to (in a hash or set or whatever) as a simple optimization.
The 16-square variant, however, is a bit more complex, with 1307674368000 possible states (but still at most only 3 useful transitions).
Admin
Admin
Oh, I hope not. Mostly because I wasn't born until the mid 80's. If I start remembering things from 1973, I will have problems.
Admin
I'm guessing the output shouldn't be a solved puzzle, but rather a series of steps to get to the solved state?
And in x86, it should be possible to get a "hello world" app done pretty quickly - set up the registers, call the BIOS function to output to screen, call MS-DOS function to exit.
Even in Win32, setting up a call to MessageBox shouldn't be too difficult, followed by ExitProcess. Now if you wanted to do a message loop, that'll take some effort!
Still, 800 bytes is impressive, but it's mostly calling Mac Toolbox functions and I'm guessing there's a lot of infrastructure already done for you, so 800 bytes for the guts may not be terribly hard.
Admin
I'm guessing the output shouldn't be a solved puzzle, but rather a series of steps to get to the solved state?
And in x86, it should be possible to get a "hello world" app done pretty quickly - set up the registers, call the BIOS function to output to screen, call MS-DOS function to exit.
Even in Win32, setting up a call to MessageBox shouldn't be too difficult, followed by ExitProcess. Now if you wanted to do a message loop, that'll take some effort!
Still, 800 bytes is impressive, but it's mostly calling Mac Toolbox functions and I'm guessing there's a lot of infrastructure already done for you, so 800 bytes for the guts may not be terribly hard.
Admin
Pretty sure it's C. Stick to Visual Basic and you'll be fine.
Admin
"software"
;oP
Admin
Actually... never mind. I didn't look at it that closely.
I really don't know anymore. (Never mind the misspellings.)
Admin
Bonus 1: What IS the maximum number/depth of scrambles? Bonus 2: How many different starting positions exist at this depth?
If you can not proove it mathematically (I can't!), try graphing depth vs. number of positions and see where it leads. At depth 1 there are 2 possible positions. You can keep a back-trace to ensure that you don't repeat a position. Once you try to repeat a position, you can stop that search vector. This is a small enough problem space that you could create a database of every possible starting position with the shortest moves to take it back to the original position. (Requirement: The solution DB must be stored in a single, enterprisey XML file. The id attribute of the position element must be specified for every possible position.)
It seems like there should be some minimum energy-state related solution to this problem where a given position should naturally decay into the next position closest to the solution. I see difficulty in modeling the blank square with this approach. Maybe if it is a roving black hole...
P.S. Don't use double quotes(_) in your postings! It will Preview, but not Submit!
Admin
Yeah really... that was hard core. I was going to do this in SQL though... but I have better things to do.
Admin
Let's go back to your original post:
Don't act like you're not flamebaiting here. Either that or you've never used C,C++ or Java which all have very similar syntax. If you find that "horrible" then maybe you should stick to (very simple) scripting and avoid any real programming.
Admin
import java.util.Deque; import java.util.HashSet; import java.util.LinkedList; import java.util.Set; public class SlidingPuzzle { public static final String NL = System.getProperty("line.separator"); public final static class PuzzleState { int state[]; int moves[]; int move = 0; int blank = 0; PuzzleState parent; public PuzzleState(PuzzleState parent, int state[], int from, int to) { this.parent = parent; this.state = state; this.blank = to; switch(this.blank) { case 0: this.moves = new int[] { 1, 3 }; break; case 1: this.moves = new int[] { 0, 2, 4 }; break; case 2: this.moves = new int[] { 1, 5 }; break; case 3: this.moves = new int[] { 0, 4, 6 }; break; case 4: this.moves = new int[] { 1, 3, 5, 7 }; break; case 5: this.moves = new int[] { 2, 4, 8}; break; case 6: this.moves = new int[] { 3, 7 }; break; case 7: this.moves = new int[] { 4, 6, 8 }; break; case 8: this.moves = new int[] { 5, 7 }; break; } if (from >= 0) { int tmpMoves[] = new int[this.moves.length - 1]; int i = 0, j = 0; for (; i < this.moves.length; i++) if (this.moves[i] != from) tmpMoves[j++] = this.moves[i]; this.moves = tmpMoves; } } public boolean solved() { for (int i = 0; i < this.state.length - 1; i++) if (state[i] != i + 1) return false; return state[this.state.length - 1] == 0; } public PuzzleState nextState() { if (this.move >= this.moves.length) return null; int newState[] = this.state.clone(); int tmp = newState[this.moves[this.move]]; newState[this.moves[this.move]] = 0; newState[this.blank] = tmp; return new PuzzleState(this, newState, this.blank, this.moves[this.move++]); } @Override public boolean equals(Object obj) { if (!(obj instanceof PuzzleState)) return false; PuzzleState p = (PuzzleState)obj; for (int i = 0; i < this.state.length; i++) if (this.state[i] != p.state[i]) return false; return true; } @Override public int hashCode() { int hash = 0; int offset = 0; for (int i = 0; i < this.state.length; i++) { if (this.state[i] == 0) continue; hash |= this.state[i] << offset; offset += 4; } return hash; } public boolean solvable() { int parity = 0; for (int i = 0; i < this.state.length - 1; i++) { if (this.state[i] <= 1) continue; int count = 0; for (int j = i + 1; j < this.state.length; j++) { if (this.state[j] > 0 && this.state[j] < this.state[i]) count++; } parity += count; } return (parity & 1) == 0; } public Deque<PuzzleState> getStepList() { return this.getStepList(new LinkedList<PuzzleState>()); } private Deque<PuzzleState> getStepList(Deque<PuzzleState> dequeue) { dequeue.addFirst(this); if (this.parent != null) this.parent.getStepList(dequeue); return dequeue; } @Override public String toString() { int c = 0; StringBuilder sb = new StringBuilder(32); for (int i = 0; i < this.state.length - 1; i++) { sb.append(this.state[i]); if (++c < 3) sb.append(" "); else { sb.append(NL); c = 0; } } sb.append(this.state[this.state.length - 1]); return sb.toString(); } } public static void main(String ... args) { Set<Integer> numbers = new HashSet<Integer>(9); if (args.length != 9) { System.out.println("usage example: 8 7 6 5 4 3 2 1 0"); System.exit(0); } int start = 0; int count = 0; int puzzle[] = new int[9]; for (String arg : args) { int number = Integer.parseInt(arg); if (number < 0 || number > 8) { System.err.println("Number: " + number + " is out of range"); System.exit(1); } if (numbers.contains(number)) { System.err.println("Number: " + number + " occurs multiple times"); System.exit(1); } else numbers.add(number); if (number == 0) start = count; puzzle[count++] = number; } Set<PuzzleState> visited = new HashSet<PuzzleState>(1024); Deque<PuzzleState> queue = new LinkedList<PuzzleState>(); PuzzleState ps = new PuzzleState(null, puzzle, -1, start); if (!ps.solvable()) { System.err.printf("Configuration is not solvable%n%n%s%n", ps); System.exit(1); } queue.add(ps); visited.add(ps); while(!queue.isEmpty()) { PuzzleState a, b; a = queue.removeFirst(); if (a.solved()) { int step = 0; for (PuzzleState p : a.getStepList()) { System.out.printf ( "Step: %d%n%s%n%s%n%n", step++, "-------------", p ); } break; } do { b = a.nextState(); if (b != null && !visited.contains(b)) { queue.addLast(b); visited.add(b); } } while (b != null); } } }Admin
Once again, this problem had crappy requirements, the mother of WTFs. By the way what is this "Bring your own code"? I was sue that it was called Programming Praxis before.
captcha: imanidiot
Admin
At any given time for NxN, there is only one empty space. Where r1 < rn < rN, and c1 < cm < cN, and the empty space is (rn, cm), the only possible pieces to move are (rn,cm+1), (rn+1,cm), (rn,cm-1) and (rn-1,cm). Removing candidates in edge cases is trivial.
What, precisely, is the point of using rand()? What next? Regexps? XML?
I could be wrong about these things. Perhaps they're an improved version of "How do you move Mount Fuji?"
(1) Did you read the question? No? Goodbye. (2) Have you considered using recursion? No? Well, we'll wait a while. (3) Can you explain why your solution requires floating-point arithmetic/random numbers/a database/SOAP/regular expressions?
The choice of language here is immaterial.
(2a) Is there a possibility of partitioning the problem?
Off-hand, I can't do that, but I'd like to hear a candidate burble about it.
(4) So your solution takes more than twenty-four hours on an eight-core server. How would you go about fixing that?
Getting it right isn't the issue. Coming up with fatuous partial solutions is.
Admin
I don't think anybody pointed out this WTF: The first poster thinks he's leet because he knows about xot swap!
4th attempt
Admin
Well, now you are Shredder, not Sue, and it's called Bring Your Own Code, not Programming Praxis.
Admin
Requirements, requirements, requirements.
Then: Death March.
There's probably a Wilfred Owen quote around here, but I can't quite reach it through the mud...
Admin
A similar C# solution as the original post (trial and error):
static int[] SolvePuzzle(int[] board) { int hole = 0; Random RNG = new Random(); for (int x = 0; x < board.Length; x++) { if (board[x] == 0) { hole = x; break; } } while (true) { bool done = true; for (int x = 0; x < board.Length; x++) { if (board[x] != ((x + 1) % board.Length)) { done = false; break; } } if (done) { return board; } int swap = hole; while ((swap == hole) || ((swap != (hole - 3)) && (swap != (hole + 3)) && ((swap / 3) != (hole / 3)))) { swap = RNG.Next(board.Length); } board[hole] ^= board[swap]; board[swap] ^= board[hole]; board[hole] ^= board[swap]; hole = swap; } }Note that it does not detect impossible starting configurations, and would simply run forever trying to find a solution.
Admin
Admin
Note - there are impossible starting configurations. Exactly half of the possible starting points can be rearranged to:
123 456 78
and the other half can't. Swapping any two pieces (as in, lifting them out and swapping them over - not sliding them) will convert a solvable problem into an unsolvable one, and vice versa.
There's a classic slidey puzzle which when solved reads:
RATE YOUR MIND PAL
and the trick is to show it to someone, and then jumble it up, quietly putting the second R into the top left corner of the puzzle. Typically the solver will leave it there and try to fit everything else in, but it can't be done. Because the two Rs have been swapped, you're now dealing with an impossible problem.
Admin
My guess is 12345678.
Admin
Puh-lease, this was a one-week assignment in grad school. I happen to have the code kickin' around... It ain't pretty, it's on time!
Here you go, A* implementation of the problem using priority queues, with cross-checking for solvability done up front.
//============================================================================ // Name : main.cpp // Author : Keith Brawner // Version : // Copyright : Keith Brawner // Description : A grid-based maze solver using the A* algorithm //============================================================================
#include <iostream> #include <stdio.h> #include <string.h> #include <vector> #include <stdlib.h> #include <queue> #include <functional> #include <cstdlib> using namespace std;
// Define a struct to hold each point. struct Point { unsigned int x; // x coordinate unsigned int y; // y coordinate };
class Node { public: Point m_Position; unsigned int m_uiYLength; unsigned int m_uiXLength; unsigned int m_uiPriority; std::vector<std::vector<char> > m_Track; std::vector< Point > m_PointsVisited;
};
struct NodeOperatorLesser : public std::binary_function<Node*, Node*, bool> { bool operator()(Node* a, Node* b) const { return a->m_uiPriority < b->m_uiPriority; } };
struct NodeOperatorGreater : public std::binary_function<Node*, Node*, bool> { bool operator()(Node* a, Node* b) const { return a->m_uiPriority > b->m_uiPriority; } };
typedef std::priority_queue< Node*, vector<Node*>, NodeOperatorGreater > my_priority_queue;
void PrintMap(const std::vector<std::vector<char> > & stdMapToPrint, const unsigned int &uiYLength, const unsigned int &uiXLength);
void CopyArray(const std::vector<std::vector<int> > & stdArray, std::vector<std::vector<int> > & stdArrayCopy, const unsigned int & iNumRows, const unsigned int & iNumCols);
bool MoveLeft(const unsigned int & uiYLength, const unsigned int & uiXLength, Node * node); bool MoveRight(const unsigned int & uiYLength, const unsigned int & uiXLength, Node * node); bool MoveDown(const unsigned int & uiYLength, const unsigned int & uiXLength, Node * node); bool MoveUp(const unsigned int & uiYLength, const unsigned int & uiXLength, Node * node);
bool ExistsInQueue(Node *node, my_priority_queue & queueOfNodes);
bool IsSame(Node * NodeOne, Node * NodeTwo);
unsigned int ManhattanDistance(const Point & pntStartPoint, const Point & pntEndPoint);
int main(int argc, char* argv[]) { char cChar; unsigned int uiYLength=0, uiXLength=0; Point pntStart, pntEnd; cout << "\n\n~~~~~ A* Search for Gridded Mazes by Keith Brawner ~~~~~\n\n";
// PrintMap(queueOpenNodes.top()->m_Track, uiYLength, uiXLength);
// cout << "Left possible" << endl; nextPoint.x = currentTopNode->m_Position.x-1; nextPoint.y = currentTopNode->m_Position.y; uiPriority = ManhattanDistance(nextPoint, pntEnd);
// cout << "Right possible" << endl; nextPoint.x = currentTopNode->m_Position.x+1; nextPoint.y = currentTopNode->m_Position.y; uiPriority = ManhattanDistance(nextPoint, pntEnd);
// cout << "Up possible" << endl; nextPoint.x = currentTopNode->m_Position.x; nextPoint.y = currentTopNode->m_Position.y-1; uiPriority = ManhattanDistance(nextPoint, pntEnd);
// cout << "Down possible" << endl; nextPoint.x = currentTopNode->m_Position.x; nextPoint.y = currentTopNode->m_Position.y+1; uiPriority = ManhattanDistance(nextPoint, pntEnd);
}
/** prints the map */ void PrintMap(const std::vector<std::vector<char> > & stdMapToPrint, const unsigned int &uiYLength, const unsigned int &uiXLength) { for(unsigned int i = 0; i < uiYLength; i++) { for(unsigned int j = 0; j < uiXLength; j++) { cout << stdMapToPrint[i][j] << " "; } cout << "\n"; } cout << "\n"; }
/**
bool ExistsInQueue(Node *node, my_priority_queue & queueOfNodes) { bool bReturnValue = false; my_priority_queue queueOfVisittedNodes; while(!queueOfNodes.empty()) { if(bReturnValue==true) { queueOfVisittedNodes.push(queueOfNodes.top()); queueOfNodes.pop(); } else { bool bTemp = IsSame(node, queueOfNodes.top()); if( bTemp == true ) { bReturnValue = true; queueOfVisittedNodes.push(queueOfNodes.top()); queueOfNodes.pop(); } else { queueOfVisittedNodes.push(queueOfNodes.top()); queueOfNodes.pop(); } } } queueOfNodes = queueOfVisittedNodes; return bReturnValue; }
/**
/**
/*
Manhattan distance between 2 points
(absolute value of the sum of the distances) */ unsigned int ManhattanDistance(const Point & pntStartPoint, const Point & pntEndPoint) { unsigned int uiXDistance = abs((int)pntStartPoint.x - (int)pntEndPoint.x); unsigned int uiYDistance = abs((int)pntStartPoint.y - (int)pntEndPoint.y);
return uiXDistance + uiYDistance; }
/**
bool MoveRight(const unsigned int & uiYLength, const unsigned int & uiXLength, Node * node) { if( node->m_Position.x+1 >= uiXLength ) { return false; } else if(node->m_Track[node->m_Position.y ][node->m_Position.x + 1 ] == 'x' || node->m_Track[node->m_Position.y ][node->m_Position.x + 1 ] == 'O') { return false; } else { return true; } }
bool MoveUp(const unsigned int & uiYLength, const unsigned int & uiXLength, Node * node) { if( (int)(node->m_Position.y-1) < 0 ) { return false; } else if(node->m_Track[node->m_Position.y - 1 ][node->m_Position.x ] == 'x' || node->m_Track[node->m_Position.y - 1 ][node->m_Position.x ] == 'O') { return false; } else { return true; } }
bool MoveDown(const unsigned int & uiYLength, const unsigned int & uiXLength, Node * node) { if( node->m_Position.y+1 >= uiYLength ) { return false; } else if(node->m_Track[node->m_Position.y + 1 ][node->m_Position.x ] == 'x' || node->m_Track[node->m_Position.y + 1 ][node->m_Position.x ] == 'O') { return false; } else { return true; } }
11 9
_ _ _ _ g _ _ _ _
x x x _ s _ x x x
_ _ _ x _ x _ _ _ _ _ x _ _ _ x _ _ _ x _ _ _ _ _ x _ x _ _ _ _ _ _ _ x
Admin
wheres the beef? I come here for wtf and get homework instead? borring
Admin
OOOPPPPSSSS. Sorry about that, that was A* used to solve a maze...
Here is BestFirst (A*) to solve the 8-puzzle
//============================================================================ // Name : IterativeDeepening.cpp // Author : Keith Brawner // Version : // Copyright : Keith Brawner // Description : Hello World in C++, Ansi-style //============================================================================
#include <iostream> #include <stdio.h> #include <string.h> #include <vector> #include <stdlib.h> #include <queue> #include <functional> using namespace std;
#define FILENAME "config.txt"
class Node { public: int m_iNumRows; int m_iNumCols; std::vector<std::vector<int> > m_stdArray; int m_iPriority; int m_iLevel; std::string m_strAllPreviousMoves;
};
struct NodeOperatorGreater : public std::binary_function<Node*, Node*, bool> { bool operator()(Node* a, Node* b) const { return a->m_iPriority > b->m_iPriority; } };
typedef std::priority_queue< Node*, vector<Node*>, NodeOperatorGreater > my_priority_queue; /typedef std::priority_queue< Node, std::vector<Node*>, compare_node_pointers > my_priority_queue ; // use object(s) of type my_priority_queue where r*/
int IsSolution(const std::vector<std::vector<int> > & stdArray, const std::vector<std::vector<int> > & stdAnswerArray, const unsigned int & iNumRows, const unsigned int & iNumCols);
bool IsSame(const std::vector<std::vector<int> > & stdArray, const std::vector<std::vector<int> > & stdAnswerArray, const unsigned int & iNumRows, const unsigned int & iNumCols);
void FindPosition(const std::vector<std::vector<int> > & stdArray, int iNumberToFind, int & iReturni, int & iReturnj, const unsigned int & iNumRows, const unsigned int & iNumCols);
bool MoveUp(std::vector<std::vector<int> > & stdArray, const unsigned int & iNumRows, const unsigned int & iNumCols, const unsigned int & iX, const unsigned int & iY, const unsigned int & iLevel);
bool MoveDown(std::vector<std::vector<int> > & stdArray, const unsigned int & iNumRows, const unsigned int & iNumCols, const unsigned int & iX, const unsigned int & iY, const unsigned int & iLevel);
bool MoveLeft(std::vector<std::vector<int> > & stdArray, const unsigned int & iNumRows, const unsigned int & iNumCols, const unsigned int & iX, const unsigned int & iY, const unsigned int & iLevel);
bool MoveRight(std::vector<std::vector<int> > & stdArray, const unsigned int & iNumRows, const unsigned int & iNumCols, const unsigned int & iX, const unsigned int & iY, const unsigned int & iLevel);
void PrintArray(const std::vector<std::vector<int> > & stdArrayToPrint, const unsigned int & iNumRows, const unsigned int & iNumCols);
void CopyArray(const std::vector<std::vector<int> > & stdArray, std::vector<std::vector<int> > & stdArrayCopy, const unsigned int & iNumRows, const unsigned int & iNumCols);
bool IsSolvable(const std::vector<std::vector<int> > & stdArray, const std::vector<std::vector<int> > & stdAnswerArray, const unsigned int & iNumRows, const unsigned int & iNumCols);
int InversionAmount(const std::vector<int> & stdStartVector, const std::vector<int> & stdAnswerVector, const unsigned int & iSize, const int & iNumber, const unsigned int & iNumberPos);
bool ExistsInQueue(Node *node, my_priority_queue & queueOfNodes);
int main() { unsigned int iNumRows=0, iNumCols=0; // cout << "Iterative Deepening by Keith Brawner \n\n";
// cout << iValue; } fscanf(fp, ") "); } fscanf(fp, ")\n");
// cout << iValue; } fscanf(fp, ") "); } fscanf(fp, ")\n");
// cout << "\nThe initial array is:\n"; // for(unsigned int i = 0; i < iNumRows; i++) // { // for(unsigned int j = 0; j < iNumCols; j++) // { // cout << stdStartArray[i][j] << " "; // } // cout << "\n"; // } // // cout << "\nThe final array is:\n"; // for(unsigned int i = 0; i < iNumRows; i++) // { // for(unsigned int j = 0; j < iNumCols; j++) // { // cout << stdEndArray[i][j] << " "; // } // cout << "\n"; // }
// if( IsSolution(stdStartArray, stdEndArray, iNumRows, iNumCols) == 0 ) // { // cout << "The goal and end are the same\n"; // cout << "(PATH-TO-GOAL (NONE))\n"; // }
// if(iPriority == 0) // { // cout << "HOORAY, the goal and the start are the same... Save me a lot of work, really\n\n"; // return EXIT_SUCCESS; // }
// cout << "Push: " << MoveUP->m_strAllPreviousMoves << "\n"; // PrintArray(stdArrayToMove, iNumRows, iNumCols); } else { delete MoveUP; MoveUP = NULL; } }
// cout << "Push: " << MoveDOWN->m_strAllPreviousMoves << "\n"; // PrintArray(stdArrayToMove, iNumRows, iNumCols); } else { delete MoveDOWN; MoveDOWN = NULL; } }
// cout << "Push: " << MoveLEFT->m_strAllPreviousMoves << "\n"; // PrintArray(stdArrayToMove, iNumRows, iNumCols); } else { delete MoveLEFT; MoveLEFT = NULL; } }
// cout << "Push: " << MoveRIGHT->m_strAllPreviousMoves << "\n"; // PrintArray(stdArrayToMove, iNumRows, iNumCols); } else { delete MoveRIGHT; MoveRIGHT = NULL; } }
}
/** returns the heuristic manhattan distance between stdArray and stdAnswerArray */ int IsSolution(const std::vector<std::vector<int> > & stdArray, const std::vector<std::vector<int> > & stdAnswerArray, const unsigned int & iNumRows, const unsigned int & iNumCols) { int iReturnValue = 0; int iDistanceI = -1; int iDistanceJ = -1; for(unsigned int i = 0; i < iNumRows; i++) { for(unsigned int j = 0; j < iNumCols; j++) { FindPosition(stdAnswerArray, stdArray[i][j], iDistanceI, iDistanceJ, iNumRows, iNumCols);
// cout << "\n\n"; // PrintArray(stdArray, iNumRows, iNumCols); // PrintArray(stdAnswerArray, iNumRows, iNumCols); // cout << "Heuristic is: " << iReturnValue << "\n\n";
}
bool IsSame(const std::vector<std::vector<int> > & stdArray, const std::vector<std::vector<int> > & stdAnswerArray, const unsigned int & iNumRows, const unsigned int & iNumCols) { for(unsigned int i = 0; i < iNumRows; i++) { for(unsigned int j = 0; j < iNumCols; j++) { if(stdArray[i][j] != stdAnswerArray[i][j]) { return false; } } } return true; }
void FindPosition(const std::vector<std::vector<int> > & stdArray, int iNumberToFind, int & iReturni, int & iReturnj, const unsigned int & iNumRows, const unsigned int & iNumCols) { iReturni = -1; iReturnj = -1; for(unsigned int i = 0; i < iNumRows; i++) { for(unsigned int j = 0; j < iNumCols; j++) { if(stdArray[i][j] == iNumberToFind) { iReturni = i; iReturnj = j; return; } } } }
/**
Returns True if moving the '*' Up by one results in a possible move
and modifies the array to reflect an upward move */ bool MoveUp(std::vector<std::vector<int> > & stdArray, const unsigned int & iNumRows, const unsigned int & iNumCols, const unsigned int & iX, const unsigned int & iY, const unsigned int & iLevel) { if(iX != 0) { cout << '(' << iLevel << " UP)\n";
} else return false; }
/**
/**
/**
/** prints the array */ void PrintArray(const std::vector<std::vector<int> > & stdArrayToPrint, const unsigned int & iNumRows, const unsigned int & iNumCols) { for(unsigned int i = 0; i < iNumRows; i++) { for(unsigned int j = 0; j < iNumCols; j++) { cout << stdArrayToPrint[i][j] << " "; } cout << "\n"; } cout << "\n"; }
bool ExistsInQueue(Node *node, my_priority_queue & queueOfNodes) { bool bReturnValue = false; my_priority_queue queueOfVisittedNodes; while(!queueOfNodes.empty()) { if(bReturnValue==true) { queueOfVisittedNodes.push(queueOfNodes.top()); queueOfNodes.pop(); } else { bool bTemp = IsSame(node->m_stdArray, queueOfNodes.top()->m_stdArray, node->m_iNumRows, node->m_iNumCols); if( bTemp == true ) { bReturnValue = true; queueOfVisittedNodes.push(queueOfNodes.top()); queueOfNodes.pop(); } else { queueOfVisittedNodes.push(queueOfNodes.top()); queueOfNodes.pop(); } } } queueOfNodes = queueOfVisittedNodes; return bReturnValue; }
void CopyArray(const std::vector<std::vector<int> > & stdArray, std::vector<std::vector<int> > & stdArrayCopy, const unsigned int & iNumRows, const unsigned int & iNumCols) { for(unsigned int i = 0; i < iNumRows; i++) { for(unsigned int j = 0; j < iNumCols; j++) { stdArrayCopy[i][j] = stdArray[i][j]; } } }
bool IsSolvable(const std::vector<std::vector<int> > & stdStartArray, const std::vector<std::vector<int> > & stdAnswerArray, const unsigned int & iNumRows, const unsigned int & iNumCols) { int iNumberOfInversions = 0; int iStartPositionI = -1, iStartPositionJ = -1, iAnswerPositionI = -1, iAnswerPositionJ = -1;
// cout << "Inversions: " << iNumberOfInversions << "\n"; // cout << "StartPosition: " << iStartPositionI << " " << iStartPositionJ << "\n"; // cout << "EndPosition: " << iAnswerPositionI << " " << iAnswerPositionJ << "\n";
}
//returns the how many numbers as supposed to come before iNumber (in start) // but instead come after iNumber (in End) int InversionAmount(const std::vector<int> & stdStartVector, const std::vector<int> & stdAnswerVector, const unsigned int & iSize, const int & iNumber, const unsigned int & iNumberPosInStartArray) { int iReturnValue = 0; int iNumberPosInEndArray = 0;
// cout << "#inversions return" << iReturnValue << "\n"; return iReturnValue; } ------------------------------------------------------------------------------------------------------------------------------------------------INPUT---------------------------------------------------------------------------------------------------------------------------------------------------------------- (3 3) ((1 2 3) (4 7 5) (6 8 *)) ((1 2 3) (4 5 6) (7 8 *))
Admin
DUH!!
Admin