CS61A Spring 2025 Midterm1 결과

 

전반적으로 어렵지 않은 문제들이다. 풀 당시에는 어려웠는데, 끝나고보니까 결과가 좀 아쉽다.

직관적인 변수명이나 함수명을 쓰고 있어서 소위 말하는 꼬인 문제는 없었다.

다만 다른 environment diagram문제나, interpreter output 추적 문제들은 다른 학기 때보다 조금 더 복잡했다.

higher-order function이나 lambda function 비중이 높았던 시험이다.

---

1. (6.0 points) What Would Python Print?
Answer the questions about this code. No errors occur while it is executed.

def double(x):
    return 2 * x
def square(f):
    return lambda x: f(x) * f(x)
def inc(f):
    return lambda x: f(x + 1)
def triple(f):
    return lambda x: f(f(f(x)))
def put(x):
    return lambda f: f(x)

one = put(1)
triple(print)(5)

 

(a) (2.0 pt) What is displayed by the last line?

 

(b) (2.0 pt) What would be displayed by evaluating print(one(square(double)))

 

(c) (2.0 pt) What would be displayed by evaluating print(inc(put)(1)(triple(double)))

2. (8.0 points) Which One Complete the environment diagram below to answer the questons about the calls to print. Only the questions will be scored, not the diagram. Each call to print is evaluated once, and there are no errors caused by running this code.

x, y = 1, 2

def this(x):
    x = 3
    print(y)
    return 4

def which(x, f):
    def this(x):
        x = 5
        return y
    y = 6
    y = f(x)
    print(this(y))
    return lambda: (print(x) or y)

print(which(7, this)())

 

(a) (2.0 pt) What is displayed by the call to print on line 5?

 

(b) (2.0 pt) What is displayed by the call to print on line 14?

 

(c) (2.0 pt) What is displayed by the call to print on line 15?

 

(d) (2.0 pt) What is displayed by the call to print on line 17?

 

3. (13.0 points) Legit Digit

(a) (4.0 points) Implement all_digits, which takes a positive integer n and one-argument function cond that always returns True or False. It returns True if cond(d) returns True when called on every digit d in n, and False otherwise.

def all_digits(n, cond):
	"""Return whether cond returns true for every digit of positive n.
	>> odd = lambda d: d % 2 == 1
	>>> all_digits(123, odd) # not all digits are odd
	False
	>>> all_digits(357, odd) # all digits are odd
	True
	"""
    
	while n:
		if _______:
			_______
		n = n // 10
	return _______

i. (2.0 pt) Fill in blank (a).

ii. (1.0 pt) Fill in blank (b).

 

ii. (1.0 pt) Fill in blank (c).

 

문제에서 든 cond의 예시로 odd는 해당 digit이 홀수일 경우 True, 홀수가 아닐 경우 False를 반환하는 람다 함수로 정의되어 있다. 

 

all_digits(123, odd)를 예시로 들어보자.

 

while n:은, n이 정수 0 이상일 때 반복문을 시행한다. 뒤에 구현해야할 내용은 무엇인지 생각해보자. 

우선, digit 하나하나를 분리시킬 필요가 있다. 밑에 n = n // 10 을 보아하니, n의 뒷자리를 하나씩 줄이고 있는 로직을 사용중이다. 처음 n은 123이고, if문을 거치고 나선 n은 12로 재할당될 것이다. 그후 또 if문을 거치면 n은 1로 재할당되고, 이를 또 반복하면 끝내 n은 0이 되어 while문을 탈출한다.

해당 함수는, n의 일의 자릿수를 차례대로 홀수인지 판단하고자 한다.

 

123의 경우, 3은 홀수지만, 십의 자리 2는 짝수다. 즉, 2가 나온 순간부터 함수는 이미 해당 123의 전체 digit은 홀수로 이루어진 숫자가 아님을 발견할 것이다. 즉, 백의 자리 숫자인 1을 확인할 필요가 없다.

 

우리가 구현해야하는 기능은 크게 2가지겠다.

1. n의 일의 자리 숫자가 짝수라면, 해당 함수를 즉시 종료한다. 

짝수가 아닌 홀수라면 if문을 벗어나 n의 digit을 줄여 재할당할 것이다.

2. n의 모든 digit이 홀수라면, 해당 함수를 True로 반환한다.

 

My code:

def all_digits(n, cond):
	"""Return whether cond returns true for every digit of positive n.
	>> odd = lambda d: d % 2 == 1
	>>> all_digits(123, odd) # not all digits are odd
	False
	>>> all_digits(357, odd) # all digits are odd
	True
	"""
    
	while n:
		if cond(n) == False:
			return False
	    n = n // 10
	return True

 

(b) (3.0 points)

Definition. A prefix of a positive integer n is the value of n//pow(10, p) for some non-negative integer p. For example, 3456 has prefixes 3456, 345, 34, 3, and 0. Implement prefix_digits, which takes a positive integer n and a one-argument function cond that always returns True or False. It returns the largest prefix of n for which cond returns True when called on every digit of the prefix. You may call all_digits and process.

def process(n, check):
    """A function to help implement prefix_digits."""
    while n:
        if check(n):
            return n
        n = n // 10
    return 0

def prefix_digits(n, cond):
    """Return the largest prefix of positive n for which cond returns true for every digit.
    >>> odd = lambda d: d % 2 == 1
    >>> prefix_digits(94720, odd)
    9
    >>> prefix_digits(919321, odd)
    9193
    >>> prefix_digits(2025, odd)
    0
    >>> prefix_digits(20252025, lambda d: d < 4)
    202
    >>> prefix_digits(20252025, lambda d: True)
    20252025
    """
    return process(n, lambda k: _______ )

 

문제 이해가 어려울 땐 예시 하나를 잡읍시다.

prefix_digits(94720, odd) 를 예시로 들면, 94720의 prefix는 94720, 9472, 947, 94, 9로 이루어져있다.

이로 알 수 있는 점은, prefix는 일의 자리를 순차적으로 없애고 있음을 확인.

 

문제에서 주어진 process 함수는 n 정수와 check함수 이렇게 두 인자를 받는 고차 함수다.

 

앞서 구현해둔 all_digit을 이용해서 함수를 만들어야하는데 어떻게 하면 만들 수 있을까?

all_digit 함수는 모든 digit이 홀수이거나 짝수여야 True를 반환하고, 하나의 digit이라도 다를 경우 False를 반환하는 함수다.

 

process 함수의 if check(n): 에서 check는 함수를 인풋으로 받은 함수 인자다. 여기에 all_digit이 사용되면, 모든 digit이 홀수라고 가정했을 때 True를 반환해서 if문이 작동된다. 좀 더 구체적으로, 

n = 94270일 때, False가 반환되며 if문을 스킵하고, n = n // 10을 만나 n = 9427로 재할당된다.

n = 9427일 때, False가 반환되며 if문을 스킵하고, n = n // 10을 만나 n = 942로 재할당된다.

n = 942일 때, False가 반환되며 if문을 스킵하고, n = n // 10을 만나 n = 94로 재할당된다.

n = 94일 때, False가 반환되며 if문을 스킵하고, n = n // 10을 만나 n = 9로 재할당된다.

n = 9일 때, True가 반환되며 if문에서 해당 n값인 9를 반환한다. 모든 digit이 홀수인 순간이기 때문이다.

 

그럼, prefix_digits의 return문에선 process 함수를 사용하고 있는데, 이 process 함수의 리턴값이 9가 되며, prefix_digits 또한 해당 9를 사용자에게 리턴해준다. 

 

이제 코드를 구현해보자.

process 함수의 if check(n)에서 n은 lambda(k)의 k로 전달된다. 그렇기에 all_digits(k, cond)라면, 해당 인자값을 받을 수 있다. 

 

My code:

def process(n, check):
    """A function to help implement prefix_digits."""
    while n:
        if check(n):
            return n
        n = n // 10
    return 0

def prefix_digits(n, cond):
    """Return the largest prefix of positive n for which cond returns true for every digit.
    >>> odd = lambda d: d % 2 == 1
    >>> prefix_digits(94720, odd)
    9
    >>> prefix_digits(919321, odd)
    9193
    >>> prefix_digits(2025, odd)
    0
    >>> prefix_digits(20252025, lambda d: d < 4)
    202
    >>> prefix_digits(20252025, lambda d: True)
    20252025
    """
    return process(n, lambda k: all_digits(k, cond))

 

(c) (6.0 points)

Re-implement prefix_digits, which takes a positive integer n and a one-argument function cond that always returns True or False. It returns the largest prefix of n for which cond returns True when called on every digit of the prefix. You may not call all_digits or process.

def prefix_digits(n, cond):
    """Return the largest prefix of positive n for which cond returns true for every digit.
    >>> odd = lambda d: d % 2 == 1
    >>> prefix_digits(94720, odd)
    9
    >>> prefix_digits(919321, odd)
    9193
    >>> prefix_digits(2025, odd)
    0
    >>> prefix_digits(20252025, lambda d: d < 4)
    202
    """
    k = 0
    while n >= ________:
        if cond(_______):
            k += 1
        else:
            n = n // 10
            _______
    return n

 

prefix_digits, 똑같은 함수를 구현하는데, 이번에는 all_digits와 process 함수를 사용하지 않아야 한다.

로직은 이해했으니, 구현 단계를 바로 보면,

 

k = 0은 뭘 위한 것인지부터 알아야한다. 일단 아무런 단서가 없으니, 차례대로 주어진 코드들을 보자.

while n >= __ 으로 반복문을 돌리고 있다. 해당 반복문 안엔 if cond()를 사용함으로써, if문으로 해당 digit이 홀수인지 아닌지를 파악하고 있다. 

if cond()가 true일 때, k를 +1하고 있는 이유는 뭘까? cond가 odd라고 가정하고:

해당 digit이 홀수일 때 k에 +1,

해당 digit이 홀수가 아니면 n의 일의 자릿수를 하나 없앤다.

인 것 같다. 

 

똑같이 prefix_digits(94720, odd)를 예시로 들자.

k = 0, n  = 94270일 때, 홀수가 아니니까 n = n // 10을 만나게 되어 n = 9427로 재할당된다.

k = 0, n = 9427일때, 홀수니까 k += 1를 만나게 되어  k = 1로 재할당된다.

k = 1, n = 9427일때, 우린 이전 단계에서 7을 확인했으니 이젠 2 digit이 홀수인지 확인해야한다. 이때, k를 사용하는 모양이다.

우리가 추측해볼 수 있는건, k를 이용해 n의 자릿수를 이동중이라는 점이다.

9427인 n에서 942로 만들려면 어떻게 코드를 작성하면 될까?

n // pow(10, k)를 사용하면, n은 942가 된다. 마찬가지로, k = 0이였을 때 n이 94270인 것도 말이 된다.

이어서,

k = 1, n = 9427일 때, n // pow(10, k)로 n은 942일 때 홀수가 아니므로, n = 942로 재할당된다.

k = 1, n = 942일때, n // pow(10, k)로 n은 94일 때 홀수가 아니므로 n = 94로 재할당된다.

k = 1, n = 94일 때 n // pow(10, k)로 n은 9일 때 홀수니까 k = 2가 된다.

k = 2, n = 94일때, n // pow(10, k)를 거치면 0이 된다.

그런데, 이 k와 n의 값은 아무런 의미가 없는 값임을 확인했다. n // pow(10, k)이 아닌 다른 로직을 구현해야했다.

 

다시 생각해보자. k는 그저 자릿수 이동을 위한 변수다. 때문에 우리가 중요하게 추적해야하는 변수는 n이다.

n의 모든 digit이 홀수일 때, 해당 n을 반환해야하는 것이다.

n // pow(10, k) 로직을 바꿔보자. digit 하나하나를 뜯어볼 수 있도록, n // pow(10, k) % 10을 사용하면 어떨까?

 

k = 0, n  = 94270일 때, n // pow(10, k) % 10은 일의 자리인 0을 확인해준다. 0은 홀수가 아니니까 n = 9427이된다.

k = 0, n = 9427일 때, n // pow(10, k) % 10을 만나 일의 자리인 7을 확인해준다. 7은 홀수니까 k = 1이 된다.

k = 1, n = 9427일 때, n // pow(10, k) % 10을 만나 일의 자리인 2를 확인해준다. 2는 홀수가 아니니까 n = 942가 된다.

k = 1, n = 942일 때, n // pow(10, k) % 10을 만나 일의 자리인 4를 확인해준다. 4는 홀수가 아니니까 n = 94가 된다.

k = 1, n = 94일 때, n // pow(10, k) % 10을 만나 일의 자리인 9를 확인해준다. 9는 홀수니까 k = 2가 된다.

k = 2, n = 94인 상황이다. 이제, 모든 digit을 돌아봤으니 나는 반복문을 끝내고 싶다. 어떻게 해야 while문을 탈출할 수 있을까?

n >= pow(10, k)를 이용하면 94는 100보다 작으니까 while문을 벗어날 수 있음을 확인했다.

우리가 반환하고 싶은 값은 94가 아니라 9인 상황인데, n에는 94가 할당되어 있는 상태다. else문에서 특정 로직이 필요하다. else문은 홀수가 아닐 때 구현되는 구문이다. 

여태 해당 else문의 일부를 스킵했기 때문에, 처음부터 다시 로직을 되돌아봐야한다 ㅠㅠ 

우리가 목표를 세워야할 부분은, n이 94가 아닌 9에 도달해야하는 것.

그래도 나머지 빈칸들을 채웠으니, 다시 구현해보자.

 

k = 0, n  = 94270일 때, n >= pow(10, k)를 만나 n은 0보다 큰 수 임을 확인했다.

n // pow(10, k) % 10은 일의 자리인 0을 확인해준다. 0은 홀수가 아니니까 n = 9427이된다. 이때 ___ 해야한다.

(일부러 빈칸으로 냅둔 상태다)

k = 0, n  = 9427일 때, n >= pow(10, k)를 만나 n은 0보다 큰 수 임을 확인했다.

n // pow(10, k) % 10은 일의 자리인 7을 확인해준다. 0은 홀수니까  k = 1 이된다.

k = 1, n  = 9427일 때, n >= pow(10, k)를 만나 n은 10보다 큰 수 임을 확인했다.

n // pow(10, k) % 10은 일의 자리인 2를 확인해준다. 2는 홀수가 아니니까 n = 942이가 된다. 이때 ___ 해야한다.

이대로 가면 위 로직과 다를게 없다. n이 94가 아닌 9에 도달하게 하려면, else문에서 k를 초기화 시키면 되지 않을까?

___ 칸에 k = 0을 넣어보자.

k = 0, n  = 942일 때, n >= pow(10, k)를 만나 n은 0보다 큰 수 임을 확인했다.

n // pow(10, k) % 10은 일의 자리인 2를 한 번 더 확인해준다. 2는 홀수가 아니니까 n = 94가 된다. 이때 k = 0 해야한다.

k = 0, n  = 94일 때, n >= pow(10, k)를 만나 n은 0보다 큰 수 임을 확인했다.

n // pow(10, k) % 10은 일의 자리인 4를 확인한다. 4는 홀수가 아니니까 n = 9가 된다. 이때 k = 0 해야한다.

k = 0, n  = 9일 때, n >= pow(10, k)를 만나 n은 0보다 큰 수 임을 확인했다.

n // pow(10, k) % 10은 일의 자리인 9를 확인한다. 9는 홀수니까, k = 1이 된다.

k = 1, n  = 9일 때, n >= pow(10, k)를 만나 n은 10보다 작아서 반복문을 탈출한다.

모든 digit을 돌아봤고, 해당 n값을 반환하겠다.

 

사실 내가 사용한 예시가 좋지 않았다고 생각한다.

94720 대신 919321을 이용했다면 좀 더 원활하게 풀 수 있었을 것 같은 문제다.

해당 문제에서 전체 감점을 당했지만 난 괜찮다^^. ㅗ맙다 버클리

 

4. (4.0 points) Hailstone Returns

Definition. A hailstone sequence is formed by picking a positive integer n as the start then repeatedly updating n until it is 1 using this rule: if n is even, divide it by 2; if n is odd, multiply it by 3 and add 1. Implement hailstone, which prints each update in a hailstone sequence by displaying: the update number (counting up from 1), the current n, an -> arrow symbol, and the updated n. This implementation may not be possible using the template. If that’s the case, respond Impossible to the following questions.

def hailstone(n):
    """Print numbered updates in the hailstone sequence.
    >>> hailstone(10)
    1 10 -> 5
    2 5 -> 16
    3 16 -> 8
    4 8 -> 4
    5 4 -> 2
    6 2 -> 1
    """
    def f():
        if n % 2 == 1:
            m = 3 * n + 1
        else:
            m = n // 2
        _______
        _______
    k = 1
    while n > 1:
        k, n = k + 1, f()

hailstone 함수 안에 f()라는 함수가 정의되어 있다. 

 

f() 함수 안에 있는 if문을 보면:

n이 홀수일 때 if n % 2 == 1를 만나 m = 3 * n + 1

n이 홀수가 아니면 m = n // 2

 

f() 함수 정의문을 벗어나면 k = 1로 k를 initialize하고 있다. 이 k는 아마 hailstone이 몇번 째 hailstone인지 나타내주는 지표로 사용될 k일 것 같다. 

while문은 n이 1보다 클 때 작동된다. 반복문 안에서는 다중 할당문이 사용되고 있는데:

k = k + 1 (k는 앞서 말했듯이 hailstone 횟수 추적용)

n = f() (f함수를 호출해서 n에 할당 중이다)

 

앞서 살펴본 f() 내부 코드가 발동될 것이고, if-else문을 벗어나 우리가 작성할 수 있는 코드는 print문일 것이다. n이 10일 때를 예시로 들어보면, 우리가 작성할 수 있는 print문은:

print(k, n, '->', m) 이면 될 것 같다. k - 1을 할 필요없는 이유는, 다중할당문이기에 f() 내부 코드에서 사용될 k는 k+1이 적용되기 전의 k이기 때문이다. 

 

그 아래 빈칸엔 무슨 코드가 올 수 있을지 생각해보자. 현재 hailstone 함수 내부에는 return문이 존재하지 않는다.

해당 빈칸이 그 자리가 될 것이다. f()함수가 m값을 리턴해야, 다중할당문에서 n이 새로운 값으로 재할당되는 것이 가능하다. 그럼, return n = m 이면 되지 않을까?

 

중간 단계를 좀 생략하고, k = 5, n = 2, m = 2 단계부터 살펴보자.

while문으로 인해:

k = 6이 되고, n은 짝수라서 m = 1이 된다. 리턴문으로 인해 n = 1이 할당되어 해당 n값을 리턴한다. 

n이 1이 되었으니, while문 조건이 false가 되며 반복문이 종료된다.

사실, return m만 해도 다중할당문에 의해 n에 해당값이 전달된다. return n = m이 아닌 return m이 맞는 답이겠다.

 

My code:

def hailstone(n):
    """Print numbered updates in the hailstone sequence.
    >>> hailstone(10)
    1 10 -> 5
    2 5 -> 16
    3 16 -> 8
    4 8 -> 4
    5 4 -> 2
    6 2 -> 1
    """
    def f():
        if n % 2 == 1:
            m = 3 * n + 1
        else:
            m = n // 2
        print(k, n, '->', m)
        return m
    k = 1
    while n > 1:
        k, n = k + 1, f()

 

5. (4.0 points) It Takes Two

Implement at_least_two, which takes three arguments. It returns True if at least two of them are true values and False otherwise. The built-in bool function takes one argument and returns True if it is a true value and False if it is a false value.

def at_least_two(x, y, z):
    """Returns whether at least two of the arguments are true values.
    >>> at_least_two(1 + 1, 3 + 3, 5 + 5)
    True
    >>> at_least_two(1 + 1, 3 - 3, 5 + 5)
    True
    >>> at_least_two(1 - 1, 3 + 3, 5 + 5)
    True
    >>> at_least_two(1 - 1, 3 + 3, 0)
    False
    >>> at_least_two(1 - 1, 0, 0)
    False
    """
    if _______:
        return _______
    else: 
        return _______

(a) (2.0 pt) Fill in blank (a)

 

(b) (1.0 pt) Fill in blank (b). Select all correct answers.

 

(c) (1.0 pt) Fill in blank (c). Select all correct answers

 

if-else문만 구현하면 끝나는 쉬운 문제다.

순서대로, x, 가 만약 0이 아닌 정수라면 y,z를 고려했을 때 둘중 하나라도 0이 아닐 때 True값을 반환할 것이다.

첫번째 if문에서, x가 true값을 가지는지 확인하고, return문에서 y or z 연산자를 사용하면 된다.

다만, bool()을 사용하지 않으면 그냥 숫자를 리턴하기 때문에 bool(y or z)만이 사용 가능하다.

 

else문에서 고려해야하는건 뭘까?

x가 true가 아니라는건, 해당 함수가 True값을 반환하기 위해선 y와 z 모두 True여야한다.

직관적으로, and 연산자가 필요한 상황임을 알 수 있다.

보기들 중 가능한 정답은 bool(y and z)다.

 

 

---

B.A. in Statistics at University of California, Berkeley