Programmers like to talk about how concurrency (multithreading, etc.)
makes code more complicated. And sometimes that’s true. But there are
a few areas where concurrency actually makes things simpler; the
“samefringe problem” is one classic example, but the “telegram
problem” is another one.
The “telegram problem” is to refill paragraphs, so as many words as
possible fit on each line, like the Unix command `fmt`. Here are
solutions with and without using Python’s built-in “generator” form of
concurrency.
#!/usr/bin/python
"Telegram problem, aka fmt."
import sys
words = lambda line: line.split()
width = lambda buf: sum(len(word) for word in buf) + len(buf) - 1
def telegram_generator_1(infile, maxwidth):
"""A purely procedural version that doesn't use generators internally.
This is what you get if you're writing a conventional procedural
program to solve the problem by imperatively producing output
lines.
"""
buf = []
for line in infile:
buf.extend(words(line))
while width(buf) > maxwidth:
n = len(buf)
while width(buf[:n]) > maxwidth:
n -= 1
yield ' '.join(buf[:n])
buf[:n] = []
yield ' '.join(buf)
# XXX what to do if a word is wider than the line?
def telegram_super_cool(infile, maxwidth):
"""Here's a totally generator-oriented version."""
buf = []
for word in (word for line in lines for word in words(line)):
buf.append(word)
if width(buf) > maxwidth:
yield ' '.join(buf[:-1])
buf[:-1] = []
yield ' '.join(buf)
class IteratorBase:
def __iter__(self): return self
class telegram_super_cool_explicit_cps(IteratorBase):
"""Here's an explicit iterator implementation.
I wrote this from telegram_super_cool above, twiddling it a little
to reduce excess complexity. It's remarkable how much excess
complexity still remains.
"""
def __init__(self, infile, maxwidth):
self.infile, self.maxwidth = iter(infile), maxwidth
self.buf = []
self.done = False
self.buf2 = []
def next_word(self):
while not self.buf2:
self.buf2 = words(self.infile.next())
return self.buf2.pop(0)
def next(self):
if self.done:
raise StopIteration
while True:
try:
self.buf.append(self.next_word())
except StopIteration:
self.done = True
return ' '.join(self.buf)
if width(self.buf) > self.maxwidth:
rv = ' '.join(self.buf[:-1])
self.buf[:-1] = []
return rv
if __name__ == '__main__':
for line in telegram_super_cool_explicit_cps(sys.stdin, 72):
print line
# Like everything else posted to kragen-hacks without a notice to the
# contrary, this software is in the public domain.
--
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-hacks
