---
# System prepended metadata

title: ICFPC 2022 negainoido 和訳

---

# ICFPC 2022 negainoido 和訳

[TOC]

* 参考：[去年](https://hackmd.io/jKSqeT9bRnqYsivVW602Yg?both)

[specification v0](https://github.com/icfpcontest2022/icfpcontest2022.github.io/blob/fbb04f977962f1cc39ba43486454b1540f634b72/ContestSpecification.pdf)

## Introduction

ラムダランドの強力な魔法使いは、昨年のあなたのポーズをすべて見て、絶対的に魅了されました。
その魅力にすっかりとりつかれてしまったようです。彼らはあなたにとても触発され
残りの期間、絵の秘術を発見し、あなたの参加を待っています。
あなたが参加するのを待っているのです。あなたの使命は、もしあなたがそれを受け入れることを選択するならば、次のようなものでしょう。
ロボペインティングのアルゴリズムを開発することです。何しろ、描くべき絵はたくさんあるのに
それを作るプログラマーは少ないのです。優勝者には
レオナルド・ダ・ヴィンチの名誉あるメダル「ロボヴィンチ・メダル」を授与します。

<!--

The mighty wizards of Lambda land has seen all your poses from last year and
they were absolutely fascinated by them. They were so inspired by you that they
have been discovering the secret arts of painting for the rest of the year, waiting
for you to join them. Your mission, if you choose to accept it; will be to develop
algorithms for robo-painters of the future. After all, there are so many paintings
to make, and so little of us functional programmers to make them. The winner
will receive the honor medal of Leondardo Da Vinci, the RoboVinci Medal.

-->

### Timeline
本仕様書は随時更新され、コンテスト期間中にも問題が公開される予定です。
公開されます。具体的には以下の時期に行われます。

* コンテスト開始4時間後（新規問題のみ、仕様変更なし）
* コンテスト開始8時間後 (新しい問題のみ、仕様変更なし)
* コンテスト開始12時間後 (新規問題作成、仕様の若干の変更)
* コンテスト開始24時間後 (雷部門終了後)
* コンテスト開始36時間後
* コンテスト開始48時間後


### Changelog
変更があった場合は、ここで公開されます。


## Problem Specification
課題は、与えられたキャンバスを最小のコストと最高の類似度で塗ることである。
タスクの一部として、あなたは与えられる。
* キャンバス上で適用可能な一連の動き
* 一連の動きを表現するための命令言語。
* 各手順のコストを計算するためのコスト関数
* キャンバスと対象絵画の類似度を計算する類似度関数。
を計算する類似性関数です。

個々の問題では、以下のものが与えられます。
- 最初のキャンバス
- 目標とする絵画

### Canvas
キャンバスは、RGBAチャンネルからなる抽象的な2次元のピクセル空間です。
各移動はキャンバスを異なる意味で変形させます。
キャンバスにすべての動きが適用された後、絵画にレンダリングすることができます。
キャンバスはブロックから構成されています。

### Blocks
ブロックは、サブブロックの集合からなるフレーム、または形状と色を持つ単純な構造
形と色を持った単純な構造体です。
関数型プログラマーの目には、このような定義が映るかもしれません。

```
data SimpleBlock = SimpleBlock Shape Color
data ComplexBlock = ComplexBlock Shape ChildBlocks
type ChildBlocks = Set<SimpleBlocks>
data Block = Either SimpleBlock ComplexBlock
```

初期状態のキャンバスにはブロックが 1 つだけあり、色は
rgba(0, 0, 0, 0) で着色されています。
ブロックは block_id で一意に定義されます。
ブロックは block_id で一意に定義され、グローバルカウンタがマージによるブロック生成のために保持されます。
マージによって新しいブロックが作成されるたびに、このカウンタは 1 つずつ増加します。
各カット技は、ブロックのサブブロックを生成します。
ブロックIDの末尾に.0、.1、.2、.3を追加することで、ブロックのサブブロックを生成します（カットの種類に依存）。


### Painting
絵画は、RGBAチャンネルからなる具体的な2次元の画素空間である。個々の問題に対して
個々の問題では、ペインティングのPNGファイルが提供されます。

### Moves
キャンバスに絵を描くために使える5種類の動きを紹介します。

#### Line Cut Move
カット技は、ブロックを取り、そのブロックの上をカットする指示もあります。新しい
サブブロックを作成し、色を保持します。
ラインカット技 ラインカット技は、ブロック（ブロック ID で定義）、方向（縦方向は X または x）を指定します。
方向（縦方向はXまたはx、横方向はYまたはy）、オフセット（カット操作の1-d座標）を取り、2つのブロックを作成します。
を取り、与えられたブロックの2つのサブブロックを作成します。
ラインカットのサブブロックは、下から上、または左から右へと番号が振られます。

#### Point Cut Move 
ポイントカット移動 ポイントカット移動は、ブロック（ブロックIDで定義）、オフセット（カット操作のための2次元座標）を取る。
オフセット（カット操作のための2次元座標）を取り、与えられたブロックの4つのサブブロックを作成する。
を作成する。
ポイントカットのサブブロックは、左下から時計回りの逆順序で番号付けされる。
番号付けを行う。
    
#### Color Move
カラー移動
カラー移動は、ブロックと、RGBA空間上のいくつかの色を取る。色移動は、ブロックとRGBA空間上のある色を受け取り、与えられたブロックの色
を指定された色に変更します。

#### Swap Move
スワップ動作
スワップ移動は、2つのブロックを取る。与えられたブロックの中身を入れ替える。
ブロックの形状は同じでなければならない。
マージ動作
2つのブロックを指定します。新しいブロックを作成し、ブロックをマージします。
この新しいブロックにサブブロックとしてこれらのブロックを追加します。
ブロックの結合には互換性が必要である。ブロックは、隣接していなければならず、その隣接する辺の
ブロックはアドジョイントでなければならず、アドジョイントの辺の長さは同じでなければならない。非公式には、ブロックのマージは
は、新しい矩形を作らなければならない。

#### Merge Move
マージ操作が行われるたびに、新しいブロックが作成されます。新しく作成されたブロックは
ブロックはグローバルカウンタに従ったブロックIDを持つ。例えば
グローバルカウンタがnの場合、このマージ操作によって生成されたブロックはブロックID n+1を持つことになります。
を持つことになる。



### 指示言語
あなたの仕事は、キャンバスに一連の動きを適用して、与えられたターゲット絵画に類似させることです。
絵画に類似させることです。この一連の動きを提供する方法として、あなたは各問題に対して
ISL(Instruction Set Language)ファイルを各問題に提出することです。ISLコードは直接
ISLコードは、上記の手の集合に直接対応します。
ISL文法のBNF(Backus-Naur Form)形式は、この仕様書の末尾に記載されています。
に示す.


### コスト関数
各手には基本コストと動的コストがある。
以下は、各手に対する基本コストの表である。

基本コスト

- ラインカット: 7
- ポイントカット: 10
- カラー: 5
- スワップ: 3
- マージ: 1


コストを表す関数は
```
cost(move, block, canvas) = round(base_cost(move) x size(canvas)/size(block)) 
```
    
です。
各投稿について、これらのスコアを各手ごとに計算し、集計して総コストを計算します。
総コストを計算する。

### 類似性関数
投稿作品の全手数を処理した後、対象作品との類似度を計算する。
を計算する。
これは、RGBA色空間での画素差を各画素ごとに計算し、その結果を集計することにより行われます。
を計算し、その結果を集計しています。
画素差は、各画素のRGBA値のユークリッド距離で計算される。
によって算出されます。計算方法は以下の通りである。

$$
pixeDistance = \sqrt{distR × distR + distG × distG + distB × distB + distA × distA}
$$

$$
imageDistance = sum(pixelDistance, ∀ pixels) × 0.05 
$$

となります。
    
混乱を避けるため、これらの計算のソースコードを提供する。

### スコアリング
各問題の得点は、ISLコードのコストとSimilarityの結果を加算して計算されます。
コードのコストとSimilarity Functionの結果を加算して算出する。コストが高いほど、スコアボードの順位は低くなります。
コンテストのスコアボードでは、まず参加者を解答を提出した問題の数で分類します。
参加者を分類する。それぞれの参加者のクラスについて
参加者のコストを合計し、それに応じて並べ替えます。次に、参加者のクラスを提出された解答の数で分類します。
参加者クラスは、解答を提出した問題数で分類します。
より具体的な例として、以下のような出場者リストがあります。


P1:
P2:
P3:
P4:

2
3
2
1

の問題です。
の問題です。
問題
問題

合計
合計
合計
トータル

コスト
コスト
コスト
コスト

90
100
80
50

スコアボードでは、参加者がP2、P3、P1、P4とソートされる。

## 提出方法
ISLコードをポータルサイト内のパネルから投稿していただきます。また
REST APIを提供します。

## 締切
従来のように、コンテストは最初の24時間にライトニング部門を設けています。
があります。ライトニング部門賞の受賞資格を得るには、以下の期限までにISLコードを投稿してください。
2021年9月3日12時(正午)まで(UTC)
フル部門賞の受賞資格を得るには、9月5日までにISLコードを送信してください。
UTC 12:00pm（正午）までにISLコードを提出してください。
賞品を獲得するためには、コンテスト終了までにソースコードを提出する必要があります。
ソースコードは、コンテスト終了までに提出してください。これは、Webポータルから行うことができます。

## 受賞者の決定
ライトニング部門、フル部門ともに、同じ手順で勝者を決定します。
各タスクのスコアの合計で計算される累積スコアで順位を決定します。
各タスクのスコアの合計で算出されます。


## ISL仕様
ISLコードは、キャンバス上の手の集合である。
まず、ISL文法の説明から始める。

### ISL文法
    
```
<program> ::= <program-line> | <program-line> <newline> <program>
<program-line> ::= <newline> | <comment> | <move>
<comment> ::= "#" <unicode-string>
<move> ::= <pcut-move> | <lcut-move> | <color-move> | <swap-move> | <merge-move>
<pcut-move> ::= "cut" <block> <point>
<lcut-move> ::= "cut" <block> <orientation> <line-number>
<color-move> ::= "color" <block> <color>
<swap-move> ::= "swap" <block> <block>
<merge-move> ::= "merge" <block> <block>
<orientation> ::= "[" <orientation-type> "]"
<orientation-type> ::= <vertical> | <horizontal>
<vertical> ::= "X" | "x"
<horizontal> ::= "Y" | "y"
<line-number> ::= "[" <number> "]"
<block> ::= "[" <block-id> "]"
<point> ::= "[" <x> "," <y> "]"
<color> ::= "[" <r> "," <g> "," <b> "," <a> "]"
<block-id> ::= <id> | <id> "." <block-id>
<x> | <y> ::= "0", "1", "2"...
<id> | <number> ::= "0", "1", "2"...
<r> | <g> | <b> | <a> ::= "0", "1", "2"..."255"
<newline> ::= "\n"
    
```
