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"))

wordbreaks.py

#! /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