Riddler Express

The riddle:

From James Anderson comes a palindromic puzzle of calendars:

This past Sunday was Groundhog Day. Also, there was a football game. But to top it all off, the date, 02/02/2020, was palindromic, meaning it reads the same forwards and backwards (if you ignore the slashes).

If we write out dates in the American format of MM/DD/YYYY (i.e., the two digits of the month, followed by the two digits of the day, followed by the four digits of the year), how many more palindromic dates will there be this century?

– Zach Wissner-Gross, “How Many More Palindrome Dates Will You See,” FiveThirtyEight

My approach:

I took a simple brute-force approach. Within a dataframe and using a little code from R’s tidyverse I…

1. created a column¹ containing each date from now until the end of the century
2. created another column that contains the reverse of this
3. filtered to only rows where the columns equal the same value
4. counted the number of rows

Which shows there will be eight more pallindromic dates in the century – one in each decade remaining.

Riddler Classic

The riddle:

Also on Super Bowl Sunday, math professor Jim Propp made a rather interesting observation:

I told my kid (who’d asked about absolute value signs) “They’re just like parentheses so there’s never any ambiguity,” but then I realized that things are more complicated; for instance |-1|-2|-3| could be 5 or -5. Has anyone encountered ambiguities like this in the wild?

— James Propp (@JimPropp) February 3, 2020

At first glance, this might look like one of those annoying memes about order of operations that goes viral every few years — but it’s not.

When you write lengthy mathematical expressions using parentheses, it’s always clear which “open” parenthesis corresponds to which “close” parenthesis. For example, in the expression (1+2(3−4)+5), the closing parenthesis after the 4 pairs with the opening parenthesis before the 3, and not with the opening parenthesis before the 1.

But pairings of other mathematical symbols can be more ambiguous. Take the absolute value symbols in Jim’s example, which are vertical bars, regardless of whether they mark the opening or closing of the absolute value. As Jim points out, |−1|−2|−3| has two possible interpretations:

The two left bars are a pair and the two right bars are a pair. In this case, we have 1−2·3 = 1−6 = −5. The two outer bars are a pair and the two inner bars are a pair. In this case, we have |−1·2−3| = |−2−3| = |−5| = 5. Of course, if we gave each pair of bars a different height (as is done in mathematical typesetting), this wouldn’t be an issue. But for the purposes of this problem, assume the bars are indistinguishable.

How many different values can the expression |−1|−2|−3|−4|−5|−6|−7|−8|−9| have?

– Zach Wissner-Gross, “How Many More Palindrome Dates Will You See,” FiveThirtyEight

My approach:

The question is how many ways can you interpret the expression above. As hinted at by the author, the ambiguity in the expression becomes resolved based on where the parentheses are placed. Hence the question is how many different ways can we arrange the parentheses?

Potential parentheses placements

Constraints on placing parentheses:

• Parentheses form pairs, hence there must be an equal numbers of left-closed and right-closed parentheses, i.e. ) and (
• We need to avoid adding meaningless parentheses (that don’t lessen ambiguity). Hence like those on the left of this expression should not count as placing a parentheses:

|(-1)|(-2)|(-3)| \(\Leftrightarrow\) |-1|-2|-3|

Hence, we will say…

• A bar can only have a single parentheses placed next to it (either a right or left closed)
• Right-closed will be placed to the left of a bar and left closed to the right of a bar, i.e. |) and (|
• We can ignore the left and right most bars and say that a left-closed parenthese has to go on the left, and a right closed parentheses on the right, hence we can start the problem like “(|-1|-2|-3|)”

With these rules we can tackle the first part of the problem and think of each interior bar as representing a place-holder, the collection of which must be filled by an equal number of ) and ( .

(|−1 _ −2 _ −3 _ −4 _ −5 _ −6 _ −7 _ −8 _−9|)

This can be represented as a combinatorics² problem that can be represented by \(6 \choose 3\).

We could use the combn() function in R to generate all these combinations.

However, there is a problem; some of the combinations created could result in configurations with open parentheses. For example, even on a shorter version of this problem, the rules above would not safeguard from configurations such as:

that go against the rules of parentheses.

You might take one of these approaches:

• plug all combinations into a calculator and throw-out those that return an error
• define additional rules about the configuration of parentheses that will filter out those configurations, like the one above, that would break (more effort)

I ended-up doing it both ways (was a good way to verify my work). See Define more rules in the Appendix if you want to see how you might take the latter approach. For now, I’ll go the easy route and start computing our expressions.

One thing I needed to do was make it so our mathematical expressions, i.e.:

Could be represented as meaningful expressions within the R programming language, i.e.:

I made an equation create_solve_expr_df() that creates the expressions and computes the solutions. See the raw Rmd file on my github to see my code³.

After creating all possible configurations, I need to actually compute each viable expression to check if any of the configurations resulted in duplicate solutions.

Number of different configurations of parentheses:

solution_9 %>% 
  nrow()

## [1] 70

There are 42 individual configurations. However we need to check if all of the evaluated solutions are unique.

solution_9 %>% 
  distinct(evaluated) %>% 
  nrow()

## [1] 69

Given these particular inputs, there are only 39 unique solutions, meaning that three configurations of parentheses led to duplicate solutions.

Appendix

set.seed(123)
solution_rand9 <- create_solve_expr_df(-runif(9))

solution_rand9 %>% 
  nrow()

## [1] 70

## [1] 70

## # A tibble: 1 x 1
##   num_possible_combinations
##                       <int>
## 1                        70

library(gganimate)

set.seed(1234)
p <- solution_9 %>% 
  mutate(comb_index = row_number()) %>% 
  sample_n(42) %>% 
  select(comb_index, equation) %>% 
  ggplot()+
  coord_cartesian(xlim = c(-.050, 0.050), ylim = c(-0.1, 0.1))+
  geom_text(aes(x = 0, y = 0, label = equation), size = 6)+
  ggforce::theme_no_axes()+
  theme(legend.position = "none", panel.border = element_blank())

p + transition_states(comb_index)
gganimate::anim_save(here::here("static/post/2020-02-13-fivethirtyeightriddlersolutions-palindrome-debts-and-ambiguous-absolut-value-signs_files/solutions.gif"))