# algorithm – Prompt a function similar to hash, but shorter and without collisions

## Question:

It is required to generate from sequential integers, unique non-sequential n-digit codes. Submit hashes, serials, or coupon numbers. An integer id from 0 to K corresponds to exactly one n-digit code. And it is important that sequential codes differ greatly, and not in one or two characters.

Example:

``````0    KXBR6Z
1    8FLWGG
2    PAZT73
``````

Due to collisions and the brevity of the required codes, popular hash functions are not suitable. No cryptographic strength required. If the villains figure out the algorithm, let them print out all the codes. It is done for beauty. Although, it is also interesting to consider what determines the complexity of guessing the algorithm by X available codes!

Question: tell me the algorithm / function `f(i) = s` to match between the sets `0..K` and n-digit `ABC123XYZ` . The inverse function would be also interesting: `f1(s) = i` to get an integer from the code, or to find out that the code is invalid.

Surely, the problem is not new, but I haven't figured out how to look for an answer. Human translation required. )

PS I'm looking for exactly "mathematics", an algorithm, and not a way to hammer unique values ​​into the database, each time I create a new one, checking the uniqueness.

Substitution ciphers do this well. The first thing you need to do is expand the alphabet (go from numbers to letters, where several letters will correspond to one number). If it is very important for you to hide the original value, then it makes sense to pre-encrypt the data with block or asymmetric encryption.

threw in an example of code with substitution, the result:

``````input/encoded/decoded - 123 / efg / 123
input/encoded/decoded - 456 / hij / 456
input/encoded/decoded - 789 / abc / 789
input/encoded/decoded - 012 / def / 012
input/encoded/decoded - 1157232188 / eoiafgpybl / 1157232188
``````

I am at:

``````import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Substitution {
private static final int NUMBER_COUNT = 10;
private static final int LETTER_COUNT = 26;
private static final int ZERO_ASCII_CODE = 48;
private static final int A_CHAR_ASCII_CODE = 97;

// substitution tables
private static final Map<Character, List<Character>> numToChar = new HashMap<Character, List<Character>>(
NUMBER_COUNT);
private static final Map<Character, Character> charToNum = new HashMap<Character, Character>(
LETTER_COUNT);

// init tables
static {
for (int i = 0; i < NUMBER_COUNT; i++) {
numToChar.put(Character.valueOf((char) (ZERO_ASCII_CODE + i)),
}

// init substitution table
for (int i = A_CHAR_ASCII_CODE; i < A_CHAR_ASCII_CODE + LETTER_COUNT; i++) {

// number = (symbol ascii code) mod 9
Character num = Character
.valueOf((char) (i % NUMBER_COUNT + ZERO_ASCII_CODE));
Character ch = Character.valueOf((char) i);

charToNum.put(ch, num);
}
}

public static void main(String[] args) {
System.out.println("dumping straight substitution table");
for (Character num : numToChar.keySet()) {
System.out.println("num to char - " + num + ", replacements = "
+ numToChar.get(num));
}
System.out.println();
System.out.println("dumping reverse substitution table");
for (Character ch : charToNum.keySet()) {
System.out.println("char to num - " + ch + ", replacements = "
+ charToNum.get(ch));
}

// test
String[] nums = new String[] { "123", "456", "789", "012", "1157232188" };
String r = null;
for (int i = 0; i < nums.length; i++) {
r = decode(nums[i], true);
System.out.println("input/encoded/decoded - " + nums[i] + " / " + r
+ " / " + decode(r, false));
}

}

public static String decode(String input, boolean direction) {
// result buffer
StringBuilder b = new StringBuilder(input.length());

// ensure all latters are in lower case
String data = input.toLowerCase();

// store indexes (determines which letter to use when coding a number)
Map<Character, Integer> indexes = new HashMap<Character, Integer>();

// encode string
for (int i = 0; i < input.length(); i++) {
b.append(decode(indexes, data.charAt(i), direction));
}

return b.toString();
}

// straight - number to letter
// reverse - letter to number
private static Character decode(Map<Character, Integer> indexes, char ch,
boolean direction) {
// convert character
Character character = Character.valueOf(ch);
if (direction) {
// get list
List<Character> list = numToChar.get(character);

// get index to use
Integer index = indexes.get(character);
if (null == index) {
index = Integer.valueOf(0);
}

// update index map
int next = index.intValue() + 1;
if (next == list.size()) {
next = 0;
}

indexes.put(character, Integer.valueOf(next));

return list.get(index);
}

return charToNum.get(character);
}
}
``````

This example is strictly "sharpened" for numbers and letters, but, by analogy, you can make a code that will make substitutions of individual characters and / or their sequences

Scroll to Top