Skip to content

Instantly share code, notes, and snippets.

@Garciat
Last active August 20, 2019 15:46
Show Gist options
  • Save Garciat/f9a45b880c9e6abddb7937c96177a37a to your computer and use it in GitHub Desktop.
Save Garciat/f9a45b880c9e6abddb7937c96177a37a to your computer and use it in GitHub Desktop.
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:]...)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment