Search

Categories

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Send mail to the author(s) E-mail

# Wednesday, 01 October 2014

Second implementation of the problem solver.

using NUnit.Framework;
using System;
using System.Collections.Generic;
using System.Linq;

namespace MonsterProject {
    class Program {
        static void Main() {
            var studentA = new Student { ChoiceA = 1, ChoiceB = 3, ChoiceC = 1 };
            var studentB = new Student { ChoiceA = 2, ChoiceB = 2, ChoiceC = 1 };
            var studentC = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 3 };
            var studentD = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var studentE = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var students = new List<Student> { studentA, studentB, studentC, studentD, studentE };
            var projects = new List<int> { 1, 2, 3, 4, 5 };

            var solver = new StudentProjectSolver();
            var result = solver.Solve(students, projects);

            students = result.Item1;
            var projectsNotAssigned = result.Item2;

            foreach (var student in students) {
                Console.WriteLine(student.Message);
            }
            Console.WriteLine("Projects not assigned:");
            foreach (var i in projectsNotAssigned) {
                Console.WriteLine(i);
            }
        }
    }

    public class StudentProjectSolver {
        //200 students
        //300 projects
        //students can choose top 5 projects
        //only 1 project per student

        //You want to find the optimal allocation of projects so most number of students are 'happy'
        //Happiness is defined as having the highest of their 'top5'

        //Look at students first choices, assigning to them ones which no other student has requested
        //Go through remaining first choices which more than 1 student has requested
        //Look at second choices and assign to them ones which no other student has asked for
        //Go through remaining second choices which more than 1 student has requested
        //Look at third choices and assign to them ones which no other student has requested
        //etc..

        [Test]
        public void Given3StudentsWithAllDifferentProjectRequests_And3DProjects_AssignProjects() {
            var studentA = new Student { ChoiceA = 1, ChoiceB = 2, ChoiceC = 3 };
            var studentB = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var studentC = new Student { ChoiceA = 3, ChoiceB = 1, ChoiceC = 2 };
            var students = new List<Student> { studentA, studentB, studentC };
            var projects = new List<int> { 1, 2, 3 };

            var result = FilterUniqueChoiceAs(students, projects);
            students = result.Item1;
            Assert.AreEqual(1, students[0].AssignedProject);
            Assert.AreEqual(2, students[1].AssignedProject);
            Assert.AreEqual(3, students[2].AssignedProject);
        }

        [Test]
        public void Given2StudentsWithAllDifferentProjectRequests_And3DProjects_ShouldAssignAndHave1LeftOverProject() {
            var studentA = new Student { ChoiceA = 1, ChoiceB = 2, ChoiceC = 3 };
            var studentB = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var students = new List<Student> { studentA, studentB };
            var projects = new List<int> { 1, 2, 3 };

            var result = FilterUniqueChoiceAs(students, projects);
            students = result.Item1;
            projects = result.Item2;
            Assert.AreEqual(1, students[0].AssignedProject);
            Assert.AreEqual(2, students[1].AssignedProject);

            Assert.AreEqual(3, projects[0]);
        }

        [Test]
        public void Given3StudentsWithAllDifferentChoiceB_And3DProjects_ShouldAssign() {
            var studentA = new Student { ChoiceA = 2, ChoiceB = 1, ChoiceC = 3 };
            var studentB = new Student { ChoiceA = 2, ChoiceB = 2, ChoiceC = 1 };
            var studentC = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var students = new List<Student> { studentA, studentB, studentC };
            var projects = new List<int> { 1, 2, 3 };

            var result = FilterUniqueChoiceAs(students, projects);
            result = FilterUniqueChoiceBs(students, projects);
            students = result.Item1;
            projects = result.Item2;
            Assert.AreEqual(1, students[0].AssignedProject);
            Assert.AreEqual(2, students[1].AssignedProject);
            Assert.AreEqual(3, students[2].AssignedProject);
        }

        [Test]
        public void Given3StudentsWithAllDifferentChoiceC_ShouldAssign() {
            var studentA = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var studentB = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 2 };
            var studentC = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 3 };
            var students = new List<Student> { studentA, studentB, studentC };
            var projects = new List<int> { 1, 2, 3 };

            var result = FilterUniqueChoiceAs(students, projects);
            result = FilterUniqueChoiceBs(students, projects);
            result = FilterUniqueChoiceCs(students, projects);
            students = result.Item1;
            projects = result.Item2;
            Assert.AreEqual(1, students[0].AssignedProject);
            Assert.AreEqual(2, students[1].AssignedProject);
            Assert.AreEqual(3, students[2].AssignedProject);
        }

        [Test]
        public void Given5StudentsWithMultiChoices_ShouldAssign() {
            var studentA = new Student { ChoiceA = 1, ChoiceB = 3, ChoiceC = 1 };
            var studentB = new Student { ChoiceA = 2, ChoiceB = 2, ChoiceC = 1 };
            var studentC = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 3 };
            var studentD = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var studentE = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var students = new List<Student> { studentA, studentB, studentC, studentD, studentE };
            var projects = new List<int> { 1, 2, 3 };

            var result = FilterUniqueChoiceAs(students, projects);
            result = FilterUniqueChoiceBs(students, projects);
            result = FilterUniqueChoiceCs(students, projects);
            students = result.Item1;
            projects = result.Item2;
            Assert.AreEqual(1, students[0].AssignedProject);
            Assert.AreEqual(2, students[1].AssignedProject);
            Assert.AreEqual(3, students[2].AssignedProject);
        }

        [Test]
        public void Given5StudentsWithMultiChoices_ShouldAssignAndPrintRemainder() {
            var studentA = new Student { ChoiceA = 1, ChoiceB = 3, ChoiceC = 1 };
            var studentB = new Student { ChoiceA = 2, ChoiceB = 2, ChoiceC = 1 };
            var studentC = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 3 };
            var studentD = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var studentE = new Student { ChoiceA = 2, ChoiceB = 3, ChoiceC = 1 };
            var students = new List<Student> { studentA, studentB, studentC, studentD, studentE };
            var projects = new List<int> { 1, 2, 3 };

            var result = FilterUniqueChoiceAs(students, projects);
            result = FilterUniqueChoiceBs(students, projects);
            result = FilterUniqueChoiceCs(students, projects);
            result = PrintMessagesInTheRest(students, projects);
            students = result.Item1;
            projects = result.Item2;
            Assert.AreEqual(1, students[0].AssignedProject);
            Assert.AreEqual(2, students[1].AssignedProject);
            Assert.AreEqual(3, students[2].AssignedProject);
            Assert.AreEqual("Didn't assign project as no choices were unique", students[3].Message);
        }

        // API
        public Tuple<List<Student>, List<int>> Solve(List<Student> students, List<int> projects) {
            var result = FilterUniqueChoiceAs(students, projects);
            result = FilterUniqueChoiceBs(students, projects);
            result = FilterUniqueChoiceCs(students, projects);
            result = PrintMessagesInTheRest(students, projects);
            return result;
        }

        private Tuple<List<Student>, List<int>> PrintMessagesInTheRest(List<Student> students, List<int> projects) {
            foreach (var student in students.Where(x => x.AssignedProject == 0)) {
                student.Message = String.Format("Didn't assign project as no choices were unique", student.ChoiceA);
                projects.Remove(student.ChoiceA);
            }
            return Tuple.Create(students, projects);
        }

        public Tuple<List<Student>, List<int>> FilterUniqueChoiceAs(List<Student> students, List<int> projects) {
            foreach (var student in students) {
                if (IsUniqueChoiceA(student.ChoiceA, students)) {
                    student.AssignedProject = student.ChoiceA;
                    student.Message = String.Format("Assigned project {0} because no other Students wanted this as ChoiceA", student.ChoiceA);
                }
                projects.Remove(student.ChoiceA);
            }
            return Tuple.Create(students, projects);
        }

        public Tuple<List<Student>, List<int>> FilterUniqueChoiceBs(List<Student> students, List<int> projects) {
            foreach (var student in students) {
                if (IsUniqueChoiceB(student.ChoiceB, students)) {
                    student.AssignedProject = student.ChoiceB;
                    student.Message = String.Format("Assigned project {0} because no other Students wanted this as ChoiceB", student.ChoiceB);
                }
                projects.Remove(student.ChoiceB);
            }
            return Tuple.Create(students, projects);
        }

        public Tuple<List<Student>, List<int>> FilterUniqueChoiceCs(List<Student> students, List<int> projects) {
            foreach (var student in students) {
                if (IsUniqueChoiceC(student.ChoiceC, students)) {
                    student.AssignedProject = student.ChoiceC;
                    student.Message = String.Format("Assigned project {0} because no other Students wanted this as ChoiceC", student.ChoiceC);
                }
                projects.Remove(student.ChoiceC);
            }
            return Tuple.Create(students, projects);
        }

        public bool IsUniqueChoiceA(int choiceA, List<Student> students) {
            {
                var x = students.Count(y => y.ChoiceA == choiceA);
                if (x > 1) return false;
                return true;
            }
        }

        public bool IsUniqueChoiceB(int choiceB, List<Student> students) {
            {
                var x = students.Count(y => y.ChoiceB == choiceB);
                if (x > 1) return false;
                return true;
            }
        }

        public bool IsUniqueChoiceC(int choiceC, List<Student> students) {
            {
                var x = students.Count(y => y.ChoiceC == choiceC);
                if (x > 1) return false;
                return true;
            }
        }
    }

    public class Student {
        public int Name { get; set; }
        public int ChoiceA { get; set; }
        public int ChoiceB { get; set; }
        public int ChoiceC { get; set; }
        public int AssignedProject { get; set; }
        public string Message { get; set; }
    }
}
| | # 
# Monday, 29 September 2014

Had to go from xUnit to NUnit to get debug information in real time in debug: http://stackoverflow.com/questions/15092438/using-resharper-how-to-show-debug-output-during-a-long-running-unit-test

http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-10-recursion/#_Toc362296468

code in https://github.com/djhmateer/StudentProjects  (currently in recd branch)

N nested loops
Each loop goes from 1 to K

If N=2 and K=3 output is:

image

N=3 and K=2 output is:

image

image
Image from website.  Strategy is to find a recurrent dependence.

public class RecursiveNestedLoops {
    int numberOfNestedLoops; // N - number of nested for sequenceOfValues
    int numberOfIterations; // K - for 1..K
    int[] sequenceOfValues;

    [Test]
    public void DoSomething() {
        numberOfNestedLoops = 3;
        numberOfIterations = 2;
        sequenceOfValues = new int[numberOfNestedLoops];
        NestedLoops(0);
    }

    public void NestedLoops(int currentLoop) {
        // Got to the bottom of the recursion, print and return
        if (currentLoop == numberOfNestedLoops) {
            PrintLoops();
            return;
        }

        // Setup an iteration from 1..K in this nestedloop
        for (int counter = 1; counter <= numberOfIterations; counter++) {
            sequenceOfValues[currentLoop] = counter;
            NestedLoops(currentLoop + 1);
        }
    }

    public void PrintLoops() {
        var message = "";
        for (int i = 0; i < numberOfNestedLoops; i++) {
            message += String.Format("{0} ", sequenceOfValues[i]);
        }
        Debug.WriteLine(message);
    }
}

Iterative Version

It is possible to do the same without recursion.  Lets see if it is easier to understand:

Output is the same for  numberOfNestedLoops N=3, numberOfIterations:  K=2
image

  • Start with a sequenceOfValues array of 1 1 1
  • Print current sequenceOfValues
  • Increment with 1 the number at position N.  If > K replace with 1and increment with 1 the value at position N-1.  If its value has become greater than K, replace it with 1 etc..
  • sequenceOfValues
    • 1 1 2
    • 1 1 3 (invalid so go inside while)
    • 1 2 1
    • 1 2 2
    • 1 2 3 (invalid so go inside while)
    • 1 2 1 (still inside while)
    • 1 3 1 (still inside while, and invalid)
    • 1 1 1 (still inside while)
    • 2 1 1
    • 2 1 2
    • 2 1 3 (invalid so go inside while)
    • 2 1 1 (inside while)
    • 2 2 1
    • 2 2 2
    • 2 2 3 (invalid so go inside while)
    • 2 2 1 (still inside while)
    • 2 3 1 (still inside while and invalid)
    • 2 1 1 (still inside while)
    • 3 1 1 (still inside while and invalid)
    • 1 1 1 (still inside while and return)

The effect is just like nested for loops.

public class NestedLoopsIterative {
    int numberOfNestedLoops;
    int numberOfIterations;
    int[] sequenceOfValues;
    int lastPositionInArray;

    [Test]
    public void DoSomething() {
        numberOfNestedLoops = 3;
        numberOfIterations = 2;
        lastPositionInArray = numberOfNestedLoops - 1;
        sequenceOfValues = new int[numberOfNestedLoops];
        NestedLoops();
    }

    public void NestedLoops() {
        InitLoops();
        while (true) {
            PrintLoops();

            int currentPositionInSOV = lastPositionInArray;
            sequenceOfValues[currentPositionInSOV] += 1;

            while (sequenceOfValues[currentPositionInSOV] > numberOfIterations) {
                sequenceOfValues[currentPositionInSOV] = 1;
                currentPositionInSOV--;

                if (currentPositionInSOV < 0) return; // break out of while
                sequenceOfValues[currentPositionInSOV] += 1;
            }
        }
    }

    public void InitLoops() {
        for (int i = 0; i < numberOfNestedLoops; i++) {
            sequenceOfValues[i] = 1;
        }
    }

    public void PrintLoops() {
        var message = "";
        for (int i = 0; i < numberOfNestedLoops; i++) {
            message += String.Format("{0} ", sequenceOfValues[i]);
        }
        Debug.WriteLine(message);
    }
}

I like this version, as slightly easier to understand.

Apply to StudentProjects

Implemented using TDD.

image
In release mode in a console app, 7 Students, and 10 Projects taking 26secs.  Actually 7 secs with no print statement.

Summary of Brute Force

This has been great fun... but by brute force I've hit the big O problem :-)  The business logic works, and can do N loops (students) and K iterations (projects)

https://github.com/djhmateer/StudentProjects

I got the non recursive version of N Loops from:

http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-10-recursion/#_Toc362296468

which I think is slightly easier to understand than the recursive version.

Found that NUnit is better than xUnit when wanting to debug and show output.

Think I'm ready to throw my code away now!!!  Although I did have an idea about pre generating the sequences...

Where now?

| | # 
# Saturday, 27 September 2014

A real problem which has peaked my interest.

  • 200 students
  • 300 projects
  • students choose top 5 projects
  • only 1 project per student
  • Want to find the optimal allocation of projects so most number of students are 'happy'
  • A students happiness is defined as having the highest of their 'top5'

Get the simplest happy path working.

[Fact]
public void Given3StudentsWhoChoose3DifferentProjectsAsTheirTop_OverallRunScoreShouldBe3WhichIsPerfectFor3Students() {
    var listOfStudents = new List<Student>();
    var student0 = new Student { ProjectChoiceA = 1, ProjectChoiceB = 2, ProjectChoiceC = 3, ProjectWinner = 0 };
    var student1 = new Student { ProjectChoiceA = 2, ProjectChoiceB = 3, ProjectChoiceC = 1, ProjectWinner = 0 };
    var student2 = new Student { ProjectChoiceA = 3, ProjectChoiceB = 1, ProjectChoiceC = 2, ProjectWinner = 0 };
    listOfStudents.Add(student0);
    listOfStudents.Add(student1);
    listOfStudents.Add(student2);

    Tuple<List<Student>, int> tuple = Solve(listOfStudents);
    int score = tuple.Item2;
    List<Student> students = tuple.Item1;
    Assert.Equal(1, students[0].ProjectWinner);
    Assert.Equal(2, students[1].ProjectWinner);
    Assert.Equal(3, students[2].ProjectWinner);

    Assert.Equal(3, score);
}

and the solve:

public Tuple<List<Student>, int> Solve(List<Student> students) {
    // run through every project permutation, so we try giving all projects to all students
    // and choose the permutation with the lowest overallScore
    // each student gets a score based on:
    // ChoiceA = 1, ChoiceB = 2 etc..
    int lowestScore = 99999;

    var projects = new[] { 1, 2, 3 };
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                // only want where i != j != k
                if (i != j && j != k && k != i) {

                    // pick a project for each student
                    var projectForStudent0 = projects[i];
                    var projectForStudent1 = projects[j];
                    var projectForStudent2 = projects[k];

                    // get score for this permutation
                    int score = 0;
                    if (projectForStudent0 == students[0].ProjectChoiceA) score += 1;
                    if (projectForStudent0 == students[0].ProjectChoiceB) score += 2;
                    if (projectForStudent0 == students[0].ProjectChoiceC) score += 3;

                    if (projectForStudent1 == students[1].ProjectChoiceA) score += 1;
                    if (projectForStudent1 == students[1].ProjectChoiceB) score += 2;
                    if (projectForStudent1 == students[1].ProjectChoiceC) score += 3;

                    if (projectForStudent2 == students[2].ProjectChoiceA) score += 1;
                    if (projectForStudent2 == students[2].ProjectChoiceB) score += 2;
                    if (projectForStudent2 == students[2].ProjectChoiceC) score += 3;

                    // is this the lowest score, remember which projects
                    if (score <= lowestScore && score >= 3) {
                        lowestScore = score;
                        students[0].ProjectWinner = projectForStudent0;
                        students[1].ProjectWinner = projectForStudent1;
                        students[2].ProjectWinner = projectForStudent2;
                    }
                }
            }
        }
    }
    return Tuple.Create(students, lowestScore);
}

then a few more tests:

[Fact]
public void Given3StudentsAnd2ChooseTheSameTopButDifferentThird_OverallRunScoreShould() {
    var listOfStudents = new List<Student>();
    //First choice
    var student0 = new Student { ProjectChoiceA = 1, ProjectChoiceB = 2, ProjectChoiceC = 3, ProjectWinner = 0 };
    //Should get second
    var student1 = new Student { ProjectChoiceA = 2, ProjectChoiceB = 3, ProjectChoiceC = 1, ProjectWinner = 0 };
    //First
    var student2 = new Student { ProjectChoiceA = 2, ProjectChoiceB = 1, ProjectChoiceC = 3, ProjectWinner = 0 };
    listOfStudents.Add(student0);
    listOfStudents.Add(student1);
    listOfStudents.Add(student2);

    Tuple<List<Student>, int> tuple = Solve(listOfStudents);
    int score = tuple.Item2;
    List<Student> students = tuple.Item1;
    Assert.Equal(1, students[0].ProjectWinner);
    Assert.Equal(3, students[1].ProjectWinner);
    Assert.Equal(2, students[2].ProjectWinner);

    Assert.Equal(4, score);
}

[Fact]
public void Given3StudentsAnd2ChooseTheSameTopButDifferentSecond_OverallRunScoreShouldBe4ie2FirstAndASecond() {
    var listOfStudents = new List<Student>();
    //First choice
    var student0 = new Student { ProjectChoiceA = 1, ProjectChoiceB = 2, ProjectChoiceC = 3, ProjectWinner = 0 };
    //First choice
    var student1 = new Student { ProjectChoiceA = 2, ProjectChoiceB = 1, ProjectChoiceC = 3, ProjectWinner = 0 };
    //Second choice
    var student2 = new Student { ProjectChoiceA = 2, ProjectChoiceB = 3, ProjectChoiceC = 1, ProjectWinner = 0 };
    listOfStudents.Add(student0);
    listOfStudents.Add(student1);
    listOfStudents.Add(student2);

    Tuple<List<Student>, int> tuple = Solve(listOfStudents);
    int score = tuple.Item2;
    List<Student> students = tuple.Item1;
    Assert.Equal(1, students[0].ProjectWinner);
    Assert.Equal(2, students[1].ProjectWinner);
    Assert.Equal(3, students[2].ProjectWinner);

    Assert.Equal(4, score);
}

[Fact]
public void Given3StudentsWhoChoose3DifferentProjectsAsTheirTopDifferentOrder_OverallRunScoreShouldBe3WhichIsPerfectFor3Students() {
    var listOfStudents = new List<Student>();
    var student0 = new Student { ProjectChoiceA = 2, ProjectChoiceB = 3, ProjectChoiceC = 1, ProjectWinner = 0 };
    var student1 = new Student { ProjectChoiceA = 1, ProjectChoiceB = 2, ProjectChoiceC = 3, ProjectWinner = 0 };
    var student2 = new Student { ProjectChoiceA = 3, ProjectChoiceB = 1, ProjectChoiceC = 2, ProjectWinner = 0 };
    listOfStudents.Add(student0);
    listOfStudents.Add(student1);
    listOfStudents.Add(student2);

    Tuple<List<Student>, int> tuple = Solve(listOfStudents);
    int score = tuple.Item2;
    List<Student> students = tuple.Item1;
    Assert.Equal(2, students[0].ProjectWinner);
    Assert.Equal(1, students[1].ProjectWinner);
    Assert.Equal(3, students[2].ProjectWinner);

    Assert.Equal(3, score);
}

Okay, so a very simple brute force way.  Next challenge will be to scale up to more than 3 projects and 3 students without doing nested if statements.  I think recursion will be the way: http://www.programgood.net/2012/06/05/Recursion.aspx

As I am now spiking, time to do a Git branch.

| | #