Incinerator

CheckIO Incineratorの問題和訳
問題ページのうち, 問題の前提となる小話は訳してません.
また各問題ページ下部にある「Precondition」は「前提条件」のため訳しません(数値の範囲などだけなので).

The Good Radix

Find the minimal possible number for a radix.

In mathematical numeral systems, the radix or base is the number of unique digits (including zero) that a positional numeral system uses to represent numbers. For example: in the decimal system, the radix is ten. This is because it has ten digits from 0 through 9. In a system with a radix of 13, there would be 13 digits. For example: a string of digits such as 398 denotes the decimal number 3 * 13^2 + 9 * 13^1 + 8 * 13^0. For the systems with a radix more than 10, we will use capital Latin symbols from A to Z, where A = 10, B = 11 ...
You are given some number n written as a string with the radix equal to k (1 < k < 37). We know that our number is divisible by (k - 1) without a remainder. You should find the minimal possible k, if it exists, or return 0.
For example: n = "18". As we can see k should be greater than 8.
If k == 9, then n = 20 in the decimal system and 20 % 9 == 2. The wrong radix.
If k == 10, then n = 18 in the decimal system and 18 % 9 == 0. We found the answer.

Input: A number as a string.
Output: The radix k as an integer.

How it is used:

Let's familiarize with numeral systems more careful and examine the radix. Many devices are built to accept numbers in decimal representation and display results in decimal. Often such devices convert from decimal to some internal radix on input, do all internal operations in that radix, and then convert the results from the internal radix to decimal on output. Such devices could in principle use any radix internally. The people who design such computing devices sometimes wonder what would be the "best" radix to use internally -- radix economy. The octal, hexadecimal and base-64 systems are often used in computing because of their ease as shorthand for binary.

訳

数学のp-進法では, 数を表現するのに0を含む桁に基数が使われる. たとえば, 10進法では基数は10だ. これは0から9の数字が10個あるからだ. 13進数では, 13個の数字がある. たとえば, 398という13進数の文字列を10進数で表すと, 3 * 13^2 + 9 * 13^1 + 8 * 13^0となる. 10以上の進数のために, 私たちはA=10, B=11,...としてAからZを使う.
あなたには基数kのいくつかの数が文字列として与えられる. 私たちはその数が(k - 1)で割り切れることを知っている. あなたは最小のk(存在するなら)を返す. 存在しないなら0を返す.
例: n = "18", kは少なくとも8より大きいことがわかる.
k == 9なら, 10進数ではn = 20となるが, 20 % 9 == 2だ. よってこの基数はダメだ.
k == 10なら, 10進法ではn = 18となり, 20 % 10 == 0だ. 答えが見つかった.

入力:文字列として数字
出力:整数の基数k

備考

p-進法や基数の調査に慣れよう. 多くのデバイスでは10進数が組み込みで使われ, 表示も10進数だ. しばしばデバイスは10進数からいくつかの基数に変換され, その基数によって演算され, 再び10進数として変換される. このようなデバイスは内部で基数変換の原理が使われている. コンピュータをデザインした人々は, 内部で効率的なよい基数を使う. 2進数を短く表現できる8進数, 16進数, そして64進数はしばしばコンピュータで使われる.

CheckSum

Help reduce the likelihood of errors during a transcription by introducing a final character that is calculated from the previous characters.

Errors during transcription are rather common. Unintentional keystrokes can cause characters to be rearranged, dropped or inserted in manually typed text.
Luckily for the robots, you have ways to solve problems like this. Your CheckSum helps to reduce the likelihood of errors by introducing a final character that is calculated from the previous characters. With the proper reasoning, the final character can always be calculated. This way, when inputs are entered, you can instantly verify that the final character matches the character predicted by CheckSum. If the two do not match, the input is rejected. The end result is that you would see fewer data entry errors.

訳

転送時のエラーは一般的である. 何気ないキーストロークは文字の再配置, 落字, または手動で入力したテキストへの挿入を引き起こす.
ロボットにとっては幸運なことに, あなたはこのような問題を解く方法を知っている. あなたのチェックサムは前の文字から計算される最後の文字を使うことで, エラーを低減させる可能性を助ける. その理由は, 最後の文字は常に計算によって得られるからだ. この方法では, チェックサムによって最後の文字が予測されるため, 容易に確認が行える. もしマッチしなければ, 入力は拒否される. この結果はあなたにデータエントリーエラーを見せる.

メモ

...

図を見ればどう計算するかわかるので思いっきり省略.

The shortest Knight's path

Find the shortest path for a knight crossing a chessboard.

Sofi found a chess set in the supply closet on the robots ship. She has decided to learn how to play the game of chess starts by attempting to understand how the knight moves.
Chess is played on a square board of eight rows (called ranks and denoted with numbers 1 to 8) and eight columns (called files and denoted with letters a to h) of squares.
The knight moves to any of the closest squares that are not on the same rank, file, or diagonal, thus the move forms an "L"-shape: two squares vertically and one square horizontally, or two squares horizontally and one square vertically.
You are given the start and end squares as chess coordinates separated by a hyphen. You should find the length of the shortest path for the knight from one point to another on the chessboard.

Input: Squares coordinates as a string.
Output: The number of moves in the shortest path the knight can take as an integer.

How it is used:

Let's think about chess and how we can use pathfinding and computer science to play this awesome game. The game structure and nature of chess is related to several branches of mathematics. Many combinatorial and topological problems connected to chess have been known for hundreds of years.

訳

ソフィーはロボット船のクローゼットにチェスのセットを見つけた. 彼女はナイトがどう動くかを理解するために, チェスのゲームの遊び方を学ぶことを決めた.
チェスは8行(ranksと呼ばれ1から8まである)と8列(filesと呼ばれaからhまである)の正方形のボードでプレイする.
ナイトの移動は最も近いマスには行けず, L字型に移動する. 1マス水平に, 2マス垂直に, もしくはその逆.
あなたにはハイフンで区切られたチェス盤の始点と終点が与えられる. あなたは始点から終点までのナイトの最短経路を見つける必要がある.

入力:文字列として2マス(始点と終点)
出力:始点から終点までの最短手, 整数

備考

チェスとコンピュータサイエンスでの経路探索について考えよう. このゲームの構造とチェスの特徴は数学のいくつかの分野と関連している. 多くの組み合わせ論やトポロジーの問題とチェスは結び付いているということが何百年もの間知られている.

Mono Captcha

Can you read the number shown in an image encoded as a 0-1 2D array?

Let's teach Stephan to recognize simple numbers. The Robots use monospaced fonts with low resolution. You can see the font on the picture below. This font has noise immunity to one-pixel error.
Your program should read the number shown in an image encoded as a binary matrix. Each digit can contain a wrong pixel, but no more than one for each digit. The space between digits is equal to one pixel (just think about "1" which is narrower than other letters, but has a width of 3 pixels).

Input: An image as a list of lists with 1 or 0.
Output: The number as an integer.

How it is used:

This task will show you how optical character recognition works and will familiarize you with low-resolution fonts requiring noise-immunity. This can be useful for the systems that required the reliability.

訳

ステファンに単純な数字の認識を教えよう. ロボットは低解像度のモノスペースなフォントを分析できる. あなたは下の写真にあるフォントを見ることができる. このフォントは1ピクセルだけノイズを持つことがある.
あなたのプログラムは2進数の行列としてエンコードされた画像から, 数字を読みとる. それぞれの数値は間違ったピクセルを含みうるが, それは多くても1つまでである. 数値同士の間は1ピクセル分開いている(ただし"1"は他と比べて幅がせまいが, 数値自体の幅は3ピクセルである).

入力:1と0からなるリストのリストを画像として扱ったもの.
出力:読みとった数値を整数で.

備考

このタスクは光学文字認識の方法を示し, ノイズ除去を必要とする低解像度のフォントに慣れさせるだろう. これは信頼性が必要なシステムでよく使われる.

Restricted Prime

Check if a number is a prime or not. Sounds easy? You're in for a surprise...

Next, we want to teach our censored calculator to check if numbers are primes or not. This crazy calculator has learned new some words (but forgotten some others) and does not accept new words, certain symbols and it hates digits!
The list of forbidden words and symbols:

import
div
eval
range
len
⁄ % −
digits (0-9)

Given a number (0 < n < 10000), you should check if it is a prime or not. Your solution should not contain any of the forbidden words, symbols or digits (even as a part of another word).

Input: A number as an integer.
Output: Is it prime or not as a boolean.

How it is used:

Challenge your creativity and come up with a solution to fit this mission's specs!

訳

さて, 私たちは数値が素数かどうかチェックするために, 検閲された計算機を教えたい. このクレイジーな計算機は記号と数値を憎み, いくつか新しい単語を学んでいる(しかしいくつかは忘れている).
下のリストが禁じられた単語と記号のリストだ.

import
div
eval
range
len
/ % -
digits(0-9)

ある数n(0 < n < 10000)が与えられ, あなたはそれが素数かどうか判定する. あなたの解答は禁じられた単語, 記号, 数値を含んでいてはならない.

入力:ある数, 整数
出力:素数かどうか, TrueかFalse, boolean

備考

あなたの創造力への挑戦だ!

Area of a convex polygon

Calculate the area of a convex polygon located on a coordinate plane.

There is a convex polygon on a coordinate plane. This polygon is presented as a list of vertices coordinates. Each vertex is connected sequentially with the last connecting back to the first. A polygon has N vertices. You should write a program that will calculate the area of a polygon. The result should be given with one digits precision as ±0.1.

Input: Coordinates as a list of lists. Each list contains two integers.
Output: The area of the polygon as a float.

How it is used:

This concept is very useful in topography and architecture. You can improve the algorithm and calculate the area of any zone on the map taking into account elevation and other points of interest. You could also use this idea to construct something like a building, or a boat.

訳

平面に凸多角形がある. この多角形は頂点の座標のリストで表現される. それぞれの頂点は連続してつながっており, 最後の頂点は最初の頂点につながる. 多角形はN個の頂点を持つ. あなたは多角形の面積を計算するプログラムを書く. 結果の誤差は±0.1とする.

入力:リストのリストとしての頂点. それぞれのリストは2つの整数を持つ.
出力:多角形の面積を浮動小数点で.

備考

このコンセプトは地形学や建築学でとてもよく使われる. あなたはアルゴリズムを改善し, あらゆる領域の面積の計算できるだろう. これは建物や船を組み立てるためのアイデアでもある.

Snake

Relive the classic game "Snake" and eat 5 cherries randomly placed on the field.

We all know the classic game "Snake".
You are given a 10x10 field of cells. You control a snake and your task is to eat 5 cherries which are randomly placed on the field. The snake starts the game 5 units long and grows by one unit for each cherry it eats. In order to survive long enough to eat the cherries, the snake must not hit a tree, the edge of the field, or its own body. Doing so would trigger a game over. The snake does not sit still and is constantly moving. It can go in one of 3 directions: Forward “F”, Left “L” and Right “R”. Left and right are defined by the current position and trajectory of the snakes head. The map of field is presented as list of strings, where:

   "." - Empty cell
   "T" - Tree
   "C" - Cherry
   "0" - Snake head
   "1..9" -  Numbered Segments of the Snake Body

This is a multi-call task and your function will be called repeatedly until the game is complete. During each function call, you can return a character or a string that contains a sequence of actions (example: “FRFLF.”) Once the snake eats a cherry the remaining actions are dropped, a new cherry appears and the game continues. Once 5 cherries are eaten the game is over and you win. This version of snake has an interesting twist: you must eat the 5 cherries in 250 steps or less or face a game over.

Input: The map of field as a list of strings.
Output: One or more actions as a string.

How it is used:

With this game you prove that you can write a simple artificial intelligence. Here you should figure out pathfinding and planning. These are useful skills for many spheres of the real life. ;-)

訳

私たち皆は古典的なゲーム"Snake"を知っている.
あなたには10x10のセルで出来たフィールドが与えられる. あなたは蛇を操作し, フィールドにランダムにおかれたサクランボを蛇に食べさせる. 蛇はゲーム開始時に5ユニット分の長さを持ち, サクランボを1つ食べるごとに1ユニット分大きくなる. サクランボを十分食べて長く生き残るためには, 蛇は木とマップの端, そして自身の体に衝突してはならない. そうしたらゲームオーバーになる. 蛇は止まることなく一定に動き続ける. 蛇は3つの方向, すなわち, 前進"F", 左"L", 右"R"のどれかを向くことができる. 左と右は現在の位置と蛇の軌道で決定される. フィールドのマップは文字列のリストとして表現される. ここで各記号の意味は以下のとおりである.

"." - 空のセル
"T" - 木
"C" - サクランボ
"0" - 蛇の頭
"1..9" - 蛇の体の数字

これは多重呼び出しのタスクで, あなたの関数はゲームが完了するまで繰り返し呼ばれ続ける. それぞれの関数が呼ばれている間, あなたはアクションのシーケンスを含んだ文字列か文字を返す(例: "FRFLF"). 蛇がサクランボを食べると残っているアクションは廃棄され, 新しいサクランボが出現し, ゲームは続行する. 5回サクランボを食べさせると, ゲームをクリアし, あなたの勝利となる. このバージョンの蛇は興味深いねじれをする. あなたは5つのサクランボを250ステップ以内食べさせないとゲームオーバーになる.

入力:文字列のリストとしてフィールドのマップ
出力:1つ以上のアクションを文字列として

備考

このゲームはあなたに単純なAIをあなたが書けるということを証明する. ここであなたは経路探索と計画を理解するだろう. 様々な分野でこのスキルは使われる.

Bulls and Cows

Have you ever played the old game "Bulls and Cows"? Yeehaaww!

In his grandfather's notebook Nicola found a description of an old game called "Bulls and Cows", which was popular amongst ancient humans. He wants to try and play it with Stephan, but Nicola does not losing games. That's where we come in!
The host thinks up a 4-digits sequence. The digits must all be different. Then, in turn, you try to guess the sequence. If the matching digits are on their right positions, they are called "bulls", when they are on different positions, they are "cows". The host tells you how many "bulls" and "cows" you've guessed. You should attempt to solve the code in eight turns (it is however, possible in seven turns).
On each step, your function receives a list with information from the previous steps. Each element of the list contains your guess and the result in the following format "XXXX YBZC", where:

XXXX is a guess
Y is a quantity of "bulls"
Z is a quantity of "cows"

For each step your function returns your new guess as a string with four digits.
Let's consider an example. The hidden code is "5612". At the start your function receives an empty list. Your guess is "1234" -- two digits are on different positions but appear in the code. So the next call will be ["1234 0B2C"]. Your next guess is "6512" -- two "bulls", two "cows". The next input is ["1234 0B2C", "6512 2B2C"]. And the last guess is "5612". Aaand you win!

Input: Information from your last steps as a list of strings.
Output: The guess as a string.

How it is used:

This is a simple game that might even amuse you without requiring much coding; however when you write the code, your algorithm is an example of what prediction software looks like.

訳

ニコラは祖母のノートに古い"Bulls and Cows"というゲームの記述を見つけた, そのゲームは古代人の中で最も有名だった. 彼はステファンとともに遊んでみたが, ニコラはゲームに負けなかった. それではやってみよう!
ホストは4桁の数を考える. その数字は全ての桁が違う数字でなければならない. そしてあなたはその数字を当てようと試みる. もし数が正しい位置でマッチしたら, かれらは"bulls"と呼び, 異なる位置でマッチしたら, 彼らは"cow"という. ホストはあなたの推測に対し何回"bulls"と"cow"があるかを教える. あなたは8ターン以内に解くコードを書く必要がある(実のところ7ターンで可能である).
それぞれのステップでは, あなたの関数は前のステップからの情報とリストを受け取る. リストの要素はあなたの推測と, "XXXX YBZC"というフォーマットの結果である. ここで結果のフォーマットをまとめる.

XXXXは推測
Yは"bulls"の数
Zは"cows"の数

それぞれのステップではあなたの関数は新しい推測を4桁の文字列として返す.
例で考えてみよう. 隠された数字は"5612"だ. まずあなたの関数は空のリストを受け取る. あなたの推測は"1234"だ, 2つの数字が異なる位置でマッチしている. なので, 次は["1234 0B2C"]だ. あなたの次の推測は"6512", 2つの"bulls"と2つの"cows"だ. 次の入力は["1234 0B2C", "6512 2B2C"]だ. 最後の推測は"5612". そしてあなたの勝利だ!

入力:文字列のリストとしてあなたの最後のステップからの情報
出力:推測の文字列

備考

これは単純なゲームで, たぶんコードなしにあなたを楽しませるだろう, しかしながら, コードを書いたとき, あなたのアルゴリズムは予想システムの例となるだろう.

Anagrams By Stacks

Play with letters to create a new word from an old word.

You have been given two anagrams as a string, separated by dash. You need to rearrange the letters to turn the first word into the second. The tools you have for this mission are two stacks and a one-letter buffer. The first stack is the beginning of a word; the second stack is where you will put the anagram. The word is placed in the stack, letter by letter. The first letter of the anagram is placed in the bottom stack and the last letter in the middle stack, until it is needed as the end of the anagram. You need to return the shortest sequence of actions to move and turn the word in the first stack into the anagram in the second. The first stack is labeled 1, the second is labeled 2, and the buffer as 0. The action is written as a string of two numbers which signify the original location of the letter and the new location. For example: 12 means that from the first stack, we take the last letter and place it at the end of the second stack. For the result, you need to get a string that lists the steps, separated by commas.

Input: Two words separated by dash as a string.
Output: A sequence of actions as a string.

How it is used:

Here you can play with stacks and how they work in games. We see stacks in everyday life, they’re in the books in our library, and the blank sheets of paper in our printer tray.

訳

あなたにはダッシュで区切られた文字列として, 2つのアナグラムが与えられる. あなたは最初の文字と2つ目の文字を再配置する必要がある. あなたはこのミッションのために2つのスタックと1文字のバッファをツールとして持っている. 最初のスタックは単語の始まりで, 次のスタックはアナグラムを置くものだ. 単語は文字ごとスタックに置かれる. アナグラムの最初の文字はスタックの底におかれ, 最後の文字はアナグラムの終わりとして必要になるまで, 中央のスタック(1文字のバッファ)に置かれる. あなたは最初のスタックから次のスタックのアナグラムへと移動させるアクションの, 最も短い数列を返す必要がある. 最初のスタックはラベル1, 次のスタックはラベル2, バッファはラベル0となっている. アクションは文字の元の場所と新しい場所を示す2つの数字の文字列として書かれる. たとえば, 12は最初のスタックの最後の文字が, 2つ目のスタックの最後の文字に移動することを意味する. 結果として, あなたはコンマで区切られたステップのリストを文字列として得る.

入力:ダッシュで区切られた2つの単語, 文字列
出力:アクションの数列, 文字列

備考

ここであなたはスタック操作とそれらがどう動くかをゲームで遊ぶことができる. 私たちは毎日の生活でスタックを見ており, それらは図書館の本の中だったり, プリンタートレイの中の印刷用紙だったりする.

Keywords Finder

Help write a CTRL+F function for the robots

Sophie has found a stash books and she wants to find information about the ancients who lived on the islands. Unfortunately, she does not have a text search module and needs some help. Let's write a program to help her search for keywords on the pages of a book.
You are given some plain text (without tags) and a string with keywords (or parts of words, or letters) separated by spaces. You will need to find all the keywords and put these words into "<span></span>" wrappers to highlight them for Sophie. You can ignore upper or lower cases for the key words, but the original letter cases in the text should remain.
For the cases when keywords contain or intersect each other you should highlight the larger word without nested span tags. Let's look it with example.
The text "Hello World! Or LOL" and keywords "hell world or lo".
The word "World" contains two keywords thus we tag only larger part "<span>World</span>".

"Hello" contains two intersected words "hell" and "lo" and we tag the larger part again "<span>Hello</span>".
Be careful, a result like "<span>Hel<span>lo</span></span>" is considered wrong because it contains nested tags.

Input: Two arguments. A text and key words as strings.
Output: The text with wrapped key words.

How it is used:

You see this task every day when use your browser or work with documents. Every time when you search something on the page and want to see the found fragments as highlighted parts, you encounter the concept seen in this task. This problem can be more complex if you use it for the languages where you need to write "lowercase" rules.

訳

ソフィアは隠された本を見つけ, この島に住んでいた古代人についての情報を調べていた. 不運な事に, 彼女はテキストの検索モジュールを持っていなかったので, 手助けを必要とした. さぁ彼女のために本のページにあるキーワードを検索するプログラムを書こう.
あなたにはタグのないいくつかの平文とキーワードとしての文字列(部分文字列や文字)がスペースで区切られて与えられる. あなたは全てのキーワードを見つけ, ソフィアのために単語を"<span></span>"で囲む必要がある. あなたはキーワードの大文字と小文字を無視することができるが, テキストにあるオリジナルの文字は残さねばならない.
spanタグがネストしないように, キーワードの中に見つかった場合は長いほうの単語にタグをつける. 例を見てみよう.
テキストは"Hello World! Or LOL"で, キーワードは"hell world or lo"だ.
"World"は2つのキーワードを含むが, 大きいほうをとるので, "<span>World</span>"となる. "Hello"は2つの単語"hell"と"lo"が交わるので, 同じように"<span>Hello</span>"となる.
"<span>Hel<span>lo</span></span>"とならないように注意しよう, それはネストしたタグである.

入力:2つの引数, テキストとキーワード.
出力:キーワードにタグが挿入されたテキスト

備考

あなたはこのタスクをブラウザやドキュメントの操作で毎日見るだろう. 毎回あなたはページで検索し, ハイライトされた単語を見ているだろう. あなたはこのタスクでそのコンセプトと出会う. この問題はあなたが小文字ルールを書く必要があるような言語などでは更に複雑になる.

Sudoku Solver

Another classic puzzle on this island: solve a Sudoku grid.

Sudoku is a logic-based combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.

Input: The initial 9x9 grid composed by integers. A zero value means that the value hasn't been set.
Output: Return the result of the sudoku (9x9 grid).

訳

数独は組み合わせ理論をもとにした数字を配置するパズルだ. このパズルの目的は行, 列と, 3x3の子グリッドからなる9x9のグリッドに, それぞれ1から9を全て満たすことである. このパズルには最初いくつかの数値が入っており, 固有の解を持つ.

入力:整数で初期化された9x9グリッド. 0はそのセルの値が未設定であることを意味する.
出力:数独の解, 9x9のグリッド