Computer Science

# Graphs: Level 4 Challenges

Curious George plays around on a planar grid. George can move one space at a time: left, right, up or down.

That is, from $(x, y)$ George can go to $(x+1, y)$, $(x-1, y)$,$(x, y+1)$, or $(x, y-1)$.

George can access any point $(x,y)$ where the sum of the digits of $|x|$ $+$ the sum of the digits of $|y|$ is $\leq 19$.

How many points can George access if he starts at $(0,0)$ including $(0,0)$ itself?

Explicit Examples

• $(59, 79)$ is inaccessible because $5 + 9 + 7 + 9 = 30$, and $30 > 19$
• $(-5, -7)$ is accessible because $|-5| + |-7| = 12 \leq 19$
• $(190,90)$ is not reachable, considering its neighbors are all not reachable.

In a laboratory housed in kotebe micro-organisms were arranged in a $n\times n$ grid for studying purpose. By accident one of the laboratory technicians spills an infectious virus on some of the organism.This virus has the ability to infect the organism located immediately (east, west, north and south) of its already infected organism in $3$ microseconds.

To mitigate the rapid spread of this deadly virus some of the grid indices were left empty. How many microseconds does it take for all the organisms to be infected for the $19\times 19$ grid shown below. were $0$ means infected and $1$ means normal and - means empty.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,-,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,-,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,-,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,0,1,1,-,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,-,1,1,1,1,1,1,1,1,1,1,1,1,1 

Details and Assumptions

-Explicit example, If the virus was spilled on a $3\times 3$ grid.

$\begin{pmatrix} 1 & 1 & 1 \\ 1 & - & 1 \\ 0 & 1 & - \end{pmatrix}\overset { 3\mu s }{ \longrightarrow } \begin{pmatrix} 1 & 1 & 1 \\ 0 & - & 1 \\ 0 & 0 & - \end{pmatrix}\overset { 3\mu s }{ \longrightarrow } \begin{pmatrix} 0 & 1 & 1 \\ 0 & - & 1 \\ 0 & 0 & - \end{pmatrix}\cdots \begin{pmatrix} 0 & 0 & 0 \\ 0 & - & 0 \\ 0 & 0 & - \end{pmatrix}$

For a total of 15 microseconds.

The organism will quickly start infecting other organisms after being infected.

##### Here is an easier version

Sally is a very bad skater, so she can only skate in one direction! But Sally still wants to find her dad in the least amount of moves possible so that she can get off the ice. Sally's only way of stopping is (crashing into) walls or the edge of the ice rink.

We describe the ice rink using the following notation:

(#) -- Wall
(.) -- Free space
(S) -- Sally's starting position

For example, in the ice rink at right, the shortest path is 18 steps.

Here is a text file of 5 ice rinks of size $20 \times 20$. The rinks are separated by hyphens.

Find the sum of the shortest paths of these five $20 \times 20$ ice rinks.

Note: Sally has to stop at her father's position. She will slide past him if there are no walls.

###### Image credit: Flickr Saad Akhtar

An engineer working for a telecom company wants to design a cable network in a small nation. He can only bury the cables along main roads. Some paths are more expensive than others. It turns out that a previous employee of the company had already layed a network that is not efficient. In order to minimize costs, our engineer wants to optimize the network by removing some edges while keeping all points on the network connected.

For example, the network below can be optimized by removing the edge from $1$ to $4$: This saves a cost of $3$.

The engineer is given this larger network to optimize. What is the total cost saved?

Details and assumtions

• The network is represented in the text file is represented in an adjacency matrix representation. Basically, the cost from node $x$ to node $y$ is represented in the matrix $A$ as $A_{xy}$(column $x$, row$y$). $A_{xy}=0$ if a path doesnt exist from $x$ to $y$.

• The example network in the picture above has the following adjacency matrix representation:

Sue is a coordinator for UPS, and she's planning out tomorrow's route. Her next assignment is a truck in New York City, which must make 99 deliveries while driving on the rectangular grid of the city's streets.

If the coordinates the driver must reach are found in this list (measured in block lengths), which of the following is the closest to the minimum distance the truck will need to travel (in blocks)?

×