DEV Community

Advent of Code 2020 Solution Megathread - Day 10: Adapter Array

Ryan Palo on December 10, 2020

We're now 40% of the way done. Almost halfway! You can make it! You can do it! I believe in you! Even if you fell off the sleigh, as they say,...

Read full post

Derk-Jan Karrenbeld • Dec 10 '20

I didn't really have fun today. My final solution in Ruby took way too long to get too and doesn't feel like an accomplishment. Rather it's a Dynamic Programming trick you just have to know or see, but not something to derive at logically or interestingly.

The grunt work is O(n), the sort is O(n log n), so sorting the input becomes the "limiting" factor. YMMV.

require 'benchmark'

adapters = File.readlines('input.txt').map(&:to_i).sort
maximum_jolt = adapters.last + 3
adapters.push(maximum_jolt)

=begin
# For the example input, here is what is being calculated:

target:  options                   => total options
     1:  only 1 option (0 + 1)     => 1
     4:  only 1 option (1 + 3)     => 1
     5:  only 1 option (4 + 1)     => 1
     6:  either 4 + 2 or 5 + 1     => 2
     7:  6 + 1 or 5 + 2 or 4 + 3   => 2 (6) + 1 (5) + 1 (4)
    10:  only 1 option (7 + 3)     => 4
    11:  only 1 option (10 + 1)    => 4
    12:  either 10 + 2 or 11 + 1   => 4 (10) + 4 (11)
    15:  only 1 option 12 + 3      => 8
    16:  only 1 option 15 + 1      => 8
    19:  only 1 option 16 + 3      => 8
    22:  only 1 option 19 + 3      => 8
=end

Benchmark.bm do |x|
  x.report(:part_1) do
    jolt_groups = adapters
      .each_with_index
      .map do |adapter, index|
        adapter - (index > 0 ? adapters[index - 1] : 0)
      end
      .group_by(&:itself)

    puts jolt_groups[1].length * jolt_groups[3].length
  end

  x.report(:part_2) do
    # Track the number of options to get to a target jolt value
    # and default to 0. The first jolt value is 0, and can only
    # be reached in one way.
    options = Hash.new(0)
    options[0] = 1

    adapters.each do |target_jolts|
      options[target_jolts] = [1, 2, 3]
        .sum { |difference| options[target_jolts - difference] }
    end

    puts options[maximum_jolt]
  end
end

Nick Lehmann • Dec 11 '20

Hey, thank you very much! Could you give me a hint on how this "trick" is called?

Derk-Jan Karrenbeld • Dec 11 '20

Certainly. It's dynamic programming!

In this case, the problem can be broken down and simplified. We're not looking for the list of combinations. We are looking for the total number of options to build a valid connection between start (0) and end (max + 3).

For each adapter the following is true:

The number of paths to get to this adapter from the start is equal to the sum of the number of paths to get from the previous adapter to this one.

That means that this problem can be reduced. You can walk the list from start to end or end to start and only answer the question: paths to / paths from this adapter.

Storing the intermediate outcome is a typical dynamic programming this.

Determine number of paths between start and first adapter (always 1). Store it.

1:  only 1 option (0 + 1)     => 1

Stored is the value 1 (ways to get to this index) on the index 1 (the joltage of the first adapter):

[1]

Determine number of paths between the second - 1 and second - 2 adapters. This is the total number of paths from start to the second adapter. Store it.

4:  only 1 option (1 + 3)     => 1

4 - 1: 0
4 - 2: 0
4 - 3: 1

Stored at index 4 (joltage) is the number of paths to this index: ways to joltage 4 - 3 plus ways to joltage 4 - 2 plus ways to joltage 4 - 1.

[1, 0, 0 , 0,1]

Determine number of paths between the third - 1, third - 2 and third - 3 adapters. The sum is the total number of paths from start tot the third adapter. Store it.

5:  only 1 option (4 + 1)     => 1

5 - 1: 1
5 - 2: 0
5 - 3: 0

Stored at index 5 (joltage) is the number of paths to this index: ways to joltage 5 - 3 plus ways to joltage 5 - 2 plus ways to joltage 5 - 1.

[1, 0, 0 , 0, 1, 1]

Determine number of paths between the fourth - 1, fourth - 2 and fourth - 3 adapters. The sum is the total number of paths from start tot the fourth adapter. Store it.

6:  either 4 + 2 or 5 + 1     => 2

6 - 1: 1
6 - 2: 1
6 - 3: 0

As you can see, here is where it becomes interesting. By storing the ways to get to a joltage in the array, when we need it's évalués, it doesn't need to calculate or worse, recalculate those values.

[1, 0, 0 , 0, 1, 1, 2]

This is what is key in Dynamic Programming. You store intermediate results so that you don't need to do the work again. A classic example is solving Fibonacci.

You may want to solve it recursively, but the problem with doing that without memorisation step is that you'll be calculating the same values over and over. Instead, because each fib(n) equals fib(n-1) + fib(n-2), the pair input and output can reduce the recursive complexity of
O(2^n) to O(n). Each term is only considered once, instead of many many many times.

Nick Lehmann • Dec 13 '20 • Edited

Oh wow, thank you very much 🚀 Really didn't expect such a lengthy, comprehensible answer. So, thank you very much again! Just thought it's a special technique one could look up and practice but I guess I just have to look into dynamic programming again 👍🏻

Derk-Jan Karrenbeld • Dec 13 '20

Yeah. Once you do a series of solutions using Dynamic Programming, you'll get a feel for it!

Joni Bekenstein • Dec 27 '20

Thanks for the clear explanation Derk-Jan Karrenbeld!

Here is my implementation in Python:

#!/usr/bin/env python3

import sys


if __name__ == '__main__':
    adapters = list(sorted(map(int, sys.stdin.read().strip().split('\n'))))
    adapters = [0] + adapters
    valid_arrangements = [1] * len(adapters)
    for index in range(1, len(adapters)):
        valid_arrangements[index] = sum(
            valid_arrangements[src_index]
            for src_index in range(max(0, index - 3), index)
            if adapters[index] - adapters[src_index] <= 3
        )
    print(valid_arrangements[-1])

Mike Gasparelli • Dec 11 '20

Another day where I solved Part1 and had to go back to rewrite it when Part2 came around!

My insight was that you could count the length of the sequences of 1 joltage deltas, and use that to derive the number of possible combinations. Unfortunately, I wasn't able to figure out the general formula for sequenceLength->permutations, and had to hardcode the table 😣

Part 1

        public override long SampleAnswer => 220;

        public override IEnumerable<int> ParseInput(string rawInput)
            => rawInput
                .Split(Environment.NewLine)
                .Where(line => line.Length > 0)
                .Select(line => int.Parse(line));

        public override long Solve(IEnumerable<int> input)
        {
            var deltas = GetDeltas(input.OrderBy(x => x).ToArray());
            return deltas.Count(x => x == 1) * deltas.Count(x => x == 3);
        }

        protected int[] GetDeltas(int[] values)
        {
            var deltas = new int[values.Length + 1];
            for (var i = 1; i < values.Length; i++)
            {
                deltas[i] = values[i] - values[i - 1];
            }

            deltas[0] = values[0];        // joltage between outlet and first adapter.
            deltas[values.Length] = 3;    // joltage between last adapter and device.

            return deltas;
        }

Part 2

    public class Part2 : Part1
    {
        public override long SampleAnswer => 19208;

        public override long Solve(IEnumerable<int> input)
        {
            int[] deltas = GetDeltas(input.OrderBy(x => x).ToArray());

            return  GetContiguousOnesCounts(deltas)
                .Aggregate(1L, (sum, cur) => sum *= PossibleCombinations(cur));
        }

        IEnumerable<int> GetContiguousOnesCounts(IEnumerable<int> deltas)
        {
            int contiguousOnes = 0;
            foreach(var delta in deltas)
            {
                if (delta == 1)
                {
                    contiguousOnes++;
                    continue;
                }

                if (contiguousOnes == 0)
                {
                    continue;
                }

                yield return contiguousOnes;
                contiguousOnes = 0;
            }
        }

        long PossibleCombinations(int seqLength)
            => seqLength switch
            {
                1 => 1,
                2 => 2,
                3 => 4,
                4 => 7,
                5 => 13,
                6 => 22,
                _ => 0
            };
    }

Kudos Beluga • Dec 10 '20 • Edited

Part 1 minified javascript solution:

let t=require("fs"),e=[];t.readFile("input.txt","utf8",(t,l)=>{if(t)throw t;for(i in l=l.split("\n").map(t=>Number(t)).sort((t,e)=>t-e))e.push(l[parseInt(i)+1]-l[i]);console.log((e.filter(t=>3==t).length+1)*(e.filter(t=>1==t).length+1))})

Here it is in normal beauty:

let fs = require("fs"),
    arr = [];
fs.readFile("input.txt", "utf8", (err, data) => {
    if (err) throw err;
    data = data.split("\n").map(e => Number(e)).sort((a, b) => a - b);
    for (i in data) {
        arr.push(data[parseInt(i) + 1] - data[i]);
    }
    console.log((arr.filter(e => e == 3).length + 1) * (arr.filter(e => e == 1).length + 1));
})

Posting part2 soon!

Neil Gall • Dec 10 '20

Bit of a mad mix of imperative and functional programming for me today. I hate calculating permutations.

use std::collections::HashMap;
use std::fs::File;
use std::io::prelude::*;


// --- file read

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

fn parse_input(input: &str) -> Vec<i64> {
    input.split_ascii_whitespace().map(|s| s.parse().unwrap()).collect()
}

// --- problems

fn differences(xs: &[i64]) -> Vec<i64> {
    let mut diffs = vec![];
    let mut ixs = xs.iter();
    let mut prev = ixs.next().unwrap();
    while let Some(next) = ixs.next() {
        diffs.push(next - prev);
        prev = next;
    }
    diffs
}

fn distribution(xs: &[i64]) -> HashMap<i64, usize> {
    let mut dist = HashMap::new();
    for next in xs.iter() {
        let count = dist.get(next).unwrap_or(&0) + 1;
        dist.insert(*next, count);
    }
    dist
}

fn adapter_order(adapters: &[i64]) -> Vec<i64> {
    let mut ordered = adapters.to_vec();
    ordered.push(0);
    ordered.push(*adapters.iter().max().unwrap() + 3);
    ordered.sort();
    ordered
}

fn adapter_permutations(adapters: &[i64]) -> usize {
    differences(&adapter_order(adapters)).iter().fold((1, 0), 
        |(permutations, ones), diff|
            if *diff == 1 {
                (permutations, ones+1)
            } else { 
                match ones {
                    0 => (permutations, 0),
                    1 => (permutations, 0),
                    2 => (permutations * 2, 0),
                    3 => (permutations * 4, 0),
                    _ => (permutations * ((1 << (ones-1)) - 1), 0)
                }
            }
        ).0
}

fn part1(adapters: &Vec<i64>) -> Option<usize> {
    let dist = distribution(&differences(&adapter_order(adapters)));
    dist.get(&1).and_then(|ones|
        dist.get(&3).map(|threes| ones * threes)
    )
}

fn part2(adapters: &Vec<i64>) -> usize {
    adapter_permutations(adapters)
}   


fn main() {
    let input = read_file("./input.txt").unwrap();
    let adapters = parse_input(&input);
    println!("part1 {:?}", part1(&adapters));
    println!("part2 {:?}", part2(&adapters));
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parser() {
        assert_eq!(parse_input("1 2 3 4"), vec![1, 2, 3, 4]);
        assert_eq!(parse_input("15\n16\n0\n99"), vec![15, 16, 0, 99]);
    }

    #[test]
    fn test_adapter_order() {
        let adapters = vec![16,10,15,5,1,11,7,19,6,12,4];
        let ordered = adapter_order(&adapters);
        assert_eq!(ordered, vec![0,1,4,5,6,7,10,11,12,15,16,19,22]);
    }

    #[test]
    fn test_differences() {
        let sequence = vec![0,1,4,5,6,7,10,11,12,15,16,19,22];
        assert_eq!(differences(&sequence), vec![1,3,1,1,1,3,1,1,3,1,3,3]);
    }

    #[test]
    fn test_distribution_of_diffs() {
        let sequence = vec![0,1,4,5,6,7,10,11,12,15,16,19,22];
        let distribution = distribution(&differences(&sequence));
        assert_eq!(distribution.len(), 2);
        assert_eq!(distribution.get(&1), Some(&7));
        assert_eq!(distribution.get(&3), Some(&5));
    }

    #[test]
    fn test_part1_example_1() {
        let adapters = vec![16,10,15,5,1,11,7,19,6,12,4];
        assert_eq!(part1(&adapters), Some(35));
    }

    #[test]
    fn test_part1_example_2() {
        let adapters = vec![28,33,18,42,31,14,46,20,48,47,24,23,49,45,19,38,39,11,1,32,25,35,8,17,7,9,4,2,34,10,3];
        assert_eq!(part1(&adapters), Some(220));
    }

    #[test]
    fn test_adapter_permutations_example_1() {
        let adapters = vec![16,10,15,5,1,11,7,19,6,12,4];
        assert_eq!(adapter_permutations(&adapters), 8);        
    }

    #[test]
    fn test_adapter_permutations_example_2() {
        let adapters = vec![28,33,18,42,31,14,46,20,48,47,24,23,49,45,19,38,39,11,1,32,25,35,8,17,7,9,4,2,34,10,3];
        assert_eq!(adapter_permutations(&adapters), 19208);        
    }
}

Frederik 👨‍💻➡️🌐 Creemers • Dec 12 '20

My Elixir solution:

defmodule Adapters do
  def getSortedAdapters() do
    {:ok, text} = File.read("10.txt")
    lines = String.split(text, "\n")
    lines = List.delete_at(lines, length(lines)-1) # remove empty line
    joltages = Enum.map(lines, &String.to_integer/1)
    Enum.sort(joltages)
  end

  def round1() do
    adapters = getSortedAdapters()
    {ones, threes, _prev} = Enum.reduce(adapters, {0, 0, 0}, fn (x, {ones, threes, prev}) ->
      cond do
        (x - prev) == 1 ->
          {ones + 1, threes, x}
        (x - prev) == 3 ->
          {ones, threes + 1, x}
        true ->
          {ones, threes, x}
      end
    end)
    threes = threes + 1 # hop from the last adapter to the built-in one
    IO.puts("#{ones} * #{threes} = #{ones * threes}")
  end

  def count_connections_upto(current, sofar) do
    IO.puts(current)
    sofar
      |> Enum.take_while(fn {adapter, _ways} -> adapter >= (current - 3) end)
      |> Enum.map(fn {_adapter, ways} -> ways end )
      |> Enum.sum()
  end

  def count_connections(adapters, sofar) do
    [current | remaining] = adapters

    n = count_connections_upto(current, sofar)
    if length(remaining) > 0 do
      count_connections(remaining, [{current, n} | sofar])
    else
      n
    end
  end

  def round2() do
    adapters = getSortedAdapters()
    IO.puts(count_connections(adapters, [{0, 1}]))
  end
end

Adapters.round2()

Ryan Palo • Dec 11 '20

Did a bit of tricky business after looking over the test cases and my input. Linear time with no recursion.

Because the numbers in my input were either 3 or 1 apart, never 2, and there were never more than 4 1's in a row before a 3, I pre-calculated the # of possibilities each of the possible patterns generated and then multiplied together to find all possible combinations.

3 - 3 (e.g. 4, 7, 10) => only 1 possible configuration
3 - 1 - 3 (e.g. 4, 7, 8, 11) => only 1 possible configuration
3 - 1 - 1 - 3 (e.g. 4, 7, 8, 9, 12) => 2 possible configurations (drop the middle number or don't)
3 - 1 - 1 - 1 - 3 (e.g. 4, 7, 8, 9, 10, 13) => 4 possible configurations (2 each for 8 and 9)
3 - 1 - 1 - 1 - 1 - 3 (e.g. 4, 7, 8, 9, 10, 11, 14) => 7 possible configurations (at least one of 8, 9, 10 must be present, so 2^3 - 1 since dropping all 3 not an option)

Then I rolled through the list producting up all the values for each "cell" of ones. The only thing I had an issue with is that I didn't think about the fact that the result was going to be a long long int, so I chased my tail printing out regular ints for a while even though my algorithm was right.

Also, TIL that C has a build-in sorting function called qsort!

#include "Day10.h"

#include <stdio.h>

#include "parsing.h"

/// Day 10: Adapter Array
///
/// Use power adapters to calculate "joltage" jumps from connection
/// to connection.

/// In a sorted array of adapters, return the number of jumps of size 1
/// multiplied by the jumps of size 3.

/// Parse the input file, one number per line into a list of integers.
static int* parse(const char* filename, int* count) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open file.\n");
    exit(EXIT_FAILURE);
  }

  *count = count_lines(fp);

  // It's going to be easier if we manually attach our outlet and device
  *count += 2;
  int* numbers = (int*)malloc(sizeof(int) * *count);

  numbers[0] = 0;
  numbers[*count - 1] = 4 * *count; // Something so huge goes to the end.
  for (int i = 1; i < *count - 1; i++) {
    char buf[5] = {0};
    fgets(buf, 5, fp);
    numbers[i] = atoi(buf);
  }

  fclose(fp);
  return numbers;
}

/// Integer comparison function for qsort.
int cmp(const void* a, const void* b) {
  return (*(int*)a - *(int*)b);
}

int part1(const char* filename) {
  int count = 0;
  int* numbers = parse(filename, &count);

  qsort(numbers, count, sizeof(int), cmp);
  numbers[count - 1] = numbers[count - 2] + 3;

  int ones = 0;
  int threes = 0;

  for (int i = 1; i < count; i++) {
    int jump = numbers[i] - numbers[i - 1];
    if (jump == 1) ones++;
    else if (jump == 3) threes++;
  }

  free(numbers);
  return ones * threes;
}

/// How many possibilities does a group of continuous ones yield?
static int pattern_to_variants(int ones) {
  switch (ones) {
    case 0: return 1;
    case 1: return 1;
    case 2: return 2;
    case 3: return 4;
    case 4: return 7;
    default:
      printf("Crap, didn't account for > 4 ones.\n");
      exit(EXIT_FAILURE);
  }
}

/// Count the number of distinct arrangements of adapters that
/// would still work.
long long int part2(const char* filename) {
  int count = 0;
  int* numbers = parse(filename, &count);

  qsort(numbers, count, sizeof(int), cmp);
  numbers[count - 1] = numbers[count - 2] + 3;

  int ones = 0;
  long long int product = 1;

  for (int i = 1; i < count; i++) {  
    int jump = numbers[i] - numbers[i - 1];
    if (jump == 1) {
      ones++;
    } else if (jump == 3) {
      product *= pattern_to_variants(ones);
      ones = 0;
    } else {
      printf("Crap, this doesn't work for jumps of 2.\n");
      exit(EXIT_FAILURE);
    }
  }
  return product;
}

/// Run both parts.
int day10() {
  printf("====== Day 10 ======\n");
  printf("Part 1: %d\n", part1("data/day10.txt"));
  printf("Part 2: %lli\n", part2("data/day10.txt"));
  return EXIT_SUCCESS;
}

craigontour • Dec 10 '20

I also use Ruby (if I have time try to replicate in Python for learning) and found part 1 ok.

 input = File.read('day10.txt').split("\n").map(&:to_i).sort!.insert(0, 0)
 input.push(input[-1]+3)

 puts "Part 1:"
 puts (0...(input.length-1)).each
                            .map { |a| input[a+1]-input[a] }
                            .group_by { |n| n }
                            .map { |e, v| v.length }
                            .reduce(:*)

But Part 2 stumped me. I got the general gist of the problem, but couldn't get started on a solution.

Pukar Giri • Dec 19 '20 • Edited

heres the solution in python for both part1 and 2 :

data=""
with open("input9.txt","r") as infile:
    data=infile.read().strip()
numbers=list(map(int, data.split("\n")))
numbers=sorted(numbers)
diff3=0
diff1=0
numbers.append(numbers[-1]+3)
numbers=[0]+numbers
memory=[1]
def no_of_paths(n):
    s=0
    for x in range(n-1,-1,-1):
        if(numbers[n]-numbers[x]<=3):s+=memory[x]
        else:   break
    return s
for x in range(1,len(numbers)):
    memory.append(no_of_paths(x))
    diff=numbers[x]-numbers[x-1]
    if(diff==1):diff1+=1
    elif(diff==3):diff3+=1
print("1. ans = ",diff3*diff1)
print("2. ans =",memory[-1])

Dirk Fraanje (the Netherlands) • Dec 11 '20

C# solution part 1.
Execution time: 0ms, 235 ticks, the quickest so far :)

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace AdventOfCode2020
{
    static class Day10
    {

        static int counterDif1 = 0;
        static int counterDif3 = 0;
        static List<int> input;

        public static void Execute()
        {
            input = File.ReadAllLines("//inputfile.txt").Select(r=> int.Parse(r)).ToList();

            //Added a imer just for fun
            var timer = new Stopwatch();
            timer.Start();

            input.Insert(0, 0);
            input.Sort();
            for (int i = input.Count-1; i >= 1; i--)
            {
                var dif = input[i] - input[i-1];
                if (dif == 1)
                    counterDif1++;
                else if (dif == 3)
                    counterDif3++;
                else
                    throw new Exception($"{dif}");
            }
            //Finally add the last adapter to your device
            counterDif3++;

            timer.Stop();
            Console.WriteLine($"1 jolts difference: {counterDif1} ");
            Console.WriteLine($"3 jolts difference: {counterDif3} ");
            Console.WriteLine($"1-jolts multiplied by 3-jolts: {counterDif1 * counterDif3}");
            Console.WriteLine($"Executed in: {timer.ElapsedMilliseconds} milliseconds, {timer.ElapsedTicks} ticks");
        }


    }
}

Benjamin Trent • Dec 10 '20

Took me a while to figure out. I was initially going down some path finding algorithm. But after looking at it a while It started to look like some dynamic programming/combinatorics.

Took me a while to get the actual equation down but finally did it.
input is with 0 and max + 3 already added.

#[aoc(day10, part1)]
fn the_path(input: &Vec<usize>) -> usize {
    let mut one_count = 0;
    let mut three_count = 0;
    for (i, v) in input[..input.len() - 1].iter().enumerate() {
        let diff = ((*v) as i32 - (input[i + 1]) as i32).abs() as usize;
        if diff == 1 {
            one_count += 1;
        } else if diff == 3 {
            three_count += 1;
        }
    }
    one_count * three_count
}

#[aoc(day10, part2)]
fn all_combinations(input: &Vec<usize>) -> usize {
    let mut the_ways = HashMap::new();
    // Only one way to get to 0 or 1
    the_ways.insert(0, 1);
    the_ways.insert(1, 1);
    for &v in &input[2..] {
        let mut val = the_ways.get(&(v - 1)).unwrap_or(&0) + the_ways.get(&(v - 2)).unwrap_or(&0);
        if v > 2 {
            val += the_ways.get(&(v - 3)).unwrap_or(&0);
        }
        the_ways.insert(v, val);
    }
    *the_ways.get(input.last().unwrap()).unwrap()
}

coderinblack • Dec 10 '20

Part 2 javscript solution 🎨:

const fs = require('fs').promises;
const path = require('path');

const main = async () => {
  const input = await fs.readFile(path.join(__dirname, './10.txt'), 'utf-8');
  let lines = input.split('\n').map((x) => parseInt(x));
  const cache = {};

  lines.push(0, Math.max(...lines) + 3);
  lines = lines.sort((a, b) => a - b);

  const dp = (n) => {
    if (n === lines.length - 1) {
      return 1;
    }
    if (n in cache) {
      return cache[n];
    }
    let ans = 0;
    for (let i = n + 1; i < lines.length; i++) {
      if (lines[i] - lines[n] <= 3) {
        ans += dp(i);
      }
    }
    cache[n] = ans;
    return ans;
  };

  console.log(dp(0));
};

main();

Anna • Dec 10 '20

COBOL, only part 1 again, gotta catch up during the week-end.

   IDENTIFICATION DIVISION.
   PROGRAM-ID. AOC-2020-10-1.
   AUTHOR ANNA KOSIERADZKA.

   ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
   FILE-CONTROL.
       SELECT INPUTFILE ASSIGN TO "d10.input"
       ORGANIZATION IS LINE SEQUENTIAL.

   DATA DIVISION.
   FILE SECTION.
     FD INPUTFILE
     RECORD IS VARYING IN SIZE FROM 1 to 99
     DEPENDING ON REC-LEN.
     01 INPUTRECORD PIC X(99).

   WORKING-STORAGE SECTION.
     01 FILE-STATUS PIC 9 VALUE 0.
     01 REC-LEN PIC 9(2) COMP.
     01 WS-ARR-LEN PIC 9(2) VALUE 95.
     01 WS-ARRAY OCCURS 11 TO 99 DEPENDING ON WS-ARR-LEN.
       05 WS-ARR-I PIC 9(3).

   LOCAL-STORAGE SECTION.
     01 RESULT UNSIGNED-INT VALUE 0.
     01 I UNSIGNED-INT VALUE 1.
     01 DIFF-1 UNSIGNED-INT VALUE 0. 
     01 DIFF-3 UNSIGNED-INT VALUE 0.
     01 DIFF UNSIGNED-INT VALUE 0.

   PROCEDURE DIVISION.
   001-MAIN.
       OPEN INPUT INPUTFILE.
       MOVE 0 TO WS-ARR-I(1).
       ADD 1 TO I.
       PERFORM 002-READ UNTIL FILE-STATUS = 1.
       CLOSE INPUTFILE.
       SORT WS-ARRAY ON ASCENDING KEY WS-ARR-I.
       PERFORM 004-SHIFT-ARRAY.
       COMPUTE WS-ARR-I(WS-ARR-LEN) = WS-ARR-I(WS-ARR-LEN - 1) + 3.
       PERFORM 005-USE-ADAPTERS.
       COMPUTE RESULT = DIFF-1 * DIFF-3.
       DISPLAY RESULT.
       STOP RUN.

   002-READ.
        READ INPUTFILE
            AT END MOVE 1 TO FILE-STATUS
            NOT AT END PERFORM 003-PROCESS-RECORD
        END-READ.

   003-PROCESS-RECORD.
       MOVE INPUTRECORD TO WS-ARR-I(I).
       ADD 1 TO I.

   004-SHIFT-ARRAY.
       PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-ARR-LEN - 1
          MOVE WS-ARR-I(I + 1) TO WS-ARR-I(I)
       END-PERFORM.

   005-USE-ADAPTERS.
       PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-ARR-LEN - 1
          COMPUTE DIFF = WS-ARR-I(I + 1) - WS-ARR-I(I)
          IF DIFF = 1 THEN
             ADD 1 TO DIFF-1
          END-IF
          IF DIFF = 3 THEN
             ADD 1 TO DIFF-3
          END-IF
       END-PERFORM.

Matt Ellen-Tsivintzeli • Dec 12 '20

Sorry it's so late, but I'm pretty proud of figuring this out :D Obviously I'm continuing my javascript odyssey. It's pretty long, so I'll just link to the gist.

Fabar • Dec 25 '20

Too late but for the sake of explanation: the DFS algorithms and the Dynamic Programming tehcniques are useful to know but the problem of counting (not enumerating) different paths in an oriented graph can be simply solved in O(n^3) time by these cycles:
for(i = 0 to N)
for(j =0 to N)
for(k = 0 to N)
path[i][j] += path[i][k] * path [k][j]

where path[][] is the matrix mapping any vertex to each other setting "0" if there is no edge between them and "1" if they are connected. The result will come in few seconds. Thanks to this post:
stackoverflow.com/questions/164213...

Thibaut Patel • Dec 10 '20

My JavaScript walkthrough (today was tough but recursion with memoization did the trick!):

Kudos Beluga • Dec 11 '20 • Edited

Part 2 stumped me, and this really helped!

Colin Vella • Dec 10 '20

Thanks for the memoizatino tip! Without caching intermediary results my algorithm was simply stuck. Once I started caching, the computation was almost instantaneous!