Skip to content

Instantly share code, notes, and snippets.

@kylelemons

kylelemons/euler24_brute.go

Created December 9, 2012 05:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kylelemons/4243521 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kylelemons/4243521 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. kylelemons revised this gist Dec 9, 2012. 2 changed files with 33 additions and 0 deletions.
    0 euler24.go → euler24_brute.go
    View file
    File renamed without changes.
    33 changes: 33 additions & 0 deletions euler24_fast.go
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,33 @@
    package main

    import (
    "fmt"
    )

    const Max = 10
    const Index = 1000000

    func main() {
    digits := make([]byte, 0, Max)
    for i := byte(0); i < Max; i++ {
    digits = append(digits, i)
    }

    rem := Index - 1
    res := make([]byte, 0, Max)
    for i := Max - 1; i >= 0; i-- {
    f := fact(i)
    quo := rem / f
    rem = rem % f
    res = append(res, digits[quo])
    digits = append(digits[:quo], digits[quo+1:]...)
    }
    fmt.Println(res)
    }

    func fact(n int) int {
    if n < 2 {
    return 1
    }
    return n * fact(n-1)
    }
  2. kylelemons revised this gist Dec 9, 2012. 1 changed file with 13 additions and 21 deletions.
    34 changes: 13 additions & 21 deletions euler24.go
    View file
    Original file line number Diff line number Diff line change
    @@ -4,44 +4,36 @@ import (
    "fmt"
    )

    var _ = fmt.Printf

    const Max = 10
    const Index = 1000000 - 1
    const Index = 1000000

    func main() {
    numbers := make([]byte, 0, Max)
    for i := 0; i < Max; i++ {
    numbers = append(numbers, byte(i))
    }

    count := 1
    for i := 2; i <= Max; i++ {
    count *= i
    }
    if count > Index {
    count = Index+1
    }
    perms = make([][Max]byte, 0, count)

    result = make(chan [Max]byte, 1)
    index = 0
    perm(numbers, 0, len(numbers))
    if len(perms) > Index {
    fmt.Println(perms[Index])
    } else {
    fmt.Println("only", len(perms), "perms generated")
    if len(result) > 0 {
    fmt.Println(<-result)
    }
    }

    var perms [][Max]byte
    var index int
    var result chan [Max]byte

    func perm(numbers []byte, lo, hi int) {
    if len(perms) > Index {
    if index > Index {
    return
    }
    if hi-lo < 2 {
    var p [Max]byte
    copy(p[:], numbers)
    perms = append(perms, p)
    if index++; index == Index {
    var p [Max]byte
    copy(p[:], numbers)
    result <- p
    }
    return
    }
    for i := 1; i < hi-lo+1; i++ {
  3. kylelemons created this gist Dec 9, 2012.
    64 changes: 64 additions & 0 deletions euler24.go
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,64 @@
    package main

    import (
    "fmt"
    )

    var _ = fmt.Printf

    const Max = 10
    const Index = 1000000 - 1

    func main() {
    numbers := make([]byte, 0, Max)
    for i := 0; i < Max; i++ {
    numbers = append(numbers, byte(i))
    }

    count := 1
    for i := 2; i <= Max; i++ {
    count *= i
    }
    if count > Index {
    count = Index+1
    }
    perms = make([][Max]byte, 0, count)

    perm(numbers, 0, len(numbers))
    if len(perms) > Index {
    fmt.Println(perms[Index])
    } else {
    fmt.Println("only", len(perms), "perms generated")
    }
    }

    var perms [][Max]byte

    func perm(numbers []byte, lo, hi int) {
    if len(perms) > Index {
    return
    }
    if hi-lo < 2 {
    var p [Max]byte
    copy(p[:], numbers)
    perms = append(perms, p)
    return
    }
    for i := 1; i < hi-lo+1; i++ {
    rotateR(numbers, lo, lo+i)
    perm(numbers, lo+1, hi)
    rotateL(numbers, lo, lo+i)
    }
    }

    func rotateL(numbers []byte, lo, hi int) {
    for i := lo + 1; i < hi; i++ {
    numbers[i-1], numbers[i] = numbers[i], numbers[i-1]
    }
    }

    func rotateR(numbers []byte, lo, hi int) {
    for i := hi - 1; i > lo; i-- {
    numbers[i-1], numbers[i] = numbers[i], numbers[i-1]
    }
    }