Solved–Challenge 00: Tidy Cards– Solution

Description

After slamming his head against the programming challenges on HackerRank and LeetCode last year, Vector Bill decided that he didn’t really want to make money or be financially independent1. Instead, he opted to take his talents to the monastery academia, where he could fulfill his live-long ambition of being a graduate teaching assistant2.

Since he is now a graduate student, Vector Bill had to move off-campus, which involved relocating many of his prized possessions such as his Birkenstocks, yellow headphones, and of course, his Magic The Gathering cards3. To ensure he didn’t lose any cards in the process of moving from Duncan4 to his new apartment, Vector Bill decided to count how many cards he had in each deck before and after the move.

As counting cards is a tedious task, Vector Bill‘s mind began to wander and he noticed that some numbers, when written in base 10 with no leading zeroes, have their digits sorted in non-decreasing order. Some examples of this are 8, 123, 555, and 224488. He really liked this phenomenon and decided to call these numbers tidy. Numbers that do not have this property, like 20, 321, 495 and 999990, are considered not tidy.

Because he doesn’t quite have any research to do yet, Vector Bill wonders if there are N cards in a deck, what was the last tidy number he counted?

You are to write a program that helps Vector Bill solve this problem.

​Input

The first line of standard input gives the number of test cases, T. T lines follow. Each subsequent line of input describes a test case with a single integer N where 0
<= N <= 1000, which is the total number of cards in that deck as counted by Vector Bill.

Here is an example input:

3
132
1000
7

​Output

For each test case, output to standard output one line containing Deck
#x: y, where x is the test case number (starting from 1) and y is the last tidy number encountered by Vector Bill.

Here is the output given the example input above:

Deck #1: 129
Deck #2: 999
Deck #3: 7

​ Google Code Jam

This programming challenge is based on Problem B. Tidy Numbers from the 2017 Qualification Round of Google Code Jam.

​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 challenge00               # Create and checkout challenge00 branch

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

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

$ git push -u origin challenge00            # Send changes to GitLab

​ Programming Languages

Note, dredd supports C, C++, Python, Java, [Go], Node, and Ruby. You may use any of those languages, just be sure to name your source file program.$EXTENSION where $EXTENSION is the appropriate file extension for your chosen language (e.g. py for Python).

If you wish to try out another language, please let the instructor know and support can be added to dredd.

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

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

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

The score returned from dredd will be one of the following:

​ Test Cases

Note, dredd contains additional test cases beyond that which is show in the examples above. This means that even if you pass on the input above, you are not guaranteed to pass the dreddtest if you do not handle additional situations.

This means you should consider what the possible edge cases are and how to handle them. Feel free to create your own input and output test files and use them to verify your program:

$ ./program < input.txt | diff -u - output.txt

Once you have commited your work and pushed it to GitLab, remember to create a merge request. Refer to the Reading 00 TA List to determine your corresponding TA for the merge request.

1. Student loans 4 lyfe. J/K. Not really. Maybe? ↩

2. He is the head TA for the class that shall not be named. ↩

3. He is always looking for people to play with! ↩

4. The dorm not the “student” center which is sometimes closed to students. ↩