f=g+h - A* Pathfinding

f=g+h is an medium difficulty programming/misc challenge from YASCON 2020, in this blog we’ll be discussing the intended way to solve the challenge.

Introduction:

We’re given an archive with a word map and a text file with a maze in it. From the text file description and the challenge name, it’s clear that we have to implement A* pathfinding algorithm and find the fastest route to the element X.

Pathfinding is basically plotting the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra’s algorithm for finding the shortest path on a weighted graph. Here we’re going to use an extension of Dijkstra’s algorithm called A* because it achieves better performance by using heuristics to guide its search.

Dijkstra's Algorithm

A* Algorithm

A* Algorithm:

A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic and represents a minimum possible distance between that node and the end. This allows it to eliminate longer paths once an initial path is found.

One important aspect of A* is f = g + h. The f, g and h variables are in our Node class and get calculated every time we create a new node. Quickly I’ll go over what these variables mean.

• F is the total cost of the node.
• G is the distance between the current node and the start node.
• H is the heuristic — estimated distance from the current node to the end node.

We won’t be implementing A* ourselves, as it’s a waste of time to reinvent the wheel, so instead we’ll be using someone else’s code 😅
Here’s a python implementation of A* from scratch: gist. All thanks to ryancollingwood 🙌

Change the maze on line 137 with the maze given in the challenge file, Set the destination value to coordinates of the element ‘X’, in our case (7, 8). So the script starts finding the shortest path from (0,0) to (7,8).

After getting the coordinates, we need to use them on the image and map out its respective character. All we have to do is just figure out what character stands in the path coordinates to find the flag. You can do that in many ways or even manually. I have created a script to visualize it using Matplotlib and OpenCV, it basically creates a table from the image and plots the points using the coordinates.

#!/usr/bin/env python3
from imutils import contours
import cv2

# Load image, grayscale, Gaussian blur, Otsu's threshold
image = cv2.imread('map.png')
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
blur = cv2.GaussianBlur(gray, (5,5), 0)
thresh = cv2.threshold(blur, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)[1]

# Find contours and remove text inside cells
cnts = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
for c in cnts:
    area = cv2.contourArea(c)
    if area < 4000:
        cv2.drawContours(thresh, [c], -1, 0, -1)

# Invert image
invert = 255 - thresh
offset, old_cY, first = 10, 0, True
visualize = cv2.cvtColor(invert, cv2.COLOR_GRAY2BGR)

# Find contours, sort from top-to-bottom and then sum up column/rows
cnts = cv2.findContours(invert, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
(cnts, _) = contours.sort_contours(cnts, method="top-to-bottom")
for c in cnts:
    # Find centroid
    M = cv2.moments(c)

    cX = int(M["m10"] / M["m00"])
    cY = int(M["m01"] / M["m00"])

    # New row
    if (abs(cY) - abs(old_cY)) > offset:
        if first:
            row, table = [], []
            first = False
        old_cY = cY
        table.append(row)
        row = []

def Reverse(tuples): 
    new_tup = () 
    for k in reversed(tuples): 
        new_tup = new_tup + (k,) 
    return new_tup
	

# coordinates of the flag string
flag = [(0, 0), (0, 1), (0, 2), (0, 3), 
        (1, 3), (2, 3), (3, 3), (3, 4),
        (3, 5), (2, 5), (1, 5), (1, 6), 
        (0, 6), (0, 7), (0, 8), (0, 9), 
        (1, 9), (2, 9), (2, 8), (3, 8), 
        (4, 8), (5, 8), (6, 8), (7, 8)]

flag2 = []

for i in flag:
    flag2.append(Reverse(i))
    
# X(base=19, diff=39) : Y(base=20, diff=42)
for coordinates in flag2:
    if(int(coordinates[0]) == 0):
        cX = 19
    else:
        cX = 19 + (coordinates[0] * 39)

    if(int(coordinates[1]) == 0):
        cY = 20
    else:
        cY = 20 + (coordinates[1] * 41)
    
    print(cX, cY)

    cv2.circle(visualize, (cX, cY), 10, (36, 255, 12), -1) 
    cv2.imshow("pathfinding", visualize)
    cv2.waitKey(200)
    

print('Rows: {}'.format(len(table)))
print('Columns: {}'.format(len(table[1])))

cv2.waitKey()

And we get the string - AESKDCDOHKKLAOPOLGTMLOME
Since the flag is MD5Sum of the path string,

YASCON{45131ca9f5140debc67047351d21a403}

---

If you wanted to try it for yourself, here’s the challenge files: chall.zip ✌️