# Ideas and Solutions for Advent of Code 2021 in Kotlin -- Part 3/4

DevFeed: [Ideas and Solutions for Advent of Code 2021 in Kotlin -- Part 3/4](<https://devfeed.tech/articles/ideas-and-solutions-for-advent-of-code-2021-in-kotlin-part-3-4-24735.md>)

Original publisher: [Read original article](<https://medium.com/xorum-io/ideas-and-solutions-for-advent-of-code-2021-in-kotlin-part-3-4-dbfd577703cc?source=rss----92bb7980cc9f---4>)

Author: Yev Kanivets

Published: 2021-12-26T14:22:49Z

Content type: tutorial

Language: en

Sources: [xorum.io - Medium](<https://devfeed.tech/sources/xorum-io-medium.md>)

Topics: [Advent of Code](<https://devfeed.tech/topics/advent-of-code.md>), [Kotlin](<https://devfeed.tech/topics/kotlin.md>), [Programming](<https://devfeed.tech/topics/programming.md>), [competitive-programming](<https://devfeed.tech/topics/competitive-programming.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>), [math](<https://devfeed.tech/topics/math.md>)

Tags: [advent-of-code](<https://devfeed.tech/tags/advent-of-code.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [array](<https://devfeed.tech/tags/array.md>), [code](<https://devfeed.tech/tags/code.md>), [competitive-programming](<https://devfeed.tech/tags/competitive-programming.md>), [data-structures](<https://devfeed.tech/tags/data-structures.md>), [graph-theory](<https://devfeed.tech/tags/graph-theory.md>), [kotlin](<https://devfeed.tech/tags/kotlin.md>), [memory](<https://devfeed.tech/tags/memory.md>), [pairs](<https://devfeed.tech/tags/pairs.md>), [programming](<https://devfeed.tech/tags/programming.md>), [solutions](<https://devfeed.tech/tags/solutions.md>), [time](<https://devfeed.tech/tags/time.md>)

## AI overview

This article presents high-level ideas and Kotlin solutions for Advent of Code 2021 tasks from days 13 to 15. It discusses folding a 2D array, modeling polymer growth with dynamic programming, and finding a shortest path in a 2D array.

## Source excerpt

Ideas and Solutions for Advent of Code 2021 in Kotlin -- Part 3/4 The third week of Advent of Code requires more time and even some competitive programming knowledge like dynamic programming and graph theory. In this article, I share some high-level ideas and my solutions if you need a hint or a few to get that gold star. Ideas and Solutions for tasks 1 to 6 can be found here, for tasks 7 to 12 -- here. Day 13: Transparent Origami The 2D array contains two types of symbols -- . and #. This array can be folded horizontally and vertically multiple times. When folding # symbols replace . symbols, but not vice versa. Here is the complete task. This is a modeling task, which you can do on the 2D array itself, but the possible range is quite large, so you can hit a memory limit. The smarter solution would be to fold the # symbols (the initial input, actually). Such folding can be done with Kotlin's fold function using the initial value of # symbol positions and mapNotNull, which mirrors X or Y coordinates depending on the fold direction. Here is my solution. Day 14: Extended Polymerization We get the initial string (template) consisting of uppercase letters, which describe the initial state of the polymer. The list of pair insertion rules allows growing the initial polymer step by step exponentially. We need to model this growth during 10 (first sub-task) and 40 (second sub-task) steps. Here is the complete task. The first sub-task can be solved just by modeling, but even 20 steps are too long and require too much memory and time. The (much) better solution is based on dynamic programming. You can easily see that every pair grows independently of others (new elements are always added inside the pair). It means that the solution can be found for each pair separately and then combined. It doesn't speed up things sufficiently though. But makes the solution easier? Yes. Now, let's grow each pair step by step. So at each step, every pair (usually) produces two more pairs, which h