# Does ARTIFICIAL INTELLIGENCE Sometimes Make You Feel Stupid?

## Learn how to dominate Artificial Intelligence.

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 followinge-book. 🎓

Now without further adieu,

**Algorithms that we will be looking into are:**

**Uninformed Search****Informed Search****Posterior Probability****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👩🎓

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

# Code👇

**Explanation🤩**

- The function has
**filename**as a parameter which is given**when function**is called. - We are using default dictionaries e
**dges, wts and edge_wt**where wts dictionary has**edge weights**as the**key and value i**s the cities having that distance - Th
**e edge_wt**has the**2 cities**as key with their respective distance as weight its value. - The edges dictionary stores the
**neighbours of cities.** - In i
**nput1**we read the input file and store the cities in**src and dest**and distances between them in wt. - After r
**eading 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_w**t 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 a**source **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👨🎓**

- Push the starting city in the
**queue.** - Push all its neighboring cities in the queue and sort them with their distances taking in account the
**heuristic distances**of each city. **Dequeue**the first element and If the node pushed in is goal state print it and stop program.- 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

filename1as a parameter which is given when function is called.We are using a heuristic list. The

filename1 isread until the wordENDis 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 **loop**by 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 **a**n**d 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:

- h
**1 (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👨🎓**

- Push the
**starting city**in the queue. - Push all its
**neighboring cities**in the queue and sort them with their distances taking in account the heuristic distances of each city. **Dequeue**the first element and If the node pushed in is goal state print it and stop program.- 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**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 1**hypotheses**. - 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 giv**e 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 LCCCCCCCCCCCLLLLLLLLLLLLLLLLLLLLLLLresult.txtObservation sequence: LCCCCCCCCCCCLLLLLLLLLLLLLLLLLLLLLLL with length: 35P(h1|Q)=0.0P(h2|Q)=5.0447788251e-07P(h3|Q)=0.195698804445P(h4|Q)=0.804300691077P(h5|Q)=0.0

Probability that the next candy we pick will be C,

given Q: 0.29892495335Probability 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**