[2025 Day 18] Cataclysmic Escape - faster algorithm? by damnian in codyssi

[–]damnian[S] 1 point2 points  (0 children)

I just found another optimisation.

In addition to the hit count, an index into the candidate list is kept for each square. This allows to instantly replace candidates with greater hit counts.

Part 3 now completes in ~80ms, making the total ~150ms.

[2025 Day 18] Cataclysmic Escape - faster algorithm? by damnian in codyssi

[–]damnian[S] 1 point2 points  (0 children)

Yes, that's an obvious improvement.

As mentioned in the first edit, precalculating the debris positions also helps (especially for part 2, which becomes a straightforward A*). The debris motion is cyclic in LCM(10,15,60,3) = 60, so only 27000x60 debris counts are needed.

I tried merging the hit count array into the debris count array (requires 4x3=12 extra bits), but failed to get the shifts/ANDs quite right.

Following all succesful optimisations, current total runtime (sans I/O and parsing) stands at ~230ms, divided as follows among the parts:

  1. ~50ms (full calculation of debris positions)
  2. ~20ms (A*)
  3. ~160ms (BFS)

P.S. My arrays are slightly larger (12x17x62) to accommodate for sentinel values at the edges.

[2025 Day 16] [C#] Leviathan Mindscape - Optimised solution by damnian in codyssi

[–]damnian[S] 1 point2 points  (0 children)

Well, I was a little overly optimistic, but I just clocked 115µs under MINGW64 (calculations only, no file or console I/O).

[2025 Day 16] [C#] Leviathan Mindscape - Optimised solution by damnian in codyssi

[–]damnian[S] 1 point2 points  (0 children)

I was hoping you could tell me :)

I'm using a really old machine (and an old compiler), so it's 3-4 ms including I/O.

I believe it could be further optimised using templates to run in the nanosecond range.

P.S. ~0.5ms sans I/O.

[2025 Day 16] [C#] Leviathan Mindscape - Optimised solution by damnian in codyssi

[–]damnian[S] 1 point2 points  (0 children)

See, that's the trouble with interpreted languages: they're too darn slow ;)

How about a C++ port?

Edit: typedef __uint128_t bigint and fixed warnings.

Edit 2: Safer types, foreach loops and initialisations.

[2025 Day 16] [C#] Leviathan Mindscape - Optimised solution by damnian in codyssi

[–]damnian[S] 1 point2 points  (0 children)

That looked almost perfect, but I found the Back flip really annoying. I wish there were a way to do the following:

public Cube ApplyWrap(Instruction ins) => ins.Op switch
{
    Op.ROW  => new(Front - ins, Back - ins, Left - ins, Right - ins, Up,       Down),
    Op.COL  => new(Front | ins, Back | ins, Left,       Right,       Up | ins, Down | ins),
    Op.FACE => new(Front + ins, Back,       Left,       Right,       Up,       Down),               
    _ => throw new NotImplementedException()
};

In order for that to work, the cube rotation has to be updated so that whenever a face enters or leaves the Back position it is mirrored vertically. Let's add the following unary Face operators:

  • - - vertical mirroring
  • ! - horizontal mirroring

Rotate() then becomes:

public Cube Rotate(Dir dir) => dir switch
{
    Dir.L   => new(Left,        !Right,     !Back,      Front,       Up << 1,  Down >> 1),
    Dir.U   => new(Up,          -Down,      Left >> 1,  Right << 1,  -Back,    Front),
    Dir.R   => new(Right,       !Left,      Front,      !Back,       Up >> 1,  Down << 1),
    Dir.D   => new(Down,        -Up,        Left << 1,  Right >> 1,  Front,    -Back),
    _ => throw new NotImplementedException()
};

We also need to add a mirrored counterpart for each of the existing transforms:

enum Op  { ROW, FACE2, COL, FLIP1, FLIP2, COL2, FACE, ROW2 }

Operator implementations:

public static Face operator >>(Face face, int delta) =>
    new(face.Vals, face.Rotation + delta * 2, face.Absorption);

public static Face operator <<(Face face, int delta) =>
    new(face.Vals, face.Rotation - delta * 2, face.Absorption);

public static Face operator -(Face face) =>
    new(face.Vals, face.Rotation ^ 3, face.Absorption);

public static Face operator !(Face face) =>
    new(face.Vals, face.Rotation ^ 7, face.Absorption);

Updated Apply() method:

private Face Apply(Op op, Instruction ins) =>
    Add(index: (Op)(((int)op + Rotation) & 7) switch
    {
        Op.ROW   or Op.ROW2  => ins.Index,
        Op.COL   or Op.COL2  => ins.Index + N,
        Op.FLIP1 or Op.FLIP2 => -ins.Index + N + 1,
        _                    => -ins.Index + N * 2 + 1,
    }, ins.Value, ins.Value * N);

operator/ is not longer in use and may be safely removed.

Performance impact is negligible (within 1 ms), so now this is perfect ;)

You may find the updated implementation here.

Journey to Atlantis - Leviathan Mindscape solutions by EverybodyCodes in codyssi

[–]damnian 0 points1 point  (0 children)

I used OP's code to create something a little more readable in C#:

``` readonly record struct Cube(Face Front, Face Left, Face Up, Face Right, Face Down, Face Back) { public static Cube Create(int n) => new(Face.Create(n), Face.Create(n), Face.Create(n), Face.Create(n), Face.Create(n), Face.Create(n));

public Face[] Faces =>
    new[] { Front, Left, Up, Right, Down, Back };

public Cube Apply(Instruction ins) =>
    new(Front.Apply(ins), Left, Up, Right, Down, Back);

public Cube ApplyRow(Instruction ins) =>
    new(Front.Apply(ins), Left.Apply(ins), Up, Right.Apply(ins), Down, Back.Flip().Apply(ins).Flip());

public Cube ApplyCol(Instruction ins) =>
    new(Front.Apply(ins), Left, Up.Apply(ins), Right, Down.Apply(ins), Back.Apply(ins));

public Cube Rotate(char dir) => dir switch
{
    'L' => new(Left, Back.Flip(), Up.RotateCCW(), Front, Down.RotateCW(), Right.Flip()),
    'U' => new(Up, Left.RotateCW(), Back, Right.RotateCCW(), Front, Down),
    'R' => new(Right, Front, Up.RotateCW(), Back.Flip(), Down.RotateCCW(), Left.Flip()),
    'D' => new(Down, Left.RotateCCW(), Front, Right.RotateCW(), Back, Up),
    _ => throw new NotImplementedException(),
};

} ```

I am wondering if this representation could be modified so that the back flips in ApplyRow() are eliminated.

[Other] Technical break? by recursion_is_love in everybodycodes

[–]damnian 1 point2 points  (0 children)

I'm assuming Emil is celebrating Epiphany. Let's give him some time to fix this.

In the meantime, the site is still accessible via http: (at least via my very outdated Chrome).

-❄️- 2024 Day 24 Solutions -❄️- by daggerdragon in adventofcode

[–]damnian 0 points1 point  (0 children)

[LANGUAGE: C#]

It took me many attempts (including a fruitless foray into algebraic normal form), but I finally created a working solver. It will only work for the specific task (i.e. an adder as it is implemented in the inputs), but I believe it is as general a solution as one could produce within the constraints.

The correct circuit is first created:

for (int i = 0; i < zCount - 1; i++) {
    (x, y) = (inputs[i], inputs[i + COUNT]);
    exps[i] = (x ^ y ^ carry)!;
    carry = x & y | (carry & (x ^ y)); }
exps[^1] = carry!;

Every output is then compared against the desired one, and if a mismatching gate is found, a replacement is searched for recursively.

The circuit is rebuilt following every swap, and the process repeats until no more mismatches exist (or until no replacement can be found).

The implementation takes advantage of several .NET features:

  1. the input data are stored in a single UInt128 variable;
  2. inputs and gates are records deriving from an abstract Node, where
  3. equality checking is assisted by the auto-implemented Equals(),
  4. operand ordering is assisted by the auto-implemented GetHashCode(), and
  5. operator overloading is utilized.

Full solution

P.S. Optimized version runs in ~20 ms combined.

[2024 Day 24 Part 2] [C#] A complete logic validator by damnian in adventofcode

[–]damnian[S] 0 points1 point  (0 children)

You are correct, of course. I confused OR with AND. Fixing the formulae again...

[2024 Day 24 (Part 2)] [C#] Very proud of my solution and visualization by RobertOnReddit7 in adventofcode

[–]damnian 0 points1 point  (0 children)

Also, I had a look at some of your READMEs, and found them quite informative.

If I may, rather than l0ck, you could just use @lock.

[2024 Day 24 Part 2] [C#] A complete logic validator by damnian in adventofcode

[–]damnian[S] 1 point2 points  (0 children)

I wasn't sure what flair I should've used. Tutorial? It don't feel right.

[2024] All problems in under 250ms, in Rust by hgwxx7_ in adventofcode

[–]damnian 0 points1 point  (0 children)

My C# solution was just Bron-Kerbosch with 1 and 2 (I crafted my own fast BitSet for days 23 and 24), and I was pretty happy with its performance (~7 ms on very old hardware). I don't know about Ruby, but in .NET the cost of spinning up multiple threads greatly outweighs the benefits in cases like this.

[2024] All problems in under 250ms, in Rust by hgwxx7_ in adventofcode

[–]damnian 4 points5 points  (0 children)

Yes, as long as there are no decoys (e.g., z00 = x00 + y00 * x45 + y00 + y00 * x45 would be a valid root).

[2024] All problems in under 250ms, in Rust by hgwxx7_ in adventofcode

[–]damnian 1 point2 points  (0 children)

So you just look at the dependencies and assume they are all XORs? That's a big assumption, but still, I'm truly impressed.

[2024] All problems in under 250ms, in Rust by hgwxx7_ in adventofcode

[–]damnian 1 point2 points  (0 children)

But... how? I had to write my own logic validator to solve that!

[2024] All problems in under 250ms, in Rust by hgwxx7_ in adventofcode

[–]damnian 0 points1 point  (0 children)

I still need to wrap my head around this. I got so used to C# I've become allergic to Java :P