Skip to content

Instantly share code, notes, and snippets.

@talyian

talyian/cracklepop.js

Last active Jan 31, 2020
Embed
What would you like to do?
CracklePop in regex
// CracklePop
// Problem: Write a program that prints out the numbers 1 to 100 (inclusive).
// If the number is divisible by 3, print Crackle instead of the number.
// If it's divisible by 5, print Pop.
// If it's divisible by both 3 and 5, print CracklePop.
// Solution: regex is not only perfectly capable of lexing HTML,
// it is also perfectly capable of expressing, in a roundabout way,
// a finite automaton that verifies divisibility by a given number.
var numbers = Array(100).fill(0).map((x, i) => i + 1).join(' ')
console.log(numbers
.replace(/\b((?:[0369]|[147][0369]*[258]|(?:[147][0369]*[147]|[258])(?:[258][0369]*[147]|[0369])*(?:[258][0369]*[258]|[147]))+0|(?:[0369]*[147]|[0369]*[258](?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147]))(?:[0369]|[258][0369]*[147]|(?:[147]|[258][0369]*[258])(?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147]))*5)\b/g, "cracklepop")
.replace(/\b\d*[05]\b/g, "pop")
.replace(/\b(?:[0369]|[147][0369]*[258]|(?:[147][0369]*[147]|[258])(?:[258][0369]*[147]|[0369])*(?:[258][0369]*[258]|[147]))+\b/g, "crackle"))
# CracklePop
# Problem: Write a program that prints out the numbers 1 to 100 (inclusive).
# If the number is divisible by 3, print Crackle instead of the number.
# If it's divisible by 5, print Pop.
# If it's divisible by both 3 and 5, print CracklePop.
# Solution: regex is not only perfectly capable of lexing HTML,
# it is also perfectly capable of expressing, in a roundabout way,
# a finite automaton that verifies divisibility by a given number.
import re
crackle_pop_regex = r"""
# The automaton for "multiple-of-15" makes heavy use of the automaton for "multiple-of-3"
# make sure you follow that before attempting to figure this group out.
\b(?P<fifteen>
# multiples of 15 can be "3 * n with a trailing 0"
(?:[0369]|[147][0369]*[258]|(?:[147][0369]*[147]|[258])(?:[258][0369]*[147]|[0369])*(?:[258][0369]*[258]|[147]))+ 0 |
# multiples of 15 can also be "(3 * n + 1) with a trailing 5
# to construct the regex for "3 * n + 1" we have to collapse the automaton to state 2, but starting from state 0
# move from [0] to [2]
(?:[0369]*[147]|[0369]*[258](?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147]))
# loop from [2] to [2]
(?:[0369]|[258][0369]*[147]|(?:[147]|[258][0369]*[258])(?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147]))*
5)\b |
# nice, "multiple-of-5" is an easy regex
(?P<five>\b\d*[05]\b) |
# you can calculate "multiple-of-3" by building a 3-state automaton and tracking the transitions between each state.
# converting from the automaton back into regex form gives the following.
(?P<three>\b(?:[0369]|[147][0369]*[258]|(?:[147][0369]*[147]|[258])(?:[258][0369]*[147]|[0369])*(?:[258][0369]*[258]|[147]))+\b)
"""
print(re.sub(
crackle_pop_regex,
lambda m: "cracklepop" if m.group("fifteen") else "crackle" if m.group("three") else "pop" if m.group("five") else '?',
' '.join(str(i) for i in range(1, 101)),
flags=re.X))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.