A chat application must fit the instructions and as much recent conversation as possible into the model's context window. Decide what to keep.
What to build
A program that keeps the instructions and the most recent messages that fit within a token budget.
Requirements
- Each message is
ROLE TEXT; its token count is the number of words in TEXT. - Always keep the first message. Then, from the newest message backwards, keep each message that still fits in the budget, stopping at the first that does not (so the kept history has no gaps).
- Print the kept messages in order as
ROLE: TEXT, thentokens used T of MAX.
Input
Line 1: the maximum number of tokens. Line 2: n. Then n messages.
Output
The kept messages, then the token line.
Constraints
1 ≤ n ≤ 1000; the first message always fits.
Example
Input:
15
4
system You are a helpful tutor
user What is a token
assistant A piece of text
user How long is a context window
Output:
system: You are a helpful tutor
assistant: A piece of text
user: How long is a context window
tokens used 15 of 15
Why it works
The newest messages matter most for the next reply and the instructions must never be lost; stopping at the first message that does not fit keeps the remembered conversation continuous.
Examples
15 4 system You are a helpful tutor user What is a token assistant A piece of text user How long is a context window
system: You are a helpful tutor assistant: A piece of text user: How long is a context window tokens used 15 of 15
3 2 system Be brief user hi
system: Be brief user: hi tokens used 3 of 3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
The first message (the instructions) is always kept; count tokens as words of the message text.
Hint 2
Walk from the newest message backwards, keeping messages while they fit in the remaining budget; stop at the first that does not fit.
Hint 3
Print the kept messages in their original order.
Solution
Show one correct solution (try it yourself first)
limit = int(input())
n = int(input())
messages = [input().split(maxsplit=1) for _ in range(n)]
used = len(messages[0][1].split())
kept = []
for role, text in reversed(messages[1:]):
size = len(text.split())
if used + size > limit:
break
used += size
kept.append((role, text))
for role, text in [messages[0]] + kept[::-1]:
print(f"{role}: {text}")
print(f"tokens used {used} of {limit}")