Last year's Advent of Code had a task that was NP complete and lacked good well known approximation algorithms. I almost gave up on it when I realised as that feels impossible

In practice the data was well behaved enough and small enough that it was very doable.