amb-ouroboros.rkt

#lang racket
(require (planet murphy/amb:1:1/amb))

(define (list->num lst)
  (define (go acc lst)
    (match lst
      [(cons x xs) (go (+ x (* 10 acc)) xs)]
      ['() acc]))
  (go 0 lst))

(define (digit)
  (amb 1 2 3 4 5 6 7 8 9 0))

(define (fail)
  (amb))

(define (search-n n)
  (define last (digit))
  (when (eq? last 0) (fail))

  (define (iter carry rem acc)
    (define next (digit))
    (unless (eq? next rem) (fail))
    (define-values (next-carry next-rem) (quotient/remainder (+ (* next n) carry) 10))
    
    ; We are doing depth first search, and need to give up somewhere.
    (when ((length acc) . > . 100) (fail))
    
    ; We can't lead with a 0.
    ; We need the leading digit to line up with the last.  When that happens we are done.
    (if (and (not (eq? next 0))
         (eq? (+ (* n next) carry) last))
        ; Convert from a list of digits to a number.
        (list->num (cons next acc))
        (iter next-carry next-rem (cons next acc))))
  
  (define-values (last-carry last-rem) (quotient/remainder (* last n) 10))
  ; We did the first iteration here, since starting is a bit weird.
  (iter last-carry last-rem (list last)))

; Stop reading here.  This is where I was just solving without loops

(define (/10 x)
  (quotient x 10))

  
(define (search)
  (define a (digit))
  (when (eq? a 0) (fail))
  (when ((* 4  a) . > . 10) (fail))
  (define f (digit))
  (when (f . < . (* 4 a)) (fail))
  (define b (digit))
  (unless ((+ (* 4 a) (/10 (* 4 b))) . <= . f) (fail))
  (define e (digit))
  (unless (eq? (remainder (* f 4) 10) e) (fail))
  (define f-carry (/10 (* f 4)))
  (define d (digit))
  (unless (eq? (remainder (+ (* e 4) f-carry) 10) d) (fail))
  (define e-carry (/10 (+ (* e 4) f-carry)))
  (define c (digit))
  (unless (eq? (remainder (+ (* d 4) e-carry) 10) c) (fail))
  (define d-carry (/10 (+ (* d 4) e-carry)))
  (unless (eq? (remainder (+ (* c 4) d-carry) 10) b) (fail))
  
  (list a b c d e f))

(define (search2)
  (define f (digit))
  (define-values (f-carry f-rem) (quotient/remainder (* f 4) 10))

  (define e (digit))
  (unless (eq? f-rem e) (fail))
  (define-values (e-carry e-rem) (quotient/remainder (+ (* e 4) f-carry) 10))
  
  (define d (digit))
  (unless (eq? e-rem d) (fail))
  (define-values (d-carry d-rem) (quotient/remainder (+ (* d 4) e-carry) 10))
  
  (define c (digit))
  (unless (eq? d-rem c) (fail))
  (define-values (c-carry c-rem) (quotient/remainder (+ (* c 4) d-carry) 10))

  (define b (digit))
  (unless (eq? c-rem b) (fail))
  (define-values (b-carry b-rem) (quotient/remainder (+ (* b 4) c-carry) 10))
  
  (define a (digit))
  (unless (eq? b-rem a) (fail))
  (define-values (a-carry a-rem) (quotient/remainder (+ (* a 4) b-carry) 10))
  
  (unless (eq? a-rem f) (fail))
  (unless (eq? a-carry 0) (fail))
  (when (eq? a 0) (fail))
    
  (list a b c d e f))