Stairs and step sizes in Go

stairs.go

package main

import "fmt"

//You're given a target number of steps and the avialable options for
//how many steps you can take at time. Find the number of options to get
//to the top.

//Assumptions
// - Can't make 0 steps since applying a step size of 0 at any point will yield infinite options.
// - Multiple ways to get to the same step are different paths and both counted.
// - No negative step sizes.

func numPathsByStepSizeWithProgress(target uint, stepSizes []uint, progress uint) uint {
	if progress == target {
		return 1
	} else if progress > target {
		return 0
	}
	var optionCount uint
	for _, step := range stepSizes {
		optionCount += numPathsByStepSizeWithProgress(target, stepSizes, progress+step)
	}
	return optionCount
}

func numPathsByStepSize(target uint, stepSizes []uint) uint {
	if target == 0 {
		return 0
	}
	return numPathsByStepSizeWithProgress(target, stepSizes, 0)
}

func numPathsByStepSizeIterative(target uint, stepSizes []uint) uint {
	if target == 0 {
		return 0
	}
	numPathsByStep := make([]uint, target)
	var step uint
	for step = 1; step <= target; step++ {
		var numPaths uint
		for _, stepSize := range stepSizes {
			if step == stepSize {
				numPaths++
			}
			if step-stepSize-1 < target {
				numPaths += numPathsByStep[step-stepSize-1]
			}
		}
		numPathsByStep[step-1] = numPaths
	}
	return numPathsByStep[target-1]
}

func main() {
	var (
		target    uint
		stepSizes []uint
	)

	target = 8
	stepSizes = []uint{1, 2}
	fmt.Println(target, stepSizes)
	fmt.Println(numPathsByStepSize(target, stepSizes))          // 1111, 112, 121, 211, 22
	fmt.Println(numPathsByStepSizeIterative(target, stepSizes)) // 1111, 112, 121, 211, 22

	target = 4
	stepSizes = []uint{3}
	fmt.Println(target, stepSizes)
	// fmt.Println(numPathsByStepSize(target, stepSizes))          //
	fmt.Println(numPathsByStepSizeIterative(target, stepSizes)) //

	target = 4
	stepSizes = []uint{1, 3, 5}
	fmt.Println(target, stepSizes)
	fmt.Println(numPathsByStepSize(target, stepSizes))          // 1111, 13, 31
	fmt.Println(numPathsByStepSizeIterative(target, stepSizes)) // 1111, 13, 31

	target = 0
	stepSizes = []uint{1, 3, 5}
	fmt.Println(target, stepSizes)
	fmt.Println(numPathsByStepSize(target, stepSizes))          // impossible
	fmt.Println(numPathsByStepSizeIterative(target, stepSizes)) // impossible

	target = 444
	stepSizes = []uint{1, 3, 5}
	fmt.Println(target, stepSizes)
	// fmt.Println(numPathsByStepSize(target, stepSizes))          // A lot; painufully slow
	fmt.Println(numPathsByStepSizeIterative(target, stepSizes)) // A lot
}