package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
/**
* Created by nemo_odissey on 10.07.2017 12:45 for
* <a href="https://toster.ru/q/440261?utm_source=email_notifications&utm_medium=email&utm_content=mention&utm_campaign=notifications#comment_1428657" >Какую сортировку применять?</a>.
*/
public class JapanEditor
{
/**
* Class to store vocabulary item and make it comparable only lexicographically
*/
public static class WordItem implements Comparable
{
public String word;
public int count;
public WordItem( String word, int count )
{
this.count = count;
this.word = word.split( "/",0 )[0];
}
@Override
public int compareTo( Object obj )
{
return this.word.compareTo( ((WordItem)obj).word );
}
public int compareByFrequency( Object obj )
{
return this.count - ((WordItem)obj).count;
}
}
/**
* Сортирует и извлекает из массива source начиная с индекса pos1 и до индекса pos2 (не включая его самого) максимальные элементы,
* по размеру массива result или меньше.
* @param maxLen максимальный размер массива с максимальными элементами
* @param dstList {@link ArrayList} для размещения результатов работы. Если {@code null}, то будет создан внутри. Очищается перед работой и заполняется результатами
* @param source исходный массив
* @param pos1 начальный индекс массива source
* @param pos2 конечный инидекс в массиве source (не включается в сортировку)
* @return {@link ArrayList} (не может быть {@code null})
*/
public static final ArrayList<WordItem> partialSort( int maxLen, ArrayList<WordItem> dstList, WordItem[] source, int pos1, int pos2 )
{
if ( dstList == null )
dstList = new ArrayList<WordItem>( 10 );
else
dstList.clear();
dstList.add( source[ pos1++ ] );
// Проверим все слова с префиксом на предмет их частоты и отберём до 10 самых часто встречающихся
for( int i = pos1; i< pos2; i++ )
{
WordItem item = source[ i ];
int placeFound = 0;
int listPos;
int cmp;
// Найдём, надо ли вставлять и куда вставить
for ( listPos = dstList.size() - 1; listPos >= 0; listPos-- )
{
if ( ( cmp = item.compareByFrequency( dstList.get( listPos ) ) ) < 0 ) // нашли элемент из списка проверенных, который больше проверяемого
break; // дальше не идём, может сможем добавить в конец списка, если там ещё есть место
if (cmp == 0) // по частоте он равен
if ( item.compareTo( dstList.get( listPos ) ) > 0 ) // но элемент из списка проверенных оказался меньше лексически
break;
}
// пытаемся вставить в массив либо на место элемента, который меньше, либо в конец списка, если там ещё есть место
if ( listPos == (dstList.size()-1) ) // младший элемент списка больше проверяемого элемента, попробуем просто сдобавить в конец
{
if ( dstList.size() < maxLen ) // массив результата ещё не полон, добавляем в конец
dstList.add( item );
continue; // переходим к следующему элементу
}
// нашли, куда вставить
if ( dstList.size() == maxLen )
{
// массив результата уже полностью заполнен, сразу удаляем нижний,
// т.к. он выйдет за разрешённые пределы при вставке нового элемента
dstList.remove( maxLen - 1 );
}
// вставляем ниже большего элемента, или, если listPos == -1, вместо самого большого
dstList.add( listPos + 1, item );
}
return dstList;
}
/**
* Обработки ошибок НЕТ
* @param args путь_к_файлу_с_данными, где хранится задание
* @throws IOException
*/
public static void main( String[] args ) throws IOException
{
long start = System.nanoTime();
BufferedReader brd = java.nio.file.Files.newBufferedReader( Paths.get( args[ 0 ] ), Charset.forName( "utf-8" ) );
// читаем число слов
int wordCnt = Integer.parseInt( brd.readLine() );
WordItem[] wordArr = new WordItem[wordCnt];
// Читаем все слова и их частоты
for(int i = 0; i < wordCnt; i++)
{
String word = brd.readLine();
String[] elems = word.split( " " );
wordArr[ i ] = new WordItem( elems[0], Integer.parseInt( elems[1] ) );
// wordArr[ i ] = new WordItem( word.toLowerCase(), freq );
}
// сортируем массив словаря
Arrays.sort( wordArr );
// считываем и обрабатываем каждый префикс один за другим
int prefCnt = Integer.parseInt( brd.readLine() );
System.out.printf( "Счётчик слов %d, счётчик префиксов %d\n", wordCnt, prefCnt );
System.out.printf( "Словарь считан и отсортирован за %,f млс.\n\n", 1e-9 * (System.nanoTime() - start) );
int summaryWordCount = 0;
WordItem prefixItem = new WordItem( "", 1 );
ArrayList<WordItem> list = new ArrayList<>( 11 );
for(int i = 0; i < prefCnt; i++)
{
String prefix = brd.readLine().trim();
prefixItem.word = prefix;
int pos1 = Arrays.binarySearch( wordArr, prefixItem ); // if positive, point to a word in vocabulary started from prefix or equal to it
if ( pos1 < 0) // no precise prefix value found in vocabulary
pos1 = -(pos1 + 1); // pos1 to the first element starting from prefix
if ( pos1 >= wordCnt) // префикс отсутствует в словаре
continue;
System.out.printf( " ~ %s\n", prefix );
if ( wordArr[pos1].word.startsWith( prefix ) ) // Если префикс есть, ищем последнюю его позицию в словаре
{
char nextLastChar = prefix.charAt( prefix.length() - 1 );
prefixItem.word = prefix.substring( 0, prefix.length() -1 ) + (++nextLastChar); // готовим следующую не строку
int pos2 = Arrays.binarySearch( wordArr, pos1, wordCnt, prefixItem ); // ищем последнее вхождение префикса в словаре
if ( pos2 < 0)
pos2 = -pos2 -1;
if ( pos2 > wordCnt)
pos2 = wordCnt;
summaryWordCount += pos2 - pos1;
list = partialSort( 10, list, wordArr, pos1, pos2 );
for( WordItem item: list )
System.out.printf( "%6d %s\n", item.count, item.word );
}
}
brd.close();
System.out.printf( ">>> Длительность обработки %,f сек., средний размер выборки по каждому префиксу %d\n", 1e-9 * (System.nanoTime() - start), summaryWordCount / prefCnt);
}
}
В данном случае мы наблюдаем шкалу градаций серого из 3-х вариантов: чёрный (тёмный), серый (промежуточный) и белый(светлый). Возможно, это сделано их целей экономии или по каким-либо иным соображениям.
Цветными эти серые изображения я бы не стал называть. Ранее (когда была самостоятельная техническая культура и страна) их называли "256 градаций серого". Назвать их серыми цветами тоже можно, но звучит как то не информативно.
Хранить в коде эти картинки можно как угодно, Зависит это, скорее всего, от контроллера, формирующего картинку. Есть стандартные форматы, известные во всех ОС, на любых процессорах, позволяющие хранить битовые картинки (BMP,PNG,GIF,TIF и т.д.). Но они нужны чисто для хранения на внешних носителях и передачи между компьютерами.
А в тамагочи разрабы вполне могли обойтись хранящимися в ПЗУ битовыми масками. Тогда проще всего хранить изображение из 3 градаций серого в 2-х битовых маскированых матрицах (2 бита на пиксель, все значения 00,01,10,11). И даже остаётся ещё одно избыточное значение, которое тоже можно куда-либо приспособить, например, как признак отсутствие значения(цвета), как раз это и были бы прозрачные пикселы, формирующие внешнюю форму (маску) объекта.