Author Archives: thorehusfeldt

Orthogonal Vectors to Perl Regex

The Orthogonal Vectors problem is given two sets of d-dimensional 01-vectors to decide if there is an orthogonal pair: two vectors, one from each set, with zero dot product. Obviously, the problem can be decided in time O(n2d) by trying all pairs.

Here’s the a complete reduction from the Orthogonal Vectors problem to evaluation of Perl regular expressions.

chomp($_ = <STDIN>);
s/0/\\d/g;
tr/1 /0|/;
print !!(<STDIN> =~ /$_/)

This is fully functional Perl code. Save the script as ov.pl and run it. The process expects two lines on standard input, each describing a set of vectors (as 01-sequences, separated by space). The script returns “1” if and only if the two sets contain an orthogonal pair of vectors.

>perl ov.pl
1000 0100 0010 1001
1110 1101 1111 1100^D
1

This construction shows that matching an n-character string against an n-character regular expression requires quadratic time under the Strong Exponential Time Hypothesis. So, the obvious quadratic-time dynamic programming algorithm for regex matching is in some sense optimal.

As to the Perl code, the first line eats the trailing newline of standard input. The next two lines contain the main part of the reduction, replacing “0” by “\d” (any digit), “1” by “0”, and “ ” by “|” to build a regex. The last line of the code attempts to match the second line from standard input to the regex. Oh, the double exclamation points? They are a perlism to enforce Boolean context, so that the output is “1” (true) exactly if the regex matches. The reduction is so obviously linear that it hurts.

Tell me this isn’t cute.

The core of the construction underlies the celebrated recent results of Backus and Indyk, Bringmann and Künnemann, and Abboud et al. that show similar bounds for various string edit distances. This particular example is just very concrete version of the NFA-acceptance reduction that appears on Karl Bringmann and Sebastian Krinninger’s slides for an MPI course on Complexity Theory of Polynomial-Time Problems (Summer 2016), there attributed to Russell Impagliazzo. I find that reduction very teachable. The step from NFA acceptance to a concrete Perl script is minimal, but makes it even more concrete (executable code!).

  • Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams: Tight Hardness Results for LCS and Other Sequence Similarity Measures. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 59-78.
  • Arturs Backurs, Piotr Indyk: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. pp. 51-58.
  • Karl Bringmann, Marvin Künnemann: Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. pp. 79-97.

Hard Problems and How To Figure Them Out

Explained using only the ten hundred words people use most often.

What is a good way of figuring out a problem?

First: it must be so simple and clear that we can explain it to a computer. (Or a Human. That’s not so different.)

Second: it must be fast enough so that it is done before lunch. (Or before the sun burns out. that’s not so different.)

Since people started using computers, lots of people get paid to think about ways to figure out problems. that’s what i’m doing.  Today we understand that some problems are hard, and others are pretty easy.

I want to help us becoming better at talking about what makes a problem hard.

So far, most of the people who think about this stuff look only at the size of the problem.

But some of us feel that you can think more clearly about problems when you not only look at their size, but at some other things as well. Sometimes, this way of thinking even helps us to come up with better ways to figure out problems!

 

small1.png

small2.pngsmall3.png

Two other people and myself have come up with a way to finish the game for all five-letter words — as long as you are forced to visit only around ten words. Or maybe twenty. So we found out that the number of words all-in-all was not so important. instead, what makes the problem hard is how many you are forced to visit. We can even find the shortest such path!

small4.png

Read more here: Another man, myself, and a woman, ‘Shortest path through stuff you didn’t choose’, place where people who care about this kind of question meet each year (the name sounds like a soft drink),  year twenty-hundred and ten and two.


Appendix

The above is a summary of a poster I made for a research sharing day at ITU.

hard-problems-poster (draft) in pdf (designed for printing in A0)

I loathe poster sessions, partly because of the unclear concept of who the audience is, and mainly because the social interaction exhausts me.

But to motivate me I gave myself the challenge to design a poster in the style of  Randall Munroe’s Up-Goer Five: Use only the 1000 most used words of English, be concrete, whimsical, accessible, and informative. Munroe has since made a whole book in this style: Thing Explainer, which is quite lovely.

I did the whole thing in Omnigraffle Professional 5, which is hard pressed to handle a document with almost 6000 elements. Drawings are free-hand in Keynote (basically because I don’t have a good way of digitising my free-hand drawings — I am a competent artist, but Munroe’s style is sufficiently simple.) The font is xkcd-font from the iPython project, licensed under CCANC 3.0.

As a starting point I used a 2012 paper of Andreas, Nina, and myself that presents an efficient FPT-algorithm for shortest Steiner cycle. That’s as accessible a result as I have. The big drawing at the end shows a path from TEARS to SMILE passing through seven intervening emotions (WORRY, SPITE, etc.) This is a highly nontrivial result and a cute story that I’m insanely happy with, I haven’t found a good way of expressing this fact in only 1000 words.

Andreas Björklund, Thore Husfeldt, and Nina Taslaman, Shortest cycle through specified elements, Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA 2012),  January 17–19, 2012, Kyoto, Japan, SIAM, pages 1747-1753. [PDF].

Artificiell intelligens – ett hot mot mänskligheten?

Föredrag den 20 september 2016 i Sällskapet Heimdall, Malmö.

Föredrag den 28 februari 2017, arrangerad av Lund Sustainable Engineers and Code@LTH, 12.15–13.00, LTH, Lunds Universitet, E-huset, E:A (eller E:B).

480px-hal9000-svgSammanfattning: Nej.

Under föredraget hoppas jag att bl a kunna förklara hur olika former för artificiell intelligens fungerar – hur bygger man en schackdator och hur en pratbot, hur fungerar maskininlärning i motsättning till god, gammaldags symbolisk AI, hur fungerar maskinöversättning baserad på stora datamängder, vad är ett artificiellt neuronnät, etc.

Är några av dessa tekniker en bit på vägen till artificiell generell intelligens? Och hur ser en värld med artificiell superintelligens ut? Kan och bör vi skydda os? Hur?

Lite AI-historia blir det nog också, så både Ada Lovelace, Jon von Neumann och Alan Turing kommer at nämnas.

Perspektivet är algoritmteoretisk och kunskapsoptimistiskt.

Referenser:

  • Olle Häggström, Here Be Dragons – Science, Technology and the Future of Humanity, Oxford University Press, 2016. [Hos förlaget.] [På Olle Häggströms blog]
  •  Nick Boström, Superintelligence, Oxford University Press, 2014. [Hos förlaget]
  • David Deutsch, »Creative blocks«, Aeon Magazine, oktober 2012. [Onlineartikel]
  • »AI och existentiell risk«, samtal med Olle Häggström och Dag Wedelin (datavetenskap, Chalmers), 16 april 2016. [Online på UR Play]
  • Alan M. Turing, »Computing machinery and intelligence«, Mind 59:433–460, 1950.
  • Thore Husfeldt, »Monstret i Turings bibliotek«, Filosofisk tidskrift 36(4):44-53, 2015. [Engelsk översättning på min blogg]

Løsning til nr. 32

Løsning til min danske kryptokryds nr. 32

Definitioner er understregede.
* angiver omkastning, < angiver omvending.

Vandret

2 Retsforfølge og lede efter vrøvl igen. (7)
SAGSØGE. SØGE (=lede) efter GAS (vrøvl) retur (=igen)

7 Lyd fra endetarm i avlssvin. (4)
MIAV. Gemt i endetarMIAVlssvin

10 Anret sumak-arrangement fra vestafrikansk land. (10)
MAURETANSK. ANRETSUMAK*

11 To kilo i vinen gør beruset. (7)
DRUKKET. KK (to kilo) i DRUEN

13 Afsætning af glas går tilbage. (4)
SALG. GLAS<

14 Propagere for EU? Bed DR om skrivelse. (7)
UDBREDE. EUBEDDR*

15 Stagnation i Liechtenstein er tidsbegrænset. (6)
INTERTI. liechtensteINERTIdsbregrænset

16 Lige fra regnvejr til robåd. (4)
ENER. Hvert andet bogstav fra REGNVEJR

17 Svovl-ledning har forskinket hvad der blev afsat seks dage til. (9)
SKABELSEN. S(vovl) + KABEL + SEN

21 Vi pirater til søs, hvor offentlighed er uønsket. (9)
PIRATERI. VIPIRATER*

25 Storme fra gale aser. (4)
RASE. ASER*.

27 Skinger tuba afbryder stilhed uden at holde tempoet. (6)
RUBATO. TUBA* i (afbryder) RO (stilhed).

29 Gøre hastværk når man restaurerer voliere. (7)
OVERILE. VOLIERE*

30 Dyr fadæse leverer indhold. (4)
ÆSEL. fadÆSELeverer

31 Var fx Finland under den kolde krig et område med god akustik? (7)
LYDLAND. Kryptisk definition, indikeret ved “?”.

32 Besvær i knoglerne, de er slemt betændte! (10)
LEDSMERTER. DEERSLEMT*

33 Klokken er forkert. (4)
URET. Dobbelt definition.

34 Dekanen, efter omorganisation, er den, der genoptager sagen. (7)
ANKENDE. DEKANEN*.

Lodret

1 Gid prishop skaber en vred kunde, fx. (10)
HIDSIGPROP. GIDPRISHOP*

2 Svagt fra sangerinder fra sjællandsk akademi. (7)
SORANER. SOPRANER uden P (“svagt”).

3 At mule over magisk smykke. (6)
AMULET. ATMULE*.

4 Overførselsindkomst til husdyr i form af tørret frugt. (5)
SUKAT. SU + KAT.

5 Finde på nyt navn til agenda: køber flås. (7)
GENDØBE. aGENDa kØBEr flået (dvs. uden det yderste lag.)

6 Opret selvstændighedsbevægelse og Belgien griner. (7)
ETABLER. ETA + B + LER.

7 Malker forbløffende fisk. (6)
MAKREL. MALKER*

8 Medrivende og ophidsende tennis. (6)
INTENS. TENNIS*.

9 Gav kærtegn, omkring et sekund, men anstrengte sig. (5)
ASEDE. AEDE omkring S.

12 Dejlig forvirret om skingert horn er lavet stål, fx. (10)
JERNHOLDIG. DEJLIG* omkring HORN*

18 Hinduistisk princip om kulde og udstråling. (7)
KARISMA. KARMA om IS.

19 Lot vendte sig godt en halv meter omkring for at se øen. (7)
ATOLLEN. ALEN omkring LOT<

20 To gange en tønde efter aftale. (7)
ENTENTE. EN T(ønde) (to gange) E(efter)

22 Denise, efter et par øl, forbliver meget kølig. (6)
ISENDE. DENISE*

23 Vitser om Puccini, fx. (6)
VERIST. VITSER*.

24 Hård på den gamle måde, indeholder lille risiko. (6)
HASARD. HAARD omkring S (small)

26 Fiskerihavn erhverver delvist skaller. (5)
AVNER. fiskerihAVNERhverver

28 Syntes at nogen fortjente grundtemaets kerne. (5)
UNDTE. grUNDTEmaets.

Lyd fra endetarm i avlssvin (4)

no28

Mit fjerde forsøg på en dansk kryptisk krydsogtværs i den engelske »bjælkede« stil. Nogle nøgler er udmærkede, andre lidt kluntede.

Som PDF: no32.  Løsning til nr. 32

Vandret
2 Retsforfølge og lede efter vrøvl igen. (7)
7 Lyd fra endetarm i avlssvin. (4)
10 Anret sumak-arrangement fra vestafrikansk land. (10)
11 To kilo i vinen gør beruset. (7)
13 Afsætning af glas går tilbage. (4)
14 Propagere for EU? Bed DR om skrivelse. (7)
15 Stagnation i Liechtenstein er tidsbegrænset. (6)
16 Lige fra regnvejr til robåd. (4)
17 Svovl-ledning har forskinket hvad der blev afsat seks dage til. (9)
21 Vi pirater til søs, hvor offentlighed er uønsket. (9)
25 Storme fra gale aser. (4)
27 Skinger tuba afbryder stilhed uden at holde tempoet. (6)
29 Gøre hastværk når man restaurerer voliere. (7)
30 Dyr fadæse leverer indhold. (4)
31 Var fx Finland under den kolde krig et område med god akustik? (7)
32 Besvær i knoglerne, de er slemt betændte! (10)
33 Klokken er forkert. (4)
34 Dekanen, efter omorganisation, er den, der genoptager sagen. (7)

Lodret
1 Gid prishop skaber en vred kunde, fx. (10)
2 Svagt fra sangerinder fra sjællandsk akademi. (7)
3 At mule over magisk smykke. (6)
4 Overførselsindkomst til husdyr i form af tørret frugt. (5)
5 Finde på nyt navn til agenda: køber flås. (7)
6 Opret selvstændighedsbevægelse og Belgien griner. (7)
7 Malker forbløffende fisk. (6)
8 Medrivende og ophidsende tennis. (6)
9 Gav kærtegn, omkring et sekund, men anstrengte sig. (5)
12 Dejlig forvirret om skingert horn er lavet stål, fx. (10)
18 Hinduistisk princip om kulde og udstråling. (7)
19 Lot vendte sig godt en halv meter omkring for at se øen. (7)
20 To gange en tønde efter aftale. (7)
22 Denise, efter et par øl, forbliver meget kølig. (6)
23 Vitser om Puccini, fx. (6)
24 Hård på den gamle måde, indeholder lille risiko. (6)
26 Fiskerihavn erhverver delvist skaller. (5)
28 Syntes at nogen fortjente grundtemaets kerne. (5)

English statistician is positive to a degree (5)

The occasion of this cryptic crossword was the workshop Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms (Nov. 2 – Nov. 6, 2015, Simons Institute for the Theory of Computing, Berkeley, California, United States) that I had the pleasure of co-organising.

The grid is a bit more difficult than usual, with several entries less than 50% checked, and two 15-letter words. Some of the clues (and jokes) make little sense if you’re not the in target group of theoretical computer scientists.

no33

Across

9 School on a graph isomorphism base. (9)
10 Who does the grading in Greek? (5)
11 Maybe a forest is better. (7)
12 Bizarre airlines ignoring N. Alon, say. (7)
13 Indian author of assumption about finding 14 across fast. (4)
14 Idiot workers take gin cocktail to first job. (10)
16 They fight to restore Rosamond’s section. (7)
17 Matrix transform vanishes when v → 0. (7)
19 Circuit complexity, typically, sounds like a religious habit (10)
22 Father of parameterised and polynomial-space algorithms, originally. (4)
24 Two-player game about encrypted mail token. (7)
25 Free variable turns leading proof assistant around. (7)
26 Additional seconds of Keynote experiments stymie brilliant talk. (5)
27 Compute |A ∪ B| as |A| + |B| like Dracula’s former girlfriend? (9)

Down

1 Maybe 20 down is a hammer made of carbon fibre? (9,6)
2 Beethoven wrote one functor in homological algebra; maybe addition. (8)
3 English statistician is positive to a degree. (5)
4 Introduces P.I.T. problem in linearly independent sets. (8)
5 Family of degree |C|. (6)
6 Tree decompostion of Sat is near. (4,5)
7 Letters from Nerode let Erdös blank out. (6)
8 Laugh at an optimal hint solving a problem. (11,4)
15 Maybe a2 + b2 + c2 challenge keeps Naor up. (9)
17 Optimal scheduler spent day and performed many tasks. (8)
18 Where identity is unique, altogether. (2,1,5)
20 More than 64 kilobyte Nintendo retro characters. (6)
21 Neglected flow algorithm starts confusingly. (6)
23 Threaten unruly spy with hierarchy. (5)

Annotated solution

Secret Sartre


(Trigger warning: this is satire intended to lampoon the two cultures currently dividing academic politics. It is also a fully playable social deduction game in the tradition of Werewolf, Mafia, The Resistance, and Avalon. In fact, Secret Sartre is a straighforward re-theming of the upcoming game Secret Hitler by Max Temkin (2016). Re-theming is a euphemism for theft, but no infringement of intellectual property is intended. Since this satire is about postmodernsim, intent is all that matters. The print-and-play edition of the original, including the rules, is available on-line; Secret Hitler is an extremely well-designed game with brilliant mechanics and a splendid theme.)

LogoSecret Sartre

In Secret Sartre, the faculty members of an unnamed university department battle for ideological supremacy. A fragile alliance of upstanding rationalists, logical positivists, empiricists, liberal humanists, scientists and other fetishizers of the Enlightenment must work together to stem the rising tide of postmodernism. Watch out, though – there are closet postmodernists among you, and someone is Secret Sartre.

Overview

At the beginning of the game, each player is secretly assigned to one of three roles: Science, Postmodernism, or Sartre. Sartre plays for the postmodern team, and the postmodernists know who Sartre is, but most of the time Sartre does not know who his fellow postmodernists are. The Scientists are far out on the autism spectrum and don’t know who anyone is.

The scientists win by enacting five rational policies or having Sartre fired. The postmodernists win by enacting six postmodernist policies, or if Sartre is elected Head of Studies late in the game. As postmodernist policies are enacted, the Department Chair gains new powers. Even scientists may find themselves tempted to enact postmodernist policies that help them control the table and fire their enemies. At the same time, the postmodernists conspire to construct a shared narrative space in which the social construction of their allegiance becomes the perceived Truth. Language is a weapon!

Set Up

Give each player a pair of cards, one identity and one allegiance. Both of these cards are secret and may never be shown to any other player, except (i) if Sartre is fired he immediately reveals it, ending the game in victory for the scientists, or (ii) if the Department Head investigates the loyality of a faculty member enacting the Diversity Training postmodern policy.

The composition of faculty is given by the following table:

Players 5 6 7 8 9 10
Science 3 4 4 5 5 6
Po-mo 1+S 1+S 2+S 2+S 3+S 3+S

Here are the faculty members’s identities. Except for Sartre, none of the names have any bearing on the game.
Identities.png
You also need an allegience card for each player. This is the cards that you show when you’re under ideological investigation from the Department Chair. You need 4 po-mo cards (for Derrida, Foucault, Rorty, and Sartre), and 6 science cards (for the rest).

Allegience.png

Put each pair of cards in a separate envelope, shuffle, and deal.

Each player looks at their identities, making sure that nobody else sees it. The player with the highest academic degree in real life is the first Department Chair candidate. If several players hold the same degree, spend some time discussing the merits of the degree-granting institutions, possibly using a recent ranking of universities. If this does not resolve the issue, another player with an MBA can break the tie using the player’s h-index.

The Department Chair candidate now enacts the following ritual. For 5–10 players:

Everybody close your eyes. Postmodernist and Sartre, open your eyes and acknowledge each other. [Take a long pause.] Everyone close your eyes. Everyone can open your eyes. If anyone is confused or something went wrong, please tell the group now.

For 7–10 players:

Everybody close your eyes and extend your hand into a fist in front of you. Sartre, keep your eyes closed but put your thumb out into a thumbs-up gesture. All postmodernists who are not Sartre, open your eyes and acknowledge each other. Postmodernists, take note of who has extended their thumb – that player is Sartre. Think about the relationship between the signifier and the signified. [Take a long pause] Everyone close your eyes and put your hands down. Everyone can open your eyes. If anyone is confused or something went wrong, please tell the group now.

Game play

Secret Sartre is played in rounds. Each round has an Election of new faculty leardership, a Faculty Meeting to enact a new policy, and an Executive Action where the Department Chair exercises his or her power.

Election

Each round, faculty members elect a new Department Chair and Head of Studies. These are shown as two placards (cut them out and fold as shown.)

Placards

  1. At the beginning of a new round, the Department Chair placard moves clockwise to the next player. This player is the new Department Chair candidate.
  2. The Department Chair candidate chooses a Head of Studies candidate by passing the Head of Studies placard to any other eligible player. (The two players who enacted the last policy are not eligible. In a five-player game, only the last active Head of Studies is not eligible.)
  3. Once the Department Chair candidate has chosen a Head of Studies candidate, all players (including the candidates) votes on the proposed government. You need some kind of ballot card for this for each player, such as a white and black stones form some other game, matchsticks, or the Ja! and Nein! cards from the original Secret Hitler. Players indicate readiness to vote by extending their chosen ballot card in front of them (or holding a coloured stone in a fist); discussion continues until every player is read to vote. Once every player is ready to vote, reveal your votes simultaneously so that everyone can see how you voted.

If more than 50% of the group votes yes, the candidates become Department Chair and Head of Studies, respectively. If three or more postmodernist policies have already been enacted, ask the new Head of Studies if he is Sartre; if he is Sartre, he must reveal himself and the game immediately ends in a postmodernist victory. Otherwise, proceed to the Faculty Meeting.

If the vote is a tie, or if most players vote no, the Department Chair placard moves clockwise to the next player and the election tracker is advanced by one election. (The election tracker is at the bottom of the Science policy board, see below. Use a coin or something similar.)

Student Reps

If faculty rejects three proposals in a row, the student representatives take matters into their own hands. Student policies are completely random: Reveal the policy on top of the Policy Draw Deck and enact it. Any power granted by this policy is ignored, but all players become eligible for Head of Studies for the next Election. Reset the Election Tracker after a policy is enacted by the populace or a government is successfully elected.

Faculty Meeting

You need 6 rational policy cards and 11 postmodernist policy cards. These are shuffled and placed face-down as the Policy deck.

Policies

The Department Chair draws the top three cards from the Policy deck,
looks at them in secret, and discards one Policy face down into the discard pile. The Chair passes the remaining two cards to the Head of Studies who looks in secret, discards one Policy card face down, and enacts the remaining Policy card by placing it face up on the corresponding track.

This is the track for the scientist’s policies:

Science policies

None of these policies has any effects on game play or real life, their role is only to mantain the status quo of male white dominance of Academia (includig Marie Curie as a token woman). The scientists win after enacting the fifth rational policy.

Depending on the number of players, one of three boards is used for postmodernist policies:

pomo-policies

 

Postmodern policies may have effects on game play, see below.
The sanctity of the faculty meeting is of the utmost importance! Once it begins with the Head drawing three Policy cards, faculty members stay silent until a policy has been enacted. Discarded policy cards may never be revealed; you must rely on the word of faculty leadership, who are allowed to lie.
If there are fewer than three cards remaining in the Policy deck at the end of a legislative session, shuffle them with the discard pile to create a new Policy deck. Unused policies should never be revealed, nor may they simply placed on top of the new Policy deck. If the government enacts a rational policy or a postmodernist policy that grants no power, begin a new round with a new Election. If the government enacts a postmodernist policy that grants power to the Department Chair, proceed to the Executive Action.

Executive Action

Whether by fate or choice, the faculty meeting may have adopted a postmodernist policy, moving the department away from excessive reductionism and granting the Deparmental Chair new powers to enforce collectivist fidelity. The Departmental Chair must enact the power granted in this round. Look at the Postmodernism policy track to determine which power, if any, has been granted.

  1. Diversity/harassment Training. The Department Chair investigates another player who has not yet been investigated by saying “I suggest [player name] be sent to a mandatory diversity/harassment training seminar”. The purpose of such a seminar is to ascertain the player’s ideological fidelity. That player passes his Allegiance Card (not his Identity!) to the Department Chair who checks that player’s allegiance in secret and then returns the card to the player. The Department Chair may share (or lie about!) the results of his investigation at his discretion, but may not show the card.
  2. Affirmative Action. The Department Chair chooses any other player at the table to be the next Department Chair candidate by passing that player the Department Chair placard. That player nominates a Head of Studies and the election proceeds as usual. After an Affirmative Action, the Departmental Chair returns to its original order.
  3. Adapt new Values Statement. The Department Chair secretly looks at the top three cards in the Policy deck and then returns them to the top of the deck without changing the order.
  4. Smear Campaign. The President fires one player at the table by saying “I fire [player name] because of [unreasonable charge of the player’s choice, excluding lack of academic excellence].” If that player is Sartre, he reveals his Identity Card and the game ends in a victory for the scientist. If the executed player is not Sartre he does not reveal his role or his loyalty. He is removed from the game and may not speak, vote, or run for office.
  5. Veto Power. After five postmodernist policies have been enacted, rational discourse among faculty members has been silenced, and departmental leadership gains much broader power over which policies are enacted. The Departmental Chair draws three policies, discards one, and passes the remaining two to the Head of Studies as usual. The Head of Studies may, instead of enacting either policy, say “This policy disadvantages [underprivileged group of player’s own choice, but not white males or Jews].” If the Departmental Chair consents, both policies are discarded and the Presidency placard passes to the left as usual. If the Departmental Chair does not consent, the Head of Studies must enact one of the two policies handed to him. Each use of the veto power represents an inactive leadership and advances the election tracker by one.

Løsning til nr. 31

Løsning til kryptokryds nr. 31.

Vandret

2 Småfed kvinde, travlt besat.
KVABSET (=småfed)
Ordspil: KV (fork. for kvinde), anagram (travlt) av BESAT

7 Drej knækket krus. (4)
SKRU (= drej)
Ordspil: anagram (drej) af KRUS

10 Tilpasning af dato: Patina ændres. (10)
ADAPTATION ( = tilpasning)
Ordspil: anagram (ændring) af DATOPATINA

11 Anarkistisk junta tilbageholder strøm d. 24. december. (7)
JULENAT (= d. 24. december)
Ordspil: Anagram (anarkistisk) af JUNTA  omkring LE (strøm “el”, omvendt)

13 Atter skjult i lykkelig ensomhed. (4)
IGEN (= atter)
Ordspil: Skjult i lykkelIGENsomhed

14 Ungt rådyr går frem og tilbage efter plante. (7)
KIDDIKE (en plante i korsblomstfamiljen)
Ordspil: KID (ungt rådyr) + DIK (KID baglæns, ordet “går frem og tilbage”) + E (“efter”)

15 Nu ses vrede efter Cæsars første folketælling. (6)
CENSUS (= folketælling)
C (Cæsars første bogstaf) + anagram (vrede) af NU SES

16 Eremit vaskede spejlet. (4)
ENER (= eremit)
Ordspil: RENE (= vaskede, adj.) baglæns

17 Omorganiseret natolager bruges til kommunikation. (9)
TALEORGAN (bruges til kommunikation)
Anagram (omorganiseret) af NATOLAGER

21 Oprørt generer de dem, der bestemmer. (9)
REGERENDE (= dem, der bestemmer)
Anagram af (oprørt) GENERER DE

25 En klovn tilbage til landet. (4)
IRAN (et land)
I (en) + NAR (= klovn) baglæns

27 Handles kort efter dyrket mark. (6)
AGERES ( = handles)
AGER (dyrket mark) + ES (et kort)

29 Betragt i fuglekæbe en del af skelettet. (7)
NÆSEBEN (del af skelettet)
SE (betragt) indeholdt i NÆB (fuglekæbe) + EN

30 Hvor man kan mødes omkring sagnvæsen. (4)
CAFE (hvor man kan mødes)
CA (omkring) + FE (et sagnvæsen)

31 Hvad siger det lille lam i skrift til europæer. (7)
RUMÆNER (europæer)
MÆ (hvad det lille lam siger) i RUNER (skrift)

32 Omdanne sær, opdyrket jordart. (10)
MORÆNESAND (jordart)
Anagram (opdyrket) af OMDANNESÆR

33 Angrib rent ud. (4)
ENTR (angrib)
Anagram (ud) af RENT

34 Tømt glas for hastig dukkert. (7)
DRUKKET (tømt glas)
Anagram (hastig) af DUKKERT

Lodret

1 Afvisning af smykke efter skaldyr på tog. (10)
REJICERING (= afvisning)
RING (smykke) efter IC (tog) i REJE (skaldyr)

2 Tænk nu gedens indvolde klemte. (7)
KNUGEDE (=klemte)
Indeholdt (“indvolde” af) tænKNUGEDEn

3 Slagmarken tabes i begyndelsen passivt. (6)
VALENT (= passiv)
VALEN (asernes slagmark) + T (første bogstav af “tabes”)

4 Fx zulu, beta, alfa, november, tango, uniform. (5)
BANTU (en gruppe af sprog som indeholder zulu)
B + A + N + T + U (ifølge i det internationale flyveralfabet)

5 Måske Gråbøl returnerer en frokost. (7)
ETTIDEN (frokost)
DITTE (Gråbøl) bagfra (“returnerer”) + EN

6 Julemad i kristendommen fx, den sidder fast i munden. (7)
TANDROD (sidder fast i munden)
AND (julemad) i TRO (kristendommen, fx) + D (den, fork.)

7 Station lever af større byer. (6)
STÆDER (større byer)
ST (station, fork.) + ÆDER (= lever af)

8 Se rundt om min horisont. (6)
KIMING (= horisont)
KIG (= se) omkring MIN

9 Flytte bruskfisk. (5)
ROKKE (= flytte) (en bruskfisk)

12 Åbner udstilling: Firserne er misforstået. (10)
FERNISERER = åbner udstilling
Anagram (misforstået) af FIRSERNE ER

18 Bredt stykke stof gør din barm gyngende. (7)
ARMBIND (bredt stykke stof)
Anagram (gyngende) af DINBARM

19 Organ findes og yder. (7)
LEVERER (= yder)
LEVER (organ) + ER (findes)

20 Lincoln, mellem venner, pruttede til vildt gilde. (7)
ABEFEST (vildt gilde)
ABE (Abraham Lincoln) + FES (pruttede) + T (til, fork.)

22 Gammelt ømtåleligt helium fx. (6)
GASART (helium, fx)
GA (gammelt, fork.) + SART (= ømtåleligt)

23 Bære en rådden frugt. (6)
ENEBÆR (frugt)
Anagram (rådden) af BÆRE EN

24 Promovere dansk kulturradikal uden ende. (6)
BRANDE (= promovere)
(Georg) BRANDES (dansk kulturradikal) uden sidste bogstav

26 Fornuft er mærkelig baglæns på engelsk. (5)
RÆSON (= fornuft)
SÆR (= mærkelig) baglæns + ON (på, engelsk)

28 Mesterskaber i vanvid i soveværelse fx. (5)
GEMAK (soveværelse, fx)
EM (mesterskaber) i GAK (vanvid)

Fx zulu, beta, alfa, november, tango, uniform. (5)

no28

Mit tredje forsøg på en dansk kryptisk krydsogtværs i den engelske »bjælkede« stil, som man kan finde hos Guardians Azed eller Times’ Listener.

Jeg finder det fortsat uhyre svært at komponere naturlige kryptiske nøgler på dansk, og resultatets kvalitet er langt under, hvad man kan finde en en almindelig engelsk avis.

Jeg prøver stadig at holde mig inden for de etablerede engelske regler, som nedfældet af mesteren Ximenes (What are Ximenean clues?).

Ikke mindst har jeg forsøgt at være nogenlunde stringent med at indikere definition ved eksempel. Hvis jeg fx vil beskrive HUND kan jeg gøre det ganske ligefremt ved en kategori (»Husdyr (4)«). Men hvis jeg vil indikere HUND ved at angive et eksempel, så skal jeg indikere det med »fx« eller »måske« eller lignende. Jeg kan altså skrive »Måske en schæfer (4)« eller »Lassie, fx (4)« men ikke bare »Grand Danois (4)«. Jeg finder selv, at de resulterende nøgler virker ganske kluntede i forhold til de tilsvarende engelske konstruktioner, men i første omgang bestræber jeg mig på at sætte så enkle kryptiske kryds og tværser som muligt, så æstetik og elegance må forblive underordnet indtil jeg bliver dygtigere.

Jeg har brugt samme gitter som til nummer 28.

PDF-udgave: no31. Løsning.

Vandret
2 Småfed kvinde, travlt besat. (7)
7 Drej knækket krus. (4)
10 Tilpasning af dato: Patina ændres. (10)
11 Anarkistisk junta tilbageholder strøm d. 24. december. (7)
13 Atter skjult i lykkelig ensomhed. (4)
14 Ungt rådyr går frem og tilbage efter plante. (7)
15 Nu ses vrede efter Cæsars første folketælling. (6)
16 Eremit vaskede spejlet. (4)
17 Omorganiseret natolager bruges til kommunikation. (9)
21 Oprørt generer de dem, der bestemmer. (9)
25 En klovn tilbage til landet. (4)
27 Handles kort efter dyrket mark. (6)
29 Betragt i fuglekæbe en del af skelettet. (7)
30 Hvor man kan mødes omkring sagnvæsen. (4)
31 Hvad siger det lille lam i skrift til europæer. (7)
32 Omdanne sær, opdyrket jordart. (10)
33 Angrib rent ud. (4)
34 Tømt glas for hastig dukkert. (7)

Lodret
1 Afvisning af smykke efter skaldyr på tog. (10)
2 Tænk nu gedens indvolde klemte. (7)
3 Slagmarken tabes i begyndelsen passivt. (6)
4 Fx zulu, beta, alfa, november, tango, uniform. (5)
5 Måske Gråbøl returnerer en frokost. (7)
6 Julemad i kristendommen fx, den sidder fast i munden. (7)
7 Station lever af større byer. (6)
8 Se rundt om min horisont. (6)
9 Flytte bruskfisk. (5)
12 Åbner udstilling: Firserne er misforstået. (10)
18 Bredt stykke stof gør din barm gyngende. (7)
19 Organ findes og yder. (7)
20 Lincoln, mellem venner, pruttede til vildt gilde. (7)
22 Gammelt ømtåleligt helium fx. (6)
23 Bære en rådden frugt. (6)
24 Promovere dansk kulturradikal uden ende. (6)
26 Fornuft er mærkelig baglæns på engelsk. (5)
28 Mesterskaber i vanvid i soveværelse fx. (5)

Hearthstone Algorithms Design Exercises

Exam time again. I’ve tried to produce exam questions for my current algorithms design class themed after Blizzard’s collectible card game Hearthstone. For a variety of reasons I decided to abandon the idea for the exam, but the ideas are cute enough for a blog post. Here are the first three. The target audience are algorithms design students struggling with Chapters 1–8 of Kleinberg and Tardos’s Algorithms Design book (so: graph traversal, greedy, divide and conquer, dynamic programming, network flow, NP-hardness). Enjoy!

Hearthstone Basics

Each card in the game Hearthstone depicts a minion. Each minion has 3 values: Attack, Health and Cost, given as integers a, h, and c. Here’s a minion with Attack 3, Health 2, and Cost 4:

xMBCWkKf

For the purpose of these exercises, these values are unbounded, positive integers. During the game, both players have a number of minions in play. In a turn of Heartstone, the player assigns his minions to fight enemy minions. Each minion gets to target a single enemy minion, initiating a fight between the two minions. When a minion with Attack A fights a minion with Health H, the other minion’s Health is reduced to max{0,H-A}. Note that both minions fight, and each deals damage to the other, regardless of who initiated the fight. Also note that an enemy minion can be involved in many fights each turn, when it is repeatedly targeted. When a minion’s Health is reduced to 0, it is removed from play.

For each of the problems below, state which algorithmic design technique should be used, or if the problem is NP-hard. Also give the best asymptotic worst-case running time.

Cleanup

You and ZombieMage02 both have the same number of minions in play. It is your turn. Can you take them all the enemy minions in one sweep?

Input:
The enemy minions (a1,h1),…,(an,hn) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2

Output: “Yes,” if your minions can take out all enemy minions this turn. “No,” otherwise.

Tanks

TwoOrcsOneCup has two minions in play. Both completely overpowered and powerful enough to wipe out your hero when it becomes TwoOrcsOneCup’s turn again. You have n minions in play. Can you take out both minions this turn?

EPfTXn7N FmSMUX1Z

Input: The enemy minions (a1,h1),(a2,h2) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2

Output: “Yes” if your minions can take out both enemy minions this turn.

Charge!

Showdown time. Your hero has almost no Health left and OprahWindfury’s mage keeps pummeling you with fireballs. This has been going on for hours—time to end this! Luckily your hand is full of high-powered cards with Charge, which can attack immediately.
Get out as many of these guys as you can afford!

Input Your available mana K. The minions with Charge on your hand, (a1,h1,c1),…,(an,hn,cn) ∈ N2.

Output: The total number of Attack points you can play this round.


Cards generated using achievementgen.com