Topic Modeling

The video that accompanies this notebook is available at https://ucdavis.box.com/v/sts-205-notebook-7.

Topic modeling is a way to imagine the shared vocabularies (topics) underlying the documents in the corpus. Running a topic model is quite easy. The hard parts are preparing your text, choosing model parameters and hyperparameters, and interpreting the model.

Topic modeling should be reserved for large corpora (more documents than unique words). Long documents should be chunked into smaller documents, as topic modeling treats a document as a bag of words. If two words are in the same document, the model doesn’t care if they are right next to each other or very far apart. Therefore, working with short documents or short segments of longer documents will ensure that the words the model associates with one another actually occur near one another in the original documents.

Start by loading packages, sourcing functions, and building the sotu data frame.

library(tidyverse)
Registered S3 methods overwritten by 'dbplyr':
  method         from
  print.tbl_lazy     
  print.tbl_sql      
── Attaching packages ─────────────────────────────────────── tidyverse 1.3.0 ──
✓ ggplot2 3.3.3     ✓ purrr   0.3.4
✓ tibble  3.0.6     ✓ dplyr   1.0.4
✓ tidyr   1.1.2     ✓ stringr 1.4.0
✓ readr   1.4.0     ✓ forcats 0.5.0
── Conflicts ────────────────────────────────────────── tidyverse_conflicts() ──
x dplyr::filter() masks stats::filter()
x dplyr::lag()    masks stats::lag()
library(tidytext)
#install.packages("textstem")
library(textstem)
Loading required package: koRpus.lang.en
Loading required package: koRpus
Loading required package: sylly
Registered S3 method overwritten by 'data.table':
  method           from
  print.data.table     
For information on available language packages for 'koRpus', run

  available.koRpus.lang()

and see ?install.koRpus.lang()


Attaching package: ‘koRpus’

The following object is masked from ‘package:readr’:

    tokenize
#install.packages("topicmodels")
library(topicmodels)
source("functions.r")
sotu <- make_sotu()

── Column specification ────────────────────────────────────────────────────────
cols(
  year = col_double(),
  pres = col_character(),
  use_last = col_logical()
)
To prepare the text, we will chunk it up into paragraphs, using the "

" tags. What we want is a data frame where each row is one paragraph of one SOTU address. We will create a unique identifier for each paragraph.

sotu_paragraphs <- data.frame()
for(i in 1:nrow(sotu)) {
  text <- str_split(sotu$text[i], " <p> ") %>% unlist
  paragraphs <- tibble(text) %>% 
                mutate(id = str_c(str_replace_all(sotu$pres[i], " ", "_"), 
                            "_", sotu$year[i], "_", 1:length(text)))
  sotu_paragraphs <- rbind(sotu_paragraphs, paragraphs)
}
head(sotu_paragraphs)

Next we will unnest tokens and remove stopwords and tokens containing digits.

sotu_words <- sotu_paragraphs %>% unnest_tokens(word, text) %>%
                anti_join(stop_words) %>% filter(!str_detect(word, "[:digit:]"))
Joining, by = "word"
head(sotu_words)

Next we will lemmatize the text. Lemmatization converts all forms of a word to the most basic form. For example, “children” becomes “child” and “men” becomes “man.” Lemmatization is not necessary for topic modeling, and you can also use it for other types of text analysis, including types we have discussed in class. I am introducing it here mainly so that you are aware of it and know how to do it.

The first step is to create a data frame with a column of all unique words in the corpus.

sotu_lemmas <- tibble(word = unique(sotu_words$word))
head(sotu_lemmas)

Now we will use the lemmatize_words function in the textstem package to create a new column of lemmas. The lemmatize_words function takes as its argument the vector of words you want to lemmatize and returns the lemma for each one.

sotu_lemmas$lemma <- lemmatize_words(sotu_lemmas$word)
head(sotu_lemmas)

Now we will join our list of lemmas to the sotu_words data frame

sotu_words <- left_join(sotu_words, sotu_lemmas) 
Joining, by = "word"
head(sotu_words)

We will use the topicmodels package for topic modeling. It requires that our corpus be in a document-term matrix, so we use the cast_dtm() function from the tidytext package to convert our token data frame into a document-term matrix.

sotu_dtm <- sotu_words %>% group_by(id) %>% count(lemma) %>% cast_dtm(id, lemma, n)

Now we can use the LDA() function in the topicmodels package to build a topic model. For our first attempt, we will ask for 15 topics. This process takes a lot of computational time. To save you that time, I have already run the model and saved it as sotu_lda_15.RDS. Read it into working memory with the code below.

 sotu_lda <- LDA(sotu_dtm, k = 15)
 saveRDS(sotu_lda, "sotu_lda_15.RDS")
sotu_lda_15 <- readRDS("sotu_lda_15.RDS")
sotu_lda_15
A LDA_VEM topic model with 15 topics.

The following code creates two data frames of results: sotu_topics indicates the probability distribution of words over topics; sotu_docs indicates the proportion of each document (paragraph) attributed to each topic.

sotu_topics <- tidy(sotu_lda_15, matrix = "beta")
head(sotu_topics)
sotu_topics %>% group_by(topic) %>% summarize(total = sum(beta))
sotu_docs <- tidy(sotu_lda_15, matrix = "gamma") 
head(sotu_docs)
sotu_docs %>% group_by(document) %>% summarize(total = sum(gamma))

One way to visualize topics is with bar charts of the five most frequent words in each topic.

topics_5 <- function(lda) {
  tidy(lda, matrix = "beta") %>% 
        group_by(topic) %>% top_n(5, beta) %>%
        ggplot(aes(x = reorder(term, beta), y = beta, fill = term)) + 
          geom_col() + coord_flip() + guides(fill = FALSE) +
          facet_wrap(vars(topic), ncol = 5, scales = "free") +
          theme_minimal(base_size = 20) +
          scale_y_continuous(labels = c()) +
          labs(title = "Topic Model - Top Five Words By Topic", 
               x = "Top Five Words", y = "Beta")
}
topics_5(sotu_lda_15)

One way to visualize the distribution of topics over documents is to calculate the proportion of each document attributed to each topic. Here I am aggregating over years.

topics_years <- function(lda) {
  tidy(lda, matrix = "gamma") %>%
    mutate(year = str_replace(document, "_[0-9]+$", "")) %>% 
    mutate(year = str_replace(year, "[A-Za-z_\\.]+_", "")) %>%
    mutate(year = as.numeric(year)) %>% 
    group_by(year, topic) %>% summarize(paras = sum(gamma)) %>%
    ungroup %>% group_by(year) %>% mutate(p = paras/sum(paras)) %>%
    ggplot(aes(x = year, y = p, fill = factor(topic))) + geom_area() +
      scale_y_continuous(labels = scales::percent) +
      labs(title = "Topic Distribution by Year - SOTU Topic Model",
           x = "Year", y = "Percent of Address (by paragraph)", fill = "Topic")
}
topics_years(sotu_lda_15)
`summarise()` has grouped output by 'year'. You can override using the `.groups` argument.

This graph indicates that the model very evenly distributed the topics among documents. We can see that by exploring the gamma column of the sotu_docs data frame.

summary(sotu_docs$gamma)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
0.03843 0.06624 0.06661 0.06667 0.06699 0.38449 
qplot(gamma, data = sotu_docs, binwidth = 0.00001)

This distribution is controlled by the alpha hyperparameter. We can see what value of alpha was used with the following code:

attr(sotu_lda_15, "alpha")
[1] 32.93211

This is very high! Let’s try a smaller alpha.

sotu_lda <- LDA(sotu_dtm, k = 15, control = list(alpha = 1))
saveRDS(sotu_lda, "sotu_lda_15_a1.RDS")

sotu_lda_15a1 <- readRDS("sotu_lda_15_a1.RDS")
topics_5(sotu_lda_15a1)

topics_years(sotu_lda_15a1)
`summarise()` has grouped output by 'year'. You can override using the `.groups` argument.

Now we are seeing some variation and change over time! We are still in the early stages of building this model, but one way we can evaluate and think with it is by looking at the words in each document that were assigned to each topic. The augment() function shows the frequency of each word in each document, and the topic to which it was assigned by the model.

We can now see what proportion of each presidents’ words was assigned to which topic.

We have not yet explored different values of the k parameter, which specifies the number of topics. One package that can help with that is ldatuning. This package allows you to try a variety of topic numbers, and generates four metrics that indicate fit.

It looks like more topics is better, so let’s try it with 50.

LS0tCnRpdGxlOiAiTm90ZWJvb2sgNyAtIFRvcGljIE1vZGVsaW5nIFBhcnQgMSIKYXV0aG9yOiAiRW1pbHkgS2xhbmNoZXIgTWVyY2hhbnQiCmRhdGU6ICJTVFMgMjA1IgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgojIFRvcGljIE1vZGVsaW5nClRoZSB2aWRlbyB0aGF0IGFjY29tcGFuaWVzIHRoaXMgbm90ZWJvb2sgaXMgYXZhaWxhYmxlIGF0IGh0dHBzOi8vdWNkYXZpcy5ib3guY29tL3Yvc3RzLTIwNS1ub3RlYm9vay03LgoKVG9waWMgbW9kZWxpbmcgaXMgYSB3YXkgdG8gaW1hZ2luZSB0aGUgc2hhcmVkIHZvY2FidWxhcmllcyAodG9waWNzKSB1bmRlcmx5aW5nIHRoZSBkb2N1bWVudHMgaW4gdGhlIGNvcnB1cy4gUnVubmluZyBhIHRvcGljIG1vZGVsIGlzIHF1aXRlIGVhc3kuIFRoZSBoYXJkIHBhcnRzIGFyZSBwcmVwYXJpbmcgeW91ciB0ZXh0LCBjaG9vc2luZyBtb2RlbCBwYXJhbWV0ZXJzIGFuZCBoeXBlcnBhcmFtZXRlcnMsIGFuZCBpbnRlcnByZXRpbmcgdGhlIG1vZGVsLgoKVG9waWMgbW9kZWxpbmcgc2hvdWxkIGJlIHJlc2VydmVkIGZvciBsYXJnZSBjb3Jwb3JhIChtb3JlIGRvY3VtZW50cyB0aGFuIHVuaXF1ZSB3b3JkcykuIExvbmcgZG9jdW1lbnRzIHNob3VsZCBiZSAqY2h1bmtlZCogaW50byBzbWFsbGVyIGRvY3VtZW50cywgYXMgdG9waWMgbW9kZWxpbmcgdHJlYXRzIGEgZG9jdW1lbnQgYXMgYSAqYmFnIG9mIHdvcmRzKi4gSWYgdHdvIHdvcmRzIGFyZSBpbiB0aGUgc2FtZSBkb2N1bWVudCwgdGhlIG1vZGVsIGRvZXNuJ3QgY2FyZSBpZiB0aGV5IGFyZSByaWdodCBuZXh0IHRvIGVhY2ggb3RoZXIgb3IgdmVyeSBmYXIgYXBhcnQuIFRoZXJlZm9yZSwgd29ya2luZyB3aXRoIHNob3J0IGRvY3VtZW50cyBvciBzaG9ydCBzZWdtZW50cyBvZiBsb25nZXIgZG9jdW1lbnRzIHdpbGwgZW5zdXJlIHRoYXQgdGhlIHdvcmRzIHRoZSBtb2RlbCBhc3NvY2lhdGVzIHdpdGggb25lIGFub3RoZXIgYWN0dWFsbHkgb2NjdXIgbmVhciBvbmUgYW5vdGhlciBpbiB0aGUgb3JpZ2luYWwgZG9jdW1lbnRzLgoKU3RhcnQgYnkgbG9hZGluZyBwYWNrYWdlcywgc291cmNpbmcgZnVuY3Rpb25zLCBhbmQgYnVpbGRpbmcgdGhlIGBzb3R1YCBkYXRhIGZyYW1lLgpgYGB7cn0KbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkodGlkeXRleHQpCiNpbnN0YWxsLnBhY2thZ2VzKCJ0ZXh0c3RlbSIpCmxpYnJhcnkodGV4dHN0ZW0pCiNpbnN0YWxsLnBhY2thZ2VzKCJ0b3BpY21vZGVscyIpCmxpYnJhcnkodG9waWNtb2RlbHMpCnNvdXJjZSgiZnVuY3Rpb25zLnIiKQpzb3R1IDwtIG1ha2Vfc290dSgpCmBgYApUbyBwcmVwYXJlIHRoZSB0ZXh0LCB3ZSB3aWxsIGNodW5rIGl0IHVwIGludG8gcGFyYWdyYXBocywgdXNpbmcgdGhlICI8cD4iIHRhZ3MuIFdoYXQgd2Ugd2FudCBpcyBhIGRhdGEgZnJhbWUgd2hlcmUgZWFjaCByb3cgaXMgb25lIHBhcmFncmFwaCBvZiBvbmUgU09UVSBhZGRyZXNzLiBXZSB3aWxsIGNyZWF0ZSBhIHVuaXF1ZSBpZGVudGlmaWVyIGZvciBlYWNoIHBhcmFncmFwaC4KYGBge3J9CnNvdHVfcGFyYWdyYXBocyA8LSBkYXRhLmZyYW1lKCkKZm9yKGkgaW4gMTpucm93KHNvdHUpKSB7CiAgdGV4dCA8LSBzdHJfc3BsaXQoc290dSR0ZXh0W2ldLCAiIDxwPiAiKSAlPiUgdW5saXN0CiAgcGFyYWdyYXBocyA8LSB0aWJibGUodGV4dCkgJT4lIAogICAgICAgICAgICAgICAgbXV0YXRlKGlkID0gc3RyX2Moc3RyX3JlcGxhY2VfYWxsKHNvdHUkcHJlc1tpXSwgIiAiLCAiXyIpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICJfIiwgc290dSR5ZWFyW2ldLCAiXyIsIDE6bGVuZ3RoKHRleHQpKSkKICBzb3R1X3BhcmFncmFwaHMgPC0gcmJpbmQoc290dV9wYXJhZ3JhcGhzLCBwYXJhZ3JhcGhzKQp9CmhlYWQoc290dV9wYXJhZ3JhcGhzKQpgYGAKTmV4dCB3ZSB3aWxsIHVubmVzdCB0b2tlbnMgYW5kIHJlbW92ZSBzdG9wd29yZHMgYW5kIHRva2VucyBjb250YWluaW5nIGRpZ2l0cy4KYGBge3J9CnNvdHVfd29yZHMgPC0gc290dV9wYXJhZ3JhcGhzICU+JSB1bm5lc3RfdG9rZW5zKHdvcmQsIHRleHQpICU+JQogICAgICAgICAgICAgICAgYW50aV9qb2luKHN0b3Bfd29yZHMpICU+JSBmaWx0ZXIoIXN0cl9kZXRlY3Qod29yZCwgIls6ZGlnaXQ6XSIpKQpoZWFkKHNvdHVfd29yZHMpCmBgYApOZXh0IHdlIHdpbGwgbGVtbWF0aXplIHRoZSB0ZXh0LiBMZW1tYXRpemF0aW9uIGNvbnZlcnRzIGFsbCBmb3JtcyBvZiBhIHdvcmQgdG8gdGhlIG1vc3QgYmFzaWMgZm9ybS4gRm9yIGV4YW1wbGUsICJjaGlsZHJlbiIgYmVjb21lcyAiY2hpbGQiIGFuZCAibWVuIiBiZWNvbWVzICJtYW4uIiBMZW1tYXRpemF0aW9uIGlzIG5vdCBuZWNlc3NhcnkgZm9yIHRvcGljIG1vZGVsaW5nLCBhbmQgeW91IGNhbiBhbHNvIHVzZSBpdCBmb3Igb3RoZXIgdHlwZXMgb2YgdGV4dCBhbmFseXNpcywgaW5jbHVkaW5nIHR5cGVzIHdlIGhhdmUgZGlzY3Vzc2VkIGluIGNsYXNzLiBJIGFtIGludHJvZHVjaW5nIGl0IGhlcmUgbWFpbmx5IHNvIHRoYXQgeW91IGFyZSBhd2FyZSBvZiBpdCBhbmQga25vdyBob3cgdG8gZG8gaXQuCgpUaGUgZmlyc3Qgc3RlcCBpcyB0byBjcmVhdGUgYSBkYXRhIGZyYW1lIHdpdGggYSBjb2x1bW4gb2YgYWxsIHVuaXF1ZSB3b3JkcyBpbiB0aGUgY29ycHVzLgpgYGB7cn0Kc290dV9sZW1tYXMgPC0gdGliYmxlKHdvcmQgPSB1bmlxdWUoc290dV93b3JkcyR3b3JkKSkKaGVhZChzb3R1X2xlbW1hcykKYGBgCk5vdyB3ZSB3aWxsIHVzZSB0aGUgYGxlbW1hdGl6ZV93b3Jkc2AgZnVuY3Rpb24gaW4gdGhlIGB0ZXh0c3RlbWAgcGFja2FnZSB0byBjcmVhdGUgYSBuZXcgY29sdW1uIG9mIGxlbW1hcy4gVGhlIGBsZW1tYXRpemVfd29yZHNgIGZ1bmN0aW9uIHRha2VzIGFzIGl0cyBhcmd1bWVudCB0aGUgdmVjdG9yIG9mIHdvcmRzIHlvdSB3YW50IHRvIGxlbW1hdGl6ZSBhbmQgcmV0dXJucyB0aGUgbGVtbWEgZm9yIGVhY2ggb25lLgpgYGB7cn0Kc290dV9sZW1tYXMkbGVtbWEgPC0gbGVtbWF0aXplX3dvcmRzKHNvdHVfbGVtbWFzJHdvcmQpCmhlYWQoc290dV9sZW1tYXMpCmBgYApOb3cgd2Ugd2lsbCBqb2luIG91ciBsaXN0IG9mIGxlbW1hcyB0byB0aGUgYHNvdHVfd29yZHNgIGRhdGEgZnJhbWUKYGBge3J9CnNvdHVfd29yZHMgPC0gbGVmdF9qb2luKHNvdHVfd29yZHMsIHNvdHVfbGVtbWFzKSAKaGVhZChzb3R1X3dvcmRzKQpgYGAKV2Ugd2lsbCB1c2UgdGhlIGB0b3BpY21vZGVsc2AgcGFja2FnZSBmb3IgdG9waWMgbW9kZWxpbmcuIEl0IHJlcXVpcmVzIHRoYXQgb3VyIGNvcnB1cyBiZSBpbiBhIGRvY3VtZW50LXRlcm0gbWF0cml4LCBzbyB3ZSB1c2UgdGhlIGBjYXN0X2R0bSgpYCBmdW5jdGlvbiBmcm9tIHRoZSBgdGlkeXRleHRgIHBhY2thZ2UgdG8gY29udmVydCBvdXIgdG9rZW4gZGF0YSBmcmFtZSBpbnRvIGEgZG9jdW1lbnQtdGVybSBtYXRyaXguCmBgYHtyfQpzb3R1X2R0bSA8LSBzb3R1X3dvcmRzICU+JSBncm91cF9ieShpZCkgJT4lIGNvdW50KGxlbW1hKSAlPiUgY2FzdF9kdG0oaWQsIGxlbW1hLCBuKQpgYGAKTm93IHdlIGNhbiB1c2UgdGhlIGBMREEoKWAgZnVuY3Rpb24gaW4gdGhlIGB0b3BpY21vZGVsc2AgcGFja2FnZSB0byBidWlsZCBhIHRvcGljIG1vZGVsLiBGb3Igb3VyIGZpcnN0IGF0dGVtcHQsIHdlIHdpbGwgYXNrIGZvciAxNSB0b3BpY3MuIFRoaXMgcHJvY2VzcyB0YWtlcyBhIGxvdCBvZiBjb21wdXRhdGlvbmFsIHRpbWUuIFRvIHNhdmUgeW91IHRoYXQgdGltZSwgSSBoYXZlIGFscmVhZHkgcnVuIHRoZSBtb2RlbCBhbmQgc2F2ZWQgaXQgYXMgYHNvdHVfbGRhXzE1LlJEU2AuIFJlYWQgaXQgaW50byB3b3JraW5nIG1lbW9yeSB3aXRoIHRoZSBjb2RlIGJlbG93LgpgYGB7cn0KIyBzb3R1X2xkYSA8LSBMREEoc290dV9kdG0sIGsgPSAxNSkKIyBzYXZlUkRTKHNvdHVfbGRhLCAic290dV9sZGFfMTUuUkRTIikKc290dV9sZGFfMTUgPC0gcmVhZFJEUygic290dV9sZGFfMTUuUkRTIikKc290dV9sZGFfMTUKYGBgClRoZSBmb2xsb3dpbmcgY29kZSBjcmVhdGVzIHR3byBkYXRhIGZyYW1lcyBvZiByZXN1bHRzOiBgc290dV90b3BpY3NgIGluZGljYXRlcyB0aGUgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG9mIHdvcmRzIG92ZXIgdG9waWNzOyBgc290dV9kb2NzYCBpbmRpY2F0ZXMgdGhlIHByb3BvcnRpb24gb2YgZWFjaCBkb2N1bWVudCAocGFyYWdyYXBoKSBhdHRyaWJ1dGVkIHRvIGVhY2ggdG9waWMuCmBgYHtyfQpzb3R1X3RvcGljcyA8LSB0aWR5KHNvdHVfbGRhXzE1LCBtYXRyaXggPSAiYmV0YSIpCmhlYWQoc290dV90b3BpY3MpCnNvdHVfdG9waWNzICU+JSBncm91cF9ieSh0b3BpYykgJT4lIHN1bW1hcml6ZSh0b3RhbCA9IHN1bShiZXRhKSkKc290dV9kb2NzIDwtIHRpZHkoc290dV9sZGFfMTUsIG1hdHJpeCA9ICJnYW1tYSIpIApoZWFkKHNvdHVfZG9jcykKc290dV9kb2NzICU+JSBncm91cF9ieShkb2N1bWVudCkgJT4lIHN1bW1hcml6ZSh0b3RhbCA9IHN1bShnYW1tYSkpCmBgYAoKT25lIHdheSB0byB2aXN1YWxpemUgdG9waWNzIGlzIHdpdGggYmFyIGNoYXJ0cyBvZiB0aGUgZml2ZSBtb3N0IGZyZXF1ZW50IHdvcmRzIGluIGVhY2ggdG9waWMuCmBgYHtyIGZpZy5oZWlnaHQgPSAxMH0KdG9waWNzXzUgPC0gZnVuY3Rpb24obGRhKSB7CiAgdGlkeShsZGEsIG1hdHJpeCA9ICJiZXRhIikgJT4lIAogICAgICAgIGdyb3VwX2J5KHRvcGljKSAlPiUgdG9wX24oNSwgYmV0YSkgJT4lCiAgICAgICAgZ2dwbG90KGFlcyh4ID0gcmVvcmRlcih0ZXJtLCBiZXRhKSwgeSA9IGJldGEsIGZpbGwgPSB0ZXJtKSkgKyAKICAgICAgICAgIGdlb21fY29sKCkgKyBjb29yZF9mbGlwKCkgKyBndWlkZXMoZmlsbCA9IEZBTFNFKSArCiAgICAgICAgICBmYWNldF93cmFwKHZhcnModG9waWMpLCBuY29sID0gNSwgc2NhbGVzID0gImZyZWUiKSArCiAgICAgICAgICB0aGVtZV9taW5pbWFsKGJhc2Vfc2l6ZSA9IDIwKSArCiAgICAgICAgICBzY2FsZV95X2NvbnRpbnVvdXMobGFiZWxzID0gYygpKSArCiAgICAgICAgICBsYWJzKHRpdGxlID0gIlRvcGljIE1vZGVsIC0gVG9wIEZpdmUgV29yZHMgQnkgVG9waWMiLCAKICAgICAgICAgICAgICAgeCA9ICJUb3AgRml2ZSBXb3JkcyIsIHkgPSAiQmV0YSIpCn0KdG9waWNzXzUoc290dV9sZGFfMTUpCmBgYApPbmUgd2F5IHRvIHZpc3VhbGl6ZSB0aGUgZGlzdHJpYnV0aW9uIG9mIHRvcGljcyBvdmVyIGRvY3VtZW50cyBpcyB0byBjYWxjdWxhdGUgdGhlIHByb3BvcnRpb24gb2YgZWFjaCBkb2N1bWVudCBhdHRyaWJ1dGVkIHRvIGVhY2ggdG9waWMuIEhlcmUgSSBhbSBhZ2dyZWdhdGluZyBvdmVyIHllYXJzLgpgYGB7cn0KdG9waWNzX3llYXJzIDwtIGZ1bmN0aW9uKGxkYSkgewogIHRpZHkobGRhLCBtYXRyaXggPSAiZ2FtbWEiKSAlPiUKICAgIG11dGF0ZSh5ZWFyID0gc3RyX3JlcGxhY2UoZG9jdW1lbnQsICJfWzAtOV0rJCIsICIiKSkgJT4lIAogICAgbXV0YXRlKHllYXIgPSBzdHJfcmVwbGFjZSh5ZWFyLCAiW0EtWmEtel9cXC5dK18iLCAiIikpICU+JQogICAgbXV0YXRlKHllYXIgPSBhcy5udW1lcmljKHllYXIpKSAlPiUgCiAgICBncm91cF9ieSh5ZWFyLCB0b3BpYykgJT4lIHN1bW1hcml6ZShwYXJhcyA9IHN1bShnYW1tYSkpICU+JQogICAgdW5ncm91cCAlPiUgZ3JvdXBfYnkoeWVhcikgJT4lIG11dGF0ZShwID0gcGFyYXMvc3VtKHBhcmFzKSkgJT4lCiAgICBnZ3Bsb3QoYWVzKHggPSB5ZWFyLCB5ID0gcCwgZmlsbCA9IGZhY3Rvcih0b3BpYykpKSArIGdlb21fYXJlYSgpICsKICAgICAgc2NhbGVfeV9jb250aW51b3VzKGxhYmVscyA9IHNjYWxlczo6cGVyY2VudCkgKwogICAgICBsYWJzKHRpdGxlID0gIlRvcGljIERpc3RyaWJ1dGlvbiBieSBZZWFyIC0gU09UVSBUb3BpYyBNb2RlbCIsCiAgICAgICAgICAgeCA9ICJZZWFyIiwgeSA9ICJQZXJjZW50IG9mIEFkZHJlc3MgKGJ5IHBhcmFncmFwaCkiLCBmaWxsID0gIlRvcGljIikKfQp0b3BpY3NfeWVhcnMoc290dV9sZGFfMTUpCmBgYApUaGlzIGdyYXBoIGluZGljYXRlcyB0aGF0IHRoZSBtb2RlbCB2ZXJ5IGV2ZW5seSBkaXN0cmlidXRlZCB0aGUgdG9waWNzIGFtb25nIGRvY3VtZW50cy4gV2UgY2FuIHNlZSB0aGF0IGJ5IGV4cGxvcmluZyB0aGUgYGdhbW1hYCBjb2x1bW4gb2YgdGhlIGBzb3R1X2RvY3NgIGRhdGEgZnJhbWUuCmBgYHtyfQpzdW1tYXJ5KHNvdHVfZG9jcyRnYW1tYSkKcXBsb3QoZ2FtbWEsIGRhdGEgPSBzb3R1X2RvY3MsIGJpbndpZHRoID0gMC4wMDAwMSkKYGBgClRoaXMgZGlzdHJpYnV0aW9uIGlzIGNvbnRyb2xsZWQgYnkgdGhlIGFscGhhICoqaHlwZXJwYXJhbWV0ZXIqKi4gV2UgY2FuIHNlZSB3aGF0IHZhbHVlIG9mIGFscGhhIHdhcyB1c2VkIHdpdGggdGhlIGZvbGxvd2luZyBjb2RlOgpgYGB7cn0KYXR0cihzb3R1X2xkYV8xNSwgImFscGhhIikKYGBgClRoaXMgaXMgdmVyeSBoaWdoISBMZXQncyB0cnkgYSBzbWFsbGVyIGFscGhhLgpgYGB7ciBmaWcuaGVpZ2h0ID0gMTB9CiMgc290dV9sZGEgPC0gTERBKHNvdHVfZHRtLCBrID0gMTUsIGNvbnRyb2wgPSBsaXN0KGFscGhhID0gMSkpCiMgc2F2ZVJEUyhzb3R1X2xkYSwgInNvdHVfbGRhXzE1X2ExLlJEUyIpCgpzb3R1X2xkYV8xNWExIDwtIHJlYWRSRFMoInNvdHVfbGRhXzE1X2ExLlJEUyIpCnRvcGljc181KHNvdHVfbGRhXzE1YTEpCnRvcGljc195ZWFycyhzb3R1X2xkYV8xNWExKQpgYGAKTm93IHdlIGFyZSBzZWVpbmcgc29tZSB2YXJpYXRpb24gYW5kIGNoYW5nZSBvdmVyIHRpbWUhIFdlIGFyZSBzdGlsbCBpbiB0aGUgZWFybHkgc3RhZ2VzIG9mIGJ1aWxkaW5nIHRoaXMgbW9kZWwsIGJ1dCBvbmUgd2F5IHdlIGNhbiBldmFsdWF0ZSBhbmQgdGhpbmsgd2l0aCBpdCBpcyBieSBsb29raW5nIGF0IHRoZSB3b3JkcyBpbiBlYWNoIGRvY3VtZW50IHRoYXQgd2VyZSBhc3NpZ25lZCB0byBlYWNoIHRvcGljLiBUaGUgYGF1Z21lbnQoKWAgZnVuY3Rpb24gc2hvd3MgdGhlIGZyZXF1ZW5jeSBvZiBlYWNoIHdvcmQgaW4gZWFjaCBkb2N1bWVudCwgYW5kIHRoZSB0b3BpYyB0byB3aGljaCBpdCB3YXMgYXNzaWduZWQgYnkgdGhlIG1vZGVsLgpgYGB7cn0Kc290dV9hc3NpZ25tZW50cyA8LSBhdWdtZW50KHNvdHVfbGRhXzE1YTEsIGRhdGEgPSBzb3R1X2R0bSkKaGVhZChzb3R1X2Fzc2lnbm1lbnRzKQp0YWlsKHNvdHVfYXNzaWdubWVudHMpCmBgYApXZSBjYW4gbm93IHNlZSB3aGF0IHByb3BvcnRpb24gb2YgZWFjaCBwcmVzaWRlbnRzJyB3b3JkcyB3YXMgYXNzaWduZWQgdG8gd2hpY2ggdG9waWMuIApgYGB7cn0KaG1hcCA8LSBmdW5jdGlvbihsZGEsIGR0bSwgdCkgewogIHByZXNfd29yZHMgPC0gYXVnbWVudChsZGEsIGRhdGEgPSBkdG0pICU+JSAKICAgICAgICAgICAgICAgICAgbXV0YXRlKHByZXMgPSBzdHJfcmVwbGFjZV9hbGwoZG9jdW1lbnQsICJbXzAtOVxcLl0rJCIsICIiKSkgJT4lIAogICAgICAgICAgICAgICAgICBtdXRhdGUocHJlcyA9IHN0cl9yZXBsYWNlX2FsbChwcmVzLCAiXyIsICIgIikpICU+JQogICAgICAgICAgICAgICAgICBtdXRhdGUocHJlcyA9IGZjdF9yZWxldmVsKGZhY3RvcihwcmVzKSwgdW5pcXVlKHNvdHUkcHJlcykpKSAlPiUKICAgICAgICAgICAgICAgICAgZ3JvdXBfYnkocHJlcywgLnRvcGljKSAlPiUgCiAgICAgICAgICAgICAgICAgIHN1bW1hcml6ZShuID0gc3VtKGNvdW50KSkgJT4lIHVuZ3JvdXAgJT4lCiAgICAgICAgICAgICAgICAgIGdyb3VwX2J5KHByZXMpICU+JSBtdXRhdGUocCA9IG4vc3VtKG4pKQogIHRfd29yZHMgPC0gdGlkeShsZGEsIG1hdHJpeCA9ICJiZXRhIikgJT4lIAogICAgICAgICAgICAgIGFycmFuZ2UodG9waWMsIC1iZXRhKSAlPiUKICAgICAgICAgICAgICBncm91cF9ieSh0b3BpYykgJT4lIHRvcF9uKDUsIGJldGEpICU+JSAKICAgICAgICAgICAgICBzdW1tYXJpemUod29yZHMgPSBwYXN0ZSh0ZXJtLCBjb2xsYXBzZSA9ICIgIikpCiAgbGVmdF9qb2luKHByZXNfd29yZHMsIHRfd29yZHMsIGJ5ID0gYygiLnRvcGljIiA9ICJ0b3BpYyIpKSAlPiUKICAgIGdncGxvdChhZXMoeCA9IHByZXMsIHkgPSB3b3JkcywgZmlsbCA9IHApKSArIGdlb21fdGlsZSgpICsKICAgICAgc2NhbGVfZmlsbF9ncmFkaWVudChsb3cgPSAid2hpdGUiLCBoaWdoID0gInN0ZWVsYmx1ZSIpICsKICAgICAgdGhlbWVfbWluaW1hbCgpICsgCiAgICAgIHNjYWxlX3hfZGlzY3JldGUoZXhwYW5kID0gYygwLCAwKSkgKwogICAgICBzY2FsZV95X2Rpc2NyZXRlKGV4cGFuZCA9IGMoMCwgMCkpICsKICAgICAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiLCBheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDI3MCwgaGp1c3QgPSAwKSkgKwogICAgICBsYWJzKHRpdGxlID0gcGFzdGUwKCJTdGF0ZSBvZiB0aGUgVW5pb24gQWRkcmVzc2VzIGJ5IFByZXNpZGVudCwgIiwgdCwgIi1Ub3BpYyBNb2RlbCIpLCAKICAgICAgICAgIHggPSAiUHJlc2lkZW50IiwgeSA9ICJUb3BpYyIpCn0KcG5nKCJobWFwXzE1X3RvcGljcy5wbmciLCBoZWlnaHQgPSA1LCB3aWR0aCA9IDE1LCB1bml0cyA9ICJpbiIsIHJlcyA9IDEwMCkKICBobWFwKHNvdHVfbGRhXzE1YTEsIHNvdHVfZHRtLCAxNSkKZGV2Lm9mZigpCmBgYAoKCgpXZSBoYXZlIG5vdCB5ZXQgZXhwbG9yZWQgZGlmZmVyZW50IHZhbHVlcyBvZiB0aGUgayBwYXJhbWV0ZXIsIHdoaWNoIHNwZWNpZmllcyB0aGUgbnVtYmVyIG9mIHRvcGljcy4gT25lIHBhY2thZ2UgdGhhdCBjYW4gaGVscCB3aXRoIHRoYXQgaXMgYGxkYXR1bmluZ2AuIFRoaXMgcGFja2FnZSBhbGxvd3MgeW91IHRvIHRyeSBhIHZhcmlldHkgb2YgdG9waWMgbnVtYmVycywgYW5kIGdlbmVyYXRlcyBmb3VyIG1ldHJpY3MgdGhhdCBpbmRpY2F0ZSBmaXQuCmBgYHtyfQpsaWJyYXJ5KGxkYXR1bmluZykKY29udHJvbF9saXN0IDwtIGxpc3QoYWxwaGEgPSAxKQogIHRvcGljX251bWJlciA8LSBGaW5kVG9waWNzTnVtYmVyKHNvdHVfZHRtLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdG9waWNzID0gYyhzZXEoZnJvbSA9IDEwLCB0byA9IDIwLCBieSA9IDEpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzZXEoMjAsIDMwLCAyKSwgc2VxKDMwLCA1MCwgNSkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtZXRyaWNzID0gYygiR3JpZmZpdGhzMjAwNCIsICJDYW9KdWFuMjAwOSIsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiQXJ1bjIwMTAiLCAiRGV2ZWF1ZDIwMTQiKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWV0aG9kID0gIkdpYmJzIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udHJvbCA9IGNvbnRyb2xfbGlzdCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWMuY29yZXMgPSA0TCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVyYm9zZSA9IFRSVUUpCnNhdmVSRFModG9waWNfbnVtYmVyLCAidG9waWNfbnVtYmVyLlJEUyIpCnRvcGljX251bWJlciA8LSByZWFkUkRTKCJ0b3BpY19udW1iZXIuUkRTIikKRmluZFRvcGljc051bWJlcl9wbG90KHRvcGljX251bWJlcikKYGBgCkl0IGxvb2tzIGxpa2UgbW9yZSB0b3BpY3MgaXMgYmV0dGVyLCBzbyBsZXQncyB0cnkgaXQgd2l0aCA1MC4KYGBge3J9CnNvdHVfbGRhXzUwYTEgPC0gTERBKHNvdHVfZHRtLCBrID0gNTAsIGNvbnRyb2wgPSBsaXN0KGFscGhhID0gMSkpCnNhdmVSRFMoc290dV9sZGFfNTBhMSwgInNvdHVfbGRhXzUwX2ExLlJEUyIpCmBgYAo=