AdventOfCode201213_2.cpp

//
//  Kudos to "Hey Programmer" youtube solution https://youtu.be/4_5mluiXF5I
//  main.cpp
//  AdventOfCode201213_2
//
//  Created by Kjell-Olov Högdal on 2020-12-28.
//

#include <iostream>
#include <sstream>
#include <vector>

extern char const* pExample;
extern char const* pExample2;
extern char const* pData;

using Count = std::uint64_t;
using Offset = unsigned int;
using TimeStamp = std::uint64_t;
using Result = TimeStamp;
using BusId = Offset;
struct Bus {BusId id; bool in_operation;};
using BusSchedule = std::vector<Bus>;

// Transform shuttle service into rack and pinions system :)

struct Pinion {
    Count tooth_count; // count of circumface teeth
    Offset offset; // offset of the zero tooth
};
using Pinions = std::vector<Pinion>;
struct RackAndPinions {
    Count rack_length;
    Pinions pinions;
};

RackAndPinions rack_and_pinions(BusSchedule const& bus_schedule) {
    RackAndPinions result;
    for (unsigned int i = 0; i<bus_schedule.size();++i) {
        if (bus_schedule[i].in_operation) {
            result.pinions.push_back({bus_schedule[i].id,i});
        }
    }
    return result;
}

Count rack_traversal(RackAndPinions const& raps) {
    std::cout << "\nrack_traversal";
    Count result {1}; // Unit (no operation) for multiplication :)
    // Ok, lets keep our reasoning on the tracks! ;)
    Pinions const& pinions = raps.pinions;
    // 0: To put pinion_0 at its zero position is trivial
    // 1: To traverse the rack so pinion_0 always stops at the same position
    //    we need to step with pinion_0 tooth count.
    //    This is the same as saying k*delta + offset_1 = l*tooth_count_1
    //    k and l some integer.
    // 2: To find the position where pinion 2 reaches its offset position
    //    we now need to step so that both pinion 0 and 1 stops at their
    //    required positions.
    //    This means we need to step in size of the product of pinion 0,1 tooth counts.
    
    // We can consolidate this to a single loop?
    Count delta = pinions[0].tooth_count;
    Count position = 0;
    for (int i = 1;i<pinions.size();++i) {
        std::cout << "\n(" << position << " + " << pinions[i].offset << ") % " << pinions[i].tooth_count << " = ";
        std::cout << (position + pinions[i].offset) % pinions[i].tooth_count;
        while ((position + pinions[i].offset) % pinions[i].tooth_count != 0) {
            position += delta;
            std::cout << "\n(" << position << " + " << pinions[i].offset << ") % " << pinions[i].tooth_count << " = ";
            std::cout << (position + pinions[i].offset) % pinions[i].tooth_count;
        }
        delta *= pinions[i].tooth_count;
    }
    // Check result
    std::cout << "\n\n<Check>";
    for (auto const& pinion : pinions) {
        std::cout << "\n(" << position << " + " << pinion.offset << ") % " << pinion.tooth_count << " = ";
        std::cout << (position + pinion.offset) % pinion.tooth_count;
    }
    result = position;
    return result;
}

int main(int argc, const char * argv[]) {
    TimeStamp arrive_time;
    BusSchedule bus_schedule;
    std::basic_istringstream<char> in {pData};
    in >> arrive_time;
    std::string sBusList;
    in >> sBusList;
    std::basic_istringstream<char> busses{sBusList};
    std::string sBusId;
    while (std::getline(busses, sBusId, ',')) {
        std::cout << "\nBusId:" << sBusId;
        if (sBusId == "x") {
            bus_schedule.push_back({std::numeric_limits<BusId>::max(),false});
        }
        else {
            BusId bus_id = std::stoi(sBusId);
            bus_schedule.push_back({bus_id,true});
        }
    }
    // The puzzle is now to determine when the following happens:
    // Bus at index 0 in the schedule departs
    // Bus at index 0+1 departs one minute later
    // ...
    // Bus at index 0+i departs i minutes later
    
    // I want to transform this problem into one of one rack and pinions :)
    // a) Each bus is modelled as a pinion with the number of teeth being the Bus ID (the roundtrip time in minutes)
    // b) Each pinion has its "zero tooth" marked (modelling the bus departure time)
    // c) The shuttle service now becomes a "rack and pinion system" where each pinion interacts with the same
    //    rack rail (they all simultaneously revolve one tooth for each tooth on the rack rail)
    // d) We now what to now how many teeth we need to move the rack rail so that:
    // 0) Pinion with index 0 has its zero-tooth at a tooth on the rack rail (bus 0 departs at this time)
    // 1) gear with index 1 is one tooth off until it will engange the rack rail (bus 1 departs in one minute)
    // ...
    // i) Gear with index n is n teeth off until it will engage the rack rail (bus i departs in n minutes)
    
    auto raps = rack_and_pinions(bus_schedule);
    auto result = rack_traversal(raps);
    std::cout << "\n\nResult part 2 = " << result;
    std::cout << "\n\nBye";
    return 0;
}

char const* pExample = R"(0000000
7,13,x,x,59,x,31,19)";
char const* pExample2 = R"(000000
17,x,13,19)";
char const* pData = R"(1000303
41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,541,x,x,x,x,x,x,x,23,x,x,x,x,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,983,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,19)";