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

He would like to write V=abh; instead, why should compiler moan about abh symbol being undefined since int a, b, h; are defined, so we can 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, multiplying by number (as in 2*a*b) is not taken into account, only variables appear.

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 following:

  1. after removing all occurences of * from P we receive T,
  2. 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 parsings of a term.


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 parsing 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 a code golf, 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 '15 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 '15 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\$ – pawel.boczarski Apr 13 '15 at 10:57
  • \$\begingroup\$ Exact duplicate of codegolf.stackexchange.com/questions/45496/… \$\endgroup\$ – feersum Apr 15 '15 at 8:46

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.

|improve this answer|||||

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:

|improve this answer|||||

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




|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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