Applied Computational Thinking Problems

Applied Computational Thinking Problems

1. Problem 1 – Using Python to analyze historical speeches

History is quite fascinating, and there are many reasons why we would look at writing algorithms to evaluate historical data and contexts.

For this problem, we want to analyze some historical text. In particular, we are going to take a look at Abraham Lincoln’s second inaugural speech. Our goal is to find some frequencies of words. There are many reasons why we’d want to perform some straightforward text analysis, especially for historical texts. We may want to compare them, understand underlying themes, and so on. For our algorithm, we are going to use a fairly simple design using the nltk package.

Because the installation of some of the components is a bit different to what we’ve done so far, we’ll provide some information in case your packages have not been installed.

pip install nltk

Because our problem is fairly simple, we’ll skip much of the computational thinking process for this particular section. We are only trying to get frequencies of words used in the speech. So let’s dive directly into the algorithm and see how we’ll use the nltk package to get what we need, including a visual representation of the data:

1. First, we’ll need to import nltk and the word_tokenize function. The word_tokenize function allows us to divide the speech into individual words and/or punctuation marks. We’ll need the speech text. In this case, the speech is copied into the algorithm. You could potentially import the file into the algorithm and do it that way. The sent_tokenize function is short for sentence tokenization. In the same way as word tokenization breaks down the text by words and punctuation marks, the sentence tokenization function allows breaking the text into full sentences. The output would contain sentences in a list separated by commas.

The following algorithm contains everything we need in order to do the analysis of Abraham Lincoln’s second inaugural speech:

import nltk
from nltk.tokenize import sent_tokenize, word_tokenize
text = 'Fellow-Countrymen: At this second appearing to take the oath of the Presidential office there is less occasion for an extended address than there was at the first. Then a statement somewhat in detail of a course to be pursued seemed fitting and proper. Now, at the expiration of four years, during which public declarations have been constantly called forth on every point and phase of the great contest which still absorbs the attention and engrosses the energies of the nation, little that is new could be presented. The progress of our arms, upon which all else chiefly depends, is as well known to the public as to myself, and it is, I trust, reasonably satisfactory and encouraging to all. With high hope for the future, no prediction in regard to it is ventured. On the occasion corresponding to this four years ago all thoughts were anxiously directed to an impending civil war. All dreaded it, all sought to avert it. While the inaugural address was being delivered from this place, devoted altogether to saving the Union without war, urgent agents were in the city seeking to destroy it without war—seeking to dissolve the Union and divide effects by negotiation. Both parties deprecated war, but one of them would make war rather than let the nation survive, and the other would accept war rather than let it perish, and the war came. One-eighth of the whole population were colored slaves, not distributed generally over the Union, but localized in the southern part of it. These slaves constituted a peculiar and powerful interest. All knew that this interest was somehow the cause of the war. To strengthen, perpetuate, and extend this interest was the object for which the insurgents would rend the Union even by war, while the Government claimed no right to do more than to restrict the territorial enlargement of it. Neither party expected for the war the magnitude or the duration which it has already attained. Neither anticipated that the cause of the conflict might cease with or even before the conflict itself should cease. Each looked for an easier triumph, and a result less fundamental and astounding. Both read the same Bible and pray to the same God, and each invokes His aid against the other. It may seem strange that any men should dare to ask a just God\’s assistance in wringing their bread from the sweat of other men\’s faces, but let us judge not, that we be not judged. The prayers of both could not be answered. That of neither has been answered fully. The Almighty has His own purposes. \“Woe unto the world because of offenses; for it must needs be that offenses come, but woe to that man by whom the offense cometh.\” If we shall suppose that American slavery is one of those offenses which, in the providence of God, must needs come, but which, having continued through His appointed time, He now wills to remove, and that He gives to both North and South this terrible war as the woe due to those by whom the offense came, shall we discern therein any departure from those divine attributes which the believers in a living God always ascribe to Him? Fondly do we hope, fervently do we pray, that this mighty scourge of war may speedily pass away. Yet, if God wills that it continue until all the wealth piled by the bondsman\’s two hundred and fifty years of unrequited toil shall be sunk, and until every drop of blood drawn with the lash shall be paid by another drawn with the sword, as was said three thousand years ago, so still it must be said \“the judgments of the Lord are true and righteous altogether.\” With malice toward none, with charity for all, with firmness in the right as God gives us to see the right, let us strive on to finish the work we are in, to bind up the nation\’s wounds, to care for him who shall have borne the battle and for his widow and his orphan, to do all which may achieve and cherish a just and lasting peace among ourselves and with all nations.'

1. Now that we’ve defined the text that we want analyzed, as shown in the preceding code snippet, we can tell the algorithm that we want to tokenize the text, that is, we want it divided into words. The algorithm will print out a list that contains each individual word or punctuation symbol separated by a comma, as shown in the following code:

tokenized_word = word_tokenize(text)
print(tokenized_word)

1. After we have our list of words, we want to get the frequency distribution of the words. To do so, we’ll import the package from nltk.probability, as shown in the following code snippet:

from nltk.probability import FreqDist
fdist = FreqDist(tokenized_word)
print(fdist)
fdist.most_common(2)

1. Once we have the distribution, we’ll want a visual plot of this data, so we’ll use matplotlib to create our distribution plot, as shown in the following code snippet:

import matplotlib.pyplot as plt
fdist.plot(30, cumulative = False)
plt.show()

That’s the entire algorithm we’ll need. When we run the algorithm, this is what our output looks like:

['Fellow-Countrymen', ':', 'At', 'this', 'second',
'appearing', 'to', 'take', 'the', 'oath', 'of', 'the',
'Presidential', 'office', 'there', 'is', 'less',
'occasion', 'for', 'an', 'extended', 'address',
'than', 'there', 'was', 'at', 'the', 'first', '.',
'Then', 'a', 'statement', 'somewhat', 'in', 'detail',
'of', 'a', 'course', 'to', 'be', 'pursued', 'seemed',
'fitting', 'and', 'proper', '.', 'Now', ',', 'at',
'the', 'expiration', 'of', 'four', 'years', ',',
'during', 'which', 'public', 'declarations', 'have',
'been', 'constantly', 'called', 'forth', 'on', 'every',
'point', 'and', 'phase', 'of', 'the', 'great', 'contest',
'which', 'still', 'absorbs', 'the', 'attention', 'and',
'engrosses', 'the', 'energies', 'of', 'the', 'nation',
',', 'little', 'that', 'is', 'new', 'could', 'be',
'presented', '.', 'The', 'progress', 'of', 'our',
'arms', ',', 'upon', 'which', 'all', 'else', 'chiefly',
'depends', ',', 'is', 'as', 'well', 'known', 'to', 'the',
'public', 'as', 'to', 'myself', ',', 'and', 'it', 'is',
',', 'I', 'trust', ',', 'reasonably', 'satisfactory',
'and', 'encouraging', 'to', 'all', '.', 'With', 'high',
'hope', 'for', 'the', 'future', ',', 'no', 'prediction',
'in', 'regard', 'to', 'it', 'is', 'ventured', '.', 'On',
'the', 'occasion', 'corresponding', 'to', 'this', 'four',
'years', 'ago', 'all', 'thoughts', 'were', 'anxiously',
'directed', 'to', 'an', 'impending', 'civil', 'war',
'.', 'All', 'dreaded', 'it', ',', 'all', 'sought',
'to', 'avert', 'it', '.', 'While', 'the', 'inaugural',
'address', 'was', 'being', 'delivered', 'from', 'this',
'place', ',', 'devoted', 'altogether', 'to', 'saving',
'the', 'Union', 'without', 'war', ',', 'urgent',
'agents', 'were', 'in', 'the', 'city', 'seeking',
'to', 'destroy', 'it', 'without', 'war—seeking',
'to', 'dissolve', 'the', 'Union', 'and', 'divide',
'effects', 'by', 'negotiation', '.', 'Both', 'parties',
'deprecated', 'war', ',', 'but', 'one', 'of', 'them',
'would', 'make', 'war', 'rather', 'than', 'let', 'the',
'nation', 'survive', ',', 'and', 'the', 'other', 'would',
'accept', 'war', 'rather', 'than', 'let', 'it', 'perish',
',', 'and', 'the', 'war', 'came', '.', 'One-eighth',
'of', 'the', 'whole', 'population', 'were', 'colored',
'slaves', ',', 'not', 'distributed', 'generally', 'over',
'the', 'Union', ',', 'but', 'localized', 'in', 'the',
'southern', 'part', 'of', 'it', '.', 'These', 'slaves',
'constituted', 'a', 'peculiar', 'and', 'powerful',
'interest', '.', 'All', 'knew', 'that', 'this',
'interest', 'was', 'somehow', 'the', 'cause', 'of',
'the', 'war', '.', 'To', 'strengthen', ',', 'perpetuate',
',', 'and', 'extend', 'this', 'interest', 'was', 'the',
'object', 'for', 'which', 'the', 'insurgents', 'would',
'rend', 'the', 'Union', 'even', 'by', 'war', ',',
'while', 'the', 'Government', 'claimed', 'no', 'right',
'to', 'do', 'more', 'than', 'to', 'restrict', 'the',
'territorial', 'enlargement', 'of', 'it', '.', 'Neither',
'party', 'expected', 'for', 'the', 'war', 'the',
'magnitude', 'or', 'the', 'duration', 'which', 'it',
'has', 'already', 'attained', '.']

1. Recall that word tokenization only included the truncated text. However, the frequency information and the plot that follow are for the entire speech. The ch15_historicalTextAnalysis.py GitHub file includes the full speech:

<FreqDist with 365 samples and 782 outcomes>

The following screenshot shows the frequency distribution visual plot for this algorithm:

Once we have this information, we can start to look more closely at the words that were used most frequently. When working with this kind of analysis, you may want to consider removing some of the words, such as to, a, and the, as they would be irrelevant to our analysis. However, words such as years and Union may be relevant to our analysis.

There are many adjustments that can be made for this algorithm, but for now, we’ve managed to at least get a frequency distribution plot for a historical speech. Now, we’ll move on to the next problem.

Full code:

import nltk
from nltk.tokenize import sent_tokenize, word_tokenize
text = 'Fellow-Countrymen: At this second appearing to take the oath of the Presidential office there is less occasion for an extended address than there was at the first. Then a statement somewhat in detail of a course to be pursued seemed fitting and proper. Now, at the expiration of four years, during which public declarations have been constantly called forth on every point and phase of the great contest which still absorbs the attention and engrosses the energies of the nation, little that is new could be presented. The progress of our arms, upon which all else chiefly depends, is as well known to the public as to myself, and it is, I trust, reasonably satisfactory and encouraging to all. With high hope for the future, no prediction in regard to it is ventured. On the occasion corresponding to this four years ago all thoughts were anxiously directed to an impending civil war. All dreaded it, all sought to avert it. While the inaugural address was being delivered from this place, devoted altogether to saving the Union without war, urgent agents were in the city seeking to destroy it without war—seeking to dissolve the Union and divide effects by negotiation. Both parties deprecated war, but one of them would make war rather than let the nation survive, and the other would accept war rather than let it perish, and the war came. One-eighth of the whole population were colored slaves, not distributed generally over the Union, but localized in the southern part of it. These slaves constituted a peculiar and powerful interest. All knew that this interest was somehow the cause of the war. To strengthen, perpetuate, and extend this interest was the object for which the insurgents would rend the Union even by war, while the Government claimed no right to do more than to restrict the territorial enlargement of it. Neither party expected for the war the magnitude or the duration which it has already attained. Neither anticipated that the cause of the conflict might cease with or even before the conflict itself should cease. Each looked for an easier triumph, and a result less fundamental and astounding. Both read the same Bible and pray to the same God, and each invokes His aid against the other. It may seem strange that any men should dare to ask a just God\’s assistance in wringing their bread from the sweat of other men\’s faces, but let us judge not, that we be not judged. The prayers of both could not be answered. That of neither has been answered fully. The Almighty has His own purposes. \“Woe unto the world because of offenses; for it must needs be that offenses come, but woe to that man by whom the offense cometh.\” If we shall suppose that American slavery is one of those offenses which, in the providence of God, must needs come, but which, having continued through His appointed time, He now wills to remove, and that He gives to both North and South this terrible war as the woe due to those by whom the offense came, shall we discern therein any departure from those divine attributes which the believers in a living God always ascribe to Him? Fondly do we hope, fervently do we pray, that this mighty scourge of war may speedily pass away. Yet, if God wills that it continue until all the wealth piled by the bondsman\’s two hundred and fifty years of unrequited toil shall be sunk, and until every drop of blood drawn with the lash shall be paid by another drawn with the sword, as was said three thousand years ago, so still it must be said \“the judgments of the Lord are true and righteous altogether.\” With malice toward none, with charity for all, with firmness in the right as God gives us to see the right, let us strive on to finish the work we are in, to bind up the nation\’s wounds, to care for him who shall have borne the battle and for his widow and his orphan, to do all which may achieve and cherish a just and lasting peace among ourselves and with all nations.'
tokenized_word = word_tokenize(text)
print(tokenized_word)

from nltk.probability import FreqDist
fdist = FreqDist(tokenized_word)
print(fdist)
fdist.most_common(2)

import matplotlib.pyplot as plt
fdist.plot(30, cumulative = False)
plt.show()

2. Problem 2 – Using Python to write stories

Let’s look at a fairly simple problem. In this section, we want to create an algorithm that produces a story based on input from a user. We can make this as simple as we want, or add some options. But let’s dig into what this is.

a. Defining, decomposing, and planning a story

First of all, what is it we’re trying to create? Well, a story. Because of the nature of this problem, we’re going to start in reverse, with a sample of the output we want to achieve, that is, a sample story. Let’s take a look at a quick story generated by our algorithm before we actually get into the algorithm:

There once was a citizen in the town of Narnia, whose name was
Malena. Malena loved to hang with their trusty dog, King Kong.
You could always see them strolling through the market in the
morning, wearing their favorite blue attire.

The preceding output was created by an algorithm that substituted names, locations, time of day, pet, and pet name. It’s a short story, but this is something that can be used in much wider applications, such as using input to write social media posts, and filling in information for things such as invitations, forms, and more.

So let’s work backward a bit to write our algorithm. And why did I start at the end this time? Well, in this case, we know what we want from the end result. You could write your story. You could have an example of that wedding invitation template you need to fill in, or the form. Now we have to figure out how to get the input and then output what we wanted.

From the story shown, here are the things we can get original input for:

• Character name
• Town name
• Type of pet
• Name of pet
• Part of town visited
• Time of day
• Favorite color

When we write our algorithm, we’ll need to get all the aforementioned inputs.

1. We will need inputs from the user, so we want to use a print statement and input requests that include instructions for what is needed:

print('Help me write a story by answering some questions.')
name = input('What name would you like to be known by? ')
location = input('What is your favorite city, real or imaginary? ')
time = input('Is this happening in the morning or afternoon? ')
color = input('What is your favorite color? ')
town_spot = input('Are you going to the market, the library, or the park? ')
pet = input('What kind of pet would you like as your companion? ')
pet_name = input('What is your pet\'s name? ')

The preceding code snippet grabs all the inputs from the user so we can write our story.

1. Once we have those, we have to print our story. Notice that we wrote it in simple terms, using %s so we could replace it with the corresponding inputs. We also used backslashes so that we can see our code on multiple lines, rather than have it in one long line:

print('There once was a citizen in the town of %s, whose name was %s. %s loved to hang with their trusty %s, %s.' % (location, name, name, pet, pet_name))
print('You could always see them strolling through the %s in the %s, wearing their favorite %s attire.' % (town_spot, time, color))

Let’s run that code one more time and see what our story says now:

Help me write a story by answering some questions.
What name would you like to be known by? Azabache
What is your favorite city, real or imaginary? Rincon
Is this happening in the morning or afternoon? afternoon
What is your favorite color? magenta
Are you going to the market, the library, or the park?
library
What kind of pet would you like as your companion? dog
What is your pet's name? Luna
There once was a citizen in the town of Rincon, whose
name was Azabache. Azabache loved to hang with their trusty dog, Luna.
You could always see them strolling through the library
in the afternoon, wearing their favorite magenta attire.

Notice that details such as character and settings have changed. In an education learning environment, such a simple algorithm can be a great tool for showing students how to interact with stories and identify key information in them.

While this is a three-sentence story, these algorithms can be much more complex, providing an opportunity to write fantastic original stories with user input. If you wanted to try some of this out, you could even put conditions for which phrases you would use based on some of the input, such as changing the sentences used based on the length of the name entered, for example. Have some fun with the code and writing some stories!

Full code:

print('Help me write a story by answering some questions. ')
name = input('What name would you like to be known by? ')
location = input('What is your favorite city, real or imaginary? ')
time = input('Is this happening in the morning or afternoon? ')
color = input('What is your favorite color? ')
town_spot = input('Are you going to the market, the library, or the park? ')
pet = input('What kind of pet would you like as your companion? ')
pet_name = input('What is your pet\'s name? ')

print('There once was a citizen in the town of %s, whose name was %s. %s loved to hang \
with their trusty %s, %s.' % (location, name, name, pet, pet_name))
print('You could always see them strolling through the %s \
in the %s, wearing their favorite %s attire.' % (town_spot, time, color))

3. Using Python to find most efficient route

For this problem, when learning about algorithms, we will use a common algorithm—the Travelling Salesman Problem (TSP). Let’s set up the problem itself.

A salesman needs to travel to a set number of cities or locations. Let’s say the salesman has 10 locations to go to. They could go to those 10 locations in a lot of different orders.

Our goal with this algorithm is to create the best possible, most efficient route to hit those locations.

Note that for this particular scenario, as we will do in the next problem, we’ll employ straightforward analysis by using the four elements of the computational thinking process.

a. Defining the problem (TSP)

This problem is a little more complex than how it appears initially. Think of it this way. If we have 10 destinations and we are calculating round-trip permutations to check the fastest routes, we’re left with more than 300,000 possible permutations and combinations. As a reminder, a permutation takes order into consideration, while a combination does not.

For example, the numbers 3344 and 3434 are two different permutations. However, they are only counted as one combination because the order of the numbers does not matter.

But back to our problem. All we need to know is that we want to create an algorithm that will take us to our destinations in the most efficient way. We have to identify the cities to be visited and identify the way we’ll travel as follows:

• There are five cities in total, namely, New York (NYC), Philadelphia, Baltimore, Chicago, and Cleveland.
• We will use one vehicle because we’re using TSP instead of a vehicle routing problem (VRP).
• The first city is 0, which is NYC. The distance between NYC and itself is 0.

b. Recognizing the pattern (TSP)

For each city, there will be a total of five distances, with the distance to itself equal to 0. We are going to need an array, or lists, for all the distances for each city. We will need to create a model in order to access the data in our algorithm. We’ll look at that while designing the algorithm. First, let’s talk about generalizing the pattern a bit.

c. Generalizing (TSP)

For this particular problem, we’ll enter the cities manually into the algorithm itself. One thing you may want to consider is how to get input from a user in order to create the arrays necessary with the distances.

You could also create a database for the distances between major cities that you can access from a .csv file so that the data for cities that a person inputs can be found there, which can then be added to our model. There are many additions to this particular algorithm and this isn’t a problem that can be solved in just one way. For now, we’re going to stay with a defined set of cities so that we can create our algorithm.

d. Designing the algorithm (TSP)

It’s time to see what we’ve been talking about. Let’s start with NYC and construct that array first. The other arrays are created in the same way. All distances are in miles and have been approximated and rounded based on Google Maps data, given as follows:

• Distance from NYC to NYC is 0.
• Distance from NYC to Philadelphia is 95.
• Distance from NYC to Baltimore is 192.
• Distance from NYC to Chicago is 789.
• Distance from NYC to Cleveland is 462

The following table shows the distances from each city to each other and itself:

So, as you can in the preceding table, if we were to write these distances as an array, we would use the following code: [0, 95, 192, 789, 462]

For Philadelphia, we would have the following array: [95, 0, 105, 759, 431]

For Baltimore, we would have the following array: [192, 105, 0, 701, 374]

For Chicago, we would have the following array: [789, 759, 701, 0, 344]

And finally, for Cleveland, we would have the following array: [462, 431, 374, 344, 0]

Note that we will give indexes to each of the cities in order to identify them. NYC is 0, Philadelphia is 1, Baltimore is 2, Chicago is 3, and Cleveland is 4. Let’s see what the algorithm looks like for this problem (note that the OR-Tools library is used to optimize vehicle routes, linear programming, constraint programming, and more):

1. First, let’s start by importing the packages and libraries we’ll need.

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

Remember that this algorithm would need to get a new distance matrix if you are planning to visit more cities and/or different cities. That is the only piece of the code you’d need to alter. The snippet of code that you will need to adjust each time is the matrix under create_data_model(), as shown in the following code snippet:

# Create data model.
def create_data_model():
    data = {}
    data['distance_matrix'] = [
            [0, 95, 192, 789, 462],
            [95, 0, 105, 759, 431],
            [192, 105, 0, 701, 374],
            [789, 759, 701, 0, 344],
            [462, 431, 374, 344, 0],
            ]
    data['num_vehicles'] = 1
    data['depot'] = 0
return data

1. After we’ve defined our data model, we’ll need to print a solution. The following function provides that information:

# Provide solution as output - print to console
def print_solution(manager, routing, solution):
    print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route for vehicle 0:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Route distance: {}miles\n'.format(route_distance)

As you can see from the preceding code, we are creating a function so that we can print the solutions based on our arrays and the distances in those arrays. Recall that you will identify the point of origin, that is, the city you’re leaving from. Then we run the algorithm to gather the information and create our print statement.

1. Finally, we’ll need to define our main() function in order to run our algorithm. The main() function tells the algorithm to go ahead and create that data model we had defined, and then store it as data. We then create the routing model to find our solution. Take a look at the following code snippet:

def main():    
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    solution = routing.SolveWithParameters(search_parameters)

    if solution:
        print_solution(manager, routing, solution)

if __name__ == '__main__':
    main()

The preceding code shows how we define our main() function. As a note, a main() function can be named anything we want. When using multiple functions, we sometimes use main() to identify the function that will be outputting what we originally wanted from the algorithm. For this problem, we’re creating a main() function that will identify the best route for our travels.

1. Now let’s take a look at what we get for our output when we run this code. The code provides us with the Objective total of miles and the route we should take for the trip. Here’s the output:

Objective: 1707 miles
Route for vehicle 0:
0 -> 1 -> 2 -> 4 -> 3 -> 0

As you can see, our trip from NYC and going back to NYC would be most efficient if we followed the route in this order: NYC | Philadelphia | Baltimore | Cleveland | Chicago | NYC.

This is not the only approach for the travel problem. It is also not necessarily the most user-friendly approach if we wanted to run this multiple times a day, for example, for different travelers. To do that, you’d want to automate a lot more of this, as mentioned earlier in the example. Some things you might consider are as follows:

• Being able to input cities
• Having a calculator that grabs information to determine distances
• Using an automated process for creating the distance matrix

Full code:

from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
# Create data model.
def create_data_model():
    data = {}
    data['distance_matrix'] = [
        [0, 95, 192, 789, 462],
        [95, 0, 105, 759, 431],
        [192, 105, 0, 701, 374],
        [789, 759, 701, 0, 344],
        [462, 431, 374, 344, 0],
    ]  
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data
# Provide solution as output - print to console
def print_solution(manager, routing, solution):
    print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route for vehicle 0:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Route distance: {}miles\n'.format(route_distance)

def main():    
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    solution = routing.SolveWithParameters(search_parameters)

    if solution:
        print_solution(manager, routing, solution)

if __name__ == '__main__':
    main()

4. Problem 4 – Using Python for cryptography

Cryptography is what we use to code and decode messages. For this problem, we’re going to use some of the packages available in Python to encrypt and decode information.

Note that for this particular scenario, we’ll use the straightforward analysis from using the four elements of the computational thinking process. While we don’t always follow them exactly, this particular problem lends itself to a fairly straightforward use.

a. Defining the problem (cryptography)

You are working on a classified project and need to encrypt your information to maintain its safety.

b. Recognizing the pattern (cryptography)

Python has a cryptography package that can be installed, much like when we installed other libraries, such as Pandas and NumPy. In our problem, one of the main things we need to know is that we may need to continue to encrypt messages. We may also want to decode messages that we receive, but we are going to focus on the encryption side of things first.

c. Generalizing (cryptography)

When we design our algorithm, we’ll want something we can continue to use throughout the life of our project with little effort. That is, any time we want to encrypt a new message, we can run the algorithm and input the message rather than add the message itself to the algorithm body every time. This is the generalized pattern for our particular problem. That means we’re ready to design.

d. Designing the algorithm (cryptography)

To write our algorithm, let’s first take a look at what we’ll need to do:

1. Define the letters.
2. Change all the letters to lowercase to run our algorithm.
3. Define the required functions—encryption, decoding, and main.
4. Call the cryptography main function.

Full code:

LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
LETTERS = LETTERS.lower()

def encrypt(message, key):
    encryptedM = ''
    for letts in message:
        if letts in LETTERS:
            num = LETTERS.find(letts)
            num += key
            encryptedM +=  LETTERS[num]

    return encryptedM

def decode(message, key):
    decodedM = ''
    for chars in message:
        if chars in LETTERS:
            num = LETTERS.find(chars)
            num -= key
            decodedM +=  LETTERS[num]

    return decodedM

def main():
    message = input('What message do you need to encrypt or decrypt? ')
    key = int(input('Enter the key, numbered 1-26: '))
    choice = input('Do you want to encrypt or decode? Type E for encrypt or D for decode: ')

    if choice.lower().startswith('e'):
        print(encrypt(message, key))
    else:
        print(decode(message, key))

if __name__ == '__main__':
    main()

5. Problem 5 - Using Python in cybersecurity

For this problem, we’ve decided to perform a fairly short cybersecurity check. First, let’s talk about cybersecurity. The market for cybersecurity is expected to grow by 10% by 2027, according to a Grand View Research report.

Translating that to the job market is a little tricky. Currently in the United States, for example, there are more cybersecurity needs for the market than people or jobs available. That job market growth is expected to be slightly above 30% between 2018 and 2028. So learning a bit about cybersecurity and cryptography won’t hurt.

For this particular problem, we are going to explore a few things. First, let’s talk about hashing . In cybersecurity, hashing means those really long strings of numbers and letters that replace things such as passwords. For example, if you entered a password of password1 (please don’t do that, never use password as a password), the hashing process would replace it with something that looks more like this:

27438d623d9e09d7b0f8083b9178b5bb8ff8bc321fee518af
4466f6aadb68a8f:100133bfdbff492cbc8f5d17af46adab

When we are creating cryptography algorithms, we have to add random data, which we call salts . Salts just provide additional input and help us make passwords more secure when storing them.

When we use hashing in Python, we can use the uuid library. UUID stands for Universal Unique Identifier. The uuid library is used when we want to generate random, 128-bit objects as IDs. But what are we really talking about?

Full code:

import uuid
import hashlib

def hash_pwd(password):
    salt = uuid.uuid4().hex 
    return hashlib.sha1(salt.encode() + password.encode()).hexdigest() + ':' + salt

def check_pwd(hashed_pwd, user_pwd):
    password, salt = hashed_pwd.split(':')
    return password == hashlib.sha1(salt.encode() + user_pwd.encode()).hexdigest()

new_pwd = input('Enter new password: ')
hashed_pwd = hash_pwd(new_pwd)
print('Hashed password: ' + hashed_pwd)
confirm_pwd = input('Confirm password: ')

if check_pwd(hashed_pwd, confirm_pwd):
    print('Confirmed!')
else:
    print('Please try again')

6. Problem 6 – Using Python to create a chatbot

Full code:

main.py

import nltk
import json
import pickle
import numpy as np

nltk.download('punkt')
nltk.download('wordnet')
from nltk.stem import WordNetLemmatizer
lemmatizer = WordNetLemmatizer()

from keras.models import Sequential
from keras.optimizers import SGD
from keras.layers import Activation, Dense, Dropout
import random

# Upload intents file and create our lists
words=[]
classes = []
doc = []
ignore_words = ['?', '!', ',', '.']
data_words = open(r'C:\...\intents.json').read()
intents = json.loads(data_words)

for intent in intents['intents']:
    for pattern in intent['patterns']:

        # Tokenize all the words (separate them)
        w = nltk.word_tokenize(pattern)
        words.extend(w)
        # Add all the words into doc 
        doc.append((w, intent['tag']))

        # Add the classes
        if intent['tag'] not in classes:
            classes.append(intent['tag'])
print(doc)      

# lemmatization      

words = [lemmatizer.lemmatize(w.lower()) for w in words if w not in ignore_words]
words = sorted(list(set(words)))


classes = sorted(list(set(classes)))

pickle.dump(words,open('words.pkl','wb'))
pickle.dump(classes,open('classes.pkl','wb'))       

# Training
training = []
output_empty = [0] * len(classes)
for doc in doc:
    # Initialize bag of words
    bag = []
    # Create list of words
    pattern_words = doc[0]
    # Word lemmatization
    pattern_words = [lemmatizer.lemmatize(word.lower()) for word in pattern_words]
    for w in words:
        bag.append(1) if w in pattern_words else bag.append(0)   
    output_row = list(output_empty)
    output_row[classes.index(doc[1])] = 1

    training.append([bag, output_row])
# Create np array
random.shuffle(training)
training = np.array(training)
# Create training and testing lists
train_x = list(training[:,0])
train_y = list(training[:,1])

# Create the model
model = Sequential()
model.add(Dense(128, input_shape=(len(train_x[0]),), activation='relu'))
model.add(Dropout(0.5))
model.add(Dense(64, activation='relu'))
model.add(Dense(35, activation='relu'))
model.add(Dense(len(train_y[0]), activation='softmax'))

# Compile the model
sgd = SGD(lr=0.01, decay=1e-6, momentum=0.9, nesterov=True)
model.compile(loss='categorical_crossentropy', optimizer=sgd, metrics=['accuracy'])

# Save the model
hist = model.fit(np.array(train_x), np.array(train_y), epochs=150, batch_size=10, verbose=1)
model.save('Mychatbot_model.h5', hist)

from keras.models import load_model
model = load_model('Mychatbot_model.h5')
import json
import random
intents = json.loads(open('intents.json').read())
words = pickle.load(open('words.pkl','rb'))
classes = pickle.load(open('classes.pkl','rb'))

# Define chatbot functions
def clean_up_sentence(sentence):
    sentence_words = nltk.word_tokenize(sentence)
    sentence_words = [lemmatizer.lemmatize(word.lower()) for word in sentence_words]
    return sentence_words

def bow(sentence, words, show_details=True):
    sentence_words = clean_up_sentence(sentence)
    bag = [0]*len(words)
    for s in sentence_words:
        for i,w in enumerate(words):
            if w == s:
                bag[i] = 1
    return(np.array(bag))

def predict_class(sentence, model):
    p = bow(sentence, words,show_details=False)
    res = model.predict(np.array([p]))[0]
    ERROR_THRESHOLD = 0.25
    results = [[i,r] for i,r in enumerate(res) if r>ERROR_THRESHOLD]
    results.sort(key=lambda x: x[1], reverse=True)
    return_list = []
    for r in results:
        return_list.append({"intent": classes[r[0]], "probability": str(r[1])})
    return return_list

def getResponse(ints, intents_json):
    tag = ints[0]['intent']
    list_of_intents = intents_json['intents']
    for i in list_of_intents:
        if(i['tag']== tag):
            result = random.choice(i['responses'])
            break
    return result

def chatbot_response(msg):
    ints = predict_class(msg, model)
    res = getResponse(ints, intents)
    return res

import tkinter
from tkinter import *

def send():
    msg = EntryBox.get("1.0",'end-1c').strip()
    EntryBox.delete("0.0",END)

    if msg != '':
        ChatLog.config(state=NORMAL)
        ChatLog.insert(END, "Me: " + msg + '\n\n')
        ChatLog.config(foreground="#3E4149", font=("Arial", 12 ))

        res = chatbot_response(msg)
        ChatLog.insert(END, "ChatBot: " + res + '\n\n')

        ChatLog.config(state=DISABLED)
        ChatLog.yview(END)


base = Tk()
base.title("Chat with Customer Service")
base.geometry("400x500")
base.resizable(width=FALSE, height=FALSE)

# Create ChatBot window
ChatLog = Text(base, bd=6, bg="white", height="8", width="70", font="Calibri")

ChatLog.config(state=DISABLED)

# Scrollbar
scrollbar = Scrollbar(base, command=ChatLog.yview, cursor="arrow")

# Create Send button
SendButton = Button(base, font=("Calibri",12,'bold'), text="Send", width="15", height=5,
                    bd=0, bg="pink", activebackground="light green",fg='black',
                    command= send )

EntryBox = Text(base, bd=0, bg="white",width="29", height="5", font="Arial")

scrollbar.place(x=376,y=6, height=386)
ChatLog.place(x=6,y=6, height=386, width=370)
EntryBox.place(x=128, y=401, height=90, width=265)
SendButton.place(x=6, y=401, height=90)

base.mainloop()

intents.json

{"intents": [
        {"tag": "greeting",
         "patterns": ["Hi", "How are you", "Is anyone there?", "Hello", "Good day"],
         "responses": ["Hello, thanks for visiting", "Good to see you again", "Hi there, how can I help?"],
         "context_set": ""
        },
        {"tag": "goodbye",
         "patterns": ["Bye", "See you later", "Goodbye"],
         "responses": ["See you later, thanks for visiting", "Have a nice day", "Bye! Come back again soon."]
        },
        {"tag": "thanks",
         "patterns": ["Thanks", "Thank you", "That's helpful"],
         "responses": ["Happy to help!", "Any time!", "My pleasure"]
        },
        {"tag": "hours",
         "patterns": ["What hours are you open?", "What are your hours?", "When are you open today?" ],
         "responses": ["We're open every day 8am-10pm. Is there anything else I can help you with?", "Our hours are 8am-10pm every day."]
        },
        {"tag": "payments",
         "patterns": ["Do you take credit cards?", "Do you accept Mastercard?", "Are you cash only?" ],
         "responses": ["We accept both VISA and Mastercard ", "We accept most major credit cards"]
        },
        {"tag": "opentoday",
         "patterns": ["Are you open today?", "When do you open today?", "What are your hours today?"],
         "responses": ["We're open every day from 8am-10pm", "Our hours are 8am-10pm every day"]
        }
   ]
}