go-05-lru-cache

# Generic LRU cache

Implement **`solution.go`** in `package challenge` exporting a generic
least-recently-used cache:

```go
type LRUCache[K comparable, V any] struct { /* unexported fields */ }

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V]

func (c *LRUCache[K, V]) Get(key K) (V, bool)
func (c *LRUCache[K, V]) Put(key K, value V)
func (c *LRUCache[K, V]) Len() int
```

Behavior:

- `NewLRUCache(capacity)` creates an empty cache that holds at most `capacity`
  entries. If `capacity <= 0`, treat it as `0`: the cache stores nothing and
  `Len()` is always `0`.
- `Get(key)` returns the stored value and `true` if `key` is present, or the
  zero value of `V` and `false` otherwise. A successful `Get` counts as a
  **use**, making `key` the most-recently-used entry.
- `Put(key, value)` inserts or updates `key`. Inserting or updating makes `key`
  the most-recently-used entry. If adding a **new** key would exceed `capacity`,
  the **least-recently-used** entry is evicted first. Updating the value of an
  existing key never evicts anything.
- `Len()` returns the current number of stored entries.
- Works for any `comparable` key type and any value type (e.g. `string`/`int`
  keys, struct or pointer values).

Examples:

```go
c := NewLRUCache[string, int](2)
c.Put("a", 1)
c.Put("b", 2)
c.Get("a")        // (1, true); now "b" is least-recently-used
c.Put("c", 3)     // evicts "b"
c.Get("b")        // (0, false)
c.Len()           // 2
```

package challenge

import "testing"

func TestLRUBasicGetPut(t *testing.T) {
	c := NewLRUCache[string, int](2)
	if _, ok := c.Get("missing"); ok {
		t.Fatalf("Get on empty cache returned ok=true")
	}
	c.Put("a", 1)
	c.Put("b", 2)
	if v, ok := c.Get("a"); !ok || v != 1 {
		t.Fatalf("Get(a) = (%d, %v), want (1, true)", v, ok)
	}
	if v, ok := c.Get("b"); !ok || v != 2 {
		t.Fatalf("Get(b) = (%d, %v), want (2, true)", v, ok)
	}
	if c.Len() != 2 {
		t.Fatalf("Len = %d, want 2", c.Len())
	}
}

func TestLRUZeroValueOnMiss(t *testing.T) {
	c := NewLRUCache[int, string](2)
	if v, ok := c.Get(99); ok || v != "" {
		t.Fatalf("Get(miss) = (%q, %v), want (\"\", false)", v, ok)
	}
}

func TestLRUEvictsLeastRecentlyUsed(t *testing.T) {
	c := NewLRUCache[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Put("c", 3) // capacity 2: "a" is LRU, evicted
	if _, ok := c.Get("a"); ok {
		t.Fatalf("expected a to be evicted")
	}
	if v, ok := c.Get("b"); !ok || v != 2 {
		t.Fatalf("Get(b) = (%d, %v), want (2, true)", v, ok)
	}
	if v, ok := c.Get("c"); !ok || v != 3 {
		t.Fatalf("Get(c) = (%d, %v), want (3, true)", v, ok)
	}
	if c.Len() != 2 {
		t.Fatalf("Len = %d, want 2", c.Len())
	}
}

func TestLRUGetCountsAsUse(t *testing.T) {
	c := NewLRUCache[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	if v, ok := c.Get("a"); !ok || v != 1 { // "a" now most-recently-used
		t.Fatalf("Get(a) = (%d, %v), want (1, true)", v, ok)
	}
	c.Put("c", 3) // "b" is LRU now, should be evicted
	if _, ok := c.Get("b"); ok {
		t.Fatalf("expected b to be evicted (Get should have refreshed a)")
	}
	if v, ok := c.Get("a"); !ok || v != 1 {
		t.Fatalf("Get(a) = (%d, %v), want (1, true)", v, ok)
	}
	if v, ok := c.Get("c"); !ok || v != 3 {
		t.Fatalf("Get(c) = (%d, %v), want (3, true)", v, ok)
	}
}

func TestLRUUpdateExistingKey(t *testing.T) {
	c := NewLRUCache[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Put("a", 100) // update value, refresh a; no eviction
	if c.Len() != 2 {
		t.Fatalf("Len = %d, want 2 (update must not evict)", c.Len())
	}
	if v, ok := c.Get("a"); !ok || v != 100 {
		t.Fatalf("Get(a) = (%d, %v), want (100, true)", v, ok)
	}
	c.Put("c", 3) // "b" is LRU, evicted
	if _, ok := c.Get("b"); ok {
		t.Fatalf("expected b to be evicted after updating a then inserting c")
	}
}

func TestLRUUpdateRefreshesRecency(t *testing.T) {
	c := NewLRUCache[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Put("a", 10) // refresh "a" via update => "b" becomes LRU
	c.Put("c", 3)  // evicts "b"
	if _, ok := c.Get("b"); ok {
		t.Fatalf("expected b to be evicted; updating a should refresh its recency")
	}
	if v, ok := c.Get("a"); !ok || v != 10 {
		t.Fatalf("Get(a) = (%d, %v), want (10, true)", v, ok)
	}
}

func TestLRUCapacityOne(t *testing.T) {
	c := NewLRUCache[int, int](1)
	c.Put(1, 10)
	c.Put(2, 20) // evicts 1
	if _, ok := c.Get(1); ok {
		t.Fatalf("expected key 1 evicted in capacity-1 cache")
	}
	if v, ok := c.Get(2); !ok || v != 20 {
		t.Fatalf("Get(2) = (%d, %v), want (20, true)", v, ok)
	}
	if c.Len() != 1 {
		t.Fatalf("Len = %d, want 1", c.Len())
	}
}

func TestLRUZeroCapacity(t *testing.T) {
	c := NewLRUCache[string, int](0)
	c.Put("a", 1)
	if _, ok := c.Get("a"); ok {
		t.Fatalf("zero-capacity cache must store nothing")
	}
	if c.Len() != 0 {
		t.Fatalf("Len = %d, want 0", c.Len())
	}
}

func TestLRUStringValues(t *testing.T) {
	c := NewLRUCache[int, string](3)
	c.Put(1, "one")
	c.Put(2, "two")
	c.Put(3, "three")
	c.Get(1) // refresh 1
	c.Put(4, "four") // evicts 2 (LRU)
	if _, ok := c.Get(2); ok {
		t.Fatalf("expected key 2 evicted")
	}
	for _, want := range []struct {
		k int
		v string
	}{{1, "one"}, {3, "three"}, {4, "four"}} {
		if v, ok := c.Get(want.k); !ok || v != want.v {
			t.Errorf("Get(%d) = (%q, %v), want (%q, true)", want.k, v, ok, want.v)
		}
	}
}

func TestLRUEvictionChain(t *testing.T) {
	c := NewLRUCache[int, int](3)
	for i := 0; i < 6; i++ {
		c.Put(i, i*i)
	}
	// Only the last 3 inserts survive: 3,4,5.
	for _, k := range []int{0, 1, 2} {
		if _, ok := c.Get(k); ok {
			t.Errorf("expected key %d evicted", k)
		}
	}
	for _, k := range []int{3, 4, 5} {
		if v, ok := c.Get(k); !ok || v != k*k {
			t.Errorf("Get(%d) = (%d, %v), want (%d, true)", k, v, ok, k*k)
		}
	}
	if c.Len() != 3 {
		t.Fatalf("Len = %d, want 3", c.Len())
	}
}

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

type node[K comparable, V any] struct {
	key   K
	value V
	prev  *node[K, V]
	next  *node[K, V]
}

type LRUCache[K comparable, V any] struct {
	capacity int
	size     int
	keyToNode map[K]*node[K, V]
	head      *node[K, V]
	tail      *node[K, V]
}

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {
	if capacity <= 0 {
		return &LRUCache[K, V]{
			capacity: 0,
			size:     0,
			keyToNode: make(map[K]*node[K, V]),
		}
	}
	return &LRUCache[K, V]{
		capacity: capacity,
		size:     0,
		keyToNode: make(map[K]*node[K, V]),
	}
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
	if c.capacity == 0 {
		var zero V
		return zero, false
	}

	node, ok := c.keyToNode[key]
	if !ok {
		var zero V
		return zero, false
	}

	c.moveToFront(node)
	return node.value, true
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}

	node, ok := c.keyToNode[key]
	if ok {
		node.value = value
		c.moveToFront(node)
		return
	}

	newNode := &node[K, V]{
		key:   key,
		value: value,
	}
	c.keyToNode[key] = newNode
	c.addToFront(newNode)
	c.size++

	if c.size > c.capacity {
		c.evictLRU()
	}
}

func (c *LRUCache[K, V]) Len() int {
	return c.size
}

func (c *LRUCache[K, V]) addToFront(node *node[K, V]) {
	if c.head == nil {
		c.head = node
		c.tail = node
	} else {
		node.next = c.head
		c.head.prev = node
		c.head = node
	}
}

func (c *LRUCache[K, V]) moveToFront(node *node[K, V]) {
	if node.prev != nil {
		node.prev.next = node.next
	}
	if node.next != nil {
		node.next.prev = node.prev
	}

	if node == c.tail {
		c.tail = node.prev
	}

	if node == c.head {
		c.head = node.next
	}

	node.prev = nil
	node.next = c.head
	if c.head != nil {
		c.head.prev = node
	}
	c.head = node
}

func (c *LRUCache[K, V]) evictLRU() {
	if c.tail == nil {
		return
	}

	node := c.tail
	delete(c.keyToNode, node.key)
	c.removeNode(node)
	c.size--
}

func (c *LRUCache[K, V]) removeNode(node *node[K, V]) {
	if node.prev != nil {
		node.prev.next = node.next
	} else {
		c.head = node.next
	}

	if node.next != nil {
		node.next.prev = node.prev
	} else {
		c.tail = node.prev
	}
}
```

The task is to implement a generic LRU (Least Recently Used) cache in Go. Let me break down the requirements:

1. Generic type `LRUCache[K comparable, V any]`
2. Constructor `NewLRUCache[K comparable, V any](capacity int)` - capacity <= 0 means 0 capacity
3. `Get(key K) (V, bool)` - returns value and true if exists, updates LRU order on successful get
4. `Put(key K, value V)` - inserts or updates, updates LRU order, evicts LRU if capacity exceeded
5. `Len() int` - returns current number of entries

For an LRU cache, I need to:
1. Track which keys are in the cache
2. Track the order of usage (most recent to least recent)
3. When capacity is exceeded, remove the least recently used entry

Common approaches:
- Use a map for O(1) key lookup
- Use a doubly linked list to maintain order (most recent at head, least recent at tail)
- When accessing/inserting, move the node to the head
- When evicting, remove from tail

Let me implement this:

```go
package challenge

import (
	"sync"
)

type LRUCache[K comparable, V any] struct {
	capacity int
	size     int
	keyToNode map[K]*node[K, V]
	head *node[K, V]
	tail *node[K, V]
}

type node[K comparable, V any] struct {
	key K
	value V
	prev *node[K, V]
	next *node[K, V]
}

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {
	if capacity <= 0 {
		return &LRUCache[K, V]{
			capacity: 0,
			size:     0,
			keyToNode: make(map[K]*node[K, V]),
		}
	}
	return &LRUCache[K, V]{
		capacity: capacity,
		size:     0,
		keyToNode: make(map[K]*node[K, V]),
	}
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
	if c.capacity == 0 {
		var zero V
		return zero, false
	}
	
	node, ok := c.keyToNode[key]
	if !ok {
		var zero V
		return zero, false
	}
	
	// Move to front (most recently used)
	c.moveToFront(node)
	
	return node.value, true
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}
	
	node, ok := c.keyToNode[key]
	if ok {
		// Update existing key
		node.value = value
		c.moveToFront(node)
		return
	}
	
	// Create new node
	newNode := &node[K, V]{
		key: key,
		value: value,
	}
	c.keyToNode[key] = newNode
	
	// Add to front
	c.addToFront(newNode)
	c.size++
	
	// Evict if over capacity
	if c.size > c.capacity {
		c.evictLRU()
	}
}

func (c *LRUCache[K, V]) Len() int {
	return c.size
}

func (c *LRUCache[K, V]) addToFront(node *node[K, V]) {
	if c.head == nil {
		c.head = node
		c.tail = node
	} else {
		node.next = c.head
		c.head.prev = node
		c.head = node
	}
}

func (c *LRUCache[K, V]) moveToFront(node *node[K, V]) {
	if node.prev != nil {
		node.prev.next = node.next
	}
	if node.next != nil {
		node.next.prev = node.prev
	}
	
	if node == c.tail {
		c.tail = node.prev
	}
	
	if node == c.head {
		c.head = node.next
	}
	
	node.prev = nil
	node.next = c.head
	if c.head != nil {
		c.head.prev = node
	}
	c.head = node
}

func (c *LRUCache[K, V]) evictLRU() {
	if c.tail == nil {
		return
	}
	
	node := c.tail
	delete(c.keyToNode, node.key)
	c.removeNode(node)
	c.size--
}

func (c *LRUCache[K, V]) removeNode(node *node[K, V]) {
	if node.prev != nil {
		node.prev.next = node.next
	} else {
		c.head = node.next
	}
	
	if node.next != nil {
		node.next.prev = node.prev
	} else {
		c.tail = node.prev
	}
}
```

I'm reconsidering the `moveToFront` implementation. The current logic for handling node removal and repositioning needs careful review to ensure correct linked list manipulation.

The key challenge is managing the head and tail pointers while moving nodes, especially when the node is already at the head or tail. I'll need to carefully track the node's position and update the surrounding pointers accordingly.

My approach will focus on creating a robust method that handles all edge cases for node repositioning in the doubly linked list.

[
  {
    "total": 1,
    "answer": "```go\npackage challenge\n\ntype node[K comparable, V any] struct {\n\tkey   K\n\tvalue V\n\tprev  *node[K, V]\n\tnext  *node[K, V]\n}\n\ntype LRUCache[K comparable, V any] struct {\n\tcapacity int\n\tsize     int\n\tkeyToNode map[K]*node[K, V]\n\thead      *node[K, V]\n\ttail      *node[K, V]\n}\n\nfunc NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {\n\tif capacity <= 0 {\n\t\treturn &LRUCache[K, V]{\n\t\t\tcapacity: 0,\n\t\t\tsize:     0,\n\t\t\tkeyToNode: make(map[K]*node[K, V]),\n\t\t}\n\t}\n\treturn &LRUCache[K, V]{\n\t\tcapacity: capacity,\n\t\tsize:     0,\n\t\tkeyToNode: make(map[K]*node[K, V]),\n\t}\n}\n\nfunc (c *LRUCache[K, V]) Get(key K) (V, bool) {\n\tif c.capacity == 0 {\n\t\tvar zero V\n\t\treturn zero, false\n\t}\n\n\tnode, ok := c.keyToNode[key]\n\tif !ok {\n\t\tvar zero V\n\t\treturn zero, false\n\t}\n\n\tc.moveToFront(node)\n\treturn node.value, true\n}\n\nfunc (c *LRUCache[K, V]) Put(key K, value V) {\n\tif c.capacity == 0 {\n\t\treturn\n\t}\n\n\tnode, ok := c.keyToNode[key]\n\tif ok {\n\t\tnode.value = value\n\t\tc.moveToFront(node)\n\t\treturn\n\t}\n\n\tnewNode := &node[K, V]{\n\t\tkey:   key,\n\t\tvalue: value,\n\t}\n\tc.keyToNode[key] = newNode\n\tc.addToFront(newNode)\n\tc.size++\n\n\tif c.size > c.capacity {\n\t\tc.evictLRU()\n\t}\n}\n\nfunc (c *LRUCache[K, V]) Len() int {\n\treturn c.size\n}\n\nfunc (c *LRUCache[K, V]) addToFront(node *node[K, V]) {\n\tif c.head == nil {\n\t\tc.head = node\n\t\tc.tail = node\n\t} else {\n\t\tnode.next = c.head\n\t\tc.head.prev = node\n\t\tc.head = node\n\t}\n}\n\nfunc (c *LRUCache[K, V]) moveToFront(node *node[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t}\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t}\n\n\tif node == c.tail {\n\t\tc.tail = node.prev\n\t}\n\n\tif node == c.head {\n\t\tc.head = node.next\n\t}\n\n\tnode.prev = nil\n\tnode.next = c.head\n\tif c.head != nil {\n\t\tc.head.prev = node\n\t}\n\tc.head = node\n}\n\nfunc (c *LRUCache[K, V]) evictLRU() {\n\tif c.tail == nil {\n\t\treturn\n\t}\n\n\tnode := c.tail\n\tdelete(c.keyToNode, node.key)\n\tc.removeNode(node)\n\tc.size--\n}\n\nfunc (c *LRUCache[K, V]) removeNode(node *node[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t} else {\n\t\tc.head = node.next\n\t}\n\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t} else {\n\t\tc.tail = node.prev\n\t}\n}\n```",
    "passed": 0,
    "reasoning": "The task is to implement a generic LRU (Least Recently Used) cache in Go. Let me break down the requirements:\n\n1. Generic type `LRUCache[K comparable, V any]`\n2. Constructor `NewLRUCache[K comparable, V any](capacity int)` - capacity <= 0 means 0 capacity\n3. `Get(key K) (V, bool)` - returns value and true if exists, updates LRU order on successful get\n4. `Put(key K, value V)` - inserts or updates, updates LRU order, evicts LRU if capacity exceeded\n5. `Len() int` - returns current number of entries\n\nFor an LRU cache, I need to:\n1. Track which keys are in the cache\n2. Track the order of usage (most recent to least recent)\n3. When capacity is exceeded, remove the least recently used entry\n\nCommon approaches:\n- Use a map for O(1) key lookup\n- Use a doubly linked list to maintain order (most recent at head, least recent at tail)\n- When accessing/inserting, move the node to the head\n- When evicting, remove from tail\n\nLet me implement this:\n\n```go\npackage challenge\n\nimport (\n\t\"sync\"\n)\n\ntype LRUCache[K comparable, V any] struct {\n\tcapacity int\n\tsize     int\n\tkeyToNode map[K]*node[K, V]\n\thead *node[K, V]\n\ttail *node[K, V]\n}\n\ntype node[K comparable, V any] struct {\n\tkey K\n\tvalue V\n\tprev *node[K, V]\n\tnext *node[K, V]\n}\n\nfunc NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {\n\tif capacity <= 0 {\n\t\treturn &LRUCache[K, V]{\n\t\t\tcapacity: 0,\n\t\t\tsize:     0,\n\t\t\tkeyToNode: make(map[K]*node[K, V]),\n\t\t}\n\t}\n\treturn &LRUCache[K, V]{\n\t\tcapacity: capacity,\n\t\tsize:     0,\n\t\tkeyToNode: make(map[K]*node[K, V]),\n\t}\n}\n\nfunc (c *LRUCache[K, V]) Get(key K) (V, bool) {\n\tif c.capacity == 0 {\n\t\tvar zero V\n\t\treturn zero, false\n\t}\n\t\n\tnode, ok := c.keyToNode[key]\n\tif !ok {\n\t\tvar zero V\n\t\treturn zero, false\n\t}\n\t\n\t// Move to front (most recently used)\n\tc.moveToFront(node)\n\t\n\treturn node.value, true\n}\n\nfunc (c *LRUCache[K, V]) Put(key K, value V) {\n\tif c.capacity == 0 {\n\t\treturn\n\t}\n\t\n\tnode, ok := c.keyToNode[key]\n\tif ok {\n\t\t// Update existing key\n\t\tnode.value = value\n\t\tc.moveToFront(node)\n\t\treturn\n\t}\n\t\n\t// Create new node\n\tnewNode := &node[K, V]{\n\t\tkey: key,\n\t\tvalue: value,\n\t}\n\tc.keyToNode[key] = newNode\n\t\n\t// Add to front\n\tc.addToFront(newNode)\n\tc.size++\n\t\n\t// Evict if over capacity\n\tif c.size > c.capacity {\n\t\tc.evictLRU()\n\t}\n}\n\nfunc (c *LRUCache[K, V]) Len() int {\n\treturn c.size\n}\n\nfunc (c *LRUCache[K, V]) addToFront(node *node[K, V]) {\n\tif c.head == nil {\n\t\tc.head = node\n\t\tc.tail = node\n\t} else {\n\t\tnode.next = c.head\n\t\tc.head.prev = node\n\t\tc.head = node\n\t}\n}\n\nfunc (c *LRUCache[K, V]) moveToFront(node *node[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t}\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t}\n\t\n\tif node == c.tail {\n\t\tc.tail = node.prev\n\t}\n\t\n\tif node == c.head {\n\t\tc.head = node.next\n\t}\n\t\n\tnode.prev = nil\n\tnode.next = c.head\n\tif c.head != nil {\n\t\tc.head.prev = node\n\t}\n\tc.head = node\n}\n\nfunc (c *LRUCache[K, V]) evictLRU() {\n\tif c.tail == nil {\n\t\treturn\n\t}\n\t\n\tnode := c.tail\n\tdelete(c.keyToNode, node.key)\n\tc.removeNode(node)\n\tc.size--\n}\n\nfunc (c *LRUCache[K, V]) removeNode(node *node[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t} else {\n\t\tc.head = node.next\n\t}\n\t\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t} else {\n\t\tc.tail = node.prev\n\t}\n}\n```\n\nI'm reconsidering the `moveToFront` implementation. The current logic for handling node removal and repositioning needs careful review to ensure correct linked list manipulation.\n\nThe key challenge is managing the head and tail pointers while moving nodes, especially when the node is already at the head or tail. I'll need to carefully track the node's position and update the surrounding pointers accordingly.\n\nMy approach will focus on creating a robust method that handles all edge cases for node repositioning in the doubly linked list.\n",
    "test_error": "{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"# challenge [challenge.test]\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:61:14: node (local variable) is not a type\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-fail\"}\n{\"Time\":\"2026-07-02T04:34:52.752406372+02:00\",\"Action\":\"start\",\"Package\":\"challenge\"}\n{\"Time\":\"2026-07-02T04:34:52.752471632+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge [build failed]\\n\"}\n{\"Time\":\"2026-07-02T04:34:52.752478462+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0,\"FailedBuild\":\"challenge [challenge.test]\"}"
  },
  {
    "total": 10,
    "answer": "```go\npackage challenge\n\ntype lruNode[K comparable, V any] struct {\n\tkey   K\n\tvalue V\n\tprev  *lruNode[K, V]\n\tnext  *lruNode[K, V]\n}\n\ntype LRUCache[K comparable, V any] struct {\n\tcapacity int\n\tsize     int\n\tkeyToNode map[K]*lruNode[K, V]\n\thead      *lruNode[K, V]\n\ttail      *lruNode[K, V]\n}\n\nfunc NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {\n\tif capacity <= 0 {\n\t\treturn &LRUCache[K, V]{\n\t\t\tcapacity: 0,\n\t\t\tsize:     0,\n\t\t\tkeyToNode: make(map[K]*lruNode[K, V]),\n\t\t}\n\t}\n\treturn &LRUCache[K, V]{\n\t\tcapacity: capacity,\n\t\tsize:     0,\n\t\tkeyToNode: make(map[K]*lruNode[K, V]),\n\t}\n}\n\nfunc (c *LRUCache[K, V]) Get(key K) (V, bool) {\n\tif c.capacity == 0 {\n\t\tvar zero V\n\t\treturn zero, false\n\t}\n\n\tnode, ok := c.keyToNode[key]\n\tif !ok {\n\t\tvar zero V\n\t\treturn zero, false\n\t}\n\n\tc.moveToFront(node)\n\treturn node.value, true\n}\n\nfunc (c *LRUCache[K, V]) Put(key K, value V) {\n\tif c.capacity == 0 {\n\t\treturn\n\t}\n\n\tnode, ok := c.keyToNode[key]\n\tif ok {\n\t\tnode.value = value\n\t\tc.moveToFront(node)\n\t\treturn\n\t}\n\n\tnewNode := &lruNode[K, V]{\n\t\tkey:   key,\n\t\tvalue: value,\n\t}\n\tc.keyToNode[key] = newNode\n\tc.addToFront(newNode)\n\tc.size++\n\n\tif c.size > c.capacity {\n\t\tc.evictLRU()\n\t}\n}\n\nfunc (c *LRUCache[K, V]) Len() int {\n\treturn c.size\n}\n\nfunc (c *LRUCache[K, V]) addToFront(node *lruNode[K, V]) {\n\tif c.head == nil {\n\t\tc.head = node\n\t\tc.tail = node\n\t} else {\n\t\tnode.next = c.head\n\t\tc.head.prev = node\n\t\tc.head = node\n\t}\n}\n\nfunc (c *LRUCache[K, V]) moveToFront(node *lruNode[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t}\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t}\n\n\tif node == c.tail {\n\t\tc.tail = node.prev\n\t}\n\n\tif node == c.head {\n\t\tc.head = node.next\n\t}\n\n\tnode.prev = nil\n\tnode.next = c.head\n\tif c.head != nil {\n\t\tc.head.prev = node\n\t}\n\tc.head = node\n}\n\nfunc (c *LRUCache[K, V]) evictLRU() {\n\tif c.tail == nil {\n\t\treturn\n\t}\n\n\tnode := c.tail\n\tdelete(c.keyToNode, node.key)\n\tc.removeNode(node)\n\tc.size--\n}\n\nfunc (c *LRUCache[K, V]) removeNode(node *lruNode[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t} else {\n\t\tc.head = node.next\n\t}\n\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t} else {\n\t\tc.tail = node.prev\n\t}\n}\n```",
    "passed": 10,
    "reasoning": "The error message says: `./solution.go:61:14: node (local variable) is not a type`\n\nLooking at line 61, I need to check what's there. In my code, line 61 would be in the `moveToFront` function. Let me look at that function:\n\n```go\nfunc (c *LRUCache[K, V]) moveToFront(node *node[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t}\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t}\n\n\tif node == c.tail {\n\t\tc.tail = node.prev\n\t}\n\n\tif node == c.head {\n\t\tc.head = node.next\n\t}\n\n\tnode.prev = nil\n\tnode.next = c.head\n\tif c.head != nil {\n\t\tc.head.prev = node\n\t}\n\tc.head = node\n}\n```\n\nWait, the issue is that I'm using `node` as a parameter name, but I also have a type called `node`. In Go, you can't have a local variable with the same name as a type in the same scope.\n\nThe type is defined as:\n```go\ntype node[K comparable, V any] struct {\n```\n\nAnd the parameter is:\n```go\nfunc (c *LRUCache[K, V]) moveToFront(node *node[K, V]) {\n```\n\nThis creates a conflict because `node` is both a type and a variable name in the same scope.\n\nI need to rename either the type or the parameter. Let me rename the type to `lruNode` to avoid conflicts.\n\nActually, looking more carefully at the error, it says `node (local variable) is not a type`. This suggests that somewhere in the code, I'm trying to use `node` as a type when it's actually a variable.\n\nLet me check all the places where I use `node`:\n\n1. `type node[K comparable, V any] struct` - this is the type definition\n2. `newNode := &node[K, V]{` - this is using the type correctly\n\n\n3. `c.keyToNode[key] = newNode` - using the variable\n4. `c.moveToFront(node)` - passing the variable\n5. `func (c *LRUCache[K, V]) moveToFront(node *node[K, V])` - parameter name conflicts with type name\n\nThe parameter name `node` in `moveToFront` conflicts with the type name `node`. I should rename the type to `lruNode` to resolve this naming conflict.\n\nActually, I need to check all the functions that use the `node` type. Let me trace through:\n\n- `NewLRUCache` - doesn't use `node` directly\n- `Get` - calls `moveToFront(node)` where `node` is a variable\n- `Put` - creates `newNode := &node[K, V]{` and calls `moveToFront(newNode)`\n- `moveToFront` - parameter is `node *node[K, V]` - this is the conflict!\n- `addToFront` - parameter is `node *node[K, V]` - this is also a conflict!\n- `evictLRU` - uses `node` as a variable\n- `removeNode` - parameter is `node *node[K, V]` - this is also a conflict!\n\nSo I need to rename the type to avoid conflicts with parameter names. I'll use `lruNode` for the type and keep `node` as the parameter name, or vice versa.\n\nActually, the cleanest solution is to rename the type to something like `lruNode` to avoid conflicts with local variable names.\n\nLet me rewrite the code with the type renamed:\n\n```go\npackage challenge\n\ntype lruNode[K comparable, V any] struct {\n\tkey   K\n\tvalue V\n\tprev  *lruNode[K, V]\n\tnext  *lruNode[K, V]\n}\n\ntype LRUCache[K comparable, V any] struct {\n\tcapacity int\n\tsize     int\n\tkeyToNode map[K]*lruNode[K, V]\n\thead      *lruNode[K, V]\n\ttail      *lruNode[K, V]\n}\n\nfunc NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {\n\tif capacity <= 0 {\n\t\treturn &LRUCache[K, V]{\n\t\t\tcapacity: 0,\n\t\t\tsize:     0,\n\t\t\tkeyToNode: make(map[K]*lruNode[K, V]),\n\t\t}\n\t}\n\treturn &LRUCache[K, V]{\n\t\tcapacity: capacity,\n\t\tsize:     0,\n\t\tkeyToNode: make(map[K]*lruNode[K, V]),\n\t}\n}\n\nfunc (c *LRUCache[K, V]) Get(key K) (V, bool) {\n\tif c.capacity == 0 {\n\t\tvar zero V\n\t\treturn zero, false\n\t}\n\n\tnode, ok := c.keyToNode[key]\n\tif !ok {\n\t\tvar zero V\n\t\treturn zero, false\n\t}\n\n\tc.moveToFront(node)\n\treturn node.value, true\n}\n\nfunc (c *LRUCache[K, V]) Put(key K, value V) {\n\tif c.capacity == 0 {\n\t\treturn\n\t}\n\n\tnode, ok := c.keyToNode[key]\n\tif ok {\n\t\tnode.value = value\n\t\tc.moveToFront(node)\n\t\treturn\n\t}\n\n\tnewNode := &lruNode[K, V]{\n\t\tkey:   key,\n\t\tvalue: value,\n\t}\n\tc.keyToNode[key] = newNode\n\tc.addToFront(newNode)\n\tc.size++\n\n\tif c.size > c.capacity {\n\t\tc.evictLRU()\n\t}\n}\n\nfunc (c *LRUCache[K, V]) Len() int {\n\treturn c.size\n}\n\nfunc (c *LRUCache[K, V]) addToFront(node *lruNode[K, V]) {\n\tif c.head == nil {\n\t\tc.head = node\n\t\tc.tail = node\n\t} else {\n\t\tnode.next = c.head\n\t\tc.head.prev = node\n\t\tc.head = node\n\t}\n}\n\nfunc (c *LRUCache[K, V]) moveToFront(node *lruNode[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t}\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t}\n\n\tif node == c.tail {\n\t\tc.tail = node.prev\n\t}\n\n\tif node == c.head {\n\t\tc.head = node.next\n\t}\n\n\tnode.prev = nil\n\tnode.next = c.head\n\tif c.head != nil {\n\t\tc.head.prev = node\n\t}\n\tc.head = node\n}\n\nfunc (c *LRUCache[K, V]) evictLRU() {\n\tif c.tail == nil {\n\t\treturn\n\t}\n\n\tnode := c.tail\n\tdelete(c.keyToNode, node.key)\n\tc.removeNode(node)\n\tc.size--\n}\n\nfunc (c *LRUCache[K, V]) removeNode(node *lruNode[K, V]) {\n\tif node.prev != nil {\n\t\tnode.prev.next = node.next\n\t} else {\n\t\tc.head = node.next\n\t}\n\n\tif node.next != nil {\n\t\tnode.next.prev = node.prev\n\t} else {\n\t\tc.tail = node.prev\n\t}\n}\n```\n\nI've renamed the type to `lruNode` to prevent naming conflicts with local variables. This resolves the compilation error by ensuring type and variable names are distinct.\n",
    "test_error": ""
  }
]