# Golang implementation of Pascal's triangle

How can I improve my code and make it more idiomatic?

package pascal

func NextRow(prevRow []int) []int {
x := make([]int, len(prevRow)+1, len(prevRow)+1)
x[0], x[len(prevRow)] = 1, 1
for i := 0; i < len(prevRow)-1; i++ {
x[i+1] = prevRow[i] + prevRow[i+1]
}
return x
}

func Triangle(x int) [][]int {
y := [][]int{}
for i := 0; i < x; i++ {
if i == 0 {
y = append(y, []int{1})
} else {
y = append(y, NextRow(y[i-1]))
}
}
return y
}


It's interesting that you chose to put the code in its own package. I think it's great - but it does make the code a little more difficult to run as an experiment, or on ideone, or something. So, I encourage you to use packages, but remember that the main function/entry point will need to be in a different directory.

Now, as a package, there should be no reason to have an exported function NextRow. Why have you capitalized it? It should be nextRow.

Then, working through your functions, the next most striking thing is the poor choice of variable names. x's that are "lines", y's that are "triangles", etc. Worse, you use the variable x in two different ways in the two different functions. Renaming some variables made it easier to read.

Finally, the go fmt tool will re-format your code to conform to go conventions. You should always do this for your code. It helps when sharing go code with others.

With those changes, I would consider your code to be reasonably good.

On the other hand, I did mess a bit with the nextRow method to use append(..) instead of direct index assignment. I feel the append helps by making the 1 at the beginning and end of the line more obvious.

I also moved the special-case of the first row outside the loop of the Triangle method. This makes it clearer, I feel.

So, your major issues are code style, and naming. The actual code is otherwise OK. Some tweaks may help readability - but that's something you should decide whether it's better.

I put those changes together in a runnable format in ideone.

package main

import (
"fmt"
"strings"
)

func nextRow(prevRow []int) []int {
current := make([]int, 0, len(prevRow)+1)

current = append(current, 1)

for i := 1; i < len(prevRow); i++ {
current = append(current, prevRow[i-1]+prevRow[i])
}

current = append(current, 1)

return current
}

func Triangle(rows int) [][]int {
triangle := [][]int{}
if rows <= 0 {
return triangle
}
triangle = append(triangle, []int{1})
for i := 1; i < rows; i++ {
triangle = append(triangle, nextRow(triangle[i-1]))
}
return triangle
}

func present(line []int) string {
words := make([]string, len(line), len(line))
for i, v := range line {
words[i] = fmt.Sprintf("%4v ", v)
}
return strings.Join(words, " ")
}

func main() {
tri := Triangle(10)
for _, line := range tri {
fmt.Println(present(line))
}
}


Consider using unsigned integers to avoid checking for negative values for depth and to extend represented range of the values. More on int vs. uint type.

You can also take advantage of the symmetry of the Pascal triangle to improve performance for higher depth values.

package main

import "fmt"

// Triangle returns Pascal's triangle with the given depth.
func Triangle(depth uint16) [][]uint64 {
t := make([][]uint64, depth)
for d := 0; d < int(depth); d++ {
r := make([]uint64, d+1)
for c := d / 2; c >= 0; c-- {
v := uint64(1)
if c > 0 {
p := t[d-1]
v = p[c-1] + p[c]
}
r[c], r[d-c] = v, v
}
t[d] = r
}
return t
}

func main() {
for _, r := range Triangle(7) {
fmt.Println(r)
}
}


The most important property of a program is that it is correct. Reading program source code is essential for verifying a program's correctness. Reading program source code is the most frequent programming activity.

Reading your program source code, it seemed too complicated, so I simplified it. For example, removing special cases (row zero) and small inner functions of little value (NextRow).

Of course, some things come down to a matters of preference and style. For example, you used variable names x and y representing Cartesian axes, which didn't confuse me but confused others. I prefer to think of rows (r) and columns (c), but x and y are OK too.

For Pascal's triangle t with depth depth and rows r and columns c, here's what I consider to be a simpler, more idiomatic Go function which is easier to read and prove correct.

package main

import "fmt"

// Triangle returns Pascal's triangle with the given depth.
func Triangle(depth int) [][]int {
t := make([][]int, depth)
for r := 0; r < depth; r++ {
t[r] = make([]int, r+1)
left, right := 1, r-1
t[r][left-1], t[r][right+1] = 1, 1
for c := left; c <= right; c++ {
t[r][c] = t[r-1][c-1] + t[r-1][c]
}
}
return t
}

func main() {
for _, r := range Triangle(7) {
fmt.Println(r)
}
}


Output:

[1]
[1 1]
[1 2 1]
[1 3 3 1]
[1 4 6 4 1]
[1 5 10 10 5 1]
[1 6 15 20 15 6 1]


Program Development by Stepwise Refinement by Niklaus Wirth

The creative activity of programming - to be distinguished from coding - is usually taught by examples serving to exhibit certain techniques. It is here considered as a sequence of design decisions concerning the decomposition of tasks into subtasks and of data into data structures. The process of successive refinement of specifications is illustrated by a short but nontrivial example, from which a number of conclusions are drawn regarding the art and the instruction of programming.

The Pascal's triangle cell values are the number of combinations of n things taken k at a time: n!/(k!*(n-k)!).

The Go int data type is either 32 or 64 bits. Therefore, to postpone overflow, we should use the 64-bit Go integer type, int64, for cell values.

The combinatorial explosion of cell values overflows the int64 data type after 67 rows. The valid range for the rows parameter is 1 through 67 inclusive. For a larger number of rows, use the Go math/big package.

For idiomatic Go, we should write tests using the Go testing package. For Pascal's triangle cell values, use values from OEIS A007318.

OEIS: Pascal triangle

OEIS: A007318: Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0 <= k <= n.

For idiomatic Go, we should measure performance using the Go benchmark package.

Here are some benchmark results for 67 rows, listed in the order that the Triangle functions were posted. The suffixes 500, rolfl, and Gyongyeee are the authors of the benchmarked Triangle function. The suffix Correct is my first version, which focused on correctness. The suffix Optimize is my second version, which focused on optimization of the correct function.

BenchmarkTriangle500           20000         66694 ns/op          75 allocs/op     25000 B/op
BenchmarkTriangleRolfl         20000         73575 ns/op          75 allocs/op     25000 B/op
BenchmarkTriangleCorrect       20000         76297 ns/op          68 allocs/op     20536 B/op
BenchmarkTriangleGyongyeee     30000         55401 ns/op          68 allocs/op     20536 B/op
BenchmarkTriangleOptimize      50000         25090 ns/op           2 allocs/op     22144 B/op


The reduction in CPU time and memory allocations does have a cost. Optimization is usually time consuming and optimization often leads to complexity and obscurity. Also, the optimization may be irrelevant. The cell values are constant. We only need to compute them once, before first use.

Here's my optimized Triangle function.

package main

import "fmt"

const (
TriangleMinRows = 1
TriangleMaxRows = 67
)

// Triangle returns Pascal's triangle with the given rows.
func Triangle(rows int) [][]int64 {
if TriangleMinRows > rows || rows > TriangleMaxRows {
panic(fmt.Sprintf("Triangle: invalid rows: %d", rows))
}

t := make([][]int64, rows)
a := make([]int64, rows*(rows+1)/2)
lo, hi := 0, 1
for i := range t {
t[i] = a[lo:hi:hi]
lo, hi = hi, hi+(i+1+1)
}

t[0][0] = 1
for r := 1; r < rows; r++ {
tr := t[r]
tr[0], tr[r] = 1, 1
tr1 := t[r-1]
for c := r / 2; c > 0; c-- {
n := tr1[c-1] + tr1[c]
tr[c], tr[r-c] = n, n
}
}
return t
}

func main() {
for _, r := range Triangle(7) {
fmt.Println(r)
}
}