Challenge 06: Distinct Fruit

A few years ago, the instructor engaged¹ 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 ².

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.

Submission¶

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

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

$ 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 GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge06 program.cpp ...
  Result Success
    Time 0.02
   Score 6.00 / 6.00

$ curl -F source=@challenge06/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa21/challenge06
{"result": "Success", "score": 6, "time": 0.016405344009399414, "value": 6, "status": 0}