Sep.10 (Mon) 17:53:
Due-date changed to Thu 23:59, as promised in class.
Last modified
You can see a running example of this program at Dr. Okie’s nifty assignment checker
(which uses gnoga to
integrate the GUI, web server, and problem solution).
On-campus or VPN session required.
Grocery shopping is pretty easy: You roll your cart down an aisle, grabbing things at certain locations. After grabbing the last item you need in aisle, you might continue to the end of the aisle and move to the next aisle. Or, you might reverse directions right where you are standing and return to the same end of the aisle you entered, before moving to the next aisle. It’s so easy, you have time to start to wonder: When should you reverse, and when should you continue?
You may realize that previously, you simply reversed whenever you were less than halfway down an aisle. This is sensible, since that gets you to the next aisle quickest. But, you suddenly realize that depending on what locations you want to visit in the next aisle, sometimes you enter at the “wrong” end, and end up walking further than necessary.
In this assignment, you will compute a shorter way to visit certain specified locations
in a store.
In particular, after visiting all of the specified locations in a given aisle, you will use the specified locations in the
next aisle to decide whether to (a) continue going forward to the other end of the aisle, or to (b) reverse and go back to the
end of the aisle where you started.
Specifically, you will take a sequence of aisle-and-locations and calculate the
shortest distance path to visit those locations, considering only the locations in the current and next aisle
in your calculation.
Distance
Aisles are of course numbered starting from one. Within an aisle, we’ll number locations from 0 to a maximum amount (for this assignment, 100). You might think of location 0 being the end of the aisle near the front of the store, and the maximum-location-number as being at the back of the store.
Locations do not have any width;
for example, within an aisle, location 20 is distance 20 location 0, and is distance 80 from location 100. Locations 0 and 100 are themselves valid locations (you might think of them as endcaps).
You can assume that you begin walking at aisle 1, location 0.
Only consider the distance that you walk up an down the aisles.
Do not include the distance walked from one aisle to the next.
After processing the locations in an aisle, if going either direction results in the same distance,
then you should continue in the direction that you are going (i.e. continue going forward, instead of
reversing).
Sample Run:
Here is a sample run of the program.
Assume that this sample input data is in the file myInput.txt:
Assume that the program is executed,
with the input redirected from the input file, as follows:
rucs% shop < myInput.txt
The resulting output should be:
Continue and enter aisle 2 at 0 and proceed to location 3, traveling 3
Reverse and enter aisle 3 at 0 and proceed to location 16, traveling 19
Continue and enter aisle 5 at 100 and proceed to location 97, traveling 87
Reverse and enter aisle 7 at 100 and proceed to location 1, traveling 102
Continue and enter aisle 8 at 0 and proceed to location 99, traveling 100
Continue and enter aisle 9 at 100 and proceed to location 95, traveling 6
Continue and enter aisle 11 at 0 and proceed to location 2, traveling 97
Reverse and exit aisle 11 at 0 and proceed to cashier, traveling 2
Aisle count: 7
Total distance: 416
Aisle average: 59.4
The last line is different from all others, even though bits of it should align with the previous lines.
It will always contain “exit” and “at 0” and “cashier, ”.
Input specification:
Input is a sequence pairs of natural numbers, each of which represents an aisle and location.
There can be arbitrary white space surrounding each number.
Aisle numbers will not decrease, and within an aisle, location numbers will increase.
Aisle numbers to process will be between 1 and 100 (inclusive); an aisle number 0 marks the end of the data.
location numbers will be between 0 to 100, inclusive.
There will be at least one aisle to process.
End of input will be marked by aisle and location numbers of 0.
Your program does not need to check for errors in the input.
Your program is to read from standard input (which is the default for
Ada.Integer_Text_IO.Get).
Output specification:
For each aisle you are to print a sentence as shown in the example, which includes:
Either the word "Reverse" or "Continue", to indicate whether or not you changed direction
The aisle number
The aisle entry location
The last location visited in the aisle
The distance walked to get that position from the previous position .
After processing all of the aisles, your program should print a summary:
The number of aisles visited.
The total distance traveled.
The average distance traveled per aisle.
Your output should follow the format of the example precisely, including blanks and columns:
Numeric fields of width 5 for aisles.
Numeric fields of width 4 for locations and distances.
Exactly one blank following a colon.
Exactly two blanks between the distance and direction.
A blank line (i.e. containing only a line separator) should appear between the aisle information and the summary.
Your output should contain no other blank lines.
Your program is to have no prompts.
Other points
Use named constants as appropriate.
You must define appropriate subtypes for aisle-numbers and locations. (The aisle subtype may include 0, as a sentinel value.)
You must define a type to represent which end of the aisle you use, rather than 0 or 100. (I called the two values of that type near and far.)
Use good variable-names (“self-documenting”).
Do not store the locations in a collection of any kind (e.g. no arrays and no lists).
Read numbers using numeric I/O, not by reading the input as one or more strings.
Make sure that your program reads from Standard Input, not from a file whose name is
specified in the program.
Your program should be called shop.adb
Suggested development
I suggest writing this program via following the steps:
To help you understand how the program is supposed to work,
create some sample input files, and the desired-output for each.
Specifically: create the files described below, among others.
Write a simple program that just reads and prints each number that is in the input.
Save this version with a unique name.
Read in the input and print each aisle on a separate line,
showing the aisle number followed by the 3 locations for that aisle.
Save this version with a unique name.
Now, solve the 3-location version of the problem.
For this version you will have to figure out
how to know when to continue or to reverse
and how to calculate distance traveled.
To address variable locations per line,
go back to the version created in step 23.
and modify it to work with any number of locations per aisle.
Finally, combine the versions from steps 4 and 5.
It’s clear that these sub-goals don’t actually require more work than “just” writing the program.
But don’t try to continue to later steps without verifying the earlier ones work.
(So many people write a huge chunk of code before compiling and running. So much unnecessary pain…)
3-location version:
One complication in this program is that the number of locations per aisle is unknown.
An easier version (“the 3-location version”) assumes that
there are exactly three locations to visit on each aisle.
Completing this version will earn up to 80% of the total points.
DO NOT attempt to write the full version until after you get the 3-location version working.
This step takes no extra work, and it guides you to a full, working version more quickly.
Grading criteria:
Grading criteria include:
3-location version works works correctly.
Correct aisle numbers, location numbers
Correct aisle distance and direction
Correct aisle count and total distance.
Read until aisle 0, location 0.
I/O uses standard input and standard output and no prompts.
Correct output format and spacing.
Program works correctly with atypical data (i.e. only one aisle and only one location per aisle)
Style: Internal and block documentation and uses appropriate white space
Late homeworks are not accepted, as per standard class policy.
Creating input files:
You are required to create several additional input & output files, representing:
exactly one single aisle (named in1.txt and out1.txt)
exactly two aisles where you will continue (not reverse) after the first (named in2c.txt and out2c.txt)
exactly two aisles where you will reverse (not continue) after the first (named in2r.txt and out2r.txt)
exactly three aisles where you reverse in one aisle and continue in the next (named in3.txt and out3.txt)
Each of these input-files will have exactly 3 items per aisle.
Create these files by hand, before you start coding. If you ask me a question about your program’s algorithm, I won’t answer until you've created these files.
Your data files can be created with any editor (e.g. Notepad, Wordpad, or AdaGide).
But save as plain-text, rather than something like .rtf (“rich text format”).
If your program has trouble reading your data files,
you might also want to double-check that the editor is set to use (say) UTF-8
rather than UTF-16.
You will want to make sure that you create your data file using the same OS that
you use to test your program. When a data file is created on a different OS, the
I/O routines may not correctly handle the end-of-file or end-of-line whitespace.
You do not need to submit your data file(s) beyond the ones above.
Challenge/Extra credit
The above algorithm, although smarter than others, is not optimal.
Show this by providing an input file, and a corresponding output file which gives a shorter result than the algorithm given in this homework.For a small amount of extra credit, show two different ways it can be sub-optimal:
An example where the optimal path visits aisles “out-of-order”.
An example where the optimal path still visits each aisle in ascending order.
Your examples should be as small as you can make them (e.g. only 3 aisles with 3 items total).
No proposed-solutions with more than 7 items will be looked at.
Generic Homework Instructions
Style
Your program should be clear and easy to read.
This includes: proper use of indentation,
and descriptive names (of variables, procedures, types, and named-constants).Your file should include, in a comment near the top,
Your name and email
The course and homework number this file is for.
a link to this homework-assignment
A short description of what the program does.
(Including the link above means that a detailed description isn’t necessary.)
Refer to Dr. Okie’s style guidefor good advice (general, and Ada-specific).
Please ask if you have questions about style.
Redirecting standard input/output
This section is not part of the homework directly.
However, it is useful unix knowledge that assists with this homework, and many other tasks as well.
When a program is run, the OS gives it two files:
its standard-input (“stdin”),
and its standard-output (“stdout”).
(In Java, a program accesses these via System.in and System.out.)
The OS usually sets these files to be the keyboard and the terminal-window.
However, if the OS runs a program and provides it other files instead,
the program itself won’t know;
it just reads from stdin and writes to stdout as usual.
This is a very convenient abstraction:
a programmer can just think of writing a program that reads/writes from the keyboard/screen,
but the OS might later run that file but set its stdout to be a file,
or even an outgoing-network-port, or as another program’s stdin!
Most importantly, this doesn’t require modifying or re-compiling the program in any way.
For this program (and for most any program on a UNIX platform), your program should just read from stdin and write to stdout.
That is, all your I/O will simply use put and get without specifying a file.
Do NOT open any files.
Redirecting from the command-line
The UNIX command-line makes it particularly easy to run a program but
use a different stdin or stdout.
To cause the program to read it’s standard input from a file named myData.txt,
you would type the following on the UNIX command line:
rucs% shop < myData.txt
End-of-File during interactive input
If you want to test your program by giving it input from the keyboard, then
you will need some way of signaling the end of the input, that is,
signaling end of file (though there is no actual file-on-disk in this case).
The way you signal end of file (“EOF”) from a keyboard differs depending on the operating system.
On unix/linux systems (including
bash-for-Windows
and
MacOS Terminal)
type control-D (“^D”) on its own line followed by enter.
From a Windows CMD shell, type control-Z (“^Z”) on its own line followed by enter.
Note that when reading from a file,
the OS recognizes when the input is at the end of file,
and so you do NOT put a control-D or control-Z into the file!
In Ada, the function end_of_file returns true when the end-of-file has been reached.
In Java, Scanner#hasNext() returns false,
and methods like Scanner#nextInt() will throw an exception
(since you are trying to read something after the end-of-file).
Redirecting in an IDE
If you are using AdaGIDE, you must tell it to use redirection and to specify the file:
use Run/Run Options, check the Redirect box, and enter the name of the file
that contains the data.
As far as I know, GPS does not allow redirection. Instead you must use a command line.
Redirecting output, and piping
Similarly, you can use > to redirect a program’s output to a file: rucs% ls *.pdf > all-pdf-names.txt is a quick way to get a file containing the names of all your pdf files (one per line).
You can combine input- and output-redirection, of course:
rucs% shop < in1.txt > actual-out1.txt
As mentioned earlier, you can also instruct the OS to take one program’s output,
and use it as another program’s input.
A common example is sending output to wc, unix’s word-count program:
rucs% ls *.pdf | wc -l
reports how many files end in .pdf.
See a tutorial such as this one for a more general description.
Pro-tip: Piping into diff
An extremely useful unix utility is diff,
which looks for differences between two files.
Usually diff requires two input-file-names on the command-line,
but it interprets the special name - to mean stdin.
Putting this all together: rucs% shop < in3.txt | diff - out3.txt— if the program produces the expected result, nothing is printed!
radford.edu