## Programming/math "puzzle" for you, guys

General FreeBASIC programming questions.
xlucas
Posts: 268
Joined: May 09, 2014 21:19
Location: Argentina

### Programming/math "puzzle" for you, guys

Yesterday night, when I was connecting my house alarm, I was noticing, like many other times, that if one misses the right key when deactivated, it is OK to just keep pressing the rest of the keys. Say my passcode is 4567 and when deactivating, I accidentally pressed 44, I don't need to start over. I can just continue to type 567 and it will be fine, because the last four digits pressed were 4567. Then a question came to my head:

What is the minimum number of keys I have to press so that I have typed all possible passcodes?

If I had to enter passcodes composed of four digits 0 through 9 and I had to press Enter at the end every time, then (not counting the Enter key), I would need 10000 (possible passcodes) times 4 (keys per passcode) total keys to type them all, but since this is continuous, if I start by typing 0000, I can then press 1 and I have already tested both 0000 and 0001, so there must be an order to get the number of typed keys to the minimum.

For programmers:

I have already come up with an algorithm that solved this in 10006 key presses. I won't post it here yet, so that you guys and play and find your own. I still don't know if this is the minimum, but looks like it probably is. I would be very interested to see other ways of solving this and whether there's one better than mine, but even if yours requires somewhat more than 10006 key presses, it'd be nice to see.

For mathematicians and math lovers:

Although I found an algorithm, I still haven't come up with a way to actually prove that this is the minimum. I am quite certain that 10000 is an absolute minimum (not necessarily the actual minimum). If anybody can prove theoretically that this is the minimum (or prove it false), it'd be amazing. Also... what would be the minimum for other number of keys per passcode?

Anyway... just a curiousity I wanted to share with you, guys :)
Tourist Trap
Posts: 2792
Joined: Jun 02, 2015 16:24

### Re: Programming/math "puzzle" for you, guys

xlucas wrote:What is the minimum number of keys I have to press so that I have typed all possible passcodes?

Funny, and quite interesting.

Ok this is my 2 cents first jet with secret codes of length 2..

Code: Select all

`'run over code combinations of the form ab, a=0..9, b=0..9#include "fbgfx.bi"dim as integer  scrW    => 800dim as integer  scrH    => 400screenRes   scrW, scrH, _               'sets the app. screen size            32, _                      'set the color depth to 32bits             2, _                      'set app. screen pages number to 2            fb.GFX_SHAPED_WINDOW   + _      'enables app. standard transparency            fb.GFX_ALPHA_PRIMITIVES   + _      'enables app. standard alpha            fb.GFX_NO_FRAME               'set the window style to no_borderstype P2D    as integer  _x    as integer  _y    as ulong    _colorend type'array to store the tested combinations as points = (comb:=ab,comb:=ab)'with this convention points combinations show as aligned on the diagonaldim as P2D    arrayOfBiComb(any)dim as integer  a   => rnd()*9dim as integer  b   => rnd()*9randomize TIMERdim as integer  loopCounterdo    redim   preserve _             arrayOfBiComb(uBound(arrayOfBiComb) - lBound(arrayOfBiComb) + 1)    arrayOfBiComb(  uBound(arrayOfBiComb) - _                     lBound(arrayOfBiComb)   )._x    = a + 10*b    arrayOfBiComb(  uBound(arrayOfBiComb) - _                     lBound(arrayOfBiComb)   )._y    = a + 10*b    'add to array the current ab combination as a P2D with  some fading    for arrayIndex as integer = lBound(arrayOfBiComb)  to _                                 uBound(arrayOfBiComb)        arrayOfBiComb(arrayIndex)._color    = rgba(250,250,255 - 255/99*arrayIndex, 255 - 255/99*arrayIndex)    next arrayIndex    '    screenSet 1,0    color , rgb(120,180,180)    cls        view    (8,8)-(scrW - 1 - 8, scrH - 1 - 8), _                 rgb(100,100,100), _                 rgb(100,200,200)        ? loopCounter, "::"; a; b        window (-.6,.6)-(99.6,99.6)            for arrayIndex as integer = lBound(arrayOfBiComb)  to _                                         uBound(arrayOfBiComb)                circle  (arrayOfBiComb(arrayIndex)._x,arrayOfBiComb(arrayIndex)._y), _                         .5, _                         arrayOfBiComb(arrayIndex)._color, _                         ,,, f                next arrayIndex        window screen        view screen    flip    '    'set the last b as the new a    a   = b    'choose a new b    b   = rnd()*9    '    loopCounter += 1    '    sleep 150loop until inkey()=chr(27)getKey()'eof`

Why does it crash here with an integer division inside RGBA???

Code: Select all

`'run over code combinations of the form ab, a=0..9, b=0..9#include "fbgfx.bi"dim as integer  scrW    => 800dim as integer  scrH    => 400screenRes   scrW, scrH, _               'sets the app. screen size            32, _                      'set the color depth to 32bits             2, _                      'set app. screen pages number to 2            fb.GFX_SHAPED_WINDOW   + _      'enables app. standard transparency            fb.GFX_ALPHA_PRIMITIVES   + _      'enables app. standard alpha            fb.GFX_NO_FRAME               'set the window style to no_borderstype P2D    as integer  _x    as integer  _y    as ulong    _colorend type'array to store the tested combinations as points = (comb:=ab,comb:=ab)'with this convention points combinations show as aligned on the diagonaldim as P2D    arrayOfBiComb(any)dim as integer  a   => rnd()*9dim as integer  b   => rnd()*9randomize TIMERdim as integer  loopCounterdo    redim   preserve _             arrayOfBiComb(uBound(arrayOfBiComb) - lBound(arrayOfBiComb) + 1)    arrayOfBiComb(  uBound(arrayOfBiComb) - _                     lBound(arrayOfBiComb)   )._x    = a + 10*b    arrayOfBiComb(  uBound(arrayOfBiComb) - _                     lBound(arrayOfBiComb)   )._y    = a + 10*b    'add to array the current ab combination as a P2D with  some fading    for arrayIndex as integer = lBound(arrayOfBiComb)  to _                                 uBound(arrayOfBiComb)                                '********************integer division crashes????    arrayOfBiComb(arrayIndex)._color    = rgba(250,250,255 - 255\99*arrayIndex, 255 - 255/99*arrayIndex)'********************    next arrayIndex    '    screenSet 1,0    color , rgb(120,180,180)    cls        view    (8,8)-(scrW - 1 - 8, scrH - 1 - 8), _                 rgb(100,100,100), _                 rgb(100,200,200)        ? loopCounter, "::"; a; b        window (-.6,.6)-(99.6,99.6)            for arrayIndex as integer = lBound(arrayOfBiComb)  to _                                         uBound(arrayOfBiComb)                circle  (arrayOfBiComb(arrayIndex)._x,arrayOfBiComb(arrayIndex)._y), _                         .5, _                         arrayOfBiComb(arrayIndex)._color, _                         ,,, f                next arrayIndex        window screen        view screen    flip    '    'set the last b as the new a    a   = b    'choose a new b    b   = rnd()*9    '    loopCounter += 1    '    sleep 150loop until inkey()=chr(27)getKey()'eof`
Provoni
Posts: 347
Joined: Jan 05, 2014 12:33
Location: Belgium

### Re: Programming/math "puzzle" for you, guys

One way to solve such problems is to scale them down.

Say we have only 2 digits in base 3 then there are 9 possible combinations:

Code: Select all

`00, 01, 0210, 11, 1220, 21, 22`

Observe that the frequencies of the last and first digits are equal. In other words, 3 combinations start with 0, 3 combinartions end with 0, 3 combinations start with 1, 3 combinations end with 1, etc... As long if this condition is met (scaling upwards) then the minimum number of keys you have to press is equal to (unique combinations + 1) because they can be connected in various ways.

Code: Select all

`0012022110`
Tourist Trap
Posts: 2792
Joined: Jun 02, 2015 16:24

### Re: Programming/math "puzzle" for you, guys

Same idea as Provoni above, just graphically assisted.

Improved version of the last stuff. It stops when all the combinations have been found. Now I need a procedure other than just some random walk!

Code: Select all

`'---------------------------------------------------------'run over code combinations of the form ab, a=0..9, b=0..9'---------------------------------------------------------#include "fbgfx.bi"'screen settingsdim as integer  scrW    => 800dim as integer  scrH    => 400screenRes   scrW, scrH, _               'sets the app. screen size            32, _                      'set the color depth to 32bits             2, _                      'set app. screen pages number to 2            fb.GFX_SHAPED_WINDOW   + _      'enables app. standard transparency            fb.GFX_ALPHA_PRIMITIVES   + _      'enables app. standard alpha            fb.GFX_NO_FRAME               'set the window style to no_borders'some storage for the points we will have to rendertype P2D    as integer  _x    as integer  _y    as ulong    _colorend type'some array to store the tested combinations as points = (comb:=ab,comb:=ab)'->with this convention points combinations show as aligned on the diagonaldim as P2D    arrayOfBiComb(any)'set randomly a first initial combinationdim as integer  a   => rnd()*9dim as integer  b   => rnd()*9'run over a loop until the full set of combinations is covered (or ESC key is pressed)'this means the diagonal should be fully coveredrandomize TIMERdim as integer  loopCounterdo    'add to array the current ab combination as a P2D with some color fading/shift    redim   preserve _             arrayOfBiComb(uBound(arrayOfBiComb) - lBound(arrayOfBiComb) + 1)    arrayOfBiComb(  uBound(arrayOfBiComb) - _                     lBound(arrayOfBiComb)   )._x    = a + 10*b    arrayOfBiComb(  uBound(arrayOfBiComb) - _                     lBound(arrayOfBiComb)   )._y    = a + 10*b    for arrayIndex as integer = lBound(arrayOfBiComb)  to _                                 uBound(arrayOfBiComb)        arrayOfBiComb(arrayIndex)._color    = rgba(250,250,255 - 255/99*arrayIndex, 255 - 255/99*arrayIndex)    next arrayIndex    '    screenSet 1,0    color , rgb(120,180,180)    cls        view    (8,8)-(scrW - 1 - 8, scrH - 1 - 8), _                 rgb(100,100,100), _                 rgb(100,200,200)        ? loopCounter, "::"; a; b        window (-.6,.6)-(99.6,99.6)        '            for arrayIndex as integer = lBound(arrayOfBiComb)  to _                                         uBound(arrayOfBiComb)                circle  (arrayOfBiComb(arrayIndex)._x,arrayOfBiComb(arrayIndex)._y), _                         .5, _                         arrayOfBiComb(arrayIndex)._color, _                         ,,, f            next arrayIndex            '            'test if we have found all the numbers between 00 and 99 (full diagonal)            scope                dim as integer  testArray(99)                for combArrayIndex as integer = lBound(arrayOfBiComb)  to _                                                 uBound(arrayOfBiComb)                    var combinationValue => arrayOfBiComb(combArrayIndex)._x                    testArray(combinationValue) = 1                    var hasSomeMissingValueFound    => FALSE                    for testArrayIndex as integer = 0 to 99                        if testArray(testArrayIndex)=0 then                            hasSomeMissingValueFound = TRUE                            exit for                        end if                    next testArrayIndex                    if not hasSomeMissingValueFound then                        circle  (   arrayOfBiComb( _                                                 uBound(arrayOfBiComb) - _                                                 lBound(arrayOfBiComb)   )._x, _                                     arrayOfBiComb( _                                                 uBound(arrayOfBiComb) - _                                                 lBound(arrayOfBiComb)   )._y    ), _                                 .8, _                                 rgb(250,0,0), _                                 ,,, f                        window screen                        view screen                        flip                        exit do                    end if                next combArrayIndex            end scope        '        window screen        view screen    flip    '    'set the last b as the new a    a   = b    'choose a new b    b   = rnd()*9    '    loopCounter += 1    '    sleep 15loop until inkey()=chr(27)getKey()'eof`
counting_pine
Posts: 6176
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

### Re: Programming/math "puzzle" for you, guys

You can improve your random walk by using int(rnd*10).
Rounding (rnd*9) to the nearest integer will cover the range, but 0 and 9 will be half as likely as the other numbers.

I'd say the theoretical minimum is 10003. That allows for 10000 combinations (because each valid combination needs three extra key presses).
In general, I'd say the *theoretical* minimum is a^b + b-1, for combinations of 'b' key presses and 'a' possible keys.

Provoni's answer reaches the theoretical minimum with 3^2+2-1=10 digits. It doesn't by itself prove that it's possible in the general case, but it seems likely.

This is an interesting problem. I once wanted to generate a block of data that couldn't be compressed (with zlib). To do that reliably I had to produce a string of 65535 bytes, with a fairly uniform distribution, where there was no repeated group of three characters.
An algorithm that solves this would probably have given me what I wanted.
xlucas
Posts: 268
Joined: May 09, 2014 21:19
Location: Argentina

### Re: Programming/math "puzzle" for you, guys

Wow! Thank you, guys! I was beginning to think the puzzle was boring to readers and now I get very interesting answers. I have read, yet not analysed the answers since I'm currently at work, but I will do that later today. In the meantime, I'll share with you what I have been doing on my end.

I first calculated a theoretical minimum of 10000, since each key yields a new combination when pressed (last four pressed). I then quickly saw it had to be 10003, because the first three keys pressed give no passcode. Then I built an algorithm, partly thinking, and partly completing with the first idea that would come to my mind and I was surprised of the good results. This is the code I tried:

Code: Select all

`Dim passcode(0 To 9999) As Byte, buffer As StringDim i As Long, aux As Long, newpass As Long, keyspressed As LongDim passcodes As Longbuffer = "0000"keyspressed = 4Do   aux = ValInt(buffer)   If passcode(aux) = 0 Then passcode(aux) = -1 : passcodes += 1      Locate , 1   Print "Pressed: "; keyspressed; " - Codes: "; passcodes;      If aux = 9999 Then Exit Do      For i = 0 To 9      newpass = 10 * (aux Mod 1000) + i      If passcode(newpass) = 0 Then Exit For   Next i      If i > 9 Then      buffer = Mid(buffer, 2) + "9"   Else      buffer = Mid(buffer, 2) + Trim(Str(i))   End If   keyspressed += 1LoopPrintGetKey`

As you guys can see, this algorithm, which appears risky and which I never expected to be optimal does step on all possible passcodes and results in a wonderful 10006 key presses. I wasn't certain whether an algorithm existed that could beat this one, but then I had the following thinking:

Say we had a string containing all possible combinations that were optimal, with no repetitions. Then each 3-tuple should appear exactly 10 times, because each appears only in 20 passcodes: 10 of the form xABC and 10 of the form ABCx. An optimal string would contain all 3-tuples in the form xABCy. Now, we know this can't be possible since the first three keys, if considered to be ABC don't have a starting x. This leaves us with an extra unpaired 3-tuple, which means if we want to achieve optimisation, we will have to end the string with another ABC to have the remaining xABC somewhere. These extra ABC add three more keys to the total, so the theoretical minimum should now be 10006. If my thinking is correct, this would mean my algorithm is surprisingly optimal! (I didn't build it taking care to make sure it would be optimal).

This would mean the theoretical minimum for n digits should be 10 ^ n + 2 * (n - 1) and this should also work for any other even base. Please don't believe in me too much. I have the feeling that I sould clearer than I am thinking. This is also just a grain of sand. The resolution would be the complete understanding of the problem. I may still be completely wrong. Opinions are welcome :)

@Tourist Trap: I'm not sure exactly why the RGBA crashes but I think of the following: you make a proportion between 255 = 256 - 1 and 99 = 100 - 1, but the difference is not proportional. One is larger to 100 than it is to 256, so the result of the division and multiplication may actually reach or exceed 256. Not completely sure about this, though. I'm still analysing youre code :)

@Provoni: That's almost right, I think. That "+1" should be "+2" because if you started with the figure x, then you will have to necessarily end the sequence with x if you want to optimise, since after having used x as the first digit, the set of the combinations including x contains now an odd number of elements. Also, this +2 = +1 + 1 is a consequence of the number of unpaired digits (at the beginning and end of the sequence), so if you had more digits per passcode, this number should grow in proportion.
Last edited by xlucas on Apr 13, 2017 20:44, edited 1 time in total.
counting_pine
Posts: 6176
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

### Re: Programming/math "puzzle" for you, guys

Unfortunately I can't follow the reasoning in your proof well enough. Partly, I don't understand what x and y represent.
Maybe give it another go at explaining, but also try working through some easier examples.
Trivially, codes of length 1 will always need as many key presses as digits. n^1+(1-1).
With binary codes of length 2, you can see that '00110' would do the job - 5 presses = 2^2+(2-1).
And we've seen ternary codes of length 2 need 10 presses = 3^2+(3-1).
xlucas
Posts: 268
Joined: May 09, 2014 21:19
Location: Argentina

### Re: Programming/math "puzzle" for you, guys

@counting_pine: Note that Provoni's result performs better than mine. The reason, I think, is because he's using an odd base. Odd bases allow for only one end of the string to be incomplete. I'll explain in more detail what I meant. It's hard to be clear... even to myself, ha, ha.
counting_pine
Posts: 6176
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

### Re: Programming/math "puzzle" for you, guys

But Binary is also an even base, although maybe too trivial a case?
It's occurred to me, this problem can reduce to the Traveling Salesman Problem:
Each 4-digit combination can be represented by a "city".
The distance between two cities is 1 if the combinations can be keyed consecutively (e.g. 7123 and 1238 can be keyed consecutively with 71238), or higher if they can't.
The theoretical minimum route will have a total cost of 10000.
The problem is, the general algorithm to solve the TSP is O(n^2*2^n), where n = 10^4 (!)
So you might find that's not the best approach, but it might just about scale up to n=3^3 with a little patience.
xlucas
Posts: 268
Joined: May 09, 2014 21:19
Location: Argentina

### Re: Programming/math "puzzle" for you, guys

Uhmm... I'm seeing that, in general, it's true. There's no need for a trailing copy of the leading n - 1 digits. Your simple example with binary is very good and very useful. I also solved it (manually) for three binary digits and two quaternary digits:

0001011100 (8 + 2 = 10)
30010203112132233 (16 + 1 = 17)

Because of pairing, there is a chance that the same rule does not follow for both even and odd bases, so I'm avoiding odd bases for now. One thing I noticed is that, when you're solving manually, you tend to get stuck if you don't enter the all-same-digit passcodes as soon as possible. That is, you should start with 00 and as soon as you enter a 1, you should enter another 1. This way, it looks like you will always go through all the combinations. Somehow, there doesn't seem to be any need to be careful.

I re-tested my code. I noticed that the three extra digits are caused by the "9s" entered when I can't find a next passcode, that is, my code is "giving up" those three digits. It's not generating a trailing copy of the first ones since, of course, I didn't program it to do it. Then there must be a procedure to go through all passcodes in 10003 steps.
Tourist Trap
Posts: 2792
Joined: Jun 02, 2015 16:24

### Re: Programming/math "puzzle" for you, guys

xlucas wrote:I re-tested my code. I noticed that the three extra digits are caused by the "9s" entered when I can't find a next passcode, that is, my code is "giving up" those three digits. It's not generating a trailing copy of the first ones since, of course, I didn't program it to do it. Then there must be a procedure to go through all passcodes in 10003 steps.

Ok from what I'm understanding, 10003 is obviously the absolute minimum if you generate the 3 incomplete codes at the research start. A, AB, ABC, dont make any valid code. But then ABCD will be an existing 4 digits code. So when you have built your stock of 3 digits, just adding one digit will make a 4 digits code.

Then I've a serious doubt about the possibility to find a simple algorithm that just add a digit to the 3 last digits obtained the most recently, and covers everything in 10000 steps. I don't understand xlucas what your algorithm does. Does it use a comparison with the codes already found or does it just walk in a tricky very clever way so that it's impossible to repeat 2 steps?

From my side I've a little improved the visualizer. Here the last version. I'm still looking at how I could plug your algorithm inside. My algorithm is just a random walk with redundant answers. I still don't know if you really have no redundancy or if you just don't count them. I just don't know for the moment at least.

Code: Select all

`'--------------------------------------------------------'run over code combinations of the form a0a1..an, ai=0..9'--------------------------------------------------------#include once "fbgfx.bi"randomize TIMER'screen settingdim as integer   scrW => anydim as integer   scrH => anyscope   var dskW   => -1   var dskH   => -1   screenControl   fb.GET_DESKTOP_SIZE, _                dskW, _                dskH   '   scrW   = dskW - 2*dskW\32   scrH   = dskH - 2*dskH\8   screenRes   scrW, scrH, _                        'sets application screen dimension            32, _                               'sets application screen color depth            2, _                               'sets application screen page number            fb.GFX_SHAPED_WINDOW   + _               'enables application standard transparency            fb.GFX_ALPHA_PRIMITIVES   + _               'enables application standard alpha            fb.GFX_NO_FRAME                        'sets application borders to noneend scope'structures to hold the informations we want to rendertype COMBINATION   'example: value=3001292091, length=10   declare constructor()   declare constructor(byval CodeLength as integer)   declare operator cast() as string   declare property Value() as integer   declare sub PlugGenerator(byval GeneratorPtr as sub(byval A0 as integer) ptr)   declare sub Generate()   declare sub PrintCombinationStringInfo()   declare sub RenderAsBarPlot()      as integer         _a(any)            'base 0 array: _a(0)=0..9, _a(i)=0..9, .., _a(codeLength - 1)=0..9       as integer         _rankOfGeneration   'the time when this combination has been generated         'address of a generator procedure (taking one argument):      as sub(byval A0 as integer) ptr      _generator   static as integer      frequency(any)      'measure of redundancy   static as integer      codeLength         'the total length of the code   static as integer      generationCounter   'each time a code is generated the counter is incremented   static as fb.IMAGE ptr   renderedImagePtr   'barplot image background   'each time a code is generated, it's stored here below:   static as COMBINATION ptr            arrayOfGeneratedCombinationPtr(any)end type'initialization of static member variables of the COMBINATION objectdim as integer            COMBINATION.frequency(any)dim as integer            COMBINATION.codeLength            => 0dim as integer            COMBINATION.generationCounter      => 0dim as fb.IMAGE ptr         COMBINATION.renderedImagePtr      => 0dim as COMBINATION ptr      COMBINATION.arrayOfGeneratedCombinationPtr(any)'implementation of the properties and methods of the COMBINATION objectconstructor COMBINATION()   'note:   'when a combination is constructed it is not yet generated, generation_rank==-1   'when a combination is generated,    'it keeps its first attributed generation_rank - unless it is reinitialized by the constructor   '   THIS._rankOfGeneration   => -1   '   if COMBINATION.codeLength<1 then      COMBINATION.codeLength   => 1   end if   redim THIS._a(COMBINATION.codeLength - 1)   redim preserve   COMBINATION.frequency(10^COMBINATION.codeLength - 1)end constructorconstructor COMBINATION(byval CodeLengthArg as integer)   THIS._rankOfGeneration   => -1   if CodeLengthArg<1 then      CodeLengthArg = 1   end if   COMBINATION.codeLength   = CodeLengthArg   redim THIS._a(COMBINATION.codeLength - 1)   redim preserve   COMBINATION.frequency(10^COMBINATION.codeLength - 1)end constructoroperator COMBINATION.cast() as string   dim as string   castValue   => ""   for arrayIndex as integer = lBound(THIS._a) to _                         uBound(THIS._a)      castValue   &= str(THIS._a(arrayIndex))   next arrayIndex   '   return castValueend operatorproperty COMBINATION.Value() as integer   dim as integer   returnValue   => -1   dim as integer   sum         => 0   for arrayIndex as integer =   0 to COMBINATION.codeLength - 1      sum   += THIS._a(COMBINATION.codeLength - 1 - arrayIndex)*10^arrayIndex      if arrayIndex=(COMBINATION.codeLength - 1) then         returnValue   = sum      end if   next arrayIndex   '   return returnValueend propertysub COMBINATION.PlugGenerator(byval GeneratorPtr as sub(byval A0 as integer) ptr)   THIS._generator   = GeneratorPtrend subsub COMBINATION.Generate()   if THIS._rankOfGeneration=-1 then      COMBINATION.generationCounter   += 1      THIS._rankOfGeneration         = COMBINATION.generationCounter      redim preserve _       COMBINATION.arrayOfGeneratedCombinationPtr(uBound(COMBINATION.arrayOfGeneratedCombinationPtr) + 1)      COMBINATION.arrayOfGeneratedCombinationPtr(uBound(COMBINATION.arrayOfGeneratedCombinationPtr))   = @THIS   end if   '   if THIS._generator=0 then      if uBound(COMBINATION.arrayOfGeneratedCombinationPtr)>1 then         THIS._a(0)   = _          COMBINATION.arrayOfGeneratedCombinationPtr(uBound(COMBINATION.arrayOfGeneratedCombinationPtr) - 1)-> _          _a(COMBINATION.codeLength - 1)      end if      for arrayIndex as integer = 1 to uBound(THIS._a)         THIS._a(arrayIndex)   = int(rnd()*10)      next arrayIndex   else      cast(sub(byval A0 as integer), THIS._generator) _      (COMBINATION.arrayOfGeneratedCombinationPtr(THIS._rankOfGeneration - 1)->_a(codeLength - 1))   end if   '   COMBINATION.frequency(THIS.Value) += 1end subsub COMBINATION.PrintCombinationStringInfo()   ? THISend subsub COMBINATION.RenderAsBarPlot()   dim as integer   scrW, scrH   screenControl   fb.GET_SCREEN_SIZE, _                scrW, _                scrH   '   view    (10, 10)-(scrW -1 - 10, scrH - 1 - 10), _          rgb(220,220,180), _          rgb(100,100,200)       if COMBINATION.renderedImagePtr<>0 then           put (0,0), COMBINATION.renderedImagePtr, TRANS       end if       imageDestroy   COMBINATION.renderedImagePtr       COMBINATION.renderedImagePtr   = imageCreate(scrW - 20, scrH - 20, rgb(255,0,255), 32)   window    (0,0)-(10^COMBINATION.codeLength - 1, 40)      line   (THIS.Value, 0)-step(1, COMBINATION.frequency(THIS.Value)), _             rgb(180,100,120), _             bf   window screen   view screen    get (10, 10)-(scrW -1 - 10, scrH - 1 - 10), COMBINATION.renderedImagePtr   view    (10, 10)-(scrW -1 - 10, scrH - 1 - 10), _          rgb(220,220,180), _          rgb(100,100,200)      put (0,0), COMBINATION.renderedImagePtr, TRANS   window    (0,0)-(10^COMBINATION.codeLength - 1, 40)       draw string (THIS.Value, 10), str(THIS.Value)   window screen   view screenend sub'-----------------------------------------------------------------------------------------MAINredim as COMBINATION      arrayOfComb(0)arrayOfComb(0)   => COMBINATION(2)         ''change this value to test more lengthy code combinationsarrayOfComb(0).Generate()var hasFoundSomeUnknownCombination   => FALSEdo   screenSet 1, 0      'bug if no graphic procedure is called the console like printing doesn't initiate/perform well      'in absence of screenset/flip we'll need this next instruction      'circle (0,0),6               'uncomment to fix            redim preserve   arrayOfComb(uBound(arrayOfComb) + 1)      arrayOfComb(uBound(arrayOfComb)).Generate()      arrayOfComb(uBound(arrayOfComb)).RenderAsBarPlot()   screenCopy 1, 0   '   'test if the whole combinations have been found   hasFoundSomeUnknownCombination   = FALSE   for frequencyArrayIndex as integer = 0 to uBound(COMBINATION.frequency)      if COMBINATION.frequency(frequencyArrayIndex)=0 then         hasFoundSomeUnknownCombination   = TRUE         exit for      end if   next frequencyArrayIndex   '   sleep 10loop until ( inkey()=chr(27) orElse (not hasFoundSomeUnknownCombination) )'---------------------------------------------------------------------------------------------getKey()'(eof)`

Just some remark about coding here. It's quite difficult to use GET inside a VIEW. Apparently it returns an error message quite radical like "invalid function call" or something like that and crash.

counting_pine wrote:You can improve your random walk by using int(rnd*10).
Rounding (rnd*9) to the nearest integer will cover the range, but 0 and 9 will be half as likely as the other numbers.

Thanks.
D.J.Peters
Posts: 7904
Joined: May 28, 2005 3:28

### Re: Programming/math "puzzle" for you, guys

A question:
if you press 1234 (no enter key)
and then press 5

case A: the result on display is 2345
case B: the display shows 1235
or are the 5' key press are ignored and the display shows the old numbers 1234 ?

In case of A or B the number of minimum needed key presses differs totaly !

Joshy
Tourist Trap
Posts: 2792
Joined: Jun 02, 2015 16:24

### Re: Programming/math "puzzle" for you, guys

D.J.Peters wrote:case A: the result on display is 2345

In this last version, I'm now in the case A, but still with random choice for 5:

Code: Select all

` '--------------------------------------------------------'run over code combinations of the form a0a1..an, ai=0..9'--------------------------------------------------------#include once "fbgfx.bi"randomize TIMER'screen settingdim as integer   scrW => anydim as integer   scrH => anyscope   var dskW   => -1   var dskH   => -1   screenControl   fb.GET_DESKTOP_SIZE, _                dskW, _                dskH   '   scrW   = dskW - 2*dskW\32   scrH   = dskH - 2*dskH\8   screenRes   scrW, scrH, _                        'sets application screen dimension            32, _                               'sets application screen color depth            2, _                               'sets application screen page number            fb.GFX_SHAPED_WINDOW   + _               'enables application standard transparency            fb.GFX_ALPHA_PRIMITIVES   + _               'enables application standard alpha            fb.GFX_NO_FRAME                        'sets application borders to noneend scope'structures to hold the informations we want to rendertype COMBINATION   '[example] value=3001292091, length=10   declare constructor()   declare constructor(byval CodeLength as integer)   declare operator cast() as string   declare property Value() as integer   declare sub PlugGenerator(byval GeneratorPtr as sub(A() as integer) ptr)   declare sub Generate(byval Seed as integer=0)   declare sub PrintCombinationStringInfo()   declare sub RenderAsBarPlot()   'instance variables:      as integer         _a(any)            'base 0 array: _a(0)=0..9, _a(i)=0..9, .., _a(codeLength - 1)=0..9       as integer         _rankOfGeneration   'the time when this combination has been generated      'address of a generator procedure (taking one argument):      as sub(A() as integer) ptr   _generator   'shared variables:   static as integer      frequency(any)      'measure of redundancy   static as integer      codeLength         'the total length of the code   static as integer      generationCounter   'each time a code is generated the counter is incremented   static as fb.IMAGE ptr   renderedImagePtr   'barplot image background   'each time a code is generated, it's stored here below:   static as COMBINATION ptr            arrayOfGeneratedCombinationPtr(any)end type'initialization of static member variables of the COMBINATION objectdim as integer            COMBINATION.frequency(any)dim as integer            COMBINATION.codeLength            => 0dim as integer            COMBINATION.generationCounter      => 0dim as fb.IMAGE ptr         COMBINATION.renderedImagePtr      => 0dim as COMBINATION ptr      COMBINATION.arrayOfGeneratedCombinationPtr(any)'implementation of the properties and methods of the COMBINATION objectconstructor COMBINATION()   'note:   'when a combination is constructed it is not yet generated, generation_rank==-1   'when a combination is generated,    'it keeps its first attributed generation_rank - unless it is reinitialized by the constructor   '   THIS._rankOfGeneration   => -1   '   if COMBINATION.codeLength<1 then      COMBINATION.codeLength   => 1   end if   redim THIS._a(COMBINATION.codeLength - 1)   redim preserve   COMBINATION.frequency(10^COMBINATION.codeLength - 1)end constructorconstructor COMBINATION(byval CodeLengthArg as integer)   THIS._rankOfGeneration   => -1   if CodeLengthArg<1 then      CodeLengthArg = 1   end if   COMBINATION.codeLength   = CodeLengthArg   redim THIS._a(COMBINATION.codeLength - 1)   redim preserve   COMBINATION.frequency(10^COMBINATION.codeLength - 1)end constructoroperator COMBINATION.cast() as string   dim as string   castValue   => ""   for arrayIndex as integer = lBound(THIS._a) to _                         uBound(THIS._a)      castValue   &= str(THIS._a(arrayIndex))   next arrayIndex   '   return castValueend operatorproperty COMBINATION.Value() as integer   dim as integer   returnValue   => -1   dim as integer   sum         => 0   for arrayIndex as integer =   0 to COMBINATION.codeLength - 1      sum   += THIS._a(COMBINATION.codeLength - 1 - arrayIndex)*10^arrayIndex      if arrayIndex=(COMBINATION.codeLength - 1) then         returnValue   = sum      end if   next arrayIndex   '   return returnValueend propertysub COMBINATION.PlugGenerator(byval GeneratorPtr as sub(A() as integer) ptr)   THIS._generator   = GeneratorPtrend subsub COMBINATION.Generate(byval Seed as integer=0)   if THIS._rankOfGeneration=-1 then      COMBINATION.generationCounter   += 1      THIS._rankOfGeneration         = COMBINATION.generationCounter      redim preserve _       COMBINATION.arrayOfGeneratedCombinationPtr(uBound(COMBINATION.arrayOfGeneratedCombinationPtr) + 1)      COMBINATION.arrayOfGeneratedCombinationPtr(uBound(COMBINATION.arrayOfGeneratedCombinationPtr))   = @THIS   end if   '   if THIS._generator=0 then      if uBound(COMBINATION.arrayOfGeneratedCombinationPtr)>1 then         for arrayIndex as integer = 0 to uBound(THIS._a) - 1               THIS._a(arrayIndex)   = _             COMBINATION.arrayOfGeneratedCombinationPtr(uBound(COMBINATION.arrayOfGeneratedCombinationPtr) - 1)-> _             _a(arrayIndex + 1)         next arrayIndex         THIS._a(uBound(THIS._a))   = int(rnd()*10)      else         for arrayIndex as integer = 0 to uBound(THIS._a)            THIS._a(arrayIndex)   = valInt(   _                                     mid(   str(Seed), _                                           uBound(THIS._a) - arrayIndex + 1, _                                           1 _                                           ) _                                    )         next arrayIndex      end if   else      *THIS._generator(COMBINATION.arrayOfGeneratedCombinationPtr(THIS._rankOfGeneration - 1)->_a())   end if   '   COMBINATION.frequency(THIS.Value) += 1end subsub COMBINATION.PrintCombinationStringInfo()   ? THISend subsub COMBINATION.RenderAsBarPlot()   dim as integer   scrW, scrH   screenControl   fb.GET_SCREEN_SIZE, _                scrW, _                scrH   '   view    (10, 10)-(scrW -1 - 10, scrH - 1 - 10), _          rgb(220,220,180), _          rgb(100,100,200)       if COMBINATION.renderedImagePtr<>0 then           put (0,0), COMBINATION.renderedImagePtr, TRANS       end if       imageDestroy   COMBINATION.renderedImagePtr       COMBINATION.renderedImagePtr   = imageCreate(scrW - 20, scrH - 20, rgb(255,0,255), 32)   window    (0,0)-(10^COMBINATION.codeLength - 1, 40)      line   (THIS.Value, 0)-step(1, COMBINATION.frequency(THIS.Value)), _             rgba(180,100,120, 100), _             bf   window screen   view screen    get (10, 10)-(scrW -1 - 10, scrH - 1 - 10), COMBINATION.renderedImagePtr   view    (10, 10)-(scrW -1 - 10, scrH - 1 - 10), _          rgb(220,220,180), _          rgb(100,100,200)      put (0,0), COMBINATION.renderedImagePtr, TRANS   window    (0,0)-(10^COMBINATION.codeLength - 1, 40)       draw string (THIS.Value, 10), str(THIS.Value)   window screen   view screenend sub'-----------------------------------------------------------------------------------------MAINredim as COMBINATION      arrayOfComb(0)arrayOfComb(0)   => COMBINATION(3)      'choose here the length of the codes to play witharrayOfComb(0).Generate()      'this generation meaningless but necessary for some reason                        '(a bad thing in the code, but where?.. )var hasFoundSomeUnknownCombination   => FALSEdo   screenSet 1, 0      redim preserve   arrayOfComb(uBound(arrayOfComb) + 1)      arrayOfComb(uBound(arrayOfComb)).Generate(444)      'here we can choose an initial seed      '      'comment/uncomment one of the 2 instruction lines below to toggle text/graphics         'arrayOfComb(uBound(arrayOfComb)).PrintCombinationStringInfo()         arrayOfComb(uBound(arrayOfComb)).RenderAsBarPlot()   screenCopy 1, 0   '   'test if the whole combinations have been found   hasFoundSomeUnknownCombination   = FALSE   for frequencyArrayIndex as integer = 0 to uBound(COMBINATION.frequency)      if COMBINATION.frequency(frequencyArrayIndex)=0 then         hasFoundSomeUnknownCombination   = TRUE         exit for      end if   next frequencyArrayIndex   '   sleep 10loop until ( inkey()=chr(27) orElse (not hasFoundSomeUnknownCombination) )color ,rgb(200,0,0)? COMBINATION.generationCounterscreenCopy 1, 0'---------------------------------------------------------------------------------------------getKey()'(eof)`

The reason for this visualizer is that a perfect one shot algorithm would be like a simple horizontal line rather than a random barplot or a barplot of any kind. The bar height is the redundancy when a code is typed twice or more.
Provoni
Posts: 347
Joined: Jan 05, 2014 12:33
Location: Belgium

### Re: Programming/math "puzzle" for you, guys

Not sure if this is helpful but this code finds the minimum for 4 base 10 digits almost instantly:

Code: Select all

`screenres 800,600dim as long i,j,k,p,m,odim as long a(9999),d(9999)do   erase a,d   d(0)=1   for i=1 to 9999      p=(a(i-1)mod 1000)*10      for j=0 to 9         k=(j+o)mod 10         if d(p+k)=0 then            d(p+k)=1            a(i)=p+k            o+=int(rnd*10)            exit for         end if         next j   next i   m=0   for i=0 to 9999      if d(i)=0 then m+=1   next iloop until m=0print "minimum found" 'stored in array a(0 to 9999)sleep`
counting_pine
Posts: 6176
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

### Re: Programming/math "puzzle" for you, guys

It works! With randomised trials it usually takes hundreds of goes, which takes about a second on my PC.
I simplified the code slightly by removing the dependency on the 'o' variable, and randomising 'k' directly before the 'j' loop. But the randomisation does seem to be key to getting it working.
I also added a step to verify all the a() values follow on from each other and counted the number of steps it took.

Code: Select all

`randomizedim as long i,j,k,p,mdim as long a(0 to 9999),d(0 to 9999)dim as long n = 0do   n += 1   erase a,d   d(0)=1   for i=1 to 9999      p=(a(i-1)mod 1000)*10      k=int(rnd*10)      for j=0 to 9         if d(p+k)=0 then            d(p+k)=1            a(i)=p+k            exit for         end if            k=(k+1)mod 10      next j   next i   m=0   for i=0 to 9999      if i>0 and (a(i) \ 10) <> (a(i-1) mod 1000) then m += 1      if d(i)=0 then m+=1   next i   'print mloop until m=0printprint n & " tries."print "minimum found" 'stored in array a(0 to 9999)`