Saturday, January 30, 2010

Lessons from Java Puzzlers

*head explodes*
*pulls hair*
*jaw drops*
Am I the only one who thinks that nested multi-line comments should be universally supported across all modern languages? It's not that much harder to parse, and it doesn't happen often but I remember specifically wishing for this language feature in the past.

And while we're at it, I think nested HTML anchor elements should be supported too.
It's quite enlightening to learn how Java matures over time. I remember when Cloneable was initially promoted as the new cool thing, but now pretty much everybody agree it's a broken mess.

Wednesday, January 27, 2010

Java!?!? NOT YOU TOO!?!?

ARGH!!! Why would a high-level language like Java behave like this!?!?

I dare any programmer to explain why this should be the preferred, or even expected, behavior.
I'm also slightly disappointed that Arrays.binarySearch() does not guarantee which value will be found in the case of multiple matches. I don't use Python, but the consistency provided by the bisect_left/right() algorithms is needed sometimes.

Oh well, at least sort() is guaranteed stable...
Also, why doesn't Math.min() do varargs? At least provide an overload for 3 arguments for my common DP needs!
I wonder if Java was the first language to allow an optional trailing comma in its array initializer syntax. It's a "feature" that I absolutely love, but I can see how that decision might've been contentious. // Nah, C has had it for a long time, apparently...
I need to get this book: Java Puzzlers: Traps, Pitfalls, and Corner Cases. I bet this shift behavior is in there somewhere. / Yep, Puzzle 27: Shifty i's.
I just found out that Java has non-short-circuiting boolean logical operators.

Unsolvable puzzle?

I will admit that I've tried to solve this puzzle twice now and failed miserably both times.

A high school math teacher chose three of his best students to conduct a little experiment. He said, "I have chosen a three-digit number, N, with the first digit not more than the second and the second not more than the third. I also have chosen a function, F(N), which is one of these five functions:

(1) SUM(N) = The Sum of the digits of N.
(2) PROD(N) = The Product of the digits of N.
(3) SSQ(N) = The Sum of the Squares of the digits of N.
(4) SSC(N) = The Sum of the Cubes of the digits of N.
(5) LCM(N) = The Least Common Multiple of the digits of N.

"I then calculated the value, V = F(N), and have written the three items, N, F, V, each on a separate piece of paper and will give one to each of you. You must try to determine the other 2 items not on your paper. You may use your computers, but cannot collaborate. Don't turn in your answers until I ask for them. Don't worry about any unfair disadvantage of which item you get, this is not a competition, only an experiment. Just make your lists and we'll see what happens!"

Here is what happened:
1:00 - Students begin working.
1:20 - Teacher asks if anyone had found the answers. No one had.
1:30 - Teacher asks if anyone had found the answers. No one had.
1:31 - Teacher asks if it would help if he told them if N was odd or even. All 3 say no.
1:40 - Teacher asks if anyone had found the answers. No one had.
1:41 - Teacher asks if it would help if he told them if V was odd or even. All 3 say no.
1:50 - Teacher asks if anyone had found the answers. No one had.
1:51 - Teacher asks if it would help if he told them the sum of N and V. All 3 say no.
2:00 - Teacher asks if anyone had found the answers. All three of them had!
Admitting that I've probably reached my limit, I posted it on XKCD forum (which I don't really frequent) to get input from others. This reply sums up my frustration exactly:
The fact that no reader of solved the final puzzle makes me reluctant to put the time into it. In theory it's the same process, but I'm not completely confident of how to parse "if it would help".

ETA: And now that I've put some time into it, it looks even more poorly defined than I had originally suspected. I'm really pretty surprised, coming from Robert Kraus and Ed Pegg, Jr.

A possible breakthrough: the envelopes may be unlabeled. A person that sees a number may not know if that's N or V. Along that line, F may also be written as a number 1..5.
Discussion on GreyLabyrinth forum | For what it's worth, the answer is supposed to be SSQ(336)=54.

Tuesday, January 26, 2010

Free e-books!

These were linked from AZSPCS's Yahoo! Groups:
- Thomas Weise: Global Optimization Algorithms - Theory and Application (see: SIGOA)
- Fred Mellender: Design Patterns for Searching in C# (PDF/code)
Speaking of which, I've dropped to 59th place in the standings, with a score of 89.57. I suppose I should go back to this contest again before it ends...
By the way, something I just discovered yesterday: sandbox pastebins (e.g., Yes, I'm kind of slow about these things...

Saturday, January 23, 2010

Facebook puzzles

Some notes about how to pass the current Facebook puzzles with the least amount of effort. I don't try to be verbose, but needless to say, SPOILERS AHEAD.

#7 hoppity: It's a FizzBuzz test, basically.
#3 meepmeep: I have absolutely no idea why this is even here. Actually, now that I think about it... Nah, even if the input file (that you're instructed to open but then ignore) contains some usable information, there's no easy way to retrieve it.
#20 liarliar: Straightforward UF.
#17 breathalyzer: The O(nm) L-d algorithm is fine. The dictionary is known in advance, but there's no need to preprocess it. No need for a fancy data structure to represent it either.
#15 gattaca: Straightforward wIS.
#13 simonsays: The hardest part is setting up the Thrift framework.
#12 dancebattle: Despite the warning, nothing insightful is necessary. Go ahead, code that obvious brute force algorithm and send it. It'll pass.
#6 smallworld: Use double precision (remember that Infinity * 0 is not 0, etc). No need to batch the k-NN retrieval.
#2 usrbincrash: Straightforward is fine.
#18 rushhour: I think this puzzle is broken, actually. Funny story: I crashed the server once. / Dear god! This puzzle is even more broken than I initially thought!
#14 battleship: Just create 2 dumb clients and have them play against each other.
#10 fridgemadness: Straightforward G-S implementation is fine.
#8 peaktraffic: Straightforward B-K implementation is fine.
#5 swarm: A layer of obnoxiously concocted math obfuscates a straightforward combinatorial problem.
#19 dinoisland: (not yet) This requires lots of investment, and honestly, I'm not sure if it's worth it. I'm not even sure if they guarantee that sufficient intelligence yields survivability. Who knows what lives on that island right now. This one time I hatched and someone ate me right away.
#11 sophie: Brute force is fine, apparently... Nope, it just got harder...
#1 facebull: (not yet) This is the Minimum Spanning Strong Subdigraph problem. <- No it's not! Anyway, somewhat surprised that I solved it, but I did. It's a computationally intractable problem, but my suggestion is to give it a try anyway.
"Hidden" ones I've found:

[hidden#1]: Noisy, buggy, this puzzle is frustrating as hell, but solvable. Use the 162x348 version. You'll get the congratulatory confirmation e-mail, but I don't think the app lets you publish that you've solved it.

[hidden#2]: I had to have someone point me in the right direction to find it, but this was a VERY satisfying puzzle.
Some prime numbers I've seen:

- The e-mail address: {0xFACEB00C>>2 in decimal} = 1051962371 is prime.
- From swarm: 654195331 = 0x26FE3A83 is prime.
- From [hidden#1]: even though the metric makes no sense for this problem, the confirmation e-mail reports that my longest running time is 73.127 ms. 73127 is prime. // Others have reported receiving different, non-prime numbers.

Tuesday, January 19, 2010

"Aber einzigartig... danke."

Are you prime? has spread a bit despite me having abandoned it for weeks now. The really cool thing is that people actually start using its publishing feature -- pretty much its only mean of spreading.

In case you're wondering, it's "but unique... thank you" in German. It's a reference to my (empty) consolation to the composites: that though it isn't prime, it's still unique (duh?). The number happens to be a squarefree semiprime (A006881). Which I think is a class special enough that it should have its own name.
Oh, and it's now approved for directory listing too. None of this really matters now, but it still makes me warm and fuzzy.
Other interesting things seen in the log:

- Record for highest number of friends seen so far: 3004. Of those, 124 are primes.
- A person had 97 friends, 6 of those prime. Apparently not satisfied, he later came back with 139 friends, 9 prime.
- One person was so amused by the app that he spammed all of his prime friends.
Hmm this is getting embarassing, actually. I should make something much bigger than this.

Saturday, January 16, 2010

Named algorithms

Obviously this is not an exhaustive list, and it omits some important algorithms as well (e.g. Lempel-Ziv family). I'm also not interested in listing algorithms whose common name is quite descriptive (e.g. Sieve of Eratosthenes, Gauss-Jordan elimination, etc).

Shortest path in a graph:
- Dijkstra's algorithm - single-source
- Bellman-Ford algorithm - single-source, negative edges
- Floyd-Warshall algorithm - all-pairs (it's neat how concise and straightforward this solution is to what at a glance looked to be a harder super-problem)

Maximum flow of a network:
- Ford-Fulkerson algorithm
- Edmonds-Karp algorithm (frankly I don't think this deserves its own name)

Minimum spanning trees:
- Kruskal's algorithm
- Prim's algorithm

String search:
- Knuth-Morris-Pratt algorithm (cool automaton!)
- Boyer-Moore algorithm (it works backward!)

Computational biology:
- Smith-Waterman algorithm - local sequence alignment
- Ukkonen's algorithm - suffix tree construction
- "Kärkkäinen's algorithm" - suffix array construction (not sure what other people think of it, but it still blows my mind how elegant it is)

Pseudorandom number generator:
- Blub Blum Shub (I don't think I can ever say it with a straight face)

Matrix multiplication:
- Strassen algorithm (it took me a few years before I gave this algorithm a chance; it's actually pretty cool, not to mention revolutionary)
- Cannon's algorithm (surprised that Wikipedia doesn't have more on this rather neat algorithm; maybe I'll contribute some day!)

- Shor's algorithm - prime factorization

- Algorithm P - random shuffle
- Algorithm X - exact cover
- Algorithm W - type-inferrence (this is what inspired this entry, actually)

And I guess I'll mention this one for giggles:

- God's algorithm

Monday, January 4, 2010

Prime bits

OEIS A000788: Total number of 1's in binary expansions of 0, ..., n

One of the given formulas there is very interesting:
a(0) = 0;
a(2n) = a(n)+a(n-1)+n;
a(2n+1) = 2a(n)+n+1
I've still yet to decypher how that formula is derived, but here's mine in Maple:
full := n -> n * 2^n / 2:

flog2 := n -> floor(log[2](n)):

f := n -> `if`(n = 0, 0,
full(flog2(n)) + (1 + n - 2^flog2(n)) + f(n - 2^flog2(n))
My formula basically partitions the rectangle of bits into 3 parts: top (first 2^k lines, explicit formula trivial), bottom-left (a single column of 1's) and bottom-right (the rest, counted recursively).
Ah, got it. The first formula reduces the problem by separating out the rightmost column and deinterleaving what's left. In any case, this problem is inspired by a Facebook puzzle, whose exact definition I can no longer find. I can assume it to be the following:
Given a, b, count how many numbers in the interval [a, b] have prime number of 1's in their binary representation.
My solution in Maple: