Challenge 06: Longest Distinct Sequence Solution

Last year, the instructor engaged1 in some biohacking. This means that he avoided eating things like grains and dairy when possible, and instead ate a lot of meats, fruits, and vegetables.

Because eating apples everyday is pretty boring, the instructor created a script that generates a sequence of fruits to eat (one per day). For example:

banana tangerine banana peach peach banana
This means that on the first day, he will eat a banana and on the second day he will eat a tangerine and so on and so forth.

Since this script uses a random number generate to select the sequence of fruits, there are sometimes duplicates in his fruit eating schedule. This can be unfortunate, because the instructor doesn't want to eat the same thing everyday 2.

Given a sequence of fruits, the instructor wants to know what it is the length of longest subsequence of days with distinct fruits (and what fruits are in that subsequence).

For instance, in the example above, the longest sequence of days with distinct fruits is tangerine
banana peach and so the length is 3.

Input
You will be given a series of fruit sequences, one sequence per line. Each line will contain a sequence of fruits separate by spaces as show below:

Example Input
pineapple
orange grape
grape coconut pear
peach pineapple peach peach
grape apple banana peach pineapple
banana tangerine banana peach peach banana
apple grape tangerine coconut apple coconut grape
apple grape banana tangerine pineapple pear orange banana
pineapple apple coconut apple pineapple banana pineapple orange coconut
Output
For each sequence of fruits, you are to report the longest sequence of distinct fruits as show below:

Example Output
1: pineapple
2: orange, grape
3: grape, coconut, pear
2: peach, pineapple
5: grape, apple, banana, peach, pineapple
3: tangerine, banana, peach
4: apple, grape, tangerine, coconut
7: apple, grape, banana, tangerine, pineapple, pear, orange
4: coconut, apple, pineapple, banana
Note, you should display the length of the subsequence, followed by the fruits, separated by ",
". If there are multiple subsequences with the maximum length, choose the first subsequence. Make sure there is no trailing space.

Programming Challenges
This problem is inspired by "Problem 13.11" in Elements of Programming Interviews.

Submission
To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments # Go to assignments repository
$ git checkout master # Make sure we are on master
$ git pull --rebase # Pull any changes from GitLab

$ git checkout -b challenge06 # Create and checkout challenge06 branch

$ $EDITOR challenge06/program.cpp # Edit your code

$ git add challenge06/program.cpp # Stage your changes
$ git commit -m "challenge06: done" # Commit your changes

$ git push -u origin challenge06 # Send changes to GitLab
To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge06 assignment ...
Submitting challenge06 code ...
Result Success
Score 6.00

$ curl -F source=@challenge06/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa18/challenge06
{"score": 6, "result": "Success"}
Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 03 TA List to determine your corresponding TA for the merge request.


Notice the past tense. ↩
Actually not true. I do eat basically the same thing everyday... ↩