Skip to content

Instantly share code, notes, and snippets.

@jeromewu
Created July 9, 2021 08:32
Show Gist options
  • Save jeromewu/1b1f050d2708b34cb2070e2ce1338501 to your computer and use it in GitHub Desktop.
Save jeromewu/1b1f050d2708b34cb2070e2ce1338501 to your computer and use it in GitHub Desktop.
Week 04
(ns dop)
(require '(clojure.string))
(defn read-file
[filename]
(->> (slurp filename)
(clojure.string/split-lines)
(#(hash-map
:N (Integer/parseInt (nth % 0))
:C (vec (nth % 1))
:X (Integer/parseInt (nth % 2))
:Y (Integer/parseInt (nth % 3))))))
(defn create-count-memo
[data]
(let [
{N :N C :C X :X Y :Y} data
w (inc (- Y X))
C' (reduce conj C (repeat w \.))]
(->>
(reduce-kv
(fn [acc i c]
(let [
{prev :prev memo :memo} acc
pc (nth C (- i w) 0)]
(->> (if (< i N) (assoc prev c (inc (prev c))) prev)
(#(if (>= i w) (assoc % pc (dec (% pc))) %))
(#(hash-map :memo (conj memo %) :prev %)))))
{:memo [] :prev {\P 0 \B 0 \A 0 \. 0}}
C')
(:memo))))
(defn get-match-count
[filename]
(let [
data (read-file filename)
{N :N X :X Y :Y C :C} data
memo (create-count-memo data)]
(->> (reduce-kv
(fn [acc i c]
(->> (if (and (= c \A) (>= i X) (< (+ i X) N))
(let [
l (nth memo (- i X))
r (nth memo (+ i Y))]
(+ (* (l \P) (r \B)) (* (l \B) (r \P))))
0)
(+ acc)))
0
C))))
(get-match-count "data/input1.txt")
package main
import (
"bufio"
"fmt"
"log"
"os"
"strconv"
)
const CAP = 300001
func readFile(filename string) []string {
f, _ := os.Open(filename)
defer f.Close()
scanner := bufio.NewScanner(f)
scanner.Buffer(make([]byte, CAP), CAP)
buf := make([]string, 0, 4)
for scanner.Scan() {
buf = append(buf, scanner.Text())
}
if err := scanner.Err(); err != nil {
log.Fatal(err)
}
return buf
}
func getMatchCount(N int32, C string, X int32, Y int32) int64 {
cnt := int64(0)
w := Y - X + 1
memo := make([]map[byte]int64, N+w)
prev := make(map[byte]int64)
for i := int32(0); i < N+w; i++ {
if i < N {
prev[C[i]]++
}
if i >= w {
prev[C[i-w]]--
}
memo[i] = map[byte]int64{'P': prev['P'], 'B': prev['B']}
}
for i := int32(0); i < N; i++ {
if C[i] == 'A' {
if i-X >= 0 && i+X < N {
l, r := memo[i-X], memo[i+Y]
cnt += l['P']*r['B'] + l['B']*r['P']
}
}
}
return cnt
}
func main() {
buf := readFile("data/input1.txt")
N, _ := strconv.Atoi(buf[0])
C := buf[1]
X, _ := strconv.Atoi(buf[2])
Y, _ := strconv.Atoi(buf[3])
fmt.Println(getMatchCount(int32(N), C, int32(X), int32(Y)))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment