#!/usr/bin/env python3
"""
This program “manually” creates a 200×200 GIF image with a red triangle drawn on
a white background. It does not use any graphics libraries – instead it writes out the
GIF file byte‐by‐byte, including a simple LZW compressor. (The triangle is defined by
its vertices (50,150), (150,150) and (100,50).)

You can run:
   python3 this_script.py > /tmp/a.gif
and then view /tmp/a.gif in an image viewer.
 
NOTE: This code implements a minimal LZW encoder for GIF image data. It outputs the LZW
stream in “sub‐block” format as required by the GIF spec.
"""

import sys
import struct

# --------------- Utility Functions ----------------

def to_bytes_le(value, length):
    "Return little‐endian representation of value in length bytes."
    return value.to_bytes(length, byteorder='little')

class BitWriter:
    "Helper to pack codes into a stream of bytes in LSB-first order."
    def __init__(self):
        self.buf = 0
        self.nbits = 0
        self.bytes = bytearray()
    def write(self, code, bit_size):
        "Write the code (an integer) using bit_size bits (LSB first)."
        # Append code bits into buffer.
        self.buf |= (code << self.nbits)
        self.nbits += bit_size
        while self.nbits >= 8:
            self.bytes.append(self.buf & 0xFF)
            self.buf >>= 8
            self.nbits -= 8
    def flush(self):
        "Flush remainder bits."
        if self.nbits:
            self.bytes.append(self.buf & 0xFF)
            self.buf = 0
            self.nbits = 0
    def get_bytes(self):
        return bytes(self.bytes)

# --------------- GIF LZW Encoder ----------------

def lzw_encode(pixels, init_code_size):
    """
    LZW encode the list of pixel indices (each 0 or 1) for a GIF image.
    The parameter init_code_size is the LZW minimum code size (we use 2).
    
    Returns the compressed byte string for the image data.
    """
    # According to the GIF spec:
    #   Clear Code = (1 << init_code_size)
    #   End-of-Information code = Clear Code + 1
    clear_code = 1 << init_code_size
    eoi_code = clear_code + 1
    next_code = eoi_code + 1

    # initial code size used in encoding (starting bit length)
    cur_code_size = init_code_size + 1
    max_code_val = (1 << cur_code_size)   # when next_code reaches this value, need to increase bit size

    # Initialize dictionary with single pixel entries.
    dictionary = {}
    for i in range(clear_code):
        dictionary[(i,)] = i

    # Prepare bit writer.
    bw = BitWriter()
    # Output clear code first.
    bw.write(clear_code, cur_code_size)

    current = ()
    # Process each pixel in order.
    for pixel in pixels:
        # candidate is sequence with appended pixel:
        candidate = current + (pixel,)
        if candidate in dictionary:
            current = candidate
        else:
            # Output the code for current.
            bw.write(dictionary[current], cur_code_size)
            # Add candidate to dictionary if room (<4096 codes allowed in GIF)
            if next_code < 4096:
                dictionary[candidate] = next_code
                next_code += 1
                # Increase cur_code_size as needed:
                if next_code >= max_code_val and cur_code_size < 12:
                    cur_code_size += 1
                    max_code_val = (1 << cur_code_size)
            else:
                # Dictionary full: output clear code and reset.
                bw.write(clear_code, cur_code_size)
                dictionary = {}
                for i in range(clear_code):
                    dictionary[(i,)] = i
                cur_code_size = init_code_size + 1
                max_code_val = (1 << cur_code_size)
                next_code = eoi_code + 1
            current = (pixel,)
    # Output code for remaining sequence.
    if current:
        bw.write(dictionary[current], cur_code_size)
    # Write end-of-information code.
    bw.write(eoi_code, cur_code_size)
    bw.flush()
    return bw.get_bytes()

def create_subblocks(data_bytes):
    """
    Given data_bytes as a bytes object (the compressed image data), break it into
    sub-blocks as required by the GIF format. Each subblock is at most 255 bytes.
    
    Returns a bytes object containing all subblocks (each preceded by its size), 
    terminated with a zero-length block.
    """
    block_bytes = bytearray()
    i = 0
    while i < len(data_bytes):
        block = data_bytes[i:i+255]
        block_bytes.append(len(block))
        block_bytes.extend(block)
        i += 255
    # Block terminator: 0
    block_bytes.append(0)
    return bytes(block_bytes)

# --------------- Triangle Rasterization ----------------

def point_in_triangle(px, py, ax, ay, bx, by, cx, cy):
    "Return True if point (px,py) is inside the triangle defined by A, B, C."
    # Using barycentric technique.
    # Compute vectors
    v0x = cx - ax
    v0y = cy - ay
    v1x = bx - ax
    v1y = by - ay
    v2x = px - ax
    v2y = py - ay

    # Compute dot products
    dot00 = v0x*v0x + v0y*v0y
    dot01 = v0x*v1x + v0y*v1y
    dot02 = v0x*v2x + v0y*v2y
    dot11 = v1x*v1x + v1y*v1y
    dot12 = v1x*v2x + v1y*v2y

    # Compute barycentric coordinates
    denom = dot00 * dot11 - dot01 * dot01
    if denom == 0:
        return False
    invDenom = 1 / denom
    u = dot11 * dot02 - dot01 * dot12
    v = dot00 * dot12 - dot01 * dot02
    u *= invDenom
    v *= invDenom
    return (u >= 0) and (v >= 0) and (u + v <= 1)

def generate_pixel_data(width, height):
    """
    Generates a flat list of pixel indices for a 200x200 image.
    The background is white (index 0) and a red triangle (index 1) is drawn.
    The triangle uses vertices: (50,150), (150,150), (100,50).
    
    Pixel (x,y) corresponds to the top-left of the image.
    We'll test the pixel center at (x+0.5, y+0.5).
    """
    pixels = []
    # Triangle vertices
    ax, ay = 50, 150
    bx, by = 150, 150
    cx, cy = 100, 50
    for y in range(height):
        for x in range(width):
            # Compute pixel center.
            px = x + 0.5
            py = y + 0.5
            if point_in_triangle(px, py, ax, ay, bx, by, cx, cy):
                pixels.append(1)  # red
            else:
                pixels.append(0)  # white
    return pixels

# --------------- Assemble the GIF File ----------------

def main():
    width = 200
    height = 200
    # Prepare pixel data (a list of 0 or 1, row-major order)
    pixels = generate_pixel_data(width, height)
    
    # LZW Minimum Code Size – per GIF spec this must be at least 2.
    lzw_min_code_size = 2
    # Compress pixel data using our LZW encoder.
    compressed_data = lzw_encode(pixels, lzw_min_code_size)
    # Break compressed data into sub-blocks.
    image_data_subblocks = create_subblocks(compressed_data)
    
    # Begin constructing GIF file as a bytearray.
    gif = bytearray()
    # 1. Header "GIF89a"
    gif.extend(b'GIF89a')
    
    # 2. Logical Screen Descriptor:
    #    a. Logical screen width and height (little-endian 16-bit each)
    gif.extend(to_bytes_le(width, 2))
    gif.extend(to_bytes_le(height, 2))
    #    b. Packed field:
    #       - Global Color Table Flag    : 1 (bit 7)
    #       - Color Resolution           : 7 (bits 4-6) [we set to max 7]
    #       - Sort Flag                  : 0 (bit 3)
    #       - Size of Global Color Table : 0 (bits 0-2) so table size = 2^(0+1)=2
    packed_byte = 0x80 | (7 << 4) | 0   # 0x80 | 0x70 = 0xF0.
    gif.append(packed_byte)
    #    c. Background Color Index (we use white = index 0)
    gif.append(0)
    #    d. Pixel Aspect Ratio (0 - not specified)
    gif.append(0)
    
    # 3. Global Color Table: 2 entries, each 3 bytes.
    # Index 0: white (255,255,255)
    gif.extend(bytes([255, 255, 255]))
    # Index 1: red (255, 0, 0)
    gif.extend(bytes([255, 0, 0]))
    
    # 4. Image Descriptor:
    #    a. Image Separator (0x2C)
    gif.append(0x2C)
    #    b. Image Left Position (2 bytes, little-endian) = 0
    gif.extend(to_bytes_le(0, 2))
    #    c. Image Top Position (2 bytes) = 0
    gif.extend(to_bytes_le(0, 2))
    #    d. Image Width and Height (2 bytes each).
    gif.extend(to_bytes_le(width, 2))
    gif.extend(to_bytes_le(height, 2))
    #    e. Packed Field: No local color table, not interlaced, etc. => 0.
    gif.append(0)
    
    # 5. Image Data:
    #    a. LZW Minimum Code Size
    gif.append(lzw_min_code_size)
    #    b. Image Data sub-blocks.
    gif.extend(image_data_subblocks)
    
    # 6. Trailer: 0x3B
    gif.append(0x3B)
    
    # Write the entire GIF to stdout in binary mode.
    sys.stdout.buffer.write(gif)

if __name__ == '__main__':
    main()

#!/usr/bin/env python3
"""
This program “manually” creates a 200×200 GIF image with a red triangle drawn on
a white background. It does not use any graphics libraries – instead it writes out the
GIF file byte‐by‐byte, including a simple LZW compressor. (The triangle is defined by
its vertices (50,150), (150,150) and (100,50).)

You can run:
   python3 this_script.py > /tmp/a.gif
and then view /tmp/a.gif in an image viewer.
 
NOTE: This code implements a minimal LZW encoder for GIF image data. It outputs the LZW
stream in “sub‐block” format as required by the GIF spec.
"""

import sys
import struct

# --------------- Utility Functions ----------------

def to_bytes_le(value, length):
    "Return little‐endian representation of value in length bytes."
    return value.to_bytes(length, byteorder='little')

class BitWriter:
    "Helper to pack codes into a stream of bytes in LSB-first order."
    def __init__(self):
        self.buf = 0
        self.nbits = 0
        self.bytes = bytearray()
    def write(self, code, bit_size):
        "Write the code (an integer) using bit_size bits (LSB first)."
        # Append code bits into buffer.
        self.buf |= (code << self.nbits)
        self.nbits += bit_size
        while self.nbits >= 8:
            self.bytes.append(self.buf & 0xFF)
            self.buf >>= 8
            self.nbits -= 8
    def flush(self):
        "Flush remainder bits."
        if self.nbits:
            self.bytes.append(self.buf & 0xFF)
            self.buf = 0
            self.nbits = 0
    def get_bytes(self):
        return bytes(self.bytes)

# --------------- GIF LZW Encoder ----------------

def lzw_encode(pixels, init_code_size):
    """
    LZW encode the list of pixel indices (each 0 or 1) for a GIF image.
    The parameter init_code_size is the LZW minimum code size (we use 2).
    
    Returns the compressed byte string for the image data.
    """
    # According to the GIF spec:
    #   Clear Code = (1 << init_code_size)
    #   End-of-Information code = Clear Code + 1
    clear_code = 1 << init_code_size
    eoi_code = clear_code + 1
    next_code = eoi_code + 1

    # initial code size used in encoding (starting bit length)
    cur_code_size = init_code_size + 1
    max_code_val = (1 << cur_code_size)   # when next_code reaches this value, need to increase bit size

    # Initialize dictionary with single pixel entries.
    dictionary = {}
    for i in range(clear_code):
        dictionary[(i,)] = i

    # Prepare bit writer.
    bw = BitWriter()
    # Output clear code first.
    bw.write(clear_code, cur_code_size)

    current = ()
    # Process each pixel in order.
    for pixel in pixels:
        # candidate is sequence with appended pixel:
        candidate = current + (pixel,)
        if candidate in dictionary:
            current = candidate
        else:
            # Output the code for current.
            bw.write(dictionary[current], cur_code_size)
            # Add candidate to dictionary if room (<4096 codes allowed in GIF)
            if next_code < 4096:
                dictionary[candidate] = next_code
                next_code += 1
                # Increase cur_code_size as needed:
                if next_code >= max_code_val and cur_code_size < 12:
                    cur_code_size += 1
                    max_code_val = (1 << cur_code_size)
            else:
                # Dictionary full: output clear code and reset.
                bw.write(clear_code, cur_code_size)
                dictionary = {}
                for i in range(clear_code):
                    dictionary[(i,)] = i
                cur_code_size = init_code_size + 1
                max_code_val = (1 << cur_code_size)
                next_code = eoi_code + 1
            current = (pixel,)
    # Output code for remaining sequence.
    if current:
        bw.write(dictionary[current], cur_code_size)
    # Write end-of-information code.
    bw.write(eoi_code, cur_code_size)
    bw.flush()
    return bw.get_bytes()

def create_subblocks(data_bytes):
    """
    Given data_bytes as a bytes object (the compressed image data), break it into
    sub-blocks as required by the GIF format. Each subblock is at most 255 bytes.
    
    Returns a bytes object containing all subblocks (each preceded by its size), 
    terminated with a zero-length block.
    """
    block_bytes = bytearray()
    i = 0
    while i < len(data_bytes):
        block = data_bytes[i:i+255]
        block_bytes.append(len(block))
        block_bytes.extend(block)
        i += 255
    # Block terminator: 0
    block_bytes.append(0)
    return bytes(block_bytes)

# --------------- Triangle Rasterization ----------------

def point_in_triangle(px, py, ax, ay, bx, by, cx, cy):
    "Return True if point (px,py) is inside the triangle defined by A, B, C."
    # Using barycentric technique.
    # Compute vectors
    v0x = cx - ax
    v0y = cy - ay
    v1x = bx - ax
    v1y = by - ay
    v2x = px - ax
    v2y = py - ay

    # Compute dot products
    dot00 = v0x*v0x + v0y*v0y
    dot01 = v0x*v1x + v0y*v1y
    dot02 = v0x*v2x + v0y*v2y
    dot11 = v1x*v1x + v1y*v1y
    dot12 = v1x*v2x + v1y*v2y

    # Compute barycentric coordinates
    denom = dot00 * dot11 - dot01 * dot01
    if denom == 0:
        return False
    invDenom = 1 / denom
    u = dot11 * dot02 - dot01 * dot12
    v = dot00 * dot12 - dot01 * dot02
    u *= invDenom
    v *= invDenom
    return (u >= 0) and (v >= 0) and (u + v <= 1)

def generate_pixel_data(width, height):
    """
    Generates a flat list of pixel indices for a 200x200 image.
    The background is white (index 0) and a red triangle (index 1) is drawn.
    The triangle uses vertices: (50,150), (150,150), (100,50).
    
    Pixel (x,y) corresponds to the top-left of the image.
    We'll test the pixel center at (x+0.5, y+0.5).
    """
    pixels = []
    # Triangle vertices
    ax, ay = 50, 150
    bx, by = 150, 150
    cx, cy = 100, 50
    for y in range(height):
        for x in range(width):
            # Compute pixel center.
            px = x + 0.5
            py = y + 0.5
            if point_in_triangle(px, py, ax, ay, bx, by, cx, cy):
                pixels.append(1)  # red
            else:
                pixels.append(0)  # white
    return pixels

# --------------- Assemble the GIF File ----------------

def main():
    width = 200
    height = 200
    # Prepare pixel data (a list of 0 or 1, row-major order)
    pixels = generate_pixel_data(width, height)
    
    # LZW Minimum Code Size – per GIF spec this must be at least 2.
    lzw_min_code_size = 2
    # Compress pixel data using our LZW encoder.
    compressed_data = lzw_encode(pixels, lzw_min_code_size)
    # Break compressed data into sub-blocks.
    image_data_subblocks = create_subblocks(compressed_data)
    
    # Begin constructing GIF file as a bytearray.
    gif = bytearray()
    # 1. Header "GIF89a"
    gif.extend(b'GIF89a')
    
    # 2. Logical Screen Descriptor:
    #    a. Logical screen width and height (little-endian 16-bit each)
    gif.extend(to_bytes_le(width, 2))
    gif.extend(to_bytes_le(height, 2))
    #    b. Packed field:
    #       - Global Color Table Flag    : 1 (bit 7)
    #       - Color Resolution           : 7 (bits 4-6) [we set to max 7]
    #       - Sort Flag                  : 0 (bit 3)
    #       - Size of Global Color Table : 0 (bits 0-2) so table size = 2^(0+1)=2
    packed_byte = 0x80 | (7 << 4) | 0   # 0x80 | 0x70 = 0xF0.
    gif.append(packed_byte)
    #    c. Background Color Index (we use white = index 0)
    gif.append(0)
    #    d. Pixel Aspect Ratio (0 - not specified)
    gif.append(0)
    
    # 3. Global Color Table: 2 entries, each 3 bytes.
    # Index 0: white (255,255,255)
    gif.extend(bytes([255, 255, 255]))
    # Index 1: red (255, 0, 0)
    gif.extend(bytes([255, 0, 0]))
    
    # 4. Image Descriptor:
    #    a. Image Separator (0x2C)
    gif.append(0x2C)
    #    b. Image Left Position (2 bytes, little-endian) = 0
    gif.extend(to_bytes_le(0, 2))
    #    c. Image Top Position (2 bytes) = 0
    gif.extend(to_bytes_le(0, 2))
    #    d. Image Width and Height (2 bytes each).
    gif.extend(to_bytes_le(width, 2))
    gif.extend(to_bytes_le(height, 2))
    #    e. Packed Field: No local color table, not interlaced, etc. => 0.
    gif.append(0)
    
    # 5. Image Data:
    #    a. LZW Minimum Code Size
    gif.append(lzw_min_code_size)
    #    b. Image Data sub-blocks.
    gif.extend(image_data_subblocks)
    
    # 6. Trailer: 0x3B
    gif.append(0x3B)
    
    # Write the entire GIF to stdout in binary mode.
    sys.stdout.buffer.write(gif)

if __name__ == '__main__':
    main()

#!/usr/bin/env python3
"""
This program creates a 200x200 GIF image “by hand” – that is,
it writes a complete GIF file byte‐by‐byte without using any graphics libraries.
It creates a white image (color index 0) with a red triangle (color index 1).
The triangle’s vertices are chosen as:
    (50,150), (150,150), (100,50)
The GIF uses a global color table with two entries:
  index 0: white (255,255,255)
  index 1: red   (255,0,0)

The pixel data is encoded using LZW compression (implemented below).
Finally the program writes the GIF binary to stdout.
Run it as:
   python your_soln.py > /tmp/a.gif
then view /tmp/a.gif.
"""

import sys, struct, math

# ----------------------------------------
# Helper: Triangle point-in-test using edge functions.
def point_in_triangle(px, py, v1, v2, v3):
    # Using barycentric/edge method: test the signs
    # Compute the sign of the area (edge function)
    def sign(ax, ay, bx, by, cx, cy):
        return (cx-ax)*(by-ay) - (cy-ay)*(bx-ax)
    d1 = sign(v1[0], v1[1], v2[0], v2[1], px, py)
    d2 = sign(v2[0], v2[1], v3[0], v3[1], px, py)
    d3 = sign(v3[0], v3[1], v1[0], v1[1], px, py)
    # Check if all are non-negative or non-positive.
    has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)
    return not (has_neg and has_pos)

# ----------------------------------------
# LZW compressor for GIF image data.
# We implement the GIF variant of LZW.
def lzw_compress(data, min_code_size):
    # In GIF, the LZW minimum code size is the number of bits needed to represent a pixel.
    # For a 2-color image, min_code_size should be 1.
    clear_code = 1 << min_code_size
    eoi_code   = clear_code + 1
    next_code  = eoi_code + 1
    current_code_size = min_code_size + 1  # initial code size used for output codes.
    max_code_val = (1 << current_code_size) - 1

    # Initialize the dictionary with all single-byte entries.
    dictionary = { (i,): i for i in range(clear_code) }

    # We'll accumulate the output bits into a bytearray.
    out_bytes = bytearray()
    bit_buffer = 0
    bit_count = 0

    # Helper: write a code using the given number of bits.
    def write_code(code, bits):
        nonlocal bit_buffer, bit_count, out_bytes
        # Add code bits to the bit_buffer (LSB first).
        bit_buffer |= (code << bit_count)
        bit_count += bits
        # Flush complete bytes.
        while bit_count >= 8:
            out_bytes.append(bit_buffer & 0xFF)
            bit_buffer >>= 8
            bit_count -= 8

    # Write the clear code at the beginning.
    write_code(clear_code, current_code_size)

    w = ()
    for symbol in data:
        wk = w + (symbol,)
        if wk in dictionary:
            w = wk
        else:
            # Output the code for w.
            write_code(dictionary[w], current_code_size)
            # Add wk to the dictionary.
            dictionary[wk] = next_code
            next_code += 1
            # Increase code size if necessary.
            if next_code > max_code_val and current_code_size < 12:
                current_code_size += 1
                max_code_val = (1 << current_code_size) - 1
            # If dictionary is full (4096 codes), output a clear code and reset.
            if next_code == 4096:
                write_code(clear_code, current_code_size)
                # Reset dictionary.
                dictionary = { (i,): i for i in range(clear_code) }
                current_code_size = min_code_size + 1
                next_code = eoi_code + 1
                max_code_val = (1 << current_code_size) - 1
            w = (symbol,)
    # Output any remaining code.
    if w:
        write_code(dictionary[w], current_code_size)
    # Write the End-Of-Information code.
    write_code(eoi_code, current_code_size)
    # Flush any remaining bits.
    if bit_count > 0:
        out_bytes.append(bit_buffer & 0xFF)
    return bytes(out_bytes)

# ----------------------------------------
# Main function that builds the GIF by assembling the headers,
# the image descriptor, compressing the pixel data, and writing out sub-blocks.
def main():
    width = 200
    height = 200

    # Prepare the pixel array.
    # We'll use a one-dimensional list of length width*height.
    # Color index 0 = white, 1 = red.
    pixels = [0] * (width * height)
    
    # Define triangle vertices.
    v1 = (50, 150)
    v2 = (150, 150)
    v3 = (100, 50)
    
    # Rasterize the triangle.
    # For each pixel, check if its center (x+0.5, y+0.5) is inside the triangle.
    for y in range(height):
        py = y + 0.5
        for x in range(width):
            px = x + 0.5
            if point_in_triangle(px, py, v1, v2, v3):
                pixels[y * width + x] = 1  # red

    # Build the GIF file parts.
    out = bytearray()

    # 1. Header: "GIF89a"
    out.extend(b"GIF89a")

    # 2. Logical Screen Descriptor (7 bytes).
    #    Fields: canvas width (2 bytes little-endian), height (2 bytes little-endian),
    #    packed field, background color index, pixel aspect ratio.
    # Global Color Table flag: 1 (bit 7 = 1)
    # Color Resolution: set to 7 (bits 6-4) [not critical]
    # Sort Flag: 0
    # Size of Global Color Table: N, where table size = 2^(N+1). For 2 colors, N = 0.
    packed_field = 0x80 | (7 << 4) | 0  # 1000 0000 | 0x70 = 0xF0? Actually, we'll use 0x80 for simplicity.
    # But since our table is size 2, ensure the lower 3 bits are 0.
    # We'll use: Global Color Table flag = 1, color res and sort don't matter.
    # So simply use 0x80.
    lsd = struct.pack("<HHBBB", width, height, 0x80, 0, 0)
    out.extend(lsd)

    # 3. Global Color Table.
    # We need 2^(N+1) entries. For N=0, that's 2 entries.
    # Entry 0: white (255,255,255); Entry 1: red (255,0,0).
    out.extend(bytes([255, 255, 255, 255, 0, 0]))

    # 4. (Optional) Graphics Control Extension could be inserted here if needed.
    # For our simple image we skip it.

    # 5. Image Descriptor.
    # Image Separator: 0x2C.
    # Image left, top, width, height, and packed field (no local color table, no interlace).
    image_descriptor = bytearray()
    image_descriptor.append(0x2C)
    image_descriptor.extend(struct.pack("<HHHHB", 0, 0, width, height, 0))
    out.extend(image_descriptor)

    # 6. Image Data.
    # The first byte is the LZW minimum code size.
    # For a 2-color image, min_code_size = max(ceil(log2(2)),1) = 1.
    min_code_size = 1
    out.append(min_code_size)

    # Compress the pixel indices using our LZW compressor.
    compressed_data = lzw_compress(pixels, min_code_size)

    # GIF image data is stored in sub-blocks up to 255 bytes.
    # So we break compressed_data into blocks, each preceded by a length byte.
    i = 0
    while i < len(compressed_data):
        block = compressed_data[i:i+255]
        out.append(len(block))
        out.extend(block)
        i += 255
    # Block terminator: a zero-length block.
    out.append(0)

    # 7. GIF Trailer.
    out.append(0x3B)

    # Write the GIF to stdout (as binary).
    sys.stdout.buffer.write(out)

if __name__ == '__main__':
    main()

#!/usr/bin/env python3
"""
This program creates a 200x200 GIF image “by hand” – that is,
it writes a complete GIF file byte‐by‐byte without using any graphics libraries.
It creates a white image (color index 0) with a red triangle (color index 1).
The triangle’s vertices are chosen as:
    (50,150), (150,150), (100,50)
The GIF uses a global color table with two entries:
  index 0: white (255,255,255)
  index 1: red   (255,0,0)

The pixel data is encoded using LZW compression (implemented below).
Finally the program writes the GIF binary to stdout.
Run it as:
   python your_soln.py > /tmp/a.gif
then view /tmp/a.gif.
"""

import sys, struct, math

# ----------------------------------------
# Helper: Triangle point-in-test using edge functions.
def point_in_triangle(px, py, v1, v2, v3):
    # Using barycentric/edge method: test the signs
    # Compute the sign of the area (edge function)
    def sign(ax, ay, bx, by, cx, cy):
        return (cx-ax)*(by-ay) - (cy-ay)*(bx-ax)
    d1 = sign(v1[0], v1[1], v2[0], v2[1], px, py)
    d2 = sign(v2[0], v2[1], v3[0], v3[1], px, py)
    d3 = sign(v3[0], v3[1], v1[0], v1[1], px, py)
    # Check if all are non-negative or non-positive.
    has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)
    return not (has_neg and has_pos)

# ----------------------------------------
# LZW compressor for GIF image data.
# We implement the GIF variant of LZW.
def lzw_compress(data, min_code_size):
    # In GIF, the LZW minimum code size is the number of bits needed to represent a pixel.
    # For a 2-color image, min_code_size should be 1.
    clear_code = 1 << min_code_size
    eoi_code   = clear_code + 1
    next_code  = eoi_code + 1
    current_code_size = min_code_size + 1  # initial code size used for output codes.
    max_code_val = (1 << current_code_size) - 1

    # Initialize the dictionary with all single-byte entries.
    dictionary = { (i,): i for i in range(clear_code) }

    # We'll accumulate the output bits into a bytearray.
    out_bytes = bytearray()
    bit_buffer = 0
    bit_count = 0

    # Helper: write a code using the given number of bits.
    def write_code(code, bits):
        nonlocal bit_buffer, bit_count, out_bytes
        # Add code bits to the bit_buffer (LSB first).
        bit_buffer |= (code << bit_count)
        bit_count += bits
        # Flush complete bytes.
        while bit_count >= 8:
            out_bytes.append(bit_buffer & 0xFF)
            bit_buffer >>= 8
            bit_count -= 8

    # Write the clear code at the beginning.
    write_code(clear_code, current_code_size)

    w = ()
    for symbol in data:
        wk = w + (symbol,)
        if wk in dictionary:
            w = wk
        else:
            # Output the code for w.
            write_code(dictionary[w], current_code_size)
            # Add wk to the dictionary.
            dictionary[wk] = next_code
            next_code += 1
            # Increase code size if necessary.
            if next_code > max_code_val and current_code_size < 12:
                current_code_size += 1
                max_code_val = (1 << current_code_size) - 1
            # If dictionary is full (4096 codes), output a clear code and reset.
            if next_code == 4096:
                write_code(clear_code, current_code_size)
                # Reset dictionary.
                dictionary = { (i,): i for i in range(clear_code) }
                current_code_size = min_code_size + 1
                next_code = eoi_code + 1
                max_code_val = (1 << current_code_size) - 1
            w = (symbol,)
    # Output any remaining code.
    if w:
        write_code(dictionary[w], current_code_size)
    # Write the End-Of-Information code.
    write_code(eoi_code, current_code_size)
    # Flush any remaining bits.
    if bit_count > 0:
        out_bytes.append(bit_buffer & 0xFF)
    return bytes(out_bytes)

# ----------------------------------------
# Main function that builds the GIF by assembling the headers,
# the image descriptor, compressing the pixel data, and writing out sub-blocks.
def main():
    width = 200
    height = 200

    # Prepare the pixel array.
    # We'll use a one-dimensional list of length width*height.
    # Color index 0 = white, 1 = red.
    pixels = [0] * (width * height)
    
    # Define triangle vertices.
    v1 = (50, 150)
    v2 = (150, 150)
    v3 = (100, 50)
    
    # Rasterize the triangle.
    # For each pixel, check if its center (x+0.5, y+0.5) is inside the triangle.
    for y in range(height):
        py = y + 0.5
        for x in range(width):
            px = x + 0.5
            if point_in_triangle(px, py, v1, v2, v3):
                pixels[y * width + x] = 1  # red

    # Build the GIF file parts.
    out = bytearray()

    # 1. Header: "GIF89a"
    out.extend(b"GIF89a")

    # 2. Logical Screen Descriptor (7 bytes).
    #    Fields: canvas width (2 bytes little-endian), height (2 bytes little-endian),
    #    packed field, background color index, pixel aspect ratio.
    # Global Color Table flag: 1 (bit 7 = 1)
    # Color Resolution: set to 7 (bits 6-4) [not critical]
    # Sort Flag: 0
    # Size of Global Color Table: N, where table size = 2^(N+1). For 2 colors, N = 0.
    packed_field = 0x80 | (7 << 4) | 0  # 1000 0000 | 0x70 = 0xF0? Actually, we'll use 0x80 for simplicity.
    # But since our table is size 2, ensure the lower 3 bits are 0.
    # We'll use: Global Color Table flag = 1, color res and sort don't matter.
    # So simply use 0x80.
    lsd = struct.pack("<HHBBB", width, height, 0x80, 0, 0)
    out.extend(lsd)

    # 3. Global Color Table.
    # We need 2^(N+1) entries. For N=0, that's 2 entries.
    # Entry 0: white (255,255,255); Entry 1: red (255,0,0).
    out.extend(bytes([255, 255, 255, 255, 0, 0]))

    # 4. (Optional) Graphics Control Extension could be inserted here if needed.
    # For our simple image we skip it.

    # 5. Image Descriptor.
    # Image Separator: 0x2C.
    # Image left, top, width, height, and packed field (no local color table, no interlace).
    image_descriptor = bytearray()
    image_descriptor.append(0x2C)
    image_descriptor.extend(struct.pack("<HHHHB", 0, 0, width, height, 0))
    out.extend(image_descriptor)

    # 6. Image Data.
    # The first byte is the LZW minimum code size.
    # For a 2-color image, min_code_size = max(ceil(log2(2)),1) = 1.
    min_code_size = 1
    out.append(min_code_size)

    # Compress the pixel indices using our LZW compressor.
    compressed_data = lzw_compress(pixels, min_code_size)

    # GIF image data is stored in sub-blocks up to 255 bytes.
    # So we break compressed_data into blocks, each preceded by a length byte.
    i = 0
    while i < len(compressed_data):
        block = compressed_data[i:i+255]
        out.append(len(block))
        out.extend(block)
        i += 255
    # Block terminator: a zero-length block.
    out.append(0)

    # 7. GIF Trailer.
    out.append(0x3B)

    # Write the GIF to stdout (as binary).
    sys.stdout.buffer.write(out)

if __name__ == '__main__':
    main()