Two Guys Arguing


Posted in questions by youngnh on 01.06.11
  1. What are you currently hacking on?

    Just before Christmas, I put together a small LL(1) parser-generator in Clojure. LL(1) has the distinction of being one of the simplest classes of grammars to parse, and a great number of textbooks on the subject will tell you that it’s often quicker to write a parser by hand for a LL(1) grammar than to go to the trouble of using a parser-generator. I think my code removes most of those objections. However, it currently suffers from 4 problems that I vowed I would remedy before it saw the light of day: its very slow for only marginally deep parse trees, it has no tests, no documentation, and the error messages it spews forth are currently only meaningful to myself. None of these problems are sexy, nor could the process of solving them be construed as “hacking”, so my motivation to finish the project has plummeted.

  2. What do you want to hack on more in 2011?

    I have no shortage of ideas that could be expressed via computational algorithms, but recently I’ve had a harder and harder time convincing myself that any of them are significant in any way other than the challenge in realizing them. This year I’d like to stay away from the “because it’s there” projects. I’d like to hack on things that:

    • someone would pay money for: a fart app, for example, or possibly one that does facial recognition so that if you think you’ve seen somebody famous on the street or simply can’t remember the name of the person you’re currently talking to, you can pull out your phone and shove its tiny camera in their face
    • something that people I’ve never met before would find useful: most of my keystrokes are deleted, a select few are saved to files, fewer still find themselves a part of a working project, and of those projects that people other than myself get their hands on, their purpose could generously be described as niche. I write software largely for the compulsive pleasure of seeing an ephemeral thought produce flashing pixels on a screen, but I’d like to try writing something that might be useful to others at the same time.
    • change an old way of doing things: Starbucks changed the way you order drinks, parenting at dinner is a contentious process, and the airline industry has been sticking with a sub-optimal solution to one of the hardest problems in all of computation but that doesn’t mean a few guys didn’t throw a bunch of servers at the problem and give it a go of their own (and crashed and burned). These are hacks in the best sense of the word.
    • change how non-programmers interact with computers: it pains me to watch people use software. You might already be rolling your eyes in preparation for a rant from a programmer about non-technical people’s poor computer skills, but that’s not it. What I see when my mother-in-law or grandfather use their computers is the incredibly resourceful, thoughtful and clever way in which they approach an inanimate, ineffable and often arbitrary hunk of plastic and silicon, and manage to make it do unbelievably complex things. I’ve read the manuals, I spent four years in college and all of my professional career learning how these things are put together and I can barely get my wireless printer to work. The only difference between us is that I have the ability to change the machine to match their understanding of it. Helping non-programmers is my peace corps, my doctors without borders.
  3. What do you want to stop hacking on in 2011?

    I think what I wrote above covered most of what I’d like to hack on, and being a very good dichotomist, I’d like to stop hacking on anything that isn’t a Big Idea. This is not to confuse Big Ideas with small hacks. Big projects never get finished. Short sprints of interesting and valuable concepts are strongly encouraged, not the least for morale. Anything that someone might ask “Why that?” of, and that I would respond with “well, because it just seemed neat…” should be viewed with strong suspicion in 2011.

  4. Big idea that just needs a free weekend to come to life?

    As you wrote big idea with a little “i”, and I’ve just finished pontificating on big “I” ideas, I’m going to say a Java compiler that does type inference. I haven’t done my homework and checked if something like this already exists, so if it does, please point me in its direction. Aside from the massive amount of typing (lol) it’d save, why should Scala get to have all the fun? A slightly more powerful compiler might lead to a better, if sloppier, place for the Java masses.

  5. How can we get more arguing on this blog?

    We could go find that youtube video of two kids having an argument and put it up here, thereby reclaiming the rest of the hits from Google searches for “two guys arguing”.

    If you’d like something software-related, pick the “social sciences” of programming, like methodologies, or productivity enhancements or what editor to use, as they often don’t have verifiable outcomes and thus can generate argument indefinitely.

    Personally, I’ve found that being wrong about a thing leads to more comments and discussion than solving that thing competently. On a positive note, I’d like to think that it has been our extreme competence in what we do that has kept this blog from rocketing us into the stratosphere of computer scientists around the world.

A Solution from Purgatory (for the Matrix from Hell)

Posted in challenge, math, questions by benjaminplee on 01.02.11

This post attempts to recount some of my thought process which eventually (more than a year later) lead to the Matrix from Hell puzzle I posted about a few days ago.  If you don’t want to know my answer, don’t read the rest of this post.  My final solution is at the bottom.

You have been warned.




Below is a list of my general thought process and the main ideas/revelations/halucinations that I know helped me to my solution.  An annotated matrix is at the bottom with some of the ideas highlighted in different colors.

  • Should indices start at 0 or 1?
  • Values along either axis count up by 1 in both directions when the other =0
  • Values are duplicated over the f(x)=y axis –> Order of indices given to function is inmaterial since they can be swapped
    [The RED 5 can be seen duplicated over the diagonal]
  • Calculation of max/min index is O(1) so stop worry about it and “forget” the bottom half of the matrix (assume X>= Y)
  • Values generally increase as they go right/down but not always
  • f(x,x)=0, f(x,0)=x
  • Values are symmetrical perpendicular to f(x)=y IFF the bounding square in question is a power of 2
  • “Quad” patterns can be seen repeating for every power of 2.  In each “Quad” the top left quadrant is the same as the bottom right and the top right is the same as the bottom left.
    [Each “Quad” of the example matrix is outlined in BLUE with the quadrants in LIGHT BLUE. PINK shows the repetition]
  • power of 2 repeating nature of the values leads to thinking of binary trees
  • binary trees leads to thinking about a possible solution which could run in O(log2 n) time:
    • In a nut shell, for a given (X,Y), algorithm would find smallest boudning power of 2 including X and would walk back “Quad”s by each successivly smaller power of 2 “Quad” until the last one is met.  For each “Quad” determine which quadrant the value lives in and remap to root values.
    • Debate if this would really work for large numbers and if it could be reduced to constant time function by math that I have forgotton from college/HS
    • Dismiss b/c I can’t remember a way and base idea is > O(1)
  • Binary trace back algorithm idea makes me realize that it can be also looked at as the “binary” representation of a number (e.g. 01011011010) where each 1 represents a “Quad” where the value was in the upper right or bottom left and vica-verca.
    [Following the matrix value at (5,6) can be seen ORANGE.  The value 3 is in the bottom right  of the 1st “Quad”, then BL, & TR. {BR BL TR} => {101} => {3}]
  • Remembered that f(x,y)=0 IFF x==y …. which means that difference between X and Y is important to value of f()
  • Eureka!
    • F(X, Y) = X xor Y
    • solution typed above in white on white to protect the innocent. highlight to view.

sample matrix with some of my thought process drawn out

That is it.  I never said it was pretty or made any sense.

Tagged with: , , , ,


Posted in questions by benjaminplee on 01.01.11

In the spirit of the first posts to this blog and the new year I poste the following 5 questions to Mr Young…

  1. What are you currently hacking on?

  2. What do you want to hack on more in 2011?

  3. What do you want to stop hacking on in 2011?

  4. Big idea that just needs a free weekend to come to life?

  5. How can we get more arguing on this blog?

Tagged with: ,