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 20218 days, 0 hours, 11 minutes ago.