From b1ad567e8bc2da532244a60fe2136fe1d49d21b3 Mon Sep 17 00:00:00 2001 From: Hisiste Date: Sun, 23 Apr 2023 19:14:31 -0600 Subject: Merge of post Double or One Thing. This is about tags and using math. --- _posts/2023-04-19-double-or-one-thing.md | 93 +++++++++++++++++++------------- 1 file changed, 57 insertions(+), 36 deletions(-) diff --git a/_posts/2023-04-19-double-or-one-thing.md b/_posts/2023-04-19-double-or-one-thing.md index c97d444..40f5359 100644 --- a/_posts/2023-04-19-double-or-one-thing.md +++ b/_posts/2023-04-19-double-or-one-thing.md @@ -2,6 +2,7 @@ title: Double or One Thing categories: [Technical Logs, Individual] tags: [python] +math: true --- > This page is still in WIP. A lot of information is missing or not reviewed. @@ -13,7 +14,13 @@ Try this problem by yourself first! Check the [Code Jam Page](https://codingcomp ## Overview -> A HIGH LEVEL SUMMARY THAT EVERY ENGINEER SHOULD UNDERSTAND AND CAN NAVIGATE THROUGH YOUR PROBLEM-SOLVING PROCESS. +We have a string of uppercase English characters. We can double or not every +character of the string. If we had the set of all possible results and sort them +alphabetically, which string would come first? + +Our only control over the string is doubling or not every character. Sorting +alphabetically means comparing letters and choosing the one that appears before +in the alphabet. We would...
O     O     O
@@ -25,10 +32,10 @@ Try this problem by yourself first! Check the [Code Jam Page](https://codingcomp Let's summarize the problem. Take a string of uppercase English characters. We can highlight any of its letters, possibly all or none of them. Every highlighted letter will be duplicated, every non-highlighted letter will stay as is. We'll give an example with all of its highlighting possibilities. -| RIDE -> RIDE | RIDE -> RIDDE | RIDE -> RIDEE | RIDE -> RIDDEE | -| RIDE -> RRIDE | RIDE -> RRIDDE | RIDE -> RRIDEE | RIDE -> RRIDDEE | -| RIDE -> RIIDE | RIDE -> RIIDDE | RIDE -> RIIDEE | RIDE -> RIIDDEE | -| RIDE -> RRIIDE | RIDE -> RRIIDDE | RIDE -> RRIIDEE | RIDE -> RRIIDDEE | +| RIDE $\rightarrow$ RIDE | RIDE $\rightarrow$ RIDDE | RIDE $\rightarrow$ RIDEE | RIDE $\rightarrow$ RIDDEE | +| RIDE $\rightarrow$ RRIDE | RIDE $\rightarrow$ RRIDDE | RIDE $\rightarrow$ RRIDEE | RIDE $\rightarrow$ RRIDDEE | +| RIDE $\rightarrow$ RIIDE | RIDE $\rightarrow$ RIIDDE | RIDE $\rightarrow$ RIIDEE | RIDE $\rightarrow$ RIIDDEE | +| RIDE $\rightarrow$ RRIIDE | RIDE $\rightarrow$ RRIIDDE | RIDE $\rightarrow$ RRIIDEE | RIDE $\rightarrow$ RRIIDDEE | Now, with all of our results, we must sort alphabetically all of them. We would obtain the following result: @@ -46,7 +53,7 @@ Let's compare two words: *book* and *boat*. Alphabetically, which one comes firs 1. Compare each letter from left to right. Find the first ones that differ. | **B** ook - **B** oat | *b* **O** ok - *b* **O** at | *bo* **O** k - *bo* **A** t | - | They're the same. (**b**) | They're the same. (**o**) | They differ. (**o** =/= **a**) | + | They're the same. (**b**) | They're the same. (**o**) | They differ. (**o** $\neq$ **a**) | 1. The letter that differs decides which word comes first. @@ -57,7 +64,7 @@ Let's compare two words: *book* and *boat*. Alphabetically, which one comes firs 1. What if one word is a subset of the other? The smallest word will come first, then. | **C** an - **C** annot | *c* **A** n - *c* **A** nnot | *ca* **N** - *ca* **N** not | *can* - *can* **N** ot | - | Same letter. (**c**) | Same letter. (**a**) | Same letter. (**n**) | Differ. (**_** =/= **n**) | + | Same letter. (**c**) | Same letter. (**a**) | Same letter. (**n**) | Differ. (**_** $\neq$ **n**) | | Can < Cannot | |:-:| @@ -85,30 +92,30 @@ We illustrate two examples following the procedure. #### RIDE -1. **R**IDE -> The *R* comes after the *I*. Hence, we won't highlight the *R*. -1. R**I**DE -> The *I* comes after the *D*. Therefore, we won't highlight the *I*. -1. RI**D**E -> The *D* comes before the *E*. Now we will highlight the *D*. -1. RID**E** -> We won't highlight the *E* because it is the last letter. +1. **R**IDE $\rightarrow$ The *R* comes after the *I*. Hence, we won't highlight the *R*. +1. R**I**DE $\rightarrow$ The *I* comes after the *D*. Therefore, we won't highlight the *I*. +1. RI**D**E $\rightarrow$ The *D* comes before the *E*. Now we will highlight the *D*. +1. RID**E** $\rightarrow$ We won't highlight the *E* because it is the last letter. The resulting string is RIDE. Just as we saw in the [context section](#context), this is the desired output. #### FEEELING -1. **F**EEELING -> *F* > *E*. Therefore, *F* is not highlighted. -1. F**E**EELING -> *E* = *E*. We'll keep walking. -1. F**E**EELING -> *E* = *E*. Keep on walkiiiing. -1. F**E**EELING -> *E* < *L*. Hence, we'll highlight all *E*'s. -1. FEEE**L**ING -> *L* > *I*. We won't highlight the *L*. -1. FEEEL**I**NG -> *I* < *N*. The *I* must be highlighted. -1. FEEELI**N**G -> *N* > *G*. You better not touch the *N*. Don't highlight it! -1. FEEELIN**G** -> *G* > *_*. Last letter must never be highlighted. >:( +1. **F**EEELING $\rightarrow$ *F* > *E*. Therefore, *F* is not highlighted. +1. F**E**EELING $\rightarrow$ *E* = *E*. We'll keep walking. +1. F**E**EELING $\rightarrow$ *E* = *E*. Keep on walkiiiing. +1. F**E**EELING $\rightarrow$ *E* < *L*. Hence, we'll highlight all *E*'s. +1. FEEE**L**ING $\rightarrow$ *L* > *I*. We won't highlight the *L*. +1. FEEEL**I**NG $\rightarrow$ *I* < *N*. The *I* must be highlighted. +1. FEEELI**N**G $\rightarrow$ *N* > *G*. You better not touch the *N*. Don't highlight it! +1. FEEELIN**G** $\rightarrow$ *G* > *_*. Last letter must never be highlighted. >:( Therefore, the solution is FEEELING. Is this the right solution? Lets use the brute force way! This means: listing all highlighting possibilities and sorting them. We obtain: -| 1. FEEELING -> FEEEEEELIING | 5. FEEELING -> FEEEEEELING | ... | 253. FEEELING -> FFEEELLING | -| 2. FEEELING -> FEEEEEELIINGG | 6. FEEELING -> FEEEEEELINGG | ... | 254. FEEELING -> FFEEELLINGG | -| 3. FEEELING -> FEEEEEELIINNG | 7. FEEELING -> FEEEEEELINNG | ... | 255. FEEELING -> FFEEELLINNG | -| 4. FEEELING -> FEEEEEELIINNGG | 8. FEEELING -> FEEEEEELINNGG | ... | 256. FEEELING -> FFEEELLINNGG | +| 1. FEEELING $\rightarrow$ FEEEEEELIING | 5. FEEELING $\rightarrow$ FEEEEEELING | ... | 253. FEEELING $\rightarrow$ FFEEELLING | +| 2. FEEELING $\rightarrow$ FEEEEEELIINGG | 6. FEEELING $\rightarrow$ FEEEEEELINGG | ... | 254. FEEELING $\rightarrow$ FFEEELLINGG | +| 3. FEEELING $\rightarrow$ FEEEEEELIINNG | 7. FEEELING $\rightarrow$ FEEEEEELINNG | ... | 255. FEEELING $\rightarrow$ FFEEELLINNG | +| 4. FEEELING $\rightarrow$ FEEEEEELIINNGG | 8. FEEELING $\rightarrow$ FEEEEEELINNGG | ... | 256. FEEELING $\rightarrow$ FFEEELLINNGG |
Source: Trust me, bro.
@@ -124,37 +131,37 @@ In the procedure we walk through each character of the string. For each one we d
RIDE
-| Highlighting? | After doubling | Sorting alphabetically | Which one won? | +| Highlighting? | After doubling | Comparing | Which one won? | |:-|:-|:-|:-| -| Highlighted | RIDE -> RRIDE | R **R** IDE | Comes second. | -| Not highlighted | RIDE -> RIDE | R **I** DE | Comes **FIRST**! | +| Highlighted | RIDE $\rightarrow$ RRIDE | R **R** IDE | Comes second. | +| Not highlighted | RIDE $\rightarrow$ RIDE | R **I** DE | Comes **FIRST**! | Because *R* comes after *I*, *RRIDE* comes after *RIDE*. We better **NOT** highlight the *R*.
RIDE
-| Highlighting? | After doubling | Sorting alphabetically | Which one won? | +| Highlighting? | After doubling | Comparing | Which one won? | |:-|:-|:-|:-| -| Highlighted | RIDE -> RIIDE | RI **I** DE | Comes second. | -| Not highlighted | RIDE -> RIDE | RI **D** E | Comes **FIRST**! | +| Highlighted | RIDE $\rightarrow$ RIIDE | RI **I** DE | Comes second. | +| Not highlighted | RIDE $\rightarrow$ RIDE | RI **D** E | Comes **FIRST**! | Because *I* comes after *D*, *RIIDE* comes after *RIDE*. We better **NOT** highlight the *I*.
RIDE
-| Highlighting? | After doubling | Sorting alphabetically | Which one won? | +| Highlighting? | After doubling | Comparing | Which one won? | |:-|:-|:-|:-| -| Highlighted | RIDE -> RIDDE | RID **D** E | Comes **FIRST**! | -| Not highlighted | RIDE -> RIDE | RID **E** | Comes second. | +| Highlighted | RIDE $\rightarrow$ RIDDE | RID **D** E | Comes **FIRST**! | +| Not highlighted | RIDE $\rightarrow$ RIDE | RID **E** | Comes second. | Because *D* comes before *E*, *RIDDE* comes before *RIDE*. We **MUST** highlight the *D*.
RIDE
-| Highlighting? | After doubling | Sorting alphabetically | Which one won? | +| Highlighting? | After doubling | Comparing | Which one won? | |:-|:-|:-|:-| -| Highlighted | RIDE -> RIDEE | RIDE **E** | Comes second. | -| Not highlighted | RIDE -> RIDE | RIDE | Comes **FIRST**! | +| Highlighted | RIDE $\rightarrow$ RIDEE | RIDE **E** | Comes second. | +| Not highlighted | RIDE $\rightarrow$ RIDE | RIDE | Comes **FIRST**! | Because *RIDE* is a subset of *RIDEE*, *RIDEE* comes after *RIDE*. We better **NOT** highlight the *E*. @@ -196,4 +203,18 @@ def first_alphabetically(my_str: str) -> str: ## Alternative Solutions -> WHAT ELSE DID YOU CONSIDER WHEN COMING UP WITH THE SOLUTION ABOVE? PROS AND CONS? +Only one alternative solution came to my mind: **brute force**. As explained at +the beginning of the [solution section](#solution), it consists on: +1. Generating all possible highlightings. +1. Sorting the results. +1. Retrieving the first one that appeared. + +Although the biggest pro in this solution is its simplicity, the biggest con is +what makes this solution inviable. Each letter can be highlighted or not, +independently of the other letters. Considering a string of $n$ characters, we +have a total number of $2^n$ possible highlightings. On a set of small strings, +this wont be much of a trouble. The problem begins when we have strings of at +most 100 characters (as seen in the *Test Set 2* on Google Code Jam). That is $$ +2^{100} = 1\,267\,650\,600\,228\,229\,401\,496\,703\,205\,376 $$ possible +highlightings. AND THAT IS AN AWFUL LOT. We don't have that much memory nor +time! So this solution had to be discarted. -- cgit v1.2.3