How Many More Palindrome Dates Will You See?

The Riddler for February 7, 2020, the week of the palindromic date 02/02/2020. The Express counts the palindrome dates still to come this century; the Classic counts the distinct values hiding inside a string of ambiguous absolute-value bars.

Riddler Express

Writing dates as MM/DD/YYYY, a palindrome reads the same forwards and backwards (ignoring the slashes); $02/02/2020$ is one. How many more palindromic dates will there be this century?

The Riddler, FiveThirtyEight, February 7, 2020(original post)

Solution

The eight digits of MM/DD/YYYY are $M_1 M_2\,D_1 D_2\,Y_1 Y_2 Y_3 Y_4$, and a palindrome demands $M_1 = Y_4$, $M_2 = Y_3$, $D_1 = Y_2$, $D_2 = Y_1$. This century the year is $20Y_3Y_4$, so $Y_1 = 2$ and $Y_2 = 0$. That fixes the day immediately: $$D_1 = Y_2 = 0, \qquad D_2 = Y_1 = 2,$$ so every palindrome date this century falls on the $2$nd, and the month is the year’s last two digits reversed, $M_1M_2 = Y_4Y_3$. Running $Y_3,Y_4$ through the years and keeping only those for which $Y_4Y_3$ is a real month $01$ to $12$ gives exactly twelve palindrome dates this century: $$\begin{aligned} &01/02/2010,\ \ 10/02/2001,\ \ 11/02/2011,\ \ 02/02/2020,\\ &12/02/2021,\ \ 03/02/2030,\ \ 04/02/2040,\ \ 05/02/2050,\\ &06/02/2060,\ \ 07/02/2070,\ \ 08/02/2080,\ \ 09/02/2090. \end{aligned}$$ Four of them fall on or before $02/02/2020$ (the two in $2001$ and $2011$, the one in $2010$, and $02/02/2020$ itself). That leaves $$\boxed{8}$$ still to come: $12/02/2021$ and then one per decade from $03/02/2030$ to $09/02/2090$.

The computation

Encode the calendar directly: walk every real date from $2020$ through $2099$, write it as the eight-digit string MM DD YYYY, and count those that read the same reversed and fall after $02/02/2020$.

from datetime import date, timedelta
d, end, count = date(2020, 1, 1), date(2099, 12, 31), 0
while d <= end:
    s = f"{d.month:02d}{d.day:02d}{d.year:04d}"
    if s == s[::-1] and d > date(2020, 2, 2):
        count += 1
    d += timedelta(days=1)
print(count)              # 8

The brute-force calendar count is $8$, as boxed.

Riddler Classic

Because absolute-value bars look the same whether they open or close, an expression like $|{-}1|{-}2|{-}3|$ is ambiguous: it can mean $1 - 2\cdot 3 = -5$ or $|{-}1\cdot 2 - 3| = 5$. Treating all the bars as indistinguishable, how many different values can $$|{-}1|{-}2|{-}3|{-}4|{-}5|{-}6|{-}7|{-}8|{-}9|$$ have?

The Riddler, FiveThirtyEight, February 7, 2020(original post)

Solution

The expression has ten vertical bars. An interpretation is a way to pair them into opening and closing bars, and because no bar can close before it opens, the legal pairings are exactly the balanced arrangements of five open and five close symbols, counted by the fifth Catalan number $C_5 = 42$. Each pairing yields one arithmetic value, so there are at most $42$ values; duplicates can only lower the count.

To turn a pairing into a number, read an opening bar as “$\lvert$ (begin)” and a closing bar as “end $\rvert$.” A signed number sitting just before a group multiplies it, and a signed number sitting just after a finished group is added (it carries its own sign). The two readings of the small example confirm the rule: $\lvert{-}1\rvert + ({-}2)\cdot\lvert{-}3\rvert = 1 - 6 = -5$, and $\lvert\,({-}1)\cdot\lvert{-}2\rvert + ({-}3)\,\rvert = \lvert{-}2-3\rvert = 5$. Evaluating all $42$ pairings of the full expression, exactly three pairs of them collide (the repeated values are $-375$, $-25$ and $105$), so the $42$ readings produce only $$\boxed{39}$$ distinct values. The Catalan count $42$ is the ceiling, and these three coincidences are all that separate the answer from it.

The computation

Enumerate the $42$ balanced bar-pairings, build the expression each one defines by the open/close, multiply/add rules above, evaluate, and count the distinct results.

nums = [-(k + 1) for k in range(9)]        # signed numbers between the 10 bars

def matchings(n):                          # all balanced '('/')' bar labellings
    out = []
    def rec(i, stack, roles):
        if i == n:
            if not stack: out.append(roles[:])
            return
        roles.append('('); rec(i + 1, stack + [i], roles); roles.pop()
        if stack:
            roles.append(')'); rec(i + 1, stack[:-1], roles); roles.pop()
    rec(0, [], [])
    return out

def value(roles):
    parts, prev = [], None                 # prev kind: 'open', 'close', 'num'
    for b in range(10):
        kind = 'open' if roles[b] == '(' else 'close'
        if prev in ('num', 'close') and kind == 'open': parts.append('*')
        parts.append('abs(' if kind == 'open' else ')')
        prev = kind
        if b < 9:
            if prev == 'close': parts.append('+')   # signed number is added
            parts.append(str(nums[b])); prev = 'num'
    return eval(''.join(parts))

vals = {value(r) for r in matchings(10)}
print(len(matchings(10)), len(vals))        # 42 39

There are $42$ pairings but only $39$ distinct values, as boxed.