Web development experience when making a “Make a Word” game

I want to share my experience working on a web project: the implementation of the game “Make a word”. The game is a famous puzzle in which you need to make different words from one long word.

The essence of the article is how and what specifically had to be done in order to bring the whole idea from idea to realization.

Introduction

From time to time I played the “paper” version of this game: we made a long word (for example: “Triceraptos” or “Spaso-Preobrazhensky”) and in 7-10 minutes tried to make as many words as possible from the available letters. Then - in turn they called their words, repeating themselves from their rivals, deleted them. Who has the last words - he won.
')
At the same time, I was looking for options for a project on which I wanted to work together in a complex, to learn web development.

Project requirements were as follows:

• not complicated, but not easy (according to applied skills and technologies);
• with a sale period of about a month (± two weeks so as not to drag out for a long time, but also did not have time to bother)
• using modern technologies and knowledge that I do not know (professional development)
• interesting in essence
• socially useful

With all the seeming simplicity, I could not think of such an idea right away. I considered various options, postponed, wondered - and finally the idea was completely “ripe”, gained clarity and a specific framework. Began a phase of action, deliberation left behind.

Work plan, ideas, ideas, architecture

The general idea was as follows: the system would consist of a backend and a frontend (one or several). The backend is the main burden of calculations, the implementation of logic and mathematics. In the form of input data, a long word comes to it (to solve it), the result of the work is data on possible variants of word combinations existing in Russian. The data is sent in JSON format, the backend works as a REST service.

The frontend accesses the web service with a client request, receives an answer (a set of possible combinations of words), and then implements one or another game interaction with the user.

Currently, there are two API methods implemented on the backend:

http://api.combination.cf/web/words/
http://api.combination.cf/web/description/

The first method gives possible combinations of words, the second is intended to interpret the meaning of a particular word.

1. Backend

1.1. Dictionary, base words

In order to give some words to the user, you must first know them and store them somewhere. Initially I was going to parse some big online dictionary or knowledge base (TSB, Wikipedia, etc.). But, having searched the web, I found already assembled and ready-made explanatory dictionaries in the form of separate files (in text format). Parsing them, of course, was much easier than pumping in several streams and disassembling tens of thousands of pages with raw data. Not to mention that the list of pages for parsing also had to be prepared.

The basis for the game dictionary were the following sources:

1. Ozhegov S. I. Dictionary of the Russian language. OK. 65 000 words / 16th ed., - M .: 1984.
2. Efremova TF Explanatory Dictionary. - M .: Rus. lang., 1996.

In order not to litter the game with various uncommon and rare words, some local, outdated words, adjectives, and multiple forms were rejected. Of course, such a cleaning is not perfect, a more correct result can be obtained by attracting a person to this work (preferably a philologist).

But, well, at least in the database there were no names, surnames, names of cities, countries, etc. (which are in the encyclopedic dictionaries, but not in the explanatory).

If you manage to use all the letters of the original word, then you get an anagram (Anagram is a literary device consisting in rearranging the letters or sounds of a certain word, which results in a different word or phrase).
Example: Australopithecus - water polo player.

1.2. Placements without repetitions

So, we have a base of words (basic dictionary). The word search algorithm is reduced to getting all possible combinations of letters and checking them for availability in the dictionary.

From a long expression you can make short words of different lengths. So, we need combinatorics, the section " Placements without repetitions ." We will search for words from 2 to ("word length" - 1) characters.

Calculate how many options we need to go through with a different length of the original word. Apply the following formula:




The number of placements without repetitions of ten elements by K:

TO	Number of placements
one	ten
2	90
3	720
four	5040
five	30240
6	151200
7	604800
eight	1814400
9	3628800
Total:	6235300

The number of options for checking a word N characters long:
(we sum up all variants of arrangements for the word of the given length)

N	Number of options to check
2	2
3	9
four	40
five	205
6	1236
7	8659
eight	69280
9	623529
ten	6235300
eleven	68588311
12	823059744
15	2246953104075
20	4180411311071440000
25	2.6652630354867E + 25

1.3. Backend, yii2

The backend is implemented in PHP (YII2), MySQL is selected as the database, and caching is Memcached. Everything is simple here: we create a separate module for the API, we write the necessary samples from the database. We give the data in JSON format.

1.4. Optimization

And now the fun begins. It was necessary to optimize the use of resources by the application and to ensure the rapid operation of scripts. We will keep track of memory usage, CPU time, and total script execution time.

Initially optimized work with memory . When transmitting a word eight characters long, the script fell with an error:

PHP Fatal error: Out of memory (allocated 128545216) (tried to allocate 77824 bytes) in /home/xxxxx/public_html

This issue was solved with the use of generators in PHP code. The function began to give the data in parts, and not to accumulate the entire result in itself. The use of the mysql_free_result ($ result) function also helped to free up all the memory occupied by the query result to the database. Memory usage now did not exceed 12-14 MB.

CPU usage . Initially, the CPU load was 100% at all times the script was running. By optimizing the code and splitting requests into more small ones (instead of a small number of large ones), we managed to reduce the load to 60-80%.

Optimization of the script runtime was achieved by using
Memcached to store a list of all the words from the dictionary. Thus, it was possible to remove the load on MySQL and speed up the time for obtaining the result. As an alternative, I rechecked the FileCache file cache as well, but here the results were worse than Memcached.

Optimization results

On a local server (quad-core processor), the search time for all combinations for a 10-letter word is about 22 seconds. In this case, two cores are loaded at 60% - 80% constantly. Another 10-11 seconds is required to check all these combinations in the dictionary (when using Memcached).

Total (for a word of 10 characters): 22 sec. (generation of variants) + 10 seconds (word test) = 32 seconds (total running time).

The time increase is linear: a 9 character word is checked in about 3 seconds, 10 characters in 32 seconds, 11 characters - 350 seconds.

Those. words from 11 letters are no longer available (within a reasonable time) for searching variants (for this algorithm, with a given hardware); 10 characters - more or less tolerated, the limit; 9 and less - fairly quickly, imperceptibly to the user.

2. Frontend

I decided to write two frontends (based on the goals). One in PHP (YII2) - the main working version of the game "Guess the words" with full user functionality; the second on React JS is the same client application, but with reduced functionality (training project for learning JS).

Implementing the functionality of the game in PHP (YII2) + the layout of Bootstrap was simple, fast and pleasant. Programming is a fun, creative lesson: create (and invent, modify on the go) user interaction interfaces, dialog boxes, menu items, buttons; fill pages with content, display informational messages; do design for all this; think over redirects, etc.

But with React JS , I was not so simple. Gaps in knowledge emerged, I had to repeat and go through the basics of JavaScript (in addition to studying the features of the React JS library itself). Sometimes it was necessary to search for several hours how to make the simplest action: download a file, display a block of text. But it was originally planned: knowledge of HTML + Jquery is no longer enough. The result was an assembled build of a static site for uploading to a hosting.

The user of the game has the following interaction options :

1. A word game - a big long word is made up; you can invent options and test them. Found words are saved, statistics are counted, informational messages are issued (the word is found / not found, an error, a combination has already been guessed, etc.). The game can be postponed and continue at another time. You can complete the game or start over.
2. Search for words - all possible combinations of words that can be made up of the initial letters are simply shown. Some kind of "tips" for the game or a separate service.
3. Meaning of the word - the interpretation of the guessed or generated word is shown. Online version of the electronic dictionary.

3. Hosting

I’m not going to write anything special here, it’s necessary to select hosting for a specific project, based on the requirements and capabilities. From what was surprised, almost all companies have high-quality technical support: they answer quickly and in fact, they help to solve the difficulties that have arisen. I learned from my own experience that the work of the sysadmin and devops is necessary and important.

Possible improvements and ideas

You can move in two directions: optimize the backend (make the API work faster) and frontend (expand and grind user interfaces). Both options are promising.

Backend - probably, here PHP capabilities for fast processing of large volumes of digital data will not be enough. It may be appropriate to write some separate fast module or script in another programming language that would quickly do all the calculations. Maybe some of the results can be cached !? For quick dictionary bulkheads, you should probably look in the direction of NoSQL databases. The increase in the services (capabilities) of the system is also appropriate.

By user interface - attracting game design experts as consultants (or sitting on your own and a couple of evenings to think what you can quickly and easily implement, we all played hundreds of different computer games in our lives): thinking through game interfaces, extending services , adding user registration, collecting statistics, high score tables, saved games, etc.

It would not be superfluous to cover the code with tests (acceptance at the frontend and unit tests on the backend). In order not to test everything manually again and again when updating and expanding the functionality.

Conclusion

In general, linguistics and philology, it turns out, is very interesting in itself. I learned a lot about the Russian language in the process of working on the project.

I will cite links to source codes in repositories and links to a working site (hosting is a basic VPS, it is possible that the site “crashes” under “Habraeffect”).

A lot of bugs and inaccuracies were found and corrected in the development process. But, some probably stayed. Please do not judge strictly if you come across them.

Site with a game
Backend repository (API) and frontend (PHP)
Frontend Repository React JS