1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

//! # [Day 5: A Maze of Twisty Trampolines, All Alike](http://adventofcode.com/2017/day/5)
//!
//! An urgent <span title="Later, on its turn, it sends you a sorcery.">
//! interrupt</span> arrives from the CPU: it's trapped in a maze of jump
//! instructions, and it would like assistance from any programs with spare
//! cycles to help find the exit.
//!

/// The message includes a list of the offsets for each jump. Jumps are
/// relative: `-1` moves to the previous instruction, and `2` skips the next
/// one. Start at the first instruction in the list. The goal is to follow
/// the jumps until one leads *outside* the list.
pub fn parse_input(input: &str) -> Vec<isize> {
    input
        .split_terminator('\n')
        .map(|x| x.parse::<isize>().expect("Unexpected non-integer jump"))
        .collect::<Vec<_>>()
}

/// In addition, these instructions are a little strange; after each jump,
/// the offset of that instruction increases by `1`. So, if you come across
/// an offset of `3`, you would move three instructions forward, but change
/// it to a `4` for the next time it is encountered.
///
/// For example, consider the following list of jump offsets:
///
/// ```text
/// 0
/// 3
/// 0
/// 1
/// -3
/// ```
///
/// Positive jumps ("forward") move downward; negative jumps move upward.
/// For legibility in this example, these offset values will be written all
/// on one line, with the current instruction marked in parentheses. The
/// following steps would be taken before an exit is found:
///
/// -   `(0) 3  0  1  -3 ` - *before* we have taken any steps.
/// -   `(1) 3  0  1  -3 ` - jump with offset `0` (that is, don't jump at
///     all). Fortunately, the instruction is then incremented to `1`.
/// -   ` 2 (3) 0  1  -3 ` - step forward because of the instruction we just
///     modified. The first instruction is incremented again, now to `2`.
/// -   ` 2  4  0  1 (-3)` - jump all the way to the end; leave a `4`
///     behind.
/// -   ` 2 (4) 0  1  -2 ` - go back to where we just were; increment `-3`
///     to `-2`.
/// -   ` 2  5  0  1  -2 ` - jump `4` steps forward, escaping the maze.
///
/// In this example, the exit is reached in `5` steps.
///
/// ```
/// # use advent_solutions::advent2017::day05::{ parse_input, part1 };
/// # let input = parse_input("0
/// # 3
/// # 0
/// # 1
/// # -3
/// # ");
/// assert_eq!(part1(&input), 5);
/// ```
///
/// *How many steps* does it take to reach the exit?
pub fn part1(jumps: &Vec<isize>) -> usize {
    let jumps = jumps.clone();

    count_steps(jumps, |ip| ip + 1 )
}

/// Now, the jumps are even stranger: after each jump, if the offset was
/// *three or more*, instead *decrease* it by `1`. Otherwise, increase it by
/// `1` as before.
///
/// Using this rule with the above example, the process now takes `10`
/// steps, and the offset values after finding the exit are left as
/// `2 3 2 3 -1`.
///
/// ```
/// # use advent_solutions::advent2017::day05::{ parse_input, part2 };
/// # let input = parse_input("0
/// # 3
/// # 0
/// # 1
/// # -3
/// # ");
/// assert_eq!(part2(&input), 10);
/// ```
///
/// *How many steps* does it now take to reach the exit?
pub fn part2(jumps: &Vec<isize>) -> usize {
    let jumps = jumps.clone();

    count_steps(jumps, |ip| if ip >= 3 { ip - 1 } else { ip + 1 } )
}

/// Counts the steps required to exit the maze, given a instruction mutation
/// function `mut_fn`.
pub fn count_steps<F: Fn(isize) -> isize>(mut memory: Vec<isize>, mut_fn: F) -> usize {
    let mut ip = 0;

    let length = memory.len();

    ::itertools::repeat_call(|| {
        let old_ip = ip;
        ip = (ip as isize + memory[ip]) as usize;
        memory[old_ip] = mut_fn(memory[old_ip]);
        ip
    })
    .take_while(|&ip| ip < length)
    .count()
    + 1
}

test_day!("05", 360603, 25347697);