Advent of Code

Naja Du musst halt herausfinden wie man herausfindet wie die Zuordnung von den 10 beobachteten Signalmustern zu den Ziffernwerten ist. Im ersten Teil hatten wir die einfachen Werte und nun eben die ”schweren”. Bei dem Beispiel in der Aufgabe ist ja beispielsweise klar das a→c und b→f gilt, weil wir wissen das "ab" wegen der Länge 2 die Ziffer 1 sein muss, und wir wissen das die Ziffer 1 im Original durch "cf" kodiert wird. Reicht das als Hinweis?

Ja, in jeder Zeile ist die Zuordnung anders: „Worse, the wire/segment connections are mixed up separately for each four-digit display! (All of the digits within a display use the same connections, though.)“

Wobei die Info in meinem Hinweis noch nicht ganz reicht. Wir wissen dadurch das zwei Signale die Ziffer 1 kodieren erst einmal nur a→c/f und b→c/f mit / als ”oder” gelesen. Festnageln kann man das aber wenn man sich die anderen Kodierungen für die Ziffern anschaut wo dort welches Segment vorkommt und wo nicht. Da kann es hilfreich sein sich das mal als Tabelle aufzuschreiben. Also beispielsweise Segmente a-f als Spalten und die Ziffern 0 bis 9 als Zeilen und eine Markierung in den Zellen ob das Segment bei der Ziffer an sein muss oder nicht.

Ich denke ein Stack ist hier die übliche und einfachste Lösung. Der ist dann ja auch praktisch für Teil 2.

Dennis89 Das Pascal-Programm ist im Beitrag vor dem mit den Bildern. Die Eingabe ist ein Array von `TLine`-Records die aus jeweils zwei `TPoint`-Records zusammengesetzt sind, welche die Endpunkte beschreiben:

type
  TPoint = record
    x, y: Integer;
  end;
  TLine = record
    p1, p2: TPoint;
  end;
  TLines = record
    items: array[1..MaxLineCount] of TLine;
    count: Word;
  end;

Und die Bilder werden von dem Programm als PGM-Dateien geschrieben. Der Karte ist einfach ein grosses, 2D-Array wo für jeden Punkt gezählt wird, wie oft der von einer Linie getroffen wird. Da es mehr als 255 Linien in der Eingabe gibt, habe ich da einen 16-Bit-Zähler pro Punkt auf der Karte. Der Code zu Speichern der Karte als Bild ist später dazu gekommen und besteht aus einer Funktion zum ermitteln des maximalen Pixelwerts und einer Prozedur, die ein eine PGM-Datei erstellt:

function GetMaxCount: Word;
var i, j, result: Word;
begin
  result := 0;
  for i := Low(TMapIndex) to High(TMapIndex) do
    for j := Low(TMapIndex) to High(TMapIndex) do
      if ocean[i]^[j] > result then result := ocean[i]^[j];
  GetMaxCount := result;
end;

procedure WritePGM(n: Byte);
type
   TRow = array[TMapIndex] of Byte;
var max: Word;
    filename: String;
    tf: Text;
    f: File;
    i, j, len: Word;
    row: TRow;
begin
  len := High(TMapIndex) - Low(TMapIndex) + 1;
  max := GetMaxCount;
  if max < 256 then
    begin
      Str(n, filename);
      filename := 'day_05_' + filename + '.pgm';
      WriteLn('Saving ', filename, ' ...');

      Assign(tf, filename);
      Rewrite(tf);
      Write(tf, 'P5', #10, len, ' ', len, #10, max, #10);
      Close(tf);

      Assign(f, filename);
      Reset(f, 1);
      Seek(f, FileSize(f));
      for i := Low(TMapIndex) to High(TMapIndex) do
        begin
          Write(i DIV 10, '%', #13);
          for j := Low(TMapIndex) to High(TMapIndex) do
            row[j] := Byte(ocean[i]^[j]);
          BlockWrite(f, row, len);
        end;
      Close(f);
    end
  else
    WriteLn('Max value ', max, ' too large for image file!');
end;

Die Netpbm-Dateiformate eignen sich super um Bilddateien in den simpelsten Programmiersprachen zu erstellen. Das Dateiformat ist ein kleiner Header aus Textzeilen gefolgt von den Pixeldaten. Entweder als Text oder Binär, je nach Unterformat. Es gibt Bitmaps („portable bitmap“, PBM) also wirklich nur Pixel ”an” oder ”aus”, Graustufenbilder („portable gray map“, PGM) mit bis zu 65536 Graustufen, und Farbbilder („portable pixel map“, PPM) mit bis zu 65536 verschiedenen Werten pro RGB-Komponente. Alle jeweils in Binär oder ”plain”, also komplett alles als Text, auch die Pixeldaten. Als erstes steht in der Datei das Unterformat P1 bis P6 das angibt ob es PBM, PGM, oder PPM in Binär oder Text ist. Dann folgt ein optionaler Kommentar der mit "#" beginnt, gefolgt von der Breite und Höhe in Pixeln. Bei PGM und PPM kommt dann noch der grösste Wert der in den Pixeldaten vorkommt. Das zweite Bild, welches das Programm speichert fängt beispielsweise so an:

$ head DAY_05_2.PGM 
P5
1000 1000
6

Danach folgen dann die 1000×1000 Bytes mit Werten zwischen 0 und 6. Also aus Sicht des Programms für Tag 5 einfach die niederwertigen Bytes des 1000×1000 Integer-Array:

$ hd DAY_05_2.PGM | head -n 20
00000000  50 35 0a 31 30 30 30 20  31 30 30 30 0a 36 0a 00  |P5.1000 1000.6..|
00000010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00002720  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 01  |................|
00002730  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00002b10  00 00 00 00 00 00 00 00  01 00 00 00 00 00 00 00  |................|
00002b20  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00002b50  00 00 01 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00002b60  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00002f00  00 01 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00002f10  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00002f30  00 00 00 00 00 00 00 00  00 00 00 01 00 00 00 00  |................|
00002f40  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00003260  00 00 00 00 00 00 01 01  01 01 01 01 01 01 01 01  |................|
00003270  01 01 01 01 01 01 01 01  01 01 01 01 01 01 01 01  |................|

Am Anfang sind nur Punkte die gar nicht oder nur 1 mal getroffen wurden. Sieht man an den Bildern ja ganz gut, das die Ränder eher langweilig sind und sich mehr in der Mitte abspielt. Also suchen wir mal den Maximalwert 6:

$ hd DAY_05_2.PGM | grep -C 3 ' 06 '
000729f0  01 00 02 00 00 00 00 00  00 01 02 00 00 02 00 00  |................|
00072a00  00 02 00 00 00 00 00 00  00 00 01 00 01 00 00 00  |................|
00072a10  00 01 00 01 00 00 00 01  00 01 00 01 00 00 01 01  |................|
00072a20  00 00 01 00 00 00 00 00  01 00 00 06 01 00 00 02  |................|
00072a30  00 00 01 01 01 00 00 01  00 01 01 01 01 00 02 00  |................|
00072a40  02 00 01 00 01 00 00 00  00 00 00 00 00 00 00 00  |................|
00072a50  00 00 00 01 01 01 02 00  00 00 00 00 00 01 00 00  |................|

Da sind im Umfeld dann auch ein paar Punkte zu sehen, die 2 mal getroffen wurden. Und der Maximalwert kommt in der ganzen Datei nur ein mal vor.

Falls man so etwas in einer Programmiersprache machen will, die mit Binärdaten nicht wirklich gut oder nur komplizierter umgehen kann, kann man statt P5 am Anfang P2 ausgeben und die Pixelwerte 1 bis 6 dann einfach als Text in die Datei schreiben, durch beliebige „whitespace“-Zeichen getrennt. Also Leerzeichen und/oder Zeilenenden.

Wenn man Bilddateien ohne zusätzliche Bibliotheken erzeugen will/muss, sind die Netpbm-Formate so ziemlich das einfachste was man machen kann das standardisiert ist und von den meisten Bildverarbeitungen und Konvertierungsprogrammen direkt gelesen werden kann. Und für Messdaten & Co ist es ganz nett, dass man da auch 16-Bit-Werte als Pixel speichern kann, also deutlich mehr als 256 Stufen/Werte abbilden kann. Reduzieren auf 256 Stufen, abbilden von Graustufen auf Falschfarben usw. kann man dann hinterher mit entsprechenden Werkzeugen machen.

Beim heutigen Puzzle bietet es sich auch an Bilder zu speichern. Sogar eine Folge von Bildern, die man hinterher in eine GIF-Animation umwandeln könnte.

Wenn ich das Programm noch einmal überarbeiten/verbessern würde, dann würde ich bei den Liniendaten speichern ob das eine horizontale, vertikale, oder diagonale Linie ist, denn dann kann man schon beim einlesen abbrechen wenn man eine findet die keines davon ist und muss die ganzen Tests nicht beim zeichnen der Linien in den beiden Aufgabenteilen wiederholt machen. Und ich würde bei Teil zwei die Linien von Teil 1 nicht löschen und alles neu zeichnen, sondern für Teil 2 nur die diagonalen Linien über die Linien aus Teil 1 zeichnen um Zeit zu sparen. Und eventuell würde es mich reizen das nicht mit dem 16-Bit protected mode Compiler zu machen, sondern beim real mode zu bleiben und den Speicher für die 1000×1000 Zähler über die EMS- oder XMS-Schnittstelle anzusprechen. Oder das ganze gar in einer Datei auf Platte zu lösen. Deutlich langsamer, würde dafür aber auch in einem PC ohne zusätzlichen Speicher funktionieren. 640 KiB RAM reichen für alles! In einem 16-Bit-DOS-Programm einfach so 2 Megabyte Speicher anzufordern fühlt sich jedenfalls leicht geschummelt an. ?

Dennis89 DIe beiden Teilfragen waren ja in welche Form ich die Eingabe gebracht habe, und wie die Diagramme/Bilder entstanden sind. Und die habe ich beantwortet. ?

An dem Pascal-Programm könnte man sich auch ganz gut für eine Python-Implementierung orientieren. Also mindestens mal was die Datentypen angeht. Also einen Punkt- oder Vektor-Datentyp und einen Typ für die Linie der die beiden Endpunkte zu einem zusammengesetzten Wert zusammenfasst.

Hab's mal überarbeitet und Objekte aus den Records gemacht und alles soweit vorbereitet, dass man die Ozeankarte auch mit anderem Speicher für die Zeilen der Karte implementieren könnte, damit das auch auf Rechnern ohne 286er-Prozessor läuft, also beispielsweise mit EMS-Speicher oder temporäre Datei auf Platte.

program Day05;

const SideLength = 1000; MaxLineCount = 500;

type
  TPoint = object
    x, y: Integer;
    function InitFromText(const text: String): Boolean;
  end;
  TLineOrientation = (Horizontal, Vertical, Diagonal, OtherOrientation);
  TOrientations = Set of TLineOrientation;
  TLine = object
    p1, p2: TPoint;
    orientation: TLineOrientation;
    function InitFromText(const text: String): Boolean;
    function IsHorizontal: Boolean;
    function IsVertical: Boolean;
    function IsDiagonal: Boolean;
    procedure Dump;
  end;
  TLines = object
    items: array[1..MaxLineCount] of TLine;
    count: Word;
    function Load(const filename: String): Boolean;
  end;
  TMapIndex = 0..SideLength - 1;
  TRow = array[TMapIndex] of Word;
  PRow = ^TRow;
  TMap = object
    private
      function GetRow(y: Word): PRow; virtual;
      procedure Clear;

    public
      constructor Init;
      destructor Done; virtual;
      procedure Plot(x, y: Word);
      procedure DrawLine(const line: TLine);
      procedure DrawLines(const lines: TLines;
        const orientations: TOrientations);
      function CountOverlapping: LongInt;
      function GetMaxCount: Word;
      procedure WritePGM(const filename: String);
  end;
  THeapMap = object(TMap)
    private
      rows: array[TMapIndex] of PRow;
      function GetRow(y: Word): PRow; virtual;

    public
      constructor Init;
      destructor Done; virtual;
  end;

  {
  TODO: Implement map object that uses EMS memory instead of allocating
        heap memory for rows.
  }

var
  lines: TLines;
{$IFDEF DPMI}
  ocean: THeapMap;
{$ELSE}
  ocean: TEmsMap;
{$ENDIF}

function TPoint.InitFromText(const text: String): Boolean;
var i: Byte;
    code: Integer;
    result: Boolean;
begin
  result := False;
  i := Pos(',', text);
  if i <> 0 then
    begin
      Val(Copy(text, 1, i - 1), x, code);
      if code = 0 then
        begin
          Val(Copy(text, i + 1, Length(text)), y, code);
          result := code = 0;
        end;
    end;
  InitFromText := result;
end;

function TLine.InitFromText(const text: String): Boolean;
var i: Byte;
    result: Boolean;
begin
  result := False;
  i := Pos(' -> ', text);
  if i <> 0 then
    begin
      result := p1.InitFromText(Copy(text, 1, i - 1));
      if result then
        result := p2.InitFromText(Copy(text, i + 4, Length(text)));
        if IsHorizontal then orientation := Horizontal
        else if IsVertical then orientation := Vertical
        else if IsDiagonal then orientation := Diagonal
        else orientation := OtherOrientation;
    end;
  InitFromText := result;
end;

procedure TLine.Dump;
begin
  Write(p1.x, ',', p1.y, ' -> ', p2.x, ',', p2.y);
end;

function TLine.IsHorizontal: Boolean;
begin
  IsHorizontal := p1.y = p2.y;
end;

function TLine.IsVertical: Boolean;
begin
  IsVertical := p1.x = p2.x;
end;

function TLine.IsDiagonal: Boolean;
begin
  IsDiagonal := abs(p1.x - p2.x) = abs(p1.y - p2.y);
end;

function TLines.Load(const filename: String): Boolean;
var f: Text;
    textLine: String;
    result: Boolean;
begin
  result := True;
  Assign(f, filename);
  Reset(f);
  count := 0;
  while result and not Eof(f) do
    begin
      ReadLn(f, textLine);
      Inc(count);
      with items[count] do
        begin
          result := InitFromText(textLine);
          if result and (orientation = OtherOrientation) then
            begin
              Write('Error: ');
              Dump;
              WriteLn(' neither horizontal, vertical, or diagonal!');
              result := False;
            end;
        end;
    end;
  Close(f);
  Load := result;
end;

constructor TMap.Init;
begin
  Clear;
end;

destructor TMap.Done;
begin
end;

function TMap.GetRow(y: Word): PRow;
begin
end;

procedure TMap.Clear;
var i: Word;
begin
  for i := Low(TMapIndex) to High(TMapIndex) do
    FillChar(GetRow(i)^, SizeOf(TRow), 0);
end;

procedure TMap.Plot(x, y: Word);
begin
  Inc(GetRow(y)^[x]);
end;

procedure TMap.DrawLine(const line: TLine);
var x, y, dx, dy: Integer;
begin
  case line.orientation of
    Horizontal:
      begin
        if line.p1.x < line.p2.x then dx := 1 else dx := -1;
        dy := 0;
      end;
    Vertical:
      begin
        dx := 0;
        if line.p1.y < line.p2.y then dy := 1 else dy := -1;
      end;
    Diagonal:
      begin
        if line.p1.x < line.p2.x then dx := 1 else dx := -1;
        if line.p1.y < line.p2.y then dy := 1 else dy := -1;
      end;
  end;
  x := line.p1.x;
  y := line.p1.y;
  Plot(x, y);
  while (x <> line.p2.x) or (y <> line.p2.y) do
    begin
      Inc(x, dx);
      Inc(y, dy);
      Plot(x, y);
    end;
end;

procedure TMap.DrawLines(const lines: TLines;
  const orientations: TOrientations);
var i: Word;
    line: TLine;
begin
  for i := 1 to lines.count do
    begin
      line := lines.items[i];
      if line.orientation in orientations then DrawLine(line);
    end;
end;

function TMap.CountOverlapping: LongInt;
var i, j: Word;
    row: PRow;
    result: LongInt;
begin
  result := 0;
  for i := Low(TMapIndex) to High(TMapIndex) do
    begin
      row := GetRow(i);
      for j := Low(TMapIndex) to High(TMapIndex) do
        if row^[j] > 1 then Inc(result);
    end;
  CountOverlapping := result;
end;

function TMap.GetMaxCount: Word;
var i, j, result: Word;
    row: PRow;
begin
  result := 0;
  for i := Low(TMapIndex) to High(TMapIndex) do
    begin
      row := GetRow(i);
      for j := Low(TMapIndex) to High(TMapIndex) do
        if row^[j] > result then result := row^[j];
    end;
  GetMaxCount := result;
end;

procedure TMap.WritePGM(const filename: String);
type
   TPixelRow = array[TMapIndex] of Byte;
var len, max: Word;
    tf: Text;
    f: File;
    i, j: Word;
    row: PRow;
    pixelRow: TPixelRow;
begin
  len := High(TMapIndex) - Low(TMapIndex) + 1;
  max := GetMaxCount;
  if max < 256 then
    begin
      WriteLn('Saving ', filename, ' ...');

      Assign(tf, filename);
      Rewrite(tf);
      Write(tf, 'P5', #10, len, ' ', len, #10, max, #10);
      Close(tf);

      Assign(f, filename);
      Reset(f, 1);
      Seek(f, FileSize(f));
      for i := Low(TMapIndex) to High(TMapIndex) do
        begin
          Write(i DIV 10, '%', #13);
          row := GetRow(i);
          for j := Low(TMapIndex) to High(TMapIndex) do
            pixelRow[j] := Byte(row^[j]);
          BlockWrite(f, pixelRow, len);
        end;
      Close(f);
    end
  else
    WriteLn('Max value ', max, ' too large for image file!');
end;

constructor THeapMap.Init;
var i: Word;
begin
  for i := Low(TMapIndex) to High(TMapIndex) do New(rows[i]);
  inherited Init;
end;

destructor THeapMap.Done;
var i: Word;
begin
  for i := Low(TMapIndex) to High(TMapIndex) do Dispose(rows[i]);
  inherited Done;
end;

function THeapMap.GetRow(y: Word): PRow;
begin
  GetRow := rows[y];
end;

begin
  if not lines.Load('input.txt') then
    begin
      WriteLn('Load error!');
      Halt(1);
    end;

  WriteLn('Part 1...');
  ocean.Init;
  ocean.DrawLines(lines, [Horizontal, Vertical]);
  WriteLn('Result: ', ocean.CountOverlapping);
  ocean.WritePGM('day_05_1.pgm');

  WriteLn('Part 2...');
  ocean.DrawLines(lines, [Diagonal]);
  WriteLn('Result: ', ocean.CountOverlapping);
  ocean.WritePGM('day_05_2.pgm');

  ocean.Done;
end.

noisefloor Mit dem Programm bekomme ich für meine Eingedaten auch einen Wert der niedriger ist als das richtige Ergebnis. Es werden nicht alle Linien gezeichnet. Hier mal eine GIF-Animation in der die für meine Eingabedaten fehlenden Linien blinken:

Speichern von 2D-Listen mit Werten bis max. 255 als PGM-Datei:

def save_pgm(filename, data):
    max_value = max(map(max, data))
    if max_value > 255:
        raise ValueError(f"max value {max_value} too large")
    
    with open(filename, "wb") as file:
        file.write(
            f"P5\n{len(data[0])} {len(data)}\n{max_value} ".encode("ascii")
        )
        file.writelines(map(bytes, data))

Ich versuche auch dieses Jahr wieder am Ball zu bleiben. Die ersten drei Tage liessen sich in CBM BASIC V2 auf einem VIC-20 mit 3½ KiB RAM noch gut lösen. ?

Ansonsten habe ich mir auch mal GW-BASIC auf einem XT-Rechner, also Intel 8088 Prozessor mit 4,77 Mhz angeschaut und bin überrascht wie schlecht das gegenüber dem VIC-20 (MOS 6502, etwas unter 1 Mhz) abschneidet. Ja es ist schneller, aber nicht mal doppelt so schnell, obwohl der Prozessor mehr als 4× so hoch getaktet ist, und die Laufwerke deutlich schneller sind. Der Preis vom PC war bei der Einführung astronomisch, selbst wenn man das mit dem Einführungspreis vom ca. 3 Jahre älteren VIC-20 vergleicht (1981, $299). Selbst QBasic ist lahm auf so einem XT und das gab es erst ab 1991. Wirklich schnell wird es erst mit Turbo Pascal. Kein Wunder dass das so beliebt war. Alternative: handgeschriebener Assembler. War ja für DOS-Programmierer auch sehr verbreitet, diese Attitüde das nur Assembler-Programme das wirklich Wahre sind.