Error trying to install dependencies for gnat
Solution 1:
I figured out the problem. It turns out the error message on apt-get was completely useless and misleading (and if someone can point me in the right direction I'm happy to submit a bug report). But by downloading the package and trying to install it with dpkg -i, I found that gnat required a version of gcc less than 7. So 'all' I had to do was get rid of gcc-7 and downgrade all its dependencies to versions that use gcc-5.