Return to Sender

This is an interactive problem.

A sender must reliably deliver a message over a network that may reorder, drop, and duplicate packets.

Real protocols like TCP solve this through sequence numbers, acknowledgments, and retransmission. In this problem, you will implement a minimal reliable transfer protocol on top of an unreliable network.

---

Packet Format

Packet {
  src, dst, seq, payload
}

• src is the source of the packet (either "S" for Sender or "R" for Receiver).
• dst is the destination of the packet (either "S" or "R", must differ from src).
• seq is a non-negative integer sequence number chosen by the sender of the packet.
• payload is an arbitrary string.

---

Network API

net_send(packet)
net_recv(id)

• This API is already provided (you do not need to implement it).
• net_send enqueues a packet into the network.
• net_recv(id) returns the next packet whose dst == id, or a sentinel value if none are available. See the Notes section for the language-specific sentinel.
• Packets may be dropped, reordered, or duplicated by the network. You cannot observe which packets are dropped.

---

Classes to Implement

Sender {
    Sender(id, receiver_id, message)
    tick()
    done()
}

Receiver {
    Receiver(id, sender_id)
    tick()
    result()
}

Sender

• The constructor takes in:
  • id: the Sender's identifier string ("S").
  • receiver_id: the Receiver's identifier string ("R").
  • message: the full byte string to be delivered.
• tick() is called repeatedly by the judge. Returns nothing.
• done() returns true iff the Sender believes all data has been acknowledged by the Receiver.

Receiver

• The constructor takes in:
  • id: the Receiver's identifier string ("R").
  • sender_id: the Sender's identifier string ("S").
• tick() is called repeatedly by the judge. Returns nothing.
• result() returns the fully reconstructed message as a string once all data has arrived in order, or an empty string if reconstruction is incomplete.

---

Protocol

You may design your own protocol. However, it must satisfy the following requirements:

1. The Sender splits message into chunks and sends each chunk as an individual packet to the Receiver. Each packet may carry at most 1024 bytes of message data. Chunk sequence numbers must be contiguous non-negative integers starting from 0.
2. The Receiver sends acknowledgment packets back to the Sender.
3. The Sender uses acknowledgments to determine which chunks have been delivered, and retransmits chunks that appear to be lost. Any chunk not acknowledged within a fixed number of ticks must be retransmitted — the Sender must not wait indefinitely.
4. The Receiver reconstructs the message in order from the received chunks.
5. Duplicate chunks (same seq received more than once) must be silently ignored by the Receiver.

The specific format of acknowledgment packets (their seq and payload fields) is up to you. You may also use the payload field of data packets to carry metadata alongside the message data. The Receiver has no other means of knowing the total message length or chunk count, so your protocol must communicate this explicitly — for instance, by including the total chunk count in every data packet's payload.

---

tick Semantics

The judge runs the simulation in discrete steps called ticks.

In each tick:

1. Zero or more packets may already be available via net_recv() (possibly out of order or duplicated).
2. The judge calls sender.tick() and receiver.tick() (order is unspecified).
3. Any packets the Sender or Receiver choose to send must be sent using net_send() during their tick() call.

Your tick() must:

• increment an internal tick counter (starting at 0) at the very start of each call,
• repeatedly call net_recv(my_id) until it returns the sentinel value,
• process any packets addressed to that participant,
• update internal protocol state accordingly,
• send any required packets using net_send().

Your tick() must not:

• block or wait for future packets,
• use real sockets or sleeping,
• assume packets arrive in order, exactly once, or at all.

Progress happens across multiple calls to tick().

---

Behavioral Requirements

Sender Rules

• The Sender must chunk the message before any tick() is called.
• The Sender must retransmit any chunk that has not been acknowledged within a fixed number of ticks. The Sender must not wait indefinitely for an acknowledgment.
• The Sender must not retransmit a chunk that has already been acknowledged.
• done() must return true only after the Sender has received evidence that all chunks have been delivered. Once done() returns true, it must remain true for all subsequent calls.

Receiver Rules

• The Receiver must send at least one acknowledgment per received data chunk.
• The Receiver must reconstruct the message in order: result() must return the chunks concatenated in ascending order of their sequence numbers.
• The Receiver must not include the payload of a duplicate chunk more than once in the reconstruction.
• result() must return an empty string until the full message has been reconstructed. Once result() returns a non-empty string, it must always return that same string on all subsequent calls.
• tick() may continue to be called after reconstruction is complete. The Receiver must continue draining net_recv() and sending acknowledgments so the Sender can reach done().

---

Out-of-Order, Dropped, and Duplicate Packets

Your implementation must be safe under any delivery pattern.

• If the Receiver gets chunk seq = 5 before chunks 0–4, it must buffer chunk 5 and wait.
• If a chunk is dropped entirely, the Sender must detect this via timeout and retransmit it.
• If the Receiver gets the same chunk twice, it must ignore the second copy.
• If the Sender gets the same acknowledgment twice, it must not retransmit an already-acknowledged chunk because of it.
• Any packet that does not match the expected protocol state (unrecognized payload format, wrong src, wrong dst, or a seq that has no meaning in the current context) must be silently ignored.

---

Network Model

The network has three parameters, hidden from you at runtime:

• Loss rate p: each packet is independently dropped with probability p.
• Reorder window w: a delivered packet may be delayed by up to w additional ticks.
• Duplication rate d: a delivered packet may be delivered again with probability d.

You are guaranteed: 0 ≤ p ≤ 0.4, 0 ≤ w ≤ 5, 0 ≤ d ≤ 0.1.

---

Determinism

For the same sequence of delivered packets, your implementation must behave deterministically. You may not use randomness, real clocks, or OS-level timing. Use tick count as your notion of time.

---

Input / Output Format

The judge will compile and run your Sender and Receiver implementation in a hidden harness.

You do not need to write any custom input or output parsing.

---

Test Groups

Group	Message size	p	w	d
1	≤ 1024 B	0	0	0
2	≤ 8192 B	0	0–2	0
3	≤ 32768 B	0–0.2	0–3	0
4	≤ 65536 B	0–0.4	0–5	0–0.1

A test case is passed when sender.done() returns true, receiver.result() equals the original message, and both conditions are met within the tick limit of 10,000 ticks.

---

Notes

• You may not use OS networking APIs (no real sockets).
• You must implement the chunking, sequencing, acknowledgment, and retransmission logic yourself.
• At most 16 net_send calls (combined across Sender and Receiver) are allowed per tick. The judge will discard excess sends beyond this limit.
• Each packet's payload must not exceed 1100 bytes in total length. This gives 1024 bytes for message data and 76 bytes of headroom for any metadata your protocol requires.
• At most 32 net_recv calls are allowed per participant per tick.
• The Sender and Receiver share the same process and the same tick timeline. Think of your tick() implementations as two coroutines running in lockstep.
• net_recv sentinel by language: in C++, net_recv returns std::optional<Packet> — check with if (!pkt) or while (auto pkt = net_recv(id)); in Python, net_recv returns None when no packet is available — check with if pkt is None.