11
\$\begingroup\$

A counterstring is some sort of self-describing test data that is used in software testing. Not sure it was actually invented by James Bach, but I know it from there.

The idea is as follows: the test data contains many asterisk (*). The number in front of the asterisk tells you how long the test data is at that point. If you need to know a position in the test data that is not an asterisk, find the last asterisk, look at the number before and add the number of digits that follow.

The sequence starts like this:

2*4*6*8*11*14*17*20*23*
             ^

As you can see, the marked asterisk is at position 14.

If a file happens to be truncated as follows

[...]2045*20

then you can derive that there is a limit of 2047 characters somewhere (2045 where the asterisk is plus 2 for 2 and 0).

It's your task to create the shortest (this is ) program that outputs (std::out or file or whatever) an arbitrary long test string of that format. The length in characters is given as argument. The program shall support up to 2 GB test data (input value 2147483647 characters).

"Dangerous" positions in the 2 GB file:

8*11*
98*102*
998*1003*
9998*10004*
99998*100005*
999995*1000003*
9999995*10000004*
99999995*100000005*
999999995*1000000006*

This should answer @Leaky Nun's question if there is a decision to make between 995*999* and 995*1000* or similar: no.

The end of the 2 GB file with input value 2147483647 is:

2147483640*2147483
\$\endgroup\$
  • \$\begingroup\$ If it does not halt then how do you test it? \$\endgroup\$ – Leaky Nun Aug 23 '16 at 21:24
  • 2
    \$\begingroup\$ Is that length in characters? \$\endgroup\$ – TheBikingViking Aug 23 '16 at 21:31
  • 4
    \$\begingroup\$ Can you prove that we would never have to choose between 995*999* and 995*1000* or anything like that? \$\endgroup\$ – Leaky Nun Aug 23 '16 at 21:36
  • 1
    \$\begingroup\$ In the future, please use the Sandbox to iron out kinks in your challenges before posting them. \$\endgroup\$ – Mego Aug 23 '16 at 22:05
  • 1
    \$\begingroup\$ @ThomasWeller If we can create a longer output, can we take no input and just produce the 2GB string? \$\endgroup\$ – xnor Aug 24 '16 at 7:43
4
\$\begingroup\$

Haskell, 60 58 bytes

As a function we get:

f=length.show
iterate(\n->1+n+(f$n+1+f n))2>>=(++"*").show

Full program, 72 70 bytes

This outputs an infinite counterstring to STDOUT:

f=length.show
main=putStr$iterate(\n->1+n+(f$n+1+f n))2>>=(++"*").show

Inputting the length requires 20 additional bytes:

main=interact(\j->take(read j)$iterate(\n->1+n+(f$n+1+f n))2>>=(++"*").show)

This works up to your approximately your RAM size, since Haskell defaults numeric integral types to Integer.

\$\endgroup\$
3
\$\begingroup\$

Pyth, 25 17 15 14 bytes

<uu++GlN\*k)Qk

Try it online.

Length is taken via STDIN.

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

Python 2, 74 72 66 64 61 Bytes

f=lambda n,i=2:"%d*"%i+f(n,len(`i+2`)-~i)[:n-2]if i<n*2else""

Takes an integer n and outputs a counterstring of length n.

program version, 69 Bytes:

s,n,i="",input(),2
while i<2*n:s+="%d*"%i;i+=len(`i+2`)+1
print s[:n]

Takes an integer n from stdin and prints a counterstring of length n.

Shorter, but only almost working, alternative version:

n,i=input(),2
while i<2*n:print("%d*"%i)[:n-i],;i+=len(str(i+2))+1
\$\endgroup\$
1
\$\begingroup\$

PowerShell v5, 97 bytes

param($n)$l=1;for($i=0;$i-lt$n){$i+="$i*".length;if("$i".Length-gt$l){$i++;$l++};ac .\o "$i*" -n}

Takes input as a command-line argument $n, sets helper $l which we use to keep track of our integer length. Then, we loop from 0 up to $n. Each iteration, we increment $i by the .length of the string formed from $i and an asterisk. Then, if the .length of $i changed (e.g., we moved from 2 digits to 3 digits), we increment both the helper $length variable and $i (to account for the additional digit). We then use the add-content command to append "$i*" to file .\o in the current directory, with -noNewLine.

NB

  • Requires v5, since the -noNewLine parameter was finally added in that version.
  • PowerShell will automatically up-convert from [int] to [double] (no, I don't know why it doesn't go to [long]), so this will properly handle input up to and greater than 2147483648, without problem. Theoretically, it will handle input somewhere up to around 1.79769313486232E+308 (max value of [double]) before complaining, but I expect the disk to fill up before that happens. ;-)
  • Due to the loop conditional checking, this will output to the file a minimum of the input length. For example, for input 10 this will output 2*4*6*8*11*, since 11 is the first $i value greater than the input.

PowerShell v2+, also 97 bytes (non-competing)

param($n)$l=1;-join(&{for($i=0;$i-lt$n){$i+="$i*".length;if("$i".Length-gt$l){$i++;$l++};"$i*"}})

Instead of sending to a file, this encapsulates the loop iterations and then -joins them together into a string. This allows it to work for versions earlier than v5. However, since .NET defines a [string] with a constructor like String(char c,Int32 length), this version does not satisfy the max input requirement, since the output string will overflow and barf.

Also, you may not want to have a ~2GB string floating around in your pipeline. Just sayin'.

\$\endgroup\$
  • \$\begingroup\$ 1.79769313486232E+308 will certainly not work, because adding small numbers to a float won't change the value any more. See stackoverflow.com/questions/12596695/… So my guess it that it stops working once it was "upgraded" to double \$\endgroup\$ – Thomas Weller Aug 24 '16 at 17:57
  • \$\begingroup\$ @ThomasWeller PowerShell [double]s are 64-bit. For example, run for($i=2147483645;$i-lt2147483655;$i++){"$i - " + $i.GetType()} will show a steady progression of $i but the Type changes at 2147483648 to double. I'm sure at some point it'll stop working, likely around ~15 digits of precision or when the .ToString starts using e. The [double]::MaxValue was more of a throwaway joke than a serious upper bound. \$\endgroup\$ – AdmBorkBork Aug 24 '16 at 18:29
1
\$\begingroup\$

Python 3, 126 114 99 bytes

def f(x,s=''):
 i=t=2
 while len(s)<x:i+=len(str(t+i))-len(str(t));s+=str(t)+'*';t+=i
 print(s[:x])

A function that takes input via argument of the character count at which to truncate the string, and prints to STDOUT.

How it works

The difference between the numbers in the string is initially 2. Every time an order of magnitude is passed, this difference is increased by 1; this can be achieved by taking the difference between the number of digits of the current number and the number of digits of the current number added to the difference, which is 1 only when required. The function simply loops while the length of the string is less than the input, appends to the string and updates the difference and number as required, and then truncates before printing.

Try it on Ideone

Infinite output version, 69 bytes

s=i=2
while 1:i+=len(str(s+i))-len(str(s));print(end=str(s)+'*');s+=i
\$\endgroup\$
1
\$\begingroup\$

R, 92 bytes

    N=nchar;f=function(n){z=0;y="";while(z<n){z=z+N(z+N(z)+1)+1;y=paste0(y,z,"*")};strtrim(y,n)}

Example output:

f(103) [1] "2*4*6*8*11*14*17*20*23*26*29*32*35*38*41*44*47*50*53*56*59*62*65*68*71*74*77*80*83*86*89*92*95*98*102*1"

\$\endgroup\$
0
\$\begingroup\$

Jelly, 22 19 18 bytes

2µṾL+®‘¹©=¡=µ³#j”*

Try it online!

Find the first n numbers in the string then join the list with an asterisk. This will always be longer than n which was allowed by OP in the comments.

The program selectively updates the register with the current number in the sequence in the # loop with ¹©=¡. I was hoping this could be shorter, by putting © after the second µ for example, but unfortunately that doesn't work and I couldn't figure out any thing shorter.

\$\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.