9
\$\begingroup\$

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

\$\endgroup\$
4
  • 6
    \$\begingroup\$ Can you add a few test cases? \$\endgroup\$
    – Jonah
    Commented Nov 7, 2023 at 7:11
  • 1
    \$\begingroup\$ what is the output? any valid suffix? All valid suffixes? any valid fixed string? The length of suffix? \$\endgroup\$
    – tsh
    Commented Nov 7, 2023 at 8:20
  • 2
    \$\begingroup\$ What does “your permitted chars” mean? Is this restricted source challenge? \$\endgroup\$
    – tsh
    Commented Nov 7, 2023 at 8:23
  • 1
    \$\begingroup\$ The output should be as I have stated in the title of this post - namely, the shortest possible suffix (or one of them, if there are multiple of equal length). "Permitted chars" represents the ASCII values that an input is guaranteed to consist of and what you are allowed to append, nothing to do with source code. \$\endgroup\$
    – Olipro
    Commented Nov 7, 2023 at 12:14

8 Answers 8

2
\$\begingroup\$

Charcoal, 38 bytes

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

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

⊞υωFυ

Start a breadth-first search with an empty suffix.

¿¬ⅈ

Check that a solution hasn't yet been found.

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

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

FΣ⟦αβ⭆χκ._⟧

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:

⊞υSFυ¿¬ⅈ¿﹪ΣEι×⊕λ℅κφFΣ⟦αβ⭆χκ._⟧⊞υ⁺ικι

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ _ is missing, but otherwise, looks good. \$\endgroup\$
    – Olipro
    Commented Nov 7, 2023 at 12:33
  • \$\begingroup\$ @Olipro fixed it \$\endgroup\$
    – bsoelch
    Commented Nov 7, 2023 at 14:27
  • \$\begingroup\$ 129 bytes by abusing IO (taking bytes or list of codepoints, returning list of codepoints) \$\endgroup\$
    – STerliakov
    Commented Nov 8, 2023 at 3:51
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Produces the wrong output for an input of .ll. \$\endgroup\$
    – Neil
    Commented Nov 7, 2023 at 20:02
  • \$\begingroup\$ @Neil thanks. I’d forgotten that base decompression didn’t use bijective base conversion. \$\endgroup\$ Commented Nov 7, 2023 at 22:00
  • \$\begingroup\$ I'm surprised there isn't a bijective version. \$\endgroup\$
    – Neil
    Commented Nov 7, 2023 at 22:02
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
}                    //
\$\endgroup\$
2
  • 1
    \$\begingroup\$ s=>{for(g=n=>S=n?B([n&127])+g(n>>7):"",n=0,B=Buffer;B(s+g(n++)).map(c=>t+=c*++i,i=t=0),t%1e3|!/^[\w.]*$/.test(S););return S} \$\endgroup\$
    – tsh
    Commented Nov 8, 2023 at 3:03
  • 1
    \$\begingroup\$ 121 \$\endgroup\$
    – l4m2
    Commented Nov 8, 2023 at 16:10
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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
  }
}
\$\endgroup\$
2
  • \$\begingroup\$ You missed _, - otherwise, looks good. \$\endgroup\$
    – Olipro
    Commented Nov 7, 2023 at 12:32
  • \$\begingroup\$ 190 bytes: ato.pxeger.com/… \$\endgroup\$
    – corvus_192
    Commented Nov 7, 2023 at 15:39
0
\$\begingroup\$

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
}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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