DEV Community: Joseph

HTML Elements, the `caption` disagreement

Joseph — Mon, 05 Oct 2020 06:48:50 +0000

Recently I wanted to build a table with double captions, one at the top and one at the bottom.

An HTML Table has a lot of elements that make it up, for example:

thead, defines a set of rows defining the head of the columns of the table.

tfoot, defines a set of rows summarizing the columns of the table.

And there is an HTML element to caption a table.

caption specifies the caption (or title) of a table

So I thought, I'll just put two of them and position them with CSS.

<table>
   <caption class="top">
     first
  </caption>
  <caption class="bottom">
     second
  </caption>
  <thead>
    <tr>
      <th>hello</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>world</td>
    </tr>
  </tbody>
</table>

The caption element is so convenient that, to position it, there is a CSS rule we can use.

.top {
    caption-side: top; 
}

.bottom {
    caption-side: bottom;
}

top is the initial-value for caption-side.

All set and done, I pushed my changes and prepared to bike home. However on my way down to my bike, I started to check how the solution looked like on the phones I have available. Chromium based (Chrome and Brave) looked alright. Safari, check.

Only Firefox was left, which is usually a very strict browser when it comes to HTML semantics, but I thought, double captions should be fine. However, this solution did not work on Firefox.

Here is a very simplified codepen, open it on Chrome, works fine, but Firefox, does not play along. Or perhaps am I playing foul?

Firefox only renders the first caption tag. The rest of tags, all have size 0x0 and have perspective-origin and transform-origin, set to 0px 0px.

A little bizarre behavior is that if you nest a caption within a caption, the browser flattens them in the DOM.

Also if the nested caption has a different caption-side, Chrome respects the CSS declaration.

Chrome Version 85.0.4183.121

Firefox Browser for Developers, version 82.0b6 (64-bit)

I did a few tests on IE 11, using Browserling, and IE is on the rendering many captions side. Though I didn't test nesting captions, I reckon it should work fine.

So who's right?

The HTML Living Standard, says:

Contexts in which this element can be used:

As the first element child of a table element.

Strictly speaking then, there should not be a possibility to have multiple captions.

The same is stated in the HTML5 Recommended specification.

The gold nugget lies in the HTML 4.01 Specification, which says:

A TABLE element may only contain one CAPTION element.

So that's the root of the behavior shown by Firefox.

Interestingly enough the HTML 4.01 also says that one should use the summary tag for table, this use case is deprecated and instead the summary tag is used instead with the details tag.

The [HTML 5 Recommended] specification also refers to the table model, where it states:

In addition to cells, columns, rows, row groups, and column groups, tables can have a caption element associated with them. This gives the table a heading, or legend.

Again, a caption element is the language used. So it makes sense to expect only one caption.

After finding this out, I decided to change my design and markup instead of forcing a workaround.

I think if you really wanted to hack this, you'd have to change the display property of the caption and then try to position your content with transform, but I wouldn't recommend it.

Happy coding!

Filtering in TypeScript

Joseph — Tue, 01 Sep 2020 08:33:46 +0000

Say that you have this type:

type List = (Subject | null | undefined)[]

Perhaps it is the result of querying for a list of identifications, where not every entry is guaranteed to have a result.

Nothing strange so far. However, let's say you now want to remove null and undefined elements, in order to do a further operation on the leftover Subject elements.

interface Subject {
    id: string | number
    name: string
}

type List = (Subject | null | undefined)[]

const joe: Subject = { id: 0, name: 'joe' }
const jane: Subject = { id: 10, name: 'jane' }
const list: List = [joe, null, undefined, jane]

const names = list.filter(entry => !!entry).map(entry => entry.name)

console.log(names)

Unfortunately this does not work:

TSError: ⨯ Unable to compile TypeScript:
index.ts:12:58 - error TS2533: Object is possibly 'null' or 'undefined'.

We need to tell TypeScript that the filter operation ensures only Subject types are left.

function exists<T>(value: T | null | undefined): value is T {
    return value === (value ?? !value)
}

The exists function, for example, makes sure to assert that value is of type T.

In production code, try to avoid generic naming such as T

To filter and have Subject types as leftover:

interface Subject {
    id: string | number
    name: string
}

type List = (Subject | null | undefined)[]

const joe: Subject = { id: 0, name: 'joe' }
const jane: Subject = { id: 10, name: 'jane' }
const list: List = [joe, null, undefined, jane]

function exists<T>(value: T | null | undefined): value is T {
    return value === (value ?? !value)
}

const names = list.filter(exists).map(entry => entry.name)

console.log(names) // [ "joe", "jane" ]

That's all! Now TypeScript makes sure that name is available on the filtered items.

Type guards are fun!

Expogo - Google Code Jam

Joseph — Thu, 18 Jun 2020 12:27:21 +0000

Expogo is a problem from Google Code Jam 2020 - Round 1B

In this article I explore:

The Problem
A solution
Interactive visualization

The Problem

The full statement can be found here at the Code Jam site.

You have just received the best gift ever: an Expogo stick. You can stand on it and use it to make increasingly large jumps.

A few facts from the problem statement:

You'll use the Expogo in an infinite two-dimensional plane
You start at point P = (0, 0)
Your goal is to reach point P = (X, Y)
All coordinates are integers
Land exactly at P = (X, Y), in as few jumps as possible
For the i-th jump, the Expogo moves you 2 ^{i - 1}
- First jump moves you 1 unit
- Second jump moves you 2 units
- Third moves you 4 units, etc...
You can aim the Expogo in any cardinal direction: North, South, East, or West
If it is impossible to land at P = (X, Y), say it so by answering IMPOSSIBLE
Otherwise, answer with a string of cardinal directions ordered from first to last jump

For example, to arrive at P = (2, 3), you'd do South, East, North, then the answer is SEN . Contrary, arriving at P = (-1, -1) is IMPOSSIBLE.

A solution

This solution uses coordinate transformations

Interestingly, the set of possible Expogo jumping lengths, has only one odd number, that is, 1.

Taking either North or South, first, makes the end Y coordinate odd, and the end X coordinate will be even.
Taking either West or East, first, makes the end X coordinate odd, and the end Y coordinate will be odd.

That means that jumping with the Expogo any number of times, ends up with an odd coordinate and an even coordinate.

We can't have both even coordinates X, Y
We can't have both odd coordinates X, Y

Immediately conclude that jumping to, for example, (R, R) or (R, -R) is impossible.

A quick way to see if a point P is made up of at both even and odd coordinates it to just add the components and check that the result is NOT even:

const isCoordinateOdd = ({ x, y }) => (x + y) % 2 !== 0;

Remember that odd + even = odd, odd + odd = even, and of course, even + even = even

Let's explore the possibilities now. From any given point P = (X, Y), there's is a set of four points where the Expogo can land us, call this set Q.

const Q = [
    [x + Math.pow(2, i - 1), y], 
    [x - Math.pow(2, i - 1), y], 
    [x, y + Math.pow(2, i - 1)],
    [x, y - Math.pow(2, i - 1)]
];

We can always move the coordinates origin to P, and have:

const Q = [
    [Math.pow(2, i - 1), 0], 
    [-Math.pow(2, i - 1), 0], 
    [0, Math.pow(2, i - 1)],
    [0, -Math.pow(2, i - 1)]
];

As we can see, after the first jump, if we keep moving the origin to the landing place after every jump, then the set of Q points where can land next, is always an even distance away.

Hypothesis

We can scale the coordinate system by dividing the coordinates by 2, but in order to do this, we need to make sure that the target coordinate is (even, even).

For example:

To arrive at P = (2, 3), from (0, 0), lets first jump one unit North, then we are at (0, 1).
Make (0, 1) the new origin, then P = (2, 2) from this new origin
Scale the coordinate system by half, then P = (1, 1)
In this new coordinate system, the Expogo moves again 1 unit!
In this new coordinate system, we are back at (0,0)
Move either, East to (1, 0)
Make (1, 0) the new origin, then P = (0, 1)
Scaling the coordinate system by half is not impossible because 1 is odd
Conclude that this path does not land at P = (2, 3), but rather it leads to P = (2, 1).

In step 1, when we moved the origin to (0, 1), P became (2, 2). We should have concluded immediately that such a move is not good, because in the scaled coordinate system, (1, 1) is impossible to reach.

In fact, any P where the X = Y, even, is already a bad option, no need to do the scale step.

Let's refine the hypothesis:

After moving the origin, we can scale the coordinate system by dividing the coordinates by 2, but in order to do this, we need to make sure that the new target coordinate is (even, even), and that after scaling, the coordinate satisfies X + Y = odd number.

Let's try to arrive at P = (2, 3) again:

From (0, 0) there's four moves, of one unit, we must move North or South because the odd coordinate, 3, lies in the Y axis
Try to jump North and move the coordinate system origin to (0, 1)
Scale by half, P = (1, 1), impossible
Try to jump South and move the coordinate system origin to (0, -1), then P = (2, 4)
Scale by half, makes P = (1, 2), possible path
Try to jump East one unit, and move the coordinate system origin to (0, 1), then P = (0, 2)
Scale by half, makes P = (0, 1), possible path
Try to jump North, one unit, and we've reached P.
Then the answer is SEN

The strategy to follow then is:

Check if the target P has become (0 , 0)
If not, check if P is odd coordinate
if so, move towards the odd coordinate of P
Transform the coordinate system, accumulating the steps taken
Repeat

With JavaScript, we can write moveExpogo which does this recursively.

const moveExpogo = ({ x, y, steps = "" }) => {
  if (x === 0 && y === 0) {
    return steps;
  }

  const isOddCoordinate = isCoordinateOdd({ x, y });

  if (!isOddCoordinate) {
    return IMPOSSIBLE;
  }

  const { step, nextX, nextY } = moveTowardsOdd({ x, y });
  return moveExpogo({ x: nextX, y: nextY, steps: `${steps}${step}` });
};

Let's write the moveTowardsOdd function, where the magic happens.

const scale = n => n / 2;
function moveTowardsOdd({ x, y }) {
  if (x === 1 && y === 0) {
    // can be finished in one move by moving EAST
    return { step: EAST, nextX: scale(x - 1), nextY: y };
  }

  if (x === -1 && y === 0) {
    // can be finished in one move by moving WEST
    return { step: WEST, nextX: scale(x + 1), nextY: y };
  }

  if (x === 0 && y === 1) {
    // can be finished in one move by moving NORTH
    return { step: NORTH, nextX: x, nextY: scale(y - 1) };
  }

  if (x === 0 && y === -1) {
    // can be finished in one move by moving SOUTH
    return { step: SOUTH, nextX: x, nextY: scale(y + 1) };
  }

  if (x % 2 !== 0) {
    // move EAST
    const wouldBeOdd = isCoordinateOdd({ x: scale(x - 1), y: scale(y) });
    if (wouldBeOdd) {
      return { step: EAST, nextX: scale(x - 1), nextY: scale(y) };
    }
    // better to move WEST
    return { step: WEST, nextX: scale(x + 1), nextY: scale(y) };
  }

  if (y % 2 !== 0) {
    // move NORTH
    const wouldBeOdd = isCoordinateOdd({ x: scale(x), y: scale(y - 1) });
    if (wouldBeOdd) {
      return { step: NORTH, nextX: scale(x), nextY: scale(y - 1) };
    }
    // better to move SOUTH
    return { step: SOUTH, nextX: scale(x), nextY: scale(y + 1) };
  }
}

Since moveTowardsOdd is called by moveExpogo only if the coordinate is odd, then we can conclude that the if branches cover all possible cases.

Remember, odd coordinates (X, Y) in this context are, those where X + Y = odd

The properties nextX and nextY represent P when the origin is moved to a new position.

Check if the P coordinate is odd, if not, conclude the whole job is IMPOSSIBLE.
If so move towards the odd coordinate
Check if there's such a move that ends the jump sequence
In either case, move the origin to the landing point,
and scale the coordinate system by half
Repeat until you arrive at the target P

These two functions solve the problem, for all test sets of Code Jam, even when the coordinates get pretty large.

Test set 3 (Visible Verdict)

1 ≤ T ≤ 100.
-10⁹ ≤ X ≤ 10⁹.
-10⁹ ≤ Y ≤ 10⁹.

My Code Jam JavaScript implementation, that takes cases from stdin, can be found here.
A full implementation to run to your hearts desire can be found in this REPL.

Visualization

These type of problems are challenging but also very fun!

Since we've got a string containing the jumping directions at ever i-th step, we can derive the coordinates where the Expogo lands us to reach point P.

JavaScript's array indexing is zero based, so there's no need to subtract one from it when calculating the Expogo jumping distance

const dir2Coords = (directions) =>
  directions.split("").reduce((prev, curr, index) => {
    const [[x, y] = [0, 0]] = prev.slice(-1);
    switch (curr) {
      case NORTH:
        return [...prev, [x, y + Math.pow(2, index)]];
      case SOUTH:
        return [...prev, [x, y - Math.pow(2, index)]];
      case EAST:
        return [...prev, [x + Math.pow(2, index), y]];
      case WEST:
        return [...prev, [x - Math.pow(2, index), y]];
      default:
        throw new Error("Invalid direction");
    }
  }, []);

This REPL does just that! Now we can use any graphical tool to draw the path taken!

I'll try out three.js for this. In particular the Voxel example, which already makes use of plane and targets coordinates given by the mouse position.

When the user holds down the shift key and clicks on a point, the Expogo path is drawn. Additionally, the mouse is followed by a cube, which is colored red if its impossible for the Expogo to reach it, otherwise it is colored green.

Live version here.

I also try to increase browser support as much as possible by avoiding arrow functions, though this might be futile.

Have you ever tried to compete in Code Jam? I assure you it is very fun!

Happy Hacking!

Advent of Code day 22 - 2019

Joseph — Mon, 08 Jun 2020 11:11:13 +0000

Advent of Code Day 22

Using JavaScript to calculate the position of a card on a deck with a total of 119 315 717 514 047 cards after shuffling it 101 741 582 076 661 times.

The problem statement in length can be found here.

The problem

The input for the problem consists of a list of shuffling instructions, to be done on a card deck. The deck is defined by its length.

The cards are numbered from 0 to length - 1 and are initially ordered in ascending order.

There are three types of shuffles, NEW STACK, INCREMENTAL or CUT.

NEW STACK takes no parameters, which is itself a type of parameter.
INCREMENTAL and CUT take in a defining parameter

One could say that NEW STACK takes in an undefined parameter

Part 1 requires to you to find out the position of card 2019 after one shuffle on a deck of length 10007.

Part 2 requires to you to find out which card is at position 2020 after a very large number of shuffles, on a very large deck.

Part 1

Easy enough, we can define a reducer, which goes over the list of shuffle instructions, pattern matching against them, collects the parameter of each instruction, and does the work on the deck.

The shuffle parameter is referred to as payload from now on.

const reducer = (deck, action) => {
  const copy = [...deck];
  switch (action.type) {
    case NEW_STACK:
      return copy.reduce((prev, curr) => [curr, ...prev], []);
    case INCREMENT:
      return dealWithIncrement(copy, action.payload);
    case CUT:
      const cut = Math.abs(action.payload);
      if (action.payload < 0) {
        // cut from the bottom to the top
        const offset = copy.length - cut;

        return copy
          .slice(offset)
          .concat(copy.slice(0, offset))
          .flat();
      }

      return copy
        .slice(cut)
        .concat(copy.slice(0, cut))
        .flat();
  }
};

Where the deal with increment is defined as:

const dealWithIncrement = (deck, increment) => {
  let newDeck = [];
  let pointer = 0n;
  let index = 0n;

  while (index < BigInt(deck.length)) {
    newDeck[pointer % deck.length] = deck[index];

    pointer = pointer + increment;
    index = index + 1n;
  }

  return newDeck;
};

Because part 2 deals with large integers, begin to use BigInt notation as early as possible.

Although verbose, it is easy to follow. We just need to create a deck array of length 10007, parse the shuffling instructions.

const newDeck = actions.reduce((prev, curr) => reducer(prev, curr), [...deck]);

Where the actions array is the result of matching all instructions in the problem input. Notice that this step parses the payload into BigInt.

const NEW_STACK = "deal into new stack";
const INCREMENT = "deal with increment";
const CUT = "cut";

const instructions = data.split("\n");

const actions = instructions.map(instruction => {
  if (instruction.includes(NEW_STACK)) {
    return { type: NEW_STACK, payload: null };
  }
  if (instruction.includes(INCREMENT)) {
    const [increment] = instruction.split(" ").slice(-1);
    return { type: INCREMENT, payload: BigInt(increment) };
  }
  if (instruction.includes(CUT)) {
    const [cut] = instruction.split(" ").slice(-1);
    return { type: CUT, payload: BigInt(cut) };
  }
});

After running this code, we just need to read the index 2019 in the newDeck. In my case that's 7860.

This solution is very slow. Part 2 uses a deck with length 119_315_717_514_047n. This approach won't cut it!

Using the index

We do not need a representation of the whole deck after a shuffle, we just need to be able to calculate the output index, given an input index.

Let's start naively with the following indexReducer, which still yields 7860 for 2019, for the same actions.

const indexReducer = length => (index, action) => {
  switch (action.type) {
    case NEW_STACK:
      const middle = length % 2n === 0n ? (length - 1n) / 2n : length / 2n;
      if (index !== middle) {
        return middle + (middle - index);
      }
      return index;
    case INCREMENT:
      const increment = action.payload;
      return (index * increment) % length;
    case CUT:
      const cut = action.payload;
      if (cut < 0n) {
        if (index < cut) {
          return index - cut;
        }
        return index - length - cut;
      } else {
        if (index < cut) {
          return index + length - cut;
        }
        return index - cut;
      }
  }
};

The INCREMENT case is the most straight forward. We can definitely improve the NEW STACK and CUT cases.

In the NEW STACK, we notice that the new index is always the length - 1 - index , for odd lengths, which is true for both part 1 and part 2.

Finally the CUT case seems to depend on the sign of the payload. However, when one inspects the branches realizes that the result is always of form index - cut ± length.

const indexReducer = length => (index, action) => {
  switch (action.type) {
    case NEW_STACK:
      return length - 1n - index;
    case INCREMENT:
      const increment = action.payload;
      return (index * increment) % length;
   case CUT:
      const cut = action.payload;
      if (cut < 0n) {
        if (index < cut) {
          return index - cut;
        }
        return index - length - cut;
      } else {
        if (index < cut) {
          return index + length - cut;
        }
        return index - cut;
      }
  }
};

One should observe that the indexes are always in the range between 0 and length - 1.

Indexes higher that L are not possible...

In practice, this means that the results of indexReducer should always be transformed to the said range.

Proof of this is that the INCREMENT case always calculates the remainder of index * increment over the length.

Can a card index be greater than or equal to the number of cards? Pro-tip: It can't be.

We should do this for every case in the reducer. The NEW STACK operation should never yield more than length, so we can leave it as is.

We move on to the CUT case, and see that after applying remainder operation the possible outputs given by index - cut ± length transform to index - cut.

The new reducer then looks like this:

const indexReducer = length => (index, action) => {
  switch (action.type) {
    case NEW_STACK:
      return length - 1n - index;
    case INCREMENT:
      const increment = action.payload;
      return (index * increment) % length;
    case CUT:
      const cut = action.payload;
      return index - cut;
  }
};

By this point we've gained a lot of speed when running the shuffling once, regardless of the deck's length.

The remainder % operations is also known as modulo.

There's one caveat. We've implied that (x - L) % L returns a valid index when doing the CUT case. In JavaScript, this does not hold for negative numbers.

> (-4 - 5) % 5
-4

Meanwhile, Python does the type of modulo we need:

>>> (-4 - 5) % 5
1

To overcome this, define the modulo operation like this:

const mod = length => val => {
  if (val < 0n) {
    return length - mod(length)(-val);
  }
  return val % length;
};

Perhaps the greatest piece of insight, is that, on each case, the indexReducer modifies its input index by a factor, and then adds or subtracts from it.

One can represent this initial condition as index = card, and then every case will modify this, for example, NEW STACK produces index = -card + length - 1.

Next, passing this through INCREMENT give us index = increment * (-card + length - 1) % length, which simplifies to, index = -increment * card % length + length - 1, making sure that we simplify -1 to length - 1 (modulo of -1 over length).

Finally if we apply the CUT case index = (-increment * card % length + length - 1) - cut) % length, one must not forget to take modulo for all the results, which simplifies the expression to, index = -increment * card % length + (length - 1 - cut) % length.

These are all linear transformations!

The order in which these are done, doesn't matter. We'll never have index squared, and we can always simplify to a y = mx + b shape! Fantastic! That means that given the initial mapping where n sits at index n, represented by the identity functions, written as y = 1 * x + 0, we can calculate m and b after a shuffle!

We need to find how m,b change after a shuffle. In the indexReducer we replace index by mx and the constant terms are by b.

const linearEqReducer = length => ([m, b], action) => {
  // index = m * x + b
  // with inputs [m,b];
  switch (action.type) {
    case NEW_STACK:
      // - index * length - 1n
      // - (m * x + b) + length - 1n
      // - m * x + length - 1n + b
      return [-m % length, (length - 1n + b) % length]; // always take % length
    case INCREMENT:
      const increment = action.payload;
      // (index * increment) % length;
      // ((m * x + b) * increment) % length;
      // (m * increment * x) % length + (b * increment) % length;
      return [(m * increment) % lenght, (b * increment) % length]; // always take % length
    case CUT:
      const cut = action.payload;
      // m * x + b - cut;
      // (m * x) % length + (b - cut) % length
      return [m % length, (b - cut) % length]; // always take % length
  }
};

Math to the rescue

Treating the shuffle as a black box, call it f, which takes in m,b as inputs, and returns m',b':

If we represent the inputs as a vector v:

If the transformations are linear, it must be true that, there's a matrix A, such that:

Next, to calculate 2 shuffles, looks like this:

Or better yet:

And in general, for n shuffles:

Then one can easily calculate the matrix A to the power of n, using the binary exponentiation technique.

To pull this off, write the binary representation of your target number, for instance 13 is 1101. Move from right to left, starting with 1 and then multiplying by A at every step.

Then filter out the products which were created under a zero digit.

Finally, we multiply all of the leftover products.

Enough Math for now. A JavaScript implementation looks like this:

const binaryExp = length => (
  number,
  seed,
  prod = (x, y) => (x * y) % length,
  identity = 1n
) => {
  const binary = number
    .toString(2)
    .split("")
    .reverse();

  return binary
    .reduce(
      prev => {
        const [last] = prev.slice(-1);
        return [...prev, prod(last, last)];
      },
      [seed]
    )
    .filter((_, i) => binary[i] === "1")
    .reduce((prev, curr) => prod(prev, curr), identity);
};

This function takes length, to handle modulo operations as matrices are multiplied. It returns a function with closure over the length.

This function, in turn, optionally takes product function, as well as, an identity to be used. When using matrices products the identity should be the identity matrix. If no prod is passed, then this function calculates binary exponentiation for numbers, and the identity defaults to 1.

The binExp function returns a function which, multiplies seed as many times as binary digits exist in number, and then collects a product that is seed ^ number, in a very fast and efficient way, O(log n).

We can now shuffle a large number of times, with log n complexity, as long as we can find the A matrix. Here I initially made a mistake. I assumed A to be 2x2 matrix.

Looking back, this should have been easily spotted, because the indexReducer and linearEqReducer clearly show that the variations of m and b are independent of each other. A matrix of 2x2 implies the opposite!

This is wrong. A better way is to say A is the matrix that applies to m, and D the matrix that applies to b. The sub vector m now equal to M0 and sub vector b equal to B0.

From the linearEqReducer, we see that m is always a multiplication p*m. With this we simplify A. Also, every new b value, depends only on b and not d, so j must be 0.

Apply m=1 and b=0 to the linearEqReducer, and to obtain p and h*d:

const [p, hd] = actions.reduce(
  (prev, action) => linearEqReducer(length)(prev, action),
  [1n, 0n]
); // h * d

And, then, applym=0 and b=1, this time the first value can be ignored.

const [, gh] = actions.reduce(
  (prev, action) => linearEqReducer(length)(prev, action),
  [0n, 1n]
); // gh is g * b + h * d

Calculate g * b by doing gh - hd = g * b + h * d - h * d = g * b. Knowing that b equals 1, we now have g.

Moreover, when we shuffle for 1 * x + 0 we take the initial deck and shuffle it once into m * x + b so hd is the next b. If we want d to be constant, then k * d = d then k = 1.

We notice that the d value is arbitrary, and different than 0, as long as we can simplify hd = h * d to h = hd / d. The easiest is for d=1. The value c is also arbitrary, and given the shape of A, we can just set it to 0.

Where g = gh - hd and h = hd derived from:

const [p, hd] = actions.reduce(
  (prev, action) => linearEqReducer(length)(prev, action),
  [1n, 0n]
);

const [, gh] = actions.reduce(
  (prev, action) => linearEqReducer(length)(prev, action),
  [0n, 1n]
);

Replacing all matrices, the M,B vectors after a shuffle follow this equation.

Part 2

Finally! We run:

const large = 119_315_717_514_047n;
const [p, hd] = actions.reduce(
  (prev, action) => linearEqReducer(large)(prev, action),
  [1n, 0n]
);
const [, gh] = actions.reduce(
  (prev, action) => linearEqReducer(large)(prev, action),
  [0n, 1n]
);

const h = hd;
const g = gh - hd;

Calculate the AD matrix:

const AD = [
  [p, 0n, 0n, 0n],
  [0n, 0n, 0n, 0n],
  [0n, 0n, g, h],
  [0n, 0n, 0n, 1n]
];

Do binary exponentiation for 101_741_582_076_661n:

const dotProduct = length => (left, right) => {
  let result = [];
  for (let i = 0; i < left.length; i++) {
    result[i] = [];
    for (let j = 0; j < right[0].length; j++) {
      let sum = 0n;
      for (let k = 0; k < left[0].length; k++) {
        sum += (left[i][k] * right[k][j]) % length;
      }
      result[i][j] = sum % length;
    }
  }
  return result;
};

const matrixMult = dotProduct(large);

const I = [
  [1n, 0n, 0n, 0n],
  [0n, 1n, 0n, 0n],
  [0n, 0n, 1n, 0n],
  [0n, 0n, 0n, 1n]
];

const total = 101_741_582_076_661n;
const matrix = binaryExp(large)(total, AD, matrixMult, I);

In the above, we define a matrixMult which does the dot product of two matrices, while taking modulo of large on every multiplication and sum performed.

const [[M_], , [B_]] = matrixMult(matrix, initial);
const largeNormalizer = mod(large);
const M = largeNormalizer(M_);
const B = largeNormalizer(B_);

And now have a formula to calculate the index = card * M + B after 101_741_582_076_661n shuffles on a deck with 119_315_717_514_047n cards.

There's just one issue. The problem requires to know which card ends up at index 2020.

That is, we need to solve for x in: y - b = m * x, or (index - B) % length = M * card, and solve for the card.

"Problems worthy of attack prove their worth by fighting back." — Piet Hein

One can just start to increase card until the expression (M * card) % length = (index - B) % length holds true, but that will take any time between 0 and length.

Up to this point the fact that 10007n and 119_315_717_514_047n are primes has not been used. We want to solve, with L=length:

Since r is less than L, we can rewrite like this:

If M is less than the prime L then all possible values of n % L contains M. Also, all natural numbers less than L are part of the set of n % L.

Although the syntax might be confusing, this just means that all possible results of M%L are contained in the set N.

If we limit M to M < L, so that we can eliminate 0 from N. Then we can multiply any n of N by a number less than prime L, call it Q, and take modulo of the result.

This will generate the same set N, albeit, in a different order, N'. Remember that Q would also be part of N.

We can be sure that N and N' are the same set, but with different order, because:

Q and n are both greater than 0, but less than prime L, so their product can never divide L, so none of N' elements is zero.
Any n * Q, for example 2 * Q exists only once, and therefore each modulo is unique. This implies the same number of elements in both sets.

In turn this means that multiplying members of both groups and taking modulo of each product, should be equal.

Again, since each factor of factorial L-1 is less than L, we can simplify the factorial on both sides.

This is called Fermat's Little Theorem. Replacing Q for M and expanding:

We have found the inverse modulo of M modulo L. This means, that x' is M ^ (L-2).

Replacing back in the original formula:

Calculate M^(L-2) using the binary exponentiation once again.

const fastModInv = length => m => {
  return binaryExp(length)(length - 2n, m);
};

const large = 119_315_717_514_047n
const modInverter = fastModInv(large);
const x_inv_mod = modInverter(M_large);
const r = 2020n - B_large;
const largeNormalizer = mod(large);
const card = largeNormalizer(x_inv_mod * r);

And it is done! Full code here.

Summary

Model a shuffle as a black box that takes an index and outputs a new index.
Realize that the black box is a linear transformation on an input equation.
Use a Matrix to model the linear transformation.
Use binary exponentiation to calculate the Matrix that represents a large number of shuffles.
Calculate the linear equation resulting of multiplying the identity linear equation with the Matrix.
Use Fermat's little theorem and binary exponentiation to calculate the inverse modulo.

I solved this problem at around midnight on my local time zone. It was super challenging for me, but I pushed through.

Happy hacking!

Use more HTML Elements - Expand/Collapse with details

Joseph — Thu, 04 Jun 2020 16:12:33 +0000

Before you continue...

This will use JavaScript. A little bit of it.

This time I explore the details and summary elements.

Using JavaScript/CSS to transition max-height we can achieve auto-dimension height effect, while doing collapse/expand of the details element.
Even if JavaScript is disabled, the user will be able to see the hidden contents, without the auto-dimension effect.

More about these elements in the MDN page.

Sadly, these two elements are not supported in IE

Expectation

Implementation

First thing, the HTML. The contents of the summary tags are always shown. Upon user interaction, the other children of details are shown.

For this demo I'll work with only two children, one of which is summary. However the implementation can be adapted to account for many children, or your HTML can be written so that you always have one child besides the summary tag.

<details>
    <summary>Details</summary>
    <p>Some content that reveals more details</p>
</details>

Next the styling, this time the CSS will be very simple.

details {
  height: auto;
  overflow: hidden;
  transition: max-height ease-in-out;
  transition-duration: var(--duration, 0.3s);
}

summary {
    cursor: pointer;
}

Notice I am using a CSS variable with a default value of 0.3s.

Finally the magic, JavaScript.

Somehow gain access to the details element DOM node
Attach a click event listener

When the click event happens

Prevent the event default behavior
Calculate the initial height of the details element
Calculate the next value, flipping the current details.open value

If we are opening

Immediately open it! The hidden overflow CSS property and the max-height, will prevent the content from leaking.
Calculate the height of the hidden content, and add it to the initial height
Set this as the max-height of the details element, this triggers the transition

Else, if we are closing

set the max-height to the initial value
create a timeout with duration equal to the duration of the transition
when timeout runs its course, set the next value on the details element

const details = document.querySelector('details')

const initial = details.offsetHeight
const duration = 600
let height = 0

details.setAttribute(
    'style',
    `--duration: ${duration / 1000}s; max-height: ${initial}px;`
)

details.addEventListener('click', e => {
    e.preventDefault()

    const next = !details.open

    if (next) {
        details.open = next

        if (document.createRange) {
            let range = document.createRange()
            range.selectNodeContents(details.lastElementChild)
            if (range.getBoundingClientRect) {
                let rect = range.getBoundingClientRect()
                if (rect) {
                    height = rect.bottom - rect.top
                }
            }
        }

        details.setAttribute(
            'style',
            `--duration:${duration / 1000}s; max-height: ${initial + height}px;`
        )

    } else {
        details.setAttribute(
            'style',
            `--duration: ${duration / 1000}s; max-height: ${initial}px;`
        )
        setTimeout(() => {
            details.open = next
        }, duration)
    }
})

That's a lot of code 🤯. Let's refactor. I am not a fan of wrapping native stuff, but I'll be using this quite a bit.

function setInlineAttribute({ element, duration, maxHeight }) {
    element.setAttribute(
        'style',
        `--duration: ${duration / 1000}s; max-height: ${maxHeight}px;`
    )
}

Isolate the range bounding client rectangle bit. This one is incredibly important, because it allows us to have a precise measure of what the maximum height should be, ensuring the transitions last exactly the time we want. More on the range API.

Sadly the range API is also not supported in IE

function calculateContentHeight(element) {
    if (document.createRange) {
        let range = document.createRange()
        range.selectNodeContents(element.lastElementChild)
        if (range.getBoundingClientRect) {
            let rect = range.getBoundingClientRect()
            if (rect) {
                return rect.bottom - rect.top
            }
        }
    }
    return 0
}

A function to collect initial values, set styles and attach the click event listener.

function animateDetailsElement(element, duration = 600) {
    const initial = element.offsetHeight
    let height = 0

    setInlineAttribute({ element, duration, maxHeight: initial })

    element.addEventListener('click', e => {
        e.preventDefault()

        const next = !element.open

        if (next) {
            element.open = next
            height = calculateContentHeight(element)
            setInlineAttribute({ element, duration, maxHeight: initial + height })

        } else {
            setInlineAttribute({ element, duration, maxHeight: initial })
            setTimeout(() => {
                element.open = next
            }, duration)
        }
    })
}

const details = document.querySelector('details')
animateDetailsElement(details)

Why do we calculate the content height and apply it as an in-line style, containing max-height and duration CSS variable?

One of the easiest techniques to create expand/collapse, is to transition the max-height, but in this article on auto-dimensions author Brandon Smith, points out two disadvantages of it.

The obvious disadvantage is that we still have to hard-code a maximum height for the element, even if we don’t have to hard-code the height itself. The second, less obvious downside, is that the transition length will not actually be what you specify unless the content height works out to be exactly the same as max-height. - Brandon Smith

The approach taken here, has a few advantages.

Manages open/close state, through the details element
Helps you to calculate the maximum height needed for your content
Because you calculate the exact maximum height, the duration of the transition will be what you specify

And the downside that it requires JavaScript.

In this implementation I've also put effort into having the duration be declared in the JavaScript side, and then transmitted to the CSS using an in-line CSS variable. That's ugly, but it works.

Refactoring further to reduce the scope of the height variable, and have a means to remove the event listener.

function animateDetailsElement(element, duration = 600) {
    let initial = element.offsetHeight

    setInlineAttribute({ element, duration, maxHeight: initial })

    function handler(e) {
        e.preventDefault()

        const next = !element.open

        if (next) {
            element.open = next
            let height = initial + calculateContentHeight(element)
            setInlineAttribute({ element, duration, maxHeight: height })

        } else {
            setInlineAttribute({ element, duration, maxHeight: initial })
            setTimeout(() => {
                element.open = next
            }, duration)
        }
    }

    element.addEventListener('click', handler);

    return () => element.removeEventListener('click', handler);
}

const details = document.querySelectorAll("details");
details.forEach(el => animateDetailsElement(el)) 
// .forEach(animateDetailsElement) would cause the duration to equal the index of el

We've accomplished a re-usable expand/collapse effect.

The details element fires a toggle event once the its value changes. Since this will fire when the element.open = next assignment happens, you could do further things, knowing the animation has finished.

Perhaps you don't like the triangle shown, the summary element can further be styled, though support is a little patchy.

details > summary {
    list-style: none;
}
/* Chrome fix */
details > summary::-webkit-details-marker {
  display: none;
}

What do you think?

Sometimes JavaScript is necessary to create a smoother experience, but it shouldn't prevent the experience from happening if JavaScript is blocked by the user.

In this case, if the user deactivated JavaScript, we'd still have the expand/collapse functionality, though content would just pop into existence.

Happy Hacking!

Use more HTML Elements - Floating Form Field Label

Joseph — Wed, 03 Jun 2020 14:36:07 +0000

I read this article, which motivated to build the floating form field using two seemingly forgotten HTML elements:

Expectation

Implementation

The MDN page for the legend already shows it doing the floating label trick, at least at the final frame, in combination with a fieldset element.

<fieldset>
  <input type="text" id="my-input" placeholder="my input"/>
  <legend>
    <label for="my-input">my input</label>
  </legend>
</fieldset>

What we want to do is:

Translate the legend to align with the input::placeholder.
When the input::placeholder is not shown, translate the legend up.

Consider:

You can translate the label all the way up, above the input, for this example I align it with the top-border of the input field.
You can also remove the padding added to the left on the legend, or translate it on the X axis when the placeholder is gone.

If you are going to implement this in an application it is better to use proper class names to avoid extremely specific selectors, here I just style the HTML elements.

First style the fieldset element:

Declare a CSS var named --typography-size, set to 14px.
Declare a CSS var named --base-ratio, set to 4px.
Set font-family to monospace.
Set padding to 0
Set border to none.

The margin in this case is optional, and set for the demo only.

fieldset {
  --typography-size: 14px;
  --base-ratio: 4px;
  font-family: monospace;
  padding: 0;
  border: none;
  margin: 16px;
}

Second, the input element.

Set the font-size to the --typography-size variable.
The input field does not inherit to the root element font-family by default, so do so.
Declare a border of 1px with solid style line, and color #c3c3c3.
Set margin to 0.
Set padding to 0.
To create spacing between the top border and actual input text, defined padding-top, in this case, 3 times the --base-ratio.
Similarly create space at the bottom, in this case, 2 times the --base-ratio.
Last but not least, space the text content from the left setting padding-left to 3 times the --base-ratio.

input {
  font-size: var(--typography-size);
  font-family: inherit;
  border: 1px solid #c3c3c3;
  margin: 0;
  padding: 0;
  padding-top: calc(var(--base-ratio) * 3);
  padding-bottom: calc(var(--base-ratio) * 2);
  padding-left: calc(var(--base-ratio) * 3);
}

It is very important to realize that for the legend, the input text is actually 13px from the left. That is because the border has 1px width. And in general:

3 * var(--base-ratio) + 1px

You could set the input::placeholder to opacity:0 (in the Codepen above it is done like that) but if you want to gracefully hide it when the input gets focused/unfocused do this:

input::placeholder {
  opacity: 1;
  transition: opacity 0.75s ease;
}

input:focus::placeholder {
  opacity: 0;
  transition: opacity 0.75s ease;
}

Third the legend element:

Match the font-size, using the --typography-size variable.
To align the legend with the input::placeholder text we need to account for 13px or rather 3 times the --base-ratio and 1px for the border of the input field.
- We break down this into padding: 0 var(--base-ratio) which implicitly sets the padding-left to 4px
- The other 9px are set using the margin-left property to 2 * var(--base-ratio) + 1px
- The combination of padding and margin is done to create 4px of white space around the x-axis of the legend.
transform the legend element in the y-axis by 100% + 3 * var(--base-ratio) + 1px. Because the input element has padding-top set to 3 * var(--base-ratio), and the 1px because of the top border in the input element.
Set the background to transparent color
Make sure all changes have transition

legend {
  font-size: var(--typography-size);
  padding: 0 var(--base-ratio);
  margin-left: calc(2 * var(--base-ratio) + 1px);
  transform: translateY(calc(100% + 3 * var(--base-ratio) + 1px));
  background: transparent;
  transition: all 0.75s ease;
}

When the input::placeholder is not being shown, the user is typing, select the legend element and change its color to hotpink, background to white, and transform to 50% in the y-axis, translateY(50%). Adjust these values to your desire.

This is the floating label effect.

Optionally, we can set the padding:0, this sets the padding-left:0 implicitly, and the legend will float to the top left corner of the input field.

input:not(:placeholder-shown) ~ legend  {
  color: hotpink;
  background: white;
  transform: translateY(50%);
  /* optional */
  /* padding: 0; */ 
}

And finally for the label.

Set the cursor to what one would normally get on a placeholder, that is text cursor.
Set the font-size to the --typography--size variable.
As a bonus,
- Allow font-size transition
- When the input::placeholder is not shown, select the label and decrease the font-size

label {
  cursor: text;
  font-size: var(--typography-size);
  transition: font-size 0.75s ease;
}

input:not(:placeholder-shown) ~ legend > label  {
 font-size: calc(var(--typography) * 0.9);
}

Hopefully I have shown you that HTML elements can already do a lot, the main part of this implementation lies on translating the legend element from its natural position to align with the input::placeholder, the rest are minor tweaks!

There's some more refactoring that could be done at the fieldset level, for example, calculate 3 * var(--base-ratio) as yet another CSS variable.

Happy hacking!

React: Slow Suspense

Joseph — Mon, 06 Apr 2020 17:10:20 +0000

There are several ways to deal with loading states, and in fact the React team came up with a solution called Suspense.

When you use Suspense directly, the fallback will show even if the fetching process is quick. And it will also disappear as soon as the fetching process is done. This would make up for a jarring UI, we can do better.

At the time of writing, there's a great package, developed by the Zeit team, called swr, which supports suspenseful data fetching.

This gist, shows a fairly simple pattern, SlowSuspense.

SlowSuspense renders its children with a Suspense boundary, when the Suspense Boundary uses the suspense-fallback, a first timer is started, if timeout occurs, then the slow-fallback is rendered.

Once the suspense settles, the suspense-fallback is unmounted, and a second timer is started, when timeout occurs, the slow-fallback is unmounted.

Should the suspense settle quickly, then we clear out all timers and prevent the slow-fallback from being rendered at all.

This CodeSandBox, has a beefed up demonstration.

Keeping track of a promise, and manage a piece of state, depending on whether or not the promise has settled, can make up for a very complicated implementation. On top of that, having to account for quick loading, or delays on the activation of the loading state, can quickly become unmanageable.

In this example, Suspense helps us remove the promise management completely, and we re-purpose the fallback props, to help us provide friendlier user experience.

Happy hacking!

isNil - nullish coalescing ??

Joseph — Wed, 01 Apr 2020 13:50:27 +0000

We have all been there. You need to check if something is null or undefined, but because false-like, falsy, values are a thing in JavaScript, 0, '', and false are also captured in your checks. You become frustrated, and, may end up writing a helper like this:

const exists = val => val !== null && val !== undefined
const isNil = val => val == null // actual lodash implementation

In the first case, you have to be verbose, and you check if something is not null, nor, undefined.

In the second, well, there's just something strange about using loose equality in modern JavaScript (wouldn't blame you if you didn't notice), and here you actually check, if something is null or undefined.

Of course, both can be re-written:

const isNil = val => val === null || val === undefined
const exists = val => val != null

Nowadays, the ?? nullish coalescing operator has been introduced, and it sits currently at stage-4, and is available in Chromium already. This operator checks for null and undefined in one go.

const str = (null || undefined) ?? 'default value'; // 'default value'
const num = 10 ?? 100 // 10

Using this new operator you could write isNil and exists like this:

const isNil = val => val !== (val ?? !val);
const exists = val => val === (val ?? !val);

There's nothing inherently better, about either of these approaches. Other than perhaps, ~~showing off~~ expanding your JavaScript knowledge.

I think the latter looks cleaner, maybe because it removes the need to explicitly write null, or undefined. Maybe because it uses flashy new language features?

One additional consideration, which I personally like, is that NaN, is also deemed to not exist, because NaN cannot be equal to itself.

Anyway, what do you think?