Table of content

What is this :grey_question:

The rules of the game are explained in my original post.

45th Challenge

Challenge

Recently I discovered code wars. Since then I have done a lot of challenges on that platform. It was ok for me for the moment. I don’t feel like I have broken the rules of this challenge, but I’m keeping at it doing what ever I’m motivated to do. I’m starting to reach my limitations and I see I have a gap in algorithms and how they work.

I feel like my solutions are limited by the fact that I do not know how to use fundamental algorithms. I have two new challenges, a series of algorithms is the first.

So where to start? I started my search by looking for some good cheat sheets on algorithms here is what I found: a good Overview of various algorithms

Graph theroy has inspired be most. I want to learn it, so from my overview I go on a further search and find (an online presentation of the basics)[https://web.stanford.edu/class/cs97si/06-basic-graph-algorithms.pdf]

GRAPH consists of nodes and one or bidirectional vertices

What do we need as storage?

nodes can be stored in arrays

edges can be stored in either adjacency matrix or adjacency list. Matrix lists each connection and a 1 if it exists and a 0 if it does not. Matix uses lots of memory O(n^2). Adjacency List uses less space. Each node has a list of nodes it points to.

Today’s challenge: Prepare a storage for a graph using an adjacency list that consists of arrays and an array of Nodes.

Solution :white_check_mark: 

	fn main() {
	    // Implementation of example
	    // on page 10 of https://web.stanford.edu/class/cs97si/06-basic-graph-algorithms.pdf
	    const M: usize = 8;
	    const N: usize = 5;

	    let mut e = [(usize::MAX, usize::MAX); M];
	    let mut le = [usize::MAX; N];

	    let edges: [(usize, usize); 8] = [
	        (0, 1),
	        (1, 2),
	        (0, 2),
	        (0, 4),
	        (3, 2),
	        (2, 1),
	        (3, 1),
	        (1, 4),
	    ];

	    let mut edge_id = 0;

	    for edge in edges {
	        println!("Adding Edge: {} -> {}", edge.0, edge.1);

	        let from = edge.0;
	        let to = edge.1;

	        e[edge_id].0 = to;
	        e[edge_id].1 = le[from];
	        le[from] = edge_id;

	        edge_id += 1;
	    }

	    println!("Edges = {:?}", e);
	    println!("Last Edges = {:?}", le);

	    // iterate over edges starting from 0
	    let mut id = le[0];
	    while e[id].1 != usize::MAX {
	        print!(" 0 -> {}", e[id].0);
	        id = e[id].1;
	    }

    	print!(" 0 -> {}", e[id].0);
	}

See github link to playground