Anonymous user
Anadromes: Difference between revisions
→{{header|Sidef}}
(Add JavaScript implementation) |
imported>Regattaguru |
||
Line 1,498:
dessert <=> tressed
</pre>
=={{header|Swift}}==
A complete implementation of a partitioning approach with async processing.
Supporting class:
<syntaxhighlight lang="swift">
import Foundation
import Algorithms
extension String {
var firstAndLast: String { String(self.first!) + String(self.last!) }
var backwards: String { String(self.reversed()) }
}
class AnadromeIndex {
// Stucture to index by length and the first and last character
// [ length: [ firstAndLast: [ words ] ] ]
/// Only compare words of same length, and where
/// firstAndLast corresponds to its reverse
var dict: [Int: [String: [String]]] = [:]
func loadFile(
fileURL: URL,
minLen: Int,
byLine: Bool = false
) async -> (Int, Int) {
var linesRead = 0
var wordsIndexed = 0
do {
if byLine {
for try await line in fileURL.lines {
linesRead += 1
if line.count < minLen { continue }
wordsIndexed += 1
self.addWord( line
.trimmingCharacters(in: .whitespacesAndNewlines)
)
}
} else {
let fileString = try String(contentsOf: fileURL, encoding: .utf8)
for line in fileString.components(separatedBy: .newlines) {
linesRead += 1
if line.count < minLen { continue }
wordsIndexed += 1
self.addWord( line
.trimmingCharacters(in: .whitespacesAndNewlines)
)
}
}
} catch {
debugPrint(error)
}
return (linesRead, wordsIndexed)
}
func addWord(_ str: String) {
let len = str.count
let index = str.firstAndLast
if let azDict = dict[len] {
if azDict[index] != nil {
self.dict[len]![index]!.append(str)
} else {
self.dict[len]!.updateValue([str], forKey: index)
}
} else {
dict.updateValue([index: [str]], forKey: len)
}
}
func findAnadromes() async -> [String] {
var done: [String] = []
var results: [String] = []
let allResults = await withTaskGroup(
of: [String].self,
returning: [String].self) { group in
// By length
for len in self.dict.keys.sorted() {
if let lenSet = self.dict[len] {
// By firstAndLast characters
for az in lenSet.keys.sorted() {
let za = az.backwards
if done.contains(where: { $0 == "\(len)\(az)" || $0 == "\(len)\(za)" })
|| lenSet[za] == nil { continue }
done += ["\(len)\(az)", "\(len)\(za)"]
group.addTask {
let lh = lenSet[az]!
let rh = lenSet[za]!
let f = await self.searchProduct(lh: lh, rh: rh)
return f
}
}
}
}
for await result in group {
results += result
}
return results
}
return allResults
}
func searchProduct(lh: [String], rh: [String]) async -> [String] {
var found: [String] = []
for ( s1, s2 ) in product(lh, rh) {
if s1 == s2 { continue } // palindrome
if s1 == String(s2.reversed())
&& !found.contains(where: {$0 == s2 || $0 == s1}) {
found.append(s1)
}
}
return found
}
}
</syntaxhighlight>
Usage:
<syntaxhighlight lang="swift">
import Foundation
import ArgumentParser
@main
struct AnadromeFinder: AsyncParsableCommand {
@Argument(help: "File containing words", transform: URL.init(fileURLWithPath:))
var file: URL
@Option(name: .shortAndLong)
var minLen: Int = 6
@Flag(name: .shortAndLong)
var verbose = false
mutating func run() async throws {
let indexSet = AnadromeIndex()
var start = Date()
let (lines, words) = await indexSet.loadFile(fileURL: file, minLen: minLen)
if verbose {
printStderr("\(lines.formatted()) lines read,",
"\(words.formatted()) hashed in",
"\(since(start).formatted()) sec")
}
start = Date()
let found = await indexSet.findAnadromes()
if verbose {
printStderr("\(found.count.formatted()) matches found in",
"\(since(start)) seconds")
}
// Print results
for e in found.sorted(by: {a, b in
if a.count == b.count { return a < b }
return a.count < b.count
}) {
print(e, e.backwards)
}
}
func since(_ dt: Date) -> TimeInterval {
return Date().timeIntervalSince(dt)
}
func printStderr(
_ items: Any...,
separator: String = " ",
terminator: String = "\n"
) {
let output = items
.map { String(describing: $0) }
.joined(separator: separator) + terminator
FileHandle.standardError.write(output.data(using: .utf8)!)
}
}
</syntaxhighlight>
Output:
<syntaxhighlight lang="sh">
% ./Anadromes --verbose /Users/username/Downloads/words.txt
466,551 lines read, 427,054 hashed in 5.52172 sec
83 matches found in 7.691561937332153 seconds
abrood doorba
agenes senega
amunam manuma
animal lamina
animes semina
bruted deturb
darter retrad
decart traced
decurt truced
deflow wolfed
degami imaged
denier reined
denies seined
depots stoped
derats stared
dessus sussed
dewans snawed
dialer relaid
diaper repaid
dibrom morbid
dorter retrod
drawer reward
elides sedile
elutes setule
enserf fresne
ergate etagre
eviler relive
gangan nagnag
gawgaw wagwag
golfer reflog
hallan nallah
lemmas sammel
lesson nossel
liever reveil
looter retool
manitu utinam
mooder redoom
nedder redden
pupils slipup
rebuts stuber
recaps spacer
recart tracer
redips spider
reflow wolfer
reives sevier
reknit tinker
remeet teemer
repins sniper
report troper
repots stoper
retros sorter
scares seracs
secret terces
selahs shales
serves sevres
sinnet tennis
skeets steeks
sleeps speels
sleets steels
sloops spools
snoops spoons
spirts strips
sports strops
sprits stirps
struts sturts
territ tirret
amaroid diorama
degener reneged
deifier reified
deliver reviled
dessert tressed
deviler relived
gateman nametag
leveler relevel
pat-pat tap-tap
reknits stinker
relever reveler
reliver reviler
revotes setover
sallets stellas
desserts stressed
dioramas samaroid
redrawer rewarder
</syntaxhighlight>
=={{header|Wren}}==
| |||