Forem: Valerie Woolard

Fibonacci Numbers & Project Euler Problem Two

Valerie Woolard — Fri, 07 Aug 2020 23:41:47 +0000

Continuing on my series of going through the first 100 Project Euler problems, we're on to problem two. Here's problem one in case you missed it.

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms

The Fibonacci sequence is a series of numbers in which the next number is the sum of the previous two.

The first time I solved this I think I probably checked if each number in the sequence was even, with a modulo similar to problem one, such as:

item % 2 == 0

But it occurred to me that the numbers follow a pattern, odd, odd, even so I could sum the even terms by adding together every third term.

I wrote a method to sum together all even Fibonacci numbers less than n. The solution is below or on GitHub

def sumOfEvenFibs(n):
  terms = [1, 1, 2]
  total = 0
  while terms[2] <= n:
    total += terms[2]
    t0 = terms[1] +  terms[2]
    t1 = terms[2] + t0
    terms = [t0, t1, t0 + t1]
  return total

print(sumOfEvenFibs(4000000))

Interested to see how others approached this one!

Modular Arithmetic & Project Euler Problem One

Valerie Woolard — Fri, 07 Aug 2020 03:11:13 +0000

In January 2020, which was approximately three years ago by my count, I happened to see this post:
// Detect dark theme var iframe = document.getElementById('tweet-1213168751413207042-890'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1213168751413207042&theme=dark" }

I vaguely thought this sounded like a cool idea and that I should do it and write blog posts about it. I've chipped away at Project Euler before, and as of writing have solved about half of the first 100, although some through methods that I would be embarrassed to tout in a programming blog post.

A lot has happened since January, but I'm going to try Lindsey's 100 days of blogging in combination with this challenge:
// Detect dark theme var iframe = document.getElementById('tweet-1291129487116050432-224'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1291129487116050432&theme=dark" }

I want to tell you straight up, right now, that we are absolutely not getting through the first 100 Project Euler problems in the next 100 days, but I want to start chipping away a bit each day and hopefully finish them all eventually. I am not planning to publish every day but stick with me.

Now, I also want to say by way of preface: these are puzzles that are fun to try yourself! There will be spoilers here, read at your own risk!

Also, Project Euler is pretty math-y. If that's not your thing, it's cool! There's plenty of programming that doesn't get this deep into math. And I'll try to bring in relevant programming and computer science concepts too when I can, because I'm not all about math either tbh

Okay, without further ado, problem one.

Find the sum of all the multiples of 3 or 5 below 1000.

This sounds similar to the classic FizzBuzz interview question and can be solved similarly.

The key idea here is that we need a way to quickly check whether a number is divisible by another number. We could do something like dividing the numbers and checking for figures after the decimal, but that seems arduous and might be annoying to ensure that the numbers are treated as decimals rather than automatically-rounded integers.

The magic here is the modulus operator. It may not have been covered in your math classes unless they covered discrete math or computer science, but the idea is pretty straightforward, it returns the remainder when the first number is divided by the second.

Here are a few examples:

10 % 5 == 0
23 % 5 == 3
4 % 5 == 4

If it's still unclear, try with a few more values in your REPL or on Repl.it.

Modular arithmetic comes up in plenty of applications irl, like minutes past the hour.

So we can see that numbers that are divisible by the second number will return zero with the modulus operator.

For numbers that are divisible by five:

i % 5 == 0

And for numbers that are divisible by three:

i % 3 == 0

Now that we have an easy way to identify these numbers, we can iterate through and add each of them to a running total. I wrote a function that would sum all 3 and 5 multiples under n, but there are plenty of alternate ways to approach it.

Here's my completed code, also available on GitHub.

def sumOf3or5MultiplesUnder(n):
    total = 0
    for i in range (0, n):
        if i % 3 == 0 or i % 5 == 0:
            total = total + i
    return total

print(sumOf3or5MultiplesUnder(1000))

That's it for problem one! Let me know what you think or if you used a different approach.

What Recreating Old School WordArt Taught Me About CSS

Valerie Woolard — Mon, 05 Aug 2019 20:54:31 +0000

A few weeks ago, after being thoroughly inspired by the wonder that is pure CSS Gritty, I got the idea to attempt to recreate WordArt from old school Microsoft Word in pure CSS.

WordArt was a staple of my early-00s Word experience, and to my middle & high school brain was just the thing to make any piece of printed material look ✨polished✨.

It has been toned down in more recent versions of Word, but I wanted to go for the nostalgia factor and recreate the classics.

I was not the first to have this idea. Several sites exist to generate modern WordArt on the web, but I noticed that these didn't seem to have all the options of the original WordArt function, and so I took this as an opportunity to get a bit better at CSS and try to implement them myself.

As it turns out, this is easier said than done, and it is with good reason that those online WordArt generators lacked some of the classics.

One of the first things I found is that CSS doesn't have a great way to "warp" text. You can have the text follow the path of an SVG, but you can't distort the shape of the text as in the third example on the first image. There may be legitimate accessibility reasons for this, as it can make text much less legible. It would also probably be difficult to implement in a robust way in CSS (and it's probably not a terribly useful or requested feature). I tried to approximate it using varying font sizes and it did not turn out too great. Image above.

It's also more difficult than you'd imagine to set an image as the fill for text. And even so, it's only supported in WebKit. There's a tutorial here. Setting a gradient as a text fill requires a similar process.

As I mentioned earlier, it is possible to wrap text along an SVG path but I think it would be hard to accommodate for text of arbitrary length (e.g. have a squiggly line that just got longer based on the text that was used). The example WordArt generators that I liked got around this issue on slanted text by using the CSS transform properties instead of SVGs.

Beyond these few challenges, I was impressed with how well most of the WordArt could be done with CSS. All the more reason to avoid embedding text in images (besides the existing accessibility wins). All of my CSS WordArt creations can be found on this Codepen.

Building my dream recipe search in Prolog

Valerie Woolard — Wed, 24 Jul 2019 20:19:26 +0000

I'm more than halfway through my twelve-week session here at the Recurse Center. While here, I've been trying to expand my programming horizons beyond my Rails web development, object-oriented centered universe. That has involved exploring natural language processing, hardware hacking, offline-first applications, and silly pure CSS WordArt, to name a few.

I've been working through the book 7 Languages in 7 Weeks with a few other folks here, and this week we came upon the Prolog programming language.

Prolog is unlike any language I've ever come across before. It's a declarative rather than procedural language, so instead of programming steps of how something is done, you essentially give it facts and rules, against which it can then execute queries. There are good Prolog tutorials on Dev and elsewhere and I will not attempt to write one here.

It looks something like this:

parent(fantine, cosette).

child(X, Y):-
  parent(Y, X)

The above states "Fantine is Cosette's parent." And establishes that X is the child of Y if Y is the parent of X. We can then run the following queries:

?- parent(fantine, cosette).
true
?- child(cosette, fantine).
true
?- child(cosette, Who).
Who = fantine

In the final example, we are essentially asking "Whose child is Cosette?" to which Prolog supplies a possible value to the variable Who as a means of solution.

If you'd like to play around more with Prolog in the browser you can do so on this page.

The book went into how this language could be used to coordinate schedules of dolphin trainers and write sudoku solvers, but I was already too focused on my white whale 🐋(pun intended): throwing the perfect dinner party.

So I thought, "What if I could supply my favorite recipes to Prolog in the form of facts and then make a query based on the amount of time I had or items that I had in the pantry?"

I started in on this blueberry muffin recipe.

recipe(muffin).

contains(blueberries, muffin).
contains(milk, muffin).
contains(butter, muffin).
contains(eggs, muffin).
contains(salt, muffin).
contains(sugar, muffin).
contains(flour, muffin).
contains('baking powder', muffin).

diet(vegetarian, muffin).
diet(nut-free, muffin).

minutes_to_prepare(40, muffin).

meal(breakfast, muffin).
meal(snack, muffin).
meal(dessert, muffin).

I did this for a few more recipes, and soon I was able to build queries like:

?- diet(vegan, First), meal(appetizer, First), 
meal(dinner, Second), contains_ingredients(Second, [basil, zucchini]), 
meal(dessert, Third).

Translated to plain English: A vegan appetizer, a dinner that contains basil and zucchini, and a dessert.

Prolog then spits out a menu suggestion:

First = gazpacho,
Second = 'summer pasta',
Third = muffin

If there is more than one possible menu that satisfies the constraints, you can run it again to see additional options.

This is, of course, a long way from a particularly user-friendly interface, but got me thinking about all the possibilities that could be implemented to make the recipe search tools of my dreams. Here's a gist with the code used here. 🥣🍝🍰

Tips for fun and productive conferencing

Valerie Woolard — Fri, 19 Jul 2019 19:57:05 +0000

Conferences are a great career opportunity, both in terms of learning resources and the chance to make lasting personal and professional connections with people in your field. But that's all a little daunting if you're new to the field or put off by the idea of "networking," so I've put together this list of some ideas to help you get the most out of your conferencing experience.
Ruby and RailsConf have a scholar/guide program to pair people new to the community up with more seasoned conference-goers. I'll be serving as a guide for the third time next week, so I'll share some of the knowledge that I've shared with and gained from the scholars I've met through the program.
I'm writing this guide with the tech conferences I've been to in mind, but the advice probably applies to other conferences as well.

Strategize
For a multi-track conference, there will be lots of sessions going on at the same time, so get at least a vague idea of what sessions you'd like to go to when. Keep in mind that at most conferences talks will be recorded, so if there is a mix of workshops and talks, you're better off going to a workshop you're interested in and getting the hands-on, interactive experience and catching the talk on video later. Keep a list of the talks you want to watch later so you don't forget by the time the videos come out.
It's also all right if you don't want to go to a talk during every slot. You can find a quiet place to process and synthesize what you've heard so far or hang out in the hallway and chat.

Know your limitations
Conferences are exhausting. It's okay if you don't have the energy or focus for a super-technical talk late in the afternoon. Or if you know you'd rather watch the video later so you can pause and rewind. Maybe you aren't big on after-hours events. Or maybe you are but you need to catch a nap first. You're allowed to come and go as you please to get the most out of your experience. That includes leaving a talk in progress if you're just not feeling it.

Put the laptop down
I know, you're at a tech conference, it's counter-intuitive. But instead of looking things up as the speaker mentions them or trying to type notes, write down notes or live-tweet the talks. The exception to this is in workshops where you're actually writing code as part of the exercise.

Tweet
If you're taking notes by hand, highlight important points to tweet during the breaks. Otherwise, live-tweet the talks you attend. Make sure to take note of or find the speaker's twitter handle if they have one. Also use the conference hashtag if there is one. This is a great way to engage with speakers, who will appreciate hearing what points struck you most, and is also a great way to engage with other attendees and the tech Twitter community at large.

Have 1:1 and small group interactions
Going to the same conference with hundreds or thousands of other people feels intimidating, so make sure that you're getting some time in smaller groups. Chat with someone at lunch or get a group of a few people together to grab coffee or dinner. This will get easier as you attend more conferences as you'll begin to see familiar faces.

That about sums up my advice. Have any comments or ideas to add?

Mechanizing Surrealism: A look at absurd_gloss

Valerie Woolard — Thu, 06 Jun 2019 18:39:08 +0000

Lately, I've been spending some time exploring the stranger corners of programming. I've been playing with natural language processing tools in Python, and last week I wrote about finding unique words in Alice in Wonderland.

While I was working through that question, I found an enigmatic method in the documentation for the Nodebox English Linguistics Library. It was called absurd_gloss and purported to return "an absurd description for the word."

Not entirely sure what that meant, I tried it out a little for myself:

>>> en.noun.absurd_gloss('castle')
'a place where you are just as comfortable and content as if you were home'
>>> en.noun.absurd_gloss('aardvark')
'primitive reptile having no opening in the temporal region of the skull; all extinct except turtles'
>>> en.noun.absurd_gloss('truck')
'handcart for moving a load of laundry'
>>> en.noun.absurd_gloss('computer')
'a subsidiary organ of government created for a special purpose; "are the judicial instrumentalities of local governments adequate?"; "he studied the French instrumentalities for law enforcement"'
>>> en.noun.absurd_gloss('cow')
'sure-footed mammal of mountainous northwestern North America'
>>> en.noun.absurd_gloss('pelican')
'chiefly web-footed swimming birds'
>>> en.noun.absurd_gloss('sleep')
'the London residence of the British sovereign'

I found the results a little surreal. Somewhat related to the original input in an uncanny way, and sometimes way off base. So what was happening here?

I dug into the source code and found the method definition:

def absurd_gloss(q, sense=0, pos=NOUNS, up=3, down=2):

    """

    Attempts to simulate humor:
    takes an abstract interpretation of the word,
    and takes random examples of that abstract;
    one of these is to be the description of the word.

    The returned gloss is thus not purely random,
    it is still faintly related to the given word.

    """

    from random import random, choice

    def _up(path):
        p = hypernym(path, sense, pos)
        if p: return p[0][0]
        return path

    def _down(path):
        p = hyponym(path, sense, pos)
        if p: return choice(p)[0]
        return path

    for i in range(up): q = _up(q)
    for i in range(down): q = _down(q)
    return gloss(q)

Okay, let's unpack this. First, the comment "attempts to simulate humor." 😂 Teaching computers to be funny is probably behind only caching and naming things in terms of hard problems.

q is the input word, sense specifies which meaning of the word to use, from most to least common (defaulted to the most common). pos is the part of speech to use (defaulted to nouns). And then there are numbers for up and down.

The way abstract_gloss works is that it takes the first hypernym of an input word, then the first hypernym of the hypernym, etc.

What's a hypernym, though?

Great question. The documentation describes it as an "abstraction," but it's probably most helpful to give examples:

>>> en.noun.hypernym('cloud')
[['physical phenomenon']]
>>> en.noun.hypernym('animal')
[['organism', 'being']]
>>> en.noun.hypernym('person')
[['organism', 'being'], ['causal agent', 'cause', 'causal agency']]
>>> en.noun.hypernym('castle')
[['mansion', 'mansion house', 'manse', 'hall', 'residence']]

So it takes those successively the number of times specified in the up argument (3 by default) and then takes random hyponyms the number of times specified in the down argument.

What's a hyponym?

A hyponym is an example of a given word. Let's look at more examples (return values truncated for brevity):

>>> en.noun.hyponym('cloud')
[['coma'], ['nebula'], ['aerosol'], ['cosmic dust'], ['dust cloud'], ['mushroom', 'mushroom cloud', 'mushroom-shaped cloud']]
>>> en.noun.hyponym('animal')
[['pest'], ['critter'], ['creepy-crawly'], ['darter']]
>>> en.noun.hyponym('person')
[['self'], ['adult', 'grownup'], ['adventurer', 'venturer']]
>>> en.noun.hyponym('castle')
[['Buckingham Palace']]

absurd_gloss takes successive hypernyms and then successive hyponyms and then returns the gloss (or definition) of the last hyponym. Because the hyponyms are chosen at random, you can get different results for the same input. And the more general a word you start with (and thus the more hyponyms there are) the bigger the potential for the result going way off the rails.

I added some print statements to trace through the process:

>>> en.noun.absurd_gloss('clown')
Hypernym : clown
Hypernym : fool
Hypernym : simpleton
Hyponym : person
Hyponym : perspirer
Resulting word: perspirer
'a person who perspires'
>>> en.noun.absurd_gloss('clown')
Hypernym : clown
Hypernym : fool
Hypernym : simpleton
Hyponym : person
Hyponym : watcher
Resulting word: browser
'a viewer who looks around casually without seeking anything in particular'
>>> en.noun.absurd_gloss('pelican')
Hypernym : pelican
Hypernym : pelecaniform seabird
Hypernym : seabird
Hyponym : aquatic bird
Hyponym : seabird
Resulting word: gaviiform seabird
'seabirds of the order Gaviiformes'
>>> en.noun.absurd_gloss('person')
Hypernym : person
Hypernym : organism
Hypernym : living thing
Hyponym : object
Hyponym : part
Resulting word: language unit
'one of the natural units into which linguistic messages can be analyzed'
>>> en.noun.absurd_gloss('universe')
Hypernym : universe
Hypernym : natural object
Hypernym : whole
Hyponym : concept
Hyponym : conceptualization
Resulting word: approach
'ideas or actions intended to deal with a problem or situation; "his approach to every problem is to draw up a list of pros and cons"; "an attack on inflation"; "his plan of attack was misguided"'
>>> en.noun.absurd_gloss('animal')
Hypernym : animal
Hypernym : organism
Hypernym : living thing
Hyponym : object
Hyponym : je ne sais quoi
Resulting word: je ne sais quoi
'something indescribable'

There's certainly more interesting work you could do by tuning the up and down values to make the results more or less abstract, but I hope this was an interesting look at a method which at first seemed completely nonsensical. 🔮🦄

This is just one of many interesting tools available in the Nodebox English Linguistics Library, which is worth exploring more if you found this interesting.

Exploring Natural Language Processing with Alice in Wonderland

Valerie Woolard — Thu, 30 May 2019 22:09:17 +0000

As both a programming nerd and a literature nerd 🤓 I've recently been trying to find more ways to unite the two. I'm currently spending the summer at the Recurse Center doing my own self-directed learning, so it seemed like a great time to start examining the overlap in this Venn diagram.

Going down this rabbit hole, I got obsessed with this adjacency matrix of characters in Les Misérables and wondering what else I might be able to look into about my favorite books with code.

I've been working through the book Natural Language Processing in Python and also love Carroll's use of language, including his tendencies to just invent words and rely on context and sound symbolism to make them comprehensible.

With that in mind, I was thinking about how to identify uncommon or invented words in a text.

So, armed with the text of Alice in Wonderland, I started on my quest (pedantic note: "Jabberwocky" in fact appears in Through the Looking Glass, so going into this I wasn't sure what, if any, invented words I should expect to find in Alice).

The book is kind enough to supply a function that should do this very thing:

def unusual_words(text):
  text_vocab = set(w.lower() for w in text if w.isalpha())
  english_vocab = set(w.lower() for w in nltk.corpus.words.words())
  unusual = text_vocab.difference(english_vocab)
  return sorted(unusual)

So I plugged that in and gave it a try. I got a list of 582 words back. That seemed like an awful lot, so I scanned through some of them. Plenty of them seemed to be pretty common: eggs, grins, happens, presented.

Ok, so maybe this was going to be harder than I thought. I got a little frustrated and tried using some other corpuses. But this corpus had a quarter-million words in it, surely it should have these incredibly common words? Then I noticed something about the words. Most of the nouns were plural (e.g. eggs) and the verbs were conjugated (e.g. presented).

I wanted to get the words into their most "basic" forms. Singular, in the case of nouns, and infinitive, in the case of verbs. To this end, I tried the NodeBox English Linguistics Library. There were a couple hiccups here. For example, is_verb? did not return true for all conjugated verbs and singular had some unexpected results, so I ended up running the infinitive and singular methods on everything, and returning them if they returned a non-empty result that was different from the starting word.

Since this method is much slower than the simple set difference in the original method, I implemented it as a second pass, only to be used on words that were not found in the first diff. I rewrote unusual_words as follows:

def unusual_words(text):
  text_vocab = set(w.lower() for w in text if w.isalpha())
  english_vocab = set(w.lower() for w in nltk.corpus.words.words())
  unusual = text_vocab.difference(english_vocab)
  basic_forms = set(basic_word_form(w) for w in unusual)
  return sorted(basic_forms.difference(english_vocab))

And wrote a new method basic_word_form, which used the NodeBox methods:

def basic_word_form(word):
   word = word.lower()
   singular = en.noun.singular(word)
   if singular !=  word:
       return singular
   else:
      infinitive = en.verb.infinitive(word)
      return infinitive if len(infinitive) > 0 else word

This got me back a list of 92 words. Not too bad. Some were Roman numerals, some were proper nouns (France, London, Shakespeare), others legitimately unusual or invented (seaography, gryphon). There were a few that seemed out of place still though, like smallest, larger, loveliest--comparatives and superlatives. I didn't see anything in NodeBox that might help with reducing these to their base adjectives or adverbs. There were also a few verbs, like dreamed, which had not been correctly converted to their infinitive forms.

I noticed that there was a tool in the Natural Language Tool Kit (NLTK) that purported to do just this--get the base (or "stem") form of a word.

I tried two different "Stemmers," the Porter Stemmer and the Snowball Stemmer:

def unusual_words_porter(text):
  text_vocab = set(w.lower() for w in text if w.isalpha())
  english_vocab = set(w.lower() for w in nltk.corpus.words.words())
  unusual = text_vocab.difference(english_vocab)
  basic_forms = set(basic_word_form_porter(w) for w in unusual)
  return sorted(basic_forms.difference(english_vocab))

def basic_word_form_porter(word):
   word = word.lower()
   stemmer = nltk.PorterStemmer()
   return stemmer.stem(word)

def unusual_words_snowball(text):
  text_vocab = set(w.lower() for w in text if w.isalpha())
  english_vocab = set(w.lower() for w in nltk.corpus.words.words())
  unusual = text_vocab.difference(english_vocab)
  basic_forms = set(basic_word_form_snowball(w) for w in unusual)
  return sorted(basic_forms.difference(english_vocab))

def basic_word_form_snowball(word):
   word = word.lower()
   stemmer = nltk.SnowballStemmer('english')
   return stemmer.stem(word)

These returned lists of 187 and 188 words, respectively. The stemmers didn't seem to do exactly what I needed--they often lobbed off conjugations or irregular plurals such that what remained was not an English word. Some of the outputs: trembl, turtl, difficulti.

I found one more tool: the lemmatizer. It is meant to reduce words to their "lemma," the "the canonical, dictionary or citation form of a word." Sounds promising.

>>> lemmatizer = WordNetLemmatizer()
>>> lemmatizer.lemmatize('hedgehogs')
u'hedgehog'
>>> lemmatizer.lemmatize('says')
u'say'

I noticed that it worked much better if you specified the part of speech of the word through an optional second argument.

>>> lemmatizer.lemmatize('prettier')
'prettier'
>>> lemmatizer.lemmatize('smallest')
'smallest'
>>> lemmatizer.lemmatize('smallest', pos='a')
u'small'
>>> lemmatizer.lemmatize('prettier', pos='a')
u'pretty'

Problem is, I didn't know what part of speech the words were, and some might be different ones depending on context, which I didn't have. So I tried each one without a part of speech, then as an adjective, a verb, and a noun, and returned the first one that didn't match the starting word. 🤷

def basic_word_form(word):
  word = word.lower()
  lemmatized_forms = [lemmatizer.lemmatize(word), lemmatizer.lemmatize(word, pos='a'), lemmatizer.lemmatize(word, pos='v'), lemmatizer.lemmatize(word, pos='n')]
  for form in lemmatized_forms:
    if form != word:
      return form
  return word

This produced the shortest list yet, at 71 words. The main false positives appeared to be British spellings, skurried, neighbour, curtsey, Roman numerals, and real words inexplicably missing from the original corpus, kid, proud. But a lot of the words did seem to be truly unusual.

I decided to do one last experiment, which was to run the text of Through the Looking Glass through the same process. I expected I'd find many more invented words, including the famous vorpal, uffish, brillig, and slithy from "Jabberwocky."

This text was not included in the NLTK by default, so I grabbed it from Project Gutenberg.

When I ran it through, I got 87 unusual words, including brillig, callay,callooh, frumious, etc. Funny enough, vorpal and slithy seem to have made their way into the NLTK corpus of "real" words, so they were not returned. 😂

This was my first foray into natural language processing tools. This is clearly not the most efficient way to do this, so I'm curious to find other possible approaches. Let me know what you think and if you have questions or ideas!