Fall Seven Times, Get Up Eight

There is a Japanese saying that goes Fall seven times, get up eight. I like it a lot but the programmer in me always stops at the numbers. If I fall seven times then I should get up seven times, so where does the eighth one come from? I am not going to argue with a proverb. I am going to use it as an excuse to write about off-by-one errors, which are bugs where the logic is right and a count is one more or one less than it should be. The examples are written in Go but the same errors exist in every programming language.

Counting get-ups in Go Link to heading

I wrote a small function that counts how many times a person gets up after a number of falls.

package main

import "fmt"

func getUps(falls int, standing bool) int {
	count := 0
	for range falls {
		// You have to be on your feet in order to fall
		if !standing {
			count++
			standing = true
		}
		standing = false
	}
	// Finish on your feet
	if !standing {
		count++
	}
	return count
}

func main() {
	fmt.Println("Start standing:", getUps(7, true))
	fmt.Println("Start on the ground:", getUps(7, false))
}

The standing parameter says where the person is before the first fall. Inside the loop a person who is on the ground has to get up before they can fall again and after the last fall they get up once more in order to finish on their feet. The two calls in main() have the same number of falls and a different value for standing.

Start standing: 7
Start on the ground: 8

Both numbers are correct. A person who starts on their feet gets up seven times and a person who starts on the ground gets up eight times. I believe that the saying starts on the ground because nobody is born standing. The number of falls was never the problem. What was missing from my question was the initial state and this is where most off-by-one errors come from.

Fences and commas Link to heading

The best known version of this is the fencepost problem, which asks how many posts you need for a fence with 10 sections. The answer is 11 because every section needs a post at its end and the first section also needs a post at its start. Printing a list with commas between the items is the same question the other way around, as 3 items need 2 commas.

package main

import (
	"fmt"
	"strings"
)

func main() {
	names := []string{"Go", "Zig", "C"}

	fmt.Print("First loop:  ")
	for _, name := range names {
		fmt.Print(name, ", ")
	}
	fmt.Println()

	fmt.Print("Second loop: ")
	for i, name := range names {
		if i > 0 {
			fmt.Print(", ")
		}
		fmt.Print(name)
	}
	fmt.Println()

	fmt.Println("Join:       ", strings.Join(names, ", "))
}
First loop:  Go, Zig, C, 
Second loop: Go, Zig, C
Join:        Go, Zig, C

The first loop prints one comma per item, which leaves a comma at the end of the line. The second loop prints a comma before every item apart from the first one and the output is right. The third line of the output comes from the last statement of the program, where strings.Join() puts the separator between the elements of the slice without a loop. I use strings.Join() whenever I can because then there is no count for me to get wrong.

Using <= instead of < Link to heading

The following loop is the most common off-by-one error that I know of.

package main

import "fmt"

func main() {
	days := []string{"Mon", "Tue", "Wed"}

	for i := 0; i <= len(days); i++ {
		fmt.Println(i, days[i])
	}
}
0 Mon
1 Tue
2 Wed
panic: runtime error: index out of range [3] with length 3

A slice with 3 elements has the indexes 0, 1 and 2. The i <= len(days) condition lets i become 3 and Go panics instead of reading memory that does not belong to the slice. I am happy with the panic because of what the same loop does in C, where nothing checks the index.

#include <stdio.h>

int main(void) {
	int numbers[] = {10, 20, 30};
	int length = sizeof(numbers) / sizeof(numbers[0]);

	for (int i = 0; i <= length; i++) {
		printf("%d %d\n", i, numbers[i]);
	}
	printf("Still running\n");
	return 0;
}
0 10
1 20
2 30
3 1
Still running

The C program compiles without a warning, even with -Wall, and it runs to the end. The fourth line of the output has the value 1, which is not in the array because it comes from whatever was in memory after the array. When I compiled the same file with -O2 that line became 3 30, so the wrong value is not even the same from one build to the next. A bug like that can stay in a program for a long time whereas the Go panic tells me the index and the length right away.

Back in Go, the fix is to write i < len(days) but I prefer the next version, which has no condition at all.

for i, day := range days {
	fmt.Println(i, day)
}

The range keyword knows where the slice ends. Since Go 1.22 it also works with an integer, so for i := range 3 goes over 0, 1 and 2. The getUps() function uses the same form for its loop.

Slices are half-open Link to heading

Slicing in Go uses a half-open range, which means that s[a:b] includes the element at index a and excludes the element at index b.

package main

import "fmt"

func main() {
	s := []int{10, 20, 30, 40, 50}

	fmt.Println(s[1:4], len(s[1:4]))
	fmt.Println(s[len(s)-1])
	fmt.Println(s[:2], s[2:])
	fmt.Println(s[len(s):], len(s[len(s):]))
}
[20 30 40] 3
50
[10 20] [30 40 50]
[] 0

The length of s[1:4] is 4 - 1 = 3 with no extra one to add or remove. The last element is at index len(s)-1 and not at index len(s). I like that s[:2] and s[2:] split the slice at the same index without losing or repeating an element. The last line looks strange because s[len(s)] panics while s[len(s):] is a valid slice with no elements.

Rounding up a division Link to heading

If I show 10 items per page, how many pages do I need for n items?

package main

import "fmt"

func main() {
	size := 10
	for _, n := range []int{0, 1, 9, 10, 11, 20, 21} {
		fmt.Printf("%2d items: n/size = %d, (n+size-1)/size = %d\n",
			n, n/size, (n+size-1)/size)
	}
}
 0 items: n/size = 0, (n+size-1)/size = 0
 1 items: n/size = 0, (n+size-1)/size = 1
 9 items: n/size = 0, (n+size-1)/size = 1
10 items: n/size = 1, (n+size-1)/size = 1
11 items: n/size = 1, (n+size-1)/size = 2
20 items: n/size = 2, (n+size-1)/size = 2
21 items: n/size = 2, (n+size-1)/size = 3

Integer division in Go throws away the remainder, so n/size forgets the last page when that page is not full. Adding size-1 before the division moves every partly filled page up to the next number while the full pages stay as they are. The rows with 0, 10 and 20 items are the ones that I check first because a formula such as n/size + 1 looks fine for 11 items and gives one page too many for these three.

How I look for them Link to heading

Most of my off-by-one bugs show up with an empty slice, with a slice that has one element or at the last index, so these are the cases that I test first. Before I write a loop I also ask myself where the counting starts, just like with the person on the ground. Apart from that I prefer range and functions like strings.Join() to writing the bounds by hand.

Back to the saying Link to heading

The saying is right. It counts from the ground and that gives eight. If you count from your feet you get seven and the number of falls is the same in both cases. I am fine with either number as long as the last thing that happens is getting up.