# Sum to 100

``````func gen_expr() is cached {
var x = ['-', '']
var y = ['+', '-', '']

gather {
cartesian([x,y,y,y,y,y,y,y,y], {|a,b,c,d,e,f,g,h,i|
take("#{a}1#{b}2#{c}3#{d}4#{e}5#{f}6#{g}7#{h}8#{i}9")
})
}
}

func eval_expr(expr) is cached {
expr.scan(/([-+]?\d+)/).sum_by { Num(_) }
}

func sum_to(val) {
gen_expr().grep { eval_expr(_) == val }
}

func max_solve() {
gen_expr().grep     { eval_expr(_) >= 0 } \
.group_by { eval_expr(_)      } \
.max_by   {|_,v| v.len        }
}

func min_solve() {
var h = gen_expr().group_by { eval_expr(_) }
for i in (0..Inf) { h.exists(i) || return i }
}

func highest_sums(n=10) {
gen_expr().map { eval_expr(_) }.uniq.sort.reverse.first(n)
}

sum_to(100).each { say "100 = #{_}" }

var (n, solutions) = max_solve()...
say "Sum of #{n} has the maximum number of solutions: #{solutions.len}"
say "Lowest positive sum that can't be expressed : #{min_solve()}"
say "Highest sums: #{highest_sums()}"
``````

#### Output:

``````100 = -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+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
Sum of 9 has the maximum number of solutions: 46
Lowest positive sum that can't be expressed : 211
Highest sums: [123456789, 23456790, 23456788, 12345687, 12345669, 3456801, 3456792, 3456790, 3456788, 3456786]
``````