Category: Swift Coding Test

1. Introduction

Breadth-First Search (BFS) is an algorithm for traversing nodes in a graph or tree structure.
BFS explores adjacent nodes first from the starting node, then examines the adjacent nodes of those nodes,
visiting all levels of nodes in order. This method is useful for finding the shortest path since it explores
the graph or tree level by level and can be applied to many problems.

2. Problem Description

        4 4
        0 0 1 0
        0 1 0 0
        2 0 1 0
        0 0 3 0
        

        7
        

3. Problem Analysis

BFS can be used to solve this problem.
BFS is suitable for finding the shortest path, starting from the starting point (2) in the given grid and
exploring the path to the destination (3) by moving to adjacent walkable areas (0).
Possible directions for movement are limited to four: up, down, left, and right.

One of the features of BFS is that it adds each node to the queue, allowing it to search in level order.
This makes it easy to count the number of moves needed to reach a specific node.
This method can be used to explore all 0s and 3s filled in the grid to check whether the destination can be reached.

4. Algorithm Design

1. **Initialize the grid and objects**: Initialize the queue for breadth-first search and a visited array based on the input grid.
2. **Add the starting point to the queue**: Add the starting point to the queue and update the visited array.
3. **Execute BFS**: For each node removed from the queue, check its four neighbors.
If the neighbor is walkable, add it to the queue and mark it as visited.
4. **Check for reaching the destination**: If the destination is reached, output the number of moves at that point.
5. **Handle cases where destination is unreachable**: If the queue is empty but the destination has not been reached, output -1.

5. Code Implementation

Now, we will implement BFS in Swift based on the above algorithm design.

import Foundation

func findShortestPath(grid: [[Int]], start: (Int, Int), end: (Int, Int)) -> Int {
    let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    var queue: [(Int, Int, Int)] = [(start.0, start.1, 0)] // (x, y, distance)
    var visited = grid
    visited[start.0][start.1] = 1 // Mark as visited

    while !queue.isEmpty {
        let (x, y, distance) = queue.removeFirst()
        
        // If reached the destination
        if (x, y) == end {
            return distance
        }

        // Explore neighboring nodes
        for direction in directions {
            let newX = x + direction.0
            let newY = y + direction.1
            
            // If within valid range and walkable
            if newX >= 0, newY >= 0, newX < grid.count, newY < grid[0].count, visited[newX][newY] == 0 {
                queue.append((newX, newY, distance + 1))
                visited[newX][newY] = 1 // Mark as visited
            }
        }
    }
    
    // If destination is not reached
    return -1
}

// Example input
let grid: [[Int]] = [
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [2, 0, 1, 0],
    [0, 0, 3, 0]
]

if let start = grid.enumerated().flatMap({ $0.element.enumerated().compactMap { $1 == 2 ? ($0.offset, $0.element) : nil } }).first,
   let end = grid.enumerated().flatMap({ $0.element.enumerated().compactMap { $1 == 3 ? ($0.offset, $0.element) : nil } }).first {
    let result = findShortestPath(grid: grid, start: start, end: end)
    print(result) // Output the minimum number of moves
}

6. Code Explanation

The code above finds the starting point and destination in the given grid and then
performs breadth-first search to find the shortest path.

• The four directions for exploration are defined as up, down, left, and right.
• A visited array is used to ensure that
  already visited nodes are not added to the queue again.
• When the destination is reached, the current distance is returned.
• If the destination cannot be reached, it returns -1.

7. Conclusion

Breadth-First Search (BFS) is a highly useful algorithm for solving shortest path problems.
It works efficiently in structures like 2D grids and frequently appears in various programming challenges.
It is important to practice different types of BFS problems to enhance understanding of the algorithm and problem-solving skills.
Through this tutorial, we hope you have gained a fundamental understanding of BFS and learned how to solve actual problems.

8. Additional Practice Problems

Try your hand at the following variant problems:

• Reach the destination while avoiding obstacles (1) using only a specific path in the given grid.
• Finding the shortest paths between multiple starting and ending points.
• Finding the shortest path when diagonal movements are also allowed, instead of only grid movements.

Tackling these problems will further enhance your understanding of the breadth-first search algorithm and improve your problem-solving abilities.

In this article, we will explore how to solve a specific problem using Swift. The topic is Sorting Digits in Descending Order. This problem allows us to practice string manipulation, sorting algorithms, and handling data types in Swift.

Problem Description

Given an array of integers, write a function that converts each integer to a string, sorts the strings in descending order by their digits, and returns the result. For example, if the array is [321, 123, 456], it should convert each integer to a string resulting in ["321", "123", "456"] and sort it in descending order, returning ["321", "456", "123"].

Problem Examples

• Input: [321, 123, 456] → Output: ["321", "456", "123"]
• Input: [12, 345, 7, 89] → Output: ["89", "7", "345", "12"]
• Input: [10, 2, 1] → Output: ["2", "10", "1"]

Problem Approach

The process to solve this problem can be divided into the following steps:

1. Convert the integers to strings.
2. Sort the strings in descending order by their digits.
3. Return the sorted result.

Step 1: Convert Integer Array to String Array

To convert an integer to a string, you can use Swift’s String() initializer. This allows you to convert all integers in the array to strings. This conversion can be easily performed using the map() function.

Step 2: Sort Strings in Descending Order

When sorting strings, you need to provide a custom sorting logic using the sorted(by:) method. Here, you can compare the lengths of the strings, or in case of equal lengths, compare them lexicographically.

Step 3: Return the Sorted Result

After sorting, you simply return the resulting array of strings. The final implementation will look like this.

Swift Code Implementation

func sortDigitsDescending(_ numbers: [Int]) -> [String] {
        // Step 1: Convert integers to strings
        let stringNumbers = numbers.map { String($0) }
        
        // Step 2: Sort strings in descending order (by digits)
        let sortedNumbers = stringNumbers.sorted { 
            (lhs, rhs) in
            if lhs.count != rhs.count {
                return lhs.count > rhs.count // Compare number of digits
            } else {
                return lhs > rhs // Compare values if lengths are equal
            }
        }
        
        // Step 3: Return the sorted result
        return sortedNumbers
    }

Code Explanation

The Swift function above works as follows:

• numbers.map { String($0) }: Converts each element of the given integer array to a string.
• sorted { ... }: Applies custom sorting logic to sort in descending order. It first compares the number of digits, and if they are the same, it compares the string values.
• Returns the sorted array of strings as the result.

Test Cases

You can run a few test cases to check if the function works correctly. Below are some example test codes using the function.

let testCase1 = [321, 123, 456]
let result1 = sortDigitsDescending(testCase1)
print(result1) // ["321", "456", "123"]

let testCase2 = [12, 345, 7, 89]
let result2 = sortDigitsDescending(testCase2)
print(result2) // ["89", "7", "345", "12"]

let testCase3 = [10, 2, 1]
let result3 = sortDigitsDescending(testCase3)
print(result3) // ["2", "10", "1"]

Conclusion

In this article, we covered the problem of converting integers to strings and sorting them in descending order by digits using Swift. This was a useful exercise to enhance understanding of string manipulation and sorting algorithms. Problems like this frequently appear in coding tests and can be beneficial in real-world applications.

The coding implementation process allows you to utilize various features of Swift and aims to help improve problem-solving skills. In the next course, we will tackle even more interesting problems!