Day 9: Disk Fragmenter
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 
3 points
Was really blanking on how to do this one nicely, so a bunch of stacked loops it is…
Also ended up writing two separate solutions for the first and second part, since I couldn’t get acceptable performance otherwise. Still takes half a second on my machine, mainly on the second part.
This is technically the second implementation, the first one took minutes to calculate, so I wasn’t really okay with stamping it as my solution-of-choice.
Can definitely still be improved, but I’ve been poking and prodding at this code for hours on end now, so it’s long past time to let it sit for a while and see if I get any better ideas later.
C#
int[] layout = new int[0];
public void Input(IEnumerable<string> lines)
{
layout = string.Join("", lines).ToCharArray().Select(c => int.Parse(c.ToString())).ToArray();
}
public void Part1()
{
ushort?[] blocks = BuildBlockmap().ToArray();
var it = 0;
for (var i = blocks.Length - 1; i > it; i--)
{
if (blocks[i] == null)
continue;
while (it < blocks.Length && blocks[it] != null)
++it;
if (it >= blocks.Length)
break;
(blocks[it], blocks[i]) = (blocks[i], null);
}
long checksum = 0;
foreach (var part in blocks.OfType<ushort>().Select((b, i) => i * b))
checksum += part;
Console.WriteLine($"Checksum: {checksum}");
}
public void Part2()
{
var sparse = BuildSparsemap().ToList();
for (var i = sparse.Count - 1; i >= 0; i--)
{
if (sparse[i].Item1 == null)
continue;
for (var j = 0; j < i; ++j)
{
if (sparse[j].Item1 != null)
continue;
if (sparse[i].Item2 > sparse[j].Item2)
continue;
var size = sparse[j].Item2;
size -= sparse[i].Item2;
(sparse[j], sparse[i]) = (sparse[i], (null, sparse[i].Item2));
if (i + 1 < sparse.Count && sparse[i + 1].Item1 == null)
{
sparse[i] = (null, (ushort)(sparse[i].Item2 + sparse[i + 1].Item2));
sparse.RemoveAt(i + 1);
}
if (sparse[i - 1].Item1 == null)
{
sparse[i - 1] = (null, (ushort)(sparse[i - 1].Item2 + sparse[i].Item2));
sparse.RemoveAt(i);
}
if (size > 0)
sparse.Insert(j + 1, (null, size));
j = i + 1;
}
}
int ind = 0;
long checksum = 0;
foreach (var (val, cnt) in sparse)
for (var i = 0; i < cnt; ++i)
{
checksum += (val ?? 0) * ind;
++ind;
}
Console.WriteLine($"Checksum: {checksum}");
}
IEnumerable<ushort?> BuildBlockmap()
{
ushort blockit = 0;
bool block = true;
foreach (var value in layout)
{
for (int i = 0; i < value; ++i)
yield return block ? blockit : null;
if (block)
blockit++;
block = !block;
}
}
IEnumerable<(ushort?, ushort)> BuildSparsemap()
{
ushort blockit = 0;
bool block = true;
foreach (var value in layout)
{
if (block)
yield return (blockit++, (ushort)value);
else
yield return (null, (ushort)value);
block = !block;
}
}
