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?

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.

Jython, It ain't no JRuby

All of my recent excursions into Python convinced me it was time to try out Jython. I have had a great experiences with JRuby. It is definitely faster than CRuby for long running processes (obviously slower for short scripts, because of the JVM startup overhead.) In my experiences, which range from doing mathematical algorithms to web applications using Rails, there is extremely good interoperability. I have had no code blow up in JRuby that ran fine in CRuby. Even IDE support has been on par. So my expectations were high for Jython.

Maybe that was the first problem, unrealistic expectations. Let's not jump into the shortcomings, just yet. First off, Jython installation is nice. Well nice as in "there is a gui." The installer only seemed to copy files into the installation directory, nothing more. That is fine, but makes me wonder I bothered with an installer at all. I at least expected into put the jython executable on my path, but it did not. No big deal.

Running a script is painless. It was odd to see a lot of activity the first time I ran a script, but the messaging (or should I say logging) was good enough to give me a good idea about what was going on and it only happens once. It also seemed like Jython was going out of its way to help performance, and JRuby had caused me to expect a nice performance boost from Jython.

So I tried out a script I wrote to solve a Project Euler problem, in particular Problem #43. The performance on Python is not that great, as it takes about 58 seconds to solve on my Macbook. Here is the code. It has been slightly optimized by Gilly.

def combinations(items, n):
    if n == 0:
        yield []
    else:
        i = 0
        l = len(items)
        while i < l:
            for combo in combinations(items[:i] + items[i+1:], n-1):
                yield [items[i]] + combo
            i += 1
 
def permutations(items):
    return combinations(items, len(items))

def to_int(seq):
    return reduce(lambda x,y: 10*x + y, seq, 0)
 
def main():
    primes = [2, 3, 5, 7, 11, 13, 17] 
    digits = range(0, 10)
    sum = 0
    for p in permutations(digits):
        if p[5] == 5 and p[0] != 0:
            j = 0
            trait = True
            while trait:
                if j == 7:
                    y = to_int(p)
                    sum += y 
                    print y
                    break
                x = 100*p[j+1] + 10*p[j+2] + p[j+3]
                trait = not x % primes[j]
                j += 1
    print "sum = " + str(sum)
 
if __name__ == '__main__':
    main()

Lots of brute force, with a little bit of clever use of Python features. I was ready to crank this up with Jython, but when I tried to run it, I got this error message:

Traceback (innermost last):
(no code object) at line 0
File "euler43.py", line 5
yield []
^
SyntaxError: invalid syntax

Ouch. This actually made me feel stupid. I should have noticed that the current version of Jython is numbered 2.2.1 and that this obviously corresponds to Python 2.2.1 (that is obvious, right?) I had used a Python feature that did not exist in 2.2.1. Luckily there is an alpha version of Jython that is numbered 2.5. What about 2.3 or 2.4, you say? Uhh...

Anyways, with the alpha version of Jython 2.5 used instead everything worked. However, the performance was not what I expected. The same script ran in 171 seconds! It took three times longer than CPython. Wow.

I wrote a similar algorithm in Ruby and it was horribly slow. Perhaps this is why JRuby is faster than CRuby, CRuby is just so slow. Perhaps not. The nice thing about this is that it forced me to optimize the code more. Here is the optimized Ruby code.

def calc(seq)
  seq.inject(0) {|x,y| x = 10*x + y}
end
 
def test(seq)
  primes = [2,3,5,7,11,13,17]
  j = 1
  trait = true
  while j < 8 && trait
    num = calc(seq[j,3])
    trait = (num % primes[j-1] == 0)
    j += 1
  end
  trait
end

sum = 0
digits = (0..4).to_a + (6..9).to_a
for p in digits.permutation
  if p[0] != 0
    x = p[0,5] + [5] + p[5,4]
    trait = test(x)
    if trait
      y = calc(x)
      sum += y
      puts "found one " + y.to_s
    end
  end
end
print "sum= " + sum.to_s

A couple of things to note. This uses Array#permutation, a new feature of Ruby 1.8.7. This is written in C, so you would think it would be super fast. You would be wrong. The latest JRuby is 1.1.3 and does not implement all of the 1.8.7 features, including Array#permutation. So this code will not run in JRuby. It winds up being much faster than the Python code, but only because the algorithm is so much better. It only deals with 9! numbers instead of 10!. Without the modification, Ruby was so slow that I did not have the patience to let it finsh. We're talking 10+ minutes for something that only took 1 minute in Python. With the improved algorithm it took about 40s to solve the problem in Ruby. When I ported the change over to Python, it dropped Python down to around 9s. When I tried the ported code in Jython, it would not run at all... I haven't tracked down that problem yet.

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.