課題7: スライス操作ユーティリティ

課題概要

スライスを使って、実用的なユーティリティ関数とデータ構造を実装します。スライスの内部構造、append、copy、容量管理を深く理解します。

マンダトリー要件

要件1: 基本的なスライス操作

基本的なスライス操作関数を実装してください。

ファイル: sliceutil/basic.go

package sliceutil

// Insert はインデックスiに要素を挿入
func Insert(s []int, i int, v int) []int {
    // TODO: 実装してください
    // - 範囲外チェック
    // - i の位置に v を挿入
}

// Remove はインデックスiの要素を削除（順序を保持）
func Remove(s []int, i int) []int {
    // TODO: 実装してください
}

// RemoveFast はインデックスiの要素を削除（順序を保持しない、高速）
func RemoveFast(s []int, i int) []int {
    // TODO: 実装してください
    // 最後の要素とスワップして削除
}

// RemoveAll は指定した値をすべて削除
func RemoveAll(s []int, value int) []int {
    // TODO: 実装してください
}

// Reverse はスライスを反転
func Reverse(s []int) []int {
    // TODO: 実装してください
    // 新しいスライスを返す
}

// ReverseInPlace はスライスを反転（インプレース）
func ReverseInPlace(s []int) {
    // TODO: 実装してください
}

// Unique は重複を削除（順序を保持）
func Unique(s []int) []int {
    // TODO: 実装してください
}

// Concat は複数のスライスを連結
func Concat(slices ...[]int) []int {
    // TODO: 実装してください
}

// Chunk はスライスをサイズnのチャンクに分割
func Chunk(s []int, n int) [][]int {
    // TODO: 実装してください
    // 例: Chunk([1,2,3,4,5], 2) → [[1,2], [3,4], [5]]
}

要件2: 検索とフィルタリング

検索とフィルタリング関数を実装してください。

ファイル: sliceutil/search.go

package sliceutil

// Contains は要素が含まれているか判定
func Contains(s []int, target int) bool {
    // TODO: 実装してください
}

// IndexOf は最初に見つかったインデックスを返す（見つからない場合は-1）
func IndexOf(s []int, target int) int {
    // TODO: 実装してください
}

// LastIndexOf は最後に見つかったインデックスを返す
func LastIndexOf(s []int, target int) int {
    // TODO: 実装してください
}

// FindAll は条件を満たすすべての要素を返す
func FindAll(s []int, predicate func(int) bool) []int {
    // TODO: 実装してください
}

// FindIndex は条件を満たす最初のインデックスを返す
func FindIndex(s []int, predicate func(int) bool) int {
    // TODO: 実装してください
}

// Count は条件を満たす要素の数を返す
func Count(s []int, predicate func(int) bool) int {
    // TODO: 実装してください
}

// Any は条件を満たす要素が1つでもあればtrue
func Any(s []int, predicate func(int) bool) bool {
    // TODO: 実装してください
}

// All はすべての要素が条件を満たせばtrue
func All(s []int, predicate func(int) bool) bool {
    // TODO: 実装してください
}

要件3: 集合演算

スライスを使った集合演算を実装してください。

ファイル: sliceutil/set.go

package sliceutil

// Union は和集合を返す（重複なし）
func Union(s1, s2 []int) []int {
    // TODO: 実装してください
}

// Intersection は積集合を返す
func Intersection(s1, s2 []int) []int {
    // TODO: 実装してください
}

// Difference は差集合を返す（s1にあってs2にない要素）
func Difference(s1, s2 []int) []int {
    // TODO: 実装してください
}

// SymmetricDifference は対称差を返す（どちらか一方にのみ存在）
func SymmetricDifference(s1, s2 []int) []int {
    // TODO: 実装してください
}

// IsSubset はs1がs2の部分集合か判定
func IsSubset(s1, s2 []int) bool {
    // TODO: 実装してください
}

// IsSuperset はs1がs2の上位集合か判定
func IsSuperset(s1, s2 []int) bool {
    // TODO: 実装してください
}

要件4: 動的配列（可変長配列）

効率的な動的配列を実装してください。

ファイル: container/dynamicarray.go

package container

type DynamicArray struct {
    data     []int
    size     int
    capacity int
}

// New は動的配列を作成
func New() *DynamicArray {
    // TODO: 実装してください
    // 初期容量は8
}

// NewWithCapacity は指定した容量で作成
func NewWithCapacity(capacity int) *DynamicArray {
    // TODO: 実装してください
}

// Append は末尾に要素を追加
func (da *DynamicArray) Append(value int) {
    // TODO: 実装してください
    // 容量が足りない場合は2倍に拡張
}

// Get はインデックスの要素を取得
func (da *DynamicArray) Get(index int) (int, error) {
    // TODO: 実装してください
}

// Set はインデックスの要素を設定
func (da *DynamicArray) Set(index int, value int) error {
    // TODO: 実装してください
}

// InsertAt はインデックスに要素を挿入
func (da *DynamicArray) InsertAt(index int, value int) error {
    // TODO: 実装してください
}

// RemoveAt はインデックスの要素を削除
func (da *DynamicArray) RemoveAt(index int) error {
    // TODO: 実装してください
}

// Size は要素数を返す
func (da *DynamicArray) Size() int {
    // TODO: 実装してください
}

// Capacity は容量を返す
func (da *DynamicArray) Capacity() int {
    // TODO: 実装してください
}

// IsEmpty は空か判定
func (da *DynamicArray) IsEmpty() bool {
    // TODO: 実装してください
}

// Clear はすべての要素を削除
func (da *DynamicArray) Clear() {
    // TODO: 実装してください
}

// ToSlice はスライスに変換
func (da *DynamicArray) ToSlice() []int {
    // TODO: 実装してください
}

期待される出力

// 基本操作
s := []int{1, 2, 3, 4, 5}
s = sliceutil.Insert(s, 2, 99)  // [1 2 99 3 4 5]
s = sliceutil.Remove(s, 2)      // [1 2 3 4 5]
s = sliceutil.Reverse(s)        // [5 4 3 2 1]

// 検索
s := []int{1, 2, 3, 4, 5, 3}
idx := sliceutil.IndexOf(s, 3)       // 2
lastIdx := sliceutil.LastIndexOf(s, 3) // 5
count := sliceutil.Count(s, func(n int) bool {
    return n > 2
})  // 4

// 集合演算
s1 := []int{1, 2, 3, 4}
s2 := []int{3, 4, 5, 6}
union := sliceutil.Union(s1, s2)              // [1 2 3 4 5 6]
intersection := sliceutil.Intersection(s1, s2) // [3 4]

// 動的配列
da := container.New()
da.Append(1)
da.Append(2)
da.Append(3)
value, _ := da.Get(1)  // 2
fmt.Println(da.Size())      // 3
fmt.Println(da.Capacity())  // 8

ボーナス課題

ボーナス1: 循環バッファ

固定サイズの循環バッファを実装してください。

package container

type CircularBuffer struct {
    buffer   []int
    head     int
    tail     int
    size     int
    capacity int
}

// NewCircularBuffer は循環バッファを作成
func NewCircularBuffer(capacity int) *CircularBuffer {
    // TODO: 実装してください
}

// Push は要素を追加（満杯なら最古の要素を上書き）
func (cb *CircularBuffer) Push(value int) {
    // TODO: 実装してください
}

// Pop は最も古い要素を取り出す
func (cb *CircularBuffer) Pop() (int, error) {
    // TODO: 実装してください
}

// Peek は最も古い要素を取得（削除しない）
func (cb *CircularBuffer) Peek() (int, error) {
    // TODO: 実装してください
}

// IsFull は満杯か判定
func (cb *CircularBuffer) IsFull() bool {
    // TODO: 実装してください
}

// IsEmpty は空か判定
func (cb *CircularBuffer) IsEmpty() bool {
    // TODO: 実装してください
}

// Size は要素数を返す
func (cb *CircularBuffer) Size() int {
    // TODO: 実装してください
}

// ToSlice はスライスに変換（古い順）
func (cb *CircularBuffer) ToSlice() []int {
    // TODO: 実装してください
}

ボーナス2: ソート済みスライス

常にソート済みを保つスライスを実装してください。

package container

type SortedSlice struct {
    data []int
}

// NewSortedSlice はソート済みスライスを作成
func NewSortedSlice() *SortedSlice {
    // TODO: 実装してください
}

// Insert は要素を正しい位置に挿入
func (ss *SortedSlice) Insert(value int) {
    // TODO: 二分探索で挿入位置を見つける
}

// Remove は要素を削除
func (ss *SortedSlice) Remove(value int) bool {
    // TODO: 二分探索で見つけて削除
}

// Contains は要素が含まれているか判定（二分探索）
func (ss *SortedSlice) Contains(value int) bool {
    // TODO: 実装してください
}

// Min は最小値を返す
func (ss *SortedSlice) Min() (int, error) {
    // TODO: 実装してください
}

// Max は最大値を返す
func (ss *SortedSlice) Max() (int, error) {
    // TODO: 実装してください
}

// Range は指定範囲の要素を返す（from <= x <= to）
func (ss *SortedSlice) Range(from, to int) []int {
    // TODO: 二分探索で範囲を見つける
}

ボーナス3: 2次元スライス操作

2次元スライス操作関数を実装してください。

package sliceutil

// Transpose は行列を転置
func Transpose(matrix [][]int) [][]int {
    // TODO: 実装してください
}

// RotateClockwise は行列を時計回りに90度回転
func RotateClockwise(matrix [][]int) [][]int {
    // TODO: 実装してください
}

// RotateCounterClockwise は行列を反時計回りに90度回転
func RotateCounterClockwise(matrix [][]int) [][]int {
    // TODO: 実装してください
}

// FlattenMatrix は2次元スライスを1次元に変換
func FlattenMatrix(matrix [][]int) []int {
    // TODO: 実装してください
}

// ReshapeMatrix は1次元スライスを2次元に変換
func ReshapeMatrix(s []int, rows, cols int) ([][]int, error) {
    // TODO: 実装してください
    // len(s) != rows * cols の場合はエラー
}

評価基準

提出方法

submission/
├── go.mod
├── sliceutil/
│   ├── basic.go
│   ├── basic_test.go
│   ├── search.go
│   ├── search_test.go
│   ├── set.go
│   └── set_test.go
├── container/
│   ├── dynamicarray.go
│   └── dynamicarray_test.go
└── bonus/
    ├── circularbuffer.go
    ├── sortedslice.go
    └── matrix.go

ヒント

• Insert: append と copy を組み合わせる
• Remove: スライシングで前後を結合
• Unique: マップで重複チェック
• 動的配列: 容量が足りなくなったら2倍に拡張
• 循環バッファ: modulo演算でインデックス管理
• ソート済み: 二分探索で O(log n) 検索

テストケース

// sliceutil/basic_test.go
func TestInsert(t *testing.T) {
    tests := []struct {
        input    []int
        index    int
        value    int
        expected []int
    }{
        {[]int{1, 2, 3}, 1, 99, []int{1, 99, 2, 3}},
        {[]int{1, 2, 3}, 0, 99, []int{99, 1, 2, 3}},
        {[]int{1, 2, 3}, 3, 99, []int{1, 2, 3, 99}},
    }

    for _, tt := range tests {
        result := Insert(tt.input, tt.index, tt.value)
        if !reflect.DeepEqual(result, tt.expected) {
            t.Errorf("Insert(%v, %d, %d) = %v; want %v",
                tt.input, tt.index, tt.value, result, tt.expected)
        }
    }
}

// container/dynamicarray_test.go
func TestDynamicArrayGrowth(t *testing.T) {
    da := NewWithCapacity(2)

    // 初期容量2
    if da.Capacity() != 2 {
        t.Errorf("Initial capacity = %d; want 2", da.Capacity())
    }

    // 3つ追加（拡張が起きる）
    da.Append(1)
    da.Append(2)
    da.Append(3)

    // 容量が4に拡張されているはず
    if da.Capacity() < 4 {
        t.Errorf("Capacity after growth = %d; want >= 4", da.Capacity())
    }

    if da.Size() != 3 {
        t.Errorf("Size = %d; want 3", da.Size())
    }
}

パフォーマンス目標

// ベンチマークテスト例
func BenchmarkDynamicArrayAppend(b *testing.B) {
    da := New()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        da.Append(i)
    }
}

func BenchmarkSortedSliceInsert(b *testing.B) {
    ss := NewSortedSlice()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        ss.Insert(rand.Intn(10000))
    }
}

学習リソース

• Go Slices: usage and internals
• Go by Example - Slices
• Effective Go - Slices
• SliceTricks