Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

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

View word-breaks.rkt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 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"))
View word-breaks.rkt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.