Здравствуйте, уважаемые читатели!
Мы вынашиваем амбициозные планы по изданию вот такой книги:
Как вы понимаете, эта книга требует не только литературного перевода, но и классной полиграфии, хорошей бумаги, широкого формата и т.п. Поэтому предлагаем ознакомиться с замечательной публикацией об этой книге, появившейся в блоге автора, Эгню Кролла, спустя несколько месяцев после публикации оригинала.
Приятного чтения, и поучаствуйте пожалуйста в опросе!
Я написал книгу If Hemingway Wrote JavaScript. В ней я фантазирую, как 25 знаменитых прозаиков, поэтов и драматургов могли бы решать простые задачи на JavaScript. Это дань уважения моим любимым писателям и признание в любви языку JavaScript – ведь я не знаю, какой еще язык наделял бы программиста такой свободой, позволял раскрыть творческий потенциал, а также был бы настолько своеобразен, чтобы привлечь внимание великих литераторов.
В этом посте – оригинальный материал, которого нет в книге (считайте его «бонусом»). Это первый глубокий технический разбор решений, приписываемых каждому автору. Некоторые решения требуют более подробных объяснений, нежели другие.
Приятного чтения!
Часть 1: Простые числа
Задание: напишите функцию, возвращающую все простые числа вплоть до значения заданного аргумента.
1. Хорхе Луис Борхес
https://github.com/angus-c/literary.js/tree/master/book/borges/prime.js
// Они повествуют (я знаю) о пинаклях, флеронах и балюстрадах,
// о потаенных интервольтах и чудищах, вечно идущих вверх размашистым шагом
var monstersAscendingAStaircase = function(numberOfSteps) {
var stairs = []; stepsUntrodden = [];
var largestGait = Math.sqrt(numberOfSteps);
// Череда тварей карабкается по ступенькам;
// шаг каждой следующей химеры шире, чем у предыдущей
for (var i = 2; i <= largestGait; i++) {
if (!stairs[i]) {
for (var j = i * i; j <= numberOfSteps; j += i) {
stairs[j] = "stomp";
}
}
// Длиннолапые чудища не попадают по ступенькам, номера которых – простые числа
for (var i = 2; i <= numberOfSteps; i++) {
if(!stairs[i]) {
stepsUntrodden.push(i);
}
}
// Вот и наш ответ
return stepsUntrodden;
};
Решение Борхеса – вариант алгоритма «Решето Эратосфена», в котором кратные каждого известного простого числа помечаются как составные (непростые) числа. В таком случае, у Борхеса длиннолапые чудовища занимают места делителей. Каждое чудище делает шаг на одну ступеньку шире, чем шедшее за ним: 2, 3, 4, 5… вплоть до квадратного корня из числа, соответствующего наивысшей ступеньке. (почему-то Борхес позволяет карабкаться по лестнице и чудищам с неровным шагом). Те ступеньки, на которые никто не встанет – и есть простые числа.
Обратите внимание на строку 12: каждый монстр начинает восхождение с квадрата своего множителя:
for (var j = i * i; j <= numberOfSteps; j += i) {
Дело в том, что составные числа между n и n² уже будут пройдены чудищами с более мелким шагом.
2. Льюис Кэрролл
https://github.com/angus-c/literary.js/tree/master/book/carroll/prime.js
function downTheRabbitHole(growThisBig) {
var theFullDeck = Array(growThisBig);
var theHatter = Function('return this/4').call(2*2);
var theMarchHare = Boolean('The frumious Bandersnatch!');
var theVerdict = 'the white rabbit'.split(/the march hare/).slice(theHatter);
// в море слез…
eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
);
return theVerdict;
}
Как и творчество Кэрролла, его код — смесь загадки и нонсенса. Давайте построчно в нем разберемся, начиная с объявления переменных.
В принципе, строка 2 вполне традиционна (если закрыть глаза на использование конструктора Array). Кэрролл создает пустой массив, длина которого совпадает с сообщенным аргументом. Он называется
theFullDeck
В строке 3 создается функция (с применением малоиспользуемого конструктора Function), а затем эта функция вызывается при помощи call, при этом 2 * 2 (т.е. 4) передается как аргумент this. Следовательно, theHatter инициализируется со значением 1.
В строке 4
theMarchHare
true
true
false
true
theMarchHare
Наконец – вероятно, это верх абсурда – в строке 6 Кэрролл присваивает
theVerdict
var theVerdict = 'the white rabbit'.split(/the march hare/).slice(theHatter);
Здесь не так много бросается в глаза. Аргумент для
split
split
slice
theHatter
Проще говоря, можно переписать объявления переменных вот так:
function downTheRabbitHole(growThisBig) {
var theFullDeck = Array(growThisBig);
var theHatter = 1;
var theMarchHare = true;
var theVerdict = [];
А теперь полный угар:
// в море слез…
eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
);
Прежде, чем перейти к пресловутой функции
eval
join
join
Array(4).join('hi'); //'hihihi'
Если вложить друг в друга два join, то вкладывается и соответствующий клей:
Array(4).join('A' + Array(4).join('a')); //'AaaaAaaaAaaa'
Когда же мы включаем в клей переменные, начинаем понимать, что к чему:
var arr = [], count = 0;
Array(4).join('arr.push(' + Array(4).join('count++,') + '-1);');
//"arr.push(count++,count++,count++,-1);arr.push(count++,count++,count++,-1);arr.push(count++,count++,count++,-1)"
Теперь, растолковав JavaScript, как генерировать JavaScript, остается только придумать, как все это запустить. Заходим в гнусную
eval
var arr = [], count = 0;
eval(Array(4).join('arr.push(' + Array(4).join('count++,') + '-1);'));
arr; //[0, 1, 2, -1, 3, 4, 5, -1, 6, 7, 8, -1]
…так вот каким образом Кэрролл автоматически генерирует программу для работы с простыми числами. Давайте еще раз взглянем на этот код:
// в море слез...
eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
);
Аргумент к eval (после форматирования) принимает вид:
if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
}
if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
}
if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
}
// etc...
…и т.д. (Сгенерированный таким образом код может получиться очень длинным. Запросив все простые числа вплоть до 100, получим более 10 000 строк кода – можете себе представить, как это скажется на производительности – но для Страны Чудес, полагаю, сойдет)
Итак, постепенно все проясняется. Оказывается, Кэрролл использовал вариант того самого решета Эратосфена, которое мы видели у Борхеса.
theFullDeck
theHatter
theMarchHare
theFullDeck
true
3. Дуглас Адамс
https://github.com/angus-c/literary.js/tree/master/book/adams/prime.js
// Вот я, мозг размером с планету, и они просят меня написать на JavaScript...
function kevinTheNumberMentioner(_){
l=[]
/* почти безвредно --> */ with(l) {
// извините за все это, у моей вавилонской рыбки сегодня мигрень...
for (ll=!+[]+!![];ll<_+(+!![]);ll++) {
lll=+!![];
while(ll%++lll);
// У меня в правом полушарии все болит от этих чертовых точек с запятой
(ll==lll)&&push(ll);
}
forEach(alert);
}
// ну так вы же точно делать не будете...
return [!+[]+!+[]+!+[]+!+[]]+[!+[]+!+[]];
}
Читать код Адамса в целом сложно, так как он многое заимствует из jsfuck – хитроумного, но убийственно лаконичного языка, в котором используется всего 6 символов. Тем не менее, это настоящий JavaScript — если вы запустите его в консоли, все сработает. Давайте переведем простой фрагмент:
for (ll=!+[]+!![];ll<_+(+!![]);ll++) {
Здесь видим цикл
for
В первом условии этой инструкции ll получает значение
!+[]+!![]
true
!+[]
true
Теперь рассмотрим второй литерал массива. Ему предшествуют два
!!
true
!![]
true
Сложив два этих выражения,
!+[]+!![]
true + true
Два остальных условия цикла
for
!![]
true
ll<_+(+!![])
ll < _ + 1
Последнее условие – это обычный постфикс JavaScript, поэтому весь цикл
for
for (ll = 2; ll < _ + 1; ll++) {
А вот все решение, переведенное на обычный мирской JavaScript (переменным я также дал более осмысленные имена)
// Вот я, мозг размером с планету, и они просят меня написать на JavaScript…
function kevinTheNumberMentioner(max){
var result = [];
/* почти безвредно --> */ with(result) {
// извините за все это, у моей вавилонской рыбки сегодня мигрень...
for (candidate = 2; candidate < max + 1; candidate++) {
var factor = 1;
while (candidate % ++factor);
// У меня в правом полушарии все болит от этих чертовых точек с запятой
(candidate == factor) && push(candidate);
}
forEach(alert);
}
// ну так вы же точно делать не будете...
return '42';
}
Славно, теперь перед нами, по крайней мере, узнаваемый JavaScript, но в нем по-прежнему таятся кое-какие странности.
Инструкция
with
with
push
forEach
result
Еще одна любопытная инструкция — цикл
while
factor
candidate
candidate
factor
result
В строке 13 перебираем результаты и во всеуслышание объявляем каждое простое число в виде
alert
4. Чарльз Диккенс
https://github.com/angus-c/literary.js/tree/master/book/dickens/prime.js
function MrsPrimmerwicksProgeny(MaxwellNumberby) {
Number.prototype.isAPrimmerwick = function() {
for (var AddableChopper = 2; AddableChopper <= this; AddableChopper++) {
var BittyRemnant = this % AddableChopper;
if (BittyRemnant == 0 && this != AddableChopper) {
return console.log(
'It is a composite. The dear, gentle, patient, noble', +this, 'is a composite'),
false;
}
}
return console.log(
'Oh', +this, +this, +this, 'what a happy day this is for you and me!'),
true;
}
var VenerableHeap = [];
for (var AveryNumberby = 2; AveryNumberby <= MaxwellNumberby; AveryNumberby++) {
if (AveryNumberby.isAPrimmerwick()) {
VenerableHeap.push(AveryNumberby);
}
}
return VenerableHeap;
}
Что, если бы вы могли спросить у числа, простое ли оно:
6..isPrime(); // ложь
7..isPrime(); // истина
Что бы сделал Чарльз Диккенс? Расширил бы
Number.prototype
isAPrimmerwick
VenerableHeap
Логика метода
isAPrimmerwick
В каждой инструкции возврата (строки 6 и 11) есть пара любопытных моментов. Во-первых, поскольку число вызывает метод в его же прототипе, на него можно сослаться при помощи
this
console.log
5. Дэвид Фостер Уоллес
https://github.com/angus-c/literary.js/tree/master/book/wallace/prime.js
var yearOfTheLighteningQuickAtkinSieve = function(tops) {
//B.P. #40 07-14
//ELEPHANT BUTTE, NM
var NSRS/*[1]*/ = [0,0,2,3];
/* два конкурентных цикла мобилизуются так, что переменные i и j (каждая с
исходным значением 1) увеличиваются на 1 при каждом инкременте
(правда, во вложенном виде). */
for(var i = 1; i < Math.sqrt(tops); i++){
for(var j = 1; j < Math.sqrt(tops); j++){
if (i*i + j*j >= tops) {
break;
}
/* Две переменные (т.e. i и j) подставляются в первую квадратичную функцию quadratic,
и результат ее присваивается дополнительной переменной (n). */
var n = 4*i*i + j*j;
/* Если дополнительная переменная (т.e. n) деленная на 12, даст в остатке
1 или 5, то у значения с этим индексом (т.e. у n) меняется знак [2]. */
if(n <= tops && (n%12 == 1 || n%12 == 5)){
NSRS[n] = NSRS[n] ? 0 : n;
}
/* Теперь мы (т.e. JavaScript) подходим ко второй квадратичной функции, and again the result
и результат вновь присваивается (существующей) переменной n. */
n = 3*i*i + j*j;
/* Хотя переменная (т.e. n) вновь делится на 12, на сей раз остаток
сравнивается с 7 для определения того, должен ли у значения с данным
индексом(т.e. у n)
меняться знак */
if(n <= tops && (n % 12 == 7)){
NSRS[n] = NSRS[n] ? 0 : n;
}
/* Теперь вы (т.e. читатель), испытываете чувство нерешительности и раскаяния,
тем не менее, мы (т.e. JavaScript) еще не закончили. Как и следовало ожидать, теперь в ход
идет третья квадратичная функция и(не менее предсказуемо) ее значение присваивается (уже
уже поистрепавшейся) переменной n. */
n = 3*i*i - j*j;
/* Единственный интересный момент в третьей операции деления (однако и самый
удручающий) заключается в том, что она происходит лишь тогда, когда первая переменная
в цикле (i) оказывается больше
т.e. не меньше (или равна) второй переменной цикла (j) [3]. */
if (i>j) {
if((n <= tops) && (n % 12 == 11)){
NSRS[n] = NSRS[n] ? 0 : n;
}
}
}
}
/* В полуобморочном состоянии (но не доверяя фильтру кольцевой факторизации) мы
(т.e. JavaScript) теперь предварительно определяем как составные
все без исключения простые множители, без учета их актуального статуса: простые ли они
(т.е не составные) или составные (т.е. не простые)
*/
for(i = 5; i < Math.sqrt(tops); i++){
if(NSRS[i] == 1){
for(j = i*i; j < tops; j += i*i){
NSRS[j] = 0;
}
}
}
return NSRS.filter(Number); // [4]
}
/*
[1] Числовая система хранения и поиска информации.
[2] То есть значения, соответствующие текущему индексу [a] устанавливаются в 0, а значения 0 устанавливаются в текущие индексы.
[3] В противном случае каждый релевантный индекс [a] менял бы знак дважды.
[4] `Array.prototype.filter` будучи функцией высшего порядка, определяется в стандарте EcmaScript-262 (5-я
версия) [b]. Поскольку `Number` - это встроенная в язык функция, преобразующая любое значение в число. а Array.prototype.filter
отклоняет ложные (т.e. неистинные) значения, значения 0, будучи ложными (т.e. неистинными) не
будут включаться в массив, возвращаемый `Array.prototype.filter`.
[a] т.e. индекс, на котором рассматриваемая квадратичная функция результирует в true.
[b] http://es5.github.io/#x15.4.4.20
*/
Благодаря пространным комментариям, которыми так известен Уоллес, рассказывать особенно нечего — надо только отметить, что в основе его решения лежит сильно оптимизированное (и слишком сложное, чтобы вдаваться здесь в объяснения) решето Эткина.
Код особенно интересен изысканной логикой и уоллесовским точным, но непринужденным стилем. Однако в строке 54 есть и интересный оборот JavaScript:
return NSRS.filter(Number); // [4]
Результат —
NSRS
[0, 0, 2, 3, undefined, 5, undefined, 7/*, etc.. */]
Функция
Array.prototype.filter
true
Number
Number
undefined
NaN
NaN
[0, 0, 2, 3, undefined, 5, undefined, 7].filter(Number); //[2, 3, 5, 7]
Заключение
Вот и все. Надеюсь, вам понравилось.
Автор: Издательский дом «Питер»
