Old arcade games had limited inputs: a joystick (Up, Down, Left, Right) and two

Question

Old arcade games had limited inputs: a joystick (Up, Down, Left, Right) and two buttons (B1 and B2). Some games also had cheat codes, which we will assume are a sequence of 20 inputs that can unlock an advantage for a player. For example, it might be the case that entering UUDD1UUDD2UUDD1UUDD2 gives the player an extra life. You have access to a large string (more than 100000 characters) describing the inputs of an experienced player who you assume knows and frequently uses the cheat codes. You would like to use this string to identify candidate sequences of inputs that could be cheat codes (the sequences of 20 inputs that occur most frequently). a) Describe an algorithm that achieves this task. b) Explain why your algorithm is correct. c) Give the worst case and expected case complexity of your algorithm.

Explanation / Answer

1. Algorithm :

Input : 100000 characters

Since the characters have to appear in sequence - The ascii value of the 20 cheat code characters is being calculated (for '1' and '2' it is calculated as 1 and 2 itself) and ascii value of subset of 100000 characters i.e. first 20 characters and then 20 characters is being grouped till it reached the end of the string. Comparison is done for that if it matches fine or else the characters are grouped by 1 to 21 , 22 to 41, 42 to 61 etc and comparison of ascii values are made. or

we could use regular expressions to find this pattern in the string to be searched. The regular expression is $[U(2)|D(2)][1][U(2)|D(2)][2][U(2)|D(2)][1][U(2)|D(2)][2]^ which is more efficient.

2. Algorithm is correct as the cheat code to be searched is in sequence of the 100000 characters to be searched. Regular expression is the best solution.

3. Worst case - O(2^m) where m is the length of regular expression O(2^20). , Expected case is O(n).

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.