4
\$\begingroup\$

I know that there are combinatoric libraries for this kind of thing. However, with me being new to C# and coding in general I found that I couldn't understand the code well enough to implement it in my solution.

Here is the challenge:

Given two integers: L and R,

find the maximal values of A xor B given, L ≤ A ≤ B ≤ R

Input Format The input contains two lines, L is present in the first line. R in the second line.

Constraints 1 ≤ L ≤ R ≤ 103

Output Format The maximal value as mentioned in the problem statement.

Sample Input#00

 1
 10

Sample Output#00

15


Sample Input#01

10
15

Sample Output#01

7


Explanation for the second example is as follows:

In the second sample let's say L=10, R=15, then all pairs which comply to above condition are

10⊕10=0
10⊕11=1
10⊕12=6
10⊕13=7
10⊕14=4
10⊕15=5
11⊕11=0
11⊕12=7
11⊕13=6
11⊕14=5
11⊕15=4
12⊕12=0
12⊕13=1
12⊕14=2
12⊕15=3
13⊕13=0
13⊕14=3
13⊕15=2
14⊕14=0
14⊕15=1
15⊕15=0

Here two pairs (10,13) and (11,12) have maximum xor value 7 and this is the answer.

The code below represents my solution to the problem in question. It works but I feel like I reinvented the wheel on this one. Is there a better way of going about it than what I have?

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;


class Solution {

    public static List<int[]> Combinations( List<int> number_list ) 
    {

        // We are only choosing 2 values out of any list of numbers
        int[] TwoList = new int[2]; 

        List<int[]> result = new List<int[]>();

        List<int> stack = new List<int>(number_list);                    

        while (stack.Count > 0) 
        {

            int StackLast = stack.Count - 1;

            for (int i =0; i < stack.Count; i++) 
            {
                TwoList[0] = stack[StackLast];

                TwoList[1] = stack[i];

                result.Add(new int[] {TwoList[0], TwoList[1]});
            }
            stack.RemoveAt(StackLast);
        }

        return result;

    }

    static int MaxXor(int l, int r) 
    {

        List<int> NumList = new List<int>(Enumerable.Range(l, r - l + 1));

        // Inserts the list combinations as int arrays
        List<int[]> comboList = Combinations(NumList); 

        int max = 0;

        foreach(var two in comboList)
        {

            int XorValue = two[0] ^ two[1];

            max = ( max > XorValue )? max : XorValue;
        }

        return max;
    }

    static void Main(String[] args) 
    {

        int _l;
        int _r;

        _l = Convert.ToInt32(Console.ReadLine());

        _r = Convert.ToInt32(Console.ReadLine());

        Console.WriteLine(MaxXor(_l, _r));
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Minor things: in C#, the generally accepted naming style is to use PascalCase for all method, constant and property names, and camelCase for everything else. snake_case is really not used in C#. Additionally, opening curly braces generally go on new lines. This helps people not mistake your code for Java while simultaneously making it more familiar to other developers. \$\endgroup\$ – Magus Oct 6 '14 at 14:50
  • \$\begingroup\$ @Magus, I was writing that answer when you posted your comment...lol \$\endgroup\$ – Malachi Oct 6 '14 at 14:56
  • 2
    \$\begingroup\$ You shouldn't edit the code in your question based on the answers you received. \$\endgroup\$ – svick Oct 6 '14 at 16:16
  • \$\begingroup\$ @svick Noted. I will keep that in mind moving forward. Thank you. \$\endgroup\$ – trendsetter37 Oct 6 '14 at 17:24
10
\$\begingroup\$

Couple of basic things with C#

  1. Don't use Egyptian style Bracing, that's for Java.
  2. Watch your indentation, I fixed it in the question.
  3. Casing should follow basic C# standards
    • PascalCase for all Methods, Constants, and Property names
    • camelCase for everything else
    • Protected and public instance variables are UpperCamelCase (to avoid confusion with 3.2) as Jeroen commented
  4. You have more than enough newlines in the code, this can be distracting in your code.
  5. From what I see of your Comments they are all unneeded
    • old code should be deleted
    • other comments are not needed to explain the flow of code or the purpose of the code because it is apparent what is going on with your code.

With these Variables I am not sure what was meant by the Underscore on them, they don't look private or look like properties, they should have a more meaningful name as well

   int _l;
   int _r;

   // We are only choosing 2 values out of any list of numbers
   int[] two_list = new int[2];

This seams like a waste of time to me, you want two numbers, not an array of numbers and not a list of numbers, so you should have two numbers.

int number1;
int number2;

and these numbers should not be written outside of the double loop, this brings me to the conclusion that they are not needed at all, and that you should write this:

        for (int i =0; i < stack.Count; i++) {

            two_list[0] = stack[stackLast];

            two_list[1] = stack[i];

            result.Add(new int[] {two_list[0], two_list[1]});

        }

instead like this

for (int i =0; i < stack.Count; i++) 
{
    result.Add(new int[] {stack[stackLast], stack[i]});
}
\$\endgroup\$
12
  • \$\begingroup\$ Protected and public instance variables are UpperCamelCase (to avoid confusion with 3.2). \$\endgroup\$ – Jeroen Vannevel Oct 6 '14 at 14:58
  • \$\begingroup\$ @JeroenVannevel: While that's true, you shouldn't have any of those, usually. As for Malachi, do note that the underscore prefix on member variables is something maybe half of people agree with. As someone who uses Resharper and can color them differently, I certainly do not agree with extra prefixes. \$\endgroup\$ – Magus Oct 6 '14 at 15:09
  • 1
    \$\begingroup\$ Even though I rely heavily on Intellisense I do not agree that coders should rely on Highlighting and intellisense, so I believe that you should write code so that you can read it without highlighting. \$\endgroup\$ – Malachi Oct 6 '14 at 15:46
  • \$\begingroup\$ @Malachi thanks. And that makes sense about the arrays being unnecessary. After going back and looking at some of the things I did earlier in an attempt to get something that just worked I saw where originally I was trying to just add two_list in its entirety at the end of each iteration in the for loop. Since that didn't work out well I decided on the method above and with that being the case your way is much better. \$\endgroup\$ – trendsetter37 Oct 6 '14 at 15:51
  • 1
    \$\begingroup\$ @Malachi: I do agree that you should be able to read the code without highlighting, but at the same time, if you require underscores to do so, you have bigger problems with overall complexity. If the benefit of both is minor, I prefer color over an extra character. \$\endgroup\$ – Magus Oct 6 '14 at 15:58
0
\$\begingroup\$

Your C# code is probably fine. However your algorithmic approach is not good. First of all, you've written some very confusing code. It is not clear what "Combinations" is doing. Basically, you've written too much code. In addition to being confusing, you are allocating way more memory than necessary. You can evaluate the combinations in a tight loop and never have to allocate anything other than one variable on the stack. Why allocate all those arrays? The alternative solution posted earlier also allocates way too much. Stop allocating like this. When your project scales one day, you will wonder where all your memory is going.

For example, in C-style pseudocode:

int m = 0
for (int A = l; A != l; A++)
     for (int B = A; B != r; B++) {
          xor = A ^ B
          if xor > m: m = xor
     }
print m

In python,

import sys

l = int(sys.argv[1])
r = int(sys.argv[2])

if l > r or l < 1 or r > 1000:
    print "invalid input"
    sys.exit(1)

m = None
for A in range (l, r):
    for B in range (A, r):
        x = A ^ B
        if m is None or x > m:
            m = x
print m
\$\endgroup\$
1
  • \$\begingroup\$ Since you insist, the Python code can stay, but only because it's relevant enough to this answer. Also, please don't continue with those rude remarks. If you have legitimate concerns, take them up on Meta. \$\endgroup\$ – Jamal Jan 4 '15 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.