Страницы

воскресенье, 10 января 2016 г.

ES6 Iterators

Пара этюдов на тему итераторов, по мотивам The Carpenter Interviews for a Job - эпизода книги JavaScript Allongé, а также поста блога Реджинальда Брэйтуэйта (имя которого я упоминал в предыдущем посте) - Solving a Coding Problem with Iterators and Generators. Первый лишний раз подтверждает принцип KISS (в контексте изложения у меня ассоциируется с библейскими бисером и свиньями), второй... просто моя интерпретация с вариациями на тему.


1. Игра: шахматная доска неизвестного размера, в каждой клетке рандомно размещены стрелки - ←→↓↑, рандомно выставляем шашку в любую из клеток и перемещаем ее по стрелкам, если шашка дошла до края доски - победа, если нет - бесконечный цикл.

Тётя (читаем оригинал) пишет код ...
const Game = (size = 8) => {  
  // initialize the board
  const board = [];
  for (let i = 0; i < size; ++i) {
    board[i] = [];
    for (let j = 0; j < size; ++j) {
      board[i][j] = '←→↓↑'[Math.floor(Math.random() * 4)];
    }
  }
 
  // initialize the position
  let initialPosition = [
    2 + Math.floor(Math.random() * (size - 4)),
    2 + Math.floor(Math.random() * (size - 4))
  ];
 
  // ???
  let [x, y] = initialPosition;
 
  const MOVE = {
    "←": ([x, y]) => [x - 1, y],
    "→": ([x, y]) => [x + 1, y],
    "↓": ([x, y]) => [x, y - 1],
    "↑": ([x, y]) => [x, y + 1]
  };
  while (x >= 0 && y >= 0 && x < size && y < size) {
    const arrow = board[x][y];    
    // ???    
    [x, y] = MOVE[arrow]([x, y]);
  }
  // ???
};
... и ждет пока соискатель расставит пропущенные буквы.

Заканчивается все тем, что соискатель предлагает блестящее решение, которое она просто не понимает.

Попробуем сделать это simple, stupid. Для начала редактируем код чтобы он нормально работал в текущей версии V8:
var game = (size) => {
  // initialize the board
  var board = [], i, j;
  if (!(typeof size === 'number' && size > 0)) {
    size = 8;
  }
  for (i = 0; i < size; ++i) {
    board[i] = [];
    for (j = 0; j < size; ++j) {
      board[i][j] = '←→↓↑'[Math.floor(Math.random() * 4)];
    }
  }
  var move = {
    "←": (position) => [position[0] - 1, position[1]],
    "→": (position) => [position[0] + 1, position[1]],
    "↓": (position) => [position[0], position[1] - 1],
    "↑": (position) => [position[0], position[1] + 1]
  };
  // initialize the position
  var position = [
    2 + Math.floor(Math.random() * (size - 4)),
    2 + Math.floor(Math.random() * (size - 4))
  ];
  var x = position[0], y = position[1];
  // ???
  while (x >= 0 && y >= 0 && x < size && y < size) {
    position = move[board[x][y]]([x, y]);
    x = position[0];
    y = position[1];
    // ???
  }
  // ???
};
 
Расставляем пропущенные буквы, можно примерно так:
var game = (size) => {
  // initialize the board
  var board = [], i, j;
  if (!(typeof size === 'number' && size > 0)) {
    size = 8;
  }
  for (i = 0; i < size; ++i) {
    board[i] = [];
    for (j = 0; j < size; ++j) {
      board[i][j] = '←→↓↑'[Math.floor(Math.random() * 4)];
    }
  }
  var move = {
    "←": (position) => [position[0] - 1, position[1]],
    "→": (position) => [position[0] + 1, position[1]],
    "↓": (position) => [position[0], position[1] - 1],
    "↑": (position) => [position[0], position[1] + 1]
  };
  // initialize the position
  var position = [
    2 + Math.floor(Math.random() * (size - 4)),
    2 + Math.floor(Math.random() * (size - 4))
  ];
  var x = position[0], y = position[1];
  // ???
  var cache = {
    _data: [[x, y]],
    has(position) {
      return this._data.some((arr) => (arr[0] === position[0] && arr[1] === position[1]));
    },
    add(position) {
      return this._data.push(position);
    }
  };
  while (x >= 0 && y >= 0 && x < size && y < size) {
    position = move[board[x][y]]([x, y]);
    x = position[0];
    y = position[1];
    // ???
    if (cache.has(position)) {
      return { result: false, x, y };
    }
    cache.add(position);
  }
  // ???
  return { result: true, x, y };
};
 
Easy peasy:

Наверняка тётя ожидала что-то подобное.

Мне этот код совсем не нравится, я бы разделил ответственность, например вот так:
var board = (size) => {
  var arr = [], i, j;
  if (!(typeof size === 'number' && size > 0)) {
    size = 8;
  }
  for (i = 0; i < size; ++i) {
    arr[i] = [];
    for (j = 0; j < size; ++j) {
      arr[i][j] = '←→↓↑'[Math.floor(Math.random() * 4)];
    }
  }
  return arr;
};
 
var move = {
  "←": (position) => [position[0] - 1, position[1]],
  "→": (position) => [position[0] + 1, position[1]],
  "↓": (position) => [position[0], position[1] - 1],
  "↑": (position) => [position[0], position[1] + 1]
};
 
var game = (board, move) => {
  var size = board[0].length, position = [
    2 + Math.floor(Math.random() * (size - 4)),
    2 + Math.floor(Math.random() * (size - 4))
  ];
  return ({
    *[Symbol.iterator]() {
      var x = position[0], y = position[1];
      while (x >= 0 && y >= 0 && x < size && y < size) {
        yield position;
        position = move[board[x][y]]([x, y]);
        x = position[0];
        y = position[1];
      }
    }
  });
};
 
var cache = () => ({
  _data: [],
  has(position) {
    return this._data.some((arr) => (arr[0] === position[0] && arr[1] === position[1]));
  },
  add(position) {
    return this._data.push(position);
  }
});
 
var hasCycle = (cache) => (position) => {
  if (cache.has(position)) return true;
  cache.add(position);
};
 
var play = (game, fail) => {
  var position;
  for (position of game) {
    if (fail(position)) {
      return { result: false, x: position[0], y: position[1] };
    }
  }
  return { result: true, x: position[0], y: position[1] };
};

По-моему так лучше: board расставляет стрелки, move мапит стрелки на перемещения, game содержит логику перемещения, cache кэширует, hasCycle тестирует на наличие цикла, play запускает игру:

Теперь можно легко поменять cache на Set:
var game = (board, move) => {
  var size = board[0].length, position = [
    2 + Math.floor(Math.random() * (size - 4)),
    2 + Math.floor(Math.random() * (size - 4))
  ];
  return ({
    *[Symbol.iterator]() {
      var x = position[0], y = position[1];
      while (x >= 0 && y >= 0 && x < size && y < size) {
        yield `x: ${x}, y: ${y}`;
        position = move[board[x][y]]([x, y]);
        x = position[0];
        y = position[1];
      }
    }
  });
};
var cache = () => new Set();
var play = (game, fail) => {
  var position;
  for (position of game) {
    if (fail(position)) {
      return { result: false, position };
    }
  }
  return { result: true, position };
};


2. Еще одно job interview: объединение сортированных списков. Далее моя интерпретация с вариациями.

2.1. Массивы (в каких-нибудь underscore или lodash наверняка эффективнее, но в контексте job interview сгодится):
var mergeArrays = (...args) => args.reduce((prev, next) => prev.concat(next), []);
 
var mergeArraysNested = (...args) => args.reduce((prev, next) => {
  for (var value of next) {
    if (Array.isArray(value)) {
      prev = prev.concat(mergeArraysNested(value));
    } else {
      prev.push(value);
    }
  }
  return prev;
}, []);
 
var mergeArraysAndSort = (...args) => {
  var fn = typeof args[args.length - 1] === 'function' && args.pop();
  return mergeArrays(...args).sort(fn);
};
 
var mergeArraysRoundRobin = (...args) => {
  var arr = [], i;
  args.reverse();
  while (i = args.length) {
    while (i--) {
      if (!args[i].length) {
        args.splice(i, 1);
        continue;
      }
      arr.push(args[i].shift());        
    }
  }
  return arr;
};


2.2. Итераторы (итерируемые объекты):
var mergeIterables = (...args) => {
  args.reverse();
  return {
    [Symbol.iterator]: function*() {      
      var its = args.map(arg => arg[Symbol.iterator]()), i = args.length, it;
      while (i--) {
        while (it = its[i].next(), !it.done) {
          yield it.value;
        }        
      }      
    }
  };
};
 
var mergeIterablesSimple = (...args) => {
  return {
    [Symbol.iterator]: function*() {   
      for (var it of args) {
        yield* it;
      }          
    }
  };
};
 
var mergeIterablesNested = (...args) => {
  return {
    [Symbol.iterator]: function*() {   
      var it, i;
      for (it of args) {
        for (i of it) {
          if (i[Symbol.iterator]) {
            yield* mergeIterablesNested(i);            
          } else {
            yield i;            
          }
        }        
      }          
    }
  };
};
 
var mergeIterablesRoundRobin = (...args) => {  
  args.reverse();
  return {
    [Symbol.iterator]: function*() {      
      var its = args.map(arg => arg[Symbol.iterator]()), i, it;      
      while (i = its.length) {
        while (i--) {
          it = its[i].next();
          if (it.done) {          
            its.splice(i, 1);
            continue;
          }
          yield it.value;                  
        }
      }
    }
  };
};
 
var mergeIterablesAndSort = (...args) => {  
  var sort = typeof args[args.length - 1] === 'function' && args.pop();
  var fn = sort ? (a,b) => sort(a.prev.value, b.prev.value) : (a,b) => (a.prev.value - b.prev.value);
  return {
    [Symbol.iterator]: function*() {
      var its = args.map(arg => {
        var it = arg[Symbol.iterator]();
        return {
          prev: it.next(),
          next() {
            var curr = this.prev;
            this.prev = it.next();
            return curr;
          }
        };
      }), i = its.length;
      while (i) {
        while (i--) {
          if (its[i].prev.done) {
            its.splice(i, 1);
          }
        }
        i = its.length;
        if (i) {
          if (i > 1) {
            its.sort(fn);
          }
          yield its[0].next().value;
        }
      }            
    }
  };  
};


Здесь комментировать нечего, найди отличия от оригинала.