DEV Community: Aravind Pai

PlantUML to compute diagrams!

Aravind Pai — Thu, 25 Jul 2024 04:10:38 +0000

This post is the Part 2 of my fun project on comparing execution times of different languages using the Queen Problem. [Link to Queen Problem Solution and Analysis—Part 1]

Once again, let me first show you some results ...

Solution to the 5-Queen problem

[NOTE: Solution to the 8-Queen problem, which is the canonical version of the N-Queen problem, draws chessboards too small for a teaser. It will appear later in this post, so keep reading. 😆]

... and then take you through the journey.

Content Waypoints

Motivation and Flashback
Solution Explanation
- Hack to use an array
- Hack to draw a chessboard
- Hack to colour the chessboard in alternating colours
- Hack to arrange the solutions
Results
- Solution to the 8-Queens problem
- Solution to the 1-Queens problem
- Solution to the 2-Queens problem
- Solution to the 3-Queens problem
- Solution to the 4-Queens problem
- Solution to the 5-Queens problem
- Solution to the 6-Queens problem
- Solution to the 7-Queens problem
- Solution to the 9-Queens problem
- Solution to the 10-Queens problem
- Solution to the 11-Queens problem
Prior Art
- Test cricket matches hosting data in a hierarchical structure
- Collatz sequence for a range of numbers
- More examples

Motivation and Flashback

In October 2021, I presented PlantUML at Smart Coffee Break, an internal tech talk series at work. While preparing for my talk, I explored PlantUML in depth and discovered its preprocessor. Initially, I was skeptical about its usefulness compared to writing the diagram descriptions directly.

However, a few days later, I realized that the preprocessor could function as a general purpose programming language! This insight inspired me to include some examples of computing diagrams, rather than "just" drawing them, to make my tech talk more entertaining. Thus began my journey of learning the PlantUML preprocessor with fun examples. The Prior Art section showcases some of my creations using the preprocessor as a programming language.

When working on the Queen problem performance analysis recently, I thought it would be cool to draw all those solutions. This was a fine reason to resume my work with the PlantUML preprocessor.

Solution Explanation

In the first step, I decided to translate my C++ recursive solution (described in Part 1) to PlantUML. The only change needed would be to replace printing the solution with drawing the solution. However, this is not so simple, I had to use a few hacks to get it working, which I will describe below.

💬 EXPOSITION

Now, you may say it is more efficient to compute the solutions with C++, then draw them with PlantUML, and you would be right! In a professional environment, I would follow that approach too. However, I use the PlantUML preprocessor for computation for two reasons:

To demonstrate the capability of the PlantUML preprocessor as a full-fledged Turing complete language—a graphical language, if you will.

Solving the problem in another language and only drawing the solution with PlantUML is mundane and boring. This is a fun project and I want to have fun.

Hack to use an array

Preprocessor does not provide an array or hashmap data structure, but the Queen problem solution requires a few arrays. To resolve this, I hacked string concatenation to simulate an array. This hack creates a variable for each array element by concatenating the array name with the index. For example, if we need an array named pawn with index positions 0 to 7, we would create 8 variables, pawn0, pawn1, ..., pawn7.

For convenience and readability, I defined a few helper functions for this hack:

!function $to_variable($array_name, $index)
'This helper function "hacks" an array.
    !return %string($array_name + $index)
!endfunction

!function $get($array_name, $index)
'This helper function gets the value of an array element.
    !return %get_variable_value($to_variable($array_name, $index))
!endfunction

!procedure $set($array_name, $index, $value)
'This helper function sets the value of an array element.
    %set_variable_value($to_variable($array_name, $index), $value)
!endprocedure

Hack to draw a chessboard

To draw a chessboard, I needed a way to draw a two-dimensional grid. I had previously used Salt wireframe diagrams to draw grids, so I started from there. I ran into a problem with the table syntax, which The-Lum addressed in this answer to my question on the PlantUML forum. Their answer helped me fix the syntax, although my eventual solution did not require Salt.

The below code draws the two-dimensional grid, with the key points being:

Draw a vertical bar (|) for each column.
Close a row with a vertical bar (|) and add a newline.

!function $make_chessboard()
    !$diagram = ""
    !$row = 0
    'The below two while loops "hack" a table to draw a chessboard.
    !while $row < $n
        !$column = 0
        !while $column < $n
            !$diagram = $diagram + "| "
            !$column = $column + 1
        !endwhile
        !$diagram = $diagram + " |" + %newline()
        !$row = $row + 1
    !endwhile
    !return $diagram
!endfunction

With the grid layout ready, placing the Queens solution was easy. While drawing the grid, the Unicode character for Queen (♛) is placed at the squares denoted by the row and column numbers in the solution. All other squares are left blank.

Here is the code snippet for placing the Queens:

' snip ... '
!$row = 0
!while $row < $n
    !$column = 0
    !while $column < $n
        ' snip ... '
        !if $get("placed_queen_id", $row) == $column
            !$diagram = $diagram + "♛"
        !endif
        !$column = $column + 1
    !endwhile
    ' snip ... '
    !$row = $row + 1
!endwhile

Hack to colour the chessboard in alternating colours

For the chessboard to look realistic, we need to colour it in alternating light and dark colours. I chose lichess's default chessboard colours. Since lichess is open source 👏, it was easy to obtain the RGB values here.

There are several ways to achieve the alternating colouring. I felt the even-odd approach was the simplest. The preprocessor does not have a modulo division function, hence I used the below integer division hack. [However, this hack may soon be unnecessary if my upcoming pull request to PlantUML gets approved. 😎]

!function $is_odd($number)
'"hack" to check if a number is odd.
'Perform integer division by 2, then multiply by 2. Due to truncation, the value will
'not be equal to the starting number if it is odd.
    !return ($number / 2 * 2) != $number
!endfunction

💭 SIDENOTE

I later remembered I had the same problem during my exploration in 2021. Back then, I had used a more primitive approach. 😇
!function $is_even($num)
    !$num_str = %string($num)
    !$last_digit = %substr($num_str, %strlen($num_str) -1, 1)
    !return ($last_digit == "0"\
            || $last_digit == "2"\
            || $last_digit == "4"\
            || $last_digit == "6"\
            || $last_digit == "8")
!endfunction

Hack to arrange the solutions

The last piece of the puzzle is arranging the multiple solutions in an aesthetically pleasing manner. For this, I used my final hack: make each solution a class in a class diagram! The class name is the solution number while the chessboard showing the solution is a class field.

!procedure $draw_solution()
    class **$solution_counter** {
        $make_chessboard()
    }
    !$solution_counter = $solution_counter + 1
!endprocedure

Results

Below are the solutions, starting with the canonical 8-Queens problem, followed by the others in numerical order.

💡 TIP

Some drawings below are too large to view easily on the webpage. You can open them in a new tab/window or download them for better clarity. The images are in SVG format, allowing you to zoom in for a clearer view.

Solution to the 8-Queens problem

Solution to the 8-Queens problem

[For more clarity, please open image in new tab and zoom in.]

Solution to the 1-Queens problem

Solution to the 2-Queens problem

Solution to the 3-Queens problem

Solution to the 4-Queens problem

Solution to the 5-Queens problem

Solution to the 6-Queens problem

Solution to the 7-Queens problem

Solution to the 9-Queens problem

Solution to the 9-Queens problem

[For more clarity, please open image in new tab and zoom in.]

Solution to the 10-Queens problem

Solution to the 10-Queens problem

[For more clarity, please open image in new tab and zoom in.]

Solution to the 11-Queens problem

Solution to the 11-Queens problem

[For more clarity, please open image in new tab and zoom in.]

Prior Art

Here are some fun and educational examples from my previous exploration in 2021.

Test cricket matches hosting data in a hierarchical structure

Data about Test cricket matches hosted at various grounds is available in JSON format. This data is drawn in a hierarchical structure based on the ground's location (city, country), while also recursively computing the sum of all lower levels.

Hierarchical structure representing Test matches hosting data

[For more clarity, please open image in new tab and zoom in.]

Collatz sequence for a range of numbers

The preprocessor draws separate diagrams showing the Collatz sequence for a range of numbers. The diagrams for two arbitrarily chosen numbers, 18 and 65, are shown below as examples. The complete set of diagrams for numbers 1 to 100 is available in my github repository here.

Collatz sequence for 18

Collatz sequence for 65

More examples

The complete list of examples and more explanation is available in my document Fun and learning with the PlantUML preprocessor.
An overview and demo of PlantUML features is available at PlantUML demo ... and other useful stuff. Example source codes are also available in the github repository.

Queen Problem Solution and Analysis—Part 1

Aravind Pai — Sun, 14 Jul 2024 09:00:23 +0000

This post describes my fun project to solve the Queen problem in multiple languages and compare their execution runtimes.

Let me first show you the results plot ...

Results plot (log scale)

... and then take you through the journey.

Content Waypoints

Motivation and Flashback
Solution Explanation
- Chess Gyan
- Calculation of the diagonal attacks
- Prototype Algorithm
Project Plan
- Storing the result artifacts
Solution Structure
Live Results
- Results interpretation
What's coming up next?

Motivation and Flashback

I have not (yet?) formally studied Computer Science. Rather, I gained my knowledge, skills, and experience through self-learning during my professional career. I discovered the Queen problem about 15 years ago. For several years, I struggled to grasp the backtracking that the solutions mentioned, and particularly, how it was different from brute force.

Then one fateful day in 2018, I found Abdul Bari's YouTube video. His clear explanation helped me easily understand the backtracking. [I binge-watched his other videos later and realized—like many others before and after me—that he is an amazing teacher!]

youtube.com

To verify my understanding, I quickly prototyped a solution in C++ on ideone. [Interestingly, when I accidentally resubmitted the solution recently, it failed to compile due to the constexpr in the template parameter.]

I did nothing more on it until mid-2024. During this time, I gained more experience with Python. I self-learned CI/CD pipelines, both Github Actions and Gitlab CI. A few weeks ago, I started learning Rust. Putting together all these skills seemed like a fun project. Thus, I revisited the Queen problem.

Solution Explanation

I decided to continue with my prototype solution and deal with improving it later.

My prototype solution is based on the following main ideas: [Of course, nothing groundbreaking—thousands of others have solved it before me.]

Pigeonhole Principle: Since each Queen occupies an entire row and column, we cannot place more than one Queen on a row or a column. Conversely, a solution to the N-Queen problem (placing N Queens on an NxN chessboard) cannot have any empty row or column. [As embarassing at it sounds in hindsight, this was a key factor I had failed to realize before, due to which I couldn't differentiate backtracking from brute force.]
Calculating the Queen's attack along the diagonals: Similarly, we cannot place more than one Queen on any diagonal. Calculating the Queen's attack along diagonals is a little more complicated, though. I'll explain my approach to this later, but first, it is time for some chess ज्ञान (gyan). 😆

Chess Gyan

The horizontal rows on a chessboard are called ranks (labelled 1 through 8, bottom to top), while the vertical columns are called files (labelled a through h, left to right). Nonetheless, in this blog post, I'll call them rows and columns, numbered 0 through 7 top to bottom and left to right respectively.
The Queen is the most powerful piece in chess, which controls between 22 and 28 squares on an 8x8 chessboard. That's a control of 34.38% to 43.75% squares. This makes the Queen problem all the more fascinating. Not only can we place 8 Queens on an 8x8 chessboard without an overlap of their controlled squares, but we can do so in 92 different positions!

Queen controls 22 squares from a corner square.

Queen controls 28 squares from a central square.

Calculation of the diagonal attacks

When making my prototype, I referred some previous solutions. Many of them used the Queen's row and column position to check if it would occupy the same diagonal as any of the previously placed Queens. I took a different approach, which is equivalent but felt easier to understand and implement.

I numbered each diagonal, in both directions, so I could maintain an array of flags to represent if a diagonal was already occupied. This is possible because the combination of row and column number satisfy an invariant along each diagonal:

Right diagonals: The sum of the row and column numbers is the same for all squares on a diagonal going up towards the right. This sum can be used to number the diagonals.

Numbering the right diagonals.

Left diagonals: The difference between the row and column numbers is the same for all squares on a diagonal going up towards the left. This difference can be used to number the diagonals.

Numbering the left diagonals.

Prototype Algorithm

Let each Queen move only along one column. The column number also serves as the Queen's identity. Due to the Pigeonhole Principle mentioned earlier, there is a 1:1 mapping between a Queen and a column. [Equivalently, a Queen could move only along a row, but personally, I found the column mapping more intuitive.]

Let each Queen can move only along one column.

Pseudo-code of the prototype algorithm:

  let ROW = 0
  for COLUMN from 0 to N - 1 (both inclusive):
  {
    if ROW, COLUMN, and both diagonals are not occupied:
    {
        (1) place Queen in column number 'COLUMN'
            [For the row number 'ROW', note occupied column number as 'COLUMN']
        (2) mark ROW, COLUMN, and both diagonals as occupied

        if ROW < N:    // there are still unoccupied rows
        {
            let ROW = ROW + 1
            attempt to place a Queen in (ROW + 1) using the approach in (1) and (2)
        }
        else:
        {
            // We checked the occupancy status along rows, columns and diagonals
            // before placing a Queen. If we have reached here, we must have placed
            // N queens successfully without conflict. We found a solution!

            print solution    // occupied column number in each row denotes the solution
        }

        // When we reach here, we have either found a solution or failed to place a
        // Queen in one of the rows without conflict. In either case, we move on to
        // search for the next solution with a clean slate.

        mark ROW, COLUMN, and both diagonals as unoccupied
    }
  }

Implementation Details
- This algorithm naturally leans towards a recursion-based implementation.
- As only one column can be occupied in any row, a one-dimensional array is adequate to note the positions of the Queens. This array also tracks the row occupancy status.
- One-dimensional arrays can denote occupancy of columns and diagonals.
- The left diagonals are numbered from -(N-1) to +(N+1), but arrays in most programming languages support only non-negative indexes. Hence, an offset should be added to bring the left diagonal numbers within the non-negative range.
- The prototype does not store the solutions. Instead, it immediately prints solutions as they are found.

Project Plan

To expand my prototype into a project, I structured the following project plan:

Step 1: Move my 2018 prototype to my Github repository as-is. Rework the solution to accept N as a command-line input instead of the template parameter. Fix some bugs and write better code documentation.
Step 2: Translate the solution into Python and Rust. To level the playing field, if you will, use the same algorithm in both of those languages.
Step 3: Develop scripts to run the solutions and plot the execution times, for both pipeline build and local developer builds.
Step 4: Share the first version of the solutions and performance results publicly, for example, in this blog post! 😆
Step 5: To be revealed in Part 2!

Storing the result artifacts

To have even more fun, I initially considered connecting an external artifact repository to store the result artifacts. Unfortunately, the service I had in mind (the one with the small jumping animal) was too pricey for a hobby project. Hence, I opted to use Github itself as the artifact repository for now, and explore alternatives later.

Execution times would be stored in CSV format, and used to plot graphs in SVG format. By sticking to these text-based formats, I avoid the shenanigans of LFS (Large File Storage)—though BFS (Binary File Storage) would be a more accurate name!

Solution Structure

You can find the project on my Github repository: dragondive/queen [Code reviews and other contributions are welcome!]

Solutions are developed on the develop/queen branch, with a separate directory for each language.
- My unoptimized prototype in C++, the project's lead language, is here.
Github Actions workflows are currently developed directly on the main branch.
- The workflow that measures solution execution times and updates the plots is here.
Solution artifacts are stored on the artifacts branch in the artifacts directory.
Conventional commits, squashed commits and controlled force pushing maintain a clean commit history [With controlled force pushing and interactive rebase, I changed the README.md in the initial commit to README.rst and performed several other commit history cleanups retroactively.]
Tagging the solution versions and running the pipeline jobs is done manually for now.

Live Results

Execution times for each solution language and version are plotted against N, considering average values. Each successful pipeline build updates the plot, making them live plots.

The log scale plot provides a more insightful visualization than the linear scale plot. Nonetheless, the pipeline build updates both the plots:

Live results plot (log scale)

Live results plot (linear scale)

Results interpretation

The most obvious observation is that the C++ solution is the fastest, with Rust close behind, and Python being significantly slower. However, execution time alone should not dictate the choice of language for a particular problem. In my opinion, rules like "never do this" and "always do that" are never helpful and always ignorable.

This topic has sparked much discussion, controversy and misinformation in both developer and sustainability communities. The debate intensified around 2021 when the 2017 research paper Energy Efficiency across Programming Languages reentered prominence. That debate was also a motivator for me to revive this fun project, as both software development and sustainability are of great interest to me. [It took me a few years though to get around to it.] See also Yelle Lieder's blog post on the topic: Sustainability of programming languages: Java rather than TypeScript?

Personally, I enjoy using both C++ and Python, among other languages. My choice of language for a particular problem is made on a case-by-case basis, and depends on several factors:

Learning time: How long it takes me (and my team) to learn the language, or in some cases, its specific "advanced" features.
Development time: The time required to write the code. In some cases, it's no good if your program runs 100 ms faster but takes three more months to develop.
Build time: The time it takes to build and deploy the application.
Debug time: As with everything else in the world, software goes wrong, sooner or later. The amount of time (and occasionally, frustration) it takes to fix problems also matters.
Documentation, testability and team composition: Most non-trivial software is developed by a team of developers. The ease of understanding and reliably modifying others' codes, especially in teams distributed across distant timezones, impacts code quality and value of the application.
Availability of useful libraries and active community: These reduce development and maintenance efforts.
Availability of enthusiastic developers: Ease of finding developers, especially at work, interested in using the language significantly impacts planning. I have encountered scenarios where developers refused job offers or even interview invitations because they didn't want to work with a specific framework being used [which was understandable as the framework was company-proprietary and completely different from the industry standards].
The frequency of use of the application: An application used several times per day benefits from high efficiency. One that is used only a few times per year, perhaps not so much.

Comparing languages solely by execution time without considering the full context is too simplistic. In particular, a "faster" language is not necessarily "greener". As developers, we should make data-driven decisions objectively, based on many diverse but relevant factors, without being biased towards our favourite language or the "flavour of the month" language.

What's coming up next?

I will optimize and partially rework my prototype. Specifically, I'll replace the recursion with iteration and use a more efficient approach for reporting results instead of the repeated I/O access. I will share my findings in the Part 3 of this blog post.

Hang on! What about Part 2? I'll be solving the Queen problem using a fourth language—one that is different, more interesting and more fun than these three. Can you guess which language that will be? Let me know in the comments!

Tools Used

Lichess board editor for the chessboard annotations.
Screenpresso image editor for the numbered circles. The tool doesn't support negative numbers, so I manually edited in the minus sign. [Disclaimer: Not a paid promotion—though I am open to the idea if Screenpresso so wishes. 😉]

My Hello world story

Aravind Pai — Tue, 21 Mar 2023 12:12:03 +0000

hello, world

The famous first words in most people's computer programming journey!

The tradition started with Professor Brian Kernighan's documentation of the B and C programming languages during his time at Bell Labs. Ozaner Hansha describes it in more detail here: On the Origin of "Hello, World!"

My early days of ignorance

When I first read it about 15 years ago in The C Programming Language (perhaps more famously known as the K&R C book), I felt the explanation was either exaggerated or dramatized. As a newborn kid in the IT industry, I had the comfort of working in environments already setup by my predecessors. I couldn't comprehend why it was a big hurdle to execute a simple program.

From my owned copy of the K&R C book, complies with Fair Use.

How experience taught me better

I have since grown out of my ignorance and naivete. Over the years, I have setup many working environments from scratch, many of them in my side-projects (of which, my Jekyll-based blog on Github Pages is a recent example). Those experiences helped me fully appreciate the insights behind that explanation.

In various different scenarios, I have met with each of the mentioned hurdles, and then some more:

On some systems, the seemingly trivial writing of a text file was a big hurdle. My preferred vi editor wasn't available, I didn't have permissions to install it, and at the time, I didn't know how to properly use the other editors.
There have been many occasions of going through dependency hell to setup the required build tools.
On a few occasions, the program executed successfully, but it took me a while to figure out where the program output went.
In the corporate environment, configuring the corporate proxy and fiddling with the VPN settings is frequently a catastrophe by itself.

Hello world, bye cognitive load

In my experience, the greatest value that reaching the Hello world checkpoint brings is it drastically reduces the cognitive load afterwards. Having seen the first program run successfully, I can fully focus on solving the actual problem. My subconscious mind is not worried about how to prepare the setup for seeing the outcome of the code I'm now writing. It is a reassuring feeling that there is already a working environment on which I can try out my solution and get quick feedback.

The many flavours of Hello world

The Hello world checkpoint is frequently more than just printing hello world. For example, in Python, printing hello world is a simple function call with zero ceremony. However, that says nothing about whether your setup can use libraries.

If you intend to write small Python scripts, your Hello world may involve installing one library and calling one of its functions.
For Python projects with more elaborate package organization, you may need a Hello world with two modules or packages, and invoking some functions in one module from the other.

The Hello world would also depend on the specific purpose of the application:

For an application that mainly works with a database, the Hello world would include connecting to a database and executing one read and one write command.
For an application that processes data fetched from API calls, it would include setting up the authentication and making an API call.

Refining Hello world iteratively

The Hello world checkpoint is not cast in stone. It can—and perhaps should—get refined iteratively as one gains more experience and understanding. My current Hello world for Python projects, for example, includes installing a local package using a pyproject.toml file, setting up a simple unit test with pytest, executing the black formatter, and running prospector code analysis. For my future Python projects, I may add or change some things as my own depth of knowledge increases and based on how the Python world changes.

Summary

Hello world is not merely a customary ritual, but is immensely helpful for software developers. It is a method to first get the pieces lined up properly before starting to play the game. This makes their subsequent work much easier by closing off one major source of distractions and frustrations.

Hello world is not one-size-fits-all, it varies from case to case. The developer should seek to constantly refine their Hello world in accordance with changing circumstances and as their own understanding increases.