# Nuts and bolts algorithm

I am trying to learn Golang. This is a problem from Robert Sedgewick's Algorithms book:

You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger. But it is not possible to directly compare two nuts or two bolts. Given an efficient method for solving the problem.

This code applies an algorithm similar to quicksort to solve the problem:

// NutsAndBolts.go
package main

import (
"fmt"
)

type nutsBolts struct {
nuts  []int
bolts []int
}

type array []int

func newNutsBolts(nuts []int, bolts []int) *nutsBolts {
nb := new(nutsBolts)
nb.bolts = bolts
nb.nuts = nuts
return nb
}

func (nb *nutsBolts) sort(lo int, hi int) {

if hi <= lo {
return
}
pivotNut := array(nb.nuts).partition(lo, hi, nb.bolts[lo])
array(nb.bolts).partition(lo, hi, nb.nuts[pivotNut])

nb.sort(lo, pivotNut-1)
nb.sort(pivotNut+1, hi)
}

func (a array) partition(lo int, hi int, pivot int) int {
i := lo
j := hi

var hold int

for {

for a[i] < pivot && i < hi {
i++
}
for a[j] > pivot && j > lo {
j--
}

if i >= j {
break
}

hold = a[j]
a[j] = a[i]
a[i] = hold

}

return j
}

func main() {
nb := newNutsBolts([]int{5, 8, 4, 3, 1}, []int{3, 5, 4, 1, 8})

nb.sort(0, len(nb.nuts)-1)

fmt.Println(nb.nuts)
fmt.Println(nb.bolts)

}


Are there any mistakes with respect to writing good Golang code?

• Arrays and slices are different things in Go. Therefore it's as inadvisable to do type array []int as it is to do type float int. – Dave C Apr 17 '15 at 15:25
• @DaveC can you please advise as to how do I change the program, to use array as a type – nmdr Apr 22 '15 at 11:07