Generate in Perl the numbers with digits in order

If you try to count using only numbers with all its digits in ascending order, you will get this:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 123, ...

This sequence is registered in OEIS as A009994 - Numbers with digits in nondecreasing order.

Note that all the jumps are located after the last digit becomes 9, because the digit 0 cannot appear after the first occurrence. Considering this, I have created a little Perl program to generate it:

#!/usr/bin/perl
for($_="";;) {
    s/([0-8]?)(9*)$/$2?($1?$1+1:1)x(length($2)+1):length($1)?$1+1:0/e;
    print "$_\n";
}

On each iteration, the regular expression is applied to the variable $_ generating the next number, following this algorithm:

• If there are one or more 9's at the end then:
• If there is a digit X<9 just before the 9's then that digit X and those 9's are all replaced with the digit X+1 repeated as many times as the number of 9's plus one, for example 22499=>22555
• If there is no digit just before the 9's then is considered that the digit is 0 and the same operation is done, for example 999=>1111
• If there are no 9's at the end then:
• If there is a digit X at the end then the digit X is replaced with the digit X+1, for example 133=>134
• If there is no digit in the number then the digit 0 is inserted

I tried to do the code as easy to understand as I could, so you can use it if you need without problem ;-). Thanks for reading!

Program to find the maximum multiplicative persistence

After watching an interesting video from Numberphile about multiplicative persistence, one of the basic operations in Persistence of numbers, I thought that I wanted to make it by myself in Perl, so here you have the program multdigits.pl:

$ perl multdigits.pl -h

Usage: perl multdigits.pl [OPTION]...
Multiply the digits of each integer recursively until get one digit,
printing all the products obtained and counting the number of them.
See https://oeis.org/A003001 for more information about the sequence.

-r, --radix=NUM   use the NUM radix or base, 10 by default
-s, --sorted      use only numbers with sorted digits as optimization
-m, --mindigit=N  when sorted, minimum digit to optimize, 1 by default
-a, --all         prints all instead of only those with more products
-o, --others      prints others with same product number, not 1st only
-d, --dots        print dots when reaches a number with one digit more
-i, --initial=NUM initial number to begin the search, 0 by default
-h, --help        print the help and exits

Faster options: perl multdigits.pl --sorted --mindigit=2 --indicator
Copyright 2021 Carlos Rica <jasampler AT gmail DOT com>

Using the faster options it finds pretty fast the smallest integer (277777788888899) having the maximum multiplicative persistence known (11) for base 10, and then the program cannot reach numbers much bigger than that, but it can do it in any base, and also it can show other numbers with the same maximum multiplicative persistence, which give interesting information about the repetition of the longest sequences of products. 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!

Repeating strings with a separator in Java

The problem of joining strings with a separator is a very common one in programming, but is surprising the number of solutions that different programmers find to that simple task.
Recently I had to repeat a given string ("?" for example) a given number of times but adding a separator between each string ("," for example). I searched for that code in other places of the project and I found many ways, including these:

if (n > 0) {
 for (int i = 1; i < n; i++) {
  buf.append("?,");
 }
 buf.append("?");
}

if (n > 0) {
 for (int i = 0; i < n; i++) {
  buf.append("?,");
 }
 buf.setLength(buf.length() - 1);
}

for (int i = 0; i < n; i++) {
 buf.append("?");
 if (i < n - 1) {
  buf.append(",");
 }
}

boolean first = true;
for (int i = 0; i < n; i++) {
 if (first) {
  first = false;
 } else {
  buf.append(",");
 }
 buf.append("?");
}

To stop this madness, I decided to create a method for reducing all those variations to simpler and less error-prone calls:

/**
 * Appends a string to a buffer a specified number of times,
 * optionally inserting another string as a separator.
 *
 * @param sb The buffer that will have the string appended, if null a new one is created.
 * @param str The string to append.
 * @param n The number of times that the string will be appended.
 * @param sep An optional separator appended between two strings.
 *
 * @return The specified buffer with the string appended or a new one if it was null.
 */
public static StringBuilder repeatAppend(StringBuilder sb, String str, int n, String sep) {
  if (sb == null) {
    sb = new StringBuilder();
  }
  if (n > 0) {
    sb.append(str);
    if (sep != null) {
      for (int i = 1; i < n; i++) {
        sb.append(sep).append(str);
      }
    } else {
      for (int i = 1; i < n; i++) {
        sb.append(str);
      }
    }
  }
  return sb;
}

Be free to use it in your project and happy coding!

Update: Apache Commons StringUtils.repeat(str, sep, n) and Java Collections.nCopies(n, str) with String.join(sep, collection) are alternatives to this method, but our method allows adding to an existing StringBuilder and the others need to create it and destroy it for that. Added return sb; to allow an inline use.

Java class for faster searching of substrings in HashMap

Creating objects in Java requires the allocation of system memory, which is a very complex operation, so many algorithms will be faster when it is avoided. This Substring class allows you to search a portion of a String in a HashMap (one with String keys) without having to create any object. Every time the String.substring method is called, a new object is allocated for the substring (only the internal array is shared), so the solution is searching in the HashMap without using a real String as the key, which can be 2 times faster:

...
Substring substr = new Substring();
for (...) { //lots of repetitions
    String str = ...; int start = ...; int end = ...;
    //obj = hmap.get(str.substring(start, end)); //before
    obj = hmap.get(substr.setSubstring(str, start, end));
    if (obj != null) { ... }
}

Because the Java memory management is so efficient, the use of this class will only be faster if your program needs to search for thousands of substrings and you reuse the same Substring object. A similar idea could also be applied to search for the uppercase version of a String in a HashMap without creating new objects (when calling to String.toUpperCase a new object is created if a lowercase character is found). This one is left as an exercise for the reader. Enjoy!

Javascript Text Replacing Tool

JS Replace is a simple tool for programmers to copy&paste multiple text lines and make automatically changes on all of them by editing the Javascript code box. Tired of building throw-away scripts or complex SQL queries or repetitive Spreadsheet formulas to make simple changes on many rows of data, I developed a simple but powerful javascript tool to assist in such tasks. Use it!