• 2 Posts
  • 96 Comments
Joined 2 years ago
cake
Cake day: December 31st, 2023

help-circle













  • NodeBB or maybe piefed to host announcements and provide a place for questions and feedback.

    Consider creating an account for each household with a “correct horse battery staple” style password that’s easy to input on mobile, print out a little slip of paper with an explanation blurb and account name & password, and deposit in their mailbox.

    Do not expect any users until you’ve hosted several game nights that had multiple attendees. From what you say you are the events committee, not the online life committee. I would thus recommend to stay focused on events until people bring up, unprompted, a desire for more casual day-to-day interactions. You want to be integrating into their existing habits, not trying to replace them. Let the “switching” happen on their own initiative lest they feel like they’re being co-opted for your own personal agenda.


  • (Browser-based) Javascript

    My initial approach was to consider each junction as a circuit, and then merge the closest circuits. Took me way to long to realize the problem statement for part 1 made this unworkable (as you need to count redundant connections as “attempts”). Thankfully part 2 doesn’t care about how many connections you make, so I was able to reuse that code to solve part 2.

    To solve part 1 “the right way”, I first thought I had to store a circuit as a collection of pairs of junctions (literally, the collection of connections). Oh god was that messy code; 3 layers of nested for-loops and it still wasn’t getting close to the answer. I eventually realized I could reference the junctions’ indices in the input to simplify things, allowing me to manipulate simple sets of ints. Combine with pre-calculating the distances once before starting the connecting/merging and you end up with a surprisingly simple and snappy algorithm.

    Given I realized these optimizations after restarting part 1, my solution for part 2 doesn’t take advantage of any of them and takes an eye-watering 22 seconds to terminate on average. It probably re-computes more distances than it computes new ones, for each iteration…

    Code
    function getExampleText() {
      return `162,817,812
    57,618,57
    906,360,560
    592,479,940
    352,342,300
    466,668,158
    542,29,236
    431,825,988
    739,650,466
    52,470,668
    216,146,977
    819,987,18
    117,168,530
    805,96,715
    346,949,466
    970,615,88
    941,993,340
    862,61,35
    984,92,344
    425,690,689
    `
    }
    function part1(inputText, maxConnections) {
      const junctions = inputText.trimEnd().split('\n')
        .map(line => line.split(',')
          .map(strValue => Number.parseInt(strValue, 10)));
      // compute the distance between each junction exactly once
      const annotatedDistances = Array(Math.ceil(((junctions.length - 1) ** 2) / 2));
      let counter = 0;
      for (let i = 0; i < junctions.length; i++) {
        const [xI, yI, zI] = junctions[i];
        for (let j = i + 1; j < junctions.length; j++) {
          const [xJ, yJ, zJ] = junctions[j];
          const distanceSquared = (xJ - xI) ** 2 + (yJ - yI) ** 2 + (zJ - zI) ** 2;
          annotatedDistances[counter] = [distanceSquared, i, j];
          counter++;
        }
      }
      // sort the pairs of junctions by closest to farthest
      annotatedDistances.sort(([dA], [dB]) => dA - dB);
      // connect the maxConnections-closest junctions
      const circuits = [];
      for (const [_, i, j] of annotatedDistances.slice(0, maxConnections)) {
        // find any existing circuit(s) that already contain(s) one of the junctions
        let existingCircuits = [];
        for (let circuitIndex = 0; circuitIndex < circuits.length; circuitIndex++) {
          const circuit = circuits[circuitIndex];
          if (circuit.has(i) || circuit.has(j)) {
            existingCircuits.push(circuitIndex);
          }
        }
        // 3 possible cases:
        // the junctions are not part of any existing circuits => connecting them creates a new circuit
        if (existingCircuits.length === 0) {
          circuits.push(new Set([i, j]));
        }
        // the junctions are part of 1 existing circuit => connecting them extends this existing circuit to encompass an additional junction (if only 1 junction is already in this circuit)
        else if (existingCircuits.length === 1) {
          const circuitToExtend = circuits[existingCircuits[0]];
          circuitToExtend.add(i);
          circuitToExtend.add(j);
        }
        // the junctions are part of 2 distinct existing circuits => connecting them merges these two circuits
        else if (existingCircuits.length === 2) {
          // merge circuit(s) with new connection between junctions i and j
          const circuitMergerIndex = existingCircuits.shift();
          for (const circuitToBeMergedIndex of existingCircuits) {
            circuits[circuitMergerIndex] = circuits[circuitMergerIndex].union(circuits[circuitToBeMergedIndex]);
            circuits.splice(circuitToBeMergedIndex, 1);
          }
        }
      }
      circuits.sort((a, b) => b.size - a.size);
    //console.debug({ sortedCircuits: structuredClone(circuits) });
      return circuits.slice(0, 3).reduce((accu, next) => accu * next.size, 1)
    }
    {
      const start = performance.now();
    //const result = part1(getExampleText(), 10);
      const result = part1(document.body.textContent, 1_000);
      const end = performance.now();
      console.info({
        day: 7,
        part: 1,
        time: end - start,
        result
      });
    }
    
    function part2(inputText) {
      const circuits = inputText
        .trimEnd()
        .split('\n')
        .map(line => ([
          line.split(',')
          .map(strVal => Number.parseInt(strVal, 10))
        ]))
      let junctionA, junctionB;
      while (circuits.length > 1) {
        let smallestSquaredDistance = Number.POSITIVE_INFINITY;
        let toConnectA, toConnectB;
        for (const circuitA of circuits) {
          for (const circuitB of circuits) {
            if (circuitA === circuitB) {
              continue;
            }
            let squaredCircuitDistance = Number.POSITIVE_INFINITY;
            for (const [xA, yA, zA] of circuitA) {
              for (const [xB, yB, zB] of circuitB) {
                const distance = (xB - xA) ** 2 + (yB - yA) ** 2 + (zB - zA) ** 2;
                if (distance < squaredCircuitDistance) {
                  squaredCircuitDistance = distance;
                  junctionA = [xA, yA, zA];
                  junctionB = [xB, yB, zB];
                }
              }
            }
            if (squaredCircuitDistance < smallestSquaredDistance) {
              smallestSquaredDistance = squaredCircuitDistance;
              toConnectA = circuitA;
              toConnectB = circuitB;
            }
          }
        }
        if (toConnectA.length > toConnectB.length) {
          toConnectA.push(...toConnectB);
          const bIndex = circuits.indexOf(toConnectB);
          circuits.splice(bIndex, 1);
        } else {
          toConnectB.push(...toConnectA);
          const aIndex = circuits.indexOf(toConnectA);
          circuits.splice(aIndex, 1);
        }
      }
      return junctionA[0] * junctionB[0];
    }
    {
      const start = performance.now();
    //  const result = part2(getExampleText());
      const result = part2(document.body.textContent);
      const end = performance.now();
      console.info({
        day: 7,
        part: 2,
        time: end - start,
        result
      });
    }
    


  • Interesting read, but I’m perhaps even less convinced than before that chat-oriented programming is a better use of my time than learning to write the thing myself. Especially having to work about token quotas is frightening; I don’t have to spend any money to think for as long as the problem requires me to, but each “thought” you make the LLM agent do is cents if not dollars up in flames.

    I’ll continue to play around with self-hosted, local models for now.