Skip navigation

Tag Archives: algorithms

While technically not part of my 2016 Resolution, I also got this:

66th percentile on HackerRank

You may be thinking, “66th percentile! Three stars! For an Asian, your standards aren’t much.”

Well, considering that I have a full-time job and that just around this time last year I was below 20th percentile, I’m calling this a win. ūüėČ ūüėČ

Happy 2015! If you are reading this it means I actually got to finish writing this blog post and it did not go to that Graveyard of Unpublished Posts in my server.

I started 2015 (the first few hours of January 1st) finishing off a phase of a personal project I’ve been working on for a few months now. World, meet Chess Templar.

So well, I guess its time for some public documentation. That’s what this post is exactly.

So what is this project all about?

Around August of 2014 (August 18, 2014, to be precise), I got fascinated with Chess. I’ve had bouts of fascination with Chess before this but I did not push it that much. I remember spending a chunk of my after-school Grade 6 time playing Chessmaster 5500. During my third year in college, I had the idea that if I play a game of chess everyday, by the end of a month, I would’ve played 30 games, and I’m 30 games more experienced than I was a month ago; I played against the Chess program in Windows Vista and against GNU Chess. I had the same idea in 2013, only that time I played against Chess Free in Android.

The thing with those bouts is that they did not last because, I guess, I was ill-equipped to study Chess. Reading reviews of Chessmaster 5500, I keep running across the remark that it has an excellent tutorial mode. I have vague recollections of using that mode but I think I just did not see the reason behind the moves the AI was coaching. Besides, will you ever trust an AI that it will coach you to defeat itself?

Sure now there are lots of software out there for studying Chess, some even free. But then, I don’t find that they have the features I’d like to have while¬†I study Chess.

What features?

For one, I’d really like an engine that will help me practice a particular opening. Or annotate games. And I’d like to be able to tinker with the algorithms (not just the parameters) of my engine.

Hey, I found this Chess software that does exactly that and it’s free and open-source!

Oh. I forgot to say that this is also my rather-lengthy exercise on artificial intelligence. There’s a reason I wrote it in Java (not my usual Python project).

To note: Had I only wanted a Chess engine to play with, I would’ve forked PyChess.

What do you have now? What’s coming up next?

The biggest chunk of Chess Templar right now is the GameArbiter, which enforces the rules of Chess. I have tried to be as meticulous as possible in encoding creating the arbiter. To mind it can take account of:

  • En passant captures
  • Subtleties of castling: you cannot castle out of, through, or into a check.
  • Rules on dealing with checks.

Notably, it cannot yet account for:

  • Draws. Man, draws must be among Chess’ most complicated rules.
  • Pawn promotions. Actually, I have not yet decided where in my code should I handle Pawn promotions.

That said, at 317 commits at press time, GameArbiter would still handle endgames poorly.

Also, coming up next is adding rudimentary AIs. I’m still studying Chess-playing algorithms. Chess is a well-known example of combinatorial explosion so it automatically rules out basic minimax, unless maybe if I limit the depth (but how much good will that be?).

To count, there are 20 possible first moves:

  • each of the eight pawns can either advance one or two squares -> 16 moves
  • the two knights have two squares each to move to -> 4 moves.

Black, in reply, have the same 20 choices.

Any metrics you are using to evaluate your output?

In the long run, if I make it good enough, I want to pit whatever engine I come up with in the Thoresen Chess Engine Competition. For now I’m settling with getting good unit-test coverage.

(Note: This is a fault of the Maven coveralls plug-in I am using but the badge at the repo’s README is misleading in terms of my current code coverage. Check the last link to see that I am at 91.86% coverage at press time).

Any algorithms/tricks/hacks you would like to note?

To check on the King’s safety, I modeled the relationship of pieces and squares in the board as a directed graph. For every square in the board, an edge is incident to it if any piece can move to it on a side’s next turn. Only squares with pieces occupying them can have an edge incident from them. (So, if an occupied square has an edge incident to it, it means that that particular piece is in danger of being captured.)

With this representation, I want to check on “hotspots” in the board: squares with the most pressure, pieces under the most pressure. Just a gut feel that I could make an engine take advantage of this.


So there, everything of note in my project so far. Happy new year and, if you’re interested, fork me on GitHub!

 

I’ve always wanted to discuss algorithm problems here but a quick look over at my posts (even just the tags) reveals that I haven’t really done much of that. Over at Github, I have a repository dedicated to solving Programming Praxis problems1 and I’ve thought of discussing my answers here but I haven’t had the time. My interview with Google is, I think, a good chance to dish out something similar to my intentions.

(Author’s note: Of course, I won’t discuss the specific problems I encountered during my interview. For reasons that will become clear if you think about it for a moment, Google clearly prohibits that.)

There are three stages I encountered during Google’s interview process. The first is a short initial (phone) chat with a recruiting coordinator. Next I had a phone technical interview which, aside from taking a longer amount of time, had me coding on a Google Doc. The third part is where they flew me to Mountain View, an interview which Google terms as “panel interview” but I will forever stubbornly refer to as a “circuit interview”.

My interviews, in general, looked at my problem solving skills. For a company like Google, I expected that they will be more interested in my¬†engineering¬†competence, i.e., questions like “How do you get things done?”, “What frameworks have you used?”, “Why would assembly trump everything?”, “Concurrency, Cloud Computing, Parallelization, Multi-core issues, Efficient Caching Mechanism, High-Throughput Responsive MVC Framework Layer MOAAARRRRR!!!”2 .

Watch this short video featuring Laszlo Block on the type of people Google is after. It may be hard to believe, as it was for me, but based on my experience, this is so true.

Overall, I’d say that my Google interview was 85% algorithms/problem solving and 15% engineering.

I found the second phone interview a bit bumpy that afterwards I did not really expect much. I was just happy that I got a Googler asking me technical questions. My interviewer’s voice wasn’t very clear through the phone (as opposed to the first one). It did not help that I was having coughs that day which later developed into a slight fever.

And, as you may know, Google Docs isn’t really made for coding. I wish Google used a platform more suitable for writing code than a word-processing document. My interviewer wasn’t meticulous about syntax but it was still awkward indenting my lines.

That said, here are some tips:

  1. For this part, do not use Python (or any similar whitespace-based language). I was intending to use Python even though I’ve already expected indentation to be difficult. Thankfully, my interviewer stated at the beginning that he’d prefer me to use Java. With Java, you can skip indentation for small blocks of code. Convenient when your line is getting long or the nesting goes deep3.
  2. Indent using two spaces. This is the indentation style of my first company. Tab is too wide and your lines might easily bleed off the edge, especially if you follow my first tip (new BufferedReader is already 18 characters!).

    Why indent at all? Well, no one’s forcing you but I find it easier to debug if I have indentations. Moreover, code is easier to read.

  3. Don’t hesitate to use the Google Doc for things other than code (like clarifications). Remember I said that my interviewer’s voice through the phone wasn’t very clear? Well, this is exactly what saved me.

As for the onsite, Google will be kind enough to fly its candidates in two days before the actual interview so you can settle down. Due to PyCon Philippines, I was unable to take full advantage of this. Nonetheless, I felt little to no jetlag that I even had time to explore a bit on my first night.

Here’s a little tip though: when coordinating with Google’s recruitment team, be clear and patient when it comes to your travel requirements. Based on my experience, Google’s recruitment team is very accommodating and helpful but that is not to say that they are 100% knowledgeable on the arrangements their applicants have to make for travel. (Cut them some slack as I’m sure they handle applicants from more countries than what you can name off the top of your head.)

In my case, I raised the point of needing a Visa for USA travel early on but it was ignored in the email thread so I assumed it’s okay. Thankfully, the issue came up when I coordinated with their preferred travel agency. This delayed me by almost a month. I should’ve been persistent because I’ve been raised since childhood knowing that Filipinos entering the USA¬†need a USA Visa.

Google would really want you to focus on your interview so there is very little that you need to mind during your stay. They’d have your basics covered (accommodation, reimbursable food allowance, reimbursable transportation allowance) so¬†just keep your receipts.

Here’s the interesting part. The onsite interview itself will last for five hours, lunch included (for comparison, the longest job interview I’ve had lasted for, I think, three hours, and it was more a personality interview; HR was talking to me). The reason why I will forever term it as “circuit interview” is because you will have five sets of interviewers, each of them in turn, as opposed to having all your interviewers in one panel.

As I’ve said, my interview was more algorithmic than engineering. One of my biggest anxieties was if they’d give questions the kind they give at ACM ICPC. I’m pretty sure I’d be tongue-tied had that happened. But fear not. The problems I encountered were less obscure and they won’t require you to provide full implementations for the more complicated ones.

Well, I did not make it so you may want to take the following with some grains of salt. But, hey, some tips:

  1. Use Python, finally. Or, bring your own whiteboard markers, as Steve Yegge advises. I’ve read Steve Yegge’s post prior to my interview but I missed the point on his tip about the whiteboard markers. I thought he was advising it just for the “preparedness” factor but notice that he advises it for the sake of whiteboard space. And yes, whiteboard space can be a real blessing. I want to note that, when I was there, Google’s Mountain View office had those flat-tip markers in stock, the kind like highlighters. In my opinion, that’s worse for an interview than the “fat ones” Yegge refers to in his post.

    Nonetheless, with Python, I was able to squeeze in three functions plus lots of scratch and some illustrations in a whiteboard of standard office size. I cannot imagine how that’d look like with Java (or worse, C/C++), nor can I overstate how good a thing is this.

    For the record, I brought my own whiteboard marker but I did not use it, did not even show or mention it, because I got anxious as to coming across as “too eager”.

  2. Use Python, again.¬†This might vary from programmer to programmer but Python gave the advantage that I can focus on high level stuff. Given the nature of Google’s interview process, I believe this worked to my advantage. It’s really like doing runnable pseudocode.
  3. Use Python, not. I think I know where the weak points of my interview was and I believe I was weakest during the last interview. You see, the interviewer started with “I heard you use Python so just keep using that.” So I did. But then he gave me a problem that would require some low-level manipulation and, as I was using Python, I took time clarifying what am I allowed to do and what am I allowed to assume.
  4. Just keep talking. Remember my anxiety above that I might get tongue-tied? Well, here’s the tip: just keep talking, as long as you’re making relative sense. I’ve been told in a pre-interview email that they want to learn how I think so think out loud.¬†Obviously, I’m not sure if this worked to my advantage or what but at least I managed to avoid that Great Wall of Social Awkwardness Produced by Silence. It might even help you;¬†there was a part in my interview when I was like “Let me try some combinatorics here…so 2 will give this…3 will give that…but 4, oh wait‚ÄĒthis is easier to to solve programmatically!”. No kidding.
  5. Relax, this isn’t the ACM ICPC. This comparison might deserve a post on its own but for now, the most obvious difference is the time constraint. I realized that the people interviewing me would like to get a picture of me in just around 45 minutes. So, in contrast to the ACM, they’d give you problems that are solvable in 45 minutes or less. Moreover, your code won’t be ran so (at least I think, and this I did), you are allowed a certain extent of handwaving and just say this function does this and that. At times, high-level descriptions of algorithms will also suffice (read: implementation, with all the debugging that might entail, is not needed).

Finally and most importantly,¬†Prepare with a capital ‘P’. Read the Steve Yegge blog post I linked above and follow his advice on having long-term and short-term preparations. I just said above that Google interview isn’t ACM ICPC but I think ACM ICPC is good standard practice material and not just for Google interviews.

What do you prepare for? In my case, knowledge of data structures like some obscure variants of balanced binary trees and even-rarer forms of trees and forests helped as it gave me some talking points. A good knowledge of textbook algorithms will also help. In one case, repurposing a textbook algorithm allowed me to reduce a naive O(n2) algorithm to just O(n).

That said, even if you’re not planning to take a Google interview anywhere in the foreseeable future, I still find preparations of this kind useful for everyday. So just keep reading up and honing your problem solving knack!

  1. I have a similar private repository for the other algorithm problems I’m solving‚ÄĒACM ICPC practice, to be specific. As a matter of principle, I’m willing to show my code solution to algorithm problems provided that the problem setters are¬†expressly showing solutions, as with Programming Praxis. []
  2. Okay I’m trying to be funny here. But you get my idea of engineering vs. algorithmic skill. []
  3. Generally, I’d be cautious against getting too deep a nesting. When I encounter this in my code, it’s a sure sign that I’m getting lost and that maybe I need to refactor or re-read the problem []

Okay. I know it’s already February and that it’s kinda late. But it’s in times like this that I say “better late than never!”. But as I’ll show, I’ve already started with my resolutions‚ÄĒI’m just writing about them now.

But since this is my coding blog, the resolution I will mention here will be my technical-life¬†resolution (as opposed to the personal ones everybody makes). So, without further ado…

I resolve to learn a new technology every month. Or, at least, get deeper with one I’m already acquainted with.

Also, I’d go into programming competitions/contests again. Team requirements limit my choices but, hey, there are a lot I can do alone online, not to mention free! (Though if anyone wants to team-up with me, let’s talk.)

And, just so I’ll stick with it, I’ll write a blog post every month about what I’ve been up to. Consider this the one for January.

For my first resolution, I created this sandbox repository at GitHub. And since my GitHub account is, in itself, already my sandbox of sorts, I guess this is some sandbox-ception eh?

January, I did¬†sockets in Python. I didn’t manage to dig as deep as I’d have wanted because the Facebook Hacker Cup kicked in earlier than I expected and that falls under my second resolution. So it had to give way. Besides, I’m already dealing with a few sockets too many at work.

Regarding my second resolution, I don’t really expect much from it. At least, I won’t get rusty from the lack of problem sets in the real world (read: industry). At most, I might score a free trip to some world finals.¬†But that world-finals scenario is still very out of my league. I’ve been doing ACM-ICPC problems since I was in my sophomore year in College and even now I find most of them really tough and tricky. Also, after less than a year out of school, I’m bound to have some rust in my system (not that school is a sure fire way to keep you sharp though). I only decided to start practicing with my algorithms sometime in December so there isn’t really much to expect.

(Note: I started writing this post in the last hour before the first round of Hacker Cup started. It’s now over and everything fell within my expectations. There’s a lot to learn. Maybe, I’ll write about this soon.)


So, what do I think about sockets in Python? (This will be short since, as mentioned, I didn’t have much time to dig deep into this.)

As with all things Python, it looks super neat. I got a client and server up and running in just 41 lines of code combined. The biggest savings comes from the fact that socket I/O is direct in Python; you no longer have to create OutputStream and InputStream objects as the socket objects themselves have methods for sending and receiving. It’s also interesting to note that Python’s socketserver class has a serve_forever method which, as the name implies, handles requests as long as it can (the official phrase is: “until an explicit shutdown signal is received”).

Oddly, this design reminds me how I handled one of the things I did at work. Won’t go into the details but I thought that it’s neat to have one class responsible for managing one whole session: packet numbers, windowing, etc. One instance of a class maps to one client; when client goes away so does this instance (at least, I no longer care if the garbage collector marks it as garbage). Makes OO live more peacefully with concurrency.

Awesome that Python enforces this design by default. Really, the more I discover about Python, the lovelier programming gets.

‘Till I get my February experiments done! ~Chad

Note:¬†My thesis is done. However, there are still some things which I find of interest to address here. Due to how our thesis was (mis)handled, I’m only finding the time to post about these things now.

Last time, I told you how we are porting all our Matlab/Octave code to Java. I wrote about a huge difference between Matlab and Octave’s implementation of rgb2gray. However, as it became apparent to me, my issues with rgb2gray are not quite done yet.

First a little background. Our project relies heavily on the Fast Fourier Transform, a numerical algorithm whose products I bet you encounter everyday though you probably are not aware of it. The 2D FFT is built-in with Octave, as expected for a language meant specifically for mathematical processing. The same, however, cannot be said for Java.

It’d be crazy for me to attempt to code it from scratch due to a number of reasons not the least of which is the fact that I don’t really have a solid training with numerical algorithms. So, after browsing through various libraries, we decided to use JTransforms, largely because we can see the source code for ourselves and it is natively in Java, in contrast to, say, FFTW, which has Java bindings¬†but is natively in C. Plus, it does not have power-of-2 constraints, a common trait among various implementations of the FFT.

Now, the thing is, there seems to be quite a considerable offset between the FFT results of Octave1 and JTransforms; the kind of offset which you’d be so tempted to chalk up to floating-point handling differences though some part of your reason tells you it is too large to be so. The offset I was seeing ranged from 2 to 12 integer values.

As I admitted earlier, I don’t have any solid grounding with numerical algorithms. The way I see it, there are a number of possible culprits on why I’m not getting the results I should get. The FFT, after all, is a blanket term for a family of algorithms which all do the same thing, namely, apply the Fourier Transform to a discrete collection of values (i.e., vectors or matrices).

What I’ve Tried (Or, the scientific probable reason on why there is this offset, as discussed by my adviser)

Warning:¬†Some equations ahead. I wouldn’t be delving too much into the equations and you should be able to understand my main point with just some basic algebra. But just so you know.

Consider this tutorial on the FFT.

It defines the 2D FFT as:

F[k,l] = \frac{1}{\sqrt{MN}}\sum_{n=0}^{N-1}\sum_{m=0}^{M-1}f[m,n]e^{-2\pi i(\frac{mk}{M}+\frac{nl}{N})} f[m,n]= \frac{1}{\sqrt{MN}}\sum_{l=0}^{N-1}\sum_{k=0}^{M-1}F[k,l]e^{2\pi i(\frac{mk}{M}+\frac{nl}{N})} 0 \leq m,k \leq M-1, 0 \leq n,l \leq N-1

where M and N is the number of samples in the x and y direction (or, for our particular problem, the dimensions of the image).

While it may seem interesting to find mutual recursion here, what my adviser told me to note is the constant at the beginning of the equations, \frac{1}{\sqrt{MN}}. According to him, depending on the implementation of the FFT we are using (remember what I told you above that Fast Fourier Transform¬†is just a blanket term for a family of algorithms), the constant varies to either¬†\frac{1}{\sqrt{MN}} or \frac{1}{MN}. It’s now just a matter of scaling the samples (the pixel values) by the appropriate constant to get the desired results.

The tutorial I linked to presents the following sample signal to demonstrate the FFT:

Sample Signal

which should evaluate to the following real and imaginary component respectively

FFT real

FFT imaginary

The following code listing directly translates the above example to Octave code:

x_real = zeros(8, 8);
x_real(2,3) = 70;
x_real(2,4) = 80;
x_real(2,5) = 90;
x_real(3,3) = 90;
x_real(3,4) = 100;
x_real(3,5) = 110;
x_real(4,3) = 110;
x_real(4,4) = 120;
x_real(4,5) = 130;
x_real(5,3) = 130;
x_real(5,4) = 140;
x_real(5,5) = 150
x_fft = fft2(x_real);
x_r = real(x_fft)
x_i = imag(x_fft)

Which results to the following output:

x_real =
 
     0     0     0     0     0     0     0     0
     0     0    70    80    90     0     0     0
     0     0    90   100   110     0     0     0
     0     0   110   120   130     0     0     0
     0     0   130   140   150     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
 
x_r =
 
   1.3200e+03  -7.9113e+02   8.0000e+01  -1.6887e+02   4.4000e+02  -1.6887e+02   8.0000e+01  -7.9113e+02
  -5.0485e+02  -9.0711e+01   2.2142e+02   1.0586e+02  -1.6828e+02   1.2721e+01  -2.6142e+02   6.8527e+02
   1.2000e+02   0.0000e+00  -4.0000e+01  -2.3431e+01   4.0000e+01   0.0000e+00   4.0000e+01  -1.3657e+02
  -3.3515e+02   1.3414e+02   2.1421e+01   5.0711e+01  -1.1172e+02   3.4731e+01  -6.1421e+01   2.6728e+02
   1.2000e+02  -6.8284e+01   0.0000e+00  -1.1716e+01   4.0000e+01  -1.1716e+01   0.0000e+00  -6.8284e+01
  -3.3515e+02   2.6728e+02  -6.1421e+01   3.4731e+01  -1.1172e+02   5.0711e+01   2.1421e+01   1.3414e+02
   1.2000e+02  -1.3657e+02   4.0000e+01   0.0000e+00   4.0000e+01  -2.3431e+01  -4.0000e+01   0.0000e+00
  -5.0485e+02   6.8527e+02  -2.6142e+02   1.2721e+01  -1.6828e+02   1.0586e+02   2.2142e+02  -9.0711e+01
 
x_i =
 
     0.00000  -711.12698   440.00000    88.87302     0.00000   -88.87302  -440.00000   711.12698
  -724.26407   713.55339  -216.56854    55.56349  -241.42136   134.14214   120.00000   158.99495
   120.00000  -136.56854    40.00000     0.00000    40.00000   -23.43146   -40.00000     0.00000
  -124.26407   255.56349  -120.00000    -6.44661   -41.42136    38.99495   103.43146  -105.85786
     0.00000   -68.28427    40.00000    11.71573     0.00000   -11.71573   -40.00000    68.28427
   124.26407   105.85786  -103.43146   -38.99495    41.42136     6.44661   120.00000  -255.56349
  -120.00000    -0.00000    40.00000    23.43146   -40.00000    -0.00000   -40.00000   136.56854
   724.26407  -158.99495  -120.00000  -134.14214   241.42136   -55.56349   216.56854  -713.55339

As evident, the results are very far from what our source says. However, dividing the sample (matrix x_r) by 8 (cf sample size) produces the results as given by our source.

Add the following line before calling fft2

x_real /= 8;

And we get,

 
x_r =
 
   165.00000   -98.89087    10.00000   -21.10913    55.00000   -21.10913    10.00000   -98.89087
   -63.10660   -11.33883    27.67767    13.23223   -21.03553     1.59010   -32.67767    85.65864
    15.00000     0.00000    -5.00000    -2.92893     5.00000     0.00000     5.00000   -17.07107
   -41.89340    16.76777     2.67767     6.33883   -13.96447     4.34136    -7.67767    33.40990
    15.00000    -8.53553     0.00000    -1.46447     5.00000    -1.46447     0.00000    -8.53553
   -41.89340    33.40990    -7.67767     4.34136   -13.96447     6.33883     2.67767    16.76777
    15.00000   -17.07107     5.00000     0.00000     5.00000    -2.92893    -5.00000     0.00000
   -63.10660    85.65864   -32.67767     1.59010   -21.03553    13.23223    27.67767   -11.33883
 
x_i =
 
    0.00000  -88.89087   55.00000   11.10913    0.00000  -11.10913  -55.00000   88.89087
  -90.53301   89.19417  -27.07107    6.94544  -30.17767   16.76777   15.00000   19.87437
   15.00000  -17.07107    5.00000    0.00000    5.00000   -2.92893   -5.00000    0.00000
  -15.53301   31.94544  -15.00000   -0.80583   -5.17767    4.87437   12.92893  -13.23223
    0.00000   -8.53553    5.00000    1.46447    0.00000   -1.46447   -5.00000    8.53553
   15.53301   13.23223  -12.92893   -4.87437    5.17767    0.80583   15.00000  -31.94544
  -15.00000   -0.00000    5.00000    2.92893   -5.00000   -0.00000   -5.00000   17.07107
   90.53301  -19.87437  -15.00000  -16.76777   30.17767   -6.94544   27.07107  -89.19417

Which, at last, agrees with our source.

The Blooper (or, the actual and embarassing reason why JTransforms FFT is not coinciding with Octave FFT)

In my first post about rgb2gray, I mentioned that I was taking the floor of the average of the RGB components of a pixel (or, in Java code, just perform integer division as the resulting precision loss is tantamount to floor). Big mistake. Octave does not merely floor values. It rounds off values.

In code, so there be no misunderstandings,

public static int[][] rgb2gray(BufferedImage bi) {
  int heightLimit = bi.getHeight();
  int widthLimit = bi.getWidth();
  int[][] converted = new int[heightLimit][widthLimit];
 
  for (int height = 0; height < heightLimit; height++) {
    for (int width = 0; width < widthLimit; width++) {
      Color c = new Color(bi.getRGB(width, height) & 0x00ffffff);
      float rgbSum = c.getRed() + c.getGreen() + c.getBlue();
      float ave = (rgbSum / 3f);
      float diff = ave % 1f;
      int iave = diff < 0.5f ? (int) ave : (int) (ave + 1);
      converted[height][width] = iave;
    }
  }
 
  return converted;
}

The moral of this long story? If two supposedly-similar functions are returning different outputs, check that the inputs are exactly the same before jumping to any wild conclusions.

  1. I’d like to note here that, according to the help file, Octave’s FFT is based on FFTW []