We give efficient approximate counting and sampling algorithms for the large q random cluster and ferromagnetic Potts models on random regular graphs at all temperatures, including critical, showing that this type of phase transition is no barrier to efficient algorithms.  We also deduce probabilistic information such as the distribution of the log partition function and exponential decay of correlations conditioned on a phase.  Our techniques (using polymer models and the cluster expansion) are quite different but complementary to those based on the cavity method and the second moment method.  Joint work with Tyler Helmuth and Matthew Jenssen.