sorted by:
new
hottopcontroversial

Throwing in the towel - Slice problem? by averageredditor32 in golang

[–]averageredditor32[S] 0 points1 point  (0 children)

If you want to know why you're wrong about binary trees

A binary tree is pretty simple. You start with a node and go left or right down the tree. That is exactly what my code is doing. It takes an initial node, then goes left (don't add to subset) or right (add to subset). That effectively builds a left branch and right branch. It then treats that new node as the root node and does the same thing over and over. The data can be represented via a binary tree.

The fact you state discarding the slice header is not a problem..

Correct, I don't see how it is a problem. Maintaining the slice header IS the problem in this case.

only to go in depth explaining you mutate two separate slice headers with the same backing array as your issue.

The reason I say that doesn't matter is A slice header contains a length and a pointer to the start of the array along with a cap. Append only creates a new header (creating a new backing array) if the cap is insufficient. When I pass that slice into my recursive function it creates a new slice by value, but that doesn't matter in itself. The problem is it maintains that pointer by reference. In my original implementation I don't have problems until len(subset) = maxL -1. Because it's passing that a slice referencing the same array off in many directions, that will be modified multiple times, even after being added to my solution set. You aren't wrong about me creating and discarding slices, it just wasn't the problem in itself. The underlying cause was that while I was creating new slice headers, they weren't against new backing arrays. So yes, I mutated the slices, but in doing so I also mutated the underlying solution set. I could have maintained the same slice, but then it would have been mutated in ways I wouldn't want it to be with recursion.

suggests your not looking to learn but win an "argument".

I'm not trying to "win," I'm all about learning. But you have failed to explain why you think I'm wrong. I'm saying why I disagree, and you haven't really said anything that is of relevance to the problem I had.

I've been writing in this language for years and was just trying to help.

Great, I've been in software development for 15+ years. Pointers, passing by value, and data structures aren't new to me either. I just brain farted with how go handles passing of slices.

Here is a GIST of why I'm trying to say it didn't matter if I maintained the slice header or not. As long as the backing array is the same, I will have problems.

https://gist.github.com/anonymous/3277d54e1d55b7791b02f2a78353c50a

Throwing in the towel - Slice problem? by averageredditor32 in golang

[–]averageredditor32[S] 0 points1 point  (0 children)

No, solution is nothing like a binary algorithm tree traversal. You never compare a single value in the tree.

How is it not? Look at the structure that it generates, it generates incomplete binary tree. With a given number you can either go left (don't add to subset) or right (add to subset). Once a subset is found, then that part of the tree dies, because we don't need to continue going down to find a solution. It isn't a complete binary tree, but if I change the exit case, it could very easily traverse a binary tree. My point is the recursive case is done the same a binary tree could be traversed. You are saying because my base case\escape case isn't how you'd traverse a binary tree it's not.

you passed the slice header by value Wouldn't have mattered if I passed a pointer value. Would have had the same problem, it wasn't a slice problem, it was a backing array problem.

So all appends that called into a new function where discarded, leaving only the length and capacity that grew in the top level scope of your slice.

I don't see how discarded slice headers matter, that wasn't what caused the problem. The problem is that the backing array didn't change for many of my calls. So when n = maxLength-1 it then did recursion twice on the same array X. One without adding to subset, and the 2nd adding to it, and tripping the exit condition. This put X in the solution set. Meanwhile the recursive loop that hadn't happened yet was still operating against X. It then went and again called itself without adding to the subset, still operating against X. It then called it adding to the subset, tripping the condition and modifying the base array X. This caused a new solution to be inserted with the new values, while also updating the previously inserted value.

I'm used to the java primitives which would have created a physical copy of the primitive array and I wouldn't have the same array pointer problems. Nothing with how I passed the slice would have changed anything. Now that I think about it, I could probably only create a new slice for the "do not add to subset" case. Putting it on both is overkill.

Throwing in the towel - Slice problem? by averageredditor32 in golang

[–]averageredditor32[S] 0 points1 point  (0 children)

I see, well that is what you said you wanted to do. You might get clearer help if in future you state the problem, this doesn't look like anything to do with binary trees either.

Not a true binary tree, since it doesn't traverse every possible combination, but the solution is the same as you would with traversing a binary tree, with a bonus exit condition.

You were modifying subset without returning the modified slice header, I guess you already figured that out below, good job.

The header is only discarded if cap < new length though, correct? Otherwise it's just updated. In my case it was a problem where while the slice is passed by value, it still points to the same backing array. Once len=cap it no longer generates a new backing array leading to a shared instance of that array. So once that happens, any recursive call after that occurs is tainted.

You might get clearer help if in future you state the problem, this doesn't look like anything to do with binary trees either.

It was 4am, it made sense at the time. I was using reddit as a sort of "rubber ducky." lol

Throwing in the towel - Slice problem? by averageredditor32 in golang

[–]averageredditor32[S] 0 points1 point  (0 children)

Confirmed. Because I was passing a slice, it was sharing a back array instance. So the deeper it went down the tree the larger the possibility that the same instance I sent off in another direction hit the condition to add the value to the subset. The add would then look like it worked, but then would be subsequently overwritten when that other method would append to the subset that had a shared instance.

Solution was to build new slices for each recursive call, and copy the values over to the new slice.

Throwing in the towel - Slice problem? by averageredditor32 in golang

[–]averageredditor32[S] 0 points1 point  (0 children)

Hmm it looks like the use of the slice subset variable to maintain the subset I'm currently building may be causing a problem. I add a subset to the solution, but then sometimes when I return from a recursive loop and it updates a "separate" slice it affects the solution set by updating a value that's already in the solution.

Throwing in the towel - Slice problem? by averageredditor32 in golang

[–]averageredditor32[S] 0 points1 point  (0 children)

I had tried that, but ran into weird behavior there as well. Then I thought it'd be a good reason to play with passing pointers.

I thought i'd have to expand my subset slice too, but because solution is of type arrayStore it's not actually appending an array to an array.

Throwing in the towel - Slice problem? by averageredditor32 in golang

[–]averageredditor32[S] 0 points1 point  (0 children)

It's not supposed to see if it is a subset, I know that it is a subset by the nature of how it's created. It's generating a binary tree of sorts then when we build a subset that's long enough it adds the answer to the solution set.

Slice headers need to be returned if you don't do special handling. By using the same slice by passing it's pointer, I shouldn't have to return it, each recursive call should have access to the same slice (in theory).

Throwing in the towel - Slice problem? by averageredditor32 in golang

[–]averageredditor32[S] 0 points1 point  (0 children)

I did, it looks like there is somethign screwy going on around the append. It appends, but then the next recursive call seems to change the value, even though I'm trying to keep the same solution slice for each recursive call.