My solver has odd worst-case-scenarios

[LB]

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}}

[ne555]

¿why can't you use Dijkstra?

[LB]

I'm trying to write a solver w/o any prior knowledge, to pass time :p

[Script Coder]

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?

[Paoletti301]

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.

[N36fSL3A]

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?

[Lachlan Easton]

@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.

[N36fSL3A]

Oh, thanks for clearing that up for me.

[LB]

@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.

[ResidentBiscuit]

^{[sub][small]Interesting...}[/sub][/small]

Yea this isn't working heh

[naraku9333]

^{_{yes it does}}
[sup ][sub ][small ]yes it does[/small][/sub][/sup] Your closing tags are in the wrong order.

[Script Coder]

@Resident Biscuit Just interested, have you ever coded in html/xml before?

[LB]

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|$

[Cubbi]

Just because boost.graph library needs more exposure

#include <string>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
#include <chrono>
#include <boost/lexical_cast.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

int main()
{
    using namespace boost;
    typedef adjacency_list<listS, vecS, directedS, no_property,
                           property<edge_weight_t, int>> graph_t;
    graph_t g;

    std::ifstream f("test.txt");
    std::vector<std::string> 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<int>(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<graph_t>::vertex_descriptor vertex_descriptor;
    std::vector<vertex_descriptor> p(num_vertices(g)); // predecessors
    std::vector<int> 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<double, std::milli> dur = time_2 - time_1;

    // print the results
    std::stack<vertex_descriptor> 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)

[ResidentBiscuit]

@ScriptCoder, never touched it. Someday I should learn some of these web languages.....

[LB]

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?

[Script Coder]

<html>
<body>
<bold>
word
<italics>
another

Is "another" in bold or not?

[ne555]

nope

<html>
   <body>
      <bold>
         word
      </>
      <italics>
         another
      </>
   </>
</>

[Script Coder]

@ne555
it could be:

<html>
     <body>
         <bold>
             world
                 <italics>
                      another
                 </>
           </>
       </>
</>

[LB]

It would be lovely if HTML allowed using </> instead of respecifying the full tag name.