{"id":1720,"date":"2024-12-15T13:08:57","date_gmt":"2024-12-15T13:08:57","guid":{"rendered":"https:\/\/code.efi.ohmportal.de\/blog\/?p=1720"},"modified":"2024-12-15T13:13:23","modified_gmt":"2024-12-15T13:13:23","slug":"advent-of-code-2024-2","status":"publish","type":"post","link":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/","title":{"rendered":"Advent of Code 2024"},"content":{"rendered":"\n

Tag 15: Lagerprobleme<\/h3>\n\n\n\n

Am Tag 15 des Adventskalenders f\u00fcr Programmierer<\/a> bestand die Aufgabe darin, das Verhalten eines Amok-laufenden Lagerroboters zu simulieren. Interessant waren vor Allem die Positionen der Kisten im Lager, die der Roboter st\u00e4ndig verschiebt, sofern sie nicht durch eine Wand oder eine S\u00e4ule abgeblockt werden. Dazu war eine Abfolge von 20000 Roboterbewegungen vorgegeben.<\/p>\n\n\n\n

W\u00e4hrend im Teil 1 des R\u00e4tsels die Kisten genau ein Feld des Lagers belegen, besitzen sie im Teil 2 die doppelte Breite, so dass sie beim Verschieben auch versetzt mehrere andere Kisten mitnehmen k\u00f6nnen. Leider war meine L\u00f6sung des 1. Teils f\u00fcr den 2. Teil v\u00f6llig unbrauchbar, so dass ein neuer Ansatz n\u00f6tig wurde: <\/p>\n\n\n\n

Verschiebungen laufen jetzt in zwei Phasen ab. In der ersten Phase wird rekursiv \u00fcberpr\u00fcft, ob die Verschiebung und die sich anschlie\u00dfenden Verschiebungen \u00fcberhaupt m\u00f6glich sind, ohne an einer S\u00e4ule oder einer Wand h\u00e4ngenzubleiben.<\/p>\n\n\n\n

def is_movable(self, pos, dx, dy):
    if pos not in self.map:
        return True
    if self.map[pos] == \"#\":   # Wand
        return False
    char = self.map[pos]
    pos = (pos[0]+dx, pos[1]+dy)
    if dy == 0 or char == \"O\": # Horizontale Verschiebung oder Teil 1
        return self.is_movable(pos, dx, dy)
    else:
        if char == \"[\":
            peer = (pos[0]+1, pos[1])
        else:
            peer = (pos[0]-1, pos[1])
        return self.is_movable(pos, dx, dy) and self.is_movable(peer, dx, dy)<\/pre>\n\n\n\n
Nur bei positivem Ausgang der Pr\u00fcfung wird die eigentliche Verschiebung wiederum rekursiv angesto\u00dfen. Die Laufzeiten f\u00fcr einen Testfall (700 Bewegungen) und das eigentliche R\u00e4tsel sind akzeptabel.<\/p>\n\n\n\n
TEST for DAY 15
Part 1: 10092 (0.0002s)
Part 2: 9021 (0.0002s)
SOLUTION for DAY 15
Part 1: 1398947 (0.0049s)
Part 2: 1397393 (0.0062s)<\/code><\/pre>\n\n\n\n
Tag 15: Lagerprobleme Am Tag 15 des Adventskalenders f\u00fcr Programmierer bestand die Aufgabe darin, das Verhalten eines Amok-laufenden Lagerroboters zu simulieren. Interessant waren vor Allem die Positionen der Kisten im Lager, die der Roboter st\u00e4ndig verschiebt, sofern sie nicht durch eine Wand oder eine S\u00e4ule abgeblockt werden. Dazu war eine Abfolge von 20000 Roboterbewegungen vorgegeben. … Advent of Code 2024<\/span> weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":1666,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[11,43],"tags":[42],"class_list":["post-1720","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding","category-python","tag-advent-of-code"],"yoast_head":"\nAdvent of Code 2024 - Code Comments<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/\" \/>\n<meta property=\"og:locale\" content=\"de_DE\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Advent of Code 2024 - Code Comments\" \/>\n<meta property=\"og:description\" content=\"Tag 15: Lagerprobleme Am Tag 15 des Adventskalenders f\u00fcr Programmierer bestand die Aufgabe darin, das Verhalten eines Amok-laufenden Lagerroboters zu simulieren. Interessant waren vor Allem die Positionen der Kisten im Lager, die der Roboter st\u00e4ndig verschiebt, sofern sie nicht durch eine Wand oder eine S\u00e4ule abgeblockt werden. Dazu war eine Abfolge von 20000 Roboterbewegungen vorgegeben. … Advent of Code 2024 weiterlesen\" \/>\n<meta property=\"og:url\" content=\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/\" \/>\n<meta property=\"og:site_name\" content=\"Code Comments\" \/>\n<meta property=\"article:published_time\" content=\"2024-12-15T13:08:57+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-12-15T13:13:23+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1000\" \/>\n\t<meta property=\"og:image:height\" content=\"417\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Oliver Hofmann\" \/>\n<meta name=\"twitter:label1\" content=\"Verfasst von\" \/>\n\t<meta name=\"twitter:data1\" content=\"Oliver Hofmann\" \/>\n\t<meta name=\"twitter:label2\" content=\"Gesch\u00e4tzte Lesezeit\" \/>\n\t<meta name=\"twitter:data2\" content=\"1\u00a0Minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/\"},\"author\":{\"name\":\"Oliver Hofmann\",\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/#\/schema\/person\/cd22585e9c447d5140fab876575fc394\"},\"headline\":\"Advent of Code 2024\",\"datePublished\":\"2024-12-15T13:08:57+00:00\",\"dateModified\":\"2024-12-15T13:13:23+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/\"},\"wordCount\":182,\"commentCount\":0,\"image\":{\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg\",\"keywords\":[\"Advent of Code\"],\"articleSection\":[\"Coding\",\"Python\"],\"inLanguage\":\"de\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/\",\"url\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/\",\"name\":\"Advent of Code 2024 - Code Comments\",\"isPartOf\":{\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg\",\"datePublished\":\"2024-12-15T13:08:57+00:00\",\"dateModified\":\"2024-12-15T13:13:23+00:00\",\"author\":{\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/#\/schema\/person\/cd22585e9c447d5140fab876575fc394\"},\"inLanguage\":\"de\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"de\",\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#primaryimage\",\"url\":\"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg\",\"contentUrl\":\"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg\",\"width\":1000,\"height\":417,\"caption\":\"Advent of Code @ EFI\"},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/#website\",\"url\":\"https:\/\/code.efi.ohmportal.de\/blog\/\",\"name\":\"Code Comments\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/code.efi.ohmportal.de\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"de\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/#\/schema\/person\/cd22585e9c447d5140fab876575fc394\",\"name\":\"Oliver Hofmann\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"de\",\"@id\":\"https:\/\/code.efi.ohmportal.de\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/b0d136459d060e391d2d3cc30a86b2bd4bb87d7358a51931de0a12ddd4f2f2bb?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/b0d136459d060e391d2d3cc30a86b2bd4bb87d7358a51931de0a12ddd4f2f2bb?s=96&d=mm&r=g\",\"caption\":\"Oliver Hofmann\"},\"sameAs\":[\"http:\/\/www.welearn.de\/fakultaet-iw\/personen\/details\/person\/prof-dr-oliver-hofmann\/\"],\"url\":\"https:\/\/code.efi.ohmportal.de\/blog\/author\/hofmanno\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Advent of Code 2024 - Code Comments","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/","og_locale":"de_DE","og_type":"article","og_title":"Advent of Code 2024 - Code Comments","og_description":"Tag 15: Lagerprobleme Am Tag 15 des Adventskalenders f\u00fcr Programmierer bestand die Aufgabe darin, das Verhalten eines Amok-laufenden Lagerroboters zu simulieren. Interessant waren vor Allem die Positionen der Kisten im Lager, die der Roboter st\u00e4ndig verschiebt, sofern sie nicht durch eine Wand oder eine S\u00e4ule abgeblockt werden. Dazu war eine Abfolge von 20000 Roboterbewegungen vorgegeben. … Advent of Code 2024 weiterlesen","og_url":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/","og_site_name":"Code Comments","article_published_time":"2024-12-15T13:08:57+00:00","article_modified_time":"2024-12-15T13:13:23+00:00","og_image":[{"width":1000,"height":417,"url":"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg","type":"image\/jpeg"}],"author":"Oliver Hofmann","twitter_misc":{"Verfasst von":"Oliver Hofmann","Gesch\u00e4tzte Lesezeit":"1\u00a0Minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#article","isPartOf":{"@id":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/"},"author":{"name":"Oliver Hofmann","@id":"https:\/\/code.efi.ohmportal.de\/blog\/#\/schema\/person\/cd22585e9c447d5140fab876575fc394"},"headline":"Advent of Code 2024","datePublished":"2024-12-15T13:08:57+00:00","dateModified":"2024-12-15T13:13:23+00:00","mainEntityOfPage":{"@id":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/"},"wordCount":182,"commentCount":0,"image":{"@id":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#primaryimage"},"thumbnailUrl":"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg","keywords":["Advent of Code"],"articleSection":["Coding","Python"],"inLanguage":"de","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/","url":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/","name":"Advent of Code 2024 - Code Comments","isPartOf":{"@id":"https:\/\/code.efi.ohmportal.de\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#primaryimage"},"image":{"@id":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#primaryimage"},"thumbnailUrl":"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg","datePublished":"2024-12-15T13:08:57+00:00","dateModified":"2024-12-15T13:13:23+00:00","author":{"@id":"https:\/\/code.efi.ohmportal.de\/blog\/#\/schema\/person\/cd22585e9c447d5140fab876575fc394"},"inLanguage":"de","potentialAction":[{"@type":"ReadAction","target":["https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/"]}]},{"@type":"ImageObject","inLanguage":"de","@id":"https:\/\/code.efi.ohmportal.de\/blog\/2024\/12\/advent-of-code-2024-2\/#primaryimage","url":"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg","contentUrl":"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg","width":1000,"height":417,"caption":"Advent of Code @ EFI"},{"@type":"WebSite","@id":"https:\/\/code.efi.ohmportal.de\/blog\/#website","url":"https:\/\/code.efi.ohmportal.de\/blog\/","name":"Code Comments","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/code.efi.ohmportal.de\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"de"},{"@type":"Person","@id":"https:\/\/code.efi.ohmportal.de\/blog\/#\/schema\/person\/cd22585e9c447d5140fab876575fc394","name":"Oliver Hofmann","image":{"@type":"ImageObject","inLanguage":"de","@id":"https:\/\/code.efi.ohmportal.de\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/b0d136459d060e391d2d3cc30a86b2bd4bb87d7358a51931de0a12ddd4f2f2bb?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/b0d136459d060e391d2d3cc30a86b2bd4bb87d7358a51931de0a12ddd4f2f2bb?s=96&d=mm&r=g","caption":"Oliver Hofmann"},"sameAs":["http:\/\/www.welearn.de\/fakultaet-iw\/personen\/details\/person\/prof-dr-oliver-hofmann\/"],"url":"https:\/\/code.efi.ohmportal.de\/blog\/author\/hofmanno\/"}]}},"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/code.efi.ohmportal.de\/blog\/wp-content\/uploads\/2022\/12\/aoC.jpg","jetpack_shortlink":"https:\/\/wp.me\/p8QwJV-rK","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/posts\/1720","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/comments?post=1720"}],"version-history":[{"count":6,"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/posts\/1720\/revisions"}],"predecessor-version":[{"id":1728,"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/posts\/1720\/revisions\/1728"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/media\/1666"}],"wp:attachment":[{"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/media?parent=1720"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/categories?post=1720"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/code.efi.ohmportal.de\/blog\/wp-json\/wp\/v2\/tags?post=1720"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}