7
\$\begingroup\$

This will turn into a series involving other aspects of calculus, including using the "derivative" of a string to find "stationary points" etc, as well as "integration" of sentences

Introduction

If y'all have ever studied calculus, you'll most likely know that differentiation is limited to differentiable functions.

Not that there's anything wrong with that, but have you ever wondered what it'd be like to take the first (or second) derivative of a word? Or how about a sentence? You probably haven't, so let me explain my theory of string based differentiation.

The Basics

If you already know how differentiation works, feel free to skip this part

When being introduced to the concept of differential calculus, most beginners are taught about the concept of differentiation from first principles. This is based on the concept of finding the gradient of a tangent to a curve via the gradient formula:

$$ m = \frac{y_2 - y_1}{x_2 - x_1} $$

On the tangent, we say that we have two points: \$(x, f(x))\$ and \$(x + h, f(x + h))\$, where \$h\$ is an infinitesimal number. Plugging this into the gradient formula gives:

$$ m = \frac{f(x+h)-f(x)}{x+h-x} = \frac{f(x+h) - f(x)}{h} $$

In order to eliminate any inaccuracies from the tangent's gradient, we take the limit of the above equation as \$h\$ approaches 0, giving us:

$$ \frac{d}{dx}(f(x)) = \lim_{h\to 0}\left(\frac{f(x+h)-f(x)}{h}\right) $$

Now, you may be asking "how on earth does that apply to string calculus? First-principles uses functions and numbers, not characters!"

Well, for this challenge, I've devised a slightly modified version of the first principles concept. The "formula" we'll be using is:

$$ \frac{d}{dx}(y) = \sum_{h=-1}^{1}\left(h\left[y\left[x+h\right]-y\left[x\right]\right]\right) = y\left[x+1\right]-y\left[x-1\right] $$

The Formula Explained

One of the major differences here is that there is no longer a limit being taken of the equation. That's because it doesn't quite make sense having something approaching 0 for the whole string. Rather, we use a \$\sum\$ to inspect the characters to the left and right of the character in question.

Also, inside the sum, the first \$y\$ is now being multiplied by the \$h\$. This is to ensure that the result is balanced, as without it, the results weren't very reflective of the string.

To evaluate this formula for a certain index \$x\$, you:

  • Evaluate \$-y[x-1] + y[x]\$
  • Evaluate \$0\$
  • Evaluate \$y[x+1] - y[x]\$
  • Summate the above three items.

Essentially, you are calculating the following:

$$ y[x+1]-y[x-1] $$

Note that when subtracting things, the ordinal values are used. E.g. c - a = 99 - 97 = 2

If any position becomes negative, it starts indexing from the back of the string (like python does). If any position becomes greater than the length of the string, the character is ignored.

Applying Differentiation to the Whole String

By now, you may have noticed that the first principles formula only works on individual characters, rather than the whole string. So, in this section, we will develop a more generalised approach to using the formula.

To apply the formula to the whole string, we get the derivative of each character in the string, convert those numbers to characters based on code point conversion (like python's chr() function) and concatenate the results into a single string. Now, the problem here is that results may sometimes be negative. To solve this problem, we will introduce a second string to store information: the sign string.

This string will consist of a combination of any two letters of your choice, representing whether or not a character is positive.

Worked Example

Let's take a look at what would happen with the word Code:

  • We start at position 0 (C). The three parts for this character are -(e + C), 0 and o - c. These evaluate to -34, 0 and 44. The sum of these is 10 and the sign is +. So a newline is added to the main string, and a + is added to the sign string.
  • We then move to position 1 (o). The three parts are: -(o + C), 0 and d - o. These evaluate to 44, 0 and -11. The sum of these is 33, so a ! is added to the main string and a + is added to the sign string.
  • We then move to position 2 (d). The three parts are: -(o + d), 0 and e - d. These evaluate to -11, 0 and 1. The sum of these is -10, so a new line is added to the main string and a - is added to the sign string.
  • We finally move to position 3 (e). The position 3 + 1 is longer than the length of the string, so therefore, the process ends.

Therefore, the final result is ["\n!\n", "++-"]

Test Cases

Format is input, newline, output. These test cases were generated using Python, and uses UTF-8.

Code
('\n!\n', 'ppn')
Code Golf
('\t!\nD\x1eO%\t', 'ppnnnppn')
Cgcc
('\x04 \x04', 'ppn')
Lyxal
('\r,\x18\x0c', 'ppnn')
3 - 3 = 0
('\x10\x06\x00\x06\x00\n\x00\r', 'nnpppppn')
Lim x -> 0
('9!I\x0b\x00K\x1e\r\x0e', 'ppnppnpnn')
lim x -> 0
('9\x01I\x0b\x00K\x1e\r\x0e', 'ppnppnpnn')

('', '')
afanfl;aknsf
('\x00\x00\x08\x05\x02+\x0b0\r\x08\x08', 'ppppnnnpppn')
nlejkgnserg
('\x05\t\x02\x06\x03\x03\x0c\t\x01\x02', 'pnnpnppnnp')
38492
('\x06\x01\x01\x02', 'pppn')
abcdefghijklmnopqrstuvwxy
('\x17\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02', 'nppppppppppppppppppppppp')
KLJBFD
('\x08\x01\n\x04\x02', 'pnnnp')
::::::::::::
('\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', 'ppppppppppp')
aaa
('\x00\x00', 'pp')
aaaaa
('\x00\x00\x00\x00', 'pppp')

Rules

  • Input will be restricted to printable ASCII
  • You can use any codepage you like for the output, just so long as it is consistently used. This means that UTF-8, CP437, etc. are fair game.
  • Input can be taken in any convenient and reasonable format
  • Output can be given in any convenient and reasonable format. Suggested formats include: a list of both strings, each string on a newline, both strings joined together. It's up to you really how you want to output the result.
  • Unicode sequences (like \x00 or \x05) can be used in the output if wanted. In other words, both real representations and Unicode control sequences are valid output given they are applied consistently.
  • You can use any two characters for the string sign. That's right! It doesn't have to be + and -... it could be p and n or 3 and '. It really doesn't matter as long as you use two distinct characters.
  • For this challenge, 0 is considered positive.
    • Both full programs and functions are allowed.

Scoring

Of course, this is code-golf, so the shortest answer wins!

Reference Program

Try it online!

Special Thanks

I'd just like to say a huge thanks to @xnor and @FryAmTheEggman for showing me that my original model of string differentiation was not the best way of doing things. I'm much happier with this new method that you see here!

\$\endgroup\$
4
  • \$\begingroup\$ How is -(e + C) = -34 do you mean -e + C \$\endgroup\$ – Expired Data Feb 27 '20 at 11:42
  • 2
    \$\begingroup\$ Can we use truthy/falsy to represent positive/negative? And can we output nothing for an empty string input? \$\endgroup\$ – Noodle9 Feb 27 '20 at 12:56
  • \$\begingroup\$ @Noodle9 you may indeed do that \$\endgroup\$ – lyxal Feb 27 '20 at 20:37
  • 1
    \$\begingroup\$ In college I thought it was just coincidence that calculus and Cthulhu both start with 'C'. Now I'm not so sure... \$\endgroup\$ – Bob Jarvis - Reinstate Monica Mar 4 '20 at 13:23
3
\$\begingroup\$

05AB1E, 12 11 bytes

Ǥš¥ü+Dd‚Äç

-1 byte thanks to @ExpiredData.

Uses I/O with UTF-8 encoding like the challenge description, and uses characters \0 for negative and \1 for 0 or positive. Outputs as a list of list of characters.

Try it online or verify all test cases (the Join is added to pretty-print the character-lists to strings, but feel free to remove it to see the actual output).

Explanation:

Ç            # Convert the characters in the (implicit) input-string to their unicode values
             #  i.e. "Code!!!" → [67,111,100,101,33,33,33]
 ¤š          # Prepend its own trailing item (without popping it)
             #  → [33,67,111,100,101,33,33,33]
   ¥         # Pop and push the deltas (forward differences) of this list
             #  → [34,44,-11,1,-68,0,0]
    ü        # For each overlapping pair of differences:
             #   → [[34,44],[44,-11],[-11,1],[1,-68],[-68,0],[0,0]] 
     +       #  Sum them together
             #   → [78,33,-10,-67,-68,0]
      D      # Duplicate this list
       d     # Check for each whether it's >=0 (0 if negative; 1 if 0 or positive)
        ‚    # Pair those two lists together
             #  → [[78,33,-10,-67,-68,0],[1,1,0,0,0,1]]
         Ä   # Take the absolute value of each
             #  → [[78,33,10,67,68,0],[1,1,0,0,0,1]]
          ç  # And convert all integers to ASCII characters
             #  → [["N","!","\n","C","D","\0"],["\1","\1","\0","\0","\0","\1"]]
             # (after which this pair of character-lists is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 11 bytes if you make your distinct values ascii 1 and ascii 0 \$\endgroup\$ – Expired Data Feb 27 '20 at 11:58
  • \$\begingroup\$ Wow! I would not have thought that this could be solved in just 11 bytes. Well done! +1 \$\endgroup\$ – lyxal Feb 27 '20 at 21:47
2
\$\begingroup\$

Burlesque, 39 bytes

)**iRrtm{{0 2}sip^.-}~]Jm{0>=}j{abL[}\m

Try it online!

)**       # Map ord() on string
iR        # Generate all rotations
rt        # Rotate once to put deriv[0] to first pos
m{        # Map
 {0 2}si  # Take the 0th and 2nd chars (either side)
 p^       # Push (un-array)
 .-       # Difference
}
~]        # Discard last (i.e. deriv[-1])
J         # Duplicate
m{0>=}    # Create pos/neg list as 0,1
j         # Swap
{
 ab       # Abs
 L[       # Chr()
}\m       # Map and concat to str
\$\endgroup\$
2
  • \$\begingroup\$ If there's one thing I enjoy about your answers on CGCC, it's your complete dedication to Burlesque. I like how you've picked up a language and stuck with it. +1 \$\endgroup\$ – lyxal Feb 27 '20 at 21:50
  • \$\begingroup\$ @Lyxal Well, my day to day languages are Fortran and Python (besides small programs). I quite like the challenge of solving things and thinking in a different way. I am not going to be competitive when it comes to some of the insane Python tricks people pull and Fortran really doesn't come close to anything resembling golf usually. \$\endgroup\$ – DeathIncarnate Feb 28 '20 at 0:13
2
\$\begingroup\$

Jelly, 13 bytes

LŻịOI+Ɲµ>-,AỌ

Try it online!

Uses \0 and \1 for the sign string, the Footer converts the output into code points to be clearer

How it works

Just a refresher on Jelly's indexing rules: 1-indexed, wrapping modularly. That means that 0 ị “1234” returns 4.

LŻịOI+Ɲµ>-,AỌ - Main link. Takes a string s on the left
L             - Length of s
 Ż            - [0, 1, 2, ..., len(s)]
   O          - Yield the code points of s
  ị           - Index into the code points with the range
                This is equivalent to prepending the last character of s
    I         - Forward differences
     +Ɲ       - Sums of overlapping pairs
       µ      - Call these sums S and use as the left and right arguments
        >-    - Is each sum greater than -1?
           A  - Yield the absolute values of each sum
          ,   - Pair
            Ọ - Convert to characters
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 28 bytes

≔E⊖Lθ⁻℅§θ⊕ι℅§θ⊖ιθ⟦⭆θ‹ι⁰⭆θ℅↔ι

Try it online! Link is to verbose version of code. Outputs the signs first (0=+,1=-) as otherwise the default print format will mangle the newlines. Explanation:

≔E⊖Lθ⁻℅§θ⊕ι℅§θ⊖ιθ

Compute the pairs of ordinal differences, excluding the last pair (which in Charcoal would normally wrap around to 0).

⟦⭆θ‹ι⁰⭆θ℅↔ι

Print the signs of the differences and the characters of the absolute values of the differences.

\$\endgroup\$
2
  • \$\begingroup\$ Where is the map function documented within the charcoal docs? I seem to be able to find it. Still, nice answer. +1 \$\endgroup\$ – lyxal Feb 27 '20 at 21:49
  • \$\begingroup\$ @Lyxal Since it returns a result, it's on the Operators page, but it's listed under "Other" at the end of that page. \$\endgroup\$ – Neil Feb 28 '20 at 0:05
1
\$\begingroup\$

Python 3, 119 \$\cdots\$ 92 91 bytes

Saved 6 bytes thanks to Kevin Cruijssen!!!
Added 6 bytes to handle empty string input.

lambda s:zip(*[(chr(abs(S)),S<0)for S in(ord(s[i+1])-ord(s[i-1])for i in range(len(s)-1))])

Try it online!

Outputs a sequence of: a tuple of characters and a tuple of True/False for negative/positive values.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 113 bytes by combining the a,b into a sum S. \$\endgroup\$ – Kevin Cruijssen Feb 27 '20 at 12:31
  • \$\begingroup\$ @KevinCruijssen Ah, very nice - thanks! :-) \$\endgroup\$ – Noodle9 Feb 27 '20 at 12:37
  • \$\begingroup\$ Interesting use of and to handle the empty string! I wouldn't have thought of using Python's short-circuiting in that way. +1 \$\endgroup\$ – lyxal Feb 27 '20 at 21:55
  • 1
    \$\begingroup\$ @Lyxal Turns out it's one less byte to use range instead of the and short-circuit with zip to handle the empty string input. \$\endgroup\$ – Noodle9 Feb 27 '20 at 23:10
1
\$\begingroup\$

Ruby, 87 85 82 bytes

->s{d=n='';i=0;loop{k=s[i+=1].ord-s[i-2].ord;n+="++-"[k<=>0];d<<k.abs}rescue[d,n]}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ What does the rescue at the end do? I've never learnt Ruby, but this answer looks impressive (+1) \$\endgroup\$ – lyxal Feb 27 '20 at 21:52
  • \$\begingroup\$ rescue is Ruby's equivalent to catch; it performs exception handling. I'll write a full explanation later, but basically I let my counter i go past the end of the string and catch the error to save bytes over actually stopping at i<s.size-1, which is just a little more expensive. \$\endgroup\$ – Value Ink Feb 27 '20 at 23:29

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.