This week's algorithm From TopCoder (Level 250)

[Seabook]

Problem Statement
   
       xxxxx...
       ....xxxx
       .x.....x
       .xxxxxxx
Your are given a picture of a snake. Lowercase 'x' characters indicate parts of the snake, and '.' characters represent empty areas. The snake consists of a sequence of horizontal and vertical segments. Successive segments in the snake share an 'x', which is considered to be in both segments. No two 'x's from different segments of the snake are horizontally or vertically adjacent.
Given a String[] snake, return the length of the longest segment in the snake. The picture is formed using successive elements of snake as successive rows in the picure.
Definition
   
Class:
Snaky
Method:
longest
Parameters:
String[]
Returns:
int
Method signature:
int longest(String[] snake)
(be sure your method is public)
   

Constraints
-
snake contains between 1 and 50 elements, inclusive.
-
Each element of snake contains the same number of characters.
-
Each element of snake contains between 1 and 50 characters, inclusive.
-
Each character in each element of snake is a period ('.') or a lowercase 'x'.
-
If two 'x's are adjacent to each other in the picture, they are in the same segment.
-
The picture shows just one connected snake, using at least 2 'x's.
Examples
0)

   
{"x.xxx.xxx",
 "x.x.x.x.x",
 "xxx.xxx.x"}
Returns: 3
This snake consists of 9 segments, each of length 3.
1)

   
{"xxxx..",
 "...x..",
 "...x..",
 "......"}
Returns: 4
One segment is length 4, the other is length 3.
2)

   
{"...x................",
 "...x................",
 "....................",
 "...................."}
Returns: 2

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]

Have fun guys, put this at the top and actively reply on this is all you need to do.

[Seabook]

Seems quite easy, but hard to pick up a really cool algorithm to deal with this.
Are you gonna search every dot?

Thanks,
Seabook

[Seabook]

Algorithm Sucks, but I add some GUI stuff to present the snake which is not too bad.
Trying to do the boring algorithm with Swing stuff, which is more fun.
Check it out.

package com.seabook.google.algorithm;

import java.awt.Color;
import java.awt.Container;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.GridLayout;
import java.awt.event.ItemEvent;
import java.awt.event.ItemListener;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.ArrayList;
import java.util.List;

import javax.swing.BorderFactory;
import javax.swing.Box;
import javax.swing.BoxLayout;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.SwingConstants;
import javax.swing.border.Border;

public class Snaky extends JPanel {
    public static final String[] snake1 = new String[] { "x.xxxxxxx","x.x.x.x.x",
     "xxx.xxx.x"};
           
    public static final String[] snake2 = new String[] { "xxxx..", "...x..",
            "...x..", "......" };
    public static final String[] snake3 = new String[] {
            "...x................", "...x................",
            "....................", "...................." };
    public static final String[] snake4 = new String[] { "xxxxx...",
            "....xxxx", ".x.....x", ".xxxxxxx" };
   
    private JLabel sizeValueLable;
   
    public Snaky() {
        Border paneEdge = BorderFactory.createEmptyBorder(0, 10, 10, 10);
        Border blackline = BorderFactory.createLineBorder(Color.black);
       
        JPanel container = new JPanel();
        container.setBorder(paneEdge);
        container.setPreferredSize(new Dimension(500, 500));
        container.setLayout(new BoxLayout(container, BoxLayout.Y_AXIS));

        addCompForBorder(blackline,"snake1", parseSankes(snake1), container);
        addCompForBorder(blackline,"snake2", parseSankes(snake2), container);
        addCompForBorder(blackline,"snake3", parseSankes(snake3), container);
        addCompForBorder(blackline,"snake4", parseSankes(snake4), container);
       
        JPanel labelPanel = new JPanel(new GridLayout(1, 0));
        JLabel sizeLable = new JLabel("Longest: ", SwingConstants.LEFT);
        sizeValueLable = new JLabel("value", SwingConstants.LEFT);
        labelPanel.add(sizeLable);
        labelPanel.add(sizeValueLable);
       
       
        container.add(labelPanel);
       
        this.add(container);
    }

    public static void main(String[] args) {

        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI();
            }

        });
    }

    private String[] parseSankes(String[] snakes) {
        List<String> snakeList = new ArrayList<String> ();
        for (String snake: snakes ) {
            String modifiedSnake = snake.replace(".", "~");
            snakeList.add(modifiedSnake);
        }
       
        return snakeList.toArray(new String[0]);
    }

    private static void createAndShowGUI() {
        JFrame frame = new JFrame("Snaky");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // Create and set up the content pane.
        Snaky snakyPane = new Snaky();
        snakyPane.setOpaque(true); // content panes must be opaque
       
        frame.setContentPane(snakyPane);

        // Display the window.
        frame.pack();
        frame.setVisible(true);
    }
   
    private void addCompForBorder(Border border, String name, String[] snake, Container container) {
        int x = snake[0].length() * 15;
        int y = snake.length * 25;
       
        JPanel snakePanel = new SnakeDrawPanel(name, snake, x, y, Snaky.longest(snake));
        snakePanel.setBorder(border);
       
        container.add(Box.createRigidArea(new Dimension(0, 10)));
        container.add(snakePanel);
    }
   
    public static int longest(String[] snake) {
        if (snake == null || snake.length == 0) {
            throw new RuntimeException("Snake can't be empty!");
        }
       
        int segments = snake.length;
        int segmentLength = snake[0].length();
        int longestHorizontal = 0;
        int tempLongest = 0;
        for (int i = 0; i < segments; i++) {
            String segment = snake[i];
            for (int j = 0; j < segmentLength; j++) {
                if ("x".equals(String.valueOf(segment.charAt(j)))) {
                    tempLongest ++ ;
                } else if (".".equals(String.valueOf(segment.charAt(j)))) {
                    if (longestHorizontal < tempLongest) {
                        longestHorizontal = tempLongest;
                    }
                    tempLongest = 0;
                }
               
                if (j == segmentLength - 1) {
                    if (longestHorizontal < tempLongest) {
                        longestHorizontal = tempLongest;
                    }
                    tempLongest = 0;
                }
            }
        }
       
        int longestVertical = 0;
        tempLongest = 0;
        for (int i = 0; i < segmentLength; i++) {
            for (int j = 0; j < segments; j++) {
                if ("x".equals(String.valueOf(snake[j].charAt(i)))) {
                    tempLongest ++ ;
                } else if (".".equals(String.valueOf(snake[j].charAt(i)))) {
                    if (longestVertical < tempLongest) {
                        longestVertical = tempLongest;
                    }
                    tempLongest = 0;
                }
               
                if (j == segments - 1) {
                    if (longestVertical < tempLongest) {
                        longestVertical = tempLongest;
                    }
                    tempLongest = 0;
                }
            }
        }
        return ((longestHorizontal - longestVertical) >=0) ? longestHorizontal : longestVertical;
    }
   
    private class SnakeDrawPanel extends JPanel implements ItemListener {
        private int propX;
        private int propY;
        private String name;
        private int longest;
       
       
        private String[] draws;
       
        public SnakeDrawPanel(String name, String[] draws, int x, int y, int longest) {
            this.name = name;
            this.draws = draws;
            this.propX = x;
            this.propY = y;
            this.longest = longest;
           
            this.addMouseListener(new MouseAdapter() {
                @Override
                public void mouseClicked(MouseEvent e) {
                    SnakeDrawPanel panel = (SnakeDrawPanel) e.getSource();
                    sizeValueLable.setText(panel.name + "'s longest sgemnt is: " + panel.longest);
                }
            });
           
        }
       
       
       
        @Override
        public Dimension getPreferredSize() {
            return new Dimension(propX, propY);
        }
       
        public void paintComponent(Graphics g) {
            super.paintComponent(g);
            g.setFont(new Font(Font.SANS_SERIF, Font.BOLD, 20));
           
            for (int i = 0; i < draws.length; i++) {
                g.drawString(draws[i], 10, (i + 1) * 20);
            }
        }

        @Override
        public void itemStateChanged(ItemEvent e) {
            if (e.getStateChange() == ItemEvent.SELECTED) {
                sizeValueLable.setText("Selected");
            }
        }
       
    }
   
}


 Thanks,
Seabook

[Seabook]

No body check out my awesome Swing Demo of this algorithm?
That's too bad. I am not happy at all. hahaha ....

Thanks,
Seabook