Aquí te mostramos cómo aprender estructuras de datos de manera divertida con Flutter

Crea juegos y aprende informática.

Las estructuras de datos forman la base del desarrollo eficiente de software, pero los métodos de aprendizaje tradicionales suelen hacer que parezcan abstractas y desconectadas de las aplicaciones del mundo real. Este artículo adopta un enfoque diferente: combina la teoría con la implementación práctica en Flutter para que el aprendizaje sea atractivo y práctico .

Inspirada en Applied CS with Android de Google, esta adaptación para Flutter ofrece una forma interactiva de comprender matrices, conjuntos de hash y mapas de hash . En tan solo 3 o 4 horas , obtendrás una comprensión más profunda de estas estructuras de datos fundamentales y las aplicarás en un contexto significativo.

Ya sea que sea un principiante que busca fortalecer sus fundamentos de informática o un desarrollador experimentado que busca perfeccionar sus habilidades, esta guía ofrece una forma eficiente y agradable de dominar las estructuras de datos esenciales. Comencemos.

Los objetivos de este artículo:

1. Familiarícese con cómo se pueden utilizar los diccionarios para almacenar datos (en este caso, palabras).
2. Utilice mapas hash para almacenar agrupaciones de palabras, que son anagramas.
3. Ser capaz de explicar las limitaciones que enfrentan algunas estructuras de datos cuando trabajan con grandes conjuntos de datos.

Preparación:

Usaremos algunas estructuras de datos en la actividad del taller, por lo que le recomendamos que revise Lists , HashSets y HashMaps . Debería poder insertar, eliminar, acceder y verificar la existencia de elementos con confianza usando estas estructuras de datos en Dart.

Esta es una pequeña introducción a las estructuras de datos, HashSets y HashMap.

Un pequeño ejercicio inicial de calentamiento:

Como ejemplo de actividad que utiliza HashMaps, cree un programa (no necesariamente una aplicación Flutter; la línea de comandos está bien) que tome un código de país de tres letras (ver ISO-3166 ) y devuelva el nombre completo del país al que pertenece.

Por ejemplo:

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

Como extensión, si la entrada tiene más de 3 letras, se considera el nombre de un país y se devuelve el código de tres letras correspondiente. Escriba un mensaje de error útil si la entrada no es un código válido ni el nombre de un país.

Empecemos.

Anagramas

Un anagrama es una palabra formada al reorganizar las letras de otra palabra. Por ejemplo, cinema es un anagrama de iceman .

La mecánica del juego es la siguiente:

1. El juego proporciona al usuario una palabra del diccionario.

   
   

2. El usuario intenta crear tantas palabras como sea posible que contengan todas las letras de la palabra dada más una letra adicional. Tenga en cuenta que agregar la letra adicional al principio o al final sin reordenar las otras letras no es válido. Por ejemplo, si el juego elige la palabra "ore" como inicial, el usuario podría adivinar "rose" o "zero" pero no "sore".

   
   

3. El usuario puede darse por vencido y ver las palabras que no adivinó.

Le proporcionamos un código de inicio que contiene un diccionario de 10,000 palabras y maneja las partes de la interfaz de usuario de este juego y usted será responsable de escribir la clase AnagramBloc que maneja todas las manipulaciones de palabras.

Recorrido por el Código

El código de inicio se compone de tres clases de dardos principales:

anagrams_page.dart

Este es un código simple que representa la pantalla que vemos arriba. Usaremos un bloque para la administración del estado de la pantalla. Comenzaremos configurando el juego lanzando un evento al bloque y definiendo qué sucederá cuando la pantalla responda a diferentes estados del juego.

 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 : muestra la palabra elegida para que el juego forme anagramas.

• _AnagramsTextField : toma la palabra y dispara un evento para procesar la palabra que el usuario ha escrito.

• _GuessListView : muestra las conjeturas que ha introducido el usuario y si son correctas o no.

• _NextWordButton : reinicia el juego y presenta al usuario todos los anagramas de la palabra actual y cuál ha adivinado el usuario.

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 contiene todas las variables de estado necesarias para ejecutar el juego.

• status : indica si el juego se está cargando (inicial), cargado o se produjo algún error.
• words : enumera todas las palabras del archivo word.txt que se cargan desde el archivo.
• anagrams : contiene todos los anagramas de la palabra elegida.
• currentword : palabra elegida de una lista de palabras y palabra a partir de la cual se forman anagramas.
• guesses : Todas las opciones que introduce el usuario y si son correctas o incorrectas.

Llegaremos al resto de los detalles más adelante en el artículo.

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 : lee el archivo, divide las palabras y las agrega a la lista. También busca la palabra actual, busca anagramas para esa palabra elegida y actualiza el estado.

• onProcessWord : este es el controlador que se llama cuando el usuario ingresa una estimación y actualiza el estado.
• onReset : se llama al hacer clic en el botón de la siguiente palabra y reinicia el juego.
• isGoodWord : afirma que la palabra dada está en el diccionario y no se forma agregando una letra al inicio o al final de la palabra base.
• getAnagrams : crea una lista de todos los anagramas posibles de una palabra determinada.
• getAnagramsWithOneMoreLetter : crea una lista de todas las palabras posibles que se pueden formar agregando una letra a la palabra dada.
• pickGoodStarterWord : selecciona aleatoriamente una palabra con al menos la cantidad deseada de anagramas.

Hito 1: Elementos esenciales

El primer hito se centra en la creación de un programa de trabajo muy sencillo. Implementarás las bases que, a su vez, se construirán en los hitos 2 y 3.

Trabajaremos en anagram_bloc.dart .

obtenerAnagramas

Implemente getAnagrams , que toma una cadena y encuentra todos los anagramas de esa cadena en nuestra entrada. Nuestra estrategia por ahora será sencilla: simplemente compare cada cadena en words List con la palabra de entrada para determinar si son anagramas. Pero, ¿cómo lo haremos?

Hay diferentes estrategias que puedes emplear para determinar si dos cadenas son anagramas entre sí (como contar el número de ocurrencias de cada letra), pero para nuestro propósito crearás una función auxiliar (llámala sortLetters ) que toma una String y devuelve otra String con las mismas letras en orden alfabético (por ejemplo, "post" -> "post").

Determinar si dos cadenas son anagramas es entonces una cuestión simple de comprobar que tengan la misma longitud (para mayor velocidad) y comprobar que las versiones ordenadas de sus letras sean iguales.

wordSet y anagramMap

Lamentablemente, la estrategia sencilla será demasiado lenta para que podamos implementar el resto de este juego. Por lo tanto, necesitaremos revisar onSetupAnagrams y encontrar algunas estructuras de datos que almacenen las palabras de maneras que sean convenientes para nuestros propósitos. Crearemos dos nuevas estructuras de datos (además de words ):

• Un HashSet (llamado wordSet ) que nos permitirá verificar rápidamente (en O(1)) si una palabra es válida.

• Un HashMap (llamado anagramMap ) que nos permitirá agrupar anagramas. Para ello, utilizaremos la versión sortLetters de una cadena como clave y almacenaremos una Lista de las palabras que corresponden a esa clave como nuestro valor. Por ejemplo, podemos tener una entrada con el formato: clave: "opst" valor: ["post", "spot", "pots", "tops", ...].

A medida que procesa las palabras de entrada, llame sortLetters en cada una de ellas y luego verifique si anagramMap ya contiene una entrada para esa clave. Si es así, agregue la palabra actual a List en esa clave. De lo contrario, cree una nueva, agregue la palabra y almacénela en el HashMap con la clave correspondiente.

Una vez que hayas completado esto, habrás llegado al final del hito 1. Ahora estás listo para pasar al segundo hito, en el que agregarás más complejidad a tu programa.

Solución al hito 1

Hito 2: Añadir calidad

El objetivo del segundo hito es garantizar que las palabras elegidas sean adecuadas para el juego de anagramas. A diferencia del hito anterior, este se divide en tres secciones.

isGoodWord

Su próxima tarea es implementar isGoodWord que verifica:

• la palabra proporcionada es una palabra válida del diccionario (es decir, en wordSet ), y
• La palabra no contiene la palabra base como subcadena.

Para comprobar si una palabra es válida en el diccionario, se puede consultar wordSet para ver si contiene la palabra. ¡Comprobar que la palabra no contenga la palabra base como subcadena es un desafío!

getAnagramsWithOneMoreLetter

Por último, implemente getAnagramsWithOneMoreLetter , que toma una cadena y encuentra todos los anagramas que se pueden formar agregando una letra a esa palabra.

Asegúrese de crear una nueva List como valor de retorno y luego verifique la palabra dada + cada letra del alfabeto una por una contra las entradas en anagramMap .

Además, actualice onRestartGame para invocar getAnagramsWithOneMoreLetter en lugar de getAnagrams .

pickGoodStarterWord

Si el juego funciona, proceda a implementar pickGoodStarterWord para que el juego sea más interesante. Elija un punto de inicio aleatorio en la lista de palabras y verifique cada palabra en la matriz hasta que encuentre una que tenga al menos minNumAnagrams . Asegúrese de controlar el retorno al inicio de la matriz si es necesario.

¡Ya hemos recorrido dos tercios del camino! Solo falta un hito y la extensión para terminar.

Solución al hito 2

Hito 3: Refactorización

En este punto, el juego funciona, pero puede resultar bastante difícil de jugar si empiezas con una palabra base larga. Para evitarlo, refactoricemos onSetupGame para que proporcione palabras de longitud creciente.

Esta refactorización comienza en onSetupGame , donde además de completar la lista word , también debe almacenar cada palabra en un HashMap (llamémoslo sizeToWords ) que asigna la longitud de la palabra a una List de todas las palabras de esa longitud. Esto significa, por ejemplo, que debe poder obtener todas las palabras de cuatro letras del diccionario llamando a sizeToWords.get(4) .

En pickGoodStarterWord , restrinja su búsqueda a las palabras de longitud wordLength y, una vez que haya terminado, incremente wordLength (a menos que ya esté en axWordLength ) para que la próxima invocación devuelva una palabra más grande.

Solución al hito 3

Extensiones

Esta actividad (como todas las actividades futuras) contiene algunas extensiones opcionales. Si el tiempo lo permite, intente al menos una extensión de la lista que aparece a continuación o una que haya inventado usted mismo.

• Modo de dos letras: cambia para permitir al usuario agregar dos letras para formar anagramas.

• Optimice la selección de palabras eliminando del conjunto de posibles palabras iniciales aquellas que no tengan suficientes anagramas. Tenga en cuenta que esas palabras deben permanecer en wordSet , ya que aún pueden usarse como anagramas en otras palabras.

• Modo de dos palabras: permite al usuario agregar una letra a un par de palabras para formar dos nuevas palabras válidas.

¡Felicitaciones por llegar al final! Has explorado cómo las listas, los conjuntos de hash y los mapas de hash potencian el manejo eficiente de datos en Flutter, tal como lo hacen en cualquier aplicación bien optimizada. Entender estas estructuras te da una ventaja a la hora de escribir código escalable y de alto rendimiento. ¡Así que adelante y date una merecida palmadita en la espalda! Ahora, ¡pon en práctica este conocimiento y sigue creando cosas increíbles!