assignment6.qmd

---
title: "Assignment 6 (R: Lists and Recursion)"
subtitle: "R: Lists and recursion"
format:
  html:
    toc: true
self-contained: true
link-external-newwindow: true
editor_options: 
  chunk_output_type: console
---

## Instructions {-}

1. You may talk to a friend, discuss the questions and potential directions for solving them. However, you need to write your own solutions and code separately, and not as a group activity. 

2. Do not write your name on the assignment.

3. Make R code chunks to insert code and type your answer outside the code chunks. Ensure that the solution is written neatly enough to understand and grade.

4. Render the file as HTML to submit.

5. The assignment is worth 100 points, and is due on **22nd November 2022 at 11:59 pm**. 

6. You are **not allowed to use a `for` loop** in this assignment, except in the last question on Sudoku.

7. In addition to uploading the HTML file on Canvas, you will submit this assignment on Github as well. Github link for the assignment is: <https://classroom.github.com/a/mzLbthmW> . 

Put the link to your Github repository containing your rendered HTML file here: \<link to Github repository>

## TED Talks

Execute the following code to get the object `ted_talks`, which contains information about TED talks.

Note that you are **not allowed to use a `for` loop** or any other kind of loop in all the questions below.

```{r}
#| eval: false
library(rjson)
ted_talks<-fromJSON(file='TED_Talks.json')
```

### Number of talks
How many TED talks are there in the data?

*(2 points)*

### Average number of views
What is the mean number of views of the TED talks?

*(4 points)*

### Highest number of views
Find the `headline`, `year_filmed`, and number of `views` of the top five talks with the highest number of views. 

Reminder: Do not use a `for` loop or any other kind of loop.

*(9 points)*

### Most *Funny* votes
Find the `headline`, `year_filmed` and `count` of *Funny* votes of the top five talks with the highest number of *Funny* votes 

Reminder: Do not use a `for` loop or any other kind of loop.

*(12 points)*

### Highest proportion of *Inspiring* votes
Find the `headline`, `year_filmed`, and proportion of *Inspiring* votes from among all the votes for the talk, of the top five talks with the highest proportion of *Inspiring* votes. 

Reminder: Do not use a `for` loop or any other kind of loop.

*(15 points)*

### Most popular voting category
Add the votes of all TED talks for each category. Which category has received the most votes? What is the proportion of total votes for this category?

Reminder: Do not use a `for` loop or any other kind of loop.


*(10 points)*

## Binary search

Execute the code below to get the object `wordlist_global`, which contains a vector of words. Write a **recursive** function that accepts a word, say `word_to_search` and a vector of words, say `wordlist` as arguments, and finds if the `word_to_search` occurs in `wordlist_global` or not. This is very simple to do with the code `word_to_search %in% tuple_of_words`. However, this code is unfortunately very slow.

As the words in `wordlist_global` are already sorted in alphabetical order, we can search using a faster way, called binary search. To implement binary search in a function, start by comparing `word_to_search` with the middle entry in the `wordlist_global`. If they are equal, then you are done and the function should return `TRUE`. On the other hand, if the `word_to_search` comes before the middle entry, then the function must call itself to search the first half of `wordlist_global`. If it comes after the middle entry, then the function must call itself to search the second half of `wordlist_global`. In every recursive call, the function must repeat the process on the appropriate half of the `wordlist` and continue until the word is found or there is nothing left to search, in which case the function should return `FALSE`. The `<` and `>` operators can be used to alphabetically compare two `character` objects.

Note that your function must use **recursion**.

### Word search check
Check your function if the `word_to_search` is:

1. `'agreement'`

2. `'aghast'`

```{r}
#| eval: false
wordlist_global<-unlist(read.table('wordlist.txt', header = FALSE, sep = "", dec = "."))
```

Reminder: Do not use a `for` loop or any other kind of loop.


*(15 points)*

### Number of iterations
Update the function to also print the number of iterations it took to find the `word_to_search` or fail in finding the `word_to_search`.

Check your function if the `word_to_search` is:

1. `'agreement'`

2. `'aghast'`

**Hint:** You can update a global variable inside the function using the `<<-` operator.

Reminder: Do not use a `for` loop or any other kind of loop.

*(3 points)*

### Index of `word_to_search`
Update the function in the previous question to also print the index of `word_to_search` in `wordlist_global` if the word is found. For example, the index of 'abacus' is 1, the index of 'abdomen' is 2, and so on.

Check your function if the `word_to_search` is:

1. `'agreement'`

2. `'aghast'`

Reminder: Do not use a `for` loop or any other kind of loop.

*(6 points)*

## Sudoku

This question is about solving the Sudoku puzzle with recursion. Read about  Sudoku [here](https://sudoku.com/how-to-play/sudoku-rules-for-complete-beginners/#:~:text=Sudoku%20is%20played%20on%20a,the%20row%2C%20column%20or%20square.). Think about how to solve the Sudoku puzzle with recursion.

This [blog](https://www.r-bloggers.com/2020/11/how-to-solve-sudoku-with-r/) provides a recursive function `solve_sudoku()` to solve the Sudoku puzzle. Read the blog and understand the recursive function. You will need to add some lines in the function to answer some of the questions below.

### Base case & recursive case
What are the base and recursive cases of the function `solve_sudoku()`? Cite the relevant lines of code, and explain.

*(2 points)*

### Solving sudoku
Use the function to solve the following Sudoku puzzle. Execute the following lines of code to see the puzzle.  
```{r}
board<-matrix(c(rep(0,4),3,rep(0,3),1,9,8,rep(0,4),6,rep(0,5),8,0,7,
                rep(0,5),6,2,0,4,0,7,0,0,4,rep(0,4),9,6,0,0,7,0,5,0,3,
                4,8,rep(0,6),1,rep(0,5),7,rep(0,4),5,9,5,rep(0,3),7,rep(0,4)),
              9,9)

plot(c(0,9),c(0,9),type="n",xlab = "",ylab = "",main = "Sudoku puzzle",
     xaxt="n",yaxt="n",bty="n",asp = 1)
for(i in 1:9)
{
  for(j in 1:9)
  {
    rect(i-1,j-1,i,j)
    if(board[10-j,i]!=0)
    {text((i-1)+0.5,(j-1)+0.5,(((board[10-j,i]))))}
  }
}
for(i in 1:3)
{
  for(j in 1:3)
  {
    rect((i-1)*3,(j-1)*3,3*i,3*j,lwd=2)
  }
}
```

After using the function to solve the puzzle, execute the following lines of code to print the solution:

```{r}
#| eval: false
plot(c(0,9),c(0,9),type="n",xlab = "",ylab = "",main = "Sudoku solved",
     xaxt="n",yaxt="n",bty="n",asp = 1)
for(i in 1:9)
{
  for(j in 1:9)
  {
    rect(i-1,j-1,i,j)
    if(board[10-j,i]!=0)
    {text((i-1)+0.5,(j-1)+0.5,(((board[10-j,i]))))}else{
    text((i-1)+0.5,(j-1)+0.5,(((result[10-j,i]))),col = 2,cex=1.25)}
  }
}
for(i in 1:3)
{
  for(j in 1:3)
  {
    rect((i-1)*3,(j-1)*3,3*i,3*j,lwd=2)
  }
}
```

*(4 points)*

### Number of recursive calls
How many times does the function `solve_sudoku` call itself to solve the puzzle?

*(3 points)*

### Number of calls for each cell

Create and print a $9 \times 9$ matrix that contains the number of times the function calls itself to try a digit for the respective cell in the puzzle.

*(5 points)*

### Reducing recursive calls

Analyze the matrix created in the previous question. Edit the function to reduce the number of recursive calls it takes to solve the puzzle. Your approach must be general and not specific to this particular puzzle. However, you will demonstrate your approach on this puzzle.

Find the number of times the functions calls itself with the improved sudoku solver to solve the given puzzle.

*(8 points)*

### Benefit of recursion
What challenges will you face if you try to solve this problem without recursion?

*(2 points)*