things and 1-9

nums.rkt

#lang racket
(define (evalexp e [n (+ (length e) 1)])
  (match e
    [`(|| . ,xs) (evalexp xs (string->number (~a (length e) n)))]
    [`(,x . ,xs) ((hash-ref (hash '+ + '- -) x) (evalexp xs) n)]
    [`() n]))

(define (perms len elms)
  (foldr (λ (_ res) (append-map (λ (p) (map (λ (e) `(,e . ,p)) elms)) res))
         '(())
         (build-list len void)))

(define (expstr l)
  (foldl ~a "" (reverse (build-list (+ 1 (length l)) add1)) `(|| . ,l)))

(define solutions (filter (λ (x) (= (evalexp x) 100)) (perms 8 '(+ - ||))))

(map expstr solutions)

So the SML thing works with trees like

    -   
   / \
  +   4
 / \
12  3

If we split up the "joined" digits, it could look more like

      -
     / \
    +   4 
   / \
  ||  3
 /  \
1    2

(Using || for joins because handy. || is the empty symbol in Racket. ~a will turn it into an empty string later, and that'll be put between digits to "join" them.)

And that looks a little bit like a list of numbers, except the insteada conses we have pluses and minuses and joins, and the list terminator is number.

We already know that the numbers are 1-9, in order like, so it's not really that important to keep track of those. And if we only need to keep track of the pluses, minuses and joins, then we could just have a list of pluses, minuses and joins.

      cons
     /    \
    cons   - 
   /    \
  cons   +
 /    \
nil   ||

So e.g. the solution 1+2+3-4+5+6+78+9 will look like (+ || + + + - + +) (which looks a bit backwards, because the top of a cons-tree is considered the beginning of a list). We can add in the right numbers when we need them, when evaluating an expression and checking if it adds up to a hundred, and when turning it into a string for maybe-prettier printing.