Я люблю разгадывать головоломки, люблю JavaScript и почти каждую неделю слушаю воскресную головоломку Уилла Шортза. Часто я ловлю себя на мысли о том, как решить головоломки Уилла с помощью кода. Этот и последующие посты - способ объединить мои увлечения и, надеюсь, немного научить JavaScript и алгоритмы.

Это первая часть решения головоломок Puzzlemaster представляет с помощью JavaScript! Я буду пытаться разгадывать головоломку каждую неделю, используя как можно больше кодового мышления, так что ждите больше. Я попытаюсь коснуться преимуществ и недостатков дизайнерских решений, но имейте в виду, что код, который я пишу здесь, не обязательно будет оптимизирован для повышения скорости. При этом, если вам нравятся решения, у вас есть улучшение, комментарий или предложение, добавьте комментарий!

Сегодняшняя головоломка - это смесь слов между странами и животными:

Буквы «Швейцария» можно переставить так, чтобы записать ящерицу и тритона: ящерица - это имя животного в единственном числе, а тритоны - во множественном числе. Назовите другую страну с такой же собственностью. Это имя другой страны, буквы которой можно переставить, чтобы назвать двух животных, одно единственное и одно множественное. Это крупная страна. Что это за страна?

Сразу же мы видим, что нам, вероятно, понадобится набор всех стран и набор всех животных.

Страны не такие уж и сложные, и мы можем найти их все у пользователя github kalinchernev‘ countries ’gist:

afghanistan
albania
algeria
...

Животные немного хитрее. Мы можем найти список всех единичных животных из пользователя github atduskgreg’s‘ animals ’gist:

cat
cattle
dog
...

Однако важно учитывать, что нам нужно будет использовать множественное число от этих животных. У большинства будет множественное число, к которому просто добавлен s, но у некоторых (например, Deer или Goose) есть специальные множественные числа. При поиске в Google по запросу животные во множественном числе появляется страница Википедии, посвященная« Условиям Венери », иначе говоря, группы животных, которые называются стаями китов. На этой странице перечислены более 200 видов животных с их вкусными названиями, но все, что нас волнует, - это формы множественного числа этих животных:

albatross
antalopes
ants
...

Обратите внимание, что все словарные данные, которые я использую в этом посте (и, возможно, в будущих постах), были преобразованы в строчные буквы.

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

Теперь давайте спланируем наше решение с учетом имеющихся данных.

Во-первых, они дают нам пример switzerland становления lizard newts. Как мы можем быть уверены, что они правы? Чтобы доказать это, нам просто нужно доказать, что страна и пара животных в единственном и множественном числе являются анаграммами. Один из быстрых способов определить, являются ли две строки анаграммами, - это отсортировать строки и сравнить отсортированные значения. Это также помогает удалить пробелы и другие бесполезные символы. Эту комбинацию я буду называть сортировкой по принципу смешения, а с этого момента и тем и другим.

// A utility method to compare strings as anagrams
// Eg, 'i like cake' => 'aceeiikkl'
function smooshSort(str) {
  return str
    .replace(/\s+/g, '') // Remove whitespace
    .split('') // Turn the string into a list of characters
    .filter(char => char) // Filter out strange falsy characters
    .sort() // Sort the characters alphabetically
    .join(''); // Turn the sorted characters back into a string
}

После того, как мы размельчились, мы видим, что switzerland и lizard newts оба становятся adeilnrstwz и, таким образом, являются анаграммами друг друга.

Один из способов найти все страны, которые могут стать парами животных в единственном числе и множественном числе (которые с этого момента будут называться просто парами животных), - это создать набор всех стран с размолвками и список всех пар животных, а затем проверить, чтобы посмотрите, не входит ли какая-либо из пар животных, которые тушат друг друга, в наборе стран с тусклым телом.

Я предпочитаю использовать карту ES6 для разбитых стран, потому что это сократит время поиска по сравнению с использованием массива разбитых стран. Мы могли бы использовать Set или обычный объект, но мне нравится использовать Карты, потому что они более выразительны.

Чтобы создать нашу карту стран, все, что нам нужно сделать, это загрузить страны из файла .txt, отсортировать каждую страну, а затем сопоставить каждое отсортированное название страны с ее исходным названием:

function smooshedCountries() {
  const allCountries = loadCountries();
  return new Map(allCountries.map(country => [
    smooshSort(country),
    country
  ]));
}

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

'aardvark aardvarks'
'aardvark bears'
'aardvark cats'
...
'bear aardvarks'
'bear bears'
'bear cats'
...

Имейте в виду, что животные во множественном числе должны будут включать как животных в единственном числе с прикрепленным s, так и всех особых животных, которые мы получили со страницы Венери в Википедии. Тоже заговор лемуров ?!

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

// Creates a list of paired singular and plural animals 
// Also smooshes them for later
// Output: [['acdgost', 'cat dogs'], ['acgipst', 'cat pigs'], ...]
function allAnimalPairs() {
  // Load in the list of singular animals
  const allAnimals = loadAnimals();
  // Load in the list of plural animals
  const allAnimalPlurals = loadAnimalPlurals();
  // Initialize an empty array for the pairs
  const flattenedPairs = []
  // For each animal
  allAnimals.forEach(singularAnimal => {
    // For each animal (yes, this is an n squared loop)
    allAnimals.forEach(pluralAnimal => {
      // Add an 's' plural of the animal
      const combined = `${singularAnimal} ${pluralAnimal}s`
      flattenedPairs.push([smooshSort(combined), combined]);
    });
    // For each plural animal
    allAnimals.concat(allAnimalPlurals).forEach(pluralAnimal => {
      // Combine the animals without an extra 's' on the plural
      const combined = `${singularAnimal} ${pluralAnimal}`
      flattenedPairs.push([smooshSort(combined), combined]);
    });
  });
  // Return the entire list of smooshed and paired tuples
  return flattenedPairs;
}

Наконец, мы можем объединить все воедино. У нас есть карта раздавленных стран и список пар животных. Все, что нам нужно сделать, это отфильтровать пары животных, чьи версии не попали на карту страны:

function findCountryAnimals() {
  const countries = smooshedCountries();
  // Filters animal pairs who's smooshed versions
  // aren't keys in the countries Map
  const countryAnimals = allAnimalPairs()
    .filter(animalPair => countries.has(animalPair[0]));
  // Removes duplicate animal pairs for a single country
  return new Map(countryAnimals.map(countryAnimal => [
    countries.get(countryAnimal[0]),
    countryAnimal[1]
  ]));
}

Запустив наш скрипт, получаем результат:

'pakistan' => 'takin asp',
'switzerland' => 'newt lizards',
'mexico' => 'ox mice'

Хороший! Похоже, есть три решения, одно из которых - комбинация Швейцария / Ньют / Ящерица, которую дал нам Уилл Шортц. Похоже, что ответ «крупная страна» будет Мексика / Бык / Мыши, но ответ Пакистан / Такин / Асп также полностью верен. Если вам, как и мне, было интересно, что такое Такин и Асп, вот несколько картинок:

Используя пару вызовов Date.now(), я обнаружил, что скрипт 2.79 секунд. Это было бы довольно ужасно на рабочем сервере, но не так уж и плохо, если у вас есть целая неделя, чтобы найти ответ.

Надеюсь, вам понравилась эта неделя решения головоломок для мастеров с помощью JavaScript! Теперь отправляйтесь в мир программирования, как Crash или Rhinos.