1 // 2008 ACM Mid-Central USA Regional Programming Contest
  2 // Test Generator for Problem H: "Steganography" [easy/moderate]
  3 // Eric Shade, Missouri State University
  4 
  5 // NOTE: This program uses Deque, so it requires Java 1.6.  However,
  6 // it's not a solution to the problem, it's used to generate test
  7 // data.  All Java *solutions* for this year's contest are compatible
  8 // with Java 1.5.
  9 
 10 
 11 import java.util.*;
 12 
 13 class stegenc {
 14     static int WIDTH;    // max line width, not including newline
 15 
 16     static Deque<Integer> bits;
 17     static Deque<String> words;
 18     static ArrayList<String> line = new ArrayList<String>();
 19     static ArrayList<Integer> spaces = new ArrayList<Integer>();
 20 
 21     static Random rand = new Random();
 22 
 23     public static void main(String[] args) {
 24         if (args.length != 2) {
 25             System.err.println("Syntax: java stegenc width \"message\".");
 26             System.err.println("Reads text from standard input and writes to standard output.");
 27             System.exit(1);
 28         }
 29 
 30         WIDTH = Integer.parseInt(args[0]);
 31         getBits(args[1].toUpperCase());
 32 
 33         Scanner in = new Scanner(System.in);
 34         words = new ArrayDeque<String>();
 35 
 36         while (in.hasNext()) {
 37             String w = in.next();
 38             if (w.length() > 0) words.offerLast(w);
 39         }
 40 
 41         in.close();
 42 
 43         while (! bits.isEmpty()) {
 44             // create a line, then print it out
 45             line.clear(); spaces.clear();
 46             String w = nextWord();
 47             int n = w.length();
 48             line.add(w); spaces.add(0);
 49             while (! bits.isEmpty() && n < WIDTH) {
 50                 int b = bits.pollFirst();
 51                 w = nextWord();
 52                 if (n + w.length() + b + 1 <= WIDTH) {
 53                     spaces.add(b + 1);
 54                     line.add(w);
 55                     n += w.length() + b + 1;
 56                 } else {
 57                     bits.offerFirst(b);
 58                     words.offerFirst(w);
 59                     break;
 60                 }
 61             }
 62             justifyLine(WIDTH - n);
 63             for (int i = 0; i < line.size(); i++) {
 64                 int s = spaces.get(i);
 65                 for (int j = 0; j < s; j++) System.out.print(" ");
 66                 System.out.print(line.get(i));
 67             }
 68             System.out.println();
 69         }
 70 
 71         System.out.println("*");
 72     }
 73 
 74 
 75     static void justifyLine(int s) {
 76         while (s > 1) {
 77             // add two spaces to zero bits
 78             for (int i = 1; i < spaces.size() && s > 1; i++) {
 79                 if ((spaces.get(i) & 1) != 0) {
 80                     spaces.set(i, spaces.get(i) + 2);
 81                     s -= 2;
 82                 }
 83             }
 84             // add two spaces to one bits
 85             for (int i = 1; i < spaces.size() && s > 1; i++) {
 86                 if ((spaces.get(i) & 1) == 0) {
 87                     spaces.set(i, spaces.get(i) + 2);
 88                     s -= 2;
 89                 }
 90             }
 91         }
 92 
 93         while (s == 1) {
 94             // this will fail if all words have length one!!
 95             int i = rand.nextInt(line.size());
 96             String w = line.get(i);
 97             if (w.length() == 1) continue;
 98             int k = rand.nextInt(w.length() - 1) + 1;
 99             line.set(i, w.substring(0, k) + "_" + w.substring(k));
100             s = 0;
101         }
102     }
103 
104 
105     static String nextWord() {
106         if (words.isEmpty()) {
107             System.err.println("Not enough words to encode the message!");
108             System.exit(1);
109         }
110 
111         return words.pollFirst();
112     }
113 
114 
115     static void getBits(String msg) {
116         bits = new ArrayDeque<Integer>();
117 
118         for (int i = 0; i < msg.length(); i++) {
119             int code = charCode(msg.charAt(i));
120 
121             if (code < 0) {
122                 System.err.printf("Invalid character '%c'.\n", msg.charAt(i));
123                 System.exit(1);
124             }
125 
126             bits.offerLast(code >> 4);
127             bits.offerLast((code >> 3) & 1);
128             bits.offerLast((code >> 2) & 1);
129             bits.offerLast((code >> 1) & 1);
130             bits.offerLast(code & 1);
131         }
132 
133         while (bits.peekLast() == 0) bits.pollLast();
134     }
135 
136 
137     static int charCode(char c) {
138         switch (c) {
139         case ' ' : return  0;
140         case '\'': return 27;
141         case ',' : return 28;
142         case '-' : return 29;
143         case '.' : return 30;
144         case '?' : return 31;
145         }
146 
147         return 'A' <= c && c <= 'Z' ? c - 'A' + 1 : -1;
148     }
149 }