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 {
	if len(inputs) == 0 {
		return []int{}
	}

	result := make([]int, len(inputs))

	// Determine actual number of workers: at most workers, at most len(inputs), at least 1
	actualWorkers := workers
	if actualWorkers > len(inputs) {
		actualWorkers = len(inputs)
	}
	if actualWorkers < 1 {
		actualWorkers = 1
	}

	type job struct {
		index int
		value int
	}

	jobs := make(chan job, len(inputs))
	var wg sync.WaitGroup

	// Start worker goroutines
	for i := 0; i < actualWorkers; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for j := range jobs {
				result[j.index] = fn(j.value)
			}
		}()
	}

	// Send all jobs
	for i, v := range inputs {
		jobs <- job{index: i, value: v}
	}
	close(jobs)

	// Wait for all workers to complete
	wg.Wait()

	return result
}
```

The user wants me to implement a concurrent ordered map function in Go. Let me break down the requirements:

1. Function signature: `func MapConcurrent(inputs []int, workers int, fn func(int) int) []int`
2. Apply `fn` to every element using at most `workers` goroutines
3. Results must be in the same order as inputs
4. Use goroutines + channels and/or sync.WaitGroup
5. Never start more workers than there is work, never fewer than 1 when there is work
6. Empty/nil inputs → return empty slice, no work started
7. workers >= 1, fn is concurrent-safe

My approach:
- Handle empty inputs case first
- Create result slice of same length as inputs
- Determine actual number of workers: min(workers, len(inputs))
- Use a worker pool pattern:
  - Create a channel for jobs (index + value pairs)
  - Start worker goroutines
  - Each worker reads from jobs channel, applies fn, writes result to result slice at the correct index
  - Use WaitGroup to wait for all workers to finish
  - Close jobs channel when all jobs are sent

Let me write this:

```go
package challenge

import "sync"

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

    result := make([]int, len(inputs))
    
    // Determine actual number of workers
    actualWorkers := workers
    if actualWorkers > len(inputs) {
        actualWorkers = len(inputs)
    }
    if actualWorkers < 1 {
        actualWorkers = 1
    }

    type job struct {
        index int
        value int
    }

    jobs := make(chan job, len(inputs))
    var wg sync.WaitGroup

    // Start workers
    for i := 0; i < actualWorkers; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for j := range jobs {
                result[j.index] = fn(j.value)
            }
        }()
    }

    // Send jobs
    for i, v := range inputs {
        jobs <- job{index: i, value: v}
    }
    close(jobs)

    // Wait for all workers to finish
    wg.Wait()

    return result
}
```

This looks correct. Let me verify against the requirements:
- Same length as inputs ✓
- result[i] = fn(inputs[i]) ✓ (we store at the correct index)
- At most workers goroutines ✓
- Workers <= len(inputs) when there's work ✓
- Never fewer than 1 when there is work ✓
- Empty inputs returns empty slice ✓
- Uses goroutines + channels + WaitGroup ✓

This should work correctly.