The rain on the lighthouse’s tiny window was a steady grey murmur, mirroring the disorientation that clung to Elias Thorpe. He was a cartographer – a maker of maps – and lately his dreams had hinted at something beyond the unsettling depictions of shifting landscapes and vanquished landmarks. He’d taken to meticulously documenting them in his dream diary.
“It feels… fragmented,” Elias said, painstakingly writing down his latest entry. “I keep trying to digest the symbolism but the echoes keep overlaying the underlying meaning.” He paused, studying the page. “I need to eliminate all types of dreams that repeat. It is obscuring the patterns. If I eliminate all entries that have duplicates, then maybe I can disentangle my dreamscape.”
Here are the first four entries from his dream diary:
I felt volcanic sand shift between my webbed toes.
I greeted a beared bronze sculpture which walked out of the sea.
I felt volcanic sand shift between my webbed toes.
I awoke from a dream that I was dreaming and wondered how far the recursion could go.
Exercise
Notice that the first and third entries are identical. Help Elias by removing all types of entries that have duplicates – that includes removing the first instance of a repeating dream. Preserving only each dream that has no duplicates/echoes will guide Elias in his dream analysis.
Data Deduplication
Data deduplication is a thing. Just removing adjacent matching lines doesn’t catch duplicates further afield. Applying a sort and then a deduplication doesn’t preserve the order. So a slightly more involved process is called for.
Sounds good to me. Would the input be a list of strings? From the start of the story I was half hoping for map tiles that need to be connected via overlapping edges (a fun Advent of Code challenge).
As a non-native English speaker I could not really follow the story (or get the title). I know that much of the mystic story atmosphere depends on wording far off from everyday English, and especially technical English. But I think many people would stop half way through it and skip to the instructions.
The instructions are clear to me. But there’s not much to do in many languages, which may collide with existing concept exercises around Set data structures that also do little more than ask for removing duplicates.
I think the idea here is not only to remove the duplicate, but the entry which has a duplicate.
So, it is more like a Map exercise which counts the number of occurrences and excludes elements which have more than 1 as count and then returns this list with elements in the same order as the input.
About the text, I loved it but I agree that it is perhaps too complicated for a worldwide audience.
Hah. That’s not my understanding of the proposal. My understanding is that the ordered list [2,2,1,5,3,4,4] should produce the ordered list [2,1,5,3,4].
This probably calls for some actual examples and maybe a simplified story.
Hah. That’s not my understanding of the proposal. My understanding is that the ordered list [2,2,1,5,3,4,4] should produce the ordered list [2,1,5,3,4].
This probably calls for some actual examples and maybe a simplified story.
Indeed. I’ve simplified the language and tried to make the story example clearer.
The Mapmaker’s Dreams
The grey rain on the lighthouse’s tiny window mirrored the confusion that clung to Elias Thorpe. He was a mapmaker – a cartographer – and lately his dreams hinted at something he couldn’t quite put his finger on. Elias was reading his dream diary trying to make sense of it all…
“I keep trying to understand the meaning, but the ideas keep mixing together.”
He paused to study the entries.
“I need to find my core dreams. Dreams which repeat are making it hard to see the patterns. If I keep only dreams which have no repetitions, then maybe I can make sense of it all.”
Here are the first four entries from his dream diary:
I felt volcanic sand shifted between my webbed toes.
I greeted a beared bronze sculpture which walked out of the sea.
I felt volcanic sand shifted between my webbed toes.
I awoke from a dream that I was dreaming and wondered how far the recursion could go.
Exercise
Notice that the first and third dreams are the same. Help Elias by removing these entries from his diary, leaving us with just:
I greeted a beared bronze sculpture which walked out of the sea.
I awoke from a dream that I was dreaming and wondered how far the recursion could go.
By preserving his dreams that don’t repeat we can help Elias in his dream analysis.
A common approach holds onto quite a bit of state information. Some languages help subordinates that detail. This can help the beginner with a first approach closer to a restatement of the problem rather than disassembly, to wit:
I was under the same original impression as Isaac in that we’d keep the first occurrence of the repeating dream. The revised story is a bit confusing though. Why is Elias discarding every occurrence of a repeating dream? Is there no use for a dream once it repeats?
Edit - Could we just say dreams that repeat aren’t core dreams so that’s why they are excluded?
The revised story is a bit confusing though. Why is Elias discarding every occurrence of a repeating dream? Is there no use for a dream once it repeats?
I agree. We could ground it more in reality. How about Elias has PTSD. He can’t tell his dreams from his nightmares. To make sense of his subconscious, he first needs to distinguish them. Elias notices that his nightmares repeat and so he has found a way to separate them from his dreams.
Yeah. I don’t think we need nightmares :) This story is also starting to feel a bit … complicated and while I love a good story, the connection between the story and the exercise feels a bit tenuous to me.
The dreams aren’t very connected to him being a cartographer. If we lean into the idea of him making a map, the data could be a list of of field notes describing distance and bearings from one landmark to another. If he records the same distance and bearing from one landmark to another, that’s clearly a mistake and needs to be removed.
It’s still a stretch because why would you throw away the original instance?
Another option is that Elias works at a library with an automated book return system. Each book has an unique barcode sticker so if the system detects the same barcode was scanned more than once, it needs to put aside all the books for that barcode for manual verification. Elias wants a report of all the books that were returned successfully.
A problem with that story is that it seems Elias would be more interested in the manually reviewed books. So another approach might be that Elias works in a geology lab where samples were recently reorganized by the box they’re in. Some rock sample labels were accidentally reused. There’s a time crunch so he doesn’t have time to figure out the original sample for those labels. That could help explain why he only wants the samples with unique labels and why keeping insertion order so he goes to the right box and grabs the right item.