AOC 2023: Problem 20

aoc.ts

// ===========================================================
// PART 1
// ===========================================================

let answer1 = 0;
const parsed = input.split(`\n`);

const links = {} as Record<string, string[]>;
const backLinks = {} as Record<string, string[]>;

/**
 * If a flip-flop module receives a high pulse, it is ignored and nothing happens.
 *
 * However, if a flip-flop module receives a low pulse, it flips between on and
 * off. If it was off, it turns on and sends a high pulse. If it was on, it turns
 * off and sends a low pulse.
 */
type FlipFlop = {
  type: 'flipflop';
  on: boolean;
};

/** Conjunction modules (prefix &) remember the type of the most recent pulse
 * received from each of their connected input modules;
 *
 * they initially default to remembering a low pulse for each input.
 *
 *  When a pulse is received, the
 * conjunction module first updates its memory for that input.
 *
 * Then, if it
 *  remembers high pulses for all inputs, it sends a low pulse; otherwise,
 * it sends a high pulse. */
type Conjuction = {
  type: 'conjunction';
  lastHigh: Record<string, boolean>;
};

type Broadcoast = {
  type: 'broadcast';
};

type Output = {
  type: 'output';
};

let state = { output: { type: 'output' } } as Record<string, FlipFlop | Conjuction | Broadcoast | Output>;

for (const line of parsed) {
  let [name, dList] = line.split(' -> ');
  const destList = dList.split(', ');
  if (name.startsWith('%')) {
    name = name.substring(1);
    links[name] = destList;
    state[name] = { type: 'flipflop', on: false };
  } else if (name.startsWith('&')) {
    name = name.substring(1);
    links[name] = destList;
    state[name] = { type: 'conjunction', lastHigh: {} };
  } else if (name === 'broadcaster') {
    links[name] = destList;
    state[name] = { type: 'broadcast' };
  } else throw new Error('Boo.');

  for (const backLink of destList) {
    if (!backLinks[backLink]) backLinks[backLink] = [];
    backLinks[backLink].push(name);
  }
}

// Init conjunction state
for (const [name, mem] of Object.entries(state)) {
  if (mem.type !== 'conjunction') continue;
  for (const backLink of backLinks[name]) {
    mem.lastHigh[backLink] = false;
  }
}

const initalState = cloneDeep(state);

let highs = 0;
let lows = 0;

function pushButton() {
  const gotLow: string[] = [];
  graphSearch({
    initial: [{ from: 'button', to: 'broadcaster', high: false }],
    toKey(current, iteration) {
      return String(iteration);
    },
    order: 'breadth',
    isDone(state, iteration) {
      return iteration > 0 && isEqual(state, initalState);
    },
    onVisit(current) {
      const { from, to, high } = current;
      if (backLinks['vr'].includes(to) && !high) {
        // console.log(`${to} received ${high ? 'high' : 'low'}`);
        gotLow.push(to);
      }
      if (high) highs++;
      else lows++;
      // console.log(`${state.from} => (${state.high ? 'high' : 'low'}) => ${state.to}`);
    },
    newStates(current, onNewState) {
      const { from, to, high } = current;
      const mem = state[to]!;
      if (!mem) {
        // console.error(`Unknown destination '${to}'`); // Only seems to be "rx"
        return;
      }
      switch (mem.type) {
        case 'broadcast': {
          for (const next of links[to]) {
            onNewState({ from: to, to: next, high });
          }
          break;
        }
        case 'conjunction': {
          mem.lastHigh[from] = high;
          const allInputsHigh = Object.values(mem.lastHigh).every((high) => !!high);
          // console.log('Checking ivnerter', to, mem.lastHigh);
          for (const next of links[to]) {
            onNewState({ from: to, to: next, high: !allInputsHigh });
          }
          break;
        }
        case 'flipflop': {
          if (high) {
            // console.log('Flip', to, 'high. Stop');
            break;
          }
          mem.on = !mem.on;
          for (const next of links[to]) {
            onNewState({ from: to, to: next, high: mem.on });
          }
          break;
        }
        case 'output': {
          console.log(`Output received: '${high}'`);
          break;
        }
        default:
          throw new Error('Casper!');
      }
    },
  });
  return gotLow;
}

for (let i = 0; i < 1000; i++) {
  pushButton();
  if (isEqual(state, initalState)) {
    // TODO: MATH IF NEEDED
    console.log(`Finished early after ${i} iterations`);
    break;
  }
}

// console.log({ lows, highs });
answer1 = lows * highs;

console.info(`Answer1: ${chalk.yellow(answer1)} after ${chalk.yellow((performance.now() - start).toFixed(2))}ms`);

// ===========================================================
// PART 2
// ===========================================================

let answer2 = 0;

state = cloneDeep(initalState);

const lowIterations = {} as Record<string, number>;

for (let i = 0; i < 1e6; i++) {
  const gotLow = pushButton();
  for (const low of gotLow) {
    if (lowIterations[low]) continue;
    lowIterations[low] = i + 1;
  }
  if (Object.keys(lowIterations).length === 4) break;
}

answer2 = product(Object.values(lowIterations));

console.info(`Answer2: ${chalk.yellow(answer2)} after ${chalk.yellow((performance.now() - start).toFixed(2))}ms`);