
## Analytical Functions

Analytical functions are brought into existence to solve the problems that we have with Aggregate functions. The biggest disadvantage of these Aggregate functions is that they always reduce the number of results, but what if we want to be able to perform functions on all our results based on the results? (think at ranking, row_number, top N problems, ...)

Here I will explain some of the Analytical function tricks that we can use to solve common problems.

Some of the database engine specific analytical functions:

* **rank()** : Returns a sequential number for the result set, this differs from row_number because this function gives duplicates the same number.
* **dense_rank()** : Does the same as rank(), only will it put gaps between the next result.
* **row_number()** : Returns a sequential number for the result set.
* **ntile(n)** : Distributes the result into groups, this returns the number to which the group belongs.

### The over() function

One of the things I have to explain first before we are able to show special queries is the usage of the over() function. The over() function will execute a reporting function over the complete table without the need of a GROUP BY statement. We can also specify a PARTITION BY to this over function, which is going to allow us to perform a GROUP BY on the OVER function.

More details to this can be found here: [http://docs.oracle.com/cd/B19306_01/server.102/b14200/functions001.htm](http://docs.oracle.com/cd/B19306_01/server.102/b14200/functions001.htm)

### MIN MAX problems (also called minimax)

Let's say that we have a table that holds the values of the language usages of a country. What if we want to get the maximum spoken languages from those countries, and then get the language that is spoken the least in that country?

This is a great problem to use a over function in. You just select the maximum usages, and then you can add for example a column that will put an X for the language that is spoken the least. To do this we use a case structure that checks if the max usage of a language is equal to the min usage over the whole result set of the max usages.

**Result:**

```sql
SELECT iso, max(usage),
  CASE
    WHEN MAX(usage) = MIN(MAX(usage)) OVER() THEN 'x' ELSE ' '
  END
FROM languageusage
WHERE hasc IN('BE', 'DE')
GROUP BY iso
```

**Our result after running the query:**

iso | usage | min(max(usages))
:-: | ----: | :--------------
kur| 0.0049998134397970222 |
ned| 0.60320897726154155 |
tur| 0.026367175354153453 |
fra| 0.33231617285165865 |
ita| 0.02480559110148637 |
sla| 0.0148750668507394 |
ara| 0.015848016537060736|
dui| 0.93813663669266079 |
poo| 0.0034948944691118493| X
spa| 0.0049217442661679302|
grn| 0.0045023195651903531|

### Creating order based on criteria

We want to be able to assign numbers based on some criteria.

**Example:** Select races, and assign a number based on:

* rownumber for each resort, sorted by racedate within resort
* rownumber for resort and racedate, sorted by resort, racedate (for all)
* rownumber for racedate, sorted by racedate (for all)

```sql
SELECT resort, racedate
, rank() over(partition by resort order by racedate) "rownr / resort"
, rank() over(order by resort, racedate) "rownr by resort and racedate"
, rank() over(order by racedate) "rownr by racedate"
FROM races
WHERE extract(year from racedate) = 2008
GROUP BY resort, racedate
ORDER BY resort, racedate
```

### Clipping

A rarely known technique for databases is called **Clipping**, clipping allows us to remove an extreme band of results from a result set. (For example, when we measured different points and we want to remove the extreme points from this resultset, then we can use clipping).

This is where ntile(n) comes in handy, we use it to divide our result set in groups, and then we select the groups that lie within boundaries.

**Example:** Let us select measure points of longitude and latitude, and we will remove the most extreme points.

Then the query becomes:

```sql
SELECT lev2, latitude, longitude,
  CASE 
    WHEN ntile(10) OVER (PARTITION BY lev2 ORDER BY latitude) BETWEEN 2 AND 9 
    THEN latitude 
  END x,
  CASE 
    WHEN ntile(10) OVER (PARTITION BY lev2 ORDER BY longitude) BETWEEN 2 AND 9 
    THEN longitude 
  END y
FROM cities
WHERE iso = 'BE'
AND lev2 IS NOT NULL
AND latitude IS NOT NULL
AND longitude IS NOT NULL;
```

### Simulating WIDTH_BUCKET

WIDTH_BUCKET is an oracle specific command that lets you construct equiwidth histograms, in which the histogram range is divided into intervals that have identical size. (More here: [https://docs.oracle.com/cd/B19306_01/server.102/b14200/functions214.htm](https://docs.oracle.com/cd/B19306_01/server.102/b14200/functions214.htm))

Since this is only in oracle we want to simulate this so we can use it in other database engines. To simulate this we can use the function CEIL together with the OVER functions.

So then this becomes:

```sql
SELECT ceil(row_number() OVER(ORDER BY ... ) / 5.0)
```

### Cumulative Total and Gliding Totals

If we want to be able to select the **cumulative total** of a resultset, then we can use this query:

```sql
SUM(points) OVER(ORDER BY points, name) AS cumul
```

However if we want to calculate the **gliding total**, then we need to use this:

```sql
SUM(points) OVER(ORDER BY date RANGE BETWEEN 90 PRECEDING AND CURRENT ROW) AS mov_average
```

## Combined Select Queries

With combined select queries we mean the joining of 2 different select queries with the use of special operators such as **union, union all, intersect, except, minus, ...**

&gt;One thing to note is that even though this is explained in this article, it is not recommended to be used. Combined Select Queries are a feature of the database engines but are mostly slower then **CTE's (Common Table Expressions)** that is why I recommend using those rather then the combined select queries. This is also the reason why this portion of the article is relatively slow compared to the rest.

### Union and Union ALL

The **union** operator will merge tables row by row but it will remove the duplicate rows. When we use **union all** then we will do the same as union, but this time we will include the duplicate rows.

**Example:**

```sql
SELECT hasc2, length
FROM boundaries
WHERE hasc1 = 'DE'
UNION ALL
SELECT hasc1, length
FROM boundaries
WHERE hasc2 = 'DE'
ORDER BY length
```

&gt; **Special Note:** If you are using a database engine that does not support the rollup and cube functions, then you can simulate those using the union operator.

### Intersect

The intersect operator will only keep the rows that the different queries have in common.

**Example:**

```sql
SELECT name,
  CASE
    WHEN MAX(SUM(points)) OVER(PARTITION BY gender, season) = SUM(points) THEN 'x'
    ELSE ' '
  END "result"
FROM Ranking
WHERE discipline IS NOT NULL
GROUP BY gender, season, name
  INTERSECT
SELECT name, 'X'
FROM competitors
WHERE nation = 'SWE'
```

### Except of minus (difference)

The except of minus operators will take the first query and they will remove every row that is the result from the other queries.

**Example:**

```sql
SELECT hasc, population, area
FROM regios
WHERE SUBSTR(hasc, 1, 2) = 'BE' AND level = 3
  EXCEPT
SELECT parent, SUM(population), SUM(area)
FROM regios
WHERE SUBSTR(hasc, 1, 2) = 'BE' AND level = 4
GROUP BY parent
```

SQL - Part 3 - Analytical Functions (Ranking, Rows, Over, ...)


## Aggregate Functions

Aggregate functions are functions that are going to aggregate data from columns, or rows. Some of these functions are: SUM, AVG, MAX, MIN, .... .

### Special GROUP BY where we are going to group by values using a CASE and then sort by based on that case

__Example:__ In this example we are sorting based on the rank achieved, we will GROUP BY this rank category so that we can count how many times the person has achieved this rank. And then we will sort based on the category from excellent to really bad.

> The trick here is to use the GROUP BY on both the category but also the category as a number, this is needed for the order by to work

```sql
SELECT cid, name,
CASE
  WHEN rank IN(1, 2, 3) THEN 'excellent'
  WHEN rank IN(4, 5, 6) THEN 'good'
  WHEN rank IN(7, 8, 9) THEN 'almost ok'
  WHEN rank IN(10, 11, 12) THEN 'bad'
  ELSE 'really bad'
END choice, count(1) amount

FROM results
GROUP BY cid, name,
CASE
  WHEN rank IN(1, 2, 3) THEN 'excellent'
  WHEN rank IN(4, 5, 6) THEN 'good'
  WHEN rank IN(7, 8, 9) THEN 'almost ok'
  WHEN rank IN(10, 11, 12) THEN 'bad'
  ELSE 'really bad'
END,
CASE
  WHEN rank IN(1, 2, 3) THEN 1
  WHEN rank IN(4, 5, 6) THEN 2
  WHEN rank IN(7, 8, 9) THEN 3
  WHEN rank IN(10, 11, 12) THEN 4
  ELSE 5
END
ORDER BY cid, name,
CASE
  WHEN rank IN(1, 2, 3) THEN 1
  WHEN rank IN(4, 5, 6) THEN 2
  WHEN rank IN(7, 8, 9) THEN 3
  WHEN rank IN(10, 11, 12) THEN 4
  ELSE 5
END;
```

### Pivoting the result table

By pivoting we want to move our results from vertical to horizontal and reverse

Example (Where result could be A, B, C, D):

NR | Name | Result
-- | ---- | ------
1 | ABBA | A
2 | Bert | B
3 | Jan | C
4 | Dan | D

And when we pivot this we get:

NR | Name | A | B | C | D |
-- | ---- | - | - | - | - |
1 | ABBA | X | | | |
1 | Bert | | X | | |
1 | Jan | | | X | |
1 | Dan | | | | X |

__Example:__ If we perform this on the previous example then we get this query:

```sql
SELECT cid, name
, COUNT(CASE WHEN rank IN(1, 2, 3) THEN 'X' END) "excellent"
, COUNT(CASE WHEN rank IN(4, 5, 6) THEN 'X' END) "good"
, COUNT(CASE WHEN rank IN(7, 8, 9) THEN 'X' END) "almost ok"
, COUNT(CASE WHEN rank IN(10, 11, 12) THEN 'X' END) "bad"
, COUNT(CASE WHEN rank > 12 THEN 'X' END) "really bad"
FROM results
GROUP BY cid, name
ORDER BY cid, name;
```

### Getting a sub-result after every group by (CUBE)

When we use the GROUP BY function, then we will select certain intervals and group those together. When we do this we are actually creating sub-results. Using ROLLUP we will generate a result set that will show an aggregation of every single combination possible. (this for the selected columns)

__Example 1:__ We select races that happened after 2000, limit it to some disciplines, and then we are going to create sub results after every GROUP BY and completely at the end.

```sql
SELECT EXTRACT(year FROM racedate) year, discipline, count(1) number_of_races
FROM races
WHERE EXTRACT(year FROM racedate) >= 2000 AND discipline IN ('SL', 'SG')
GROUP BY CUBE(EXTRACT(year FROM racedate), discipline)
ORDER BY year;
```

The result (simulated and not the real one) will look a bit like this:

| NR | Disc | NUMBER_OF_GAMES |
| ----| ------ | --------------- |
| 1 | SG | 5 |
| 2 | SL | 3 |
| 3 | SE | 2 |
| 4 | SE | 5 |
| ALL | (NULL) | 5 |
| ALL | (NULL) | 3 |
| ALL | (NULL) | 7 |
| ALL | (NULL) | 10 |

The NULL column will show the counted values from ABOVE, or NULL when it can't count those together.

> __Note:__ We are able to change the NULL value to something else such as '---' or ' ' by using the GROUPING function. This will be explained in the next example.

__Example 2:__ We now want to remove that NULL value (We don't like those kind of values in a result set ;) ). This can be done by using the GROUPING function. GROUPING accepts 1 parameter and that is a column. As a result it will return a 1 or a 0 depending on if the result was aggregated or not.

In our example the grouping will thus return 1 when we have a CUBE row, or 0 when we don't have a CUBE row. So if we check if the GROUPING(discipline) is 1 then we know it is cubed and then we just enter '---'. Else we print the discipline.

```sql
SELECT EXTRACT(year FROM racedate) year, CASE WHEN grouping(discipline) = 1 THEN '---' ELSE discipline END, count(1) number_of_races
FROM races
WHERE EXTRACT(year FROM racedate) >= 2000 AND discipline IN ('SL', 'SG')
GROUP BY CUBE(EXTRACT(year FROM racedate), discipline)
ORDER BY year;
```

> __Note:__ We used CUBE here, but there is another function called ROLLUP, ROLLUP will also get a count of values, but this time ROLLUP will "generate a result set that shows the aggregates for a hierarchy of values in the selected columns." (which in simple terms means: 1 result over for each combination of elements in the group by, and not total set / group by on the end.)

### Setting the name of the rollup results

For this we can use a ROLLUP which will give us the extra rows, but we will also need to name those (which is tricky). We can do this by applying a trick. We know that GROUPING returns 1 or 0. And we also know that together this could return 0, 1 or 2. Now if it is 1 then we are not sure in which column we are. so that is why we will multiply one of the groupings by 2 so that we get 4 unique results back which we can then handle.

You can compare this by a binary table for 2 values (this is when we do not multiply by 2 and just add them together):

| a1 | a2 | q0 |
| -- | -- | -- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 2 |

However when we multiply the first column by 2 then we are actually using the above binary table as the way it is supposed to work.

| a1 | a2 | q0 |
| -- | -- | -- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 2 |
| 1 | 1 | 3 |

Which returns 4 values for us to use.

__Example:__ Let's say we want to get the population from France and Germany in their county. Now we want to get the sum of the total population in both France and Germany but also a sub-result noting the total population for France and Germany separately.

```sql
SELECT
CASE
WHEN GROUPING(iso) + GROUPING(lev1) = 0 THEN iso ELSE ' '
END iso
, lev1, count(1)

,CASE 2* GROUPING(iso) + GROUPING(lev1)
WHEN 0 THEN lev1
WHEN 1 THEN 'total country ' || iso
WHEN 3 THEN '**total**'
END regio

FROM cities
WHERE (iso = 'DE' OR iso = 'FR') AND lev1 IS NOT NULL
GROUP BY ROLLUP(iso, lev1)
```

### Putting it all together

For this exercise we are going to put everything together that we have learned so far. The task here was to get data from a table that holds regios, we grouped those together to be able to get the continents, area, population and more.

On the end we had to make sure that we had this result:

continent | population | area <= 50000 | area <= 100000 | area <= 500000 | area > 500000 | #
:-------: | :--------: | :-----------: | :------------: | :------------: | :-----------: | :-:
AFR | pop < 1 million | 11 | 0 | 1 | 0 | 12 AFR | pop 1-5 million | 3 | 3 | 4 | 3 | 13 AFR | pop > 5 million | 1 | 1 | 8 | 13 | 23
--- | AFR totaal | 15 | 4 | 13 | 16 | 48
ASI | pop < 1 million | 7 | 0 | 0 | 0 | 7 ASI | pop 1-5 million | 4 | 1 | 4 | 1 | 10 ASI | pop > 5 million | 2 | 4 | 12 | 10 | 28
--- | ASI totaal | 13 | 5 | 16 | 11 | 45
EUR | pop < 1 million | 10 | 1 | 1 | 0 | 12 EUR | pop 1-5 million | 4 | 4 | 1 | 0 | 9 EUR | pop > 5 million | 5 | 4 | 11 | 3 | 23
--- | EUR totaal | 19 | 9 | 13 | 3 | 44
--- | globaal totaal | 47 | 18 | 42 | 30 | 137

For this we wrote this query:

```sql
SELECT
  -- Continent
  CASE 
    WHEN 
      grouping(parent) * 2 + grouping(
        CASE 
          WHEN population < 1000000 THEN 'pop < 1 million'
          WHEN population BETWEEN 1000000 AND 5000000 THEN 'pop 1-5 million' 
          ELSE 'pop > 5 million'
        END
      ) >= 1 THEN '---' 
    ELSE TO_CHAR(parent) 
  END continent,

  -- Population
  CASE grouping(parent) * 2 + grouping(
    CASE WHEN population < 1000000 THEN 'pop < 1 million' 
      WHEN population BETWEEN 1000000 AND 5000000 THEN 'pop 1-5 million' 
      ELSE 'pop > 5 million'
    END
  ) 
  WHEN 3 THEN 'globaal totaal'
  WHEN 1 THEN TO_CHAR(parent) || ' totaal'
  ELSE
  CASE 
    WHEN population < 1000000 THEN 'pop < 1 million' 
    WHEN population BETWEEN 1000000 AND 5000000 THEN 'pop 1-5 million' 
    ELSE 'pop > 5 million'
  END
  END population

  -- Area <= 50000
  , SUM(CASE WHEN area <= 50000 THEN 1 ELSE 0 END) "area <= 50000"
  , SUM(CASE WHEN area > 50000 AND area <= 100000 THEN 1 ELSE 0 END) "area <= 100000"
  , SUM(CASE WHEN area > 100000 AND area <= 500000 THEN 1 ELSE 0 END) "area <= 500000"
  , SUM(CASE WHEN area > 500000 THEN 1 ELSE 0 END) "area > 500000"

  -- Number of countries
  ,COUNT(1) "#"
FROM regios
WHERE parent IN('EUR', 'AFR', 'ASI')
  AND population IS NOT NULL
  AND area IS NOT NULL
GROUP BY ROLLUP(parent, 
  CASE 
    WHEN population < 1000000 THEN 'pop < 1 million'
    WHEN population BETWEEN 1000000 AND 5000000 THEN 'pop 1-5 million'
    ELSE 'pop > 5 million'
  END
)
ORDER BY parent,
  CASE population
  WHEN 'pop < 1 million' THEN 1
  WHEN 'pop 1-5 million' THEN 2
  ELSE 3
END;
```

> Don't be discouraged by a query's size, many of these query's look big but once you start writing them you just have to make sure you have the right formatting and then everything will fall in place just nicely.

SQL - Part 2 - Aggregate Functions (GROUP BY, CUBE, ROLLUP, ...)


While I was studying the course Databases at the University of Ghent, we encountered some special queries that we were not being thaught in the Professional Bachelor course. This is why I tried to summarise those queries here for everyone to learn from.

The database engine being used is Oracle SQL server. This has been chosen
because Oracle supports most of the functions that we needed in this class.
(Another good SQL engine to use is MSSQL).

> Please note, every query given here is based on the database that we had in
the class, this database is not mine and therefor I can not publish this here
nor post results of the query.

## Case Functions

### Order by given order

To order by a given order we are going to give a specific number from 1 .. x for the values that we want. We do this by using a case in the order part of our SQL statement.

__Example 1:__ Order by disciplines 'KB', 'GS', 'SL', 'DH', 'SG'

```sql
SELECT distinct discipline, resort
FROM races
ORDER BY
CASE discipline
  WHEN 'KB' THEN 1
  WHEN 'GS' THEN 2
  WHEN 'SL' THEN 3
  WHEN 'DH' THEN 4
  WHEN 'SG' THEN 5
  ELSE 6
END;
```

__Example 2:__ Order by NULL or other values (NULL first, then the other values)

```sql
SELECT rid, modus
FROM races
WHERE discipline = 'SL' AND gender = 'M'
ORDER BY
CASE
  WHEN modus IS NULL THEN 0
  ELSE (modus + 1)
END
ASC;
```

### Putting an X in one of multiple columns based on the value that we have

here is a query that is going to put an X in the column where we want it.

__Example 1:__ We are calculating the BMI and have 3 columns stating: "underweight",
"obesity", "normal". Now we are going to put an X in the column that matches the
person his/her weight.

```sql
SELECT
name
, weight
, gender
, ROUND((weight / (height * height) ), 3) BMI
, CASE WHEN ROUND((weight / (height * height) ), 3) < 17
    THEN 'X'
    ELSE ' '
  END underweight
, CASE WHEN ROUND((weight / (height * height) ), 3) BETWEEN 17 AND 23.999 
    THEN 'X'
    ELSE ' '
  END normal
, CASE WHEN ROUND((weight / (height * height) ), 3) >= 24 
    THEN 'X'
    ELSE ' '
  END obesity
FROM competitors
WHERE weight IS NOT NULL AND height IS NOT NULL
ORDER BY ROUND((weight / (height * height) ), 3);
```

__Example 2:__ We have races that are being done on a specific date, we want to be able to put an X based on the season.

```sql
SELECT EXTRACT(year FROM (racedate + 183)) season, racedate
, CASE WHEN racedate BETWEEN TO_DATE('21 03 ' || extract(year FROM racedate), 'dd MM YYYY') AND TO_DATE('20 06 ' || extract(year FROM racedate), 'dd MM YYYY') THEN 'X' ELSE ' ' END spring
, CASE WHEN racedate BETWEEN TO_DATE('21 06 ' || extract(year FROM racedate), 'dd MM YYYY') AND TO_DATE('20 09 ' || extract(year FROM racedate), 'dd MM YYYY') THEN 'X' ELSE ' ' END summer
, CASE WHEN racedate BETWEEN TO_DATE('21 09 ' || extract(year FROM racedate), 'dd MM YYYY') AND TO_DATE('20 12 ' || extract(year FROM racedate), 'dd MM YYYY') THEN 'X' ELSE ' ' END autumn
, CASE WHEN racedate BETWEEN TO_DATE('21 03 ' || extract(year FROM racedate), 'dd MM YYYY') AND TO_DATE('20 12 ' || extract(year FROM racedate), 'dd MM YYYY') THEN ' ' ELSE 'X' END winter
FROM races
WHERE EXTRACT(year FROM (racedate + 183)) BETWEEN 1990 AND 1992 AND discipline = 'SL'
ORDER BY summer desc, spring desc, autumn desc, winter desc, racedate;
```

### Replace NVL with a CASE structure

NVL is a database engine specific function that is going to replace the NULL values with a value that you give to it. We want to be able to use this on other database engines so that is why we are going to write this as a normal CASE structure.

__Example with NVL:__

```sql
SELECT rid, rank, nvl(points, 0)
FROM results
WHERE rank = 4 AND points < 12;
```

__Example with CASE:__

```sql
SELECT rid, rank,
CASE
WHEN points IS NULL THEN 0
ELSE points
END points
FROM results
WHERE rank = 4 AND points < 12;
```

### Combination of all the above

```sql
SELECT
CASE
WHEN nation IN ('CAN', 'USA') THEN 'North America'
WHEN nation IN ('BUL', 'RUS', 'CZE', 'SLO', 'CRO') THEN 'Eastern-Europe'
WHEN nation IN ('JPN', 'KOR') THEN 'Asia'
ELSE 'Western-Europe'
END Continent
, nation, name, finishaltitude
, CASE WHEN finishaltitude < 1200 THEN 'X' ELSE ' ' END "<1200" , CASE WHEN finishaltitude BETWEEN 1200 AND 1700 THEN 'X' ELSE ' ' END "1200-1700" , CASE WHEN finishaltitude > 1700 THEN 'X' ELSE ' ' END ">1700"
FROM resorts
WHERE finishaltitude IS NOT NULL
-- Order by: Western-Europe, Eastern-Europe, North America, Asia
ORDER BY
CASE
WHEN nation IN ('CAN', 'USA') THEN 3
WHEN nation IN ('BUL', 'RUS', 'CZE', 'SLO', 'CRO') THEN 2
WHEN nation IN ('JPN', 'KOR') THEN 4
ELSE 1
END
ASC

-- By category with X
, CASE WHEN finishaltitude < 1200 THEN 1
WHEN finishaltitude BETWEEN 1200 AND 1700 THEN 2
ELSE 3
END
ASC

-- Resort name
, name;
```

SQL - Part 1 - Advanced CASE Selecting


Mazes are really famous puzzles where the goal is to find the exit starting from an entrance. We can see these kind of puzzles as a labyrinth. When we found the solution we then draw over them to mark the path that we have to find.

Most of the time these puzzles are generated by computer programs, these computer programs then use algorithms such as depth-first searching to create the mazes. We can however also solve these puzzles by using the same algorithm.

> This article will cover the solving of a maze, there will be more efficient methods to solve these mazes but I will just explain one of the many. 

## Reading in the maze

Reading in the maze can be done in several different file formats. We will use a SVG format here because this lets us draw the solution on top of it easily.

### Example of a maze in svg:

```xml
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="112" height="96" version="1.1" xmlns="http://www.w3.org/2000/svg">
  <rect width="112" height="96" fill="white" stroke="none" />
  <title>5 by 4 orthogonal maze</title>
  <g fill="none" stroke="#000000" stroke-width="3" stroke-linecap="round" stroke-linejoin="round">
    <line x1="16" y1="16" x2="32" y2="16" />
    <line x1="48" y1="16" x2="80" y2="16" />
    <line x1="16" y1="80" x2="96" y2="80" />
    <line x1="16" y1="16" x2="16" y2="80" />
    <line x1="96" y1="16" x2="96" y2="80" />
    <line x1="64" y1="16" x2="64" y2="32" />
    <line x1="32" y1="32" x2="32" y2="48" />
    <line x1="32" y1="32" x2="48" y2="32" />
    <line x1="64" y1="32" x2="64" y2="48" />
    <line x1="64" y1="32" x2="80" y2="32" />
    <line x1="32" y1="48" x2="48" y2="48" />
    <line x1="48" y1="48" x2="48" y2="64" />
    <line x1="48" y1="48" x2="64" y2="48" />
    <line x1="80" y1="48" x2="80" y2="64" />
    <line x1="16" y1="64" x2="32" y2="64" />
    <line x1="48" y1="64" x2="64" y2="64" />
    <line x1="80" y1="64" x2="80" y2="80" />
  </g>
  <g fill="black" stroke="none" stroke-width="1">
    <text x="24" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">1</text>
    <text x="40" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">2</text>
    <text x="56" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">3</text>
    <text x="72" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">4</text>
    <text x="88" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">5</text>
    <text x="24" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">6</text>
    <text x="40" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">7</text>
    <text x="56" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">8</text>
    <text x="72" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">9</text>
    <text x="88" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">10</text>
    <text x="24" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">11</text>
    <text x="40" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">12</text>
    <text x="56" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">13</text>
    <text x="72" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">14</text>
    <text x="88" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">15</text>
    <text x="24" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">16</text>
    <text x="40" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">17</text>
    <text x="56" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">18</text>
    <text x="72" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">19</text>
    <text x="88" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">20</text>
  </g>
</svg>
```

To process this file we will use 2 regexes, one regex that will get the size and another regex to get the lines.

### Regex for the size:

```perl
m/<title>([0-9]*)\sby\s([0-9]*).*/g
```

### Regex for the lines:

```perl
m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g
```

We then process the file into a specific data structure to hold the lines, one that looks like this:

```perl
{
    "x1" => 0,
    "y1" => 0,
    "x2" => 0,
    "y2" => 0
}
```

A second thing that we can see in the svg files is that everything is based in a magnitude of 16. We therefor will divide the x and y values by 16 so that we have an incremental sequence.

The last thing that we will do with the file is save the number of columns and rows. This is done by getting the first group of the regex.

## Creating the adjacency list (neighbour list)

A last thing that we have to do before we can start applying our algorithm explained below this section is to create a adjacency list (commonly referred as a neighbour list). This list is a indication of every element with it’s neighbour.

### Output of the neighbour list for the maze given above:

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

This however is not as easy as it seems. We will have to take the lines that remove some of the neighbours into consideration. To do this we will first start finding all the neighbours. The neighbours that we can not reach will be noted down as a -1. The others will be the numbers.

After that we will go through every line and rule out the neighbours that not connected. As a last step we will then push all these neighbours on an array and print them out as stated above.

Now we have the neighbours and we can start with our algorithm to find the solution.

## Depth-first searching

When we have a graph, we can iterate over the nodes of this graph and go over every node. To do this we will see these nodes as 3 different categories:

* Black nodes, these are the discovered nodes
* Grey nodes, these are the discovered but not yet processed nodes
* White nodes, these are the nodes that are not yet discovered.

We then start at a random node and will go through all of it’s neighbours. For every of these neighbours we will then mark them as discovered and repeat these steps until we went through all the nodes.

In pseudo code this looks like this:

```
// Discovered nodes
discovered = array();

// Init White nodes
for (i = 0; i < discovered.size(); i++)
    discovered[i] = false;

// Start
endIdx = someEndIndex;
start_node_idx = someStartNodeIndex;
DFS(start_node_idx);

// Algorithm
void DFS(nodeIdx) {
    if (nodeIdx == endIdx) {
        // If end, mark discovered and return true
        discovered[nodeIdx] = true;

        return true;
    } else if (discovered[nodeIdx]) {
        // If already discovered, return false
        return false;
    } else {
        // Else, mark as discovered and process it's neighbours
        discovered[nodeIdx] = true;

        foreach (neighbour i of nodeIdx) {
            result = DFS(i);

            if (result) {
                return true; // Solution found, return
            }
        }

        return false; // Nothing found, cancel      
    }
}
```

We will use this later on in our perl code to solve the maze.
Printing the solution

Printing the solution is the most easy step to do. We will find the center of each point (\frac{left top + right bot}{2}) and then we will just draw a line from point to point while printing it out.
Putting it all together in perl code

After we have put all the above steps together we get this as a solution:

```perl
@ARGV = ("/PATH/05.svg"); # We can also remove this and call the program with the path as an argument.
undef $/;
$input=(<>);
$idx = 1;
my $rows;
my $cols;
# ====================
# Reading in the lines
# ====================
while ($input =~ m/<title>([0-9]*)\sby\s([0-9]*).*/g) {
    ($colCount, $rowCount) = ($1, $2);
    $rows = $rowCount;
    $cols = $colCount;
    print "Rows: $rows Cols: $cols\n";
}
my @lines;
while ($input =~ m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g) {
    ($x1,$y1,$x2,$y2) = ($1 / 16,$2 / 16,$3 / 16,$4 / 16);
    my %H = (
        "x1" => $x1,
        "x2" => $x2,
        "y1" => $y1,
        "y2" => $y2
    );
    #print "#$idx: X1 : ".$H{"x1"}." X2: $x2 Y1: $y1 Y2: $y2\n";
    $idx++;
    # Set row and col count
    #if ($y2 > $rows + 1) { $rows = $y2 - 1; }
    #if ($x2 > $cols + 1) { $cols = $x2 - 1; }
    # Add to lines
    push @lines, \%H;
}
# ================================================
# Getting the neighbours for each element
# HASH[EL + 1][top|right|bot|left] = value;
# ================================================
$elCount = $rows * $cols;
# For every element, get the border
my @elements = ();
my @corners = ();
for (my $i = 0; $i < $elCount; $i++) {
    my %H = (
        "top" => ($i + 1) - $cols,
        "right" => ($i + 1) + 1,
        "bot" => ($i + 1) + $cols,
        "left" => ($i + 1) - 1,
        "left_top_x" => 0,
        "left_top_y" => 0,
        "right_top_x" => 0,
        "right_top_y" => 0
    );
    # Row and column
    $row = int($i / $cols) + 1;
    $col = int($i % $cols) + 1;
    # Boundaries
    if ($H{"top"} > $elCount || $H{"top"} < 1) { $H{"top"} = 0; }
    if ($H{"right"} > ($row * $cols) || $H{"right"} < 1) { $H{"right"} = 0; }
    if ($H{"bot"} > $elCount || $H{"bot"} < 1) { $H{"bot"} = 0; }
    if ($H{"left"} < ((($row  - 1)* $cols) + 1) || $H{"left"} < 1) { $H{"left"} = 0; }
    #print "Row: $row Col: $col\n";
    $mult = 1;
    #print "El: #".($i + 1)." \n";
    @corners[$i] = {
        "left_top_x" => (($col + 0) * $mult), # Set left top corner
        "left_top_y" => (($row + 0) * $mult),
        "right_top_x" => (($col + 1) * $mult), # Set right top corner
        "right_top_y" => (($row + 0) * $mult)
    };
    #print "Top:   (".(($col + 0) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 0) * $mult).")\n";
    #print "Bot:   (".(($col + 0) * $mult).",".(($row + 1) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 1) * $mult).")\n";
    #print "Right: (".(($col + 1) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 1) * $mult).")\n";
    #print "Left:  (".(($col + 0) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 0) * $mult).",".(($row + 1) * $mult).")\n";
    foreach (@lines) {
        #print "(".$_->{"x1"}.",".$_->{"y1"}.") -> (".$_->{"x2"}.",".$_->{"y2"}.")\n";
        # Check if top neighbour
        if ($_->{"y1"} == (($row + 0) * $mult) && (($col + 0) * $mult) >= $_->{"x1"} && (($col + 1) * $mult) <= $_->{"x2"}) {
            # print "No Top Neighbour: ".($i + 1)."\n";
            undef $H{"top"};
        }
        # Check if bot neighbour
        if ($_->{"y1"} == (($row + 1) * $mult) && (($col + 0) * $mult) >= $_->{"x1"} && (($col + 1) * $mult) <= $_->{"x2"}) {
            # print "No Bot Neighbour: ".($i + 1)."\n";
            undef $H{"bot"};
        }
        # Check if right neighbour
        if ($_->{"x1"} == (($col + 1) * $mult) && (($row + 0) * $mult) >= $_->{"y1"} && (($row + 1) * $mult) <= $_->{"y2"}) {
            # print "No Right Neighbour: ".($i + 1)."\n";
            undef $H{"right"};
        }
        # Check if left neighbour
        if ($_->{"x1"} == (($col + 0) * $mult) && (($row + 0) * $mult) >= $_->{"y1"} && (($row + 1) * $mult) <= $_->{"y2"}) {
            # print "No Left Neighbour: ".($i + 1)."\n";
            undef $H{"left"};
        }
    }
    # print ($i + 1);
    # print ":";
    # print "\t".$H{"top"} if defined $H{"top"};
    # print "\t".$H{"right"} if defined $H{"right"};
    # print "\t".$H{"bot"} if defined $H{"bot"};
    # print "\t".$H{"left"} if defined $H{"left"};
    push @{$elements[$i]}, $H{"top"} if defined $H{"top"};
    push @{$elements[$i]}, $H{"right"} if defined $H{"right"};
    push @{$elements[$i]}, $H{"bot"} if defined $H{"bot"};
    push @{$elements[$i]}, $H{"left"} if defined $H{"left"};
    print "".($i + 1).":\t";
    foreach (@{$elements[$i]}) {
        print $_."\t";
    }
    print "\n";
}
# ================================================
# Finding a path
# ================================================
my $start;
my $end;
my $newElement;
my $oldElement;
my @solution;
# 1. Find start and start
print "Determining start and end point\n";
for ($i = 0; $i < scalar @elements; $i++) {
    for ($j = 0; $j < scalar @{$elements[$i]}; $j++) {
        if ($start && @{$elements[$i]}[$j] == 0) {
            print "End = ".($i + 1)."\n";
            $end = $i;
            last;
        }
        if (!$start && @{$elements[$i]}[$j] == 0) {
            print "Start = ".($i + 1)."\n";
            $start = $i;
        }
    }
}
# 2. Calculate path from start to end
# We see that in the lines above that we created a neighbour list graph
# To solve the maze we will therefor use a popular algorithm called depth first search
# Depth search will go through the neighbours by setting them discovered or not
my $discovered = ();
# Set discovered on false (all white nodes)
print "#Nodes: ".(scalar @elements)."\n\n";
for ($i = 0; $i < scalar @elements; $i++) {
    $discovered[$i] = 0;
}
# Start for the neighbours of our start element
DFS($start);
sub DFS {
    my ($i) = @_;
    # If this is the end of the maze, set as visited and add to solution
    if (($i + 1) == ($end + 1)) {                   # If solution, add to solution and return true
        push @solution, ($i + 1);
        $discovered[$i] = 1;
        return 1;
    } elsif ($discovered[($_ - 1)] == 1) {  # If visited already, return false
        return 0;
    } else {                                # Else process
        #print "Node: ".($i + 1)."\n";
        $discovered[$i] = 1;
        # For every neighbour, process it
        # If this returns true, then add it to the solution
        foreach (@{$elements[$i]}) {
            #print "Neighbour: ".($_)."\n";
            # If neighbour is 0, return false this is start or end!
            if ($_ != 0) {
                $result = DFS($_ - 1);
                if ($result == 1) {
                    push @solution, $_;
                    return 1;
                }
            }
        }
        # Else return nothing
        return 0;
    }
}
# Also push the solution
push @solution, ($start + 1);
# ===============================================================
# Printing
# Create lines from start to end depending on the solutionStack
# ===============================================================
print "\nStack: ";
foreach (@solution) {
    print "$_ ";
}
print "\n";
print "<g fill=\"none\" stroke=\"#FF0000\" stroke-width=\"3\" stroke-linecap=\"round\" stroke-linejoin=\"round\">";
for ($i = 0; $i < scalar @solution; $i++) {
    $x = ((($corners[$solution[$i] - 1]{"right_top_x"} + $corners[$solution[$i] - 1]{"left_top_x"}) / 2) * 16);
    $y = ((($corners[$solution[$i] - 1]{"right_top_y"} + $corners[$solution[$i] - 1]{"left_top_y"}) / 2) * 16) + 8;
    if (($i + 1) < scalar @solution) {
        $x2 = ((($corners[$solution[$i + 1] - 1]{"right_top_x"} + $corners[$solution[$i + 1] - 1]{"left_top_x"}) / 2) * 16);
        $y2 = ((($corners[$solution[$i + 1] - 1]{"right_top_y"} + $corners[$solution[$i + 1] - 1]{"left_top_y"}) / 2) * 16) + 8;
    }
    print "<line x1=\"$x\" y1=\"$y\" x2=\"$x2\" y2=\"$y2\" />\n";
}
print "</g>\n";
#
# print "Found Solution!";
```

This will print out the lines that we will need to add to our svg files.

```svg
<g fill="none" stroke="#FF0000" stroke-width="3" stroke-linecap="round" stroke-linejoin="round"><line x1="88" y1="24" x2="88" y2="24" />
    <line x1="88" y1="24" x2="88" y2="40" />
    <line x1="88" y1="40" x2="72" y2="40" />
    <line x1="72" y1="40" x2="72" y2="56" />
    <line x1="72" y1="56" x2="72" y2="72" />
    <line x1="72" y1="72" x2="56" y2="72" />
    <line x1="56" y1="72" x2="40" y2="72" />
    <line x1="40" y1="72" x2="40" y2="56" />
    <line x1="40" y1="56" x2="24" y2="56" />
    <line x1="24" y1="56" x2="24" y2="40" />
    <line x1="24" y1="40" x2="24" y2="24" />
    <line x1="24" y1="24" x2="40" y2="24" />
    <line x1="40" y1="24" x2="40" y2="24" />
</g>
```

We just add these and we will get our solution. Have fun solving mazes!
