part 2 of the question projest 4 puzzle contains only valid values (1s and 2s) h
ID: 3834161 • Letter: P
Question
part 2 of the question projest 4
puzzle contains only valid values (1s and 2s)
has_repeat(xs, v): given a list of numbers xs and a number n, check whether xs has repeated values of
n. Return True if v occurs more than once in xs; return False otherwise. You may not use .count()! o has_repeat([None], 1) False o has_repeat([1,2,3], 1) False o has_repeat([1,2,1], 1) True
get_row(puzzle, row_index): return the row at the specified row_index from puzzle as a list. Return None if the row_index is invalid.
o
get_row([[1,None],[2,None]], 0)
[1, None] # row 0
o
get_row([[1,None],[2,None]], 1)
[2, None] # row 1
o
get_row([[1,None],[2,None]], 2)
None # invalid index
is_valid_row(puzzle, row_index, complete): given a puzzle, determine if the row at row_index is a valid set of numbers (containing only valid values and unique values). complete is a boolean indicating if the row may contain None values. As before, if the puzzle is incomplete, also allow None, if it is complete, do not allow None. Also note that it is OK to have multiple None values in one row. (HINT:
use get_valid_numbers(), get_row() and has_repeat().)
board = [[2,4,None,None],[1,2,3,3],[3,1,None,5],[4,3,None,None]] o is_valid_row(board, 0, False) True # ok to have None if incomplete o is_valid_row(board, 0, True) False # cannot have None if complete o is_valid_row(board, 1, True) False # two 3s in same row o is_valid_row(board, 2, False) False # invalid value 5 o is_valid_row(board, -2, True) False # not even a valid row
has_valid_rows(puzzle, complete): determine if all the rows in puzzle are valid. complete is a boolean indicating if the rows should not contain None values. If incomplete allow None, if complete, do not allow None. (HINT: use get_row() and is_valid_row() as part of your solution).
o
has_valid_rows([[1,2],[1,2]], True)
True
o
has_valid_rows([[1,None],[1,2]], False)
True
o
has_valid_rows([[1,None],[1,2]], True)
False # cannot have None if complete
o
has_valid_rows([[1,4],[1,2]], True)
False # row 0 has a 4 in a 2x2 puzzle
get_column(puzzle, col_index): return the column with specified col_index from puzzle as a list. Return None if col_index is invalid.
o
get_column([[1,None],[2,None]], 0)
[1, 2]
# col 0
o
get_column([[1,None],[2,None]], 1)
[None, None]
# col 1
o
get_column([[1,None],[2,None]], 2)
None
# invalid index
is_valid_col(puzzle, col_index, complete): similar to is_valid_row but checking the validity of specified column instead. (HINT: use get_valid_numbers(), get_column() and has_repeat().)
board = [[2,1,None,None],[None,2,3,3],[3,1,None,5],[4,3,None,None]] o is_valid_col(board, 0, False) True # ok to have None if incomplete o is_valid_col(board, 0, True) False # cannot have None if complete o is_valid_col(board, 1, True) False # two 1s in same column o is_valid_col(board, 3, False) False # invalid value 5 o is_valid_col(board, 7, True) False # not even a valid column
has_valid_cols(puzzle, complete): determine if all the columns in puzzle are valid. complete is a boolean indicating if the columns may contain None values. If incomplete allow None, if complete, do not allow None. (HINT: use is_valid_col() and get_column() as part of your solution).
o
has_valid_cols([[1,2],[1,1]], True)
False # two 1s in col 0
o
has_valid_cols([[1,None],[2,1]], False)
True
o
has_valid_cols([[1,None],[2,1]], True)
False # cannot have None if complete
o
has_valid_cols([[1,4],[2,1]], True)
False # col 1 has a 4 in a 2x2 puzzle
• is_valid_cage_solution(puzzle, op, expected_total, locations): given a puzzle, an operation op, an integer expected_total, and a list of location tuples(e.g. a "cage" in a KenkKen puzzle), determine if the puzzle locations total correctly for the operation. You do not need to check if the rows/columns of the puzzle are valid.
Assumptions:
the puzzle is complete
the operation will be one of: '+', '-', or 'x'
subtraction operations will always involve two (and only two) locations o subtraction operations pass in the absolute value of the operation (see examples) o the locations will be valid and in a list in the form: [(row, col), (row, col), ..., (row, col)]
Examples:
is_valid_cage_solution([[1]], '+', 1, [(0,0)]) True
# location (0,0) sums to 1
is_valid_cage_solution([[1,2],[2,1]], '-', 1, [(0,0),(1,0)]) True
# the absolute value of location (0,0) – location (1,0) is 1 o is_valid_cage_solution([[1,2],[2,1]], '-', 1, [(1,0),(0,0)]) True
# the absolute value of location (1,0) – location (0,0) is 1 o is_valid_cage_solution([[1,2],[2,1]], 'x', 4, [(0,0),(0,1),(1,0),(1,1)]) True
# all values in the puzzle multiplied together = 4 o is_valid_cage_solution([[1,1],[1,1]], 'x', 1, [(0,0)]) True
# location (0,0) multiplies to 1
is_valid_cage_solution([[1,2],[2,1]], '+', 4, [(0,0),(0,1)]) False # location (0,0) and (0,1) do not sum to 4
is_valid(puzzle, cages, complete): determine if the given puzzle is currently in a valid state: if incomplete, check whether all rows/columns are valid; if complete also check cages and determine if the puzzle locations total correctly for the operation. (HINT: use has_valid_rows(), has_valid_cols(), and is_valid_cage_solution().)
board_1 = [[3,1,2],[2,3,1],[1,2,3]] board_2 = [[3,1,2],[2,2,1],[1,2,3]]
is_valid(board_1, [], False) True
is_valid(board_1, [['+',5,[(0,0),(1,0)]]], True) True o is_valid(board_1, [['+',4,[(0,0),(1,0)]]], True) False # not valid cage o is_valid(board_2, [['+',5,[(0,0),(1,0)]]], True) False # invalid row o is_valid([[None, None],[None,None]], [['+',5,[(0,0),(1,0)]]], False) True
get_board_string(puzzle): return a string representation of a puzzle which, when printed, would display an ascii art version of the puzzle. You may assume a puzzle of size 9x9 or smaller for this method only. Example:
For the puzzle [3,1,2],[2,None,None],[None,None,None]] the string would be: " [0] [1] [2] ------------- [0] | 3 | 1 | 2 | [1] | 2 | . | . | [2] | . | . | . | -------------"
Which printed would display as:
[0] [1] [2]
-------------
| 3 | 1 | 2 |
| 2 | . | . |
| . | . | . |
-------------
Notes: (a) Columns are three characters wide (a space, a number, and a space) with a dividers (|).
For the dashed lines “------” we need just enough to cover the top and bottom of the puzzle, no matter what size the puzzle is (one dash to start, then four dashes per column). To make the dashes appear in the correct place, there are also four spaces to the left.
The column headers ([0], [1], etc.) are centered on the columns and the row headers ([0], [1], etc.) have a single space between them and the first “|”. There are no leading spaces for the row headers.
Extra Credit
Implement these functions, and get up to five additional points (via the test cases).
get_missing_numbers_row_or_col(xs): determine which values are missing from the specified row (or column). The numbers should be returned in order. Note that if a column is passed in, it will be as a list
(as is the return from get_column(). (HINT: use get_valid_numbers() to as part of your solution.)
o get_missing_numbers_row_or_col([1,2]) [] # no values missing o get_missing_numbers_row_or_col([1,None,2]) [3] # value mising o get_missing_numbers_row_or_col([None,None,None]) [1,2,3] # all missing o get_missing_numbers_row_or_col([None,None,1]) [2,3] # 1 is in place o get_missing_numbers_row_or_col([1,1,1]) [2,3] # 1 is in place
candidates_at_location(puzzle, loc): return a list of suggested values for the given location (row, column) based on missing value checking of row and col. If the location is invalid or already contains a value, return None. (HINT: use is_valid_location() and get_missing_numbers_row_or_col().) o candidates_at_location([[None]], (0,0)) [1]
candidates_at_location([[1]], (0,0)) None
# location already contains a value
candidates_at_location([[None]], (1,1)) None
# location is invalid
candidates_at_location([[1,2,3],[2,3,1],[3,None,None]], (2,1)) [1]
# [1,2] valid for row, only [1] valid for column
candidates_at_location([[1,2,3],[1,3,2],[1,None,None]], (2,1)) []
# [2,3] valid for row, [1] valid for column
is_symmetric(puzzle): check whether the given puzzle is symmetric with respect to the main diagonal; return True if it is symmetric and False otherwise. See examples below.
Restriction: must not modify the original puzzle!
board_1 = [[3,1,2],[1,3,1],[2,1,3]] board_2 = [[3,1,2],[2,3,1],[1,2,3]]
o is_symmetric(board_1)
True
o is_symmetric(board_2)
False
Provided Code
[PROVIDED CODE] game(size, cages): For a given KenKen puzzle size and list of cages, game() will play in an interactive mode! Starting from an empty board, the user needs to decide how to fill the number in step by step until a solution is found and the cages are correct. Play with it!
This function calls your implementation of make_empty_board, set_location, unset_location, contains_only_valid_symbols, is_complete, is_valid, and
get_board_string. It will not be able to find correct solutions if your implementation of those functions is incomplete or buggy!
play_game_3x3() and play_game_4x4(): these functions will kick off one of two configured games for you to play (using the game() method above). If you want to try calling game() yourself, use these functions as a model.
How to play: when your implementation is ready, copy all the provided code from p4provided.py over into your .py file. Then load the file and enter the interactive mode using python3 -i yourcode.py. You can then run play_game_3x3() or play_game_4x4() and enjoy!
§ Note: If you’re having trouble following the text descriptions while playing, they are the same puzzles as Inky #1 from:
https://krazydad.com/inkies/sfiles/INKY_3E_b001_4pp.pdf (3x3)
https://krazydad.com/inkies/sfiles/INKY_4KX_b001_4pp.pdf (4x4)
[PROVIDED CODE] get_cages_string(cages): given a list of cage descriptions, returns user-readable string representation in the format below. This is a helper method for game().
Sample Runs
Sample runs have been provided for both play_game_3x3() and play_game_4x4(). These are the included files exampleRun3x3.txt and exampleRun4x4.txt respectively.
Grading Rubric
Code passes shared tests: 90 (zero points for hard-coding)
Well-documented/submitted: 10
TOTAL: 100 +5 extra credit
Some common reasons for other deductions: importing and using definitions; using built-ins or methods not explicitly approved above; hard-coding to match the provided test cases.
You will not earn test case points if you hard-code the answers. Your program should work for all possible inputs, not just the provided test cases. If you notice that one test case calls something(3), and you write the following to pass that particular test case, you'd be hardcoding.
def something(x): if x==3: #hard-coding example
return 8
...
Notice how it's not actually calculating, it's merely regurgitating a memorized answer. Doing this for all used test cases might make you feel like you've completed the program, but there are really unlimited numbers of test cases; hardcoded programs only work on the inputs that were hardcoded. Nobody learns, and the program isn't really that useful.
Reminders on Turning It In:
No work is accepted more than 48 hours after the initial deadline, regardless of token usage. Tokens are automatically applied whenever they are available, based on your last valid submission's time stamp. Late penalty will be applied if you have no tokens left.
You can turn in your code as many times as you want; we only grade the last submission that is <=48 hours late. If you are getting perilously close to the deadline, it may be worth it to turn in an "almost-done" version about 30 minutes before the clock strikes midnight. If you don't solve anything substantial at the last moment, you don't need to worry about turning in code that may or may not be runnable, or worry about being late by just an infuriatingly small number of seconds – you've already got a good version turned in that you knew worked at least for part of the program.
You can (and should) check your submitted files. If you re-visit BlackBoard and navigate to your submission, you can double-check that you actually submitted a file (it's possible to skip that crucial step and turn in a no-files submission!), you can re-download that file, and then you can re-test that file to make sure you turned in the version you intended to turn in. It is your responsibility to turn in the correct file, on time, to the correct assignment.
Use a backup service. Do future you an enormous favor, and keep all of your code in an automatically synced location, such as a Dropbox or Google Drive folder. Each semester someone's computer is lost/drowned/dead, or their USB drive or hard drive fails. Don't give these situations the chance to doom your project work!
o
get_row([[1,None],[2,None]], 0)
[1, None] # row 0
o
get_row([[1,None],[2,None]], 1)
[2, None] # row 1
o
get_row([[1,None],[2,None]], 2)
None # invalid index
Explanation / Answer
def get_valid_numbers(n):
return range(1, n+1)
def get_row(puzzle, row_index):
if row_index >= len(puzzle) or row_index < 0:
return None
return puzzle[row_index]
def has_repeat(xs, x):
count = 0
for n in xs:
if n == x:
if count == 1:
return True
else:
count = 1
return False
def is_valid_row(puzzle, row_index, complete):
row = get_row(puzzle, row_index)
if row == None:
return False
valid_numbers = get_valid_numbers(len(row))
for n in row:
if complete and (n == None):
return False
if n == None:
continue
if (not n in valid_numbers):
return False
if has_repeat(row, n):
return False
return True
def has_valid_rows(puzzle, complete):
for i in range(0, len(puzzle)):
if not is_valid_row(puzzle, i, complete):
return False
return True
def get_column(puzzle, col_index):
if col_index < 0 or col_index >= len(puzzle):
return None
col = []
for row in puzzle:
col.append(row[col_index])
return col
def is_valid_col(puzzle, col_index, complete):
col = get_column(puzzle, col_index)
if col == None:
return False
valid_numbers = get_valid_numbers(len(col))
for n in col:
if complete and (n == None):
return False
if n == None:
continue
if (not n in valid_numbers):
return False
if has_repeat(col, n):
return False
return True
def has_valid_cols(puzzle, complete):
for i in range(0, len(puzzle)):
if not is_valid_col(puzzle, i, complete):
return False
return True
print("is_valid_row")
board = [[2,4,None, None], [1,2,3,3], [3,1,None, 5], [4,3, None, None]]
print(is_valid_row(board, 0, False))
print(is_valid_row(board, 0, True))
print(is_valid_row(board, 1, True))
print(is_valid_row(board, 2, False))
print(is_valid_row(board, -2, True))
print()
print("has_valid_row")
print(has_valid_rows([[1,2],[1,2]], True))
print(has_valid_rows([[1,None],[1,2]], False))
print(has_valid_rows([[1,None],[1,2]], True))
print(has_valid_rows([[1,4],[1,2]], True))
print()
print ("get_column")
print(get_column([[1,None],[2,None]], 0))
print(get_column([[1,None],[2,None]], 1))
print(get_column([[1,None],[2,None]], 2))
print ()
print ("is_valid_col")
board = [[2,1,None,None],[None,2,3,3],[3,1,None,5],[4,3,None,None]]
print(is_valid_col(board, 0, False))
print(is_valid_col(board, 0, True))
print(is_valid_col(board, 1, True) )
print(is_valid_col(board, 3, False))
print(is_valid_col(board, 7, True))
print()
print("has_valid_cols")
print(has_valid_cols([[1,2],[1,1]], True))
print(has_valid_cols([[1,None],[2,1]], False))
print(has_valid_cols([[1,None],[2,1]], True))
print(has_valid_cols([[1,4],[2,1]], True))
# online code link in case indentation mess up https://goo.gl/0YioUl
# specification for is_valid_cage_solutions is not clear
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.