iT邦幫忙

5

[Google Code Jam][資格賽]Saving The Universe Again(再次拯救宇宙)

HIHI,今天來分享個Google Code Jam 2018比賽的題目解法。不過因為時間的問題,所以我解完一題才會PO上來,所以這個系列大概會有四篇以上,還有因為其實我對C++不太熟,所以就用目前比較熟悉的JavaScript解出邏輯,希望各位大大不要介意。

首先是資格賽第一題「Saving The Universe Again(再次拯救宇宙)」:

故事背景是有個外星機器人在攻擊宇宙,而我們必須阻止他。機器人的初始攻擊力為1,攻擊方式是使用一串指令做執行,指令由兩個動作所組成第一個是「C(充電)」他會使機器人的攻擊力翻倍,第二個是「S(射擊)」機器人會以目前的攻擊力做出等同數值的傷害。

舉例來說,如果機器人的的指令是CSCCS,他所執行的動作會是以下:
1.C:充電,將初始攻擊力1翻倍變為2
2.S:射擊,將造成目前攻擊力2點傷害
3.C:充電,將目前攻擊力2翻倍變為4
4.C:充電,將目前攻擊力4翻倍變為8
5.S:射擊,將造成目前攻擊力8點傷害
所以可以得知以上的指令共會造成10點傷害。

而現在的宇宙科學家有發明出一個能夠承受傷害的盾牌,但是機器人的指令造成的傷害可能會比盾牌能夠承受的傷害還高,所以在指令運行之前,我們能夠去破解指令,讓機器人造成的傷害能夠讓盾牌承受住並保護宇宙。破解的規則是交換相鄰的指令,例如上述的CSCCS,他可以透過交換第一個和第二個指令來讓指令變為SCCCS,如此一來就能讓傷害從10減少為9,接著又可以再交換第四個和第五個指令變成SCCSC,這樣又能讓傷害從9減少為5,透過不斷地破解讓盾牌能夠承受住機器人的傷害,不過為了避免機器人發現,破解的次數越少越好。

所以這一題求的是,在機器人的一串指令下,確保盾牌能夠承受傷害的最少破解次數是多少?

輸入的方式,第一行是指令數,接著輸入的規則是盾牌血量和指令,以下例子:
3
1 CS
2 CS
1 SS

輸出的結果為:
Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE

第一個指令:盾牌血量為1,指令為CS,先充電再射擊會讓總傷害為2,所以透過把他們交換為SC,讓傷害從2減少為1,成功抵擋攻擊,因為交換了一次,所以是1。
第二個指令:盾牌血量為2,指令為CS,先充電再射擊總傷害為2,因此不用交換盾牌就能承受了,所以是0次。
第三個指令:盾牌血量為1,指令為SS,不論怎麼交換,總傷害都會是2,因此盾牌絕對承受不了這次攻擊,所以是IMPOSSIBLE。

好的,那以下是我的程式碼:

<html>
    <body>
        <!--透過textarea輸入多行指令-->
        <textarea id="input" rows="10" cols="50"></textarea>
        <!--透過button執行事件-->
        <input type="button" value="送出" onclick="send()"/>
    <script>

    function send(){
        //取得攻擊指令
        let word = document.getElementById('input').value;
        //總共有幾行指令
        let rowCount = word.split('\n').length-1;
        //用來裝每次攻擊的結果
        let arrResult = new Array();

        //開始讀取指令(把盾的血量和攻擊指令傳到處理的函式)
        for(let i=1;i<=rowCount;i++){
            //取這一行的開始和最後位置
            let first = findIndex(word,'\n',i);
            let last = findIndex(word,'\n',i+1) || word.length;
            //擷取那一行的字串,開始擷取的地方+1才不會截到斷行
            let rowStr = word.slice(first+1,last);
            //把那行的字串用空白分割開來,因為前面是血量,後面是指令
            let hp = rowStr.split(' ')[0];
            let command = rowStr.split(' ')[1];
            //送去判斷能不能擋下這次攻擊,然後要交換幾次
            arrResult[(i - 1)] = 'Case #' + i + ': ' + handleCommand(hp, command);
            //印出結果
            console.log('Case #' + i + ': ' + handleCommand(hp, command));
        }
    };

    //處理指令
    //hp:盾牌血量 command:攻擊指令
    function handleCommand(hp, command) {
        //先計算目前傷害值
        let killValue = getKillValue(command);
        //計算次數
        let count = -1;
        do {
            if (count === -1) { //第一次先單純判斷「有沒有可能達成」或「有沒有需要換位置」
                //如果他目前傷害值小於盾的血量就不需要換
                if (Number(killValue) <= Number(hp)) {
                    return '0';
                }
                //如果他的S的數量大於盾的血量就沒不可能達成
                if ((command.replace(/C/g, '')).length > Number(hp)) {
                    return 'IMPOSSIBLE';
                }
                count = 0; //下一次的迴圈就跑else
            }
            else { //第二次開始要換位置
                count += 1; //先計算次數
                //改變位置,讓他去跑看看
                command = revisionCommand(command);
            }
        }
        while (hp < getKillValue(command)); //如果總傷害量超過血量就繼續跑迴圈

        //過了以後回傳次數
        return count;

    };

    //計算傷害值
    //command:指令
    function getKillValue(command) {
        //規則是 C:充電 S:射擊
        let killValue = 0; //總傷害量
        let basedKill = 1; //目前傷害量

        for (let i = 0; i <= command.length - 1; i++) {
            switch (command[i]) {
                case "C": { //集氣
                    basedKill *= 2;
                    break;
                };
                case "S": { //加上目前傷害值
                    killValue += basedKill;
                    break;
                };
            };
        };

        return killValue;
    };

    //改變指令
    //command:當前攻擊指令
    function revisionCommand(command) {
        //規則是用最少的移動來讓指令傷害不超過盾牌血量
        //也就是說在C是充能和S是攻擊的狀況下,可以推出以下結論
        //一、只要C後面沒有S就等同不會造成更高的傷害,所以就在每一次交換的時候把C往S後面移動
        //二、由於要在最少次數達成,所以優先處理最後出現的CS,因為CS出現在越後面代表傷害越高

        //尋找指令中最後出現的CS然後將他們換位置
        let lastCS = command.lastIndexOf('CS');
        //把指令放進陣列中
        let arrCommand = command.split('');
        //把原本位置中的C換成S,S換成C
        arrCommand[lastCS] = 'S';
        arrCommand[lastCS + 1] = 'C';

        //把更改過位置的陣列轉成字串後回傳
        return arrCommand.join('');
    }

    //尋找字串
    //str:被尋找的字串  findStr:要尋找的字串  findNum:要找第幾個出現的字串
    function findIndex(str, findStr, findNum) {
        //先取得第一次出現的位置
        let index = str.indexOf(findStr);

        //之後去跑看要找第幾次出現的地方
        for (let i = 0; i < findNum - 1; i++) {
            //從上一次出現的地方開始找
            index = str.indexOf(findStr, index + 1);
        }

        //如果是-1代表沒找到就回傳undefined
        if (index === -1) {
            index = undefined;
        }

        //回傳最後一次出現的位置
        return index;
    };
    </script>

    </body>
</html>

以上是我的程式碼,結果如下:
https://ithelp.ithome.com.tw/upload/images/20180422/20106935nzZH7LnDDX.jpg

因為我也沒有其他指令能夠測試到底正不正確了,所以如果以上有錯誤的地方,或是有哪裡覺得怎麼寫會更好,再麻煩各位大大告訴我,我會盡速改進,謝謝大家。


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
小碼農米爾
iT邦高手 1 級 ‧ 2018-04-28 13:49:05

參加 Code Jam 各種程式語言都可以,
我用 C++ 只是比較熟悉而已,
這個禮拜比較忙,現在才來看大大的程式。/images/emoticon/emoticon02.gif

神Q超人 iT邦研究生 5 級 ‧ 2018-05-02 13:36:45 檢舉

可是用JavaScript感覺會比較容易,因為他的現有function應該比C++多很多吧,哈哈。

我要留言

立即登入留言