Chapter 1

Chapter 2

This chapter is an introductory chapter used to justify the use of C as the languaged used in this book. Post that, it goes over a single example with the purpose of introducing the C programming language to the reader.

Example: Euclid's Algorithm

To begin, we'll consider a C program to solve a classic elementary problem: "Reduce a given fraction to its lowest to its lowest terms." We want to write 2/3, not 4/6, 200/300. or 178468/267702. Solving this problem is equivalent to finding the greatest common divisor (gcd) of the numerator and the denominator: the largest integer which divides them both. A fraction is reduced to lowest terms by dividing both numerator and denominator by their greatest common divisor. An effective method for finding the greatest common divisor was discovered by the ancient Greeks over two thousand years ago: it is called Euclid's algorithm because it is spelled out in Euclid's famous treatise Elements.

Euclid's method is based on the fact that if u is greater than v then the greatest common divisor of u and v is the same as the greatest common divisor of v and u - v. This observation leads to the following implementation in C:

#include <stdio.h>

int gcd(int u, int v)
{
  int t;
  while (u > 0)
    {
      if (u < v)
	{ t = u; u = v; v = t; }
      u = u -v;
    }
  return v;
}

main()
{
  int x, y;
  while (scanf("%d %d", &x, &y) != EOF)
    if (x>0 && y >0)
      printf("%d %d %d\n", x, y, gcd(x,y));
}

Here is the implementation written in Rust:

use std::io;

fn gcd(mut u: u32, mut v: u32) -> u32 {
    let mut t;
    while u > 0 {
        if u < v {
            t = u;
            u = v;
            v = t;
        }
        u = u - v;
    }
    v
}

fn main() {
    for line in io::stdin().lines() {
        let elements: Vec<u32> = line
            .unwrap()
            .split(" ")
            .map(|x| x.parse::<u32>().expect("unable to parse string into i32"))
            .collect();

        match elements.len() {
            2 => {
                if elements[0] > 0 && elements[1] > 0 {
                    println!(
                        "gcd({}, {}) => {}",
                        elements[0],
                        elements[1],
                        gcd(elements[0], elements[1])
                    );
                }
            }
            _ => println!("The string must be two integers separated by a space"),
        }
    }
}

Notes:

I am not the best with C syntax, but there are some things that we need to cover for both C and Rust before moving on:

Copying

In C, functions create local copies of their arguments, so even though x and y are passed into the gcd, their original values are not modified because u and v are not references to x and y.

This is why we can write printf("%d %d\n", x, y, gcd(x,y)). In theory, the gcd call gets evaluated before the printf call, so, if x and y were references and not copies, their updated values would have been printed in the printf call.

The Rust code is doing the exact same thing, but the mechanics of why it is happening are slightly different.

println!(
	"gcd({}, {}) => {}",
    elements[0],
    elements[1],
    gcd(elements[0], elements[1])
);

Rust has Ownership, which can be summed up as follows:

Each value in Rust has an owner.
There can only be one owner at a time.
When the owner goes out of scope, the value will be dropped.

In general, this means that variables passed to functions and methods or also passing ownership over those varables to functions and methods. I am not sure how things are handled with println! because that is a macro, but, the point remains that if element[0] and element[1] are passed to gcd and gcd gets evaluated first, then the println! macro should have printed the updated values for elements[0] and elements[1], right? Also, based off the rules of Ownership, it seems like we cannot have two versions of elements[0] and elements[1] around. So, what is going on?

The answer is the Copy Trait. The docs cover a lot, but the gist is that if a struct implements the Copy Trait, then instead of moving into the function (the transfer of ownership) it will implicitly create a copy of itself and pass that into the function. The data type u32 implements that Copy Trait, so ownership over elemtns[0] and elements[1] was never transfered because they were never moved.

scanf

We do not have scanf in Rust. As a result, I had to scan and parse the input myself, which led to a lot of extra code being added to the main function.

Thoughts

I really appreciated seeing gcd implemented using subtraction. Previously, I have only seen it implemented using remainder operators or mod operators, which have a direct relationship to subtraction, but I never think of them being on the same level. For example, I can understand someone not knowing modular arithmetic, but I would be completely surprised if they did not know how to subtract. So, for me, seeing this implemented using subtraction is a suble remnder that all this stuff can be written in such basic forms that it is hard to imagine anything of this stuff every being "difficult".

Chapter 3: Elementary Data Structures

Arrays

Perhaps the most fundamental data structure is the array, which is defined as a primitive in C and most other programming languages. An array is a fixed number of data items that are stored contiguously and that are accessed by an index. We refer to the ith element of the array a as a[i]. It is the responsibility of the programmer to store something meaningful in an array position a[i] before referring to it; neglecting this is on of the most common programming mistakes.

A simple example of the useof an array is given by the following program, which prints out all the prime numbers less than 1000. The method used, which dates back to the 3rd century B.C., is called the "sieve of Erathosthenes":

Sieve of Erathosthenes

The algorithm works by creating an array with indices 0 to 1000. The indice will represent the number and the value associated with the indice will be a boolean that denotes if the number is prime.

We start of by setting all of the values to the indices to True to represent them potentially being prime. Then we systematically use variables i and j to construct all the products (i*j) that are less then 1000 and set the values to those indices to False. At the end of this process, all the indices that are still set to True are prime.

C Implementation

#include <stdio.h>

#define N 1000
main()
{
  int i, j, a[N+1];
  for (a[1] = 0, i = 2; i <= N; i++) a[i] = 1;
  for (i = 2; i <= N/2; i++)
    for (j=2; j <= N/i; j++)
      a[i*j] = 0;
  for (i = 1; i <= N; i++)
    if (a[i]) printf("%4d", i);
  printf("\n");
}

Rust Implementation

const N: usize = 1000;

fn main() {
    let (mut i, mut j) = (2, 3);
    let mut a: [bool; N + 1] = [false; N + 1];

    // Setting up the initial array
    a[1] = false;
    for value in a.iter_mut() {
        *value = true
    }

    // We know that i*j is not prime,
    // So for each product we can create,
    // we set that index's value to false
    while i <= N / 2 {
        while j <= N / i {
            a[i * j] = false;
            j += 1;
        }
        j = 2;
        i += 1;
    }

    // Printing out all the primes
    for index in 2..N + 1 {
        if a[index] {
            print!("{:4}", index);
        }
    }
    print!("\n");
}

In the Rust implementation, I converted the for loops to while loops but, otherwise, I kept the code more or less the same.

Linked Lists

The second elementary data structure to consider is the linked list, which is defined as a primitive in some programming languages (notably in Lisp) but not in C. However, C does provide basic operations that make it easy to use linked lists.

The primary advantage of linked list over arrays is that linked lists can grow and shrink in size during their lifetime. In particular, their maximum size need not be known in advance. A second advantage of linked lists is that they provide flexibility in allowing the items to be rearranged efficiently. This flexibility is gained at the expense of quick access to any arbitrary item in the list.

A linked list is a set of items organized sequentially, just like an array. In an array, the sequential organization is provided implicitly (by the position in the array); in a linked list, we use an explicit arrangement in which each item is part of a "node" that also contains a "link" to the next node.

Note

The book has a lot of amazing diagrams illustrating examples of linked lists. I do not think I can recreate the diagrams well, but I will attempt to do them in mermaid.js.

Note

On another note, they way they discribe linked list makes me think that arrays that automatically increase in size as needed were not the norm them. That said, I do not think that our "automatically increasing in size" arrays every decrease their size when it is no longer needed. So, with respect to this book and to its focus on memory effeciency, it makes sense to use linked list over our automatically increasing in size arrays because it provides almost the same utility with the assurance that temporary increase in memory usage will be reclaimed, which will allow other parts of the program to use it later.

flowchart LR
    A((A)) --> L((L)) 
    L --> I((I))
    I --> S((S))
    S --> T((T))

Figure 3.1: A linked list

Figure 3.1 shows a linked list, with items represented by letters, nodes by circles and links by lines connecting the nodes. We look in detail below at how lists are represented within the computer; for now we'll talk simply in terms of nodes and links.

Even the simple representation of Figure 3.1 exposes two details we must consider. First, every node has a link, so the link in the last node of the list must specify some "next" node. Our convention will be to have a "dummy" node, which we'll call z, for this purpose: The last node of the list will point to z, and z will point to itself. In addition, we normally will have a dummy node at the other end of the list, again by convention. This node, which we'll call head, will pont to the first node in the list. The main purpose of the dummy nodes is to make cerain manipulations with the links, especially those involving the first and last nodes on the list, more convenient. Other conventions are discussed below. Figure 3.2 shows the list structure with these dummy nodes included.

flowchart LR
    head --> A((A))
    A --> L((L)) 
    L --> I((I))
    I --> S((S))
    S --> T((T))
    T --> z
    z --> z

Figure 3.2: A linked list with its dummy nodes

Now, this explicit representation of the ordering allows certain operations to be performed much more efficiently than would be possible for arrays. For example, suppose that we want to move the T from the end of the list ot the beginning. In an array, we would have to move every item to make room for the new item at the beginning; in a linked list, we just change three links, as shown in Figure 3.3.

flowchart LR
    head
    A((A))
    L((L))
    I((I))
    S((S))
    T((T))
    z

    head --> T
    A --> L 
    L --> I
    I --> S
    S --> z
    T --> A
    z --> z

Figure 3.3: Rearranging a linked list

Note

In Figure 3.3, I was unable to preserve the ordering while rearranging the links. As such, I can only produce the end result diagram and not the itermediate step.

We make the node containing T point to A, the node containing S point to z, and the head point to T. Even if the list was very long, we could make this structural cahnge by changing just three links.

More important, we can talk of "inserting" and item into a linked list (which makes it grow by one in length), an operation that is unnatural and inconvenient in an array. Figure 3.4 shows how to insert X into our example list by ptting X in a node that points to S, then making the node containing I point to the new node.

Similarly, we can speak of "deleting" an item from a linked list (which makes it shrink by one in length). For example, the second list in Figure 3.4 shows how to delete X from the second list simply by making the node containing I point to S, skipping X. Now, the node containing X still exists (in fact it still points to S), and perhaps should be disposed of in some way -- the point is that X is no longer part of the list, and cannot be accessed by following links from the head. We will return to this issue below.

flowchart LR
    head
    A((A))
    L((L))
    I((I))
    S((S))
    T((T))
    X((X))
    z

    head --> A
    A --> L 
    L --> I
    I --> X
    X --> S
    S --> T
    T --> z
    z --> z

flowchart LR
    head
    A((A))
    L((L))
    I((I))
    S((S))
    T((T))
    X((X))
    z

    head --> A
    A --> L 
    L --> I
    I --> S
	X --> S
    S --> T
    T --> z
    z --> z

Figure 3.4: Insertion into and deletion from a linked list

On the other hand, there are other operations for which a linked list are not well-suited. The most obvious of these is "find the _k_th item" (find an item given its index): in an array this is done simply by accessing a[k], but in a linked list we have to travel through k links.

Another operation that is unnatural on linked lists is "find the item before a given item." If all we have is the link to T in our sample list, then the only way we can find the link to S is to start as head and travel through the linked list to find the node that points to T. As a matter of fact, this operations is necessary if we want to be able to delete a given node froma linked list: how else do we find the node whose link much be changed? In many applications, we can get around this problem by redesigning the fundemental deletion operation to be "delete the next node." A similar problem can be avoided for insertion by making the fundemental insertion operation "insert a given item after a given node" in the list.

C Implementation

C provides primitives operations that allow linked lists to be implemented directly. The following code fragment is a sample implementation of the basic functions that we have discussed so far.

#include <stdlib.h>

struct node
{ int key; struct node *next;};

struct node *head, *z, *t;

listinitialize()
{
  head = (struct node *) malloc(sizeof *head);
  z = (struct node *) malloc(sizeof *z);
  head->next = z; z->next = z; 
}

deletenext(struct node *t)
{t->next = t->next->next;}

struct node *insertafter(int v, struct node *t)
{
  struct node *x;
  x = (struct node *) malloc(sizeof *x);
  x->key = v; x->next = t->next;
  t->next=x;
  return x;
}

main(){}

Note

The original code was a snippet that did not have the import line or a main function. I added those so that the code would compile.

Note

The use of the dummy node head and z do make the implementation easier. For example, the deletenext function never has to worry about t->next->next not existing, and the insertafter method never has to t->next because the first node will always be head and the head node will always have a next.

Rust Implementation

I was unable to write this in Rust. It is not possible with Safe Rust because all of these nodes are owned by the linked_list and the main function that is passing them into these methods. I believe this is possible with Unsafe Rust, but I do not know how to write Unsafe Rust and I cannot justify that rabbit hole for this book.

The compromise is that I wrote it in Python.

Python implementation

class Node:
    def __init__(self, key, node=None):
        self.key = key
        self.next = node

    def __repr__(self):
        return f"Node(key={self.key})"

class LinkedList:
    def __init__(self):
        self.head = Node(None)
        self.z = Node(None)
        self.head.next = self.z
        self.z.next = self.z

    def delete_next(self, node):
        node.next = node.next.next

    def insert_after(self, value, node):
        new_node = Node(value, node.next)
        node.next = new_node
        return new_node

    def __repr__(self):
        result = ""
        current_node = self.head.next
        index = 0
        while current_node != self.z:
            result += f"{index}: {current_node}\n"
            current_node = current_node.next
            index += 1
        return result
    
def main():
    linked_list = LinkedList()
    node_one = linked_list.insert_after(5, linked_list.head)
    node_two = linked_list.insert_after(10, node_one)
    node_three = linked_list.insert_after(15, node_two)

    print(f"{linked_list}")
    print(f"Delete {node_two}\n")

    linked_list.delete_next(node_one)
    print(f"{linked_list}")
    
if __name__ == "__main__":
    main()

Thoughts

I'm kind of angry with how easy it was to translate this into Python. I love Rust, but it always hurts when you try to do "simple" things in programming that are actually extremely difficult in Rust and you end up struggling for hours.

That aside, the Python translation was straightforward. I added __repr__ methods to both the Node and LinkedList so that I could see the output. The tricky part about that is that the Node method cannot print node.next because z points it itself, so it hits your recursive upper limit and crashes.

For the LinkedList, having the dummy head and z worked wonders in making the insert_after and the delete_next methods simple. It also does not limit the your options for new Nodes because the terminal node z is a pointer check to the class instance and not a equality check. So, in theory, I can add other nodes with the same properties of z to my linked_list and it should work fine.

I also liked how easy it was to skip the dummy nodes when iterating over the list. If you don't look at the implementation, (based off main and the output) you would never know that dummy nodes are being used.

JavaScript Implementation

class Node {
    constructor(key, node) {
        this.key = key;
        this.node = node;
    }
    print() {
        console.log(`Node(${this.key})`);
    }
}

class LinkedList {
    constructor() {
        this.head = new Node(null, null);
        this.z = new Node(null, null);
        this.head.next = this.z;
        this.z.next = this.z; // Sentinel node
    }

    delete_next(node) {
        node.next = node.next.next;
    }

    insert_after(value, node) {
        const newNode = new Node(value, node.next);
        node.next = newNode;
        return newNode;
    }
    print() {
        let current = this.head.next;
        while (current != null) {
            current.print();
            current = current.next;
        }
    }
}


function main() {
    const linkedList = new LinkedList();
    nodeOne = linkedList.insert_after(5, linkedList.head);
    nodeTwo = linkedList.insert_after(10, nodeOne);
    nodeThree = linkedList.insert_after(15, nodeTwo);

    console.log("Print linkedList")
    linkedList.print()

    console.log(`delete ${nodeTwo.key}`);
    linkedList.delete_next(nodeOne);
    console.log("\nPrint linkedList");
    linkedList.print();
}

main();

Thoughts:

JavaScript is strange, VS Code is strange and I'm so tired that I am surprised I was able to do anything.

Also, I hate the copilit suggestions. It interrupts my thoughts. No matter what I do, the suggestions are still there?!

I think the suggestions are gone... FINALLY!

Linked List -- Continued

The reader is encouraged to check these C implementations against the English language description given above. In particular, it is instructive at this stage to consider why the dummy nodes are useful. First, if the convention were to have head point to the beginning of the list rather than having a head node, then the insert procedure would need a special test for insertion at the beginning of the list. Second, the convention for z protects the delete procedure from (for exampe) a call to delete an item from an empty list.

Another common convention for terminating a list is to make the last node point to the first, rather than using either of the dummy odes head of z. This is called a circular list: it allows a program to go around and around the list. Using one dummy node to mark the beginning (and the end) of the list and to help handle the case of the empty list is sometimes convenient.

It is possible to support the operation "find the item before a given item" by using a doubly linked list in which we maintain two links for each node, one to the item before, one to the item after. The cost of providing this extra capability is doubling the number of link manipulations per basic operation, so it is not normally used unless specifically called for. As mentioned above, however, if a node is to be deleted and only a link to the node is available (perhaps it is also part of some other data structure), double linking may be called for.

Note

The "Josephus problem" describe in the next paragraph would never be written in a modern book, but I find it very interesting that something like this was every okay to mention in a tech book.

We'll see many examples of applications of these and other basic operations on linked lists in later chapters. Since the operations involve only a few statements, we noramlly manipulate the list directly rather than use the precise procedure above. As an example, we consider next a program for solving the so-called "Josephus problem" in the spirit of Eratosthenes. We imagine that N people have decided to commit mass suicide by arranging themselves in a circle and killing the Mth persion around the circle, closing ranks as each person drops out of the circle. The problem is to find out which person is the last to die (though perhaps that person would have a change of heart at the end!), or, more generally, to find the order in which the people are executed. For example, if N = 9 and M = 5, then people are killed in the order of 5, 1, 7, 4, 3, 6, 9, 2, 8. The following program reads in N and M and prints out this ordering:

C implementation

Note

The original code does not have comments. I added them for clarity.

#include <stdio.h>
#include <stdlib.h>

struct node {
  int key;
  struct node *next;
}

main() {
  int i, N, M;
  struct node *t, *x;

  // Capture user input
  scanf("%d %d", &N, &M);

  // Creating the linked list of number
  t = (struct node *)malloc(sizeof *t);
  t->key = 1;
  x = t;
  for (i = 2; i <= N; i++) {
    t->next = (struct node *)malloc(sizeof *t);
    t = t->next;
    t->key = i;
  }

  // Pointing the last node to the first node.
  // Makes the linked list circular
  t->next = x;

  // Josephus problem
  while (t != t->next) {
    for (i = 1; i < M; i++)
      t = t->next;
    printf("%d ", t->next->key);
    x = t->next;
    t->next = t->next->next;
    free(x);
  }
  printf("%d\n", t->key);
}

Python Implementation

The Python code stays pretty true to the C implementation.

class Node:
    def __init__(self, key, next=None):
        self.key = key
        self.next = next


def main():
    node = Node(1, None)

    # Capture user input
    N, M = input("Set N and M (example: '9 5': ").split()
    N = int(N)
    M = int(M)

    # Create linked list
    first_node = node
    for x in range(2, N + 1):
        node.next = Node(x)
        node = node.next

    # Make the linked list into a circular linked list
    node.next = first_node

    # Josephus problem
    while node != node.next:
        for _ in range(1, M):
            node = node.next
        print(f"{node.next.key}", end=" ")
        node.next = node.next.next

    print(f"{node.key}")


if __name__ == "__main__":
    main()

Rust Implementation

In Rust, I cannot use Linked List in they way Python and C do it, so I implemented a (bad) solution to the problem using a Vec.

use std::io;

fn main() {
    println!("Set N and M (example: '9 5'):");

    // Capture user input
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).unwrap();

    // Parse user input
    let data: Vec<usize> = buffer
        .split_whitespace()
        .collect::<Vec<_>>()
        .iter()
        .map(|x| x.parse().expect("Expect a digit"))
        .collect();

    #[allow(non_snake_case)]
    let N = data[0];
    #[allow(non_snake_case)]
    let M = data[1];

    // Create List
    let mut list: Vec<usize> = (1..=N).collect();

    // Josephus problem
    while list.len() > 1 {
        for _ in 1..M {
            // Rotate the items in the list to the left
            list.rotate_left(1);
        }
        let data = list.remove(0);
        print!("{data} ")
    }
    print!("{}", list[0]);
}

Back to the Book:

The program uses a circular linked list to simulate the sequence of executions directly. First, the list is built with keys from 1 to N: the variable x holds onto the beginning of the list as it is built, then the pointer in the last node in the list is set to x. Then, the program proceeds through the list, counting through M - 1 items and deleting the next, until only one is left (which then points to itself). Note the call to free for the delete, which corresponds to an execution: this is the opposite of malloc as mentioned before.

Storage Allocation

C's pointers provide a convenient way to implement lists, as shown above, but there aere alternatives. In this section we discuss how to use arrays to implement linked lists and how this is related to the actual representation of memory of a computer, so that analysis of how a data structure is implemented as an array will give you some insight into how it might be represented at a low level in the computer. In particular, we're interested in seeing how several lists might be represented simultaneously.

In a direct-array representation of linked lists, we use indices instead of links. One way to proceed would be to define an array of records like those above, but using integers (for array indices) rather than pointers for the next field. An alternative, which often turns out to be more convenient, is to use "parallel arrays": we keep the items in an array key and the links in an array next. Thus, key[next][head] refers ti the information associated with the first item on the list, key[next[next[head]]] to the second, etc. The advantage of using parallel arrays is that the structure can be built "on top of" the data: the array key contains data and only data -- all the structure is in the parallel array next. For example, another list can be built using the same data array and a different parallel "link" array, or more data can be added with more parallel arrays. The following code implements the basic list operations using parallel arrays:

C Implementation:

The errors you get when you try to compile code snippets from books can be rough, especially when you do not know the language well.

/*
  The original code used `max+2` and not 12.

  I changed it because it was giving me compile errors.
 */
int key[12], next[12];
int x, head, z;

int listinitialize()
{
  head = 0; z = 1; x = 2;
  next[head] = z; next[z] = z;
 };
int deletenext(int t)
  { next[t] = next[next[t]]; };
int insertafter(int v, int t)
{
  key[x] = v; next[x] = next[t];
  next[t] = x;
  return x++;
};

int main(){
}

Rust Implementation:

I wrote this about two weeks ago, so I am a bit fuzzy on how I felt at the time of writing it. All I know is that I spent hours trying to write a node based linked list and, after giving up, I came back, I think a day later, and struggled translating this to Rust. I believe the tricky part was getting the indices right. If insert_after does not return the correct value for the next index, everything becomes wonky.

const SIZE: usize = 10;

#[derive(Debug)]
struct List<T>
where
    T: Default + std::fmt::Debug + Copy,
{
    head: usize,
    z: usize,
    x: usize,

    key: [T; SIZE],
    next: [usize; SIZE],
}

impl<T: Default + std::fmt::Debug + Copy> List<T> {
    pub fn new() -> Self {
        let head = 0;
        let z = 1;
        let x = 2;
        // The Copy Trait is being used here because the default value is being
        // copied for each place holder
        let key = [T::default(); SIZE];
        let mut next = [0; SIZE];

        next[head] = z as usize;
        next[z] = z as usize;

        Self {
            head,
            z,
            x,
            key,
            next,
        }
    }

    pub fn delete_next(&mut self, t: usize) {
        self.next[t] = self.next[self.next[t]]
    }

    pub fn insert_after(&mut self, v: T, t: usize) -> usize {
        self.key[self.x] = v;
        self.next[self.x] = self.next[t];
        self.next[t] = self.x;
        self.x += 1;
        self.x - 1
    }

    pub fn print(&self) {
        let mut n = self.next[0];

        while n != self.z {
            println!("{:?}", self.key[n]);
            n = self.next[n];
        }
    }
}

fn main() {
    let mut list: List<i32> = List::new();
    let mut next = list.insert_after(5, 0);
    for x in [10, 15, 20] {
        next = list.insert_after(x, next);
        println!("{:?} -- next: {next}", list);
    }
    list.insert_after(100, next);
    println!("{:?}", list);

    list.print();

    list.delete_next(4);
    println!("{:?}", list);
    list.print();
}

Continue the Book

Each call on the storage allocation function malloc is replaced by simply incrementing the "pointer" x: it keeps track of the next unused position in the array.

Note

I'm skipping the Figure examples in this section because I cannot draw them.

The crux of the matter is to consider how the built-in procedures malloc and free might be implemented. We presume that the only space for nodes and links are the arrays we've been using; this presumption puts us in the situation the system is in when it has to provide the capability to grow and shrink a data structure wuth a fixed data structure (the memory itself). For example, suppose that the node containing A is to be deleted from the example in Figure 3.5 and then disposed of. It is one thing to rearrange the links so that node is no longer hooked into the list, but what do we do with the space occupied by that node? And how do we find space for a node when new is called and more space is needed?

On reflection, the reader will see that the solution is clear: a linked list should be used to keep track of the free space! We refer to this list as the "free list." Then, when we delete a node from our list we dispose of it by inserting it into the free list, and when we need a new node, we get it by deleting it from the free list. This mechanism allows several different lists to occupy the same array.

When storage management is provided by the system, as in C, there is no reason to override in this way. The description above is intented to indicate how the storage management is done by the system. The actual problem faced by the system is rather more complex, as not all nodes are necessarily of the same size. Also, some systems relieve the user of the need to explicitly free nodes by using garbage-collection algorithms to remove any nodes not referenced by any link. A number of rather clever storage management algorithms have been developed to handle these two situations.

Pushdown Stacks

We have been concentrating on structuring data in order to insert, delete, or access items arbitrarily. Actually, it turns out that for many applications, it suffices to consider various (rather stringent) restrictions on how the data structure is accessed. Such restrictions are beneficial in two ways: first, they can alleviate the need for the program using data structure to be concerned with its details (for example, keeping track of links to or indices of items); second, they allow simpler and more flexible implementations, since fewer operations need be supported.

The most important restricted-access data structure is the pushdown stack. Only two basic operations are involved: one can push an item into the stack (insert it at the beginning) and pop an item (remove it from the beginning). A stack operates somewhat like a busy executive's "in" box: work piles up in a stack, and whenever the executive is ready to do some work, he takes it off the top. This might mean that something get stuck in the bottom of the stack for some time, but a good executive would presumably manage to get the stack emptied periodically. It turns out that sometimes a computer program is naturally organized in this way, postponing some tasks while doing others, and thus pushdown stacks appear as the fundamental data structure for many algorithms.

We'll see a great many applications of stacks in the chapters that follow: for an introductory example, let's look at using stacks in evaluating arithmetic expressions. Suppose that one wants to find the value of a simple arithmetic expression involving multiplication and addition of integers, such as:

5 * (((9 + 8) * (4 * 6)) + 7

A stack is the ideal mechanism for saving intermediate results in such a calculation. The above example might be computed with the calls:

push(5);
push(9);
push(8);
push(pop() + pop());
push(4);
push(6);
push(pop()*pop());
push(pop()*pop());
push(7);
push(pop()+pop());
push(pop()*pop());
printf("%d\n", pop());

The order in which the operations are performed is dictated by the parentheses in the expression, and by the convention that we proceed from left to right. Other conventions are possible; for example 4*6 could be computed before 9+8 in the example above. And in C, the order in which the two pop() operations is performed is unspecified, so slightly more complicated code is needed for noncommutative operators such as subtract and divide.

Some calculators and some computing languages base their method of calculation on stack operations explicitly: every operations pops its argument from the stack and returns its results to the stack. As we'll see in Chapter 5, stacks often arise implicitly even when not used explicitly.

The basic stack operations are easy to implement using linked lists as in the following implementation:

C Implementation

Day 1: Not Quite Lisp

Link to problem

The Problem

Santa is trying to deliver presents in a large apartment building, but he can't find the right floor - the directions he got are a little confusing. He starts on the ground floor (floor 0) and then follows the instructions one character at a time.

An opening parenthesis, (, means he should go up one floor, and a closing parenthesis, ), means he should go down one floor.

The apartment building is very tall, and the basement is very deep; he will never find the top or bottom floors.

For example:

(()) and ()() both result in floor 0.
((( and (()(()( both result in floor 3.
))((((( also results in floor 3.
()) and ))( both result in floor -1 (the first basement level).
))) and )())()) both result in floor -3.

To what floor do the instructions take Santa?

Thoughts

This is a warm up problem, so there is not much to think about, but I did appreciate the opportunity to think about the process I want to use to solve these problems. I just finished reading The C Programming Language book and the small commandline programs they built throughout that book was eye opening. So, for my solutions, I will pass the input to my programs via stdin.

use std::io;

fn main() {
    let mut floor = 0;

    for line in io::stdin().lines() {
        for character in line.unwrap().chars() {
            if character.eq(&'(') {
                floor += 1;
            } else if character.eq(&')') {
                floor -= 1;
            }
        }
    }
    println!("Floor {}", floor);
}

The Problem Part 2

Now, given the same instructions, find the position of the first character that causes him to enter the basement (floor -1). The first character in the instructions has position 1, the second character has position 2, and so on.

For example:

) causes him to enter the basement at character position 1.
()()) causes him to enter the basement at character position 5.

What is the position of the character that causes Santa to first enter the basement?

Thoughts

This took me by surprise! I had already started working on day 2. I actually saw that day 2 has a part 2 before I realized that day one had a part 2.

At first glance, this problem looks like it is just about counting the characters I see and reporting when the floor hits -1. In the spirit of unix and in the aim of learning to let go of code, I will create a new project for this.

use std::io;

fn main() {
    let mut floor = 0;
    let mut position = 0;

    for line in io::stdin().lines() {
        for character in line.unwrap().chars() {
            position += 1;
            if character.eq(&'(') {
                floor += 1;
            } else if character.eq(&')') {
                floor -= 1;
            }

            if floor == -1 {
                break;
            }
        }
    }
    println!(
        "Santa has reached the basement floor at position {}",
        position
    );
}

Day 2: I Was Told There Would Be No Math

Link to problem

The Problem

The elves are running low on wrapping paper, and so they need to submit an order for more. They have a list of the dimensions (length l, width w, and height h) of each present, and only want to order exactly as much as they need.

Fortunately, every present is a box (a perfect right rectangular prism), which makes calculating the required wrapping paper for each gift a little easier: find the surface area of the box, which is 2*l*w + 2*w*h + 2*h*l. The elves also need a little extra paper for each present: the area of the smallest side.

For example:

A present with dimensions 2x3x4 requires 2*6 + 2*12 + 2*8 = 52 square feet of wrapping paper plus 6 square feet of slack, for a total of 58 square feet.

A present with dimensions 1x1x10 requires 2*1 + 2*10 + 2*10 = 42 square feet of wrapping paper plus 1 square foot of slack, for a total of 43 square feet.

All numbers in the elves' list are in feet. How many total square feet of wrapping paper should they order?

Thoughts

For this problem, I wanted to play around with variable initialization. I couldn't get the collect call to return the just the three values in like a tuple that I could distribute to individual variables, so I settled on putting it into a Vec and separating them later.

The side variables are meh. I could have done something more fancy with them, but I was tired and it didn't seem worth it. The extra variable initialization though! I like that one. I rarely use random code block at all in my code, but using it like this to initialize a semi complicated variable lets me see the power of these blocks!

use std::io;

fn main() {
    let mut wrapping_paper = 0;

    for line in io::stdin().lines() {
        let dimensions: Vec<isize> = line
            .unwrap()
            .split("x")
            .map(|x| x.parse::<isize>().unwrap())
            .collect();

        let (l, w, h) = (dimensions[0], dimensions[1], dimensions[2]);

        let side_1 = 2 * l * w;
        let side_2 = 2 * w * h;
        let side_3 = 2 * h * l;
        let extra = {
            let mut temp = vec![l * w, w * h, h * l];
            temp.sort();
            temp[0]
        };

        wrapping_paper += side_1 + side_2 + side_3 + extra;
    }
    println!(
        "The elves need {} square feet of wrapping paper",
        wrapping_paper
    );
}

The Problem Part 2

The elves are also running low on ribbon. Ribbon is all the same width, so they only have to worry about the length they need to order, which they would again like to be exact.

The ribbon required to wrap a present is the shortest distance around its sides, or the smallest perimeter of any one face. Each present also requires a bow made out of ribbon as well; the feet of ribbon required for the perfect bow is equal to the cubic feet of volume of the present. Don't ask how they tie the bow, though; they'll never tell.

For example:

A present with dimensions 2x3x4 requires 2+2+3+3 = 10 feet of ribbon to wrap the present plus 234 = 24 feet of ribbon for the bow, for a total of 34 feet.

A present with dimensions 1x1x10 requires 1+1+1+1 = 4 feet of ribbon to wrap the present plus 1110 = 10 feet of ribbon for the bow, for a total of 14 feet.

How many total feet of ribbon should they order?

Thoughts

I made this problem extremely annoying by trying to be fancy. If you put all the sides into an Vec and sort it, then the first two entries will be the smaller two sides. That is straight forward. Another thing that should have been straight forward is getting the cubed size. All you have to do is multiple dimension[0] * dimension[1] * dimension[2], but no. I wanted to be fancy and use reduce.

Fun fact. If you are iterating over a Vec, then you have access to references of the elements. If you call reduce on a Vec of references, then Rust expects you to deal with references in your reduce. I don't want to deal with references. As such, it took me 10 minutes to figure out that I had to use map to make non-reference copies of the elements of the Vec before calling reduce.

All in all, being fancy was stupid. Next time just mupltiple the items together...

use std::io;

fn main() {
    let mut ribbon = 0;

    for line in io::stdin().lines() {
        let mut dimensions: Vec<isize> = line
            .unwrap()
            .split("x")
            .map(|x| x.parse::<isize>().unwrap())
            .collect();

        dimensions.sort();

        ribbon += 2 * dimensions[0]
            + 2 * dimensions[1]
            + dimensions
                .iter()
                .map(|x| x.clone())
                .reduce(|acc, e| acc * e)
                .unwrap();
    }

    println!("The elves need {} total feet of ribbon", ribbon);
}

Day 3: Perfectly Spherical Houses in a Vacuum

link to problem

The Problem

Santa is delivering presents to an infinite two-dimensional grid of houses.

He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (^), south (v), east (>), or west (<). After each move, he delivers another present to the house at his new location.

However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. How many houses receive at least one present?

For example:

_> delivers presents to 2 houses: one at the starting location, and one to the east.

^>v< delivers presents to 4 houses in a square, including twice to the house at his starting/ending location.

^v^v^v^v^v delivers a bunch of presents to some very lucky children at only 2 houses.

Thoughts

If you treat the directions as 2d grid coordinates and then put the seen coordinates into a set, you are pretty much done. The only part I was confused about was whether or not I would make the borrow checker angry by passing my varaibles (that I still plan on using) to the HashSet. Upon reviewing the Rust Book, I performed a "Stack-Only Data Copy", which means that, for integers that exist entirely on the stack, a copy is made when you assign them to another variable leaving both variable valid.

use std::collections::HashSet;
use std::io;

fn main() {
    let mut up_down = 0;
    let mut left_right = 0;
    let mut set = HashSet::new();

    set.insert((0, 0));

    for line in io::stdin().lines() {
        for character in line.unwrap().chars() {
            if character.eq(&'^') {
                up_down += 1;
            } else if character.eq(&'v') {
                up_down -= 1;
            } else if character.eq(&'<') {
                left_right -= 1;
            } else if character.eq(&'>') {
                left_right += 1;
            }

            set.insert((up_down, left_right));
        }
    }

    println!("Santa delivered presents to {} homes", set.len());
}

Problem 2

The next year, to speed up the process, Santa creates a robot version of himself, Robo-Santa, to deliver presents with him.

Santa and Robo-Santa start at the same location (delivering two presents to the same starting house), then take turns moving based on instructions from the elf, who is eggnoggedly reading from the same script as the previous year.

This year, how many houses receive at least one present?

For example:

^v delivers presents to 3 houses, because Santa goes north, and then Robo-Santa goes south.

^>v< now delivers presents to 3 houses, and Santa and Robo-Santa end up back where they started.

^v^v^v^v^v now delivers presents to 11 houses, with Santa going one direction and Robo-Santa going the other.

Thoughts

The problem seems more or less the same, with the difference being that even instructions go to Santa and the odd instructions go to the Robot.

For a moment there, I was going to try to think of clever ways to split up the program, but the simple solution of maintaining two set of grid coordinates seems fine.

use std::collections::HashSet;
use std::io;

fn update_coordinates(
    direction: &char,
    x: &mut isize,
    y: &mut isize,
    set: &mut HashSet<(isize, isize)>,
) {
    if direction.eq(&'^') {
        *x += 1;
    } else if direction.eq(&'v') {
        *x -= 1;
    } else if direction.eq(&'<') {
        *y -= 1;
    } else if direction.eq(&'>') {
        *y += 1;
    }

    set.insert((*x, *y));
}

fn main() {
    let mut santa_up_down = 0;
    let mut santa_left_right = 0;
    let mut robot_up_down = 0;
    let mut robot_left_right = 0;

    let mut set = HashSet::new();

    set.insert((0, 0));

    for line in io::stdin().lines() {
        for (index, character) in line.unwrap().chars().enumerate() {
            if index % 2 == 0 {
                update_coordinates(
                    &character,
                    &mut santa_up_down,
                    &mut santa_left_right,
                    &mut set,
                );
            } else {
                update_coordinates(
                    &character,
                    &mut robot_up_down,
                    &mut robot_left_right,
                    &mut set,
                );
            }
        }
    }

    println!("Santa delivered presents to {} homes", set.len());
}

During my first pass at it, I put all the code in main. Though the answer was right, the repetition of code within the if blocks was hurting my eyes. So I pulled that code out into its own function. At the end of the day it is the same code, but the function of all reference does give the impression that I know what I am doing. hahaha

Day 4: The Ideal Stocking Stuffer

link to the problem

The Problem

Santa needs help mining some AdventCoins (very similar to bitcoins) to use as gifts for all the economically forward-thinking little girls and boys.

To do this, he needs to find MD5 hashes which, in hexadecimal, start with at least five zeroes. The input to the MD5 hash is some secret key (your puzzle input, given below) followed by a number in decimal. To mine AdventCoins, you must find Santa the lowest positive number (no leading zeroes: 1, 2, 3, ...) that produces such a hash.

For example:

If your secret key is abcdef, the answer is 609043, because the MD5 hash of abcdef609043 starts with five zeroes (000001dbbfa...), and it is the lowest such number to do so.

If your secret key is pqrstuv, the lowest number it combines with to make an MD5 hash starting with five zeroes is 1048970; that is, the MD5 hash of pqrstuv1048970 looks like 000006136ef....

Your puzzle input is iwrupvqb.

Thoughts

I took a brief look at the MD5 Wiki page and no obvious ways to force my wanted output jumped out at me, so I think I am going to go with the brute force approach. In the largest example, it looked like it was a little over a million MD5 computations (assuming that you start from 1).

use std::io;

use md5;

fn main() {
    for line in io::stdin().lines() {
        let mut found = None;

        let key = line.as_ref().unwrap();
        print!("{key}");

        for num in 0..=2000000 {
            let digest = md5::compute(format!("{}{}", line.as_ref().unwrap(), num));

            if format!("{:x}", digest).starts_with("00000") {
                println!(" -- {:?}", digest);
                found = Some(num);
                break;
            }
        }

        match found {
            None => {
                println!("\nDid not find a number to give me a MD5 value starting with '00000'\n")
            }
            Some(num) => println!("The magic number is {:?}\n", num),
        }
    }
}

I was right in that brute force was the way to go, but it was also wrong of me to do this problem while tired. I made so many little mistakes that it became frustrating. For example, I miss read the problem and thought that I had to submit the MD5 hash digest as the answer. One nice thing I can say is that even in my tired state, I had to good sense to take input from stdin. By putting the example keys and my key in a file I was able to solve all three problems at once, which allowed me to verify the examples while solving the problem for my input.

Anyway, md5::compute returns the digest, but it doesn't implement the Display Trait or have a single method to give me back the Hash in string form. I luckily noticed that it implemented the Debug Trait and that the debug string was the has I wanted. Though, I did look at their implementation for the Debug Trait and it look like it converted the digest to LowerHex before so that it could use the LowerHex fmt method to produce the string.... Wait... LowerHex is a standard library type... I was suppose to convert the digest to my wanted type and then do what I wanted to it.

I am going try doing that and see if it cleans up the code a bit.

Yeah, I was still wrong. LowerHex is a trait used for formatting strings. The full mapping of formatting trait shorcuts can be found here.

All in all, the change to the code was small. Now, I am using the LowerHex formatter instead of the Debug formatter. Though this makes my code a little cleaner, both traits were using the same fmt code under the hood, so its all kind of pointless...

The Problem Part 2

Now find one that starts with six zeroes.

Thoughts

I was going to go to bed, but I this seems like the exact same problem as the first. so I am going to take a crack at it.

...

They got me. The wording is different between part 1 and part 2. In part 1 it was "at least five zeros" and now it is "starts with six zeros", which means that if it starts with seven zeros, its is not correct! Given that I now have to care about the value that comes after the six zeros, I moved to using regex. The regex that I am currently using is ^0{6}[a-zA-Z1-9], but I am pretty sure this is overkill because hexidecimal is a-f and 0-9. Plus, I am explicitly setting it to LowerHex, which means that I do not have to care about the A-F.

use std::io;

use md5;
use regex::Regex;

fn main() {
    let re = Regex::new(r"^0{6}[a-f1-9]").unwrap();

    for line in io::stdin().lines() {
        let mut found = None;

        let key = line.as_ref().unwrap();
        print!("{key}");

        for num in 0..=2000000000 {
            let digest = md5::compute(format!("{}{}", line.as_ref().unwrap(), num));

            if re.is_match(format!("{:x}", digest).as_str()) {
                println!(" -- {:?}", digest);
                found = Some(num);
                break;
            }
        }

        match found {
            None => {
                println!("\nDid not find a number to give me a MD5 value starting with '00000'\n")
            }
            Some(num) => println!("The magic number is {:?}\n", num),
        }
    }
}

Hello 4 am and goodnight to the world.

Day 5: Doesn't He Have Intern-Elves For This?

link to the problem

The Problem

Santa needs help figuring out which strings in his text file are naughty or nice.

A nice string is one with all of the following properties:

It contains at least three vowels (aeiou only), like aei, xazegov, or aeiouaeiouaeiou.
It contains at least one letter that appears twice in a row, like xx, abcdde (dd), or aabbccdd (aa, bb, cc, or dd).
It does not contain the strings ab, cd, pq, or xy, even if they are part of one of the other requirements.

For example:

ugknbfddgicrmopn is nice because it has at least three vowels (u...i...o...), a double letter (...dd...), and none of the disallowed substrings.

aaa is nice because it has at least three vowels and a double letter, even though the letters used by different rules overlap.

jchzalrnumimnmhp is naughty because it has no double letter.

haegwjzuvuyypxyu is naughty because it contains the string xy.

dvszwmarrgswjxmb is naughty because it contains only one vowel.

How many strings are nice?

Thoughts

This sounds like a one pass scan of the word with various check. For example, the first check is the vowels, so you add a set of vowels and check the current character against it and count the positive hits.

The second condition is two character condition. If you are iterating over the input one character at a time, it makes sense to use index 0 to set the first prev_char and then use the pair of the previous character and the current character to check this condition (Must remember to update prev_char).

The third condition has a similar setup to the second condition, but it is a "not containt", which means means that we can use this for early termination (ie, continue to the next input, but we don't have to. This could just be a flag as well).

On the face of it, this seems pretty straight forward. Lets try to write it up.

use std::collections::HashSet;
use std::io;

fn main() {
    let mut nice_string = 0;

    let vowels = HashSet::from(['a', 'e', 'i', 'o', 'u']);
    let bad_pairs = HashSet::from(["ab", "cd", "pq", "xy"]);

    for line in io::stdin().lines() {
        let mut vowel_count = 0;
        let mut double_char_count = 0;
        let mut bad_pair_count = 0;
        let mut prev_char = None;

        for (index, character) in line.unwrap().chars().enumerate() {
            if vowels.contains(&character) {
                vowel_count += 1;
            }

            match prev_char {
                None => prev_char = Some(character),
                Some(prev) => {
                    if prev.eq(&character) {
                        double_char_count += 1;
                    }

                    if bad_pairs.contains(format!("{}{}", prev, character).as_str()) {
                        bad_pair_count += 1;
                    }

                    prev_char = Some(character)
                }
            }
        }

        if bad_pair_count == 0 && vowel_count >= 3 && double_char_count >= 1 {
            nice_string += 1;
        }

        println!(
            "nice string count: {} ---- vowels: {}, doubles: {}, bad pairs: {}",
            nice_string, vowel_count, double_char_count, bad_pair_count
        );
    }
}

It was actually that straight forward. The only new insight I had while writing it up is that the prev_char is easier to handle as a Option because I could then use a match statement to handle all of the stuff linked to prev_char in one place.

The Problem Part 2

Realizing the error of his ways, Santa has switched to a better model of determining whether a string is naughty or nice. None of the old rules apply, as they are all clearly ridiculous.

Now, a nice string is one with all of the following properties:

It contains a pair of any two letters that appears at least twice in the string without overlapping, like xyxy (xy) or aabcdefgaa (aa), but not like aaa (aa, but it overlaps).
It contains at least one letter which repeats with exactly one letter between them, like xyx, abcdefeghi (efe), or even aaa.

For example:

qjhvhtzxzqqjkmpb is nice because is has a pair that appears twice (qj) and a letter that repeats with exactly one letter between them (zxz).

xxyxx is nice because it has a pair that appears twice and a letter that repeats with one between, even though the letters used by each rule overlap.

uurcxstgmygtbstg is naughty because it has a pair (tg) but no repeat with a single letter between them.

ieodomkazucvgmuy is naughty because it has a repeating letter with one between (odo), but no pair that appears twice.

How many strings are nice under these new rules?

Thoughts

I agree that the first set of ruls was ridiculous, but I am not sure I am a fan of the new rules...

The first rules is tricky beause they cannot overlap. For example, if I kept a hashmap of each pair of a string, then aaa would count as 2 pairs. And aaaa should count as 2 pairs, but how do you know that they are not overlapping? You cannot split them by even and odd indices because the first pair may be one an even index while the second pair is on an odd index.

I am going to have to continue thinking about this.

The second condition is more straight forward. It is asking if the current character is equal to the character that appeared 2 indices ago. That is only slightly different than the prev_char in part 1. In thoery, you can use the prev_char result to setup a match for prev_prev_char and then do the check there (LOL). I'll probably write it up that way because thinking about it makes me giggle.

Alright, I need to figure out rule 1.

What do I know:

I know I can use a hashmap to do a seen check on the pairs.
I also know that the "no overlap" is currently an issue that I need to overcome.

How do I prevent overlap?

I could have a second hashmap to keep track of the indices? For example, take xyxy. When we see xy for the first time, one hashmap will keep a count seens, which will get set to one and the other will keep an array of indices where this has been seen (current entry being (0,1)). Then, when the second xy comes along, we can check the hashmap to array first and verify that the previous xy has different indices before sending it to the hashmap count to up the count. Though I think this will work, it sounds like too much work for this problem..
For an overlap to exist, the previous char must be equal to the current char, right? Maybe I can take advantage of that. I can keep track of the prev_char and the prev_prev_char. If prev_prev_char is None, and the prev_char is a... I might need a prev_prev_prev_char for this so that I have 4 chars that I can compare against because if all 4 are a, then we have aaa and that is fine. If we have None, aaa, then we know we have overlap.

The seconds approach sounds more straight forward, but only of you have the chars on an array where you can use the index to explicitly previous chars...

I guess that makes sense. I can convert the line to an Vec and then iterate over the Vec. I will have access to the index and for rule 2, I can check to if index i and index i-2 are the same char. For rule one, if the current char and the previous char are equal, then I can check the two character before that and if they are all eqal, it is not an overlap.

I think this will work. Let me try writing it up.

use std::collections::HashMap;
use std::io;

fn main() {
    let mut nice_words_count = 0;

    for line in io::stdin().lines() {
        let vec_chars: Vec<char> = line.unwrap().chars().collect();

        let mut index = 1;
        let mut doubles_count = HashMap::new();
        let mut char_repeat_count = 0;

        for character in vec_chars[1..].iter() {
            if index >= 2 {
                if vec_chars[index - 2].eq(character) {
                    char_repeat_count += 1;
                }
            }

            match index {
                1 => {
                    doubles_count
                        .entry(format!("{}{}", vec_chars[index - 1], vec_chars[index]))
                        .and_modify(|count| *count += 1)
                        .or_insert(1);
                }
                2 => {
                    if vec_chars[index - 1].eq(character) && vec_chars[index - 2].eq(character) {
                    } else {
                        doubles_count
                            .entry(format!("{}{}", vec_chars[index - 1], vec_chars[index]))
                            .and_modify(|count| *count += 1)
                            .or_insert(1);
                    }
                }
                x if x >= 3 => {
                    if vec_chars[index - 1].eq(character) && vec_chars[index - 2].eq(character) {
                        if vec_chars[index - 3].eq(character) {
                            doubles_count
                                .entry(format!("{}{}", vec_chars[index - 1], vec_chars[index]))
                                .and_modify(|count| *count += 1)
                                .or_insert(1);
                        }
                    } else {
                        doubles_count
                            .entry(format!("{}{}", vec_chars[index - 1], vec_chars[index]))
                            .and_modify(|count| *count += 1)
                            .or_insert(1);
                    }
                }
                _ => {}
            }

            index += 1;
        }

        if char_repeat_count >= 1 && doubles_count.values().any(|&x| x > 1) {
            nice_words_count += 1;
        }

        println!(
            "nice_words_count: {}, char repeat count: {}, doubles count: {:?}",
            nice_words_count, char_repeat_count, doubles_count
        );
    }
}

That actually went much smoother than I expected it to go! When writing it up, I realized that I did not need the first index of the vec_chars, so I created a slice of it that goes from index 1 to the end and iterated over that. This meant that I could note use enumerate to manage the index for me, which was fine.

I then used a match statement to manage the different cases that I was talking about before for rule 1. If the index is 1, then there are only 2 chars so overlap is not possible. If the index is 2, then there are 3 chars. Overlap is now possible, so you have to make sure that all three chars are not the same value (Note: I think I wrote the case compliment if statements because it is easier for me to think about when I want to act as appose to when I don't want to act, but I probably could have gotten away with a simpler conditional if I did it the other way... I may change it...). If the index is 3, then there are 4 chars which means that have to check the aaaa and baaa cases.

One thing that is cool about the HashMap is that we have the Entry API, which allows me to create an entry counter in one line via defining what I want to happen for new entry and what I want to happen for existing entries.

With regard to Rust, I can say that today was the first time I used the any method that is defined for iterators. It is pretty cool and useful that that HashMap values method returns a type (The the is Values) that implements and iterator.

Note: I updated the match index == 2 if check. It is much easier to read now.

Day 6: Probably a Fire Hazard

link to problem

The problem

Because your neighbors keep defeating you in the holiday house decorating contest year after year, you've decided to deploy one million lights in a 1000x1000 grid.

Furthermore, because you've been especially nice this year, Santa has mailed you instructions on how to display the ideal lighting configuration.

Lights in your grid are numbered from 0 to 999 in each direction; the lights at each corner are at 0,0, 0,999, 999,999, and 999,0. The instructions include whether to turn on, turn off, or toggle various inclusive ranges given as coordinate pairs. Each coordinate pair represents opposite corners of a rectangle, inclusive; a coordinate pair like 0,0 through 2,2 therefore refers to 9 lights in a 3x3 square. The lights all start turned off.

To defeat your neighbors this year, all you have to do is set up your lights by doing the instructions Santa sent you in order.

For example:

turn on 0,0 through 999,999 would turn on (or leave on) every light.

toggle 0,0 through 999,0 would toggle the first line of 1000 lights, turning off the ones that were on, and turning on the ones that were off.

turn off 499,499 through 500,500 would turn off (or leave off) the middle four lights.

After following the instructions, how many lights are lit?

Thoughts

This seems like a mini parser... We have strings like turn on 0,0 through 999,999, which are <command> <start_coordinates> through <end_coordinates>.

I don't think I want to write a parser though, so lets split the words up by white space.

Command:

turn on
turn off
toggle

The coordindates can be split by , to get the x and y.

I need to think about th lights situation. I am thinking about making them an enum.

Enum:

Enum Methods:

turn on
tun off
toggle

Then the grid will be a 2 dimensional Vec filled with my enums. I can iterate over it and call the appropriate method.

Speaking of iteration, I need to be able to figure out the start and stop of my iterations...

Lets say, they give me 2,4 through 5,6. This means that I from 2,4 to 2,999, the to 3,0 to 3,999, 4,0 to 4,999, then 5,0 to 5,6. Wait, I don't think I read that properly...

Each coordinate pair represents opposite corners of a rectangle, inclusive; a coordinate pair like 0,0 through 2,2 therefore refers to 9 lights in a 3x3 square. The lights all start turned off.

Opposite corners! So 0,0 through 2,2 is 0,0 | 0,1 | 1,2 | 1,0 | 1,1 | 1,2 | 2,0 | 2,1 | 2,2.

This means that 2,4 through 5,6 is 2,4 | 2,5 | 2,6 | 3,4 | 3,5 | 3,6 | 4,4 | 4,5 | 4,6 | 5,4 | 5,5 | 5,6.

In the above cases 2..=5, 4..=6.

Note: I thing the coordinates are (y, x) in the above case because Vec[y][x], but, since we only care about the number of lights on, I think I can get away with using Vec[x][y].

They are giving us opposite corners of the rectangle. All of the example are bottom left corner to top right corner, but I do not know if all the inputs are these corners in this order.

I took a quick glance at the inputs, and I think they are all bottom left to top right.

This means that I can for like:

for x in 2..=5:
  for y in 4..=6:
     vec[x][y] = vec[x][y].<command>

I will try to write it up, but it is getting late, so I do not know if I will finish it tonight.

use std::io;

enum Light {
    On,
    Off,
}

impl Light {
    fn new() -> Self {
        Light::Off
    }

    fn toggle(&self) -> Self {
        match self {
            Light::On => Light::Off,
            Light::Off => Light::On,
        }
    }

    fn turn_on(&self) -> Self {
        Light::On
    }

    fn turn_off(&self) -> Self {
        Light::Off
    }
}

fn parse(data: &Vec<&str>) -> (String, (usize, usize), (usize, usize)) {
    let len = data.len();

    let mut command = data[0].to_string();
    if len == 5 {
        command = format!("{} {}", data[0], data[1]);
    }

    let start: Vec<usize> = data[len - 3]
        .to_string()
        .as_str()
        .split(",")
        .map(|x| x.parse().unwrap())
        .collect();
    let end: Vec<usize> = data[len - 1]
        .to_string()
        .as_str()
        .split(",")
        .map(|x| x.parse().unwrap())
        .collect();

    return (command, (start[0], start[1]), (end[0], end[1]));
}

fn create_grid() -> Vec<Vec<Light>> {
    let mut vec_1 = Vec::with_capacity(999);
    for _ in 0..=999 {
        let mut vec_2 = Vec::with_capacity(999);

        for _ in 0..=999 {
            vec_2.push(Light::new());
        }
        vec_1.push(vec_2);
    }

    return vec_1;
}

fn change_lights(
    command: String,
    data: &mut Vec<Vec<Light>>,
    coord_1: (usize, usize),
    coord_2: (usize, usize),
) {
    for x in coord_1.0..=coord_2.0 {
        for y in coord_1.1..=coord_2.1 {
            if command.eq(&"turn on") {
                data[x][y] = data[x][y].turn_on();
            } else if command.eq(&"turn off") {
                data[x][y] = data[x][y].turn_off();
            } else if command.eq(&"toggle") {
                data[x][y] = data[x][y].toggle();
            }
        }
    }
}

fn main() {
    let mut grid = create_grid();
    for line in io::stdin().lines() {
        let data = line.unwrap();
        let data: Vec<&str> = data.split(" ").collect();

        println!("data: {:?} ", data);
        let (command, coord_1, coord_2) = parse(&data);
        println!("{} {:?} {:?}", command, coord_1, coord_2);

        change_lights(command, &mut grid, coord_1, coord_2);
    }

    // How many lights are on
    let mut count = 0;
    for row in grid.iter() {
        for light in row.iter() {
            match light {
                Light::On => count += 1,
                _ => {}
            }
        }
    }

    println!("{} lights are on", count);
}

It took longer than I thought to write, but it wasn't that bad. To make the program less confusing, I decided to keep the coordinates as (x1, y1), (x2, y2). Outside of that, some annoying things were:

Indecing on a Vec<&str>.
- In Rust, we cannot use negative indexes to get the items of that end of the Vec
Parsing the coordinates:
- I had to make sure their type was usize so that I can use them when indexing the grid.
- Also, the long string of methods I used to actually parse the &str to usize was annoying. Cloning &str clones the pointer and not the value, so I converted to a String, but Strings do not have a split method. So I converted the String to str and then did the split and parse.
The program is long! I did not like how long this is.

The Problem Part 2

You just finish implementing your winning light pattern when you realize you mistranslated Santa's message from Ancient Nordic Elvish.

The light grid you bought actually has individual brightness controls; each light can have a brightness of zero or more. The lights all start at zero.

The phrase turn on actually means that you should increase the brightness of those lights by 1.

The phrase turn off actually means that you should decrease the brightness of those lights by 1, to a minimum of zero.

The phrase toggle actually means that you should increase the brightness of those lights by 2.

What is the total brightness of all lights combined after following Santa's instructions?

For example:

turn on 0,0 through 0,0 would increase the total brightness by 1.

toggle 0,0 through 999,999 would increase the total brightness by 2000000.

Thoughts

I actually think this is easier than part one. I don't need an enum anymore. I can have a regular struct that has an internal counter that goes up and down with a min value of zero. And the structure of the program is identical to the first one.

I am going to try to write this up quickly and move on to my next task for the night.

use std::io;

struct Light {
    brightness: usize,
}

impl Light {
    fn new() -> Self {
        Self { brightness: 0 }
    }

    fn brightness(&self) -> usize {
        self.brightness
    }

    fn toggle(&mut self) {
        self.brightness += 2;
    }

    fn turn_on(&mut self) {
        self.brightness += 1;
    }

    fn turn_off(&mut self) {
        match self.brightness {
            0 => {}
            _ => self.brightness -= 1,
        };
    }
}

fn parse(data: &Vec<&str>) -> (String, (usize, usize), (usize, usize)) {
    let len = data.len();

    let mut command = data[0].to_string();
    if len == 5 {
        command = format!("{} {}", data[0], data[1]);
    }

    let start: Vec<usize> = data[len - 3]
        .to_string()
        .as_str()
        .split(",")
        .map(|x| x.parse().unwrap())
        .collect();
    let end: Vec<usize> = data[len - 1]
        .to_string()
        .as_str()
        .split(",")
        .map(|x| x.parse().unwrap())
        .collect();

    return (command, (start[0], start[1]), (end[0], end[1]));
}

fn create_grid() -> Vec<Vec<Light>> {
    let mut vec_1 = Vec::with_capacity(999);
    for _ in 0..=999 {
        let mut vec_2 = Vec::with_capacity(999);

        for _ in 0..=999 {
            vec_2.push(Light::new());
        }
        vec_1.push(vec_2);
    }

    return vec_1;
}

fn change_lights(
    command: String,
    data: &mut Vec<Vec<Light>>,
    coord_1: (usize, usize),
    coord_2: (usize, usize),
) {
    for x in coord_1.0..=coord_2.0 {
        for y in coord_1.1..=coord_2.1 {
            if command.eq(&"turn on") {
                data[x][y].turn_on();
            } else if command.eq(&"turn off") {
                data[x][y].turn_off();
            } else if command.eq(&"toggle") {
                data[x][y].toggle();
            }
        }
    }
}

fn main() {
    let mut grid = create_grid();
    for line in io::stdin().lines() {
        let data = line.unwrap();
        let data: Vec<&str> = data.split(" ").collect();

        println!("data: {:?} ", data);
        let (command, coord_1, coord_2) = parse(&data);
        println!("{} {:?} {:?}", command, coord_1, coord_2);

        change_lights(command, &mut grid, coord_1, coord_2);
    }

    // How many lights are on
    let mut count = 0;
    for row in grid.iter() {
        for light in row.iter() {
            count += light.brightness;
        }
    }

    println!("The total brightness of the lights is {}", count);
}

The changes were so minor that this win doesn't feel like it counts. I changed the enum to a struct and updated the methods to do the brightness thing. I also added a new method get the current brightness level, but my counter is of type usize, so I don't have to worry about the borrow checker. Anyway, since I kept the name Light when I made the change from enum to struct, all the type checking and setup remained valid. The next thing I changes was in the change_lights function, and all I had to do was call the turn_on, turn_off, and toggle method on the Lights.

Lastly, I changed how I do the counting at the end of the program. Then I updated the last print statement for kicks.

This feels like the part 2 was way too easy when compared to the part 1, but its probably the case that I made part 1 more complicated than it needed to be. I used an enum when 0, 1 and a few if statements would have worked. If that was my starting point, then part 2 would have been a lot more difficult than part 2.

Day 7: Some Assembly Required

link to problem

The Problem

This year, Santa brought little Bobby Tables a set of wires and bitwise logic gates! Unfortunately, little Bobby is a little under the recommended age range, and he needs help assembling the circuit.

Each wire has an identifier (some lowercase letters) and can carry a 16-bit signal (a number from 0 to 65535). A signal is provided to each wire by a gate, another wire, or some specific value. Each wire can only get a signal from one source, but can provide its signal to multiple destinations. A gate provides no signal until all of its inputs have a signal.

The included instructions booklet describes how to connect the parts together: x AND y -> z means to connect wires x and y to an AND gate, and then connect its output to wire z.

For example:

123 -> x means that the signal 123 is provided to wire x.

x AND y -> z means that the bitwise AND of wire x and wire y is provided to wire z.

p LSHIFT 2 -> q means that the value from wire p is left-shifted by 2 and then provided to wire q.

NOT e -> f means that the bitwise complement of the value from wire e is provided to wire f.

Other possible gates include OR (bitwise OR) and RSHIFT (right-shift). If, for some reason, you'd like to emulate the circuit instead, almost all programming languages (for example, C, JavaScript, or Python) provide operators for these gates.

For example, here is a simple circuit:

123 -> x
456 -> y
x AND y -> d
x OR y -> e
x LSHIFT 2 -> f
y RSHIFT 2 -> g
NOT x -> h
NOT y -> i

After it is run, these are the signals on the wires:

d: 72
e: 507
f: 492
g: 114
h: 65412
i: 65079
x: 123
y: 456

In little Bobby's kit's instructions booklet (provided as your puzzle input), what signal is ultimately provided to wire a?

Thoughts

Though I have a general idea of what all of this means, it is best to refresh myself on the terms and operations before breaking down the problem.

So bitwise operations happen on a bit array, which you can think of as your binary representation of a number using 1's and 0's. We were told that our wire can carry up to a 16 bit signal. A bit is single place holder for a 0 or a 1. A 16 bit signal is 16 bits, which implies that we have 16 place holders for a 0 or 1.

For example:

0000000000000000 and 1111111111111111 are both 16 bits

Remember that we are using a binary representation of a number, which is really your number (which is typically in base 10) converted to base 2. Given that there are 16 place holders and there are 2 options for each place (the options being 1 or 2), the largest number we can represent is (2^16 -1) == 65536 -1 == 65535 (I think the minus 1 is becauase we start our count at zero, but I am not sure). Anyway, I mention that because they mention that a number can be from 0 to 65535.

It should be noted that all the numbers in this range is positive. This is because we ran out of bits. If we wanted to represent a negative number, we would have to use a bit to represent whether or not the number was positive or negative. In doing so, we would lose a factor of 2 because one bit would be dedicated to the sign (positive or negative) of the number.

Moving on to the bitwise operators, the list we are given is:

AND
OR
LSHIFT
RSHIFT
NOT (complement)

The Wiki page gives examples of these operations using 4 bits (a nibble or half a byte):

    0101 (decimal 5)
AND 0011 (decimal 3)
  = 0001 (decimal 1)

   0101 (decimal 5)
OR 0011 (decimal 3)
 = 0111 (decimal 7)

NOT 0111  (decimal 7)
  = 1000  (decimal 8)

Shifts involve shifting all bits over to the left or right X number times. It should be noted that there is a different between Arithmetic shifts and Logical shift, and our link was to Logical shifts.

For logical shifts, all bits move a placeholder to the left and the least significat bit (LSB -- placeholder 0) gets replaced with a 0. The same process happens for right shift just in the opposite direction. So the most significant bit is replaced with 0. You may be curious about the bits that get pushed off the end. They are gone forever.

For example:

0011 (3) + LSHIFT 1 => 0110 (6)
0011 (3) + LSHIFT 2 => 1100 (12)

0011 (3) + RSHIFT 1 => 0001 (1)
0011 (3) + RSHIFT 2 => 0000 (0)

Thoughts on the actual problem

This is like a mini compiler. I say that because we are given a string to parse to set variables. We are then given other strings that use our stored variables in operations, which then set other variables. Then, at the end of the program, we need to be able to state the current value of one of our variables.

There example was:

123 -> x            x = 123 == 0000000001111011
456 -> y            y = 456 == 0000000111001000
x AND y -> d        
                    0000000001111011
               AND  0000000111001000
				--------------------
				    0000000001001000

                    d = 72 == 0000000001001000

x OR y -> e
                    0000000001111011
	            OR  0000000111001000
				--------------------
				    0000000111111011

                    e = 507 == 0000000111111011

x LSHIFT 2 -> f
                    f = 492 == 0000000111101100

y RSHIFT 2 -> g
                    g = 114 == 0000000001110010 

NOT x -> h
                    h = 65412 == 1111111110000100
NOT y -> i
                    i = 65079 == 1111111000110111

The Parsing:

Spliting by whitespace, we have:

[123, ->, x]           | len 3
[456, ->, y]           | len 3
[x, AND, y, ->, d]     | len 5
[x, OR, y, ->, d]      | len 5
[x, LSHIFT, 2, ->, f]  | len 5
[y, RSHIFT, 2, ->, g]  | len 5
[NOT, x, ->, h]        | len 4
[NOT, y, ->, i]        | len 4

If the len is 3, we can directly set a variable.

If the len is 4, we take the complement of one variable to set another.

if the lent is 5, we check the item at index 1 to figure out which operation we are doing.

The Operations

The Rust Book as a page of all the operators.

AND
&	expr & expr	Bitwise AND	BitAnd
&=	var &= expr	Bitwise AND and assignment	BitAndAssign


OR
|	expr | expr	Bitwise OR	BitOr
|=	var |= expr	Bitwise OR and assignment	BitOrAssign

RSHIFT
>>	expr >> expr	Right-shift	Shr
>>=	var >>= expr	Right-shift and assignment	ShrAssign

LSHIFT
<<	expr << expr	Left-shift	Shl
<<=	var <<= expr	Left-shift and assignment	ShlAssign

Note: The NOT (!) operator was not listed on that page, but !x works on u16.

Storing values

Is value is a u16 and I think I can store them in a HashMap<(String, u16)>

It took so long to write all of this out, that I do not feel like writing it up anymore...

Mistakes...

I did not pay enough attention to this one line...

A gate provides no signal until all of its inputs have a signal.

This means that the data will come out of order.

Off the top of my head, I am thinking about maintaining a list with the data that cannot be process yet and continuously iterating over it until it all gets processed, but I am not sure if I can do that easily though.

Regardless, I need to be able to reject data that connot be processed yet and dave it for later.

Note: Though the command are out of order, the order of which they are seen might actually matter because a series of commands can produce different outputs based on the order (Consider the case where a varaible x was set twice. Any commands using x should have two differnt results depending on which version of x they see. -- debunked! I took a quick glance at our data and nothing is being set twice).

Alright, I guess I can keep a left of "still need to process" items. At the start of each input iteration, I can try to process the items in that list. If nothing gets processed, I move onto the streamed input.

At the end of the program. I try to process the "still need to process" items over and over again until the entire list is done?

Solution

use std::collections::{HashMap, HashSet};
use std::io;

fn is_digit(data: &str) -> bool {
    let mut result = true;
    for character in data.chars() {
        if !character.is_digit(10) {
            result = false;
            break;
        }
    }
    result
}

fn compliment(data: Vec<&str>, map: &mut HashMap<String, u16>) {
    let a = data[1];

    let digit = match is_digit(a) {
        true => a.parse::<u16>().unwrap(),
        false => map.get(a).unwrap().clone(),
    };

    map.insert(data[3].to_string(), !digit);
}

fn assign_variable(data: Vec<&str>, map: &mut HashMap<String, u16>) {
    let a = data[0];
    let b = data[2];

    match is_digit(a) {
        true => {
            let digit = a.parse::<u16>().unwrap();
            map.insert(b.to_string(), digit);
        }
        false => {
            let digit = map.get(a).unwrap().clone();
            map.insert(b.to_string(), digit);
        }
    }
}

fn and(data: Vec<&str>, map: &mut HashMap<String, u16>) {
    let a = data[0];
    let b = data[2];

    let digit_1 = match is_digit(a) {
        true => a.parse::<u16>().unwrap(),
        false => map.get(a).unwrap().clone(),
    };
    let digit_2 = match is_digit(b) {
        true => b.parse::<u16>().unwrap(),
        false => map.get(b).unwrap().clone(),
    };

    map.insert(data[4].to_string(), digit_1 & digit_2);
}

fn or(data: Vec<&str>, map: &mut HashMap<String, u16>) {
    let a = data[0];
    let b = data[2];

    let digit_1 = match is_digit(a) {
        true => a.parse::<u16>().unwrap(),
        false => map.get(a).unwrap().clone(),
    };
    let digit_2 = match is_digit(b) {
        true => b.parse::<u16>().unwrap(),
        false => map.get(b).unwrap().clone(),
    };

    map.insert(data[4].to_string(), digit_1 | digit_2);
}

fn left_shift(data: Vec<&str>, map: &mut HashMap<String, u16>) {
    let a = data[0];
    let b = data[2].parse::<u16>().unwrap();

    let digit_1 = match is_digit(a) {
        true => a.parse::<u16>().unwrap(),
        false => map.get(a).unwrap().clone(),
    };

    map.insert(data[4].to_string(), digit_1 << b);
}

fn right_shift(data: Vec<&str>, map: &mut HashMap<String, u16>) {
    let a = data[0];
    let b = data[2].parse::<u16>().unwrap();

    let digit_1 = match is_digit(a) {
        true => a.parse::<u16>().unwrap(),
        false => map.get(a).unwrap().clone(),
    };

    map.insert(data[4].to_string(), digit_1 >> b);
}

fn process_line(command: &str, map: &mut HashMap<String, u16>) {
    let data: Vec<&str> = command.split(" ").collect();

    println!("data: {:?} ", data);

    if data.len() == 3 {
        assign_variable(data, map);
    } else if data.len() == 4 {
        compliment(data, map);
    } else if data.len() == 5 {
        match data[1] {
            "AND" => and(data, map),
            "OR" => or(data, map),
            "LSHIFT" => left_shift(data, map),
            "RSHIFT" => right_shift(data, map),
            _ => {}
        }
    }
}

fn needed_vars_set(command: &str, map: &HashMap<String, u16>) -> bool {
    let mut result = true;

    let ignore_list = HashSet::from(["AND", "OR", "LSHIFT", "RSHIFT", "NOT"]);

    for part in command.split(" ") {
        if part.eq("->") {
            break;
        }
        if is_digit(part) {
            continue;
        }

        if ignore_list.contains(part) {
            continue;
        }

        if map.get(part).is_none() {
            result = false;
            break;
        }
    }
    result
}

fn main() {
    let mut old_commands = Vec::new();
    let mut variables: HashMap<String, u16> = HashMap::new();

    for line in io::stdin().lines() {
        let command = line.unwrap();

        if needed_vars_set(&command, &variables) {
            process_line(&command, &mut variables);
        } else {
            old_commands.push(command);
        }
    }

    while old_commands.len() > 0 {
        let mut other_commands = Vec::new();
        for command in old_commands.iter() {
            //println!("{command}, {:#?}", variables);

            if needed_vars_set(command, &variables) {
                process_line(command, &mut variables);
            } else {
                other_commands.push(command.clone());
            }
        }
        old_commands = other_commands;
    }

    println!("{:?}", variables.get("a"));
}

This was pretty painful. I made silly mistakes, like not understand that the commands are coming out of order. Post that, I made a bunch of small programming errors in the needed_vars_set function that led to infinite loops.

Also, I changed the "process old commands" approach. I decided that it would be easier to parse the command and find all the variables list in in, then check to see of those variables are set. If they are set, then I process the command. If they are not set, I store that command in a list and try processing it again later.

Once I got to the part where I am only processing old commands, I used the same exact approach again to re-process everything. The main difference is that this time i put it into a while loop and kept repeating the process until all the commands were processed.

All in all, I am really glad that I took time to think through the parts of the problem I did understand correctly. I think that if I were confused by any of the bitwise operations or the initial line parsing, I would have made so many mistakes that I would have given up out of frustration.

The Problem Part 2

Now, take the signal you got on wire a, override wire b to that signal, and reset the other wires (including wire a). What new signal is ultimately provided to wire a?

Thoughts

ITS THE SAME PROBLEM WITH ONE VARIABLE CHANGED!!!

I updated the value for b in the input and ran the code again to get the answer. Off the top of my head, I am not exactly sure how this problem is any different from part 1.

Meh. At least I solved it.

Day 8: Matchsticks

link to problem

The Problem

Space on the sleigh is limited this year, and so Santa will be bringing his list as a digital copy. He needs to know how much space it will take up when stored.

It is common in many programming languages to provide a way to escape special characters in strings. For example, C, JavaScript, Perl, Python, and even PHP handle special characters in very similar ways.

However, it is important to realize the difference between the number of characters in the code representation of the string literal and the number of characters in the in-memory string itself.

For example:

"" is 2 characters of code (the two double quotes), but the string contains zero characters.

"abc" is 5 characters of code, but 3 characters in the string data.

"aaa"aaa" is 10 characters of code, but the string itself contains six "a" characters and a single, escaped quote character, for a total of 7 characters in the string data.

"\x27" is 6 characters of code, but the string itself contains just one - an apostrophe ('), escaped using hexadecimal notation.

Santa's list is a file that contains many double-quoted string literals, one on each line. The only escape sequences used are \ (which represents a single backslash), " (which represents a lone double-quote character), and \x plus two hexadecimal characters (which represents a single character with that ASCII code).

Disregarding the whitespace in the file, what is the number of characters of code for string literals minus the number of characters in memory for the values of the strings in total for the entire file?

For example, given the four strings above, the total number of characters of string code (2 + 5 + 10 + 6 = 23) minus the total number of characters in memory for string values (0 + 3 + 7 + 1 = 11) is 23 - 11 = 12.

Thoughts

I am not sure of quick way of solving this that is not brute force pattern matching.

The cases seem to be:

String with characters
- Char count + 2
String with characters and esc
- Char count + 2 + 1 for each escaped character
Hex String
- ???
- I am not sure if each Hex is 6 characters and I am not sure if chars will the Hex in pieces or the string presentations...
Come to think about it, the escape char list may pose a problem. "" is fine, but \\ in a string could prove troublesome because it overlaps with Hex. So, for "\x27", is the string 2 chars (\') or 7/8 chars?

Meh. I guess I will find out.

Thoughts post some investigation

I think I was wrong about this problem. All the input will come in as strings and I need to deduce which parts of it count as part of the string.

For example, if "/x27" comes in, I need to be able to identify that is ti a hex value. Hex values are seemingly single chars, so should have a string count of 1 and a character count of 6.

For the escape characters, I need to figure out what counts as a escaped character. So, "/'", "/"" and "//" all count.

So, if the string is not a Hex, then I can do a 2 character check to see if the string has escaped characters.

Also, all of the inputs are in quotes, so calling "data.len()" when data is "" will give me 2. This means that I am litary scanning the string trying to decide what the string number should be for all of these. lol

Notes:
- all strings should be of length 2 or greater.
- If hex, then the string count is 1
- If not hex, minus 1 for every / in string?
I don't know if this is right, but I can write it up and test it against the test case.

Mistakes
1. I miss interpreted the problem. The hex code can be found within the string at any point in time. For example, "\x5em\"squulpy" starts with a hex and then there is the rest of the string. So (I think) \x5e should count as 1 string char, but this could have been "y\x5em\"squulp".
2. Over counting. In my first implementation, I did not consider the case \\\x5e, which is \\ + \x5e. So the mistake I made was iterating over the it character by character, when really I needed to skip ahead to account for escaped characters that I have already counted.

Solution

use std::io;

fn main() {
  let mut total_chars = 0;
  let mut total_strings = 0;

  for line in io::stdin().lines() {
      let data = line.unwrap();
      let char_count = data.len();
      let mut escaped_count = 0;

      let characters: Vec<char> = data.chars().collect();

      let mut index = 2;
      while index < characters.len() - 1 {
          let prev = index - 1;

          let pair = format!("{}{}", characters[prev], characters[index]);
          if pair.eq("\\\"") || pair.eq("\\\\") {
              escaped_count += 1;
              index += 1 // skip over 1 to prevent double counting
          } else if pair.eq("\\x") {
              escaped_count += 3; // for hex
              index += 3 // skip over 3 to prevent double counting
          }

          index += 1
      }
      let string_count = char_count - escaped_count - 2;
      println!("{data} - Char count: {char_count} - Escaped count: {escaped_count} - Diff (char - eascped - 2 = string count) {string_count}");
      total_chars += char_count;
      total_strings += string_count;
  }
  println!(
      "Chars: {total_chars}, Strings: {total_strings}, Diff: {}",
      total_chars - total_strings
  );
}

The code it pretty ugly. That aside, the print statements gave me a ton of audit information. Without that, I definitely would not have solve this one tonight.

Anyway, the trick to solving this problem is understanding the window you are looking at. I choose the window of two characters, the current one and the previous one. I took the approach of counting the escaped characters and adding 2 to the for the quotes (Note: When I iterate over the Vec, i shrunk the bounds to leave out the start and end quotes).

For the while loop, lets examine aa\\\x5em:

My first pair is aa. Nothing happens here, so we increment the index by one.

Next is a\. Nothing again. Increment by 1.

Next is \\. We have an escaped backslash. Increment by two to prevent double counting.

Next is \x. We have the start of a hex code. These are exactly 4 characters, so we increment by 4.

The index is not out of bound, so we stop the count. It should be noted that the m was never looked at, but you need at least 2 characters for an escape, so not looking at it is fine.

Here is example output that shows why I found the print statements so helpful (It was kind of hard to read it as a code block, so I quoted each line of the output).

"" - Char count: 2 - Escaped count: 0 - Diff (char - eascped - 2 = string count) 0

"abc" - Char count: 5 - Escaped count: 0 - Diff (char - eascped - 2 = string count) 3

"aaa"aaa" - Char count: 10 - Escaped count: 1 - Diff (char - eascped - 2 = string count) 7

"\x27" - Char count: 6 - Escaped count: 3 - Diff (char - eascped - 2 = string count) 1

"\\x5em"squulpy" - Char count: 18 - Escaped count: 5 - Diff (char - eascped - 2 = string count) 11

Chars: 41, Strings: 22, Diff: 19

The Problem Part 2

Now, let's go the other way. In addition to finding the number of characters of code, you should now encode each code representation as a new string and find the number of characters of the new encoded representation, including the surrounding double quotes.

For example:

"" encodes to """", an increase from 2 characters to 6.

"abc" encodes to ""abc"", an increase from 5 characters to 9.

"aaa"aaa" encodes to ""aaa\"aaa"", an increase from 10 characters to 16.

"\x27" encodes to ""\x27"", an increase from 6 characters to 11.

Your task is to find the total number of characters to represent the newly encoded strings minus the number of characters of code in each original string literal. For example, for the strings above, the total encoded length (6 + 9 + 16 + 11 = 42) minus the characters in the original code representation (23, just like in the first part of this puzzle) is 42 - 23 = 19.

Thoughts

It is 2 am, I'm tired, and I should go to bed, but this looks a lot simplier than part 1.

Each line gets a plus 2 because we have new quotes.

I iterate over each char and add 1 everytime I see a " of a \. This accounts for the new escapes. To get the new size, we characters.len() + new_escapes + 2 (for the new quotes).

"" => characters.len() + new_escapes + new_qoutes = 2 + 2 + 2 = 6

"abc" => 5 + 2 + 2 = 9

"aaa"aaa" => 10 + 4 + 2 = 16

"\x27" => 6 + 3 + 2 = 11

Solution Part 2

use std::io;

fn main() {
  let mut total_chars = 0;
  let mut total_expanded = 0;

  for line in io::stdin().lines() {
      let data = line.unwrap();

      let mut expanded_count = 0;
      for character in data.chars() {
          match character {
              '\\' => expanded_count += 1,
              '"' => expanded_count += 1,
              _ => {}
          }
      }

      let expanded_count = data.len() + expanded_count + 2;
      println!(
          "line: {data} -- chars: {} -- expanded: {expanded_count}",
          data.len()
      );
      total_expanded += expanded_count;
      total_chars += data.len();
  }

  println!(
      "{total_expanded} - {total_chars} = {}",
      total_expanded - total_chars
  );
}

This was definitely much easier than part 1.

Day 9: All in a Single Night

link to problem

The Problem

Every year, Santa manages to deliver all of his presents in a single night.

This year, however, he has some new locations to visit; his elves have provided him the distances between every pair of locations. He can start and end at any two (different) locations he wants, but he must visit each location exactly once. What is the shortest distance he can travel to achieve this?

For example, given the following distances:

London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141

The possible routes are therefore:

Dublin -> London -> Belfast = 982
London -> Dublin -> Belfast = 605
London -> Belfast -> Dublin = 659
Dublin -> Belfast -> London = 659
Belfast -> Dublin -> London = 605
Belfast -> London -> Dublin = 982

The shortest of these is London -> Dublin -> Belfast = 605, and so the answer is 605 in this example.

What is the distance of the shortest route?

Thoughts

These problems always scare me because I suck at them. In Python, I would use itertools.permutations to get the list of distinct possible routes, sum them up and keep the lowest value, but I don't have that function in Rust. The Python docs have and example of how to write the algorthim and I am hesitant to transcribe it to Rust because I do not fully understand (and will most likely make a mistake...).

I know that this is a simple problem. I know that combinatorially their are n!/2 options. n! because you have n options for the first place and n-1 options for the next, and so on. You divide by 2 because, with reference to this problem, going forward and going backwards gives you the same value. So in there example, we had 3 options, which leads to 3! (6) total permutations, but half of these permuations give identical results.

The input file only has 7 options. 7!. I was going to say that 7!/2 was small enough to do by hand, but then I opened up a calculator and discovered thats 2,520 options...

Okay, maybe my anxiety was justified.

Anyway, I have thought about cheap ways of solving the problem. I could use a random number generator randomize the travel list and then compute the sums. If I did this enough times, say 10,000 time, I would definitely get the correct answer.

To me, casually throwing my vague understanding of dynamic programming at this problem seems like it would undermine my goals here, which are to learn.

Breath in, breath out and lets think about this.

Thoughts after calming down

Let's answer some basic stuff first.

How do I want to represent the data?

These seems like dictionaries. My London dictionary will have keys for Dublin and Beldfast.

 london = {"dublin": 464, "belfast": 518}
 dublin = {"london": 464, "belfast": 141}
 belfast = {"london": 518, "dublin": 141}

The above should probably be in a dictionary too so that it can be easily referenced.

 distances = {
   "london": {"dublin": 464, "belfast": 518},
   "dublin": {"london": 464, "belfast": 141},
   "belfast": {"london": 518, "dublin": 141},
 }

Now, if I was iterating over a list like ["dublin", "london", "belfast"], I would start at index 0 and 1 like distances[index_0][index_1], which is distances['dubline']['london'] = 464.

This representation makes sense to me bacause it makes the distance reference easy.

Generating the permutations

The first question I should ask is, do I have to do this? I believe the answer is yes, but I want to take a few minutes and brainstorm if there are other ways to approach this problem.

There is the min distance subset approach where I pick a location and then find the shortest distance to the another location and then pick that location. This process repeats till you get to the end location. Then, you change your start location and try again.

Given that forward a backwards are the same, the swapping of starting locations should help with the pigeon hole issue of placing a extremely far distance at the end of the list because there are no other options left. The reason this will help is because when one of those two locations with that extremely far distance is the starting point, it will never pair with that far away place.

The more I think about it, the more this "min max solution" sounds promising.

I do not have time to write this up now, but I think these are the steps.

Steps:

Parse file to create my Dict[str: Dict[str: int]]
Iterate over the keys of the top level dict to get my starting points.
Then I have my min max loop process.
- Find the shortest distance to the next place.
- Put that location in the seen set. (Note: the starting location should be in this set already)
- Start from that next place and find the closest place that is not in the seen set
- Repeat till size of seen set is equal to the number of locations.
- Save that value (and the path for audit purposes) and move on to the next start point.
Take the samest distanced travelled and hope that is the solution.

I will be really happy if this works, but I will not be able to find that out today.

Solution

use std::collections::{HashMap, HashSet};
use std::io;

fn update_distances(
    mut distances: HashMap<String, HashMap<String, usize>>,
    start: String,
    end: String,
    distance: usize,
) -> HashMap<String, HashMap<String, usize>> {
    match distances.contains_key(&start) {
        false => {
            let mut temp = HashMap::new();
            temp.insert(end.clone(), distance.clone());
            distances.insert(start.clone(), temp);
        }
        true => {
            if let Some(data) = distances.get_mut(&start) {
                data.insert(end.clone(), distance.clone());
            }
        }
    }

    distances
}

fn create_data_structure(
    mut distances: HashMap<String, HashMap<String, usize>>,
) -> HashMap<String, HashMap<String, usize>> {
    for line in io::stdin().lines() {
        let data = line.unwrap();
        let data: Vec<String> = data.split(" ").map(|x| x.to_string()).collect();

        let (start, end, distance) = (data[0].clone(), data[2].clone(), data[4].clone());
        let distance: usize = distance.parse().unwrap();

        // updating the map
        distances = update_distances(distances, start.clone(), end.clone(), distance.clone());
        distances = update_distances(distances, end.clone(), start.clone(), distance.clone());
        println!("{start} {end} {distance}");
    }

    distances
}

fn closest_distance(
    map: &HashMap<String, usize>,
    seen: &HashSet<String>,
) -> Option<(String, usize)> {
    let mut result = None;
    let mut min = 1000;
    for (loc, dis) in map.iter() {
        if !seen.contains(loc) {
            if dis < &min {
                min = dis.clone();
                result = Some((loc.to_string(), dis.clone()));
            }
        }
    }
    result
}

fn main() {
    let mut distances: HashMap<String, HashMap<String, usize>> = HashMap::new();
    distances = create_data_structure(distances);

    let mut shortest_distance = 10000;
    for (start, map) in distances.iter() {
        print!("Start {start} -> ");

        let mut current_loc = start.clone();
        let mut current_map = map;
        let mut total = 0;
        let mut seen = HashSet::new();
        while seen.len() < map.len() {
            seen.insert(current_loc.clone());
            match closest_distance(current_map, &seen) {
                None => {}
                Some((loc, dis)) => {
                    total += dis;
                    print!("{loc} ({total}) -> ");

                    current_loc = loc;
                    current_map = distances.get(&current_loc).unwrap()
                }
            }
        }
        if total < shortest_distance {
            shortest_distance = total;
        }
        println!("\n");
    }

    println!("{}", shortest_distance);
}

I fumbled through this, but I kept the outline steps I wrote in my heads and used it as a guiding star until I completed the implementation.

If you look at fn main, I start off creating the data structure I want, which is the nested HashMap that we talked about. I then have a function called create_data_structure, which fills in the data for the nested map (just like we talked about).

Everything after this point is related to the min-max loop that we are going to use to find the closest distance.

I create a variable called shortest_distance that will hold the the final answer. I initialize it to a way too big number so that it will replaced by the first total distances we get.

For the loop, I iterate of the outer HashMap. This will give use our starting location and the map all the other locations with their distances from the starting location.

We copy these items to variables called current_loc and current_map. These values will get updated as we travel. For example, if was start at London and then travel to Belfast, our new current location is Belfast, which means that our new current map should be the Belfast map that have all of the locations and distances relative to Belfast.

In order to make sure we do not travel to the same location twice, we create a seen HashSet use to track the locations that we have been to.

So the process is:

We start at a location (set this to current location)
- We add our current location the seen
- We find the closest location to our current location
- We set current location to the closet location (ie we traveled to the next location)
- Repeat until we have traveled to all the locations (ie seen.len() == HashMap.len())

Of course, we did some math to track the total distances traveled, and, when needed, we updated our shortest_distance variable.

Thoughts on Solution

I find it visually ugly, but I think that is because I muddled through. All the steps I wanted are here, but I did not know how to write the steps. So I would writes things in main to test out ideas and once I got something working, I would copy it into a function and delete it from main. This style of programming works, but I care so much about "trying out an idea" that I spent little time on my variable names and code structure and quality.

I think this is my first time using a nested HashMap in Rust, so navigating that was kind of awkward. It was a lot to type and I sometimes got lost in the get a reference or get a mutable reference of the inner HashMap. At one point, I even got tired of typing, so I copied and pasted the signature whenever I needed it. I guess I could have declared the signature as a new type and that would have saved me tome typing.

The CLONING!!! I kept throwing that method at the wall everytime I ran into an issue instead of taking the time to think about my data and if the clone makes sense.

Though I had a clear outline of how I wanted to solve the clostest distance part, I couldn't translate it into code at first. I made a number of mistakes before I got it right.

The Problem Part 2

The next year, just to show off, Santa decides to take the route with the longest distance instead.

He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once.

For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast.

What is the distance of the longest route?

Thoughts:

I should be able to copy and paste the solution from part 1 and change the operators from less than to greater than and get the answer... I hope that's it because I really do not want to spend too much more time on this problem.

Solution Part 2

Change operators and some variable names from like min to max and shortest to longest, but that was all.

use std::collections::{HashMap, HashSet};
use std::io;

fn update_distances(
    mut distances: HashMap<String, HashMap<String, usize>>,
    start: String,
    end: String,
    distance: usize,
) -> HashMap<String, HashMap<String, usize>> {
    match distances.contains_key(&start) {
        false => {
            let mut temp = HashMap::new();
            temp.insert(end.clone(), distance.clone());
            distances.insert(start.clone(), temp);
        }
        true => {
            if let Some(data) = distances.get_mut(&start) {
                data.insert(end.clone(), distance.clone());
            }
        }
    }

    distances
}

fn create_data_structure(
    mut distances: HashMap<String, HashMap<String, usize>>,
) -> HashMap<String, HashMap<String, usize>> {
    for line in io::stdin().lines() {
        let data = line.unwrap();
        let data: Vec<String> = data.split(" ").map(|x| x.to_string()).collect();

        let (start, end, distance) = (data[0].clone(), data[2].clone(), data[4].clone());
        let distance: usize = distance.parse().unwrap();

        // updating the map
        distances = update_distances(distances, start.clone(), end.clone(), distance.clone());
        distances = update_distances(distances, end.clone(), start.clone(), distance.clone());
        println!("{start} {end} {distance}");
    }

    distances
}

fn farthest_distance(
    map: &HashMap<String, usize>,
    seen: &HashSet<String>,
) -> Option<(String, usize)> {
    let mut result = None;
    let mut max = 0;
    for (loc, dis) in map.iter() {
        if !seen.contains(loc) {
            if dis > &max {
                max = dis.clone();
                result = Some((loc.to_string(), dis.clone()));
            }
        }
    }
    result
}

fn main() {
    let mut distances: HashMap<String, HashMap<String, usize>> = HashMap::new();
    distances = create_data_structure(distances);

    let mut longest_distance = 0;
    for (start, map) in distances.iter() {
        print!("Start {start} -> ");

        let mut current_loc = start.clone();
        let mut current_map = map;
        let mut total = 0;
        let mut seen = HashSet::new();
        while seen.len() < map.len() {
            seen.insert(current_loc.clone());
            match farthest_distance(current_map, &seen) {
                None => {}
                Some((loc, dis)) => {
                    total += dis;
                    print!("{loc} ({total}) -> ");

                    current_loc = loc;
                    current_map = distances.get(&current_loc).unwrap()
                }
            }
        }
        if total > longest_distance {
            longest_distance = total;
        }
        println!("\n");
    }

    println!("{}", longest_distance);
}

Day 10 Elves Look, Elves Say

link to problem

The Problem

Today, the Elves are playing a game called look-and-say. They take turns making sequences by reading aloud the previous sequence and using that reading as the next sequence. For example, 211 is read as "one two, two ones", which becomes 1221 (1 2, 2 1s).

Look-and-say sequences are generated iteratively, using the previous value as input for the next step. For each step, take the previous value, and replace each run of digits (like 111) with the number of digits (3) followed by the digit itself (1).

For example:

1 becomes 11 (1 copy of digit 1).

11 becomes 21 (2 copies of digit 1).

21 becomes 1211 (one 2 followed by one 1).

1211 becomes 111221 (one 1, one 2, and two 1s).

111221 becomes 312211 (three 1s, two 2s, and one 1).

Starting with the digits in your puzzle input, apply this process 40 times. What is the length of the result?

Your puzzle input is 1113122113.

Thoughts

This seems like a string builder program. I read in the input string, I count how many times I see the same char, then I write it out literally.

Take 111221 for example:

111 has a count of 3, so it becomes 31
22 has a count of 2, so it becomes 22
1 has a count of 1, so it becomes 11

Putting that all together gives us 312211, which is the answer.

Solution

For context, problem part 1 and part 2 were the same. The only difference between them was how many you run the process.

I wrote the solution out a couple of days ago, but I remember it pretty quick. I iterated over the string and looked at the previous character and the current character. If those two characters are equal, I up the count by 1. If not, I append the count and previous character to my result string, set the current count equal to 1 and start the process over again. Once the iteration is finished, you have to remember to add the last count and character to the result string.

The above code got put into a function so that I can take its output and use it as input. This also made it easy to call it 40 or 50 times too.

use std::io;

fn new_string(line: &str) -> String {
    let mut count = 0;
    let mut result = String::new();

    let mut current_char = None;
    for character in line.chars() {
        match current_char {
            None => {
                current_char = Some(character);
                count = 1;
            }
            Some(old_char) => {
                if old_char.eq(&character) {
                    count += 1;
                } else {
                    result.push_str(format!("{count}{old_char}").as_str());
                    current_char = Some(character);
                    count = 1;
                }
            }
        }
    }
    // This is here to pick up the last count and char
    result.push_str(format!("{count}{}", current_char.unwrap()).as_str());
    result
}

fn main() {
    for line in io::stdin().lines() {
        let mut data = line.unwrap();
        println!("Start: {data}");

        for round in 1..=50 {
            let prev_data = data.clone();
            data = new_string(&data);
            println!("({round}): {prev_data} -->  {data}");
        }
        println!("The final result has {} digits in it.", data.len());
        println!("\n\n");
    }
}

Day 11: Corporate Policy

link to problem

The Problem

Santa's previous password expired, and he needs help choosing a new one.

To help him remember his new password after the old one expires, Santa has devised a method of coming up with a password based on the previous one. Corporate policy dictates that passwords must be exactly eight lowercase letters (for security reasons), so he finds his new password by incrementing his old password string repeatedly until it is valid.

Incrementing is just like counting with numbers: xx, xy, xz, ya, yb, and so on. Increase the rightmost letter one step; if it was z, it wraps around to a, and repeat with the next letter to the left until one doesn't wrap around.

Unfortunately for Santa, a new Security-Elf recently started, and he has imposed some additional password requirements:

Passwords must include one increasing straight of at least three letters, like abc, bcd, cde, and so on, up to xyz. They cannot skip letters; abd doesn't count.

Passwords may not contain the letters i, o, or l, as these letters can be mistaken for other characters and are therefore confusing.

Passwords must contain at least two different, non-overlapping pairs of letters, like aa, bb, or zz.

For example:

hijklmmn meets the first requirement (because it contains the straight hij) but fails the second requirement requirement (because it contains i and l).

abbceffg meets the third requirement (because it repeats bb and ff) but fails the first requirement.

abbcegjk fails the third requirement, because it only has one double letter (bb).

The next password after abcdefgh is abcdffaa.

The next password after ghijklmn is ghjaabcc, because you eventually skip all the passwords that start with ghi..., since i is not allowed.

Given Santa's current password (your puzzle input), what should his next password be?

Your puzzle input is hxbxwxba.

Thoughts

The password being a fixed size great help. 8 characters is small enough that I can create a function for each one of these checks and not care how long it will take to process.

For no reason in particular, I am thinking about fancy stuff like a validate function that takes a list of functions and a string as input. The string will then get tested against all the functions in the list and if any of the function return false, it will return false.

The reason I can do this is because all the validation checks have the same function signature, which is that they take in a string reference and return a boolean.

The harder part of this question might be the incrementing of strings. I'm silly. I have been sitting here struggling to think of ways to interate over the charaters while skipping i, o, and l, like that is actually a requirement. I will use the numbers 0 - 25 and i will convert them back and forth between characters as needed. I'm thinking a struct that holds an internal list of numbers. It has an increment method that cycles up and another method that returns the string representation of the array so that I can pass it to the validate function.

I could take time to think about the other parts of the problem, but I'm pretty tired. So lets write this up and go to bed.

Solution

This took a lot longer to write than I thought it would and, with regard to speed of the code, this is, by far, the slowest thing I have written so far.

use std::collections::HashMap;
use std::io;

struct Password {
    internal: Vec<usize>,
    number_map: HashMap<usize, String>,
    letter_map: HashMap<String, usize>,
}

impl Password {
    fn new(
        data: &str,
        number_map: HashMap<usize, String>,
        letter_map: HashMap<String, usize>,
    ) -> Self {
        let internal: Vec<usize> = data
            .chars()
            .map(|x| x.to_string())
            .map(|y| letter_map.get(&y).unwrap().clone())
            .collect();
        Self {
            internal,
            number_map,
            letter_map,
        }
    }

    fn to_string(&self) -> String {
        self.internal
            .iter()
            .map(|x| self.number_map.get(x).unwrap())
            .map(|y| y.clone())
            .collect()
    }

    fn increment(&mut self) {
        let mut index = self.internal.len() - 1;

        loop {
            match self.internal[index] {
                25 => {
                    self.internal[index] = 0;
                    if index == 0 {
                        break;
                    } else {
                        index -= 1;
                    }
                }
                _ => {
                    self.internal[index] += 1;
                    break;
                }
            }
        }
    }
}

fn validate(funcs: Vec<fn(&str) -> bool>, input: String) -> bool {
    let mut result = true;

    for func in funcs.iter() {
        match func(&input) {
            false => {
                result = false;
                break;
            }
            true => {}
        }
    }
    result
}

fn contains_unwanted_letters(data: &str) -> bool {
    let mut result = true;

    for letter in data.chars() {
        match letter {
            'o' | 'i' | 'l' => {
                result = false;
                break;
            }
            _ => {}
        }
    }
    result
}

fn contains_two_pairs(data: &str) -> bool {
    let mut pairs = Vec::new();

    let list: Vec<char> = data.chars().collect();

    let mut index = 1;
    while index < list.len() {
        let prev_char = list[index - 1];
        let curr_char = list[index];

        match prev_char.eq(&curr_char) {
            true => {
                if !pairs.contains(&format!("{prev_char}{curr_char}")) {
                    pairs.push(format!("{prev_char}{curr_char}"));
                    index += 1;
                }
            }
            false => {}
        }

        index += 1;
    }

    pairs.len() >= 2
}

fn contains_seq_letters(data: &str) -> bool {
    let letter_map: HashMap<String, usize> = "abcdefghijklmnopqrstuvwxyz"
        .chars()
        .map(|x| x.to_string())
        .enumerate()
        .map(|(num, letter)| (letter, num))
        .collect();

    let mut result = false;

    let list: Vec<String> = data.chars().map(|x| x.to_string()).collect();
    let mut index = 2;

    while index < list.len() {
        let num_1 = letter_map.get(&list[index - 2]).unwrap();
        let num_2 = letter_map.get(&list[index - 1]).unwrap();
        let num_3 = letter_map.get(&list[index]).unwrap();

        //println!("{}, {}, {}", num_1, num_2, num_3);

        if num_1 + 1 == *num_2 && num_2 + 1 == *num_3 {
            result = true;
            break;
        }
        index += 1;
    }
    //println!("seq: {result}");
    result
}

fn main() {
    let mut letter_to_number = HashMap::new();
    let mut number_to_letter = HashMap::new();

    for (index, letter) in "abcdefghijklmnopqrstuvwxyz".chars().enumerate() {
        letter_to_number.insert(index.clone(), letter.to_string());
        number_to_letter.insert(letter.to_string(), index);
    }

    for line in io::stdin().lines() {
        let data = line.unwrap();

        let mut password = Password::new(
            &data.to_string(),
            letter_to_number.clone(),
            number_to_letter.clone(),
        );

        let mut result = password.to_string();
        let checks = vec![
            contains_seq_letters,
            contains_unwanted_letters,
            contains_two_pairs,
        ];

        while !validate(checks.clone(), result.clone()) {
            password.increment();
            result = password.to_string();
            //println!("{result}");
        }

        println!("{result}");
    }
}

I did everything I said I was going to do. I created a struct called Password that has a increment method and a to_string method. Internally, it manipulates and Vec of numbbers, which makes the implementation for the increment method manageable.

I have a validate function that takes a list of functions with the signature of fn (&str) -> bool and it also has a parameter called input which is a String. The validate function iterates over the functions in the list, it passes a reference to input to those functions and makes sure they all return true.

I then wrote out each of the requirements as functions.

Architectually, I really like this code because everything is broken down into small components. Maintaining this code would a breeze. That said, the reason the code is slow to solve the problem is because I separated everything out.

The next password after ghijklmn is ghjaabcc, because you eventually skip all the passwords that start with ghi..., since i is not allowed.

My code increments that password one unit at a time, which means that I have to go through every ghi.... combination before getting to the correct answer. For this test input, the code took so long to complete that I was positive that I had an infinite loop somewhere. It wasn't until I killed the program and added print statements that realized that the program is fine, its just slow. That said, it was really cool to see the password increment up super fast.

The Problem Part 2

After I found the password in part 1, they wanted me to find the next password. So the code stays the same, but I did manually increment part 1's password by one to that it would be invalid. Otherwise the code returns the input because the input is a valid password.

Day 12: JSAbacusFramework.io

link to problem

The Problem

Santa's Accounting-Elves need help balancing the books after a recent order. Unfortunately, their accounting software uses a peculiar storage format. That's where you come in.

They have a JSON document which contains a variety of things: arrays ([1,2,3]), objects ({"a":1, "b":2}), numbers, and strings. Your first job is to simply find all of the numbers throughout the document and add them together.

For example:

[1,2,3] and {"a":2,"b":4} both have a sum of 6.

[[[3]]] and {"a":{"b":4},"c":-1} both have a sum of 3.

{"a":[-1,1]} and [-1,{"a":1}] both have a sum of 0.

[] and {} both have a sum of 0.

You will not encounter any strings containing numbers.

What is the sum of all numbers in the document?

Thoughts

I don't want to use a JSON library for this. This seems like a string parser will do. I think I an use a state machine to capture the number.

States:

InNumber
OutNumber

The first character is a - or a digit and the rest of the characters are digits. Since this is JSON, the starting state is OutNumber.

Everytime I capture a number, I will add it to the sum.

In terms of representing the number, I will build it as a string and parse it once I hit the OutNumber state.

Given that there are only two states, I can probably use a boolean for them.

Solution

The code is simplier than I thought. Technically speaking, it is a state machine, but since there are only two states, I do not need a variable to keep track of it.

use std::io;

fn main() {
    for line in io::stdin().lines() {
        let mut number = String::new();
        let mut sum: i32 = 0;
        for character in line.unwrap().chars() {
            if character.eq(&'-') || character.is_digit(10) {
                number.push(character);
            } else {
                match number.is_empty() {
                    true => {}
                    false => {
                        sum += number.parse::<i32>().unwrap().clone();
                        number = String::new();
                    }
                }
            }
        }

        println!("sum: {sum}");
    }
}

The Problem Part 2

Uh oh - the Accounting-Elves have realized that they double-counted everything red.

Ignore any object (and all of its children) which has any property with the value "red". Do this only for objects ({...}), not arrays ([...]).

[1,2,3] still has a sum of 6.

[1,{"c":"red","b":2},3] now has a sum of 4, because the middle object is ignored.

{"d":"red","e":[1,2,3,4],"f":5} now has a sum of 0, because the entire structure is ignored.

[1,"red",5] has a sum of 6, because "red" in an array has no effect.

Thoughts

They want me to keep track of the curly brackets. That said, this is pretty tricky because "red" could be the last item in the object, and, if it is, I have to ignore all the numbers collected in that object.

I also have to take nested children into consideration as well. So...Is this like a Stack where each entry represents a level of depth? Maybe not a stack. I think I can use a Vec and have each index be a sum for that depth. If I see "red", everything at the idex and past it get set to zero.

At the end of the program, I sum the Vec.

This program will be easier to write if I use a Vec of a fixed size. The input.txt file doesn't look like it has too many nested objects. I will start with a size of 10 and bump it if I need to.

Second attempt

I underestimated the problem... So here I am days later attempting to solve it again.

This is awkward. Enough time has passed that I forgot what I was doing and which mistakes I made. Oh well.

I think I wanted to solve this recursively? Like, sum all object from the inner nested ones outward. For example,

We know this {"d":"red","e":[1,2,3,4],"f":5} is 0 because there is a "red" in the object. We know this {"d":"1","e":[1,2,"red",4],"f":5} is 13 because the red is ignored (array rule).

If we can sum these individually and sum them together as we go back up the stack, we should get the answer.

Now how to I recursively break the structure down...

Something like this might work. Let me try it.

def test(vec, start):
   sum = 0
   string = "{"
   for x in range(index, len(vec)):
       if vec[x] == "{":
	     sum += test(vec, x + 1)
	   elif vec[x] == "}":
	     # sum rules
		 # do this is a different function
		 string += "}"
		 sum += func()
	   else:
	     string += vec[x]

I admit defeat. I had a lot of fun, but nothing I did work.

I am ready to move on with life.

Rust Programs