How did writing the solution go? Ready to look at the answer?

For this problem, you’ll look at a few different solutions. The first of these is not so good:

# integersums.pydeffirst(n):num=1sum=0whilenum<n+1:sum=sum+numnum=num+1returnsum

In this solution, you manually build awhile loop to run through the numbers1 throughn. You keep a runningsum and then return it when you’ve finished the loop.

This solution works, but it has two problems:

1. It doesn’t display your knowledge of Python and how the language simplifies tasks like this.

2. It doesn’t meet the error conditions in the problem description. Passing in astring will result in the function throwing an exception when it should just return0.

You’ll deal with the error conditions in the final answer below, but first let’s refine the core solution to be a bit morePythonic.

The first thing to think about is thatwhile loop. Python has powerful mechanisms for iterating over lists and ranges. Creating your own is usually unnecessary, and that’s certainly the case here. You can replace thewhile loop with a loop that iterates over arange():

# integersums.pydefbetter(n):sum=0fornuminrange(n+1):sum+=numreturnsum

You can see that thefor...range() construct has replaced yourwhile loop and shortened the code. One thing to note is thatrange() goes up to but does not include the number given, so you need to usen + 1 here.

This was a nice step! It removes some of the boilerplate code of looping over a range and makes your intention clearer. But there’s still more you can do here.

Summing a list of integers is another thing Python is good at:

# integersums.pydefeven_better(n):returnsum(range(n+1))

Wow! By using the built-insum(), you got this down to one line of code! Whilecode golf generally doesn’t produce the most readable code, in this case you have a win-win: shorterand more readable code.

There’s one problem remaining, however. This code still doesn’t handle the error conditions correctly. To fix that, you can wrap your previous code in atry...except block:

# integersums.pydefadd_it_up(n):try:result=sum(range(n+1))exceptTypeError:result=0returnresult

This solves the problem and handles the error conditions correctly. Way to go!

Occasionally, interviewers will ask this question with a fixed limit, something like “Print the sum of the first nine integers.” When the problem is phrased that way, one correct solution would beprint(45).

If you give this answer, however, then you should follow up with code that solves the problem step by step. The trick answer is a good place to start your answer, but it’s not a great place to end.

If you’d like to extend this problem, try adding an optional lower limit toadd_it_up() to give it more flexibility!

This solution makes use of.translate() from thestr class in the standard library. If you struggled with this problem, then you might want to pause a moment and consider how you could use.translate() in your solution.

Okay, now that you’re ready, let’s look at this solution:

 1# caesar.py 2importstring 3 4defcaesar(plain_text,shift_num=1): 5letters=string.ascii_lowercase 6mask=letters[shift_num:]+letters[:shift_num] 7trantab=str.maketrans(letters,mask) 8returnplain_text.translate(trantab)

You can see that the function makes use of three things from thestring module:

1. .ascii_lowercase
2. .maketrans()
3. .translate()

In the first two lines, you create a variable with all the lowercase letters of the alphabet (ASCII only for this program) and then create amask, which is the same set of letters, only shifted. The slicing syntax is not always obvious, so let’s walk through it with a real-world example:

>>>importstring>>>x=string.ascii_lowercase>>>x'abcdefghijklmnopqrstuvwxyz'>>>x[3:]'defghijklmnopqrstuvwxyz'>>>x[:3]'abc'

You can see thatx[3:] is all the lettersafter the third letter,'c', whilex[:3] is just the first three letters.

Line 6 in the solution,letters[shift_num:] + letters[:shift_num], creates a list of letters shifted byshift_num letters, with the letters at the end wrapped around to the front. Once you have the list of letters and themask of letters you want to map to, you call.maketrans() to create a translation table.

Next, you pass the translation table to the string method.translate(). It maps all characters inletters to the corresponding letters inmask and leaves all other characters alone.

This question is an exercise in knowing and using the standard library. You may be asked a question like this at some point during an interview. If that happens to you, it’s good to spend some time thinking about possible answers. If you can remember the method—.translate() in this case—then you’re all set.

But there are a couple of other scenarios to consider:

1. You may completely draw a blank. In this case, you’ll probably solve this problem the way you solvethe next one, and that’s an acceptable answer.

2. You may remember that the standard libraryhas a function to do what you want but not remember the details.

If you were doing normal work and hit either of these situations, then you’d just do some searching and be on your way. But in an interview situation, it will help your cause to talk through the problem out loud.

Asking the interviewer for specific help is far better than just ignoring it. Try something like “Ithink there’s a function that maps one set of characters to another. Can you help me remember what it’s called?”

In an interview situation, it’s often better to admit that you don’t know something than to try to bluff your way through.

For this problem, two different solutions are provided. Check out both and see which one you prefer!

Solution 1

For the first solution, you follow the problem description closely, adding an amount to each character and flipping it back to the beginning of the alphabet when it goeson beyondz:

 1# caesar.py 2importstring 3 4defshift_n(letter,amount): 5ifletternotinstring.ascii_lowercase: 6returnletter 7new_letter=ord(letter)+amount 8whilenew_letter>ord("z"): 9new_letter-=2610whilenew_letter<ord("a"):11new_letter+=2612returnchr(new_letter)1314defcaesar(message,amount):15enc_list=[shift_n(letter,amount)forletterinmessage]16return"".join(enc_list)

Starting on line 14, you can see thatcaesar() does alist comprehension, calling a helper function for each letter inmessage. It then does a.join() to create the new encoded string. This is short and sweet, and you’ll see a similar structure in the second solution. The interesting part happens inshift_n().

Here you can see another use forstring.ascii_lowercase, this time filtering out any letter that isn’t in that group. Once you’re certain you’ve filtered out any non-letters, you can proceed to encoding. In this version of encoding, you use two functions from the Python standard library:

1. ord()
2. chr()

Again, you’re encouraged not only to learn these functions but also to consider how you might respond in an interview situation if you couldn’t remember their names.

ord() does the work of converting a letter to a number, andchr() converts it back to a letter. This is handy as it allows you to do arithmetic on letters, which is what you want for this problem.

The first step of your encoding on line 7 gets the numeric value of the encoded letter by usingord() to get the numeric value of the original letter.ord() returns theUnicode code point of the character, which turns out to be the ASCII value.

For many letters with small shift values, you can convert the letter back to a character and you’ll be done. But consider the starting letter,z.

A shift of one character should result in the lettera. To achieve this wraparound, you find the difference from the encoded letter to the letterz. If that difference is positive, then you need to wrap back to the beginning.

You do this in lines 8 to 11 by repeatedly adding 26 to or subtracting it from the character until it’s in the range of ASCII characters. Note that this is a fairly inefficient method for fixing this issue. You’ll see a better solution in the next answer.

Finally, on line 12, your conversion shift function takes the numeric value of the new letter and converts it back to a letter to return it.

While this solution takes a literal approach to solving the Caesar cipher problem, you could also use a different approach modeled after the.translate() solution inpractice problem 2.

Solution 2

The second solution to this problem mimics the behavior of Python’s built-in method.translate(). Instead of shifting each letter by a given amount, it creates a translation map and uses it to encode each letter:

 1# caesar.py 2importstring 3 4defshift_n(letter,table): 5try: 6index=string.ascii_lowercase.index(letter) 7returntable[index] 8exceptValueError: 9returnletter1011defcaesar(message,amount):12amount=amount%2613table=string.ascii_lowercase[amount:]+string.ascii_lowercase[:amount]14enc_list=[shift_n(letter,table)forletterinmessage]15return"".join(enc_list)

Starting withcaesar() on line 11, you start by fixing the problem ofamount being greater than26. In the previous solution, you looped repeatedly until the result was in the proper range. Here, you take a more direct and more efficient approach using the mod operator (%).

Themod operator produces the remainder from an integer division. In this case, you divide by26, which means the results are guaranteed to be between0 and25, inclusive.

Next, you create the translation table. This is a change from the previous solutions and is worth some attention. You’ll see more about this toward the end of this section.

Once you create thetable, the rest ofcaesar() is identical to the previous solution: a list comprehension to encrypt each letter and a.join() to create a string.

shift_n() finds the index of the given letter in the alphabet and then uses this to pull a letter from thetable. Thetry...except block catches those cases that aren’t found in the list of lowercase letters.

Now let’s discuss the table creation issue. For this toy example, it probably doesn’t matter too much, but it illustrates a situation that occurs frequently in everyday development: balancing clarity of code against known performance bottlenecks.

If you examine the code again, you’ll see thattable is used only insideshift_n(). This indicates that, in normal circumstances, it should have been created in, and thus have itsscope limited to,shift_n():

# caesar.pyimportstringdefslow_shift_n(letter,amount):table=string.ascii_lowercase[amount:]+string.ascii_lowercase[:amount]try:index=string.ascii_lowercase.index(letter)returntable[index]exceptValueError:returnletterdefslow_caesar(message,amount):amount=amount%26enc_list=[shift_n(letter,amount)forletterinmessage]return"".join(enc_list)

The issue with that approach is that it spends time calculating the same table for every letter of the message. For small messages, this time will be negligible, but it might add up for larger messages.

Another possible way that you could avoid this performance penalty would be to maketable aglobal variable. While this also cuts down on the construction penalty, it makes the scope oftable even larger. This doesn’t seem better than the approach shown above.

At the end of the day, the choice between creatingtable once up front and giving it a larger scope or just creating it for every letter is what’s called adesign decision. You need to choose the design based on what you know about the actual problem you’re trying to solve.

If this is a small project and you know it will be used to encode large messages, then creating the table only once could be the right decision. If this is only a portion of a larger project, meaning maintainability is key, then perhaps creating the table each time is the better option.

Since you’ve looked at two solutions, it’s worth taking a moment to discuss their similarities and differences.

Solution Comparison

You’ve seen two solutions in this part of the Caesar cipher, and they’re fairly similar in many ways. They’re about the same number of lines. The two main routines are identical except for limitingamount and creatingtable. It’s only when you look at the two versions of the helper function,shift_n(), that the differences appear.

The firstshift_n() is an almost literal translation of what the problem is asking for: “Shift the letter down the alphabet and wrap it around atz.” This clearly maps back to the problem statement, but it has a few drawbacks.

Although it’s about the same length as the second version, the first version ofshift_n() is more complex. This complexity comes from the letter conversion and math needed to do the translation. The details involved—converting to numbers, subtracting, and wrapping—mask the operation you’re performing. The secondshift_n() is far less involved in its details.

The first version of the function is also specific to solving this particular problem. The second version ofshift_n(), like the standard library’s.translate() that it’s modeled after, is more general-purpose and can be used to solve a larger set of problems. Note that this is not necessarily a good design goal.

One of the mantras that came out of theExtreme Programming movement is “You aren’t gonna need it” (YAGNI). Frequently, software developers will look at a function likeshift_n() and decide that it would be better and more general-purpose if they made it evenmore flexible, perhaps by passing in a parameter instead of usingstring.ascii_lowercase.

While that would indeed make the function more general-purpose, it would also make it more complex. The YAGNI mantra is there to remind you not to add complexity before you have a specific use case for it.

To wrap up your Caesar cipher section, there are clear trade-offs between the two solutions, but the secondshift_n() seems like a slightly better and more Pythonic function.

Full Solution

Since this solution is longer than what you saw for the integer sums or the Caesar cipher problems, let’s start with the full program:

# logparse.pyimportdatetimeimportsysdefget_next_event(filename):withopen(filename,"r")asdatafile:forlineindatafile:if"dut: Device State: "inline:line=line.strip()# Parse out the action and timestampaction=line.split()[-1]timestamp=line[:19]yield(action,timestamp)defcompute_time_diff_seconds(start,end):format="%b%d %H:%M:%S:%f"start_time=datetime.datetime.strptime(start,format)end_time=datetime.datetime.strptime(end,format)return(end_time-start_time).total_seconds()defextract_data(filename):time_on_started=Noneerrs=[]total_time_on=0foraction,timestampinget_next_event(filename):# First test for errsif"ERR"==action:errs.append(timestamp)elif("ON"==action)and(nottime_on_started):time_on_started=timestampelif("OFF"==action)andtime_on_started:time_on=compute_time_diff_seconds(time_on_started,timestamp)total_time_on+=time_ontime_on_started=Nonereturntotal_time_on,errsif__name__=="__main__":total_time_on,errs=extract_data(sys.argv[1])print(f"Device was on for{total_time_on} seconds")iferrs:print("Timestamps of error events:")forerrinerrs:print(f"\t{err}")else:print("No error events found.")

That’s your full solution. You can see that the program consists of three functions and the main section. You’ll work through them from the top.

Helper Function:get_next_event()

First up isget_next_event():

# logparse.pydefget_next_event(filename):withopen(filename,"r")asdatafile:forlineindatafile:if"dut: Device State: "inline:line=line.strip()# Parse out the action and timestampaction=line.split()[-1]timestamp=line[:19]yield(action,timestamp)

Because it contains ayield statement, this function is agenerator. That means you can use it to generate one event from the log file at a time.

You could have just usedfor line in datafile, but instead you add a little bit of filtering. The calling routine will get only those events that havedut: Device State: in them. This keeps all the file-specific parsing contained in a single function.

This might makeget_next_event() a bit more complicated, but it’s a relatively small function, so it remains short enough to read and comprehend. It also keeps that complicated code encapsulated in a single location.

You might be wondering whendatafile gets closed. As long as you call the generator until all of the lines are read fromdatafile, thefor loop will complete, allowing you to leave thewith block and exit from the function.

Helper Function:compute_time_diff_seconds()

The second function iscompute_time_diff_seconds(), which, as the name suggests, computes the number of seconds between two timestamps:

# logparse.pydefcompute_time_diff_seconds(start,end):format="%b%d %H:%M:%S:%f"start_time=datetime.datetime.strptime(start,format)end_time=datetime.datetime.strptime(end,format)return(end_time-start_time).total_seconds()

There are a few interesting points to this function. The first is that subtracting the twodatetime objects results in adatetime.timedelta. For this problem, you will report total seconds, so returning.total_seconds() from thetimedelta is appropriate.

The second item of note is that there are many, many packages in Python that simplify handling dates and times. In this case, your use model is simple enough that it doesn’t warrant the complexity of pulling in an external library when the standard library functions will suffice.

That said,datetime.datetime.strptime() is worthy of mention. When passed a string and a specific format,.strptime() parses that string with the given format and produces adatetime object.

This is another place where, in an interview situation, it’s important not to panic if you can’t remember the exact names of the Python standard library functions.

Helper Function:extract_data()

Next up isextract_data(), which does the bulk of the work in this program. Before you dive into the code, let’s step back and talk about state machines.

State machines are software (or hardware) devices that transition from onestate to another depending on specific inputs. That’s a really broad definition that might be difficult to grasp, so let’s look at a diagram of the state machine you’ll be using below:

In this diagram, the states are represented by the labeled boxes. There are only two states here,ON andOFF, which correspond to the state of the device. There are also two input signals,Device State: ON andDevice State: OFF. The diagram uses arrows to show what happens when an input occurs while the machine is in each state.

For example, if the machine is in theON state and theDevice State: ON input occurs, then the machine stays in theON state. No change happens. Conversely, if the machine receives theDevice State: OFF input when it’s in theON state, then it will transition to theOFF state.

While the state machine here is only two states with two inputs, state machines are often much more complex. Creating a diagram of expected behavior can help you make the code that implements the state machine more concise.

Let’s move back toextract_data():

# logparse.pydefextract_data(filename):time_on_started=Noneerrs=[]total_time_on=0foraction,timestampinget_next_event(filename):# First test for errsif"ERR"==action:errs.append(timestamp)elif("ON"==action)and(nottime_on_started):time_on_started=timestampelif("OFF"==action)andtime_on_started:time_on=compute_time_diff_seconds(time_on_started,timestamp)total_time_on+=time_ontime_on_started=Nonereturntotal_time_on,errs

It might be hard to see the state machine here. Usually, state machines require a variable to hold the state. In this case, you usetime_on_started to serve two purposes:

1. Indicate state:time_on_started holds the state of your state machine. If it’sNone, then the machine is in theOFF state. If it’snot None, then the machine isON.
2. Store start time: If the state isON, thentime_on_started also holds the timestamp of when the device turned on. You use this timestamp to callcompute_time_diff_seconds().

The top ofextract_data() sets up your state variable,time_on_started, and also the two outputs you want.errs is a list of timestamps at which theERR message was found, andtotal_time_on is the sum of all periods when the device was on.

Once you’ve completed the initial setup, you call theget_next_event() generator to retrieve each event and timestamp. Theaction it receives is used to drive the state machine, but before it checks for state changes, it first uses anif block to filter out anyERR conditions and add those toerrs.

After the error check, the firstelif block handles transitions to theON state. You can transition toON only when you’re in theOFF state, which is signaled bytime_on_started beingFalse. If you’re not already in theON state and the action is"ON", then you store thetimestamp, putting the machine into theON state.

The secondelif handles the transition to theOFF state. On this transition,extract_data() needs to compute the number of seconds the device was on. It does this using thecompute_time_diff_seconds() you saw above. It adds this time to the runningtotal_time_on and setstime_on_started back toNone, effectively putting the machine back into theOFF state.

Main Function

Finally, you can move on to the__main__ section. This final section passessys.argv[1], which is the firstcommand-line argument, toextract_data() and then presents a report of the results:

# logparse.pyif__name__=="__main__":total_time_on,errs=extract_data(sys.argv[1])print(f"Device was on for{total_time_on} seconds")iferrs:print("Timestamps of error events:")forerrinerrs:print(f"\t{err}")else:print("No error events found.")

To call this solution, you run the script and pass the name of the log file. Running your example code results in this output:

$python3logparse.pytest.logDevice was on for 7 secondsTimestamps of error events:   Jul 11 16:11:54:661   Jul 11 16:11:56:067

Your solution might have different formatting, but the information should be the same for the sample log file.

There are many ways to solve a problem like this. Remember that in an interview situation, talking through the problem and your thought process can be more important than which solution you choose to implement.

This is a larger and more complex problem than you’ve looked at so far in this tutorial. You’ll walk through the problem step by step, ending with arecursive function that solves the puzzle. Here’s a rough outline of the steps you’ll take:

• Read the puzzle into a grid form.
• For each cell:
  • For each possible number in that cell:
    • Place the number in the cell.
    • Remove that number from the row, column, and small square.
    • Move to the next position.
  • If no possible numbers remain, then declare the puzzleunsolvable.
  • If all cells are filled, thenreturn the solution.

The tricky part of this algorithm is keeping track of the grid at each step of the process. You’ll use recursion, making a new copy of the grid at each level of the recursion, to maintain this information.

With that outline in mind, let’s start with the first step, creating the grid.

Generating a Grid From a Line

To start, it’s helpful to convert the puzzle data into a more usable format. Even if you eventually want to solve the puzzle in the givenSDM format, you’ll likely make faster progress working through the details of your algorithm with the data in a grid form. Once you have a solution that works, then you can convert it to work on a different data structure.

To this end, let’s start with a couple of conversion functions:

 1# sudokusolve.py 2defline_to_grid(values): 3grid=[] 4line=[] 5forindex,charinenumerate(values): 6ifindexandindex%9==0: 7grid.append(line) 8line=[] 9line.append(int(char))10# Add the final line11grid.append(line)12returngrid1314defgrid_to_line(grid):15line=""16forrowingrid:17r="".join(str(x)forxinrow)18line+=r19returnline

Your first function,line_to_grid(), converts the data from a single string of eighty-one digits to a list of lists. For example, it converts the stringline to a grid likestart:

line="0040060790000006020560923000780...90007410920105000000840600100"start=[[0,0,4,0,0,6,0,7,9],[0,0,0,0,0,0,6,0,2],[0,5,6,0,9,2,3,0,0],[0,7,8,0,6,1,0,3,0],[5,0,9,0,0,0,4,0,6],[0,2,0,5,4,0,8,9,0],[0,0,7,4,1,0,9,2,0],[1,0,5,0,0,0,0,0,0],[8,4,0,6,0,0,1,0,0],]

Each inner list here represents a horizontal row in your sudoku puzzle.

You start with an emptygrid and an emptyline. You then build eachline by converting nine characters from thevalues string to single-digit integers and then appending them to the currentline. Once you have nine values in aline, as indicated byindex % 9 == 0 on line 7, you insert thatline into thegrid and start a new one.

The function ends by appending the finalline to thegrid. You need this because thefor loop will end with the lastline still stored in the local variable and not yet appended togrid.

The inverse function,grid_to_line(), is slightly shorter. It uses agenerator expression with.join() to create a nine-digit string for each row. It then appends that string to the overallline and returns it. Note that it’s possible to use nested generators to create this result in fewer lines of code, but the readability of the solution starts to fall off dramatically.

Now that you’ve got the data in the data structure you want, let’s start working with it.

Generating a Small Square Iterator

Your next function is a generator that will help you search for the smaller three-by-three square a given position is in. Given the x- and y-coordinates of the cell in question, this generator will produce a list of coordinates that match the square that contains it:

In the image above, you’re examining cell(3, 1), so your generator will produce coordinate pairs corresponding to all the lightly shaded cells, skipping the coordinates that were passed in:

(3,0),(4,0),(5,0),(4,1),(5,1),(3,2),(4,2),(5,2)

Putting the logic for determining this small square in a separate utility function keeps the flow of your other functions more readable. Making this a generator allows you to use it in afor loop to iterate through each of the values.

The function to do this involves using the limitations of integer math:

# sudokusolve.pydefsmall_square(x,y):upperX=((x+3)//3)*3upperY=((y+3)//3)*3lowerX=upperX-3lowerY=upperY-3forsubXinrange(lowerX,upperX):forsubYinrange(lowerY,upperY):# If subX != x or subY != y:ifnot(subX==xandsubY==y):yieldsubX,subY

There are a lot of threes in a couple of those lines, which makes lines like((x + 3) // 3) * 3 look confusing. Here’s what happens whenx is1.

>>>x=1>>>x+34>>>(x+3)//31>>>((x+3)//3)*33

Using the rounding of integer math allows you to get the next-highest multiple of three above a given value. Once you have this, subtracting three will give you the multiple of three below the given number.

There are a few more low-level utility functions to examine before you start building on top of them.

Moving to the Next Spot

Your solution will need to walk through the grid structure one cell at a time. This means that at some point, you’ll need to figure out what the next position should be.compute_next_position() to the rescue!

compute_next_position() takes the current x- and y-coordinates as input and returns a tuple containing afinished flag along with the x- and y-coordinates of the next position:

# sudokusolve.pydefcompute_next_position(x,y):nextY=ynextX=(x+1)%9ifnextX<x:nextY=(y+1)%9ifnextY<y:return(True,0,0)return(False,nextX,nextY)

Thefinished flag tells the caller that the algorithm has walked off the end of the puzzle and has completed all the squares. You’ll see how that’s used in a later section.

Removing Impossible Numbers

Your final low-level utility is quite small. It takes an integer value and an iterable. If the value is nonzero and appears in the iterable, then the function removes it from the iterable:

# sudokusolve.pydeftest_and_remove(value,possible):ifvalue!=0andvalueinpossible:possible.remove(value)

Typically, you wouldn’t make this small bit of functionality into a function. You’ll use this function several times, though, so it’s best to follow theDRY principle and pull it up to a function.

Now you’ve seen the bottom level of the functionality pyramid. It’s time to step up and use those tools to build a more complex function. You’re almost ready to solve the puzzle!

Finding What’s Possible

Your next function makes use of some of the low-level functions you’ve just walked through. Given a grid and a position on that grid, it determines what values that position could still have:

For the grid above, at the position(3, 1), the possible values are[1, 5, 8] because the other values are all present, either in that row or column or in the small square you looked at earlier.

This is the responsibility ofdetect_possible():

# sudokusolve.pydefdetect_possible(grid,x,y):ifgrid[x][y]:return[grid[x][y]]possible=set(range(1,10))# Test horizontal and verticalforindexinrange(9):ifindex!=y:test_and_remove(grid[x][index],possible)ifindex!=x:test_and_remove(grid[index][y],possible)# Test in small squareforsubX,subYinsmall_square(x,y):test_and_remove(grid[subX][subY],possible)returnlist(possible)

The function starts by checking if the given position atx andy already has a nonzero value. If so, then that’s the only possible value and it returns.

If not, then the function creates a set of the numbers one through nine. The function proceeds to check different blocking numbers and removes those from this set.

It starts by checking the column and row of the given position. This can be done with a single loop by just alternating which subscript changes.grid[x][index] checks values in the same column, whilegrid[index][y] checks those values in the same row. You can see that you’re usingtest_and_remove() here to simplify the code.

Once those values have been removed from yourpossible set, the function moves on to the small square. This is where thesmall_square() generator you created before comes in handy. You can use it to iterate over each position in the small square, again usingtest_and_remove() to eliminate any known values from yourpossible list.

Once all the known blocking values have been removed from your set, you have the list of allpossible values for that position on that grid.

You might wonder why the code and its description make a point about the position being “on that grid.” In your next function, you’ll see that the program makes many copies of the grid as it tries to solve it.

Solving It

You’ve reached the heart of this solution:solve()! This function is recursive, so a little up-front explanation might help.

The general design ofsolve() is based on testing a single position at a time. For the position of interest, the algorithm gets the list of possible values and then selects those values, one at a time, to be in this position.

For each of these values, it creates a grid with the guessed value in this position. It then calls a function to test for a solution, passing in the new grid and the next position.

It just so happens that the function it calls is itself.

For any recursion, you need a termination condition. This algorithm has four of them:

1. There are no possible values for this position. That indicates the solution it’s testing can’t work.
2. It’s walked to the end of the grid and found a possible value for each position. The puzzle is solved!
3. One of the guesses at this position, when passed back to the solver, returns a solution.
4. It’s tried all possible values at this position and none of them will work.

Let’s look at the code for this and see how it all plays out:

# sudokusolve.pyimportcopydefsolve(start,x,y):temp=copy.deepcopy(start)whileTrue:possible=detect_possible(temp,x,y)ifnotpossible:returnFalsefinished,nextX,nextY=compute_next_position(x,y)iffinished:temp[x][y]=possible[0]returntempiflen(possible)>1:breaktemp[x][y]=possible[0]x=nextXy=nextYforguessinpossible:temp[x][y]=guessresult=solve(temp,nextX,nextY)ifresult:returnresultreturnFalse

The first thing to note in this function is that it makes a.deepcopy() of the grid. It does adeep copy because the algorithm needs to keep track of exactly where it was at any point in the recursion. If the function made only a shallow copy, then every recursive version of this function would use the same grid.

Once the grid is copied,solve() can work with the new copy,temp. A position on the grid was passed in, so that’s the number that this version of the function will solve. The first step is to see what values are possible in this position. As you saw earlier,detect_possible() returns a list of possible values that may be empty.

If there are no possible values, then you’ve hit the first termination condition for the recursion. The function returnsFalse, and the calling routine moves on.

If thereare possible values, then you need to move on and see if any of them is a solution. Before you do that, you can add a little optimization to the code. If there’s only a single possible value, then you can insert that value and move on to the next position. The solution shown does this in a loop, so you can place multiple numbers into the grid without having to recur.

This may seem like a small improvement, and I’ll admit my first implementation did not include this. But some testing showed that this solution was dramatically faster than simply recurring here at the price of more complex code.

Sometimes, of course, there will be multiple possible values for the current position, and you’ll need to decide if any of them will lead to a solution. Fortunately, you’ve already determined the next position in the grid, so you can forgo placing the possible values.

If the next position is off the end of the grid, then the current position is the final one to fill. If you know that there’s at least one possible value for this position, then you’ve found a solution! The current position is filled in and the completed grid is returned up to the calling function.

If the next position is still on the grid, then you loop through each possible value for the current spot, filling in the guess at the current position and then callingsolve() with thetemp grid and the new position to test.

solve() can return only a completed grid orFalse, so if any of the possible guesses returns a result that isn’tFalse, then a result has been found, and that grid can be returned up the stack.

If all possible guesses have been made and none of them is a solution, then the grid that was passed in is unsolvable. If this is the top-level call, then that means the puzzle is unsolvable. If the call is lower in the recursion tree, then it just means that this branch of the recursion tree isn’t viable.

Putting It All Together

At this point, you’re almost through the solution. There’s only one final function left,sudoku_solve():

# sudokusolve.pydefsudoku_solve(input_string):grid=line_to_grid(input_string)answer=solve(grid,0,0)ifanswer:returngrid_to_line(answer)else:return"Unsolvable"

This function does three things:

1. Converts the input string into a grid
2. Callssolve() with that grid to get a solution
3. Returns the solution as a string or"Unsolvable" if there’s no solution

That’s it! You’ve walked through a solution for the sudoku solver problem.

Interview Discussion Topics

The sudoku solver solution you just walked through is a good deal of code for an interview situation. Part of an interview process would likely be to discuss some of the code and, more importantly, some of the design trade-offs you made. Let’s look at a few of those trade-offs.

Recursion

The biggest design decision revolves around using recursion. It’s possible to write a non-recursive solution to any problem that has a recursive solution. Why choose recursion over another option?

This is a discussion that depends not only on the problem but also on the developers involved in writing and maintaining the solution. Some problems lend themselves to rather clean recursive solutions, and some don’t.

In general, recursive solutions will take more time to run and use more memory than non-recursive solutions. But that’s not always true and, more importantly, it’s not alwaysimportant.

Similarly, some teams of developers are comfortable with recursive solutions, while others find them exotic or unnecessarily complex. Maintainability should play into your design decisions as well.

One good discussion to have about a decision like this is around performance. How fast does this solution need to execute? Will it be used to solve billions of puzzles or just a handful? Will it run on a small embedded system with memory constraints, or will it be on a large server?

These external factors can help you decide which is a better design decision. These aregreat topics to bring up in an interview as you’re working through a problem or discussing code. A single product might have places where performance is critical (doing ray tracing on a graphics algorithm, for example) and places where it doesn’t matter at all (such as parsing the version number during installation).

Bringing up topics like this during an interview shows that you’re not only thinking about solving an abstract problem, but you’re also willing and able to take it to the next level and solve a specific problem facing the team.

Readability and Maintainability

Sometimes it’s worth picking a solution that’s slower in order to make a solution that’s easier to work with, debug, and extend. The decision in the sudoku solver challenge to convert the data structure to a grid is one of those decisions.

That design decision likely slows down the program, but unless you’ve measured, you don’t know. Even if it does, putting the data structure into a form that’s natural for the problem can make the code easier to comprehend.

It’s entirely possible to write a solver that operates on the linear strings you’re given as input. It’s likely faster and probably takes less memory, butsmall_square(), among others, will be a lot harder to write, read, and maintain in this version.

Missteps

Another thing to discuss with an interviewer, whether you’re live coding or discussing code you wrote offline, is the mistakes and false turns you took along the way.

This is a little less obvious and can be slightly detrimental, but particularly if you’re live coding, taking a step to refactor code that isn’t right or could be better can show how you work. Few developers can write perfect code the first time. Heck, few developers can writegood code the first time.

Good developers write the code, then go back and refactor it and fix it. For example, my first implementation ofdetect_possible() looked like this:

# sudokusolve.pydeffirst_detect_possible(x,y,grid):print(f"position [{x}][{y}] ={grid[x][y]}")possible=set(range(1,10))# Test horizontalforindex,valueinenumerate(grid[x]):ifindex!=y:ifgrid[x][index]!=0:possible.remove(grid[x][index])# Test verticalforindex,rowinenumerate(grid):ifindex!=x:ifgrid[index][y]!=0:possible.remove(grid[index][y])print(possible)

Ignoring that it doesn’t consider thesmall_square() information, this code can be improved. If you compare this to the final version ofdetect_possible() above, you’ll see that the final version uses a single loop to test both the horizontaland the vertical dimensions.

Wrapping Up

That’s your tour through a sudoku solver solution. There’s more information available onformats for storing puzzles and ahuge list of sudoku puzzles you can test your algorithm on.