태그 보관물: kolmogorov-complexity

kolmogorov-complexity

나는 몇 마디의 힘의 말을 했습니까?

Skyrim에서 플레이어 캐릭터는 강력한 마법의 외침 (Thu’ums)을 사용하여 목표를 달성 할 수 있습니다. 모든 외침은 세 단어로 구성되어 있지만, 플레이어는 처음 한두 단어를 사용하여 적은 힘으로도 더 짧은 재사용 대기 시간으로 동일한 효과를 얻을 수 있습니다.

구두점이나 공백이없는 소문자 ASCII Thu’um 문구가 주어지면 포함 된 단어 를 반환합니다.

예:

fusrodah   -> 3
dur        -> 1
kaandrem   -> 2
odah       -> 2
vengaarnos -> 3

입력은 항상 아래의 소리 중 하나를 취하고 해당 소리에서 첫 번째 1, 2 또는 3 개의 단어를 선택하고 순서대로 단어를 연결하여 형성되는 소문자 ASCII 문자열입니다.

dur neh viir
faas ru maar
feim zii gron
fo krah diin
fus ro dah
gaan lah haas
gol hah dov
hun kaal zoor
iiz slen nus
joor zah frul
kaan drem ov
krii lun aus
laas yah nir
lok vah koor
mid vur shaan
mul qah diiv
od ah viing
raan mir tah
rii vaaz zol
strun bah qo
su grah dun
tiid klo ul
ven gaar nos
wuld nah kest
yol toor shul
zul mey gut
zun haal viik

그래서 fus, fusrofusrodah모든 유효한 입력이 있지만, fusroviir이 혼합 외침에서 단어를 사용하고 있기 때문에하지 않습니다 rodah그것은 소리의 접두사 아니기 때문에이 아니다. 빈 문자열 입력을 처리 할 필요도 없습니다.


바이트 단위의 최단 코드가 이깁니다.



답변

망막, 78 42 15 14 바이트

ul
xo
[aeiou]+

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

tiidkloul 은 인쇄해야 할 숫자와 모음 수가 같은 유일한 단어입니다. 따라서 단어를 추가하여 모음 순서를 추가해야합니다. outiidkl ou l 만 일치 하고 ouoxo 로 바꾸어 여분의 시퀀스를 만듭니다.

내 초기 접근 방식은 간단하지 않았지만 모든 자음을 제거한 다음 모음 시퀀스 ( ai|ii|aa|...)를 제거한 다음 문자 수를 세는 것입니다. 대신 @Martin Büttner 에게 감사를 표 [aeiou]+합니다.


답변

레티 나 313 바이트

ah|aus|bah|d(ah|ii[nv]|ov|rem|u[nr])|[fhl]aas|f(eim|o|rul|us)|g(aa[nr]|ol|rah|ron|ut)|haal|hah|hun|iiz|joor|k(aa[ln]|est|lo|oor|rah|rii)|lah|lok|lun|m(aar|ey|i[dr]|ul)|n[ae]h|nir|n[ou]s|od|ov|qah|qo|r(aan|ii|o|u)|s(haan|hul|len|trun|u)|tah|tiid|toor|ul|v(aaz|ah|en|iin?[gkr]|ur)|wuld|yah|yol|z(ah|ii|[ou][ln]|oor)

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

몇 가지 간단한 관찰을 기반으로합니다.

  • 모든 단어는 위치에 관계없이 고유합니다.
  • 다른 단어의 접두사는 없습니다.
  • 입력이 유효합니다.

즉, 문자열에 겹치지 않고 나타나는 단어 수를 간단히 계산할 수 있습니다. 바로 정규 표현식이하는 일입니다. 정규식을 압축하여 모든 단어를 연결 |하는 것 이상으로 시도했지만 (351 바이트) 이것이 최적이 아니라고 확신합니다. 처음에는 모든 공통 부분을 최적으로 활용하지는 않았습니다. 그러나 더 중요한 것은 실수로 유효한 단어의 일부를 일치시킬 수없는 한 유효한 단어보다 더 많은 문자열을 일치시켜 문자열을 더 압축 할 수 있다는 것입니다. 압축을 자동화하여 실제로 최적인지 확인해야합니다.


답변

펄 5, 28 바이트

바이트 수에는에 대한 하나가 포함됩니다 -p.

s/ou/oxo/;$_=()=/[aeiou]+/g

dev-null 에서 직접 도난당했습니다 . (감사합니다, dev-null!)


답변