2022-09-13 23:39:52 +02:00
|
|
|
// Copyright 2022 wanderer <wanderer at dotya.ml>
|
|
|
|
// SPDX-License-Identifier: GPL-3.0-or-later
|
|
|
|
|
|
|
|
package main
|
|
|
|
|
|
|
|
import (
|
|
|
|
"log"
|
|
|
|
"os"
|
|
|
|
"strconv"
|
2022-09-14 00:33:11 +02:00
|
|
|
"strings"
|
2022-09-13 23:39:52 +02:00
|
|
|
"time"
|
|
|
|
)
|
|
|
|
|
|
|
|
type matrix struct {
|
|
|
|
rows [][]int
|
|
|
|
}
|
|
|
|
|
|
|
|
// stoi attempts to convert a supposed int in string form to an actual int,
|
|
|
|
// fails loudly if it doesn't work.
|
|
|
|
func stoi(s string) int {
|
|
|
|
val, err := strconv.Atoi(s)
|
|
|
|
if err != nil {
|
|
|
|
log.Fatalln("could not convert from string to int:", s, err)
|
|
|
|
}
|
|
|
|
|
|
|
|
return val
|
|
|
|
}
|
|
|
|
|
|
|
|
// rowtoi converts a row (a []string) to an []int and returns it.
|
|
|
|
func rowtoi(row []string) []int {
|
|
|
|
cols := len(row)
|
|
|
|
|
|
|
|
// prealloc, when the size is known, gosimple is wrong here.
|
|
|
|
intRow := make([]int, cols, cols) //nolint:gosimple
|
|
|
|
|
|
|
|
for i, v := range row {
|
|
|
|
intRow[i] = stoi(v)
|
|
|
|
}
|
|
|
|
|
|
|
|
return intRow
|
|
|
|
}
|
|
|
|
|
|
|
|
// isNonEmptyMatrix checks the [][]string input and determines whether it is a
|
|
|
|
// non-empty matrix, since that is the kind we care about.
|
|
|
|
func isNonEmptyMatrix(strmatrix [][]string) bool {
|
|
|
|
initCols := len(strmatrix[0])
|
|
|
|
|
|
|
|
if initCols == 0 || len(strmatrix) == 0 {
|
|
|
|
log.Printf("emptymatrix: we don't want those")
|
|
|
|
return false
|
|
|
|
}
|
|
|
|
|
|
|
|
for i, v := range strmatrix {
|
|
|
|
cols := len(v)
|
|
|
|
|
|
|
|
if cols != initCols {
|
2022-09-13 23:42:01 +02:00
|
|
|
log.Printf(
|
|
|
|
"notamatrix: all rows until now were of '%d' columns\n"+
|
|
|
|
"offending row: #%d, size: %d",
|
|
|
|
initCols, i, cols,
|
|
|
|
)
|
|
|
|
|
2022-09-13 23:39:52 +02:00
|
|
|
return false
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
return true
|
|
|
|
}
|
|
|
|
|
|
|
|
func initMatrix(strmatrix [][]string) matrix {
|
|
|
|
m := &matrix{}
|
|
|
|
// we can now safely do this because at this point we have already checked
|
|
|
|
// that strmatrix is a "valid" matrix.
|
|
|
|
cols := len(strmatrix[0])
|
|
|
|
rows := len(strmatrix)
|
|
|
|
|
|
|
|
// prealloc, when the size is known, gosimple is wrong here.
|
|
|
|
m.rows = make([][]int, rows, rows) //nolint:gosimple
|
|
|
|
for i := range strmatrix {
|
|
|
|
// prealloc, when the size is known, gosimple is wrong here.
|
|
|
|
m.rows[i] = make([]int, cols, cols) //nolint:gosimple
|
|
|
|
}
|
|
|
|
|
|
|
|
return *m
|
|
|
|
}
|
|
|
|
|
|
|
|
// convertMatrix attempts to convert the whole string matrix to an int matrix.
|
|
|
|
func convertMatrix(strmatrix [][]string) matrix {
|
|
|
|
if !isNonEmptyMatrix(strmatrix) {
|
|
|
|
log.Fatalln("bailing...")
|
|
|
|
os.Exit(2)
|
|
|
|
}
|
|
|
|
|
|
|
|
m := initMatrix(strmatrix)
|
|
|
|
|
|
|
|
for i, v := range strmatrix {
|
|
|
|
m.rows[i] = rowtoi(v)
|
|
|
|
}
|
|
|
|
|
|
|
|
return m
|
|
|
|
}
|
|
|
|
|
2022-09-14 00:33:11 +02:00
|
|
|
// fmtPath efficiently formats positional values for printing.
|
|
|
|
func fmtPath(x, y, val int) string {
|
|
|
|
s := "[" + strconv.Itoa(x) + "," + strconv.Itoa(y) + "] (" +
|
|
|
|
strconv.Itoa(val) + ")"
|
|
|
|
return s
|
|
|
|
}
|
|
|
|
|
2022-09-13 23:39:52 +02:00
|
|
|
// traverseMatrix traverses the given matrix in such a manner as to accumulate
|
|
|
|
// the smallest possible sum. allowed movements are down and to the right.
|
2022-09-14 00:33:11 +02:00
|
|
|
// it also prints a cute ascii path of traversal.
|
|
|
|
func traverseMatrixMinSumPath(m matrix) {
|
2022-09-13 23:39:52 +02:00
|
|
|
start := time.Now()
|
|
|
|
|
2022-09-14 00:33:11 +02:00
|
|
|
cols := len(m.rows[0])
|
|
|
|
rows := len(m.rows)
|
|
|
|
// current column.
|
|
|
|
col := 0
|
|
|
|
// current row index.
|
|
|
|
i := 0
|
|
|
|
sum := m.rows[i][col]
|
|
|
|
traversing := true
|
|
|
|
path := "init"
|
|
|
|
graph := "x"
|
|
|
|
|
|
|
|
log.Printf("matrix cols: %d, rows: %d\n", cols, rows)
|
|
|
|
|
|
|
|
for traversing {
|
|
|
|
path += ", " + fmtPath(i, col, m.rows[i][col])
|
|
|
|
|
|
|
|
nextCol := col + 1
|
|
|
|
nextRow := i + 1
|
|
|
|
|
|
|
|
switch {
|
|
|
|
case nextCol < cols && nextRow < rows:
|
|
|
|
// can go either way.
|
|
|
|
right := m.rows[i][col+1]
|
|
|
|
down := m.rows[i+1][col]
|
|
|
|
|
|
|
|
if right < down {
|
|
|
|
col++
|
|
|
|
|
|
|
|
sum += right
|
|
|
|
graph += "x"
|
|
|
|
} else {
|
|
|
|
i++
|
|
|
|
|
|
|
|
sum += down
|
|
|
|
graph += "\n" + strings.Repeat(" ", col) + "x"
|
|
|
|
}
|
|
|
|
|
|
|
|
case nextRow == rows && nextCol < cols:
|
|
|
|
// can only go right.
|
|
|
|
col++
|
|
|
|
sum += m.rows[i][col]
|
|
|
|
graph += "x"
|
|
|
|
|
|
|
|
case nextCol == cols && nextRow < rows:
|
|
|
|
// can only go down.
|
|
|
|
i++
|
|
|
|
sum += m.rows[i][col]
|
|
|
|
graph += "\n" + strings.Repeat(" ", col) + "x"
|
|
|
|
|
|
|
|
default:
|
|
|
|
path += ", finish"
|
|
|
|
|
|
|
|
log.Printf(
|
|
|
|
"traversal concluded with sum: %d\n"+
|
|
|
|
"graph:\n%s\n"+
|
|
|
|
"traversal path:\n%s\n\n",
|
|
|
|
sum, graph, path,
|
|
|
|
)
|
|
|
|
|
|
|
|
traversing = false
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
log.Printf("traversing the matrix took: %s\n", time.Since(start))
|
2022-09-13 23:39:52 +02:00
|
|
|
}
|