1
\$\begingroup\$

Inspired (you don't need to know them for this challenge) by the Pumping Lemma for various languages, I propose the following challenge:

  • choose some basis \$B \geq 2\$ and an integer \$n \geq 0\$
  • write a program/function \$P\$
  • partition* \$P\$ into some strings \$s_i \neq \epsilon\$, st. \$P = s_n | \cdots | s_i | \cdots | s_0\$

So far easy enough, here comes the tricky part: The program \$P\$ must for any given string with \$e_i \in \mathbb{N}^+\$

$$(s_n)^{e_n} | \cdots | (s_i)^{e_i} | \cdots | (s_0)^{e_0}$$

output \$\sum_{i=0}^n e_i \cdot B^i\$ and something distinct from any positive number (eg. erroring, \$0\$, \$-1\$ etc.) for any other string.

* You must ensure that for a pumped string as described above the \$e_i\$s are unique.

Informal Explanation

Write a program and split it into a fixed number of chunks and pick a power-series (eg. \$1,2,4,8,\dotsc\$). The program needs to take a string as input and output a number in the following way:

  1. First decide if the input string is made out of the same chunks (in order) as the program, though each chunk can be repeated any number of times. If this is not the case, return \$0\$, a negative number, error out etc.
  2. Count the number of times each chunk is repeated and output (using the powerseries of \$2\$ as example): number_of_last_chunk * 1 + number_of_second_last_chunk * 2 + number_of_third_last_chunk * 4 + ...

Thanks Laikoni for helping me with the explanation!

Example

Suppose I have the program \$\texttt{ABCDEF}\$ and I choose \$n = 2\$ with the partitioning \$s_2 = \texttt{ABC}\$, \$s_1 = \texttt{D}\$ and \$s_0 = \texttt{EF}\$, choosing basis \$B = 2\$ we would have the following example outputs (the input is given to the original program):

$$ \begin{aligned} \text{Input} &\mapsto \text{Output} \\\ \texttt{ABCDE} &\mapsto 0 \\\ \texttt{ABCDEF} &\mapsto 7 \\\ \texttt{ABCDEFEF} &\mapsto 8 \\\ \texttt{ABCABCDEF} &\mapsto 11 \\\ \texttt{ABCDDEFEFEF} &\mapsto 11 \\\ \texttt{ABCABCDDEF} &\mapsto 13 \end{aligned} $$

This submission has score \$3\$.

Walk-through

The example \$\texttt{ABCDE}\$ maps to \$0\$ because the \$\texttt{F}\$ is missing.


Now let's walk through the fifth example: The input is \$\texttt{ABCDDEFEFEF}\$ which we can write using the strings \$s_2,s_1,s_0\$ as follows:

$$ (\texttt{ABC})^1 | (\texttt{D})^2 | (\texttt{EF})^3 $$

So this gives us \$1\cdot 2^2 + 2 \cdot 2^1 + 3 \cdot 2^0 = 4+4+3 = 11\$.

Winning criterion

The score of your program/function will be \$n+1\$ where larger is better, ties will be the submission date earlier is better.

In case you're able to generalize your submission to an arbitrarily large \$n\$, you may explain how and score it as \$\infty\$.


Notations: \$\epsilon\$ denotes the empty string, \$x | y\$ the string concatenation of \$x\$ and \$y\$ & \$x^n\$ is the string \$x\$ repeated \$n\$ times.

\$\endgroup\$
  • \$\begingroup\$ It took me quite I while to get what you are asking even though I'm generally familiar with formal notation. I think it would be nice to give an informal high-level explanation of what the program needs to do at the beginning and additionally at least one worked out example which includes all steps to get to the output number. \$\endgroup\$ – Laikoni Dec 23 '18 at 15:23
  • \$\begingroup\$ @Laikoni: Done so, is it of any help? It's not easy to determine how high-level such an informal explanation should be, that's why I added an example. I'll add an explanation of one input/output-tuple on why it results in that number. \$\endgroup\$ – ბიმო Dec 23 '18 at 15:39
  • \$\begingroup\$ @Arnauld: Yes it is, I'll emphasize in the specification. \$\endgroup\$ – ბიმო Dec 23 '18 at 15:43
  • \$\begingroup\$ @BMO It's still pretty mathy, though I think the explanation of the example is quite helpful. \$\endgroup\$ – Laikoni Dec 23 '18 at 16:10
  • \$\begingroup\$ For the ABCDEF example, why is it allowed when the eᵢs are not unique? \$\endgroup\$ – LegionMammal978 Dec 23 '18 at 17:05
3
\$\begingroup\$

Mathematica, \$B=2\$, score \$\infty\$

With[{s = 
    StringJoin[StringRepeat["a", #] <> "b" & /@ Reverse[Range[#]]]}, 
  ToString[(s; 
     StringReplace[#, 
       StartOfString ~~ a : "(\"" .. ~~ b : ("a" .. ~~ "b") .. ~~ 
          c : ("\"; " <> 
              StringTake[
               ToString[Extract[#0, {1, 2}, Hold], 
                InputForm], {6, -2}] <> ") & ") .. ~~ EndOfString /; 
         AllTrue[Differences[
            d = Length /@ Split[Characters[b]][[;; ;; 2]]], -2 < # < 
             1 &] && Length[d] > 1 :> 
        2^Max[d] StringLength[a] + Total[2^# #2 & @@@ Tally[d]] + 
         StringLength[c]/389][[1]]) &, InputForm]] &

Pure function. Takes \$k=n-1\$ as input and returns the string representing \$P_k\$ as output (for \$k\geq2\$). For the purposes of illustration, take this formatted version of \$P_3\$:

("aaabaabab"; 
  StringReplace[#1, 
    StartOfString ~~ a : ("(\"" ..) ~~ b : (("a" .. ~~ "b") ..) ~~ 
       c : ("\"; " <> 
           StringTake[
            ToString[Extract[#0, {1, 2}, Hold], InputForm], {6, -2}] <>
            ") & " ..) ~~ EndOfString /; 
      AllTrue[Differences[
         d = Length /@ 
           Split[Characters[b]][[1 ;; All ;; 2]]], -2 < #1 < 1 &] && 
       Length[d] > 1 :> 
     2^Max[d] StringLength[a] + 
      Total[Apply[2^#1 #2 &, Tally[d], {1}]] + StringLength[c]/389][[
   1]]) &

This function takes a string as input and either returns a positive integer or an invalid expression ("..."[[1]]) as output. Here, \$s_4=\texttt{("}\$, \$s_3=\texttt{aaab}\$, \$s_2=\texttt{aab}\$, \$s_1=\texttt{ab}\$, and \$s_0\$ encompasses the remainder of the function.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.