Corning Community College CSCS2330 Discrete Structures ======PROJECT: SORTING ALGORITHM FUN naive approach (SAF0)====== =====Objective===== Using the TIC-80 fantasy console simulator on your pi, implement a program that performs sorting of a randomized list of values, both displaying an animation of the sort, along with timing and keeping track of the approximate number of steps needed to accomplish the task for variable numbers of non-animated runtimes. The sorting algorithm I'd like for you to produce is that of a naive approach: * not looking up anything about sorting algorithms, how would you implement an algorithm to take an arbitrary list of values and cause them to be arranged in order from least to greatest? In future projects, we will be looking at the specifics of established, existing sorting algorithms. Part of the task here is to establish a baseline: you exploring some processes without existing knowledge or experience in sorting so that you can become more familiar with some of the underlying details of what it means to sort values (so our later explorations make more sense). Additionally, the entire class will be participating in documenting and filling out this project page. It is the responsibility of EACH class member to: * ask copious, clarifying questions (so you can better add content) * craft a coherent and organized document, with information located under pertinent headings * explain the fundamentals of the process, conceptual background, algorithmic approach, and you can even suggest particulars related to TIC-80 (certain functions that might prove useful- individual, unrelated snippets to do things like capturing time or displaying text, etc.) * to get full credit, each individual that submits must perform no fewer than 4 changes to this document (as viewable from the wiki revision system). Failure to do so will result in documentation penalties being applied. =====Specifications===== ====Process==== ==Randomness within Lua== The function `math.random()` within Lua generates a pseudo-random integer within a set bound (if there are no arguments, it defaults to 0-1). This can be used to generate your list of numbers if you want the numbers themselves to be random. The generated integer can be stuck within an array (or just a bunch of fixed integers, your choice) and BOOM, there's your list. To maintain unique values one must constantly be checking if a randomized value //already// exists in the list. Completely random and mostly random have different visuals for your animations, they are both worth trying out to see how that affects the animations. Whichever one you stick with is up to you, but try them both. Surprisingly, one can create a randomized list of numbers in a specific range by not generating random numbers - but generating steadily iterated numbers and storing them in random array indices. This method theoretically saves time on checking to see whether a specific number has already been generated. Traditionally, one would have to increment through the entire array every time a random number is generated. With this method, one only has to check that the random array index is not already storing something or if it is nil. This is because the numbers that are stored increment with each loop - so it is guaranteed to be different. Theoretically, however, this could take just as long as the method where the array index is incremented if there is bad luck with choosing unused array indices. Random values do not just have their usage with random values in an array, but may be used to randomize the algorithm used depending on how the game will work. ==A Sort Synopsis== Broadly, to "sort" is to observe a set of values, knowing their relative significance, and arrange them by some pattern of those relationships. In terms of this project, all that must be done is to arrange a list of values (say, 1-10), which begins in a random order, in least-to-greatest order, which we mathematicians understand as being [1,2,3,4,5,6,7,8,9,10]. That's all well and good, but how do humans //really// go about accomplishing such a task? The easiest way to answer this question may be to bring the problem into the physical realm. Imagine (or physically use) a deck of cards, Ace through Ten. Shuffle them, and arrange them (in the random order produced) in a straight line. Taking a slight detour back into the theoretical realm, understand that a computer is only really capable of "thinking" about one thing at a time - it can only hold one piece of information in its working memory. Given that, when a computer needs to re-arrange something (as has been explored in the various array-manipulators assigned in the past), it must essentially swap two values at a time: retrieve one index, set that index to the other value, and then set the other index to the value retrieved. Likewise, as we go about re-arranging these cards, we will be performing swapping operations, where two cards mutually exchange positions. The purpose of this project is to decide how to go about performing those swaps in a consistent pattern such that by performing the same logic over and over again the cards end up in Ace-Ten order. To illustrate the idea of a swap more clearly: Original: [5,4,1,7,9,10,1,8,2,6,3] Swapped : [4,5,1,7,9,10,1,8,2,6,3] (here, 4 and 5 changed places) Swapped : [4,1,5,7,9,10,1,8,2,6,3] (here, 5 and 1 changed places) Swapped : [1,4,5,7,9,10,1,8,2,6,3] (here, 4 and 1 changed places) ====Display==== **Among** the many possibilities for display, the classic example of variably-sized bars tends to come to mind, and, using the scaling techniques that may have been employed in pnf3, this can be accomplished relatively simply by defining the size and position of some rectangles based on the stored value of array positions and their offsets and scaling them to the size of the screen. After that is initially determined, the scaling value may be applied to allow the user to experience the wonders of the TIC80 sorting program (this should be recalculated once per frame with the current state of the array). Another idea, perhaps more similar to the approaches that many seem to explore in pnf3, would be to arrange the numbers on the screen in some order representing their positions in the array. This can simply be done by having a function print the array indices in order after every swap. In this print function - one can also have some if statements that variably determine the spacing in between the numbers, depending on the size of the randomly generated list. This allows fewer numbers to fill the screen more and allows for more numbers to fit on the screen. If scaling is not your forte, then numbers can be generated from the lowest pixel position possible to the highest pixel position possible. This is essentially the equivalent of scaling since numbers cannot be represented by pixel positions higher than the bounds of the screen. Both scaling and non-scaling algorithms are fine, and lead to essentially the same thing; one may bring more variation over the other though (scaling). =====References===== https://github.com/nesbox/TIC-80/wiki https://hub.xpub.nl/sandbot/PrototypingTimes/tic80-manual.html https://www.lua.org/pil/contents.html http://lua-users.org/wiki/MathLibraryTutorial =====Submission===== To submit the game file, our "tic" file, the file must be added to your lab46 somehow. This can be achieved through FTP software, such as FileZilla, or more easily by putting the file onto your Pi then pushing to your repo and pulling from lab46. //Of course, if you are using the TIC-80 application on your Pi then the file will exist there when saved.// To submit this project using the **submit** tool, run the following command at your lab46 prompt: lab46:~/src/SEMESTER/DESIG/safX$ submit DESIG safX GAMENAME.tic Submitting DESIG project "safX": -> GAMENAME.tic(OK) SUCCESSFULLY SUBMITTED NOTE: "GAMENAME" here is the name of your game. Please do not literally submit a tic file named "GAMENAME", come up with a creative name for your game. I'll be looking for the following: 52:saf0:final tally of results (52/52) *:saf0:no errors, program runs without issue in TIC-80 [13/13] *:saf0:specified algorithm is implemented and functional [13/13] *:saf0:metrics, timing of process is implemented, functional, shown [13/13] *:saf0:project page contributions as per project specifications [13/13] Additionally: * Solutions not abiding by **SPIRIT** of the project will be subject to a 25% overall deduction * Solutions not utilizing descriptive why and how **COMMENTS** will be subject to a 25% overall deduction * Solutions not utilizing **INDENTATION** to promote scope and clarity will be subject to a 25% overall deduction * Solutions lacking **ORGANIZATION** and are not easy to read (within 90 char width) are subject to a 25% overall deduction **How Do?** In your pi's home directory, you can "find" any of your .tic files using: "find . -name *.tic" This lists the paths for these files, enabling you to copy(cp) them into the location of your choice (possibly in SEMESTER/discrete/saf0). From there, you can add and commit this file into your repository, making it available to access on the lab46 servers. Once you push it from the pi and pull it from lab46, you can submit that .tic file in all of its original glory.