!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!");

}