태그 보관물: data-structures

data-structures

우리는 친구가되어야합니까? 당신의 임무는 Bacefook이 새로운 제안 시스템을 구현하도록

이것은 주로 데이터 구조 에 중점을 둔 질문입니다.

소개

Bacefook은 사람들이 더 친해지기를 원합니다! 그래서 그들은 친구를 제안하는 새로운 시스템을 구현하고 있습니다! 당신의 임무는 Bacefook이 새로운 제안 시스템을 구현하도록 돕는 것입니다.

명세서:

프로그램은 FRIEND, SUGGEST및 의 세 가지 유형의 명령을 지원하는 REPL (read-eval-print loop)이어야합니다 KNOW.

FRIEND X Y-되도록 지정 X및 Y소셜 네트워크에서 친구입니다.

  • X가 Y와 친구 인 경우 Y는 X와 친구입니다

  • 가능하지만 출력 할 필요는 없습니다.

  • X는 항상 X와 친구입니다

KNOW X Y -X와 Y가 친구이면 거짓 값을 출력하고, 그렇지 않으면 거짓

  • KNOW X X 항상 진실한 가치를 산출 할 것입니다

SUGGEST X Y-X와 Y가 친구라면 거짓 값을 출력하고, 그렇지 않으면 거짓 값을 출력합니다. 다음과 같은 경우 X와 Y는 친구 여야합니다.

  • X와 Y는 친구가 아닙니다

  • X와 Y는 공통 친구가 1 명 이상입니다.

당신은 대체 할 수 있습니다 FRIEND, SUGGEST그리고 KNOW자신의 문자열,하지만 당신은 당신이 각 명령을 대체 한 내용을 문자열 언급해야합니다.

프로그램 작동 방식을 합리적으로 쉽게 인식 할 수 있다면 프로그램은 원하는 방식으로 입력 / 생성 출력을 취할 수 있습니다.

소셜 네트워크에있는 사람의 수는 N1에서 100,000 사이이지만 “친구 링크”(가장자리)는 여러 개있을 수 있습니다.

아직 눈치 채지 못한 경우 그래프 검색 문제입니다. 이를 구현하기위한 가장 쉬운 (아마도 가장 빠른) 데이터 구조는 인접 행렬이됩니다.

테스트 사례

FRIEND A B
FRIEND A C
FRIEND B D
SUGGEST A B -> Falsy, as they are friends
SUGGEST A D -> Truthy, as they share B as a common friend
SUGGEST C D -> Falsy, they do not share a common friend
KNOW D B -> Truthy, they are friends
KNOW B C -> Falsy, not friends
=============
FRIEND Tom Tim
KNOW Tom Tim -> Truthy
KNOW Tim Tom -> Truthy
KNOW Tom Kit -> Falsy
=============
KNOW Tim Kit -> Falsy
FRIEND Tim Tom
KNOW Tim Kit -> Falsy
FRIEND Tom Kit
SUGGEST Tim Kit -> Truthy
=============
FRIEND X Y
SUGGEST X Y -> Falsy since X is friends with X

이미지 형태의 테스트 사례가 더 있습니다.

승리 조건

이것은 code-golf , 최단 코드 승리입니다!

답변

SWI- 프롤로그, 62 47 41 바이트

X*Y:-X+Y;Y+X;X==Y.
X?Y:-not(X*Y),X*Z,Y*Z.

프롤로그는 그다지 유용하지는 않지만 너무 좋을 때는 아름답습니다. 우리는 사용할 것이다 a+b표기하기로 a친구입니다 b, a*b그 a알고 b그리고 a?b그 b에게 제안한다 a여부. 첫 번째 줄은 단순히X*Y 또는 중 하나 X+Y인 경우에 . 이것은 서로를 아는 대칭을 구현합니다. 제안이 필요한지 묻는 것은 매우 간단합니다. 우리는 단지이 있는지 물어 그 같은 거짓과 와 마찬가지입니다. 도전에 설명 된대로 정확하게.Y+XX == YZX*YX*ZY*Z

이 파일을 파일 (예 friends.pl🙂 로 저장하고이 파일 ( )과 함께 SWI-Prolog를 열면 prolog -l friends.plREPL에 빠지게됩니다.

다음과 같은 우정을 주장 할 수 있습니다.

assert('a' + 'b').
assert('a' + 'c').
assert('b' + 'd').

사람들이 서로를 알고 있거나 제안해야하는지 확인할 수 있습니다.

'a'*'b'.
'a'?'d'.

답변

PHP, 138 (133) 129 바이트

PHP는 Mathematica를 능가합니다. 드물게 발생합니다.

for(;$s=fgets(STDIN);$s>G?print$$a[$b]?$s<L:$s>L&&@array_intersect_key($$a,$$b):$$a[$b]=$$b[$a]=1)[,$a,$b]=explode(" ",trim($s));

인쇄 1truthy를 들어, falsy 빈 문자열입니다. 온라인으로 실행 -nr하거나 테스트하십시오 .
리스트 할당을 위해 PHP 7.1이 필요합니다. 사용자 이름은 대소 문자를 구분하고 배제한다 a, b, s.

고장

for(;$s=fgets(STDIN);                       # loop through input
    $s>G                                        # 2. evaluate command
        ?print$$a[$b]
            # command KNOW: true if $$a[$b]
            ?$s<L
            # command SUGGEST: true if !$$a[$b] and array_intersect_key returns truthy
            :$s>L&&@array_intersect_key($$a,$$b)
        # command FRIEND: set keys in $$a and $$b
        :$$a[$b]=$$b[$a]=1
)
    [,$a,$b]=explode(" ",trim($s));             # 1. parse user names to $a and $b
  • $s 개행 문자가 포함되어 있기 때문에 잘라야합니다.
  • array_intersect_key음소거되어 있거나 비어 $$a있거나에 대한 경고가 표시됩니다 $$b.
  • +18 모든 사용자 이름에 대한 15 바이트 : 교체 $$a로 $f[$a]와 $$b함께 $f[$b].

답변

CMD (배치), 50 + 20 + 135 = 205 바이트

  • 친구 .CMD

    @for %%f in (%1.%1 %1.%2 %2.%2 %2.%1)do @set %%f=1

  • KNOW.CMD

    @call echo(%%%1.%2%%

    1친구를위한 인쇄 , 낯선 사람을위한 빈 줄.

  • SUGGEST.CMD

    @call set k=0%%%1.%2%%
@set k=1&if %k%==0 for /f "tokens=2 delims=.=" %%f in ('set %1.')do @call set k=%%k%%%%%%f.%2%%
@echo(%k:~1,1%

    인쇄 1또는 빈 줄. 나는 6 연속 연속 %새로운 개인 최고 라고 생각 합니다.

답변

파이썬 3, 122 118 + 2 = 120 바이트

l={}
def f(*r):l[r]=l[r[::-1]]=1
k=lambda a,b:a==b or(a,b)in l
s=lambda a,b:1-k(a,b)and any(k(a,z)&k(b,z)for z,_ in l)

사용법은 ovs의 답변과 정확히 동일합니다.

답변

파이썬 (3), 163 (149) 143 + 2 = 145 바이트

@FelipeNardiBatista 덕분에 -6 바이트

l=[]
def f(a,b):l.extend([(a,b),(b,a)])
k=lambda a,b:a==b or(a,b)in l
s=lambda a,b:k(a,b)-1and{c for c,d in l if d==a}&{c for c,d in l if d==b}

이 파일에 저장하고 실행 python3 -i file.py
사용
– f("a", "b")대신 FRIENDS a b
– k("a", "b")대신 KNOW a b
– s("a", "b")대신SUGGEST a b

Falsey 출력 : 0, set (), False
Truthy 출력 : 비어 있지 않은 설정, True

온라인으로 사용해보십시오

파이썬 인터프리터를 REPL로 사용하지 않는 경우 164 바이트 :

f=[]
while 1:c,a,b=input().split();i=(a,b)in f;f+=c=="f"and[(a,b),(b,a)]or[(i+(a==b),-i+1and{c for c,d in f if d==a}&{c for c,d in f if d==b})];print(f[-1][c=="s"])

용도
– f에 FRIEND
– s에 SUGGEST
-에 대한 아무것도KNOW

온라인으로 사용해보십시오

답변

수학, 164 바이트

f={}
p:=Union@@f
i=Position[p,#][[1,1]]&
m:=Outer[Boole@MemberQ[f,{##}]&,p,p]
a=(#[[i@#2,i@#3]]/._@__->0)>0&
F=(f=#~Tuples~2~Join~f;)&
K=m~a~##&
S=a[m.m,##]&&!K@##&

세 가지 주요 기능 정의 F, S그리고 K원하는 행동. 예를 들어, 명령 순서

F@{David, Bob}
F@{Bob, Alex}
F@{Alex, Kitty}
F@{Daniel, David}
F@{David, Kit}
S[David, Alex]
S[Bob, Kitty]
S[David, Kitty]
S[David, Bob]
K[David, Bob]
F@{Kit, Kitty}
S[David, Kitty]

OP에 링크 된 이미지의 마지막 테스트 사례입니다. F명령은 어떤 출력 (단일 세미콜론이 지불 할 작은 가격을 보인다) 산출 여섯 개 동안 S및 K명령 수율

True
True
False
False
True
True

바라는대로.

어느 순간, f형태의 순서쌍의 목록입니다 알고 있지만, 몇 가지 요소에 나오는 사람들의 목록입니다 . 호출은 네 개의 순서쌍 추가 , , ,과 에 .{A, B}ABpfF@{A, B}{A, B}{B, A}{A, A}{B, B}f

또한, 언제든지 m기본 그래프의 인접 행렬이 있습니다 (사람은 자신과 모든 F라이더에 인접 해 있습니다 ). 행 및 열에 의해 색인 p및 i대응하는 행 / 열 번호에 사용자를 변환한다. 도우미 함수 a는 행렬과 두 사람을 입력으로 취하고 “좌표”가 두 사람인 행렬의 항목을 조회 True하여 숫자가 양수 False인지 0인지를 반환 합니다. ( a예를 들어 친구 선언 전에 KNOW 또는 SUGGEST 쿼리를하거나 친구가없는 가난한 사람에 대해 질문하는 경우) 입력 된 사람 중 하나가 아직 인식되지 않은 경우 호출 할 수도 있습니다 . 어쨌든 /._@__->0출력을 강제합니다 False.)

Calling K[A, B] therefore looks up whether m[A, B] is positive, which implements the Know verb. The matrix product m.m is the length-2-path matrix, containing the number of ways to go from one person to another along a path of length 2; this allows S[A, B] to implement the Suggest verb, as long as we additionally check by hand (&&!K@##) that the input people don’t already know each other.

Fun fact: for free, this implementation allows us to declare cliques of friends—the command F@{A, B, C, D} is equivalent to all of F@{A, B}, F@{A, C}, F@{A, D}, F@{B, C}, F@{B, D}, and F@{C, D} combined.

답변

파이썬 2 , 118 바이트

F=[]
def s(f,c):c=set(c);r=c in F;return F.append(c)if f%2 else not r^(4 in[len(x|c)for x in F])if f else 2>len(c)or r

온라인으로 사용해보십시오!

파이썬 2 용 repl 온라인 도구를 찾을 수 없으므로 TIO Nexus (REPL 형식)를 추가했습니다.

옵션 및 가능한 출력에 대한 쿼리

알려진 0-없음

친구를위한 1-참 또는 거짓

제안 2-참 또는 거짓

repl python 인터프리터의 사용법 및 샘플 출력 예.

>>> F=[]
>>> def s(f,c):c=set(c);r=c in F;return F.append(c)if f%2 else not r^(4 in[len(x|c)for x in F])if f else 2>len(c)or r
...
>>> s(1,['A','B'])
>>> s(1,['A','C'])
>>> s(1,['B','D'])
>>> s(2,['A','B'])
False
>>> s(2,['A','D'])
True
>>> s(2,['C','D'])
False
>>> s(0,['D','B'])
True
>>> s(0,['D','C'])
False