# [Community Puzzle] Running Up That Hill

Coding Games and Programming Challenges to Code Better

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.