Adventures in Prolog - Simplify Sum (4)

Last post was concerned with implementing the simplification of an additive (compound) term. The proposed solution consists of three elementary steps (sorting, simplifying and reducing). Although the proposed solution is quite flexible, i.e. works on any atom not specifically a single character,
the sorting of characters decreases performance somewhat. For this, this post is concerned with a more targeted approach to the introduced problem.

Given an additive (compound) term containing numbers and (unitary) variable symbols (e.g., a, b, x, y, z), we wish to obtain a reduced form of this term, which simplifies the same variables and sums multiple numbers to one single number.

The following solution makes use of:

1. The (German and English) alphabet contains only 26 elementary characters (variable symbols)
2. Character symbols can be ordered according to their occurence within the alphabet.

Instead of operating on additive compound term, the proposed solution operates on a character array , i.e. array indexing individual variable characters. The following solution consists of two main steps:

1. Simplification of additive (compound) term
2. Computing a reduced printable form (string) of the simplified term.

Now, given the perimeters of the proposed approach, this is what it looks like:

map_index(a, 1).
map_index(b, 2).
map_index(c, 3).
map_index(d, 4).
map_index(e, 5).
map_index(f, 6).
map_index(g, 7).
map_index(h, 8).
map_index(i, 9).
map_index(j, 10).
map_index(k, 11).
map_index(l, 12).
map_index(m, 13).
map_index(n, 14).
map_index(o, 15).
map_index(p, 16).
map_index(q, 17).
map_index(r, 18).
map_index(s, 19).
map_index(t, 20).
map_index(u, 21).
map_index(v, 22).
map_index(w, 23).
map_index(x, 24).
map_index(y, 25).
map_index(z, 26).
map_index(V, 27) :- number(V).

map_index defines the array index of each variable symbol. index 27 is reserved as the computation cell for numbers.

increment(1, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A1, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- A1 is A + 1.
increment(2, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- B1 is B + 1.
increment(3, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- C1 is C + 1.
increment(4, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D1, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- D1 is D + 1.
increment(5, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E1, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- E1 is E + 1.
increment(6, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F1, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- F1 is F + 1.
increment(7, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G1, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- G1 is G + 1.
increment(8, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H1, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- H1 is H + 1.
increment(9, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I1, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- I1 is I + 1.
increment(10, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- J1 is J + 1.
increment(11, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- K1 is K + 1.
increment(12, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L1, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- L1 is L + 1.
increment(13, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- M1 is M + 1.
increment(14, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N1, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- N1 is N + 1.
increment(15, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O1, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- O1 is O + 1.
increment(16, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P1, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- P1 is P + 1.
increment(17, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q1, R, S, T, U, V, W, X, Y, Z, NN]) :- Q1 is Q + 1.
increment(18, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R1, S, T, U, V, W, X, Y, Z, NN]) :- R1 is R + 1.
increment(19, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S1, T, U, V, W, X, Y, Z, NN]) :- S1 is S + 1.
increment(20, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T1, U, V, W, X, Y, Z, NN]) :- T1 is T + 1.
increment(21, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U1, V, W, X, Y, Z, NN]) :- U1 is U + 1.
increment(22, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V1, W, X, Y, Z, NN]) :- V1 is V + 1.
increment(23, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W1, X, Y, Z, NN]) :- W1 is W + 1.
increment(24, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X1, Y, Z, NN]) :- X1 is X + 1.
increment(25, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y1, Z, NN]) :- Y1 is Y + 1.
increment(26, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z1, NN]) :- Z1 is Z + 1.

increment(27, Inc, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN1]) :- NN1 is NN + Inc.

increment uses an index and updates the respective variable or number cell. Note that, variables may only be
incremented by one, whereas numbers can be incremented by any other number (adding two numbers).

simplify(In) :-
simplify_a(In, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], OutMap),
print_simplified(OutMap), !.

simplify(_).

simplify_a(X, InMap, OutMap) :-
  atomic(X),
  map_index(X, I),
  print('Index: '), print(I), nl,
  increment(I, X, InMap, OutMap), !.

simplify_a(A + B, InMap, OutMap) :-
  atomic(A),
  atomic(B),
  map_index(A, I1),
  map_index(B, I2),
  increment(I1, A, InMap, TMap),
  increment(I2, B, TMap, OutMap), !.

simplify_a(A + B, InMap, OutMap) :-
  compound(A),
  atomic(B),
  map_index(B, I),
  increment(I, B, InMap, TMap),
  simplify_a(A, TMap, OutMap), !.

simplify_a(_, InMap, InMap).

simplify calls simplify_a, which is responsible for obtaining a simplified representation from some additive term.

print_simplified(In) :-
  print('Result:'), nl,
  str_simplified_t(In, 1, '', OutStr),
  print(OutStr), nl, !.

get_no(_, 0, '').
get_no(Char, 1, Char).
get_no(Char, X, X*Char).

str_simplified_t([0|Rest], Index, TStr, RStr) :-
  Index1 is Index + 1,
  str_simplified_t(Rest, Index1, TStr, RStr), !.

str_simplified_t([X, 0], 26, TStr, RStr) :-
  map_index(Char, 26),
  RStr = TStr + X*Char, !.

str_simplified_t([X, N], 26, TStr, RStr) :-
  map_index(Char, 26),
  get_no(Char, X, XStr),
  RStr = TStr + XStr + N, !.

str_simplified_t([X|R], 1, _, RStr) :-
  map_index(Char, Loop),
  get_no(Char, X, AStr),
  I1 is Loop + 1,
  str_simplified_t(R, I1, AStr, RStr), !.

str_simplified_t([X|R], Loop, TStr, RStr) :-
  map_index(Char, Loop),
  get_no(Char, X, XStr),
  AStr = TStr + XStr,
  I1 is Loop + 1,
  str_simplified_t(R, I1, AStr, RStr).

print_simplified calls str_simplified_t to compute the reduced string representing a simplified additive term of the initial additive term.

As one can see this solution is somewhat less complex and more performant than the previous solution. Most of the code is responsible for computing array indices or updating an array cell. For this, further (code length) optimizations may be identified. The array approach completely avoids the sort predicate thereby reducing run-time overhead. On the downside, this approach works with single characters instead of any atom.