9billionnames.frink

Download or view 9billionnames.frink in plain text format

/** Solution for "9 billion names of God the integer" task on RosettaCode:
    http://rosettacode.org/wiki/9_billion_names_of_God_the_integer */

class PartitionCount
{
   // Array of elements.  triangle@row@col is the number of partitions of row
   // have col as the largest element.  Conversely, it is ALSO the number of
   // partitions of row into exactly col parts.
   class var triangle = [[0],[0,1]]

   // Array of cumulative sums in each row.
   class var sumTriangle = [[1],[0,1]]

   class calcRowsTo[toRow] :=
   {
      for row = length[triangle] to toRow
      {
         triangle@row = workrow = new array[[row+1],0]
         sumTriangle@row = sumworkrow = new array[[row+1],0]
         oversum = 0
         for col = 1 to row
         {
            otherRow = row-col
            sum = sumTriangle@otherRow@min[col,otherRow]
            workrow@col = sum
            oversum = oversum + sum
            sumworkrow@col = oversum
         }
      }
   }

   class rowSum[row] :=
   {
      calcRowsTo[row]
      return sumTriangle@row@row
   }
}

PartitionCount.calcRowsTo[25]
for row=1 to 25
{
   for col=1 to row
      print[PartitionCount.triangle@row@col + " "]
   println[]
}

// Test against Frink's built-in much faster partitionCount function that uses
// Euler's pentagonal method for counting partitions.
testRow[row] :=
{
   sum = PartitionCount.rowSum[row]
   println["$row\t$sum\t" + (sum == partitionCount[row] ? "correct" : "incorrect")]
}

println[]
testRow[23]
testRow[123]
testRow[1234]
testRow[12345]



Download or view 9billionnames.frink in plain text format

This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 19966 days, 18 hours, 55 minutes ago.