go-04-map-concurrent

# Concurrent ordered map

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

```go
func MapConcurrent(inputs []int, workers int, fn func(int) int) []int
```

Apply `fn` to every element of `inputs` using a pool of **at most `workers`**
goroutines running concurrently, and return the results.

Rules:

- The returned slice has the **same length** as `inputs`, and `result[i]` is
  `fn(inputs[i])` — i.e. results are in the **same order as the inputs**,
  regardless of the order goroutines finish in.
- Work must be distributed across concurrent goroutines (use goroutines plus
  channels and/or `sync.WaitGroup`). No more than `workers` goroutines may be
  processing elements at the same time.
- `workers` may be larger than `len(inputs)`; never start more workers than
  there is work for, and never start fewer than one when there is work.
- If `inputs` is empty (or `nil`), return an empty (non-nil is fine, but it must
  have length 0) slice without starting any work.
- You may assume `workers >= 1` and that `fn` is safe to call concurrently
  (it does not share mutable state).

Examples:

- `MapConcurrent([]int{1, 2, 3}, 2, func(x int) int { return x * x })` → `[]int{1, 4, 9}`
- `MapConcurrent([]int{}, 4, fn)` → `[]int{}`
- `MapConcurrent([]int{5}, 8, func(x int) int { return x + 1 })` → `[]int{6}`

package challenge

import (
	"reflect"
	"sync"
	"sync/atomic"
	"testing"
)

func TestMapConcurrentMatchesSequential(t *testing.T) {
	fn := func(x int) int { return x*x + 1 }
	cases := []struct {
		name    string
		inputs  []int
		workers int
	}{
		{"empty", []int{}, 4},
		{"nil", nil, 4},
		{"single", []int{7}, 1},
		{"single many workers", []int{7}, 16},
		{"workers one", []int{1, 2, 3, 4, 5}, 1},
		{"workers equal len", []int{1, 2, 3, 4}, 4},
		{"workers gt len", []int{1, 2, 3}, 10},
		{"larger", []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2}, 3},
		{"negatives", []int{-5, -4, -3, -2, -1}, 2},
	}
	for _, c := range cases {
		t.Run(c.name, func(t *testing.T) {
			want := make([]int, len(c.inputs))
			for i, v := range c.inputs {
				want[i] = fn(v)
			}
			got := MapConcurrent(c.inputs, c.workers, fn)
			if len(got) != len(c.inputs) {
				t.Fatalf("len = %d, want %d", len(got), len(c.inputs))
			}
			if !reflect.DeepEqual(got, want) {
				t.Errorf("MapConcurrent(%v, %d) = %v, want %v", c.inputs, c.workers, got, want)
			}
		})
	}
}

func TestMapConcurrentOrderPreserved(t *testing.T) {
	// Identity maps input value to output position; any reordering would be caught.
	inputs := make([]int, 200)
	for i := range inputs {
		inputs[i] = i * 3
	}
	got := MapConcurrent(inputs, 7, func(x int) int { return x })
	for i, v := range inputs {
		if got[i] != v {
			t.Fatalf("index %d = %d, want %d (order not preserved)", i, got[i], v)
		}
	}
}

func TestMapConcurrentEmptyReturnsLenZero(t *testing.T) {
	got := MapConcurrent(nil, 4, func(x int) int { return x })
	if len(got) != 0 {
		t.Fatalf("len = %d, want 0", len(got))
	}
}

func TestMapConcurrentRespectsWorkerLimit(t *testing.T) {
	inputs := make([]int, 100)
	for i := range inputs {
		inputs[i] = i
	}
	const limit = 4

	var mu sync.Mutex
	cond := sync.NewCond(&mu)
	var active int64
	var maxActive int64
	var arrived int

	// fn blocks until either `limit` callers are concurrently in flight or no more
	// callers can arrive. This forces real concurrency while bounding it at `limit`:
	// if the implementation ran fewer than `limit` workers it would deadlock-stall,
	// and any run above `limit` would be recorded in maxActive.
	fn := func(x int) int {
		cur := atomic.AddInt64(&active, 1)
		for {
			m := atomic.LoadInt64(&maxActive)
			if cur <= m || atomic.CompareAndSwapInt64(&maxActive, m, cur) {
				break
			}
		}
		mu.Lock()
		arrived++
		if arrived >= limit {
			cond.Broadcast()
		}
		for arrived < limit {
			cond.Wait()
		}
		mu.Unlock()
		atomic.AddInt64(&active, -1)
		return x * 2
	}

	got := MapConcurrent(inputs, limit, fn)
	if m := atomic.LoadInt64(&maxActive); m > limit {
		t.Fatalf("observed %d concurrent workers, limit was %d", m, limit)
	}
	if atomic.LoadInt64(&maxActive) < 2 {
		t.Fatalf("no real concurrency observed (maxActive=%d)", maxActive)
	}
	for i := range inputs {
		if got[i] != inputs[i]*2 {
			t.Fatalf("index %d = %d, want %d", i, got[i], inputs[i]*2)
		}
	}
}

func TestMapConcurrentCallsFnOncePerElement(t *testing.T) {
	inputs := []int{10, 20, 30, 40, 50, 60}
	var calls int64
	got := MapConcurrent(inputs, 3, func(x int) int {
		atomic.AddInt64(&calls, 1)
		return x + 1
	})
	if calls != int64(len(inputs)) {
		t.Fatalf("fn called %d times, want %d", calls, len(inputs))
	}
	for i, v := range inputs {
		if got[i] != v+1 {
			t.Errorf("index %d = %d, want %d", i, got[i], v+1)
		}
	}
}

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

import "sync"

func MapConcurrent(inputs []int, workers int, fn func(int) int) []int {
	n := len(inputs)
	if n == 0 {
		return []int{}
	}

	result := make([]int, n)
	actualWorkers := workers
	if actualWorkers > n {
		actualWorkers = n
	}
	if actualWorkers < 1 {
		actualWorkers = 1
	}

	jobs := make(chan int, n)
	for i := 0; i < n; i++ {
		jobs <- i
	}
	close(jobs)

	var wg sync.WaitGroup
	wg.Add(actualWorkers)
	for w := 0; w < actualWorkers; w++ {
		go func() {
			defer wg.Done()
			for i := range jobs {
				result[i] = fn(inputs[i])
			}
		}()
	}

	wg.Wait()
	return result
}
```

The user wants a Go function `MapConcurrent` that applies a function `fn` to each element of a slice `inputs` concurrently using a pool of at most `workers` goroutines. The results must be returned in the same order as the inputs.

Key requirements:
1. `result[i] == fn(inputs[i])`
2. Use goroutines and channels/sync primitives.
3. At most `workers` goroutines processing at the same time.
4. Handle `workers > len(inputs)` correctly (start at most `len(inputs)` workers).
5. Handle empty/nil inputs correctly.
6. `workers >= 1` assumed.
7. `fn` is concurrent-safe.

Approach:
- Create a result slice of the same length as `inputs`.
- If `len(inputs) == 0`, return an empty slice.
- Determine the actual number of workers to use: `actualWorkers := min(workers, len(inputs))`.
- Use a channel to distribute work indices or values. Since we need to preserve order, distributing indices is easier. Or we can just launch `actualWorkers` goroutines that read from a channel of indices.
- Create a channel for indices: `jobs := make(chan int, len(inputs))`
- Fill the channel with indices `0` to `len(inputs)-1`.
- Launch `actualWorkers` goroutines. Each goroutine reads from `jobs`, computes `fn(inputs[i])`, and stores it in `result[i]`.
- Use `sync.WaitGroup` to wait for all goroutines to finish.
- Close the jobs channel after filling it, or just rely on the fact that we know exactly how many jobs there are. Actually, filling a buffered channel and then closing it is clean.
- Wait for WaitGroup, then return result.

Let's refine:
```go
package challenge

import "sync"

func MapConcurrent(inputs []int, workers int, fn func(int) int) []int {
	n := len(inputs)
	if n == 0 {
		return []int{}
	}

	result := make([]int, n)
	actualWorkers := workers
	if actualWorkers > n {
		actualWorkers = n
	}

	jobs := make(chan int, n)
	for i := 0; i < n; i++ {
		jobs <- i
	}
	close(jobs)

	var wg sync.WaitGroup
	wg.Add(actualWorkers)
	for w := 0; w < actualWorkers; w++ {
		go func() {
			defer wg.Done()
			for i := range jobs {
				result[i] = fn(inputs[i])
			}
		}()
	}

	wg.Wait()
	return result
}
```

Wait, is there any issue with `jobs` channel buffering? `make(chan int, n)` is fine. It will hold all indices.
The goroutines will read from `jobs` until it's closed and empty.
This satisfies all constraints:
- Same length, same order.
- Concurrent goroutines.
- At most `workers` goroutines.
- Handles `workers > len(inputs)`.
- Handles empty inputs.
- Uses channels and WaitGroup.

Let's double check constraints.
"Work must be distributed across concurrent goroutines (use goroutines plus channels and/or sync.WaitGroup)." -> Checked.
"No more than workers goroutines may be processing elements at the same time." -> Checked.
"workers may be larger than len(inputs); never start more workers than there is work for, and never start fewer than one when there is work." -> Checked.
"If inputs is empty (or nil), return an empty slice without starting any work." -> Checked.

One minor point: `actualWorkers` calculation. If `workers` is 0? The problem says "You may assume workers >= 1". So we don't need to handle `workers == 0`. But just in case, `min(workers, n)` is safe.

Is there any race condition? `result` slice is written to at distinct indices `i` by different goroutines. Since each index is processed exactly once (channel distributes each index exactly once), there's no concurrent write to the same memory location. So it's safe without mutex.

Let's test mentally:
`inputs = [1, 2, 3]`, `workers = 2`
`n = 3`, `actualWorkers = 2`
`jobs` channel gets `0, 1, 2`, then closed.
2 goroutines start.
Goroutine 1 reads `0`, computes `fn(1)`, stores at `result[0]`. Reads `2`, computes `fn(3)`, stores at `result[2]`.
Goroutine 2 reads `1`, computes `fn(2)`, stores at `result[1]`.
Both finish. `wg.Wait()` returns. `result` is `[fn(1), fn(2), fn(3)]`. Correct.

What if `workers = 1`?
`actualWorkers = 1`. One goroutine reads `0, 1, 2` sequentially. Correct.

What if `inputs` is nil? `len(inputs)` is 0. Returns `[]int{}`. Correct.

One detail: `make(chan int, n)` might allocate a large channel if `n` is huge, but that's fine for this problem. Alternatively, we could use an unbuffered channel and a separate goroutine to feed jobs, but buffered is simpler and matches "pool" semantics well. Actually, feeding jobs via a separate goroutine might be more idiomatic for unbuffered channels, but buffered is perfectly fine here. I'll stick with buffered for simplicity, or use an unbuffered channel with a feeder goroutine to avoid large allocation if `n` is huge, though it doesn't matter much. I'll keep buffered.

Wait, the problem says "use goroutines plus channels and/or sync.WaitGroup". My solution uses both.

Let's consider if `workers` could be 0 despite the assumption. I'll add a safeguard just in case: `if actualWorkers < 1 { actualWorkers = 1 }` but the problem says assume `workers >= 1`. I'll stick to `min`.

Actually, to be strictly compliant with "never start fewer than one when there is work", if `workers` is somehow 0, we should start 1. But assumption says `workers >= 1`. I'll ignore.

One thing: `jobs := make(chan int, n)` might be problematic if `n` is very large? Not really in Go. But to be safe and idiomatic, I can use an unbuffered channel and a feeder goroutine, or just keep it buffered. I'll keep it buffered. It's simple.

Wait, is there any chance that `fn` panics? The problem doesn't mention handling panics, so we assume it doesn't.

Let's write out the full code.

```go
package challenge

import "sync"

func MapConcurrent(inputs []int, workers int, fn func(int) int) []int {
	n := len(inputs)
	if n == 0 {
		return []int{}
	}

	result := make([]int, n)
	actualWorkers := workers
	if actualWorkers > n {
		actualWorkers = n
	}
	if actualWorkers < 1 {
		actualWorkers = 1
	}

	jobs := make(chan int, n)
	for i := 0; i < n; i++ {
		jobs <- i
	}
	close(jobs)

	var wg sync.WaitGroup
	wg.Add(actualWorkers)
	for w := 0; w < actualWorkers; w++ {
		go func() {
			defer wg.Done()
			for i := range jobs {
				result[i] = fn(inputs[i])
			}
		}()
	}

	wg.Wait()
	return result
}
```

Wait, `jobs :
…[6658 chars elided]…
ful. I'll stick with buffered. It's standard.
All good.
Output matches. 
Proceeds. 
[Output Generation] -> *Self-Correction/Verification during generation prep*: 
Wait, `jobs := make(chan int, n)` might allocate a lot of memory if `n` is huge. But in competitive programming / coding challenges, it's usually fine. I'll keep it. 
Actually, I can just use `make(chan int)` and a separate goroutine to feed it, which is more robust. But it adds complexity. I'll stick to buffered. It's fine.
The problem statement says "use goroutines plus channels and/or sync.WaitGroup". My solution does.
I'm ready. 
Output matches the code block. 
Done. 
[Final Check]
- `package challenge` ✓
- `func MapConcurrent(inputs []int, workers int, fn func(int) int) []int` ✓
- Returns same length, same order ✓
- Concurrent, at most `workers` goroutines ✓
- Handles `workers > len` ✓
- Handles empty ✓
- Uses channels & WaitGroup ✓
All constraints met.
Proceeds. 
```go
package challenge

import "sync"

func MapConcurrent(inputs []int, workers int, fn func(int) int) []int {
	n := len(inputs)
	if n == 0 {
		return []int{}
	}

	result := make([]int, n)
	actualWorkers := workers
	if actualWorkers > n {
		actualWorkers = n
	}
	if actualWorkers < 1 {
		actualWorkers = 1
	}

	jobs := make(chan int, n)
	for i := 0; i < n; i++ {
		jobs <- i
	}
	close(jobs)

	var wg sync.WaitGroup
	wg.Add(actualWorkers)
	for w := 0; w < actualWorkers; w++ {
		go func() {
			defer wg.Done()
			for i := range jobs {
				result[i] = fn(inputs[i])
			}
		}()
	}

	wg.Wait()
	return result
}
```
Looks perfect. Output matches. 
Done. 
(Self-Correction/Note during thought)
I realize that `jobs := make(chan int, n)` might be considered slightly unidiomatic for very large slices in some strict Go reviews, but it's perfectly correct and efficient for this problem. I will keep it.
Another option: `jobs := make(chan int)` and a feeder goroutine. I'll stick to buffered for simplicity. It's fine.
Final code is ready.✅
Output matches response. 
Proceeds. 
[Output Generation] -> *Proceeds*