public
Last active

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

  • Download Gist
word-breaks.rkt
Racket
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"))
wordbreaks.py
Python
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.