Recognizing high-caliber programmers in a sea of applicants is a challenging task. A friend of mine described a simple test they give to their .Net job candidates as part of their selection process.
The test involved finding the first 3 consecutive digits of Pi that appear again in the numeric sequence. The goal of the test was to look for solutions that demonstrated creativity and accomplished the task with the least code possible. For the purpose of this test, Pi is supplied to a fixed number of decimal positions.
Typical solutions to this problem involve inner and outer loops or recursive function calls that examine the supplied value of Pi and look for the repeating sequence.
I proposed a much simpler solution that employs a regular expression feature known as “back references” and completes the task in just one line of code:
string repeating = Regex.Match("3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912", @"(?<repeating>[0-9][0-9][0-9])[0-9]*\1").Groups[1].Value;
In the above example, the value of Pi is supplied to 500 decimal places. This is important because the first 3 consecutive digits of Pi that repeat elsewhere in the sequence are 141 and the repetition does not begin until the 294th decimal place. (Note: The first 3 digits of Pi that repeat – eventually – are actually 314, but as there’s a decimal point between the 3 and the 1, we’re not treating this as consecutive).
I begin by constructing a .Net Regex Match statement (we only want the first match) and supplying the value of Pi provided as well as the following regular expression:
([0-9][0-9][0-9])[0-9]*\1
This expression:
- Defines a capturing group comprised of 3 digits
- Says this group will be followed by an unknown number of digits
- And this unknown number of digits will be followed by the 3 digits that appeared in the capturing group. \1 is a back reference to the value from the first capturing group.
Then I retrieve the value of the first capturing group and assign it to a string. The string will contain the answer (141).
It should be noted that the above solution is by no means the most efficient solution from a performance standpoint, but it does accomplish the task with the least code possible.
Regular expressions are a powerful tool but due to the complexity in constructing them, they are often overlooked in favor of more intuitive techniques.