A code that is a word forwards & a different word backwards

Question

Hello!

For a present, I am trying to create a code that reads as a certain word forwards and a different word backwards. An example (0,1,2 are the available symbols):

D = 02, E = 01, H = 201, L = 1, O = 211, R = 10, W = 11

Then the pair "HELLO"/"WORLD" would be

2010111211 HELLO
1121110102 WORLD

I would like to generate a code that fits other word pairs. Obviously, I cannot brute force the solution (if one exists for that pair). All the optimization / search methods I know (simulated annealing, hill climbing, genetic algorithm) give me imperfect solutions only, if the word pairs are long.

The above example was found in a genetic algorithm I wrote to solve this, but after many generations with different parameters and word order, etc. it never quite reaches 100%.

How can I approach this differently? The length of each codeword is not very important should be less than 10 symbols per character, the number of different symbols used should stay under 5, and the code does not need to be prefix-free.

Edit: Following the comments, here is what I'm actually trying to do: Basically, I want to have a necklace with differently shaped beads (per symbol) that encode a word, and if you twist it then it encodes a different word. Therefore the codewords shouldn't be extremely long, and there cannot be too many different symbols.

Edit 2: Forwards, it should read FESTUNG DRESDEN (or FESTUNGDRESDEN), backwards some combination of generic "nice wishes", i.e. FRIENDS, FORTUNE, LUCK, HAPPINESS (or the German equivalent of these words) or just the name MARIA (yes, you've guessed right, it's for a girl...). It does not matter, if these words form pairs (i.e. FESTUNG reads backwards to FORTUNE, DRESDEN reads backwards to FRIENDS) or if it's the long version (i.e. FESTUNGDRESDEN reads backwards to FRIENDS&FORTUNE).

Thanks in advance!

Answer 1

If the code does not need to be prefix free and you don't care how long the codes are, then just one symbol is enough!

You encode each character by a different number of 1's, so that, in the end, the total number of 1s for one word is the same as the total number for the other.

To do this, remove the common characters.

In case of HELLO and WORLD, you are left with HEL and WRD.

Now you need six distinct integers which can be grouped into two groups of 3, such that sum of one group = sum of other.

One way to do this is to select odd numbers greater than 1 for one group and even numbers for the other (and possibly 1, depending on the number in each group).

For HEL and WRD you select

{3,5,7} and {1,6,8}.

For the common ones, now you can select numbers not in either group and you are done! (Although some care needs to be taken for words of very different length).

I have a feeling I have misunderstood something though.

Answer 2

I tried to transform FESTUNGDRESDEN into MARIA.

I found a possible encoding that does not satisfy all the specified conditions, since one of the letters needs more than 10 symbols.

A "manual" procedure: As both words share only one letter (the "R") I broke up both words as follows

  --------------->
  FESTUNGD R ESDEN
    A I    R  A M
   <--------------

so, keeping the code for R as a palindrome

   cod(FESTUNGD) = cod*(IA)
   and
   cod(ESDEN) = cod*(MA)

   where cod*() means "reading the code backwards"

Then I divided the problem one step further splitting the codes for the E and T

  ----------------------------------->
  FES(T2) (T1)UNGD R ESD(E3) (E2)(E1)N
    A        I     R      A      M
   <----------------------------------

I think this could be a starting point for developing a "real" algorithm in the future.

Anyway, by doing so I was able to write down the equations for each encoded char. The only difficult part is the "A", since it is repeated. This leads to the following equation

  cod("FES") & (T2) = cod("ESD") & (E3)

Proceeding in a similar way (further splitting the codes for letter X in X(1) X(2) X(3)), I rewrote the above equation into sub-parts and solved it. Not difficult, but tedious.

The result is:

F= 21243
E= 2124
S= 3212
T= 125
U= 1

N= 4

G= 3
D= 4321
R= 33
N= 2

M= 24
A= 212123421234212 --> Here is the looong one
I= 12343215

So, when you read

      f     e    s    t   u n g d    r  e    s    d    e    n
      21243 2124 3212 125 1 2 3 4321 33 2124 3212 4321 2124 2
   <--------------------------------------------------------
   v  backwards is:
   |
   |  M  A               R  I        A 
   |  24 212123421234212 33 12343215 212123421234212
   ------------------------------------------------->

I think this solution doesn't contribute in the field of algorithm development, but hopefully it does in the better cause of love :)

EDIT > FRIENDSHIP

Following the same procedure as above (and the suggestion made by Justin L.) , I tried with the word "Friendship", which seems aligned with the idea you want to communicate.

With the following table:

f 434
e 44
s 543
t 22
u 1
n 34
g 5
d 3
r 43

i 345
h 122
p 44434

The result is

       f   e  s   t  u  n   g  d  r  e   s    d   e   n
       434 44 543 22 1  34  5  3  43 44  543  3   44  34
   <-----------------------------------------------------
   v  and backwards is:
   |
   |   f   r   i   e   n   d  s   h   i   p
   |   434 43  345 44  34  3  543 122 345 44434
   ---------------------------------------------->

Please note that the equations for "t" "u" and "h" are independent from the rest of the system. So you can choose any unused combination of {3,4,5} (of any length) for them, possibly making the necklace with only 3 symbols. For doing this you could try

 t -> 4
 u -> 54

 which results in

 h -> 454

 all 3 are unused and available codes

Don't forget to upload a photo of the necklace!

Viel Glück!