All expressions of 123456789 and signs +/- which value is 100
Submitted by st on
Suppose a string of ordered cyphers 123456789
. You can insert signs "+" and "-" between any cyphers to make a correct arithmetical expression. The problem is to find all expressions which sum is 100.
This problem may be interesting for dynamic script languages having the function of a string expression evaluation.
E.g. solving in bash
$ for i in {,-}1{,+,-}2{,+,-}3{,+,-}4{,+,-}5{,+,-}6{,+,-}7{,+,-}8{,+,-}9; do (($i == 100)) && echo $i; done
Result
123+45-67+8-9 123+4-5+67-89 123-45-67+89 123-4-5-6-7+8-9 12+3+4+5-6-7+89 12+3-4+5+67+8+9 12-3-4+5-6+7+89 1+23-4+56+7+8+9 1+23-4+5+6+78-9 1+2+34-5+67-8+9 1+2+3-4+5+6+78+9 -1+2-3+4+5+6+78+9
The standard SQL has no evaluation functions. However, the recursive query approach can help.
Solution in ANSI SQL
WITH signs AS ( SELECT '' AS s, 0 AS sv UNION SELECT '+' AS s, 1 AS sv UNION SELECT '-' AS s, -1 AS sv ), curr (sv, c, expr, num, val) AS ( SELECT 0 AS sv, 0 AS c, CAST('' AS varchar(20)) AS expr, 0 AS num, 0 AS val UNION ALL SELECT signs.sv AS sv, c + 1 AS c, CAST(expr + signs.s + CAST((c + 1) AS varchar(1)) AS varchar(20)) AS expr, CASE WHEN signs.sv = 0 THEN num * 10 + (CASE WHEN num < 0 THEN -(c + 1) ELSE c + 1 END) ELSE signs.sv * (c + 1) END AS num, CASE WHEN signs.sv = 0 THEN val ELSE val + num END AS val FROM curr CROSS JOIN signs WHERE curr.c < 9 AND NOT (c = 0 AND signs.sv = 1) ) SELECT expr, val + num AS total FROM curr WHERE c = 9 AND val + num = 100
Result
expr total -------------------- ----------- -1+2-3+4+5+6+78+9 100 1+2+3-4+5+6+78+9 100 1+2+34-5+67-8+9 100 1+23-4+5+6+78-9 100 1+23-4+56+7+8+9 100 12-3-4+5-6+7+89 100 12+3-4+5+67+8+9 100 12+3+4+5-6-7+89 100 123-4-5-6-7+8-9 100 123-45-67+89 100 123+4-5+67-89 100 123+45-67+8-9 100 (12 rows affected)