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

go

Solution

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 `wordValue`s. Therefore, the random iteration over the map may choose some different `lowVal` and `lowValName` pairs and different map entries may be deleted.

Non-unique `wordValue`s:

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

Problem

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) } ```

Original source