Common Lisp and How It Conquered the Euler Problem 2

So yesterday I took down Euler problem 1. Yeah, I’m just that good. In fact, only something like 250k of the entire world population (7 billion or so) got it right. That’s not even including people like Santa Clause. Elite level, here I am.

I would tell you what the second question asks, but that would mean I read it correctly the first time around. What I read was something like “Add up all even Fibonacci numbers up to the four millionth Fibonacci number.” Cake! Right off the bat I was going to do this tail recursive style, ’cause that’s the way an elite programmer like me does it. Now, I know I’d seen the cannon version of how to get the Nth Fibonacci number, but I chose to blaze some trails. (And I forgot what the cannon version was) The idea was instead of doing that whole (n – 1) and (n – 2) nonsense.

So to start there is 0 and 1. Then 1 and 1. Then 1 and 2. Then 2 and 3. Every iteration has a sort of shift where the right parameter becomes the left, and the new right was the old left + right. Sounds like a really easy recursion problem. Only thing missing is an iteration used to find the Nth Fibonacci. That will just be reduced by one every iteration until it hits 0.  Once that happens, the last number is returned.

  (defun fib (left right iteration) 
    (if (= 0 iteration) 
      left 
      (fib right (+ right left) (- iteration 1))))

And it would be called by:

  (fib 1 0 37)

Which, by the way, is 24157817.

So now I have a way to get the Nth, it’s time to add up all evens up to the 4 millionth Fibonacci number. Oh yeah.

 ;;This is needed to add the current Fibonacci number to the sum if it's even
  (defun adjust-sum(sum currentNumber)
    (if (evenp currentNumber) (+ sum currentNumber) sum))

 ;;And this is an update that keeps adding up the even Fibonacci numbers and stuff.
 (defun fibo (left right iteration sum)
   (if (= 0  iteration)
     sum
     (fibo right (+ right left)  (- iteration 1) (adjust-sum sum left))))

Now the site gave me the first 10 numbers: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. So adding up the even numbers in that list gets… eh… Oh! 44. Well time to see if the above bit of lisp works.

(fibo 0 1 10 0) ;;44

Yay. Well that’s easy. Next 4 million.

(fibo 0 1 10 4000000)





15 minutes later


Now the fun part about that solution is that I will never get a stack overflow. Bad part is that I have no idea how long it would take to add up 0 -> 4 millionth Fibonacci number. So at that point I was thinking I would have to somehow create a tree structure of parallel operations. Start with 4000000 / 2 and find the total in those two. To do that, I would halve those, and then halve again… ect, and sum up everything while traveling back up the tree. Or is it down? Whatever. I couldn’t believe how *(@#ing hard this second problem was. That was when I re-read the problem. Turns out I was supposed to add up every even up to 4 million. So the Fibonacci number closest to 4 million. Not the 4 millionth Fibonacci number. Then it seemed to be back to what I would expect for the second problem.

  (defun fibos (left right sum)
    (let ((adjustment (adjust-sum sum left)))
      (if (< right 4000000)
        (fibos right (+ right left) adjustment)
        adjustment)))

Basically every number found that is even, add it to the sum. That is until the right number is greater than 4 million. (Which would make the left number too high on the next iteration) At that point, add the left (If even), and return the sum. And guess what? It worked.

Now this wouldn’t be a lisp post if I didn’t add in some macro for over kill. After I failed to add up all even numbers up to the 4 millionth Fibonacci, I thought that maybe if I put them all in a list, and then added them up: magic would happen. Magic did happen, I killed the heap. I mean if adding two really big numbers was killing lisp, having a bunch of lists full of large numbers being added together should be fine, right? Make perfect sense. HOWEVER, one interesting thing did come from that: A macro. Here’s the original function for the array adding, pre massive tree idea. This just puts all into a list. I didn’t even get to the adding part.

  (defun fibl (left right iteration numbers)
    (if (= 0  iteration)
      numbers
      (fibl right (+ right left)  (- iteration 1) (if (evenp left) (append numbers (list left)) numbers))))

Well I figured instead of just having a method call fibl to add all the numbers, just make a macro that would call fibl to get the list, then run an eval to add them all together. Why settle for simple, when a macro can make it way more complex. Although in my defense, when using macroexpand-1, I get to see the whole list of numbers before they are added.

  (defmacro fibl-bibl (a b c)
    `(eval (+ ,@(fibl a b c '()))))

With expansion:

  (macroexpand-1 '(fibl-bibl 1 2 100))

I got:

(EVAL
 (+ 2 8 34 144 610 2584 10946 46368 196418 832040 3524578 14930352 63245986
    267914296 1134903170 4807526976 20365011074 86267571272 365435296162
    1548008755920 6557470319842 27777890035288 117669030460994 498454011879264
    2111485077978050 8944394323791464 37889062373143906 160500643816367088
    679891637638612258 2880067194370816120 12200160415121876738
    51680708854858323072 218922995834555169026))

A list of Fibblenibble numbers. That was a lot for just one problem. Oh and for fun, here is the original golden function when adding all evens up to the 100000th number.

210134635149757719315950255064695756588695785131611725165235804359916786572863811331696923863350683048126683085142916459332058114941110766686678707363430726110258898018010828814604839776532825126899915724751316525031035954444949232180979996323811805415925251187493235192974551234331062086534136805786177582386212877375117620623437303742552667696171935177393500985079313725745197179088900620541323223091163646241337468114147700211796183133392908337016188476611677040521713333083986943297965232600862288054724778303558352715084544785730244200683974569728324692232314945603947032229789125399896443936969649280509005067194130014191019906960046358175606148496241991973176681118479994029681227415747795999136572033230343019483738392331535711939926003061047418009792141434744705747844399720376659431081235302156392379430858982251915271749438857727345183251386080769599191998495894067199070972184404625055740909899201130583052303659016146177688301879324924998727010234689589652398161124306953007370681861516962672162830424285078239244552669896314483208891095985314333206792218890143817628106119467673305141311764463161724418159970207964328041486429941060257374678419608037203240907685335494485955430304182439776700248640864773279209804130107815203595074666252436894851980635269999972922994229316228817842523295140034108168011150940569150560436362656065740205309181537316695861739407779209971100218486739728373214686579514950816073845513802397657286856676531046668500663748143833301204618907223112395593062138681442360586312693005182921398053824358166567360026424432237244893361109213993070525649845617875919021011326149817574499600796480668479299614246073642029837591242910304168518758793534817372587124224044754480947765539973773666516619403727561494805255585195903740965473156483826329176162700309900774052207962720926430456721705920419295629157748986005586754127144175997102510354485314565966185296805934985438370260768324842285912332030181915108852664242572126624872731549974878879155226050609755790730339295164790392508584467954066309414696582480695424863249711810312524443221741471814759761642591927546176444474249387569051116004412758001682082295704641159441424272689037737589652445380001275607073531853320125093627397613857071252531071586306675618824599663218410951341233889913902500614833884066908233398699567328935275637267197347202298538859593997703697713802957906539642606370828416414147810799658734529479109231110665556187176418548476384868832963210485071523013131404475587489246037723764622677791224251854058483148068071872834278461455417690222393581989010116042011804685461127070238504845641024580288388683486518326824941746182412364178381937706647179795904877648631685848537286241780452140116126363436113503233969227750339200404403271385824016244124590198080724853578464251549859567798872700339233328199123293182072219835862411700901312198089085324168018585880297699588552274806528231438637456543897771694662159568469764070690619750679540394911382924413162540130926242538137809271974228796966756307877297146883981035775477003257465643278222185432771988583677109052727922684880948307777590208566505337135736871655930805583340006737117885774782210441102763126560381512377013745064883258066541654232929359000450636792943019366164523868429521535469074034946258620181476030719978796857587893526752267013243359357704275788464983521293250604674874972904203574191004579440328676946195685201217530982857554917402649304912755548774644266805777262869652122134839557928817095037660048000300983583156138998227663706230691350142110382572156360795370566704001744520381292459642329429020643458193257739821488816256213262167854518663999704530401445716210010813920156878484439665966358964075682592874240824755027657575343644672852034918243245446316952102752735068725543566246724899970431874885063985801405302823267128880668375592237892911980938256404473624342563948754159675405491888599705183505124206483194289438402679806151662578956199048579482571884905313726646964715915902481919126863415141459926644007647035716861604316055203082217917719133243245860921910514675871227687275287904537667794101260280122689215877177692659971254050108571563988273142096434551936972388013889468525869265313987202386124454335737401442779149708893730357123453230525472812601106412916497512782130114995296452342079789558396075642943016414842497563577672325443914816380590195336781663311206154684378687331712606758533984749064480897205038658440932747251187171925615932041948405830247876193685033702230130932424171267174008628519670296361919459610294515999453092599210519154108208264305103436934737238114113533578104044878364038805466064185038826829618126068508780524600524532396321751115668117851883641022819256371424253155374856570004090384898320933546043135375879145452469151210230166702462732829179222147648168544388272632793803303122346891630514391171335250309356292095466008088199378325674346357700504254182363476775695790837935514439560228061226354773830823231721171817925342307215071868982885889541475143724812654735837013547431202790870732505233531398825890187747794954413346873325089496704707900879389656488821344562140479083399346311640681278838002510254530994419956170461984422108213527538906614386259246674521029974783963230282955512888041250709653893598294048112482622910077840761873334973198377454635795213978371736970235694420172850166988573277784747359753551788762540593326628753294639877707665080404530665383601082885770093671822607628346295993226276841728411776535299081065042752452287473106250279305015609577612263706122258615273003824478437201890581856024447124072122869194061082349696061506541146882810975740599373902964150305958292734863572211538327420362893741030060918112493319686075487376326876983867697925992238478866107122304899040508647431253037732782392528717428733688046182831729132774784725040247331280034150165198489598636448927438644934585011667241905557181221099862417418669690895727041918337056896533627181530365929210694465523664873064732165456703307561043626687310115887431899952005701851752064305634513236819669863690896215787275155359301452323258424483249574247791813760513919904799453367672688587351772118267772287356372396160702030198472586422560132252593869683043910370213989746468578566913116289689458398973054296570754784174314808120093787794706506020368933585621886459424376006095645540516337457704802032437712446376726098103705121264595688347218451606605177546669112269977919387895237275587948254401392746864976823592328331881845950067569933987319425473420264227457037823974302822896032471480891487098097305485181465226545673335811922107441009472479075151488317678985169434996018295266202368656027482782167093131138853719482321158978983728897817066141539245801340677422731168147452795744266894019921848745903566804479001006155549580727806394856431476422910453397609716348844849887606352116821462340936742691737144466549028005167896114433828324010330732622222173088700586063219910281155121562420408416384427387652289708818083295152927629068305962450984958140124822704302666063753142031169908652700969937967560785599365331808920514154488957336620911995116533849705595812479209241064508087094244537228712955164255338447272814693237786944972817747162992695126655916021555696910288300621111158764772032998163892743242649237104158980565714542878020285536410647945320115296595370947305512788680378113862524317461361104377898340233653765440250113911194734180701435331951303967217221734314727819805156190906849061439718539268419425329956751349030666546704748089678154731359992660080659657693255422636089340707029328611600500872957698125089435060190254908205989007442684601204354306128681811653225112598061698749618332036772594552243139973109440779102119329001540055344504861934352772627605541498252958062267170758050417721581345853192205827455124849694038122424540952113490208003720269622508701810492374185547454640205838677373971255884836178808659477383029849240657152245346957236828601255626545670117515828979636355357010237289609065632163399008313810676989365934339225832320452186973067052917093306509725760336403569400860087523267258884178358312322554843735839611544507427486582585771335956735088950482325185692785684530748994744497094422864864143797723195179954757435410302928616925707931383712057489757701207799996919323616506079812268859145047501530863469235679989559672702217770826479903005058658549708092818077513289356168467776629816164319215465270457262582602493827064947268566585714868977533411971593664133914653747763343228160437188427004775818365599277926000143684854386339411112041507140914711404454127284070064271895340157513116501567771785420553078419525971929246516298920300129180663727392570824792779311312612668016083738349081021091366969260329686954844262639357270307133632913108878682752416413368429863460872892282596218097575256714738390692771125065632039823487232487934816134008137046656159997657704350599552440619655586356167648218951021071029187849742480638340944718834853662025553240185857312911444283841660542935130176492325518542248626959742553708412118992866903849589661592444892326674773575698043679715574196616158748568450383757530991595937631481647034939033650291447159318070426821677259125681086668323496716293016795080464641752217809778007597626795191933481646571059765954320801474588409330216905430892844682932638129957978823154452874202850621093728059168457837220013599499692971762130344115615325995269667250785121954660127785415291473924408415171614813511358905517066018649343142785307691809627637425698725735864130408323368656111884389482769754811960576769415909056295045296535188276050861691547829255173581117186073547261975619158894909018402883026854086197997246977225550369748004330315700368486340493017657401401781958962964775701777837545067311278282560025002019448234788264341968794716332067981937949097609548861654631809646464344213575300476910860746689637212371057494876111459257852148911385967048755465998441364146400022319073769030669486255997867547995222556113671998576983652014900141037588411791395604752605136783160867609748118109236373232248011307499087595417610165317101079602536029939751761961409793458257927122496473727405330252505881260348617548185100987630099263033869211094826230264992746499766937765664767047006915745373423356974983886028631806018605368717143402885871329102564704048497978176595564136999504898026980399221876155825386735988890478521694182263511982214715473315781195200662586608289146076691505127900696857629942816467387762785961640417229457596102193240304059314877424478667842289912208938780134312689210803665796315755850327333239648241364437120059014779223556434771264888962692080320296371365675443041834819783967762151313094344287600324088024886298056503696129538223922486941503288613783288870731822184804697687684051260150598523227085670596698786755189436919638468778275342260526833915914197270020098776736064622519166800190869283946064085690137489511277163716308622192219175958296397500085684126837927336173451686684923202975662385803826521428261798994900934113002497407521439855373833822964723019320494102332671987095211054238025332581283303947523503685018243913424390547185206189041043360160551399181866804529327190930148746439057774213307320757229157969585047879576209642937323116289964490410633199594898960154825688501502166627998287854790244025814015914565894614176980590304824038029416219941692596393563315421871832759822557040046812392613152131516662651071131811697677932327278397600019337002820692075165825022159844139593104475602024359541715915936040280694024136104975224838491512973122332169367004377967404039156085742436134266885110263040401912806482685606546407143416336601227367095920477163288537592301398535052907715237130177064760726499531799400005658598752165833477119918705900029310637497082895816444819618200059170161703470214369422592382641320506101680281216156081778448799318487482379825143559429289217755084375231231826966227624507701607028493277365212297731816558232776081859195320720765487935640845306071293298175978648896121109699931766693640815838766469144414269416881611661901832254474993736903002870444918037696406186096461094396767891407003453281738910144375394090662039131219749613014416244957286368701539109549586816734329366236746259041128698402728540623058249769198276372684574367047631508878368246825155252000604186666175384857635626157366171685799119057749145104626216349054268607435891936118142348404291584681919224938269484894447299275783313866238268605651170354567618500066640828464663845039073553932154895328922389658948027157160251222979894704360571691297862952533805704188878883347493951724921180841678272882101995530922680946787505085500886281017788478168947687933289789265967458335625338880010055835991224103398106910681873999803919447373848842718558974101069467493059087041449542369885578310978786508338476580819501430821887216699397523296232481211068079127848989527274911018295957930245601035781781552015776949331402066548318836070545702259101601202858355941021723239696437490190967646907252717163788218362609765047387412812296570896130256850884470118212380074491599062494090782968188381275032884690293738157030772407788960626763826311786521684459634262702726313120595550807817889783348003295426613850135163759356093858562640172806341511755083377256237743856688685833977571021335173367552139558669231461890051388052084168584309212686328101875686642176681678258161007255939143491156297571055310068227096515002086176644475958915947792826544980920701818638312130673149091618335925811380646453223742132133536011417584230713296025838111560391541436824783737657386591404783962547872759160432036001703664023848862521453258338793133106897041110831983625006829845247141544780274547562798449396105088732940897438717261579517926301609165483354955629169674272424362392449499327755308169464334499835011272786260059623448169962267096528431414363307727748879558583861743513655499714227653314531461547230325298066242977520913896933633425978231755203930891989970693601676641392159782285450394650447351396177405259220091086399878803399037284230150075406946172625105252246743707323586128249768358241061843301856995209716718881119943331925960878386314159192691633628371990365999473324033224660166283362406508472119313013046929763109273691491482783208361952804867618709155359763254784189783537132337034192486723758484296789460982120806248955719901979533349518748800253928816551805010361299912777533130155627166184669776817910914491556108545726579739015553397637872032024840343939020724989466155622700211781395397524802676616039939897330181240843168074214891914751916504821544411228786746871441634365565516782266448300241467948069931858061626078054431628234960332693691868914691195100883613120189661632186182481828827508722120099555633056092701975580830614548967717547124834107408844338075996676965118798713414760398527484510079855409467866187873865171641234435736694892493290285643393962280230933866378605205069640229730086747322559948835347701346316298854270595950784552299777610367564656909358070274954245477742270971746595867221526118823469613170169632325502587230182228537723192376736698335277895419921587983445396504232871929928095633156235885197769500331225291266518088953227966713707787164877369121792584377914564446736202678535672272911148596686537910294857223644454489067037707405536559306146842998665525356136573125169693694886923967734414247683916610832803230551830328329656615597750684742556921964560578078724927390800180947770481117230846398997474232831807416534958691477507232803171451867978795773477926362693036590124982640838421272171294486953694217648730529551119670790362378479165040057727884581718811537409504375754180213357329518840339658857659225472227753910940218573950862702436879531170719059054588899794722642555547715622550383094211836998109622803898475556138968220399520755975722033077348250428810898854659545479156649389371726108262751722270235138158485718438123481002162926100167821842434644145808964390957121673782737814361306217583217184598124487848407570736394438276748884900324043557738088347297955596146371472719244124866695710978580801114611245318214829898604977359790001251837337744732514003227801568532210870981711391593902347140202374989962533922017246308539050932634459280027964473921781011525328104539916639202720496687716273313449817119092654390857956906620484412000245041169243761472435023051769094170910850758938973425167314947084154044967895410170129849078550957606216129957114899698050874439894391514059609561936396117681164751704852351319228847525908033832852224331049094563435794419534196340813328302275203470566275886315079650273405931265702058827312707374247710482760916463127541794836090581772091569435534252008530734238443706779462426747561809295073772989948906690839206749462851068679596295946925255856047917667723409795120929223023568942635473417139817402379357828670784544822226269789762591879865710801484081920604407651804998349809431989752090348608514876630638518621108872119987893037612213788399531244956067024823744464295926421141662355934743056022382942013556145563955739612625216357651684218328907508641093930276516014993979403960868963166273417646322104257657318991066104656039851755604731303550365138945603628337154214247460120272519587532156053928853272059360997202235662983082664787151377470547835077166304969488757406500477091420132564946761388009999150205307085916054009789475189522966304063839406949736916211375628242467064326553552643434482432201764730991631960975879963107928392665409042731125871602886202088963271887832908611559265610937788384690085152310913834573388112507237937730757225715912796153347153130186632328418177766308016585771876766217468711212548383498610478459146019961088987462203396327400295530783739475027149900881772201888789353158601700677782184152573400851186942994078175811891797233717783138006757483715072021020758596443618732393369139098591351799194301830809367863135024667117464305862025311413756063774077713211423576086774857290123690738822518048520949175918815981438611077457489344566987152913956325533160483220764219027004363784496316622361504723876457646422206742143391453606184716462121044180218197530275337938606215705136430264193780692405120326312862385649988784732175002811670077610443264135934777412150018828223954244695050026842052876118164018541944874833774670555994814420671882408288137775812469290989993809529670529829438647687529606774014120319239986257497301032425187103725121654968658239135595585158593925124607814088125454604787206451352483254459291222047592454341812243065137310481737689661315940835763055390630366405531005767248882907865249389338691377250865829483136636108551155102223445510020797415176337695410000496618501795801013486367948364379840004621567554498797988586983536885277281766989388141535482632178393529591983320058577012810211414053003397205458982697084268250263636216226849867255775808792107079985095487774153671231747128545554886268144818502591552230433514295245774489272593082024298356091609395630161222343283728600145481504536639820969054368415028850424427493816321210061288780567589605603485304929240318765007165160314895042800565872673010844927496776724062145035309838535179167338585946480482502304095322690687232463519446532509780903023128865047531103223461741746558159843591973034411569970280749644844477684427221300798945879744261065241666018944132807794398191204384532714659652333888454053602445432009656690476219493586861862650276087376220797396105688332640294421919802707378374349366858367758305227152144956599671541049582507982382810422816218154089085630110850817388778205572090179609654423564462789769682143891222682702408297516161189408903014295279135004336934244187516885749045858222234653015419511298118997313635664488446496836226827661674123289710636701353528269425596810788132814943234221768541178592404212356919876288915506439277672285401338295086910304093675952549924981548295539671618340692698510141069747470306724497622695441545177289389783198167673153308821130110105288781096189097874731485821840767460542853635315821366422678874925699731857970947686041338357356660254628504966783647630558181400040291220487730085425878820572203969786010762422205821077797891437437271211300592243295335783205540143414525910530643020222737525571946127221957193409744066896412724685850198276695031732241655051863572337617886213017558284975788698382145678631876793675083523530665626372542375260667989689193097509441096459016277376089258829001608871316651176241624092467422390421989410935677121376456674284503881285948347811403148308417350334010647129893085265060932398947369906762515000254008951352275939889675264734960540139416482458019250609247002478434809985351376227426552083399686034233737113135721952938073954444792091208018687445435005640893031581207597214528639333548781765175930179702379384879976002408492565223093051749059256

Project Euler: Question One… And A Pointless Macro

So for the something of it I am going to see how far I can get in the Euler Project Problems (Not sure if I should have capitalized “problems”). Basically finding solutions to questions no one has ever asked. If nothing else, this is a way to further my Lisp knowledge… so yes, this is in Lisp. Hide the children.

First problem is simply to add up all the numbers that are multiples of 3 and 5. It’s like a more boring version of FizzBuzz. Apparently that is possible.

So it’s not exactly a difficult problem. Essentially I just went with tail recursion. Don’t know what that is? Well it’s magic. This is typical recursion:

 def someMethod(current, end)
    if current == end
      return end
    else
      return current + someMethod(current+1, end)

Basically the method calls will look like this:

(0 + (1 + (2 + (3 + (4..... end)...)

Because the preceding method depends on the current’s answer, that method call has to sit in memory. If end = 10000000… Stack overflow. Oh yeah.

Now some languages have something called “tail call optimization” which basically means all useful information is passed into the next method. IE the preceding method isn’t waiting for a return, because it supplied the next method with everything.

def someMethod(current, end, final)
  if current == end
    return final
  else
    return someMethod(current+1, end, final + current)

The big difference here is that every iteration sends all information forward… as in there is no return “x + someMethod(…)” call that leaves the previous iteration on the hook for the current function’s return. Yay. Why does that matter? ‘cuz. Fine. Some languages are smart enough to forget about the previous call, because it no longer has a use. Kind of like garbage collection.

So to attack the original problem at hand, I used a simple tail recursion strategy. Every iteration with push the next number to check, and the updated total to the next.

def euler-one(currentNumber, total)
  if currentNumber == 1000
    //At the end, so just return the final tally
    return total
  else
    if(currentNumber % 3 == 0 || currentNumber % 5 == 0) 
       //The currentNumber is divisible by 3 or 5 // so add it to the total, and increase the currentNumber
       return euler-one(currentNumber + 1, total + currentNumber)
    else
       //The currentNumber is not divisible by 3 or 5 // so just increase the currentNumber, and leave the total alone
       return euler-one(currentNumber + 1, total)

Or in a real language:

(defun euler-one (currentNumber total)
  (if (= currentNumber 1000)
    total
    (euler-one (+ currentNumber 1)
      (if (or (= 0 (mod currentNumber 3)) (= 0 (mod currentNumber 5)))
        (+ total currentNumber)
        total))))

Of course this wouldn’t be a post by me if I didn’t over complicate it… MACRO TIME!

You might have read my macros primer thing (Most likely not), so this shouldn’t be to hard to understand… right??

What I was shooting for is a macro that would not only do the above, but would allow for as many numbers to check as the divisorable thing… So instead of:

(euler-one 1 0)

Where “1” is the starting number, and “0” is the starting amount. Instead I want to do this:

(euler-go 3 5 7)

Where “3”, “5”, and “7” are the numbers to check if the current number is divisible by. Pretty sure that made sense… Ok, so!

(defmacro euler-go (&rest args)
  `(progn
     (defun euler-one-a (currentNumber total)
       (if (= currentNumber 1000)
         total
         (euler-one-a (+ currentNumber 1)
            (if (or ,@(mapcar (lambda (x) `(= 0 (mod currentNumber ,x))) args))
              (+ total currentNumber)
              total))))
     (eval (euler-one-a 1 0))))

And here’s what it looks like expanded.

(PROGN
 (DEFUN EULER-ONE-A (CURRENTNUMBER TOTAL)
   (IF (= CURRENTNUMBER 1000)
     TOTAL
     (EULER-ONE-A (+ CURRENTNUMBER 1)
       (IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5)))
         (+ TOTAL CURRENTNUMBER)
         TOTAL))))
 (EVAL (EULER-ONE-A 1 0)))

Looks pretty much the same right? ‘Cept for the PROGN thing. PROGN basically just runs everything in order, and returns the result of the last section. So this macro actually creates the euler-one-a method, and then calls it with the “(EVAL (EULER-ONE-A 1 0))”. The important part is the section that creates the divisor check:

(IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5)))

Which looks an awful lot like:

(if (or (= 0 (mod currentNumber 3)) (= 0 (mod currentNumber 5)))

From the original method. HOWEVER, the one thing the macro can do is make as many or checks as I want. Say I want to use 3,5,7,9:

(euler-go 3 5 7 9)

The expansion is:

(PROGN
 (DEFUN EULER-ONE-A (CURRENTNUMBER TOTAL)
   (IF (= CURRENTNUMBER 1000)
       TOTAL
       (EULER-ONE-A (+ CURRENTNUMBER 1)
        (IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5))
                (= 0 (MOD CURRENTNUMBER 7)) (= 0 (MOD CURRENTNUMBER 9)))
            (+ TOTAL CURRENTNUMBER)
            TOTAL))))
 (EVAL (EULER-ONE-A 1 0)))

And the macro creates all four. How is that possible? One line in the macro:

(if (or ,@(mapcar (lambda (x) `(= 0 (mod currentNumber ,x))) args))

Remember, with macros there’s a step where you can create more code BEFORE the final expansion. What that line says is to take all the values in args (3,5,7,9), and create a “(= 0 (MOD CURRENTNUMBER X)” where X is 3,5,7,9. For people more familiar with c#, pretend you are creating a string.

"(if (or (" + args.Select(x => "(= 0 (mod currentNumber " + x + ")) ".Aggregate(new StringBuilder(), (builder, current) => builder.append(current)).ToString() + ")";

Or something like that. The difference is lisp is creating actual code, not strings. Anyways, that’s it. Yeah. This is awkward.

Common Lisp: Intro to Macros… Because I Only Know Enough for an Intro

SPECIAL NOTE:
I am extremely new to Common Lisp, and macros. I’m willing to bet that anything shown here can be improved.

Been reading through Paul Graham’s On Lisp which is probably not a real “Intro to Lisp”, but well within the grasp of my super interlect. Well at least it was today when I had a breakthrough on macros. I had some introductory stuff on macros when I was perusing through various ancient texts of the language of Clojure. However, I never really looked into to macros much since I was trying to figure out things like how to set up a web server in Clojure. For whatever reason, call it divine intervention or maybe vision inducing exhaustion, it dawned on me to read On Lisp. I figured that if I were to learn macros, I might as well learn them from a person who I can only guess is Lisp: Paul Graham. Turns out, this was a good choice.

Now to start, understanding what a macro is, I have to introduce the word “homoiconic”. It’s a really fancy word that means that a Lisp code is compromised of data structures. In simple terms: Lisp is built on lists. For example:

(+ 1 2 3)

Is that code or a list? Yes. Why is this important? Because any code can be from combining lists together, or by taking a smaller list and expanding it out into code. Unlike other languages that might use a method to evaluate a string representation of code, or some kind of preprocessor directive, you are creating real code that needs nothing special to read/evaluate it. A kind of useless example of this is taking a method, and making it into a macro:

  (defun average (x y)
    (/ (+ x y) 2))

And the macro:

  (defmacro average-macro (&rest args)
    `(/ (+ ,@args) ,(length args)))

Completely obvious, am I right? Nothing seems odd or foreign… HRAHARAHRAHAR

Ok sooo… The main thing about macros is what is supposed to be evaluated at the time the macro is expanded, and what to ignore. Essentially when the macro is expanded, you can have method calls to create code to add to the final expanded code, or code that will remain untouched to become a part of the final product. It’s kind of an odd thing to understand. After all, it means you have to think in more than just one dimension. Think of it like you are concatenating a string. In something like c# you might have a string built like this:

string function ReturnFinalString(name) {
  return CreateFormalGreeting(name) + ".  It is nice to meet you on this fine " + RetrieveTheDayName(DateTime.Now);
}

Ignore that I am using the + string concatenation junk instead of string.format, or StringBuilder. Just wanted something easy to read.

As you can see, there are parts of the string that don’t need any changing, because they are in a final state. (Meaning that’s exactly how they will appear in the final string) However, there are other parts that need the result of an evaluated method. Once those method returns are resolved, you get a single string. A macro isn’t too much different in concept. Instead of creating a list of characters, you are creating lists of code.

Ok so now it’s time to break that macro down. Remember, macros are about what to evaluate, and what to ignore.

  (defmacro average-macro (&rest args)

First two parts should be easy to understand, but the third one is misleading somewhat. What looks like two parameters is really just one: args. The &rest is just syntax for “What ever arguments are left.” For instance, say this macro was more generic where it would take in a function (add, subtract, whatever), and also some numbers. The syntax would be:

  (defmacro do-something (methodToUse &rest args)

The call would be like:

  (do-something add 1 2 3 4)

“add” would be the “methodToUse”, and 1 2 3 4 would be “args”. An important point is that anything passed the named parameters gets lumped into a list. So if I was completely stupid (I’m only partially), and didn’t know what I was supposed to sent into “do-something”, I might do this:

  (do-something add 1 "a" someVariable derp)

The “args” would be (1 “a” someVariable derp). Most likely the macro would throw an error if you tried to use it in the REPL, but the point is just to realize how “&rest args” works.

That was the easy part. Now for the weird part.

`(/ (+ ,@args) ,(length args)))

Looks like a dragged my face across the keyboard, or PERL. Either way, the syntax is pretty goofy looking at first… And even after that. However, the idea behind it isn’t that bad.

Remember how I said something about it all being about what to evaluate, and what to ignore? Well right off the bat, the macro is told to ignore everything. Why? The back quote.

`(... stuff here...)

Without any special characters, the macro will just ignore everything within the parenthesis. So if I did this:

  (defmacro add-this ()
    `(+ 1 2))

Everything in there will not change when the macro is expanded. So basically that’s a really stupid macro. What’s the best thing to do with a useless macro? Make it more complex.

  (defmacro add-this ()
    `(+ ,(+ 1 2) 2)) 

New syntax, the comma. The comma is the opposite of the back quote. It basically says not to ignore what’s there, and to evaluate it. Before the final product, the (+ 1 2) will be evaluated, and that result will end up in the final expansion. Without that comma, the final product would be:

(+ (+ 1 2) 2)

But it really is:

(+ 3 2)

The difference is subtle, but it’s everything. What this means is that in the version with the comma, the (+ 1 2) is being evaluated, and its result (3) is then applied to the macro expansion. Given this example, it’s hard to understand what use that could be, but it will be completely obvious when the last part of the original macro is explained.

`(/ (+ ,@args) ...

So the comma is used to make sure that parts are evaluated for the final expansion, but what is @? @ is an interesting concept that also has large implications, despite the textbook explanation being underwhelming. The , followed by the @ means that it will strip the outermost parenthesis off. Yeah, boring BUT critical. I had explained that &rest args dumps all remaining arguments into a list, right? Well what if you needed to use the values in “args”, but not as a list.

What if I created a simple macro like:

  (defmacro add-that(&rest args)
    `(+ ,args))

And the call would be:

  (add-that 1 2 3)

Now + can’t be used with list, because it expects single values like:

  (+ 1 2 3)

Now in this macro, I did this:

  (defmacro add-that(&rest args)
    `(+ ,args))

Which says to ignore the +, and evaluate “args”. Well we know that the macro call stuff 1 2 3 into one list. So as is, if this is expanded, it will look like this:

  (+ '(1 2 3))

Bad. How can that be fixed? The @ sign.

  (defmacro add-that(&rest args)
    `(+ ,@args))

This will expand to:

  (+ 1 2 3)

As you can see, the ‘(1 2 3) “args” was evaluated to just “1 2 3” before the final product.

With that all in mind, time to go back to the original semi-useless macro:

  (defmacro average-macro (&rest args)
    `(/ (+ ,@args) ,(length args)))

Read out loud it says:

1) ignore the /
2) ignore the (+
3) remove the parenthesis from args
4) ignore the )
5) get the length of args
6) ignore the )

The interesting part to note is step 5. This shows the power of macros, even in a lame example. To make sure the average of x number of er numbers, there has to be a total count of numbers to divide by. When looking at the original function that this macro was based on:

  (defun average (x y)
    (/ (+ x y) 2))

If you want to find the average of 3 numbers, you hosed. BUT since the macro is able to take the length of the args list, and then apply that value to the final expansion; You can easily find the average of however many numbers you want. Remember, the “,(length args)” part is able to resolve that count BEFORE the final expansion is evaluated. This can be shown using macroexpand-1:

  ;; When the macro is expanded
  (macroexpand-1 '(average-macro 1 2 3 4 5))
  ;; Becomes:
  (/ (+ 1 2 3 4 5) 5)

As you can see, the final product has 5 in place of ,(length args). Magic.

  ;; When the macro is expanded
  (macroexpand-1 '(average-macro 1 2 3 4 5))
  ;; Becomes:
  (/ (+ 1 2 3 4 5) 5)

This macro is kind of pointless, because it could be done with a better function than the original one. However, the concepts are what matter.
Now for something more interesting. What if you don’t like the way that functions are declared? I kind of do. I started with Racket (Scheme) before I ended up at Common Lisp. In Racket, there is a uniform definition.

(define (name argument) ...)

But with Common Lisp, the “name” is outside the argument list. Well with macros that can change. And rather easily:

;;(DEFUN X () (+ 1 X))
(defmacro define (head &rest body)
  `(defun ,(car head) ,(cdr head) ,@body))

And it would be called like this:

(define (test-it x y) (+ x y))

Which is syntactically different than the Common Lisp way:

(defun test-it (x y) (+ x y))

How did I do that? There is a little trickery involved, but nothing hackish. Just opinionated. (Or Convention over Configuration as some might call it) Time to break it down.

(defmacro define (head &rest body)

Here’s the start of the trickery. I know that anything that is in “body” is what’s left over after “head” is set. Right off the bat, that could be an issue. After all, “test-it” not only needs the function name, but has two parameters in “x” and “y”. Doesn’t take long to realize that “x” and “y” will somehow have to be accounted for. This means they will end up in “head”, or “body”. In this case, “head”.

`(defun ,(car head) ,(cdr head)....))

And that’s what I mean about opinionated. I expect that “head” is actually a list. A list that starts with the function name, and then has all the parameters. That’s where car and cdr come in. (car means grab the first item in the list, and cdr means grab all BUT the first item in the list) My macro expects that the first item in the “head” list is the function name: “test-it”. It then expects anything else in “head” is a parameter. When the part above is evaluated, it will ignore “defun”, get the first item “test-it”, and the get the list of remaining items. Since cdr returns a list, the function definition doesn’t need anything special done to the parameters.

`(defun ,(car head) ,(cdr head) === (defun test-it (x y )...

After that, the rest is easy.

,@body === (+ x y)

Ok, how about something even more interesting. Say you wanted to completely change the syntax for lambda expressions. This is the normal way:

(mapcar (lambda (x) (+ 1 x))...)

I say, “To hell with that.” I also say, “I want something like this:”

(-> x y z (+ x y z))

Not only did I remove the “lambda” keyword, I removed the parentheses around the parameters. HOW CAN THIS BE?!?! More trickery.

(defmacro -> (&rest arguments)
  (let ((reversed (reverse arguments)))
    (let ((last (car reversed))
          (undone (reverse (cdr reversed))))
    `(lambda ,undone ,last))))

And that’s it. Good night.

Oh, you want an explanation, so be it. The idea behind this is that I will expect the call to have this: n1 n2 n3 … nx (method call). This means that when all items smashed into “arguments”, everything but the last item in the list is a parameter. So no matter how long the “arguments” list is, the most important thing to remember is that ONLY the last item is the body of the function. I think I just wrote the same thing twice, but whatever. Now to break it down.

(defmacro -> (&rest arguments)

Just the typical start to a macro.

(let ((reversed (reverse arguments)))

Here’s something a bit new. As the other macros I showed didn’t need any fields, I didn’t use let. This time the “arguments” field is taken, and then reversed. Why? So that I can do this:

  (let ((last (car reversed))
    (undone (reverse (cdr reversed))))

I took “reversed” from the original let statement, and then retrieved two things from it: The head (Which is actually the last item of the original “arguments” list, but now it the first in the reversed list), and all the rest re-reversed.

arguments == ‘(x y z (+ x y z))
reversed == ‘((+x y z) z y x)
last == ‘(x y z)
undone == (x y z)

The reason why “undone” has to be reversed it that when the “arguments” list was reversed, the “x y z” ended up as “z y x”. If I hadn’t reversed it, the parameters in the method would be reversed. This would be a large issue.

(z y x (+ x y z))  ;;BAD
(x y z (+ x y z))  ;;GOOD

Last part:

  `(lambda ,undone ,last))))

Oh yea, there was an actual part to be expanded in the macro. Why wasn’t ,@ used? Remember that the lambda syntax is:

(lambda (x y z) (+ x y z))

Meaning that the parenthesis that surround “undone” and “last” are OK to keep.

Done yet? Too bad, because here’s one more. The last macro has room to improve from a structure stand point (as I am new to Lisp), but also on a conceptual level. The next big thing would be to not have to bother with declaring the method parameters for the lambda clause. I want to turn something like this:

(mapcar #'(lambda (x y z) (+ x y z))

Into:

(?> (+ z y z) '(1) '(2) '(3))

Where the ‘(1), ‘(2), and ‘(3) are the values that will be passed into “mapcar”. As you can see, I have no declaration of the lambda or its parameters. Crazy, I know. The idea is to have a macro not only create the needed mapcar and lambda syntax, but to generate one parameter declaration for every argument… no matter how many arguments there are. The caveat here is that the generated argument names shouldn’t be something so common as x, y, or z. For this demo I’ll be using a list of numbers that have the “%” character appended to them. So instead of the “x y z” above, it will be “1% 2% 3%”. The final expansion should be:

(mapcar #'(lambda (1% 2% 3%) (+ 1% 2% 3%))

Before I get to the macro, I need a couple of helper methods.

First I need something that will generate a list of numbers as string. The reason why is that later I will concatenate each number string with the “%” character to have a basis for the created parameter names.

;;This creates a ascending list of numbers as string.  
;;  (numbers 5) == ("1" "2" "3" "4" "5")
(defun numbers (count &optional (finalList '()))
  (if (= 0 count)
      finalList
      (numbers (- count 1) (append (list (write-to-string count)) finalList))))

Now I need something to concatenate the number strings with “%”, AND turn them into legal parameter names.

;;This is used to take two concatenated strings, and turn them into potential parameter names
;;  (create-parameter-name "1" "%") == 1%
(defun create-parameter-name (x y)
  (read-from-string (concatenate 'string x y)))

Finally I need a method to use the other two method to create the needed list of parameters:

;;This is used to dynamically create the needed parameters for a lambda expression
;;  (create-placeholders "a" "b" "c") ==  '(1% 2% 3%)
(defun create-placeholders(arguments)
  (let ((argumentCount (length arguments)))
    (mapcar #'create-parameter-name  (numbers argumentCount) (make-list argumentCount :initial-element "%"))))

And here is the macro:

(defmacro ?> (conversion &rest args)
  `(mapcar #'(lambda (,@(create-placeholders args)) (,@conversion)) ,@args))

;;Expanded
(macroexpand-1 '(?> (+ 1% 2% 3%) '(4) '(5) '(6)))
(MAPCAR #'(LAMBDA (1% 2% 3%) (+ 1% 2% 3%)) '(4) '(5) '(6))

1) Ignore (mapcar #'(lambda(
2) Create the parameters based on the length of args
3) Ignore ) (
d) Evaluate the contents of conversion (the passed in method), and remove the surrounding parenthesis
5) Ignore the )
VI) Evaluate args, and remove the surrounding parenthesis
7) ignore )

Yay. Time to stop for now.

TDD – Test First: A Javascript Story

You might be wondering a great many things as you begin to read this most epic of epic things. I can only give you some of the answers you seek, and some that you don’t even know you need. I’m mysterious like that.

A while back I made a rather involved step by step example on how to do Test First design. Luckily I took down some good notes, and made a plethora of images to document the whole thing. I’m glad I did, since I did this about 4? months ago. Far beyond my 1 day long term memory. Basically it’s a step by step process on how to Test First validating a string based Social Security Number.

Side Note

Why use JavaScript? Ease and cross platform functionality. It was the easiest choice when making sure I had a language anyone can use. That coupled with the Chrome development tools, any one can debug also.

End Side Note

Now most people would just copy and paste some obscenely long regex string, and call it a day. I’ll assume you aren’t that guy, because if you are; I wish the internet had a door so it could hit your $@@ on the way out.

Why shouldn’t you use regex? Oh I don’t know. Could be have to do with it looking like something I could produce with a keyboard and a nerd rage session. Or it could be that regex is understood by (approximately) .0000000000000001% of the programming population that most of it remains untouched for decades “cause it werkz”. (I’m not bitter though) Not saying all regex is bad, just when it’s used for something as complex as a Social Security Number. Also, it makes for a reasonably short post… which I’ve already wasted 2 minutes (To 5 minutes depending on your reading level) of your life with. Efficient!

So these are the four rules that will be covered here:

1: It will return false if the string is null.
2: It will return false if there are any characters.
3: It will ignore dashes.
5: It will require a length of 9.

Are these all the rules? Sort of. There are actually some government based rules about what can be where, and were I not so lazy I would include them. However, that they even exist makes regex even more convoluted and/or impossible.

1) Folder Structure

  

As you can see, the final folder structure is pretty simple. If you’ve never used Jasmine before, it also is pretty simple. It is here on github, and… pretty simple? There are three files. That’s it. With those files you’ll find an html page to include jasmine

  

Ok since this is test first, a test has to be made first. Boom.

  

As you see, this test calls a method named “is_real_social_security_number”. Only thing is, that method doesn’t exist yet. Fear not, because here it is:

  

Well at least the shell. Why isn’t there code yet? Because right now it’s just about creating just enough to get it to “compile”, or at least in this case get a useful test failure that doesn’t #@!Q$% about a method that doesn’t exist.

RULE 1 – GET THE TEST TO COMPILE

Now when opening the html test page, it looks like thus:

  

RED!!! AHH!!11 That’s useless… or is it? This is an introduction to an important concept:

RULE 2 – GET A FAILURE

I know that seems sort of weird. After all, how often do you actually try to fail? Other than doing a really bad job of painting a room so that you’ll never be asked to again. Well in Test First you want a failure. In fact a success first can cause panic at times, because it might mean that your test is jacked or useless. For example: If I knew my test should expect a non null return based on a specific rule, and I haven’t added the rule yet. If it runs green, than it’s very possible the test isn’t written correctly, or that your tested code is returning something it shouldn’t. Good thing this isn’t true for the current test. Be happy, you can now prove to your mom that failure is good!

Ok now for the next rule:

RULE 2.43 – DO THE ABSOLUTE MINIMUM TO GET IT TO GO GREEN

This is probably the hardest concept to get in testing. The idea is, as the rule suggests, do just enough to get the current test to go green. That is the rule if it is the first or fifth test. So at this point, what will make it go green? Well remember that the first rule is “It will return false if the parameter is null.” So… send it a null, and return a true.

  

Now anyone who isn’t familiar with JavaScript, there is a bit of trickery here. Turns out that if(null) returns false. This makes if(argument) equivalent to if(argument != null). Aaaaaaaand if the test is run again:

  

Weeee green!

Ok so next on the list is: It will return false if there are any characters.

So once again, make the test first and watch it fail:

  
  

What the !@#%? Remember that thing about success sucks sometimes? This is it. Why is it green? The validation method is returning false no matter what, because the return variable in the method is currently hard coded to false. This coupled with the fact that the second test is looking for false makes it go green. (Yes testing for false is OK) Well, that can be fixed:

  

Now the return is always true if the argument is not null, and since texts is being sent through:

  

&*#% yah, failure!

Ok so now there needs to be code to make this go green. Sounds reasonable enough.

  

Ok so that may look a little strange at first. At least past the opening clause. First clause is just a check to make sure that it’s not an empty string. You might be wondering why I’m not checking for null in “contains_a_character”. This method I created is nothing more than an abstraction (Meaning it was taken straight from the main method, and had a method wrapped around it) from the method being tested. Because of that, the main method is checking for nulls. Were the “contains_a_character” method made to stand on its own, then there would most likely be a null check. Just think of the method as a private method. Aaaaand that brings us to another shouting rule:

RULE D – DO NOT TEST PRIVATE METHODS

This is a hard rule to get someone to understand. After all, if private methods aren’t tested, how can one be sure they work? The answer is: Because you’re testing the public method that is using said private method, the test suite by association tests the private methods. If anything is wrong with the private method, it will make the tests for the public one fail. Besides, in this case the “contains_a_character” method is nothing more than taking code out of the main method, and slapping a method signature on it to help with readability.

It also brings up something else… I made an oopsy. Generally method abstractions happen AFTER a green test. That way, you can get the test to go green with the most simple (and possibly inefficient) code. Then when the test goes green, you can optimize/abstract knowing that if you screw up, the test will fail. I’ll forgive myself this time…

Non Sequitur

One small thing that may be of interest is the return line. Most people would have just used a for loop. Start at the first dcharacter, walk each one, and break on the first non number. I am not most people, unless most people are defined as “recursion friendly”. Essentially I call the “contains_a_character” method over and over, with each call taking one character off the original string.

  isNan(currentText[0])

This is used to check just the first character in the string. If it is a non number (NAN) then true is returned. If it is a number:

  contains_a_character(currentText.substring(1))

This lops off the first character in the string (or grabs everything other that the first character), and calls the “contains_a_character” method all over again.

Side Note

Taking the first item of a list is usually referred to as “head”, “first”, or “car”. Taking all but the first is usually refereed to “tail”, “rest”, or “cdr”.

End Note

Do you have to use recursion? Nope. Most languages don’t handle recursion (Tail call to be specific) so you can end up blowing the stack (stack overflow). Not sure that was an appropriate way to phrase that…

In the end, for small string it’s up to you.

End Non Sequitur

Ok so now that’s done with, and as you could see: The parent method now has the “contains_a_character” method being called with the null
check. Time to run that test again.

  

Alright, so now it checks for null and non numbers. Awesome. Two more to go.

Ok, now something to ignore dashes. Personally I’d rather irraticate them all, but they breed like rabbits.

  

Pretty straight forward. Call the method with dashes, and expect it to show more tolerance for dashes than I have. Making the test a better man than I.

Now to run it.

  

And it failed. Please say you weren’t surprised by the result. Now for the code to fix it.

  

Ok so once again there’s some trickery going on here, so I’ll break it down.

  if((plainText = argument ? argument.replace('-', '') : argument))

Ok so that could actually look like this:

  var plainText;
  
  if(argument != null) {
    plainText = argument.replace('-', '');
  }

  if(plainText && !containes_a_number(plainText)

A lot more typing. Because the plainText = ar… part is encased in a pair of parentheses: the statement is run, plainText is given a new value, and that value is evaluated with the rest of the if statement. And since the if statement is done left to right, by the time it gets to the “!contains_a_number(plainText)” section of the if statement, plainText already has its new value.

  

&*#@! Ok so something is wrong. How do I know? I’m smart like that. The question is: Why did it fail? After all, the whole thing is based on the replace method. Time to dive into that. To do that in chrome you need to open the developer tools.

  

OR just press CTRL + SHIFT + J. tHATS… That’s the easier way. Next it’s a trip to “sources” land.

  

What this does is allows a user to view any JavaScript file in use for the page. For the purposes of this train wreck, the non test JavaScript file will be opened. There will be a break point on the return line.

  

Hrmmmmmm still looks like it has dashes in it. Turns out that replace only replaces the first instance. Learned that from the Google. After doing some searching on that, I came across This post. Basically it shows that using replace with a regular expression is the preferable way to remove all the dashes.

  

Although in retrospec, I could have done something like this:

  function removeDashes(stringToCopyFrom cleanedUpText){
    return stringToCopyFrom.length === 0  ? cleanedUpText  : removeDashes(state.substring(1), stringToCopyFrom[0] === '-' ? cleanedUpText : cleanedUpText + stringToCopyFrom[0]);
  }

Once again, this is a recursive call. If the stringToCopyFrom text has no length, return cleanedUpText. What’s cleanedUpText? It’s the string that will grow for every time the method is called recursively. The idea is to construct a new string that has no dashes by walking through the original string, and adding any non dashes to the cleanedUpText string. So for every “iteration” the first character is checked to see if it’s a dash. If it is, then ignore it and pass through the current value of cleanedUpText as the second value of the method call. If it isn’t, then append the current character to the current cleanedUpText, and send that through as the new cleanedUpText value.

The main reason I’m pointing this out is that even though I had decided at the time the solution I had was good (I has = I stole); possible improvements can always be sought. Yes I know, I’m not as perfect as you thought I was.

Now to run.

  

WEEEEEEEEEEEEEEEEEEEEEEEEEE

Now for the last step: Length check. So once again, the test is created first.

  

As you can see, there are three assertions in the one test. It could be argued that they should be three separate tests since it should be a 1:1 ratio. Or it could be argued that even though there are three assertions, they work the same. Another possibility would be to combine all three into one statement by using &&. Apparently once again my laziness got the better of me.

Now to run that @#%&*:

  

Looks like only two failed, as they should have. After all, a string of 9 letters has no reason to fail with the given code. This is another reason why the test could be split up. One that checks to make sure the “happy path” works (9 numbers), and the other to make sure any other length fails.

  

Simple addition of the length check. Now to run the test again:

  

Alright. Hard to type why simultaneously patting myself on the back. So this means we’re done, right? Hell no.The best part is next: Refactoring. The goal will be to abstract away a lot of the code into methods with very English and readable names.

Refactor 1: Impact – slight

Remember that bit where I said there didn’t need to be a null check in the “contains_a_character” method? Still doesn’t, BUT I can get that check for free. Just add the assertion to the test:

  

And then replace the === “” check with the much shorter JavaScript null/empty string check:

  

And run the test:

  

Ok, that’s one down.

Refactor 2: Impact – Questionable

Next is to remove some code from the main method.

  

What happened there? I removed the “isARealSocialSecurityNumber” variable since it only held the result of the truth check. This is questionable since it could be argued that even though the “isARealSocialSecurityNumber” might have been extraneous, it helped convey the intention of the method. Personally, I’m fine with reducing that down to only a truth check.

  

Oh &(%@ no. I dun broke somethin’. For some reason the original test to expect false when passing in an empty string (or null) is now failing. This means that the method is allowing empty strings to pass through. (Hence the “Expected ” to be false” error) Bad. This time we’ll take a trip to jsfiddle land. What is jsfiddle? It’s a site where you can paste JavaScript, and get an immediate result.

  

Just as suspected, the method is returning an empty string instead of a Boolean. Since there no longer is an if statement, the assignment trick fails to return a Boolean on an empty string. The reason being is that since the original if statement actually returned “false” if the string was empty. Now the assignment trick is returning the actual string because of this:

  if(plainText = argument ? ... : argument)

So if the argument is empty, false is evaluated. This means the second half of the ? : will return the actual arugment string. This is not a true/false value.

  

That part of the if statement will now return “false” if the “argument” is empty/null.

  

Yay.

Refactor 3A: Impact – Questionable

Much like the last questionable refactoring, I am combining two truth checks:

  

Now the entire “contains_a_character” is one if statement return.

Refactor 3B: Impact – Great

In that same image you might have noticed there was more to the change. The easiest to notice is the method was renamed from “contains_a_character” to “does_not_contain_a_character”. With that change, the truth check involved was reversed. By doing this, I was able to replace the old “!contains_a_character” with just “does_not_contain_a_character”. This makes the whole thing more readable:

  

This brings up another rule:

RULE IV – DO NOT THINK REFACTORING STOPS AT STRUCTURE CHANGES

Basically, when one is refactoring, one should not just look for code improvements. Renaming methods to make their intention known is incredibly important. Renaming them so they could be understood by those things we call “business analysts” means someone with any experience with reading can immediately pick up what the method is doing.

Refactor I lost count: Impact – Great

  

This is yet another section of the if statement that has been pulled into a method with a very readable name. In fact, if you replace “&&” in your head with the word “and” it reads like:

if .. and does not contain a character and has a valid length

Much nicer than what it was before.

Refactor 0110: Impact – Great

  

One more abstraction, and now even a child could understand. Well a child that can read. Probably not a baby.

  

Yay for the final green.

Now there are more rules for a social security number, but this had been more than enough to waste your time. I’ll spare you from any further harm.