User Tools

Site Tools


notes:discrete:fall2021:projects:fom0

This is an old revision of the document!


Corning Community College

CSCS2330 Discrete Structures

PROJECT: Flexible Observant Mind (FOM0)

Objective

Using the TIC-80 fantasy console simulator on your pi, implement a program that performs a sprite-based animated count of a set of LEDs (a minimum of 9) in binary from 0 through the maximum value able to be represented therein.

The three approaches I'd like for you to implement are those of:

  • bitwise-logic
  • remainders (the division approach when converting base 10 to base 2)
  • the “contains” approach, resulting in a progressive subtraction

The universal restriction: you must not have 2^number of LEDs if statements, one per potential number. That is NOT a feasible way to carry out this approach.

You may want to work out these approaches by hand on paper to understand their details and steps of progression, then to implement them.

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

Successive Containment

In this method, one ends up doing some fun progressive subtraction. This method essentially breaks down a decimal number into its binary places and asks for each place whether it exists in that number. In binary, as we've all *probably* learned by now, each place is 2 times that of the previous place. I.E. 16, 8, 4, 2, 1. We start with the greatest place, and work our way down, asking if the decimal number associated with that place exists in the decimal number we are converting to binary and then acting correspondingly. If we were working with 4 bits, it would look something like this:

Given the number 13, we first figure out whether there is a 1 in the 8's place.
Essentially, we ask the question "Is 13 - 8 >= 0?" If so, we do that subtraction,
and then we set that bit (the 8's place) to 1.
    
    1---
    
Now we are left with the remaining 5, and we are now checking the 4's place.
"Is 5 - 4 >= 0?" If so, we subtract and set the bit to 1.
    
    11--
    
With 1 remaining we check the 2's place.
"Is 1 - 2 >= 0?" If so, we subtract and set the bit to 1.
    
    110-
    
With 1 remaining we check the 1's place.
"Is 1 - 1 >= 0?" If so, we subtract and set the bit to 1.
    
    1101

Obviously, this should be scaled up for fom0 purposes, because we will be counting to higher numbers than 15. The logic however remains the same, we just start by subtracting higher numbers for higher places.

Modulo Conversion

In this method, which is at its core a conversion from base 10 to base 2, the input number is repeatedly divided and rounded down by the base until each of the binary digits are obtained and the input becomes 0.

For example:

Given the number 13:

                            13 % 2 = 1
                    13 / 2 = 6 % 2 = 0
            13 / 2 = 6 / 2 = 3 % 2 = 1
    13 / 2 = 6 / 2 = 3 / 2 = 1 % 2 = 1
    
                                  1101
One could shorten it like so:

                        13 / 1 % 2 = 1
                        13 / 2 % 2 = 0
                        13 / 4 % 2 = 1
                        13 / 8 % 2 = 1
    
                                  1101

Since this method relies on repetition until some condition is met, it will occur within a loop after declaring the output variable (which will be a string for this example):

out = ""
while (input != 0):

Within this loop, the first step will be to obtain the smallest binary digit from the input number, which we can do via modulo:

...
  // Insert the smallest obtainable digit at the start of out
  out = (input % 2) + "" + out
  // And truncate input, removing the lower obtained portion
  input = roundDown(input / 2);

By performing that operation until input reaches 0, digits will be successively added until the full binary representation is ascertained.

Bitwise Incrementation

A computer thinks of every number as a binary number. Thus, we can take advantage of that by using some binary specific operations to convert decimal numbers into binary numbers to display. The computer knows the binary conversion of the incrementing counter number, what we need to do is force the extraction of said number.

For example, Given the number 13:

(Remembering that we are just using the AND on ‘13’ But the computer sees it as binary)

13 == 1101
  AND 0001
      ————
      0001

Now we know whether the first bit should be set. From there, we right shift it and AND it against the same 0001:

      0110
  AND 0001
      ————
      0000

Now we know the second bit is zero, so the counter should show that. Next, we right shift and AND yet again.

      0011
  AND 0001
      ————
      0001

Now we have the third bit as being on. Right shift and AND:

      0001
  AND 0001
      ————
      0001

Blazam! Now we have an ‘on’ state for the final bit, and therefore a known state for every bit in the number 13. For larger numbers like the ones we will see on fom0, we will scale this method up.

Display

In terms of display, the basics are as such: two sprites should exist, one which represents an off state (this could also be a blank / no sprite), and one which represents an on state. By showing either of these two sprites as part of some ordered set, a binary number can be represented as if it were 1s and 0s.

References

Submission

I'll be looking for the following:

78:fom0:final tally of results (78/78)
*:fom0:no errors, program runs without issue in TIC-80 [13/13]
*:fom0:specified algorithms are implemented and functional [39/39]
*:fom0:display of sprite based, animated count [13/13]
*:fom0:project page contributions as per project specifications [13/13]

Additionally:

  • Solutions not abiding by SPIRIT of 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
notes/discrete/fall2021/projects/fom0.1635274672.txt.gz · Last modified: 2021/10/26 18:57 by mpronti2