I can define a word as being a set of tuples formed by character/position. Thus, the word banana
would have the following mathematical representation:
{
('b',0),
('a',1),
('n',2),
('a',3),
('n',4),
('a',5)
}
I can change the definition a little bit so that each letter is mapped to a set of positions; so, banana
would look like this:
{
('b',{0}),
('a',{1,3,5}),
('n',{2,4})
}
Something interesting about this definition is that if my letter is not in the word, I can associate it with the empty set:
{
('a',{1,3,5}),
('b',{0}),
('c',{}),
('d',{}),
('e',{}),
('f',{}),
('g',{}),
('h',{}),
('i',{}),
('j',{}),
('k',{}),
('l',{}),
('m',{}),
('n',{2,4}),
('o',{}),
('p',{}),
('q',{}),
('r',{}),
('s',{}),
('t',{}),
('u',{}),
('v',{}),
('w',{}),
('x',{}),
('y',{}),
('z',{})
}
This type of data structure, from a key map to a set of elements, is called multimope. In general, multimapa has two operations: insert value and redeem set.
So, in the multimap of banana
(hereafter referred to as mm_banana
), we can add s
in position 6
:
mm_banana.put('s', 6)
// conteúdo de mm_banana modificado sem conjuntos vazios:
{
('a',{1,3,5}),
('b',{0}),
('n',{2,4}),
('s',{6})
}
If we add 's',6
, 'e',7
and 's',8
to mm_banana
, would look like this:
mm_banana.put('s', 6)
mm_banana.put('e', 7)
mm_banana.put('s', 8)
// conteúdo de mm_banana modificado sem conjuntos vazios:
{
('a',{1,3,5}),
('b',{0}),
('e',{7}),
('n',{2,4}),
('s',{6,8})
}
The decimal representation of a number is a word multimope (as described above), the key alphabet being the decimal digits.
To, from any number x
, obtain its decimal representation, we make successive divisions and store the rest. For the sake of simplicity, let’s consider writing the word decimal in little-endian, where the least significant comes first. Thus, the number 0x10
has its representation in decimal word little-endian 61
. The following Python code below demonstrates this:
def representacao_base(x, base):
digit_pos = 0
while (x > 0):
digito = x % base
print("digito %d, posição %d" % (digito, digit_pos));
x //= base
digitPos += 1
representacao_base(0x10, 10)
See working on ideone.
Did you notice that I wrote generally for any basis? It is, the advantage of this is that we can verify if a number is Picua on any further basis. Then, 12 would be represented as 0011
on base 2 using little-endian. The endianism does not influence the decision of the number to be Capicua or not, just as writing a contrary word does not influence the fact whether or not it is palíndrome.
To detect that a number is Picua, we use the above algorithm to dismember it and put each digit as the key of the multimapa, each position as the value being inserted into the multimapa. In Java, I achieved this in the following way:
public class Multimapa {
Set<Integer>[] pos;
int size;
int base;
private void initPos(int base) {
pos = new HashSet[base];
for (int i = 0; i < base; i++) {
pos[i] = new HashSet<>();
}
}
public Multimapa(int n, int base) {
this.base = base;
initPos(base);
if (n == 0) {
pos[0].add(0);
size = 1;
return;
}
if (n < 0) {
n = -n;
}
int digitPos = 0;
while (n > 0) {
int digit = n % base;
pos[digit].add(digitPos);
n /= base;
digitPos++;
}
size = digitPos;
}
}
Note that since the key is a digit, and a digit in turn is an integer, the multimope is provided by the attribute pos
; pos[7]
will get the positions in little-endian that digit 7 occupies in the base passed. Detail: the key is an integer and the value is a set (set in English means ensemble in Portuguese, in the mathematical context) of integers.
Thus, to demonstrate that the class Multimapa
behaves like the multimope data structure described above, I need to show that it supports the same insertion and rescue operations.
The rescue operation is simple. Given a digit d
, pos[d]
redeems the matching set. To add the position p
to the digit d
, just do pos[d].add(p)
. Note that this is an idempotent operation, so pos[d].add(p);
has the same effect as pos[d].add(p); pos[d].add(p); pos[d].add(p);
.
Remember the word representation with multimope using empty set for the non-existence of that letter in the word? We are using the same concept here, to facilitate the rescue and addition operations without requiring further negotiations or offending the definition.
To determine whether the number is repeated, we can verify that it has more than one nonzero digit. To do this, simply iterate on the digits and check the size of the sets. If there is only one digit of non-zero size, then the number is repeated. To detect if it is not repeated, just do the logical inversion. Since there is no number option without digit, then the minimum of digits with at least one position in the number is 1. Therefore, the negation of being number with a single digit is having the count > 1
.
private static boolean ehNaoRepetido(Multimapa mm) {
int nDigitosDistintos = 0;
for (int i = 0; i < mm.base; i++) {
nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
}
return nDigitosDistintos > 1;
}
To check if a number is Picua in the defined base, we need to ensure that every digit in the position p
has another digit in the specular position p'
. A special case is the number of the intermediate position with odd-sized numbers: it is its own to speculate, so it can be ignored.
The relationship between p
, p'
and the size size
of the number is:
p + p' = size - 1
||
\/
p' = size - 1 - p
The intermediate position t
, which will be ignored, is calculated thus:
t = size % 2 == 1? size/2: -1;
As there are only filled positions from 0, placing -1 will ensure that t
will always be ignored for numbers of an even size of digits.
Therefore, the following verification deals with this:
private static boolean ehCapicua(Multimapa mm) {
int somaSimetrica = mm.size - 1;
int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;
for (int d = 0; d < mm.base; d++) {
for (Integer p: mm.pos[d]) {
// só tenta verificar se tem o complemento se e somente se não é ignorado
if (p != posIgnorada) {
int posComplemento = somaSimetrica - p;
// se não existe o dígito na posição complementar, então não é capicua
if (!mm.pos[d].contains(posComplemento)) {
return false;
}
}
}
}
return true;
}
Follow the complete code used to verify if a number is Picua not repeated in the given bases:
package capicua;
import java.util.HashSet;
import java.util.Set;
public class Multimapa {
Set<Integer>[] pos;
int size;
int base;
private void initPos(int base) {
pos = new HashSet[base];
for (int i = 0; i < base; i++) {
pos[i] = new HashSet<>();
}
}
public Multimapa(int n, int base) {
this.base = base;
initPos(base);
if (n == 0) {
pos[0].add(0);
size = 1;
return;
}
if (n < 0) {
n = -n;
}
int digitPos = 0;
while (n > 0) {
int digit = n % base;
pos[digit].add(digitPos);
n /= base;
digitPos++;
}
size = digitPos;
}
public static void main(String... args) {
int qntNumerosInteressantes = 0;
for (int i = 0; i < 99999999; i++) {
if (julga(i, 10)) {
System.out.println(i + " é capicua não repetido na base " + 10);
qntNumerosInteressantes++;
}
}
System.out.println("quantidade de números capicua e não repetidos nas base 10: " + qntNumerosInteressantes);
qntNumerosInteressantes = 0;
for (int i = 0; i < 99999999; i++) {
if (julga(i, 16)) {
System.out.println(i + " é capicua não repetido na base " + 16);
qntNumerosInteressantes++;
}
}
System.out.println("quantidade de números capicua e não repetidos nas base 16: " + qntNumerosInteressantes);
meta_julga(0xffeff, 10); // 1048319
meta_julga(121, 10);
meta_julga(1221, 10);
meta_julga(12721, 10);
meta_julga(12721, 16); // 31b1
meta_julga(0xffeff, 16);
meta_julga(0xffdead, 16);
meta_julga(0101, 8);
meta_julga(0171, 8);
meta_julga(01267621, 8);
meta_julga(01267421, 8);
meta_julga(5, 2); // 101
meta_julga(6, 2); // 110
meta_julga(7, 2); // 111
meta_julga(4, 2); // 10
meta_julga(16, 3); // 121
meta_julga(10, 3); // 101
meta_julga(12, 3); // 110
}
private static void meta_julga(int n, int base) {
if (julga(n, base)) {
System.out.println(n + " é capicua não repetido na base " + base);
} else {
System.out.println(n + " não é capicua não repetido na base " + base);
}
}
// retorna verdade se todos os dígitos do número passado forem idênticos
//
// algoritmo de detecção: se, por acaso, existirem pelo menos dois dígitos com 1 ou mais posições, então é não repetido.
// caso seja tudo zero exceto por um único dígito, então é repetido
private static boolean ehNaoRepetido(Multimapa mm) {
int nDigitosDistintos = 0;
for (int i = 0; i < mm.base; i++) {
nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
}
return nDigitosDistintos > 1;
}
// retorna verdadeiro caso seja capicua
//
// algoritmo: verifica cada dígito; se for de tamanho `t` ímpar, então o dígito da posição `floor(t/2)` deve ser ignorado
// para um dígito `d` na posição `p` não ignorado, é necessário existir um outro dígito `d` na posição complementar `p'`, tal que `p + p' = t - 1`
private static boolean ehCapicua(Multimapa mm) {
int somaSimetrica = mm.size - 1;
int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;
for (int d = 0; d < mm.base; d++) {
for (Integer p: mm.pos[d]) {
// só tenta verificar se tem o complemento se e somente se não é ignorado
if (p != posIgnorada) {
int posComplemento = somaSimetrica - p;
// se não existe o dígito na posição complementar, então não é capicua
if (!mm.pos[d].contains(posComplemento)) {
return false;
}
}
}
}
return true;
}
private static boolean julga(int n, int base) {
Multimapa mm = new Multimapa(n, base);
if (ehNaoRepetido(mm)) {
if (ehCapicua(mm)) {
return true;
}
}
return false;
}
}
See working on ideone.
has to be by mathematical method?
– Guilherme Lautert
@Guilhermelautert yes, I believe that there are libs that do this, but I believe that then I would have no challenge :p
– user28595
I can point out unorthodox indirect methods that make unnecessary use of Features of a language?
– Jefferson Quesado
@Jeffersonquesado to get involved a little of the mathematics in logic, of course yes :)
– user28595
@Articuno I’m not sure I understand the question, do you want to find out if a given number is Capicua or generate all the numbers Capicua? Or something else?
– Piovezan
@Piovezan is to find out if a number that has 5 digits is Picua. This is the essence of the question, although many answers have not limited to only 5 (which has made them even more interesting).
– user28595