203 lines
9.9 KiB
C#
203 lines
9.9 KiB
C#
// #define Day19
|
|
#if Day19
|
|
using System.Collections.Immutable;
|
|
using AoC2021;
|
|
|
|
// this code is ugly and not performant. could be made more performant but already spent way too much time on day19
|
|
|
|
var textSplitByScanner = File.ReadAllText("day19/input")
|
|
.Split("\n\n")
|
|
.ToList();
|
|
|
|
var scanners = textSplitByScanner
|
|
.Select(t => t.Split("\n", StringSplitOptions.RemoveEmptyEntries)
|
|
.Skip(1)
|
|
.Select(l => l.Split(","))
|
|
.Select(l => new Point() {x=int.Parse(l[0]), y=int.Parse(l[1]), z=int.Parse(l[2])})
|
|
.ToList()
|
|
).ToList();
|
|
|
|
|
|
int numberOfSameBeacons = 11;
|
|
|
|
var curBeacons = scanners[0].ToHashSet();
|
|
|
|
scanners.RemoveAt(0);
|
|
|
|
List<Point> scannerLocations = new List<Point>() {new Point(){x=0, y=0, z=0}};
|
|
int totalFound = 1;
|
|
while (scanners.Count > 0) {
|
|
var curScannerBeacons = curBeacons.ToDictionary(p => p, p => GetVectors(p, curBeacons));
|
|
|
|
int pos = -1;
|
|
List<Point> beaconsFound = null;
|
|
Point fromFirst = null;
|
|
Point fromFound = null;
|
|
for (int i = 0; i < scanners.Count; i++) {
|
|
foreach (var curSecondBeacons in GetOrientations(scanners[i])) {
|
|
var curSecondBeaconsAsList = curSecondBeacons.ToList();
|
|
var curSecondBeaconsAsDict = curSecondBeaconsAsList.ToDictionary(p => p, p => GetVectors(p, curSecondBeaconsAsList));
|
|
|
|
foreach (var firstScannerBeaconsKey in curScannerBeacons.Keys) {
|
|
var firstVectors = ImmutableHashSet.CreateRange(curScannerBeacons[firstScannerBeaconsKey]);
|
|
foreach (var secondScannerBeaconsKey in curSecondBeaconsAsDict.Keys) {
|
|
var secondVectors = ImmutableHashSet.CreateRange(curSecondBeaconsAsDict[secondScannerBeaconsKey]);
|
|
var intersection = firstVectors.Intersect(secondVectors);
|
|
if (intersection.Count >= numberOfSameBeacons) {
|
|
pos = i;
|
|
beaconsFound = curSecondBeaconsAsList;
|
|
fromFirst = firstScannerBeaconsKey;
|
|
fromFound = secondScannerBeaconsKey;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (pos >= 0) {
|
|
break;
|
|
}
|
|
}
|
|
if (pos >= 0) {
|
|
break;
|
|
}
|
|
}
|
|
if (pos >= 0) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
var transformVector = GetVector(fromFound, fromFirst);
|
|
beaconsFound.Select(b => GetVector(b, transformVector)).ForEachAsList(b => curBeacons.Add(b));
|
|
scanners.RemoveAt(pos);
|
|
|
|
scannerLocations.Add(transformVector);
|
|
totalFound++;
|
|
Console.WriteLine($"Total Found: {totalFound}");
|
|
}
|
|
|
|
scannerLocations.ForEach(Console.WriteLine);
|
|
Console.WriteLine(curBeacons.Count);
|
|
|
|
List<long> man = new List<long>();
|
|
for (int i = 0; i < scannerLocations.Count; i++) {
|
|
for (int j = 0; j < scannerLocations.Count; j++) {
|
|
var dist = GetVector(scannerLocations[i],scannerLocations[j]);
|
|
Console.WriteLine(dist);
|
|
man.Add(Math.Abs(dist.x) + Math.Abs(dist.y) + Math.Abs(dist.z));
|
|
Console.WriteLine(Math.Abs(dist.x) + Math.Abs(dist.y) + Math.Abs(dist.z));
|
|
}
|
|
}
|
|
|
|
Console.WriteLine(man.Max());
|
|
|
|
|
|
HashSet<Point> GetVectors(Point cur, IEnumerable<Point> otherPoints) {
|
|
return otherPoints.Where(p => !cur.Equals(p)).Select(p => GetVector(p, cur)).ToHashSet();
|
|
}
|
|
|
|
|
|
Point GetVector(Point a, Point b) => new Point() {x= a.x - b.x, y=a.y - b.y, z = a.z - b.z};
|
|
|
|
IEnumerable<IEnumerable<Point>> GetOrientations(List<Point> beacons) {
|
|
// Something was wrong with trying the 24 possible combinations...
|
|
// // there are some duplicates
|
|
// // x positive rotate around x
|
|
// yield return beacons.Select(b => new Point() {x = b.x, y = b.y, z = b.z});
|
|
// yield return beacons.Select(b => new Point() {x = b.x, y = b.z, z = -b.y});
|
|
// yield return beacons.Select(b => new Point() {x = b.x, y = -b.y, z = -b.z});
|
|
// yield return beacons.Select(b => new Point() {x = b.x, y = -b.z, z = b.y});
|
|
//
|
|
// // x negative rotate around x
|
|
// yield return beacons.Select(b => new Point() {x = -b.x, y = b.y, z = b.z});
|
|
// yield return beacons.Select(b => new Point() {x = -b.x, y = b.z, z = -b.y});
|
|
// yield return beacons.Select(b => new Point() {x = -b.x, y = -b.y, z = -b.z});
|
|
// yield return beacons.Select(b => new Point() {x = -b.x, y = -b.z, z = b.y});
|
|
//
|
|
// // y positive rotate around y
|
|
// yield return beacons.Select(b => new Point() {x = b.x, y = b.y, z = b.z});
|
|
// yield return beacons.Select(b => new Point() {x = -b.z, y = b.y, z = b.x});
|
|
// yield return beacons.Select(b => new Point() {x = -b.x, y = b.y, z = -b.z});
|
|
// yield return beacons.Select(b => new Point() {x = b.z, y = b.y, z = -b.x});
|
|
//
|
|
// // y positive rotate around y
|
|
// yield return beacons.Select(b => new Point() {x = b.x, y = -b.y, z = b.z});
|
|
// yield return beacons.Select(b => new Point() {x = -b.z, y = -b.y, z = b.x});
|
|
// yield return beacons.Select(b => new Point() {x = -b.x, y = -b.y, z = -b.z});
|
|
// yield return beacons.Select(b => new Point() {x = b.z, y = -b.y, z = -b.x});
|
|
//
|
|
// // rotate around z positive
|
|
// yield return beacons.Select(b => new Point() {x = b.x, y = b.y, z = b.z});
|
|
// yield return beacons.Select(b => new Point() {x = b.y, y = -b.x, z = b.z});
|
|
// yield return beacons.Select(b => new Point() {x = -b.x, y = -b.y, z = b.z});
|
|
// yield return beacons.Select(b => new Point() {x = -b.y, y = b.x, z = b.z});
|
|
//
|
|
// // rotate around z negative
|
|
// yield return beacons.Select(b => new Point() {x = b.x, y = b.y, z = -b.z});
|
|
// yield return beacons.Select(b => new Point() {x = b.y, y = -b.x, z = -b.z});
|
|
// yield return beacons.Select(b => new Point() {x = -b.x, y = -b.y, z = -b.z});
|
|
// yield return beacons.Select(b => new Point() {x = -b.y, y = b.x, z = -b.z});
|
|
|
|
// try all combinations, even though some are not correct.
|
|
yield return beacons.Select(b => new Point() {x = b.x, y = b.y, z = b.z});
|
|
yield return beacons.Select(b => new Point() {x = b.x, y = b.z, z = b.y});
|
|
yield return beacons.Select(b => new Point() {x = b.y, y = b.x, z = b.z});
|
|
yield return beacons.Select(b => new Point() {x = b.y, y = b.z, z = b.x});
|
|
yield return beacons.Select(b => new Point() {x = b.z, y = b.x, z = b.y});
|
|
yield return beacons.Select(b => new Point() {x = b.z, y = b.y, z = b.x});
|
|
|
|
yield return beacons.Select(b => new Point() {x = -b.x, y = b.y, z = b.z});
|
|
yield return beacons.Select(b => new Point() {x = -b.x, y = b.z, z = b.y});
|
|
yield return beacons.Select(b => new Point() {x = -b.y, y = b.x, z = b.z});
|
|
yield return beacons.Select(b => new Point() {x = -b.y, y = b.z, z = b.x});
|
|
yield return beacons.Select(b => new Point() {x = -b.z, y = b.x, z = b.y});
|
|
yield return beacons.Select(b => new Point() {x = -b.z, y = b.y, z = b.x});
|
|
|
|
yield return beacons.Select(b => new Point() {x = b.x, y = -b.y, z = b.z});
|
|
yield return beacons.Select(b => new Point() {x = b.x, y = -b.z, z = b.y});
|
|
yield return beacons.Select(b => new Point() {x = b.y, y = -b.x, z = b.z});
|
|
yield return beacons.Select(b => new Point() {x = b.y, y = -b.z, z = b.x});
|
|
yield return beacons.Select(b => new Point() {x = b.z, y = -b.x, z = b.y});
|
|
yield return beacons.Select(b => new Point() {x = b.z, y = -b.y, z = b.x});
|
|
|
|
yield return beacons.Select(b => new Point() {x = -b.x, y = -b.y, z = b.z});
|
|
yield return beacons.Select(b => new Point() {x = -b.x, y = -b.z, z = b.y});
|
|
yield return beacons.Select(b => new Point() {x = -b.y, y = -b.x, z = b.z});
|
|
yield return beacons.Select(b => new Point() {x = -b.y, y = -b.z, z = b.x});
|
|
yield return beacons.Select(b => new Point() {x = -b.z, y = -b.x, z = b.y});
|
|
yield return beacons.Select(b => new Point() {x = -b.z, y = -b.y, z = b.x});
|
|
|
|
yield return beacons.Select(b => new Point() {x = b.x, y = b.y, z = -b.z});
|
|
yield return beacons.Select(b => new Point() {x = b.x, y = b.z, z = -b.y});
|
|
yield return beacons.Select(b => new Point() {x = b.y, y = b.x, z = -b.z});
|
|
yield return beacons.Select(b => new Point() {x = b.y, y = b.z, z = -b.x});
|
|
yield return beacons.Select(b => new Point() {x = b.z, y = b.x, z = -b.y});
|
|
yield return beacons.Select(b => new Point() {x = b.z, y = b.y, z = -b.x});
|
|
|
|
yield return beacons.Select(b => new Point() {x = -b.x, y = b.y, z = -b.z});
|
|
yield return beacons.Select(b => new Point() {x = -b.x, y = b.z, z = -b.y});
|
|
yield return beacons.Select(b => new Point() {x = -b.y, y = b.x, z = -b.z});
|
|
yield return beacons.Select(b => new Point() {x = -b.y, y = b.z, z = -b.x});
|
|
yield return beacons.Select(b => new Point() {x = -b.z, y = b.x, z = -b.y});
|
|
yield return beacons.Select(b => new Point() {x = -b.z, y = b.y, z = -b.x});
|
|
|
|
yield return beacons.Select(b => new Point() {x = b.x, y = -b.y, z = -b.z});
|
|
yield return beacons.Select(b => new Point() {x = b.x, y = -b.z, z = -b.y});
|
|
yield return beacons.Select(b => new Point() {x = b.y, y = -b.x, z = -b.z});
|
|
yield return beacons.Select(b => new Point() {x = b.y, y = -b.z, z = -b.x});
|
|
yield return beacons.Select(b => new Point() {x = b.z, y = -b.x, z = -b.y});
|
|
yield return beacons.Select(b => new Point() {x = b.z, y = -b.y, z = -b.x});
|
|
|
|
yield return beacons.Select(b => new Point() {x = -b.x, y = -b.y, z = -b.z});
|
|
yield return beacons.Select(b => new Point() {x = -b.x, y = -b.z, z = -b.y});
|
|
yield return beacons.Select(b => new Point() {x = -b.y, y = -b.x, z = -b.z});
|
|
yield return beacons.Select(b => new Point() {x = -b.y, y = -b.z, z = -b.x});
|
|
yield return beacons.Select(b => new Point() {x = -b.z, y = -b.x, z = -b.y});
|
|
yield return beacons.Select(b => new Point() {x = -b.z, y = -b.y, z = -b.x});
|
|
|
|
}
|
|
|
|
record Point {
|
|
public int x { get; set; }
|
|
public int y { get; set; }
|
|
public int z { get; set; }
|
|
}
|
|
#endif |