Cracking the Code

Aja and Emily have decided to quit their jobs as TAs and become l$33$t h$4$x$0$rz$.$

But it turns out, hacking is mostly just brute force trial and error. They have guesses at what the password hashing function is$,$ but need to confirm it$.$

Here$$s where you come in$.$ They need you to verify if their password cracker is w Cracking the Code

Aja and Emily have decided to quit their jobs as TAs and become l$33$t h$4$x$0$rz$.$

But it turns out, hacking is mostly just brute force trial and error. They have guesses at what the password hashing function is$,$ but need to confirm it$.$

Here$$s where you come in$.$ They need you to verify if their password cracker is working. Don$$t worry, you won$$t need to know anything about cryptography. In fact, the final password cracking algorithm will be hidden from you.

You will be given a function that can compare two hashed passwords and returns true if they are the same unhashed password, and false if they are not.

Using this function, we want to determine if there are popular passwords in a list because those accounts likely share overused, simple credentials and are easily exploited.

Your job is to take a list of unsorted passwords, and determine if more than half are the same password. For example, let A$,$ B$,$ and C be unhashed passwords.

$[$A$,$A$,$A$,$A$]$wouldresultin$[1,2,3,4]$

$[$A$,$ A$,$ B$,$ A$]$ would result in $[1,2,4]$

$[$A$,$ B$,$ C$,$ A$]$ would result in $[]$

$[$A$,$A$,$A$,$B$,$B$,$B$,$C$,$C$]$wouldresultin$[]$

You cannot compare passwords directly to each other because they are $($naively$)$ salted.

Good luck! Make Aja and Emily proud.

Develop an efficient divide & conquer algorithm to determine if more than half are the same password and if so$,$ retrieve the indices the popular password is stored in$.$

Notes:

$$ You must use the provided function to compare two passwords. $$ Your output must be in ascending order.

Implement your algorithm for solving this problem in cs$6515\_$cracking$\_$the$\_$code.py$.$

Divide & Conquer Homework

In this assignment you will use the provided code template to implement solutions to each given problem. The solutions you submit must follow the guidelines provided in this document as well as any given in code.

Your solutions must implement a divide & conquer approach to each given problem. Both recursive and iterative implementations are accepted.

When using a known divide & conquer algorithm, only those covered in course material $($see Ed$)$ are allowed, and some are provided for you to use.

Restrictions

$$ Template code is provided and must be used.

$$ Your code must be compatible with Python $3\mathrm{.}10.$

$$ The provided container classes and their public methods are the only allowed means for retrieving, storing, and modifying data for solving each given problem.

$$ Use of built$-$in functions $($e$.$g$.,$ map, zip, sorted$)$ and raw container types $($e$.$g$.,$ dict, set, list$)$ to do so is strictly prohibited.

$$ Accessing private members and methods $($denoted by a $\_$ prefix$)$ of the provided container classes is strictly prohibited.

$$ Do not add, change, or remove imports in the code file used for submission.

$$ Do not modify the function name, definition, or any of the provided utilities.

Testing

You can run your test cases by issuing the python$3-$m unittest command from the directory containing your solution files.

Generally Accepted Algorithm Practices

While using most built$-$in convenience features of Python is prohibited, the following examples are considered allowed, sensible use.

$$ Using local variables to hold default, intermediate, or single$-$result data.

$$ Using public methods of any provided standard library types, such as Decimal.

$$ Using raw containers to initialize given containers or facilitate use of approved built$-$in methods. $$ Using abs$()$ to get the absolute value of a number or calculation.

$$ Using len$()$ to determine the length of your input$($s$).$

$$ Using match to simplify chained conditional checks.

$$ Using max$()$ and min$()$ to perform a value comparison between $2$ or more items. May use key$=.$ Using range$()$ as part of a loop construct.

$$ Using round$()$ to round values, if a given problem calls for it$.$

Implementation file:

cs$6515\_$cracking$\_$the$\_$code.py

from typing import Callable

import algo

from util.mutablesequence import MutableSequence

from util.sequence import Sequence

global$\_$password$\_$list $=$ None

global$\_$cracking$\_$function $=$ None

def CrackingCode$($

password$\_$list: Sequence$[$int$],$

cracking$\_$function: Callable$[[$Sequence$[$int$],$ int, int$],$ bool$],$

$)->$ MutableSequence$[$int$]$:

# Using globals here allow you to call compare$\_$passwords from anywhere without having to pass the list and function around.

# You do not need to use this if you would rather use local scope only.

global global$\_$password$\_$list, global$\_$cracking$\_$function

global$\_$password$\_$list $=$ password$\_$list

global$\_$cracking$\_$function $=$ cracking$\_$function

pass

def compare$\_$passwords$($a: int, b: int$)->$ bool:

return global$\_$cracking$\_$function$($global$\_$password$\_$list, a$,$ b$)$