Project Euler 18

euler18.scala

object Main extends App {
	val triangle = Array(
				Array(75),
				Array(95, 64),
				Array(17, 47, 82),
				Array(18, 35, 87, 10),
				Array(20,  4, 82, 47, 65),
				Array(19,  1, 23, 75,  3, 34),
				Array(88,  2, 77, 73,  7, 63, 67),
				Array(99, 65,  4, 28,  6, 16, 70, 92),
				Array(41, 41, 26, 56, 83, 40, 80, 70, 33),
				Array(41, 48, 72, 33, 47, 32, 37, 16, 94, 29),
				Array(53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14),
				Array(70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57),
				Array(91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48),
				Array(63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31),
				Array( 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23)
			)
			
	def toBitSet(n: Int, size: Int): Array[Int] = {
		var (a, idx) = (n, 0)
		val bits = new Array[Int](14)
		
		while (a > 0) {
			if (a % 2 != 0) bits(idx) += 1
			else bits(idx) += 0
			a = a >> 1
			idx += 1
		}
		
		bits
	}
	
	def getPath(bits: Array[Int]): Array[Int] = {
		val path = new Array[Int](15)
		path(0) = triangle(0)(0)
		var (i, idx) = (0, 1)

		while (idx < 15) {
			val bit = bits(idx-1)
			if (bit == 1) i += 1
			path(idx) = triangle(idx)(i)
			idx += 1
		}
		
		path
	}
	
	println((0 until 16384).map(i => toBitSet(i, 14)).map(getPath).map(_.sum).max)
}