15
\$\begingroup\$

Futoshiki is a logic puzzle where an \$n×n\$ Latin square must be completed based on given numbers and inequalities between adjacent cells. Each row and column must contain exactly one of each number from \$1\$ to \$n\$ while satisfying the inequalities.

In a solved Futoshiki puzzle any row (or column) forms a linear extension of the poset induced by that row's inequalities. Counting linear extensions of posets of this kind is a polynomial-time problem, as opposed to #P-complete for the general case.

Given the sequence of \$n\ge0\$ symbols between cells of an initially empty Futoshiki row of length \$n+1\$, each of which is one of \$<\$, \$>\$ or \$-\$ (nothing; no constraint), output the number of solutions of that row when considered in isolation. You may use any three distinct symbols for \$<,>,-\$, but your program must pass all test cases below in reasonable time.

This is ; fewest bytes wins.

Test cases

"" -> 1
">" -> 1
"<" -> 1
"-" -> 2
"<>" -> 2
">-" -> 3
"><>" -> 5
"---" -> 24
">->>" -> 10
"><><>" -> 61
"->->-<<>" -> 11340
">-<><--<>><" -> 4573800
"><>><><<<>><>" -> 26260625
">><<>><<>><<>>" -> 120686411
\$\endgroup\$
5
  • 1
    \$\begingroup\$ This is a good challenge but the time requirement is unfortunate. It's easy to miss because it's mentioned once inline and there's no restricted-time tag. And "reasonable time" is vague. The largest output of ~120 million isn't so big as to definitively rule out exponential-time solutions. My brute-force Python code that branches on all options but stops on a violation takes 25 minutes on my machine -- is that a reasonable time? Other languages and machine are likely faster. If efficiency is important to the challenge, bigger test cases or restricted-complexity could have helped. \$\endgroup\$
    – xnor
    Sep 30, 2022 at 22:47
  • \$\begingroup\$ Some of the test cases look like fish. Someone answer in ><> \$\endgroup\$
    – naffetS
    Sep 30, 2022 at 22:50
  • \$\begingroup\$ @xnor done.\${}{}\$ \$\endgroup\$ Oct 1, 2022 at 4:17
  • 1
    \$\begingroup\$ @ParclyTaxel Sorry, I wasn't actually suggesting you change it now given that there's answers relying on it, just so you know for future challenges. \$\endgroup\$
    – xnor
    Oct 1, 2022 at 4:57
  • \$\begingroup\$ @xnor Don't worry. I merely saw the sandbox proposal having 4 upvotes and decided to post it as it was at a most opportune time. :) \$\endgroup\$ Oct 1, 2022 at 4:59

10 Answers 10

4
\$\begingroup\$

Wolfram Language (Mathematica), 84 bytes

t["-"<>#<>"-"]&
t@s_:=t@s=Tr[t/@StringReplaceList[s,"->"|"<>"|"<-"|"--"->"-"]]~Max~1

Try it online!

A fast solution using memoization. Finishes all test cases in a second.

Without memoization (t@s=) it would save 4 bytes, and the last three testcases would take 42 seconds, 4 minutes and 20 minutes respectively on my computer.


Wolfram Language (Mathematica), 58 bytes

Count[Sign@*Differences/@Permutations@Range[0,Tr[1^#]],#]&

Try it online!

Brute force. Cannot pass the last three testcases in reasonable time.

Takes input as a list, where >, <, - are represented by 1, -1, _ respectively.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6),  110  98 bytes

f=(s,m=t=0,j,p)=>s[~~j]?[...s,0].map((_,v)=>m>>++v&1|p*!eval(p+s[j]+v)||f(s,m|1<<v,j+1|0,v))|t:++t

Try it online!

Commented

f = (              // f is a recursive function taking:
  s,               //   s = input string of length N
  m =              //   m = bitmask of already used numbers
  t = 0,           //   t = number of solutions
  j,               //   j = pointer in s, initially undefined
  p                //   p = previous number in the permutation
) =>               //
s[~~j] ?           // if there's still something to process:
  [...s, 0]        //   create an array of length N + 1
  .map((_, v) =>   //   for each value at position v in there:
    m >> ++v & 1 | //     increment v; abort if v was already used
    p * !eval(     //     or p is defined and
      p + s[j] + v //       the expression p + s[j] + v
    ) ||           //     is falsy once evaluated as JS code
    f(             //     otherwise, do a recursive call:
      s,           //       pass s unchanged
      m | 1 << v,  //       update m to mark v as used
      j + 1        //       increment j
      | 0,         //       or force it to 0 if it was undefined
      v            //       set p = v
    )              //     end of recursive call
  ) | t            //   end of map(); yield t
:                  // else:
  ++t              //   increment t
\$\endgroup\$
2
  • \$\begingroup\$ Does this pass the last three test cases “in reasonable time”? \$\endgroup\$
    – Jordan
    Sep 29, 2022 at 17:20
  • \$\begingroup\$ @Jordan 37 seconds, 3 minutes and 23 minutes respectively on my laptop. Now, I've no idea whether that's reasonable or not. (At least it does not compute all \$(n+1)!\$ permutations but aborts as soon as the expression is inconsistent.) \$\endgroup\$
    – Arnauld
    Sep 29, 2022 at 17:57
3
\$\begingroup\$

Python, 111 bytes

f=lambda s,t="",b=1:b and(s+t==""or(s<">">"<"!=t[-1:])*b*f(s[1:])*f(t[:-1])+f(s[1:],t+s[:1],b*-len(s)/~len(t)))

Attempt This Online!

Python, 118 bytes

f=lambda s,t="",b=1:(s<">">"<"!=t[-1:]and(s+t==""or b*f(s[1:])*f(t[:-1])))+(s>""and f(s[1:],t+s[0],b*-len(s)/~len(t)))

Attempt This Online!

Python, 123 bytes

f=lambda s,t="",b=1:(s[:1]!=">">"<"!=t[-1:]and(s+t==""or b*f(s[1:])*f(t[:-1])))+(s>""and f(s[1:],t+s[0],b*-len(s)/~len(t)))

Attempt This Online!

Python, 165 bytes (@Steffan)

f=lambda s,b=1:s==""or sum((b:=b*(i-len(s))/~i)
*("<"<s[i]and">">s[i+1]and f(s[i+2:])*f(s[:i]))for i in range(len(s)-1))+(s<">"and f(s[1:]))+(s[-1]>"<"and f(s[:-1]))

Attempt This Online!

Python, 174 bytes

f=lambda s,b=1:s==""or sum((b:=b*(i-len(s))/~i)
*((s[i]>"<")*(s[i+1]<">")and f(s[i+2:])*f(s[:i]))for i in range(len(s)-1))+((s[0]<">")and f(s[1:]))+((s[-1]>"<")and f(s[:-1]))

Attempt This Online!

This will surely be outgolfed to oblivion but it finishes all test cases in a second on ato.

Takes "=" instead of "-" because it sits conveniently between "<" and ">" codepointwise.

Uses a divide-and-conquer-ish approach: take the first element recurse into the two leftover halves and multiply their counts with each other and the number of ways they can be merged which is some binomial coefficient.

\$\endgroup\$
2
  • \$\begingroup\$ you have two places with redundant parens. 170 \$\endgroup\$
    – naffetS
    Sep 30, 2022 at 1:50
  • \$\begingroup\$ 168 by replacing a multiplication with and. and you can save another three by doing s<"<" instead of s[0]<"<" \$\endgroup\$
    – naffetS
    Sep 30, 2022 at 1:52
3
\$\begingroup\$

Goruby, 72 50 bytes

-28 bytes thanks to Dingus and G B.

I wasn't going to post this since it craps out on the last three test cases on ATO but it looks like I'll be in good company anyway, so here it is.

->s{[*0..s.sz].pe.ct{|a|s.a?{|t|1>t*=a.po-a[-1]}}}

Attempt This Online!

Ruby, 95 67 bytes

-22 bytes thanks to Dingus and G B.

->s{[*0..s.size].permutation.count{|a|s.all?{|t|1>t*=a.pop-a[-1]}}}

Attempt This Online!

\$\endgroup\$
6
  • \$\begingroup\$ What is GoRuby ? This redirects me to the same page as normal Ruby \$\endgroup\$
    – TKirishima
    Sep 29, 2022 at 21:11
  • 1
    \$\begingroup\$ @TKirishima Oops, the link is supposed to be this one: codegolf.stackexchange.com/questions/363/… TL;DR Goruby is a compact dialect of Ruby. \$\endgroup\$
    – Jordan
    Sep 29, 2022 at 21:14
  • 1
    \$\begingroup\$ Using ct/count instead of su/sum (thus eliminating ?1:0), [0,m<=>n][t]==t instead of t==0||t==(m<=>n), and _1 instead of |a|a saves 7 bytes in Goruby and 5 in Ruby. \$\endgroup\$
    – Dingus
    Sep 29, 2022 at 23:44
  • 1
    \$\begingroup\$ 67 bytes: ->s{[*0..s.size].permutation.count{|a|s.all?{|t|1>t*=a.pop-a[-1]}}} \$\endgroup\$
    – G B
    Sep 30, 2022 at 6:49
  • \$\begingroup\$ @Dingus Very clever. Thanks! \$\endgroup\$
    – Jordan
    Sep 30, 2022 at 15:23
2
\$\begingroup\$

Japt -x, 19 bytes

Pretty horrific brute force solution, exacerbated by me being so horribly out of practice!
Will crap out on inputs longer than 8 characters.

¬³ð á ®ã2 e@OxXqUgY

Try it

¬³ð á ®ã2 e@OxXqUgY     :Implicit input of string U
¬                       :Split
 ³                      :Push 3 (value is irrelevant, we just need an extra element)
  ð                     :0-based truthy indices (which is all of them as every element is a non-empty string, or 3)
    á                   :Permutations
      ®                 :Map
       ã2               :  Sub-arrays of length 2
          e             :  Does every pair return true
           @            :  When passed through the following function as X, at index Y
            Ox          :    Eval as JavaScript
              Xq        :      Join X with
                UgY     :      Character in U at index Y
                        :Implicit output of sum of resulting array
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 87 bytes

≔⪫--Sθ≔⦃⦄η⊞υθFυ«§≔ηιEΦ⊖Lι∧⁻>§ικ⁻<§ι⊕κ⁺⁺…ικ-✂ι⁺²κF⁻§ηιυ⊞υκ»FLθFΦυ⁼⊕ιLκ§≔ηκ∨ΣE§ηκ§ηλ¹I§ηθ

Attempt This Online! Link is to verbose version of code. Explanation: Port of @alephalpha's Mathematica answer. The number of solutions for any given string of inequalities is the sum of the numbers of solutions when the highest number is placed in any legal cell (i.e. not to the right of > or to the left of <). These numbers of solutions are equivalent to the numbers of solutions of a reduced string of inequalities where the cell and its inequalities have been replaced by a separator.

≔⪫--Sθ

Wrap the inequalities in -s. This makes the legal highest cells easier to identify.

≔⦃⦄η

Start collecting lists of reduced strings of inequalities.

⊞υθFυ«

Start a breadth-first search with the wrapped input string.

§≔ηιEΦ⊖Lι∧⁻>§ικ⁻<§ι⊕κ⁺⁺…ικ-✂ι⁺²κ

Get the possible reduced strings of inequalities for this string and save them in the dictionary.

F⁻§ηιυ⊞υκ

Add those strings that have not yet been seen to the search for further processing.

»FLθFΦυ⁼⊕ιLκ

Process the strings of inequalities in increasing order of length.

§≔ηκ∨ΣE§ηκ§ηλ¹

Update the dictionary with the total count for this string of inequalities.

I§ηθ

Output the total count for the wrapped input string.

Charcoal, 50 bytes

≔⁺-Sθ⊞υ⟦⟧Fθ≔ΣEυEΦ⁻Eθνκ∧∨⁻ι<‹↨κ⁰μ∨⁻ι>›↨κ⁰μ⁺κ⟦μ⟧υILυ

Attempt This Online! Link is to verbose version of code. Brute force, so the last few test cases will time out on ATO. Explanation:

≔⁺-Sθ

Prepend a - to the input string as the first number is not constrained by any previous number.

⊞υ⟦⟧

Start with a list of no numbers found.

Fθ

Loop over each constraint.

≔ΣEυEΦ⁻Eθνκ∧∨⁻ι<‹↨κ⁰μ∨⁻ι>›↨κ⁰μ⁺κ⟦μ⟧υ

For each list so far find all the numbers that satisfy the next constraint and create a new list of lists.

ILυ

Output the number of lists found.

\$\endgroup\$
2
\$\begingroup\$

Jelly, Fast: 47 bytes / Slow: 13 bytes

Slow:

L‘Œ!IṠnẠ¥ƇV€L

A monadic Link that accepts a list of characters - <-> represented as -01 respectively and yields the solution count.

Try it online! Or see the, truncated test-suite (shows the Link input in parentheses).

How?
L‘Œ!IṠnẠ¥ƇV€L - Link: list of characters, A, from '-01' (equivalent to '<->' respectively):
L             - length (of A)
 ‘            - increment
  Œ!          - all permutations of [1..that]
    I         - deltas (b-a for each neighbouring pair (a,b) in each list)
     Ṡ        - signs -> 1 if a<b; -1 if a>b
          V€  - evaluate each (of A) as Jelly code -> '-': -1, '0' -> 0, '1' -> 1
        ¥Ƈ    - keep those (of the delta lists) for which:
      n       -   not equal? (vectorises)
       Ạ      -   all?
            L - length

Fast:

ḅ3$Ɲ%6ỊTœP€⁸;ḊŻ$}¥/€Ñ€Sȯ1
i@‘ịɗ,Ç$;ɼ0ịƲe?®
Ø0jÇ

A monadic Link that accepts a list of integers - <-> represented as [2,0,1] respectively and yields the solution count.

Try it online! Or see the test-suite (shows the Link input in parentheses).

How?

Implements the same algorithm as alephalpha's Mathematica answer - go show some love :)

No built-in cache so this implements one. It's not got particularly great performance because (a) Jelly has no dictionary or hash-map data type, (b) Jelly only has a single register, so I keep values alongside their corresponding keys so it must search through those too (they can never match as keys are lists while values are positive integers), and (c) I went with a golfy implementation which looks up the key twice.

Note: the main Link is the one at the bottom, Ø0jÇ.

ḅ3$Ɲ%6ỊTœP€⁸;ḊŻ$}¥/€Ñ€Sȯ1 - Link 1, calculate count: list of integers, A, from [0,1,2] (equivalent to '-><' respectively):
ḅ3$Ɲ                      - convert each neighbouring pair from base 3
    %6                    - modulo by six (vectorises)
      Ị                   - insignificant? (effectively is that 0 or 1?)
       T                  - truthy indices
                            -> starts of substrings equivalent to: '->', '<-', '<>', and '--'
                               i.e. possible surrounding chars of the highest value
        œP€⁸              - partition (A) at each of those (discarding the index itself)
                 ¥/€      - reduce each by:
               $}         -   apply to the right hand one:
             Ḋ            -     dequeue
              Ż           -     prefix a zero (equivalent to a '-')
            ;             -   (left one) concatenate (that)
                    р    - call Link 2 (below) for each (if any)
                      S   - sum
                       ȯ1 - logical OR with one

i@‘ịɗ,Ç$;ɼ0ịƲe?® - Link 2, get count: list of integers, A, from [0,1,2] (equivalent to '-><' respectively):
               ® - recall from the register
                     Our cache: initially zero, but becomes a list of inputs (lists)
                                and outputs (positive integers) with a zero prefix
                                e.g. [0, [2], 1, [2,2], 1, [1], 1, [1,2], 2, ...]
                                         '<'=1   '<<'=1    '>'=1   '><'=2    ...
                                
              ?  - if...
             e   - ...condition: exists?
    ɗ            - ...then: last three links as a dyad - f(A, cache)
i@               -   index (of A) in (the cache)
  ‘              -   increment -> index of the pre-calculated value
   ị             -   index into the cache -> pre-calculated value
            Ʋ    - ...else: last four links as a monad - f(A):
       $         -   last two links as a monad - f(A):
      Ç          -     call Link 1 (above)
     ,           -     (A) paired with that
         ɼ       -     apply to the register & yield:
        ;        -       (register) concatenate (that) -> adds the "key" A (a list) and value 
          0ị     -     0 index into -> gets the value back out

Ø0jÇ - Link 3 (main Link): list of integers, A, from [0,1,2] (equivalent to '-><' respectively):
Ø0   - [0,0] (equivalent to "--")
  j  - join with A
   Ç - call Link 2 (above)

Also:

Fast version taking the characters as given in the question \$51\$ bytes:

*Ɲ%87%5ḂTœP€⁸;45;Ḋ}ʋ/€Ñ€Sȯ1
i@‘ịɗ,Ç$;ɼ0ịƲe?®
⁾--jOÇ

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E (non-competing), 16 bytes

† Non-competing, because the challenge states "your program must pass all test cases below in reasonable time", which this brute-force approach definitely doesn't do. (And yes, I know the challenge doesn't contain a tag, so it isn't a hard requirement.)

Ćāœεü2I‚øε».V]PO

Uses //1 for </>/ respectively, and takes the input as a list of characters.

Try it online or verify some of the smaller test cases.

Explanation:

Ć             # Enclose the (implicit) input-list; appending its own first item
 ā            # Push a list in the range [1,length] (without popping), which will
              # be a list in the range [1, input-length + 1] due to the enclose
  œ           # Get all permutations of this list
   ε          # Map each permutation to:
    ü2        #  Create overlapping pairs of the integer-list
      I‚      #  Pair it with the input character-list
        ø     #  Zip/transpose; swapping rows/columns
         ε    #  Map over each pair of pair + character:
          »   #   Join the inner pair by spaces, and then both items by newlines
              #   (e.g. [[1,2],"‹"] becomes "1 2\n‹")
           .V #   Evaluate and execute it as 05AB1E code
   ]          # Close both maps
    P         # Get the product of each inner list
     O        # Sum the list to get the amount of truthy values
              # (which is output implicitly as result)
\$\endgroup\$
1
\$\begingroup\$

Rust + itertools, 149 bytes

use itertools::*;|s|(1..(s.len()as i8+2)).permutations(s.len()+1).filter(|p|p.windows(2).zip(s).all(|(a,&c)|c==1||(a[1]-a[0]).signum()==c-1)).count()

Try it online!

Can be assigned to a variable of type fn(&[i8]) -> usize. It uses this mapping of characters to ints as input:

'>' 0
'<' 2
'-' 1
\$\endgroup\$
1
\$\begingroup\$

Pyth, 130 bytes

DgGHI!GR]1=Tgt^2tl.BGtH=bYVhG ab1FdUtHIv@.[\0tH.BNd=k-tHd Xb_1-/*s<>T.<.>Nktk^2tkhH.!k@b_1)))Rb;J.!hlzVcz)=/*Jegim!!xNdN2lN.!hlN;J

Try it online!

Uses input <> in place of <>-.

Okay, so... this is pretty bad. For one thing it's like 17 bytes longer than the current best python, and it's slower. Depending on what "reasonable" means it may not even meet the requirements. Alright, so why did I bother sharing it? Well because I think the algorithm is cool, and I'm really just amazed I got it to work. It uses a formula presented in this OEIS, I'll give a brief explanation.

So first we can split the sequence along any - into some number of subsequences. Our base point for the final answer is then the number of permutations of the whole sequence divided by each subsequences, this is computed with simple factorials. Then all we need is the number of valid subsequence orders. This is where the OEIS formula comes into play, it basically comes down to a particular sum of sequences one less in length than itself. We multiply all of these by the base point and that's our answer.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @JonathanAllan Fixed at the cost of 2 bytes, thanks for noticing. It was actually an issue with the way input was being interpreted. \$\endgroup\$ Oct 3, 2022 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.