Does ARTIFICIAL INTELLIGENCE Sometimes Make You Feel Stupid?

Learn how to dominate Artificial Intelligence.

Photo by Lenin Estrada on Unsplash

Hey Guys, Today I am introducing an ensemble of the basic AI programs that will aid you in kick starting your adventure into the programming fundamentals of Artificial Intelligence.

I have a 100 day challenge going on. Where I solve 1 programming question each day that has been asked in previous interviews.

All these problems are taken from the following e-book. 🎓

Now without further adieu,

Algorithms that we will be looking into are:

1. Uninformed Search
2. Informed Search
3. Posterior Probability
4. Bayesian Networks

1) Uninformed Search

Aim🏹

Given a list of cities with their distances from each other find the shortest path distance when source and destination city is given.

Input📥

A data file which will contain all the distances between cities and a source destination.

Output📤

The path followed to get to destination with minimum distance or cost.

Algorithm👩‍🎓

1. Push the starting city in the queue.
2. Push all its neighbouring cities in the queue and sort them with their distances.
3. Dequeue the first element and If the node pushed in is goal state print it and stop program.
4. If not then keep repeating the process till the queue is not empty.

Code👇

Programmed by : Architha Harinath

Explanation🤩

1. The function has filename as a parameter which is given when function is called.
2. We are using default dictionaries edges, wts and edge_wt where wts dictionary has edge weights as the key and value is the cities having that distance
3. The edge_wt has the 2 cities as key with their respective distance as weight its value.
4. The edges dictionary stores the neighbours of cities.
5. In input1 we read the input file and store the cities in src and dest and distances between them in wt.
6. After reading them we are returning the edges and edge_wt dictionaries.

Calculation

Explanation 🕵️‍♂️

We append the src with Dist 0 in the list fifo and its parent as None with Dist 0 along with its child in parent list.

The while loop goes until the fifo list is not empty.

• The cost and name of city is stored in cost1 and node1 variable and the count var is incremented.
• If node1 is same as goal then the count is displayed and the distance from the fifo list is displayed.
• We sort the parent list according to the distances.
• The current node is appended in parent1 list.
• Else we pop the first element of fifo list.
• If the node is not in visited list then use a for loop to go through the edges dictionary with node1 as key and in results store the distance between node1 and I in the for loop for the edges_wt dictionary as key having Dist as the value.
• Then calculating the total cost by taking the cost1 from node1 and result list and appending in fifo list as well as parent list.
• Sorting the fifo list as to take the min distance first and then appending the node in visited.

Explanation

In the command line the first argument should be the input file name,source city and destination city.

Calling storing_input(filename)

Then calling ucs() with src, dest and edges , edge_wt as parameters returned from storing_input().

2) Informed Search

Aim🏹

Given a list of cities with their distances from each other find the shortest path distance when source and destination city and heuristic distance file is given(A star) i.e. informed search.

Input📥

A data file which will contain all the distances between cities and asource destination and another data file which has city name and heuristic distances.

Output📤

The path followed to get to destination with minimum distance or cost.

Algorithm👨‍🎓

1. Push the starting city in the queue.
2. Push all its neighboring cities in the queue and sort them with their distances taking in account the heuristic distances of each city.
3. Dequeue the first element and If the node pushed in is goal state print it and stop program.
4. If not then keep repeating the process till the queue is not empty.

Program 👇

Explanation 🕵️‍♀️

The function has filename as a parameter which is given when function is called.

We are using default dictionaries edges, wts and edge_wt where wts dictionary has edge weights as the key and value is the cities having that distance.

The edge_wt has the 2 cities as key with their respective distance as weight its value.

The edges dictionary stores the neighbor of cities.

In input1 we read the input file and store the cities in src and dest and distances between them in wt.

After reading them we are returning the edges and edge_wt dictionaries.

Explanation

The function has filename1 as a parameter which is given when function is called.

We are using a heuristic list. The filename1 is read until the word END is not read. Then the lines are split into city name and distance to goal state which is appended to the heuristic list.

This function returns the heuristic list.

Explanation

The function has source city, goal city, edges dictionary, edge_wt dictionary and heuristic list as parameters.

A for loop is till the length of heuristic list and if the source city matches the city name in heuristic list we append it in fifo list the heuristic distance, distance and source city name and in the parent list the city distance,distance, parent name and source city name. Then we come out of the loopby using break.

The while loop goes until the fifo list is not empty.

• The cost and name of city is stored in cost1 and node1 variable and the count var is incremented.
• If node1 is same as goal then the count is displayed and the distance from the fifo list is displayed.
• We sort the parent list according to the distances.
• The current node is appended in parent1 list.
• Else we pop the first element of fifo list.

If the node is not in visited list then use a for loop to go through the edges dictionary with node1 as key.

Another for loop j to length of the heuristic list and if i in edges[node1]dictionary matches with city in heuristic list (heuristic[j][0])then results variable stores the distance between node1 and i in the for loop for the edges_wt dictionary as key having distance as the value.

Then calculating the total_cost1 by taking the sum of cost1 from node, result list and heuristic list.

Similarly, calculating the total_cost2 by taking sum of cost1 and result list.

Then appending total_cost1, total_cost2 and i in the fifo list and parent list with addition of node1 in parent list. Then we come out of the loop using break statement.

Sorting the fifo list as to take the min distance first and then appending the node in visited.

Explanation

In the command line the first argument should be the input file name, source city, destination city and heuristic filename.

Calling storing_input(filename) and sotring_input2(filename1)

Then calling astar() with src, dest, edges , edge_wt and heristic list as parameters returned from storing_input() and storing_input2().

3) Posterior Probability

Aim🏹

To determine the posterior probability of different hypotheses, given priors for these hypotheses, and given a sequence of observations and determine the probability that the next observation will be of a specific type, priors for different hypotheses, and given a sequence of observations.

The five possible hypotheses for our bag are:

• h1 (prior: 10%): This type of bag contains 100% cherry candies.
• h2 (prior: 20%): This type of bag contains 75% cherry candies and 25% lime candies.
• h3 (prior: 40%): This type of bag contains 50% cherry candies and 50% lime candies.
• h4 (prior: 20%): This type of bag contains 25% cherry candies and 75% lime candies.
• h5 (prior: 10%): This type of bag contains 100% lime candies.

Input📥

A string which represents sequence of candies we have already picked. C should be for cherry candy and L for lime candy.

Output📤

The probability of every hypothesis given the sequence and probability of the next candy picked given sequence will be written in a result.txt file.

Algorithm👨‍🎓

1. Push the starting city in the queue.
2. Push all its neighboring cities in the queue and sort them with their distances taking in account the heuristic distances of each city.
3. Dequeue the first element and If the node pushed in is goal state print it and stop program.
4. If not then keep repeating the process till the queue is not empty.

Program 👇

Explanation🕵️‍♀️

• In sequence we are storing the sequence user enters through the command line and stores it’s length in lseq.
• The p_cc and prior are the probabilities given in the problem itself.
• A for loop runs through the length of sequence to calculate number of occurrences of C and L.
• There is for loop which runs till range 5 as there are 5 hypotheses. So for each hypotheses we are calculating its posterior by taking the p_cc value and raising it to count of C multiplied with 1-p_cc raise to count of L and multiplying the prior probability of 1hypotheses.
• A sum1 is used to maintain the addition of all values. The same calculation is done for each hypotheses and appended into a list called posterior.
• We open a file result.txt in write mode. In a for loop with length of posterior we divide all its elements with sum1 to get the probability and write that into the file.
• For calculating the probability of next candy again a for loop is used till length of posterior by multiplying posterior of each with p_cc of each and taking sum of these which will give probability next candy picked is C and 1-that sum is probability next candy picked is L which is written in the file.
• We close the file.

Example

python compute_a_posteriori.py LCCCCCCCCCCCLLLLLLLLLLLLLLLLLLLLLLL
result.txt
Observation sequence: LCCCCCCCCCCCLLLLLLLLLLLLLLLLLLLLLLL with length: 35
P(h1|Q)=0.0
P(h2|Q)=5.0447788251e-07
P(h3|Q)=0.195698804445
P(h4|Q)=0.804300691077
P(h5|Q)=0.0

Probability that the next candy we pick will be C, given Q: 0.29892495335

Probability that the next candy we pick will be L, given Q: 0.70107504665

4) Bayesian Networks

The problems are made easier to understand with the help of explanation and Algorithm that we provide along with the code. If you have any doubts feel free to comment on the Blog. Enough of me trying to increase my audience :p . Let’s take a look at the problem.

Aim🏹

For the Bayesian network given above, write a program which computes and prints out the probability of any combination of events given other combinations.

Input📥

First, there are one to five arguments, each argument specifying a variable among Burglary, Earthquake, Alarm, JohnCalls, and MaryCalls and a value equal to true or false. Each of these arguments is a string with two letters.

The first letter is B (for Burglary), E (for Earthquake), A (for Alarm), J (for JohnCalls) or M (for MaryCalls).

The second letter is t (for true) or f (for false).

Then, optionally, the word “given” follows, followed by one to four arguments. These last arguments specify a combination of events C2 such that we need to compute the probability of C1 given C2

Output📤

The probability of the combination user types in

Program👇

Explanation

Import division needed so that the division has the decimal point answer and sys for accepting input through command line.

Creating dictionaries for storing the values(Boolean true or false or empty i.e. -) the user enters for corresponding keys which is already known.

Explanation🕵️‍♀️

• A class called Bayesian_network created.
• The constructor __init__ initializes the values of the 5 vars calculated from the Bayesian network given in the diagram and two lists are made.
• The computeProbability() function takes the 5 var input values given by user. We create a empty list ‘l’.
• Multiple if conditions written for each var value to check if its empty and not in the list then append it to the ‘data1’ list.
• Else if it has some values then for each var we check if it’s value is true and append it in ‘l’ and 1-var_value in ‘l’ if false.
• If an event occurs has probability x then probability of event not occurring is 1-x.
• The Alarm has two parents Burglary and Earthquake so in ‘l’ we append according to the Burglary and Earthquake values.
• MaryCallas and JohnCalls depend upon Alarm value so accordingly true or false will be appended to ‘l’. Then a loop is used to access each element of list ‘l’ and multiply them together and append in the list ‘data2’.
• In the first var we store the first element of the data1 list and in ‘data1’ list we store elements from the second element to its length.
• Then if conditions are used to check ‘first’ has which of the variable names and within that again if that variable name has a true or false value and accordingly computeProbability() function is called with sending those parameters.
• At the end ‘data2’ list is returned.

Explanation👨‍🔧

• First we check length of the argv is 1 then it is invalid and exit the program.
• Else if the given is there in argv then we get the index of that word and in num var we store values from starting to index-1and index+1 to end. And denum we store values after the index of given till end.
• An object of bayesian_network() called bnet is made. A for loop is used to access items in num var and dict1 dictionary initialized using __init__ the keys are made using item[0] and its values are item[1] of the num variable.
• Then we take the sum of the result returned by computeProbability() function in n. The same process for denum variable and store result in d var. Then the probability is printed by dividing n/d.
• Else we create an object of the class and append the argv arguments in data list. And for items in data we create keys of dict1 of items[0] and its values with item[1]. The probability is sum of value returned by computeProbability() function.

if __name__ == ‘__main__’:

main(sys.argv)

Calls the main function sending the arguments user entered in command line.

Conclusion

Don’t forget to hit the follow button✅to receive updates when we post new coding challenges. Tell us how you solved this problem in the comments section below. 🔥 We would be thrilled to read them. ❤

I have published an ebook. A compilation of 100 Java(Interview) Programming problems which have been solved . (HackerRank) 🐱‍💻

Click HERE 🧨🎊🎃

This is completely free 🆓 if you have amazon kindle subscription.

Previous Blog Posts

100 Days to Amazon — Day 1

One Does Not Simply Solve 50 Hacker Rank Coding Challenges

Top Programming Language Books to Read this 2019

Author: Akshay Ravindran