Q161155 - Excel - Pi got your number.md

PPCG Question Link

Copy of Challenge Spec

Challenge:

$\pi$ is supposed to be infinite. That means every number is contained inside the decimal part of $\pi$. Your task will be to take a positive integer on input and return the position of this number in $\pi$ digits on output.

For example, if the input is 59, we'll return 4

Here is why : we will look for the number 59 in the digits of $\pi$

3.14159265...
     ^^

The value starts at the 4th digit, so the output will be 4.

Some other examples :

input : 1      output : 1
input : 65     output : 7
input : 93993  output : 42
input : 3      output : 9

Rules :

• You don't have to handle digits that doesn't exist within the first 200 digits
• Standard loopholes are, as always, forbidden.
• This is tag:codegolf, so the fewer bytes wins.

---

Approach 0: Raw String

Because the Pi() built-in function is only accurate to the first 14 decimal places, the built-in alone cannot be used to reach the $200$ decimal-point precision needed for the challenge. Beyond this, the precision exceed that of Excel's doubles. As such $\pi$ will need to be either calculated, or encoded as a String responses.

The simplest way to do this, as shown in @Engineer Toast's response to this prompt, is to simply store the first 200 decimal places of $\pi$ in a string, and pass this into the Find() function , along with the digits to be found.

As per convention, the user specified input shall be taken from cell [A1].

=FIND(A1,"14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196")

Score: 212 Bytes

Approach 1: Append to Pi()

We can take advantage of the Pi() built-in to reduce the number of characters we need to store by $14$. In doing so, we need to adjust the formula so that we either remove or ignore the impact of the 3. that Pi() will leave as a previx.

We do this by passing 3 as the start argument to Find() and subtracting 2 from the result.

 =FIND(A1,PI()&"323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196",3)-2

Score: 207 Bytes

Approach 2: Base 36 String Compression

Since we know our output will only include base-$10$ numbers, we can try a couple of different approaches for string compression. We'll start with Base-$36$.

The key to this approach will be the Base function. Of note here is that this function has an optional Min_Length argument that can allow us to ensure each segment of the compressed string is a consistent number of characters long. This will save us having to deal with that later, so we'll take advantage of it.

We will use a let command to block out the steps of the process here. We start by assigning the numbers we want to compress as to a variable, as a string.

=LET(
pi_210_digits,"141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975",

Then we are going to take an input representing how long each segment of the number that will be read in then string compressed is fom some cell, here we use [N2].

...
sec_leng,N2,

Because are working with $\pi$ which known to a functionally arbitraty precision, and only have compress the $200$ most major decimal places, we will trim down $\pi$ so its length is the least multiple of sec_leng at or longer than 200 digits in length.

...
seq_items,200/sec_leng,
pi_digits_needed,ROUNDUP(seq_items,0)*sec_leng,
pi_digits,MID(pi_210_digits,1,pi_digits_needed),

We then define an array of integers ${1 ...n}$ where $n$ is the ceiling of sec_items.

...
seq,SEQUENCE(ROUNDUP(seq_items,0)),

We use that array to split up $\pi$ into sections, each of them sec_leng in length.

...
secs,MID(pi_digits,sec_leng*(seq-1)+1,sec_leng),

We then convert all of the sections to our base - here Base-$36$ - then check to see what the length longest output string is.

...
b36_secs_raw,BASE(secs,36),
b36_secs_len,MAX(LEN(b36_secs_raw)),

We re-convert the $\pi$ to Base-$36$ again, this time passing in the length we just found.

...
b36_secs,BASE(secs,36,b36_secs_len),

We concat the array of Base-$36$ sections and output.

...
CONCAT(b36_secs)
)

Combined this leaves us with the following formula:

=LET(
pi_210_digits,"141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975",
sec_leng,N2,
seq_items,200/sec_leng,
pi_digits_needed,ROUNDUP(seq_items,0)*sec_leng,
pi_digits,MID(pi_210_digits,1,pi_digits_needed),
seq,SEQUENCE(ROUNDUP(seq_items,0)),
secs,MID(pi_digits,sec_leng*(seq-1)+1,sec_leng),
b36_secs_raw,BASE(secs,36),
b36_secs_len,MAX(LEN(b36_secs_raw)),
b36_secs,BASE(secs,36,b36_secs_len),
CONCAT(b36_secs)
)

Using this formula and varying the input for sec_leng in the domain of $[1 ...15]$ will allow us to find the most efficent Base-$36$ compression that can be handled in an excel formula.

Once a Base-$36$ string and segment length are found, we need to write a decompression formula for that string. In this case, we found that a segment length of $6$ was ideal, and rendered the following string:

"2CATL99R5BDI7NG1X34MEPT039E0VR67BTI4G4GG28539KNQ4QEG9YADWYRT5NOR7VG8QUBA8HLF5UAP9GT0A2WS8M3TYOFJ6QZLY91XXD7W1P59BM8M93MFANSI90FSJGZXFY7216"

To decompress this, we will first split it back into the $23$ length $6$ sections using MID and ROW

MID(~,1+(ROW(1:23)-1)*6,6)

We then convert the resulting array of strings back into Base-$10$ using DECIMAL

DECIMAL(MID(~),36)

This renders a string array of the digits, with each index holding $6$ digits. We concat this array to get a single string holding all of our needed digits.

CONCAT(DECIMAL(~))

From here we can implement FIND as in approach 0

=FIND(A1,CONCAT(~))

Combined, this leaves us with the formula

=FIND(A1,CONCAT(DECIMAL(MID("2CATL99R5BDI7NG1X34MEPT039E0VR67BTI4G4GG28539KNQ4QEG9YADWYRT5NOR7VG8QUBA8HLF5UAP9GT0A2WS8M3TYOFJ6QZLY91XXD7W1P59BM8M93MFANSI90FSJGZXFY7216",1+(ROW(1:23)-1)*6,6),36)))

Score: 195 Bytes

We can try combining this with the prefixing trick from Approach 1 - this changes the Base-$36$ finding let function to be:

=LET(
pi_210_digits,"3238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975",
sec_leng,N2,
seq_items,(200-(LEN(PI()&"")-2))/sec_leng,
pi_digits_needed,ROUNDUP(seq_items,0)*sec_leng,
pi_digits,MID(pi_210_digits,1,pi_digits_needed),
seq,SEQUENCE(ROUNDUP(seq_items,0)),
secs,MID(pi_digits,sec_leng*(seq-1)+1,sec_leng),
b36_secs_raw,BASE(secs,36),
b36_secs_len,MAX(LEN(b36_secs_raw)),
b36_secs,BASE(secs,36,b36_secs_len),
CONCAT(b36_secs)
)

In this case we end up with a longer segment length of $8$ being optimal, which ends up adding bytes to the formula, rather than making it smaller.

=FIND(A1,CONCAT(PI(),DECIMAL(MID("0EVKYXOH129AGROK0922YG810NGEQMS50KHH3WX40INX8CIR13MX3ASD0JCJEXN206SWOSHS0ALH6IVU0KHRDHIU0AN8BV5W11CAVLPI0N3LUTYL17454FYZ18B1LEY90P8G4PZG",1+(ROW(1:17)-1)*8,8),36)),3)-2

Score: 202 Bytes

Approach 3: UTF-8 TBCS String Compression

If instead of going to ASCII Base-$36$, we use unicode charaters we can use up to three bytes per character and then retrieve that info using the UNICODE command.

To find the optimal unicode string compression of $\pi$ past the decimal using UTF-8 TBCS, we will first start by storing our desired digits of $\pi$ as a string in cell [A2]. (note: we are reserving [A1] as the input to the end function)

We will then define a table as below. The formulas will result in a guess which is valid iff the sum of the last two values in Columns Start and length is equal to the number of chars needed, and all values in Is Valid are true. Note that we will mark any segment that begins with 0 as when this leading zero will be lost when the string is decompressed. Simialrly any value that is equal to 34 is flagged as being invalid, as this corresponds to the " character, and breaks the containing string. - alternatively, this could be flagged, and a double quote inserted it it's place.

Note that restricting the value of any substring only to being less than $2^{16}$, in the formula for length what makes this a TBCS approach.

Start	Length	SubString	Is Valid	Char
1	=IF(VALUE(MID($A$2,[@Start],3))<(2^16),3,2)	=MID($A$2,[@Start],[@Length])B2,C2)	=NOT(OR(VALUE([@SubString])=34,LEFT([@SubString])="0"))	=UNICHAR([@SubString])
=SUM(OFFSET(Tbl[@[Start]:[Length]],-1,0))	''	''	''	''

To address any invalid symbols or segments, we will move from the top row and move down. If a value in Is Valid is False, then this can likely be corrected by manually reducing the Length in one of the rows above.

Note: Without modification, it is not possible to compress numbers with runs of five or more consecutive 0s or any number that begins with 0.

Once a valid set of chars is found it can be collected into a string with =CONCAT(Tbl[Char]).

Decompressing this string is similar to that of Approach 2: the string is wrapped in logic that splits by character, gets the character code then concats and outputs the results.

 CONCAT(UNICODE(MID(~,ROW(1:44),1)))

Alternatively the string can be collected in reverse as with =LET(chrs,Tbl[Char],CONCAT(MID(chrs,SEQUENCE(LEN(chrs),,LEN(chrs),-1),1)))

And this renders a string of the same length which can be decompressed with

CONCAT(UNICODE(RIGHT(~,ROW(1:44))))

This of course, means that this leads to two equivalent solutions to our stated problem

=FIND(A1,CONCAT(UNICODE(MID("㝏枧⌓纀閷┞⊉◴Ⓑ銆ᵆᇰ砽慨↬⌦뱽ၳᮛ♝믖좀ं᥆⒨됏얖媄ᓯ齬℡Җ쑬⠞䮹剱ᗜ깎┑횒锴",ROW(1:44),1))))

or

=FIND(A1,CONCAT(UNICODE(RIGHT("锴횒┑깎ᗜ剱䮹⠞쑬Җ℡齬ᓯ媄얖됏⒨᥆ं좀믖♝ᮛၳ뱽⌦↬慨砽ᇰᵆ銆Ⓑ◴⊉┞閷纀⌓枧㝏",ROW(1:44)))))    

Score: 90 Char, 177 Bytes

We can also modify the table above so that Start has an initial value of 15, to combine this approach with with prefixing trick from Approach 1.

This renders two solutions with no score improvement.

=FIND(A1,CONCAT(PI(),UNICODE(MID("纀閷┞⊉◴Ⓑ銆ᵆᇰ砽慨↬⌦뱽ၳᮛ♝믖좀娚ብ༄៏얖媄ᓯ齬℡Җ쑬⠞䮹剱ᗜ깎┑횒锴",ROW(1:41),1))),3)-2

=FIND(A1,CONCAT(PI(),UNICODE(RIGHT("锴횒┑깎ᗜ剱䮹⠞쑬Җ℡齬ᓯ媄얖៏༄ብ娚좀믖♝ᮛၳ뱽⌦↬慨砽ᇰᵆ銆Ⓑ◴⊉┞閷纀",ROW(1:41)))),3)-2

Score: 96 Char, 177 Bytes

Approach 4: UTF-8 DBCS String Compression

We can modify Approach 3 so that the table column Length is initially defined as being restricted such that no substring has a value greater than $2^8$, rather then $2^{16}$ to make DBCS solution.

=IF(VALUE(MID($A$2,[@Start],3))<(2^8),3,2)

Following the method as described above renders the two equivalant solutions:

=FIND(A1,CONCAT(CODE(RIGHT("Ä&�1_0�>,`7i�UÁFf��2Jo0��(;5¬ß:2_<�T]F�B�R 3VPÖbCF
*ý0�P�VcÐV>(�N�\-^JÑ:
K]'©ÅT�2O &+�.î]a:5�;�",ROW(1:95)))))

=FIND(A1,CONCAT(CODE(RIGHT("Ä&�1_0�>,`7i�UÁFf��2Jo0��(;5¬ß:2_<�T]F�B�R 3VPÖbCF
*ý0�P�VcÐV>(�N�\-^JÑ:
K]'©ÅT�2O &+�.î]a:5�;�",ROW(1:95)))))

Score: 138 Char, 151 Bytes

Here if we apply the prefixing trick we do actually manage to save a single byte, and get the solutions

=FIND(A1,CONCAT(PI(),CODE(RIGHT("Ä&�1_0�>,`7i�UÁFf��2Jo0�Q(;5¬ß:2_<�T]F�B�R 3VPÖbCF
*ý0�P>bY�V>(�N�\-^JÑ:
K]'©ÅT�2O &+�.& ",ROW(1:89)))),3)-2

=FIND(A1,CONCAT(PI(),CODE(MID(" &.�+& O2�TÅ©']K
:ÑJ^-\�N�(>V�Yb>P�0ý*
FCbÖPV3 R�B�F]T�<_2:߬5;(Q�0oJ2��fFÁU�i7`,>�0_1�&Ä",ROW(1:89),1))),3)-2

Score: 141 Char, 150 Bytes

Approach 5: ASCII String Compression

If we again modify Approach 3, this time such that Length is initially defined as being restricted such that no substring has a value greater than $2^7$, then we can make an ASCII only solution.

=IF(VALUE(MID($A$2,[@Start],3))<(2^7),3,2)

Following the method as described above renders the two equivalant solutions:

=FIND(A1,CONCAT(CODE(MID("��\A#YO &.�+& O2�T�GE']Ki��a1,;��N�(>V�Yb>P�0�5*
FCb��PV3 R�B�F]T�<_2:��H5;(Q�0oJ2��fF�&4n7;@.�^Y6	�&��,",ROW(1:44),1))))

=FIND(A1,CONCAT(CODE(RIGHT(",��&�	6Y^�.@;7n4&�Ff��2Jo0�Q(;5H��:2_<�T]F�B�R 3VP��bCF
*5�0�P>bY�V>(�N��;,1a��iK]'EG�T�2O &+�.& OY#A\��",ROW(1:104)))))

Score 148 char, 148 bytes

If we apply the prefixing solution again, we find no improvement yet again.

=FIND(A1,PI()&CONCAT(CODE(MID(" &.�+& O2�T�GE']Ki��a1,;��N�(>V�Yb>P�0�5*
FCb��PV3 R�B�F]T�<_2:��H5;(Q�0oJ2��fF�&4n7;@.�^Y6	�&��",ROW(1:96),1))),3)-2

=FIND(A1,PI()&CONCAT(CODE(RIGHT("��&�	6Y^�.@;7n4&�Ff��2Jo0�Q(;5H��:2_<�T]F�B�R 3VP��bCF
*5�0�P>bY�V>(�N��;,1a��iK]'EG�T�2O &+�.& ",ROW(1:96)))),3)-2

Conclusion:

Going by bytecount, the four ASCII sting compressed solutions shown in Approach 5 seem optimal at 148 bytes. By char count, the two inital UTF-8 TBCS solutions shown in Approach 3 seem optimal at 90 char / 177 Bytes.