Description
Unlike the computer lab exercises, this is not a collaborative assignment. You must design, implement, and test your code on your own without the assistance of anyone other than the course instructor or TAs. In addition, you may not include solutions or portions of solutions obtained from any source other than those provided in class (so you are ONLY allowed to reuse examples from the textbook, lectures, or code you and your partner write to solve lab problems). Otherwise obtaining or providing solutions to any homework problem for this class is considered Academic Misconduct. See the syllabus and read section “Academic Dishonesty” for information concerning cheating. Always feel free to ask the instructor or the TAs if you are unsure of something. They will be more than glad to answer any questions that you have. We want you to be successful and learn so give us the chance to help you.
Instructions: This assignment consists of 3 problems, worth a total of 40 points. Solve the problems below by yourself, and put all functions in a single file called hw4.py. Use the signatures given for each class and function. We will be calling your functions with our test cases so you must use the information provided. If you have questions, ask!
Because homework files are submitted and tested electronically, the following are very important:
-
You follow all naming conventions mentioned in this homework description.
-
You submit the correct file, hw4.py, through Github by the due date deadline.
-
You follow the example input and output formats shown.
-
Regardless of how or where you develop your solutions, your programs should execute using the python3 command on CSELabs computers running the Linux operating system.
Push your work into Github under your own repo. The specific hosting directory should be: repo-<username>/hw4, where you replace <username> with your U of M user name. For instance, if your email address is bondx007@umn.edu, you should push your hw4 to this directory: repo-bondx007/hw4, meaning that the path to your file is repo-bondx007/hw4/hw4.py
The following will result in a score reduction equal to a percentage of the total possible points:
-
Incorrectly named/submitted source file, functions, or classes (20%)
-
Constraints not followed (40%)
-
Failure to execute due to syntax errors (30%)
-
Not filling out the documentation template for every function, other bad code style (10%)
Copyright ©2019 University of Minnesota. Do not copy, share, or redistribute without the express consent of the CSCI 1133 Staff.
Problem A. (20 points) Brute Force Password Cracking
You have intercepted some important documents from the Illuminati. The bad news is that they’re password-protected. The good news is that they’re encrypted with a four letter password, with only lowercase letters (a-z) allowed, so there’s only 264 = 456976 possibilities. Trying all of them is a bit unreasonable for a human, but should be easy for a computer.
Download the template file hw4.py from Canvas, along with all of the example encrypted .txt files (They are all in the compressed folder labelled hw4.zip) Since we haven’t covered reading from files yet, and most of you probably haven’t taken a course on cryptography, we have written the decrypt function for you: this takes the text from one of the encrypted files (as a string), and a four letter password as arguments. If the password works, then it prints out the decrypted text and returns the boolean value True; if not then it prints out nothing and returns False. (If you’re interested, the encryption used is a combination of the Vigenère cipher and modular exponentiation).
You must edit the function find_password(filename), which is partially written for you already. The function takes in a single string argument filename, which is a string representing the name of the file to be decrypted. Currently, it tries to decrypt the data in the file with the password ‘pwnd’ (you happen to know that this is the password to encrypted1.txt, but it does not work on any of the others). Change the function so that it tries every possible four letter lowercase alphabetic password, and then returns the password once it finds one that works. You can assume that all of the encrypted files will have a valid password.
Hints:
-
The chr() built-in function can be used to turn an integer into its ascii character. The ascii values for lowercase a through z are 97 through 122, inclusive.
-
Think about how many nested loops you need to hit every possible four-letter password.
Constraints:
-
Do not import/use any Python modules.
-
Do not use the input() function.
-
Your submission should have no code outside of function definitions (comments are fine).
-
Don’t edit the decrypt, vigenere, or encode functions in the template.
-
456976 is a lot of possibilities to check, but find_password still should run in under a minute on any lab machine.
-
We will test your program on files other than the example files given, so it must try all lowercase 4 letter passwords, not just the ones that work for the test files.
Examples (assumes that you are running this in the same folder as the .txt files; bold text indicates the password returned by find_password, italic text is the decrypted text printed by the decrypt function when it finds a match):
-
find_password(‘encrypted1.txt’) all your base are belong to us
‘pwnd’
-
find_password(‘encrypted2.txt’) stan is not what he seems
‘ford’
The zipped folder you downloaded should have two more examples, encrypted3.txt and encrypted4.txt. I won’t post the passwords and deciphered text for those two here, but if you get a decrypted phrase out that remotely resembles English, it probably worked.
Problem B. (10 points) Counting Primes
Many better cryptosystems than the one used in the previous problem rely on finding very large prime numbers. In this problem, we’ll find all of the primes within a given range.
Recall that a positive integer x is prime if it is divisible by exactly two positive integers: itself and 1. This
means that 1 is NOT prime: it is divisible by only one positive integer (1). To determine whether x is prime, you can check whether x is divisible by any integer between 2 and the square root of x (rounded down), inclusive. If not, then it is prime. Think about why you don’t have to check potential divisors above the square root of x.
Write a function count_primes(low, high) that takes in two positive integers, low and high. count_primes should return the number of primes between low and high, inclusive. It should also print out any such primes as it counts, one per line. If low > high, print nothing and return 0.
Hints:
-
You should consider breaking this problem into two parts. Write a function that determines whether a single integer is prime, and returns True or False. Test that function to ensure that it works. Then, use that function inside count_primes.
-
If a % b == 0, then a is divisible by b.
-
0 is not a positive integer, so it is not a valid input for this problem
Constraints:
-
Do not import/use any Python modules.
-
Do not use the input() function.
-
Your submission should have no code outside of function definitions (comments are fine).
-
When checking whether a given number x is prime, do not test potential divisors greater than the square root of x.
-
None of the examples below should take longer than a few seconds (if they do, then you’re probably checking more divisors than necessary).
Examples (text in bold is returned, text in italics is printed):
-
count_primes(1, 20) 2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
8
-
count_primes(547120100, 547120200) 547120117 is prime
547120193 is prime
3
-
count_primes(79, 97) 79 is prime
83 is prime
89 is prime
97 is prime
4
-
count_primes(3201814, 200)
0
-
count_primes(37, 37)
37 is prime
1
Problem C. (10 points) There’s Always a Bigger Fish
One simple model of predator-prey populations is the Lotka–Volterra equations. This model has three basic tenants, which have at least some basis in reality:
-
Without the influence of predators, the prey’s population experiences exponential growth (we assume here that the prey always have enough food).
-
Without the influence of prey, the predator’s population experiences exponential decay (we assume here that the prey is the predator’s primary food source).
-
Interactions between predators and prey cause the prey’s population to go down (because they are eaten), and the predator’s to go up (because they are able to feed themselves and their young). Interactions are proportional to both the number of prey in the area and the number of predators.
In this problem, we’ll be using a similar model to simulate the populations of three types of fish living in an isolated lake. We’ll call these bigfish, middlefish, and smallfish. The bigfish primarily consume middlefish, the middlefish primarily consume smallfish, and the smallfish do not require sustenance because they are magic.
Let s be the number of smallfish, m be the number of middlefish, and b be the number of bigfish in the lake. Each week, the net change in the population for each fish is given by the following equations (note that the symbol here stands for “net change”: these equations calculate the change in population for the week, not the new population total):
Δs = 0.1*s – 0.0002*s*m
Δm = -0.05*m + 0.0001*s*m – 0.00025*m*b Δb = -0.1*b + 0.0002*m*b
The above calculations should be applied based on the populations of the fish at the beginning of the week, so compute the changes to all three populations before applying any of them. These may generate non-integer populations of fish, but it’s an approximation anyway, so just leave the populations as floating point numbers.
Write a function called population(small, middle, big), which takes three integers as arguments, representing the initial numbers of smallfish, middlefish, and bigfish in the lake, respectively. The function should simulate the change in population each week using the equation above, and print out the populations truncated down to the nearest whole number (continue to store the populations as floating point values; truncate them only for printing purposes). You can use the int() built-in function for this. The function should return the number of weeks it takes for one of the populations to be essentially wiped out (less than 10 members), or 100 in the case that all three populations are still greater than or equal to 10 after 100 weeks.
Constraints:
-
Do not import/use any Python modules.
-
Do not use the input() function.
-
Your submission should have no code outside of function definitions (comments are fine).
Examples (text in bold is returned, everything else is printed):
>>> population(800, 600, 1000)
Week 1 – Small: 784 Middle: 468 Big: 1020
Week 2 – Small: 789 Middle: 361 Big: 1013
Week 3 – Small: 810 Middle: 280 Big: 985
Week 4 – Small: 846 Middle: 220 Big: 942
Week 5 – Small: 893 Middle: 176 Big: 889
Week 6 – Small: 951 Middle: 143 Big: 831
Week 7 – Small: 1019 Middle: 120 Big: 772
Week 8 – Small: 1096 Middle: 103 Big: 713
Week 9 – Small: 1183 Middle: 91 Big: 657
Week 10 – Small: 1280 Middle: 82 Big: 603
Week 11 – Small: 1387 Middle: 76 Big: 553
Week 12 – Small: 1505 Middle: 72 Big: 506
Week 13 – Small: 1633 Middle: 70 Big: 463
Week 14 – Small: 1774 Middle: 70 Big: 423
Week 15 – Small: 1926 Middle: 72 Big: 386
Week 16 – Small: 2091 Middle: 75 Big: 353
Week 17 – Small: 2269 Middle: 80 Big: 323
Week 18 – Small: 2459 Middle: 88 Big: 296
Week 19 – Small: 2661 Middle: 99 Big: 272
Week 20 – Small: 2875 Middle: 113 Big: 250
Week 21 – Small: 3097 Middle: 133 Big: 231
Week 22 – Small: 3323 Middle: 160 Big: 214
Week 23 – Small: 3549 Middle: 197 Big: 199
Week 24 – Small: 3764 Middle: 248 Big: 187
Week 25 – Small: 3953 Middle: 317 Big: 178
Week 26 – Small: 4098 Middle: 412 Big: 171
Week 27 – Small: 4169 Middle: 543 Big: 168
Week 28 – Small: 4133 Middle: 720 Big: 170
Week 29 – Small: 3951 Middle: 951 Big: 177
Week 30 – Small: 3594 Middle: 1237 Big: 193
Week 31 – Small: 3064 Middle: 1560 Big: 222
Week 32 – Small: 2414 Middle: 1874 Big: 269
Week 33 – Small: 1750 Middle: 2106 Big: 343
Week 34 – Small: 1188 Middle: 2189 Big: 453
Week 35 – Small: 786 Middle: 2091 Big: 606
Week 36 – Small: 536 Middle: 1834 Big: 799
Week 37 – Small: 393 Middle: 1474 Big: 1013
Week 38 – Small: 316 Middle: 1085 Big: 1210
Week 39 – Small: 279 Middle: 736 Big: 1352
Week 40 – Small: 266 Middle: 471 Big: 1416
Week 41 – Small: 267 Middle: 293 Big: 1408
Week 42 – Small: 278 Middle: 183 Big: 1350
Week 43 – Small: 296 Middle: 117 Big: 1264
Week 44 – Small: 319 Middle: 77 Big: 1167 Week 45 – Small: 346 Middle: 53 Big: 1069 Week 46 – Small: 377 Middle: 38 Big: 973 Week 47 – Small: 411 Middle: 28 Big: 884 Week 48 – Small: 450 Middle: 22 Big: 800 Week 49 – Small: 493 Middle: 17 Big: 724 Week 50 – Small: 541 Middle: 14 Big: 654 Week 51 – Small: 593 Middle: 12 Big: 590 Week 52 – Small: 651 Middle: 10 Big: 533 Week 53 – Small: 715 Middle: 9 Big: 480 53
>>> population(20,30000,10)
Week 1 – Small: -98 Middle: 28485 Big: 69
1
-
population(400, 1000, 9)
0
-
population(1200,400,300)
Week 1 – Small: 1224 Middle: 398 Big: 294
Week 2 – Small: 1248 Middle: 397 Big: 288
Week 3 – Small: 1274 Middle: 398 Big: 282
Week 4 – Small: 1300 Middle: 401 Big: 276
Week 5 – Small: 1326 Middle: 405 Big: 270
Week 6 – Small: 1350 Middle: 411 Big: 265
Week 7 – Small: 1374 Middle: 419 Big: 261
Week 8 – Small: 1396 Middle: 428 Big: 256
Week 9 – Small: 1416 Middle: 439 Big: 253
Week 10 – Small: 1433 Middle: 452 Big: 250
Week 11 – Small: 1447 Middle: 466 Big: 247
Week 12 – Small: 1457 Middle: 481 Big: 246
Week 13 – Small: 1462 Middle: 497 Big: 245
Week 14 – Small: 1463 Middle: 515 Big: 245
Week 15 – Small: 1458 Middle: 533 Big: 245
Week 16 – Small: 1449 Middle: 551 Big: 247
Week 17 – Small: 1434 Middle: 569 Big: 250
Week 18 – Small: 1413 Middle: 587 Big: 253
Week 19 – Small: 1389 Middle: 604 Big: 258
Week 20 – Small: 1360 Middle: 618 Big: 263
Week 21 – Small: 1327 Middle: 631 Big: 269
Week 22 – Small: 1293 Middle: 640 Big: 276
Week 23 – Small: 1256 Middle: 647 Big: 284
Week 24 – Small: 1219 Middle: 650 Big: 292
Week 25 – Small: 1182 Middle: 649 Big: 301
Week 26 – Small: 1147 Middle: 644 Big: 310
Week 27 – Small: 1114 Middle: 636 Big: 319
Week 28 – Small: 1083 Middle: 624 Big: 328
Week 29 – Small: 1056 Middle: 609 Big: 336
Week 30 – Small: 1033 Middle: 592 Big: 344
Week 31 – Small: 1014 Middle: 573 Big: 350
Week 32 – Small: 999 Middle: 552 Big: 355
Week 33 – Small: 989 Middle: 530 Big: 359
Week 34 – Small: 983 Middle: 509 Big: 361
Week 35 – Small: 981 Middle: 487 Big: 362
Week 36 – Small: 983 Middle: 467 Big: 361
Week 37 – Small: 990 Middle: 447 Big: 358
Week 38 – Small: 1000 Middle: 429 Big: 355
Week 39 – Small: 1014 Middle: 412 Big: 350
Week 40 – Small: 1032 Middle: 397 Big: 344
Week 41 – Small: 1053 Middle: 384 Big: 337
Week 42 – Small: 1077 Middle: 373 Big: 329
Week 43 – Small: 1105 Middle: 364 Big: 320
Week 44 – Small: 1135 Middle: 357 Big: 312
Week 45 – Small: 1167 Middle: 352 Big: 303
Week 46 – Small: 1202 Middle: 348 Big: 294
Week 47 – Small: 1238 Middle: 347 Big: 285
Week 48 – Small: 1276 Middle: 348 Big: 276
Week 49 – Small: 1314 Middle: 351 Big: 268
Week 50 – Small: 1353 Middle: 356 Big: 260
Week 51 – Small: 1392 Middle: 363 Big: 252
Week 52 – Small: 1430 Middle: 373 Big: 246
Week 53 – Small: 1466 Middle: 384 Big: 239
Week 54 – Small: 1500 Middle: 399 Big: 234
Week 55 – Small: 1530 Middle: 415 Big: 229
Week 56 – Small: 1556 Middle: 434 Big: 225
Week 57 – Small: 1577 Middle: 456 Big: 222
Week 58 – Small: 1590 Middle: 479 Big: 220
Week 59 – Small: 1597 Middle: 505 Big: 219
Week 60 – Small: 1595 Middle: 533 Big: 220
Week 61 – Small: 1584 Middle: 562 Big: 221
Week 62 – Small: 1565 Middle: 592 Big: 224
Week 63 – Small: 1536 Middle: 622 Big: 228
Week 64 – Small: 1498 Middle: 651 Big: 234
Week 65 – Small: 1453 Middle: 678 Big: 241
Week 66 – Small: 1401 Middle: 701 Big: 249
Week 67 – Small: 1344 Middle: 721 Big: 259
Week 68 – Small: 1285 Middle: 735 Big: 271
Week 69 – Small: 1224 Middle: 743 Big: 284
Week 70 – Small: 1165 Middle: 744 Big: 297
Week 71 – Small: 1108 Middle: 738 Big: 312 Week 72 – Small: 1055 Middle: 725 Big: 327 Week 73 – Small: 1007 Middle: 706 Big: 342 Week 74 – Small: 966 Middle: 681 Big: 356 Week 75 – Small: 931 Middle: 653 Big: 369 Week 76 – Small: 902 Middle: 620 Big: 380 Week 77 – Small: 880 Middle: 586 Big: 389 Week 78 – Small: 865 Middle: 551 Big: 396 Week 79 – Small: 856 Middle: 517 Big: 400 Week 80 – Small: 853 Middle: 484 Big: 402 Week 81 – Small: 856 Middle: 452 Big: 400 Week 82 – Small: 864 Middle: 423 Big: 396 Week 83 – Small: 877 Middle: 396 Big: 390 Week 84 – Small: 895 Middle: 372 Big: 382 Week 85 – Small: 918 Middle: 351 Big: 373 Week 86 – Small: 945 Middle: 333 Big: 362 Week 87 – Small: 977 Middle: 318 Big: 350 Week 88 – Small: 1012 Middle: 305 Big: 337 Week 89 – Small: 1051 Middle: 295 Big: 324 Week 90 – Small: 1094 Middle: 288 Big: 310 Week 91 – Small: 1141 Middle: 282 Big: 297 Week 92 – Small: 1190 Middle: 279 Big: 284 Week 93 – Small: 1243 Middle: 279 Big: 272 Week 94 – Small: 1298 Middle: 281 Big: 260 Week 95 – Small: 1354 Middle: 285 Big: 248 Week 96 – Small: 1413 Middle: 291 Big: 238 Week 97 – Small: 1471 Middle: 301 Big: 228 Week 98 – Small: 1530 Middle: 313 Big: 219 Week 99 – Small: 1587 Middle: 328 Big: 211 Week 100 – Small: 1642 Middle: 346 Big: 203 100
