JJinuxLand

I was thinking about the Travelling Salesman problem this morning. I came up with an algorithm that permits a few nice optimizations. My guess is that Knuth probably already came up with this algorithm, formally analyzed it, and then came up with 15 others that were much better. Nonetheless, I figured I'd jot it down.

Warning: This is a rough draft of an algorithm. You shouldn't bother reading this if you want real rigor. I'm just writing it down to get it off my chest.

Rather than picking the first segment of the journey and working my way to the end, I want to pick a middle segment of the journey and work my way outwards recursively.

Given a list of distances (or times, or costs, or whatever) between cities, sort the list from shortest distance to longest distance regardless of which cities are involved. Now, loop over this list and use each element of the list as a middle segment of your journey. This gives us a list of "first steps" (or rather, first midd…

I was thinking this morning about factoring numbers. I wonder if it might sometimes be helpful to use real numbers to gain an interesting perspective in order to solve certain problems involving integer numbers (i.e. number theory problems). For instance, I was thinking about factoring large numbers.

For every natural number, C, (that isn't equal to 0 or 1), there are an infinite number of pairs of positive, real numbers A and B for which A * B = C. For instance, 6 = 1.0 * 6.0 = 2.4 * 2.5 = 2.0 * 3.0 = ... I wonder if playing around with pairs of real numbers like (2.4, 2.5) can lead you to pairs of integer numbers like (2, 3).

Imagine all the pairs (A, B) for which A * B = C. Let's create a way to graph all such pairs in a funny sort of way. Let's pick a bunch of A's going from 0 to C. For each different A, we can calculate B via C / A. Let's consider the parts of A and B that are to the right of the decimal point to see if one pair, (A, B) can lead us to an…

First of all, let me apologize for my sloppy terminology. I've always been a better software engineer than a computer scientist.

This is how Wikipedia describes NP-complete problems:In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial-time, and also in the set of NP-hard problems so that any NP problem can be converted into L by a transformation of the inputs in polynomial-time.
Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem gr…

For my first Dart program, I decided to implement Tetris. I was inspired by Alexei Kourbatov at javascripter.net which contains an implementation of Tetris he wrote way back in 1999!

You can play my version here. The source code is here.

Overall, I like Dart. The Dart version of my code is about the same length as the JavaScript version of my code (the Dart version is slightly longer because I switched from using innerHTML to using the DOM). The combination of the optional static typing and Dart Editor helped me avoid many, many bugs. I'm still a Python guy at heart, but my experience with Dart was a very pleasant one.

I jotted down some lessons I learned. Warning: This is my first Dart program, and I haven't even read the tutorial yet, so I could be missing the boat on some of these points!

Don't try to play with DOM elements before the DOM is loaded. The easiest way to achieve this is to import your Dart-compiled JavaScript at the bottom of the page.

Dart has gene…

I can't figure out whether I should use Eclipse or IntelliJ.

Eclipse is good in that it's open source and free. Furthermore, Google has released several plugins for it such as the ADT (Android Developer Tools) plugin and the Google Plugin for Eclipse. However, Eclipse generally leaves me feeling confused, overwhelmed, and out of control. I spent two days reading a bunch of tutorials, but I still feel like I can't do what I want. I installed Aptana Studio 3 (which includes PyDev) in order to play around with my Python Google App Engine project. However, I couldn't figure out how to do two things: 1) update the PYTHONPATH for my project to include a few project-specific directories 2) use two space indents in Python code just for this project (which is the standard at Google).

On the other hand, there's IntelliJ. I've never used IntelliJ for Java development, but I've used PyCharm and RubyMine for Python and Ruby development. The downside is that it'…