110 lines
3.9 KiB
Java
110 lines
3.9 KiB
Java
package dev.forstenlechner.aoc;
|
|
|
|
import java.nio.file.Files;
|
|
import java.nio.file.Paths;
|
|
import java.util.Arrays;
|
|
import java.util.Comparator;
|
|
import java.util.List;
|
|
import java.util.stream.IntStream;
|
|
import java.util.stream.Stream;
|
|
|
|
import static java.util.stream.Collectors.toList;
|
|
|
|
public class Day13 {
|
|
|
|
record EarliestBus(long earliest, long bus) {}
|
|
|
|
record BusWithOffset(long bus, long offset) {}
|
|
|
|
record BusAsStringWithOffset(String bus, long offset) {}
|
|
|
|
public static void main(String[] args) throws Exception {
|
|
new Day13().solve();
|
|
}
|
|
|
|
private void solve() throws Exception {
|
|
List<String> lines = Files.lines(Paths.get("day13/input")).collect(toList());
|
|
|
|
part1(lines);
|
|
part2(lines.get(1));
|
|
part2FromFusch(lines.get(1));
|
|
}
|
|
|
|
private void part2(String busLine) {
|
|
String[] busses = busLine.split(",");
|
|
List<BusWithOffset> busWithOffsets = IntStream.range(0, busses.length)
|
|
.mapToObj(offset -> new BusAsStringWithOffset(busses[offset], offset))
|
|
.filter(bus -> !bus.bus().equals("x"))
|
|
.map(bus -> new BusWithOffset(Long.parseLong(bus.bus()), bus.offset()))
|
|
.collect(toList());
|
|
|
|
busWithOffsets.forEach(System.out::println);
|
|
|
|
long bus23 = 23;
|
|
long minBusProduct = bus23 * 647 * 19 * 29 * 37;
|
|
|
|
long count = 1;
|
|
while (true) {
|
|
if (count % 1000 == 0) {
|
|
System.out.println(count);
|
|
}
|
|
long possibleT = minBusProduct * count - bus23;
|
|
if (busWithOffsets.stream().allMatch(bus -> ((possibleT + bus.offset()) % bus.bus()) == 0)) {
|
|
System.out.println(possibleT);
|
|
break;
|
|
}
|
|
count++;
|
|
}
|
|
System.out.println(count);
|
|
}
|
|
|
|
private void part2FromFusch(String busLine) {
|
|
List<BusWithOffset> busWithOffsets = getBussesWithOffset(busLine);
|
|
|
|
long count = 1;
|
|
|
|
long currentNumber = 1;
|
|
long stepWidth = 1;
|
|
for (BusWithOffset busWithOffset : busWithOffsets) {
|
|
while ((currentNumber + busWithOffset.offset) % busWithOffset.bus != 0)
|
|
{
|
|
currentNumber += stepWidth;
|
|
count++;
|
|
}
|
|
|
|
// Found the number that fulfills the requirement.
|
|
// Adapt step width, so all further steps also fulfill this requirement
|
|
// KGV shouldn't be necessary, because input is all primes
|
|
stepWidth *= busWithOffset.bus;
|
|
}
|
|
|
|
System.out.println(count);
|
|
System.out.println(currentNumber);
|
|
}
|
|
|
|
private List<BusWithOffset> getBussesWithOffset(String busLine) {
|
|
String[] busses = busLine.split(",");
|
|
return IntStream.range(0, busses.length)
|
|
.mapToObj(offset -> new BusAsStringWithOffset(busses[offset], offset))
|
|
.filter(bus -> !bus.bus().equals("x"))
|
|
.map(bus -> new BusWithOffset(Long.parseLong(bus.bus()), bus.offset()))
|
|
.collect(toList());
|
|
}
|
|
|
|
|
|
private void part1(List<String> lines) {
|
|
long earliestDeparture = Long.parseLong(lines.get(0));
|
|
Stream<Long> busTimes = Arrays.stream(lines.get(1).split(",")).filter(x -> !x.equals("x")).map(Long::parseLong);
|
|
EarliestBus earliestBus = busTimes.map(t -> earliestDepartureForBus(earliestDeparture, t)).min(Comparator.comparing(EarliestBus::earliest)).orElseThrow();
|
|
System.out.println(earliestBus.bus() * (earliestBus.earliest() - earliestDeparture));
|
|
}
|
|
|
|
private EarliestBus earliestDepartureForBus(long earliestDeparture, long bus) {
|
|
if (earliestDeparture % bus == 0) {
|
|
return new EarliestBus(earliestDeparture, bus);
|
|
}
|
|
|
|
return new EarliestBus((earliestDeparture / bus + 1) * bus, bus);
|
|
}
|
|
}
|