Longest sequence of two-digit sum replacements

Question

You are given a two-digit number. You can replace one of its digits with the sum of its digits modulo 10. For example, if the starting number is 58 then you can change it to 38 or 53. You can continue changing this number provided that you do not repeat a previously created number. This means if you went from 58 to 53 then you cannot go back to 58. Leading zeroes are not allowed.

What is the longest sequence of numbers you can create if you start with the number 10?

Hint:

Think about numbers that cannot be reached. Also think which numbers will get you stuck in a cycle quickly. These two things should give you a good upper bound on the maximum score.

Answer 1

Like Daniel in the comments, I also thought this would be easy to code. However, my brute force approach ran out of memory pretty quickly. I tried moving the history to a database, but that's very slow. Here's the best I've found so far:

67 moves [10, 11, 12, 13, 14, 15, 65, 61, 67, 63, 69, 59, 54, 94, 93, 23, 53, 58, 38, 18, 98, 97, 96, 95, 45, 49, 43, 47, 41, 51, 56, 16, 17, 87, 57, 52, 72, 92, 91, 90, 99, 89, 79, 76, 73, 70, 77, 74, 71, 78, 75, 25, 27, 29, 21, 31, 34, 37, 30, 33, 36, 39, 32, 35, 85, 83, 81]

A little more thought, and I realised that I could represent all the possible moves from one number to another as a directed graph. Then the problem becomes finding the longest path in the graph. Bad news: that problem is NP hard for a general graph. It's possible that there's some shortcut I could use for this graph, but I haven't found it yet.

Answer 2

First, a map: (very minor spoiler)

Second, notice that

replacing a digit with the sum of the two preserves divisibility by 2 and 5, so the reachable numbers are precisely the ones that don't share either factor. (Hence the spoiler)
By inclusion-exclusion, we can confirm that there should be 72 stations (allowing leading zeroes, except this actually doesn't matter as I'll explain below): 10^2 pairs sharing no factors - 5^2 pairs sharing 2 - 2^2 pairs sharing 5 + 1 pair (00) sharing both.
Now, notice that not all 72 stations are reachable - the eight purple stations only lead to the four white ones because their other paths [omitted] lead to themselves. Therefore, only five can be visited (and the fifth only as the last stop). If leading zeros are prohibited, then this is irrelevant - each white station has exactly one purple input and the length is capped at 68 instead of 69.
The last step for a proof of the optimality of @Don Kirkby's answer is to show that all four blue stations cannot be passed* in a single trip - unfortunately, I don't have a justification for that right now.
*Don's route misses 19 - the one leading back to the start.