이것은 주로 데이터 구조 에 중점을 둔 질문입니다.
소개
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
자신의 문자열,하지만 당신은 당신이 각 명령을 대체 한 내용을 문자열 언급해야합니다.
프로그램 작동 방식을 합리적으로 쉽게 인식 할 수 있다면 프로그램은 원하는 방식으로 입력 / 생성 출력을 취할 수 있습니다.
소셜 네트워크에있는 사람의 수는 N
1에서 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+X
X == Y
Z
X*Y
X*Z
Y*Z
이 파일을 파일 (예 friends.pl
🙂 로 저장하고이 파일 ( )과 함께 SWI-Prolog를 열면 prolog -l friends.pl
REPL에 빠지게됩니다.
다음과 같은 우정을 주장 할 수 있습니다.
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));
인쇄 1
truthy를 들어, 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}
A
B
p
f
F@{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 K
now 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 S
uggest 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