Common modern literary tropes

Ananace@lemmy.ananace.dev · 1 day ago

And now we get into the days where caching really is king. My first attempt didn’t go so well, I tried to handle the full list result as one cache step, instead of individually caching the result of calculating each stone per step.

I think my original attempt is still calculating at home, but I finished up this much better version on the trip to work.
All hail public transport.

C#

List<long> stones = new List<long>();
public void Input(IEnumerable<string> lines)
{
  stones = string.Concat(lines).Split(' ').Select(v => long.Parse(v)).ToList();
}

public void Part1()
{
  var expanded = TryExpand(stones, 25);

  Console.WriteLine($"Stones: {expanded}");
}
public void Part2()
{
  var expanded = TryExpand(stones, 75);

  Console.WriteLine($"Stones: {expanded}");
}

public long TryExpand(IEnumerable<long> stones, int steps)
{
  if (steps == 0)
    return stones.Count();
  return stones.Select(s => TryExpand(s, steps)).Sum();
}
Dictionary<(long, int), long> cache = new Dictionary<(long, int), long>();
public long TryExpand(long stone, int steps)
{
  var key = (stone, steps);
  if (cache.ContainsKey(key))
    return cache[key];

  var result = TryExpand(Blink(stone), steps - 1);
  cache[key] = result;
  return result;
}

public IEnumerable<long> Blink(long stone)
{
  if (stone == 0)
  {
    yield return 1;
    yield break;
  }
  var str = stone.ToString();
  if (str.Length % 2 == 0)
  {
    yield return long.Parse(str[..(str.Length / 2)]);
    yield return long.Parse(str[(str.Length / 2)..]);
    yield break;
  }
  yield return stone * 2024;
}

Ananace@lemmy.ananace.dev · 2 days ago

Nice to have a really simple one for a change, both my day 1 and 2 solutions worked on their very first attempts.
I rewrote the code to combine the two though, since the implementations were almost identical for both solutions, and also to replace the recursion with a search list instead.

C#

int[] heights = new int[0];
(int, int) size = (0, 0);

public void Input(IEnumerable<string> lines)
{
  size = (lines.First().Length, lines.Count());
  heights = string.Concat(lines).Select(c => int.Parse(c.ToString())).ToArray();
}

int trails = 0, trailheads = 0;
public void PreCalc()
{
  for (int y = 0; y < size.Item2; ++y)
    for (int x = 0; x < size.Item1; ++x)
      if (heights[y * size.Item1 + x] == 0)
      {
        var unique = new HashSet<(int, int)>();
        trails += CountTrails((x, y), unique);
        trailheads += unique.Count;
      }
}

public void Part1()
{
  Console.WriteLine($"Trailheads: {trailheads}");
}
public void Part2()
{
  Console.WriteLine($"Trails: {trails}");
}

int CountTrails((int, int) from, HashSet<(int,int)> unique)
{
  int found = 0;

  List<(int,int)> toSearch = new List<(int, int)>();
  toSearch.Add(from);

  while (toSearch.Any())
  {
    var cur = toSearch.First();
    toSearch.RemoveAt(0);

    int height = heights[cur.Item2 * size.Item1 + cur.Item1];
    for (int y = -1; y <= 1; ++y)
      for (int x = -1; x <= 1; ++x)
      {
        if ((y != 0 && x != 0) || (y == 0 && x == 0))
          continue;

        var newAt = (cur.Item1 + x, cur.Item2 + y);
        if (newAt.Item1 < 0 || newAt.Item1 >= size.Item1 || newAt.Item2 < 0 || newAt.Item2 >= size.Item2)
          continue;

        int newHeight = heights[newAt.Item2 * size.Item1 + newAt.Item1];
        if (newHeight - height != 1)
          continue;

        if (newHeight == 9)
        {
          unique.Add(newAt);
          found++;
          continue;
        }

        toSearch.Add(newAt);
      }
  }

  return found;
}

Ananace@lemmy.ananace.dev · 3 days ago

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;
  }
}

Ananace@lemmy.ananace.dev · 4 days ago

And I of course misread and wasted a bunch of time debugging the second part, entirely missed the fact that antinodes occurred on top of the emanating antennae as well…

C#

public static class LINQExt
{
  public static IEnumerable<(T,T)> PermutatePairs<T>(this IEnumerable<T> source) {
    return source.SelectMany(k => source.Where(v => !v?.Equals(k) ?? false).Select(v => (k, v)));
  }
}

struct Antenna
{
  public int X, Y;
  public char Frequency;
}

List<Antenna> antennae = new List<Antenna>();
int width, height;

public void Input(IEnumerable<string> lines)
{
  char[] map = string.Join("", lines).ToCharArray();
  width = lines.First().Length;
  height = lines.Count();

  for (int y = 0; y < height; ++y)
    for (int x = 0; x < width; ++x)
    {
      char at = map[y * width + x];
      if (at == '.')
        continue;

      antennae.Add(new Antenna{ X = x, Y = y, Frequency = at });
    }
}

public void Part1()
{
  HashSet<(int, int)> antinodes = new HashSet<(int, int)>();

  foreach (var antinode in antennae.GroupBy(k => k.Frequency).SelectMany(g => g.PermutatePairs()).SelectMany(v => GetOpposing(v.Item1, v.Item2)).Where(InRange))
    antinodes.Add(antinode);

  Console.WriteLine($"Unique antinodes: {antinodes.Count}");
}
public void Part2()
{
  HashSet<(int, int)> antinodes = new HashSet<(int, int)>();

  foreach (var antennaePair in antennae.GroupBy(k => k.Frequency).SelectMany(g => g.PermutatePairs()))
  {
    // Iterate separately, to make the handling of bound exit easier
    foreach (var antinode in GetAllOpposing(antennaePair.Item1, antennaePair.Item2).TakeWhile(InRange))
      antinodes.Add(antinode);
    foreach (var antinode in GetAllOpposing(antennaePair.Item2, antennaePair.Item1).TakeWhile(InRange))
      antinodes.Add(antinode);
  }
  Console.WriteLine($"Unique antinodes: {antinodes.Count}");
}

bool InRange((int, int) point) {
  return point.Item1 >= 0 && point.Item1 < width && point.Item2 >= 0 && point.Item2 < height;
}
(int, int)[] GetOpposing(Antenna a, Antenna b) {
  return new[] { (a.X + (a.X - b.X), a.Y + (a.Y - b.Y)), (b.X + (b.X - a.X), b.Y + (b.Y - a.Y)) };
}
IEnumerable<(int, int)> GetAllOpposing(Antenna a, Antenna b) {
  (int, int) diff = (a.X - b.X, a.Y - b.Y);
  (int, int) at = (a.X, a.Y);
  yield return at;

  while (true)
  {
    at.Item1 += diff.Item1;
    at.Item2 += diff.Item2;

    yield return at;
  }
}

Ananace@lemmy.ananace.dev · edit-2 5 days ago

Made a couple of attempts to munge the input data into some kind of binary search tree, lost some time to that, then threw my hands into the air and did a more naïve sort-of breadth-first search instead. Which turned out to be better for part 2 anyway.
Also, maths. Runs in just over a hundred milliseconds when using AsParallel, around half a second without.

C#

List<(long, int[])> data = new List<(long, int[])>();

public void Input(IEnumerable<string> lines)
{
  foreach (var line in lines)
  {
    var parts = line.Split(':', StringSplitOptions.TrimEntries);

    data.Add((long.Parse(parts.First()), parts.Last().Split(' ').Select(int.Parse).ToArray()));
  }
}

public void Part1()
{
  var correct = data.Where(kv => CalcPart(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum();

  Console.WriteLine($"Correct: {correct}");
}
public void Part2()
{
  var correct = data.AsParallel().Where(kv => CalcPart2(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum();

  Console.WriteLine($"Correct: {correct}");
}

public bool CalcPart(long res, Span<int> num, long carried = 0)
{
  var next = num[0];
  if (num.Length == 1)
    return res == carried + next || res == carried * next;
  return CalcPart(res, num.Slice(1), carried + next) || CalcPart(res, num.Slice(1), carried * next);
}

public bool CalcPart2(long res, Span<int> num, long carried = 0)
{
  var next = num[0];
  // Get the 10 logarithm for the next number, expand the carried value by 10^<next 10log + 1>, add the two together
  // For 123 || 45
  // 45 ⇒ 10log(45) + 1 == 2
  // 123 * 10^2 + 45 == 12345
  long combined = carried * (long)Math.Pow(10, Math.Floor(Math.Log10(next) + 1)) + next;
  if (num.Length == 1)
    return res == carried + next || res == carried * next || res == combined;
  return CalcPart2(res, num.Slice(1), carried + next) || CalcPart2(res, num.Slice(1), carried * next) || CalcPart2(res, num.Slice(1), combined);
}

Ananace@lemmy.ananace.dev · 22 days ago

Common modern literary tropes

Ananace@lemmy.ananace.dev · 8 months ago

I’ve been hoping to find a non-PHP alternative to Nextcloud for a while, but unfortunately I’ve yet to find one which supports my base requirements for the file storage.

Due to some quirks with my setup, my backing storage consists of a mix of local folders, S3 buckets, SMB/SFTP mounts (with user credential login), and even an external WebDav server.
Nextcloud does manage such a thing phenomenally, while all the alternatives I’ve tested (including a Radicale backed by rclone mounts) tend to fall completely to pieces as soon as more than one storage backend ends up getting involved, especially when some of said backends need to be accessed with user-specific credentials.

Ananace

Common modern literary tropes

Common modern literary tropes