Solve 8-tile sliding puzzle

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
8
down vote

favorite












I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.



Advice on how to aproach this would be appreciated.



Code for DFS and printing omitted for clarity:



#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle

 int state[PUZZLE_LENGTH];
 int gapLocation;
;

struct breadthPuzzle

 Puzzle puzzle;
 int parent;
;

const Puzzle SOLVED_PUZZLE = 1,2,3,4,5,6,7,8,EMPTY ;

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)

 int inversions = 0;

 for ( int i = 0; i < PUZZLE_LENGTH; i++ )
 for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
 if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
 inversions++;

 // If the amount of inversions is even the puzzle can be solved
 return inversions % 2 == 0;



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);


bool canNorth(int gapLocation)

 return gapLocation > 2;


bool canEast(int gapLocation)

 return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);


bool canSouth(int gapLocation)

 return gapLocation < 6;


bool canWest(int gapLocation)

 return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);


int north(int gap)

 return gap - 3;


int east(int gap)

 return gap + 1;


int south(int gap)

 return gap + 3;


int west(int gap)

 return gap - 1;


Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)

 int temp = currentPuzzle.state[pos];
 currentPuzzle.state[currentPuzzle.gapLocation] = temp;
 currentPuzzle.state[pos] = EMPTY;
 currentPuzzle.gapLocation = pos;
 return currentPuzzle;


void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)

 Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

 if ( !puzzleExists(currentPuzzle, currentRoute) )
 
 breadthPuzzle candidate currentPuzzle, i ;
 currentRoute.push_back(candidate);
 


void breadthFirst(Puzzle initalPuzzle)

 // Origin has no parent, thus -1 as start.
 vector<breadthPuzzle> breadthVector = initalPuzzle, -1 ;
 int i = 0;

 while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
 
 Puzzle currentPuzzle = breadthVector[i].puzzle;
 int gapLocation = currentPuzzle.gapLocation;

 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
 i++;
 


int main()

 Puzzle toSolve = 1,2,3,4,6,5,8,7,EMPTY, 8 ;
 //Breadth-First: Duration in seconds = 72;
 //Depth-First: Duration in seconds = 15;

 high_resolution_clock::time_point t1 = high_resolution_clock::now();

 if ( isSolvable(toSolve) )
 
 cout << "Puzzle Solvablen";
 breadthFirst(toSolve);
 
 else
 cout << "Puzzle insolvable, stoppingn";

 high_resolution_clock::time_point t2 = high_resolution_clock::now();
 auto durationSec = duration_cast<seconds>(t2 - t1).count();

 cout << "Duration in seconds of function: " << durationSec << endl;




c++ performance algorithm breadth-first-search sliding-tile-puzzle




share|improve this question






















  • Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
    – Toby Speight
    Aug 10 at 12:15

















up vote
8
down vote

favorite












I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.



Advice on how to aproach this would be appreciated.



Code for DFS and printing omitted for clarity:



#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle

 int state[PUZZLE_LENGTH];
 int gapLocation;
;

struct breadthPuzzle

 Puzzle puzzle;
 int parent;
;

const Puzzle SOLVED_PUZZLE = 1,2,3,4,5,6,7,8,EMPTY ;

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)

 int inversions = 0;

 for ( int i = 0; i < PUZZLE_LENGTH; i++ )
 for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
 if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
 inversions++;

 // If the amount of inversions is even the puzzle can be solved
 return inversions % 2 == 0;



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);


bool canNorth(int gapLocation)

 return gapLocation > 2;


bool canEast(int gapLocation)

 return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);


bool canSouth(int gapLocation)

 return gapLocation < 6;


bool canWest(int gapLocation)

 return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);


int north(int gap)

 return gap - 3;


int east(int gap)

 return gap + 1;


int south(int gap)

 return gap + 3;


int west(int gap)

 return gap - 1;


Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)

 int temp = currentPuzzle.state[pos];
 currentPuzzle.state[currentPuzzle.gapLocation] = temp;
 currentPuzzle.state[pos] = EMPTY;
 currentPuzzle.gapLocation = pos;
 return currentPuzzle;


void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)

 Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

 if ( !puzzleExists(currentPuzzle, currentRoute) )
 
 breadthPuzzle candidate currentPuzzle, i ;
 currentRoute.push_back(candidate);
 


void breadthFirst(Puzzle initalPuzzle)

 // Origin has no parent, thus -1 as start.
 vector<breadthPuzzle> breadthVector = initalPuzzle, -1 ;
 int i = 0;

 while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
 
 Puzzle currentPuzzle = breadthVector[i].puzzle;
 int gapLocation = currentPuzzle.gapLocation;

 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
 i++;
 


int main()

 Puzzle toSolve = 1,2,3,4,6,5,8,7,EMPTY, 8 ;
 //Breadth-First: Duration in seconds = 72;
 //Depth-First: Duration in seconds = 15;

 high_resolution_clock::time_point t1 = high_resolution_clock::now();

 if ( isSolvable(toSolve) )
 
 cout << "Puzzle Solvablen";
 breadthFirst(toSolve);
 
 else
 cout << "Puzzle insolvable, stoppingn";

 high_resolution_clock::time_point t2 = high_resolution_clock::now();
 auto durationSec = duration_cast<seconds>(t2 - t1).count();

 cout << "Duration in seconds of function: " << durationSec << endl;




c++ performance algorithm breadth-first-search sliding-tile-puzzle




share|improve this question






















  • Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
    – Toby Speight
    Aug 10 at 12:15













up vote
8
down vote

favorite









up vote
8
down vote

favorite











I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.



Advice on how to aproach this would be appreciated.



Code for DFS and printing omitted for clarity:



#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle

 int state[PUZZLE_LENGTH];
 int gapLocation;
;

struct breadthPuzzle

 Puzzle puzzle;
 int parent;
;

const Puzzle SOLVED_PUZZLE = 1,2,3,4,5,6,7,8,EMPTY ;

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)

 int inversions = 0;

 for ( int i = 0; i < PUZZLE_LENGTH; i++ )
 for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
 if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
 inversions++;

 // If the amount of inversions is even the puzzle can be solved
 return inversions % 2 == 0;



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);


bool canNorth(int gapLocation)

 return gapLocation > 2;


bool canEast(int gapLocation)

 return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);


bool canSouth(int gapLocation)

 return gapLocation < 6;


bool canWest(int gapLocation)

 return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);


int north(int gap)

 return gap - 3;


int east(int gap)

 return gap + 1;


int south(int gap)

 return gap + 3;


int west(int gap)

 return gap - 1;


Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)

 int temp = currentPuzzle.state[pos];
 currentPuzzle.state[currentPuzzle.gapLocation] = temp;
 currentPuzzle.state[pos] = EMPTY;
 currentPuzzle.gapLocation = pos;
 return currentPuzzle;


void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)

 Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

 if ( !puzzleExists(currentPuzzle, currentRoute) )
 
 breadthPuzzle candidate currentPuzzle, i ;
 currentRoute.push_back(candidate);
 


void breadthFirst(Puzzle initalPuzzle)

 // Origin has no parent, thus -1 as start.
 vector<breadthPuzzle> breadthVector = initalPuzzle, -1 ;
 int i = 0;

 while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
 
 Puzzle currentPuzzle = breadthVector[i].puzzle;
 int gapLocation = currentPuzzle.gapLocation;

 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
 i++;
 


int main()

 Puzzle toSolve = 1,2,3,4,6,5,8,7,EMPTY, 8 ;
 //Breadth-First: Duration in seconds = 72;
 //Depth-First: Duration in seconds = 15;

 high_resolution_clock::time_point t1 = high_resolution_clock::now();

 if ( isSolvable(toSolve) )
 
 cout << "Puzzle Solvablen";
 breadthFirst(toSolve);
 
 else
 cout << "Puzzle insolvable, stoppingn";

 high_resolution_clock::time_point t2 = high_resolution_clock::now();
 auto durationSec = duration_cast<seconds>(t2 - t1).count();

 cout << "Duration in seconds of function: " << durationSec << endl;




c++ performance algorithm breadth-first-search sliding-tile-puzzle




share|improve this question














I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.



Advice on how to aproach this would be appreciated.



Code for DFS and printing omitted for clarity:



#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle

 int state[PUZZLE_LENGTH];
 int gapLocation;
;

struct breadthPuzzle

 Puzzle puzzle;
 int parent;
;

const Puzzle SOLVED_PUZZLE = 1,2,3,4,5,6,7,8,EMPTY ;

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)

 int inversions = 0;

 for ( int i = 0; i < PUZZLE_LENGTH; i++ )
 for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
 if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
 inversions++;

 // If the amount of inversions is even the puzzle can be solved
 return inversions % 2 == 0;



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);


bool canNorth(int gapLocation)

 return gapLocation > 2;


bool canEast(int gapLocation)

 return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);


bool canSouth(int gapLocation)

 return gapLocation < 6;


bool canWest(int gapLocation)

 return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);


int north(int gap)

 return gap - 3;


int east(int gap)

 return gap + 1;


int south(int gap)

 return gap + 3;


int west(int gap)

 return gap - 1;


Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)

 int temp = currentPuzzle.state[pos];
 currentPuzzle.state[currentPuzzle.gapLocation] = temp;
 currentPuzzle.state[pos] = EMPTY;
 currentPuzzle.gapLocation = pos;
 return currentPuzzle;


void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)

 Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

 if ( !puzzleExists(currentPuzzle, currentRoute) )
 
 breadthPuzzle candidate currentPuzzle, i ;
 currentRoute.push_back(candidate);
 


void breadthFirst(Puzzle initalPuzzle)

 // Origin has no parent, thus -1 as start.
 vector<breadthPuzzle> breadthVector = initalPuzzle, -1 ;
 int i = 0;

 while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
 
 Puzzle currentPuzzle = breadthVector[i].puzzle;
 int gapLocation = currentPuzzle.gapLocation;

 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
 i++;
 


int main()

 Puzzle toSolve = 1,2,3,4,6,5,8,7,EMPTY, 8 ;
 //Breadth-First: Duration in seconds = 72;
 //Depth-First: Duration in seconds = 15;

 high_resolution_clock::time_point t1 = high_resolution_clock::now();

 if ( isSolvable(toSolve) )
 
 cout << "Puzzle Solvablen";
 breadthFirst(toSolve);
 
 else
 cout << "Puzzle insolvable, stoppingn";

 high_resolution_clock::time_point t2 = high_resolution_clock::now();
 auto durationSec = duration_cast<seconds>(t2 - t1).count();

 cout << "Duration in seconds of function: " << durationSec << endl;





c++ performance algorithm breadth-first-search sliding-tile-puzzle





share|improve this question













share|improve this question




share|improve this question








edited Aug 10 at 12:14









Toby Speight

18.6k13695




18.6k13695










asked Aug 9 at 17:09









Hirtol

433




433











  • Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
    – Toby Speight
    Aug 10 at 12:15

















  • Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
    – Toby Speight
    Aug 10 at 12:15
















Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
– Toby Speight
Aug 10 at 12:15





Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
– Toby Speight
Aug 10 at 12:15











1 Answer
1






active

oldest

votes

















up vote
8
down vote



accepted










Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.






share|improve this answer




















  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f201308%2fsolve-8-tile-sliding-puzzle%23new-answer', 'question_page');

);

Post as a guest

















1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
8
down vote



accepted










Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.






share|improve this answer




















  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16














up vote
8
down vote



accepted










Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.






share|improve this answer




















  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16












up vote
8
down vote



accepted







up vote
8
down vote



accepted






Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.






share|improve this answer












Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.







share|improve this answer












share|improve this answer



share|improve this answer










answered Aug 9 at 18:24









Quuxplusone

10.1k11752




10.1k11752











  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16
















  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16















Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
– Hirtol
Aug 9 at 20:39




Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
– Hirtol
Aug 9 at 20:39




1




1




In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
– Quuxplusone
Aug 10 at 1:16




In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
– Quuxplusone
Aug 10 at 1:16

















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f201308%2fsolve-8-tile-sliding-puzzle%23new-answer', 'question_page');

);

Post as a guest
































































Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being “babysat” by supervisor

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote 31 down vote favorite 4 I hold a PhD in mechanical engineering with a 7 year background in self-guided, self-paced research including 2 years as a graduate level course instructor and a subject matter expert for various engineering projects in a university setting in the United States. For the last 10-11 months, I am working in a research industry in France where my task is to debug C++ spaghetti code written over a period of several years by my current supervisor. It is a team of 2: just I and my supervisor. Diurnally, I am posed with a "bug of the day" to get out of this C++ code. My supervisor generally gives me about 15-30 minutes to solve it and then accosts me about whether or not the task is completed and then rinses and repeats this until the end of the day. Off-late, my supervisor has been holding 6-7 hour long "meetin
Read more

What does second last employer means? [closed]

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address only
Read more

One-line joke

A one-liner is a joke that is delivered in a single line. A good one-liner is said to be pithy - concise and meaningful. [1] Comedians and actors use this comedic method as part of their act, e.g. Jimmy Carr, Tommy Cooper, Rodney Dangerfield, Norm Macdonald, Ken Dodd, Stewart Francis, Zach Galifianakis, Mitch Hedberg, Anthony Jeselnik, Milton Jones, Shappi Khorsandi, Jay London, Mark Linn-Baker, Demetri Martin, Groucho Marx, Dan Mintz, Emo Philips, Tim Vine, Steven Wright and Henny Youngman and Arnold Schwarzenegger. [ citation needed ] Many fictional characters are also known to deliver one-liners, including James Bond, who usually includes pithy and laconic quips after disposing of a villain. [ citation needed ] Examples "A baby seal walks into a club." "A dyslexic man walks into a bra." (Anonymous) "There are three types of people, those who can count and those who can't." "Venison's dear, isn't it?" (Jimmy Carr) "An escala
Read more