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()
input_text = input()
: This line reads the input from the environment as a string and stores it in theinput_text
variable. The input is expected to be a Python-style list of integers (e.g.,[3, 2, 5, 10, 7]
).import ast
: This line imports theast
module, which provides functions for working with Python abstract syntax trees, including safely evaluating strings containing Python literals.def solve():
: This defines the main function that contains the logic to solve the problem.try...except
block: This block attempts to parse theinput_text
as a Python list usingast.literal_eval()
. If there's a syntax error in the input, it prints an error message and returns.- 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.
- 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).
- 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 updatesprev1
andprev2
for the next iteration.
print(prev2)
: After the loop finishes,prev2
will hold the maximum sum of non-adjacent tokens, which is printed to the standard output.solve()
: This line calls thesolve()
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}