Как выйти из std.algorithm.iteration.recece преждевременно? - PullRequest
Новая
       5

Как выйти из std.algorithm.iteration.recece преждевременно?

0 голосов
/ 10 декабря 2018

У меня есть следующая функция findFirstDuplicateFrequency, которая реализует (правильно) алгоритм для программирования пазл .

Вместо обязательного зацикливания я хотел бы продвигать D's функционалфункции и думал, что смогу применить уменьшить к проблеме.

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

AFAICS Стандартное уменьшение не может быть завершено в середине обработки, и я также борюсь, как получить дополнительную информацию о накопителе, которая используется для вычисления условия выхода.

Итак, каков будет правильный (?) Идиоматический D-подход для решения проблемы (более) функциональным способом?

Это моя самая первая D-программа в истории, и поэтому все остальные комментариидобро пожаловать тоже! 

import std.conv: to;

/**
From: https://adventofcode.com/2018/day/1

You notice that the device repeats the same frequency change list over and
over. To calibrate the device, you need to find the first frequency it reaches
twice.

For example, using the same list of changes above, the device would loop as
follows:

    Current frequency  0, change of +1; resulting frequency  1.
    Current frequency  1, change of -2; resulting frequency -1.
    Current frequency -1, change of +3; resulting frequency  2.
    Current frequency  2, change of +1; resulting frequency  3.
    (At this point, the device continues from the start of the list.)
    Current frequency  3, change of +1; resulting frequency  4.
    Current frequency  4, change of -2; resulting frequency  2, which has already been seen.

In this example, the first frequency reached twice is 2. Note that your device
might need to repeat its list of frequency changes many times before a
duplicate frequency is found, and that duplicates might be found while in the
middle of processing the list.

Here are other examples:

    +1, -1 first reaches 0 twice.
    +3, +3, +4, -2, -4 first reaches 10 twice.
    -6, +3, +8, +5, -6 first reaches 5 twice.
    +7, +7, -2, -7, -4 first reaches 14 twice.

What is the first frequency your device reaches twice?
*/
int findFirstDuplicateFrequency(int[] frequencyChanges)
pure
{
  int[int] alreadySeen = [0:1];
  int frequency = 0;

 out_: while(true) {
    foreach(change; frequencyChanges) {
      frequency += change;
      if (int* _ = frequency in alreadySeen) {
        break out_;
      } else {
        alreadySeen[frequency] = 1;
      }
    }
  }

  return frequency;
} unittest {
  int answer = 0;

  answer = findFirstDuplicateFrequency([1, -2, 3, 1]);
  assert(answer == 2, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequency([1, -1]);
  assert(answer == 0, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequency([3, 3, 4, -2, -4]);
  assert(answer == 10, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequency([-6, 3, 8, 5, -6]);
  assert(answer == 5, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequency([7, 7, -2, -7, -4]);
  assert(answer == 14, "Got: " ~ to!string(answer));
}

void main() {}

1 Ответ

0 голосов
/ 15 декабря 2018

Даже в соответствии с @ AdamD.Ruppe, нет больших надежд сделать код более «функциональным». Я был вдохновлен подсказкой @ 1001 * + until от BioTronic и решил посмотреть второй взгляд.

К сожалению, я не вижу способа применить cumulativeFold + until, поскольку у меня нет значения дозорного, требуемого для until, и проблема с остановкой по-прежнему та же, что и для reduce.

КогдаЯ просматривал ссылку на стандартную библиотеку времени выполнения Я заметил, что each действительно имеют опцию раннего выхода (или частичной итерации).Я также сталкиваюсь с std.range.cycle.

Объединяя эти две блестящие новые вещи, я пришел к решению ниже.findFirstDuplicateFrequencyV2 использует cycle и each для замены императивных циклов первой версии.Я не уверен, что эта версия проще, но, надеюсь, она более "модная"! 

int findFirstDuplicateFrequencyV2(int[] frequencyChanges)
pure
{
  import std.algorithm.iteration : each;
  import std.range : cycle;
  import std.typecons : Yes, No;

  int[int] alreadySeen = [0:1];
  int frequency = 0;

  frequencyChanges.cycle.each!((change) {
      frequency += change;
      if (frequency in alreadySeen) {
        return No.each;
      }
      alreadySeen[frequency] = 1;
      return Yes.each;
    });

  return frequency;
} unittest {
  import std.conv : to;

  int answer = 0;

  answer = findFirstDuplicateFrequencyV2([1, -2, 3, 1]);
  assert(answer == 2, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequencyV2([1, -1]);
  assert(answer == 0, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequencyV2([3, 3, 4, -2, -4]);
  assert(answer == 10, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequencyV2([-6, 3, 8, 5, -6]);
  assert(answer == 5, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequencyV2([7, 7, -2, -7, -4]);
  assert(answer == 14, "Got: " ~ to!string(answer));
}
...