Здравствуйте, уважаемые хаброжители!
Мы вынашиваем амбициозные планы по изданию вот такой книги:
Как вы понимаете, эта книга требует не только литературного перевода, но и классной полиграфии, хорошей бумаги, широкого формата и т.п. Поэтому предлагаем ознакомиться с замечательной публикацией об этой книге, появившейся в блоге автора, Эгню Кролла, спустя несколько месяцев после публикации оригинала.
Приятного чтения, и поучаствуйте пожалуйста в опросе!
Я написал книгу 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 . Когда конструктор Boolean вызывается как функция, его аргумент преобразуется в true или false . В таком случае непустая строка ‘The frumious Bandersnatch!’ преобразуется в true . (Кстати, такое присваивание не очень-то здесь нужно, поскольку в строке 10 theMarchHare присваивается новое значение).
Наконец – вероятно, это верх абсурда – в строке 6 Кэрролл присваивает theVerdict пустой массив, и делает это максимально иносказательно:
var theVerdict = 'the white rabbit'.split(/the march hare/).slice(theHatter); Здесь не так много бросается в глаза. Аргумент для split – это регулярное выражение, не совпадающее с ‘the white rabbit’, поэтому при вызове split получаем массив, в котором содержится лишь ‘the white rabbit’. Последующая операция slice заносит в копию массива все элементы исходного массива, начиная с заданного индекса. Поскольку в нашем одноэлементном массиве нет индекса 1 (таково значение 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 превращает массив в строку, при этом ее аргумент служит клеем между элементами массива. Если вызвать join применительно к пустому массиву, получится строка, состоящая из сплошного клея (повторенная n – 1 раз, где n – длина массива):
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 и _ — имена переменных. Все остальное – литерал и форменный вынос мозга.
В первом условии этой инструкции ll получает значение !+[]+!![] . Разобрав это выражение, видим в нем два пустых литерала массива. Перед первым стоит +, из-за которого массив принудительно приводится к числу 0. Прямо перед ним стоит!, принудительно приводящий 0 к его булевской противоположности, то есть, к true . Итак, !+[] результирует в true .
Теперь рассмотрим второй литерал массива. Ему предшествуют два !! , что попросту принудительно приведет его к булеану. Поскольку массивы – всегда объекты, булеан массива всегда равен true . Итак, !![] всегда дает true .
Сложив два этих выражения, !+[]+!![] , фактически, имеем true + true . Здесь + принудительно приводит оба операнда к числу 1, поэтому окончательный результат всего выражения равен 2.
Два остальных условия цикла for теперь понятны без труда. Опять же, имеем !![] , на сей раз перед ним идет +, принудительно приводящий true к 1. Итак, 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 относится к наиболее предосудительным с точки зрения «блюстителей чистоты JavaScript», но все-таки в строке 3 – именно она. JavaScript попытается заключить все свойства, на которые не указывают ссылки, в блоке with заданного объекта. Следовательно, неприкаянные методы массива push and forEach окажутся в области видимости result .
Еще одна любопытная инструкция — цикл while в девятой строке. У этого цикла нет тела, поэтому factor просто продолжает увеличиваться на единицу, пока не станет нацело делиться, давая candidate в качестве частного. В следующей строке проверяется, равны ли теперь значения candidate и factor . В таком случае, у числа нет меньших делителей, следовательно, оно простое и добавляется к result .
В строке 13 перебираем результаты и во всеуслышание объявляем каждое простое число в виде alert . Наконец, программа возвращает 42.
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 (на самом деле, у всех объектов здесь причудливые диккенсовские имена) и определяется в строках 2-14. В строках 17-21 мы просто спрашиваем каждое число, простое ли оно, и добавляем простые числа в массив с результатами, который называется 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, 0, 2, 3, undefined, 5, undefined, 7].filter(Number); //[2, 3, 5, 7] Заключение
Вот и все. Надеюсь, вам понравилось.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
ссылка на оригинал статьи http://habrahabr.ru/post/275245/
Добавить комментарий