First, a non-helpful thing I figured out:
If you find a way to get true answers you can solve the arf-vs-ruf dilemma with “is the pope catholic?” because whatever the answer to that is – arf or ruf – it means yes. But it turns out we can’t afford to waste a question for that. I believe it’s not even possible to learn the 3 identities and what arf and ruf mean with only 3 bits of information! So we have to somehow take these 3 arfs/rufs and infer the identities of the dogs without ever learning what arf and ruf actually mean!
And now a kind of hint, or, basically the solution to all such logic puzzles with truthers and liars or knights and knaves or whatever the puzzle calls them. Including a version so classic it’s in Dr Who. But not this one with the Random and arf-vs-ruf monkey wrenches.
I call this the Double Negative Indirection (DNI) trick. (It has a standard name in the literature which I won’t mention yet to keep all this as ungooglable as possible.) If you know that someone either always tells the truth or always lies you can ask them “what would you say if I asked you proposition P?” Truth-tellers obviously tell you whether P is true and liars lie to you about what they would say, which means they also tell you the truth. Cuz they lie about their lying! Pretty guileless for an inveterate liar but we’ll let that slide.)
But that doesn’t work with Random. If Random is truthful then it’ll peek into the random number generator of the hypothetical world where you ask it the embedded question and might truthfully tell you that it’ll lie in that case. Or vice versa. Point is, we lose the nice “either truthing about truthing or lying about lying, yielding the truth either way” property.
But we can fix that! Stay tuned…