杠杆拼图

Question

我开始玩开拓者:王者，很快就进了一个有6个杠杆的房间，还有一项通过操纵杠杆打开秘密门的任务。我以为所有杠杆的正确位置都是上升的。但是当你转动一个杠杆时，其他一两根杠杆也会翻转。例如，如果你翻转杠杆一，那么杠杆二和四也翻转，当你翻转杠杆二，杠杆一也翻转，等等。

但是你知道吗，编程比玩游戏更有趣，所以让我们弄清楚我们需要用什么样的杠杆来把它们都拉起来！

征求反馈意见:我刚在金刚，什么都行！

package main

import (
    "fmt"
    "strings"
)

type node struct {
    state      int         // a bitmask for every possible levers' configuration, lever one is the least significant bit, 1 is up, 0 is down
    neighbours []int       // all configurations (states, above) that are reachable by flipping a single lever
    levers     map[int]int // lookup that given a neighbour state gives what lever is pulled to reach this state
}

// given levers configuration, print it out in human-readable format
func formatState(state int, width int) string {
    var sb strings.Builder
    for i := 0; i < width; i++ {
        var desc string
        if state&1 == 0 {
            desc = "down"
        } else {
            desc = "up"
        }
        state >>= 1
        sb.WriteString(fmt.Sprintf("%d - %s; ", i+1, desc))
    }
    result := sb.String()
    if len(result) > 2 { // remove final "; "
        result = result[:len(result)-2]
    }
    return result
}

func printSolution(graph []node, prev map[int]int, start, end, width int) {
    path := []int{end}
    for z := end; z != start; z = prev[z] {
        path = append(path, prev[z])
    }
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    for i := 1; i < len(path); i++ {
        fmt.Printf("Pull lever %d:\n", graph[path[i-1]].levers[path[i]]+1)
        fmt.Println(formatState(path[i], width))
    }
}

// Simplified Dijkstra's algorithm
// https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode
func search(graph []node, start, end int) map[int]int {
    q := []int{start}
    prev := map[int]int{}
    dist := map[int]int{}
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        if u == end {
            return prev
        }
        for _, v := range graph[u].neighbours {
            alt := dist[u] + 1
            if i, ok := dist[v]; !ok || alt < i {
                prev[v] = u
                dist[v] = alt
                q = append(q, v)
            }
        }
    }
    return nil
}

func initGraph(levers []int) []node {
    var graph = make([]node, 1<<len(levers))
    for i := 0; i < len(graph); i++ {
        graph[i].state = i
        graph[i].levers = make(map[int]int)
        for j := 0; j < len(levers); j++ {
            n := i ^ levers[j]
            graph[i].neighbours = append(graph[i].neighbours, n)
            graph[i].levers[n] = j
        }
    }
    return graph
}

func main() {
    // This can come from an external input, but let's not overcomplicate:
    var levers = []int{
        0b001011, // lever one flips levers one, two and four
        0b000011, // lever two flips levers one, and two
        0b100100, // lever three flips levers three, two and six
        0b011001, // lever four flips levers one, four and five
        0b111000, // lever five flips levers four, five and six
        0b110100, // lever six flips levers three, five and six
    }
    width := len(levers)
    graph := initGraph(levers)
    start := 0b011111
    end := 0b111111
    fmt.Printf("Starting poisition:\n%s\n", formatState(start, width))
    fmt.Printf("Goal poisition:\n%s\n", formatState(end, width))
    prev := search(graph, start, end)
    if prev != nil {
        printSolution(graph, prev, start, end, width)
    } else {
        fmt.Println("Solution not found")
    }
}

程序输出：

Starting poisition:
1 - up; 2 - up; 3 - up; 4 - up; 5 - up; 6 - down
Goal poisition:
1 - up; 2 - up; 3 - up; 4 - up; 5 - up; 6 - up
Pull lever 1:
1 - down; 2 - down; 3 - up; 4 - down; 5 - up; 6 - down
Pull lever 2:
1 - up; 2 - up; 3 - up; 4 - down; 5 - up; 6 - down
Pull lever 3:
1 - up; 2 - up; 3 - down; 4 - down; 5 - up; 6 - up
Pull lever 5:
1 - up; 2 - up; 3 - down; 4 - up; 5 - down; 6 - down
Pull lever 6:
1 - up; 2 - up; 3 - up; 4 - up; 5 - up; 6 - up

Answer 1

prev := map[int]int{}

使用var和make (而不是空映射的简写声明)可能更符合习惯吗？您通常会使用速记声明来分配初始值，并使用var初始化为零值。

你这样做是在initGraph。在您的代码中保持这一点的一致性可能会更好。