The length L at the time of joining, when the length of the bar of the N (1 ≦ N ≦ 5000) is supplied from standard input, is the L by connecting three lengths among the N number of bars please write a program to find the total number of combinations of. However, and the length of the individual bars, length was pieced together (L) is a positive integer, is sufficient handle range in 32bit integer. In addition, it has all the length of the bar different things.
for example) input:
15
5
8
4
10
3
2
output:
2 //{{2, 3, 10}, {3, 4, 8}}
example 2) input :
35
10
13
12
17
10
4
18
3
11
5
7
output:
6 //{{4, 13, 18}, {5, 12, 18}, {5, 13, 17}, {7, 10, 18}, {7, 11, 17}, {10, 12, 13}}
and my answer is here
package main
import (
"fmt"
"sort"
)
func main() {
input_count := 0
var target int
var count int
var v int
var array []int
for read_count, _ := fmt.Scan(&v); read_count != 0; read_count, _ = fmt.Scan(&v) {
if 0 == input_count {
target = v
} else if 1 == input_count {
count = v
array = make([]int, count)
} else {
array[input_count-2] = v
}
input_count++
}
sort.Ints(array)
fmt.Println(Calculate(target, count, array))
}
func Except(pair []int, count int, array []int) []int {
except := make([]int, count-pair[2])
except_index := 0
on := false
for _, v := range array {
if on {
except[except_index] = v
except_index++
}
if v == pair[1] {
on = true
}
}
return except
}
func ListUp(target int, count int, array []int) [][]int {
max := array[count-1]
list := make([][]int, Fact(count-1))
list_index := 0
for i, h := range array {
if count > i+1 && target > h+array[i+1] {
for j, v := range array[i+1:] {
if count > i+j+1 && target <= max+h+v && target > h+v {
list[list_index] = []int{h, v, i + j + 1}
list_index++
}
}
}
}
return list
}
//func Calculate(target int, count int, array []int) [][]int {
func Calculate(target int, count int, array []int) int {
// var answers [][]int
answer_count := 0
for _, pair := range ListUp(target, count, array) {
if 3 == len(pair) {
pair_sum := pair[0] + pair[1]
if target-pair_sum >= array[0] {
for _, v := range Except(pair, count, array) {
if target == pair[0]+pair[1]+v {
// answers = append(answers, []int{pair[0], pair[1], v})
answer_count++
}
}
}
}
}
return answer_count
}
func Fact(n int) int {
if n == 0 {
return 0
}
return n + Fact(n-1)
}
Does anyone who can refactor the code? and you should refactor it if input https://github.com/freddiefujiwara/horiemon-challenge-codeiq/blob/master/sample4.txt then output
1571200
in 10 seconds
current status is here
time ./horiemon-challenge-codeiq < sample4.txt
1571200
real 6m56.584s
user 6m56.132s
sys 0m1.578s
very very slow.
Your time of almost seven minutes is very, very slow. Ten seconds is slow. One second is more reasonable, a tenth of a second is good. For example, using an O(N*N) algorithm,
package main
import (
"bufio"
"errors"
"fmt"
"io"
"os"
"sort"
"strconv"
"strings"
)
func triples(l int, b []int) int {
t := 0
sort.Ints(b)
// for i < j < k, b[i] <= b[j] <= b[k]
for i := 0; i < len(b)-2; i++ {
x := b[i]
if x > l {
break
}
lx := l - x
j, k := i+1, len(b)-1
y := b[j]
z := b[k]
for j < k {
yz := y + z
switch {
case lx > yz:
j++
y = b[j]
case lx < yz:
k--
z = b[k]
default:
// l == b[i]+b[j]+b[k]
t++
j++
k--
y = b[j]
z = b[k]
}
}
}
return t
}
func readInput() (l int, b []int, err error) {
r := bufio.NewReader(os.Stdin)
for {
line, err := r.ReadString('
')
line = strings.TrimSpace(line)
if err == nil && len(line) == 0 {
err = io.EOF
}
if err != nil {
if err == io.EOF {
break
}
return 0, nil, err
}
i, err := strconv.Atoi(string(line))
if err == nil && i < 0 {
err = errors.New("Nonpositive number: " + line)
}
if err != nil {
return 0, nil, err
}
b = append(b, i)
}
if len(b) > 0 {
l = b[0]
b = b[1:]
if len(b) > 1 {
n := b[0]
b = b[1:]
if n != len(b) {
err := errors.New("Invalid number of bars: " + strconv.Itoa(len(b)))
return 0, nil, err
}
}
}
return l, b, nil
}
func main() {
l, b, err := readInput()
if err != nil {
fmt.Fprintln(os.Stderr, err)
return
}
t := triples(l, b)
fmt.Println(t)
}
Output:
1571200
real 0m0.164s
user 0m0.161s
sys 0m0.004s
For comparison, your program,
Output:
1571200
real 9m24.384s
user 16m14.592s
sys 0m19.129s
ive tuned
package main
import (
"bufio"
"errors"
"fmt"
"io"
"os"
"sort"
"strconv"
"strings"
)
type triple struct {
x, y, z int
}
func triples(l int, n []int, list bool) (nt int, t []triple) {
num_of_list := len(n)
for i := 0; i < num_of_list-2; i++ {
x := n[i]
if x > l {
break
}
for j := i + 1; j < num_of_list-1; j++ {
y := x + n[j]
if y > l {
break
}
pos := sort.SearchInts(n[j:], l-y)
if j < pos+j && pos+j < num_of_list && n[pos+j] == l-y {
nt++
}
}
}
return nt, t
}
func readInput() (l int, n []int, err error) {
r := bufio.NewReader(os.Stdin)
for {
line, err := r.ReadString('
')
line = strings.TrimSpace(line)
if err == nil && len(line) == 0 {
err = io.EOF
}
if err != nil {
if err == io.EOF {
break
}
return 0, nil, err
}
i, err := strconv.Atoi(string(line))
if err == nil && i < 0 {
err = errors.New("Nonpositive number: " + line)
}
if err != nil {
return 0, nil, err
}
n = append(n, i)
}
if len(n) > 0 {
l = n[0]
n = n[1:]
}
sort.Ints(n)
for i := 1; i < len(n); i++ {
if n[i] == n[i-1] {
copy(n[i:], n[i+1:])
n = n[:len(n)-1]
}
}
return l, n, nil
}
func main() {
l, n, err := readInput()
if err != nil {
fmt.Fprintln(os.Stderr, err)
return
}
list := false
nt, t := triples(l, n, list)
fmt.Println(nt)
if list {
fmt.Println(t)
}
}