assignmentF.qmd

---
title: "Assignment F (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 {.unnumbered}

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.  There are 5 points for clealiness and organization. The code should be commented and clearly written with intuitive variable names. For example, use variable names such as number_input, factor, hours, instead of a,b,xyz, etc.

6.  The assignment is worth 100 points, and is due on **30th May 2023 at 11:59 pm**.

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

## 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?

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

*(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.

*(6 points)*

### Most fascinating votss

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.

*(8 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.

*(10 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)*

## Recursive 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 the `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 short return `False`. The `<` and `>` operators can be used to alphabetically compare two `character` objects.

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

### Word search

Check your function if the `word_to_search` is:

1.  `'agreement'`

2.  `'qualifier'`

3.  `'agree'`

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

*(6 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.  `'tiring'`

*(8 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.  `'skirmish'`

*(10 points)*

## Sudoku

This question is about solving the Sudoku puzzle with recursion. Read about the Sudoku rules [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 how the function is implemented. You will need to add some lines in the code to answer some of the questions below.

### Base case & recursive case

What are the base and recursive cases of the function? Cite the relevant lines of code, and explain.

*(4 points)*

### Solving Sudoku

Use the function to solve the following Sudoku puzzle. Execute the following lines of code to see the puzzle.

```{r}
#| eval: false
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. The `result` object will be created when you solve the puzzle, and will be used by the function below 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)
  }
}
```

*(2 points)*

### Number of calls

How many times does the function `solve_sudoku` call itself to solve the puzzle?

*(4 points)*

### Number of calls for each cell

Create a 9x9 matrix that contains the number of times the function calls itself for the respective cell in the puzzle.

*(6 points)*

### Reducing recursive calls

Analyze the matrix in the previous question. Edit the function to reduce the number of calls it makes to itself to solve the puzzle. The approach must be general and not specific to this particular puzzle.

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

Also, create a 9x9 matrix that contains the number of times the function calls itself for the respective cell in the puzzle (with the improved Sudoku solver), and print the matrix.

*(15 points)*