last-digit-of-a-huge-number.go

package kata

// LastDigit kata
func LastDigit(as []int) int {
	if len(as) == 0 {
		return 1
	}
	return newModPowBase(&simpleGen{
    state: 1,
    base: as[0],
    mod: 10,
  }).ModPowMulti(as[1:]...)
}

type GenThing interface {
  Gen() int
}

type simpleGen struct {
  state int
  base int
  mod int
}

func (g *simpleGen) Gen() int {
  v := g.state
  g.state = (g.state * (g.base % g.mod)) % g.mod
  return v
}

type modPowGen struct {
  modPow *modPowBase
  state int
  base int
}

func (g *modPowGen) Gen() int {
  v := g.modPow.ModPowAgainstPower(g.base, g.state)
  g.state += 1
  return v
}

type modPowBase struct {
	resultsPrefix []int
	resultsCycle  []int
}

func newModPowBase(g GenThing) *modPowBase {
	values := []int{}
	indexByValue := map[int]int{}

  var currentValue int
	for {
		currentValue = g.Gen()
		if _, exists := indexByValue[currentValue]; exists {
			break
		} else {
			indexByValue[currentValue] = len(values)
			values = append(values, currentValue)
		}
	}
  
	cycleStartPos := indexByValue[currentValue]
	return &modPowBase{
		resultsPrefix: values[:cycleStartPos],
		resultsCycle:  values[cycleStartPos:],
	}
}

func (c *modPowBase) Len() int {
	return c.PrefixLen() + c.CycleLen()
}

func (c *modPowBase) PrefixLen() int {
	return len(c.resultsPrefix)
}

func (c *modPowBase) CycleLen() int {
	return len(c.resultsCycle)
}

func (c *modPowBase) ModPow(y int) int {
	if y < c.PrefixLen() {
		return c.resultsPrefix[y]
	}
	return c.resultsCycle[(y-c.PrefixLen())%c.CycleLen()]
}

func (c *modPowBase) ModPowAgainstPower(y, z int) int {
	// Assume: y, z >= 0
	if z == 0 {
		return c.ModPow(1)
	} else if y == 0 {
		return c.ModPow(0)
	} else if y == 1 {
		return c.ModPow(1)
	}
  
	// Currently: y >= 2; z >= 1
	powerValue := y
	for i := 1; i <= z; i, powerValue = i+1, powerValue*y {
		if powerValue >= c.PrefixLen() {
			// If we get here, the result is NOT in the cycle prefix
			resultPos := newModPowBase(&simpleGen{
        state: 1,
        base: y,
        mod: c.CycleLen(),
      }).ModPow(z) - c.PrefixLen()
			for resultPos < 0 {
				resultPos += c.CycleLen()
			}
			return c.resultsCycle[resultPos]
		}
	}
	return c.resultsPrefix[powerValue]
}

func (c *modPowBase) ModPowMulti(as ...int) int {
	if len(as) == 0 {
		return c.ModPow(1)
	} else if len(as) == 1 {
		return c.ModPow(as[0])
	}
	return newModPowBase(&modPowGen{
    modPow: c,
    state: 0,
    base: as[0],
  }).ModPowMulti(as[1:]...)
}