!752

p {
  S s = "Hello world world world";
  print("Original:\n  " + s);
  S transformed = bwt(s, '|');
  print("BWT Transformed:\n  " + transformed);
  S x = inverseBWT(transformed, '|');
  print("Transformed back:\n  " + x);
  print(eq(s, x) ? "Yo!" : "No...");
  print();

  // Transform it again
  S doublyTransformed = bwt(transformed, '^');
  print("Doubly Transformed (not very useful):\n  " + doublyTransformed);
}

static S bwt(S input, char endMarker) {
  input += endMarker;
  int n = l(input);
  S[] tbl = new S[n];
  for i to n:
    tbl[i] = rotateString(input, i);
  sort(tbl);
  new StringBuilder buf;
  for i to n:
    buf.append(last(tbl[i]));
  ret str(buf);
}

static S rotateString(S s, int n) {
  if (n == 0) ret s;
  ret substring(s, l(s)-n) + substring(s, 0, l(s)-n);
}

static S inverseBWT(S s, char endMarker) {
  int n = l(s);
  S[] tbl = new S[n];
  for i to n:
    tbl[i] = "";
  for i to n: {
    // insert
    for j to n:
      tbl[j] = s.charAt(j) + tbl[j];
      
    // sort
    sort(tbl);
  }
  for i to n:
    if (last(tbl[i]) == endMarker)
      ret dropLast(tbl[i]);
      
  fail("NEVER FAIL in a perfect world!");
}