After enjoying watching The Greatest Showman outside at the Movies on the Lawn in the Orange County Great Park a couple of years ago, the instructor's children asked to watch more musicals. Having grown up a huge Disney fan, the instructor's wife showed them the classic Mary Poppins.

In this musical, there is a song about the peculiar and ridiculous1 word Supercalifragilisticexpialidocious. The children thought this word was hilarious and asked Alexa to play the song over and over2. Eventually, they asked Alexa to spell the word, but the spy nanny digital assistant didn't understand their command, so the children (begrudgingly) resorted to asking their parents, who wrote down the word for them on some paper3.

Looking at the word on paper, the children realized they could form many smaller words from the letters in Supercalifragilisticexpialidocious. For instance, they could form the word is three times, ace twice, and rage once using the letters in Supercalifragilisticexpialidocious only up to the number times they occurred in the original word.

Knowing that their father has a bunch of students who do that computer programming thing, they asked him to request that you write a program that determines the number of times a word could be formed out of the letters of another word.

Input

The input will be a series of space-separated word pairs, s1 and s2, with one pair per line. Here is an example input:

supercalifragilisticexpialidocious is
supercalifragilisticexpialidocious ace
supercalifragilisticexpialidocious rage

Output

For each pair of words, your program is to determine how many times s2 can be formed using the letters in s1 (where each letter in s1 is only used up to the number of times it appears in s1) and print out that number.

Here is the output for the example input above:

3
2
1

Submission

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

$ cd path/to/cse-30872-fa20-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 challenge01               # Create and checkout challenge01 branch

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

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

$ git push -u origin challenge01            # Send changes to GitHub

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

$ .scripts/submit.py
Submitting challenge01 assignment ...
Submitting challenge01 code ...
  Result Success
   Score 6.00
    Time 0.02

$ curl -F source=@challenge01/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa20/challenge01
{"result": "Success", "score": 6, "time": 0.016292572021484375}

Pull Request

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 01 TA List.


  1. Quite atrocious; makes you sound precocious. 

  2. I hope the NSA likes Disney musicals. 

  3. After consulting the spellchecker in the cloud (ie. DuckDuckGo).