iumzlinol
BAN USERBelow is my C++ solution. For each string of length n there are 3^(n-1) expressions.
$ c++ wallprimes.cpp -o wallprimes
$ ./wallprimes 2 011 12345
6
64
#include <iostream>
#include <string>
#include <cstddef>
#include <cstdlib>
int count = 0;
bool is_wallprime(int n)
{
return n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0;
}
void count_wallprimes(int result, std::string n, const std::string& str, size_t index)
{
if (index < str.length())
{
// first digit uses no operator
if (index > 0)
{
count_wallprimes(result + atoi(n.c_str()), std::string("+") + str[index], str, index + 1);
count_wallprimes(result + atoi(n.c_str()), std::string("-") + str[index], str, index + 1);
}
count_wallprimes(result, n + str[index], str, index + 1);
}
else
{
// add or subtract remaining digits
result += atoi(n.c_str());
if (is_wallprime(result))
count++;
}
}
int main(int argc, char** argv)
{
for (int i = 2; i < argc; i++)
{
count = 0;
int result = 0;
std::string n("0");
size_t index = 0;
count_wallprimes(result, n, argv[i], index);
std::cout << count << std::endl;
}
return 0;
}
Below is a C++11 solution that finds the shortest path using backtracking. The code is quite fast as it immediately abandons any partial solution that is larger than a previously found partial solution. This implementation uses depth first search and works best with sparse matrices. For dense matrices an implementation based on breadth first search runs faster.
$ c++ -std=c++11 shortest_path.cpp -o shortest_path
$ ./shortest_path
[0][0], [1][0], [2][1], [1][2], [0][3], [0][4], [0][5], [1][6], [0][7], [1][8], [2][9],
[3][9], [4][8], [5][7], [4][6], [4][5], [4][4], [5][3], [4][2], [4][1], [5][0], [6][0],
[7][0], [8][1], [7][2], [7][3], [7][4], [7][5], [8][6], [7][7], [7][8], [8][9],
- iumzlinol November 02, 2013