Can you publish a paper Simply Implementing another Paper's Algorithm? There was a highly cited paper published earlier this year in my field which introduced a highly theoretical, non trivial, algorithm that relied on extremely heavy theory. The algorithm was exact (Gave the correct solution) but 3 papers were published later on criticizing that it was highly non practical (Its implementation was a nightmare) and proposed approximation algorithms that were simple to implement. 

So over the past year, me and 2 of my friends have been trying to implement the exact algorithm and finally we were able to implement it. The algorithm spans 14 files and is implemented in Python. The running time is acceptable for the input size in my field (takes 3-4 minutes on a modern computer to terminate). We also verified its correctness on a data set and it really did predict the exact solution. 

We would love to publish the code, but one of our advisors said that it is unlikely that Code only would be publishable in a reputable journal/conference. One option is that we can just put it on Github but that doesn't really count as a publication. Are there conferences/journals which would take a 1-2 page paper that just describes a hard implementation? The only novel thing we did was that we've had to make very minor changes to the algorithm to make it practical but proved that these minor changes don't change the correctness (just makes implementation a lot easier!).

Any ideas?
This is a judgement call and will be for editors and reviewers. But the main question they will want answered is what is new/novel in your paper? If you can give them that, then they will be more likely to accept it. 

The other question is, whether exactness is worth the effort. If the approximation methods give good enough answers then the expense of an exact solution may not be worth it in practice. Can you address that issue in your paper? 

You don't describe anything here about scaling if that is an issue with the algorithm. A few minutes on a modern system may be good or bad, depending. If the algorithm needs to be executed once for each Google query, then it is pretty bad. If it has to be executed once per "noticed supernova" then probably fine. 

There are a lot of questions your paper could address that might push the editor toward acceptance if you can handle them well.