Overview

bin100 is a finite state machine that accepts a 12 character key.

Writeup

We take a look at main and see that the program takes a 12 character string as an argument, then calls FSM_Ctor on the first character in it. We suspect this allocates and initializes an object, so start identifying the important fields. The object returned by this fiction is used repeatedly in the main loop, consuming characters in the input.

We can see from these that each state is represented as a function that consumes a fsm_t object and a character of input, mutating the state machine and setting the next function. Furthermore, each state fails if the previous state was not correct.

We thus need to find a string that is (at least) 12 characters in length and will be accepted by the finite state machine. We go through each state and record the valid transitions, then write a program to do a depth first search for the longest valid path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/python

import fileinput
import re

edges = {}

for line in fileinput.input():
	source = line[0]
	dest = line[2]

	if not source in edges:
		edges[source] = [dest]
	else:
		edges[source].append(dest)

def maxPathFrom(node):
	if node not in edges:
		return node
	else:
		return node + max(map(maxPathFrom, edges[node]), key=len)

print maxPathFrom('M')
1
2
% python bin100.py <bin100.txt
MCA-173E6D84I