Implement Greedy Decoding (k=1) and Beam Search (k>1) with Length Normalization

Problem: Implement Greedy Decoding and Beam Search (with Length Normalization) You are given a language-model output unrolled by time steps. At each time step t, the model provides a set of candidate tokens with their log-probabilities logp(t, token) (log-probabilities are non-positive; higher is better). Implement two decoding strategies: Greedy decoding (k = 1): at each step pick the token with the highest log-probability, stopping when EOS is generated or max_len is reached. Beam Search (k > 1): keep up to k hypotheses (the beam). At each time step, expand every active hypothesis with all candidate tokens for that step, then select the best k hypotheses according to the scoring function. Hypotheses that already ended with EOS should not be expanded further but must remain eligible for selection. Input steps: a list of length T. steps[t] is a dictionary token -> logp for step t. k: beam width. k = 1 reduces to greedy. eos_token: the end token string (e.g., "<eos>"). max_len: maximum generated length (token count, including EOS if produced). length_norm: boolean. If True, apply length normalization to avoid overly penalizing longer sequences: score = (sum_logp) / L, where L is the current sequence length. If False, use score = sum_logp. Output Return the single best sequence (a list of tokens, no BOS token; include EOS if produced), chosen by the scoring function (ties can be broken arbitrarily). Constraints 1 <= T <= 50 candidates per step: 1..1000 1 <= k <= 50 EOS may be absent at some steps. You may stop early if all beam hypotheses have ended with EOS. Sample Tests All cases use eos_token = "<eos>". Case 1: Greedy (k=1) steps = [ {"A": -0.1, "B": -0.2}, {"C": -0.1, "<eos>": -0.5}, {"<eos>": -0.1} ] k = 1 length_norm = False max_len = 10 Expected: A C <eos> Case 2: Beam (k=2) without length norm steps = [ {"A": -0.1, "B": -0.2}, {"<eos>": -0.3, "C": -0.05}, {"<eos>": -0.05} ] k = 2 length_norm = False max_len = 10 Expected: A C <eos> Case 3: Beam (k=2) with length norm steps = [ {"A": -0.01, "B": -0.02}, {"<eos>": -0.02, "C": -0.01}, {"<eos>": -0.01} ] k = 2 length_norm = True max_len = 10 Expected: A C <eos> Case 4: Early stop (all ended) steps = [ {"<eos>": -0.01, "A": -0.5}, {"A": -0.01, "<eos>": -0.02} ] k = 3 length_norm = False max_len = 10 Expected: <eos> Case 5: Hit max_len steps = [ {"A": -0.1}, {"B": -0.1}, {"C": -0.1}, {"D": -0.1} ] k = 2 length_norm = False max_len = 3 Expected: A B C Example Input 3 2 A -0.1 B -0.2 2 C -0.1 <eos> -0.5 1 <eos> -0.1 1 <eos> 10 0 Output A C <eos>