Flutter でデータ構造を楽しく学ぶ方法

ゲームを構築し、コンピュータサイエンスを学びます。

データ構造は効率的なソフトウェア開発の基盤となりますが、従来の学習方法では抽象的で現実世界のアプリケーションから切り離されているように感じられがちです。この記事では異なるアプローチを採用し、Flutter での理論と実践的な実装を組み合わせて、学習を魅力的かつ実践的なものにします。

Google のAndroid 向け応用 CSにヒントを得たこの Flutter 向けコースでは、配列、ハッシュセット、ハッシュマップをインタラクティブに理解できます。わずか3～4 時間で、これらの基本的なデータ構造をより深く理解し、意味のあるコンテキストに適用できるようになります。

CS の基礎を強化したい初心者でも、スキルを磨きたい経験豊富な開発者でも、このガイドは基本的なデータ構造を習得するための効率的で楽しい方法を提供します。さあ、始めましょう。

この記事の目的:

1. 辞書を使用してデータ (この場合は単語) を保存する方法について理解します。
2. ハッシュ マップを使用して、アナグラムである単語のグループを保存します。
3. 大規模なデータセットを扱う際に、一部のデータ構造が直面する制限を説明できるようになります。

準備：

ワークショップのアクティビティではいくつかのデータ構造を使用するので、 Lists 、 HashSets 、 HashMapsを確認してください。Dart でこれらのデータ構造を使用して、自信を持って要素の挿入、削除、アクセス、存在の確認を行うことができるはずです。

これは、データ構造、HashSets、および HashMap の簡単な紹介です。

ちょっとした初心者向けエクササイズのウォームアップ:

HashMaps を使用したアクティビティの例として、3 文字の国コード ( ISO-3166を参照) を受け取り、その国が属する国の完全な名前を返すプログラム (必ずしも Flutter アプリである必要はなく、コマンドラインでもかまいません) を作成します。

例えば：

 Input | Output ----- | ---------------------------------------------------- GBR | United Kingdom of Great Britain and Northern Ireland IDN | Indonesia IND | India

拡張機能として、入力が 3 文字を超える場合は、国名と見なし、その 3 文字のコードを返します。入力が有効なコードでも国名でもない場合は、役立つエラー メッセージを記述します。

始めましょう。

アナグラム

アナグラムとは、別の単語の文字を並べ替えて作られた単語です。たとえば、 cinema はicemanのアナグラムです。

ゲームの仕組みは次のとおりです。

1. ゲームでは、辞書から単語をユーザーに提供します。

   
   

2. ユーザーは、与えられた単語のすべての文字と 1 つの追加文字を含む単語をできるだけ多く作成しようとします。他の文字を並べ替えずに先頭または末尾に追加の文字を追加することは無効であることに注意してください。たとえば、ゲームがスターターとして単語「ore」を選択した場合、ユーザーは「rose」または「zero」を推測することはできますが、「sore」は推測できません。

   
   

3. ユーザーは諦めて、推測できなかった単語を見ることができます。

10,000 語の辞書が含まれ、このゲームの UI 部分を処理するスターター コードが提供されています。すべての単語操作を処理する AnagramBloc クラスの作成は、ユーザーの責任となります。

コードのツアー

スターター コードは、次の 3 つの主要な Dart クラスで構成されています。

anagrams_page.dart

これは、上記の画面を表すシンプルなコードです。画面の状態管理にはブロックを使用します。まず、ブロックにイベントを発生させてゲームを設定し、画面がさまざまなゲーム状態に応答したときに何が起こるかを定義します。

 import 'package:anagrams/anagrams/bloc/anagram_bloc.dart'; import 'package:anagrams/anagrams/domain/word.dart'; import 'package:anagrams/l10n/l10n.dart'; import 'package:bloc_presentation/bloc_presentation.dart'; import 'package:flutter/material.dart'; import 'package:flutter_bloc/flutter_bloc.dart'; class AnagramsPage extends StatelessWidget { const AnagramsPage({super.key}); @override Widget build(BuildContext context) { return BlocProvider( create: (_) => AnagramBloc() ..add( SetupAnagrams( DefaultAssetBundle.of(context), ), ), child: const AnagramsView(), ); } } class AnagramsView extends StatelessWidget { const AnagramsView({super.key}); @override Widget build(BuildContext context) { final l10n = context.l10n; return Scaffold( appBar: AppBar(title: Text(l10n.anagramAppBarTitle)), body: BlocBuilder<AnagramBloc, AnagramState>( builder: (context, state) { switch (state.status) { case AnagramGameStatus.gameError: return const Center( child: Text('An error occurred'), ); case AnagramGameStatus.loaded: return Padding( padding: const EdgeInsets.all(20), child: ListView( children: const [ _SelectedWord(), SizedBox(height: 20), _AnagramsTextField(), SizedBox(height: 10), _GuessListView(), ], ), ); case AnagramGameStatus.initial: return const Center( child: CircularProgressIndicator(), ); } }, ), floatingActionButton: const _NextWordButton(), ); } } class _SelectedWord extends StatelessWidget { const _SelectedWord(); @override Widget build(BuildContext context) { return BlocSelector<AnagramBloc, AnagramState, String>( selector: (state) => state.currentWord, builder: (context, currentWord) { return Text.rich( TextSpan( text: 'Find as many words as possible that can be ' 'formed by adding one letter to ', children: [ TextSpan( text: currentWord.toUpperCase(), style: const TextStyle(fontWeight: FontWeight.bold), ), TextSpan( text: ' (but that do not contain the substring' ' ${currentWord.toUpperCase()}).', ), ], ), ); }, ); } } class _AnagramsTextField extends StatelessWidget { const _AnagramsTextField(); @override Widget build(BuildContext context) { final controller = TextEditingController(); return TextField( controller: controller, decoration: const InputDecoration( hintText: 'Enter an anagram', border: OutlineInputBorder(), ), keyboardType: TextInputType.text, textInputAction: TextInputAction.done, onSubmitted: (value) { controller.clear(); context.read<AnagramBloc>().add(ProcessWord(value)); }, ); } } class _GuessListView extends StatelessWidget { const _GuessListView(); @override Widget build(BuildContext context) { return BlocSelector<AnagramBloc, AnagramState, List<Word>>( selector: (state) => state.guesses, builder: (context, guesses) { return Column( children: guesses.map((word) { return ListTile( minTileHeight: 0, contentPadding: EdgeInsets.zero, visualDensity: VisualDensity.compact, title: Text(word.value), leading: Icon( word.isAnagram ? Icons.check : Icons.close, color: word.isAnagram ? Colors.green : Colors.red, ), ); }).toList(), ); }, ); } } class _GameResult extends StatelessWidget { const _GameResult(this.currentWord, this.result); final List<Word> result; final String currentWord; @override Widget build(BuildContext context) { return ListView( shrinkWrap: true, children: [ const SizedBox(height: 20), Padding( padding: const EdgeInsets.symmetric( horizontal: 20, ), child: Text( 'Game Result for $currentWord', style: const TextStyle(fontSize: 20), ), ), Padding( padding: const EdgeInsets.all(20), child: SizedBox( width: double.infinity, child: DataTable( decoration: BoxDecoration( border: Border.all( color: Colors.grey.shade400, ), borderRadius: BorderRadius.circular(10), ), columns: const [ DataColumn(label: Text('Possible Anagrams')), DataColumn(label: Text('Your Guesses')), ], rows: result.map((word) { return DataRow( cells: [ DataCell(Text(word.value)), DataCell( Center( child: Icon( word.isAnagram ? Icons.check : Icons.close, color: word.isAnagram ? Colors.green : Colors.red, ), ), ), ], ); }).toList(), ), ), ), ], ); } } class _NextWordButton extends StatelessWidget { const _NextWordButton(); @override Widget build(BuildContext context) { final l10n = context.l10n; return BlocPresentationListener<AnagramBloc, AnagramPresenterEvent>( listener: (context, event) { if (event is FinishGuess) { // show a bottom sheet with the anagrams that were not guessed showModalBottomSheet<void>( context: context, useSafeArea: true, builder: (context) { return _GameResult(event.currentWord, event.result); }, ); } }, child: FloatingActionButton.extended( onPressed: () async { context.read<AnagramBloc>().add(ResetGame()); }, label: Text(l10n.nextWordButton), ), ); } }

• _SelectWord : ゲームでアナグラムを作成するために選択された単語を表示します。

• _AnagramsTextField : 単語を受け取り、ユーザーが入力した単語を処理するイベントを発生させます。

• _GuessListView : ユーザーが入力した推測とそれが正しいかどうかを表示します。

• _NextWordButton : ゲームをリセットし、現在の単語のすべてのアナグラムとユーザーが推測したアナグラムをユーザーに提示します。

anagram_states.dart

 enum AnagramGameStatus { initial, loaded, gameError } const minNumAnagrams = 5; const defaultWordLength = 3; const maxDefaultWordLength = 7; @immutable final class AnagramState extends Equatable { factory AnagramState({ AnagramGameStatus status = AnagramGameStatus.initial, List<String> words = const [], String currentWord = '', List<String> anagrams = const [], List<Word> guesses = const [], HashSet<String>? wordSet, HashMap<String, List<String>>? anagramMap, HashMap<int, List<String>>? sizeToWords, int wordLength = defaultWordLength, }) { return AnagramState._( status: status, words: words, currentWord: currentWord, anagrams: anagrams, guesses: guesses, wordSet: wordSet ?? HashSet<String>(), anagramMap: anagramMap ?? HashMap<String, List<String>>(), sizeToWords: sizeToWords ?? HashMap<int, List<String>>(), wordLength: wordLength, ); } const AnagramState._({ required this.status, required this.words, required this.currentWord, required this.anagrams, required this.guesses, required this.wordSet, required this.anagramMap, required this.sizeToWords, this.wordLength = defaultWordLength, }); // The current status of the game final AnagramGameStatus status; // All the words in the game final List<String> words; // Currently chosen word of the game to form anagrams final String currentWord; // All the anagrams for the current word final List<String> anagrams; // All the guesses user has made final List<Word> guesses; // A set of all the words in the game final HashSet<String> wordSet; // A map of anagrams for each word final HashMap<String, List<String>> anagramMap; // Stores the words in increasing order of their length final HashMap<int, List<String>> sizeToWords; final int wordLength; AnagramState copyWith({ AnagramGameStatus? status, List<String>? words, String? currentWord, List<String>? anagrams, List<Word>? guesses, HashSet<String>? wordSet, HashMap<String, List<String>>? anagramMap, HashMap<int, List<String>>? sizeToWords, int? wordLength, }) { return AnagramState( status: status ?? this.status, words: words ?? this.words, currentWord: currentWord ?? this.currentWord, anagrams: anagrams ?? this.anagrams, guesses: guesses ?? this.guesses, wordSet: wordSet ?? this.wordSet, anagramMap: anagramMap ?? this.anagramMap, sizeToWords: sizeToWords ?? this.sizeToWords, wordLength: wordLength ?? this.wordLength, ); } @override List<Object?> get props => [ status, words, currentWord, anagrams, guesses, wordSet, anagramMap, sizeToWords, wordLength, ]; }

AnagramState は、ゲームの実行に必要なすべての状態変数を保持します。

• status : ゲームがロード中 (初期)、ロード済み、または何らかのエラーが発生したかどうかを保持します。
• words : ファイルから読み込まれたファイル word.txt のすべての単語を一覧表示します。
• anagrams : 選択した単語のすべてのアナグラムを保持します。
• currentword : 単語リストから選択された単語とアナグラムを形成する単語。
• guesses : ユーザーが入力したすべての選択肢と、それが正しいか間違っているか。

残りの詳細については、この記事の後半で説明します。

anagram_bloc.dart

 import 'dart:async'; import 'dart:collection'; import 'dart:convert'; import 'package:anagrams/anagrams/domain/word.dart'; import 'package:bloc_presentation/bloc_presentation.dart'; import 'package:equatable/equatable.dart'; import 'package:flutter/widgets.dart'; import 'package:flutter_bloc/flutter_bloc.dart'; part 'anagram_events.dart'; part 'anagram_states.dart'; class AnagramBloc extends Bloc<AnagramEvent, AnagramState> with BlocPresentationMixin<AnagramState, AnagramPresenterEvent> { AnagramBloc() : super(AnagramState()) { on<SetupAnagrams>(_onSetupAnagrams); on<ProcessWord>(_onProcessWord); on<ResetGame>(_onResetGame); } Future<void> _onSetupAnagrams( SetupAnagrams event, Emitter<AnagramState> emit, ) async { try { // this should not be done here, // but for the sake of simplicity, we will do it here final wordsFile = await event.defaultAssetBundle.loadString('assets/words.txt'); // read each line in the file final words = const LineSplitter().convert(wordsFile); // change the state of the game emit( state.copyWith( status: AnagramGameStatus.loaded, words: words, ), ); // reset the game _onRestartGame(emit); } catch (e) { emit( state.copyWith( status: AnagramGameStatus.gameError, ), ); } } Future<void> _onProcessWord( ProcessWord event, Emitter<AnagramState> emit, ) async { try { final word = event.word.trim().toLowerCase(); if (word.isEmpty) { return; } if (_isGoodWord(word) && state.anagrams.contains(word)) { // remove the word from the list of anagrams // add the word to the list of guesses emit( state.copyWith( anagrams: state.anagrams..remove(word), guesses: [...state.guesses, Word(word, isAnagram: true)], ), ); // if there are no more anagrams, the game is over // call _onResetGame to reset the game if (state.anagrams.isEmpty) { add(ResetGame()); } } else { emit( state.copyWith( guesses: [...state.guesses, Word(word)], ), ); } } catch (e) { // show an error message } } FutureOr<void> _onResetGame(ResetGame event, Emitter<AnagramState> emit) { _onGameFinished(); _onRestartGame(emit); } void _onRestartGame(Emitter<AnagramState> emit) { final starterWord = _pickGoodStarterWord(emit); emit( state.copyWith( status: AnagramGameStatus.loaded, currentWord: starterWord, anagrams: _getAnagrams(starterWord), guesses: [], ), ); } void _onGameFinished() { emitPresentation(FinishGuess(_result, state.currentWord)); } List<Word> get _result { // All the anagrams that were not guessed final notGuessedAnagrams = state.anagrams.map(Word.new).toList(); // All the guesses that were made final guesses = state.guesses.where((word) => word.isAnagram).toList(); // return the list of anagrams that were not guessed return [...guesses, ...notGuessedAnagrams]; } /// create a function to find all the anagrams of the target word List<String> _getAnagrams(String targetWord) { // find all the anagrams of the target word final anagrams = <String>[]; // return the list of anagrams return anagrams; } // ignore: unused_element List<String> _getAnagramsWithOneMoreLetter(String targetWord) { final anagrams = HashSet<String>(); // return the list of anagrams return anagrams.toList(); } /// Picks a good starter word for the game. String _pickGoodStarterWord(Emitter<AnagramState> emit) { const word = 'skate'; return word; } /// Checks if the word is a good word. bool _isGoodWord(String word) { return true; } }

• onSetupAnagrams : ファイルを読み取り、単語を分割してリストに追加します。また、現在の単語を検索し、選択した単語のアナグラムを検索して、状態を更新します。

• onProcessWord : これは、ユーザーが推測を入力して状態を更新したときに呼び出されるハンドラーです。
• onReset : 次の単語ボタンをクリックすると呼び出され、ゲームをリセットします。
• isGoodWord : 指定された単語が辞書内に存在し、基本単語の先頭または末尾に文字を追加して形成されていないことを確認します。
• getAnagrams : 指定された単語のすべての可能なアナグラムのリストを作成します。
• getAnagramsWithOneMoreLetter : 指定された単語に 1 文字を追加して形成できるすべての単語のリストを作成します。
• pickGoodStarterWord : 少なくとも希望する数のアナグラムを持つ単語をランダムに選択します。

マイルストーン 1: 必需品

最初のマイルストーンでは、非常にシンプルな実用的なプログラムの作成に重点が置かれます。マイルストーン 2 と 3 で構築される基礎を実装します。

anagram_bloc.dartに取り組みます。

アナグラムを取得

getAnagramsを実装します。これは文字列を受け取り、入力内のその文字列のすべてのアナグラムを検索します。現時点での戦略は単純です。words リスト内の各words列を入力単語と比較して、アナグラムかどうかを判断するだけです。しかし、それをどのように行うのでしょうか。

2 つの文字列が互いにアナグラムであるかどうかを判断するために使用できるさまざまな戦略 (各文字の出現回数を数えるなど) がありますが、ここでは、 Stringを受け取り、同じ文字をアルファベット順に並べた別の文字String (例: "post" -> "post") を返すヘルパー関数 ( sortLettersと呼びます) を作成します。

2 つの文字列がアナグラムであるかどうかを判断するには、それらの長さが同じであるかどうか (速度のため) を確認し、それらの文字の並べ替えられたバージョンが等しいかどうかを確認するだけです。

wordSet と anagramMap

残念ながら、単純な戦略では、このゲームの残りの部分を実装するには時間がかかりすぎます。そのため、 onSetupAnagrams再度検討し、目的に合った方法で単語を格納するデータ構造を見つける必要があります。2 つの新しいデータ構造 ( wordsに加えて) を作成します。

• 単語が有効かどうかを迅速に（O(1)で）検証できるHashSet （ wordSetと呼ばれる）。

• アナグラムをグループ化できるHashMap ( anagramMapと呼ばれます)。これを行うには、キーとして文字列のsortLettersバージョンを使用し、そのキーに対応する単語のリストを値として保存します。たとえば、次の形式のエントリがあるとします: キー: "opst" 値: ["post", "spot", "pots", "tops", ...]。

入力された単語を処理するときに、それぞれの単語に対してsortLettersを呼び出し、 anagramMapにそのキーのエントリがすでに含まれていないかどうかを確認します。含まれている場合は、現在の単語をそのキーのListに追加します。含まれていない場合は、新しい単語を作成し、それに単語を追加して、対応するキーとともにHashMapに格納します。

これが完了すると、マイルストーン 1 は終了です。これで、プログラムをさらに複雑にする 2 番目のマイルストーンに進む準備が整いました。

マイルストーン 1 の解決策

マイルストーン2: 品質の向上

マイルストーン 2 では、選択した単語がアナグラム ゲームに適していることを確認することがすべてです。前のマイルストーンとは異なり、このマイルストーンは 3 つのセクションに分かれています。

isGoodWord

次のタスクは、次の点をチェックするisGoodWord実装することです。

• 指定された単語は有効な辞書単語（つまり、 wordSet内）であり、
• 単語には基本単語が部分文字列として含まれていません。

単語が有効な辞書単語であるかどうかを確認するには、 wordSetを調べて、その単語が含まれているかどうかを確認します。単語に基本単語が部分文字列として含まれていないことを確認するのは、課題として残ります。

getAnagramsWithOneMoreLetter

最後に、文字列を受け取り、その単語に 1 文字を追加することで形成できるすべてのアナグラムを検索するgetAnagramsWithOneMoreLetterを実装します。

必ず新しいList戻り値としてインスタンス化し、指定された単語とアルファベットの各文字をanagramMapのエントリに対して 1 つずつチェックしてください。

また、 onRestartGameを更新して、 getAnagramsではなくgetAnagramsWithOneMoreLetterを呼び出します。

pickGoodStarterWord

ゲームが動作している場合は、 pickGoodStarterWordを実装して、ゲームをさらに面白くします。単語リストからランダムな開始点を選択し、配列内の各単語をチェックして、少なくともminNumAnagramsを持つ単語を見つけます。必要に応じて、配列の先頭への折り返しを必ず処理してください。

3分の2が終わりました。あと1つのマイルストーンと延長が完了です。

マイルストーン2の解決策

マイルストーン 3: リファクタリング

この時点で、ゲームは機能しますが、長い基本単語から始めると、プレイするのがかなり難しくなる可能性があります。これを回避するには、 onSetupGameをリファクタリングして、単語の長さが増加するようにします。

このリファクタリングはonSetupGameから始まります。ここでは、 wordリストを設定するだけでなく、単語の長さをその長さのすべての単語のListにマッピングするHashMap ( sizeToWordsと呼びます) に各単語を保存する必要があります。つまり、たとえば、 sizeToWords.get(4)を呼び出すことで、辞書内のすべての 4 文字の単語を取得できる必要があります。

pickGoodStarterWordでは、検索を長さwordLengthの単語に制限し、完了したらwordLengthを増分します (すでにaxWordLengthに達していない場合)。これにより、次の呼び出しでより大きな単語が返されます。

マイルストーン3の解決策

拡張機能

このアクティビティには (今後のすべてのアクティビティと同様に) オプションの拡張機能がいくつか含まれています。時間に余裕があれば、以下のリストにある拡張機能、または自分で考案した拡張機能を少なくとも 1 つ試してください。

• 2 文字モード: ユーザーが 2 つの文字を追加してアナグラムを作成できるように切り替えます。

• 十分なアナグラムを持たない単語を、可能性のある開始単語のプールから削除して、単語の選択を最適化します。これらの単語は、他の単語のアナグラムとして引き続き使用できるため、 wordSetに残しておく必要があることに注意してください。

• 2 単語モード: ユーザーが単語のペアに 1 文字を追加して、2 つの新しい有効な単語を形成できるようにします。

最後までおめでとうございます！ リスト、HashSet、HashMap が、最適化されたアプリケーションと同様に、Flutter で効率的なデータ処理を実現する仕組みについて学習しました。 これらの構造を理解することで、スケーラブルでパフォーマンスの高いコードを書く際に優位に立つことができます。 さあ、最後まで読んで、自分を褒めてあげてください！ さあ、この知識を実践して、素晴らしいものを作り続けましょう！