Weekend Algorithm. Happy coding.

Seabook

unread,

Aug 26, 2011, 8:04:26 AM8/26/11

to happy-pr...@googlegroups.com

Problem Statement

There's a group of people sitting in a row of seats. Each seat can hold only one person. Your goal is to arrange the people so they're all sitting together and there are no empty seats between people. You are given a String[] s representing the row of seats from left to right. The ith element of s is '.' if the ith seat is empty and uppercase 'X' if it's occupied. Each seat is one unit of length wide. There is no space between adjacent seats.
The distance that one person needs to travel to relocate from the ith seat to the jth seat is the absolute value of (i - j) units. Return the minimum possible total distance in units that the people must travel in order to achieve your goal.
Definition

Class:
ChangingSeats
Method:
getDistance
Parameters:
String
Returns:
int
Method signature:
int getDistance(String s)
(be sure your method is public)


Constraints
-
s will contain between 1 and 50 characters, inclusive.
-
s will contain the characters '.' and uppercase 'X' only.
Examples
0)


"X.X"
Returns: 1

1)


"X.X.XXX"
Returns: 3
Let's number the people from 1 to 5 (left to right). To make them all sit together, we can move person 2 one seat to the right and person 1 two seats to the right. The resulting configuration is "..XXXXX". Another way to achieve this is to move person 1 three seats to the right. Either way, the total distance is 3 units.
2)


"....X.X.X.X.XXXXX"
Returns: 10

3)


".XXXXX..........X.X.XX......X.XX...."
Returns: 81

4)


"...................."
Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Seabook

unread,

Aug 30, 2011, 1:28:48 AM8/30/11

to happy-pr...@googlegroups.com

Interesting problem.

1) Find the largest consecutive number of seats which is occupied. Keep them stay.
2) move other people all around.

Is that gonna be the best alogrithm?

Thanks,
Seabook

Seabook

unread,

Aug 30, 2011, 8:53:12 AM8/30/11

to happy-pr...@googlegroups.com

Found an interesting place to do the algorithm.
http://codingbat.com/

Not too bad do some small coding. LOL.

Thanks,
Seabook

Seabook

unread,

Aug 30, 2011, 7:49:50 PM8/30/11

to happy-pr...@googlegroups.com

A good place to learn Python.
http://code.google.com/edu/languages/google-python-class/

Thanks,
Seabook

Seabook

unread,

Sep 6, 2011, 3:01:43 AM9/6/11

to happy-pr...@googlegroups.com

It's pity that no one do this algorithm.
This one is a bit of difficult I have to admit. But I always would like to challenge my self. :-)

Thanks,
Seabook

Seabook

unread,

Sep 6, 2011, 3:04:01 AM9/6/11

to happy-pr...@googlegroups.com

Here is a new algorithm for fun.
http://codingbat.com/prob/p183562

Ok smarties, see if you can solve the Java makeBricks() problem in 1 try (not counting compile errors of course) .

Actually I tried twice for the completely pass. : - )

Do some coding today. LOL.

Thanks,
Seabook

Seabook

unread,

Sep 13, 2011, 9:25:14 AM9/13/11

to happy-pr...@googlegroups.com

Seems no one continues to do the coding stuff these days.
And I will use Javascript to write the code.

Here is the answer for the makeBricks();

public class MakeBricks {
    public boolean makeBricks(int small, int big, int goal) {
        //Basic Checks to make sure small && big && goal > 0;
        //TODO

        int maxLength = small + 5 * big;

        if (goal > maxLength) {
            return false;
        }

        int howManyBigBricks = goal / 5;

        if (howManyBigBricks >= big) {
            howManyBigBricks = big;
        }

        int leftOver = goal - 5 * howManyBigBricks;

        if (leftOver == 0) {
            return true;
        } else {
            return leftOver <= small;
        }
    }

    public static void main(String[] args) {
        MakeBricks mb = new MakeBricks();
        mb.makeBricks(3, 2, 9);
    }

}

Seabook

unread,

Sep 14, 2011, 9:00:19 AM9/14/11

to happy-pr...@googlegroups.com

I thought it was tough to do some complex algorithm.
Let's take it easy and do some simple little easy ones, which may boost your confidence a bit.
Here is the one:
http://codingbat.com/prob/p130788

Thanks
Seabook

Seabook

unread,

Sep 14, 2011, 9:24:48 AM9/14/11

to happy-pr...@googlegroups.com

Honestly Super Easy.

<!DOCTYPE html>
<html>
<head>
    <style type="text/css">
        .resultPassed {
            color:green;
        }

        .resultFailed {
            color:red;
        }
    </style>
    <script>
        function luckySum(a, b, c) {
            if (a == 13) {
                return 0;
            } else if (b == 13) {
                return a;
            } else if (c == 13) {
                return a + b;
            } else {
                return a + b + c;
            }
        }

        function print(value, assertStr) {
            if (value === true) {
                document.write("<p class='resultPassed'>" + assertStr + " ===> " + value + "</p>");
            } else {
                document.write("<p class='resultFailed'>" + assertStr + " ===> " + value + "</p>");
            }

        }

        function doAssert(expected, passIn) {
            if (expected === passIn) {
                return true;
            } else {
                return false;
            }
        }
    </script>
</head>
<body>
    <div id="testLuckySum">
        <h3>testLuckySum</h3>
        <script type="text/javascript">
            print(doAssert(6, luckySum(1, 2, 3)), "luckySum(1, 2, 3)");
            print(doAssert(3, luckySum(1, 2, 13)), "luckySum(1, 2, 13)");
            print(doAssert(1, luckySum(1, 13, 3)), "luckySum(1, 13, 3)");
            print(doAssert(1, luckySum(9, 4, 13)), "luckySum(9, 4, 13)");
        </script>
    </div>
</body>
</html>

Seabook

unread,

Oct 7, 2011, 12:37:55 AM10/7/11

to happy-pr...@googlegroups.com

/**
* Glen's solution for this. Not sure whether it is 100% correct.
* It's for the seating problems.
*/

public class ChangingSeats {

public int getDistance(String s) {

boolean[] seats = new boolean[s.length()];

float people = 0;

for (int i = 0; i < s.length(); i++) {

seats[i] = s.charAt(i) == 'X';

if (seats[i])

people++;

}

// Find the "centre of gravity" of the people - moves will be made toward that

float seatMass = 0;

for (int i = 0; i < seats.length; i++)

if (seats[i])

seatMass += i;

// Find the "centre" position

int centre = (int) Math.round(seatMass / people);

// The answer is the total gaps between each person and the centre

int totalMoves = 0;

for (int i = 0; i < seats.length; i++)

if (seats[i]) {

// Add the total gaps between i and centre

if (i < centre) {

for (int j = i + 1; j <= centre; j++)

if (!seats[j])

totalMoves++;

} else if (i > centre) {

for (int j = centre + 1; j < i; j++)

if (!seats[j])

totalMoves++;

}

return totalMoves;

}

private static boolean test(String string, int expected) {

int actual = new ChangingSeats().getDistance(string);

if (actual == expected) {

System.out.println("Result correct for '" + string + "' = " + actual);

return true;

}

System.out.println("Incorrect result for '" + string + "'. Expected " + expected + ", but was " + actual);

return false;

}

public static void main(String[] args) {

boolean ok = true;

ok &= test("X.X", 1);

ok &= test("X.X.XXX", 3);

ok &= test("....X.X.X.X.XXXXX", 10);

ok &= test(".XXXXX..........X.X.XX......X.XX....", 81);

ok &= test("....................", 0);

ok &= test("........X............", 0);

ok &= test("X", 0);

if (ok)

System.out.println("All tests passed");

}

Reply all

Reply to author

Forward