Mandelbrot Set

Click on a position on the image panel, then click the Zoom In button

This will not work in Safari

Sudoku Applet

The above applet will not work in Safari. Never going to use JApplet to host a Swing application again...

Scala Code Snippet for Project Euler

Problem 1

// problem 1
  var one = (3 until 1000 by 3 sum) + (5 until 1000 by 5 sum) - (15 until 1000 by 15 sum)
  // or better yet
  var two = (3 until 1000 filter (x => x % 3 == 0 || x % 5 == 0) sum)

Problem 2

  val limit = 4000000
  val fibs: Stream[Int] = 1 #:: fibs.scanLeft(1)(_ + _)
  val result = fibs takeWhile(_ <= limit) filter(_ % 2 == 0) sum

Problem 4

  var maxPalindrom = (for (
    i <- (100 until 999 reverse);
    j <- (100 until 999 reverse) if (i * j).toString() == (i * j).toString().reverse
  ) yield (i * j)) max

Problem 5

  val l = 20
  val d = 2 to l 
  var result = l 
  while(d.takeWhile(result % _ == 0).length != d.length) {
    result += l
  }   
  println(result)

Problem 6

  val sosq = 1 to limit map(x => x * x) sum  
  val temp = 1 to limit sum
  val sqos = temp * temp
  val result = sqos - sosq  
  println(result)

Maybe next time I should start with problem 377 and work my way down...

Fun with Scala Parallel Collection

The above image is the output of the following scala program

import java.awt.image.BufferedImage
import java.awt.Color
import java.awt.Dimension
import java.awt.Graphics2D

import scala.swing.MainFrame
import scala.swing.Panel
import scala.swing.SimpleSwingApplication

object Mandelbrot extends SimpleSwingApplication {
  val ER = 4.0 // escape radius
  val maxIter = 50000 // max iteration
  val N = 1000 // image dimension

  def top = new MainFrame {
    title = "Mandelbrot Set"

    contents = new Panel {
      override protected def paintComponent(g: Graphics2D) = {
        super.paintComponent(g)
        var start = System.currentTimeMillis()
        g setColor Color.BLACK
        var image = new BufferedImage(N, N, BufferedImage.TYPE_INT_RGB)
        var m = new Mandelbrot(N, ER, maxIter, 1)
        for {
          i <- 0 until N
          j <- 0 until N
        } image.setRGB(i, j, m.pms(i * N + j))
        g.drawImage(image, 0, 0, null)
        println(System.currentTimeMillis() - start)
      }
    }

    size = new Dimension(N, N)
  }
}

class Mandelbrot(n: Int, er: Double, maxIter: Int, zoom: Int) {

  val pms = (0 to n * n).map { (x => computeColor(x / n, x % n)) } // work gets done here

  def computeColor(x: Int, y: Int): Int = {

    var (i, zx, zy) = (0, 0.0, 0.0)
    val cx = -2.5 + x * (er / n) / zoom
    val cy = 2 - y * (er / n) / zoom

    while (zx * zx + zy * zy < er && i < maxIter) {
      val temp = zx * zx - zy * zy + cx
      zy = 2 * zx * zy + cy;
      zx = temp;
      i = i + 1;
    }

    if (i == maxIter)
      Color.BLACK.getRGB()
    else
      (Color.getHSBColor(i / 20.0F, 1F, 1F)).getRGB()
  }
}

It took over 22.811 second to generate 1000 by 1000 fractal image, the max iteration is set at 50000 per pixel. This is without parallelization. So let's introduce parallel processing to the program with one line of change. Made the following change to line 40 to the above code.

// Before
val pms = (0 to n * n).map { (x => computeColor(x / n, x % n)) } // work gets done here

// After
val pms = (0 to n * n).par.map { (x => computeColor(x / n, x % n)) } // work gets done here

// notice the extra method call par after the list

The new fractal image took only 3.771 second to generate, over 6 fold increase.

Notice that all 8 cores of my i7-2600K CPU is pulling its weight. A simple method call par after a collection gives you the power of parallelism, try that in Java. Here’s a video of Aleksandar Prokopec explaining parallel collections at Scala Days 2010

Fourth floor challenge

Couple days ago, a friend sent me this link, which has an interesting problem.

In short, there is a vending machine that tries to dispense the fewest coins necessary to meet the change. The algorithm is to always dispensing the largest denomination coin that was equal or less than the remaining change first, and then repeating the process on the remaining change amount.

The algorithm would fail if the coins are denominated in 1, 4, 5, and 9 cents. For example, to return 8 cents the machine will return 5, 1, 1, 1; but 4, 4 would be fewer coins.

So the question is from 0 to 1000 cents, how many cases would the vending machine return more coins than necessary.

First list all the cases from 1 to 25:
1 => 1
2 => 1 1
3 => 1 1 1
4 => 4
5 => 5
6 => 5 1
7 => 5 1 1
8 => 5 1 1 1 (fails, more coins than necessary)
9 => 9
10 => 9 1
11 => 9 1 1
12 => 9 1 1 1 (fails again, 4, 4, 4 is better)
13 => 9 4
14 => 9 5
15 => 9 5 1
16 => 9 5 1 1
17 => 9 5 1 1 1 (9, 4, 4 is better)
18 => 9 9
19 => 9 9 1
20 => 9 9 1 1
21 => 9 9 1 1 1 (9, 4, 4, 4 is better)
22 => 9 9 4
23 => 9 9 5
24 => 9 9 5 1
25 => 9 9 5 1 1

It is not hard to see that the failed cases either ends with 5 1 1 1 (case 8 and 17) or 1 1 1 (case 12 and 21), and they all preceded by 9, not counting the first 1 1 1 case. This can be solved with one line of Scala code.

// Scala interpreter
// So start with case 4, all the way up to case 1000
// Count any case that has either 8 or 3 as remainder when divided by 9
scala> 4 to 1000 count {x => (x % 9 == 8) || (x % 9 == 3)}