{"id":1363,"date":"2014-03-31T07:00:00","date_gmt":"2014-03-31T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/03\/31\/a-puzzle-involving-dynamic-programming-or-maybe-it-doesnt\/"},"modified":"2014-03-31T07:00:00","modified_gmt":"2014-03-31T07:00:00","slug":"a-puzzle-involving-dynamic-programming-or-maybe-it-doesnt","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20140331-00\/?p=1363","title":{"rendered":"A puzzle involving dynamic programming, or maybe it doesn't"},"content":{"rendered":"

\nHere’s a programming challenge:\n<\/p>\n

\n

\nEvaluate the following recurrence relation efficiently\nfor a given array\n\n[x<\/var>0<\/sub>, …, x<\/var>n<\/var>−1<\/sub>]\n<\/span>\nand integer\nk<\/var><\/span>.\n<\/p>\n\n\n= 3″><\/p>\n= 3″><\/p>\n
\n f<\/var> ([x<\/var>0<\/sub>, x<\/var>1<\/sub>], \n <\/td>\n\n k<\/var>) = <\/sub>\n <\/td>\n\n (x<\/var>0<\/sub> + x<\/var>1<\/sub>) \/ 2 \n <\/td>\n\n <\/td>\n\n <\/td>\n\n for all k<\/var>, n<\/var> = 2. <\/sub>\n <\/td>\n<\/tr>\n
\n f<\/var> ([x<\/var>0<\/sub>, …,\n x<\/var>n<\/var>−1<\/sub>], \n <\/td>\n\n k<\/var>) = <\/sub>\n <\/td>\n\n (x<\/var>0<\/sub> + x<\/var>n<\/var>−1<\/sub>) \/ 2 + \n <\/td>\n\n f<\/var> ([x<\/var>0<\/sub>, …, x<\/var>n<\/var>−2<\/sub>], k<\/var> + 1) \/ 2 + \n <\/td>\n\n f<\/var> ([x<\/var>1<\/sub>, …, x<\/var>n<\/var>−1<\/sub>], k<\/var> + 1) \/ 2 \n <\/td>\n\n for even k<\/var>, n<\/var> ≥ 3. <\/sub>\n <\/td>\n<\/tr>\n
\n f<\/var> ([x<\/var>0<\/sub>, …,\n x<\/var>n<\/var>−1<\/sub>], \n <\/td>\n\n k<\/var>) = <\/sub>\n <\/td>\n\n  \n <\/td>\n\n f<\/var> ([x<\/var>0<\/sub>, …, x<\/var>n<\/var>−2<\/sub>], k<\/var> + 1) \/ 2 + \n <\/td>\n\n f<\/var> ([x<\/var>1<\/sub>, …, x<\/var>n<\/var>−1<\/sub>], k<\/var> + 1) \/ 2 \n <\/td>\n\n for odd k<\/var>, n<\/var> ≥ 3. <\/sub>\n <\/td>\n<\/tr>\n<\/table>\n

\nHint: Use dynamic programming.\n<\/p>\n<\/blockquote>\n

\nIn words:\n<\/p>\n

    \n
  • If the array has only two elements, then the result is the average\n of the two elements.<\/p>\n
  • If the array has more than two elements, then\n then the result is the sum of the following:<\/p>\n
      \n
    • Half the value of the function evaluated on the array with the\n first<\/i> element deleted\n and the second parameter incremented by one.<\/p>\n
    • Half the value of the function evaluated on the array with the\n last<\/i> element deleted\n and the second parameter incremented by one.<\/p>\n
    • If the second parameter is even,\n then also add the average of the first and last elements\n of the original array.\n <\/ul>\n<\/ul>\n

      \nThe traditional approach with dynamic programming is to cache intermediate\nresults in anticipation that the values will be needed again later.\nThe naïve solution, therefore, would have a cache keyed by\nthe vector and\nk<\/var>.\n<\/p>\n

      \nMy habit when trying to solve these sorts of recurrence relations\nis to solve the first few low-valued cases by hand.\nThat gives me a better insight into the problem\nand may reveal some patterns or tricks.\n<\/p>\n\n\n\n\n\n
      \n f<\/var> ([x<\/var>0<\/sub>,\n x<\/var>1<\/sub>,\n x<\/var>2<\/sub>], k<\/var>even<\/sub>) \n <\/td>\n\n = (x<\/var>0<\/sub> + x<\/var>2<\/sub>) \/ 2 +\n f<\/var> ([x<\/var>0<\/sub>, x<\/var>1<\/sub>], k<\/var>even<\/sub> + 1) \/ 2 +\n f<\/var> ([x<\/var>1<\/sub>, x<\/var>2<\/sub>], k<\/var>even<\/sub> + 1) \/ 2\n <\/td>\n<\/tr>\n
       <\/td>\n\n = (x<\/var>0<\/sub> + x<\/var>2<\/sub>) \/ 2 +\n f<\/var> ([x<\/var>0<\/sub>, x<\/var>1<\/sub>], k<\/var>odd<\/sub>) \/ 2 +\n f<\/var> ([x<\/var>1<\/sub>, x<\/var>2<\/sub>], k<\/var>odd<\/sub>) \/ 2\n <\/td>\n<\/tr>\n
       <\/td>\n\n = (x<\/var>0<\/sub> + x<\/var>2<\/sub>) \/ 2 +\n (x<\/var>0<\/sub> + x<\/var>1<\/sub>) \/ 4 +\n (x<\/var>1<\/sub> + x<\/var>2<\/sub>) \/ 4\n <\/td>\n<\/tr>\n
       <\/td>\n\n = ¾x<\/var>0<\/sub> +\n ½x<\/var>1<\/sub> +\n ¾x<\/var>2<\/sub>\n <\/td>\n<\/tr>\n<\/table>\n

      \nEven just doing this one computation, we learned a lot.\n(Each of which can be proved by induction if you are new to this sort of\nthing, or which is evident by inspection if you’re handy with math.)\n<\/p>\n

      \nFirst observation:\nThe function is linear in the array elements.\nIn other words,\n<\/p>\n\n\n\n
      \n f<\/var> (x<\/b><\/var> + y<\/b><\/var>, \n <\/td>\n\n k<\/var>) \n <\/td>\n\n = \n <\/td>\n\n f<\/var> (x<\/b><\/var>, k<\/var>) +\n f<\/var> (y<\/b><\/var>, k<\/var>),\n <\/td>\n<\/tr>\n
      \n f<\/var> (a<\/var>x<\/b><\/var>, \n <\/td>\n\n k<\/var>) \n <\/td>\n\n = a<\/var>\n <\/td>\n\n f<\/var> (x<\/b><\/var>, k<\/var>).\n <\/td>\n<\/tr>\n<\/table>\n

      \nTo save space and improve readability, I’m using vector notation,\nwhere\nadding two vectors adds the elements componentwise,\nand multiplying a vector by a constant multiples each component.\nThe long-form version of the first of the above equations would be\n<\/p>\n\n\n
      \n f<\/var> ([x<\/var>0<\/sub> + y<\/var>0<\/sub>,\n …, x<\/var>n<\/var>−1<\/sub> +\n y<\/var>n<\/var>−1<\/sub>], k<\/var>) =\n f<\/var> ([x<\/var>0<\/sub>, …, x<\/var>n<\/var>−1<\/sub>], k<\/var>) +\n f<\/var> ([y<\/var>0<\/sub>, …, y<\/var>n<\/var>−1<\/sub>], k<\/var>)\n <\/td>\n<\/tr>\n<\/table>\n

      \nSince the result is a linear combination\nof the vector elements,\nwe can work just with the coefficients and save ourselves some\ntyping.\n(“Move to the dual space.”)\nFor notational convenience, we will write\n<\/p>\n\n\n
      \n ⟨a<\/var>0<\/sub>, …\n a<\/var>n<\/var>−1<\/sub>⟩ =\n a<\/var>0<\/sub> x<\/var>0<\/sub> +\n ⋯ +\n a<\/var>n<\/var>−1<\/sub> x<\/var>n<\/var>−1<\/sub>\n <\/td>\n<\/tr>\n<\/table>\n

      \nSecond observation:\nThe specific value of\nk<\/var> is not important.\nAll that matters is whether it is even or odd,\nand each time we recurse to the next level,\nthe parity flips.\nSo the second parameter is really just a boolean.\nThat greatly reduces the amount of stuff we need to cache,\nas well as increasing the likelihood of a cache hit.\n(The naïve version would not have realized that\nf<\/var> (x<\/b><\/var>, k<\/var>)<\/span>\ncan steal the cached result from\nf<\/var> (x<\/b><\/var>, k<\/var> + 2)<\/span>.)\n<\/p>\n

      \nOur previous hand computation can now be written as\n<\/p>\n\n\n\n\n\n
      \n f<\/var> ([x<\/var>0<\/sub>,\n x<\/var>1<\/sub>,\n x<\/var>2<\/sub>], even) \n <\/td>\n\n = ⟨&frac12, 0, ½⟩ +\n f<\/var> ([x<\/var>0<\/sub>, x<\/var>1<\/sub>], odd) \/ 2 +\n f<\/var> ([x<\/var>1<\/sub>, x<\/var>2<\/sub>], odd) \/ 2\n <\/td>\n<\/tr>\n
       <\/td>\n\n = ⟨½, 0, ½⟩ +\n ⟨½, ½, 0⟩ \/ 2 +\n ⟨0, ½, ½⟩ \/ 2\n <\/td>\n<\/tr>\n
       <\/td>\n\n = ⟨½, 0, ½⟩ +\n ⟨¼, ¼, 0⟩ +\n ⟨0, ¼, ¼⟩\n <\/td>\n<\/tr>\n
       <\/td>\n\n = ⟨¾, ½, ¾⟩\n <\/td>\n<\/tr>\n<\/table>\n

      \nNow that we are working with coefficients, we don’t need\nto deal with\nx<\/b><\/var> any more!\nAll that matters is the length of the vector.\nThis makes our recurrences much simpler:\n<\/p>\n\n\n\n\n
      \n f<\/var> (2, \n <\/td>\nk<\/var>) \n <\/td>\n\n = \n <\/td>\n\n ⟨½, ½⟩ \n <\/td>\n\n <\/td>\n\n <\/td>\n\n for all k<\/var>.\n <\/td>\n<\/tr>\n
      \n f<\/var> (n<\/var>, \n <\/td>\n\n even) \n <\/td>\n= \n <\/td>\n\n ⟨½, 0, …, 0, ½⟩ + \n <\/td>\n\n ⟨f<\/var> (n<\/var>−1, odd) \/ 2, 0⟩ + \n <\/td>\n\n ⟨0, f<\/var> (n<\/var>−1, odd) \/ 2⟩ \n <\/td>\n\n for n<\/var> ≥ 3.\n <\/td>\n<\/tr>\n
      \n f<\/var> (n<\/var>, \n <\/td>\n\n odd) \n <\/td>\n= \n <\/td>\n\n  \n <\/td>\n\n ⟨f<\/var> (n<\/var>−1, even) \/ 2, 0⟩ + \n <\/td>\n\n ⟨0, f<\/var> (n<\/var>−1, even) \/ 2⟩ \n <\/td>\n\n for n<\/var> ≥ 3.\n <\/td>\n<\/tr>\n<\/table>\n

      \nNow we can carry out a few more hand computations.\n<\/p>\n\n\n\n\n\n\n\n\n\n\n
      \n f<\/var> (3, odd) \n <\/td>\n\n =\n ⟨f<\/var> (2, even) \/ 2, 0⟩ +\n ⟨0, f<\/var> (2, even) \/ 2⟩\n <\/td>\n<\/tr>\n
       <\/td>\n\n =\n ⟨¼, ¼, 0⟩ +\n ⟨0, ¼, ¼⟩\n <\/td>\n<\/tr>\n
       <\/td>\n\n = ⟨¼, ½, ¼⟩\n <\/td>\n<\/tr>\n
      \n f<\/var> (4, even) \n <\/td>\n\n = ⟨½, 0, 0, ½⟩ +\n ⟨f<\/var> (3, odd) \/ 2, 0⟩ +\n ⟨0, f<\/var> (3, odd) \/ 2⟩\n <\/td>\n<\/tr>\n
       <\/td>\n\n = ⟨½, 0, 0, ½⟩ +\n ⟨⅛, ¼, ⅛, 0⟩ +\n ⟨0, ⅛, ¼, ⅛⟩\n <\/td>\n<\/tr>\n
       <\/td>\n\n = ⟨⅝, ⅜, ⅜, ⅝⟩\n <\/td>\n<\/tr>\n
      \n f<\/var> (4, odd) \n <\/td>\n\n =\n ⟨f<\/var> (3, even) \/ 2, 0⟩ +\n ⟨0, f<\/var> (3, even) \/ 2⟩\n <\/td>\n<\/tr>\n
       <\/td>\n\n =\n ⟨⅜, ¼, ⅜, 0⟩ +\n ⟨0, ⅜, ¼, ⅜⟩\n <\/td>\n<\/tr>\n
       <\/td>\n\n = ⟨⅜, ⅝, ⅝, ⅜⟩\n <\/td>\n<\/tr>\n<\/table>\n

      \nThe interesting thing to observe here is that the recursion\ndoes not branch.\nWhen we reduce the size of the vector by one element,\nthe recursive calls are basically identical.\nWe have to shift the coefficients differently in order\nto build up the results,\nbut the recursive call itself is unchanged.\nThis means that we need to perform only\nn<\/var>−2\nrecursive steps to compute\nf<\/var> (n<\/var>, k<\/var>)<\/span>.\n<\/p>\n

      \nOkay, now that we’ve studied the problem a bit,\nwe can write the code.\nI’ll write three versions of the function.\nThe first computes according to the recurrence relation\nas originally written.\nWe use this to verify our calculations.\n<\/p>\n

      \nfunction f1(x, k) {\n if (x.length == 2) {\n  return (x[0] + x[1]) \/ 2;\n }\n var term = 0;\n if (k % 2 == 0) {\n  term = (x[0] + x[x.length - 1]) \/ 2;\n }\n return term +\n        f1(x.slice(0,-1), k + 1) \/ 2 +\n        f1(x.slice(1), k + 1) \/ 2;\n}\nImmediate window:\nf1([1,2,3], 0)\n= 4.0\n<\/pre>\n
      \nOkay, that matches our hand calculations,\n¾·1 + ½·2 + ¾·3 = 4.\n<\/p>\n
      \nNow let’s do the straight recursive version.\n<\/p>\n
      \nfunction dotproduct(a, x)\n{\n var total = 0;\n for (var i = 0; i < a.length; i++) total += a[i] * x[i];\n return total;\n}\nfunction f2a(n, k)\n{\n if (n == 2) return [1\/2, 1\/2];\n var c = new Array(n);\n for (var i = 0; i < n; i++) c[i] = 0;\n if (k % 2 == 0) {\n  c[0] = 1\/2;\n  c[n-1] = 1\/2;\n }\n var inner = f2a(n-1, k+1);\n for (var i = 0; i < n - 1; i++) {\n  c[i] += inner[i] \/ 2;\n  c[i+1] += inner[i] \/ 2;\n }\n return c;\n}\nfunction f2(x, k)\n{\n return dotproduct(f2a(x.length, k), x);\n}\nImmediate window:\nf2([1,2,3], 0)\n= 4.0\n<\/pre>\n
      \nNotice that there is no dynamic programming involved.\nThe hint in the problem statement was a red herring!<\/b>\n<\/p>\n
      \nFinally, we can eliminate the recursion by iterating\nn<\/code> up from 2.\n<\/p>\n
      \nfunction f3(x, k)\n{\n var c = new Array(x.length);\n for (var i = 0; i < x.length; i++) c[i] = 0;\n c[0] = 1\/2;\n c[1] = 1\/2;\n for (var n = 3; n <= x.length; n++) {\n  var carry = 0;\n  for (var i = 0; i < n; i++) {\n   var nextcarry = c[i];\n   c[i] = (carry + c[i]) \/ 2;\n   carry = nextcarry;\n  }\n  if ((k + n + x.length) % 2 == 0) {\n   c[0] += 1\/2;\n   c[n-1] += 1\/2;\n  }\n }\n return dotproduct(c, x);\n}\n<\/pre>\n
      \nI pulled a sneaky trick here in the place we test whether\nwe are in the even or odd case.\nOfficially, the test should be\n<\/p>\n
      \n  if ((k + (x.length - n)) % 2 == 0) {\n<\/pre>\n
      \nbut since we are interested only in whether the result is\neven or odd,\nwe can just add the components together,\nbecause subtraction and addition have the same effect\non even-ness and odd-ness.\n(If I really felt like micro-optimizing,\nI could fold x.length<\/code> into k<\/code>.)\n<\/p>\n
      \nOkay, now that we have our code,\nlet’s interpret the original problem.\n<\/p>\n
      \nThe expression\n\n⟨f<\/var> (n<\/var>, k<\/var>) \/ 2, 0⟩ +\n⟨0, f<\/var> (n<\/var>, k<\/var>) \/ 2⟩<\/span>\ntakes the vector\n\nf<\/var> (n<\/var>, k<\/var>)<\/span>\nand averages it against a shifted copy of itself.\n(The word convolution<\/i> could be invoked here.)\nIf you think of the coefficients as describing the distribution\nof a chemical,\nthe expression calculates the effect of diffusion after one\ntime step according to the simple model\n“At each time step, each molecule has a 50% chance of moving\nto the left and a 50% chance of moving to the right.”\n(Since the length of the vector varies with\nn<\/var>,\nI’ll visualize the vector drawn with center-alignment.)\n<\/p>\n
      \nThe base case\n⟨½, ½⟩\ndescribes the initial conditions of the diffusion,\nwhere half of the chemicals are on the left and half are\non the right.\nThis is one time step after one unit of the chemical\nwas placed in the center.\nLet’s get rid of the extra term in the recurrence and focus\njust on the diffusion aspect:\n<\/p>\n\n\n= 3″><\/p>\n
      \n    d<\/var>(2) =\n    ⟨½, ½⟩ \n    <\/td>\n<\/tr>\n
      \n    d<\/var>(n<\/var>) =\n    ⟨d<\/var>(n<\/var>−1) \/ 2, 0⟩ +\n    ⟨0, d<\/var>(n<\/var>−1) \/ 2⟩ \n    <\/td>\n\n    for n<\/var> ≥ 3.\n    <\/td>\n<\/tr>\n<\/table>\n
      \nIf you compute these values, you’ll see that the results are\nawfully familiar.\nI’ve pulled out the common denominator to avoid the ugly fractions.\n<\/p>\n\n\n\n\n\n\n
      \n    1 1\n    <\/td>\n\n    entire row divided by 2\n    <\/td>\n<\/tr>\n
      \n    1 2 1\n    <\/td>\n\n    entire row divided by 4\n    <\/td>\n<\/tr>\n
      \n    1 3 3 1\n    <\/td>\n\n    entire row divided by 8\n    <\/td>\n<\/tr>\n
      \n    1 4 6 4 1\n    <\/td>\n\n    entire row divided by 16\n    <\/td>\n<\/tr>\n
      \n    1 5 10 10 5 1  \n    <\/td>\n\n    entire row divided by 32\n    <\/td>\n<\/tr>\n<\/table>\n
      \nYup, it’s Pascal’s Triangle.\n<\/p>\n
      \nNotice that the sum across the row equals the amount we are dividing by,\nso that the sum of the row is always 1.\n(This is easy to see from the recurrence relation, since the base\ncase establishes the property that the sum of the coordinates is 1,\nand the recurrence preserves it.)\n<\/p>\n
      \nThis means that\nwe can calculate the coefficients of\nd<\/var>(n<\/var>)\nfor any value of\nn<\/var> directly,\nwithout having to calculate any of coefficients for smaller values\nof\nn<\/var>.\nThe coefficients are just row\nn<\/var> of Pascal’s triangle,\n\nwhich we know how to compute in\nO<\/var>(n<\/var>)<\/a> time<\/a>.\n<\/p>\n
      \nNow we can also interpret the extra term we removed at the even steps.\nThat term of the recurrence\nsimulates adding a unit of chemical to the solution\nat every other time step,\nhalf a unit at the left edge and half at the right edge.\nAnd we can calculate these directly in the same way that\nwe calculated the diffusion coefficients,\nsince they basically are<\/i> the diffusion coefficients,\njust with a time and location adjustment.\n<\/p>\n
      \nI pulled a fast one here.\nMaybe you didn’t pick up on it:\nI’m assuming that the two parts of the recurrence\nunrelated to the diffusion behavior\n(the base condition and the extra term at the even steps)\nare independent and can simply be added together.\nYou can show this by noting that given the generalized recurrence\n<\/p>\n\n\n\n
      \n    f<\/var>G<\/var><\/sub>(2, k<\/var>)\n    = G<\/var>(2, k<\/var>)\n    <\/td>\n<\/tr>\n
      \n    f<\/var>G<\/var><\/sub>(n<\/var>, k<\/var>)\n    =\n    G<\/var>(n<\/var>, k<\/var>)\n    +\n    ⟨f<\/var>G<\/var><\/sub>(n<\/var>−1, k<\/var> + 1) \/ 2, 0⟩ +\n    ⟨0, f<\/var>G<\/var><\/sub>(n<\/var>−1, k<\/var> + 1) \/ 2⟩\n    for n<\/var> ≥ 3.\n    <\/td>\n<\/tr>\n<\/table>\n
      \nthen\n\nf<\/var>G<\/var>+H<\/var><\/sub>\n=\nf<\/var>G<\/var><\/sub> +\nf<\/var>H<\/var><\/sub><\/span>.\n(As before, induct on the recurrence relations.)\nTherefore, we can solve each of the pieces separately\nand just add the results together.\n<\/p>\n
      \nIf I had the time and inclination,\nI could work out the solution for\n<\/p>\n\n\n
      \nC<\/var>(n<\/var>, i<\/var>) +\nΣ<\/var><\/font>k<\/var> even, 2 < k<\/var> ≤ n<\/sub>\nC<\/var>(k<\/var>, i<\/var>) \/ 2k<\/var><\/sup>\n    <\/td>\n<\/tr>\n<\/table>\n
      \nor something similar to that.\nLike I said, I ran out of time and inclination.\nBut if I could come up with an efficient way to compute that\nvalue for all values of\ni<\/var>\nfor fixed\nn<\/var>\n(and I believe there is, I’m just too lazy to work it out),\nthen I would have an\nO<\/var>(n<\/var>)<\/a> solution\nto the original recurrence.\n<\/p>\n
      \n(Okay, so the “If I had the time” bit is a cop-out, but\nI sort of lost interest in the problem.)<\/p>\n","protected":false},"excerpt":{"rendered":"
      Here’s a programming challenge: Evaluate the following recurrence relation efficiently for a given array [x0, …, xn−1] and integer k. f ([x0, x1],  k) =  (x0 + x1) \/ 2  for all k, n = 2.  = 3″> f ([x0, …, xn−1],  k) =  (x0 + xn−1) \/ 2 +  f ([x0, …, xn−2], k + 1) \/ […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-1363","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
      Here’s a programming challenge: Evaluate the following recurrence relation efficiently for a given array [x0, …, xn−1] and integer k. f ([x0, x1],  k) =  (x0 + x1) \/ 2  for all k, n = 2.  = 3″> f ([x0, …, xn−1],  k) =  (x0 + xn−1) \/ 2 +  f ([x0, …, xn−2], k + 1) \/ […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1363","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=1363"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1363\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=1363"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=1363"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=1363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}