CODEWITHSUNDEEP
algorithmshortest-pathuniform
cobie
cobie

Reputation: 7271

Uniform Cost search project euler #81

I am working on project euler programs for the sake of 'enlightenment' not just solving them. I have solved question 81 using dynamic progam on the 80x80 matrix but when I try to solve it using uniform cost search my program disappears into never land. I just want to know if this problem tractable using uniform cost search? The problem is available at this link.

Upvotes: 1

Views: 2546

Answers (2)

dinox0r
dinox0r

Reputation: 16039

Here (as a reference) is a solution using Uniform-cost search in c++, compiled with -O2 takes less than a second on a i7 (without optimizations takes 3 secs):

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
struct Node { 
    size_t i, j; int cost;
    Node(size_t i, size_t j, int cost) : i(i), j(j), cost(cost) {}
};
bool operator<(const Node& a, const Node& b) { return b.cost < a.cost; }
bool operator==(const Node& a, const Node& b) { return a.i == b.i && a.j == b.j; }

int main() {
    const size_t SIZE = 80;
    ifstream fis("matrix.txt");
    int matrix[SIZE][SIZE];
    char crap;
    for (size_t i = 0; i < SIZE; i++)
        for (size_t j = 0; j < SIZE; j++) {
            fis >> matrix[i][j];
            if (j < SIZE - 1) fis >> crap;
        }
    vector<Node> open;
    set<Node> closed;
    open.push_back(Node(0, 0, matrix[0][0]));
    make_heap(open.begin(), open.end());
    while (!open.empty()) {
        Node node = open.front();
        pop_heap(open.begin(), open.end()); open.pop_back();

        if (node.i == SIZE - 1 && node.j == SIZE - 1) {
            cout << "solution " << node.cost << endl;
            return 0;
        }
        closed.insert(node);
        Node children[] = { Node(node.i + 1, node.j, node.cost + matrix[node.i + 1][node.j]),
                            Node(node.i, node.j + 1, node.cost + matrix[node.i][node.j + 1]) };
        for (int k = 0; k < 2; k++) { 
            Node child = children[k];
            if (!closed.count(child)) {
                vector<Node>::iterator elem = find(open.begin(), open.end(), child);
                if (elem == open.end()) { 
                    open.push_back(child); push_heap(open.begin(), open.end());
                } else if (child.cost < (*elem).cost) {
                    (*elem).cost = child.cost;
                    make_heap(open.begin(), open.end());
                }
            }
        }
    }
}

This solution would be little slow because it calls make_heap for element replacement in the open node list which rebuilds the heap in the vector, but shouldn't go to forever land and proves that the problem can be solved with UCS. A suggestion is to debug your solution using the base case given in Project Euler problem statement.

Upvotes: 1

user541686
user541686

Reputation: 210437

UCS definitely works.

from Queue import PriorityQueue
with open('matrix.txt') as f:
    data = map(lambda s: map(int, s.strip().split(',')), f.readlines())
seen = set()
pq = PriorityQueue()
pq.put((data[0][0], 0, 0))
while not pq.empty():
    (s, i, j) = pq.get()
    if (i, j) not in seen:
        seen.add((i, j))
        if i + 1 < len(data):    pq.put((s + data[i + 1][j], i + 1, j))
        if j + 1 < len(data[i]): pq.put((s + data[i][j + 1], i, j + 1))
        if i + 1 >= len(data) and j + 1 >= len(data): print s

Upvotes: 3

Related Questions