CODEWITHSUNDEEP
go
user10826273
user10826273

Reputation:

When is the slice element covered in this code?

I logged every element before I appending it. But the result looks like that some element is covered.

I do not know when it is covered.

package main

import "fmt"

func main() {
    graph := [][]int{
        []int{3, 1},
        []int{4, 6, 7, 2, 5},
        []int{4, 6, 3},
        []int{6, 4},
        []int{7, 6, 5},
        []int{6},
        []int{7},
        []int{},
    }

    fmt.Println(allPathsSourceTarget(graph))
}

func allPathsSourceTarget(graph [][]int) [][]int {
    n := len(graph) - 1
    result := make([][]int, 0, 200)

    var pathRecord func(target, path []int)
    pathRecord = func(target, path []int) {
        if (len(target) == 0) && (path[len(path)-1] == n) {
            fmt.Println("insert into", path) // should end with 7
            result = append(result, path)
        }

        for _, v := range target {
            pathRecord(graph[v], append(path, v))
        }
    }

    for _, v := range graph[0] {
        pathRecord(graph[v], []int{0, v})
    }

    return result
}

Every element in the result should end with 7.

Upvotes: 1

Views: 60

Answers (2)

Vorsprung
Vorsprung

Reputation: 34337

This works for me. I assume it's weirdness with append and slices

I assume that the memory backing "this append" is passed into the recursive function as the slice is acting something like a pointer

Then the next time it's the same memory so it gets overwritten

So you need to take a copy at each recursion to stop it overwriting 

pathRecord = func(target, path []int) {
    if (len(target) == 0) && (path[len(path)-1] == n) {
        var c []int = make([]int, len(path))
        copy(c, path)
        //fmt.Println("insert into", payload) // should end with 7
        result = append(result, c)
    }

    for _, v := range target {
        pathRecord(graph[v], append(path, v)) //this append
    }
}

Upvotes: 2

Roee Gavirel
Roee Gavirel

Reputation: 19445

You issue is with this line:

pathRecord(graph[v], append(path, v))

Go is so "smart" so he's trying to reuse the same slice allocated memory and you actually change the path you already added to result. ):

try this instead:

newPath = make([]int, len(path))
copy(newPath, path)
pathRecord(graph[v], append(newPath, v))

Upvotes: 2

Related Questions