Re: Optimisation

J'ai essayé et ça ne m'a pas fait gagner grand chose. J'ai trouvé par contre une solution efficace.

Au lieu de faire tomber un grain de sable, je regarde toutes les positions accessible depuis le point de départ avec comme règle les même mouvements qu'un pion aux échecs. Je passe de 27 minutes d’exécution à 0.7s.

En groovy ça donne:

import java.time.Duration
import java.time.Instant
import java.util.regex.Pattern
def start = Instant.now()
def sc = new Scanner(new File('input'))
record Point(int x, int y) {}
static Set<Point> readInput(Scanner sc) {
 def coordPattern = Pattern.compile("(\\d+),(\\d+)")
 def rocks = [] as Set<Point>
 while (sc.hasNextLine()) {
 def line = sc.nextLine()
 def matcher = coordPattern.matcher(line)
 Point prev = null
 while (matcher.find()) {
 def current = new Point(
 Integer.parseInt(matcher.group(1)),
 Integer.parseInt(matcher.group(2))
 )
 rocks << current
 if (prev != null) {
 for (def i = Math.min(prev.x(), current.x()); i < Math.max(prev.x(), current.x()); i++) {
 rocks << new Point(i, current.y())
 }
 for (def j = Math.min(prev.y(), current.y()); j < Math.max(prev.y(), current.y()); j++) {
 rocks << new Point(current.x(), j)
 }
 }
 prev = current
 }
 }
 return rocks
}
def rocks = readInput(sc)
def floor = rocks.max { it.y() }.y() + 2
def sand = 0
def newSands = [new Point(500, 0)]
while (!newSands.isEmpty()) {
 def nextSands = [] as Set<Point>
 for (s in newSands) {
 Set<Point> fallen = fall(s)
 .findAll { !rocks.contains(it) }
 .findAll { it.y() < floor }
 nextSands.addAll(fallen)
 }
 rocks.addAll(nextSands)
 sand += nextSands.size()
 newSands = nextSands
}
println(sand)
def duration = Duration.between(start, Instant.now())
println(duration)
static Set<Point> fall(Point sand) {
 return [
 sand,
 new Point(sand.x(), sand.y() + 1),
 new Point(sand.x() - 1, sand.y() + 1),
 new Point(sand.x() + 1, sand.y() + 1)
 ]
}

https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll