Dart

Part 1 was easy enough. For Part 2 I took a guess that the cycles were all well behaved and I could get away with just calculating the LCM, and it paid off.

(List, Map) parse(List lines) => (
      lines.first.split(''),
      {
        for (var l in lines.skip(2).map((e) => e.split(RegExp(r'[^A-Z0-9]'))))
          l[0]: [l[4], l[6]]
      }
    );
int movesTo(pos, steps, rules) {
  var stepNo = -1;
  while (!pos.endsWith('Z')) {
    pos = rules[pos]![steps[(stepNo += 1) % steps.length] == 'L' ? 0 : 1];
  }
  return stepNo + 1;
}

part1(List lines) {
  var (steps, rules) = parse(lines);
  return movesTo('AAA', steps, rules);
}

// All cycles are independent of state of `steps`, and have
// first instance == cycle length which makes this verrry simple.
part2(List lines) {
  var (steps, rules) = parse(lines);
  return [
    for (var start in rules.keys.where((e) => e.endsWith('A')))
      movesTo(start, steps, rules)
  ].reduce((s, t) => s.lcm(t));
}
}