Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;
//Using Maybe.cs
namespace ArrayStructure
{
[TestFixture]
public class Tests
{
[Test]
public void RepeatingNumber_EmptyArray_ReturnsNone()
{
Assert.False(FirstNonRepeatingNumber(new int[] {}).HasValue);
}
[Test]
public void RepeatingNumber_ArrayContainsOneValue_ReturnThatValue()
{
Assert.True(FirstNonRepeatingNumber(new[] {1}).Value == 1);
}
[Test]
public void RepeatingNumber_ArrayContains_Two_NonRepeatingNumbers_ReturnTheFirst()
{
Assert.True(FirstNonRepeatingNumber(new[] {1,2}).Value == 1);
}
[Test]
public void RepeatingNumber_ArrayContainsTwoReapeating_OneNon_ReturnNonRepeating()
{
Assert.True(FirstNonRepeatingNumber(new[] {1,1,2}).Value == 2);
}
[Test]
public void RepeatingNumber_ArrayContainsThreeRepeating_NoNon_ReturnNone()
{
Assert.False(FirstNonRepeatingNumber(new[] {1,1,2,2,3,3}).HasValue);
}
[Test]
public void RepeatingNumber_ArrayContainsManyMultipleRepeating_ReturnNon_Performs()
{
Assert.True(FirstNonRepeatingNumber(new[] {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1}).Value == 2);
}
[Test]
public void RepeatingNumber_ArrayContainsUnOrderedInvariants_ReturnTwo()
{
Assert.True(FirstNonRepeatingNumber(new[] {1,3,5,3,1,2,5}).Value == 2);
}
[Test]
public void RepeatingNumber_ArrayContainsANegativeNonRepeating_ReturnNegativeThree()
{
Assert.True(FirstNonRepeatingNumber(new[] {2,2,-3,6,6}).Value == -3);
}
private Maybe<int> FirstNonRepeatingNumber(IReadOnlyList<int> ints)
{
if (!ints.Any()) return Maybe<int>.None;
var duplicates = new List<int>();
for (var i = 0; i < ints.Count; i++)
{
for (var j = i+1; j < ints.Count; j++)
{
if (ints[i] == ints[j])
{
duplicates.Add(ints[i]);
}
}
}
var nonDuplicates = ints.ToList();
if (duplicates.Count == (double)nonDuplicates.Count / 2)
{
return Maybe<int>.None;
}
foreach (var item in duplicates)
{
nonDuplicates.RemoveAll(x => x == item);
}
return Maybe<int>.Some(nonDuplicates[0]);
}
}
}
@jbrains
Copy link

jbrains commented Jul 20, 2018

The check at line 77 seems unnecessarily clever. How often will the list of numbers contains exactly 2 copies of every unique number? Meh. I would remove it.

@jbrains
Copy link

jbrains commented Jul 20, 2018

I really like how you've chosen to use weaker and more intention-revealing types, like IReadOnlyList.

@jbrains
Copy link

jbrains commented Jul 20, 2018

Does this example fail? [3, 3, 5, 3, 5] I have a new laptop, it's Linux, and I don't know how to run C# code on it, otherwise I'd just run it now and find out for myself. Maybe I'll try running it in codeanywhere as an excuse to learn about it. :)

I got this running with VS Code... eventually. I found that torturous.

Indeed, the example I mentioned here fails with:

Failed   OnlyRepeatingNumbers_NotAllMerelyDuplicated
Error Message:
 System.ArgumentOutOfRangeException : Index was out of range. Must be non-negative and less than the size of the collection.
Parameter name: index

@aswhitehouse
Copy link
Author

Very clever mr JB. Indeed I didn’t consider more than 2 as repeating

@aswhitehouse
Copy link
Author

The below fixes that bug and also the bug left when removing the divide in two clause.

private Maybe FirstNonRepeatingNumber(IReadOnlyList ints)
{
if (!ints.Any()) return Maybe.None;

    var duplicates = new List<int>();
    
    for (var i = 0; i < ints.Count; i++)
    {
        for (var j = i+1; j < ints.Count; j++)
        {
            if (ints[i] == ints[j])
            {
                duplicates.Add(ints[i]);
            }
        }
    }

    var nonDuplicates = ints.ToList();

    foreach (var item in duplicates)
    {
        nonDuplicates.RemoveAll(x => x == item);
    }

    return nonDuplicates.Count != 0 ? Maybe<int>.Some(nonDuplicates[0]) : Maybe<int>.None;
}

}

@aswhitehouse
Copy link
Author

We can also now lose the first line thanks to your change.

    private Maybe<int> FirstNonRepeatingNumber(IReadOnlyList<int> ints)
    {            
        var duplicates = new List<int>();
        
        for (var i = 0; i < ints.Count; i++)
        {
            for (var j = i+1; j < ints.Count; j++)
            {
                if (ints[i] == ints[j])
                {
                    duplicates.Add(ints[i]);
                }
            }
        }

        var nonDuplicates = ints.ToList();

        foreach (var item in duplicates)
        {
            nonDuplicates.RemoveAll(x => x == item);
        }

        return nonDuplicates.Count != 0 ? Maybe<int>.Some(nonDuplicates[0]) : Maybe<int>.None;
    }
}

@aswhitehouse
Copy link
Author

This is way more "elegant". But actually really hard to read compared to the for loop one.

    private Maybe<int> FirstNonRepeatingNumber(IReadOnlyList<int> ints)
    {            
        var duplicates = ints.GroupBy(x => x)
            .Where(g => g.Count() > 1)
            .Select(y => y.Key)
            .ToList();

        var nonDuplicates = ints.ToList();

        foreach (var item in duplicates)
        {
            nonDuplicates.RemoveAll(x => x == item);
        }
        return nonDuplicates.Count != 0 ? Maybe<int>.Some(nonDuplicates[0]) : Maybe<int>.None;
    }

@aswhitehouse
Copy link
Author

This is even better - but still.. Linq syntax isn't that readable.

    private Maybe<int> FirstNonRepeatingNumber(IReadOnlyList<int> ints)
    {            
        var duplicates = ints.GroupBy(x => x)
            .Where(g => g.Count() == 1)
            .Select(y => y.Key)
            .ToList();

        return duplicates.Count != 0 ? Maybe<int>.Some(duplicates[0]) : Maybe<int>.None;
    }

@jbrains
Copy link

jbrains commented Jul 25, 2018

I don't know the significance of Key here, but should it be Value? I'm literally just guessing based on the words and what I've seen in other libraries. I guess GroupBy().Where(Count == 1) creates a tuple of pairs that may 2 to the collection of 2s and 6 to the collection of 6s. Am I even close? In that case, Key makes sense. With my limited knowledge of LINQ, I'd leave a comment.

A nicer library would make the last line easier. In Haskell, for example, there is the function head which turns a list of Ts into Maybe a T, implemented exactly this way: return the first element of the list or Nothing if there isn't one. Maybe IReadOnlyList has such a beast? If not, then I'd extract that to a function and call it Head.

A question: how do you know that GroupBy() guarantees that the groupings appear in that List in the same sequence as the corresponding numbers in the original List? Do you just know it? Is it part of the actual contract of GroupBy()? or is it an accident of how GroupBy() is implemented right now? I came by this question merely by noting that I see no words in this implementation that appear to attempt to preserve this property. (It might just be common knowledge that GroupBy() works this way. I don't know.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment