Jack likes the C programming language, but hates writing expressions like V=a*b\*h; to multiply values.

He would like to just write V=abh; instead; why should the compiler moan about abh being undefined? Since int a, b, h; are defined, can't it just deduce multiplication? Help him implement a parser that deciphers a single multiplication term, provided the set of variables defined in current scope is known.

For simplicity, no numbers will be included (i.e. 2abh), only single-character variables.

The input is a multiplication term T, fulfilling regexp:


and a variable set Z .

A parsing P of the term T over variable set Z is a string fulfilling the following conditions:

  1. P can be turned back into T by removing all * characters
  2. The string either is a variable name from Z or consists of proper variable names from Z split up by single * characters.

The solution should print all possible ways to parse the input.


Vars           a, c, ab, bc
Term           abc
Solution       ab*c, a*bc

Vars           ab, bc
Term           abc
Solution       -

Vars           -
Term           xyz
Solution       -

Vars           xyz
Term           xyz
Solution       xyz

Vars           width, height
Term           widthheight
Solution       width*height

Vars           width, height
Term           widthheightdepth
Solution       -

Vars           aaa, a
Term           aaaa
Solution       aaa*a, a*aaa, a*a*a*a

The input (the list of variables and the term) may be supplied in any way suitable for the language.

The output can be in any sensible form (one result per line or a comma-separated list etc.) - but it should be unambiguous and possible to read.

Empty output is acceptable if there is no possible parsing of a term (in the examples I used '-' for clarity).

This is , so the shortest code wins.

  • 1
    \$\begingroup\$ In your first example, I believe ab*c is an incorrect parse, since c is not an allowed variable. \$\endgroup\$
    – isaacg
    Apr 12, 2015 at 21:31
  • 1
    \$\begingroup\$ With a recursive scan I find exactly your result in the sample. But it's questionable: why a*aaa aaa*a and not ab*c c*ab \$\endgroup\$
    – edc65
    Apr 13, 2015 at 8:11
  • \$\begingroup\$ Because of rule 1. of parsing. Yes, multiplication is usually commutative, but we don't go so far - we just want to "reconstruct" multiplication in the order it was done. Actually in Jack's language we could have a matrix type - the multiplication is not commutative then. And "aaaa" can be both juxtaposition of "aaa" and "a" or "a" and "aaa" - this not for commutativeness, rather for ambiguity we are taking both into account. \$\endgroup\$ Apr 13, 2015 at 10:57
  • \$\begingroup\$ Exact duplicate of codegolf.stackexchange.com/questions/45496/… \$\endgroup\$
    – feersum
    Apr 15, 2015 at 8:46

3 Answers 3


Pyth, 18 chars


This solution is adapted from my Interpreting Fish solution. The problems are actually very similar.

Expects input as such:

"a", "aaa"

Gives output like this:

['a*aaa', 'aaa*a', 'a*a*a*a']

Try it here.

  • sm^Qkhlz: Generates all sequences of variables containing up to the length of the input string number of variables.

  • fqzsT: Filters out the variable sequences that match the input string

  • mj\*d: Inserts the * symbol and prints.


Python 2 - 147 94 bytes

R=lambda S,V,F=[]:S and[R(S[len(v):],V,F+[v])for v in V if v==S[:len(v)]]or print("*".join(F))

This defines a function R to be used like:

>>> R("abc", ["a", "bc", "ab", "c"])

Prints output like:


JavaScript (ES6) 111

Adapted from my "fish" answer, the main difference is finding all solutions, not just the first.


The output is printed to the console. The function result have no meaning and must be discarded.

Test In Firefox/FireBug console





Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.