성냥개비 압축

주간 챌린지 296

매주 Mohammad S. Anwar는 우리 모두가 두 가지 주간 작업에 대한 해결책을 생각해 낼 수 있는 주간 챌린지를 보냅니다. 내 솔루션은 먼저 Python으로 작성된 다음 Perl로 변환됩니다. 이는 우리 모두가 코딩을 연습할 수 있는 좋은 방법입니다.

도전, 나의 솔루션

작업 1: 문자열 압축

일

알파벳 문자열 $chars가 제공됩니다.

예제와 같이 실행 길이 인코딩으로 문자열을 압축하는 스크립트를 작성하세요.

압축 단위는 단일 문자이거나 개수 뒤에 문자가 올 수 있습니다.

보너스: 압축 해제 기능을 작성하세요.

내 솔루션

정규 표현식의 힘 덕분에 이는 매우 간단한 작업입니다. Python과 Perl 모두 대체 값이 함수가 되는 것을 허용합니다. 따라서 여러 문자를 숫자와 문자로 변환하는 sc라는 함수가 있습니다. 예를 들어 입력이 aaa인 경우 3a를 반환합니다.

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

그럼 이 함수를 필요에 따라 호출하면 되는 문제입니다.

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])+)', sc, s)

압축 해제 기능(Python에만 해당)도 비슷한 방식으로 작동합니다. 숫자 뒤에 문자가 오는 패턴을 취해 지정된 횟수만큼 반복되는 문자로 변경합니다.

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

명령줄에서 실행하려면 argparse 모듈을 사용하여 --decompress 옵션이 지정되었는지 확인합니다.

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("--decompress", help="decompress the input", action='store_true')
    parser.add_argument("str", help="the string to compress/decompress")
    args = parser.parse_args()

    if args.decompress:
        result = string_decompress(args.str)
    else:
        result = string_compress(args.str)
    print(result)

예

$ ./ch-1.py abbc
a2bc

$ ./ch-1.py aaabccc
3ab3c

$ ./ch-1.py abcc
ab2c

$ ./ch-1.py --decompress a2bc
abbc

$ ./ch-1.py --decompress 3ab3c
aaabccc

$ ./ch-1.py --decompress ab2c
abcc

작업 2: 성냥개비 사각형

일

정수 배열 @int가 제공됩니다.

주어진 배열 @ints에서와 같이 막대를 사용하여 하나의 정사각형을 만드는 것이 가능한지 알아보는 스크립트를 작성하세요. 여기서 $ints[ì]는 i번째 막대의 길이입니다.

내 솔루션

좀 길어질 것 같으니 단단히 준비하세요. 제가 가장 먼저 확인하는 것은 막대의 합이 4로 나누어진다는 것입니다. 그렇지 않다면 가능한 해결책이 없으며 false를 반환할 수 있습니다

또한 막대기 하나가 한 변보다 길지 않다는 것도 확인할 수 있습니다. 이런 일이 발생하면 false도 반환합니다.

이 두 가지 검사를 통해 모든 예는 올바른 결과를 제공합니다. 그러나 실제로는 그렇지 않은데 4 3 3 3 3이 참이라고 잘못 보고됩니다.

두 번째 시도

예시와 내 생각을 살펴보면서 양쪽에 일치하는 값 쌍을 일치시키는 것이 해결책이라고 생각했습니다. 예를 들어 3 4 1 4 3 1의 경우 3과 1의 막대기 두 쌍이 있어 4개가 됩니다. 이렇게 하면 4 3 3 3 3 문제가 해결됩니다. 왜냐하면 3개는 일치하는 항목이 없기 때문입니다.

하지만 막대가 4 4 3 1 2 1 1인 경우 한쪽에는 막대 3개(2 1개와 1 2개)를 사용하므로 이 방법은 작동하지 않습니다.

세 번째 시도

그래서 다음 시도는 좀 더 복잡했고 좋은 해결책이라고 생각했는데... 결국 그렇지 않았습니다. 이번 시도에서는 가장 긴 막대기로 시작했습니다. 측면의 길이가 아닌 경우 측면을 완성하는 데 필요한 다음으로 가장 긴 막대를 가져와 가능한 해결책이 없을 때까지 반복했습니다. 이 방법을 사용하면 다음과 같은 해결 방법이 적용됩니다.

• 4 4 3 1 2 1 1
• 9 5 4 3 3 3 3 3 3
• 9 6 3 5 4 3 3 3
• 9 6 3 5 4 3 3 2 1

9 5 3 1 5 2 2 3 3 3이 작동하지 않는다는 것을 깨닫기 전까지는 이것이 해결책이라고 생각했습니다. 첫 번째 변은 9이고, 다음 변은 5 3 1이며, 세 번째 변은 5 3이고 1이 없으면 실패합니다.

4번 시도

이 시점에서 저는 폭력을 사용하지 않고도 해결책을 찾는 것이 가능한지 궁금해지기 시작했습니다. 그래서 그 위에서 자고, 태블릿에 이것저것 적고(휴가 중이라 화이트보드를 사용할 수 없습니다), 다시 그 위에서 잤습니다. 내 결론은 재귀 함수를 사용하는 것이 유일한 해결책이라는 것입니다.

아마 제가 이 모든 것을 너무 많이 생각하고 있는 것일 수도 있고, 아니면 제가 방금 생각해낸 아주 간단한 해결책이 있을 수도 있습니다(지난주의 경우처럼).

최종 코드

아직도 읽고 계시나요? 수고했어요 :)

이 작업을 위해 make_side라는 재귀 함수가 있습니다. 남은 스틱 목록(Perl의 arrayref)과 필요한 길이를 가져옵니다. 그런 다음 나머지 스틱(가장 높은 스틱부터)을 통과합니다. 그러면 다음 세 가지 중 하나가 발생합니다.

• 스틱이 필요한 길이보다 길면 생략합니다.
• 필요한 길이이면 반품해드립니다.
• 짧으면 사용하고 또 다른 스틱을 사용하기 위해 함수를 다시 호출합니다. 호출은 사용한 스틱을 제거하고, 사용한 스틱의 길이만큼 필요한 길이를 줄입니다.

이 함수는 사용된 스틱 목록을 반환하거나, 유효한 스틱 조합이 발견되지 않은 경우 None(Perl에서는 undef)을 반환합니다.

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

퍼즐의 마지막 조각에서는 첫 번째 부분에서 언급한 검사를 수행한 다음(합은 4로 나눌 수 있고 막대는 한 변보다 길지 않음) 위 함수를 호출합니다. None을 반환하면 false를 반환합니다. 스틱을 모두 사용하면 true를 반환합니다.

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])+)', sc, s)

예

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

위 내용은 성냥개비 압축의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!