Write-up for Summoners Incantation Challenge

Prompt:

Summoners Incantation

To awaken the ancient power of the Dragon's Heart, the summoners must combine magical incantation tokens. However, the tokens are delicate; no two adjacent tokens can be combined without losing their energy. The optimal incantation is the maximum sum obtainable by choosing non-adjacent tokens.

Goal in the Docker Environment:

The goal within the Docker environment is to write a Python program that takes a single line containing a Python-style list of integers (representing the energy values of the tokens) as input and outputs a single integer representing the maximum sum of non-adjacent tokens. The input is provided to the program via the input() function, which is assigned to the input_text variable. The program needs to process this input and print the calculated maximum sum to standard output.

Code Explanation:

# Input the text as a single string
input_text = input()

# Write your solution below and make sure to encode the word correctly

import ast

def solve():
try:
tokens = ast.literal_eval(input_text)
except (SyntaxError) as e:
print(f"Error reading input: {e}")
return

n = len(tokens)
if n == 0:
print(0)
return
if n == 1:
print(tokens[0])
return

prev1 = tokens[0]
prev2 = max(tokens[0], tokens[1])

for i in range(2, n):
current = max(prev2, tokens[i] + prev1)
prev1 = prev2
prev2 = current

print(prev2)

# The solve() function will be called automatically when you "Cast Spell"
solve()
  1. input_text = input(): This line reads the input from the environment as a string and stores it in the input_text variable. The input is expected to be a Python-style list of integers (e.g., [3, 2, 5, 10, 7]).
  2. import ast: This line imports the ast module, which provides functions for working with Python abstract syntax trees, including safely evaluating strings containing Python literals.
  3. def solve():: This defines the main function that contains the logic to solve the problem.
  4. try...except block: This block attempts to parse the input_text as a Python list using ast.literal_eval(). If there's a syntax error in the input, it prints an error message and returns.
  5. Handle base cases:
  • If the list of tokens is empty (n == 0), the maximum sum is 0.
  • If the list contains only one token (n == 1), the maximum sum is the value of that token.
  1. Initialize DP variables:
  • prev1 stores the maximum sum obtainable considering the first token.
  • prev2 stores the maximum sum obtainable considering the first two tokens (it's the maximum of the first and second token values).
  1. Iterate and calculate maximum sum: The code iterates through the tokens starting from the third token (index 2). For each token at index i, it calculates the maximum sum (current) by considering two options:
  • Not including the current token: In this case, the maximum sum is the same as the maximum sum obtained up to the previous token (prev2).
  • Including the current token: In this case, the maximum sum is the current token's value plus the maximum sum obtained up to the token before the previous one (tokens[i] + prev1). The code takes the maximum of these two options. Then, it updates prev1 and prev2 for the next iteration.
  1. print(prev2): After the loop finishes, prev2 will hold the maximum sum of non-adjacent tokens, which is printed to the standard output.
  2. solve(): This line calls the solve() function to execute the solution logic.

Solution:

The solution to this problem uses dynamic programming to find the maximum sum of non-adjacent elements in the given list of token energies. The code iterates through the tokens, keeping track of the maximum sum achievable up to the current position, considering the non-adjacency constraint.

Flag:

HTB{SUMM0N3RS_INC4NT4T10N_R3S0LV3D_f191a4b3546ccb43c2223e0bb506f05a}