אתגר תכנות: הנמלה של לנגטון

אתגר תכנות
#1

הנמלה של לנגטון הוא תיאור של עולם דו מימדי בו נמלה מטיילת על רשת אין סופית של משבצות. כל המשבצות מתחילות בצבע לבן. הנמלה מתחילה בנקודה שנקרא לה (0,0) ומטיילת לפי הכללים הבאים:

  1. כשהנמלה מגיעה למשבצת לבנה היא מסתובבת 90 מעלות ימינה, משנה את צבע המשבצת לשחור ומתקדמת צעד אחד.

  2. כשהנמלה מגיעה למשבצת שחורה היא מסתובבת 90 מעלות שמאלה, משנה את צבע המשבצת ללבן ומתקדמת צעד אחד.

התמונה הבאה ממחישה את 200 הצעדים הראשונים של הנמלה:
LangtonsAntAnimated

  1. כתבו תוכנית מחשב (בכל שפה) באמצעותה ספרו כמה משבצות שחורות בלוח אחרי 100,000 צעדים של הנמלה.

  2. כתבו עמוד Web בו אפשר לראות את תנועת הנמלה כמו בתמונה המצורפת.

את התוכניות שתכתבו מוזמנים לפרסם כאן כתגובות.

לייק 1
#2

פיתרון לדוגמא בשפת רובי - בינתיים בלי הדפסת המטריצה:

require 'matrix'
require 'pp'

class Game
  attr_accessor :grid, :direction, :position

  def initialize
    @grid = Hash.new :white
    @direction = Vector[1, 0]
    @position  = Vector[0, 0]
  end

  def step
    case grid[position]
    when :white
      turn_right
      paint(:black)

    when :black
      turn_left
      paint(:white)
    end

    self.position += direction
  end

  def paint(color)
    grid[position] = color
  end

  def turn_right
    self.direction = case direction
                     when Vector[1, 0]
                       Vector[0, 1]
                     when Vector[0, 1]
                       Vector[-1, 0]
                     when Vector[-1, 0]
                       Vector[0, -1]
                     when Vector[0, -1]
                       Vector[1, 0]
                     end
  end

  def turn_left
    self.direction = case direction
                     when Vector[1, 0]
                       Vector[0, -1]
                     when Vector[0, -1]
                       Vector[-1, 0]
                     when Vector[-1, 0]
                       Vector[0, 1]
                     when Vector[0, 1]
                       Vector[1, 0]
                     end
  end
end

g = Game.new
100_000.times { g.step }
puts g.grid.select {|k, v| v == :black }.count
#3

עוד גירסא הפעם בשפת אליקסיר (וכוללת גם הדפסה של הלוח בסוף).

defmodule Game do
  defstruct matrix: %{}, pos: {0, 0}, head: { 1, 0 }
end

defmodule Day22 do
  @directions [{1, 0}, {0, 1}, {-1, 0}, {0, -1}]

  def next("#"), do: "."
  def next("."), do: "#"
  def next(nil), do: "#"

  def pp(game, size) do
    matrix = game.matrix
    pos = game.pos

    for i <- 0..size-1 do
      for j <- 0..size-1 do
        val = Map.get(matrix, { i - div(size, 2), j - div(size, 2) }) 
        if val do
          if pos == { i - div(size, 2), j - div(size, 2) } do
            "[#{val}]"
          else
            " #{val} "
          end
        else
          if pos == { i - div(size, 2), j - div(size, 2) } do
            "[.]"
          else
            " . "
          end
        end
      end
      |> Enum.join("")
    end
    |> Enum.join("\n")
  end

  def flip(matrix, { row, col }) do
    { _, next } = matrix
                  |> Map.get_and_update(
                    { row, col },
                    fn current_value -> { current_value, next(current_value) }
                    end
                  )
    next
  end

  def right(direction) do
    idx = Enum.find_index(@directions, fn x -> x == direction end)
    Enum.at(@directions, rem(idx + 1, length(@directions)))
  end

  def left(direction) do
    idx = Enum.find_index(@directions, fn x -> x == direction end)
    Enum.at(@directions, rem(idx - 1, length(@directions)))
  end

  def move({ dr, dc }, { row, col }), do: { row + dr, col + dc }

  def step(game) do    
    next_direction = case Map.get(game.matrix, game.pos, ".") do
      "." -> left(game.head)
      "#" -> right(game.head)
    end

    Map.merge(
      game,
      %{
        head: next_direction,
        matrix: flip(game.matrix, game.pos),
        pos: move(next_direction, game.pos)
      }
    )
  end

  def play(game, 0) do
    game
  end

  def play(game, n) do
    play(step(game), n - 1)
  end


  def main do
    iterations = System.argv() |> Enum.at(0) |> String.to_integer
    game = %Game{}

    s1 = play(game, iterations)

    s1
    |> pp(20)
    |> IO.puts

    Enum.count(s1.matrix, fn {_, v} -> v == "#" end)
    |> IO.puts
  end
end

Day22.main

וככה זה נראה כשמריצים:

localhost:aoc2017 ynonperek$ elixir day22_b.elxrs 100000
 #  #  .  .  #  .  .  .  .  .  .  #  .  .  #  .  .  #  .  . 
 #  .  #  #  .  .  .  .  .  .  .  #  .  .  .  #  .  .  #  . 
 .  #  #  #  #  #  #  #  #  .  #  .  .  .  .  #  .  .  #  . 
 #  .  #  .  #  #  .  #  #  .  .  .  .  #  .  #  .  #  .  # 
 .  .  .  .  #  .  .  .  #  .  #  #  .  .  .  #  #  .  .  # 
 .  #  .  .  #  #  #  #  .  .  .  #  .  .  #  .  .  .  #  # 
 .  .  #  #  .  #  #  #  #  #  .  .  #  .  #  #  #  #  .  . 
 .  .  .  #  .  #  .  .  #  #  .  #  #  #  #  #  .  #  #  . 
 #  .  #  .  .  .  .  .  #  #  #  #  #  .  #  .  #  #  #  # 
 .  .  .  #  .  #  .  #  #  .  #  .  #  #  .  #  #  #  #  # 
 .  #  #  #  .  #  #  #  .  #  #  .  #  #  .  .  .  #  #  . 
 #  #  #  #  #  #  #  #  #  .  .  #  #  .  .  #  #  #  #  . 
 #  .  .  #  .  #  #  #  #  #  #  #  #  #  #  #  .  .  #  # 
 #  #  #  .  .  .  .  .  .  .  #  #  .  .  .  #  .  #  #  . 
 #  #  .  .  .  .  .  .  #  #  .  #  .  #  .  #  #  #  .  # 
 #  .  #  #  #  #  #  .  .  #  #  .  .  #  #  .  #  .  #  # 
 .  .  .  .  .  .  #  .  .  #  #  #  .  #  .  .  #  .  .  . 
 #  #  .  #  .  .  #  #  .  #  #  #  #  .  #  .  #  .  .  # 
 .  .  .  .  #  .  .  #  #  #  .  .  .  #  #  .  #  #  .  . 
 .  #  .  .  .  .  .  #  #  .  .  #  .  .  #  #  #  .  #  # 
11108

הבא בתור בפייתון?

#4

קוד בפייתון :

import numpy as np
from functools import reduce
from collections import defaultdict
from operator import __add__ as add

STEPS = 100_000
plot_threshold = 200

right = np.array([[0,-1],[1,0]])    # vector rotation matrix
left  =  -1*right

white,black = False, True

class Langton_Ant:  

    def __init__(self):
        self._grid = defaultdict(lambda : white)
        self._direction = np.array([1,0])
        self._position = np.array([0,0])
        self._grid[tuple(self._position)]=white
    
    def step(self):                
        if self._grid[tuple(self._position)] is white:
            self.turn(right)        
            self.paint(black)
        else: # is black
            self.turn(left)        
            self.paint(white)
        
        self._position += self._direction                    
        
    def turn(self,turn_direction):
        self._direction = self._direction.dot(turn_direction)  # matrix dot product           
   
    def paint(self,color):
        self._grid[tuple(self._position)] = color    

g = Langton_Ant()
for i in range(STEPS): 
    g.step()
print ("Number of black slots is:",reduce(lambda x,y: x+y, (g._grid[x] for x in g._grid ) ,0))
#5

ועוד תוספת להדפסה אינטראקטיבית של הלוח :
(המשך ישיר של התגובה הקודמת)

import matplotlib.pyplot as plt

# set x,y axis limits 
max_val = max( map(abs, reduce(add, (list(a) for a in g._grid),[]))) + 1

offset = [max_val+1,max_val+1]              #   Ant's starting point

img = np.ones((max_val*2,max_val*2,3))      #   Initialize empty image

#some graphics
plt.ion()
fig = plt.figure('Langton''s Ant')
ax = fig.add_subplot(111)
if max_val < (plot_threshold/8) :
    ax.set_xticks(range(-1*max_val,max_val,1),minor=True)
    ax.set_yticks(range(-1*max_val,max_val,1),minor=True)
    ax.grid(which='minor')        

# plot the image with adjustments for x/y axis flip (top-left / bottom-right)
imgplot = ax.imshow(np.flip(img.swapaxes(0,1),1),extent=[-1*max_val,max_val]*2)

if STEPS < plot_threshold:
    g = Langton_Ant()
    loop_stages = STEPS
else:
    loop_stages = 1
    
for i in range(loop_stages):
    g.step()

    #update whole image
    for tpl in g._grid:
        val=(1-g._grid[tpl])        
        img[tuple(np.array(tpl)-offset)]=[val,val,val]

    #update ant's location
    img[tuple(g._position-offset)]=[1,0,0] 
    imgplot.set_data(np.flip(img.swapaxes(0,1),1))
    
    fig.canvas.draw()

השתמשתי בספריה matplotlib בשביל הגרפיקה
langston_ant

לייק 1
#6

זה הציג אצלך את הלוח באנימציה? כי אצלי על המק הופיע רק המצב הסופי (מה שמוצג בתמונה שצירפת), וגם בשביל לקבל את זה הייתי צריך להוסיף:

plt.show(block=True)

בסוף הקוד

#7

ואגב עוד דבר מוזר- זמני ריצה. העליתי למיליון צעדים כדי שיהיה מעניין:

אליקסיר יצא המהיר ביותר:

 time elixir day22_b.elxrs 1000000
114952

real	0m2.793s
user	0m2.524s
sys	0m0.444s

אחריו רובי:

localhost:aoc2017 ynonperek$ time ruby ~/a.rb 
114952

real	0m9.667s
user	0m7.517s
sys	0m0.518s

ורק בסוף numpy:

localhost:aoc2017 ynonperek$ time python3 ~/a.py
Number of black slots is: 114952

real	0m10.862s
user	0m8.314s
sys	0m0.571s

אולי ההמרה מ numpy.array ל tuple האטה, או אולי משהו אחר. אבל מפתיע (ונחמד) לראות את אליקסיר מגיעה לתוצאה פי 5 יותר מהר

#8

זה מציג באנימציה בלי לשנות כלום, על ווינדוס.
בגלל ש 100,000 צעדים באנימציה זה יקח מלא זמן לעדכן את הלוח, שמתי משתנה סף.

STEPS = 100_000
plot_threshold = 200

כרגע הוא נקבע על 200, אם תשנה את מספר הצעדים לפחות מ 200, או תגדיל את הסף, תקבל אנימציה של שלב שלב. אם זה מעל הסף הוא מציג רק את המצב הסופי.

בנוסף לגבי זמני הריצה - אני מקווה שמדדת ללא הגרפיקה. אני מניח שההמרה ל numpy array וחזרה ל tuple באמת מאטה. אפשר לכתוב את זה בקלות ללא numpy, אבל היה לי יותר נוח להשתמש בקוד במטריצת סיבוב וכפל מטריצות עבור פנייה ימינה או שמאלה, במקום לכתוב case ארוך. :slightly_smiling_face: