Problem: Given an array of positive distinct integer denoting the crossing time of ‘n’ people. These ‘n’ people are standing at one side of bridge. Bridge can hold at max two people at a time. When two people cross the bridge, they must move at the slower person’s pace. Find the minimum total time in which all persons can cross the bridge.
I am not able to find the pattern as of how to scale this for 'n' people. But somehow I managed to find the case with 4 people. Can someone help me with this. I am new to Golang and I am stuck with this problem.
package main
import (
"fmt"
"io/ioutil"
"log"
"os"
"sort"
"gopkg.in/yaml.v2"
)
type conf struct {
Person []map[string]float32 `yaml:"person"`
}
func (c *conf) getConf() *conf {
filename := os.Args[1] // Taking file input
yamlFile, err := ioutil.ReadFile(filename) // Yaml parse
if err != nil {
log.Printf("yamlFile.Get err #%v ", err)
}
err = yaml.Unmarshal(yamlFile, c)
if err != nil {
log.Fatalf("Unmarshal: %v", err)
}
return c
}
func main() {
var c conf // Object of struct conf
c.getConf() // calling getConf function
// Sorting the current conf map
n := map[float32][]string{} // Map to store current conf map
var a []float32 // Store values from conf map
for k, v := range c.Person {
v := float32(v)
fmt.Println(k, v)
n[v] = append(n[v], k)
}
for k := range n {
a = append(a, k)
}
// Converting float32 as float64 in order to sort the values in conf map
float32AsFloat64Values := make([]float64, len(a))
for i, val := range a {
float32AsFloat64Values[i] = float64(val)
}
sort.Float64s(float32AsFloat64Values)
for i, val := range float32AsFloat64Values {
a[i] = float32(val)
}
var time float32
fmt.Printf("
%v
", a)
for _, k := range a {
min1 := a[0]
min2 := a[1]
min3 := a[2]
for _, s := range n[k] {
//Debug:
fmt.Printf("%s, %g
", s, k)
if len(a) > 3 {
time = (3 * min2) + min1 + a[3] //Formula for minimum time in case of 4 people
} else if len(a) == 3 {
time = min1 + min2 + min3
} else {
fmt.Println("Enter valid arguments in config.yaml")
}
}
}
fmt.Printf("Minimum time taken to cross the bridge is:\t%g
", time)
}
Playground: https://play.golang.org/p/ObTVA8gk0mg
Config.yaml is:
person:
person_1: 2
person_2: 1
person_3: 5
person_4: 8
person_5: 9
One could run this as: 'go run main.go config.yaml'. My scenario is that there could be 4,5 or 'n' number of people given in this yaml. Then what would be the minimum time for them to cross the bridge given the constraints.