go-01-unique

# Unique preserving order

Implement **`solution.go`** in `package challenge` exporting:

```go
func Unique(xs []int) []int
```

Return a new slice containing the elements of `xs` with duplicates removed, keeping each value at
the position of its **first occurrence**.

Rules:

- Preserve **first-occurrence order** — do not sort the result.
- Each distinct value appears exactly once.
- Do **not** mutate the input slice.
- For an empty (or nil) input, return an **empty, non-nil** slice (length 0).

Examples:

```go
Unique([]int{3, 1, 3, 2, 1}) // => [3, 1, 2]
Unique([]int{1, 2, 3})       // => [1, 2, 3]
Unique([]int{5, 5, 5})       // => [5]
Unique([]int{})              // => [] (non-nil, length 0)
```

package challenge

import (
	"reflect"
	"testing"
)

func TestUnique(t *testing.T) {
	cases := []struct {
		name string
		in   []int
		want []int
	}{
		{"removes duplicates preserving order", []int{3, 1, 3, 2, 1}, []int{3, 1, 2}},
		{"already unique unchanged", []int{1, 2, 3}, []int{1, 2, 3}},
		{"all same collapses to one", []int{5, 5, 5}, []int{5}},
		{"empty returns empty", []int{}, []int{}},
		{"single element", []int{42}, []int{42}},
		{"negatives and zero", []int{0, -1, 0, -1, 2}, []int{0, -1, 2}},
	}
	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			got := Unique(tc.in)
			if !reflect.DeepEqual(got, tc.want) {
				t.Errorf("Unique(%v) = %v, want %v", tc.in, got, tc.want)
			}
		})
	}
}

func TestUniqueReturnsNonNil(t *testing.T) {
	if Unique([]int{}) == nil {
		t.Error("Unique should return a non-nil slice for empty input")
	}
	if Unique(nil) == nil {
		t.Error("Unique should return a non-nil slice for nil input")
	}
}

func TestUniqueDoesNotMutateInput(t *testing.T) {
	in := []int{1, 1, 2}
	_ = Unique(in)
	if !reflect.DeepEqual(in, []int{1, 1, 2}) {
		t.Errorf("input was mutated: got %v", in)
	}
}

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```go
package challenge

func Unique(xs []int) []int {
	seen := make(map[int]struct{})
	result := make([]int, 0, len(xs))
	for _, x := range xs {
		if _, ok := seen[x]; !ok {
			seen[x] = struct{}{}
			result = append(result, x)
		}
	}
	return result
}
```

The user wants a Go function `Unique(xs []int) []int` that removes duplicates from a slice of integers while preserving the order of first occurrence.
Constraints:
- Preserve first-occurrence order.
- Each distinct value appears exactly once.
- Do not mutate the input slice.
- Return empty, non-nil slice for empty/nil input.

Implementation details:
- Use a map to keep track of seen elements.
- Iterate over the input slice.
- If an element hasn't been seen, append it to the result slice and mark it as seen.
- Return the result slice.
- Handle nil/empty input correctly (the loop won't execute, result will be initialized as `make([]int, 0)` or `[]int{}`, which is non-nil and length 0).

Let's write it out:
```go
package challenge

func Unique(xs []int) []int {
    seen := make(map[int]struct{})
    result := make([]int, 0, len(xs))
    for _, x := range xs {
        if _, ok := seen[x]; !ok {
            seen[x] = struct{}{}
            result = append(result, x)
        }
    }
    return result
}
```

Check constraints:
- Preserve order: yes, iterates in order.
- Each distinct value once: yes, map check.
- Do not mutate input: yes, creates new slice.
- Empty/nil input: `make([]int, 0, 0)` returns non-nil slice of length 0. Loop doesn't run. Returns `result`. Correct.

One minor point: `make([]int, 0, len(xs))` is fine. If `xs` is nil, `len(xs)` is 0, so `make([]int, 0, 0)` works.
The problem says "return an empty, non-nil slice (length 0)". `make([]int, 0)` satisfies this.

Let's verify with examples:
`Unique([]int{3, 1, 3, 2, 1})` -> seen: 3, result: [3]; seen: 3,1, result: [3,1]; seen: 3,1, result: [3,1]; seen: 3,1,2, result: [3,1,2]; seen: 3,1,2, result: [3,1,2]. Returns `[3, 1, 2]`. Correct.
`Unique([]int{1, 2, 3})` -> `[1, 2, 3]`. Correct.
`Unique([]int{5, 5, 5})` -> `[5]`. Correct.
`Unique([]int{})` -> `[]`. Correct.

The code looks solid. I will wrap it in the requested format.
Package name: `challenge`
Function signature: `func Unique(xs []int) []int`

One thing to consider: should I use `[]int{}` or `make([]int, 0)`? Both are fine. `make([]int, 0, len(xs))` is slightly more efficient for capacity.

I'll produce the final code.
No extra prose.
Code block with `solution.go`.
Done. 
Let's double check the exact prompt: "Implement **`solution.go`** in `package challenge` exporting: `func Unique(xs []int) []int`"
All good.
Output matches requirements.
Proceed. 
Self-Correction/Verification during thought:
- Does `make([]int, 0, len(xs))` work when `xs` is nil? Yes, `len(nil)` is 0 in Go.
- Is `struct{}{}` the best for map values? Yes, zero allocation.
- Could use `map[int]bool` but `struct{}{}` is idiomatic.
- The prompt says "Do not mutate the input slice." - we are not mutating it.
- "For an empty (or nil) input, return an empty, non-nil slice (length 0)." - `make([]int, 0)` returns a non-nil slice with length 0.

Everything is correct.
Output matches.
Proceeding. 
Generating response. 
```go
package challenge

func Unique(xs []int) []int {
	seen := make(map[int]struct{})
	result := make([]int, 0, len(xs))
	for _, x := range xs {
		if _, ok := seen[x]; !ok {
			seen[x] = struct{}{}
			result = append(result, x)
		}
	}
	return result
}
```
Looks good. I will present it exactly as requested.
All constraints met.
Ready. 
Output matches response. 
Proceeds. 
[Done]