こんにちは。最近やっと春休みに入って少し一息ついています。１週間だけなのでほんとひと息と言う感じですが。。
ではCodeFights ArcadeモードIntroでの問題演習５週目、かつIntro編最後の記事です。春休みの間にUnityの勉強を始めたかったのでペース上げて行きます。
49. lineEncoding
Given a string, return its encoding defined as follows:
First, the string is divided into the least possible number of disjoint substrings consisting of identical characters
for example, "aabbbc" is divided into ["aa", "bbb", "c"]
Next, each substring with length greater than one is replaced with a concatenation of its length and the repeating character
for example, substring "bbb" is replaced by "3b"
Finally, all the new strings are concatenated together in the same order and a new string is returned.Example:
For s = "aabbbc", the output should be
lineEncoding(s) = "2a3bc".
自分の解答
とてもながい(白目)
std::string lineEncoding(std::string s) {
int c = 1, p = 0;
std::string ret = "";
for (int i = 1; i < s.size(); i++){
if (s[p] == s[i]) c++;
else {
if (c > 1) ret += std::to_string(c);
ret += s[p];
p = i;
c = 1;
}
}
if (c > 1) ret += std::to_string(c);
ret += s[p];
return ret;
}
別解
fyzixさんより。条件演算子のところ、""の後にsが続いてるのは一体どうして。。。？
std::string r, lineEncoding(std::string s) {
for (auto i = begin(s), j = i; i != end(s); i = j) {
while (*j == *i) ++j;
r.append(j-i>1 ? to_string(j-i) : ""s).push_back(*i);
}
return r;
}
50. chessKnight
Given a position of a knight on the standard chessboard, find the number of different moves the knight can perform.
自分の解答
普通に一マスずつナイトが動けるかどうか調べました。マインスイーパの問題の別解(24. Minesweeper)を思い出しながら解きました。
int chessKnight(std::string cell) {
int c = 0;
c += cell[0] < 'h' && cell[1] < '7';
c += cell[0] < 'g' && cell[1] < '8';
c += cell[0] < 'g' && cell[1] > '1';
c += cell[0] < 'h' && cell[1] > '2';
c += cell[0] > 'a' && cell[1] > '2';
c += cell[0] > 'b' && cell[1] > '1';
c += cell[0] > 'b' && cell[1] < '8';
c += cell[0] > 'a' && cell[1] < '7';
return c;
}
別解１
sir_ementalerさんより。
bool valid(int a, int b) {
return a >= 0 && a < 8 && b >= 0 && b < 8;
}
int chessKnight(std::string cell) {
int a = cell.front() - 'a', b = cell.back() - '1';
return
+ valid(a - 2, b - 1)
+ valid(a - 2, b + 1)
+ valid(a + 2, b - 1)
+ valid(a + 2, b + 1)
+ valid(a - 1, b - 2)
+ valid(a - 1, b + 2)
+ valid(a + 1, b - 2)
+ valid(a + 1, b + 2)
;
}
別解２
yasharさんより。
int chessKnight(std::string c) {
int ans = 0;
for(int i = -2; i < 3; ++i)
for(int j = -2; j < 3; ++j)
{
if(abs(i)+abs(j)==3)
ans += c[0]+i>='a' && c[0]+i<='h' && c[1]+j>='1' && c[1]+j<='8';
}
return ans;
}
51. deleteDigit
Given some integer, find the maximal number you can obtain by deleting exactly one digit of the given number.
Example:
For n = 152, the output should be
deleteDigit(n) = 52;
For n = 1001, the output should be
deleteDigit(n) = 101.
自分の解答
最初は単に一番小さい数字を消せば良いだけかと思ったらそんなことはなかった。
(例えば deleteDigit(32512) = 3512)
int deleteDigit(int n) {
string s = to_string(n);
for (int i = 1; i < s.size(); i++)
if (s[i - 1] < s[i]) {s.erase(s.begin() + i - 1); return stoi(s);}
s.erase(s.end() - 1);
return stoi(s);
}
それと、最後のs.eraseは-1しないとうまくいかないです。s.end()の戻り値がstringの末尾の次を指すiteratorなので。
string::end
別解１
thienbuiさんより。大した場合の数じゃないし一つ一つ数字を消して見るのもありでした。が、こんな消し方があるんですねびっくり。
int deleteDigit(int n) {
int ans = 0;
for(int d=1;d <= n; d*=10){
int tmp = n%d + ((n/d)/10)*d;
ans = max(ans,tmp);
}
return ans;
}
別解２
le_d5さんより。僕と似てるけどもっとシンプル。
int deleteDigit(int n) {
std::string digitStr = to_string(n);
int index = 0;
for(; index < digitStr.size()-1; index++)
{
if( digitStr[index] < digitStr[index+1] ) break;
}
return stoi( digitStr.substr(0,index) + digitStr.substr(index+1) );
}
52. longestWord
Define a word as a sequence of consecutive English letters. Find the longest word from the given string.
Example:
For text = "Ready, steady, go!", the output should be
longestWord(text) = "steady".
自分の解答
文字列分割系はいつも苦戦する。。。
std::string longestWord(std::string text) {
std::string ret = "";
for (int i = 0; i < text.size();) {
int c = 0;
while (isalpha(text[i + c])){c++;}
ret = ret.size() > c ? ret : text.substr(i, c);
c == 0 ? i++ : i += c;
}
return ret;
}
別解
sir_ementalerさんより。またregexだ。。。 正規表現に関してはあとでしっかり勉強する機会設けよう_:(´ཀ`」 ∠):
std::string longestWord(std::string text) {
std::regex expr("[A-Za-z]+");
std::sregex_iterator it(text.begin(), text.end(), expr), end;
return std::max_element(it, end, [](const std::smatch& a, const std::smatch& b) {
return a.length() < b.length();
})->str();
}
53. Valid Time
Check if the given string is a correct time representation of the 24-hour clock.
Example:
For time = "13:58", the output should be
validTime(time) = true;
For time = "25:51", the output should be
validTime(time) = false;
For time = "02:76", the output should be
validTime(time) = false.
自分の解答
以前別の問題の別解で見た解答を参考に解きました。
bool validTime(std::string time) {
int a, b;
sscanf(time.c_str(),"%d:%d", &a,&b);
return 0<=a && a<24 && 0<=b && b<60;
}
sscanf
別解
確実にプレッシャーをかけてくる正規表現怖い。にしてもこれだけ頻出するものを授業で習わなかったのはなんでだ。。
bool validTime(std::string time) {
return std::regex_match(time, std::regex("(?:[01]\\d|2[0-3]):[0-5]\\d"));
}
54. sumUpNumbers
CodeMaster has just returned from shopping. He scanned the check of the items he bought and gave the resulting string to Ratiorg to figure out the total number of purchased items. Since Ratiorg is a bot he is definitely going to automate it, so he needs a program that sums up all the numbers which appear in the given input.
Help Ratiorg by writing a function that returns the sum of numbers that appear in the given inputString.
Example:
For inputString = "2 apples, 12 oranges", the output should be
sumUpNumbers(inputString) = 14.
自分の解答
うーーんstringの扱いが特に苦手。
int sumUpNumbers(std::string s) {
int ret = 0;
for (int i = 0; i < s.size();) {
int c = 0;
while (isdigit(s[i + c])) c++;
if(c == 0) {i ++; continue;}
string sub = s.substr(i, c);
ret += stoi(sub);
i += c;
}
return ret;
}
別解１
yasharさんより。４行目はなんのためなのか🤔
int sumUpNumbers(std::string s) {
int cur = 0;
int sum = 0;
s.push_back('@');
for(char c:s)
if(c>='0'&&c<='9')
cur = cur*10 + c-'0';
else
sum += cur, cur = 0;
return sum;
}
別解２
sir_ementalerさんより。またregexか
int sumUpNumbers(std::string inputString) {
std::regex expr("\\d+");
std::sregex_iterator it(inputString.begin(), inputString.end(), expr), end;
return std::accumulate(it, end, 0, [](int sum, const std::smatch& s) {
return sum + std::stoi(s.str());
});
}
55. Different Squares
Given a rectangular matrix containing only digits, calculate the number of different 2 × 2 squares in it.
Example:
For
matrix = [[1, 2, 1],
[2, 2, 2],
[2, 2, 2],
[1, 2, 3],
[2, 2, 1]]
the output should be
differentSquares(matrix) = 6.
自分の解答
以下の解答では大きいインプットに対して処理に時間がかかり過ぎてしまったためNGが出た。自分でもごちゃごちゃし過ぎていると思ったし他にやり方思いつかなかったのでこの問題は大人しくヒント(別解)見てときました。
int differentSquares(std::vector<std::vector<int>> m) {
if (m.size() < 2 || m.front().size() < 2) return 0;
vector<vector<vector<int>>> vvv(0, vector<vector<int>>(2, vector<int>(2, 0)));
for (int i = 1; i < m.size(); i++) {
vector<vector<int>> t;
for (int j = 1; j < m.front().size(); j++) {
t = vector<vector<int>>{{m[i-1][j-1], m[i-1][j]}, {m[i][j-1], m[i][j]}};
bool found = false;
for (vector<vector<int>> vv: vvv) if (vv == t) {found = true; break;}
if (!found) vvv.push_back(t);
}
}
return vvv.size();
}
別解
yasharさんより。そうじゃんset使えば自分で被りチェックする必要もなかった！！思い出せなかったの悔しい(´；ω；`)
int differentSquares(std::vector<std::vector<int>> m) {
set<int> se;
for(int i = 1; i < m.size(); ++i)
for(int j = 1; j < m[0].size(); ++j)
se.insert(m[i][j]+10*m[i-1][j]+100*m[i][j-1]+1000*m[i-1][j-1]);
return se.size();
}
std::set
手を動かしてさくさく理解する
C++ 順序付集合 std::set 入門
56. digitsProduct
Given an integer product, find the smallest positive (i.e. greater than 0) integer the product of whose digits is equal to product. If there is no such integer, return -1 instead.
Example:
For product = 12, the output should be
digitsProduct(product) = 26;
For product = 19, the output should be
digitsProduct(product) = -1.
自分の解答
pの一桁の約数を大きいものから、retの小さい桁から大きい桁へと順に追加していけば良いと考えました。
int digitsProduct(int p) {
if (p == 0) return 10;
if (p > 0 && p < 10) return p;
int ret = 0;
for (int i = 9; i > 1; i--) {
while (p % i == 0) {
if(!ret) ret = i;
else ret += i * pow(10, int(log10(ret)+1));
p /= i;
}
}
if (p != 1) return -1;
return ret;
}
別解
yasharさんより。コードは僕のよりずっと好きりしていて見やすい。でもこれだとループの回数結構多くならないのかな。。。？
int digitsProduct(int product) {
for(int i = 1; i < 100000; ++i)
{
int p=1, d = i;
while(d)
{
p *= d%10;
d /= 10;
}
if(p==product)
return i;
}
return -1;
}
57. File Naming
You are given an array of desired filenames in the order of their creation. Since two files cannot have equal names, the one which comes later will have an addition to its name in a form of (k), where k is the smallest positive integer such that the obtained name is not used yet.
Return an array of names that will be given to the files.
Example:
For names = ["doc", "doc", "image", "doc(1)", "doc"], the output should be
fileNaming(names) = ["doc", "doc(1)", "image", "doc(1)(1)", "doc(2)"].
自分の解答
うわなにこれって思いながらコード書いたら意外と解けた。
std::vector<std::string> fileNaming(std::vector<std::string> n) {
set<string> ms;
for (string &s: n){
int c = 1;
string t = s;
while (ms.find(t) != ms.end()) t = s + "(" + to_string(c++) + ")";
ms.insert(t);
s = t;
}
return n;
}
上位の人の解答見てたらみんな戻す用のvector.string作ってたんだけどそのほうがいいのだろうか？inputにconstついてないから気にせずリファレンス使ってしまった。
58. messageFromBinaryCode
You are taking part in an Escape Room challenge designed specifically for programmers. In your efforts to find a clue, you've found a binary code written on the wall behind a vase, and realized that it must be an encrypted message. After some thought, your first guess is that each consecutive 8 bits of the code stand for the character with the corresponding extended ASCII code.
Assuming that your hunch is correct, decode the message.
Example:
For code = "010010000110010101101100011011000110111100100001", the output should be
messageFromBinaryCode(code) = "Hello!".The first 8 characters of the code are 01001000, which is 72 in the binary numeral system. 72 stands for H in the ASCII-table, so the first letter is H.
Other letters can be obtained in the same manner.
自分の解答
初めてみるタイプの問題。5行目、ASCIIコード入れても勝手にcharに変換してくれしてくれるのか便利だ。なんならb.to_ulong()だけでも問題ないみたい。
std::string messageFromBinaryCode(std::string code) {
string ret = "";
for (int i = 0; i < code.size(); i += 8) {
bitset<8> b(code.substr(i, 8));
ret += char(b.to_ulong());
}
return ret;
}
std::bitset
The class template bitset represents a fixed-size sequence of N bits. Bitsets can be manipulated by standard logic operators and converted to and from strings and integers.
別解
yasharさんより。bitset使わなかった場合。
std::string messageFromBinaryCode(std::string s) {
string ans = "";
for(int i = 0; i < s.size(); i += 8)
{
char d = 0;
for(int j = 0; j < 8; ++j)
d = d*2 + (s[i+j]=='1');
ans.push_back(d);
}
return ans;
}
59. spiralNumbers
Construct a square matrix with a size N × N containing integers from 1 to N * N in a spiral order, starting from top-left and in clockwise direction.
Example:
For n = 3, the output should bespiralNumbers(n) =
[[1, 2, 3],
[8, 9, 4],
[7, 6, 5]]
自分の解答
ぐるぐるぐるぐるぐるぐる
std::vector<std::vector<int>> spiralNumbers(int n) {
vector<vector<int>> ret(n, vector<int>(n, 0));
int c = 1, s = 0, e = n - 1;
while (c <= n * n) {
for (int lr = s; lr <= e; lr++) ret[s][lr] = c++;
for (int tb = s + 1; tb <= e; tb++) ret[tb][e] = c++;
for (int rl = e - 1; rl >= s; rl--) ret[e][rl] = c++;
for (int bt = e - 1; bt >= s + 1; bt--) ret[bt][s] = c++;
s++, e--;
}
return ret;
}
欲を言えば行・列の位置でそのマスに入る数を求める式を見つけたかった。
60.Sudoku
Sudoku is a 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.
This algorithm should check if the given grid of numbers represents a correct solution to Sudoku.
数独って日本発祥だったのか
自分の解答
行、列、3*3マスの順に1~9の数字が含まれているかチェックしました。
bool sudoku(std::vector<std::vector<int>> g) {
set<int> ms;
for (vector<int> v: g) {
ms = set<int>(v.begin(), v.end());
if (ms.size() != 9) return false;
ms.clear();
}
for (int i = 0; i < g.size(); i++) {
for (int j = 0; j < g[0].size(); j++)
ms.insert(g[j][i]);
if (ms.size() != 9) return false;
ms.clear();
}
for (int i = 0; i < g.size(); i += 3)
for (int j = 0; j < g[0].size(); j += 3) {
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++)
ms.insert(g[i + r][j+ c]);
if (ms.size() != 9) return false;
ms.clear();
}
return true;
}
別解
sir_ementalerさんより。久しぶりになにが起きてるのか全くわからなくて笑った。
bool sudoku(std::vector<std::vector<int>> grid) {
for (int i = 0; i < 9; i++) {
int a = 0, b = 0, c = 0;
for (int j = 0; j < 9; j++) {
a ^= 1 << grid[i][j];
b ^= 1 << grid[j][i];
c ^= 1 << grid[i - i % 3 + j / 3][i % 3 * 3 + j % 3];
}
if (a != 1022 || b != 1022 || c != 1022)
return false;
}
return true;
}
まとめ
これにてCodeFights ArcadeモードIntro編おしまいです！
たかだか60問とはいえどれも解きごたえのある問題で楽しく勉強できました。最後の10問弱は特に悩みました。。
それと、やっぱり経験豊富なプログラマーさんのコードを見れると確実に知識が増えていく感じがして良いですね。ただ今のままではすぐに忘れてしまうので、今後も機会を見つけては問題演習していこうと思います。また、まだまだ理解が曖昧なもの(regexとかregexとかregexとか...)がたくさんあるのでそこの辺の勉強もおいおいしていきます。
そして次回からはUnityの勉強をしていく予定です。やっとゲーム作れる嬉しいーーー！！！
では最後まで読んでくれた方もそうでない方も、わざわざこの記事を見ていただきありがとうございました。ほとんど自分用の備忘録として使っているのであまり役に立つ記事にはならなかったかもしれませんが、少しでも何かの役にたったのなら幸いです。