mmmkot

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

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                                                          .                   X
X                     X                                   . .                  X
X                                 X                      .   .                 X
X  X                                                    .     .                X
X                    o                                 .       .               X
X                     .          XXXXXXX              .         .              X  
X                    X .         X                   .           .             X
X                       .        X                  .          X  .            X
X                     X  .       X                 .           .   .           X
X                         .      X                .           . .   .          X
X          X               .     X            X  .           .   .   .         X
X                           .           .       .     X     .     .   . X      X
X                            .           .     .           .       .   .       X
X       XXXXXX                .           .   .           .         .   .      X
X       XXXXXX                 .           . .           .           .   .     X
X       XXXXXX                  .           .           .             .   .    X
X                    X           .         . .         .               .   .   X
X                                 .       .   .       .                 .   .  X
X                                  .     .     .     .                   .   . X
X                                   .   .       .   .                     .   .X
X                                X   . .    X    . .                       . . X
X                                     .           .                         .  X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Понятно, что в зависимости от конфигурации препятствия шарик будет отскакивать в разных направлениях, а писать сложные проверки не хотелось:

X X X
_ 1 _
_ _ 2

_ X _
_ 1 X
2 _ _

(На рисунках выше шарик до удара двигался в направлении вверх и вправо.)

Несложно понять, что для определения следующего положения шарика необходимо знать кусочек поля размером 3x3, и что возможно всего 2⁸=256 вариантов препятствий вокруг шарика.

Но кодировать все 256 вариантов тоже не хочется, поэтому вспоминаем про сопоставление с шаблоном -- идею, о которой узнал, разбираясь с функциональным программированием. Заметим, что в некоторых случаях направление дальнейшего движения зависит только от ключевых кусков стены и не зависит от того, что находится в остальных местах, например:

_ X _     X X X     X X _     _ X X
_ 1 _     _ 1 _     _ 1 _     _ 1 _
_ _ 2     _ _ 2     _ _ 2     _ _ 2

Введём обозначения: X -- стена, _ -- пустая клетка, ? -- всё что угодно.

Тогда приведённые выше конфигурации и некоторые другие задаются следующим шаблоном:

? X ?
? o _
? _ _

И всё, осталось только написать функцию сопоставления с шаблоном и придумать набор шаблонов, полностью покрывающих все возможные варианты стен. Всё это можно найти в скрипте ниже (Почему Bash? Так надо.)

#!/bin/bash -i

declare -a map
mapWidth=$COLUMNS
mapHeight=$LINES

((ballX = mapWidth / 2))
((ballY = mapHeight / 2))
ballDX=1
ballDY=1

function compare() {
	local -a pattern=( $1 )
	local -a x=( $2 )
	local i
	for ((i = 0; i < 8; ++i)); do
		if [[ "${pattern[$i]}" != "?" && "${pattern[$i]}" != "${x[$i]}" ]]; then
			return 1
		fi
	done
	return 0
}

rules=(
#	pattern           dy dx
	"? _ _ ? _ ? ? ?"  1  1
	"? X ? ? _ ? _ _" -1  1
	"_ _ ? _ X ? ? ?"  1 -1
	"? X ? ? ? ? X ?"  0  0
	"? ? ? X X ? ? ?"  0  0
	"X ? X ? ? X ? X"  0  0
	"? X ? ? ? X ? X"  0  0
	"X ? ? ? X X ? ?"  0  0
	"? ? X X ? ? ? X"  0  0 
	"X ? X ? ? ? X ?"  0  0
	"_ _ X _ _ _ _ _" -1 -1
	"? X ? _ X _ _ ?" -1 -1
	"X ? X _ ? _ _ X" -1 -1
	"X ? X ? _ ? _ _" -1  1
	"_ _ X _ ? ? ? X"  1 -1
	"X ? ? ? X ? X ?"  0  0
	"? X ? X ? ? ? X"  0  0
	"? X ? ? X X ? ?"  0  0
	"? ? X X ? ? X ?"  0  0
	"X ? ? _ X _ _ ?" -1 -1
	"? X ? ? _ X _ _" -1  1
	"_ _ X _ ? ? X ?"  1 -1
	"_ _ ? _ X X ? ?"  1 -1
	"? X ? _ ? _ _ X" -1 -1
	"? ? X X _ ? _ _" -1  1
	"_ _ X _ _ X _ _"  0  0
) 

function findRule() {
	local x=$1
	local countRules=$((${#rules[*]} / 3))
	for ((i = 0; i < countRules; ++i)); do
		if compare "${rules[$((i * 3))]}" "$x"; then
			echo "${rules[$((i * 3 + 1))]} ${rules[$((i * 3 + 2))]}"
			break
		fi
	done
}

function moveBall() {
	local -a x
	x[0]=${map[$(((ballY + ballDY) * mapWidth + ballX - ballDX))]}
	x[1]=${map[$(((ballY + ballDY) * mapWidth + ballX         ))]}
	x[2]=${map[$(((ballY + ballDY) * mapWidth + ballX + ballDX))]}
	x[3]=${map[$(((ballY         ) * mapWidth + ballX - ballDX))]}
	x[4]=${map[$(((ballY         ) * mapWidth + ballX + ballDX))]}
	x[5]=${map[$(((ballY - ballDY) * mapWidth + ballX - ballDX))]}
	x[6]=${map[$(((ballY - ballDY) * mapWidth + ballX         ))]}
	x[7]=${map[$(((ballY - ballDY) * mapWidth + ballX + ballDX))]}
	local -a rule=( `findRule "${x[*]}"` )
	((ballDY *= rule[0]))
	((ballDX *= rule[1]))
	((ballX += ballDX))
	((ballY += ballDY))
}


countPoints=20

function fillMap() {
	local i
	local j
	for ((i = 1; i < mapHeight - 1; ++i)); do
		for ((j = 1; j < mapWidth - 1; ++j)); do
			map[$((i * mapWidth + j))]="_"
		done
	done
	for ((i = 0; i < mapWidth; ++i)); do 
		map[$i]="X"
		map[$(((mapHeight - 1) * mapWidth + $i))]="X"
	done
	for ((i = 0; i < mapHeight; ++i)); do
		map[$((i * mapWidth))]="X"
		map[$((i * mapWidth + mapWidth - 1))]="X"
	done

	for ((i = 0; i < countPoints; ++i)); do
		map[$((RANDOM % (mapWidth * mapHeight)))]="X"
	done
	map[$((ballY * mapWidth + ballX))]="_"
}

function drawMap() {
	local i
	local j
	for ((i = 0; i < mapHeight; ++i)); do
		for ((j = 0; j < mapWidth; ++j)); do
			if [[ ${map[$((i * mapWidth + j))]} == "X" ]]; then
				echo -ne "\e[$((i + 1));$((j + 1))fX"
			fi
		done
	done 
}

function clearBall() {
	echo -ne "\e[$((ballY + 1));$((ballX + 1))f."
}

function drawBall() {
	echo -ne "\e[$((ballY + 1));$((ballX + 1))fo"
}

function init() {
	clear
	fillMap
	drawMap
}

function run() {
	local -l key=""
	while : ; do
		read -n 1 -t 0.1 key
		if [[ "$key" == "q" ]]; then
			break;
		fi
		clearBall
		moveBall
		drawBall
	done
}

function finish() {
	clear
}

init
run
finish

Более подробно про сопоставление с шаблоном можно почитать, например, в статье Евгения Кирпичёва Элементы функционального программирования и ещё где-нибудь, а про программирование на Bash в Advanced Bash-Scripting Guide.

Уже несколько лет пишу скрипты на Bash, но только вчера узнал, что у переменных там динамическая область видимости, а не привычная лексическая, то есть следующий код

i=3

function f() {
    echo $i
}

function g() {
    local i=5
    f
}

function h() {
    local i=10
    f
}

g
h

выведет 5 и 10.

Аналогичный код на JavaScript

var i = 3;

function f() {
    alert(i);
}

function g() {
    var i = 5;
    f();
}

function h() {
    var i = 10;
    f();
}

g();
h();

ясное дело выведет два раза 3.

Не следует ни на секунду забывать, что float и double это не совсем вещественные числа, а совсем невещественные числа:

1 - (1 - 9f / 10) * 10                   = -2.3841858E-7
1 - (1 - 99f / 100) * 100                =  9.536743E-7
1 - (1 - 999f / 1000) * 1000             =  1.2874603E-5
1 - (1 - 9999f / 10000) * 10000          = -1.6593933E-4
1 - (1 - 99999f / 100000) * 100000       = -0.0013580322
1 - (1 - 999999f / 1000000) * 1000000    = -0.013278961
1 - (1 - 9999999f / 10000000) * 10000000 = -0.1920929

Я вот забыл и на исключение нарвался.

Добавил статью Игры с треугольником и ковром Серпинского. Идея как всегда проста как пять копеек. Рассматриваем треугольник Серпинского как подмножество комплексной плоскости и применяем к нему различные преобразования комплексной плоскости.

http://twitter.com/mkotov -- о жизни, учёбе, мире, обо всём вобщем.

http://twitter.com/fractal_world -- о фракталах.

http://twitter.com/xkotov -- всякие картинки, цитаты и т. д., которые мне понравились.

Иногда возникает в программировании ситуация, когда нужно перевести декартовы координаты (x, y) в полярные (r, a). Как это происходит, если не знать одну очень хорошую функцию.

Программист вспоминает, что радиус вычисляется по формуле r = sqrt(x^2 + y^2). Здесь всё нормально. Дальше он вспоминает, что на a есть условия tan(a) = y / x, sin(a) = y / r, cos(a) = x / r. Программист выбирает первое равенство и пишет код

a = arctan(y / x);

и замечает, что при x = 0 программа падает, поэтому пишется код

if (x == 0) a = pi / 2;
else a = arctan(y / x); 

Но тут снова программист замечает, что в одних четвертях это всё работает, а в других бред какой-то получается. Путём экспериментов код переписывается следующим образом:

if (x == 0 && y > 0) a = pi / 2;
else if (x == 0 && y < 0) a = -pi / 2;
else if (x == 0 && y == 0) a = 0;
else if (x > 0) a = arctan(y / x);
else if (x < 0 && y >= 0) a = arctan(y / x) + pi;
else if (x < 0 && y < 0) a = arctan(y / x) - pi;  

Потом программист осознаёт, что эту задача не очень простая и стандартная и её уже кто-то должен был решать. И оказывается, что существует функция arctan2(y, x), которая делает, то что надо. Причём она существует во всех популярных языках программирования. Так что правильное решение есть:

r = sqrt(x^2 + y^2);
a = arctan2(y, x);

И наверное на лекциях по ангему об этом нужно программистам рассказывать.

(Вместо 'программист' следует подставить моё имя, но не я один на эти грабли наступал.)

Прочитал тут сегодня в Десяти Буквах заблуждение:
некоторые думают, что сумма двух иррациональных чисел есть иррациональное число.
И вспомнил следующее заблуждение (если бы меня спросили, правда ли это, я сказал бы, что это правда, так что я сам так заблуждался, но никто не спрашивал, и я про него просто вычитал).
Все знают как доказывается теорема о том, что множество простых чисел бесконечно: предположим что их конечно, все перемножим и прибавим единицу. Получим число, которое ни на что не делится кроме себя и 1. Во-о-от. Несложно подумать поэтому, что если взять несколько первых простых чисел и перемножить их, а затем прибавить 1, то получим простое число. Можно даже эксперимент поставить:
2 + 1 = 3 -- простое,
2 * 3 + 1 = 7 -- простое,
2 * 3 * 5 + 1 = 31 -- простое,
2 * 3 * 5 * 7 + 1 = 221 -- простое,
2 * 3 * 5 * 7 * 11 + 1 = 2311 -- простое...

Но если кто попытается это доказать, то у него не получится, более того, уже 2 * 3 * 5 * 7 * 11 * 13 + 1 простым не является.

http://fractalworld.xaoc.ru/Binary_trees

Обновил http://fractalworld.xaoc.ru/Pythagoras_tree

Встречаем Треугольник Паскаля. Это заключительная часть трилогии про забавные способы построения треугольника и ковра Серпинского.