topcoder question

  • Thread starter Thread starter Roy Lawson
  • Start date Start date
R

Roy Lawson

Just curious if anyone here participates in the topcoder competitions.
I have been doing some of their practice challenges from prior
competitions and find them to be very challenging.

Only problem so far is that most of the coders are developing in Java,
C++, or C# so I am not able to compare my VB7 code to others in order
to better evaluate myself.

Anyways, checkout www.topcoder.com and if you do any of their practice
challenges let me know which one so I can compare my style.

-Roy Lawson
 
Hi Roy,

To save having to download Sun's VM and the TopCoder app, and having to
register, would you care to post one of the challenges that you're
particularly interested in?

DF
 
To save having to download Sun's VM and the TopCoder
app, and having to
register, would you care to post one of the challenges that you're
particularly interested in?

Yeah, that is my one complaint about the site. I would
rather have a desktop application reside on my machine
that connects to their database. Perhaps MS would be
interested in developing a site similar to this for .NET
coders? You can still submit your .NET code but most of
the coders are Java or C++ coders. Here is the last one I
did:

##################
Problem Statement#
##################

Tommy is learning a simple card game called Circle. To
play the game, the single player shuffles a deck of cards.
He or she then flips through the deck, removing all
instances of the 'K' card, and all consecutive pairs of
cards that add up to 13. The deck does wrap around, so
that if the last card remaining in the deck and the first
card remaining in the deck add up to 13, they are both
removed. The player keeps cycling through the deck until
no more cards can be removed.

Create a class CircleGame containing the method cardsLeft
that takes a String deck representing a not-necessarily
complete nor correct deck of cards. Each character of deck
represents the value of a card without the suit. The
values shown on the card represent the following numerical
values:

'A' - 1
'2' - 2
'3' - 3
'4' - 4
'5' - 5
'6' - 6
'7' - 7
'8' - 8
'9' - 9
'T' - 10
'J' - 11
'Q' - 12
'K' - 13

Given deck, return the number of cards remaining after the
game has been played to its fullest such that no more
cards can be removed.
Definition

Class:
CircleGame
Method:
cardsLeft
Parameters:
String
Returns:
Integer
Method signature:
Public Function cardsLeft(deck As String) As Integer
(be sure your method is public)


Notes
-
There are no guarantees made about the contents of the
deck. For example, there can be more than four of a given
value of card.
-
Note that if a particular card can make a sum of 13 with
the card before or after it, it does not matter which is
chosen. For example, 38582, whether you use the first 8 or
the second 8, will still become 382 after the two cards (5
and 8) are removed.
Constraints
-
deck will have between 10 and 50 characters, inclusive.
-
each character of deck will be a character from the set
{'2'-'9','A','T','J','Q','K'}.
Examples
0)


"KKKKKKKKKK"
Returns: 0
All K cards are always removed from the deck.
1)


"KKKKKAQT23"
Returns: 1
The K cards are removed, leaving AQT23. AQ are then
removed because they add up to 13, leaving T23. Since the
deck wraps around and T and 3 add up to 13, they are also
removed, just leaving the 2.
2)


"KKKKATQ23J"
Returns: 6
Only the K cards can be removed.
3)


"AT68482AK6875QJ5K9573Q"
Returns: 4
The remaining deck is 6875.
4)


"AQK262362TKKAQ6262437892KTTJA332"
Returns: 24
 
Hi Some Guy, Roy

I like a challenge. :-)

Here's my version. I left in the comments and debug output, though in the
competition I would remove them.

Are you going to post yours for review?

Regards,
Fergus

<code>
'Start time 9:50pm
'First run 10:20
'First successful completion of examples 10:27
'Finished testing 10:36
'Ready to submit 10:38
'
Public Class CircleDeck

Public Sub Test
cardsLeft ("QJT98765432AQJT98765432A")
cardsLeft ("") '0
cardsLeft ("QQQ") '0
cardsLeft ("KKKKKKKKKK") '0
cardsLeft ("T1111113") '6
cardsLeft ("111111T3") '6
cardsLeft ("KQJT987K65432AQJT987K65432AK") '0
cardsLeft ("KKKKKAQT23") '1
cardsLeft ("KKKKATQ23J") '6
cardsLeft ("AT68482AK6875QJ5K9573Q") '4
cardsLeft ("AQK262362TKKAQ6262437892KTTJA332") '24
End Sub

Public Function cardsLeft (sDeck As String) As Integer
Dim sCards As String = "23456789TJQK"
Dim NumCards = sDeck.Length
Dim I = 0
Dim J = 0
Dim StillGoing

Dim NoRemoveCount = 0
Console.WriteLine ("CARDS = {0}", sDeck)

Do Until NoRemoveCount = sDeck.Length
'Get the next index.
J = IIF (I + 1 < sDeck.Length, I + 1, 0)
Console.Write ("I = {0}, J = {1}, ", I, J)
Console.WriteLine ("c1 = {0}, c2 = {1}, v1 = {2}, v2 = {3}", _
sDeck.Substring (I, 1), _
sDeck.Substring (J, 1), _
sCards.IndexOf (sDeck.Substring (I, 1)) + 2, _
sCards.IndexOf (sDeck.Substring (J, 1)) + 2 _
)

'Get the values for the next pair of cards.
Dim v1 As Integer = sCards.IndexOf (sDeck.Substring (I, 1)) + 2
If v1 = 13 Then
Console.WriteLine ("Remove King:{0} {1}", vbCrLf, sDeck)
'Remove King.
sDeck = sDeck.Substring (0, I) & sDeck.Substring (I + 1)
'I stays same or.
If I >= sDeck.Length Then
I = 0
End If
NoRemoveCount = 0
Else
J = IIF (I + 1 < sDeck.Length, I + 1, 0)
Dim v2 As Integer = sCards.IndexOf (sDeck.Substring (J, 1)) +
2
If v1 + v2 = 13 Then
'Remove the pair.
If J = 0 Then
'Lose both ends.
Console.WriteLine ("Lose Ends:{0} {1}", vbCrLf,
sDeck)
sDeck = sDeck.Substring (1, I - 1)
Console.WriteLine (" {0}", sDeck)
'I drops by two.
I = I - 2
Else
'Lose two from middle or far end.
Console.WriteLine ("Lose Middle:{0} {1}", vbCrLf,
sDeck)
sDeck = sDeck.Substring (0, I) & sDeck.Substring (J +
1)
Console.WriteLine (" {0}", sDeck)
'I stays same or.
If I >= sDeck.Length Then
I = 0
End If
End If
NoRemoveCount = 0
Else
I = I + 1
If I >= sDeck.Length Then
I = 0
End If
NoRemoveCount = NoRemoveCount + 1
End If
End If
Loop
Console.WriteLine ("Result = {0}", sDeck.Length)
Return sDeck.Length
End Function

End Class
</code>
 
Cool, it took me a bit longer but this is what I came up
with (I didn't keep exact track of time) Also, I let the
topcoder engine compile and run test cases against it so I
know it works...there are certainly some improvements
needed as far as style:

Public Class clsCircle
Private intCards As Integer
Public newDeck As String
Private x As Integer
Private b As Integer
Private y As String
Private z As String
Private yy As String
Private zz As String
Private count As Integer
Private Shift As Boolean
Private newString As String


Public Function cardsLeft(ByVal deck As String) As
Integer

newDeck = deck.ToString
newDeck = newDeck.Trim("K")

For count = 0 To newDeck.Length - 1
y = newDeck.Chars(0)
z = newDeck.Chars(newDeck.Length - 1)
yy = newDeck.Chars(0)
zz = newDeck.Chars(newDeck.Length - 1)

'too lazy to get fancy here
If y = "A" Then y = "1"
If y = "T" Then y = "10"
If y = "J" Then y = "11"
If y = "Q" Then y = "12"
If y = "K" Then y = "13"

If z = "A" Then z = "1"
If z = "T" Then z = "10"
If z = "J" Then z = "11"
If z = "Q" Then z = "12"
If z = "K" Then z = "13"

Shift = True
If (Int(y) + Int(z)) = 13 Then
newDeck = newDeck.TrimEnd(zz)
newDeck = newDeck.TrimStart(yy)
newDeck = newDeck.Trim()
Shift = False
End If

If Shift = True Then
b = newDeck.Length - 1
newString = Nothing
For x = 0 To newDeck.Length - 2
If Shift = True Then newString =
newString & newDeck.Chars(newDeck.Length - 1)
Shift = False
newString = newString & newDeck.Chars
(x)
Next
newDeck = newString
newDeck = newDeck.Trim("K")
newDeck = newDeck.Trim()
End If
Next
x = newDeck.Length
Return x
End Function
End Class
 
Hi Roy,

|| newDeck = newDeck.Trim("K")


Doh! I didn't think of Trim() and Chars(), nor Replace(). Lol.


The bad news is that your method fails on the first test case. :-(

In fact it'll fail on "QA". A For loop calculates the end value once. As
you remove values, that final index will be out of bounds. A dynamic loop (Do
or While) is required.

Regards,
Fergus
 
Hi Fergus,

Thanks for testing it. Your code seemed to pass every
test I threw at it so looks like it came out on top. I
was having a heck of a time using Replace...so that is why
I stuck with Trim. I wanted to Replace "K" from the
entire string with one command and insert nothing instead
but no dice.

At first, I tried to put every Char(x) into an array of
integers, converting the letters beforehand into their
respective integer values. But I was having problems
figuring out how to delete the index of whatever element I
wanted to remove, plus having problems rotating the
positions. There is another way to handle the rotation
though which I thought of afterwords.

I am unemployed right and since I don't want to become
rusty, this seems like it will do the trick as far as
staying on top of things.

In the topcoder game, you could challenge my solution like
you did and get 50 points if it succeeds added on your
score...and I would lose 50 points.

Regards,
-Roy
 
Hi Roy,

Strange that Replace() didn't work. I presume you had newDeck =
newDeck.Replace ("K", ""). I put this is into your class and it was fine.

With the array deletion, alCards.RemoveAt (I) will do the job - provided
you use an ArrayList. Rotation is also made easy by the ArrayList as it
provides Insert - eg, alCards.Insert (0, alCards (I)) will add card I to the
front. using the RemoveAt will make it a move. Very handy things, ArrayLists.
:-)

I must admit I had trouble understanding your method. I gathered that it
was removing the cards when the pair occurred at each end. But the shuffling
had me beaten!!

Shall we play with another one?

Regards,
Fergus
 
Sure, I will start another thread so we can find this more
easily for another problem. I won't use a topcoder one
though, they are copyrighted...but I have found some other
ones from some universities that seem challenging.

-Roy
 
Back
Top