AOC第8天 - 树梢树屋-DEV365 开发者社区

树梢树屋

精灵出现问题，他们想建造一棵树屋，但他们想确保他们有足够的掩护。

我们获得了森林的地图，其中有一个代表每棵树高度的数字。

解析

我们关心每棵树及其高度的位置。
如果我们将地图解析为矩阵[][]int

func parse(raw string) [][]int {
    rows := strings.Split(string(raw), "\n")
    matrix := make([][]int, len(rows))
    for i, row := range rows {
        matrix[i] = make([]int, len(row))
    }

    for i, row := range rows {
        for j, c := range row {
            matrix[i][j] = util.ParseInt(string(c))
        }
    }

    return matrix
}

第1部分

我们的任务是确定地图上有多少可见树。

从给定的方向（向上，右，下和左）可见一棵树，只有直接在该线上和边缘上的所有树都比他短。

根据该定义，我们可以推断出地图边缘上的每棵树都是可见的，并且从Get-go
中看到了最初的可见树

// (len(mat)-2)*2 top and bottom rows - the shared elements with the columns
// len(mat[0])*2 right and left most columns
visibleTrees := (len(mat)-2)*2 + len(mat[0])*2

现在，对于其他每棵树，我们需要检查它是否可以从某个方向可见
为此，我们将编写4个功能，每个功能检查不同的方向


func checkLeft(mat [][]int, i, j int) bool {
    for k := j - 1; k >= 0; k-- {
        if mat[i][k] >= mat[i][j] {
            return false
        }
    }
    return true
}

func checkRight(mat [][]int, i, j int) bool {
    for k := j + 1; k < len(mat[0]); k++ {
        if mat[i][k] >= mat[i][j] {
            return false
        }
    }
    return true
}

func checkUp(mat [][]int, i, j int) bool {
    for k := i - 1; k >= 0; k-- {
        if mat[k][j] >= mat[i][j] {
            return false
        }
    }
    return true
}

func checkDown(mat [][]int, i, j int) bool {
    for k := i + 1; k < len(mat[0]); k++ {
        if mat[k][j] >= mat[i][j] {
            return false
        }
    }
    return true
}

对于每个方向，我们一直走到边缘，如果在某个时候，一棵树比当前的树高，我们会返回false并尝试另一个方向。

让我们看看第一部分的完整解决方案

func Part1(raw string) int {
    mat := parse(raw)
    visibleTrees := (len(mat)-2)*2 + len(mat[0])*2

    for i, row := range mat {
        if i == 0 || i == len(mat)-1 {
            continue
        }

        for j, _ := range row {
            if j == 0 || j == len(row)-1 {
                continue
            }
            if checkLeft(mat, i, j) {
                visibleTrees++
                continue
            }
            if checkRight(mat, i, j) {
                visibleTrees++
                continue
            }
            if checkUp(mat, i, j) {
                visibleTrees++
                continue
            }
            if checkDown(mat, i, j) {
                visibleTrees++
                continue
            }

        }
    }

    return visibleTrees
}

我们在每个循环的开头都有一个if语句，以确保我们不再计算边缘。

此解决方案非常详细，我们可以通过多种方法来优化它，例如，跟踪每列和行中最高的树，并随着这些信息跳过一些检查。

但是...当前的解决方案足够快，并在我的本地机器上使用我的AOC输入在0.35中运行。

第2部分

计算每个树从各个方向可见多少树，乘以数字并在我们的地图中找到最大值树

我们将采用我们的检查功能并创建一个类似的对应物，名为calc<Direction>

func calcLeft(mat [][]int, i, j int) int {
    vis := 0
    for k := j - 1; k >= 0; k-- {

        if mat[i][k] >= mat[i][j] {
            return vis + 1
        }
        vis++
    }
    return vis
}

func calcRight(mat [][]int, i, j int) int {
    vis := 0
    for k := j + 1; k < len(mat[0]); k++ {
        if mat[i][k] >= mat[i][j] {
            return vis + 1
        }
        vis++
    }
    return vis
}

func calcUp(mat [][]int, i, j int) int {
    vis := 0
    for k := i - 1; k >= 0; k-- {
        if mat[k][j] >= mat[i][j] {
            return vis + 1
        }
        vis++
    }
    return vis
}

func calcDown(mat [][]int, i, j int) int {
    vis := 0
    for k := i + 1; k < len(mat[0]); k++ {
        if mat[k][j] >= mat[i][j] {
            return vis + 1
        }
        vis++
    }
    return vis
}

每个钙函数返回从地图上的点可见的树的数量。

我们的解决方案现在非常简单，对于每棵树，我们根据说明计算得分。
然后，我们将该分数与当前的最大分数进行比较，并在需要时交换它们。

func Part2(raw string) int {
    mat := parse(raw)
    max := 0
    for i, row := range mat {
        for j, _ := range row {
            score := calcLeft(mat, i, j) * calcRight(mat, i, j) * calcUp(mat, i, j) * calcDown(mat, i, j)
            if score > max {
                max = score
            }
        }
    }

    return max
}

就是今天，明天见，

您可以找到完整的代码here
感谢您的阅读！