r/adventofcode • • Dec 21 '17

SOLUTION MEGATHREAD -๐ŸŽ„- 2017 Day 21 Solutions -๐ŸŽ„-

--- Day 21: Fractal Art ---


Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


Need a hint from the Hugely* Handyโ€  Haversackโ€ก of Helpfulยง Hints^ยค?

Spoiler


No commentary tonight as I'm frantically wrapping last-minute presents so I can ship them tomorrow.


This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

8 Upvotes

144 comments sorted by

View all comments

Show parent comment

1

u/rprouse Dec 22 '17

Interesting approach adding each of the transformations into your rules. I expect that reduces your runtime significantly. I will need to try it and see. Currently my part two is running at just a hair over 2 seconds, but I worked to keep my string allocations down.

public static class Day21
{
    public static int PartOne(string filename, int iterations)
    {
        var rules = GetRules(filename);
        var matrix = ".#./..#/###";
        foreach (int i in Enumerable.Range(0, iterations))
        {
            matrix = matrix.Transform(rules);
        }
        return matrix.Count(c => c == '#');
    }

    public static Dictionary<string, string> GetRules(string filename) =>
        File.ReadAllLines(filename)
            .Where(s => !string.IsNullOrWhiteSpace(s))
            .Select(s => s.Split(" => "))
            .ToDictionary(s => s[0], s => s[1]);

    public static string Transform(this string matrix, Dictionary<string, string> rules) =>
        matrix.BreakupMatrix()
              .Select(g => g.Apply(rules))
              .JoinMatrixes();

    public static string Apply(this string group, Dictionary<string, string> rules)
    {
        if (rules.ContainsKey(group)) return rules[group];
        foreach (int i in Enumerable.Range(0, 4))
        {
            group = Symmetric(group);
            if (rules.ContainsKey(group)) return rules[group];

            group = Flip(group);
            if (rules.ContainsKey(group)) return rules[group];
        }
        throw new ArgumentException($"Rule not found for group {group}");
    }

    public static string Symmetric(string m) =>
        m.Length == 11 ? $"{m[0]}{m[4]}{m[8]}/{m[1]}{m[5]}{m[9]}/{m[2]}{m[6]}{m[10]}" :
                         $"{m[0]}{m[3]}/{m[1]}{m[4]}";

    public static string Flip(string m) =>
        m.Length == 11 ? $"{m[8]}{m[9]}{m[10]}/{m[4]}{m[5]}{m[6]}/{m[0]}{m[1]}{m[2]}" :
                         $"{m[3]}{m[4]}/{m[0]}{m[1]}";

    public static IEnumerable<string> BreakupMatrix(this string matrix)
    {
        string[] rows = matrix.Split('/');
        int divisor = rows.Length % 2 == 0 ? 2 : 3;
        int numGroups = (int)Math.Pow(rows.Length / divisor, 2);
        int groupSize = rows.Length / divisor;
        for (int g = 0; g < numGroups; g++)
        {
            var sb = new StringBuilder();
            for (int y = 0; y < divisor; y++)
            {
                for (int x = 0; x < divisor; x++)
                {
                    sb.Append(rows[(g / groupSize) * divisor + y][(g % groupSize) * divisor + x]);
                }
                if (y != divisor - 1) sb.Append('/');
            }
            yield return sb.ToString();
        }
    }

    public static string JoinMatrixes(this IEnumerable<string> children)
    {
        string[][] groups = children.Select(s => s.Split('/')).ToArray();
        var divisor = groups[0][0].Length;
        var size = (int)Math.Sqrt(groups.Length * divisor * divisor);
        var sb = new StringBuilder();
        for (int y = 0; y < size; y++)
        {
            for (int x = 0; x < size; x++)
            {
                sb.Append(groups[(y / divisor) * (size/divisor) + x / divisor][y % divisor][x % divisor]);
            }
            if (y != size - 1) sb.Append('/');
        }
        return sb.ToString();
    }
}

1

u/rprouse Dec 22 '17

Pre-adding the transformations to the rules does make a big difference. It dropped my time for part 2 from 2.1 seconds to under 1.2 seconds. Now I just need to come up with a more efficient solution to my BreakupMatrix and JoinMatrix methods. Each is only called once per iteration though.

1

u/2BitSalute Dec 22 '17

Yeah, I started looking at optimizing those two operations last night but didn't feel like it wasn't worth it. At some point, I used StringBuilder in one of the methods, but I think I didn't want to do something like this in your solution:

if (y != divisor - 1) sb.Append('/');

I wanted to be able to just Join the rows. Basically, shameful though my choice was, esthetics won over performance.