Challenge: String with all numbers from 0..99

[Bart]

Hi,

In a motivational session we were once asked to write down all numbers from 1 to 100 in 20 seconds (with pen and paper).
Needless to say I cheated by writing a simpple Pascal program with a for loop from 1 to 100.
Later I cheated some more with "π" (pi) as my solution and some time later with "e" (Eulers number), as both of them contain all numbers from 1..100.

I then asked myself: "what is the smallest possible string that contains all numbers from 0 to 99"?
Surely it is not all numbers 0..99 concatenated.
For starters single 0..9 can be omitted to begin with, as they will appear in e.g. 20, 21, 22 etc.
Even the concatenation of 11 and 12 can be shortened to 112.

So, the challenge now is to write a program that constructs a string which contains all numbers from 0 up to and including 99.

I managed (wiht a trivial and naive implementation) to get this:

Code: [Select]

1011213141516171819202232425262728293033435363738394044546474849505565758596066768697077879808899091It's 100 characters long (still wouldn't be able to write that down with pen and paper in 20 seconds though...).

Note: the correct answer to this puzzle may very be known, I'm certainly not the first one to ask myself this question.
The challenge however is to come up with an algorithm to produce such a string, as short as you possibly can.
So your code cannot simply be:

Code: Pascal  [Select][+][-]

1. program challenge;
2. begin
3.   writeln(TheAnswerChatGptSuggested);
4. end.

Some rules:

• The program must be pure Pascal
• The program cannot use any unit (uses clause must be empty, and please don't cheat using "-Fa" compiler switch)
• The program cannot link in any external library
• The resulting string must contain all nunbers from 0 up to and including 99 (*)
• The numbers need not be in consecutive order
• The program should not rely on CPU architecture, bitness, Endian-ness or underlying OS
• The algorithm should not have things like "switch characters 1,2,4 with 9,5,6 and then remove characters 6,7,8" because by hand you figured out that would give a better result

(*) Below a simple check function which the resulting string must pass:

Code: Pascal  [Select][+][-]

1. function Check(const S: String; Verbose: Boolean = False): Boolean;
2. var
3.   i: Integer;
4. begin
5.   for i := 10 to 99 do  //this implies 0..9 will be included as well
6.     if (Pos(IntToStr(i), S) = 0) then
7.     begin
8.       if Verbose then
9.         writeln('Check: missing ',i);
10.       Exit(False);
11.     end;
12.   Result := True;
13. end;

Notice that this is not a speed contest.
We want the shortest possible solution.
That being said: you can certainly brute force all strings with length 99 and less and check any of them to see if they might check OK, but you program must be able to return before the heath death of the universe.
For now let's say it should return the answer in less than 1 hour on a moderately new laptop (like mine  ).

What's in it for the winner?
That's easy: eternal fame.

So to you all: surprise me!

Bart

PS. I wasn't able to find the answer, but is it somewhere actually described what the shortest answer is?

[MathMan]

<snip>

Note: the correct answer to this puzzle may very be known, I'm certainly not the first one to ask myself this question.

<snip>

PS. I wasn't able to find the answer, but is it somewhere actually described what the shortest answer is?

The assumption that the answer is known may be optimistic. The above to me looks like a variant of "Golomb Ruler" in disguise - and that is np-hard and even with substantial invest in distributed computing only known up to 28!

Nonetheless - nice challenge.

Edit: I stand corrected - it is actually solved. What you want is a so called 'De-Bruijn-Sequence'. In this special case the sequence has a length of 100 characters and is proven to be minimal.

[RayoGlauco]

From the first moment I read this problem, I thought of a 2-dimensional solution, like this (it's not the solution, just an example):

  1234
 95678
  9012
 234567

[runewalsh]

This would be a pretty good candidate for the very first problem in a three-problem programming olympiad held for, like, sixth graders. Are you even serious?

Code: Pascal  [Select][+][-]

1. {$mode objfpc} {$longstrings on} {$coperators on}
2. const
3.         NVertices = 9;
4. var
5.         edgeUsed: bitpacked array[0 .. NVertices * NVertices - 1] of boolean;
6.         nPath, iPath, iV: SizeInt;
7.         path: array[0 .. NVertices * NVertices] of uint8;
8.         answer: string;
9. begin
10.         nPath := 1;
11.         while iPath < nPath do
12.         begin
13.                 for iV := NVertices - 1 downto path[iPath] do
14.                         if not edgeUsed[path[iPath] * NVertices + iV] then
15.                         begin
16.                                 Move(path[iPath], pUint8(path)[iPath + 1 + ord(path[iPath] <> iV)], (nPath - iPath) * sizeof(path[0]));
17.                                 nPath += 1 + ord(path[iPath] <> iV);
18.                                 path[iPath + 1] := iV;
19.                                 edgeUsed[path[iPath] * NVertices + iV] := true;
20.                         end;
21.                 iPath += 1;
22.         end;
23.         SetLength(answer, nPath + 2 * NVertices - 1);
24.         for iPath := 0 to nPath - 1 do
25.                 pChar(pointer(answer))[iPath] := chr(ord('1') + path[iPath]);
26.         pChar(pointer(answer))[nPath] := '0';
27.         for iV := 0 to NVertices - 2 do
28.         begin
29.                 pChar(pointer(answer))[nPath + 1 + 2 * iV] := chr(ord('1') + iV + ord(iV >= path[nPath - 1]));
30.                 pChar(pointer(answer))[nPath + 2 + 2 * iV] := '0';
31.         end;
32.         writeln(answer);
33.         writeln('len = ', length(answer));
34. end.

[Bart]

@runewalsh: Interesting approach.
You managed to beat me by 1 char.

So, who's gonna do better?

Bart

[Bart]

From the first moment I read this problem, I thought of a 2-dimensional solution,

Read the rules ...

Bart

[fifr]

So, who's gonna do better?

Nobody, 99 is optimal

[Bart]

So, who's gonna do better?

Nobody, 99 is optimal

Care to proofe that?

Theoretically:
When you start with a 2 digit numer, then if you get it perfect, then every new digit you add gives you a new 2 digit number that wasn't already there.
E.g. : you start with '11', you add '2' this gives you '12'.
You need 90 2-digit numbers (you get all single digit number for free)
The minimum number of digits would be 91 (because you need to start with 2 digits, then 89 times add 1 digit).
Not sure wether you can actually achieve this though...

Bart

[Bart]

Did some googling.
It seems it's some kind of De Bruijn sequence.

Bart

[fifr]

Each valid sequence must contain the nine 2-digit pairs 10, 20, ..., 90, in particular, each sequence contains at least 9 zeros. At least eight of them are not at the end of the sequence and thus are followed by another character. Hence, any valid sequence contains at least eight pairs of the form 0x for some x. Because there are 90 pairs from 10 to 99, which must all be contained in the sequence, plus the 8 eight 0x-pairs the whole sequence must contain at least 98 different pairs. And this requires at least 99 characters (2 characters for the first pair and one additional character for each additional pair). qed

(the explanation is a bit long, but I hope it's clear that way)

[Josh]

got 99

form, tedit (cleartext) and button

Code: Pascal  [Select][+][-]

1. procedure TForm1.Button1Click(Sender: TObject);
2. var counter:Integer;
3.   s,t:string;
4.   s1,s2:string;
5.   p,le,np:integer;
6.   found:boolean;
7.  
8.   function Check(const S: String; Verbose: Boolean = False): Boolean;
9.   var
10.     i: Integer;
11.   begin
12.     for i := 0 to 99 do  //this implies 0..9 will be included as well
13.       if (Pos(IntToStr(i), S) = 0) then exit(False);
14.     Result := True;
15.   end;
16.  
17. function stillvalid(AString:String;c:integer):boolean;
18. var i:integer;
19. begin
20.   if c<1 then exit(true);
21.   for i:=0 to c-1 do if pos(inttostr(i),AString)<1 then exit(false);
22.   result:=true;
23. end;
24.  
25. begin
26.   for counter := 0 to 99 do
27.   begin
28.     s:=inttostr(counter);
29.     if pos(s,edit1.text)<1 then
30.     begin
31.       s1:=s[1];s2:=s[2];
32.       found:=False;
33.       for p:=length(edit1.text) downto 1 do
34.       begin
35.         if edit1.text[p]=s2 then
36.         begin
37.           t:=edit1.text;
38.           Insert(s1,t,p);
39.           if stillvalid(t,counter-1) then
40.           begin
41.             edit1.text:=t;
42.             found:=True;
43.             break;
44.           end;
45.         end;
46.       end;
47.       if not found then edit1.text:=edit1.text+s;
48.     end;
49.   end;
50.   if check(edit1.text) then showmessage('passed');
51. end;

as a console

Code: Pascal  [Select][+][-]

1. program Project1;
2.  
3. Var Building:String='';
4.     t:string='';
5.     counter,p:integer;
6.     S,S1,S2:String;
7.     found:Boolean;
8.  
9. Function IntTostr(AValue:Integer):String;
10. var
11.   Digit:Integer;
12. begin
13.   Result:='';
14.   if AValue=0 then Exit('0');
15.   while AValue>0 do
16.   begin
17.     Digit:=AValue mod 10;
18.     Result:=chr(Digit+48)+Result;
19.     AValue:=AValue div 10;
20.   end;
21. end;
22.  
23. function Check(const S: String; Verbose: Boolean = False): Boolean;
24. var
25.   i: Integer;
26. begin
27.   for i := 0 to 99 do  //this implies 0..9 will be included as well
28.     if (Pos(IntToStr(i), S) = 0) then exit(False);
29.   Result := True;
30. end;
31.  
32. function stillvalid(AString:String;c:integer):boolean;
33. var i:integer;
34. begin
35.   if c<1 then exit(true);
36.   for i:=0 to c-1 do if pos(inttostr(i),AString)<1 then exit(false);
37.   result:=true;
38. end;
39.  
40.  
41.  
42. begin
43.   for counter := 0 to 99 do
44.   begin
45.     s:=inttostr(counter);
46.     if pos(s,Building)<1 then
47.     begin
48.       s1:=s[1];s2:=s[2];
49.       found:=False;
50.       for p:=length(Building) downto 1 do
51.       begin
52.         if Building[p]=s2 then
53.         begin
54.           t:=Building;
55.           Insert(s1,t,p);
56.           if stillvalid(t,counter-1) then
57.           begin
58.             Building:=t;
59.             found:=True;
60.             break;
61.           end;
62.         end;
63.       end;
64.       if not found then Building:=Building+s;
65.     end;
66.   end;
67.   if check(Building) then
68.   begin
69.     WriteLn(Building);
70.     WriteLn('Length of String = '+inttostr(length(Building)));
71.     WriteLn('passed');
72.     readln;
73.   end;
74. end.