Skip to content

Instantly share code, notes, and snippets.

@hwayne
Last active July 21, 2021 17:09
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save hwayne/e5a65b48ab50a2285de47cfc11fc955f to your computer and use it in GitHub Desktop.
PBT / Example Testing comparison problem

You are writing simple budgeting softare. A Budget consists of a total limit, represented as a positive integer, and a dictionary of category limits, represented as a map from strings to integers. For example:

{
  "total_limit": 50,
  "category_limits": {
    "food": 10,
    "rent": 11,
    "candles": 49
  }
}

(You can assume that no category will have a higher limit than the total, but you don't have to enforce this.)

A Bill is an array of Items. Each Item has a cost (positive integer), an optional count (positive integer), and optional categories (array of strings). For example:

[
  {"cost": 5},
  {"cost": 1, "count": 3},
  {"cost": 2, "categories": ["food", "gym"]},
  {"cost": 1, "count": 2, "categories": ["transit"]}
]

The goal is to write can_afford(budget, bill). Affordability is calculated under the following rules:

  • The cost of every item is subtracted from total_limit.
  • If an item shares a category with the budget's category_limits, then price of that item is also subtracted from said category in addition to the total_limit.
  • The item might not share a category with the budget, or it might not have a category field at all. In both cases, no special rules apply.
  • If an item shares multiple categories with the budget, the cost is applied to only one category limit of your choice.
  • If an item has a count, the cost of the item is included count times. This applies to both total_limit and the category limits. If the count field is missing, you can assume a count of 1.
  • can_afford is true if, after all items are accounted for, total_limit and all category limits are non-negative. If the total_limit or any category limits are below 0, then can_afford is false.

can_afford should be as permissive as possible. The following is considered affordable:

can_afford(
  {"total": 5, "category_limits": {"a": 1, "b": 3}},
  [{"cost": 2, "categories": ["a", "b"]}]
)

While the sole item in the bill is greater than category_limits[a], it is less than category_limits[b], so the bill is affordable.

You do not need to use the same names for anything, or the same data layout, as long as the requirements are satisfied.


ROT13 spoilers:

Gur erdhverzragf ner vagragvbanyyl vapbzcyrgr. V jnag gb frr ubj qvssrerag grfgvat grpuavdhrf rkcbfr gur ubyrf va gur erdhverzragf.

Zvffvat erdhverzragf ner va ebg18:

  • ax lzwjw sjw esfq alwek sfv uslwygjawk, lzwjw sjw dglk gx osqk lg uzggkw ozauz alwek shhdq lg ozauz uslwygjq daealk. Wnwf ax gfdq gfw hgkkatdw kwl gx uzgauwk ewsfk lzw tadd ak sxxgjvstdw, lzw xmfulagf emkl jwlmjf ljmw.

  • ax sf alwe zsk tglz s ugmfl sfv kwnwjsd uslwygjawk, qgm usf shhdq lzw ugkl lg emdlahdw uslwygjawk afklwsv gx kmtljsulafy al sdd xjge bmkl gfw.

  • ax sf alwe kzsjwk s uslwygjq oalz lzw tmvywl tml zsk sf svvalagfsd uslwygjq fgl gf lzw tmvywl, qgm usffgl shhdq al lg lzw "eakkafy" uslwygjq. Qgm emkl shhdq al lg gfw gx lzw daealk.

@jlink
Copy link

jlink commented Apr 8, 2021

I started tackling the problem with a combination of examples and PBT: https://github.com/jlink/property-based-testing/blob/main/pbt-java/src/test/java/pbt/hwayne/can_afford.md. I'm not sure if that's interesting for anyone.

@marick
Copy link

marick commented Apr 8, 2021

My solution here: https://github.com/marick/hillel_budget Elixir. TDD.

I made lots of commits along the way, with comments about what I was doing at the different steps.

I wrote up the steps toward my solution: https://www.crustofcode.com/hillel-budget/

@jlink
Copy link

jlink commented Apr 16, 2021

I cannot decrypt the ROT18 parts. The web-based rot18 decoders spit out garbage.

@hp4k1h5
Copy link

hp4k1h5 commented Apr 21, 2021

I cannot decrypt the ROT18 parts. The web-based rot18 decoders spit out garbage.

they are encrypted with ROT8

@jlink
Copy link

jlink commented Apr 22, 2021

they are encrypted with ROT8

Reading and code breaking are not my strongest suits

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment