### My solver has odd worst-case-scenarios

Pages: 12
For most mazes mine takes under a second, but this particular maze costs my solver over a minute:
 ```125499256931647 3168434313598|2 581|58673473353 665145165879445 1|238247736|729 75391815125|7|7 9919899119|4568 91|78335|6989|9 38281387783|861 |268183249|354\$ ```
The numbers represent how expensive a tile is, the pipes are walls, and the dollar sign is the goal. You must start in the top left corner.

I am yet to debug my solver to see why this particular arrangement is so expensive on time.

(In case you're interested, this is my solver: https://www.dropbox.com/s/clruww60hmlctyp/Main.java )
https://gist.github.com/LB--/5864799#file-maze-solving-L154
Last edited on
¿why can't you use Dijkstra?
I'm trying to write a solver w/o any prior knowledge, to pass time :p
You don't know Dijkstra?
Anyway, are you using brute force? or a greedy solution? (from your code, it looks like a brute force) and yes those tend to take long times on most data sets, even with certain optimisations, there are certain cases (like the one you mentioned) where the optimisations are useless. Maybe you could find an optimization for this type of maze?
what type of maze is that?
I'm just guessing that maybe every time you move you add the value of the space you just went on and try to get the lost amount of "points"?
I'm just really curious.
How'd you get your text that small?

Can't look at your code atm but you say the number represents the cost of the tile, I'm trying to figure if there's a variable for money?
@Fredbill: Higher cost meaning harder (or less desirable) to cross. For example in a video game it would cost less for an AI character to walk along a footpath than wade through mud.
Oh, thanks for clearing that up for me.
@Script Coder: I know the name of the person but not the algorithm. I am using a brute force with optimizations that prevent it from doing things pointlessly (e.g. it gives up if it's already found a cost higher than an existing solution, and gives up if there's no path to the goal e.g. it boxed itself in).

@Paoletti301: It's a tile cost maze.

@Fredbill30: There are the [small] tags, the [sub] tags, and the [sup] tags - combine all three and you have ultra tiny text.
[sub][small]Interesting...[/sub][/small]

Yea this isn't working heh
Last edited on
yes it does
[sup ][sub ][small ]yes it does[/small][/sub][/sup] Your closing tags are in the wrong order.
Last edited on
@Resident Biscuit Just interested, have you ever coded in html/xml before?
I made a couple optimizations and now a maze that took 1000+ seconds to solve now takes less than 10 seconds to solve. With this new code I've found another maze that takes 33+ seconds to solve.

Code: https://www.dropbox.com/s/clruww60hmlctyp/Main.java
33+ second maze:
 ```193947277636999 178313231476569 547347||||46562 533296622674275 8753367462975|2 51198142|552479 834536513257|47 5432|99792433|8 8544384474325|7 9|72927936726|\$```
Just because boost.graph library needs more exposure

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374`` ``````#include #include #include #include #include #include #include #include #include int main() { using namespace boost; typedef adjacency_list> graph_t; graph_t g; std::ifstream f("test.txt"); std::vector maze; for(std::string line; f >> line;) maze.push_back(line); std::size_t nrows = maze.size(); std::size_t ncols = maze[0].size(); // todo check if all are the same int target_pos = 0; for(std::size_t row = 0; row < maze.size(); ++row) for(std::size_t col = 0; col < maze[row].size(); ++col) { // special cases if(maze[row][col] == '|') continue; // wall if(maze[row][col] == '\$') { // goal maze[row][col] = '0'; target_pos = row*ncols + col; } // the weight of this node int w = lexical_cast(maze[row][col]); // edges leading to this location have the weight 'w' if(row > 0 && maze[row-1][col] != '|') get(edge_weight, g)[add_edge( (row-1) * ncols + col , row*ncols+col, g).first] = w; if(row < nrows-1 && maze[row+1][col] != '|') get(edge_weight, g)[add_edge( (row+1) * ncols + col , row*ncols+col, g).first] = w; if(col > 0 && maze[row][col-1] != '|') get(edge_weight, g)[add_edge( row * ncols + (col-1), row*ncols+col, g).first] = w; if(col < ncols-1 && maze[row][col+1] != '|') get(edge_weight, g)[add_edge( row * ncols + (col+1), row*ncols+col, g).first] = w; } std::cout << "Loaded the " << ncols << "x" << nrows << " maze as a graph with " << num_vertices(g) << " nodes\n"; // call Dijkstra typedef graph_traits::vertex_descriptor vertex_descriptor; std::vector p(num_vertices(g)); // predecessors std::vector d(num_vertices(g)); // distances vertex_descriptor start = vertex(0, g); // starting point vertex_descriptor goal = vertex(target_pos, g); auto time_1 = std::chrono::high_resolution_clock::now(); dijkstra_shortest_paths(g, start, predecessor_map(&p[0]).distance_map(&d[0])); auto time_2 = std::chrono::high_resolution_clock::now(); std::chrono::duration dur = time_2 - time_1; // print the results std::stack path; for(vertex_descriptor v = goal; v != start; v = p[v]) path.push(v); path.push(start); std::cout << "Total weight of the shortest path: " << d[target_pos] << '\n' << "The number of steps: " << path.size() << '\n'; while(!path.empty()) { int pos = path.top(); std::cout << '[' << pos / ncols << ',' << pos % ncols << "] "; path.pop(); } std::cout << "\nIt took " << dur.count() << " ms to calculate\n"; }``````

output:
 ```\$ ./test Loaded the 15x10 maze as a graph with 150 nodes Total weight of the shortest path: 92 The number of steps: 26 [0,0] [1,0] [2,0] [2,1] [3,1] [3,2] [3,3] [4,3] [4,4] [4,5] [5,5] [5,6] [5,7] [6,7] [6,8] [6,9] [5,9] [5,10] [5,11] [5,12] [5,13] [6,13] [6,14] [7,14] [8,14] [9,14] It took 0.019746 ms to calculate ```

(I should probably add the weight of the start node.. depending on what you're counting)
@ScriptCoder, never touched it. Someday I should learn some of these web languages.....
XML and HTML are horrid formats, the redundancy is off the charts. So you open a tag by specifying it's name, and you close a tag by specifying it's name, but you can't have overlapping tags so why specify it's name to close it?
 ``123456`` `````` word another``````

Is "another" in bold or not?
nope
 ``12345678910`` `````` word another ``````
@ne555
it could be:
 ``12345678910`` `````` world another ``````
It would be lovely if HTML allowed using </> instead of respecifying the full tag name.
Pages: 12