import math

# Die 5 Zeilen aus dem Rätsel
daten = [
    "011101110001110111011101110111011101110111011101110111011101110",
    "000100010001000101000100010001010101000001000101010100000100010",
    "011101110001110111000100010001010101110111011101110111011101110",
    "000101000001010101000100010001010100010001000100010101010001000",
    "011101110001110111000100010001011101110111011101110111011101110",
]

# Definition der Ziffern im 3x5-Raster
ziffern_muster = {
    "111101101101111": "0",
    "001001001001001": "1",
    "111001111100111": "2",
    "111001111001111": "3",
    "101101111001001": "4",
    "111100111001111": "5",
    "111100111101111": "6",
    "111001001001001": "7",
    "111101111101111": "8",
    "111101111001111": "9",
}


def dekodiere_koordinaten(zeilen):
    breite = len(zeilen[0])  # Korrigiert: Länge der ersten Zeile (63 Zeichen)
    spalte = 0
    ergebnis = ""

    while spalte < breite:
        spalten_werte = [zeile[spalte] for zeile in zeilen]
        if all(wert == "0" for wert in spalten_werte):
            if spalte + 1 < breite and all(
                zeile[spalte + 1] == "0" for zeile in zeilen
            ):
                if not ergebnis.endswith(" "):
                    ergebnis += " "
            spalte += 1
        else:
            block = "".join(zeile[spalte : spalte + 3] for zeile in zeilen)
            ergebnis += ziffern_muster.get(block, "?")
            spalte += 3

    return ergebnis.strip()


def utm_zu_wgs84(zone, easting, northing):
    """Rechnet UTM-Koordinaten (Nordhalbkugel) in Breiten- und Längengrad (WGS84) um."""
    a = 6378137.0
    f = 1 / 298.257223563
    k0 = 0.9996
    e2 = f * (2 - f)
    e_prime2 = e2 / (1 - e2)

    x = easting - 500000.0
    y = northing

    M = y / k0
    mu = M / (a * (1 - e2 / 4 - 3 * e2**2 / 64 - 5 * e2**3 / 256))

    e1 = (1 - math.sqrt(1 - e2)) / (1 + math.sqrt(1 - e2))
    phi1 = (
        mu
        + (3 * e1 / 2 - 27 * e1**3 / 32) * math.sin(2 * mu)
        + (21 * e1**2 / 16 - 55 * e1**4 / 32) * math.sin(4 * mu)
        + (151 * e1**3 / 96) * math.sin(6 * mu)
        + (1097 * e1**4 / 512) * math.sin(8 * mu)
    )

    C1 = e_prime2 * math.cos(phi1) ** 2
    T1 = math.tan(phi1) ** 2
    N1 = a / math.sqrt(1 - e2 * math.sin(phi1) ** 2)
    R1 = a * (1 - e2) / ((1 - e2 * math.sin(phi1) ** 2) ** 1.5)
    D = x / (N1 * k0)

    lat = phi1 - (N1 * math.tan(phi1) / R1) * (
        D**2 / 2
        - (5 + 3 * T1 + 10 * C1 - 4 * C1**2 - 9 * e_prime2) * D**4 / 24
        + (61 + 90 * T1 + 298 * C1 + 45 * T1**2 - 252 * e_prime2 - 3 * C1**2)
        * D**6
        / 720
    )

    lon0 = math.radians((zone - 1) * 6 - 180 + 3)
    lon = (
        lon0
        + (
            D
            - (1 + 2 * T1 + C1) * D**3 / 6
            + (5 - 2 * C1 + 28 * T1 - 3 * C1**2 + 8 * e_prime2 + 24 * T1**2)
            * D**5
            / 120
        )
        / math.cos(phi1)
    )

    return math.degrees(lat), math.degrees(lon)


def formatiere_geocaching(lat, lon):
    """Formatiert Dezimalgrad in N/S GG° MM.MMM' E/W GGG° MM.MMM'."""
    ns = "N" if lat >= 0 else "S"
    ew = "E" if lon >= 0 else "W"

    lat_abs, lon_abs = abs(lat), abs(lon)
    lat_deg, lon_deg = int(lat_abs), int(lon_abs)
    lat_min = (lat_abs - lat_deg) * 60
    lon_min = (lon_abs - lon_deg) * 60

    return f"{ns} {lat_deg:02d}° {lat_min:06.3f}' {ew} {lon_deg:03d}° {lon_min:06.3f}'"


# --- Hauptprogramm ---
rohtext = dekodiere_koordinaten(daten)
teile = rohtext.split()

# Prüfen, ob Zone und die 13-stellige Koordinatenfolge erkannt wurden
if len(teile) == 2 and len(teile[1]) == 13:
    zone = int(teile[0])
    easting = float(teile[1][:6])   # Erste 6 Ziffern = Rechtswert (687770)
    northing = float(teile[1][6:])  # Letzte 7 Ziffern = Hochwert (5339622)

    lat, lon = utm_zu_wgs84(zone, easting, northing)
    gc_format = formatiere_geocaching(lat, lon)

    print(f"UTM-Koordinaten:    {zone}U {int(easting)} {int(northing)}")
    print(f"Dezimalgrad:        {lat:.6f}, {lon:.6f}")
    print(f"Geocaching-Format:  {gc_format}")
    print(f"Google Maps Link:   https://[Log in to view URL]{lat:.6f},{lon:.6f}")
else:
    print(f"Unerwartetes Format erkannt: {rohtext}")