Markov Chains Done Quick

markov.js

// @TODO: Read this to improve model http://www.roguebasin.com/index.php?title=Names_from_a_high_order_Markov_Process_and_a_simplified_Katz_back-off_scheme

const rand = (min, max) => ((Math.random() * max) + min) | 0

class ProbabilityMap {
  constructor (map) { // map = {foo: 32, bar: 21}
    this.calculateSize = () => {
      let count = 0
      for (let [,value] of this.set) {
        count += value
      }
      return count
    }
    this.set = map ? new Map(Object.entries(map)) : new Map()
    this.size = map ? this.calculateSize() : 0
    this.increment = (key) => {
      this.size++
      if (this.set.has(key)) this.set.set(key, this.set.get(key) + 1)
      else this.set.set(key, 1)
    }
    this.pick = () => {
      let pick = this.size * Math.random()
      for (let [key, value] of this.set) {
        pick -= value
        if (pick < 0) return key
      }
    }
  }
}

class MarkovChain {
  constructor(order = 0) {
    this.order = order
    this.set = new Map()
    this.insert = (key, value) => {
      if (!this.set.has(key)) this.set.set(key, new ProbabilityMap())
      const map = this.set.get(key)
      map.increment(value)
    }

    this.insertString = (str) => {
      for(let len = 0; len < str.length - this.order; len++) {
        this.insert(str.substr(len, this.order), str.charAt(len + this.order))
      }
    }

    this.pick = () => {
      // @todo: Look at this, think it needs some work
      const size = this.set.size
      let pick = Math.random() * size
      for (let [key] of this.set) {
        pick--;
        if (pick < 0) return key
      }
    }
  }
}

class MarkovProcess {
  constructor(max_order = 2) {
    this.orders = Array.from({ length: max_order + 1}, (v, n) => new MarkovChain(n))
    this.firstOrder = new ProbabilityMap()
    this.max_order = max_order
    this.insertString = str => {
      for (let chain of this.orders) {
        this.firstOrder.increment(str.substr(0, this.max_order))
        chain.insertString(str)
      }
    }

    this.pick = (str = '') => {
      for (let i = this.max_order; i >= 0; i--) {
        let newStr = str.substring(str.length - i, str.length)
        const chain = this.orders[i]
        if (chain.set.has(newStr)) {
          return chain.set.get(newStr).pick()
        }
      }
    }

    this.generate = ({minLen = 7, maxLen = 12, useFirstOrder = true, firstOrder = this.max_order}) => {
      const len = (Math.random() * maxLen + minLen) | 0
      let str = useFirstOrder ? this.firstOrder.pick() : this.orders[firstOrder].pick()
      while (str.length <= len) {
        str += this.pick(str)
      }
      return str
    }
  }
}

const trainMarkovProcess = (order = 3, data = '', separator = ' ') => {
  const process = new MarkovProcess(order)
  const testData = data.split(separator).filter(Boolean)
  for (let str of testData) {
    process.insertString(str)
  }
  return process
}

const firstNames = `aaron ada adam adrian adrienne agnes alan albert alberta alberto alex alexander alexandra alexis alfred alfredo alice alicia alison allan allen allison alma alvin alyssa amanda amber amelia amy ana andre andrea andrew andy angel angel angela angelica angelina angie anita ann anna anne annette annie anthony antoinette antonia antonio april arlene armando arnold arthur ashley audrey barbara barry beatrice becky belinda ben benjamin bernadette bernard bernice bertha bessie beth bethany betsy betty beulah beverly bill billie billy blanca blanche bob bobbie bobby bonnie brad bradley brandi brandon brandy brenda brent brett brian bridget brittany brooke bruce bryan byron calvin camille candace candice carl carla carlos carmen carol carole caroline carolyn carrie casey casey cassandra catherine cathy cecelia cecil cecilia celia chad charlene charles charlie charlotte chelsea cheryl chester chris christian christie christina christine christopher christy cindy claire clara clarence claude claudia clayton clifford clifton clinton clyde cody colleen connie constance cora corey cory courtney craig cristina crystal curtis cynthia daisy dale dan dana daniel danielle danny darla darlene darrell darren darryl daryl dave david dawn dean deanna debbie deborah debra delia della delores denise dennis derek derrick desiree diana diane dianna dianne dixie dolores don donald donna dora doreen doris dorothy douglas duane dustin dwayne dwight earl ebony eddie edgar edith edna eduardo edward edwin eileen elaine eleanor elena elisa elizabeth ella ellen elmer eloise elsa elsie elvira emily emma enrique eric erica erik erika erin erma ernest ernestine essie estelle esther ethel eugene eula eunice eva evelyn everett faith fannie faye felicia felix fernando flora florence floyd frances francis francis francisco frank franklin fred freda freddie frederick gabriel gail gary gayle gene geneva genevieve george georgia gerald geraldine gertrude gilbert gina ginger gladys glen glenda glenn gloria gordon grace greg gregory gretchen guadalupe guy gwen gwendolyn hannah harold harriet harry harvey hattie hazel heather hector heidi helen henrietta henry herbert herman hilda holly hope howard hugh ian ida inez irene iris irma isaac isabel ivan jack jackie jacob jacqueline jacquelyn jaime jaime james jamie jamie jan jana jane janet janice janie janis jared jasmine jason javier jay jean jeanette jeanne jeannette jeannie jeff jeffery jeffrey jenna jennie jennifer jenny jeremy jerome jerry jesse jessica jessie jessie jesus jill jim jimmie jimmy jo joan joann joanna joanne jodi jody joe joel johanna john johnnie johnnie johnny jon jonathan jordan jorge jose josefina joseph josephine joshua joy joyce juan juana juanita judith judy julia julian julie julio june justin kara karen kari karl karla kate katherine kathleen kathryn kathy katie katrina kay kayla keith kelley kelli kellie kelly kelly ken kendra kenneth kent kerry kevin kim kimberly kirk krista kristen kristi kristie kristin kristina kristine kristy krystal kurt kyle lana lance larry latoya laura lauren laurie laverne lawrence leah lee lee leigh lela lena leo leon leona leonard leroy leslie leslie lester leticia lewis lila lillian lillie linda lindsay lindsey lisa lloyd lois lola lonnie lora lorena lorene loretta lori lorraine louis louise lucia lucille lucy luis lula luz lydia lynda lynette lynn lynne mabel mable madeline mae maggie mamie mandy manuel marc marcella marcia marcus margaret margarita margie marguerite maria marian marianne marie marilyn mario marion marion marjorie mark marlene marsha marshall marta martha martin marvin mary maryann mathew matthew mattie maureen maurice max maxine may megan meghan melanie melba melinda melissa melody melvin mercedes meredith michael micheal michele michelle miguel mike mildred milton mindy minnie miranda miriam misty mitchell molly mona monica monique morris muriel myra myrtle nadine nancy naomi natalie natasha nathan nathaniel neil nellie nelson nettie nicholas nichole nicole nina nora norma norman olga olive olivia ollie opal ora oscar pam pamela pat patricia patrick patsy patti patty paul paula paulette pauline pearl pedro peggy penny perry peter philip phillip phyllis priscilla rachael rachel rafael ralph ramon ramona randall randy raquel raul ray raymond rebecca regina reginald rene renee rhonda ricardo richard rick ricky rita robert roberta roberto robin robyn rochelle rodney roger roland ron ronald ronnie rosa rosalie rose rosemarie rosemary rosie ross roxanne roy ruben ruby russell ruth ryan sabrina sadie sally salvador sam samantha samuel sandra sandy sara sarah scott sean sergio seth shane shannon shari sharon shawn shawna sheila shelia shelley shelly sheri sherri sherry sheryl shirley sidney silvia sonia sonja sonya sophia sophie stacey stacy stanley stella stephanie stephen steve steven sue susan susie suzanne sylvia tabitha tamara tami tammy tanya tara tasha ted teresa teri terrance terrence terri terry terry thelma theodore theresa thomas tiffany tim timothy tina todd tom tommy toni tony tonya tracey traci tracy tracy travis tricia troy tyler tyrone valerie vanessa velma vera verna vernon veronica vicki vickie vicky victor victoria vincent viola violet virgil virginia vivian wade wallace walter wanda warren wayne wendy wesley whitney willard william willie willie wilma winifred yolanda yvette yvonne zachary`
const lastNames = `abbott acevedo acosta adams adkins aguilar aguirre albert alexander alford allen allison alston alvarado alvarez anderson andrews anthony armstrong arnold ashley atkins atkinson austin avery avila ayala ayers bailey baird baker baldwin ball ballard banks barber barker barlow barnes barnett barr barrera barrett barron barry bartlett barton bass bates battle bauer baxter beach bean beard beasley beck becker bell bender benjamin bennett benson bentley benton berg berger bernard berry best bird bishop black blackburn blackwell blair blake blanchard blankenship blevins bolton bond bonner booker boone booth bowen bowers bowman boyd boyer boyle bradford bradley bradshaw brady branch bray brennan brewer bridges briggs bright britt brock brooks brown browning bruce bryan bryant buchanan buck buckley buckner bullock burch burgess burke burks burnett burns burris burt burton bush butler byers byrd cabrera cain calderon caldwell calhoun callahan camacho cameron campbell campos cannon cantrell cantu cardenas carey carlson carney carpenter carr carrillo carroll carson carter carver case casey cash castaneda castillo castro cervantes chambers chan chandler chaney chang chapman charles chase chavez chen cherry christensen christian church clark clarke clay clayton clements clemons cleveland cline cobb cochran coffey cohen cole coleman collier collins colon combs compton conley conner conrad contreras conway cook cooke cooley cooper copeland cortez cote cotton cox craft craig crane crawford crosby cross cruz cummings cunningham curry curtis dale dalton daniel daniels daugherty davenport david davidson davis dawson day dean decker dejesus delacruz delaney deleon delgado dennis diaz dickerson dickson dillard dillon dixon dodson dominguez donaldson donovan dorsey dotson douglas downs doyle drake dudley duffy duke duncan dunlap dunn duran durham dyer eaton edwards elliott ellis ellison emerson england english erickson espinoza estes estrada evans everett ewing farley farmer farrell faulkner ferguson fernandez ferrell fields figueroa finch finley fischer fisher fitzgerald fitzpatrick fleming fletcher flores flowers floyd flynn foley forbes ford foreman foster fowler fox francis franco frank franklin franks frazier frederick freeman french frost fry frye fuentes fuller fulton gaines gallagher gallegos galloway gamble garcia gardner garner garrett garrison garza gates gay gentry george gibbs gibson gilbert giles gill gillespie gilliam gilmore glass glenn glover goff golden gomez gonzales gonzalez good goodman goodwin gordon gould graham grant graves gray green greene greer gregory griffin griffith grimes gross guerra guerrero guthrie gutierrez guy guzman hahn hale haley hall hamilton hammond hampton hancock haney hansen hanson hardin harding hardy harmon harper harrell harrington harris harrison hart hartman harvey hatfield hawkins hayden hayes haynes hays head heath hebert henderson hendricks hendrix henry hensley henson herman hernandez herrera herring hess hester hewitt hickman hicks higgins hill hines hinton hobbs hodge hodges hoffman hogan holcomb holden holder holland holloway holman holmes holt hood hooper hoover hopkins hopper horn horne horton house houston howard howe howell hubbard huber hudson huff huffman hughes hull humphrey hunt hunter hurley hurst hutchinson hyde ingram irwin jackson jacobs jacobson james jarvis jefferson jenkins jennings jensen jimenez johns johnson johnston jones jordan joseph joyce joyner juarez justice kane kaufman keith keller kelley kelly kemp kennedy kent kerr key kidd kim king kinney kirby kirk kirkland klein kline knapp knight knowles knox koch kramer lamb lambert lancaster landry lane lang langley lara larsen larson lawrence lawson le leach leblanc lee leon leonard lester levine levy lewis lindsay lindsey little livingston lloyd logan long lopez lott love lowe lowery lucas luna lynch lynn lyons macdonald macias mack madden maddox maldonado malone mann manning marks marquez marsh marshall martin martinez mason massey mathews mathis matthews maxwell may mayer maynard mayo mays mcbride mccall mccarthy mccarty mcclain mcclure mcconnell mccormick mccoy mccray mccullough mcdaniel mcdonald mcdowell mcfadden mcfarland mcgee mcgowan mcguire mcintosh mcintyre mckay mckee mckenzie mckinney mcknight mclaughlin mclean mcleod mcmahon mcmillan mcneil mcpherson meadows medina mejia melendez melton mendez mendoza mercado mercer merrill merritt meyer meyers michael middleton miles miller mills miranda mitchell molina monroe montgomery montoya moody moon mooney moore morales moran moreno morgan morin morris morrison morrow morse morton moses mosley moss mueller mullen mullins munoz murphy murray myers nash navarro neal nelson newman newton nguyen nichols nicholson nielsen nieves nixon noble noel nolan norman norris norton nunez obrien ochoa oconnor odom odonnell oliver olsen olson oneal oneil oneill orr ortega ortiz osborn osborne owen owens pace pacheco padilla page palmer park parker parks parrish parsons pate patel patrick patterson patton paul payne pearson peck pena pennington perez perkins perry peters petersen peterson petty phelps phillips pickett pierce pittman pitts pollard poole pope porter potter potts powell powers pratt preston price prince pruitt puckett pugh quinn ramirez ramos ramsey randall randolph rasmussen ratliff ray raymond reed reese reeves reid reilly reyes reynolds rhodes rice rich richard richards richardson richmond riddle riggs riley rios rivas rivera rivers roach robbins roberson roberts robertson robinson robles rocha rodgers rodriguez rodriquez rogers rojas rollins roman romero rosa rosales rosario rose ross roth rowe rowland roy ruiz rush russell russo rutledge ryan salas salazar salinas sampson sanchez sanders sandoval sanford santana santiago santos sargent saunders savage sawyer schmidt schneider schroeder schultz schwartz scott sears sellers serrano sexton shaffer shannon sharp sharpe shaw shelton shepard shepherd sheppard sherman shields short silva simmons simon simpson sims singleton skinner slater sloan small smith snider snow snyder solis solomon sosa soto sparks spears spence spencer stafford stanley stanton stark steele stein stephens stephenson stevens stevenson stewart stokes stone stout strickland strong stuart suarez sullivan summers sutton swanson sweeney sweet sykes talley tanner tate taylor terrell terry thomas thompson thornton tillman todd torres townsend tran travis trevino trujillo tucker turner tyler tyson underwood valdez valencia valentine valenzuela vance vang vargas vasquez vaughan vaughn vazquez vega velasquez velazquez velez villarreal vincent vinson wade wagner walker wall wallace waller walls walsh walter walters walton ward ware warner warren washington waters watkins watson watts weaver webb weber webster weeks weiss welch wells west wheeler whitaker white whitehead whitfield whitley whitney wiggins wilcox wilder wiley wilkerson wilkins wilkinson william williams williamson willis wilson winters wise witt wolf wolfe wong wood woodard woods woodward wooten workman wright wyatt wynn yang yates york young zamora zimmerman`
const cityNames = `abilene akron albuquerque alexandria allentown amarillo anaheim anchorage annarbor antioch arvada athens atlanta augusta aurora aurora austin bakersfield baltimore batonrouge beaumont bellevue berkeley billings boise boston boulder bridgeport brokenarrow brownsville buffalo burbank cambridge capecoral carlsbad carrollton cary centennial chandler charleston charlotte chattanooga chesapeake chicago chulavista cincinnati clarksville clearwater cleveland clovis collegestation columbia columbia columbus columbus concord corona corpuschristi costamesa dallas davenport dayton denver detroit downey durham edison elmonte elgin elkgrove eugene evansville everett fairfield fargo fortcollins fortlauderdale fortwayne fortworth fremont fresno frisco fullerton garland gilbert glendale glendale grandprairie grandrapids greenbay greensboro gresham hampton henderson hillsboro hollywood honolulu houston huntingtonbeach huntsville independence indianapolis inglewood irvine irving jackson jacksonville jerseycity joliet kansascity kansascity kent killeen knoxville lafayette lakeland lakewood lancaster lansing laredo lascruces lasvegas lewisville lexington lincoln littlerock longbeach losangeles lowell lubbock macon madison manchester mcallen mckinney memphis mesa mesquite miami miamigardens midland milwaukee minneapolis mobile montgomery murfreesboro murrieta naperville nashville neworleans newyork newportnews norfolk norman northcharleston northlasvegas norwalk oakland oceanside oklahomacity olathe omaha ontario orange orlando overlandpark palmbay palmdale pasadena pasadena paterson pearland pembrokepines peoria peoria philadelphia phoenix pittsburgh plano pomona pompanobeach portland providence pueblo raleigh ranchocucamonga reno rialto richardson richmond riverside rockford roundrock sacramento saintpaul salem salinas saltlakecity sanantonio sandiego sanfrancisco sanmateo sandysprings santaana santaclara santaclarita santamaria santarosa scottsdale seattle simivalley siouxfalls southbend springfield springfield stamford stockton sunnyvale surprise syracuse tallahassee tampa temecula tempe thornton toledo topeka torrance tucson tulsa tyler vallejo vancouver victorville virginiabeach vista warren washington waterbury westjordan westpalmbeach westvalleycity westminster wichita wichitfalls wilmington winstonsalem woodbridge yonkers`
const streetNames = `Acme Acorn Alert Amity Angelos Anglo Argent Attridge August Avoca Baxter Bengal Bergen Bob Brant Card Clarion Cooper Copper Cuba Decker Dicha Dixie Doric Drummond Duncombe Dunnes Elim Fisher Gatun Gerke Globe Harlem Hobart Hodges Hooker Hulbert Icehouse Imperial Iron Jack Jack Jack Jerome Kenny Keyes Lassen Ludlow Lulu Mabel Malden Morgan Mulford Nobles Ophir Orange Osage Oscar Parkhurst Pink Pino Redfield Rock Ross Saint Saint School Scott Shaw Sloan Trader Troy Tulip Tuscany Venard Wagner Waldo 02nd 03rd 04th 05th 06th 07th 08th 09th 10th 11th 12th 14th 15th 16th 17th 18th 19th 20th 21st 22nd 23rd 24th 25th 26th 27th 28th 29th 30th 31st 32nd 33rd 34th 35th 36th 37th 38th 39th 40th 41st 42nd 43rd 44th 45th 46th 47th 48th Acacia Acevedo Admiral Agnon Aloha Alton Amazon Anza Anzavista Appleton Aptos Arellano Argonaut Arleta Armstrong Arnold Arthur Ashton Avalon Balceta Bancroft Barcelona Barnard Barneveld Beaumont Behr Belgrave Belle Bellevue Belmont Benton Bigler Bitting Blanken Blythdale Brazil Brentwood Brighton Brompton Brookdale Bruce Buena Buena Burke Burnett Burnett Burnside Burr Caine California Camellia Campbell Capistrano Capitol Cardenas Carroll Caselli Casitas Castelo Castenada Castle Cayuga Cecilia Cedro Central Cerritos Charter Chaves Chester Chilton Circular Clarendon Cleo College Colon Columbus Commonwealth Corbett Cortes Cortland Coso Cragmont Crescent Crissy Custer Cutler Davidson De Del Del Delano Dellbrook Diaz Donner Dorantes Dorman Duboce Edgar Edgewood Egbert Ellington Encanto Escondido Esmeralda Estero Euclid Eugenia Evans Excelsior Fair Fairfax Farragut Faxon Felix Fisher Fitzgerald Flood Florentine Foote Forest Fortuna Fowler France Fuente Funston Galindo Galvez Garcia Garrison Gateview General Geneva Gillette Gilman Glenbrook Golden Goleta Gorgas Grafton Granada Grand Grant Greenough Greenwood Hamerton Hardie Harkness Harold Hazelwood Healley Hearst Heather Hernandez Hester Heyman Highland Higuera Hiliritas Hill Hillway Hoffman Holladay Hollister Holloway Hopkins Horne Hudson Huron Idora Ignacio Ingerson Innes Iris Issleib Italley Jamestown Jarboe Jerrold Joost Jordan Josepha Josiah Judson Jules Julian Kelloch Kempton Key Keyes Kirkwood Kobbe La La Lakeview Lakewood Lansdale Lathrop Lawrence Le Lee Leland Liggett Linares Lippard Locksley Lomita Long Lopez Lupine Lydia Macarthur Maddux Madrone Magellan Majestic Mangels Manzanita Marcela Margaret Marne Marston Martha Masonic Mccarthy Mcdowell Mckinley Mckinnon Mclaren Meade Meda Melba Melrose Mendosa Merced Mesa Mirabel Miramar Modoc Montalvo Montecito Moraga Mount Mountain Mullen Naglee Nahua Nantucket Navajo Nelson Newcomb Niagara Niantic Nido Nimitz North Nueva Oakdale Ocean Ogden Olney Oloran Oneida Onondaga Oreilly Orizaba Otega Otsego Ottawa Pacific Palm Palmetto Palo Paloma Palou Paradise Park Parker Parnassus Paul Peninsula Pennsylvania Peralta Perasto Persia Peru Peters Phelan Pico Pilgrim Pinto Plymouth Point Potrero Powers Powhattan Precita Presidio Prospect Pulaski Quebec Quesada Rae Ralston Ramona Raymond Revere Rex Richardson Richland Richter Ridgewood Riley Rivas Robblee Rockaway Rossi Ruckman Rudden Russia Saint Saint Saint Saint Salinas Sampson San San San San San San San San San San San Santa Santa Santa Santa Santa Santa Santa Santa Santa Santa Scotia Seacliff Seminole Seneca Shafter Shawnee Sheridan Shore Shoup Sickles Silver Sola Sotelo South Southern Spear Standish Stanford Staples Stillings Stoneybrook Stoneyford Storey Sumner Sunnydale Sutro Swiss Teddy Terra Thomas Thor Thornton Tiffany Tioga Tocoloma Tompkins Topeka Torney Towerside Treat Tucker Tunnel Underwood Upton Valdez Vale Van Van Van Varela Vasquez Velasco Ventura Virginia Visitacion Wallace Watt West West West Wheeler Whipple Wilde Williams Williar Woodland Woodside Worcester Wyman Yerba Yosemite Zanowitz Alemany Arguello Bay Bernal Cervantes Claremont Dewey Diamond Executive Font Geary Harrison Hunters Junipero Laguna Lake Lincoln Marina Mission Mission Monterey Oshaughnessy Park Park Presidio Saint Skyline Sloat South Stanyan Sunset Telegraph Teresita Terry Turk Twin Washington Mission Mission Atoll Bayview Cloud Galewood Holly Juan Le Lindsay Mission Orsi Richards Science Thomas Whitney Amber Arballo Arelious Armory Auto Automobile Banbury Bayside Beachmont Bowling Bridgeview Broadmoor Bucareli Burlwood Burrows Calvert Cambon Canyon Chain Christopher Chumasero Cielito Clearfield Concourse Conservatory Conservatory Country Cranleigh Crespi Cresta Crestlake Crestline Crestmont Crossover Denslowe Eastwood Elmhurst Esquina Eucalleyptus Everglade Exposition Fernwood First First Forest Forest Garces Gardenside Gellert Giants Gladstone Glenview Gold Gonzalez Grijalva Hagiwara Havenside Hill Huntington Inverness John John John Johnstone Justin Kendall Kezar Lagunitas Lakeshore Legion Letterman Los Lyndhurst Main Malta Manor Marietta Marina Marine Mariner Martin Mayfair Maywood Meadowbrook Megan Middle Middlefield Miraloma Mission Molimo Monte Morningside Music Nancy Nautilus Nimitz North Northgate Northpoint Northwood Oak Overlook Panorama Park Parkridge Parque Pershing Portal Portola Raccoon Ravenwood Riverton Robinhood Robinson Rockdale Rockridge Rosewood Rossmoor Saddleback Saint Seal Second Serrano Silverview South Southwood Spreckels Springfield State Stonecrest Stow Stratford Sunview Sylvan Tapia Terrace Thomas Transverse Upland Urbano Veterans Vidal Warren Westgate Westmoorland Westside Westwood Willie Winston Woodacre Yerba Hunters Knockash Great Amatista Arbol Ashwood Beatrice Beeman Bertha Bertie Blairwood Blatchford Bonnie Brookhaven Brush Campus Canby Chancery Chula Clarke Claude Clover Coralino Coventry Davenport Emerald Emery Emil Farnsworth Fauntleroy Fenton Forsyth Fredela Galilee Gallagher Gibbon Gladiolus Glenhaven Goldberg Golding Harriet Hawkins Heritage Hillside Hitchcock Ils Inca Isadora Kaplan Kearny Lamson Lancaster Lettuce Lois Lori Lottie Lundys Macondray Maiden Mandalay Mark Mcrae Menoher Merriam Moore Mount Murray Napier Nelson Nimitz North North Oakhurst Old Onique Opalo Osceola Peek Penny Pierpoint Pinar Poppy Quickstep Racine Rebecca Ridge Robert Rosa Rosie Royal Safira Seawell Sibert Smith Sonora Soule South South Sproule Stoneridge Sunbeam Sunglow Tampa Thorp Toyon Treat Turk Vista Western Wyton Yerba Zampa Amatury Dove El Fisher Muir Piper Sibert Simonds Wright Clinton Elgin Public Forest Ingleside Perimeter Portal Armistead Battery Battery Battery Battery Battery Battery Battery Battery Battery Bayview Bercut Birmingham Bliss Central Christmas Church Compton Conservatory Coral Crisp Deems Dewitt Dormitory Dudley Dutch East East East Edie Fell Finley Forest Fort Funston Gardener Gibson Girard Golf Harbor Harding Hicks Hillcrest Howard Hunter Incinerator Kiska Macalla Mclaren Merchant Metson Middle Miller Millwright Music Nauman Navy North Northridge Oak Olympic Patten Pope Quarry Reardon Recycle Recycling Rod Schofield Shafter Sherman Sibley Signal South Sternberg Stilwell Taylor Thornburg Treasure Upper West West Yacht Yerba Abbey Acacia Acadia Acton Adair Adam Addison Alabama Alameda Alberta Albion Alder Alhambra Allen Allison Alma Alpha Alta Alvarado Alviso Alvord Amador Ambrose Ames Amherst Anderson Andover Andrew Ankeny Annie Anthony Antonio Anza Apollo Appleton Arago Arbor Arch Arkansas Arlington Ash Ashbury Athens Auburn Augusta Austin Avery Avila Aztec Bache Bacon Baden Badger Baker Balance Balboa Balmy Bank Banks Bannock Bartlett Bartol Battery Bay Bay Beach Beacon Beale Beaver Beckett Beideman Belcher Belden Belles Belvedere Bemis Bennington Bepler Bernard Bernice Berry Berry Bertita Bessie Beulah Beverly Birch Bird Bishop Blake Blanche Blandy Bluxome Boalt Bocana Bonifacio Bonita Bonview Borica Bosworth Boutwell Bowdoin Bowley Boyd Boylston Bradford Brady Brannan Brewster Bright Britton Broad Broderick Bronte Brook Brooks Brosnan Brown Brunswick Brussels Bryant Buchanan Burgoyne Burritt Burrows Bush Byxbee C Cabrillo Caledonia Calgary California Cambridge Camp Canby Capp Carl Carmel Carmelita Carolina Carr Carrie Carrizal Carson Carter Carver Case Cashmere Castillo Castle Castro Catalina Cedar Ceres Cesar Channel Chapman Charles Chattanooga Chenery Cherry Chesley Chestnut Child China Church Clara Clarke Clarkson Clay Clayton Clement Clementina Cleveland Clipper Clover Clyde Cochrane Colby Cole Coleman Coleridge Colin Collingwood Collins Colton Columbia Comerford Commercial Concord Congdon Congo Conkling Connecticut Conrad Converse Cook Cora Cordelia Cordova Cornwall Corona Coronado Corwin Cosgrove Costa Cotter Cowles Crane Craut Crook Cross Crystal Cumberland Curtis Cushman Cuvier Cypress Cyril D Daggett Dakota Danton Danvers Dartmouth Dashiell Davis Day De De De De De Dearborn Decatur Dehon Del Delancey Delaware Delmar Delta Deming Derby Desmond Detroit Diamond Diana Dickinson Digby Divisadero Division Dock Dodge Dolores Donahue Dore Dorland Double Douglass Downey Drake Drumm Dublin Duncan Dunshee Dunsmuir Dwight E Eagle Earl Eastman Ecker Eddy Edinburgh Edith Edna Edward El Eldridge Elizabeth Elk Ellert Elliot Ellis Ellsworth Elm Elmira Elsie Elwood Emerson Emma English Enterprise Erie Ervine Espanola Essex Eureka Eve Everson Exeter Fair Fairbanks Fairmount Faith Falmouth Farallones Farnum Federal Fell Felton Fern Fernandez Fielding Fifth Filbert Fillmore Fitch Flint Flora Florence Florida Flournoy Flower Foerster Folsom Ford Fountain Francis Francisco Franconia Frank Franklin Frederick Freelon Fremont Fresno Friedell Front Fulton Gambier Garden Garfield Gates Gaven Geary Gennessee Georgia Germania Getz Gibb Gilbert Gilroy Girard Gladys Glendale Glover Godeus Goethe Goettingen Gold Gordon Gorham Gough Gould Grace Graham Grattan Green Greenwich Griffith Grove Guerrero Guttenberg H Hahn Haight Hale Hallam Halleck Hamilton Hamlin Hampshire Hancock Hangah Hanover Hare Harlow Harper Harriet Harrington Harrison Harry Hartford Harvard Hattie Havelock Havens Hawes Hawthorne Hayes Hays Hayward Head Helen Helena Hemlock Henry Henry Hermann Heron Hickory High Hill Hilton Hitchcock Hoff Hoffman Hollis Holyoke Homer Homestead Hooper Horace Houston Howard Howth Hubbell Hugo Humboldt Hunt Hunter Hussey Hyde I Illinois India Indiana Industrial Ingalls Iowa Irving Irwin Isis Islais Ivy J Jackson Jansen Jauss Java Jefferson Jennings Jersey Jessie Jessie Jessie Jewett John John Joice Jones Joy Judah Julia Julius Juniper Juri Kalmanovitz Kansas Kate Kearny Keith Kent Kern King Kingston Kinzey Kirkham Kissling Lafayette Laguna Laidley Lake Lake Lake Lamartine Landers Lane Langton Lansing Lapidge Lapu-lapu Larch Larkin Laskie Latona Laura Laurel Laussat Lawton Leavenworth Ledyard Leese Leidesdorff Leo Lessing Levant Lexington Liberty Liebig Lilac Lillian Lily Linda Linden Lisbon Livingston Lloyd Lobos Lockwood Locust Loehr Lombard London Long Loomis Louisburg Louisiana Lowell Lower Lucerne Lucky Lucy Lundeen Lurline Lusk Lyell Lynch Lyon Lysette Mabini Macedonia Madera Madison Madrid Magnolia Mahan Main Manchester Manseau Mansell Mansfield Maple Marengo Marin Mariposa Market Mars Marshall Marsily Martinez Mary Mary Maryland Mason Massachusetts Massasoit Mateo Mauldin Mayflower Maynard Mcallister Mccann Mccoppin Mccormick Mcdonald Mcrae Mendell Merchant Mercury Merlin Merrill Merrimac Merritt Mersey Mesa Michigan Midway Miguel Miles Miley Mill Milton Milton Minerva Minna Minnesota Mint Mission Mission Mississippi Missouri Mistral Mizpah Moffitt Mojave Mono Montana Montcalm Montezuma Montgomery Monticello Moraga Moreland Morrell Morris Morse Morton Moscow Moss Moulton Moultrie Munich Murray Myrtle Naples Napoleon Natick Natoma Naylor Nebraska Nellie Neptune Nevada New Newburg Newell Newhall Newman Newton Ney Noe Nordhoff Norfolk Noriega North Norton Norwich Oak Oak Oakwood Octavia Ofarrell Old Olive Oliver Olmstead Ord Ordway Ortega Otis Owen Owens Oxford Pacheco Page Panama Paris Park Parsons Pasadena Patterson Patton Paulding Payson Peabody Pearl Pena Pennington Perry Pfeiffer Phelps Piedmont Pierce Pine Pioche Pixley Plaza Pleasant Plum Polk Pollock Pomona Pond Pontiac Pope Poplar Porter Portola Post Potomac Powell Prado Prague Prentiss Priest Princeton Progress Prosper Pueblo Putnam Quane Quincy Quint Quintara R Raleigh Ralston Ramsell Randall Randolph Rankin Rausch Rawles Rayburn Reddy Redondo Redwood Reed Regent Reservoir Rey Rhine Rhode Rice Rickard Rincon Ringold Rio Ripley Ritch Rivera Rivoli Rizal Roach Roanoke Robinson Rockland Rodgers Rodriguez Rolph Romain Rome Romolo Roscoe Rose Rosenkranz Rotteck Rousseau Ruger Russ Russell Ruth Rutland Rutledge Sacramento Sadowa Sagamore Sal Salmon Samoset San San Sanches Sanchez Sansome Santa Santiago Santos Sargent Saturn Saul Sawyer Schwerin Scotland Scott Sears Selby Sergeant Service Severn Seville Seward Seymour Shakespeare Shannon Sharon Sheridan Sherman Shields Ship Shipley Short Shotwell Shrader Sierra Silliman Sixth Somerset Sonoma South Sparrow Sparta Spear Spencer Spofford Spring Spruce Stanford Stanley Stanton Stanyan Stark States Steiner Sterling Steuart Steuben Stevenson Still Stillman Stockton Stone Stoneman Storrie Striped Sturgeon Summit Sumner Surrey Sussex Sutter Sweeny Sycamore Tacoma Talbert Tara Taraval Taylor Tehama Temple Tennessee Tevis Texas Theresa Thrift Tingley Todd Toland Tonquin Touchard Townsend Trainor Trenton Trinity Truby Truett Trumbull Tubbs Tulane Tulare Turk Ulloa Union University Upton Utah Valencia Vallejo Valley Valparaiso Van Vandewater Vara Varennes Vega Venus Vermont Verna Vernon Vesta Vicente Vicksburg Victoria Vienna Virgil Von Walbridge Wallen Waller Walnut Walter Waltham Wanda Ward Ware Washburn Washington Water Waterloo Waterville Wawona Wayland Webster Wedemeyer Weldon Welsh West West Wetmore Wheat White Whiting Whitney Whittier Wiese Wilder Willard Willard Willow Wills Wilmot Wilson Winfield Winthrop Wisconsin Wood Woodward Wool Woolsey Worden Worth Wright Yale Yorba York Young Yukon Zanowitz Zoe Aerial Agua Ahern Alana Allston Alta Amethyst Apparel Aquavista Arco Ardenwood Arroyo Avocet Avon Baltimore Banneker Bella Berkeley Berkshire Bernice Bridgeview Brotherhood Buckingham Cameo Cameron Campus Candlestick Capra Cargo Carnelian Casa Chicago Cityview Clipper Colleen Colonial Constanso Continuum Crescent Dalewood Darien Dawnview De Devonshire Don Dorcas Dorchester Edgehill El El Elmwood Emerald Escolta Evelyn Fairfield Fanning Fresnel Gabilan Garden Gaviota Gene Genebern Gladeview Granville Harney Ironwood Isola Jack Jean Juanita Kensington Kenwood Keystone Knollview Koret La Lapham Lenox Lincoln Lunado Mallorca Marview Medical Mercedes Merrie Midcrest Mirando Moncada Moneta Monument Museum Myra Nichols Ohlone Olympia Omar Ora Oriole Ortega Peter Pinehurst Pizarro Polaris Pretor Quartz Red Reposa Restani Retiro Rico Roemer Roosevelt Saint San San San San San San San San San Sandpiper Santa Scenic Selma Sequoia Skyview Starr Starview Summit Sunrise Sydney Thomas Thorne Toledo Topaz Treat Turquoise Verdun Waithman Watchman Whitecliff Whiting Wildwood Winding Winn Al`
const streetSuffuxes = `Alley Avenue Boulevard Circle Lane Parkway Plaza Road Square Street Terrace Trail Way`
  .split(' ').filter(Boolean)

const firstNamesProcess = trainMarkovProcess(4, firstNames)
const lastNamesProcess = trainMarkovProcess(3, lastNames)
const streetNamesProcess = trainMarkovProcess(5, streetNames)
const cityNamesProcess = trainMarkovProcess(3, cityNames)


const capitalize = s => s.charAt(0).toUpperCase() + s.slice(1)

Array.from({ length: 2000 }).forEach(() => {
  const firstName = firstNamesProcess.generate({
    minLen: 4,
    maxLen: 8,
  })
  const lastName = lastNamesProcess.generate({
    minLen: 4,
    maxLen: 10,
    firstOrder: false
  })
  const streetNumber = rand(1, 9999)
  const streetName = streetNamesProcess.generate({
    minLen: 6,
    maxLen: 10,
  })
  const streetSuffux = streetSuffuxes[rand(0, streetSuffuxes.length)]
  const cityName = cityNamesProcess.generate({
    minLen: 6,
    maxLen: 10,
  })
  console.log(`${capitalize(firstName)} ${capitalize(lastName)} of ${streetNumber} ${streetName} ${streetSuffux}, ${capitalize(cityName)}`)
})

module.exports = {
  ProbabilityMap,
  MarkovChain,
  MarkovProcess,
  trainMarkovProcess
}