Addition chains: Difference between revisions

Content added Content deleted
(→‎{{header|Go}}: Added a second much faster version.)
Line 661: Line 661:


=={{header|Go}}==
=={{header|Go}}==
===Version 1===
{{trans|Kotlin}}
{{trans|Kotlin}}
<lang go>package main
<lang go>package main
Line 897: Line 898:
Brauer example : [1 2 3 4 7 10 17 27 44 88 176 203 379]
Brauer example : [1 2 3 4 7 10 17 27 44 88 176 203 379]
Non-Brauer analysis suppressed
Non-Brauer analysis suppressed
</pre>
<br>
===Version 2===
{{trans|Phix}}
Much faster than Version 1 and can now complete the non-Brauer analysis for N > 79 in a reasonable time.
<lang go>package main

import (
"fmt"
"time"
)

const (
maxLen = 13
maxNonBrauer = 382
)

func max(a, b int) int {
if a > b {
return a
}
return b
}

func contains(s []int, n int) bool {
for _, i := range s {
if i == n {
return true
}
}
return false
}

func isBrauer(a []int) bool {
for i := 2; i < len(a); i++ {
ok := false
for j := i - 1; j >= 0; j-- {
if a[i-1]+a[j] == a[i] {
ok = true
break
}
}
if !ok {
return false
}
}
return true
}

var (
brauerCount, nonBrauerCount int
brauerExample, nonBrauerExample string
)

func additionChains(target, length int, chosen []int) int {
le := len(chosen)
last := chosen[le-1]
if last == target {
if le < length {
brauerCount = 0
nonBrauerCount = 0
}
if isBrauer(chosen) {
brauerCount++
brauerExample = fmt.Sprint(chosen)
} else {
nonBrauerCount++
nonBrauerExample = fmt.Sprint(chosen)
}
return le
}
if le == length {
return length
}
if target > maxNonBrauer {
for i := le - 1; i >= 0; i-- {
next := last + chosen[i]
if next <= target && next > chosen[len(chosen)-1] && i < length {
length = additionChains(target, length, append(chosen, next))
}
}
} else {
var ndone []int
for {
for i := le - 1; i >= 0; i-- {
next := last + chosen[i]
if next <= target && next > chosen[len(chosen)-1] && i < length &&
!contains(ndone, next) {
ndone = append(ndone, next)
length = additionChains(target, length, append(chosen, next))
}
}
le--
if le == 0 {
break
}
last = chosen[le-1]
}
}
return length
}

func main() {
start := time.Now()
nums := []int{7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379}
fmt.Println("Searching for Brauer chains up to a minimum length of", maxLen-1)
for _, num := range nums {
brauerCount = 0
nonBrauerCount = 0
le := additionChains(num, maxLen, []int{1})
fmt.Println("\nN =", num)
fmt.Printf("Minimum length of chains : L(%d) = %d\n", num, le-1)
fmt.Println("Number of minimum length Brauer chains :", brauerCount)
if brauerCount > 0 {
fmt.Println("Brauer example :", brauerExample)
}
fmt.Println("Number of minimum length non-Brauer chains :", nonBrauerCount)
if nonBrauerCount > 0 {
fmt.Println("Non-Brauer example :", nonBrauerExample)
}
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</lang>

{{out}}
Timing is for an Intel Core i7 8565U machine:
<pre>
Searching for Brauer chains up to a minimum length of 12

N = 7
Minimum length of chains : L(7) = 4
Number of minimum length Brauer chains : 5
Brauer example : [1 2 3 4 7]
Number of minimum length non-Brauer chains : 0

N = 14
Minimum length of chains : L(14) = 5
Number of minimum length Brauer chains : 14
Brauer example : [1 2 3 4 7 14]
Number of minimum length non-Brauer chains : 0

N = 21
Minimum length of chains : L(21) = 6
Number of minimum length Brauer chains : 26
Brauer example : [1 2 3 4 7 14 21]
Number of minimum length non-Brauer chains : 3
Non-Brauer example : [1 2 4 5 8 13 21]

N = 29
Minimum length of chains : L(29) = 7
Number of minimum length Brauer chains : 114
Brauer example : [1 2 3 4 7 11 18 29]
Number of minimum length non-Brauer chains : 18
Non-Brauer example : [1 2 3 6 9 11 18 29]

N = 32
Minimum length of chains : L(32) = 5
Number of minimum length Brauer chains : 1
Brauer example : [1 2 4 8 16 32]
Number of minimum length non-Brauer chains : 0

N = 42
Minimum length of chains : L(42) = 7
Number of minimum length Brauer chains : 78
Brauer example : [1 2 3 4 7 14 21 42]
Number of minimum length non-Brauer chains : 6
Non-Brauer example : [1 2 4 5 8 13 21 42]

N = 64
Minimum length of chains : L(64) = 6
Number of minimum length Brauer chains : 1
Brauer example : [1 2 4 8 16 32 64]
Number of minimum length non-Brauer chains : 0

N = 47
Minimum length of chains : L(47) = 8
Number of minimum length Brauer chains : 183
Brauer example : [1 2 3 4 7 10 20 27 47]
Number of minimum length non-Brauer chains : 37
Non-Brauer example : [1 2 3 5 7 14 19 28 47]

N = 79
Minimum length of chains : L(79) = 9
Number of minimum length Brauer chains : 492
Brauer example : [1 2 3 4 7 9 18 36 43 79]
Number of minimum length non-Brauer chains : 129
Non-Brauer example : [1 2 3 5 7 12 24 31 48 79]

N = 191
Minimum length of chains : L(191) = 11
Number of minimum length Brauer chains : 7172
Brauer example : [1 2 3 4 7 8 15 22 44 88 103 191]
Number of minimum length non-Brauer chains : 2615
Non-Brauer example : [1 2 3 4 7 9 14 23 46 92 99 191]

N = 382
Minimum length of chains : L(382) = 11
Number of minimum length Brauer chains : 4
Brauer example : [1 2 4 5 9 14 23 46 92 184 198 382]
Number of minimum length non-Brauer chains : 0

N = 379
Minimum length of chains : L(379) = 12
Number of minimum length Brauer chains : 6583
Brauer example : [1 2 3 4 7 10 17 27 44 88 176 203 379]
Number of minimum length non-Brauer chains : 2493
Non-Brauer example : [1 2 3 4 7 14 17 31 62 124 131 248 379]

Took 1m52.920399026s
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Addition_chains"