Programming/math "puzzle" for you, guys
Re: Programming/math "puzzle" for you, guys
muttonhead.
10000 I think.
What happened to your method, it seemed very goood?
10000 I think.
What happened to your method, it seemed very goood?
-
- Posts: 139
- Joined: May 28, 2009 20:07
Re: Programming/math "puzzle" for you, guys
the detector stops at 10002.... sometimes with patience....
i will prove it... :)....
some code:
ha... work wrong :D
i will prove it... :)....
some code:
Code: Select all
dim as string AllCodes,PressedKeys
dim as integer keycount,runvalue, found(9999)
'Fill a "pool" with all codes
'up ordered pool
'for i as integer=0 to 9999
' AllCodes & = right("000" & i,4)
'next i
'down ordered pool
'for i as integer=9999 to 0 step -1
' AllCodes & = right("000" & i,4)
'next i
do
'random pool
randomize timer
dim as uinteger numbers(9999)
for i as uinteger=0 to 9999
numbers(i)=i
next i
'shakem 10000 times
for i as uinteger=0 to 9999
swap numbers(9999*rnd),numbers(9999*rnd)
next i
AllCodes=""
for i as integer=0 to 9999
AllCodes & = right("000" & numbers(i),4)
next i
'******************************************
'indicator: wich code was found
for i as integer=0 to 9999
found(i)=0
next i
'initial 4 keys
PressedKeys="0000"
keycount=4
found(0)=1
'extract all keys that creates a new code from the pool
for i as integer=2 to len(AllCodes)-3
runvalue=val(mid(AllCodes,i,4))
if found(runvalue)=0 then
found(runvalue)=1
keycount +=1
PressedKeys & = mid(AllCodes,i+3,1)
end if
next i
if len(PressedKeys)<10003 then exit do'<----------------------------------------------!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
loop
dim as integer ff=freefile
open "PressedKeys.txt"for output as ff
print #ff,PressedKeys;
close ff
print PressedKeys
print keycount
print "...saved in file"
print "press key..."
sleep
ha... work wrong :D
Re: Programming/math "puzzle" for you, guys
Fewer than 10003 is clearly impossible. What we've seeing lately is that apparently this minimum is reachable, so the magic number would be 10003.
Why is 10003 the minimum? Because the first three keys you press will yield no code. So, the minimum would be one that gave one code for every other key. Since there are 10000 codes, this means 10003 is an absolute minimum. No question about this. Now... the guys have been showing that the codes themselves can always be sorted so that they share 3 digits with the neighbouring code all the time. If we are right, then no matter what base (usually 10) and how many digits/symbols you use, you can always reach the minimum of base ^ digits + digits - 1 (i.e.: 10003 in this case).
Why is 10003 the minimum? Because the first three keys you press will yield no code. So, the minimum would be one that gave one code for every other key. Since there are 10000 codes, this means 10003 is an absolute minimum. No question about this. Now... the guys have been showing that the codes themselves can always be sorted so that they share 3 digits with the neighbouring code all the time. If we are right, then no matter what base (usually 10) and how many digits/symbols you use, you can always reach the minimum of base ^ digits + digits - 1 (i.e.: 10003 in this case).
Re: Programming/math "puzzle" for you, guys
I had not considered the first three digits.
So 1003 would be the minimum.
Just for a last (on my part) look at this, if there were three code digits, A to Z choice, this would be equivalent to number base 25.
But this stuff really has nothing to do with number bases, it is simply permutation driven.(IMHO)
With three digits, A to Z, 17576 options exist (compared to the previous 10000).
So it takes 15 seconds to sieve the combinations out.
So 1003 would be the minimum.
Just for a last (on my part) look at this, if there were three code digits, A to Z choice, this would be equivalent to number base 25.
But this stuff really has nothing to do with number bases, it is simply permutation driven.(IMHO)
With three digits, A to Z, 17576 options exist (compared to the previous 10000).
So it takes 15 seconds to sieve the combinations out.
Code: Select all
Sub QuickSort(array() As string,begin As long,Finish As long)
Dim As long i=begin,j=finish
Dim As string x =array(((I+J)\2))
While I <= J
While array(I) < X
I+=1
Wend
While array(J) > X
J-=1
Wend
If I<=J Then
Swap array(I),array(J)
I+=1
J-=1
End If
Wend
If J > begin Then QuickSort(array(),begin,J)
If I < Finish Then QuickSort(array(),I,Finish)
End Sub
Sub inc(s As String)
Dim As Integer counts
Var ls=Len(s)
Do
If s[ls-counts-1]=57 Then
counts=counts+1
If counts=ls Then s="1"+String(ls,"0"):Exit Do
Else
s=Left(s,ls-counts-1)+Str(s[ls-counts-1]-47)+String(counts,"0")
Exit Do
End If
Loop
End Sub
function seive(a() as string,s as string,res() as string) as string
static as long idx
idx+=1
for n as long =0 to 17575
if a(n)<>"a" then
if mid(a(n),1,2)=s then
res(idx-1)=a(n)
function= a(n)
a(n)="a"
exit function
end if
end if
next n
print "OUT"
end function
dim as string a(17575)
dim as long ctr=-1
for n1 as long=65 to 90
for n2 as long=65 to 90
for n3 as long=65 to 90
ctr+=1
a(ctr)=chr(n1,n2,n3)
next
next
next
dim as string res(17575)
print "Please wait about 15 seconds"
var st=mid(a(17575),2,2),t=""
for n as long=0 to 17575
t= seive(a(),st,res())
st=mid(t,2,2)
next n
for n as long=0 to 17575
print res(n);" ";
next
print
print "Press a key to see the pressed digits"
sleep
dim as string p
for n as long=0 to 17575
p+=right(res(n),1)
next
print
print "presses"
print p
print "press a key to verify all three digit codes"
sleep
print
print
print "___________________________"
quicksort(res(),0,17575)
for n as long=0 to 17575
print res(n);" ";
if n <17575 then
If res(n)>=res(n+1) then print "ERROR",n,res(n):sleep
end if
next
sleep
-
- Site Admin
- Posts: 6323
- Joined: Jul 05, 2005 17:32
- Location: Manchester, Lancs
Re: Programming/math "puzzle" for you, guys
While that's true, what I've tended to see in people's code is that it's counted in combinations, not key presses.xlucas wrote:Fewer than 10003 is clearly impossible.
So then the goal becomes to find exactly 10000 unique combinations, where each pair of consecutive combinations share the middle three digits, rather than finding 10003 key presses that include all combinations.
Re: Programming/math "puzzle" for you, guys
Dodicat: That would be a base 26 code, actually, but the number of combinations you give is correct. Looks like it's possible to concatenate them all too! So the number of key presses would be (26 ^ 3) + 3 - 1 = 17576 + 2 = 17578. Optimal result :) I would like you and the guys to note that your algorithm always ends up producing a chain of codes in which the first one starts with the same n - 1 symbols as the last one ends. I had said earlier I expected this had to be the case if the chain was to be optimal and it looks like at least at that, I was right. It's the concept of code pairing I mentioned very early in the thread and then abandoned until now.
Counting_Pine: I think you're right. At the beginning, my question was which was the minimum number of key presses, but as it becomes clearer and clearer that an optimal result is always possible, then the actual problem has become to demonstrate that it always is, that is, that one can always concatenate all combinations without extra symbols. Even after all my analysis and that of everybody else, I still don't feel this has been "demonstrated", but the conjecture has escalated to a level of certainty that's too high to just try to find exceptions.
A curiousity: when I spent a year in New Zealand, I discovered, to my great surprise, that native English speakers don't usually know the words "truncate" and "concatenate". Of course, a programmer is always more likely to know these words, but in Spanish, the corresponding words "truncar" and "concatenar" are a lot more used by common people... especially the first one. Just came to my mind when I used the word in the last paragraph. If anybody has something to say about that topic, we should create a new thread about it, ha, ha, or you can just PM me.
Counting_Pine: I think you're right. At the beginning, my question was which was the minimum number of key presses, but as it becomes clearer and clearer that an optimal result is always possible, then the actual problem has become to demonstrate that it always is, that is, that one can always concatenate all combinations without extra symbols. Even after all my analysis and that of everybody else, I still don't feel this has been "demonstrated", but the conjecture has escalated to a level of certainty that's too high to just try to find exceptions.
A curiousity: when I spent a year in New Zealand, I discovered, to my great surprise, that native English speakers don't usually know the words "truncate" and "concatenate". Of course, a programmer is always more likely to know these words, but in Spanish, the corresponding words "truncar" and "concatenar" are a lot more used by common people... especially the first one. Just came to my mind when I used the word in the last paragraph. If anybody has something to say about that topic, we should create a new thread about it, ha, ha, or you can just PM me.
I solved it! :D
I think I've solved the puzzle! -- That is, I have a rigorous mathematical proof... apparently. What I have found is that it is always possible to concatenate all codes in a way that adds only one digit per code, for any number of digits per code, as long as the base is even. If one is not careful, one may get stuck, but a simple pattern is followed, the solution is always found.
Proof for even bases:
- Let n be the number of digits per code and b the base (number of possible symbols per digit) with b even. When giving examples, I will assume n = 4 and b = 10, the original values.
- For n = 1, the solution is trivial. There is no overlap, but still only one digit per code is used and the solution exists for every base.
- For n > 1, there is an overlap of length n - 1. In our case, every code pair will overlap at 3 digits. These triplets may result in two cases: if the three digits are not all equal, then there exist 20 codes containing that substring (10 starting with it and 10 ending with it). For example, the substring 123 is found in 20 codes of 4 digits: the codes 0123 through 9123 and the codes 1230 through 1239. If the triplet contains all identical difits, then there are 19 codes containing that triplet. Say the triplet is 000, then 0000 both starts and ends in 000, so it's its own pair in the set. Therefore, for these triplets, the number of codes containing them is odd. It's easy to see how this same reasoning on overlaps extends to all possible values of n greater than 1 and to all even values of b. For odd values, it appears like odd and even cases would get switched, but I haven't yet verified this.
- Note that only codes that have all digits identical can start and end with the same substring of n - 1 digits, since if the digits are a1, a2, a3, ... an, then we have a1 = a2, a2 = a3, a3 = a4, ...., a(n-1) = an and therefore a1 = a2 = a3 = ... = an.
- So now comes the thing. Suppose you start the string with a first code having its digits not all the same. Then you start adding one digit at a time. Each time you add a digit, you have to look for a number starting with the same three digits as the last one ended. The question is, is it possible to ever get stuck? If you do get stuck, why would that be? Well, getting stuck at a code ABCD means that there are no remaining codes starting in BCD. If B, C and D are not all equal, then all the 2 x b codes containing them have been issued, but if we started with any triplet other than BCD, this is not possible, since 2 x b is even, so every time a code of the form xBCD is entered, it must have been followed by one of the form BCDy. So you will never get stuck this way. This leaves only two ways of getting stuck: either B, C and D are all equal or the string starts with BCD.
- If the string did not start with BCD, then B=C=D. But this could have been avoided by making sure that, for one of the pairs xBBB and BBBy, you placed the code BBBB in between them like this: xBBBBy. So the first time you get to a code ending in n - 1 equal digits, the code made out of n equal digits like that one must be pushed in, if it has not yet been pushed. This way, you can no longer get stuck in this fashion.
- Now say B, C and D are not equal, but the string started with BCD. You could have avoided this by just leaving the last code ending in BCD to be the last in the string.
- Finally, there is the case in which the string started with BCD and B=C=D. We can avoid this by simply never starting the string with three equal digits.
- It's easy to see that all these step are valid for all n > 1 and for all b even.
Proof for even bases:
- Let n be the number of digits per code and b the base (number of possible symbols per digit) with b even. When giving examples, I will assume n = 4 and b = 10, the original values.
- For n = 1, the solution is trivial. There is no overlap, but still only one digit per code is used and the solution exists for every base.
- For n > 1, there is an overlap of length n - 1. In our case, every code pair will overlap at 3 digits. These triplets may result in two cases: if the three digits are not all equal, then there exist 20 codes containing that substring (10 starting with it and 10 ending with it). For example, the substring 123 is found in 20 codes of 4 digits: the codes 0123 through 9123 and the codes 1230 through 1239. If the triplet contains all identical difits, then there are 19 codes containing that triplet. Say the triplet is 000, then 0000 both starts and ends in 000, so it's its own pair in the set. Therefore, for these triplets, the number of codes containing them is odd. It's easy to see how this same reasoning on overlaps extends to all possible values of n greater than 1 and to all even values of b. For odd values, it appears like odd and even cases would get switched, but I haven't yet verified this.
- Note that only codes that have all digits identical can start and end with the same substring of n - 1 digits, since if the digits are a1, a2, a3, ... an, then we have a1 = a2, a2 = a3, a3 = a4, ...., a(n-1) = an and therefore a1 = a2 = a3 = ... = an.
- So now comes the thing. Suppose you start the string with a first code having its digits not all the same. Then you start adding one digit at a time. Each time you add a digit, you have to look for a number starting with the same three digits as the last one ended. The question is, is it possible to ever get stuck? If you do get stuck, why would that be? Well, getting stuck at a code ABCD means that there are no remaining codes starting in BCD. If B, C and D are not all equal, then all the 2 x b codes containing them have been issued, but if we started with any triplet other than BCD, this is not possible, since 2 x b is even, so every time a code of the form xBCD is entered, it must have been followed by one of the form BCDy. So you will never get stuck this way. This leaves only two ways of getting stuck: either B, C and D are all equal or the string starts with BCD.
- If the string did not start with BCD, then B=C=D. But this could have been avoided by making sure that, for one of the pairs xBBB and BBBy, you placed the code BBBB in between them like this: xBBBBy. So the first time you get to a code ending in n - 1 equal digits, the code made out of n equal digits like that one must be pushed in, if it has not yet been pushed. This way, you can no longer get stuck in this fashion.
- Now say B, C and D are not equal, but the string started with BCD. You could have avoided this by just leaving the last code ending in BCD to be the last in the string.
- Finally, there is the case in which the string started with BCD and B=C=D. We can avoid this by simply never starting the string with three equal digits.
- It's easy to see that all these step are valid for all n > 1 and for all b even.
-
- Posts: 139
- Joined: May 28, 2009 20:07
Re: Programming/math "puzzle" for you, guys
What does this mean? You will (or must) get stuck if you start with 000,111 ... 999?- Finally, there is the case in which the string started with BCD and B=C=D. We can avoid this by simply never starting the string with three equal digits.
Have you checked this?
Mutton
-
- Site Admin
- Posts: 6323
- Joined: Jul 05, 2005 17:32
- Location: Manchester, Lancs
Re: Programming/math "puzzle" for you, guys
I think it means the above proof doesn't show it to be necessarily possible (or impossible).Muttonhead wrote:What does this mean? You will (or must) get stuck if you start with 000,111 ... 999?- Finally, there is the case in which the string started with BCD and B=C=D. We can avoid this by simply never starting the string with three equal digits.
It doesn't mean it's impossible in all cases, since the sequence "00110" works for binary codes of length 2.
If we can validate the proof, it would be interesting to see if we can progress from there to an algorithm that can deterministically solve the problem.
-
- Posts: 139
- Joined: May 28, 2009 20:07
Re: Programming/math "puzzle" for you, guys
I think I have understood what you said, not quite sure :)I think it means the above proof doesn't show it to be necessarily possible (or impossible).
this little zip contains 10 files, 10003 bytes long and the code inside starts with 000,111....999
http://www.muttonhead.homepage.t-online ... dcodes.zip
this little proggy check the number of combined codes inside:
Code: Select all
#INCLUDE "file.bi"
dim as string*1 char
dim as string combined,filename
dim as uinteger codes(9999),initial,val_code,val_single,count,ff,clen
'FileLoader
filename="Codes\444"
clen=filelen(filename)
ff=freefile
open filename for binary as ff
for i as integer=1 to clen
get #ff,,char
combined &=char
next i
close ff
print clen
'detect all combined codes*************************************************************
'reset indicator
for i as integer=0 to 9999
codes(i)=0
next i
count=0
for i as integer=1 to clen-3
val_code=val( mid(combined,i,4) )
if codes(val_code)=0 then
count +=1
print right("000" & val_code,4) & " ";
codes(val_code)=1
end if
next i
print
print count & " chained codes found"
sleep
Code: Select all
#INCLUDE "file.bi"
dim as string*1 char
dim as string combined,filename
dim as uinteger clen,diff(18),a,b,ff
'FileLoader
filename="Codes\999"
clen=filelen(filename)
ff=freefile
open filename for binary as ff
for i as integer=1 to clen
get #ff,,char
combined &=char
next i
close ff
'detect all combined codes*************************************************************
for i as integer=2 to clen
a=val(mid(combined,i-1,1))
b=val(mid(combined,i,1))
diff(a-b+9) +=1
locate (1,1)
for k as integer=9 to -9 step -1
print k & ": " & diff(k+9)
next k
next i
sleep
Code: Select all
9: 100
8: 200
7: 300
6: 400
5: 500
4: 600
3: 700
2: 800
1: 900
0: 1002
-1: 900
-2: 800
-3: 700
-4: 600
-5: 500
-6: 400
-7: 300
-8: 200
-9: 100
Mutton
Re: Programming/math "puzzle" for you, guys
Hi, guys! Yes, what I meant is that, if you start the string with n equal digits, even if you respect the other rules, the chance still exists that you get stuck, depending on how you chose the next numbers, whereas if you never start the string like that, you're guaranteed that you won't get stuck. I've also been thinking and I concluded that this same proof works also for odd bases. There is one thing I had forgotten, though. When you have two digits per code, the substrings are one digit long, so they always contain "all equal digits", meaning you can't help starting with a substring of this type. We know by testing that this works anyway for base 10 and n = 2, but this proof wouldn't be enough to prove for other bases, because of that (or maybe it would... not sure). Anyway, I'm quite confident that this works for all bases.
Mutton: That is indeed very interesting. I wouldn't have thought of measuring that. I think it makes sense that the results are so round because, when we give restrictions on how to sort numbers that would otherwise be random, what we are doing is sorting them. Besides, because we are going through all codes, eventually, cumulate comparisons should get normalised. That is, I'm not surprised that they are all multiples of 100 (except for 0, which I believe may have to do with the fact that the first code was probably 0000; try starting with 1111 and I guess this will change), but I'm more surprised about how some digits get say, 800, while others get 100. My thinking tells me that this must have to do with the procedure you're using to pick them when you create the string. There is a large number of possible valid strings (which would be interesting to calculate and demonstrate too) and my guess is that the cumulative differences would change depending on which of these valid strings you picked. Furthermore, if you add the differences from all possible valid strings, my guess is all digits would get exactly the same cumulative difference (a very large one... or zero if you allow sign).
To illustrate why I expect these things to happen, I'll give you a very human example. There's a Spanish cards game called Escoba ("The Sweeper"), in which each player is given three cards and four extra cards are placed face-up on the table. Card values go from 1 to 10, with four suites. On each round, each player must try to add 15 using one of his cards and one or more of the cards on the table. If such thing were not possible, the player must throw any of his cards, adding it to the table. When all players run out of cards, three more are given to each until the deck is empty. The interesting thing is that, at the end of the game, on the table always remains a sum of the form 10 + 15 * k with k an integer equal or greater than 0. The maximum sum possible is 55, so the possible values are: 10, 25, 40 and 55. This is completely independent on how lucky the players were or how well they played. Also, if you are the one giving the cards, you play last. If at the end, you kept a 10 as your last card, the person before you almost invariably will take the whole table. Players often use this to predict what will happen at the end of the game and make it profitable for them.
Mutton: That is indeed very interesting. I wouldn't have thought of measuring that. I think it makes sense that the results are so round because, when we give restrictions on how to sort numbers that would otherwise be random, what we are doing is sorting them. Besides, because we are going through all codes, eventually, cumulate comparisons should get normalised. That is, I'm not surprised that they are all multiples of 100 (except for 0, which I believe may have to do with the fact that the first code was probably 0000; try starting with 1111 and I guess this will change), but I'm more surprised about how some digits get say, 800, while others get 100. My thinking tells me that this must have to do with the procedure you're using to pick them when you create the string. There is a large number of possible valid strings (which would be interesting to calculate and demonstrate too) and my guess is that the cumulative differences would change depending on which of these valid strings you picked. Furthermore, if you add the differences from all possible valid strings, my guess is all digits would get exactly the same cumulative difference (a very large one... or zero if you allow sign).
To illustrate why I expect these things to happen, I'll give you a very human example. There's a Spanish cards game called Escoba ("The Sweeper"), in which each player is given three cards and four extra cards are placed face-up on the table. Card values go from 1 to 10, with four suites. On each round, each player must try to add 15 using one of his cards and one or more of the cards on the table. If such thing were not possible, the player must throw any of his cards, adding it to the table. When all players run out of cards, three more are given to each until the deck is empty. The interesting thing is that, at the end of the game, on the table always remains a sum of the form 10 + 15 * k with k an integer equal or greater than 0. The maximum sum possible is 55, so the possible values are: 10, 25, 40 and 55. This is completely independent on how lucky the players were or how well they played. Also, if you are the one giving the cards, you play last. If at the end, you kept a 10 as your last card, the person before you almost invariably will take the whole table. Players often use this to predict what will happen at the end of the game and make it profitable for them.
-
- Posts: 139
- Joined: May 28, 2009 20:07
Re: Programming/math "puzzle" for you, guys
Ok, for the archive whas an adapted version necessary.My thinking tells me that this must have to do with the procedure you're using to pick them when you create the string. There is a large number of possible valid strings (which would be interesting to calculate and demonstrate too) and my guess is that the cumulative differences would change depending on which of these valid strings you picked. Furthermore, if you add the differences from all possible valid strings, my guess is all digits would get exactly the same cumulative difference (a very large one... or zero if you allow sign).
Here is my "random brute force" method!
At first, it creates a random sequence of all codes that can be generated.
By the way: four times longer (a 4 digit long code !!!) than the combined string to be produced later!
The rest is simply a hopefully successful "merge of BCD plus x"
:)
If the method was successful, and it is relatively rare, the result is saved.
Please check if the same statistic also occurs on successful randomly generated combined code strings:
Code: Select all
dim as string combined,str_code,str_leftcode,str_rightcode,filename
dim as uinteger codes(9999),found(9999),val_code,count,ff,init,x
randomize timer
do
'create an array with all codes in a random order*******************************
'reset indicator
for i as integer=0 to 9999
found(i)=0
next i
for i as integer=0 to 9999
do
x=0
val_code=rnd*10000
if found(val_code)=0 then
codes(i)=val_code
found(val_code)=1
x=1
end if
loop until x=1
next i
'create a combined string**************************************************************
'reset indicator
for i as integer=0 to 9999
found(i)=0
next i
combined=right("00" & codes(9999),3)
for i as integer=0 to 9999
str_code=right("000" & codes(i),4)
str_leftcode=right(combined,3)
for k as integer=1 to 4
str_rightcode=mid(str_code,k,1)
val_code=val(str_leftcode & str_rightcode)
if found(val_code)=0 then
combined &=str_rightcode
str_leftcode=right(combined,3)
found(val_code)=1
end if
next k
next i
'detect all combined codes*************************************************************
'reset indicator
for i as integer=0 to 9999
found(i)=0
next i
count=0
for i as integer=1 to len(combined)-3
val_code=val( mid(combined,i,4) )
if found(val_code)=0 then
count +=1
found(val_code)=1
end if
next i
print ".";
if count>9999 then
'filename=left(combined,3) & ".bas"
filename=time & ".bas"'.bas faster displayed in Filerequester of IDE :)
mid(filename,3,1)="_"
mid(filename,6,1)="_"
'filename="Codes\" & filename
ff=freefile
open filename for output as ff
print #ff,combined;
close ff
print
print count & " codes found in >combined<"
end if
loop until inkey<>""
Re: Programming/math "puzzle" for you, guys
In my computer, it takes forever. From time to time, it displays that it's found 10000 codes and keeps on trying to build the string. I can make it run faster if I use graphics mode. In GNU/Linux, the console is very powerful, but a lot slower than in Windows, so normally, I only use the console if I'm making a program I want to run that way.
If my proof were perfect, a random look shouldn't be necessary. One would just follow the instructions and voilà, but you can't see this is not so. I've made a mistake. You can't just reserve a code ending in the same three digits as the first one to be the last, because that same code is one of the 10 codes that starts with a certain different triplet. I'm trying to get that fixed.
This code should work if my proof were right:
But as you see, if stops somewhere always. If you change the starting 3 digits, the string will get longer or shorter, but I haven't found a starting code that leads to completing the string and the process always breaks at a point where a code is required of the same three digits as at the beginning. If you uncomment the line that reserves one of the codes, you'll see that the process still breaks somewhere much earlier than at the end.
My code is attempting to just chain the codes as necessary without any random action, just following the rules, but these rules are clearly not enough.
If my proof were perfect, a random look shouldn't be necessary. One would just follow the instructions and voilà, but you can't see this is not so. I've made a mistake. You can't just reserve a code ending in the same three digits as the first one to be the last, because that same code is one of the 10 codes that starts with a certain different triplet. I'm trying to get that fixed.
This code should work if my proof were right:
Code: Select all
Dim code(0 To 9999) As Byte
Dim starter As Byte = 19, total_left As Long = 10000
Dim s As String, i As Long, v As Long
Dim temp As String
'It looks like I made a mistake in my proof. If I reserve the
'last code ending in the same triplet as the string started so
'that it becomes the last one, I'm also reserving one of the
'codes begining in a certain other triplet, which leads to
'the process getting stuck most of the time. It's funny how it
'always gets stuck at the starting code, though.
s = "832" 'Start with a random triple of non-all-equals
Print
Print s;
'Uncomment to reserve one of the codes for the end
'code(1832) = -1
Do
For i = 0 To 9
'Try adding each digit 0 through 9 after the last 3 digits
'and see if the code is still available
v = ValInt(Right(s, 3) + Trim(Str(i)))
If code(v) = 0 Then
'If it is, mark it us unavailable and add the last digit
'to the string, also decrementing the amount of codes left
code(v) = -1
total_left -= 1
s &= Str(i)
Print Str(i);
Exit For
End If
Next i
'The For loop was completed and none of the 10 codes is available
'We've got stuck!
If i > 9 Then
Print
Print "No more codes of that type"
Print "Ending with "; total_left; " codes left"
Print
Exit Do
End If
Loop Until total_left = 0
My code is attempting to just chain the codes as necessary without any random action, just following the rules, but these rules are clearly not enough.
Re: Programming/math "puzzle" for you, guys
Re starting values.
At first I thought this problem was symbol based.
The house alarm values could be smileys/stars/letters whatever ...
Any starting symbols for your puzzle would initiate the process of matching and finding another permutation until all were found.
But this seems not to be the case.
There is an underlying number base system here.
for base 10, 4 digit code the starter must be (something)+999
For base 16, 4 digit code the starter must be (something)+FFF
Here are base change options and digit number options.
I have written down the possible starter digits to ensure completion in a run.-- line 85
lines 61/67 for the base options.
(large number bases with 4 digits are slow)
An actual proof, IMHO , would still use permutations or perhaps more complex groups.
My previous permutations proof was too simple and missing something.
I suggest not using option -exx (I have already tested). It slows everything down.
@muttonhead- I shall download and try your method later.
At first I thought this problem was symbol based.
The house alarm values could be smileys/stars/letters whatever ...
Any starting symbols for your puzzle would initiate the process of matching and finding another permutation until all were found.
But this seems not to be the case.
There is an underlying number base system here.
for base 10, 4 digit code the starter must be (something)+999
For base 16, 4 digit code the starter must be (something)+FFF
Here are base change options and digit number options.
I have written down the possible starter digits to ensure completion in a run.-- line 85
lines 61/67 for the base options.
(large number bases with 4 digits are slow)
Code: Select all
#include "crt.bi"
width 100,10000 'not required win 10
dim shared as long limit
redim shared as string a(),res()
dim shared as long lefta(),righta()
dim shared as long idx,dd
'from a decimal long to a string base _base
function ULongToBase(N as ulong,_base as byte) as string
dim as zstring * 50 buffer
_itoa(n,@buffer,_base)
return ucase(buffer)
end function
'from as string base _base to a decimal long
function ULongFromBase(N as string,_base as byte) as ulong
return strtoul(n,0,_base)
end function
Sub QuickSort(array() As string,begin As long,Finish As long)
Dim As long i=begin,j=finish
Dim As string x =array(((I+J)\2))
While I <= J
While array(I) < X
I+=1
Wend
While array(J) > X
J-=1
Wend
If I<=J Then
Swap array(I),array(J)
I+=1
J-=1
End If
Wend
If J > begin Then QuickSort(array(),begin,J)
If I < Finish Then QuickSort(array(),I,Finish)
End Sub
function seive(rightavalue as long) as long
idx+=1
for n as long =0 to limit
if lefta(n)<>-1 then
if lefta(n)=rightavalue then 'compare valint values
res(idx-1)=a(n) 'build the answer array
lefta(n)=-1
return n 'return the array index
end if
end if
next n
return -1 'no match found
end function
'===========
'===========
dim as long b =16 'number base
dim as long digits=4'code length
limit=b^(digits)-1
dd=digits-1
'===========
'===========
redim a(limit) 'string
redim lefta(limit)'long
redim righta(limit)'long
redim res(limit)'string
print "creating digits"
for n as long=0 to limit 'create all the three digit codes +left and right integers
a(n)= right(string(digits,"0")+ULongToBase(n,b),digits)
lefta(n) =ULongFromBase(left(a(n),dd),b)
righta(n)=ULongFromBase(right(a(n),dd),b)
next
dim as string start=a(limit) ' or a(limit-b^(digits-1)) , a(limit-2*b^(digits-1)) .... a(limit-(b-1)*b^(digits-1))
print "Number base = ";b
print "Digit number = ";digits
print "Presses expected ";limit+1
print "Starting at ";start
print "Please wait a few seconds"
dim as long startval=ULongFromBase(right(start,dd),b) 'start integer
print
dim as long v
'NOTE: loop closes when choices are exhausted.
do
v= seive(startval)
if v=-1 then exit do
startval=righta(v)
loop
dim as string show
for n as long=0 to limit
show+=res(n)+" "
if n<limit then
if right(res(n),dd)<>left(res(n+1),dd) then print "ERROR AT",right(res(n),dd);" Press a key":sleep
end if
next
print show
print
print "Press a key to see the pressed digits"
sleep
dim as string p 'presses
for n as long=0 to limit
p+=right(res(n),1)
next
print
print "presses"
print p
print len(p);" in total";" (should be ";limit+1;")"
print "press a key to verify all "; digits;" digit codes"
sleep
print
print
print "___________________________"
quicksort(res(),0,limit)
show=""
for n as long=0 to limit
show+=res(n)+" "
if n <limit then
If res(n)>=res(n+1) then print "ERROR",n,res(n):sleep
if inkey=chr(27) then exit for
end if
next
print show
print
print "Done, press a key"
sleep
My previous permutations proof was too simple and missing something.
I suggest not using option -exx (I have already tested). It slows everything down.
@muttonhead- I shall download and try your method later.
Re: Programming/math "puzzle" for you, guys
Hello, I am new to this forum and in fact signed up because I have been following this thread and must ask,
Can anyone produce a string less than 10124 in length?
Because I have a very simple code to produce one at 10124 not translated to FB but very QB like:
? means print
I have been waiting to see something like this, but haven't yet... maybe I missed it.
Can anyone produce a string less than 10124 in length?
Because I have a very simple code to produce one at 10124 not translated to FB but very QB like:
Code: Select all
' key code string.bas SmallBASIC 0.12.9 [B+=MGA] 2017-04-15
b = ""
for i = 0 to 9999
new = right("0000" + str(i), 4)
if !(instr(b, new)) then b = b+new
next
? : ?
? len(b)
pause
? means print
I have been waiting to see something like this, but haven't yet... maybe I missed it.