Skip to content

Instantly share code, notes, and snippets.

@adolfopa
Created August 12, 2011 14:31
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save adolfopa/1142151 to your computer and use it in GitHub Desktop.
Racket and Python solutions to Programming Praxis exercise "Word breaks" August 12, 2011
#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"))
#! /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