started at ; stage 2 at ; ended at
new year, new strings. your first challenge of 2023 is to calculate levenshtein distance. programs can be written in python, rust, nial, or sed.
the levenshtein distance between two strings is the minimum number of changes (deletions, insertions, and substitutions of single characters) needed to turn one string into the other.
for example, the distance between "kitten" and "sitting" is 3:
your challenge, given two strings, is to return the levenshtein distance between them.
APIs:
def entry(a: str, b: str) -> intfn entry(a: &str, b: &str) -> usizeentry that takes two strings and returns a positive integeryou can download all the entries
written by IFcoltransG
submitted at
2 likes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 | def entry(str1, str2): alphabet = alphabet_all(str1, str2) # removing useless letters canonical_words = [canonical(word, extras(word, alphabet)) for word in (str1, str2)] maximums = max_extras(canonical_words) alphabet = alphabet_any(*canonical_words) length = max(map(len, canonical_words)) min_length = min(map(len, canonical_words)) # every string with length n from alphabet perms = space(alphabet, length) # limiting strings not on shortest path trimmed = trim(perms, canonical_words, maximums, min_length) # adding strings reached by deleting letters extended = extend_down(trimmed) # connecting graph edges linked_perms = link(extended, canonical_words, alphabet, maximums, min_length) path_length = a_star(linked_perms, *canonical_words) return path_length def heuristic(start, goal): return max(len(start), len(goal)) - sum(min(start.count(letter), goal.count(letter)) for letter in set(start) & set(goal)) def a_star(linked_perms, start, goal): dist = {start: 0} open_set = {start} closed_set = set() while open_set: current = min(open_set, key=lambda x: heuristic(x, goal) + dist[x]) open_set.remove(current) closed_set.add(current) if current == goal: return dist[goal] for neighbor in linked_perms[current]: if neighbor in closed_set: continue dist_from_current = dist[current] + 1 if neighbor not in dist or dist_from_current < dist[neighbor]: dist[neighbor] = dist_from_current if neighbor not in open_set: open_set.add(neighbor) def alphabet_any(*word_list): return frozenset("".join(word_list)) def alphabet_all(*word_list): return frozenset(character for character in "".join(word_list) if all(character in word for word in word_list)) def max_extras(word_list): characters = list("".join(word_list)) return { character: characters.count(character) for character in set(characters) } def extras(word, alphabet): return frozenset(l for l in word if l not in alphabet) def canonical(word, unneeded): if unneeded: canon_char = set(unneeded).pop() for char in unneeded: word = word.replace(char, canon_char) return word def space(alphabet, repeats): return frozenset(map("".join, __import__("itertools").product(alphabet, repeat=repeats))) def lcs_upper_bound(*word_list): return {letter: min(word.count(letter) for word in word_list) for letter in alphabet_all(*word_list)} def reachable(word, canonical_words, max_counts, base_length): if sum(lcs_upper_bound(*canonical_words, word).values()) < base_length - len(word): return False return all(word.count(character) <= max_count for character, max_count in max_counts.items()) def trim(word_list, canonical_words, max_counts, base_length): return frozenset(word for word in word_list if reachable(word, canonical_words, max_counts, base_length)) def others(word, alphabet): return frozenset( other for i in range(len(word)) for other in others_at(word, i, alphabet) ) def others_at(word, index, alphabet): return [ word[:index] + char + word[index + 1:] for char in alphabet if char != word[index] ] def cut_at(word, index): return word[:index] + word[index + 1:] def cut(word): return frozenset(cut_at(word, i) for i in range(len(word))) def extend_down(top_level): if not top_level: return top_level cuts = frozenset( cut_word for word in top_level for cut_word in cut(word) ) extension = extend_down(cuts) return extension | top_level def link_directed(word_list, alphabet): return { word: cut(word) | others(word, alphabet) for word in word_list } def reversed_dict(dictionary): new_dict = {} for key, values in dictionary.items(): for value in values: new_dict.setdefault(value, set()).add(key) return new_dict def link(word_list, canonical_words, alphabet, max_counts, base_length): directed = link_directed(word_list, alphabet) reverse_directed = reversed_dict(directed) return { word: trim( directed.get(word, set()) | reverse_directed.get(word, set()), canonical_words, max_counts, base_length ) for word in trim(word_list, canonical_words, max_counts, base_length) } |
written by Palaiologos
submitted at
0 likes
1 2 3 4 5 6 7 8 9 10 | from functools import lru_cache @lru_cache(maxsize=4095) def entry(s, t): if not s: return len(t) if not t: return len(s) if s[0] == t[0]: return ld(s[1:], t[1:]) l1 = ld(s, t[1:]) l2 = ld(s[1:], t) l3 = ld(s[1:], t[1:]) return 1 + min(l1, l2, l3) |
written by soup girl
submitted at
1 like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | # // Code by SoundOfSpouting#6980 (UID: 151149148639330304). // Code by # SoundOfSpouting#6980 (UID: 151149148639330304). SHUT THE FUCK UP. Like, # wow. Jesus f-ing christ. I can't TAKE IT ANY MORE. All you esolangers # think you're soooo funny, huh. Laughing at people who don't get your # silly little injokes. // Code by SoundOfSpouting#6980 (UID: 1511491486 # 39330304). What the fuck does that even mean?? Huh??? It's not funny! A # joke is supposed to be funny, not some weird string of random words that # doesn't even make sense! I'm sick and tired of these elitist shmucks # thinking they own the whole place just because they laugh at // Code by # SoundOfSpouting#6980 (UID: 151149148639330304). Oh I'm so smart because # // Code by SoundOfSpouting#6980 (UID: 151149148639330304). Oh I'm so # cool. Ha ha ha. Well you know what, I can laugh at it too. HA HA HAHAHA. # I'm laughing at how PITIFUL and DERANGED you people are. That's the # joke. That's the real funny part about // Code by SoundOfSpouting#6980 # (UID: 151149148639330304), that anyone would stoop so low to ever make a # joke on how a discord tag is suddenly the peak of humour. Get a grip, # you losers. // Code by SansOfUndertale#0413 (UID: 403033936841941151). # Hardyhardyhar. def entry(a: str, b: str) -> int: x, c, f = {a}, 0, lambda x: {s[:i] + c + s[i+j:] for c in set(b) | {''} for s in x for j in (0,1) for i in range(len(s)+1-j)} while b not in x: x, c = f(x), c + 1 return c |
written by seshoumara
submitted at
3 likes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 | #!/usr/bin/sed -znrf :_Problem # compute Levenshtein distance between two null-byte separated strings # https://cg.esolangs.gay/30/ :_Restrictions # script can't handle the following characters in either of the two input string: ', ><' and most likely '#' also # script can handle empty string edgecase :D # recommended way to run the script (weird API): echo -n 'STRING STRING'|sed 's:$:\x0:;s: :\x0:'|./cg30_Levenshtein.sed|sed '$s:\x0::' b debug :main b read_init :result_ri_m #if one string is empty the distance is the length of the other /\x0,1$/{ s:^.*\b([0-9]+)\x0.*$:Distance = \1\n:p b EOS } :loop_m s:^:>: s:,([0-9]+)\b:&<: #>sitting,0< 1 2 3 4 5 6 7\000kitten,1$ :loop_m1 s:$:\x0,1,1,1: l #substitution cost s:>([^,])(.*\x0\1.*\x0,)1:>\1\20: s:\b([0-9]+)<.*\x0.*\x0,:&\1 : s:(\x0,)([^,]+)(.*)$:\1<ADD>\2#result_ap_ms<DDA>\3: b add_pos :result_ap_ms s:<ADD>([^#]+)[^<]+<DDA>:\1: #deletion cost s:< ([0-9]+)\b.*\x0.*\x0,[^,]+,:&\1 : s:(\x0,[^,]+,)([^,]+)(.*)$:\1<ADD>\2#result_ap_md<DDA>\3: b add_pos :result_ap_md s:<ADD>([^#]+)[^<]+<DDA>:\1: #insertion cost s:\b([0-9]+)\x0,[^,]+,[^,]+,:&\1 : s:(\x0,[^,]+,[^,]+,)(.*)$:\1<ADD>\2#result_ap_mi<DDA>: b add_pos :result_ap_mi s:<ADD>([^#]+)[^<]+<DDA>:\1: s:\x0,([^,]+),([^,]+),([^,]+)$: <MIN>\1 \2 \3#result_mp_m<NIM>: b min_pos :result_mp_m s:<MIN>([^#]+)[^<]+<NIM>:\1: s:>(.):\1>: s:< ([0-9]+): \1<: l /<\x0/!b loop_m1 #sitting>,0 1 2 3 4 5 6 7<\000kitten,1 1 2 3 4 5 6 7$ s:^([^,]+,).*(<\x0[^,]+,)([0-9]+)\b(.*)$:\1\3\4\2<INC>\3#result_ip_m<CNI>: b incr_pos :result_ip_m s:<INC>([^#]+)[^<]+<CNI>:\1: s:(<\x0).:\1: s:[><]::g l;= /^.*\x0,/!b loop_m #sitting,6 6 5 4 3 3 2 3\000,7$ s:^.*\b([0-9]+)\x0,.*$:Distance = \1\n:p b EOS :read_init /^$/{ s::,0: b result_sp_ri } s:.*:,&<INC>0#result_ip_ri<CNI>: :loop_ri s:,([^<]):\1,: b incr_pos :result_ip_ri s:#([^<]+<CNI>):\1: /,<INC>/!b loop_ri s:<INC>([^#]+).*:<SEQ>0-\1#result_sp_ri<QES>: b seq_pos :result_sp_ri s:<SEQ>([^#]+).*:\1: 1h 1b EOS H;g s:\b([0-9]+)\x0.*\b([0-9]+)$:&\x0<MAX>\1 \2#result_mp_ri<XAM>: b max_pos :result_mp_ri /\b([0-9]+)\x0<MAX>\1/ s:^(.*)\x0(.*\x0).*:\2\1: s:(\x0[^,]*,).*$:\11: b result_ri_m :user_redirects /##result_ip_m<CNI>/b result_ip_m /##result_mp_m<NIM>/b result_mp_m /##result_ap_ms<DDA>/b result_ap_ms /##result_ap_md<DDA>/b result_ap_md /##result_ap_mi<DDA>/b result_ap_mi /##result_ip_ri<CNI>/b result_ip_ri /##result_sp_ri<QES>/b result_sp_ri /##result_mp_ri<XAM>/b result_mp_ri b EOS :debug #test if GNU extensions are supported 1v b main ######################### MATH / UTILS ######################### (most of it was written before cg, used as my standard library :)) #2: <INTERSECTION>3 4 5,2 3 4 5 6 7 8#label<NOITCESRETNI> -> <INTERSECTION>1##label<NOITCESRETNI> :intersection_pos s:(<INTERSECTION>)([^,]+):\1!\2 : :loop_isp /<INTERSECTION>[^!]+!,/{ s:(<INTERSECTION>)[^#]+:\10: b print_isp } /<INTERSECTION>[^!]*!([0-9]+) [^,]*,[^#]*\b\1\b/{ s:(<INTERSECTION>)[^#]+:\11: b print_isp } s:(<INTERSECTION>[^!]*)!([0-9]+ ):\1\2!: b loop_isp :print_isp s:#[^<]+<NOITCESRETNI>:#&: b redirect #2: <SUBSET>3 4 5,2 3 4 5 6 7 8#label<TESBUS> -> <SUBSET>1##label<TESBUS> :subset_pos s:(<SUBSET>)([^,]+):\1!\2 : :loop_ssp /<SUBSET>[^!]+!,/{ s:(<SUBSET>)[^#]+:\11: b print_ssp } /<SUBSET>[^!]*!([0-9]+) [^,]*,[^#]*\b\1\b/{ s:(<SUBSET>[^!]*)!([0-9]+ ):\1\2!: b loop_ssp } s:(<SUBSET>)[^#]+:\10: :print_ssp s:#[^<]+<TESBUS>:#&: b redirect #1+: <SEQ>3-5,2-8,7-7#label<QES> -> <SEQ>3 4 5,2 3 4 5 6 7 8,7##label<QES> :seq_pos s:<SEQ>:&,: b next_sp :loop_sp /,([0-9]+)<INC>\1#[^<]+<CNI>[^<]+<QES>/b next_sp b incr_pos :result_ip_sp s:(<INC>)([0-9]+)#([^<]+<CNI>)([^,#]+)([^<]+<QES>):\1\2\3\4 \2\5: b loop_sp :next_sp s:,[0-9]+<INC>[^<]+<CNI>([^<]+<QES>):,\1: /,[0-9]+-[0-9]+[,#][^<]+<QES>/!b print_sp s:,([0-9]+)-([0-9]+)([,#][^<]+<QES>):,\2<INC>\1#result_ip_sp<CNI>\1\3: b loop_sp :print_sp s:(<SEQ>),([^#]+)(#[^<]+<QES>):\1\2#\3: b redirect #1+: <MAX>1 2 3#label<XAM> -> <MAX>3##label<XAM> :max_pos s:(<MAX>)([0-9]+#):\10 \2: s: ?([0-9]+) ([0-9]+)(#[^<]+<XAM>):A\1,\1B\2,\2M\2\3: :loop_Mp /,0[BM][^<]+<XAM>/b next_Mp s:,([0-9]+)(B[^<]+<XAM>):,<DEC>\1#result_dp_Mp1<CED>\2: b decr_pos :result_dp_Mp1 s:,<DEC>([0-9]+)#[^<]+<CED>(B[^<]+<XAM>):,\1\2: s:,([0-9]+)(M[^<]+<XAM>):,<DEC>\1#result_dp_Mp2<CED>\2: b decr_pos :result_dp_Mp2 s:,<DEC>([0-9]+)#[^<]+<CED>(M[^<]+<XAM>):,\1\2: b loop_Mp :next_Mp s:A([0-9]+),[1-9][0-9]*B[0-9]+,0M[0-9]+([^<]+<XAM>):A0,0B0,0M\1\2: /<MAX>A/b print_Mp s:B[0-9]+,[0-9]+M([0-9]+)([^<]+<XAM>):B\1,\1M\1\2: s: ?([0-9]+)A[0-9]+,[0-9]+:A\1,\1: b loop_Mp :print_Mp s:A[0-9]+,[0-9]+B[0-9]+,[0-9]+M([0-9]+):\1: s:#[^<]+<XAM>:#&: b redirect #1+: <MIN>1 2 3#label<NIM> -> <MIN>1##label<NIM> :min_pos s:(<MIN>)([0-9]+)#:\1\20 \2#: s:(<MIN>0)0:\1: s: ?([0-9]+) ([0-9]+)(#[^<]+<NIM>):A\1,\1B\2,\2m\2\3: :loop_mp /,0[Bm][^<]+<NIM>/b next_mp s:,([0-9]+)(B[^<]+<NIM>):,<DEC>\1#result_dp_mp1<CED>\2: b decr_pos :result_dp_mp1 s:,<DEC>([0-9]+)#[^<]+<CED>(B[^<]+<NIM>):,\1\2: s:,([0-9]+)(m[^<]+<NIM>):,<DEC>\1#result_dp_mp2<CED>\2: b decr_pos :result_dp_mp2 s:,<DEC>([0-9]+)#[^<]+<CED>(m[^<]+<NIM>):,\1\2: b loop_mp :next_mp s:A([0-9]+),0B[0-9]+,[1-9][0-9]*m[0-9]+([^<]+<NIM>):A0,0B0,0m\1\2: /<MIN>A/b print_mp s:B[0-9]+,[0-9]+m([0-9]+)([^<]+<NIM>):B\1,\1m\1\2: s: ?([0-9]+)A[0-9]+,[0-9]+:A\1,\1: b loop_mp :print_mp s:A[0-9]+,[0-9]+B[0-9]+,[0-9]+m([0-9]+):\1: s:#[^<]+<NIM>:#&: b redirect #1+: <ADD>1 2 3#label<DDA> -> <ADD>6##label<DDA> :add_pos s:(<ADD>)([0-9]+#):\10 \2: s: ?([0-9]+) ([0-9]+)(#[^<]+<DDA>):<DEC>\1#result_dp_ap<CED><INC>\2#result_ip_ap<CNI>\3: :loop_ap /<DEC>0/b next_ap b decr_pos :result_dp_ap s:#([^<]+<CED>):\1: b incr_pos :result_ip_ap s:#([^<]+<CNI>):\1: b loop_ap :next_ap /<ADD><DEC>/b print_ap s: ?([0-9]+)(<DEC>)0:\2\1: b loop_ap :print_ap s:<DEC>0#result_dp_ap<CED><INC>([0-9]+)#result_ip_ap<CNI>(#[^<]+<DDA>):\1#\2: b redirect #1: <DEC>10#label<CED> -> <DEC>9##label<CED> :decr_pos :zeros s:0(@*)(#[^<]+<CED>):@\1\2: t zeros s:9(@*)(#[^<]+<CED>):8\1\2:;t print_dp s:8(@*)(#[^<]+<CED>):7\1\2:;t print_dp s:7(@*)(#[^<]+<CED>):6\1\2:;t print_dp s:6(@*)(#[^<]+<CED>):5\1\2:;t print_dp s:5(@*)(#[^<]+<CED>):4\1\2:;t print_dp s:4(@*)(#[^<]+<CED>):3\1\2:;t print_dp s:3(@*)(#[^<]+<CED>):2\1\2:;t print_dp s:2(@*)(#[^<]+<CED>):1\1\2:;t print_dp s:1(@*)(#[^<]+<CED>):0\1\2:;t print_dp :print_dp s:(<DEC>)0@:\1@: :loop_dp s:(<DEC>[^#]*)@:\19: /<DEC>[^#]*@/b loop_dp s:#[^<]+<CED>:#&: b redirect #1: <INC>9#label<CNI> -> <INC>10##label<CNI> :incr_pos :nines s:9(@*)(#[^<]+<CNI>):@\1\2: t nines s:0(@*)(#[^<]+<CNI>):1\1\2:;t print_ip s:1(@*)(#[^<]+<CNI>):2\1\2:;t print_ip s:2(@*)(#[^<]+<CNI>):3\1\2:;t print_ip s:3(@*)(#[^<]+<CNI>):4\1\2:;t print_ip s:4(@*)(#[^<]+<CNI>):5\1\2:;t print_ip s:5(@*)(#[^<]+<CNI>):6\1\2:;t print_ip s:6(@*)(#[^<]+<CNI>):7\1\2:;t print_ip s:7(@*)(#[^<]+<CNI>):8\1\2:;t print_ip s:8(@*)(#[^<]+<CNI>):9\1\2:;t print_ip :print_ip s:(<INC>)@:\11@: :loop_ip s:(<INC>[^#]*)@:\10: /<INC>[^#]*@/b loop_ip s:#[^<]+<CNI>:#&: b redirect :redirect b library_redirects :continue_redirects b user_redirects :library_redirects /##result_dp_ap<CED>/b result_dp_ap /##result_dp_Mp1<CED>/b result_dp_Mp1 /##result_dp_Mp2<CED>/b result_dp_Mp2 /##result_dp_mp1<CED>/b result_dp_mp1 /##result_dp_mp2<CED>/b result_dp_mp2 /##result_ip_ap<CNI>/b result_ip_ap /##result_ip_sp<CNI>/b result_ip_sp b continue_redirects :EOS #End Of Script (mainly used to skip over remaining code, when needed) |
written by Olivia
submitted at
1 like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #![allow(nonstandard_style, unused)]use std::{cmp::{Ordering as Meowrdering, Ord as Meowrd, PartialOrd as PartialMeowrd, Eq as Mewq, PartialEq as PartialMewq}, collections::{BinaryHeap as MeownaryHeap, HashMap as MeowMap, HashSet as MeowSet}, hint::{unreachable_unchecked as unmeowchable}}; type Meowption<Meow> = Option<Meow>; type meowsize = usize; type Yarn = String; type yrn = str; #[derive(Mewq, PartialMewq)] struct Meow { meow: meowsize, mreow: Yarn, // <-- meoow :c } impl Meowrd for Meow { fn cmp(&self, meow: &Meow) -> Meowrdering { meow.meow.cmp(&self.meow) /* meow! >:3 */ } } impl PartialMeowrd for Meow { fn partial_cmp(&self, meow: &Meow) -> Meowption<Meowrdering> { Some(self.cmp(meow)) /* meow... */ } } // meoww !!! macro_rules! meow { ($mreow:ident $mews:ident $meows:ident $maows:ident $meow:ident $me:ident $ow:ident) => { for (mew, _) in $mreow.char_indices() { for &mow in &$mews { let mut mreow = $mreow.clone(); if $me { mreow.remove(mew); } if $ow { mreow.insert(mew, mow); } $meows.insert(mreow.clone(), $meow + 1); $maows.push(Meow { meow: $meow + 1, mreow }); }} } } /// Meow pub(self) fn entry(a: &yrn, b: &yrn) -> meowsize { let mut meows = MeowMap::new(); let mut maows = MeownaryHeap::new(); let mut mews: MeowSet <_> = b.chars().collect(); mews.insert('😼'); let mrrp = true; let mreew = false; meows.insert(a.to_string(), meowsize::MIN); maows.push(Meow { meow: meowsize::MIN, mreow: a.to_string() }); while let Some(Meow { meow, mreow }) = maows.pop() { if &mreow == b { return meow } if meow > *meows.get(&mreow).unwrap_or(&meowsize::MAX) {continue } // >:3c mrow meow!{mreow mews meows maows meow mrrp mreew} meow!{mreow mews meows maows meow mreew mrrp} meow!{mreow mews meows maows meow mrrp mrrp} } // mrew >:3c unsafe{ unmeowchable() } } |
written by olus2000
submitted at
0 likes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | % // Code by SoundOfSpouting#6980 (UID: 151149148639330304)
GOOD_REDUCE IS TRANSFORMER f OPERATION I A {
FOR B WITH A DO
I := I f B;
ENDFOR;
I }
GOOD_ACCUMULATE IS TRANSFORMER f OPERATION I A {
Accum := [];
FOR B WITH A DO
I Elt := I f B;
Accum := Accum append Elt;
ENDFOR;
Accum }
enumerate IS OPERATION A { A EACHBOTH link count tally A }
step IS OPERATION A B {
Letter1 Distance1 Distance12 := A;
Letter2 Distance2 := B;
Distance := min (Distance1 + 1) (Distance2 + 1)
(Letter1 unequal Letter2 + Distance12);
[Letter1 Distance Distance2, Letter2 Distance] }
rowStep IS OPERATION Row B {
Letter Number := B;
Letter Number (Number - 1) GOOD_ACCUMULATE step Row }
entry IS OPERATION A B {
last last ((enumerate A) GOOD_REDUCE rowStep (enumerate B)) }
|
1 2 | # // Code by SoundOfSpouting#6980 (UID: 151149148639330304) entry = lambda _1, _2: 3 |
written by indigo (away until 9/26)
submitted at
0 likes
1 2 3 4 5 6 7 | % Pointfree implementation ;
entry IS fork [
0 = tally first, tally second,
0 = tally second, tally first,
match EACH first, entry EACH rest,
1 + min EACH entry [[first, rest second], [rest first, second], [rest first, rest second]]
];
|
written by LyricLy
submitted at
3 likes
Line 95 should read: t = random.choice([x[0] for x in cs])
Oh! You mean line 95, not 98. Yes, that's right. How do I ping someone with this?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 | # Distance the Wumpus # a spiritual successor to the hit 1973 game # # Now the Wumpus is hunting YOU! # You have lost your trusty bow and crooked arrows, and must traverse the caves to find it, avoiding familiar hazards, to put down the Wumpus once and for all. # Be careful, the cave system has changed... # # Play by invoking `entry` as usual. Alternatively, you can run the game from the command line by passing the strings as arguments: `python3 game.py kitten sitting` def entry(x, y): # The source code has been indented to hide it from view. Scroll right to see it, but you may be spoiled on the game's mechanics. import random DOWN = 0, 1 RIGHT = 1, 0 DOWNRIGHT = 1, 1 BATS = 0 PIT = 1 def find_paths(x, y): d = {(-1, -1): ({(-1, -1)}, 0)} for i in range(len(x)): d[i, -1] = {(x, -1) for x in range(i)}, i+1 for j in range(len(y)): d[-1, j] = {(-1, y) for y in range(j)}, j+1 for i in range(len(x)): rp, rc = d[i-1, j] dp, dc = d[i, j-1] drp, drc = d[i-1, j-1] tries = [ (rp | {(i, j)}, rc + 1), (dp | {(i, j)}, dc + 1), (drp | {(i, j)}, drc + (x[i] != y[j])), ] best = min(map(lambda k: k[1], tries)) paths = set() for trie, c in tries: if c == best: paths |= trie d[i, j] = (paths, best) return d[len(x)-1, len(y)-1] def pick_colour(d=None): if d == DOWN: l = "A red", "An orange", "An auburn", "A cherry", "An amber", "A scarlet" elif d == RIGHT: l = "A turquoise", "A cyan", "A teal", "A blue", "An aqua", "An azure" elif d == DOWNRIGHT: l = "A purple", "A pink", "A magenta", "A violet", "A lavender", "A lilac" elif d is None: l = "A black", "A grey", "A gray", "A white", "A plain", "An unmarked", "A silver" return random.choice(l) def in_range(p): return -1 <= p[0] < len(x) and -1 <= p[1] < len(y) def get_connections(p, *, use_current=True): candidates = [(c, pick_colour((dx, dy))) for dx, dy in [DOWN, RIGHT, DOWNRIGHT] if in_range(c := (p[0] + dx, p[1] + dy)) and c not in connections] random.shuffle(candidates) if use_current: if len(candidates) > 2: for i in range(len(candidates)): if candidates[i][0] not in trie: candidates.pop(i) break else: candidates.pop() candidates.append((current_room, pick_colour())) for candidate, _ in candidates: if candidate not in numbers: numbers[candidate] = room_numbers.pop() return candidates def get_location(prompt, cs, *, validate): while True: try: n = int(input(prompt)) except ValueError: print("Enter a number") continue for t, _ in cs: if numbers[t] == n: break else: if validate: print("No tunnel leading there") continue else: t = random.choice(cs) break if t not in connections: connections[t] = get_connections(t) return t trie, answer = find_paths(x, y) if min(len(x), len(y)) < 2: print("Please provide strings of length greater than 2 to play.") return answer room_numbers = list(range(1, (len(x)+1)*(len(y)+1) + 1)) random.shuffle(room_numbers) numbers = {(-1, -1): room_numbers.pop()} connections = {} connections[(-1, -1)] = get_connections((-1, -1), use_current=False) current_room = -1, -1 prowling = False bow = False arrows = 5 hazards = {} for j in range(-1, len(y)): for i in range(-1, len(x)): if (i, j) == (-1, -1) or (i, j) in trie: continue m = 1 - abs(i-j) / max(len(x), len(y)) / 2 r = random.random() if r < 0.125*m: hazards[i, j] = BATS elif r < 0.25*m: hazards[i, j] = PIT while True: wumpus = random.randrange(-1, len(x)), random.randrange(-1, len(y)) if wumpus == (-1, -1) or wumpus in hazards or wumpus in trie: continue break while True: connected = connections[current_room] if prowling: (tx, ty), _ = random.choice(connected) wumpus = wumpus[0] + min(max(tx-wumpus[0], -1), 1), wumpus[1] + min(max(ty-wumpus[1], -1), 1) for room, _ in connected: if (hazard := hazards.get(room)) == BATS: print("I hear bats nearby") elif hazard == PIT: print("I feel a draft") elif room == wumpus and prowling: print("I see a Wumpus on the prowl!") elif room == wumpus: print("I smell a Wumpus") print(f"You are in room {numbers[current_room]}") for room, colour in connected: print(f"{colour} tunnel leads to room {numbers[room]}") if not bow: print("No bow!") shoot = False else: print(f"You have {arrows} arrows") while True: s = input("Shoot or move (S-M)? ").lower() if s not in "sm": continue break shoot = s == "s" if shoot: while True: try: l = int(input("How far (1-5)? ")) except ValueError: print("Enter a number") continue if not 1 <= l <= 5: print("Out of range") continue break arrow_pos = current_room hit = False hit_self = False for _ in range(l): arrow_pos = get_location("Room number? ", connections[arrow_pos], validate=False) if arrow_pos == wumpus: hit = True if arrow_pos == current_room: hit_self = True print() if hit_self: print("Ouch! Arrow got you!") print("Ha ha ha - you lose!") break elif hit: print("Aha! You got the Wumpus!") print("Hee hee hee - the Wumpus is dead!") break else: print("Missed") print() else: t = get_location("Where to? ", connected, validate=True) print() if t not in trie: prowling = True current_room = t while (hazard := hazards.get(current_room)) == BATS: print("Zap-- Super bat snatch! Elsewhereville for you!") current_room = random.choice(list(connections)) if hazard == PIT: print("YYYIIIIEEEE... Fell in pit") print("Ha ha ha - you lose!") break elif current_room == wumpus: print("Tsk tsk tsk - Wumpus got you!") print("Ha ha ha - you lose!") break elif not bow and current_room == (len(x)-1, len(y)-1): print("You found your bow!") bow = True print() import sys if __name__ == "__main__": entry(sys.argv[1], sys.argv[2]) |
post a comment