User:Hakerh400/Code golf challenges

Given that User:Hakerh400 will never create an account on the PPCG website (due to disagreement with the StackExchange's privacy policy and terms of service), he decided to write all challenge ideas here. If someone has a PPCG account and finds some of these ideas interesting, feel free to post on the PPCG website. All challenges that are published here are in the public domain.

Browsing articles

Difficulty: Easy

Overview

You are reading some articles on a website on the internet. Each article on that website is on a separate page. Pages are numbered starting from $1$. The article on the page with number $1$ is the last article that is published. The article on the page with number $2$ is the previous article, and so on. However, when a new article is published, all previous articles get shifted by a page (so the last published article will be on page $1$, the article which was on page $1$ will be moved to page $2$, and so on).

On each page there is a button next which goes to the next page. If you opened page $n$, and while you are reading the article from that page another article is published, when you click next, you will navigate to the $n+1$ th page, but it will contain the same article that you have just read. If two articles were published, you would see the article that was $n-1$ th while you was reading the $n$th article.

You start from the first article (the article on the first page, we call it $\Omega$). After you read it, you click next. The second page will be opened. You have no idea how many articles are published in the meantime, so you may be reading the article that is chronologically published before $\Omega$, or after $\Omega$, or it could even be the same article (in that case you would know that exactly one article is published in the meantime). After you read the article from the second page, you again click next and you go to the third page. Again, any number of articles may be published in the meantime, and so on. The last article that you read is $\mathrm {A}$. The only thing you know is that $\Omega$ is not chronologically published before $\mathrm {A}$ (so either $\Omega$ is $\mathrm {A}$, or $\Omega$ is published after $\mathrm {A}$).

Goal

Your task is to determine how many articles there are between $\mathrm {A}$ and $\Omega$ (including them).

Input

The input contains the array of the titles of all articles that you have read so far (each article has a unique title). The first article from the array corresponds to $\Omega$ and the last article corresponds to $\mathrm {A}$.

Output

The output is the number of all articles that are published after $\mathrm {A}$, but before $\Omega$ (plus $2$ because we count $\mathrm {A}$ and $\Omega$ too, or plus $1$ if $\mathrm {A} =\Omega$).

Examples

Input: A
Output: 1

Input: A A
Output: 1

Input: A B
Output: 2

Input: A A A A B C A D
Output: 2

Input: A B C D E F G A H A H I J K
Output: 5

Input: A B C C C D A A B E E A B B C B C C B C D F F D C C D F G
Output: 6

Input: A A B C C C A B C C D D E F E D G H A A B C I I J B C C C I J I J J K L L
Output: 7

Input: A B A B B C D D D B C D A A E A E A A A A A B B B E F G H F G E F I J K I I H H F H K I I I H F F G E A B C A A B B C C D D A B B G E A B B B B E G E G K L L L L M M N O L L L L J K K I H F F G E E E A B C D
Output: 4

Input: A B B C A D A B A A A D E E F G F G H H I E I I E E J I H I E J K L K K K L L E J K K K E F G H I E J K E I I E J K L M M L G N O N O P N Q Q R S T U T T U Q Q U U R S T T V W X X W V W Y Z Z Y Y Y Z Z Y Z AA Y AA AB AB AC AD AE AD AB AF AG AH AE AH AE AD AD AB AC AB AD AB AB AC AC AB AC AC AI AA AA AA Y Y Z Y Z AJ AJ AJ AK AK AK AL V W X R S T U U Q AM P AM P N N O N O F O F G G F G H H F P AM P P AM S R X R R S T T T U Q Q AM P N O F F G H I E E J H I E J J K L M AN D A B B A B C D A AN AN D AN AN AN AN AN D AN M AN E G N O F F P AM U Q X R V AJ Y AC AI AA Y Y Z AJ Z Z AJ AJ AK AK AL AK AL V V V W V V W W V V Z Z Z AC AC AI AD AE AG AO AP AP AF AF AF AO AP AQ AO AR AR AS AR AT AT AU AR AT AU AU AU AR AS AV AW AX AX AQ AO AP AX AQ AO AO AO AP AF AP AF AP AQ AX AW AW AX AQ AQ AO AP AF AP AF AG AP AF AP AO AO AP AP AF AF AP AF AG AG AO AQ AW AX AW AR AS AV AY AZ BA AY BB AT AU AR AU AR AT AT AU AR AS AR AS AV AW AW AW AW AV AS AS AV AV AR AR AS AV AR AS AS AV AW AS AV AS AS AV AS AV AW AW AV AW AW AX AX AW AX AX AW AW AX AQ AQ AX AQ AW AX AV AW AX AQ AO AQ AO AO AP AP AF AF AF AF AF AG AH AE AF AP AF AG AP AF AG AH AG AH AG AH AE AF AG AH AF AF AO AO AP AF AG AF AG AH AH AE AG AH AE AD AD AB AE AD AE AH AG AF AO AP AF AP AO AO AW AV AT AT AU AR AR AR AS AU AU AU BA AZ AZ BA BA AY BB AT AT AT AU AR AR AR BA AY AY BB BB AT BB AT AT AU BC BD BD BE BF BG BH BF BG BH BH BF BE BH BI BI BJ BK BL BL BL BJ BI BM BJ BI BM BG BG BH BF BF BE BN BC BD BC BD BO BC BC BN BN BC BC BD BD BD BC BD BO AZ BA AY AY AZ BA BA AY AY AZ BA AY BB BB AT AU AR AS AS AV AS AV AV AW AW AW AX AQ AW AW AS AS AV AV AV AS AV AS AV AW AX AQ AO AP AF AP AP AP AF AG AG AH AH AH AO AO AP AP AX AQ AO AQ AQ AO AX AX AQ AO AP AO AP AF AP AF AP AF AF AG AH AE AD AE AE AE AD AB AC AE AD AD AD AD AB AC AD AH AE AF AG AG AF AG AF AG AG AF AG AH AH AE AE AD AD AG AG AU AT AT AU AR AT AZ AZ AZ BA AY BB AT AY BB BB BB AT AU BB AT AU AR AR AU BB AT AU AU AR AR AS AV AW AX AX AV AW AX AQ AW AW AW AR AR AR AR AU AR AR AS AR AS AV AS AV AV AV AW AW AX AW AX AQ AO AP AQ AO AP AF AG AH AH AP AF AG AH AH AF AG AW AV AW AX AQ AO AQ AO AS AR AS AS AS AY AY AY BB AT AY AY AY BB BD BD BD BN BC BD BO AZ BA AY AZ BA AY BB AT AT BA BA AY BB AT AU BB AT AT AY BA AY BA AY BB AY BB AT AT AT AT AU AR AS BB BB AY BB BB BB BB AT AU AU AU AU AT AT AT AY AY BB AT AT AT AT AU AR AS AU AU AR AS AR AS AS AV AW AW AX AW AX AX AR AS AR AS AS AV AW AW AX AX AX AX AQ AO AP AP AQ AO AO AO AP AF AF AG AG AW AV AW AX AS AS AS AT AU BB AT AU AU AR AS AV AW AW AX AS AR AS AV AV AW AX AX AX AQ AO AX AQ AO AQ AS AV AW AX AQ AX AS AS AV AW AS AV AV AW AX AX AS AV AW AW AX AQ AQ AO AQ AV AS AS AV AV AR AS AV AW AX AQ AV AR AU AR AS AV AV AS AV AW AW AX AW AX AQ AO AO AO AQ AO AO AX AX AQ AX AX AQ AQ AQ AO AW AX AX AT AU AR AS AV AW AX AQ AO AP AF AG AH AE AD AB AC AI AA Y Z AJ AK AL V W X R S T U Q AM P N O F G H I E J K L M AN D A B C BP
Output: 4

Reference implementation

Try it online!

Scoring

This is code-golf, so the shortest answer in bytes wins.

Dictionary

Difficulty: Easy

Overview

A dictionary is defined by an array of key-value pairs. Both keys and values are words consisting of lowercase english letters. Each line in a dictionary contains two words separated by a space (the left one is key and the right on is value). Same key can appear multiple times and in that case the last value for that key is the actual value. Example of a dictionary:

abc xy
defgh pqrst
asdf fd
abc z

As we can see, abc is redefined, so it has value z, because it is the last value that is defined for that key. However, it is important to keep track of two things for each key:

• The first time when the key is added to the dictionary
• The last time when a key is updated

Updating with the same value also counts as updating.

Based on the above metrics, we define two lists of keys for each dictionary (both contain the same number of keys):

• keys1 - The list of keys sorted by the ascending time when the key is added to the dictionary for the first time
• keys2 - The list of keys sorted by the ascending time when the key is last updated

In the example above, keys1 is [abc, defgh, asdf] and keys2 is [defgh, asdf, abc].

Reduced dictionary

We display a dictionary in the reduced form by first listing all key-value pairs ordered by keys1 and then we list keys2 in a new line (keys separated by spaces). The reduced dictionary from the example above would be:

abc z
defgh pqrst
asdf fd
defgh asdf abc

The first three lines represent key-value pairs (abc is redefined to be z instead of xy) and the last line contains keys2.

Product of two dictionaries

The syntax $P[k]$ represents the value of key $k$ from dictionary $P$.

For two dictionaries $A$ and $B$, we define their product $C=A\times B$ in the following way:

• $C$ is initially empty
• All keys that are in $A$, but not in $B$, we add them to $B$ and for each such key in $B$ we set the value to be the key itself
• All values that are in $A$, but not as keys in $B$, we add them as keys to $B$ and for each such key in $B$ we set the value to be the key itself
• For each element keys of [A.keys1, A.keys2] (in that order)

• For each key $K_{1}$ of keys

• Let $K_{2}=B[K_{1}]$
• Let $S=\left\{x\mid B[x]=K_{2}\right\}$
• Let $K_{3}$ be the last element of A.keys2 that is in $S$
• Set $C[K_{2}]=B\left[A[K_{3}]\right]$

Goal

Your task is to calculate the product of two given dictionaries and output it in the reduced form. Bonus points if you can solve it in $O(n\log n)$ time complexity.

Input

Two reduced dictionaries $A$ and $B$. Use any input format you like.

Output

Reduced dictionary $A\times B$. Use any output format you like.

Examples

=== Example 1 ===

Input:
  p P
  x A
  q Q
  y B
  r R
  q y r x p

  x y
  x

Output:
  p P
  y A
  q Q
  r R
  q r y p

=== Example 2 ===

Input:
  p P
  x A
  q Q
  y B
  r R
  q y r x p

  y x
  y

Output:
  p P
  x A
  q Q
  r R
  q r x p

=== Example 3 ===

Input:
  p P
  x A
  q Q
  y B
  r R
  q y r x p

  x y
  y x
  A B
  B C
  x y A B

Output:
  p P
  y B
  q Q
  x C
  r R
  q x r y p

Reference implementation

Try it online!

Scoring

This is code-golf, so the shortest answer in bytes wins.