ICFPC 2012 submission

icfpc2012.ls

time_start = process.hrtime!

String::replaceAt = (idx, c) ->
  @substr(0, idx) + c + @substr(idx + c.length)

PF = require \pathfinding
fs = require \fs
read-map = -> 
  arr = fs.readFileSync it, \ascii |> (.split \\n)
  idx = 0
  find (-> idx++; it is ''), arr
  game-state.water = 0
  game-state.waterproof = 10
  game-state.flooding = 0
  if arr.length > idx
    raw-opts = arr.slice idx
    handle-opt = ->
      [opt, val] = it.split ' '
      val = parseInt val, 10
      switch opt | \Water => game-state.water = val
                 | \Flooding => game-state.flooding = val
                 | \Waterproof => game-state.waterproof = val
    each handle-opt, raw-opts
  #it.slice 0, idx
  res =
    map: arr.slice 0, idx - 1
game-state = new Object!

game-state.get-cell = (x, y) -> @map[@height - y][x - 1]
game-state.update-cell = (x, y, c) ->
  str = @map[@height - y]
  @map[@height - y] = str.replaceAt x - 1, c

game-state.init-map = ->
  @height = @map.length
  @width = map (.length), @map |> maximum
  @rocks = new Array!
  @walls = new Array!
  @earth = new Array!
  @lambdas = new Array!
  @lambdas-next-gen = new Array!
  @lambdas-generation = 0
  @robot = new Object!
  @robot-old = new Object!
  @lift = new Object!
  @turn = 0
  @score = 0
  @steps-in-water = 0
  for x from 1 to @width
    for y from 1 to @height
      switch @get-cell x, y | \\ => @lambdas.push x: x, y: y
                            | \# => @walls.push   x: x, y: y
                            | \* => @rocks.push   x: x, y: y
                            | \L => @lift =       x: x, y: y
                            | \R => @robot =      x: x, y: y
                            | \. => @earth.push   x: x, y: y

_map = read-map \/dev/stdin
game-state.map = _map.map
game-state.init-map!

game-state.is-rock = (x, y) -> @get-cell(x, y) is \*
game-state.is-wall = (x, y) -> @get-cell(x, y) is \#
game-state.is-earth = (x, y) -> @get-cell(x, y) is \.
game-state.is-lambda = (x, y) -> @get-cell(x, y) is \\
game-state.is-empty = (x, y) -> @get-cell(x, y) is ' '
game-state.not-passable = (x, y) -> cell = @get-cell(x, y); cell is '#' or cell is '*'

check-rock = (rock) ->
  if game-state.robot.x is rock.x and game-state.robot.y is rock.y and
     game-state.is-empty rock.x + 1, rock.y and game-state.robot-old.x is rock.x - 1
    return rock: rock, action: \pushed-right
  if game-state.robot.x is rock.x and game-state.robot.y is rock.y and
     game-state.is-empty rock.x - 1, rock.y and game-state.robot-old.x is rock.x + 1
    return rock: rock, action: \pushed-left
  if game-state.is-empty rock.x, rock.y - 1
    return rock: rock, action: \fall
  if (game-state.is-rock rock.x, rock.y - 1) and
     (game-state.is-empty rock.x + 1, rock.y) and
     (game-state.is-empty rock.x + 1, rock.y - 1)
    return rock: rock, action: \fall-right
  if (game-state.is-rock rock.x, rock.y - 1) and
     ((!game-state.is-empty rock.x + 1, rock.y) or
      (!game-state.is-empty rock.x + 1, rock.y - 1)) and
     (game-state.is-empty rock.x - 1, rock.y) and (game-state.is-empty rock.x - 1, rock.y - 1)
    return rock: rock, action: \fall-left
  if (game-state.is-lambda rock.x, rock.y - 1) and
     (game-state.is-empty rock.x + 1, rock.y) and
     (game-state.is-empty rock.x + 1, rock.y - 1)
    return rock: rock, action: \fall-right
  return undefined

process-actions = (action) ->
  {rock, action} = action
  switch action
    when \fall
      game-state.update-cell rock.x, rock.y, ' '
      game-state.update-cell rock.x, rock.y - 1, \*
      game-state.grid.setWalkableAt rock.x - 1, rock.y, true
      game-state.grid.setWalkableAt rock.x - 1, rock.y - 1, false
      rock.y = rock.y - 1
    when \fall-left
      game-state.update-cell rock.x, rock.y, ' '
      game-state.update-cell rock.x - 1, rock.y - 1, \*
      game-state.grid.setWalkableAt rock.x - 1, rock.y - 1, true
      game-state.grid.setWalkableAt rock.x - 1 - 1, rock.y - 1 - 1, false
      rock.x = rock.x - 1
      rock.y = rock.y - 1
    when \fall-right
      game-state.update-cell rock.x, rock.y, ' '
      game-state.update-cell rock.x + 1, rock.y - 1, \*
      game-state.grid.setWalkableAt rock.x - 1, rock.y - 1, true
      game-state.grid.setWalkableAt rock.x + 1 - 1, rock.y - 1 - 1, false
      rock.x = rock.x + 1
      rock.y = rock.y - 1
    when \pushed-right
      game-state.update-cell rock.x, rock.y, ' '
      game-state.update-cell rock.x + 1, rock.y, \*
      game-state.grid.setWalkableAt rock.x - 1, rock.y - 1, true
      game-state.grid.setWalkableAt rock.x + 1 - 1, rock.y - 1, false
      rock.x = rock.x + 1
    when \pushed-left
      game-state.update-cell rock.x, rock.y, ' '
      game-state.update-cell rock.x - 1, rock.y, \*
      game-state.grid.setWalkableAt rock.x - 1, rock.y - 1, true
      game-state.grid.setWalkableAt rock.x - 1 - 1, rock.y - 1, false
      rock.x = rock.x - 1

get-element-with-minimum-distance = (elem, arr) ->
  distance = (a, b) -> abs(a.x - b.x) + abs(a.y - b.y)
  compare = (current, next) ->
    if distance(elem, current) > distance(elem, next)
      return next
    else return current
  foldr compare, arr[0], arr

game-state.process-map = ->
  @turn++
  if @flooding > 0
    if @flooding % @turn is 0
      @water++
  if @water > 0
    if @robot.y <= @water
      @steps-in-water++
    else
      @steps-in-water = 0
    if @steps-in-water is @waterproof
      process.stdout.write \A\n
      process.exit 0
  @score--
  actions = map check-rock, @rocks |> filter id
  if actions.length > 0
    #console.log 'processed map, actions: ', actions
    each process-actions, actions
  if @is-rock @robot.x, @robot.y + 1
    @grid.setWalkableAt @robot.x, @robot.y - 1, false

unload-coords = -> [it.x - 1, it.y - 1]

path-to-commands = (path) ->
  res = for i from 0 to path.length - 2
    [_ax, _ay, _bx, _by] = path[i].concat path[i + 1]
    switch | _ax > _bx => 'L'
           | _ax < _bx => 'R'
           | _ay > _by => 'D'
           | _ay < _by => 'U'
  res.join ''

game-state.set-walk = (x, y, status) -> @grid.setWalkableAt x - 1, y - 1, status

take-steps = ->
  commands = ''
  path = undefined

  filter_movements = ->
    r = game-state.robot
    g-s = game-state


    if (g-s.is-rock r.x, r.y + 1) or # rock above
       (g-s.is-rock r.x + 1, r.y and g-s.is-rock r.x + 1, r.y + 1) # rock on rock at right
      g-s.set-walk r.x, r.y - 1, false

    #if (((g-s.is-rock r.x - 1, r.y) and ((g-s.is-rock r.x - 1, r.y - 1) or (g-s.is-lambda r.x - 1, r.y - 1))) or 
    #   ((g-s.is-rock r.x + 1, r.y) and (g-s.is-rock r.x + 1, r.y - 1))) and (g-s.is-empty r.x, r.y - 1)
    #  g-s.set-walk r.x, r.y - 1, false # rock at side, don't go down

    #if (g-s.is-lambda r.x, r.y + 1) and (g-s.is-rock r.x, r.y + 1) and
    #   (g-s.not-passable r.x + 1, r.y + 1) and (g-s.not-passable r.x - 1, r.y + 1)
    #  g-s.set-walk r.x, r.y + 1, false

    func = (rock) ->
      if g-s.is-empty(rock.x - 1, rock.y) and g-s.is-empty(rock.x + 1, rock.y)
        g-s.set-walk rock.x, rock.y, true
      if g-s.is-empty(rock.x + 1, rock.y) and (r.x is rock.x - 1)
        g-s.set-walk rock.x, rock.y, true
      if g-s.is-empty(rock.x - 1, rock.y) and (r.x is rock.x + 1)
        g-s.set-walk rock.x, rock.y, true

    #console.log 'GENERATION: ', g-s.lambdas-generation
    each func, g-s.rocks if g-s.lambdas-generation > 0
    
  setup_pathfinder = (target, final = false, allow_pushing = false) ->
    game-state.lambdas-generation = 1 if allow_pushing
    game-state.grid = new PF.Grid game-state.width, game-state.height
    obstacles = game-state.rocks.concat game-state.walls
    obstacles = obstacles.concat [game-state.lift] unless final
    map (-> x: it.x - 1, y: it.y - 1), obstacles |> each (-> game-state.grid.setWalkableAt it.x, it.y, false)
    finder = new PF.AStarFinder allowDiagonal: false
    _start = unload-coords game-state.robot
    _end = unload-coords target
    filter_movements!
    path := finder.findPath _start[0], _start[1], _end[0], _end[1], game-state.grid
     #if res.length is 0 # manual control, just go somewhere, where empty
     #  g-s = game-state
     #  r = g-s.robot
     #  if g-s.is-empty r.x, r.y + 1
     #    res = [[_start[0], _start[1]], [_start[0], _start[1] + 1]]
    #path := res
  
  get-path-for-lambda = ->
    prev-gen-pos = undefined
    while true
      if game-state.lambdas.length is 0
        return undefined if (prev-gen-pos = game-state.robot) and (game-state.lambdas-generation > 2)
        #console.log 'lambdas', game-state.lambdas
        #console.log 'next-gen', game-state.lambdas-next-gen
        prev-gen-pos = game-state.robot
        game-state.lambdas-generation++
        game-state.lambdas = game-state.lambdas-next-gen
        game-state.lambdas-next-get = new Array!
      target = get-element-with-minimum-distance game-state.robot, game-state.lambdas
      setup_pathfinder get-element-with-minimum-distance game-state.robot, game-state.lambdas
      #console.log game-state.grid.nodes
      #console.log 'get-path-for-lambda', path
      if path.length > 1
        #console.log 'PATH', path
        return path
      else
        #console.log 'PUSHIG'
        game-state.lambdas = reject (-> it.x is target.x and it.y is target.y), game-state.lambdas
        game-state.lambdas-next-gen.push target

  #print-state!
  while game-state.lambdas.length > 0
    #process.stdout.write commands
    path = get-path-for-lambda!
    break unless path
    #commands += path-to-commands [path[0], path[1]]
    #console.log commands
    process.stdout.write path-to-commands [path[0], path[1]]
    game-state.update-cell game-state.robot.x, game-state.robot.y, ' '
    game-state.robot-old = game-state.robot
    game-state.robot = x: path[1][0] + 1, y: path[1][1] + 1
    got_lambda = game-state.is-lambda path[1][0] + 1, path[1][1] + 1
    if got_lambda
      game-state.score += 25
      game-state.lambdas = reject (-> it.x is path[1][0] + 1 and it.y is path[1][1] + 1), game-state.lambdas
      #console.log 'lambdas left: ', game-state.lambdas.length
    game-state.update-cell game-state.robot.x, game-state.robot.y, 'R'
    game-state.process-map!
    #print-state!

  unless game-state.lambdas.length > 0 or game-state.lambdas-next-gen.length > 0
    setup_pathfinder game-state.lift, true
    setup_pathfinder game-state.lift, true, true if path.length is 0
    while path.length > 1
      #console.log path
      setup_pathfinder game-state.lift, true
      #commands += path-to-commands [path[0], path[1]]
      #console.log commands
      process.stdout.write path-to-commands [path[0], path[1]]
      game-state.update-cell game-state.robot.x, game-state.robot.y, ' '
      game-state.robot-old = game-state.robot
      game-state.robot = x: path[1][0] + 1, y: path[1][1] + 1
      game-state.update-cell game-state.robot.x, game-state.robot.y, 'R'
      game-state.process-map!
      #print-state!
      path.shift!

  #commands += \A\n
  #console.log commands
  process.stdout.write \A\n

print-state = ->
#  if 34 < game-state.turn < 38
  console.error "=====\nTurn: #{game-state.turn}, Score: #{game-state.score}\n"
  console.error game-state.map.join \\n

take-steps!
#path-to-commands path |> console.log

time_end = process.hrtime time_start

#console.error "Run time: #{time_end[0] + time_end[1] * (10 ** -8)}"