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
Thanks for the puzzle i was very happy to brush up my 20 years old memories of linear algrebra⌠but you mention linalg cheater ⌠i still used linalg for determinant instead of recoding a gauss pivot ⌠It was still interesting , as indeed you canât naively use linalg inverse. For what its worth my python solution is 200 lines long
1 Like
Hello,
Can someone confirm that the numbers of the Hill matrix are integers only ?
Thanks
Yes, they are.
Thanks,
Unless I didnât understand something, each number is integer but not only between 0 and 9 . I wrongly assumed that .
They are between 0 and 44.