Racket and Python solutions to Programming Praxis exercise "Word breaks" August 12, 2011

word-breaks.rkt

#lang racket

(require rackunit)

(define dictionary
  (set "a" "brown" "apple" "pie"))

(define (in-prefixes str)
  (define (pos->element i)
    (values (substring str 0 (+ 1 i)) (substring str (+ 1 i))))
  (define (next-pos i)
    (+ i 1))
  (define initial-position 0)
  (define (contains-index? i)
    (< i (string-length str)))
  (define (contains-value? prefix rest)
    #t)
  (define (contains-index-and-value? i prefix rest)
    #t)
  (make-do-sequence
   (lambda ()
     (values pos->element
             next-pos
             initial-position
             contains-index?
             contains-value?
             contains-index-and-value?))))

(define (string-empty? str)
  (zero? (string-length str)))

(define (word-break dictionary word)
  (for/first (((prefix remaining) (in-prefixes word))
              #:when (set-member? dictionary prefix)
              (rest (in-value (if (string-empty? remaining)
                                  '()
                                  (word-break dictionary remaining))))
              #:when rest)
    (cons prefix rest)))

(check-equal? (word-break dictionary "") #f)

(check-equal? (word-break dictionary "pear") #f)

(check-equal? (word-break dictionary "a") '("a"))

(check-equal? (word-break dictionary "apple") '("apple"))

(check-equal? (word-break dictionary "applepie") '("apple" "pie"))

(check-equal? (word-break dictionary "brownapplepie") '("brown" "apple" "pie"))