 |
Cheat Engine
The Official Site of Cheat Engine
|
| View previous topic :: View next topic |
| Author |
Message |
richie86
Grandmaster Cheater
 Reputation: 0
Joined: 13 Jan 2006
Posts: 664
|
 Posted: Mon Dec 17, 2007 3:08 pm Post subject: [Challenge] How Good is Your Algorithm ??? [C# Solution] |
 |
|
Anyone know how to generate a combination of set of card? with the value of number of card per combination provided by user.
Rule:
- You can use Math Class on visual studio if you want
- Array is allowed
- ArrayList is not allowed
- Result must be combination but not permutation.
- No redundancy card is allowed, EG "1,1,2,3,4" 1 is redundant
EG: A, B, C
Permutation = AB, AC, BA, BC, CA, CB
Combination = AB, AC, BC // regardless the arrangement
Question:
Populate all combination that can form from a poker card(total 52 card) where 3 card per combination
52_Choose_3....
so use some loop logic to come out an algorithm to produce output like this
| Code: | 1,2,3,4,5
1,2,3,4,6
1,2,3,4,7
...
1,2,3,5,6
1,2,3,5,7
1,2,3,5,8
...
...
until
48,49,50,51,52 |
EDIT:
Here is my solution by using recursive algorithm.
| Code: | private void button1_Click(object sender, EventArgs e)
{
int totalCard = Convert.ToInt16(txtR.Text); // getting r value from textbox
string strSet = LoadAll(); // generate all set of card: 1 to 52
Pull(strSet, totalCard, strSet.Length, ""); // calling recursive procedure
lstResult.TopIndex = lstResult.Items.Count - 1;
} |
| Code: | private string LoadAll()
{
string str = "";
for (int i = 1; i <= 52; i++)
{
// (char)i = > get ascii char of value i
// reason is because 1 to 52, char length for each is 1 or 2,
// so turn them to ascii so char length is fixed to 1 each
str += Convert.ToString((char)i);
}
return str;
} |
| Code: | private void Pull(string strSet, int r, int n, string strResult)
{ // accept 4 param, (all set of card, r value, n value, result string after recursion)
if (r == 0) // recursion done.. show result
{
lstResult.Items.Add(FormatStr(strResult)); // format them before add to list box
lblCount.Text = "nCr=" + lstResult.Items.Count; // show total count which is nCr
Application.DoEvents(); // show result when loop still going
}
else
{
// extract the character from 52 - n, or we call the first of the last n
string c = strSet.Substring(strSet.Length - n,1);
// continue recursive, for case that you want to include c
Pull(strSet, r - 1, n - 1, strResult + c);
if (r < n) // continue recursive for the case you dont want to include c
Pull(strSet, r, n - 1, strResult);
// this method that recall function itself make us use no for loop at all
// let say first set of char is "abcde" and r is 5
// if you debug from beginning of this procedure, you can see value of strResult is changed each time call itself
// 1. "a"
// 2. "ab"
// 3. "abc"
// 4. "abcd"
// 5. "abcde"
// 6. r==0 result returned, back to the place where it call itself then continue again
// 7. "a"
// 8. "ab"
// 9. "abc"
// 10. "abcd"
// 11. "abcdf"
// 12. continue until everything done
}
} |
| Code: | private string FormatStr(string str)
{ // turn ascii back to something we understand
string strResult = "";
string strValue = ""; // string to store value, so we can show J Q K
int value, num, cell; // value is the value of card(1 to 13), num(1 to 52), cell is card type (0-3)
for (int i = 0; i < str.Length; i++) // loop all string element
{
num = (int)Convert.ToChar(str.Substring(i, 1)); // extract substring, convert to char then get the ascii value
value = num % 13; // mod with 13 to get value
cell = num / 13; // divide to get cell
if (num % 13 == 0) // this case is for when num is 13,26,39..
{
value = 13; // overwrite value to 13, if not num % 13 value is 0
cell = num / 13 - 1; // 13/13 = 1, should be 0, so overwrite it by -1
}
if (value == 11)
strValue = "J";
else if (value == 12)
strValue = "Q";
else if (value == 13)
strValue = "K";
else if (value == 1)
strValue = "A";
else
strValue = Convert.ToString(value);
strResult += "[" + GetCell(cell) + "-" + strValue + "]"; // format them !!
}
return strResult;
} |
| Code: | private string GetCell(int cell)
{ // cell value is 0 to 3, turn it to be more understandable
string str="";
switch (cell)
{
case 0:
str = "♠";
break;
case 1:
str = "♥";
break;
case 2:
str = "♣";
break;
case 3:
str = "♦";
break;
}
return str;
} |
References: Thanks to marlin314 for recursive algorithm
check this link if you interested, its in java.
http://forum.java.sun.com/thread.jspa?threadID=681181&messageID=3971590
Solution Output:
_________________
Last edited by richie86 on Wed Dec 19, 2007 11:49 am; edited 2 times in total |
|
| Back to top |
|
 |
samuri25404
Grandmaster Cheater
 Reputation: 7
Joined: 04 May 2007
Posts: 955
Location: Why do you care?
|
| Posted: Mon Dec 17, 2007 7:44 pm Post subject: |
|
|
ArrayLists aren't allowed?
What about System.Collection.Generic.List<T>s?
If not, can anyone say Array.Resize()?
_________________
|
|
| Back to top |
|
|
rapion124
Grandmaster Cheater Supreme
![]() Reputation: 0
Joined: 25 Mar 2007
Posts: 1095
|
| Posted: Mon Dec 17, 2007 7:48 pm Post subject: |
|
|
| Does it have to be in VB? I wanna write mine in Delphi.
|
|
| Back to top |
|
|
samuri25404
Grandmaster Cheater
Reputation: 7
Joined: 04 May 2007
Posts: 955
Location: Why do you care?
|
| Posted: Mon Dec 17, 2007 8:09 pm Post subject: |
|
|
I see no VB, though I'd do it in C#.
I'm not quite sure what the problem is though.
If you just want to do something like:
| Code: |
1 2
1 3
1 4
1 5
2 1
2 2
2 3
etc..
|
Then just nest some loops within each other.
I'm not too sure about what the user input is supposed to be
_________________
|
|
| Back to top |
|
|
killersamurai
Expert Cheater
![]() Reputation: 0
Joined: 10 Sep 2007
Posts: 197
Location: Colorado
|
| Posted: Tue Dec 18, 2007 1:18 am Post subject: |
|
|
The user input will be a k. He makes reference to it with the screen shot and 52 C 3
| Code: |
n C k
n!
-----------
k!(n - k)!
|
If it were to have permutations, your formula will be without the k! in the bottom
| Code: |
n P k
n!
--------
(n - k)!
|
If I have the time (have to go to work and go to school), I'll take a shot at it.
|
|
| Back to top |
|
|
richie86
Grandmaster Cheater
Reputation: 0
Joined: 13 Jan 2006
Posts: 664
|
| Posted: Tue Dec 18, 2007 3:11 am Post subject: |
|
|
| killersamurai wrote: | The user input will be a k. He makes reference to it with the screen shot and 52 C 3
| Code: |
n C k
n!
-----------
k!(n - k)!
|
If it were to have permutations, your formula will be without the k! in the bottom
| Code: |
n P k
n!
--------
(n - k)!
|
If I have the time (have to go to work and go to school), I'll take a shot at it. |
yep, no external class allowed. mostly use fundamental method ^^
| rapion124 wrote: |
Does it have to be in VB? I wanna write mine in Delphi. |
doesn't matter, the fundamental logic will be the best ^^
_________________
|
|
| Back to top |
|
|
Uzeil
Moderator
 Reputation: 6
Joined: 21 Oct 2006
Posts: 2411
|
| Posted: Tue Dec 18, 2007 3:51 am Post subject: |
|
|
Seems fairly simple, the only challenging part of it is being able to support a user-input-based subset number, but that can be done by recursion 
Anywho, if no one has gotten it, I'll write one up (I'll probably go for ASM so it isn't a snore), assuming it's as easy as it sounds  It's always possible I reach a stump I didn't expect, but, you don't have to speculate, I'd surely post it with a big  face attached.
_________________
|
|
| Back to top |
|
|
richie86
Grandmaster Cheater
Reputation: 0
Joined: 13 Jan 2006
Posts: 664
|
| Posted: Tue Dec 18, 2007 4:11 am Post subject: |
|
|
btw.. performance is also another thing to challenge.. we can come out a very simple loop, but it take long time to loop and filter.. so it's about the algorithm you use ^^
EDIT:  Finally xD
_________________
|
|
| Back to top |
|
|
Uzeil
Moderator
Reputation: 6
Joined: 21 Oct 2006
Posts: 2411
|
| Posted: Tue Dec 18, 2007 1:53 pm Post subject: |
|
|
Richie: Does you algorithm allow any subset number above 0(or 1)? 
That's the only reason this algorithm gets fun, outside of that all you'd need is a for loop for every subset - snorrrrre.
_________________
|
|
| Back to top |
|
|
DoomsDay
Grandmaster Cheater
 Reputation: 0
Joined: 06 Jan 2007
Posts: 768
Location: %HomePath%
|
| Posted: Tue Dec 18, 2007 3:02 pm Post subject: |
|
|
I'll butify\optimize this later (one more register is needed =P), but I got the concept. | Code: | start:
mov eax,1
mov ebx,2
mov ecx,3
mov edx,4
bigassloop:
call dump
.if (edx == 52)
.if (ecx == 51)
.if (ebx == 50)
.if (eax == 49)
call dump
jmp lol
.else
inc eax
.endif
mov ebx,eax
inc ebx
.else
inc ebx
.endif
mov ecx,ebx
inc ecx
.else
inc ecx
.endif
mov edx,ecx
inc edx
.else
inc edx
.endif
jmp bigassloop
lol:
invoke ExitProcess,0
end start |
|
|
| Back to top |
|
|
Trow
Grandmaster Cheater
 Reputation: 2
Joined: 17 Aug 2006
Posts: 957
|
| Posted: Tue Dec 18, 2007 4:33 pm Post subject: |
|
|
So far so good (besides the way I sort the numbers is "card 3 is top priority")
currently no inputs to change "52", but I have to go to school so I don't care to change it now
edit: i'll cheat and replace "52" with a constant you can change... and change the sorting scheme from "last number first" to "first number first"
Option Explicit
Const CN = 10
Private Sub Form_Load()
On Error Resume Next
Dim A As Long, B As Long, C As Long
For A = 1 To CN Step 1
For B = 1 To CN Step 1
If B = A Then Exit For
For C = 1 To CN Step 1
If C = A Or C = B Then Exit For
L.AddItem C & ", " & B & ", " & A
DoEvents
Next
Next
Next
Debug.Print L.ListCount
End Sub
| Description: |
|
| Filesize: |
42.9 KB |
| Viewed: |
10144 Time(s) |
|
_________________
Get kidnapped often. |
|
| Back to top |
|
|
richie86
Grandmaster Cheater
Reputation: 0
Joined: 13 Jan 2006
Posts: 664
|
| Posted: Tue Dec 18, 2007 5:11 pm Post subject: |
|
|
| Uzeil wrote: | Richie: Does you algorithm allow any subset number above 0(or 1)?
That's the only reason this algorithm gets fun, outside of that all you'd need is a for loop for every subset - snorrrrre. |
I can set it to 4 or whatever, i have a constant called totalCard which represent how many card per combination.
In my algo, I have total of two for loop, each of them from different function, there is no nested loop at all 
This is what you want to see.. Rather than use constant, I read the input from GUI.
Edit: some friend ask me what is 12:52.. I'm try to see how fast i can type out the algo.. so 12:52 is the starting time and so far I used 11 min to do it !! I hope it can be even faster..
to blland: Do you have the same total of nCr after all of your loop?
_________________
|
|
| Back to top |
|
|
Uzeil
Moderator
Reputation: 6
Joined: 21 Oct 2006
Posts: 2411
|
| Posted: Tue Dec 18, 2007 6:02 pm Post subject: |
|
|
Richie: a-4 b-4 ? I thought you said no repetition.
DoomsDay: That allows no fluctuation for the users' wishes, it's constant from your own calculations and the assumption that they want the 52:3 setup that was used in Richie's example.
_________________
|
|
| Back to top |
|
|
richie86
Grandmaster Cheater
Reputation: 0
Joined: 13 Jan 2006
Posts: 664
|
| Posted: Tue Dec 18, 2007 9:32 pm Post subject: |
|
|
| Uzeil wrote: | Richie: a-4 b-4 ? I thought you said no repetition.
DoomsDay: That allows no fluctuation for the users' wishes, it's constant from your own calculations and the assumption that they want the 52:3 setup that was used in Richie's example. |
a,b,c,d stand for spades, heart, clubs, and diamond.
a-4 and b-4 is different.
there will be no x-y that appeared two time in each combination.
_________________
|
|
| Back to top |
|
|
DoomsDay
Grandmaster Cheater
Reputation: 0
Joined: 06 Jan 2007
Posts: 768
Location: %HomePath%
|
| Posted: Wed Dec 19, 2007 1:46 pm Post subject: |
|
|
| Uzeil wrote: | Richie: a-4 b-4 ? I thought you said no repetition.
DoomsDay: That allows no fluctuation for the users' wishes, it's constant from your own calculations and the assumption that they want the 52:3 setup that was used in Richie's example. |
>=]
(I tried to explain it, I realy did) | Code: | ;Created by DoomsDay
;speed: less than a second!
;output: none =D
.686
.model flat,stdcall
option casemap:none
.code
Calculate proc DeckSize,Count
mov eax,Count
cmp eax,DeckSize
jge Invalid ;Count > DeckSize = bad
mov ebx,01 ;Creating an enviornment for the 'cards'
.while (ebx <= eax)
push ebx
inc ebx
.endw
mov eax,DeckSize ;setting the 'max value'
mov ebx,4 ;EBX = array counter for the enviornment created earlier
push offset BigLoop ;will be used later, see 'push [esp]'
BigLoop:
.if ([esp+ebx] == eax) ;I've pushed the 'cards' to the stack, I'm using EBX as a counter
add ebx,8 ;That's the growth factor for each loop
dec eax ;EAX is used to determine the max value of the 'card'
mov ecx,Count ;(Count*8)+4 = highest value of EBX = deepest BigLoop call
imul ecx,8
add ecx,4
.if (ecx != ebx)
call BigLoop ;EBX is not maxed, go deeper
.else
mov eax,1 ;TRUE (deepest loop ended[the last 'card' maxed out])
sub ebx,4 ;restoring the stack to it's original position
add esp,ebx
pop ebp ;end
retn 08
.endif
sub ebx,8 ;end of the loop, restore the stack and the counter
add esp,4
inc eax ;restoring the 'max value'
inc edx ;see the 'else' section coming later... it>
;> holds the 'max value' that has been reached on the last 'card'
mov [esp+ebx],edx ;applying the value - (Value+1) to the next 'card'
push [esp] ;operates with the CALLing issue, see the 'push offset BigLoop' above
retn
.else
mov edx,[esp+ebx] ;increasing the 'card'
inc edx
mov [esp+ebx],edx
push [esp]
retn
.endif
Invalid:
xor eax,eax ;FALSE only reached when the arguments are bad
pop ebp
retn 08
Calculate endp
start:
invoke Calculate,52,5
retn
end start |
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
