Queens/primes tutorial on list processing

Queens/primes tutorial on list processing preview image

1 collaborator

Ahdekker Anthony Dekker (Author)

Tags

lists 

Tagged by Anthony Dekker over 5 years ago

tutorials 

Tagged by Anthony Dekker over 5 years ago

Visible to everyone | Changeable by the author
Model was written in NetLogo 5.0.3 • Viewed 395 times • Downloaded 26 times • Run 0 times
Download the 'Queens/primes tutorial on list processing' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


NETLOGO LISTS EXAMPLE

This example is explained in the tutorial at http://scientificgems.wordpress.com/2013/12/16/list-processing-in-netlogo-a-tutorial/

RUNNING THE EXAMPLE

QUEENS generates a list of solutions to the 8-queens puzzle, and displays the first one. Subsequent button-presses iterate through the list

PRIMES shows a list of primes, with patches 1, 2, 3, starting at the top left.

MODIFICATIONS

The world can be resized, as long as it remains square, and patch (0,0) is at the bottom left. QUEENS becomes slower with larger grids.

Comments and Questions

Explanation

This model is associated with a tutorial at http://scientificgems.wordpress.com/2013/12/16/list-processing-in-netlogo-a-tutorial/

Posted over 5 years ago

Click to Run Model

to-report add-queen [ lst n ]
  ;; NB fput and lput are the same speed in NetLogo 5.0, so need not use fput
  report lput n lst 
end 

to-report threatens [ i j m n ]
  report (j = n) or (i + j = m + n) or (i - j = m - n)
end 

to-report safe [ lst n ]
  ;; Solution lists look like [1 5 8 6 3 7 2 4]. These are row positions.
  ;; Column positions 1..8 are implied
  let m ((length lst) + 1)
  let i 1
  foreach lst [
    if (threatens i ? m n) [ report false ]
    set i (i + 1)
  ]
  report true
end 

to-report queen-solutions [ n num-rows ]
  if-else (n = 0)
    [ report [ [] ] ]
    [ let lst (queen-solutions (n - 1) num-rows )
      let res []
      foreach lst [
        let i 1
        while [i <= num-rows] [
          if (safe ? i) [ set res (lput (add-queen ? i) res) ]
          set i (i + 1)
        ]
      ]
      report res
    ]
end 

to-report all-queen-solutions [ n ]
  report (queen-solutions n n)
end 

globals [
  queens
  scan
]

;; code for QUEENS button

to queens-go
  ;; remove any old turtles
  ask turtles [ die ]
  
  ;; set up chessboard pattern
  ask patches [
    if-else ((pxcor - pycor) mod 2 = 0) [ set pcolor white ] [ set pcolor black ]
  ]
  
  ;; the first time the QUEENS button is pressed, calculate list of all solutions
  if (queens = 0) [
    reset-timer
    set queens (all-queen-solutions world-width)
    type (length queens) print " solutions"
    type timer print " seconds taken"
    set scan 0
  ]
  
  ;; every time the QUEENS button is pressed, display one solution
  ;; increment scan as an index into the list of all solutions
  let q (item scan queens)
  set scan (scan + 1)
  type "solution #" type scan type ": " print q
  if (scan = (length queens)) [ set scan 0 ]
  
  ;; display a solution by placing turtles in the world
  ;; convert coordinates assuming bottom left corner of world is (0,0)
  let i 1
  foreach q [
    crt 1 [
      setxy (i - 1) (world-width - ?)
      set shape "face happy"
      set color orange
      set size 0.8
    ]
    set i (i + 1)
  ]
end 

;; RESET button erases everything

to reset
  clear-all
  reset-ticks
end 

to-report sequence [ m n ]
  let res []
  let i m
  while [i <= n] [
    set res (lput i res)
    set i (i + 1)
  ]
  report res
end 

to-report sieve [ lst maxn ]
  ;; assume lst is not empty and that first element is prime (we will start with 2)
  let fst (first lst)
  if-else (fst * fst > maxn) 
    [ report lst ]
    [ let a (filter [? mod fst > 0] lst)
      let b (sieve a maxn)
      report (fput fst b) ]
end 

to-report latitude [ n ]
  report ((n - 1) mod world-width)
end 

to-report longitude [ n ]
  report ((world-width - 1) - floor ((n - 1) / world-width))
end 

;; code for PRIMES button

to primes-go
  ;; remove any old turtles
  ask turtles [ die ]
  
  ;; set up chessboard pattern
  ask patches [
    if-else ((pxcor - pycor) mod 2 = 0) [ set pcolor 48 ] [ set pcolor 28 ]
  ]
  
  ;; calculate the primes
  let maxn (world-width * world-height)
  let numbers (sequence 2 maxn)
  let primes (sieve numbers maxn)
  type "primes " print primes
  
  ;; place turtles at prime positions
  ;; brackets identify the multi-argument version of foreach
  ;; we illustrate two different ways of using map
  (foreach (map latitude primes) (map [longitude ?] primes) [
    crt 1 [
      setxy ?1 ?2
      set shape "circle"
      set color blue
      set size 0.8
    ]
  ])
end 

There are 2 versions of this model.

Uploaded by When Description Download
Anthony Dekker over 5 years ago Fixed typo in "help" Download this version
Anthony Dekker over 5 years ago Initial upload Download this version

Attached files

File Type Description Last updated
Queens/primes tutorial on list processing.png preview Preview for 'Queens/primes tutorial on list processing' over 5 years ago, by Anthony Dekker Download

This model does not have any ancestors.

This model does not have any descendants.