DEV Community: WolfOf420Stret

I Built an AI Land Fraud Detector for Kenya — Here's the Full Engineering Story

WolfOf420Stret — Wed, 20 May 2026 11:55:20 +0000

"In God We Trust. In Land We Verify."

The Problem Is Personal

In Kenya, land is not just an asset. It is identity. Families save for decades to buy a small shamba. It is the thing you show your children. The thing that says you made it.

And it is being stolen — systematically, at scale, with forged documents and complicit officials — from ordinary people who have no way to fight back.

The most brutal variant is called "air supply": a fraudster markets a plot of land that does not legally exist. They have a polished brochure, a site visit to a real-looking location, and a convincing sale agreement. The buyer pays. The title deed never comes. By the time they discover the fraud — sometimes years later — the money is gone and the legal system offers little recourse.

The Lesedi Developers scandal is the most notorious recent example: thousands of prospective homeowners lost over Sh1 billion to phantom estates in Nairobi's satellite towns. Juja. Ruiru. Thika. Real places. Fake plots.

This is the problem I set out to solve here using this Code

The Hackathon That Pushed Me to Build It

I submitted TitleTrust to the 2026 Google Gemini 3 Hackathon. The timing was right: Gemini 3 Pro's native multimodality, two-million-token context window, and "Thinking Mode" made it the first model powerful enough to reason about the chain of title in the way a forensic auditor would — not just retrieve facts, but detect what is missing, what is temporally impossible, and what is legally void.

This is not a chatbot wrapper. This is an autonomous investigation agent.

What TitleTrust Actually Does

Let me describe the product as a user experiences it, then I'll explain the engineering underneath each step.

1. The Investigator Opens a Session

A field investigator — a community advocate, a local official, a buyer's agent — opens TitleTrust on their phone and starts a new investigation. They upload the "deal pack": a Title Deed, a Green Card (the official registry history), a Mutation Form (subdivision records), and a Sale Agreement.

The session starts. A live timeline appears on screen. The agents go to work.

2. The Forensic Agent Reads the Documents

The ForensicEngine (backend/forensic_engine.py) takes the uploaded images and PDFs and runs them through Gemini 3 Pro with structured prompts that force chain-of-thought reasoning.

It does not just OCR the documents. It reasons about them.

It extracts every date, every transaction, every party name — and then checks:

Can you transfer land before you legally own it? (No.)
Can a Discharge of Charge predate the Charge itself? (No — but forged Green Cards try.)
Is the Surveyor on the Mutation Form licensed? (Cross-referenced against gazette records.)
Does the sum of the subdivided plots exceed the Mother Title's area? (If yes: oversubscription fraud.)

Why Gemini Thinking Mode matters here: standard LLMs hallucinate compromises when laws conflict. A County Zoning map might say "Residential" while the National Land Act says "Riparian Reserve." Gemini 3's include_thoughts=True forces the model to reason through the hierarchy — National Law overrides County Law — and produce a defensible verdict with a visible reasoning trace. That trace is not a nice-to-have. In this context, the reasoning trace is the product. An investigator, a lawyer, or a judge needs to see why the AI flagged something, not just that it did.

3. The Location Agent Checks Physical Reality

The GeospatialEngine (backend/geospatial_engine.py) answers a different question: does the land exist where they say it does?

The most insidious fraud variant is the bait-and-switch: the buyer is taken to a beautiful, flat, accessible plot. The title deed they receive is for a swamp 5km away.

The investigator stands on the land, captures GPS and photos. The GeospatialEngine:

Validates GPS traces against the parcel geometry from the deed
Runs plausibility checks: distance-to-boundary, location confidence heuristics
Detects riparian vegetation patterns that suggest the plot is in a protected river reserve
Emits a geospatial_verification event: either "Location verified" or "Location mismatch — please re-scan beacons"

If the Solar API data shows the claimed plot is in a flood zone. If the 30-metre riparian buffer overlay shows 60% of the plot is legally unbuildable. The investigator knows before they pay.

4. The Orchestrator Keeps the Investigation Moving

The MarathonLoop (backend/agent/marathon_loop.py) is the job state machine that coordinates everything. It:

Starts when a session is created
Advances through investigation stages
Decides what to check next (without the investigator having to think about it)
Retries failed API calls with exponential backoff
Escalates to the user when human input is genuinely needed: "Please provide a clearer photo of the beacon in the northeast corner"

It is designed to behave like an assistant-led investigation. The field investigator should not need to understand conveyancing law. They follow prompts. The system reasons.

5. The Mobile Client Shows Everything, Live

The Flutter client maintains a live, deduplicated, sequence-aware timeline of all agent activity. Every finding. Every evidence registration. Every verification step.

This is not just UX polish. For an investigation tool, the live timeline is the audit trail that an investigator presents to authorities. It needs to be complete, ordered, and reproducible — even if the phone lost signal for ten minutes in the middle of a rural field check.

The Engineering Architecture — Every Decision Tied to the Product

Here is where most case studies go wrong: they describe the architecture and then separately describe the product. In TitleTrust, every engineering decision was made because of a product constraint. Let me walk through them.

Why SSE Instead of WebSockets

The field investigator is standing in Juja, on cheap mobile data, with an intermittent signal. WebSockets require a persistent bidirectional connection. When it drops, you rebuild state from scratch.

SSE (Server-Sent Events) with Last-Event-ID gives you something better: the browser (and Flutter client) automatically reconnects and sends the last event ID it received. The server replays from exactly that point. The investigator's timeline heals itself without them noticing.

For a progress-update use case — which is all we need for server→client communication — SSE is simpler, more resilient on mobile networks, and natively supports replay semantics.

Why Redis Streams (Not Just a Message Queue)

A standard message queue delivers messages and forgets them. That is fine for background jobs. It is not fine for an investigation audit trail.

Redis Streams is an append-only, ordered log. Every event is stored with a stable offset. When the mobile client reconnects after a signal drop, the server can replay the exact sequence of agent actions from the last confirmed point.

More importantly: after an investigation closes, a lawyer needs to reconstruct exactly what the agent found, in what order, with what evidence. Redis Streams is that record. It is not just infrastructure — it is the chain of custody.

Why Two Cursors (`event_id` + `stream_offset`)

Every event carries two identifiers:

event_id: a stable application-level UUID the client tracks across reconnections
stream_offset: the Redis Streams position for efficient server-side seeks

The client knows event_id. The server knows stream_offset. The resume logic maps between them.

Why both? Because event_id survives Redis restarts and re-ingestions — it is stable application identity. stream_offset gives the server an efficient seek into the durable log. Without both, you either replay too much (wasteful) or risk replaying from the wrong point (incorrect).

For an investigation where every event is a piece of evidence, incorrect replay is a correctness bug, not just a performance bug.

Why In-Process Broadcaster + Redis Streams (The Hybrid)

The Broadcaster (backend/realtime/broadcaster.py) maintains both an in-memory local fanout queue and a durable Redis Streams append.

The in-memory queue delivers events to the SSE client in milliseconds — even when Redis has a hiccup. The Redis Streams append persists the event for replay and audit.

In degraded mode (Redis unavailable), the system flips a flag, continues local delivery, and the client can recover authoritative state from Firestore when connectivity returns. The investigator's timeline keeps updating. They never see a spinner.

The product constraint driving this: an investigator doing a site visit in a low-connectivity area should not have their session stall because a Redis instance is momentarily unreachable. Availability for the user is non-negotiable. But so is the audit trail. The hybrid gives you both.

Why Evidence Gets SHA256 Checksums and Trace IDs

Every piece of evidence the ForensicEngine registers — every photo, every document analysis result — gets:

A SHA256 checksum of the content
A trace_id linking it across services
A sequence_id for ordering within the session

This is not engineering over-engineering. This is chain of custody. If an investigator presents TitleTrust findings to a Land Control Board or a court, the evidence must be verifiable as unmodified and correctly attributed. The checksum proves content integrity. The trace ID proves provenance. The sequence ID proves ordering.

Why Deterministic Chaos Tests

Before any public deployment of a system that people will rely on to protect their life savings, I needed to be able to prove the system behaves correctly under failure — not just hope it does.

The test harness (tests/test_realtime_chaos.py, tests/support/fake_redis.py) includes:

A fake Redis that can be programmatically failed, truncated, or made to reject writes
A failure injector that simulates xadd failures, publish delays, and partial persistence
Tests that validate: sequence monotonicity, correct replay after Redis restart, fallback to local buffer, client convergence to authoritative state after gap detection

Real bugs surfaced in this harness that would never have appeared in happy-path testing:

Prometheus collector collisions when test instances reused metric names
Replay mismatches when clients passed a non-Redis ID as the resume token
Accidental use of non-durable items as the authoritative replay source

The product argument for this: stochastic integration tests find bugs sometimes. Deterministic failure injection finds bugs reproducibly. For a correctness-critical system, reproducible is the only acceptable standard.

Architecture Diagram

┌─────────────────────────────────────────────────────────┐
│              Flutter Mobile Client                      │
│  RealtimeController: dedupe, sequence, gap detection    │
│  RecoveryCoordinator: authoritative Firestore recovery  │
└────────────────────┬────────────────────────────────────┘
                     │ SSE (Last-Event-ID)
                     ▼
┌─────────────────────────────────────────────────────────┐
│                FastAPI Backend                          │
│  /realtime/sse  ·  /realtime/last-state/{session_id}   │
└────────────────────┬────────────────────────────────────┘
                     │
                     ▼
┌─────────────────────────────────────────────────────────┐
│                   Broadcaster                           │
│  In-process bounded queues (low-latency local fanout)  │
│  Redis Pub/Sub (cross-instance fanout)                  │
│  Redis Streams (durable ordered log + replay)           │
└──────┬──────────────────────┬───────────────────────────┘
       │                      │
       ▼                      ▼
┌─────────────┐     ┌──────────────────────────────────┐
│  Redis      │     │  Agent Workers                   │
│  Streams    │     │  MarathonLoop (orchestrator)     │
│  (durable   │     │  ForensicEngine (vision/docs)    │
│   log)      │     │  GeospatialEngine (GPS/maps)     │
└─────────────┘     └──────────────┬───────────────────┘
                                   │
                                   ▼
                         ┌──────────────────┐
                         │    Firestore     │
                         │  (canonical      │
                         │   session state) │
                         └──────────────────┘

A Day in the Life: One Investigation

To make this concrete, here is the complete flow for a single field check:

Investigator uploads a deal pack (Title Deed, Green Card, Mutation Form) via the Flutter app.
Session created in Firestore. MarathonLoop starts. A session_started event is emitted, broadcast locally, appended to Redis Streams.
ForensicEngine runs: Gemini 3 Pro reads the Green Card. It finds Entry #4: Charge to Equity Bank, 12/01/2018 and Entry #6: Discharge of Charge, 10/01/2018. The Discharge predates the Charge. Temporal anomaly flagged. Evidence registered with SHA256 checksum and trace ID. evidence_registered event emitted.
The timeline on the investigator's phone updates instantly via SSE. They see: "⚠️ Temporal anomaly detected — Discharge of Charge predates Charge. Likely forgery."
Investigator walks the plot boundary and captures GPS + photos. GeospatialEngine validates location. Finds: plot coordinates overlap 60% with the Athi River 30m riparian buffer. Critical risk flagged. geospatial_verification event emitted.
Phone signal drops for 4 minutes. Client reconnects with Last-Event-ID. Server maps it to Redis stream offset. Replays the 3 events the client missed. Timeline is complete.
Investigation complete. MarathonLoop emits investigation_complete with a risk score of 91 (CRITICAL). The full event log — ordered, checksummed, traceable — is the audit trail the investigator presents to the Land Control Board.

What I Used Gemini 3 For Specifically

This is important because I did not use Gemini 3 as a chatbot. I used it as a reasoning engine embedded in a structured investigation workflow.

Thinking Mode (include_thoughts=True) — for legal conflict resolution. When a County Zoning map conflicts with the National Land Act, I cannot use a black-box verdict. The reasoning trace showing why one law overrides another is what makes the output usable in a legal context.

Native multimodality — for reading handwritten Green Cards. Kenya's registry history is often handwritten, sometimes in cursive, on physical cards. Gemini 3 Pro reads these without a separate OCR step, preserving spatial context (stamps over signatures, marginal notes) that traditional OCR loses.

2M token context window — for tracing chain of title through decades of subdivisions. A Mother Title in Kiambu might have 50+ years of subdivision history. Fitting the complete legal history in a single context window enables the kind of deep chronological reasoning that was previously only possible for senior conveyancing lawyers charging Ksh 10,000+ per review.

Structured outputs — for emitting machine-readable findings. Every ForensicEngine result is a typed JSON finding, not free text. This is what allows the mobile timeline to render findings as UI components rather than just paragraphs.

The Numbers

What	Why it matters
~Ksh 500 per basic forensic check	vs Ksh 5,000–10,000 for a lawyer
~3 minutes for a full audit	vs 30 days for traditional due diligence
SHA256 checksums on all evidence	Chain of custody for legal proceedings
Deterministic chaos tests	Correctness provable, not assumed
Degraded mode (Redis down)	Investigators never lose session continuity

Key Engineering Takeaways

1. Tie every infrastructure decision to a user outcome.
Redis Streams exists because investigators need an audit trail, not because append-only logs are cool. SSE exists because mobile reconnection in rural Kenya needs to be seamless. When you can answer "why does this exist?" with a user story, your architecture stays honest.

2. The reasoning trace is the product.
For AI systems used in high-stakes decisions — land fraud, medical diagnosis, legal analysis — the output is not the verdict. The output is the evidence behind the verdict. Design your AI integration accordingly.

3. Deterministic failure injection is the only way to prove correctness.
Stochastic tests find bugs sometimes. Deterministic failure injection finds them reproducibly. For a system that people will rely on to protect their life savings, "probably works" is not good enough.

4. Hybrid realtime (local fanout + durable stream) is the right model for mobile-first AI systems.
Local in-memory fanout keeps UX responsive under partial failures. Redis Streams provides the durable, replayable log for recovery and audit. You do not have to choose between fast and correct.

What's Next

Shadow Registry: a crowdsourced, hashed double-allocation detector. When two independent investigators verify the same plot, the system flags a potential double sale — without exposing either party's identity until a match is confirmed.
Case Law RAG: grounding forensic reasoning in Kenya Law Reports (eKLR) for land dispute precedents.
Blockchain title anchoring: publishing investigation hashes to an immutable ledger so findings cannot be retroactively modified.
Hardware-backed device attestation: for high-assurance deployments where the physical device must be cryptographically verified.

The Repo

The codebase is organized around clear responsibility boundaries:

File	Purpose
`backend/realtime/broadcaster.py`	In-process fanout, Redis Pub/Sub, degraded mode
`backend/realtime/store.py`	Redis Streams event store, two-cursor resume logic
`backend/agent/marathon_loop.py`	Orchestration, job lifecycle, event emission
`backend/forensic_engine.py`	Vision analysis, evidence registration, checksumming
`backend/geospatial_engine.py`	GPS/parcel validation, spatial event emission
`frontend/titletrust/lib/realtime/realtime_controller.dart`	Dedupe, sequence tracking, authoritative recovery
`tests/test_realtime_chaos.py`	Deterministic chaos suite
`tests/support/fake_redis.py`	Programmatic Redis failure injection

Final Thought

Land fraud in Kenya is not a technology problem. It is a power problem: the people who commit it have access to systems, officials, and legal processes that ordinary buyers do not. TitleTrust does not fix that power imbalance by itself.

But it gives ordinary people — investigators, buyers, community advocates — the same forensic tools that a senior lawyer and a licensed surveyor would use. For Ksh 500 and three minutes instead of Ksh 10,000 and thirty days.

That is the point. The engineering exists to serve that point.

If you are building AI systems for high-stakes decisions in emerging markets, I would love to talk. The problems are real, the constraints are severe, and the standard tooling assumptions often do not hold.

Built with Gemini 3 Pro, FastAPI, Flutter, Redis Streams, and Firebase. Submitted to the Google Gemini 3 Hackathon, 2026.

Building AdMidnight: A Privacy-Preserving Ad Platform on the Midnight Blockchain

WolfOf420Stret — Tue, 19 May 2026 17:28:19 +0000

How I built a zero-knowledge ad-tech stack in a weekend using AI-assisted development, Midnight's programmable data protection, and a lot of coffee.

"The best ads are the ones you actually want to see — but that shouldn't
require surrendering your entire digital life to get there."

I built AdMidnight at the Midnight Hackathon — a
privacy-preserving ad-tech platform where advertisers can target users
by behavioral segment without ever seeing raw user data, users get
verifiably rewarded for their attention, and every settlement happens
transparently on-chain. No surveillance. No data brokers. Just
zero-knowledge proofs doing what they were designed to do.

This article is the full story: the problem, the technology, the
architecture decisions, the AI-assisted development workflow, the
safeguards we put in place, and every ugly thing that broke at 2am.

The Problem with Advertising
What is Midnight?
The MLH Hackathon Context
Architecture Overview
The ZK Proof Flow
Building the Stack
AI-Assisted Development
Code Review with CodeRabbit
Safeguards and Quality Gates
The Ugly Parts
What I'd Do Differently
What's Next

The Problem with Advertising

Digital advertising as it exists today is a privacy disaster. The
current model works roughly like this:

You visit a website
A tracker records your behavior
That data gets sold to a data broker
An advertiser buys a profile that includes you
You see an ad
You have no idea any of this happened and received nothing for it

The advertiser paid for your attention. The platform took the money.
You got nothing except a feeling of being watched.

The technical problem is equally bad on the advertiser side. To
target effectively, advertisers need behavioral signals — but those
signals are locked inside walled gardens (Google, Meta, Apple).
Every ad network that wants to compete has to either build its own
surveillance infrastructure or pay the gatekeepers.

There's a better model. What if:

Users computed their own behavioral embedding locally on their device
A ZK proof attested "this user matches segment X" without revealing why they match
Advertisers bid on that proof, not on the user's identity
The whole settlement happened on a public ledger with no single party controlling the data

That's AdMidnight.

What is Midnight?

Midnight is a data protection blockchain
built by Input Output (the team behind Cardano). It's designed for
exactly this kind of use case: applications where you need the
auditability of a public blockchain but the privacy guarantees of
zero-knowledge cryptography.

Programmable Data Protection

What makes Midnight different from other ZK-enabled chains is its
concept of programmable data protection. Rather than bolting privacy
onto an existing smart contract model, Midnight was designed from the
ground up with two distinct data zones:

Public state: visible on-chain to everyone (aggregate counters, settlement hashes, nullifier sets)
Private state: shielded by ZK proofs, accessible only to the data owner

This isn't just confidential transactions. It's a full smart contract
model where you can write logic that operates over private inputs
without those inputs ever being revealed to validators or other
participants.

Compact: Midnight's Contract Language

Midnight contracts are written in Compact, a domain-specific
language designed for ZK circuit compilation. A Compact contract
looks superficially like TypeScript but compiles down to arithmetic
circuits that can generate and verify zero-knowledge proofs.

Here's a simplified example of what an AdMidnight match registry
looks like in Compact:

// AdMatchRegistry.compact

circuit proveSegmentMatch(
  segmentId: Bytes<32>,
  campaignId: Bytes<32>,
  nullifier: Bytes<32>,
  commitmentHash: Bytes<32>
): Boolean {
  // Verify this nullifier hasn't been used before
  assert !claimedNullifiers.member(nullifier);

  // Record the impression
  campaignImpressions.set(
    campaignId,
    campaignImpressions.lookup(campaignId) + 1
  );

  // Mark nullifier as spent
  claimedNullifiers.insert(nullifier);

  return true;
}

The key insight: nullifier is a private input. The circuit proves
it's valid without the chain ever knowing what it is. Double-spend
prevention works through the nullifier set — but the nullifier itself
is a hash of the user's private data, so it reveals nothing.

The Midnight SDK

Midnight provides a TypeScript SDK for connecting to contracts from
off-chain applications. The SDK handles:

Provider setup (wallet, ZK proof generation, transaction submission)
Contract deployment and address management
callTx wrappers for circuit invocations
Indexer queries for reading contract state

The SDK is ESM-only and fairly new, which caused some interesting
integration challenges with NestJS (more on that later).

The MLH Hackathon Context

Major League Hacking (MLH) runs hundreds of hackathons a year, from
24-hour sprints to week-long builds. This event was a Midnight Hackathon
hackathon with a focus on opportunity to build on a fully launched network designed to solve the internet's biggest privacy challenges.

The Rules That Shaped the Build

MLH hackathons have strict rules that actually make you a better
engineer:

No prior work: everything must be built during the event weekend. This forces you to make architecture decisions fast and commit to them.
Public repo: your code must be public and stay public. This makes you think about what you're actually committing.
2-minute demo video: ruthless constraint on scope. If you can't explain it in 2 minutes, you haven't understood it.
Team size max 4: I went solo, which meant every architectural decision was mine to live with.

Going solo at a hackathon in 2026 is a different experience than it
was even two years ago. AI tooling has genuinely changed what one
person can ship in a weekend. But it comes with its own set of
traps — more on that in the AI section.

Architecture Overview

AdMidnight is a monorepo with four main execution layers:

apps/
  api/                    # NestJS + Fastify backend
  advertiser-dashboard/   # Next.js 14 App Router
  mobile/                 # Flutter (on-device ZK)

packages/
  zk-circuits/            # Midnight Compact contracts
  midnight-sdk-wrapper/   # ESM bridge for Midnight SDK
  shared/                 # Shared types and DTOs

Why a Monorepo?

The shared types between the API and dashboard were the deciding
factor. When the API returns a CampaignResponseDto, I want the
dashboard to have the exact same TypeScript type without copying.
pnpm workspaces made this straightforward with local package
references.

The Four Execution Layers

Layer 1: Advertiser Dashboard (Next.js 14)

Server components fetch data directly from the API using the session
cookie. Client components handle form interactions. The App Router's
layout system handles auth gating via middleware — unauthenticated
requests to /campaigns/* redirect to /login before they hit
the server component.

Layer 2: NestJS API

The API is the trust boundary. It validates every request with
NestJS global validation pipes, enforces JWT auth via guards, and
is the sole path from the application layer into the Midnight
contracts. Nothing touches the contracts except through
MidnightGateway.

Key modules:

AuthModule — JWT issuance, cookie management
AdvertiserModule — campaign CRUD, auction flow
UserModule — proof submission, reward claims
PublisherModule — impression registration, revenue
MidnightModule — gateway, provider service, indexer queries

Layer 3: Flutter Mobile App

The mobile app is where the privacy guarantee lives. The user's
behavioral embedding never leaves the device. The app:

Fetches active segment definitions from /user/segments/available
Computes a 128-dimensional embedding from local behavioral signals
Runs cosine similarity against segment centroids
If threshold met, calls the ZK proof engine to build a proof envelope
Submits only proofBytes + publicInputs + generatedAt to the API

The raw embedding — the thing that actually reveals user behavior —
never hits a network request.

Layer 4: Midnight Compact Contracts

Three contracts handle the on-chain state:

AdMatchRegistry: impression counting, nullifier set, segment registry
AdAuction: sealed bid commitments, reveal phase, winner settlement
UserReward: reward escrow, claim verification, spend tracking

The contracts are compiled from Compact source and deployed to the
Midnight devnet. Contract addresses are stored in .env.local after
deployment and referenced by the API gateway.

The ZK Proof Flow

This is the core of the system. Here's the full sequence:

Mobile App                    NestJS API              Midnight Ledger
    │                              │                        │
    │  Load segment centroids      │                        │
    │ ◄────────────────────────── │                        │
    │                              │                        │
    │  [Local computation]         │                        │
    │  - Compute embedding         │                        │
    │  - Cosine similarity check   │                        │
    │  - Build ZK proof envelope   │                        │
    │                              │                        │
    │  POST /user/proof/match      │                        │
    │  { proofBytes,               │                        │
    │    publicInputs,             │                        │
    │    generatedAt }             │                        │
    │ ────────────────────────── ► │                        │
    │                              │  verifyAndBind         │
    │                              │  submitMatchProof      │
    │                              │ ──────────────────── ► │
    │                              │                        │  proveSegmentMatch()
    │                              │                        │  - Check nullifier
    │                              │                        │  - Increment counter
    │                              │                        │  - Escrow reward
    │                              │ ◄────────────────────  │
    │                              │  txHash                │
    │ ◄────────────────────────── │                        │
    │  { valid: true,              │                        │
    │    rewardEscrow,             │                        │
    │    relayTxHash }             │                        │

Why Nullifiers?

The nullifier pattern is how ZK systems prevent double-spending
without revealing identity. Here's the intuition:

The user generates nullifier = hash(privateKey + campaignId + salt)
The nullifier is included as a public input to the proof
The contract checks that this nullifier isn't in claimedNullifiers
After the proof is accepted, the nullifier is added to the set

An observer sees: "a nullifier was spent". They do not see: "which
user spent it". The nullifier is a commitment to the user's identity
without revealing it.

The Sealed Bid Auction

The auction uses a commit-reveal scheme:

Commit phase: advertiser submits commitmentHash = hash(actualBid + nonce)
Reveal phase: advertiser submits actualBid and nonce
Settlement: contract verifies hash(actualBid + nonce) == commitmentHash on-chain

This prevents front-running. Other bidders can see that a commitment
exists but cannot learn the bid value until reveal. By then, the
commitment is already locked on-chain.

Building the Stack

Day 1: Foundation

The first day was architecture and scaffolding. I set up the monorepo
with pnpm workspaces, got the NestJS app bootstrapping, and wrote
the Prisma schema.

The Prisma schema ended up being the most important design document
for the whole project. Getting the data models right early meant
the API handlers almost wrote themselves:

model Campaign {
  id              String   @id @default(cuid())
  advertiserId    String
  title           String
  status          String   @default("DRAFT")
  budgetMidnight  String
  cpmBidMidnight  String
  startTime       DateTime
  endTime         DateTime
  onChainTxHash   String?

  advertiser      Advertiser @relation(fields: [advertiserId], 
                                       references: [id])
  bids            Bid[]
  proofRecords    ProofRecord[]

  createdAt       DateTime @default(now())
  updatedAt       DateTime @updatedAt
}

Day 2: The Hard Parts

Day 2 was Midnight integration and the Flutter ZK engine. These were
the two highest-risk components — both used bleeding-edge SDKs that
I hadn't worked with before.

The Midnight SDK integration hit an immediate wall: the SDK is
ESM-only but NestJS compiles to CommonJS. In a normal project you'd
just configure "type": "module" in package.json and move on. With
NestJS that breaks the entire DI system.

The fix was a midnight-sdk-wrapper package that builds with
"module": "CommonJS" in its tsconfig, giving NestJS a CJS-compatible
entry point. The wrapper re-exports only what the API needs, keeping
the surface area small.

The Flutter ZK engine was more straightforward. The proof generation
logic lives in zk_proof_engine.dart and uses Dart's isolate
system to run the computation off the main thread:

Future<ProofEnvelope> generateMatchProof({
  required List<double> userEmbedding,
  required List<double> segmentCentroid,
  required double threshold,
  required String campaignId,
  required String segmentId,
}) async {
  return await Isolate.run(() async {
    final similarity = _cosineSimilarity(
      userEmbedding, 
      segmentCentroid
    );

    if (similarity < threshold) {
      throw ProofGenerationException('Below threshold');
    }

    final nullifier = _generateNullifier(campaignId);
    final proofBytes = await _buildZKProof(
      similarity, nullifier, campaignId, segmentId
    );

    return ProofEnvelope(
      proofBytes: proofBytes,
      publicInputs: PublicInputs(
        segmentId: segmentId,
        campaignId: campaignId,
        isMatch: true,
        nullifier: nullifier,
      ),
      generatedAt: DateTime.now().toIso8601String(),
    );
  });
}

The Monorepo Build Problem

With four packages and two apps, the build order matters. pnpm
workspaces handles this via the dependency graph, but Docker builds
don't understand workspace protocols. The Dockerfile needs to copy
the full monorepo context and run filtered installs:

FROM node:20-alpine AS base
RUN npm install -g pnpm

WORKDIR /app
COPY pnpm-workspace.yaml package.json pnpm-lock.yaml ./
COPY packages/ ./packages/
COPY apps/api/ ./apps/api/

RUN pnpm install --filter @admidnight/api... --frozen-lockfile
RUN pnpm --filter @admidnight/api run build

The --filter @admidnight/api... flag (note the ...) tells pnpm
to install the API and all its workspace dependencies. Without the
ellipsis you only get the API's direct dependencies, not the
transitive workspace packages.

AI-Assisted Development

I want to be honest about how I used AI on this project, because I
think the honest version is more useful than the sanitized version.

What Worked Well

Boilerplate generation: NestJS modules follow a rigid pattern —
controller, service, module, DTOs, guards. Generating the initial
scaffold for each module with an AI assistant saved probably 3-4
hours of typing.

Error message interpretation: When you're working with a new SDK
and hitting cryptic TypeScript errors, having an AI that can parse
the error, trace it back to the type definitions, and suggest a fix
is genuinely useful. The ESM/CJS issue with the Midnight SDK was
diagnosed in minutes rather than hours.

Prompt-driven architecture review: I used Claude as a sounding
board for architectural decisions. "Given this constraint, what's
the tradeoff between approach A and approach B?" is a great use of
AI — it forces you to articulate the constraint clearly, and the
response gives you angles you might not have considered.

Documentation: The README, API reference, and this article were
all drafted with AI assistance. The structure and technical accuracy
are mine; the AI helped with prose flow and completeness checking.

What Didn't Work

Long autonomous runs: I gave the AI agent long multi-step
prompts and let it run for extended periods. This is where things
went wrong. The agent would fix one issue, introduce a new one,
fix that, loop back to a previous state, and spend an hour going
in circles on a problem that needed a 5-minute human decision.

The specific failure mode was the Docker build. The agent kept
trying increasingly complex fixes (esbuild transforms, custom
predev scripts, lazy imports) for a problem that had a simple
root cause: the API shouldn't run in Docker during development
at all. That was a 30-second architectural decision. The agent
couldn't make it because it requires stepping back from the
immediate error.

Lesson: give AI agents tightly scoped tasks with clear
success criteria. "Fix this one error and tell me when it's
done" works. "Fix everything until the demo runs" does not.

Type correctness: AI-generated NestJS code had a systematic
bug throughout: injectable dependencies were imported as
import type { Service } instead of import { Service }.
TypeScript type-only imports are erased at compile time, which
breaks NestJS's reflection-based dependency injection at runtime.
The AI never caught this pattern because it's valid TypeScript —
it just doesn't work with NestJS's decorator metadata system.

Lesson: AI knows TypeScript. AI does not always know framework
constraints that diverge from standard TypeScript behavior. You
still need to know your framework.

The Workflow That Actually Worked

By day 2 I had settled on this pattern:

I write the architecture decision (which module, what responsibility, what the interface looks like)
AI generates the implementation (the controller, the service, the DTOs)
I review the output before running it (5 minutes of reading is worth an hour of debugging AI-generated bugs)
I write the test or at minimum the curl command that proves it works
AI fixes failures from the test output with a tight prompt: "this curl returns 400, here's the response body, here's the DTO, fix the validation"

This kept the AI in the implementation lane and me in the
architecture lane. It's roughly 10x faster than writing everything
myself and much more reliable than giving the AI architectural
autonomy.

Code Review with CodeRabbit

CodeRabbit is an AI-powered code review
tool that integrates directly with GitHub pull requests. On a solo
hackathon project it fills a critical gap: you have no teammates to
catch your blind spots.

What CodeRabbit Caught

Security issues: CodeRabbit flagged a route in the advertiser
module where the campaign ownership check happened after the database
fetch rather than in the query itself. An advertiser could request
analytics for any campaign ID and get a response before the
authorization check fired. The fix was a one-line Prisma where
clause addition, but it's exactly the kind of thing you miss when
you're moving fast.

Missing input validation: The segmentConfig.centroid array
needed to be exactly 128 entries. The DTO had @IsArray() but not
@ArrayMinSize(128) or @ArrayMaxSize(128). CodeRabbit caught the
missing size constraints.

Unhandled promise rejections: Several service methods had
await prisma.something() without try-catch in error paths.
CodeRabbit flagged these as unhandled rejection risks. In NestJS
this will crash the process rather than returning a 500 to the client.

Overly broad CORS: The initial CORS configuration used
origin: '*' which is fine for development but CodeRabbit correctly
flagged it as a production concern and suggested the env-variable
pattern.

The Review Workflow

I ran CodeRabbit on every commit to the main branch. The workflow:

Push a feature branch
Open a PR (even on a solo project — PRs give you a review surface)
CodeRabbit posts a summary and line-level comments within minutes
Address the comments before merging
Merge when CodeRabbit shows no critical issues

On a 48-hour hackathon this might sound like overhead, but it
actually saves time. Catching a security issue during review is
10 minutes. Catching it after you've built three more features
on top of it is an afternoon.

Safeguards and Quality Gates

Building fast doesn't mean building recklessly. These were the
non-negotiable safeguards:

Never Expose Raw User Data

This was the architectural principle everything else flowed from.
The rule: user embeddings never leave the device. If I ever found
myself writing code that sent raw behavioral data to the API, that
was a design failure to fix, not a compromise to accept.

In practice this meant:

The mobile app's proof engine runs in an isolate with no network access
The API accepts only proofBytes + publicInputs — no raw vectors
The Prisma schema has no column for user embeddings

Environment Variable Discipline

No secrets in code. Ever. The Zod config schema at
apps/api/src/config.ts validates every required environment
variable at startup and throws with a descriptive error if any
are missing. The .env.example file documents every variable
with safe placeholder values. The .gitignore excludes .env
and .env.local.

Input Validation Everywhere

NestJS global validation pipes with whitelist: true and
forbidNonWhitelisted: true. This means:

Unknown properties on request bodies are rejected, not ignored
Every DTO field is validated before it reaches a controller
Type coercion only happens where explicitly configured

The segmentConfig.centroid validation is worth calling out
specifically:

@IsArray()
@ArrayMinSize(128)
@ArrayMaxSize(128)
@IsNumber({}, { each: true })
@Min(-1, { each: true })
@Max(1, { each: true })
centroid: number[];

A malformed centroid could corrupt the cosine similarity calculation.
Validate at the boundary.

MIDNIGHT_DEV_MODE

The Midnight devnet is not always available. During development
and CI, MIDNIGHT_DEV_MODE=true causes the gateway to return
realistic mock responses instead of attempting on-chain calls.
This is implemented as a guard at the gateway layer — not scattered
through service logic:

if (this.devMode) {
  return {
    success: true,
    data: {
      txHash: `0xdev_${Date.now()}`,
      relayTxHash: `0xrelay_${Date.now()}`,
    }
  };
}
// Real gateway call below

The mock returns the same shape as the real response so the rest
of the application can't tell the difference.

The Ugly Parts

No article about a hackathon build is complete without honesty
about what broke.

The `import type` Bug

Every injectable service in the initial AI-generated code used
import type { Service } for its dependencies. NestJS uses
TypeScript decorator metadata (reflect-metadata) to resolve
constructor parameter types at runtime. Type-only imports are
erased by the TypeScript compiler, so the metadata is never
written. Result: Nest can't resolve dependencies of the X (?)
errors across every module.

The fix was a global sed across the codebase:

find src -name "*.ts" | xargs sed -i '' \
  's/import type { \([A-Za-z]*Service\) }/import { \1 }/g'

The Docker Build Loop

I spent several hours trying to get the API running inside Docker
while the Midnight SDK's ESM-only nature caused the build to fail
in increasingly creative ways. The correct decision — run the API
locally during development, only containerize Postgres and the
Midnight infrastructure — was obvious in retrospect but took too
long to reach.

The rule I'll carry forward: containerize stateful infrastructure,
run stateless applications locally during development. Docker is
not a debugging environment.

The Proof Server Image Tag

The Midnight proof server Docker image had a breaking tag change
between the version in the original compose file and the latest
available image. bricktowers/proof-server:8.0.3 did not exist.
7.0.0 did. This was a 30-minute debugging session that should
have been a 30-second check.

Rule: always pin Docker image tags to versions you have verified
exist. Never use latest in a project you care about.

What I'd Do Differently

Start with the Makefile. The demo runner, e2e tests, and
service startup scripts should be the first thing you write, not
the last. Every hour you spend on "how do I run this?" during the
hackathon is an hour not spent building.

Shorter AI agent prompts with tighter success criteria.
"Run this curl, fix the specific error it returns" is a good
agent prompt. "Make everything work" is not. The agent doesn't
know when to stop.

Review AI output before running it. Five minutes of reading
prevents an hour of debugging. The import type bug was in the
first file the AI generated. If I'd read it before running it
I'd have caught it immediately.

Validate third-party SDK assumptions early. The Midnight SDK
ESM issue was knowable before I wrote a single line of application
code. A one-hour spike on "can I actually import this SDK in a
NestJS app" would have saved four hours of runtime debugging.

What's Next

AdMidnight is a proof of concept, but the core primitives are real
and the use case is genuine. The roadmap from here:

Real on-device proof generation: The current mobile app uses
a simplified proof scheme. The next step is integrating the full
Midnight proof generation SDK on Flutter via a native bridge,
so the ZK proofs are cryptographically sound, not just structurally
correct.

Publisher SDK: The publisher side of AdMidnight is
underbuilt. A JavaScript SDK that publishers can drop into any
website — similar to a Google AdSense tag but privacy-preserving
by construction — would unlock the distribution side of the
marketplace.

Decentralized segment registry: Right now segments are
registered by advertisers through the API. A fully decentralized
model would let segment definitions live entirely on-chain,
with the mobile app fetching them directly from the Midnight
indexer without going through any centralized API.

Privacy-preserving analytics: The current analytics endpoint
returns aggregate counts. The long-term vision is differential
privacy guarantees on the analytics — so even the aggregate numbers
can't be used to infer individual user behavior.

Closing Thoughts

Privacy-preserving advertising sounds like a contradiction in terms
until you've worked with ZK proofs. The math genuinely allows you
to prove membership in a group without revealing which member you are.
Midnight makes that math accessible to application developers through
Compact and a reasonable SDK.

The hackathon format forced the right kind of discipline: make
decisions fast, ship working software, document the real tradeoffs.
AI tooling made it possible for one developer to build what would
normally require a team — but only because I kept myself in the
architecture seat and the AI in the implementation seat.

The code is at https://github.com/Wolfof420Street/AdMidnight.git.
The demo is at [https://youtu.be/yW8hl8WuggY].

If you're building on Midnight or thinking about privacy-preserving
applications, I'd love to talk. Find me on X at [@fbillionaire__] or
open an issue on the repo.

Built with NestJS, Next.js, Flutter, Midnight Compact, and an
unreasonable amount of determination.

Resources

Eco Trace

WolfOf420Stret — Mon, 20 Apr 2026 06:46:29 +0000

This is a submission for Weekend Challenge: Earth Day Edition

What I Built

EcoTrace is a personal carbon footprint tracker powered by an AI coach that
remembers your eco-journey across sessions (Backboard + Gemini), secured by
Auth0 for Agents, with live emission factor data from Snowflake, NFT achievement
badges minted on Solana, and anonymous community benchmarking that shows exactly
how your footprint stacks up against other users — all inside a Next.js 14 App
Router project with a bioluminescent dark/light UI.

I had no idea how carbon-heavy my daily choices were until I started tracking.
One beef burger equals driving 30 km. A single short-haul flight equals two weeks
of commuting. The data exists — people just never see it mapped to their own life.
EcoTrace fixes that.

Demo

🌍 Live App — ecotrace.vercel.app

Code

🌍 Github

How I Built It

Architecture: Clean, DRY, and SOLID throughout

The biggest technical decision was committing to Clean Architecture from the
start rather than letting a weekend project collapse into a single pages/ mess.
The codebase is split into four strict layers:

Domain — pure TypeScript entities, value objects, and repository interfaces. Zero framework dependencies. CO2Amount is a branded type so you can never accidentally pass a raw number where a validated CO₂ value is expected.
Application — use cases like LogActivityUseCase and GetDashboardDataUseCase that orchestrate domain logic. They depend on interfaces, never on concrete infrastructure classes.
Infrastructure — the real implementations: Supabase, Snowflake, Backboard, Auth0, Solana. Each implements a domain interface and is swappable.
Presentation — Next.js App Router pages, server components, client components, hooks, and the shared UI kit.

Every API route is wrapped with withAuth and withValidation middleware —
defined once, applied everywhere. userId is always sourced from the Auth0 session
on the server, never from request bodies. Supabase Row Level Security enforces
data ownership at the database level as a second line of defence.

Snowflake: Live emission factors + community benchmarking

Instead of hardcoding emission factors, they live in a Snowflake table seeded
from EPA, BEIS, and IPCC sources. When the grid gets greener, the electricity
factor updates in one place and every calculation reflects it instantly.

The second Snowflake table is more interesting: every time a user logs a day's
total, an anonymised row (no user ID, coarse region only) is written to
COMMUNITY_DAILY_TOTALS. A percentile query against that table powers the
dashboard widget that says "you emitted less than 67% of EcoTrace users today."
Turns out that number is surprisingly motivating.

Backboard: AI that actually remembers you

This was the integration I was most sceptical about and ended up being the most
impressive in practice. Every chat message is sent with memory: "Auto" —
Backboard automatically extracts facts from the conversation and retrieves
relevant ones in future sessions. The AI coach genuinely recalls things like
"you told me last week you're trying to go plant-based on Tuesdays" without
any extra work on my end.

Each user gets a persistent Backboard thread ID stored in their Supabase profile.
The AI also receives the user's actual carbon data as a system prompt context on
every request, so it can say "your Tuesday flight was 3x your entire rest-of-week
footprint" rather than giving generic advice.

Auth0 for Agents: Real auth plus a background scanner

Auth0 handles user authentication via Universal Login (Google social, email/password).
The more interesting part is the Token Vault integration: users can connect their
Google Calendar in Settings, and the EcoTrace agent scans for travel-related events
— flights, hotel stays, train journeys — and suggests logging them as carbon
activities. Every suggested item requires explicit user approval before anything
is written (CIBA human-in-the-loop flow). An audit log in Supabase records every
scan and every approval/rejection for transparency.

Solana: On-chain achievement badges

Five badges (common → epic rarity) are minted as compressed NFTs on Solana
devnet using Metaplex Bubblegum. cNFTs cost a fraction of a cent to mint vs
standard NFTs, which makes them practical for an achievement system. The
mint authority keypair lives server-side only — the user connects their Phantom
or Solflare wallet and the server mints to their address. Each minted badge
links to Solana Explorer so it's verifiably permanent, not just a database flag.

GitHub Copilot: The coding co-pilot

Copilot was running throughout the build. The moments where it saved the most
time: autocompleting Recharts gradient fill configuration (I'd never used that
specific API), the Snowflake parameterised query syntax (unfamiliar SDK),
and generating the Zod schema for nested badge threshold types. I'd estimate
it saved 3–4 hours across the weekend — time that went into the UI polish instead.

The UI: "Bioluminescent Data"

The design system is built around two modes that share the same CSS variable
tokens. Dark mode is "Bioluminescent Depths" — deep forest blacks with glowing
green data points. Light mode is "Sunlit Canopy" — warm parchment backgrounds
with deep forest greens. The fonts are Fraunces (editorial display, used for
headlines and the hero), DM Mono (all CO₂ numbers in tabular-nums), and Geist
(body). The carbon score ring is an SVG stroke-dashoffset animated with
Framer Motion spring physics — it colour-shifts from green through amber to red
based on how the day's total compares to the global average.

Prize Categories

Best Use of Backboard — Persistent AI memory via memory: "Auto" on every
message. The EcoTrace AI coach remembers your eco-journey across sessions
without any manual state management. Thread IDs persist per user in Supabase.

Best Use of Auth0 for Agents — Universal Login for user auth plus Token Vault
for the Google Calendar agent scanner, with CIBA async approval so the agent
never logs anything without explicit user confirmation.

Best Use of Snowflake — Emission factors live in Snowflake and are queried
at runtime (not hardcoded). Anonymous community daily totals power a percentile
widget showing how each user compares to the EcoTrace community.

Best Use of Solana — Compressed NFT eco-badges minted on devnet via Metaplex
Bubblegum. Five badge tiers, wallet adapter integration (Phantom + Solflare),
and on-chain verification via Solana Explorer.

Best Use of GitHub Copilot — Used throughout the build for Recharts config,
Snowflake SDK syntax, Zod schema generation, and Metaplex boilerplate.
Documented with screenshots in the repo README.

The Future of Self-Care: How AI is Revolutionizing Personalized Affirmations with Affirmi

WolfOf420Stret — Sun, 10 Aug 2025 22:00:23 +0000

Tired of hearing the same generic "you are enough" every morning? You're not alone. The mental wellness revolution is here, and it's powered by AI that actually gets you.

The Problem with Generic Affirmations: Why One-Size-Fits-All Doesn't Work

Picture this: You wake up feeling anxious about a big presentation today, and your wellness app chirps "You are beautiful inside and out!" While well-intentioned, this generic message completely misses the mark. You needed confidence and focus, not a beauty boost.

This disconnect isn't uncommon. Our extensive market research revealed critical pain points across existing affirmation apps: users consistently report feeling misunderstood by generic content that doesn't match their current emotional state or life circumstances.

Take Sarah, a cancer patient who left a heartbreaking review on the "I Am - Daily Affirmations" app: "The health affirmations felt tone-deaf when I'm literally fighting for my life. I needed something that understood my specific struggle, not general wellness platitudes."

The psychology behind this is clear. According to recent studies on neuroplasticity and positive psychology, affirmations only create lasting change when they feel authentic and personally relevant to the listener. Generic messages often trigger what researchers call "cognitive dissonance" – when your brain rejects positive statements that don't align with your current reality or emotional state.

This is exactly why 91% of people don't reach their personal development goals. They're using tools designed for everyone, which means they're designed for no one.

The data speaks for itself. When 89% of users specifically request the ability to hear affirmations in their own voice, and 73% describe generic content as feeling "fake" or "cringey", it's clear the market is desperately ready for a more personalized approach.

Enter Affirmi: AI-Powered Personalization

What if your affirmations could actually understand your mood, your goals, and your unique circumstances? That's exactly what we're building with Affirmi.

Our AI doesn't just randomly select from a database of generic phrases. Instead, it analyzes your current emotional state through mood tracking, considers your personal journal entries, and generates affirmations that speak directly to where you are right now.

Here's how it works in practice:

Morning anxiety about work? Affirmi might generate: "I have the skills and preparation to handle today's challenges. My anxiety shows I care deeply about doing well."
Feeling overwhelmed as a new parent? You might hear: "I'm learning something new every day, and that's exactly what good parenting looks like. My love for my child guides me through uncertainty."
Struggling with creative block? Affirmi could offer: "My creativity flows in cycles, and rest is part of the creative process. Ideas are forming even when I can't see them yet."

The difference is profound. Instead of fighting against generic positivity, users report feeling genuinely understood and supported. Our beta testers describe it as "finally having someone who gets it."

Beyond Text: The Power of Voice Cloning in Affirmations

Here's where Affirmi takes a revolutionary leap forward: you can hear these personalized affirmations in your own voice.

The science behind this is fascinating. Research from neuroscience labs shows that familiar voices activate brain regions associated with social safety and emotional regulation. When you hear affirmations in your own voice, your brain processes them differently than when hearing a stranger's voice – with less skepticism and more acceptance.

Our voice cloning feature uses cutting-edge AI from ElevenLabs to create a natural-sounding version of your voice from just a 30-60 second audio sample. The result? Affirmations that don't just feel personal – they literally are personal.

Privacy is paramount in this process. Your voice data is processed securely, temporarily stored only during the cloning process, and then immediately deleted. The resulting voice model stays private to your account, and we never share or sell this data to anyone.

Beta user Jake shares his experience: "Hearing my own voice tell me I'm capable of handling my ADHD challenges was incredibly powerful. It felt like the encouraging inner voice I always wished I had."

Our #BuildInPublic Journey: Transparency and Innovation

Building Affirmi hasn't happened behind closed doors. We're committed to radical transparency through our #BuildInPublic approach, sharing every challenge, breakthrough, and learning along the way.

Why build in public? Mental wellness technology requires trust. By showing you exactly how we're developing Affirmi, the technical decisions we're making, and the privacy safeguards we're implementing, we're proving our commitment to building something genuinely helpful rather than just another wellness app cash grab.

Our recent participation in the RevenueCat Shipathon exemplifies this approach. While competing for the "Build in Public" award, we've documented:

Technical deep-dives into our AI architecture transition from basic API calls to sophisticated on-device machine learning
Privacy-first design decisions that ensure your mood data and journal entries never leave your device for processing
User feedback integration showing how real user pain points directly influence our development priorities
Transparent monetization approach using RevenueCat's subscription management, with clear value propositions for premium features

This transparency extends to our data practices. Unlike many wellness apps that sell user data or show intrusive ads, Affirmi operates on a straightforward freemium model. Free users get essential features to try our personalization, while premium subscribers ($4.99/month or $59.99/year) unlock unlimited AI-generated affirmations, voice cloning, and advanced journaling insights.

The Market Validation: You're Not Alone in Wanting Something Better

The numbers tell a compelling story. The mental health apps market is exploding, growing from $6.52 billion in 2024 to a projected $23.8 billion by 2032 – an 18% annual growth rate. This isn't just about market size; it's about genuine demand for better solutions.

Wellness apps overall are expected to reach $45.65 billion by 2034, with personalized AI-driven solutions leading the charge. Users are clearly willing to pay for tools that actually understand and adapt to their needs.

But here's what most market reports miss: the frustration with existing solutions is real and widespread. Our research across Reddit communities, app store reviews, and user surveys revealed consistent themes:

"Generic content feels cringey and fake" (mentioned in 73% of negative reviews across top affirmation apps)
"I want to hear affirmations in my own voice" (requested by 89% of users in affirmation app communities)
"The app doesn't understand my actual problems" (common complaint across mental wellness platforms)

Affirmi directly addresses every single one of these pain points.

The spiritual wellness apps market alone is projected to grow from $2.60 billion in 2025 to $10.16 billion by 2035, while meditation apps are expected to reach $4.97 billion by 2030. These numbers reflect a massive shift toward personalized, technology-enhanced mental wellness solutions.

What's Next for Your Mental Wellness Journey with Affirmi

We're just getting started. Our roadmap for the next 6-12 months includes:

Technical Evolution: We're transitioning from cloud-based AI processing to on-device machine learning, meaning your most personal data will never leave your phone while still providing incredibly sophisticated personalization.

Advanced Personalization: Our AI will learn from your engagement patterns, mood trends, and journaling insights to provide even more nuanced and helpful affirmations over time.

Integration Possibilities: Potential connections with wearables, calendar apps, and other wellness tools to provide contextual affirmations based on your actual life events and schedule.

Ready to Experience Affirmations That Actually Get You?

The future of self-care isn't about more generic positivity – it's about deeply personal, AI-powered support that meets you exactly where you are.

🎯 AI that understands your mood and generates relevant affirmations
🗣️ Your own voice delivering encouragement that actually lands
📔 Integrated journaling that helps the AI learn your unique patterns
🔒 Privacy-first design that keeps your data secure and private
🚀 Continuous improvement through our transparent development process

Available now on iOS and Android

Follow our #BuildInPublic journey on Twitter @AffirmiApp and be part of the conversation shaping the future of personalized mental wellness.

Because you deserve affirmations that actually affirm who you are and where you're going.

Key Takeaways for Developers

If you're building in the mental wellness space, here are some insights from our research:

Personalization is non-negotiable - 73% of users reject generic content
Voice technology is underutilized - 89% want personalized audio experiences
Privacy builds trust - Transparent data practices are a competitive advantage
Build in public works - Authentic sharing creates stronger user connections
Focus on real problems - Market research reveals users are frustrated with existing solutions

Tech Stack Highlights:

Kotlin Multiplatform for cross-platform development
Firebase for backend infrastructure and ML model hosting
ElevenLabs API for voice cloning and TTS
RevenueCat for subscription management
TensorFlow Lite for on-device ML inference

Ready to try Affirmi? Start with our free tier and experience AI-powered personalization for yourself. Upgrade to premium for unlimited affirmations and voice cloning features.

Affirmi is not a replacement for professional therapy or medical treatment. If you're experiencing severe mental health challenges, please consult with a qualified healthcare provider.

What are your thoughts on AI-powered mental wellness tools? Have you tried any affirmation apps that felt truly personalized? Share your experiences in the comments below!

Trees in Kotlin: A Comprehensive Guide 🌳

WolfOf420Stret — Fri, 31 Jan 2025 10:00:12 +0000

Introduction
What Even Is a Tree?
Basic Tree Concepts
Binary Trees Deep Dive
Binary Trees Vs Binary Search Trees
Core Operations
Tree Traversal: The Grand Tour
AVL Trees: The Yoga Masters
B-Trees: The Database Darlings
Search Algorithms
Advanced Implementation and Best Practices
Performance Comparison
Common Interview Questions
Final Thoughts: The Forest for the Trees

Introduction

Remember playing "family tree" as a kid? Well, welcome to the grown-up version, where instead of arguing about who gets to be the cool aunt, we're organizing data in the most efficient way possible. Trees in computer science are like family trees on steroids – they're hierarchical, they're powerful, and they definitely won't ask to borrow money.

What Even Is a Tree? (And No, We're Not Arguing About Botany)

In programming, a tree is made up of nodes. Think of it like a family tree, but instead of awkward Thanksgiving dinners, you get neat, logical relationships. Here's the breakdown:

Root: The OG node. The Beyoncé of the tree. Everything starts here.
Parent/Child: Nodes can have children (like the root), and children can have their own children. Basically, it's a never-ending cycle of responsibility.
Leaf: A node with no children. The introvert of the tree. Just wants to be left alone.
Node : A fundamental unit containing data and references to other nodes
Edge: The connection between nodes
Height : The length of the longest path from root to leaf
Depth : The length of the path from a node to the root
Subtree : A tree consisting of a node and all its descendants

If you're picturing an upside-down oak tree with numbers instead of acorns, you're on the right track.

Basic Tree Concepts

Let's start with the basics (because even Olympic athletes had to learn to walk first):

data class TreeNode<T>(
    val value: T,
    val children: MutableList<TreeNode<T>> = mutableListOf()
) {
    fun addChild(value: T): TreeNode<T> {
        val child = TreeNode(value)
        children.add(child)
        return child
    }

    fun removeChild(value: T) {
        children.removeIf { it.value == value }
    }
    fun findChild(value: T): TreeNode<T>? {
        if (this.value == value) return this

        for (child in children) {
            val found = child.findChild(value)
            if (found != null) return found
        }
        return null
    }

}

Binary Trees Deep Dive

Binary trees are like having kids with a strict two-child policy. Each node can have at most two children, making them perfect for divide-and-conquer scenarios.

data class BinaryNode<T>(
    val value: T,
    var left: BinaryNode<T>? = null,
    var right: BinaryNode<T>? = null
) {
    fun isLeaf() = left == null && right == null
    fun hasSingleChild() = left == null xor right == null
    fun hasChildren() = left != null || right != null
}

Binary Trees Vs Binary Search Trees

A BST is a binary tree with additional ordering properties:

All nodes in the left subtree must be less than the current node
All nodes in the right subtree must be greater than the current node
No duplicate values allowed (in most implementations)

class BinarySearchTree<T : Comparable<T>> {
    private var root: BinaryNode<T>? = null

    fun insert(value: T) {
        root = insertRec(root, value)
    }

    private fun insertRec(node: BinaryNode<T>?, value: T): BinaryNode<T> {
        if (node == null) return BinaryNode(value)

        when {
            value < node.value -> node.left = insertRec(node.left, value)
            value > node.value -> node.right = insertRec(node.right, value)
            else -> return node // Duplicate values not allowed
        }
        return node
    }

    fun find(value: T): BinaryNode<T>? {
        var current = root
        while (current != null) {
            when {
                value < current.value -> current = current.left
                value > current.value -> current = current.right
                else -> return current
            }
        }
        return null
    }

    fun delete(value: T) {
        root = deleteRec(root, value)
    }

    private fun deleteRec(node: BinaryNode<T>?, value: T): BinaryNode<T>? {
        if (node == null) return null

        when {
            value < node.value -> node.left = deleteRec(node.left, value)
            value > node.value -> node.right = deleteRec(node.right, value)
            else -> {
                // Node with only one child or no child
                if (node.left == null) return node.right
                if (node.right == null) return node.left

                // Node with two children: Get the inorder successor (smallest
                // in the right subtree)
                node.value = minValue(node.right!!)
                node.right = deleteRec(node.right, node.value)
            }
        }
        return node
    }

    private fun minValue(node: BinaryNode<T>): T {
        var current = node
        while (current.left != null) {
            current = current.left!!
        }
        return current.value
    }
}

Core Operations

Insertion

Binary Tree: Can insert at any available position
BST: Must maintain ordering property

Compare with current node
Go left if smaller
Go right if larger
Create new node when null position is found

Searching

Binary Tree: Must check all nodes (O(n))
BST: Can use ordering to optimize (O(log n) average case)

Compare with current node
Go left if smaller
Go right if larger
Return null if not found

Deletion

Binary Tree: Simply remove node and restructure
BST: Three cases:

Leaf node: Simply remove
One child: Replace with child
Two children: Replace with inorder successor (smallest in right subtree)

Tree Traversal: The Grand Tour

Think of tree traversal as being a tourist in a tree-shaped city. There are several ways to explore:

1. Depth-First Search (DFS) Variants

class TreeTraversal<T> {
    // Pre-order: Root → Left → Right
    fun preorderTraversal(root: BinaryNode<T>?, result: MutableList<T> = mutableListOf()): List<T> {
        root?.let {
            result.add(it.value)
            preorderTraversal(it.left, result)
            preorderTraversal(it.right, result)
        }
        return result
    }

    // In-order: Left → Root → Right
    fun inorderTraversal(root: BinaryNode<T>?, result: MutableList<T> = mutableListOf()): List<T> {
        root?.let {
            inorderTraversal(it.left, result)
            result.add(it.value)
            inorderTraversal(it.right, result)
        }
        return result
    }

    // Post-order: Left → Right → Root
    fun postorderTraversal(root: BinaryNode<T>?, result: MutableList<T> = mutableListOf()): List<T> {
        root?.let {
            postorderTraversal(it.left, result)
            postorderTraversal(it.right, result)
            result.add(it.value)
        }
        return result
    }

    // Iterative In-order traversal (because recursion isn't always the answer)
    fun iterativeInorderTraversal(root: BinaryNode<T>?): List<T> {
        val result = mutableListOf<T>()
        val stack = Stack<BinaryNode<T>>()
        var current = root

        while (current != null || stack.isNotEmpty()) {
            // Reach the leftmost node of the current node
            while (current != null) {
                stack.push(current)
                current = current.left
            }

            // Current is now null, pop an element from stack
            current = stack.pop()
            result.add(current.value)

            // Move to the right subtree
            current = current.right
        }
        return result
    }
}

2. Breadth-First Search (BFS)

When you want to explore level by level, like a proper tourist:

fun <T> levelOrderTraversal(root: BinaryNode<T>?): List<List<T>> {
    val result = mutableListOf<List<T>>()
    if (root == null) return result

    val queue = LinkedList<BinaryNode<T>>()
    queue.offer(root)

    while (queue.isNotEmpty()) {
        val levelSize = queue.size
        val currentLevel = mutableListOf<T>()

        repeat(levelSize) {
            val node = queue.poll()
            currentLevel.add(node.value)

            node.left?.let { queue.offer(it) }
            node.right?.let { queue.offer(it) }
        }
        result.add(currentLevel)
    }
    return result
}

AVL Trees: The Yoga Masters

AVL trees are binary search trees that do yoga every morning to stay balanced. They maintain their balance by ensuring that the heights of the left and right subtrees of any node differ by at most one.

data class AVLNode<T : Comparable<T>>(
    val value: T,
    var left: AVLNode<T>? = null,
    var right: AVLNode<T>? = null,
    var height: Int = 1
) {
    val balanceFactor: Int
        get() = (left?.height ?: 0) - (right?.height ?: 0)

    fun updateHeight() {
        height = maxOf(left?.height ?: 0, right?.height ?: 0) + 1
    }
}

class AVLTree<T : Comparable<T>> {
    private var root: AVLNode<T>? = null

    private fun rotateRight(y: AVLNode<T>): AVLNode<T> {
        val x = y.left!!
        val T2 = x.right

        x.right = y
        y.left = T2

        y.updateHeight()
        x.updateHeight()

        return x
    }

    private fun rotateLeft(x: AVLNode<T>): AVLNode<T> {
        val y = x.right!!
        val T2 = y.left

        y.left = x
        x.right = T2

        x.updateHeight()
        y.updateHeight()

        return y
    }

    fun insert(value: T) {
        root = insert(root, value)
    }

    private fun insert(node: AVLNode<T>?, value: T): AVLNode<T> {
        // Standard BST insert
        if (node == null) return AVLNode(value)

        when {
            value < node.value -> node.left = insert(node.left, value)
            value > node.value -> node.right = insert(node.right, value)
            else -> return node // Duplicate values not allowed
        }

        // Update height of current node
        node.updateHeight()

        // Get balance factor and balance if needed
        return when (node.balanceFactor) {
            2 -> { // Left heavy
                if ((node.left?.balanceFactor ?: 0) < 0) {
                    node.left = rotateLeft(node.left!!)
                }
                rotateRight(node)
            }
            -2 -> { // Right heavy
                if ((node.right?.balanceFactor ?: 0) > 0) {
                    node.right = rotateRight(node.right!!)
                }
                rotateLeft(node)
            }
            else -> node
        }
    }
}

B-Trees: The Database Darlings

B-Trees are the backbone of database indexing. Unlike binary trees, they can have multiple keys per node and multiple children. They're like those big family reunions where everyone somehow fits at the table.

data class BTreeNode<K : Comparable<K>, V>(
    val keys: MutableList<K> = mutableListOf(),
    val values: MutableList<V> = mutableListOf(),
    val children: MutableList<BTreeNode<K, V>> = mutableListOf(),
    var isLeaf: Boolean = true
) {
    fun insertNonFull(key: K, value: V, degree: Int) {
        var i = keys.size - 1

        if (isLeaf) {
            // Find location to insert and move all greater keys up
            while (i >= 0 && keys[i] > key) {
                keys.add(i + 1, keys[i])
                values.add(i + 1, values[i])
                i--
            }
            keys.add(i + 1, key)
            values.add(i + 1, value)
        } else {
            // Find child which is going to have the new key
            while (i >= 0 && keys[i] > key) i--

            if (children[i + 1].keys.size == 2 * degree - 1) {
                splitChild(i + 1, children[i + 1], degree)
                if (keys[i + 1] < key) i++
            }
            children[i + 1].insertNonFull(key, value, degree)
        }
    }

    private fun splitChild(i: Int, y: BTreeNode<K, V>, degree: Int) {
        val z = BTreeNode<K, V>(isLeaf = y.isLeaf)

        // Copy the last (t-1) keys of y to z
        for (j in 0 until degree - 1) {
            z.keys.add(y.keys[j + degree])
            z.values.add(y.values[j + degree])
        }

        // Copy the last t children of y to z
        if (!y.isLeaf) {
            for (j in 0 until degree) {
                z.children.add(y.children[j + degree])
            }
        }

        // Insert new child in this node
        children.add(i + 1, z)

        // Move middle key to this node
        keys.add(i, y.keys[degree - 1])
        values.add(i, y.values[degree - 1])

        // Remove keys and children from y
        for (j in y.keys.size - 1 downTo degree - 1) {
            y.keys.removeAt(j)
            y.values.removeAt(j)
        }
        if (!y.isLeaf) {
            for (j in y.children.size - 1 downTo degree) {
                y.children.removeAt(j)
            }
        }
    }
}

class BTree<K : Comparable<K>, V>(private val degree: Int) {
    private var root: BTreeNode<K, V> = BTreeNode()

    fun insert(key: K, value: V) {
        val r = root
        if (r.keys.size == 2 * degree - 1) {
            val s = BTreeNode<K, V>(isLeaf = false)
            root = s
            s.children.add(r)
            s.splitChild(0, r, degree)
            s.insertNonFull(key, value, degree)
        } else {
            r.insertNonFull(key, value, degree)
        }
    }
}

Search Algorithms

Let's look at different ways to find our data (because sometimes it likes to play hide and seek):

Binary Search Tree Search

fun <T : Comparable<T>> BinaryNode<T>.search(value: T): BinaryNode<T>? {
    return when {
        this.value == value -> this
        value < this.value -> left?.search(value)
        else -> right?.search(value)
    }
}

Advanced Search Patterns

class TreeSearcher<T : Comparable<T>> {
    // Find closest value in BST
    fun findClosest(root: BinaryNode<T>?, target: T): T? {
        var closest: T? = null
        var minDiff: Int? = null
        var current = root

        while (current != null) {
            val currentDiff = abs(current.value.compareTo(target))
            if (minDiff == null || currentDiff < minDiff) {
                closest = current.value
                minDiff = currentDiff
            }

            current = when {
                target < current.value -> current.left
                target > current.value -> current.right
                else -> return current.value // Exact match found
            }
        }

        return closest
    }

    // Find kth smallest element
    fun findKthSmallest(root: BinaryNode<T>?, k: Int): T? {
        val stack = Stack<BinaryNode<T>>()
        var current = root
        var count = 0

        while (current != null || stack.isNotEmpty()) {
            while (current != null) {
                stack.push(current)
                current = current.left
            }

            current = stack.pop()
            count++

            if (count == k) {
                return current.value
            }

            current = current.right
        }

        return null
    }
}

Advanced Implementation and Best Practices

Memory Optimization

class CompactTree<T>(
    private val values: Array<T?>,
    private val size: Int
) {
    fun getLeft(index: Int) = 2 * index + 1
    fun getRight(index: Int) = 2 * index + 2
    fun getParent(index: Int) = (index - 1) / 2

    fun getValue(index: Int): T? =
        if (index < size) values[index] else null
}

Thread Safety

class ThreadSafeTree<T> {
    private val lock = ReentrantReadWriteLock()
    private var root: TreeNode<T>? = null

    fun insert(value: T) {
        lock.writeLock().use {
            // Perform thread-safe insertion
        }
    }

    fun search(value: T): Boolean {
        lock.readLock().use {
            // Perform thread-safe search
        }
    }
}

Performance Comparison

Operation	BST (avg)	BST (worst)	AVL Tree	B-Tree
Search	O(log n)	O(n)	O(log n)	O(log n)
Insert	O(log n)	O(n)	O(log n)	O(log n)
Delete	O(log n)	O(n)	O(log n)	O(log n)
Space	O(n)	O(n)	O(n)	O(n)

🌳 Real-World Analogies

AVL Rotations: Like adjusting a wobbly table—rotate legs until stable.
B-Tree Splitting: Similar to splitting an overpacked suitcase—take out the middle item (median) and distribute the rest.

Tree Traversals:

In-Order: Reading a book from left to right
Level-Order: Scanning a supermarket aisle shelf by shelf
Post-Order: Assembling furniture (build children first, then parent)

Common Interview Questions

Easy

Maximum Depth of Binary Tree

fun maxDepth(root: BinaryNode<T>?): Int {
    if (root == null) return 0
    return 1 + maxOf(maxDepth(root.left), maxDepth(root.right))
}

Check if Binary Tree is Symmetric

fun isSymmetric(root: BinaryNode<T>?): Boolean {
    if (root == null) return true
    return isMirror(root.left, root.right)
}

private fun isMirror(left: BinaryNode<T>?, right: BinaryNode<T>?): Boolean {
    if (left == null && right == null) return true
    if (left == null || right == null) return false

    return (left.value == right.value) &&
           isMirror(left.left, right.right) &&
           isMirror(left.right, right.left)
}

Medium

Validate Binary Search Tree

fun isValidBST(root: BinaryNode<T>?): Boolean {
    return isValidBST(root, null, null)
}

private fun isValidBST(
    node: BinaryNode<T>?,
    min: T?,
    max: T?
): Boolean {
    if (node == null) return true

    if ((min != null && node.value <= min) ||
        (max != null && node.value >= max)) {
        return false
    }

    return isValidBST(node.left, min, node.value) &&
           isValidBST(node.right, node.value, max)
}

Lowest Common Ancestor

fun lowestCommonAncestor(
    root: BinaryNode<T>?,
    p: BinaryNode<T>,
    q: BinaryNode<T>
): BinaryNode<T>? {
    if (root == null || root == p || root == q) return root

    val left = lowestCommonAncestor(root.left, p, q)
    val right = lowestCommonAncestor(root.right, p, q)

    return when {
        left != null && right != null -> root
        left != null -> left
        else -> right
    }
}

Hard

Serialize and Deserialize Binary Tree

class Codec {
    fun serialize(root: BinaryNode<String>?): String {
        if (root == null) return "null"
        return "${root.value},${serialize(root.left)},${serialize(root.right)}"
    }

    fun deserialize(data: String): BinaryNode<String>? {
        val nodes = LinkedList(data.split(","))
        return deserializeHelper(nodes)
    }

    private fun deserializeHelper(nodes: LinkedList<String>): BinaryNode<String>? {
        val value = nodes.removeFirst()
        if (value == "null") return null

        val node = BinaryNode(value)
        node.left = deserializeHelper(nodes)
        node.right = deserializeHelper(nodes)
        return node
    }
}

💡 Pro Tips

Use AVL trees when you need frequent inserts/deletes with fast lookups
Choose B-trees for disk-based storage (they minimize disk I/O)
Prefer iterative traversal for deep trees to avoid stack overflow
Combine tree structures: Use a trie for autocomplete, then an AVL tree for sorting suggestions

🚀 When Trees Collide: Hybrid Structures

Modern systems often combine tree variants:

Databases use B-trees for storage and BSTs for in-memory indices
File systems might use tries for path lookup and AVL trees for metadata
Game engines employ spatial trees (like octrees) built using balancing techniques from AVL

🎓 Tree Wisdom

Trees teach us valuable programming lessons:

Balance is key (AVL)
Divide and conquer (B-tree splits)
Different perspectives matter (traversal orders)
Growth requires adaptation (balancing operations)

🔧 Debugging Tree Issues

Common pitfalls and solutions:

Infinite Loops: Check for missing parent pointers in rotations
Memory Leaks: Null out children references when deleting nodes
Balance Factor Errors: Always update heights after rotations
Incorrect Traversal Order: Double-check left/right recursion order

Final Thoughts: The Forest for the Trees

Trees are like the Swiss Army knife of data. Trees are more than data structures—they're a way of thinking hierarchically. Whether you're balancing AVL nodes like a tightrope walker or splitting B-tree nodes like a careful librarian, remember: every tree starts with a single root. Now go forth and branch out!

(But seriously, if your binary tree starts growing mushrooms, maybe check your recursion depth.)

Search Algorithms in Kotlin: A Comprehensive Guide

WolfOf420Stret — Fri, 24 Jan 2025 07:40:31 +0000

Linear Search

Overview

Linear search (or sequential search) is the simplest search algorithm that works by checking every element in a collection until a match is found or the entire collection has been searched.

Implementation

fun <T> List<T>.linearSearch(element: T): Int {
    for (i in this.indices) {
        if (this[i] == element) {
            return i
        }
    }
    return -1
}

// Generic implementation with predicate
fun <T> List<T>.linearSearchBy(predicate: (T) -> Boolean): Int {
    for (i in this.indices) {
        if (predicate(this[i])) {
            return i
        }
    }
    return -1
}

Advanced Implementations

Parallel Linear Search

fun <T> List<T>.parallelLinearSearch(element: T): Int = runBlocking {
    if (size <= 1000) return@runBlocking linearSearch(element)

    val numberOfThreads = Runtime.getRuntime().availableProcessors()
    val chunkSize = size / numberOfThreads

    val deferreds = List(numberOfThreads) { threadIndex ->
        async(Dispatchers.Default) {
            val startIndex = threadIndex * chunkSize
            val endIndex = if (threadIndex == numberOfThreads - 1) size else startIndex + chunkSize

            for (i in startIndex until endIndex) {
                if (this@parallelLinearSearch[i] == element) return@async i
            }
            return@async -1
        }
    }

    deferreds.awaitAll().firstOrNull { it != -1 } ?: -1
}

Early-Stopping Linear Search

fun <T> List<T>.linearSearchWithEarlyStop(
    element: T,
    shouldStop: (T) -> Boolean
): Int {
    for (i in this.indices) {
        if (this[i] == element) return i
        if (shouldStop(this[i])) break
    }
    return -1
}

Time and Space Complexity

Time Complexity

Best Case: O(1) - Element found at first position
Average Case: O(n/2) - Element found at middle position
Worst Case: O(n) - Element not found or at last position

Space Complexity

O(1) - Constant space regardless of input size

Performance Analysis

fun analyzeSingleLinearSearch(size: Int): Long {
    val list = List(size) { it }
    val target = size - 1  // Worst case scenario

    val startTime = System.nanoTime()
    list.linearSearch(target)
    return System.nanoTime() - startTime
}

data class PerformanceMetrics(
    val size: Int,
    val bestCase: Long,
    val averageCase: Long,
    val worstCase: Long
)

fun generatePerformanceTable(): List<PerformanceMetrics> {
    return listOf(100, 1000, 10000, 100000).map { size ->
        val list = List(size) { it }

        val bestCase = measureNanoTime { list.linearSearch(0) }
        val averageCase = measureNanoTime { list.linearSearch(size / 2) }
        val worstCase = measureNanoTime { list.linearSearch(size - 1) }

        PerformanceMetrics(size, bestCase, averageCase, worstCase)
    }
}

Binary Search

Overview

Binary search is an efficient algorithm for searching a sorted array by repeatedly dividing the search interval in half. It works on the principle of divide and conquer.

Basic Implementation

fun <T : Comparable<T>> List<T>.binarySearch(element: T): Int {
    var low = 0
    var high = size - 1

    while (low <= high) {
        val mid = (low + high) / 2
        when {
            this[mid] == element -> return mid
            this[mid] > element -> high = mid - 1
            else -> low = mid + 1
        }
    }
    return -1
}

Advanced Implementations

Recursive Binary Search

fun <T : Comparable<T>> List<T>.binarySearchRecursive(
    element: T,
    low: Int = 0,
    high: Int = size - 1
): Int {
    if (low > high) return -1

    val mid = (low + high) / 2
    return when {
        this[mid] == element -> mid
        this[mid] > element -> binarySearchRecursive(element, low, mid - 1)
        else -> binarySearchRecursive(element, mid + 1, high)
    }
}

Binary Search with Custom Comparator

fun <T> List<T>.binarySearchBy(
    element: T,
    comparator: Comparator<T>
): Int {
    var low = 0
    var high = size - 1

    while (low <= high) {
        val mid = (low + high) / 2
        val comparison = comparator.compare(this[mid], element)

        when {
            comparison == 0 -> return mid
            comparison > 0 -> high = mid - 1
            else -> low = mid + 1
        }
    }
    return -1
}

Generic Binary Search for Range

fun binarySearchRange(
    start: Int,
    end: Int,
    predicate: (Int) -> Boolean
): Int {
    var low = start
    var high = end

    while (low <= high) {
        val mid = low + (high - low) / 2

        when {
            predicate(mid) -> high = mid - 1
            else -> low = mid + 1
        }
    }
    return low
}

Common Pitfalls and Solutions

Integer Overflow

// Incorrect
val mid = (low + high) / 2

// Correct
val mid = low + (high - low) / 2

Infinite Loop

// Potential infinite loop
while (low < high)

// Correct
while (low <= high)

Off-by-One Errors

// Common mistake
high = mid
low = mid

// Correct
high = mid - 1
low = mid + 1

Performance Comparison

fun compareSearchAlgorithms(size: Int, iterations: Int = 1000): SearchComparison {
    val sortedList = List(size) { it }

    val linearSearchTime = measureNanoTime {
        repeat(iterations) {
            sortedList.linearSearch(size / 2)
        }
    } / iterations

    val binarySearchTime = measureNanoTime {
        repeat(iterations) {
            sortedList.binarySearch(size / 2)
        }
    } / iterations

    return SearchComparison(size, linearSearchTime, binarySearchTime)
}

data class SearchComparison(
    val size: Int,
    val linearSearchTime: Long,
    val binarySearchTime: Long
)

Time and Space Complexity

Binary Search

Time Complexity:
- Best Case: O(1) - Element found at middle
- Average Case: O(log n)
- Worst Case: O(log n)
Space Complexity:
- Iterative: O(1)
- Recursive: O(log n) due to call stack

Practical Applications

Database Indexing

class IndexedDatabase<K : Comparable<K>, V>(
    private val keys: MutableList<K> = mutableListOf(),
    private val values: MutableList<V> = mutableListOf()
) {
    fun insert(key: K, value: V) {
        val index = keys.binarySearch(key).let { 
            if (it < 0) -(it + 1) else it 
        }
        keys.add(index, key)
        values.add(index, value)
    }

    fun find(key: K): V? {
        val index = keys.binarySearch(key)
        return if (index >= 0) values[index] else null
    }
}

Range Queries

fun <T : Comparable<T>> List<T>.findRange(
    start: T,
    end: T
): IntRange? {
    val startIndex = binarySearchBy { it >= start }
    if (startIndex == size) return null

    val endIndex = binarySearchBy { it > end }
    if (startIndex >= endIndex) return null

    return startIndex until endIndex
}

Best Practices and Optimization Tips

Choose the Right Algorithm:
- Use Linear Search for:
  - Small datasets (n < 50)
  - Unsorted data
  - When preprocessing overhead matters
- Use Binary Search for:
  - Large sorted datasets
  - Frequent searches
  - When initial sorting cost is justified
Implementation Considerations:
- Always validate input data
- Handle edge cases properly
- Consider using built-in functions for standard cases
- Use appropriate data types for indices
Performance Optimization:
- Keep data sorted when possible
- Use iterative implementation for better space complexity
- Consider parallel search for very large datasets
- Cache results when appropriate
Error Handling:

fun <T : Comparable<T>> List<T>.safeBinarySearch(
    element: T
): Result<Int> = runCatching {
    require(isNotEmpty()) { "List is empty" }
    require(isSorted()) { "List must be sorted" }
    binarySearch(element)
}

fun <T : Comparable<T>> List<T>.isSorted(): Boolean =
    zipWithNext { a, b -> a <= b }.all { it }

Comparison Table

Aspect	Linear Search	Binary Search
Time Complexity	O(n)	O(log n)
Space Complexity	O(1)	O(1)
Prerequisites	None	Sorted data
Best Use Case	Small/unsorted	Large/sorted
Implementation	Simple	More complex
Stability	Stable	Stable
Adaptability	More flexible	Less flexible

Conclusion

Both linear and binary search algorithms have their place in modern software development. Linear search's simplicity makes it ideal for small datasets and unsorted collections, while binary search's efficiency makes it the go-to choice for large, sorted datasets. Understanding the trade-offs and implementation details of both algorithms is crucial for writing efficient and maintainable code.

Kotlin Data Structures: A Comprehensive Guide

WolfOf420Stret — Fri, 24 Jan 2025 07:24:03 +0000

LinkedList in Kotlin

Overview

A LinkedList is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Kotlin provides both the standard library implementation and the ability to create custom implementations.

Implementation from Scratch

class Node<T>(
    var value: T,
    var next: Node<T>? = null
)

class LinkedList<T> {
    private var head: Node<T>? = null
    private var tail: Node<T>? = null
    var size = 0
        private set

    fun add(value: T) {
        val newNode = Node(value)
        if (head == null) {
            head = newNode
            tail = newNode
        } else {
            tail?.next = newNode
            tail = newNode
        }
        size++
    }

    fun addFirst(value: T) {
        val newNode = Node(value)
        newNode.next = head
        head = newNode
        if (tail == null) {
            tail = newNode
        }
        size++
    }

    fun removeFirst(): T? {
        if (head == null) return null
        val value = head?.value
        head = head?.next
        size--
        if (head == null) {
            tail = null
        }
        return value
    }

    fun find(value: T): Boolean {
        var current = head
        while (current != null) {
            if (current.value == value) return true
            current = current.next
        }
        return false
    }

    override fun toString(): String {
        return buildString {
            var current = head
            append("[")
            while (current != null) {
                append(current.value)
                if (current.next != null) append(", ")
                current = current.next
            }
            append("]")
        }
    }
}

Using Kotlin's Built-in LinkedList

fun main() {
    // Creating a LinkedList
    val linkedList = LinkedList<String>()

    // Adding elements
    linkedList.add("First")
    linkedList.add("Second")
    linkedList.addFirst("New First")

    // Accessing elements
    println(linkedList.first)    // New First
    println(linkedList.last)     // Second

    // Removing elements
    linkedList.removeFirst()
    linkedList.removeLast()

    // Checking size and emptiness
    println(linkedList.size)     // 1
    println(linkedList.isEmpty()) // false
}

Stack in Kotlin

Overview

A Stack is a LIFO (Last-In-First-Out) data structure. While Kotlin doesn't have a built-in Stack class, we can implement one using various approaches.

Custom Stack Implementation

class Stack<T> {
    private val elements = mutableListOf<T>()

    fun push(element: T) {
        elements.add(element)
    }

    fun pop(): T? {
        if (elements.isEmpty()) return null
        return elements.removeAt(elements.lastIndex)
    }

    fun peek(): T? {
        return elements.lastOrNull()
    }

    fun isEmpty() = elements.isEmpty()

    fun size() = elements.size

    override fun toString() = elements.toString()
}

// Usage example
fun main() {
    val stack = Stack<Int>()
    stack.push(1)
    stack.push(2)
    stack.push(3)

    println(stack.pop())    // 3
    println(stack.peek())   // 2
    println(stack.size())   // 2
}

Using Kotlin Collections as Stack

fun main() {
    // Using MutableList as a stack
    val stack = mutableListOf<Int>()

    // Push operations
    stack.add(1)        // push
    stack.add(2)        // push

    // Pop operation
    val lastElement = stack.removeLastOrNull()

    // Peek operation
    val topElement = stack.lastOrNull()
}

Queue in Kotlin

Overview

A Queue is a FIFO (First-In-First-Out) data structure. We'll implement both a basic Queue and a more advanced implementation with Kotlin's features.

Basic Queue Implementation

class Queue<T> {
    private val elements = mutableListOf<T>()

    fun enqueue(element: T) {
        elements.add(element)
    }

    fun dequeue(): T? {
        if (elements.isEmpty()) return null
        return elements.removeAt(0)
    }

    fun peek(): T? = elements.firstOrNull()

    fun isEmpty() = elements.isEmpty()

    fun size() = elements.size

    override fun toString() = elements.toString()
}

Advanced Queue Implementation with Circular Buffer

class CircularQueue<T>(private val capacity: Int) {
    private val elements = Array<Any?>(capacity) { null }
    private var front = 0
    private var rear = -1
    private var size = 0

    fun enqueue(element: T): Boolean {
        if (isFull()) return false

        rear = (rear + 1) % capacity
        elements[rear] = element
        size++
        return true
    }

    @Suppress("UNCHECKED_CAST")
    fun dequeue(): T? {
        if (isEmpty()) return null

        val element = elements[front] as T
        elements[front] = null
        front = (front + 1) % capacity
        size--
        return element
    }

    @Suppress("UNCHECKED_CAST")
    fun peek(): T? = if (isEmpty()) null else elements[front] as T

    fun isEmpty() = size == 0

    fun isFull() = size == capacity

    fun size() = size
}

HashTables in Kotlin

Overview

HashTables (or HashMaps in Kotlin) are key-value data structures that provide constant-time average case complexity for insertions and lookups.

Custom HashTable Implementation

class HashTable<K, V>(private val capacity: Int = 16) {
    private data class Entry<K, V>(
        val key: K,
        var value: V,
        var next: Entry<K, V>? = null
    )

    private val buckets = Array<Entry<K, V>?>(capacity) { null }
    private var size = 0

    private fun hash(key: K): Int {
        return Math.abs(key.hashCode() % capacity)
    }

    fun put(key: K, value: V) {
        val index = hash(key)
        val entry = Entry(key, value)

        if (buckets[index] == null) {
            buckets[index] = entry
            size++
            return
        }

        var current = buckets[index]
        while (current != null) {
            if (current.key == key) {
                current.value = value
                return
            }
            if (current.next == null) {
                current.next = entry
                size++
                return
            }
            current = current.next
        }
    }

    fun get(key: K): V? {
        val index = hash(key)
        var current = buckets[index]

        while (current != null) {
            if (current.key == key) {
                return current.value
            }
            current = current.next
        }
        return null
    }

    fun remove(key: K): Boolean {
        val index = hash(key)
        var current = buckets[index]
        var prev: Entry<K, V>? = null

        while (current != null) {
            if (current.key == key) {
                if (prev == null) {
                    buckets[index] = current.next
                } else {
                    prev.next = current.next
                }
                size--
                return true
            }
            prev = current
            current = current.next
        }
        return false
    }

    fun size() = size
    fun isEmpty() = size == 0
}

Using Kotlin's Built-in HashMap

fun main() {
    // Creating a HashMap
    val map = HashMap<String, Int>()

    // Adding entries
    map["one"] = 1
    map["two"] = 2
    map.put("three", 3)

    // Accessing values
    println(map["one"])           // 1
    println(map.get("two"))       // 2
    println(map.getOrDefault("four", 0)) // 0

    // Removing entries
    map.remove("one")

    // Checking containment
    println(map.containsKey("one"))    // false
    println(map.containsValue(2))      // true

    // Iterating over entries
    for ((key, value) in map) {
        println("$key = $value")
    }

    // Using with nullable values
    val nullableMap = HashMap<String, Int?>()
    nullableMap["nullable"] = null
}

Performance Characteristics

LinkedList

Access: O(n)
Search: O(n)
Insertion at beginning: O(1)
Insertion at end: O(1) with tail reference
Deletion at beginning: O(1)
Deletion at end: O(n)
Space complexity: O(n)

Stack

Push: O(1)
Pop: O(1)
Peek: O(1)
Space complexity: O(n)

Queue

Enqueue: O(1)
Dequeue: O(1) with proper implementation
Peek: O(1)
Space complexity: O(n)

HashTable

Insert: O(1) average, O(n) worst
Delete: O(1) average, O(n) worst
Search: O(1) average, O(n) worst
Space complexity: O(n)

Best Practices and Tips

Choose the Right Collection:
- Use LinkedList when frequent insertions/deletions at both ends are needed
- Use Stack for LIFO operations
- Use Queue for FIFO operations
- Use HashTable for key-value associations with fast lookups
Memory Considerations:
- LinkedList requires extra memory for node references
- CircularQueue can help manage memory in fixed-size scenarios
- HashTable size should be balanced against expected number of elements
Thread Safety:
- These implementations are not thread-safe by default
- Use Collections.synchronizedList() or other concurrent implementations for thread safety
Performance Optimization:
- Initialize collections with expected capacity when possible
- Consider using specialized implementations for specific use cases
- Monitor load factor in HashTable implementations

Understanding Heap Sort in Kotlin: A Beginner's Guide

WolfOf420Stret — Wed, 22 Jan 2025 07:13:03 +0000

What is HeapSort?

HeapSort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. Developed by J. W. J. Williams in 1964, it combines the efficiency of both insertion sort and merge sort while performing sorting in-place. The algorithm works by first building a heap from the input data and then repeatedly extracting the maximum element from the heap and rebuilding it until all elements are sorted.

When to Use HeapSort?

HeapSort is particularly useful in several scenarios:

Limited Memory: Its in-place sorting capability makes it memory efficient.
Guaranteed Performance: Unlike QuickSort, HeapSort maintains O(n log n) complexity even in worst cases.
Priority Queue Operations: When you need to maintain a sorted sequence with frequent insertions/deletions.
Large Datasets: The consistent O(n log n) performance makes it reliable for large arrays.

How HeapSort Works

HeapSort operates in two main phases: heap construction and successive removal of the maximum element.

Step-by-Step Explanation

Build Max Heap:
- Convert the input array into a max heap structure.
- Parent nodes must be greater than their children.
Heap Extraction:
- Repeatedly remove the maximum element (root).
- Restructure the heap after each removal.
- Place extracted elements at the end of the array.
Final Array:
- The process results in a sorted array in ascending order.

Visual Representation of HeapSort

To sort the array [64, 34, 25, 12, 22]:

Build max heap:

Extract maximum elements:

   Step 1: [22, 34, 25, 12, |64]
   Step 2: [12, 34, 25, |22, 64]
   Step 3: [12, 25, |34, 22, 64]
   ...

Pseudocode for HeapSort

function heapSort(arr):
    n = length(arr)

    // Build max heap
    for i from n/2-1 down to 0:
        heapify(arr, n, i)

    // Extract elements from heap
    for i from n-1 down to 0:
        swap arr[0] with arr[i]
        heapify(arr, i, 0)

function heapify(arr, n, i):
    largest = i
    left = 2*i + 1
    right = 2*i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap arr[i] with arr[largest]
        heapify(arr, n, largest)

Implementing HeapSort in Kotlin

fun heapSort(arr: IntArray) {
    val n = arr.size

    // Build max heap
    for (i in n / 2 - 1 downTo 0) {
        heapify(arr, n, i)
    }

    // Extract elements from heap
    for (i in n - 1 downTo 0) {
        // Move current root to end
        arr[0] = arr[i].also { arr[i] = arr[0] }
        heapify(arr, i, 0)
    }
}

fun heapify(arr: IntArray, n: Int, i: Int) {
    var largest = i
    val left = 2 * i + 1
    val right = 2 * i + 2

    if (left < n && arr[left] > arr[largest])
        largest = left

    if (right < n && arr[right] > arr[largest])
        largest = right

    if (largest != i) {
        arr[i] = arr[largest].also { arr[largest] = arr[i] }
        heapify(arr, n, largest)
    }
}

Code Walkthrough

Main Function:
- First phase builds the max heap structure
- Second phase extracts elements in order
- Maintains heap property throughout
Heapify Function:
- Ensures the heap property is maintained
- Recursively adjusts sub-trees as needed
- Compares parent with children and swaps if necessary

Visual Step-by-Step Process

Initial Array: [64, 34, 25, 12, 22]

Building Max Heap:

Step 1: [64, 34, 25, 12, 22]
        64
       /  \
      34   25
     /  \
    12   22

Step 2: After heapify
        64
       /  \
      34   25
     /  \
    12   22

Extraction Phase:

Step 1: [22, 34, 25, 12, |64]
Step 2: [12, 34, 25, |22, 64]
Step 3: [12, 25, |34, 22, 64]
Final:  [12, 22, 25, 34, 64]

Time Complexity Analysis

Building Heap: O(n)

Although it appears to be O(n log n), it's actually O(n)
Upper levels of the tree have more work but fewer nodes

Extraction Phase: O(n log n)

n elements
log n operations per extraction

Overall Complexity: O(n log n)

Consistent across all cases (best, average, worst)
More predictable than QuickSort

Space Complexity: O(1)

In-place sorting algorithm
Only requires constant extra space

Detailed Performance Breakdown

Number of Operations

For an array of size n:

Comparisons:
- Building heap: O(n)
- Extraction phase: O(n log n) Total: O(n log n)
Swaps:
- Building heap: O(n)
- Extraction phase: O(n log n) Total: O(n log n)

Performance Table

Array Size (n)	Build Heap	Extraction	Total Operations
10	10	23	33
100	100	460	560
1,000	1,000	6,908	7,908

Optimization Techniques

Bottom-up Heap Construction

fun buildHeapBottomUp(arr: IntArray) {
    val n = arr.size
    for (i in n / 2 - 1 downTo 0) {
        heapifyIterative(arr, n, i)
    }
}

fun heapifyIterative(arr: IntArray, n: Int, i: Int) {
    var current = i
    while (true) {
        val largest = current
        val left = 2 * current + 1
        val right = 2 * current + 2

        if (left < n && arr[left] > arr[largest])
            largest = left
        if (right < n && arr[right] > arr[largest])
            largest = right

        if (largest == current) break

        arr[current] = arr[largest].also { arr[largest] = arr[current] }
        current = largest
    }
}

Cache-Optimized Implementation

fun heapSortCacheOptimized(arr: IntArray) {
    val n = arr.size
    buildHeapBottomUp(arr)

    for (i in n - 1 downTo 0) {
        arr[0] = arr[i].also { arr[i] = arr[0] }
        siftDown(arr, 0, i)
    }
}

Comparison with Other Sorting Algorithms

Algorithm	Best Case	Average Case	Worst Case	Space	Stable
HeapSort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
QuickSort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
MergeSort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
InsertionSort	O(n)	O(n²)	O(n²)	O(1)	Yes

Advantages and Disadvantages of HeapSort

Advantages:

Consistent O(n log n) performance
In-place sorting with O(1) extra space
No quadratic worst-case scenario
Excellent for systems with memory constraints

Disadvantages:

Usually slower than QuickSort in practice
Not stable - doesn't preserve order of equal elements
Poor cache performance due to non-sequential memory access
More complex implementation than simpler algorithms

Conclusion

HeapSort stands out for its consistent performance and memory efficiency. While it may not be the fastest sorting algorithm in practice, its guaranteed O(n log n) complexity and in-place sorting make it an excellent choice for systems with memory constraints or when consistent performance is crucial. Its unique properties also make it valuable in implementing priority queues and other specialized data structures.

Understanding Quick Sort in Kotlin : A Beginner's Guide

WolfOf420Stret — Sat, 11 Jan 2025 23:05:06 +0000

What is QuickSort?

QuickSort is a highly efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy. Developed by Tony Hoare in 1959, it has become one of the most widely used sorting algorithms due to its excellent average-case performance and efficient memory usage.

The algorithm works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

When to Use QuickSort?

QuickSort is an excellent general-purpose sorting algorithm with several ideal use cases:

Large Datasets: QuickSort's O(n log n) average time complexity makes it efficient for large arrays.
Limited Memory: Its in-place sorting capability makes it memory efficient.
Random Access Memory: QuickSort performs well when accessing elements at arbitrary positions.

However, it may not be the best choice when stable sorting is required or when dealing with nearly sorted data.

How QuickSort Works

QuickSort employs a divide-and-conquer strategy through partitioning around a pivot element.

Step-by-Step Explanation

Choose Pivot:
- Select a pivot element from the array (commonly first, last, or middle element).
Partition:
- Rearrange elements so that all elements smaller than the pivot are on the left.
- All elements larger than the pivot are on the right.
Recursive Sort:
- Recursively apply the same process to the sub-arrays on either side of the pivot.

Visual Representation of QuickSort

To sort the array [64, 34, 25, 12, 22] with last element as pivot:

First partition (pivot = 22):
- Result: [12, 34, 25, 64, 22] → [12, 22, 25, 64, 34]
Recursively sort left and right partitions

Pseudocode for QuickSort

function quickSort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quickSort(arr, low, pivot_index - 1)
        quickSort(arr, pivot_index + 1, high)

function partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j from low to high - 1:
        if arr[j] <= pivot:
            i = i + 1
            swap arr[i] with arr[j]
    swap arr[i + 1] with arr[high]
    return i + 1

Implementing QuickSort in Kotlin

fun quickSort(arr: IntArray, low: Int = 0, high: Int = arr.size - 1) {
    if (low < high) {
        val pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low - 1

    for (j in low until high) {
        if (arr[j] <= pivot) {
            i++
            // Swap elements
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    // Place pivot in correct position
    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    return i + 1
}

Code Walkthrough

Main Function:
- Recursively divides array into smaller partitions.
- Continues until partitions are of size 1 or 0.
Partition Function:
- Selects last element as pivot.
- Places smaller elements to left, larger to right.
- Returns final position of pivot.

Visual Step-by-Step Process

Initial Array: [64, 34, 25, 12, 22]

First Partition:

[64, 34, 25, 12, 22]  // Choose 22 as pivot
                   ↓
[12, 34, 25, 64, 22]  // Arrange elements around pivot
 ↓           ↑   ↓
[12, 22, 25, 64, 34]  // Pivot in final position
     ↓

Recursive Partitions:

Left: [12]           // Already sorted
Right: [25, 64, 34]  // Continue partitioning
      [25, 34, 64]   // Final sorted array

Legend:

↓ : Pivot element
↑ : Elements being compared
Unmarked: Unsorted elements

Time Complexity Analysis

Best Case: O(n log n)

Occurs when pivot consistently divides array into equal halves
Each level of recursion processes n elements
log n levels of recursion

Worst Case: O(n²)

Occurs when pivot is always smallest/largest element
Each partition removes only one element
n levels of recursion required

Average Case: O(n log n)

Random pivot selection typically provides good partitioning
Balanced division of array in most cases

Space Complexity: O(log n)

Recursive call stack in balanced cases
O(n) in worst case with unbalanced partitioning

Detailed Performance Breakdown

Number of Operations

For an array of size n:

Comparisons:
- Best case: n log n
- Worst case: n²/2
- Average case: 1.386n log n
Swaps:
- Best case: n log n
- Worst case: n²/2
- Average case: 0.693n log n

Performance Table

Array Size (n)	Best Case (n log n)	Average Case	Worst Case (n²)
10	33	46	100
100	664	921	10,000
1,000	9,966	13,812	1,000,000

Optimization Techniques

Median-of-Three Pivot Selection

fun medianOfThree(arr: IntArray, low: Int, high: Int): Int {
    val mid = (low + high) / 2
    if (arr[low] > arr[mid]) swap(arr, low, mid)
    if (arr[mid] > arr[high]) swap(arr, mid, high)
    if (arr[low] > arr[mid]) swap(arr, low, mid)
    return mid
}

Three-Way Partitioning

fun quickSort3Way(arr: IntArray, low: Int, high: Int) {
    if (high <= low) return

    var lt = low
    var gt = high
    val pivot = arr[low]
    var i = low + 1

    while (i <= gt) {
        when {
            arr[i] < pivot -> swap(arr, lt++, i++)
            arr[i] > pivot -> swap(arr, i, gt--)
            else -> i++
        }
    }

    quickSort3Way(arr, low, lt - 1)
    quickSort3Way(arr, gt + 1, high)
}

Comparison with Other Sorting Algorithms

Algorithm	Average Case	Worst Case	Space	Stable	In-Place
QuickSort	O(n log n)	O(n²)	O(log n)	No	Yes
MergeSort	O(n log n)	O(n log n)	O(n)	Yes	No
HeapSort	O(n log n)	O(n log n)	O(1)	No	Yes
InsertionSort	O(n²)	O(n²)	O(1)	Yes	Yes

Advantages and Disadvantages of QuickSort

Advantages:

Excellent average case performance
In-place sorting with minimal additional memory
Cache-friendly due to good locality of reference
Parallelizable for multi-threaded implementations

Disadvantages:

Unstable - doesn't preserve order of equal elements
Poor performance on already sorted or nearly sorted data
Vulnerable to poor pivot selection
Recursive nature can lead to stack overflow

Conclusion

QuickSort remains one of the most practical and efficient sorting algorithms available. Its combination of good average-case performance, in-place sorting, and cache efficiency makes it a popular choice in many programming languages' standard libraries. While it has some drawbacks, various optimizations and hybrid approaches have been developed to address these limitations, cementing QuickSort's position as a cornerstone of modern sorting implementations.

Understanding Insertion Sort in Kotlin : A Beginner's Guide

WolfOf420Stret — Sat, 11 Jan 2025 22:26:45 +0000

What is Insertion Sort?

Insertion Sort is an intuitive and adaptive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how most people sort playing cards in their hands - by taking one card at a time and inserting it into its correct position among the cards already sorted.

While not optimal for large datasets, Insertion Sort is efficient for small arrays and nearly-sorted data. Its simplicity and adaptiveness make it a practical choice in specific scenarios, and it's often used as part of more complex hybrid sorting algorithms.

When to Use Insertion Sort?

Insertion Sort shines in several specific scenarios:

Nearly Sorted Data: When the array is already partially sorted, Insertion Sort can perform nearly linearly.
Small Datasets: For arrays with fewer than 50 elements, Insertion Sort's simplicity can make it faster than more complex algorithms.
Online Sorting: When you need to sort data as it is received, Insertion Sort can efficiently insert new elements into an already-sorted portion.

However, for large, randomly ordered datasets, more efficient algorithms like QuickSort or MergeSort are preferable.

How Insertion Sort Works

Insertion Sort divides the array into sorted and unsorted sections, gradually moving elements from the unsorted section to their correct position in the sorted section.

Step-by-Step Explanation

Here's how Insertion Sort operates:

Start with First Element:
- Consider the first element as a sorted section of length one.
Take Next Element:
- Select the first unsorted element and store it as the 'key'.
Insert in Correct Position:
- Compare the key with each element in the sorted section from right to left.
- Shift larger elements one position ahead.
- Insert the key in its correct position.

Visual Representation of Insertion Sort

To sort the array [64, 34, 25, 12, 22]:

Take 34 and insert it before 64: [34, 64, 25, 12, 22]
Take 25 and insert it before 34: [25, 34, 64, 12, 22]
Continue until fully sorted: [12, 22, 25, 34, 64]

Pseudocode for Insertion Sort

function insertionSort(arr):
    for i from 1 to size of arr:
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key
    return arr

Implementing Insertion Sort in Kotlin

fun insertionSort(arr: IntArray): IntArray {
    for (i in 1 until arr.size) {
        val key = arr[i]
        var j = i - 1

        // Move elements greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
    return arr
}

Code Walkthrough

Outer Loop:
- Iterates through the unsorted section, starting from the second element.
Inner Loop:
- Shifts elements of the sorted section that are greater than the key.
Key Placement:
- Places the key in its correct position within the sorted section.

Visual Step-by-Step Process

Initial Array: [64, 34, 25, 12, 22]

Pass 1:

[64, 34, 25, 12, 22]  // Compare 34 with sorted portion
 ↓   ↓
[34, 64, 25, 12, 22]  // Insert 34 before 64
 ✓   ✓

Pass 2:

[34, 64, 25, 12, 22]  // Compare 25 with sorted portion
 ↓   ↓   ↓
[25, 34, 64, 12, 22]  // Insert 25 at start
 ✓   ✓   ✓

Pass 3:

[25, 34, 64, 12, 22]  // Compare 12 with sorted portion
 ↓   ↓   ↓   ↓
[12, 25, 34, 64, 22]  // Insert 12 at start
 ✓   ✓   ✓   ✓

Pass 4:

[12, 25, 34, 64, 22]  // Compare 22 with sorted portion
 ↓   ↓   ↓   ↓   ↓
[12, 22, 25, 34, 64]  // Insert 22 after 12
 ✓   ✓   ✓   ✓   ✓

Legend:

↓ : Elements being compared
✓ : Sorted portion
Unmarked: Unsorted portion

Time Complexity Analysis

Best Case: O(n)

Occurs when array is already sorted
Only requires one comparison per element
No shifting needed

Worst Case: O(n²)

Occurs when array is sorted in reverse order
Maximum comparisons and shifts needed for each element
Each element must be compared with every sorted element

Average Case: O(n²)

Random input data
Approximately half of the sorted elements are compared
Requires shifting of elements

Space Complexity: O(1)

Only requires a single additional memory space for the key
Sorts in-place

Detailed Performance Breakdown

Number of Operations

For an array of size n:

Comparisons:
- Best case: (n-1)
- Worst case: n(n-1)/2
- Average case: n(n-1)/4
Shifts:
- Best case: 0
- Worst case: n(n-1)/2
- Average case: n(n-1)/4

Performance Table

Array Size (n)	Best Case (n)	Average Case (n²/4)	Worst Case (n²/2)
10	9	22	45
100	99	2,475	4,950
1,000	999	249,750	499,500

Optimization Techniques

Binary Search Insertion

   fun insertionSortWithBinarySearch(arr: IntArray): IntArray {
       for (i in 1 until arr.size) {
           val key = arr[i]
           val location = binarySearch(arr, key, 0, i)
           for (j in i downTo location + 1) {
               arr[j] = arr[j - 1]
           }
           arr[location] = key
       }
       return arr
   }

Shell Sort Variation
- A variation of Insertion Sort that allows exchange of items that are far apart

Comparison with Other Sorting Algorithms

Algorithm	Best Case	Average Case	Worst Case	Space	Stable
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No

Advantages and Disadvantages of Insertion Sort

Advantages:

Adaptive - efficient for data that is already substantially sorted
Stable - maintains relative order of equal elements
In-place - only requires a constant amount O(1) of additional memory space
Online - can sort a list as it receives it

Disadvantages:

Quadratic time complexity makes it inefficient for large datasets
Generally performs worse than advanced algorithms like QuickSort
Requires shifting of elements, which can be expensive

Conclusion

Insertion Sort, while not suitable for large datasets, remains a valuable algorithm in specific scenarios, particularly for small or nearly-sorted arrays. Its adaptiveness, stability, and simple implementation make it a practical choice in certain applications, especially when dealing with continuous, real-time data streams.

Understanding Selection Sort in Kotlin: A Beginner's Guide

WolfOf420Stret — Thu, 09 Jan 2025 23:06:35 +0000

What is Selection Sort?

Selection Sort is a simple and intuitive sorting algorithm that divides the input array into two parts: a sorted section and an unsorted section. It repeatedly selects the smallest (or largest, depending on the order) element from the unsorted section and swaps it with the first element of the unsorted section, effectively growing the sorted section one element at a time.

While not as efficient as algorithms like Merge Sort or Quick Sort, Selection Sort is easy to understand and implement. It is most suitable for small datasets due to its simplicity and predictable behavior.

When to Use Selection Sort?

Selection Sort is not the fastest algorithm for large datasets, but it has some use cases where it might be a reasonable choice:

Small Datasets: For small arrays, the simplicity of Selection Sort can make it a convenient choice.
Limited Memory: Selection Sort sorts in place, meaning it requires minimal additional memory, making it suitable for memory-constrained applications.
Understanding Sorting Fundamentals: Its straightforward nature makes Selection Sort an excellent starting point for learning about sorting algorithms.

However, for larger datasets, Selection Sort's inefficiency becomes apparent due to its O(n²) time complexity in both average and worst-case scenarios.

How Selection Sort Works

Selection Sort operates in a step-by-step process that involves finding the smallest (or largest) element in the unsorted section and moving it to the sorted section.

Step-by-Step Explanation

Here's how Selection Sort works:

Find the Smallest Element:
- Start from the first element of the array and traverse through the unsorted section to find the smallest element.
Swap the Smallest Element:
- Swap the smallest element with the first element of the unsorted section, effectively growing the sorted section by one.
Repeat:
- Move to the next element and repeat the process until the entire array is sorted.

Visual Representation of Selection Sort

To sort the array [29, 10, 14, 37, 13]:

Find the smallest element (10) and swap it with the first element: [10, 29, 14, 37, 13]
Find the next smallest element (13) and swap it with the second element: [10, 13, 14, 37, 29]
Continue this process until the array is fully sorted: [10, 13, 14, 29, 37]

Pseudocode for Selection Sort

function selectionSort(arr):
    for i from 0 to size of arr - 1:
        minIndex = i
        for j from i + 1 to size of arr:
            if arr[j] < arr[minIndex]:
                minIndex = j
        swap arr[i] with arr[minIndex]
    return arr

Implementing Selection Sort in Kotlin

fun selectionSort(arr: IntArray): IntArray {
    for (i in arr.indices) {
        // Assume the first unsorted element is the smallest
        var minIndex = i
        for (j in i + 1 until arr.size) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        // Swap the smallest element with the first unsorted element
        val temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    return arr
}

Code Walkthrough

Outer Loop:
- The outer loop starts from the first element and moves towards the last, representing the growing sorted section.
Inner Loop:
- The inner loop scans the unsorted section of the array to find the smallest element.
Swap Operation:
- The smallest element is swapped with the first element of the unsorted section, ensuring the sorted section grows by one.

Visual Step-by-Step Process

Initial Array: [29, 10, 14, 37, 13]

Pass 1:

[29, 10, 14, 37, 13]  // Find minimum in entire array
 ↓   ↓         
[10, 29, 14, 37, 13]  // 10 is minimum, swap with first element
 ✓

Pass 2:

[10, 29, 14, 37, 13]  // Find minimum in unsorted portion
 ✓   ↓          ↓
[10, 13, 14, 37, 29]  // 13 is minimum, swap with second element
 ✓   ✓

Pass 3:

[10, 13, 14, 37, 29]  // Find minimum in unsorted portion
 ✓   ✓   ↓
[10, 13, 14, 37, 29]  // 14 is already in position
 ✓   ✓   ✓

Pass 4:

[10, 13, 14, 37, 29]  // Find minimum in unsorted portion
 ✓   ✓   ✓   ↓   ↓
[10, 13, 14, 29, 37]  // 29 is minimum, swap with fourth element
 ✓   ✓   ✓   ✓

Final Result:

[10, 13, 14, 29, 37]  // Array is sorted
 ✓   ✓   ✓   ✓   ✓

Legend:

↓ : Elements being compared
✓ : Sorted portion
Unmarked: Unsorted portion

Time Complexity Analysis

Best Case: O(n²)

Even if the array is already sorted, Selection Sort still needs to verify this by comparing all elements
For each element i, it needs to scan through (n-i) elements to confirm it's in the right position
Total comparisons: (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

Worst Case: O(n²)

Occurs when array is sorted in reverse order
Same number of comparisons as best case
Maximum number of swaps needed (n-1 swaps)

Average Case: O(n²)

Regardless of input distribution, Selection Sort always makes the same number of comparisons
Number of comparisons: n(n-1)/2
Number of swaps ranges from 0 to (n-1)

Space Complexity: O(1)

Only requires a single additional memory space for the swap operation
Sorts in-place, modifying the original array

Detailed Performance Breakdown

Number of Operations

For an array of size n:

Comparisons:
- First pass: (n-1) comparisons
- Second pass: (n-2) comparisons
- Third pass: (n-3) comparisons And so on...

Total comparisons = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

Swaps:
- Best case: 0 swaps (already sorted)
- Worst case: (n-1) swaps (reverse sorted)
- Average case: (n-1)/2 swaps

Performance Table

Array Size (n)	Comparisons	Worst Case Swaps
10	45	9
100	4,950	99
1,000	499,500	999

Optimization Techniques

Early Termination
- If no swaps are made in a pass, the array is sorted
- However, this doesn't improve the big-O complexity
Memory Usage Optimization

   fun selectionSort(arr: IntArray) {
       for (i in arr.indices) {
           var minIdx = i
           for (j in i + 1 until arr.size) {
               if (arr[j] < arr[minIdx]) minIdx = j
           }
           // Single swap operation using XOR
           if (i != minIdx) {
               arr[i] = arr[i] xor arr[minIdx]
               arr[minIdx] = arr[i] xor arr[minIdx]
               arr[i] = arr[i] xor arr[minIdx]
           }
       }
   }

Comparison with Other Sorting Algorithms

Algorithm	Time Complexity (Average)	Space Complexity	Stable	In-Place
Selection Sort	O(n²)	O(1)	No	Yes
Bubble Sort	O(n²)	O(1)	Yes	Yes
Quick Sort	O(n log n)	O(log n)	No	Yes
Merge Sort	O(n log n)	O(n)	Yes	No

Advantages and Disadvantages of Selection Sort

Advantages:

Simple to understand and implement
Performs well on small datasets
Requires no additional memory

Disadvantages:

Inefficient for large datasets due to O(n²) time complexity
Not a stable sorting algorithm (does not preserve the order of equal elements)

Conclusion

Selection Sort is a straightforward sorting algorithm best suited for small datasets or learning purposes. While it may not match the efficiency of more advanced algorithms like Merge Sort or Quick Sort, its simplicity and in-place sorting make it a useful tool in specific scenarios.

Understanding Merge Sort in Kotlin: A Beginner's Guide

WolfOf420Stret — Wed, 08 Jan 2025 10:14:42 +0000

Understanding Merge Sort: A Comprehensive Guide

What is Merge Sort?

Merge Sort is one of the most efficient and widely-used sorting algorithms. It is a divide-and-conquer algorithm, meaning it breaks the problem into smaller subproblems, solves them independently, and then combines their solutions to solve the original problem.

The main idea behind Merge Sort is to divide the input array into smaller subarrays until each subarray contains only one element. Then, these subarrays are merged back together in a sorted manner, resulting in a completely sorted array.

Merge Sort is particularly useful for large datasets due to its efficiency, with a time complexity of O(n log n) in both the average and worst-case scenarios. This makes it much faster than simpler algorithms like Bubble Sort for larger datasets.

When to Use Merge Sort?

Merge Sort is one of the most versatile sorting algorithms, offering excellent performance and stability (it maintains the relative order of equal elements). Here's when it's a good choice:

Large Datasets: Unlike Bubble Sort or Insertion Sort, Merge Sort is highly efficient for sorting large datasets, as its time complexity grows logarithmically with the input size.
Stable Sorting: If stability is important in your application (e.g., preserving the relative order of objects with equal keys), Merge Sort is an ideal choice.
External Sorting: Merge Sort works well for sorting data that doesn't fit into memory, as it can handle data stored in chunks.

However, Merge Sort does require extra memory for its temporary arrays, making it less suitable for applications with strict memory constraints.

How Merge Sort Works

Merge Sort operates in two main phases:

Divide: The input array is recursively split into two halves until each subarray has only one element (a single-element array is inherently sorted).
Conquer and Merge: The subarrays are merged back together in sorted order, step by step, until the entire array is sorted.

Step-by-Step Explanation

Here's how Merge Sort works in detail:

Split the Array:
- Divide the array into two halves, left and right, until each subarray has only one element.
Sort and Merge:
- Compare the elements of the two subarrays and merge them into a new sorted array.
- Continue merging until all subarrays are combined into one fully sorted array.
Repeat Until Sorted:
- Continue recursively splitting and merging until the entire array is sorted.

Visual Representation of Merge Sort

Merge Sort works by creating a binary tree of splits, which are merged back together in sorted order.

For example, sorting the array [8, 3, 7, 4, 6, 2, 5, 1] involves:

Dividing: [8, 3, 7, 4] and [6, 2, 5, 1] → further split into single-element arrays.
Merging: [3, 8], [4, 7], [2, 6], [1, 5] → continue merging.
Result: A fully sorted array [1, 2, 3, 4, 5, 6, 7, 8].

Pseudocode for Merge Sort

Here's a high-level pseudocode for Merge Sort:

function mergeSort(arr):
    if size of arr <= 1:
        return arr

    mid = size of arr / 2
    left = mergeSort(arr[0...mid])
    right = mergeSort(arr[mid...end])

    return merge(left, right)

function merge(left, right):
    result = empty array
    while left and right are not empty:
        if left[0] <= right[0]:
            append left[0] to result
            remove left[0]
        else:
            append right[0] to result
            remove right[0]

    append remaining elements of left and right to result
    return result

Implementing Merge Sort in Kotlin

Here's how you can implement Merge Sort in Kotlin:

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr

    // Split the array into two halves
    val mid = arr.size / 2
    val left = arr.sliceArray(0 until mid)
    val right = arr.sliceArray(mid until arr.size)

    // Recursively sort both halves
    return merge(mergeSort(left), mergeSort(right))
}

fun merge(left: IntArray, right: IntArray): IntArray {
    val result = mutableListOf<Int>()
    var i = 0
    var j = 0

    // Merge the two sorted arrays
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            result.add(left[i])
            i++
        } else {
            result.add(right[j])
            j++
        }
    }

    // Add any remaining elements
    while (i < left.size) {
        result.add(left[i])
        i++
    }
    while (j < right.size) {
        result.add(right[j])
        j++
    }

    return result.toIntArray()
}

Code Walkthrough

Base Case:
- If the array contains 0 or 1 element, it's already sorted, so we return it directly.
Divide:
- The array is split into two halves using slicing.
Recursive Calls:
- The mergeSort function is called recursively for both halves of the array.
Merge:
- The merge function compares elements from the left and right halves and combines them into a sorted array.
- Any remaining elements in either half are added to the result.

Optimizations

Merge Sort can be optimized for performance in the following ways:

Avoid Excessive Copying: Instead of slicing arrays, use index pointers to avoid creating new arrays at every step.
Switch to Insertion Sort for Small Subarrays: For small arrays (e.g., size < 10), Insertion Sort may be faster due to reduced overhead.

Advantages of Merge Sort

Efficiency: With a time complexity of O(n log n), Merge Sort is highly efficient for large datasets.
Stability: It preserves the relative order of equal elements.
Divide-and-Conquer Paradigm: This makes it easy to parallelize.

Disadvantages

Memory Usage: Merge Sort requires additional memory for temporary arrays, making it less suitable for memory-constrained environments.

Time Complexity Analysis

Best Case: O(n log n)

Dividing: log n levels
Merging: n operations per level
Total: n * log n

Worst Case: O(n log n)

Same as best case - one of Merge Sort's advantages
is its consistent performance

Space Complexity: O(n)

Requires additional array of size n for merging
Plus log n stack space for recursion

Comparison with Other Sorting Algorithms

Algorithm	Time (Best)	Time (Average)	Time (Worst)	Space	Stable
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes

Optimizations

1. Hybrid with Insertion Sort

fun optimizedMergeSort(arr: IntArray, threshold: Int = 10): IntArray {
    if (arr.size <= 1) return arr
    if (arr.size <= threshold) {
        return insertionSort(arr)  // Use insertion sort for small arrays
    }

    val mid = arr.size / 2
    val left = arr.sliceArray(0 until mid)
    val right = arr.sliceArray(mid until arr.size)

    return merge(
        optimizedMergeSort(left, threshold),
        optimizedMergeSort(right, threshold)
    )
}

2. In-Place Merging

fun mergeInPlace(arr: IntArray, start: Int, mid: Int, end: Int) {
    val leftArray = arr.sliceArray(start until mid)
    var i = 0
    var j = mid
    var k = start

    while (i < leftArray.size && j < end) {
        if (leftArray[i] <= arr[j]) {
            arr[k] = leftArray[i]
            i++
        } else {
            arr[k] = arr[j]
            j++
        }
        k++
    }

    while (i < leftArray.size) {
        arr[k] = leftArray[i]
        i++
        k++
    }
}

Memory Usage Visualization

Original Array:  [38, 27, 43, 3, 9, 82, 10]
                  ↓
Temporary Arrays: Left:[38, 27, 43, 3] Right:[9, 82, 10]
                  ↓
Merge Buffer:    [3, 9, 10, 27, 38, 43, 82]

Practical Implementation Tips

Memory Management

// Reuse arrays to reduce allocation
class MergeSorter {
    private lateinit var tempArray: IntArray

    fun sort(arr: IntArray) {
        tempArray = IntArray(arr.size)
        mergeSortWithBuffer(arr, 0, arr.size - 1)
    }
}

Parallel Implementation

fun parallelMergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr

    val mid = arr.size / 2
    val left = arr.sliceArray(0 until mid)
    val right = arr.sliceArray(mid until arr.size)

    return runBlocking {
        val sortedLeft = async { mergeSort(left) }
        val sortedRight = async { mergeSort(right) }
        merge(sortedLeft.await(), sortedRight.await())
    }
}

Real-World Performance Metrics

For array size n = 1,000,000:

Algorithm        Time (ms)    Memory (MB)
----------------------------------------
Merge Sort       150         ~8
Quick Sort       130         ~0.1
Heap Sort        180         ~0
Bubble Sort      45,000      ~0

Conclusion

Merge Sort is an elegant and powerful sorting algorithm that combines efficiency and stability. While it may not always be the most practical choice for small datasets, its predictable performance and divide-and-conquer approach make it a cornerstone of algorithmic thinking.

By mastering Merge Sort, you'll not only understand a highly efficient sorting method but also gain insight into the design principles behind many advanced algorithms.

Further Reading
To deepen your understanding of sorting algorithms and Kotlin programming, here are some additional resources:

"Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein - A comprehensive guide to algorithms, including a detailed section on sorting algorithms.
GeeksforGeeks Sorting Algorithms - Sorting Algorithms - A collection of tutorials and examples covering various sorting algorithms.

Kotlin Documentation - Kotlin Official Documentation - Learn more about Kotlin’s features and how to use them effectively.

LeetCode - LeetCode Sorting Problems - Practice your skills with a variety of sorting problems in Kotlin.

By exploring these resources, you’ll be well on your way to mastering sorting algorithms and becoming proficient in Kotlin. Happy coding!

DEV Community: WolfOf420Stret

I Built an AI Land Fraud Detector for Kenya — Here's the Full Engineering Story

The Problem Is Personal

The Hackathon That Pushed Me to Build It

What TitleTrust Actually Does

1. The Investigator Opens a Session

2. The Forensic Agent Reads the Documents

3. The Location Agent Checks Physical Reality

4. The Orchestrator Keeps the Investigation Moving

5. The Mobile Client Shows Everything, Live

The Engineering Architecture — Every Decision Tied to the Product

Why SSE Instead of WebSockets

Why Redis Streams (Not Just a Message Queue)

Why Two Cursors (event_id + stream_offset)

Why In-Process Broadcaster + Redis Streams (The Hybrid)

Why Evidence Gets SHA256 Checksums and Trace IDs

Why Deterministic Chaos Tests

Architecture Diagram

A Day in the Life: One Investigation

What I Used Gemini 3 For Specifically

The Numbers

Key Engineering Takeaways

What's Next

The Repo

Final Thought

Building AdMidnight: A Privacy-Preserving Ad Platform on the Midnight Blockchain

Table of Contents

The Problem with Advertising

What is Midnight?

Programmable Data Protection

Compact: Midnight's Contract Language

The Midnight SDK

The MLH Hackathon Context

The Rules That Shaped the Build

Architecture Overview

Why a Monorepo?

The Four Execution Layers

The ZK Proof Flow

Why Nullifiers?

The Sealed Bid Auction

Building the Stack

Day 1: Foundation

Day 2: The Hard Parts

The Monorepo Build Problem

AI-Assisted Development

What Worked Well

What Didn't Work

The Workflow That Actually Worked

Code Review with CodeRabbit

What CodeRabbit Caught

The Review Workflow

Safeguards and Quality Gates

Never Expose Raw User Data

Environment Variable Discipline

Input Validation Everywhere

MIDNIGHT_DEV_MODE

The Ugly Parts

The import type Bug

The Docker Build Loop

The Proof Server Image Tag

What I'd Do Differently

What's Next

Closing Thoughts

Resources

Eco Trace

What I Built

Demo

Code

How I Built It

Architecture: Clean, DRY, and SOLID throughout

Snowflake: Live emission factors + community benchmarking

Backboard: AI that actually remembers you

Auth0 for Agents: Real auth plus a background scanner

Solana: On-chain achievement badges

GitHub Copilot: The coding co-pilot

The UI: "Bioluminescent Data"

Prize Categories

The Future of Self-Care: How AI is Revolutionizing Personalized Affirmations with Affirmi

The Problem with Generic Affirmations: Why One-Size-Fits-All Doesn't Work

Enter Affirmi: AI-Powered Personalization

Why Two Cursors (`event_id` + `stream_offset`)

The `import type` Bug