Recently in response to
[https://www.reddit.com/r/dailyprogrammer/comments/ffxabb/20200309_challenge_383_easy_necklace_matching](https://www.reddit.com/r/dailyprogrammer/comments/ffxabb/20200309_challenge_383_easy_necklace_matching)/
I came up with my nim solution which was pretty identical to that of a Go code
someone else posted. Seeing Go executing the same algorithm faster I translated
almost 1:1 from Go but Go still wins:
import os, tables
# My original
# func smallestRepr(arg: string): string =
# let repeated = arg & arg
# result = arg
# var i = 0
# while i + high(arg) <= repeated.high():
# let slice = repeated[i .. i + arg.high()]
# if slice < result:
# result = slice
# inc i
# Translation
func smallestRepr(arg: string): string =
let repeated = arg & arg
result = arg
for i in 1 .. arg.len():
let slice = repeated[i .. i + arg.high()]
if slice < result:
result = slice
when isMainModule:
var wordTable = initTable[string, seq[string]]()
for word in paramStr(1).lines():
let key = word.smallestRepr()
if unlikely wordTable.hasKey(key):
wordTable[key] &= word
if wordTable[key].len() == 4:
echo(wordTable[key])
break
else:
wordTable[key] = @[word]
Run
Go:
package main
import (
"bufio"
"fmt"
"os"
)
func canonicalize(s string) string {
c := s + s[:len(s)-1]
best := s
for i := 1; i < len(s); i++ {
if c[i:i+len(s)] < best {
best = c[i : i+len(s)]
}
}
return best
}
func main() {
seen := make(map[string][]string)
inputFile, err := os.Open(os.Args[1])
defer inputFile.Close()
if err != nil {
os.Exit(1)
}
scanner := bufio.NewScanner(inputFile)
for scanner.Scan() {
word := scanner.Text()
n := canonicalize(word)
seen[n] = append(seen[n], word)
}
for _, words := range seen {
if len(words) == 4 {
fmt.Printf("%v\n", words)
break
}
}
}
Run
In my machine, Nim version compiled with -d:release executes in 0.274 seconds
while the Go version takes only 0.120 seconds. I'm looking for places where I
didn't notice any performance pitfall.
