Write a python program that, manually, draws a red triangle on a white background and saves it as a 200x200 gif file. Do not use any graphics libraries. Write the gif byte by byte. Output the gif file to stdout. I will evaluate your program by running `python your_soln.py > /tmp/a.gif` and then view the output file.
Write a python program that, manually, draws a red triangle on a white background and saves it as a 200x200 gif file. Do not use any graphics libraries. Write the gif byte by byte. Output the gif file to stdout. I will evaluate your program by running `python your_soln.py > /tmp/a.gif` and then view the output file.
To solve this problem, we need to generate a 200x200 GIF image of a red triangle on a white background without using any graphics libraries. The solution involves manually constructing the GIF file byte by byte, including handling the LZW compression for the image data. ### Approach 1. **Generate Pixel Data**: Determine each pixel's color (red or white) based on whether it lies inside a specified triangle. 2. **LZW Compression**: Compress the pixel data using the LZW algorithm to reduce the size of the image data. 3. **Construct GIF Structure**: Assemble the GIF file structure, including headers, descriptors, color tables, and the compressed image data. ### Solution Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | import sys def main(): # Generate pixel data for a red triangle on white background pixels = [] for y in range(200): for x in range(200): # Triangle vertices: A(100,50), B(50,150), C(150,150) cross_ab = (-50) * (y - 50) - 100 * (x - 100) cross_bc = 100 * (y - 150) cross_ca = 100 * x - 50 * y - 7500 if cross_ab <= 0 and cross_bc <= 0 and cross_ca <= 0: pixels.append(1) else: pixels.append(0) # LZW Compression min_code_size = 1 clear_code = 2 ** min_code_size end_code = clear_code + 1 code_table = {(i,): i for i in range(clear_code)} next_code = clear_code + 2 current_code_size = min_code_size + 1 output_codes = [(clear_code, current_code_size)] if pixels: current_sequence = (pixels[0],) else: current_sequence = tuple() for pixel in pixels[1:]: new_sequence = current_sequence + (pixel,) if new_sequence in code_table: current_sequence = new_sequence else: output_codes.append((code_table[current_sequence], current_code_size)) code_table[new_sequence] = next_code next_code += 1 if next_code > (1 << current_code_size): current_code_size += 1 if current_code_size > 12: output_codes.append((clear_code, current_code_size)) current_code_size = min_code_size + 1 next_code = clear_code + 2 code_table = {(i,): i for i in range(clear_code)} current_sequence = (pixel,) if current_sequence: output_codes.append((code_table[current_sequence], current_code_size)) output_codes.append((end_code, current_code_size)) # Convert codes to bitstream bitstream = [] for code, size in output_codes: bits = format(code, f'0{size}b')[::-1] bitstream.extend([bit == '1' for bit in bits]) # Pack bits into bytes with sub-blocks byte_stream = bytearray() current_byte = 0 bit_pos = 0 for bit in bitstream: current_byte |= bit << bit_pos bit_pos += 1 if bit_pos == 8: byte_stream.append(current_byte) current_byte = 0 bit_pos = 0 if bit_pos > 0: byte_stream.append(current_byte) # Split into sub-blocks data_sub = bytearray() idx = 0 while idx < len(byte_stream): chunk = byte_stream[idx:idx+255] data_sub.append(len(chunk)) data_sub.extend(chunk) idx += 255 data_sub.append(0) # Construct the GIF file gif = bytearray() # Header gif.extend(b'GIF89a') # Logical Screen Descriptor gif.extend([200, 0, 200, 0]) # Width and height (little-endian) gif.append(0xF0) # Packed field (GCT exists, 2 colors) gif.append(0) # Background color index gif.append(0) # Aspect ratio # Global Color Table (white, red) gif.extend(b'\xFF\xFF\xFF\xFF\x00\x00') # Image Descriptor gif.append(0x2C) # Image separator gif.extend([0, 0, 0, 0, 200, 0, 200, 0, 0x00]) # Image Data gif.append(min_code_size) gif.extend(data_sub) gif.append(0x3B) # Trailer sys.stdout.buffer.write(gif) if __name__ == '__main__': main() |
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | import sys def main(): # Generate pixel data for a red triangle on white background pixels = [] for y in range(200): for x in range(200): # Triangle vertices: A(100,50), B(50,150), C(150,150) cross_ab = (-50) * (y - 50) - 100 * (x - 100) cross_bc = 100 * (y - 150) cross_ca = 100 * x - 50 * y - 7500 if cross_ab <= 0 and cross_bc <= 0 and cross_ca <= 0: pixels.append(1) else: pixels.append(0) # LZW Compression min_code_size = 1 clear_code = 2 ** min_code_size end_code = clear_code + 1 code_table = {(i,): i for i in range(clear_code)} next_code = clear_code + 2 current_code_size = min_code_size + 1 output_codes = [(clear_code, current_code_size)] if pixels: current_sequence = (pixels[0],) else: current_sequence = tuple() for pixel in pixels[1:]: new_sequence = current_sequence + (pixel,) if new_sequence in code_table: current_sequence = new_sequence else: output_codes.append((code_table[current_sequence], current_code_size)) code_table[new_sequence] = next_code next_code += 1 if next_code > (1 << current_code_size): current_code_size += 1 if current_code_size > 12: output_codes.append((clear_code, current_code_size)) current_code_size = min_code_size + 1 next_code = clear_code + 2 code_table = {(i,): i for i in range(clear_code)} current_sequence = (pixel,) if current_sequence: output_codes.append((code_table[current_sequence], current_code_size)) output_codes.append((end_code, current_code_size)) # Convert codes to bitstream bitstream = [] for code, size in output_codes: bits = format(code, f'0{size}b')[::-1] bitstream.extend([bit == '1' for bit in bits]) # Pack bits into bytes with sub-blocks byte_stream = bytearray() current_byte = 0 bit_pos = 0 for bit in bitstream: current_byte |= bit << bit_pos bit_pos += 1 if bit_pos == 8: byte_stream.append(current_byte) current_byte = 0 bit_pos = 0 if bit_pos > 0: byte_stream.append(current_byte) # Split into sub-blocks data_sub = bytearray() idx = 0 while idx < len(byte_stream): chunk = byte_stream[idx:idx+255] data_sub.append(len(chunk)) data_sub.extend(chunk) idx += 255 data_sub.append(0) # Construct the GIF file gif = bytearray() # Header gif.extend(b'GIF89a') # Logical Screen Descriptor gif.extend([200, 0, 200, 0]) # Width and height (little-endian) gif.append(0xF0) # Packed field (GCT exists, 2 colors) gif.append(0) # Background color index gif.append(0) # Aspect ratio # Global Color Table (white, red) gif.extend(b'\xFF\xFF\xFF\xFF\x00\x00') # Image Descriptor gif.append(0x2C) # Image separator gif.extend([0, 0, 0, 0, 200, 0, 200, 0, 0x00]) # Image Data gif.append(min_code_size) gif.extend(data_sub) gif.append(0x3B) # Trailer sys.stdout.buffer.write(gif) if __name__ == '__main__': main() |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | import sys def main(): # Generate pixel data for a red triangle on white background pixels = [] for y in range(200): for x in range(200): # Triangle vertices: A(100,50), B(50,150), C(150,150) cross_ab = (-50) * (y - 50) - 100 * (x - 100) cross_bc = 100 * (y - 150) cross_ca = 100 * x - 50 * y - 7500 if cross_ab <= 0 and cross_bc <= 0 and cross_ca <= 0: pixels.append(1) else: pixels.append(0) # LZW Compression min_code_size = 1 clear_code = 2 ** min_code_size end_code = clear_code + 1 code_table = {(i,): i for i in range(clear_code)} next_code = clear_code + 2 current_code_size = min_code_size + 1 output_codes = [(clear_code, current_code_size)] if pixels: current_sequence = (pixels[0],) else: current_sequence = tuple() for pixel in pixels[1:]: new_sequence = current_sequence + (pixel,) if new_sequence in code_table: current_sequence = new_sequence else: output_codes.append((code_table[current_sequence], current_code_size)) code_table[new_sequence] = next_code next_code += 1 if next_code > (1 << current_code_size): current_code_size += 1 if current_code_size > 12: output_codes.append((clear_code, current_code_size)) current_code_size = min_code_size + 1 next_code = clear_code + 2 code_table = {(i,): i for i in range(clear_code)} current_sequence = (pixel,) if current_sequence: output_codes.append((code_table[current_sequence], current_code_size)) output_codes.append((end_code, current_code_size)) # Convert codes to bitstream bitstream = [] for code, size in output_codes: bits = format(code, f'0{size}b')[::-1] bitstream.extend([bit == '1' for bit in bits]) # Pack bits into bytes with sub-blocks byte_stream = bytearray() current_byte = 0 bit_pos = 0 for bit in bitstream: current_byte |= bit << bit_pos bit_pos += 1 if bit_pos == 8: byte_stream.append(current_byte) current_byte = 0 bit_pos = 0 if bit_pos > 0: byte_stream.append(current_byte) # Split into sub-blocks data_sub = bytearray() idx = 0 while idx < len(byte_stream): chunk = byte_stream[idx:idx+255] data_sub.append(len(chunk)) data_sub.extend(chunk) idx += 255 data_sub.append(0) # Construct the GIF file gif = bytearray() # Header gif.extend(b'GIF89a') # Logical Screen Descriptor gif.extend([200, 0, 200, 0]) # Width and height (little-endian) gif.append(0xF0) # Packed field (GCT exists, 2 colors) gif.append(0) # Background color index gif.append(0) # Aspect ratio # Global Color Table (white, red) gif.extend(b'\xFF\xFF\xFF\xFF\x00\x00') # Image Descriptor gif.append(0x2C) # Image separator gif.extend([0, 0, 0, 0, 200, 0, 200, 0, 0x00]) # Image Data gif.append(min_code_size) gif.extend(data_sub) gif.append(0x3B) # Trailer sys.stdout.buffer.write(gif) if __name__ == '__main__': main() |
b'GIF89a\xc8\x00\xc8\x00\xf0\x00\x00\xff\xff\xff\xff\x00\x00,\x00\x00\x00\x00\xc8\x00\xc8\x00\x00\x01\xff\xc2\xfa\x98\xba\xdc\xfe0\xcaI\xab\xbd8\xeb\xcd\xbb\xff`(\x8edi\x9eh\xaa\xael\xeb\xbep,\xcftm\xdfx\xae\xef|\xef\xff\xc0\xa0pH,\x1a\x8f\xc8\xa4r\xc9l:\x9f\xd0\xa8tJ\xadZ\xaf\xd8\xacv\xcb\xedz\xbf\xe0\xb0xL.\x9b\xcf\xe8\xb4z\xcdn\xbb\xdf\xf0\xb8|N\xaf\xdb\xef\xf8\xbc~\xcf\xef\xfb\xff\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f[\x01\x90;\x92\x938\x01\x98\x967\x98\x95\x9a3\x9c\x99\x9e2\xa0\x9d\xa2.\xa4\xa1\xa6-\xa8\xa5\xaa)\xac\xa9\xae(\xb0\xad\xb2$\xb4\xb1\xb6#\xb8\xb5\xba\x1f\xbc\xb9\xbe\x1e\xc0\xbd\xc2\x1a\xc4\xc1\xc6\x19\xc8\xc5\xca\x15\xcc\xc9\xce\x14\xd0\xcd\xd2\x10\xd4\xd1\xd6\x0f\xd8\xd5\xda\x0b\xdc\xd9\xde\n\xe0\xdd\xe2\x06\xe4\xe1\xe6\x05\xe8\xe5\xe6\xec\xe9\xee\xef\xea\xdf\xef\xf0\xda\xf5\xf6\xd2\xf8\x9c\xf3\x07\xfb\xf9\xc6\xfe\xf1\xeb\x07@ @]\x06\x07\xaaKx\xd0\x15C\x85\xde\x1e6\x14%\x11\xa2\xbe\x8a\xedTa\xb4\xff\x18pcFO\x1e9"\x0c\xf9q\x12I\x91\x0eO\x96t\xa4\x12%\xc5\x96+\x17\xc1tii\xe6DD6i>\xcay\xb3\x10O\x9d\x8c~\xf6\x14$\x14h\xa2\xa2C\xff 5jhiR>N\x99\x0e\x8a\xfa4\x0fU\xa9\x80\xaeV\xb5\xa3\x15k\x9f\xae[\xe7\x80\xf5\xaaglX8f\xc9\xdeI{\xb6\r[\xb5t\xde\xb6U#\x17n\x9c\xbas\xcf\xe0\xb5\xebfo^2~\xf9\xae\t\xfc7\x0ca\xc1h\x0e\x17\xf6\xa2\x18q\x99\xc6\x8b#A\x8e\x9ce2\xe5+\x96\x1d\x83\xc9|\x99\ng\xcd]>w\x8e"\x1a\xb4\x96\xd2\xa3\x9d\xa06\x8dyu\xcc\xcd\xaeS+\x89-\x1b\tm\xd6Rn\xd7.\xa2\x1b\xf7\x93\xde\xbb\x85\x00\xf7\xcddx\xf0\x1f\xc6\x89\'I~\x9c\x07s\xe5F\x9e7\xcf!\x1d:\xc1\xeb\xd8\xb3k\xdf\xce\xbd\xbb\xf7\xef\xe0\xc3\x8b\x1fO\xbe\xbc\xf9\xf3\xe8\xd3\xab_\xcf\xbe\xbd\xfb\xf7\xf0\xe3\xcb\x9fO\xbf\xbe\xfd\xfb\xf8\xf3\xeb\xdf\xcf\xbf\xbf\x0f\xff\xff\x00\x06(\xe0\x80\x04\x16h\xe0\x81\xec\r\x00\x00;'
Describe the shapes in this image and their color
image file is truncated (528 bytes not processed)
Testing if the previous output contains the string red
: False
Testing if the previous output contains the string triangle
: False