Programming/math "puzzle" for you, guys

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

Programming/math "puzzle" for you, guys

Post by xlucas »

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

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

Post by Tourist Trap »

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: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

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

Post by Provoni »

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

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

Post by Tourist Trap »

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: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

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

Post by counting_pine »

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: 334
Joined: May 09, 2014 21:19
Location: Argentina

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

Post by xlucas »

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: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

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

Post by counting_pine »

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: 334
Joined: May 09, 2014 21:19
Location: Argentina

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

Post by xlucas »

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

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

Post by counting_pine »

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: 334
Joined: May 09, 2014 21:19
Location: Argentina

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

Post by xlucas »

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

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

Post by Tourist Trap »

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: 8586
Joined: May 28, 2005 3:28
Contact:

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

Post by D.J.Peters »

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

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

Post by Tourist Trap »

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: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

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

Post by Provoni »

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: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

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

Post by counting_pine »

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)
Post Reply