Programming/math "puzzle" for you, guys
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 :)
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 :)
-
- Posts: 2958
- Joined: Jun 02, 2015 16:24
Re: Programming/math "puzzle" for you, guys
Funny, and quite interesting.xlucas wrote: What is the minimum number of keys I have to press so that I have typed all possible passcodes?
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
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
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:
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.
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
Code: Select all
0012022110
-
- Posts: 2958
- 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!
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
-
- Site Admin
- Posts: 6323
- 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.
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.
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:
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.
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
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.
-
- Site Admin
- Posts: 6323
- 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).
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).
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.
-
- Site Admin
- Posts: 6323
- 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.
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.
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.
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.
-
- Posts: 2958
- Joined: Jun 02, 2015 16:24
Re: Programming/math "puzzle" for you, guys
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.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.
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)
Thanks.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.
-
- Posts: 8586
- Joined: May 28, 2005 3:28
- Contact:
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
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
-
- Posts: 2958
- Joined: Jun 02, 2015 16:24
Re: Programming/math "puzzle" for you, guys
In this last version, I'm now in the case A, but still with random choice for 5:D.J.Peters wrote: case A: the result on display is 2345
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)
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,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
-
- Site Admin
- Posts: 6323
- 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.
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)