Odd word problem

Odd word problem is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Write a program that solves the odd word problem.

Description: You are promised an input stream consisting of English letters and punctuations. It is guaranteed that

• the words (sequence of consecutive letters) are delimited by one and only one punctuation; that
• the stream will begin with a word; that
• the words will be at least one letter long; and that
• a full stop (.) appears after, and only after, the last word.

For example, what,is,the;meaning,of:life. is such a stream with six words. Your task is to reverse the letters in every other word while leaving punctuations intact, producing e.g. "what,si,the;gninaem,of:efil.", while observing the following restrictions:

1. Only I/O allowed is reading or writing one character at a time, which means: no reading in a string, no peeking ahead, no pushing characters back into the stream, and no storing characters in a global variable for later use;
2. You are not to explicitly save characters in a collection data structure, such as arrays, strings, hash tables, etc, for later reversal;
3. You are allowed to use recursions, closures, continuations, threads, coroutines, etc.

Test case: work on both the "life" example given above, and the text we,are;not,in,kansas;any,more.

C

Using GCC nested function as closures. This can only be passed up the stack, not the other way around. It's also doable with makecontext, and may be possible with setjmp.

<lang c>#include <stdio.h>

1. include <ctype.h>

int do_char(int odd, void (*f)(void)) { int c = getchar();

void write_out(void) { putchar(c); if (f) f(); }

if (!odd) putchar(c);

if (isalpha(c)) return do_char(odd, write_out);

if (odd) { if (f) f(); putchar(c); }

return c != '.'; }

int main() { int i = 1; while (do_char(i = !i, 0));

return 0; }</lang>

Common Lisp

Even words are straightforward. For odd words, the final punctuation is printed by a closure passed back up the caller chain. <lang lisp>(defun do-even (&aux (c (read-char)))

 (if (alpha-char-p (write-char c))
   (do-even)
   (char/= c #\.)))

(defun do-odd (&aux (c (read-char)))

 (if (alpha-char-p c)
   (prog1
     (do-odd)
     (write-char c))
   (lambda ()
     (write-char c)
     (char/= #\.))))

(defun do-char (is-even)

 (if is-even
   (do-even)
   (funcall (do-odd))))

(loop for x = t then (not x)

     while (do-char x))</lang>

Factor

This is a delicate program with arcane control flow. To reverse each odd word, this code uses continuations to jump-back into earlier iterations of a while loop. This trick reverses the letters by reversing the loop!

This code is difficult to follow, because it twists its control flow like spaghetti. These continuations form a singly-linked list, where each continuation contains a letter and a previous continuation. The program effectively reverses this linked list.

<lang factor>USING: continuations kernel io io.streams.string locals unicode.categories ; IN: rosetta.odd-word

<PRIVATE ! Save current continuation.

savecc ( -- continuation/f )

   [ ] callcc1 ; inline

! Jump back to continuation, where savecc will return f.

jump-back ( continuation -- )

   f swap continue-with ; inline

PRIVATE>

read-odd-word ( -- )

   f :> first-continuation!
   f :> last-continuation!
   f :> reverse!
   ! Read characters. Loop until end of stream.
   [ read1 dup ] [
       dup Letter? [
           ! This character is a letter.
           reverse [
               ! Odd word: Write letters in reverse order.
               last-continuation savecc dup [
                   last-continuation!
                   2drop       ! Drop letter and previous continuation.
               ] [
                   ! After jump: print letters in reverse.
                   drop                ! Drop f.
                   swap write1         ! Write letter.
                   jump-back           ! Follow chain of continuations.
               ] if
           ] [
               ! Even word: Write letters immediately.
               write1
           ] if
       ] [
           ! This character is punctuation.
           reverse [
               ! End odd word. Fix trampoline, follow chain of continuations
               ! (to print letters in reverse), then bounce off trampoline.
               savecc dup [
                   first-continuation!
                   last-continuation jump-back
               ] [ drop ] if
               write1                  ! Write punctuation.
               f reverse!              ! Begin even word.
           ] [
               write1                  ! Write punctuation.
               t reverse!              ! Begin odd word.
               ! Create trampoline to bounce to (future) first-continuation.
               savecc dup [
                   last-continuation!
               ] [ drop first-continuation jump-back ] if
           ] if
       ] if
   ] while
   ! Drop f from read1. Then print a cosmetic newline.
   drop nl ;

odd-word ( string -- )

   [ read-odd-word ] with-string-reader ;</lang>

USE: rosetta.odd-word
( scratchpad ) "what,is,the;meaning,of:life." odd-word
what,si,the;gninaem,of:efil.
( scratchpad ) "we,are;not,in,kansas;any,more." odd-word
we,era;not,ni,kansas;yna,more.

Go

<lang go>package main

import (

   "bytes"
   "fmt"
   "io"
   "os"
   "unicode"

)

func main() {

   owp(os.Stdout, bytes.NewBufferString("what,is,the;meaning,of:life."))
   fmt.Println()
   owp(os.Stdout, bytes.NewBufferString("we,are;not,in,kansas;any,more."))
   fmt.Println()

}

func owp(dst io.Writer, src io.Reader) {

   byte_in := func () byte {
       bs := make([]byte, 1)
       src.Read(bs)
       return bs[0]
   }
   byte_out := func (b byte) { dst.Write([]byte{b}) }    
   var odd func() byte
   odd = func() byte {
       s := byte_in()
       if unicode.IsPunct(rune(s)) {
           return s
       }
       b := odd()
       byte_out(s)
       return b
   }
   for {
       for {
           b := byte_in()
           byte_out(b)
           if b == '.' {
               return
           }
           if unicode.IsPunct(rune(b)) {
               break
           }
       }
       b := odd()
       byte_out(b)
       if b == '.' {
           return
       }
   }

}</lang> Output:

what,si,the;gninaem,of:efil.
we,era;not,ni,kansas;yna,more.

A different approach, using defer: <lang go>package main

import (

   "bytes"
   "fmt"
   "io"
   "os"
   "unicode"

)

func main() {

   owp(os.Stdout, bytes.NewBufferString("what,is,the;meaning,of:life."))
   fmt.Println()
   owp(os.Stdout, bytes.NewBufferString("we,are;not,in,kansas;any,more."))
   fmt.Println()

}

func owp(dst io.Writer, src io.Reader) {

   byte_in := func () byte {
       bs := make([]byte, 1)
       src.Read(bs)
       return bs[0]
   }
   byte_out := func (b byte) { dst.Write([]byte{b}) }    
   odd := func() byte {
       for {
           b := byte_in()
           if unicode.IsPunct(int(b)) {
               return b
           }
           defer byte_out(b)
       }
       panic("impossible")
   }
   for {
       for {
           b := byte_in()
           byte_out(b)
           if b == '.' {
               return
           }
           if unicode.IsPunct(rune(b)) {
               break
           }
       }
       b := odd()
       byte_out(b)
       if b == '.' {
           return
       }
   }

}</lang>

Icon and Unicon

The following recursive version is based on the non-deferred GO version. A co-expression is used to turn the parameter to the wrapper into a character at a time stream.

<lang Icon>procedure main() every OddWord(!["what,is,the;meaning,of:life.",

               "we,are;not,in,kansas;any,more."])

end

procedure OddWord(stream) #: wrapper for demonstration

  write("Input stream: ",stream)
  writes("Output stream: ") & eWord(create !stream,'.,;:') & write()

end

procedure eWord(stream,marks) #: handle even words

  repeat {                               
     repeat 
        writes(@stream) ? if ="." then return else if any(marks) then break
     if writes(oWord(stream,marks)) == '.' then return
     }

end

procedure oWord(stream,marks) #: handle odd words (reverse)

  if any(marks,s := @stream) then return s
  return 1(oWord(stream,marks), writes(s))  

end</lang>

Output:

Input stream: what,is,the;meaning,of:life.
Output stream: what,si,the;gninaem,of:efil.
Input stream: we,are;not,in,kansas;any,more.
Output stream: we,era;not,ni,kansas;yna,more.

A slightly different solution which uses real I/O from stdin is: <lang Unicon>procedure main(A)

   repeat (while writes((any(&letters, c := reads(&input,1)),c))) |
          (if "." ~== writes(c) then "." ~== writes(rWord()))     | break
   write()

end

procedure rWord(c)

   c1 := rWord((any(&letters, c1 := reads(&input,1)),c1))
   writes(\c)
   return c1

end</lang> And some sample runs:

->rw
what,is,the;meaning,of:life.
what,si,the;gninaem,of:efil.
->rw
we,are;not,in,kansas;any,more.
we,era;not,ni,kansas;yna,more.
->

J

This task's requirement to perform buffering implicitly rather than explicitly was perplexing from a J point of view (see talk page for some of that discussion). To avoid this issue, this implementation uses a coroutine-like utility.

<lang j>instream=. 'example text'

 last=. _1

 getch=: 3 :0
   last=: last+1
   last{instream
 )

outstream=.

 putch=: 3 :0
   outstream=: outstream, y
   return 
 )

isletter=: toupper ~: tolower

do_char=: 3 :0

 ch=. getch
 if. isletter ch do.
   if. even do.
     return ch return.
   else.
     (return@[ putch bind ch) yield do_char  return.
   end.
 elseif. '.' = ch do.
   return ch return.
 elseif. do.
   even=: -. even
   return ch return.
 end.

)

evenodd=: 3 :0

 instream=: y
 outstream=: 
 last=: _1
 even=: 1
 whilst. '.'~:char do.
   putch char=. do_char coroutine 
 end.
 outstream

)</lang>

With this implementation:

<lang j> evenodd 'what,is,the;meaning,of:life.' what,si,the;gninaem,of:efil.

  evenodd 'we,are;not,in,kansas;any,more.'

we,era;not,ni,kansas;yna,more.</lang>

That said, note that this implementation has significant overhead when compared to a more direct implementation of the algorithm.

Java

<lang java>public class OddWord {

   interface CharHandler {

CharHandler handle(char c) throws Exception;

   }
   final CharHandler fwd = new CharHandler() {

public CharHandler handle(char c) { System.out.print(c); return (Character.isLetter(c) ? fwd : rev); }

   };
   class Reverser extends Thread implements CharHandler {

Reverser() { setDaemon(true); start(); } private Character ch; // For inter-thread comms private char recur() throws Exception { notify(); while (ch == null) wait(); char c = ch, ret = c; ch = null; if (Character.isLetter(c)) { ret = recur(); System.out.print(c); } return ret; } public synchronized void run() { try { while (true) { System.out.print(recur()); notify(); } } catch (Exception e) {} } public synchronized CharHandler handle(char c) throws Exception { while (ch != null) wait(); ch = c; notify(); while (ch != null) wait(); return (Character.isLetter(c) ? rev : fwd); }

   }
   final CharHandler rev = new Reverser();

   public void loop() throws Exception {

CharHandler handler = fwd; int c; while ((c = System.in.read()) >= 0) { handler = handler.handle((char) c); }

   }

   public static void main(String...args) throws Exception {

new OddWord().loop();

   }

}</lang> Output is equivalent to that of the Python solution.

Python

<lang python>from sys import stdin, stdout

def char_in(): return stdin.read(1) def char_out(c): stdout.write(c)

def odd(prev = lambda: None): a = char_in() if not a.isalpha(): prev() char_out(a) return a != '.'

# delay action until later, in the shape of a closure def clos(): char_out(a) prev()

return odd(clos)

def even(): while True: c = char_in() char_out(c) if not c.isalpha(): return c != '.'

e = False while odd() if e else even(): e = not e</lang> Running:<lang>$ echo "what,is,the;meaning,of:life." | python odd.py what,si,the;gninaem,of:efil. $ echo "we,are;not,in,kansas;any,more." | python odd.py we,era;not,ni,kansas;yna,more.</lang>

Ruby

Ruby programs use single-character strings.

Using fibers and recursion

Translation of: Tcl

Works with: Ruby version 1.9

<lang ruby>f, r = nil fwd = proc {|c|

 c =~ /alpha:/ ? [(print c), fwd[Fiber.yield f]][1] : c }

rev = proc {|c|

 c =~ /alpha:/ ? [rev[Fiber.yield r], (print c)][0] : c }

(f = Fiber.new { loop { print fwd[Fiber.yield r] }}).resume (r = Fiber.new { loop { print rev[Fiber.yield f] }}).resume

coro = f until $stdin.eof?

 coro = coro.resume($stdin.getc)

end</lang>

Using continuations

Translation of: Factor

Library: continuation

<lang ruby>require 'continuation' unless defined? Continuation require 'stringio'

1. Save current continuation.

def savecc(*data)

 # With MRI 1.8 (but not 1.9), the array literal
 #   [callcc {|cc| cc}, *data]
 # used the wrong return value from callcc. The workaround is to
 # put callcc outside the array literal.
 continuation = callcc {|cc| cc}
 [continuation, *data]

end

1. Jump back to continuation, where savecc will return [nil, *data].

def jump_back(continuation)

 continuation[nil]

end

def read_odd_word(input, output)

 first_continuation, last_continuation = nil
 reverse = false
 # Read characters. Loop until end of stream.
 while c = input.getc
   c = c.chr   # For Ruby 1.8, convert Integer to String.
   if c =~ /alpha:/
     # This character is a letter.
     if reverse
       # Odd word: Write letters in reverse order.
       saving, last_continuation, c = savecc(last_continuation, c)
       if saving
         last_continuation = saving
       else
         # After jump: print letters in reverse.
         output.print c
         jump_back last_continuation
       end
     else
       # Even word: Write letters immediately.
       output.print c
     end
   else
     # This character is punctuation.
     if reverse
       # End odd word. Fix trampoline, follow chain of continuations
       # (to print letters in reverse), then bounce off trampoline.
       first_continuation, c = savecc(c)
       if first_continuation
         jump_back last_continuation
       end
       output.print c      # Write punctuation.
       reverse = false     # Begin even word.
     else
       output.print c      # Write punctuation.
       reverse = true      # Begin odd word.
       # Create trampoline to bounce to (future) first_continuation.
       last_continuation, = savecc
       unless last_continuation
         jump_back first_continuation
       end
     end
   end
 end
 output.puts   # Print a cosmetic newline.

end

def odd_word(string)

 read_odd_word StringIO.new(string), $stdout

end

odd_word "what,is,the;meaning,of:life." odd_word "we,are;not,in,kansas;any,more."</lang>

Scheme

Output is identical to python. <lang lisp>(define (odd)

 (let ((c (read-char)))
   (if (char-alphabetic? c)
     (let ((r (odd)))

(write-char c) r)

     (lambda () (write-char c) c))))

(define (even)

 (let ((c (read-char)))
   (write-char c)
   (if (char-alphabetic? c)
     (even)
     c)))

(let loop ((i #f))

 (let ((c (if i ((odd)) (even))))
   (if (char=? c #\.)
     (exit)
     (loop (not i)))))</lang>

Tcl

Although the input is handled as strings, they're all as single-character strings.

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

proc fwd c {

   expr {[string is alpha $c] ? "[fwd [yield f][puts -nonewline $c]]" : $c}

} proc rev c {

   expr {[string is alpha $c] ? "[rev [yield r]][puts -nonewline $c]" : $c}

} coroutine f while 1 {puts -nonewline [fwd [yield r]]} coroutine r while 1 {puts -nonewline [rev [yield f]]} for {set coro f} {![eof stdin]} {} {

   set coro [$coro [read stdin 1]]

}</lang> Output is identical to Python and Scheme versions.

The only difference between the two coroutines (apart from the different names used when flipping back and forth) is the timing of the write of the character with respect to the recursive call.