# 13 Sun

## 오토마타와 컴파일러

### River Crossing : 최종 코드

{% embed url="<http://lg-sl.net/product/scilab/sciencestorylist/ALMA/readSciencestoryList.mvc?sciencestoryListId=ALMA2020010003>" %}

![](/files/-MORlpJC9hxX1WOC5TUN)

```
#
#   data : 2020.12.02
#   author : sangmandu at Dankook Univ.
#   program : river crossing
#   language : python
#

#
#   H : Human,  W : Wolf,   S : Sheep,  C : Cabbage
#   1 ... W eat S when there are only W and S
#   2 ... S eat C when there are only S and C
#   3 ... boat can be accommodate in up to 2 elements and Human essential
#   4 ... objective is that all element moves left to right
#

#
#   two lists that left and right
#   prior : keep from generating duplicate
#   dir : direction left to right or vice versa
#   record : the procedure to success(or failure)
#
#   failure     1) left check issue : collision with rule 1 or 2
#               2) left check issue : collision with rule 1 or 2
#               3) duplicate case : prevent that infinite loop
#   

# initialization
_left = ['H', 'W', 'S', 'C']
_prior = ''
_right = []
_dir = '>'
_record = []

# check rule 1 and 2
# when breaking rule then True else False
def checkIssue(rand):
    if len(rand) == 2 and 'S' in rand:
        if 'W' in rand or 'C' in rand:
            return True
    return False

stack = [(_left, _prior, _right, _dir, _record)]
while stack:
    left, prior, right, dir, record = stack.pop(0)
    print()
    print("selected element : ", left, prior, right, dir)
    print("and remained stack : ", stack)
    if not left:
        _record.append(record)
        continue

    if dir == ">":
        for ele in left:
            if ele == 'H':
                continue
            print(f"ele is {ele}")
            l, p, r, rec = left[:], prior[:], right[:], record[:]
            if ele == prior:
                print("ele == prior")
                continue
            l.remove(ele)
            l.remove('H')
            if checkIssue(l):
                print("left check issue")
                continue
            r.append(ele)
            r.append('H')
            if checkIssue(r):
                print("right check issue")
                continue
            memo = f"{ele} and human move from left : {left} to right : {right}"
            if memo in rec:
                print("duplicate issue")
                continue
            rec.append(memo)
            stack.append((l, ele, r, '<', rec))
            print(f"stack append {(l, ele, r, '<', rec)}")
    else:   # dir == "<"
        for ele in right:
            if ele == 'H':
                continue
            print(f"ele is {ele}")
            l, p, r, rec = left[:], prior[:], right[:], record[:]
            if ele == prior:
                print("ele == prior")
                continue
            r.remove(ele)
            r.remove('H')
            if checkIssue(r):
                print("right check issue")
                continue
            l.append(ele)
            l.append('H')
            if checkIssue(l):
                print("left check issue")
                continue
            memo = f"{ele} and human move to left : {left} from right : {right} "
            if memo in rec:
                print("duplicate issue")
                continue
            rec.append(memo)
            stack.append((l, ele, r, '>', rec))
            print(f"stack append {(l, ele, r, '>', rec)}")
        record.append(f"only human moves to left : {left} from right : {right} ")
        right.remove('H')
        left.append('H')
        if checkIssue(right):
            print("right check issue when human only on board")
            continue
        stack.append((left, '', right, '>', record))
        print(f"stack append that only human {(l, '', r, '>', rec)}")

print()
for idx, record in enumerate(_record, 1):
    print(f"#{idx} success case")
    for rec in record:
        print(rec)
    print()
```

중간 코드와는 비슷하면서 좀 다르다. (한번 갈아 엎어가지고...) 재귀 함수보다는 while / stack 방식이 변수 관리가 편한 것 같다. 함수 내에서 반복적으로 사용되는 변수는 l = left\[:] 와 같이 깊은 복사를 하려고 해도 잘 안된다. 결국 copy.deepcopy를 써야 되는데, 굳이 이렇게? 라는 생각이 너무 많이 든다. 함수 내에서는 재귀함수 또한 동일한 변수를 사용해서 그런게 아닐까 라는 추측은 있지만 확실한 이유는 모르겠다.

100줄 조금 넘게 작성된 코드. 좀 더 함수화하고 함축하여 코드를 줄일 수 있겠지만 애초에 메모리가 작아서 그럴 필요가 없다. 좀 더 직관적이어서 설명하거나 볼 때는 좋을 수 있다. 조금 더 수정하자면 prior 변수를 없애고 duplicate case에 추가할 수 있겠다.

간단한 알고리즘인데 생각보다 고민이 길었다. 주된 포인트는 left to right인지 또는 반대인지를 확인하고 이에 대해 각 left(or right)에서 다시 반대편으로 건너갈 요소를 고른다. 이 때 prior는 이전에 가져온 요소를 기억하여 다시 고르지 않도록 한다. checkIssue는 전달된 리스트에서 rule이 지켜지는지 확인하여 지켜지지 않았을 경우 True를 반환한다. (룰 확인을 위해 if문 쓸 때 not을 쓰기가 지저분 한것 같아 True를 반환하도록 했다...)&#x20;

각 case를 BFS 방식으로 접근하며 각 케이스마다 실패할 경우 실패 이유가 출력된다. 실패했을 경우에는 그 과정은 일부로 출력하지 않도록 했다. (안궁금해서?) 또한 성공할 경우를 마지막에 정리해서 다시 출력하도록 했다. 실제로도 2가지의 경우의 수가 존재하는데, 프로그램 또한 두 가지의 성공 케이스를 출력한다. 결과 150줄 정도 출력된다.&#x20;

![](/files/-MORpXptk06wl7N_a7l3)

BFS방식으로 출력하는 모습. 각 실패 케이스의 이유는 다음과 같다.

![](/files/-MORqbn54BHXZodoKUuk)

다음은 성공적으로 출력되는 모습.

![](/files/-MORqjmrzhsU-kOELNF8)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sangmandu.gitbook.io/til/2020/dec/13.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.