Fine-tuning CodeLlama-7B for Fortran Code Generation

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4 Output: 4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1 Output: 1

Constraints:

1 <= bad <= n <= 231 - 1

Note: This problem is from LeetCode.

✅ Compiled

❌ Executed

❌ Correct

program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer :: n, i, j
    logical :: bad
    real(kind=DP) :: x

    ! read input
    read (*, *) n

    ! solve problem
    do i = 1, n
        call isBadVersion(i, bad)
        if (bad) then
            write (unit=error_unit, fmt='(A, I0)') 'First bad version: ', i
            exit
        end if
    end do

contains

    subroutine isBadVersion(version, bad)
        implicit none
        integer, value :: version
        logical, intent(out) :: bad

        select case (version)
        case (1)
            bad = .false.
        case (2)
            bad = .true.
        case (3)
            bad = .false.
        case (4)
            bad = .true.
        case (5)
            bad = .true.
        case default
            bad = .false.
        end select
    end subroutine isBadVersion
end program main

stderr

At line 9 of file temp.f95 (unit = 5, file = 'stdin')
Fortran runtime error: End of file

Error termination. Backtrace:
#0  0x7e0f7c3c7960 in ???
#1  0x7e0f7c3c84d9 in ???
#2  0x7e0f7c61c17b in ???
#3  0x7e0f7c615684 in ???
#4  0x7e0f7c6162aa in ???
#5  0x5819373092a3 in MAIN__
#6  0x5819373093df in main

❌ Compiled

❌ Executed

❌ Correct

module isBadVersion

    implicit none

    interface
        function isBadVersion(version) result(is_bad)
            integer, intent(in) :: version
            logical :: is_bad
        end function isBadVersion
    end interface

contains

    function findFirstBadVersion(n) result(first_bad)
        integer, intent(in) :: n
        integer :: i
        logical :: is_bad

        first_bad = -1

        do i = 1, n
            is_bad = isBadVersion(i)
            if (is_bad) then
                first_bad = i
                exit
            end if
        end do
    end function findFirstBadVersion

end module isBadVersion

program main
    use isBadVersion
    implicit none

    integer :: n, first_bad

    ! Example 1
    n = 5
    first_bad = findFirstBadVersion(n)
    if (first_bad /= 4) then
        write (*,*) "Test 1 failed"
        stop 1
    end if

    ! Example 2
    n = 1
    first_bad = findFirstBadVersion(n)
    if (first_bad /= 1) then
        write (*,*) "Test 2 failed"
        stop 1
    end if

    ! Example 3
    n = 2
    first_bad = findFirstBadVersion(n)
    if (first_bad /= -1) then
        write (*,*) "Test 3 failed"
        stop 1
    end if

    ! Example 4
    n = 3
    first_bad = findFirstBadVersion(n)
    if (first_bad /= -1) then
        write (*,*) "Test 4 failed"
        stop 1
    end if

    ! Example 5
    n = 4
    first_bad = findFirstBadVersion(n)
    if (first_bad /= -1) then
        write (*,*) "Test 5 failed"
        stop 1
    end if

    ! Example 6
    n = 5
    first_bad = findFirstBadVersion(n)
    if (first_bad /= 4) then
        write (*,*) "Test 6 failed"
        stop 1
    end if

    ! Example 7
    n = 6
    first_bad = findFirstBadVersion(n)
    if (first_bad /= 4) then
        write (*,*) "Test 7 failed"
        stop 1
    end if

    ! Example 8
    n = 7
    first_bad = findFirstBadVersion(n)
    if (first_bad /= 4) then
        write (*,*) "Test 8 failed"
        stop 1
    end if

    ! Example 9
    n = 8
    first_bad = findFirstBadVersion(n)
    if (first_bad /= 4) then
        write (*,*) "Test 9 failed"
        stop 1
    end if

    ! Example 10
    n = 9
    first_bad = findFirstBadVersion(n)
    if (first_bad /= 4) then
        write (*,*) "Test 10 failed"
        stop 1
    end if

    write (*,*) "All tests passed"

end program main

stderr

temp.f95:6:29:

    6 |         function isBadVersion(version) result(is_bad)
      |                             1
Error: MODULE attribute of ‘isbadversion’ conflicts with PROCEDURE attribute at (1)
temp.f95:7:42:

    7 |             integer, intent(in) :: version
      |                                          1
Error: Unexpected data declaration statement in INTERFACE block at (1)
temp.f95:8:29:

    8 |             logical :: is_bad
      |                             1
Error: Unexpected data declaration statement in INTERFACE block at (1)
temp.f95:9:11:

    9 |         end function isBadVersion
      |           1
Error: Expecting END INTERFACE statement at (1)
temp.f95:14:53:

   14 |     function findFirstBadVersion(n) result(first_bad)
      |                                                     1
Error: Function result ‘first_bad’ at (1) has no IMPLICIT type
temp.f95:22:34:

   22 |             is_bad = isBadVersion(i)
      |                                  1
Error: Symbol at (1) is not appropriate for an expression
temp.f95:33:9:

   33 |     use isBadVersion
      |         1
Fatal Error: Cannot open module file ‘isbadversion.mod’ for reading at (1): No such file or directory
compilation terminated.

🌐 Data from online sources

def first_bad_version(n):
    left, right = 1, n
    while left < right:
        mid = left + (right - left) // 2
        if is_bad_version(mid):
            right = mid
        else:
            left = mid + 1
    return left

The algorithm used here is a binary search approach which starts with the range from the first to the last version. In each iteration, it takes the middle point and checks if it's a bad version by calling `isBadVersion()` API.

If the middle version is bad, this means that the first bad version is either the middle version or somewhere on the left side of the range. So, we update the right end of the range to the middle version.

If the middle version is not bad, the first bad version must be somewhere on the right side of the range. So, we update the left end of the range to the middle version + 1.

The loop will continue until the left and right pointers converge, indicating that we have found the first bad version. As a result, we return the value of the left pointer.

This algorithm has a complexity of O(log n), as it reduces the search range by half at each iteration hence minimizing the number of calls to the API.

🌐 Data from online sources

int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

The algorithm used here is a binary search approach which starts with the range from the first to the last version. In each iteration, it takes the middle point and checks if it's a bad version by calling `isBadVersion()` API.

If the middle version is not bad, the first bad version must be somewhere on the right side of the range. So, we update the left end of the range to the middle version + 1.

The loop will continue until the left and right pointers converge, indicating that we have found the first bad version. As a result, we return the value of the left pointer.

This algorithm has a complexity of O(log n), as it reduces the search range by half at each iteration hence minimizing the number of calls to the API.

First Bad Version