Berikut Cara Mempelajari Struktur Data dengan Cara Menyenangkan Menggunakan Flutter

Membuat game dan mempelajari Ilmu Komputer.

Struktur data membentuk fondasi pengembangan perangkat lunak yang efisien, namun metode pembelajaran tradisional sering kali membuatnya terasa abstrak dan terputus dari aplikasi dunia nyata. Artikel ini mengambil pendekatan yang berbeda — menggabungkan teori dengan implementasi langsung di Flutter untuk membuat pembelajaran menarik dan praktis .

Terinspirasi oleh Applied CS milik Google dengan Android , adaptasi untuk Flutter ini menyediakan cara interaktif untuk memahami Array, HashSet, dan HashMap . Hanya dalam waktu 3–4 jam , Anda akan memperoleh pemahaman yang lebih mendalam tentang struktur data fundamental ini sambil menerapkannya dalam konteks yang bermakna.

Baik Anda seorang pemula yang ingin memperkuat dasar-dasar CS atau pengembang berpengalaman yang ingin menyempurnakan keterampilan Anda, panduan ini menawarkan cara yang efisien dan menyenangkan untuk menguasai struktur data penting. Mari kita mulai.

Tujuan Artikel Ini:

1. Biasakan diri Anda dengan bagaimana kamus dapat digunakan untuk menyimpan data (dalam hal ini kata-kata).
2. Gunakan peta hash untuk menyimpan pengelompokan kata, yang merupakan anagram.
3. Mampu menjelaskan keterbatasan yang dihadapi beberapa struktur data saat bekerja dengan kumpulan data besar.

Persiapan:

Kami akan menggunakan beberapa struktur data dalam aktivitas lokakarya, jadi harap tinjau Lists , HashSets , dan HashMaps . Anda seharusnya dapat dengan yakin memasukkan, menghapus, mengakses, dan memeriksa keberadaan elemen menggunakan struktur data ini di Dart.

Ini adalah pengenalan singkat tentang struktur data, HashSet dan HashMap.

Latihan pemanasan awal yang kecil:

Sebagai contoh aktivitas menggunakan HashMaps, buatlah sebuah program (tidak harus aplikasi Flutter — baris perintah pun tidak masalah) yang akan menerima kode negara tiga huruf (lihat ISO-3166 ) dan mengembalikan nama lengkap negara tempat kode tersebut berada.

Misalnya:

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

Sebagai tambahan, jika input lebih dari 3 huruf, anggap itu sebagai nama negara, dan kembalikan kode tiga huruf untuknya. Tulis pesan kesalahan yang membantu jika input bukan kode yang valid atau nama negara.

Mari kita mulai.

Anagram

Anagram adalah kata yang dibentuk dengan menata ulang huruf-huruf dari kata lain. Misalnya, cinema adalah anagram dari iceman .

Mekanisme permainannya adalah sebagai berikut:

1. Permainan ini memberi pengguna sebuah kata dari kamus.

   
   

2. Pengguna mencoba membuat kata sebanyak mungkin yang mengandung semua huruf dari kata yang diberikan ditambah satu huruf tambahan. Perhatikan bahwa menambahkan huruf tambahan di awal atau akhir tanpa menyusun ulang huruf lainnya tidak valid. Misalnya, jika permainan memilih kata 'ore' sebagai kata pembuka, pengguna mungkin menebak 'rose' atau 'zero' tetapi tidak 'sore'.

   
   

3. Pengguna dapat menyerah dan melihat kata-kata yang tidak mereka tebak.

Kami telah memberi Anda beberapa kode awal yang berisi kamus 10.000 kata dan menangani bagian UI permainan ini dan Anda akan bertanggung jawab untuk menulis kelas AnagramBloc yang menangani semua manipulasi kata.

Tur Kode

Kode permulaan terdiri dari tiga kelas dart utama:

anagrams_page.dart

Ini adalah kode sederhana yang mewakili layar yang kita lihat di atas. Kita akan menggunakan blok untuk manajemen status layar. Kita akan mulai dengan menyiapkan permainan dengan menjalankan suatu peristiwa ke blok dan menentukan apa yang akan terjadi ketika layar merespons berbagai status permainan.

 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 : menampilkan kata yang dipilih untuk permainan untuk membentuk anagram.

• _AnagramsTextField : menerima kata dan memicu peristiwa untuk memproses kata yang diketik pengguna.

• _GuessListView : menampilkan tebakan yang dimasukkan pengguna dan apakah tebakannya benar atau tidak.

• _NextWordButton : mengatur ulang permainan dan menyajikan kepada pengguna semua anagram dari kata saat ini dan kata mana yang telah ditebak pengguna.

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 menampung semua variabel status yang dibutuhkan untuk menjalankan permainan.

• status : berlaku apakah permainan sedang dimuat (awal), dimuat, atau terjadi kesalahan.
• words : Mencantumkan semua kata dari file word.txt yang dimuat dari file.
• anagrams : menampung semua anagram untuk kata yang dipilih.
• currentword : kata yang dipilih dari daftar kata dan kata untuk membentuk anagram.
• guesses : Semua pilihan yang dimasukkan pengguna dan apakah tebakannya benar atau salah.

Kami akan membahas rincian selengkapnya di artikel berikutnya.

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 : Membaca berkas, membagi kata-kata, dan menambahkannya ke dalam daftar. Ia juga menemukan kata saat ini, menemukan anagram untuk kata yang dipilih, dan memperbarui statusnya.

• onProcessWord : Ini adalah pengendali yang dipanggil saat pengguna memasukkan tebakan dan memperbarui status.
• onReset : Dipanggil saat mengklik tombol kata berikutnya dan mengatur ulang permainan.
• isGoodWord : Menegaskan bahwa kata yang diberikan ada dalam kamus dan tidak dibentuk dengan menambahkan huruf di awal atau akhir kata dasar.
• getAnagrams : Membuat daftar semua kemungkinan anagram dari kata tertentu.
• getAnagramsWithOneMoreLetter : Membuat daftar semua kemungkinan kata yang dapat dibentuk dengan menambahkan satu huruf ke kata yang diberikan.
• pickGoodStarterWord : Pilih secara acak kata dengan setidaknya jumlah anagram yang diinginkan.

Tahap 1: Hal-hal penting

Tahap pertama difokuskan pada pembuatan program kerja yang sangat sederhana. Anda akan menerapkan fondasi yang selanjutnya akan dibangun di Tahap 2 dan 3.

Kami akan mengerjakan anagram_bloc.dart .

dapatkanAnagram

Terapkan getAnagrams yang mengambil string dan menemukan semua anagram dari string tersebut dalam input kita. Strategi kita untuk saat ini akan mudah: cukup bandingkan setiap string dalam daftar words dengan kata input untuk menentukan apakah itu anagram. Namun, bagaimana kita melakukannya?

Ada beberapa strategi berbeda yang bisa Anda terapkan untuk menentukan apakah dua string merupakan anagram satu sama lain (seperti menghitung jumlah kemunculan setiap huruf), tetapi untuk tujuan kita, Anda akan membuat fungsi pembantu (sebut saja sortLetters ) yang mengambil sebuah String dan mengembalikan String lain dengan huruf yang sama dalam urutan abjad (misalnya "post" -> "post").

Menentukan apakah dua string merupakan anagram adalah masalah sederhana dengan memeriksa bahwa keduanya memiliki panjang yang sama (demi kecepatan) dan memeriksa bahwa versi huruf yang diurutkan adalah sama.

wordSet dan anagramMap

Sayangnya, strategi langsung ini akan terlalu lambat bagi kita untuk menerapkan sisa permainan ini. Jadi, kita perlu meninjau kembali onSetupAnagrams kita dan menemukan beberapa struktur data yang menyimpan kata-kata dengan cara yang sesuai untuk tujuan kita. Kita akan membuat dua struktur data baru (selain words ):

• HashSet (disebut wordSet ) yang memungkinkan kita dengan cepat (dalam O(1)) memverifikasi apakah suatu kata valid.

• HashMap (disebut anagramMap ) yang akan memungkinkan kita mengelompokkan anagram. Kita akan melakukannya dengan menggunakan versi sortLetters dari string sebagai kunci dan menyimpan Daftar kata-kata yang sesuai dengan kunci tersebut sebagai nilai kita. Misalnya, kita mungkin memiliki entri dalam bentuk: kunci: "opst" nilai: ["post", "spot", "pots", "tops", ...].

Saat Anda memproses kata-kata masukan, panggil sortLetters pada masing-masing kata, lalu periksa apakah anagramMap sudah berisi entri untuk kunci tersebut. Jika ya, tambahkan kata saat ini ke List pada kunci tersebut. Jika tidak, buat kata baru, tambahkan kata tersebut ke dalamnya, dan simpan di HashMap dengan kunci yang sesuai.

Setelah Anda menyelesaikan ini, Anda telah mencapai akhir Milestone 1! Anda sekarang siap untuk beralih ke milestone kedua, di mana Anda akan menambahkan lebih banyak kompleksitas ke program Anda.

Solusi untuk milestone 1

Tahap 2: Menambahkan Kualitas

Tahap 2 adalah tentang memastikan bahwa kata-kata yang dipilih cocok untuk permainan anagram. Tidak seperti tahap sebelumnya, tahap ini dibagi menjadi tiga bagian.

isGoodWord

Tugas Anda selanjutnya adalah mengimplementasikan isGoodWord yang memeriksa:

• kata yang diberikan adalah kata kamus yang valid (yaitu, dalam wordSet ), dan
• kata tersebut tidak mengandung kata dasar sebagai sub-string.

Memeriksa apakah sebuah kata merupakan kata kamus yang valid dapat dilakukan dengan melihat wordSet untuk melihat apakah kata tersebut mengandung kata tersebut. Memeriksa bahwa kata tersebut tidak mengandung kata dasar sebagai substring merupakan tantangan tersendiri!

getAnagramsWithOneMoreLetter

Terakhir, terapkan getAnagramsWithOneMoreLetter yang mengambil string dan menemukan semua anagram yang dapat dibentuk dengan menambahkan satu huruf ke kata tersebut.

Pastikan untuk membuat List baru sebagai nilai pengembalian Anda, lalu periksa kata yang diberikan + setiap huruf alfabet satu per satu terhadap entri di anagramMap .

Selain itu, perbarui onRestartGame untuk memanggil getAnagramsWithOneMoreLetter dan bukan getAnagrams .

pickGoodStarterWord

Jika permainan Anda berjalan, lanjutkan dengan menerapkan pickGoodStarterWord untuk membuat permainan lebih menarik. Pilih titik awal acak dalam Daftar kata dan periksa setiap kata dalam array hingga Anda menemukan kata yang memiliki setidaknya minNumAnagrams . Pastikan untuk menangani pembungkusan ke awal array jika diperlukan.

Dua pertiga perjalanan telah dilalui! Tinggal satu tonggak pencapaian dan perpanjangan sebelum Anda selesai.

Solusi untuk milestone 2

Tahap 3: Refaktorisasi

Pada titik ini, permainan sudah berfungsi tetapi bisa jadi cukup sulit dimainkan jika Anda memulai dengan kata dasar yang panjang. Untuk menghindari hal ini, mari kita lakukan refaktor onSetupGame untuk menghasilkan kata-kata dengan panjang yang bertambah.

Refaktor ini dimulai di onSetupGame , di mana selain mengisi Daftar word , Anda juga harus menyimpan setiap kata dalam HashMap (sebut saja sizeToWords ) yang memetakan panjang kata ke List semua kata dengan panjang tersebut. Ini berarti, misalnya, Anda seharusnya bisa mendapatkan semua kata berhuruf empat dalam kamus dengan memanggil sizeToWords.get(4) .

Dalam pickGoodStarterWord , batasi pencarian Anda pada kata-kata dengan panjang wordLength , dan setelah selesai, tingkatkan wordLength (kecuali jika sudah mencapai axWordLength ) sehingga pemanggilan berikutnya akan mengembalikan kata yang lebih besar.

Solusi untuk milestone 3

Ekstensi

Aktivitas ini (seperti semua aktivitas mendatang) berisi beberapa ekstensi opsional. Jika waktu memungkinkan, cobalah setidaknya satu ekstensi dari daftar di bawah ini atau ekstensi yang Anda buat sendiri.

• Mode dua huruf: beralih ke memungkinkan pengguna menambahkan dua huruf untuk membentuk anagram.

• Optimalkan pemilihan kata dengan menghapus kata-kata yang tidak memiliki cukup anagram dari kumpulan kata-kata awal yang memungkinkan. Perhatikan bahwa kata-kata tersebut harus tetap berada di wordSet karena masih dapat digunakan sebagai anagram dalam kata-kata lain.

• Mode dua kata: Memungkinkan pengguna menambahkan satu huruf ke sepasang kata untuk membentuk dua kata baru yang valid.

Selamat karena berhasil sampai akhir! Anda telah mempelajari bagaimana Lists, HashSets, dan HashMap mendukung penanganan data yang efisien di Flutter, seperti halnya di aplikasi yang dioptimalkan dengan baik. Memahami struktur ini memberi Anda keunggulan dalam menulis kode yang dapat diskalakan dan berkinerja baik. Jadi, teruslah maju dan berikan diri Anda tepukan di punggung yang pantas! Sekarang, terapkan pengetahuan ini dan teruslah membangun hal-hal yang menakjubkan!