Solving seemingly simple math problems using Perl
Group Dynamic
Some mathematical puzzles initially sound easy to solve. Those who actually try, however, will see how quickly the problems can become difficult.
Almost 20 years ago, in the warm summer of 1996, I was earning my money as a developer at a wellknown software company east of Munich when a colleague excitedly reported a simplesounding, but apparently difficulttosolve, problem.
The principal of a school was confronted with the task of dividing nine teachers, 27 female students, and 18 male students into nine groups that would change in such a way that the students would sit in class with different teachers and different classmates each day. Each group was to consist of exactly one teacher, two boys, and three girls, and nine group classes were to take place in different classrooms each day, with each class taught by one of the nine teachers. For how many days could the school go ahead with lessons without the group compositions overlapping? Maybe five?
"Nothing easier than that!" my colleagues and I shouted immediately. We put our project on hold for a while and started to type the first programs on our workstations. Figure 1 shows the first attempt with a simple algorithm that populates nine groups with the same teachers, and notyet allocated students, every day. It keeps a record of who has already been together with whom and simply takes the next student from the notallocated pool if there is an overlap.
The teachers are enumerated with a letter i
(for instructor) from 1 to 9, the boys from b1
to b18
(boy) and the girls with g1
to g27
(girl). For example, teacher i1
conducts the class in group room 1 on the first day with male students b1
and b2
and female students g1
, g2
, and g3
:
day1 group1: i1 b1 b2 g1 g2 g3
On the second day, the algorithm in group 1 detects that boys b1
and b2
were already paired with teacher i1
the previous day and therefore assigns b3
and b5
to the latter (it can't use b4
because b4
attended class with b3
on the day before). And, it works this way for a while.
However, by the end of the second school day, it hits a brick wall, because there are no more female students available for group 7: g19
, g20
, and g21
were already with i7
in group 7 on the first day. Also, g22
, g23
, and g24
were already with b15
in group 8. And, g25
, g26
, and g27
were with b17
in group 9, so the strategy failed miserably!
Seriously Miscalculated
After several failed attempts, it slowly began to dawn on us that this probably required more brain and computing power than first imagined. So, we started to mistreat our brand new HPUX workstations with backtracking algorithms.
To everyone's surprise, however, we did not see any success after a few hours of merciless bruteforce attacks, but instead faced general disillusionment. There were simply too many combinations; attempting to try them all was condemned to failure from the outset. No one, neither young guns nor old hands came up with a solution that worked for more than two and a half days.
Where to look for help? The Internet was still in its infancy in 1996, the web in particular was completely useless, because it mainly consisted of "homepages" that dazzled users with BLINK
tags and "Under Construction" signs. However, Usenet [1] already existed and was mainly frequented by university staff, so I set about trying to describe the problem on the newsgroup rec.puzzles and asking the community for help (Figure 2).
Antique Internet Helps
A few days later, the reply came from a mathematician called Barry Wolk from the University of Manitoba in Canada. He had solved the problem using the heavy weapons of discrete mathematics: a Galois field [2] with nine elements and nine mutually orthogonal Latin squares [3] generated from them.
I quickly manufactured a Perl script from his crystalclear instructions that even nonexperts could understand. The Perl script spat out a solution in a split second for not just five, but nine days (Figure 3). I was the hero!
The Canadian mathematician proposed constructing a set of Latin squares. Even the grumpy 18th century Austrian mathematician Leonhard Euler found pleasure in these structures, which are reminiscent of Sudoku puzzles containing the numbers from 1 to n exactly once for each column or row.
Figure 4 shows a Latin square with 9x9 dimensions with the numbers 1 to 9. Anyone navigating through the columns and rows will easily see that not a single number ever repeats either vertically or horizontally. Back then, Euler filled his squares with Latin capital letters A, B, … , instead of numbers; this is how the "Latin" name came about.
Monster Squares
However, another dimension is still missing for putting students into groups on multiple days. For this, you need a total of n1 of these Latin squares which are orthogonal to one another, which means that the generated combinations are all unique if you compute a monster square from the superpositions of the x/y values of all the squares.
Figure 5, for example, shows four Mutually Orthogonal Latin Squares (MOLS) of the dimension 5x5 [4]. Only the blue marked values are of importance now; I'll explain the black values along the sides in a minute.
All four squares grouped element by element result in the megasquare in Figure 6, whose entries each consist of the corresponding values of the four original squares in the same positions. The values 5, 4, 3, and 2 are in the fourth row of the first column of the original MOLS, for example, which is why the value 5432 is in the same place in the superimposed square.
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you've found an article to be beneficial.
News

Zorin OS 17 Beta Available for Testing
The upcoming version of Zorin OS includes plenty of improvements to take your PC to a whole new level of userfriendliness.

Red Hat Migrates RHEL from Xorg to Wayland
If you've been wondering when Xorg will finally be a thing of the past, wonder no more, as Red Hat has made it clear.

PipeWire 1.0 Officially Released
PipeWire was created to take the place of the ofttroubled PulseAudio and has finally reached the 1.0 status as a major update with plenty of improvements and the usual bug fixes.

Rocky Linux 9.3 Available for Download
The latest version of the RHEL alternative is now available and brings back cloud and container images for ppc64le along with plenty of new features and fixes.

Ubuntu Budgie Shifts How to Tackle Wayland
Ubuntu Budgie has yet to make the switch to Wayland but with a change in approaches, they're finally on track to making it happen.

TUXEDO's New Ultraportable Linux Workstation Released
The TUXEDO Pulse 14 blends portability with power, thanks to the AMD Ryzen 7 7840HS CPU.

AlmaLinux Will No Longer Be "Just Another RHEL Clone"
With the release of AlmaLinux 9.3, the distribution will be built entirely from upstream sources.

elementary OS 8 Has a Big Surprise in Store
When elementary OS 8 finally arrives, it will not only be based on Ubuntu 24.04 but it will also default to Wayland for better performance and security.

OpenELA Releases Enterprise Linux Source Code
With Red Hat restricting the source for RHEL, it was only a matter of time before those who depended on that source struck out on their own.

StripedFly Malware Hiding in Plain Sight as a Cryptocurrency Miner
A rather deceptive piece of malware has infected 1 million Windows and Linux hosts since 2017.