Tuesday, April 27, 2010

[TF003] You can only throw instanceof Throwable in Java (true/false?)

(true/false?) In Java, you can only throw something that is an instanceof Throwable.

Saturday, April 24, 2010

On the all other products, no division problem

This is among my favorite interview questions:
Given an array of numbers, return an array of the products of all other elements in the array.

More formally, write a method int[] products(int...), where products(nums)[i] is the product of all nums[j], j != i.
System.out.println(
   java.util.Arrays.toString(
      products(1, 2, 3, 4, 5)
   )
); // prints "[120, 60, 40, 30, 24]"
   // i.e. [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
You must do this in O(N) without using division.
I offer two solutions, both beautiful and hideous in their own ways.

Thursday, April 22, 2010

[TF002] dot-star matches all strings! (true/false?)

(true/false?) In regex, the dot metacharacter matches everything, and the star allows zero or more repetition, so for all s instanceof String, s.matches(".*").
static void tf002(String s) {
   if (s instanceof String) {
      assert s.matches(".*");
   }
}

Wednesday, April 21, 2010

[TF001] An empty string doesn't contain anything! (true/false?)

Note: This is the start of a (daily, hopefully!) series of articles exploring various "True or False?" statements regarding Java. Hint: they're all false. The idea is to correct misconceptions through counterproofs just have fun.
(true/false?) By definition, something is empty if it doesn't contains anything, so given String s1, s2, if s1.isEmpty(), then !s1.contains(s2).
static void tf001(String s1, String s2) {
   if (s1.isEmpty()) {
      assert !(s1.contains(s2));
   }
}

Tuesday, April 13, 2010

CodingBat string manipulation problems - Extra

This part includes solutions that I didn't come up with, my own variants of the original problems, exercising variations on previous regex solutions, etc.

A little help

plusOut: Given a string and a non-empty word string, return a version of the original string where all chars have been replaced by pluses ("+"), except for appearances of the word string which are preserved unchanged.
public String plusOut(String str, String word) {
  return str.replaceAll(
    "(?<!(?=word).{0,M})."
      .replace("word", java.util.regex.Pattern.quote(word))
      .replace("M", String.valueOf(word.length()-1)),
    "+"
  );  
}
Credit to Alan Moore on stackoverflow for this last one.

Monday, April 12, 2010

CodingBat string manipulation problems - Appendix

This appendix just has more examples, including one where my first attempt ended in an unreadable disaster.

Octoslash disaster

last2: Given a string, return the count of the number of times that the string consisting of the last 2 characters also appear elsewhere.
public int last2(String str) {
  return str.isEmpty() ? 0
    : str.split(
        "(.)(?=(.).)(?=.*\\1\\2$)",
        -1
      ).length - 1;
}
The above was not my first solution. That would be this one:

Sunday, April 11, 2010

CodingBat string manipulation problems - Part 5

This last part covers some solutions that aren't pure regex; unlike the other parts where I used stubbornly used regex whenever possible, here I use whatever comes naturally.

xyBalance: Return true if the given string is xy-balanced, that is for all the 'x' chars in the string, there exists a 'y' char somewhere later in the string. One 'y' can balance multiple 'x's.
public boolean xyBalance(String str) {
  return str.lastIndexOf('x') <= str.lastIndexOf('y');
}

Saturday, April 10, 2010

CodingBat string manipulation problems - Part 4

This second to last part shares a few things you should know about Java regex, how to measure lengths, the "2-for-1" technique, and a few other tricks.

Know your flags

withoutString: Given two strings, base and remove, return a version of the base string where all non-overlapping instances of the remove string have been removed (not case sensitive).
public String withoutString(String base, String remove) {
  return base.replaceAll(
    "(?i)" + java.util.regex.Pattern.quote(remove), "");
}
The 'i' flag enables case-insensitive matching; Pattern.quote is used (unnecessarily for codingbat tests) to match remove literally, giving no special meaning to any regex special metacharacters.

Friday, April 9, 2010

CodingBat string manipulation problems - Part 3

This part of the series covers relatively more complicated solutions, including one that exploits a known bug, and another using nested assertions.

Negative assertions

gHappy: We'll say that a lowercase 'g' in a string is "happy" if there is another 'g' immediately to its left or right. Return true if all the 'g's in the given string are happy.
public boolean gHappy(String str) {
  return !str.matches(".*(?<!g)g(?!g).*");
}
In the absence of s.contains("pattern"), one can always resort to s.matches(".*pattern.*").

Also note the use of first-order logic duality ∀x P(x) ⇔ ¬∃x ¬P(x) (the quantified version of De Morgan's law): instead of checking that all 'g's are "happy", we check that there isn't a 'g' that isn't.

Thursday, April 8, 2010

CodingBat string manipulation problems - Part 2

Continuing on with the series, this part shows basic uses of lookarounds and the split counting idiom.

Lookarounds

frontAgain: Given a string of any length, return true if the first 2 chars in the string also appear at the end of the string (allowing overlap).
public boolean frontAgain(String str) {
  return str.matches("(?=(..)).*\\1");
}

Wednesday, April 7, 2010

CodingBat string manipulation problems - Part 1

I had fun doing all the Java exercises on codingbat.com the other week (all 264 at last count). None of them were truly hard, but I challenged myself to stubbornly use regex whenever possible, but also especially when it actually leads to a much better solution.

This part shows some of the easier ones.

zipZap: Look for patterns like "zip" and "zap" in the string -- length-3, starting with 'z' and ending with 'p'. Return a string where for all such words, the middle letter is gone.
public String zipZap(String str) {
  return str.replaceAll("z.p", "zp");
}
Why regex? This is why!

Tuesday, April 6, 2010

Ternary operator idioms

I'm sure others have done something similar, but these are the idioms I use for ternary operators:
return what ? yes : no;

return what ? yes
  : noooooooooooooooooooooooo
;

return whaaaaatttttttttt
  ? yeeessss : noooooo
;

return whaaaaatttttttttt
  ? yeeeeeeeeesssssssssssssss
  : noooooooooooooooooooooooo
;

return
  thisWay ? thisThing :
  thatWay ? thatThing :
  otherThing
;
Variation include NOT having the semicolon on its own line, and of course return can be replaced by other grammatical possibilities (e.g. variable declaration and initialization), but these are the idioms in my standard repertoire that I've developed over the years.

I'm not sure how common these idioms are (the people at stackoverflow often complain of unreadability), but I'd like to think that these are very useful idioms, and very readable once you get used to it.

Why Floyd-Warshall is one of my favorite algorithms

Among classes of algorithms, dynamic programming is my favorite. The way it happened was almost a bait-and-switch: I was quickly drawn to it by its name, followed by a brief period of rejection ("Such a cool name and this is it?") and misunderstanding ("It's just caching!"), before eventually appreciation and finally admiration comes in.

If I have to pick a favorite among many dynamic programming algorithms, it will be Floyd-Warshall's all-pairs shortest path algorithm.
procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
Here's why it's cool: when you first learn about the shortest-path problem in your graph theory course, you probably start with Dijkstra's algorithm that solves single-source shortest path. It's quite complicated at first, but then you get over it, and you fully understood it.

Then the teacher says "Now we want to solve the same problem but for ALL sources". You think to yourself, "Oh god, this is going to be a much harder problem! It's going to be at least N times more complicated than Dijkstra's algorithm!!!".

Then the teacher gives you Floyd-Warshall. And your mind explodes. Then you start to tear up at how beautifully simple the algorithm is. It's just a triply-nested loop. It only uses a simple array for its data structure.

The most eye-opening part for me is the following realization: say you have a solution for problem A. Then you have a bigger "superproblem" B which contains problem A. The solution to problem B may in fact be simpler than the solution to problem A.

Sunday, April 4, 2010

sort3

A snippet from my latest question on stackoverflow "Reordering arguments using recursion (pro, cons, alternatives)", what I honestly believe is the most elegant solution one can write for sorting 3 values:
// sorts 3 values and return as array
static int[] sort3(int a, int b, int c) {
    return
      (a > b) ? sort3(b, a, c) :
      (b > c) ? sort3(a, c, b) :
      new int[] { a, b, c };
}
So far, most people say that the code is unreadable. Which is rather sad, actually.

I hope I won't ever have to dumb down my work for stupid people.

Saturday, April 3, 2010

ABC of regex

System.out.println(
   "abc".replaceAll("(?=(.*)).", "$1!")
); // prints "abc!bc!c!"

System.out.println(
   "abc".replaceAll(".(?<=(^.*))", "$1!")
); // prints "a!ab!abc!"

System.out.println(
   "abc".replaceAll(".(?=.*(?<=(^.*)))", "$1!")
); // prints "abc!abc!abc!"
Fun fact: non-obvious length lookbehind shouldn't even compile (Bug ID 6695369).

From regular-expressions.info:
Java takes things a step further by allowing finite repetition. You still cannot use the star or plus, but you can use the question mark and the curly braces with the max parameter specified. Java recognizes the fact that finite repetition can be rewritten as an alternation of strings with different, but fixed lengths.
Well, so much for that limitation.