[Community Puzzle] Running Up That Hill

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?

1 Like

if there is a scipy.linalg.crack_hill() or something similar :slight_smile:

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. :frowning:
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… :slight_smile:

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 :slight_smile: (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 :slight_smile:

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.