JavaFX: Some Frustrations...

Yesterday was the much ballyhooed release of JavaFX. I was excited about this for a few reasons. First, I started following JavaFX back when it was called F3. I remember last year planning on attending Chris Oliver's session at JavaOne on F3, when I read on his blog that F3 was now being called JavaFX. Second, a big part of my job is staying on top of RIA technologies and JavaFX certainly falls in that category. Lastly, it's a new programing language that runs on the JVM! How could I not want to learn it.

So I started playing around with JavaFX. Instead of going after lots of graphical goodness, I went for more mathematical stuff. I did a few problems with JavaFX, and then came across a problem that required finding the prime factors of a large integer. JavaFX has an Integer type that maps to java.lang.Integer. There is nothing in JavaFX specifically for large integers, but part of the beauty of JavaFX is that you can use classes from Java in it. In particular you can use java.math.BigInteger. So far so good.

In my solution, I wrote a prime sieve and then checked the modulus of the primes against the large integer. Now for normal 32-bit Integers, JavaFX has some nice syntax:

var remainder = n mod p;

It looks like math! Of course I love this. However, this does not work for BigIntegers. No problem, BigInteger has its own method for this:

var remainder = n.mod(p);

But this does not compile! Why? As you can infer from the first example, mod is a reserved word in JavaFX, so you can't use it as an identifier. Thus you can't use it as a method name. Of course you could surely use reflection to get around this, but who wants to do that?

Facebook Puzzler in Scala

An associate of mine pointed out some fun programming puzzles on Facebook. This one was interesting to me. It was interesting because I think it is poorly. Well at the very least it confused on first read. When specifying the cost/weight, if they would have just used the word 'each' in there it would have been far less confusing... Anyways, I decided to solve the problem in Scala, since I've been doing a lot more Scala programming lately. Here is my Solver:

object Solver {
    def cache = new scala.collection.mutable.HashMap[(List[Int], Int), List[List[Int]]]()

    /**
     * Generates a list of solutions to the Diophantine inequality
     * w1*x1 + w2*x2 +... wN*xN >= max
     * where weights = (w1,w2,...wN)
     * Each solution is a minimal solution.
     * This means that if (x1,x2,...xN) is a solution
     * then (x1,x2, ... ,-1 + xM , ... xN) is NOT a solution
     */
    def solve(weights: List[Int], max: Int): List[List[Int]] = {
        if (cache.contains((weights,max))){
          return cache((weights,max))
        }
        if (weights.length == 1) {
            return List(List(max / weights(0) + 1))
        }
        var all: List[List[Int]] = Nil
        var a = 0
        while (a * weights(0) < max) {
            all = all ++ solve(weights.drop(1).toList, max - a * weights(0)).map(a :: _)
            a += 1
        }
        val solution = (a :: weights.drop(1).map(_ * 0)) :: all
        cache.put((weights,max), solution)
        solution
    }

    /**
     * For a given set of weights (w1, w2, ... wN) and costs (c1, c2, ... cN)
     * This finds the solution (x1,x2,...xN) to the inequality
     * w1*x1 + w2*x2 + ... wN*xN <= max that minimizes the total cost
     * c1*x1 + c2*x2 + ... cN*xN
     * It returns the solutions as a Tuple where the first element is
     * the solution (x1,x2,...xN) and the second is the minimal total cost
     */
    def optimizer(costs: List[Int], weights: List[Int], max: Int): (List[Int], Int) = {
        val solutions = solve(weights, max)
        var answer: List[Int] = Nil
        var best = (answer, Integer.MAX_VALUE)
        solutions.foreach((solution) => {
            val cost = solution.zip(costs).foldLeft(0){(a,b) => a + b._1*b._2}
            if (cost < best._2) {
                best = (solution, cost)
            }      
        })
        best
    }
}

I put in the cache for memoization purposes, but it doesn't always help. For example, with their sample input/output, the cache is useless. Anyways, I showed the problem to other smarter folks who immediately pointed out that this was a variant of the unbounded knapsack problem and that my solution uses dynamic programming.

Here's a dirty little secret about yours truly. I studied mathematics in college, not computer science. So it's always amusing for me to come across a problem like this and have people start talking about CS terms. Personally I looked it as a Diophantine equation (inequality to be more accurate.) Of course maybe if I was a CS person, then I would have written a nicer solution.

Scala ArrayStack

I had not done any Project Euler problems for awhile, so I decided to solve one yesterday. I was also planning on attending the next BASE meeting, so I wanted to brush up my Scala. Thus it was time to solve Problem #47 in Scala.

The solution got me a little more familiar with some of the data structures available in scala.collection.mutable. In particular I needed a structure to hold a list of factors. I decided that ArrayStack was the best choice. Here is my solution:

package probs
import scala.collection.mutable.ArrayStack

object Euler47 {
  def main(args : Array[String]) : Unit = {
    val start = System.nanoTime
    solve(4)
    val duration = System.nanoTime - start
    println("duration=" + duration/1000000.0)
  }

  def solve(n:Int):Unit = {
    var i = 2
    while (i > 0){
      var j = i
      while (j<i+n && numFactors(j) ==n){
        j += 1
      }
      if (j-i == n){
        val msg = (i until j).foldLeft(""){(x,y) => x + y + " "}
        println(msg)
        return
      }
      i += 1
    }
  }
  
  def numFactors(n:Int):Int = {
    var factors = new ArrayStack[Int]
    var i=2
    var m = n
    while (i <= m/i){
      while (m % i ==0){
        if (factors.size ==0  || i != factors.peek){
          factors += i
        }  
        m /= i
      }
      i += 1
    }
    if (m != 1){
      factors += m
    }
    factors.size
  }
}

I was very pleased with the performance, solving the problem in about 0.4 seconds on my MacBook. I saw a similar, but not as good Java solution on the message boards that ran in 1.5 seconds. That solution added all of the factors repeated times and then had to loop through them again to get rid of duplicates. I ran it on my MacBook and it ran in 1.1 seconds. Even when I "fixed" it, it still took about one second. I am sure I could have done a lot of work to it and got it as fast as Scala, but why bother.

Diophantine Equation

Earlier today I solved Problem 31 on Project Euler. The problem is to find the number of ways of making change for 2 British pounds (or 200 pence) given 8 types of coins. For a mathematical person like myself, the problem reduces to a Diophantine Equation:

a + 2b + 5c + 10d + 20e + 50f + 100g + 200h = 200

Where 1,2,5,10,20,50,100,200 are the values of the various types of coins. I had some meetings to go to, so I wrote a brute force solution (in Ruby) and let it run. I got back an hour later, and it was still running. I felt quite stupid. I then came up with a much better solution using some dynamic programming and recursion. It ran in 0.23s. Here it is:

def solve(n,coefficients)
  x = coefficients.pop
  if (coefficients.length == 0)
    if (n % x == 0)
      return 1
    else
      return 0
    end
  else
    d = (n/x).to_i
    cnt = 0
    0.upto(d){|y|
      xc = coefficients.collect{|p| p} #must copy since we pop array
      cnt += solve(n-x*y,xc)
    }
    return cnt
  end
end
 
c = [1,2,5,10,20,50,100,200]
n = 200
puts solve(n,c)

Long Division

Earlier this week, I solved another problem from Project Euler. This was #26. Here is the description:

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2	=	0.5
1/3	=	0.(3)
1/4	=	0.25
1/5	=	0.2
1/6	=	0.1(6)
1/7	=	0.(142857)
1/8	=	0.125
1/9	=	0.(1)
1/10	=	0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/_d contains the longest recurring cycle in its decimal fraction part.

I knew this problem was related to the totient function, but I went a brute force route instead. The brute force route required writing a long division algorithm, which just seemed like a fun thing to do anyways. So I solved the problem, and the solution was plenty fast (0.185s for the calculation.)

I was ready to post my solution to the forums. I was also planning on reading the forums to see if anyone had a clever solution using the totient function. So I was greatly disappointed to see that the forms were down. Still my ego required me to publish my long division algorithm, so here it is:

def cycle(d)

 m,i = 1,1
 arr = Hash.new

 while m > 0
   while m < d
     m *= 10

     i += 1
   end
   m = m % d

   if arr[m]
     return i - arr[m]

   end
   arr[m] = i
 end
 return 0

end
 
max = 0
m = 2
3.upto(ARGV[0].to_i){|n|
 c = cycle(n)

 if c > max
   max = c
   m = n

 end
}
puts m

Obviously this is in Ruby. The cycle calculates the length of the recurring cycle. The m variable is essentially the digits in the decimal representation of 1/d. The algorithm doesn't capture it, since it is not needed for the problem, but you could easily capture it (append to a string or array or whatever) and return it for a true long division algorithm.

The Age Question

I've avoided joining the echo chamber on the question of age and entrepreneurs, but then Marc Andressen wrote something really interesting about it. One of the important "scientific" conclusions he sites is that in some disciplines (math, physics) people peak in their late 20's to early 30's, but in others (writing, history) they peak much later, in their 40's or even 50's. So then the question becomes are entrepreneurs more like mathematicians or historians?

Of course most people would say that entrepreneurs are more like mathematicians, so the younger the better. I will argue that entrepreneurs are nothing like mathematicians and physicists, but that does not mean that they are not more like those types than they are like historians and writers.

First some disclaimers. I have a degree in mathematics, and like to humor myself by considering myself a mathematician at my core. Truth is that I am a software engineer, a very different discipline, and I cannot deny this.

Ok, first off entrepreneurs are completely full of themselves for trying to enter this kind of comparison. By even making these analogies, you are equating the creativity and skill of scientists and scholars with the ... attributes ... of entrepreneurs. This is ridiculous. It is like trying to compare the skills of a microsurgeon with the skills of a race horse. It just doesn't make any sense.

Entrepreneurs definitely have creativity, intelligence, and skill, but it is not of the same species as scientists and scholars. Entrepreneurs have any measurement of their prowess: money. If their ideas make money, they are good ideas. If they do not make money, they are not good ideas. It's painfully simple.

Scientists and scholars are held to very different standards. Now it is true that scientific endeavor is open to experimentation and verification, a kind of litmus test similar to the success or failure of an entrepreneur's business. But a lot of the really great scientists have theories that are so theoretical and advanced that they cannot just be easily verified in a lab experiment. Similarly mathematicians must write proofs of their theories. These proofs must judged both objectively and subjectively by peers. Of course scholars have no "out" in terms of being proven right or wrong. Thus they all share something similar: their success is measured in the near term by the scrutiny of the most brilliant minds in the world.

This is a kind of scrutiny that no entrepreneur can experience. If the top two dozen computer scientists all thought that Google had a great search engine eight years ago, it would not have meant anything for Google. If those same elite scientists decided Google was crap, again it meant nothing.

The other flip side to the world of science and scholarship is that the very peers who decided your success or failure, are often wrong. That's why there are numerous examples of scientists whose work is not appreciated until after their death.

I could easily make arguments about how scientists and scholars have to be so much "smarter" than entrepreneurs, but I think just looking at the criteria for success is sufficient.

Again, given my background in mathematics, I have a little insight into why mathematicians peak in their late 20's or early 30's. The obvious reason is that solving highly theoretical problems requires tremendous time and submersion into you work. This is true, but it's only part of the reason. The other reason is that to solve those kind of problems, you need to have very little else to think about. I'm not talking about things outside of your work and study, I'm talking about things inside it.

As you progress in any field, you absorb more and more knowledge. This knowledge is tapped in some way, even if subconsciously, whenever you set out to solve a new problem. Knowing less, and thus have more focussed concentration on what you do know, is exactly the kind of thing needed to solve certain kinds of problems. Those kinds of problems are much more common in mathematics and physics than in history and literature.

So even if I humor the self-loving entrepreneurs out there and compare them to scientists and scholars, I cannot really say who they are more similar to. I do think that engineers play a significant role in the kind of technological endeavors common to entrepreneurs. As an engineer who was once a mathematician, I can say with confidence that engineers are much more like writers and historians than like mathematicians and physicists. Extra knowledge and experience definitely help an engineer to be more creative and productive. Computer scientists may be more like physicists. I wouldn't know, as I am an engineer, not a computer scientist.