Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @nicola,validated by @Tabaxi3K,@pluieciel and @DKurilo.

If you have any issues, feel free to ping them.

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @nicola,validated by @Tabaxi3K,@pluieciel and @DKurilo.

If you have any issues, feel free to ping them.

I like this puzzle, much kudos to the author!

However, I ran into a problem: As the modulus is not prime, many numbers have no modular inverse, so my modular division function cannot continue. I try to use LU decomposition adapted to modular arithmethics to solve the system of linear equations, and this algo uses division. I read in the Hill cipher wiki page that modulus is better to be a prime to avoid 0 determinant, but my algo fails at division even if the determinant would be nonzero. Any idea where do I go wrong?

Use GauĂâ way to trigonalize then diagonalize.

Donât hesitate to divide by the gcd of a line, because the Hill matrix determinant is alwaysâŚ

Am I going to make a giant c++ solution then find out it is 5 lines in python?

if there is a `scipy.linalg.crack_hill()`

or something similar

1 Like

I have the same problem when I try to multiply one row by modular inverse of pivot to reach 1 in pivot, since there is some (no modular inverse) numbers.

âaddition with lower rowsâ and then âmultiplyâ is good enough to solve that for me.

I didnât figure out how to use the libraries/packages when there is the modular thing.

I tried to use np.linalg.solve with (PP.t)A.t=(PC.t) to solve A.t, but dont know how to deal with the modularâŚ

The modular thingy was designed to prevent `linalg`

cheaters as much as possible.

I also played with the pivot selection to avoid a non-reversible pivot, but cannot succeed all the time. So currently stuck at 92%, with the test case âAnother 6x6â and its validator pair still failing.

It seems that LU decomposition is very fragile when the arithmethic is not over real numbers, or at least a finite fieldâŚ

You could probably solve for the matrix with a greedy algorithm, or annealing.

only âselectionâ is probably not enough. when current and lower rows all have non-reversible pivots (candidate), an addition could help escape the trap.

1 Like

Yes, that was what I was trying: adding another row from below (even tried multiplying by different scalars before adding)

It turned out that there was a bug in another part of my code, that ruined the already found solution in some edge cases.

Now I pass all tests at last. Oh my, solving this took much longer for me than it should have been! I will dream of matricesâŚ

2 Likes

aha! I have thwarted you! (I basically did what TBali was talking about where Iâd find two none-solved rows in the case the leading non-zero term was not coprime to 45 and look for one to only be a multiple of 3 and not 5 and another to be a multiple of 5 and not 3. Then Iâd add them and continue on my merry gauss-jordan way (Totally possible btw, I even brute forced inverses haha)

1 Like

You could also use the Chinese remainder theorem, that allows you to work in Z/9Z and Z/5Z instead of Z/45Z.

Yep and Z/9Z is not a field.

Thanks @nicola for this interesting puzzle ! I learned a lot about modular algebra, determinant, inverse, GaussâŚ things I learned 20 years ago but forgotten in the meanwhile

1 Like