37383940...9394 is a concatenation of all integers from 37 to 94.
From this 116-digit number you are requested to erase 77 digits to leave the biggest number possible.
Please provide both the result and the reasoning to get it.

CLS
FOR i = 37 TO 94
  s$ = s$ + LTRIM$(STR$(i))
NEXT
PRINT s$, LEN(s$)
PRINT : PRINT

s1$ = s$
startPos = 1
goalLen = LEN(s$) - 77
DO
  FOR i = 9 TO 1 STEP -1
    c$ = LTRIM$(STR$(i))
    ix = INSTR(MID$(s1$, startPos), c$)
    IF ix > 0 THEN
      chars = startPos - 1 + LEN(MID$(s1$, startPos)) - (ix - 1)
      IF chars >= goalLen THEN
        expunge$ = MID$(s1$, startPos, ix - 1)
        s1$ = LEFT$(s1$, startPos - 1) + MID$(s1$, startPos + LEN(expunge$))
        PRINT "erase "; expunge$, "leaving "; s1$: PRINT
        startPos = startPos + 1
        EXIT FOR
      END IF
    END IF
  NEXT
LOOP UNTIL LEN(s1$) = goalLen
PRINT s1$

The goal of the program is to retain one more character at a time by erasing up to the highest possible digit so long as that digit is not so far away as to exceed the specified number of erasures.

erase 37383   leaving
94041424344454647484950515253545556575859606162636465666768697071727374757677787
9808182838485868788899091929394

erase 4041424344454647484   leaving
99505152535455565758596061626364656667686970717273747576777879808182838485868788
899091929394

erase 5051525354555657585   leaving
9996061626364656667686970717273747576777879808182838485868788899091929394

erase 6061626364656667686   leaving
999970717273747576777879808182838485868788899091929394

erase         leaving 999970717273747576777879808182838485868788899091929394

erase 0       leaving 99997717273747576777879808182838485868788899091929394

erase 17273747576777        leaving 999977879808182838485868788899091929394

999977879808182838485868788899091929394 is the remaining number.

The only quizzical line being the one that erases nothing, as the next digit, 7 of the number 70, remains in place as any 8's or 9's are too far away to leave enough digits (i.e., we'd have to erase too many).

So at the end of each phase, we have left (built) 9, then 99, 999,9999, 99997, 999977, 9999778...., at which point the erasures have added up to the requisite 77 characters.

Posted by Charlie on 2011-06-27 16:37:01