Ch5-Implementation

1. Implementation
2. Memory limitation

Q1.Up and Down

Q2.Time

Q3.Knight of Emperor

Q4.Game development

1. Implementation

Implementation in coding test is process what you think algorithm to code. Type of implementation problem is necessary when you solve any kind of problems. So most of algorithm books doesn’t mention about implementation problem but there are many questions for implementation therefore it is mentioned in this chapter. The people who join the coding competition say it is better that firstly solving implementation problem when you meet lots of difficult problems. I combine complete search problems with simulation problems in this chapter. Brute forcing problems is the method calculate every number of cases. Simulation problem is the type perform step by step algorithm which given from question. You need to know system environment in coding test so i firstly talk about limitation

2. Memory limitation

C/C++ need to set type and it has integer limitation of range but python automatically set the type. Python use list when there are lots of elements. there is memory limitation in coding test and it limit memory as 128 ~ 513 MB. Sometimes, programmer need to deal over 10 million of datas in the question. you need to take care about memory in this case. Python support automatic type declaration but datas use memory like following table.

Q1. Up and down

There is N x M matrix space and one person stand on it. This space is divided by rectangle of 1 X 1 size. Top left coordinate is (1,1) and Bottom right coordinate is (N,N). The person can move to up, down, right and left and starting point is always (1,1). The paper for moving plain is like following picture and rule is like this. and If person move to out of rectangle space, movement is canceled.

• L : Move one space to the left.
• R : Move one space to the right.
• U : Move one space to the up.
• D : Move one space to the down.

This photo is N = 5 of plan and map. The position is (1,2), (1,3), (1,4), (1,4), (2,4), (3,4) by plan. Final destination is (3,4). Make the program to printing final destination.

This problem is type of simulation because it moves point step by step. Some people say this problem to other word so just remember that simulation, implementation, and complete search are similar. Let’s make sentence

Here is flow chart

This is answer code

# Input N
n = int(input())
x, y = 1, 1
plans = input().split()

# Direction of L,R,U,D
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_types = ['L','R','U','D']

# Check the move plans
for plan in plans:
    # find cooridate after moving
    for i in range(len(move_types)):
       if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # Ignore when move out from space
    if nx > 1 or ny < 1 or nx > n or ny > n:
        continue
    # move
    x, y = nx, ny

print(x,y)

"""
5
R R R U D D
1 4
"""

Q2.Time

Make the program when input the integer N and return the number of every case include 3 from 00 hour 00 minutes 00 second to N hour 59 hour 59 minutes. Fore example, if you put 1, it include 3.

• 00 hour 00 minutes 03 second
• 00 hour 13 minutes 30 second

And this is wrong case because is doesn’t include 3.

• 00 hour 02 minutes 55 second
• 01 hour 27 minutes 45 second

solution

This question is solved when counting the number of every case because the second in a day is 86,400 second. In other word, the number of every case is 86,400 from 00 hour 00 minutes 00 second to 00 hour 00 minutes 00 second. so you can use string operator in python library and check the number 3 is included in time to solve the problem within 2 second.

The solution is checking the number 3 when increasing the one second. Whole of time is calculated by using triple for statement and it is hour, minutes, second which are 24 x 60 x 60. This problem can be brute forcing type. It is a representative problem in implement problem. but it has inefficient time complexity so it works well if there are many datas. Therefore, Brute forcing is efficient method when the datas are under million.

Get ConfidenceCoding’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This code check number 3 is included after changing time to string. For example, increasing 1 second from 00 hour 00 minutes 00 second to 23 hour 59 minutes 59 second and it combines hour, minutes and second. When checking 03 hour 20 minute 35 second. it will be ‘032035’ and check ‘3’ is in the string data. Let’s make sentence

This is answer code

# Input H
h = int(input())

count = 0 
for i in range(h+1):
    for j in range(60):
        for k in range(60):
        # count if it include '3'
            if '3' in str(i) + str(j) + str(k):
                count += 1
print(count) 

"""
5
11475
"""

Q3.Knight of Emperor

The garden in kingdom is 8 x 8 plane like chess board. Knight ride horse and he can move only L shape and can’t move out of garden. This is rule of moving knight.

1. Move two horizontal space and move one vertical space.
2. Move two vertical space and move one horizontal space.

Make the program which return the number of cases when knight move in 8 x 8 plane. Rows are presented by 1 to 8 and Columns are presented by a to h. For example, the number of case is ‘2’ when knight is in the ‘a1’. ‘a1’ is in corner of plane and knight can’t move out of garden.

1. Move two right way and move one space down. (c2)
2. Move two space down and move one right way. (b3)

If knight is in ‘c2’, the number of cases will be ‘6’.

Solution

This problem is similar like ‘up and down’ problem. you can check every route knight can move with paying attention to move out from garden. Knight can move 2 routes

1. Move two horizontal space and move one vertical space.
2. Move two vertical space and move one horizontal space.

Following this steps, direction which knight can move will be ‘ step = [ (-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1) ] ’. Positive numbers are right side or down. Negative numbers are left side or up.

Now if question give random position, add route from present position and check the position where in 8 x 8 plane. Loop statement can be used in this case.

This is flow chart

And this is code

# Input current position of knight
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# Define 8 direction where knight can move
steps = [(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)]

# Check the possibility knigh can move to 8 direction
result = 0 
for step in steps:
    # Check the position where knight will move
    next_row = row + step[0]
    next_column = column + step[1]
    # Count if it is possible to move
    if next_row >= 1 and next_row <= 8 and next_column >=1 and next_column <= 8:
        result += 1

print(result)

"""
a1
2
"""

Q4.Game development

Peter develop game NPC move in the map. Space is N x M rectangle shape made by 1 x 1 size. Each space in map is (A,B) and A is the number of space from north side, B is the number of space from west side. There are land and sea and NPC can’t move to see. The rule for moving NPC is like this.

1. Move first the left side from the current position.
2. If there is space NPC hasn’t been on left side, turn left and move one space to left side. If NPC already visited left space, just turn left and return first rule.
3. If NPC visited every four side or move to sea space, remain the direction, go back one space and return first rule.

There are four type of direction and ‘0’ is north, ‘1’ is east, ‘2’ is south, ‘3’ is north. Land will be presented by ‘0’ and Sea will be presented by ‘1’. Peter repeatedly perform this rules and test the program. Make the program return the number of space where NPC visited.

solution

This is typical type of simulation problem. It can be solved by implement without specific algorithm but this question has long sentence and it is not easy to make code. So it need to practice the problem many times.

It is efficient to decide direction is additional the list which are dx, dy. For example, if NPC face to north side, add dx[0], dy[0] for moving to north side. It means to move ( -1, 0 ). You can implement by using loop statement and it is initialized to 2-dimension list by using list comprehension syntax. It is efficient to use list comprehension syntax in python. You can check list comprehension syntax in Ch1. ‘global’ key word is used in method which is ‘turn_left()’ turn to left side. Because the variable ‘direction’ is defined where out side of function. Let’s look at sentence.

This is answer code

# Input N,M with space
n, m = map(int, input().split())

# Initialize map to 0 for saving visited position  
d = [[0] * m for _ in range(n) ]
# Input current position X, Y, direction of NPC
x, y, direction = map(int, input().split())
# Mark the current position.
d[x][y] = 1

# Input entire map information
array = []
for i in range(n):
    array.append(list(map(int, input().split() )))

# Define north, east, south, west
dx = [-1, 0, 1, 0 ]
dy = [0, 1, 0, -1 ]

# Turn left
def turn_left():
    global direction
    direction -= 1
    if direction == -1:
        direction = 3

# Start simulation
count = 1
turn_time = 0 
while True:
    # turn left
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    # After turning left, move to front side if it not visited yet
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
    # After turning left,if it is sea or already visited space
    else:
        turn_time += 1
    
    # If it can move any direction
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        # if it can move to back, move to back
        if  array[nx][ny] == 0:
            x = nx
            y = ny
        # if back is sea
        else:
           break
        turn_time = 0

print(count) 

"""
4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1


3
"""