Project Euler #22 with Golang; returns different result every time

Question

I am doing problem 22 of Project Euler with Go, which I am new to, and my code gives me inconsistent results meaning every time I run the program it shows a different result. It is always very close to what I have seen is the correct answer but ranges around within several hundred points. I originally thought it may have been due to float rounding inaccuracy but I have checked and that is not the case(I think). I would really appreciate it if someone could point out what may be going on that would cause this. I have struggled to find the problem with my code for several days and have not been able to solve it or even find similar issues on forums. As a side note I originally wrote this using the golang math/big package and was getting the same changing results.

package main

import (
    "fmt"
    "io/ioutil"
    "log"
    "math"
    "strings"
)

func openFileReturnSlice(f string) []string {
    bytes, err := ioutil.ReadFile(f)
    if err != nil {
        log.Fatal("Failed to read file: p022_names.txt")
    }
    s2s := strings.Split(string(bytes), "\"")
    s22 := strings.Join(s2s, "")
    names := strings.Split(s22, ",")
    return names
}

func alphabetize(n []string) ([]string, map[string]int) {
    wordsValues := make(map[string]float64)
    wordLetterVal := make(map[string]int)
    for _, s := range n {
        loop := -1
        var wordValue float64
        alpha := int(0)
        for _, l := range s {
            ell := int(l) - 64
            mvDec := math.Pow(100, math.Abs(float64(loop)))
            wordValue += float64(l) / mvDec
            alpha += ell
            loop--
        }
        wordsValues[s] = wordValue
        wordLetterVal[s] = alpha
    }
    var sortedNames []string
    lenWordValues := len(wordsValues)
    for i := 0; i < lenWordValues; i++ {
        var lowValName string
        lowVal := float64(10)
        for k, v := range wordsValues {
            if v < lowVal {
                lowVal = v
                lowValName = k
            }
        }
        delete(wordsValues, lowValName)
        sortedNames = append(sortedNames, lowValName)
    }
    return sortedNames, wordLetterVal
}

func main() {
    names := openFileReturnSlice("p022_names.txt")
    alphabetical, sumAlphaValues := alphabetize(names)
    var total int
    for k := 0; k < len(alphabetical); k++ {
        var temp int
        key := k + 1
        temp = sumAlphaValues[alphabetical[k]] * key
        total += temp
    }
    fmt.Println("The total is: ", total)
}

Answer 1

You are correct about the fault in your code being related to floating point numbers. Take these two names for example:

["BERNARDINE", "BERNARDINA"]

If you simply run your code on this input set, you get the following value for wordsValues:

map[BERNARDINE:0.6669827865826875 BERNARDINA:0.6669827865826875]

As you can clearly see, both these keys map to same value due to loss in floating point number precision. And as it has already been mentioned that map iteration order is randomized in Go, it is possible that your sorting algorithm is producing incorrect result (some iteration may put BERNARDINE before BERNARDINA since both will have same values).

Since float64 supports up to 15 significant digits, names having more than 8 characters could spell trouble.

The best solution is to use pre-existing sorting procedure as already detailed by @peterSO above.

Answer 2

The use of floating point is suspicious, it's imprecise. The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. Your use of maps is the most likely explanation for seemingly random behavior.

---

The first question to ask is: What is the right answer?

package main

import (
    "bytes"
    "fmt"
    "io/ioutil"
    "log"
    "strings"
)

func readNames(f string) []string {
    b, err := ioutil.ReadFile(f)
    if err != nil {
        log.Fatal(err)
    }
    s := string(bytes.Replace(b, []byte(`"`), []byte(``), -1))
    return strings.Split(s, ",")
}

func totalScores(names []string) int64 {
    for i := 0; i < len(names); i++ {
        for j := i + 1; j < len(names); j++ {
            if names[i] > names[j] {
                names[i], names[j] = names[j], names[i]
            }
        }
    }

    total := int64(0)
    for i, name := range names {
        score := int64(0)
        for _, char := range name {
            score += int64(char - 'A' + 1)
        }
        score *= int64(i) + 1
        total += score
    }
    return total
}

func main() {
    names := readNames("p022_names.txt")
    total := totalScores(names)
    fmt.Println("The total is: ", total)
}

Output:

The total is:  871198282

This is how Project Euler expected you to write the first version of your solution. Your second version should replace the simple selection sort with a faster sort, like Quicksort.

For example, your program takes a long time to produce the wrong result:

The total is:  871197995
real    0m1.945s
user    0m1.944s
sys     0m0.004s

My program produces the correct result and is faster:

The total is:  871198282
real    0m0.771s
user    0m0.768s
sys     0m0.004s

If we replace my selection sort with a Go sort:

sort.StringSlice(names).Sort()

The revised program produces the correct result and it's much faster:

The total is:  871198282
real    0m0.014s
user    0m0.012s
sys     0m0.000s

Project Euler, Names scores, Problem 22 is about fast sort algorithms, not about the trivial calculation of scores.

---

For a stable result from your code, comment out the delete statement:

// delete(wordsValues, lowValName)

Now you are left with the floating-point error: Floating-point arithmetic and IEEE floating point.

---

Your algorithm creates approximate, non-unique floating-point wordValues. Therefore, the random iteration over the map may choose some different lowVal and lowValName pairs and different map entries may be deleted.

Non-unique wordValues:

0.657666698284738
0.6576697465786885
0.6576697465786885
0.6576698865786884
0.6578786577658275
0.6578847978698485
0.658571858384738
0.6669827865826875
0.6765847269827377
0.676976698384738
0.677282738384698
0.6772827383847367
0.6772827383847367
0.677282738384738
0.677282738384738
0.6772827383847982
0.6776697769788476
0.6982786983847379
0.6986657871697675
0.7076798269786776
0.7076798269788476
0.7082657867698368
0.7082657867738368
0.7082696869827366
0.7082696869827366
0.7165668273697676
0.716979827169658
0.7169798271698486
0.716979827173658
0.716979827173658
0.716979827173658
0.7185737676698277
0.7269788273698486
0.7273766869716582
0.7465678185697674
0.746567818569769
0.746567818569769
0.7469657878698486
0.7479836980727379
0.7565847265827377
0.7565847269827377
0.7573776669827669
0.7765716865766978
0.7765826769767379
0.7765826769767379
0.7765827165826985
0.7765827165826985
0.7765827165826985
0.7765827165826985
0.7765827165827385
0.7765827165827385
0.7765827185698275
0.7773677269767378
0.827983657673787
0.8384698072657875
0.8472797765837379
0.8665766978847378