Monday, August 2, 2010

I wanted more immediate feedback about my Rock Band scores, so I modified the code I wrote that takes a picture of the television screen and does OCR (optical character recognition) to figure out what song was just played, and run text-to-speech with the name of the song and my high score. It works about half the time. But when it works, I get to know if I got a new high score without having to go over to the computer and check, which means I can be ready to play the next song.

Monday, July 26, 2010

Continuing to look at the Project Euler problems. The third 10 are a little more difficult than the previous 20.

My Haskell solution for problem 21 was too slow. So, in Java, I made a table of the sum of the divisors for the numbers from 1 to 9999, then added up the numbers that pointed at each other, as well as the numbers in the table that paired with numbers greater than 9999, and it was reasonably fast.

Problem 22 was straightforward.

I could not write a fast algorithm for problem 23 in Haskell. So, in Java, I made a table of whether the number is abundant for 1 to 28123. Then, each number from 1 to 28123 could be tested by testing for pairs of trues in the table where the indices added up to the number, which should be less than around 200 million tests, and short-circuiting after the first pair is found means the actual number of tests should be much lower than that.

Problem 24 doesn't require much computation. The first element of the nth permutation is the (n-1)/m!+1th element, where m+1 is the number of elements, and the rest of the nth permutation is the remainder of (n-1)/m!+1th permutation of the remaining elements.

Problem 25 was straightforward.

My solution to problem 26 was kind of slow, but not excessively slow. I calculated the cycle length by making a list of the remainders and searched the list of remainders for repeats with each new digit in the quotient. After that, it was a brute-force maximum search: snd $ maximum $ map (\ n -> (cycleLength n,n)) [1..1000].

My solution for problem 27 was kind of slow. b must be a prime under 1000 due to n=0, so there 168 possibilities for b. Given b and n, p = n2 + an + b, where p is prime, so a = (p - b)/n - n, so p - b has to be a multiple of n, so I made a list of primes satisfying that condition, which can be mapped to a list of values for a, which can be filtered for |a| < 1000. Then, I brute-force searched the 168 values of b for the maximum n and the corresponding a.

Problem 28 doesn't require much computation. The numbers on the corner of the nxn square, where n is odd, is a simple function of n, so the numbers on the diagonals can be added by recursively adding the diagonals of the (n-2)x(n-2) square.

For problem 29, any pair that has ai ≤ 100, where i > 1 and i divides b is not distinct and can be filtered out.

My solution for problem 30 was quite slow. Since 6×95 = 354294, 299999 is an upper bound. 25 + 5×95 = 295277, 15 + 5×95 = 295246, so I used 295246 as an upper bound for the brute force search. After working on problem 34, which is almost the same problem with a much bigger upper bound, I made the search faster by searching by 10s and only going through the 1s digits if the sum of the other digits is between the number + 9 - 95 and the number. This could be generalized to further prune the search by only considering the most significant digits, and only iterating through less significant digits if sum of the digits is within range of the number.

Monday, July 19, 2010

Continuing to look at the Project Euler problems. The second 10 are a little more difficult than the first 10.

Problem 11 is yet another search. I used transpose . zipWith drop [0..] to get a quarter of the diagonals, and combined it with various uses of reverse to get the rest of the diagonals. The result was on a diagonal.

My solution to problem 12 was horribly slow with hugs, so I solved it in Java. The algorithm I used should be O(N3/2), and the answer I got was between 50 million and 100 million. Perhaps my calculation of triangle numbers was O(N2) in hugs, instead of O(N), causing the calculation to be O(N5/2).

Problem 13 might have been more of a challenge when restricted to fixed size integer arithmetic. As it was, take 10 . show . sum.

My Haskell solution to problem 14 was horribly slow, so I solved it in Java by tabulating the results under a million and using the recursive formula whenever it went over a million.

My Haskell solution to problem 15 was horribly slow, so I solved it in Java by tabulating the results by building on the previously tabulated results for smaller grids, which should be O(N2).

Problem 16, like problem 13, was a simple one-liner that would have been much more difficult when restricted to fixed size integers.

Problem 17 is just a matter of counting correctly, without any nontrivial mathematical reasoning or computation.

Problem 18 (and problem 67) can be solved with pretty much a one-liner: foldr1 (\ row sums -> zipWith3 (\ i l r -> i + max l r) row sums (tail sums)).

Problem 19 is an easy brute-force iteration, with only 1200 months to consider. The 100 and 400 year rules can be ignored, given the range.

Problem 20 is a simple one-liner just like problem 16, where the challenge is mainly for those restricted to fixed-size integers.

Monday, July 12, 2010

When there was only busy-work at work, I started working through the Project Euler problems. For the most part, I used the hugs implementation of Haskell, since the problems ought to be solvable without a huge amount of computation. However, some of my solutions were way too slow, so I used Java to solve some of the problems. I haven't submitted any of my answers, so I don't have that verification that my answers are correct.

Problem 1 was a simple one-liner in Haskell

p1 = sum [3,6..999] + sum [5,10..999] - sum [15,30..999]


Problem 2 was a simple 2-liner in Haskell.

For problem 3, I started by computing a list of primes. After getting the answer, I realized that calculating the primes was superfluous. I could just divide out all factors, starting from 2, regardless if they were prime or not, and the remainder would be the largest prime factor.

I just brute forced problem 4, though I can halve the search space since multiplication is commutative.

Problem 5 was a simple one-liner. Haskell's Prelude provides gcd.

Problem 6 was another simple one-liner.

My solution for problem 7 was pretty slow. Adding a type declaration: primes :: [Int], made it over 3 times faster, though still slow, with hugs. The inferred type would have been primes :: [Integer], but since all of the relevant numbers fit into signed 32-bit integers, [Int] would still give the correct result. I sped up a number of slow solutions by adding Int declarations.

I brute forced problem 8. Since the last digit was a 0, I could just do product . take 5 and not worry about a spurious result, which I would have had to worry about if the number had ended with 09999.

Problem 9 was another brute-force search. Since 1000 > c > b > a > 0, I could limit the search to 1000 > c > 333 and c > b > c/2.

My solution to problem 10 in Haskell was just too slow using hugs, so I wrote basically the same algorithm in about 20 lines of Java, which was fast. The result had to be a long, since it was too big to for 32-bit integers. I manually stored the computed primes in an array in the Java solution. Perhaps hugs wasn't memoizing the list of primes that was being computed, causing the algorithm that was supposed to be O(N3/2) to be O(N2).

Monday, July 5, 2010

The service that I work on interfaces with things that other people work on. One problem that came up multiple times is that these other systems have hard-coded invalid assumptions that have worked so far, for various reasons. One of the reasons is that one of the early features that didn't fit those assumptions simply got reclassified as unsupported and has been removed from every release. Due to these problems, I'll have to account for these hard-coded assumptions in these other systems when adding new features in the future.

Monday, June 28, 2010

I got pulled into yet another demo, involving building yet another prototype. I managed to get something functional in under a week, in about 2000 lines of Java. The next two weeks involved rewriting lots of the code either due to my misunderstanding of what it was supposed to do, or changes in what it should do after having something available to play with. Since I was the only one working on the code, I felt free to rewrite big chunks of it. The demo ended up being about 3000 lines of Java and seems to have gone successfully.

Two things, which I've said before, apply to this experience.

  • Being able to throw away the first few iterations is valuable. The design of later iterations can incorporate issues that weren't forseen in the earlier iterations.

  • Static typing makes replacing large chunks of code manageable. The compiler caught numerous little oversights, whereas using a dynamically typed language would have been much more painful.


So, for prototyping and rapid iteration, I strongly prefer using statically typed languages.

For an established code base that has many people working on it, rewriting large chunks of code is less of an option.

  • It's harder to understand all of the issues in a large codebase.

  • Management conservatism discourages potentially disruptive changes.

Monday, June 21, 2010

After setting up my computer to take pictures of my television screen when finishing a Rock Band song, I can go back and see if I got any new high scores afterwards. However, the leaderboard interface is limited by the controllers and navigating hundreds of songs is clumsy, so I came up with a way to make the computer do most of that work. I can get my scores from rockbandscores.com in csv format, and use OCR (optical character recognition) software to get the name of the song out of the picture.

The scores and song names show up in two different ways. In the middle of a set, the song name appears at the bottom left of the screen. At the end of the set, the song name appears at the top of the screen, in uppercase, and in a different font. There are also lots of non-textual graphics on the screen. However, the OCR software doesn't have to be anywhere near perfect, since all it needs to do is to enable distinguishing between a limited set of a few hundred song titles. So I got ocrad, which is free, lightweight, and fast, though not very sophisticated or flexible.

I send the upper part of each image and the lower left of each image through OCR after processing the piece of the image into monochrome, selecting the whitest and brightest pixels. Originally, I selected for the brightest pixels, but I found that also selecting for the whitest pixels worked much better. There are still lots of non-text clutter left, which the OCR software interprets. So after gathering data on what results the OCR software got from various pictures, I made and refined a heuristic for matching the OCR results with the song titles.

Here are some initial results after getting it to work pretty well. First, a song in the middle of a setlist:


Processing the upper part and the lower left part causes the song title to stand out in the lower left.


The OCR software does a reasonable job on the lower left:

M1dn19htR1d9r. . .
\ a ' ;' '' .. , 1
_-__.


The OCR text is good enough that it matches one song in the scores.csv file, the correct one, and I did not get a new high score:

[Midnight Rider, The Allman Brothers Band, GUITAR:75218 6.18, DRUMS:127100 5.37]


After finishing the set:


Processing the upper part and lower left part of the image causes the song name and score to show up cleanly in the upper part:


The OCR software returns:

FRRNH11N'5 7DWER
225,225 _K1,v,v_

and the A in the picture does look like an R, and the K does look like an H, and all the other misread characters do look like the characters returned by the OCR software. The score was also correctly recognized, but that usually doesn't happen.

Matching the text with the scores.csv file, I got a new high score:

[Franklin's Tower, Grateful Dead, DRUMS:223275 5.98, GUITAR:155807 6.67]