Dance Dance Resolution

Written by

Dylan Holmes

StepMania_5.0.5_Demo.jpg

This is a picture of Stepmania, a free-software rhythm video game. You play by following along with footwork shown on-screen. It's good fun. Part of the intellectual fun is the presence of patterns—actually, there's room for a theory about what makes good choreography. Something about motifs that recur and resolve, load balancing the left and right feet, keeping within physiological limits, and creating interesting combinations out of a finite set of moves.

Where is this theory? There are some online tutorials on the mechanics of making choreography for these games—what software to use, for example. But I can't find anything on the craft of it—how to not just make a song, but make a satisfying song.

This article is a small step in that direction. I present a theory about how players choose which foot to step on which arrow. I argue that the choice of foot varies based on how you've positioned your body up to that point, and where you'll need to move next. The theory consists of three constraints that I developed by observing what I naturally do during play. I believe they accurately and completely capture how I decide what foot to use, although I suspect other more advanced players may be less constrained.

The constraints are simple, but powerful. They capture one piece of what it means to be a good song. Whenever they're violated, the result is awkward choreography. So if you're a choreography designer, you can use these constraints as a rubric. That is the key contribution of this work: clearly articulated rules that, when followed, produce more elegant dance patterns.

I'll explain the three principles, then show an implementation in Python that can read choreography from a stepmania .sm file and assign footwork to it. It produces footwork by resolving the three constraints.

1 Three constraints

The three contraints are:1

The home principle
Step on L with the left foot and R with the right foot.
The alternation principle
As a rule, you should alternate stepping with the left and right foot. You may, however, step on the same arrow repeatedly with the same foot; see below.
The min-spin principle
When the same foot must step twice consecutively, it is especially good to keep it on the same arrow and especially bad to make it leap to the arrow on the opposite side (e.g. U to D).

Here are some follow-up remarks:

  1. Note that the home principle incidentally constrains you to always orient toward the screen.
  2. While the home principle establishes the footwork for L and R, the alternation principle helps disambiguate the footwork for U and D. For example, if you have the sequence L-U, you step it as Lʟ-Uʀ.
  3. Together, these two rules explain why stepping a pattern like L-U-R feels so awkward: you must violate either the home principle or the alternation principle. This is the smallest possible awkward step sequence; uncovering it is one special achievement of the theory.
  4. Sometimes, large sections of a song can remain technically ambiguous: if your song begins U, D, U, D, U, D, U, D, L, then the Us and Ds remain ambiguous until you finally see the L. Note that this also implies that future arrows can influence choreography earlier in the song. (The constraints are about neighboring notes, independent of temporal order.) Hence repeated practice trials are sometimes necessary in order to obtain optimal constraint-satisfying footwork.
  5. There are six double-arrow combinations: UL UR UD LR DL DR. Note that the home principle completely determines footwork for all of these except UD. The min-spin principle helps disambiguate footwork for the UD case.
  6. For example, if you have to step DR-UD, the footing on DR is DʟRʀ by the home principle. The footing on UD is initially ambiguous on its own: UʟDʀ or UʀDʟ? But the min-spin principle says DʟRʀ-UʟDʀ would be bad because the left foot would go from D to U in a single step. So the correct transition is DʟRʀ-DʟUʀ, which satisfies all the constraints.
  7. You can prove to yourself that if UD follows one of the other six double-arrow combinations, its footwork is often completely determined:
    • LR-UD (ambiguous)
    • LU-UD (left foot on D)
    • LD-UD (left foot on U)
    • UR-UD (left foot on U)
    • UD-UD (ambiguous)

    • DR-UD (left foot on D)

      UD remains ambiguous in only two cases (preceded by LR or UD). In the rest, the footwork is completely determined by the home and min-spin principles.

  8. When footings remain ambiguous, they're equally easy to do either way. For example LR-UD-LR can do footing for UD any which way. This is consistent with my experience.
  9. As predicted by the theory, LD-UD-DR is an awkward double-step transition. One way to look at it is that UD has conflicting footing cues from each side: Based on LʟDʀ-UD-DR, it should be left foot on U. Based on LD-UD-DʟRʀ, it should be left foot on down. Another way of looking at it is the progression forces an awkward move: LʟDʀ-UD-DR forces LʟDʀ-UʟDʀ-DR, which when you continue to DR, requires either a violation of the home principle (*left on R) or violation of the min-spin principle (*left goes from U to D in a single step)
  10. Technical aside: In terms of automata theory, the footing constraints form a regular language; you can assign footing using a finite state machine.2

2 Python code

The code consists of utilities for (1) extracting note data out of stepmania .sm song files, and (2) assigning footing to the notes by applying our three principles. Note extraction involves some careful parsing, but the program for assigning footwork is pretty straightforward:

There are three constraint checkers, corresponding to the three enumerated principles. Each one has the same form: it takes in a beat of the song as well as the most recent beat that came before it. Here, a beat is an arrow or arrow pair, along with a footing assignment. The constraint checker returns True if the assignment follows the rule, or False if it violates it. 

# Throughout, feet is a dictionary assigning a single arrow or arrow
# pair to footing, e.g. {"U" : "L", "R" : "R"}

def enforce_home_principle(feet, _) :
    if feet.get("L") == "R" or feet.get("R") == "L" :
        return False
    return True

def enforce_alternation_principle(feet, feet_prev) :
    if feet_prev is None :
        return True
    if len(feet) > 1 or len(feet_prev) > 1 :
        return True # Double steps reset the alternation counter

    # Strong version:
    # If the arrows are the same, the footing must be the same.
    # If the arrows are different, the footing must be different.
    return (list(feet.values()) == list(feet_prev.values())) == (list(feet.keys()) == list(feet_prev.keys()))

def enforce_minspin_principle(feet, feet_prev) :
    if feet_prev is None :
        return True
    pairs = [(feet.get("L"), feet_prev.get("L")),
             (feet.get("R"), feet_prev.get("R"))]

    # Neither foot may go immediately between U and D.
    if ("U","D") in pairs or ("D", "U") in pairs :
        return False
    return True

There is also code for iterating over all of the beats in the song, passing pairs of consecutive notes to a constraint checker, and returning the valid assignments. I run the iterator once for each individual constraint, and then again in the reverse direction (since the constraint checker is direction-specific, but the principle is not). 

# Here, domain_steps is an ordered list of arrows or arrow-pairs in a
# song; the arrows are paired with a list of all possible footing
# assignments.  The iterate function applies a constraint checker to
# consecutive arrow pairs, eliminating any incompatible footing
# assignments.

def iterate(domain_steps, constraint_fn) :
        labeled_steps = [(index, step, domain) for (index, (step, domain)) in zip(range(len(domain_steps)), domain_steps)]

        prev_feet = None
        for (index, step, domain) in labeled_steps :
            if len(step.arrows()) == 0 :
                continue

            new_domain = list(filter(lambda x: constraint_fn(x, prev_feet), domain))
            if not new_domain :
                print("! Unsatisfiable constriant at "+str((index,domain))+" "+str(prev_feet), constraint_fn.__name__)
            elif len(new_domain) == 1 :
                prev_feet = new_domain[0]        
                labeled_steps[index] = (index, step, new_domain)
            else :
                prev_feet = None
        return [(step, domain) for (_, step, domain) in labeled_steps]

2.1 COMPLETE CODE FILE

# 2020/05/24
# PROGRAM FOR READING AND ANALYZING STEPMANIA STEPFILES
# (C)2020 Dylan Holmes. Licensed under GPL v3.

import re
from functools import reduce
from itertools import permutations

rt re
from functools import reduce
from itertools import permutations

path_example = "/opt/stepmania/Songs/Valex's Magical 4-Arrow Adventure 9/Bass Bomb/Bass Bomb.sm"

ARROW_CHAR = {"L" : "l",
              "D" : "d",
              "U" : "u",
              "R" : "r"}

MINIMUM_MATCH_SIZE = 4

# ------- BASIC UTILITIES
def gcd(a,b) :
    if a < b :
        (a,b) = (b,a)
    r = a % b
    if r == 0 :
        return b
    return gcd(a, r)

def lcm(a,b=0) :
    if b == 0 :
        return a
    return int(a*b / gcd(a,b))


PERM4 = list(permutations(range(4)))

def permute(indexes, coll) :
    return [coll[i] for i in indexes]

# ------- STEPFILE PARSING FUNCTIONS

class Beat :
    def __init__(self, quarto, subdivs = None) :
        self.subdivs = subdivs
        self.quarto = quarto

    def __repr__(self) :
        A = self.quarto+'-'+str(self.subdivs)
        B = ''.join([ARROW_CHAR[direction] if activity != '0' else '' for (direction, activity) in zip("LDUR", self.quarto)]) or '_'
        return B
        return self.quarto
        return A+"\t"+B

    def is_stasis(self) :
        return self.quarto == "0000"

    def simultaneous(self) : 
        return len([x for x in list(self.quarto) if x != '0'])
    # A+"\t"+B

    def left(self) :
        return int(self.quarto[0])
    def down(self) :
        return int(self.quarto[1])
    def up(self) :
        return int(self.quarto[2])
    def right(self) :
        return int(self.quarto[3])

    def arrows(self, query=None) :
        letters = "".join([x*int(self.quarto[i] != '0') for (x,i) in zip(list("LDUR"), range(4))])
        if query is None :
            return letters
        else :
            return all([x in letters for x in query])


def stepfile_parse_notes(text) :
    segments = re.split(r":\n*\s*", text)
    notes = segments[-1].split("\n")

    challenge_level = segments[2]
    debug = print if challenge_level == 'Easy' else lambda x:None
 #   debug(challenge_level)


    beats = []

    current_measure = []
    while notes :
        line = notes.pop(0)
        line = re.sub(r"\/\/.*", "", line)
        if not line :
            continue
        if re.search(r"[,;]", line) :
            # END OF MEASURE
            subdivs = len(current_measure)
            for b in current_measure:
                b.subdivs = subdivs
            beats += current_measure
            current_measure = []
        else :
            current_measure += [Beat(line)] 
    segments[-1] = beats
    return dict(zip(('chart-type', 'author', 'difficulty', 'meter','radar','notes'), segments))
def stepfile_read(path) :
    with open(path) as f:
        read_data = f.read()
        # print(read_data)
    match = re.findall(r"#([A-Z]+):([^;]*);", read_data, re.DOTALL)


    song_dict = {}
    for m in match :
        (key, val) = m
        if key != "NOTES" :
            song_dict[key] = val
        else :
            song_dict["NOTES"] = song_dict.get("NOTES", []) + [stepfile_parse_notes(val)]



    return song_dict

def stepfile_print_beats(beats) :
    measure_lengths = set([beat.subdivs for beat in beats])
    print(measure_lengths)
    common_measure = reduce(lcm, measure_lengths)

    count = 1
    beat_index = 0
    for b in beats :
        print(b, "\t\t", beat_index, "\n" * (common_measure // b.subdivs - 1))
        # print(b, "\t\t",count, "\n" * (common_measure // b.subdivs - 1))
        count += common_measure // b.subdivs
        beat_index += 1
    pass



def align_beat(beat1, beat2, permset=None) :
    if beat1.subdivs != beat2.subdivs :
        # beats must have the same length
        return None
    if sorted(beat1.quarto) != sorted(beat2.quarto) :
        # beats must have the same activity signature
        # (number of notes, and how those notes are played)
        return None

    if permset is None :
        permset = PERM4

    # print([x for x in x.quarto], [y.quarto[i] for i in  PERM4[0]] )

    return [abcd for abcd in permset
            if permute((0,1,2,3), beat1.quarto) == permute(abcd, beat2.quarto)]

def interestingness(match) :
    # (root_index, subject_index, match_length, patterns, beats)

    match_length = match[2]

    note_rhythms= [x.subdivs for x in match[4]]
    note_types = set(note_rhythms)
    note_variety = sum([1 if a == b else 0 for (a,b) in zip(note_rhythms,
                                                        note_rhythms[1:])])
    return -len(note_types), -match[2]
    # return note_variety, -match[2]

def align_beat_multiple(beats) :
    """Find patterns of similar rhythms in the song"""

    closed_matches = []
    # format: [root_index, final_index, match_length, match_example?]

    for root_index in range(len(beats)) : 
        if beats[root_index].is_stasis() :
            # I've decided to ignore matches that start with 'rest'
            # notes.
            continue

        matching_indexes = [idx for idx in range(root_index+1,len(beats))
                                if align_beat(beats[root_index], beats[idx])]
        matches = [(idx, align_beat(beats[root_index], beats[idx]), [beats[idx]]) for idx in matching_indexes]


        match_length = 1

        while matches :
            match_length += 1
            extended_matches = []
            for (i, ptns, bs) in matches :
                if i + match_length - 1 < len(beats) :
                    # no out of bounds error
                    ptns_new = align_beat(beats[root_index + match_length - 1],
                                          beats[i + match_length - 1],
                                          ptns)
                    if ptns_new :
                        # next beat also matches
                        extended_matches += [(i, ptns_new, bs + [beats[i+match_length-1]])]
                        continue

                # THE MATCH HAS OVERREACHED; ADD IT TO THE CLOSED LIST.
                match = (root_index, i, match_length-1, ptns, bs)

                # --- check for "transitive duplicates" before adding

                # match1 : its subject index is our root index.
                # match2 : its subject index is our subject index.
                # both matches have the same root index.  both matches
                # have the same length, and the same length as our
                # match.

                def has_duplicate(closed_matches, match) :

                    # check for subset duplicates
                    for m in closed_matches :
                        diff = m[2] - match[2] # difference in match lengths
                        if diff <= 0 :
                            continue
                        if m[0] + diff == match[0] and m[1] + diff == match[1] :
                            return True
                    # check for transitive duplicates
                    potential_duplicates = [m for m in closed_matches if m[2] == match[2]]
                    for m1 in potential_duplicates :
                        if m1[1] != match[0] :
                            continue
                        for m2 in potential_duplicates :
                            if m2[1] != match[1] or m1[0] != m2[0] :
                                continue
                            return True
                    return False

                #if has_duplicate(closed_matches, match) :
                #    pass
                # print(True)
                if match_length -1 >= MINIMUM_MATCH_SIZE and not has_duplicate(closed_matches, match) : 
                    closed_matches += [match]
            matches = extended_matches


    closed_matches = sorted(closed_matches, key=interestingness)

    freq_count = {}
    for (from_index, to_index, match_length, ptns, bs) in closed_matches :
        freq_count[(from_index, match_length)] = freq_count.get((from_index, match_length), 0) + 1

    closed_matches = sorted(closed_matches,
                            key=lambda x : freq_count.get((x[0],x[2]),0), reverse=True )    

    return closed_matches, freq_count
    # return closed_matches
    # print(beats[root_index])


def chunked_beats(steps) :
    alignments, freqs = align_beat_multiple(steps)
    index = 0
    letters = list("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")

    named_patterns = {}

    labeled_steps = list(map(list,zip(steps, [None]*len(steps), range(len(steps)))))
    while 1 :
        # Find next step that isn't part of a pattern yet
        index = None
        for (x, label, i) in labeled_steps :
            if label is None :
                index = i
                break
        if index is None :
            break

        # Pick which pattern it's supposed to be
        match = None 
        for m in alignments :
            if m[0] == index :
                # all terms in sequence are unlabeled
                if all([x[1] is None for x in labeled_steps[m[0]:m[0]+m[2]]]) :
                    match = m
                    break
        if match is None :
            # This note is not part of any pattern
            labeled_steps[index][1] = labeled_steps[index][0]
 #           print(index, "none match")
            continue

        # Give this pattern a unique identifier
        signature = (match[0], match[2])
        named_patterns[signature] = named_patterns.get(signature) or letters.pop(0)
        symbol = named_patterns[signature]
        signature = (match[0], symbol, match[2:])


        # Find all other instances of this pattern
        all_matches = []
        for m in alignments :
            if m[0] == match[0] and m[2] == match[2] :
                # same from_index and match_length

                # all terms in sequence are unlabeled
                if all([x[1] is None for x in labeled_steps[m[1]:m[1]+m[2]]]) :
                    all_matches += [m]

        indexes = [match[0]] + [m[1] for m in all_matches]

        # greedy principle to ensure that labeling will not clobber
        # itself
        kept_indexes = []
        while indexes :
            i = indexes.pop(0)
            kept_indexes += [i]
            indexes = list(filter(lambda j: not (i <= j < i+match[2]), indexes))
        indexes = kept_indexes

        # label the match throughout each range
        for offset in range(match[2]) :
            for index in indexes :
                # if labeled_steps[index + offset][1] :
                #     print(symbol, indexes, match[2], labeled_steps[index + offset])
                #     raise Exception
                labeled_steps[index + offset][1] = symbol, index, match[4]


    for x in labeled_steps :
        print(x)
    # map(print,labeled_steps)
    print(sorted(freqs.items(), key=lambda x: -x[1]))



def assign_footwork_new(steps) :
    domain_steps = []
    for step in steps:
        arrows = step.arrows()
        if not arrows :
            domain_steps += [(step, [{}])]
        elif len(arrows) == 1 :
            domain_steps += [(step, [{"L" : arrows[0]},
                                     {"R" : arrows[0]}])]
        else :
            domain_steps += [(step, [{"L" : arrows[0],
                                      "R" : arrows[1]},
                                     {"R" : arrows[0],
                                      "L" : arrows[1]}])]

    strict_repetition_mode = True # for alternation

    def enforce_home_principle(feet, _) :
        if feet.get("L") == "R" or feet.get("R") == "L" :
            return False
        return True

    def enforce_alternation_principle(feet, feet_prev) :
        if feet_prev is None :
            return True
        if len(feet) > 1 or len(feet_prev) > 1 :
            return True # I guess double steps reset the alternation counter


        if strict_repetition_mode :
            # must step with new foot on new arrow AND
            # must step with same foot on same arrow

            return (list(feet.values()) == list(feet_prev.values())) == (list(feet.keys()) == list(feet_prev.keys()))
        else :
            # every time you step on a new arrow, you must use a new foot.
            # if it's the same arrow, you can use any foot
            return (list(feet.values()) == list(feet_prev.values())) or (list(feet.keys()) != list(feet_prev.keys()))

    def enforce_minspin_principle(feet, feet_prev) :
        if feet_prev is None :
            return True
        pairs = [(feet.get("L"), feet_prev.get("L")),
                 (feet.get("R"), feet_prev.get("R"))]

        if ("U","D") in pairs or ("D", "U") in pairs :
            return False
        return True



    def iterate(domain_steps, constraint_fn) :
        labeled_steps = [(index, step, domain) for (index, (step, domain)) in zip(range(len(domain_steps)), domain_steps)]


        prev_feet = None
        for (index, step, domain) in labeled_steps :
            if len(step.arrows()) == 0 :
                continue

            new_domain = list(filter(lambda x: constraint_fn(x, prev_feet), domain))
            if not new_domain :
                print("! Unsatisfiable constriant at "+str((index,domain))+" "+str(prev_feet), constraint_fn.__name__)
            elif len(new_domain) == 1 :
                prev_feet = new_domain[0]        
                labeled_steps[index] = (index, step, new_domain)
            else :
                prev_feet = None
        return [(step, domain) for (_, step, domain) in labeled_steps]


    domain_steps = iterate(domain_steps, enforce_home_principle)
    domain_steps = iterate(domain_steps, enforce_alternation_principle)
    domain_steps = iterate(domain_steps, enforce_minspin_principle)

    domain_steps = iterate(domain_steps[::-1], enforce_home_principle)[::-1]
    domain_steps = iterate(domain_steps[::-1], enforce_alternation_principle)[::-1]
    domain_steps = iterate(domain_steps[::-1], enforce_minspin_principle)[::-1]



    for (step, domain) in domain_steps :
        if len(domain) == 1 :
            print (step, domain[0])
        else :
            print (step, "\t", domain)

    print(domain_steps)
    return domain_steps

def assign_footwork(steps) :

    labeled_steps = [(step, None) for step in steps]
    print("footwork")

    debug = lambda s: print("! "+s)


    def complete_other_foot(arrows, label) :
        """If only one foot has been assigned a label, assign the other foot accordingly and return the label."""
        if len(arrows) < 2 or len(label) == 2 :
            return label
        for (side,other) in [("L","R"), ("R","L")] :
            if label.get(side) :
                other_label = [x for x in arrows if x != label.get(side)][0]
                label[other] = other_label
        return label

    def principle_home(labeled_steps) :
        labeled_steps = [(i, step, label) for (i, (step,label)) in zip(range(len(steps)), labeled_steps)]

        # THE HOME PRINCIPLE
        for (i, s, label) in labeled_steps :
            if label is not None :
                # constraint checking for assigned feet
                if label.get("L") == "R" or label.get("R") == "L" :
                    debug("Home principle violation", (i,s,label))
                continue

            feet = {}  # {L : ?, R : ?}

            if s.left() :
                feet["L"] = "L"
            if s.right() :
                feet["R"] = "R"

            feet = complete_other_foot(s.arrows(), feet)
            # if 0 < len(feet) < s.simultaneous() == 2 :
            #     current_foot = list(feet)[0]
            #     other_foot = "R" if current_foot == "L" else "L"

            #     feet[other_foot] = "D" if s.down() else "U" 

            if feet :
                labeled_steps[i] = (i, s, feet)
        return [(s, feet) for (i,s,feet) in labeled_steps]

    def principle_alternation(labeled_steps) :
        # THE ALTERNATION PRINCIPLE
        labeled_steps = [(i, step, label) for (i, (step,label)) in zip(range(len(steps)), labeled_steps)]


        most_recent_step = None
        for (i, s, label) in labeled_steps :
            if s.is_stasis() :
                labeled_steps[i] = (i, s, {})
                continue # ignore "rests"
            if label is not None :
                # question: how does alternation principle apply to
                # double-steps?  does the doublestep reset the alternation
                # counter? ignore it? increment it?

                # TODO: constraint checking for assigned feet

                if len(label) > 1 :
                    most_recent_step = None # resets the counter
                else :
                    most_recent_step = (s,label)
                continue

            if most_recent_step and s.simultaneous() == 1 : # everything but UD

                (prev_step, prev_feet) = most_recent_step 

                # Heavyhanded: /require/ repeated steps to have same foot 
                if prev_step.quarto == s.quarto :
                    # debug # prev_feet["samequarto"] = True
                    labeled_steps[i] = (i, s, prev_feet)
                    continue
                else :
                    current_foot = list(prev_feet)[0]
                    other_foot = "R" if current_foot == "L" else "L"

                    feet = {}
                    feet[other_foot] = "D" if s.down() else "U" 
                    labeled_steps[i] = (i, s, feet)
                    most_recent_step = (s, feet)
        return [(s, feet) for (i,s,feet) in labeled_steps]


    def principle_minspin(labeled_steps) :
        # THE MIN-SPIN PRINCIPLE

        labeled_steps = [(i, step, label) for (i, (step,label)) in zip(range(len(steps)), labeled_steps)]


        most_recent_step = None
        for (i, s, label) in labeled_steps :

            print(">", (i,s.quarto,label))
            if s.is_stasis() :
                continue # ignore "rests"
            if label is not None :
                # TODO: constraint checking for assigned feet
                most_recent_step = (s,label)
                continue


            (prev_step, prev_label) = most_recent_step

            print(i, most_recent_step, s.arrows())
            label = {}

            for (foot, arrow) in prev_label.items() :
                if arrow in s.arrows() :
                    label[foot] = arrow
                    label = complete_other_foot(s.arrows(), label)
                    labeled_steps[i]  = (i, s, label)

        return [(s, feet) for (i,s,feet) in labeled_steps]


    labeled_steps = principle_home(labeled_steps)
    labeled_steps = principle_alternation(labeled_steps)
  #  labeled_steps = principle_alternation(labeled_steps[::-1])[::-1]
    labeled_steps = principle_minspin(labeled_steps)

    # principle_alternation(labeled_steps)


    labeled_steps = [(i, s, label) for (i, (s,label)) in zip(range(len(labeled_steps)), labeled_steps)]
    for x in labeled_steps:
        print("X", x[0], x[1], x[2])





# ------------- SANDBOX    
steps = stepfile_read(path_example)

target_difficulty = 'Easy'
print (target_difficulty)

# GET THE EASY SONG IF ANY
steps = filter(lambda x: x.get('difficulty') == target_difficulty, steps.get("NOTES"))
steps = list(steps)[0]['notes']
steps = assign_footwork_new(steps)

Footnotes:

1
Notation: I use single-letter abbreviations for the {L}eft, {D}own, {U}p, and {R}ight arrows. And I indicate footwork with superscripts, so for example stepping on the Up arrow with your right foot is Uʀ.
2
Specifically, the alphabet symbols are the ten arrow types (L, UR, etc.) and the states are all thirteen legal footing assignments for each arrow type (UʟDʀ, UʀDʟ, etc.). A nondeterministic finite state machine enforces the constraints by allowing transitions like \[\mathrm{L^LU^R}\xrightarrow{ud}\mathrm{U^RD^L}\] and forbidding transitions like \[\mathrm{L^LU^R}\xrightarrow{ud}\mathrm{U^LD^R}.\]If the automaton accepts a sequence of arrows, then it's a valid nonawkward choreography, and the suitable footing assignment is given by the sequence of states leading to acceptance. (There may be multiple sequences if the parse is ambiguous.)

Date: 2020/May/25

Author: Dylan Holmes

Created: 2020-05-25 Mon 21:20

Validate