icfp pc 2018の問題を解く、前準備を勧めている

だいたいタイトルどおりの話です。なおまだ問題全然解いてないです。

ICFP Programming Contest 2018

icfp pc はなんか数日間頑張って最適化とかの問題を解いてスコアを競うやつです。今回のはざっくりいうと3Dプリンタの最適化問題で、指定の座標を塗りつぶしたモデルを作成するためにボットを操るやつです。なおかなり前に終了しています。

モデルのデコーダ

モデル = 指定の座標がどこか示してあるやつ。これのデコーダがないとその後扱える気がしなかったのでとりあえず書いたのだが、冷静になってみるとブラウザでレンダリングして簡単そうなのを選んだほうがよかったかもしれない。
フォーマットは、僕の理解ではこんな感じ。

• 先頭1バイトはサイズrを指定。 r * r * r のサイズの空間でなんかやる
• 座標(x, y, z)に対応した整数として x * r² + y * r + z (r進数的に解釈したやつ)を考える
• 2バイト目以降は座標に対応したビットが立ってるかどうかで判定
  • 2バイト目は [7, 6, 5, 4, 3, 2, 1, 0]
  • 3バイト目は [15, 14, 13, 12, 11, 10, 9, 8]

いまの版ではこんな感じです。最初goで書いてたんだけどrubyのが楽だった。bit操作になれてなさすぎてbitを真面目に扱うより to_s(2) して文字列操作したほうが楽であることが判明した。これは今後も使っていきたいテクニックである

コレ自体はコンテスト期間中も書いてたのだけど、あとで viewer にかけたら chars.reverse の reverse がないせいでバグってたことが判明して昨日直したのと、あといま書いてて r が奇数のときはバイトが余るので to_s(2) しても8桁にならない可能性があって、それを format で直すの忘れてたんのでなおした。

つもりになってたが今直したほうは最上位 bit が立ってないケースも該当してて、それは reverse してるから特に問題なかったな……。はい

require 'model'
require 'coordinate'

class ModelDecoder
  def initialize(src)
    @src = src
  end

  def decode
    return @model if defined?(@model)
    _decode
  end

  private

  def _decode
    @r = bytes.first
    indexes = []
    bytes.drop(1).each.with_index do |b, i|
      base = i * 8
      str = "%80d" % b.to_s(2)
      str.chars.reverse.each.with_index do |c, j|
        if c == '1'
          indexes << base + j
        end
      end
    end
    cs = indexes.map do |i|
      x, tmp = i.divmod(@r*@r)
      y, tmp = tmp.divmod(@r)
      z = tmp
      Coordinate.new(x, y, z)
    end
    @model = Model.new(r: @r, fulls: cs)
  end

  def bytes
    @bytes ||= File.open(@src) do |io|
      io.each_byte.to_a
    end
  end
end

コマンドのエンコーダ/デコーダ

これは特に書いてて面白いことなかったのでパス。固定長じゃなくて2バイト読む必要があったのがめんどかった。配列渡して shift していく方式にして必要なら余分に shift すればおk

viewer

three.js つかって書いたら結構簡単にできてすごーいってなった。texture に適当にそのへんにあった water.jpg を使っているのだが見にくい。
左が公式のやつで右が僕のやつです。公式のやつ影とかついてて偉いな……。

なお、コレをみてなんかモデルのデコード失敗してんだなと理解して直した↓

そんなに真面目にフロント書くわけじゃないし webpack とか使う気にならず、 ln -s ../node_modules/three/build/three.min.js three.min.js とかで symlink はって終わらせました。

画像が回転できないと話にならないので回転させたんだけど最初は scene の rotate ではなくカメラのポジションをぐるぐるまわして、中心に向き直ってーとか考えてた。
原点を中心とした球の面上を移動すればよくて、(0, 0, R) を始点として zx 側の角度と zy 側の角度がわかれば球上の1点を指定できる気がした……のだがこれがどうもうまくいかない。たぶん球上の点になってないけどベクトルはあってるみたいな状態になってるので何倍かしてやればよかったな、と今更思った。

document.addEventListener("DOMContentLoaded", function() {
  var delta = 10;

  const modelSelect = document.getElementById("model");
  const viewerDiv = document.getElementById("viewer");
  const rightArrow = document.getElementById("right-arrow");
  const leftArrow = document.getElementById("left-arrow");
  const topArrow = document.getElementById("top-arrow");
  const downArrow = document.getElementById("down-arrow");
  fetch("/models")
    .then(e => e.json())
    .then(function(list) {
      const fragment = document.createDocumentFragment();
      list.sort().forEach(e => {
        const opt = document.createElement("option");
        opt.value = e;
        opt.textContent = e;
        fragment.appendChild(opt);
      });
      modelSelect.appendChild(fragment);
    });
  modelSelect.addEventListener("change", function() {
    const value = this.value;
    fetch(value)
      .then(e => e.json())
      .then(function(model) {
        const r = model.r;
        scene = new THREE.Scene();
        camera.position.z = 2 * unit * r;
        model.fulls.forEach(function({ x, y, z }) {
          scene.add(cubeCreator(r, x, y, z));
        });
        requestAnimationFrame(animate);
      });
  });
  rightArrow.addEventListener("click", function() {
    scene.rotateY(THREE.Math.degToRad(delta));
    requestAnimationFrame(animate);
  });
  leftArrow.addEventListener("click", function() {
    scene.rotateY(THREE.Math.degToRad(-delta));
    requestAnimationFrame(animate);
  });
  topArrow.addEventListener("click", function() {
    scene.rotateX(THREE.Math.degToRad(delta));
    requestAnimationFrame(animate);
  });
  downArrow.addEventListener("click", function() {
    scene.rotateX(THREE.Math.degToRad(-delta));
    requestAnimationFrame(animate);
  });
  document.addEventListener("keydown", function(e) {
    if (e.keyCode === 37) {
      leftArrow.click();
    }
    if (e.keyCode === 38) {
      topArrow.click();
    }
    if (e.keyCode === 39) {
      rightArrow.click();
    }
    if (e.keyCode === 40) {
      downArrow.click();
    }
  });

  var camera, scene, renderer;
  const unit = 1;
  const width = 820;
  const height = 820;
  const cubeCreator = (function() {
    const texture = new THREE.TextureLoader().load("textures/water.jpg");
    return function(r, x, y, z) {
      const geometry = new THREE.BoxBufferGeometry(unit, unit, unit);
      const material = new THREE.MeshBasicMaterial({ map: texture });
      const mesh = new THREE.Mesh(geometry, material);
      mesh.position.x += (x - r / 2) * unit;
      mesh.position.y += (y - r / 2) * unit;
      mesh.position.z += (z - r / 2) * unit;
      return mesh;
    };
  })();
  init();
  function init() {
    camera = new THREE.PerspectiveCamera(70, width / height, 1, 1000);
    renderer = new THREE.WebGLRenderer({ antialias: true });
    renderer.setPixelRatio(window.devicePixelRatio);
    renderer.setSize(width, height);
    viewerDiv.appendChild(renderer.domElement);
  }
  function animate() {
    if (scene) {
      renderer.render(scene, camera);
    }
  }
});

simulator

やる気にならなくていまブログ書いてるところです

今後

シミュレータがあれば適当に手で生成した命令列を実行したときの結果が見えるから戦略を考えてざーっと確かめられそう。でも下回りが整ったら飽きそうではある。