Queens/primes tutorial on list processing

1 collaborator

Anthony Dekker (Author)

Tags

lists

Tagged by Anthony Dekker over 10 years ago

tutorials

Tagged by Anthony Dekker over 10 years ago

Visible to everyone | Changeable by the author
Model was written in NetLogo 5.0.3 • Viewed 591 times • Downloaded 46 times • Run 0 times

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.

Explanation

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

Posted over 10 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

;; set up chessboard pattern
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

;; set up chessboard pattern
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.

Anthony Dekker over 10 years ago Fixed typo in "help" 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 10 years ago, by Anthony Dekker Download

This model does not have any ancestors.

This model does not have any descendants.