PINsmith — HackTheBox

Description

After gaining access to CygnusCorp's internal network, you've uncovered a critical system locked behind a numeric PIN. The catch? Only partial digits are visible, leaving you to piece together the rest. With your mission progressing, every second counts. You can't afford to waste time blindly guessing. Can you use the partial information at hand to orchestrate an educated brute force attack and break into the system before you're caught?

Rules

• Known digits are fixed and must appear in the indicated positions
• Unknown positions are represented by *
• Digits may repeat in the PIN, but not in adjacent positions
• Output the valid PINs in ascending lexicographical order

Analysis

The task is a classic combination generation problem with constraints:

1. Fixed positions: If a digit is specified in the template, it must remain in its place
2. Wildcard positions: The * symbol means we need to iterate through all possible digits 0-9
3. Adjacency constraint: Adjacent positions cannot contain the same digits

The service works via HTTP API:

• Endpoint: /run
• Method: POST
• Format: JSON with code and language fields

Solution

Using the backtracking algorithm:

def solve(template):
    n = len(template)
    results = []
    
    def backtrack(pos, current):
        if pos == n:
            results.append("".join(current))
            return
        
        if template[pos] != "*":
            # Fixed digit
            digit = template[pos]
            # Check that it doesn't match the previous one
            if pos == 0 or current[pos-1] != digit:
                current.append(digit)
                backtrack(pos + 1, current)
                current.pop()
        else:
            # Wildcard - iterate through all digits
            for d in "0123456789":
                # Check: doesn't match the previous one
                if pos == 0 or current[pos-1] != d:
                    # Look-ahead: if next position is fixed and equals d, skip
                    if pos + 1 < n and template[pos + 1] != "*" and template[pos + 1] == d:
                        continue
                    current.append(d)
                    backtrack(pos + 1, current)
                    current.pop()
    
    backtrack(0, [])
    return sorted(results)

template = input().strip()
result = solve(template)
for pin in result:
    print(pin)

Example

Input: *23

Algorithm:

1. Position 0: * - iterate 0-9, but skip 2 (next fixed position = 2)
2. Position 1: 2 - fixed
3. Position 2: 3 - fixed

Output:

023
123
323
423
523
623
723
823
923

Submitting the Solution

import requests

code = '''
def solve(template):
    n = len(template)
    results = []
    
    def backtrack(pos, current):
        if pos == n:
            results.append("".join(current))
            return
        
        if template[pos] != "*":
            digit = template[pos]
            if pos == 0 or current[pos-1] != digit:
                current.append(digit)
                backtrack(pos + 1, current)
                current.pop()
        else:
            for d in "0123456789":
                if pos == 0 or current[pos-1] != d:
                    if pos + 1 < n and template[pos + 1] != "*" and template[pos + 1] == d:
                        continue
                    current.append(d)
                    backtrack(pos + 1, current)
                    current.pop()
    
    backtrack(0, [])
    return sorted(results)

template = input().strip()
result = solve(template)
for pin in result:
    print(pin)
'''

response = requests.post(
    "http://83.136.251.11:56814/run",
    json={"code": code, "language": "python"}
)
print(response.text)

Key Indicators

Use this technique when:

• You need to generate all combinations with constraints
• There is a template with fixed and variable positions
• Certain combinations need to be excluded (e.g., adjacent duplicates)
• The result must be sorted

Algorithm Complexity

• Time: O(10^k * n), where k is the number of wildcards, n is the template length
• Space: O(n) for recursion stack + O(10^k * n) for storing results

Alternative Approaches

1. Itertools + filtering: Generate all combinations via itertools.product, then filter out invalid ones. Less efficient but simpler to implement.

2. Dynamic programming: Can count the number of valid PINs without generating them, if only statistics are needed.