![\"ap_comp_sci\"](\"http:\/\/hybridclassroom.com\/blog\/wp-content\/uploads\/2014\/05\/ap_comp_sci.jpg\")
<\/a><\/p>\nOn one of the last days of the AP Computer Science class, I met with a few students who had been participating in the High School Capture the Flag hacking contest. A high school in New Jersey had created a competition that would allow teams of high school students using digital tools to solve various types of puzzles.<\/p>\n
One of the problems involved a text file with just two lines in it. The first line explaining that students would need to search the file for a series of English words in sequence, although those words wouldn’t be separated by spaces. The second line consisted of over 10 million letters, mostly scrambled, but with words occasionally found within them.<\/p>\n
Here are 200 letters from that file:<\/p>\n
You can see the word “hiss” in there, as well as “rips”, “fee”, “call”, “has”, as well as a number of 1- and 2-letter words, but clearly nothing identifiable as a sequential series of words. <\/p>\n So how do you go about looking those needles in that haystack?<\/p>\n I had some ideas, and I’d been working on the problem for a day or two. I wrote a Python program to read all 10 million characters into a string so that I could search through it. I Googled and found a couple of lists of English words, arranged in order of popularity, and inserted those into my program as a list of words.<\/p>\n But now what? How do you start trying to find a sequence of words in a line of ten million letters?<\/p>\n My first algorithm looked liked this:<\/p>\n It didn’t work. It was a first attempt at trying to work through the file, and this particular strategy was much too slow—my search was going nowhere fast. <\/p>\n Time to alter the strategy.<\/p>\n My second try concentrated on reducing the number of text interactions that had to take place. This time, I would:<\/p>\n Here’s what the results look like for that strategy:<\/p>\n It didn’t work. I mean, the program worked fine, producing a seemingly endless string of lines that matched the specifications I had, but none of the lines produced were what I was looking for. Here’s the partial output from that second algorithm.<\/p>\n I still was getting “words” in each of those lines that didn’t correspond to the flag I was searching for. This was starting to get frustrating.<\/p>\n I went into class the next day and explained to the students my frustrations, and they were happy to brainstorm different strategies. At one point, Daniel said, “Why don’t you just look through each line in the file and count the number of words in it? Maybe the line with the most words will be the one we’re looking for.”<\/p>\n “That’s a good idea, Daniel, but the file isn’t split up into lines. It’s just one long line of characters.”<\/p>\n He thought about it for a minute, and his partner Ezra said, “Well, let’s just split it up into lines. 140 character lines. That’s good enough for Twitter.”<\/p>\n So that’s what we did. The students have been studying Java for this past year and I was coding in Python, so they watched while I coded their strategy:<\/p>\n Because it was a relatively simple strategy, the two decided that they could afford to search for any words contained in 10,000-word dictionary. We watched as the results appeared on the screen:<\/p>\n Last login: Sat May 24 18:03:42 on ttys002 And there it is, on the line with 33 matches, just a few moments after starting the program running:<\/p>\n these letters represent the cloth marker that unlocks rewards<\/em><\/p>\n We submitted the flag to the contest and saw out score total immediately jump up 400 points—it was our single biggest success of the competition to that point.<\/p>\n I like this story because it reminds me of a few things that we sometimes forget. Working on digital problems like this is not always about coding— sometimes it’s about strategies. Also, there are trade-offs in strategies that require considering constraints: how much memory, power, time, and data do you have? How do your solution results vary based on the trade-offs you make?<\/p>\n Computer Science teachers talk about these things, but I’m always pleased to see a situation where the students get to actually experience that exploratory process themselves.<\/p>\n Thanks to Daniel, Ezra, Adam, and Stephanie for being willing to play with this problem on the last day of school!<\/p>\n","protected":false},"excerpt":{"rendered":" DANIEL’S SEARCH HACK by Richard White 2014-05-24 On one of the last days of the AP Computer Science class, I met with a few students who had been participating in the High School Capture the Flag hacking contest. A high school in New Jersey had created a competition that would allow teams of high school … Continue reading Daniel’s Search Hack<\/span> nhisseokenphoncecrgoeemmoedkihrhobufiiripsthituhelttiytftihweaihurmadarwwesrfeehstetpiaiiendyeogeallrrrescihslhyorsdccalloaaoeyrotlnnstuovdhreshapmmrennaaehtprsedtlsciaemtggsriedencsneihassskusosekhci<\/code><\/p>\n\n
\n
alludcgytsooiahitaonoayhlfcdseheieytreee
\n alludcgytsooiahitaonoayhlfcdseheieytreee
\n alludcgytsooiahitaonoayhlfcdseheieytreee
\n alloswvgtwousmipohivteceyihrugitdrttsinu
\n allesettupslasweoovnsetlbiaerietmntadnea
\n allesettupslasweoovnsetlbiaerietmntadnea
\n allesettupslasweoovnsetlbiaerietmntadnea
\n allechslaashtwnonhhsirewteoaeadmoiitlrhi
\n alloiarlfeyedacusoemtniohneegsaailaennso
\n alloiarlfeyedacusoemtniohneegsaailaennso
\n alloiarlfeyedacusoemtniohneegsaailaennso
\n allswhybrnastsoetedotwilnrmollhtieeterol
\n allpeinnucctdanyedrtsittadhhnldvsiniedln
\n alladhlasgdeaeihownaotoroeemhaueailoenwh
\n allihyhcinnchpbsoileowidsupredhnpywoweyh
\n allihyhcinnchpbsoileowidsupredhnpywoweyh
\n allmhmsfoodieutreethktevkevfaieehvtlhaii
\n allvcniaionoeuwesthiontnebedneehgecetlts
\n allvcniaionoeuwesthiontnebedneehgecetlts
\n allacohohhssoraaehylesooyfeeithseiioatrm
\n alllaseeatholnsttochtiwrlsridtwodrefvneo
\n alleeoninshrhugdnewizdeydtepnrartsossrtl
\n<\/code><\/p>\n for line in lines:\r\n num_of_words = 0\r\n for word in searchTerms: \r\n if line.find(word) != -1: \r\n num_of_words += 1\r\n if num_of_words > 25:\r\n print num_of_words, line\r\n<\/pre>\n
\nMotteRouge:~ rwhite$ \/var\/folders\/6x\/vklj_pls5215szrp_k2qcjcc0000gn\/T\/Cleanup\\ At\\ Startup\/find3-422672661.132.py.command ; exit;
\nFile has been split into lines! Proceeding…<\/p>\n 26 netenivgdyblduenehttihaaoshasnoadhigdateilnoteanabinmstaruceoarasuleedpnhtgeoendtgedeeincodolropthei
\n 26 deeeeepraosderwfsrerepimnsinaosutttnoeytvrvtheterthistollagtitnhsminewitcecnlrsbgeoeddiorwadanartell
\n 27 chaoomelohdanamtgswsbtroddtapmcfhlewasalnewasisscelapostnecstotvstviiiederectunoauwjleeddicbsigesnem
\n 27 ailmavbfngdfawdigcrseentatoueiefrdrnorfkersrutccamemdireaeiedsleoauieiaitmlsitemhiapropenhbutworfson
\n 27 tnatrsirvsprosaeseebatoniwrtaptranuinetdsyraheroenattphweelilnhopedelrudolbiaimoioiaahlttonesoucoduy
\n 26 thahksvrtetentnaanyosmyclekrmrnotestadrtslonuisnproncedpesaehietidethereheionmcbalasaeriantrsrheteeh
\n 26 odicelerussltltmerehsoaeebaotruettanarfdereunecgtsnsnatllasteakitnngodrsuseerthdfaisirnswaudcsvwhvie
\n 27 akyoeaaptebheaeasetrrsdairnslegstensnhhtirepysuxxthseelesnetfdaniknsethaiarsoslutsperaegotedibnnlids
\n 27 hidsrdaedoiltdetoeiepdscencairdstheeovrncwaaihstnthtnebemochthestyaahiseperateanhistseaoneeyntareade
\n 26 edlotetwlettdtstfdnseovnrpamatelfroltsmahliassseaueeeamihnhgavepaadatrglettanitoleeenlredramdhoyaddt
\n 30 latecwhoodehderowtaesitfeflantenvweosrehonsethlaerateeeersiosrlesuaidpeutdineacetzrthrchbhrideeafsat
\n 26 tvanodeaosomidhonatnusidispithscvhsnhsoilesacciraeenycielaehoallooldamwrneirwcfamotntrdataoeenogleeb
\n 33 ntevnaaureakltyashtbosutheselettersrepresenttheclothmarkerthatunlocksrewardsehegcceremuahwtmknnflswa
\n 29 bandosytrctanoyearenonajrnpasrlgaohisnhunetnsielistdoecdpeehenaasshecisiojersydataelpsheeulhesvfonli
\n 28 nargelrhendedtoidlteauuvtihsursaioptehetclbnigeauhoneystolheatbsantrwmsctipsslagedsehieahsadoacscihn
\n<\/code><\/p>\n