I decided to stick to 16F15345 and see where I can reduce code.

I wanted to use the haversine formula to calculate distance between the current location and the secret location but did not have enough program memory to do floating point operations. So I started scaling things down, start using equarectangular approximation and then a cosine approximation.

To approximate cosine I used the CORDIC algorithm in fixed point.

After all that, I realized I don't need to any of that math and can just see if the difference between my two coordinates is small enough. It's not an exact distance but it's close enough.