GCJ – Cookie Clicker Alpha

Cookie Clicker Alpha, Qualification Round 2014.

This problem is also fairly simple, and we can solve it with a straightforward algorithm. Many thanks to both Dashamir and Karell who pointed out ways to simplify my original solution in the comments.

We want to decide for each farm if we’ll be able to win faster without buying the next farm (which will take X / rate time) or with buying the next farm (which will take C / rate time to save up cookies to buy the farm and a further X / (rate + F) time to win with the new, higher, production rate. If we don’t buy the farm, we report the current time plus the time to win with the current rate. If we do buy the farm, then we just repeat the step above after incrementing our rate and time to account for the new farm purchase.

def solve_case(case):
    C, F, X = case
    
    rate = 2.0
    time = 0.0

    while True:
        time_if_wait = X / rate
        time_if_buy = C / rate + X / (rate + F)
        if time_if_wait <= time_if_buy:
            return time + time_if_wait
        time += C / rate
        rate += F
Advertisements

GCJ – Magic Trick

Magic Trick, Qualification Round 2014.

Just as a reminder, all the Google Code Jam code and solutions I’m posting are based off of the template code I posted last year. It handles all the homework of reading and writing files properly and allows me to simply focus on solving the problem. I’ll generally only post the solve_case function and leave the rest to you.

As the first problem in the Qualification Round, this problem is more a test of basic coding ability than algorithm design. We’re given two 4 by 4 arrays and a row is chosen from each of them. The number of interest is supposed to be found in each of the chosen rows of the two arrays. So we want to find all numbers that are in both rows. We can do this quite easily using Python sets, although be careful of the indexing change from the row numbers we’re given (1 to 4) and the way Python indexes arrays (0 to 3). Once we have our list of potential numbers, then if there’s exactly one, that must be the one we want. If there’s more than two, the magician didn’t choose the arrays properly, and if there’s none, then the volunteer must be cheating.

def solve_case(case):
    ans1, grid1, ans2, grid2 = case
    
    valid = set(grid1[ans1-1]) & set(grid2[ans2-1])
    
    if len(valid) == 1:
        return valid.pop()
    elif len(valid) > 1:
        return "Bad magician!"
    else:
        return "Volunteer cheated!"

GCJ – Minesweeper Master

Minesweeper Master, Qualification Round 2014

There are a couple of key insights necessary to solve this problem. We know how many mines there will be and the size of the board, and we want to find some board state that would clear all the empty squares at once. It doesn’t have to be a likely state, it just has to be a valid state given the board size and mine count. So we can rearrange the board at will to find a state that will work.

The first insight is that for the board to clear in one click, all the empty spaces must be contiguous. Because a square can’t cascade to a square it’s not next to, we have to bunch all the empty squares together in one region.

The second insight is that this empty region should be up against the corner. Suppose we have a 2 by 2 clear area in a 4 by 4 region with mines surrounding it. If the empty region is in the middle or on the side, like this,

**** ****
*..* ****
*..* *..*
**** *..*

then all of the empty squares are next to a mine and they won’t cascade. If the empty region is in the corner,

****
****
..**
..**

then the corner square is next to the edge of the board rather than mines and will cascade, and we can win in a single click. So not only should our empty region be in the corner, but the clicked square should always be the corner square. Other squares might be able to cascade, but the corner one definitely will if others could.

With these insights, it’s now a matter of figuring out how to build our empty region and how to tell if it will cascade properly.

To build it, first note that if we can fill up a whole row or whole column of the board with mines, then we should do so. We’ll start up with the empty region filling the whole board, fill the shortest whole row or whole column available with mines, and repeat until we don’t have enough mines to keep going. At that point, we’ll have an empty rectangular region with the clicked square in the corner and some uneven number of mines to keep placing. If we have no mines, then we’ve finished our board and found a good position. We just need to check and make sure that the corner will cascade. If it won’t, then the board position doesn’t work with a single click and won’t be possible.

If we do still have mines to place, we’ll start placing them along the sides kitty corner to the clicked corner, like so:

c..**
...**
..***
*****

But we’re limited in how many we can place, because the rest of those rows and columns have to be cleared as well. We have to leave at least two empty squares at the edge of both the row and the column. With only a single empty square, the empty square next to it won’t cascade and we won’t clear the singleton:

c..**
..***
..***
*****

So the most we can place is the length of the empty space plus the width of the empty space minus five – two for the row, two for the column, and one for the overlap. If the number of mines to place is less than this, then we do so and report the board position. If not, then it’s impossible. That, along with some careful outlining of edge cases, will solve the problem.

def solve_case(case):
    R, C, M = case
    free = R * C - M
    
    def write_board(board):
        d = {0:'.', 1:'c', 2:'*'}
        return '\n' + '\n'.join([''.join([d[n] for n in r])for r in board]) + '\n'
    
    board = np.zeros((R, C), dtype=int)
    board[0,0] = 1
    
    while min(R, C) <= M:
        if R < C:
            board[:,C-1] = 2
            C -= 1
            M -= R
        elif C <= R:
            board[R-1,:] = 2
            R -= 1
            M -= C
    
    def cascades(board, r, c):
        rows = [i for i in (r-1, r, r+1) if (i >= 0 and i < board.shape[0])]
        cols = [i for i in (c-1, c, c+1) if (i >= 0 and i < board.shape[1])]
        for r in rows:
            for c in cols:
                if board[r,c] == 2:
                    return False
        return True
    
    if M == 0:
        if cascades(board, 0, 0) or free == 1:
            return write_board(board)
        else:
            return "\nImpossible"
    
    if M > (R + C - 5):
        return "\nImpossible"
        
    if R <= 2 or C <= 2:
        return "\nImpossible"
        
    fill_num = min(M, R - 2)
    board[(R - fill_num):,C-1] = 2
    M -= fill_num
    
    fill_num = min(M, C - 3)
    board[R-1,(C - fill_num - 1):] = 2
    M -= fill_num
    
    return write_board(board)

GCJ – Deceitful War

Deceitful War, Qualification Round 2014.

This was a fun one. There are three strategies that we need to figure out and take into account when we’re writing our solution:

  1. Ken’s optimal strategy for playing normal War.
  2. Naomi’s optimal strategy for playing normal War.
  3. Naomi’s optimal strategy for playing Deceitful War.

Let’s start with Ken’s strategy. As far as he knows, Naomi accurately tells him the weight of the block she has chosen, and then he gets to pick one of his blocks to play. Which block should he pick? Well, he always wants to win. So if he can, he should pick a block of his that is larger than Told_{Naomi} . Of those blocks that are larger, he should use the smallest, because that will allow the larger blocks to be used later and potentially win more rounds. If he has no blocks larger than Told_{Naomi} , then he should just use the smallest block he has. He can’t win this round, so he may as well avoid wasting any of his heavier blocks.

When Naomi plays normal War, she gets to pick the order in which she plays her blocks. Which block should she pick? We know that if she picks a block which Ken can beat, he’ll play the smallest block that can beat it. Otherwise, he’ll play his smallest block. She wants to force Ken to play his highest blocks, and the best way to do that is to play her highest blocks. So she’ll play her blocks in order from largest to smallest, giving her the best possible score without knowing the weights of Ken’s blocks.

But when Naomi plays Deceitful War she not only gets to choose the order of her blocks, she also gets to lie to Ken about the weight of her blocks. She can’t lie to win matches that she otherwise would have lost, because then Ken will figure out that she’s cheating. But she can lie to force Ken to use different, larger, blocks than he otherwise would have. Start with Naomi’s smallest block. If it’s smaller than Ken’s smallest block, then she can’t possibly win with it. But she can lie about its weight and force Ken to use his largest block to beat it, by telling Ken its weight is between his largest and his second-largest block. If it’s larger than Ken’s smallest block, then she can win by lying about its weight, telling Ken it’s bigger than his biggest block. Ken will then play his smallest block, and Naomi will win. Naomi can keep going through her blocks like this from smallest to largest, systematically lying and get the most wins possible without Ken finding out about her deceit.

def ken_choice(told_naomi, ken):
    for j in range(len(ken)):
        if ken[j] > told_naomi:
            return ken.pop(j)
    return ken.pop(0)

def normal_war(naomi, ken):
    score = 0
    for i in range(len(naomi))[::-1]:
        if naomi[i] > ken_choice(naomi[i], ken):
            score += 1
    return score

def deceitful_war(naomi, ken):
    score = 0
    for i in range(len(naomi)):
        if naomi[0] > ken[0]:
            score += 1
            ken.pop(0)
        else:
            ken.pop(-1)
        naomi.pop(0)
    return score

def solve_case(case):
    naomi, ken = case
    naomi.sort()
    ken.sort()
    normal = normal_war(naomi.tolist(), ken.tolist())
    deceitful = deceitful_war(naomi.tolist(), ken.tolist())
    return "%i %i" % (deceitful, normal)