Produce the shortest suffix for an (almost) arbitrary string

Question

I encountered some silly code from a game and I figured this would actually turn into a fun golfing problem, so:

Given any ASCII string in the limited char range specified below.

Append as few characters as possible such that, given:

i = 1
sum = 0
for char in string
  sum += char.intval * i++
end for

sum % 1000 == 0

Where intval is the ASCII value of the character.

Both the string prefix and your permitted chars are: A-Z a-z 0-9 . _

You may assume the numeric result of the pseudo-code above is a number that fits within an unsigned 32-bit int (i.e. no input will be given that causes sum to exceed 2^32-1 after appending the minimum possible chars to satisfy sum)

You may choose to output the input concatenated with your calculated suffix string, or just your suffix string as you prefer.

Example

Given the input ddd the shortest solution would be appending one more d because (100 + (100*2) + (100*3) + (100*4)) % 1000 == 0

Answer 1

Charcoal, 38 bytes

⊞υωＦυ¿¬ⅈ¿﹪ΣＥ⁺θι×⊕λ℅κφＦΣ⟦αβ⭆χκ._⟧⊞υ⁺ικι

Try it online! Link is to verbose version of code. Explanation:

⊞υωＦυ

Start a breadth-first search with an empty suffix.

¿¬ⅈ

Check that a solution hasn't yet been found.

¿﹪ΣＥ⁺θι×⊕λ℅κφ

If the input plus current suffix is not a multiple of 1000, then:

ＦΣ⟦αβ⭆χκ._⟧

Loop over all valid characters.

⊞υ⁺ικ

Append the character to the suffix and add this to the list of suffixes to check.

ι

But if it is then output the suffix as the solution.

Would be only 36 bytes to output the full string:

⊞υＳＦυ¿¬ⅈ¿﹪ΣＥι×⊕λ℅κφＦΣ⟦αβ⭆χκ._⟧⊞υ⁺ικι

Try it online! Link is to verbose version of code.

Answer 2

Python, 147 bytes

-7 bytes, thanks to STerliakov

def f(s,q="",Q=[]):
 while(i:=0)+sum((i:=i+1)*ord(c)for c in s+q)%1000:*Q,q=[q+c for c in{*map(chr,range(46,123))}-{*"/:;<=>?@[\\]^`"}]+Q
 return q

Attempt This Online!

{*map(chr,range(46,123))}-{*"/:;<=>?@[\\]^`"} produces an iterable of the allowed characters by taking all ASCII-characters form . to z (smallest and largest allowed character) and the removing the additional characters.
Using the standard library would take the same amount of characters: from string import* "._"+digits+ascii_letters

---

Python, 140 bytes

def f(s,Q=[]):
 while(i:=0)+sum((i:=i+1)*ord(c)for c in s)%1000:*Q,s=[s+c for c in{*map(chr,range(46,123))}-{*"/:;<=>?@[\\]^`"}]+Q
 return s

Attempt This Online!

---

Python, 129 bytes

suggested by STerliakov, uses binary strings instead of strings

def f(s,Q=[]):
 while(i:=0)+sum(c*(i:=i+1)for c in s)%1000:*Q,s=[[*s,c]for c in{*range(46,123)}-{*b"/:;<=>?@[\\]^`"}]+Q
 return s

Attempt This Online!

Answer 3

Jelly, 26 bytes

ṃØW;”.¤Ḋ
Ç;@O×JSƊȷḍ
0ç1#ḢÑ

Try it online!

A full program that takes a string argument and implicitly prints the suffix needed.

Thanks to Neil for pointing out a problem related to base decompression, now fixed (at a cost of two bytes and a 64-fold efficiency penalty!

Explanation

ṃØW;”.¤Ḋ     # ‎⁡Helper link 1: takes an integer and generates a suffix
ṃ            # ‎⁢Base decompress into:
 ØW;”.¤      # ‎⁣- Word characters (A-Za-z0-9_) concatenated to "."
       Ḋ     # Remove first character (avoids issue related to suffixes that start with .)
‎⁤
Ç;@O×JSƊȷḍ  # ‎⁢⁡Helper link 2: Takes an integer as left argument and the original string as right argument and returns 1 if it meets the requirements and zero if not
Ç           # ‎⁢⁢Call helper link 1
 ;@         # ‎⁢⁣Concatenate the output of this to the original string
   O        # ‎⁢⁤Codepoints
       Ɗ    # ‎⁣⁡As a monadic chain:
    ×J      # ‎⁣⁢Multiply by indices
      S     # ‎⁣⁣Sum
        ȷḍ  # ‎⁣⁤Divisible by 1000
‎⁤⁢
0ç1#ḢÑ       # ‎⁤⁣Main link: takes a string as its argument and returns the suffix needed
0ç1#         # ‎⁤⁤Starting with zero, find the first integer that when called into helper link 2 returns truthy
    Ḣ        # Head (since # returns a list)
     Ñ       # ‎⁢⁡⁡Call helper link 1 to regenerate the suffix

💎

Created with the help of Luminespire.

Answer 4

Scala 2, 153 142 136 bytes

s=>{def z:Stream[String]=s#::z.flatMap(x=>'.'to'z'diff "/:;<=>?@[\\]^`"map(x+))
z.find(_.zipWithIndex.map{case(c,j)=>j*c+c}.sum%1000<1)}

Attempt This Online!

Recursively constructs an infinite Stream of possible suffixes and chooses the first with the correct sum. They iterate from shortest to longest, so it produces the correct output.

Alternative Solution, 158 139 bytes:

s=>Stream.iterate(Seq(s))(_.flatMap(s=>'.'to'z'diff "/:;<=>?@[\\]^`"map(s+))).flatten.find(_.zipWithIndex.map{case(c,j)=>j*c+c}.sum%1000<1)

Same idea as above, without a recursive function. Sadly, Stream.iterate and flatten is very verbose.

Answer 5

JavaScript (Node.js), 121 bytes

-3 thanks to @tsh
-3 thanks to @l4m2

s=>{for(B=Buffer,g=n=>S=n?B([n&127])+g(n>>7):"",n=0;B(s+g(n++)).map(c=>t+=c*++i,i=t=0),t%1e3|/[^\w.]/.test(S););return S}

Try it online!

Or 118 bytes if we can return the full string instead of just the suffix.

Commented

s => {               // s = input string
  for(               // loop:
    B = Buffer,      //   B = alias for Buffer
    g =              //   g is a recursive helper function
    n =>             //   taking n = integer encoding the suffix
      S =            //     save the suffix in S
      n ?            //     if n is not 0:
        B([n & 127]) //       append the char. with ASCII code n & 127
        + g(n >> 7)  //       and do a recursive call with n >> 7
      :              //     else:
        "",          //       stop
    n = 0;           //   start with n = 0
    B(               //   get the ASCII codes of:
      s +            //     the input string
      g(n++)         //     followed by the suffix computed with g(n)
    )                //     (increment n afterwards)
    .map(c =>        //   for each ASCII code c:
      t += c * ++i,  //     increment i and add c * i to t
      i = t = 0      //     start with i = 0 and t = 0
    ),               //   end of map()
    t % 1e3 |        //   continue while t is not divisible by 1000
    /[^\w.]/         //   or there is an invalid character ...
    .test(S);        //   ... in the suffix
  );                 // end of for()
  return S           // return the suffix
}                    //

Answer 6

05AB1E, 19 bytes

žj'.«∞δã˜õš.Δ«ÇƶO₄Ö

Try it online or verify some more test cases.

Explanation:

žj          # Push builtin string "ab...yzAB...YZ01...89_"
  '.«      '# Append an "."
     ∞      # Push an infinite positive list: [1,2,3,...]
      δ     # Use each integer in this list as separated argument on the string:
       ã    #  Cartesian power
        ˜   # Flatten this list of lists of strings
         õš # Prepend an empty string ""
.Δ          # Pop and find the first value that's truthy for:
  «         #  Append the current potential suffix to the (implicit) input-string
   Ç        #  Convert it to a list of codepoint-integers
    ƶ       #  Multiply each integer by its 1-based index
     O      #  Sum the list together
      ₄Ö    #  Check whether this sum is divisible by 1000
            # (after which the found result is output implicitly)

Answer 7

Scala, 267 190 bytes

A port of @bsoelch's Python answer in Scala.

Saved 77 bytes thaks to @corvus_192

---

Golfed version. Attempt this online!

s=>{var(a,z,l)=(Seq[String](),"",".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ")
val V=l+l.toLowerCase
while(0<(s+z).zipWithIndex.map{case(c,j)=>j*c+c}.sum%1000){a=a.drop(1)++V.map(z+);z=a.head}
z}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    println(f(""))
    println(f("Test"))
    println(f("Hello World"))
    println(f("235711"))
  }

  def f(s: String, q: String = "", i: Int = 0, Q: List[String] = List(), l: String = ".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"): String = {
    val lLower = l + l.toLowerCase
    var QNew = Q
    var qNew = q
    var iNew = i
    while ((s + qNew).map(_.toInt).zipWithIndex.map { case (c, ind) => (ind + 1) * c }.sum % 1000 != 0) {
      QNew = QNew.drop(1) ++ lLower.map(qNew + _)
      qNew = QNew.head
      iNew = 0
    }
    qNew
  }
}

Answer 8

Go, 309 305 bytes

Saved 4 bytes thanks to the comment of @ceilingcat

---

Golfed version. Attempt This Online!

func f(s string)string{return g(s,"",0,[]string{},".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ")}
func g(s,q string,i int,Q[]string,l string)string{l+=strings.ToLower(l);for{r:=0
for i,c:=range s+q{r-=^i*int(c)};if r%1000<1{break};if len(Q)>1{Q=Q[1:]};for _,c:=range l{Q=append(Q,q+string(c))};q=Q[0]};return q}

Ungolfed version. Attempt This Online!

package main

import (
	"fmt"
	"strings"
)

func main() {
	fmt.Println(fWithDefaults(""))
	fmt.Println(fWithDefaults("Test"))
	fmt.Println(fWithDefaults("Hello World"))
	fmt.Println(fWithDefaults("235711"))
}

func fWithDefaults(s string) string {
	return f(s, "", 0, []string{}, ".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ")
}

func f(s string, q string, i int, Q []string, l string) string {
	lLower := l + strings.ToLower(l)
	var QNew = Q
	var qNew = q
	for {
		var sum int
		for ind, c := range s + qNew {
			sum += (ind + 1) * int(c)
		}
		if sum%1000 == 0 {
			break
		}
		if len(QNew) > 1 {
			QNew = QNew[1:]
		}
		for _, c := range lLower {
			QNew = append(QNew, qNew+string(c))
		}
		qNew = QNew[0]
	}
	return qNew
}