# Longest mathematical expression in a grid

Given a grid which contains these signs: 0..9, x, =, write the fastest code that outputs the longest string of connected (horizontally, vertically, and diagonally adjacent), distinct cells which is a mathematically valid expression formed on this grammar:

E := T '=' T
T := F 'x' T | F
F -> {0..9}+


More formally, a solution will have this form: an equality between a product of terms:

S = F0 x .. x Fp = Fp+1 x .. x Fn

I define N(S) = Max_i(F_i)

If two strings of the same length need to be compared, then I will compare their largest multiplicand. i.e. 30x3=90 < 33x3=99 because 90 < 99

## The grids

Grid 0: 3 x 3

13x
=73
481


which contains: 13x37=481

Grid 1: 7 x 9

6996640
1127=39
186=940
8329706
3683980
6349307
75x19x0
5065350
0051900


which contains:

a=611333
b=599999
c=494687
d=531337
and a*b=366799188667
and c*d=262845506519


Grid 2: 8 x 8

1851x412
40081737
72330964
14461858
17604=67
89653745
13612200
14433193


Grid 3: 16 x 16

0951x71=7=41659x
958525855332=25x
8462=1x119191x76
993928209055089x
1523060251420490
=883152021094970
0146645532106152
87x96=294=x80675
7960948222x0440x
x577x987x0993241
29564563x=x5=800
03508x17050=6565


OK so after a short discussion in the comment sections, I am adding a few restrictions to allow me to do a fair comparison of solutions:

I will run the solution on my Macbook Pro which is 2,4 GHz Core 2 Duo running Mavericks. The language you are going to propose needs to be running natively on my computer, but fortunately, a lot of languages are available on OS X.

I will measure the quality of a program by comparing the time taken to find my hidden solution. Your program will probably find strings that are even longer that the one I hid in the first place, but this can not be avoided as I would need a program that enumerates all the solution of the grids I'm going to submit.. and this is the reason of this code golf..

• Do you mean the largest factor (in which case presumably it's the largest factor of the value of each side of the =) or the largest multiplicand? – Peter Taylor Jun 25 '14 at 15:33
• Ah one more thing. It may well be the case that some solutions won't be able to solve your larger grids. To not exclude them from the competition, you could do the following: add grids of regularly increasing sizes (say, 3x3, 4x4, 5x5, ... 15x15). Then the winner is the program that can handle the largest size in 10/30/60 minutes (some fixed time, depends on how long you want to the programs to run on your machine). If multiple programs tie at the same size, the tie is broken by actual runtime. This makes it also fairer to add new test cases, when submissions solve the largest size. – Martin Ender Jun 25 '14 at 16:26
• I am currently writing a program that generates those grids. Just a few minutes.. Please comment on the comparison of strings of the same length. – user3585425 Jun 25 '14 at 16:34
• In the expression A × B = C, A is the multiplier, B is the multiplicand, and C is the product. Did you want the sum with the largest product, perhaps? – squeamish ossifrage Jun 25 '14 at 18:49
• @squeamishossifrage No, the specification is quite clear I think. In A x B = C x D, he wants the solution with largest maximum among A, B, C, D. You could call it "factor" instead of "multiplicand" but, as Peter Taylor commented, that suggests that he's looking for the product with the largest prime factor. (At least that's how I understood him.) – Martin Ender Jun 25 '14 at 20:16

# C, checks about 7,500,000 paths per second

So here is my first pass over this. It's quite horrible code because it's all in one huge main and the two (nested) loops over the left-hand side and right-hand-side of the equation are pretty much exactly the same, but well, it works.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define MAX_SIZE 32

typedef struct {
char symbol;
int visited;
} cell;

typedef struct {
int x;
int y;
} coord;

static cell grid[MAX_SIZE][MAX_SIZE];
static int nEquals = 0;
static coord equals[MAX_SIZE*MAX_SIZE];

static coord dirs[8] = {
{ .x = -1, .y = -1 },
{ .x =  0, .y = -1 },
{ .x =  1, .y = -1 },
{ .x =  1, .y =  0 },
{ .x =  1, .y =  1 },
{ .x =  0, .y =  1 },
{ .x = -1, .y =  1 },
{ .x = -1, .y =  0 },
};

static char best_string[2*MAX_SIZE*MAX_SIZE+1];
static int best_length = 0;
static unsigned long long best_factor;

int main(int argc, char *argv[])
{
FILE *fp = fopen("grid.txt", "r");
if (!fp) perror("Memory allocation failed"), exit(1);

fseek(fp, 0L, SEEK_END);
long lSize = ftell(fp);
rewind(fp);

char *buffer = calloc(1, lSize+1);
if (!buffer)
{
fclose(fp);
perror("Memory allocation failed");
exit(1);
}

if (1 != fread(buffer, lSize, 1, fp))
{
fclose(fp);
free(buffer);
exit(1);
}

fclose(fp);

char *cp;
cp = buffer;
int width = (int)strtol(cp, &cp, 10);
int height = (int)strtol(cp, &cp, 10);

++cp;
int i, j;
for (j = 0; j < height; ++j)
{
for (i = 0; i < width; ++i)
{
grid[j][i].symbol = *cp;
grid[j][i].visited = 0;

if (*cp == '=')
{
equals[nEquals].x = i;
equals[nEquals].y = j;
++nEquals;
}
++cp;
}
++cp;
}

printf("Analysing %d x %d grid...\n", width, height);

unsigned long long strings_checked = 0;

clock_t start = clock();

for (j = 0; j < nEquals; ++j)
{
char expression[2*MAX_SIZE*MAX_SIZE+1];
coord lpos = equals[j];
coord rpos = equals[j];

// Set to spaces to ease parsing
for (i = 0; i < 2*MAX_SIZE*MAX_SIZE+1; ++i)
expression[i] = ' ';

int center = MAX_SIZE*MAX_SIZE;
expression[center] = '=';

int lhs_size = 0;
int lhs_n_factors = 0;

int lhs_dirs[MAX_SIZE*MAX_SIZE];
for (i = 0; i < MAX_SIZE*MAX_SIZE; ++i)
lhs_dirs[i] = -2;
int rhs_dirs[MAX_SIZE*MAX_SIZE];
for (i = 0; i < MAX_SIZE*MAX_SIZE; ++i)
rhs_dirs[i] = -2;

unsigned long long lhs_factors[MAX_SIZE*MAX_SIZE];
unsigned long long lhs_max_factors[MAX_SIZE*MAX_SIZE];
unsigned long long lhs_products[MAX_SIZE*MAX_SIZE];
lhs_max_factors[0] = 0;
lhs_products[0] = 1;

while (lhs_size >= 0)
{
int dir = ++lhs_dirs[lhs_size];
char lmost_char = expression[center-lhs_size];

if (dir == -1)
{
grid[lpos.y][lpos.x].visited = 1;

if (lmost_char == 'x')
{
unsigned long long factor = strtoll(expression+center-lhs_size + 1, NULL, 10);
lhs_factors[lhs_n_factors] = factor;
++lhs_n_factors;
if (factor > lhs_max_factors[lhs_n_factors-1])
lhs_max_factors[lhs_n_factors] = factor;
else
lhs_max_factors[lhs_n_factors] = lhs_max_factors[lhs_n_factors-1];
lhs_products[lhs_n_factors] = lhs_products[lhs_n_factors-1] * factor;
continue;
}
else if (lmost_char == '=')
continue;
else
{
unsigned long long factor = strtoll(expression+center-lhs_size, NULL, 10);
unsigned long long max_lhs_factor;
if (factor > lhs_max_factors[lhs_n_factors])
max_lhs_factor = factor;
else
max_lhs_factor = lhs_max_factors[lhs_n_factors];

unsigned long long lhs_product = lhs_products[lhs_n_factors] * factor;

int rhs_size = 0;

int rhs_n_factors = 0;
unsigned long long max_rhs_factor = 0;

unsigned long long rhs_factors[MAX_SIZE*MAX_SIZE];
unsigned long long max_factors[MAX_SIZE*MAX_SIZE];
unsigned long long rhs_products[MAX_SIZE*MAX_SIZE];
max_factors[0] = max_lhs_factor;
rhs_products[0] = 1;

char *rhs_factor_pointers[MAX_SIZE*MAX_SIZE];
rhs_factor_pointers[0] = expression+center+1;

while (rhs_size >= 0)
{
int dir = ++rhs_dirs[rhs_size];
char rmost_char = expression[center+rhs_size];

if (dir == -1)
{
grid[rpos.y][rpos.x].visited = 1;

if (rmost_char == 'x')
{
factor = strtoll(rhs_factor_pointers[rhs_n_factors], NULL, 10);
rhs_factors[rhs_n_factors] = factor;
++rhs_n_factors;
rhs_factor_pointers[rhs_n_factors] = expression + center + rhs_size + 1;
if (factor > max_factors[rhs_n_factors-1])
max_factors[rhs_n_factors] = factor;
else
max_factors[rhs_n_factors] = max_factors[rhs_n_factors-1];
rhs_products[rhs_n_factors] = rhs_products[rhs_n_factors-1] * factor;
continue;
}
else if (rmost_char == '=')
continue;
else
{
// check for solution
++strings_checked;

factor = strtoll(rhs_factor_pointers[rhs_n_factors], NULL, 10);
unsigned long long max_factor;
if (factor > max_factors[rhs_n_factors])
max_factor = factor;
else
max_factor = max_factors[rhs_n_factors];

unsigned long long rhs_product = rhs_products[rhs_n_factors] * factor;

//printf("%.19s = %d\n", expression + center - 9, rhs_product);
//  printf("%.51s\n", expression + center - 25);
int length = rhs_size + lhs_size + 1;

if (lhs_product == rhs_product &&
(length > best_length ||
length == best_length && max_factor > best_factor))
{
best_length = length;
best_factor = max_factor;
memcpy(best_string, expression + center - lhs_size, length);
best_string[length] = 0;
}

}
}
else if (dir < 8)
{
coord step = dirs[dir];
int new_x = rpos.x + step.x;
int new_y = rpos.y + step.y;
char new_char;

if (new_x < 0 || new_x >= width ||
new_y < 0 || new_y >= height ||
grid[new_y][new_x].visited ||
(new_char = grid[new_y][new_x].symbol) == '=' ||
new_char == 'x' && (rmost_char == 'x' || rmost_char == '=')) continue;

// TODO: Should diagonally crossing paths be disallowed, too?

++rhs_size;

rpos.x = new_x;
rpos.y = new_y;
expression[center+rhs_size] = new_char;
}
else
{
if (rmost_char == 'x')
--rhs_n_factors;

rhs_dirs[rhs_size] = -2;
if (rmost_char != '=') expression[center+rhs_size] = ' ';
grid[rpos.y][rpos.x].visited = 0;

--rhs_size;
coord step = dirs[rhs_dirs[rhs_size]];
rpos.x -= step.x;
rpos.y -= step.y;
}
}
}
}
else if (dir < 8)
{
coord step = dirs[dir];
int new_x = lpos.x + step.x;
int new_y = lpos.y + step.y;
char new_char;

if (new_x < 0 || new_x >= width ||
new_y < 0 || new_y >= height ||
grid[new_y][new_x].visited ||
(new_char = grid[new_y][new_x].symbol) == '=' ||
new_char == 'x' && (lmost_char == 'x' || lmost_char == '=')) continue;

// TODO: Should diagonally crossing paths be disallowed, too?

++lhs_size;

lpos.x = new_x;
lpos.y = new_y;
expression[center-lhs_size] = new_char;
}
else
{
if (lmost_char == 'x')
--lhs_n_factors;

lhs_dirs[lhs_size] = -2;
expression[center-lhs_size] = ' ';
grid[lpos.y][lpos.x].visited = 0;

--lhs_size;
coord step = dirs[lhs_dirs[lhs_size]];
lpos.x -= step.x;
lpos.y -= step.y;
}
}
}

clock_t end = clock();
float seconds = (float)(end - start) / CLOCKS_PER_SEC;

printf("Checked %llu paths.\n", strings_checked);

printf("Took %f seconds.\n", seconds);

printf("Result: %s\n", best_string);
}


This expects the input stored in a file grid.txt. The first line is the space-separated size of the grid, which is followed by the grid itself. Like:

3 3
13x
=73
481


The algorithm is currently checking all possible well-formed paths (brute force). By well-formed, I mean that paths containing xx or two = are skipped, and I only start looking for paths starting from a = in both directions. Basically, I check all possible LHSs and for each such path, I check all possible RHSs. Over the next few days, I plan to add several optimisations to skip more paths, since the runtime per path will only go up and not down from here.

This will run into some problems with grid sizes of more than some 20 cells, due to integer overflow. I'll have to use some bigint-library when I get to solving those in a reasonable amount of time (which, I'm afraid, will reduce the paths/second a bit).

Currently, the largest sizes that can be solved in a reasonable amount of time at the moment are 7x3 or 5x4 (both taking under two minutes). 8x3 would take about half an hour, and 9x3 or 6x4 or 5x5 would take a few hours (between 1 and 7 I think).

EDIT: Managed to speed it up by close to 20 percent, because now I'm parsing each multiplicand when it's "locked" (i.e. when an x next to it has been parsed) instead of parsing the entire right-hand side for each possible path. And I should add that I observed those 20% for a grid where there's only a single x to be found, so I expect the performance gain for grids with many x to actually be quite substantial. Next stop: bigints.

### Python + networkx (Bruteforce, checks about 10000 paths per second on my machine)

It's not fast, but it works at least. Checks literally every path.

Amount of cycles necessary can be found here. This program solved a 5*6 in half an hour.

TODO: replace eval by something less terrible. Done.

__author__ = 'Synthetica'

import networkx as nx
import itertools as it
import time as tm

def main():
longest = 0
data = ['6996640', '1127=39', '186=940', '8329706', '3683980', '6349307',
'75x19x0', '5065350', '0051900']

hor = len(data[0])
vert = len(data)

G = nx.grid_2d_graph(vert, hor)
# Q = qu.LifoQueue(maxsize=1000)
printevery = 10**4
tested = 0
t = tm.time()
for node in it.product(G.nodes(), repeat=2):
if node[0]==node[1]:
continue
for path in nx.all_simple_paths(G, source=node[0], target=node[1]):
tested += 1
path = "".join(data[x][y] for x, y in path)
if tested > printevery:
ot = t
t = tm.time()
tested = 0
print printevery, "tested. Speed:", printevery/(t-ot), "s**-1"
if not all((path.count('=')==1, 'x' in path, len(path) >= longest)):
continue
#newpath = path.replace('=', '==').replace('x', '*')
try:
#print "Calling eval on", newpath
parts = path.split("=")
part0 = parts[0].split('x')
part1 = parts[1].split('x')

part0 = map(int,part0)
part1 = map(int,part1)

part0 = reduce(int.__mul__, part0)
part1 = reduce(int.__mul__, part1)

result = part0 == part1

except:
result = False
if result:
print 'Found new best:',path
longest = len(path)

if __name__ == "__main__":
main()