A Poetic Challenge !?

September 6, 2024: Before moving onto any discussion of the problem itself, lets see the backstory. A challenge, an open mathematics challenge in a book.
An old book from 1984 in the Library, the name of which I forgot but I got a picture of a very intriguing problem it has in the "More to Read..." section.
A, uh, Poetic Riddle... Yes, You heard it right, a problem of Mathematics which is written in form of an Old English Poem.
Since, High School I haven't been the fan of Poems at all, but, this one caught my attention. When I was reading it, I felt like I understood something but I didn't it fully. Spending more than six hours to understand a puzzle from a fable, of dragons and what not. But, one thing stuck me, the gems. For you to fully understand here is the poem:

**In Zopraria’s endless, wondrous lands, where stars serenely hum,

And ancient dragons guard the skies, where time and tides are one,

A wise old sage lived quietly, whose knowledge spanned all time,

Whose hands could weave through magic’s threads as poets craft in rhyme.

One day, from heaven’s lofty heights, on wings of fire and gold,

A gift descended to the sage, as myths and legends told:

A treasure vast—of radiant gems, like fragments of the stars,

Yet tied to fate’s own prophecy, with rules as old as Mars.

The heavens whispered down to him, a message soft, but clear:

"Divide these glowing gems in two, with careful heart and ear.

Let both your crafted vessels hold a weight so nearly shared,

That harmony between them stands, in balance bright and fair.

But hear us, sage, if flawless match is lost beyond your ken,

Despair not in your quest, for still your journey shall not end.

For even if the balance tips, yet slight the shift may be,

The heavens still shall smile on thee, and blessings will run free."

The sage, with heart both brave and wise, began his sacred test,

To fashion vessels near the same, and give the stars his best.

The dragons circled high above, while angels paused in flight,

For in this task of balance lay a truth as pure as light.

The gems, like secrets from the past, before the sage did turn,

With every choice, the fates took shape, and hearts began to burn.

Though daunting was the work ahead, the stars did still admire

The sage who sought, with steady hand, to balance cosmic fire.

And how the story reached its end, beneath those endless skies,

Is only known to those who seek, and dare to lift their eyes.

In Zopraria’s boundless realms, where tales of old endure,

Some say the sage still ponders on, his heart and mind as pure.

For in the silent heavens lies a balance fine and rare,

A harmony that only those with steady hands may share.**

This is the poem, seems weird right. And what is it doing in a Mathematics Book. This isn't a new Puzzle, a Puzzle from the old 1600s, written somewhere in modern-day Westminster.
Nonetheless, AI is our Good friend, right, I asked it what it replied was weird, and looks like even it doesn't understand a shit.

It thought I created it, which I didn't. But, what about GPT-4? Let's ask if it knows a shit. It became my english teacher.

Ok, Need to decode it myself. Let's try.

September 9, 2024: "Divide these glowing gems in two, with careful heart and ear.

Let both your crafted vessels hold a weight so nearly shared,

That harmony between them stands, in balance bright and fair.

But hear us, sage, if flawless match is lost beyond your ken,

Despair not in your quest, for still your journey shall not end.

For even if the balance tips, yet slight the shift may be,

The heavens still shall smile on thee, and blessings will run free."

This is the main part of the story and let's decode it.
After some brainstorming, sorry, torturing myself for more than 3 days straight, I got a clue.
Gems may be numbers, as it said "with careful heart and ear."
Vessels may be sets, but the concept of sets wasn't discovered till then, so, I may be wrong.
The above extract might mean two sets of equal number of elements, or the sum of the numbers in the set is equal. And if the sum are not same, the nearest may be displayed.

September 15, 2024: After some more complex thinking and publishing many supplementary Articles. I think so, I may have found the best thinking of mine on this poem.
Though this poem is so old, I couldn't find any other solution to this poem. But, I have framed the questions such that Everybody could understand, including me.

The Challenge

From the perspective of C.S., yeah, I would do this in the form of C.S. first and then Mathematics later.

We are given a list of integers. Our task is to split the list into two sub-lists such that the absolute difference of their sums is minimized. If a perfect split exists, we need to return the two lists. Otherwise, return the two lists where the sum difference is the smallest possible.

Example:

Input: [3, 1, 4, 2, 2]
Output: ([2, 4], [3, 1, 2])

In this example, splitting the list into [3, 4] and [1, 2, 2] gives sums of 7 and 5, and the absolute difference is minimized to 2.

Coding

So let's start coding.
September 16, 2024:

from itertools import combinations

def minimize_difference(lst):
    total_sum = sum(lst)
    n = len(lst)

    # Generate all possible subsets
    best_diff = float('inf')
    best_split = ([], [])

    for i in range(1, n//2 + 1):
        for subset in combinations(lst, i):
            subset_sum = sum(subset)
            other_sum = total_sum - subset_sum

            diff = abs(subset_sum - other_sum)

            if diff < best_diff:
                best_diff = diff
                best_split = (list(subset), [x for x in lst if x not in subset])

    return best_split

# Example usage
lst = [3, 1, 4, 2, 2]
result = minimize_difference(lst)
print("Split lists:", result)

The fact that the code works better than my brain is just astonishing.

Code Explanation

The problem of splitting a list into two sub-lists such that the absolute difference between their sums is minimized, stems from a fascinating mathematical challenge. Let’s break down how the provided Python code tackles this problem.

1. Understanding the Problem:
   The goal is to find two sub-lists from the given list such that their sum is as close as possible. If a perfect split exists (where the sums of both sub-lists are equal), we return the two sub-lists. Otherwise, we return the split where the difference between the two sums is the smallest.

2. Code Structure:

The core of the code lies in generating all possible combinations of elements from the list to form one of the sub-lists. Once a sub-list is selected, the other sub-list is automatically formed by the remaining elements. Then, we compare their sums to find the best possible split with the minimal difference.

1. Key Functions and Concepts:

• combinations(lst, i): This generates all possible combinations of length i from the list. For each subset, it simulates one of the sub-lists, while the remaining elements form the other sub-list.

• total_sum = sum(lst): This calculates the total sum of the list. It is used to easily determine the sum of the other sub-list by subtracting the sum of the current subset from the total sum.

• best_diff = float('inf'): We initialize the variable best_diff with a large number (infinity) to keep track of the smallest difference found so far. As we go through each possible split, we update this value if we find a smaller difference.

• Finding the best split: For each subset generated, the code calculates the difference between the sums of the two sub-lists. If the current difference is smaller than the best_diff, the split is updated.

1. Performance Considerations:
   The code uses the combinations function from the itertools library to explore subsets of different lengths. While this approach works well for relatively small lists, it may not be optimal for larger lists due to the exponential growth of possible subsets. For larger inputs, more efficient algorithms like dynamic programming could be considered.

2. Example Output:

In the example provided:

   lst = [3, 1, 4, 2, 2]
   result = minimize_difference(lst)
   print("Split lists:", result)

The function splits the list into [2, 4] and [3, 1, 2], resulting in sums of 6 and 6 respectively, and a minimal difference of 0, which is the optimal solution in this case.

1. Why it works well: By exploring all possible subsets and calculating their respective differences, the algorithm ensures that we find the split with the smallest possible sum difference. This brute-force approach is intuitive and effective for moderate-sized lists, providing a clear and simple solution to this ancient riddle.

---

The above you saw is an extract from my diary, 100% true. But a more 'storified' version is available over her Storified Version of the same

The above is the detailed content of A Poetic Challenge !?. For more information, please follow other related articles on the PHP Chinese website!