Jesus Christ that second stage was hard. For future players: it is beatable.
Yes, I was very surprised by how large the state space was. The first stage cleverly hiding this truth made it more amazing.