// Name: Abby Jacobs
// Class: CSCI 226
// Date: Spring 2024

// ===========================================================================
// Notes
// ===========================================================================

// Reminder about data types for the Arduino microcontroller:
//   byte             8 bits, unsigned, range is 0 to 255
//   char             8 bits, may or may not be signed, meant to hold ASCII characters
//   unsigned int     16 bits, unsigned, range is 0 to 65535
//   int              16 bits, signed twos complement, range is -32768 to +32767
//   unsigned long    32 bits, unsigned, range is 0 to approx 4billion
//   long             32 bits, signed twos complement, range is approx -2billion to +2billion


// ===========================================================================
// Code for working with binary and hex representations
// ===========================================================================

// print_binary(x, numbits) prints x using binary notation. Only the given
// number of bits are printed, any bits to the left of that are ignored. Note:
// numbits should be between 1 and 32, since x can hold at most 32 bits.
// Examples:
//    print_binary(19, 8) would print "00010011"
//    print_binary(-1, 8) would print "11111111"
//    print_binary(7, 16) would print "0000000000000111"
void print_binary(unsigned long x, int numbits) {
  // Iterate through each position, starting at numbits-1, counting down
  for (int i = numbits-1; i >= 0; i--) {
    // Check if that bit of x is a 1 or a 0, print accordingly
    if ((x & (1<<i)) != 0)
      Serial.print('1');
    else
      Serial.print('0');
  }
  // Print a final newline
  Serial.print("\n");
}

// find_highest_one(x) takes a 16-bit number x and scans it from left to right
// ignoring bits that are zeros and looking for bits that are ones. It returns
// the position of the first "one" found, where the left-most bit is position
// 15, and the right-most bit is position 0. If all the bits are zero, this
// function returns -1 to indicate "not found".
//
// So if x is 2607 in decimal, which is 0x0a2f in hex, or 0000101000101111 in binary,
// then the function should start at position 15 (left-most zero in the binary),
// counting downwards (rightwards) and checking each position until it finds a
// the first 1, in position 11.
//    binary:  0  0  0  0  1  0  1  0  0  0  1  0  1  1  1  1
//  position: 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
//                         ^-- the first 1 in the binary is here, in position 11
// Examples:
//   find_highest_one(19) would return 4, because there is a 1 in position 4
//   find_highest_one(-1) would return 15, because there is a 1 in the left-most position
//   find_highest_one(1) would return 0, because there is a 1 in the right-most position
//   find_highest_one(0) would return -1, because there are no 1's in this number
int find_highest_one(unsigned int x) {
  // TODO (1): Implement this function
  for(int i = 0; i < 16; i++){
    if(x>>(15-i) == 1)
      return 15-i;
  }
  return -1;
}

// count_ones(x) takes a 16-bit number x and counts how many of the bits are
// ones. The result will always be a number between 0 and 16.
//
// So if x is 2607 in decimal, which is 0x0a2f in hex, or 0000101000101111 in binary,
// then the function should scan through the bits and count all the 1's,
// resulting in 7 total 1's found.
//    binary:  0  0  0  0  1  0  1  0  0  0  1  0  1  1  1  1
//                         ^-----^-----------^-----^--^--^--^--- here are the 1's
// Examples:
//   count_ones(19) would return 3, because there are three 1's in "0000000000010011"
//   count_ones(32) would return 1, because there is one 1 in "0000000000100000"
//   count_ones(0) would return 0, because there are no 1's in that number
//   count_ones(-1) would return 16, because all the bits of that number are 1's
int count_ones(unsigned int x) {
  // TODO (2): Implement this function
  int n = 0;
  for(int i = 0; i < 16; i++){
    if(x & (1<<i)){
      n++;
    }
  }
  return n;
}

// extract_nibble(x, pos) takes a 16-bit number x, which consists of four
// nibbles (four 4-bit groups, or four hex digits), and it returns one of
// those nibbles as a result. The pos parameter is a number from 0 to 3
// indicating which nibble to return, 0 for the right-most nibble, 3 for the
// left-most, etc.
//
// So if x is 2607 in decimal, which is 0x0a2f in hex, or 0000101000101111 in binary,
// then there are four possible nibbles to choose from:
//        hex:     0    a    2    f
//     binary:  0000 1010 0010 1111
//   position:     3    2    1    0
//
// Examples:
//   extract_nibble(2607, 0) would return 15, or 0xf (see above diagram)
//   extract_nibble(2607, 1) would return 2 (see above diagram)
//   extract_nibble(2607, 2) would return 10, or 0xa (see above diagram)
//   extract_nibble(2607, 3) would return 0 (see above diagram)
//   extract_nibble(19, 0) would return 3, because the last 4 bits of 19 are "0011"
//   extract_nibble(19, 1) would return 1, because the next 4 bits of 19 are "0001"
//   extract_nibble(19, 2) would return 0, because the rest of the bits of 19 are all zeros.
//   extract_nibble(-1, 2) would return 15, because the rest of the bits of 19 are all zeros.
int extract_nibble(unsigned long x, int pos) {
  // TODO (3): Implement this function
  return (x>>(pos*4))&0x0f;
}

// print_hex(x, numbits) prints x using hexadecimal notation, with an "0x"
// prefix. Only the given number of bits (rounded up to a multiple of 4) are
// printed, any bits to the left of that are ignored. Note: numbits should be a
// multiple of 4 between 4 and 32, since x can hold at most 32 bits.
// Examples:
//    print_hex(19, 8) would print "0x13"
//    print_hex(-1, 8) would print "0xff"
//    print_hex(-1, 16) would print "0xffff"
//    print_hex(7, 32) would print "0x00000007"
void print_hex(unsigned long x, int numbits) {
  char *hex_digit = "0123456789ABCDEF";
  Serial.print("0x");
  for (int i = (numbits+3)/4 - 1; i >= 0; i--) {
    int h = extract_nibble(x, i);
    Serial.print(hex_digit[h]);
  }
  Serial.print("\n");
}

// get_int_from_user() waits for the user to type a number using the Serial
// console (the regular keyboard, not the "hex keypad"), and returns this as the
// result. The user should enter the number in regular decimal notation, with
// positive or negative as desired, e.g. "125" or "-99". The allowable range is
// -32768 to +32767, because that's the range for int variables.
int get_int_from_user() {
  // Wait for user to type something that looks like an integer
  Serial.setTimeout(20000);
  while (true) {
    int ch = Serial.peek();
    if (ch == '-' || ch == '+' || (ch >= '0' && ch <= '9'))
      break;
    if (ch < 0)
      delay(100); // no characters available, wait a while
    else
      Serial.read(); // unrecognized character, read and discard it
  }
  int result = Serial.parseInt();
  Serial.readStringUntil('\n');
  return result;
}

// show_operation() is used for testing. It prints the title, then prints x, y,
// and the result all in 16-bit binary, all in a pretty format.
void show_operation(char *title, unsigned int x, unsigned int y, char *operation, unsigned int result) {
  Serial.print("Example of ");
  Serial.println(title);
  Serial.print("      x is ");
  print_binary(x, 16);
  Serial.print("      y is ");
  print_binary(y, 16);
  Serial.print("  x ");
  Serial.print(operation);
  Serial.print(" y is ");
  print_binary(result, 16);
}

// do_conversion_demo() is used for testing. It calls all of the above functions
// and prints the results.
void do_conversion_demo() {
  Serial.print("Enter a number, in decimal, between -32768 and +32767:\n");
  int x = get_int_from_user();

  // Print the number in decimal, hex, and binary.
  Serial.print("In decimal, that is: ");
  Serial.println(x); // prints in decimal, by default
  Serial.print("In binary, that is : ");
  print_binary(x, 16);
  Serial.print("In hex, that is    : ");
  print_hex(x, 16);

  // Print some information about the number.
  Serial.print("Number of ones     : ");
  Serial.println(count_ones(x));
  Serial.print("Position of highest one : ");
  Serial.println(find_highest_one(x));

  // Do some operations, like shifting, negation, and complement.
  Serial.print("    ~x produces decimal ");
  Serial.print(~x);
  Serial.print(" which is binary ");
  print_binary(~x, 16);
  Serial.print("    -x produces decimal ");
  Serial.print(-x);
  Serial.print(" which is binary ");
  print_binary(-x, 16);
  Serial.print("x << 1 produces decimal ");
  Serial.print(x << 1);
  Serial.print(" which is binary ");
  print_binary(x << 1, 16);
  Serial.print("x >> 1 produces decimal ");
  Serial.print(x >> 1);
  Serial.print(" which is binary ");
  print_binary(x >> 1, 16);

  // Do some bitwise operations using a second number.
  int y = 0x060f; // arbitrary example, feel free to change this

  show_operation("bitwise AND", x, y, "&", x & y);
  show_operation("bitwise OR", x, y, "|", x | y);
  show_operation("bitwise XOR", x, y, "^", x ^ y);
}


// ===========================================================================
// Code to generate random numbers
// ===========================================================================

// This 16-bit variable keeps track of the most recent random value generated.
unsigned int randval = 0xcafe; // Initialize to arbitrary 16-bit value to start.

// prng_update() takes the existing randval and updates it using the "middle
// square" method, which works as follows:
//      Example      Explanation
//       0xcafe      Step 0: Take the current randval variable, a 16-bit value.
//   0x0000cafe      Step 1: Put that value into a 32-bit variable.
//   0xa0f5d404      Step 2: Square that new variable. Here, 0xcafe * 0xcafe = 0xa0f6d404.
//       0xf5d4      Step 3: Extract the middle 16 bits, and put this into the randval variable.
// This function returns nothing, it only updates the randval variable.
void prng_update() {
  unsigned long var = randval; // Take 16-bit randval variable, put into a new 32-bit variable.
  // TODO (4) Implement the rest of the middle square algorithm.
  var = var*var;
  var = var&0x00ffff00;
  randval = var>>8;


  // Special case: if randval ever becomes zero, change it to something else,
  // otherwise it would get stuck at zero forever more.
  if (randval == 0)
    randval = millis();
}

// get_random_4bit_num() updates the randval variable, then uses it to compute a
// random-seeming 4 bit value (a number from 0 to 15). To get from the 16-bit
// randval value down to a 4-bit value, it uses XOR to combine each 4-bit nibble. So
// it takes the top 4 bits, XORs with the next 4 bits, XORs with the next 4
// bits, and finally XORs with the last 4 bits, to produce a 4 bit result.
// Example: If randval happens to be 0xf5d4 after calling prng_update, this
// function would...
//       take the nibble in the 3rd position:  f  or 1111
//       take the nibble in the 2nd position:  5  or 0101
//       take the nibble in the 1st position:  d  or 1101
//       take the nibble in the 0th position:  4  or 0100
//            then XOR all of those together:  3  or 0011, this is the result
// Note: it doesn't matter what order you XOR the parts.
int get_random_4bit_num() {
  prng_update();
  // TODO (5) Compute and return a 4-bit number using the updated randval value.
  int randomNum = extract_nibble(randval, 3)^extract_nibble(randval, 2)^extract_nibble(randval, 1)^extract_nibble(randval, 0);
  return randomNum;
}

// do_rand_demo() is used for testing. It calls the above functions and prints
// the results.
void do_rand_demo() {
  Serial.print("Initial randval is "); print_hex(randval, 16);
  prng_update();
  Serial.print("Updated randval is "); print_hex(randval, 16);
  prng_update();
  Serial.print("Updated randval is "); print_hex(randval, 16);
  prng_update();
  Serial.print("Updated randval is "); print_hex(randval, 16);
  prng_update();
  Serial.print("Updated randval is "); print_hex(randval, 16);

  Serial.print("Some random 4-bit numbers:");
  for (int i = 0; i < 32; i++) {
    int fourbit = get_random_4bit_num();
    Serial.print(" ");
    Serial.print(fourbit);
  }
  Serial.print("\n");
}

// ===========================================================================
// Code to control the colored LEDs
// ===========================================================================

// turn_on_green_led() will turn ON the green LED. This is accomplished by
// setting bit 2 of the PORTD variable to be zero. The PORTD variable is a
// special 8-bit variable that is connected to the colored lights, where each
// bit of the variable has a specific meaning:
//
//         +-------+-------+-------+-------+-------+-------+-------+-------+
// PORTD:  |       |       | yellow| blue  |  red  | green |       |       |
//         +-------+-------+-------+-------+-------+-------+-------+-------+
// position:   7      6        5       4       3       2       1       0
//
// Note: The LEDs here are "active low", meaning that the behavior is the
// opposite of what you might normally expect:
//   * putting a 1 in bit position 2 turns OFF the green LED
//   * putting a 0 in bit position 2 turns ON the green LED
// Sorry, that's just how these are wired up.
// Also: Do NOT change any of the bits here except the bit in position 2.
void turn_on_green_led() {
  Serial.print("Green Light ON\n");
  // TODO (6): Change PORTD so that bit position 2 is a zero, but all other
  // bits remain how they were. Hint: A single bitwise operation with a
  // well-chosen constant is all that is needed here.
  PORTD = PORTD & 0b11111011;

}

// turn_off_green_led() will turn OFF the green LED. This is accomplished by
// setting bit 2 of the PORTD variable to be one, essentially the opposite of
// the above function.
void turn_off_green_led() {
  Serial.print("Green Light OFF\n");
  // TODO (7): Change PORTD so that bit position 2 is a one, but all other
  // bits remain how they were. Hint: A single bitwise operation with a
  // well-chosen constant is all that is needed here.
  PORTD = PORTD | 0b00000100;

}

// toggle_four_leds() will toggle all four colored LEDs, so that whichever ones
// used to be ON are now turned OFF, and vice versa.
// setting bit 2 of the PORTD variable to be one, essentially the opposite of
// the above function.
void toggle_four_leds() {
  // TODO (8): Change PORTD so that bit positions 5, 4, 3, and 2 all become the
  // opposite of whatever they were, but all other bits remain how they were. 
  // Hint: A single bitwise operation with a well-chosen constant is all that is
  // needed here.
PORTD = PORTD ^ 0b00111100;

}

// setfour_leds(x) will change all four colored LEDs, so that they are either ON
// or OFF according to the lowest four bits in x. 
// Examples:
//   set_four_leds(0x0f) should turn ON all four LEDs by changing bits 5, 4, 3,
//      and 2 of PORTD so they are all ZEROs.
//   set_four_leds(0x00) should turn OFF all four LEDs by changing bits 5, 4, 3,
//      and 2 of PORTD so they are all ONEs.
//   set_four_leds(0x08) should turn ON one of the four LEDs by changing bit 5
//      so it is a ZERO, and it should turn OFF the other three LEDs by
//      changing bits 4, 3, and 2 so they are all ONEs.
// Hint:
//   Suppose x is 0x0d, or 1101 in binary, so we want 3 LEDs ON, one LED OFF.
//   And suppose PORTD is this initially : xx0110xx where "x" means "leave alone",
//     and these are bits we must change :   ^^^^
//   Change PORTD so it looks like this  : xx0000xx
//   Then change x so that it looks like : 00110100
//   Then combine the two to get         : xx1101xx
//   And make this the new value of PORTD.
void set_four_leds(int x) {
  // TODO (9): Change PORTD so that bit positions 5, 4, 3, and 2 each become
  // either ZERO or ONE, depending on the values in the lowest four bits of x.
  // Hint: This one will require several bitwise operations to ...
  //    - first change PORTD so all the affected bits are ZEROs, leaving other
  //      bits unchanged
  //    - use the value of x to modify PORTD so some or all of the affected bits
  //      get changed into ONEs, again leaving all other bits unchanged.
  PORTD = PORTD&0xc3;
  x = x<<2;
  PORTD = PORTD | x;

}

// turn_on_some_leds(n) will change the four colored LEDs so that n of them are
// turned ON, and the others are turned OFF. The value of n should be between 0
// and 4.
// Examples:
//   turn_on_some_leds(0) will turn on OFF all colored LEDs
//   turn_on_some_leds(1) will turn on one colored LED, and turn the rest OFF
//   turn_on_some_leds(2) will turn on two colored LEDs, and turn the rest OFF
//   turn_on_some_leds(3) will turn on three colored LEDs, and turn the rest OFF
//   turn_on_some_leds(4) will turn on three colored LEDs, and turn the rest OFF
void turn_on_some_leds(int n) {
  // Trick: If n = 3, then 0xf0 >> 3 will be 00011110
  // And if we then bitwise-AND with 0xf     00001111
  // we will end up with:                    00001110
  // which has exactly 3 bits turned ON, as desired..
  set_four_leds((0xf0 >> n) & 0xf);
}

// do_blink_demo() is used for testing. It calls some of the above functions.
void do_blink_demo() {
  for (int i = 0; i < 5; i++) {
    delay(1000); // pause for 1000 ms, or 1 second
    turn_on_green_led();
    delay(1000); // pause for 1000 ms, or 1 second
    turn_off_green_led();
  }
}

// do_animation_demo() is used for testing. It calls most of the above functions.
void do_animation_demo() {
  // Start with all LEDs OFF.
  set_four_leds(0x0);
  // Toggle all of them a few times.
  for (int i = 0; i < 16; i++) {
    toggle_four_leds();
    delay(150); // pause for 150 ms, or 0.15 seconds
  }
  // Then show the pattern given by the rainbow array, a few times.
  byte rainbow[] = { 0x8, 0xc, 0x6, 0x3, 0x1, 0x3, 0x6, 0xc };
  for (int repeat = 0; repeat < 4; repeat++) {
    for (int i = 0; i < 8; i++) {
      set_four_leds(rainbow[i]);
      delay(150);
    }
  }
  // Then show the numbers 0 to F in binary on the colored LEDs, slowly.
  for (int num = 0; num < 16; num++) {
    set_four_leds(num);
    delay(700); // pause for 700 ms, or 0.7 seconds
  }
  // Then show a growing and shrinking bar of lights a few times.
  for (int repeat = 0; repeat < 4; repeat++) {
    turn_on_some_leds(0); delay(200);
    turn_on_some_leds(1); delay(200);
    turn_on_some_leds(2); delay(200);
    turn_on_some_leds(3); delay(200);
    turn_on_some_leds(4); delay(200);
    turn_on_some_leds(3); delay(200);
    turn_on_some_leds(2); delay(200);
    turn_on_some_leds(1); delay(200);
  }

  // Then show some random patterns.
  for (int i = 0; i < 32; i++) {
    set_four_leds(get_random_4bit_num());
    delay(150);
  }
}

// ===========================================================================
// Code to control the 8x8 matrix of LEDs
// ===========================================================================

// matrix_set_row(rownum, data) follows a special protocol to send data to the
// 8x8 LED matrix. The rownum should be a number from 0 (the top row) to 7 (the
// bottom row), and data is an 8-bit value that conrols the LEDs in that row.
// Examples:
//   matrix_set_row(3, 0xff) will turn ON all the LEDs in row 3
//   matrix_set_row(7, 0x00) will turn OFF all the LEDs in the bottom row, row 7
//   matrix_set_row(0, 0xc1) will turn ON all the left 2 LEDs and the rightmost
//     LED in the top row, row 0, and turn OFF all the other LEDs in that row
void matrix_set_row(byte rownum, byte data) {
  byte x;
  PORTB = PORTB & ~0x18; // drive MATRIX_CS low, drive MATRIX_CLK low
  // Send rownum+1, one bit at a time, MSB first.
  x = rownum+1;
  for (int i = 7; i >= 0; i--) {
    PORTB = (PORTB & ~0x04) | (((x >> i) & 1) << 2); // set MATRIX_DATA
    PORTB = PORTB | 0x10; // turn MATRIX_CLK on
    PORTB = PORTB & ~0x10; // turn MATRIX_CLK off
  }
  // Send data, one bit at a time, LSB first.
  x = data;
  for (int i = 0; i < 8; i++) {
    PORTB = (PORTB & ~0x04) | (((x >> i) & 1) << 2); // set MATRIX_DATA
    PORTB = PORTB | 0x10; // turn MATRIX_CLK on
    PORTB = PORTB & ~0x10; // turn MATRIX_CLK off
  }
  PORTB = PORTB | 0x08; // drive MATRIX_CS high
}

// matrix_display(pixels) will change all 8x8 LEDs. The pixels argument
// is an array of eight bytes, one for each of the eight rows of LEDs.
// So pixels[0] is an 8-bit value to control the top row of LEDs.
// So pixels[1] is an 8-bit value to control the next row of LEDs.
// And pixels[2] is an 8-bit value to control the third row of LEDs.
// ...
// And pixels[7] is an 8-bit value to control the bottom row of LEDs.
void matrix_display(byte pixels[]) {
  for (int row = 0; row < 8; row++) {
    matrix_set_row(row, pixels[row]);
  }
}

// draw_down_arrow() draws a big arrow, pointing down, on the LED matrix.
void draw_down_arrow() {
  matrix_set_row(0, 0x00);  //   _ _ _ _ _ _ _ _    // note: using _ instead of 0
  matrix_set_row(1, 0x38);  //   _ _ 1 1 1 _ _ _
  matrix_set_row(2, 0x38);  //   _ _ 1 1 1 _ _ _
  matrix_set_row(3, 0x38);  //   _ _ 1 1 1 _ _ _
  matrix_set_row(4, 0xfe);  //   1 1 1 1 1 1 1 _
  matrix_set_row(5, 0x7c);  //   _ 1 1 1 1 1 _ _
  matrix_set_row(6, 0x38);  //   _ _ 1 1 1 _ _ _
  matrix_set_row(7, 0x10);  //   _ _ _ 1 _ _ _ _
}

// draw_happy_icon() should draw some happy picture on the LED matrix.
void draw_happy_icon() {
  // TODO (10): Implement this function. See previous function for an example.
  matrix_set_row(0, 0x00);
  matrix_set_row(1, 0x24);
  matrix_set_row(2, 0x00);
  matrix_set_row(3, 0x81);
  matrix_set_row(4, 0x42);
  matrix_set_row(5, 0x3c);
  matrix_set_row(6, 0x00);
  matrix_set_row(7, 0x00);
  matrix_set_row(8, 0x00);
}

// draw_sad_icon() should draw some sad, animated, picture on the LED matrix.
void draw_sad_icon_animated() {
  // TODO (11): First, fill in the array with data to draw some image.
  byte pixels[] = { 0x00, 0x24, 0x00, 0x3c, 0x42, 0x00, 0x00, 0x00 };

  matrix_display(pixels); // draw the initial image
  // Then do several more steps to create an animation effect.
  for (int steps = 0; steps < 16; steps++) { 
    // For each row in the pixels array...
    for (int row = 0; row < 8; row++) {
      // TODO (12): modify the pixles[row] value in some way using bitwise
      // operations. For example, "rotate" the eight bits, so the leftmost bit
      // becomes the rightmost bit, and the other seven bits all move one
      // position to the left.
      if(row>4 && row<7)
        pixels[row] = pixels[row]^0x42;
    }
    matrix_display(pixels); // display the new picture
    delay(200); // pause for 200 ms, or 0.2 seconds
  }
}

// do_matrix_animation() is used for testing. It calls the above functions.
void do_matrix_animation() {

  // Start by displaying various binary patterns on the LED matrix.
  matrix_set_row(0, 0x08);
  matrix_set_row(1, 0x19);
  matrix_set_row(2, 0x2a);
  matrix_set_row(3, 0x3b);
  matrix_set_row(4, 0x4c);
  matrix_set_row(5, 0x5d);
  matrix_set_row(6, 0x6e);
  matrix_set_row(7, 0x7f);
  delay(1000);

  // Next, draw a big arrow
  draw_down_arrow();
  delay(1000);

  // Next, draw a happy image
  draw_happy_icon();
  delay(1000);

  // Next, draw an arrow, then have it "fade to static" by randomly toggling pixels
  byte arrow[] = { 0x08, 0x0c, 0xfe, 0xff, 0xfe, 0x0c, 0x08, 0x00 };
  matrix_display(arrow);
  for (int step = 0; step < 16; step++) {
    for (int row = 0; row < 8; row++) {
      // Explanation: pick a random 4-bit number (range 0 to 15),
      // then bitwise-AND with 0x7 to produce a 3-bit number (range 0 to 7),
      // then shift a 1 by this amount to get an 8-bit value with a 1 in a random position,
      // then XOR with the row of pixels to toggle that bit ON or OFF.
      arrow[row] = arrow[row] ^ (1 << (get_random_4bit_num() & 0x7));
    }
    matrix_display(arrow);
    delay(200);
  }

  // Next, draw a sad face, animated
  draw_sad_icon_animated();
}

// ===========================================================================
// Code for a tetris-like game
// ===========================================================================

// The game board is eight rows, each with 8-bits (one byte) of data.
byte tetris_board[8];

// get_tetris_piece_from_user() waits for the user to type a number (in decimal)
// using Serial input (regular keyboard, not the keypad). Only numbers between 1
// and 255 are accepted.
byte get_tetris_piece_from_user() {
  while (true) {
    int result = get_int_from_user();
    if (result >= 1 && result <= 255) {
      Serial.print("Dropping byte: ");
      print_hex(result, 8);
      return result;
    }
    Serial.print("Sorry, ");
    Serial.print(result);
    Serial.print(" is not a valid unsigned byte.\n");
  }
}

// bytes_collide(x, y) checks whether or not the bits in x and in y "collide" in
// the sense that they both have a 1 in the same position. This is used by the
// tetris game to check if a piece (x) collides with or fits nicely into the
// gaps in some row (y).
//   bytes_collide(00111100,
//                 11000001)
//                 would return false, because none of the 1's overlap.
//   bytes_collide(10110001,
//                 01000010)
//                 would return false, because none of the 1's overlap.
//   bytes_collide(00111100,
//                 01001000)
//                 would return true, because both have a 1 in the same position
//                 near the middle, position 4, the 8's place in binary.
//   bytes_collide(11000011,
//                 00010001)
//                 would return true, because both have a 1 in the same position
//                 at the far right side, position 0, the ones place in binary.
bool bytes_collide(byte x, byte y) {
  // TODO(13): Implement this function. One bitwise operation is enough here.
  x = x&y;
  return (x & y) != 0x00;
}

// merge_bytes(x, y) combines the bits of x and y together, keeping all the 1s,
// as if x and y were two puzzle pieces fitting together. This is used by the
// tetris game to combine a falling piece (x) with an existing row (y).
// Examples:
//   merge_bytes(00111100,
//               11000001) should combine these and
//        return 11111101 as the result.
//   merge_bytes(10110001,
//               01000010) should combine these and
//        return 11110011 as the result.
byte merge_bytes(byte x, byte y) {
  // TODO(14): Implement this function. One bitwise operation is enough here.
  y = (x | y);
  return (x | y);
}

// tetris() plays a tetris-like game. The bottom half of the screen is filled
// with random bits arranged in rows. The user must enter bytes, in decimal,
// which are then shown as binary numbers that fall from the top row down
// towards the bottom row. These bits must fit into the gaps in the existing
// rows to fill up each row.
void tetris() {
  Serial.print("Welcome to binary tetris!\n");

  // clear the board
  memset(tetris_board, 0, 8);

  // initialize the bottom four rows to random data
  for (int row = 4; row < 8; row++) {
    while (tetris_board[row] == 0 || tetris_board[row] == 0xff) {
      // TODO (15): initialize tetris_board[row] to a random 8-bit number
      // between 1 and 254. Note: 00000000 should not be chosen, because that
      // makes an empty row. Similarly, 11111111 should not be chosen, as that
      // would be a completely filled row.
      tetris_board[row] = get_random_4bit_num()+get_random_4bit_num();
    }
  }

  // show the initialized board
  matrix_display(tetris_board);

  Serial.print("Use the keyboard to enter decimal numbers (1 to 255)...\n");

  while (true) {
    byte piece = get_tetris_piece_from_user();

    // animate piece downwards until we reach the bottom or a non-empty row
    int row = 0;
    while (row < 7 && tetris_board[row] == 0x00) {
      tetris_board[row] = piece;
      matrix_display(tetris_board);
      delay(500);
      tetris_board[row] = 0;
      matrix_display(tetris_board);
      row++;
    }
    if (bytes_collide(piece, tetris_board[row])) {
      // Piece does NOT fit in this row...
      if (row == 0) {
        // ... but this is the top row, so game over.
        Serial.print("Sorry, piece does not fit. Game over.\n");
        return;
      } else {
        // ... so put it in the row above this one.
        tetris_board[row-1] = piece;
        matrix_display(tetris_board);
      }
    } else {
      // Piece DOES fit in this row, so merge it in.
      tetris_board[row] = merge_bytes(piece, tetris_board[row]);
      matrix_display(tetris_board);
      // Check if this row is entirely full.
      if (tetris_board[row] == 0xff) {
        delay(200); 
        tetris_board[row] = 0;
        matrix_display(tetris_board);
        delay(200); 
        tetris_board[row] = 0xff;
        matrix_display(tetris_board);
        delay(200); 
        tetris_board[row] = 0;
        matrix_display(tetris_board);
        if (row == 7) {
          Serial.print("You win!\n");
          draw_happy_icon();
          return;
        }
      }
    }
  }
}

// ===========================================================================
// Code for the hex-invaders game.
// ===========================================================================

// Each invader alien is a non-zero 4 bit number. There are 8 rows, each row has
// up to two invaders, one in the left half of the row, one in the right half.
// The board can fit up to 16 invaders, but normally would only have a few
// invaders with the rest of the places set to all zeros.
// Example with 5 alien invaders:
//     +------+------+------+------+------+------+------+------+
//     |    alien invader 1        |                           |
//     +------+------+------+------+------+------+------+------+
//     |                           |    alien invader 2        |
//     +------+------+------+------+------+------+------+------+
//     |                           |                           |
//     +------+------+------+------+------+------+------+------+
//     |    alien invader 3        |    alien invader 4        |
//     +------+------+------+------+------+------+------+------+
//     |                           |                           |
//     +------+------+------+------+------+------+------+------+
//     |                           |                           |
//     +------+------+------+------+------+------+------+------+
//     |                           |    alien invader 5        |
//     +------+------+------+------+------+------+------+------+
//     |                           |                           |
//     +------+------+------+------+------+------+------+------+
//
byte alien_board[8]; // keeps track of the invaders on the screen
int num_aliens;      // how many invaders are on the screen
int points;          // one point for each invader intercepted
int level;           // game level, starts at 1, increments once for every 15 points
int lives;           // number of mistakes allowed remaining
unsigned long last_update; // a timestamp, used for smoother animation

// show_lives(n) prints a message showing how many lives are left, and also
// turns on n of the colored LEDs to show that same information.
void show_lives(int n) {
  Serial.print("You have ");
  Serial.print(n);
  Serial.print(" lives left!\n");
  turn_on_some_leds(n);
}

// initialize_hex_invaders() initializes all the variables for a new game.
void initialize_hex_invaders() {
  Serial.print("Starting game, get ready!\n");
  Serial.print("Use the keypad with the mouse to click hex digits,\n");
  Serial.print("or select the keypad then type hex digits with keyboard.\n");

  draw_happy_icon();
  delay(500);

  lives = 4;
  points = 0;
  level = 1;
  num_aliens = 0;
  memset(alien_board, 0, 8); // set all bytes to zero

  // animinate the colored lights to show how many lives are left
  for (int n = 0; n <= 4; n++) {
    turn_on_some_leds(n);
    delay(500);
  }

  // almost ready to start
  draw_down_arrow();
  delay(300);

  // show the initial (blank) board
  matrix_display(alien_board);
}

// hex_invaders() plays the alien invader game.
void hex_invaders() {

  initialize_hex_invaders();
  last_update = millis();

  while (true) {
    // Deploy a new alien invader, if needed
    if (num_aliens < level && ((alien_board[0] & 0xf0) == 0 || (alien_board[0] & 0x0f) == 0)) {
      // Pick a new 4-bit random number, but not zero
      byte m = 0;
      while (m == 0) {
        m = get_random_4bit_num();
      }
      // Merge the 4-bit value of m into either the left half or the right half
      // of alien_board[0]. But be careful: half of that row might already have
      // an alien invader present. So if there is an invader already in the left
      // half of alien_board[0], then merge m into the right half. If there is
      // an invader already on the right side, then merge m into the left side.
      // If the row is entirely empty, then pick left or right half at random.
      if (alien_board[0] == 0x00) {
        // TODO (16): Merge m into either the left or right half, at random.
        if(alien_board[0] == 0x00){
          if(get_random_4bit_num()%2==0){
            alien_board[0]=merge_bytes(m<<4, alien_board[0]);
          }
          else{
            alien_board[0]=merge_bytes(m, alien_board[0]);
          }
        }
      } else if ((alien_board[0] & 0xf0) == 0) {
        // TODO (17): Merge m into the appropriate half of alien_board[0].
        alien_board[0]=merge_bytes(m<<4, alien_board[0]);
      } else {
        // TODO (18): Merge m into the appropriate half of alien_board[0].
        alien_board[0]=merge_bytes(m, alien_board[0]);
      }
      num_aliens++;
    }

    // Get user input from keypad
    int user_input = get_keypad_hex_digit();
    if (user_input > 0) {
      int hit = 0;
      // Check each row to see if user intercepted an alien invader.
      for (int row = 7; row >= 0 && !hit; row--) {
        // Check right half of row
        if ((alien_board[row] & 0x0f) == user_input) {
          // Hit! Erase the right half of the row.
          alien_board[row] &= 0xf0;
          hit = 1;
        }
        // Otherwise, check left half of row
        else if ((alien_board[row] & 0xf0) == (user_input << 4)) {
          // Hit! Erase the left half of the row.
          alien_board[row] &= 0x0f;
          hit = 1;
        }
      }
      if (hit) {
        // Upon a hit, update the score and print status.
        matrix_display(alien_board);
        num_aliens--;
        Serial.println(num_aliens);
        points++;
        Serial.print("You have ");
        Serial.print(points);
        Serial.print(" points!\n");
        if ((points & 0xf) == 0) {
          level++;
          Serial.print("You reached level ");
          Serial.print(level);
          Serial.print("!\n");
        }
      } else {
        // Upon a miss, update the lives variable.
        lives--;
        show_lives(lives);
      }
    }

    // Animate the aliens so they move down the screen
    unsigned long time_now = millis();
    if ((time_now - last_update) >= 1500) {
      // It has been 500 ms, or 0.5 seconds, since the last screen update
      last_update = time_now;
      // Checkk for aliens at bottom of screen.
      if (alien_board[7] != 0) {
        // One or two alien invaders have reached the bottom of the screen.
        // Update the lives variable, and update the alien count.
        lives--;
        show_lives(lives);
        if ((alien_board[7] & 0xf0) != 0 && (alien_board[7] & 0x0f) != 0) {
          num_aliens -= 2;
        } else {
          num_aliens--;
        }
      }
      // Move all other aliens down a row.
      for (int row = 7; row > 0; row--) {
        alien_board[row] = alien_board[row-1];
      }
      // Clear the top row.
      alien_board[0] = 0;
      // Display the updated board.
      matrix_display(alien_board);
    }

    // Check for game-over condition.
    if (lives == 0) {
      Serial.print("Game over!\n");
      draw_sad_icon_animated();
      return;
    }
  }
}

// ===========================================================================
// Code for the main menu
// ===========================================================================

// loop() is is called repeatedly, automatically, as fast as the Arduino can go.
void loop() {
  Serial.print("Type an option, then press enter ...\n");
  Serial.print("  c: demonstration of hex/binary/integer conversions\n");
  Serial.print("  b: blink the green LED a few times\n");
  Serial.print("  r: generate some random numbers\n");
  Serial.print("  a: make a pretty animation on the colored LEDs\n");
  Serial.print("  m: make a pretty animation on the 8x8 LED matrix\n");
  Serial.print("  t: play a tetris-like game\n");
  Serial.print("  h: play the hex-invaders game (or press 0 on keypad)\n");

  while (true) {
    char b = 0;
    while (b == 0) {
      if (get_keypad_hex_digit() == 0)
        b = 'h';
      else if (Serial.available())
        b = Serial.read();
    }
    if (b == '\r' || b == '\n' || b == ' ' || b <= 0 || b > 127) {
      // simply ignore spaces and newlines, or anything out of the ASCII range
      continue;
    }
    Serial.print("You picked: ");
    Serial.println(b);
    if (b == 'c') {
      do_conversion_demo();
      return;
    } else if (b == 'b') {
      do_blink_demo();
      return;
    } else if (b == 'r') {
      do_rand_demo();
      return;
    } else if (b == 'a') {
      do_animation_demo();
      return;
    } else if (b == 'm') {
      do_matrix_animation();
      return;
    } else if (b == 't') {
      tetris();
      return;
    } else if (b == 'h') {
      hex_invaders();
      return;
    } else {
      Serial.print("I don't understand '");
      Serial.print(b);
      Serial.print("' (");
      Serial.print((int)b);
      Serial.print(").\n");
    }
  }
}

// ===========================================================================
// Hardware Configuration and Setup
// ===========================================================================

// Connected to pins 2, 3, 4, and 5 are four colored LEDs. These LEDs are
// "active low", meaning that the behavior is the opposite of what you might
// normally expect:
//   * an output of zero means "turn the light ON"
//   * an output of one means "turn the light OFF"
#define LED_G      (2)
#define LED_R      (3)
#define LED_B      (4)
#define LED_Y      (5)

// Connected to pins 10, 11, and 12 are sixteen LEDs, arranged in a 8x8 grid (or
// "matrix"). To control each of these sixteen LEDs requires sending a certain
// sequence of signals on these three output pins. The exact protocol is
// detailed below.
#define MATRIX_DATA  (10)
#define MATRIX_CS    (11)
#define MATRIX_CLK   (12)

// Connected to pins 9, 6, 14, 15, 16, 17, 18, and 19 is a keypad with sixteen
// buttons, arranged in a 4x4 grid with labels like an old-style telephone. To
// check whether a button is being pressed requires sending a certain pattern of
// bits to the COL outputs, then reading data from the ROW inputs.
#define KEYPAD_ROW1  (9)
#define KEYPAD_ROW2  (6)
#define KEYPAD_ROW3  (14) // also known as A0
#define KEYPAD_ROW4  (15) // also known as A1
#define KEYPAD_COL1  (16) // also known as A2
#define KEYPAD_COL2  (17) // also known as A3
#define KEYPAD_COL3  (18) // also known as A4
#define KEYPAD_COL4  (19) // also known as A5

// setup() runs once, automatically, when the Arduino boots, to initialize the
// program and configure the Arduino hardware pins to act as inputs or outputs.
void setup() {

  // Configure the four colored LED pins as outputs.
  pinMode(LED_G, OUTPUT);
  pinMode(LED_R, OUTPUT);
  pinMode(LED_B, OUTPUT);
  pinMode(LED_Y, OUTPUT);

  // Configure the LED matrix pins as outputs, and set them to default values.
  pinMode(MATRIX_DATA, OUTPUT);
  pinMode(MATRIX_CS, OUTPUT);
  pinMode(MATRIX_CLK, OUTPUT);
  digitalWrite(MATRIX_CS, 1);
  digitalWrite(MATRIX_CLK, 0);
  digitalWrite(MATRIX_DATA, 0);

  // Configure the Keypad pins as inputs.
  pinMode(KEYPAD_COL1, INPUT);
  pinMode(KEYPAD_COL2, INPUT);
  pinMode(KEYPAD_COL3, INPUT);
  pinMode(KEYPAD_COL4, INPUT);
  pinMode(KEYPAD_ROW1, INPUT_PULLUP);
  pinMode(KEYPAD_ROW2, INPUT_PULLUP);
  pinMode(KEYPAD_ROW3, INPUT_PULLUP);
  pinMode(KEYPAD_ROW4, INPUT_PULLUP);

  // Initialize the serial port, which allows for text input and output.
  Serial.begin(57600);
  while (!Serial) { }
  Serial.print("Welcome!\n");
}

unsigned int btn_state = 0; // 16 bit tracking which keypad buttons were being pressed recently

// get_keypad_status() examines each row and column of the keypad to deterimine
// which button or buttons are being pressed.
unsigned int get_keypad_status() {
  unsigned int status = 0;
  int COL[] = { KEYPAD_COL1, KEYPAD_COL2, KEYPAD_COL3, KEYPAD_COL4 };
  int ROW[] = { KEYPAD_ROW1, KEYPAD_ROW2, KEYPAD_ROW3, KEYPAD_ROW4 };
  for (int c = 0; c < 4; c++) {
    pinMode(COL[c], OUTPUT);
    digitalWrite(COL[c], LOW);
    for (int r = 0; r < 4; r++) {
      int n = 4*r + c;
      if (digitalRead(ROW[r]) == LOW) {
        status = status | (1 << n);
      }
    }
    pinMode(COL[c], INPUT);
  }
  return status;
}

int get_keypad_hex_digit() {
  unsigned int new_status = get_keypad_status();
  if (new_status == btn_state)
    return -1; // nothing has changed, pretend nothing is being pressed
  btn_state = new_status;
  return find_highest_one(btn_state);
}