Using jugs of known capacities to get certain quantity

Suppose you only have a few containers of known capacities for measuring quantities, for example two jugs of 5 and 7 litres of capacity respectively, and you want to use them to obtain exactly 1 litre, for example. Can you do it?

To solve this kind of problems, I wrote a simple Perl program, jugs.pl, that explores the solutions using a brute-force backtracking algorithm limiting its recursivity level for finding the solutions with minimum steps.

There are two versions of these problems, one having a limited quantity of the substance to be moved from one jug to another, and other having an unlimited quantity available to fill any jug and discard it. My program only supports the first version, since the second one can be simulated by creating one jug filled with a large quantity that represents the source and sink of the substance, for example:

This way you can use the program to print a solution for the problem:

$ perl jugs.pl 20,7,5 20,0,0 1
(12) (7) (1)    1->3 3->2 1->3 3->2 2->1 3->2 1->3 3->2
$ perl jugs.pl
Use: perl jugs.pl M1,M2,...,MX I1,I2,...,IX N [NUMSTEPS]
Minimum steps to obtain N units in one of X jugs
given the Maximum and Initial quantity for each jug.

This way you can explore different configurations to learn more from the problem, even setting the number of steps of the solutions. Enjoy!

How do I solve the puzzle 2048

The game 2048 is an entertaining one, despite its simple rules. You can play it from your internet browser in many websites by searching 2048 in any search engine, or by installing an app in your smartphone.

I'm sure that better strategies can be found, but this is what worked for me: Maintain always the biggest numbers in a line at one side of the board, in ascending order, for example:

Having this, all you have to do is increase the numbers of this line in a progressive way, in ascending order, avoiding separate the line from the border and maintaining the biggest number in the corner, so you can use the rest of the space to work.

In order to maintain this structure, is important to have this line complete with different numbers all the time, so you can move the rest of the numbers without affecting it. If the line is altered, as when is temporarily shortened at the minor side after merging two numbers, or if you are forced to separate the line from the border, the structure must be recovered as soon as possible, filing the gaps and restoring the order to make it easier.

I hope this advice helps you to enjoy it even more. Happy game!

Magic squares generator in C

2021-11-10: NOTE: I rewrote the program to make it faster in magic-square.

A magic square is a table with equal number of rows and columns that is filled with all the numbers from 1 to NxN (being N the number of rows) in a way that verifies that the sum of the numbers in any row, in any column and in any of the two diagonals gives the same result in all cases, which is called the magic constant. If you choose a different initial number than 1 for filling the square (even zero or negative) and a different increment than 1 to get the following numbers, you will also get the same number of magic squares although the magic constant will change.

Because by rotation or reflection of a magic square you can get other 8 magic squares, only one of those variations (or trivial solutions) is counted. One magic square of size 1x1 exists, zero magic squares of size 2x2 exist and one magic square of size 3x3 exist (with 8 rotations and/or reflections) whose lines sum 15. If you choose the magic square of size 3x3 with the minimum corners, you get this one (printed by my magic square generator):

 2 | 9 | 4 
---+---+---
 7 | 5 | 3 
---+---+---
 6 | 1 | 8 

Exist 880 magic squares of size 4x4 (7040 if you count the trivial solutions) with sum 34, and the magic squares of size 5x5 with sum 65 are many many more, so I created this magic square generator to count them and verify the number of magic squares that others found. Because that number is so big and the program cannot generate all magic squares in a short time, you can can restart the counting from any point by choosing the numbers of the corners with the -c option, although it only accepts ordered numbers for the initial corners. The minimum corners that I have found that generate solutions is this:

$ ./magic-square -c1,2,5,22 5
  1 | 18 | 20 | 24 |  2 
----+----+----+----+----
 23 |  8 |  6 | 12 | 16 
----+----+----+----+----
 19 |  3 | 25 |  7 | 11 
----+----+----+----+----
 17 | 21 |  4 |  9 | 14 
----+----+----+----+----
  5 | 15 | 10 | 13 | 22 
...

To stop the program you can hit Control+C or wait until it reaches the last corners 22,23,24,25. The available options are shown by executing the program without arguments. The -q option counts the solutions without printing them. Happy searching!