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

Postby xlucas » Apr 11, 2017 20:57

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: 2768
Joined: Jun 02, 2015 16:24

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

Postby Tourist Trap » Apr 13, 2017 12:56

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    => 800
dim as integer  scrH    => 400
screenRes   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


type P2D
    as integer  _x
    as integer  _y
    as ulong    _color
end type


'array to store the tested combinations as points = (comb:=ab,comb:=ab)
'with this convention points combinations show as aligned on the diagonal
dim as P2D    arrayOfBiComb(any)


dim as integer  a   => rnd()*9
dim as integer  b   => rnd()*9



randomize TIMER
dim as integer  loopCounter
do
    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 150
loop 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    => 800
dim as integer  scrH    => 400
screenRes   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


type P2D
    as integer  _x
    as integer  _y
    as ulong    _color
end type


'array to store the tested combinations as points = (comb:=ab,comb:=ab)
'with this convention points combinations show as aligned on the diagonal
dim as P2D    arrayOfBiComb(any)


dim as integer  a   => rnd()*9
dim as integer  b   => rnd()*9



randomize TIMER
dim as integer  loopCounter
do
    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 150
loop until inkey()=chr(27)


getKey()
'eof
Provoni
Posts: 346
Joined: Jan 05, 2014 12:33
Location: Belgium

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

Postby Provoni » Apr 13, 2017 14:04

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, 02
10, 11, 12
20, 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: 2768
Joined: Jun 02, 2015 16:24

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

Postby Tourist Trap » Apr 13, 2017 14:38

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 settings
dim as integer  scrW    => 800
dim as integer  scrH    => 400
screenRes   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 render
type P2D
    as integer  _x
    as integer  _y
    as ulong    _color
end type


'some array to store the tested combinations as points = (comb:=ab,comb:=ab)
'->with this convention points combinations show as aligned on the diagonal
dim as P2D    arrayOfBiComb(any)


'set randomly a first initial combination
dim as integer  a   => rnd()*9
dim 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 covered
randomize TIMER
dim as integer  loopCounter
do
    '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 15
loop until inkey()=chr(27)


getKey()
'eof
counting_pine
Site Admin
Posts: 6174
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

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

Postby counting_pine » Apr 13, 2017 19:02

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

Postby xlucas » Apr 13, 2017 20:06

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 String
Dim i As Long, aux As Long, newpass As Long, keyspressed As Long
Dim passcodes As Long

buffer = "0000"
keyspressed = 4

Do
   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 += 1
Loop

Print
GetKey


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
Site Admin
Posts: 6174
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

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

Postby counting_pine » Apr 13, 2017 20:43

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

Postby xlucas » Apr 13, 2017 20:48

@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
Site Admin
Posts: 6174
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

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

Postby counting_pine » Apr 13, 2017 21:05

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

Postby xlucas » Apr 13, 2017 21:46

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: 2768
Joined: Jun 02, 2015 16:24

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

Postby Tourist Trap » Apr 15, 2017 13:24

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 setting
dim as integer   scrW => any
dim as integer   scrH => any
scope
   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 none
end scope


'structures to hold the informations we want to render
type 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 object
dim as integer            COMBINATION.frequency(any)
dim as integer            COMBINATION.codeLength            => 0
dim as integer            COMBINATION.generationCounter      => 0
dim as fb.IMAGE ptr         COMBINATION.renderedImagePtr      => 0
dim as COMBINATION ptr      COMBINATION.arrayOfGeneratedCombinationPtr(any)

'implementation of the properties and methods of the COMBINATION object
constructor 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 constructor
constructor 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 constructor
operator 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 castValue
end operator
property 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 returnValue
end property
sub COMBINATION.PlugGenerator(byval GeneratorPtr as sub(byval A0 as integer) ptr)
   THIS._generator   = GeneratorPtr
end sub
sub 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) += 1
end sub
sub COMBINATION.PrintCombinationStringInfo()
   ? THIS
end sub
sub 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 screen
end sub

'-----------------------------------------------------------------------------------------MAIN


redim as COMBINATION      arrayOfComb(0)
arrayOfComb(0)   => COMBINATION(2)         ''change this value to test more lengthy code combinations
arrayOfComb(0).Generate()

var hasFoundSomeUnknownCombination   => FALSE
do
   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 10
loop 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: 7852
Joined: May 28, 2005 3:28

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

Postby D.J.Peters » Apr 15, 2017 14:34

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: 2768
Joined: Jun 02, 2015 16:24

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

Postby Tourist Trap » Apr 15, 2017 18:00

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 setting
dim as integer   scrW => any
dim as integer   scrH => any
scope
   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 none
end scope


'structures to hold the informations we want to render
type 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 object
dim as integer            COMBINATION.frequency(any)
dim as integer            COMBINATION.codeLength            => 0
dim as integer            COMBINATION.generationCounter      => 0
dim as fb.IMAGE ptr         COMBINATION.renderedImagePtr      => 0
dim as COMBINATION ptr      COMBINATION.arrayOfGeneratedCombinationPtr(any)

'implementation of the properties and methods of the COMBINATION object
constructor 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 constructor
constructor 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 constructor
operator 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 castValue
end operator
property 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 returnValue
end property
sub COMBINATION.PlugGenerator(byval GeneratorPtr as sub(A() as integer) ptr)
   THIS._generator   = GeneratorPtr
end sub
sub 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) += 1
end sub
sub COMBINATION.PrintCombinationStringInfo()
   ? THIS
end sub
sub 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 screen
end sub

'-----------------------------------------------------------------------------------------MAIN
redim as COMBINATION      arrayOfComb(0)
arrayOfComb(0)   => COMBINATION(3)      'choose here the length of the codes to play with
arrayOfComb(0).Generate()      'this generation meaningless but necessary for some reason
                        '(a bad thing in the code, but where?.. )


var hasFoundSomeUnknownCombination   => FALSE
do
   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 10
loop until ( inkey()=chr(27) orElse (not hasFoundSomeUnknownCombination) )


color ,rgb(200,0,0)
? COMBINATION.generationCounter
screenCopy 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: 346
Joined: Jan 05, 2014 12:33
Location: Belgium

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

Postby Provoni » Apr 15, 2017 18:40

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

Code: Select all

screenres 800,600

dim as long i,j,k,p,m,o
dim 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 i
loop until m=0

print "minimum found" 'stored in array a(0 to 9999)

sleep
counting_pine
Site Admin
Posts: 6174
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

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

Postby counting_pine » Apr 15, 2017 20:41

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

randomize
dim as long i,j,k,p,m
dim as long a(0 to 9999),d(0 to 9999)
dim as long n = 0
do
   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 m
loop until m=0

print
print n & " tries."
print "minimum found" 'stored in array a(0 to 9999)

Return to “General”

Who is online

Users browsing this forum: andykmv and 1 guest