The purpose of this assignment is to get you to implement and use lists. The assignment consists of three (3) problems, corresponding to minimum (C), expected (B), and outstanding (A) levels of difficulty. That is, solving the first problem yields a grade of C, solving the first two problems yields a grade of B, and solving all three problems yields a grade of A. Background Radio stations have a challenging job: Creating a daily play-list. At the beginning of each day, a radio station creates a daily play-list (a list of songs that it will play for that day). If a radio station wishes to stay in business, it will choose the songs that are likely to be most popular. It has been observed that the number of requests for a song in the preceding days is a good predictor of whether the song will be popular in the future. In fact requests in recent days are better predictors of a song's popularity than requests in earlier days. For a given song, this observation is modeled by the erponential moving average: P. = RW + P-1(1 - W) where P is the predicted popularity of the song after dayt, Re is the fraction of requests for the song out all requests on that day, . # of requests for the song on day t Total # of requests on day and W is the weight given to more recent requests and is in the range 0 Problem 1 (C Grade): Radio Ga Ga Given a list of songs, and sequences of daily song requests your program will need to create a play-list of a specified length that the radio station should play. Write a program called RadioGaGa.java that reads in a song list, and a sequence of song requests, spanning multiple days, and outputs a play-list of specified length for each following day. ALLAN m W Input WWWWWWWWW inimum WW.Www mumma mm mm The input comprises a number of lines. The first line, contains an integer N, denoting the number of songs in the song list. This is followed by N lines enumerating the songs Bach NO WWW.ANIMA wwwwwwwwwwww wwwwwwwwww line consists of three values: a single word, denoting the title of the song; an integer T, denoting the length of the song in seconds); and decimal value between 0 and 1 denoting the initial popularity of the song. For example: Red_Barchetta 371 0.5 The next line contains three values: an integer T, denoting the maximum length (in minutes) of the play-list, a double W denoting the weight attributed to new requests (see the formula above); and an integer D denoting the number of days of song requests to follow. For example, 22 0.5 2 specifies a T = 22 minute play-list, with a weight W -- 0.5, and D -- 2 days of song requests. Each day of requests consists of a number of lines. The first line contains the integer R, denoting the number of song requests to follow. The next R lines contain song titles from the previously loaded song list. (See Example section.) Processing The day 0 of programming begins after the list is read. Ench following day begins after a day of song requests have been read. The play-list should be as close to the specified time T as possible without exceeding T minutes. Songs should be added to the list according to popularity (most popular to least pop- ular), with ties broken by song length. For example, if two songs are equally popular, the shorter one is preferred. If a song is too long to fit on the play-list, it is passed over. The order of the songs on the play-list should be the order in which they were added. Output For each day (O... D) your program should output a play-list. I.e., there should be D +1 play-lists. Each play-list consists of single line. Each line starts with an integer denoting the day followed by the play-list song titles in the order specified, separated by spaces. Each line is terminated by a new-line character. See next section for example of output. w Example Sample Input The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.5 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Arm_And_Sword 396 0.55 Test_For_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 22 0.5 2 Red_Sector_A Red_Sector_A Vapor_Trails Red_Sector_A Test_for_Echo The Garden Vapor_Trails 2112_Overture The_Garden Test_For_Echo 2112_Overture Sample Output O Closer_To_The_Heart The_Garden Red_Sector_A The Pass 1 Red_Sector_A Closer_To_The_Heart The_Garden The_Pass 2 The Garden Red_Sector A Closer_To_The_Heart Test_For Echo Problem 2 (B Grade): Radio Network Instead of a single radio station, your program has to make play-lists for several radio stations that share the same song list. But, each radio station has its own demographic, which will result in song ratings that vary from station to station. Given a list of songs, and sequences of daily song requests for your rndio stations, your program will need to create a play-list of a specified length for each of the radio stations. Write a program called RadioNetwork.java that reads in a song list, a list of radio stations, and a sequence of song requests, spanning multiple dnys, and outputs in play-list for each radio station of specified length for each following day. Input The input is very similar to Problem 1. The first part of the input is a list of songs, identical to the input format in Problem 1. The song list is followed by two integers: an integer S, denoting the number of stntions; and an integer D denoting the number of days, just like in Problein 1. These nre followed by S radio station specifications. Each station specification consist of a station identifier; the length of the play-list, T, in minutes (just like in Problem 1); and the weight W Gust like in Problem 1). For example, 11 CBC1 22 0.5 The last part of the input are the requests, these are similar to Problem I, except thnt each request consists of two words: the identifier of the radio station to which the request was sent and the song title. For example, CBC1 The_Garden Please see full example below. www WW WW LE Processing . The processing is the same as in Problem 1 except for the following differences, Each radio station can have its own length of play-list T and its own weight A song request affects the ratings of a song at the specified radio station nnd not all radio stations. That is, the request rate Re for a song nt a radio station is # of requests for the song on day t at specified radiostation Total # of requests on day tam specified radiostation Each station's requests are only counted for the specified radio station. Output For each day (0... D) your program should output a play-list for each radio station. I.e., there should be S x (D+1) play-lists. The output for each day begins with an integer denoting the day. This is followed by S lines, each displaying a play-list for a radio station. Ench play-list consists of single line. Each line has the format: W WWW + Station Song Song Song3 ... For example, + CBC1: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass Each line is terminated by a new-line character. The play-lists should be in the same order as the input order of the radio stations. Example Sample Input The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.6 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Arm_And_Sword 396 0.56 Test_For_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 31 CBC 22 0.5 CBC1 22 0.5 CBC2 22 0.5 CBC Red_Sector_A CBC1 Red_Sector_A CBC2 Vapor Trails CBC Red_Sector_A CBC Test_For Echo Sample Output + CBC: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass + CBC1: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass + CBC2: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass + CBC: Red_Sector_A Closer_To_The_Heart The_Garden Test_For_Echo + CBC1: Red Sector A Closer_To_The_Heart The_Garden The_Pass + CBC2: Vapor_Trails Closer_To_The_Heart The_Garden Red_Sector_A Problem 3 (A Grade): Radio Difference As a radio network baron, you are always in the lookout to cut corners and save money. If two radio stations are playing similar play-lists, then you can save money by eliminating one of the radio stations or aiming it at a different dernographic. You need to determine which of your stations are too similar. The difference between two radio stations is defined as the sum of squares of the differ- ences between the ratings of the song ratings. That is, all radio stations have the same set of songs, each with their own ratings. Suppose the ratings for the songs at radio station U are tuo, ,u2,.. and the ratings for the same songs at radio station V are un, V1, 112,... UN, where th; and t; are ratings for the same song at the respective radio stations. Then the difference between the two radio stations is: D(UV) = (20 - 20) + (u1 - 01? + (u2 2x) + ... + (un - Un)? If D(UV) is smaller than the specified similarity threshold, then the two radio stations are too similar. Given a list of songs, and sequences of daily song requests for your radio stations, your program will need to determine if each pair of radio stations is too similar. Write a program called RadioDifference.java that reads in a song list, a list of radio stations, a sequence of song requests, and a similarity threshold. The program outputs all pairs of radio stations whose difference is less than the similarity threshold after all the requests in ench dny have been processed. Input The input is the same as Problem 2, except for one snall difference. The song list is followed by three numbers (not two): an integer S, denoting the number of radio stations; an integer D, denoting the number of days of requests; and lastly, a double X, denoting the the similarity threshold. Please see full example below. Processing w The processing is the same as in Problem 2 except that no play-lists are generated. Once all requests are processed, the difference for each pair of stations is computed and all pairs of stations whose difference is below the similarity threshold are displayed. Each pair that is displayed should only be displayed once, and the order of the stations should match the input order. Output For each pair of stations whose difference is below the similarity threshold, output the line Difference between U and V is below threshold where U and V are the station identifiers of the two stations. Note that U must come before V in the radio station list. See next section for example of output Example Sample Input 13 The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.5 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Armi And_Sword 396 0.55 Test_for_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 31 0.2 CBC 22 0.5 CBC1 22 0.5 CBC2 22 0.5 CBC Red_Sector_A CBC1 Red_Sector_A CBC2 Vapor Trails CBC Red_Sector_A CBC Test_For_Echo Sample Output Difference between CBC and CBC1 is below threshold Hints and Suggestions Use one of Java's list implementations for this assignment. Create a Song class in your program The Java Collections class has a sort method that works on lists. It will be very useful. For Problems 2 and 3, create a Station class Problem 1 is a natural starting point for Problem 2. Be sure to actually make copies of the Song objects for each radio station. The same song may have different popularity ratings at different stations. Problem 2 is a natural starting point for Problem 3. There is not a lot of code to write. The solution to Problem 1 is under 170 lines of code. Problem 2 reuses most of the code from Problem 1, requiring just 80 lines of additional code. Problem 3 requires even less additional code. Your code must compile. If it does not compile, you will receive a 0 on the assignment. Your code must be well commented and indented. Please see the Assignments section for this course on Brightspace for Code Style Guidelines. You may assume that all input will be correct. Be sure to test your programs using the provided tests or with Mimir. What to Hand In Submit the source files for your program via Mimir as described in the first tutorial. A link to Mimir is available on Brightspace. At least three of the submitted files must be RadioGaga.java, RadioNetwork.java, and RadioDifference.java, which is where the main programs start to run. The purpose of this assignment is to get you to implement and use lists. The assignment consists of three (3) problems, corresponding to minimum (C), expected (B), and outstanding (A) levels of difficulty. That is, solving the first problem yields a grade of C, solving the first two problems yields a grade of B, and solving all three problems yields a grade of A. Background Radio stations have a challenging job: Creating a daily play-list. At the beginning of each day, a radio station creates a daily play-list (a list of songs that it will play for that day). If a radio station wishes to stay in business, it will choose the songs that are likely to be most popular. It has been observed that the number of requests for a song in the preceding days is a good predictor of whether the song will be popular in the future. In fact requests in recent days are better predictors of a song's popularity than requests in earlier days. For a given song, this observation is modeled by the erponential moving average: P. = RW + P-1(1 - W) where P is the predicted popularity of the song after dayt, Re is the fraction of requests for the song out all requests on that day, . # of requests for the song on day t Total # of requests on day and W is the weight given to more recent requests and is in the range 0 Problem 1 (C Grade): Radio Ga Ga Given a list of songs, and sequences of daily song requests your program will need to create a play-list of a specified length that the radio station should play. Write a program called RadioGaGa.java that reads in a song list, and a sequence of song requests, spanning multiple days, and outputs a play-list of specified length for each following day. ALLAN m W Input WWWWWWWWW inimum WW.Www mumma mm mm The input comprises a number of lines. The first line, contains an integer N, denoting the number of songs in the song list. This is followed by N lines enumerating the songs Bach NO WWW.ANIMA wwwwwwwwwwww wwwwwwwwww line consists of three values: a single word, denoting the title of the song; an integer T, denoting the length of the song in seconds); and decimal value between 0 and 1 denoting the initial popularity of the song. For example: Red_Barchetta 371 0.5 The next line contains three values: an integer T, denoting the maximum length (in minutes) of the play-list, a double W denoting the weight attributed to new requests (see the formula above); and an integer D denoting the number of days of song requests to follow. For example, 22 0.5 2 specifies a T = 22 minute play-list, with a weight W -- 0.5, and D -- 2 days of song requests. Each day of requests consists of a number of lines. The first line contains the integer R, denoting the number of song requests to follow. The next R lines contain song titles from the previously loaded song list. (See Example section.) Processing The day 0 of programming begins after the list is read. Ench following day begins after a day of song requests have been read. The play-list should be as close to the specified time T as possible without exceeding T minutes. Songs should be added to the list according to popularity (most popular to least pop- ular), with ties broken by song length. For example, if two songs are equally popular, the shorter one is preferred. If a song is too long to fit on the play-list, it is passed over. The order of the songs on the play-list should be the order in which they were added. Output For each day (O... D) your program should output a play-list. I.e., there should be D +1 play-lists. Each play-list consists of single line. Each line starts with an integer denoting the day followed by the play-list song titles in the order specified, separated by spaces. Each line is terminated by a new-line character. See next section for example of output. w Example Sample Input The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.5 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Arm_And_Sword 396 0.55 Test_For_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 22 0.5 2 Red_Sector_A Red_Sector_A Vapor_Trails Red_Sector_A Test_for_Echo The Garden Vapor_Trails 2112_Overture The_Garden Test_For_Echo 2112_Overture Sample Output O Closer_To_The_Heart The_Garden Red_Sector_A The Pass 1 Red_Sector_A Closer_To_The_Heart The_Garden The_Pass 2 The Garden Red_Sector A Closer_To_The_Heart Test_For Echo Problem 2 (B Grade): Radio Network Instead of a single radio station, your program has to make play-lists for several radio stations that share the same song list. But, each radio station has its own demographic, which will result in song ratings that vary from station to station. Given a list of songs, and sequences of daily song requests for your rndio stations, your program will need to create a play-list of a specified length for each of the radio stations. Write a program called RadioNetwork.java that reads in a song list, a list of radio stations, and a sequence of song requests, spanning multiple dnys, and outputs in play-list for each radio station of specified length for each following day. Input The input is very similar to Problem 1. The first part of the input is a list of songs, identical to the input format in Problem 1. The song list is followed by two integers: an integer S, denoting the number of stntions; and an integer D denoting the number of days, just like in Problein 1. These nre followed by S radio station specifications. Each station specification consist of a station identifier; the length of the play-list, T, in minutes (just like in Problem 1); and the weight W Gust like in Problem 1). For example, 11 CBC1 22 0.5 The last part of the input are the requests, these are similar to Problem I, except thnt each request consists of two words: the identifier of the radio station to which the request was sent and the song title. For example, CBC1 The_Garden Please see full example below. www WW WW LE Processing . The processing is the same as in Problem 1 except for the following differences, Each radio station can have its own length of play-list T and its own weight A song request affects the ratings of a song at the specified radio station nnd not all radio stations. That is, the request rate Re for a song nt a radio station is # of requests for the song on day t at specified radiostation Total # of requests on day tam specified radiostation Each station's requests are only counted for the specified radio station. Output For each day (0... D) your program should output a play-list for each radio station. I.e., there should be S x (D+1) play-lists. The output for each day begins with an integer denoting the day. This is followed by S lines, each displaying a play-list for a radio station. Ench play-list consists of single line. Each line has the format: W WWW + Station Song Song Song3 ... For example, + CBC1: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass Each line is terminated by a new-line character. The play-lists should be in the same order as the input order of the radio stations. Example Sample Input The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.6 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Arm_And_Sword 396 0.56 Test_For_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 31 CBC 22 0.5 CBC1 22 0.5 CBC2 22 0.5 CBC Red_Sector_A CBC1 Red_Sector_A CBC2 Vapor Trails CBC Red_Sector_A CBC Test_For Echo Sample Output + CBC: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass + CBC1: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass + CBC2: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass + CBC: Red_Sector_A Closer_To_The_Heart The_Garden Test_For_Echo + CBC1: Red Sector A Closer_To_The_Heart The_Garden The_Pass + CBC2: Vapor_Trails Closer_To_The_Heart The_Garden Red_Sector_A Problem 3 (A Grade): Radio Difference As a radio network baron, you are always in the lookout to cut corners and save money. If two radio stations are playing similar play-lists, then you can save money by eliminating one of the radio stations or aiming it at a different dernographic. You need to determine which of your stations are too similar. The difference between two radio stations is defined as the sum of squares of the differ- ences between the ratings of the song ratings. That is, all radio stations have the same set of songs, each with their own ratings. Suppose the ratings for the songs at radio station U are tuo, ,u2,.. and the ratings for the same songs at radio station V are un, V1, 112,... UN, where th; and t; are ratings for the same song at the respective radio stations. Then the difference between the two radio stations is: D(UV) = (20 - 20) + (u1 - 01? + (u2 2x) + ... + (un - Un)? If D(UV) is smaller than the specified similarity threshold, then the two radio stations are too similar. Given a list of songs, and sequences of daily song requests for your radio stations, your program will need to determine if each pair of radio stations is too similar. Write a program called RadioDifference.java that reads in a song list, a list of radio stations, a sequence of song requests, and a similarity threshold. The program outputs all pairs of radio stations whose difference is less than the similarity threshold after all the requests in ench dny have been processed. Input The input is the same as Problem 2, except for one snall difference. The song list is followed by three numbers (not two): an integer S, denoting the number of radio stations; an integer D, denoting the number of days of requests; and lastly, a double X, denoting the the similarity threshold. Please see full example below. Processing w The processing is the same as in Problem 2 except that no play-lists are generated. Once all requests are processed, the difference for each pair of stations is computed and all pairs of stations whose difference is below the similarity threshold are displayed. Each pair that is displayed should only be displayed once, and the order of the stations should match the input order. Output For each pair of stations whose difference is below the similarity threshold, output the line Difference between U and V is below threshold where U and V are the station identifiers of the two stations. Note that U must come before V in the radio station list. See next section for example of output Example Sample Input 13 The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.5 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Armi And_Sword 396 0.55 Test_for_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 31 0.2 CBC 22 0.5 CBC1 22 0.5 CBC2 22 0.5 CBC Red_Sector_A CBC1 Red_Sector_A CBC2 Vapor Trails CBC Red_Sector_A CBC Test_For_Echo Sample Output Difference between CBC and CBC1 is below threshold Hints and Suggestions Use one of Java's list implementations for this assignment. Create a Song class in your program The Java Collections class has a sort method that works on lists. It will be very useful. For Problems 2 and 3, create a Station class Problem 1 is a natural starting point for Problem 2. Be sure to actually make copies of the Song objects for each radio station. The same song may have different popularity ratings at different stations. Problem 2 is a natural starting point for Problem 3. There is not a lot of code to write. The solution to Problem 1 is under 170 lines of code. Problem 2 reuses most of the code from Problem 1, requiring just 80 lines of additional code. Problem 3 requires even less additional code. Your code must compile. If it does not compile, you will receive a 0 on the assignment. Your code must be well commented and indented. Please see the Assignments section for this course on Brightspace for Code Style Guidelines. You may assume that all input will be correct. Be sure to test your programs using the provided tests or with Mimir. What to Hand In Submit the source files for your program via Mimir as described in the first tutorial. A link to Mimir is available on Brightspace. At least three of the submitted files must be RadioGaga.java, RadioNetwork.java, and RadioDifference.java, which is where the main programs start to run