I know the answer is $(7+7)*(7+(1/7))$ or a more ghetto answer is $177-77$.
I'm not interested in the answer, more in the problem itself.
- What is the name of this class of problem?
- Is there a repeatable process I can apply to solve it? Or is it one that requires some sort of intuition? ie. Given a different set of digits and operators, could I follow the same process to derive the answer?
I'm a software engineer so my first reaction was to try all combinations of the digits and operators and evaluate each to see if it was $100$. Obviously there are a lot of combinations!
As it turns out GUILE Scheme does provide hash tables. In order to leave this discussion in an acceptable state for future viewers, I am posting an implementation of the above algorithm using hash tables, which makes for a much simpler and much more readable solution.
This is the code:
(use-modules (ice-9 format)) (define (digits-table mincnt maxcnt maxit minv maxv) (let ((layers (make-vector (+ 1 maxit))) (allsols (make-hash-table)) (initial (make-hash-table))) (for-each (lambda (ex-p) (hash-set! initial (car ex-p) (cdr ex-p))) '((1 . "1") (7 . "7") (17 . "17") (77 . "77") (71 . "71") (777 . "777") (177 . "177") (717 . "717") (771 . "771"))) (vector-set! layers 0 initial) (letrec ((insert (lambda (ht v s) (let ((ent (hash-ref ht v))) (if (or (and ent (> (string-length ent) (string-length s))) (not ent)) (hash-set! ht v s))))) (combine (lambda (res a b) (let* ((ha (vector-ref layers a)) (hb (vector-ref layers b))) (hash-for-each (lambda (v1 s1) (hash-for-each (lambda (v2 s2) (if (not (and (string-contains s1 "1") (string-contains s2 "1"))) (begin (insert res (+ v1 v2) (format #f "(~a)+(~a)" s1 s2)) (insert res (- v1 v2) (format #f "(~a)-(~a)" s1 s2)) (insert res (* v1 v2) (format #f "(~a)*(~a)" s1 s2)) (if (not (zero? v2)) (insert res (/ v1 v2) (format #f "(~a)/(~a)" s1 s2)))))) hb)) ha) res))) (iter (lambda (k) (if (not (= maxit k)) (let ((res (make-hash-table))) (do ((a 0 (1+ a))) ((> a k)) (combine res a (- k a))) (vector-set! layers (1+ k) res) (iter (1+ k))))))) (iter 0) (letrec ((do-disp (lambda (l) (if (not (null? l)) (let ((ex-p (car l))) (begin (display (format #f "~35a ~20a ~8f" (cdr ex-p) (car ex-p) (exact->inexact (car ex-p)))) (newline) (do-disp (cdr l)))))))) (do ((a 0 (1+ a))) ((> a maxit)) (hash-for-each (lambda (v s) (insert allsols v s)) (vector-ref layers a))) (do-disp (filter (lambda (p) (and (<= minv (car p)) (<= (car p) maxv) (<= mincnt (string-count (cdr p) #\7) maxcnt) (= (string-count (cdr p) #\1) 1))) (sort (hash-fold (lambda (v s prior) (cons (cons v s) prior)) '() allsols) (lambda (ex-p1 ex-p2) (< (car ex-p1) (car ex-p2))))))))) '())This will produce output e.g. like this