Вычисление координат в матрице

#c_sharp #алгоритм #математика #геометрия #вычислительная_геометрия

Есть 5x5 матрица квадратов в произвольной части экрана. Как найти координаты (x,
y) в центре каждого квадрата?


    

Ответы

Ответ 1

координатные оси вправо и вниз

l, t, r, b = координаты матрицы
s = ширина разделительной линии (отступы по краям ей тоже равны)
n, m = количество прямоугольников по вертикали и горизонтали

w = (r-l - s * (m+1)) / m
h = (t-b - s * (n+1)) / n

x0 = l + s + w / 2
y0 = t + s + h / 2

i, j = номера строки и столбца в 0-индексации

x = x0 + (w+s)*i
y = y0 + (h+s)*j


PS: Если значения (даже промежуточные) дробные, то при реализации алгоритма имеет
смысл сделать всё одной формулой, чтобы умножение что до деления.

PPS: Если отступов по краям нет, то вместо +1 надо использовать -1.

Переконвертация UTF8 <> 1251 и большая буква “И”

#java #utf_8 #encoding #cp1251

Берем строку "Игра!" и переводим в массив байт (1).
Создаём строку, из этого массива байт, но указываем "неверную" кодировку(2).
В итоге получаем строку с "поехавшей кодировкой"(utf8AsW1251 ).

Выполняем обратные действия(3). 
и видим что строка переконвертировалась нормально за исключение большой буквы "И".
Почему большая буква "И" отображается как �? ?

import java.nio.charset.Charset;

public class Main {
private static final Charset CS_1251 = Charset.forName("windows-1251");
private static final Charset CS_UTF8 = Charset.forName("UTF-8");

public static void main(String[] args) {
    String in = "Игра!";
    byte[] bytesUtf8 = in.getBytes(CS_UTF8);                    //(1)
    String utf8AsW1251 = new String(bytesUtf8, CS_1251);        //(2) 

    System.out.println("utf8 bytes as 1251: " + utf8AsW1251);   //utf8 bytes as 1251:
�гра!

    System.out.println(
            new String(utf8AsW1251.getBytes(CS_1251), CS_UTF8)  //(3) 
    );                                                          //�?гра!
}


}
    

Ответы

Ответ 1

– Доктор, когда я делаю так, у меня болит
  – Не делайте так


Буква И кодируется в utf-8 как последовательность байтов 0xd0, 0x98

Код 0xd0 соответствует символу Р в кодировке cp1251, а вот код 0x98 не соответствует
никакому символу, он просто отсутствует в кодировке, поэтому вместо несуществующего
символа будет подставлен заменяющий. Получится строка Р�.

Cимвол � тоже отсутсвует в cp1251, поэтому при повторном кодировании будет заменен
на ? (с кодом 0x3f), получаем последовательность байтов 0xd0, 0x3f.

При декодировании сталкиваемся еще с одной проблемой: последовательность 0xd0, 0x3f
недопустима в utf-8, поэтому теперь уже вместо 0xd0 будет подставлен заменяющий символ,
в итоге получается строка �?

С остальными буквами такого может и не произойти, но это не значит, что подобные
манипуляции всегда будут приводить к правильному результату

Й → 0xd0, 0x99 → Р™ → 0xd0, 0x99 → Й

Поиск максимальной цепочки в последовательности

#python #алгоритм

Имеется к примеру последовательность: [b,ab,bc,bb] из неё надо построить цепочку
вида: ab -> bb -> b -> bc (как понял вариант с b->bb тоже рабочий) и для этого я применял
сначала вот такой алгоритм:

def chains(words, previous_word_index=None):
   yield []
   if previous_word_index is not None:
       previous_letter = words[previous_word_index][-1]
       words = words[:previous_word_index] + words[previous_word_index + 1:]
   for i, each_word in enumerate( words ):
       if previous_word_index is None or each_word.startswith(previous_letter):
           for tail in chains(words, previous_word_index=i):
                yield [each_word] + tail  
print(max(chains(words), key=len))


потом пробовал использовать алгоритм по нахождению эйлерового пути, но там лишнее
выводило и я от него отказался.
Библиотечная функция networkx.dag_longest_path тоже не вариант тк в графе есть цикл
(b->bb, bb->b).

Есть вариант не рекурсивного алгоритма для поиска такой максимальной последовательности?

p.s. без полного перебора.

Ссылка на задачу с её полным описанием: 

atpp.vstu.edu.ru/cgi-bin/arh_problems.pl?id_prb=205

    

Ответы

Ответ 1

Прочитав внимательно и несколько раз условие, ставится понятно, что нужно искать
не максимальный путь, а именно полный путь. 

Если переформулировать условие. У нас есть граф, где вершины - {a..z} а ребро - слово
начинающееся на первую вершину и заканчивающееся на 2. (Да мультиграф, да есть петли).
Нам нужно найти Эйлеров путь. В целом можно уже ничего не писать, а давать ссылку
на википедию) Но вот код на С++ (быстро проверить идею). Основной код достаточно маленький

while (!st.empty()){
    int v = st.top();
    int i;
    for (i=0; i<26; ++i)
        if (G[v][i])
            break;
    if (i == 26){
        res.push_back (v);
        st.pop();
    }
    else {
        G[v][i]--;
        st.push (i);
    }
}


ссылка на запускаемый пример https://ideone.com/zvqa9m

Сложность не больше чем 26*N. (и то можно без 26, но это уже мелочи. успевает с диким
запасом).


Ответ 2

Можно что-то и получше придумать чем это:

import copy


class Item(object):
    def __init__(self, value, items):
        self.value = value
        self.next = self._get_next(items)

    def _get_next(self, items):
        return [item for item in items if self.value[-1] == item[0]]


def copy_dictionary(dictionary):
    return {key: copy.deepcopy(value) for key, value in dictionary.items()}


graph = {}
items = ['b', 'ab', 'bc', 'bb']

for index, item in enumerate(items):
    graph[item] = Item(item, items[:index] + items[index + 1:])

longest_path = []

for item in items:
    tmp_graph = copy_dictionary(graph)
    queue = [[tmp_graph[item]]]
    while queue:
        current_items = queue.pop(0)

        if not current_items[-1].next:
            if len(current_items) > len(longest_path):
                longest_path = current_items
            continue

        for next_item in current_items[-1].next:
            if tmp_graph[next_item].value in [current_item.value for current_item
in current_items]:
                continue
            queue.append(current_items + [tmp_graph[next_item]])


print(' -> '.join([item.value for item in longest_path]))  # 'ab -> b -> bb -> bc'


UPDATE: в предыдущих примерах делал интуитивно то же самое, что и @pavel, но к своему
стыду не знал про Эйлеров граф.

# матрица смежности графа (количество ребер, соединяющих вершины)
graph = [[0] * 26 for _ in range(26)]
# словарь (та же матрица смежности, только вместо количества ребер - массив слов)
dictionary = [[[] for __ in range(26)] for _ in range(26)]
# массив со степенями вершин
deg = [0] * 26
# последовательность слов
stack = []
# массив с индексами позиций слов
result = []

n = int(input())

# если задано всего одно слово, то сразу его и выводим
if n == 1:
    print(input())
else:
    for _ in range(n):
        word = input()
        # первый символ слова (исходящая вершина)
        first_char = ord(word[0]) - ord('a')
        # последний символ слова (входная вершина)
        last_char = ord(word[-1]) - ord('a')
        # увеличиваем количество ребер между этими вершинами
        graph[first_char][last_char] += 1
        # добавляем в словарь
        dictionary[first_char][last_char].append(word)
        # для исходящей вершины повышаем степень
        deg[first_char] += 1
        # для входной понижаем
        deg[last_char] -= 1

    # в результате тестового примера получится следующее:
    #   |  a  |      b      |  c     |
    # --+-----+-------------+--------|
    # a | [ ] | ['ab']      | [ ]    |
    # --+-----+-------------+--------|
    # b | [ ] | ['b', 'bb'] | ['bc'] |
    # --+-----+-------------+--------|
    # c | [ ] | [ ]         | [ ]    |
    # --+----------------------------|

    start = -1
    finish = -1

    # нужно найти подходящую вершину, 
    # с которой лучше начинать составлять последовательность слов
    for index in range(26):
        if deg[index] == 0:
            continue
        # подойдет та вершина, из которой исходящих ребер больше, чем входных
        # (в тестовом примере это 'ab', а 'bc' не подойдет - нет исходящих ребер)
        elif deg[index] == 1 and start == -1:
            start = index
        elif deg[index] == -1 and finish == -1:
            finish = index
        else:
            print('NO')
            exit(0)

    # если идеально подходящих для старта вершин нет, то начинаем по порядку
    if start == -1:
        start = 0

    stack.append(start)

    # обычный алгоритм поиска путей в графе
    while stack:
        vertex = stack[-1]
        index = 0

        while index < 26:
            if graph[vertex][index] > 0:
                break
            index += 1

        if index == 26:
            result.append(vertex)
            stack.pop()
        else:
            graph[vertex][index] -= 1
            stack.append(index)

    if len(result) - 1 != n:
        print('NO')
        exit(0)

    for index in range(len(result) - 1, 0, -1):
        print(dictionary[result[index]][result[index - 1]].pop(0))


Результат: данное решение прошло успешно все тесты.

Диапазон покрытия по всему сроку Python Pandas

#python #pandas

Я хочу рассчитать количество прогрессов по выполнению домашних работ в каждом месяце
за всю историю (каждый месяц в диапазоне от июня 2018 до февраля 2019 включительно)
для каждого курса.
Необходимо учитывать, что прогресс выполнения домашней работы может перетекать из
одного месяца в другой (такие прогрессы надо включать в общее число прогрессов для
всех месяцев, которые покрывает срок выполнения этих домашних работ). 

progress_id – id прогресса,
course – название курса,
start – начало выполнения домашней работы,
finish – конец выполнения домашней работы. 

list_month = ['2018-06', '2018-07', '2018-08', 
              '2018-09', '2018-10', '2018-11', 
              '2018-12', '2019-01', '2019-02']

df_table = pd.DataFrame({'progress_id': ['progress1', 'progress2', 
                                         'progress3', 'progress4', 
                                         'progress5', 'progress6'], 
                         'course': ['course1', 'course2', 'course1', 
                                    'course3', 'course3', 'course4'],
                         'start': ['2018-06', '2018-07', '2018-07', 
                                   '2018-10', '2018-09', '2018-12'], 
                         'finish': ['2018-08', '2018-07', '2018-10', 
                                    '2018-12', '2018-11', '2019-02']
                          }, 
                          columns = ['progress_id','course', 
                                     'start', 'finish'])


Попытка сделать добавление новых строк в конец датафрейма ни к чему не привела: 
 попытка сделать цикл while df_table['start'] != df_table['finish'] с наращиванием
через счетчик значения месяца 'start' до тех пор пока он не будет равен месяцу 'finish'
и добавление нового "промежуточного" месяца в колонку 'finish'. 

Подскажите пожалуйста, как это можно сделать корректно? 
    

Ответы

Ответ 1

df_table.groupby('course') \
   .apply(lambda course: \
      course.apply(lambda x: \
               pd.Series(1, index=pd.date_range(x['start'], x['finish'], closed=None,
freq='MS')) \
               , axis=1) \
            .sum(axis=0)) \
   .reset_index(level=0).pivot(columns='course', values=0) \
   .reindex(pd.date_range(df_table.start.min(), df_table.finish.max(), freq='MS'),
fill_value=np.nan)

course      course1  course2  course3  course4
2018-06-01      1.0      NaN      NaN      NaN
2018-07-01      2.0      1.0      NaN      NaN
2018-08-01      2.0      NaN      NaN      NaN
2018-09-01      1.0      NaN      1.0      NaN
2018-10-01      1.0      NaN      2.0      NaN
2018-11-01      NaN      NaN      2.0      NaN
2018-12-01      NaN      NaN      1.0      1.0
2019-01-01      NaN      NaN      NaN      1.0
2019-02-01      NaN      NaN      NaN      1.0




Вот немного о том. как это работает

Самый внутренний apply превращает каждую строку в Series вот такого вида

2018-12-01  1
2019-01-01  1
2019-02-01  1


Внешний собирает их все по курсам

course             
course1  2018-06-01    1.0
         2018-07-01    2.0
         2018-08-01    2.0
         2018-09-01    1.0
         2018-10-01    1.0
course2  2018-07-01    1.0
course3  2018-09-01    1.0
...


Дальше строим сводную таблицу 

В последней строке заполняем возможные пропуски индекса.


Ответ 2

Вся программа (после импортов и создания вашей таблицы):

for dt in pd.date_range("2018-06-01", "2019-02-01", freq="MS"):
    new_column = str.format("{}-{:02d}", dt.year, dt.month)
    df_table[new_column] = 0

for ind, row in df_table.iterrows():
    start  = row["start"]  + "-01"
    finish = row["finish"] + "-01"
    dtRange = pd.date_range(start, finish, freq="MS")
    for dt in dtRange:
        colName = str.format("{}-{:02d}", dt.year, dt.month)
        df_table.loc[ind, colName] = 1

print(df_table.sum(numeric_only=True))


Вывод:


2018-06    1
2018-07    3
2018-08    2
2018-09    2
2018-10    3
2018-11    2
2018-12    2
2019-01    1
2019-02    1
dtype: int64





Объяснение:


Главная идея:

Как перечислить все месяцы между (например) 2018-12 и 2019-03?
Так что построим объект типа DatetimeIndex с месячной частотой, с первого дня в месяце:

In[3]: pd.date_range("2018-12-01", "2019-02-01", freq="MS")
Out[3]: DatetimeIndex(['2018-12-01', '2019-01-01', '2019-02-01', '2019-03-01'], dtype='datetime64[ns]',
freq='MS')



А теперь постепенно.

Ваша исходная таблица:

In[61]: df_table
Out[61]: 
  progress_id   course    start   finish
0   progress1  course1  2018-06  2018-08
1   progress2  course2  2018-07  2018-07
2   progress3  course1  2018-07  2018-10
3   progress4  course3  2018-10  2018-12
4   progress5  course3  2018-09  2018-11
5   progress6  course4  2018-12  2019-02


Добавим колонки для всея индивидуальных месяцев в вами требуемом диапазоне:

In[62]: for dt in pd.date_range("2018-06-01", "2019-02-01", freq="MS"):
   ...:     new_column = str.format("{}-{:02d}", dt.year, dt.month)
   ...:     df_table[new_column] = 0
   ...:     
In[63]: df_table
Out[63]: 
  progress_id   course    start   finish  2018-06  2018-07  2018-08  2018-09  \
0   progress1  course1  2018-06  2018-08        0        0        0        0   
1   progress2  course2  2018-07  2018-07        0        0        0        0   
2   progress3  course1  2018-07  2018-10        0        0        0        0   
3   progress4  course3  2018-10  2018-12        0        0        0        0   
4   progress5  course3  2018-09  2018-11        0        0        0        0   
5   progress6  course4  2018-12  2019-02        0        0        0        0   

   2018-10  2018-11  2018-12  2019-01  2019-02  
0        0        0        0        0        0  
1        0        0        0        0        0  
2        0        0        0        0        0  
3        0        0        0        0        0  
4        0        0        0        0        0  
5        0        0        0        0        0  


В цикле для каждой строки таблицы сделаем объект типа DatetimeIndex в диапазоне значений
в колонках start и finish, а затем для всякого его элемента в этом объекте запишем
значение 1 для соответствующей колонки:

In[64]: for ind, row in df_table.iterrows():
   ...:     start  = row["start"]  + "-01"
   ...:     finish = row["finish"] + "-01"
   ...:     dtRange = pd.date_range(start, finish, freq="MS")
   ...:     for dt in dtRange:
   ...:         colName = str.format("{}-{:02d}", dt.year, dt.month)
   ...:         df_table.loc[ind, colName] = 1 
   ...:         
In[65]: df_table
Out[65]: 
  progress_id   course    start   finish  2018-06  2018-07  2018-08  2018-09  \
0   progress1  course1  2018-06  2018-08        1        1        1        0   
1   progress2  course2  2018-07  2018-07        0        1        0        0   
2   progress3  course1  2018-07  2018-10        0        1        1        1   
3   progress4  course3  2018-10  2018-12        0        0        0        0   
4   progress5  course3  2018-09  2018-11        0        0        0        1   
5   progress6  course4  2018-12  2019-02        0        0        0        0   

   2018-10  2018-11  2018-12  2019-01  2019-02  
0        0        0        0        0        0  
1        0        0        0        0        0  
2        1        0        0        0        0  
3        1        1        1        0        0  
4        1        1        0        0        0  
5        0        0        1        1        1  


Но а наконец применим метод .sum():

In[66]: df_table.sum(numeric_only=True)
Out[66]: 
2018-06    1
2018-07    3
2018-08    2
2018-09    2
2018-10    3
2018-11    2
2018-12    2
2019-01    1
2019-02    1
dtype: int64


Ответ 3

Вся программа (после импортов и создания вашей таблицы):

df_table["Months"] = 0                    # Добавим новую колонку для количества месяцев

for ind, row in df_table.iterrows():      # Проходим строками таблицы
    start  = row["start"]  + "-01"        # После года и месяца добавим и день в месяце
    finish = row["finish"] + "-01"
    df_table.loc[ind, "Months"] = len(pd.date_range(start, finish, freq="MS")) #
см. далее

print(df_table.groupby("course").sum())


Вывод:


         Months
course         
course1       7
course2       1
course3       6
course4       3





Объяснение:

Как посчитать, сколько месяцев между (например) 2018-12 и 2019-02 (ваша последняя
строка в таблице)?

Так:


Построим DatetimeIndex с месячной частотой, от первого дня в месяце:

In[3]: pd.date_range("2018-12-01", "2019-02-01", freq="MS")
Out[3]: DatetimeIndex(['2018-12-01', '2019-01-01', '2019-02-01'], dtype='datetime64[ns]',
freq='MS')

Посчитаем, сколько в нем элементов:

In[4]: len(_)                 
Out[4]: 3



Теперь то же самое с вашей таблицей df_table, добавляя вычисленное значение в новый
столбец:

In[6]: df_table["Months"] = 0

In[7]: for ind, row in df_table.iterrows():
   ...:     start  = row["start"]  + "-01"
   ...:     finish = row["finish"] + "-01"
   ...:     df_table.loc[ind, "Months"] = len(pd.date_range(start, finish, freq="MS"))
   ...: 
In[8]: df_table
Out[8]: 
  progress_id   course    start   finish  Months
0   progress1  course1  2018-06  2018-08       3
1   progress2  course2  2018-07  2018-07       1
2   progress3  course1  2018-07  2018-10       4
3   progress4  course3  2018-10  2018-12       3
4   progress5  course3  2018-09  2018-11       3
5   progress6  course4  2018-12  2019-02       3


И наконец применим метод groupby():

In[9]: df_table.groupby("course").sum()
Out[9]: 
         Months
course         
course1       7
course2       1
course3       6
course4       3

Почему у числа нельзя вызвать метод напрямую?

#python #python_3x

Вопрос особого практического смысла не имеет, просто стало любопытно, почему в Python
нельзя вызвать метод напрямую у числа? Например, я могу сделать это со строкой:

'3'.__add__('4') # 34


Или со списком:

[].__add__([3]) # [3]


Но не могу сделать так с числом:

3.__add__(4) # SyntaxError: invalid syntax


При этом я могу записать 3 в переменную и тогда все, естественно, ок:

x = 3
x.__add__(4) #7

    

Ответы

Ответ 1

Потому что с точки зрения парсера у вас написано число (float) 3., а за ним вызов
__add__(4) и получается синтаксическая ошибка. Нужно объяснить парсеру, что вы вовсе
не имели в виду число 3., например заключив число в скобки или поставив пробел перед
точкой:

>>> (3).__add__(4)
7
>>> 3 .__add__(4)
7


Ещё один вариант 3..__add__(4) (= 7.0), но результат будет числом с плавающей точкой,
обычно это не то что требуется.

Как еще можно задать default-значение переменной кроме try-except?

#python #python_3x #атрибуты

Объект obj - это инстанс какой-то джанго-модели. Допустим, у него есть поле prop,
которое по идее должно быть связано с другой моделью, но может также быть None. Моя
задача - записать в переменную var поле target второй связанной модели.

var = obj.prop.target


Если поле prop окажется равно None, то все сломается, так как у None нет поля target.
В этом случае я хочу записать в переменную var значение None. В принципе я могу это
сделать так

try:
    var = obj.prop.target
except AttributeError:
    var = None


Нет ли какого-нибудь другого способа это сделать, наподобие setdefault у  словарей? 
    

Ответы

Ответ 1

Воспользуйтесь встроенной функцией getattr(object, name[, default]):

var = getattr(obj.prop, "target", None)


Выдержка из документации:

getattr(object, name[, default])



  Return the value of the named attribute of object. name must be a
  string. If the string is the name of one of the object’s attributes,
  the result is the value of that attribute. For example, getattr(x, 'foobar') is
equivalent to x.foobar. If the named attribute does not
  exist, default is returned if provided, otherwise AttributeError is
  raised.

Почему строки с fuzzy в django.po не переводятся?

#python #локализация #django

Я обновляю файл django.po таким образом:
$ python manage.py makemessages -l ru
$ python manage.py compilemessages -l ru

После этого часть строк в django.po помечаются как fuzzy и не переводятся во время
работы приложения. Например, при 
#, fuzzy
msgid "view"
msgstr "показ"

вместо показ будет view.    

Ответы

Ответ 1

При выполнении makemessage как fuzzy помечаются строки имеющие близкий msgid. Такие
строки не попадают в итоговый *.mo из *.po, как предположительно неверные. Нужно их
поправить и убрать пометку fuzzy.