Alex Raichev

Jumping Jack

I'd like to present some solutions to the following puzzle that appeared as March 22, 2013 Programming Praxis puzzle.

Jack starts at 0 on the number line and jumps one unit in either direction. Each successive jump he makes is longer than the previous by 1 unit, and can be made in either direction. Design an algorithm that takes an integer n and returns a shortest sequence of jumps that Jack can perform to reach n along with the length of that sequence.

Algorithm 1

Brute-force. Perform a breadth-first search through the binary tree of all valid jump/integer summand sequences (0, -1, 1, -1 - 2, -1 + 2, 1 - 2, 1 + 2, ...) and stop when the target sum n is reached.

Algorithm 2

Brute-force with pruning. Label the nodes of the binary tree with their partial sums and order the nodes of so that the left child is less than the right child (0, -1, 1, -3, -1, -1, 3, ...). Notice that every pair of nodes at the same height with equal partial sums have equal subtrees. Notice also that every pair of nodes at the same height with partial sums of opposite sign have mirror image subtrees. Notice also that flipping the signs/turns of a path with partial sum s yields a path of the same length to -s. So in our breadth-first search, we don't need to search down a node at a given height if we've already discovered a node at the same height with the same magnitude partial sum.

Analyzing the worst-case time complexity of Algorithm 1 or Algorithm 2 requires knowing at what tree height the given number n is first discovered. If you can figure that out, then you probably discovered...

Algorithm 3

Smart-force. Find the least integer k such that t_k := 1 + 2 + 3 + ... + k >= |n| and t_k has the same parity (evenness/oddness) as |n|. Then flip the signs of the summands of t_k in a systematic way to total n.

Here are the details. Notice that t_k = k(k + 1)/2, a triangular number. Setting t_k = |n| and solving for k gives the ceiling of (-1 + sqrt(1 + 8 |n|))/2. So k equals the ceiling or 1 or 2 plus it, whichever of those three numbers has the same parity as n and is least. Here we're using the fact that the set {t, t + s, t + s + (s + 1)} of three consecutive triangular numbers contains both even and odd numbers for any positive integers t, s. (Simply check all four parity possibilities for t, s.)

To find a minimal length sum for n, first compute d := (t_k - n)/2. Because t_k >= |n| and t_k and n have the same parity, d lies in the set {0, 1, 2, ..., t_k}. Now repeatedly subtract: d = a_k (k) + r_k, r_k = a_{k-1} (k-1) + r_{k-1}, ..., r_2 = a_1 (1) + r_1, choosing each a_i maximally in {0, 1}. By the lemma below, r_1 = 0. So d = sum_{i=1}^k a_i i. Thus n = t_k - 2d = sum_{i=1}^k i - sum_{i=1}^k 2a_i i = sum_{i=1}^k (1 - 2a_i) i and 1 - 2a_i in {-1, 1}. So the sequence b_i := 1 - 2a_i is a path, and by the minimality of k, b_i is a minimal path.

Algorithm 3 example

Consider the target number n=12. According to Algorithm 3, the possibilities for k are 5, 6, 7. The corresponding values of t_k are 15, 21, and 28. Since 28 is the least of these with the same parity as n, we see that k=7. So d = (t_k - n)/2 = 8, which we write as 1 + 7 according to the algorithm. Thus a shortest path to 12 is -1 + 2 + 3 + 4 + 5 + 6 - 7.

I say a shortest path, because shortest paths aren't unique in general. For example, 1 + 2 -3 + 4 - 5 + 6 + 7 also works.

Algorithm 3 correctness

Lemma: Let A_k = {0, 1, 2, ..., t_k}. Then a number lies in A_k if and only if it can be expressed as a sum sum_{i=1}^k a_i i for some a_i in {0, 1}.

Proof: By induction on k. First, 0 = sum_{i=1}^0 1, the empty sum. Now suppose the result holds for all k - 1 >= 0 and let d in A_k. Repeatedly subtract: d = a_k (k) + r_k, r_k = a_{k-1} (k-1) + r_{k-1}, ..., choosing each a_i maximally in {0, 1} and stopping at the first r_j in A_j for some j < k. Then by the induction hypothesis, r_j = sum_{i=0}^j b_i i for some b_i in {0, 1}. Then d = r_j + sum_{i=j+1}^k a_k i, as desired. Conversely, a sum s := sum_{i=1}^k a_i i for a_i in {0, 1} satisfies 0 <= s <= sum_{i=1}^k i = t_k, and so s in A_k.

Algorithm 3 time complexity

Assuming that arithmetic operations are constant time, it takes O(1) time to compute k from n, and hence the length of a minimal path to n. Then it takes O(k) time to find a minimal length sum for d and O(k) time to use that sum to produce a minimal length sum for n. So O(k) = O(sqrt(n)) time all up.

Author: Alex Raichev
Date: 2013-03-28
Tags: algorithm, puzzle
Permalink, Comment

Hourly Wage

Suppose you work in New Zealand, would like to earn a given net weekly income (for 52 weeks per year) after income tax, and would like to work a given number of hours per week (for 47 weeks per year; NZ workers get 4 weeks annual leave plus roughly 1 week of public holidays). What gross hourly income must you earn?

To answer that question, i used the 1 April 2012 to 31 March 2013 NZ income tax rates for individuals, wrote this Python program, and used it with Sage to make this table:

The gross hourly incomes needed are displayed in the main body of the table in New Zealand dollars, rounded to the nearest dollar and excluding GST. For example, to earn $1200/week after tax, working 25 hours/week, you need to earn $68/hour before tax.

Author: Alex Raichev
Date: 2013-03-19
Permalink, Comment

Science and Python: retrospective of a (mostly) successful decade

youtube~F4rFuIb1Ie4

Video sourced from YouTube here.

Author: Alex Raichev
Date: 2013-02-27
Tags: video, Python, science
Permalink, Comment

Happiness Beyond Thought 2

An interview with Gary Weber, a self-reporter of persistent nonduality and participant in several neuroscience experiments regarding the brain's selfing network.

Watch it on Bloggingheads.tv

Author: Alex Raichev
Date: 2013-02-13
Tags: video, nonduality
Permalink, Comment

In Grave Danger of Falling Food

youtube~CjWaP0iQmWw

1989 documentary about Bill Mollison, cofounder of the permaculture movement.

Video sourced from YouTube here.

Author: Alex Raichev
Date: 2013-02-13
Tags: video, resilience
Permalink, Comment

Lies, Damned Lies, and Medical Science

"Much of what medical researchers conclude in their studies is misleading, exaggerated, or flat-out wrong. So why are doctors—to a striking extent—still drawing upon misinformation in their everyday practice? Dr. John Ioannidis has spent his career challenging his peers by exposing their bad science."

Read the full article on the Atlantic's website.

Author: Alex Raichev
Date: 2013-02-13
Tags: article
Permalink, Comment

Apricot Balls

Ingredients

  • 3/4 C raw cashews
  • 3/4 C raw almonds
  • 1/2 C pitted dates
  • 3/2 C dried apricots
  • dash salt
  • 1/4 C shredded coconut
  • 1 T grated orange zest
  • 3/2 T grated fresh ginger

Directions

  1. Blend all the ingredients except the ginger in a food processor until homogeneous.
  2. Blend in the ginger.
  3. Shape into balls.

Notes

Makes about 20 tablespoon-sized balls. C = cup, T = tablespoon.

Author: Alex Raichev
Date: 2012-12-29
Tags: recipe
Permalink, Comment

Lightning Captured at 7207 Images Per Second

youtube~qQ4At_ctuLk

Video sourced from YouTube here.

For commentary, see xkcd's what if.

Author: Alex Raichev
Date: 2012-12-08
Tags: video
Permalink, Comment

The Exponential Function

Dr. Albert Bartlett demonstrates that "the greatest shortcoming of the human race is our inability to understand the exponential function".

Watch it on Thought Maybe

Author: Alex Raichev
Date: 2012-12-08
Tags: video, collapse
Permalink, Comment

The Face Game

Douglas Harding argues that all the psychological games that people play arise from one basic game, which he calls the Face Game.

Author: Alex Raichev
Date: 2012-10-27
Tags: nonduality
Permalink, Comment


Why no comments? I used to do public comments but found that moderating and maintaining them took too much time in front of the computer, time better spent playing outdoors. So these days I only do private comments, that is, you can email me comments regarding a post by clicking the 'Comment' link at the bottom of the post.