ReasonML - Advent of Code - Day 2

Table Of Contents

• ReasonML lag features for today
• Setup
• First Problem
• Second Problem

Advent of Code - Day 2. If you are new here, I would recommend you to check the Day 1 solution where I cover more basics on ReasonML.

ReasonML Language Features for today

I am only going to introduce the language features we are going to use today. Some of them are List, Switch (Pattern Matching), Arrays, rec (Recursive functions).

• List is defined like so

let list_of_numbers = [0, 1, 2, 3, 4, 5];

• Lists are immutable, which means we cannot update their values if we need to do random updates we should use Arrays instead. List is great for prepending items and immutability.

• An array is defined like so
  

let inputArray = [|1, 2, 3, 4|];

• Unlike List, an Array can be mutated, which means we can update any arbitrary value like array[1] = 3. Mutability can be a problem at times, we will use List for those cases, we can convert a List to an array using Array.of_list(List).

• Pattern Matching is one of the most interesting features of Reasonml, it is a switch statement on steroids.
  

switch (data) {
| "hello" => "Hello world"
| "Bye" => "Bye world"
| _ => "Welcome"
};

• We have defined a very basic form of a switch statement, it will just check if data matches any of the cases like "hello" or "Bye" and take respective actions. The _ is our default case when nothing matches. We can do more interesting things with switch, but that's for some other time.

• As we have seen on Day 1, we have to use rec to mark a function as recursive. A recursive function is a function which calls itself.

Setup

Let us create a file Day2.re in our src folder and add the main function as we did on Day 1.

let main = () => {
  Js.log("Welcome to day 2");
};

Inside our index.re let's comment the Day1.main() and Day2.main().

// Day1.main();
Day2.main();

Now let's look at the first problem.

First Problem

Please check the problem statement at Advent of code Day 2 problem.

To brief, we are given a list of integers that acts like computer instructions. The pattern is fixed for it, the first number is operation/instruction type, the next two numbers are pointers to the values to use for the operation, and next to them is the pointer to where we should store the result of our operation. There are two operations, add 1 and multiply 2, and one terminal notation 99. For example [2,4,4,5,99,0], here the first character 2 states we should multiply the values pointed by the next two pointers, which is 99 for both (this is zero-indexed), and the third pointer 5 points to where we should store the result of multiplication. So 99 * 99 = 9801, the final solution would be [2,4,4,5,99, 9801]. The actual answer expected is the value at index 0.

So the plan is to go through each instruction one by one, solve it and proceed until we hit 99, where we stop and get the value at 0th index - our answer.

Let's define some test values in an array.

let test_values = [|2, 4, 4, 5, 99, 0|];

Now we define our compute function, which will take the int_code(The input) and instruction_pointer and recursively call itself until we hit 99.

let rec compute = (int_code, instruction_pointer) => {
  let op_code = int_code[instruction_pointer];
  if (op_code != 99) {
    compute(int_code, instruction_pointer + 1);
  } else {
    0;
  };
};

The above function does exactly what we want, though it is of no use till now. note that we have to write rec to say that this function is recursive. Let's call this from our main function with our test_values.

let main = () => {
  compute(test_values, 0) |> Js.log;
};

The console should log 0 at this point. Now that we know our recursion is working, lets us go through each instruction recursively and solve them.

let rec compute = (int_code, instruction_pointer) => {
  let op_code = int_code[instruction_pointer];
  if (op_code == 1) {
    let first_value_pointer = int_code[instruction_pointer + 1];
    let second_value_pointer = int_code[instruction_pointer + 2];
    let result_pointer = int_code[instruction_pointer + 3];
    int_code[result_pointer] =
      int_code[first_value_pointer] + int_code[second_value_pointer];
    compute(int_code, instruction_pointer + 4);
  } else if (op_code == 2) {
    let first_value_pointer = int_code[instruction_pointer + 1];
    let second_value_pointer = int_code[instruction_pointer + 2];
    let result_pointer = int_code[instruction_pointer + 3];
    int_code[result_pointer] =
      int_code[first_value_pointer] * int_code[second_value_pointer];
    compute(int_code, instruction_pointer + 4);
  } else {
    int_code[0];
  };
};

Here we check the op_code value and decide which operation to do add, multiply, or terminate. For both add and multiply we take the value pointers from the next 2 instructions and the result pointer from the third pointer, then we compute the value and store them at the said location. Finally, we call our compute function with instruction_pointer + 4 to move it after the current instruction set. For any case other than 1 and 2, we terminate our calls and return the result at the 0th index.

The console should log 2. You can test with other input values as well. It should just work fine.

Now let's refactor our solution a bit, using switch case.

let rec compute = (int_code, instruction_pointer) => {
  let op_code = int_code[instruction_pointer];
  switch (op_code) {
  | 1 =>
    int_code[int_code[instruction_pointer + 3]] =
      int_code[int_code[instruction_pointer + 2]]
      + int_code[int_code[instruction_pointer + 1]];
    compute(int_code, instruction_pointer + 4);
  | 2 =>
    int_code[int_code[instruction_pointer + 3]] =
      int_code[int_code[instruction_pointer + 2]]
      * int_code[int_code[instruction_pointer + 1]];
    compute(int_code, instruction_pointer + 4);
  | 99 => int_code[0]
  | _ => int_code[0]
  };
};

Here we check the op_code, and for each possible value which we want to handle we write a pattern 1 | 2 | 99 and _ is the default case.

You can pass the input you get from Advent Of code to get your solution.

Second Problem

The second problem is to find inputs required to get a specific output, the inputs are at index 1 and 2, called as noun and verb. The instruction set is the same as before, and the specific output is 19690720, for which we have to find values to pass at position 1 and 2. the values can be between 0 and 99 inclusive.

The plan here is to brute force (No elegant solution here, I might add a bonus post when I find one, or you can comment below). So we will loop through all the values of noun and verb between 0 and 99 until we get a solution.

For this let's create another recursive function that takes noun and verb as input.

let rec find_inputs = (noun, verb) =>
  if (verb >= 99 && noun < 99) {
    find_inputs(noun + 1, 0);
  } else if (verb < 99) {
    find_inputs(noun, verb + 1);
  } else {
    "End of the loop";
  };

The above function will loop through all the combinations of noun and verb from 0 till 99 and then output "End of the loop" in the console. Here we first check that have we gone from 0 till 99 for the verb, if yes then we increment the noun, else we keep on incrementing the verb until 99.

With the loop set up, we now just have to get the computed_value from our compute function, check if it is the value we want, then return noun * 100 + verb as required by the problem, else continue with the loop.

let rec find_inputs = (noun, verb) => {
  let int_code = test_values;
  int_code[1] = noun;
  int_code[2] = verb;
  let computed_value = compute(int_code, 0);
  if (computed_value == 19690720) {
    noun * 100 + verb;
  } else if (verb >= 99 && noun < 99) {
    find_inputs(noun + 1, 0);
  } else if (verb < 99) {
    find_inputs(noun, verb + 1);
  } else {
    0;
  };
};

We take the input and change the values at 1 and 2 with noun and verb respectively, then get the computed value to check if we get the correct value or not.

Let's call this from our main function.

let main = () => {
  find_inputs(0, 0) |> Js.log;
};

If you check your console, you would see 0 as the output. This is because we are using an array, which is mutable and hence it affects our solution (This was intentional). To fix this we need to use List, converting our array to list.

let test_values = [2, 4, 4, 5, 99, 0];

Notice we don't have any | here. List is immutable, which solves one of our problems of keeping the original input the same, but we cannot update its value, which is the need for the problem. So let's convert our input to Array just before using it.

let rec find_inputs = (noun, verb) => {
  let int_code = Array.of_list(test_values);
  int_code[1] = noun;
  int_code[2] = verb;
  let computed_value = compute(int_code, 0);
  if (computed_value == 19690720) {
    noun * 100 + verb;
  } else if (verb >= 99 && noun < 99) {
    find_inputs(noun + 1, 0);
  } else if (verb < 99) {
    find_inputs(noun, verb + 1);
  } else {
    0;
  };
};

Here Array.of_list converts our list into an Array, which we can mutate as we want, without affecting our original input List.

Tada, we have our solution.
We will explore more tomorrow. Message me or comment here if you have any questions or better solutions.