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.

Update: Created an account on a different website.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha} . The only thing you know is that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Omega} is not chronologically published before Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha} (so either Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Omega} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha} , or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Omega} is published after Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha} ).

Goal

Your task is to determine how many articles there are between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Omega} and the last article corresponds to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha} .

Output

The output is the number of all articles that are published after Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha} , but before Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Omega} (plus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2} because we count Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Omega} too, or plus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Alpha=\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):

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

In the example above, keys₁ is [abc, defgh, asdf] and keys₂ is [defgh, asdf, abc].

Reduced dictionary

We display a dictionary in the reduced form by first listing all key-value pairs ordered by keys₁ and then we list keys₂ 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 keys₂.

Product of two dictionaries

The syntax Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P[k]} represents the value of key Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} from dictionary Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} .

For two dictionaries Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} , we define their product Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C=A\times B} in the following way:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C} is initially empty
All keys that are in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} , but not in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} , we add them to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} and for each such key in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} we set the value to be the key itself
All values that are in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} , but not as keys in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} , we add them as keys to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} and for each such key in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} we set the value to be the key itself
For each element keys of [A.keys₁, A.keys₂] (in that order)

For each key Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_1} of keys

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_2=B[K_1]}
Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S=\left\{x\mid B[x]=K_2\right\}}
Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_3} be the last element of A.keys₂ 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.

User:Hakerh400/Code golf challenges

Contents

Browsing articles

Overview

Goal

Input

Output

Examples

Reference implementation

Scoring

Dictionary

Overview

Reduced dictionary

Product of two dictionaries

Goal

Input

Output

Examples

Reference implementation

Scoring

Navigation menu

User:Hakerh400/Code golf challenges

Browsing articles

Overview

Goal

Input

Output

Examples

Reference implementation

Scoring

Dictionary

Overview

Reduced dictionary

Product of two dictionaries

Goal

Input

Output

Examples

Reference implementation

Scoring

Navigation menu

Search