Doing a Cast Within a LINQ Query

Question

My question is in reference to the FB HackerCup 2013 QualificationRound problem - BalancedSmileys.

Problem Statement: https://www.facebook.com/hackercup/problems.php?pid=403525256396727&round=185564241586420 (copy here too: https://github.com/anuragkapur/Algorithmic-Programming/tree/master/src/com/anuragkapur/fb/hackercup2013/qr#problem-2-balanced-smileys)

I figured how to solve this problem using the BruteForce method which has exponential running time.

As per the official solutions posted, there is a solution with linear running time. It is described here: https://www.facebook.com/notes/facebook-hacker-cup/qualification-round-solutions/598486173500621

Essentially, it maintains two counters: minOpen and maxOpen. Whenever a open parenthesis "(" is encountered, maxOpen is incremented. If the "(" was NOT a part of a smiley, minOpen is also incremented. Similar strategy for handling ")" as well, as described in the explanation link above.

I can see that the linear time method works, but it is not crystal clear in my head - how? So I am polling this group to find out if anyone can give an alternate "explanation" of the linear running time solution.

Many thanks!

Solution 1

Try this:

from TabSection t in content.ChildControls

Also, even if this were not available (or for a different, future scenario you may encounter), you wouldn't be restricted to converting everything to Lists. Converting to a List causes query evaluation on the spot. But if you removing the ToList call, you could work with the IEnumerable type, which would continue to defer the execution of the query until you actually iterate or store in a real container.

Solution 2

Depending on what you are trying to do, one of these might do the trick:

List<Line> parentLineList1 =
  (from t in content.ChildControls.OfType<TabSection>()
   from p in t.ChildControls.OfType<Paragraph>()
   from pl in p.ChildControls.OfType<Line>()
   select pl).ToList();

List<Line> parentLineList2 =
  (from TabSection t in content.ChildControls
   from Paragraph p in t.ChildControls
   from Line pl in p.ChildControls
   select pl).ToList();

Note that one uses OfType<T>(), which you were using. This will filter the results and return only the items of the specified type. The second query implicitly uses Cast<T>(), which casts the results into the specified type. If any item cannot be cast, an exception is thrown. As mentioned by Turbulent Intellect, you should refrain from calling ToList() as long as possible, or try to avoid it altogether.

Solution 3

List<TabSection> tabList = (from t in content.ChildControls
                            let ts = t as TabSection
                            where ts != null
                            select ts).ToList();

Solution 4

yes you can do the following:

List<TabSection> tabList = (from t in content.ChildControls
                            where t as TabSection != null
                            select t as TabSection).ToList();

Solution 5

And here's the query method form.

List<Line> parentLineList =
  content.ChildControls.OfType<TabSections>()
    .SelectMany(t => t.ChildControls.OfType<Paragraph>())
    .SelectMany(p => p.ChildControls.OfType<Line>())
    .ToList();

View more solutions

Comments

[Bartlomiej Lewandowski]

You have to have an equal amount of open and close brackets. You do not count the ones in smileys. There is nothing more to this

[Anurag Kapur]

Just an equal amount of open and close brackets is not enough. They need to be in the right order. Also, I dont think it is true to say that the brackets in smileys are not counted. They are, if there isn't a simple bracket to balance another. Thats why minOpen and maxOpen are evaluated.

[Philip]

Should have read your question more carefully. I'll leave my answer as a reminder for others.