Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / Проблема с TopCoder-а / 15 сообщений из 15, страница 1 из 1
23.07.2013, 17:22:07
    #38340989
Vigoole
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
Вот проблема с TopCoder-a, я ее сделал. Но за такое можно свобоно оторвать мне руки. Как мне избежать такой вложоности if/for, как по другому написать чтоб было понятно и другим ?
Проблема

Problem Statement

Sometimes when computer programs have a limited number of colors to use, they use a technique called dithering. Dithering is when you use a pattern made up of different colors such that when the colors are viewed together, they appear like another color. For example, you can use a checkerboard pattern of black and white pixels to achieve the illusion of gray.
You are writing a program to determine how much of the screen is covered by a certain dithered color. Given a computer screen where each pixel has a certain color, and a list of all the solid colors that make up the dithered color, return the number of pixels on the screen that are used to make up the dithered color. Each pixel will be represented by a character in screen. Each character in screen and in dithered will be an uppercase letter ('A'-'Z') representing a color.
Assume that any pixel which is a color contained in dithered is part of the dithered color.
Definition

Class:
ImageDithering
Method:
count
Parameters:
String, String[]
Returns:
int
Method signature:
int count(String dithered, String[] screen)
(be sure your method is public)


Constraints
-
dithered will contain between 2 and 26 upper case letters ('A'-'Z'), inclusive.
-
There will be no repeated characters in dithered.
-
screen will have between 1 and 50 elements, inclusive.
-
Each element of screen will contain between 1 and 50 upper case letters ('A'-'Z'), inclusive.
-
All elements of screen will contain the same number of characters.
Examples
0)

"BW"
{"AAAAAAAA",
"ABWBWBWA",
"AWBWBWBA",
"ABWBWBWA",
"AWBWBWBA",
"AAAAAAAA"}
Returns: 24
Here, our dithered color could consist of black (B) and white (W) pixels, composing a shade of gray. In the picture, there is a dithered gray square surrounded by another color (A).
1)


"BW"
{"BBBBBBBB",
"BBWBWBWB",
"BWBWBWBB",
"BBWBWBWB",
"BWBWBWBB",
"BBBBBBBB"}
Returns: 48
Here is the same picture, but with the outer color replaced with black pixels. Although in reality, the outer pixels do not form a dithered color, your algorithm should still assume they are part of the dithered pattern.
2)


"ACEGIKMOQSUWY"
{"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX"}
Returns: 150
A picture of vertical stripes, every other stripe is considered part of the dithered color.
3)


"CA"
{"BBBBBBB",
"BBBBBBB",
"BBBBBBB"}
Returns: 0
The dithered color is not present.
4)


"DCBA"
{"ACBD"}
Returns: 4
The order of the colors doesn't matter.
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.


Мой код
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
public class ImageDithering {

	public static int count(String dithered, String[] screen) {
		int answer = 0;
		if (dithered.length() >= 2 && dithered.length() <= 26)
			if (dithered.matches("[A-Z]*"))
				if (screen.length >= 1 && screen.length <= 50)
					for (int i = 0, j = screen[0].length(); i < screen.length; i++) {
						if (screen[i].matches("[A-Z]*")
								&& j == screen[i].length()) {
							if (screen[i].matches("["+dithered+"^[A-Z]]*")) {
								for (int k = 0; k < dithered.length(); k++) {
									for (int n = 0; n < screen[i].length(); n++) {
										if(dithered.charAt(k)==screen[i].charAt(n))
											answer++;
									}
								}
							}
						}
						else System.exit(1);
						
					}

		return answer;
	}

	public static void main(String[] args) {
		String tt = "BW";
		String[] strArray = { "AAAAAAAA", 
				      "ABWBWBWA", 
				      "AWBWBWBA", 
				      "ABWBWBWA",
				      "AWBWBWBA", 
				      "AAAAAAAA" };
		System.out.println(tt.length());
		System.out.println(ImageDithering.count(tt, strArray));

	}
}

...
Рейтинг: 0 / 0
23.07.2013, 17:25:53
    #38340996
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
Вы бы начали с табуляции. А то косоглазие сторо будет от восьми пробелов на отступ.
...
Рейтинг: 0 / 0
23.07.2013, 17:29:37
    #38341009
Vigoole
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
Табуляция нормальная но когда ставил код из эклипс тут по другому все выглядит, и какбудто нажимал 2 раза таб.
...
Рейтинг: 0 / 0
23.07.2013, 17:41:50
    #38341043
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
VigooleТабуляция нормальная но когда ставил код из эклипс тут по другому все выглядит, и какбудто нажимал 2 раза таб.
Ну, дык перенастройте на 4.
...
Рейтинг: 0 / 0
23.07.2013, 17:44:56
    #38341051
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
Первые три блока - превалидация. Их лучше отделить от реализации логики.

Код: java
1.
2.
3.
4.
5.
6.
7.
if (!(dithered.length() >= 2 && dithered.length() <= 26)) return 0;
if (!(dithered.matches("[A-Z]*")))  return 0;
if (!(screen.length >= 1 && screen.length <= 50)) return 0;

for (int i = 0, j = screen[0].length(); i < screen.length; i++) {
  ...						
}



else System.exit(1); - тоже сильный ход.
...
Рейтинг: 0 / 0
23.07.2013, 17:55:04
    #38341078
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
переменная i не нужна. enhanced for loop будет проще. Переменная j хранит длину, а не индекс вводит читателя в заблуждение.
...
Рейтинг: 0 / 0
23.07.2013, 18:59:39
    #38341174
rfq
rfq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
BlazkowiczПервые три блока - превалидация. Их лучше отделить от реализации логики.

Код: java
1.
2.
3.
4.
5.
6.
7.
if (!(dithered.length() >= 2 && dithered.length() <= 26)) return 0;
if (!(dithered.matches("[A-Z]*")))  return 0;
if (!(screen.length >= 1 && screen.length <= 50)) return 0;

for (int i = 0, j = screen[0].length(); i < screen.length; i++) {
  ...						
}



else System.exit(1); - тоже сильный ход.
Поддерживаю.
Аналогично меняется:,
Код: java
1.
2.
if (screen[i].matches("[A-Z]*") &&  j == screen[i].length()) System.exit(1);
if (screen[i].matches("["+dithered+"^[A-Z]]*")) continue;
...
Рейтинг: 0 / 0
23.07.2013, 19:02:07
    #38341180
Vigoole
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
Blazkowiczelse System.exit(1); - тоже сильный ход.
Недавно написал простую программку и выдавало какуюту ошибку в eclipse связано с JRE так нашол что можно обойти именно с этой команды.
Табуляция по умолчанию настроена на 4
Спс за ответы
...
Рейтинг: 0 / 0
23.07.2013, 19:02:19
    #38341181
rfq
rfq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
rfqАналогично меняется:,
Код: java
1.
2.
if (screen[i].matches("[A-Z]*") &&  j == screen[i].length()) System.exit(1);
if (screen[i].matches("["+dithered+"^[A-Z]]*")) continue;



Забыл обратить булевы значения условий.
...
Рейтинг: 0 / 0
23.07.2013, 19:04:49
    #38341184
rfq
rfq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
VigooleТабуляция по умолчанию настроена на 4
Спс за ответы
Это она в Эклипсе настроена на 4. В тексте ставится символ '\t', а здесь он считается за 8. Лучше избавьтесь от табуляций в тексте вообще, пишите одни пробелы - в Эклипсе есть такая опция.
...
Рейтинг: 0 / 0
23.07.2013, 19:49:33
    #38341235
ivanra
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
А еще лучше попытаться сначала найти правильное решение, и потом заниматься украшательствами.
- судя по примеру №2 должны учитываться не только горизонтальные, но и вертикальные совпадения. Приведенное решение ищет только в строках
- судя по примеру №3 учитываются "разреженные" совпадения
вывод: Задача сформулирована небрежно, либо примеры неправильные.

Подозреваю, что можно обобщить на диагонали и ломанные.
Исходя из этого обобщения решение следующее:
- весь массив свалить в кучу
- убедиться что в этой куче есть все символы из шаблона (решается в один проход с помощью HashSet)
- в этом же проходе выкинуть все лишние символы
- посчитать результат
...
Рейтинг: 0 / 0
23.07.2013, 21:48:18
    #38341371
Vigoole
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
ivanraА еще лучше попытаться сначала найти правильное решение, и потом заниматься украшательствами.
- судя по примеру №2 должны учитываться не только горизонтальные, но и вертикальные совпадения. Приведенное решение ищет только в строках
- судя по примеру №3 учитываются "разреженные" совпадения
вывод: Задача сформулирована небрежно , либо примеры неправильные.

Подозреваю , что можно обобщить на диагонали и ломанные.
Исходя из этого обобщения решение следующее:
- весь массив свалить в кучу
- убедиться что в этой куче есть все символы из шаблона (решается в один проход с помощью HashSet)
- в этом же проходе выкинуть все лишние символы
- посчитать результат

Обратите внимания в проблеме одномерный масив строк
...
Рейтинг: 0 / 0
23.07.2013, 21:58:13
    #38341377
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
VigooleОбратите внимания в проблеме одномерный масив строк
Problem в данном контексте - "задача", а не "проблема"
...
Рейтинг: 0 / 0
23.07.2013, 21:59:15
    #38341379
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
VigooleНедавно написал простую программку и выдавало какуюту ошибку в eclipse связано с JRE так нашол что можно обойти именно с этой команды.
Т.е. "не знаю что было, не знаю зачем сделал, но есть как есть"
...
Рейтинг: 0 / 0
24.07.2013, 09:35:57
    #38341588
ivanra
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Проблема с TopCoder-а
По оформлению: ограничения (constraints) обычно не проверяются, это то, что "дано", на вход подаются данные уже удовлетворяющие перечисленным условиям. Понятно, что лишняя проверка не повредит, но в общем случае это лишний код:
Код: java
1.
2.
3.
4.
if (dithered.length() >= 2 && dithered.length() <= 26)
if (dithered.matches("[A-Z]*"))
if (screen.length >= 1 && screen.length <= 50)
if (screen[i].matches("[A-Z]*") && j == screen[i].length()) {


Но если очень хочется, то проверку можно вынести в отдельный метод.

По самому решению. Вот массив из 2 примера:
Код: java
1.
2.
3.
4.
5.
6.
BBBBBBBB
BBWBWBWB
BWBWBWBB
BBWBWBWB
BWBWBWBB
BBBBBBBB


Все 48 "пикселей" этого массива удовлетворяют шаблону BW, в том числе и угловые, отсюда и можно сделать вывод, что учитываются не только горизонтальные, но и вертикальные и диагональные совпадения (и даже ходы "конем"). То есть пиксели не должны стоять рядом, достаточно найти любое совпадение. Для примера, такой массив должен тоже дать в результате 48:
Код: java
1.
2.
3.
4.
5.
6.
WBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB


Далее просто обобщаем на ломанные в случае с более длинными шаблонами. В конце концов, в условиях задачи нигде не сказано, что пиксели должны составлять линию, либо находиться на определенном расстоянии друг от друга.

Ну, и отсюда решение:
- проверить, что на экране есть все пиксели из шаблона, если это не так, результат 0.
- посчитать на экране те пиксели, которые имеются в шаблоне - это и есть ответ.
Я предложил решать с помощью множеств, но это для ленивых, более эффективный алгоритм можно написать с использованием целочисленных массивов.
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / Проблема с TopCoder-а / 15 сообщений из 15, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]