CodenJoy. 2048

В предыдущем посте я написал о посещении frameworksdays, на котором нас познакомили с проектом codenjoy. Очередные головоломки для разработчиков. В перечне задачек была предложена игра 2048 - суть задания написать алгоритм (бота), позволяющий набрать максимальное количество баллов из всех зарегистрированных участников.

Взаимодействие с сервером осуществляется посредством websoсket'ов. Значит нет привязки к языку программирования - что не может не радовать. 

Установил себе модуль https://pypi.python.org/pypi/websocket-client для работы с вебсокетами через python и начеркал примитивный алгоритм, который может прийти в голову - постоянно жмем кнопку вниз, когда строка (двумерный массив разложенный в строку) не изменилась от предыдущего действия, то нажимаем влево. В результате имеем следующий код:

import websocket

def on_message(ws, message):
    ws.send("LEFT" if message == ws.last_message else "DOWN")
    ws.last_message = message

if __name__ == "__main__":
    ws = websocket.WebSocketApp( "ws://tetrisj.jvmhost.net:12270/codenjoy-contest/ws?user=[user]"
                               , on_message = on_message)
    ws.last_message = ""
    ws.run_forever()

Такой бот смог набрать 7938 и занять 3е место в рейтинге, к заметке - второе место имеет такое же количество баллов.

Для сброса текущего счета (перерегистрация) клиента:
curl http://codenjoy.com/codenjoy-contest/register -d "name=[user]&password=[pass]&gameName=a2048"

Если будет возможность написать обновленного бота, который выйдет на первую строчку рейтинга, то обязательно выложу исходный код. И напоследок - советую всем попробовать свои силы в написании алгоритмов для подобных задачек.

Codility. Train. Brackets ★

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

• S is empty;
• S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

int solution(char *S);

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.

Assume that:

• N is an integer within the range [0..200,000];
• string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Codility. Train. Number-of-disc-intersections ★★★

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.

Write a function:

def solution(A)

that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:

A[0] = 1  A[1] = 5  A[2] = 2 
A[3] = 1  A[4] = 4  A[5] = 0  

intersecting discs appear in eleven pairs of elements:

• 0 and 1,
• 0 and 2,
• 0 and 4,
• 1 and 2,
• 1 and 3,
• 1 and 4,
• 1 and 5,
• 2 and 3,
• 2 and 4,
• 3 and 4,
• 4 and 5.

so the function should return 11.

The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Assume that:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [0..2147483647].

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Max-product-of-three ★★

A non-empty zero-indexed array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:

  A[0] = -3
  A[1] = 1
  A[2] = 2
  A[3] = -2
  A[4] = 5
  A[5] = 6

contains the following example triplets:

• (0, 1, 2), product is −3 * 1 * 2 = −6
• (1, 2, 4), product is 1 * 2 * 5 = 10
• (2, 4, 5), product is 2 * 5 * 6 = 60

Your goal is to find the maximal product of any triplet.

Write a function:

def solution(A)

that, given a non-empty zero-indexed array A, returns the value of the maximal product of any triplet.

For example, given array A such that:

  A[0] = -3
  A[1] = 1
  A[2] = 2
  A[3] = -2
  A[4] = 5
  A[5] = 6

the function should return 60, as the product of triplet (2, 4, 5) is maximal.

Assume that:

• N is an integer within the range [3..100,000];
• each element of array A is an integer within the range [−1,000..1,000].

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Triangle ★

A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q].

For example, consider array A such that:

  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 20

Triplet (0, 2, 4) is triangular.

Write a function:

def solution(A)

that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise. For example, given array A such that:

  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 20

the function should return 1, as explained above. Given array A such that:

  A[0] = 10    A[1] = 50    A[2] = 5
  A[3] = 1

the function should return 0.

Assume that:

• N is an integer within the range [0..1,000,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Genomic-range-query ★★★

A non-empty zero-indexed string S is given. String S consists of N characters from the set of upper-case English letters A, C, G, T.

This string actually represents a DNA sequence, and the upper-case letters represent single nucleotides.

You are also given non-empty zero-indexed arrays P and Q consisting of M integers. These arrays represent queries about minimal nucleotides. We represent the letters of string S as integers 1, 2, 3, 4 in arrays P and Q, where A = 1, C = 2, G = 3, T = 4, and we assume that A < C < G < T.

Query K requires you to find the minimal nucleotide from the range (P[K], Q[K]), 0 ≤ P[i] ≤ Q[i] < N.

For example, consider string S = GACACCATA and arrays P, Q such that:

    P[0] = 0    Q[0] = 8
    P[1] = 0    Q[1] = 2
    P[2] = 4    Q[2] = 5
    P[3] = 7    Q[3] = 7

The minimal nucleotides from these ranges are as follows:

• (0, 8) is A identified by 1,
• (0, 2) is A identified by 1,
• (4, 5) is C identified by 2,
• (7, 7) is T identified by 4.

Write a function:

def solution(S, P, Q)

that, given a non-empty zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M characters specifying the consecutive answers to all queries.

The sequence should be returned as:

• a Results structure (in C), or
• a vector of integers (in C++), or
• a Results record (in Pascal), or
• an array of integers (in any other programming language).

For example, given the string S = GACACCATA and arrays P, Q such that:

    P[0] = 0    Q[0] = 8
    P[1] = 0    Q[1] = 2
    P[2] = 4    Q[2] = 5
    P[3] = 7    Q[3] = 7

the function should return the values [1, 1, 2, 4], as explained above.

Assume that:

• N is an integer within the range [1..100,000];
• M is an integer within the range [1..50,000];
• each element of array P, Q is an integer within the range [0..N − 1];
• P[i] ≤ Q[i];
• string S consists only of upper-case English letters A, C, G, T.

Complexity:

• expected worst-case time complexity is O(N+M);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Passing-cars ★★

A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

• 0 represents a car traveling east,
• 1 represents a car traveling west.

The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

For example, consider array A such that:

  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1

We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

Write a function:

def solution(A)

that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.

The function should return −1 if the number of passing cars exceeds 1,000,000,000.

For example, given:

  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1

the function should return 5, as explained above.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [0..1].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Max-Counters ★★★

You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) − counter X is increased by 1,
• max_counter − all counters are set to the maximum value of any counter.

A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max_counter.

For example, given integer N = 5 and array A such that:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4

the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty zero-indexed array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

• a structure Results (in C), or
• a vector of integers (in C++), or
• a record Results (in Pascal), or
• an array of integers (in any other programming language).

For example, given:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Assume that:

• N and M are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..N + 1].

Complexity:

• expected worst-case time complexity is O(N+M);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Frog-River-One ★★

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.

You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.

For example, you are given integer X = 5 and array A such that:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

In minute 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

def solution(X, A)

that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

the function should return 6, as explained above. Assume that:

• N and X are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..X].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Perm-Check ★

A non-empty zero-indexed array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2

is a permutation, but array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3

is not a permutation.

The goal is to check whether array A is a permutation.

Write a function:

def solution(A)

that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2

the function should return 1.

Given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3

the function should return 0.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Tape-Equilibrium ★★★

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non−empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

We can split this tape in four places:

• P = 1, difference = |3 − 10| = 7 
• P = 2, difference = |4 − 9| = 5 
• P = 3, difference = |6 − 7| = 1 
• P = 4, difference = |10 − 3| = 7 

Write a function:

def solution(A)

that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.

For example, given:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

the function should return 1, as explained above.

Assume that:

• N is an integer within the range [2..100,000];
• each element of array A is an integer within the range [−1,000..1,000].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Perm-Missing-Elem ★★

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

def solution(A)

that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5

the function should return 4, as it is the missing element.

Assume that:

• N is an integer within the range [0..100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1..(N + 1)].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Codility. Train. Frog-Jmp ★

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

def solution(X, Y, D)

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

  X = 10
  Y = 85
  D = 30

the function should return 3, because the frog will be positioned as follows:

• after the first jump, at position 10 + 30 = 40
• after the second jump, at position 10 + 30 + 30 = 70
• after the third jump, at position 10 + 30 + 30 + 30 = 100

Assume that:

• X, Y and D are integers within the range [1..1,000,000,000];
• X ≤ Y.

Complexity:

• expected worst-case time complexity is O(1);
• expected worst-case space complexity is O(1).

Monster World. Я миллионер.

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

Python. Active Directory. Сброс пароля учетной записи.

Долго искал решение для сброса пароля для учетной записи пользователя active directory через python. Первым делом установил LDAP client API for Python, проживающий по адресу www.python-ldap.org. Почему-то во время попытки сброса пароля выдавались непредвиденные ошибки, которые не должны быть. В каких только вариантах я не перепробовал установку атрибута "unicodePwd" для сброса пароля - но все никак, сервер отказывался выполнять мою команду. 

ManageEngine ServiceDesk. Расширяем функционал.

Прошло некоторое время после моего поста "Error 2004: Can't create TCP/IP socket (10106)" - решение небольшой проблемы с которой я столкнулся во время изучения возможности расширения функциональности программного продукта ServiceDesk Plus от компании ManageEngine. SDP является коробочной версией, поэтому вносить изменения в исходный код не представляется возможным. 

Error 2004: Can't create TCP/IP socket (10106)

Подключил Python как CGI в Tomcat'e как написано в документации: удалил комментирование с блоков подключения CGIServlet-а и маппинга сервлета, а также переименовал servlets-cgi.renametojar в servlets-cgi.jar. Перезапустил веб-сервер, теперь все файлы находящиеся в папке cgi обрабатываются через python. Все было бы хорошо, но столкнулся с проблемой - при открытии сокетов вываливалась ошибка:

Error 2004: Can't create TCP/IP socket (10106)

Приятно быть в новостях!

Новоиспеченная компания Aperon выпустила продукт "электронной регистрации заказов" для  системы D2Restaurant компании SYTEC, который был представлен на выставке "Ресторан Экспо Украина". 

Мобильный терминал официанта базируется на платформе Android. Подробнее можно ознакомиться по адресу http://d2.ua/ru/content/145.

За развитием проекта можно следите по новостям компании SYTEC http://d2.ua/ru/news/.