adolfopa · August 12, 2011 14:31 · Aug 12, 2011 · Aug 12, 2011
diff --git a/wordbreaks.py b/wordbreaks.py
@@ -0,0 +1,33 @@
+#! /usr/bin/env python
+
+from nose.tools import assert_equals
+
+DICTIONARY = {'a', 'apple', 'pie', 'brown'}
+
+def test_empty_word():
+    assert_equals(None, word_break(DICTIONARY, ''))
+
+def test_simple_word():
+    assert_equals(['a'], word_break(DICTIONARY, 'a'))
+
+def test_one_word():
+    assert_equals(['apple'], word_break(DICTIONARY, 'apple'))
+
+def test_two_word():
+    assert_equals(['apple', 'pie'], word_break(DICTIONARY, 'applepie'))
+
+def test_three_words():
+    assert_equals(['brown', 'apple', 'pie'], word_break(DICTIONARY, 'brownapplepie'))
+
+def word_break(dictionary, word):
+    def break_string(s):
+        return [] if s == '' else word_break(dictionary, s)
+
+    for split_point in range(len(word) + 1):
+        prefix = word[:split_point]
+
+        if prefix in dictionary:
+            rest = break_string(word[split_point:])
+
+            if rest is not None:
+                return [prefix] + rest
diff --git a/word-breaks.rkt b/word-breaks.rkt
@@ -0,0 +1,51 @@
+#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"))