3
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Dave C Apr 17 '15 at 15:25
  • \$\begingroup\$ @DaveC can you please advise as to how do I change the program, to use array as a type \$\endgroup\$ – nmdr Apr 22 '15 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.